DETERMINATION OF OPTIMAL HANDOVER BOUNDARIES IN A CELLULAR NETWORK IBASED ON TRAFFIC DISTRIBUTION ANALYSIS OF MOBILE MEASUREMENT REPORTS

C. Chandra

T. Jeanes
Motorola 1501 W. Shure Dr. IL27-AR3205 Arlington Heights, 11. 60004 USA

W.H. Leung

Abstract: Traffic distributions in a cellular network tend to follow periodic patterns where local congestions occur. By optimizing handover boundaries between neighboring cells, opportunities for load sharing can be exploited to maximize the capacity of the cellular network as a whole. We propose a method for determining optimal handover boundaries by analyzing historical measurement reports data, as an indication of traffic distribution patterns within the network; and modeling the problem as an optimization problem with a set of nonlinear constraints.

INTRODUCTION

To achieve ubiquitous coverage and call continuity the coverage areas among cells in a cellular network environment tend to be highly overlapped. Under normal conditions, mobiles are served by cells that provide the strongest signal strength and handovers are initiated when a neighbor cells received signal becomes stronger than the servers received signal, after some appropriate averaging window and hysteresis margin to avoid ping-pong handovers. In the case that more than one neighbor cell is stronger than the serving cell then handover is ideally attempted to the strongest neighbor. In a live network, the traffic load experienced by neighboring cells tends to vary at different times of the day and commonly follows predictable patterns according to rush hours and centers of activities. Often times, handing over to the strongest neighbor will not achieve the most capacity out of the network because some cells are more heavily loaded than others. By allowing mobiles to be served by cells with lower received signals but are within an acceptable quality level, localized congestion can be avoided and a higher call carrying capacity can be achieved by the combined network. This can be achieved by allowing less heavily loaded cells to serve mobiles beyond its ideal

