Latency of opportunistic forwarding in finite regular wireless networks

ABSTRACT

In opportunistic forwarding, a node randomly relays packets to one of its neighbors based on local information, without the knowledge of global topology. Each intermediate node continues this process until the packet arrives at its destination. This is particularly attractive in certain types of wireless ad hoc and sensor networks where obtaining accurate knowledge of global topology may be infeasible. However, opportunistic forwarding is hampered by the difficulty to control its performance, particularly, the end-to-end latency. This paper presents new analytical results that shed light on the latency of "random walk", the simplest type of opportunistic forwarding, for several useful regular network topologies, such as r-nearest cycle that can model variable wireless transmission distance in one dimensional scenario, and a 2D regular torus-type graph that can approximate grid-like deployments. We give new exact and approximation formulas for the maximum expected hitting time of random walk on such topologies.

REFERENCES

• 1: S. Boyd, A. Ghosh, B. Prabhakar, and D. Shah, "Randomized gossip algorithms," IEEE Trans. Information Theory, vol. 52, no. 6, June 2006.
• 2: R. B. Ellis, "Discrete green's functions for products of regular graphs," 2003, arXiv:math/0309080v2.
• 3: Fan Chung , S.-T. Yau, Discrete Green's functions, Journal of Combinatorial Theory Series A, v.91 n.1-2, p.191-214, July-Aug. 2000 [doi>10.1006/jcta.2000.3094]
• 4: D. A. Levin, Y. Peres, and E. L. Wilmer, "Markov chains and mixing times," http://www.oberlin.edu/markov/, 2006, lecture notes.
• 5: D. Aldous and J. A. Fill, "Reversible Markov chains and random walks on graphs," http://www.stat.berkeley.edu/aldous/RWG/book.html, 1999, lecture notes.
• 6: L. Lovasz, "Random walk on graphs: A survey," Combinatorics, Paul Erdos is Eighty, vol. 2, pp. 1--46, 1993.
• 7: D. Geller, I. Kra, S. Popescu, and S. Simanca, "On circulant matrices," http://www.math.sunysb.edu/sorin/, lecture notes.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory

General Terms:
Algorithms, Design, Theory

Keywords:
opportunistic forwarding, random walk on finite graphs, wireless ad hoc and sensor networks