Sub-Carrier Allocation in OFDM Systems: Complexity, Approximability and

Algorithms

Pai-Han Huang, Yi Gai, Bhaskar Krishnamachari Ashwin Sridharan

EE-System Sprint Lab
University of Southern California [email protected]
{paihanhu,ygai,bkrishna}@usc.edu

Abstract LANs[6], in order to provide high-speed mobile wireless

data services.
Orthogonal Frequency Division Multiplexing (OFDM) Although the OFDMA framework provides a mecha-
has become the de facto standard for fourth generation nism for a user to spread information across the set of as-
wireless networks[5]. In such a network, the frequency signed sub-carriers, it still leaves the question of how to as-
band is divided into numerous orthogonal sub-carriers. In sign sub-carriers to users. This immediately presents itself
each time-slot, disjoint sets of sub-carriers can be assigned as a resource allocation problem in combinatorics: in each
to users based on some target objective. The users in turn time-slot, give m users and n sub-carriers, how to assign
transmit data by spreading the information across the as- disjoint sets of sub-carriers to each user so as to optimize
signed sub-carriers. The main contribution of this work some system metric. The allocation problem has received
is a formal analysis of the complexity of this class of re- active interest in the research community and has been stud-
source allocation problems for various objectives and sce- ied from basically two perspectives (based on the objective
narios. Specifically we formally prove that the sub-carrier function): schemes that seek to minimize the amount of
resource allocation problem is NP-hard for both power min- transmit power [8][17] or those that seek to achieve max-
imization as well as rate maximization in both uplink and imum throughput [10][14]. However, a common theme
downlink scenarios. More importantly, we also provide (elaborated in Section 2) across these works is that they all
in-approximability results for these scenarios, outlining a propose heuristics that are evaluated only through simula-
hard limit on what deterministic allocation algorithms can tions. This leaves open the question of how well these algo-
achieve for this class of problems. While these results are rithms perform in general, and at a more fundamental level,
mostly of a negative nature, we also propose a class of how well can any deterministic algorithm perform for this
heuristics, called k-interchange, which are shown to yield class of problems.
close to optimal performance via simulations. We address this gap in existing literature by formally ad-
dressing the complexity of the sub-carrier allocation prob-
lem under several scenarios, namely uplink and downlink
OFDMA, for both power minimization and rate maximiza-
1. Introduction tion. The problem is shown to be NP-hard in all versions.
While this is of academic interest, more importantly we also
Orthogonal Frequency Division Multiple Access present approximability bounds for these problems, that is,
(OFDMA) is a time-frequency hybrid system wherein the we bound the best performance achievable by any algo-
frequency band is divided into a large number of small rithm. In addition, we propose a k-interchange heuristic
bands called sub-carriers that use specific frequencies which allows a natural trade-off between time complexity
so as to be completely orthogonal to each other. In and performance and utilize it to demonstrate both: its near-
every time-slot, each user is assigned a disjoint set of optimal performance in simulations as well as worst case
sub-carriers across which the user may spread information scenarios.
for transmission purposes. Because of its capability of Our contributions can be summarized as follows :
exploiting multi-path fading and spatial/temporal diversity
to improve performance, it becomes physical layer trans- 1. We formally show that the general problem of sub-
mission scheme of choice adopted by fourth generation carrier allocation with the objective of power min-
wireless networks, e.g. cellular networks [5], broadband imization is NP-hard and cannot be approximated
 within a fixed factor by any deterministic algorithm. access the same partition, their solution includes a conflict
