# Lagrangian Dual Decomposition for Joint Resource Allocation Optimization Problem in OFDMA Downlink Networks

Authors: Li-Jun Jia; Yu-Cheng He; Dong-Hua Chen; Lin Zhou
Journal: Mathematical Problems in Engineering
 (2018)

---

## Abstract

This paper proposes an efficient method for joint power and subcarrier allocation in a multicell multiuser OFDMA downlink network. The joint optimization problem is formulated with the objective of maximizing the energy efficiency subject to the constraints on the quality of service in sum transmission rates for each cell and the total transmit power for the network. Due to intercell cochannel interferences and multiple variable coupling, the problem is intractable in its original form. To relax the difficulties in coordinating cochannel interferences, we introduce the tolerable interferences constraints for interference channels. To cope with the multiple variable coupling, we decompose the joint optimization problem into two iterative processes of user scheduling and a parametric convex optimization problem, where the energy efficiency is treated as the parameter and approached by bisection search. Then, by double dual decomposition, the parametric convex problem is transformed into Lagrangian dual problems at two levels of cells and subcarriers, and a decentralized solution is obtained in closed form. Based on the reformulations, an iterative subgradient algorithm is presented for approaching the joint optimization problem with acceptable complexity. Computer simulations are conducted to validate the proposed algorithm and examine the effects of various system parameters.


---

## Body

## 1. Introduction

As millions of base stations and billions of user terminals are expected to operate simultaneously and consume huge amounts of energy, energy efficiency is becoming an increasingly important issue in wireless communications in order to reduce operational expenditure and carbon dioxide emissions [1, 2]. In [3, 4], power allocation strategies were investigated for both single-cell and multicell systems under the assumption of perfect channel state information (CSI). In [5], a resource allocation scheme was proposed for improving energy efficiency under imperfect CSI conditions.The optimization of energy-efficient resource allocation usually appears as a nonconvex problem. The key issue in solving such a nonconvex problem is how to transform it into its convex alternative that can be solved with an acceptable complexity. For example, in [6], the energy-efficient power allocation problem for orthogonal frequency division multiplexing (OFDM) cognitive radio networks was transformed into a fractional programming problem [7]. Then, based on the fractional programming method, the energy-efficient power and subcarrier allocation scheme was proposed in [8] for multiuser OFDMA networks, where the requirements for quality of service (QoS) were not taken into account. However, simply improving the energy efficiency of the system may often degrade the QoS for users.It is worth mentioning that, in practical cellular systems, the QoS requirements usually provide an important specification to justify the resource allocation schemes. To ensure necessary QoS for users, the minimum transmission rate constraint was incorporated into the energy-efficient resource allocation problem in [9] for single-cell OFDMA systems. On the other hand, for multicell OFDMA systems, the optimal resource allocation problem presents an NP-hard problem [10] due to the existence of intercell interferences [11]. To relax the difficulty caused by intercell interferences, a tolerable interference (TI) constraint was introduced in [11, 12], whereas intercell interference coordination was investigated in [13]. Meanwhile, an interference-aware scheme was proposed in [14], and an iterative method was proposed in [15], both in a noncooperative way. An heuristic scheduling approach was also investigated in [16] in order to achieve trade-offs between QoS and throughout under the total power constraint.Motivated by the works above, we have also investigated the resource allocation problems for multicell multiuser systems. First, by using a universal multiuser interference channel model [17], we investigated the power minimization and sum rate maximization problems under the constraints on system power budget and individual users’ QoS requirements, while taking into account wireless power transfer and physical layer security. Then, upon extending the multiuser interference channel model to a multicell multiuser massive MIMO system [18], we investigated the resource allocation problems for guaranteeing individual users’ QoS requirements with causal time-splitting wireless power transfer. The core part of our previous works was to reformulate the originally intractable nonconvex optimization problems by using the mathematical tools of semidefinite relaxation (SDR) and S-procedure for convex approximation, and thus to design iterative successive convex approximation (SCA) algorithms for efficiently solving these problems.In this paper, we address an efficient iterative algorithm for solving the joint power and subcarrier allocation problem for multicell OFDMA downlink networks. Different from the works in [11–16], the proposed optimization scheme is aimed to maximize the energy efficiency under the total power constraint of the system, while ensuring the QoS requirements in terms of different minimum sum rates for each cell. To solve the resource allocation problem which is originally nonlinear and nonconvex, the following problem solving methods are considered:(1)
To circumvent the difficulties caused by intercell cochannel interferences, the maximum TI thresholds are introduced practically for each interference channel, which makes the original problem remarkably simplified.(2)
To decouple the optimization variables, the simplified resource allocation problem is decomposed into two iterative updating processes:
(a)
Subcarrier allocation based on optimal user scheduling.(b)
Power allocation based on a convex parametric problem using the energy efficiencyα as the parameter.Since the convex parametric problem is a strictly decreasing function ofα, the optimal α∗ is reached by converting the iterative updating processes into an efficient bisection search, during which the optimal solution to the resource allocation problem is accordingly obtained.(3)
To solve the convex parametric problem for givenα, the convex parametric problem is converted into Lagrangian dual problems at two levels and solved in the way of distributive closed-form computations as follows:
(a)
The Lagrangian dual problem at the first level comprises a master problem and an inner problem, the latter being decomposed into independent inner subproblems with respect to cells.(b)
Each inner subproblem from the first level is further rewritten as a master problem and an inner problem, the latter being decomposed into independent inner subproblems with respect to subcarriers. Then, each inner subproblem at the second level has an optimal solution that can be analytically determined.According to the derivations and reformulations, the iterative algorithm, based on a bisection search in combination with the subgradient method, is presented for solving the joint resource allocation problem. Computer simulations are conducted to validate the proposed algorithm and examine its performance under various system settings.In the remainder of the paper, Section2 presents the system model together with the problem formulation, Section 3 presents the problem reformulations and the iterative algorithm, and Section 4 demonstrates simulation results to validate the iterative algorithm and examine its performances. Finally, the paper is concluded by Section 5.


## 2. System Model

