15.2 Intelligent Paging Scheme

The movement of MTs is modeled according to some ergodic, stochastic process. ^[9] To provide a ubiquitous communications link, irrespective of the location of MTs, the BSs (base stations) provide continuous coverage during the call, as well as in the idle state. When an incoming call comes to an MT, which roams within a certain LA, paging is initially performed within a portion of LA, which is a subset of the actual LA. This portion of the LA, which is a set of base stations of paging (BSPs), is termed a paging area (PA). Intelligent paging is a multistep paging strategy, ^[10] which aims at determining the proper PA within which the called MT currently roams. In order to quantitatively evaluate the average cost of paging, time-varying probability distributions on MTs are required. These distributions may be derived from the specific motion models, approximated via empirical data or even provided by the MTs in the form of partial itinerary at the time of last contact. It is assumed that

The probability density function of the speed of MTs is known.
The process of movement of MTs is isotropic, Brownian motion ^[11] with drift. In a one-dimensional version of Brownian motion, an MT moves by one step Ax to the right with some probability p, and to the left with probability q, and stays there with probability (1-p-q) for each time step At. Given the MT starts at time t = 0 for position x = 0, the Gaussian pdf on the location of an MT is given by

(15.1)

where v = (p - q) * (Δx/Δt) is the drift velocity, and D = 2[(1 - p)p + (1 - q)q + 2pq] (Δx)²/Δt is the diffusion constant, both functions of the relative values of time and space steps. Drift is defined as mean velocity in a given direction and is used to model directed traffic such as vehicles along a highway.
Time has elapsed since the last known location.
The paging process described here is rapid enough to the rate of motion of MT (i.e., MT, to be found, does not change its location during the paging process).

The algorithm of the intelligent paging process on arrival of a PR is

    While PR is attached {     while MT is not busy {      if current traffic load exceeds threshold traffic load {         initialize the incremental counter i = 0;         select the proper PA;         page within the selected PA;         if reply against PR received            then stop;         else {            while (i < maximum value of incremental counter i)              do {                page within another PA;                  increase the incremental counter i = i +1;              }         }      }      else         apply blanket paging;     }    }

The intelligent paging strategy maps the cells inside the location area comprising S cells into a probability line at the time of arrival of the incoming call. This mapping depends on factors such as mobility of the MT, its speed profile, the incoming call statistics, and the state of the MT at that instant. This procedure is called attachment. If it is detached, the paging requests (PRs) are cancelled. If it is busy, a relation between the MT and the network already exists and therefore paging is not required. If it is free, the network proceeds for paging upon receipt of a PR (see above algorithm). In an intelligent paging scheme, the network determines the probability of occupancy of the called MT in different cells in an LA. These probabilities are arranged in descending order. The order in which cells are to be polled depends on the ordered set of probability occupancy vectors. In each paging cycle, the MSC serves PRs stored in its buffer, independently of each other. It is done by assigning a BS to each of the n requests in the buffer according to an assignment policy. The j-th PR may be sent to the i-th BS, in order to be paged in the corresponding cell. There are many ways to generate such assignments. Two methods will be presented subsequently in this chapter as part of the proposed intelligent paging scheme. If the buffer size is n and there are k PAs (denoted by A_1, A₂, .., A_k), then we can write

A₁⋃A₂⋃.....⋃A_k = S

A_i⋃A_j = φ

This means that the PAs are mutually exclusive and collectively exhaustive. Paging and channel allocation packets from a BS to MTs are multiplexed stream in a forward signaling channel. Paging rate represents the average number of paging packets, which arrive at a base station during unit time. Paging signals are sent to the BSs via landlines and are broadcast over the forward signaling channel. As each attached MT in the location area constantly monitors the paging channels to check whether it is paged or not, the distributor in the MSC which is a part of MM allocates the distribution of PRs to the BSs for each paging cycle based on the information collected over the previous paging cycle. As soon as an MT is found, the corresponding PR is purged from the buffer and a new PR replaces it. The function of the distributor in the MM is to map the PRs to the PAs:

g : (PR₁, PR₂, ..., PR_n) → (A₁, A₂, ...,A_k)

Paging and channel allocation packets from a BS to MTs are multiplexed to stream in a forward signaling channel. Paging rate represents the average number of paging packets, which arrives at a base station during unit time. Paging signals are sent to the BSs via landlines and are broadcast over the forward signaling channel. As each attached MT in the location area constantly monitors the paging channels to check whether it is paged or not, the distributor in the MSC which is a part of MM allocates the distribution of PRs to the BSs for each paging cycle based on the information collected over previous paging cycle. As soon as an MT is found, the corresponding PR is purged from the buffer and a new PR replaces it.

