Abstract
A fundamental challenge in wireless network performance engineering is optimizing link activation—the selection of concurrent links that satisfy specific signal-to-interference-and-noise ratio (SINR) thresholds. Traditionally, this combinatorial problem is approached using Single-User Decoding (SUD), which treats all interference as additive noise. This paper explores a paradigm shift toward Multiuser Decoding (MUD) receivers capable of Successive Interference Cancellation (SIC) and Parallel Interference Cancellation (PIC). By proving the NP-hardness of these problems and developing compact integer linear programming (ILP) formulations, we demonstrate that interference cancellation allows for significantly denser link packing. Our findings indicate substantial throughput improvements at low-to-medium SINR thresholds, providing a benchmark for future scheduling and resource management protocols.
Introduction
In traditional wireless networking, "spatial reuse" is the governing principle: to avoid interference, active links must be separated by sufficient physical distance. This approach stems from the use of Single-User Decoding (SUD), where any signal not intended for a specific receiver is treated as noise. However, modern receiver capabilities allow for a more sophisticated approach. Multiuser Decoding (MUD) enables a receiver to decode a strong interfering signal, subtract it from the total received signal, and then decode its own intended message with a significantly improved SINR.
This paper investigates the optimal Link Activation (LA) problem under this new setup. We move beyond the view of interference as a purely negative force, exploring how Interference Cancellation (IC) can be leveraged to increase network density and throughput.
The Mechanics of Interference Cancellation
The authors analyze two primary methods of interference cancellation:
- Parallel IC (PIC): This involves a single stage of cancellation. For an interferer to be removed, its signal must be strong enough to be decoded successfully in the presence of all other active signals and noise.
- Successive IC (SIC): This is a multi-stage process. Once a dominant interferer is decoded and removed, the effective noise floor drops. This reduction may then allow a second, slightly weaker interferer to be decoded and removed, creating a "domino effect" of signal purification.
While IC offers clear benefits, it complicates the link activation problem. Scheduling no longer involves just selecting a set of links; it requires determining which links will cancel which others and in what specific order.
Theoretical Contributions and Complexity
The paper establishes that both LA-PIC and LA-SIC are NP-hard, confirming that finding the global optimum for large-scale networks is computationally intensive. To address this, the authors developed compact Integer Linear Programming (ILP) formulations to find optimal solutions for benchmarking:
- PIC Formulation: The authors achieved a formulation of quadratic size $O(K^2)$ relative to the number of links $K$.
- SIC and the Pre-ordering Theorem: The most significant theoretical breakthrough involves the "Pre-ordering Theorem." For the case of a common SINR threshold, the authors proved that at the optimum, if a receiver can cancel a specific interfering signal, it must also be able to cancel any signal stronger than it. This insight allowed them to reduce the SIC formulation from a complex permutation problem to a manageable $O(K^2)$ linear model. For general cases with individual thresholds, a cubic $O(K^3)$ formulation was provided.
Performance Evaluation
The models were tested using two synthetic datasets: Dataset I (Information-Theoretic), featuring arbitrary link lengths, and Dataset N (Networking-Oriented), mimicking multihop mesh networks with link lengths between 3m and 200m. Tests were conducted across sparse and dense topologies with 5 to 30 links.
Key Findings
- The Power of SIC: At low-to-medium SINR thresholds (e.g., -9dB), SIC can activate three to four times as many links as the SUD baseline. While SIC consistently outperforms PIC, even simple "Single-Link IC" (canceling only the strongest interferer) captures the majority of the available gains.
- The SINR Cliff: The benefits of IC are not infinite. There is a distinct threshold (approximately 3dB in these tests) where the intended signal becomes so dominant that it is no longer possible to decode the interferer first. Beyond this "cliff," IC gains vanish, and the network reverts to traditional spatial reuse patterns.
- Robustness: The relative gains provided by IC remained remarkably consistent across different network densities, suggesting that the benefits of multiuser decoding scale well with network size.
Conclusion and Future Directions
This research demonstrates that strong interference, traditionally viewed as a disaster for wireless links, can be an asset when using MUD receivers. By providing optimal ILP formulations, the authors have established a rigorous benchmark for the maximum possible gains from interference cancellation.
Future work may expand these models to include dynamic power control, which could further optimize the "cancelability" of interferers. Additionally, while the $O(K^2)$ formulations are compact, they remain too slow for real-time scheduling in massive networks. These optimal results should therefore serve as the foundation for developing high-performance, distributed heuristics for next-generation wireless systems.
Summary updated