# Grid-based correlation localization method in mixed line-of-sight/non-line-of-sight environments.

1. IntroductionLocation 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 [OMEGA], we consider a system consisting ofN stationary anchors nodes (ANs) with known locations [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and a target node (TN) with unknown location [theta] = [[x, y].sup.T], which is to be estimated based on RSS. RSS measurements are received by the TN from M hearable ANs, where M [subset or equal to] N. A simple illustration of the mixed LOS/NLOS localization scenario is illustrated in Fig. 1

The signal strength [P.sub.r,i] measured by the TN from the i th reachable AN can be modeled by the log-path-loss model as follows[9].

[P.sub.r,i] = [P.sub.t] + [P.sub.0] - 10[beta] [log.sub.10] ([[parallel] [theta] - [a.sub.i] [parallel]]/[d.sub.0]) + [n.sub.i] (1)

where i = 1, 2, ..., M, [P.sub.t] is the transmission power and [P.sub.0] is the signal strength at the reference distance [d.sub.0], generally, [d.sub.0] = 1m; [beta] is the path loss exponent (generally ranging from 2 to 7 [22-23]); [n.sub.i] is the Gaussian random variable representing the shadowing effect in the environments and [n.sub.i] ~ N(0, [[sigma].sup.2]). In this paper, [P.sub.r], [P.sub.t] and [P.sub.0] are in dB scale. [P.sub.t] and [P.sub.0] are known as identical constant for all ANs. For simplicity, we assume [P.sub.t] = 0 dB.

Suppose the observation vector is [P.sub.r] = [[[P.sub.r,1], [P.sub.r,2], ..., [P.sub.r,M]].sup.T], [P.sub.r,i] follows the Gaussian distribution. Therefore, under the independence assumption of [P.sub.r,i], the joint conditional PDF of [P.sub.r] is

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (2)

Obviously, the ML estimator of [theta] is

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (3)

The root mean square error (RMSE) of [??] is lower bounded by the Cramer-Rao lower bound (CRLB) [24]

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (4)

where the Fisher Information matrix F is defined as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (5)

It serves as a performance benchmark for location estimation in Section 6.

3.2 Original Grid-based Correlation Method

Given an arbitrary location [[theta].sub.g] = [[[x.sub.g], [y.sub.g]].sup.T], suppose the corresponding distance vector and observation vector are [d.sub.g] = [[[d.sub.g,l], [d.sub.g,2], ...,[d.sub.g,M]].sup.T] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] respectively, where [d.sub.g,i] is the distance between [[theta].sub.g] and the i th AN. Then the correlation coefficient [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] between [d.sub.g] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is defined as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (6)

and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] in ideal environments without noise.

Suppose the length and width of the localization region [OMEGA] are L m and W m respectively. and [OMEGA] is divided into grids with length s. Further denote the center coordinate of each grid as [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Then for each [c.sub.k], the corresponding correlation coefficient [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] can be calculated from (6), given the received RSS observation vector [P.sub.r]. Thus

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (7)

where [delta](*) is the Dirac function. Therefore. the location estimation of the TN is obtained by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (8)

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 [beta] = 2, [[sigma].sup.2] = [3.4.sup.2].

Remarkl: 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.sub.0] = [OMEGA], with the initial length [L.sub.0] = L and the initial width [W.sub.0] = W, then the i th iteration is briefly described as follows.

1) Original grid-based correlation operation: divide [R.sub.i] into grids by grid length [s.sub.i], then calculates the correlation coefficient [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] by (6) for each grid. Therefore we have a coefficient vector [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], where the index K indicates that there are totally K grids, K =[[L.sub.i][W.sub.i]/[s.sup.2.sub.i]].

2) Update high probability region: Sort [gamma] in the order of descendent. Take the middle component of the sorted coefficient vector as the threshold [p.sub.th], then we have a subset of [gamma], denoted as [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Consequently we have the corresponding coordinate subset [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Then the corresponding grids with center [c.sub.k] [member of] [phi] establish the high probability region [R.sub.i+1]. Obviously there exist

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (9)

where [absolute value of y] denotes the cardinality of the set [gamma], and S(*) is the area operation. Furthermore, [R.sub.i+1] can be defined by four vertices

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (10)

The sides length of [R.sub.i+1] can be updated by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (11)

3) Update grid length: The grid length is updated by [s.sub.i+1] = [s.sub.i]/2. If [s.sub.i+1] < [s.sub.min], the routine exit iteration and return [[gamma].sub.sub], [phi], else the routine go back to Step 1). Note that [s.sub.min] is the minimal step depended on applications. It is set [s.sub.min] = 0.5 m in the performance evaluations.

