# Relay Selection and Subcarrier-Pair Based Energy-Efficient Resource Allocation for Multirelay Cooperative OFDMA Networks

Authors: Wanming Hao; Shouyi Yang; Wanliang Hao
Journal: International Journal of Antennas and Propagation
 (2014)

---

## Abstract

Energy-efficient resource allocation is investigated for a relay-based multiuser cooperation orthogonal frequency division multiple access (OFDMA) uplink system with amplify-and-forward (AF) protocol for all relays. The objective is to maximize the total energy efficiency (EE) of the uplink system with consideration of some practical limitations, such as the individual power constraint for the users and relays and the quality of service (QoS) for every user. We formulate an energy-efficient resource allocation problem that seeks joint optimization of subcarrier pairing, relay selection, subcarrier assignment, and power allocation. Unlike previous optimization throughput models, we transform the considered EE problem in fractional form into an equivalent optimal problem in subtractive form, which is solved by using dual decomposition and subgradient methods. To reduce computation costs, we propose two low-complexity suboptimal schemes. Numerical studies are conducted to evaluate the EE of the proposed algorithms.


---

## Body

## 1. Introduction

Transmit diversity generally requires more than one antenna at the transmitter and receiver. However, many wireless devices are limited to single antenna because of size or hardware complexity. Cooperation communication is a promising solution to address this problem in various wireless systems, such as ad hoc and cellular networks [1, 2]. In contrast to traditional point-to-point or point-to-multipoint wireless communication, cooperation communication allows different users or nodes in a wireless system to share resources and create collaboration through distributed transmission; every piece of user’s information is sent not only by itself but also by the collaborating users or nodes [3]. Therefore, cooperative communication formulates a new form of space diversity to combat the negative effect of severe fading [4]. Cooperative communication can improve the overall system performance by improving the spectrum efficiency, extending the coverage area, and prolonging the network lifetime. Orthogonal frequency division multiple access (OFDMA) or multiuser orthogonal frequency division multiplexing (MU-OFDM) is the preferred multiple access scheme for high-speed wireless multiuser communication networks because of its high spectrum efficiency and resistance to multipath fading [5]. Moreover, several users’ signals are simultaneously transmitted over different subcarriers on each OFDM symbol to avoid interference between users. Thus, to improve system performance, studying optimal resource allocation in relay-assisted OFDMA communication system is important.Relaying protocols have three main types, namely, amplify-and-forward (AF), decode-and-forward (DF), and compress-and-forward (CF). In AF, the signal received by relay is amplified and retransmitted to the destination. The noise is also amplified at the relay. This protocol is simple and of low cost. In DF, the relay attempts to decode the received signal. If successful, DF reencodes the information and retransmits the signal. CF attempts to generate an estimate for the received signal. Hoping the estimated value provides some assistance in decoding the original codeword at the destination. Given the limited available space, we only study the energy-efficient resource allocation with AF protocol. The other relaying protocols will be studied in future works.Compared with previous studies on single-carrier relay networks or multicarrier noncooperation networks, more technical challenges exist in the study of multicarrier cooperation networks. We not only consider the relaying protocols (AF, DF, and CF) but also solve the problems about relay selection and power allocation between users and relays in relaying networks. Several results have been reported recently about relaying networks [6–14]. The optimal power allocation and subcarrier pairing under AF and DF relay links have been studied, and the optimality of ordered subcarrier pairing (OSP) for these two protocols without diversity under total power constraint has been proved [6]. However, multiple relays usually exist in a practical system; thus, subcarrier-to-relay assignment must be considered [8]. The authors in [9] attempted to solve subcarrier-to-relay assignment and subcarrier pairing problems in multirelay OFDM system with a single user. Individual and total power constraints were all considered, but multiple users were not studied. In [10], the authors studied optimal relay selection, power allocation, and subcarrier assignment scheme under total power constraint. However, individual power constraint and subcarrier pairing were not considered. Optimal power and time allocation under a long-term total power constraint in OFDM-based linear multihop relay networks with DF protocol were considered in [11, 12]. In [13], the authors considered that a subcarrier may carry a signal for different services. They also proposed maximizing the weighted sum rate by joint optimal subcarrier pairing and power allocation under total and individual power constraints for the source and relay. Cross-layer scheduling for the downlink of AF relay-assisted OFDMA networks under imperfect channel-state information at the transmitter in slow fading was introduced in [14]. The authors optimized the rate, power, and subcarrier allocation to maximize the system goodput.We have discussed only the throughput maximum problem in resource allocation for relay-assisted cooperative OFDMA systems. However, explosively growing data traffic and the requirement for ubiquitous access have triggered the escalation of energy, which results in increased greenhouse gas emission [15]. Therefore, energy efficiency (EE) has become an important problem in later development. Besides, mobile terminals cannot connect to an external charger; EE (bits/Hz/Joule) may be a better performance metric than system throughput (bits/s/Hz) in evaluating the performance of wireless communication systems [16–18]. A number of studies on energy-efficient resource allocation have been reported [19–24]. Power adaptation for maximizing the EE in downlink and uplink OFDMA cellular networks was studied in [19]. For downlink transmission, the total EE was maximized; for the uplink case, the minimum individual EE was maximized. In [20], the fundamental tradeoff between EE and spectral efficiency (SE) in downlink OFDMA systems was studied. In [21], the authors transformed the considered EE problem in fractional form into an equivalent optimal problem in subtractive form. They also studied the resource allocation for energy-efficient communication in multicell OFDMA downlink networks. References [22, 23] used the Dinkelbach method to solve the EE maximum problem in OFDM systems and found the optimal resource allocation. The literature in [24] used the resembled solution in [17] to deal with the energy-efficient resource allocation problem in a multiuser OFDMA system. Users’ quality-of-service (QoS) requirements were also considered.For relaying networks, limited study about EE exists. The authors in [25] formulated EE optimization problem by joint subcarrier assignment, bit, and power allocation. However, they provided only near-optimal and suboptimal resource schemes to maximize the overall EE and did not find the global optimum. Power constraints for sources and relay were also not considered. The power allocation to maximize EE for a two-hop AF relay link under QoS requirement has also been investigated [26]; single user and relay have been studied, but the subcarrier pairing problem has not been considered.Considerable research exists about the optimal resource allocation mechanisms in relaying networks, including power allocation, subcarrier pairing, and relay selection; see, for example, [6–14]. However, these problems have only been studied in the case of throughput maximization (supposing throughput as objective function). Optimal resource allocation mechanisms will be changed when we consider the system EE (supposing EE as objective function). Hence, we must provide a new optimal resource allocation mechanism to meet the requirements of systems. In this paper, we address the energy-efficient resource allocation in AF-based cooperative two-hop multirelay uplink OFDMA system. Considering an actual situation, individual power constraint for the users and relays is applied. QoS for every user should be considered. Then, the subcarrier pairing, relay selection, subcarrier assignment, and power allocation problem are formulated as a joint optimization problem with the objective of maximizing the uplink system total EE. Given integer assignment variables, the optimal EE problem falls within the scope of combinatorial programming, which is NP-hard. Thus, we transform the EE problem in fractional form into an equivalent optimal problem in subtractive form, which is solved by using dual decomposition and subgradient methods. We also propose two suboptimal algorithms to trade off performance and complexity.The remainder of this paper is organized as follows. Section2 introduces the system model and formulates the optimization EE problem. Section 3 presents the optimal resource allocation algorithm. Section 4 shows suboptimal algorithms with low complexity. Section 5 demonstrates simulation results to verify the performance of the proposed algorithms. Section 6 concludes the paper.


## 2. System Model and Problem Formulation

