Sequential Uniformly Reweighted Sum-Product Algorithm for Cooperative Localization in Wireless Networks

Abstract

Graphical models have been widely applied in solving distributed inference problems in wireless networks. In this paper, we formulate the cooperative localization problem in a mobile network as an inference problem on a factor graph. Using a sequential schedule of message updates, a sequential uniformly reweighted sum-product algorithm (SURW-SPA) is developed for mobile localization problems. The proposed algorithm combines the distributed nature of belief propagation (BP) with the improved performance of sequential tree-reweighted message passing (TRW-S) algorithm. We apply the SURW-SPA to cooperative localization in both static and mobile networks, and evaluate its performance in terms of localization accuracy and convergence speed.

1. Introduction

Cooperative localization is a critical problem in wireless networks, as information collected and communicated by a wireless node is often valuable only if the node's location is known. The availability of location information can enable many effective applications in wireless networks [1–3], such as search-and-rescue, asset tracking, and indoor navigation. In cooperative localization problems, the goal of wireless nodes at unknown positions (referred to as target nodes) is to estimate their own positions by exploiting absolute position information available from a few reference nodes (referred to as anchor nodes) and relative position information obtained from measurements with neighboring target nodes. When target nodes cannot independently determine their own positions using only distance measurements with the anchors, they can communicate with the neighboring targets and cooperatively determine their positions. In general, cooperative localization can improve the localization accuracy. Therefore, high anchor density or long-range anchor transmissions are no longer required.

It is widely recognized that distributed inference methods developed for graphical models comprise a principled approach for cooperative localization in wireless networks. With graphical inference tools, the similarity between wireless networks and graphical models compels researchers to model cooperative localization problems using graphical models so that the graph-based inference algorithms, including belief propagation (BP) [4], sum-product algorithm (SPA) [5], and variational algorithms [6], can be applied to cooperative localization in wireless networks.

A number of cooperative localization algorithms have been proposed for static networks [7–12]. BP-based cooperative localization algorithm is proposed in [7]. The main advantages of BP for cooperative localization are its easy implementation in a distributed fashion and capability of providing information about location estimation uncertainties. However, BP is faced by a lack of convergence guarantees in a network with loops [13], or even if BP converges, it could provide us less accurate estimates. In [8], Savic and Zazo proposed a generalized BP based on junction tree method (GBP-JT) for sensor localization. GBP-JT converges well in networks with loops, but the price for this is unacceptable large computational cost. Another variant of BP, called tree-reweighted BP (TRW-BP), is proposed in [14]. TRW-BP has stronger convergence guarantees [15] and the potential to outperform BP. However, the performance of TRW-BP depends mainly on the choice of edge appearance probabilities (EAPs). Finding a valid collection of EAPs would require significant network overhead, which makes TRW-BP difficult to implement in a distributed manner. Recently, a distributed inference algorithm, called uniformly reweighted BP (URW-BP), is proposed in [9, 10]. It collapses the EAPs into a single scalar variable, which makes it suitable for distributed processing over wireless networks. However, similar to BP and TRW-BP, URW-BP is still not guaranteed to converge in graphs with loops.

For cooperative localization in mobile networks, repeating the static localization algorithms can provide location estimates, but this approach is not optimal due to the lack of additional information provided by the mobility of wireless nodes. Taking this information into account, some localization algorithms have been developed for mobile networks [16–23]. Wymeersch et al. in [16] gave an overview of cooperative localization approaches and developed a distributed localization algorithm based on SPA for large-scale mobile heterogeneous networks. In [17], Savic and Zazo extended the standard nonparametric BP (NBP) method for cooperative localization in mobile networks and proposed some improved techniques for localization accuracy, communication overhead, and robustness. However, in mobile localization, SPA and NBP still suffer from the problem of convergence guarantees in networks with loops. Wang et al. in [19] designed distributed scheduling algorithms with low complexity and overhead for cooperative localization networks, which improve the efficiency of localization through neighbor selection and collision control. A deep understanding of information exchange and cooperation in the network is crucial for the design of location-aware networks. Win et al. in [20] presented an exploration of cooperative network localization and navigation from a theoretical foundation to applications, covering technologies and spatiotemporal cooperative algorithms. Shen et al. in [21] introduced the notion of network navigation, a new paradigm in which mobile nodes exploit both spatial and temporal cooperation to infer their positions. They established a theoretical foundation for network navigation and determined the fundamental limits of navigation accuracy using equivalent Fisher information analysis. Moreover, Conti et al. in [22] introduced the notion of network experimentation and developed an experimentation methodology for the characterization of cooperative wireless networks in realistic environments.

In this paper, we propose a new framework for cooperative localization in mobile networks. We map a factor graph (FG) onto the time-varying network topology and develop a new variant of SPA, called sequential uniformly reweighted SPA (SURW-SPA), for mobile localization problems. In the proposed algorithm, the EAPs are set to be all equal, which make SURW-SPA distributed and cooperative. Moreover, we employ a sequential message schedule, which makes SURW-SPA converge faster and achieve higher accuracy than BP and URW-BP.

The rest of this paper is organized as follows. In Section 2, we present an FG model for the cooperative localization problem in a mobile network and provide a concise overview of BP and TRW-BP. In Section 3, we propose the SURW-SPA for mobile localization in wireless networks. We then evaluate the performance of SURW-SPA for cooperative localization in both static and mobile networks in Section 4. Finally, Section 5 provides the conclusions and future work perspective.

2. Factor Graph-Based Cooperative Localization

2.1. Problem Formulation

The self-localization problem in [24] provides an excellent example of how to convert a distributed inference problem in a wireless network into an inference problem in a graphical model. Similar to this scheme, the FG framework is used to model the cooperative localization problem in a mobile network.

