Abstract
Due to the increasing requirements of the seamless and round-the-clock Location-based services (LBSs), a growing interest in Wi-Fi network aided location tracking is witnessed in the past decade. One of the significant problems of the conventional Wi-Fi location tracking approaches based on received signal strength (RSS) fingerprinting is the time-consuming and labor intensive work involved in location fingerprint calibration. To solve this problem, a novel unlabeled Wi-Fi simultaneous localization and mapping (SLAM) approach is developed to avoid the location fingerprinting and additional inertial or vision sensors. In this approach, an unlabeled mobility map of the coverage area is first constructed by using the crowd-sourcing from a batch of sporadically recorded Wi-Fi RSS sequences based on the spectral cluster assembling. Then, the sequence alignment algorithm is applied to conduct location tracking and mobility map updating. Finally, the effectiveness of this approach is verified by the extensive experiments carried out in a campus-wide area.
1. Introduction
Location tracking in wireless mobile environments plays an important role in recent development of Location-based services (LBSs), such as visitor navigation, elderly health care, facility management, transportation, and emergency rescue [1–3]. With the significant growing interests in Wi-Fi technology and the ubiquitous deployment of Wi-Fi infrastructures, intense attention has been paid to various approaches of Wi-Fi network aided location tracking [4]. Location tracking using Wi-Fi received signal strength (RSS) fingerprints presents many challenges due to less predictable variations of RSSs with respect to the distances from the access points (APs) to the receiver. The Wi-Fi network aided location tracking approaches can be generally classified into two categories. In the first one, only Wi-Fi RSS data are used to estimate the parameters in propagation models [5, 6] or construct a radio map corresponding to the coverage area [7, 8]. Then, the target locations are estimated based on the propagation model aided triangulation algorithm or radio map aided fingerprint matching. The major limitations of such category are that (i) the RSS propagation modeling requires the prior knowledge of AP locations and easily leads to the low accuracy when the relations between the RSSs and their corresponding distances are not captured appropriately and (ii) the construction of radio map usually involves the site survey over a large number of reference points (RPs) and their associated RSSs, which deteriorates the adaptability for the large coverage area, and meanwhile the radio map can easily become outdated.
In the second one, the Wi-Fi RSSs and the acquired measurements from several different types of inertial and vision sensors are integrated to achieve simultaneous localization and mapping (SLAM) [9]. The SLAM approach can be used to construct the virtual floor plan corresponding to the coverage area, meanwhile conducting location tracking. Although the RSS propagation modeling and radio map construction are not required, the combined problem of target localization and mobility mapping needs to be significantly concerned in order to make the SLAM approach robust to the radio noise. Specifically, the mobility mapping built up from the environment helps to keep tracking of the target locations, while the results of location tracking feed the process of the mobility mapping. The aim of this paper is to use solely Wi-Fi network to construct a mobility map without location fingerprinting and inertial or vision sensing (or called unlabeled mobility map) for the coverage area. Moreover, the proposed approach is expected to achieve a high-enough probability of locating the new RSS data into the corridor where these data are actually recorded, namely, the corridor-level location accuracy. In summary, the following two problems are resolved in this paper.
(i) How to construct an unlabeled mobility map by using crowd-sourcing based on the sporadically recorded RSS data without explicit information of their physical coordinates?
(ii) How to simultaneously conduct location tracking and mobility map updating?
The solution to the construction of the unlabeled mobility map is by spectral cluster assembling, which consists of the intrasequence spectral clustering step and the intersequence cluster assembling step. The solution to the target location tracking and mobility map updating is called sequence alignment algorithm, which matches the new RSS data against the constructed mobility map and selects the location point (LP) with the highest alignment similarity as the tracked location for each location query.
Solution 1 (spectral cluster assembling). Mobility map construction by using crowd-sourcing consists of two main steps: intrasequence clustering and intersequence assembling. In the intrasequence clustering step, each string of time-stamped consecutive RSS samples recorded by the person is first represented as an RSS sequence, where the RSS samples in each sequence are sequenced in chronological order. Then, for any recorded RSS sequence, spectral clustering is performed on this sequence to classify the RSS samples into different clusters. The spectral clustering used in this paper preserves the locality of RSS samples in RSSs and time-stamps. Another significant advantage of spectral clustering is that the RSS samples which are high-dimensional can be mapped into a low-dimensional space, which is beneficial to the information retrieval and data mining [10]. Specifically, after an RSS sequence is recorded, the similarity of every two RSS samples in this sequence is first calculated, and then a low-dimensional mapped space is constructed by using Laplacian embedding. Finally, the -means clustering is performed to classify the RSS samples into different clusters.
In the intersequence assembling step, the concept of winning path used in Smith-Waterman algorithm for protein sequencing [11] is first applied to identify the clusters which have high similarities between each other. The similarity of any two clusters is measured by their cumulative matching score, which is calculated based on the Kullback-Leibler (KL) divergence of their RSS distributions and the cumulative matching scores of several previous pairs of clusters (or called pairs of clusters with time-stamps before the current pair of clusters). After the matrix of cumulative matching scores between the clusters, namely, the scoring space, for each pair of RSS sequences is obtained, the pairs of RSS sequences having one or more pairs of clusters with the cumulative matching scores higher than a given threshold are required to be assembled, while the corresponding pairs of clusters are merged into a new cluster. This process is repeated until all the remaining pairs of clusters are with the cumulative matching scores lower than the threshold. At this point, each remaining cluster is recognized as an LP in mobility map.
Solution 2 (sequence alignment algorithm). For the purpose of simultaneously conducting location tracking and mobility map updating, the three RSS sequences containing the largest number of RSS samples, namely, the three longest RSS sequences, in each LP is first selected as the virtual fingerprints. The concept of sequence alignment in protein sequencing is then used to find the strings of tracking LPs which have the highest alignment similarities to the new RSS sequences. Finally, based on the time-stamped transition relations of LPs, the target locations can be tracked by using the modified strings of tracking LPs with the improved accuracy performance. A preliminary discussion on the time-stamped transition relations of LPs in mobility map can be found in the previous work [4]. In this paper, to validate the construction of mobility map by using crowd-sourcing and the unlabeled Wi-Fi SLAM, extensive experiments are conducted in a campus-wide area.
The remainder of this paper is organized as follows. Section 2 reviews some related work on SLAM based location tracking. In Section 3, the steps of the proposed crowd-sourced mobility mapping for location tracking without the site survey on location fingerprinting and inertial or vision sensing are described in detail. The experimental results and the related discussions are shown in Section 4. Finally, this paper is concluded in Section 5.
2. Related Work
Tracking the target locations cost-efficiently by using the conventional RSS propagation modeling and construction of radio map is a challenging work since both of them involve the time-consuming and labor intensive site survey on the relations between RSSs and physical locations [12, 13]. To achieve the cost-efficiency purpose, the recent works began to focus on the SLAM based location tracking approaches, which have good adaptability to the environment with low site survey effort and high robustness to the environment noise.
Wang and Thorpe [14] integrated the SLAM and detection and tracking of moving objects (DTMO) approaches and verified the efficiency of the integrated SLAM and DTMO at high speed in a large crowded city environment. A simulation system is designed to be implemented to analyze and validate the SLAM based on the well-known extended Kalman filter (EKF) [15]. There are generally three major approaches studied for SLAM, optimal control approach, local submap approach, and frontier based approach, to achieve the localization and mapping purposes in an active and intelligent way. Similar work on Kalman filter (KF) based SLAM has been addressed extensively in the literature [16, 17]. Chatterjee and Matsuno [16] introduced a new approach of using the neurofuzzy assisted EKF to enhance the performance of SLAM. There are two limitations of this approach. First of all, to suitably use the neurofuzzy supervision, the free parameters of neurofuzzy system are required to be learned carefully. Second, this approach could be unavailable when the process and sensor noise covariance matrices are inaccurate. To improve the accuracy and fast convergence of state estimation involved in KF, the pseudolinear model based Kalman filter (PLKF) based SLAM is proposed [17]. The PLKF based SLAM outperforms the conventional EKF based SLAM since the pseudolinear model preserves the nonlinearity in the system, motion, and observation models.
Wang et al. [18] proved that the particle filtering (PF) can also be used to improve the performance of SLAM. The PF can not only reduce the complexity of the data but also enhance the real-time capacity of SLAM. The weakness of the PF based SLAM is that many types of sensors and the related data fusion process are required to guarantee the effectiveness of the feature extraction in the unknown and highly complex environments. The Rao-Blackwellised particle filter (IRBPF) based SLAM is used to achieve the accurate localization and generate a consistent map of the environment [19]. The IRBPF based SLAM first uses PF to estimate the posterior probability distributions of the target. The adaptive resampling approach is then applied to reduce the risk of sample depletion. Finally, the motion and observation models are constructed based on the data from a ranging sensor and an odometer. However, this approach is not suitable for the highly dynamic environment.
Luo et al. [20] presented a new concept of vision based SLAM (V-SLAM), in which the visual feature point buffer and human body elimination are used to decrease the estimative errors to the system. Specifically, the V-SLAM implements the visual feature point buffer to filter the temporary feature points which are extracted from features from accelerated segment test (FAST) corner detector and conducts the human body elimination to help V-SLAM to be more accurate. As an application example, the V-SLAM is used to aid inertial navigation by compensating for inertial navigation divergence [21]. Sazdovski and Silson [21] proved that such an integrated inertial navigation system with V-SLAM requires the coordination between the guidance and control measurements to achieve the high navigation accuracy.
The aforementioned SLAM is based on the single target and single model. The decentralized platform developed by Saeedi et al. [22] is known as the first application of neural network for SLAM in multiple targets condition. Their proposed approach consists of five modules of the high-level map segmentation for map preprocessing, application of self-organizing maps for preprocessed map clustering, inclusion of map uncertainty in learning phase, estimation of the relative transformation matrix of every two maps, and use of surface norms for relative transformation determination. Yingmin and Ding [23] investigated the nonlinear interacting multiple model (IMM) based SLAM to solve the problem of the statistical property mutation of SLAM. There are five steps involved in the nonlinear IMM based SLAM, the model condition reinitialization, model condition filtering and data association, model probability updating and estimate fusion, and state augmentation and map building.
By considering the indoor Wi-Fi network, the Wi-Fi SLAM is invented to gather the location and mapping information simultaneously [24]. Specifically, the Wi-Fi SLAM first uses the location fingerprinting to get an idea of what the construction of a particular building is going to do to Wi-Fi RSS distributions. The initial trajectories are then constructed based on the measurements from multiple sensors on a smartphone including the accelerometer, gyroscope, and magnetometer. Finally, the constructed trajectories are mated with the results of Wi-Fi RSS trilateration to serve fine-grain localization and create accurate indoor maps. Since the measurements are gathered by different sensors, the Wi-Fi SLAM uses pattern recognition and machine learning to draw the correlations between these measurements for data fusion purpose. The SmartSLAM is recognized as another representative Wi-Fi network based SLAM by using the measurements from inertial sensors and Wi-Fi network [9]. One of the significant problems of SmartSLAM is that the high energy cost involved in continuously scanning multiple sensors and Wi-Fi channels seriously limits the practical use.
In this paper, a better solution will be provided to the simultaneous mobility mapping and location tracking by using crowd-sourcing from the sporadically recorded Wi-Fi RSS data without location fingerprinting and inertial or vision sensing. In summary, the three major contributions of this paper are as follows.
(i) An unlabeled Wi-Fi SLAM approach is developed to avoid the location fingerprinting and additional inertial or vision sensors.
(ii) The mobility map is constructed by using crowd-sourcing based on the sporadically recorded Wi-Fi RSS data without explicit information of their physical coordinates.
(iii) The concept of alignment similarities between the newly recorded RSS data and prestored virtual fingerprints is utilized to achieve the location tracking.
The major notations and parameters used in this paper are summarized in Notations and Parameters section.
3. System Description
3.1. Intrasequence Clustering
3.1.1. Problem Statement
In the system, each person holding a Wi-Fi RSS receiver walks around the coverage area and collects Wi-Fi RSS sequences. It is assumed that such sequences are collected where is the th sequence and is the th sample (of dimensions ) in which contains samples. Each sample is a vector containing the RSS values from APs. The th () element in , is the RSS value from the th AP. The difference in RSSs and time-stamps between any two RSS samples in the same sequence is calculated by and where is the time-stamp of in and is the sampling interval.
Here, the intrasequence clustering problem is as follows. Given a set of RSS samples belonging to a -dimensional mapped space , which is embedded in the raw -dimensional RSS space , a set of mapped vectors in is first found such that is mapped from , and then the mapped vectors are classified into RSS clusters. Finally, the RSS samples which have the corresponding mapped vectors in the same cluster are also classified into the same RSS cluster.
The first advantage of intrasequence clustering is that the similarities of RSS samples in RSSs and time-stamps between any two clusters are minimized. Second, the graph Laplacian which is selected for dimensionality reduction can avoid the situation that the isolated RSS samples accidentally form some outlier RSS clusters by minimizing the values of Ncut over all the RSS clusters [10, 25].
3.1.2. Steps
The steps of intrasequence clustering are provided as follows.
Step 1. The similarity of and is computed as , where and are two tunable weighting factors and and are the normalized values of and , respectively.
Step 2. Consider the problem of mapping the RSS samples in each sequence onto a line such that the RSS samples with large similarities in RSSs and time-stamps are corresponding to the mapped points which can stay as close together as possible on the line. Let be the set of the mapped points. The optimal objective function to this problem can be described as .
Step 3. Compute the Laplacian matrix for each RSS sequence. If , is set as . Otherwise, is set as 0. By using the Lagrange multiplier method [4], the problem described in Step 2 is converted to , where ’s are the eigenvalues of .
Step 4. Consider the general problem of mapping each RSS sequence (of dimensions ) into the -dimensional space, where . The set of mapped vectors, namely, the mapped sequence, is given by a matrix , where is the mapped vector of and the superscript “” represents the transpose operation. Thus, the optimal objective function to this general problem equals . Based on the previous work [4], the solution to this optimal objective function can be provided by the eigenvectors which are corresponding to smallest eigenvalues of the generalized eigenvalue problem .
Step 5. As discussed in the literature [10, 26], the process of the previous dimensionality reduction which preserves the locality of RSS samples in RSSs and time-stamps can also yield a similar solution to the RSS clustering. In concrete terms, after the dimensionality reduction from to , -means clustering is conducted on the mapped vectors to obtain RSS clusters for each RSS sequence, where is the th RSS cluster in .
3.2. Intersequence Assembling
3.2.1. Problem Statement
The problem to be solved by intersequence assembling is to assemble the RSS clusters obtained in intrasequence clustering step into a mobility map. Since each RSS sequence can be represented by a string of consecutive time-stamped RSS clusters, , the concept of winning path in scoring space used by Smith-Waterman alignment is applied to identify the RSS clusters required to be merged. By considering the process of clusters combination graphically, each string of consecutive time-stamped RSS clusters is first viewed as a string of consecutive vertices in a graph, where any two adjacent vertices are connected by an edge. Second, the string assembling is conducted by merging the specific vertices in different strings. Finally, after all the strings of consecutive vertices have been assembled, the mobility map is constructed in which and represent the sets of vertices and edges in graph, respectively.
3.2.2. Steps
The four steps of intersequence assembling are as follows.
Step 1. For every two strings of consecutive vertices and , their initial scoring space is set as a zero matrix . The entry at position in scoring space is the cumulative matching score between and .
Step 2. The entries in scoring space are calculated starting at position and proceeding from the first to the last rows in scoring space. The entry at position , , is calculated that (i) when , ; (ii) when , ; (iii) when , , and , ; and (iv) otherwise, one haswhere and are the missing factor and the damping factor, respectively; is a threshold; and . and are the probabilities of RSS value under the RSS distributions in and , respectively.
Step 3. The winning path creation is started at the position with the largest entry, namely, the first position on the winning path, in scoring space, such thatwhere is a threshold.
After the first position on the winning path is obtained, it is required to go backwards to one of positions, , , and , and compare the entries of these three positions, , , and . A connection from to , notated as , is constructed as the first jump on the winning path, where
This process is continued until the winning path reaches the first row or the first column in scoring space or reaches a position with the entry not larger than the threshold .
Step 4. After the winning path is created, the specific RSS clusters in and , respectively, are merged based on the concept of jumps used in Smith-Waterman alignment [27]. It is required to start from the last jump and go forward to the first jump on the winning path to identify the specific RSS clusters to be merged. There are three types of jumps involved [27]: (i) diagonal jump implying that and are required to be merged into a LP; (ii) top-down jump implying that is an isolated LP; and (iii) left-right jump implying is an isolated LP. Figure 1 gives an example of the winning path creation, while the two RSS sequences and happen to be both with four RSS clusters in length. Based on the created winning path in Figure 1, we can obtain three pairs of RSS clusters to be merged into , , and , respectively, and eventually construct a mobility map containing 5 LPs, notated as LP , and 5 transitions, notated as Tran. , between the LPs.
3.3. Sequence Alignment Algorithm
So far, the mobility map has been constructed based on the intrasequence clustering and intersequence assembling steps. In this subsection, the algorithm used for location tracking will be investigated based on the constructed mobility map. The target locations are tracked as follows.
Step 1. In each LP , the RSS sequences with the largest number of RSS samples are selected as the virtual fingerprints , where is the number of RSS samples in , namely, length of .
Step 2. By assuming that the interval of location query is , the segment of RSS samples used for the th location query is , where and the notation “” represents the rounding operation. If is selected as the tracked location for the th location query, where is the alignment similarity between and . In (4), is calculated that (i) when or , ; (ii) when , , and , ; and (iii) otherwise, one haswhere is a threshold.
Step 3. After the tracked locations are obtained, the tracked motion path will be constructed by the following steps.
First of all, it is defined that if the difference of average time-stamps of the RSS samples in and , respectively, is smaller than , then is in the -neighborhood of . On this basis, it is noted that the -neighborhood relationship is naturally symmetric.
Second, by setting as the set of tracked locations which are in the -neighborhood of , one has that (i) if , is left in the set of tracked locations, and it is continued to examine whether is in the -neighborhood of ; and (ii) otherwise, it is continued to examine whether is in the -neighborhood of . When , both and are left in the set of tracked locations, and it is continued to examine whether is in the -neighborhood of . Otherwise, is removed from the set of tracked locations, and it is continued to examine whether is in the -neighborhood of . This process is repeated until the most recent tracked location is reached or one obtainsIn the former case, all the tracked locations with the time-stamps after are removed, whereas, in the latter case, is left in the set of tracked locations and it is continued to examine whether is in the -neighborhood of .
Finally, the tracked locations that remain are connected in chronological order along the path passing by the smallest number of LPs in mobility map as the tracked motion path. To conduct mobility map updating, the segments of RSS samples are merged into their corresponding tracked locations.
4. Experimental Results
4.1. Experimental Setup
In this section, we will evaluate the performance of our proposed approach for mobility map construction and location tracking on four representative paths in HKUST campus, as shown in Figure 2. They are path 1 between Lab 2149 and North Entrance; path 2 between Lab 2149 and LT-J Theater; path 3 between Lab 2149 and Coffee Shop; and path 4 between Coffee Shop and Library. A summary of these four paths is given in Table 1.
Two planned volunteers hold tablet computers which have the self-developed Wi-Fi RSS scanner software installed and walk along the four paths. On each path, each volunteer has recorded 10 RSS sequences with 5 of them in forward direction, whereas the rest in backward direction. The RSS sequences on each path are with the same sampling rate of 1 Hz (i.e., s) and the same dimensions of 650 (i.e., ). During the testing, the data recorded by volunteer 1 are first used to show the result of the constructed mobility map, and then the data recorded by volunteer 2 are used to examine the performance of location tracking.
4.2. Test of Mobility Map Construction
4.2.1. Results of Intrasequence Clustering
For comparison, the other two widely used approaches for intrasequence clustering are conducted: -means clustering, a baseline approach designed for data clustering [28], and affinity propagation clustering, a state-of-the-art approach that is based on the concept of exchanging the responsible and availability messages among the data [29].
The parameters involved in intrasequence clustering are not specifically fine-tuned. Instead, they are determined at a coarse level. It is set that , , , s, and equals the average of distances of every two RSS samples with 30 s time-stamp difference.
The results, shown in Figure 3, are produced by -means clustering (KMC), affinity propagation clustering (APC), and intrasequence clustering (ISC) which are conducted on each path. Different clusters are indicated by different symbols.
(a) KMC on path 1
(b) APC on path 1
(c) ISC on path 1
(d) KMC on path 2
(e) APC on path 2
(f) ISC on path 2
(g) KMC on path 3
(h) APC on path 3
(i) ISC on path 3
(j) KMC on path 4
(k) APC on path 4
(l) ISC on path 4
In Figure 3, it is observed that the proposed intrasequence clustering not only preserves the locality of RSS samples in each sequence but also exhibits better adaptation to different path lengths compared to the -means clustering and affinity propagation clustering. The results on path 1 are taken for instance. By -means clustering, Cluster 3 which contains very few RSS samples tends to lead to poor clustering performance, while Cluster 6 which is generated by affinity propagation clustering contains too many RSS samples results in the degradation of position resolution of RSS clusters.
4.2.2. Results of Intersequence Assembling
In this subsection, the result of mobility map construction by intersequence assembling will be shown. For simplicity, the intersequence assembling is first conducted on the RSS sequences which are recorded on each path, and then they are assembled into the complete mobility map. Figure 4 shows the scoring spaces between the first recorded RSS sequence and the other 9 RSS sequences on each path. It is set that , , and and equal the largest entry in scoring space and the average of KL divergence of RSS distributions of every two RSS clusters, respectively.
(a) On path 1
(b) On path 2
(c) On path 3
(d) On path 4
As can be seen from Figure 4, it is found that (i) similar variation patterns of entries in scoring space can be found for any two pairs of RSS sequences with the same directions on each path and (ii) the entries in scoring space corresponding to the pair of sequences in the same direction are generally larger than the ones in scoring space corresponding to the pair of sequences in opposite directions. After the scoring spaces are obtained, it is continued to identify the specific RSS clusters required to be merged based on the concept of jumps used in Smith-Waterman alignment. Figure 5(a) shows the results of intersequence assembling on each path. The th RSS cluster in sequence on paths 1, 2, 3, and 4 is notated as , , , and , respectively, and the th merged RSS cluster on paths 1, 2, 3, and 4 is notated as , , , and , respectively. Furthermore, for simplicity, the RSS clusters that are not merged (e.g., ) will not be considered during the intersequence assembling among different paths since these isolated RSS clusters which contain very few RSS samples generally represent the locations where the target rarely visited.
(a) Assembling on each path
(b) Assembling among different paths
After the assembled RSS sequence on each path is obtained, it is continued to assemble the RSS sequences among different paths into the complete mobility map. To do this, the cumulative matching scores between the merged RSS clusters in different assembled RSS sequences are first calculated. Figure 6 shows the cumulative matching scores between the merged RSS clusters on path 1 and the ones on paths 2, 3, and 4. Based on the created winning paths which are indicated by red box symbols, the mobility map consisting of 13 LPs and 12 transitions is eventually obtained, as shown in Figure 5(b).
4.3. Test of Location Tracking
The aim of this subsection is to verify that, by employing the proposed sequence alignment algorithm, the target locations can be tracked accurately in the mobile scenario. To examine whether sequence alignment algorithm can achieve corridor-level accuracy, the corridor-level segmentation is conducted on the constructed mobility map. The segmented corridors in mobility map are Corridor 1 “LP1, LP2,” Corridor 2 “LP3, LP4,” Corridor 3 “LP5, LP6,” Corridor 4 “LP7, LP8, and LP9,” Corridor 5 “LP10, LP11,” and Corridor 6 “LP12, LP13.” It is set that , s, and equals the average of distances of the newly recorded RSS samples and the ones in virtual fingerprints. Figure 7 shows the alignment similarities of the segments of RSS samples and the LPs. The real location of the target for each location query is indicated by a red box symbol. The A-1, A-5, and A-10 stand for the situations that only the first sequence, the 5 sequences in the same direction, and all the 10 sequences are used, respectively, for the testing.
(a) A-1 on path 1
(b) A-5 on path 1
(c) A-10 on path 1
(d) A-1 on path 2
(e) A-5 on path 2
(f) A-10 on path 2
(g) A-1 on path 3
(h) A-5 on path 3
(i) A-10 on path 3
(j) A-1 on path 4
(k) A-5 on path 4
(l) A-10 on path 4
From Figure 7, it is found that (i) similar patterns of alignment similarities for A-1, A-5, and A-10 situations can be found on each path and (ii) compared to A-1 situation, higher alignment similarities are obtained in A-5 and A-10 situations, whereas the ones in A-5 and A-10 situations are similar. To illustrate this result clearer, Figure 8 shows the alignment similarities achieved by the tracked locations, namely, highest alignment similarities, in A-1, A-5, and A-10 situations on each path.
(a) On path 1
(b) On path 2
(c) On path 3
(d) On path 4
Finally, Figure 9 illustrates the variations of probabilities of locating the target locations in correct corridors and LPs as the interval of location query increases from 5 s to 20 s. In Figure 9, It is found that (i) the largest mean of probabilities in correct corridors and LPs, 91.0% and 69.4%, are obtained in the condition of s; and (ii) the probabilities in correct corridors and LPs with respect to s, 88.1% and 65.6%, are slightly lower than the ones achieved by s, whereas the real-time capacity is significantly enhanced.
(a) Corridor-level accuracy
(b) LP-level accuracy
5. Conclusions
In this paper, the crowd-sourced mobility mapping approach is proposed to solve the problem of location tracking in Wi-Fi area by using a new concept of unlabeled Wi-Fi SLAM. In the system, spectral cluster assembling is first applied to construct an unlabeled mobility map corresponding to the Wi-Fi coverage area, and then sequence alignment algorithm is used to simultaneously track the target locations and conduct mobility map updating. Extensive experiments in a campus-wide area prove that high accuracy of location tracking can be achieved without the site survey on location fingerprinting and motion sensing which are adopted by many existing Wi-Fi location systems. Furthermore, the proposed approach can also construct mobility map by using the crowd-sourcing from massive and high-dimensional Wi-Fi RSS data which are sporadically recorded in large-scale area.
The significance of this paper is that both the RSS and time-stamp relations of the sporadically recorded Wi-Fi RSS data are used to conduct the crowd-sourced mobility mapping, and meanwhile alignment similarities between the newly recorded segments of RSS samples and prestored virtual fingerprints are considered to track the target locations. In future, the performance of integrating the time-stamped Wi-Fi RSS data with the data from inertial measurement unit (IMU) will be investigated to try to construct a more precise mobility map. For instance, the transitions among different LPs in mobility map can be better described by the moving speed and orientation of the target compared to the difference of time-stamps of RSS samples, and meanwhile more parameters may also be varied, such as the thresholds for scoring space construction and winning path creation in the intersequence assembling step, and also the threshold for alignment similarity calculation in sequence alignment algorithm.
Notations and Parameters
| : | Number of RSS sequences |
| and : | Number of samples in and |
| : | Number of Aps |
| : | Number of virtual fingerprints in each RSS cluster |
| and : | th RSS sequence of samples and clusters |
| : | Number of RSS clusters in |
| : | th sample in |
| : | Sample mapped from |
| : | th RSS cluster in |
| : | Tracked location for the th location query |
| : | Time-stamp of in |
| : | RSS value from the th AP in |
| : | Similarity between and |
| : | th virtual fingerprint in |
| : | Segment of samples used for the th location query |
| and : | Cumulative matching score and KL divergence between and |
| : | Set of tracked locations in -neighborhood of |
| : | Sampling interval |
| and : | Weighting factors for time-stamps and RSSs |
| and : | Missing and damping factors |
| and : | and -dimensional spaces. |
Conflict of Interests
The authors declare that there is no conflict of interests regarding the publication of this paper.
Acknowledgments
The authors wish to thank the editor and reviewers for the careful review and valuable suggestions. This work was supported in part by the Program for Changjiang Scholars and Innovative Research Team in University (IRT1299), National Natural Science Foundation of China (61301126, 61471077), Special Fund of Chongqing Key Laboratory (CSTC), Fundamental and Frontier Research Project of Chongqing (cstc2013jcyjA40041, cstc2013jcyjA40032), Scientific and Technological Research Program of Chongqing Municipal Education Commission (KJ130528), Startup Foundation for Doctors of CQUPT (A2012-33), Science Foundation for Young Scientists of CQUPT (A2012-77), and Student Research Training Program of CQUPT (A2013-64).