close

Вход

Забыли?

вход по аккаунту

?

j.comcom.2018.08.005

код для вставкиСкачать
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
Документ
Категория
Без категории
Просмотров
4
Размер файла
1 590 Кб
Теги
comcom, 005, 2018
1/--страниц
Пожаловаться на содержимое документа