Consider a multicell multiuser OFDMA downlink network composed ofN cells. Each cell n∈N={1,2,…,N} consists of a base station (BS) and Kn users Kn={1,2,…,Kn}. During each time interval, all the BS’s transmit signals to the users in respective cells simultaneously over the same set of orthogonal subcarriers M={1,2,…,M}.Figure1 shows the channel model, where gn,knm is the transmission channel power gain from BS n to user kn over subcarrier m, and gj,knm is the intercell interference channel power gain from BS j∈N∖n to user kn over subcarrier m. Note that N∖n denotes the subset of N with the element n excluded. Specifically, knm represents the user of cell n that will be scheduled to work on subcarrier m.Figure 1
The channel model demonstrated with two cellsn and j.Letpnm be the transmit power allocated to user kn∈Kn working on subcarrier m∈M in cell n∈N. Then, the signal-to-interference-plus-noise ratio (SINR) at this user is given by(1)γn,knm=pnmgn,knm∑j≠nNpjmgj,knm+σn,kn2where σn,kn2 is the associated additive white Gaussian noise (AWGN) power.Letan,knm be the subcarrier allocation indicator, i.e., an,knm=1 if user kn is scheduled for subcarrier m, and an,knm=0 otherwise. Then, the achievable transmission rate over the subcarrier is given by(2)Rnm=∑kn=1Knan,knmlog21+γn,knmand the sum rate over all subcarriers in cell n is given by Rn=∑m=1MRnm.For system design, denote the power allocation matrix byP=p1,p2,…,pN with column vectors pn=(pnm)M×1, and denote the subcarrier allocation matrix by A=A1,A2,…,AN with submatrices An=(an,knm)M×Kn, where n∈N. Let Rminn be the minimum sum rate in cell n that measures the QoS requirement of the cell. Let Pmax be the total transmit power threshold, and let Pc be the constant total circuit power consumption independent of the transmission power. With the objective of maximizing the energy efficiency, the joint resource allocation problem is formulated, under the constraints on the total transmit power of the system and the QoS requirements of all cells, as(3)maxA,Pρ=∑n=1NRn∑n=1N∑m=1Mpnm+Pc(4)s.t.C1:∑n=1N∑m=1Mpnm≤PmaxC2:pnm≥0C3:Rn≥RminnC4:∑kn=1Knan,knm≤1forn∈Nandm∈Mwhere ρ is defined as the energy efficiency of the system in “bit/Hz/Joule” [19], C1 and C2 represent the transmit power constraints, C3 represents the QoS constraints for each cell, and C4 indicates that each subcarrier in a cell can either be allocated exclusively to a user or stay idle depending upon user scheduling. Due to the coupling of the optimization variables pnm and an,knm in the objective function, the problem is nonlinear and nonconcave and thus is intractable in its original form.Remark 1.
In the QoS constraintsC3, Rminn can be chosen distinctly for different cells. Furthermore, C3 can also be defined as Rnm≥Rn,minm by using Rn,minm to measure the QoS requirements of individual users.


## 3. Problem Reformulations and Solving Algorithm

In this section, problem (3) is first relaxed by introducing TIs to cope with intercell cochannel interferences, and the resultant problem is then decomposed into a user scheduling problem and a conditional power allocation problem that can be solved in an iterative manner. By using the energy efficiency α as the parameter, the conditional power allocation problem is converted into a convex parametric problem. This strategy makes the joint optimization problem solvable by a bisection search for the parameter α in combination with two-level iterative updates derived from double dual decomposition.


### 3.1. Problem Relaxation by Introducing TIs

To relax the difficulties caused by intercell cochannel interferences [12], it is practical to introduce a set of preset thresholds {ηj,nm:j∈N∖n} for each pair (n,m), where ηj,nm represents the TI from cell j to cell n over subcarrier m. Thus, under the constraints pjmgj,knm≤ηj,nm, we obtain from (2) a lower bound on Rnm as(5)R¯nm=∑kn=1Knan,knmlog21+pnmgn,knmIn,knmwhere In,knm=∑j≠nNηj,nm+σn,kn2 becomes a constant for any triple (n,m,kn).LetR¯n=∑m=1MR¯nm. Then, we simplify problem (3) as(6)maxA,Pα=∑n=1NR¯n∑n=1N∑m=1Mpnm+Pc(7)s.t.C1,C2C4:∑kn=1Knan,knm≤1C5:R¯n≥RminnC6:pnmgn,kjm≤ηn,jmforn∈N,m∈M,andj∈N∖nwhere α is defined as the lower bound on the energy efficiency ρ, C5 can be viewed as a constricted form of C3, and C6 represents the newly added power constraints on pnm because of TIs.


### 3.2. Iterative Processes of Subcarrier Allocation and Power Allocation

Consider now the subcarrier allocation by means of user scheduling. To maximize local energy efficiencies and hence the global one, the optimal user scheduling rule can be expressed as a function of power allocationP below(8)knmP=argmaxkn∈Knlog21+γn,knmpnm+pc,nmwhere pc,nm is the associated circuit power such that ∑n=1N∑m=1Mpc,nm=Pc.Therefore, given any power allocationP, the optimal user scheduling rule reduces to(9)knm=argmaxkn∈Knγn,knmthus yielding the optimal subcarrier allocation A with an,knmm=1, and an,knm=0 for all kn∈Kn∖knm.Conversely, given a subcarrier allocationA, the constraint C4 in problem (6) is resolved, and hence we need to solve a conditional power allocation problem(10)maxPα=∑n=1NR¯n∑n=1N∑m=1Mpnm+Pc(11)s.t.C1,C2C5:R¯n≥RminnC6:pnmgn,kjmm≤ηn,jmforn∈N,m∈M,andj∈N∖nwhere R¯nm is simplified from (5) as(12)R¯nm=log21+pnmgn,knmmIn,knmm.Based on the reformulations above, the joint resource allocation in problem (6) is solvable by iteratively performing updates in (9) and (10). When P converges to the optimal P∗, A must also converges to the optimal A∗, while the maximized objective function in (10) yields the optimal energy efficiency α=α∗.Now that problem (10) remains nonconvex and difficult to directly solve. Fortunately, it is solvable by fraction programming [20]. To do this, we transform it into a convex parametric problem as(13)Fα≜maxPfP,α=∑n=1NR¯n-α∑n=1N∑m=1Mpnm+Pc(14)s.t.C1,C2,C5,C6where α>0 is treated as the positive parameter and f(P,α) is a strictly concave function of P since it strictly holds that the second partial derivatives ∂2f/∂(pnm)2<0 for all pnm.Let us discuss the equivalence between (10) and (13) as follows. It is observed that maximizing α in (10) is essentially equivalent to maximizing the numerator therein while minimizing the denominator of the fraction. The optimal point α=α∗ just reaches the best tradeoff between the maximizing and minimizing operations under the convex constraints. In (13), the intention is reflected by maximizing f(P,α) which expresses the fraction of (10) in the difference form. Therefore, the optimal solutions A∗ and P∗ to problem (6) can be equivalently approached by iterations between (9) and (13), for which the optimal α∗ turns out to be the root of the nonlinear equation F(α)=0 [6].Clearly,F(α) is a strictly decreasing function of α. There exists a feasible range (αl,αh) such that 0<αl<α∗<αh. It follows that F(α)>0 if α∈(αl,α∗), and F(α)<0 if α∈(α∗,αh). These properties imply an efficient bisection search for the root α∗, and the feasible range can be determined loosely from (10) as(15a)αl=1Pmax+Pc∑n=1NRminn(15b)αh=1Pc∑n=1N∑m=1Mlog21+PmaxNM·gn,knmmIn,knmm.


