Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

Hierarchical Spatial Gossip for Multiresolution Representations in Sensor Networks

Hierarchical Spatial Gossip for Multiresolution Representations in Sensor Networks Hierarchical Spatial Gossip for Multiresolution Representations in Sensor Networks RIK SARKAR, XIANJIN ZHU, and JIE GAO, Stony Brook University In this article we propose a lightweight algorithm for constructing multiresolution data representations for sensor networks. At each sensor node u, we compute O(log n) aggregates about exponentially enlarging neighborhoods centered at u. The ith aggregate is the aggregated data from nodes approximately within 2i hops of u. We present a scheme, named the hierarchical spatial gossip algorithm, to extract and construct these aggregates, for all sensors simultaneously, with a total communication cost of O(n polylog n). The hierarchical gossip algorithm adopts atomic communication steps with each node choosing to exchange information with a node distance d away with probability ¼ 1/d3 . The attractiveness of the algorithm can be attributed to its simplicity, low communication cost, distributed nature, and robustness to node failures and link failures. We show in addition that computing multiresolution aggregates precisely (i.e., each aggregate š uses all and only the nodes within 2i hops) requires a communication cost of (n n), which does not scale well with network size. An approximate range in aggregate computation like that introduced by the gossip mechanism is therefore http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png ACM Transactions on Sensor Networks (TOSN) Association for Computing Machinery

Hierarchical Spatial Gossip for Multiresolution Representations in Sensor Networks

Download PDF
24 pages

Loading next page...
 
/lp/association-for-computing-machinery/hierarchical-spatial-gossip-for-multiresolution-representations-in-UMrHhX9W8i
Publisher
Association for Computing Machinery
Copyright
Copyright © 2011 by ACM Inc.
ISSN
1550-4859
DOI
10.1145/1993042.1993046
Publisher site
See Article on Publisher Site

Abstract

Hierarchical Spatial Gossip for Multiresolution Representations in Sensor Networks RIK SARKAR, XIANJIN ZHU, and JIE GAO, Stony Brook University In this article we propose a lightweight algorithm for constructing multiresolution data representations for sensor networks. At each sensor node u, we compute O(log n) aggregates about exponentially enlarging neighborhoods centered at u. The ith aggregate is the aggregated data from nodes approximately within 2i hops of u. We present a scheme, named the hierarchical spatial gossip algorithm, to extract and construct these aggregates, for all sensors simultaneously, with a total communication cost of O(n polylog n). The hierarchical gossip algorithm adopts atomic communication steps with each node choosing to exchange information with a node distance d away with probability ¼ 1/d3 . The attractiveness of the algorithm can be attributed to its simplicity, low communication cost, distributed nature, and robustness to node failures and link failures. We show in addition that computing multiresolution aggregates precisely (i.e., each aggregate š uses all and only the nodes within 2i hops) requires a communication cost of (n n), which does not scale well with network size. An approximate range in aggregate computation like that introduced by the gossip mechanism is therefore

Journal

ACM Transactions on Sensor Networks (TOSN) – Association for Computing Machinery

Published: Aug 1, 2011

There are no references for this article.