Robustness-supported user association and small cell switching ON/OFF strategies in 5G mm-wave networks①

Ma Zhongyu (马忠彧),Li Bo,Yan Zhongjiang,Yang Mao

(*School of Electronics and Information,Northwestern Polytechnical University,Xi’an 710129,P.R.China)(**School of Electronic Information Engineering,Lanzhou Institute of Technology,Lanzhou 730050,P.R.China)

Abstract

Key words:millimeter wave (mm-wave),user allocation,minimum dominating set,robustness-supported

0 Introduction

Load-bearing ability of existing network may be overwhelmed by the whole traffic demand resulted from massive intelligent wireless terminals and diversified applications.As a result,some potential designs,such as ultra-dense deployment of small cell station (SCS) and millimeter-wave (mm-wave) communication,have been exploited in 5G system.

A flexible framework for the solution may be mm-wave integrated backhaul and access network (mm-wave IBAN),where a large number of mm-wave SCSs are deployed densely in the area of macro base stations (MBS)[1].From the perspective of backhaul,some SCSs (named aggregation SCS,A-SCS) are connected to the core network with dedicated fiber.Traffic of other SCSs (referred as general SCSs,G-SCS) are backhauled to the A-SCSs with mm-wave wireless communication in one hop or multi-hops.From the aspect of access,user equipment (UE) should be associated with multiple SCSs for the enhancement of the robustness in transmission link and the conquest of the sensitive to the obstruction in mm-wave.To that end,UEs can be connected to back-up SCSs when a SCS is slammed into fault or the link is interrupted.In other words,it is necessary for each UE be associated with at leastk(k≥2) SCSs for the improvement of access link robustness.Therefore,the robustness of UE association can be enhanced with the redundant SCSs.It should be noted that these interruptions are not obvious on the backhaul links between SCSs because most SCSs are deployed on building roofs or lamps,i.e.the line-of-sight transmission environment between SCSs is comparatively stable.On the other hand,huge power consumption generated by the deployed SCSs and UEs can not be ignored.As reported in Ref.[2],the dominant part of the total power consumptions are contributed by the SCSs.In other words,more SCSs are switched on,more power consumptions are produced.To that end,the number of the active SCSs should be minimized due to the requirement of 5G green communication.Therefore,how to keep the minimum number of the active SCSs under the consideration of the capacity constraints and user association robustness is an urgent problem to be solved.

The ON/OFF control strategies of SCSs in mm-wave IBAN are focused on by many references in the reduction of the power consumption.As a preliminary work,great power-saving potentials in the dynamic adjustment of the control strategies are demonstrated in Ref.[3].In Refs[4,5],the potential is further developed and a SCS control algorithm is proposed.In Ref.[6],the dynamic adjustment of active SCSs in heterogeneous networks is studied for the minimization of the total power consumption.In Ref.[7],the energy efficiency (EE) of mm-wave IBAN is maximized with the dynamic control strategies of SCSs.In Ref.[8],EE of mm-IBAN is optimized through the introduction of different levels in sleep depth.However,link robustness of mm-wave is not considered in the above-mentioned related work.In fact,mm-wave access links will be severely interrupted due to changes of the blocking and the transmission distance.

Many attentions of the user association problem in mm-wave IBAN are focused on by scholars in recent years due to its key role in enhancing load balancing,spectrum efficiency and network energy efficiency.In Ref.[9],the joint optimization of user association and power allocation is investigated,and a polynomial time sub-optimal solution is found with linear relaxation and Lagrangian dual decomposition theory.In Refs[10,11],the joint optimization of user association and resource allocation in two-tier heterogeneous networks is investigated.In Ref.[12],a QoS-aware decision strategy of joint user association and resource allocation is proposed for the maximization of network energy efficiency.In Ref.[13],the framework of user association algorithms in 5G system is classified and introduced.In Ref.[14],a mobility-aware user association strategy for mm-wave IBAN is designed.In Ref.[15],the optimization of multiple SCSs associated by users and corresponding backhual path planning are studied for the maximization of the energy efficiency.