Consider a graph G defined by a set of vertices $\mathcal{V}$ and a set of edges $\mathcal{E}$ (see Figure 1). Each vertex $i\in \mathcal{V}$ represents a wireless node scattered in a planar region and each edge $(k,i)\in \mathcal{E}$ represents a communication link between nodes k and i. The set $\mathcal{V}$ of wireless nodes is divided into a set of anchor nodes ${\mathcal{V}}_A$ at known positions and a set of target nodes ${\mathcal{V}}_T$ at unknown positions. In this work, the anchor nodes are static, and the target nodes can move independently from positions at time slot $t-\mathrm{1}$ to new positions at time slot t. The two-dimensional position of node i at time t is given by $x_{i,t}$ .

Figure 1

Example network with anchor nodes (black vertices), target nodes (white vertices), and their communication links (edges).

Assuming that wireless nodes can only communicate with neighboring nodes within a predefined radius R, the set ${\mathcal{E}}_t$ at time t is obtained as follows: for any $k,i\in \mathcal{V}$ , $(k,i)\in {\mathcal{E}}_t$ if, and only if, $\parallel x_{k,t}-x_{i,t}\parallel \le R$ . At time t, if $(k,i)\in {\mathcal{E}}_t$ , node i can obtain node k's current position information and a noisy measurement $z_{k,i,t}$ of its distance from node k:

$$\begin{array}{cc}& z_{k,i,t}=\parallel x_{k,t}-x_{i,t}\parallel +v_{k,i},\end{array}$$

(1)

where $v_{k,i}$ represents the measurement noise which is assumed to be a zero-mean Gaussian random variable with variance ${\sigma }_{k,i}^2$ . This measurement provides us with a likelihood function $p(z_{k,i,t}\hspace{0.17em}|\hspace{0.17em}{x}_{k,t},x_{i,t})$ between each pair of neighboring nodes $(k,i)$ .

Let ${\mathbf{x}}_t=\{x_{i,t}\hspace{0.17em}|\hspace{0.17em}i\in {\mathcal{V}}_T\}$ denote the set of the positions of target nodes at time t, and let ${\mathbf{z}}_t=\{z_{k,i,t}\hspace{0.17em}|\hspace{0.17em}(k,i)\in {\mathcal{E}}_t\}$ denote the set of distance observations between the connected nodes. Based on the following Markovian assumption [16],

$$\begin{array}{cc}& p\left(x_{i,t}\hspace{0.17em}|\hspace{0.17em}{\mathbf{x}}_{0:t-1}\right)=p\left(x_{i,t}\hspace{0.17em}|\hspace{0.17em}{x}_{i,t-1}\right),\end{array}$$

(2)

the joint probability for ${\mathbf{x}}_t$ and ${\mathbf{z}}_{1:t}$ can be written as

$$\begin{array}{l}p\left({\mathbf{x}}_t,{\mathbf{z}}_{\mathrm{1}:t}\right)\propto p({\mathbf{x}}_t,{\mathbf{z}}_t\hspace{0.17em}|\hspace{0.17em}{\mathbf{z}}_{\mathrm{1}:t-\mathrm{1}})\\ \propto p\left({\mathbf{z}}_t\hspace{0.17em}|\hspace{0.17em}{\mathbf{x}}_t\right)p\left({\mathbf{x}}_t\hspace{0.17em}|\hspace{0.17em}{\mathbf{z}}_{\mathrm{1}:t-\mathrm{1}}\right)\\ \propto {\displaystyle \prod }_{(k,i)\in {\mathcal{E}}_t}p\left(z_{k,i,t}\hspace{0.17em}|\hspace{0.17em}{x}_{k,t},x_{i,t}\right){\displaystyle \prod }_{i\in {\mathcal{V}}_T}p\left(x_{i,t}\hspace{0.17em}|\hspace{0.17em}{\mathbf{z}}_{\mathrm{1}:t-\mathrm{1}}\right),\end{array}$$

(3)

where

$$\begin{array}{cc}& p\left(x_{i,t}\hspace{0.17em}|\hspace{0.17em}{\mathbf{z}}_{\mathrm{1}:t-\mathrm{1}}\right)={\displaystyle \int }p\left(x_{i,t}\hspace{0.17em}|\hspace{0.17em}{x}_{i,t-1}\right)p\left(x_{i,t-1}\hspace{0.17em}|\hspace{0.17em}{\mathbf{z}}_{\mathrm{1}:t-\mathrm{1}}\right)d{x}_{i,t-1}.\end{array}$$

(4)

In most cooperative localization problems, the minimum mean squared error (MMSE) estimate of target positions can be determined by taking the mean of the marginal a posteriori distribution $p(x_{i,t}\hspace{0.17em}|\hspace{0.17em}{\mathbf{z}}_{\mathrm{1}:t})$ of the variable $x_{i,t}$ . Therefore, our goal is to calculate the marginal a posterior distribution $p(x_{i,t}\hspace{0.17em}|\hspace{0.17em}{\mathbf{z}}_{\mathrm{1}:t})$ for all target nodes $i\in {\mathcal{V}}_T$ :

$$\begin{array}{l}p\left(x_{i,t}\hspace{0.17em}|\hspace{0.17em}{\mathbf{z}}_{\mathrm{1}:t}\right)\propto {\displaystyle \int }p({\mathbf{x}}_t,{\mathbf{z}}_{\mathrm{1}:t})d{x}_{\setminus \left\{i\right\},t}\\ \propto {\displaystyle \int }{\displaystyle \prod }_{(k,i)\in {\mathcal{E}}_t}p\left(z_{k,i,t}\hspace{0.17em}|\hspace{0.17em}{x}_{k,t},x_{i,t}\right)\\ \hspace{0.5em}\times {\displaystyle \prod }_{j\in {\mathcal{V}}_T}p\left(x_{j,t}\hspace{0.17em}|\hspace{0.17em}{\mathbf{z}}_{1:t-\mathrm{1}}\right)d{x}_{\setminus \left\{i\right\},t},\end{array}$$

(5)

where $x_{\setminus \{i\},t}$ denotes the positions of all the target nodes at time t except $x_{i,t}$ .

Equation (3) expresses a factorization of a joint probability distribution which is suitable for representation by an FG [5]. Let

$$\begin{array}{cc}& f_{i,t}\left(x_{i,t-1},x_{i,t}\right)=p\left(x_{i,t}\hspace{0.17em}|\hspace{0.17em}{x}_{i,t-1}\right),\end{array}$$

