Joint User Association and Fair Scheduling for Dual Connectivity Heterogeneous Networks

Haixia Cui ,Yongliang Du

1 School of Electronics and Information Engineering,South China Normal University,Foshan 528225,China

2 School of Physics and Telecommunication Engineering,South China Normal University,Guangzhou 510006,China

Abstract: Heterogeneous small cell network is one of the most effective solutions to overcome spectrum scarcity for the next generation of mobile networks.Dual connectivity (DC) can improve the throughput for each individual user by allowing concurrent access to two heterogeneous radio networks.In this paper,we propose a joint user association and fair scheduling algorithm(JUAFS)to deal with the resource allocation and load balancing issues for DC heterogeneous small cell networks.Considering different coverage sizes,numbers of users,and quality of experience characteristics of heterogeneous cells,we present a proportional fair scheduling for user association among cells and utilize interference graph to minimize the transmission conflict probability.Simulation results show the performance improvement of the proposed algorithm in spectrum efficiency and fairness comparing to the existing schemes.

Keywords: fair scheduling;heterogeneous networks;dual connectivity;interference management

I.INTRODUCTION

With the rapid development of Internet of Things(IoT),user terminals,driverless vehicles,and future wireless traffics are expected to grow faster and faster[1].For example,the traffic demand for future IoT will be extremely high due to the use of Augmented Reality(AR)and Virtual Reality(VR)[2].To meet the raising requirements of applications,many efforts have been done and ultra dense heterogeneous small cell network is one of the most potential technologies among them [3,4].With dual connectivity (DC) networks which is proposed in 3GPP release 12 for LTE and release 16 for LTE-New Radio(LTE-NR),each user can access two different heterogeneous cells simultaneously[5].For congested areas or ultra sense environments,DC can improve the quality of experience for users significantly.Furthermore,compared with the traditional single connectivity network architectures,such as LTE,DC networks are multi-frequency-multistructure in which two heterogeneous cells could share the same radio spectrum.If the wireless resources are not properly scheduled,it may incur inter-cell interference and thus degrade system performance accordingly.Therefore,the user association and interference management issues are key for mining potential of DC heterogeneous networks.

At present,many solutions have been proposed for traffic balancing and scheduling in DC heterogeneous networks [6-8].In LTE-NR DC networks [6],the users with dual access points could communicate with LTE and NR base stations at the same time to improve the throughput and balance the load traffic.However,the involved network structure needs an efficient scheduling mechanism to control the inter-cell interference.In [7],a downlink traffic scheduling algorithm was presented to split data into MeNBs and SeNBs for LTE DC networks.To further enhance system performance and control interference among cells carefully in LTE-NR DC networks,the base station assignment problem has been investigated in[8].For green communication in DC heterogeneous networks,a joint optimization algorithm for bandwidth and power allocation has been proposed in [9].In addition,user association mechanisms to enable relatively less energy consumption for ultra dense heterogenous networks have been incorporated into the current communication system[10,11].

For the state-of-the-art on the multi-connectivity networks we refer the readers to [12-18].In particular,the scheduling schemes proposed in [12] for split responsibility could overcome several task association issues.Distributed resource allocation for multi-access scenarios was achieved by maximizing the minimal user throughput subject to the constraint that user throughput must be higher than a requirement in [13].In [14],the joint user association and spectrum allocation issue was studied for heterogeneous networks in both downlink and uplink.By solving the network utility maximization problem,the optimal user association and spectrum partition are obtained.To alleviate the energy consumption of users and create a more satisfactory user experience for multiconnectivity networks,energy efficient resource allocation and user association have been actively studied in[15,16].In[17],a proportional fairness strategy in user association has been proposed to improve the fairness performance of multi-connectivity networks and the user association scheme in [18] has increased the overall network utility accordingly.Proportional fair seeks to balance throughput maximization with fairness between different heterogeneous base stations,also called as fair utility,which is a scheduling technique to maintain fairness for users [19].However,most of the above existing works in DC heterogenous networks have not taken the fairness and inter-cell interference into account comprehensively.

