Exact Analysis of Latency of Stateless Opportunistic Forwarding

Stateless opportunistic forwarding is a simple fault-tolerant distributed approach for data delivery and information querying in wireless ad hoc networks, where packets are forwarded to the next available neighbors in a "random walk" fashion, until they reach the destinations or expire. This approach is robust against ad hoc topology changes and is amenable to computation/bandwidth/energy-constrained devices; however, it is generally difficult to predict the end-to-end latency suffered by such a random walk in a given network. In this paper, we make several contributions on this topic. First, by using spectral graph theory we derive a general formula for computing the exact hitting and commute times of weighted random walks on a finite graph with heterogeneous sojourn times at relaying nodes. Such sojourn times can model heterogeneous duty cycling rates in sensor networks, or heterogeneous delivery times in delay tolerant networks. Second, we study a common class of distance-regular networks with varying numbers of geographical neighbors, and obtain simple estimate-formulas of hitting times by numerical analysis. Third, we study the more sophisticated settings of random geographical locations and distance-dependent sojourn times through simulations. Finally, we discuss the implications of this on the optimization of latency-overhead trade-off.