Abstract：To mitigate the impacts of non-line-of-sight (NLOS) errors on location accuracy, a non-parametric belief propagation (NBP)-based localization algorithm in the NLOS environment for wireless sensor networks is proposed. According to the amount of prior information known about the probabilities and distribution parameters of the NLOS error distribution, three different cases of the maximum a posterior (MAP) localization problems are introduced. The first case is the idealized case, i.e., the range measurements in the NLOS conditions and the corresponding distribution parameters of the NLOS errors are known. The probability of a communication of a pair of nodes in the NLOS conditions and the corresponding distribution parameters of the NLOS errors are known in the second case. The third case is the worst case, in which only knowledge about noise measurement power is obtained. The proposed algorithm is compared with the maximum likelihood-simulated annealing (ML-SA)-based localization algorithm. Simulation results demonstrate that the proposed algorithm provides good location accuracy and considerably outperforms the ML-SA-based localization algorithm for every case. The root mean square error (RMSE) of the location estimate of the NBP-based localization algorithm is reduced by about 1.6 m in Case 1, 1.8 m in Case 2 and 2.3 m in Case 3 compared with the ML-SA-based localization algorithm. Therefore, in the NLOS environments, the localization algorithms can obtain the location estimates with high accuracy by using the NBP method.
Key words：non-line-of-sight (NLOS); localization accuracy; wireless sensor networks
The wireless localization systems have recently become an important part of human life due to the increasing demand of location-based services. The position of the targets can be located by using the measurements obtained from the base station (BSs) whose locations are known. These measurements include signal strength (RSS), time-of-arrival (TOA), time-difference-of-arrival (TDOA), angle-of-arrival (AOA) or a combination of them. In any scenario, the location accuracy suffers from the effects of multipath propagation, fading, shadowing, environmental noise, signal bandwidth, etc., which can cause location estimate error. Particularly, whenever there are obstacles between the targets and the BSs that block the direct propagation path between them, localization accuracy faces another challenge, which arises from the NLOS radio propagation.
The harsh environments, particularly urban and indoor environments offer almost full NLOS connections between BSs and targets[1]. Woo et al.[2] demonstrated that NLOS error is the primary source of inaccuracy positioning. Therefore, it is very important for positioning systems to be able to identify the presence of NLOS measurements in the total measurements and mitigate their effects on location accuracy[3-5].
Many methods that reduce the impact of the NLOS measurements on location accuracy have been proposed. These works can be classified into two categories[6]. The first one discards the NLOS measurements from total measurements after identifying them and only the line-of-sight (LOS) measurement is used for positioning. The second one takes all LOS and NLOS measurements into the process of the location estimate.
A prior NLOS measurement correction (PNMC) method was proposed in Ref.[7], which finds the knowledge of the ratio of the NLOS measurements in the total recorded measurements. These NLOS measurements are discarded from the location process if they are a small portion of total measurements; otherwise, they are corrected by separating the range of possible values of NLOS errors into equiprobable segments. Through subtracting the expected error in each segment, all of the NLOS measurements are corrected. This method can cause the NLOS estimates to be very similar to those obtained from the measurements in LOS propagation. There are two reasons that make the discarding of the NLOS range measurements an unwise choice. One reason is that the numbers of available neighbor BSs for the locating process in cellular networks are usually not many, and the limited connectivity with anchors in sensor networks makes the number of available range estimates for the location process limited; and the other reason is that the NLOS range estimates themselves have information about the location. Therefore, it is necessary to use the entire set of range measurements to compute the targets’ locations in order to improve the performance of the localization system.
The authors in Ref.[8] described the indoor ranging error as a dynamic Gaussian model, in which the instantaneous LOS or NLOS error at a typical time was regarded as the drift from this general distribution dynamically. According to the dynamic Gaussian model, a measurement adaptation method was proposed to reduce the error caused by NLOS conditions. Li et al.[9] took the correlation between TDOA measurements caused by NLOS errors into account to reduce the effects of NLOS errors on the performance of the localization problem of semi-static targets.
Some of the above methods are deployed under the assumption that the NLOS range measurements have been identified (that may not occur in actual systems). More-over, some of them have high computational complexity.
In this article, the node localization problem in wireless sensor networks is formulated as an inference problem on a graphical model to apply NBP[10], a variant of the belief propagation (BP) algorithm[11], to obtain an approximate solution. Based on a priori information on NLOS error, we propose an NBP-based localization algorithm which can effectively incorporate both LOS and NLOS range measurements into the location estimate process of the nodes.
1.1 Network model
We consider a network consisting of a set of m anchor nodes (anchors) named as 
a and a set of n-m sensor nodes (sensors) named as s. The set of all nodes in the network is then defined as =a∪s. Nodes are located in a two-dimensional Euclidean space R2 and the position of each node is regarded as a stochastic vector with prior density, p(xi), i=1,2,…,n. In addition, the location of anchors is known and the sensors’ locations need to be estimated.
Naturally, we can use an undirected graph G(V,Es∪Ea) to present a sensor network localization problem in terms of geometrical networks, where V is the set of all nodes; Es is the set of sensor-sensor edges; and Ea is the set of sensor-anchor edges. A pair of nodes (i,j)∈E, E=Es∪Ea means that they are in communication range R of each other and a subset F∈V is fully connected if any two nodes (i,j)∈F are connected. Similarly, we use χLOS and χNLOS to denote the set of index pairs to show the measurement between nodes is LOS and NLOS, respectively. The set of all range measurements is then defined as χ=χLOS∪χNLOS=E.
1.2 Problem formulation
The measurement distance rij between node i and node j obtained by some detection probability 
is given as
rij=dij+bij+nij (i,j)∈χ
(1)
where 
2 is the true distance between node i and node j; 
) is the measurement noise which follows a zero-mean Gaussian distribution with variance 
; and bij is the extra distance caused by NLOS propagation in addition to the LOS distance. Without loss of generality, we here assume that bij follows an exponential distribution 
) with mean λij and variance 
. The value of bias bij=0 as an LOS path exits between node i and node j, i.e., (i,j)∈χLOS and, otherwise, bij≠0 if (i,j)∈χNLOS.
Let an indicator binary variable be defined as
(2)
and assume that all the measurements are mutually independent. The joint posterior probability density function (PDF) of sensors is then given by
·
·
P(xm+1,xm+2,…,xn)
(3)
The location estimate of sensors is produced by maximizing the joint posterior PDF and it is expressed as
(4)
NBP is an inference algorithm for graphical models containing continuous, non-Gauss random variables. NBP extends the popular class of particle filtering algorithms, which assume that variables are related to a Markov chain on general graphs. Recently, the NBP algorithm has been applied in many fields, particularly in localization. The evolution of the NBP-based localization algorithms can be described as follows[12].
At the beginning, each node obtains its local information p(xi). If available, it broadcasts its ID number while listening to the IDs of other nodes. After that it computes the distance to the nodes it received the IDs from. At the first iteration, t=1, the particles of nodes are deployed randomly in the feasible region generated by the convex hull of its neighbor nodes. The weights of these particles are set to be 1, and the posterior marginal is set as
p0(xi)≅pi(xi) i=1,2,…,n
(5)
At iteration t=ti+1, given the weighted 
of node i obtained at previous iteration t=ti, in which Np is the number of particles, we derive the measurement distance from these particles of node i to its neighbor node j as
(6)
A particle of the message between a pair of nodes (i,j) is then drawn by shifting the coordinates of particle 
in the direction of θk～U(0,2π) by an amount of the estimated distance rij, that is
∀
(7)
In the case where node i is anchor, i.e., i∈a, the message received at neighbor node j of node i is
(8)
where 
is the set of neighbor nodes of node i, and ψij(xi,xj) is the pairwise potential between nodes i and j. The outgoing message 
) of the neighbor nodes j of node i is computed based on 
(xj) received from node i at iterative ti-1, that is
(9)
The weight of the message obtained at each particle then becomes
(10)
The evolution process will be repeated until the algorithm obtains a sufficient convergence. After that, the estimate position of node i is the product of particle 
and its weight 
is
(11)
Due to the existence of the indefiniteness of the wireless channel and other reasons as aforementioned before, there is some uncertainty in the estimate position of the nodes. Being unique to other localization algorithms, NBP-based localization algorithms can tell you the reliability (belief) of the estimate position, which is computed as
(12)
To verify the performance of algorithms in NLOS propagation conditions, we consider the scenario in which all of the neighbor nodes of the sensors are anchors, and the distance measurements between sensors and anchors are 1-hop measurements. Furthermore, the channel is assumed to be reciprocal, i.e., sij=sji, rij=rji, lij=lji, 
.
Based on the surveyed data, we can obtain some priori information about the NLOS errors. This priori information is very helpful for the location estimation, due to the fact that the accuracy of the estimate location depends on how much priori information is available in several cases. In this subsection, three different cases are introduced according to the amount of the priori information we have.
3.1 Idealized case: known NLOS status and distribution parameters
In this ideal case, the knowledge of which range measurements are under NLOS conditions and the distribution parameters of NLOS errors are perfectly known.
3.1.1 ML-based localization
Assuming that the distribution of the stochastic vector of sensors p(xi), i=m+1,m+2,…,n is uniform, the MAP estimate coincides with the maximum likelihood estimate.
The joint likelihood function of Xs={xm+1,xm+2,…,xn}T can be written as
·
(13)
where pbij and pnij denote the PDFs of bij and nij, respectively. To facilitate the maximization of Eq.(13), the logarithmic version is considered,
(14)
As the first term is independent of Xs, maximizing Eq.(14) is in fact equivalent to minimizing the second term and the ML location estimation of sensors then can be formulated as
(15)
3.1.2 NBP-based localization
To reduce complexity, which is the challenge of the ML-based localization algorithms, NBP factorizes the joint posterior PDF in Eq.(4).
The message received at each particle of sensor i from its neighbor anchor j is given as follows.
For (i,j)∈χLOS, i.e., the neighbor anchor j has an LOS link with sensor i, then,
(16)
Hence, the weight of the LOS message is
(17)
Also, for (i,j)∈χNLOS, i.e., the neighbor anchor j has an NLOS link with sensor i, then,
(18)
Hence, the weight of the NLOS message is
(19)
The estimate position of each sensor then is given by
(20)
3.2 Known NLOS probability and distribution parameters
In this case, we do not know which range measurements are under the NLOS conditions, but we have a priori information about NLOS probability and the corresponding distribution parameters.
3.2.1 ML-based localization
The joint likelihood function in this case can be written as
(21)
where 
is the probability that sensor i has an LOS link with anchor j; and 
is the probability that there is an NLOS link between sensor i and anchor j. Similarly to Eq.(15), the location estimation of each sensor can be formulated as
(22)
3.2.2 NBP-based localization
The message received at each particle of sensor i from its neighbor anchor j becomes
(23)
q.(16) and Eq.(18). The weight of message is expressed as
(i,j)∈χ
(24)
The estimate position of each sensor in this case is
(25)
3.3 Known distribution parameters only
In this subsection, we consider the worst case, in which only the distribution parameters δij and λij are known. To estimate the position of sensors, we need to draw a possible feasible region in which the sensors lie. In other words, we need to obtain the upper bounds as well as the lower bounds for the distance measurements of each pair of nodes without knowing whether the distance measurements are under the LOS or NLOS conditions.
We know that the measurement distance under NLOS conditions is significantly larger than their true distance. Therefore, the upper bound of a measurement distance can be given by
(26)
The lower bound is given based on the min-max method as
(27)
3.3.1 ML-based localization
For constraint 
, it is easy to see that there is one position estimate lying on a circle[13], which has its centre at xi and radius 
.
The location estimation of the sensors can be determined by minimizing the following expression:
(28)
Expanding (28) yields
(29)
As the 
2 is the constant, therefore, the optimization problem for locating sensors is equivalent to
(30)
3.3.2 NBP-based localization
Similar to the case of the ML-based localization, the message between a pair of nodes is expressed as
(31)
The weight of each outgoing message is
(32)
Finally, the estimate position of each sensor is
(33)
Remark To solve the localization problem in Eq.(5), we need to marginalize the joint posterior PDF, 
}), which is not tractable for the localization problem, because this marginalization will have exponential complexity with respect to the number of sensors. There are two approaches that are given in our work to overcome this problem: 1) The localization problem (5) is converted to an ML problem and then it is solved by the SA algorithm; 2) The localization problem is solved by the aforementioned message-passing method NBP.
We consider a network of six nodes including five anchors and one sensor deployed in a two-dimensional region with the size of 40 m×40 m.
We assume that the sensor can communicate with all the anchors. For the noise standard deviation δi of measurement error and the mean λi of NLOS error of a range measurement between anchor i and the sensor, we assume that they are identical for all range measurements, i.e., δi=δ and λi=λ.
To verify the performance of the algorithms, the following simulations are carried out, in which the performance is evaluated in terms of RMSE.
4.1 Relationship between the number of neighbors of the sensor and the belief of its estimate position
In this subsection, we provide simulation results with the belief of the sensor’s estimate position as the number of the neighbor anchors of the sensor varies.
Fig.1(a) plots the belief of the sensor’s estimate positions as the sensor is localized with only one neighbor anchor. The possible position estimate of the sensor lies on a circle, which has its center at the anchor and the radius equal to the measurement distance of the anchor-sensor. This is because the positioning problem is solved by only one positioning equation in this case. As the number of the neighbor anchors is two, the positioning problem has two solutions, as shown in Fig.1(b). Also, the positioning problem has a unique solution as the number of neighbor anchors is equal to or larger than three, as shown in Fig.1(c). The magnitude of these estimate positions represents their reliability, the higher the belief, the higher the reliability, and the lower the positioning error.
(a)
(b)
(c)
Fig.1 Belief of the sensor estimate position. (a) m=1; (b) m=2; (c) m=3
4.2 RMSE as a function of noise standard deviation
In this subsection, we provide simulation results of the performance of the NBP-based and ML-SA-based localization algorithms in three cases depending on the amount of NLOS error prior information as the measurement noise standard deviation varies.
The number of NLOS anchors is set to be 1 and the mean of the NLOS error λ is set to be 5 m. The probability 
that a range measurement between anchor i and the sensor is an LOS measurement is set to be 0.3, meaning that the probability of a range measurement between anchor-i and the sensor is an NLOS measurement equivalent to 0.7.
From Fig.2, we see that the values of RMSE for both the NBP-based and ML-SA-based localization algorithms increase when the noise level increases from 1 to 6 m. The accuracy of the sensor’s location estimate is best when the NLOS status and distribution parameters are known exactly and is worst when only the distribution parameters are known. We can see that, under NLOS conditions, the NBP-based localization algorithm provides significantly better performance than that of the ML-SA-based localization algorithms. For example, when δ=6 m, the RMSE of the NBP-based localization algorithm is reduced by about 2 m compared to the ML-SA-based localization algorithm in the case that only the information about distribution parameters is known.
(a)
(b)
(c)
Fig.2 RMSE vs. noise standard deviation. (a) Case 1; (b) Case 2; (c) Case 3
4.3 RMSE as a function of the number of NLOS anchors
In this subsection, we provide the simulation results of the performance of the NBP-based and ML-SA-based localization algorithms as the number of NLOS anchors varies from 0 to 3. From Fig.3, we can see that the RMSE of both of the algorithms significantly increases when the number of NLOS anchors varies from 2 to 3, about 2.2 m in the NBP-based algorithm and 3.2 m in the ML-SA-based algorithm. For example, the RMSE of the NBP-based localization algorithm is reduced by about 3 m compared to the ML-SA-based algorithm as the number of NLOS anchors is 3.
Fig.3 RMSE vs. the number of NLOS anchors
An NBP-based node localization algorithm in the NLOS environments is proposed. All the LOS and NLOS range measurements are incorporated into the localization process, and there is no range information discarded. Given the priori information about NLOS error distribution, three cases of localization problems are introduced. The simulation results show that the proposed algorithm can achieve high performance in terms of location accuracy; even for the case in which the NLOS and LOS range measurements are not identifiable.
References：
[1]Silventoinen M, Rantalainen T. Mobile station locating in GSM [C]//IEEE Wireless Communication System Symposium. New York, USA, 1996: 53-59. DOI: 10.1109/WCSS.1995.588481.
[2]Woo S-S, You H-R, Koh J-S. The NLOS mitigation technique for position location using IS-95 CDMA networks [C]//The 52nd Vehicular Technology Conference. Boston, USA, 2000: 2556-2560. DOI: 10.1109/VETECF.2000.886790.
[3]Xiao Z L, Wen H K, Markham A. Non-line-of-sight identification and mitigation using received signal strength [J]. IEEE Transactions on Wireless Communication, 2015, 14(3): 1689-1702. DOI: 10.1109/TWC.2014.2372341.
[4]Almazrouei E, Al Sindi N, Al-Araji S R, et al. Measurement and analysis of NLOS identification metrics for WLAN systems [C]//IEEE 25th Annual International Symposium on Personal, Indoor, and Mobile Radio Communication (PIMRC). Washington DC, USA, 2014: 280-284. DOI: 10.1109/PIMRC.2014.7136175.
[5]Nguyen T V, Jeong Y M, Shin H D, et al. Machine learning for wideband localization [J]. IEEE Journal on Selected Area in Communications, 2015, 33(7): 1357-1380. DOI:10.1109/JSAC.2015.2430191.
[6]Liu D W, Lee M-C, Pun C-M, et al. Analysis of wireless localization in nonline-of-sight conditions [J]. IEEE Transactions on Vehicular Technology, 2013, 62(4): 1484-1492. DOI:10.1109/tvt.2013.2244928.
[7]Mazuelas S, Lago F A, Blas J, et al. Prior NLOS measurement correction for positioning in cellular wireless networks [J]. IEEE Transactions on Vehicular Technology, 2009, 58(5): 2585-2591. DOI:10.1109/tvt.2008.2009305.
[8]Zhao Y B, Yang Y, Kyas M. Adaptive range-based nonlinear filters for wireless indoor positioning system using dynamic Gaussian model [J]. IEEE Transactions on Vehicular Technology, 2015, 64(9): 4282-4291. DOI:10.1109/TVT.2014.2364045.
[9]Li S, Hedley M, Collings I B, et al. TDOA-based localization for seme-static targets in NLOS environments [J]. IEEE Wireless Communication Letters, 2015, 4(5): 513-516. DOI:10.1109/lwc.2015.2449306.
[10]Sudderth E B, Ihler A T, Isard M, et al. Nonparametric belief propagation [J]. Communications of the ACM, 2010, 53(10): 95-103. DOI:10.1145/1831407.1831431.
[11]Pearl J. Probabilistic reasoning in intelligent systems [M]. San Francisco, CA, USA: Morgan Kaufmann Publishers Inc., 1988.
[12]Ihler A T, Fisher J W, Moses R L, et al. Nonparametric belief propagation for self-localization of sensor networks [J]. IEEE Journal on Selected Areas in Communications, 2005, 23(4): 809-819. DOI:10.1109/jsac.2005.843548.
[13]Chen H Y, Wang G, Wang Z Z, et al. Non-line-of-sight node localization based on seme-definite programming in wireless sensor networks [J]. IEEE Transactions on Wireless Communications, 2012, 11(1): 108-116. DOI:10.1109/twc.2011.110811.101739.
摘要：为了减少定位精度上由于NLOS误差造成的影响,基于非参数信任传输(NBP)方法建立一种在NLOS环境下的定位算法.根据NLOS误差的分布概率及分布参数的先验信息量,给出了3种不同情况下定位问题的最大后验概率.第1种情形为理想化情形，即已知NLOS环境下的距离测量及相应的NLOS误差分布参数.在第2种情形中，仅已知任意2个节点之间的通信处于NLOS环境下的概率及相应的NLOS误差分布参数.第3种情形为最差情形,仅获得测量误差的信息.将所提算法与基于最大似然退火法(ML-SA)的定位算法进行了比较,仿真结果表明:在每种情形下所提算法获得的定位精度都远超过基于ML-SA的定位算法.在3种不同情形下基于NBP定位算法的位置估计均方根误差比基于ML-SA的定位算法分别降低了1.6,1.8和2.3 m左右.因此,在NLOS传输环境下,采用NBP的定位算法可获得较高的定位精度.
关键词：NLOS误差;定位精度;无线传感器网络
中图分类号：TN929.5
Foundation item：The National Natural Science Foundation of China (No. 61271207,61372104).
Citation：：Bui Thi Oanh, Xu Pingping, Zhu Wenxiang, et al. NBP-based localization algorithm for wireless sensor networks in NLOS environments[J].Journal of Southeast University (English Edition),2016,32(4):395-401.
DOI：10.3969/j.issn.1003-7985.2016.04.001.
DOI：10.3969/j.issn.1003-7985.2016.04.001
Received 2016-05-28.
Biographies：Bui Thi Oanh(1984—), female, graduate; Xu Pingping (corresponding author), female, doctor, professor, xpp@seu.edu.cn.