A Low Complexity Algorithm for Proportional
Resource Allocation in OFDMA Systems
Ian C. Wong, Zukang Shen, Brian L. Evans, and Jeffrey G. Andrews
Wireless Networking and Communications Group
Dept. of Electrical and Computer Engineering
The University of Texas at Austin, Austin, Texas 78712
Email: {iwong, shen, bevans, jandrews}@ece.utexas.edu
Abstract— Orthogonal Frequency Division Multiple Access
(OFDMA) basestations allow multiple users to transmit simulta-
neously on different subcarriers during the same symbol period.
This paper considers basestation allocation of subcarriers and
power to each user to maximize the sum of user data rates,
subject to constraints on total power, bit error rate, and propor-
tionality among user data rates. Previous allocation methods have
been iterative nonlinear methods suitable for offline optimization.
In the special high subchannel SNR case, an iterative root-finding
method has linear-time complexity in the number of users and
N log N complexity in the number of subchannels. We propose
a non-iterative method that is made possible by our relaxation
of strict user rate proportionality constraints. Compared to the
root-finding method, the proposed method waives the restriction
of high subchannel SNR, has significantly lower complexity, and
in simulation, yields higher user data rates.
I. INTRODUCTION
OFDMA, also referred to as Multiuser-OFDM [1], is being
considered as a modulation and multiple access method for 4th
generation wireless networks [2]. OFDMA is an extension of
Orthogonal Frequency Division Multiplexing (OFDM), which
is currently the modulation of choice for high speed data
access systems such as IEEE 802.11a/g wireless LAN [3] and
IEEE 802.16a fixed wireless broadband access [4] systems.
OFDM systems divide a broadband channel into many
narrowband subchannels. Each subchannel carries a quadra-
ture amplitude modulated (QAM) signal. The subcarriers are
combined in a computationally efficient manner by means of
an inverse fast Fourier transform (IFFT) in the transmitter.
Each complex-valued IFFT input is obtained from a QAM
constellation mapping (lookup table). The IFFT outputs form
the transmitted symbol. Before transmission, a cyclic prefix
(copy of the last few symbol samples) is prepended to the
symbol. The receiver performs the dual operations of cyclic
prefix (CP) removal, FFT, and QAM demapping.
In current OFDM systems, only a single user can transmit
on all of the subcarriers at any given time, and time division
or frequency division multiple access is employed to support
multiple users. The major setback to this static multiple access
scheme is the fact that the different users see the wireless
channel differently is not being utilized. OFDMA, on the other
hand, allows multiple users to transmit simultaneously on the
different subcarriers per OFDM symbol. Since the probability
that all users experience a deep fade in a particular subcarrier
is very low, it can be assured that subcarriers are assigned to
the users who see good channel gains on them.
The problem of assigning subcarriers and power to the
different users in an OFDMA system has recently been an area
of active research. In [5], the margin-adaptive resource alloca-
tion problem was tackled, wherein an iterative subcarrier and
power allocation algorithm was proposed to minimize the total
transmit power given a set of fixed user data rates and bit error
rate (BER) requirements. In [6], the rate-adaptive problem was
investigated, wherein the objective was to maximize the total
data rate over all users subject to power and BER constraints.
It was shown in [6] that in order to maximize the total capacity,
each subcarrier should be allocated to the user with the best
gain on it, and the power should be allocated using the water-
filling algorithm across the subcarriers. However, no fairness
among the users was considered in [6]. This problem was
partially addressed in [7] by ensuring that each user would
be able to transmit at a minimum rate, and also in [8] by
incorporating a notion of fairness in the resource allocation
through maximizing the minimum user’s data rate. In [9], the
fairness was extended to incorporate varying priorities. Instead
of maximizing the minimum user’s capacity, the total capacity
was maximized subject to user rate proportionality constraints.
This is very useful for service level differentiation, which
allows for flexible billing mechanisms for different classes
of users. However, the algorithm proposed in [9] involves
solving non-linear equations, which requires computationally
expensive iterative operations and is thus not suitable for a
cost-effective real-time implementation.
This paper extends the work in [9] by developing a sub-
carrier allocation scheme that linearizes the power allocation
problem while achieving approximate rate proportionality.
The resulting power allocation problem is thus reduced to a
solution to simultaneous linear equations. In simulation, the
proposed algorithm achieves a total capacity that is consis-
tently higher than the previous work, requires significantly less
computation, while achieving acceptable rate proportionality.
II. S
YSTEM MODEL
The block diagram for the downlink of a typical OFDMA
system is shown in Fig. 1. At the base station transmitter,
the bits for each of the different K users are allocated to the
N subcarriers, and each subcarrier n (1 ≤ n ≤ N) of user
10-7803-8504-7/04/$20.00 ©2004 IEEE SIPS 2004
Authorized licensed use limited to: CHONGQING UNIV OF POST AND TELECOM. Downloaded on October 11, 2008 at 10:17 from IEEE Xplore. Restrictions apply.