J Shanghai Univ (Engl Ed), 2011, 15(2): 128–131 Digital Object Identifier(DOI): 10.1007/s11741-011-0707-2
Real-time localization estimator of mobile node in wireless sensor networks based on extended Kalman filter TIAN Jin-peng (
),
Üú)
ZHENG Guo-xin (
Key Laboratory of Specialty Fiber Optics and Optical Access Networks, School of Communication and Information Engineering, Shanghai University, Shanghai 200072, P. R. China ©Shanghai University and Springer-Verlag Berlin Heidelberg 2011
Abstract Localization of the sensor nodes is a key supporting technology in wireless sensor networks (WSNs). In this paper, a real-time localization estimator of mobile node in WSNs based on extended Kalman filter (KF) is proposed. Mobile node movement model is analyzed and online sequential iterative method is used to compute location result. The detailed steps of mobile sensor node self-localization adopting extended Kalman filter (EKF) is designed. The simulation results show that the accuracy of the localization estimator scheme designed is better than those of maximum likelihood estimation (MLE) and traditional KF algorithm. Keywords wireless sensor networks (WSNs), node location, localization algorithm, Kalman filter (KF)
Introduction Determining the location of a mobile user is a fundamental problem in wireless sensor networks (WSNs)[1] . Irrespective of the scenario, the information collected within a WSN has significant added value when accurate timing and location data is included, and for some of these applications, this information is crucial. Several approaches to WSN localization in static conditions exist. Most of them are surveyed in [2] while a deep analysis of the localization algorithms theoretical accuracies can be found in [3]. Recently, the mobility has been addressed with several tracking systems, surveyed in [4], and typically based on prediction-correction algorithms like Kalman filters (KF)[5−8] . While these works consider the problem of mobility, the KF executes after location position computation, which usually leads to big error when asynchronous range measurements and low real-time performance. In this paper, we proposed a real-time localization estimator of mobile node in WSNs based on KF. In this approach, a mobile node computes its position when it receives a ranging signal such as received signal strength (RSS) or time of arrival (TOA). By employing an extended Kalman filter (EKF) algorithm, the mobile node can track its trajectory in real-time. Compared with the maximum likelihood estimation (MLE) and traditional
KF localization scheme, the proposed localization and tracking scheme achieve better location accuracy.
1 Overview of the KF algorithm The KF algorithm is introduced by Kalman in 1960. It describes a recursive solution to the discrete data linear filtering problem. The KF has many applications in technology, and it is an essential part of the development of space and military technology. The KF algorithm offers an elegant, efficient and optimal solution to localization problems when the system at hand is linear and random measurements errors follow a Gaussian distribution. Since these conditions are not always met, some linearization and approximation are needed to transform the KF into the EKF, suitable for non-linear systems[9] . The discrete EKF estimates recursively the state of a dynamic system modeled by discrete-time state equation: xk = f (xk−1 ) + wk , p(wk ) ∼ N (0, Qk ),
(1)
where x k is the state vector at time k, f the state transition function which evolves the state in time given the previous state x k−1 . The process noise vector w k takes into account the nonlinearities and perturbations on the system, modeled by a vector of random noise (not neces-
Received Oct.4, 2010; Revised Dec.16, 2010 Project supported by the Shanghai Leading Academic Discipcine Project (Grant No.S30108), the National Natural Science Foundation of China (Grant No.60872021), and the Science and Technology Commission of Shanghai Municipality (Grant No.08DZ2231100) Corresponding author ZHENG Guo-xin, Prof, E-mail: gxzheng@staff.shu.edu.cn
J Shanghai Univ (Engl Ed), 2011, 15(2): 128–131
129
sarily stationary) normally distributed with zero mean and covariance matrix Q k . This system is observed through the measurement equation: zk = h(xk ) + vk , p(vk ) ∼ N (0, Rk ),
(2)
where z k is the measurement vector at time k, h the observation function which estimates the expected measurements at the true state x k , and v k the observation noise vector assumed as a vector of random variables normally distributed with zero mean and covariance matrix Rk . Given both models, the EKF equations can be divided into two categories: time update equations and measurement update equations. The time update equations are used to obtain a priori state and error covariance estimates for the next time step according to the current estimates. The measurement update equations. are used to incorporate a new measurement into the a priori estimate to obtain an improved a posteriori estimate. (i) Time update equations The time update equations compute the a priori state ˆ− vector estimation (i.e., prediction) x k at time k on the ˆ k−1 : basis of the previous posteriori state estimate x ˆ k−1 ). ˆ− x k = f (x
(3)
The covariance matrix Pˆk− associated to the preˆ− dicted state vector x k is evaluated from the previous estimate Pˆk−1 and process noise covariance matrix Q k : Pˆk− = Ak Pk−1 AT k + Qk ,
(4)
ˆ where Ak = ∂f ∂x (xk−1 ) is the Jacobian matrix of the state transition function f computed around the previous estimates. (ii) Measurement update equations Measurement update equations are presented as follows: Kk = Pk− HkT (Hk Pk− HkT + Rk )−1 ,
(5)
−1 ˆ− ˆ− ˆk = x , x k + Kk (zk − h(x k ))
(6)
Pk = (I − Kk Hk )Pk− , ˆ− where Hk = ∂h k ) is ∂x (x
(7)
the Jacobian matrix of partial derivatives of observation function h with respect to x . The first task during the measurement update is to compute the Kalman gain K k . The next step is to actually measure the process to obtain z k , and then to generate an a posteriori state estimate by incorporating the measurement as in (6). The final step is to obtain an a posteriori error covariance estimate via (7).
2 Establishment of the system state equation and the measurement equation Usually, localization scheme for WSNs can be divided into centralized and decentralized way. In general, the centralized localization scheme for WSNs requires more communication cost than the decentralized way. Wireless transmission of one data bit would consume more energy than a single local computation. Therefore, it is worth developing decentralized localization schemes for WSNs in order to reduce energy consumption and improve bandwidth efficiency. The localization estimator scheme designed is self-localization in decentralized way. The EKF performance depends heavily on how well the system dynamics and measurements (including their statistical characterization) are modeled. This work focuses on the design of a low-complexity location tracking system in a low dynamics scenario. The system dynamics model suitable for this scenario can be written as xk = Φ k xk−1 + Gk wk ,
(8)
where xk = [pxk , pyk , vxk , vyk ]T is the state vector of mobile node composed by the position coordinates and the velocity components. p(wk ) ∼ N (0, Qk ) means the state noise or the random acceleration of the mobile node, which is normally distributed with zero mean and covariance matrix Q k . The state transition matrix Φk and the noise gain matrix Gk are written as ⎡ ⎤ 1 0 Tk 0 ⎢ ⎥ ⎢ 0 1 0 Tk ⎥ ⎢ ⎥, (9) Φk = ⎢ 0 ⎥ ⎣ 0 0 1 ⎦ 0 0 0 1 ⎡
Tk2 2 Tk
⎢ ⎢ ⎢ Gk = ⎢ ⎢ ⎢ 0 ⎣ 0
⎤ 0 ⎥ ⎥ 0 ⎥ ⎥, Tk2 ⎥ ⎥ 2 ⎦ Tk
(10)
where Tk is the adjacent time interval of ranging signal the mobile node received. In order to estimate mobile user’s location, we must obtain the estimation distance between the mobile user and anchor nodes, and put the estimation distance into localization algorithms to get the coordination of mobile user. The measurement equation can be written as dk = h(xk ) + vk = (apxk − pxk )2 + (apyk − pyk ) + vk ,
(11)
130
J Shanghai Univ (Engl Ed), 2011, 15(2): 128–131
where dk is the measurement distance between mobile user and anchor node. It can be obtained by using TOA or RSS technology. p(vk ) ∼ N (0, Rk ) is the observation noise, which is a random variable normally distributed with zero mean and covariance Rk .
3 Real-time localization estimator based on EKF Before discussing the localization schemes, we first outline the context in which these algorithms have to operate. There are two types of WSNs node in the localization area: the anchor nodes and the mobile nodes. The anchor nodes, which have precise coordination information of their own, broadcast the ranging signal to mobile nodes at fixed time interval. The mobile nodes randomly move across the environment. For simplicity and ease of presentation, we limit the environment to two dimensions, however all algorithms are capable of operating in three dimensions. The real-time localization estimator based on EKF can be divided into three phases: initial state estimation phase, time update phase and measurement update phase. (i) Initial state estimation phase When the mobile node receives ranging signal of three or more anchor nodes, it can compute its approximate initial coordination by using classical localization algorithm as MLE. The localization algorithm should execute two times to obtain the initial velocity. (ii) Time update phase Firstly, the adjacent time interval Tk is computed according to the received time of the ranging signal. Then the state transition matrix Φk via (9) and the noise gain matrix Gk via (10) can be determined. The priori estimate and the priori estimate error covariance of mobile node state update according to the following equation: ˆ k−1 , x ˆ− k = Φk x
(12)
Pˆk− = Φk Pk−1 ΦkT + Gk Qk GT k.
(13)
(iii) Measurement update phase In measurement update phase, the Kalman gain K k , the posteriori estimate and the posteriori estimate error covariance of mobile node state update according to (5)−(7). ˆ− Here Hk = ∂h k ) is the Jacobian matrix of par∂x (x tial derivatives of the measurement function (11) with respect to x. Therefore H k can be expressed as −
ˆ k − apxk pyˆk− − apyk px 0 0 . (14) Hk = zˆk zˆk Now an iterative computation of EKF is completed. The next iterative computation (consist of time update
phase and measurement update phase) begins when the next new ranging signal is received.
4 Simulation results We simulate the performance of the real-time localization estimator scheme base on EKF through a set of simulation and compare it with the MLE and traditional KF localization scheme. (i) Simulation parameters The simulation described in the subsequent sections share a standard scenario, in which certain parameters are varied: measurement noise variance, process noise variance and initial speed. The standard scenario consists of a network of 4 anchor nodes placed in a square with sides of 100 units. The initial state of mobile node is x0 = [0 50 0.5 0]. The state noise covariance is set as 0.1, and the measurement error covariance is set as 10. Unless specified otherwise, all data will be based on this standard scenario. We repeat each experiment 500 times and report the averaged results. In standard scenario, a typical location result that adopt real-time localization based on EKF, MLE and traditional KF localization scheme is shown in Fig.1. The MLE localization scheme, not considering mobility factor, has low location accuracy and its location track is not smoothing. The real-time EKF and traditional KF localization scheme, with low accuracy at the beginning, have obvious higher location accuracy after about 10 times iterative computation. However, the real-time EKF scheme has a better localization precision than traditional KF scheme because of its real-time character.
Fig.1
Typical location result of the three location schemes
(ii) Localization errors when changing simulation parameter. The location errors of the three localization estimator schemes under different process noise variance, measurement noise variance and initial velocity are shown in Figs.2−4. The process noise variance determines the uncertainty of node mobility. The measurement noise variance depends on the ranging precision in location
J Shanghai Univ (Engl Ed), 2011, 15(2): 128–131
measurement. The initial velocity of the mobile node determines the mean velocity of mobile node on the probability for the process noise is set as random variables normally distributed with zero mean. As is shown by the figures, the real-time EKF and traditional KF localization scheme have obvious higher location accuracy than MLE localization scheme. However, the location accuracy of the real-time EKF designed by us improves steadily about 1 unit compared with the traditional KF localization scheme.
131
employing EKF algorithm in real-time. The simulation results show that the proposed localization and tracking scheme achieves better location accuracy compare with the MLE and traditional KF localization scheme.
References [1] Akyildiz I F, Sankarasubramaniam Y, Cayirci E. Wireless sensor networks: A survey [J]. Computer Networks, 2002, 38(4): 393–422. [2] Hightower J, Borriello G. Location systems for ubiquitous computing [J]. IEEE Computer, 2001, 34(8): 57–66. [3] Patwari N, Ash J, Kyperountas S, Hero A O I, Moses R L, Correal N S. Locating the nodes: Cooperative localization in wireless sensor networks [J]. Signal Processing Magazine, 2005, 22(4): 54–69.
Fig.2
Location error under different process noise variance
[4] Hu B, Li H S, Liu S M. Research on localization algorithm of mobile nodes in wireless sensor networks [C]// Proceedings of Computational Intelligence and Software Engineering, Wuhan, China. 2009: 1–4. [5] Smith A, Balakrishnan H, Goraczko M, Priyantha N. Tracking moving devices with the cricket location system [C]// Proceedings of the 2nd International Conference on Mobile Systems, Applications and Services, Boston, USA. 2004: 190–202.
Fig.3
Location error under different measurement noise variance
[6] Caceres M A, Sottile F, Spirito M A. Adaptive location tracking by Kalman filter in wireless sensor networks [C]// Proceedings of the 5th IEEE International Conference on Wireless and Mobile Computing, Networking and Communications, Marrakech, Morocco. 2009: 123–128. [7] Echu E J, Roumeliotis S I, Ribeiro A, Giannakis G B. Distributed iteratively quantilzed Kalman filtering for wireless sensor networks [C]// Proceedings of the 41st Asilomar Conference on Signals, Systems and Computers, California, USA. 2007: 646–650.
Fig.4
Location error under different initial velocity
5 Conclusions In this paper we have described real-time localization estimator of mobile node in WSNs based on EKF. In this scheme, the mobile node can track its trajectory by
[8] Wang L J, Wang J K, Wang Y. Location estimation of mobile user in wireless sensor network based on unscented Kalman filter [C]// Proceedings of Microwave and Millimeter Wave Technology, Nanjing, China. 2008: 96–99. [9] Gasparri A, Pascucci F. An interlaced extended information filter for self-localization in sensor networks [J]. Mobile Computing, 2010, 9(10): 1491–1504. (Editor HONG Ou)
