Wireless Netw DOI 10.1007/s11276-013-0573-1

Decentralized target positioning and tracking based on a weighted extended Kalman filter for wireless sensor networks Chin-Liang Wang • Dong-Shing Wu

 Springer Science+Business Media New York 2013

Abstract This paper presents a decentralized positioning and tracking method based on recursive weighted leastsquares optimization for wireless sensor networks. The proposed algorithm—weighted extended Kalman filter—is derived by minimizing a recursive-in-time objective function and then applying it in an iterative decentralized manner. The target location is calculated iteratively by taking a weighted average of the local estimates based on the participating sensor nodes’ reliability, where a participating sensor node computes the newest location estimate according to its own observation and the most recent local estimate passed from the previous participating sensor node. A convergence analysis is given to show the convergence behavior of the proposed algorithm. To track the target in the network, a message-passing algorithm is proposed for adaptively selecting the participating sensor nodes as the target moves around the area. During each iteration, the current participating sensor node computes the local estimate and passes it on to the next participating sensor node for further processing. The update process is circulated only among the selected participating sensor nodes that surround the target. Computer simulation results show that our proposed algorithm outperforms previous related methods.

C.-L. Wang Department of Electrical Engineering, National Tsing Hua University, Hsinchu 30013, Taiwan, ROC e-mail: [email protected] URL: http://www.ee.nthu.edu.tw/clwang/ C.-L. Wang  D.-S. Wu (&) Institute of Communications Engineering, National Tsing Hua University, Hsinchu 30013, Taiwan, ROC e-mail: [email protected]

Keywords Decentralized methods  Extended Kalman filters  Least-squares optimization  Positioning  Tracking  Wireless sensor networks

1 Introduction 1.1 Positioning techniques Wireless sensor networks (WSN) typically consist of a large number of tiny devices that collect measurements of the desired information from the physical environment [1–3]. When compared with traditional sensor networks, WSNs are easy to deploy, programmable, and dynamically reconfigurable [4–7]. Because of these advanced features, WSNs have many location-aware applications in the industrial, household, and community safety areas, battlefield reconnaissance, hazards mitigation, environmental tracking, and others [6, 8, 9]. Many existing indoor positioning schemes in [10, 11] use a centralized approach, in which the measurements from all sensor nodes are collected and jointly processed at a central processor (CP). At the beginning of these protocols, the target broadcasts a signal to all sensor nodes, informing them of its presence. The sensor nodes obtain the local measurements from the target’s signal, and this information then is transmitted over multiple hops to the CP, where an optimal location estimate is computed. An accurate estimate can be obtained using this optimal processing technique, but the amount of energy consumed in transmitting the measurements to the CP can be prohibitive in sensor networks. A decentralized approach is viable alternative when developing a positioning system in large-scale and/or dense WSNs because the computation of the location estimate is performed by each sensor node rather than by the CP. This is an advantage because the

123

Wireless Netw

wireless transmission of one data bit in the centralized scheme described above consumes more energy than a single local computation within the sensor nodes [1, 12]. A comparison of the energy efficiencies of the centralized and decentralized approaches is described in the literature (see [13] and references therein); the decentralized approach uses less energy than the centralized approach as the number of sensor nodes in the network increases. Several decentralized positioning methods have been presented in [14–17], where the location estimation is formulated as a nonlinear least-squares (NLS) problem [14, 15] or as a convex feasibility (CF) problem [16, 17] according to the received signal strength (RSS) measurements, and the problems are solved in the local sensor nodes in an iterative manner. As compared to the time of arrival, the time difference of arrival, and the angle of arrival schemes, the RSS scheme does not require extra hardware and software for ranging, which makes sensor node positioning cost-inexpensive. Rabbat and Nowak [14] proposed an incremental subgradient (IG) method with a fixed step size [18] to solve the NLS problem in the decentralized approach, which achieves better energy efficiency as the size of the network increases. In [16, 17], an alternate incremental method, called the projection-onto-convex-sets (POCS) method is applied to solve the CF problem, which converges to the optimal solution when a specific sequence of relaxation parameters is used. A better method was proposed in [15], where the authors presented an adaptive weighted interpolation (WIP) scheme based on the POCS method. Because the WIP scheme considers the reliability of the different sensor nodes in the positioning process, it has better performance than the POCS method. It also was shown in [19] that conventional Kalman filtering (CKF) can be used in the centralized manner to further improve the location accuracy of the POCS and WIP methods. However, in practice, the KF methods can be implemented in a decentralized fashion by using the incremental procedure. In [20, 21], Bertsekas proposed an iterated extended Kalman filter (IEKF) for the NLS problem, where each update process consists of repeated cycles through the local observations. Characteristically, this modified EKF is incremental, and is equivalent to the IG method with a diminishing step size for each iteration. The IEKF typically has a fast convergence rate when compared with the fixed step size IG method and its step sizes are chosen adaptively based on the sensor nodes’ observations; this is more appropriate for use in decentralized target positioning. One drawback of the methods in [14, 16–18, 20, 21] is that they do not take into account the reliability information from the different sensor nodes, rather giving equal weight to all sensor nodes even if they have high measurement noise, which can degrade performance. In [15], a weighting scheme was proposed for the case of two sensor nodes to

123

overcome this weakness, but this would not be optimal for a network of multiple sensor nodes. In addition, the abovementioned methods rely on the computation of the set of sensor nodes whose positions are fixed during the process. Thus, these methods are not adaptive to changes in network topology or to movements of the target. In this paper, we propose a weighted extended Kalman filter (WEKF) algorithm based on recursive weighted leastsquares optimization for WSNs, where a recursive-in-time objective function is defined and then an iterative procedure is used to approach the optimal solution. During each iteration, a current participating sensor node computes a new local estimate by taking the weighted average of its own observation and the previous local estimate passed on by a neighbor participating sensor node responsible for the previous iteration, and then the current participating sensor node broadcasts its local estimate for the next iteration. The average is attained iteratively, with each iteration being executed by a different participating sensor node in the network. We present a convergence analysis of the WEKF algorithm to prove that the iterative procedure converges. We further propose a message-passing (MP) algorithm to adaptively select a subset of sensor nodes (i.e., the participating sensor nodes) that are located in the vicinity of the target. The participating sensor nodes are picked adaptively depending on the reliability of their RSS measurements of the target’s signal; thus, the update process is cycled among a subset of sensor nodes that encircle the target. The WEKF algorithm can be regarded as an improved version of the IG method or the IEKF method, where the reliability information of the current participating sensor node and all previous participating sensor nodes is considered in updating the variable step size for each iteration. Given that the WEKF algorithm uses more reliability information, it achieves better location accuracy than the IG and IEKF methods. Computer simulation results are given to demonstrate that the proposed algorithm not only can converge to a limit solution near the target location, but also that it has better location accuracy, a faster convergence rate, and better tracking performance than previous related methods. 1.2 Related works and motivation In recent years, fingerprint-based (FB) techniques have been developed due to the poor coverage of the Global Positioning System (GPS) in indoor environments [22–24]. The FB methods consist of two stages: offline training stage and online positioning stage. During the offline training stage, the CP receives the RSS measurements from the sensor nodes at predefined locations and constructs a radio map of the physical region based on these measurements. In the online positioning stage, the CP uses the current RSS measurements received from the target and the radio map to

Wireless Netw

estimate the target’s location. Generally, the main limitations of the FB methods are: (1.1) the measurement collection process is time consuming, and the radio map is static and can be easily outdated due to environmental dynamics; (1.2) some physical locations may be difficult to identify if their RSS fingerprints are closer together; (1.3) the number of the recorded RSS measurements in the CP increases as the computational complexity of the FB scheme increases; and (1.4) the FB methods without a positioning and tracking method may fall into ambiguous states in a moving target’s location estimation. To overcome these limitations, a realtime localization method that is highly robust, such as the CKF, the EKF, and the particle filter (PF) [25–27], can be used in the tracking community for indoor scenarios. Theoretically, these methods can derive better location estimates by using the sensor nodes’ measurements combined with the stochastic model of the target motion in a centralized way, as compared with the FB methods. These dynamic tracking pairs are both probabilistic models, and especially suited to the stochastic RSS map-based positioning. However, for large-scale and dense WSN deployment, there are three major disadvantages to practical implementation of the CKF, EKF, and PF methods: (2.1) the state of the target’s motion (horizontal and vertical directions and speeds), the state transition, the process noise covariance, the estimation error covariance, and the measurement noise covariance matrices must be computed in the prediction and update phases; thus, the computational complexity of these methods increases significantly with the number of sensor nodes (i.e., the more sensor nodes, the higher the computational complexity of these methods); (2.2) transmitting a large number of raw measurements from the sensor nodes to the CP may place a significant drain on communication and energy resources; and (2.3) the large delay in communicating the measurements to the CP makes it even more difficult to track a moving target in real time. As a result, the decentralized positioning approach is worth developing for in-network data processing, aimed at avoiding the complex statistical operations of (2.1) and reducing the amount of energy resources used for communication of (2.2). A robust decentralized method called the IEKF already has been proposed in [20, 21], and this incremental optimization method is designed based on the concept of EKF. The main difference between the IEKF and the EKF is that, in the IEKF iteration, each sensor node makes a small subgradient descent-like adjustment (i.e., a modified Kalman gain (as a diminishing step size discussed in [18]) multiplied by a gradient operation) to a previous location estimate from a neighboring sensor node based only on its RSS measurement, and the update process is circulated among the sensor nodes. The properties of the modified Kalman gains and the gradient operations can be found in [20, 21]. During the EKF iteration, the observations of all sensor nodes are passed over

