Ferkans — Interactive Telecom Tutor

How Fast Can Wireless Networks Scale?

As the number of nodes $n$ in a wireless network grows, what is the maximum per-node throughput $T(n)$ achievable? This question — the scaling law of wireless networks — was answered in a landmark paper by Gupta and Kumar (2000), who showed that with multi-hop routing over random node placements, the per-node throughput scales as $\Theta(1/\sqrt{n \log n})$ , vanishing to zero as $n \to \infty$ . This pessimistic result means that each node's share of network capacity shrinks as the network grows. However, Ozgur, Leveque, and Tse (2007) showed that hierarchical MIMO cooperation can achieve $\Theta(1)$ per-node throughput — a constant independent of $n$ — fundamentally changing the picture. Understanding these scaling laws is essential for designing large-scale wireless networks and for assessing the fundamental limits of technologies like mesh networks, sensor networks, and device-to-device communication.

Definition:
Transport Capacity and Per-Node Throughput

Consider $n$ nodes placed in a unit-area region, each wishing to communicate with a randomly chosen destination. The per-node throughput $T(n)$ (bits/s) is the common rate achievable by all source-destination pairs simultaneously.

The transport capacity $C_T$ (bit-metres/s) measures the sum of rate $\times$ distance products across all active links:

$C_T = \sum_i R_i \cdot d_i$

where $R_i$ is the rate and $d_i$ is the distance of the $i$ -th concurrent transmission. The transport capacity captures the fact that long-distance communication consumes more spatial resources (spectrum and power) than short-distance communication.

The per-node throughput and transport capacity are related by:

$T(n) = \frac{C_T}{n \cdot \bar{d}}$

where $\bar{d}$ is the average source-destination distance (approximately $\Theta(1)$ for random placements in a unit area).

Definition:
Hierarchical MIMO Cooperation

Hierarchical MIMO cooperation (Ozgur--Leveque--Tse, 2007) is a multi-level cooperative protocol that achieves $\Theta(1)$ per-node throughput by recursively forming virtual MIMO arrays:

Level 0: Individual nodes communicate with neighbours.

Level 1: Groups of $M_1$ nearby nodes form virtual MIMO arrays, cooperating to perform distributed space-time coding. Each group communicates as a single $M_1$ -antenna transmitter to another group.

Level $k$ : Groups of $M_k = M_1^k$ nodes cooperate, forming $M_k \times M_k$ virtual MIMO channels between groups.

At each level, the intra-group information exchange uses the protocol of the previous level. After $L = O(\log \log n)$ levels, the system achieves per-node throughput $\Theta(1)$ , because the MIMO multiplexing gain compensates for the overhead of distributed cooperation.

Theorem: Gupta--Kumar Scaling Law

Consider $n$ nodes placed uniformly at random in a unit-area disk, each communicating with a randomly chosen destination. Under the protocol model (a transmission succeeds if the receiver is within range $r$ and no interferer is within distance $(1+\Delta)r$ ), the per-node throughput satisfies:

$T(n) = \Theta\!\left(\frac{1}{\sqrt{n \log n}}\right)$

Specifically:

Upper bound: $T(n) = O(1/\sqrt{n \log n})$ for any scheduling and routing strategy.
Lower bound: $T(n) = \Omega(1/\sqrt{n \log n})$ is achievable by multi-hop with nearest-neighbour routing and TDMA scheduling.

Under the physical model (SINR-based decoding), the same $\Theta(1/\sqrt{n \log n})$ scaling holds with multi-hop transmission.

However, with hierarchical MIMO cooperation, the per-node throughput can be improved to:

$T(n) = \Theta(1) \quad\text{(Ozgur--Leveque--Tse, 2007)}$

i.e., a constant independent of $n$ .

The Gupta--Kumar result arises from a spatial bottleneck: with $n$ source-destination pairs, each pair's traffic must traverse approximately $\sqrt{n}$ hops (the typical number of hops in a random network). Each node acts as a relay for $\Theta(\sqrt{n})$ other flows, but can only serve one at a time. The total network capacity is $\Theta(n)$ (from spatial reuse), but each node relays for $\Theta(\sqrt{n})$ flows, leaving $\Theta(1/\sqrt{n})$ per source. The extra $\log n$ factor comes from the communication range needed for connectivity.

