Performance of ad hoc networks with two-hop relay routing and limited packet lifetime

ABSTRACT

Considered is a mobile ad hoc network consisting of three types of nodes (source, destination and relay nodes) and using the two-hop relay routing protocol. Packets at relay nodes are assumed to have a limited lifetime in the network. All nodes are moving inside a bounded region according to some random mobility model. Both closed-form expressions, and asymptotic results when the number of nodes is large, are provided for the packet delivery delay and the energy needed to transmit a packet from the source to its destination. We also introduce and evaluate a variant of the two-hop relay protocol that limits the number of generated copies in the network. Our model is validated through simulations for two mobility models (random waypoint and random direction mobility models), numerical results for the two-hop relay protocols are reported, and the performance of the two-hop routing and of the epidemic routing protocols are compared.

REFERENCES

• 1: Delay tolerant research group. Web site: http://www.dtnrg.org.
• 2: D. Anick, D. Mitra, and M. M. Sondhi. Stochastic theory of a data-handling system with multiple sources. Bell System Technical Journal, 61(8):1871--1896, Oct. 1982.
• 3: Christian Bettstetter, Mobility modeling in wireless networks: categorization, smooth movement, and border effects, ACM SIGMOBILE Mobile Computing and Communications Review, v.5 n.3, p.55-66, July 2001 [doi>10.1145/584051.584056]
• 4: J.-Y. L. Boudec and M. Vojnovic. Perfect simulation and stationarity of a class of mobility models. In Proc. of IEEE INFOCOM, Miami, FL, Apr. 2005.
• 5: 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]
• 6: A. E. Gamal, J. Mammen, B. Prabhakar, and D. Shah. Throughput-delay trade-off in wireless networks. In Proc. of IEEE INFOCOM, Hong Kong, Apr. 2004.
• 7: C. Grinstead and J. Snell. Introduction to Probability. American Mathematical Society, 1997.
• 8: R. Groenevelt, P. Nain, and G. Koole. The message delay in mobile ad hoc networks. In Posters ACM SIGMETRICS 2005, Canada, 2005.
• 9: Matthias Grossglauser , David N. C. Tse, Mobility increases the capacity of ad hoc wireless networks, IEEE/ACM Transactions on Networking (TON), v.10 n.4, p.477-486, August 2002 [doi>10.1109/TNET.2002.801403]
• 10: P. Gupta and P. R. Kumar. The capacity of wireless networks. ACM/IEEE Transactions on Information Theory, 46(2), Mar. 2000.
• 11: A. A. Hanbali, P. Nain, and E. Altman. Performance evaluation of packet relaying in ad hoc network. Technical Report RR-5860, INRIA, Mar. 2006.
• 12: T. G. Kurtz. Solutions of ordinary differential equations as limits of pure jump markov processes. Applied Probility, 7:49--58, 1970.
• 13: B. L. P. Nain, D. Towsley and Z. Liu. Properties of random direction models. In Proc. of IEEE INFOCOM, Miami, FL, Mar. 2005.
• 14: Tara Small , Zygmunt J. Haas, The shared wireless infostation model: a new ad hoc networking paradigm (or where there is a whale, there is a way), Proceedings of the 4th ACM international symposium on Mobile ad hoc networking & computing, June 01-03, 2003, Annapolis, Maryland, USA [doi>10.1145/778415.778443]
• 15: Tara Small , Zygmunt J. Haas, Resource and performance tradeoffs in delay-tolerant wireless networks, Proceeding of the 2005 ACM SIGCOMM workshop on Delay-tolerant networking, p.260-267, August 26-26, 2005, Philadelphia, Pennsylvania, USA [doi>10.1145/1080139.1080144]
• 16: E. Zhang, G. Neglia, J. Kurose, and D. Towsley. Performance modeling of epidemic routing. In Proc. of Networking, pages 827--839, Coimbra, Portugal, May 2006.

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Bounded-action devices (e.g., Turing machines, random access machines)

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Network problems

Keywords:
delay tolerant network, limited packet lifetime, mobile ad hoc network, mobility model, performance analysis, two-hop relay protocol