resolving mechanism.
2. We also show that the rate-maximization version is In sum, none of existing papers we are aware of has
NP-hard and cannot be approximated to a factor bet- a proof of hardness or performance bound about the sub-
m
ter than m+1 . carrier allocation problem.
3. We propose a local search based, polynomial time
algorithm, k−interchange. In most scenarios, 3. System Model and Problem Formulation
k−interchange demonstrates close to optimal perfor-
mance. On the other hand, we also use the k- We assume complete knowledge of channel states at both
interchange heuristic to demonstrate scenarios corre- transmitter and receiver ends, and they do not change during
sponding to when worst case performance can occur. the scheduling. A subcarrier can be used by at most 1 user at
This paper is organized as follows: In Section 2 we out- any instance, and every user’s rate request must be satisfied.
line past related work and differentiate our contribution. We refer these two restrictions to “feasibility constraints”.
Section 3 presents the system model and formal problem We assume that the system has m sub-carriers and a
formulation. In Section 4, we prove the hardness and in- static population of n users. The focus of this work is al-
approximability of our problem. Section 5, presents numer- location of sub-carriers in a single time-slot (a granularity
ical comparison of our proposed algorithms and the optimal readily available in current 4G networks). Each user i re-
solutions and the worst case scenario. Future directions are quests a rate ri in the time-slot. Sub-carrier allocation is
addressed in Section 6. determined at the base-station as a function of the perceived
signal strength of each user on each sub-carrier as well as
the user requested rate. In the uplink environment, after the
2. Related Work allocation is conveyed to the user (we assume the implicit
presence of such a mechanism. For example, in WiMax,
Although the continuous case of single-user/multi- this information is conveyed using a UL-MAP message),
subcarrier has been optimally solved [4][2], and the dis- each user performs rate loading across the assigned sub-
crete version[7] of single-user/multi-subcarrier has also carriers to transmit information. On the other hand, the
been solved near-optimally, the case of multi-user/multi- rate loading becomes a task of the base-station in the down-
subcarrier power allocation is still an area of active investi- link environment. Rate loading is typically governed by the
gation. In addition, it has been shown that adaptive resource available transmission rates (i.e., modulation schemes).
allocation can significantly increase the capacity of OFDM For convenience, we summarize the symbols used in this
systems[16], comparing with fixed resource allocation strat- paper as follows.
egy [13][12][3]. Thus, how to allocate power or data rate
on each sub-carrier to satisfy all requests, while optimiz- • S: The set of all sub-carriers. S = {si |i = 1, . . . , m}.
ing either power or throughput related objectives becomes a
popular research issue. • U : The set of all users. U = {ui |i = 1, . . . , n}
Wong et al.[17] propose a multi-user, multi sub-carrier,
bit and power allocation algorithm, which aims to minimize • ri : The constant data rate that the user i requests.
the overall power consumption. Their iterative search al-
gorithm exploits Lagrangian Relaxation technique. How- • rij : The data rate user i loads on subcarrier j.
ever, this algorithm does not converge rapidly in general.
• pi : The power budget of user i.
Rhee et al.[11] try to maximize the minimal user through-
put, such that a fixed total power budget is given. One of • S i : This represents the set of sub-carriers which are
their assumption: every sub-carrier is allocated with equal allocated to user i.
power, limits the applicability of their solution. Kivanc et
al.[8] adopt a similar formulation as [17]. The authors pro- • fij (rij ): The power required to transmit at rate rij by
pose a two-step solution: first determine the number of sub- user i on sub-carrier j is given by fij (rij ).
carriers allocated to each user, and then allocate sub-carriers
to users in a greedy manner. Thereafter, they refine their so- • di,j : di,j = 1 if sub-carrier j is allocated to user i.
lution quality by using local search technique. Alen et al.[1] Otherwise, it equals 0.
devise a distributed algorithm aims to maximize system ca-
pacity. They first divide available sub-carriers into a set of • Ti : In practice, a user is allowed to transmit only at cer-
partitions, and let users contend these partitions themselves. tain discrete rates. We assume that the set of feasible
To solve the issue of partition sharing, i.e. multiple users rates allowed on a sub-carrier i is given by Ti .
3.1 Uplink Sub-carrier Allocation 3.2 Downlink Sub-carrier Allocation

When OFDM downlink sub-carrier allocation is consid-

We assume the functions {fij (·)} are convex, increas-
ered, a key difference is that individual user power con-
ing, continuous, and fij (0) = 0, ∀ui ∈ U, sj ∈ S. In
straints are replaced with the power constraint for total sum
addition, every user i has a power limit pi that needs to
of transmit powers, i.e the entire base-station’s transmit
be respected. The objective of our interest is to minimize
power (which is critical in practice to reduce inter-cell in-
the maximal individual user’s power consumption, and the
terference). This problem is referred to Continuous Down-
problem is referred to Continuous Uplink Sub-carrier Al-
link Sub-carrier Allocation, and this optimization problem
location. Mathematically, we can formulate it as Equation
can be described by removing the last constraint, the power
1:
budget constraint, inPEquation P 1, and replacing the objec-
X tive with minimize ui ∈U sj ∈S fij (rij dij ). In addition,
minimize maxui ∈U { fij (rij di,j )}
sj ∈S
if {fij (·)} are discrete, then this problem is referred to Dis-
X crete Downlink Sub-carrier Allocation, and we have to re-
subject to: rij di,j = ri , ∀ui ∈ U place one more constraint rij ≥ 0 with rij ∈ Tj .
sj ∈S

