# On Lookahead Strategy for Movement-Based Location Update: A General Formulation

Vicente Casares-Giner

<figure><img src="image_1.png" /></figure>

To cite this version:

Vicente Casares-Giner. On Lookahead Strategy for Movement-Based Location Update: A General Formulation. Performance Evaluation of Computer and Communication Systems (PERFORM), Oct 2010, Vienna, Austria. pp.153-166, 10.1007/978-3-642-25575-5_13. hal-01586908

HAL Id: hal-01586908

https://inria.hal.science/hal-01586908

Submitted on 13 Sep 2017

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# On Lookahead Strategy for Movement-based Location Update. A General Formulation

Vicente Casares-Giner

GIRBA Group - Instituto ITACA, Universidad Politécnica de Valencia,
Camino de Vera s/n. 46022 Valencia, Spain
vcasares@upvnet.upv.es

**Abstract.** Location management deals with the procedure to update the current location of a mobile terminal (MT) and with the procedure to deliver incoming calls to that called MT. Basically, the performance evaluation of location management procedures are dependent on the MT's mobility behavior, on the MT's cell residence time and on the call arrival process to the MT. In the open literature, the typical analysis for location management has been addressed under the assumptions of a random walk mobility model, the exponential cell sojourn time of the MT -some times relaxed to a general probability distribution function- and the exponential inter-arrival time distribution for incoming calls. However, the random walk model seems not to be valid as many mobile users follow some daily trajectories, such as from home to the working place, from the working place to the shopping center, etc. To reflect a more realistic movement pattern, we propose a directional oriented mobility model. And as a consequence of that, we also propose a lookahead procedure combined with the movement-based location update scheme, with the main idea of saving signaling traffic through the air interface. In the lookahead strategy we analytically derive closed form expressions for the mean number of location update (LU) messages triggered by the MT between two consecutive call arrivals and the paging probabilities to evaluate the paging cost under some selective paging strategies. The analysis has been carried out assuming a general cell residence time and a renewal point process for call arrivals to the MT.

**Keywords:** Location update, selective paging

## 1 Introduction

Mobility management is a key functionality that aims in providing ubiquitous telecommunication services in wireless mobile access networks. Mobility management procedures can be classified as handoff management and location management. The first procedure aims to guarantee the continuity of an on going call when the mobile terminal (MT) visits a new cell. Location management is defined as a set of procedures that allow a MT being located at anytime, anywhere, so that incoming calls may be delivered to that MT. This set consists of location update (LU) and call delivery (CD). The LU process consists of maintaining the
MT location information updated in the system database. The database entry of an MT is updated whenever the MT triggers an LU message or an incoming call is delivered. The CD procedure is decomposed into two steps: interrogation and terminal paging (PG). Firstly, in the interrogation step, the system database is queried to obtain the Registration Area (RA) where the MT is supposed to be in. Afterwards, the PG procedure follows, i.e., the MT is searched by polling the set of cells of the RA.

There is a trade off between LU and PG procedures. As the number of LU messages increases, the LU cost becomes higher but the PG cost decreases as the MT position is known more accurately. On the other hand, the lower is the number of LUs, the lower is the LU cost; but the uncertainty of the MT position is higher and the PG cost increases.

The performance of a location management procedure is dependent on the mobility patterns of the MT. One of the most extended mobility models used in the evaluation of location tracking is the random walk mobility model, [1] [2]. However, the random walk model is rather unrealistic since many MTs follow daily trajectories such as, as we have said before, from home to the working place, from home to the recreation center, etc. Therefore, in order to evaluate in a proper way the signaling load associated to mobility tracking, more realistic mobility models are required [3].

In this work we consider a mobility model with a certain directionality, and as a consequence of that information, an enhanced movement-based mobility tracking procedure is proposed. The proposal is based on the lookahead tracking principle and it is illustrated and evaluated in a 2-D scenario.

# 2 Movement-based Location Update

## 2.1 Scenario and mobility model

Although hexagonal and square cell layouts in a 2-D scenario can be considered, here we analyze our proposal in the hexagonal cell layout [4]. Cells are located in a plane and they are enumerated according to Fig. 1. The mobility model is as follows. After a certain sojourn or cell dwell time in cell (i, j), characterized by a probability density function (pdf) $f_{m; i, j}(t)$, our MT will travel in the direction of angles $\{i\pi/3\}$ with probabilities $\{p_i\}$, counterclockwise, for $i = 0, 1, 2, 3, 4, 5$, respectively. We will assume that all cells have the same size, and that $f_{m; i, j}(t) = f_m(t)$. The following probabilities $\{p_i\}$ are considered for our single parameter mobility model

