Reactive routing overhead in networks with unreliable nodes

ABSTRACT

This paper presents a new mathematical and simulative framework for quantifying the overhead of a broad class of reactive routing protocols, such as DSR and AODV, in wireless variable topology (ad-hoc) networks. We focus on situations where the nodes are stationary but unreliable, as is common in the case of sensor networks. We explicitly model the application-level traffic in terms of the statistical description of the number of hops between a source and a destination. The sensor network is modelled by an unreliable regular Manhattan (i.e. degree four) grid, and expressions for various components of the routing overhead are derived. Results are compared against ns-2 simulations for regular and random topologies, which corroborate the essential characteristics of the analytical results. One of the key insights that can be drawn from the mathematical results of this paper is that it is possible to design infinitely scalable reactive routing protocols for variable topology networks by judicious engineering of the traffic patterns to satisfy the conditions presented in this paper.

REFERENCES

• 1: C. E. Perkins, E. M. Belding-Royer, and S. R. Das. Ad hoc on-demand distance vector (AODV) routing. Internet Draft draft-ietf-manet-aodv-12.txt, Mobile Ad Hoc Networking Working Group, November 4 2002.
• 2: D. B. Johnson, D. A. Maltz, Y.-C. Hu, and J. G. Jetcheva. The dynamic source routing protocol for mobile ad hoc networks (DSR). Internet Draft draft-ietf-manet-dsr-07.txt, IETF MANET Working Group, February 21 2002.
• 3: Josh Broch , David A. Maltz , David B. Johnson , Yih-Chun Hu , Jorjeta Jetcheva, A performance comparison of multi-hop wireless ad hoc network routing protocols, Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking, p.85-97, October 25-30, 1998, Dallas, Texas, United States [doi>10.1145/288235.288256]
• 4: ns-Network Simulator. 1995. http://www.isi.edu/nsnam/ns/.
• 5: Yih-Chun Hu , David B. Johnson, Caching strategies in on-demand routing protocols for wireless ad hoc networks, Proceedings of the 6th annual international conference on Mobile computing and networking, p.231-242, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345952]
• 6: D. Estrin et al. Embedded Everywhere: A research agenda for networked systems of embedded computers. National Research Council, 2001.
• 7: P. Gupta and P. R. Kumar. Critical power for asymptotic connectivity in wireless networks. In W. M. McEneaney, G. Yin, Q. Zhang, and Birkhauser, editors, Stochastic Analysis, Control, Optimization and Applications: A Volume in Honor of W.H. Fleming, Boston, 1998.
• 8: Feng Xue , P. R. Kumar, The number of neighbors needed for connectivity of wireless networks, Wireless Networks, v.10 n.2, p.169-181, March 2004 [doi>10.1023/B:WINE.0000013081.09837.c0]
• 9: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Routing protocols

Additional Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.5 Model Development
          Subjects: Modeling methodologies

General Terms:
Algorithms, Design, Performance, Theory

Keywords:
AODV, DSR, ad hoc networks, reactive routing, reliability, routing overhead, sensor networks