di,j ∈ {0, 1}∀ui ∈ U, sj ∈ S 4. NP-hardness and In-approximability

X
di,j ≤ 1, ∀sj ∈ S
ui ∈U 4.1 NP-hardness Proof
rij ≥ 0, ∀ui ∈ U, sj ∈ S
X The decision version of Continuous Downlink Sub-
di,j ≥ 1, ∀ui ∈ U carrier Allocation can be stated as:
sj ∈S
X Problem 1 Given a set of n user rate requests, convex con-
fij (rij di,j ) ≤ pi , ∀ui ∈ U (1) tinuous rate-power equations for n users and m sub-carriers
sj ∈S
combination, and m > n, does there exist a set of sub-
carrier and user assignment with rate allocation on individ-
If {fij (·)} are convex, increasing, fij (0) = 0, ∀ui ∈ ual sub-carrier, such that the sum of all user’s power con-
U, sj ∈ S, but discrete, i.e. only certain rate are allowed sumption is at most P , every user’s request is satisfied, and
on a sub-carrier, then this problem is referred to Discrete no sub-carrier is allocated to more than 1 user?
Uplink Sub-carrier Allocation, and can be mathematically
stated by replacing rij ≥ 0 with rij ∈ Tj in Equation 1. The NP-hardness of Continuous Downlink Sub-carrier
Another interesting uplink problem is trying to maximize Allocation is shown below.
total transmission rate, subject to a set of fixed power bud- Theorem 1 Continuous Downlink Sub-carrier Allocation
get, and can be mathematically described as Equation 2: is NP-hard.
X X proof: We first show that Subset Sum[9] ≤P Continu-
maximize rij di,j
ous Downlink Sub-carrier Allocation. Consider an arbi-
ui ∈U sj ∈S
X trary instance of Subset Sum, with a set of natural numbers
subject to: fij (rij di,j ) ≤ pi , ∀ui ∈ U W = {wi }, and a target V . We construct a corresponding
sj ∈S two user Continuous Uplink Sub-carrier Allocation instance
di,j ∈ {0, 1}, ∀ui ∈ U, sj ∈ S as follows. For every wi , we construct a sub-carrier i with
X a rate-power equation, which is the same for both users, i.e.
di,j ≤ 1, ∀sj ∈ S f1i = f2i = fi . Specifically, fi has the following proper-
ui ∈U
X ties: the power for rate 0 is 0, the power of rate wi is no more
P 1
di,j ≥ 1, ∀ui ∈ U (2) than |W | , the power of rate wi + |W | is no less than P , and
sj ∈S the rate-power relation between rate 0 and infinity is contin-
uous and convex. This constructed rate-power equation can
Similarly, if the given rate-power equations are discrete, be plotted as Figure 1. To satisfy the above constraints for a
then we add rij ∈ Tj , ∀ui ∈ U, sj ∈ S into Equation 2. constructed rate-power equation, we can use a function like
We refer the above two versions of rate maximizing fi (r) = α(2βr −1) where α and β are unknown, or a piece-
problems as Continuous Rate Maximizing Sub-carrier Al- wise linear function. In addition, finding feasible α and β,
location and Discrete Rate Maximizing Sub-carrier Alloca- or a piece wise linear function can be done in polynomial
tion, respectively. time.
 Figure 1. An example rate-power curve of a Figure 2. An example rate-power curve of
constructed sub-carrier in Continuous Down- a constructed sub-carrier in Discrete Uplink
link Sub-carrier Allocation. (Note: This figure Sub-carrier Allocation. (Note: This figure is
is only for illustration purpose.) only for illustration purpose.)

