Restricted random waypoint model

In mobility management, the restricted random waypoint model is a random model for the movement of mobile users, similar to the random waypoint model, but where the waypoints are restricted to fall within one of a finite set of sub-domains. It was originally introduced by Blaževic et al. in order to model intercity examples and later defined in a more general setting by Le Boudec et al.

Definition

The restricted random waypoint models the trajectory of a mobile user in a connected domain $A$. Given a sequence of locations $M_{0},M_{1},...$ in $A$, called waypoints, the trajectory of the mobile is defined by traveling from one waypoint $M_{n}$ to the next $M_{n+1}$ along the shortest path in $A$ between them. In the restricted setting, the waypoints are restricted to fall within one of a finite set of subdomains $A_{i}\subset A$.

On the trip between $M_{n}$ and $M_{n+1}$, the mobile moves at constant speed $V_{n}$ which is sampled from some distribution, usually a uniform distribution. The duration of the $n$-th trip is thus:

$S_{n}={\frac {d(M_{n},M_{n+1})}{V_{n}}}$

where $d(x,y)$ is the length of the shortest path in $A$ between $x$ and $y$.

The mobile may also pause at a waypoint, in which case the $n$-th trip is a pause at the location of the $n$-th waypoint, i.e. $M_{n+1}=M_{n}$. A duration $S_{n}$ is drawn from some distribution $F_{\text{pause}}$ to indicate the end of the pause.

The transition instants $T_{n}$ are the time at which the mobile reaches the $n$-th waypoint. They are defined as follow:

${\begin{cases}T_{0}{\text{ is chosen by some initialization rule }}\\T_{n+1}=T_{n}+S_{n}\end{cases}}$

The sampling algorithm for the waypoints depends on the phase of the simulation.

An initial phase $I_{0}=(i,j,r,p)$ is chosen according to some initialization rule.

• $i$ is the index of the current sub-domain $A_{i}$.
• $r$ is the remaining number of waypoints to sample from this sub-domain $A_{i}$.
• $j$ is the index of the next sub-domain.
• And $p\in \{{\text{pause}},{\text{move}}\}$ indicates whether the $n$-th trip is a pause.

Given phase $I_{n}=(i,j,r,p)$, the next phase $I_{n+1}$ is chosen as follows. If $r>0$ then $p'$ is sampled from some distribution and $I_{n+1}=(i,j,r-1,p')$. Otherwise, a new sub-domain $k$ is sampled and a number $r'$ of trip to undergo in sub-domain $j$ is sampled. The new phase is: $I_{n+1}=(j,k,r',{\text{move}})$.

Given a phase $I_{n}=(i,j,r,p)$ the waypoint $M_{n+1}$ is set to $M_{n}$ if $p={\text{pause}}$. Otherwise, it is sampled from sub-domain $A_{i}$ if $r>0$ and from sub-domain $A_{j}$ if $r=0$.

Transient and stationary period

In a typical simulation models, when the condition for stability is satisfied, simulation runs go through a transient period and converge to the stationary regime. It is important to remove the transients for performing meaningful comparisons of, for example, different mobility regimes. A standard method for avoiding such a bias is to (i) make sure the used model has a stationary regime and (ii) remove the beginning of all simulation runs in the hope that long runs converge to stationary regime. However the length of transients may be prohibitively long for even simple mobility models and a major difficulty is to know when the transient ends. An alternative, called "perfect simulation", is to sample the initial simulation state from the stationary regime.

There exists algorithms for perfect simulation of the general restricted random waypoint. They are described in Perfect simulation and stationarity of a class of mobility models (2005) and a Python implementation is available on GitHub.