The Random Trip Model, Part I: Stability

We define “random trip”, a generic mobility model for independent random motions of nodes, which contains as special cases: the random waypoint on convex or non convex domains, random walk on torus, billiards, city section, space graph, intercity and other models. We show that, for this model, a necessary and sufficient for a stationary regime to exist is that the mean trip duration (sampled at trip endpoints) is finite. When this holds, we show that the distribution of node mobility state converges to a time-stationary distribution, starting from any initial state. For the special case of random waypoint, we provide for the first time a proof and a sufficient and necessary condition of the existence of a stationary regime, thus closing a long standing issue. We show that random walk on torus and billiards belong to the random trip class of models, and establish that the long term distribution of node location for these two models is uniform, starting from any initial distribution, even in cases where the speed vector does not have circular symmetry. In part I, we describe the random trip model, show that all examples mentioned above satisfy the assumptions, and establish the main stability result. In part II, we describe the time stationary distribution in detail, and show how to perform a simulation that eliminates the initial transients (“perfect simulation”), for any random trip model that satisfies the stability condition.