(6)

$$\begin{array}{cc}& f_{k,i,t}\left(x_{k,t},x_{i,t}\right)=p\left(z_{k,i,t}\hspace{0.17em}|\hspace{0.17em}{x}_{k,t},x_{i,t}\right).\end{array}$$

(7)

For each wireless node i, we draw a variable node, representing node i's position $x_{i,t}$ , and an edge, connecting the variable node $x_{i,t}$ with a factor node when the variable $x_{i,t}$ appears in the corresponding factor. Similar to [24], the variable node of an anchor k is only connected to the variable node of a target i via $f_{k,i,t}$ because anchor nodes need not estimate their positions and therefore may disregard messages from neighboring nodes. The FG representation of Figure 1 at time t is shown in Figure 2.

Figure 2

The FG representation of Figure 1 at time t.

2.2. Message Passing Algorithms

Given an FG of $p({\mathbf{x}}_t,{\mathbf{z}}_{\mathrm{1}:t})$ , the marginal a posteriori distribution $p(x_{i,t}\hspace{0.17em}|\hspace{0.17em}{\mathbf{z}}_{\mathrm{1}:t})$ of target node $i\in {\mathcal{V}}_T$ can be estimated via message passing algorithms. Two common message passing algorithms adapted to FGs as depicted in Figure 2 are BP and TRW-BP.

2.2.1. Belief Propagation

Let ${\mathcal{N}}_i$ denote the set of neighboring nodes of the node i. The message from variable node $x_{k,t}$ to factor node $f_{k,i,t}(x_{k,t},x_{i,t})$ can be written as

$$\begin{array}{cc}& m_{x_{k,t}\to f_{k,i,t}}\left(x_{k,t}\right)\propto m_{f_{k,t}\to x_{k,t}}\left(x_{k,t}\right){\displaystyle \prod }_{j\in {\mathcal{N}}_k\setminus \left\{i\right\}}{m}_{f_{j,k,t}\to x_{k,t}}\left(x_{k,t}\right),\end{array}$$

(8)

and messages from factor nodes to variable node $x_{i,t}$ are given by

$$\begin{array}{cc}& m_{f_{i,t}\to x_{i,t}}\left(x_{i,t}\right)\propto {\displaystyle \int }{f}_{i,t}\left(x_{i,t-1},x_{i,t}\right)m_{x_{i,t-1}\to f_{i,t}}\left(x_{i,t-1}\right)d{x}_{i,t-1},\end{array}$$

(9)

$$\begin{array}{cc}& m_{f_{k,i,t}\to x_{i,t}}\left(x_{i,t}\right)\propto {\displaystyle \int }{f}_{k,i,t}\left(x_{k,t},x_{i,t}\right)m_{x_{k,t}\to f_{k,i,t}}\left(x_{k,t}\right)d{x}_{k,t}.\end{array}$$

(10)

Finally, the so-called belief, $b_{i,t}(x_{i,t})$ , which is an approximation of the a posteriori marginal $p(x_{i,t}\hspace{0.17em}|\hspace{0.17em}{\mathbf{z}}_{1:t})$ , takes the form

$$\begin{array}{cc}& b_{i,t}\left(x_{i,t}\right)\propto m_{f_{i,t}\to x_{i,t}}\left(x_{i,t}\right){\displaystyle \prod }_{k\in {\mathcal{N}}_i}{m}_{f_{k,i,t}\to x_{i,t}}\left(x_{i,t}\right).\end{array}$$

(11)

2.2.2. Tree-Reweighted Belief Propagation

In TRW-BP, the message from variable node $x_{k,t}$ to factor node $f_{k,i,t}(x_{k,t},x_{i,t})$ can be written as

$$\begin{array}{l}{m}_{x_{k,t}\to f_{k,i,t}}\left(x_{k,t}\right)\propto m_{f_{k,t}\to x_{k,t}}\left(x_{k,t}\right)m_{f_{i,k,t}\to x_{k,t}}^{{\rho }_{i,k}-1}\left(x_{k,t}\right)\\ \times {\displaystyle \prod }_{j\in {\mathcal{N}}_k\setminus \left\{i\right\}}{m}_{f_{j,k,t}\to x_{k,t}}^{{\rho }_{j,k}}\left(x_{k,t}\right),\end{array}$$

(12)

where ${\rho }_{k,i}={\rho }_{i,k}$ is the EAP of the factor node $f_{k,i,t}(x_{k,t},x_{i,t})$ . The message from factor node $f_{k,i,t}(x_{k,t},x_{i,t})$ to variable node $x_{i,t}$ is given by

$$\begin{array}{cc}& m_{f_{k,i,t}\to x_{i,t}}\left(x_{i,t}\right)\propto {\displaystyle \int }{f}_{k,i,t}^{1/{\rho }_{k,i}}\left(x_{k,t},x_{i,t}\right)m_{x_{k,t}\to f_{k,i,t}}\left(x_{k,t}\right)d{x}_{k,t}.\end{array}$$

(13)

The belief $b_{i,t}(x_{i,t})$ takes the form

$$\begin{array}{cc}& b_{i,t}\left(x_{i,t}\right)\propto m_{f_{i,t}\to x_{i,t}}\left(x_{i,t}\right){\displaystyle \prod }_{k\in {\mathcal{N}}_i}{m}_{f_{k,i,t}\to x_{i,t}}^{{\rho }_{k,i}}\left(x_{i,t}\right).\end{array}$$

(14)

Equations (12)–(14) are iterated until the beliefs converge. TRW-BP involves a high-dimensional optimization problem over the EAPs. Finding a valid collection of EAPs would require significant network overhead, even for small networks. This makes TRW-BP unsuitable for distributed inference problems (e.g., over wireless networks). Note that when an FG is loop-free, ${\rho }_{k,i}=\mathrm{1}$ , for all factor nodes. BP and TRW-BP are equivalent and provide the exact marginals. When an FG contains loops, ${\rho }_{k,i}<\mathrm{1}$ , for at least one factor node. BP and TRW-BP are not guaranteed to yield the true marginal posteriors or even to converge at all.