The comparison of reduction in computation load is showed in Fig. 3. Scene1 is a square region in Lab, [s.sub.0] = 3 m, [L.sub.0] = [W.sub.0] = 6 m. Scene2 is a square region in simulation, [s.sub.0] = 7 m, [L.sub.0] = [W.sub.0] = 70 m. Scene3 is a rectangle region in the central bus station, [s.sub.0] = 9 m, [L.sub.0] = 100 m, [W.sub.0] = 45 m. For all scenes, [s.sub.min] = 0.5 m. It can be seen that the number of grids in the improved version is nearly one grade lower than that in the original version.

4.2 The Location Estimation

In order to improve the localization performance in harsh environments, a weighted location estimation method is proposed. Remember that [[gamma].sub.sub], [phi] are obtained in the previous routine, thus

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (12)

where [summation][[gamma].sub.sub] add up all elements of [[gamma].sub.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 x 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.sub.max]), [B.sub.max] = 10 dB [25].

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 [sigma] = 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 [sigma] 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 [absolute value of [P.sub.r,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 [absolute value of[P.sub.r,i]]), and [P.sub.t] = 0dB, then from (1) have

[beta] = [absolute value of E([P.sub.r,i])] - [absolute value of [P.sub.0]]/ 10[log.sub.10]([parallel][theta] - [a.sub.i][parallel]/[d.sub.0]) (13)

where E(*) means expectation operation. As mentioned above, [absolute value of [P.sub.r,i]] gets larger in NLOS, therefore [beta] 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, [absolute value of [P.sub.r,25]] gets larger in the first half sequence in Fig. 4.

Further denote [[absolute value of [[bar.P].sub.r,i]].sub.NLOS] and [[absolute value of [[bar.P].sub.r,i]].sub.NLOS] as the mean value of [absolute value of [P.sub.r,i]] in NLOS and LOS respectively. As discussed before, [[absolute value of [[bar.P].sub.r,i]].sub.NLOS] is larger than [[absolute value of [[bar.P].sub.r,i]].sub.LOS], and the NLOS bias is [absolute value of [DELTA][[bar.P].sub.r,i]] = [[absolute value of [[bar.P].sub.r,i]].sub.NLOS] - [[absolute value of [[bar.P].sub.r,i]].sub.LOS]. Suppose there have [[absolute value of [[bar.P].sub.r,i]].sub.LOS] = [absolute value of [P.sub.0]] + 10[beta][log.sub.10]([parallel][theta] - [a.sub.i][parallel]/[d.sub.0]) under LOS scenarios, then have [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] in NLOS.

Therefore, under NLOS scenarios, the path loss model can be re-written as

[P.sub.r,i] = [P.sub.0] - 10[beta][log.sub.10]([parallel][theta] - [a.sub.i][parallel]/[d.sub.0]) + [n.sub.i] [n.sub.i] ~ ([DELTA][[bar.P].sub.r,i], [[sigma].sup.2]) (14)

Since the statistics characteristics of [DELTA][[bar.P].sub.r,i]. 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 [DELTA][[bar.P].sub.r,i] 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 [??] obtained by the correlation method, the path loss exponent [[??].sub.i] can be calculated by (13). As discussed before, it is reasonable to confirm that the AN with high value of [[??].sub.i] may be with high probability of NLOS occurrence. Therefore, the main idea of the proposed mitigation method is to subtract the NLOS bias [DELTA][[bar.P].sub.r,i] from the RSS measurements received from the AN with high [[??].sub.i]. Since [DELTA][[bar.P].sub.r,i] 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 [P.sub.com] in Algorithm 1.

Generally, in the proposed mitigation method, large [P.sub.com] 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 [P.sub.com] is small.

An example in Lab experiments in LOS is showed in Table 2. It can be seen that [absolute value of [P.sub.com]([S.sub.2])] are small compared to the corresponding [absolute value of [[bar.P].sub.r,i]], 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.

Algorithm 1. The NLOS mitigation method Input: Received RSS vector [P.sub.r], known constant [P.sub.0], coarse estimation [??] Output: Mitigated RSS vector [[??].sub.r] 1) Compute [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], where [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. 2) Calculate residual [DELTA][??] = [??] - mean ([??]) 3) Find the set of ANs with positive residual [S.sub.1] = find([DELTA][??] > 0) 4) Calculate compensation vector [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] where [??]([S.sub.1]) means the components of [??] whose indices are in [S.sub.1] 5) Find the set of ANs to be mitigated [S.sub.2] = find (([??] - mean ([??]([S.sub.1])))> 0) 6) Mitigation for ANs in [S.sub.2], calculate [P.sub.r] ([S.sub.2]) = [P.sub.r]([S.sub.2]) - [P.sub.com] ([S.sub.2]), where [P.sub.r] ([S.sub.2]) means the components of [P.sub.r] whose indices are in [S.sub.2]. Return [[??].sub.r] = [P.sub.r].

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.

