The Random Trip Mobility Model
New: The paper that describes the random trip model won the Infocom 2005 Best Paper Award
Welcome to the random trip mobility model page. You will find here a description of the model and ns-2 code to use it in simulations.
The random trip model is a generic mobility model that generalizes random waypoint and random walk to realistic scenarios.
You can use it to give a realistic flavour to your simulations. It is implemented in ns-2 and can be used without license.
The implementation performs perfect initialization, i.e. the mobility model has no transient phase.
The Random Trip Models
The Random Trip Models, a wide class of mobility models, contain many existing mobility models in one, plus some new ones.
Examples include random waypoint on
general connected domain, restricted random waypoint, and random walk models with either wrap-around or reflection.
Illustration of some random trip models
A description of the model and its properties can be found in:
If well-defined, random trip models feature:
- Existence of a unique steady-state distribution
- Perfect simulation is easy to do
- No need to know geometric normalization constants when they are difficult to compute -- bound on diameter of the mobility domain suffices
ns-2 code
Code to use random trip with ns-2 network simulator is freely available from:
- ns-2 code, by S. PalChaudhuri, Rice University.
The code includes the model with perfect sampling, i.e. the initial mobility state can be set in steady state at the beginning
of the simulation, so that annoying transient artifacts are avoided.
Importance of perfect mobility simulations
More details in:
Slide shows
- Cambridge University, November 2005, "Simulation of Random Trip Mobility Models: Stationarity, Perfect Simulation and Long Range Dependence", ppt
Tutorials
- Random Trip tutorial, Mobicom 2006, with Frequently Asked Questions ppt
- Tutorial: "Understanding the Simulation of Mobility Models with Palm Calculus", J.-Y. Le Boudec, EPFL technical report IC/2004/53, 2004;
pdf
- Slides presented at Performance 2005
References
We give below a non-exhaustive catalog of random trip models. If anyone knows of a random trip model, which we omitted to list below, please
send us a link (contact: see below).
Surveys
- "A Survey of Mobility Models for Ad Hoc Network Research," T. Camp, J. Boleng, and V. Davies, Wireless Communication & Mobile Computing (WCMC): Special Issue on Mobile Ad Hoc Networking Research, Trends and Applications, Vol. 2, No. 5, pp. 483-502, 2002,
pdf
Random Waypoint
- See random waypoint in action: htm.
See also applet by Esa Hyytia (TKK, Helsinki University of Technology).
- "Dynamic Source Routing in Ad Hoc Wireless Networks," D. B. Johnson and D. A. Maltz, Mobile Computing, edt. by T. Imielinski and H. Korth,
Chapter 5, p. 153-181, Kluwer Academic Publishers, 1996; ps.
Advent of random waypoint model: "Each host is initially placed at a random position within in the simulation area.
As the simulation progresses, each host pauses at its current location for a period, which we call the pause time, and then randomly chooses a new
location to move to and a velocity between 0.3 and 0.7 meters per second at which to move there. Each host continues this behavior, alternately pausing
and moving to a new location, for the duration of the simulation."
- "Stationary Distributions for the Random Waypoint Model," W. Navid and T. Camp, IEEE Transactions on Mobile Computing, Vol. 3, No. 1, pp. 99-108, 2004;
technical report version pdf; related technical report
pdf
"We derive the stationary distributions for location, speed, and pause time for the random waypoint mobility model. We then show how to implement the random waypoint
mobility model in order to construct more efficient and reliable simulations for mobile ad hoc networks."
- "A Location Based Routing Method for Mobile Ad Hoc Networks," Lj. Blazevic, J.-Y. Le Boudec, and S. Giordano, IEEE Transactions on Mobile
Computing, Vol. 3, No. 4, Dec 2004; pdf.
Defines a restricted random waypoint model.
- "Random Waypoint Considered Harmful," J. Yoon, M. Liu, and B. Noble, IEEE Infocom 2003, San Franciso, CA;
pdf.
"Our findings show that this model fails to provide a "steady state" in
that the average nodal speed consistently decreases over time, and therefore should not be directly used for simulations."
- "Sound Mobility Models," J. Yoon, M. Liu, B. Noble, ACM Mobicom 2003, San Diego, California, 2003;
pdf
" ... 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."
- The Node Distribution of the Random Waypoint Mobility Model for Wireless Ad Hoc Networks," C. Bettstetter, G. Resta, and P. Santi,
IEEE Transactions on Mobile Computing, Vol. 2, No. 3, pp 257-269, July-Sept 2003;
pdf (if subscribed)
- "Towards Realistic Mobility Models for Mobile Ad Hoc Networks," A. Jardosh, E. M. Belding-Royer, K. C. Almeroth, S. Suri, ACM Mobicom 2003, San Diego, CA, September 2003;
pdf.
Proposes a specific construction of space graphs for mobility domain. The model is restricted random waypoint.
Random Walk
- "Properties of Random Direction Models," P. Nain, D. Towsley, B. Liu, and Z. Liu, INRIA technical report RR-5284, July 2004;
pdf
"We consider two variations, the random direction model with wrap around and with reflection. We establish a simple relationship between these two models and, for both, show that positions and directions are uniformly distributed
in steady-state for a class of Markov movement models regardless of initial position."
Empirically-based models
Maintained by Jean-Yves Le Boudec and Milan Vojnovic. Last update: Nov 12, 2004. Contact: email.