Cooperative and Distributed Localization for Wireless Sensor Networks in Multipath Environments

We consider the problem of sensor localization in a wireless network in a multipath environment, where time and angle of arrival information are available at each sensor. We propose a distributed algorithm based on belief propagation, which allows sensors to cooperatively self-localize with respect to one single anchor in a multihop network. The algorithm has low overhead and is scalable. Simulations show that although the network is loopy, the proposed algorithm converges, and achieves good localization accuracy.


I. INTRODUCTION
A wireless sensor network (WSN) consists of many devices (or nodes) capable of onboard sensing, computing and communications. WSNs are used in industrial and commercial applications, such as environmental monitoring and pollution detection, control of industrial machines and home appliances, event detection, and object tracking [1]- [3]. In most applications, the data collected by the sensor nodes can only be meaningfully interpreted if it is correlated with the location of the corresponding sensors. The Global Positioning System (GPS) is widely used for localization in outdoor environments [4]. However, GPS is a costly option and is not suitable for power-limited sensor nodes in WSNs. Furthermore, GPS signals do not penetrate well to indoor environments. Therefore, alternatives to GPS localization have been widely studied [4], [5]. In a WSN, nodes whose positions are known are called "anchors". By making use of pairwise range or angle measurements between anchors and/or other sensor nodes whose positions are unknown, sensors with no access to GPS can perform self-localization. Typical techniques include the use of time-of-arrival (TOA), time-difference-of-arrival (TDOA), received-signal-strength (RSS) and/or angle-of-arrival (AOA) information in triangulating the location of a node. This is usually studied in line-of-sight (LOS) environments [6], [7].
However, LOS signals do not always exist in urban or cluttered environments, where signals usually experience multiple refections and diffractions. Such signals are referred to as nonline-of-sight (NLOS) signals and are commonly encountered in both indoor (e.g., residential buildings, offices and shopping malls) and outdoor (e.g., metropolitan and urban) environments. NLOS  extensively investigated [8]- [14], but most of the algorithms in the literature focus on locating one single sensor with several anchors. Since they require each sensor to have direct signal paths to anchors in the network, such algorithms cannot be applied in network-wide localization. On the other hand, several algorithms for network-wide localization have been proposed in the literature [5], [15]- [18]. Unfortunately, only LOS signals are considered in these algorithms.
Distributed localization algorithms for multipath environments were proposed in [19], [20], where NLOS error is modeled as a positive bias in range and angle measurements, and its statistical characteristics are inferred by numerical methods, such as bootstrap sampling in [19], and particle filters in [20]. One of the major disadvantages is that these Bayesian inference techniques require a large number of observations and are computationally expensive. Generally, the statistical model for NLOS errors depends on various factors, such as signal bandwidth, propagation medium and environment temperature. Different models including the uniform, exponential and Rayleigh distributions, have been proposed in the literature [21], [22].
Instead of modeling NLOS errors in multipath environments as random biases, geometric analysis can be applied in pairwise localization [12]- [14], where measurements of different paths are modeled using closed-form expressions, which significantly simplifies the system model. In this paper, we derive a distributed localization algorithm based on range and direction measurements at each node, and where nodes exchange information to cooperatively perform self-localization relative to a fixed reference node. We show through simulation that by exchanging limited information, all the nodes in the network can perform localization to a good accuracy. We compare the performance to that achieved without cooperation, and show that cooperation amongst neighboring nodes significantly improves the localization accuracy.
The rest of this paper is organized as follows. In Section II, we define the system model. We describe our algorithm in Section III, and provide simulation results in Section IV. In Section V, we summarize and conclude. The objective of each S i is to perform self-localization relative to S 0 .
In the following, we consider two nodes S i and S j . Similar to [14], we describe a model to relate the range and direction measurements at each node to their positions. Suppose that there are R LOS or NLOS paths between S i and S j . An example of a single-bounce scattering path is shown in Figure  1, where the signal from S j to S i is reflected at a nearby scatter, and the communication link between two nodes is assumed to be symmetric. Let d r ji be the distance measured by S i using the time-of-arrival information of the signal along the r th path from S j , and θ r ji be the corresponding angle-ofarrival information. Nodes S i and S j exchange measurements with each other, so that both nodes have the measurements {d r ij , d r ji , θ r ij , θ r ji } R r=1 . Consider the r th path between S i and S j . Given the position of S j and {d r ij , d r ji , θ r ij , θ r ji }, the position of S i cannot be determined with certainty even in the absence of measurement and communication noise. As shown in Figure 1, the estimated position for S i can be any point along the line AB. If there are multiple paths between S i and S j from non-parallel scatters, the position of S i can be found as the intersection point of two such lines. Suppose that there is no measurement noise, then a straightforward geometric consideration shows that where p A and p B are the positions of A and B respectively. A vector perpendicular to p A − p B , is Since both A and S i are on the line AB, we have n T , which can be further simplified as where We have made use of the fact that d r ij = d r ji for symmetric communication links between S i and S j in (3). We have not factored in measurement and communication noise up to this point. Let the corresponding noisy measurements be {d r ji ,θ r ji ,θ r ij }. Modeling the total effect of noise as a Gaussian random error r ji , we havẽ We assume that measurements for the R paths are such that g θr ji ,θ r ij : r = 1, . . . , R are linearly independently, otherwise some of the paths are duplicates of each other. We also assume that the noise terms r ji are i.i.d. Gaussian random variables with zero mean and variance σ 2 . Stacking the measurements from all R paths into a vector where G † ji is the Moore-Penrose pseudo-inverse of the matrix G ji . If there are more than one signal paths between nodes S i and S j , we have The posterior distribution of the node locations is given by [14] proposes a least square estimator to localize a single node with respect to a reference node. However, to localize every node in a network, it is necessary to consider the interaction between S i and all the other nodes {S j } M j=0,j =i . The MAP estimator for s i is given by (7) on top of next page. The joint posterior distribution in (7) depends on interactions amongst all the variables and is difficult to compute by brute-force integration.
In order to provide a computationally efficient algorithm to calculate the marginal distributions, we observe that the state at any sensor depends directly only on its neighboring sensors whose number is usually far less than the total number of variables. To explore such conditional independence structure, we make use of belief propagation in the following and propose an efficient algorithm which computes a set of marginal distributions from the joint posterior distribution without performing a full integration as in (7).
Remark 1: When there exists a LOS path between S i and S j , it is easy to see that |θ r ji − θ r ij | = π and d r ji = |s i − s j |, which is a special case of (3).
Remark 2: When there exists paths with multiple bounces between S i and S j , a two-step proximity detection scheme suggested in [14] can be applied to detect and discard such paths, leaving measurements from either LOS and/or singlebounce paths for processing.

