Randomized Gossip with Power of Two Choices for Energy Aware Distributed Averaging

Distributed computation of average values held by nodes belonging to a self-organized network is a key task in many application areas, ranging from sensor and ad-hoc networks to networked control systems. Severe computational, communication, and energy constraints typical of these environments prompt for the design of specific solutions addressing these issues. In this context, gossip algorithms represent valuable approaches because of their simple local communication patterns, resulting into robustness to dynamic topology changes. Several variants of gossip-based techniques have been proposed, mainly focused on improvements of the convergence time, which directly impacts energy expenditure. Energy efficiency remains however a challenging issue to be addressed. In this paper we introduce a novel energy-aware distributed averaging algorithm which combines the standard randomized gossip protocol with a probabilistic load balancing technique, the power of two choices. Experimental results show that the proposed solution achieves better load balancing with respect to standard pairwise averaging, enabling considerable improvements in the network lifetime without impairing convergence time.