$$p_0 = \frac{\beta^3}{D(\beta)}; \quad p_1 = p_5 = \frac{\beta^2}{D(\beta)}; \quad p_2 = p_4 = \frac{\beta}{D(\beta)}; \quad p_3 = \frac{1}{D(\beta)}$$

$$\text{with } D(\beta) = (\beta^3 + 2\beta^2 + 2\beta + 1) = (\beta + 1)(\beta^2 + \beta + 1);$$

where $\beta$ is positive number, $\beta \in (0, 1)$ or $\beta \in (1, \infty)$, and $D(\beta)$ is a normalization factor. Clearly, the parameter $\beta$ provides a wide range of the directionality
of the MT's movement. For instance, if $\beta = 1$, $p_i = 1/6, \forall i$, we have the standard random walk model. For $\beta > 1$ we have $p_o > p_1 = p_5 > p_2 = p_4 > p_3$. Clearly when $\beta \to \infty, p_0 \to 1$ the MT will always travel in the same direction, i.e. according to Fig. 1, towards the right hand side. The higher is $\beta$ the higher the directionality of our MT will be.

<figure><img src="image_3.png" /><figcaption>**Fig. 1.** Illustration of the lookahead strategy for movement based location update, with movement-counter threshold $M = 4$ and $\Delta = \{(3, 3), (3, 4), (4, 3), (4, 4)\}$.</figcaption></figure>

## 2.2 Lookahead strategy

Let us consider that at time $t = 0^+$ our MT is located at cell $(i, j) = (0, 0)$, see Fig. 1. We choose a set of target cells, the $\Delta$ set, that our MT will likely find along its trajectory. For example, if $\beta > 1$ cells (1, 1), (2, 2), (3, 3), ... can be reached by our MT with higher probability than cells $(-1, -1)$, $(-2, -2)$, $(-3, -3)$, ... . Then, each time the MT visits a cell that does not belong to the $\Delta$ set, its movement counter is increased in one unit. When the movement counter reaches a certain threshold, say $M$, it will send a LU message to the network. But, if the MT visits any cell of the $\Delta$ set before the threshold $M$ is reached, it will reset its movement counter. Fig. 1 depicts the case of $M = 4$ and $\Delta = \{(3, 3), (3, 4), (4, 3), (4, 4)\}$. Obviously the distance $d_\Delta$ between the starting point, the cell (0, 0) and the nearest target cell, measured in terms of cells, must be such that $0 \le d_\Delta \le M$; $d_\Delta = 3$ in Fig. 1. The case $d_\Delta > M$ is equivalent to having no target cells since, in this case, our MT will trigger LU messages according to the standard movement-based scheme, i.e. no absorption into the $\Delta$ set will happen. Notice that, each time the MT triggers a LU message the procedure starts anew at cell (0, 0), i.e. the scenario depicted in Fig. 1 is repeated.

## 2.3 Modeling and analysis

In this paper we generalize the work [5] in two aspects; first by allowing more than one cell in the $\Delta$ set, secondly by considering a general renewal point
process for modeling call arrivals to the MT. Then, for a predetermined number of movements *m* we are interested in the number of LU messages triggered by our MT between two consecutive call arrivals. We say that our MT is in state *S*<sub>i</sub> if it is roaming in cell *i*. Although a natural cell identification in a 2-D space is the use of two indexes, for the sake of simplicity in the mathematic notation we will use a single index. Since the RA where the MT is roaming is configured by a finite number of cells, a correspondence between the identification with two indexes and the identification with a single index can be established. Then, starting from state *S*<sub>0</sub>, cell (0, 0) in Fig. 1, if an absorption into the Δ set happens at movement *M* or before, the MT will reset its movement counter. If the MT visits a cell that does not belong to the Δ set it will increase in one unit its movement counter. When the movement counter reaches the threshold *M* without being absorbed into the Δ set, the MT will trigger a LU message and the process starts anew at state *S*<sub>0</sub>.

The analysis can be formulated by building a suitable Markov chain and using some useful taboo probabilities [6]. We call $\mathcal{H}f_{i,j}^{(n)}$ the conditional probability that the Markov chain enters state $S_j$ for the first time at the nth step, having initially started from state $S_i$ and avoiding the set of states $H$.

With no loss of generality, in the sequel we assume that the Δ set of absorbing states is configured by three cells, *j*, *k* and *l*, that is, Δ = {*j*, *k*, *l*}. Also, we denote by $\bar{\Delta}_s$ the complementary set of cells in Δ with respect to cell *s*. In our case $\bar{\Delta}_j = \{k,l\}$, $\bar{\Delta}_k = \{j,l\}$ and $\bar{\Delta}_l = \{j,k\}$.