multiple hops to the CP to perform the update procedure. However, in practice, although the IEKF method eliminates the complicated statistical operations, the method is nonadaptive in the presence of measurement noise because: (3.1) the IEKF method does not take into consideration the RSS measurement reliability of the different sensor nodes, thereby giving equal weight to sensor nodes with high measurement noise (i.e., the equal weight assignment scheme for a network of multiple sensor nodes is not an optimal) and, thus, the performance of the IEKF may be degraded; (3.2) the IEKF has a slow convergence rate, not only because it is an equal weighting method, but also because it needs a suitable Kalman gain for convergence; and (3.3) the IEKF does not have an effective tracking algorithm and must rely on the calculation of a fixed set of sensor nodes in the network, thus, this method is not adaptive to varying network topology or to movements of the target. To overcome the disadvantages of the IEKF, we propose the WEKF and the MP algorithms, called the WEKF-based method for real-time tracking, as presented in Sect. 1.1. Specifically, the WEKF-based method takes only a dynamic set of sensor nodes in the network to obtain the estimate of the target’s location, where the dynamic set of sensor nodes is selected adaptively depending on the reliability of its RSS measurements on the target’s signal and the WEKF algorithm by which the weighting factor and the modified Kalman gain as the variable step size in [18] is dynamically chosen to minimize the mean squared error at each iteration. Consequently, we provide a complete explanation of the motivation for the proposed approach in this section. Another motivation for our work is that the tracking problems usually are solved by using the Bayesian methods in [25–28], but realistic implementation of these robust methods is difficult in a decentralized process because it is not possible to obtain good estimates of the state of the target’s motion, the state transition, the process noise covariance, the estimation error covariance, and the measurement noise covariance matrices at each sensor node based only on an RSS measurement and a previous location estimate. In addition, because the sensor nodes have limited in power, computational capacity, and memory [1, 12], the large amounts of energy consumed in computing the complicated statistical estimates and the optimal location solution only at a sensor node may be prohibitive in large-scale and/or dense WSNs. Therefore, we attempt to develop a decentralized positioning and tracking method with a robust property that goes against the mainstream approach to avoid these problems in time-variant environments. In indoor scenarios, the use of RSS measurements has been validated in combination with fingerprinting (empirical) in [22–24]. Nevertheless, the RSS measurements could be affected by scattering and reflection propagated in indoor surroundings; thus, the FB techniques may result in

123

Wireless Netw

inaccurate location estimation when the variation of RSS measurements or when the measurement noise is very large. To solve the problems associated with changes in indoor environments, an alternative RSS-based positioning method is worth investigating. According to the notion of path loss measurements in [29–31], an empirical statistical model (called the log-distance path loss model) often is useful to understand the propagation of radio waves in indoor areas; these empirical studies have shown that this widely used model works well in buildings [32–34]. When the target sends a signal with power (P) to a sensor node, an RSS measurement of sensor node (R) is related to a path loss measurement (PL) by the relationship PL = P - R. With this relationship, the positioning problem can be equivalently considered by the path loss measurements instead of the RSS measurements. The details of the logdistance path loss model are described in Sect. 2. From a theoretical standpoint, the proposed method is derived by minimizing the recursive-in-time objective function formulated by the log-distance path loss model and then realized in an iterative decentralized manner. Accordingly, our work is for indoor scenarios. It is interesting to note that RSS measurements also are valid for use in outdoor environments in [29–31], so our approach can be used to address outdoor positioning and tracking problems in the following scenario. We consider that the target is a small device (e.g., a wireless sensor node) that has low transmission power and is capable of communicating only over a short distance, which makes it difficult to use GPS satellites without special assistive devices (e.g., ground-based GPS servers) to measure the target’s signal and to perform the RSS-based positioning. 2 Problem formulation Consider a sensor network composed of N sensor nodes uniformly distributed in a two-dimensional space, where the ith sensor node is at a known location pi 2 <2 , i = 1, 2, …, N. Assume that a target at location h 2 <2 broadcasts a signal with power P to all sensor nodes, and that each sensor node uses its RSS measurement to estimate the distance between the target and itself. Based on the RSS measurement at the ith sensor node, denoted as Ri, the path loss from the target to the ith sensor is measured as PLi = P - Ri. Referring to [29–34], we can describe the RSS measurement of sensor node i by using the log-distance path loss model in decibels (dB), as follows: PLi ðdBÞ ¼ PL0 þ 10m log10 ðdi =d0 Þ þ X0 ;

ð1Þ

where PLi denotes the path loss measured at sensor node i with the real distance di ¼ kpi  h k, PL0 (in dB) is the reference path loss at a position with distance d0, m is the

123

mean path loss exponent for the surroundings, and X0  N ð0; r2X0 Þ (in dB) is the zero-mean white Gaussian noise with variance r2X0 , representing the log-normal shadowing effect. In [29–34], PL0 and m are known from prior measurements in the actual environments or are assumed known a priori; based on that, we can compute the distance estimate at sensor node i using the maximum likelihood estimate of the distance in [30] as d^i ¼ d0 10

PLi PL0 10m

X0

¼ di 1010m :

ð2Þ

With c ¼ 10m= ln 10, we can calculate the mean and variance of d^i and the mean of d^i2 as ld^i ¼ Efd^i g   Z1 1 1 2 p ffiffiffiffiffi ffi expðX0 =cÞ exp  ðX0 =rX0 Þ dX0 ¼ di 2 2prX0 1 h . pffiffiffi i2 ¼ di exp rX0 ð 2cÞ ð3Þ r2d^ i

2

¼ Efðd^i  ld^i Þ g

