# Energy-Efficient User Association Strategy for Hyperdense Heterogeneous Networking in the Fifth Generation Systems

Authors: Lei Li; Hao Jin; Zhipeng Yan; Changqing Yang; Yong Wu
Journal: International Journal of Antennas and Propagation
 (2015)

---

## Abstract

Redesigning user association strategies to improve energy efficiency (EE) has been viewed as one of the promising shifting paradigms for the fifth generation (5G) cellular networks. In this paper, we investigate how to optimize users’ association to enhance EE for hyper dense heterogeneous networking in the 5G cellular networks, where the low-power node (LPN) much outnumbers the high-power node (HPN). To characterize that densely deployed LPNs would undertake a majority of high-rate services, while HPNs mainly support coverage; the EE metric is defined as average weighted EE of access nodes with the unit of bit per joule. Then, the EE optimization objective function is formulated and proved to be nonconvex. Two mathematical transformation techniques are presented to solve the nonconvex problem. In the first case, the original problem is reformulated as an equivalent problem involving the maximization of a biconcave function. In the second case, it is equivalent to a concave minimization problem. We focus on the solution of the biconcave framework, and, by exploiting the biconcave structure, a novel iterative algorithm based on dual theory is proposed, where a partially optimal solution can be achieved. Simulation results have verified the effectiveness of the proposed algorithm.


---

## Body

## 1. Introduction

To provide universal high-data coverage and a seamless user experience, it is anticipated that the fifth generation (5G) cellular networks have extreme base station (BS) density and heterogeneity. Besides, the core networks can reach unprecedented levels of flexibility and intelligence [1], which allows the cellular strategies designed towards high efficiency with moderate complexity. Meanwhile the issue on improving energy efficiency (EE) has gained big momentum due to the increasing awareness of environmental protection and cost-efficiency. Energy-aware design and planning are motivated by the fact that wireless networks are responsible for a fraction between 0.2 and 0.4 percent of total carbon dioxide emissions [2], and this value is expected to grow due to the ever-increasing number of subscribers.To curtail expenditures and improve EE performance, cloud radio access networks (C-RANs) are by now recognized as a promising system structure evolution for the 5G cellular networks [3]. The densely deployed remote radio heads (RRHs) operate as soft relay by compressing and forwarding the received signals from UEs to the centralized baseband unit (BBU) pool. Then, the centralized large-scale cooperative processing, such as the joint decompression and decoding schemes, can proceed in the BBUs. Since RRHs are mainly deployed to provide high capacity in special zones, to guarantee backward compatibility with the existing cellular systems and support seamless coverage, high-power nodes (HPNs) are still critical in C-RANs. With the help of HPNs, the multiple heterogeneous radio networks can be converged, and all system control signals are delivered wherein. Consequently, HPNs should be incorporated into C-RANs, and thus heterogeneous cloud radio access networks (H-CRANs) are proposed in [4, 5], to take full advantage of both HetNets and C-RANs. The abovementioned advantages and challenges for cellular networks request a redesign of user association strategies [6]. Therefore, this paper focuses on how to design user association strategies to improve EE for the hyperdense heterogeneous networking with a mass of low-power nodes (LPNs) and some HPNs.Traditionally, users are associated with the BS providing the maximum received signal reference power (RSRP), which imposes a heavy burden on the tower-mounted macro BSs. To make the most of the dense low-power infrastructure, mobile users are actively pushed onto small BSs by usingbiases in [7]. Considering the fairness among users, load balancing between macrocells and small cells is investigated in [8, 9]. In [8], the metric of cell selection is changed from the signal strength to theaverage throughput. Based on this metric, handover will happen once it brings positive gain of network throughput. In [9], the received signal to interference and noise ratios (SINRs) at users from BSs are multiplied by the designed factors to make small cells more attractive than macrocells. To control the bias towards improving throughput and enhancing users’ fairness during association, a α-fairness network utility function is formulated and optimized in [10]. The user association problem in conjunction with the almost blank subframe (ABSF) technique is considered in heterogeneous networks (HetNets) in [11], and the optimal ABSF density is proved to be the proportion of vulnerable users in total users. All aforementioned works have a network utility maximization objective that was adopted with log-utility to obtain network-wide proportional fairness [12], but few of them focus on the EE performance of cellular networks.Recently, attentions have been also paid to the energy-efficient design of user association strategies [13, 14]. A distributed association strategy is developed to minimize the total power cost of heterogeneous cloud cellular networks in [13]. An energy-efficient user association problem is studied from a population game-theoretic perspective to minimize power consumption in [14]. However, the researches on energy-efficient user associations are still much limited and insufficient. One of the open issues is how to define EE for different networks. Ordinarily, EE metrics are mainly designed either to minimize the network power consumption under quality of service (QoS) constraints or to maximize the ratio of the network throughput to the area power consumption. However, for hyperdense heterogeneous networking in the 5G cellular networks, with the loads continuing to be transferred from macrocells to small cells, the roles of macro BSs and small BSs are gradually distinguished [15]. High-power macrocells are mainly responsible for coverage, while a large number of low-power small cells undertake a majority of high-rate services. It indicates that power is consumed for both providing coverage and enhancing network capacity. Such distinction should be reflected in the EE metric. Therefore, the EE metric may need to be redesigned for above characteristics.Another important issue is how to solve nonconvex EE optimization problems. In [16], the weighted EE is proved to be quasiconcave, and a bisection based resource allocation (RA) strategy is proposed accordingly. In [17], to monotonically increase EE, a quasi-distributed iterative RA algorithm is proposed for heterogeneous orthogonal frequency division multiplexing (OFDM) systems. In [18], an equivalent model for the nonconvex EE optimization object function is researched and solved by an iterative algorithm. These aforementioned works mainly focus on the design of energy-efficient RA strategies and suggest that there is no common solution for nonconvex optimization problems. In this paper, two mathematical transformation techniques will be presented to solve the nonconvex energy-efficient association strategy.Contributions of this paper are summarized as follows. First, the EE performance of HPNs and LPNs is distinguished, and a new EE metric, that is,average weighted EE of access nodes, with the unit of bit per joule is proposed. Second, an EE optimization objective function is formulated to optimize user association strategy under the constraints of backhaul capacity, users’ data rate, and the maximum transmit power of BSs, which is proved to be neither convex nor quasiconvex. Third, two mathematical transformation techniques are introduced. In the first case, the nonconvex original problem is reformulated as a biconcave maximization framework. In the second case, the original problem is equivalent to a concave minimization framework. Furthermore, the relationship between two reformulated problems is presented. Fourth, an iterative algorithm based on dual theory and properties of the biconcavity is proposed to solve the equivalent biconcave maximization problem. Simulation results have verified the effectiveness of the iterative algorithm and suggest that transferring loads from HPNs to LPNs can improve the network EE.The remainder of the paper is organized as follows. Section2 gives the system model and formulates the problem. In Section 3, two equivalent transformation techniques are presented, respectively; then the optimization algorithm for the first equivalent problem is introduced. In Section 4, simulation results are presented, followed by some conclusions drawn in Section 5.


