An Efficient Biasing Strategy for Random Walk in Wireless Ad Hoc Networks

Random walk (RW) based search algorithms are often suggested to solve a search problem, namely the need to locate a node with a given property in a network, e.g., a node providing a service. In order for this solution to be efficient, the number of steps the walker makes before hitting the target node should be low. This can be achieved exploiting some form of bias, which forces the walker to always explore new parts of the network. In this paper we propose a novel biasing strategy for RW that relies only on the local information available to a node. We then compare our proposed strategy with some of the existing strategies, that also rely on local information. Through extensive simulations on square grid topology we show that the proposed biasing strategy is most cost effective in searching, most scalable, least effected by neighbor density, and most effective in replicated services scenarios among the compared strategies.