boundary and distributing the traffic load more evenly among the cells through the use of handover preference margins. These handover margins reflect the loading of cells to offset the strongest received signal criteria for selecting handover target cells. When the overall generated traffic capacity in the network stays within the offered load, but moving concentrations of traffic exist, then dynamic adjustment of handover boundaries offers the least costly method for increasing localized capacity, without adding additional resources (e.g. carriers, new cells). Various congestion relief techniques to handle temporary traffic concentrations have been proposed in the literature. These techniques range from similar methods of changing boundary parameters to more costly methods that introduce additional hardware. More costly methods, such as using ada tive antennas to dynamically target traffic coverage have been propclsed, but these methods introduce new hardware to the system. Representative works in the first category include directed retry 13, overlapping cells with channel reuse partitioning [2 , and using an additional offset parameter to reflect cell loads to control han51. dover decisions [4, While these works propose similar schemes for moving handover boundaries to relieve local (congestion,a method of determining the optimal handover margins (boundaries) to maximize the overall network capacity has not been addressed. In this paper, we present an approach to determine optimal configurations of handover boundaries between neighboring cells to maximize overall network capacity that is based on an analysis of historical measurement report data. Unlike the various methods that have been proposed, where the system performs a reactive action to deal with congestion, our approach attempts to be more predictive of possible future congestion, by analyzing traffic patterns from previous measurement data. The rest of this paper is organized as follows. Section 2 provides a brief background of the basic handover algorithm in the GSM system. Section 3

fi]

0-7803-3659-3/97 0.000 1 997 IEEE $1

305

presents our approach to determining optimal handover margins configuration to maximize network capacity, by using nonlinear programming technique. Section 4 provides experimental results of this approach. Finally, we conclude in section 5.

Y mobiles o

I1

BACKGROUND

In GSM cellular system, the handover algorithm is based on four types of indications: 0 signal level (RxLev)
I

0 0

signal quality (RxQual) mobile distance (signal propagation delay) pathloss difference between server and neighbor cell (power budget) Figure 1: Distribution function of power budget of neighbor n is triggered. When more than one neighbor satisfies the above condition] then the neighbor with the highest power budget value is selected as the target cell for a handover. In order to set the H,, of various cells to the appropriate values, we need to know how much traffic would be absorbed by neighbor n by a setting of Hsn. approximation could be made by An looking at past measurements of mobiles in the boundary region of the serving cell having various values of power budgets for various neighbors n. Capturing the percentage of mobiles having particular power budget measurements will tell us how many mobiles are likely to handover to a particular neighbor cell when H,, is set to a certain value. We are only interested, however, in measurements of mobiles at the boundary regions that meet the following conditions: The measurement of RxLev(n) (signal strength) for neighbor n is above RxLev-Threshold where RxLev-Threshold is a measure of "good enough" signal level. This condition indicates whether the neighbor can adequately serve the mobile. PBGT(s,n) is among the three highest measured for the mobile. This condition ensures that the mobile is handed over to cells that are close to the location of the mobile. Capturing only the three highest measurements also simplifies the formulation of the problem, as will be seen later. By capturing the power budget measurements of mobiles and those measurements where the received signal strength from corresponding neighbors cells are below RxLev-Threshold, we can determine the distribution function F ( P B G T ( s ,n ) ) of mobiles that can't handover to a given nei hbor cell when the handover margin is set to PBGTTs, n ) . On a per neighbor cell basis, the percentage of mobiles that will be absorbed from the traffic currently covered by the serving cell, when H,, is set to a given power budget value is then: 1 - F(Hsn)

with corresponding thresholds for each handover criteria. While the signal level, signal quality, and mobile distance thresholds are based on hard performance requirements power budget is based on a less stringent criteria to minimize the pathloss between the serving cell and the mobile. The corresponding threshold for power budget, the handover margin, is then used to offset the minimum pathloss criteria to prevent pingpong at cell boundaries and as a "preference level" among the feasible serving cells. In an environment where the traffic is unevenly distributed among cells, the handover margin can be used as an offset to prefer covering cells, which are less heavily loaded.

I11

APPROACH

Our approach relies on past measurement data to predict the traffic distribution patterns and fit the handover margin threshold parameters to the measurement data in order to maximize the carried capacity of the entire network. Our analysis is based on measurements of downlink power level of the serving and surrounding base stations, which are reported by the mobile to its serving base station at every measurement period. At every measurement period, the following value is calculated at the base station, based on the measurement reports: PBGT(sln ) M P L ( s ) - P L ( n ) where PBGT(s, n) = the power budget of a neighbor cell n with respect to server cell s PL(n) = pathloss from mobile to neighbor cell n , PL(s) = pathloss from mobile to serving cell
S

When

P B G T ( s , n ) 2 H,,
where H,, is the handover margin from serving cell s to neighbor cell n , a handover caused by power budget

. Fig. 1 illustrates the relationship between the distribution function F ( ) and the percentage of mobiles that are absorbed by a neighbor cell.

306

with the following nonlinear constraints: For each i , j where i ranges over all cells and j ranges over all neighbors of cell i:

k c n e i g h b o r s of i ; k # j

f
Ti

\ Hik

+
x -y

1,mcneighbors of i ; l , m # j

< H i j - H i l , ~ -.Z < H i j - H i m ) )

*T,

Figure 2: Illustration of variable definitions We can now formulate the handover margin parameter optimization problem as a nonlinear optimization problem. Let the following variables define the parameters in the system: Ti = Traffic currently originated within cell is coverage, including served and blocked calls (Erlangs).

where 2 E P B G T ( i , j ) , y E PBGT(i,k) in the first summation and 2 E PBGT(i,j ) , y E PBGT(i,Z), and z E PBGT(i,m) in the second summation. For each cell i:

Si

52?:j c n e i g h b o r s of i

Gij

(4)

For each cell j :

Gij+Sj
i e n e i g h b o r s of j

5Rj

(5)

Si = Amount of traffic (ErXangs) from that will be retained by cell i with the optimized settings of
various handover margin neighbor parameters.

For each neighbor cells pair i, j:

Hij P < -Hji (6) where P > 0. Also, Z , S i , G i j , R i 2 0 and Hmin 5 Hij 5 Hmaz where Hmin and H,,, are not restricted in sign. In the above formulation, the first objective function tries to maximize the overall traffic carried by all the cells in the network. The second objective function makes a trade-off between maximizing capacity with maintaining good signal quality. Equation (2) tries to keep the setting of the handover margins as close to the ideal as possible, where the ideal is the situation when a handover is generated at the point when the signal strengths of the neighbor and serving cell are equal (handover margin equals 0). With this objective function, when there are more then one lightly loaded neighbors the overflow traffic will be partitioned to the neighbors such that the path losses are minimized. In (3), F ( ) denotes the distribution function of the power budget measurements and P ( ) denotes the corresponding joint probability functions. Equation (3), essentially states that the amount of traffic that cell i gives up to cell j is bounded by the percentage of mobiles having power budget measurements above the handover margin setting H i j . The additional terms in the multiplier are needed to reflect the overlapping regicins of the traffic distribution among the neighbor cells. The first summation is the overlap between any pair of neighbors, that may result in traffic attributed to neighbor j being actually absorbed by neighbor k. A mobile will actually be absorbed by neighbor k when its power budget measurement for neighbor j is greater than H i j , but the difference between the power budget measurements for neighbors j and k is less than H j j - H i k . In such a case,