We consider a multirelay-assisted cooperation OFDMA system, as shown in Figure1. K users (1
≤
k
≤
K) and N relays (1
≤
n
≤
N) are assumed. The relays are shared by all users. The total number of the subcarriers used is M (1
≤
m
≤
M) in the single cell system. Broadband channel is assumed to be frequency-selective Rayleigh fading. All channel-state information is assumed to be perfectly known. Each relay node operates in a time-division half-duplex mode with AF protocol. Therefore, two phases are needed for the communication between the user and base station. In the first phase, the user transmits the signal to the base station, which is overheard by the selected relay as well. In the second phase, the selected relay forwards the received signal to the base station using AF cooperation protocol. n is supposed to receive the signal from user k on subcarrier m in the first phase, and the signal is then forwarded on subcarrier m
′ in the second phase; the subcarrier m may not be the same as m
′, and they are thus called a subcarrier pair (m, m
′) [9].Figure 1
System model.The noise variances of the source-to-relay (SR) links, relay-to-destination (RD) links, and source-to-destination (SD) links are denoted byσ
k
,
n
2, σ
n
,
D
2, and σ
k
,
D
2, respectively. The channel coefficients of S
→
R and S
→
D links on the subcarrier m in the first phase are denoted by h
k
,
n
m and h
k
,
D
m, respectively, and that of the R
→
D links on the subcarrier m
′ in the second phase is denoted by h
n
,
D
m
′. The efficient channel gain of the three links on the subcarrier m or m
′ for user k and relay n can be denoted by α
k
,
n
m
=
|
h
k
,
n
m
|
2
/
σ
k
,
n
2, α
k
,
D
m
=
|
h
k
,
D
m
|
2
/
σ
k
,
D
2, and α
n
,
D
m
′
=
|
h
n
,
D
m
′
|
2
/
σ
n
,
D
2, respectively. The channel variances of S
→
R, S
→
D, and R
→
D links are denoted by δ
k
,
n
2, δ
k
,
D
2, and δ
n
,
D
2, respectively.In this relaying system, the base station controls all users and relays. The resource allocation information, including subcarrier pairing, relay selection, subcarrier assignment, and power allocation, is sent to users and relays by the base station via downlink control channel.The achievable rate for thekth user in the subcarrier pair (m, m
′) when the nth relay is selected is given by
(1)
r
k
,
n
m
,
m
′
=
1
2
lo
g
2
(
1
+
p
S
,
k
m
α
k
,
D
m
+
p
S
,
k
m
α
k
,
n
m
p
R
,
n
m
′
α
n
,
D
m
′
1
+
p
S
,
k
m
α
k
,
n
m
+
p
R
,
n
m
′
α
n
,
D
m
′
)
,
where p
S
,
k
m is the transmit power of the kth user in the mth subcarrier and p
R
,
n
m
′ is the transmit power of the nth relay in the m
′th subcarrier. The factor 1/2 is due to the two-phase transmission.r
k
,
n
m
,
m
′ is not jointly concave in p
S
,
k
m and p
R
,
n
m
′. To make the problem tractable, we adopt the following approximation:
(2)
r
k
,
n
m
,
m
′
≈
1
2
lo
g
2
(
1
+
p
S
,
k
m
α
k
,
D
m
+
p
S
,
k
m
α
k
,
n
m
p
R
,
n
m
′
α
n
,
D
m
′
p
S
,
k
m
α
k
,
n
m
+
p
R
,
n
m
′
α
n
,
D
m
′
)
.The above approximation is jointly concave inp
S
,
k
m and p
R
,
n
m
′, as proved in Appendix A. This approximation is based on the assumption that the signal is amplified and forwarded by the relay under a high signal-to-ratio (SNR) condition. Such approximation has been used in the literatures [7, 9, 27]. However, in a low-SNR regime, [27] proved that the resource allocation almost reaches the true optimal capacity by optimizing the rate (2).Our objective is to maximize the uplink system total EE subject to a set of constraints. The relay selection and subcarrier assignment constraints are as follows:(3)
∑
k
=
1
K
∑
n
=
1
N
ρ
k
,
n
m
,
m
′
=
1
,
ρ
k
,
n
m
,
m
′
∈
{
0,1
}
,
∀
m
,
m
′
,
where ρ
k
,
n
m
,
m
′
=
1 indicates that user n uses relay k as a relay in the subcarrier pair (m, m
′); otherwise, ρ
k
,
n
m
,
m
′
=
0.γ
m
,
m
′ denotes the indicator for subcarrier pairing. When γ
m
,
m
′
=
1, subcarrier m in the first phase is paired with subcarrier m
′ in the second phase; otherwise, γ
m
,
m
′
=
0. Given that each subcarrier in the first phase can be paired with only one subcarrier in the second phase, the binary variables {
γ
m
,
m
′
} must satisfy the following equation:
(4)
∑
m
=
1
M
γ
m
,
m
′
=
1
,
∑
m
′
=
1
M
γ
m
,
m
′
=
1
,
∀
m
,
m
′
.The individual power constraint of the users and relays can be expressed as follows:(5)
User power constraint:
∑
m
=
1
M
p
S
,
k
m
≤
P
S
,
k
,
∀
k
,
Relay power constraint:
∑
m
′
=
1
M
p
R
,
n
m
′
≤
P
R
,
n
,
∀
n
.Aside from transmit power, the energy consumption also includes circuit energy consumption [28] and overall power consumption. The power consumptions of user n and relay k are modeled as follows:
(6)
user power consumption:
P
S
,
k
total
=
ξ
∑
m
=
1
M
p
S
,
k
m
+
P
C
,
S
k
,
relay power consumption:
P
R
,
n
total
=
ξ
∑
m
′
=
1
M
p
R
,
n
m
′
+
P
C
,
R
n
,
where ξ is the reciprocal of drain efficiency of power amplifier. We assume that the reciprocal is the same for all the users and relays.The optimization EE problem can be formulated as(7)
max
⁡
⁡
EE
=
(
∑
k
=
1
K
w
k
∑
n
=
1
N
∑
m
=
1
M
∑
m
′
=
1
M
ρ
k
,
n
m
,
m
′
γ
m
,
m
′
r
k
,
n
m
,
m
′
)
×
(
ξ
∑
k
=
1
K
∑
n
=
1
N
∑
m
=
1
M
∑
m
′
=
1
M
ρ
k
,
n
m
,
m
′
γ
m
,
m
′
(
p
S
,
k
m
+
p
R
,
n
m
′
)
d
d
d
d
i
i
+
∑
k
=
1
K
P
C
,
S
k
+
∑
n
=
1
N
P
C
,
R
n
)
-
1
,
which is subject to
(8)
ρ
k
,
n
m
,
m
′
∈
{
0,1
}
,
∀
k
,
n
,
m
,
m
′
,
(9)
∑
k
=
1
K
∑
n
=
1
N
ρ
k
,
n
m
,
m
′
=
1
,
∀
m
,
m
′
,
(10)
γ
m
,
m
′
∈
{
0,1
}
,
∀
m
,
m
′
,
(11)
∑
m
=
1
M
γ
m
,
m
′
=
1
,
∑
m
′
=
1
M
γ
m
,
m
′
=
1
,
∀
m
,
m
′
,
(12)
∑
m
=
1
M
p
S
,
k
m
≤
P
S
,
k
,
∀
k
,
(13)
∑
m
′
=
1
M
p
R
,
n
m
′
≤
P
S
,
n
,
∀
n
,
(14)
R
S
,
k
≥
Q
S
,
k
,
∀
k
,
(15)
p
S
,
k
m
≥
0
,
p
R
,
n
m
′
≥
0
,
∀
k
,
n
,
m
,
m
′
,
where constraint (14) denotes the minimum QoS requirements for the users and R
S
,
k
=
∑
n
=
1
N
∑
m
=
1
M
∑
m
′
=
1
M
r
k
,
n
m
,
m
′. The predetermined weights, w
k, can provide a certain level of priority and/or fairness among users.


## 3. Optimal Resource Allocation

The integer assignment variablesρ
k
,
n
m
,
m
′and γ
m
,
m
′ above EE problem are generally NP-hard for optimal solution. If we consider all possibilities of subcarrier pairings and subcarrier-pair-to-user and relay assignments, then the complexity is high with large K, N, and M. The fraction further complicates the problem. Hence, we apply an effective method to solve this challenging problem.


### 3.1. Equivalence Transformation of the Optimization Problem

For the fraction objective function in (7), we first rewrite problems (7)–(15) in the following compact form:
(16)
maximize
ρ
,
γ
,
p
∈
π
R
(
ρ
,
γ
,
p
)
P
(
ρ
,
γ
,
p
)
,
where ρ
=
{
ρ
k
,
n
m
,
m
′
}, γ
=
{
γ
m
,
m
′
}, and p
=
{
p
S
,
k
m
,
p
R
,
n
m
′
}. π denotes the feasible domain defined by (8)–(15). R
(
ρ
,
γ
,
p
) and P
(
ρ
,
γ
,
p
) are the numerator and denominator in (7), respectively. Problem (16) is a nonlinear fractional problem. According to [29], we transform the considered EE problem in fractional form into an equivalent optimal problem in subtractive form. We then define the following parameter problem:
(17)
F
(
q
)
≜
maximize
ρ
,
γ
,
p
∈
π
{
R
(
ρ
,
γ
,
p
)
-
q
P
(
ρ
,
γ
,
p
)
}
,
where q
∈
R is treated as a parameter. We have the following theorems, all of which are proved in Appendix B.Theorem 1.
F
(
q
) is strictly monotonically decreasing for q.Theorem 2.
F
(
q
)
=
0 has a unique solution.Theorem 3.
Consider(18)
q
0
=
R
(
ρ
0
,
γ
0
,
p
0
)
P
(
ρ
0
,
γ
0
,
p
0
)
=
max
⁡
ρ
,
γ
,
p
∈
π
⁡
R
(
ρ
,
γ
,
p
)
P
(
ρ
,
γ
,
p
)
only
if
F
(
q
0
)
=
F
(
q
0
,
(
ρ
0
,
γ
0
,
p
0
)
)
=
max
⁡
ρ
,
γ
,
p
∈
π
⁡
{
R
(
ρ
,
γ
,
p
)
-
q
0
(
ρ
,
γ
,
p
)
}
=
0
.Based on the above theorems, we can use binary search method to findF
(
q
)
=
0 and the optimal solution for the primal problem. Therefore, the difficulty is to solve T
(
q
) for a given q. The optimization problem is
(19)
max
⁡
ρ
,
γ
,
p
∈
π
R
(
ρ
,
γ
,
p
)
-
q
(
ρ
,
γ
,
p
)
.Obtaining the joint optimalρ
*, γ
*, and p
* for (19) requires solving a mixed integer programming problem. Therefore, finding the optimal solution for problem (19) requires searching through all possible users, relays, and subcarrier allocation, which is a complex task when the system is large. The literature in [30] showed that the duality gap of a nonconvex resource allocation problem that satisfies the time-sharing condition is nearly zero with a large number of subcarriers in a multicarrier system. Thus, we solve this problem by using the Lagrange dual method.


