| Full text | Click to download. |
| Citation | Workshop on Algorithmic Aspects of Wireless Sensor Networks, 2004
|
| Authors | M. Enachescu
A. Goel R. Govindan Rajeev Motwani |
Sensor networks are distributed data collection systems, frequently used for monitoring environments in which "nearby" data has a high degree of correlation. This induces opportunities for data aggregation, that are crucial given the severe energy constraints of the sensors. Thus it is very desirable to take advantage of data correlations in order to avoid transmitting redundancy. In our model, we formalize a notion of correlation, that can vary according to a parameter k. We propose a very simple randomized algorithm for routing information on a grid of sensors in a way which promotes data aggregation. We prove that this simple scheme is constant factor approximation (in expectation) to the optimum aggregation tree simultaneously for all correlation parameters k. The key idea of our randomized analysis is to relate the expected collision time of random walks on the grid to scale free aggregation.