This full text paper was peer reviewed at the direction of IEEE Communications Society subject matter experts

for publication in the WCNC 2009 proceedings.

On QoS-Guaranteed Downlink Cooperative

OFDMA Systems with Amplify-and-Forward
Relays: Optimal Schedule and Resource Allocation
Danhua Zhang, Youzheng Wang, Jianhua Lu
Dept. of Electronic Engineering
Tsinghua University, Beijing, P. R. China
Email: {zhangdh, wangyz, lujh}@wmc.ee.tsinghua.edu.cn
Abstract This paper considers joint schedule and resource allocation in downlink cooperative OFDMA systems with multiple
sources, multiple relays and a single destination. Each user has
individual QoS requirements and the relays operate in amplifyand-forward and half-duplex mode. We try to find optimal
power allocation, relay selection and subcarrier assignment to
maximize overall system rates. The problem is formulated as
a Mixed Binary Integer Programming (MBIP). Although the
original problem is comprehensive in nature, a novel two-level
dual-primal decomposition based algorithm is proposed to tackle
the problem. Optimal solutions are given in closed-form and the
algorithm has a polynomial complexity in general. The efficiency
of the algorithm is finally illustrated by numerical results.

I. I NTRODUCTION
In the future 4th Generation (4G) wireless system, orthogonal frequency division multiple access (OFDMA) is one of
the most promising solutions to provide a high-performance
transmission in emerging cellular networks. OFDMA eliminates the frequency selectivity effect by transmitting the wideband signal on multiple orthogonal subcarriers as narrow-band
signals. Also recently, cooperative relaying has emerged as
a promising technology to achieve virtual spatial diversity
in wireless communication networks [1]. Cooperative transmission by relay nodes has the potential to further improve
the overall network performance, e.g., throughput increase,
coverage extension, power saving, and interference mitigation.
Cooperative OFDMA based broadband wireless access (BWA)
networks are currently under standardization by the IEEE
802.16j task group [2].
Although the effectiveness of the new architecture has
been demonstrated, analytical results have also indicated that
such performance heavily depends on schedule and resource
allocation, i.e., power allocation, relay selection and subcarrier allocation. Several fundamental questions need to be
answered: In a cooperative OFDMA system, each user should
communicate with the help of relay or not? Which relay and
what relay strategy should be employed? How much power
should be allocated? How to schedule the transmission and
allocate subcarriers? And what the scenarios will be like
when users have heterogenous QoS requirements? However,
answers to these questions in a cooperative OFDMA system
are generally complicated due to several reasons: (1) relay
selection and subcarrier assignment are discrete in nature, (2)

unlike systems without relays, the cooperative transmission

rate is non-convex or even non-differential to the overall
resource, and (3) the individual Quality of Service (QoS)
constraints make the problem even less tractable.
For these reasons, the literature for cooperative OFDMA
systems is still in a nascent state. A graph theory based
schedule algorithm is proposed in [3] yet with fixed power
allocation. Heuristic algorithms are discussed in [4], [5]. While
enjoy a low complexity, the performance of the algorithms
may not be guaranteed. Resource allocation for multi-hop
cooperation is considered in [6] and [7], but they are generally
not applicable for other cooperative modes. [8] focuses on
a peer-to-peer relay network while no QoS requirements are
incorporated.
In this paper, we first formulate a general optimization
problem for schedule and resource allocation in downlink
cooperative OFDMA systems. Both relay schemes of amplifyand-forward (AF) with and without diversity are considered
in half-duplex mode. Each user is subject to individual QoS
constraint. We try to find optimal power allocation, relay selection and subcarrier assignment to maximize overall system
rates. Although the problem is comprehensive in its original
form, which has nonconvex objective, integer and coupled
constraints, we propose a novel two-level dual-primal decomposition based algorithm to tackle the problem. The problem
is first decomposed into subproblems at each subcarrier and
then we obtain optimal power allocation, relay selection and
subcarrier assignment in closed-form.
The rest of this paper is organized as follows. Section
II provides the cooperative OFDMA system model. Section
III formulates the resource allocation problem. Section IV
analyzes the optimization problem and proposes our algorithms. Section IV illustrates the efficiency of the algorithms
by numerical results. Finally, we conclude the paper in Section
VI.
II. S YSTEM M ODEL
Consider a downlink wireless cellular network with one base
station (BS), multiple relay stations (RSs) and multiple mobile
stations (MSs) (Fig. 1). Each station is equipped with a single
antenna. Full channel state information (CSI) is assumed to
be available at the stations via channel estimation. RSs and