Algorithm 2. Grid-based correlation location estimation algorithm Input: received RSS vector [P.sub.r], ANs location vector a, Region sides length L and width W, minimum grid length [S.sub.min] Output: Location estimation [??] of the TN Step 1--Initialization Set the iteration index i = 0, sides length [L.sub.i] = L and width [W.sub.i] = W, grid length [s.sub.i] =[max([L.sub.i], [W.sub.i])/m], where m is a constant, and depended on applications. Step 2--Iteration --Divide grids with length [s.sub.i] in the location region --Compute distance vector [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for each grid center [c.sub.k] --Calculate correlation coefficient by (6) for each grid, and sort the coefficient vector. --Update the high probability region by (9) and (10), sides length by (11) Step 3--Convergence check --If ([s.sub.i]/2) > [s.sub.min], set [s.sub.i+1] = ([s.sub.i]/2), set i = i + 1, return to Step 2 --Otherwise, compute location estimation [??] by (12), then go to Step 4 Step 4--NLOS mitigation Execute the NLOS mitigation method in Algorithm 1, go to Step 5 Step 5--ML estimation Taken [??] as the initial point, execute ML estimation based on (3). The MLE estimation [??] is the final location estimation of the TN.

5.2 Complexity Analysis

The complexity of SDP is commonly approximated by O(O([M.sup.1/2])[M.sup.4]) [26], and the complexity of MLE is O([K.sub.GN][M.sup.3]), where [K.sub.GN] 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.sup.1/2]) [M.sup.4] + [K.sub.GN][M.sup.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.sub.0], then the initial number of grids is LW/[s.sup.2.sub.0], where L and W are the length and width of the localization region Q 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.sub.0]/[2.sup.i] and [2.sup.i] LW/[s.sup.2.sub.0] respectively. Consider the stop condition [s.sub.[kappa]] = [s.sub.0]/[2.sup.[kappa]] [less than or equal to] 0.5, thus there have [kappa] [greater than or equal to] [1 + [log.sub.2][s.sub.0]] iterations and ([2.sup.[kappa] + 1] - 1)LW/[s.sup.2.sub.0] 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 O((([2.sup.[kappa] + 1] - 1)LW/[s.sup.2.sub.0])M). Since CORR is appended by MLE in CORR-ML, the complexity of CORR-ML is O((([2.sup.[kappa]+1] - 1)LW/[s.sup.2.sub.0])M + [K.sub.GN][M.sup.3]).

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.

6. Simulation and Experimental Results and Analysis

The root mean square error (RMSE) of the location estimation [??] has been defined in (4). Now further define the average root mean square error (aRMSE) as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (15)

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 [??] 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 ([[mu].sub.i], [[sigma].sup.2]) is adopted to model the statistic characteristics of RSS in mixed LOS/NLOS environments, where [[mu].sub.i] follows the uniform distribution U[0,[B.sub.max]], [B.sub.max] = 25 dB, i = 1, 2, ...,M. The path loss exponent [beta] = 3.5 in simulations. The number of ANs in NLOS is denoted as [N.sub.n], and accordingly N represents the number of ANs in LOS. Thus the number of ANs in total is M = [N.sub.n] + [N.sub.l] = 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, [N.sub.n] is fixed on 15. When simulating the effect of the number of NLOS, [sigma] 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 [sigma] is small, which demonstrates that NLOS has significant influence on the localization accuracy(note that [N.sub.n] = 15).