### 3.3. Double Dual Decomposition for Solving the Convex Parametric Problem

In this subsection, we cope with the parametric convex problem (13) with the parameter α by exploiting Lagrangian dualities at two levels with respect to cells and subcarriers, respectively.


#### 3.3.1. Dual Decomposition at the First Level regarding Cells

To address the total power constraintC1, we introduce a nonnegative dual variable λ, define a Lagrangian function g(α,λ,P), and convert problem (13) into a Lagrangian dual problem as follows:(16a)Fα=minλ≥0Gα,λ(16b)Gα,λ=maxPgα,λ,P(16c)s.t.C2,C5,C6gα,λ,P=fP,α+λPmax-∑n=1N∑m=1Mpnm=∑n=1NR¯n-α+λ∑m=1Mpnm+λPmax-αPcwhere the master problem (16a) explores the optimal λ while seeking to minimize G(α,λ), whereas the inner problem (16b) explores the optimal P so as to provide G(α,λ) as a candidate upper bound of F(α) for given {α,λ}.Since the itemλPmax-αPc in (16c) is irrelevant to P, it can be moved to the objective function of the master problem (16a). By decomposing the remaining summation item in (16c), we can reformulate the dual problem above into a master problem and N independent inner subproblems as follows:(17a)Fα=minλ≥0∑n=1NGnα,λ+λPmax-αPc(17b)Gnα,λ=maxpnR¯n-α+λ∑m=1Mpnm(18)s.t.C2n:pnm≥0C5n:R¯n≥RminnC6n:pnmgn,kjmm≤ηn,jmform∈Mandj∈N∖n.where subproblem (17b) for each n∈N turns to explore pn while seeking to maximize Gn(α,λ) under the related constraints.The optimal value forλ that minimizes the objective function of (17a) can be approached by applying the heuristic subgradient method [20](19)λt1+1=λt1-ΔPmax-∑n=1N∑m=1Mpnmt1+where [·]+=max{·,0}, t1 denotes the iteration index, the expression enclosed in the parentheses is the derived subgradient, and Δ is a positive constant specified as the searching step size. As t1 grows, λ[t1] will reach the optimal point when P converges to some fixed point conditioned on the given α.


#### 3.3.2. Dual Decomposition at the First Level regarding Subcarriers

To solve the subproblem (17b) given {α,λ,n}, we introduce a dual variable μn>0 and a set of dual variables {φn,jm>0:m∈M,j∈N∖n} to resolve the constraints C5n and C6n, respectively. For notation convenience, let Φn=(φn1,φn2,…,φnM) and φnm=(φn,jm:j≠n)(N-1)×1. By defining a Lagrangian function hn(α,λ,μn,Φn,pn), subproblem (17b) can be converted into a dual problem(20a)Gnα,λ=minμn,ΦnHnα,λ,μn,Φn(20b)Hnα,λ,μn,Φn=maxpnhnα,λ,μn,Φn,pn(20c)s.t.pnm≥0,m∈Mhnα,λ,μn,Φn,pn=R¯n-α+λ∑m=1Mpnm+μnR¯n-Rminn+∑j≠nN∑m=1Mφn,jmηn,jm-pnmgn,kjmm=∑m=1M1+μnR¯nm-pnmα+λ+∑j≠nNφn,jmgn,kjmm-μnRminn+∑j≠nN∑m=1Mφn,jmηn,jm.Similarly, the item-μnRminn+∑j≠nN∑m=1Mφn,jmηn,jm on the last line of (20c) is irrelevant to pn, whereas each bracketed summand in the first summation of (20c) is related to a unique pnm for m∈M. Therefore, we can rewrite the dual problem expressed by (20a)–(20c) into the form of a master problem connected with M independent inner subproblems as follows:(21a)Gnα,λ=minμn,Φn∑m=1MHnmα,λ,μn,φnm-μnRminn+∑j≠nN∑m=1Mφn,jmηn,jm(21b)Hnmα,λ,μn,φnm=maxpnmhmα,λ,μn,φnm,pnm(21c)s.t.pnm≥0hnmα,λ,μn,φnm,pnm=1+μnlog21+pnmgn,knmmIn,knmm-pnmα+λ+∑j≠nNφn,jmgn,kjmmwhere the master problem (21a) seeks to optimize μn,Φn while achieving the least upper bound Gn(α,λ) with {α,λ,n} given and subproblem 16b seeks to maximize hnmα,λ,μn,φnm,pnm by finding the optimal pnm≥0 with {α,λ,n,m,μn,φnm} given.It is readily shown thathnmα,λ,μn,φnm,pnm is a strictly concave function of pnm as it is differentiable with the strictly negative second derivative ∂2hnm/∂(pnm)2<0 existing in the real domain. By taking the first derivative ∂hnm/∂pnm and letting it be zero, the maximum point for pnm≥0 is derived as(22)pnm∗=1+μnα+λ+∑j≠nNφn,jmgn,kjmmln⁡2-In,knmmgn,knmm+thus yielding the optimal solution to subproblem (21b) as(23)Hnmα,λ,μn,φnm=hnmα,λ,μn,φnm,pnm∗.By substituting solution (23), the master problem (21a) for each n can be solved by using the heuristic subgradient method in the following form:(24a)μnt2+1=μnt2-ΔR¯nt2-Rminn+(24b)φn,jmt2+1=φn,jmt2-Δηn,jm-pnmt2gn,kjmm+where t2 indexes the iterations at the second level, and the expressions enclosed in the parentheses are the derived subgradients, and Δ is the same searching step size as in (19). As t2 grows, the dual variables in μn[t2],Φn[t2] will reach their optimal values when P updated by (22) converges to a fixed point for given α,λ,n.


