# Mean Shift-Based Mobile Localization Method in Mixed LOS/NLOS Environments for Wireless Sensor Network

Authors: Xiaosheng Yu; Peng Ji; Ying Wang; Hao Chu
Journal: Journal of Sensors
 (2017)

---

## Abstract

Mobile localization estimation is a significant research topic in the fields of wireless sensor network (WSN), which is of concern greatly in the past decades. Non-line-of-sight (NLOS) propagation seriously decreases the positioning accuracy if it is not considered when the mobile localization algorithm is designed. NLOS propagation has been a serious challenge. This paper presents a novel mobile localization method in order to overcome the effects of NLOS errors by utilizing the mean shift-based Kalman filter. The binary hypothesis is firstly carried out to detect the measurements which contain the NLOS errors. For NLOS propagation condition, mean shift algorithm is utilized to evaluate the means of the NLOS measurements and the data association method is proposed to mitigate the NLOS errors. Simulation results show that the proposed method can provide higher location accuracy in comparison with some traditional methods.


---

## Body

## 1. Introduction

Wireless localization is one of the technologies in the fields of the intelligent robot, national security, and health surveillance [1] and has received the researcher’s considerable attention in the past decades. With the increase of the demand for positioning service, many wireless positioning systems have been developed, among of which Global Positioning System (GPS) is one of the most popular localization systems. However, GPS is not able to provide the desirable performance when the receiver is in indoor environments. Wireless sensor network (WSN) is a novel technology with rapid diffusion. Location is a significant application of WSN. The WSN-based location methods have widely been used for indoor location [2, 3].In the WSN-based localization approaches’ design, the location of the beacon nodes and the measurements between the beacon nodes and unknown node are assumed to be the known prior information. Generally, there are four measurement methods: time of arrival (TOA) [4], time difference of arrival (TDOA) [5], received signal strength (RSS) [6], and angle of arrival (AOA) [7]. However, there are many objects located in some practical environments. These objects may block the direct propagation path which leads to the non-line-of-sight (NLOS) environments. The measurement contains a positive bias which is termed as NLOS error. In this environment, the performance of the conventional positioning methods will degrade dramatically. Therefore, the accurate localization in the NLOS environments has been a significant topic.In this paper, we propose a novel location algorithm which can solve the NLOS errors. This paper is structured as follows: related works are introduced in Section2. System model and mean shift methods are described in Section 3. Section 4 presents the proposed algorithm. The performance evolution of the proposed algorithm is shown in Section 5. Section 6 presents the conclusions.


## 2. Related Works

In order to solve the NLOS errors, researchers proposed numerous methods. These methods can be generally divided into two types [8]: hard-decision ones and soft-decision ones. In the first methods, an identification and discard strategy is employed, which means that the NLOS measurements are firstly identified and then discarded. The localization is only dependent on the line-of-sight (LOS) measurements. There are many promising approaches to be proposed to estimate the propagation paths [8–11]. These kinds of algorithms require accurate identification and enough LOS measurements which are not suitable in some practical environments. The second methods utilize all of the measurements with different weights to locate the target. The interacting multiple model (IMM) with different filter approaches such as the Kalman filer [12], the extended Kalman filer [6, 13, 14], the cubature Kalman filer [15], and the hidden Markov models [16] can be considered as the most classical soft-decision methods. These kinds of methods are practical when only a small number of measurements can be used for positioning. Most of the methods mentioned above were designed with the prior information of the NLOS errors. But, in practical and complicated environments, the prior information is usually unknown.There are many approaches proposed to realize the accurate location without any prior knowledge of statistical information of the NLOS measurements. These methods are termed as nonparametric methods. In [17], Chen proposed a residual weighting (Rwgh) algorithm. The residuals are presented to compute the weights for the initial node coordinates from the least squares estimation of all possible combinations of the measurements. The final localization result is obtained by weighting these initial results. In [18], Yu et al. constructed a voting matrix to estimate the initial localization results and then employed the residual weighting to acquire the final estimated position. In [19, 20], Garcia et al. utilized a training strategy to obtain the training measurements. The final position is estimated by using these measurements. In [21], Lloret et al. proposed a novel stochastic algorithm which is based on a combination of deductive and inductive methods to decide the estimated position. In [22, 23], the statistical features including mean, variance, and Rician K factor are used to train the support vector machine (SVM) classifier to identify the propagation condition. They can obtain the desirable results with enough training samples. In [24], a min–max strategy is invented to identify the propagation paths by constructing a detection region according to the range measurements. If the localization is far away from the edge of the region, the propagation is an NLOS propagation. In [25], Cheng et al. employed the Gaussian mixture distributions to describe the distributions of NLOS errors and the estimated mean is used for poisoning in the Kalman filter frame. In [26], Hu et al. proposed a probabilistic data-association-based IMM approach to improve the location accuracy in the rough environment. The position estimation is performed by using an IMM frame and then the PDA approach is employed to correct it.Most of the nonparametric methods mentioned above were designed with the assumption that the obstacles are fixed. But, in the practical and complicated environments, the positions of the obstacles may be changed dynamically. These nonparametric methods cannot provide desirable position estimation in mixed LOS/NLOS environments where some obstacles are always moving. This paper presents an efficient mobile node localization approach which is termed as improved Kalman filter (IKF) based on mean shift [27] to overcome the NLOS effect in mixed LOS/NLOS environments. Our algorithm has the desirable location ability without any prior knowledge of statistical information of the NLOS measurements. The simulation results demonstrate its effectiveness.


