A novel neighbor selectionbased fingerprinting algorithm using matrix correlation (MC) for WiFi 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 online RSS samples in the form of a matrix and measures correlations between the online RSS matrix and RSS matrices in the radiomap. The algorithm makes efficient use of online RSS information and considers RSS variations of reference points (RPs) for localization, so it offers more accurate localization results than classic neighbor selectionbased 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 online phase, localization errors are estimated and then used to correct the localization results to reduce negative influences caused by a static radiomap and RP distribution. Experimental results demonstrate that the MC algorithm outperforms the other neighbor selectionbased algorithms and the error estimation method can reduce the mean of localization errors by nearly half.
1. Introduction
A
s demands for locationbased services (LBSs) increase, accurate indoor localization techniques have been extensively researched. Satellitebased localization systems are able to offer satisfactory localization results for outdoor users
[1]
. However, regarding indoor environments like shopping malls, libraries and offices, satellitebased 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 WiFi signals
[3
,
4]
. Through combining Bluetooth and infrared (IR), TOPAZ can provide roomlevel 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 ultrasoundbased Active Bat can provide centimeterlevel accuracy using trilateration
[7]
. LANDMARC is a localization system based on active radiofrequency identification (RFID), which adopts Knearest 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, WiFibased localization systems are more suitable for wide applications than the other systems because the WiFibased systems can employ widely deployed access points (APs) and commonly available WiFi terminal devices
[10]
. Compared with the other methods that are also based on WiFi 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 nonlineofsight (NLOS) conditions and can be implemented for localization without hardware modification. The fingerprinting method matches online RSS samples with the offline RSS samples in the radiomap 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 selectionbased fingerprinting algorithms comprise nearest neighbor, KNN and weighted Knearest neighbors (WKNN)
[16
,
17]
. The neighbor selectionbased algorithms outperform the machine learningbased algorithms on adaptability, but their performances are relative to reference point (RP) distribution, number of neighbors and so on
[4]
. The machine learningbased 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 learningbased fingerprinting algorithms depend on nonlinear mapping models that are trained with the radiomap in the offline phase. If the radio signal propagation changes greatly, the nonlinear mapping models must be trained again with an updated radiomap.
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 online RSS samples. Because usually multiple online RSS samples are collected at one location for calculating one localization result, in the process of calculating one RSS mean sample with the multiple online RSS samples, useful online 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 online 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 outofdate radiomap. A radiomap 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 radiomap. However, collecting RSS data at all the RPs for updating the whole radiomap is a laborious and timeconsuming task. The whole radiomap cannot be updated frequently. So the EE method is proposed to eliminate the influence of the outofdate radiomap 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 online RSS samples in the form of an RSS matrix for making efficient use of available online 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 offline 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 outofdate radiomap 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 selectionbased 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 online 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 WiFi 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 online 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 fingerprintingbased localization, so far, no correlation measurementbased fingerprinting algorithm using RSS matrices has been presented, but Liu et al.
[26]
evaluated spatial correlations using correlation measurements in outdoor WiFi 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 radiomap could be built quickly for outdoor fingerprintingbased WiFi localization.
Regarding the radiomap update, several methods have been proposed. An approach based on manifold coregularization for radiomap 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 radiomap for indoor localization. A few radiofrequency receivers were first placed at RPs to collect online RSS samples. The static radiomap was corrected by the online RSS samples using regression analysis. Then the static radiomap was compiled into a model tree for indoor localization. Wang et al. presented a dynamic radiomap 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 offline phase. In the online phase, online RSS samples at RPs were updated by the ANN model using RSS samples collected at calibration points. A radiomap management method for localization was also proposed
[28]
. It first clustered RPs by using Kmeans clustering algorithm, and then sensors were deployed at clustering centers of these clusters to sense online RSS samples. Based on the online 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 radiomap 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 radiomap with newly collected RSS data. Thus, the proposed EE method can reduce localization errors not only caused by a static radiomap, but also caused by RP distribution. Other methods of estimating localization errors for WiFibased 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 backpropagation (BP) algorithm in the offline phase using an easily updated database to guarantee accuracy of estimating localization errors and realtime error estimations in the online 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 MCEE fingerprinting method also has two phases, the offline phase and online phase.
In the offline 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 online phase, when a few online 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 online RSS matrix, and then each online 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.
Architecture of proposed method, where is an online RSS value collected from M th AP in N th online 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 selectionbased algorithms, both the RSS samples of each RP in the radiomap and multiple online RSS samples collected at one location are first averaged. RPs are selected for localization through matching the online RSS mean sample with the RSS mean sample of each RP. Machine learningbased algorithms train nonlinear mapping functions in the offline phase with RSS samples and location coordinates of RPs in the radiomap. In the online phase, after collecting multiple online RSS samples at one location, the RSS mean sample of the online 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 online RSS samples are averaged to calculate one single RSS mean sample. Thus, an online RSS sample matrix, which comprises all the online RSS samples collected continuously at one location, is used to calculate localization coordinates. The correlations between the online 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 online 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 uncorrelation. 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 selectionbased fingerprinting algorithm.
Let
M
,
L
and
N
denote the numbers of deployed APs, labeled RPs for establishing the radiomap and online RSS samples, respectively. Then
N
online RSS samples are arranged into an online RSS matrix
RSS
^{OL}
with dimensions of
M
×
N
as follows:
A total of
L
RSS matrices with the same dimensions of
M
×
N
are created from RSS data of the
L
RPs. RSS matrix
of
i
th RP is denoted as:
The CC
r_{i}
denotes the correlation degree between the online RSS matrix
RSS
^{OL}
and RSS matrix
of
i
th RP in the radiomap, which is calculated by:
where
and
are elements in the
m
th row and
n
th column of matrix
RSS
^{OL}
and matrix
, respectively.
and
are the means of matrix
RSS
^{OL}
and matrix
, respectively.
After all the CCs are computed, they are sorted in descending order, which means the correlations between
RSS
^{OL}
and
,
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:
where {
MAX
_
K
(
r
_{1}
,
r
_{2}
,⋯,
r
_{L}
)} is the set of the first
K
maximum CCs,
s_{q}
and
are location coordinates of
q
th selected RP and localization coordinates, respectively.
In (3), term
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
r_{i}
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 online RSS matrix and RSS matrices of RPs in the radiomap, 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 offline phase, a static radiomap is established with a great number of RSS samples collected at RPs to describe the relationship between WiFi radio signals and physical location coordinates. However, indoor radio signal propagation is timevarying, which may vary remarkably because of indoor structure and layout changes. Under such condition, The RSS samples measured in the online phase may considerably deviate from the RSS samples in the static radiomap at the same locations. Using such radiomap for localization, fingerprinting algorithms perform poorly
[21

23
,
27
,
28]
. Additionally, regarding the neighbor selectionbased 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 radiomap 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 multilayer 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 online RSS samples, respectively, so the number of the inputs is
M
×
N
+2 that includes all the RSS values contained in the
N
online 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
online RSS samples
,
i
=1,,⋯,
N
are combined into an RSS vector
as part of the inputs of the MLP network, where
,
i
=1,2,⋯,
N
. The RSS vector
and localization coordinates
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:
Proposed MLP network structure for estimating localization errors, where M and N are the numbers of APs and online RSS samples, respectively
The outputs in layer
l
of the MLP network for sample
k
can be calculated by:
where
is the input from neuron
i
in layer(
l
1),
is the output of neuron
j
in layer
l
,
is the weight from neuron
i
in layer (
l
1) to neuron
j
in layer
l
,
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:
where
d_{j,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 offline 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
.
Training of ANN model in the offline phase
Let
,
i
=1,2,⋯,
Q
, and
,
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
is the
N
th RSS sample received from
M
APs contained in
i
th training vector. Then
i
th RSS training vector
is first arranged into an RSS matrix. Using (3) and (4), CCs are computed between the RSS matrix and RSS matrices in the radiomap denoted by (2) to obtain localization results of the training points
. Localization errors of the training points
,
i
=1,2,⋯,
Q
, are computed by (8):
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.
In the online phase, the process of estimating localization errors is shown in
Fig. 4
. When
N
online RSS samples
,
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
using the MC fingerprinting algorithm described by (3) and (4). The localization coordinates
and the online RSS vector
are inputted into the optimized ANN model as a vector
to estimate the localization errors
. Then, according to (8), the final localization coordinates
are obtained through the error corrections given by:
Process of error corrections in the online phase
4. Experimental Results and Analyses
 4.1 Experimental Setup
To evaluate the performance of the proposed MCEE 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 radiomap. 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 offline 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 radiomap was built.
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.
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 selectionbased 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.
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 threelayer MLP with 20 inputs including 2 online 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 outofdate radiomap 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 online 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 outofdate radiomap. 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 MCEE and WKNNEE are 1.52m and 1.64m, respectively.
Localization results of MC and MCEE
Localization results of WKNN and WKNNEE
 4.4 Comparisons and Analyses of Localization Results
With the radiomap 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 learningbased fingerprinting algorithm for comparison. Using 5400 RSS testing samples, the mean error and error standard deviation of the ANNbased fingerprinting algorithm are 2.72m and 1.59m, respectively. Its performance is better than neighbor selectionbased 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.
Cumulative probabilities of various algorithms
Performance comparison of various algorithms
Performance comparison of various algorithms
In order to improve localization performance, researchers have proposed several stateoftheart fingerprinting localization systems. For example, Feng et al. proposed an RSSbased localization system using compressive sensing (CS)
[33]
. The mean errors of the KNN and CSbased 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 semisupervised 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 discriminantadaptive 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 MCEE 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 MCEE, respectively. The cumulative probabilities of the MCEE 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 MCEE 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 stateoftheart 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 radiomap.
 4.5 Complexity Analyses
Let
M
,
L
,
N
, and
K
denote the numbers of APs, RPs, online 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 online 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 online computational complexity of the MC algorithm is highest among these neighbor selectionbased algorithms, for
i
th RP, differences between each component in the RSS matrix of the RP and the mean of all these components
, 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 millisecondlevel, so the proposed MC algorithm and EE method can meet realtime computing requirements for mobile terminals.
Comparison of online computational complexity
Comparison of online computational complexity
In this study, in order to establish the database called radiomap, a total of 300×67=20100 RSS samples are collected, so it is difficult to update the whole radiomap 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 radiomap 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 radiomap update for WiFi localization based on MC fingerprinting algorithm is proposed. Compared with classic fingerprinting algorithms that calculate localization results using online 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 online RSS data and outperforms the other neighbor selectionbased 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 online 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 offline phase using a training point database. In the online 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 radiomap. Thus, the experimental results demonstrate that the proposed MCEE method can not only improve localization performance greatly, but also offer an effective solution to radiomap update.
In the future, based on the idea of employing all online 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
YongLiang 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.
YuBin 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, radiowave propagation and trunking communications.
View Fulltext
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 1518
Article (CrossRef Link)
720 
724
Bahl P.
,
Padmanabhan V.N.
2000
“RADAR: an inbuilding RFbased user location and tracking system”
in Proc. of 19th IEEE Computer and Communications Societies Conference
March 2630
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 builtin WiFi 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 CyberneticsPart 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/ipcom: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 realtime 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 1317
Article (CrossRef Link)
2338 
2343
Wong C.
,
Klukas R.
,
Messier G.G.
2008
“Using WLAN infrastructure for angleofarrival 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 1921
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 610
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 2528
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.10044132.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 twostage 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 multiview 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 signalstrengthbased 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 realtime 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 1820
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 HumanMachine Systems and Cybernetics
August 2627
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 14
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 1519
Article (CrossRef Link)
1 
5
Rumelhart D.E.
,
Hinton G.E.
,
Williams R.J.
1986
“Learning representations by backpropagating errors”
Nature
Article (CrossRef Link)
323
533 
536
DOI : 10.1038/323533a0
Outemzabet S.
,
Nerguizian C.
2008
“Accuracy enhancement of an indoor ANNbased fingerprinting location system using particle filtering and a lowcost sensor”
in Proc. of IEEE 67th Vehicular Technology Conf.
May 1114
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
“Receivedsignalstrengthbased 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 WiFi 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 Artiﬁcial Intelligence
July 1317
Article (CrossRef Link)
1421 
1426
Pan J.L.
,
Zheng W.C.
,
Yang Q.
,
Hu H.
2008
“Transfer learning for WiFibased indoor localization”
in Proc. of the Workshop on Transfer Learning for Complex Task of the 23rd AAAI Conference on Artiﬁcial Intelligence
July 1317
Article (CrossRef Link)
43 
48
Fang S.H.
,
Lin T.N.
2008
“Indoor location system based on discriminantadaptive 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