hierarchical spatial gossip for multi-resolution representations in sensor networks
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 i th aggregate is the aggregated data among 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 1 / d 3 . 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.
gossip multi-resolution representation sensor networks