skip to main content
article

The random trip model: stability, stationary regime, and perfect simulation

Published: 01 December 2006 Publication History

Abstract

We define "random trip", a generic mobility model for random, independent node motions, which contains as special cases: the random waypoint on convex or nonconvex domains, random walk on torus, billiards, city section, space graph, intercity and other models. We show that, for this model, a necessary and sufficient condition for a time-stationary regime to exist is that the mean trip duration (sampled at trip endpoints) is finite. When this holds, we show that the distribution of node mobility state converges to the time-stationary distribution, starting from the origin of an arbitrary trip. For the special case of random waypoint, we provide for the first time a proof and a sufficient and necessary condition of the existence of a stationary regime, thus closing a long standing issue. We show that random walk on torus and billiards belong to the random trip class of models, and establish that the time-limit distribution of node location for these two models is uniform, for any initial distribution, even in cases where the speed vector does not have circular symmetry. Using Palm calculus, we establish properties of the time-stationary regime, when the condition for its existence holds. We provide an algorithm to sample the simulation state from a time-stationary distribution at time 0 ("perfect simulation"), without computing geometric constants. For random waypoint on the sphere, random walk on torus and billiards, we show that, in the time-stationary regime, the node location is uniform. Our perfect sampling algorithm is implemented to use with ns-2, and is available to download from http://ica1www.epfl.ch/RandomTrip.

References

[1]
{1} G. Alsmeyer, "The Markov renewal theorem and related results," Markov Proc. Rel. Fields, vol. 3, pp. 103-127, 1997.
[2]
{2} S. Asmussen, Applied Probability and Queues, 2nd ed. New York: Springer, 2003.
[3]
{3} F. Baccelli and P. Brémaud, Elements of Queueing Theory: Palm Martingale Calculus and Stochastic Recurrences, 2nd ed. Berlin: Springer-Verlag, 2003, vol. 26, Applications of Mathematics.
[4]
{4} C. Bettstetter, "Mobility modeling in wireless networks: categorization, smooth movement, and border effects," Mobile Comput. Commun. Rev., vol. 5, no. 3, pp. 55-67, 2001.
[5]
{5} C. Bettstetter, "The node distribution of the random waypoint mobility model for wireless ad hoc networks," IEEE Trans. Mobile Comput., vol. 2, no. 3, pp. 257-269, Jul.-Sep. 2003.
[6]
{6} L. Blažević, J.-Y. Le Boudec, and S. Giordano, "A location-based routing method for mobile ad hoc networks," IEEE Trans. Mobile Comput., vol. 3, no. 4, pp. 97-110, Dec. 2004.
[7]
{7} J.-Y. Le Boudec and M. Vojnović, "Perfect simulation and stationarity of a class of mobility models," in Proc. IEEE INFOCOM 2005, Miami, FL, Mar. 2005, pp. 2743-2754.
[8]
{8} J.-Y. Le Boudec and M. Vojnović, "The Random Trip model: Stability, stationary regime, and perfect simulation," Microsoft Research, Cambridge, U.K., Tech. Rep. MSR-TR-2006-26, 2006 {Online}. Available: http://research.microsoft.com/research/pubs/view.aspx?type=Technical%20Report&id =1070
[9]
{9} J. Broch, D. A. Maltz, D. B. Johnson, Y.-C. Hu, and J. Jetcheva, "A performance comparison of multi-hop wireless ad hoc network routing protocols,"Mobile Comput. Netw., pp. 85-97, 1998.
[10]
{10} T. Camp, J. Boleng, and V. Davies, "A survey of mobility models for ad hoc network research," WCMC: Special Issue on Mobile Ad Hoc Networking: Research, Trends and Applications, vol. 2, no. 5, pp. 483-502, 2002.
[11]
{11} H. Hartenstein, C. Bettstetter, and X. Pérez-Costa, "Stochastic properties of the random waypoint mobility model," ACM/Kluwer Wireless Networks, Special Issue on Modeling and Analysis of Mobile Networks, vol. 10, no. 5, pp. 555-567, Sep. 2004.
[12]
{12} G. Hardy, J. E. Littlewood, and G. Pólya, Inequalities, 2nd ed. Cambridge, U.K.: Cambridge Univ. Press, 1952.
[13]
{13} A. Jardosh, E. M. Belding-Royer, K. C. Almeroth, and S. Suri, "Towards realistic mobility models for mobile ad hoc networking," in Proc. ACM MOBICOM 2003, San Diego, CA, 2003, pp. 217-229.
[14]
{14} J.-Y. Le Boudec, "On the stationary distribution of speed and location of random waypoint," IEEE Trans. Mobile Comput., vol. 4, no. 4, pp. 404-405, Jul.-Aug. 2005.
[15]
{15} J.-Y. Le Boudec, "Understanding the simulation of mobility models with palm calculus,"Perform. Eval., in press, also available as EPFL Tech. Rep. EPFL/IC/2004/53.
[16]
{16} G. Lin, G. Noubir, and R. Rajamaran, "Mobility models for ad hoc network simulation," in Proc. IEEE INFOCOM 2004, Hong Kong, Apr. 2004, pp. 454-463.
[17]
{17} T. Lindvall, Lectures on the Coupling Method. New York: Dover, 2002, originally published by Wiley in 1992.
[18]
{18} M. Drmota and R. F. Tichy, Sequences, Discrepancies and Applications . New York: Springer, 1997, vol. 1651, Lecture Notes in Mathematics.
[19]
{19} P. Nain, D. Towsley, B. Liu, and Z. Liu, "Properties of random direction models," in Proc. IEEE INFOCOM 2005, Miami, FL, Mar. 2005, pp. 1897-1907.
[20]
{20} W. Navidi and T. Camp, "Stationary distributions for the random waypoint mobility model," IEEE Trans. Mobile Comput., vol. 3, no. 1, pp. 99-108, Jan.-Feb. 2004.
[21]
{21} J. G. Propp and D. B. Wilson, "Exact sampling with coupled Markov chains and applications to statistical mechanics," Random Struct. Algor., vol. 9, no. 1-2, pp. 223-252, 1996.
[22]
{22} T. Camp, W. Navidi, and N. Bauer, "Improving the accuracy of random waypoint simulations through steady-state initialization," in Proc. 15th Int. Conf. Modeling and Simulation (MS'04), Marina del Rey, CA, Mar. 2004, pp. 319-326.
[23]
{23} J. Yoon, M. Liu, and B. Noble, "Random waypoint considered harmful," in Proc. IEEE INFOCOM 2003, San Francisco, CA, pp. 1312-1321.
[24]
{24} J. Yoon, M. Liu, and B. Noble, "Sound mobility models," in Proc. ACM MOBICOM 2003, San Diego, CA, pp. 205-216.

Cited By

View all
  • (2021)MoverProceedings of the ACM on Interactive, Mobile, Wearable and Ubiquitous Technologies10.1145/34949975:4(1-21)Online publication date: 30-Dec-2021
  • (2018)Improved bounds on information dissemination by Manhattan Random Waypoint modelProceedings of the 26th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems10.1145/3274895.3274917(139-148)Online publication date: 6-Nov-2018
  • (2016)Improving hybrid ad hoc networksApplied Soft Computing10.1016/j.asoc.2015.12.01241:C(1-14)Online publication date: 1-Apr-2016
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image IEEE/ACM Transactions on Networking
IEEE/ACM Transactions on Networking  Volume 14, Issue 6
December 2006
247 pages

Publisher

IEEE Press

Publication History

Published: 01 December 2006
Published in TON Volume 14, Issue 6

Author Tags

  1. mobility models
  2. random waypoint
  3. simulation

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)0
  • Downloads (Last 6 weeks)0
