Exercises

Relay: $\frac{1}{2}\log(1+20) = \frac{1}{2}\log 21 \approx 2.18$ bits. Cooperative: $\frac{1}{2}\log(1+20) = \frac{1}{2}\log 21 \approx 2.18$ bits. DF rate: $\min\{2.18, 2.18\} = 2.18$ bits.

Relay: $\frac{1}{2}\log(1+0.19 \cdot 10/0.5) = \frac{1}{2}\log(1+3.8) = \frac{1}{2}\log 4.8 \approx 1.13$ bits. Cooperative: $\frac{1}{2}\log(1+10+10+18) = \frac{1}{2}\log 39 \approx 2.78$ bits. DF rate: $\min\{1.13, 2.78\} = 1.13$ bits.

$\rho = 0$ achieves 2.18 bits vs. $\rho = 0.9$ achieves only 1.13 bits. High correlation hurts because the relay cannot decode: the "fresh" information $(1-\rho^2)P$ drops dramatically. The optimal $\rho^*$ lies between 0 and 0.9.

In the CF rate $\frac{1}{2}\log(1 + P/N + \frac{P/N_r}{1+\Delta/N_r})$, as $\Delta \to \infty$, the relay term $\frac{P/N_r}{1+\Delta/N_r} \to 0$. The rate approaches $\frac{1}{2}\log(1 + P/N)$, the direct-link rate.

Since $\Delta < \infty$ gives a strictly positive relay contribution, the CF rate is always $\geq \frac{1}{2}\log(1+P/N)$. The relay can never hurt with CF.

For two uniformly random points in $[0,1]^2$, the expected Euclidean distance is $\mathbb{E}[d] = \frac{2+\sqrt{2}+5\ln(1+\sqrt{2})}{15} \approx 0.52$.

With $n$ nodes in a unit square, the nearest-neighbor distance is $\sim c/\sqrt{n}$. To cover distance $\sim 0.52$, we need $\sim 0.52\sqrt{n}/c = \Theta(\sqrt{n})$ hops.

Each packet requires $\Theta(\sqrt{n})$ hops, each consuming a channel use. This is the root cause of the $\Theta(1/\sqrt{n})$ throughput scaling.

For small networks ($K \leq 5$), the gap is modest (1-2 bits). For larger networks, the gap grows linearly with $K$. However, this is a worst-case bound — the actual gap is typically much smaller, especially for well-connected topologies.

Set $1 + (1-\rho^2)P/N_r = 1 + (P+P_r+2\rho\sqrt{PP_r})/N$. This gives $(1-\rho^2)P/N_r = (P+P_r+2\rho\sqrt{PP_r})/N$.

$(1-\rho^2)PN = (P+P_r+2\rho\sqrt{PP_r})N_r$. $PN - \rho^2 PN = PN_r + P_r N_r + 2\rho\sqrt{PP_r}N_r$. $\rho^2 PN + 2\rho\sqrt{PP_r}N_r + (P_r N_r + PN_r - PN) = 0$. This is a quadratic in $\rho$ with $a = PN$, $b = 2\sqrt{PP_r}N_r$, $c = N_r(P+P_r) - PN$: $$\rho^* = \frac{-b + \sqrt{b^2 - 4ac}}{2a}$$ taking the root in $[0, 1]$.

The cut-set bound's broadcast cut includes the coherent gain: $\frac{1}{2}\log(1 + (P+P_r+2\sqrt{PP_r})/N) = \frac{1}{2}\log(1 + (\sqrt{P}+\sqrt{P_r})^2/N)$. CF uses independent inputs: $\frac{1}{2}\log(1 + (P+P_r)/N)$.

$(\sqrt{P}+\sqrt{P_r})^2 = P + P_r + 2\sqrt{PP_r} \leq 2(P + P_r)$ by AM-GM. Therefore: $$\frac{1}{2}\log\frac{1+(\sqrt{P}+\sqrt{P_r})^2/N}{1+(P+P_r)/N} \leq \frac{1}{2}\log\frac{1+2(P+P_r)/N}{1+(P+P_r)/N} \leq \frac{1}{2}\log 2 = 0.5 \text{ bits}.$$

Each hop has capacity $\frac{1}{2}\log(1+100) \approx 3.33$ bits. DF rate = $\min\{3.33, 3.33, 3.33\} = 3.33$ bits.

Each of the three cuts gives $\frac{1}{2}\log(1+100) = 3.33$ bits. Cut-set bound = 3.33 bits. DF achieves the cut-set bound for the serial chain.

NNC with $K = 4$ nodes: gap $\leq (4-1)/2 = 1.5$ bits. NNC rate $\geq 3.33 - 1.5 = 1.83$ bits. NNC is suboptimal for the serial chain because it does not exploit the sequential structure.

