Accelerating Distributed Averaging in Sensor Networks: Randomized Gossip over Virtual Coordinates

Distributed averaging represents a central task in many applications related to sensor networks, ad-hoc networks, and embedded wireless systems. These systems are typically constrained in terms of computation, communication and energy requirements, thus making the design of effective solutions particularly challenging. Algorithms based on iterative rounds of computation among selected nodes of the network, such as randomized gossip algorithms, are regarded as viable approaches because of their robustness in dynamic settings and their simple conceptual design principles. Several efforts have been devoted to reduce the number of transmissions required by gossip algorithms to converge, in order to mitigate energy consumption and prolong the system lifetime. Geographic gossip, for instance, exploits geographic routing to enable values exchange between non-neighboring nodes through multi-hop communication, leading to faster convergence. In this paper we propose to extend this approach to networks whose nodes are not aware of their geographic location by developing a lightweight algorithm based on simple virtual coordinates. Experimental results point out the validity of the proposed method which, despite its simplicity, achieves significant gains in terms of convergence rate with respect to the reference randomized gossip across a wide range of operating conditions.