A Robust Architecture for Distributed Inference in Sensor Networks

Many inference problems that arise in sensor networks can be formulated as a search for a global explanation which is consistent with local information known to each node. Examples include probabilistic inference, pattern classification, regression, and constraint satisfaction. Centralized inference algorithms for these problems often take the form of message passing on a special type of data structure called a junction tree, which has the important property that local consistency between adjacent nodes is su#cient to ensure global consistency between all pairs of nodes. In this paper we present an architecture for distributed inference in sensor networks which is robust to unreliable communication and node failures. In our architecture, the nodes of the sensor network assemble themselves into a stable spanning tree, and use an asynchronous message passing algorithm to transform the spanning tree into a junction tree for the inference problem. Using asynchronous message passing on this junction tree, the nodes can solve the inference problem e#ciently and exactly. We also present an e#cient distributed algorithm for optimizing the choice of junction tree so that the communication and computational cost of inference can be minimized. We present experimental results for three applications---distributed sensor calibration, optimal control, and sensor field modeling---on data from a real sensor network deployment