The importance of control strategies and user association in performance improvement is fully illustrated by the above inspiring work.Obviously,the access link fault and the switching ON/OFF control strategies are not considered simultaneously in the above-mentioned methods.Therefore,the optimization problem of robustness-supported user association and SCS switching ON/OFF is investigated in this work,where the minimum number of active SCSs or the aggregation power consumption of SCSs is determined under the condition that all UEs are connected to at leastkSCSs and the link capacity constraints are satisfied.

1 System overview

Following assumptions are made under the consideration of unique characteristics in mm-wave IBAN.Firstly,the downlink transmission scenario is considered and saturated traffic of access link is generated at each UE.Secondly,a two-layer network is considered due to the end-to-end delay requirement pointed out in Ref.[16],i.e.,traffic of user associated in each SCS is transmitted from the gateway in 2 hops.Finally as shown in Fig.1,there are 2 types of link failure in the user access link because mm-wave transmission is sensitive to obstruction.One type of failure is link between G-SCS and the associated UE is blocked.The other type of failure is the SCS is in fault and links between G-SCS and all the associated UEs are blocked.For the former,the UE can be converted to other backup G-SCS.For the latter,all UEs originally associated with the faulty G-SCS are connected to respective backup G-SCSs.

Fig.1 The k-connected user association and link faults

It is supposed that there are some A-SCS,G-SCS and UEs uniformly distributed in the coverage area of MBS,and the set of devices in the network is denoted byV=N∪M∪U.The number of A-SCSs isN=|N|,the number of G-SCSs isM=|M| and the number of UEs isU=|U|,where |·| is the operator of cardinality.For the achievement of the high directional transmission,multiple electronically steerable directional antennas (ESDA) may be installed in each SCS for data transmission.However,there is only one ESDA installed in each UE due to the limited space and prohibitive cost.The unified resource ratio between the access and backhaul is partitioned in each SCS for the avoidance of the co-channel interference between the access and backhaul.Therefore,the backhaul band used in each SCS isWBHand the access band used in each SCS isWAC.The link set in the network is denoted byε=εAC∪εBH,whereεACis the access link set andεBHis the backhaul set.

(1)

The reception antenna gain ofrlis given as

(2)

In Eqs(1) and (2),ifl∈εBH,then the sender is A-SCS and the receiver is G-SCS,and ifl∈εAC,then the sender is G-SCS and the receiver is UE.The values of parametersαandθare different with the attribute ofl,i.e.l∈εACorl∈εBH.It is assumed that there may be 3 transmission states,which are line of sight (LOS),non-line of sight (NLOS) and interruption,in mm-wave access link between any UE and the associated SCS.In Ref.[17],the probability functions of the 3 states in mm-wave transmission are described as

,lac∈εAC(3)

lac∈εAC(4)

In Eq.(4),ξacis random variables subjected to standard normal distribution with parameterσac.The values of parametersτac,βacandσacin the state of LOS and NLOS are different.Since the backhaul link is relatively stable and is always in the LOS state,the path loss function for backhaul link is expressed as

lbh∈εBH(5)

Therefore,the receiving power ofrlfor any linkl∈εcan be obtained as

(6)

l,f∈ε,f≠l(7)

In Eq.(7),the situation that linklis interfered by linkfis denoted byf∝l.The multiuser interference factor used to characterize the cross-correlation of signals on different links is denoted byρ.Small-scale fading is not considered in this paper because there is little influence on mm-wave networks.Therefore,the SINR of the receiverrloflcan be expressed as

(8)

In Eq.(8),N0is the background noise,the communication bandwidth of linklisWl.It should be noted that different communication bandwidth corresponds to different link attributes.In other words,ifl∈εACthenWl=WAC,ifl∈εBHthenWl=WBH.Therefore,the achievable rate of linklcan be calculated with Shannon theory as

Rl=Wl×log2(1+SINRrl),l∈ε

(9)

2 Greedy-based user association and swiching ON/OFF strategy of SCS

2.1 Problem formulation