Based on fast fluctuation of wireless channels effecting communication performance significantly,a good resource scheduling scheme in DC heterogeneous networks should consider both fairness and interference management,i.e.,how to schedule heterogeneous radio access technologies to satisfy requirements of users with proportional fairness and how to allocate wireless resource between heterogeneous radio access technologies to mitigate interference? This paper focuses on optimizing communication in DC heterogeneous networks by answering the above two questions.Specifically,we propose a joint user association and fair scheduling (JUAFS) algorithm to deal with presented issues and improve system performance.Considering coverage sizes,numbers of users,and quality of experience of heterogeneous cells,we incorporate proportional fair scheduling into user association and utilize interference graph to minimize the transmission conflict probability.

The rest of the paper is organized as follows.Section II presents the system model including the interference graph and the reverse engineering analysis about proportional fair scheduling theory.In Section III,the proportional fair scheduling with inter-cell interference management in DC heterogeneous networks is formulated as an optimization framework.Section IV develops the proposed JUAFS algorithm.We also discuss the stability of the obtained optimization problem.Simulation results are presented in Section V.Finally,we conclude the paper in Section VI.

II.SYSTEM MODEL

In this section,the inter-cell interference model and the proportional fair scheduling framework will be detailed.

2.1 Interference Graph Model

Taking a two-tier DC heterogeneous network with macrocell and picocells as an example,as shown in Figure 1,the terminal users are covered by a macrocell.At the same time,most of them also can be served by a picocell in the heterogeneous macro-pico DC network.Usually,the users located at the cell borders suffer more inter-cell interference and we consider downlink interference among the heterogeneous cells here.Consider that graph theory is a popular tool to resolve the interference issues in distributed wireless networks[20],the inter-cell interference graph can be mapped out in which the vertexes denote the heterogeneous cell base stations or distributed access points and the edges denote interference relationships between corresponding two vertexes,as shown in Figure 2.Unlike the regular centralized scheduling schemes,all the heterogeneous cell base stations or distributed access points in our system model will establish clusters to mitigate the inter-cell interference.The cluster is used for base station scheduling access with small collision probability and the same coordination scheduling policy is executed in each cluster.From [21],the maximal chromatic number in a planar graph is less than or equal to 4.Here,we set the maximum size of the cluster as three base stations and it can be set other values based on the network conditions.For example,in Figure 2,users 4,5,and 7 form a cluster and execute the same scheduling algorithm that will be detailed in the following sections.However,cluster{1,4,5}and cluster{4,5,7}cannot execute the scheduling policy simultaneously because they share base stations{4,5}and cannot run two different scheduling policies.

Figure 1. Illustration of a macro-pico DC heterogeneous network.

Figure 2. Inter-cell interference graph and maximum cluster.

Figure 3. Conflict graph of cluster.

To resolve the above clustering problem,we redraw another conflict graph,as shown in Figure 3,in which the vertexes{A,B,...,H}represent the clusters in Figure 2.For example,vertex A donates the cluster{1,4,5},vertex B denotes the cluster{1,2,5},and so on.Moreover,A and B are connected with one edge since they have the same vertexes{1,5}.If vertexes are not connected with each other,they can execute the corresponding scheduling approach at the same time.We should bring out all interference graphs and conflict graphs before the available user association and scheduling policy will be proposed.

Figure 4. Utility function of cumulative average rate,pi=0.5,ri=6Mbps.

Figure 5. Resource block allocation.

2.2 Reverse Engineering Analysis of Proportional Fair Scheduling in Single Connectivity Networks

The proportional fairness scheduling in [8] not only ensures fairness among users but also takes channel conditions into consideration for LTE system.For communication requirements,only users with the highest priority parameters can be scheduled for services.The corresponding priority parameter of useriin time slotkcan be calculated as

whereri(k)is the traffic rate requirement of useriin time slotkand(k -1) is the cumulative average transmission rate of useriin time slotk-1.(k-1)can be calculated by

wheretcis a time slot.If the communication of useriis successful,the corresponding cumulative average transmission rate will increase since it will have a smaller advantage in the next round of scheduling competition.On the other hand,the greater rate requirement means bigger numerator which reflects the channel condition.This scheduling scheme can well balance transmission of different users in heterogeneous single connectivity wireless networks[22].

For a reverse engineering analysis of the above proportional fairness scheduling,we take 1/tc=αand the above equation can be rewritten as

Taking the scheduled ratio of useri,pi(0≤pi ≤1),into consideration,the expectation of the cumulative average transmission rate can be unfolded as

