In this paper, we propose a fast adaptive power allocation method for an orthogonal frequency division multiple access (OFDMA) system that employs an adaptive modulation and coding (AMC) scheme. The proposed scheme aims to reduce the calculation complexity of greedy adaptive power allocation (APA), which is known as the optimal algorithm for maximizing the utility argument of power. Unlike greedy APA, which starts power allocation from “0”, the proposed algorithm initially allocates a certain level of power determined by the waterfilling scheme. We theoretically demonstrate that the proposed algorithm has almost the same capability of maximizing the utility argument as the greedy APA while reducing the number of operations by 2
M
, where
M
is the number of AMC levels.
1. Introduction
The orthogonal frequency division multiple access (OFDMA) system is a multicarrier system. As such, the system capacity is obtained by the sum of the individual subcarrier capacities, which highly depends on the amount of power allocated to each subcarrier. Naturally, the subcarrier capacity increases when more power is allocated. To maximize the overall system capacity, optimally controlling and assigning the power for each individual carrier within the limits of the total transmission power would be ideal. Such power allocation has been a difficult and challenging issue for many researchers. Lagrangian methods have been used as potential solutions for capacity maximization. Waterfilling, in which more power is allocated to stronger subcarriers, is known as the optimal solution for capacity maximization using Lagrangian methods
[1]
.
However, waterfilling is inappropriate for obtaining the best performance when the adaptive modulation and coding (AMC) scheme is employed, in which the power allocation is performed with a number of discrete power levels. Regarding this issue, several adaptive power allocation (APA) schemes, which are sometimes called the “bitloading” problem, have been investigated to increase the system utility in an OFDMA system with discrete AMC levels
[3]