PROPAGATION
We use Belief Propagation (BP) on a factor graph [23] in this paper. An example for a network with 5 nodes is shown in Figure 2. Each random variable s i is represented by a variable node (circle). The interaction between two sensors S i and S j is represented by a factor node (square) connected to both variable nodes s i and s j . We split the interaction between S i and S j into two factors f ji Since messages only flow in one direction along the edges in the factor graph, they can be broadcast by the sensor nodes.
Without loss of generality, suppose the sensor S 0 is the anchor with a known position (0, 0). For each variable s i , i ∈ {1, · · · , M }, the marginal posterior distribution m(s i ) is found by iterative belief propagation, where two kinds of messages are involved, where B i is the index set of S i 's neighboring sensors.
Therefore, setting the initial belief b i (s i ) to be the corresponding prior distribution p(s i ), beliefs (8) and messages (9) are iteratively updated at each sensor, and the estimation for s i is found by maximizing the converged belief b

A. Derivation for closed-form beliefs and messages
To derive closed-form expressions for (8) and (9), we first consider the message from the anchor S 0 to a neighboring sensor S i . Since s 0 ≡ (0, 0), its belief is a constant and can be represented as b (l) 0 (s 0 ) = δ{s 0 , (0, 0)}, where δ{·, ·} is the Krocnecker delta function. Therefore, the message from S 0 to S i will be constant over all iterations, and is given by where ν 0i = G † 0i d 0i and W 0i = σ 2 Σ 0i with Σ 0i = G † 0i (G † 0i ) T . Other the other hand, for all nodes S j other than S 0 , we set the initial belief of S j as a Gaussian distribution with zero mean and large variance, i.e., for j = 1, · · · , M , b where α is a large positive value of at least an order of magnitude larger than the dimension of the environment in which the sensor nodes are located. Let λ max ij be the largest eigenvalue of Σ ij . We assume that α ≥ 2σ 2 max i,j λ max ij . As the BP algorithm proceeds, the belief b Algorithm 1 Distributed Localization in Multi-path Environments 1: Initialization: 2: Set the position at the anchor S 0 as s 0 = (0, 0). 3: Set µ (0) i = (0, 0) and where ν  The belief of s i after the l th iteration then follows from (8). Since all the messages in the product in (8) are Gaussian distributions, we have b and µ (l) At the end of the l th iteration, sensor S i estimates its position by maximizing the belief b i (s i ) is a Gaussian distribution, the estimator for s i at the l th iteration is given byŝ i . This iterative procedure is formally given in Algorithm 1. Notice that factor nodes are virtual, and are introduced only to facilitate the derivation of the algorithm. In practice, the update is performed at each individual sensor directly.