Gjj = Amount of traffic (Erlangs) out of 2?: that cell i gives up to cell j when the handover margin is
set to
Hij Hij.

= Handover margin setting from cell i to cell j .

Ri = Resource (offered load) of cell i (Erlangs).

Fig. 2 illustrates the definition of these variables. In Fig. 2 cell i is shown to have two neighbor cells: j and k. The traffic that is currently generated within cell i is bounded by the heavy circle. The handover margins to the two neighbor cells are set to H i j and H i k respectively and with these settings, the distribution of traffic that cell i is giving up to cell j and k are denoted by the cross hatched regions ( G i j , G i k ) . The traffic that cell i retains is the shaded area that is left from the heavy circle after subtracting the cross hatched areas, and is denoted by Si. Note that since Ti includes the blocked calls that are originated in cell i , whereas Si, Gij, and Gik denote the amount of traffic that can actually be served by the cells according to each cells offered load, Z 2 S i + ~ j , - n e i g h b o r s of Gij. The optimization that we are interested in can be formulated using the following two objective functions:

i c c e l l s j e n e i g h b o r s of i

ieeells

and
i c c e l l s j c n e i g h b o r s of i

307

For each cell i:

j c n e i g h b o r s of i

where UT, is the slack in (4), that indicates how much more resources are required to handle the additional traffic in cell i. Similarly, from (5), the following can be derived: For each cell j: Figure 3: Relative placements of handover margin boundaries and the guard margin required between mutual neighbors to avoid ping-pong
i e n e i g h b o r s of j

PBGT(i,j ) -H i j < PBGT(i,k)- H i k . The joint density function in the first summation term exactly reflects the amount of traffic overlap that is absorbed by cell k out of the traffic that has already been attributed to cell j in the first distribution function term. The second summation term denotes the amount of overlap between any three neighbor cells. The first summation term would have reduced any three-way distribution overlap twice, therefore this amount has to be added back into the percentage calculation. Since our distribution functions only take into account the three highest power budget measurements, a three variable joint distribution is as far as we need to consider to account for overlapping regions among neighboring cells. Equation (4), is a constraint relationship among the traffic that each cell retains, the amount that it gives up to its neighbors and the total traffic generated within its boundaries. Equation (5), reflects the resource constraint of each cell. This constraint states that the amount of traffic that each cell absorbs from its neighbors and the amount of traffic that it retains (not including blocked calls) are bounded by its resources (offered capacity). Equation (6), is a constraint on the settings of the handover margins of neighboring cells to prevent ping-pong handovers. Fig. 3, illustrates the relative placements of the handover margin boundaries between neighboring cells that are necessary to avoid ping-pong. The parameter P denotes the distance between the two handover margin boundaries. Having formulated the handover boundaries optimization problem as a constrained nonlinear optimization, we can use an optimization tool to solve our objective function with its associated constraints to obtain optimal values for the handover margin parameters H . . . Our analysis optimizes over sets of measureexhibiting similar traffic distribution pattern. Each distribution pattern may then yield different sets of optimal handover margin settings. In the future, cluster analysis may be used to analyze similar distribution patterns. The results from the above analysis could also be used to determine the sites that need additional resources because of very high traffic concentration. From (4), the following can be derived:

where U R is the slack between the amount of resources ~ available in a cell and how much traffic its serving. The slack value indicates if additional resources are available in the cell to possibly increase its physical coverage. Both of the above slack information would help in the planning and deployment of additional resources for various cells in the network.

IV

EXPERIMENTAL RESULTS

ment xata that are gathered over a period of time,

