Advanced
Error Estimation Method for Matrix Correlation-Based Wi-Fi Indoor Localization
Error Estimation Method for Matrix Correlation-Based Wi-Fi Indoor Localization
KSII Transactions on Internet and Information Systems (TIIS). 2013. Nov, 7(11): 2657-2675
Copyright © 2013, Korean Society For Internet Information
  • Received : February 08, 2013
  • Accepted : October 24, 2013
  • Published : November 30, 2013
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
Yong-Liang Sun
Yu-Bin Xu

Abstract
A novel neighbor selection-based fingerprinting algorithm using matrix correlation (MC) for Wi-Fi localization is presented in this paper. Compared with classic fingerprinting algorithms that usually employ a single received signal strength (RSS) sample, the presented algorithm uses multiple on-line RSS samples in the form of a matrix and measures correlations between the on-line RSS matrix and RSS matrices in the radio-map. The algorithm makes efficient use of on-line RSS information and considers RSS variations of reference points (RPs) for localization, so it offers more accurate localization results than classic neighbor selection-based algorithms. Based on the MC algorithm, an error estimation method using artificial neural network is also presented to fuse available information that includes RSS samples and localization results computed by the MC algorithm and model the nonlinear relationship between the available information and localization errors. In the on-line phase, localization errors are estimated and then used to correct the localization results to reduce negative influences caused by a static radio-map and RP distribution. Experimental results demonstrate that the MC algorithm outperforms the other neighbor selection-based algorithms and the error estimation method can reduce the mean of localization errors by nearly half.
Keywords
1. Introduction
A s demands for location-based services (LBSs) increase, accurate indoor localization techniques have been extensively researched. Satellite-based localization systems are able to offer satisfactory localization results for outdoor users [1] . However, regarding indoor environments like shopping malls, libraries and offices, satellite-based localization systems perform badly because of building barriers [2] . Thus, numerous indoor localization systems have been developed, such as RADAR system proposed by Microsoft Research offers indoor LBSs by using Wi-Fi signals [3 , 4] . Through combining Bluetooth and infrared (IR), TOPAZ can provide room-level accuracy for multiple targets at the same time [5] . Active Badge developed by AT&T Cambridge applies sensor networks to detect IR signals transmitted by IR emitters [6] . An ultrasound-based Active Bat can provide centimeter-level accuracy using trilateration [7] . LANDMARC is a localization system based on active radio-frequency identification (RFID), which adopts K-nearest neighbors (KNN) algorithm to locate RFID tags [8] . Ubisense’s ultra wideband (UWB) systems are able to provide accurate localization results with high reliability in complex indoor environments [9] .
Among these systems, Wi-Fi-based localization systems are more suitable for wide applications than the other systems because the Wi-Fi-based systems can employ widely deployed access points (APs) and commonly available Wi-Fi terminal devices [10] . Compared with the other methods that are also based on Wi-Fi such as propagation model [11] , time of arrival (TOA) [12] , time difference of arrival (TDOA) [13] , and angle of arrival (AOA) [14] , the fingerprinting method using received signal strength (RSS) has better performance under non-line-of-sight (NLOS) conditions and can be implemented for localization without hardware modification. The fingerprinting method matches on-line RSS samples with the off-line RSS samples in the radio-map to estimate localization results with a fingerprinting algorithm [15] .
The existing fingerprinting algorithms can be generally classified into two classes, fingerprinting algorithms based on neighbor selection and machine learning. The neighbor selection-based fingerprinting algorithms comprise nearest neighbor, KNN and weighted K-nearest neighbors (WKNN) [16 , 17] . The neighbor selection-based algorithms outperform the machine learning-based algorithms on adaptability, but their performances are relative to reference point (RP) distribution, number of neighbors and so on [4] . The machine learning-based fingerprinting algorithms utilize artificial intelligence techniques, like artificial neural network (ANN) [18] , support vector machine (SVM) [19] and fuzzy logic [20] . The performances of the machine learning-based fingerprinting algorithms depend on nonlinear mapping models that are trained with the radio-map in the off-line phase. If the radio signal propagation changes greatly, the nonlinear mapping models must be trained again with an updated radio-map.
To the best of our knowledge, a drawback of existing fingerprinting algorithms is that they calculate a localization result by using an RSS mean sample [3 , 18 - 20] , which fails to make use of all the available on-line RSS samples. Because usually multiple on-line RSS samples are collected at one location for calculating one localization result, in the process of calculating one RSS mean sample with the multiple on-line RSS samples, useful on-line RSS information can be lost. Thus, as one contribution of the paper, a matrix correlation (MC) algorithm is proposed to calculate one localization result with all the available on-line RSS samples forlocalization performance improvement. The other two contributions of this paper are proposed as an error estimation (EE) method that is a strong solution to localization accuracy decreasement caused by an out-of-date radio-map. A radio-map built previously may be out of date due to variations of radio signal propagation [21 - 23] . The localization performance of the fingerprinting method decreases greatly by using such radio-map. However, collecting RSS data at all the RPs for updating the whole radio-map is a laborious and time-consuming task. The whole radio-map cannot be updated frequently. So the EE method is proposed to eliminate the influence of the out-of-date radio-map to some degree with greatly reduced RSS collection effort.
Based on the analyses above, the three contributions of this paper are summarized as follows:
First, a novel fingerprinting algorithm based on MC is proposed. The proposed MC algorithm not only employs all the collected on-line RSS samples in the form of an RSS matrix for making efficient use of available on-line RSS information, but also incorporates RSS variations of RPs into correlation computations for neighbor selection to obtain more accurate localization results.
Second, an EE method is proposed to correct localization results of the MC algorithm with localization errors that are estimated by an ANN model. The ANN model is trained in the off-line phase with an easily updated database for saving great RSS update effort. When the ANN model is adapted according to radio propagation variations with easily updated training RSS data, through error corrections, the method will be consistently effective to reduce localization errors caused by an out-of-date radio-map and RP distribution.
Third, the ANN model is not only used for nonlinear mapping, but also used for data fusion. A relationship exists between localization results and localization errors of neighbor selection-based algorithms, which is proved by the experimental results in this paper. In order to employ all the available information, the localization results of the MC algorithm and on-line RSS samples are fused together to estimate localization errors.
The rest of the paper is organized as follows. In Section 2, related work is reviewed. The proposed MC fingerprinting algorithm and EE method for Wi-Fi indoor localization are given in detail in Section 3. Section 4 demonstrates experimental setup, experimental results as well as comparisons and analyses of experimental results and computational complexity. Finally, conclusions are drawn and ideas for future work are presented in Section 5.
2. Related Work
Although researchers have presented many classic fingerprinting algorithms like KNN, WKNN, ANN, SVM, and fuzzy logic, all of them calculate a localization result with a single RSS sample, usually an RSS mean sample. Because data similarities can be evaluated by correlation measurements [24 , 25] , the proposed MC algorithm not only applies correlation measurements for matching RSS matrices with all the on-line RSS samples in the form of an RSS matrix, but also incorporates RSS variations of RPs into correlation computations to obtain accurate localization results. Thus, it can make use of the available RSS data more effectively than the classic fingerprinting algorithms mentioned above.
In the area of fingerprinting-based localization, so far, no correlation measurement-based fingerprinting algorithm using RSS matrices has been presented, but Liu et al. [26] evaluated spatial correlations using correlation measurements in outdoor Wi-Fi fingerprinting localization. The spatial correlations between an RP and scanning points (SPs) nearby in the same micro cell were estimated. According to the correlation measurements, the SPs and their RSS samples were selected to estimate the RSS samples of RPs, so an outdoor radio-map could be built quickly for outdoor fingerprinting-based Wi-Fi localization.
Regarding the radio-map update, several methods have been proposed. An approach based on manifold co-regularization for radio-map update was proposed [21] . It adapted a previously learned mapping function between RSS samples and physical coordinates for latter time periods with only a small amount of new calibration data. The localization results in latter time period were estimated by a new mapping function. Yin et al. [22 , 23] presented a method of adaptive temporal radio-map for indoor localization. A few radio-frequency receivers were first placed at RPs to collect on-line RSS samples. The static radio-map was corrected by the on-line RSS samples using regression analysis. Then the static radio-map was compiled into a model tree for indoor localization. Wang et al. presented a dynamic radio-map construction method using ANN [27] . The method modeled the relationship between RSS samples at calibration points and those at RPs using an ANN model in the off-line phase. In the on-line phase, on-line RSS samples at RPs were updated by the ANN model using RSS samples collected at calibration points. A radio-map management method for localization was also proposed [28] . It first clustered RPs by using K-means clustering algorithm, and then sensors were deployed at clustering centers of these clusters to sense on-line RSS samples. Based on the on-line RSS data collected by the sensors at the clustering centers, RSS samples of all the RPs in the same cluster were updated with a propagation model.
The difference between the methods for updating radio-map mentioned above and the proposed EE method is that the EE method corrects localization results with an error estimation model that is trained with an easily updated database instead of simply updating a static radio-map with newly collected RSS data. Thus, the proposed EE method can reduce localization errors not only caused by a static radio-map, but also caused by RP distribution. Other methods of estimating localization errors for Wi-Fi-based indoor localization have also been developed. Mitilineos et al. [29] presented a technique for localization accuracy improvement through modeling localization errors. The localization error function was modeled by a polynomial approximation, which was optimized by genetic algorithm. Using the error function, more accurate localization results could be obtained. Mathematical relations of statistical errors of RADAR system, number of neighbors and number and interval of RPs in linear distribution model were also analyzed [4] . Through evaluating the statistical errors, a more accurate and reliable RADAR system could be designed and accuracy requirements for LBSs could be guaranteed. However, polynomial approximations are limited concerning their accuracy and settings of mathematical operations for evaluating the statistical errors in linear distribution model are too ideal compared to practical indoor environments. Therefore, in this study, an ANN model that has been widely used for nonlinear mapping and data fusion in engineering is applied to estimate localization errors. The ANN model is trained by back-propagation (BP) algorithm in the off-line phase using an easily updated database to guarantee accuracy of estimating localization errors and real-time error estimations in the on-line phase.
3. Error Estimation Method for Matrix Correlation Fingerprinting Localization
- 3.1 Overview of Proposed Method
As shown in Fig. 1 , like the classic fingerprinting method, the proposed MC-EE fingerprinting method also has two phases, the off-line phase and on-line phase.
In the off-line phase, some training points are labeled for ANN training, RSS data and location coordinates of the training points are recorded in a training point database. The raw RSS samples of the training points are first arranged into RSS matrices. Using the RSS matrices, localization results are computed by the proposed MC algorithm and then localization errors of the training points can be obtained. The RSS data and localization results of the training points are inputted into an ANN model as inputs and the localization errors are used as outputs for the training of the ANN model. The ANN model is optimized by BP algorithm to approximate to the nonlinear relationship between its inputs and outputs.
In the on-line phase, when a few on-line RSS samples are collected at a specific location, they are also arranged into an RSS matrix. Localization coordinates are first calculated by the same MC algorithm using the on-line RSS matrix, and then each on-line RSS value in the matrix and the localization coordinates are inputted into the trained ANN model to estimate localization errors. The localization coordinates calculated by the MC algorithm are corrected by the estimated localization errors. Thus, more accurate localization coordinates can be obtained after reducing localization errors that exist in the localization coordinates.
PPT Slide
Lager Image
Architecture of proposed method, where is an on-line RSS value collected from M th AP in N th on-line RSS sample
- 3.2 Matrix Correlation Fingerprinting Algorithm
- 3.2.1 Motivation of Matrix Correlation Fingerprinting
Classic fingerprinting algorithms based on both neighbor selection and machine learning calculate localization coordinates using a single RSS sample. Regarding classic neighbor selection-based algorithms, both the RSS samples of each RP in the radio-map and multiple on-line RSS samples collected at one location are first averaged. RPs are selected for localization through matching the on-line RSS mean sample with the RSS mean sample of each RP. Machine learning-based algorithms train nonlinear mapping functions in the off-line phase with RSS samples and location coordinates of RPs in the radio-map. In the on-line phase, after collecting multiple on-line RSS samples at one location, the RSS mean sample of the on-line RSS samples is usually inputted into the trained nonlinear functions to calculate localization coordinates.
When only one single RSS mean sample is used for indoor localization, a great deal of useful RSS information can be wasted because multiple raw on-line RSS samples are averaged to calculate one single RSS mean sample. Thus, an on-line RSS sample matrix, which comprises all the on-line RSS samples collected continuously at one location, is used to calculate localization coordinates. The correlations between the on-line RSS matrix and created RSS matrices of the RPs are measured by the MC algorithm. Additionally, through incorporating RSS variations of RPs into correlation computations as weights, RPs with more stable RSS samples are selected for localization and therefore more accurate localization results can be obtained.
- 3.2.2 Matrix Correlation Fingerprinting Algorithm Based on Neighbor Selection
The proposed MC algorithm evaluates correlations between matrices using correlation coefficients (CCs) [24] . Correlation degree between an on-line RSS matrix and the RSS matrix of one RP is measured by a CC that ranges between -1 and 1. The CC is equal to −1 in the case of the perfect negative correlation and 1 in the case of the perfect positive correlation. As the CC approaches to zero, the two RSS matrices get closer to un-correlation. The closer the CC approaches to either −1 or 1, the stronger the correlation between the two RSS matrices. In this study, the RPs that correspond to the first maximum K CCs should be selected for localization, so the proposed MC algorithm is also a neighbor selection-based fingerprinting algorithm.
Let M , L and N denote the numbers of deployed APs, labeled RPs for establishing the radio-map and on-line RSS samples, respectively. Then N on-line RSS samples are arranged into an on-line RSS matrix RSS OL with dimensions of M × N as follows:
PPT Slide
Lager Image
A total of L RSS matrices with the same dimensions of M × N are created from RSS data of the L RPs. RSS matrix
PPT Slide
Lager Image
of i th RP is denoted as:
PPT Slide
Lager Image
The CC ri denotes the correlation degree between the on-line RSS matrix RSS OL and RSS matrix
PPT Slide
Lager Image
of i th RP in the radio-map, which is calculated by:
PPT Slide
Lager Image
where
PPT Slide
Lager Image
and
PPT Slide
Lager Image
are elements in the m th row and n th column of matrix RSS OL and matrix
PPT Slide
Lager Image
, respectively.
PPT Slide
Lager Image
and
PPT Slide
Lager Image
are the means of matrix RSS OL and matrix
PPT Slide
Lager Image
, respectively.
After all the CCs are computed, they are sorted in descending order, which means the correlations between RSS OL and
PPT Slide
Lager Image
, i =1,2,⋯, L , are ranked in the same descending order. The RPs that correspond to the first K CCs in the sequence are selected and their location coordinates are averaged to calculate a localization result. The calculation process is given by:
PPT Slide
Lager Image
where { MAX _ K ( r 1 , r 2 ,⋯, r L )} is the set of the first K maximum CCs, sq and
PPT Slide
Lager Image
are location coordinates of q th selected RP and localization coordinates, respectively.
In (3), term
PPT Slide
Lager Image
describes RSS variation degree of i th RP. If RSS samples of this RP vary greatly, then the value of the term is large and the value of ri is small, which means the RP is not suitable for localization because of its unstable RSS samples. The probability of selecting this RP is small. Compared with KNN and WKNN algorithms, the proposed MC algorithm not only computes correlations between on-line RSS matrix and RSS matrices of RPs in the radio-map, but also incorporates RSS variations of RPs as weights into correlation computations. The RPs that contribute more to localization results can be selected accurately. Thus, the MC algorithm outperforms the KNN and WKNN algorithms that only calculate RSS distances between two RSS mean samples.
- 3.3 Error Estimation Method Using Artificial Neural Network
- 3.3.1 Motivation of Estimating Errors
In the off-line phase, a static radio-map is established with a great number of RSS samples collected at RPs to describe the relationship between Wi-Fi radio signals and physical location coordinates. However, indoor radio signal propagation is time-varying, which may vary remarkably because of indoor structure and layout changes. Under such condition, The RSS samples measured in the on-line phase may considerably deviate from the RSS samples in the static radio-map at the same locations. Using such radio-map for localization, fingerprinting algorithms perform poorly [21 - 23 , 27 , 28] . Additionally, regarding the neighbor selection-based fingerprinting algorithms, because localization results are obtained by averaging location coordinates of selected RPs, users at the locations that are not surrounded by RPs cannot be accurately located. The influences of RP distribution in indoor environments are unavoidable. Thus, the EE method aims to model localization errors caused by a static radio-map and RP distribution and reduce the negative influences on localization results.
- 3.3.2 Artificial Neural Network Structure for Estimating Errors
In this study, a multi-layer perceptron (MLP) network structure is applied for nonlinear mapping and data fusion [30 - 32] , which is trained by BP algorithm. Considering its function approximation ability and computational complexity, the MLP network is constructed as a three layer network with one input layer, one hidden layer and one output layer. As shown in Fig. 2 , the inputs of the MLP network are RSS data and localization coordinates calculated by the MC fingerprinting algorithm and the outputs of the MLP network are localization errors. Let M and N still denote numbers of APs and on-line RSS samples, respectively, so the number of the inputs is M × N +2 that includes all the RSS values contained in the N on-line RSS samples collected from M APs and localization coordinates in X axis and Y axis. The outputs are localization errors in X axis and Y axis.
Specifically, all the N on-line RSS samples
PPT Slide
Lager Image
, i =1,,⋯, N are combined into an RSS vector
PPT Slide
Lager Image
as part of the inputs of the MLP network, where
PPT Slide
Lager Image
, i =1,2,⋯, N . The RSS vector
PPT Slide
Lager Image
and localization coordinates
PPT Slide
Lager Image
are the inputs of the MLP network and localization errors ( δ x , δ y ) are the outputs of the MLP network. The nonlinear relationship between the inputs and outputs can be denoted by a nonlinear function F (·) given as follows:
PPT Slide
Lager Image
PPT Slide
Lager Image
Proposed MLP network structure for estimating localization errors, where M and N are the numbers of APs and on-line RSS samples, respectively
The outputs in layer l of the MLP network for sample k can be calculated by:
PPT Slide
Lager Image
where
PPT Slide
Lager Image
is the input from neuron i in layer( l -1),
PPT Slide
Lager Image
is the output of neuron j in layer l ,
PPT Slide
Lager Image
is the weight from neuron i in layer ( l -1) to neuron j in layer l ,
PPT Slide
Lager Image
is the threshold of neuron j in layer l , and f (·) is the activation function.
The errors in the output layer are computed and then are propagated backwards to update all the weights and thresholds of the MLP network. The updating process will be repeated until the maximum number of iterative epochs is reached or the total squared error of the MLP network becomes less than the expected value, which are set in the BP algorithm initialization. According to the BP algorithm, the weights and thresholds of the MLP can be updated by:
PPT Slide
Lager Image
where dj,k is the expected output of neuron j , η and γ are the learning rates for updating are the learning rates for updating weights and thresholds of the MLP network, respectively. Usually, the learning rates are adjusted adaptively to balance training time and stability.
- 3.3.3 Error Estimation Method Using Artificial Neural Network
In the off-line phase, weights and thresholds of the MLP network are optimized by BP algorithm using training point data, which include RSS samples and localization coordinates as inputs and localization errors as outputs. The detailed process of training the ANN model is shown in Fig. 3 .
PPT Slide
Lager Image
Training of ANN model in the off-line phase
Let
PPT Slide
Lager Image
, i =1,2,⋯, Q , and
PPT Slide
Lager Image
, i =1,2,⋯, Q , denote RSS training vectors and location coordinates of training points, respectively, where Q is the number of training vectors for training the ANN model and
PPT Slide
Lager Image
is the N th RSS sample received from M APs contained in i th training vector. Then i th RSS training vector
PPT Slide
Lager Image
is first arranged into an RSS matrix. Using (3) and (4), CCs are computed between the RSS matrix and RSS matrices in the radio-map denoted by (2) to obtain localization results of the training points
PPT Slide
Lager Image
. Localization errors of the training points
PPT Slide
Lager Image
, i =1,2,⋯, Q , are computed by (8):
PPT Slide
Lager Image
According to (5), the nonlinear function can be denoted as (9), which has M × N +2 inputs and 2 outputs, and it is trained with Q training vectors by BP algorithm to obtain an optimized ANN model.
PPT Slide
Lager Image
In the on-line phase, the process of estimating localization errors is shown in Fig. 4 . When N on-line RSS samples
PPT Slide
Lager Image
, i =1,2,⋯, N , are collected by a user, they are arranged into an RSS matrix denoted by (1) and used to calculate the localization coordinates of the user
PPT Slide
Lager Image
using the MC fingerprinting algorithm described by (3) and (4). The localization coordinates
PPT Slide
Lager Image
and the on-line RSS vector
PPT Slide
Lager Image
are inputted into the optimized ANN model as a vector
PPT Slide
Lager Image
to estimate the localization errors
PPT Slide
Lager Image
. Then, according to (8), the final localization coordinates
PPT Slide
Lager Image
are obtained through the error corrections given by:
PPT Slide
Lager Image
PPT Slide
Lager Image
Process of error corrections in the on-line phase
4. Experimental Results and Analyses
- 4.1 Experimental Setup
To evaluate the performance of the proposed MC-EE method, a typical office environment covering an area of 24.9m×66.4m was chosen as the experimental environment. For communication requirement, 9 Linksys WAP54G APs were deployed in the whole floor. As shown in Fig. 5 , all the experiments were carried out in a part of the floor with dimensions of 24.9m×28.0m and only 4 Linksys WAP54G APs were deployed in the experimental region. Installed a software program named NetStumbler, an ASUS A8F laptop was used to collect RSS samples with a sampling rate of 2 RSS samples per second. A total of 67 RPs with 1m gaps are chosen in the corridor and 300 RSS samples per RP were recorded to establish the radio-map. The experimental trajectory is from A to B along the 3m width corridor as marked with black stars in Fig. 5 . 1500 RSS samples were collected at training points along the experimental trajectory for training the ANN model in the off-line phase. A total of 54 testing points (TPs) were chosen with 0.6m gaps along the experimental trajectory. The RSS data at training points and TPs were collected at the same time, which is different from the time when the static radio-map was built.
PPT Slide
Lager Image
Experimental area plan
- 4.2 Localization Results of Matrix Correlation Fingerprinting Algorithm
With RSS samples collected from the experimental area, the MC algorithm is compared with the WKNN algorithm with parameters N and K varying from 1 to 20, respectively. As the experimental results shown in Fig. 6 , mean errors of the MC algorithm are generally less than those of the WKNN algorithm and the overall performance of the MC algorithm is much better and more stable than the performance of the WKNN algorithm. As parameter N increases, the mean error of the WKNN algorithm does not decrease greatly in some cases, which means some newly added RSS samples are lost in the process of calculating RSS mean samples, so they do not have contribution to localization performance improvement. Fig. 6 also shows that, when parameter K ranges from 5 to 11, the performance of the WKNN algorithm is better. But it is not easy to determine parameter K in practical application. Compared with the WKNN algorithm, the performance of the MC algorithm is not as sensitive to parameter K as that of the WKNN algorithm. It is easier to set a proper parameter K to enable the MC algorithm a good performance.
PPT Slide
Lager Image
Mean error surfaces of MC and WKNN algorithms with parameters N and K varying from 1 to 20, respectively
- 4.3 Results of Error Estimation Method Using Artificial Neural Network
Fig. 7 shows that the localization results and errors of the MC and WKNN algorithms using 20 RSS samples per TP with parameter K is set equal to 7 and parameter N is set equal to 2. In order to show the relationship between localization coordinates and errors better, the experimental results are sorted according to the order of TPs along the experimental trajectory. As shown in Fig. 7 , the relationship between the localization coordinates and errors of the neighbor selection-based algorithms is caused by RP distribution and indoor structures and layouts. For example, at the second corner on the experimental trajectory from A to B, the performances of the algorithms become worse, because the radio signal propagation at the corner is usually more complicated than straight corridors. The localization coordinates in X axis greatly deviate from their real locations, which results in significant localization errors in X axis in that area. Thus, the relationship can be employed by the proposed ANN structure to model the nonlinear function between the inputted RSS data and localization coordinates and outputted localization errors.
PPT Slide
Lager Image
Localization coordinates and errors of MC and WKNN algorithms
Based on localization results computed by the MC algorithm when parameter K is set equal to 7 and parameter N is set equal to 2, localization errors are estimated by the proposed EE method using the ANN model. When parameter N is set equal to 2, it means that 2 RSS samples collected within 1s per TP are used for localization to simulate the condition that a user moves along the experimental trajectory at a speed of 0.6m/s. The adopted ANN structure is a basic three-layer MLP with 20 inputs including 2 on-line RSS samples and localization coordinates in X axis and Y axis. The number of neurons in the hidden layer is three times of the inputs and the number of iterative epochs is set equal to 1000. Sigmoid function and linear function are selected as the activation functions for the hidden layer and output layer of the ANN model, respectively.
The localization results computed by the MC and WKNN and the results after error corrections are shown in Fig. 8 and Fig. 9 , respectively. The localization performance is obviously improved after the error corrections. The negative influence caused by the out-of-date radio-map is reduced. Once newly collected RSS samples for the ANN training are available, localization errors at training points are calculated. Then the ANN model is updated to precisely calculate on-line localization errors for error corrections. When the easily collected training point data is updated frequently, the EE method will consistently solve localization accuracy decreasement caused by the out-of-date radio-map. In addition, owing to the influences of RP distribution, the localization results in the beginning and the end of the experimental trajectory cannot approach to the real TPs. Also, at the corners of the corridor, the localization results are very inaccurate. However, after the localization results are processed by the trained ANN model, the corrected results are closer to their real locations and therefore more accurate localization results are obtained. The mean errors of the MC and WKNN in the test are 2.87m and 3.05m, respectively. By contrast, the mean errors of the MC-EE and WKNN-EE are 1.52m and 1.64m, respectively.
PPT Slide
Lager Image
Localization results of MC and MC-EE
PPT Slide
Lager Image
Localization results of WKNN and WKNN-EE
- 4.4 Comparisons and Analyses of Localization Results
With the radio-map and training point data, an ANN model of the same parameters as the ANN model for estimating localization errors is also trained as a machine learning-based fingerprinting algorithm for comparison. Using 5400 RSS testing samples, the mean error and error standard deviation of the ANN-based fingerprinting algorithm are 2.72m and 1.59m, respectively. Its performance is better than neighbor selection-based algorithms. As shown in Table 1 , the mean errors of the KNN, WKNN and MC are 2.93m, 2.91m and 2.78m, respectively. Their error standard deviations are 2.02m, 2.03m and 2.04m, respectively. However, after the error corrections, the mean errors of the KNN, WKNN and MC are reduced to 1.63m, 1.59m and 1.49m, respectively, and their error standard deviations are reduced to 1.09m, 1.11m and 1.10m, respectively. As the cumulative probability curves of these algorithms shown in Fig. 10 , the cumulative probabilities of the KNN, WKNN and MC within localization error of 2m after the error corrections increase to 70.1%, 72.9% and 75.1% from 39.3%, 40.9% and 42.3%, respectively. Within localization error of 3m, the cumulative probabilities of the corrected results can reach to 90.3%, 90.7% and 90.7%, respectively.
PPT Slide
Lager Image
Cumulative probabilities of various algorithms
Performance comparison of various algorithms
PPT Slide
Lager Image
Performance comparison of various algorithms
In order to improve localization performance, researchers have proposed several state-of-the-art fingerprinting localization systems. For example, Feng et al. proposed an RSS-based localization system using compressive sensing (CS) [33] . The mean errors of the KNN and CS-based method in [33] were 1.8m and 1.5m, respectively. The mean error was reduced by 16.7%. Based on the combination of AP selection, local discriminant embedding and clustering analysis, Deng et al. proposed a system that extracted the most discriminative features for localization while reducing the energy consumption on mobile terminals [34] . The system could achieve a mean error of 1.71m in an office environment. Compared with a mean error of 2.37m computed by the WKNN in [34] , the mean error was reduced by 27.8%. Zheng et al. proposed a semi-supervised Transferred Hidden Markov Model (TrHMM) to combine both labeled and unlabeled data for the model adaptation [35 , 36] . The model could provide accurate localization results with small calibration effort. In [35] , cumulative probabilities of the TrHMM within localization error of 2m and 3m were about 25% and 15% higher, respectively, than those of the RADAR system, which applied KNN as its fingerprinting algorithm. Fang et al. proposed a localization algorithm based on discriminant-adaptive neural network (DANN) [37] . It extracted the useful information into discriminative components for network training. Cumulative probabilities within localization error of 4m computed by the DANN and WKNN in [37] were 88.6% and 79.6%, respectively. The cumulative probability of the DANN was 9.0% higher than that of the WKNN.
By contrast, in this study, the mean errors of the KNN, WKNN and MC-EE are 2.93m, 2.91m and 1.49m, respectively. Compared with the KNN and WKNN, the mean errors are reduced by 49.1% and 48.8% by the MC-EE, respectively. The cumulative probabilities of the MC-EE within localization error of 2m and 3m are 35.8% and 31.7% higher respectively than those of the KNN. The cumulative probability of the MC-EE within localization error of 4m is 21.2% higher than that of the WKNN. Therefore, the proposed system can improve localization performance more effectively than the mentioned state-of-the-art localization systems. However, it requires a training point database to train the ANN model for estimating localization errors, which needs extra data collection effort after establishing the radio-map.
- 4.5 Complexity Analyses
Let M , L , N , and K denote the numbers of APs, RPs, on-line RSS samples collected at one location, and selected RPs, respectively. In this study, parameters M , L , N , and K are set equal to 9, 67, 2, and 7, respectively. The number of neurons in the hidden layer is three times of the number of inputs. The comparison of on-line computational complexity for calculating each localization result is shown in Table 2 . All the algorithms are run 10000 times on a computer with 2.6GHz CPU and 2G RAM. Although the on-line computational complexity of the MC algorithm is highest among these neighbor selection-based algorithms, for i th RP, differences between each component in the RSS matrix of the RP and the mean of all these components
PPT Slide
Lager Image
, where, m =1,2,⋯, M ; n =1,2,⋯, N , and its squared values denoted in (3) only need to be computed one time. The differences and their squared values of all the RPs can be stored in memory for following computations. As listed in Table 2 , the averaged execution time of each algorithm is in millisecond-level, so the proposed MC algorithm and EE method can meet real-time computing requirements for mobile terminals.
Comparison of on-line computational complexity
PPT Slide
Lager Image
Comparison of on-line computational complexity
In this study, in order to establish the database called radio-map, a total of 300×67=20100 RSS samples are collected, so it is difficult to update the whole radio-map frequently. However, only 1500 RSS samples along the experimental trajectory are collected at training points for training the ANN model, which is easily updated. Thus, negative influences of a static radio-map can be eliminated to a great degree by correcting localization results with the estimated localization errors.
5. Conclusions and Future Work
In this study, an EE solution to radio-map update for Wi-Fi localization based on MC fingerprinting algorithm is proposed. Compared with classic fingerprinting algorithms that calculate localization results using on-line RSS mean samples, the proposed MC fingerprinting algorithm calculates localization results by using all the collected RSS samples and considering RSS variations of RPs for selecting RPs. Experimental results show that the MC algorithm is able to make efficient use of the on-line RSS data and outperforms the other neighbor selection-based fingerprinting algorithms, the KNN and WKNN. Based on the MC algorithm, an EE method using ANN model is also proposed for nonlinear mapping and data fusion. The ANN model fuses all the RSS values contained in the on-line RSS samples and localization results computed by the MC algorithm as its inputs and models the nonlinear relationship between these data and its outputs, localization errors. The ANN model is first trained in the off-line phase using a training point database. In the on-line phase, localization errors are estimated by the trained ANN model and used to correct the localization results. The training point database is also much easier to be updated than the whole radio-map. Thus, the experimental results demonstrate that the proposed MC-EE method can not only improve localization performance greatly, but also offer an effective solution to radio-map update.
In the future, based on the idea of employing all on-line RSS samples, some other algorithms will be tested as fingerprinting algorithms in order to achieve higher localization accuracy. Also, the ANN model will be further optimized to estimate localization errors more precisely and other nonlinear mapping models will also be researched for estimating localization errors.
BIO
Yong-Liang Sun received the B.S. degree in Electronic Information Engineering at Harbin Engineering University in 2006 and M.S. degree in Information and Communication Engineering at Harbin Institute of Technology in 2008, respectively. Currently, he is pursuing his Ph.D. degree in Information and Communication Engineering at Harbin Institute of Technology. His main research interests include wireless localization, cognitive radio and trunking communications.
Yu-Bin Xu received the B.S. degree in radio measurement in 1986, the M.S. degree in Electronics and Communication System in 1993 and Ph.D. degree in Electronics and Communication System in 2005, all from Harbin Institute of Technology. Currently, he is a Professor and Vice Director of Communication Research Center. His research interests include wireless localization, radio-wave propagation and trunking communications.
References
Hegarty C.J. , Chatre E. 2008 “Evolution of the global navigation satellite system (GNSS)” Proceedings of the IEEE Article (CrossRef Link) 96 (12) 1902 - 1917    DOI : 10.1109/JPROC.2008.2006090
Prasithsangaree P. , Krishnamurthy P. , Chrysanthis P.K. 2002 “On indoor position location with wireless lans” in Proc. of 13th IEEE International Symposium on Personal, Indoor and Mobile Radio Communications September 15-18 Article (CrossRef Link) 720 - 724
Bahl P. , Padmanabhan V.N. 2000 “RADAR: an in-building RF-based user location and tracking system” in Proc. of 19th IEEE Computer and Communications Societies Conference March 26-30 Article (CrossRef Link) 775 - 784
Zhou M. , Xu Y.B. , Ma L. , Tian S. 2012 “On the statistical errors of RADAR location sensor networks with built-in Wi-Fi gaussian linear fingerprints” Sensors Article (CrossRef Link) 12 3605 - 3626    DOI : 10.3390/s120303605
Liu H. , Darabi H. , Banerjee P. , Liu J. 2007 “Survey of wireless indoor positioning techniques and systems” IEEE Transaction on Systems, Man, and Cybernetics-Part C: Application and Reviews Article (CrossRef Link) 37 (6) 1067 - 1080    DOI : 10.1109/TSMCC.2007.905750
Want R. , Hopper A. , Falcao V. , Gibbons J. 1992 “The active badge location system,” ACM Transactions on Information Systems Article (CrossRef Link) 10 (1) 91 - 102    DOI : 10.1145/128756.128759
Woodman O.J. , Harle R.K. 2010 “Concurrent scheduling in the active bat location system” in Proc. of 2010 8th IEEE International Conference on Pervasive Computing and Communications Workshops Article (CrossRef Link) 431 - 437
Ni L.M. , Liu Y. , Lau Y.C. , Patil A.P. 2003 “LANDMARC: indoor location sensing using active RFID” in Proc. of the First IEEE International Conference on Pervasive Computing and Communications March Article (CrossRef Link) 407 - 415
Gu Y.Y. , Lo A. , Niemegeers I. 2009 “A survey of indoor positioning systems for wireless personal networks,” IEEE Communication Surveys&Tutorials Article (CrossRef Link) 11 (1) 13 - 32    DOI : 10.1109/SURV.2009.090103
Li B.H. , Wang Y. , Lee H.K. , Dempster A.G. , Rizos C. 2005 “Method for yielding a database of location fingerprints in WLAN” IEE Proceedings Communications Article (CrossRef Link) 152 (5) 580 - 586    DOI : 10.1049/ip-com:20050078
Mazuelas S. , Bahillo A. , Lorenzo R.M. , Fernandez P. , Lago F.A. , Garcia E. , Blas J. , Abril E.J. 2009 “Robust indoor positioning provided by real-time RSSI values in unmodified WLAN networks,” IEEE Journal of Selected Topics in Signal Processing Article (CrossRef Link) 3 (5) 821 - 831    DOI : 10.1109/JSTSP.2009.2029191
Ciurana M. , Barceló F. , Cugno S. 2006 “Indoor tracking in WLAN location with TOA measurements” in Proc. of the 2006 ACM International Workshop on Mobility Management and Wireless Access October Article (CrossRef Link) 121 - 125
Yamasaki R. , Ogino A. , Tamaki T. , Uta T. , Matsuzawa N. , Kato T. 2005 “TDOA location system for IEEE 802.11b WLAN” In Proc. of IEEE Wireless Communications and Networking Conf. March 13-17 Article (CrossRef Link) 2338 - 2343
Wong C. , Klukas R. , Messier G.G. 2008 “Using WLAN infrastructure for angle-of-arrival indoor user location” in Proc. of the 68th IEEE Vehicular Technology Conf. September Article (CrossRef Link) 1 - 5
Baala O. , Caminada A. 2006 “Location precision in indoor positioning system” in Proc. of 2006 Innovations in Information Technology November 19-21 Article (CrossRef Link) 1 - 5
Xu Y.B. , Zhou M. , Meng W.X. , Ma L. 2010 “Optimal KNN positioning algorithm via theoretical accuracy criterion in WLAN indoor environment” in Proc. of 2010 IEEE Global Telecommunications Conf. December 6-10 Article (CrossRef Link) 1 - 5
Tran Q. , Tantra J.W. , Foh C.H. , Tan A.H. , Yow K.C. , Qiu D.Y. 2006 “Wireless indoor positioning system with enhanced nearest neighbors in signal space algorithm” in Proc. of 2006 IEEE 64th Vehicular Technology Conf. September 25-28 Article (CrossRef Link) 2355 - 2359
Zhou M. , Xu Y.B. , Tang L. 2010 “Multilayer ANN indoor location system with area division in WLAN environment” Journal of Systems Engineering and Electronics Article (CrossRef Link) 21 (5) 914 - 926    DOI : 10.3969/j.issn.1004-4132.2010.05.028
Brunato M. , Battiti R. 2005 “Statistical learning theory for location fingerprinting in wireless LANs” Computer Networks Article (CrossRef Link) 47 (6) 825 - 845    DOI : 10.1016/j.comnet.2004.09.004
Teuber A. , Eissfeller B. , Pany T. 2006 “A two-stage fuzzy logic approach for wireless LAN indoor positioning” in Proc. of 2006 IEEE/ION Position, Location, and Navigation Symposium April Article (CrossRef Link) 730 - 78
Pan J.L. , Kwok J.T. , Yang Q. , Pan J.F. 2007 “Adaptive localization in a dynamic WiFi environment through multi-view learning,” in Proc. of 22nd AAAI Conf. on Artificial Intelligence and the 19th Innovative Applications of Artificial Intelligence Conf. July Article (CrossRef Link) 1108 - 1113
Yin J. , Yang Q. , Ni L.M. 2008 “Learning adaptive temporal radio maps for signal-strength-based location estimation” IEEE Transactions on Mobile Computing Article (CrossRef Link) 7 (7) 869 - 883    DOI : 10.1109/TMC.2007.70764
Yin J. , Yang Q. , Ni L.M. 2005 “Adaptive temporal radio maps for indoor location estimation” in Proc. of 3rd IEEE Int. Conf. on Pervasive Computing and Communications Article (CrossRef Link) 85 - 94
Rodgers J.L. , Nicewander W.A. 1988 “Thirteen ways to look at the correlation coefficient” The American Statistician Article (CrossRef Link) 42 (1) 59 - 66    DOI : 10.2307/2685263
Zebker H.A. , Chen K. 2005 “Accurate estimation of correlation in InSAR observations,” IEEE Geoscience and Remote Sensing Letters Article (CrossRef Link) 2 (2) 124 - 127    DOI : 10.1109/LGRS.2004.842375
Liu X.C , Zhang S. , Zhao Q.Y. , Lin X.K. 2010 “A real-time algorithm for fingerprint localization based on clustering and spatial diversity” in Proc. of 2010 Int. Congress on Ultra Modern Telecommunications and Control Systems and Workshops October 18-20 Article (CrossRef Link) 74 - 81
Wang H.M. , Ma L. , Xu Y.B. , Deng Z.A. 2011 “Dynamic radio map construction for WLAN indoor location” in Proc. of 2011 3rd Int. Conf. on Intelligent Human-Machine Systems and Cybernetics August 26-27 Article (CrossRef Link) 162 - 165
Shih C.Y. , Chen L.H. , Chen G.H. , Wu H.K. , Jin M.H. 2012 “Intelligent radio map management for future WLAN indoor location fingerprinting” in Proc. of IEEE Wireless Communications and Networking Conf. April 1-4 Article (CrossRef Link) 2769 - 2773
Mitilineos S.A. , Roumeliotis G.K. , Mougiakos K.S. , Capsalis C.N. , Thomopoulos S.C.A. 2009 “Positioning accuracy enhancement using localization error modeling” in Proc. of 2009 IEEE Int. Symposium on a World of Wireless, Mobile and Multimedia Networks and Workshops June 15-19 Article (CrossRef Link) 1 - 5
Rumelhart D.E. , Hinton G.E. , Williams R.J. 1986 “Learning representations by back-propagating errors” Nature Article (CrossRef Link) 323 533 - 536    DOI : 10.1038/323533a0
Outemzabet S. , Nerguizian C. 2008 “Accuracy enhancement of an indoor ANN-based fingerprinting location system using particle filtering and a low-cost sensor” in Proc. of IEEE 67th Vehicular Technology Conf. May 11-14 Article (CrossRef Link) 2750 - 2754
Sharaf R. , Noureldin A. 2007 “Sensor integration for satellite based vehicular navigation using neural networks,” IEEE Transactions on Neural Networks Article (CrossRef Link) 18 (2) 589 - 594    DOI : 10.1109/TNN.2006.890811
Feng C. , Anthea Au W.S. , Valaee S. , Tan Z.H. 2012 “Received-signal-strength-based indoor positioning using compressive sensing” IEEE Transactions on Mobile Computing Article (CrossRef Link) 11 (12) 1983 - 1993    DOI : 10.1109/TMC.2011.216
Deng Z.A. , Xu Y.B. , Ma L. 2012 “Joint access point selection and local discriminant embedding for energy efficient and accurate Wi-Fi positioning,” KSII Transactions on Internet and Information Systems Article (CrossRef Link) 6 (3) 791 - 814
Zheng W.C. , Xiang W. , Yang Q. , Shen D. 2008 “Transferring localization models over time” in Proc. of the 23rd AAAI Conference on Artificial Intelligence July 13-17 Article (CrossRef Link) 1421 - 1426
Pan J.L. , Zheng W.C. , Yang Q. , Hu H. 2008 “Transfer learning for WiFi-based indoor localization” in Proc. of the Workshop on Transfer Learning for Complex Task of the 23rd AAAI Conference on Artificial Intelligence July 13-17 Article (CrossRef Link) 43 - 48
Fang S.H. , Lin T.N. 2008 “Indoor location system based on discriminant-adaptive neural network in IEEE 802.11 environments,” IEEE Transactions on neural networks Article (CrossRef Link) 19 (11) 1973 - 1978    DOI : 10.1109/TNN.2008.2005494