## 2. System Model and Problem Formulation

A general K-tier downlink radio network is considered, which can apply to a H-CRAN network or a dense HetNet. All deployed access nodes are called a BS for simplicity. Then, denote byB the set of all BSs in K-tiers and U the set of all users. As shown in Figure 1, users are allowed to be associated with multiple BSs at the same time. The association indicator for the ith user and the jth BS is represented as xi,j, where ∀i∈U, j∈B, xi,j∈0,1, and ∑i∈U‍xi,j=1. Denote by cBji the average spectral efficiency (SE) on the radio link between the ith user and the jth BS, and assume that the system has the knowledge of cBjiU×B during association (similar assumptions can be found in [7–11], in which the received average SINRs at users from BSs for different radio resources are fixed during association; in addition, cBjiU×B can be easily obtained in H-CRANs, wherein HPNs can achieve all system control signals in a centralized way). The data rate requirement of the ith user is represented as Ri, and the jth BS is responsible for xi,jRi. Denote by Wj and PBj the total frequency band and maximum transmit power of the jth BS, respectively. Then, the jth BS needs to assign the user with wBji=xi,jRi/cBji frequency band, which accounts for wBjiPBj/Wj power consumption. Based on above assumptions, it is easy to verify that if the requirement of the ith user is satisfied, the achieved data rate is Ri. The total transmit power and throughput in the ith BS are written as Ptj=∑i∈U‍(xi,jRiPBj/CBjiWj) and Cj=∑i∈U‍xi,jRi, respectively.Figure 1
User association in the hyperdense HetNet.


### 2.1. Energy Efficiency Metric

Then, how to define EE for the dense K-tier radio network is our focus in this part. As mentioned in the Introduction, for hyperdense heterogeneous networking, a large number of LPNs like pico BSs undertake a majority of high-rate services, while HPNs like macro BSs are mainly responsible for coverage. Though HPNs could contribute a small proportion of throughput compared with LPNs, they account for a significant proportion of power consumption due to high transmit, circuit, and cooling power. The existing EE metric defined as the ratio of area network throughput to area power consumption can not reflect the above characteristics. To distinguish the power consumption for ensuring coverage and providing high-rate services, we propose a new EE metric:(1)EE¯=1B∑j∈BkjEEj,which also has the unit bit per joule, where B denotes the cardinality of the BS set B and kj and EEj are the predefined weight factor and the EE value of the jth BS, respectively. A tradeoff between ensuring coverage and enhancing data services can be achieved by adjusting the weight factors of HPNs and LPNs.


### 2.2. Problem Formulation

Denote byx=xi,jU×B the association matrix. Mathematically, we formulate the EE optimization objective function for the association as(2)PXmax⁡xη¯EEx=1B∑j∈BkjCjPtjβj+P0j(3)s.t.PtjPBj=∑i∈Uxi,jRicBjiWj≤1,∀j∈B,(4)∑i∈Uxi,jRi≤RBHj,∀j∈B,(5)∑j∈Bxi,j=1,xi,j∈0,1∣∀i∈U,j∈B,where βj and P0j are the amplifier coefficient and the fixed power consumption in the jth BS, respectively. The fixed power includes circuit power and cooling power (only macro BSs). The expressions (3), (4), and (5) constrain the transmit power of BSs, the backhaul throughput, and users’ data rate, respectively. In (4), RBHj represents the capacity limitation for the backhaul links of the jth BS.Remark 1.
Problem (PX) is presented as the maximization of the sum of linear fractional functions over the domain constrained by (3)~(5). Though the domain can be proved to be convex, it is shown in [19] that problem (PX) is neither quasiconcave nor quasiconvex, even when B=2 and Pt2+P02 is set equal to 1, that is, even when problem (PX) is simplified as the sum of one linear term and one fractional term.