Reflects downloads up to 15 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2021)MoverProceedings of the ACM on Interactive, Mobile, Wearable and Ubiquitous Technologies10.1145/34949975:4(1-21)Online publication date: 30-Dec-2021
  • (2018)Improved bounds on information dissemination by Manhattan Random Waypoint modelProceedings of the 26th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems10.1145/3274895.3274917(139-148)Online publication date: 6-Nov-2018
  • (2016)Improving hybrid ad hoc networksApplied Soft Computing10.1016/j.asoc.2015.12.01241:C(1-14)Online publication date: 1-Apr-2016
  • (2016)BETA random waypoint mobility model for wireless network simulationAd Hoc Networks10.1016/j.adhoc.2016.06.00148:C(93-100)Online publication date: 15-Sep-2016
  • (2015)Information spreading in dynamic graphsDistributed Computing10.1007/s00446-014-0219-228:1(55-73)Online publication date: 1-Feb-2015
  • (2014)Efficient Data Transfer by Mobility Adjustment Algorithm for Clustered Mobile Ad-Hoc NetworksCybernetics and Information Technologies10.2478/cait-2014-001914:2(50-64)Online publication date: 1-Jul-2014
  • (2014)A Taxonomy and Survey of Microscopic Mobility Models from the Mobile Networking DomainACM Computing Surveys10.1145/261697347:1(1-32)Online publication date: 14-Jul-2014
  • (2014)Performance evaluation of routing protocols based on realistic traces from driving simulatorProceedings of the 8th International Conference on Ubiquitous Information Management and Communication10.1145/2557977.2558033(1-7)Online publication date: 9-Jan-2014
  • (2014)Parsimonious flooding in geometric random-walksJournal of Computer and System Sciences10.1016/j.jcss.2014.06.00281:1(219-233)Online publication date: 1-Oct-2014
  • (2013)Opportunistic MANETsIEEE/ACM Transactions on Networking10.1109/TNET.2012.220440721:2(610-620)Online publication date: 1-Apr-2013
  • Show More Cited By

View Options

Login options

Full Access

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media