Average delay analysis of opportunistic single copy delivery in Manhattan area using biased random walk

In Mobile Opportunistic Networks, the cost and effectiveness of any opportunistic forwarding is measured by the expected delay of a message. Hence, its critical goal is to have low delay for a message. This paper studies the average delay of a message in a Mobile Opportunistic Network on Manhattan area. We first model the mobility of a message as a biased random walk in tilted grid and analyze the delay of a message based on the hitting time of a bias random walk. We have derived an exact expression of expected delay for a walk starting from any point in tilted grid for both biased and unbiased random walks and provide a closed form approximation of average delay of a message for the case of unbiased random walk. The key result is that the average delay of a message in Mobile Opportunistic Networks is very sensitive to the biased level of a random walk at each stage of the walk (depends on the distance from destination at its current stage). Then, this key result explains why most of the smart message forwarding algorithm in Mobile Opportunistic Network works reasonably well.