whereri=ri(k)denotes that the rate requirement of useriis stable in the transmission process.According to the Taylor Expansion Expression 1/(1-x)=for anyx,the expectation of the cumulative average transmission rate can be obtained as

In fact,with the increase of transmission time,i(k) will converge to a limit value which can be found in the above analysis.It also can be shown by a utility functionU()ofas follows,

Furthermore,the convergence ofaccording to the utility functionU()can be expressed as

Figure 4 shows the relationship between utility functionU()and.The cumulative average rate,,has a optimal value with suitable parameter setting.Therefore,by the reverse engineering analysis,the key of proportional fair scheduling is adjusting the cumulative average transmission rate of different users to maintain inter-cell load balancing.According to Eq.(1),Eq.(4),and Eq.(5),the expectation of the priority parameter can be expressed as

whereri(k) is independent withRi(k -1) and it is only related to the network service requirements.

III.INTER-CELL INTERFERENCE CONTROL IN DC HETEROGENEOUS NETWORKS

In macro-pico DC heterogeneous networks,the above proportional fair scheduling scheme should be redesigned with double service line modules.Here,the wireless spectrum is divided into small time and frequency blocks,called resource blocks,as shown in Figure 5.Users are supplied with resource blocks according to their priority parameters and the corresponding cumulative average transmission rate of useriin this DC heterogeneous network can be rewritten as

Figure 6. Priority iteration of pico cells.

Figure 7. The cumulative average rate of networks.

Figure 8. Priority iteration of macro cells.

whererm,i(k) is the traffic transmission rate requirement of useriwith resource blockmin time slottand Sirepresents the available resource block set for useri.

3.1 Interference Framework

Generally,the inter-cell interference is serious in DC heterogeneous networks due to the short distances among heterogeneous base stations.For useri,the received signal-to-interference-and-noise-ratio (SINR)with resource blockmcan be expressed as

wherePeandPjdenote the transmission powers from base stationseandjto useri,respectively.anddonate the channel coefficients from base stationseandjto useriwith resource blockm,respectively.xjis an binary variable which equals to 1 when there is inter-cell interference fromjtoiand 0,otherwise.σrepresents the additive Gaussian white noise.

From the above,different combinations of base stations and users will generate different interference environments.DenoteUas pico base station set andVas macro base station set.Usersujandvjare in the coverage of pico base stationuand macro base stationv,whereu ∈U,v ∈V,respectively.Thus,there arepossible transmission rates with the service of picocells and macrocells,where|X|is the component number of any setX,respectively.In other words,there areu′+v′transmission states and all states are associated to different base stations and users.By carefully choosing when and which service should be activated,the intercell interference can be mitigated obviously.Based on the above proportional fair scheduling ratio of useri,its statistical transmission rate can be expressed as

3.2 Fair Scheduling for DC Heterogeneous Networks

Based on the analysis of reverse engineering for proportional fair scheduling in single connectivity networks and the inter-cell interference framework [23],we rewrite the optimization problem for wireless resource scheduling in DC heterogeneous networks as follows.

where the log function is only used for obtaining the optimal solution easily and has no practical significance.nis the number of users.

To obtain the optimal resource scheduling solution for the above optimization problem,we first relax it with the Lagrangian dual function.By relaxing the scheduling conditions and taking p andλas the optimization variable parameters,we can obtain the solution to the above optimization problem according to Lagrangian function by

and Gradient Descent,we can obtain the optimal solution for the scheduling optimization expression Eq.(12)according to Lagrangian multiplier.

However,the wireless channels and mobile communication environments are dynamically varying.We should update the priority scheduling parameters of each service line periodically as follows.

Figure 6,7,8 show how the fairness can be guaranteed.The scheduling method for the random connections is based on the priority scheduling parameters in Eq.(18).There is only one channel available.In one picocell,connections 1 and 2 compete with each other and only the connection with the highest priority can communicate with the picocell base station.In addition,connections 1 and 2 can also be serviced by macrocells while connection 3 is not in the coverage of any picocell andis belong to connection 3.According to the expressions in Eq.(18),all the scheduling priorities are convergent,as shown in Figure 7.In Figure 8,without DC service chance,the sum of the cumulative average rate of connection 3 is lower than others significantly.Therefore,the priority of connection 3 in macrocells is much bigger than others in any iteration,which means macrocell base station will not communicate with connections 1 and 2 in order to offer more ratio resource for connection 3 to maintain the performance fairness.