We claim that Subset Sum has a satisfying solution if and proof: The proof of Subset Sum ≤P Continuous Uplink
only if Continuous Downlink Sub-carrier Allocation has an Sub-carrier Allocation is line by line similar to Theorem 1
assignment,
Pm which can satisfy two users with rate requests with two additional conditions: the power budget p1 = ∞
V and ( i=1 wi − V ) and the total power consumption is and p2 = ∞.
no more than P . Suppose Subset Sum has a solution such We claim that Subset Sum has a satisfying solution if and
that the sum of the subset S is exactly V . If we allocate only if Continuous Uplink Sub-carrier Allocation has an as-
every corresponding sub-carrier in S to one user, and all
Pm which can satisfy two users with rate requests V
signment,
the remaining sub-carriers to the other user, and load every and ( i=1 wi − V ) and the maximal individual power con-
sub-carrier with rate wi , then this assignment would be a sumption is no more than P . If Subset Sum has a satisfying
satisfying solution to Continuous Downlink Sub-carrier Al- solution, then the optimal solution for Continuous Uplink
location. On the other hand, if Subset Sum is a NO instance, Sub-carrier Allocation has value no more than P , thus mak-
then no subset can give us a sum exactly V . Because every ing it a YES instance. On the other hand, if Subset Sum is
wi is a natural number, the difference of sum between any a NO instance, then, for the same reasons as in the proof
subset and V must be no less than 1. In addition, the largest of Theorem 1, we know the maximal individual power con-
number of sub-carrier a user can be allocated is |W | − 1. sumption is higher than P , which implies a NO instance of
Consequently, one of the two users has to load at least one Continuous Uplink Sub-carrier Allocation.
of the sub-carrier assigned to him/her with rate higher than Also, by using sub-carriers with rate-power relations as
1
wi + |W | , which implies the maximal individual power con- plotted in Figure 2, a line by line similar proof as in Theo-
sumption higher than P , thus making the total power con- rem 3 can give us the following conclusion.
sumption also higher than P .
In the proof of Theorem 1, if we replace the rate-power Theorem 4 Discrete Uplink Sub-carrier Allocation is NP-
equations with discrete ones, which can be obtained by hard.
discretizing the continuous counterpart with polynomially
many pieces as plotted in Figure 2, then a line by line simi- The decision version of Continuous Rate Maximizing
lar proof can give us the following conclusion. Sub-carrier Allocation is stated as follows.

Problem 2 Given a set of n user power budgets, convex

Theorem 2 Discrete Downlink Sub-carrier Allocation is
continuous rate-power equations for n users and m sub-
NP-hard.
carriers combination, and m > n, does there exist a set of
Next, we prove the NP-hardness of Continuous Uplink sub-carrier and user assignment with power allocation on
Sub-carrier Allocation. Note that, due to the space con- individual sub-carrier, such that the sum of all user’s rate
straint and the similarity between Problem 1, the decision is at least R, every user’s power budget is honored, and no
problem statement is omitted. sub-carrier is allocated to more than 1 user?

