Advanced
Load Balancing Algorithm of Ultra-Dense Networks: a Stochastic Differential Game based Scheme
Load Balancing Algorithm of Ultra-Dense Networks: a Stochastic Differential Game based Scheme
KSII Transactions on Internet and Information Systems (TIIS). 2015. Jul, 9(7): 2454-2467
Copyright © 2015, Korean Society For Internet Information
  • Received : January 25, 2015
  • Accepted : June 02, 2015
  • Published : July 31, 2015
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
Haitao Xu
School of Computer and Communication Engineering, University of Science and Technology Beijing (USTB) Beijing, 100083 - China
Zhen He
School of Computer and Communication Engineering, University of Science and Technology Beijing (USTB) Beijing, 100083 - China
Xianwei Zhou
School of Computer and Communication Engineering, University of Science and Technology Beijing (USTB) Beijing, 100083 - China

Abstract
Increasing traffic and bandwidth requirements bring challenges to the next generation wireless networks (5G). As one of the main technology in 5G networks, Ultra-Dense Network (UDN) can be used to improve network coverage. In this paper, a radio over fiber based model is proposed to solve the load balancing problem in ultra-dense network. Stochastic differential game is introduced for the load balancing algorithm, and optimal load allocated to each access point (RAP) are formulated as Nash Equilibrium. It is proved that the optimal load can be achieved and the stochastic differential game based scheme is applicable and acceptable. Numerical results are given to prove the effectiveness of the optimal algorithm.
Keywords
1. Introduction
O ur world will be changed by connecting anything to anything in 5G [1 - 2] . Moreover, unlike its predecessors, 5G needs to provide increasing mobile data traffic and bandwidth to satisfy the increasing services requirements. One available solution to meet the demand for higher data rate is to reduce the size of the cell [3] , to obtain higher spectral efficiency with higher frequency reuse. Additionally, coverage can be improved by deploying small cells. As one of the main technology in 5G networks, Ultra Dense Network (UDN) can be used to improve network coverage [4 - 5] , greatly improve system capacity, and to bypass their business, can realize more flexible network deployment and more efficient frequency reuse.
Generally speaking, the micro cells (small cells) are not new concept in the research of wireless network, ultra-dense networks (UDNs) are eager for performing better through the re-considering and recapture of the traditional network technologies [6 - 7] . RoF (Radio over Fiber) [8] , the integration of optical and broadband technology, can be used as micro cell in next generation network and be comprised to form a UDN to achieve higher transmission data rate. RoF technology combines the advantages of optical fiber communication and wireless mobile communications together, such as: high capacity, low power consumption, low cost, easy installation, etc., and is becoming a hot research topic in recent years. In this paper, we consider using RoF as micro cell to form a UDN to improve network coverage and system capacity. Since the coverage of the RoF system is relatively small, the frequent movement of users will influence the system’s performance, which causes improper traffic distribution problems. There are three possible scenarios that the RoF system is overloaded [9] ,
(1) Handoff-intensive caused by the users’ movement, the processing task is complex in the overlapping region;
(2) The cell edge users are in severe channel environments, which can be considered as relative overload;
(3) Multipath propagation, fading, and superposition of multiple antennas would cause an overload.
Because of the randomness of load variations, it is essential to research the load balancing problem in RoF system. As one of the most important optimization functions, load balancing is an effective way to cope with improper traffic load distribution in mobile network [10] , and to improve QoS and GoS performance. Researchers have proposed lots of dynamic equilibrium methods to improve utilities. However, because of the special structure of RoF system, the traditional load balancing methods are not suitable. It is necessary to raise a novel load balancing scheme for ROF system based Ultra Dense Network networks.
Lots works have been down on the load balancing problem in wireless networks [8 - 12] . In [11] , Shiang et al. proposed an active load balancing algorithm to minimize system transmission delays and to obtain a Pareto-efficient solution. They modeled the mobile users as game players to compose a load balancing game. In [12] , a three-stage load-balancing (3SLB) switch was proposed to solve the mis-sequencing problem, without using complex real-time scheduling algorithm. Ref [13] rationally distributed load through the proposed scheme and solved the slow convergence problem. Generally speaking, for some of the previous algorithms, the load migration effect is not obvious, because it can only switch the overlapping coverage region of neighboring calls. Some of the previous algorithms may result in more severe co-channel interference, and the channel locking method is necessary for the previous algorithms. The novelty of our work is in considering a differential game based load balancing scheme, to cope with improper traffic load distribution in mobile network. Differential games or continuous-time infinite dynamic games study a class of decision problems, under which the evolution of the state is described by a differential equation and the players act throughout a time interval. Compared with the existing algorithms, in this paper, a stochastic differential game based load balancing algorithm is introduced to ROF based 5G networks to automatically control traffic load among cells. In our model, as a game player, each cell act as rational, selfish players who compete in the differential game to calculates an optimal load to minimize its cost. Optimal load can be achieved through the algorithms. The key optimization algorithm is based on a differential game model, which was firstly introduced by Dixit [14] , being used for pollution analysis by Yeung [15] . Some works have been down in [9] , which considers a non-cooperative differential game based load balancing algorithm in ROF systems, only considering the energy cost for the game model construction. No changes effects or variations effects of the mobile users are considered in that manuscript.
The whole paper is organized as follows. Section 2 introduces the system model. In section 3, the non-cooperative Nash Equilibrium solution to the model is given and the loading balance algorithm is proposed to solve the overloaded problem in the ROF system, and a load balancing algorithm is introduced based on the solution. In Section 4, The performance of the proposed scheme is simulated and compared. Finally, the concluding remarks are given in Section 5.
2. System Model
In RoF cell (as shown in Fig.1 ), there are K radio access points (RAPs) and one virtual base station (VBS). The distances among the RAPs are larger than the carrier wavelength. Each RAP connects to the VBS through optical fibre. The coverage area of RAP is small, which can be considered as a micro cell. All RAPs are controlled by the VBS, and VBS can be considered as a router of the RoF cell. Based on the network architecture and functions, the structure of the RoF system is flat, one RoF cell can be considered as a local area network.
PPT Slide
Lager Image
System Model
Let K ={1,2,3,…, k } denote the set of radio access points, each RAP is a player of the load balancing game. The load of RAP i at time instant t is li ( t ), where i K . Then the total load of the RoF cell can be calculated as follows,
PPT Slide
Lager Image
The price function defines the instantaneous “price” a RAP pays for having a specific amount of load that causes impacts in the system, which is based on the RAP, is a linear form of the amount of load, and can be defined as follows
PPT Slide
Lager Image
In the practical applications of RoF system, because of the small coverage area of the RAPs, handover frequency is larger than that of the traditional mobile cellular networks. The real load depends on the time that the mobile users stay in the cell. Then we can re-define the instantaneous “price” a RAP pays for having a specific amount of load as
PPT Slide
Lager Image
where πij is positive parameter. πij means the exchange rate of the load between RAP i and RAP j . Generally, we have πij = πji . The price function (3) shows that the actual price of RAP is a form of impact of load variations based on the movement of the mobile users. In the case when πij =0, there is no user moving from RAP i to RAP j . Moreover, the price function generated by this model is computable and fully tractable.
The energy cost of each RAP also depends on the load, which can be defined as follows, which is inspired by reference [16] .
PPT Slide
Lager Image
where βi is a positive congestion cost parameters. Let x ( t )∈ R + denote the mobile users in the RoF system at time instant t , and the dynamic of the users can be generated by the stochastic differential equation as follows,
PPT Slide
Lager Image
where ωi and ε are positive parameters. The dynamic of the users will be changed at a rate ε with the movement of the mobile users. According to the assumption and analysis of the above, each RAP wants to minimize its system load cost to control the load level. Let the minimization of cost to be the objectives, for each RAP i , one can obtain a stochastic differential game at time instant t as follows,
PPT Slide
Lager Image
where λ is the common discount rate, which is applied to find the discount, subtracted from a future value to find the value before the game start. gi ≥ 0 and
PPT Slide
Lager Image
(
PPT Slide
Lager Image
≥ 0) is a threshold. δix ( t ) is the additional cost caused by the load balancing algorithm. Then the load balancing problem in RoF system can be considered as a non-cooperative differential game G G ( K ,{ li }, Ci ) as follows.
1) The players of G are RAPs K≡{1,2,,…, Κ }.
2) The strategy of the player i is li ( t ), which denotes the allocated load, and the game’s strategy profile is L ( t )=( l 1 ( t ), l 2 ( t ),…, lk ( t )).
3) The players’ utilities are the objective of the minimization problem in the equation (6).
4) Generally, the cost of the defined game G are not linear, which is different from the original normal game form.
3. Load Balancing Algorithm
- 3.1 Nash Equilibrium
In this section, the Nash Equilibrium and the load balancing algorithm will be discussed. The dynamic optimization program technique was developed by Bellman [17] , and is given in Theorem 1.
Theorem 1 A set of controls l * ( t )= φ * ( t,x ) constitutes an optimal solution to the control problem (6) if there exist continuously differentiable functions V ( t,x ) defined on [0, T Rm R and satisfying the following Bellman equation,
PPT Slide
Lager Image
PPT Slide
Lager Image
For the optimization problem of the formula (6), the value function Vi ( t,x ) can be represented as follows,
PPT Slide
Lager Image
Then Vi ( t,x ) satisfies the following Bellman equation,
PPT Slide
Lager Image
PPT Slide
Lager Image
Performing the indicated maximization for the optimization problem indicated above, we can obtain the Nash equilibrium for users, that is,
PPT Slide
Lager Image
Proposition 1 The system (9) admits a solution
PPT Slide
Lager Image
with { A 1 ( t ), A 2 ( t ), A 3 ( t ),…, AK ( t )} satisfying the following equations
PPT Slide
Lager Image
PPT Slide
Lager Image
and { B 1 ( t ), B 2 ( t ), B 3 ( t ),…, Bn ( t )} is given by
PPT Slide
Lager Image
PPT Slide
Lager Image
Proof.
Using formula (13), we have
PPT Slide
Lager Image
PPT Slide
Lager Image
Using (18-19), system (6) can be expressed as
PPT Slide
Lager Image
PPT Slide
Lager Image
For (20-21) to hold, it is required that
PPT Slide
Lager Image
PPT Slide
Lager Image
PPT Slide
Lager Image
PPT Slide
Lager Image
Then we have
PPT Slide
Lager Image
Since Bi ( t ) is independent of Bj ( t ) for i j , Bi ( t ) can be solve by (24) and (25) and can be expressed as follows.
PPT Slide
Lager Image
with
PPT Slide
Lager Image
PPT Slide
Lager Image
Generally, we can get
PPT Slide
Lager Image
where
PPT Slide
Lager Image
and
PPT Slide
Lager Image
- 3.2 Load Balancing Algorithm
This section will discuss the load balancing algorithm. We give the whole algorithm based on the Nash Equilibrium in the first section. The progress can be described as following.
Load balancing Mechanism
PPT Slide
Lager Image
Load balancing Mechanism
And the flow chart is given in Fig. 2 as follows.
PPT Slide
Lager Image
Algorithm flow chart
4 Performance Evaluations
In this section, we consider an example to help understand the concepts of proposed load balancing differential game model. We consider a scenario where twenty RAPs need to control their load. The study simulates the proposed scheme based on the Matlab simulation environment. The number results for optimal load allocated to every RAPs will be given. Parameters set for simulations are shown in Table 1 and Table 2 .
Applications in each class
PPT Slide
Lager Image
Applications in each class
Number Values of Parameters
PPT Slide
Lager Image
Number Values of Parameters
In this simulations, the simulations of the median value Ai ( t ) and the expected corresponding feedback Nash equilibrium strategies φ*i ( t ) of the game are considered. As shown in Fig. 3 , the variation of Ai ( t ) will be analyzed, as the key parameter of optimal solution of the differential game. Fig. 3 shows how Ai ( t ) varies with time. It is noted that Ai ( t ) is almost inverse proportion to the time variation. It is decreased as time goes on. Variations of Ai ( t ) will significantly reflect on the variation of φ*i ( t ). Fig. 4 shows the optimal load allocated to each radio access point achieve through the algorithm. It is noted that φ*i ( t ) has the same varying trends as Ai ( t ). It is verified that the optimal load to each RAP can be achieved through the proposed algorithm based on the numerical simulations. Fig. 5 and Fig. 6 show out the vary trends of Ai ( t ) and φ*i ( t ) with discount rate respectively.
PPT Slide
Lager Image
The variation of Ai(t) with time
PPT Slide
Lager Image
The variation of φ*i(t) with time
PPT Slide
Lager Image
The variation of Ai(t) with discount rate
PPT Slide
Lager Image
The variation of φ*i(t) with discount rate
5 Conclusions
In this paper, a non-cooperative differential game based load balancing approach is proposed in Ultra Dense Network, based on the radio over fiber technology, to achieve autonomous and coordinate management of network resources. It has been proved that the differential game theory can be used to achieve load balancing. It is proved that the optimal allocated load to each RAPs can be achieved through the proposed scheme.
BIO
Xu Haitao, received his B.S. degree in Communication Engineering from Sun Yat-Sen University, in 2007, and his M.S. degree from University of Bristol in 2009. He obtained the PHD degree in Department of Communication Engineering, from University of Science and Technology Beijing. Now he is a lecturer in University of Science and Technology Beijing. His research interests include big data, cognitive radio networks, self-organized networks, mathematical model, game theory and next-generation networks. Coressponding Email: alex_xuht@hotmail.com
He Zhen, received his master’s degree from the School of computer and Communication engineering at Zhengzhou University of Light Industry in 2011. Now he is pursuing the PhD degree in the Department of Communication Engineering, School of computer and Communication engineering at the University of Science and Technology Beijing( USTB). His research interests lie in wireless network and optical fiber communication.
Zhou Xianwei, as a professor in Department of Communication Engineering, School of Computer & communication Engineering, University of Science and Technology Beijing, His research interests include the security of communication networks, next-generation networks, mobile IPv6, scheduling theory and game theory.
References
Imran A. , Zoha A. , Abu-Dayya A. 2014 "Challenges in 5G: how to empower SON with big data for enabling 5G," Network, IEEE 28 (6) 27 - 33    DOI : 10.1109/MNET.2014.6963801
Jo Minho , Maksymyuk T. , Batista R.L. , Maciel T.F. , de Almeida A.L.F. , Klymash M. 2014 "A survey of converging solutions for heterogeneous mobile networks," Wireless Communications, IEEE 21 (6)    DOI : 10.1109/MWC.2014.7000972
Chin Woon Hau , Zhong Fan , Haines R. 2014 "Emerging technologies and research challenges for 5G wireless networks," Wireless Communications, IEEE 21 (2) 106 - 112    DOI : 10.1109/MWC.2014.6812298
Bhushan N. , Junyi Li , Malladi D. , Gilmore R. , Brenner D. , Damnjanovic A. , Sukhavasi R. , Patel C. , Geirhofer S. 2014 "Network densification: the dominant theme for wireless evolution into 5G," Communications Magazine, IEEE 52 (2) 82 - 89    DOI : 10.1109/MCOM.2014.6736747
Gelabert X. , Legg P. , Qvarfordt C. "Small Cell densification requirements in high capacity future cellular networks," in Proc. of Communications Workshops (ICC), 2013 IEEE International Conference on 2013
Gotsis A.G. , Stefanatos S. , Alexiou A. "Spatial coordination strategies in future ultra-dense wireless networks," Wireless Communications Systems (ISWCS), 2014 11th International Symposium on 2014
Dennis Hui , Axnas Johan "Joint routing and resource allocation for wireless self-backhaul in an indoor ultra-dense network," Personal Indoor and Mobile Radio Communications (PIMRC), 2013 IEEE 24th International Symposium on 2013 3083 - 3088
Cooper A.J. 1990 "'Fibre/radio' for the provision of cordless/mobile telephony services in the access network," Electronics Letters 26 (24) 2054 - 2056    DOI : 10.1049/el:19901325
Zhen He , Wang Jianping 2014 "Non-cooperative differential game based Load Balancing Algorithm in Radio-over-Fibre system," Communications, China 11 (14)    DOI : 10.1109/CC.2014.7085387
Balachandran A , Bahl P , Voelker G M 2002 "Hot-spot congestion relief and service guarantees in public-area wireless networks," ACM SIGCOMM Computer Communication Review 32 (1) 59 - 59    DOI : 10.1145/510726.510733
Shiang Hsien-Po , van der Schaar M. 2013 "Conjecture-based load balancing for delay-sensitive users without message exchanges," Vehicular Technology, IEEE Transactions on 62 (8) 3983 - 3995    DOI : 10.1109/TVT.2013.2260188
Cai Yan , Wang Xiaolin , Gong Weibo , Towsley D. 2014 "A study on the performance of a three-stage load-balancing switch, " Networking, IEEE/ACM Transactions on 22 (1) 52 - 65    DOI : 10.1109/TNET.2013.2244906
Sheng Min , Yang Chungang , Zhang Yan , Li Jiandong 2014 "Zone-based load balancing in LTE self-optimizing networks: a game-theoretic approach," Vehicular Technology, IEEE Transactions on 63 (6) 2916 - 2925    DOI : 10.1109/TVT.2013.2293785
Dixit A 1979 "A model of duopoly suggesting a theory of entry barriers," General Information 20 - 32
Yeung D W K 2007 "Dynamically consistent cooperative solution in a differential game of transboundary industrial pollution," Journal of optimization theory and applications 134 (1) 143 - 160    DOI : 10.1007/s10957-007-9240-y
Cheng Z , Zhou X , Ding Y 2013 "A transmission rate control algorithm based on non-cooperative differential game model in deep space networks," Wireless Personal Communications 71 (3) 1915 - 1929    DOI : 10.1007/s11277-012-0915-9
Yeung D.W.K. , Petrosyan L.A. 2006 "Cooperative stochastic differential games,"Springer Series in Operations Research and Financial Engineering Springer Press