Scale Free Aggregation in Sensor Networks

Sensor networks are distributed data collection systems, frequently used for mon-itoring 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 cor-relations in order to avoid transmitting redundancy. In our model, we formalize a notion of correlation, that can vary according to a parameter k. Then we relate the expected collision time of ”nearby” walks on the grid to the optimum cost of scale-free aggregation. We also propose a very simple randomized algorithm for routing information on a grid of sensors that satisfies the appropriate collision time condition. Thus, we prove that this simple scheme is a constant factor approximation (in expectation) to the optimum aggregation tree simultaneously for all correlation parameters k. The key contribution in our randomized analysis is to bound the average expected collision time of non-homogeneous random walks on the grid, i.e. the next hop probability depends on the current position