Random Waypoint Model

Random Waypoint (RWP) model is a commonly used synthetic model for mobility, e.g., in Ad Hoc networks. It is an elementary model which describes the movement pattern of independent nodes by simple terms.

Briefly, in the RWP model:

Each node moves along a zigzag line from one waypoint P_i to the next P_i+1.
The waypoints are uniformly distributed over the given convex area, e.g. unit disk.
At the start of each leg a random velocity is drawn from the velocity distribution.
(in the basic case the velocity is constant 1)
Optionally, the nodes may have so-called "thinking times" when they reach each waypoint before continuing on the next leg, where durations are independent and identically distributed random variables.

1. Common Problems with Random Waypoint Model

Zig-zag trajectories: RWP model is elementary and it is easy to argue about the paths being unnatural. Then again, any practical protocol or mechanism should be robust and give a reasonable performance with a wide range of moving patterns, including movement similar to RWP model.
Velocity distribution: The most common problem with simulation studies using random waypoint model is a poor choice of velocity distribution [5], e.g., uniform distribution U(0,V_max). Such velocity distributions (which seem to be common with NS-2 simulations!) lead to a situation where at the stationary state each node stops moving. In order to avoid this the velocity distribution should be such that
1/E[1/V] > 0
Note that the mean time a node spends on a single leg is proportional to 1/E[1/V].

2. Random Waypoint on the Border (RWPB)

In the (standard) RWP model the waypoints are uniformly distributed over the given domain. Alternatively, the waypoints can be uniformly distributed on the border of the domain and this model is referred to as the "Random waypoint on the border" (RWPB) model. The spatial node density resulting from RWPB model is quite different from the RWP model, i.e. the probability mass shifts from the center of the area to the borders. In particular, if the border contains a straight line segment, then there is a positive probability that a random leg resides on the line segment (resulting in a 1-dimension pdf on each line segment on the border).

3. Markovian Waypoint Model (MWP)

The RWP model can be further extended, e.g., by allowing the next waypoint depend on the current waypoint. This leads to a so-called Markovian Waypoint Model (MWP) [11], where one can also define leg depending velocity distributions (velocity from P₁ to P₂ is no longer i.i.d. random variable but depends on P₁ and P₂) and random pause times during the transition between two waypoints.

References:

David B. Johnson and David A. Maltz. Dynamic source routing in ad hoc wireless networks. In Tomasz Imielinski and Hank Korth, editors, Mobile Computing, volume 353, pages 153-181. Kluwer Academic Publishers, 1996. Chapter 5.
C. Bettstetter and C. Wagner. The spatial node distribution of the random waypoint mobility model. In Proceedings of German Workshop on Mobile Ad Hoc networks (WMAN), Ulm, Germany, March 2002.
C. Bettstetter, H. Hartenstein, 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, 10(5), September 2004.
G. Resta and P. Santi. An analysis of the node spatial distribution of the random waypoint model for Ad Hoc networks. In Proceedings of ACM Workshop on Principles of Mobile Computing (POMC), pages 44-50, Toulouse, France, October 2002.
J. Yoon, M. Liu, and B. Noble. Random waypoint considered harmful. In Proceedings of Infocom '03, pages 1312-1321, San Fransisco, California, USA, April 2003. IEEE.
Christian Bettstetter, Giovanni Resta, and Paolo Santi. The node distribution of the random waypoint mobility model for wireless ad hoc networks. IEEE Transactions on Mobile Computing, 2(3):257-269, July-September 2003.
W. Navidi and T. Camp. Stationary distributions for the random waypoint mobility model. IEEE Transactions on Mobile Computing, 3(1):99-108, January-March 2004.
Jean-Yves Le Boudec. Understanding the Simulation of Mobility Models with Palm Calculus. Technical report, EPFL, 2005.
Jean-Yves Le Boudec and Milan Vojnovic. The Random Trip Model: Stability, Stationary Regime, and Perfect Simulation. Technical report, EPFL, 2006.
Esa Hyytiä, Pasi Lassila, and Jorma Virtamo. Spatial Node Distribution of the Random Waypoint Mobility Model with Applications. IEEE Trans. Mobile Computing, 2006. (link)
Esa Hyytiä and Jorma Virtamo. Random waypoint model in n-dimensional space. Operations Research Letters, vol. 33/6, pp. 567-571, 2005. (link)
Esa Hyytiä and Jorma Virtamo. Random waypoint model in cellular networks. Wireless Networks, Online First, 2006. (link)
Esa Hyytiä, Pasi Lassila and Jorma Virtamo. A Markovian Waypoint Mobility Model with Application to Hotspot Modeling. In Proceedings of IEEE ICC 2006, June 2006. (link)

Back to the RWP applet page.

Esa Hyytiä, 2004-2005.