Service discovery in MANET via biased random walks

In this paper we tackle the problem of service discovery in mobile wireless networks by exploiting an informed random walk based search, which is implemented directly atop the data link layer. The algorithm can be used both to discover a service and route data packets back to the requesting node, without any routing layer support. The information driving a search consists of the estimated distance of nodes from a service and the previously visited nodes. The suitability of the approach is shown through simulations and supported by an analytical model.