978-1-4244-2948-6/09/$25.00 2009 IEEE

This full text paper was peer reviewed at the direction of IEEE Communications Society subject matter experts for publication in the WCNC 2009 proceedings.

n
subcarrier with power Pr,km
. The noise variances at RS and
2
MS within one OFDM subchannel are denoted by r2 and m
,
respectively.
1) AF with diversity: For AF with diversity scheme, signals
of both time slots are combined with maximum-ratio combiner.
The signal to noise ratio (SNR) at the destination for the relay
pair (k, m) on the nth subcarrier is given by.
n n
dm +
SNRnkm,AF D = Ps,k

n n
n
ak Pr,km
bnkm
Ps,k
n an + P n
n
1 + Ps,k
k
r,km bkm

(1)

2
where ank = |hna,k |2 /r2 , bnkm = |hnb,km |2 /m
, and dnm =
n
2
2
|hd,m | /m . The instantaneous rate of relay pair (k, m) on
the nth subcarrier for AF with diversity scheme is therefore
given by

1
log(1 +SNRnkm,AF D )
2
n n
n
ak Pr,km
bnkm
Ps,k
1
n n
dm +
= log(1 + Ps,k
n an + P n
n )
2
1 + Ps,k
k
r,km bkm
(2)

cnkm,AF D =

Fig. 1.

The system model of downlink cooperative OFDMA network

MSs report their CSI to the base station through feedback.

The MSs also report their minimum rate requirements to the
BS. In accordance with WiMAX/802.16e standard, a central
control unit is assumed at the base station to perform power
allocation, relay selection and subcarrier assignment.
We assume the channel between stations is frequency selective and OFDMA is employed to convert the channel into
orthogonal subcarriers with flat fading. The channel is also
assumed to be static during the resource allocation.
Since there are many limitations in radio implementation
for full-duplex operation, we assume the half-duplex operation
of RSs. We consider a TDD transmission mode while in the
first time slot, the BS transmits with RSs and MSs receive.
In the second time slot, the RSs forward signals to the MSs
by employing Amplify-and-Forward (AF) relay schemes as
shown in Section III.
III. P ROBLEM F ORMULATION
Suppose there are one base station, M mobile stations
denoted S = {s1 , . . . , sm , . . . , sM } and K relay stations
forming the set R = {r1 , . . . , rk , . . . , rK }. All stations share
a total number of N subcarriers in the cell denoted N =
{n1 , . . . , nn , . . . , nN }. For the nth subcarrier, the channel
coefficients between BS and mth MS, BS and kth RS, kth RS
and mth MS are denoted by hnd,m , hna,k , hnb,km , respectively
(Fig. 1).

2) AF without diversity: When AF without diversity protocol is adopted, the destination only receivers the signal from
the relay in the second time slot, and the transmission rate can
be similarly derived as
1
log(1 +SNRnkm,AF )
2
n n
n
ak Pr,km
bnkm
Ps,k
1
= log(1 +
n an + P n
n )
2
1 + Ps,k
k
r,km bkm

cnkm,AF =

(3)

