Stationary Distributions for theRandom Waypoint Mobility Model∗†‡William Navidi and Tracy CampDepartment of Mathematical and Computer SciencesColorado School of MinesGolden, Colorado [email protected]; [email protected] 12th, 2003AbstractIn simulations of mobile ad hoc networks, the probability distribution governing the move-ment of the nodes typically varies over time, and converges to a “steady-state” distribution,known in the probability literature as the stationary distribution. Some published simulationresults ignore this initialization discrepancy. For those results that attempt to account for thisdiscrepancy, the practice is to discard an initial sequence of observations from a simulationin the hope that the remaining values will closely represent the stationary distribution. Thisapproach is inefficient and not always reliable. However, if the initial locations and speeds ofthe nodes are chosen from the stationary distribution, convergence is immediate and no dataneed be discarded. We derive the stationary distributions for location, speed, and pause timefor the random waypoint mobility model. We then show how to implement the random way-point mobility model in order to construct more efficient and reliable simulations for mobilead hoc networks. Simulation results, which verify the correctness of our method, are included.In addition, implementation of our method for the NS-2 simulator is available.Keywords: simulation of mobile ad hoc networks, random waypoint mobility model, mobilitymodels∗This work was partially supported by National Science Foundation grant ANI-0208352.†Research group’s URL is http://toilers.mines.edu‡Reference for this manuscript: Technical Report MCS-03-04, The Colorado School of Mines, April 2003.11 IntroductionMobile ad hoc networks are often studied through simulation, and their performance can dependheavily on the mobility model that governs the movement of the nodes [1]. In most cases, theprobability distribution of the initial locations and speeds of the nodes differs from the distributionat later points in the simulation. In fact, it is generally true that the probability distributions ofboth location and speed vary continuously over time, and converge to a “steady-state” distribution,known in the probability literature as the stationary distribution. At any given point in the simu-lation, the distribution of location and speed is a weighted average of the initial distribution andthe stationary distribution, with the weight shifting from the initial distribution to the stationarydistribution as the simulation progresses.Because the distributions of location and speed vary as a simulation progresses, the performance ofthe network can vary as well. In particular, network performance early in a simulation may differsubstantially from the performance later in the simulation [2]. Up to now, the primary methodfor dealing with this problem (when the problem is addressed at all) has been to discard an initialsequence of observations [3]. The hope is that the values observed for location and speed pastthis initial sequence will have been sampled approximately from the stationary distribution. Thisapproach has two drawbacks. First, it is inefficient, since it requires the discarding of data. Second,and more importantly, it is difficult to know just how long a sequence one needs to discard in orderto be safely near stationarity. As we will show below, if the minimum speed is low, convergencecan take more than 1000 seconds of simulation time.We focus our discussion on the random waypoint mobility model [4, 5]. In this model, each nodeis assigned an initial location (x0,y0), a destination (x1,y1), and a speed S. The points (x0,y0) and(x1,y1) are chosen independently and uniformly on the region in which the nodes move. The speedis chosen uniformly on an interval (v0,v1), independently of both the initial location and destina-2tion1. After reaching the destination, a new destination is chosen from the uniform distribution, anda new speed is chosen uniformly on (v0,v1), independently of all previous destinations and speeds.Nodes may pause upon reaching each destination, or they may immediately begin traveling to thenext destination without pausing. If they pause, the pause times are chosen independently of speedand location.Virtually all published simulation results that use the random waypoint mobility model begin withthe nodes placed uniformly in the simulation area. Of course, this initial random distribution ofnodes is not representative of the manner in which nodes distribute themselves when moving. Thestationary distributions of location and speed in the random waypoint mobility model are in factquite different from the uniform distribution. In particular it has been noticed [2, 7, 8] that thestationary distribution of the location of a node is more concentrated near the center of the regionin which the nodes move, since nodes traveling between uniformly chosen points spend more timenear the center than near the edges. Yoon et al. [2] noticed that the stationary distribution of thespeed differs from the uniform as well, and showed in particular that if the minimum speed v0is taken to be 0, the mean node speed approaches 0. A variant of the random waypoint mobilitymodel is presented in [11], but the stationary distribution for this model differs from the uniformas well. Blough et al. [13] determined that if the nodes move according to a random walk ratherthan according to the random waypoint mobility model, the stationary distribution of the locationis close to uniform.One implementation of the random waypoint mobility model (setdest) begins with a pause at theinitial location [5, 6]. Another implementation (mobgen) begins with the nodes moving [3]; thus,the first pause occurs upon reaching the first destination. Once the initial locations are uniformlychosen, simulations that use setdest (or a variant of it) have nodes begin paused at their initial loca-1In practice, the distribution for speed is usually uniform. In principle, any distribution is possible. We discussalternatives for speed in Section 5.3tions (the pause time is chosen from a uniform distribution). In other words, each node remains inits initial uniformly distributed position for a given initial pause time. Simulations that use mobgen(or a variant of it) begin with nodes moving from their initial locations to their first destinationsimmediately. For this