$M$ nodes must share $M$ messages. Using nearest-neighbor communication within the group (which has diameter $\sim \sqrt{M/n}$), each message can reach all nodes in $\Theta(\sqrt{M})$ hops via flooding. The total local cooperation time is $\Theta(M \cdot \sqrt{M}) = \Theta(M^{3/2})$ channel uses.

The MIMO transmission phase takes $\Theta(n)$ channel uses (one long codeword per virtual MIMO link). The cooperation overhead is $\Theta(M^{3/2}/n)$ per node. For $M = n^{1/L}$ (the hierarchical choice), this fraction vanishes as $n \to \infty$ for fixed $L$.

DF rate: $\min\{\frac{1}{2}\log(1+|h|^2 P/N_r), \frac{1}{2}\log(1+2|g|^2 P_r/N)\}$. At symmetry: $|h|^2 P/N_r = |g|^2 P_r/N \triangleq \gamma$. DF = $\min\{\frac{1}{2}\log(1+\gamma), \frac{1}{2}\log(1+2\gamma)\} = \frac{1}{2}\log(1+\gamma)$.

CF uses the relay-destination link to carry compressed observations. At symmetry ($\gamma$ equal for both links), the CF rate with optimal quantization also evaluates to approximately $\frac{1}{2}\log(1+\gamma)$, as the compression overhead balances the side information gain.

At the symmetry point, neither strategy has an advantage — both achieve the same rate $\frac{1}{2}\log(1+\gamma)$. Away from symmetry, DF is better when the source-relay link is stronger, and CF is better when the relay-destination link dominates.

With $n$ nodes in a unit square and $\alpha = 2$, a node at the origin experiences aggregate interference $I \sim \sum_{k \neq 0} d_k^{-2}$. For uniformly distributed nodes, this sum scales as $\Theta(n)$ (since $\int_0^1 r^{-2} \cdot 2\pi r \cdot n \, dr$ diverges).

The SINR at any receiver is $\Theta(P \cdot d_{\text{hop}}^{-2} / (N + I))$. With $I = \Theta(n \cdot P)$ and $d_{\text{hop}} = \Theta(1/\sqrt{n})$: SINR $= \Theta(Pn / (N + nP)) = \Theta(1)$ (bounded). The per-link rate is $\Theta(1)$, and with $\Theta(\sqrt{n})$ hops: $T(n) = \Theta(1/\sqrt{n})$.

For $\alpha > 2$, the aggregate interference is bounded, giving SINR $= \Theta(n)$ and per-link rate $\Theta(\log n)$, leading to $T(n) = \Theta(\log n / \sqrt{n}) = \Theta(1/\sqrt{n/\log n})$ — the Gupta-Kumar result. For $\alpha = 2$, the interference is larger, reducing per-link rate to $\Theta(1)$.

$\hat{R}_k = \frac{1}{2}\log(1 + (P + N_k)/N_k) = \frac{1}{2}\log(1 + P/N_k + 1) = \frac{1}{2}\log(2 + P/N_k)$.

At high SNR ($P/N_k \gg 1$): $\hat{R}_k \approx \frac{1}{2}\log(P/N_k) = \frac{1}{2}\log \text{SNR}_{k}$. This is approximately the point-to-point capacity of the relay's received link. Quantizing at the noise level captures all the useful information (above the noise floor) and discards only the noise — an operationally optimal choice.

With optimal $\rho$: $C_{\text{CS}} \leq \frac{1}{2}\log((\sqrt{P}+\sqrt{P_r})^2/N) + o(1)$ $= \frac{1}{2}\log(P(1+\sqrt{P_r/P})^2/N) + o(1)$.

With optimal $\Delta$: $R_{\text{CF}} = \frac{1}{2}\log((P+P_r)/N) + o(1)$ $= \frac{1}{2}\log(P(1+P_r/P)/N) + o(1)$.

$C_{\text{CS}} - R_{\text{CF}} = \frac{1}{2}\log\frac{(1+\sqrt{P_r/P})^2}{1+P_r/P} = \frac{1}{2}\log\frac{(\sqrt{r}+1)^2}{r+1}$ where $r = P_r/P$. This is maximized at $r = 1$: $\frac{1}{2}\log\frac{4}{2} = \frac{1}{2}\log 2 = 0.5$ bits. The gap is exactly 0.5 bits when $P = P_r$ at high SNR.

Within a cluster of $M$ nodes, the diameter is $\sim \sqrt{M/n}$. Each node transmits its message to all cluster members. Using TDMA within the cluster, this takes $\Theta(M)$ time slots (each slot at rate $\Theta(\log(1 + n/M))$ — short-range link).

The MIMO transmission between two clusters uses $n_{\text{code}}$ channel uses at rate $\Theta(M)$ bits per channel use. To transmit $M$ messages (each of $n_{\text{msg}}$ bits), we need $n_{\text{code}} = \Theta(M \cdot n_{\text{msg}} / M) = \Theta(n_{\text{msg}})$ channel uses.

