A Reservation and Retrial Queue Analysis for Cellular Networks

A Reservation and Retrial Queue Analysis for Cellular Networks

Anioke Chidera Linda

Department of Electronic Engineering University of Nigeria Nsukka

Nigeria

Cosmas I. Ani

Department of Electronic Engineering University of Nigeria Nsukka

Nigeria

AbstractIn cellular networks, dropped calls and blocked calls can be a problem. This problem can be mitigated if the network service is optimized. Service optimization can be achieved by employing a reservation scheme and a retrial queueing scheme. In this paper, an analytical model that employed an approximate technique was formulated. A two dimensional continuous time markov chain (CTMC) provided a complete description of the system states and their transitions. Results show that the reservation scheme with retrial improved the networks performance by minimizing to a large extent the blocking probability and the handover dropping probability even under high load conditions.

Keywordsretrial queue, handover, CTMC

1. INTRODUCTION

   The mobile cellular network is saddled with an exponential growth of subscribers impelling the communication industry to provide extensive information access [1]. This means that an increase in cellular network capacity is required to optimize network usage [2]. Techniques are therefore employed in the design of the cellular network so as to increase the number of cells in a given network area. Consequently cell sizes shrink resulting to the microcellular network structure which leads to an overlapping of cells and an increase in the number of handovers in the network.

   Therefore, a technique must be employed to prioritize handovers as well as satisfy new calls that are in danger of being blocked from getting a free channel. The technique adopted to improve the QoS of the network is the guard channel scheme with retrial queue. The retrial queue is a special type of queueing system that takes into account the retrial phenomenon where arriving calls that find all the channels in a cell occupied will tend to retry for service after a random interval of time following a random order discipline or the FCFS discipline [3, 4]. Guard channels are channels that are reserved solely for handovers [2]. Its adoption is due to its simplicity and ease of analysis.

   In literature, variants of the guard channel and the retrial queue have been implemented in both telecommunication and computer networks as a way of optimizing service. For

   instance, a handover retrial mechanism with the guard channel scheme was applied in [5], nevertheless consideration was given only to the handover calls. A complex and not entirely tractable recursive method was used to derive analytical models from which the network performance parameters were evaluated. In [6], the fractional guard channel (FGC) scheme alongside the retrial queue was implemented in a wireless cellular network. A computational algorithm with the matrix analytical approach was used to determine the network performance. To improve the performance of the GSM, the MOSEL (Modelling, Specification and Evaluation Language) tool a complex computer programming language was applied in [7]. However, these approaches are complex and are unable to track the system responses analytically.

   Since deriving the steady-state probabilities in most retrial queue systems is challenging [3, 8], an approximate approach will be employed. Approximate techniques have been applied in [8] to evaluate the performance of an M/M/2 retrial queue where both servers are subject to active and idle breakdowns. In this paper, fairness is considered in resource reservation for all call types new and handover calls. The analytical solution, which combines the characteristics of the guard channel with the retrial queue phenomenon, derived in [9] is applied in this work. From the responses obtained, it has been shown that new calls should be treated fairly and not to be entirely blocked from gaining access to the network when the handover calls are absolutely comfortable to achieve service optimization.

   The rest of the paper is structured as follows. Section 2 describes the analytical and physical model of the system. Section 3 defines the performance parameters of interest and validates the analytical model. Section 4 evaluates the impact that the different features of the model have on system performance. It also determines the various responses required to meet a given QoS objective. Section 4 concludes the paper and makes recommendations.

2. MODEL DEVELOPMENT

1. PHYSICAL MODEL

   The physical model of the network is shown in Figure 1. An isolated node in an isolated cell admitting two types of calls as well as guard channels for reservation is considered. Cells are assumed to be identical. Both types of calls are assumed to arrive according to a Poisson distribution with exponentially distributed interarrival times. The rates of distribution for both new and handover calls are N and H respectively with exponentially distributed and random holding times, µ. It is also assumed that blocked new calls will retry for a free channel with retrial probability or abandon the system and be lost with probability 1- if blocked the second time. A

   The analysis of each state of the markov model is complex and it involves so many variables, therefore, an approximate technique developed by Korolyuk and Korolyuk [10, 11] known as the Phase Merging Algorithm (PMA) will be applied in the network analysis. The PMA is a mathematical tool that eliminates complications or complexity in the construction of a mathematical model required for an adequate description of real systems [10]. By applying the PMA, a simplified model of the system is constructed based on the merged phase space of the system state [10, 11]. The PMA works by splitting the state space of the two-dimensional markov model into classes or sets that do not intersect with each other.

   limited number of retrials in the network will prevent a

   The state space is defined as; =

   , = , ;

   =0

   negative influence of retrials on new calls that are arriving at the network for their first call attempt and also on handover calls. The time between retrials is exponentially distributed and the retrial rate is denoted by . Among the channels in the system there are the free channels which accept new and handover requests, while the guard channels, g, are reserved sorely for handover requests. A queue with size K is provided to hold blocked calls (new) for a second retrial at the free channel. After unsuccessful retrials, the blocked calls return to the queue with probability 1 or leave the system 1-1.

   = 0,1,2, , + 1, defines the occupied channels at time t and = 0,1,2, defines the number of calls in the retrial queue at time t. Each set correspond to the levels of the retrial queue. This results in a finite number of levels which is analyzed individually. The PMA will be applied in a form that is suited to a two-dimensional CTMC

   [9] to obtain the steady-state probabilities of the network and also the system performance measures.

   H 1

   N

   . . . . .

   K . . . . 2 1

   2

   .

   .

   n-g n-g+1

   .

   .

   µ

   guard channels (g)

   1

   Retrial Queue

   1-

   n

   1-1

   Figure 1: Physical representation of the guard channel system with retrial queue.

