Accepted Manuscript Energy efficiency maximization oriented resource allocation in 5G ultra-dense network: Centralized and distributed algorithms Wei Li, Jun Wang, Guosheng Yang, Yue Zuo, Qijia Shao, Shaoqian Li PII: DOI: Reference: S0140-3664(18)30518-8 https://doi.org/10.1016/j.comcom.2018.08.005 COMCOM 5761 To appear in: Computer Communications Received date : 30 May 2018; Revised date : Accepted date : 10 August 2018 10 August 2018; Please cite this article as:, Energy efficiency maximization oriented resource allocation in 5G ultra-dense network: Centralized and distributed algorithms, Computer Communications (2018), https://doi.org/10.1016/j.comcom.2018.08.005 This is a PDF file of an unedited manuscript that has been accepted for publication. As a service to our customers we are providing this early version of the manuscript. The manuscript will undergo copyediting, typesetting, and review of the resulting proof before it is published in its final form. Please note that during the production process errors may be discovered which could affect the content, and all legal disclaimers that apply to the journal pertain. Energy E?ciency Maximization Oriented Resource Allocation in 5G Ultra-Dense Network: Centralized and Distributed Algorithms I Wei Li?, Jun Wang, Guosheng Yang, Yue Zuo, Qijia Shao, Shaoqian Li National Key Laboratory of Science and Technology on Communications, University of Electronic Science and Technology of China, Chengdu 611731, China Abstract Spurred by both economic and environmental concerns, energy e?ciency (EE) has now become one of the key pillars for the ?fth generation (5G) mobile communication networks. To maximize the downlink EE of the 5G ultra dense network (UDN), we formulate a constrained EE maximization problem and translate it into a convex representation based on the fractional programming theory. To solve this problem, we ?rst adopt a centralized algorithm to reach the optimum based on Dinkelbach?s procedure. To improve the e?ciency and reduce the computational complexity, we further propose a distributed iteration resource allocation algorithm based on alternating direction method of multipliers (ADMM). For the proposed distributed algorithm, the local and dual variables are updated by each base station (BS) in parallel and independently, and the global variables are updated through the coordination and information exchange among BSs. Moreover, as the noise may lead to imperfect information exchange among BSs, the global variables update may be subject to failure. To cope with this problem, we propose a robust distributed algorithm, for which the global variable only updates as the information exchange is successful. We I This work is supported in part by the National Natural Science Foundation of China (NSFC) under grant 61471099, , the Funding of National Key Laboratory of Science and Technology on Communications, National Defense Pre-Research Foundation of China, and Innovation Fund of NCL (IFN) under grant IFN2018214. ? Corresponding author Email address: WeiLee@std.uestc.edu.cn (Wei Li) Preprint submitted to Journal of LATEX Templates August 13, 2018 prove that this modi?ed robust distributed algorithm converges to the optimal solution of the primal problem almost surely. Simulation results validate our proposed centralized and distributed algorithms. Especially, the proposed robust distributed algorithm can e?ectively eliminate the impact of noise and converge to the optimal value at the cost of a little increase of computational complexity. Keywords: 5G, Ultra-Dense Network, Resource Allocation, Energy E?ciency, Robust Distributed Algorithm 1. Introduction With the advent of the ?fth generation (5G) mobile communication networks, millions more base stations and billions of connected devices will bring exponential growth in network tra?c volume. The traditional spectrum management and cell structure can not meet the increasing tra?c demands [1]. On the other hand, the power consumption of the information and communication technology (ICT) industry and the corresponding energy-related pollution are becoming major societal and economical concerns. To simultaneously achieve high network area throughput and less power consumption is seemingly contradictory for 5G mobile communication networks. One promising answer to this issue lies in optimizing the energy e?ciency (EE) of ICT system, that is maximizing the amount of information reliably transmitted per Joule of consumed energy [2]: 2 EE , Area Spectral E?ciency [bit/symbol/km ] 2 (Transmit Power + Circuit Power )[J/symbol/km ] bit/J (1) To achieve higher system EE, the ultra-dense network (UDN), in which the low-cost and low-power small access points (SAP) with a very high density are overlayed with the macro base stations (MBS), has been proposed in recent years [3], [4]. It turns out that the UDN can obtain high system EE by elabo- 2 rate network settings, e.g, cell density, base station (BS) transmit power, radio resource allocation strategy, etc.. Therefore, this new network architecture has attracted a lot of interest from both academic and industrial ?elds. 1.1. Related work In earlier studies [5]-[7], the authors mainly focus on minimizing total transmit power through e?cient resource allocation algorithms. The authors of [5] propose an optimization problem to minimize the total power consumption while satisfying the Quality-of-Service (QoS) of the users and the power constraints at the MBSs and SAPs. They have proved that their proposed optimization problem has a hidden convex structure so that the optimal solution can be obtained in polynomial time. Based on the study of [5], [6] and [7] formulate the power minimization problem as a second-order cone program (SOCP) problem with a sparsity regularizer. Even though the SOCP problem admits a convex representation, direct optimization methods using standard tools [8] require central control, have large communication overhead, and are computationally intensive. Therefore, the authors of [9] provide distributed algorithms based on alternating direction method of multipliers (ADMM) to make the resource allocation e?cient and reduce the computational cost. Unlike the transmit power minimization oriented resource allocation, EE maximization problem has the form of nonlinear ratio-of-sum (NRS) [9], [18], which has the nature of non-convexity and is hard to get the optimal solution. To the best of our knowledge, the latest studies [10]-[16] pertaining to maximizing system EE mainly lie in two aspects. For one aspect, maximizing system EE is formulated as a constrained optimization problem, and some translations are introduced so that the primal problem can be converted to a convex form. Then, some algorithms are proposed to solve the problem in a centralized manner [11], [12]. This method is usually used in the resource allocation of the downlink. Unfortunately, the resulting algorithms are manifested to be ine?ective due to high computational cost. In [11], the authors put e?orts into searching the global maximum of 3 the system EE. They have jointly exploited the hidden monotonic structure of the most common EE maximization problem and the fractional programming theory [17], [18] to obtain globally optimal solution at the cost of high computation complexity. To overcome this defect, they further propose a power control strategy with a?ordable complexity. However, their proposed power control strategy only gets the suboptimal results. In [12], three de?nitions of energy e?ciency are considered for system design, and the corresponding optimization problems accounting for both the radiated and the circuit power are formulated. And then, the iteration algorithms based on Dinkelbach?s procedure are proposed to solve the resulting problems. As these algorithms have to solve a ) ( sub-optimization problem with a complexity of O (M N I)3 in every iteration, where M is the dimension of the variable, N is the number of BSs and I is the number of users, the computation complexity is very high. This makes the algorithms ine?ective especially in the UDN scenario, where the number of BSs and users are extremely large. For the other aspect, the network nodes behave in a competitive, selforganizing way, aiming at maximizing their own individual EE in a distributed manner [13]-[16]. This model is usually used in the uplink to maximize EE of the users and prolong the working time of the mobile devices. In [13], the authors aim at maximizing the EE for each individual user while guaranteeing the QoS requirement by formulating a multiple-objective optimization problem (MOOP). To ?nd its Pareto optimization solution, motivated by the weighted Tchebyche? method, they ?nd a single-objective optimization problem (SOOP) which can achieve the Pareto optimization solution of the original MOOP. [14] tackles the problem of joint users? uplink transmission power and data rate allocation in multi-service two-tier femtocell networks. Based on supermodular game theory, the joint resource allocation problem is directly formulated as a two-variable optimization problem and a non-cooperative game. Moreover, the authors provide a distributed and iterative algorithm to compute the desired Nash Equilibrium (NE) point. The authors of [15] focus on the problem of optimal cell selection and power control in the uplink of a two-tier femtocel4 l network through game theory. They propose a learning based algorithm to determine the Nash Equilibrium (NE) point of the cell selection game. In [16], the problem of e?cient power allocation in the uplink of a two-tier femtocell network has been addressed. The authors formulate the overall problem as a non-cooperative game, and solve it by supermodularity theory. By decomposing the original problem into several subproblems with smaller scale that can be computed in a parallel way, the distributed strategy has the advantage of lower computational complexity comparing with the centralized algorithm. However, the distributed schemes mentioned above generally su?er from performance degradation in searching the global optimum comparing with the centralized schemes. 1.2. Motivation and contribution In this paper, we focus on maximizing the downlink system EE under the scenario of 5G UDN to develop e?cient resource allocation algorithms with low computational complexity. Our contributions are listed as following: First, we formulate a constrained EE maximization problem and translate the primal problem into a convex form based on the fractional programming theory. We adopt a centralized algorithm based on Dinkelbach?s procedure to solve this problem. The similar processing methods have been used in [11]-[13]. As analyzed in [11], the Dinkelbach?s procedure based algorithm can always guarantee the EE to converge to the optimal value. Second, we further propose a distributed parallel processing algorithm based on ADMM [19] to reduce the computational overhead and improve the e?ciency. The Dinkelbach?s procedure based centralized algorithms are usually computed in an iterative manner, for which a subproblem with the same scale of variables as the corresponding primal problem needs to be solved during each iteration step. Therefore, these algorithms are usually ine?cient and have high computational complexity in the 5G UDN scenario, where the number of BSs and users are extremely large. Moreover, these algotihms need a central node to collect the channel information, solve the optimization problem, and release 5 the results. This increases the capital expenditure (CAPEX) of telecom operators and makes the algorithm impractical. To avoid these disadvantages of the Dinkelbach?s procedure based centralized algorithms, the proposed distributed algorithm decomposes the original problem into a series of iterations. The local and dual variables are updated independently and in parallel at each BS, and the global variables are updated through the coordination and information exchange among BSs. In contrast to the distributed algorithms proposed in [13] and [14], our proposed algorithm can achieve the same performance as that of the centralized algorithm. Moreover, it has low computational complexity. Third, we propose a robust distributed algorithm to cope with the imperfect information exchange among BSs during the iterations. Because of the commonly existing noise in communication systems, the information exchange among BSs may be erroneous, so that the global variable update may be subject to failure. We assume that the receiver can only decode the information correctly if the signal-to-interference-plus-noise ratio (SINR) is larger than a speci?c threshold, otherwise, the information exchange will fail. For this case, we modify the primal distributed algorithm to update the global variable only when the link does not fail. We prove that the modi?ed robust distributed algorithm converges to the optimal solution of the primal problem almost surely. Simulation results validate our proposed centralized and distributed algorithms. Comparing with our primal distributed algorithm, numerical results show that the proposed robust distributed algorithm can e?ectively eliminate the impact of noise and converge to the optimum at the cost of a little increase of the computational complexity. Meanwhile, the proposed robust distributed algorithm have signi?cantly lower computation complexity than that of the centralized algorithms. 1.3. Organization and Notations The rest of the paper is organized as follows. The system model and EE oriented resource allocation problem formulation are introduced in Section 2. Section 3 gives the centralized algorithm and the ADMM based distributed al6 gorithm. In Section 4, we propose a robust distributed algorithm to cope with the imperfect information exchange among BSs during the iterations. Simulation results are presented to verify our proposed algorithms in Section 5. Finally, Section 6 concludes this paper. Notations: We use boldface letters to denote matrices or vectors. For a vector x, xi denotes its ith element, ||x|| represents its Euclidean norm, ||x||2 is the Frobebius norm and xT stands for its transpose. We use curlicue letters to denote a set. For a set U, |U| denotes its cardinality, ui ? U represents its element. The notation E{и} denotes the expectation with respect to a random variable. We use ? to denote the gradient operation. The dimension of a variable is denoted as the superscript, e.g., X ? RaОb means that X is a real matrix of a rows and b columns. We use the notation O(и) to denote the complexity order of an algorithm. 2. System model and problem formulation In this section, we describe the system model and formulate the EE oriented optimization problem for 5G UDN. 2.1. System description As illustrated in Fig. 1, we consider a K-tier network covering an area of A, in which the BSs (including MBS, SAPs, etc.) in each tier are independently distributed according to a spatial homogeneous poisson point process (PPP) ?k with density ?k . In this paper, we consider the downlink employing M subcarriers and universal frequency reuse (UFR), where the BSs in di?erent tiers share the whole spectrum and users can access to any of the subcarrier of its service BS [4]. Let the notation k denote the index of a speci?c tier, and k ? K = {1, и и и , K}, where K represents the set of all tiers. The BSs in tier k form a set Nk , and all the BSs in the considered UDN form the set N = {Nk }k?K . The notation nk and ik represent the index of the n-th BS in iter k and i-th user served by the BS in tier k, respectively. The index of the nth BS from tier k can be uniquely determined by the notation nk . Similarly, the 7 Core or Network e Servers SGW Mobile Node Hotspot Link Connected Through Internet Backhaul Link Office Buiding Millimeter-wave Link Airport Internet Beanforming Link Dense Small Cell Base Station Femtocell Cache Malls Small Cell Radio Tower Home Hotspot Camera Watch Access Point IoT WiFi Network Academic Area Dense Area User Equipment Users Figure 1: General architecture of 5G ultra-dense network index of the ith user from tier k can be uniquely determined by the notation ik . Each BS equipments with a single antenna and serves the single antenna users within its service range 1 . The users are assumed to be distributed according to a homogeneous PPP ?u with density ?u . We denote Unk as the user set which is served by BS nk , and all the users in the considered scenario form a set of U = {Unk }nk ?N . Each user is only connected to one BS, which is selected based on long-term channel quality measurements. 2.2. Problem formulation We assume that the channel between the BS and the user remain constant during each transmission. Meanwhile, we assume that the user can e?ectively estimate the channel state information (CSI) and provide necessary feedback to 1 Note that our model can be easily extended to the multi antenna scenario. Please refer to our previous work [20] for the details. 8 the BS. By assuming perfect synchronization, the signal received by user ik is |Nl | K ? ? [m] [m] [m] [m] [m] Hnl ,ik x[m] yik = Hnk ,ik xnk ,ik + nl + wnk ,ik , | | {z } {z } l=1 nl =1,nl ?=nk noise target signal | {z } (2) interference [m] where Hnk ,ik is the complex channel response between BS nk and user ik on subcarrier m, which includes both small scale fading and large scale fading [21]; [m] xnk ,ik is the complex symbol transmitted by BS nk to user ik on subcarrier m; [m] xnl represents the signal transmitted on subcarrier m by BS nl . |Nl | represents the number of BSs in layer l. The transmitted symbols are modeled as indepen [m] 2 [m] dent random variables with zero mean and variance E{xnk ,ik } = pnk ,ik > 0. [m] wnk ,ik represents the noise at user ik , which is a circularly-symmetric complex [m] Gaussian random variable with mean zero and variance ?nk ,ik /2 per dimension. Therefore, the SINR of user ik on subcarrier m can be expressed as [m] [m] SINRnk ,ik = 1+ [m] pnk ,ik Gnk ,ik ?K ?|Nl | nl =1,nl ?=nk l=1 [m] [m] pnl Gnl ,ik , (3) [m] 2 [m] [m] [m] where Gnk ,ik = Hnk ,ik /?ik is the equivalent channel gain, and pnl = [m] 2 E{xnl }. Hence, the corresponding achievable information rate of user ik on subcarrier m can be expressed as ( [m] [m] ) Rnk ,ik = Bm log 1 + SINRnk ,ik , (4) where Bm is the bandwidth of subcarrier m. As described in [5] and [22], the typical power consumption of a BS can be modeled as the sum of dynamic and static terms, i.e., Pnk = ?nk | M ? p[m] nk + ?nk /M , | {z } m=1 Pstatic {z } Pdynamic 9 (5) where the dynamic term Pdynamic is the aggregation of the emitted power, and ?nk accounts for the e?ciency of the transmitter power ampli?er. The static term Pstatic is inversely related to the number of subcarriers, and ?nk models the power dissipation of the circuits. Therefore, the system downlink EE can be given as follows 2 EE = ( [m] ) Bm log 1 + SINRnk ,ik . ? ?M [m] nk ?N (?nk m=1 pnk + ?nk /M ) ? ik ?U ?M m=1 (6) Our target is to maximize the system EE while satisfying the QoS and the power constraints. Hence, we formulate the optimization problem as arg max EE [m] pnk ,?m,nk ,ik s.t. Pnk ? P?nk , ?nk ? N [m] (7) [m] Rnk ,ik ? ?ik , ?ik ? U, [m] where P?nk is the maximum power budget of BS nk , ?ik is the minimum rate to meet the communication requirements of user ik on subcarrier m. In traditional multi-cell network analysis, the target is to minimize the sum of transmitting power. As the resulting objective function is convex and separable, it can be solved with standard methods. However, problem Eq.(7) is non-convex because the objective function Eq.(6) has the form of nonlinear ratio-of-sum [18]. Therefore, we have to convert the primal problem into a convex form and provide algorithms to solve it. The details will be discussed in the next section. 3. Optimization of energy e?ciency In this section, we convert the primal problem Eq.(7) into a convex form based on fractional programming theory and present centralized and distributed 2 According to the de?nition in Eq.(1), the numerator of (6) should be the spectrum e?cien( ? ?M [m] ) ?M cy expressed as m=1 Bm . As the sum bandwidth ik ?U m=1 Bm log 1 + SINRnk ,ik / ?M B is a constant, we ignore this part. m=1 m 10 algorithms to solve it. 3.1. Centralized algorithm for EE maximization Generally, the optimization problem with a ratio-of-sum objective function can be solved by the Dinkelbach?s algorithm in an iterative manner [9]. Let the objective function be f (x)/g(x). During each iteration, the Dinkelbach?s algorithm should get the solution of the intermediate function F (?) = arg max min{f (x) ? ?g(x)}. However, the intermediate function of our optimization problem is not convex. The Dinkelbach?s algorithm can not be used to solve our problem directly. To combat with this di?culty, we ?rst introduce two lemmas and a transformation to convert the intermediate function into a convex form. Then, we propose a Dinkelbach?s algorithm to solve the resulting convex optimization problem. To get the global optimum of problem Eq.(7), we need to covert the primal problem into a convex form. We ?rst introduce the following Lemmas [11], [23]: Lemma 1. Assume f and g are continuous, g is positive, and S is compact. De?ne F (?) = max{f (x)??g(x)}. Then, for any x ? S, F (?x ) ? 0, where ?x = x?S f (x)/g(x). Speci?cally, F (?x ) = 0 holds when x = arg max{f (x) ? ?x g(x)}. x?S Lemma 2. For any non-negative ? and ?0 , log(1 + ?) ? ? log(?) + ?, where ? = ?0 /(1 + ?0 ), ? = log(1 + ?0 ) ? ?0 log(?0 )/(1 + ?0 ). Speci?cally, log(1 + ?) = ? log(?) + ? holds for ? = ?0 . From Lemma 1, we get that for the speci?c x? ? S and ?? = f (x? )/g(x? ), x? is the solution of max f (x)/g(x) if and only if x? = arg max{f (x) ? ?? g(x)}. x?S x?S Therefore, the objective function of primal problem Eq.(7) can be converted to the following form: f = EE M ? ? ik ?U m=1 | ( ) ( ? ) M ? ( ) [m] Bm log 1 + SINRnk ,ik ?? , ?nk p[m] + ? /M nk nk {z f (p) } 11 | nk ?N m=1 {z g(p) } (8) where the parameter ? can be calculated according to Lemma 1, and p is the [m] variable obtained by stacking all the variables {pnk }, ?m, nk . Based on the transformation given in Lemma 2, the objective function Eq.(8) can be further converted to f = f (p) ? ?g(p) EE ( ) M ? ? [m] [m] [m] ? ?nk ,ik Bm log(SINRnk ,ik ) + ?nk ,ik ??g(p), ik ?U m=1 {z | [m] (9) } f?(p) [m] where ?nk ,ik and ?nk ,ik are given as [m]? [m] ?nk ,ik = and [m] ?nk ,ik SINRnk ,ik [m]? 1 + SINRnk ,ik , (10) ( ) [m]? [m]? SINRnk ,ik log2 SINRnk ,ik [m]? = log2 1 + SINRnk ,ik ? , [m]? 1 + SINRnk ,ik [m]? (11) [m] respectively. Meanwhile, SINRnk ,ik is the approximation of SINRnk ,ik given in [m]? Eq.(3). The calculation method of SINRnk ,ik will be presented in Algorithm 1. [m]? As described in Lemma 2, the equality of Eq.(9) will be hold while SINRnk ,ik = [m] SINRnk ,ik . [m] [m] [m] [m] [m] Let qnk ,ik = ln pnk ,ik , qnk = ln pnk , and all the variables qnk ,ik , ?m, nk , ik are stacked in three-order tensor q [25]. We can ?nally translate the primal optimization problem Eq.(7) into the following form: arg max q s.t. [m] f?(exp(q)) ? ?g(exp(q)) ( ) Pnk exp(q) ? P?nk , ?nk ) [m] ( [m] Rnk ,ik exp(q) ? ?ik , ?ik , (12) where Pnk (и) and Rnk ,ik (и) can be given based on Eq.(3), Eq.(4) and Eq.(5), respectively. Then, we have the following theorem: 12 Theorem 1. The optimization problem Eq.(12) is a concave function of q. Proof. The proof of Theorem 1 is presented in Appendix A. Theorem 1 implies that the EE maximization oriented optimization problem can be solved by a centralized algorithm based on Dinkelbach?s procedure [9]. The corresponding algorithm is summarized as Algorithm 1. In Algorithm [m]? 1, s denotes the iteration step index, ? is the stop criteria, ?nk ,ik stands for [m]? SINRnk ,ik , and F (?) is calculated based on Lemma 1. Algorithm 1: Dinkelbach?s procedure based centralized algorithm for EE maximization. 1: Initialization: s = 1, ? > 0, and ?[s] = 0. 2: While F (?[s?1] ) ? ? do Solve the problem Eq.(12) and get q[s] . Update parameters: ?[s] = f (exp(q[s] ))/g(exp(q[s] )), F (?[s] ) = f (exp(q[s] )) ? ?[s] g(exp(q[s] )), [m]? [m]? Substitute exp(q[s] ) into Eq.(3) to get SINRnk ,ik and ?ik [m] 3: [m]? = SINRnk ,ik , [m] update ?nk ,ik and ?nk ,ik according to Eq.(10) and Eq.(11), s=s+1 . End while 4: Substitute exp(q) into Eq.(6) to get EE. As the optimization problem of Eq.(12) is convex, standard tools, such as cvx [8], can be used in step 2 of Algorithm 1 to solve it. Note that, although the objective function of problem Eq.(12) is the lower bound of Eq.(6), Algorithm 1 can still converge to the optimal EE. In order to prove this claim, we introduce the following sequential optimization theory, which readily follows from [36]. Lemma 3. Let F be a maximization problem with di?erentiable objective f0 (x), constraints fi (x) ? 0, ?i ? {1, и и и , I}, and a compact feasible set. Let Gj be a maximization problem with di?erentiable objective g0,j (x), constraints gi,j (x) ? 13 0, ?i ? {1, и и и , I}, compact feasible set, and optimal solution x?j . Assume that ?j and ?i ? {1, и и и , I}, gi,j (и) satis?es the following two properties: 1) gi,j (x) ? fi (x), ?x; 2) gi,j (x?j?1 ) = fi (x?j?1 ). Then, the sequence f0 (x?j ) is monotonically increasing and converges to a ?nite limit g. Next, assume the following third property is also satis?ed ?j and ?i ? {1, и и и , I}: 3) ?gi,j (x?j?1 ) = ?f (x?j?1 ). Then, under suitable constraint quali?cations, every limit point of {x}j that achieves the objective value g ful?lls the KKT conditions of the original problem F. Lemma 3 shows that by solving the sequence of approximate problem {G}j , one can generate a sequence of feasible points x?j that monotonically increases the value of the original objective f0 . Moreover, the limit value g is the value that the original objective attains at a KKT point of F. Therefore, according to Lemma 2 and Lemma 3, the sequential optimization solution of algorithm 1 will approach the optimal value of Eq.(6) asymptotically. 3.2. ADMM based distributed algorithm for EE optimization The centralized algorithm proposed above is computed in an iterative manner. In each iteration, the subproblem to be solved has the same scale of variables as that of the primal one. Therefore, the algorithm may be ine?cient and has high computational cost, especially in the 5G UDN scenario where the number of BSs and users are extremely large. What?s more, in order to perform this centralized algorithm, a high performance central node is necessary to collect the CSI, solve the optimization, and release the results. To avoid these disadvantages of the centralized algorithm, we further exploit the structure of the primal problem to develop a distributed algorithm based on the well-known ADMM algorithm. The distributed algorithm decomposes the primal problem into a series of iterative steps, in which the local variable and the dual variable update are carried out independently and in parallel by all BSs. Meanwhile, the global variable update is carried out by the coordination and information exchange among the BSs. 14 To facilitate describing the information exchange among the BSs, we model the connections among the BSs as a connected undirected graph G = {V, E}. ?K Here, V = {1, и и и , N } represents the set of nodes in our scenario, N = k=1 A?k , and E is the set of edges, i.e., for n ? V, j ? V, (n, j) ? E if and only if n and j are neighbors. The neighbors subset of node n ? V is de?ned as: N?n = {j ? V|(n, j) ? E}. (13) As exp(q) in Eq.(12) represents the transmit power from all BSs to their ser?K vicing users, we have q ? RM ОA?u О k=1 A?k . Because each user is only allowed to connect to one BS, q is a spare 3-order tensor determined by the associated schedule strategy. Then, we can extend the variable by the Lathauwer-MoorVanderwalle (LMV) method [26] and reconstruct it as q(2) , [qT1 , и и и , qTN ] , where qn = RM ОA?u О1 represents the nth element of q(2) . We expand the object function of Eq.(12) to get f?(exp(q)) ? ?g(exp(q)) ( ? ?M [m] [m] [m] ) = ik ?U m=1 ?nk ,ik Bm log(SINRnk ,ik ) + ?nk ,ik ) (? ?M ?? nk ?N (?nk m=1 exp(qnk ) + ?nk /M ) . (14) As U = {Unk }nk ?N , the ?rst item of Eq.(14) can be decomposed as the accumulation of N subitems. Hence, Eq.(14) can be further expressed as follows f?(exp(q)) ? ?g(exp(q)) = where N ? ?n (qn ), [ [m] [m] m=1 ?nk ,ik Bm log(SINRnk ,ik ?M ???n m=1 exp(qn ) + ?nk /M. ?n (qn ) = (15) n=1 ?M ] [m] + ?nk ,ik ) (16) Therefore, the primal problem Eq.(7) can be reformulated as N ? arg max T q=[qT 1 ,иии ,qN ],qn ?Xn n=1 15 ?n (qn ), (17) where Xn , n = 1, и и и , N is the convex constraint of qn . The detailed description of Eq.(17) is given in Appendix B. We further introduce the function ?(z) and a equality constraint to reformulate problem Eq.(17) as ?N arg max n=1 T [qT 1 ,иии ,qN ],z,qn ?Xn ?n (qn ) + ?(z) ?N s.t. (18) n=1 En qn = z, where En is a prede?ned coe?cient matrix and known by each BS. To ensure that problem Eq.(17) and problem Eq.(18) are equivalent, ?(z) should be a constant, e.g., zero. The Lagrange dual problem of Eq.(18) is given as arg min y N ? ( ?n (y) + n=1 1 T ) y z , N (19) where ?n (y) , arg max{?n (qn ) + yT En qn }, ?n ? V. (20) qn ?Xn From the above derivation and discussion, we can conclude that problem Eq.(18) is a convex problem, i.e., ?n , n = 1, и и и , N is a proper closed convex function, and Xn , n = 1, и и и , N is a compact convex set. Therefore, problem Eq.(18) satis?es the strong dual condition and there is no duality gap between Eq.(18) and its Lagrange dual. Moreover, the minimum of Eq.(18) and its optimal dual value can be attained. To facilitate multi-BS distributed optimization, we allow each BS to have a local copy of the dual variable y, which is denoted as yn , ?n ? V. In our scenario, we only allow the information exchange between neighbouring BSs. Then, Eq.(19) can be equivalently reformulated as the following problem arg min yn ,{en,j } s.t. ?N n=1 ( ?n (yn ) + ) 1 T N yn z (21) yn = en,j , yj = en,j , ?n ? V, j ? N?n , where {ei,j } is the slack variable ensuring neighbor-wise consensus. As the 16 strong convexity hold, the dual gap will be zero, and the optimal solution of problem Eq.(21) equals the solution of the primal problem. The augmented Lagrangian function of problem Eq.(21) is shown as La , ?N n=1 ( ?n (yn ) + ) 1 T N yn z ) +vTn,j (yj ? en,j ) + ) +||yj ? en,j ||22 , ? 2 + ?N ?N n=1 n=1 ? ? j?N?n j?N?n ( ( uTn,j (yn ? en,j ) ||yn ? en,j ||22 (22) where un,j and vn,j are the lagrange dual variables, ? /2 is the penalty parameter. Hence, the standard ADMM [24], [27] steps to solve problem Eq.(21) can be shown as follows: [s] yn { = arg min ?n (yn ) + yn 1 T N yn z + ? j?N?n ( [s?1] uTn,j (yn ? en,j ) ( ? [s?1] ) [s?1] vTn,j (yj ? en,j ) + ?2 j?N?n ||yn ? en,j ||22 } ) [s?1] +||yj ? en,j ||22 , ?n ? V, { [s?1] u [s] [s] en,j = arg min ||yn ? en,j + n,j ||22 ? en,j } [s?1] v [s] 2 ||yj ? en,j + n,j || 2 , ?n ? V, j ? N?n , ? [s] [s?1] + ? (y[s] n ? en,j ), ?j ? N?n , n ? V, [s] [s?1] + ? (y[s] n ? en,j ), ?j ? N?n , n ? V, un,j = un,j vn,j = vn,j (23) (24) [s] (25) [s] (26) where s is the update step index. From the de?nition of ?(и) given in Eq.(20), we know that Eq.(23) is a min-max (saddle point) problem. By plugging Eq.(16), Eq.(24), Eq.(25), and 17 Eq.(26) into Eq.(23), the ?rst step of the update can be simpli?ed as [s] { ?n (qn ) + yTn (En qn ? yn qn ?Xn [s?1] } ? y[s?1] +y +? j?N?n ||yn ? n 2 j ||22 yn = arg min max 1 N z) { ? 1 1 ?n (qn ) ? 4N ? (En qn ? N z) + yn qn ?Xn [? [s?1] [s?1] 2 1 ) 2 + ? N yn ? 2N +yj j?N?n (yn ( )] } 2 [s] + ?1 En qn ? N1 z 2 . = arg min max ? [s?1] j?N?n (yn [s?1] + yj (27) ) Obviously, the above optimization problem has the property of strong convexity with respect to yn given any qn , or with respect to qn given any yn . Therefore, we can apply the min-max theorem [28] to decouple the above problem. Finally, we can get the update steps of qn and yn as follows { [s] qn = arg min ?n (qn ) + qn + y[s] n = 1 2N ? [s?1] j?N?n (yn ( ? ( ? 1 4N ? (En qn [s?1] + yj [s?1] ) yn[s?1] + yj j?N?n + 2 } )2 , ? 1 N z) (28) ) 1( 1 ) En q[s] ? z . n ? N (29) From the expression of Eq.(24), it can be derived that [s] en,j = [s] [s?1] [s?1] yn + yj vn,j + un,j + . 2 2? (30) [s] [s] By plugging Eq.(30) into Eq.(25) and Eq.(26), respectively, we get un,j + vn,j = [s] 0. Hence, the update of the variable en,j can be simpli?ed as [s] [s] en,j = [s] yn + yj , ?n ? V, j ? Nn . 2 (31) Then, to update variable e for BS n, information y from its neighbour is required. So, e can be considered as a global variable, which stands for the information exchange between the neighboring BSs. The details of ADMM based 18 Algorithm 2: ADMM based distributed algorithm for EE maximization [0] [0] [0] 1: Initialize variables: yn = 0, un,j = 0, and vn,j = 0 for each BS n, n ? V, j ? Nn and set s = 1. 2: For all n ? V, j ? Nn update (in parallel), { ? [s?1] [s?1] 2 } [s] 1 ? 1 ) 2 , (yn + yj qn = arg min ?n (qn ) + 4N ? (En qn ? N z) + qn ?Xn [s] yn = 1 2N ( ? [s?1] (yn + [s?1] yj ) [s] 1 ? (En qn + j?N?n [s] en,j [s] un,j [s] { [s] = arg min yn ? en,j + en,j = [s?1] un,j [s?1] vn,j = vn,j s = s + 1. [s] [s] [s] [s] + ? (yn ? en,j ), [s?1] un,j ? j?N?n ? ) 1 N z) , 2 [s] + y ? en,j + j 2 [s?1] vn,j ? } 2 , 2 + ? (yn ? en,j ), 3: Stop while a prede?ned stopping criterion is satis?ed. 4: Substitute exp(qn ), ?n into the primal problem Eq.(17) to get optimal EE. distributed algorithm is summarized in Algorithm 2. 3.3. Discussions Comparing with Algorithm 1, Algorithm 2 has the following advantages: 1) Computational costs: As noted above, Algorithm 1 should solve the ?K problem whose variable has the scale of M О ?u A О k=1 ?k A during each iteration step. If we use standard interior point algorithm to deal with this optimization problem, the computational complexity will be in the order of ) ( ?K O (M О ?u A О k=1 ?k A)3 [29]. Comparing with Algorithm 1, Algorithm 2 ?K decomposes the primal problem into N (where N = k=1 ?k A) subproblems whose variable has the scale of M О?u A, the computational complexity of Algo( ) rithm 2 will be in the order of O N О (M О ?u A)3 . Although the DinkelBach?s procedure based algorithm has a faster convergence rate than the ADMM based distributed algorithm, [30] and [31] show that a typical DinkelBach?s procedure and a ADMM based distributed algorithm have convergence rate of 19 1 2( ?1 5+1)s and 1s , respectively. So, the advantage is not signi?cant. Moreover, the computational complexity of the distributed algorithm will be much lower than that of the centralized algorithm while the number of BS N becomes large. We will provide detailed numerical comparison in Section 5. 2) Distributed implementation: Another advantage of Algorithm 2 is that it can be implemented in parallel. From the iteration step shown in Algorithm 2, the N subproblem can be allocated to the corresponding N BSs and be computed at the same time. Then, Algorithm 2 is time e?cient. 4. Robust distributed algorithm Recently, [32] and [33] have proposed robust ADMM algorithms to cope with the communication error caused by the change of nodes state (in state ?ON? or ?OFF? randomly) in the network during each iteration period. However, the adopted model in [32] and [33] is not suitable for our considered 5G UDN scenario. In fact, as 5G mobile communication network is a time sensitive network which needs to support a roundtrip latency of about 1 ms [1], the time granularity of the applied algorithm should be much smaller than that of network state. That is to say, within the performing period of an algorithm, the state of the nodes in the UDN should keep unchanged. Otherwise, the algorithm is time-costly and may not be suitable for the UDN. Therefore, we consider the scenarios where the exchanged information is contaminated by the channel noise during each iteration and to develop a robust distributed algorithm in this Section. In spite that it has the advantages in computational complexity and time e?ciency, Algorithm 2 is over-reliant on the quality of links between the neighbouring BSs. Because of the widespread noise in communication systems, information exchange during iterations may be imperfect. Then, the global variable update in Algorithm 2 may be subject to failure. It is reasonable to assume that the BSs can receive information from its neighbour correctly if the SINR is larger than a speci?c threshold. Otherwise, 20 the information exchange will fail. We assume that, at each iteration, the information exchange will fail with a probability pl ? [0, 1). The link state can be expressed as (n, j) = ? ? 0, communication link between BS n and BS j fails, ? 1, (32) otherwise. The communication link between BSn and BSj is considered to be active if (n, j) = 1, which means that the information exchange between these two BSs can be successfully completed. Note that, as the link state varies, the set of neighbor of BS n will change at the same time. Therefore, we de?ne the dynamic neighbor set in iteration step s as {N?n[s] : ?n, j ? N?n & (n, j) = 1}. (33) To deal with the above mentioned dynamic feature of link state, we propose that only the BSs with active communication link can update the global variables, otherwise, the global variables keep unchanged at each iteration. By incorporating this modi?cation, Algorithm 2 is improved to Algorithm 3. The convergence of Algorithm 3 is given in Theorem 2. Theorem 2. Suppose that the probability of the link failure pl ?= 1 and the topology of the network G is connected in the long run, exp(qn ), ?n generated by Algorithm 3 converges to the optimal solution set of problem Eq.(7) almost surely. Proof. The proof of Theorem 2 is presented in Appendix C. 5. Numerical results In this section, we provide simulation results to validate the proposed EE maximization resource allocation algorithms. We consider a two-tier UDN consisting of MBSs as tier 1 and SAPs as tier 2. The network covers an area with 21 Algorithm 3: Robust distributed algorithm for EE maximization [0] [0] [0] 1: Initialize variables: yn = 0, un,j = 0, and vn,j = 0 for each BS n, n ? V, j ? Nn , and set s = 1. 2: For all n ? V, j ? Nn update (in parallel), { ? [s?1] [s] [s?1] 2 } 1 ? 1 qn = arg min ?n (qn ) + 4N (yn + yj ) 2 , ? (En qn ? N z) + qn ?Xn [s] yn = 1 2N ( ? [s?1] (yn + [s?1] yj ) + [s] 1 ? (En qn j?N?n [s] en,j [s] ? ) , ? { [s?1] 2 } [s?1] 2 ? ? min y[s] ? e + un,j + y[s] ? e + vn,j , j ? N? [s] n,j n,j n ? 2 j ? 2 = en,j n ? ? [s?1] en,j , otherwise. [s?1] un,j = un,j [s] j?N?n 1 N z) [s?1] vn,j = vn,j s = s + 1. [s] [s] [s] [s] + ? (yn ? en,j ), + ? (yn ? en,j ), 3: Stop while the prede?ned stopping criterion is satis?ed. 4: Substitute exp(qn ), ?n into the primal problem Eq.(17) to get optimal EE. radius R = 0.5Km. The users are distributed in the coverage according to PPP with density ?u = 200 (users per Km2 ), and the QoS constrain of the users is 2 bits/s/Hz. The maximum transmit power of the BSs on each of subcarrier are P?1 = 66mW and P?2 = 0.8mW, respectively. The channel response between BS q and user i includes both small scale fading (Rayleigh fading) and large scale fading. The adopted parameters are listed in Table 1. The densities of MBS and SAP are ?1 = 19 (MBSs per Km2 ) and ?2 = 56 (SAPs per Km2 ), respectively. To simulate the parallel processing algorithms, we have used the MATLAB Parallel Computation Toolbox [35]. Fig. 2 shows the comparison of the Algorithm 1 for EE maximization oriented resource allocation schedule and the transmit power minimization/capacity maximization oriented resource allocation schedules adopted in [5]. From this ?gure, we can see that EE maximization oriented resource allocation has obvi- 22 Table 1: Simulation parameters parameters power ampli?er e?ciency max transmit power power dissipation number of subcarriers subcarrier bandwidth small-scale fading between BS nk and user ik log-normal shadowing path and penetration loss (distance d km ) values 1 ?1 = 0.388, ?12 = 0.052 P?1 = 66mW, P?2 = 0.8mW ?nk = 189/M M = 600 15kHz hnikk ? CN (0, 1) 7dB 148.1 + 37.6 log10 (d)dB ous advantage in terms of higher area throughput and less power consumption. As the DinkelBach?s procedure based algorithm searches the global optimum of the system EE, the system can achieve about 5 times higher EE of the other two schemes. 7 12 x 10 Energy Efficiency [bit/J] 10 8 6 Algorithm 1 Capacity Max Power Min 4 2 0 0 20 40 60 80 100 Iterations 120 140 160 180 200 Figure 2: Comparison of Algorithm 1 for EE maximization oriented resource allocation schedule and transmit power minimization/capacity maximization oriented resource allocation schedules. Fig. 3 shows the performance comparison between our proposed algorithms 23 and the one proposed in [13]. Note that Algorithm 3 is simulated under the scenario with a link failure probability pl = 0.05. All the algorithms have the same stop criteria ? = 10?3 . From this ?gure, it can be observed that these three algorithms proposed in our paper converge to the same optimal value. This result veri?es that the distributed algorithms (Algorithm 2 and Algorithm 3) can achieve the same performance as the centralized algorithm (Algorithm 1). What?s more, this result also validates that Algorithm 3 can eliminate the in?uence of possible information exchange failure due to the communication link dynamic feature to get the global optimal value. On the other hand, we also present the performance of the algorithm proposed in [13]. As discussed in Section 1.1, the algorithm from [13] can only obtain the suboptimal solution, and then su?ers from signi?cant performance degradation comparing with global optimal solution. It can be seen that, comparing with the algorithms proposed in our paper, the algorithm from [13] su?ers from a twenty percent performance degradation. 12 Energy Efficiency [Mbit/J] 10 8 6 4 Algorithm 1 Algorithm 2 Algorithm 3 Algorithm from [13] 2 0 0 200 400 600 800 1000 1200 Iterations 1400 1600 1800 2000 Figure 3: Performance comparison between our proposed algorithms and the algorithm proposed in [13] with parameters: Pl = 0.05, ? = 10?3 . 24 Fig. 4 shows the convergence speed under di?erent stop criteria. It can be seen that Algorithm 1 has the fastest convergence speed in terms of iteration number, and Algorithm 3 needs the largest number of iteration steps to converge to the same stop criteria. As analyzed in the previous section, the convergence rate of DinkelBach? procedure based algorithm is rate of the ADMM based distributed algorithm is 1 , while the convergence 1 s. Because of the in?uence ? 5+1 s 2 of noise, information can not be exchanged e?ciently during each iteration, Algorithm 3 needs a little more steps to converge to the optimal value. ?1 10 Algorithm 1 Algorithm 2 Aglorithm 3 ?2 10 Stop Criteria ?3 10 ?4 10 ?5 10 ?6 10 0 200 400 600 800 1000 1200 Iterations 1400 1600 1800 2000 Figure 4: The convergence speed of the three algorithms under di?erent stop criteria while pl = 0.05. However, as much simpler sub-problems are solved in parallel by N BSs, the required computation time of the distributed algorithms can still be signi?cantly reduced. Table 2 presents the comparison of computing time and iteration steps for ? = 10?3 and ? = 10?4 . From Table 2, we can see that, although Algorithm 2 needs more iteration steps, the corresponding computation time is much less than that of Algorithm 1. It can be seen that, in spite of the iteration numbers, the running time required by the distributed algorithms is at least one order of 25 Table 2: Average performance of computing time and iteration steps. Stop Cr. ? = 10?3 Algorithm1 Algorithm2 Comp. Time (sec.) Ite. Num 62.709 73 2.510 456 Stop Cr. ? = 10?4 Algorithm1 Algorithm2 Comp. Time (sec.) Ite. Num 183.215 176 4.710 903 Algorithm3 pl = 0.05 3.102 537 Algorithm3 pl = 0.05 6.828 1205 Algorithm3 pl = 0.10 6.977 1320 Algorithm3 pl = 0.10 8.029 1516 magnitude less than that of the centralized one. Even for the worst case, the running time of our proposed distributed algorithms is still less than ten seconds. Due to the capacity limitation of the simulation platform performed in a PC, the running time of our distributed algorithms is larger than the delay threshold of the real system, e.g., the delay threshold of users plane is 5 ms in LTE system. Not that, in real system, the distributed algorithms will be performed in parallel with high performance ASIC so that the computing time can much less than the delay threshold of the real system. Therefore, our distributed algorithms can be practical in real system. Due to the in?uence of possible link failure, Algorithm 3 needs a little more iteration steps than Algorithm 2, but its computation complexity is still signi?cantly lower than that of Algorithm 1. Algorithm 2 will crash once the communication link is failure in any iteration because the global variable can not be successfully updated. Therefore, Algorithm 3 is more robust than Algorithm 2. Intuitively, a smaller stop criteria ? will lead to more iteration steps. What?s more, the value of the link failure probability has e?ect on the iteration steps and computation time. Fig. 5 shows the convergence speed of the Algorithm 3 under di?erent link failure probabilities. We have tried a lot of failure probabilities in our simulations, and ?nd that pl = 0.20 is the largest failure probability with a?ordable convergence time. It can be seen that, as the link failure probability increases, more iteration steps are needed to converge to the same stop criteria. Therefore, if the link quality between the neighbouring BSs becomes worse, the computational complexity will increase. 26 ?1 10 pl=0.05 p =0.10 l ?2 p =0.15 10 l p =0.20 Stop Criteria ? l ?3 10 ?4 10 ?5 10 ?6 10 0 200 400 600 800 1000 Iteration 1200 1400 1600 1800 2000 Figure 5: The convergence speed of Algorithm 3 under di?erent link failure probability 6. Conclusion In this paper, we focus on maximizing the downlink system of 5G UDN. First, we formulate a constrained EE maximization problem and translate the primal problem into a convex form based on the fractional programming theory. We adopt a centralized algorithm based on Dinkelbachs procedure to solve this problem. However, the centralized algorithm may be ine?cient and has high computational cost in our considered 5G UDN scenario, where the number of BSs and user are extremely large. Therefore, we further propose a distributed algorithm based on ADMM. For this distributed algorithm, the local and dual variables are updated independently and in parallel by all BSs, and the global variables are updated by the coordination and information exchanging between BSs. The simulation results show that the running time of the distributed algorithms is at least one order of magnitude less than that of the centralized algorithm. Moreover, because of the widespread noise in communication systems, information exchanging between BSs may be imperfect. For this case, we 27 propose to update the global variables only when the link does not fail, and prove that the modi?ed robust algorithm converges to the optimal solution of the primal problem almost surely. Even for the case that the failure probability is as high as 0.2, the simulation results show that the proposed robust distributed algorithm can still coverage to the optimal value at the cost of a little increase of running time and iteration numbers . Appendix A. Proof of Theorem 1 According to the expression of g(и) shown in Eq.(8), ??g(exp(q)) can be viewed as the negative log-sum-exp. From the expressions of Eq.(9), Eq.(3) and Eq.(5), the concavity of f?(exp(q)) follows the fact that the log-sum-exp function is convex [22]. By combining the power model Eq.(5), the ?rst constraint of Eq.(12) has the form of log-sum-exp. According to [22], it is a convex constraint. The last constraint of Eq.(12) can be converted to an a?ne constraint of p by means of basic convex transformations. Therefore, problem Eq.(12) is a concave function of q. Appendix B. Details of problem Eq.(17) The ?rst constraint of the primal problem denotes the maximum power expenditure given in Eq.(5). Let?s introduce the transformation q = ln p and drop the subscript k, we get ?n | exp(qn )| + ?n /M ? P?n . Obviously, the left side is a linear function of exp(q), which is expressed as L1 (и) ? P?n for conciseness. The second constraint of the primal problem represents the QoS constraint given in Eq.(4). By some basic transformations, we can get K ? ? ( [m] ) [m] ( ) [m] exp qnk ,ik Gnk ,ik ? ?? exp q[m] nl Gnl ,ik ? ??, k=1 nl ?Nl 28 where ?? = 2 [m] k ,ik ?n ? 1. Therefore, the left side of the above equation is a?ne function of exp(q), which is expressed as L2 (и) ? ?? for conciseness. By de?ning ? L1 (exp(qn )) ? P?n ? L2 (exp(qn )) ? ?? ? , qn ? Xn , we get Eq.(17). According to Theorem 1, Xn is convex. Appendix C. Proof of Theorem 2 The proof of Theorem 2 follows a similar procedure of Appendix C in [31]. The main di?erence is that our model deals with the case of communication link failure with probability pl , while [33] considers the case of BSs disable with [s] [s] probability ?n . In this part, we will show that the iterative variables {qn , yn } satisfy the Karush-Kuhn-Tucker (KKT) conditions of problem Eq.(18) as s ? ? almost surely. The KKT conditions of problem Eq.(18) are ?n (q?n ) ? ?(qn ) + ETn y ? (q?n ? qn ) ? 0, ?qn ? Xn , n ? V, N ? En q?i = b. (C.1a) (C.1b) i=1 All the iterative variables for iteration step s are: { q?[s] n = arg min ?n (qn ) + ? qn ?Xn [s?1] (yn + j?N?n y?[s] n = [s?1] yj ? 1 4N ? (En qn 2 } )2 , ?n ? V, ? 1 N z)+ 1 ( ? [s?1] 1 ) 1 [s?1] z) , ?n ? V, (yn + yj ) + (En q[s] n ? 2N ? N (C.2) (C.3) j?N?n { [s?1] [s?1] } un,j 2 [s] vn,j 2 [s] , e?n,j = arg min y[s] ? e + + y ? e + n,j n,j n ? 2 j ? 2 en,j 29 (C.4) [s] [s?1] + ? (y[s] n ? en,j ), ?n ? V, [s] [s?1] + ? (y[s] n ? en,j ), ?n ? V. u?n,j = un,j vn,j = vn,j [s] (C.5) [s] (C.6) [s] They coincide with Algorithm 2 for ?j ? N?n , i.e., [n] q?n[s] = qn , ?n ? V, [s] [s] [k] [k] [k] [k] [s] e?n,j = en,j , u?n,j = un,j , v?n,j = vn,j , ?n ? V, j ? N?n . (C.7) The Lagrangian function of Eq.(18) is L(q, y) = N ? ?n (qn ) + yT ( n=1 N ? n=1 We de?ne Ge (e[s] , y) , En qn ? z). N ? ? 1 [s] ||en,j ? y||22 , p l n=1 (C.8) (C.9) j?N?n Gu (u[s] , u? ) , N ? ? 1 [s] ||un,j ? u?n,j ||22 , p l n=1 (C.10) j?N?n and the historical event set Js?1 , {q[l] , u[l] , N?n[s] , l = s ? 1, и и и , 0}. (C.11) Based on Lemma 1 of [31] which bounds the gap between L(q?[s] , y) and the optimal problem Eq.(18), we have ? E[Ge (e[s] , y)|Js?1 ] + ?1 E[Gu (u[s] , u? )|Js?1 ] ? ? Ge (e[s?1] , y) + ?1 Gu (u[s?1] , u? ) ? ? ||e?[s] ? e[s?1] ||22 ? ?1 ||u?[s] ? u[s?1] ||22 . 30 (C.12) Then, by the lemma of Robbins and Siegmmund [34], we know that ||e?[s] ? e[s?1] ||22 ? 0, a.s., ||u?[s] ? u[s?1] || ? 0, a.s. (C.13) Therefore, by applying Eq.(C.13) to Eq.(C.5), we obtain that [s] y?[s] n ? e?n,j ? 0, a.s. ?n, j. (C.14) Subsequently, we show that N ? n=1 En q[s] n ? z ? 0, a.s. as s ? ?. (C.15) From Lemma 1 of [33] En q?[s] n = z/N + 2? ? j?Nn [s] [s?1] (e?n,j ? en,j ) + ? j?Nn [s] [s] (u?n,i + v?n,j ), ?n, s we have the following result ? [s] [s] [s] En qn ? z [s] En qn + j?N?n \N?n j?N?n ? ? [s] [s? ] [s? ] ) 2? [s] (e?n,j ) + [s] (e?n,j ? en,j ) n?V i?V j?N?n j?N?n \N?n ? ? [s? ] [s? ] [s] [s] + n?V j?N?n \N? [s] (u?n,j ? u?j,n ? u?n,j + u?j,n ), n ?N [s] En q n ? z = (? ? n=1 = ? (C.16) where s? is a iteration number which satis?es s? < s. Substituting Eq.(25), Eq.(26), Eq.(29), and Eq. (31) into the above equation, we have [s] [s?1] u?n,j ? u?n,j = ? [s?1] ? u?[s] n,j ? un,j , ? [s] (n, j) ? N?n[s] , [s?1] [s?2] (u?n,j ? un,j ) + (un,j [s?1] ? u?n,j ), otherwise (C.17) ? 0 a.s. [s] [s?1] Therefore, by applying Eq.(C.17), e?n,j ? en,j ? 0, a.s. ?n, j and Eq.(C.13) to Eq.(C.16), we get the conclusion that Eq.(C.15) is true. 31 Then, we will show that [s] T [s] ?n (q[s] n ) ? ?n (qn ) + (yn ) En (qn ? qn ) ? 0, ?qn ? Xn , ?n, s. (C.18) From Lemma 1 of [33], we have [s] [s] T ?n (q?[s] n ) ? ?n (qn ) + (yn ) En (qn ? qn ) ? ? ? ] [s ] T [s ] = ?n (q?[s n ) ? ?n (qn ) + (y?n ) En (q?n ? qn ) ? 0, ?qn ? Xn , ?n, s. So, Eq.(C.18) is true for all n, s. In summary, from Eq.(C.15) and Eq.(C.18), [s] [s] it is almost surely that qn , ?n and yn , ?n satisfy the KKT conditions as s ? ?. Therefore, the solution qn , ?n generated by Algorithm 3 converges to the optimal solution of problem Eq.(18) as s ? ? almost surely. Reference [1] J. G. Andrews, S. Buzzi, C. Wan, and S. V. Hanly, etc., ?What will 5G be?? IEEE J. Select. Areas Commun., vol. 32, no. 6, pp. 1065-1082, Jun. 2014. [2] S. Buzzi, I. Chih-Lin, T. E. Klein, H. V. Poor, C. Yang, and A. Zappone, ?A survey of energy-e?cient techniques for 5G networks and challenges ahead,? IEEE J. Select. Areas Commun., vol. 34, no. 4, pp. 697-709, Apr. 2016. [3] Kamel, Mahmoud, W. Hamouda, and A. Youssef. ?Ultra-dense networks: a survey,? IEEE Commun. Surveys and Tutorials. vol. 18, no. 4, PP. 25222545, Nov. 2016. [4] Y. Gao, L. Dai, and X. Hei, ?Thoughput optimization of multi-BSS IEEE 802.11 networks with universal frequency reuse,? IEEE Trans. on Commun. vol. 65, no. 8, pp. 3399-3414, Aug. 2017. [5] E. Bjornson, M. Kountouris, and M. Debbah, ?Massive MIMO and small cells: Improving energy e?ciency by optimal soft-cell coordination,? in Proc. 20th Int. Conf. Telecommun. (ICT), pp. 1-5, May 2013. 32 [6] S. K. Joshi, M. Codreanu, and M. Latva, ?Distributed resource allocation for MISO downlink systems via the alternating direction method of multipliers,? EURASIP J. Wireless Commun. Netw., vol. 2014, pp. 1-19, Jan. 2014. [7] W. Liao, M. Hong, Y. Liu, and Z. Luo, ?Base station activation and linear transceiver design for optimal resource management in heterogeneous networks,? IEEE Trans. Signal Process., vol. 62, no. 15, pp. 3939-3952, Aug. 2014. [8] M. Grant and S. Boyd, CVX: Matlab software for disciplined convex programming. Jun. 2009 [Online]. Available: http://stanford.edu/ boyd/cvx. [9] Zappone, Alessio, and E. Jorswieck. ?Energy e?ciency in wireless networks via fractional programming theory.? Now Publishers Inc. 2015. [10] S. Buzzi, I. Chih-Lin, E. T. Klein, H. V. Poor, C. Y. Yang, and A. Zappone, ?A survey of energy-e?cient techniques for 5G networks and challenges ahead,? IEEE J. Select. Areas Commun., vol. 34, no. 4, pp. 697-709. Apr. 2016. [11] A. Zappone, E. Bjornson, L. Sanguinetti, and E. Jorswieck, ?Globally optimal energy-e?cient power control and receiver design in wireless networks,? IEEE Trans. Signal Process., vol. 65, no. 11, pp. 2844-2859, Feb. 2017. [12] L. Venturino, A. Zappone, C. Risi, and S. Buzzi, ?Energy-e?cient scheduling and power allocation in downlink ofdma networks with base station coordination,? IEEE Trans. Wireless Commun., vol. 14, no. 1, pp. 1-14, Jan. 2015. [13] G. D. Yu, Y. H. Jiang, L. K. Xu, and G. Y. Li, ?Multi-objective energye?cient resource allocation for multi-rat heterogeneous network,? IEEE J. Select. Areas Commun., vol. 33, no. 10, pp. 2118-2127, Oct. 2015. [14] Tsiropoulou, Eirini Eleni, P. Vamvakas, and S. Papavassiliou. ?Supermodular game-based distributed joint uplink power and rate allocation in two-tier 33 femtocell networks.? IEEE Trans. on Mobile Comput. vol. 16, no. 19, pp. 2656-2667, Sept. 2017. [15] E. E. Tsiropoulou, G. Katsinis, A. Filios, and S. Papavassiliou, ?On the problem of optimal cell selection & uplink power control in open access multi-service two-tier femtocell networks,? in Ad-hoc, Mobile and Wireless Networks (LNCS) Sprigner, Jun 2014. [16] E. E. Tsiropoulou, G. Katsinis, P. Vamvakas, and S. Papavassiliou, ?E?cient uplink power control in multi-service two-tier femtocell networks via a game theoretic approach,? IEEE International Workshop on ComputerAided Modeling Analysis and Design of Communication Links and Networks (CAMAD), Berlin, 2013. [17] H. P. Benson. ?Global optimization of noonlinear sums of ratios.? Journal of Mathematical Analysis and Applications, vol. 263, no. 1, pp.301-315, 2001. [18] H. P. Beson. ?Solving sum of ratios fractional programs via concave minimization. Journal of Optimization Theory and Applications, vol. 135, pp. 1-17, 2007. [19] S. Boyd, N. Parikh, E. Chu, B. Peleato, and J. Eckstein, ?Distributed optimization and statistical learning via the alternating direction method of multipliers,? Fundations and Trends in Machine Learning, vol. 3, no. 1, pp. 1-122, 2011. [20] Wei Li, Jun Wang, Guosheng Yang, etc., ?E?cient resource allocation for energy e?ciency maximization in ultra-dense network.? in Proc. IEEE GlOBECOM, Singapore, Dec. 4-8. [21] A. Goldmith, Wireless Communications. Cambridge, U.K.: Cambridge Univ. Press, 2005. [22] E. Bjornson, L. Sanguinetti, and M. Kountouris, ?Deploying dense networks for maximal energy e?ciency: small cell meet massive MIMO,? IEEE J. Select. Areas Commun., vol. 34, no. 4, pp. 832-847, Apr. 2016. 34 [23] J. Papandriopoulos and J. S. Evans, ?Low-complexity distributed algorithms for spectrum balancing in multi-user DSL networks,? in Proc. IEEE ICC, Istanbul, Turkey, Jun. 2006, pp. 3270-3275. [24] C. Saraydar, N. B. Mandayam, and D. Goodman, ?E?cient power control via pricing in wireless data networks,? IEEE Trans. Commun., vol. 50, no.2, pp. 291-303, Feb. 2002. [25] Kolda, Tamara G., and B. W. Bader. ?Tensor decompositions and applications.? SIAM Review vol. 51, no. 3, pp. 455-500, 2009. [26] Lathauwer L. D., Moor B. D., Vandewalle J. ?A multilinear singular value decomposition,? SIAM J. Matrix Anal. Appl., vol. 21, no. 2, pp. 1252-1278, 2000. [27] D. P. Bertsekas, and J. N. Tsitsiklis, Parallel and Distributed Commputation: Numerical Methods. Upper Saddle River, NI, USA: Prentice-Hall, 1989. [28] D. P. Bertsekas, A. Nedic, and A. E. Ozdaglar, Convex Analysis and Optimization. Cambridge, MA, USA: Athena Scienti?c, 2003. [29] S. G. Nash, and A. Sofer, ?On the complexity of a practical interior-point method,? SIAM J. Optim., vol. 8, no. 3, pp. 833-849, 1998. [30] Borde, J., and J. P. Crouzeix. ?Convergence of a dinkelbach-type algorithm in generalized fractional programming.? Zeitschrift Fr Operations Research, vol. 31, no. 1, pp. 31-54, 1987. [31] W. Shi, Q. Ling, K. Yuan, G. Wu, and W. Yin, ?On the linear convergence of the ADMM in decentralized consensus optimization,? IEEE Trans. Signal Process., vol. 62, no. 7, pp. 1750-1761, Apr. 2014. [32] E. Wei, and A. Ozdaglar, ?On the O(1/K) convergence of asynchronous distributed alternating direction method of multipliers,? available on arxiv.org. 35 [33] Chang, Tsung Hui. ?A proximal dual consensus ADMM method for multiggent constrained optimization.? IEEE Trans. on Signal Processing, vol. 64, no. 14, pp. 3719-3734, July 2016. [34] E. E. Tsiropoulou, P. Vamvakas, G. Katsinis, S. Papavassiliou, ?Combined power and rate allocation in self-optimized multi-service two-tier femtocell networks,? Computer Communications, Elsevier, vol. 72, pp. 38-48, 2015. [35] Suh, Jung W., and Y. Kim. MATLAB and Parallel Computing Toolbox. Accelerating Matlab with GPUs. pp. 99-125, 2014. [36] B. R. Marks and G. P. Wright, ?A general inner approximation algorithm for non-covex mathematical programs,? Operations Research, vol. 26, no. 4, pp. 681-683, 1978. 36

1/--страниц