Gossip algorithms for aggregation have recently received significant attention for sensor network applications because of their simplicity and robustness in noisy and uncertain environments. However, gossip algorithms can waste significant energy by essentially passing around redundant information multiple times. For realistic sensor network model topologies like grids and random geometric graphs, the inefficiency of gossip schemes is caused by slow mixing times of random walks on those graphs. We propose and analyze an alternative gossiping scheme that exploits geographic information. By utilizing a simple resampling method, we can demonstrate substantial gains over previously proposed gossip protocols. In particular, for random geometric graphs, our algorithm computes the true average to accuracy @math using @math radio transmissions, which reduces the energy consumption by a @math factor over standard gossip algorithms.
@cite_18: We consider two distributed algorithms to compute functions that admit flexible decomposition in terms of pairwise computations. Under these algorithms a transmitting node becomes inactive and does not transmit further messages until it is reactivated by a message reception from another node. The algorithms thereby have sequential nature and bear a close relationship to random walks. We quantify their time and message complexities on the d-dimensional torus and establish substantial gains in message complexity with respect to gossip algorithms. The algorithms exhibit a favorable tradeoff between the two complexities in lower dimensions. In particular on the 2-dimensional torus with n nodes, time and per-node message complexities scale as Θ(n log n) and O((log n)) respectively, whereas both complexities scale as Ω(n) for gossip algorithms.
In @cite_18 the authors consider the related problem of computing the average of a network in . They propose a distributed algorithm to solve this problem and show how it can be related to cover times of random walks on graphs.