Technical Report IC/2005/033http://lcawww.epfl.ch/Publications/LeBoudec/LeBoudecV04.pdfUnderstanding the Simulation of Mobility Models withPalm CalculusJean-Yves Le BoudecJune 23, 2005AbstractThe simulation of mobility models such as the random waypoint often cause subtle prob-lems, for example the decay of average speed as the simulation progresses, a difference be-tween the long term distribution of nodes and the initial one, and sometimes the instabilityof the model. All of this has to do with time averages versus event averages. This is a wellunderstood, but little known topic, called Palm calculus. In this paper we first give a very shortprimer on Palm calculus. Then we apply it to the random waypoint model and variants (withpause time, random walk). We show how to simply obtain the stationary distribution of nodesand speeds, on a connected (possibly non convex) area. We derive a closed form for the densityof node location on a square or a disk. We also show how to perform a perfect (i.e. transientfree) simulation without computing complicated integrals. Last, we analyze decay and explainit as either convergence to steady state or lack of convergence.Keywords: Mobility Model, Random Waypoint, Random Walk, Palm Calculus, Perfect Simula-tion.1 IntroductionThis paper reviews recent results about the random waypoint model; we give a short tutorial onPalm calculus, then we show how it helps understanding the simulation of the random waypoint.We also derive some new results like a closed form for the probability density function of the nodelocation.The simulation of the random waypoint model poses a surprising number of challenges, such as:• “Unfortunately, the vast majority of mobility models [...] suffer from decay; average speeddecreases until converging to some long-term average. Such decay provides an unsound1basis for simulation studies that collect results averaged over time, complicating the experi-mental process” [15].• “The random waypoint model is considered harmful” [14]. The “harmfulness” of randomwaypoint can be attributed to the uniform selection of speed over the interval [vmin,vmax],with vmin=0. Taking vmin> 0 solves the problem.• Simulation of some random waypoint models can be started in steady-state [8, 12]• The distribution of nodes is not uniform [4]These questions have been addressed in an ad-hoc fashion in the literature. The derivations involvelong and complex computations, leaving the reader with little understanding of the “why”. Ourstarting point is the observation that all of this can be very easily understood with a little bit ofPalm calculus. Palm calculus is a set of formulas that relate time averages to event averages. Theyare now well established, but not widely used or even known in applied areas.The reason is maybe that the construction of the Palm theory is complex in continuous time,whereas in discrete time it is a simple exercise on conditional probabilities [1, 7]. In this paperwe explain Palm calculus concisely, and rigorously in discrete time.Then we show how to apply Palm calculus to do simulation “the right way” for mobility models.In particular, we show how to easily compute the stationary distribution of nodes in a randomwaypoint model on any convex area (a problem considered difficult, or even intractable in [4]). Wealso show how to easily write a simulation that is in stationary regime at time 0 (this is called a“perfect” simulation). Last, we can also understand when the random waypoint model has at all astationary regime and when not.Being able to simulate the stationary distribution of a mobility model is important for two reasons.First, this speeds up considerably the warmup phase of a simulation (if we use a perfect simulationof the mobility model). As illustrated on Figure 10, the transient time for a realistic mobilitymodel may span several hundreds of seconds of simulated time, which is large compared to thetransients of simulations of networking protocols without mobility models. Second, this is usefulwhen comparing the performance of some system with or without mobility; many published papersinvariably distribute nodes uniformly in the static scenario, whereas, as we see later in this paper,the stationary distribution of nodes for a mobile scenario with the random waypoint is not uniform.A fair comparison should instead place the nodes for the static scenario according to the stationarydistribution of the mobile scenario.There are well established techniques for performing perfect simulation. The method in [9] appliesto a large class of Markov chains on which some partial ordering can be defined, and uses couplingfrom the past (sample trajectories starting in the past at different initial conditions). The techniquepresented in this paper is much simpler, as, unlike in the case of [9], we can obtain an explicitrepresentation of the stationary distribution.Our use of Palm calculus simplifies the understanding of existing results on mobility models. Italso extends them in a few directions. First we show that the stationary distribution can be com-puted explicitly for a wide class of models, including any arbitrary convex area. Second, we findhow to do perfect simulation, which involves a little more than simply finding the stationary distri-bution of locations and speeds. We show how to sample the stationary regime without computingdifficult integrals. In order to keep the focus on the main ideas, rather than clumsy technical details,we first start with the simplest random waypoint model, without pauses, on a convex area. The2generalization to variants (with pause times or random walk with wrapping) is given at the end ofthe paper.The rest of this paper is organized as follows. In Section 2 we describe the simplest randomwaypoint model. In Section 3 give a brief tutorial on Palm calculus. In Section 4 we apply Palmcalculus to obtain the stationary distribution of nodes and speeds, and to perfect simulation. InSection 5 we analyze when the random waypoint model has a stationary regime and when not. InSection 6 we generalize the results to variants of the random waypoint model: random waypointwith pauses, on non convex (but connected) area, random walk with reflection or wrapping.Notation And TermsA Geographical area over which random waypoint is definedaM(θ) Distance from M ∈ A to the boundary of A, in the direction θ (Figure 8)DnDistance Mn+1− Mn¯∆ Average distance between two