3. Sequential Uniformly Reweighted Sum-Product Algorithm

In this section, we formulate a new variant of SPA to be used with FGs for cooperative localization in wireless networks. As depicted in Figure 2, there exists a factor node for each pair of neighboring wireless nodes, for which a distance measurement is available. Therefore, for cooperative localization problems, we restrict our attention to FGs with degree-two factor nodes.

3.1. Uniform Edge Appearance Probability

For cooperative localization in wireless networks, the main problem of TRW-BP is that, in its original form, TRW-BP is not suitable for a distributed implementation. In order to solve this problem, motivated by [9], we reduce the degrees of freedom in TRW-BP to a single scalar variable. In other words, the EAPs in (12)–(14) are set to be all equal (and denoted by ρ). This can take advantage of the local nature of BP and the improved performance of TRW-BP. Therefore, we can easily obtain a practical alternative to TRW-BP for cooperative localization problems, which is called uniformly reweighted BP (URW-BP). The message update rules of URW-BP can be expressed as follows.

Message from variable node $x_{k,t}$ to factor node $f_{k,i,t}(x_{k,t},x_{i,t})$ is

$$\begin{array}{l}{m}_{x_{k,t}\to f_{k,i,t}}\left(x_{k,t}\right)\propto m_{f_{k,t}\to x_{k,t}}\left(x_{k,t}\right)m_{f_{i,k,t}\to x_{k,t}}^{\rho -1}\left(x_{k,t}\right)\\ \times {\displaystyle \prod }_{j\in {\mathcal{N}}_k\setminus \left\{i\right\}}{m}_{f_{j,k,t}\to x_{k,t}}^{\rho }\left(x_{k,t}\right).\end{array}$$

(15)

Message from factor node $f_{k,i,t}(x_{k,t},x_{i,t})$ to variable node $x_{i,t}$ is

$$\begin{array}{cc}& m_{f_{k,i,t}\to x_{i,t}}\left(x_{i,t}\right)\propto {\displaystyle \int }{f}_{k,i,t}^{1/\rho }\left(x_{k,t},x_{i,t}\right)m_{x_{k,t}\to f_{k,i,t}}\left(x_{k,t}\right)d{x}_{k,t}.\end{array}$$

(16)

Belief of variable $x_{i,t}$ is

$$\begin{array}{cc}& b_{i,t}\left(x_{i,t}\right)\propto m_{f_{i,t}\to x_{i,t}}\left(x_{i,t}\right){\displaystyle \prod }_{k\in {\mathcal{N}}_i}{m}_{f_{k,i,t}\to x_{i,t}}^{\rho }\left(x_{i,t}\right).\end{array}$$

(17)

As a special case, URW-BP can revert to BP under suitable choice of ρ; that is, $\rho =1$ . In general, URW-BP is not guaranteed to outperform TRW-BP. However, there are some sufficient, though not necessary conditions, under which URW-BP corresponds to optimized TRW-BP. The work in [14] points out that, for symmetric factorizations with only pairwise interactions, the optimal EAPs in TRW-BP are uniform and can be written as ${\rho }_{\text{opt}}=(N-1)/L$ , where $N=\left|\mathcal{V}\right|$ and $L=\left|\mathcal{E}\right|$ . Introducing $n_d$ as the number of pairwise interactions in which each variable is involved, a simple counting argument yields $n_d\approx 2L/N$ , so that

$$\begin{array}{cc}& {\rho }_{\text{opt}}\approx \min \left(\mathrm{1},\frac{2}{n_d}\left(1-\frac{1}{N}\right)\right).\end{array}$$

(18)

Note that, for trees, $L=N-1$ , so that $n_d\approx \mathrm{2}$ , with corresponding ${\rho }_{\text{opt}}=\mathrm{1}$ . However, symmetric factorizations are not interesting from a practical perspective. We expect that URW-BP can perform close to optimized TRW-BP as long as the factorization exhibits sufficient symmetry or when the factor graph is sufficiently tree-like. In practice, the best value of ρ will depend on the strength of the interactions between variables. An empirical approach for finding optimal EAP is considered in the following section. Moreover, similar to BP and TRW-BP, URW-BP is still not guaranteed to converge in graphs with loops.

3.2. Message Schedule

In FGs without loops (i.e., trees), BP is guaranteed to converge and provide us with exact marginals. However, in FGs with loops, there is no such guarantee. We can only extend BP, which becomes iterative. The computed belief is no longer exactly equal to the corresponding marginal a posteriori distribution. Fortunately, in FGs with loops, there are a lot of possible update orders in which messages are computed (also known as message schedules). Each message schedule has a strong influence on the convergence of message passing and even potentially the quality of the converged solution. Therefore, choosing a proper update schedule turns out to be very important in deriving a cooperative localization algorithm.

Meltzer et al. in [25] presented a unifying view of convergent message passing algorithms and pointed out that a nonconvergent message passing algorithm becomes convergent when the right update order is used. Specifically, they proved that Kolmogorov's TRW-S algorithm [26] is guaranteed to converge and differs from TRW-BP only in the scheduling of messages. As discussed in [26], for an efficient implementation of TRW-S algorithm, one needs to choose the ordering of nodes $c(·)$ , that is, mapping of nodes in $\mathcal{V}$ onto the set $\{\mathrm{1,2},\dots ,\left|\mathcal{V}\right|\}$ , and the chains which are monotonic with respect to the node ordering $c(·)$ . Here, monotonic chains are defined as follows: given an ordering of the nodes in a graph, a set of chains is monotonic if the order of nodes in the chain respects the given ordering. TRW-S algorithm uses the sequential schedule of updating messages and follows the node ordering first forward and then backward.

In general, good node ordering should allow long monotonic chains. However, this ordering would require significant network overhead. In practice, the sequential schedule is robust to small reordering [7]. Thus, we randomly assign an order to the nodes. Automatic selection of node ordering for an arbitrary graph is an open question which is not addressed in this paper. Given an ordering of the nodes, we choose a monotonic chain in a greedy manner such that it is not possible to expend it. In other words, for the first node i in the monotonic chain, there are no edges $(k,i)$ with $c(k)<c(i)$ and, for the last node t, there are no edges $(u,t)$ with $c(u)>c(t)$ . After that, we remove corresponding edges from the graph and repeat the procedure until no edges are left.

