Efficient Interference Management Policies for Femtocell Networks

Kartik Ahuja, Yuanzhang Xiao, Mihaela van der Schaar

Abstract

Managing interference in a network of macrocells underlaid with femtocells presents an important, yet challenging problem. A majority of spatial (frequency/time) reuse based approaches partition the users based on coloring the interference graph, which is shown to be suboptimal. Some spatial time reuse based approaches schedule the maximal independent sets (MISs) in a cyclic, (weighted) round-robin fashion, which is inefficient for delay-sensitive applications. Our proposed policies schedule the MISs in a non-cyclic fashion, which aim to optimize any given network performance criterion for delay-sensitive applications while fulfilling minimum throughput requirements of the users. Importantly, we do not take the interference graph as given as in existing works; we propose an optimal construction of the interference graph. We prove that under certain conditions, the proposed policy achieves the optimal network performance. For large networks, we propose a low-complexity algorithm for computing the proposed policy. We show that the policy computed achieves a constant competitive ratio (with respect to the optimal network performance), which is independent of the network size, under wide range of deployment scenarios. The policy can be implemented in a decentralized manner by the users. Compared to the existing policies, our proposed policies can achieve improvement of up to 130 % in large-scale deployments.

Introduction

As mobile data demand continues to grow, operators are increasingly deploying "femtocells"—small, low-power base stations—to offload traffic from congested macrocells. However, the dense deployment of these small cells, particularly in environments like apartment buildings or office complexes, creates a complex "interference nightmare."

Traditional interference management solutions typically fall into two categories:

  1. Power Control: All users transmit simultaneously but at reduced power levels, which often results in poor Signal-to-Interference-plus-Noise Ratio (SINR).
  2. Spatial Reuse (Coloring/Cyclic Scheduling): Users are partitioned into non-interfering groups (colors) that take turns transmitting.

This research argues that these approaches are suboptimal. Standard graph coloring fails to maximize the number of simultaneous transmissions. Moreover, cyclic (round-robin) scheduling is poorly suited for delay-sensitive traffic, such as video streaming or gaming, as users may miss packet deadlines while waiting for their allocated slot in the cycle.

Methodology

The proposed framework introduces a five-step design process to optimize interference management:

  1. Information Gathering: Local channel gains and Quality of Service (QoS) requirements are collected.
  2. Optimal Graph Construction: Unlike traditional methods that treat the interference graph as static, this approach treats the distance threshold (determining interference between cells) as a tunable parameter to maximize overall performance.
  3. MIS Identification: The system identifies Maximal Independent Sets (MISs)—the largest groups of users capable of simultaneous transmission without violating interference constraints.
  4. Target Weight Optimization: A convex optimization problem is solved to determine the ideal time fraction for each MIS to meet minimum throughput requirements.
  5. Non-Stationary Scheduling: An online, decentralized algorithm is employed where User Equipments (UEs) track a performance metric, and the MIS with the highest metric is scheduled. This non-cyclic approach allows for dynamic adaptation to traffic needs.
Figure 1: (a) Comparison of coloring-based vs. MIS-based scheduling. (b) System model and interference graph construction.

For large-scale networks where finding all MISs is computationally prohibitive (NP-hard), a low-complexity variant using approximate vertex coloring is introduced to find a high-performing subset of MISs in polynomial time. The framework was evaluated using numerical simulations of small-scale (3x3 grid) and large-scale (12-room building with up to 180 UEs) deployments.

Key Insights

  • Non-Cyclic Scheduling: By moving away from rigid round-robin queues, the proposed policy "spreads" transmission opportunities more effectively, significantly benefiting delay-sensitive packets.
  • Optimized Graph Construction: The interference graph is treated as a "binary quantization" of the physical environment. By carefully selecting the distance threshold, the system balances strong local interference against cumulative weak interference from distant cells.
  • Scalability: The low-complexity algorithm maintains a constant competitive ratio relative to the theoretical optimum, ensuring performance does not degrade as the network size increases.
  • Decentralized Execution: While target weights are calculated centrally, slot-by-slot decisions are made by UEs with zero communication overhead during the transmission phase.

Results and Performance

The proposed policies demonstrate significant gains over existing methods:

  • Throughput Improvements: In a 5-femtocell pentagon network, the policy achieved a max-min throughput of 1.60 bits/s/Hz, outperforming constant power (1.32) and cyclic MIS scheduling (1.49).
  • Large-Scale Gains: In dense deployments of 180 UEs, the policy showed a 131% improvement in worst-case user throughput compared to cyclic policies.
  • Robustness: The policy remains practical under dynamic channel conditions. Using a fixed interference graph based on average path loss resulted in only an 8% performance loss compared to frequent re-computation, suggesting high real-world viability.

Conclusion and Future Work

While the proposed framework offers substantial improvements, some challenges remain. The policy assumes time-slotted synchronization across all cells, which can be difficult in uncoordinated residential settings. Additionally, while the framework handles fading, it primarily focuses on static or slow-moving users; high mobility would require more frequent updates to the MIS sets. Future work may also address the signaling overhead on backhaul links required for initial channel gain reporting in extremely large networks.

Summary updated

Abstract

Managing interference in a network of macrocells underlaid with femtocells presents an important, yet challenging problem. A majority of spatial (frequency/time) reuse based approaches partition the users based on coloring the interference graph, which is shown to be suboptimal. Some spatial time reuse based approaches schedule the maximal independent sets (MISs) in a cyclic, (weighted) round-robin fashion, which is inefficient for delay-sensitive applications. Our proposed policies schedule the MISs in a non-cyclic fashion, which aim to optimize any given network performance criterion for delay-sensitive applications while fulfilling minimum throughput requirements of the users. Importantly, we do not take the interference graph as given as in existing works; we propose an optimal construction of the interference graph. We prove that under certain conditions, the proposed policy achieves the optimal network performance. For large networks, we propose a low-complexity algorithm for computing the proposed policy. We show that the policy computed achieves a constant competitive ratio (with respect to the optimal network performance), which is independent of the network size, under wide range of deployment scenarios. The policy can be implemented in a decentralized manner by the users. Compared to the existing policies, our proposed policies can achieve improvement of up to 130 % in large-scale deployments.
BibTeX
@article{ahuja2015efficient,
  author = {Kartik Ahuja and Yuanzhang Xiao and Mihaela van der Schaar},
  title = {{Efficient Interference Management Policies for Femtocell Networks}},
  journal = {IEEE Trans. Wireless Communications},
  year = {2015},
  url = {https://openreview.net/forum?id=jFeNaD8IbJi},
}
Figure