IV. SIMULATION RESULTS
Numerical simulations are conducted to validate the effectiveness of our proposed algorithm. We consider a network   First, we consider scenarios where scatters are orthogonal. We compare the performance of cooperative and pairwise localization. The cumulative distribution functions for absolute localization error of each sensor are shown in Figure 3. Corresponding to the factor graph in Figure 2, sensors S 1 and S 2 are directly connected to the anchor. Sensors S 3 and S 4 do not have any paths to the anchor. Instead each has a NLOS path to S 1 or S 2 respectively, and a NLOS path between themselves. In pairwise localization, S 3 localizes using only measurements from S 1 , and S 4 localizes with respect to S 2 . It can be seen from Figure 3(a) that S 3 and S 4 are localized with larger errors than S 1 and S 2 , and this is because errors are accumulated over hops. In cooperative localization, S 3 and S 4 exchange information and incorporate measurements from the NLOS path between themselves. As shown in Figure 3(a), the cooperative localization achieves better performances with more than 90% of the localization errors less than 2m and all errors smaller than 3m. Moreover, results for estimation on y-coordinates are shown in Figure 3(b). It can be seen that both schemes have similar performances for sensors directly connected to the anchor (e.g., S 1 and S 2 ), and cooperation localization for S 3 and S 4 achieves better performances. The mean absolute errors for both schemes are further shown in Table I. Second, we consider scenarios where scatters are horizontal or at angle 45 • to the horizontal. As can be seen from Figure 4, cooperation among neighboring sensors improves performance on both xand ycoordinates. We also note that compared with Figure 3(b), estimation errors for y-coordinates deteriorate due to correlation between measurements on the vertical direction. On the other hand, we investigate the convergence rate for our proposed algorithm in this biorthogonal scenarios, and the result is shown in Figure 5. Simulations are also conducted when scatters are at 10 • , 20 • and 30 • to the horizontal. Similar results as in Figure 5 are obtained and hence omitted here. These numerical results suggest that even for scenarios with non-orthogonal scatters, the mean of belief at each sensor converges in the proposed algorithm.

V. CONCLUSIONS
In this paper, we propose a distributed algorithm based on belief propagation for network-wide localization in multipath environments. The proposed algorithm requires communications only between neighboring sensors, with each sensor processing only information local to itself. The proposed algorithm has low overhead and can achieve robust and scalable localization. By utilizing both TOA and AOA information of the single-bounce scattering paths, we require only one anchor in the whole network, and sensors that do not have LOS/NLOS paths to the anchor can be localized by cooperation with its neighboring sensors. Simulation results show that our proposed algorithm achieve accuracy less than 1m in a 10m×10m square area.