### 3.4. Iterative Algorithm for Solving Problem

Figure2 shows a framework for solving the concave parametric problem (13) based on the double dual decomposition above. Given a value of α, F(α) in (17a) is minimized by exploring λ while demanding Gn(α,λ):n∈N from (21a). Given any instance of (α,λ), each Gn(α,λ) in (21a) is minimized by exploring μn,φnm:m∈M while demanding Hnm(α,λ,μn,φnm):m∈M from (21b). Given an instance of (α,λ,μn,φnm), the optimal pnm and hence Hnm are computed by (22) and (23), respectively. By using the heuristic subgradient methods based on (19) and (24a), (24b), the concave parametric problem (13) is gradually approached by two-level iterations running over (17a) and (21a).Figure 2
Problem solving framework of two-level iterations based on double dual decomposition.The iterative algorithm for solving the joint resource allocation problem (6) is presented in Algorithm 1, which mainly comprises three loops of “repeat-until” as follows:(i)
Loop 1, including lines 2–34, performs the bisection search for α in the range (αl,αh) given by (15a) and (15b), where the exiting condition is expressed as |F(α)|2≤ε, and ε is the accuracy.(ii)
Loop 2, including lines 6–27, performs the subgradient search for λ according to (19), while updating F(α) with the results of Gn:n∈N fromLoop 3 below, where the exiting condition is expressed as δ1≤ε, and δ1 is the mean squared error (MSE) metric defined as(25)δ1Pt1+1,Pt1=1NM∑n=1N∑m=1Mpnmt1+1-pnmt12.(iii)
Loop 3, including lines 11–21, performs the subgradient search for μn and Φn according to (24a) and (24b), while updating {Gn:n∈N} with the results of pnm,Hnm:m∈M from (22) and (23), where the exiting condition is expressed as δ2≤ε, and δ2 is the MSE metric defined as(26)δ2pnt2+1,pnt2=1M∑m=1Mpnmt2+1-pnmt22.Algorithm 1:Iterative algorithm for solving problem (6).
Input:  N,M,{Kn,Rminn,ηn,jm:n∈N,m∈M,j∈N∖n},Pmax,αl,αh,λ0,μ0,φ0,Δ,ε Output:  the subcarrier allocation A, and the power allocation P 1:pnm[0]←Pmax/(NM) for n∈N and m∈M 2:repeat  ∖∗ the bisection search for α∗∗∖ 3:update A by (9) with P[0] 4:α←(αl+αh)/2 5:t1←0,F(α)←∞,λ←λ0 6:repeat  ∖∗ the search for λ∗∖ 7:P′[0]←P[t1] 8:for  n=1  to  N  do 9:t2←0, Gn←∞, μn[0]←μ0 10:φn,jm[0]←φ0 for m∈M and j∈N∖n 11:repeat  ∖∗ the search for μn,Φn∗∖ 12:for  m=1  to  M  do 13:compute pnm∗ by (22) with {α,λ[t1],μn[t2],φnm[t2]} 14:compute Hnm by (23) with {α,λ[t1],μn[t2],φnm[t2],pnm∗} 15:end for 16:update Gn by (21a) with {μn[t2],φnm[t2],Hnm:m∈M} 17:t2←t2+1 18:pn′[t2]←{pnm∗:m∈M} 19:update μn[t2] by (24a) with pn′[t2] 20:update {φn,jm[t2]:m∈M,j∈N∖n} by (24b) with pn′[t2] 21:until  δ2pn′[t2],pn′[t2-1]≤ε 22:end for 23:update F(α) by (17a) with {α,λ[t1],Gn:n∈N} 24:t1←t1+1 25:P[t1]←P′[t2] 26:update λ[t1] by (19) with P[t1] 27:until  δ1(P[t1],P[t1-1])≤ε 28:if  F(α)>0  then 29:αl=α 30:else if  F(α)<0  then 31:αh=α 32:end if 33:P[0]←P[t1]) 34:until  |F(α)|2≤ε 35:return  A,P[0]We briefly analyze the computational complexity of the algorithm. By (9), the subcarrier allocation yields a complexity of order O∑n=1NKnM. For power allocation, there are NM optimization variables pnm in P, one dual variable λ in (17a), and 1+(N-1)M dual variables μn and φn,jm in Φn for each n in (21a). Thus, the power allocation yields a complexity of order O(N2M+N+1). To achieve the accuracy ε for the bisection search, the computational complexity is estimated of polynomial order O∑n=1NKnM+N2M+N+1log2(1/ε) in the network scale parameters and thus acceptable for practical applications.


## 3.1. Problem Relaxation by Introducing TIs

To relax the difficulties caused by intercell cochannel interferences [12], it is practical to introduce a set of preset thresholds {ηj,nm:j∈N∖n} for each pair (n,m), where ηj,nm represents the TI from cell j to cell n over subcarrier m. Thus, under the constraints pjmgj,knm≤ηj,nm, we obtain from (2) a lower bound on Rnm as(5)R¯nm=∑kn=1Knan,knmlog21+pnmgn,knmIn,knmwhere In,knm=∑j≠nNηj,nm+σn,kn2 becomes a constant for any triple (n,m,kn).LetR¯n=∑m=1MR¯nm. Then, we simplify problem (3) as(6)maxA,Pα=∑n=1NR¯n∑n=1N∑m=1Mpnm+Pc(7)s.t.C1,C2C4:∑kn=1Knan,knm≤1C5:R¯n≥RminnC6:pnmgn,kjm≤ηn,jmforn∈N,m∈M,andj∈N∖nwhere α is defined as the lower bound on the energy efficiency ρ, C5 can be viewed as a constricted form of C3, and C6 represents the newly added power constraints on pnm because of TIs.


## 3.2. Iterative Processes of Subcarrier Allocation and Power Allocation