### 3.2. Dual Problem

The Lagrange dual function of problem (19) can be written as
(20)
g
(
λ
,
μ
,
υ
)
=
max
⁡
{
ρ
,
γ
}
∈
Ω
L
(
ρ
,
γ
,
p
,
λ
,
μ
,
υ
)
,
(21)
L
(
ρ
,
γ
,
p
,
λ
,
μ
,
υ
)
=
∑
k
=
1
K
∑
n
=
1
N
∑
m
=
1
M
∑
m
′
=
1
M
w
k
2
ρ
k
,
n
m
,
m
′
γ
m
,
m
′
d
d
d
d
d
d
d
d
d
d
d
i
×
lo
g
2
(
1

+
p
S
,
k
m
α
k
,
D
m

+
p
S
,
k
m
α
k
,
n
m
p
R
,
n
m
′
α
n
,
D
m
′
p
S
,
k
m
α
k
,
n
m
+
p
R
,
n
m
′
α
n
,
D
m
′
)
-
q
(
ξ
∑
k
=
1
K
∑
n
=
1
N
∑
m
=
1
M
∑
m
′
=
1
M
ρ
k
,
n
m
,
m
′
γ
m
,
m
′
(
p
S
,
k
m
+
p
R
,
n
m
′
)
d
d
d
d
d
d
+
∑
k
=
1
K
P
C
,
S
k
+
∑
n
=
1
N
P
C
,
R
n
)
+
∑
k
=
1
k
λ
k
(
P
S
,
k
-
∑
m
=
1
M
p
S
,
k
m
)
+
∑
n
=
1
N
μ
n
(
P
S
,
n
-
∑
m
′
=
1
M
p
R
,
n
m
′
)
+
∑
k
=
1
k
υ
k
(
R
S
,
k
-
Q
S
,
k
)
,
where Lagrange is given in (21).In (20), λ
=
(
λ
1
,
λ
2
,
…
,
λ
K
)
≥
0, μ
=
(
μ
1
,
μ
2
,
…
,
μ
N
)
≥
0, and υ
=
(
υ
1
,
υ
2
,
…
,
υ
K
)
≥
0 are the vectors of the dual variables associated with the individual power constraint for the users, individual power constraint for the relays, and individual rate constraint for the users, respectively. Hence, the dual optimization problem is given by
(22)
min
⁡
g
(
λ
,
μ
,
υ
)
,
i
i
s.t.
λ
,
μ
,
υ
≥
0
.The literature in [31] proved that a dual function is always convex. Therefore, subgradient-based methods can be used to minimize g
(
λ
,
μ
,
υ
) with guaranteed convergence. Dual variables can be updated in parallel as follows:
(23)
λ
k
(
d
+
1
)
=
[
λ
k
(
d
)
+
o
(
d
)
(
∑
m
=
1
M
p
S
,
k
m
-
P
S
,
k
)
]
+
μ
n
(
d
+
1
)
=
[
μ
n
(
d
)
+
θ
(
d
)
(
∑
m
′
=
1
M
p
R
,
n
m
′
-
P
S
,
n
)
]
+
υ
k
(
d
+
1
)
=
[
υ
k
(
d
)
+
ϑ
(
d
)
(
Q
S
,
k
-
R
S
,
k
)
]
+
.o
(
d
), θ
(
d
), and ϑ
(
d
) are used as the step size, and d is the iteration index. To guarantee optimal dual variable convergence, the step size is chosen following the diminishing step size policy [32].


### 3.3. Optimizing Primal Variables with Given Dual Variables

Computing the dual functiong
(
λ
,
μ
,
υ
) involves determining the optimal ρ, γ, and p at given dual points λ, μ, and υ. Therefore, we present the detailed solution procedure in three phases.


#### 3.3.1. Finding the Optimalp for Fixed ρ and γ