## 2.1. Energy Efficiency Metric

Then, how to define EE for the dense K-tier radio network is our focus in this part. As mentioned in the Introduction, for hyperdense heterogeneous networking, a large number of LPNs like pico BSs undertake a majority of high-rate services, while HPNs like macro BSs are mainly responsible for coverage. Though HPNs could contribute a small proportion of throughput compared with LPNs, they account for a significant proportion of power consumption due to high transmit, circuit, and cooling power. The existing EE metric defined as the ratio of area network throughput to area power consumption can not reflect the above characteristics. To distinguish the power consumption for ensuring coverage and providing high-rate services, we propose a new EE metric:(1)EE¯=1B∑j∈BkjEEj,which also has the unit bit per joule, where B denotes the cardinality of the BS set B and kj and EEj are the predefined weight factor and the EE value of the jth BS, respectively. A tradeoff between ensuring coverage and enhancing data services can be achieved by adjusting the weight factors of HPNs and LPNs.


## 2.2. Problem Formulation

Denote byx=xi,jU×B the association matrix. Mathematically, we formulate the EE optimization objective function for the association as(2)PXmax⁡xη¯EEx=1B∑j∈BkjCjPtjβj+P0j(3)s.t.PtjPBj=∑i∈Uxi,jRicBjiWj≤1,∀j∈B,(4)∑i∈Uxi,jRi≤RBHj,∀j∈B,(5)∑j∈Bxi,j=1,xi,j∈0,1∣∀i∈U,j∈B,where βj and P0j are the amplifier coefficient and the fixed power consumption in the jth BS, respectively. The fixed power includes circuit power and cooling power (only macro BSs). The expressions (3), (4), and (5) constrain the transmit power of BSs, the backhaul throughput, and users’ data rate, respectively. In (4), RBHj represents the capacity limitation for the backhaul links of the jth BS.Remark 1.
Problem (PX) is presented as the maximization of the sum of linear fractional functions over the domain constrained by (3)~(5). Though the domain can be proved to be convex, it is shown in [19] that problem (PX) is neither quasiconcave nor quasiconvex, even when B=2 and Pt2+P02 is set equal to 1, that is, even when problem (PX) is simplified as the sum of one linear term and one fractional term.


## 3. Two Mathematical Transformation Techniques and Association Optimization Methods

In this section, two mathematical transformation techniques for the nonconvex problem (PX) are introduced individually. First, problem (PX) is reformulated as an equivalent biconcave maximization problem. Second, problem (PX) is equivalent to a concave minimization problem. The relationship between the two equivalent problems will be introduced. Then, we focus on how to solve the biconcave maximization framework by employing dual theory and properties of biconcave functions.


### 3.1. The First Mathematical Transformation Technique

Denote byX the domain constrained by (3), (4), and (5). For j=1,2,…,B, we first consider the subproblem(6)PXjmax⁡xkj∑i∈Uxi,jRi∑i∈Uxi,jRi/cBjiWjPBjβj+P0,js.t.x∈X.Since the numerator in (6) is differentiable and concave on X and the denominator in (6) is positive and linear on X, problem (PXj) is pseudoconcave on X according to [20]. Therefore, for each j=1,2,…,B, any local maximum of problem (PXj) is also a global maximum of problem (PXj). Furthermore, problem (PXj) can be solved by using any appropriate convex programming methods. For example, a simple roll polling algorithm can be employed here; that is, the jth BS first serves the user with the largest cBji, and other users can be served if and only if their association can enhance the EE of the jth BS. Note that the association optimization for a single user to a single BS is convex. The detailed procedures for the roll polling algorithm are omitted here to save space, and we directly denote the maximum value of problem (PXj) by Qj. Then, a vector parameter q=qj1×B can be defined in the following set: (7)Q=q∈RB∣0≤qj≤Qj,j∈B,where RB denotes B-dimensional real space. Since problem (PX) is nonconvex, we introduce the following problem:(8)PX1max⁡x,qUx,q=1B∑j∈B2qjkj∑i∈Uxi,jRi-qj2∑i∈Uxi,jRicBjiWjPBjβj+P0js.t.x∈X,q∈Q.The objective of problem (PX1) is to achieve the optimal combination ofx,q that maximizes the network-wide utility function U(x,q). Both X and Q can be proved to be convex sets. Problems (PX) and (PX1) are equivalent in the aspects shown in Theorem 2 according to [19].Theorem 2.
Problem (PX1) is biconcave onX×Q. If x∗,q∗ is a globally optimal combination for problem (PX1), then x∗ is a globally optimal solution for the EE optimization problem (PX). Besides, it holds the relationship(9)qj∗=kj∑i∈Uxi,j∗Ri∑i∈Uxi,j∗Ri/cBjiWjPBjβj+P0j,j∈B.Proof.
First,X and Q are convex sets. For all j∈B, let(10)mjx,qj=2qjkj∑i∈Uxi,jRi-qj2∑i∈Uxi,jRicBjiWjPBjβj+P0j,where x∈X and qj∈0,Qj. Since, for each x∈X and q∈Q,(11)Ux,q=1B∑j∈Bmjx,qj,to show that (PX1) is biconcave, it suffices to show that, for all j∈B, mj is biconcave. Given a fixed x∈X, mj is a quadratic function with respect to qj. Since the coefficient ∑i∈U‍(xi,jRi/cBjiWj)PBjβj+P0j is always positive, mj is concave to qj on 0,Qj. In addition, given a fixed qj∈0,Qj, the power function 2qjkj∑i∈U‍xi,jRi can be easily proved to be concave on X. Besides, qj2∑i∈U‍(xi,jRi/cBjiWj)PBjβj+P0j is linear. Therefore, mjx,qj is concave on the vector xj, where xj=x1,j,…,xU,jT. The notation ·T represents the transpose operation. The biconcavity has been proved.
Suppose thatx∗,q∗ is the globally optimal solution to problem (PX1). q∗ can be directly obtained based on the biconcavity of problem (PX1) by solving(12)∂Ux∗,qj∂qj=0,0⩽qj⩽Qj,j∈B.
It is easy to verify that(13)qj∗=kj∑i∈Uxi,j∗Ri∑i∈Uxi,j∗Ri/cBjiWjPBjβj+P0j,j∈B.
To prove the optimality ofx∗, we first deny that x∗ is the globally optimal solution for the EE optimization problem (PX). Then, for some x¯∈X,(14)η¯EEx¯>η¯EEx∗.
Also, becauseUx,q is biconcave on X×Q, the globally optimal solution q¯ to the subproblem(15)max⁡qUx,qs.t.q∈Q,x=x¯can be calculated as(16)q¯j=kj∑i∈Ux¯i,jRi∑i∈Ux¯i,jRi/cBjiWjPBjβj+P0j,j∈B.
Sinceq¯j must be smaller than Qj according to subproblem (PXj), the combination x¯,q¯ is a feasible point in X×Q. Substituting (16) into problem (PX1), the utility value of problem (PX1) can be obtained, which equals η¯EEx¯. Similarly, substituting (13) into problem (PX1), the result is η¯EEx∗. Since x∗,q∗ is the global optimal solution of problem (PX1) in X×Q, it requires that η¯EEx¯≤η¯EEx∗ which contrasts (14). Therefore, x∗ must be a globally optimal association matrix for the EE optimization problem (PX).According to Theorem2, the nonconvex EE optimization problem in (2) can be reformulated as an equivalent optimization problem (PX1) involving the maximization of a biconcave function over X×Q, where Q⊆+RJ is a hyperrectangle.


