Studying the Geographical Cluster Paging with Delay Constraint in Registration Areas with the Algorithm NSGAII

Abstract

The mobility management strategy based on registration areas is one of the most popular strategies to manage the subscribers’ mobility in current Public Land Mobile Networks. For it, the network cells are arranged in continuous and non-overlapped sets in order to partially track the subscribers’ movement. In this way, the network knows the location of its subscribers at a registration area level and the paging should only be performed in the cells within the last updated registration area. The paging scheme studied in this work is the geographical cluster paging, a probabilistic paging in which it is assumed that the probability of finding a mobile station (i.e. the subscriber’s terminal) decreases as we move away from the last updated network cell following a normal distribution. The main appeal of this paging scheme is that we can considerably reduce the signaling traffic (with respect to the simultaneous paging) without including new elements in the network. Furthermore, we analyze it for different probability thresholds and considering delay constraints. On the other hand, we use our implementation of the Non-dominated Sorting Genetic Algorithm II (NSGAII) with the aim of finding the best possible sets of non-dominated solutions. Results show that each probability threshold has its own non-dominated region in the objective space, and that the signaling traffic can be reduced by about 30 % (with respect to the simultaneous paging).

1 Introduction

Public Land Mobile Networks (PLMNs) are widely used throughout the world. In fact, the GSM Association estimates that there will be approximately 3.9 billion of mobile subscribers in 2017 [1]. That is, approximately half of the world’s population will use mobile communications. In these networks and in order to cope with such huge demand, the coverage area is divided into several smaller land areas (known as network cells) among which the radio-electric resources are distributed and reused [2]. Nonetheless, an access network based on cells has an important issue related to the subscribers’ movement because a mobile station (i.e. the subscriber’s terminal) can be in any cell and receive a call at any time. Therefore, every PLMN must have a method to properly redirect the incoming calls (i.e. determine the exact cell in which the callee’s terminal is located).

In the literature, we can find several mobility management strategies, most of them consist of two main procedures: the subscriber’s location update and the paging [3]. The subscriber’s location update is the procedure whereby a mobile station reports (to the network) that its location should be updated. There are several strategies of location update: never update (a mobile station never updates its location), always update (a mobile station updates its location whenever it moves from one network cell to another), cell-based (a mobile station updates its location whenever it moves to a specific type of network cell), and area-based (a mobile station updates its location whenever it moves from one registration area to another, where a registration area is a continuous and non-overlapped set of network cells). On the other hand, the network uses the paging to determine the exact cell in which the callee’s terminal is located. For it, the network sends broadcast paging messages around the last updated location (for the mobile station in question). The different paging schemes can be classified into two main groups: simultaneous paging and sequential paging. In the simultaneous paging, all the network cells that have to be paged are polled simultaneously; and in the sequential paging, all the cells that have to be paged are arranged into paging areas that are sequentially polled (all the cells within a paging area are polled simultaneously). In this work, we study the mobility management strategy based on registration areas (because it is widely used in current PLMNs [4]) with the geographical cluster paging (a sequential paging in which it is assumed that the probability of finding a mobile station decreases following a normal distribution) in a multiobjective way. We analyze this paging scheme because it allows us to reduce the signaling traffic associated with the mobility management task (which could be more than 33 % of the total signaling traffic [4]) without including new elements in the network.

The optimization problem addressed in this manuscript is called the Registration Areas Planning Problem (RAPP), an optimization problem in where the main challenge consists in finding the configurations of registration areas than minimize simultaneously the number of location updates and the number of paging messages. It is important to empathize that this problem is a multiobjective optimization problem which was classified as an NP-hard problem in the literature [5]. This is the reason why our research is focused on the use of multiobjective optimization techniques applied to different mobility management strategies in PLMNs. In this work and with the aim of finding the best possible set of non-dominated solutions, we use our implementation of the Non-dominated Sorting Genetic Algorithm II (NSGAII, a well-known multiobjective evolutionary algorithm [6]).

The rest of the paper is organized as follows. Section 2 presents the related work. The optimization problem addressed in this manuscript is defined in Sect. 3. Our implementation of NSGAII is briefly explained in Sect. 4. The performance of the geographical cluster paging is analyzed in Sect. 5. Finally, our conclusions and future work are discussed in Sect. 6.

2 Related Work

