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

edit

The restricted random waypoint models the trajectory of a mobile user in a connected domain  . Given a sequence of locations   in  , called waypoints, the trajectory of the mobile is defined by traveling from one waypoint   to the next   along the shortest path in   between them. In the restricted setting, the waypoints are restricted to fall within one of a finite set of subdomains  .

On the trip between   and  , the mobile moves at constant speed   which is sampled from some distribution, usually a uniform distribution. The duration of the  -th trip is thus:

 

where   is the length of the shortest path in   between   and  .

The mobile may also pause at a waypoint, in which case the  -th trip is a pause at the location of the  -th waypoint, i.e.  . A duration   is drawn from some distribution   to indicate the end of the pause.

The transition instants   are the time at which the mobile reaches the  -th waypoint. They are defined as follow:

 

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

An initial phase   is chosen according to some initialization rule.

  •   is the index of the current sub-domain  .
  •   is the remaining number of waypoints to sample from this sub-domain  .
  •   is the index of the next sub-domain.
  • And   indicates whether the  -th trip is a pause.

Given phase  , the next phase   is chosen as follows. If   then   is sampled from some distribution and  . Otherwise, a new sub-domain   is sampled and a number   of trip to undergo in sub-domain   is sampled. The new phase is:  .

Given a phase   the waypoint   is set to   if  . Otherwise, it is sampled from sub-domain   if   and from sub-domain   if  .

Transient and stationary period

edit

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

edit
  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. ^ a b c 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