Ferkans — Interactive Telecom Tutor

Exploiting Multi-User Diversity

With $K$ users experiencing independent fading, the probability that at least one user has a strong channel is high even when individual channels are poor on average. Multi-user diversity exploits this by scheduling transmission to the user(s) with the best instantaneous channels. When the base station has $N_t$ antennas and serves $K \gg N_t$ users, the challenge becomes selecting a subset of $N_t$ (or fewer) users whose channels are both strong and mutually near-orthogonal. This section develops the theory of multi-user diversity and the semi-orthogonal user selection (SUS) algorithm that achieves near-optimal performance with polynomial complexity.

Definition:
Multi-User Diversity Gain

Multi-user diversity arises when a base station can select among $K$ users for transmission. In the simplest single-antenna case, the BS transmits to the user with the strongest channel:

$k^* = \arg\max_{k \in \{1, \ldots, K\}} |h_k|^2$

The throughput is $R = \log_2(1 + \text{SNR} \cdot \max_k |h_k|^2)$ .

For i.i.d. Rayleigh fading with $|h_k|^2 \sim \text{Exp}(1)$ , the expected maximum channel gain scales as:

$\mathbb{E}[\max_k |h_k|^2] \approx \ln K + \gamma_{\text{EM}}$

where $\gamma_{\text{EM}} \approx 0.5772$ is the Euler-Mascheroni constant. This yields a multi-user diversity gain of:

$\Delta R \approx \log_2(\ln K)$

additional bits/s/Hz compared to serving a random user.

Multi-user diversity is a form of selection diversity in the user domain. Unlike antenna diversity (which combats fading), multi-user diversity exploits fading: independent fading across users creates peaks that can be opportunistically utilised.

Definition:
Semi-Orthogonal User Selection (SUS)

Semi-orthogonal user selection (SUS) selects a subset of users whose channels are both strong and nearly orthogonal, enabling efficient ZF precoding. The algorithm is parameterised by an orthogonality threshold $\alpha \in (0, 1]$ .

SUS selects users greedily: at each step, it picks the user with the strongest (projected) channel that is sufficiently orthogonal to all previously selected users. The projection ensures that the new user's channel component in the subspace of already-selected users is small, limiting the ZF power penalty.

After selecting the user subset $\mathcal{S}$ with $|\mathcal{S}| \leq N_t$ , ZF precoding is applied to the reduced channel matrix $\mathbf{H}_\mathcal{S}$ .

Semi-Orthogonal User Selection (SUS) Algorithm

Complexity:

O(K N_t^2)

— dominated by the Gram-Schmidt projections. This is linear in the number of candidate users

K

and polynomial in

N_t

, making SUS practical for large user pools.

Input: Channel vectors

\{\mathbf{h}_k\}_{k=1}^K

, number of BS antennas

N_t

, threshold

\alpha \in (0,1]

Initialise:

\mathcal{S} = \emptyset

,

\mathcal{T} = \{1, \ldots, K\}

,

\mathbf{g}_k = \mathbf{h}_k\;\forall k

For

i = 1, 2, \ldots, N_t

:

\quad

1. Select user with strongest projected channel:

\quad\quad

k_i = \arg\max_{k \in \mathcal{T}} \|\mathbf{g}_k\|^2

\quad

2. If

\|\mathbf{g}_{k_i}\|^2 = 0

: break (no more orthogonal users)

\quad

3. Update selected set:

\mathcal{S} \leftarrow \mathcal{S} \cup \{k_i\}

\quad

4. Compute orthogonal direction:

\mathbf{e}_i = \mathbf{g}_{k_i}/\|\mathbf{g}_{k_i}\|

\quad

5. Project out selected direction and remove near-parallel users:

\quad\quad

For each

k \in \mathcal{T} \setminus \{k_i\}

:

\quad\quad\quad

\mathbf{g}_k \leftarrow \mathbf{g}_k - (\mathbf{e}_i^H\mathbf{g}_k)\mathbf{e}_i

(Gram-Schmidt)

\quad\quad\quad

If

\|\mathbf{g}_k\|^2 < \alpha^2 \|\mathbf{h}_k\|^2

:

\mathcal{T} \leftarrow \mathcal{T} \setminus \{k\}

End For

Output: Selected user set

\mathcal{S}

, apply ZF precoding to

\mathbf{H}_\mathcal{S} = [\mathbf{h}_{k}]_{k \in \mathcal{S}}^H

