The wireless sensor network (WSN) has received increasing attention since it has many potential applications such as the internet of things and smart city. The localization technology is critical for the application of the WSN. The obstacles induce the larger non-line of sight (NLOS) error and it may decrease the localization accuracy. In this paper, we mainly investigate the non-line of sight localization problem for WSN. Firstly, the Pearson's chi-squared testing is employed to identify the propagation condition. Secondly, the particle swarm optimization based localization method is proposed to estimate the position of unknown node. Finally the simulation experiments are implemented. The simulation results show that the proposed method owns higher localization accuracy when compared with other two methods.
Open Peer Review Details | |||
---|---|---|---|
Manuscript submitted on 02-02-2016 |
Original Manuscript | A Non-Parametric Propagation Condition Identification Method and Non-Line of Sight Mitigation Algorithm for Wireless Sensor Network |
Wireless sensor network (WSN) is an emerging technology in recent years and it becomes the key technology for the internet of things (IoT) [1Z. Chen, F. Xia, T. Huang, F. Bu, and H. Wang, "A localization method for the Internet of Things", J. Supercomput., vol. 63, no. 3, pp. 657-674, 2013.
[http://dx.doi.org/10.1007/s11227-011-0693-2] ]. WSN which integrates the sensor technology, modern communication and wireless communication technology is an intelligent information processing platform. It has a wide application prospects and the development of it will have profound influence to human life and production of various fields. The localization technology is one of the most important applications for the WSN [2G. Han, H. Xu, and T.Q. Duong, "Localization algorithms of wireless sensor networks: A survey", Telecomm. Syst., vol. 52, pp. 2419-2436, 2013.
[http://dx.doi.org/10.1007/s11235-011-9564-7] ]. The sensor node should know the position of itself in the network initialization phase. According to the measurement modes, the localization methods can be categorized as received signal strength (RSS) [3A. Moragrega, P. Closas, and C. Ibars, "Potential game for energy-efficient rss-based positioning in wireless sensor networks", IEEE J. Sel. Areas Comm., vol. 33, no. 7, pp. 1394-1406, 2015.
[http://dx.doi.org/10.1109/JSAC.2015.2430172] ], time of arrival (TOA) [4K. Yu, Y.J. Guo, and M. Hedley, "TOA-based distributed localisation with unknown internal delays and clock frequency offsets in wireless sensor networks", IET Signal Process., vol. 3, no. 2, pp. 106-118, 2009.
[http://dx.doi.org/10.1049/iet-spr:20080029] ], time of difference of arrival (TDOA) [5W. Meng, L. Xie, and W. Xiao, "Decentralized tdoa sensor pairing in multihop wireless sensor networks", IEEE Signal Process. Lett., vol. 20, no. 2, pp. 181-184, 2013.
[http://dx.doi.org/10.1109/LSP.2013.2237823] ] and angle of arrival (AOA) [6H. Shao, X. Zhang, and Z. Wang, "Efficient closed-form algorithms for aoa based self-localization of sensor nodes using auxiliary variables", IEEE Trans. Signal Process., vol. 62, no. 10, pp. 2580-2594, 2014.
[http://dx.doi.org/10.1109/TSP.2014.2314064] ] localization methods. The RSS localization methods do not need more hardware support, so it is a lower cost solution. But the RSS is easily affected by environment and the localization accuracy is low. TDOA and AOA localization methods need additional hardware such as antenna array or ultrasonic transducer, therefore, they are suit for the small-scale localization scene. In this paper, we investigate the TOA localization method.
The contributions of this paper as follows:
The reminder of this paper is organized as follows: in section 2, we describe the related works in NLOS localization. The system setting and measurement model are expressed in section 3. In section 4, the proposed methods are presented. The simulation results are presented in section 5. Section 6 concludes this paper.
The accuracy localization results can be achieved in the free space. However, the propagation condition between the nodes is non-line of sight (NLOS) in most localization scenes such as indoor and subway environment [7F. Zhang, L. Huang, and S. Yuan, "A novel strategy of localization based on EKF for mobile robot", In: 33rd Chinese Control Conference (CCC), IEEE, 2014, pp. 333-338.
[http://dx.doi.org/10.1109/ChiCC.2014.6896644] ]. The localization accuracy degrades dramatically in NLOS environment. The NLOS localization has received much attention of researchers. According to whether the parameters of the NLOS error is known, the NLOS localization methods can be divided into two categories: parametric based and non-parametric localization methods [8L. Cheng, C. Wu, Y. Zhang, and H. Wu, "A survey of localization in wireless sensor network", Int. J. Distrib. Sens. Netw., vol. 2012, pp. 1-12, 2012.
[http://dx.doi.org/10.1155/2012/962523] ]. The advantage of the parametric based localization methods is that it can achieve higher localization accuracy. However, it need to know the parameters and distribution of the NLOS error, it is unrealistic in most conditions. For the dynamic environment, the parameters of NLOS error are changing over time. Therefore, the non-parametric localization methods own more flexible.
There are many parametric NLOS localization methods are proposed in recent years. The NLOS identification in MIMO-OFDM based sensor network is proposed [9W. Xu, and S.A. Zekavat, "A high-performance measure for non-line-of-sight identification in mimo-ofdm-based sensor networks", IEEE Systems J., vol. 8, no. 1, pp. 125-130, 2014.
[http://dx.doi.org/10.1109/JSYST.2013.2260627] ]. In this method, the mean value and standard deviation of space-frequency correlation over multiple transmit and receive antenna combinations are used to identify the propagation condition. A low complexity algorithm for estimating the channel condition is proposed [10N. Alsindi, C. Duan, and J. Zhang, "NLOS channel identification and mitigation in mltra wideband ToA-based wireless sensor networks", In: Proceeding in 6th Workshop on Positioning Navigation and Communication, IEEE: Hannover, 2009, pp. 59-66.
[http://dx.doi.org/10.1109/WPNC.2009.4907804] ]. This method uses a priori statistical channel model information to compute the probability of each of each channel condition. And then a soft and hard weight assignment schemes is integrated into the localization algorithm. The sequential probability ratio test is used to identify whether the measurement contains the non-line of sight (NLOS) errors [11L. Cheng, C. Wu, Y. Zhang, and Y. Wang, "An indoor localization strategy for mini-uav in presence of obstacles", Int. J. Adv. Robot. Syst., vol. 9, pp. 1-8, 2012.]. And a particle swarm optimization based maximum joint probability localization algorithm is proposed to mitigate the NLOS error.
The non-parametric NLOS localization methods have received many attentions. A low complexity localization algorithm based on NLOS node identification using minimum subset is proposed for the NLOS environment [12T. Fujita, and T. Ohtsuki, "Low complexity localization algorithm based on NLOS node identification using minimum subset for NLOS environments", In: Proceeding in IEEE Global Telecommunications Conference, IEEE: New Orleans, LO, 2008, pp. 1-5.
[http://dx.doi.org/10.1109/GLOCOM.2008.ECP.1029] ]. This method could reduce the amount of calculation and need less number of LOS measurements. A support vector machine (SVM) classifier is used to distinguish between LOS and NLOS conditions. And the development of SVM regressor based techniques is proposed to mitigate the ranging bias in NLOS situations [13S. Marano, W.M. Gifford, H. Wymeersch, and M.Z. Win, "NLOS identification and mitigation for localization based on uwb experimental data", IEEE J. Sel. Areas Comm., vol. 28, no. 7, pp. 1026-1035, 2010.
[http://dx.doi.org/10.1109/JSAC.2010.100907] ]. The Edgeworth expansion method is proposed to reconstruct the statistics of the measurement noise and estimates the accurate error bounds [14O. Oshiga, S. Severi, and G. Abreu, "Non-parametric estimation of error bounds in LOS and NLOS environments", In: 10th Workshop on Positioning Navigation and Communication, IEEE: Dresden, 2013, pp. 1-6.
[http://dx.doi.org/10.1109/WPNC.2013.6533286] ]. This method could improve the localization accuracy and does not need to estimate a priori the statistic of the channel.
N beacon nodes and one unknown node are randomly deployed in the field. The position of ith beacon node denotes as Xi [xi, yi]. The position of the unknown node is U [x, y]. The beacon nodes emit the signal to the unknown node. The unknown node receives the signal and converts it into the distance. The true distance between the ith beacon node and the unknown node is:
In LOS condition, the measurement distance between the ith beacon node and the unknown node is [15D. Sun, H. Zhang, and Z. Qian, "A non-line-of-sight mitigation localization algorithm for sensor networks using clustering analysis", Comput. Electr. Eng., vol. 40, no. 2, pp. 433-442, 2014.
[http://dx.doi.org/10.1016/j.compeleceng.2013.11.027] ]:
where, ni is the measurement noise which is modeled as the zero mean with σi standard deviation Gaussian distribution, i.e.
In NLOS condition, the measurement distance between the ith beacon node and the unknown node is:
where, nLOS is the NLOS error, it obeys different distributions in different environments [16I. Rasool, and A.H. Kemp, "Statistical analysis of wireless sensor network Gaussian range estimation errors", IET Wireless Sensor Syst., vol. 3, no. 1, pp. 57-68, 2013.
[http://dx.doi.org/10.1049/iet-wss.2012.0073] , 17Y. Wang, L. Cheng, and N. Hu, "Bayes sequential test based NLOS localization method for wireless sensor network", In: 2015 27th Chinese Control and Decision Conference (CCDC), 2015, pp. 5230-5234.
[http://dx.doi.org/10.1109/CCDC.2015.7162857] ]. It may obey Uniform distribution
, Exponential distribution
or other distributions.
In this section, we introduce the proposed method in details. The proposed method consists of two steps: propagation condition identification and NLOS mitigation. We employ the Pearson's chi-squared testing method to detect the propagation condition. And the LOS measurements are used to establish the localization objective function and the NLOS measurements are introduced as the constraints. Finally, we employ the particle swarm optimization method to estimate the position of unknown node.
According to Eq.(2), the measurements obey Gaussian distribution in LOS condition. However, the measurements do not obey the Gaussian distribution in NLOS condition. We assume that the unknown node could obtain M measurements for ith beacon node, the measurement set can be expressed as . We firstly assume that the measurements obey the Gaussian distribution. Then we firstly estimate the mean and standard deviation of the measurements as follows:
The measurements set are divided among r different cells, i.e. R1, R2, …, Rr. the ith cell is defined as . And then compute the number of the measurements occurs in each cell Oi. Oi is termed as the number of measurements of type ith. The observed frequency for type ith is defined as:
A simple application is to test the hypothesis that, in the general population, values would occur in each cell with equal frequency. Therefore, we estimate the theoretical frequency of type ith according to the estimated parameters in Eq.(4) and Eq.(5) as follows
where, .
The value of the test-statistic is:
According to the central limit theorem, X2 is approximate, Xα2 (r-1), α is the significance level. For a given significance level, the refused domain is defined as:
So the propagation condition is LOS if , otherwise the propagation condition is NLOS.
When the propagation condition is identified, we proposed a NLOS error mitigation method to improve the localization accuracy. We employ the Fig. (1) to show the principle of the proposed localization method. As shown in Fig. (1), there are three beacon nodes in the field. The propagation condition between BN1 and unknown node is LOS. The propagation condition of other two beacon nodes is NLOS. Since the LOS measurement contains small error and the NLOS measurement contains larger positive error, the position of unknown node surrounds the circle with BN1 as the center. And position of unknown node is in the circles with BN2 and BN3 as the centers.
We assume that at least one LOS measurement can be obtained. The LOS measurement set denotes as . The NLOS measurement set denotes as . We establish the localization objective function as follows:
Fig. (1) The illustrate of the NLOS localization. |
In order to estimate the optimal solution for the objective function, we propose to employ the particle swarm optimization (PSO) method to solve it. In past several years, PSO has been successfully applied in many research and application areas [18C.C. Chen, "Two-layer particle swarm optimization for unconstrained optimization problems", Appl. Soft Comput., vol. 11, no. 1, pp. 295-304, 2011.
[http://dx.doi.org/10.1016/j.asoc.2009.11.020] ]. The PSO method is a population-based stochastic approach for solving continuous and discrete optimization problems. In PSO, the particles move in the search space of an optimization problem. The position of a particle represents a candidate solution to the optimization problem. Each particle searches for better positions in the search space by updating its velocity and position according to rules.
The position of the particle is denoted as S={P1,…PL}, L is the number of particles. The updated equations of velocity and position for the ith particle at kth step are:
where, vi(k) is the velocity of particle i at step k. pi(K). is the position of the ith particle, pbest represents the best location in the search space ever visited by the ith particle, gbest is the best location discovered so far. c1 and c2 are two acceleration constants, where c1=c2 = 2. ξ and η are two uniform random numbers in [0,1]. The maximum number of iterations is 50.
The steps of PSO based localization as follows:
The gbest is the estimated position of the unknown node.
In this section, we evaluate the performance of the proposed method. Let us consider a scenario consisting of N beacon node placed in the 50m × 50m square. The parameters of the measurement model are shown in Table 1. In this section, the NLOS error is assumed that obeys the Uniform distribution ( ) or Exponential distribution ( ). We mainly evaluate two aspects of the proposed method: the identification success rate and the localization accuracy. We compare the proposed method with maximum likelihood (ML) method and residual weighting algorithm (Rwgh) method. The simulation results are obtained by 1000 Monte Carlo runs. The average localization error is considered to evaluate the localization accuracy. It is defined by:
Where, Ui is the true position of unknown node for ith trial. is the estimated position of the unknown node.
Figs. (2 and 3) show the performance of identification success rate when the NLOS error obeys the Uniform distribution () or Exponential distribution () respectively. Fig. (2) shows the relationship between the parameter b and the identification success rate under different standard deviations of measurement noise. It can be observed that the success rate increases with the value of parameter b increases. It is because the larger value of parameter b, the non-Gaussian characteristic of measurement more obvious. And the standard deviation of measurement noise has the negative impact of the success rate. The larger standard deviation will induce larger interference. On the whole, the proposed method could achieve higher success rate.
Fig. (2) The parameter b versus identification success rate. |
Fig. (3) The parameter λ versus identification success rate. |
Fig. (3) shows the impact of the parameter λ on the identification success rate. The success rate decreases with the value of parameter λ increases. And the standard deviation of measurement noise has less negative impact on the success rate compared with Fig. (2). The larger standard deviation of measurement noise results in better performance of success rate. The success rate is greater than 93% in most situations.
Fig. (4) shows the relationship between the number of beacon nodes and the average localization error when NLOS error obeys Uniform distribution U (0,7) and U (0,11). It can be observed that the ML method has the worst localization accuracy. And the proposed method owns the best performance. When the NLOS error obey U (0,11), average localization accuracy is 6m, 2.45m and 0.67m for the ML method, Rwgh and the proposed method respectively. The localization errors of the three method increase with the value of parameter b increases. This is because the larger value of parameter b, the more NLOS error interference.
Fig. (4) The number of beacon nodes versus average localization error. |
Fig. (5) illustrates the impact of the standard deviation of measurement noise on the average localization error when the NLOS error obey the Exponential distribution E(5) and E(9). The localization error of ML method increases with the standard deviation increases. The localization errors of the Rwgh and the proposed method remain relatively stable. Therefore, the Rwgh and the proposed methods are robust to the NLOS error obeys the Exponential distribution. The performance of the proposed method improves 85.89% and 64.62% when compared with ML and Rwgh method.
Fig. (5) The standard deviation of measurement noise versus average localization error. |
In this paper, the NLOS localization problem for wireless sensor network is investigated. The proposed method consists of two main steps: the non-parametric propagation condition identification method and PSO based NLOS error mitigation method. The Pearson's chi-squared testing method is used to detect the propagation condition. The advantage of this method is that it does not need the prior knowledge of the NLOS error. The LOS measurements are used to establish the localization objective function and the NLOS measurements are employed as the restrictions. The PSO method is used to estimate the position of the unknown node. The simulation results show the proposed method outperforms the other method.
The authors confirm that this article content has no conflict of interest.
This work was supported in part by the National Nature Science Foundation of China (No. 61273078 and 61203216), Fundamental Research Funds for the Central Universities of China (No. N130323002 and N130323004).
[1] | Z. Chen, F. Xia, T. Huang, F. Bu, and H. Wang, "A localization method for the Internet of Things", J. Supercomput., vol. 63, no. 3, pp. 657-674, 2013. [http://dx.doi.org/10.1007/s11227-011-0693-2] |
[2] | G. Han, H. Xu, and T.Q. Duong, "Localization algorithms of wireless sensor networks: A survey", Telecomm. Syst., vol. 52, pp. 2419-2436, 2013. [http://dx.doi.org/10.1007/s11235-011-9564-7] |
[3] | A. Moragrega, P. Closas, and C. Ibars, "Potential game for energy-efficient rss-based positioning in wireless sensor networks", IEEE J. Sel. Areas Comm., vol. 33, no. 7, pp. 1394-1406, 2015. [http://dx.doi.org/10.1109/JSAC.2015.2430172] |
[4] | K. Yu, Y.J. Guo, and M. Hedley, "TOA-based distributed localisation with unknown internal delays and clock frequency offsets in wireless sensor networks", IET Signal Process., vol. 3, no. 2, pp. 106-118, 2009. [http://dx.doi.org/10.1049/iet-spr:20080029] |
[5] | W. Meng, L. Xie, and W. Xiao, "Decentralized tdoa sensor pairing in multihop wireless sensor networks", IEEE Signal Process. Lett., vol. 20, no. 2, pp. 181-184, 2013. [http://dx.doi.org/10.1109/LSP.2013.2237823] |
[6] | H. Shao, X. Zhang, and Z. Wang, "Efficient closed-form algorithms for aoa based self-localization of sensor nodes using auxiliary variables", IEEE Trans. Signal Process., vol. 62, no. 10, pp. 2580-2594, 2014. [http://dx.doi.org/10.1109/TSP.2014.2314064] |
[7] | F. Zhang, L. Huang, and S. Yuan, "A novel strategy of localization based on EKF for mobile robot", In: 33rd Chinese Control Conference (CCC), IEEE, 2014, pp. 333-338. [http://dx.doi.org/10.1109/ChiCC.2014.6896644] |
[8] | L. Cheng, C. Wu, Y. Zhang, and H. Wu, "A survey of localization in wireless sensor network", Int. J. Distrib. Sens. Netw., vol. 2012, pp. 1-12, 2012. [http://dx.doi.org/10.1155/2012/962523] |
[9] | W. Xu, and S.A. Zekavat, "A high-performance measure for non-line-of-sight identification in mimo-ofdm-based sensor networks", IEEE Systems J., vol. 8, no. 1, pp. 125-130, 2014. [http://dx.doi.org/10.1109/JSYST.2013.2260627] |
[10] | N. Alsindi, C. Duan, and J. Zhang, "NLOS channel identification and mitigation in mltra wideband ToA-based wireless sensor networks", In: Proceeding in 6th Workshop on Positioning Navigation and Communication, IEEE: Hannover, 2009, pp. 59-66. [http://dx.doi.org/10.1109/WPNC.2009.4907804] |
[11] | L. Cheng, C. Wu, Y. Zhang, and Y. Wang, "An indoor localization strategy for mini-uav in presence of obstacles", Int. J. Adv. Robot. Syst., vol. 9, pp. 1-8, 2012. |
[12] | T. Fujita, and T. Ohtsuki, "Low complexity localization algorithm based on NLOS node identification using minimum subset for NLOS environments", In: Proceeding in IEEE Global Telecommunications Conference, IEEE: New Orleans, LO, 2008, pp. 1-5. [http://dx.doi.org/10.1109/GLOCOM.2008.ECP.1029] |
[13] | S. Marano, W.M. Gifford, H. Wymeersch, and M.Z. Win, "NLOS identification and mitigation for localization based on uwb experimental data", IEEE J. Sel. Areas Comm., vol. 28, no. 7, pp. 1026-1035, 2010. [http://dx.doi.org/10.1109/JSAC.2010.100907] |
[14] | O. Oshiga, S. Severi, and G. Abreu, "Non-parametric estimation of error bounds in LOS and NLOS environments", In: 10th Workshop on Positioning Navigation and Communication, IEEE: Dresden, 2013, pp. 1-6. [http://dx.doi.org/10.1109/WPNC.2013.6533286] |
[15] | D. Sun, H. Zhang, and Z. Qian, "A non-line-of-sight mitigation localization algorithm for sensor networks using clustering analysis", Comput. Electr. Eng., vol. 40, no. 2, pp. 433-442, 2014. [http://dx.doi.org/10.1016/j.compeleceng.2013.11.027] |
[16] | I. Rasool, and A.H. Kemp, "Statistical analysis of wireless sensor network Gaussian range estimation errors", IET Wireless Sensor Syst., vol. 3, no. 1, pp. 57-68, 2013. [http://dx.doi.org/10.1049/iet-wss.2012.0073] |
[17] | Y. Wang, L. Cheng, and N. Hu, "Bayes sequential test based NLOS localization method for wireless sensor network", In: 2015 27th Chinese Control and Decision Conference (CCDC), 2015, pp. 5230-5234. [http://dx.doi.org/10.1109/CCDC.2015.7162857] |
[18] | C.C. Chen, "Two-layer particle swarm optimization for unconstrained optimization problems", Appl. Soft Comput., vol. 11, no. 1, pp. 295-304, 2011. [http://dx.doi.org/10.1016/j.asoc.2009.11.020] |