2. ANALYTICAL MODEL

The network is modelled as a two dimensional continuous time markov chain (CTMC) as shown in Figur 2. The state of the system is described by a two variable random process in continuous time, {X(t), Y(t) : 0}, where X(t) is the number of occupied channels at time t and Y(t) is the number of blocked new requests in the retrial queue. The state space of the CTMC is defined as; S = {, }, = 0,1,2, , + 1, ; = 0,1,2, . P(, ) is the probability that the system

is in a state (, ) where (, ) S.

To determine the approximate steady-state probability, the first step is to determine the conditional probability distribution of the number of channels occupied at time t given the number of blocked new requests in the retrial queue also at time t. Secondly the marginal probability of the different levels of the retrial queue is determined.

The following assumptions were made in the application of the PMA. In order to accurately approximate the joint probability distribution, it is assumed that the transition intensities between states in the same level are significantly greater than the transition intensities between levels (i.e. the retrial queue). This assumption is realistic because in cellular networks, the flow of traffic in and out of the channels is

greater than the flow between the retrial queue waiting spaces.

0 +

( ) = 1 (4)

It is also assumed that is independent of since the value of

=0

!

= +1

!

is constant for each level as illustrated in Figure 2. Each level is analyzed as a CTMC where the birth-death analysis is

The initial conditional probability 0

1

employed. From this analysis the approximate conditional

probabilities, | of one variable with respect to the variable

0 =

+

( )

(5)

of the disjoint sets are determined.

!

=0

= +1

!

Each level of the retrial group is then considered as a macrostate (an aggregate of all states in a level or a merged model). These macrostates form the overall state space of the

merged model which is defined as

Level 1 Level 2 Level 3 Level 4

0, 0 0, 1

0, 2

. K 0, K

µ

1, 0

2µ

µ

1, 1

2µ

2

2

µ

3

1, 2

2µ

.

.

.

. K

µ

1, K

2µ

—– —— —— ——-

(n-g)µ

(1- )

(n-g)µ

2

2(1- )

(n-g)µ 3

(n-g)µ

.

n-g, 0

1

N

n-g, 1

1

N

n-g, 2

3(1-1)

N

K(1-1)

.

n-g, K

N

H (n-g+1)µ H

(n-g+1)µ 2

(n-g+1)µ

H 3

. K

H

n-g+1, 0

(1-1)

N

n-g+1, 1

2(1-1)

N

n-g+1, 2

3(1-1)

N

K(1-1)

.

N

n-g+1,K

