A robust and energy efficient protocol for random walk in ad hoc networks with IEEE 802.11

Random walk (RW) based algorithms are often proposed to solve many problems in wireless networks. The implementation of such algorithms are usually done at the application layer so that many characteristics of the wireless transmissions are not exploited. In this paper, we show that we can greatly reduce the energy requirements to perform a RW by better exploiting the broadcast nature of the transmissions. We propose a broadcast based distributed next hop selection algorithm and compare it with a standard unicast based next hop selection algorithm. To evaluate the algorithms, we present a simulation study performed with ns-2. We found that the proposed algorithm is energy efficient, results in less source to destination delay, incurs less number of hops or transmissions and more robust in mobility as compared to a standard unicast based implementation of next hop selection algorithm for RW. © 2010 Taylor & Francis.