3.3. Sequential Uniformly Reweighted Sum-Product Algorithm for Mobile Localization

In mobile localization problems, our goal is to calculate the marginal a posteriori distribution $p(x_{i,t}\hspace{0.17em}|\hspace{0.17em}{\mathbf{z}}_{1:t})$ for all target nodes $i\in {\mathcal{V}}_T$ . Given $p(x_{i,t-1}\hspace{0.17em}|\hspace{0.17em}{\mathbf{z}}_{1:t-1})$ , we can determine $p(x_{i,t}\hspace{0.17em}|\hspace{0.17em}{\mathbf{z}}_{\mathrm{1}:t})$ as follows: (i) a prediction operation, during which we determine the distribution $p(x_{i,t}\hspace{0.17em}|\hspace{0.17em}{\mathbf{z}}_{1:t-1})$ , given all measurements before time t, according to (4); (ii) a correction operation, in which we account for the new measurements ${\mathbf{z}}_t$ to calculate $p(x_{i,t}\hspace{0.17em}|\hspace{0.17em}{\mathbf{z}}_{\mathrm{1}:t})$ , according to (5). Therefore, at every time t, we have the marginal a posteriori distribution $p(x_{i,t}\hspace{0.17em}|\hspace{0.17em}{\mathbf{z}}_{\mathrm{1}:t})$ of the variable $x_{i,t}$ given all the measurements up to and including time t.

In this section, motivated by [9, 26], we propose a sequential uniformly reweighted sum-product algorithm (SURW-SPA) for mobile localization problems in wireless networks, which combines the distributed nature of URW-BP with the convergence of TRW-S. In SURW-SPA, we set the EAPs to be all equal and employ a sequential schedule of message updates, in which each node in turn transmits a message to all its neighbors. SURW-SPA for mobile localization is given in Algorithm 1.

Algorithm 1: SURW-SPA for mobile localization at time $\mathrm{t}$ .

(1)    given incoming messages ${\mathrm{m}}_{{\mathrm{x}}_{\mathrm{i},\mathrm{t}-\mathrm{1}}\to {\mathrm{f}}_{\mathrm{i},\mathrm{t}}}({\mathrm{x}}_{\mathrm{i},\mathrm{t}-\mathrm{1}})$ , $\forall \mathrm{i}\in {\mathcal{V}}_{\mathrm{T}}$ .

Prediction phase:

(2)    nodes   $\mathrm{i}=\mathit{1}$ to N  in parallel

(3)    compute new message ${\mathrm{m}}_{{\mathrm{f}}_{\mathrm{i},\mathrm{t}}\to {\mathrm{x}}_{\mathrm{i},\mathrm{t}}}({\mathrm{x}}_{\mathrm{i},\mathrm{t}})$ using (9)

       $\begin{array}{c}{\mathrm{m}}_{{\mathrm{f}}_{\mathrm{i},\mathrm{t}}\to {\mathrm{x}}_{\mathrm{i},\mathrm{t}}}\left({\mathrm{x}}_{\mathrm{i},\mathrm{t}}\right)\propto \int {\mathrm{f}}_{\mathrm{i},\mathrm{t}}\left({\mathrm{x}}_{\mathrm{i},\mathrm{t}-\mathrm{1}},{\mathrm{x}}_{\mathrm{i},\mathrm{t}}\right){\mathrm{m}}_{{\mathrm{x}}_{\mathrm{i},\mathrm{t}-\mathrm{1}}\to {\mathrm{f}}_{\mathrm{i},\mathrm{t}}}\left({\mathrm{x}}_{\mathrm{i},\mathrm{t}-\mathrm{1}}\right)\mathrm{d}{\mathrm{x}}_{\mathrm{i},\mathrm{t}-\mathrm{1}}\\ \phantom{{\mathrm{m}}_{{\mathrm{f}}_{\mathrm{i},\mathrm{t}}\to {\mathrm{x}}_{\mathrm{i},\mathrm{t}}}\left({\mathrm{x}}_{\mathrm{i},\mathrm{t}}\right)}\propto \int \mathrm{p}\left({\mathrm{x}}_{\mathrm{i},\mathrm{t}}\hspace{0.17em}|\hspace{0.17em}{\mathrm{x}}_{\mathrm{i},\mathrm{t}-\mathrm{1}}\right){\mathrm{m}}_{{\mathrm{x}}_{\mathrm{i},\mathrm{t}-\mathrm{1}}\to {\mathrm{f}}_{\mathrm{i},\mathrm{t}}}\left({\mathrm{x}}_{\mathrm{i},\mathrm{t}-\mathrm{1}}\right)\mathrm{d}{\mathrm{x}}_{\mathrm{i},\mathrm{t}-\mathrm{1}}\end{array}$ .           (*)

(4)    end parallel

Correction phase:

(5)    nodes   $\mathrm{i}=\mathit{1}$ to N  in parallel

(6)    obtain distance observations ${\mathrm{z}}_{\mathrm{k},\mathrm{i},\mathrm{t}}$ to neighboring nodes.

(7)    initialize ${\mathrm{b}}_{\mathrm{i},\mathrm{t}}^{(\mathrm{0})}({\mathrm{x}}_{\mathrm{i},\mathrm{t}})={\mathrm{m}}_{{\mathrm{f}}_{\mathrm{i},\mathrm{t}}\to {\mathrm{x}}_{\mathrm{i},\mathrm{t}}}({\mathrm{x}}_{\mathrm{i},\mathrm{t}})$ and ${\mathrm{m}}_{{\mathrm{f}}_{\mathrm{k},\mathrm{i},\mathrm{t}}\to {\mathrm{x}}_{\mathrm{i},\mathrm{t}}}^{(\mathrm{0})}({\mathrm{x}}_{\mathrm{i},\mathrm{t}})=\mathrm{1}$ , $\mathrm{k}\in {\mathcal{N}}_{\mathrm{i}}$ .

