Advanced
Grid-based Correlation Localization Method in Mixed Line-of-Sight/Non-Line-of-Sight Environments
Grid-based Correlation Localization Method in Mixed Line-of-Sight/Non-Line-of-Sight Environments
KSII Transactions on Internet and Information Systems (TIIS). 2015. Jan, 9(1): 87-107
Copyright © 2015, Korean Society For Internet Information
  • Received : August 23, 2014
  • Accepted : December 13, 2014
  • Published : January 31, 2015
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
Wang Riming
School of Information Engineering, Guangdong University of Technology Guangzhou, Guangdong, 510006, China
Feng Jiuchao
School of Electronic and Information Engineering, South China University of Technology Guangzhou, Guangdong, 510641, China

Abstract
Considering the localization estimation issue in mixed line-of-sight (LOS)/non-LOS(NLOS) environments based on received signal strength (RSS) measurements in wireless sensor networks, a grid-based correlation method based on the relationship between distance and RSS is proposed in this paper. The Maximum-Likelihood (ML) estimator is appended to further improve the localization accuracy. Furthermore, in order to reduce computation load and enhance performance, an improved recursively version with NLOS mitigation is also proposed. The most advantages of the proposed localization algorithm is that, it does not need any prior knowledge of the propagation model parameters and therefore does not need any offline calibration effort to calibrate the model parameters in harsh environments, which makes it more convenient for rapid implementation in practical applications. The simulation and experimental results evidence that the proposed localization algorithm exhibits good localization performance and flexibilities for different devices.
Keywords
1. Introduction
L Ocation estimation via received signal strength (RSS) has attracted much attention for its low hardware cost. Localization via RSS is the best choice for some applications where the localization error in meter is accepted, e.g. vehicle localization in parking lot. There are numerous articles on localization technologies based on RSS measurements, which can be broadly categorized into two classes: propagation model-based and empirical model-based. Although empirical model-based method generally have higher localization accuracy than the former method, it needs a tedious offline training phase.
In this paper, we focus on the propagation model-based method based on RSS measurements. A new localization method based on recursive grid-based correlation method is proposed. The performance of the proposed method is validated in simulations and experiments.
The remainder of this paper is organized as follows. Section 2 reviews the related works and presents the main contributions in this paper. Section 3 addresses the RSS signal model, the Cramer-Rao Lower Bound(CRLB) for the ML estimator and the original correlation method. Section 4 describes the proposed improved correlation version with NLOS mitigation. Section 5 presents the framework of the proposed localization algorithm. Section 6 shows the simulation and experimental results and analysis.
2. Related Works and Main Contributions
The least squares estimator and the maximum-likelihood estimator are widely used in propagation model-based localization problems. In [1] , the nonlinear equations constructed from the noisy range measurements are converted to the weighted least squares problem by eliminating the common range variable by subtracting the reference equation. Recently, an optimal reference equation selection method is proposed in [2] , in which several selection methods are proposed and compared. Further, the authors in [3] introduce a range variable instead of subtracting the reference equation, and then exploit a linearization approach to devise two linear least squares (LLS) estimators for RSS-based positioning. Another alteration of substraction is the iterative least squares method presented in [4] .
In the presence of NLOS bias, bias mitigation helps to improve localization accuracy. In [5] , a ‘balancing’ bias variable is introduced for simplification. Furthermore, given a good initial point and the Taylor series expansion technology [6 , 7] , the highly nonlinear joint estimation problem of location and biases can be reduced to a linear least squares issue, which called TS-LQP. Although TS-LQP will result in some accuracy degradation than the sequential quadratic programming algorithm, TS-LQP has much less computation complexity.
In general, the performance of linear least squares estimators will not be comparable to the ML estimators in noisy environments [8] . The ML cost function based on the log-path-loss propagation model [9] is non-convex and highly nonlinear. It is easy to trap in local minima and hard to reach the global minima. Therefore, a good initial point is very important for the ML estimator. There are several methods to provide the initial point, i.e. least squares, linear least squares etc. In [10] , a SDP relaxation convex problem is formulated, and the solution is served as the initial point for the appending ML estimator (called SDP-ML). Simulations demonstrate that SDP-ML exhibits excellent perfomance and performs closely to the corresponding CRLB in RSS-based wireless localization.
In addition to the good initial point, calibration on model parameters is another effective way to improve localization accuracy. In [11] , a self-calibrating RSS ranging method is presented, where the propagation model parameters are self-calibrated by online RSS measurements between the known-location ANs. In [12] , an offline calibration is performed by fitting the RSS measurements collected in experiments. Compared to the above calibration methods, the proposed correlation localization algorithm in this paper does not depend on the propagation model parameters, therefore it dose not need any offline/online calibration effort.
Moreover, geometric layout of anchor nodes can significantly affect the potential localization accuracy. In [13] , a metric for optimal sensor placement is proposed, and the optimal sensor-target localization geometries is analyzed completely for homogeneous sensor networks, including the geometry of range-only based localization, the geometry of time-of-arrival localization and the geometry of bearing-only based localization etc. The authors in [14] focus on the optimal geometries for heterogeneous sensor networks. It can be concluded from [13 - 14] that the localization region should be inside the convex hull formed by the uniformly and randomly deployed anchor nodes (ANs) in order to reach better localization performance. This will be evidenced in the experiments in Section 6.
Generally, mixed line-of-sight (LOS) /non-line-of-sight (NLOS) is common in application environments, which leads to severe accuracy degradation. Identification and mitigation are widely used to deal with NLOS. In [15] , the authors investigated NLOS identification by employing the statistical decision theory. In [16] , the mixture distribution is utilized to characterize the non-Gaussian and heavy-tailed nature of the measurements error in mixed LOS/NLOS environments. However, although many algorithmes have been proposed to identify and mitigate NLOS [17 - 20] , it is still hard to model the mixed LOS/NLOS characteristics exactly and mitigate NLOS effectively by now, due to the unknown prior knowledge of LOS/NLOS status and statistical characteristics.
In [21] , a correlation localization method is presented. However, it utilizes the correlation between online RSS matrix and offline radio-map, thus the offline training phase is unavoidable. Different from [21] , the correlation method proposed in this paper utilizes the correlation between online RSS measurements and distance, thus the tedious offline traning phase is avoided. Compared to the related works mentioned above, the proposed algorithm in this paper does not need to select the initial point, and does not depend on the propogation model parameters, therefore any offline/online calibration and training effort is avoided, which makes it more suitable for rapid implementation in applications.
The main contributions of this paper are: (1) Propose an innovational method in utilizing the correlation between online RSS measurements and distance to locate the target. The proposed correlation method bypass the difficulty to know the path loss exponent in advance in localization. As soon as online RSS measurements are received, the location estimation of the target can be obtained immediately, no matter how the path loss exponent changes due to the variations in environments. (2) Present a simple and effective NLOS mitigation method for RSS-based wireless localization in mixed LOS/NLOS environments. (3) Put forward some important guidlines on the ANs deployment to improve localization accuracy, which are useful for network implementation in applications based on RSS measurements.
3. Signal Model and Correlation Method
- 3.1 Signal Model and ML Estimator
In the localization planer Ω, we consider a system consisting of N stationary anchors nodes (ANs) with known locations ai = [ xa , yai ] T , i =1,2,⋯, N and a target node (TN) with unknown location θ = [ x , y ] T , which is to be estimated based on RSS. RSS measurements are received by the TN from M hearable ANs, where M N . A simple illustration of the mixed LOS/NLOS localization scenario is illustrated in Fig. 1 .
PPT Slide
Lager Image
A simple example of localization in mixed LOS/NLOS environments.
The signal strength Pr,i , measured by the TN from the i th reachable AN can be modeled by the log-path-loss model as follows [9] .
PPT Slide
Lager Image
where i = 1,2,,⋯, M , Pt is the transmission power and P0 is the signal strength at the reference distance d0 , generally, d0 = 1m; β is the path loss exponent (generally ranging from 2 to 7 [22 - 23] ); ni is the Gaussian random variable representing the shadowing effect in the environments and ni ~ N (0, σ2 ). In this paper, Pr , Pt and P0 are in dB scale. Pt and P0 are known as identical constant for all ANs. For simplicity, we assume Pt =0 dB.
Suppose the observation vector is Pr =[ P r ,1 , P r ,2 ,⋯, P r,M ] T , P r ,i follows the Gaussian distribution. Therefore, under the independence assumption of P r ,i , the joint conditional PDF of P r is
PPT Slide
Lager Image
Obviously, the ML estimator of θ is
PPT Slide
Lager Image
The root mean square error ( RMSE ) of
PPT Slide
Lager Image
is lower bounded by the Cramer-Rao lower bound (CRLB) [24]
PPT Slide
Lager Image
where the Fisher Information matrix F is defined as
PPT Slide
Lager Image
It serves as a performance benchmark for location estimation in Section 6.
- 3.2 Original Grid-based Correlation Method
Given an arbitrary location θg = [ xg , yg ] T , suppose the corresponding distance vector and observation vector are dg = [ dg ,1 , dg ,2 ,⋯, dg ,M ] T and Prg = ⎿ Prg ,1 , Prg ,2 ,⋯, Prg ,M T respectively, where dg,i , is the distance between θ g and the i th AN. Then the correlation coefficient γθg between dg and Prg is defined as
PPT Slide
Lager Image
and γθg =1 in ideal environments without noise.
Suppose the length and width of the localization region Ω are L m and W m respectively, and Ω is divided into grids with length s . Further denote the center coordinate of each grid as ck = [ xck , yck ] T , k = 1,2,⋯, K , and K = ⎿ LW/s2 ⏌. Then for each ck , the corresponding correlation coefficient γck can be calculated from (6) , given the received RSS observation vector Pr . Thus
PPT Slide
Lager Image
where δ (•) is the Dirac function. Therefore, the location estimation of the TN is obtained by
PPT Slide
Lager Image
A simple illustration is depicted in Fig. 2 . it can be observed that four ANs are located at four corners respectively, the TN is located at [4,2]. Numbers in each grid are the correlation coefficients accordingly. According to (8), the location estimation of the TN is [5,1], with parameters β =2, σ 2 = 3.4 2 .
PPT Slide
Lager Image
A simple localization example of the original correlation method
Remark1: The location estimation obtained by the correlation method is a coarse estimation, and the corresponding localization error decreases as the grid length s gets smaller.
Remark2: The correlation coefficient cannot provide high resolution with noisy RSS measurements. The location estimation obtained by the correlation method are more suitable to serve as good initial point for the ML estimator than to be the final location estimation.
Remark3: Computation load of the grid-based correlation method increases quickly as the grid length gets smaller. Therefore, an improved grid-based correlation method is proposed in Section 4, which has much less computation cost and more steady estimation output.
4. Improved Correlation Method and NLOS Mitigation
- 4.1 Recursively Grid-based Correlation Method
To reduce the computation cost is equivalent to reduce the amount of grids. In order to reduce the amount of grids, a large grid length is set in initialization, and then reduced by half in each iteration subsequently. Also, the high probability region is reduced by half in each iteration. The method to reduce by half in each iteration is inspired from the binary search, which owes good performance and fast speed in searching. Note that the grid with largest correlation coefficient maybe not the closest grid to the true location of the target, due to noisy RSS measurements and NLOS bias. Therefore, the two-step strategy is not adopted, which select the grid with largest coefficient first and then refine in it later.
Suppose the initial high probability region R 0 = Ω, with the initial length L 0 = L and the initial width W 0 = W , then the ith iteration is briefly described as follows.
1) Original grid-based correlation operation : divide Ri into grids by grid length si , then calculates the correlation coefficient γck by (6) for each grid. Therefore we have a coefficient vector γ = [ γc 1 , γc 2 ,⋯, γcK ] T , where the index K indicates that there are totally K grids,
PPT Slide
Lager Image
2) Update high probability region : Sort γ in the order of descendent. Take the middle component of the sorted coefficient vector as the threshold pth , then we have a subset of γ , denoted as γsub = { γck | γck > pth }. Consequently we have the corresponding coordinate subset φ = { ck | γck γsub }. Then the corresponding grids with center ck φ establish the high probability region Ri +1 . Obviously there exist
PPT Slide
Lager Image
where γ denotes the cardinality of the set γ , and S (•) is the area operation. Furthermore, Ri +1 can be defined by four corner vertices
PPT Slide
Lager Image
The sides length of Ri +1 can be updated by
PPT Slide
Lager Image
3) Update grid length : The grid length is updated by si +1 = si /2 . If si +1 ˂ smin , the routine exit iteration and return γ sub , φ , else the routine go back to Step 1). Note that smin is the minimal step depended on applications. It is set smin = 0.5m in the performance evaluations.
The comparison of reduction in computation load is showed in Fig. 3 . Scene1 is a square region in Lab, s 0 = 3m, L 0 = W 0 = 6m. Scene2 is a square region in simulation, s 0 = 7m, L 0 = W 0 = 70m. Scene3 is a rectangle region in the central bus station, s 0 = 9m, L 0 = 100m, W 0 = 45m. For all scenes, smin = 0.5m. It can be seen that the number of grids in the improved version is nearly one grade lower than that in the original version.
PPT Slide
Lager Image
Comparison of reduction in computation load
- 4.2 The Location Estimation
In order to improve the localization performance in harsh environments, a weighted location estimation method is proposed. Remember that γsub , φ are obtained in the previous routine, thus
PPT Slide
Lager Image
where Σ γsub add up all elements of γsub for normalization.
Performance comparison of (8) and (12) are presented in Table 1 . In the performance evaluations, there are totally 12 TN positions randomly and uniformly selected inside the 6m×6m region with four ANs at four corners respectively, and 50 independent localizations are performed at each position. The NLOS bias is assumed to follow the uniform distribution U (0, B max ), B max = 10dB [25] .
Mean and variance of localization error in the origin and improved method
PPT Slide
Lager Image
Mean and variance of localization error in the origin and improved method
The original method in (8) and the improved method in (12) are denoted as “Org” and “Imp” in Table 1 , respectively. The left numbering 1-4 indicate σ=1,2,3,4 respectively. The right numbering 1-4 indicate there are 1,2,3,4 ANs in NLOS respectively. The mean of localization error is calculated by the root mean square error ( RMSE ) in (4). It can be seen that the mean of localization errors in (8) and (12) differ little with each other as σ or NLOS increases. Furthermore, they are both steady, which indicate that the correlation method is not sensitive to measurement noise and NLOS bias. Moreover, the variance of localization error in (12) is much less than that in (8), thus (12) is more acceptable for location estimation.
- 4.3 NLOS Mitigation
Under NLOS scenarios, since the direct sight paths between the TN and the ANs are blocked by the obstacles, the radio power attenuation are more severe than that under LOS scenarios, thus | Pr,i |(the absolute value of RSS) gets larger in NLOS. Note that the RSS measurements obtained by Zigbee chip CC2530 are positive values(equivalent to | Pr,i |), and Pt = 0dB, then from (1) have
PPT Slide
Lager Image
where E (•) means expectation operation. As mentioned above, | Pr,i |) gets larger in NLOS, therefore β increases under NLOS situations. For example, Fig. 4 displays the RSS measurements received by the TN from the 25th AN in the experiments in the central bus station. There was a bus passing by the TN when observing the first half sequence of RSS. Obviously, | Pr,i |) gets larger in the first half sequence in Fig. 4 .
PPT Slide
Lager Image
An example of RSS measurements obtained in the central bus station.
Further denote
PPT Slide
Lager Image
and
PPT Slide
Lager Image
as the mean value of | Pr,i | in NLOS and LOS respectively. As discussed before,
PPT Slide
Lager Image
, is larger than
PPT Slide
Lager Image
, and the NLOS bias is
PPT Slide
Lager Image
Suppose there have
PPT Slide
Lager Image
under LOS scenarios, then have
PPT Slide
Lager Image
in NLOS.
Therefore, under NLOS scenarios, the path loss model can be re-written as
PPT Slide
Lager Image
Since the statistics characteristics of
PPT Slide
Lager Image
in experiments are complicated and varying, it is hard to be exactly modeled. For simplicity but not loss generality, the uniform distribution is used to approximately model the NLOS bias
PPT Slide
Lager Image
in simulations.
Based on the above analysis, a simple and effective method to reduce the effect of NLOS is proposed in this section, which requires no prior knowledge of NLOS status and statistics characteristics. The idea is as follows. Given the coarse location estimation
PPT Slide
Lager Image
obtained by the correlation method, the path loss exponent
PPT Slide
Lager Image
can be calculated by (13). As discussed before, it is reasonable to confirm that the AN with high value of
PPT Slide
Lager Image
may be with high probability of NLOS occurrence. Therefore, the main idea of the proposed mitigation method is to subtract the NLOS bias
PPT Slide
Lager Image
from the RSS measurements received from the AN with high
PPT Slide
Lager Image
. Since
PPT Slide
Lager Image
is unknown, it needs to be estimated. However, it is hard to estimate individual NLOS bias for each AN, due to no NLOS identification part. Therefore, a “balancing” bias variable is introduced for simplification, which denoted as Pcom in Algorithm 1 .
The NLOS mitigation method
PPT Slide
Lager Image
The NLOS mitigation method
Generally, in the proposed mitigation method, large Pcom appears on the extreme outliers of the path loss exponents. In LOS scenarios, there are few extreme outliers in the path loss exponents. Therefore, the additional error introduced by subtracting the NLOS bias Pcom is small.
An example in Lab experiments in LOS is showed in Table 2 . It can be seen that | Pcom ( S2 )| are small compared to the corresponding
PPT Slide
Lager Image
, thus have small impact on the appending ML estimator. The additional error introduced in the location estimation is 0.07m in this example. However, due to no identification part, the additional error can’t be avoided. This is the disadvantage of this method.
An example in Lab experiments
PPT Slide
Lager Image
An example in Lab experiments
5. The Grid-based Correlation Location Estimation Algorithm
- 5.1 Framework of The Algorithm
The proposed improved correlation method in Section 4.1 is denoted as CORR. By appending ML estimator to CORR, we get CORR-ML. The location estimation obtained by CORR provides a good initial point for the appending ML estimator, which improve the localization performance further. Moreover, the NLOS mitigation method helps to reduce the effect of NLOS bias, and enhance the localization accuracy further. The framework of CORR-ML is showed in Algorithm 2 .
Grid-based correlation location estimation algorithm
PPT Slide
Lager Image
Grid-based correlation location estimation algorithm
- 5.2 Complexity Analysis
The complexity of SDP is commonly approximated by O ( O ( M 1/2 ) M 4 ) [26] , and the complexity of MLE is O ( KGN M 3 ), where KGN is the iterations needed in Gauss-Newton method [27] . Since SDP is appended by MLE in SDP-ML [10] , the complexity of SDP-ML is approximated by O ( O ( M 1/2 ) M 4 + KGN M 3 ). Besides, LLS [3] and TS-LQP [5] are single loop algorithms, the complexities of LLS and TS-LQP are O ( M ).
In the proposed correlation method, suppose the initial grid length is s 0 , then the initial number of grids is
PPT Slide
Lager Image
, where L and W are the length and width of the localization region Ω respectively. According to the proposed method, the high probability region and the grid length are reduced by half in each iteration. Therefore, the grid length and the number of grids in the i th iteration are s 0 /2 i and 2 i
PPT Slide
Lager Image
respectively. Consider the stop condition s k = s 0 /2 k ≤ 0.5, thus there have k ≥⎾1+log 2 s o ⏋ iterations and
PPT Slide
Lager Image
grids in total. Because each grid corresponding to a correlation coefficient, and the complexity of calculating the correlation coefficient is O ( M ), then the complexity of CORR is
PPT Slide
Lager Image
Since CORR is appended by MLE in CORR-ML, the complexity of CORR-ML is
PPT Slide
Lager Image
The summary of complexity and average running-time in the mentioned Scene1-3 in Fig. 3 are shown in Table 3 . Obviously, the cost of CORR-ML is smaller than SDP-ML.
The summary of complexity and average running time
PPT Slide
Lager Image
The summary of complexity and average running time
6. Simulation and Experimental Results and Analysis
The root mean square error ( RMSE ) of the location estimation
PPT Slide
Lager Image
has been defined in (4). Now further define the average root mean square error ( aRMSE ) as
PPT Slide
Lager Image
where J is the number of TN positions. The performance is evaluated using aRMSE .
LLS [3] , TS-LQP [5] and SDP-ML [10] are compared in simulation and experiments. The proposed improved correlation method in Section 4.1 is denoted as CORR. CORR-ML is the proposed localization algorithm in Section 5.1. For fair comparison, the coarse location estimation
PPT Slide
Lager Image
obtain by CORR also serves as the initial point for TS-LQP.
The simulations are done via MATLAB. MLE is solved by MATLAB function lsqnonlin , SDP is solved by CVX toolbox [28] . In experiments, all RSS measurements are relayed to the fusion center via Zigbee wireless network, and saved in files for post-processing.
- 6.1 Simulation Results and Analysis
The simulation scenario is a square region with sides length 70 meters. Three geometric layout of ANs are selected for performance comparison. (1) ‘Net-I’: There are M = 30 ANs randomly and uniformly deployed inside the square region. (2) ‘Net-II’: There are M = 30 ANs randomly and uniformly distributed on edges of the square region. (3) ‘Net-III’: There are half of M = 30 ANs randomly and uniformly distributed on edges of the square region, and the remains are randomly and uniformly deployed inside the square region. There are J = 50 TN positions randomly and uniformly selected inside the convex hull formed by ANs for Net-I, Net-II, Net-III respectively.
As discussed in Section 4, the nonzero Gaussian distribution N ( μi , σ 2 ) is adopted to model the statistic characteristics of RSS in mixed LOS/NLOS environments, where μi follows the uniform distribution U [0, B max ], B max = 25dB, i = 1,2,⋯, M . The path loss exponent β = 3.5 in simulations. The number of ANs in NLOS is denoted as Nn , and accordingly Nl represents the number of ANs in LOS. Thus the number of ANs in total is M = Nn + Nl = 30.
1) Effect of the standard deviation and the number of NLOS : The simulation is performed with layout ‘Net-I’. When simulating the effect of the standard deviation, nN is fixed on 15. When simulating the effect of the number of NLOS, σ is fixed on 7.
It can be observed from Fig. 5 that the aRMSE of any estimator shows degradation as the standard deviation increases. CORR-ML exhibits much better performance than LLS and TS-LQP. SDP-ML performs almost the same as CORR-ML. In addition, the aRMSE of SDP-ML and CORR-ML are both far larger than CRLB even when σ is small, which demonstrates that NLOS has significant influence on the localization accuracy(note that Nn = 15).
PPT Slide
Lager Image
aRMSE versus σ when Nn = 15, M = 30.
Fig. 6 displays the aRMSE versus the number of NLOS. In Fig. 6 (a), the path loss exponent β of TS-LQP and SDP-ML is fixed on 3.5, it can be seen that TS-LQP and SDP-ML cannot work properly as Nn gets larger. This phenomenon stems from the feature of TS-LQP and SDP-ML that they are highly dependent on the value of β , however the true value of β becomes larger than 3.5 as Nn increases. It means that in environments with dynamic NLOS, TS-LQP and SDP-ML maybe failure if the path loss exponent is not correctly decided. On the contrary, CORR-ML requires no prior knowledge of the path loss exponent, which is evidenced by the steady performance of CORR-ML in Fig. 6 (a) and Fig. 6 (b). Therefore the offline calibration or training effort is omitted in implementation, which makes CORR-ML more suitable for applications.
PPT Slide
Lager Image
aRMSE versus Nn when σ= 7, M = 30.
Fig. 6 (b) shows that, on the condition that the path loss exponent β is tuned to the right value accordingly, SDP-ML have almost the same performance as CORR-ML. Note that CRLB decreases as the path loss exponent β gets larger, for the inverse proportional relationship with β [10] .
Surprisingly, from Fig. 6 (b), we can observe that SDP-ML, CORR, CORR-ML exhibit steady performance as Nn gets larger than 15, and TS-LQP shows even better performance. The reasonable interpretation may be as follows. The diversity of NLOS bias reach peak when Nn = 15, Nl =15. As Nn gets larger than 15, the diversity of bias decreases. For example, the diversity of bias when Nn = 30, Nl = 0 is almost the same as that when Nn = 0, Nl = 30. Therefore the worst performance maybe not exhibit at Nn = 30, Nl = 0. Moreover, as announced in [5] , TS-LQP would be most efficient when all the bias values are similar. Therefore, the performance of TS-LQP exhibits better as Nn gets larger than 15 due to the more similar bias values.
2) Effect of NLOS mitigation : This simulation is performed with layout ‘Net-I’. The number of NLOS Nn vary form 1 to 30, and the standard deviation σ = 7. Fig. 7 shows that the performance of CORR-ML with NLOS mitigation is much better than that without NLOS mitigation. The phenomenon of performance improvement happens when Nn = 30, which is similar to the phenonmenon in Fig. 6 (b). The reasonable interpretation is the same as that in Fig. 6 (b), due to the decrease in the diversity of NLOS biases.
PPT Slide
Lager Image
The performance comparison of CORR-ML with and without NLOS mitigation
3) Effect of the numbers of hearable ANs : In this simulation, the number of hearable ANs M vary from 10 to 40 , and they are randomly and uniformly deployed inside the square localization region. The standard deviation σ = 7. It can be observed from Fig. 8 that the performance of any algorithm improves as M increases, demonstrating that more hearable ANs result in higher localization accuracy. In addition, SDP-ML performs a bit better than CORR-ML as M increases. However, as analyzed in Section 5.2, the complexity of SDP-ML is the order of M 4 , thus the cost of SDP-ML increases more quicker than CORR-ML as M increases.
PPT Slide
Lager Image
aRMSE versus M when Nn = 10, σ = 7
4) Effect of the geometric layout : There is no doubt that the geometric layout of ANs has significant effect on the potential performance of any localization algorithm. Recently many articles focused on the topic of optimal geometric layout for localization [13 , 29 - 31] . It can be concluded from the mentioned articles that the optimal geometric layout is not unique, and the uniformly and randomly deployment is the near-optimal geometric layout.
The performance comparison of the three above-mentioned layouts (‘Net-I’, ‘Net-II’ and ‘Net-III’) are displayed in Fig. 9 , where Nn = 15, σ = 4. It is worth noting that, (1) in the three layouts, all TN positions are located inside the convex hull formed by the ANS; (2) there are ANs placed on the edges of the localization region except the layout “Net-I”. It can be observed from Fig. 9 that “Net-I” exhibits even better performance than the other two layouts, which indicates that to place ANs on the edges of the localization region is not necessary for performance improvement, as long as the interesting localization positions are inside the convex hull formed by the ANs. This conclusion is useful for network implementation in applications.
PPT Slide
Lager Image
The localization performance comparison of different geometric layout
- 6.2 Experimental Results and Analysis
Experiments are taken in the Lab (LOS environments) and the central bus station (mixed LOS/NLOS environments) respectively.
1) Experiment in the Lab
The localization region in the Lab is a square region with sides length 6 m, and all wireless links between any two nodes are in line of sight, as depicted in Fig. 10 (a). The ANs and the TN are Zigbee nodes, which equipped with IEEE 802.15.4 Compliant RF chip TI CC2530 and omni antenna, as showed in Fig. 10 (b). In this scenario, the ANs are deployed randomly and uniformly, and the TN positions are uniformly and randomly selected, as displayed in Fig.11 (a). The red ‘o’ represents ANs positions, the blue ‘+’ represents TN positions, the red dot line represents the convex hull formed by ANs. There are 4 TN positions in the convex hull, and other 8 TN positions are out of the convex hull. The CRLB corresponding to this scenario in Lab is showed in Fig. 11 (b).
PPT Slide
Lager Image
(a) The localization region in Lab. (b) The Zigbee nodes used in experiments.
PPT Slide
Lager Image
(a)The ANs deployment and the TN positions. (b) The corresponding CRLB in Lab
Obviously, from Fig. 11 (b) we see that the localization error becomes larger when closer to the boundary, which is evidenced by the results showed in Fig. 12 , where the localization error of any estimator in the convex hull is much less than that out of the convex hull. Moreover, it can be further demonstrated from Fig. 12 that although good localization performance is achieved under uniformly and randomly deployment, the localization accuracy can be further improved if all the interesting localization positions are ensured to be located inside the convex hull formed by the uniformly and randomly deployed ANs. This is an important guideline for ANs deployment in practice.
PPT Slide
Lager Image
The localization performance comparison of in/out of the convex hull
2) Experiment in the central bus station.
The localization region is located inside the central bus station, with 100 meters long and 45 meters wide. we deployed 30 Zigbee nodes (ANs) in the localization region uniformly, all are mounted on the concrete poles at the same level of height, and about 4.5 meters higher than the floor, as showed in Fig. 13 . The TN is placed in the front of the bus and under the front windscreen.
PPT Slide
Lager Image
(a) Part of the scenario in the central bus station. (b) The close shot of ANs.
In order to analyze the localization performance for different devices, there are 5 target nodes placed in the bus at the same time at each position, and denoted as Dev1, Dev2, Dev3, Dev4, Dev5 respectively. There are totally 26 TN positions uniformly and randomly selected inside the localization region. Fig. 14 depicts the performance comparison of these five devices. It can be observed that the average localization accuracy differs much from each other. For example, the aRMSE of Dev1 is about 1.5 meters less than that of Dev3 for CORR-ML, which is about 30% lower. Generally, It is hard to exclude the influence of the unpredictable hardware diversities between different devices.
PPT Slide
Lager Image
The localization performance comparison of different devices
In addition, NLOS biases have significant influence on the localization accuracy degradation. For example, in Lab experiments, the aRMSE of CORR-ML can reach 0.6m, as shown in Fig. 12 . However, in the central bus station, the aRMSE of CORR-ML increase to over 4m , which due to the severe NLOS biases caused by the nearby buses.
In order to further investigate the flexibilities of the compared algorithms, the performance evaluations with randomly selected devices are performed. As mentioned before, all RSS measurements in experiments are relayed to the fusion center and saved in files for post-processing. Thus we can select RSS measurements of any device randomly at each position. The box plot of the performance evaluations with randomly selected devices are showed in Fig. 15 . On each box, the central mark is the median, the edges of the box are the 25th and 75th percentiles, and the whiskers extend to the most extreme data points. It can be observed from Fig. 15 that the median RMSE of SDP-ML is lower than CORR-ML, but the extreme RMSE of SDP-ML is about 3 meters larger than CORR-ML. In other words, CORR-ML can provide more steady localization estimations than SDP-ML, and exhibit more flexibilities for different devices.
PPT Slide
Lager Image
The localization performance of randomly selected devices in experiments.
7. Conclusions
The recursively grid-based correlation localization method (CORR) based on the relationship between RSS and distance has been proposed in this paper, which does not need any prior knowledge of the propagation model parameters compared to other propagation model-based algorithms. By appending ML estimator to CORR, which called CORR-ML, can reach higher localization accuracy. Performance evaluations are performed in the simulations and the experiments in the Lab and the central bus station. The results indicate that CORR-ML performs much better than LLS, TS-LQP, and exhibits better performance than SDP-ML in experiments. Moreover, CORR-ML provides more steady localization estimations for different devices than other algorithms. Mostly, CORR-ML does not need any offline calibration effort to calibrate the path loss exponent, which makes it more suitable, simple and convenient for applications.
BIO
Riming Wang received his MS from Guangdong University of Technology, Guangzhou, China, in 2006. He is currently a PhD candidate in the School of Electronic and Information Engineering, South China University of Technology, Guangzhou, China. His research interests include statistical signal processing and wireless sensor networks.
Jiuchao Feng was born in Sichuan, China. He received the B.S. degree in physics from Southwest China Normal University, Chongqing, China, in 1986, the M.E. degree in communication and electronic systems from the South China University of Technology, Guangzhou, China, in 1997, and the Ph.D. degree (winning Distinguished Ph.D. Thesis Award) from The Hong Kong Polytechnic University, Hong Kong, in 2002. He is currently Chair Professor with the School of Electronic and Information Engineering, South China University of Technology, and a Distinguished Professor of Guangdong Province, China.
References
Chan Y. T. , Ho K. C. 1994 "A simple and efficient estimator for hyperbolic location," IEEE Transactions on Signal Processing 42 (8) 1905 - 1915    DOI : 10.1109/78.301830
Salman N. , Ghogho M. , Kemp A. 2014 "Optimized low complexity sensor node positioning in wireless sensor networks," IEEE Sensors Journal 14 (1) 39 - 46    DOI : 10.1109/JSEN.2013.2278864
So H. C. , Lin L. 2011 "Linear Least Squares Approach for Accurate Received Signal Strength Based Source Localization," IEEE Transactions on Signal Processing 59 (8) 4035 - 4040    DOI : 10.1109/TSP.2011.2152400
Coluccia A. , Ricciato F. 2014 "RSS-Based Localization via Bayesian Ranging and Iterative Least Squares Positioning," IEEE Communications Letters 18 (5) 873 - 876    DOI : 10.1109/LCOMM.2014.040214.132781
Yu K. , Guo Y. J. 2008 "Improved positioning algorithms for nonline-of-sight environments," IEEE Transactions on Vehicular Technology 57 (4) 2342 - 2353    DOI : 10.1109/TVT.2007.912598
Chen J. , Wang Yeong-Cheng , Maa C. , Chen J. 2006 "Network-side mobile position location using factor graphs," IEEE Transactions on Wireless Communications 5 (10) 2696 - 2704    DOI : 10.1109/TWC.2006.03401
Wu N. , Li B. , Wang H. , Xing C. , Kuang J. 2014 Distributed cooperative localization based on Gaussian message passing on factor graph in wireless networks," Science China Information Sciences 57 (9) 1 - 15
Yu K. , Sharp I. , Guo Y. J. 2009 Ground-based wireless positioning, vol.5 John Wiley & Sons Ltd.
Goldsmith A. 2005 Wireless communications Cambridge university press
Ouyang R. W. , Wong A. , Lea C. 2010 "Received signal strength-based wireless localization via semidefinite programming: noncooperative and cooperative schemes," IEEE Transactions on Vehicular Technology 59 (3) 1307 - 1318
Coluccia A. 2013 "Reduced-Bias ML-Based Estimators with Low Complexity for Self-Calibrating RSS Ranging," IEEE Transactions on Wireless Communications 12 (3) 1220 - 1230    DOI : 10.1109/TWC.2013.011713.120557
Montorsi F. , Pancaldi F. , Vitetta G. 2014 "Map-Aware Models for Indoor Wireless Localization Systems: An Experimental Study," IEEE Transactions on Wireless Communications 13 (5) 2850 - 2862    DOI : 10.1109/TWC.2014.040714.130893
Bishop A. N. , Fidan B. I. C. S. , Anderson B. , Doğançay K. 2010 "Optimality analysis of sensor-target localization geometries," Automatica 46 (3) 479 - 492    DOI : 10.1016/j.automatica.2009.12.003
Meng W. , Xie L. , Xiao W. 2013 "Optimality analysis of sensor-source geometries in heterogeneous sensor networks," IEEE Transactions on Wireless Communications 12 (4) 1958 - 1967    DOI : 10.1109/TWC.2013.021213.121269
Guo K. , Yu Y. J. 2009 "Statistical NLOS identification based on AOA, TOA, and signal strength," IEEE Transactions on Vehicular Technology 58 (1) 274 - 286    DOI : 10.1109/TVT.2008.924975
Yin F. , Fritsche C. , Gustafsson F. , Zoubir A. M. 2014 "EM-and JMAP-ML Based Joint Estimation Algorithms for Robust Wireless Geolocation in Mixed LOS/NLOS Environments," IEEE Transactions on Signal Processing 62 (1) 168 - 182    DOI : 10.1109/TSP.2013.2286779
Venkatesh S. , Buehrer R. M. "A linear programming approach to NLOS error mitigation in sensor networks," in Proc. of the 5th international conference on Information processing in sensor networks April, 2006 301 - 308
Chan Y. , Tsui W. , So H. , Ching P. 2006 "Time-of-arrival based localization under NLOS conditions," IEEE Transactions on Vehicular Technology 55 (1) 17 - 24    DOI : 10.1109/TVT.2005.861207
Macagnano D. , de Abreu G. 2013 "Algebraic Approach for Robust Localization with Heterogeneous Information," IEEE Transactions on Wireless Communications 12 (10) 5334 - 5345    DOI : 10.1109/TWC.2013.090313.130301
Wang Y. , Cheng L. , Han G. , Wu H. , Jiang B. 2014 "RSS Localization Algorithm Based on Nonline of Sight Identification for Wireless Sensor Network," International Journal of Distributed Sensor Networks 2014 1 - 8
Sun Y. , Xu Y. 2013 "Error Estimation Method for Matrix Correlation-Based Wi-Fi Indoor Localization," KSII Transactions on Internet and Information Systems (TIIS) 7 (11) 2657 - 2675    DOI : 10.3837/tiis.2013.11.006
Tang L. , Wang K. C. , Huang Y. , Gu F. 2007 "Channel characterization and link quality assessment of ieee 802.15. 4-compliant radio for factory environments," IEEE Transactions on Industrial Informatics 3 (2) 99 - 110    DOI : 10.1109/TII.2007.898414
Molisch A. F. , Balakrishnan K. , Cassioli D. , Chong C. C. , Emami S. , Fort A. , Karedal J. , Kunisch J. , Schantz H. , Schuster U. , Siwiak K. 2004 "IEEE 802.15. 4a channel model-final report," IEEE P802 15 (04) 662 -
Kay S. M. Fundamentals of statistical signal processing, volume I: Estimation theory PTR Prentice-Hall Englewood Cliffs, NJ
Wang G. , Chen H. , Li Y. , Ansari N. 2014 "NLOS Error Mitigation for TOA-Based Localization via Convex Relaxation," IEEE Transactions on Wireless Communications 13 (8) 4119 - 4131    DOI : 10.1109/TWC.2014.2314640
Vandenberghe L. , Boyd S. 1996 "Semidefinite programming," SIAM review 38 (1) 49 - 95    DOI : 10.1137/1038003
Gholami M. R. , Vaghefi R. M. , Strom E. G. 2013 "RSS-based sensor localization in the presence of unknown channel parameters," IEEE Transactions on Signal Processing 61 (15) 3752 - 3759    DOI : 10.1109/TSP.2013.2260330
Grant M. , Boyd S. , Ye Y. "CVX: Matlab software for disciplined convex programming,"ver.1.21 [Online].
Yang C. , Kaplan L. , Blasch E. , Bakich M. 2013 "Optimal Placement of Heterogeneous Sensors for Targets with Gaussian Priors," IEEE Transactions on Aerospace and Electronic Systems 49 (3) 1637 - 1653    DOI : 10.1109/TAES.2013.6558009
Zhou J. , Shi J. , Qu X. 2010 "Landmark placement for wireless localization in rectangular-shaped industrial facilities," IEEE Transactions on Vehicular Technology 59 (6) 3081 - 3090    DOI : 10.1109/TVT.2010.2048765
Huang B. , Li T. , Anderson B. , Yu C. 2012 "Performance limits in sensor localization," Automatica 49 (2) 503 - 509    DOI : 10.1016/j.automatica.2012.11.011