Theorem 3 Continuous Uplink Sub-carrier Allocation is Theorem 5 Continuous Rate Maximizing Sub-carrier Al-
NP-hard. location is NP-hard.
proof: The proof of Subset Sum ≤P Continuous Rate Max-
imizing Sub-carrier Allocation is line by line similar to The-
orem 1, except the rate-power equations: the power for rate
R 1
0 is 0, the power of rate |W | − 1 is no less than wi − |W | ,
R
the power of rate |W | is no more than wi , the power of rate
R+1
P m
|W | is no less than i=1 wi −1, and the rate-power relation
between rate 0 and infinity is continuous and convex. This
constructed rate-power equation can be plotted as Figure 3.
We claim that Subset Sum has a satisfying solution if
and only if Continuous Rate Maximizing Sub-carrier Allo-
cation has an assignment,
Pm which honors two users’ power
budgets V and ( i=1 wi − V ) and has total rate no less
Figure 3. An example rate-power curve of a
than R. Suppose Subset Sum has a solution such that the
constructed sub-carrier in Continuous Rate
sum of the subset S is exactly V . Then, we can allocate
Maximizing Sub-carrier Allocation.
every corresponding sub-carrier in S to one user, and all the
remaining sub-carriers to the other user. Moreover, every
R
sub-carrier is loaded with rate exactly |W | . This assignment
can be a satisfying solution to Continuous Rate Maximizing proof: The proof of Subset Sum ≤P Continuous Downlink
Sub-carrier Allocation. On the other hand, if Subset Sum is Sub-carrier Allocation is line by line similar as Theorem 3,
1
a NO instance, then no subset can give us a sum exactly except that the power for rate wi + |W | is no less than αP .
V . Because every wi is a natural number, the difference of The rate-power equations of constructed sub-carriers can be
sum between any subset and V must be no less than 1. In plotted in Figure 4.
addition, the largest number of sub-carrier a user can be al- We claim that Subset Sum has a satisfying solution if
located is |W | − 1, and and only if an α−approximation algorithm of Continuous
Pmthe highest power budget of these
two user is at most i=1 wi − 1. Consequently, one of Downlink Sub-carrier Allocation generates an solution with
the two users has to load power on one of the sub-carrier as- total power consumption at most αP . Suppose Subset Sum
1 has a solution such that the sum of the subset S is exactly
signed to him/her with value no more than wi − |W | . On the
other hand, the other user can load power on at most one of V , then we know the optimal solution for the correspond-
the ing Continuous Downlink Sub-carrier Allocation is no more
Pmsub-carrier assigned to him/her with value no more than
i=1 wi − 1. Therefore, the total rate must be less than R,
than P . Consequently, an α−approximation algorithm of
which implies a NO instance of Continuous Rate Maximiz- Continuous Downlink Sub-carrier Allocation will give a so-
ing Sub-carrier Allocation. lution that is at most αP .
By replacing the continuous constructed rate-power On the other hand, if Subset Sum is a NO instance, then
equations in the proof of Theorem 5 with discrete ones, a no subset can give us a sum exactly V . Because every wi
line by line similar proof can give us the following conclu- is a natural number, the difference of sum between any sub-
sion: set and V must be no less than 1. In addition, the largest
number of sub-carrier a user can be allocated is |W | − 1.
Theorem 6 Discrete Rate Maximizing Sub-carrier Alloca- Consequently, one of the two users has to allocate at least
tion is NP-hard. one of the sub-carrier assigned to him/her with rate higher
1
than wi + |W | . Therefore the optimal maximal individual
4.2 In-approximability Proof power consumption is higher than αP , and so is the total
power consumption, which implies the solution provided by
In the previous section we rigorously demonstrated the α−approximation algorithm must be higher than αP .
a standard assumption that various versions of the sub- Similarly, by replacing the constructed rate-power equa-
carrier problem are fundamentally hard. We next compute tions in the proof of Theorem 7 with discrete ones similar
to what extend deterministic polynomial time algorithms to Figure 4, we can have the following theorem:
can approximate the optimal solution in such scenarios. Theorem 8 Achieving an approximation ratio α, ∀α ≥ 1
Gap-introducing technique[15] is adopted in the following for Discrete Downlink Sub-carrier Allocation is NP-hard.
proofs.
Using a similar technique as we prove Theorem 1 and 3,
Theorem 7 Achieving an approximation ratio α, ∀α ≥ 1 1 and 2, we can have the following conclusions:
for Continuous Downlink Sub-carrier Allocation is NP-
hard. Theorem 9 Achieving an approximation ratio α, ∀α ≥ 1
 Figure 4. An example rate-power curve of a Figure 5. An example rate-power curve of a
constructed sub-carrier in Continuous Uplink constructed sub-carrier in Continuous Rate
Sub-carrier Allocation. Maximizing Sub-carrier Allocation.

for Continuous Uplink Sub-carrier Allocation and Discrete