### 3.2. The Second Mathematical Transformation Technique

Based on above discussions, the nonconvex problem (PX) can be reformulated as an equivalent biconcave problem. In this part, we will present another transformation technique which reformulates problem (PX) as a concave minimization framework.For eachj∈B, let Qj and qj be defined as before. For a given q, a new vector v=vj1×B is introduced, which is constrained as(17)V=v∈RB∣qj2⩽vj⩽Qj2,j∈B.Then, a utility function is formulated onQ×V as(18)
Y
q
,
v
=
min
x
∈
X
⁡
∑
j
∈
B
-
2
q
j
k
j
∑
i
∈
U
x
i
,
j
R
i
+
v
j
∑
i
∈
U
x
i
,
j
R
i
c
B
j
i
W
j
P
B
j
+
P
0
,
j
.Notice thatQ×V is a convex set. Furthermore, for each q¯,v¯∈Q×V, Yq¯,v¯ is the minimum value of a set of linear functions of (q,v) evaluated at q¯,v¯. Since linear functions are also concave functions, Y is a concave function on Q×V according to [21]. Based on the definition of Y function, we formulate a utility minimization problem as follows:(19)PX2min⁡q,vYq,vs.t.q∈Q,v∈V.Problem (PX2) involves the minimization of a concave functionY on the convex set Q×V, and it is an equivalent problem of the EE optimization problem (PX) in the aspects shown in Theorem 3.Theorem 3.
Ifq∗,v∗ is a globally optimal solution for problem (PX2), then x∗ is a globally optimal solution for problem (PX), where x∗ is any association matrix that achieves the minimum in (18) with q,v=q∗,v∗.Proof.
First, suppose thatq∗,v∗ is a globally optimal solution for problem (PX2) and x∗ achieves the minimum in (18) with q,v=q∗,v∗. Since in cellular networks the expressions kj∑i∈U‍xi,jRi and ∑i∈U‍(xi,jRi/cBjiWj)PBj+P0,j are always positive for each j∈B, to achieve the minimum of Y(q,v), the variable v should be assigned with a minimum value in V. Therefore, based on the definition of V, it holds that v∗=q∗2, and this implies that x∗ globally minimizes Yq∗,q∗2. It is equivalent to saying that (x∗,q∗) is the globally optimal solution for problem (PX1), which maximizes Ux,q. Therefore, x∗ is the globally optimal solution for problem (PX) according to Theorem 2.Based on above discussion, the nonconvex EE optimization problem (PX) can be reformulated as a concave minimization problem (PX2). This new property provides a new way to solve the original EE optimization problem. In addition, as proved in Theorem3, problem (PX2) can be further transformed to problem (PX1) by setting v=q2; hence our next focus is how to solve problem (PX1) by taking advantage of its biconcavity.


### 3.3. The Energy-Efficient Association Strategy

