Hierarchical Spatial Gossip for Multiresolution Representations in Sensor Networks

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 2(i) 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 similar to 1/d(3). 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 Omega(n root 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.