m = |W |, thus completes our proof.
Uplink Sub-carrier Allocation are both NP-hard.
Again, using a line by line similar proof with discrete
For the Continuous Rate Maximizing Sub-carrier Allo- version of Figure 5, we can have the following theorem:
cation, we have a slightly different conclusion: m
Theorem 11 Achieving an approximation ratio 1+m for
m
Theorem 10 Achieving an approximation ratio for
1+m Discrete Rate Maximizing Sub-carrier Allocation is NP-
Continuous Rate Maximizing Sub-carrier Allocation is NP- hard.
hard.
proof: Consider the above reduction of Subset Sum to Con- 5. Simulation and Discussion
tinuous Rate Maximizing Sub-carrier Allocation with the
1 Although we have proved the in-approximability of var-
following changes. The power for rate wi − W is no less
αR
than |W | − (1 − α)R − 1, and can be plotted in Figure 5. ious sub-carrier allocation problems, we also notice that
We claim that Subset Sum has a solution if and only if an a local search based algorithm, which is referred to k-
α−approximation algorithm of Continuous Rate Maximiz- interchange and is listed in 1, performs close to optimal in
ing Sub-carrier Allocation gives a solution with total rate at all of our simulation instances.
least αR. Suppose Subset Sum has a solution such that the
sum of the subset S is exactly V , then we know the optimal 5.1 k-interchange Algorithm
solution for the corresponding Continuous Rate Maximiz-
ing Sub-carrier Allocation is no less than R. Consequently,
an α−approximation algorithm of Continuous Rate Maxi- Algorithm 1 k-Interchange Algorithm for Uplink
mizing Sub-carrier Allocation will give a solution that is no 1: Start with t = 0, and E = {(ui , sj )|i = 1, . . . , m; j =
less than αR. 1, . . . , n}.
If Subset Sum is a NO instance, then no subset can give 2: Randomly assign all sub-carriers to users under the fea-
us a sum exactly V . Because every wi is a natural number, sibility constraint.
the difference of sum between any subset and V must be no 3: We denote this assignment set as S 0 .
less than 1. In addition, the largest number of sub-carrier 4: while ∃V ⊂ E under feasibility constraint, such that
a user can be allocated is P |W | − 1, and the highest power |V | = m, |V − S t | = |S t − V | ≤ k, and the objective
budget a user can have is wi − 1. Consequently, one of can be improved by more than the threshold factor  do
the two users has to allocate one of the sub-carrier assigned 5: Let S t = V
1 t=t+1
to him/her with power at most wi − |W | . On the other hand,
6:
the other user can load at most one of the sub-carrier allo- 7: end while
P
cated to him/her with power no higher then wi − 1, thus
the total rate these two users can have must be less than αR, The k-interchange algorithm works in the following
and so is the output of the α−approximation algorithm. fashion. It starts with a random feasible solution, wherein a
However, in order to make the reduction valid, we need solution comprises feasible sub-carrier allocation to users,
αR |W |
|W | −(1−α)R−1 > 0, which implies α > 1+|W | . Because followed by a feasible rate loading on assigned sub-carriers
by the respective users. It then explores solutions in the
neighborhood of the current one, by randomly permuting
up to k sub-carriers across users and identifying an allo-
cation which can improve existing solution by an amount
more than some a priori chosen factor . If no such solu-
tion is found, the algorithm terminates, else it proceeds to
explore the k-neighborhood of the new solution.
k-interchange algorithm is consisted of two parts. In the
first part, k-interchange needs to assign all sub-carriers to
all users under the feasibility constraints stated in previous
section. In the second part, after every user being assigned
a set of sub-carriers, he/she needs to load power onto each
of these sub-carriers to satisfy his/her date rate demands.
Figure 6. Required average bit SNR (dB) of
optimal and 2-interchange solutions. Param-
5.2 Simulation Environments eters: m = 10, n = {2, 3, 4, 5}.

In our simulation, we use 1-, 2-, and 3-interchange algo-

rithm, i.e. k = {1, 2, 3}, and compare their solutions with
optimal ones, which are computed by exhaustive search.
There are 2 to 5 users, and all of their rate requests are
10. Up to 10 sub-carriers downlinks are available, and the
number of sub-carriers is strictly larger than the number of
users in every instance. (Note that computation of the op-
timal solution is computationally very expensive and hence
we are forced to limit scenarios to small problems.) Ev-
ery sub-carrier has the same bandwidth, and we assume the
single-sided noise Power Spectral Density for every sub-
carrier and every user is 1. The signal propagation environ-
ment utilized a simplified path loss model combined with
log-normal shadowing [4]. The path loss statistics were
assumed to be independent across users with the path loss Figure 7. Required average bit SNR (dB) of
factor chosen uniformly in the range [−10dB, −20dB] and optimal and 2-interchange solutions. Param-
the exponent in the range [2, 3]. The log-normal shadowing eters: m = {4, 5, 6, 7, 8, 9, 10}, n = 3.
model is characterized by a random variable ψdB with nor-
mal distribution N (0dB, 3dB). M-QAM is adopted, and
the required power for supporting c bits/symbol at a given
BER is provided in Wong’s paper [17]. In this paper, we as-
sume the BER for every user is 10−4 . In addition, the value
of  used for k-interchange algorithm is 0.01.

5.3 Simulation Results

In Figure 6, 7, and 8, we plot the required bit SNR (in

dB) for the optimal and 2-interchange algorithm solutions
by varying user number, sub-carrier number and the vari-
ance of log-normal model. The parameters used in these
figures are described in the corresponding captions, and the
Figure 8. Required average bit SNR (dB) vs.
value plotted are averaged over 100 iterations under differ-
average computing time per iteration for var-
ent settings. Note that, although we only plot the results for
ious k-interchange and optimal solution. Pa-
the settings specified in the captions, the results for all the
rameters: m = 10, n = 3.
other parameter combinations are very similar to what we
present here.
 As plotted Figure 6, when user number increases, the av-