Hierarchical MIMO breaks this bottleneck by allowing simultaneous transmission of multiple streams through distributed spatial multiplexing, avoiding the relay congestion inherent in multi-hop.

Proof

Upper bound (information-theoretic argument)

Consider any horizontal strip of width $1/\sqrt{n}$ . With $n$ nodes in the unit area, approximately $\sqrt{n}$ nodes lie in this strip. Any source-destination pair that crosses this strip must transmit information through it.

By random placement, $\Theta(n)$ source-destination pairs cross any such strip. The total capacity of the strip is limited by the bandwidth $W$ and the number of simultaneous transmissions (at most $\Theta(\sqrt{n/\log n})$ by spatial reuse with connectivity radius $r = \Theta(\sqrt{\log n/n})$ ).

Therefore: total throughput crossing the strip $= O(\sqrt{n/\log n})$ . Per-pair throughput: $T(n) = O(\sqrt{n/\log n}/n) = O(1/\sqrt{n \log n})$ .

Lower bound (multi-hop achievability)

Choose communication range $r = c\sqrt{\log n / n}$ for a constant $c$ large enough to ensure connectivity (by the Penrose threshold). Divide the area into cells of side $r$ . Each cell contains $\Theta(\log n)$ nodes. Within each cell, TDMA allows one transmission per time slot.

Multi-hop routes traverse $\Theta(1/r) = \Theta(\sqrt{n/\log n})$ hops. With $\Theta(n/\log n)$ cells doing spatial reuse and $\Theta(\sqrt{n \log n})$ hops per route:

$T(n) = \Omega\!\left(\frac{1}{\sqrt{n\log n}}\right)$

Hierarchical MIMO improvement

The hierarchical scheme of Ozgur et al. creates virtual $M \times M$ MIMO links with $M = n^{1-\epsilon}$ . The MIMO multiplexing gain provides $\Theta(M)$ streams, while the cooperation overhead is $o(M)$ at each level. The net per-node throughput is $\Theta(M/M) = \Theta(1)$ .

The key requirement is that the path-loss exponent $\alpha > 2$ , ensuring that inter-cluster interference is manageable. $\blacksquare$

,

Network Capacity Scaling: Gupta-Kumar vs Hierarchical MIMO

Watch a wireless network grow from 10 to 100 nodes. The Gupta-Kumar throughput vanishes as

1/\sqrt{n \log n}

, while hierarchical MIMO cooperation maintains

\Theta(1)

per-node throughput.

The Gupta-Kumar result shows that multi-hop routing in large random networks is fundamentally bottlenecked by relay congestion. Hierarchical MIMO breaks this barrier through cooperative spatial multiplexing.

Network Throughput Scaling

Visualise how the per-node throughput scales with the number of nodes $n$ under different strategies: multi-hop (Gupta--Kumar $\Theta(1/\sqrt{n \log n})$ ), direct transmission ( $\Theta(1/n)$ ), and hierarchical MIMO cooperation ( $\Theta(1)$ ). Adjust the maximum network size to see the asymptotic behaviour. The plot clearly shows that multi-hop provides a substantial improvement over direct transmission but still vanishes, while hierarchical MIMO maintains constant per-node throughput.

Parameters

n_{\max}

(maximum number of nodes)500

Example: Comparing Scaling Laws

A wireless mesh network has $n = 100$ nodes in a 1 km $^2$ area, each with 1 MHz bandwidth.

(a) Under Gupta--Kumar scaling, estimate the per-node throughput. (b) Under hierarchical MIMO with $T(n) = c$ bits/s/Hz per node, estimate the per-node throughput (assume $c = 0.5$ bits/s/Hz). (c) If the network grows to $n = 10{,}000$ , recompute both. (d) At what network size does hierarchical MIMO provide a 10 $\times$ throughput advantage over multi-hop?

Solution

Gupta-Kumar at $n = 100$

(a) $T(100) = \frac{c_0}{\sqrt{100 \times \ln 100}} = \frac{c_0}{\sqrt{460.5}} = \frac{c_0}{21.46}$ .

