Hierarchical Spatial Gossip for Multiresolution Representations in Sensor Networks

Rik Sarkar, Xianjin Zhu, Jie Gao

Research output: Contribution to journalArticlepeer-review

Abstract / Description of output

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 necessary in a scalable efficient algorithm. Besides the natural applications of multiresolution data summaries in data validation and information mining, we also demonstrate the application of the precomputed multiresolution data summaries in answering range queries efficiently.

Original languageEnglish
Article number4
Pages (from-to)4:1-4:24
Number of pages24
JournalACM Transactions on Sensor Networks
Issue number1
Publication statusPublished - 1 Aug 2011


Dive into the research topics of 'Hierarchical Spatial Gossip for Multiresolution Representations in Sensor Networks'. Together they form a unique fingerprint.

Cite this