erage bit SNR increases. Because every sub-carrier must
be allocated exclusively, every sub-carrier needs to carry
higher rate in average when user number increases, thus
raising the required average bit SNR. In Figure 7, when
channel number increases, the average bit SNR decreases.
Since the rate that each sub-carrier needs to provide re-
duces as the sub-carrier number increases, it can be ex-
pected that the average bit SNR decreases. Among these
figures, there is one thing in common: the solutions gener-
ated by 2-interchange algorithm has close to optimal qual-
ity. Although the performance of 2-interchange is promis-
ing in our simulations, a natural question we would like to
Figure 9. Histogram of (Difference of objec-
ask is: how sensitive the performance degradation is when
tive value between 1-interchange and op-
the neighborhood definition becomes different, i.e. perfor-
tima)/(Optimal objective). Parameters: m =
mance variation vs. different values of k? In order to an-
10, n = 3.
swer this question, we plot the average per iteration com-
puting time of 1−, 2−, 3−-interchange and their average bit
SNR in Figure 8. For comparison purpose, we also plot the
optimal average bit SNR in the same figure.

The circles from left to right represent 1−, 2−,

3−interchange, and optimal solution, respectively. As can
be observed from Figure 8, the highest gain is between
1− and 2−interchange solution, and the average difference
is 0.48 dB. Although 3-interchange is still better than 2-
interchange in average, the difference is merely 0.01 dB,
and both their solutions are within 0.02 dB from the opti-
mal solutions in average. However, the computing time for
various k value are significantly different. While all 3 k-
Figure 10. Histogram of (Difference of ob- interchange algorithms terminate within 5.1 seconds in av-
jective value between 2-interchange and op- erage for one iteration, the optimal solution takes 65.7 sec-
tima)/(Optimal objective). Parameters: m = onds. Even for the case of 5 users and 10 sub-carriers, all
10, n = 3. k-interchange can finish within 28 seconds in average, but
the optimal solution takes around 6,250 seconds. To further
understand the solution quality for each k value, we plot
the histogram of power difference from optimal solutions in
Figure 9, 10, and 11.

As we can see from Figure 9, although over 90% of in-

stances using 1-interchange are within 10% difference from
the optima, this gap can go up to around 70% in the worst
case scenario. On the other hand, in Figure 10, the worst
case of using 2-interchange algorithm is still within 7% gap
from optima, and over 95% of instances, this gap is within
1%. In addition, as depicted in Figure 11, the gap between
3-interchange solutions and optima is no more than 0.03%.

Figure 11. Histogram of (Difference of ob- In sum, although using a large neighborhood definition,
jective value between 3-interchange and op- i.e. value of k increases, can give us better average so-
tima)/(Optimal objective). Parameters: m = lution quality, but the marginal improvement diminishes
10, n = 3. rapidly. On the contrary, the computing time for different
k increases in the order of sub-carrier number.
5.4 When k-interchange Fails for sub-carrier allocation, especially when power minimiza-
tion is concerned. This points to the direction of random-
Although the solution quality of k-interchange looks ized algorithms as an alternative promising approach, which
promising in our simulations, we would like to demonstrate we hope to address in future work.
an example when the k-interchange algorithm may perform Although the sub-carrier allocation problems with power
arbitrarily bad. related objective have been proved in-approximable, the
Consider the following 3-users (user A, B, and C), proposed algorithm, k−interchange, performs close to op-
4-channels (channel I, II, III, and IV) situations for 2- timal in all our simulations. In addition, we also identify
interchange algorithm. For convenience, we use γi,j to rep- the worst case scenario, such that using k−interchange may
resent the channel gain for user i with respect to sub-carrier lead to arbitrarily bad solution quality.
j. As an extension, we plan to do extensive numerical com-
parison between our algorithm and other existing efforts by
• γA,I = 10−3 , γA,III = 1, and γA,II = γA,IV = ∞. simulations. It is also of interest to investigate the effect of
an adaptive threshold value, and strategies to reduce running
• γB,II = 10−3 , γB,I = 1, and γB,III = γB,IV = ∞. time of k−interchange algorithm.

• γC,III = 10−3 , γC,II = 1, and γC,I = γC,IV = ∞. 7. Acknowledgment

