Comparison of Random Walk Strategies for Ad Hoc Networks
Sukhwinder Singh Dhillon, Piet Van Mieghem · Research Repository (Delft University of Technology) · 2007
We study different variations of the random walk (RW) such as RW with memory, RW with lookahead, RW using highest degree and RW proportional to the degree for random graphs.One of our insights is that comparison of different RW strategies based on the expected hopcount or weight is not sufficient.The expected hopcount for certain RW variations such as RW using highest degree is small.However, these strategies generally lead to infinite loops.Furthermore, the simulations show that RW using highest degree with look-ahead and memory is the most efficient algorithm for searching in random graphs.