Loopy Belief Propagation as a Basis for Communication in Sensor Networks

By Christopher John Crick, Avi Pfeffer. 2002

110 citations recorded by the source corpus.

Sensor networks are an exciting new kind of computer system. Consisting of a large number of tiny, cheap computational devices physically distributed in an environment, they gather and process data about the environment in real time. One of the central questions in sensor networks is what to do with the data, i.e. how to reason with it and how to communicate it. This paper argues that the lessons of the UAI community, in particular that one should produce and communicate beliefs rather than raw sensor values, are highly relevant to sensor networks. We contend that loopy belief propagation is particularly well suited to communicating beliefs in sensor networks, due to its compact implementation and distributed nature. We investigate the ability of loopy belief propagation to function under the stressful conditions likely to prevail in sensor networks. Our experiments show that it performs well and degrades gracefully. It converges to appropriate beliefs even in highly asynchronous settings where some nodes communicate far less frequently than others; it continues to function if some nodes fail to participate in the propagation process; and it can track changes in the environment that occur while beliefs are propagating. As a result, we believe that sensor networks present an important application opportunity for UAI.

Subfields: Artificial Intelligence, Computer Networks and Communications

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

Citations in the corpus

Deep Coordination Graphs (2019, background): “…al., 2004), but messages can diverge in cyclic graphs, for example fully connected CGs. Subtracting a normalization constant c ij := a µ ( a ) / |A i | from each message µ ij before it is sent often leads to convergence in practice (Murphy et al., 1999; Crick & Pfeffer, 2002; Yedidia et al., 2003).”
Materials that couple sensing, actuation, computation, and communication (2015, methodology): “A simpler loopy belief propagation algorithm had been described earlier than the junction tree based belief propagation algorithm [23].”
Collaborative Multiagent Reinforcement Learning by Payoff Propagation (2006, methodology): “Regardless of these results, the algorithm has been successfully applied in practice in graphs with cycles (Murphy et al., 1999; Crick and Pfeffer, 2003; Yedidia et al., 2003).”
Multiagent Reinforcement Learning for Urban Traffic Control Using Coordination Graphs (2008, methodology): “Nevertheless, the algorithm has been successfully applied to such graphs [6, 10, 16].”