Search

In distributed target tracking for wireless sensor networks, agreement on the target state can be achieved by the construction and maintenance of a communication path, in order to exchange information regarding local likelihood functions. Such an approach lacks robustness to failures and is not easily applicable to ad-hoc networks. To address this, several methods have been proposed that allow agreement on the global likelihood through fully distributed belief consensus (BC) algorithms, operating on local likelihoods in distributed particle filtering (DPF). However, a unified comparison of the convergence speed and communication cost has not been performed. In this paper, we provide such a comparison and propose a novel BC algorithm based on belief propagation (BP). According to our study, DPF based on metropolis belief consensus (MBC) is the fastest in loopy graphs, while DPF based on BP consensus is the fastest in tree graphs. Moreover, we found that BC-based DPF methods have lower communication overhead than data flooding when the network is sufficiently sparse., COOPLOC

Of the many state-of-the-art methods for cooperative localization in wireless sensor networks (WSNs), only very few adapt well to mobile networks. The main problems of the well-known algorithms, based on nonparametric belief propagation (NBP), are the high communication cost and inefficient sampling techniques. Moreover, they either do not use smoothing or just apply it offline. Therefore, in this article, we propose more flexible and efficient variants of NBP for cooperative localization in mobile networks. In particular, we provide: (i) an optional 1-lag smoothing done almost in real-time, (ii) a novel low-cost communication protocol based on package approximation and censoring, (iii) higher robustness of the standard mixture importance sampling (MIS) technique, and (iv) a higher amount of information in the importance densities by using the population Monte Carlo (PMC) approach, or an auxiliary variable. Through extensive simulations, we confirmed that all the proposed techniques outperform the standard NBP method.

In this paper, we propose a new inference algorithm, suitable for distributed processing over wireless networks. The algorithm, called uniformly reweighted belief propagation (URW-BP), combines the local nature of belief propagation with the improved performance of tree-reweighted belief propagation (TRW-BP) in graphs with cycles. It reduces the degrees of freedom in the latter algorithm to a single scalar variable, the uniform edge appearance probability ρ. We provide a variational interpretation of URW-BP, give insights into good choices of ρ, develop an extension to higher-order potentials, and complement our work with numerical performance results on three inference problems in wireless communication systems: spectrum sensing in cognitive radio, cooperative positioning, and decoding of a low-density parity-check (LDPC) code.

The objective of this thesis is the development of cooperative localization and tracking algorithms using nonparametric message passing techniques. In contrast to the most well-known techniques, the goal is to estimate the posterior probability density function (PDF) of the position of each sensor. This problem can be solved using Bayesian approach, but it is intractable in general case. Nevertheless, the particle-based approximation (via nonparametric representation), and an appropriate factorization of the joint PDFs (using message passing methods), make Bayesian approach acceptable for inference in sensor networks. The well-known method for this problem, nonparametric belief propagation (NBP), can lead to inaccurate beliefs and possible non-convergence in loopy networks. Therefore, we propose four novel algorithms which alleviate these problems: nonparametric generalized belief propagation (NGBP) based on junction tree (NGBP-JT), NGBP based on pseudo-junction tree (NGBP-PJT), NBP based on spanning trees (NBP-ST), and uniformly-reweighted NBP (URW-NBP). We also extend NBP for cooperative localization in mobile networks. In contrast to the previous methods, we use an optional smoothing, provide a novel communication protocol, and increase the efficiency of the sampling techniques. Moreover, we propose novel algorithms for distributed tracking, in which the goal is to track the passive object which cannot locate itself. In particular, we develop distributed particle filtering (DPF) based on three asynchronous belief consensus (BC) algorithms: standard belief consensus (SBC), broadcast gossip (BG), and belief propagation (BP). Finally, the last part of this thesis includes the experimental analysis of some of the proposed algorithms, in which we found that the results based on real measurements are very similar with the results based on theoretical models.

Distributed target tracking in wireless sensor networks (WSN) is an important problem, in which agreement on the target state can be achieved using particle filters with standard consensus methods, which may take long to converge. We propose distributed particle filtering based on belief propagation (DPF-BP) consensus, a fast method for target tracking. According to our simulations, DPF-BP provides better performance than DPF based on standard belief consensus (DPF-SBC) in terms of disagreement in the network. However, in terms of root-mean square error, it can outperform DPF-SBC only for a specific number of consensus iterations.

Belief propagation (BP) is a technique for distributed inference in wireless networks and is often used even when the underlying graphical model contains cycles. In this paper, we propose a uniformly reweighted BP scheme that reduces the impact of cycles by weighting messages by a constant “edge appearance probability” ρ ≤ 1. We apply this algorithm to distributed binary hypothesis testing problems (e.g., distributed detection) in wireless networks with Markov random field models. We demonstrate that in the considered setting the proposed method outperforms standard BP, while maintaining similar complexity. We then show that the optimal ρ can be approximated as a simple function of the average node degree, and can hence be computed in a distributed fashion through a consensus algorithm.

Tree-reweighted belief propagation is a message passing method that has certain advantages compared to traditional belief propagation (BP). However, it fails to outperform BP in a consistent manner, does not lend itself well to distributed implementation, and has not been applied to distributions with higher-order interactions. We propose a method called uniformly-reweighted belief propagation that mitigates these drawbacks. After having shown in previous works that this method can substantially outperform BP in distributed inference with pairwise interaction models, in this paper we extend it to higher-order interactions and apply it to LDPC decoding, leading performance gains over BP.

Nonparametric belief propagation (NBP) is one of the best-known methods for cooperative localization in sensor networks. It is capable of providing information about location estimation with appropriate uncertainty and to accommodate non-Gaussian distance measurement errors. However, the accuracy of NBP is questionable in loopy networks. Therefore, in this paper, we propose a novel approach, NBP based on spanning trees (NBP-ST) created by breadth first search (BFS) method. In addition, we propose a reliable indoor model based on obtained measurements in our lab. According to our simulation results, NBP-ST performs better than NBP in terms of accuracy and communication cost in the networks with high connectivity (i.e., highly loopy networks). Furthermore, the computational and communication costs are nearly constant with respect to the transmission radius. However, the drawbacks of proposed method are a little bit higher computational cost and poor performance in low-connected networks.

Nonparametric belief propagation (NBP) is well-known probabilistic method for cooperative localization in sensor networks. However, due to the double counting problem, NBP convergence is not guaranteed in the networks with loops or even if NBP converges, it could provide us less accurate estimates. The well-known solution for this problem is nonparametric generalized belief propagation based on junction tree (NGBP-JT). However, there are two problems: how to efficiently form the junction tree in an arbitrary network, and how to decrease the number of particles while keeping the good performance. Therefore, in this paper, we propose the formation of pseudo-junction tree (PJT), which represents the approximated junction tree based on thin graph. In addition, in order to decrease the number of particles, we use a set of very strong constraints. The resulting localization method, NGBP based on PJT (NGBP-PJT), overperforms NBP in terms of accuracy and communication cost in any arbitrary network.