For the fixedρ and γ, we rewrite (20) as
(24)
g
(
λ
,
μ
,
υ
)
=
max
⁡
{
ρ
,
γ
}
∈
Ω
∑
k
=
1
K
∑
n
=
1
N
∑
m
=
1
M
∑
m
′
=
1
M
L
k
,
n
m
,
m
′
+
∑
k
=
1
k
λ
k
P
S
,
k
+
∑
n
=
1
N
μ
n
P
S
,
n
+
q
(
∑
k
=
1
K
P
C
,
S
k
+
∑
n
=
1
N
P
C
,
R
n
)
-
∑
k
=
1
k
υ
k
Q
S
,
k
,
where
(25)
L
k
,
n
m
,
m
′
≜
w
k
2
(
1
+
υ
k
)
×
lo
g
2
(
1
+
p
S
,
k
m
α
k
,
D
m
+
p
S
,
k
m
α
k
,
n
m
p
R
,
n
m
′
α
n
,
D
m
′
p
S
,
k
m
α
k
,
n
m
+
p
R
,
n
m
′
α
n
,
D
m
′
)
-
(
q
ξ
+
λ
k
)
p
S
,
k
m
-
(
q
ξ
+
μ
n
)
p
R
,
n
m
′
.A detailed derivation is given in AppendixC.According to the Lagrange dual decomposition method, the optimal power allocation can be determined by solving the following problem:(26)
max
⁡
⁡
L
k
,
n
m
,
m
′
p
S
,
k
m
≥
0
,
p
R
,
n
m
′
≥
0
,
∀
k
,
n
,
m
,
m
′
.AppendixA indicates that L
k
,
n
m
,
m
′ is a joint concave function of (
p
S
,
k
m
,
p
R
,
n
m
′
). Applying the Karush-Kuhn-Tucker (KKT) conditions [28], we can obtain the following optimal power allocation:(27)
p
S
,
k
m
=
{
b
k
,
n
m
,
m
′
p
R
,
n
m
′
,
if
p
R
,
n
m
′
>
0
(
w
k
(
1
+
υ
k
)
2
ln
⁡
2
(
q
ξ
+
λ
k
)
-
1
α
k
,
D
m
)
+
if
p
R
,
n
m
′
=
0
,
(28)
p
R
,
n
m
′
=
{
(
w
k
(
1
+
υ
k
)
2
ln
⁡
2
(
α
k
,
n
m
α
n
,
D
m
′
2
+
(
α
k
,
D
m
-
(
2
(
q
ξ
+
λ
k
)
ln
⁡
2
)
/
(
w
k
(
1
+
υ
k
)
)
)
(
α
k
,
n
m
b
k
,
n
m
,
m
′
+
α
n
,
D
m
′
2
)
2
(
α
k
,
n
m
b
k
,
n
m
,
m
′
+
α
n
,
D
m
′
2
)
2
(
α
k
,
D
m
α
k
,
n
m
α
n
,
D
m
′
)
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
d
d
d
i
i
i
×
(
α
k
,
n
m
b
k
,
n
m
,
m
′
+
α
n
,
D
m
′
2
)
2
)
i
i
i
i
×
(
b
k
,
n
m
,
m
′
(
q
ξ
+
λ
k
)
(
α
k
,
n
m
b
k
,
n
m
,
m
′
+
α
n
,
D
m
′
)
d
d
d
d
d
×
(
α
k
,
D
m
α
k
,
n
m
b
k
,
n
m
,
m
′
+
α
n
,
D
m
′
α
k
,
D
m
+
α
k
,
n
m
α
n
,
D
m
′
)
)
-
1
(
α
k
,
n
m
b
k
,
n
m
,
m
′
+
α
n
,
D
m
′
2
)
2
(
α
k
,
D
m
α
k
,
n
m
α
n
,
D
m
′
)
)
+
if
α
n
,
D
m
′
(
q
ξ
+
λ
k
)
>
α
k
,
D
m
(
q
ξ
+
μ
n
)
0
if
α
n
,
D
m
′
(
q
ξ
+
λ
k
)
≤
α
k
,
D
m
(
q
ξ
+
μ
n
)
.
(29)
b
k
,
n
m
,
m
′
=
α
n
,
D
m
′
(
(
q
ξ
+
μ
n
)
(
α
k
,
n
m
α
n
,
D
m
′
(
q
ξ
+
λ
k
)
-
α
k
,
n
m
α
k
,
D
m
(
q
ξ
+
μ
n
)
+
α
n
,
D
m
′
α
k
,
D
m
(
q
ξ
+
λ
k
)
)
+
α
k
,
D
m
(
q
ξ
+
μ
n
)
)
α
k
,
n
m
[
α
n
,
D
m
′
(
q
ξ
+
λ
k
)
-
α
k
,
D
m
(
q
ξ
+
μ
n
)
]
.And p
R
,
n
m
′ is given in (28).A detailed derivation is given in AppendixD.


#### 3.3.2. Finding the Optimalρ for Fixed γ

Substituting the optimal power allocation expressions (27) and (28) into (20), we can obtain an alternative expression of the dual without power variables as
(30)
g
(
λ
,
μ
,
υ
)
=
max
⁡
{
ρ
,
γ
}
∈
Ω
⁡
∑
k
=
1
K
∑
n
=
1
N
∑
m
=
1
M
∑
m
′
=
1
M
ρ
k
,
n
m
,
m
′
γ
m
,
m
′
H
k
,
n
m
,
m
′
(
λ
,
μ
,
υ
)
+
∑
k
=
1
k
λ
k
P
S
,
k
+
∑
n
=
1
N
μ
n
P
S
,
n
+
q
(
∑
k
=
1
K
P
C
,
S
k
+
∑
n
=
1
N
P
C
,
R
n
)
-
∑
k
=
1
k
υ
k
Q
S
,
k
,
where the function H
k
,
n
m
,
m
′
(
λ
,
μ
,
υ
) can be defined as follows:
(31)
H
k
,
n
m
,
m
′
=
w
k
(
1
+
υ
k
)
r
k
,
n
m
,
m
′
-
(
q
ξ
+
λ
k
)
p
S
,
k
m
-
(
q
ξ
+
μ
n
)
p
R
,
n
m
′
.Therefore, the functionH
k
,
n
m
,
m
′
(
λ
,
μ
,
υ
) is the optimal criterion for relay and user selection. We can interpret this criterion by using an economic form. The first term can be viewed as the rate obtained by selecting subcarrier pairing (m
,
m
′) by user k and relay n, such as our gross income in the business. The second term is the cost for the user’s power consumption. The third term is the cost for the relay’s power consumption. H
k
,
n
m
,
m
′
(
λ
,
μ
,
υ
) then represents our net profit. We should find the optimal k and n to maximize the profit. K
×
N profit matrix exists for every subcarrier pairing (m, m
′). We should find a maximum value in this matrix; thus, the sum of profit could be large. The optimal relay selection and subcarrier allocation should therefore be the maximum value in (31) and is given by
(32)
ρ
k
,
n
m
,
m
′
=
{
1
,
(
k
*
,
n
*
)
=
arg
max
⁡
k
,
n
⁡
H
k
,
n
m
,
m
′
0
,
otherwise
.In the operation, the optimal power allocation can first be computed by using (28) and (29). These power values can then be substituted into (31) to compute H
k
,
n
m
,
m
′. Finally, we need to find a maximum value in K
×
N profit matrix, and the user and relay pair will be determined.


#### 3.3.3. Finding the Optimalγ for Fixed ρ

After finding the optimalρ, we can obtain the corresponding dual function by substituting (32) into (20) as follows:
(33)
g
(
λ
,
μ
,
υ
)
=
max
⁡
γ
∈
Ω
∑
m
=
1
M
∑
m
′
=
1
M
γ
m
,
m
′
H
m
,
m
′
(
λ
,
μ
,
υ
)
+
∑
k
=
1
k
λ
k
P
S
,
k
+
∑
n
=
1
N
μ
n
P
S
,
n
+
q
(
∑
k
=
1
K
P
C
,
S
k
+
∑
n
=
1
N
P
C
,
R
n
)
-
∑
k
=
1
k
υ
k
Q
S
,
k
.We can then find the optimal subcarrier pairingγ. To this end, we launch the first term in (33) and define M
×
M profit matrix as follows:
(34)
[
γ
1,1
H
1,1
γ
1,2
H
1,2
⋯
γ
1
,
M
H
1
,
M
γ
2,1
H
2,1
γ
2,2
H
2,2
⋯
γ
2
,
M
H
2
,
M
⋮
⋮
⋱
⋮
γ
M
,
1
H
M
,
1
γ
M
,
2
H
M
,
2
⋯
γ
M
,
M
H
M
,
M
]
.We need to select one element in each row and each column in matrix (34) for the sum of profit to be large. Clearly, the problem is a standard linear assignment and can be solved by using the Hungarian method [33]. Ψ
(
m
) is defined as the subcarrier index in the second phase optimally paired with subcarrier m in the first phase. The optimal subcarrier pairing can be expressed as
(35)
γ
m
,
m
′
=
{
1
,
m
′
=
ψ
(
m
)
0
,
otherwise
.We have obtained the optimal variablesρ, γ, and p for given dual variables λ, μ, and υ. We can subsequently obtain the joint optimization problem by updating the dual variables.T
(
q
) is obtained according to the preceding analysis for a given q. However, we should find the optimal q to satisfy T
(
q
)
=
0. q
=
0, which yields T
(
q
)
>
0 and T
(
q
)
<
0 with q
→
∞. Thus, we can use binary search method to find the optimal q, as stated in Algorithm 1.Algorithm 1:Bisection-based energy-efficient resource allocation algorithm.
(1)Initialize  q
min
⁡ = 0, q
max
⁡ >> 0 with F
(
q
min
⁡
) > 0 and F
(
q
max
⁡
) < 0, ε.
(2) (i)Update  q
middle
←
(
q
min
⁡
+
q
max
⁡
)
/
2;
(ii)Initialization: λ
k, μ
n, and ν
k;
(a) Obtain the optimal power via (27) and (28);
(b) Obtain (m
,
m
′) via (35);
(c) Obtain (n
,
k) for given (m
,
m
′) via (32);
(d) Update the dual variablesλ
k, μ
n, and ν
k via (23);
(e) Repeat (a) → (d) until convergence;
(3) IfF
(
q
middle
)
>
0
,
q
min
⁡
←
q
middle; otherwise, q
max
⁡
←
q
middle;
(4)Repeat  Steps 2 and 3 until |
F
(
q
middle
)
|
<
ε.


## 3.1. Equivalence Transformation of the Optimization Problem

For the fraction objective function in (7), we first rewrite problems (7)–(15) in the following compact form:
(16)
maximize
ρ
,
γ
,
p
∈
π
R
(
ρ
,
γ
,
p
)
P
(
ρ
,
γ
,
p
)
,
where ρ
=
{
ρ
k
,
n
m
,
m
′
}, γ
=
{
γ
m
,
m
′
}, and p
=
{
p
S
,
k
m
,
p
R
,
n
m
′
}. π denotes the feasible domain defined by (8)–(15). R
(
ρ
,
γ
,
p
) and P
(
ρ
,
γ
,
p
) are the numerator and denominator in (7), respectively. Problem (16) is a nonlinear fractional problem. According to [29], we transform the considered EE problem in fractional form into an equivalent optimal problem in subtractive form. We then define the following parameter problem:
(17)
F
(
q
)
≜
maximize
ρ
,
γ
,
p
∈
π
{
R
(
ρ
,
γ
,
p
)
-
q
P
(
ρ
,
γ
,
p
)
}
,
where q
∈
R is treated as a parameter. We have the following theorems, all of which are proved in Appendix B.Theorem 1.
F
(
q
) is strictly monotonically decreasing for q.Theorem 2.
F
(
q
)
=
0 has a unique solution.Theorem 3.
Consider(18)
q
0
=
R
(
ρ
0
,
γ
0
,
p
0
)
P
(
ρ
0
,
γ
0
,
p
0
)
=
max
⁡
ρ
,
γ
,
p
∈
π
⁡
R
(
ρ
,
γ
,
p
)
P
(
ρ
,
γ
,
p
)
only
if
F
(
q
0
)
=
F
(
q
0
,
(
ρ
0
,
γ
0
,
p
0
)
)
=
max
⁡
ρ
,
γ
,
p
∈
π
⁡
{
R
(
ρ
,
γ
,
p
)
-
q
0
(
ρ
,
γ
,
p
)
}
=
0
.Based on the above theorems, we can use binary search method to findF
(
q
)
=
0 and the optimal solution for the primal problem. Therefore, the difficulty is to solve T
(
q
) for a given q. The optimization problem is
(19)
max
⁡
ρ
,
γ
,
p
∈
π
R
(
ρ
,
γ
,
p
)
-
q
(
ρ
,
γ
,
p
)
.Obtaining the joint optimalρ
*, γ
*, and p
* for (19) requires solving a mixed integer programming problem. Therefore, finding the optimal solution for problem (19) requires searching through all possible users, relays, and subcarrier allocation, which is a complex task when the system is large. The literature in [30] showed that the duality gap of a nonconvex resource allocation problem that satisfies the time-sharing condition is nearly zero with a large number of subcarriers in a multicarrier system. Thus, we solve this problem by using the Lagrange dual method.


## 3.2. Dual Problem

The Lagrange dual function of problem (19) can be written as
(20)
g
(
λ
,
μ
,
υ
)
=
max
⁡
{
ρ
,
γ
}
∈
Ω
L
(
ρ
,
γ
,
p
,
λ
,
μ
,
υ
)
,
(21)
L
(
ρ
,
γ
,
p
,
λ
,
μ
,
υ
)
=
∑
k
=
1
K
∑
n
=
1
N
∑
m
=
1
M
∑
m
′
=
1
M
w
k
2
ρ
k
,
n
m
,
m
′
γ
m
,
m
′
d
d
d
d
d
d
d
d
d
d
d
i
×
lo
g
2
(
1

+
p
S
,
k
m
α
k
,
D
m

+
p
S
,
k
m
α
k
,
n
m
p
R
,
n
m
′
α
n
,
D
m
′
p
S
,
k
m
α
k
,
n
m
+
p
R
,
n
m
′
α
n
,
D
m
′
)
-
q
(
ξ
∑
k
=
1
K
∑
n
=
1
N
∑
m
=
1
M
∑
m
′
=
1
M
ρ
k
,
n
m
,
m
′
γ
m
,
m
′
(
p
S
,
k
m
+
p
R
,
n
m
′
)
d
d
d
d
d
d
+
∑
k
=
1
K
P
C
,
S
k
+
∑
n
=
1
N
P
C
,
R
n
)
+
∑
k
=
1
k
λ
k
(
P
S
,
k
-
∑
m
=
1
M
p
S
,
k
m
)
+
∑
n
=
1
N
μ
n
(
P
S
,
n
-
∑
m
′
=
1
M
p
R
,
n
m
′
)
+
∑
k
=
1
k
υ
k
(
R
S
,
k
-
Q
S
,
k
)
,
where Lagrange is given in (21).In (20), λ
=
(
λ
1
,
λ
2
,
…
,
λ
K
)
≥
0, μ
=
(
μ
1
,
μ
2
,
…
,
μ
N
)
≥
0, and υ
=
(
υ
1
,
υ
2
,
…
,
υ
K
)
≥
0 are the vectors of the dual variables associated with the individual power constraint for the users, individual power constraint for the relays, and individual rate constraint for the users, respectively. Hence, the dual optimization problem is given by
(22)
min
⁡
g
(
λ
,
μ
,
υ
)
,
i
i
s.t.
λ
,
μ
,
υ
≥
0
.The literature in [31] proved that a dual function is always convex. Therefore, subgradient-based methods can be used to minimize g
(
λ
,
μ
,
υ
) with guaranteed convergence. Dual variables can be updated in parallel as follows:
(23)
λ
k
(
d
+
1
)
=
[
λ
k
(
d
)
+
o
(
d
)
(
∑
m
=
1
M
p
S
,
k
m
-
P
S
,
k
)
]
+
μ
n
(
d
+
1
)
=
[
μ
n
(
d
)
+
θ
(
d
)
(
∑
m
′
=
1
M
p
R
,
n
m
′
-
P
S
,
n
)
]
+
υ
k
(
d
+
1
)
=
[
υ
k
(
d
)
+
ϑ
(
d
)
(
Q
S
,
k
-
R
S
,
k
)
]
+
.o
(
d
), θ
(
d
), and ϑ
(
d
) are used as the step size, and d is the iteration index. To guarantee optimal dual variable convergence, the step size is chosen following the diminishing step size policy [32].


## 3.3. Optimizing Primal Variables with Given Dual Variables

Computing the dual functiong
(
λ
,
μ
,
υ
) involves determining the optimal ρ, γ, and p at given dual points λ, μ, and υ. Therefore, we present the detailed solution procedure in three phases.


### 3.3.1. Finding the Optimalp for Fixed ρ and γ

For the fixedρ and γ, we rewrite (20) as
(24)
g
(
λ
,
μ
,
υ
)
=
max
⁡
{
ρ
,
γ
}
∈
Ω
∑
k
=
1
K
∑
n
=
1
N
∑
m
=
1
M
∑
m
′
=
1
M
L
k
,
n
m
,
m
′
+
∑
k
=
1
k
λ
k
P
S
,
k
+
∑
n
=
1
N
μ
n
P
S
,
n
+
q
(
∑
k
=
1
K
P
C
,
S
k
+
∑
n
=
1
N
P
C
,
R
n
)
-
∑
k
=
1
k
υ
k
Q
S
,
k
,
where
(25)
L
k
,
n
m
,
m
′
≜
w
k
2
(
1
+
υ
k
)
×
lo
g
2
(
1
+
p
S
,
k
m
α
k
,
D
m
+
p
S
,
k
m
α
k
,
n
m
p
R
,
n
m
′
α
n
,
D
m
′
p
S
,
k
m
α
k
,
n
m
+
p
R
,
n
m
′
α
n
,
D
m
′
)
-
(
q
ξ
+
λ
k
)
p
S
,
k
m
-
(
q
ξ
+
μ
n
)
p
R
,
n
m
′
.A detailed derivation is given in AppendixC.According to the Lagrange dual decomposition method, the optimal power allocation can be determined by solving the following problem:(26)
max
⁡
⁡
L
k
,
n
m
,
m
′
p
S
,
k
m
≥
0
,
p
R
,
n
m
′
≥
0
,
∀
k
,
n
,
m
,
m
′
.AppendixA indicates that L
k
,
n
m
,
m
′ is a joint concave function of (
p
S
,
k
m
,
p
R
,
n
m
′
). Applying the Karush-Kuhn-Tucker (KKT) conditions [28], we can obtain the following optimal power allocation:(27)
p
S
,
k
m
=
{
b
k
,
n
m
,
m
′
p
R
,
n
m
′
,
if
p
R
,
n
m
′
>
0
(
w
k
(
1
+
υ
k
)
2
ln
⁡
2
(
q
ξ
+
λ
k
)
-
1
α
k
,
D
m
)
+
if
p
R
,
n
m
′
=
0
,
(28)
p
R
,
n
m
′
=
{
(
w
k
(
1
+
υ
k
)
2
ln
⁡
2
(
α
k
,
n
m
α
n
,
D
m
′
2
+
(
α
k
,
D
m
-
(
2
(
q
ξ
+
λ
k
)
ln
⁡
2
)
/
(
w
k
(
1
+
υ
k
)
)
)
(
α
k
,
n
m
b
k
,
n
m
,
m
′
+
α
n
,
D
m
′
2
)
2
(
α
k
,
n
m
b
k
,
n
m
,
m
′
+
α
n
,
D
m
′
2
)
2
(
α
k
,
D
m
α
k
,
n
m
α
n
,
D
m
′
)
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
d
d
d
i
i
i
×
(
α
k
,
n
m
b
k
,
n
m
,
m
′
+
α
n
,
D
m
′
2
)
2
)
i
i
i
i
×
(
b
k
,
n
m
,
m
′
(
q
ξ
+
λ
k
)
(
α
k
,
n
m
b
k
,
n
m
,
m
′
+
α
n
,
D
m
′
)
d
d
d
d
d
×
(
α
k
,
D
m
α
k
,
n
m
b
k
,
n
m
,
m
′
+
α
n
,
D
m
′
α
k
,
D
m
+
α
k
,
n
m
α
n
,
D
m
′
)
)
-
1
(
α
k
,
n
m
b
k
,
n
m
,
m
′
+
α
n
,
D
m
′
2
)
2
(
α
k
,
D
m
α
k
,
n
m
α
n
,
D
m
′
)
)
+
if
α
n
,
D
m
′
(
q
ξ
+
λ
k
)
>
α
k
,
D
m
(
q
ξ
+
μ
n
)
0
if
α
n
,
D
m
′
(
q
ξ
+
λ
k
)
≤
α
k
,
D
m
(
q
ξ
+
μ
n
)
.
(29)
b
k
,
n
m
,
m
′
=
α
n
,
D
m
′
(
(
q
ξ
+
μ
n
)
(
α
k
,
n
m
α
n
,
D
m
′
(
q
ξ
+
λ
k
)
-
α
k
,
n
m
α
k
,
D
m
(
q
ξ
+
μ
n
)
+
α
n
,
D
m
′
α
k
,
D
m
(
q
ξ
+
λ
k
)
)
+
α
k
,
D
m
(
q
ξ
+
μ
n
)
)
α
k
,
n
m
[
α
n
,
D
m
′
(
q
ξ
+
λ
k
)
-
α
k
,
D
m
(
q
ξ
+
μ
n
)
]
.And p
R
,
n
m
′ is given in (28).A detailed derivation is given in AppendixD.


### 3.3.2. Finding the Optimalρ for Fixed γ

Substituting the optimal power allocation expressions (27) and (28) into (20), we can obtain an alternative expression of the dual without power variables as
(30)
g
(
λ
,
μ
,
υ
)
=
max
⁡
{
ρ
,
γ
}
∈
Ω
⁡
∑
k
=
1
K
∑
n
=
1
N
∑
m
=
1
M
∑
m
′
=
1
M
ρ
k
,
n
m
,
m
′
γ
m
,
m
′
H
k
,
n
m
,
m
′
(
λ
,
μ
,
υ
)
+
∑
k
=
1
k
λ
k
P
S
,
k
+
∑
n
=
1
N
μ
n
P
S
,
n
+
q
(
∑
k
=
1
K
P
C
,
S
k
+
∑
n
=
1
N
P
C
,
R
n
)
-
∑
k
=
1
k
υ
k
Q
S
,
k
,
where the function H
k
,
n
m
,
m
′
(
λ
,
μ
,
υ
) can be defined as follows:
(31)
H
k
,
n
m
,
m
′
=
w
k
(
1
+
υ
k
)
r
k
,
n
m
,
m
′
-
(
q
ξ
+
λ
k
)
p
S
,
k
m
-
(
q
ξ
+
μ
n
)
p
R
,
n
m
′
.Therefore, the functionH
k
,
n
m
,
m
′
(
λ
,
μ
,
υ
) is the optimal criterion for relay and user selection. We can interpret this criterion by using an economic form. The first term can be viewed as the rate obtained by selecting subcarrier pairing (m
,
m
′) by user k and relay n, such as our gross income in the business. The second term is the cost for the user’s power consumption. The third term is the cost for the relay’s power consumption. H
k
,
n
m
,
m
′
(
λ
,
μ
,
υ
) then represents our net profit. We should find the optimal k and n to maximize the profit. K
×
N profit matrix exists for every subcarrier pairing (m, m
′). We should find a maximum value in this matrix; thus, the sum of profit could be large. The optimal relay selection and subcarrier allocation should therefore be the maximum value in (31) and is given by
(32)
ρ
k
,
n
m
,
m
′
=
{
1
,
(
k
*
,
n
*
)
=
arg
max
⁡
k
,
n
⁡
H
k
,
n
m
,
m
′
0
,
otherwise
.In the operation, the optimal power allocation can first be computed by using (28) and (29). These power values can then be substituted into (31) to compute H
k
,
n
m
,
m
′. Finally, we need to find a maximum value in K
×
N profit matrix, and the user and relay pair will be determined.


### 3.3.3. Finding the Optimalγ for Fixed ρ

After finding the optimalρ, we can obtain the corresponding dual function by substituting (32) into (20) as follows:
(33)
g
(
λ
,
μ
,
υ
)
=
max
⁡
γ
∈
Ω
∑
m
=
1
M
∑
m
′
=
1
M
γ
m
,
m
′
H
m
,
m
′
(
λ
,
μ
,
υ
)
+
∑
k
=
1
k
λ
k
P
S
,
k
+
∑
n
=
1
N
μ
n
P
S
,
n
+
q
(
∑
k
=
1
K
P
C
,
S
k
+
∑
n
=
1
N
P
C
,
R
n
)
-
∑
k
=
1
k
υ
k
Q
S
,
k
.We can then find the optimal subcarrier pairingγ. To this end, we launch the first term in (33) and define M
×
M profit matrix as follows:
(34)
[
γ
1,1
H
1,1
γ
1,2
H
1,2
⋯
γ
1
,
M
H
1
,
M
γ
2,1
H
2,1
γ
2,2
H
2,2
⋯
γ
2
,
M
H
2
,
M
⋮
⋮
⋱
⋮
γ
M
,
1
H
M
,
1
γ
M
,
2
H
M
,
2
⋯
γ
M
,
M
H
M
,
M
]
.We need to select one element in each row and each column in matrix (34) for the sum of profit to be large. Clearly, the problem is a standard linear assignment and can be solved by using the Hungarian method [33]. Ψ
(
m
) is defined as the subcarrier index in the second phase optimally paired with subcarrier m in the first phase. The optimal subcarrier pairing can be expressed as
(35)
γ
m
,
m
′
=
{
1
,
m
′
=
ψ
(
m
)
0
,
otherwise
.We have obtained the optimal variablesρ, γ, and p for given dual variables λ, μ, and υ. We can subsequently obtain the joint optimization problem by updating the dual variables.T
(
q
) is obtained according to the preceding analysis for a given q. However, we should find the optimal q to satisfy T
(
q
)
=
0. q
=
0, which yields T
(
q
)
>
0 and T
(
q
)
<
0 with q
→
∞. Thus, we can use binary search method to find the optimal q, as stated in Algorithm 1.Algorithm 1:Bisection-based energy-efficient resource allocation algorithm.
(1)Initialize  q
min
⁡ = 0, q
max
⁡ >> 0 with F
(
q
min
⁡
) > 0 and F
(
q
max
⁡
) < 0, ε.
(2) (i)Update  q
middle
←
(
q
min
⁡
+
q
max
⁡
)
/
2;
(ii)Initialization: λ
k, μ
n, and ν
k;
(a) Obtain the optimal power via (27) and (28);
(b) Obtain (m
,
m
′) via (35);
(c) Obtain (n
,
k) for given (m
,
m
′) via (32);
(d) Update the dual variablesλ
k, μ
n, and ν
k via (23);
(e) Repeat (a) → (d) until convergence;
(3) IfF
(
q
middle
)
>
0
,
q
min
⁡
←
q
middle; otherwise, q
max
⁡
←
q
middle;
(4)Repeat  Steps 2 and 3 until |
F
(
q
middle
)
|
<
ε.


## 3.3.1. Finding the Optimalp for Fixed ρ and γ

For the fixedρ and γ, we rewrite (20) as
(24)
g
(
λ
,
μ
,
υ
)
=
max
⁡
{
ρ
,
γ
}
∈
Ω
∑
k
=
1
K
∑
n
=
1
N
∑
m
=
1
M
∑
m
′
=
1
M
L
k
,
n
m
,
m
′
+
∑
k
=
1
k
λ
k
P
S
,
k
+
∑
n
=
1
N
μ
n
P
S
,
n
+
q
(
∑
k
=
1
K
P
C
,
S
k
+
∑
n
=
1
N
P
C
,
R
n
)
-
∑
k
=
1
k
υ
k
Q
S
,
k
,
where
(25)
L
k
,
n
m
,
m
′
≜
w
k
2
(
1
+
υ
k
)
×
lo
g
2
(
1
+
p
S
,
k
m
α
k
,
D
m
+
p
S
,
k
m
α
k
,
n
m
p
R
,
n
m
′
α
n
,
D
m
′
p
S
,
k
m
α
k
,
n
m
+
p
R
,
n
m
′
α
n
,
D
m
′
)
-
(
q
ξ
+
λ
k
)
p
S
,
k
m
-
(
q
ξ
+
μ
n
)
p
R
,
n
m
′
.A detailed derivation is given in AppendixC.According to the Lagrange dual decomposition method, the optimal power allocation can be determined by solving the following problem:(26)
max
⁡
⁡
L
k
,
n
m
,
m
′
p
S
,
k
m
≥
0
,
p
R
,
n
m
′
≥
0
,
∀
k
,
n
,
m
,
m
′
.AppendixA indicates that L
k
,
n
m
,
m
′ is a joint concave function of (
p
S
,
k
m
,
p
R
,
n
m
′
). Applying the Karush-Kuhn-Tucker (KKT) conditions [28], we can obtain the following optimal power allocation:(27)
p
S
,
k
m
=
{
b
k
,
n
m
,
m
′
p
R
,
n
m
′
,
if
p
R
,
n
m
′
>
0
(
w
k
(
1
+
υ
k
)
2
ln
⁡
2
(
q
ξ
+
λ
k
)
-
1
α
k
,
D
m
)
+
if
p
R
,
n
m
′
=
0
,
(28)
p
R
,
n
m
′
=
{
(
w
k
(
1
+
υ
k
)
2
ln
⁡
2
(
α
k
,
n
m
α
n
,
D
m
′
2
+
(
α
k
,
D
m
-
(
2
(
q
ξ
+
λ
k
)
ln
⁡
2
)
/
(
w
k
(
1
+
υ
k
)
)
)
(
α
k
,
n
m
b
k
,
n
m
,
m
′
+
α
n
,
D
m
′
2
)
2
(
α
k
,
n
m
b
k
,
n
m
,
m
′
+
α
n
,
D
m
′
2
)
2
(
α
k
,
D
m
α
k
,
n
m
α
n
,
D
m
′
)
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
d
d
d
i
i
i
×
(
α
k
,
n
m
b
k
,
n
m
,
m
′
+
α
n
,
D
m
′
2
)
2
)
i
i
i
i
×
(
b
k
,
n
m
,
m
′
(
q
ξ
+
λ
k
)
(
α
k
,
n
m
b
k
,
n
m
,
m
′
+
α
n
,
D
m
′
)
d
d
d
d
d
×
(
α
k
,
D
m
α
k
,
n
m
b
k
,
n
m
,
m
′
+
α
n
,
D
m
′
α
k
,
D
m
+
α
k
,
n
m
α
n
,
D
m
′
)
)
-
1
(
α
k
,
n
m
b
k
,
n
m
,
m
′
+
α
n
,
D
m
′
2
)
2
(
α
k
,
D
m
α
k
,
n
m
α
n
,
D
m
′
)
)
+
if
α
n
,
D
m
′
(
q
ξ
+
λ
k
)
>
α
k
,
D
m
(
q
ξ
+
μ
n
)
0
if
α
n
,
D
m
′
(
q
ξ
+
λ
k
)
≤
α
k
,
D
m
(
q
ξ
+
μ
n
)
.
(29)
b
k
,
n
m
,
m
′
=
α
n
,
D
m
′
(
(
q
ξ
+
μ
n
)
(
α
k
,
n
m
α
n
,
D
m
′
(
q
ξ
+
λ
k
)
-
α
k
,
n
m
α
k
,
D
m
(
q
ξ
+
μ
n
)
+
α
n
,
D
m
′
α
k
,
D
m
(
q
ξ
+
λ
k
)
)
+
α
k
,
D
m
(
q
ξ
+
μ
n
)
)
α
k
,
n
m
[
α
n
,
D
m
′
(
q
ξ
+
λ
k
)
-
α
k
,
D
m
(
q
ξ
+
μ
n
)
]
.And p
R
,
n
m
′ is given in (28).A detailed derivation is given in AppendixD.


## 3.3.2. Finding the Optimalρ for Fixed γ

Substituting the optimal power allocation expressions (27) and (28) into (20), we can obtain an alternative expression of the dual without power variables as
(30)
g
(
λ
,
μ
,
υ
)
=
max
⁡
{
ρ
,
γ
}
∈
Ω
⁡
∑
k
=
1
K
∑
n
=
1
N
∑
m
=
1
M
∑
m
′
=
1
M
ρ
k
,
n
m
,
m
′
γ
m
,
m
′
H
k
,
n
m
,
m
′
(
λ
,
μ
,
υ
)
+
∑
k
=
1
k
λ
k
P
S
,
k
+
∑
n
=
1
N
μ
n
P
S
,
n
+
q
(
∑
k
=
1
K
P
C
,
S
k
+
∑
n
=
1
N
P
C
,
R
n
)
-
∑
k
=
1
k
υ
k
Q
S
,
k
,
where the function H
k
,
n
m
,
m
′
(
λ
,
μ
,
υ
) can be defined as follows:
(31)
H
k
,
n
m
,
m
′
=
w
k
(
1
+
υ
k
)
r
k
,
n
m
,
m
′
-
(
q
ξ
+
λ
k
)
p
S
,
k
m
-
(
q
ξ
+
μ
n
)
p
R
,
n
m
′
.Therefore, the functionH
k
,
n
m
,
m
′
(
λ
,
μ
,
υ
) is the optimal criterion for relay and user selection. We can interpret this criterion by using an economic form. The first term can be viewed as the rate obtained by selecting subcarrier pairing (m
,
m
′) by user k and relay n, such as our gross income in the business. The second term is the cost for the user’s power consumption. The third term is the cost for the relay’s power consumption. H
k
,
n
m
,
m
′
(
λ
,
μ
,
υ
) then represents our net profit. We should find the optimal k and n to maximize the profit. K
×
N profit matrix exists for every subcarrier pairing (m, m
′). We should find a maximum value in this matrix; thus, the sum of profit could be large. The optimal relay selection and subcarrier allocation should therefore be the maximum value in (31) and is given by
(32)
ρ
k
,
n
m
,
m
′
=
{
1
,
(
k
*
,
n
*
)
=
arg
max
⁡
k
,
n
⁡
H
k
,
n
m
,
m
′
0
,
otherwise
.In the operation, the optimal power allocation can first be computed by using (28) and (29). These power values can then be substituted into (31) to compute H
k
,
n
m
,
m
′. Finally, we need to find a maximum value in K
×
N profit matrix, and the user and relay pair will be determined.


## 3.3.3. Finding the Optimalγ for Fixed ρ

After finding the optimalρ, we can obtain the corresponding dual function by substituting (32) into (20) as follows:
(33)
g
(
λ
,
μ
,
υ
)
=
max
⁡
γ
∈
Ω
∑
m
=
1
M
∑
m
′
=
1
M
γ
m
,
m
′
H
m
,
m
′
(
λ
,
μ
,
υ
)
+
∑
k
=
1
k
λ
k
P
S
,
k
+
∑
n
=
1
N
μ
n
P
S
,
n
+
q
(
∑
k
=
1
K
P
C
,
S
k
+
∑
n
=
1
N
P
C
,
R
n
)
-
∑
k
=
1
k
υ
k
Q
S
,
k
.We can then find the optimal subcarrier pairingγ. To this end, we launch the first term in (33) and define M
×
M profit matrix as follows:
(34)
[
γ
1,1
H
1,1
γ
1,2
H
1,2
⋯
γ
1
,
M
H
1
,
M
γ
2,1
H
2,1
γ
2,2
H
2,2
⋯
γ
2
,
M
H
2
,
M
⋮
⋮
⋱
⋮
γ
M
,
1
H
M
,
1
γ
M
,
2
H
M
,
2
⋯
γ
M
,
M
H
M
,
M
]
.We need to select one element in each row and each column in matrix (34) for the sum of profit to be large. Clearly, the problem is a standard linear assignment and can be solved by using the Hungarian method [33]. Ψ
(
m
) is defined as the subcarrier index in the second phase optimally paired with subcarrier m in the first phase. The optimal subcarrier pairing can be expressed as
(35)
γ
m
,
m
′
=
{
1
,
m
′
=
ψ
(
m
)
0
,
otherwise
.We have obtained the optimal variablesρ, γ, and p for given dual variables λ, μ, and υ. We can subsequently obtain the joint optimization problem by updating the dual variables.T
(
q
) is obtained according to the preceding analysis for a given q. However, we should find the optimal q to satisfy T
(
q
)
=
0. q
=
0, which yields T
(
q
)
>
0 and T
(
q
)
<
0 with q
→
∞. Thus, we can use binary search method to find the optimal q, as stated in Algorithm 1.Algorithm 1:Bisection-based energy-efficient resource allocation algorithm.
(1)Initialize  q
min
⁡ = 0, q
max
⁡ >> 0 with F
(
q
min
⁡
) > 0 and F
(
q
max
⁡
) < 0, ε.
(2) (i)Update  q
middle
←
(
q
min
⁡
+
q
max
⁡
)
/
2;
(ii)Initialization: λ
k, μ
n, and ν
k;
(a) Obtain the optimal power via (27) and (28);
(b) Obtain (m
,
m
′) via (35);
(c) Obtain (n
,
k) for given (m
,
m
′) via (32);
(d) Update the dual variablesλ
k, μ
n, and ν
k via (23);
(e) Repeat (a) → (d) until convergence;
(3) IfF
(
q
middle
)
>
0
,
q
min
⁡
←
q
middle; otherwise, q
max
⁡
←
q
middle;
(4)Repeat  Steps 2 and 3 until |
F
(
q
middle
)
|
<
ε.


## 4. Suboptimal Schemes

We analyze the complexity of the proposed optimal scheme. For every subcarrier pair, the number of computations needed to perform relay selection isK
N. Therefore, the complexity at relay selection for all the subcarrier pair is O
(
M
K
N
). The complexity of the Hungarian method is O
(
M
3
). The complexity of the subgradient method is polynomial in the number of dual variables. Considering the individual power constraint for the users and relays and the individual rate constraint for the users, the number of the dual variables is (2
K
+
N). Therefore, the overall complexity is O
(
|
2
K
+
N
|
2
M
4
K
N
·
log
⁡
2
(
1
/
ε
)
). ε is the accuracy required for the binary search. In this section, we only propose two schemes for the subcarrier pairing.


### 4.1. Suboptimal Scheme 1: Order Subcarrier Pairing

Similar to the literature in [6], OSP denotes the best S
→
R subcarrier in the first phase with the best R
→
D subcarrier in the secondary phase, pairing the next best S
→
R subcarrier in the first phase with the next best R
→
D subcarrier in the secondary phase until all the subcarriers are paired. The complexity is O
(
2
M
2
) for OSP. When the number of subcarriers is small, the advantage of using OSP is not obvious. By contrast, the advantage is obvious when the number of subcarriers is large.


### 4.2. Suboptimal Scheme 2: Fixed Subcarrier Pairing

To reduce the complexity of the subcarrier pairing, we let the subcarrier pairing be prefixed, rather than seeking the optimal subcarrier pairing. Similar to the previous suboptimal scheme [33], the subcarrier pairing can be arranged as
(36)
ψ
(
m
)
=
m
,
∀
m
.Thus, the source and relay use the same subcarrier to transmit and forward a signal in different phases, respectively. We do not need to make the subcarrier pair.In the two suboptimal schemes, we only reduce the complexity for subcarrier pairing. The dual variables still need to be updated to computeH
k
,
n
m
,
m
′.


## 4.1. Suboptimal Scheme 1: Order Subcarrier Pairing

Similar to the literature in [6], OSP denotes the best S
→
R subcarrier in the first phase with the best R
→
D subcarrier in the secondary phase, pairing the next best S
→
R subcarrier in the first phase with the next best R
→
D subcarrier in the secondary phase until all the subcarriers are paired. The complexity is O
(
2
M
2
) for OSP. When the number of subcarriers is small, the advantage of using OSP is not obvious. By contrast, the advantage is obvious when the number of subcarriers is large.


## 4.2. Suboptimal Scheme 2: Fixed Subcarrier Pairing

To reduce the complexity of the subcarrier pairing, we let the subcarrier pairing be prefixed, rather than seeking the optimal subcarrier pairing. Similar to the previous suboptimal scheme [33], the subcarrier pairing can be arranged as
(36)
ψ
(
m
)
=
m
,
∀
m
.Thus, the source and relay use the same subcarrier to transmit and forward a signal in different phases, respectively. We do not need to make the subcarrier pair.In the two suboptimal schemes, we only reduce the complexity for subcarrier pairing. The dual variables still need to be updated to computeH
k
,
n
m
,
m
′.


## 5. Simulation Results

In this section, simulation results are presented to demonstrate the performance of the three proposed schemes. In the simulation, we consider quasistatic frequency-selective Rayleigh fading channels with a six-tap equal-gain, equal-space delay profile. The delay interval between adjacent taps is equal to the inverse of the OFDM system bandwidth. We considerM
=
48 subcarriers. The bandwidth of each subcarrier is 15 kHz. Without loss of generality, we assume that all the noise terms are complex Gaussian random variables with zero mean and variance with 1. To produce large channel fading between users and destination, we assume that the channel variance of S
→
D link is −8 dB. Two users have the same minimum rate requirement of 0.5 bps/Hz. For each user and relay, the maximum transmit power and the circuit power are 1 W and 0.2 W, respectively. For simplicity, we assume that the drain efficiency of power amplifier is 0.35.EE of the energy-efficient design that optimizes EE and the spectral-efficient design that maximizes the weight sum rate with the same constraints is evaluated in Figures2 and 3. For any k and n, we assume that the value of δ
k
,
n
2 is the same and define it as δ
S
,
R
2. We set δ
n
,
D
2
=
0dB for any n. Accordingly, the energy-efficient design significantly improves EE compared with the spectral-efficient design. The suboptimal scheme-based OSP is close to the optimal scheme, and its performance reached 97% or more of the optimal performance. EE performance of the suboptimal scheme-based fixed subcarrier paring is worse compared with the other two schemes. However, this scheme does not need subcarrier pairing, and its computation complexity is lower. Figure 3 shows that EE will decrease when considering the user’s priority, namely, the weight factors.Figure 2
Energy efficiency versus channel variance ofS
→
R link with N
=
2 relays, and w
1
=
w
2
=
1.Figure 3
Energy efficiency versus channel variance ofS
→
R link with N
=
2 relays, andw
1
=
1, w
2
=
2.For comparison with EE performance under different number of relays, we also plot EE with 12 relays with equal weight factor for all the users in Figure4. EE in Figure 4 is lower than that in Figure 2 for a given δ
S
,
R
2. The literature in [8] indicated that, as the number of relays increases, the average throughput increases. When considering EE, this relationship may be changed, as presented in Figures 2 and 4. Aside from the power consumption of signals, additional circuit energy consumption for the users and relays must be considered. Such additional circuit energy consumption will increase with the number of relays. We consider the throughput per unit power rather than the throughput. Therefore, EE will decrease when the energy consumption is greater than its contribution in rate. This phenomenon will occur especially when the number of relays is large.Figure 4
Energy efficiency versus channel variance ofS
→
R link with N
=
12 relays, and w
1
=
w
2
=
1.Figures5, 6, and 7 plot the throughput corresponding to the EE in Figures 2, 3, and 4, respectively. From them, the throughput of the spectral-efficient design is, as expected, more than that of the energy-efficient design. Combining Figures 2 and 5, Figures 3 and 6, and Figures 4 and 7, we can get that the maximum EE and the maximum throughput are not necessarily simultaneously achieved. Due to the limited space, we will investigate the tradeoff relationship in detail in our future work.Figure 5
Throughput versus channel variance ofS
→
R link with N= 2 relays, and w
1
=
1, w
2
=
1.Figure 6
Throughput versus channel variance ofS
→
R link with N= 2 relays, and w
1
=
1, w
2
=
2.Figure 7
Throughput versus channel variance ofS
→
R link with N= 12 relays, and w
1
=
w
2
=
1.Figure8 illustrates EE versus different numbers of relays under the proposed optimal scheme and suboptimal scheme-based OSP. δ
k
,
n
2 and δ
n
,
D
2 are set to zero. Figure 8 indicates that, as the relay number increases, EE first increases and then decreases. For different circuit energy consumption, the relay number also differs when EE reaches the maximum. For example, for P
c = 0.18 W, EE reaches the maximum when the number of relays is 6. However, for P
c = 0.2 W, the best relay number is 4. With the decreased circuit energy consumption, the best relay number increases. To express the relationship clearly, we plot EE versus different relay numbers and circuit energy consumption with the optimal scheme only in Figure 9. The figure illustrates that the change of EE with the relay number differs under different circuit energy consumption. For example, when the circuit energy consumption is low, EE increases with the relay number. However, with increasing circuit energy consumption, EE first increases and then decreases. When the circuit energy consumption is high, EE monotone decreases. Therefore, high circuit energy consumption is unfavorable to EE when the number of relays is large.Figure 8
Energy efficiency versus different numbers of relays withw
1
=
w
2
=
1.Figure 9
Energy efficiency versus different numbers of relays and circuit energy consumption withw
1
=
w
2
=
1.


## 6. Conclusion

In this paper, we formulate an energy-efficient resource allocation problem for a cooperative multirelay OFDMA uplink system with AF protocol. This paper determines the joint optimization of subcarrier pairing, relay assignment, subcarrier assignment, and power allocation with the objective of maximizing EE. Individual power constraint for every user and relay is applied. To solve the complex fraction problem, we transform the considered EE problem in fractional form into an equivalent optimal problem in subtractive form. However, the mixed integer programming problem is NP-hard. We utilize the dual method to solve the problem efficiently. To reduce the complexity of the problem, we propose two low-complexity schemes for subcarrier pairing. The simulation results show greater EE improvement of the energy-efficient design than that of the spectral-efficient design, and the performance of the proposed suboptimal algorithm OSP-based is close to that of the optimal algorithm. EE differs under different relay numbers and is also affected by circuit energy consumption. In future work, we will study the fundamental tradeoff between EE and SE in cooperative communication.



---

*Source: 461713-2014-07-10.xml*