. 3 2 2 ðX  2r 0 X0 cÞ 1 5 pffiffiffiffiffiffi exp4 ¼ di2 expðr2X0 c2 Þ 2r2X0 1 2prX0 ) h i . expðr2X0 c2 ÞdX0  1 ¼ di2 expðrX0 =cÞ2 expðrX0 =cÞ2  1 (Z

.

1

2

ð4Þ .

pffiffiffi ld^2 ¼ Efd^i2 g ¼ r2d^ þ l2d^ ¼ di2 expð 2rX0 cÞ2 : i

i

i

ð5Þ

Let ei ¼ d^i  di denote the distance estimation error at sensor node i. Then the corresponding mean, variance, and mean-square error (MSE) are as follows:  h .  pffiffiffi i2 lei ¼ Efei g ¼ di exp rX0 2c 1 ð6Þ h i

2 r2ei ¼ Ef ei  lei g ¼ di2 expðrX0 =cÞ2 expðrX0 =cÞ2 1 ð7Þ MSE ¼ E½e2i 

¼ di2 exp

 .pffiffiffi 2  pffiffiffi . 2 2c þ1 : 2rX0 c 2 exp rX0 ð8Þ

It can be seen that the MSE given in (8) is proportional to di, and even X0 is assumed to be independent of di. This implies that the greater the real distance, the larger the distance estimation error. In other words, the sensor nodes closer to the target are more likely to produce accurate or reliable estimates of the distances in (2). This is consistent

Wireless Netw

with our intuition that the signal transmitted to a sensor node that is located far away from the target may encounter more obstacles and be subject to more scatter, which would make the corresponding RSS (i.e., path loss) measurement less reliable and the distance estimate less accurate. At the beginning of the positioning procedure, each sensor node receives the signal from the target, and then the RSS measurements are processed to derive the optimal location estimate at the central processor. However, the quality of the local observations varies dramatically from sensor node to sensor node in diverse or hostile environments, which makes it necessary to take into consideration the sensor nodes’ reliability in the positioning procedure. A reliability concept of distance estimation for the sensor nodes is presented in [15] as on the distance-based weighting factors (i.e., fwi gNi¼1 ¼ 1=Oðfd^i2 gNi¼1 Þ), where the more reliable estimates (i.e., those with smaller distance estimates) are given more weight and the effects of the less reliable estimates (i.e., those with larger distance estimates) are suppressed at the sensor nodes. As described in [14–16, 18, 19], the sum of N weighted observation functions for N sensor nodes can be expressed as N X i¼1

wi ðPLi  PLðkpi  hkÞÞ2 ¼

N X

wi fi ðhÞ;

ð9Þ

i¼1

where h 2 <2 is the location estimate to be computed, the ith term with PLðkpi  hkÞ,PL0 þ 10m log10 ðkpi  hk=d0 Þ in the summation is evaluated by sensor node i and its distance estimate kpi  hk, fi ðhÞ,ðPLi  PLðkpi  hkÞÞ2 is the ith 2 observation function, and wi ,1=ð1 þ d^i2 =d^i1 Þ is the ith weighting factor derived in [15, 19]. The observation functions in (9) were exploited in the implementation of the decentralized IG method in [14], where the IG method converges to a location estimate in the vicinity of the target that minimizes the sum of the observation functions when a certain sequence of step sizes is used. However, the IG method typically has a slow convergence rate because a small step size for convergence is required. If the IG method’s step size is instead taken to be a large value to improve the convergence rate, an oscillation within each observation cycle usually arises, as presented in [14]. An alternative scheme—the IEKF—is proposed in [20, 21] to solve the NLS problem. The diminishing step sizes of the IEKF are picked adaptively according to the sensor nodes’ observations, where a large step size is computed early in the process to achieve a fast convergence rate and a small step size is calculated later for better convergence. Hence, the IEKF method is considered more suitable for decentralized positioning applications. The disadvantage of the IEKF method is that it does not take into account the reliability of the distance estimates from the different sensor nodes and gives equal weight to all sensor nodes with high measurement

noise. In the next section, we focus on a weighted positioning method that combines the advantage of the IG method for a finite set of observations with the often superior convergence rate of the IEKF method. 3 A decentralized weighted extended Kalman filterbased (WEKF-based) method 3.1 A WEKF algorithm based on recursive weighted least-squares optimization For ease of presentation, the ordered sequence of sensor nodes operating in the decentralized positioning process is denoted as {1, 2, …, j, …, i,…, n}. To derive the WEKF algorithm in an iterative manner, we consider the jth term in the summation in (9) and adopt a local objective function in sensor node j at the jth iteration of the kth iteration cycle. Using a design technique for the local objective function presented in [20, 21], we attempt to let the location estimate ^hj;k be the given vector ^zj;k in Eq. (9) of [20] and Eq. (1.125) of [21] and to make the local objective function that is nonlinear of the form at the jth iteration of the kth iteration cycle as pffiffiffiffiffiffiffiffiffi  fj ðhÞ ¼ ^hj;k  wj Cj ð^hj1;k Þh; ð10Þ k2 where fj ðhÞ and wj are defined in the same way as in (9), the location estimates ^hj1;k 2 <2 and ^hj;k 2 <2 are computed at the (j - 1)th iteration and the jth iteration, respectively, the parameter k increased with the kth iteration cycle is designed for the convergence of the method (as the relaxation parameter used in the POCS method in [16, 17]) that we will describe in Sect. 3.2, rfj ð^hj1;k Þ,ofj ð^hj1;k Þ=o^hj1;k is the subgradient of the function fj evaluated at ^hj1;k , and Cj ð^hj1;k Þ, krfj ð^hj1;k Þ. Comparing (10) with Eq. (9) in [20], we see that, when ^hj;k ¼ ^zj;k and k = 1, (10) is formulated by the nonlinear method and the function Cj ð^hj1;k Þh in (10) is assigned the weight wj based on the reliability of the jth sensor node, which differs from the linear method with an equal weight scheme in Eq. (9) of [20]. As a result, the convergence analysis in [20] is not applicable to our proposed method. According to the form adopted in (10), we would like to fit a nonlinear model fwj Cj ð^hj1;k Þhgij¼1 to the set of ^h1;k , ^ h2;k , …, ^hj;k , …, ^hi;k at the kth iteration cycle. Consider the incremental method that sequentially generates the location estimates pffiffiffiffiffiffiffiffiffi!2 ij  i X fj ðhÞ k ^hi;k ¼ arg min Fi;k ðhÞ, arg min k2 h2<2 h2<2 j¼1 ¼ arg min h2<2

i   2 X  ij ^  hj;k  wj Cj ð^hj1;k Þh  ; k

ð11Þ

j¼1

123

Wireless Netw

where ^ hi;k is computed in sensor node i at the ith iteration, a recursive-in-time objective function Fi;k ðhÞ is adopted, kij is the jth forgetting factor with 0\kij  1 described in [20, 21] which is used to provide bias to the jth local objective function, and sensor node i acts at the ith iteration with 2 Pi   ij ^  ^ j¼1 k ðhj;k þ kwj rfj ðhj1;k ÞhÞ . Given the incremental nature in (11), it can be referred to as a recursive weighted leastsquares optimization process [35]. By carrying out the minimization of (11) in the x-dimensional space and multiplying both sides by kwj rx fj ð^ hj1;k Þ, the x x ^ and h are found to be solutions with the relations of h j;k

hj1;k Þ^ hxi;k ðkwj rx fj ð^ hj1;k ÞÞ kij kwj rx fj ð^ j¼1;...;i ij ^x x ^ ¼ k hj;k ðkwj r fj ðhj1;k ÞÞ ; j¼1;...;i

ð12Þ

^y Þ, h,ðhx ; hy Þ, and ^ hxj;k ; h hi;k ,ð^ hxi;k ; h^yi;k Þ are where ^ hj;k ,ð^ j;k defined in (10) and (11). Summing both sides of (12) over j = 1, …, i, we have " # i1 X hx ^hx ¼ ðkij kwj rx fj ð^ hj1;k Þ^ hx Þ i;k i;k

j;k

j¼1

 kwi rx fi ð^ hi1;k Þ^ hxi;k

ð13Þ

with hxi;k ¼

i X

kij ðkwj rx fj ð^ hj1;k ÞÞ2

j¼1

¼ khxi1;k þ ðkwi rx fi ð^ hi1;k ÞÞ2 ;

ð14Þ

where hxi;k is the diminishing factor at the ith iteration and hx0;1 ,0. This means kwi rx fi ð^ hi1;k Þ at the

that

hxi;k

can be easily calculated by

current sensor node i and hxi1;k passed from the previous sensor node i - 1. In the case k\1, the effect of the previous hxi1;k is discounted, and the current hxi;k produced by (14) tends to change more rapidly. Substituting the lefthand side of (12) for j = 1, 2, …, i - 1 into the brackets of (13) gives hxi;k ^ hxi;k ¼

" i1 X

hxi1;k kij ðkwj rx fj ð^ hj1;k ÞÞ2 ^

f i ð^ hi1;k Þ^ hxi;k

 kwi r hxi1;k  kwi rx fi ð^ ¼ hxi;k ^ hi1;k Þ x x ^ þ kwi r fi ð^ hi1;k Þ^ hx Þ; ðh i;k

123

i1;k

Multiplying both sides of (16) by 1=hxi;k , ^hxi;k can be computed as qffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi   ^  wi   fi ðhi1;k Þ ^hx ¼ ^hx rx fi ð^hi1;k Þ i;k i1;k  khxi;k ð17Þ ¼ ^hxi1;k  lxi;k rx fi ð^hi1;k Þ; where

the ith variable step size is defined as qffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi   x ^  lxi;k ,wi   fi ðhi1;k Þ=ðkhi;k Þ, which depends on the reliability information of the current sensor node and all previous ones and decreases with the increasing parameter khxi;k . It is easy to understand that the location estimate h^y in the yi;k

dimensional space can be derived by the above proof procedure (12)–(17) when the superscript is y instead of x. Note that although the IEKF method minimizes the sum of the local objective functions in concept, a corresponding proof has not been given to show this. Specifically, we provide a complete proof in (10)–(17) to fill this gap. Per the statement above, the iterative positioning scheme based on the WEKF algorithm can be summarized as follows: Step 1

First Iteration Cycle: k = 1

Step 2 Initialization: Use the location of sensor node 1 as the initial value ^h0 ¼ ^h0;1 Step 3

Iteration Steps: for i = 1, 2, …, n

½^hxi;k ^hyi;k T ¼ ½^hxi1;k ^hyi1;k T  ½lxi;k rx fi ð^hi1;k Þlyi;k ry fi ð^hi1;k ÞT ½hxi;k hyi;k T ¼ k½hxi1;k hyi1;k T

ð18Þ

Step 4 ^hn;k is used as ^h0;kþ1 at the next iteration cycle k = k ?1

j¼1

x

defined as the ith local objective function for the ith iteration. Thus, we obtain qffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi  x wi  x ^x x ^x ^ hi;k hi;k ¼ hi;k hi1;k   ð16Þ fi ð^hi1;k Þ  r fi ðhi1;k Þ: k

þ ðkwi Þ2 ½ðrx fi ð^hi1;k ÞÞ2 ðry fi ð^hi1;k ÞÞ2 T

#

 kwi rx fi ð^ hi1;k Þ^ hxi;k h i hxi1;k  ðkwi rx fi ð^ hxi1;k ¼ hxi;k ^ hi1;k ÞÞ2 ^

qffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi   2 x x x ^ ^ ^ ^  where hi;k þ kwi r fi ðhi1;k Þhi1;k ¼   fi ðhi1;k Þ=k is

ð15Þ

Step 5 Repeat Step 3: The iterative process is stopped when k = W and i = n, where n (  N) is the number of participating sensor nodes, superscript T denotes transpose, W is the total number of iteration cycles, hi;k ,ðhxi;k ; hyi;k Þ and li;k ,ðlxi;k ; lyi;k Þ are denoted in (14) and (17), respectively, and

Wireless Netw

li;k rfi ð^ hi1;k Þ,ðlxi;k rx fi ð^ hi1;k Þ; lyi;k ry fi ð^ hi1;k ÞÞ with the upper bounds for li;k as qffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi   qffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi  f i ð^   hi1;k Þ ^i1;k Þ    fi ðh          li;k  ¼      khi;k  khi1;k  þ ðkwi  hi1;k ÞÞ2 rfi ð^ qffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi    f i ð^ hi1;k Þ     :  max ð19Þ   1  i  n;1  k  W hi1;k ÞÞ2 ðwi rfi ð^ It also can be shown that the subgradient boundedness holds as follows:    20m  ðp  ^  i hi1;k Þ   ^i1;k Þ ¼  rfi ðh 2 fPLi  ½PL0 þ 10mlog10 ln10  ^i1;k  pi  h     .   ^i1;k  d0 Þg ðpi  h   20m max k½10mlog10 ðdi =d0 Þ d0 ln10 1in þX0 k,C; ð20Þ     hi1;k Þ for all i = 1, where C is the upper bound of rfi ð^ 

2, …, n and k = 1, 2, …, W. Fig. 1 demonstrates how the positioning process operates among the participating sensor nodes. During the ith iteration of the kth iteration cycle, sensor node i computes ^ hi;k according to its RSS measurement PLi, the accumulated diminishing vector hi1;k , and ^ hik;k from the (i–1)th iteration of the kth iteration cycle, and then transmits ^ hi;k and hi;k to sensor node i ? 1 for further processing. For decentralized positioning, the IG method in [14] and the IEKF method in [20, 21] (or the weighting scheme of the WIP method in [15, 19]) can be viewed as special cases of our proposed WEKF algorithm. For the latter, the current

Initial Estimate

Final Estimate

0

n ,W

n− 1,W

, hn− 1,W

i + 1,k

PLi +1

Sensor Node 1

Sensor Node n

PLn

1,1

, hi+ 1,k

PL1

, h1,1

i− 1,k

Sensor Node i+1

Sensor Node i i ,k

, hi− 1,k PLi

, hi ,k

Fig. 1 The decentralized WEKF algorithm for n 9 W iterations

reliability information and the accumulated reliability information from the past to the present are used to update the variable step size, but for the former, only the fixed step size [14] and the diminishing step size [20, 21] (or the current reliability information and an appropriate previous one [15, 19]) are considered. To simplify the IEKF method, the authors of [18] further replace the diminishing step size in each iteration with the fixed step size to form a reduced-complexity IG method and thus the difference between the IEKF method (or the WEKF method) and the IG method appears to be very modest, as presented in [18]. In fact, the WEKF method adopts an effective rule for updating the step size at each iteration, which is a large difference from the IG method. Accordingly, it is expected that the WEKF algorithm generally has better performance and is more robust than the WIP, IG, and IEKF methods in time-variant environments. 3.2 A convergence analysis of the WEKF algorithm To demonstrate the convergence behavior of our proposed WEKF algorithm, the following two propositions are given. Proposition 1 Letting the magnitude boundedness of (20) hold, we have min f ð^hk Þ  f  þ nC 2 þ d;

ð21Þ

1kW

where f   inf ^hk 2<2 f ð^hk Þ is a theoretical optimal value, ^hk ¼ ^hn;k1 ¼ ^h0;k is obtained at the nth iteration of the (k - 1)th iteration cycle, and d is a positive scalar whose range is derived in Proposition 2. Because every iteration cycle consists of n iterations, the number of iteration cycles W needed for (21) to hold is given by $ ! )% ,(  2  n  X ^    W ¼ h 0  h   ; ð22Þ 2 min d l  1kW

i;k

i¼1

where ^h0 defined in Sect. 3.1. After W iteration cycles, it is guaranteed that min1  k  W f ð^hk Þ converges to a finite value within OðnC 2 þ dÞ of f*, in which, if a small step size is given to improve the convergence accuracy, W will increase, and vice versa. In fact, our proposed variable step size rule in (17) may lead to convergence that approximates the target location in a reasonable amount of iteration cycles because a large variable step size is chose in early to improve the convergence rate, and then is followed by a small variable step size to achieve accurate positioning. We give a proof for Proposition 1 in Appendix 1. Proposition 2 Assume that Proposition 1 holds and that 0 there exists a positive scalar d such that f ð^hk Þ  f   2   d0 h^k  h  ; 8^hk 2 <2 , we have

123

Wireless Netw

"  2 ^  hWþ1  h   1  2d0 min

1kW

 2 ^  h0  h  þ

n   X   li;k 

!#W

i¼1

2

d0

ðnCÞ P    n  min i¼1 li;k 

ð23Þ

1kW

and  2 ^  ðnCÞ2 h0  h  þ d0 min Pn l ð i¼1 k i;j kÞ  j  k1   1P 0d  n  2 min i¼1 li;j  1  j  k1  P    with d0  1=f2 min1  k  W ð ni¼1 li;k Þg.

ð24Þ

A proof for Proposition 2 is presented in Appendix 2. These propositions confirm the convergence behavior of the WEKF algorithm, which shows that both the initial value and the number of iteration cycles play key roles in estimation accuracy and convergence rate. From the propositions, the closer the initial value is to the target, the more likely it is to improve our algorithm’s performance or any other decentralized method’s performance. In addition, min1  k  W f ð^ hk Þ will approach f* after W iteration cycles when a low d can be obtained. Therefore, the estimation accuracy that is relevant to the step size rule and the initial value selection, and the number of iteration cycles required to converge on the neighborhood of the target location depends on the real surroundings. It is very interesting to note that the convergence analysis results of the IEKF and IG methods are not applicable to our proposed algorithm. The convergence analysis we present for the WEKF algorithm is different from those of the IEKF and IG methods as follows: (1) we proved the subgradient boundedness in (20) holds, rather than assuming it holds as it did in [18, 20]; (2) we considered the reliability information of the distance estimates in our analysis; (3) we derived the relationship in (24) between Proposition 1 (similar to Proposition 2.3 in [18]) and Proposition 2 (similar to Proposition 2.4 in [18]) in terms of 0 the positive scalars d and d ; and (4) we discussed how the initial value ^ h0 , the iteration cycle k, the number of iteration cycles W, and the positive scalar d affect the convergence behavior of the WEKF algorithm. 3.3 A message-passing (MP) algorithm for target tracking In dense large-scale sensor networks, we propose an MP algorithm for the WEKF algorithm and for adaptively selecting the participating sensor nodes. During network initialization, we assume that sensor node 1 as s[1], sensor node 2 as s[2], …, sensor node i as s[i], …, and sensor node n as s[n] are an ordered sequence of sensor nodes that

123

participate in the positioning process, and that Time[1], Time[2], …, Time[i], …, Time[n] are an ordered sequence of time indices in a path of cycle routing. In other words, Time[i] is the period of time of the ith iteration at sensor node i in accordance with the order, where i = 1, 2, …, n at the kth iteration cycle and k = 1, 2, …, W at an update process. Each participating sensor node is able to establish a one-hop neighbor table that contains the following information: (1) Sensor node ID and location coordinate: Each sensor node is given a unique identification number and its location coordinates after deployment; (2) Sensor node state: Each sensor node can operate in active, standby, or sleep mode; and (3) Sensor node routing path: The active (i.e., participating) sensor nodes can construct a routing path through the active network based on the RSS measurements, and each active sensor node makes a calculation once per iteration. As an energy consideration for the sensor nodes in [1, 12], we set three different power thresholds at each sensor node, and the sensor nodes can operate under one of three modes: active mode, standby mode, and sleep mode. Each sensor node has a sensing ability to detect the presence of the target, and the RSS measurements can be recorded at the sensor nodes. When a sensor node receives the target’s broadcast signal, the sensor node’s mode is determined solely by comparing the RSS measurements with three different power thresholds. For example, if the RSS measurement exceeds the sleep threshold, then the sensor node goes into either the active mode or the standby mode. Thus, the RSS measurement at a sensor node that is far away from the target likely will be low; therefore, that sensor node likely will not be selected as an active sensor node and will be allowed to enter the sleep mode for a short period of time. Each sensor node in the sleep mode wakes up periodically to compute a relative distance between itself and the target by using (2). If the RSS measurement exceeds the standby power threshold or if the local estimate indicates that the target is sufficiently close, the sensor node will switch from sleep mode into standby mode; when in standby mode, it will listen frequently to the messages from the active sensor nodes. A sensor node that is located in the vicinity of the target receives a high RSS measurement, is in active mode, and has a high probability of being selected as a participant. In this case, the sensor node remains active throughout the period. The decision procedure of the ordered sequence of active sensor nodes can be performed by having each active sensor node set a timer that is proportional to the inverse of the RSS measurement (i.e., the timer of active sensor node i is set to 1/RSSi). When the time expires, a message containing the time-stamp at the instant time expired is broadcast to other active sensor nodes. If the received time-stamp at any active sensor node is smaller

Wireless Netw

200 Routing Path Target Location Standby/Sleep Sensor Nodes Active Sensor Nodes

180 160

S[4]

140 Time1[n-3]

Meter

120

S[3]

S[n-2]

100

Time1[3]

S[n-3]

Time1[2]

Time1[1]

Time1[n-2]

80

S[2]

S[1]

60 40

S[n-1]

Time1[n-1]

Time1[n]

20 0

S[n] 0

20

40

60

80

100

120

140

160

180

200

Meter

Fig. 2 The decentralized WEKF-based method for locating a moving target

than the local time-stamp, only the smaller of the two is passed on to other active sensor nodes. If an active sensor node does not receive a message with a smaller timestamp, it will be selected as an active sensor node with the largest RSS measurement. The active sensor nodes use the magnitude of the RSS measurements to determine their ordered sequence, as follows: the comparison of the RSS measurements are s[1] [ _ [ s[i] [ _ [ s[n]. In other words, s[1] has the largest RSS measurement and s[n] has the smallest RSS measurement. With the s[1]’s RSS measurement, s[1] has a high probability of being close to the target location. Hence, s[1]’s location (i.e., ps[1]) and s[1] is set as the initial value ^ h0 and the cluster head, respectively. This is important in both estimation accuracy and in the convergence rate, which we have shown by using mathematical proofs in Sect. 3.2. On the 1st iteration of the 1st iteration cycle, once ^h1;1 is computed at s[1] by using (18), s[1] selects an active sensor node with the second largest RSS measurement as s[2] and passes ^ h1;1 to s[2], and the update procedure continues according to the ordered sequence. When the 1st iteration cycle is completed at the nth iteration, s[n] updates ^hn;1 to ^ h0;2 , which then is used as the initial value at the 1st iteration of the 2nd iteration cycle. The newest location estimate always surrounds the target during the period of n 9 W iterations, in which an update process is circulated through the active sensor nodes and stopped at the nth iteration of the Wth iteration cycle, as presented in Sect. 3.1. In the moving target tracking application, we hypothesize that the target moves from the current location A to the next location B and broadcasts a signal to all sensor nodes at these two locations. We here consider the message passing is sufficiently faster than the movement of the target and that the location estimate can be maintained as it moves around the area in the period of n 9 W iterations

(i.e., an update process). According to the update statement above, when a final estimate ^hAn;W is computed by the current active sensor nodes in the neighborhood of location A, s[1] will broadcast :^hAn;W to the next active sensor nodes in the neighborhood of location B, and h^A then is viewed n;W

as an initial value ^hB0;1 to track the target location. Fig. 2 shows that the active sensor nodes act like a dynamic cluster that always surrounds the target by using different operation modes, and that the newest estimate is circulated only among these active sensor nodes. It is clear that the MP algorithm is more energy efficient, when the average number of hops to a central processor or an active sensor node (i.e., a sink node) exceeds the necessary number of iterations in an update process, as compared to the centralized manner in [10, 11]. To achieve better energy efficiency, the WEKF-based method (i.e., the WEKF algorithm with the MP algorithm) can be extended to a mix of centralized and decentralized approaches because two different approaches are chosen adaptively based on a comparison of the numbers of hops and iterations. This is a worthy subject for future research. 4 Computer simulation results To verify the performance of the proposed WEKF-based method, we performed computer simulations on a sensor network with N = 20 9 20 sensor nodes uniformly distributed over a 200 9 200 m2 two-dimensional area. Because the density of the network is dependent on the number of sensor nodes, we choose N = 400 to form a dense network. The parameters of (1) are: d0 = 1 m, PL0 = 34.7 dB, m = 3, and X0  N ð0; 72 Þ. This is because d0 typically is set to 1 m in indoor environments [29–34], PL0 = 34.7 dB is measured using a narrow-band signal

123

Wireless Netw 200

10 Target Locations Target Location Estimates Standby/Sleep Sensor Nodes Active Sensor Nodes

180 160 140

10

IG method IEKF method WEKF method

2

RMSE (m)

120

Meter

3

100 80

10

60

1

40 20 0

10 0

20

40

60

80

100

120

140

160

180

200

Meter

Fig. 3 Simulation results of the decentralized WEKF-based method for tracking a moving target

strength measurement system in a free space environment in [32], and m = 3 and X0  N ð0; 72 Þ are selected as an office room environment in [29]. A simulation example of a continuing moving target scenario is given in Fig. 3, where a target broadcasts one signal per second (every 1.5 m) to all sensor nodes and moves continuously along the thin solid straight line from one location coordinate (x-dimensional location = 5 m, y-dimensional location = 5 m) to another (x-dimensional location = 110 m, y-dimensional location = 110 m) at a rate of v = 1.5 m/s during 100 s, and that the target motion model is x(s) = 5 ? vx 9 s and y(s) = 5 ? vy 9 s with vx = 1.0607 m/s as the horizontal velocity and vy = 1.0607 m/s as the vertical velocity. Therefore, the target broadcasts 100 signals to all sensor nodes in each 100 s of each trial, and we have 100 update processes (100 estimated target locations) to track the target locations in every trial. With the proposed MP algorithm in Sect. 3.3, an active power threshold was set to be 75 dB at each sensor node that received a path loss (i.e., RSS) measurement every second, and the number of active sensor nodes n is environment-dependent and may be different in different update processes. The ordered sequence for the positioning process was determined by the reverse order of the path loss measurements at the active sensor nodes and the initial value ^ h0 was set as the s[1]’s location. The total number of iteration cycles W in an update process was set to one. That is, there is one iteration cycle and the cycle consists of n iterations in an update process. The active sensor nodes circulate a location estimate once during one second to obtain ^ hn; 1 in the current update process, which then is used as an initial value ^ h0; 1 in the next update process. Note that the average number of active sensor nodes was about n ¼ 23 for each iteration cycle in our

123

0

0

0.2

0.4

0.6

0.8

1

Parameters

Fig. 4 The RMSE versus a of the IG-based method, kIEKF of the IEKF-based method, and kWEKF of the WEKF-based method in a moving target scenario

simulations. For the purposes of comparison, the IG-based, POCS-based, WIP-based, and IEKF-based methods [14–21] also were simulated in the same environment, where we repeated the trial of the minimum root-mean-squared error (RMSE) of the IG-based, IEKF-based, and WEKF-based methods 10,000 times at each step size a and each forgetting factor k between 0.01 and 1 (in increments of 0.01) to pick their parameters according to a minimum RMSE. In Fig. 4, optimal parameters of the IG-based method, IEKF-based method, and WEKF-based method were selected as a = 0.03, kIEKF = 0.6, and kWEKF = 0.8 in the tracking process, respectively. A convergence criterion in [16] is repeatedly checked to determine the POCS method’s relaxation parameter. We compare the cumulative distribution function (CDF) of the distance estimation error and the RMSE of the target location estimate for the converged estimate using 10,000 trials. Fig. 5 shows simulation results of the CDF of the distance estimation error for different methods. We can see that the distance estimation error is within 5.7, 10.25, 6.66, 6.1, and 4.1 m in 90 % of the trials for the IG-based, POCS-based, WIP-based, IEKF-based, and WEKF-based methods, respectively, where the proposed WEKF-based approach has better positioning accuracy than the other four. The WEKF-based method also obtains a good RMSE and a fast convergence rate as shown in Fig. 6. During each update process, as displayed in Fig. 6, our proposed algorithm converges to a boundary point in the neighborhood of the target location and has an average RMSE was 3.3223 m for 100 target location estimates. It also has a better convergence curve than the other methods because the average RMSE of the IG-based method, POCS-based method, WIP-based method, and IEKF-based method was 4.3847,

1

1

0.9

0.9

0.8

0.8

0.7

0.7

0.6

0.6

CDF

CDF

Wireless Netw

0.5 0.4

0.4

0.3

IG method POCS method WIP method IEKF method WEKF method

0.2 0.1 0

0

2

4

6

8

10

12

0.2 0.1 14

12

IG method POCS method WIP method IEKF method WEKF method

RMSE (m)

8

6

4

2

10

20

30

40

50

60

70

80

0

0

2

4

6

8

10

12

14

16

18

Distance Estimation Error (m)

Fig. 5 The CDF of the distance estimation error for different positioning methods

10

IG method POCS method WIP method IEKF method WEKF method

0.3

Distance Estimation Error (m)

0

0.5

90

100

Number of Target Location Estimates

Fig. 6 The RMSE versus the number of target location estimates for different positioning methods

8.0492, 4.4919, and 4.8995 m, respectively. As shown in Figs. 3 and 6, the WEKF-based method locks quickly onto the target location in the tracking process, which suggests that our proposed algorithm may be less sensitive to locally optimal solutions than the other methods since our algorithm takes into consideration the distance estimates’ reliability for the participating sensor nodes. Consequently, the computer simulation results show that the WEKF-based method not only provides for extremely fast convergence rates, but also leads to the iteration quickly converging on the neighborhood of the target location based on the proposed variable step size rule. In addition, we conducted computer simulations for 10,000 trials under an arbitrary initial point to show that the WEKF-based method significantly outperforms the other four methods in Fig. 7, where

Fig. 7 The CDF of the distance estimation error for different positioning methods with arbitrary initial value

the initial point was randomly located with a uniform distribution for each trial in the area. In Fig. 7, it can be observed that the distance estimation error is within 19 m in 82 % of the trials for the IG-based method and the distance estimation error is within 14.85, 11.85, 12.95, and 6.65 m in 90 % of the trials for the POCS-based, WIPbased, IEKF-based, and WEKF-based methods, respectively. This result demonstrates that the WEKF-based method is always better than the other methods and that performance gains over the other four methods seem very large, although the positioning performance is worse than that for the initial point set at the location of s[1] in Fig. 5. To study the effects of the parameters N, d0, PL0, and m on the tracking results for different positioning methods, we conducted computer simulations of the CDF of the distance estimation error in Figs. 8, 9, 10, and 11, respectively, where the simulation environment was the same as that in Fig. 5, except for the number of sensor nodes, the reference distance, the reference path loss, or the path loss exponent in each trial being N = 15 9 15 for a sparse network in Fig. 8, m = 3.3 for a factory environment [29] in Fig. 9, d0 = 0.8 for a short reference distance in Fig. 10, and PL0 = 38.7 for a large reference path loss in Fig. 11. In short, the computer simulation results demonstrate that more than 90 % of the estimated locations using the WEKF-based method achieved error distances of less than 7.25, 5.9, 5.6, and 4.93 m, while the other methods had error distances of more than 10.25, 7.6, 7.5, and 7.05 in Fig. 8, in Fig. 9, in Fig. 10, and in Fig. 11, respectively. Specifically, comparisons of the WEKF-based method and the other methods with these parameter settings in terms of the CDF of the distance estimation error (90 % of the estimated error distances) are given in Table 1, where the average number of active sensor nodes n is around 12, 20,

123

1

1

0.9

0.9

0.8

0.8

0.7

0.7

0.6

0.6

CDF

CDF

Wireless Netw

0.5

0.4

0.4 0.3

0.3

IG method POCS method WIP method IEKF method WEKF method

0.2 0.1 0

0.5

0

2

4

6

8

10

12

14

16

IG method POCS method WIP method IEKF method WEKF method

0.2 0.1 0

18

0

2

4

Distance Estimation Error (m)

Fig. 8 The CDF of the distance estimation error for different positioning methods with N = 15 9 15

8

10

12

14

16

Fig. 10 The CDF of the distance estimation error for different positioning methods with d0 = 0.8 m

1

1

0.9

0.9

0.8

0.8

0.7

0.7

0.6

0.6

CDF

CDF

6

Distance Estimation Error (m)

0.5

0.5 0.4

0.4 0.3 0.2 0.1

0.2 0.1 0

0 0

2

4

6

8

10

12

14

16

IG method POCS method WIP method IEKF method WEKF method

0.3

IG method POCS method WIP method IEKF method WEKF method 18

Distance Estimation Error (m)

0

2

4

6

8

10

12

14

Distance Estimation Error (m)

Fig. 9 The CDF of the distance estimation error for different positioning methods with m = 3.3

Fig. 11 The CDF of the distance estimation error for different positioning methods with PL0 = 38.7 dB

14, and 12 for the parameters N, m, d0, and PL0, respectively, by our simulations. According to the simulation results in Figs. 5 and 8, decreasing the number of sensor nodes has a considerable effect on the performance of the decentralized methods, but our method still outperforms the other four. In Fig. 5, the dense deployment of sensor nodes (i.e., the more sensor nodes) provides an accurate and robust estimate of the target location. This is mainly due to the fact that the closer the sensor nodes are to the target, the more likely they are to improve the accuracy of the distance estimates and the positioning efficiency, as noted in the reliability concept discussed in Sect. 2. When the value of N becomes small, it diminishes the location accuracy of the methods, as shown in Fig. 8, especially for the IG-based, POCS-based, WIP-based, and IEKF-based methods, which

are more sensitive than the WEKF-based method to variation in the number of sensor nodes. Using the same active power threshold in Fig. 5, the relationships between the average number of active sensor nodes n and the settings of parameters m, d0, and PL0 are displayed in Table 1, where the parameters are related to the path loss measurements of sensor nodes as shown in (1). As compared to the case of n ¼ 23 in Fig. 5, we see that the selected parameters in Table 1 increase the path loss measurement of each sensor node; thus, the values of n for m, d0, and PL0 will decrease at the same active power threshold. These simulation results are expected because n is linked to m, d0, and PL0 of (1) through the fixed active power threshold. From n ¼ 23 in Fig. 5 and Table 1, we observe that the positioning performance of the different methods improve for the case of

123

Wireless Netw Table 1 The CDF of the distance estimation error for different positioning methods with different parameter settings Methods

Parameters N = 15 9 15, n ¼ 12

m = 3.3, n ¼ 20

do = 0.8 m, n ¼ 14

IG [CDF 90 % (m)]

10.25

POCS [CDF 90 % (m)]

13

11.7

10.95

9.1

WIP [CDF 90 % (m)]

11

10.4

9.62

8.8

IEKF [CDF 90 % (m)]

10.3

7.6

7.5

7.05

5.9

5.6

4.93

WEKF [CDF 90 % (m)]

8.75

7.25

a=0.5

7.77

and observed from the simulation results that our method still outperforms the other methods; however, the localization performance for the correlated noise cases is worse than that for the white noise case. The performance degradation is not significant for a = 0.1 and a = 0.3, and is still acceptable for a = 0.5 (shown in Fig. 12). These further support the usefulness of the proposed WEKF-based method.

1 0.9 0.8 0.7 0.6

CDF

8.87

PLo = 38.7 dB, n ¼ 12

0.5 0.4

0.2 0.1 0

5 Conclusion

IG method POCS method WIP method IEKF method WEKF method

0.3

0

5

10

15

20

Distance Estimation Error (m)

Fig. 12 The CDF of the distance estimation error for an environment with correlated noises

n ¼ 23 as compared to the cases of n ¼ 20, n ¼ 14, and n ¼ 12. This is because the probability that the target is inside the convex hull of the active sensor nodes’ locations increases as the number of active sensor nodes increases, as the CF problem discussed in [16]. Consequently, simulation results show that the WEKF-based methods in Figs. 9, 10, and 11 have degraded positioning accuracy as compared with that of the WEKF-based method in Fig. 5, but all of them show performance improvements over the previous IG-based, POCS-based, WIP-based, and IEKF-based methods, except for the IG-based method in Fig. 5. To further verify the effectiveness of the WEKF-based method (derived under the white noise assumption), we conducted more computer simulations with correlated noises. For each simulation, the correlated case was generated from a system function H(z) = 1/(1 - az-1) with the zero-mean white noise X0  N ð0; 72 Þ as input, where 0 \ a \ 1 and the higher the values of a the more highly correlated the noise. We performed simulations for a = 0.1, 0.3, 0.5, and 0.7,

In this paper, we have derived a decentralized WEKF algorithm for WSNs via the minimization of a recursive-intime objective function. At each sensor node, we use the proposed algorithm where the weighted average is taken between the sensor node’s observation and the previous local estimate (i.e., the estimate passed to the sensor node from the previous iteration). Also, we have shown the convergence of the WEKF algorithm. We have proposed a simple sensor node selection scheme used for the proposed algorithm based only on the local RSS measurements in the network, which allows the selected sensor nodes to act as a dynamic cluster that surrounds the moving target, and the newest estimate is cyclically updated among these sensor nodes. Computer simulation results are given to show that our proposed method has better performance than the related methods described previously. Acknowledgments This work was supported by the National Science Council of the Republic of China under Grants NSC 94-2219-E007-009, NSC 95-2219-E-007-008, NSC 96-2219-E-007-008, and NSC 96-2752-E-007-003-PAE. This paper was presented in part at the 2008 IEEE Global Communications Conference (Globecom 2008), New Orleans, LA, Nov. 30–Dec. 4, 2008.

Appendix 1 Proof of Proposition 1 We first define a subgradient inequality as [18]

123

Wireless Netw  ^ 0  f i ð^ hi1;k Þ      f \fi ðhi1;k Þ       ^  fi ðh Þ  rfi ðhi1;k Þ^ hi1;k  h ; hi1;k  h   C ^

ð25Þ where C derived in (20). Let assumption (25) hold and let f^ hi;k gni¼1 be the sequence generated by the WEKF algorithm in (18). Then, the sum of squares error for i = 1, 2, …, n, which is bounded by 2 X 2 n  n  X ^  ^  hi1;k Þh  hi;k h  ¼ hi1;k li;k rfi ð^ i¼1

i¼1



i¼1

fi ðh ÞÞþC 2 2

i¼1

n  X i¼1

  n  X   ^   li;k ðfi ðh0;k Þfi ðh ÞÞ2 li;k  i¼1

ðfi ð^ hi1;k Þfi ð^ h0;k ÞÞþC 2

n  X  li;k 2 : i¼1

ð26Þ Rearranging both sides of (26) and applying an inequality P h0;k Þfi ðh ÞÞ in (25), we obtain as f ð^ h0;k Þf   ni¼1 ðfi ð^  2  2 n   X ^      h0;k  h  2ðf ð^ h0;k Þ  f  Þ hn;k  h   ^ li;k 

  2  2 ^  h0;k Þ li;k   h0;k  h  2ðf ð^

  h  i n  n  X X        f Þ li;k  þ 2 li;k C Cði  1Þli;k  þ C2

i¼1 n  X i¼1

  2 li;k  ;

123

i¼1

i¼1

Nevertheless, the relation of (30) cannot hold for a sufficiently large iteration cycle k in the right-hand side  2   because ^hkþ1  h  must be greater than or equal to zero. Hence, (21) is obtained via the proof by contradiction. Following (30), for k = 1, 2, …, W, we get  2  2     0  ^hkþ1  h   ^h0  h  2W min

1kW

! n   X   d li;k  : i¼1

ð31Þ

ð32Þ

i¼1

As desired, (22) can be derived by (32), which contradicts the definition of W.

the outcome in (27). We simplify the terms of (27) with the hkþ1 and ^ h0;k ¼ ^ hk , which become relations of ^ hn;k ¼ ^  2  2  n  X ^      hk  h  2ðf ð^ hk Þ  f  Þ hkþ1  h   ^ li;k 

i¼1

ð30Þ

!   n  n  X X     þ li;2  þ    þ li;k  :

1kW

i¼2

ð27Þ     where we use a relation of inequality as ^ hi1;k  ^hi2;k  ¼     ^  hi2;k ÞÞ  ^ hi2;k   Cli1;k  to obtain ðhi2;k  li1;k rfi ð^

n   X  2 þ 2nC2 li;k  :

 2 n   X          ^h1  h  2d li;1 

Then, W is derived as  2 ^  h0  h 

W  : n  P   2 min d li;k 

i¼2 n  X i¼1

Substituting the result as f ^hk Þ  f  [ nC2 þ d in (29) into (28), we have  2  2 n  X  ^    li;k  hkþ1  h   ^hk  h  2d

i¼1

n    X  ^  þ 2C h0;k  li;k hi1;k  ^

þ C2

ð29Þ

1kW

i¼1

n  n  2 X  X ^  li;k 2 ¼ hi1;k h  i¼1

f ð^hk Þ min f ð^hk Þ [ f  þ nC 2 þ d:

i¼1

n  2 n   X X ^    ^ hi1;k h  2 li;k ðfi ðhi1;k Þ i¼1

To obtain (21) and (22), we use a method of proof by contradiction, as follows: For k = 1, …, W, we assume that if the result of (21) does not hold, then there exists a scalar d 0 such that

i¼1

ð28Þ

Appendix 2 Proof of Proposition 2 A further convergence result of the proposed algorithm is derived from (28), and this result is related to the initial 0 value and a scalar d C 0. Following the assumptions in  2   Proposition 2 and substituting f ð^hk Þ  f  d0 ^hk  h  into (28), we have

Wireless Netw

!  2   2 n  X ^   ^  0  hWþ1  h   1  2d li;W  hW  h  i¼1 ! 2  n  n  X X     0 þ 2nC 2 li;W   1  2d li;W  i¼1 i¼1 ! ! n   n   X X     0 0 1  2d li;W1     1  2d li;1  i¼1

 2  2     where the positive scalar :d ¼ ðh^k  h  ^hkþ1  h  Þ=  P     2 ni¼1 li;k  . Using the derived inequalities d   2   Pn  ^     2 hk  h  =ð2 i¼1 li;k Þ in (36) and h^Wþ1  h k   2 i h Pn  ^    2 h0  h  þðnCÞ = d0 min1  k  W ð i¼1 li;k Þ in (34),

i¼1

 2 2  n  n  X X ^     2 h0  h  þ2nC2 li;W  þ    þ 2nC 2 li;1  i¼1 i¼1 ! ! n   n   X X     0 0 1  2d 1  2d li;W  li;W1  i¼1 ! i¼1 n   X  

   1  d0 li;2  : i¼1

ð33Þ Simplifying and rearranging the outcome in (33), we can express (23) as follows:  2 ^  hWþ1  h  "

!#  W 2 n  X   ^   1  2d min li;k  h0  h  1kW i¼1 ! n   X  2 2 þ 2nC max li;k  0

W 1 X

"

1kW

1  2d

j¼0

0

i¼1

min

1kW

"

 1  2d0 min

1kW

þ d0

!# n   j X   li;k 

ð34Þ

i¼1

!# n   W 2 X   ^  li;k  h0  h  i¼1

ðnCÞ2

n   : P  min li;k 

1kW

i¼1

With the derived result in (28), an inequality for f ð^hk Þ is expressed as  2  2 ^    hkþ1  h  hk  h  ^   f ð^ hk Þ  f þ þ nC 2 : ð35Þ Pn    2 i¼1 li;k  According to (35) and (21), we get min f ð^ hk Þ  f ð ^ hk Þ  f  þ nC2  2  2 ^    hkþ1  h  hk  h  ^ þ  n  P   2 li;k 

1kW

i¼1

¼ f  þ nC2 þ d;

ð36Þ

we finally have  2 ^  hk  h   d P    2 ni¼1 li;k 

 2 ^  h0  h  þ 2

d0

2 ðnCÞ P

n

ð i¼1 kli;j kÞ  j  k1   1P :  n  min i¼1 li;j  min

1  j  k1

ð37Þ References 1. Stankovic, J. A. (2008). Wireless sensor networks. IEEE Computer, 41(10), 92–95. 2. Whelan, M. J., Gangone, M. V., & Janoyan, K. D. (2009). Highway bridge assessment using an adaptive real-time wireless sensor network. IEEE Sensors Journal, 9(11), 1405–1413. 3. Gungor, V. C., Lu, B., & Hancke, G. P. (2010). Opportunities and challenges of wireless sensor networks in smart grid. IEEE Transactions on Industrial Electronics, 57(10), 3557–3564. 4. Shen, C., Srisathapornphat, C., & Jaikaeo, C. (2001). Sensor information networking architecture and applications. IEEE Personal Communications, 8(4), 52–59. 5. Akyildiz, I. F., Su, W., Sankarasubramaniam, Y., & Cayirci, E. (2002). A survey on sensor networks. IEEE Communications Magazine, 40(8), 102–114. 6. Kuo, S.-P., Lin, C.-Y., Lee, Y.-F., Fang, H.-W., Hong, Y.-W., Lin, H.-C., Tseng, Y.-C., King, C.-T., & Wang, C.-L. (2008). The NTP experimental platform for heterogeneous wireless sensor networks. In Proceedings of ACM TRIDENTCOM 2008 (pp. 1–6). 7. Zhao, Z., Yang, G.-H., Liu, Q., Li, V. O. K., & Cui, L. (2011). Implementation and application of a multi-radio wireless sensor networks testbed. IET Wireless Sensor Systems, 1(4), 191–199. 8. Oh, S., Chen, P., Manzo, M., & Sastry, S. (2006). Instrumenting wireless sensor networks for real-time surveillance. In Proceedings of IEEE ICRA 2006 (pp. 3128–3133). 9. Lu, C.-H., & Fu, L.-C. (2009). Robust location-aware activity recognition using wireless sensor network in an attentive home. IEEE Transactions on Automation Science and Engineering, 6(4), 598–609. 10. Patwari, N., Ash, J. N., Kyperountas, S., Hero, A. O., I. I. I., Moses, R. L., & Correal, N. S. (2005). Locating the nodes: Cooperative localization in wireless sensor networks. IEEE Signal Processing Magazine, 22(4), 54–69. 11. Mao, G., Fidan, B., & Anderson, B. D. O. (2007). Wireless sensor network localization techniques. Elsevier Computer Networks, 51(10), 2529–2553. 12. Doherty, L., Warneke, B. A., Boser, B. E., & Pister, K. S. J. (2001). Energy and performance considerations for smart dust. International Journal of Parallel and Distributed Systems and Networks, 4(3), 121–133. 13. Rabbat, M. G., & Nowak, R. D. (2005). Quantized incremental algorithms for distributed optimization. IEEE Journal on Selected Areas in Communications, 23(4), 798–808.

123

Wireless Netw 14. Rabbat, M. G., & Nowak, R. D. (2004). Decentralized source localization and tracking. In Proceedings of IEEE ICASSP 2004 (pp. 921–924). 15. Wang, C.-L., Hong, Y.-W., & Dai, Y.-S. (2007). A decentralized positioning method for wireless sensor networks based on weighted interpolation. In Proceedings of IEEE ICC 2007 (pp. 3167–3172). 16. Blatt, D., & Hero, A. O., I. I. I. (2006). Energy-based sensor network source localization via projection onto convex sets. IEEE Transactions on Signal Processing, 54(9), 3614–3619. 17. Gholami, M. R., Wymeersch, H., Stro¨m, E. G., & Rydstro¨m, M. (2011). Wireless network positioning as a convex feasibility problem. EURASIP Journal on Wireless Communications and Networking, 2011(161), 1–15. 18. Nedic´, A., & Bertsekas, D. P. (2000). Convergence rate of incremental subgradient algorithms. Stochastic Optimization: Algorithms and Applications, 263–304. 19. Wang, C.-L., Chiou, Y.-S., & Dai, Y.-S. (2007). An adaptive location estimator based on Kalman filtering for wireless sensor networks. In Proceedings of IEEE VTC 2007-Spring (pp. 864–868). 20. Bertsekas, D. P. (1996). Incremental least squares methods and the extended Kalman filter. SIAM Journal on Optimization, 6(3), 807–822. 21. Bertsekas, D. P. (1999). Nonlinear programming. Massachusetts: Athena Scientific. 22. Kaemarungsi, K., & Krishnamurthy, P. (2004). Modeling of indoor positioning systems based on location fingerprinting. In Proceedings of IEEE INFOCOM 2004 (pp. 1012–1022). 23. Gogolak, L., Pletl, S., & Kukolj, D. (2011). Indoor fingerprint localization in WSN environment based on neural network. In Proceedings of IEEE SISY 2011 (pp. 293–296). 24. Jung, S.-H., Lee, C.-O., & Han, D.-S. (2011). Wi-Fi fingerprintbased approaches following log-distance path loss model for indoor positioning. In Proceedings of IEEE IMWS-IRFPT 2011 (pp. 1–2). 25. Welch, G., & Bishop, G. (1995). An introduction to the Kalman filter, University of North Carolina at Chapel Hill, Department of Computer Science, Chapel Hill, NC, USA. TR95-041. 26. Zaidi, Z. R., & Mark, B. L. (2005). Real-time mobility tracking algorithms for cellular networks based on Kalman filtering. IEEE Transactions on Mobile Computing, 4(2), 195–208. 27. Zhai, Y., Yeary, M. B., Havlicek, J. P., & Fan, G. (2008). A new centralized sensor fusion-tracking methodology based on particle filtering for power-aware systems. IEEE Transactions on Instrumentation and Measurement, 57(10), 2377–2387. 28. Arasaratnam, I., & Haykin, S. (2009). Cubature Kalman filters. IEEE Transactions on Automatic Control, 54(6), 1254–1269. 29. Rappaport, T. S. (2002). Wireless communications: Principles and practice. New Jersey: Prentice Hall PTR. 30. Patwari, N., Hero, A. O., I. I. I., Perkins, M., Correal, N. S., & O’Dea, R. J. (2003). Relative location estimation in wireless sensor networks. IEEE Transactions on Signal Processing, 51(8), 2137–2148. 31. Wang, G., & Yang, K. (2011). A new approach to sensor node localization using RSS measurements in wireless sensor networks. IEEE Transactions on Wireless Communications, 10(5), 1389–1395. 32. Phaiboon, S. (2002). An empirically based path loss model for indoor wireless channels in laboratory buildings. In Proceedings of IEEE TENCON 2002 (pp. 1020–1023). 33. Hills, A., Schlegel, J., & Jenkins, B. (2004). Estimating signal strengths in the design of an indoor wireless network. IEEE Transactions on Wireless Communications, 3(1), 17–19.

123

34. Klozar, L., Prokopec, J., Hanus, S., Slanina, M., & Fedra, Z. (2011). Indoor channel modeling based on experience with outdoor urban measurement-Multislope modeling. In Proceedings of IEEE COMCAS 2011 (pp. 1–4). 35. Clarkson, P. M. (1993). Optimal and adaptive signal processing. Florida: CRC Press.

Author Biographies Chin-Liang Wang was born in Tainan, Taiwan, R.O.C., in 1959. He received the B.S. degree in electronics engineering from National Chiao Tung University (NCTU), Hsinchu, Taiwan, in 1982, the M.S. degree in electrical engineering from National Taiwan University, Taipei, Taiwan, in 1984, and the Ph.D. degree in electronics engineering from NCTU in 1987. He joined the faculty of National Tsing Hua University (NTHU), Hsinchu, Taiwan, in 1987, where he is currently a Professor and Chair of the Department of Electrical Engineering and a Professor of the Institute of Communications Engineering. During the academic year 1996–1997, he was on leave at the Information Systems Laboratory, Department of Electrical Engineering, Stanford University, Stanford, CA, as a Visiting Scholar. He served as the Director of the Institute of Communications Engineering from 1999 to 2002 and the Director of the University’s Computer & Communications Center from 2002 to 2006. He was the Chair of the Wireless Networks Group of the National Science & Technology Program for Telecommunications from 2004 to 2008, and was the Director of the Communications Engineering Program, National Science Council (NSC), R.O.C, from 2009 to 2011. He has been the Chair of the Access Technology Group of the Networked Communications Program since 2009. His current research interests are primarily in baseband technologies for OFDMbased wireless communications, cooperative communications, and cognitive radios. Dr. Wang was a recipient of the NTHU Distinguished Teaching Award in 1992, the Distinguished Teaching Award granted by the Ministry of Education, R.O.C., in 1992, the Distinguished Electrical Engineering Professor Award granted by the Chinese Institute of Electrical Engineering in 2010, and the NSC Distinguished Research Award in 2013. He received the Acer Dragon Thesis Award in 1987, the NSC Outstanding Research Awards in 1994 and 1995, the Acer Dragon Thesis Advisor Awards in 1995 and 1996, and the HDTV Academic Achievement Award from the Digital Video Industry Development Program Office, Ministry of Economic Affairs, R.O.C., in 1996. He was also the advisor on several technical works that won various awards in Taiwan, including the Outstanding Award of the 1993 Texas Instruments DSP Product Design Challenge in Taiwan, the Outstanding Award of the 1994 Contest on Design and Implementation of Microprocessor Application Systems sponsored by the Ministry of Education, R.O.C., the 1995 and 2000 Master Thesis Awards of the Chinese Institute of Electrical Engineering, etc. Dr. Wang served as an Associate Editor for the IEEE Transactions on Signal Processing from 1998 to 2000 and an Editor for Equalization for the IEEE Transactions on Communications from 1998 to 2011. He

Wireless Netw was also one of the Guest Editors for the Special Issue on Model Order Selection in Signal Processing Systems of the IEEE Journal of Selected Topics in Signal Processing. He has been recognized as an IEEE Fellow for his contributions to signal processing algorithms and architectures for digital communications. Dong-Shing Wu was born in Nantou, Taiwan, R.O.C., in 1972. He received the B.S. and M.S. degrees in electrical engineering from I-Shou Universiy, Kaohsiung, Taiwan, in 1998 and 2002, respectively. He is working toward the Ph.D. degree in communications engineering at National Tsing Hua University, Hsinchu, Taiwan. His current research interests are in signal processing algorithms and positioning/tracking techniques for wireless sensor networks.

123