Consider now the subcarrier allocation by means of user scheduling. To maximize local energy efficiencies and hence the global one, the optimal user scheduling rule can be expressed as a function of power allocationP below(8)knmP=argmaxkn∈Knlog21+γn,knmpnm+pc,nmwhere pc,nm is the associated circuit power such that ∑n=1N∑m=1Mpc,nm=Pc.Therefore, given any power allocationP, the optimal user scheduling rule reduces to(9)knm=argmaxkn∈Knγn,knmthus yielding the optimal subcarrier allocation A with an,knmm=1, and an,knm=0 for all kn∈Kn∖knm.Conversely, given a subcarrier allocationA, the constraint C4 in problem (6) is resolved, and hence we need to solve a conditional power allocation problem(10)maxPα=∑n=1NR¯n∑n=1N∑m=1Mpnm+Pc(11)s.t.C1,C2C5:R¯n≥RminnC6:pnmgn,kjmm≤ηn,jmforn∈N,m∈M,andj∈N∖nwhere R¯nm is simplified from (5) as(12)R¯nm=log21+pnmgn,knmmIn,knmm.Based on the reformulations above, the joint resource allocation in problem (6) is solvable by iteratively performing updates in (9) and (10). When P converges to the optimal P∗, A must also converges to the optimal A∗, while the maximized objective function in (10) yields the optimal energy efficiency α=α∗.Now that problem (10) remains nonconvex and difficult to directly solve. Fortunately, it is solvable by fraction programming [20]. To do this, we transform it into a convex parametric problem as(13)Fα≜maxPfP,α=∑n=1NR¯n-α∑n=1N∑m=1Mpnm+Pc(14)s.t.C1,C2,C5,C6where α>0 is treated as the positive parameter and f(P,α) is a strictly concave function of P since it strictly holds that the second partial derivatives ∂2f/∂(pnm)2<0 for all pnm.Let us discuss the equivalence between (10) and (13) as follows. It is observed that maximizing α in (10) is essentially equivalent to maximizing the numerator therein while minimizing the denominator of the fraction. The optimal point α=α∗ just reaches the best tradeoff between the maximizing and minimizing operations under the convex constraints. In (13), the intention is reflected by maximizing f(P,α) which expresses the fraction of (10) in the difference form. Therefore, the optimal solutions A∗ and P∗ to problem (6) can be equivalently approached by iterations between (9) and (13), for which the optimal α∗ turns out to be the root of the nonlinear equation F(α)=0 [6].Clearly,F(α) is a strictly decreasing function of α. There exists a feasible range (αl,αh) such that 0<αl<α∗<αh. It follows that F(α)>0 if α∈(αl,α∗), and F(α)<0 if α∈(α∗,αh). These properties imply an efficient bisection search for the root α∗, and the feasible range can be determined loosely from (10) as(15a)αl=1Pmax+Pc∑n=1NRminn(15b)αh=1Pc∑n=1N∑m=1Mlog21+PmaxNM·gn,knmmIn,knmm.


## 3.3. Double Dual Decomposition for Solving the Convex Parametric Problem

In this subsection, we cope with the parametric convex problem (13) with the parameter α by exploiting Lagrangian dualities at two levels with respect to cells and subcarriers, respectively.


### 3.3.1. Dual Decomposition at the First Level regarding Cells

To address the total power constraintC1, we introduce a nonnegative dual variable λ, define a Lagrangian function g(α,λ,P), and convert problem (13) into a Lagrangian dual problem as follows:(16a)Fα=minλ≥0Gα,λ(16b)Gα,λ=maxPgα,λ,P(16c)s.t.C2,C5,C6gα,λ,P=fP,α+λPmax-∑n=1N∑m=1Mpnm=∑n=1NR¯n-α+λ∑m=1Mpnm+λPmax-αPcwhere the master problem (16a) explores the optimal λ while seeking to minimize G(α,λ), whereas the inner problem (16b) explores the optimal P so as to provide G(α,λ) as a candidate upper bound of F(α) for given {α,λ}.Since the itemλPmax-αPc in (16c) is irrelevant to P, it can be moved to the objective function of the master problem (16a). By decomposing the remaining summation item in (16c), we can reformulate the dual problem above into a master problem and N independent inner subproblems as follows:(17a)Fα=minλ≥0∑n=1NGnα,λ+λPmax-αPc(17b)Gnα,λ=maxpnR¯n-α+λ∑m=1Mpnm(18)s.t.C2n:pnm≥0C5n:R¯n≥RminnC6n:pnmgn,kjmm≤ηn,jmform∈Mandj∈N∖n.where subproblem (17b) for each n∈N turns to explore pn while seeking to maximize Gn(α,λ) under the related constraints.The optimal value forλ that minimizes the objective function of (17a) can be approached by applying the heuristic subgradient method [20](19)λt1+1=λt1-ΔPmax-∑n=1N∑m=1Mpnmt1+where [·]+=max{·,0}, t1 denotes the iteration index, the expression enclosed in the parentheses is the derived subgradient, and Δ is a positive constant specified as the searching step size. As t1 grows, λ[t1] will reach the optimal point when P converges to some fixed point conditioned on the given α.


### 3.3.2. Dual Decomposition at the First Level regarding Subcarriers