## 3. Background

In this section, we consider the scenario withM beacon nodes and an unknown node. These beacon nodes are randomly distributed, and their coordinates are known which are given by θn=xn,ynT, where n=1,…,N. There are many obstacles deployed in the field whose positions are not given. At time k, the target is moving in the area and its position is denoted by xk,ykk=1,2,…K. The wireless signal is transmitted from the beacon nodes to the unknown node. The measured distance is estimated by TOA. The illustration of the LOS/NLOS propagation is show in Figure 1.Figure 1
The LOS/NLOS propagation.


### 3.1. System Model

At timek, the range measurements between the unknown node and nth (n = 1,…, N) beacon node can be acquired, which is represented by the following:
(1)znk=dnk+εn,k=1,…,K,where dnk=xk−xn2+yk−yn2 stands for the true distance. εn is noise which has different forms in the LOS environment and NLOS environment. Generally, εn is modeled by
(2)εn=vn,LOS;vn+bNLOS,NLOS,where vn is the measurement noise, vn~N0,σn2. The NLOS error bNLOS is often regarded as a positive bias due to the longer indirect propagation path in NLOS condition and independent of vn. The NLOS error bNLOS is different from vn which may follow different distributions [28], such as Gaussian distribution, uniform distribution, and exponential distribution in different conditions.In the LOS propagation environment, the probability density function (PDF) ofεn is
(3)pLεn=12πσn2exp−εn22σn2.In the NLOS propagation environment,εn has different forms because the NLOS error bNLOS may obey different distributions. When bNLOS obeys a Gaussian distribution, bNLOS~Nμb,σb2, the PDF of εn is
(4)pNLεn=12πσε2exp−εn−μb22σe2,where σε2=σb2+σn2. When bNLOS obeys a uniform distribution, bNLOS~Uumin,umax, the PDF of εn can be described as follows:
(5)pNLεn=1umax−uminQεn−umaxσn−Qεn−uminσn,where Q() stands for the cumulative distribution function of the standard normal distribution. When bNLOS obeys an exponential distribution, bNLOS~Eλ, the PDF of εn is as follows:
(6)pNLεn=λ2exp−λεn−λ2σn22Φλσn2−εn2σn,where λ is a positive constant and Φ is the complementary error function.


### 3.2. Mean Shift Method

The prior knowledge of the NLOS errors cannot be obtained in practical environment. The mean shift method is employed to approximate the probability density. It is assumed that there areM range measurements z^k=z^1k,…,z^Mk at time k. For an initial estimate zk, the weighted mean of the measurements z^k is determined as follows:
(7)νzk=∑z^jk∈NzkKMz^jk−zkz^jk∑z^jk∈NzkKMz^jk−zk,where Nzk stands for the neighborhood of the initial estimate zk and Nzk∈z^k and KMx≠0 stands for the kernel function with the following forms:
(8)KEMx=c1−x2,x≤1,0,otherwise,KUMx=cx≤1,0,otherwise,KNMx=c⋅exp−12x2.This kernel function is used to determine the weights of the neighborhood data to re-estimate the mean. In the practical application, there are many initial estimates required to obtain the desirable results. The weighted means can be obtained through an iteration process. This method always sets the initial estimateszk constantly to obtain the new estimations of vzk, and the estimation process always repeats until vzk is converged.


