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.
|Title of host publication||Proceedings of the 6th International Conference on Information Processing in Sensor Networks, IPSN 2007, Cambridge, Massachusetts, USA, April 25-27, 2007|
|Number of pages||10|
|Publication status||Published - 2007|