To solve the subproblem (17b) given {α,λ,n}, we introduce a dual variable μn>0 and a set of dual variables {φn,jm>0:m∈M,j∈N∖n} to resolve the constraints C5n and C6n, respectively. For notation convenience, let Φn=(φn1,φn2,…,φnM) and φnm=(φn,jm:j≠n)(N-1)×1. By defining a Lagrangian function hn(α,λ,μn,Φn,pn), subproblem (17b) can be converted into a dual problem(20a)Gnα,λ=minμn,ΦnHnα,λ,μn,Φn(20b)Hnα,λ,μn,Φn=maxpnhnα,λ,μn,Φn,pn(20c)s.t.pnm≥0,m∈Mhnα,λ,μn,Φn,pn=R¯n-α+λ∑m=1Mpnm+μnR¯n-Rminn+∑j≠nN∑m=1Mφn,jmηn,jm-pnmgn,kjmm=∑m=1M1+μnR¯nm-pnmα+λ+∑j≠nNφn,jmgn,kjmm-μnRminn+∑j≠nN∑m=1Mφn,jmηn,jm.Similarly, the item-μnRminn+∑j≠nN∑m=1Mφn,jmηn,jm on the last line of (20c) is irrelevant to pn, whereas each bracketed summand in the first summation of (20c) is related to a unique pnm for m∈M. Therefore, we can rewrite the dual problem expressed by (20a)–(20c) into the form of a master problem connected with M independent inner subproblems as follows:(21a)Gnα,λ=minμn,Φn∑m=1MHnmα,λ,μn,φnm-μnRminn+∑j≠nN∑m=1Mφn,jmηn,jm(21b)Hnmα,λ,μn,φnm=maxpnmhmα,λ,μn,φnm,pnm(21c)s.t.pnm≥0hnmα,λ,μn,φnm,pnm=1+μnlog21+pnmgn,knmmIn,knmm-pnmα+λ+∑j≠nNφn,jmgn,kjmmwhere the master problem (21a) seeks to optimize μn,Φn while achieving the least upper bound Gn(α,λ) with {α,λ,n} given and subproblem 16b seeks to maximize hnmα,λ,μn,φnm,pnm by finding the optimal pnm≥0 with {α,λ,n,m,μn,φnm} given.It is readily shown thathnmα,λ,μn,φnm,pnm is a strictly concave function of pnm as it is differentiable with the strictly negative second derivative ∂2hnm/∂(pnm)2<0 existing in the real domain. By taking the first derivative ∂hnm/∂pnm and letting it be zero, the maximum point for pnm≥0 is derived as(22)pnm∗=1+μnα+λ+∑j≠nNφn,jmgn,kjmmln⁡2-In,knmmgn,knmm+thus yielding the optimal solution to subproblem (21b) as(23)Hnmα,λ,μn,φnm=hnmα,λ,μn,φnm,pnm∗.By substituting solution (23), the master problem (21a) for each n can be solved by using the heuristic subgradient method in the following form:(24a)μnt2+1=μnt2-ΔR¯nt2-Rminn+(24b)φn,jmt2+1=φn,jmt2-Δηn,jm-pnmt2gn,kjmm+where t2 indexes the iterations at the second level, and the expressions enclosed in the parentheses are the derived subgradients, and Δ is the same searching step size as in (19). As t2 grows, the dual variables in μn[t2],Φn[t2] will reach their optimal values when P updated by (22) converges to a fixed point for given α,λ,n.


## 3.3.1. Dual Decomposition at the First Level regarding Cells

To address the total power constraintC1, we introduce a nonnegative dual variable λ, define a Lagrangian function g(α,λ,P), and convert problem (13) into a Lagrangian dual problem as follows:(16a)Fα=minλ≥0Gα,λ(16b)Gα,λ=maxPgα,λ,P(16c)s.t.C2,C5,C6gα,λ,P=fP,α+λPmax-∑n=1N∑m=1Mpnm=∑n=1NR¯n-α+λ∑m=1Mpnm+λPmax-αPcwhere the master problem (16a) explores the optimal λ while seeking to minimize G(α,λ), whereas the inner problem (16b) explores the optimal P so as to provide G(α,λ) as a candidate upper bound of F(α) for given {α,λ}.Since the itemλPmax-αPc in (16c) is irrelevant to P, it can be moved to the objective function of the master problem (16a). By decomposing the remaining summation item in (16c), we can reformulate the dual problem above into a master problem and N independent inner subproblems as follows:(17a)Fα=minλ≥0∑n=1NGnα,λ+λPmax-αPc(17b)Gnα,λ=maxpnR¯n-α+λ∑m=1Mpnm(18)s.t.C2n:pnm≥0C5n:R¯n≥RminnC6n:pnmgn,kjmm≤ηn,jmform∈Mandj∈N∖n.where subproblem (17b) for each n∈N turns to explore pn while seeking to maximize Gn(α,λ) under the related constraints.The optimal value forλ that minimizes the objective function of (17a) can be approached by applying the heuristic subgradient method [20](19)λt1+1=λt1-ΔPmax-∑n=1N∑m=1Mpnmt1+where [·]+=max{·,0}, t1 denotes the iteration index, the expression enclosed in the parentheses is the derived subgradient, and Δ is a positive constant specified as the searching step size. As t1 grows, λ[t1] will reach the optimal point when P converges to some fixed point conditioned on the given α.


## 3.3.2. Dual Decomposition at the First Level regarding Subcarriers

To solve the subproblem (17b) given {α,λ,n}, we introduce a dual variable μn>0 and a set of dual variables {φn,jm>0:m∈M,j∈N∖n} to resolve the constraints C5n and C6n, respectively. For notation convenience, let Φn=(φn1,φn2,…,φnM) and φnm=(φn,jm:j≠n)(N-1)×1. By defining a Lagrangian function hn(α,λ,μn,Φn,pn), subproblem (17b) can be converted into a dual problem(20a)Gnα,λ=minμn,ΦnHnα,λ,μn,Φn(20b)Hnα,λ,μn,Φn=maxpnhnα,λ,μn,Φn,pn(20c)s.t.pnm≥0,m∈Mhnα,λ,μn,Φn,pn=R¯n-α+λ∑m=1Mpnm+μnR¯n-Rminn+∑j≠nN∑m=1Mφn,jmηn,jm-pnmgn,kjmm=∑m=1M1+μnR¯nm-pnmα+λ+∑j≠nNφn,jmgn,kjmm-μnRminn+∑j≠nN∑m=1Mφn,jmηn,jm.Similarly, the item-μnRminn+∑j≠nN∑m=1Mφn,jmηn,jm on the last line of (20c) is irrelevant to pn, whereas each bracketed summand in the first summation of (20c) is related to a unique pnm for m∈M. Therefore, we can rewrite the dual problem expressed by (20a)–(20c) into the form of a master problem connected with M independent inner subproblems as follows:(21a)Gnα,λ=minμn,Φn∑m=1MHnmα,λ,μn,φnm-μnRminn+∑j≠nN∑m=1Mφn,jmηn,jm(21b)Hnmα,λ,μn,φnm=maxpnmhmα,λ,μn,φnm,pnm(21c)s.t.pnm≥0hnmα,λ,μn,φnm,pnm=1+μnlog21+pnmgn,knmmIn,knmm-pnmα+λ+∑j≠nNφn,jmgn,kjmmwhere the master problem (21a) seeks to optimize μn,Φn while achieving the least upper bound Gn(α,λ) with {α,λ,n} given and subproblem 16b seeks to maximize hnmα,λ,μn,φnm,pnm by finding the optimal pnm≥0 with {α,λ,n,m,μn,φnm} given.It is readily shown thathnmα,λ,μn,φnm,pnm is a strictly concave function of pnm as it is differentiable with the strictly negative second derivative ∂2hnm/∂(pnm)2<0 existing in the real domain. By taking the first derivative ∂hnm/∂pnm and letting it be zero, the maximum point for pnm≥0 is derived as(22)pnm∗=1+μnα+λ+∑j≠nNφn,jmgn,kjmmln⁡2-In,knmmgn,knmm+thus yielding the optimal solution to subproblem (21b) as(23)Hnmα,λ,μn,φnm=hnmα,λ,μn,φnm,pnm∗.By substituting solution (23), the master problem (21a) for each n can be solved by using the heuristic subgradient method in the following form:(24a)μnt2+1=μnt2-ΔR¯nt2-Rminn+(24b)φn,jmt2+1=φn,jmt2-Δηn,jm-pnmt2gn,kjmm+where t2 indexes the iterations at the second level, and the expressions enclosed in the parentheses are the derived subgradients, and Δ is the same searching step size as in (19). As t2 grows, the dual variables in μn[t2],Φn[t2] will reach their optimal values when P updated by (22) converges to a fixed point for given α,λ,n.


