Ferkans — Interactive Telecom Tutor

Optimal Assignment in the Frequency Domain

Sections 20.1--20.2 considered time-domain scheduling: one user is served per time slot. OFDMA (Orthogonal Frequency-Division Multiple Access), the air interface of LTE and 5G NR, adds a second dimension: the base station can assign different subcarriers to different users within the same time slot. Since each user's channel varies across frequency (due to frequency-selective fading from Chapter 14), there is rich structure to exploit. The key problem becomes a combinatorial assignment: which user should get which subcarriers, and how should power be distributed? This section formalises and solves this joint subcarrier-and-power allocation problem.

Definition:
Subcarrier and Power Allocation Problem

An OFDMA downlink has $N$ subcarriers and $K$ users. Let $H_{k,n}$ denote the channel gain of user $k$ on subcarrier $n$ and define the subcarrier SNR:

$\gamma_{k,n} = \frac{|H_{k,n}|^2}{\sigma^2}$

A subcarrier assignment $\pi : \{1,\ldots,N\} \to \{1,\ldots,K\}$ maps each subcarrier to exactly one user (exclusive assignment). A power allocation $\{p_n\}_{n=1}^{N}$ distributes the total power budget $P$ across subcarriers.

The sum-rate maximisation problem is:

$\max_{\pi,\,\{p_n\}} \;\; \sum_{n=1}^{N} \log_2\!\left(1 + p_n\,\gamma_{\pi(n),n}\right)$

$\text{subject to} \quad \sum_{n=1}^{N} p_n \leq P, \quad p_n \geq 0 \;\;\forall\, n$

This is a mixed combinatorial-continuous optimisation: the assignment $\pi$ is discrete and the power allocation is continuous.

In practice, LTE assigns resources in blocks of 12 contiguous subcarriers (resource blocks, RBs) rather than individual subcarriers, reducing the problem dimension but also the granularity of frequency-domain diversity. 5G NR supports both contiguous and non-contiguous RB allocation.

Theorem: Near-Optimality of Greedy Subcarrier Allocation

Consider the sum-rate maximisation problem for OFDMA. The following two-step procedure achieves the global optimum:

Step 1 (Assignment): Assign each subcarrier to the user with the highest channel gain on that subcarrier:

$\pi^{\star}(n) = \arg\max_{k} \; \gamma_{k,n} \quad \forall\, n = 1, \ldots, N$

Step 2 (Power): Given $\pi^{\star}$ , apply water-filling across the $N$ assigned subcarriers:

$p_n^{\star} = \left(\mu - \frac{1}{\gamma_{\pi^{\star}(n),n}}\right)^{+}$

where $\mu$ is chosen so that $\sum_n p_n^{\star} = P$ .

When the sum-rate objective is used without per-user rate constraints, this greedy-then-water-fill solution is globally optimal. With per-user minimum rate constraints, the problem becomes NP-hard in general, but the greedy assignment remains a practical near-optimal heuristic.

Since sum rate is the objective and subcarriers are orthogonal (no inter-carrier interference), the assignment that maximises the effective channel gain on each subcarrier also maximises the rate after water-filling. Each subcarrier's contribution to the sum rate is a concave function of its power, and the pointwise maximum of channel gains is achieved by the greedy rule. The separability of subcarriers is key — without it (e.g., with inter-cell interference), the problem does not decompose.

Proof

Decomposition by subcarrier

Since subcarriers are orthogonal, the sum rate decomposes:

$R_{\text{sum}} = \sum_{n=1}^{N} \log_2(1 + p_n \gamma_{\pi(n),n})$

For any fixed power allocation $\{p_n\}$ , the rate is maximised by choosing $\pi(n) = \arg\max_k \gamma_{k,n}$ for each $n$ , because $\log_2(1 + p_n x)$ is increasing in $x$ .

Optimal power allocation

With $\pi^{\star}$ fixed, the problem becomes a standard water-filling problem over $N$ parallel channels with gains $\gamma_{\pi^{\star}(n),n}$ :

$\max_{\{p_n \geq 0\}} \sum_{n=1}^{N} \log_2(1 + p_n \gamma_{\pi^{\star}(n),n}) \quad \text{s.t.} \quad \sum_n p_n \leq P$

The KKT conditions yield the water-filling solution $p_n^{\star} = (\mu - 1/\gamma_{\pi^{\star}(n),n})^+$ .

Joint optimality

We have shown that the optimal assignment does not depend on the power allocation (it is always the greedy rule), and the optimal power given the assignment is water-filling. Therefore the two-step procedure achieves the global optimum. $\blacksquare$

,

OFDMA Subcarrier Allocation

Visualise the OFDMA resource allocation for $K$ users across $N$ subcarriers. The plot shows each user's channel gain $|H_{k,n}|^2$ per subcarrier, the optimal subcarrier assignment (colour-coded by user), and the water-filling power allocation. Observe how users are assigned subcarriers where they have the best relative channel. Increasing the SNR reduces the number of inactive (zero-power) subcarriers; increasing $N$ provides finer frequency granularity.

Parameters

K

(number of users)4

N

(number of subcarriers)64

SNR (dB)15

Greedy OFDMA Subcarrier Allocation with Water-Filling

Complexity:

O(KN)

for the assignment step (scanning all users on each subcarrier) plus

O(N \log N)

for sorting in the water-filling step. Total:

O(KN + N\log N)

.

Input: Channel gains

\{\gamma_{k,n}\}_{k=1,\ldots,K}^{n=1,\ldots,N}