3) Direct Transmission: When the BS works in noncooperative mode, it transmits directly to the mobile station
over two time slots. Assume the BS transmits with power
n
to sm on subcarrier n, the instantaneous rate can be
Ps,0m
written as
n
dnm )
(4)
cn0m = log(1 + Ps,0m
The schedule of transmission can be represented by binary
assignment variables xnkm with xnkm = 1 indicating that the
base communicates with sm with the help of relay rk utilizing
subcarrier n and xnkm = 0 otherwise. For mobile station m,
it works in non-cooperative mode on subcarrier n if xnkm =
1, k = 0 and in cooperation with relay station k if xnkm =
1, k = 1, 2, . . . , K. Then the aggregate system rate can be
expressed in a compact form as
Csum =

N
M 
K 


cnkm xnkm

(5)

k=0 m=1 n=1

B. QoS Constraint
A. Achievable Rate
The base station can communicate with mobile stations
either in cooperative mode or non-cooperative mode. For the
cooperative mode, both AF with and without diversity schemes
are considered [1]. In the first time slot, BS sends data with
n
on the nth subcarrier to rk . In the second time
power Ps,k
slot, rk forward the received data to the mth user on the same

QoS guarantees play an important role in the future mobile

wireless networks. It is a challenging task to meet the diverse
QoS requirements imposed by current and envisioned services.
With various practical applications, QoS requirements can be
modeled in many ways including e.g., minimum transmission
rates, maximum tolerable error rates, maximum delay bounds.
In this paper, we try to maximize system aggregate rates

This full text paper was peer reviewed at the direction of IEEE Communications Society subject matter experts for publication in the WCNC 2009 proceedings.

subject to individual minimum rate constraints, thus the QoS

constraint can be described for each sm as
N
K 


IV. J OINT O PTIMAL S CHEDULE AND R ESOURCE

A LLOCATION A LGORITHM
We first derive the Lagrangian function as follows

cnkm xnkm

cm ,

(6)

L(X, Pr , , )

k=0 N =1

where cm is the minimum rate requirement for user m.

Since the cooperative transmission rate is not joint convex
in Ps and Pr , we assume a pre-determined Ps and the relays
have a sum power constraint
N
M 
K 


n
Pr,km
P.

(7)

M
K 


xnkm 1, n.

(8)

k=0 m=1

Therefore, the optimization problem for joint schedule and

resource allocation in downlink cooperative OFDMA networks
can be formulated as follows.

maximize

Csum =

N
M 
K 


cnkm xnkm

cnkm xnkm

k=0 m=1 N =1

M
K 


+ P

subject to

k=0 N =1
M
K 


cnkm xnkm

k=0 m=1
xnkm {0, 1},
N
M 
K 


N


N
K 



cnkm xnkm

n
Pr,km

K M
N



cnkm xnkm +

n=1 k=0 m=1


M
K 

n

Pr,km
k=0 m=1

M


m=1

M


K


cnkm xnkm

k=0

m cm + P

m=1

(10)

where = [1 , 2 , . . . , M ]T is the vector of dual variables

for the QoS constraints and is single dual variable for sum
power constraint. The Lagrangian dual function can therefore
be obtained [11]

max L(X, Pr , , )

X,Pr

M
K 

(11)
g(, ) = s.t.
xnkm 1, n

m=1
k=0

n
0
xnkm {0, 1}, Pr,km
and dual problem is
(12)

,0

m
(9)

k, m, n

n
Pr,km

m=1
n=1
k=1
n
0, k, m, n
Pr,km

cm

k=0 N =1

min g(, )

cm ,

xnkm 1,

m=1

k=0 m=1 n=1

K 
N


M


k=0 m=1 n=1

k=1 m=1 n=1

Each MS can utilize multiple subcarriers to transmit, either

cooperative or non-cooperative. However, each subcarrier can
not be shared by different MSs which means

N
M 
K 


X is a (K+1)M N matrix with elements xnkm . It should be

noted that we can answer three questions simultaneously if optimal X is obtained: Cooperate or not? Cooperate with which
relay? Transmit on which subcarrier? Meanwhile, optimal
power control is realized by optimizing Pr . Unfortunately, the
optimization problem is a Mixed Binary Integer Programming
(MBIP) problem which is hard to tackle. Since binary variable
X and continuous variable P coexist, even an exhaustive
search of the problem space is not applicable. The coupled
QoS constraints make the problem even harder to solve.
However, in the following section, we will propose a twolevel primal-dual decomposition method and obtain optimal
algorithm to solve (9) which can be proven to be optimal and
efficient.

There are several things to be noted here. First, the duality

gap is generally not zero due to the integer constraints.
However, when time sharing condition is satisfied, it can be
proved that the duality gap becomes asymptotically zero as
N goes to infinity [9]. A rigorous investigation is available in
[10]. Since time sharing condition is readily satisfied in our
case, it follows that the duality gap for (12) is zero. Second, we
have removed the coupling between subcarriers via lagrangian
relaxation and g(, ) can be decomposed into N subproblem
at each subcarrier which can be independently solved given
, . The subproblem at subcarrier n is
maximize

Ln (Xn , Pnr ) =

M
K 


cnkm xnkm +

k=0 m=1
M


subject to

K


cnkm xnkm

m=1
k=0
K
M

xnkm 1
k=0 m=1
n
xnkm {0, 1}, Pr,km

M
K 

k=0 m=1

0,

n
Pr,km

(13)

k, m

n
where Xn , Pnr are vectors of xnmk , Pr,km
on subcarrier n.
In order to get close form solution, we then try to solve
the subproblem through a second level primal decomposition.

This full text paper was peer reviewed at the direction of IEEE Communications Society subject matter experts for publication in the WCNC 2009 proceedings.

Note that the variables Pnr and Xn are only coupled at the
objective, we can first fix schedule variables Xn and have
optimization over Pnr

M
K 
M
K




n
n

c
x
+

cnkm xnkm
max

m
km km

Pn

m=1
k=0 m=1
k=0

M
K 
f (Xn ) =

n

Pr,km

k=0 m=1

n
s.t. Pr,km
0, k, m
(14)
and then solve the master problem over Xn
maximize
subject to

TABLE I
J OINT O PTIMAL S CHEDULE AND R ESOURCE A LLOCATION (JOSRA)
A LGORITHM

1. Initialization: Initialize (0), (0)

2. Solve subproblem (13) at each subcarrier as follows
n
1) Calculate optimal Pr,km
according to (18).
n
2) Obtain A(k, m) with optimal Pr,km
.

