Distributed Interference Management Policies for Heterogeneous Small Cell Networks

Kartik Ahuja, Yuanzhang Xiao, Mihaela van der Schaar

TL;DR

This paper introduces a scalable, distributed framework for managing interference in dense, heterogeneous small cell networks (like picocells and femtocells). By combining graph theory (Maximal Independent Sets) with a clever optimization reformulation (ADMM), the authors achieve throughput gains of up to 700% over existing methods while guaranteeing performance that stays consistent regardless of how large the network grows.

What Problem Does This Paper Address?

As mobile data demand explodes, providers are deploying "small cells" (low-power base stations) in offices and homes. While this boosts capacity, it creates a "wild west" of interference. Traditional cellular networks rely on a central controller to tell every device when to transmit, but in a dense, heterogeneous environment with thousands of small cells, centralized coordination is computationally impossible (NP-hard) and creates massive signaling overhead.

The challenge is: How can individual user equipments (UEs) and base stations (SBSs) decide when to transmit and at what power level using only local information, while still ensuring every user meets their minimum throughput requirements?

Methods

The authors propose a four-step distributed framework:

  1. Neighbor Identification: Each UE-SBS pair identifies "strong interferers" in its immediate vicinity to build a local view of an interference graph.
  2. Distributed MIS Generation: The network identifies Maximal Independent Sets (MISs). An independent set is a group of users who don't strongly interfere with each other and can therefore transmit simultaneously (spatial reuse). The authors provide a distributed algorithm that finds these sets in logarithmic time relative to the number of users—a significant speedup over previous linear-time methods.
  3. Optimization via ADMM: Determining the optimal fraction of time each MIS should transmit is normally a "coupled" problem requiring global knowledge. The authors reformulate this into a Decoupled Problem (DP). They use the Alternating Direction Method of Multipliers (ADMM), allowing users to reach a consensus on optimal timing through simple local message exchanges with neighbors.
  4. Transmission: Users transmit during their assigned time slots at maximum power, exploiting the "weak" interference allowed within an MIS.

The framework also includes a self-adjusting mechanism to handle users entering or leaving the network without recomputing the entire schedule.

Datasets

The paper evaluates the framework using extensive numerical simulations rather than static datasets, as is standard for wireless networking research. They modeled:

  • Small-scale scenarios: A 4-cell heterogeneous network (2 picocells, 2 femtocells).
  • Large-scale scenarios: A 3x3 grid of 9 SBSs and a 12-room building model with up to 105 UEs.
  • Channel Models: They used standard path-loss models (exponent of 4) and Rayleigh fading to simulate realistic, time-varying wireless environments.

Key Insights and Ideas

  • Spatial Reuse > Power Control: Traditional methods often focus on constant power control. This paper argues that "scheduling" (turning users on/off via MISs) is more effective at eliminating the "strong" interference that kills performance in dense deployments.
  • The Power of Decoupling: The "aha moment" is the mathematical proof that a global optimization problem can be solved locally. By introducing auxiliary variables and using ADMM, the authors prove that local consensus is equivalent to the global optimum.
  • Size Doesn't Matter (For Performance): They analytically prove a constant competitive ratio. This means the gap between their distributed solution and the theoretical "perfect" centralized solution does not grow as you add more base stations. This is the definition of true scalability.
  • Bounded-Degree Necessity: The authors show that for the system to be feasible (meeting everyone's minimum requirements), the interference graph must have a bounded degree. Essentially, if one user is being blasted by too many neighbors, no algorithm—centralized or otherwise—can save their connection.

Key Results

  • Massive Throughput Gains: In simulations, the proposed policy outperformed state-of-the-art STDMA and power control policies by 150% to 700%.
  • Fairness: Under max-min fairness criteria, the policy achieved significantly higher minimum throughput for the "worst-off" users compared to standard benchmarks.
  • Fast Convergence: The distributed coloring and MIS generation converged in logarithmic time, making it practical for real-time hardware implementation.
  • Robustness: The system maintained high performance even under dynamic channel conditions (fading) and when users frequently entered or exited the network.

Limitations and Future Work

  • Synchronization: The model assumes time-slotted synchronization across the network. Implementing this in a truly ad-hoc, uncoordinated environment can be challenging in practice.
  • Backhaul Overhead: While the message exchange is "local," it still requires a reliable backhaul (like the X2 interface) between neighboring small cells to exchange ADMM parameters.
  • Beamforming: The current model does not explicitly implement beamforming (MIMO). The authors suggest that beamforming could be integrated by "deleting edges" in the interference graph (since beamforming reduces interference), but they don't provide a formal joint optimization for it.
  • Fixed SBS: The self-adjusting mechanism handles dynamic users, but assumes the base stations themselves are stationary and their locations are known.

Summary updated

Abstract

We study the problem of distributed interference management in a network of heterogeneous small cells with different cell sizes, different numbers of user equipments (UEs) served, and different throughput requirements by UEs. We consider the uplink transmission, where each UE determines when and at what power level it should transmit to its serving small cell base station (SBS). We propose a general framework for designing distributed interference management policies, which exploits weak interference among non-neighboring UEs by letting them transmit simultaneously (i.e., spatial reuse), while eliminating strong interference among neighboring UEs by letting them transmit in different time slots. The design of optimal interference management policies has two key steps. Ideally, we need to find all the subsets of non-interfering UEs i.e., the maximal independent sets (MISs) of the interference graph, but this is computationally intractable even when solved in a centralized manner. Then, to maximize some given network performance criterion subject to UEs' minimum throughput requirements, we need to determine the optimal fraction of time occupied by each MIS, which requires global information (e.g., all the UEs' throughput requirements and channel gains). In our framework, we first propose a distributed algorithm for the UE-SBS pairs to find a subset of MISs in logarithmic time (with respect to the number of UEs). Then we propose a novel problem reformulation which enables UE-SBS pairs to determine the optimal fraction of time occupied by each MIS with only local message exchange among the neighbors in the interference graph. Despite the fact that our interference management policies are distributed and utilize only local information, we can analytically bound their performance under a wide range of heterogeneous deployment scenarios in terms of the competitive ratio with respect to the optimal network performance, which can only be obtained in a centralized manner with NP complexity. Remarkably, we prove that the competitive ratio is independent of the network size. Through extensive simulations, we show that our proposed policies achieve significant performance improvements (ranging from 160% to 700%) over state-of-the-art policies.
BibTeX
@article{ahuja2015distributed,
  author = {Kartik Ahuja and Yuanzhang Xiao and Mihaela van der Schaar},
  title = {{Distributed Interference Management Policies for Heterogeneous Small Cell Networks}},
  journal = {IEEE J. Sel. Areas Commun.},
  year = {2015},
  url = {https://openreview.net/forum?id=6dbOQIz-2Y},
}

Loading related content...

Figure