Fig. 6 displays the aRMSE versus the number of NLOS. In Fig. 6(a), the path loss exponent [beta] 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 [N.sub.n] gets larger. This phenomenon stems from the feature of TS-LQP and SDP-ML that they are highly dependent on the value of [beta], however the true value of [beta] becomes larger than 3.5 as [N.sub.n] 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.

Fig. 6(b) shows that, on the condition that the path loss exponent [beta] 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 [beta] gets larger, for the inverse proportional relationship with [beta] [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 [N.sub.n] = 15, [N.sub.l] = 15. As [N.sub.n] gets larger than 15, the diversity of bias decreases. For example, the diversity of bias when [N.sub.n] = 30, [N.sub.l] = 0 is almost the same as that when [N.sub.n] = 0, [N.sub.l] = 30. Therefore the worst performance maybe not exhibit at [N.sub.n] = 30, [N.sub.l] = 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 [N.sub.n] vary form 1 to 30, and the standard deviation [sigma] = 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 [N.sub.n] = 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.

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 [sigma] = 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.sup.4], thus the cost of SDP-ML increases more quicker than CORR-ML as M increases.

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 [N.sub.n] = 15, [sigma] = 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.

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).

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.

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.

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.

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.

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.

This work was supported by the Nature Science Foundation of China (60872123, 61101014).

http://dx.doi.org/10.3837/tiis.2015.01.006

Reference

[1] Y. T. Chan and K. C. Ho, "A simple and efficient estimator for hyperbolic location," IEEE Transactions on Signal Processing, vol. 42, no. 8, pp. 1905-1915, August, 1994. Article (CrossRef Link)

[2] N. Salman, M. Ghogho and A. Kemp, "Optimized low complexity sensor node positioning in wireless sensor networks," IEEE Sensors Journal, vol. 14, no. 1, pp. 39-46, January, 2014. Article (CrossRef Link)

[3] H. C. So and L. Lin, "Linear Least Squares Approach for Accurate Received Signal Strength Based Source Localization," IEEE Transactions on Signal Processing, vol. 59, no. 8, pp. 4035-4040, August, 2011. Article (CrossRef Link)

[4] A. Coluccia and F. Ricciato, "RSS-Based Localization via Bayesian Ranging and Iterative Least Squares Positioning," IEEE Communications Letters, vol. 18, no. 5, pp. 873-876, May, 2014. Article (CrossRef Link)

[5] K. Yu and Y. J. Guo, "Improved positioning algorithms for nonline-of-sight environments," IEEE Transactions on Vehicular Technology, vol. 57, no. 4, pp. 2342-2353, July, 2008. Article (CrossRef Link)

[6] J. Chen, Y. Yeong-Cheng Wang, C. Maa, and J. Chen, "Network-side mobile position location using factor graphs," IEEE Transactions on Wireless Communications, vol. 5, no. 10, pp. 2696-2704, Oct, 2006. Article (CrossRef Link)

[7] N. Wu, B. Li, H. Wang, C. Xing, and J. Kuang, "Distributed cooperative localization based on Gaussian message passing on factor graph in wireless networks," Science China Information Sciences, vol. 57, no. 9, pp.1-15, Sep, 2014. Article (CrossRef Link)

[8] K. Yu, I. Sharp and Y. J. Guo, Ground-based wireless positioning, vol.5. John Wiley & Sons Ltd., 2009. Article (CrossRef Link)

[9] A. Goldsmith, Wireless communications, Cambridge university press, 2005. Article (CrossRef Link)

[10] R. W. Ouyang, A. Wong and C. Lea, "Received signal strength-based wireless localization via semidefinite programming: noncooperative and cooperative schemes," IEEE Transactions on Vehicular Technology, vol. 59, no. 3, pp. 1307-1318, March, 2010. Article (CrossRef Link)