Depending on the nature of polling, there may be two types of search, sequential and parallel-o-sequential. In purely sequential polling, one cell is polled in a paging cycle. Sometimes, due to delay constraint, instead of polling one cell at a time, we poll a cluster of cells in an LA. This is called parallel-o-sequential intelligent paging (PSIP), which is a special case of sequential intelligent polling (SIP). The network first examines whether a multiple-step paging strategy should be applied or not. The decision is based on the current traffic load. Normally, when this load exceeds a threshold value, a multiple-step paging strategy is employed (Figure 15.1). In the very first phase, the network decides whether checking the current status of the MT needs paging. The network then examines whether the appropriate type of paging is blanket paging or multiple step paging. The granularity factor (K) shows fineness in polling. In general, the granularity factor is defined as

K = (number of cells to be polled in a cycle)/(number of cells in an LA)

The maximum value of granularity factor is 1, when all cells in an LA are polled in one polling cycle. The granularity factor in SIP is

K^SIP = 1/(number of cells in an LA)

The granularity factor in PSIP is

K^PSIP = (number of cells in the cluster)/(number of cells in an LA)

We assumed a perfect paging mechanism where an MT will always respond to a paging signal meant for it, provided it receives the PR. However, situations may leave an MT undetected even though the distributor in the MSC is able to select the corresponding BS and initiate PR for it. Such a situation will arise when there are more PRs assigned to a BS by the distributor than the number of paging channels available in a cycle. As there are only l paging channels per BS, the PRs in excess of l will be considered blocked. These excess PRs will be attempted for sending to select BSs in subsequent paging cycles. So the called MT may be inside the area of an overloaded cell. But the PR for it might be blocked in a paging cycle. So, the distributor must keep track of the number of times a search has been attempted for the PR.

The application of intelligent paging includes the event of paging failures due to wrong predictions of the locations of the called MT. In such cases, another step or more than one step will be required (i.e., the called MT will be paged in other PAs). Continuous unsuccessful paging attempts may lead to unacceptable network performance in terms of paging delay. Moreover, the paging cost will increase with each unsuccessful attempt to locate the called MT. In such cases, the network does not preclude the option of single-step paging at certain intermediate point of search.

15.2.1 Sequential Intelligent Paging

In a sequential intelligent paging scheme, one cell is polled at a time and the process continues until such time the called MT is found or time out occurs, whichever is earlier. The selection of the cell to be polled sequentially depends on the value of occupancy probability vector, which is based on the stochastic modeling delineating the movement of the MT. In SIP, the PRs are stored in a buffer of MSC, and each PR is sent to that BS where there is maximum probability of finding the called MT. When the paging is unsuccessful during a polling cycle, the MT is paged sequentially in other cells of the LA that have not been polled so far. This phase is completed in one or more paging step(s). The sequential paging algorithm is

STEP 1:	When an incoming call arrives, calculate the occupancy probability vector [P] of an MT for the cells in the LA based on the probability density function, which characterizes the motion of the MT;
STEP 2:	Sort the elements of [P] in descending order;
STEP 3.0:	FLAG = False; i = 1;
STEP 3.1:	Poll the i-th cell for I ∈ S;
STEP 3.2:	If the MT is found FLAG = True; Go to ENDSTEP;
STEP 4.0:	If time out occurs Go to ENDSTEP; Else i = i+ 1; Go to STEP 3.1; Endif
ENDSTEP:	If FLAG = True Declare "Polling is Successful"; Else Declare "Polling is Unsuccessful"; Endif

As extra processing is required to be done at the MSC, an inherent delay will be associated with this process, i.e., before the PR is sent to the appropriate BS. This delay includes the determination of the probabilities in different cells, sorting of these probabilities in descending order, and polling the cells sequentially depending on those values. This delay will be added to the call setup process. The amount of this delay will be ~ [O (S) + O (S log S) + O (S/2)].

15.2.2 Parallel-o-Sequential Intelligent Paging