In this section, the biconcave problem (PX1) is solved by using the Alternate Convex Search (ACS) algorithm as in [20]. First, given a feasible association matrix x0∈X, the subproblem(20)S1:max⁡qUx,qs.t.q∈Q,x=x0=xi,j0U×Bis concave on Q and has a globally optimal solution represented as q0=qj01×B, where(21)qj0=kj∑i∈Uxi,j0Ri∑i∈Uxi,j0Ri/cBjiWjPBjβj+P0j,j∈B.The solutionx0,q0 is a feasible point in X×Q for problem (PX1). Similarly, given the q0, the subproblem(22)S2:max⁡xUx,qs.t.x∈X,q=q0is concave on X. To obtain the globally optimal solution of problem (S2), the dual theory is applied here. The duality gap is zeros since problem (S2) is concave. The Lagrange dual function for problem (S2) is formulated as(23)gα,β,λ=maxx∈X⁡Lx,α,β,λ=maxx∈X⁡∑j∈B2qj0kj∑i∈Uxi,jRi-qj02∑i∈Uxi,jRi/cBjiWjPBjβj+P0jB+∑j∈Bαj1-∑i∈Uxi,jRicBjiWj+∑j∈BβjRBHj-∑i∈Uxi,jRi+∑i∈Uλi1-∑j∈Bxi,j,where Lx,α,β,λ is the Lagrangian function and α=αj,j∈B⪰0,  β=βj,j∈B⪰0, and λ=λi,i∈U⪰0 are the dual variables for constraints (3), (4), and (5), respectively. The notation ⪰ is an element-wide operation. Lx,α,β,λ can be easily proved to be concave on x∈X, and the optimal solution x∗ to (23) is represented as(24)xi,j∗=0,τ0⩽0τ0,0<τ0<11,1⩽τ0,where τ0=qj02kjRi/γi+βjRiB+(αjRiB+qj02RiPBjβj)/cBjiWj2-∑m∈U∖i‍xm,j∗(Rm/Ri).Considering thatLx,α,β,λ is concave on X, the optimal association matrix for problem (S2) can be achieved by using the iterative coordinate search method in [21]. The explicit procedures are omitted here to save space. For simplicity of presentation, the solution of problem (S2) with input q0 is represented as x∗(q0)∈X. The dual problem is given as(25)D-S2mingα,β,λ=Lx∗q0,α,β,λs.t.α⪰0,β⪰0,λ⪰0.Obviously,Lx∗q0,α,β,λ is linear to α,β,λ. Hence, gα,β,λ is the maximum of linear function and the dual problem (D-S2) is always convex. Furthermore, the subgradient of gα,β,λ is presented as(26)Δαj=∑i∈Uxi,jRicBjiWj-1,Δβj=∑i∈Uxi,jRi-RBHj,Δλi=∑j∈Bxi,j-1.Then, problem (S2) can be solved by updatingα,β,λ via the ellipsoid method [21], of which the details are omitted here for brevity. Finally, the ACS algorithm is shown in Algorithm 1 at the next page. For simplicity, denote by xn∗ and qn∗ the solutions to problem (S1) and problem (S2) at the nth iteration, respectively.Algorithm 1:The Alternate Convex Search algorithm.
(1) Input:x0∈X, q0∈Q, CBjiu×B
(2) Initialize the maximum toleranceε, the maximum iteration number Nmax, the iteration index n=1,
x0∗=x0, and q0∗=q0.
(3)repeat  MainLoop
(4)  Calculate the optimalqn∗ by solving problem (S1) with input xn-1∗.
(5)  Calculate the optimalxn∗ by solving problem (S2) with input qn∗.
(6)if  Uxn∗,qn∗-Uxn-1∗,qn-1∗<ε
(7)then Convergence = true
(8)end if
(9)n=n+1
(10)until Convergence =  true or n>NmaxThe complexity of Algorithm1 is related with the value of ε. In each iteration, problem (S1) can be directly and optimally solved, while problem (S2) needs an inner loop to attain the optimal x∗ for a fixed q. The main operation expenditure of Algorithm 1 is equivalent to that of solving problem (S2), which is further equivalent to the complexity of solving (B×U) linear equations. Therefore, the complexity of Algorithm 1 is OB×U.Theorem 4.
The obtained sequenceUxn∗,qn∗n∈N generated by Algorithm 1 monotonically converges. Further, it holds that limn→∞xn∗-xn-1∗=0. (N denotes the set of nonnegative integers, and the notation · denotes the Euclidean norm of a matrix.)Proof.
Since the sequenceUxn∗,qn∗n∈N generated by Algorithm 1 is monotonically increasing and the function Ux,q is bounded from above, the sequence Uxn∗,qn∗n∈N converges to a finite value. Furthermore, suppose a feasible point x′,q′∈X×U. Since both problem (S1) with fixed x′ and problem (S2) with fixed q′ are convex and have a globally optimal solution, limn→∞xn∗-xn-1∗=0 holds according to Theorem  4.9 in [20].Although it has been proved in Theorem3 that both the sequence Uxn∗,qn∗n∈N and the sequence xn∗n∈N converge in finite iterations, the obtained xn∗ by Algorithm 1 is a partially optimal solution to problem (PX) instead of a globally optimal one.


## 3.1. The First Mathematical Transformation Technique

