Energy Optimized Topologies for Distributed Averaging in Wireless Sensor Networks
The authors study the energy efficient implementation of averaging/consensus algorithms in wireless sensor networks. For static, time-invariant topologies they start from the recent result that a bidirectional spanning tree is preferable in terms of convergence time. They formulate the combinatorial optimization problem of selecting such a minimal energy tree as a mixed integer linear programming problem. Since the problem is NP-complete they devise a semi-definite relaxation and establish bounds on the optimal cost. They also develop a series of graph-based algorithms that yield energy efficient bidirectional spanning trees and establish associated bounds on the optimal cost.