Clustering-based resource allocation algorithm in ultra dense network

TAN Bowen, ZHANG Zhenfeng, WEI Huan, FAN Bin

(School of Communication and Information Engineering, Chongqing University of Posts and Telecommunications,Chongqing 400065, P.R. China)

Abstract: In ultra-dense network(UDN), the serious inter-cell interference has restricted the data rate of users. In view of this problem, a new coloring-based clustering resource allocation scheme is proposed in this paper. The scheme is divided into three steps: the first step uses graph-based coloring algorithm for femtocell access points (FAPs). The second step uses the amount of data to be transmitted, the queuing delay and the interference intensity of each femtocell user equipment (FUEs) in the cluster to build the corresponding priority, and then calculate the priority of each cluster. Such clusters owning high priority can received sub-channel of good channel gain first. The third step allocates power for FUEs by Karush-Kuhn-Tucker(KKT) and water-filling algorithm. Simulation results show that the proposed scheme can effectively reduce the interference among femtocells and also greatly satisfy the needs of users, while improving the throughput and spectrum efficiency. In addition, the power of each sub-channel is dynamically adjusted based on the fairness criterion of maximum power and minimum rate which further improves the fairness degree among FUEs.

Keywords：ultra-dense network(UDN); femtocell; clustering; resource allocation

1 Introduction

To support the 1000-fold throughout increase in the fifth-generation(5G) mobile communication system, network densification has become a dominant trend. In order to improve system capacity and realize seamless coverage, UDN(ultra-dense network) is considered as one of the key techniques of 5G to achieve this goal, which deploy a large number of low-power nodes such as femtocells[1]. The system performance has become a challenge due to kinds of serious interference[2], such as co-tier interference between macrocell base station(MBS), cross-tier interference between MBS and femtocells and co-tier interference between femtocells, in which the interference between femtocells is particularly serious. Therefore, effective inter-cell interference management scheme and resource allocation scheme are extremely beneficial to the academia and business community to enhance the overall system performance and meet the needs of users[3].

At present, domestic and foreign scholars have conducted a great deal of researches and explorations on the above issues. For the purpose of managing resource allocation in UDN, [4] proposes a multi-dimensional resource allocation algorithm based on non-cooperative game theory. The algorithm is divided into two parts: transmission node joint, channel and power allocation. The feasible region and the discrete variable relaxation method in the algorithm can optimize the multi-dimensional resource allocation problem with much lower complexity. In [5], the authors use game theory to propose a clustering algorithm based on load information and design a resource scheduling scheme(TS-JCS) based on proposed clustering algorithm in small cells. The work in [6] maximizes the total weight sum rate of all users considering the feedback resource constraints. Firstly, L1-norm optimization method was implemented to convert non-concave feedback constraints to a model that could be solved. Then, recalculate the second order objective function according to the continuous parameter optimization method and finally form an iterative algorithm aiming at optimal solution.

However, none of these studies considered the interference in system. A complete graph-based clustering resource allocation scheme divides all base stations into independent clusters[7]. The cluster allocates mutually orthogonal frequency resources to eliminate interference. In [8], a worst-case subcarrier avoiding (WSA) algorithm is proposed to prevent user equipment from allocating subcarriers with poor channel gain and improve system capacity at the same time. Taking into account the difference between the actual application scenarios and theory scenarios, two new resource allocation algorithms are proposed in [9], which are autonomous allocation and coordinated allocation respectively. The result shows that the proposed algorithm is more efficient in network throughput compare to existing resource allocation algorithms. In [10], a new graph-coloring based dynamic frequency reuse(GB-DFR) is introduced. It can equilibrium the inter-cell interference and spectrum resource reuse , which is more suitable for deploying randomly in wireless network system. A graph-based frequency allocation (UGFA) algorithm in [11] is proposed in UDN. The purpose of the algorithm is to increase the frequency reuse ratio and enhance the network throughput. In [12]，a coloring-based cluster resource allocation (CCRA) is proposed which can improve spectrum efficiency and coordinate inter-cell interference in UDN. The algorithm ensures that the interference of the users in the cluster is within the acceptable range, then allocates resource to users according to different interference environments. Nonetheless, the graph-based coloring algorithm is not given specifically.

