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.^[1] in order to model intercity examples and later defined in a more general setting by Le Boudec et al.^[2]

Definition

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

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

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

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

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

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

${\displaystyle {\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 ${\displaystyle I_{0}=(i,j,r,p)}$ is chosen according to some initialization rule.

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

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

Given a phase ${\displaystyle I_{n}=(i,j,r,p)}$ the waypoint ${\displaystyle M_{n+1}}$ is set to ${\displaystyle M_{n}}$ if ${\displaystyle p={\text{pause}}}$. Otherwise, it is sampled from sub-domain ${\displaystyle A_{i}}$ if ${\displaystyle r>0}$ and from sub-domain ${\displaystyle A_{j}}$ if ${\displaystyle 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.^[2] 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)^[2] and a Python implementation is available on GitHub.^[3]

References

1. Blazevic, L.; Le Boudec, J.-Y.; Giordano, S. (2005). "A location-based routing method for mobile ad hoc networks". IEEE Transactions on Mobile Computing. 4 (2): 97–110. doi:10.1109/tmc.2005.16. ISSN 1536-1233. S2CID 6215410.
2. Le Boudec, J.-Y.; Vojnovic, M. (2005). "Perfect simulation and stationarity of a class of mobility models". Proceedings IEEE 24th Annual Joint Conference of the IEEE Computer and Communications Societies. Vol. 4. IEEE. pp. 2743–2754. doi:10.1109/infcom.2005.1498557. ISBN 0780389689. S2CID 361135.
3. Harbulot, Julien (2019-06-02), Simulation and initialization in stationary regime of the mobility model called Restricted Random Waypoint model, along with some examples including the four squares setting and city section.: jul.., retrieved 2019-06-02