## 3.4. Iterative Algorithm for Solving Problem

Figure2 shows a framework for solving the concave parametric problem (13) based on the double dual decomposition above. Given a value of α, F(α) in (17a) is minimized by exploring λ while demanding Gn(α,λ):n∈N from (21a). Given any instance of (α,λ), each Gn(α,λ) in (21a) is minimized by exploring μn,φnm:m∈M while demanding Hnm(α,λ,μn,φnm):m∈M from (21b). Given an instance of (α,λ,μn,φnm), the optimal pnm and hence Hnm are computed by (22) and (23), respectively. By using the heuristic subgradient methods based on (19) and (24a), (24b), the concave parametric problem (13) is gradually approached by two-level iterations running over (17a) and (21a).Figure 2
Problem solving framework of two-level iterations based on double dual decomposition.The iterative algorithm for solving the joint resource allocation problem (6) is presented in Algorithm 1, which mainly comprises three loops of “repeat-until” as follows:(i)
Loop 1, including lines 2–34, performs the bisection search for α in the range (αl,αh) given by (15a) and (15b), where the exiting condition is expressed as |F(α)|2≤ε, and ε is the accuracy.(ii)
Loop 2, including lines 6–27, performs the subgradient search for λ according to (19), while updating F(α) with the results of Gn:n∈N fromLoop 3 below, where the exiting condition is expressed as δ1≤ε, and δ1 is the mean squared error (MSE) metric defined as(25)δ1Pt1+1,Pt1=1NM∑n=1N∑m=1Mpnmt1+1-pnmt12.(iii)
Loop 3, including lines 11–21, performs the subgradient search for μn and Φn according to (24a) and (24b), while updating {Gn:n∈N} with the results of pnm,Hnm:m∈M from (22) and (23), where the exiting condition is expressed as δ2≤ε, and δ2 is the MSE metric defined as(26)δ2pnt2+1,pnt2=1M∑m=1Mpnmt2+1-pnmt22.Algorithm 1:Iterative algorithm for solving problem (6).
Input:  N,M,{Kn,Rminn,ηn,jm:n∈N,m∈M,j∈N∖n},Pmax,αl,αh,λ0,μ0,φ0,Δ,ε Output:  the subcarrier allocation A, and the power allocation P 1:pnm[0]←Pmax/(NM) for n∈N and m∈M 2:repeat  ∖∗ the bisection search for α∗∗∖ 3:update A by (9) with P[0] 4:α←(αl+αh)/2 5:t1←0,F(α)←∞,λ←λ0 6:repeat  ∖∗ the search for λ∗∖ 7:P′[0]←P[t1] 8:for  n=1  to  N  do 9:t2←0, Gn←∞, μn[0]←μ0 10:φn,jm[0]←φ0 for m∈M and j∈N∖n 11:repeat  ∖∗ the search for μn,Φn∗∖ 12:for  m=1  to  M  do 13:compute pnm∗ by (22) with {α,λ[t1],μn[t2],φnm[t2]} 14:compute Hnm by (23) with {α,λ[t1],μn[t2],φnm[t2],pnm∗} 15:end for 16:update Gn by (21a) with {μn[t2],φnm[t2],Hnm:m∈M} 17:t2←t2+1 18:pn′[t2]←{pnm∗:m∈M} 19:update μn[t2] by (24a) with pn′[t2] 20:update {φn,jm[t2]:m∈M,j∈N∖n} by (24b) with pn′[t2] 21:until  δ2pn′[t2],pn′[t2-1]≤ε 22:end for 23:update F(α) by (17a) with {α,λ[t1],Gn:n∈N} 24:t1←t1+1 25:P[t1]←P′[t2] 26:update λ[t1] by (19) with P[t1] 27:until  δ1(P[t1],P[t1-1])≤ε 28:if  F(α)>0  then 29:αl=α 30:else if  F(α)<0  then 31:αh=α 32:end if 33:P[0]←P[t1]) 34:until  |F(α)|2≤ε 35:return  A,P[0]We briefly analyze the computational complexity of the algorithm. By (9), the subcarrier allocation yields a complexity of order O∑n=1NKnM. For power allocation, there are NM optimization variables pnm in P, one dual variable λ in (17a), and 1+(N-1)M dual variables μn and φn,jm in Φn for each n in (21a). Thus, the power allocation yields a complexity of order O(N2M+N+1). To achieve the accuracy ε for the bisection search, the computational complexity is estimated of polynomial order O∑n=1NKnM+N2M+N+1log2(1/ε) in the network scale parameters and thus acceptable for practical applications.


## 4. Simulation Results