Parallel-o-sequential intelligent paging is a special case of SIP where K > 1. Instead of polling a single cell in each cycle, here we partition the LAs into several PAs and poll those PAs sequentially comprising more than one cell. The benefit that accrues out of PSIP is significant improvement in expected discovery rate of called MTs and the overwhelming reduction in paging cost and signaling load. The number of steps in which the paging process should be completed depends on the allowed delay during paging. The application of PSIP also includes the event of paging failures due to unsuccessful predictions of location of called MT. In such cases, multiple steps are required and the called MT is paged in another portion of the LA. To obviate the deterioration of the network performance in such a situation and minimize the number of paging steps, the network should guarantee formation of PAs such that the P_SFP is high (typical value > 90 percent). So, the PA should consist of those cells where the sum of probabilities of finding the called MT is greater than or equal to the typical value chosen for P_SFP. The parallel-o-sequential paging algorithm is

STEP 1:	When an incoming call arrives, find out the current state of the called MT;
STEP 2:	If MT is detached PR is cancelled; Go to ENDSTEP; Else If MT is busy (location is known) Go to ENDSTEP; Else Find granularity factor K; Endif
STEP 3:	If granularity factor is 1 Poll all the cells; Go to ENDSTEP; Else Find out [P], the occupancy probability vector of the MT for the cells in the LA, based on the probability density function, which characterizes the motion of the MT; Endif
STEP 4:	Sort the elements of [P] in descending order; Set all the cells as "unmarked";
STEP 5.0:	Select a proper PA consisting of "unmarked" cells for which Sp_i > PSFP; FLAG = False;
STEP 5.1:	Poll i-th cluster and label the cells in i-th cluster as "marked"
STEP 5.2:	If the MT is found FLAG = True; Go to ENDSTEP;
STEP 6.0:	If time out occurs Go to ENDSTEP; Else Go to STEP 5.0; Endif
ENDSTEP:	If FLAG = True Declare : "Polling is Successful"; Else Declare "Polling is Unsuccessful"; Endif

15.2.3 Comparison of Paging Costs

In the conventional or the blanket paging, upon arrival of an incoming call the paging message is broadcast from all the BSs in the LA, which means all the cells in the LA are polled at a time for locating the called MT, i.e., each MT is paged S times before the called MT is discovered. The polling cost per cycle is

(15.2)

The SIP strategy described here aims at the significant reduction in load of paging signaling on the radio link by paging a cell sequentially. PRs arrive according to a Poisson process at the buffer of the MSC. The distributor issues the PRs to appropriate BSs. These PRs are queued at the location and serviced on FCFS at the average rate ζ. The result may be a success or a failure. The results of completed polls are fed back to the controller in the BS for further appropriate action. As pointed out earlier, a called MT may not be found during a paging cycle. Either the number of paging channels may be insufficient to accommodate the PR in a particular cycle or the search for the called MT in the cell results in a failure. In both cases, the polling process goes through more than one cycle. So, the paging cost per polling cycle in this scheme is

(15.3)

The variable z accounts for the unsuccessful PRs from the previous cycle due to either of two reasons: z depends on the success rate, time-out duration, and the number of paging channels available per BS. In GSM, assuming that a sufficient channel for paging is there, z becomes zero. In the best case, i.e., when the called MT is found during the first polling cycle of SIP, z also is zero. In the worst case, all the cells in the LA are to be polled before the MT is found. Then the polling cost just exceeds that of GSM. Moreover, the delay is maximum, i.e., S units. There may be a situation when the polling cost in the SIP scheme exceeds the cost in blanket polling significantly. If the MT resides in a cell with a low occupancy of probability and returns to one of the cells, which is polled already after the polling cycle, the called MT will not be found even after polling all the cells in the LA. Such an incidence is likely when the number of cells is more, a few cells have the same probability of occupancy, and the MT is very mobile. In this case, the call is blocked or the cells are polled sequentially once again to find out the MT. So, K has an inverse effect on z. The granularity factor K is generally chosen more than once to avoid such a scenario. The paging cost per polling cycle in PSIP is

(15.4)

The variable z also accounts for the unsuccessful PRs from the previous cycle. As mentioned earlier, K is chosen such that P_SFP > 0.9. The optimum value of K varies from case to case.

^[9]Bhattacharjee, P.S., Saha, D., and Mukherjee, A., Paging strategies for future personal communication services networks, Proc. 6th Int. Conf. on High Performance Computing (HiPC'99), Calcutta, India, Dec. 1999.

^[10]Markoulidakis, G.L. et al., Evaluation in LA planning in future mobile telecommunication systems, Wireless Networks, 1995.

^[11]Papoulis, A., Probability, Random Variable and Stochastic Processes, 3rd ed., McGraw-Hill, New York.