With $c_0 \approx 1$ (normalised): $T \approx 0.047$ bits/s/Hz. Throughput: $0.047 \times 1 = 47$ kbps per node.

Hierarchical MIMO at $n = 100$

(b) $T = 0.5$ bits/s/Hz $\Rightarrow$ 500 kbps per node.

10.6 $\times$ higher than Gupta--Kumar.

Scaling to $n = 10{,}000$

(c) Gupta--Kumar: $T(10^4) = c_0/\sqrt{10^4 \times 9.21} = c_0/303.5 \approx 0.0033$ bits/s/Hz (3.3 kbps).

Hierarchical: still 500 kbps.

Ratio: $500/3.3 = 152\times$ .

10$\times$ advantage threshold

(d) Need $0.5 / (c_0/\sqrt{n \ln n}) = 10$ : $\sqrt{n \ln n} = 0.5/(10 \times c_0) \cdot (1/c_0)$ .

With $c_0 = 1$ : $\sqrt{n \ln n} = 20$ , $n \ln n = 400$ . Solving: $n \approx 65$ .

Hierarchical MIMO is 10 $\times$ better once $n > 65$ . $\blacksquare$

,

Quick Check

What is the fundamental bottleneck that causes the per-node throughput to vanish as $\Theta(1/\sqrt{n \log n})$ in the Gupta--Kumar model?

Insufficient total bandwidth

Each node must relay traffic for $\Theta(\sqrt{n})$ other flows, creating a per-node relay bottleneck

Interference from all $n$ nodes prevents any communication

The transmit power decreases as $1/n$

Correction:

Each node must relay traffic for

\Theta(\sqrt{n})

other flows, creating a per-node relay bottleneck

With random source-destination pairs separated by $\Theta(1)$ distance and hop length $\Theta(1/\sqrt{n})$ , each pair requires $\Theta(\sqrt{n})$ hops. Since each intermediate node relays for many flows, the per-node capacity is shared among $\Theta(\sqrt{n})$ relay duties, yielding $\Theta(1/\sqrt{n})$ per source (with a $\log n$ correction for connectivity).

Gupta--Kumar Scaling Law

The result that in a wireless network of $n$ randomly placed nodes with multi-hop routing, the per-node throughput scales as $\Theta(1/\sqrt{n \log n})$ , vanishing as $n \to \infty$ . This fundamental limit arises from the relay congestion at intermediate nodes and the connectivity requirement.

Transport Capacity

The sum of rate-distance products $C_T = \sum_i R_i d_i$ across all simultaneous transmissions in a wireless network. Transport capacity measures the network's ability to move information over distance and is bounded by $\Theta(\sqrt{n})$ in a network of $n$ nodes.

Related: Gupta--Kumar Scaling Law

Hierarchical MIMO Cooperation

A multi-level cooperative scheme where nodes recursively form virtual MIMO arrays of increasing size, enabling distributed spatial multiplexing. Proposed by Ozgur, Leveque, and Tse (2007), it achieves $\Theta(1)$ per-node throughput, breaking the Gupta--Kumar bottleneck.

Why This Matters: Beyond Gupta-Kumar via Coded Caching and Content Placement

The Gupta-Kumar scaling law assumes every source-destination pair has independent traffic. When traffic has shared content (e.g., video streaming), coded caching (Chapter 20) can fundamentally alter the scaling:

Without caching: Per-node throughput $\Theta(1/\sqrt{n \log n})$ (Gupta-Kumar).
With local caching and D2D: Ji, Caire, and Molisch (2016) showed that coded caching combined with device-to-device communication achieves per-node throughput $\Theta(M/N)$ where $M$ is the cache size and $N$ is the library size — independent of $n$ if $M/N$ is constant.

This result connects relay/multi-hop theory to content delivery and is developed in depth in Book CC (Coded Caching). The hierarchical MIMO scheme of Ozgur-Leveque-Tse (2007) achieves $\Theta(1)$ for general traffic but requires global cooperation; coded caching achieves similar scaling with only local cooperation and finite cache memory.

Scaling Laws