Our experimental results are based on measurement reports data on a subset of carriers within six nearby cells in a live network. The measurement reports are analyzed for the power budget distributions of every significant pair of server-neighbor cells reported, where the significance level is set to 1% frequency of occurrence within the entire sample. We assume a normal distribution of the data, which were validated to model the actual measurements quite well. The number of significant neighbors for each of the six cells are 10, 16, 16, 14, 13, and 24 respectively, with a total of 71 significant cells in the cluster being analyzed. RxLewThreshoZd was set to -110 dBm in determining this distribution function. From the computed power budget distributions, the objective functions and the set of constraint equations (3), (4), are generated. The maximum and minimum allowable handover margins were set to Hmin -10 and = H,, = 15 respectively. The set of generated constraint optimization problem are then processed using MATLAB to compute the optimized handover margins to maximize the carried load of the network with 71 cells. The weighting factors for the two objective functions that were found to work well are 1 and 85 respectively. We assume that the six cells have a congestion profile that reflect blocking within 0-15%. For the remaining cells, channel utilization was set at 95%. Table 1 summarizes the original utilization (including blocked calls and optimized utilization (theoretical carried load) a ter adjustments of handover margins within each cell. Table 1 also indicates the total percentage (sum) of blocked calls and the theoretical percentage being carried after optimization of the handover margin. Due to space limitation, the power budget distributions and resulting optimized handover margins between pairs of neighbor cells are not shown here. These results show that quite significant capacity increase can be obtained from adjusting handover boundaries within

308

Table 1: Original (including blocked calls) and optimized utilization (carried load) within each

the acceptable quality and resource constraints of a network with typically high utilization.

CONCLUSION

Orig. 95% 95% 95% 95% 95% Optim. 95% 96% 96% 100% 100% 21 22 23 24 25 Cells 95% 95% Orig. 95% 95% 95% . Optim. 100% 100% 1oo%loo%loo%~ Cells 26 27 28 29 30 Orig. 95% 95% 95% 95% 95% . Optim. 96% 96% 100% 100% 96% . Cells 31 32 33 34 35 Orig. 95% 95% . Optim. 96% 95% Cells 36 37 I 38 I 39 I 40 fl U Orig. 95% 95% . Optim. 95% 95% 95 95 Cells 41 42 43 44 45 Orig. 95% 95% 95% 95% 95% . Optim. 96% 95% 95% 95% 95% 47 48 1 Cells 46 49 50 I Orig. 95% 95% - Optim. 95% 95% Cells 51 52 I 53 I 54 I 55 I] Orig. 95% 95% . Optim. 95% 95% Cells 56 57 58 59 60 Orig. 5 9 % 5 9 % 5 - 9 % 5 9 % 5 9 % . Optim. 96% 95% 96% 100% 95% Cells 61 62 63 64 65 Orig. 95% . Optim. 95% 95% 95 96 95% Cells 66 67 P E
,_

Oar approach assumes that traffic concentrations withiin regions in a cellular network tend to follow periodic patterns, therefore by analyzing past measurement data, we should be able to plan for similar traffic distributions that tend to recur in the future. By anticipating for similar traffic distributions, localized congestions could be redistributed to less congested neighboring cells to maximize the capacity of the whole network. Th,e optimization model that we developed allows the determination of the maximum capacity that can be achieved by moving handover boundaries; the setting of the handover margins to achieve that maximum capacity; and pinpoints areas where redistribution of traffic to overlapping cells can no longer increase the total carried capacity within the area, and therefore, additional resources may be required. Our experimental results show that significant capacity increase can be achieved by adjusting handover boundaries within the prescribed quality and resource constraints of the network. The tool that we developed can be used to guide the optimization of an already deployed network to adjust handover boundaries according to changing traffic concentrations.

1-

ACKNOWLEDGEMENTS
We thank Kenneth Haas for writing the patent application for this work.

References
13. Eklundh, Channel Utilization and Blocking ]?robability in a Cellular Mobile Telephone System with Directed Retry, IEEE Trans. of Communications, Vol. COM-34, Apr. 1986.
Eai-Po Chu, Stephen Rappaport, Overlapping Coverage with Reuse Partitioning in Microcellular Communication Systems, IEEE Vehicular Technology Conference, 1995. IMitsuhiko Mizuno, Takeo Ohgane, Application of Adaptive Array Antennas to Radio Communications, Electronics and Communications in ,Japan, Part 1, Vol77, No. 2, 1994.

m i

!3S. Kuek, Wai-Choong Wong, Rajiv Vijayan,

]David J. Goodman, A Predictive Load Sharing 9cheme in a Microcellular Radio Environment, lEEE Trans. on Vehicular Technology, Vol. 42, No. 4,Nov. 1993.

R. Bodin, A. Norefers, Load Sharing Control jor a Mobile Cellular Radio System, Patent No. 15241685, Aug. 31, 1993.

309