[11] A. Coluccia, "Reduced-Bias ML-Based Estimators with Low Complexity for Self-Calibrating RSS Ranging," IEEE Transactions on Wireless Communications, vol. 12, no. 3, pp. 1220-1230, March, 2013. Article (CrossRef Link)

[12] F. Montorsi, F. Pancaldi and G. Vitetta, "Map-Aware Models for Indoor Wireless Localization Systems: An Experimental Study," IEEE Transactions on Wireless Communications, vol. 13, no. 5, pp. 2850-2862, May, 2014. Article (CrossRef Link)

[13] A. N. Bishop, B. I. C. S. Fidan, B. Anderson, K. Dogangay and P. N. Pathirana, "Optimality analysis of sensor-target localization geometries," Automatica, vol. 46, no. 3, pp. 479-492, 2010. Article (CrossRef Link)

[14] W. Meng, L. Xie and W. Xiao, "Optimality analysis of sensor-source geometries in heterogeneous sensor networks," IEEE Transactions on Wireless Communications, vol. 12, no. 4, pp. 1958-1967, 2013. Article (CrossRef Link)

[15] K. Yu and Y. J. Guo, "Statistical NLOS identification based on AOA, TOA, and signal strength," IEEE Transactions on Vehicular Technology, vol. 58, no. 1, pp. 274-286, January, 2009. Article (CrossRef Link)

[16] F. Yin, C. Fritsche, F. Gustafsson and A. M. Zoubir, "EM-and JMAP-ML Based Joint Estimation Algorithms for Robust Wireless Geolocation in Mixed LOS/NLOS Environments," IEEE Transactions on Signal Processing, vol. 62, no. 1, pp. 168-182, January, 2014. Article (CrossRef Link)

[17] S. Venkatesh and R. M. Buehrer, "A linear programming approach to NLOS error mitigation in sensor networks," in Proc. of the 5 th international conference on Information processing in sensor networks, pp. 301-308, April, 2006. Article (CrossRef Link)

[18] Y. Chan, W. Tsui, H. So and P. Ching, "Time-of-arrival based localization under NLOS conditions," IEEE Transactions on Vehicular Technology, vol. 55, no. 1, pp. 17-24, January, 2006. Article (CrossRef Link)

[19] D. Macagnano and G. de Abreu, "Algebraic Approach for Robust Localization with Heterogeneous Information," IEEE Transactions on Wireless Communications, vol. 12, no. 10, pp. 5334-5345, October, 2013. Article (CrossRef Link)

[20] Y. Wang, L. Cheng, G. Han, H. Wu and B. Jiang, "RSS Localization Algorithm Based on Nonline of Sight Identification for Wireless Sensor Network," International Journal of Distributed Sensor Networks, vol. 2014, pp. 1-8, July, 2014. Article (CrossRef Link)

[21] Y. Sun and Y. Xu, "Error Estimation Method for Matrix Correlation-Based Wi-Fi Indoor Localization," KSII Transactions on Internet and Information Systems (TIIS), vol. 7, no. 11, pp. 2657-2675, November, 2013. Article (CrossRef Link)

[22] L. Tang, K. C. Wang, Y. Huang and F. Gu, "Channel characterization and link quality assessment of ieee 802.15. 4-compliant radio for factory environments," IEEE Transactions on Industrial Informatics, vol. 3, no. 2, pp. 99-110, 2007. Article (CrossRef Link)

[23] A. F. Molisch, K. Balakrishnan, D. Cassioli, C. C. Chong, S. Emami, A. Fort, J. Karedal, J. Kunisch, H. Schantz, U. Schuster and K. Siwiak, "IEEE 802.15. 4a channel model-final report," IEEE P802, vol. 15, no. 04, pp. 662, 2004. Article (CrossRef Link)

[24] S. M. Kay, Fundamentals of statistical signal processing, volume I: Estimation theory, PTR Prentice-Hall, Englewood Cliffs, NJ, 1993. Article (CrossRef Link)

[25] G. Wang, H. Chen, Y. Li and N. Ansari, "NLOS Error Mitigation for TOA-Based Localization via Convex Relaxation," IEEE Transactions on Wireless Communications, vol. 13, no. 8, pp. 4119-4131, August, 2014. Article (CrossRef Link)

