Geographic gossip: efficient aggregation for sensor networks Export

@proceedings{Dimakis2006geographic, abstract = {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 1/n^a using O(n^1.5radic(logn)) radio transmissions, which reduces the energy consumption by a radic(n/logn) factor over standard gossip algorithms}, author = {Dimakis, A. G. and Sarwate, A. D. and Wainwright, M. J.}, citeulike-article-id = {5805150}, citeulike-linkout-0 = {http://dx.doi.org/10.1109/IPSN.2006.244081}, citeulike-linkout-1 = {http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=1662442}, day = {31}, doi = {10.1109/IPSN.2006.244081}, journal = {Information Processing in Sensor Networks, 2006. IPSN 2006. The Fifth International Conference on}, keywords = {\_new, geographic, power, wsn}, month = {July}, pages = {69--76}, posted-at = {2009-10-15 01:49:38}, priority = {2}, title = {Geographic gossip: efficient aggregation for sensor networks}, url = {http://dx.doi.org/10.1109/IPSN.2006.244081}, year = {2006} }

TY - CONF ID - Dimakis2006geographic L3 - citeulike-article-id:5805150 N2 - 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 1/n^a using O(n^1.5radic(logn)) radio transmissions, which reduces the energy consumption by a radic(n/logn) factor over standard gossip algorithms JF - Information Processing in Sensor Networks, 2006. IPSN 2006. The Fifth International Conference on EP - 76 TI - Geographic gossip: efficient aggregation for sensor networks SP - 69 KW - _new KW - geographic KW - power KW - wsn AU - Dimakis, AG AU - Sarwate, AD AU - Wainwright, MJ PY - 2006/07/31/ UR - http://dx.doi.org/10.1109/IPSN.2006.244081 ER -