On the Efficiency of Random Walk Routing in Multihop Wireless Network

In this paper, we propose a novel routing metric, namely biased delivery probability (BDP), for measuring the wireless node\´s capacity of forwarding data packet to the destination. BDP essentially assigns different weights to the multi-paths information associated with different hop counts. An theoretical theory is established to compute the weights for different scenarios. Using BDP routing metric, we design a prioritized random walk routing (PRR) protocol for multihop wireless network, which incorporates random network coding strategy, and can force the coded packet only randomly "walk" through the higher priority node set, instead of randomly encountered nodes. In such a way, it provides a loop-free random walk forwarding and guarantees the packets consequently go through the right "direction" step by step to the destination. Extensive simulation results show that the PRR protocol can dramatically improve the network performance over existing forwarding scheme, in terms of the throughputs, the end to end delay and the number of transmissions.