Sound mobility models

ABSTRACT

Simulation has become an indispensable tool in the construction and evaluation of mobile systems. By using mobility models that describe constituent movement, one can explore large systems, producing repeatable results for comparison between alternatives. Unfortunately, the vast majority of mobility models---including all those in which nodal speed and distance or destination are chosen independently---suffer from decay; average speed decreases until converging to some long-term average. Such decay provides an unsound basis for simulation studies that collect results averaged over time, complicating the experimental process.This paper shows via analysis that such decay is inevitable in a wide variety of mobility models, including the most common in use today. We derive a general framework for describing this decay, and apply it to a number of practical cases. Furthermore, this framework allows us to transform any given mobility model into a stationary one: choose initial speeds from the steady-state distribution, and subsequent speeds from the original. This transformation provides sound models for simulation, eliminating variations in average nodal speed.

REFERENCES

• 1: The network simulator - ns-2. http://www.isi.edu/nsnam/ns/, 2002.
• 2: Arnold O. Allen, Probability, statistics, and queueing theory with computer science applications, Academic Press Professional, Inc., San Diego, CA, 1990
• 3: F. Baccelli and P. Bremaud. Elements of Queueing Theory, Palm Martingale Calculus and Stochastic Recurrences. Springer, second edition, 2003.
• 4: 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]
• 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: T. Camp, J. Boleng, and V. Davies. A survey of mobility models for ad hoc network research. In Wireless Communication and Mobile Computing (WCMC): Special issue on Mobile Ad Hoc Networking: Research, Trends and Applications, 2002.
• 7: T. Chu and I. Nikolaidis. On the artifacts of random waypoint simulations. In Proceedings of the 1st International Workshop on Wired/Wireless Internet Communications (WWIC2002), in conjunctions with the International Conference on Internet Computing (IC'02), 2002.
• 8: D. R. Cox. Renewal Theory. Methuen, London, 1967.
• 9: I. S. Gradshteyn and I. M. Ryzhik. Table of Integral, Series, and Products. Academic Press, sixth edition, 2000.
• 10: 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]
• 11: 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
• 12: 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]
• 13: R. Jain. The Art of Computer Systems Performance Analysis: Techniques for Experimental Design, Measurement, Simulation, and Modeling. John Wiley & Sons, 1991.
• 14: D. B. Johnson and D. A. Maltz. Dynamic source routing in ad hoc wireless networks. In Imielinski and Korth, editors, Mobile Computing, volume 353. Kluwer Academic Publishers, 1996.
• 15: Young-Bae Ko , Nitin H. Vaidya, Location-aided routing (LAR) in mobile ad hoc networks, Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking, p.66-75, October 25-30, 1998, Dallas, Texas, United States [doi>10.1145/288235.288252]
• 16: W. Navidi and T. Camp. Stationary distributions for the random waypoint mobility model. Technical Report MCS-03-04, The Colorado School of Mines, April 2003.
• 17: Charles E. Perkins , Elizabeth M. Royer, Ad-hoc On-Demand Distance Vector Routing, Proceedings of the Second IEEE Workshop on Mobile Computer Systems and Applications, p.90, February 25-26, 1999
• 18: C. E. Perkins, E. M. Royer, S. R. Das, and M. K. Marina. Performance comparison of two on-demand routing protocols for ad hoc networks. IEEE Personal Communications, 8(1):16--28, February 2001.
• 19: D. D. Perkins, H. D. Hughes, and C. B. Owen. Factors affecting the performance of ad hoc networks. In Proceedings of the IEEE International Conference on Communications (ICC), 2002.
• 20: E. M. Royer, P. M. Melliar-Smith, and L. E. Moser. An analysis of the optimum node density for ad hoc mobile networks. In Proceedings of the IEEE International Conference on Communications (ICC), Helsinki, Finland, June 2001.
• 21: J. Yoon, M. Liu, and B. Noble. Random waypoint considered harmful. In Proceedings of IEEE INFOCOM 2003, pages 1312--1321, San Francisco, CA, April 2003.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING

General Terms:
Experimentation, Performance, Theory

Keywords:
mobility model, renewal process, stationary distribution