A greedy topology design to accelerate consensus in broadcast wireless sensor networks

We present techniques to improve convergence speed of distributed average consensus algorithms in wireless sensor networks by means of topology design. A broadcast network is assumed, so that only the transmit power of each node can be independently controlled, rather than each individual link. Starting with a maximally connected configuration in which all nodes transmit at full power, the proposed methods successively reduce the transmit power of a chosen node in order to remove one and only one link; nodes are greedily selected either in order to yield fastest convergence at each step, or if they have the largest degree in the network. These greedy schemes provide a good complexity-performance tradeoff with respect to full-blown global search methods. As a side benefit, improving the convergence speed also results in savings in energy consumption with respect to the maximally connected setting.