## 3.1. System Model

At timek, the range measurements between the unknown node and nth (n = 1,…, N) beacon node can be acquired, which is represented by the following:
(1)znk=dnk+εn,k=1,…,K,where dnk=xk−xn2+yk−yn2 stands for the true distance. εn is noise which has different forms in the LOS environment and NLOS environment. Generally, εn is modeled by
(2)εn=vn,LOS;vn+bNLOS,NLOS,where vn is the measurement noise, vn~N0,σn2. The NLOS error bNLOS is often regarded as a positive bias due to the longer indirect propagation path in NLOS condition and independent of vn. The NLOS error bNLOS is different from vn which may follow different distributions [28], such as Gaussian distribution, uniform distribution, and exponential distribution in different conditions.In the LOS propagation environment, the probability density function (PDF) ofεn is
(3)pLεn=12πσn2exp−εn22σn2.In the NLOS propagation environment,εn has different forms because the NLOS error bNLOS may obey different distributions. When bNLOS obeys a Gaussian distribution, bNLOS~Nμb,σb2, the PDF of εn is
(4)pNLεn=12πσε2exp−εn−μb22σe2,where σε2=σb2+σn2. When bNLOS obeys a uniform distribution, bNLOS~Uumin,umax, the PDF of εn can be described as follows:
(5)pNLεn=1umax−uminQεn−umaxσn−Qεn−uminσn,where Q() stands for the cumulative distribution function of the standard normal distribution. When bNLOS obeys an exponential distribution, bNLOS~Eλ, the PDF of εn is as follows:
(6)pNLεn=λ2exp−λεn−λ2σn22Φλσn2−εn2σn,where λ is a positive constant and Φ is the complementary error function.


## 3.2. Mean Shift Method

The prior knowledge of the NLOS errors cannot be obtained in practical environment. The mean shift method is employed to approximate the probability density. It is assumed that there areM range measurements z^k=z^1k,…,z^Mk at time k. For an initial estimate zk, the weighted mean of the measurements z^k is determined as follows:
(7)νzk=∑z^jk∈NzkKMz^jk−zkz^jk∑z^jk∈NzkKMz^jk−zk,where Nzk stands for the neighborhood of the initial estimate zk and Nzk∈z^k and KMx≠0 stands for the kernel function with the following forms:
(8)KEMx=c1−x2,x≤1,0,otherwise,KUMx=cx≤1,0,otherwise,KNMx=c⋅exp−12x2.This kernel function is used to determine the weights of the neighborhood data to re-estimate the mean. In the practical application, there are many initial estimates required to obtain the desirable results. The weighted means can be obtained through an iteration process. This method always sets the initial estimateszk constantly to obtain the new estimations of vzk, and the estimation process always repeats until vzk is converged.


## 4. Proposed NLOS Localization Method