3) Solve optimal xn
km via (16).
3. Updates dual variables , according to (22).
4. Termination: Repeat 2,3 until convergence.

f (Xn )
M
K 


xnkm
m=1
k=0
xnkm {0, 1}

1,

(15)

In general, the master problem can be solved by exhaustive

search over feasible space of (X)n . However, observing the
specific structure of the subproblem, we can obtain close-form
solution for the primal problem. To do so, we first introduce
the following lemma.
Lemma 1: The optimization problem (14) and (15) are
equivalent1 to the following problem

1, (k, m) = (k  , m ) = arg max A
n
k,m
xkm =
(16)
0, otherwise

where
nkm =

n n
ak
Ps,k
,
n
1 + Ps,k dnm

P n an ,
s,k k
n
n
;
km = nk,m k,m
n
b
n
km
km
=
1 + Ps,k ank

AF with diversity

(19)

AF without diversity
(20)
(21)

Finally, The dual problem (12) can be solved by subgradient

method [11]. Dual variables , are updated in parallel as
follows
+

K N

cnkm (t)xnkm (t) cm
m (t + 1) = m (t) + (t)
k=0 N =1



+
where A is a matrix with elements A(k, m) and
N
M 
K 

n

(t + 1) = (t) + (t) P
Pr,km
(t)
n
max
cnkm + m cnkm Pr,km
n
k=0 m=1 n=1
Pr,km
(17)
A(k, m) =
(22)
s.t. P n 0, k, m
r,km
Proof: By visiting the constraints in (15), we first note where (t) and (t) are proper step sizes. The above updated
that Xn is a all-zero matrix except for one non-zero entry. is guaranteed to converge to the optimal dual variable if the
Therefore, f (Xn ) is equivalent to A(k, m) when transmission step sizes are chosen following a diminishing step size rule
pair (k, m) utilize the subcarrier. As a result, the optimization [12]. Since our problem has zero duality gap as mentioned
of problem (15) over feasible space of Xn can be cast as before, the optimal primal variables can be obtained accordfinding optimal (k, m) that with maximal element in A. This ingly. The algorithm is finally presented in Table I.
is the optimization in (16) and that concludes our proof.
Therefore, the difficulty of problem has been reduced to A. Complexity Analysis and Implementation Issues
We now analyze the complexity of our algorithm. For all
the optimization of (17). Since the rates are concave in relay
constraints,
M (K + 1) computations are needed to calculate
powers, we can find closed-form solution by substituting (2),
n
A
and
N
assignments for all subcarriers. Therefore, the
(3) into (17) and taking derivative with respect to Pr,km . After
complexity
for
one iteration is O(M KN ). Since the iteration
some manipulations, the optimal power allocation for both
number
increases
linearly with the dual variables and there are
with and without diversity can be expressed in a compact form
(M
+1)
dual
variables
, the overall complexity is O(M 2 KN ).
as follows
With
channel
state
information
through feedback, which is
+

