Random Waypoint

Random Waypoint is a very popular mobility model used in ad hoc networking research. It seeks to model the motion of a mobile node (representing, say, a person) around a fixed region R^*. The algorithm for it is parametrised by an interval [V_min,V_max] of valid movement speeds, and a value P₀ representing pausing time.

Algorithm:

1. Pick a random position in R^*, and jump to it.
2. Loop:
   1. Pause for P₀ seconds.
   2. Pick a random position X ∈ R^*.
   3. Pick a random speed s ∈ [V_min,V_max].
   4. Move towards X at constant speed s.
3. Jump to step 2.

Although it represents motion quite well (a person thinks of where they want to be, goes there, does something, repeats), some care should be taken with this algorithm. It does have a few non-obvious properties:

• For convex regions, there will be a greater node density in the middle of the region than near the edges. This is not necessarily non-realistic for most scenarios.
• If V_min = 0 (or close to), then the modelled situation will not have a steady state, and no average node speed (see [Yoon03]). Roughly, this is because as the simulation continues, more nodes can get trapped in travelling long distances at very low speeds. This causes the average node speed to steadily decrease over time. The obvious fix is to have a reasonable value for V_min.

References

[Camp02]

T. Camp, J. Boleng, V. Davies. "A Survey of Mobility Models for Ad Hoc Network Research". http://citeseer.nj.nec.com/camp02survey.html

[Yoon03]

J. Yoon, M. Liu, B. Noble. "Random Waypoint Considered Harmful". http://citeseer.nj.nec.com/yoon03random.html