Exercises

Each AP estimates $K = 50$ channels. Total: $M \times K = 100 \times 50 = 5{,}000$ estimates per coherence block.

Per data symbol, each AP sends $K = 50$ combining outputs to the CPU. Total: $M \times K = 5{,}000$ complex scalars per symbol.

Each AP estimates channels to at most $L_{\max} = 12$ users. Total: $\sum_{m=1}^{M} |\mathcal{K}_m| \leq M \times L_{\max} = 100 \times 12 = 1{,}200$ estimates. Equivalently, $\sum_{k=1}^{K} |\mathcal{M}_k| = 50 \times 8 = 400$ estimates (the two sums are equal by double-counting the indicator matrix $\mathbf{D}$).

Per data symbol, AP $m$ sends $|\mathcal{K}_m| \leq 12$ combining outputs. Total: at most $1{,}200$ complex scalars per symbol, a $5{,}000/1{,}200 \approx 4.2\times$ reduction.

The total number of ones in $\mathbf{D}$ can be counted by rows or columns: $$\sum_{m=1}^{M} \sum_{k=1}^{K} D_{mk} = \sum_{m=1}^{M} |\mathcal{K}_m| = \sum_{k=1}^{K} |\mathcal{M}_k|.$$ The first equality follows because $|\mathcal{K}_m| = \sum_{k} D_{mk}$ (row sum). The second follows because $|\mathcal{M}_k| = \sum_{m} D_{mk}$ (column sum). $\blacksquare$

Since each user selects exactly $N_{\text{cl}}$ APs, the total number of ones in $\mathbf{D}$ is $N_{\text{cl}} K$.

If APs and users are uniformly and independently distributed in the deployment area, then by symmetry each AP is equally likely to be among the top $N_{\text{cl}}$ for any given user. The expected load is $\mathbb{E}[|\mathcal{K}_m|] = N_{\text{cl}} K / M$. For $N_{\text{cl}} = 10$, $K = 100$, $M = 500$: expected load $= 2$ users per AP.

The bound $|\mathcal{K}_m| \leq K$ is the trivial worst case (all users select AP $m$). In practice, centrally located APs carry more load than edge APs. The load distribution follows approximately a Poisson distribution with parameter $N_{\text{cl}} K / M$, with deviations from non-uniform deployment. $\blacksquare$

In user-centric processing, the CPU forms $\hat{s}_k = \sum_{m \in \mathcal{M}_k} \hat{g}_{mk}^* y_m$ instead of $\sum_{m=1}^{M}$. Every subsequent step in the UatF derivation applies with $\{1, \ldots, M\}$ replaced by $\mathcal{M}_k$.