Then, if initially the MT is in state $S_0$ the probability that in *M* movements no absorption into the Δ set occurs, $P_{nab(0,\Delta)}(M)$, is given by

$$P_{nab(0,\Delta)}(M) = 1 - \sum_{n=1}^{M} f_{0,\Delta}^{(n)} = 1 - \sum_{n=1}^{M} \left( \bar{\Delta}_j f_{0,j}^{(n)} + \bar{\Delta}_k f_{0,k}^{(n)} + \bar{\Delta}_l f_{0,l}^{(n)} \right) \quad (1)$$

Also, if initially the MT is in state $S_s$, for ($s = j, k, l$) the probability that in *M* movements no absorption into the Δ set occurs, $P_{nab(s,\Delta)}(M)$, is given by

$$P_{nab(s,\Delta)} = 1 - \sum_{n=1}^{M} f_{s,\Delta}^{(n)} = 1 - \sum_{n=1}^{M} \left( \bar{\Delta}_j f_{s,j}^{(n)} + \bar{\Delta}_k f_{s,k}^{(n)} + \bar{\Delta}_l f_{s,l}^{(n)} \right); \quad \text{for } s = j, k, l \qquad (2)$$

NOTE: Details on how the taboo probabilities {$\mathcal{H}f_{i,j}^{(n)}$} are evaluated are given in the internal report [7].

# 3 The number of location update messages

## 3.1 Mean number of LU messages for a fixed number of movements

Let $P_0^{(m)}(i)$ ($P_s^{(m)}(i)$, for $s = j, k, l$) denote the probability of having *i* LU messages triggered in *m* movements, under the assumption that the MT starts
its trajectory in cell 0 ($s = j, k, l$). Let $M_0^{(m)}$ ($M_s^{(m)}$, for $s = j, k, l$) denote the mean number of LU messages. Then, we have

$$M_0^{(m)} = \begin{cases} 0; & \text{for } m < M \\ \sum_{n=1}^{M} \mathbf{f}_{0,\Delta}^{(n)} \mathbf{M}_{\Delta}^{(m-n)} + P_{\text{nab}(0,\Delta)}(M)[1 + M_0^{(m-M)}]; & \text{for } m \ge M \end{cases} \quad (3)$$

and

$$\mathbf{M}_{\Delta}^{(m)} = \begin{cases} 0; & (\text{a column vector of zeros}); \quad \text{for } m < M \\ \sum_{n=1}^{M} \mathbf{f}_{\Delta,\Delta}^{(n)} \mathbf{M}_{\Delta}^{(m-n)} + \mathbf{P}_{\text{nab}(\Delta,\Delta)}(M)[1 + M_0^{(m-M)}]; & \text{for } m \ge M \end{cases} \quad (4)$$

where (more details are given in [7])

$$\mathbf{M}_{\Delta}^{(m)} = (M_{j}^{(m)}, M_{k}^{(m)}, M_{l}^{(m)})^{T} = \sum_{i=0}^{\infty} i \mathbf{P}_{\Delta}^{(m)}(i);$$

$$\text{with } \mathbf{P}_{\Delta}^{(m)}(i) = (P_{j}^{(m)}(i), P_{k}^{(m)}(i), P_{l}^{(m)}(i))^{T};$$

$$\mathbf{P}_{\text{nab}(\Delta,\Delta)}(M) = (P_{\text{nab}(j,\Delta)}(M), P_{\text{nab}(k,\Delta)}(M), P_{\text{nab}(l,\Delta)}(M))^{T};$$

$$\mathbf{f}_{0,\Delta}^{(n)} = (\bar{\Delta}_j f_{0,j}^{(n)}, \bar{\Delta}_k f_{0,k}^{(n)}, \bar{\Delta}_l f_{0,l}^{(n)}); \quad \mathbf{f}_{\Delta,\Delta}^{(n)} = \begin{pmatrix} \bar{\Delta}_j f_{j,j}^{(n)} & \bar{\Delta}_k f_{j,k}^{(n)} & \bar{\Delta}_l f_{j,l}^{(n)} \\ \bar{\Delta}_j f_{k,j}^{(n)} & \bar{\Delta}_k f_{k,k}^{(n)} & \bar{\Delta}_l f_{k,l}^{(n)} \\ \bar{\Delta}_j f_{l,j}^{(n)} & \bar{\Delta}_k f_{l,k}^{(n)} & \bar{\Delta}_l f_{l,l}^{(n)} \end{pmatrix}$$