However,the inter-cell interference is not considered in Eq.(18)although the fairness performance is guaranteed.To solve this problem,all theu′+v′possible transmission states should be utilized to reduce the inter-cell interference according to Eq.(12).Therefore,similar with the priority setting in Eq.(18),we can improve the system performance by combining all theu′+v′possible transmission states and offering an updating model for the priority scheduling parameters as

where(k-1) is the cumulative average transmission rate with DC.Different from the traditional proportional fair scheduling scheme,our aim is to schedule radio resource with proportional fair for different states rather than connections.That is to say,the priority scheduling scheme is transmission state scheduling.From Eq.(19),only the states with the highest priority parameters in DC heterogeneous networks will be scheduled with services.

Therefore,the connections that can be scheduled in each time slot need be selected from theu′+v′possible transmission states.There areu′+v′priorities and the computational complexity is extremely high,especially in ultra-dense heterogeneous networks.The calculation complexity grows exponentially with the network scale increasing.It is a NPhard problem,withtime complexity and space complexity,whereujandvj′are the user numbers in the picocelluand macrocellv,respectively.In the following discussion,we will find a low-complexity method for the proposed scheduling algorithm.

IV.JOINT USER ASSOCIATION AND FAIR SCHEDULING ALGORITHM(JUAFS)

This section will present the details of JUAFS in DC heterogeneous networks.First,the maximal clusters for inter-cell interference graph and conflict graph should be given.

4.1 Cluster Searching

Due to the random topology of terminal users,the maximal cluster searching is time-consuming and an NP-hard problem[20].In this paper,we will simplify the searching process through geometric construction and the obtained clusters can approximate the maximal clusters in the corresponding graphs.In this case,our inter-cell interference graph can be served as a planar map to reduce the complexity of searching process since there are only adjacent cell interferences in practical applications.Furthermore,the special shape of cellular networks makes it easier to find the maximal clusters.For example,the size of maximal cluster is 3 and a network hole is equal to a maximal cluster in cellular network frameworks [20,21].Based on the above,we can find all the clusters through the following process.

First,we acquire the locations of all heterogeneous cell base stations and constitute a graphG(ˆV,ˆE),where vertexesare base stations and edgesare interference relations between vertexes.The vertexes are selected one by one as the origin to construct the rectangular plane coordinate system.At the same time,the vertexes that connect with the corresponding vertexxare added into=1,...,n′,wheren′=|U|+|V|is the number of heterogeneous network base stations.The anticlockwise angle from the horizontal axis to edge that connects with the origin and the other vertex are added into=1,...,n′.Thus,vector sets Concan be obtained.Through classification of the vector set Con based on Ang,all maximum clusters of the interference graph can be acquired,as shown in Algorithm 1.

Then,we try to find the maximal clusters for the conflict graph.Taking clusters inCli(C1,C2,...) as vertexes and connecting them with same sharing elements,we can get the conflict graphBy obtaining the maximal independence set ofor the maximal cluster inwhich is a complement graph ofwe can schedule the base stations in proper order.However,the obtained conflict graph is not planer.So,the maximal conflict cluster searching inis time-consuming particularly,especially in ultra-dense network environments.Considering that the graphand its maximal clusters need be used to carry out our proposed proportional fair scheduling algorithm,we put forward to an approximate algorithm to simplify the above complicated search process.

Specifically,the total computational complexity of the proposed Algorithm 1 and 2 are allO(nK2),whereKis the number of nodes in adjacent clique,which is equivalent to the DC assignment strategy in[8].

4.2 JUAFS with Obtained Clusters

For JUAFS,two important issues should be answered first.1)Which cluster ofshould be scheduled in each time slot?2)Which transmission state for the running cluster ofshould be scheduled in each time slot?

Denotezas the sequence number of one maximal cluster.The effective transmission rate of useriwith clusterzwill be written as

wheredenote the achieved transmission rate of useriwith transmission stateland resource blockmin clusterzand the corresponding scheduling ratio,respectively.The statistical transmission rate of userican calculated as

Thus far,based on the proportional fair principle,the optimization problem of system utility can be formulated as

whereu(i)is the set of users in the coverage of picocelluthat services for useri.

