Nonparametric belief propagation for self-localization of sensor networks

By A. Ihler, John W. Fisher III, Randolph L. Moses, Alan S. Willsky. 2005

567 citations recorded by the source corpus.

Automatic self-localization is a critical need for the effective use of ad hoc sensor networks in military or civilian applications. In general, self-localization involves the combination of absolute location information (e.g., from a global positioning system) with relative calibration information (e.g., distance measurements between sensors) over regions of the network. Furthermore, it is generally desirable to distribute the computational burden across the network and minimize the amount of intersensor communication. We demonstrate that the information used for sensor localization is fundamentally local with regard to the network topology and use this observation to reformulate the problem within a graphical model framework. We then present and demonstrate the utility of nonparametric belief propagation (NBP), a recent generalization of particle filtering, for both estimating sensor locations and representing location uncertainties. NBP has the advantage that it is easily implemented in a distributed fashion, admits a wide variety of statistical models, and can represent multimodal uncertainty. Using simulations of small to moderately sized sensor networks, we show that NBP may be made robust to outlier measurement errors by a simple model augmentation, and that judicious message construction can result in better estimates. Furthermore, we provide an analysis of NBP's communications requirements, showing that typically only a few messages per sensor are required, and that even low bit-rate approximations of these messages can be used with little or no performance impact.

Subfields: Artificial Intelligence, Computer Networks and Communications, Electrical and Electronic Engineering

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

In Electrical and Electronic Engineering

Citations in the corpus

Kernel Sequential Monte Carlo (2015, background): “Previously, [14] focussed on MAP estimation of the sensor locations, and [15] focussed on a well-conditioned case ( S = 8 sensors and B = 3 base sensors with known locations) that results in almost no ambiguity in the posterior.”
Wormhole Hamiltonian Monte Carlo (2013, methodology): “Sensor Network Localization For our second example, we use a problem previously discussed by (Ihler et al. 2005) and (Ahn, Chen, and Welling 2013).”
Particle Belief Propagation (2009, methodology): “In work analyzing the properties of BP, the norm of choice is Hilbert’s projective measure, to which generalizations of Birkhoff’s contraction coefficient are applied (Ihler et al., 2005b; Mooij and Kappen, 2007).”
Belief Propagation, Dykstra's Algorithm, and Iterated Information Projections (2010, background): “Further validation followed with the resurrection [5] of low density parity check codes [6], and in relatively short time successful applications of belief propagation have been reported in network diagnostics [7], sensor self-localization [8], distributed inference in sensor networks [9], [10], and”
Boosting Variational Inference (2016, methodology): “In this experiment, we look at a sensor network localization problem that has been considered by Ihler et al. [2005], Ahn”
Cooperative Localization in Wireless Networks (2009, background): “Bayesian cooperative localization for networks wit hout mobility was investigated in [14], [109], [110].”
Fault Identification Via Nonparametric Belief Propagation (2009, methodology): “Table II outlines the two models and the transformation needed to shift between them; we use the notation1 for the all-ones vector of appropriate size.”
Message Passing Algorithms for Scalable Multitarget Tracking (2018, unknown): “In the last 25 years, message passing has been successfully used in many applications including iterative decoding of channel codes [34]–[37], communication receivers [38]–[40], and cooperative localization [41]–[43].”
A Survey of Enabling Technologies for Network Localization, Tracking, and Navigation (2018, background): “In addition, non-parametric belief propagation has appeared for localization in sensor networks in [224].”
Wireless sensor network localization techniques (2007, methodology): “It is demonstrated via simulations [102] that the overall performance of NBP is comparable to that of a centralized MAP (maximum a posteriori) estimate.”
Information fusion for wireless sensor networks: Methods, models, and classifications (2007, background): “Saligrama et al. [2006] use a variant of belief propagation [Pearl 1988; Ihler et al. 2005] as collaboration strategy for distributed classi.cation that reaches a consensus to the centralized MAP estimate.”
SfM with MRFs: Discrete-Continuous Optimization for Large-Scale Structure from Motion (2013, unknown): “Researchers in sensor networks have investigated message passing techniques for calibrating distributed camera networks, including forms of distributed averaging [26] and BP [27], [28].”
A Theoretical Foundation of Network Localization and Navigation (2018, background): “Such a process is highly complex and inefficient especially in medium- to large-scale networks, because joint estimation requires high-dimensional inference and incurs large communication overhead [165]–[167].”