In the literature, we can find several manuscripts that tackle the Registration Areas Planning Problem (RAPP). Please, take into account the fact that the name of the registration area depends on the underlying mobile technology (e.g. location area in GSM (Global System for Mobile communications), routing area in GPRS (General Packet Radio Service), UTRAN registration area in UMTS (Universal Mobile Telecommunications System), or tracking area in LTE (Long Term Evolution)). P. R. L. Gondim was one of the first authors in using a Genetic Algorithm (GA) for finding quasi-optimal configurations of registration areas [5]. In that work, it was also shown that RAPP is an NP-hard combinatorial optimization problem. P. Demestichas et al. analyzed this optimization problem in different environments and with different metaheuristics (Simulated Annealing (SA), Tabu Search (TS), and GA) [7]. I. Demirkol et al. implemented a metaheuristic based on SA in where one of the two objective functions was considered as a constraint [8]. J. Taheri and A. Y. Zomaya analyzed the feasibility of different metaheuristics to optimize registration areas (Hopfield Neural Network (HNN) [9], SA [10], GA [11], and different combinations of HNN with GA (HNN-GA) [12]). S. M. Almeida-Luz et al. proposed other two optimization techniques based on Differential Evolution (DE) [13] and Scatter Search (SS) [14].

The main weakness of this related work is the fact that, although RAPP is in essence a multiobjective optimization problem (as we show in Sect. 3), this problem was tackled with single-objective optimization techniques (by considering one of the two objective functions as a constraint [8], or by using the linear aggregation of the objective functions [5, 7, 9–14]. Furthermore, these works only consider the simultaneous paging (i.e. the traditional paging scheme).

In our previous work, we have already analyzed the feasibility of different multiobjective evolutionary algorithms for optimizing registration areas [15], and the effect of increasing the number of paging cycles of the geographical cluster paging in the SUMATRA test network (a test network which was well-validated against real data measured in the San Francisco Bay) [16]. The main contribution of this manuscript is that, for a given number of paging cycles (i.e. considering delay constraints), we analyze the effect of varying the sizes of the paging areas in the geographical cluster paging. Furthermore, we study other set of mobile networks sited in four world capital cities. On the other hand and with the aim of finding the best possible set of non-dominated solutions, we use our implementation of the Non-dominated Sorting Genetic Algorithm II (NSGAII, a well-known multiobjective evolutionary algorithm) [6]. We have chosen NSGAII because it is the algorithm with which we obtain our better results in our previous work [15, 16].

3 Registration Areas Planning

In a location update strategy based on registration areas (RAs), the network cells are arranged in continuous and non-overlapped sets in order to partially track the subscribers’ movement [17]. In this way, a mobile station only initiates a location update procedure when moving from one registration area to another. Therefore, the network knows the location of its subscribers at a registration area level, and consequently, the paging should only be performed in the network cells within the last updated registration area (for the callee’s terminal in question). It is noteworthy that a mobile station knows the cell in which it is currently located because every base station (i.e. the network entity that provides access to the mobile stations) periodically broadcasts its cell global identification packet, which contains the following information: cell identity, registration area identity, registration area code, mobile network code, and mobile country code [18].

The main challenge of the Registration Areas Planning Problem consists in finding the configurations of registration areas that minimize the number of location updates (or location update cost, LU$_{\text {cost}}$) and the number of paging messages (or paging cost, PA$_{\text {cost}}$) simultaneously. For a given configuration of registration areas (every cell has assigned an RA, that is, for a given combination of decision variables), these two costs can be calculated as follows:

$$\begin{aligned} \mathbf f _{\text {1}}=\text {min}\left\{ \text {LU}_{\text {cost}}=\sum _{\text {t=T}_{\text {ini}}}^{\text {T}_{\text {fin}}}\sum _{\text {i=1}}^{\text {N}_{\text {user}}}\gamma _{\text {t,i}}\right\} , \end{aligned}$$

(1)

$$\begin{aligned} \mathbf f _{2}=\text {min}\left\{ \text {PA}_{\text {cost}} = \sum _{\text {t}=\text {T}_{\text {ini}}}^{\text {T}_{\text {fin}}}\sum _{\text {i}=1}^{\text {N}_{\text {user}}}\rho _{\text {t},\text {i}}\cdot \varphi _{\text {t},\text {i}}\right\} , \end{aligned}$$

(2)

where $\left[ \text {T}_{\text {ini}}, \text {T}_{\text {fin}}\right]$ is the time interval of the mobile activity trace. $\text {N}_{\text {user}}$ is the number of mobile stations. $\gamma _{\text {t,i}}$ is a binary variable which is equal to 1 when the mobile station i crosses the boundary between two registration areas in the time t. $\rho _{\text {t,i}}$ is a binary variable which is equal to 1 when the mobile station i has an incoming call in the time t. Finally, $\varphi _{\text {t},\text {i}}$ is the number of network cells that have to be polled in order to locate the mobile station i in the time t. It should be noticed that these two objective functions are conflicting, and therefore, this optimization problem can be classified as a multiobjective optimization problem. Suppose first that we want to reduce to its minimum the location update cost. For it, all the network cells must belong to the same registration area, because in this case a mobile station never updates its location ($\gamma _{\text {t,i}}=0~\forall \text {t,i}$). However, the paging cost is maximum in this configuration because every mobile station should be searched in the whole network whenever it has an incoming call (please, note that in this case the network has not previous information about the location of its subscribers). On the other hand, if we want to minimize the paging cost, each network cell must be in a different registration area ($\varphi _{\text {t},\text {i}}= 1~\forall \text {t,i}$). In this case, the network knows the location of its subscribers at a cell level, which leads to a maximum location update cost because a mobile station will initiate a location update whenever it moves from one network cell to another.

Fig. 1.

Geographical cluster paging with two paging cycles

3.1 Geographical Cluster Paging with Delay Constraint

The geographical cluster paging is a sequential paging scheme in which it is assumed that the probability of finding a mobile station decreases (following a normal distribution) as we move away from the last updated cell [19]. In this way, the paging procedure is performed in concentric rings starting from the last updated network cell until finding the mobile station in question. As a result, the network cells within the last updated registration area (RA$_{\text {t,i}}$) are arranged in different paging areas ($\text {A}_{\text {t,i,j}}$), where each paging area is composed by one or more concentric rings. This last can be mathematically expressed as:

$$\begin{aligned} \text {RA}_{\text {t,i}} = \text {A}_{\text {t,i,1}} \cup \text {A}_{\text {t,i,2}} \cup \dots \cup \text {A}_{\text {t,i,m}}, \end{aligned}$$

(3)

$$\begin{aligned} \text {A}_{\text {t,i,j}} \cap \text {A}_{\text {t,i,k}} = \emptyset , \forall \text {j} \ne \text {k}, \text {j}\le \text {m}, \text {k}\le \text {m}, \end{aligned}$$

(4)

$$\begin{aligned} \alpha _{\text {t,i,j-1}}\ge \alpha _{\text {t,i,j}}, 2\le \text {j}\le \text {m}, \end{aligned}$$

(5)

$$\begin{aligned} \varphi _{\text {t},\text {i}}=\sum _{\text {j=1}}^{\text {m}}\alpha _{\text {t,i,j}}\cdot \mid \text {A}_{\text {t,i,j}} \mid , \end{aligned}$$

(6)

where m is the number of paging cycles. $\alpha _{\text {t,i,j}}$ is a binary variable which is equal to 1 when the mobile station i is located in a cell of the paging area j in the time t. Finally, $\mid \text {A}_{\text {t,i,j}} \mid$ is the number of network cells within the paging area $\text {A}_{\text {t,i,j}}$. In real world applications, the paging procedure must be performed within a fixed time constraint known as maximum paging delay. This imposes limits on the number of paging cycles. In this work and in contrast to our previous work, we analyze the effect of increasing the size of the first paging area ($\text {A}_{\text {t,i,1}}$) in a geographical cluster paging with two paging cycles (i.e. $m=2$), which is considered to be acceptable in practical implementations [19]. In the following, G-PAn makes reference to each probability threshold studied in this manuscript, where n represents the number of concentric rings inside the first paging area ($\text {A}_{\text {t,i,1}}$). Figure 1 presents an example for the probability thresholds $n=1$ ($\text {A}_{\text {t,i,1}}$ is composed by the last updated network cell) and $n=2$ ($\text {A}_{\text {t,i,1}}$ is composed by the last updated network cell and its neighboring cells), where $\text {A}_{\text {t,i,1}}$ is represented in red color (or dark gray in a B/W printed version).

4 Non-dominated Sorting Genetic Algorithm II

As stated in Sect. 3, RAPP is a multiobjective optimization problem. In this kind of problems, the challenge consists in finding the best possible set of non-dominated solutions, where each non-dominated solution is related to a specific trade-off among objectives [20]. For definition and assuming a minimization bi-objective optimization problem, a solution x $^{\text {i}}$ is said to dominate another solution x $^{\text {j}}$ (represented as x $^{\text {i}} \prec \mathbf x ^{\text {j}}$) if and only if $\forall \mathrm{k}\in [1,2], \mathbf{z}^{\mathrm{i}}_{\mathrm{k}}={\varvec{f}}_{\text {k}}\left( \mathbf x ^{\text {i}}\right) \le \mathbf z ^{\text {j}}_{\text {k}}={\varvec{f}}_{\text {k}}\left( \mathbf x ^{\text {j}}\right) \wedge \exists \text {k}\in \left[ 1,2\right] : \mathbf z ^{\text {i}}_{\text {k}} < \mathbf z ^{\text {j}}_{\text {k}}$, where $\mathbf z ^{\text {i}}=\left[ \mathbf z ^{\text {i}}_{\text {1}},\mathbf z ^{\text {i}}_{\text {2}}\right]$ is the objective vector of the solution i, and the graphical representation of the non-dominated objective vectors is known as Pareto front. In this work, every individual (i.e. an encoded solution of the problem) is a vector in which we store the registration area associated with each network cell, see Fig. 2.

Fig. 2.

Chromosome representation

With the aim of finding the best possible set of non-dominated solutions, we use our implementation of the Non-dominated Sorting Genetic Algorithm II (NSGAII), a well-known multiobjective evolutionary algorithm proposed by K. Deb et al. in [6]. NSGAII is an elitist genetic algorithm with a fitness function used to estimate the quality of a solution in the multiobjective context. This fitness function arranges the solutions in fronts according to the non-dominance concept. After that, the crowding distance is applied in order to discriminate among solutions within the same front. For further information about this fitness function, please consult [6]. In our implementation of NSGAII, we have used a multi-point crossover in where the maximum number of crossover points is equal to 4. Furthermore, we have defined two mutation operations specific to the problem. In the first one, we merge a randomly selected border cell (i.e. a network cell which is border among two or more registration areas) with its smallest neighboring registration area. On the other hand, in the second mutation operation, the smallest registration area is merged with its smallest neighboring registration area. For a detailed explanation of our implementation of NSGAII, please consult our previous work [15, 16].

5 Results

In this section, we present the study accomplished to evaluate (in a multiobjective way) the performance of the geographical cluster paging with two paging cycles ($m=2$) in a location update strategy based on registration areas. To the best of our knowledge, this analysis is a novel contribution of our research. As stated in Sect. 3.1, this paging scheme is analyzed for different probability thresholds (i.e. for different sizes of the first paging area, $\textit{n}\in \left\{ 1,2,3,4\right\}$). An analysis for higher values of n is not presented because we did not notice a significant improvement in the results.

This study is performed over a set of mobile networks sited in four world capital cities: Rome (a mobile network with 218 cells), Hong Kong (a mobile network with 220 cells), London (a mobile network with 276 cells), and Paris (a mobile network with 345 cells). The mobile activity traces for these networks can be downloaded from http://arco.unex.es/vicberpla/MAT.html.

It is noteworthy that NSGAII is a stochastic optimization technique, and therefore, it is necessary a statistical study in order to determine whether the differences among the experiments are statistically significant. The first step consists in applying the Shapiro-Wilk test to know whether the samples follow a normal distribution. After that and whenever the Shapiro-Wilk test is positive, the Levene test is used to check the homogeneity of the variances. Finally and whenever the Levene test is positive, the ANOVA analysis is applied in order to determine whether the differences among the means of the experiments are statistically significant. Otherwise, the Mann-Whitney U test is applied to determine whether the differences among the medians of the experiments are statistically significant. All of these tests have been configured with a confidence level equal to 95 %.

After a parametric study, we have chosen the configuration of NSGAII that maximizes the Hypervolume indicator: N$_{\text {POP}}=300$ (population size), N$_{\text {G}}=3000$ (number of generations), P$_{\text {C}}=0.90$ (crossover probability), and P$_{\text {M}}=0.25$ (mutation probability). The Hypervolume (I$_{\text {H}}$) is a multiobjective indicator that associates the quality of a Pareto front with the area of the objective space that is dominated by these non-dominated solutions, and is bounded by the reference points [20]. According to this metric, a set of non-dominated solutions A is said to be better than another set B if and only if I$_{\text {H}}(A) > \text {I}_{\text {H}}(B)$.

Table 1 gathers statistical data of the Hypervolume (median ($\widetilde{\text {I}}_{\text {H}}$) and interquartile range ($\text {iqr}$)) of 31 independent runs per each experiment (probability threshold). Due to the fact that each probability threshold has its own maximum paging cost, we have used the reference points associated with the simultaneous paging ($m=1$, also known as Blanket Polling (BP)). In this table, we can observe that, with some intelligence in the paging procedure, we can increase considerably the Hypervolume, which leads to a reduction in the signaling load. Furthermore, we notice that the Hypervolume gradually decreases as we increase the size of the first paging area, i.e. we can deduce that, in general, G-PA1 is the best probability threshold. Nonetheless, a different conclusion can be drawn if we combine the Pareto fronts of each probability threshold and we obtain the non-dominated solutions of this combined set, see Fig. 3, in where we present the Pareto fronts associated with the median Hypervolume ($\widetilde{\text {I}}_{\text {H}}$). As we can observe in this figure, every probability threshold has its own non-dominated region in the objective space. Thus, the network operator could choose a different probability threshold depending on the selected configuration of registration areas. It is also important to note that this feature of the geographical cluster paging would not have been detected without a multiobjective analysis. On the other hand, Fig. 4(a) presents a comparison between the simultaneous paging and the geographical cluster paging in the mobile network sited in Paris (similar comparisons were obtained with the other networks). As stated before, we can notice that the geographical cluster paging covers more area of the objective space than the simultaneous paging, and hence, we obtain more efficient configurations of registration areas. For example and assuming an LTE (Long Term Evolution) network with one Mobility Management Entity, if we select the non-dominated solution that minimize the total signaling load (see Fig. 4(b)), we can notice that the signaling load can be reduced by about 30 % (BP: 7,642,638 signaling messages per working day (4,787,136 messages due to location updates and 2,855,502 messages due to the paging procedure), G-PA: 5,363,228 signaling messages per working day (2,798,766 messages due to location updates and 2,564,462 messages due to the paging procedure)). It is also noteworthy that the use of a more efficient paging procedure allows configurations with higher registration areas, which leads to a reduction in the location update cost.

Table 1. Statistics of Hypervolume ($\widetilde{\text {I}}_{\text {H}~\pm ~ \text {iqr}}$)

Fig. 3.

Analysis of the obtained Pareto fronts

5.1 Comparison with Other Works

In this section, we compare our implementation of NSGAII with other optimization techniques published in the literature [9–14]. It should be noted that all of these optimization techniques are single-objective algorithms. Therefore and in order to compare with these previous manuscripts, we must select in our Pareto fronts the non-dominated solution that best optimizes the objective function used by these single-objective metaheuristics (i.e. $\mathbf f ^{\text {SO}} = 10\cdot \mathbf f _{1}+\mathbf f _{2}$). With the aim of performing a fair comparison, we have configured our implementation of NSGAII with the same population size (N$_{\text {POP}}=300$) and the same number of generations (N$_{\text {G}}=5000$) as in these previous works [9–14]. Furthermore, we use the same paging procedure (simultaneous paging) and the same test networks (LAl, where l is the number of network cells). The results of this comparative study are gathered in Table 2, in where we present the minimum value found of $\mathbf f ^{\text {SO}}$. Regrettably, an in-depth statistical study cannot be conducted because the experimental data of these previous works are not available. Furthermore, the authors of [9–12] only provide the minimum value found of $\mathbf f ^{\text {SO}}$. This table reveals that our implementation of NSGAII is also able to equal or even improve the results obtained with single-objective metaheuristics. This last is far from trivial because a single-objective metaheuristic is specialized in finding only one solution (i.e. the one that best optimizes its objective function), and our implementation of NSGAII is specialized in finding a wide range of non-dominated solutions.

Fig. 4.

(a) Comparison with simultaneous paging. (b) Selection of the non-dominated solution (mobile network of Paris).

Table 2. Comparison with other works published in the literature [9–14]: $\mathbf f ^{\text {SO}}$

6 Conclusion and Future Work

This manuscript presents a multiobjective analysis of the geographical cluster paging in a location update strategy based on registration areas, a mobility management strategy that defines a multiobjective optimization problem with two objective functions. To the best of our knowledge, this is a novel contribution of our research. This paging scheme is studied considering delay constraints and for different probability thresholds. With the aim of finding the best possible set of non-dominated solutions, we have used our implementation of the Non-dominated Sorting Genetic Algorithm II (a multiobjective evolutionary algorithm by means of which we have obtained our better results in our previous work). After an experimental study, we have noticed that the signaling traffic associated with the mobility management can be reduced by about 30 % with some intelligence in the paging procedure. Furthermore and after a multiobjective analysis, we have shown that each probability threshold has its own non-dominated region in the objective space. In this way, the network operator could choose a different probability threshold depending on the selected configuration of registration areas.

As a future work, it would be interesting to analyze the performance of other paging schemes and other location update strategies in a multiobjective way, as well as to compare them with the mobility management strategy studied in this manuscript. Concretely, the multiobjective analysis of paging schemes and dynamic location update strategies based on Markov chains could be a good challenge.