Denote byX the domain constrained by (3), (4), and (5). For j=1,2,…,B, we first consider the subproblem(6)PXjmax⁡xkj∑i∈Uxi,jRi∑i∈Uxi,jRi/cBjiWjPBjβj+P0,js.t.x∈X.Since the numerator in (6) is differentiable and concave on X and the denominator in (6) is positive and linear on X, problem (PXj) is pseudoconcave on X according to [20]. Therefore, for each j=1,2,…,B, any local maximum of problem (PXj) is also a global maximum of problem (PXj). Furthermore, problem (PXj) can be solved by using any appropriate convex programming methods. For example, a simple roll polling algorithm can be employed here; that is, the jth BS first serves the user with the largest cBji, and other users can be served if and only if their association can enhance the EE of the jth BS. Note that the association optimization for a single user to a single BS is convex. The detailed procedures for the roll polling algorithm are omitted here to save space, and we directly denote the maximum value of problem (PXj) by Qj. Then, a vector parameter q=qj1×B can be defined in the following set: (7)Q=q∈RB∣0≤qj≤Qj,j∈B,where RB denotes B-dimensional real space. Since problem (PX) is nonconvex, we introduce the following problem:(8)PX1max⁡x,qUx,q=1B∑j∈B2qjkj∑i∈Uxi,jRi-qj2∑i∈Uxi,jRicBjiWjPBjβj+P0js.t.x∈X,q∈Q.The objective of problem (PX1) is to achieve the optimal combination ofx,q that maximizes the network-wide utility function U(x,q). Both X and Q can be proved to be convex sets. Problems (PX) and (PX1) are equivalent in the aspects shown in Theorem 2 according to [19].Theorem 2.
Problem (PX1) is biconcave onX×Q. If x∗,q∗ is a globally optimal combination for problem (PX1), then x∗ is a globally optimal solution for the EE optimization problem (PX). Besides, it holds the relationship(9)qj∗=kj∑i∈Uxi,j∗Ri∑i∈Uxi,j∗Ri/cBjiWjPBjβj+P0j,j∈B.Proof.
First,X and Q are convex sets. For all j∈B, let(10)mjx,qj=2qjkj∑i∈Uxi,jRi-qj2∑i∈Uxi,jRicBjiWjPBjβj+P0j,where x∈X and qj∈0,Qj. Since, for each x∈X and q∈Q,(11)Ux,q=1B∑j∈Bmjx,qj,to show that (PX1) is biconcave, it suffices to show that, for all j∈B, mj is biconcave. Given a fixed x∈X, mj is a quadratic function with respect to qj. Since the coefficient ∑i∈U‍(xi,jRi/cBjiWj)PBjβj+P0j is always positive, mj is concave to qj on 0,Qj. In addition, given a fixed qj∈0,Qj, the power function 2qjkj∑i∈U‍xi,jRi can be easily proved to be concave on X. Besides, qj2∑i∈U‍(xi,jRi/cBjiWj)PBjβj+P0j is linear. Therefore, mjx,qj is concave on the vector xj, where xj=x1,j,…,xU,jT. The notation ·T represents the transpose operation. The biconcavity has been proved.
Suppose thatx∗,q∗ is the globally optimal solution to problem (PX1). q∗ can be directly obtained based on the biconcavity of problem (PX1) by solving(12)∂Ux∗,qj∂qj=0,0⩽qj⩽Qj,j∈B.
It is easy to verify that(13)qj∗=kj∑i∈Uxi,j∗Ri∑i∈Uxi,j∗Ri/cBjiWjPBjβj+P0j,j∈B.
To prove the optimality ofx∗, we first deny that x∗ is the globally optimal solution for the EE optimization problem (PX). Then, for some x¯∈X,(14)η¯EEx¯>η¯EEx∗.
Also, becauseUx,q is biconcave on X×Q, the globally optimal solution q¯ to the subproblem(15)max⁡qUx,qs.t.q∈Q,x=x¯can be calculated as(16)q¯j=kj∑i∈Ux¯i,jRi∑i∈Ux¯i,jRi/cBjiWjPBjβj+P0j,j∈B.
Sinceq¯j must be smaller than Qj according to subproblem (PXj), the combination x¯,q¯ is a feasible point in X×Q. Substituting (16) into problem (PX1), the utility value of problem (PX1) can be obtained, which equals η¯EEx¯. Similarly, substituting (13) into problem (PX1), the result is η¯EEx∗. Since x∗,q∗ is the global optimal solution of problem (PX1) in X×Q, it requires that η¯EEx¯≤η¯EEx∗ which contrasts (14). Therefore, x∗ must be a globally optimal association matrix for the EE optimization problem (PX).According to Theorem2, the nonconvex EE optimization problem in (2) can be reformulated as an equivalent optimization problem (PX1) involving the maximization of a biconcave function over X×Q, where Q⊆+RJ is a hyperrectangle.


## 3.2. The Second Mathematical Transformation Technique