The range measurements play the significant roles in the whole process of mobile localization. We adopt the high-frequency measurements [29], the reliable data. Therefore, at time k, we can obtain M range measurements z^nk=z^n1k,…,z^nMk between the target and the nth beacon node. Their mean value is
(9)γnk=1M∑m=1Mz^nmk.We define the following state vector of the unknown node relative to thenth beacon node at time k:
(10)Xnk=γnk,γ̇nkT,k=1,…,K,where γ̇nk stands for the velocity.The corresponding state model is(11)Xnk+1=AXnk+Gωnk,where A=1t01 stands for the state transition matrix, G=t2/2t, t stands for the sample period, and ωnk stands for the random process noise.The measurement equation in the mixed propagation environment is(12)Znk=HXnk+εn,where H=1,0 stands for the observation matrix and εn is the noise.Figure2 indicates the architecture of the proposed improved Kalman filter. Firstly, the Kalman prediction step is carried out. Secondly, a hypothesis and an alternative method are utilized to detect the channel conditions. Thirdly, in the NLOS condition, the mean shift method is used to calculate the weighted means of the range measurements and a novel algorithm is proposed to provide the measurement residual for data association. Fourthly, the Kalman update step is implemented. Finally, the maximum likelihood algorithm is employed to obtain the final position with the filtered range measurements. The detailed steps of the proposed algorithm are listed below.Figure 2
Structure of the improved Kalman filter.Step 1
(Kalman predication). It is assumed thatX^n0∣0~NXn0,Pn0∣0 is known to complete the initialization of the Kalman filter. For the time interval k=1,…,K, the conventional time update equation of Kalman filter is expressed as follows:
(13)X^nk+1k=AX^nkk,Pnk+1k=APnkkAT+GQGT,where X^nk+1∣k and X^nk∣k represent the predicted and updated state estimate, respectively, of the state vector of the unknown node relative to the nth beacon at time k. Pnk∣k and Pnk+1∣k represent the predicted and updated covariance. Q denotes the variance of the process noise.
The measurement residual is defined by the following:(14)Enk+1=γnk+1−Z^nk+1k,(15)Z^nk+1k=HX^nk+1∣k.
The innovation covariance matrix is expressed as follows:(16)Snk+1=HPnk+1kHT+Q.
The Kalman gain is expressed as follows:(17)Knk+1=Pnk+1kHTSnk+1−1.Step 2
(NLOS detection). We employ the hypotheses and alternatives [8] to detect the NLOS propagation. According to the above equations, in LOS condition, it can be summarized that
(18)Enk~N0,Snk,where N0,Snk stands for the Gaussian density function of Enk with zero mean and variance Sn2k. Due to (18), the test statistic Γnk is defined as follows:
(19)Γnk=EnkTSnkEnk.
The following hypotheses and alternative are utilized to identify the propagation condition:(20)H0:Γnk≥ξ,H1:Γnk<ξ,where ξ is the threshold. If Γnk is larger than ξ, the hypotheses, H0, and the range measurements are obtained in the LOS condition. Otherwise, the range measurements contain the numerous NLOS errors.Step 3
(mean shift-based data association). In the NLOS condition, the mean shift method is employed to compute the weighted means of the measurementsz^nk with the corresponding l initial estimates zk=z1k,…,zlk.
(21)νizk=∑z^jk∈NzkKMz^jk−zkz^jk∑z^jk∈NzkKMz^jk−zk.
The output resultνi can be obtained through an iterative process, and the corresponding measurement residuals are given by the following:
(22)Eik+1=νi−Z^nk+1k,i=1,…,I.
Ifνi is the LOS measurement, it is similar to the predicted measurement. Hence, the weights for each measurement residual are given by the following:
(23)μik=NEik;0,Snk∑i=1INEik;0,Snk.
The output of the mean shift-based data association is expressed as(24)Enk=∑i=1IEikμik.Step 4
(Kalman update). In the LOS environment,Enk is computed according to (14). In the NLOS environment, Enk is computed according to (24). The final state estimate can be obtained using the following equation:
(25)X^nk+1k+1=X^nk+1k+Knk+1Enk+1.
The covariance can be updated as follows:(26)Pnk+1k+1=Pnk+1k−Knk+1Snk+1Knk+1T.
After obtaining the state estimation vectorX^nk+1∣k+1, the filtered measurements are as follows:
(27)z~nk=ΩX^nk+1k+1,Ω=1,0.Step 5
(ML-based location). We use the ML method to realize the final localization estimation. As mentioned above, the coordinates of the beacon nodes arex1,y1,x2,y2,…,xn,yn as the prior information. The evaluated coordinate of the target is denoted by Yk=xk,ykT, and the processed range measurements are denoted by z~nk at time k. The following linear equation is summarized as follows:
(28)DYk=B,where
(29)D=2x1−x2y1−y2x1−x3⋮x1−xNy1−y3⋮y1−yN,B=z~2k2−z~1k2−x12+y12+x22+y22z~3k2−z~1k2−x12+y12+x32+y32⋮z~Nk2−z~1k2−x12+y12+xN2+yN2.
The final position of the moving target can be obtained as follows:(30)Yk=DTD−1DTB.