It is assumed that the power consumption of an active G-SCS isPt.On the one hand,each UE can be connected to at leastkG-SCS under the consideration of the robustness requirement for network access link.When one access link is blocked or faulted,other access links can be selected for access transmission.On the other hand,more active G-SCS mean higher aggregated power consumption.Therefore,the number of active G-SCS in the network should be minimized under the consideration that the robustness of user access link is ensured.To that end,how to minimize the aggregation power consumption,i.e.,the number of G-SCS,under the consideration of the requirement for the robustness should be focused on.The network in a given area is represented as an undirected network graph,which is denoted byG=(V,ε).V=M∪N∪U,whereNis the set of A-SCSs,Mis the set of G-SCSs,Uis the set of UEs.ε=εAC∪εBHis the set of links,whereεBHis the backhaul links between G-SCSs and A-SCSs,εACis the access links between G-SCSs and UEs.The set of selected active G-SCSs is denoted by.If vertexuis connected with vertexv∈C,thenuis dominated byv.The physical meaning is that the traffic ofuwill be transmitted fromvoruis associated withv.The objective of the problem is to find the setCwhose cardinality is minimum so thatu∈Uis dominated by at leastk(k≥2) vertices inC.In other words,the link invulnerability degree for each UE isk-1.There are at least otherk-1 access links connected to G-SCSs from the UE when the first type of link failure occurrs on one access link.When the second type of link failure occurrs on any G-SCS as above-mentioned,all associated UEs are still dominated by setC.In terms of capacity constraints,the total traffic volume on the access links of each G-SCS should be less than or equal to the backhaul link capacity.To that end,the G-SCS with better channel state is preferred to be chosen for the minimizing the number of selected active G-SCSs,i.e.the cardinality of the setC.

In terms of mathematical model expression,the optimization problem is formulated as the following 0-1 integer programming (IP) problem:

(10)

In Eq.(10),the binary decision variablexvis defined to indicate whether the vertexvis selected as active G-SCS,i.e.ifxv=1,then vertexv∈Mis selected as the activated G-SCS,i.e.v∈C.Otherwise,the G-SCS represented by vertexvis set the state of sleeping.Similarly,the binary decision variableyexis defined to indicate whether the edgeeis adjacent to vertexx(x=voru),i.e.ifyex=1,then edgeeis adjacent to vertexx,which is denoted byx↗e(x=voru).The edge set in which the edge is adjacent to vertexxis represented byΞ(x)(x=voru).C1 is the link capacity constraint,the backhaul link capacity of active G-SCS should not be exceeded by the access link capacity of all UEs associated with the G-SCS whenvis selected as active G-SCS.The access link capacity of edgee,which is adjacent to the vertexv∈C,for the active G-SCS is denoted byRve.The capacity of the backhaul link between A-SCS and G-SCS is expressed asΓ.C2 is the link redundancy constraint of the UEs,i.e.each UE can be connected to at leastkG-SCS.The constraints relationship between the binary decision variablesxvandyevare described withC3.In other words,once the G-SCS represented by vertexvis selected as active G-SCS there must be one edge that is adjacent to itself.C4 andC5 are integer constraints for the 2 types of binary variables.For ease of description,the problem described in Eq.(10) is expressed asP1.

Obviously,the algorithm complexity for solvingP1 is exponentially increased with the enlargement of the cardinality of the dominant setC(|C|) due to its combinability.To that end,P1 is proofed as a NP-hard problem through simplification into minimal dominant set,which is a classical case of NP-hard problem.

Definition1Given undirected graphG′=(V′,ε′),a subsetC′⊆V′ is called dominant set if and only if each vertexv∈V′C′ is covered by a vertexu∈C′.In particular,as few vertexes as possible are selected fromV′ into the subsetC′,so that the remaining vertexes ofV′ are edged with the vertexes inC′.Such a subsetC′ is the minimum dominant set (MDS).

Lemma1P1 can be simplified into the MDS problem.

ProofofLemma1P1 can be described as the determination of the dominant setC′ with the minimum number of vertices,where the vertex is used to backhaul the traffic of the associated UEs.According to Definition 1,we can setG′=G,V′=V,ε′=ε.The capacity of vertexc∈Vis defined as infinite for the relaxation of constraintC1.At the same time,letk=1 in the constraint conditionC4.Then the solution of the minimum dominant set is also the solution ofP1.To that end,the problemP1 is translated into the minimum dominant set problem.

