Èíòåðíåò ññûëêà: http://network.ee.tsinghua.edu.cn/green973/images/8/81/120000.pdf
WANG Hao1,2 , LIU Nan1, LI Zhihang1, WU Ping2, PAN Zhiwen1 & YOU Xiaohu1
1National Mobile Communications Research Laboratory, School of Information Science and Engineering,
Southeast University, Nanjing 210096, China;
2Signal and System at Department of Engineering Sciences, Uppsala University,
Uppsala 75121, Sweden
Received June 1, 2012; accepted September 1, 2012
Abstract 3GPP long term evolution (LTE) is a promising candidate for the next-generation wireless network, which is expected to achieve high spectrum eciency by using advanced physical layer techniques and flat network structures. However, the LTE network still faces the problem of load imbalance as in GSM/WCDMA networks, and this may cause significant deterioration of system performance. To deal with this problem, mobility load balancing (MLB) has been proposed as an important use case in 3GPP self-organizing network (SON), in which the serving cell of a user can be selected to achieve load balancing rather than act as the cell with the maximum received power. Furthermore, the LTE network aims to serve users with dierent quality-of-service (QoS) requirements, and the network-wide objective function for load balancing is distinct for dierent kinds of users. Thus, in this paper, a unified algorithm is proposed for MLB in the LTE network. The load balancing problem is first formulated as an optimization problem with the optimizing variables being cell-user connections. Then the complexity and overhead of the optimal solution is analyzed and a practical and distributed algorithm is given. After that, the proposed algorithm is evaluated for users with dierent kinds of QoS requirements, i.e., guaranteed bit rate (GBR) users with the objective function of load balance index and non-GBR (nGBR) users with the objective function of total utility, respectively. Simulation results show that the proposed algorithm leads to significantly balanced load distribution for GBR users to decrease the new call blocking rate, and for nGBR users to improve the cell-edge throughput at the cost of only slight deterioration of total throughput.
Keywords self-organizing network (SON), mobility load balancing(MLB), quality-of-service (QoS), load balance index, total utility
Citation Wang H, Liu N, Li Z, et al. A Unified Algorithm for Mobility Load Balancing in 3GPP LTE Multi-Cell Networks.
1 Introduction
3GPP long term evolution (LTE) network can achieve high spectrum eciency due to the usage of flat network structures and advanced physical layer techniques, i.e., orthogonal frequency division multiple access technology and multi-input and multi-output antennas [1-3]. However, as in GSM/WCDMA networks, the system performance is still influenced by unbalanced load distribution among nearby cells [4-6]. To deal with this problem, real-time inter-cell optimization is needed. Previous inter-cell optimizations in GSM/WCDMA networks are usually performed at the network planning stage, and often done manually; thus it cannot remain optimal when the environments change. Hence, it is necessary for the network to conduct inter-cell optimization dynamically and adaptively according to its environments, especially when the loads of cells are not uniformly distributed, namely not balanced, and vary with time. This issue has received much attention in 3GPP LTE self-organizing network (SON) [7], in which mobility load balancing (MLB) is an important use case.
There have been lots of methods considering load balancing problem in wireless cellular networks, among which “cell breathing” is a universal one applicable to arbitrary networks, e.g., WCDMA, WLAN and LTE. Using “cell breathing”, the coverage of congested (or idle) cells is contracted (or expanded) either by reducing (or raising) the pilot power [8,9] or by increasing (or reducing) the threshold of handover [10-12], thus making the load more balanced among cells. However, the granularity of “cell breathing” is too large since lots of cell-edge users may be switched out to nearby cells indiscriminately when only considering power factor, in which the discrepancy among users are ignored. Therefore, “cell breathing” can hardly achieve the global optimum of the networkwide load balancing objective function for all users. In circuit-switched networks (e.g., GSM), each active user is allocated a dedicated channel, and load balancing can be achieved through “channel borrowing” or “dynamic channel allocation”. Please refer to [13] and the reference therein. However, neither of the two methods can be applied to packet-switched networks (e.g., LTE and WCDMA), in which to support more users, a cell would use an e ective scheduling algorithm to allocate its time-frequency resources and therefore dedicated channels no longer exist. Hence, the corresponding load balancing in packet-switched networks is often modeled as an optimization problem on matching between users and cells according to di erent metrics [14-17]. However, most previous researches on load balancing in packet-switched networks only consider users without any quality-ofservice (QoS) requirements, and therefor may be incomplete in the LTE network which aims to serve users with di erent QoS requirements.
In this paper, we propose a unified algorithm to achieve MLB for users with di erent QoS requirements in the LTE network. In the proposed algorithm, a unified load balancing objective function for homogeneous users with the same kind of QoS requirement is constructed with the variables being cell-user connections. Then the complexity of the optimal solution is analyzed, which is proved to be an NP-hard problem, and a practical and distributed algorithm is given. Then the proposed algorithm is applied to two main QoS requirements in the LTE network [18], i.e., guaranteed bit rate (GBR) users and non-GBR (nGBR) users, respectively. For GBR users, the load balancing objective is formulated as the load balance index while that for nGBR users is formulated as the total utility. The e ectiveness of the proposed algorithm is verified by exhaustive simulations. Simulation results show that the proposed algorithm performs very well for both GBR and nGBR users, thus lead to significantly balanced load distribution for GBR users to decrease the new call blocking rate and for nGBR users to improve the cell-edge throughput with only slight deterioration of total throughput. Finally, we consider the case where both GBR and nGBR users exist in the network.
The rest of this paper is organized as follows. In Section 2, we give the system model. In Section 3, the unified optimization problem is formulated and the complexity/overhead of the optimal solution is analyzed, and then a practical and distributed algorithm is proposed. After that, both the problem formulation and the proposed algorithm are applied to GBR and nGBR users respectively in Section 4. Simulation results are given in Section 5. Coexistence of both GBR and nGBR users in the LTE network is considered in Section 6 and the whole paper is concluded in Section 7.
2 System Model
2.1 Network Model
The unified problem formulation and algorithm proposed in this paper can be applied to LTE network with any topology. For easy of presentation, a hexagonal network is considered here. As shown in Figure 1, there are seven cells numbered with 1,...,7, respectively, and each cell is controlled by a central eNodeB. Cell 1 is assumed to be an over-loaded one with more users than other cells. Its cell-edge users a, b and c can also be served by cells 3 and 4, 5, 2 and 7, respectively. If Cell 1 wants to handover some users for load balancing, which users and which target cells should be chosen? In the following, we deal with this problem by taking into consideration a unified load balancing objective function for all users in the network. Throughout this paper, cell and eNodeB are used interchangeably, and the following assumptions are made:
1) Each user knows the instantaneous signal strength from its serving cell and all the neighboring cells through pilot measurements. All users send them back to their respective serving eNodeBs periodically.
2) Each eNodeB allocates power equally to all the PRBs being used.
3) Neighboring eNodeBs can exchange their load status information periodically through the X2 interface [19].
4) Twelve adjacent subcarriers are grouped into a physical resource block (PRB), which is the smallest unit that can be allocated to each user in a subframe (1ms) [1]. 5) All time t mentioned in this paper represents the time point to conduct load balancing handover, and the span between any t and t + 1 is a load balancing cycle, which is much larger than a subframe. C, K and Ki are used to denote the sets of cells, users and users served by cell i, respectively. A cell-user connection variable Ii,k(t) is defined, which equals 1 when user k is served by cell i at time t, and 0 otherwise.
2.2 Link Model
The instantaneous signal to interference plus noise ratio (SINR) for user k received on PRB l from cell i
at a subframe 
is
where
gi;l;k( ) represents the instantaneous channel gain between eNodeB i and user k on PRB l at subframe . The
channel gain takes into account the path loss, log-normal shadowing and fast fading.
pt represents the equal transmit power on each PRB. And gi,l,k( )*pt is the instantaneously received signal
strength of user k from cell i on PRB l at subframe .
N0 is the additive white Gaussian noise (AWGN) on a PRB. Without loss of generality, we assume the noise level is the same for all PRBs.
Eq. (1) is justified for the case where all of the system resources are exhausted. Even for the case where there are
residual system resources, eq. (1) is still meaningful and can be seen as a conservative low-bound of the practicalreceived SINR. Given SINRi,l,k( ), the instantaneous bandwidth eciency ei,l,k( ) of user k in cell i on PRB l at
subframe is
3 Problem Formulation,Complexity/Overhead Analysis, and Practical Algorithm
3.1 Problem Formulation and Complexity/Overhead Analysis
A unified load balancing optimization problem is formulated with the optimization variables being cell-user connections. Our objective is to make use of enforced handover to perform load balancing for all users in the network, such that the maximum (or minimum) of the network-wide load balancing objective function with the optimal cell-user connections can be achieved. This is equivalent to the following constrained optimization problem:
Constraints in eq. (7) imply that one user can only be served by one cell at a certain time t. Constraints in eq. (8) explain that the minimum bandwidth eciency of any user k has to be satisfied strictly in its serving cell, which is reasonable because a cell-center users often may not be served by nearby cells. It is well-known that all minimization problems can be transformed into maximization problems with the negative objective function. The optimization problem is formulated as a maximization problem in eq. (6) for simplicity.
The above P1 is an integer optimization problem with the variable as cell-user connection Ii,k(t), which is similar to the optimization problem in [17] and has been proved to be an NP-hard problem even if the mapping relation f is simple enough to be a linear combination of each cell’s load. To the best of our knowledge, there are no e ective methods, except brute-force search (BFS), to find the optimum. However, the computational complexity of BFS is too tremendous. For example, if there exist p cells and q users in the network, the computational complexity of BFS increases with O(pq). Apart from the computational complexity, BFS also has implementation dificulties. Firstly, a central unit to run BFS is indispensable. Secondly, bandwidth eciency information feedback from all users to the central unit as well as the distribution of central unit’ s decision definitely brings a huge overhead to the network.
3.2 Practical and Distributed Algorithm
In this subsection, a practical and distributed algorithm is proposed for the above optimization problem P1. Since the objective function is optimized at each time t, we omit the symbol t in the following for convenience. In cell i, if a user k is switched to a neighboring cell j for load balancing, the gain of the handover for load balancing is defined as
where Obj(j,k) and Obj(i, k) stand for the network-wide load balancing objective function in eq. (5) after and before the handover, respectively.
In each cell i, there may be lots of users with a positive load balancing gain at the same time. To avoid ping-pong eject, in each load balancing cycle, cell i only chooses the user and its corresponding target cell with the largest load balancing gain defined in eq. (9), and meanwhile the constraints in eqs. (7) and (8) should be satisfied. That is, for all users in cell i, the user k and its target cell j are chosen as
4 Simulation
Simulations are performed to evaluate the performance of the proposed algorithm in terms of load balance index
and new call blocking rate for GBR users, total utility , fifth percentile throughput and total throughput
for nGBR users. The fifth percentile throughput is defined as the average of the lowest 5% throughput of nGBR
users and usually regarded as a representative performance metric of cell-edge users.
4.1 Simulation Setup
The network considered here is composed of seven hexagonal micro cells with unbalanced user distribution as shown in Fig. 1. The distance between adjacent eNodeBs is 130 m. The maximum transmission power of all eNodeBs is 38 dBm and the bandwidth is 10 MHz. The path loss in dB is 39 + 20log10(d); 10 < d 6 45 or 39 + 67log10(d); d > 45, where d is the distance from eNodeB to user (in meters). And the minimum coupling loss is -53 dB when d is less than 10 m. The standard deviation and correlation distance of log-normal shadowing are 10 dB and 25 m, respectively. And Rayleigh fast fading is considered in this paper. All of the parameters are consistent with the simulation scenario recommended by 3GPP in [22]. To avoid border e ects, the wrap-around technique [23] is used.
In order to provide practical simulation results, the proposed algorithm is investigated in a dynamic setting. GBR and nGBR users arrive in any cell i according to a Poisson process at uniformly distributed locations and depart from the system after holding for an exponentially distributed period with the mean of 100 seconds. The rate requirements of all GBR users are uniformly chosen from 64 256 kbps. To differentiate the load of neighboring cells, Cell 1 is chosen as the busiest cell with an alterable arrival rate for its serving users, while that in all the other cells are assumed to be 0:2 (user/second). Each simulation takes 1000 seconds, and simulations are performed thousands of times under each arrival rate of Cell 1 to get the average performance.
The choice of load balancing cycle is a tradeo between signaling overhead and the performance gain (the shorter the period, the better the performance, and the heavier the overhead). Since the load of each cell varies slowly due to the above settings, 1 second is taken as the load balancing cycle in our simulations. In the following, N/A and MLB are used to represent no handover for load balancing and run the proposed algorithm for load balancing in Section 4, respectively. Besides, CB is used to present the load balancing method of cell breathing, which is similar to that in [10] with reasonable modification to our scenario.
4.2 Optimality Analysis for both GBR and nGBR Users
In this subsection, an optimality analysis is given to compare the proposed algorithm to the optimal one, i.e., BFS.
Thousands of random static scenarios are picked, in which there are no user arrivals/departures but the number and
allocation of users are varying in each scenario. For each scenario the optimal user-cell connections was obtained
by BFS, and we evaluated the proposed algorithm for both GBR and nGBR users. Fig. 2 exhibits the CDF for the
performance ratios, which are defined as the ratio of performance values obtained from the proposed algorithm
to that from BFS. As can be seen, the performance ratio of load balance index exceeds 84% for almost all
scenarios, 90% for 91.4% scenarios, and reaches 100% for 56.6% scenarios. The performance ratio of total utility
exceeds 97% for all scenarios. The optimality loss of load balance index compared to that of total
utility mainly comes from the simplification in the deduction of eq. (16). From Fig. 2, we can conclude
that our proposed algorithm, which is ecient and easy to implement, is a good approximation of the optimal BFS
algorithm for both GBR and nGBR users.
4.3 Simulation Results of GBR Users
In this subsection, the simulations results are given in terms of load balance index and new call blocking rate
with an alterable arrival rate of Cell 1 for GBR users.
4.3.1 Load Balance Index of GBR Users
The variation of load balance index of GBR users with di erent arrival rates of Cell 1 is shown in Fig. 3.
We see that the load balance index OGBR
b j of N/A, CB and MlB all decrease monotonously with the increasing
arrival rates. That is reasonable since the value of arrival rate determines the degree of load imbalance. In other
words, the larger the arrival rate of Cell 1, the more unbalanced the load distribution among cells, and the lower the
load balance index . In addition, Fig. 3 shows that the load balance index in MLB is larger than that in
N/A and CB by about 8:42% and 5:24% on average, respectively. This demonstrates that the proposed algorithm
performs better than cell breathing and no handover, thus yielding significant performance gain for GBR users to
enhance the load balance index .
4.3.2 New Call Blocking Rate of GBR Users
The new call blocking rate of GBR users is shown in Fig. 4 and it increases with the arrival rates in N/A, CB and MLB. As shown in Fig. 4, utilizing the proposed algorithm leads to a decrease in the new call blocking rate of GBR users by about 72:28% and 53:43% on average compared to N/A and CB, respectively. With small arrival rates (0.3-0.4 user/second), the proposed algorithm can even avoid the blocking of newly arriving users completely.
5 Further Consideration
In this section, we consider the case where there are both GBR and nGBR users in the network. In each load
balancing cycle, we try to maximize and simultaneously. Since both of them are determined by the
cell-user connection 
, the problem can be formulated as the following multi-objective optimization
problem [24]:
For multi-objective optimization problem, the most intuitive approach is constructing a single aggregate objective
function, where linear weighted sum (LWS) of the objectives is a well-known method [25]. Another straightforward
way is sequential optimization (SO); that is, one objective is optimized first, followed by the other. LWS
gives di erent weights on both GBR and nGBR users while SO gives absolute priority to one objective, e.g., for GBR users. The service provider may decide which method to use, and our proposed algorithm can be applied
to both methods.
6 Conclusion
In this paper, a unified algorithm is proposed for MLB in the LTE network. The load balancing problem is first formulated as an optimization problem with the variables of cell-user connections. Then the complexity and overhead of the optimal solution are analyzed and a practical and distributed algorithm is given. After that, the proposed algorithm is evaluated for users with di erent kinds of QoS requirements, i.e., GBR users with the objective function as load balance index and nGBR users with the objective function as total utility. Simulation results show that the proposed algorithm can be applied for both GBR and nGBR users, and leads to significantly balanced load distribution for GBR users to decrease the new call blocking rate, and for nGBR users to improve cell-edge throughput at the cost of only slight deterioration of total throughput.
Acknowledgements This work was supported by the National Basic Research Program of China (973 Program 2012CB316004), the National Special Key Program (Grant Nos. 2011ZX03003-002-02, 2012ZX03003010-002, 2012ZX03001036-004), the International Science and Technology Cooperation Program (Grant No. 2008DFA12090), the Natural Science Foundation of China (Grant No. 61101086), the Research Fund of National Mobile Communications Research Laboratory at Southeast University (Grant No. 2012A02), the Jiangsu Provincial Key Technology R&D Program (Grant No. BE2012165), the Liuda Rencai Gaofeng of Jiangsu Province, and Huawei Corp., Ltd.
References
1 3GPP. Evolved Universal Terrestrial Radio Access (E-UTRA); LTE physical layer; General description (Release 10). 3GPP TS 36.201. 2010
2 3GPP. Evolved Universal Terrestrial Radio Access Network (E-UTRAN); Architecture description (Release 10). 3GPP TS 36.401. 2011
3 S. Sesia, I. Toufik, M. Baker. LTE, The UMTS Long Term Evolution: From Theory to Practice. John Wiley & Sons Ltd., 2011.
4 Tolli A, Barbancho I, Gomez J, et al. Intra-system load balancing between adjacent GSM cells. In: Proceedings of IEEE VTC, 2003. 393–397
5 Du L, Bigham J, Cuthbert L. Geographic load balancing for WCDMA mobile networks using a bubble oscillation algorithm. In: Proceedings of IEEE WCNC, 2005. 1714–1719
6 Zhu H, Buot T, Nagaike R, et al. Load balancing in WCDMA systems by adjusting pilot power. In: Proceedings of IEEE WPMC, 2002. 936–940
7 3GPP. Evolved Universal Terrestrial Radio Access Network (E-UTRAN); Self-configuring and self-optimizing network (SON) use cases and solutions (Release 9). 3GPP TR 36.902. 2011
8 Hanly S. V. An algorithm for combined cell-site selection and power control to maximize cellular spread spectrum capacity. IEEE J Selected Areas Commun, 1995, 13(7): 1332–1340
9 Bejerano Y., Han S. Cell breathing techniques for load balancing in wireless lans. In: Proceedings of IEEE INFOCOM, 2006.
10 Kwan R, Arnott R, Paterson R, et al. On mobility load balancing for LTE systems. In: Proceedings of IEEE VTC, 2010. 1–5
11 Suga J, Kojima Y, Okuda M. Centralized mobility load balancing scheme in LTE systems. In: Proceedings of IEEE ISWCS, 2011. 306–310
12 Wei Y, Peng M. A mobility load balancing optimization method for hybrid architecture in self-organizing network. In: Proceedings of IET ICCTA, 2011. 828–832
13 Katzela I, Naghshineh M. Channel assignment schemes for cellular mobile telecommunication systems: a comprehensive survey. IEEE Commun Surveys Tuts, 2000, 3(2): 10–31
14 Son K, Chong S, Veciana G. Dynamic association for load balancing and interference avoidance in multi-cell networks. IEEE Trans Wireless Commun, 2009, 8(7): 3566–3576
15 Wang H, Ding L, Wu P, et al. Dynamic load balancing and throughput optimization in 3gpp LTE networks. In: Proceedings of IEEE IWCMC, 2010. 939–943
16 Sang A, Wang X, Madihian M, et al. Coordinated load balancing, hando /cell-site selection, and scheduling in multi-cell packet data systems. Wirel Netw, 2008, 14(1): 103–120
17 Bu T, Li L, Ramjee R. Generalized proportional fair scheduling in third generation wireless data networks. In: Proceedings of IEEE INFOCOM, 2006. 1–12
18 3GPP. Technical Specification Group Services and System Aspects; Policy and charging control architecture (Release 11). 3GPP TS 23.203. 2012
19 3GPP. Technical Specification Group Radio Access Network; Evolved Universal Terrestrial Radio Access Network (E-UTRAN); X2 general aspects and principles (Release 10). 3GPP TS 36.420. 2011
20 Jain R, Chiu D, HaweW. A quantitative measure of fairness and discrimination for resource allocation in shared systems. Digital Equipment Corp., DEC-TR-301, Tech. Rep., 1984
21 Chiang M, Low S, Calderbank A, et al. Layering as optimization decomposition. In Proceedings of IEEE, 2007, 95(1): 255–312
22 3GPP. Technical Specification Group Radio Access Network; Physical layer aspects for evolved Universal Terrestrial Radio Access (UTRA) (Release 7). 3GPP TR 25.814. 2006
23 Kim S J, Wang X. Hierarchical approach to interference mitigation in multi-cell downlink orthogonal frequency-division multiple-access networks with low feedback. IET Communications, 2011, 5(5): 660–666
24 Marler R T, Arora J S. Survey of multi-objective optimization methods for engineering. Structural and Multidisciplinary Optimization, 2004, 26(6): 369–395
25 Marler R T, Arora J S. The weighted sum method for multi-objective optimization: new insights. Structural and Multidisciplinary Optimization, 2010, 41, 853–862.