An Adapting Random Walk for Ad hoc and Sensor Networks

In this paper we propose an adaptive random walk for wireless networks. The lifetime of the walk is varied in such a way that at least a given fraction of nodes is covered, in expectation. The only parameter of the random walk, α, depends on the nominal network size N and on the required coverage. For sizes lower than N the required coverage is satisfied with lifetime slightly higher than the optimal one. The paper reports performance results obtained through analytical study backed up with simulations. 1