PAN et al.: DISTRIBUTED RESOURCE ALLOCATION FOR OFDMA-BASED RELAY NETWORKS 921
allocation. Section VII evaluates the performance of the
suggested algorithms. Finally, conclusions are presented in
Section VIII.
II. S
YSTEM MODEL
This paper investigates the problem of resource allocation in
an OFDMA-based relaying network. In particular, the OFDMA
downlink transmission is studied for a single BS cell. The
system consists of a single BS, K mobile users or UE terminals,
and L RSs. Each radio unit is equipped with a single antenna
[see Fig. 1(b)].
The relaying scenario operates as follows. The BS broadcasts
OFDMA s ymbols, and the RSs decode the symbols and retrans-
mit them to the UEs (using a DF relaying strategy) in a different
frequency band from the BS broadcast channel. Two-hop trans-
mission is considered, as shown in Fig. 1(b). The layout of the
transceivers in this figure is only for illustration. The RSs select
and allocate different subcarriers and power levels for each UE
to utilize the multiuser diversity present in the network. Perfect
knowledge of the channel-state information (CSI) is assumed at
the receivers, and this information is fed back to the RSs. The
RSs communicate with the UEs after the subcarrier allocation
has occurred. This condition ensures that the UEs can combine
the relayed symbols and the symbol that was s ent by the BS
using maximum-ratio combining (MRC). This paper focuses
on distributive resource allocation schemes for the RSs. The
subcarrier allocation decision at the BS is assumed not to be
affected. Therefore, the RSs can join or leave the system at
any time and improve the system performance without causing
instability at the BS.
TheBSisassumedtohaveN data subcarriers numbered
from 1 to N in the frequency domain. There are L RSs, and
each RS l has N
l
data subcarriers, where l ∈ [1,L], and N
l
≤
N. The subcarrier allocation results are mapped by Ω
l
(n),
where l ∈ [1,L], n ∈ [1,N], and Ω
l
(n) ∈ [1,N
l
]. For example,
Ω
l
(n)=n
l
means that the n
l
th subcarrier at the lth RS is used
to relay the data symbol carried by the nth subcarrier of the
BS. l =0 represents the BS, and consequently, Ω
0
(n)=n.
For a multiuser system, the subcarrier allocation at the BS
for multiple UEs is mapped by U(n), where n ∈ [1,N], and
U(n) ∈ [1,K]. U(n)=k means that the nth subcarrier of the
BS is used to transmit data for UE k. Ω
l
(n)=0represents the
situation where RS l does not relay for subcarrier n of the BS,
perhaps because the link quality of subcarrier n from the BS to
RS l is low, or the total number of subcarriers at RS l is less
than N.
One example is shown in Fig. 2. The BS has eight subcarriers
numbered from 1 to 8. Ω
1
(3) = 1 means that the first subcarrier
of RS 1 is allocated to relay for the third BS subcarrier, and so
on. Because the third BS subcarrier transmits data for UE 2, i.e.,
U(3) = 2, the first subcarrier at RS 1 will relay data f or UE 2. In
this example, for RS 1, the values of Ω
1
(4), Ω
1
(6), and Ω
1
(8)
are all 0, because RS 1 does not relay for these subcarriers.
p
(n
l
)
l
denotes the power allocation at the n
l
th subcarrier of
RS l, where l ∈ [1,L] and n
l
∈ [1,N
l
]. The channel gain from
the n
l
th subcarrier of RS l to UE k is represented by h
(n
l
)
l,k
,
where l ∈ [1,L], k ∈ [1,K], and n
l
∈ [1,N
l
]. To simplify the
Fig. 2. Example of subcarrier allocation. The horizontal direction of tiles
lists the active subcarriers in sequence. Note that the alignment of tiles in the
horizontal direction does not refer to spectrum overlapping.
notation, p
(n)
0
and h
(n)
0,k
are used to represent the power al-
location and the channel gain at the BS, respectively, where
n ∈ [1,N]. The total bandwidth for N subcarriers is assumed to
be B, and the bandwidth for each subcarrier is B/N. Noise at
each subcarrier is modeled as a zero-mean circular symmetric
complex Gaussian sample with variance N
0
B/N.
III. I
TERATIVE WATERFILLING FOR OPTIMAL
POW E R ALLOCATION
The resource allocation problem defined in the previous
section is a mixed integer and continuous variable optimization
problem that is generally difficult to solve. In fact, even the
subcarrier allocation problem alone (with fixed-power alloca-
tion, e.g., equal) can be viewed as a multidimensional weighted
matching problem and is NP-complete [20]. To simplify the
problem, in this section, we first investigate the power alloca-
tion problem with the following assumptions.
1) The frequency spectrum utilized at each RS does not
overlap with that used by the other RSs. With this as-
sumption, the UEs can separately detect the signals from
the BS and all RSs and then combine them using MRC.
In Section IV, it will be shown that the optimal power
allocation can still be approximated when this assumption
is removed.
2) If Ω
l
(n) =0, the SNR from the BS to RS l at subcarrier n
is assumed to be high enough such that RS l can correctly
decode the symbol, because the geographical placement
of the RSs can ensure that this condition is met. This
assumption ignores the channel constraints from the BS
to the RSs. This case is valid in several situations where
the fixed RSs are normally in the line of sight (LoS) of the
BS, and it is possible to deploy multiple receive antennas
at the fixed RSs to improve the SNR. Alternatively, the
RS can simply choose not to relay if the SNR between
the BS and the RS is low. Conditions for removing this
assumption are investigated in Section V.
3) The subcarriers are assumed to have been allocated, and
the objective now is to find the optimal power alloca-
tion for the RSs based on the given subcarrier alloca-
tion. The subcarrier allocation problem is investigated in
Section VI.