## 5. Performance Evaluation

The location ability of the proposed approach in the mixed LOS/NLOS environments is tested through the following simulations in this section. The proposed improved Kalman filter (IKF) algorithm is compared with the maximum likelihood (ML) algorithm, the residual weighting (Rwgh) algorithm, and the Kalman filter (KF) algorithm to validate its effectiveness. We consider a 100 m × 100 m square area. There are seven beacon nodes in this area. The target is moving in this field with the velocity of 1 m/s. The obstacles are distributed randomly, and their positions are always changed dynamically. Figure3 shows the diagram of the simulation environment. We assumed that the communication ranges for all sensor nodes are the same which are equal to 150 m. The measure noise vn is the white Gaussian noise with variance σn (defaulted as 1), vn~N0,1. The NLOS errors obey Gaussian distribution, uniform distribution, and exponential distribution, respectively. We carry out 2000 Monte Carlo runs to obtain the simulation results of these four algorithms in each case.Figure 3
Diagram of the simulation environment.The location ability of these four approaches is evaluated by the average location error:(31)ALE=1K⋅ti∑i=1ti∑k=1Kxk−x^ik2+yk−y^ik2,where K = 2000, ti=100, and xk,yk and x^ik,y^ik denote the real position and the estimated position of the moving target at time k.Firstly, we discuss the location ability of these four methods in the case of Gaussian distribution, in which the NOLS errorbNLOS~Nμb,σb2. Both Figures 4 and 5 display the different simulation results in the two cases. The relationship between the mean of the NLOS errors μb and the average location error is indicated in Figure 4. During the whole simulation process, the variance of the NLOS errors σb2 is equal to 3. The mean of NLOS errors varies from 1 to 5. Obviously, the average location errors of these four algorithms all rise when the parameter μb increases. The localization ability of ML is the worst because its average location errors have the most rapid rising. The proposed IKF method outperforms the other three methods. It always has the highest localization accuracy than ML, Rwgh, and KF methods, about 26.73%, 14.17%, and 13.69%, respectively.Figure 4
μ
b versus ALE.Figure 5
σ
b
2 versus ALE.We illustrate the variance of NLOS errors versus the average location error of these four approaches as shown in Figure5. In this simulation, the parameter μb is equal to 3. The variance of NLOS errors varies from 1 to 6. It can be seen that these four algorithms are all sensitive to the variance of NLOS errors. The location performance degrades with the increment of the variance of NLOS errors. By contrast, the proposed IKF method always has the best performance than the other three methods.Secondly, we discuss the location ability of these four methods in the case of uniform distribution, in which the NOLS errorbNLOS~Uumin,umax. In this simulation, the parameter umin is equal to 3. Figure 6 indicates the relationship between the parameter umax and the average location error. It is obvious that the performance of the ML methods is almost the worst. The average location error of the KF method always rises with the increment of the parameter umax. The average location errors of the both the Rwgh and IKF algorithms rise when the parameter umax≤6. The location accuracy of both the Rwgh and IKF algorithms improves significantly when umax>6 due to their robustness to the large NLOS errors. The performance of the IKF algorithm is always the best.Figure 6
u
max versus ALE.Finally, we investigate the performance of the four approaches with the assumption that the NLOS errors obey the exponential distributionbNLOS~Eλ. In this simulation, the parameter λ varies from 1 to 6. Figure 7 indicates the relationship between the parameter λ and the average location error. It is obvious that the ML method always owns the worst location performance. The proposed method offers the better location estimation than the other three methods.Figure 7
λ versus ALE.


## 6. Conclusion

We investigated the mobile localization in rough environments and presented a novel IKF algorithm which can realize the accurate mobile node localization. The proposed IKF algorithm is independent of prior information. In the whole location process, the NLOS errors are completely unknown. In the simulation, the proposed method is compared with three traditional algorithms. The simulation results illustrate that the proposed IKF approach has the best performance. It has higher localization accuracy than KF, Rwgh, and ML methods about 32.8%, 17.19%, and 13.07%, respectively. In the future, we will focus on the robust localization method with the mobile beacon nodes in the mixed LOS/NLOS environments.



---

*Source: 5325174-2017-12-25.xml*