PATHS: analysis of PATH duration statistics and their impact on reactive MANET routing protocols

ABSTRACT

We develop a detailed approach to study how mobility impacts the performance of reactive MANET routing protocols. In particular we examine how the statistics of path durations including PDFs vary with the parameters such as the mobility model, relative speed, number of hops, and radio range. We find that at low speeds, certain mobility models may induce multi-modal distributions that reflect the characteristics of the spatial map, mobility constraints and the communicating traffic pattern. However, our study suggests that at moderate and high velocities the exponential distribution with appropriate parameterizations is a good approximation of the path duration distribution for a range of mobility models. The reciprocal of the average path duration is analytically shown to have a strong linear relationship with the throughput and overhead that is confirmed by the simulation results for DSR.

REFERENCES

• 1: 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]
• 2: David B. Johnson , David A. Maltz , Josh Broch, DSR: the dynamic source routing protocol for multihop wireless ad hoc networks, Ad hoc networking, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2001
• 3: Charles E. Perkins , Pravin Bhagwat, Highly dynamic Destination-Sequenced Distance-Vector routing (DSDV) for mobile computers, Proceedings of the conference on Communications architectures, protocols and applications, p.234-244, August 31-September 02, 1994, London, United Kingdom
• 4: David A. Maltz, Josh Broch, Jorjeta Jetcheva, and David B. Johnson. The Effects of On-Demand Behavior in Routing Protocols for Multi-Hop Wireless Ad Hoc Networks. IEEE Journal on Selected Areas in Communications special issue on mobile and wireless networks. August 1999.
• 5: Charles Perkins, Ad hoc On Demand Distance Vector (AODV) Routing, Internet draft, draft-ietf-manet-aodv-00.txt.
• 6: A. Bruce McDonald and Taieb Znati. A Path Availability Model for Wireless Ad Hoc Networks. In Proceedings of IEEE Wireless Communications and Networking Conference 1999 (WCNC '99), New Orleans, LA.
• 7: Xiaoyan Hong , Taek Jin Kwon , Mario Gerla , Daniel Lihui Gu , Guangyu Pei, A Mobility Framework for Ad Hoc Wireless Networks, Proceedings of the Second International Conference on Mobile Data Management, p.185-196, January 08-10, 2001
• 8: Xiaoyan Hong , Mario Gerla , Guangyu Pei , Ching-Chuan Chiang, A group mobility model for ad hoc wireless networks, Proceedings of the 2nd ACM international workshop on Modeling, analysis and simulation of wireless and mobile systems, p.53-60, August 20-20, 1999, Seattle, Washington, United States [doi>10.1145/313237.313248]
• 9: W. Su, S.-J. Lee, and M. Gerla. Mobility Prediction in Wireless Networks.In Proceedings of IEEE MILCOM 2000, Los Angeles, CA, Oct. 2000.
• 10: Per Johansson , Tony Larsson , Nicklas Hedman , Bartosz Mielczarek , Mikael Degermark, Scenario-based performance analysis of routing protocols for mobile ad-hoc networks, Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking, p.195-206, August 15-19, 1999, Seattle, Washington, United States [doi>10.1145/313451.313535]
• 11: S.-J. Lee, M. Gerla, and C.-K. Toh. A Simulation Study of Table-Driven and On-Demand Routing Protocols for Mobile Ad Hoc Networks. IEEE Network,vol. 13, no. 4, Jul/Aug 1999, pp. 48--54.
• 12: S. R. Das, C. E. Perkins and E. M. Royer. Performance Comparison of Two On-demand Routing Protocols for Ad Hoc Networks. Proceedings of INFOCOM 2000 Conference, Tel-Aviv, Israel, March 2000.
• 13: Comparative Performance Evaluation of Routing Protocols for Mobile, Ad hoc, Proceedings of the International Conference on Computer Communications and Networks, p.153, October 12-15, 1998
• 14: G.Pei, M. Gerla, X. Hong and C.-C.-Chiang. A wireless hierarchical protocol with group mobility. In proceedings of IEEE WCNC '99, September 1999.
• 15: Lee Breslau , Deborah Estrin , Kevin Fall , Sally Floyd , John Heidemann , Ahmed Helmy , Polly Huang , Steven McCanne , Kannan Varadhan , Ya Xu , Haobo Yu, Advances in Network Simulation, Computer, v.33 n.5, p.59-67, May 2000 [doi>10.1109/2.841785]
• 16: Vincent D. Park and M. Scott Corson. Temporally-Ordered Routing Algorithm (TORA) Version 1: Functional Specification. Internet-Draft, draft-ietf-manet-tora-spec-01.txt, Aug 1998.
• 17: F. Bai, N. Sadagopan, A. Helmy, "IMPORTANT: A framework to systematically analyze the Impact of Mobility on Performance of RouTing protocols for Adhoc NeTworks", IEEE INFOCOM (The 22nd Annual Joint Conference of the IEEE Computer and Communications Societies), March/April 2003, San Francisco. (Accepted To Appear).
• 18: F. Bai, N. Sadagopan, A. Helmy, "BRICS: A Building-block approach for analyzing RoutIng protoCols in Ad Hoc Networks - A Case Study of Reactive Routing Protocols", USC-CS-TR-02-775, November 2002. (Submitted for Review)
• 19: N. Sadagopan, F. Bai, B. Krishnamachari, A. Helmy, "PATHS: analysis of PATH duration Statistics and their impact on reactive MANET routing protocols", USC-CS-TR-02-778, December 2002.
• 20: Asis Nasipuri , Robert Castañeda , Samir R. Das, Performance of multipath routing for on-demand protocols in mobile ad hoc networks, Mobile Networks and Applications, v.6 n.4, p.339-349, Aug. 2001 [doi>10.1023/A:1011426611520]
• 21: Christian Bettstetter , Hannes Hartenstein , Xavier Pérez-Costa, Stochastic properties of the random waypoint mobility model: epoch length, direction distribution, and cell change rate, Proceedings of the 5th ACM international workshop on Modeling analysis and simulation of wireless and mobile systems, September 28-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570758.570761]
• 22: Christian Bettstetter, Smooth is better than sharp: a random mobility model for simulation of wireless networks, Proceedings of the 4th ACM international workshop on Modeling, analysis and simulation of wireless and mobile systems, p.19-27, July 2001, Rome, Italy [doi>10.1145/381591.381600]
• 23: Douglas M. Blough , Giovanni Resta , Paolo Santi, A statistical analysis of the long-run node spatial distribution in mobile ad hoc networks, Proceedings of the 5th ACM international workshop on Modeling analysis and simulation of wireless and mobile systems, September 28-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570758.570765]
• 24: Ingo Gruber , Hui Li, Link Expiration Times in Mobile Ad Hoc Networks, Proceedings of the 27th Annual IEEE Conference on Local Computer Networks, p.743-750, November 06-08, 2002
• 25: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 26: A. Papoulis "Probability, Random Variables and Stochastic Processes", Third Edition, Mc Graw Hill, 1991.

INDEX TERMS

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

General Terms:
Design, Performance

Keywords:
mobile ad hoc network, mobility, path duration, performance