Total time per round: $\Theta(M) + \Theta(n_{\text{msg}})$. For the cooperation overhead to be negligible, we need $M \ll n_{\text{msg}}$, which is satisfied by choosing long codewords. The per-node throughput is $\Theta(n_{\text{msg}} / (M + n_{\text{msg}})) = \Theta(1)$.

The relay receives $Y_r = h_1 X_1 + h_2 X_2 + Z_r$ — a superposition of both sources. Its compressed observation $\hat{Y}_r$ necessarily contains information about both messages. The relay-destination link is shared: $R$ transmits one signal $X_r$ that must help both destinations. This coupling makes the problem fundamentally different from two parallel relay channels.

With NNC, the relay compresses $Y_r$ (containing both messages) and both destinations jointly decode using $(Y_{d_k}, \hat{Y}_r)$. The NNC rate region is the set of $(R_1, R_2)$ satisfying the cut-set conditions with a compression overhead penalty.

With $K = 5$ nodes, the gap is at most $(5-1)/2 = 2$ bits per user. The shared relay creates a rate coupling between the two users, but NNC handles it automatically through joint decoding.

With parallel relays: $Y_{r_k} = h_k X + Z_{r_k}$, $Y = \sum_k g_k X_{r_k} + Z$. The cut-set bound: $\min\{\frac{1}{2}\log(1+\sum_k |h_k|^2 P/N_{r_k}), \frac{1}{2}\log(1+\sum_k |g_k|^2 P_r/N)\}$.

Each relay quantizes at $\Delta_k = N_{r_k}$. The destination jointly decodes. The coherent gain loss: $(\sum \sqrt{|g_k|^2 P_r})^2 \leq K \sum |g_k|^2 P_r$ (Cauchy-Schwarz), giving a gap of $\frac{1}{2}\log K$.

$\frac{1}{2}\log K < (K-1)/2$ for all $K \geq 2$. The parallel structure allows a tighter gap because the compression indices at different relays are independent (no inter-relay interference to account for).

$R_{\text{DF}} = \min\{\min_k \frac{1}{2}\log(1+|h_k|^2 P/N_{r_k}), \frac{1}{2}\log(1+\sum_k |g_k|^2 P_{r_k}/N)\}$. The relay decoding constraint is the bottleneck when any source-relay link is weak.

$R_{\text{NNC}} \approx \frac{1}{2}\log(1+\frac{P}{N} \cdot \text{combined relay gain}) - O(K)$. NNC avoids the relay decoding bottleneck at the cost of the compression gap.

DF outperforms NNC when all source-relay SNRs exceed a threshold: $\min_k |h_k|^2 P / N_{r_k} > \text{effective NNC penalty}$. NNC outperforms DF when some source-relay link is weak: $\min_k |h_k|^2 P/N_{r_k} < \text{MAC capacity minus compression overhead}$. The exact boundary depends on the specific link gains and can be computed numerically.

DF outage occurs when $\min\{\frac{1}{2}\log(1+|h_{\text{sr}}|^2 \text{SNR}), \frac{1}{2}\log(1+|h_{\text{sd}}|^2 \text{SNR} + |h_{\text{rd}}|^2 \text{SNR}_{r})\} < R$. This simplifies to: $|h_{\text{sr}}|^2 < (2^{2R}-1)/\text{SNR}$ OR $|h_{\text{sd}}|^2 \text{SNR} + |h_{\text{rd}}|^2 \text{SNR}_{r} < 2^{2R}-1$.

With Rayleigh fading ($|h|^2 \sim \text{Exp}(1)$):

• Without direct link: $P_{\text{out}} \sim \frac{(2^{2R}-1)}{\text{SNR}} \cdot P(\text{relay-dest outage})$. The relay path has diversity order 1 (bottlenecked by worse of two serial links).
• With direct link: $P_{\text{out}} \sim \frac{(2^{2R}-1)^2}{\text{SNR}^{2}}$ at high SNR. Diversity order 2 because the direct and relay paths provide independent fading paths.

Partition the $n$ nodes into two halves $\mathcal{S}$ and $\mathcal{S}^c$ by a vertical line. Approximately $n/2$ source-destination pairs are cut. The total rate across this cut is bounded by the mutual information between the two halves.

The total transmit power on the source side is at most $nP/2$. With $\alpha = 2$ and distance $\sim 1$ between the two halves, the received power at the destination side is $\Theta(nP)$. The MIMO capacity across the cut is $\frac{1}{2}\log \det(\mathbf{I} + \text{SNR} \mathbf{H}\mathbf{H}^H)$ where $\mathbf{H}$ is the $n/2 \times n/2$ cross-cut channel matrix.

The total throughput is bounded by $\Theta(n)$ because the MIMO capacity across any balanced cut is $\Theta(n)$ (at most $n/2$ spatial DoF, each carrying $\Theta(1)$ bits). This matches the achievability result, proving optimality.