Networking sensors using belief propagation

This paper investigates the performance of belief propagation (BP) as a distributed solution to two combinatorial resource allocation problems arising in sensor networks: network formation and fusion center location. We model these problems by max-weight b-matching and uncapacitated facility location, respectively. Each of these is a classical optimization problem. For both problems, we (a) show how BP can be simplified for implementation in distributed environments where transmissions are broadcast and can interfere, (b) derive a principled interpretation of estimates before convergence, and (c) compare the performance of BP to that of linear programming.