Therefore, the mean number of LU messages triggered by the MT between two consecutive call arrivals, $\overline{\#_{LU}}$, can be expressed as

$$\overline{\#_{LU}} = \sum_{m=0}^{\infty} M_{0}^{(m)} \alpha(m) = \sum_{m=M}^{\infty} M_{0}^{(m)} \alpha(m) \quad (5)$$

where $\alpha(m)$ is the probability of $m$ cell boundary crossings between two consecutive call arrivals. $\alpha(m)$ is derived in the next section.

## 3.2 On the number of cell boundary crossing between two call arrivals

We assume that calls arrive to the MT following a renewal point process with inter-arrival time pdf given by $f_c(t)$. We denote $f_c^*(s)$ the Laplace transform (LT) of $f_c(t)$. Then, $\alpha(k)$ is given by (see [7]),
$$ \alpha(k) = \begin{cases} \frac{1}{2\pi i} \int_{c-i\infty}^{c+i\infty} \frac{[1 - f_{mr}^*(s)]}{s} f_c^*(-s)ds; & \text{for } k = 0 \\ \frac{1}{2\pi i} \int_{c-i\infty}^{c+i\infty} \frac{f_{mr}^*(s)[1 - f_m^*(s)][f_m^*(s)]^{k-1}}{s} f_c^*(-s)ds; & \text{for } k > 0 \end{cases} \quad (6) $$

In (6), $f_m^*(s)$ is the LT of $f_m(t)$; the pdf of the MT dwell time or residence time in a cell, with mean value $1/\lambda_m = -f_m^{*'}(0)$. $f_{mr}^*(s)$ is the LT of the residual cell residence time, $f_{mr}^*(t)$. Following the residual life theorem [8] we have

$$ f_{mr}(t) = \lambda_m \int_t^\infty f_m(t)dt = \lambda_m[1 - F_m(t)]; \quad f_{mr}^*(s) = \frac{\lambda_m}{s}[1 - f_m^*(s)] \quad (7) $$

### 3.3 Mean number of LU between two consecutive call arrivals

In order to obtain a closed form expression for (5) first we define the following generating functions

$$ M_0^*(z) = \sum_{m=0}^{\infty} M_0^{(m)} z^m; \quad M_{\Delta}^*(z) = \sum_{k=0}^{\infty} M_{\Delta}^{(k)} z^k \quad (8) $$

$$ \mathbf{F}_{0,\Delta}^*(z) = \sum_{n=1}^{M} \mathbf{f}_{0,\Delta}^{(n)} z^n = (F_{0,j}^*(z), F_{0,k}^*(z), F_{0,l}^*(z)); \\ \text{with } F_{0,s}^*(z) = \sum_{n=1}^{M} \bar{\Delta}_s f_{0,s}^{(n)} z^n, \quad \text{for } s \in \Delta \equiv \{j, k, l\} $$

$$ \mathbf{F}_{\Delta,\Delta}^*(z) = \sum_{n=1}^{M} \mathbf{f}_{\Delta,\Delta}^{(n)} z^n = \begin{pmatrix} F_{j,j}^*(z) & F_{j,k}^*(z) & F_{j,l}^*(z) \\ F_{k,j}^*(z) & F_{k,k}^*(z) & F_{k,l}^*(z) \\ F_{l,j}^*(z) & F_{l,k}^*(z) & F_{l,l}^*(z) \end{pmatrix}; \\ \text{with } F_{r,s}^*(z) = \sum_{n=1}^{M} \bar{\Delta}_s f_{r,s}^{(n)} z^n, \quad \text{for } r, s \in \Delta \equiv \{j, k, l\} $$

Then, from (3) and (4) a linear relationship between $M_0^*(z)$ and $M_{\Delta}^*(z)$ is obtained. That is

$$ \begin{aligned} M_0^*(z) &= \mathbf{F}_{0,\Delta}^*(z)\mathbf{M}_{\Delta}^*(z) + P_{nab(0,\Delta)}(M)z^M \left(\frac{1}{1-z} + M_0^*(z)\right) \\ \mathbf{M}_{\Delta}^*(z) &= \mathbf{F}_{\Delta,\Delta}^*(z)\mathbf{M}_{\Delta}^*(z) + \mathbf{P}_{nab(\Delta,\Delta)}(M)z^M \left(\frac{1}{1-z} + M_0^*(z)\right) \end{aligned} \quad (9) $$

Therefore, solving (9) we get the expression for $M_0^*(z)$
$$ M_0^*(z) = \frac{1}{1-z} \frac{\{\mathbf{F}_{0,\Delta}^*(z)[\mathbf{I} - \mathbf{F}_{\Delta,\Delta}^*(z)]^{-1}\mathbf{P}_{nab(\Delta,\Delta)}(M) + \mathbf{P}_{nab(0,\Delta)}(M)\}z^M}{1 - \{\mathbf{F}_{0,\Delta}^*(z)[\mathbf{I} - \mathbf{F}_{\Delta,\Delta}^*(z)]^{-1}\mathbf{P}_{nab(\Delta,\Delta)}(M) + \mathbf{P}_{nab(0,\Delta)}(M)\}z^M} \quad (10) $$

Secondly, from (3)-(6) we can write, after some algebra, [7],

$$ \begin{aligned} \overline{\#_{LU}} &= \sum_{m=0}^{\infty} M_0^{(m)} \alpha(m) = \sum_{k=M}^{\infty} M_0^{(k)} \alpha(k) = \\ &= \frac{1}{2\pi i} \int_{c-i\infty}^{c+i\infty} \frac{f_{mr}^*(s)[1-f_m^*(s)]}{s f_m^*(s)} M_0^*(f_m^*(s)) f_c^*(-s) ds \quad (11) \\ &= -\sum_{p \in \sigma_c} \mathrm{Res}_{s=p} \frac{f_{mr}^*(s)[1-f_m^*(s)]}{s f_m^*(s)} M_0^*(f_m^*(s)) f_c^*(-s) \end{aligned} $$

The last equality in (11) is derived applying the Cauchy's Residue Theorem, i.e., $\sigma_c$ denotes the set of poles of $f_c^*(-s)$ in the right half complex plane, and $\mathrm{Res}_{s=p}$ denotes the residue at poles $s = p \in \sigma_c$. $M_0^*(f_m^*(s))$ is the expression (10) evaluated at $z = f_m^*(s)$.

# 4 Terminal paging procedure

Blanket or non selective and selective or multi-step PG procedures are considered. For PG evaluation, in the first case we only need the number of cells that conforms the RA. Once the parameter $M$ and the $\Delta$ set are fixed, the total number of cells to poll can easily be obtained. For instance, when $M = 4$ and $\Delta = \{(3,3), (3,4), (4,3), (4,4)\}$ Fig. 1 accounts for the set of cells, the $\Omega$ set, in which the MT can be in. The cardinality of $\Omega$ is $C(\Omega) = 73$. Obviously, for selective PG we need the PG probabilities. They are derived in the next lines.

## 4.1 Paging probabilities

Let $\pi_{i,t}^{(m)}$ denotes the probability that starting at cell $i$ the MT is located at cell $t$ after $m$ movements. Then, following the arguments used in section 3.1 we can write, for $i = 0$

$$ \pi_{0,t}^{(m)} = \begin{cases} p_{0,t}^{(m)}; & \text{for } m < M \\ \sum_{n=1}^{M} \mathbf{f}_{0,\Delta}^{(n)} \boldsymbol{\pi}_{\Delta,t}^{(m-n)} + P_{nab(0,\Delta)}(M) \pi_{0,t}^{(m-M)}; & \text{for } m \ge M \end{cases} \quad (12) $$

and for the $\Delta$ set, cells $i = s \in \Delta \equiv \{j,k,l\}$
$$ \pi_{\Delta,t}^{(m)} = \begin{cases} \mathbf{P}_{\Delta,t}^{(m)}; & \text{for } m < M \\ \sum_{n=1}^{M} \mathbf{f}_{\Delta,\Delta}^{(n)} \pi_{\Delta,t}^{(m-n)} + \mathbf{P}_{nab(\Delta,\Delta)}(M) \pi_{0,t}^{(m-M)}; & \text{for } m \ge M \end{cases} \quad (13) $$

with

$$ \pi_{\Delta,t}^{(m)} = (\pi_{j,t}^{(m)}, \pi_{k,t}^{(m)}, \pi_{l,t}^{(m)})^T; \quad \mathbf{P}_{\Delta,t}^{(m)} = (p_{j,t}^{(m)}, p_{k,t}^{(m)}, p_{l,t}^{(m)})^T; $$

Therefore the set of probabilities $\{\pi_{i,t}\}$ can be expressed as

$$ \pi_{i,t} = \sum_{m=0}^{\infty} \pi_{i,t}^{(m)} \alpha(m) \quad (14) $$

For $i = 0$, (14) gives the probability that the MT is located at cell $j$ when a call arrival occurs. To evaluate the set $\{\pi_{0,t}\}$ we follow a similar procedure to that in section 3. To that end, first, let us define the following generating functions, $\pi_{0,t}^*(z)$ and $\pi_{\Delta,t}^*(z)$

$$ \pi_{0,t}^*(z) = \sum_{m=0}^{\infty} \pi_{0,t}^{(m)} z^m; \quad \pi_{\Delta,t}^*(z) = \sum_{m=0}^{\infty} \pi_{\Delta,t}^{(m)} z^m; \quad (15) $$

Then, from equations (12) and (13) a linear relationships between $\pi_{0,j}^*(z)$ and $\pi_{\Delta,t}^*(z)$ is obtained. That is

$$ \begin{aligned} [1 - z^M P_{nab(0,\Delta)}(M)] \pi_{0,t}^*(z) - \mathbf{F}_{0,\Delta}^*(z) \pi_{\Delta,t}^*(z) &= \\ &= \sum_{n=0}^{M-1} p_{0,t}^{(n)} z^n - \sum_{n=1}^{M-1} \mathbf{f}_{0,\Delta}^{(n)} \left[ \sum_{k=0}^{M-n-1} \mathbf{P}_{\Delta,t}^{(k)} z^k \right] z^n = \mathcal{Y}(0, \Delta, z, t); \end{aligned} \quad (16) \\ -z^M \mathbf{P}_{nab(\Delta,\Delta)}(M) \pi_{0,t}^*(z) + [\mathbf{I} - \mathbf{F}_{\Delta,\Delta}^*(z)] \pi_{\Delta,t}^*(z) &= \\ &= \sum_{n=0}^{M-1} \mathbf{P}_{\Delta,t}^{(n)} z^n - \sum_{n=1}^{M-1} \mathbf{f}_{\Delta,\Delta}^{(n)} \left[ \sum_{k=0}^{M-n-1} \mathbf{P}_{\Delta,t}^{(k)} z^k \right] z^n = \mathbf{\Gamma}(\Delta, \Delta, z, t); \end{aligned} $$

Therefore, solving (16) for $\pi_{0,t}^*(z)$ we have

$$ \pi_{0,t}^*(z) = \frac{\mathbf{F}_{0,\Delta}^*(z)[\mathbf{I} - \mathbf{F}_{\Delta,\Delta}^*(z)]^{-1}\mathbf{\Gamma}(\Delta, \Delta, z, t) + \mathcal{Y}(0, \Delta, z, t)}{1 - \{\mathbf{F}_{0,\Delta}^*(z)[\mathbf{I} - \mathbf{F}_{\Delta,\Delta}^*(z)]^{-1}\mathbf{P}_{nab(\Delta,\Delta)}(M) + \mathbf{P}_{nab(0,\Delta)}(M)\}z^M} \quad (17) $$

Secondly, from (12)-(13) and (6) the paging probabilities, (14) for $i = 0$, can be written as
$$
\begin{align}
\pi_{0,t} &= \sum_{k=0}^{\infty} \pi_{0,t}^{(k)} \alpha(k) = \pi_{0,t}^{(0)} \alpha(0) + \sum_{k=1}^{\infty} \pi_{0,t}^{(k)} \alpha(k) = \nonumber \\
&= \frac{1}{2\pi i} \int_{c-i\infty}^{c+i\infty} \left[ \frac{[f_m^*(s) - f_{mr}^*(s)]}{s f_m^*(s)} p_{0,t}^{(0)} + \frac{f_{mr}^*(s)[1 - f_m^*(s)]}{s f_m^*(s)} \pi_{0,t}^*(f_m^*(s)) \right] f_c^*(-s) ds \nonumber \\
&= - \sum_{p \in \sigma_c} \mathrm{Res}_{s=p} \left[ \frac{[f_m^*(s) - f_{mr}^*(s)]}{s f_m^*(s)} p_{0,t}^{(0)} + \frac{f_{mr}^*(s)[1 - f_m^*(s)]}{s f_m^*(s)} \pi_{0,t}^*(f_m^*(s)) \right] f_c^*(-s) \tag{18}
\end{align}
$$

As in (11), Cauchy's Residue Theorem is used to reach the last equality in (18).

## 4.2 Paging procedure

We have evaluated the PG cost for the conventional blanket or single step paging, $\eta = 1$ and for two selective paging schemes with delays $\eta = 2$ and $\eta = 3$. In the illustrative example we have used a single absorbing state for the $\Delta$ set. Also, we have implemented the line-paging philosophy suggested in [9]. To that end we have defined three sets of disjoint cells, A, B and C, that is, $A \cap B = \emptyset$, $A \cap C = \emptyset$, $B \cap C = \emptyset$, and $A \cup B \cup C = \Omega$, being $\emptyset$ the empty set and $\Omega$ the full set of cells where the MT can be in. Denoting by $C\{X\}$ the cardinality of X, we have chosen

$$
\begin{align}
A &= \{(0,0), (1,1), \dots, (\min\{\Delta + M - 1, 2\Delta\}, \min\{\Delta + M - 1, 2\Delta\})\}, \nonumber \\
C\{A\} &= \min(\Delta + M - 1, 2\Delta) + 1; \nonumber \\
B &= \{\text{The first ring of cells around the set A}\}, \nonumber \\
C\{B\} &= \begin{cases} 2C\{A\} + 4; & \text{if } \Delta < M - 1 \\ 2C\{A\} + 1; & \text{if } M - 1 \le \Delta \le M \end{cases}, \tag{19} \\
C &= \{\text{The remaining set of cells: } \Omega - A \cup B\}, \nonumber \\
C\{C\} &= C\{\Omega\} - C\{A \cup B\} = C\{\Omega\} - C\{A\} - C\{B\} \nonumber \\
\text{and } C\{\Omega\} &= 3(M - 1)^2 + 3(M - 1) + 1 + \Delta(2M - 1). \nonumber
\end{align}
$$

# 5 Numerical Analysis

The following assumptions have been established. A Gamma distributed for the cell residence time, with pdf and LT given by

$$f_m(t) = \frac{(\gamma \lambda_m)^\gamma t^{\gamma-1}}{\Gamma(\gamma)} e^{-\gamma \lambda_m t}, \quad f_m^*(s) = \left( \frac{\gamma \lambda_m}{s + \gamma \lambda_m} \right)^\gamma \quad (20)$$
<figure><img src="image_4.png" /><figcaption>**Fig. 2.** Paging schemes for $M = 5$ and $\Delta = \{(3,3)\}$. Cells are grouped into three sets and they are sorted for paging procedure. Blanket polling: set $\Omega = A \cup B \cup C$. Two step paging: first A, secondly $B \cup C$. Three step paging: first A, secondly B, thirdly C.</figcaption></figure>

with mean value $1/\lambda_m$ and with the squared coefficient of variation $C_m^2 = 1/\gamma$, [8]. For the call inter-arrival time, on one hand, the Erlangian-Geo-type $f_{c,e}(t)$, with LT

$$f_{c,e}^*(s) = \prod_{i=0}^{n-1} \frac{\lambda_i}{s + \lambda_i}, \quad \lambda_i = \frac{\lambda_c (1 - a^n)}{a^i (1 - a)} \quad (21)$$

with mean value $1/\lambda_c$ and $C_{c,e}^2 = \frac{(1+a^n)(1-a)}{(1-a^n)(1+a)} \le 1$ for $0 < a < 1$ and $n$ any natural number. On the other hand, the hyper-exponential distribution $H_2$, $f_{c,h}(t)$, with LT

$$f_{c,h}^*(s) = a \frac{\lambda_1}{s + \lambda_1} + (1 - a) \frac{\lambda_2}{s + \lambda_2}, \quad \lambda_2 = n\lambda_1, \quad \frac{1}{\lambda_c} = \frac{a}{\lambda_1} + \frac{(1 - a)}{n\lambda_1} \quad (22)$$

with mean value equal to $1/\lambda_c$ and $C_{c,h}^2 = \frac{1 + 2an(n-1) - a^2(n-1)^2}{1 + 2a(n-1) + a^2(n-1)^2} \ge 1$ for $0 < a < 1$, equivalently $\frac{1}{n} \le \frac{\lambda_1}{\lambda_c} \le 1$, and $n$ any natural number. It is easy to verify that the maximum $C_h^2$ is achieved for $a = 1/(n+1)$.

All plots have been obtained for a Call-to-Mobility ratio (CMR) equals to $\lambda_c/\lambda_m = 0.10$. From Fig. 3 we observe that for $C_m^2 \le 1$ the mean number of LU messages, $\#_{LU}$ in (5), reduces when $C_c^2$ increases. However, when $C_m^2 > 1$ the mean number of LU messages, $\#_{LU}$ is rather insensitive to $C_c^2$.

A significant saving is achieved when selective paging is implemented as it can be seen in Fig. 4 and Fig. 5. The saving is quite noticeable from blanket polling (not shown in the paper, since it is quite trivial) to the two step PG or polling scheme. Also a noticeable saving is obtained from two step polling to three step polling. As additional observation we realize that, for a fixed number of PG steps, and for a fixed $C_m^2$, the paging cost is no sensitive to the inter-arrival process. Also, for a fixed number of paging steps, for a fixed value of $C_c^2$ and for $C_m^2 \le 1$ ($C_m^2 > 1$) the PG cost is rather insensitive (quite sensitive) to the inter-arrival time distribution.
# 6 Conclusions

In this paper we have proposed and studied within a general framework, a lookahead location update procedure with selective paging. We have seen that the information about the directionality of the mobile terminal's movement can be used to save signaling cost associated to movement-based location management procedures. With a lookahead scheme the size of the registration area increases and a selective paging scheme is recommended to avoid a noticeable increment in the paging cost. The net effect is a significant saving in the total signaling traffic on the common air interface. We believe that this scheme could be used by mobile operators where mobile terminals follow certain daily or customary trajectory.

# Acknowledgments

This research has been financed by the Spanish Ministerio de Ciencia e Innovación project TSI2007-66869-C02-02 and by the Universidad Politécnica de Valencia under the grant PAID-05-08. Also, thanks for the support received from the European Network of Excellence Euro NF and to its research community for many scientific and fruitful interactions with its partners.

# References

1. T. Camp, T., Boleng, J., Davies, V.: A survey of mobility models for ad hoc network research. Wireless Communications and Mobile Computing. Vol.2, no.5, 483-502 (2002)

2. Bettstetter, C., Hartenstein, H., Perez-Costa, X.: Stochastic properties of the random waypoint mobility model. Wireless Networks Vol. 10, no. 5, 555-567 (2004)

3. Martinez-Arrue, I., Escalle-Garcia P., Casares-Giner, V.: Location Management Based on the Mobility Patterns of Mobile Users. In Cerd-Alabern Ll. (Ed:9) Wireless Systems and Mobility in Next Generation Internet 2008, LNCS Vol. 5122, pp. 185-200. Springer (2008)

4. Escalle-García, P., Casares-Giner, V., Mataix-Oltra, J.: Reducing location update and paging costs in a Personal Communications Services Network. IEEE Trans. on Wireless Communications. Vol. 1, n. 2, 200-209 (2002).

5. Casares-Giner, V., Escalle-García, P.: On Movement-Based Location Update. A Lookahead Strategy. In: Proceedings of the 5th Euro-NGI conference on Next Generation Internet networks. pp 213-220 IEEExplore (2009).

6. Karlin, S., Taylor, H. M.: A first course in stochastic processes, Second edition, Academic Press (1975.)

7. Casares-Giner, V.: On lookahead strategy for movement-based location update. A general formulation. Internal Report Universidad Politecnica de Valencia, (2010).

8. Kleinrock, L.: Queuing Theory (Vol 1: Theory). John Wiley (1975)

9. Hwang, H. W., Chang, M. F., Tseng, and C. C.: A direction-based location update scheme with a line-paging strategy for PCS networks. IEEE Communications Letters. Vol. 4, n. 5, pp 149-151, (2000).
<figure><img src="image_5.png" /><figcaption>**Fig. 3.** Average number of LU messages between two consecutive call arrivals in terms of the mobility model parameter $\beta$ with the target $\Delta$ cell as varying parameter ($\Delta = i$ means the target cell $(i, i)$ in Fig. 2). Inter-arrival call process: Erlangian-Geo with $n= 10$ stages and $C_{c,e}^2 = 0.109$ (low-variance) on the left and hyper-exponential with $n=20$ and $C_{c,h}^2 = 10.025$ (high-variance) on the right. Cell residence time, from top to bottom: Gamma distribution with $C_m^2 = 0.01$ (low-variance), $C_m^2 = 1$ (exponential) and $C_m^2 = 100$ (high-variance), respectively.</figcaption></figure>
<figure><img src="image_6.png" /><figcaption>**Fig. 4.** Two steps paging. Average number of cells polled per call arrival in terms of the mobility model parameter $\beta$ with the target $\Delta$ cell as varying parameter ($\Delta = i$ means the target cell $(i, i)$ in Fig. 2). Inter-arrival call process: Erlangian-Geo with $n= 10$ stages and $C_{c,e}^2 = 0.109$ (low-variance) on the left and hyper-exponential with $n=20$ and $C_{c,h}^2 = 10.025$ (high-variance) on the right. Cell residence time, from top to bottom: Gamma distribution with $C_m^2 = 0.01$ (low-variance), $C_m^2 = 1$ (exponential) and $C_m^2 = 100$ (high-variance), respectively.</figcaption></figure>
<figure><img src="image_7.png" /><figcaption>**Fig. 5.** Three steps paging. Average number of cells polled per call arrival in terms of the mobility model parameter $\beta$ with the target $\Delta$ cell as varying parameter ($\Delta = i$ means the target cell $(i, i)$ in Fig. 2). Inter-arrival call process: Erlangian-Geo with $n= 10$ stages and $C_{c,e}^2 = 0.109$ (low-variance) on the left and hyper-exponential with $n=20$ and $C_{c,h}^2 = 10.025$ (high-variance) on the right. Cell residence time, from top to bottom: Gamma distribution with $C_m^2 = 0.01$ (low-variance), $C_m^2 = 1$ (exponential) and $C_m^2 = 100$ (high-variance), respectively.</figcaption></figure>