4n
the major overhead, the base station can easily perform the
(nkm )2 + km (1 + nkm )(1 + m ) nkm 2
n
optimization. The polynomial complexity of the algorithm also
=
Pr,km
n + n )
2(km
km
greatly facilitates the implementation.
(18)
V. N UMERICAL R ESULTS
1 Technically, the equivalence of two optimization problems is quite complicated. A simple notation is applied here which means the two problem have
the same solutions

This section provides performance of our proposed algorithm by means of Monte-Carlo simulations. We consider an

70

60

60

50

50

40

Rate

Average Rate

This full text paper was peer reviewed at the direction of IEEE Communications Society subject matter experts for publication in the WCNC 2009 proceedings.

40

30

30

20
AF diversity
AF w/o diveristy
AF diversity QoS
AF w/o diversity QoS

20

10

AF diversity
AF w/o diveristy
AF diversity QoS
AF w/o diversity QoS

10
12
Number of Subcarriers

14

10

16

Mobile Station

Fig. 2. Average Rate vs. number of subcarriers for two AF schemes with
and without QoS constraints; M = 8, K = 4, 0 = 0dB

Fig. 3. Rate vs. Mobile Station for two problems with four relay schemes ;
M = 8, K = 4, N = 16, 0 = 0dB

OFDMA based cooperative cellular network with a single cell,

M mobile stations and K relay stations sharing N subcarriers.
The base station located at the center of the cell with a radius
of r1 = 300m. Relay stations are placed on a circle with
a radius of r2 = 150m at equal angular distance. MSs are
randomly distributed in the cell coverage area with a radius
between r1 and nr2 . Power level is determined to ensure SNR
Ps,km
P
ratio 0 = 2 (1+r
= K 2 (1+r ) from cellular boundary
1)
1
d
d
to the base station. The channel is generated with number of
channel taps L = 4, path loss exponent = 3 and noise ratio
d2 = r2 .
In Fig. 2, the average rates for two AF schemes with respect
to number of subcarriers are obtained. With the increase of
subcarriers, spectrum efficiency of all scenarios are improved.
Since direct transmission is within the selection pool, our
algorithm guarantee to outperform no relay cases. Moreover,
we can observe that little rate is sacrificed to guarantee QoS
performance which facilitate our implementations.
In Fig. 3, QoS guarantee results are shown in detail. We
consider a four users case where the first two users have higher
QoS requirements cm = 12 and the other two need cm = 6
as illustrated with dash line in the figure. Four schemes are
plotted and we can observe that for scenarios without QoS
constraints, the rates vary a lot between different users and
sometimes users may achieve no rates (i.e., user 2) which
means no fairness is considered in the system. With QoS
constraints, however, the rates are reallocated and users not
only have fair transmission but also meet their heterogenous
requirements as well.

problem subject to individual QoS constraints as a binary

integer programming problem. We propose a two level dualprimal decomposition based algorithm to solve the problem.
The efficiency of the algorithm is finally illustrated by numerical results.

VI. C ONCLUSION
In this paper we consider schedule and resource allocation
in OFDMA based cooperative cellular networks with multiple
sources, multiple relays and a single destination. We formulate
the power allocation relay selection and subcarrier assignment

R EFERENCES
[1] J. Laneman, D. Tse, and G. Wornell, Cooperative diversity in wireless
networks: Efficient protocols and outage behavior, IEEE Transactions
on Information Theory, vol. 50, no. 12, pp. 3062-3080, 2004.
[2] Draft standard for local and metropolitan area networksCpart 16: Air
interface for fixed and mobile broadband wireless access systemsC
multihop relay specification, IEEE Unapproved Draft Std P802.16j/D1,
2007.
[3] G. Li and H. Liu,Resource allocation for OFDMA relay networks with
fairness constraints, IEEE J. Sel. Areas Comm., vol. 24, no. 11, pp.
2061-2069, Nov. 2006.
[4] C. Bae and D. Cho, Fairness-Aware Adaptive Resource Allocation
Scheme in Multihop OFDMA Systems, IEEE Communication Letters,
vol. 11, no. 2, pp. 134-136, Feb. 2007.
[5] M. Awad and S. Shen,OFDMA Based Two-hop Cooperative Relay
Network Resources Allocation, in Proc. IEEE International Conference
on Communication, 2008, pp. 4414-4418.
[6] W. Nam, W. Chang, S. Chung and Y. H. Lee,Transmit Optimization for
Relay-Based Cellular OFDMA Systems, in Proc. IEEE International
Conference on Communication, 2007, pp. 5714-5719.
[7] R. Kwak and J. M. Cioffi,Resource-Allocation for OFDMA Multi-Hop
Relaying Downlink Systems, in Proc. IEEE Global Telecommunications
Conference, 2007, pp. 3225-3229.
[8] T. Ng and W. Yu, Joint optimization of relay strategies and resource
allocations in cooperative cellular networks, IEEE J. Sel. Areas Comm.,
vol. 25, no. 2, pp. 328-339, Feb. 2007.
[9] W. Yu and R. Lui, Dual methods for nonconvex spectrum optimization
of multicarrier systems, IEEE Trans. Commun., vol. 54, no. 7, pp. 13101322, July 2006.
[10] Z. Luo and S. Zhang, Dynamic Spectrum Management: Complexity
and Duality, IEEE J. Sel. Topics Sign. Proc., vol. 2, no. 1, pp. 57-73,
Feb. 2008.
[11] S. Boyd and L. Vandenberghe, Convex Optimization. Cambridge, U.K.:
Cambridge Univ. Press, 2004.
[12] D. P. Bertsekas, A. Nedic, and A. E. Ozdaglar, Convex Analysis and
Optimization. Belmont, MA, USE: Athena Scientific, 2003.