(8)    end parallel

(9)    for   $\mathrm{l}=\mathit{1}$ to $N_{\text{iter}}$   do  {iteration index}

(10)  nodes   $\mathrm{i}=\mathit{1}$ to N  in the sequence of increasing   $\mathrm{c}(\mathrm{i})$

(11)    receive ${\mathrm{b}}_{\mathrm{k},\mathrm{t}}^{(\mathrm{l})}({\mathrm{x}}_{\mathrm{k},\mathrm{t}})$ from neighbors $\mathrm{k}\in {\mathcal{N}}_{\mathrm{i}}$ .

(12)   compute new messages ${\mathrm{m}}_{{\mathrm{f}}_{\mathrm{k},\mathrm{i},\mathrm{t}}\to {\mathrm{x}}_{\mathrm{i},\mathrm{t}}}^{(\mathrm{l})}({\mathrm{x}}_{\mathrm{i},\mathrm{t}})$ for $\mathrm{c}(\mathrm{k})<\mathrm{c}(\mathrm{i})$ , $\mathrm{k}\in {\mathcal{N}}_{\mathrm{i}}$ using (21)

         ${\mathrm{m}}_{{\mathrm{f}}_{\mathrm{k},\mathrm{i},\mathrm{t}}\to {\mathrm{x}}_{\mathrm{i},\mathrm{t}}}^{(\mathrm{l})}({\mathrm{x}}_{\mathrm{i},\mathrm{t}})\propto \int {\mathrm{f}}_{\mathrm{k},\mathrm{i},\mathrm{t}}^{\mathrm{1}/\mathrm{\rho }}({\mathrm{x}}_{\mathrm{k},\mathrm{t}},{\mathrm{x}}_{\mathrm{i},\mathrm{t}})\frac{{\mathrm{b}}_{\mathrm{k},\mathrm{t}}^{(\mathrm{l})}({\mathrm{x}}_{\mathrm{k},\mathrm{t}})}{{\mathrm{m}}_{{\mathrm{f}}_{\mathrm{i},\mathrm{k},\mathrm{t}}\to {\mathrm{x}}_{\mathrm{k},\mathrm{t}}}^{(\mathrm{l}-\mathrm{1})}({\mathrm{x}}_{\mathrm{k},\mathrm{t}})}\mathrm{d}{\mathrm{x}}_{\mathrm{k},\mathrm{t}}$ .           (**)

(13)   compute new marginal estimate ${\mathrm{b}}_{\mathrm{i},\mathrm{t}}^{(\mathrm{l})}({\mathrm{x}}_{\mathrm{i},\mathrm{t}})$ using (19)

      ${\mathrm{b}}_{\mathrm{i},\mathrm{t}}^{(\mathrm{l})}\left({\mathrm{x}}_{\mathrm{i},\mathrm{t}}\right)\propto {\mathrm{m}}_{{\mathrm{f}}_{\mathrm{i},\mathrm{t}}\to {\mathrm{x}}_{\mathrm{i},\mathrm{t}}}\left({\mathrm{x}}_{\mathrm{i},\mathrm{t}}\right)\prod _{\mathrm{c}(\mathrm{k})>\mathrm{c}(\mathrm{i}),\mathrm{k}\in {\mathcal{N}}_{\mathrm{i}}}{\mathrm{m}}_{{\mathrm{f}}_{\mathrm{k},\mathrm{i},\mathrm{t}}\to {\mathrm{x}}_{\mathrm{i},\mathrm{t}}}^{(\mathrm{l}-\mathrm{1})}{\left({\mathrm{x}}_{\mathrm{i},\mathrm{t}}\right)}^{\mathrm{\rho }}\prod _{\mathrm{c}(\mathrm{k})<\mathrm{c}(\mathrm{i}),\mathrm{k}\in {\mathcal{N}}_{\mathrm{i}}}{\mathrm{m}}_{{\mathrm{f}}_{\mathrm{k},\mathrm{i},\mathrm{t}}\to {\mathrm{x}}_{\mathrm{i},\mathrm{t}}}^{(\mathrm{l})}{\left({\mathrm{x}}_{\mathrm{i},\mathrm{t}}\right)}^{\mathrm{\rho }}$     (***)

(14)   broadcast ${\mathrm{b}}_{\mathrm{i},\mathrm{t}}^{(\mathrm{l})}({\mathrm{x}}_{\mathrm{i},\mathrm{t}})$ .

(15)  end sequence

(16)    reverse the ordering: set $\mathrm{c}(\mathrm{i})=\mathrm{N}+\mathrm{1}-\mathrm{c}(\mathrm{i})$ .

(17)  end for

(18)  nodes   $\mathrm{i}=\mathit{1}$ to N  in parallel

(19)    determine outgoing message: ${\mathrm{m}}_{{\mathrm{x}}_{\mathrm{i},\mathrm{t}}\to {\mathrm{f}}_{\mathrm{i},\mathrm{t}+\mathrm{1}}}({\mathrm{x}}_{\mathrm{i},\mathrm{t}})={\mathrm{b}}_{\mathrm{i},\mathrm{t}}^{(N_{\text{iter}})}({\mathrm{x}}_{\mathrm{i},\mathrm{t}})$ .

(20) end parallel

Naturally, one can assume that the messages should be exchanged between each pair of the neighboring nodes. However, this produces a huge communication overhead since each node would need to send one message to each of its neighbors. In order to take advantage of the broadcast in wireless networks, it is more convenient to compute the beliefs at every iteration l and use them to update the messages. This leads to an equivalent form of URW-BP: by substituting (15) and (17) into (16), we can easily find that the belief update and message update rules of URW-BP are, respectively, given by

$$\begin{array}{cc}& b_{i,t}^{\left(l\right)}\left(x_{i,t}\right)\propto m_{f_{i,t}\to x_{i,t}}\left(x_{i,t}\right){\displaystyle \prod }_{k\in {\mathcal{N}}_i}{m}_{f_{k,i,t}\to x_{i,t}}^{\left(l\right)}{\left(x_{i,t}\right)}^{\rho },\end{array}$$