The above system utility expression is a composite function related to our obtained maximal cliques and their transmission states.Similar with Eq.(13),Eq.(14),Eq.(15),Eq.(16),and Eq.(17),we can bring out the solution with the priority of maximum cliques for conflict clusters easily by

wherecan be updated when maximum clusterzin conflict graph is scheduled.

Considering the second question in this part,the system utility optimization problem can be rewritten as

wherez(l) andz(l′) denote the clusters including transmission stateslandl′,respectively.

V.PERFORMANCE EVALUATION

In this section,we evaluate the performance of the proposed JUAFS scheme via computer simulation.We will compare the spectrum efficiency and user fairness with other different scheduling schemes.

5.1 Simulation Setup

We consider a random topology with a square area of 200m×200m in the coverage of one macro base station,as shown in Figure 1,and each picocell is a circular area with radius of 50m,which is in the coverage of macro cell.We use cost-231 Walfish-Ikegami mode in [24-26] as our channel fading model.The macrocell and picocell signal loss models areLm(dB)=194.64+26log(d)andLp(dB)=189.65+20log(d),wheredis transmission distance,respectively.Other parameters are shown in Table 1.

Table 1. Simulation parameters.

5.2 Simulation Results and Discussions

Figure 9 demonstrates the total throughput versus the number of picocell base stations in DC heterogeneous networks.It is observed that the throughput increases with base station number raising and the performance of our algorithm is better than the LTE DC assignment algorithm without considering the fair scheduling problem.Although the LTE DC heterogeneous access algorithm involved interference control between cells,the user association could not achieve a fair scheduling condition to the heterogeneous base stations.Therefore,the proposed JUAFS outperforms it in total throughput,especially when the number of pico cells is large.In addition,we also observe that in less pico cell case,the advantages our proposedalgorithm are not obvious or even worse.Such performance degradation results from the sparse heterogeneous environments because the fewer small cell base stations,the less obvious the advantages of fair scheduling between heterogeneous cells.Even,due to the strong coverage ability of macro cell and less cell interference,the total throughput performance without considering the fair scheduling shows better results.From Figure 10,the average cell transmission rates gradually decline under a fixed ratio between users and base stations with network density increasing.This is because that the inter-cell interference among different cells is increasing.Fortunately,the descent rate of proposed algorithm is slower than those without considering inter-cell interference.

Figure 9. Total throughput comparison with different association scheduling strategies.

To better understand the fairness gains,in Figure 11,we setlog(Ri) as the fair index of user association and scheduling algorithm in DC heterogeneous networks,whereRiis the average rate of useri.It can been see that the fair index of JUAFS is much higher than the others and it closes to the one of optimization algorithm in Section III infinitely.This is because of the proportional fair scheduling strategy.Furthermore,when the experiment number is large enough,log(Ri)changes weakly with the base station density.So,the obtained fair index curve looks like a straight line.On the other hand,the cumulative distribution functions of fair index for different association scheduling strategies are also extremely approximated 1 and our proposed algorithm is greater than the others,as shown in Figure 12.

Figure 10. Average cell throughput comparison with different association scheduling strategies.

Figure 11. System fairness index.

Figure 12. CDFs of fairness index with different association scheduling strategies.

Figure 13. Average user throughput with different association scheduling strategies.

Figure 13 shows an example for different association scheduling algorithms.In this case,users 2,3,4 are assumed outside the coverage of picocell base stations.The other users can be served by both pico and macro cell base stations simultaneously.From Figure 13,the data rate difference among users in traditional DC networks is higher than our proposed algorithm.The rate gap of user 7 and user 1,which have the greatest and slowest rate served by picocells,respectively,is bigger than the one in LTE DC algorithm.Besides,users 3 which only can be serviced by macrocell networks also has a slower data rate.

VI.CONCLUSION

In this paper,we have proposed a joint user association and fair scheduling algorithm based on interference and conflict graph for DC heterogeneous networks.By scheduling the radio resources at base stations suitably,the system performance has been improved significantly.Furthermore,to reduce the complexity of proposed algorithm,we have reconstructed JUAFS by decomposing the heterogeneous networks into several cell clusters.Simulation results show the effectiveness of the proposed algorithm.

ACKNOWLEDGEMENT

This work was supported in part by the National Natural Science Foundation of China under Grant 61871433,61828103 and in part by the Research Platform of South China Normal University and Foshan.