Asymptotic critical transmission radius for greedy forward routing in wireless ad hoc networks

ABSTRACT

Greedy forward routing (abbreviated by GFR)in wireless ad hoc networks is a localized geographic routing in which each node discards a packet if one of its neighbors is closer to the destination of the packet than itself, or otherwise forwards the packet to the neighbor closest to the destination of the packet. If all nodes have the same transmission radii, the critical transmission radius for GFR is the smallest transmission radius which ensures that packets can be delivered between any source-destination pairs. In this paper, we study the asymptotic critical transmission radius for GFR in randomly deployed wireless ad hoc networks. We assume that the network nodes are represented by a Poisson point process of density n over a convex compact region of u it area with bounded curvature.Let ß₀ = 1/ (⅔√3 over 2π) ≈ 1.6². We show that √ß₀ 1n n over πn is asymptotically almost surely (abbreviated by a.a.s.) the threshold of the critical transmission radius for GFR.I other words,for ß > ß₀ if the trasmission radius is √ß 1n n over πn, it is a.a.s. packets can be delivered between any source-destination pairs; for any ß < ß₀ if the transmission radius is √ß 1n noverπn, it is a.a.s. packets can't be delivered between some source-destination pair.

REFERENCES

• 1: F. Baccelli and P. Bremaud. Elements of Queueing Theory: Palm-Martingale Calculus and Stochastic Recurrences Springer, February 12 2003.
• 2: G. Finn. Routing and addressing problems in large metropolitan-scale internetworks, March 1987. Techical Report ISI Research Report ISU/RR-87-180.
• 3: J. Geißler and H.vo Weizsäcker. Geometric measure theory. Script.
• 4: Brad Karp , H. T. Kung, GPSR: greedy perimeter stateless routing for wireless networks, Proceedings of the 6th annual international conference on Mobile computing and networking, p.243-254, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345953]
• 5: F. Lin and X. Yang, editors. Geometric Measure Theory: An Introduction International Press, 2003.
• 6: H. Takagi and L. Kleinrock. Optimal transmission ranges for randomly distributed packet radio terminals. IEEE Transactions on Communications COM-32(3):246--257, March 1984.
• 7: Guoliang Xing , Chenyang Lu , Robert Pless , Qingfeng Huang, On greedy geographic routing algorithms in sensing-covered networks, Proceedings of the 5th ACM international symposium on Mobile ad hoc networking and computing, May 24-26, 2004, Roppongi Hills, Tokyo, Japan [doi>10.1145/989459.989465]

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:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Routing protocols
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Reliability, availability, and serviceability

General Terms:
Theory

Keywords:
greedy forward routing, random deployment, wireless ad hoc networks