Theorem1The problemP1 is a NP-hard problem.

ProofofTheorem1If there is only one active G-SCS inCto be associated by each UE,the subsetCcomposed by the selected active G-SCSs is equivalent to the dominant setC′.In other words,the minimum dominant set problem is a special case of problemP1,i.e.,kis equal to 1 at this point.According to Definition 1 and Lemma 1,problemP1 is also considered as a NP-hard problem reasonably because the minimum dominant set problem is a NP-hard problem.

It should be further clarified thatP1 is actually ak-minimum dominated set problem (k-MDS).Here,kmeans that each UE is connected to at leastkG-SCSs.In addition,the cardinality of the dominant setC(|C|) should be minimized ink-MDS on the basis that all of the UEs in the network are dominated byC.

2.2 Greedy idea based heuristic algorithm

As mentioned above,P1 is a NP-hard problem,and the solution of which is difficult to find in polynomial time.Therefore,a greedy-idea-based heuristic algorithm (GIHA) is proposed for the searching of suboptimal solution ofP1.The idea of GIHA is extended from that of Ref.[18].In Ref.[18],the construction problem of ak-connected andm-dominated set (kCmDS) is formulated for the location selection of central server in communication system.A centralized algorithm is presented for the capacity constrained MDS (cc-MDS) problem and the asymptotic bound of the algorithm presented in Ref.[18] is given asIn(N).

A general description of GIHA is given first.Initially,Cis an empty set,i.e.,there is no vertex inC.As the algorithm runs,the vertex with the largest coverage degree is selected and added into the dominant setC.The algorithm stops running until all the vertexesu∈Uare dominated by the vertexes ofC.Specific steps are shown in Algorithm 1.Then the detailed description of the used symbols and the appeared operations of Algorithm 1 are explained.

If an assignment where the G-SCS is assigned to the UE under the consideration of the capacity constraintC2 inP1 is found,the assignment is a feasible assignment.Given a feasible assignmento,U(o) is a set of unassigned fixed points,i.e.U(o)=UDom(o).Dom(o) is the set of vertices covered byo,and the set of uncovered vertexes is denoted byU(o).Given a feasible assignmento,some vertexes are not necessarily dominated by theirkneighbors G-SCSs.The set where the vertex is dominated bya(ak) vertexes ofCis denoted byPa(o).For any feasible assignmento,the ‘excess degree’ ofois defined as

(11)

As can be seen,the value ofQ(C,o) is zero when all of theu∈Uis associated by the vertexesv∈C.

Algorithm1Greedyideabasedheuristicalgorithm(GI-HA)Input:G=(V,ε),kOutput:C1:Initialization:C=ϕ2:whileQ(C)≻0do3: forn∈MCdo4:Selectthevertexn′∈MCthatthevalueofQ(C∪{n′})isminimalandaddintoC′=C∪{n′};5:Constructflownetwork Gf=(C′,VC′,∞,Ruv,Γ);6:CalculatethemaximumintegralflowfGforGf;7: CalculateQ(C′,o);8:endfor9: Setn′=o(v)asdominatingvertexofvsuchthatfG(n′,v)≻0;10: Returnn′11:endwhile

In line 1 of Algorithm 1,the dominant set is initialized.From line 2 to line 11,the local optimal solutionis are iteratively selected for the feasible assignments under the consideration of robustness and capacity constraints,where the minimum excess degree of a given dominant setCin graphGis calculated under the consideration of the domination number and the capacity constraints.In fact,the minimum excess degree is resulted from the maximum flow obtained.A network flow graph,which is denoted byGf=(C,U,c1,c2,c3),is constructed with the current assignment functionU(o).It is shown in Fig.2 that the network flow graphGfis composed of a bipartite graphGb=(C,U,εc),whereεc={(u,v)|v∈C,u∈U} is a set composed of edges connecting the vertexesv∈Cand the vertexesu∈U.In addition,two additional virtual vertexes,which are denoted bysandd,are added into the bipartite graphGb.sis the virtual source node representing the core network from which the traffic is generated.dis the virtual destination node representing the UEs to which the traffic is received.