,

total power

P

Output: Assignment

\pi^{\star}

, power allocation

\{p_n^{\star}\}

// Step 1: Greedy subcarrier assignment

1. for

n = 1, \ldots, N

do

2.

\quad \pi^{\star}(n) \leftarrow \arg\max_{k \in \{1,\ldots,K\}} \gamma_{k,n}

3. end for

// Step 2: Water-filling power allocation

4. Collect effective gains:

g_n \leftarrow \gamma_{\pi^{\star}(n),n}

for

n = 1, \ldots, N

5. Sort subcarriers by

g_n

in decreasing order

6. Set water level

\mu

by solving:

7.

\quad \sum_{n=1}^{N} \left(\mu - 1/g_n\right)^+ = P

8. for

n = 1, \ldots, N

do

9.

\quad p_n^{\star} \leftarrow \max(\mu - 1/g_n,\; 0)

10. end for

11. return

\pi^{\star}

,

\{p_n^{\star}\}

When per-user minimum rate constraints are imposed, the greedy assignment may violate them. In that case, a modified algorithm first reserves subcarriers for rate-constrained users (e.g., via the Hungarian method or iterative reallocation) and then applies greedy-plus-water-filling to the remaining subcarriers.

Example: Two-User OFDMA Allocation

Two users share $N = 4$ subcarriers with total power $P = 4$ (linear units) and noise variance $\sigma^2 = 1$ . The channel gains $|H_{k,n}|^2$ are:

Subcarrier	User 1	User 2
1	4.0	1.0
2	0.5	3.0
3	2.0	2.0
4	1.0	5.0

(a) Determine the greedy subcarrier assignment. (b) Compute the water-filling power allocation. (c) Compute the sum rate. (d) Compare with equal-power allocation across all subcarriers.

Solution

Greedy assignment

(a) Assign each subcarrier to the user with the higher gain:

Subcarrier 1: User 1 (4.0 > 1.0)
Subcarrier 2: User 2 (3.0 > 0.5)
Subcarrier 3: Either (tie at 2.0; assign to User 1)
Subcarrier 4: User 2 (5.0 > 1.0)

Effective gains: $g_1 = 4, g_2 = 3, g_3 = 2, g_4 = 5$ .

Water-filling

(b) With $\gamma_{k,n} = |H_{k,n}|^2/\sigma^2 = |H_{k,n}|^2$ :

Sort by effective gain: $g_4 = 5, g_1 = 4, g_2 = 3, g_3 = 2$ .

Water level: $\sum_n (\mu - 1/g_n) = P = 4$ :

$4\mu - (1/5 + 1/4 + 1/3 + 1/2) = 4$

$4\mu - 1.283 = 4 \implies \mu = 1.321$

$p_1 = 1.321 - 0.250 = 1.071$ $p_2 = 1.321 - 0.333 = 0.988$ $p_3 = 1.321 - 0.500 = 0.821$ $p_4 = 1.321 - 0.200 = 1.121$

All subcarriers are active ( $p_n > 0$ ).

Sum rate

(c) $R_1 = \log_2(1 + 1.071 \times 4) = \log_2(5.283) = 2.40$ $R_2 = \log_2(1 + 0.988 \times 3) = \log_2(3.963) = 1.99$ $R_3 = \log_2(1 + 0.821 \times 2) = \log_2(2.641) = 1.40$ $R_4 = \log_2(1 + 1.121 \times 5) = \log_2(6.603) = 2.72$

Sum rate $= 2.40 + 1.99 + 1.40 + 2.72 = 8.51$ bits/s/Hz.

Equal-power comparison

(d) With $p_n = P/N = 1$ for all $n$ and the same assignment:

$R_{\text{equal}} = \log_2(5) + \log_2(4) + \log_2(3) + \log_2(6) = 2.32 + 2.00 + 1.58 + 2.58 = 8.49$ bits/s/Hz.

The water-filling gain is only 0.02 bits/s/Hz (0.3%) here because all effective gains are similar. The gain from water-filling is largest when channels are highly disparate (some subcarriers much weaker than others). $\blacksquare$

Quick Check

In OFDMA sum-rate maximisation without per-user rate constraints, why is the greedy subcarrier assignment (give each subcarrier to the user with the best channel on it) globally optimal?

Because the subcarriers are orthogonal and each contributes independently to the sum rate

Because the Hungarian algorithm always finds the greedy solution

Because water-filling makes any assignment optimal

Because all users have the same average channel gain

Correction:

Because the subcarriers are orthogonal and each contributes independently to the sum rate

Orthogonality means there is no inter-subcarrier interference. The sum rate decomposes into $N$ independent terms, and each term is maximised by choosing the user with the highest channel gain on that subcarrier. The continuous power allocation (water-filling) is then solved separately.

OFDMA

Orthogonal Frequency-Division Multiple Access: a multiple-access scheme that assigns disjoint subsets of OFDM subcarriers to different users within the same time slot. OFDMA enables frequency-domain scheduling, exploiting each user's frequency-selective fading to maximise throughput via subcarrier and power allocation.

Related: Resource Block (RB)

Resource Block (RB)

The smallest unit of radio resource allocation in LTE and 5G NR, consisting of 12 contiguous subcarriers over one slot (0.5 ms in LTE, variable in NR). The scheduler assigns integer numbers of RBs to each user, with channel quality assumed approximately constant within one RB.

Related: OFDMA

OFDMA Resource Allocation