Based on above discussions, the nonconvex problem (PX) can be reformulated as an equivalent biconcave problem. In this part, we will present another transformation technique which reformulates problem (PX) as a concave minimization framework.For eachj∈B, let Qj and qj be defined as before. For a given q, a new vector v=vj1×B is introduced, which is constrained as(17)V=v∈RB∣qj2⩽vj⩽Qj2,j∈B.Then, a utility function is formulated onQ×V as(18)
Y
q
,
v
=
min
x
∈
X
⁡
∑
j
∈
B
-
2
q
j
k
j
∑
i
∈
U
x
i
,
j
R
i
+
v
j
∑
i
∈
U
x
i
,
j
R
i
c
B
j
i
W
j
P
B
j
+
P
0
,
j
.Notice thatQ×V is a convex set. Furthermore, for each q¯,v¯∈Q×V, Yq¯,v¯ is the minimum value of a set of linear functions of (q,v) evaluated at q¯,v¯. Since linear functions are also concave functions, Y is a concave function on Q×V according to [21]. Based on the definition of Y function, we formulate a utility minimization problem as follows:(19)PX2min⁡q,vYq,vs.t.q∈Q,v∈V.Problem (PX2) involves the minimization of a concave functionY on the convex set Q×V, and it is an equivalent problem of the EE optimization problem (PX) in the aspects shown in Theorem 3.Theorem 3.
Ifq∗,v∗ is a globally optimal solution for problem (PX2), then x∗ is a globally optimal solution for problem (PX), where x∗ is any association matrix that achieves the minimum in (18) with q,v=q∗,v∗.Proof.
First, suppose thatq∗,v∗ is a globally optimal solution for problem (PX2) and x∗ achieves the minimum in (18) with q,v=q∗,v∗. Since in cellular networks the expressions kj∑i∈U‍xi,jRi and ∑i∈U‍(xi,jRi/cBjiWj)PBj+P0,j are always positive for each j∈B, to achieve the minimum of Y(q,v), the variable v should be assigned with a minimum value in V. Therefore, based on the definition of V, it holds that v∗=q∗2, and this implies that x∗ globally minimizes Yq∗,q∗2. It is equivalent to saying that (x∗,q∗) is the globally optimal solution for problem (PX1), which maximizes Ux,q. Therefore, x∗ is the globally optimal solution for problem (PX) according to Theorem 2.Based on above discussion, the nonconvex EE optimization problem (PX) can be reformulated as a concave minimization problem (PX2). This new property provides a new way to solve the original EE optimization problem. In addition, as proved in Theorem3, problem (PX2) can be further transformed to problem (PX1) by setting v=q2; hence our next focus is how to solve problem (PX1) by taking advantage of its biconcavity.


## 3.3. The Energy-Efficient Association Strategy

In this section, the biconcave problem (PX1) is solved by using the Alternate Convex Search (ACS) algorithm as in [20]. First, given a feasible association matrix x0∈X, the subproblem(20)S1:max⁡qUx,qs.t.q∈Q,x=x0=xi,j0U×Bis concave on Q and has a globally optimal solution represented as q0=qj01×B, where(21)qj0=kj∑i∈Uxi,j0Ri∑i∈Uxi,j0Ri/cBjiWjPBjβj+P0j,j∈B.The solutionx0,q0 is a feasible point in X×Q for problem (PX1). Similarly, given the q0, the subproblem(22)S2:max⁡xUx,qs.t.x∈X,q=q0is concave on X. To obtain the globally optimal solution of problem (S2), the dual theory is applied here. The duality gap is zeros since problem (S2) is concave. The Lagrange dual function for problem (S2) is formulated as(23)gα,β,λ=maxx∈X⁡Lx,α,β,λ=maxx∈X⁡∑j∈B2qj0kj∑i∈Uxi,jRi-qj02∑i∈Uxi,jRi/cBjiWjPBjβj+P0jB+∑j∈Bαj1-∑i∈Uxi,jRicBjiWj+∑j∈BβjRBHj-∑i∈Uxi,jRi+∑i∈Uλi1-∑j∈Bxi,j,where Lx,α,β,λ is the Lagrangian function and α=αj,j∈B⪰0,  β=βj,j∈B⪰0, and λ=λi,i∈U⪰0 are the dual variables for constraints (3), (4), and (5), respectively. The notation ⪰ is an element-wide operation. Lx,α,β,λ can be easily proved to be concave on x∈X, and the optimal solution x∗ to (23) is represented as(24)xi,j∗=0,τ0⩽0τ0,0<τ0<11,1⩽τ0,where τ0=qj02kjRi/γi+βjRiB+(αjRiB+qj02RiPBjβj)/cBjiWj2-∑m∈U∖i‍xm,j∗(Rm/Ri).Considering thatLx,α,β,λ is concave on X, the optimal association matrix for problem (S2) can be achieved by using the iterative coordinate search method in [21]. The explicit procedures are omitted here to save space. For simplicity of presentation, the solution of problem (S2) with input q0 is represented as x∗(q0)∈X. The dual problem is given as(25)D-S2mingα,β,λ=Lx∗q0,α,β,λs.t.α⪰0,β⪰0,λ⪰0.Obviously,Lx∗q0,α,β,λ is linear to α,β,λ. Hence, gα,β,λ is the maximum of linear function and the dual problem (D-S2) is always convex. Furthermore, the subgradient of gα,β,λ is presented as(26)Δαj=∑i∈Uxi,jRicBjiWj-1,Δβj=∑i∈Uxi,jRi-RBHj,Δλi=∑j∈Bxi,j-1.Then, problem (S2) can be solved by updatingα,β,λ via the ellipsoid method [21], of which the details are omitted here for brevity. Finally, the ACS algorithm is shown in Algorithm 1 at the next page. For simplicity, denote by xn∗ and qn∗ the solutions to problem (S1) and problem (S2) at the nth iteration, respectively.Algorithm 1:The Alternate Convex Search algorithm.
(1) Input:x0∈X, q0∈Q, CBjiu×B
(2) Initialize the maximum toleranceε, the maximum iteration number Nmax, the iteration index n=1,
x0∗=x0, and q0∗=q0.
(3)repeat  MainLoop
(4)  Calculate the optimalqn∗ by solving problem (S1) with input xn-1∗.
(5)  Calculate the optimalxn∗ by solving problem (S2) with input qn∗.
(6)if  Uxn∗,qn∗-Uxn-1∗,qn-1∗<ε
(7)then Convergence = true
(8)end if
(9)n=n+1
(10)until Convergence =  true or n>NmaxThe complexity of Algorithm1 is related with the value of ε. In each iteration, problem (S1) can be directly and optimally solved, while problem (S2) needs an inner loop to attain the optimal x∗ for a fixed q. The main operation expenditure of Algorithm 1 is equivalent to that of solving problem (S2), which is further equivalent to the complexity of solving (B×U) linear equations. Therefore, the complexity of Algorithm 1 is OB×U.Theorem 4.
The obtained sequenceUxn∗,qn∗n∈N generated by Algorithm 1 monotonically converges. Further, it holds that limn→∞xn∗-xn-1∗=0. (N denotes the set of nonnegative integers, and the notation · denotes the Euclidean norm of a matrix.)Proof.
Since the sequenceUxn∗,qn∗n∈N generated by Algorithm 1 is monotonically increasing and the function Ux,q is bounded from above, the sequence Uxn∗,qn∗n∈N converges to a finite value. Furthermore, suppose a feasible point x′,q′∈X×U. Since both problem (S1) with fixed x′ and problem (S2) with fixed q′ are convex and have a globally optimal solution, limn→∞xn∗-xn-1∗=0 holds according to Theorem  4.9 in [20].Although it has been proved in Theorem3 that both the sequence Uxn∗,qn∗n∈N and the sequence xn∗n∈N converge in finite iterations, the obtained xn∗ by Algorithm 1 is a partially optimal solution to problem (PX) instead of a globally optimal one.


