Resource Allocation in Wireless Communication
Introduction
In wireless communication systems, the need to simultaneously and reliably provide multiple users with highrate communication links leads to challenging optimization problems. Questions of cell and resource block assignment, interference, and power consumption at base station and mobile devices have to be answered in the face of timevarying frequencyselective channels. Furthermore, the heterogeneity of modern mobile services means that delay and data rate requirements vary greatly between applications and users. These questions and requirements can be formulated as resource allocation problems.
This research is concerned with the modeling, analysis and solving of resource allocation problems. As the combinatorial nature of these problems is computationally prohibitive, the development of approximation techniques and algorithms plays an important practical role. By combining results from integer, convex and nonconvex optimization theory, performance estimates and bounds for these approaches can be derived.
OFDMA Resource Allocation
A prime example for a wireless resource allocation problem occurs in orthogonal frequencydivision multiple access (OFDMA) systems. With orthogonal frequencydivision multiplexing (OFDM), the frequency band is split into multiple independent resource blocks that can be modeled as noninterfering flat narrowband channels. In OFDMA systems, multiple users are served simultaneously by assigning these blocks or subcarriers to users in a way that each subcarrier is occupied by at most one user. Adaptive coding and modulation techniques allow users to adapt their data transmission scheme to the wireless channel conditions on a persubcarrier basis, maximizing frequency diversity gain. Fig. 1 shows exemplary channel gains of two users on 128 subcarriers.
Figure 1: Channel gains of two users on orthogonal subcarriers. 
The resource allocation problem in OFDMA consists of multiple interdependent problems:
 Subcarrier assignment
 Choice of modulation levels
 Global and/or local power budgets
 Rate and fairness requirements
We have shown that OFDMA resource allocation problems can be formulated as socalled multiplechoice knapsack problems. Like in the classical knapsack problem, the aim of the multiplechoice knapsack problem is to maximize the value of the objects in a knapsack with one or more weight constraints. However, objects are divided into subsets and the problem has to be solved by choosing exactly one object from each subset. Fig. 2 shows a schematic model of a multiplechoice knapsack.
Figure 2: A model for a multiplechoice knapsack. Exactly one item from each subset has to be chosen.

In the OFDMA resource allocation problem, the usermodulation pairs are the knapsack objects, and the persubcarrier assignment corresponds to the multiplechoice constraint. Each usermodulation pair has a weight (power) and an associated profit value (data rate). These powerrate pairs are given by rate functions that depend on channel gains and system specifics. Fig. 3 shows a discrete and a continuous rate function for a single subcarrier.
Figure 3: Discrete and continuous rate utility functions. In the discrete case, there is a finite number of modulation levels m available. 
While knapsack problems are computationally prohibitive, the multiplechoice knapsack formulation allows us to apply powerful tools from integer and linear optimization. When modeling continuous rate functions, more general convex optimization techniques can be applied. Fig. 4 exemplifies how these methods help to find approximate solutions for subcarrier assignment and choice of modulation level.
Figure 4: Linear and convex optimization methods can be applied to obtain a set of parameters (λ, α , β) by which to assign subcarriers and modulation levels. 