(19)

$$\begin{array}{cc}& m_{x_{k,t}\to f_{k,i,t}}^{\left(l\right)}\left(x_{k,t}\right)\propto \frac{b_{k,t}^{\left(l-1\right)}\left(x_{k,t}\right)}{m_{f_{i,k,t}\to x_{k,t}}^{\left(l-1\right)}\left(x_{k,t}\right)},\end{array}$$

(20)

$$\begin{array}{cc}& m_{f_{k,i,t}\to x_{i,t}}^{\left(l\right)}\left(x_{i,t}\right)\propto {\displaystyle \int }{f}_{k,i,t}^{1/\rho }\left(x_{k,t},x_{i,t}\right)\frac{b_{k,t}^{\left(l-1\right)}\left(x_{k,t}\right)}{m_{f_{i,k,t}\to x_{k,t}}^{\left(l-1\right)}\left(x_{k,t}\right)}d{x}_{k,t}.\end{array}$$

(21)

From (21), we can see that only the belief of node k (source node) is not available at node i (destination node) and therefore has to be transmitted. Thus, each node only needs to broadcast its belief instead of $n_d$ messages (where $n_d$ is the node degree). This is paid by increased computational cost since the message $m_{f_{i,k,t}\to x_{k,t}}^{(l-1)}(x_{k,t})$ from the previous iteration must be computed twice: once at the source node and once at the destination node. However, it is already well known that the communication is much more energy-consuming than computation.

Initially, target nodes have no information about their positions, so that the message $m_{x_{i,0}\to f_{i,1}}(x_{i,0})$ can be represented by a uniform a priori distribution, for all $i\in {\mathcal{V}}_T$ . Anchor nodes have perfect location information, so that $b_{i,t}^{(l)}(x_{i,t})$ are Dirac delta functions, for all $l,t$ , $i\in {\mathcal{V}}_A$ . Also, anchor nodes disregard the messages from their neighboring nodes, since they need not estimate their positions. Then, SURW-SPA can be performed by following the ordering of nodes first forward and then backward, updating each time only the messages in the direction of the scan until a preset number of iterations are attained. At any time slot t, each target i can determine ${\widehat{x}}_{i,t}$ , the MMSE estimate of its own position, by taking the mean of its local message $m_{x_{i,t}\to f_{i,t+1}}(x_{i,t})$ .

4. Evaluation

To verify the performance of the SURW-SPA, in this section, we consider the cooperative localization problem in both static and mobile networks.

4.1. Static Networks

In the first set of experiments, we consider a static network with 6 anchor nodes and 6 target nodes, in a 100 m by 100 m deployment area. All the nodes are positioned in a structured manner as depicted in Figure 3, in which each anchor is connected exactly to one target. Each node has a communication link to all other nodes within a range of 30 m. For simplicity, we assume that nodes k and i make the same distance observation $z_{ki}=z_{ik}$ and that the measurement noise variance is equal for all nodes; that is, ${\sigma }_{k,i}^2={\sigma }_v^2$ . Here, we set ${\sigma }_v=\mathrm{1}$  m. As the cooperative localization problem is nonlinear and potentially non-Gaussian, exact message representation and updating are not tractable. Therefore, we use a particle-based version of SURW-SPA and the messages are represented by 500 particles [27]. The simulation results of BP and URW-BP are also provided for comparison. All simulation results are averaged over 100 Monte Carlo runs.

Figure 3

Example of 12-node network with loops.

In order to determine the optimal value of ρ for SURW-SPA and URW-BP, Figure 4 depicts the estimated mean localization error of SURW-SPA and URW-BP as a function of ρ after 10 iterations. We can easily observe that $\rho =1$ does not yield the best performance and the global minimum in the mean localization error is achieved by $\rho =0.5$ for SURW-SPA and URW-BP, which is the same as the theoretical value computed according to (18). Moreover, when $\rho =0.3~1$ , SURW-SPA provides better performance than URW-BP. We can also find that, with a wide range of ρ (in this case, 0.2~1), SURW-SPA outperforms standard BP (corresponding to URW-BP with $\rho =1$ ). That means that we can even use a coarse approximation of the optimal ρ. In the following experiments, we will use the optimal value of ρ for SURW-SPA and URW-BP.

Figure 4

Estimated mean localization error of SURW-SPA and URW-BP as a function of ρ in a static network with 6 anchor nodes and 6 target nodes.

Figure 5 shows the estimated mean localization error of SURW-SPA, URW-BP, and BP as a function of the iteration index averaged over 100 Monte Carlo runs. We can observe that the estimated mean localization error of SURW-SPA does not change significantly after 3 iterations, whereas URW-BP and BP require 5 iterations to converge. Furthermore, it is seen that the mean localization error of URW-BP and BP stabilizes at 1.81 and 2.14, respectively, while the result of SURW-SPA reaches 1.69. Based on the above observations, it is easy to conclude that SURW-SPA requires fewer iterations to achieve higher accuracy than URW-BP and BP.

Figure 5

Estimated mean localization error of SURW-SPA, URW-BP, and BP as a function of the iteration index in a static network with 6 anchor nodes and 6 target nodes.

Another comparison is offered in Figure 6, showing the estimated cumulative localization error probability of SURW-SPA, URW-BP, and BP as a function of allowable error. We compare the three localization algorithms with 5 iterations, which are required to converge by URW-BP and BP. It can be observed that, for an allowable error of 5 m, nearly 97% of the target nodes are well localized for BP. URW-BP can increase the percentage to some extent, while SURW-SPA offers additional performance gains and the cumulative localization error probability reaches one. At an allowable error of 3 m, 94% of the targets are well localized for SURW-SPA. The cumulative localization error probability drops to 87% for URW-BP and is further reduced to 78% for BP. It is worthy to note that for this scenario SURW-SPA converges after only 3 iterations and achieves better performance than URW-BP and BP, which require 5 iterations to converge.

Figure 6

Estimated cumulative localization error probability of SURW-SPA, URW-BP, and BP as a function of allowable error in a static network with 6 anchor nodes and 6 target nodes.

