{'fraction_non_alphanumeric': 0.04119233598374724, 'fraction_numerical': 0.010543276472030544, 'mean_word_length': 4.5663872099824525, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 6, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Sequential Uniformly Reweighted Sum-Product Algorithm for Cooperative Localization in Wireless Networks

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.


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][2][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][8][9][10][11][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 treereweighted BP (TRW-BP), is proposed in [14]. TRW-BP has stronger convergence guarantees [15] and the potential 2 International Journal of Distributed Sensor Networks 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][17][18][19][20][21][22][23]. Wymeersch et al. in [16] gave an overview of cooperative localization approaches and developed a distributed localization algorithm based on SPA for largescale 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.

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 defined by a set of vertices V and a set of edges E (see Figure 1). Each vertex ∈ V represents a wireless node scattered in a planar region and each edge ( , ) ∈ E represents a communication link between nodes and . The set V of wireless nodes is divided into a set of anchor nodes V at known positions and a set of target nodes V at unknown positions. In this work, the anchor nodes are static, and the target nodes can move independently from positions at time slot − 1 to new positions at time slot . The two-dimensional position of node at time is given by , .
Assuming that wireless nodes can only communicate with neighboring nodes within a predefined radius , the set E at time is obtained as follows: for any , ∈ V, ( , ) ∈ E if, and only if, ‖ , − , ‖ ≤ . At time , if ( , ) ∈ E , node can obtain node 's current position information and a noisy measurement , , of its distance from node : where V , represents the measurement noise which is assumed to be a zero-mean Gaussian random variable with variance 2 , . This measurement provides us with a likelihood function ( , , | , , , ) between each pair of neighboring nodes ( , ).
Let x = { , | ∈ V } denote the set of the positions of target nodes at time , and let z = { , , | ( , ) ∈ E } denote the set of distance observations between the connected nodes. Based on the following Markovian assumption [16], the joint probability for x and z 1: can be written as where 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 ( , | z 1: ) of the variable , . Therefore, our goal is to calculate the marginal a posterior distribution ( , | z 1: ) for all target nodes ∈ V : where \{ }, denotes the positions of all the target nodes at time except , . Equation (3) expresses a factorization of a joint probability distribution which is suitable for representation by an FG [5]. Let , , ( , , , ) = ( , , | , , , ) .
For each wireless node , we draw a variable node, representing node 's position , , and an edge, connecting the variable node , with a factor node when the variable , appears in the corresponding factor. Similar to [24], the variable node of an anchor is only connected to the variable node of a target via , , because anchor nodes need not estimate their positions and therefore may disregard messages from neighboring nodes. The FG representation of Figure 1 at time is shown in Figure 2.

Message Passing Algorithms.
Given an FG of (x , z 1: ), the marginal a posteriori distribution ( , | z 1: ) of target node ∈ V 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.

Belief Propagation.
Let N denote the set of neighboring nodes of the node . The message from variable node , to factor node , , ( , , , ) can be written as and messages from factor nodes to variable node , are given by Finally, the so-called belief, , ( , ), which is an approximation of the a posteriori marginal ( , | z 1: ), takes the form International Journal of Distributed Sensor Networks
The message from factor node , , ( , , , ) to variable node , is given by The belief , ( , ) takes the form 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, , = 1, for all factor nodes. BP and TRW-BP are equivalent and provide the exact marginals. When an FG contains loops, , < 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.

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.

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 , to factor node Message from factor node , , ( , , , ) to variable node , is Belief of variable , is As a special case, URW-BP can revert to BP under suitable choice of ; that is, = 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 opt = ( − 1)/ , where = |V| and = |E|. Introducing as the number of pairwise interactions in which each variable is involved, a simple counting argument yields ≈ 2 / , so that opt ≈ min (1, 2 (1 − 1 )) .
Note that, for trees, = − 1, so that ≈ 2, with corresponding opt = 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.

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 (⋅), that is, mapping of nodes in V onto the set {1, 2, . . . , |V|}, and the chains which are monotonic with respect to the node ordering (⋅). 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 in the monotonic chain, there are no edges ( , ) with ( ) < ( ) and, for the last node , there are no edges ( , ) with ( ) > ( ). After that, we remove corresponding edges from the graph and repeat the procedure until no edges are left.

Sequential Uniformly Reweighted Sum-Product Algorithm for Mobile Localization.
In mobile localization problems, our goal is to calculate the marginal a posteriori distribution ( , | z 1: ) for all target nodes ∈ V . Given ( , −1 | z 1: −1 ), we can determine ( , | z 1: ) as follows: (i) a prediction operation, during which we determine the distribution ( , | z 1: −1 ), given all measurements before time , according to (4); (ii) a correction operation, in which we account for the new measurements z to calculate ( , | z 1: ), according to (5). Therefore, at every time , we have the marginal a posteriori distribution ( , | z 1: ) of the variable , given all the measurements up to and including time .
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.
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 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 From (21), we can see that only the belief of node (source node) is not available at node (destination node) and therefore has to be transmitted. Thus, each node only needs to broadcast its belief instead of messages (where is the node degree). This is paid by increased computational cost since the message ( −1) , , → , ( , ) 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 ,0 → ,1 ( ,0 ) can be represented by a uniform a priori distribution, for all ∈ V . Anchor nodes have perfect location information, so that

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

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 and make the same distance observation = and that the measurement noise variance is equal for all nodes; that is, 2 , = 2 V . Here, we set V = 1m. As the cooperative localization problem is nonlinear and potentially (1) given incoming messages , −1 → , ( , −1 ), ∀ ∈ V . Prediction phase: (2) nodes = 1 to in parallel (3) compute new message , → , ( , ) using (9) (4) end parallel Correction phase: (5) nodes = 1 to in parallel (6) obtain distance observations , , to neighboring nodes. (7) initialize end sequence (16) reverse the ordering: set ( ) = + 1 − ( ). (17) end for (18) nodes = 1 to in parallel (19) determine outgoing message: , → , +1 ( , ) = 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.
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 = 1 does not yield the best performance and the global minimum in the mean localization error is achieved by = 0.5 for SURW-SPA and URW-BP, which is the same as the theoretical value computed according to (18). Moreover, when = 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 = 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 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.
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.

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: where , and , are the new speed and direction of target at time slot ; and are constants representing the mean value of speed and direction; V and V are random variables from a Gaussian distribution. In the following experiments, V and V 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 is modified when the targets move within a certain distance of an edge. At time = 0, each target is assumed to have perfect knowledge of 8  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 is fixed at 2 m/s, the value of 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 = 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.
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.
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 = 20, SURW-SPA provides smaller localization errors than URW-BP. At = 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.
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.

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 International Journal of Distributed Sensor Networks   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.