In this paper, we propose an improved coloring-based cluster resource allocation(ICCRA) considering the interference between femtocells in UDN. The scheme has three stages: clustering stage, sub-channel allocation stage and power allocation stage. In clustering stage, we use a graph-based coloring algorithm to cluster FAPs in the constructed interference topology. Hence the FAPs with the same color are divided into the same cluster and they reuse the same frequency spectrum resources. In this way, the interference influence for system is almost mitigated. Then in sub-channel allocation stage, we calculate the cluster priority of each femtocell user equipment(FUE) which relying on the amount of data to be sent, the queuing delay and the interference intensity and then allocate sub-channel with good gain to users who have high priority. While in power allocation stage, in order to maximize system throughput, we allocate power subject to the constraints of maximum power and lowest sum rate.

2 System model

Here, an ultra dense small cell cellular network is considered. Assuming that the system consists of one MBS andXFAPs. For the sake of simplicity, each FAP accesses one closest FUE as shown in Fig. 1. LetFbe the set of FAPs,Ube the set of FUEs. Of which FAPs and FUEs are randomly distributed within the macro cell coverage, we assume that all FAPs use a closed-loop access mode.

Fig.1 System model

The signal to interference plus noise ratio(SINR) of FUEiserved by FAPjon channelkcan be written as

(1)

(2)

Therefore, assuming that the total bandwidth of system isB, Δf=B/K, whereKis the number of sub-channels. The transmission rate of FUEion sub-channelkcan be expressed as

(3)

The total rate of system is

(4)

3 Clustering for FAPs

3.1 Interference graph construction

The interference graphG=(V,E) consists ofVvertices corresponding to the femtocells in the macro-cell range andEedges that show the interference conditions between different femtocells. We defineV={1,2,…,v} be the set of vertices, consequently their serial number can be written as ID={1,2,…,v}. Assuming that there is inter-cell interference in the overlapping regions of the system model in Fig.1, hence the simplified interference topology is now shown in Fig.2.

Fig.2 Simplified interference graph

3.2 Coloring-based clustering algorithm

Specific algorithm flow is as follows. As shown in Fig.3, we perform clustering after coloring. Vertices with the same color belong to the same cluster. The example of clustering results is {1,6,8},{2,4,7},{3,5}.

Algorithm1Coloring-based clustering algorithm

Step1Initializing: Calculate the degree of each vertex which is expressed asD(number of edges associated with vertices) and sortDin a descending order which is stored inList_D. Then create a list of used color asList_C.

Step2Find the vertex corresponding to the maximum value inList_D. If there are multiple maximum value simultaneously, select the vertex with the smallest ID firstly. Choose a color from the palette for the vertex, and then delete the value corresponding to the vertex which is inList_D.

Step3Find the vertex corresponding to the maximum value inList_D, compare it with the neighbor vertices, and select a different color from the palette to color it.

Step4Repeat Step 3 until all the vertices have been colored. As a result, the vertices have the same color are divided into the same cluster.

Fig.3 An example of clustering results

4 Resource allocation for FAPs

4.1 Sub-channel allocation

The purpose of sub-channel allocation is to allocate orthogonal sub-channels to different clusters, and then FAPs in the same cluster can use the same sub-channel. This paper proposes a sub-channel allocation algorithm based on priority of cluster. Assuming each FAP has a buffer queue namedArraydatawhich stores the data to be transmitted by each FUE. Taking into account the user’s fairness and without loss of generality, the factors that influence the priority of receiving resources are defined as: ①the amount of data to be transmitted by FUEs, ②the queuing delay of FUEs, ③the interference intensity of FUEs which is affected by other FAPs. In general, the more data to be transmitted is, the large the waiting delay of FUEs is, or the larger the interference intensity is, the higher priority FUEs will have.

(5)

2)Assuming FUEiinitiates a resource request at momentTi_reqand receives the wireless resource at momentTi_rec, therefore the queuing delayTiof FUEiis

Ti=Ti_rec-Ti_req

(6)

3)We can know from system model, the transmit power of FAPjispjand the channel gain between FAPjand FUEiisgj,i, then the suffered interferenceIiof FUEiwhich is disturbed by FAPjcan be expressed as

Ii=pjgj,i

(7)

Assuming thati,i′∈U, the priority of receiving resource by FUEican be defined as

(8)

(9)

(10)

Algorithm2

A sub-channel allocation algorithm based on priority of cluster

Step1CalculateDi,Ti,Ii,PRFUE(i) of each FUE andKaof each cluster.

Step2CalculatePRclu(i) of each cluster, and sortPRclu(i) in a descending order which is stored inList_PR.