4.2. Mobile Networks

In contrast to previous experiments, we now consider a mobile network. We assume that there are 13 anchor nodes and 100 target nodes, deployed in a 100 m by 100 m area. Anchors are static, while targets are mobile. Static anchors are positioned in a grid topology similar to the one described in [24]. Target nodes move independently with respect to one another and from time slot to time slot according to the random walk mobility model [28]. In this mobility model, each target moves from its current position to a new position by updating its speed and direction as follows:

$$\begin{array}{cc}& s_{i,t}=\stackrel{-}{s}+v_s,\end{array}$$

(22)

$$\begin{array}{cc}& {\theta }_{i,t}=\stackrel{-}{\theta }+v_{\theta },\end{array}$$

(23)

where $s_{i,t}$ and ${\theta }_{i,t}$ are the new speed and direction of target i at time slot t; $\stackrel{-}{s}$ and $\stackrel{-}{\theta }$ are constants representing the mean value of speed and direction; $v_s$ and $v_{\theta }$ are random variables from a Gaussian distribution. In the following experiments, $v_s$ and $v_{\theta }$ are chosen from a random Gaussian distribution with mean equal to zero and standard deviation equal to one.

To ensure that the targets are always within the deployment area, the mean direction variable $\stackrel{-}{\theta }$ is modified when the targets move within a certain distance of an edge. At time $t=\mathrm{0}$ , each target is assumed to have perfect knowledge of its position, so that the a priori distribution of each target is a Dirac delta function. We use the following parameters: time interval is 1 second, tracking period is 20 seconds, the value of $\stackrel{-}{s}$ is fixed at 2 m/s, the value of $\stackrel{-}{\theta }$ is initially 90 degrees but changes over time according to the edge proximity of targets, communication radius is 20 m, standard deviation of the zero-mean Gaussian noise for the distance observation is 1 m, and the number of particles for messages is 500. Finally, all simulation results represent the average over 100 Monte Carlo runs.

Figure 7 shows the estimated mean localization error of SURW-SPA and URW-BP as a function of ρ after 10 iterations in a mobile network with 13 static anchors and 100 mobile targets. As can be seen, the optimal value of ρ for SURW-SPA is 0.3 and for URW-BP is 0.5. With the same value of ρ, SURW-SPA provides better performance than URW-BP. Furthermore, when $\rho =0.1~1$ , SURW-SPA consistently performs better than BP. The optimal value of ρ for SURW-SPA and URW-BP will be used in the following experiments.

Figure 7

Estimated mean localization error of SURW-SPA and URW-BP as a function of ρ in a mobile network with 13 static anchors and 100 mobile targets.

For an investigation of the convergence performance, we refer to Figure 8 which depicts the estimated mean localization error as a function of the iteration index in the mobile network. We observe the similar results as shown in Figure 5 for a static network. SURW-SPA requires only 2 iterations to converge, whereas URW-BP and BP both need 6 iterations until convergence. That means that SURW-SPA can converge faster than URW-BP and BP in mobile networks. This is a critical point for localization algorithm design, since more iterations correspond to an increased delay in determining target nodes' positions. This makes SURW-SPA more suitable for real-time applications. Moreover, we can also see that the converged solution of SURW-SPA is better than the results of URW-BP and BP.

Figure 8

Estimated mean localization error of SURW-SPA, URW-BP, and BP as a function of the iteration index in a mobile network with 13 static anchors and 100 mobile targets.

Based on the above observations, we will analyze the localization accuracy of SURW-SPA. Figure 9 shows the evolution of the estimated mean localization error as a function of time in a mobile network with 13 static anchors and 100 mobile targets. The results of URW-BP and BP are also depicted for comparison. As shown in Figure 9, SURW-SPA achieves small localization errors, ranging from 0.77 to 2.32. At all time slots, SURW-SPA consistently outperforms BP. Moreover, except for $t=\mathrm{20}$ , SURW-SPA provides smaller localization errors than URW-BP. At $t=\mathrm{20}$ , SURW-SPA performs worse than URW-BP, due to the fact that target nodes move independently according to the random walk mobility model. Some targets move in close proximity to the edge of the deployment area. Therefore, these targets have too few distance observations from their neighbors and cannot unambiguously determine their positions.

Figure 9

Estimated mean localization error of SURW-SPA, URW-BP, and BP as a function of time in a mobile network with 13 static anchors and 100 mobile targets.

Finally, a different view is offered in Figure 10, showing the estimated cumulative localization error probability as a function of allowable error. It can be seen that, by using the SURW-SPA, all targets but only a few are localized with high accuracy. The curve of SURW-SPA stabilizes at the value lower than one. At an allowable error of 5 m, 99% of the targets are well localized for SURW-SPA. We also observe that URW-BP and BP exhibit significant performance degradation, as compared with the curve of SURW-SPA. Using the uniform EAP and the sequential message schedule, SURW-SPA can converge faster and achieve higher accuracy than URW-BP and BP.

Figure 10

Estimated cumulative localization error probability of SURW-SPA, URW-BP, and BP as a function of allowable error in a mobile network with 13 static anchors and 100 mobile targets.

5. Conclusion

A new framework has been proposed for cooperative localization in mobile networks. The FG is introduced to model the mobile localization problems in wireless networks. A novel variant of SPA, called sequential uniformly reweighted SPA (SURW-SPA), is developed by employing a sequential message schedule and by reducing the EAPs to one scalar tuning parameter (i.e., the uniform EAP). The proposed algorithm combines the distributed nature of BP with the improved performance of TRW-S. Through Monte Carlo simulations, we have evaluated the performance of SURW-SPA in both static and mobile networks. Simulation results show that SURW-SPA can converge faster and achieve higher accuracy than BP and URW-BP. Our future work will focus on the theoretical studies regarding the convergence behavior of SURW-SPA. Moreover, the choice of optimal EAP is an open problem. It is worthwhile to design online algorithms to determine the uniform EAP for arbitrary network topologies. A straightforward extension of this work would be to employ the variational message passing method to reduce the communication overhead for cooperative localization.