In this section, we use computer simulations to validate Algorithm1 and examine its performance. For demonstration purpose, we consider a small scaled OFDMA downlink network with the number of cells N=2, the number of users in each cell K1=K2=4, and the number of subcarriers M=10. Upon assuming that all the channels experience independent identically distributed (i.i.d) Rayleigh fading, the intracell and intercell average channel gains are given by E(gn,knm)=1 and E(gn,kjm)=1/3, respectively, for all m∈M and j≠n∈N. Without loss of generality, we assume identically the circuit powers Pc=0.5 W and pc,nm=Pc/(NM)=0.025 W, the noise powers σn,kn2=σ2, the minimum cell sum rates Rminn=Rmin, and the TI thresholds ηn,jm=η for all m and j≠n.For performance comparison for different parameters and different schemes, we define the average signal-to-noise ratio (SNR) asSNR=Pmax/(NMσ2) per subcarrier. To determine the total transmit power threshold Pmax such that the QoS requirements can be satisfied for all cells, we define a satisfaction index (SI) metric in percentage as(27)SI=1N∑n=1Nmin1,RnRminwhere Rn is the sum rate of cell n computed from (2), and Rmin represents the QoS requirements for all cells. Clearly, we have SI=100% if and only if Rn≥Rmin for all n∈N.Figure3 shows the tendencies of SI versus SNR for various Rmin values, where equal power allocation per carrier is considered, and the noise power is set to be σ2=0.01 W. For each Rmin value, it is seen that SI tends to reach the maximum of 100% when SNR increases beyond some critical point. Meanwhile, it is in nature to observe that the critical SNR value increases with Rmin. Therefore, for simulations regarding a specific Rmin value, we can use the associated critical SNR value and the used σ2 value to estimate Pmax=SNR·NMσ2 as the minimum required system power. For example, the critical SNR value associated with Rmin=16 bps/Hz is approximately 12 dB by the figure, which corresponds to Pmax=3.17 W when σ2=0.01 W.Figure 3
QoS satisfaction index versus SNR for variousRmin values based on equal power allocation.Figure4 shows the simulation results on energy efficiency performance of Algorithm 1 versus Rmin within the range from 1 to 10 bps/Hz, where SNR=10 dB, and η=10σ2 under various channel conditions σ2=0.01,0.02,0.03,0.04 W. Accordingly, the total transmit power threshold is determined to be Pmax=2,4,6,8 W. The simulation results are analyzed as follows: leftmargin=∗,labelsep=4.9mm.(1)
The effects of the QoS requirementsRmin: for each given σ2 and hence Pmax, it is observed that the energy efficiency reaches the maximum over a lower region of Rmin and becomes decreasing as Rmin increases over the relatively higher region. This behavior is relevant to the effects of intercell interferences. To achieve a large Rmin value, each cell definitely needs to consume a high power, which can generate severer interferences to other cells. To overwhelm the interferences, an extra amount of power is in turn required, thus degrading the energy efficiency.(2)
The effects of the channel conditionsσ2: for a fixed Rmin, it is seen that a worse channel condition σ2 results in an increased Pmax and hence a degraded energy efficiency. For the instance of Rmin=1 bps/Hz, when σ2 is increased from 0.01 to 0.04 W such that Pmax is increased from 2 to 8 W, the energy efficiency is reduced from 26.5 to 12.5 bits/Hz/Joule at a reduction of approximately 53%. This behavior can be similarly analyzed in that more power consumptions are required to overwhelm large noise powers and increased intercell interferences.Figure 4
Comparison of energy efficiencies versusRmin for variant Pmax with respect to SNR=10 dB and η=10σ2.Next, we present a comprehensive comparison of the system performance in energy efficiency, total power, and throughput between the proposed scheme and the scheme in [16]. Note that the heuristic scheduling in [16] was designed to maximize the system throughout for multicell multiuser OFDMA networks under the total power constraint, which could result in large achievable rates for users with good channel conditions, but smaller achievable rates for users with worse channel conditions. However, in the proposed scheme, the throughout can be guaranteed by presetting Rminn for each cell.Figure5 compares the energy efficiency performance versus SNR between Algorithm 1 (noted “EE-opt”) and the algorithm proposed in [16] (noted “SE-opt”) for Rmin=1bps/Hz. To examine the effects of TI thresholds, two different settings of η=10σ2 and η=20σ2 are considered. It is observed that increasing SNR can improve the energy efficiency for both algorithms, while the proposed EE-opt algorithm outperforms the SE-opt one with an increasing performance gap. On the other hand, increasing the TI threshold from η=10σ2 to η=20σ2 reduces the energy efficiency for each algorithm. The performance loss tends to become larger as SNR increases. This observation can be explained by the fact that the increased TI threshold allows for severer intercell interferences, and thus more power is allocated to maintain the required Rmin.Figure 5
Comparison of energy efficiencies for two different settings of TI thresholdsη and two different algorithms with Rmin=1bps/Hz.Figure6 compares the total power consumption and the achievable rate for the system under the settings Rmin=1 bps/Hz, Pmax=2 W, η=10σ2, and the appropriate σ2 values determined with respect to the range of SNR values considered. It is observed that the proposed EE-opt algorithm is more advantageous over the SE-opt algorithm in power efficiency, although it suffers from a loss in achievable rate. This can be explained by the different objectives of the two algorithms. With the objective of maximizing the energy efficiency, the EE-opt algorithm may allocate only a partial amount of Pmax to satisfy the QoS constraint of Rmin. However, the SE-opt algorithm is aimed to maximize the throughout by allocating fully the amount of Pmax. This also interprets the observation that the SE-opt algorithm yields a constant power consumption of Pmax. Therefore, from Figures 5 and 6, it is concluded that the proposed EE-opt algorithm can be employed to provide a good tradeoff between energy efficiency and system throughput while satisfying the QoS requirements for all cells. In particular, the proposed EE-opt algorithm is also suitable to guarantee the QoS requirements for each user by slightly adjusting the QoS constraints as mentioned in Remark 1.Figure 6
Comparisons of transmit powers and achievable sum rates for two different algorithms withRmin=1bps/Hz and η=10σ2.


## 5. Conclusions

An energy-efficient algorithm for joint power and subcarrier allocation has been derived for a multicell OFDMA downlink network. Based on double dual decomposition, the joint optimization problem can be approached efficiently by distributive computations in closed form. Simulation results have validated the proposed algorithm by examining the effects of various system parameters, showing that the proposed algorithm can provide a good tradeoff between the energy efficiency and the system throughput compared with the existing algorithm.



---

*Source: 6875090-2018-10-30.xml*