Step3According to the gain of all FUEs on different sub-channels in each cluster, the average gain of cluster on each sub-channel is calculated. Follow the principle of sorting the average gain in a descending order, rewrite the gain matrix in an other form called number matrix consists of sub-channel serial number. The matrixHseqhasCrows andKcolumns.

Step4Firstly assign the sub-channel with the best gain to the cluster with the highest priority which is stored inList_PR. Let us begin at the first row ofHseq, selectNasub-channels from left to right. Then selectNasub-channels for the next cluster at next row, the selected sub-channels should be removed in process. Repeat until each cluster is assigned enough orthogonal sub-channels.

4.2 Power allocation

After deriving the result of the sub-channel allocation, the resource allocation can be translated into power allocation of FUEs. Therefore the objective function can be described as

(11a)

Subject to：

(11b)

(11c)

(11d)

(12)

(13)

Where [x]+means taking the maximum value inxand 0.

5 Simulation results

In this section, we conduct simulations to verify the effectiveness of the proposed scheme in mitigating interference and optimizing spectrum efficiency of UDN. This paper adopts the urban deployment scenario in the 3GPP standards[14], there is one MBS andXFAPs in this simulation scenario for the sake of brevity. Specific simulation parameters set as shown in Tab.1.

Tab.1 Simulation parameters

This paper analyze the performance of system by using the proposed algorithm compare to three kinds of resource allocation schemes, CCRA, UGFA and GB-DFR respectively. The CCRA algorithm takes the inter-cell interference intensity as the priority and the cell with higher priority will obtain the resource block first. The UGFA algorithm regards users as the center and allocates spectrum resources in each cluster in the ultra-dense deployed femtocell network. The GB-DFR algorithm allocates resource blocks to the users according to the sequential coloring algorithm.

The cumulative probability density function (CDF) of average FUE throughput is shown in Fig.4. In the UGFA and CCRA algorithms, the vertices in the interference graph represent users. It is possible to cause the same spectrum reuse among the cells, users in the system will suffer interference more serious as a result. Hence the average user throughput is not good, while the interference intensity is taken as a priority in the CCRA algorithm. The average user throughput of CCRA is effectively increased. The GB-DFR algorithm prioritizes the throughput of users in cell edge, but has an impact on the average user throughput. The proposed ICCRA algorithm uses the cluster priority as a criterion, and allocates sub-channels with good channel gain to the clusters with higher priority. The total transmission rate of the FUEs is the objective function, the optimized power allocation of users guarantees the requirements and also the average user throughput at the same time.

Fig.4 Average FUE throughput

Fig.5 shows the CDF of the average FUE spectral efficiency. Neighboring base stations without interference in the GB-DFR algorithm also use orthogonal frequency, which causes a large amount of waste of frequency spectrum resources. The UFGA algorithm allocates the same number of resources for each cluster. Therefore, the average spectral utilization rate of GB-DFR and UFGA is the lowest. Compared with the CCRA algorithm, the proposed ICCRA algorithm allocates resources according to the amount of resource demands in the cluster. Thereby saving spectrum resources and improving the average user spectrum efficiency.

The fairness degree index[15]among FUEs is shown in Fig.6. As the density of femtocells increases, the fairness degree of ICCRA algorithm is significantly higher than other algorithms. Since the ICCRA algorithm takes the amount of data to be transmitted, the queuing delay and the interference intensity of each femtocell User Equipment (FUEs) in the cluster into account. Then the ICCRA algorithm allocates sub-channels and power in clusters based on the fairness criterion of maximum power and minimum sum rate. The power of sub-channels is adjusted dynamically which further improves the fairness among FUEs. Nevertheless, the CCRA and UFGA algorithm only consider the inter-cell interference, and the GB-DFR algorithm does not consider the transmission rate of users in cell edge.

Fig.5 Average FUE spectral efficiency

Fig.6 Fairness degree among FUEs

6 Conclusions

In this paper, the co-layer interference and resource allocation among femtocells in UDN are discussed. An improved resource allocation algorithm based on clustering is proposed to solve the challenge in UDN. The proposed algorithm consists of color-based clustering algorithm, sub-channel allocation algorithm and the optimal solution power allocation algorithm. The algorithm theoretically makes up for the deficiencies of the staining algorithm in [12], adds optimal power allocation, and maximizes spectral efficiency. In fact, taking into account the needs of users, it is apply to the actual scene to enhance the fairness among users. Simulation results show that the algorithm in this paper has been relatively improved in fairness, average user throughput and spectral efficiency, especially in terms of user fairness.