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

•Reaching a distributed average consensus is an important topic for Wireless Sensor Networks (WSNs).•Improving the convergence speed of such consensus algorithms translates into energy saving for the sensor nodes.•The problem of accelerating consensus in broadcast WSNs can be translated into a range assignment (RA) problem.•RA is an NP-hard problem.•Two different greedy techniques are proposed, which outperform state-of-the-art and meta-heuristic solutions.

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.