• The rate requests of user A, B, and C are all 1.
The work described here is supported in part by
• power = 1
× (2 rate
− 1) NSF through grants CNS-0347621, CNS-0627028, CCF-
γ
0430061, CNS-0325875, NASA through an AIST grant.
One possible output of 2-interchange algorithm can be Any opinions, findings, and conclusions or recommenda-
{dA,I = 1, dB,II = 1, dC,III = 1, dC,IV = 1}. How- tions expressed in this material are those of the authors and
ever, the optimal solution for this instance is {dA,III = do not necessarily reflect the views of the NSF, NASA, or
1, dB,I = 1, dC,II = 1, dC,IV = 1}. Because every eligi- USC Viterbi School of Engineering.
ble 2-interchange movement increases the total power con-
sumption to infinity, thus it is impossible to transform the References
solution of 2-interchange to the optimal one.
However, if we are allowed to reallocate 3 sub-carriers [1] T. Alen, A. Madhukumar, and F. Chin. Capacity enhance-
at once, i.e. using 3−interchange algorithm instead, then ment of a multi-user ofdm system using dynamic frequency
we can greatly reduce the total power consumption (from allocation. IEEE, 2003.
3000 to 3), as well as maximal individual power consump- [2] T. Cover and J. Thomas. Elements of information theory.
tion (from 1000 to 1). In addition, this gap can be arbitrarily 1991.
bad as we decrease the value of γA,I , γB,II , γC,III . There- [3] A. Czylwik. Adaptive ofdm for wideband eadio channels.
fore, 2-interchange does not have a bound. Similarly, we IEEE Globecom’96, London, UK, November 1996.
can construct a worst case example for any k−interchange [4] A. Goldsmith. Wireless Communications. Cambridge Uni-
versity Press, 2005.
algorithm, that makes the solution quality arbitrarily bad.
[5] IEEE. 802.16: Worldwid interoperability for microwave ac-
In sum, when channel gains have very high variability, cess (wimax). December 2001.
which prevents k-interchange from making small moves, it [6] IEEE. 802.11g: Lan/man standards committee. June 2003.
is possible that the solution quality of the proposed algo- [7] I. Kim, H. Lee, B. Kim, and Y. Lee. On the use of linear
rithm is bad. programming for dynamic subchannel and bit allocation in
multiuser ofdm. IEEE, 2001.
[8] D. Kivanc, G. Li, and H. Liu. Computationally efficient
6. Conclusion bandwidth allocation and power control for ofdma. IEEE,
2003.
In this paper, we study a multi-user/multi-subcarrier al- [9] J. Kleinberg and E. Tardos. Algorithm Design. Addison-
location problem, which can be applied to OFDM systems. Wesley, 2006.
[10] M.Bohge, J. Gross, and A. Wolisz. A new optimization
We formally prove that the sub-carrier resource allocation
model for dynamic power and sub-carrier allocations in
problem is NP-hard for both power minimization as well as packet-centric ofdma cells. Proc. Of 11th International
rate maximization in both uplink and downlink scenarios. OFDM-Workshop, August 2006.
In addition, we also demonstrate a set of in-approximability [11] W. Rhee and J. Cioffi. Increase in capacity of multiuser ofdm
results which indicate that deterministic polynomial time al- system using dynamic subsubcarrier allocation. Proceedings
gorithms cannot hope to always provide good performance of VTC, 2000.
[12] H. Rohling and R. Grunheid. Performance comparison of
different multiple access schemes for the downlink of an
ofdm communication system. Proc. IEEE VTC’97, Phoenix,
AZ.
[13] H. Rohling and R. Grunheid. Performance of an odfm-tdma
mobile communication system. Proc. IEEE VTC’96, At-
lanta, GA, 1996.
[14] Z. Shen, J. Andrews, and B. Evans. Adaptive resource allo-
cation in multiuser ofdm systems with proportional rate con-
straints. IEEE Transactions on Wireless Communications, 4,
November 2005.
[15] V. Vazirani. Approximation algorithms. 2003.
[16] M. Wahlqvist, H. Olofsson, M. Ericson, C. Ostberg, and
R. Larsson. Capacity comparison of an ofdm based multiple
access system using different dynamic resouce allocation.
IEEE, 1997.
[17] C. Wong and R. Cheng. Multiuser ofdm with adaptive sub-
carrier, bit, power allocation. IEEE JSAC, 17(10), October
1999.