The threshold $\alpha$ controls the trade-off between channel strength and orthogonality: $\alpha \to 0$ accepts any user (pure strength-based selection), while $\alpha \to 1$ requires near-perfect orthogonality. The optimal $\alpha$ depends on $K$ , $N_t$ , and SNR; typical values are $\alpha \in [0.1, 0.5]$ .

User Scheduling Performance

Compare the sum rate of SUS scheduling with random user selection and exhaustive search as the number of candidate users $K$ grows. Observe the multi-user diversity gain: the sum rate increases logarithmically with $K$ even with fixed BS antennas.

Parameters

N_t

(BS antennas)4

K

(candidate users)30

SNR (dB)15

Theorem: Multi-User Diversity Scaling (log log K)

For the $K$ -user MISO broadcast channel with $N_t$ BS antennas, i.i.d. Rayleigh fading, and ZF precoding with optimal user selection:

$R_{\text{sum}} = N_t \log_2\!\left(1 + \frac{P}{N_t\sigma^2} (N_t - 1 + \ln(K/N_t) + o(1))\right)$

as $K \to \infty$ with $N_t$ fixed.

The multi-user diversity gain scales as:

$\Delta R_{\text{sum}} \approx N_t \log_2\!\left(1 + \frac{P\ln(K/N_t)}{N_t\sigma^2}\right) \approx N_t \log_2(\ln K) \quad \text{at high SNR}$

Furthermore, the SUS algorithm with threshold $\alpha = O(1/\ln K)$ achieves the same $\log_2 \ln K$ scaling as exhaustive search, with only $O(KN_t^2)$ complexity versus $O(\binom{K}{N_t})$ for exhaustive search.

As $K$ grows, the selected users' channels become stronger (each has gain $\approx \ln(K/N_t)$ ) and more orthogonal (there are more candidates to choose from). The $\ln K$ channel gain translates to a $\log_2 \ln K$ rate gain — a double-logarithmic scaling. While this grows slowly, it is essentially "free" (no extra power or bandwidth needed).

Proof

Maximum channel gain with selection

After SUS selects $N_t$ near-orthogonal users, each selected user's effective channel gain (after projection) concentrates around $\ln(K/N_t)$ . This follows from the extreme value theory of chi-squared random variables:

For $K$ users with $\|\mathbf{h}_k\|^2 \sim \chi^2_{2N_t}$ , the order statistics satisfy:

$\|\mathbf{h}_{(K)}\|^2 \approx N_t + \ln K + O(\ln\ln K)$

where $\mathbf{h}_{(K)}$ is the strongest channel.

Sum rate with selected users

With $N_t$ selected near-orthogonal users, ZF precoding achieves per-user rate:

$R_k \approx \log_2\!\left(1 + \frac{P}{N_t\sigma^2}\cdot \frac{\|\mathbf{h}_{k}\|^2}{[(\mathbf{H}_\mathcal{S}\mathbf{H}_\mathcal{S}^H)^{-1}]_{kk}}\right)$

For near-orthogonal users, $[(\mathbf{H}_\mathcal{S}\mathbf{H}_\mathcal{S}^H)^{-1}]_{kk} \approx 1/\|\mathbf{h}_k\|^2$ , so:

$R_k \approx \log_2\!\left(1 + \frac{P\|\mathbf{h}_k\|^2}{N_t\sigma^2}\right)$

Scaling law

Substituting the expected channel gain of $\approx \ln(K/N_t) + N_t$ :

$R_{\text{sum}} \approx N_t\log_2\!\left(1 + \frac{P(N_t - 1 + \ln(K/N_t))}{N_t\sigma^2}\right)$

The dominant term in the growth with $K$ is $\log_2(\ln K)$ , the double-logarithmic multi-user diversity gain.

Yoo and Goldsmith (2006) proved that SUS achieves this scaling with $O(KN_t^2)$ complexity, matching the performance of $O(\binom{K}{N_t})$ exhaustive search. $\blacksquare$

Example: SUS vs Greedy Selection

A BS with $N_t = 2$ antennas has $K = 4$ candidate users with channels (all in $\mathbb{C}^2$ ):

$\mathbf{h}_1 = \begin{bmatrix} 2 \\ 0.1 \end{bmatrix},\; \mathbf{h}_2 = \begin{bmatrix} 1.8 \\ 0.2 \end{bmatrix},\; \mathbf{h}_3 = \begin{bmatrix} 0.3 \\ 1.5 \end{bmatrix},\; \mathbf{h}_4 = \begin{bmatrix} 1 \\ 1 \end{bmatrix}$

