On Optimal Link Activation with Interference Cancellation in Wireless Networking

Di Yuan, Vangelis Angelakis, Lei Chen, Eleftherios Karipidis, Erik G. Larsson

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:

  1. 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.
  2. 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

Abstract

A fundamental aspect in performance engineering of wireless networks is optimizing the set of links that can be concurrently activated to meet given signal-to-interference-and-noise ratio (SINR) thresholds. The solution of this combinatorial problem is the key element in scheduling and cross-layer resource management. Previous works on link activation assume single-user decoding receivers, that treat interference in the same way as noise. In this paper, we assume multiuser decoding receivers, which can cancel strongly interfering signals. As a result, in contrast to classical spatial reuse, links being close to each other are more likely to be active simultaneously. Our goal here is to deliver a comprehensive theoretical and numerical study on optimal link activation under this novel setup, in order to provide insight into the gains from adopting interference cancellation. We therefore consider the optimal problem setting of successive interference cancellation (SIC), as well as the simpler, yet instructive, case of parallel interference cancellation (PIC). We prove that both problems are NP-hard and develop compact integer linear programming formulations that enable us to approach the global optimum solutions. We provide an extensive numerical performance evaluation, indicating that for low to medium SINR thresholds the improvement is quite substantial, especially with SIC, whereas for high SINR thresholds the improvement diminishes and both schemes perform equally well.
BibTeX
@misc{yuan2011optimal,
  author = {Di Yuan and Vangelis Angelakis and Lei Chen and Eleftherios Karipidis and Erik G. Larsson},
  title = {{On Optimal Link Activation with Interference Cancellation in Wireless Networking}},
  year = {2011},
  eprint = {1112.1314},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1112.1314},
}
Figure