Hierarchical spatial gossip for multi-resolution representations in sensor networks

Rik Sarkar, Xianjin Zhu, Jie Gao

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract / Description of output

In this paper we propose a lightweight algorithm for constructing multi-resolution data representations for sensor networks. We compute, at each sensor node u, O(log n) aggregates about exponentially enlarging neighborhoods centered at u. The ith aggregate is the aggregated data among 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 attributes to its simplicity, low communication cost, distributed nature and robustness to node failures and link failures. Besides the natural applications of multi-resolution data summaries in data validation and information mining, we also demonstrate the application of the pre-computed spatial multi-resolution data summaries in answering range queries efficiently.
Original languageEnglish
Title of host publicationProceedings of the 6th International Conference on Information Processing in Sensor Networks, IPSN 2007, Cambridge, Massachusetts, USA, April 25-27, 2007
Number of pages10
ISBN (Print)978-1-59593-638-7
Publication statusPublished - 2007


Dive into the research topics of 'Hierarchical spatial gossip for multi-resolution representations in sensor networks'. Together they form a unique fingerprint.

Cite this