[5]
. APA schemes have been developed with slightly different objectives and constraints. In
[3]
, the maximum utility rate has been obtained under a limited power constraint, whereas in
[5]
, the total transmission power is minimized to achieve a target datarate of the system, which is the sum of the individual datarates of all users. These schemes have an iterative procedure to successfully achieve each objective by using optimal
[3]
, heuristic
[4]
, or suboptimal
[5]
algorithms. In particular, as an optimal algorithm, greedy APA (the modified LevinCampello algorithm) maximizes the utility argument of power at each bit assignment. However, because zero power is initially allocated to all subcarriers, the processing time for iterative allocation of power to all subcarriers until the total allocated power reaches the limit is excessively long. In this paper, we propose a fast convergent power allocation method to significantly reduce the processing time for an OFDMA system that employs AMC.
The remainder of this paper is organized as follows. In section 2, we explain the OFDMA channel architecture and some system parameter. In section 3, we provide problem formulation and proposed algorithm. Section 4 describes the computer simulation model and its numerical results. Finally, conclusions are presented in Section 5.
2. System Model
We assume that AMC has
M
discrete channel states and the channels are already allocated to users by means of one of the existing subcarrier allocation methods such as maximum C/I or proportional fairness (PF). In this paper, we address only the power allocation to each subcarrier. The channel state of subcarrier i is denoted by
ρ_{i}
, which the corresponding user experiences. It is defined as
, where
N_{i}
and
h_{i}
are the noise power density and frequency response, respectively, of subcarrier
i
[2]
. Thus, the channel state vector is defined by
where
S
denotes the number of subcarriers.
3. Problem Formulation and Proposed Algorithm
In this section, we formulate an optimization problem to maximize the system utility for the allocated subcarriers and provide a power allocation algorithm to obtain an optimal solution.
Let
U_{i}
(·) be the utility function for subcarrier
i
and
P_{total}
be the total transmission power. If subcarrier
i
has an allocated power
P_{i}
, then its utility is
U_{i}
(
P_{i}
). Thus, we are interested in the following problem:
where
U_{i}
(
P_{i}
)=
a_{i}
log(1+
b_{i}P_{i} ρ_{i}
) is a differentiable nondecreasing concave function,
a_{i}
is the weight vector for the allocated user at subcarrier
i
to generalize the problem, and
b_{i}
is the factor for controlling the bit error rate of the allocated user at subcarrier
i
. By changing the value of
a_{i}
, Problem (
P
) can cover throughput maximization as well as PF allocation, and
b_{i}
is determined by
b_{i}
= −1.5/ln(5⋅BER
_{i}
) [8], where BER
_{i}
is the bit error rate of the allocated user at subcarrier
i
. Then, the optimal power allocation for problem (
P
) has the following solution
[1]
:
where (
x
)
^{+}
= max(
x
, 0) and
λ
is chosen such that the power constraint is satisfied:
This equation represents the waterfilling method of power allocation.
If the fixed subcarrier allocation is based on the subcarrier channel state as in the greedy or PF algorithm for system throughput, the variation of each subcarrier channel state is sufficiently low to satisfy the following constraint:
Thus, the solution of problem (
P
), (4), is rewritten as:
where
E
(
a_{i}
) indicates the average of
a_{i}
. The term (1/
S
)Σ(1/
b_{k}ρ_{k}
) on the righthand side indicates the average of the inverse channel states. Thus, we know that the performance improvements are marginal even though APA is employed in a continuous utility system under the following assumptions
[2]
:
A1) The variation of each subcarrier channel state is sufficiently low.
A2) The variation of weighting factor a_{i} decreases as longterm utility is maximized.
By using these properties (A1 and A2), we propose a new algorithm for a discrete data rate. The proposed algorithm allocates power to maximize the system utility. This purpose is the same as that of the underlying greedy APA
[3]
. However, our proposed scheme initializes
P_{i}
using the
value, whereas greedy APA initializes
P_{i}
as “0.” Therefore, the proposed scheme can reduce the number of iterations for power allocation.
To compare the performance of the proposed algorithm with greedy APA, we explain some variables by using
Fig. 1.
In this figure,
is the optimum power for the
i
th subcarrier and
P_{i}
[
n
] is the minimum required power of level
n
for the
i
th subcarrier. The relationship between (
δ
_{1}
) and (
δ
_{2}
) as well as that between (
δ
_{2}
) and (
δ
_{3}
) in
Fig. 1
are explained by
Theorems 1
and
2
, respectively. The inequality of the slopes for (
δ
_{1}
) and (
δ
_{4}
) are shown in the
Claim
.
Some variables for a new algorithm
The proposed algorithm is described in the following procedures:
1) For initialization,
2) The remaining power,
P_{total}
−Σ
_{i}P_{i}
, is allocated using greedy APA.
Theorem 1:
If
U_{i}
(
P_{i}
) is a differentiable nondecreasing concave function, for every
i
, the following property is satisfied:
where Δ
U_{i}^{L}
=
U_{i}
(
Pi
[
n
^{*}
])−
U_{i}
(
P_{i}
[
n
^{*}
−1]), Δ
P_{i}^{L}
=
P_{i}
[
n
^{*}
]−
P_{i}
[
n
^{*}
−1], Δ
U_{i}
^{*}
=
U_{i}
(
P_{i}
^{*}
)−
U_{i}
(
P_{i}
[
n
^{*}
]), and Δ
P_{i}
^{*}
=
P_{i}
^{*}
−
P_{i}
[
n
^{*}
].
Proof:
Eq. (8) is achieved because
U_{i}
(
P_{i}
) is a nondecreasing and concave function and
Theorem 2:
If
U_{i}
(
P_{i}
) is a differentiable nondecreasing concave function, for every
i
and
j
, the following property is satisfied:
Proof: If
and
are optimal, then any change in allocation will not increase the average utility. Let 0 < Δ
P
<
, 0 < Δ
P
<
and two arbitrary users exchange an amount of power equal to Δ
P
with each other. The new average utility will then be equal to or less than the optimal one. This inequality is given by
which is equivalent to
When Δ
P
→ 0, we have
and similarly, we obtain
Using (12) and (13), we obtain
Claim:
If
U_{j}
(
P_{j}
) is a nondecreasing concave function and variables
α_{j}
and
β_{i}
are given by
and
Proof:
U_{j}
(
P_{j}
) is a nondecreasing concave function and
P_{j}
[
n
^{*}
+1] >
>
P_{j}
[
n
^{*}
]. Therefore, approximate equality and inequality are given by
From
Theorem 1
and (17), for every
i
and
j
, variables
α_{j}
and
β_{i}
satisfy the inequalities
α_{j}
≈ 1 and
β_{i}
> 1, respectively
Therefore, the following equation is satisfied by using
Theorem 2
and
Claim
for every
i
and
j
:
Thus, if
P_{i}
[
n
^{*}
] is allocated to every
i
th subcarrier before
P_{i}
[
n
^{*}
+1] is allocated to any
j
th subcarrier, the performance of greedy APA is guaranteed.
For the iteration component, the greedy APA algorithm finds the subcarrier with the maximum value of system utility per power. Thus, the computational complexity of a single iteration is
O
(
S
). We can ignore other components of the iteration and initialization processes because their computational complexity is much smaller than
O
(
S
). Therefore, if
A_{i}
is the number of power allocations of subcarrier
i
, the computational complexity of greedy APA is
We can rewrite (19) as follows because max
A_{i}
is
M
:
For the proposed scheme, the computational complexity of the initialization is
O
(
S
). Furthermore, the computational complexity of the proposed scheme is
O
(
S
) during a single iteration because the iteration component is the same as that of greedy APA. However, because of the initialization, the remaining power is given by Σ
_{i}
, which is always less than Σ
_{i}
. Therefore, the power allocation to each subcarrier occurs only once or not at all. Finally, the maximum computational complexity of the proposed scheme is
4. Numerical Results
This section, the performance of the proposed scheme is evaluated in terms of system utility and the number of operations by comparing it with the performances of the greedy APA
[3]
, adaptive transmission scheme (ATS)
[4]
, or waterfilling
[1]
schemes under random varying radio channel conditions. As assumed in section III, the overall system capacity function is a nondecreasing concave function. Therefore, we use the overall system capacity as the system utility for a simple simulation. Although the discrete utility function is considered for the proposed scheme, greedy APA, and ATS, the continuous utility function is considered for the waterfilling scheme.
The OFDMA system, proposed by the IEEE 802.16 WMANS standard, is considered herein with 240 subcarriers and 7 AMC levels. The probability density function of the signaltonoise ratio (SNR) is assumed to be an exponentially distributed random variable with mean values uniformly distributed between [0, 16] dB
[6]
. We suppose that user traffic is sufficiently heavy to fully occupy a buffer.
Fig. 2
shows the average system utility for 100 symbol times. In
Fig. 2
, the maximum C/I method with the dynamic subcarrier allocation algorithm is used for all power allocation schemes. The system utility of each scheme increases as the number of users increases owing to multiuser diversity. The waterfilling scheme, which is the solution to the optimization problem for the continuous system utility function, shows maximum system utility. The proposed scheme outperforms ATS and equal power allocation with the discrete system utility function and shows the same performance as greedy APA.
Average system utility versus number of users
Fig. 3
shows the number of operations for power allocation, which is the total number of iterations for 100 symbols. The proposed scheme reduces the number of operations by almost thirteen times compared with greedy APA. This is because the average AMC level for each selected user in our simulation is about 6. Therefore, the proposed scheme needs less than one operation for each subcarrier, however, greedy APA needs more than six operations for each subcarrier. This result corresponds to (20) and (21).
Number of operations for power allocation
5. Conclusion
In this paper, we proposed a fast APA algorithm to maximize the discrete system utility for an OFDMA system employing AMC. The proposed scheme showed the same performance as greedy APA, which is the optimum solution for a discrete system utility function. In addition, it reduced the number of operations by almost 2M times that of greedy APA. Therefore, the proposed scheme can be used in an actual system that employs AMC to maximize the system utility within a short processing time.
Acknowledgements
This work was supported in part by Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education, Science and Technology (NRF2012R1A1A4A01).This work was also supported in part by Defense Acquisition Program Administration and Agency for Defense Development under the contract UD130007DD.
BIO
Sungho Hwang He received the B.S., M.S., and Ph. D. degrees in electrical engineering from Kyungpook National University in 2004, 2006, and 2010, respectively. In 2010, he joined LIG Nex1 R&D center as a Research Engineer. His current research interests include radio resource management, MAC protocol design, and RADAR resource management.
HoShin Cho He received the B.S., M.S., and Ph. D. degrees in electrical engineering from the Korea Advanced Institute of Science and Technology in 1992, 1994, and 1999, respectively. From 1999 to 2000, he was a Senior Member of the Research Staff with the Electronics and Telecommunications Research Institute, where he was involved in developing a base station system for IMT2000. From 2001 to 2002, he was a faculty member of the School of Electronics, Telecommunications, and Computer Engineering, Hankuk Aviation University. In 2003, he joined faculty of the School of Electronics Engineering, Kyungpook National University. In 2010, He was a visiting professor at University of Connecticut, USA. His current research interests include radio resource management, MAC protocol design, traffic modeling, selforganized network in wireless mobile communication systems and underwater acoustic sensor networks. Prof. Cho was awarded a rising researcher fellowship of KRF in 1998, and is a member of IEEE, IEICE, IEEK, ASK, and KICS.
Tse D.
2005
Fundamentals of Wireless Communication
Cambridge University Press
Song G.
,
Li Y. (G.)
2005
“CrossLayer Optimization for OFDM Wireless NetworksPart I: Theoretical Framework,”
IEEE Trans. Commun.
4
(2)
614 
624
Song G.
,
Li Y. (G.)
2005
“CrossLayer Optimization for OFDM Wireless NetworksPart II: Algorithm Development,”
IEEE Trans. Commun.
4
(2)
625 
634
Kim K.
2005
“Efficient Adaptive Modulation and Power Allocation Algorithm for OFDMA Cellular Systems,”
in Proc. 2005 Wireless Telecommunications Symposium
169 
173
Chen Y. F.
,
Chen J. W.
2008
“A Fast Subcarrier, Bit, and Power Allocation Algorithm for Multiuser OFDMbased Systems,”
IEEE Trans. Veh. Tech.
57
(2)
873 
881
DOI : 10.1109/TVT.2007.907029
Ali S.H.
,
Lee KiDong
,
Leung V.C.M.
2007
“Dynamic resource allocation in OFDMA wireless metropolitan area networks,”
IEEE Wireless Communications
14
(1)
6 
13