(n-g+1

H (n-g+2)µ

H

(n-g+2)µ

2 H

(n-g+2)µ

. K H

(n-g+2

—– —— —— ——-

nµ

3 .

2 nµ H

H H

(1-1)

nµ H

2(1-1)

3(1-1)

nµ

.

K(1-1)

n, 0

N

n, 1 n, 2

N

N

N

n, K

Figure 2: State transition diagram of the two dimensional markov chain.

= |

=

! 0 1

0 <

!

Applying the normalization condition in (2)

(1)

merged model which is defined as : . The macrostates are also analyzed as a CTMC where the flows

between macrostates correspond to calls entering or leaving the retrial queue. The macrostates form the overall state space of the merged model. Analyzing this system of macrostates yields the approximate marginal probability distribution of the

=0

= 1 (2)

number of blocked new requests in the retrial queue.

Therefore;

The transitions into and out of the macrostates can be

= !

=0

• 0 +

=+1

0 (3)

!

expressed in (6) and (7);

Factorizing 0 from (3)

=

(6)

1

(1 )

+ (1 1) (7)

( ) =

N (, )

(14)

=

=

= +1 =1

Let the total traffic intensity between the macrostates be defined as q,

b. Handover dropping probability, PH: The handover

=

=

(8)

dropping probability can be determined when all the channels

1 + (1 1)

in the network are occupied including the guard channels.

=

=

From the state transition diagram of Figure 2, the probability

The steady-state marginal probability will be obtained by applying the Erlang formula to the merged model.

= ! 0 (9)

is defined as the marginal probability for each level of the

of dropped handover calls can be obtained at state (n, 0). At this state all the cell resources are fully occupied and there are only waiting spaces on the retrial queue for blocked new calls to retry for service.

merged model and 0 is defined as the initial marginal probability for the merged model.

= (, )

=

(15)

To obtain the initial marginal probability, all probabilities on the system of macrostates are summed to unity.

PH largely depends on the amount of resources in the cell and how these resources are distributed or utilized.

! 0 = 1 (10)

=

1. NUMERICAL EVALUATION

   =

   1

   The numerical evaluation is aimed at assessing the impact on

   0 = !

   (11)

   performance of varying the values and/or distribution of the

   Substituting equation (11) into equation (9) the steady-state marginal probability in equation (10) will be the same as the Erlangs formula.

   !

   system parameters. Both the handover calls and the new calls are accounted for. Each blocked new call tries to reconnect with the network with retrials separated by time intervals that are randomly distributed. Guard channels are reserved for handover calls when the free channels are all occupied. The

   =

   (12)

   considered cell can handle up to n=10 simultaneous active

   communications. Table 1 lists the parameters used in the

   =0 !

   The approximate steady-state probability distribution can be obtained by taking the product of the approximate conditional probability and the marginal probability to obtain a joint probability distribution which is the steady state distribution of

   {X(t), Y(t) : 0}.

   1. SYSTEM PERFORMANCE MEASURES

      numerical evaluation, their values and the description of each parameter.

      Table 1: Parameter values

      Parameter	Value	Description
      n	10	Number of channels in each cell
      g	3	Number of guard channels
      	0.001 to 1.000	Traffic intensity for handover calls
      	0.01 to 1.01	Total traffic intensity
      	0 to 10	Amount of traffic
      	1 5per sec	Service departure rate
      	0.4 per sec	Rate of retrial
      	10	Number of waiting spaces on p>the retrial queue

      The new call blocking probability, PB and the handover call

      dropping probability, PH are the system performance measures to be computed. Therefore the states in which a call may be blocked or dropped will first be identified.

      a. Blocking Probability, PB: The blocking of new calls result from the fact that all the free channels are busy or occupied at the time call arrived. Therefore, such calls cannot be served on their first attempt. The blocking probability can be obtained by considering events on the state diagram of Figure 2 that resulted to the free channels being occupied.

      = , (13)

      = +1 =

      By introducing the retrial queue into the system, blocked calls that cannot be served on their first attempt retry for service after a random time interval following a random order discipline.

      1. RESULT EVALUATION

         First the response of the network without a reservation scheme or the retrial queue is considered. This response will determine if there is an improvement in the networks QoS standard and how much improvement there is when the call improvement schemes have been applied. Figure 3 presents this response and as expected, the volume of calls blocked from gaining access into the network is very high. Also there will be an

         increase in forcefully terminated calls. With the introduction of the reservation scheme and the retrial queue into the cell, blocked calls are greatly reduced as presented in figure 4. The number of blocked calls is negligible thus improving the network QoS standard and consequently customer satisfaction. The reservation scheme used also reduces the number of calls dropped while being handed over from one cell to another. This is evident from figure 5 which presents PH as a function of . From the response, there is an increase in the probability of successful handovers.

         To arm the network operator with choices needed to achieve a high QoS standard, PH is plotted as a function of n. This response is presented in figure 6. Increasing n gives the network more channels and lesser dropped calls.

         Figure 7 compares different responses, PB with retrial and reservation (g=3), PB with retrial and no reservation (g=0) and PB without retrial or reservation. This comparison confirms that the retrial queue and the reservation scheme employed enhance the network QoS. The responses also show that with retrial and reservation schemes, the network will operate at its optimum with minimal or no congestion even in high traffic situations.

         Blocking probability without retrial vs varying traffic intensity

         0.0001

         0.00009

         Blocking Probability, PB

         0.00008

         0.00007

         0.00006

         0.00005

         0.00004

         0.00003

         0.00002

         0.00001

         0

         -0.00001

         0 0.5 1 1.5

         Traffic intensity,

         Blocking probability

         Blocking Probability with retrial

         2.5E-11

         2E-11

         1.5E-11

         1E-11

         Blocking Probability with retrial versus total traffic intensity

         3E-11

         Blocking Probability, PB (with retrial)

         Figure 3: Blocking Probability versus total traffic intensity without retrial or reservation.

         0.5

         1

         1.5

         Traffic intensity,

         5E-12

         0

         -5E-12 0

         Figure 4: Blocking probability with retrial and reservation versus traffic intensity.

         Handover dropping probability versus increasing total traffic intensity

         1.2E-10

         Handover dropping probability,PH

         1E-10

         8E-11

         6E-11

         4E-11

         2E-11

         0

         -2E-11

         0.

         5

         1

         0

         Traffic intensity,

         handover dropping probability

         1.

         5

         Handovver dropping probability, PH

         Figure 5: Handover dropping probability versus increasing total traffic intensity

         Handover call drop probability versus number of channels

         1.00000E-04

         6 8 10 12

         1.00000E-05

         1.00000E-06

         Handover drop

         1.00000E-07 probability

         1.00000E-08

         1.00000E-09

         Number of channels, n

         Figure 6: Handover dropping probability versus number of channels

         Comparing the blocking probabilities with and without retrial and guard channels

         1.

         1

         8

         0.

         6

         0.

         4

         0.

         .2

         0.1

         Blocking Probability, PB

         0 2

         0.001

         1E-05

         1E-07

         1E-09

         1E-11

         1E-13

         1E-15

         Blocking probability with retrial,g=3

         Blocking probability with retrial,g=0

         Blocking probability without retrial, g=0

         1E-17

         Traffic intensity,

         Figure 7: Blocking probabilities for different responses

      2. CONCLUSION AND RECOMMENDATION

The advantage of the retrial queue stems from the fact that it reduces the blocking probability of new requests and it aids the network operator to maintain a stable and high quality network even under high traffic situations. The choice of application of the conventional guard channel scheme is due to its simplicity, ease of analysis and implementation and lesser control parameters. Moreover the conventional guard channel scheme greatly improves the handover dropping probability and prevents the forced termination of handover requests. It was observed that an increase in the number of channels or system resources minimizes the handover dropping probability to a large extent. Finally, a comparison was carried out on the different responses obtained in order to determine the best scheme for various traffic conditions. We observed that by integrating the retrial queue and guard channel scheme into the network, it can operate in areas of both high and low traffic intensities with very little variation in the performance measures. However, with the application of the retrial queue alone without guard channels, the network will not operate at its optimum.

REFERENCES

1. Theodore S. Rappaport, Wireless Communications Principles and Practice. Prentice Hall, 2002, ISBN 0-13-042232-0.

2. Michael Mandjes and Kurt Tutschku, Efficient Call Handling Procedures in cellular mobile networks. Institute of Computer Science University of Wurzburg, July 1996.

3. Jesus R. Artalejo and Antonio Gomez-Corral, Retrial Queueing Systems: A Computational Approach, Springerlink, 2008, ISBN 978-3- 540-78724-2.

4. I. Atencia, P.Moreno, A Single-server Retrial Queue with General Retrial Times and Bernoulli Schedule, Applied Mathematics and Computation, Elsevier Inc., pp 855-880, 2005.

5. Jahangir Khan et al, Cellular Handover Approaches in 2.5G to 5G Technology, International Journal of Computer Applications (0975- 8887), vol. 21, May 2011.

6. Tien Van Do, Solution for a Retrial Queueing Problem in Cellular Networks, International Journal of Mathematical and Computer Modelling, volume 53, pp 2059-2066, June 2011.

7. Brian P. Crawford, Approximate Analysis of an unreliable M/M/2 Retrial Queue, Department of Operational Sciences, Airforce Institute of Technology, Wright-Patterson Air Force Base Ohio, March 2007.

8. J.M Gimenez-Guzman et al, Analysis of a cellular network with user redials and automatic handover retrials, Proceeding of the 7th International Conference on Next Generation Teletraffic and Wired/Wireless Advanced Networking, pp 210-222, 2007.

9. Bong Dae Choi, Agassi Melikov and Amir Velibekov, A Simple Numerical Approximation of Joint Probabilities of calls in service and calls in the Retrial Group in a Picocell, Appl. Comput. Math, vol. 7, no. 1, 2008.

10. Vladimir S. Korolyuk and Nikolaos Liminios, Stochastic Systems in Merging Phase Space, Singapore, World Scientific Publishing Co. Plc Ltd, 2005, ISBN 981-256-591-4.

11. Vladimir S. Korolyuk and Vladimir V. Korolyuk, Stochastic Models of Systes, Kluwer Academic Publishers, Boston 1999, ISBN 0-7923- 5606-3.