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_16: We present a new approach to localizing an isotropic energy source using measurements from distributed sensors based on kernel averaging techniques. The location estimate is easily and efficiently calculated in a decentralized fashion. Statistical properties are derived for a very general measurement model. Experiments suggest that the proposed estimator is much more robust and exhibits better performance characteristics than the popular least squares estimator under a variety of conditions.
@cite_3: 
@cite_2: This paper introduces a class of probabilistic counting algorithms with which one can estimate the number of distinct elements in a large collection of data (typically a large file stored on disk) in a single pass using only a small additional storage (typically less than a hundred binary words) and only a few operations per element scanned. The algorithms are based on statistical observations made on bits of hashed values of records. They are by construction totally insensitive to the replicative structure of elements in the file; they can be used in the context of distributed systems without any degradation of performances and prove especially useful in the context of data bases query optimisation.
Two very recent papers by Moallemi and Van Roy @cite_3 and Mosk-Aoyama and Shah @cite_16 also consider the problem of computing averages in networks. The consensus propagation algorithm of @cite_3 is a modified form of belief propagation that attempts to mitigate the inefficiencies introduced by the random walk'' in gossip algorithms. However, their results, although promising, have only been proven for regular graphs, and it is unclear whether their algorithm will prove efficient for the networks in this paper. In @cite_16 , the authors use an algorithm based on Flajolet and Martin @cite_2 to compute averages and bound the averaging time in terms of a spreading time'' associated with the communication graph. However, they only show the optimality of their algorithm for a graph consisting of a single cycle, so it is currently difficult to speculate how it would perform on a geometric random graph.