ISR Distinguished Lecturer Series
Understanding the simulation of mobility models
Jean-Yves Le Boudec
Ecole Polytechnique Fédérale de Lausanne (EPFL)
The simulation of mobility models often causes problems due to long transients or even lack of convergence to a stationary regime ("The random waypoint model considered harmful"). To analyze this, we define a formally sound framework, which we call the random trip model.
The framework is a generic mobility model for independent mobiles that contains as special cases: the random waypoint on convex or non convex domains, random walk, billiards, city section, space graph and other models.
We use Palm calculus to study the model and give a necessary and sufficient condition for a stationary regime to exist. When this condition is satisfied, we compute the stationary regime and give an algorithm to start a simulation in steady state (perfect simulation). The algorithm does not require knowledge of geometric constants. For the special case of random waypoint, we provide for the first time a proof and a necessary and sufficient condition for the existence of a stationary regime. Further, we extend its applicability to a broad class of nonconvex and multi-site examples, and provide a ready-to-use algorithm for perfect simulation. For the special case of random walks or billiards, we show that, in the stationary regime, the mobile location is uniformly distributed and is independent of the speed vector, and that there is no speed decay. Our framework provides a rich set of well understood models that can be used to simulate mobile networks with independent node movements. Our perfect sampling is implemented to use with ns-2, and it is freely available to download.
We lastly discuss how random trip mobility model accommodates various mobility properties (some of which may be invariants of real-world mobility), such as, for example, recent empirical evidence that the distribution of human inter-contact times are heavy-tailed, long-range dependent models and their implications on simulation averaging, and parameter settings of node mobility to achieve a target time-stationary distribution of node location.
Jean-Yves Le Boudec is full professor at EPFL, Fellow of the IEEE and Director of the Institute of Communication Systems. He graduated from Ecole Normale Superieure de Saint-Cloud, Paris, where he obtained the Agregation in Mathematics in 1980 (rank 4) and received his doctorate in 1984 from the University of Rennes, France. From 1984 to 1987 he was with INSA/IRISA, Rennes. In 1987 he joined Bell Northern Research, Ottawa, Canada, as a member of scientific staff. In 1988, he joined the IBM Zurich Research Laboratory where he was manager of the Customer Premises Network Department.
He joined EPFL as Associate Professor in 1994. His interests are in the performance and architecture of communication systems. He co-authored the book Network Calculus (Springer, 2006). He received the Infocom 2005 Best Paper Award with Milan Vojnovic of Microsoft Research for elucidating the perfect simulation and stationarity of mobility models.
He is or has been on the program committee or editorial board of many conferences and journals, including Sigcomm, Sigmetrics, Infocom, Performance Evaluation and ACM/IEEE Transactions on Networking.
Tony Ephremides and Eyad Abed