[26] L. Vandenberghe and S. Boyd, "Semidefinite programming," SIAM review, vol. 38, no. 1, pp. 49-95, 1996. Article (CrossRef Link)

[27] M. R. Gholami, R. M. Vaghefi and E. G. Strom, "RSS-based sensor localization in the presence of unknown channel parameters," IEEE Transactions on Signal Processing, vol. 61, no. 15, pp. 3752-3759, 2013. Article (CrossRef Link)

[28] M. Grant, S. Boyd and Y. Ye, "CVX: Matlab software for disciplined convex programming," ver.1.21, Feb, 2011, [Online]. http://cvxr.com/cvx/. Article (CrossRef Link)

[29] C. Yang, L. Kaplan, E. Blasch and M. Bakich, "Optimal Placement of Heterogeneous Sensors for Targets with Gaussian Priors," IEEE Transactions on Aerospace and Electronic Systems, vol. 49, no. 3, pp. 1637-1653, July, 2013. Article (CrossRef Link)

[30] J. Zhou, J. Shi and X. Qu, "Landmark placement for wireless localization in rectangular-shaped industrial facilities," IEEE Transactions on Vehicular Technology, vol. 59, no. 6, pp. 3081-3090, July, 2010. Article (CrossRef Link)

[31] B. Huang, T. Li, B. Anderson and C. Yu, "Performance limits in sensor localization," Automatica, vol. 49, no. 2, pp. 503-509, February, 2012. Article (CrossRef Link)

Received August 23, 2014; revised November 19, 2014; accepted December 13, 2014; published January 31, 2015

Riming Wang (1, 2), Jiuchao Feng (1)

(1) School of Electronic and Information Engineering, South China University of Technology Guangzhou, Guangdong, 510641, China

[e-mail: wangriming@163.com, fengjc@scut.edu.cn]

(2) School of Information Engineering, Guangdong University of Technology Guangzhou, Guangdong, 510006, China

[e-mail: wangriming@163.com]

* Corresponding author: Riming Wang

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.

Table 1. Mean and variance of localization error in the origin and improved method Mean Variance [sigma] Org Imp Org Imp 1 0.9336 1.0675 0.3607 0.0423 2 0.9177 1.0809 0.4092 0.1240 3 0.9379 1.0862 0.4355 0.1528 4 0.9966 1.0960 0.5101 0.1823 NLOS Mean Variance Org Imp Org Imp 1 1.2493 1.1775 0.6543 0.3177 2 1.3995 1.2845 0.7236 0.4188 3 1.4290 1.3018 0.7357 0.4393 4 1.3993 1.2665 0.7497 0.3989 Table 2. An example in Lab experiments Ans [absolute [[??].sub.i] [S.sub.1] numbering value of [[bar.P].sub.r,i]] 1 52.75 3.06 2 49.00 3.20 3 54.27 3.53 * 4 45.18 3.11 5 52.42 3.58 * 6 48.00 3.78 * 7 55.39 3.71 * 8 49.00 3.20 Ans [S.sub.2] [absolute value numbering of [P.sub.com] ([S.sub.2])] 1 2 3 4 5 6 * 1.07 7 * 1.59 8 Table 3. The summary of complexity and average running time Method Cost Time (s) Scene1 Scene2 Scene3 LLS O(M) 4.56e-4 6.16e-4 6.06e-4 TS-LQP O(M) 2.67e-4 5.33e-4 4.08e-4 CORR-ML 0((([2.sup. 0.04 0.87 0.75 [kappa]+1] - 1) LW/[s.sup.2. sub.0])M + [K.sub.GN] [M.sup.3]) SDP-ML 0(0([M.sup.1/2]) 0.67 1.21 1.19 [M.sup.4] + [K.sub.GN] [M.sup.3])

Printer friendly Cite/link Email Feedback | |

Author: | Wang, Riming; Feng, Jiuchao |
---|---|

Publication: | KSII Transactions on Internet and Information Systems |

Article Type: | Report |

Date: | Jan 1, 2015 |

Words: | 7695 |

Previous Article: | Network selection algorithm based on spectral bandwidth mapping and an economic model in WLAN & LTE heterogeneous networks. |

Next Article: | Half-duplex relaying strategy suitable for a relay with mobility. |

Topics: |