« March 2018 »
Home Research Resource Allocation in Wireless Communication

Resource Allocation in Wireless Communication


In wireless communication systems, the need to simultaneously and reliably provide multiple users with high-rate 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 time-varying frequency-selective 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 frequency-division multiple access (OFDMA) systems. With orthogonal frequency-division multiplexing (OFDM), the frequency band is split into multiple independent resource blocks that can be modeled as non-interfering 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 per-subcarrier basis, maximizing frequency diversity gain. Fig. 1 shows exemplary channel gains of two users on 128 subcarriers.

Channel gains
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 so-called multiple-choice knapsack problems. Like in the classical knapsack problem, the aim of the multiple-choice 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 multiple-choice knapsack.

Multiple-choice knapsack
Figure 2: A model for a multiple-choice knapsack. Exactly one item from each subset has to be chosen.

In the OFDMA resource allocation problem, the user-modulation pairs are the knapsack objects, and the per-subcarrier assignment corresponds to the multiple-choice constraint. Each user-modulation pair has a weight (power) and an associated profit value (data rate). These power-rate 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.

Rate functions
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 multiple-choice 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.