Fig.2 Construction for Gf(C,U,c1,c2,c3)

In addition,sis connected with every vertex ofC,anddis linked with every vertex inU.Finally,the link capacity is defined asγ.The capacity of 3 types of links is set asc1=γ(u,d)(u∈U),c2=γ(v,u),c3=γ(s,v)(v∈C).Therefore,network flow graphGf(C,U,c1,c2,c3) is constructed on the basis of bipartite graphGb=(C,U,εc).

Each vertexn∈MCis traversed in the four loops.For each vertexn∈MC,assignmentn′=o(v) is included in current coverage setC,i.e.,C=C∪{n′}.At this time,Gf=(C,U,∞,Ruv,Γ) is constructed.To that end,the excess degreeQ(C,o) of network flow graphGfcan be obtained with the calculation of the maximum integral flowfG.The vertexes representing the SCS with the smallest excess degreeQare selected as active G-SCSs.

The proposed GIHA runs out when the value ofQ(C,o) generated by dominant setCis equal to 0.This also means that the unassigned vertex setU(o) will eventually become an empty set because all the vertexes ofU(o) are traversed by the proposed GIHA in each iteration.In addition,it should be noted that the output dominant set,i.e.,C,is a complete feasible set when the proposed GIHA runs out.In other words,the constraints fromC1 toC5 inP1 are well satisfied.Moreover,the complete feasible set always exists in the scenario where the network is fully connected.In particular,the asymptotic bound of the algorithms complexity for GIHA isln(M+U) if the value ofkis equal to 1 and the backhaul capacity of each SCS is constant,whereMis the number of G-SCSs in the network andUis the number of UEs in the network.

3 Performance simulation

3.1 Parameter setting

In the simulation,SCSs and UEs are intensively deployed in a square kilometer area.The distribution of UEs follows the poisson point process (P.P.P.) with mean valueλUE.λUEincreases from 20 to 200 with an increment steps of 10.The distribution of SCSs is subjected to the P.P.P.with mean valueλSCS=100.The effective communication distance of mm-wave wireless communication is set as 200 m.The available communication bandwidth for each SCS in the network is 2 GHz,i.e.,W=2 GHz,whereWBH=0.7WandWAC=0.3W,WBHis the backhaul bandwidth andWACis the access bandwidth.Other parameters including parameters of the three-state statistical model,path loss model and small-scale fading,related to the channel model are shown in Table 1.

Table 1 Parameters in the simulation

3.2 Result analysis

The distribution density of UEs is increased at a linear rate for the investigation of the variation in the number of the active G-SCSs used to associate with the UEs.The variation in the number of the active G-SCSs in the optimal algorithm,the proposed algorithm (GIHA) and the shortest distance access algorithm are shown in Fig.3.The optimal algorithm is obtained through the use of MILP solver,which is CVX with Gurobi optimization.Generally,linear programming relaxation based on branch-and-bound algorithm is used by MILP solver to solve MILP problem.The results represented with every bar are the average values of 1 000 simulations in each algorithm.

It can be seen in Fig.3 that the number of active G-SCSs is increased logarithmically when the distribution density of UE is increased along theX-axis.In addition,it can also be seen that the number of G-SCSs used for UE association tends to be saturated when the UE distributed in the network becomes more dense.This means that the total traffic transmitted to UEs in each G-SCS may be smaller.To that end,the total achievable rate of the system will also be saturated due to the increase of ambient interference and the constant link capacity.The gap in the number of G-SCSs between the 3 algorithms is very small when the user density is small.However,the difference in the gap of the number of G-SCSs selected by the 3 methods is increased to 15 when the distribution density of UE becomes denser,i.e.greater than 150.

Fig.3 Number of active G-SCSs vs.distribution density of UE

