Hitting time analysis for a class of random packet forwarding schemes in ad hoc networks

In this paper, we study the problem of searching for a node or a piece of data in an ad hoc network using random packet forwarding. In particular, we examine three different methods. The first is a random direction forwarding scheme where the query packet is forwarded along a randomly chosen direction (following an approximate straight line) till it either hits the destination node (the target) or the boundary. It bounces off the boundary in the latter case and the process continues till the target is found. In the second approach, in addition to query packet traversing the network, the target releases an advertisement packet that propagates along a randomly chosen direction so that all nodes visited by the advertisement packet obtain and store the target location information. In the third method the query packet is assumed to follow a random walk type of forwarding. Our primary interest is in comparing the average hitting time under these methods and the memory required to store location information. In particular, we show that under the random direction forwarding the target hitting time is Θa2b, where aa and bb denote the size/radii of the network and the target area, assumed to be circular in shape, respectively. The hitting time is Θ(a)Θ(a) with target advertisement, and Θa2logab under the random walk type of forwarding. We further show that the target advertisement method achieves mean hitting time on the same order as greedy forwarding schemes with less memory requirement. We compare this class of schemes with the family of Lévy walks and provide simulation results on their performance under more realistic settings.