Compare (a) greedy selection (pick 2 strongest users) with (b) SUS selection ( $\alpha = 0.5$ ) using ZF precoding, $P = 20$ , $\sigma^2 = 1$ .

Solution

Channel strengths

$\|\mathbf{h}_1\|^2 = 4.01$ , $\|\mathbf{h}_2\|^2 = 3.28$ , $\|\mathbf{h}_3\|^2 = 2.34$ , $\|\mathbf{h}_4\|^2 = 2.00$

Greedy selects users 1 and 2 (strongest channels).

Greedy ZF performance

Users 1 and 2 have nearly parallel channels: $|\mathbf{h}_1^H\mathbf{h}_2|/(\|\mathbf{h}_1\|\|\mathbf{h}_2\|) = (3.62)/(2.002 \times 1.811) \approx 0.999$

The channels are almost collinear, causing massive ZF power penalty. $[(\mathbf{H}_{12}\mathbf{H}_{12}^{H})^{-1}]_{kk}$ is very large, resulting in very low effective SNR.

$R_{\text{sum}}^{\text{greedy}} \approx 2.1\;\text{bits/s/Hz}$ (poor)

SUS selection and performance

SUS: First select user 1 (strongest). $\mathbf{e}_1 = \mathbf{h}_1/\|\mathbf{h}_1\| \approx [0.999, 0.050]^T$ .

Project remaining users: remove component along $\mathbf{e}_1$ .

$\|\mathbf{g}_2\|^2/\|\mathbf{h}_2\|^2$ : User 2's projected channel is tiny (nearly parallel to user 1); removed by threshold $\alpha = 0.5$ .

$\|\mathbf{g}_3\|^2/\|\mathbf{h}_3\|^2 \approx 0.96$ : User 3 is nearly orthogonal to user 1; kept.

$\|\mathbf{g}_4\|^2/\|\mathbf{h}_4\|^2 \approx 0.50$ : User 4 is at the threshold; marginally kept.

SUS selects user 3 as the second user.

Users 1 and 3 have well-separated channels. $R_{\text{sum}}^{\text{SUS}} \approx 7.8\;\text{bits/s/Hz}$ — a dramatic improvement over greedy selection. $\blacksquare$

Quick Check

How does the multi-user diversity sum-rate gain scale with the number of users $K$ (for fixed $N_t$ and SNR)?

Linearly: $\Theta(K)$

Logarithmically: $\Theta(\log K)$

Double-logarithmically: $\Theta(\log \log K)$

It saturates for large $K$

Correction:

Double-logarithmically:

\Theta(\log \log K)

The selected users have channel gain $\approx \ln K$ , which translates to a rate gain of $\log_2(\ln K)$ bits/s/Hz. This double-logarithmic scaling is the fundamental multi-user diversity gain.

Why This Matters: User Scheduling in LTE and 5G NR

User scheduling is integral to all modern cellular standards. LTE employs proportional fair (PF) scheduling, which balances throughput and fairness by scheduling user $k^*$ that maximises $R_k(t)/\bar{R}_k(t)$ (instantaneous rate divided by average throughput). PF scheduling captures multi-user diversity while ensuring long-term fairness. 5G NR extends this with multi-beam scheduling for massive MIMO: the gNB uses beam management procedures (SSB beams, CSI-RS) to identify the best beam per user, then co-schedules users on orthogonal beams. In both LTE and 5G, the scheduler operates every TTI (1 ms in LTE, as short as 0.125 ms in 5G NR), exploiting multi-user diversity in both time and frequency domains.

Multi-User Diversity

The gain obtained by scheduling transmission to users with favourable instantaneous channel conditions. With $K$ users experiencing independent fading, the best user's channel gain grows as $\ln K$ , providing a $\log_2 \ln K$ rate gain.

Semi-Orthogonal User Selection (SUS)

A greedy user selection algorithm that iteratively picks users with strong channels that are nearly orthogonal to previously selected users, enabling efficient ZF precoding with $O(KN_t^2)$ complexity.

Proportional Fair Scheduling

A scheduling policy that selects the user maximising the ratio of instantaneous rate to average throughput: $k^* = \arg\max_k R_k(t)/\bar{R}_k(t)$ . It balances throughput maximisation with long-term fairness across users.

User Scheduling and Multi-User Diversity