On energy optimized averaging in wireless sensor networks

This paper studies the energy costs of running a distributed averaging/consensus algorithm in a wireless sensor network. It has recently been shown that running such an algorithm over a bidirectional spanning tree is preferable in terms of convergence time. We formulate the combinatorial optimization problem of selecting a minimal energy bidirectional spanning tree as a mixed integer linear programming problem. This problem has been shown to be NP-complete and can only be solved for small instances. We devise a semi-definite relaxation and establish bounds on the optimal cost. We also develop a series of graph-based algorithms that yield energy efficient bidirectional spanning trees and establish associated bounds on the optimal cost. Some of our algorithms can be run in a distributed manner and numerical results establish that they produce near-optimal solutions.