## 4. Simulation

In this section, simulations are carried out to verify the effectiveness of Algorithm1. A macro-pico HetNet is considered, and the parameters of BSs are set as in [21], where, for pico BSs, PBj=1 W, Poj=6.8 W, and βj=4.7; for macro BSs, PBj=40 W, Poj=130 W, and βj=4. ∀j∈B, Wj=107 Hz. In addition, k1=k2=⋯=kB=1. The initialed value of the association matrix is set as x0=1/BU×B, that is, an average connection. We focus on the EE and the utility performances of a macro BS and several pico BSs.Figure2 shows how the network EE η¯EEx and the utility value U(x,q) change with respect to the iteration number in Algorithm 1. First, for both scenarios with ideal and nonideal backhaul, the EE lines and the utility lines monotonically increase with respect to the iteration number and match with each other in the end. The blue line represents the maximum EE value for the ideal backhaul scenario, where the optimal association matrix is obtained by a brute-force search. The solid lines of EE and the utility can gradually approach the optimal value as the iteration number increases, which verifies the effectiveness of Algorithm 1. In addition, as expected, nonideal backhaul can reduce the performance of network EE compared with the scenario with ideal backhaul.Figure 2
The network EE and the utility value of HetNets with respect to iteration number under ideal and nonideal backhaul scenarios.Figure3 shows how the EE and the utility value of individual pico BSs and macro BSs change with respect to the iteration number in Algorithm 1. First, as with Figure 2, all the dashed utility lines and solid EE lines of pico BSs and macro BSs match well when the iteration ends. Second, pico BSs perform much better than macro BSs in terms of EE, and their EE values are about 10 times larger than that of the macro BS. Third, it can be seen that, during the association, loads are transferred from macro BSs to pico BSs and among pico BSs. From the 2nd iteration to the 7th iteration, the EE values of the above three pico BSs’ lines almost do not change, while the EE of the macro BS decreases, and the EE of the below pico BS’s line increases. It indicates that the loads of the macro BS are transferred to the pico BS. From the 8th iteration to the 14th iteration, the EE of the macro BS remains the same, while the blue pico BS’s line continues to increase; the other pico BSs’ lines monotonically decrease. It indicates that loads are being transferred among pico BSs. Since the network EE can monotonically increase, the above results suggest that one simple energy-efficient association strategy is to transfer the loads of macro BSs to pico BSs as much as possible.Figure 3
The EE and utility value of pico BSs and macro BSs with respect to iteration number under ideal backhaul scenario.Figure4 presents the impact of the weight factors of macro BSs on the performance of the network EE. For both scenarios with ideal and nonideal backhaul, the network EE monotonically decreases as the weight factor of the macro BS increases. It further suggests that transferring loads from macro BSs to pico BSs is a promising approach to improve EE. For the blue line, the EE value at the point of k=5 is about 7 times larger than the EE value at the point of k=15. Therefore, a proper design of the weight factors can achieve a large gain of network EE.Figure 4
The network EE with respect to the weight factor of macro BSs under ideal and nonideal backhaul scenarios.


## 5. Conclusion

In this paper, we investigate the design of energy-efficient association strategy for hyperdense heterogeneous networking in the 5G cellular networks. The network EE is defined as average weighted EE of access nodes to characterize the feature that high-power macro BSs are mainly responsible for coverage while low-power small BSs undertake a majority of high-data rate services. The formulated EE optimization objective function is proved to be nonconvex. Two mathematical transformation techniques are presented to equivalently reformulate the original nonconvex problem as a biconcave maximization and a concave minimization problems, respectively. Furthermore, an iterative algorithm based on the properties of biconcave functions and dual theory is proposed to solve the biconcave problem. Simulation results indicate that transferring loads from macro BSs to small BSs can improve the network EE.



---

*Source: 686783-2015-07-27.xml*