In fact,the problem of active G-SCSs selection in this paper is similar to the problem of the establishment of the virtual backbone network in the field of wireless ad hoc network (such as wireless sensor network,WSN).The problem is mainly used to effectively reduce the routing energy consumption and the reliable data aggregation of WSN.Usually,this problem is expressed as the construction of ak-connected andm-dominated set (kCmDS) of the graph.In addition,it is calledk-vertex connection if there are at leastkindependent paths between each pair of vertices.The proposed algorithm is compared with the FindkmCDs algorithm,which is a centralized algorithm proposed in Ref.[18].

In the FindkmCDs algorithm of Ref.[18],the vertexes are sorted in descending order of node degree firstly.Then the vertexes whose node degree is minimum are added into the subset until each vertex is dominated by at leastmvertexes.Fastly,theknon-dominant vertexes are allocated to each vertex ofC.To that end,ak-connected andm-dominated set is constructed.On this basis,a slight modification is made in our algorithm from two aspects,i.e.,1) An iterative control variable named ‘excess degree’,which is equal to zero when the condition of user access robustness is satisfied,is defined for the feasible assignment.2) Vertexes are dominated and covered only when the capacity constraints are satisfied.

As shown in Fig.4,the difference between FindkmCDs and the proposed algorithm (GIHA) is very small whenk=1.Intuitively speaking,the cardinality of the dominant set is smaller if the vertexes with larger node degree are added.However,all the UEs may be not necessarily dominated by the adjacent vertex with largest node degree in FindkmCDs without the consideration of link capacity.The gap between FindkmCDs and GIHA becomes larger whenk= 2.This is because that the local optimal solution in each iteration is chosen by the proposed GIHA.However,the sequenced SCS vertexes are added repeatedly in FindkmCDs.To that end,there may be some redundant vertexes existing in the dominant set.

Fig.4 Comparison of selected G-SCS number between the 3 algorithms when k=1 and k=2

If the traffic variation between different G-SCSs is considered,it is shown in the results that there are more opportunities for the G-SCS with lighter associated load to be selected in GIHA.Therefore,ten different levels of traffic requirement for UEs are set up in the network.The results of 2 algorithms,i.e.,GIHA and the optimal algorithm,under 2 representative traffic load levels,i.e.,the highest level and lowest traffic level,are plotted in Fig.5.It can be seen that Fig.5 can be divided into 2 parts,the first part is the low density scenario where the density of the UEs is less than 50,and the other part is the high density scenario where the density of UEs is higher than 50.For high density network scenarios,the percentage of the selected low-traffic G-SCSs to total SCSs is increased with the enhancement of the UE density.It is shown in the results that the system tends to choose G-SCS with larger access capacity to associate more UEs.In this way,GIHA is better than the optimal algorithm because the size of the active G-SCS set for the UE association is sacrificed in GIHA.For low-density network scenarios,the trend is reverse because the ratio of selected G-SCSs to the total G-SCSs is as high as 40%.On the other hand,the percentage of selected SCSs with the heaviest traffic acts vise versa.The decreasing trends are shown in the 2 lower curves in Fig.5.

Fig.5 The percentage of different loading-level G-SCS selected varying with the increasing UE densities

4 Conclusions

In this paper,a robustness-supported user association and small cell ON/OFF strategies is proposed for mm-wave IBAN.To that end,the number of G-SCSs that are active and associated with UEs is minimized under the consideration of the link capacity and the robustness constraint,where there are at leastMYMkMYMG-SCS for the each UE to connected.At the same time,the proposed algorithm,the optimization algorithm and FindkmCDs algorithm are compared in terms of the number of the selected active G-SCSs,i.e.the total power consumption of the network,and the proportion of active G-SCSs to the total G-SCSs.As a result,the advantages of the proposed algorithm in the densely deployed mm-wave IBAN network are illustrated.

Actually,there is a strong coupling between access and backhaul of mm-wave IBAN.It should be pointed out that the multi-hops backhaul scenario of mm-wave IBAN and the integrated optimization method of backhaul and access are not considered in this paper.Therefore,the resources duality between the backhaul link and access link of SCSs will be considered in future work for the fully studying of the joint optimization system in terms of user association,backhaul path planning and resource allocation.