Signal power: $p_k (\sum_{m \in \mathcal{M}_k} \gamma_{mk})^2$. Interference from user $k'$: $p_{k'} \sum_{m \in \mathcal{M}_k} \gamma_{mk} \beta_{mk'}$. Note that the interference sum runs over $\mathcal{M}_k$, capturing only the interference seen at user $k$'s serving APs — which is all that matters.

Combining yields $$\text{SINR}_k^{\text{UC}} = \frac{p_k (\sum_{m \in \mathcal{M}_k} \gamma_{mk})^2}{\sum_{k'} p_{k'} \sum_{m \in \mathcal{M}_k} \gamma_{mk} \beta_{mk'} + \sigma^2 \sum_{m \in \mathcal{M}_k} \gamma_{mk}}$$ which matches TSINR Under User-Centric MRC Processing. $\blacksquare$

The AP closest to $x_u = 0.5$ is AP 25 (or 26) with distance $|0.49 - 0.5| = 0.01$. Path loss: $(0.01 + 0.01)^{-3} = 0.02^{-3} = 1.25 \times 10^5$. The 5th-closest AP has distance $\approx 0.05$, path loss $(0.06)^{-3} \approx 4630$. The 10th-closest has distance $\approx 0.1$, path loss $(0.11)^{-3} \approx 751$.

Numerically, the top 5 APs capture $\approx 88\%$ of the total gain, and the top 8 APs capture $\approx 95\%$. So $N_{\text{cl}} \approx 8$ suffices to capture 95% of the beamforming gain, leaving the remaining 42 APs essentially irrelevant.

With path loss exponent $\alpha = 3$, the contribution of an AP at distance $d$ from the user decays as $d^{-3}$. The closest few APs dominate the sum, and the cluster size needed to capture most of the gain is small and independent of $M$.

$\rho(k, k') = \sum_{m \in \mathcal{M}_k} \beta_{mk'} + \sum_{m \in \mathcal{M}_{k'}} \beta_{mk}$. Swapping $k$ and $k'$: $\rho(k', k) = \sum_{m \in \mathcal{M}_{k'}} \beta_{mk} + \sum_{m \in \mathcal{M}_k} \beta_{mk'} = \rho(k, k')$. $\checkmark$

Since $\beta_{mk} \geq 0$ for all $m, k$, each sum is non-negative, hence $\rho(k, k') \geq 0$. Equality holds iff both sums are zero, which requires every term to be zero: $\beta_{mk'} = 0$ for all $m \in \mathcal{M}_k$ and $\beta_{mk} = 0$ for all $m \in \mathcal{M}_{k'}$. $\blacksquare$

Suppose AP $m$ is at the center of a dense user cluster. All nearby users satisfy $\beta_{mk} \geq \beta_{\text{th}}$. If there are 100 such users, then $|\mathcal{K}_m| = 100$, violating $L_{\max}$ unless $L_{\max} \geq 100$.

Modify the clustering to process users sequentially (e.g., by decreasing rate requirement). When assigning $\mathcal{M}_k$, include AP $m$ only if $\beta_{mk} \geq \beta_{\text{th}}$ and $|\mathcal{K}_m| < L_{\max}$. If the load constraint is binding, the user selects the next-best AP. This ensures $\max_m |\mathcal{K}_m| \leq L_{\max}$ at the cost of slightly degraded cluster quality for some users.

For a given $t > 0$, the constraint $\text{SINR}_k^{\text{fog}} \geq t$ becomes $$p_k \left(\sum_{m \in \mathcal{M}_k} \gamma_{mk}\right)^2 \geq t \left[\sum_{k'} p_{k'} \sum_{m \in \mathcal{M}_k} \gamma_{mk} \beta_{mk'} + \sigma^2 \sum_{m \in \mathcal{M}_k} \gamma_{mk}\right].$$

Rearranging: $p_k A_k - t \sum_{k'} p_{k'} B_{kk'} \geq t C_k$ where $A_k = (\sum_{m \in \mathcal{M}_k} \gamma_{mk})^2$, $B_{kk'} = \sum_{m \in \mathcal{M}_k} \gamma_{mk} \beta_{mk'}$, $C_k = \sigma^2 \sum_{m \in \mathcal{M}_k} \gamma_{mk}$. This is linear in $\{p_k\}$ for fixed $t$.

Combined with the per-AP constraints $\sum_{k \in \mathcal{K}_m} p_k \leq P_t$, the feasibility check is a linear program. Bisect over $t$: if feasible at $t$, try $t' > t$; if infeasible, try $t' < t$. The max-min SINR is the largest feasible $t$. $\blacksquare$

Each cluster $\mathcal{M}_k$ covers a spatial region around user $k$ with "radius" proportional to $(N_{\text{cl}}/M)^{1/d}$ in $d$ dimensions. Two clusters overlap if their regions intersect, which happens when $|x_k - x_{k'}| \lesssim 2(N_{\text{cl}}/M)^{1/d}$.

The probability that user $k'$ overlaps with $k$'s cluster is proportional to the overlap area divided by the total area, which scales as $O(N_{\text{cl}}/M)$ (in 2D, area scales as $N_{\text{cl}}/M$). The expected number of overlapping users is $O(K \cdot N_{\text{cl}}/M)$.

The contamination metric $\rho(k, k')$ is significant when both clusters overlap, introducing a factor of $N_{\text{cl}}$ for the number of shared APs. The average degree is $O(N_{\text{cl}} \cdot K \cdot N_{\text{cl}}/M) = O(N_{\text{cl}}^2 K/M)$. For $N_{\text{cl}} = 10$, $K = 100$, $M = 500$: degree $\approx 2$. The interference graph is sparse. $\blacksquare$

AP $m$ computes $|\mathcal{K}_m|$ MMSE channel estimates and sends them to the master APs. Each estimate is a complex scalar quantized with $B_q$ bits. Pilot phase rate: $|\mathcal{K}_m| \cdot 2 B_q$ bits per coherence block.

During the $\tau_c - \tau_p$ data symbols, AP $m$ sends $|\mathcal{K}_m|$ combining outputs per symbol, each quantized with $B_q$ bits. Data phase rate: $|\mathcal{K}_m| \cdot 2 B_q \cdot (\tau_c - \tau_p)$ bits.

Total per coherence block: $|\mathcal{K}_m| \cdot 2 B_q \cdot (1 + \tau_c - \tau_p)$ bits. Per-second rate: $F_m = \frac{|\mathcal{K}_m| \cdot 2 B_q \cdot (1 + \tau_c - \tau_p)}{T_c}$. With $|\mathcal{K}_m| = 15$, $B_q = 8$, $\tau_c = 200$, $\tau_p = 10$, $T_c = 1$ ms: $F_m = 15 \times 16 \times 191 / 10^{-3} = 45.84$ Mbps. $\blacksquare$

$\sum_{m \in \mathcal{M}_k} \gamma_{mk} = N_{\text{cl}} \gamma$ and $\sum_{m \in \mathcal{M}_k} \gamma_{mk} \beta_{mk'} = N_{\text{cl}} \gamma \beta_0$. Substituting into TSINR Under User-Centric MRC Processing yields the stated expression.

The full cell-free SINR replaces $N_{\text{cl}}$ by $M$: $\text{SINR}_k^{\text{full}} / \text{SINR}_k^{\text{UC}} \approx M / N_{\text{cl}}$ in the interference-limited regime. However, this idealized scenario overstates the gain of additional APs because all APs have equal path loss. In practice, path loss decay makes the additional APs much weaker. $\blacksquare$

Zero-contamination pilot assignment requires ${\mathbf{S}_{i,k}}_{k} \neq {\mathbf{S}_{i,k}}_{k'}$ whenever $(k, k') \in E$. This is exactly the definition of a proper vertex coloring of $G$ with $\tau_p$ colors. The minimum $\tau_p$ is $\chi(G)$.

Brooks' theorem states that $\chi(G) \leq \Delta(G) + 1$ for any graph, with equality only for complete graphs and odd cycles. Since the interference graph is typically sparse ($\Delta(G) \ll K$), we have $\chi(G) \ll K$.

If the user-centric clusters have limited overlap — for instance, each cluster overlaps with at most $d$ other clusters — then $\Delta(G) \leq d$ and $\chi(G) \leq d + 1$. For well-separated users or small cluster sizes, $d$ remains bounded even as $K \to \infty$. $\blacksquare$

For user 1 (centered at AP 3): $\beta_{11} = (0.4 + 1)^{-1} = 0.714$, $\beta_{21} = (0.1 + 1)^{-1} = 0.909$, $\beta_{31} = 1.0$, $\beta_{41} = 0.909$, $\beta_{51} = 0.714$. For user 2 (centered at AP 5): $\beta_{32} = (0.4 + 1)^{-1} = 0.714$, $\beta_{42} = 0.909$, $\beta_{52} = 1.0$, $\beta_{62} = 0.909$, $\beta_{72} = 0.714$.

$\sum_{m \in \mathcal{M}_1} \beta_{m2} = \beta_{12} + \beta_{22} + \beta_{32} + \beta_{42} + \beta_{52}$. $\beta_{12} = (0.1 \cdot 16 + 1)^{-1} = 0.385$, $\beta_{22} = (0.1 \cdot 9 + 1)^{-1} = 0.526$. Sum $= 0.385 + 0.526 + 0.714 + 0.909 + 1.0 = 3.534$. Similarly, $\sum_{m \in \mathcal{M}_2} \beta_{m1} = \beta_{31} + \beta_{41} + \beta_{51} + \beta_{61} + \beta_{71}$. $\beta_{61} = (0.1 \cdot 9 + 1)^{-1} = 0.526$, $\beta_{71} = (0.1 \cdot 16 + 1)^{-1} = 0.385$. Sum $= 1.0 + 0.909 + 0.714 + 0.526 + 0.385 = 3.534$. So $\rho(1, 2) = 3.534 + 3.534 = 7.068$.

$\sum_{m \in \mathcal{M}_1} \beta_{m1} = 0.714 + 0.909 + 1.0 + 0.909 + 0.714 = 4.246$. $\sum_{m \in \mathcal{M}_2} \beta_{m2} = 0.714 + 0.909 + 1.0 + 0.909 + 0.714 = 4.246$. Threshold: $\epsilon \cdot \min(4.246, 4.246) = 0.1 \times 4.246 = 0.4246$. Since $\rho(1, 2) = 7.068 \gg 0.4246$, the users cannot safely share a pilot. The overlapping clusters cause too much contamination.

$\max_{\mathbf{D}, \{{\mathbf{S}_{i,k}}_{k}\}} \min_k R_k(\mathbf{D}, \{{\mathbf{S}_{i,k}}_{k}\})$$subject to:$D_{mk} \in {0, 1}$,$\sum_k D_{mk} \leq L_{\max}$,$\sum_m D_{mk} \leq N_{\max}$,${\mathbf{S}{i,k}}{k} \in {1, \ldots, \tau_p}$. The rate$R_k$depends on both the cluster (through the SINR sums) and the pilot assignment (through the estimation quality$\gamma_{mk}$).

Even for fixed $\mathbf{D}$, the pilot assignment subproblem is equivalent to weighted graph coloring on the interference graph, which is NP-hard. The addition of binary cluster variables only makes the problem harder.

Stage 1 (Cluster design): Apply LLSF clustering assuming orthogonal pilots (no contamination). This gives an initial $\mathbf{D}$. Stage 2 (Pilot assignment): Given $\mathbf{D}$, build the interference graph and apply greedy graph coloring. Optional refinement: Iteratively update clusters based on the contamination pattern from Stage 2, then re-run Stage 2. Convergence is typically achieved in 2–3 iterations. This heuristic runs in polynomial time and achieves near-optimal performance in simulations.

1. Pilot assignment: The master AP decides which pilot sequence user $k$ should transmit, using knowledge of the local interference graph.
2. Power control: The master AP computes the transmit power coefficients for user $k$, solving a local version of the max-min fairness problem.
3. Data routing: The master AP receives the final decoded data for user $k$ and forwards it to the core network. $\blacksquare$

Generate random AP and user locations. For each $N_{\text{cl}}$, compute the user-centric SINR using TSINR Under User-Centric MRC Processing and compare the CDFs. The 5th-percentile rate is $R_{0.05} = \log_2(1 + \text{SINR}_{0.05})$.

For $N_{\text{cl}} = 10$, the 5th-percentile SINR is typically within 2–3 dB of the full cell-free baseline. For $N_{\text{cl}} = 20$, the gap shrinks to less than 1 dB. $N_{\text{cl}} = 5$ shows a noticeable gap of 4–6 dB but still far outperforms cellular.

Define the marginal utility of adding AP $m$ to user $k$'s cluster: $\Delta U_{mk} = R_k(\mathcal{M}_k \cup \{m\}) - R_k(\mathcal{M}_k) - c_{\text{fh}}$ where $c_{\text{fh}}$ is the fronthaul cost per AP-user link. Add AP $m$ if $\Delta U_{mk} > 0$ and $|\mathcal{K}_m| < L_{\max}$.

Initialize with $\mathcal{M}_k = \{m^*(k)\}$ (master AP only). Iteratively add the AP with the largest positive $\Delta U_{mk}$ until no AP improves the utility. The algorithm is a greedy hill-climbing procedure.

The utility function is submodular in the AP set (adding APs has diminishing returns due to the log in the rate expression). Therefore, the greedy algorithm achieves at least $(1 - 1/e)$-fraction of the optimal utility. The algorithm terminates in at most $M$ iterations per user, and the total complexity is $O(K M)$.