P. Skraba, A. Nguyen, Q. Fang, L. J. Guibas, Sweep Over Sensor Networks, International Conference on Information Processing in Sensor Networks (IPSN'06), pp 143-151, 2006.


We present a robust approach to data collection, aggregation, and dissemination problems in sensor networks. Our method is based on the idea of a {\em sweep} over the network: a wavefront that traverses the network, passes over each node exactly once, and performs the desired operation(s). We do not require global information about the sensor field such as node locations. Instead, in a preprocessing phase, we compute a potential function over the network whose gradients guide the sweep process. The sweep itself operates asynchronously, using only local operations to advance the wavefront. The gradient information provides a local ordering of the nodes that helps reduce the number of MAC-layer collisions as the wavefront advances, while also globally shaping the wavefront so as to conform to the sensor field layout. The approach is robust to both link volatility and node failures that may be present in real network conditions. The potential is computed by a stable diffusion process in which each node repeatedly set its potential to the average of the potentials of its neighbors. Aggregation paths are decided on-line as the sweep proceeds and no fixed tree structure is needed over the course of the computation. We present simulation results illustrating the correctness of the algorithm and comparing the performance of the sweep to aggregation trees under various network conditions.


 author = {Primoz Skraba and Qing Fang and An Nguyen and Leonidas Guibas},
 title = {Sweeps over wireless sensor networks},
 booktitle = {IPSN '06: Proceedings of the fifth international conference on Information processing in sensor networks},
 year = {2006},
 isbn = {1-59593-334-4},
 pages = {143--151},
 location = {Nashville, Tennessee, USA},
 doi = {http://doi.acm.org/10.1145/1127777.1127802},
 publisher = {ACM Press},
 address = {New York, NY, USA},