Coordinated Scheduling for the Downlink of Cloud Radio-Access Networks

Ahmed Douik, Hayssam Dahrouj, Tareq Y. Al-Naffouri, Mohamed-Slim Alouini

Abstract

This paper addresses the coordinated scheduling problem in cloud-enabled networks. Consider the downlink of a cloud-radio access network (C-RAN), where the cloud is only responsible for the scheduling policy and the synchronization of the transmit frames across the connected base-stations (BS). The transmitted frame of every BS consists of several time/frequency blocks, called power-zones (PZ), maintained at fixed transmit power. The paper considers the problem of scheduling users to PZs and BSs in a coordinated fashion across the network, by maximizing a network-wide utility under the practical constraint that each user cannot be served by more than one base-station, but can be served by one or more power-zone within each base-station frame. The paper solves the problem using a graph theoretical approach by introducing the scheduling graph in which each vertex represents an association of users, PZs and BSs. The problem is formulated as a maximum weight clique, in which the weight of each vertex is the benefit of the association represented by that vertex. The paper further presents heuristic algorithms with low computational complexity. Simulation results show the performance of the proposed algorithms and suggest that the heuristics perform near optimal in low shadowing environments.

Introduction

In the evolution toward 5G and beyond, Cloud Radio-Access Networks (C-RANs) have emerged as a primary solution for interference management. Traditional research often focuses on signal-level coordination, where multiple base stations (BSs) jointly process signals for a single user. While high-performing, this approach demands massive backhaul capacity to share raw data streams in real-time, which is often prohibitively expensive. This paper shifts the focus to coordinated scheduling, where a central cloud acts as a master conductor, synchronizing BS timing and allocating resource blocks without the need for high-capacity signal processing.

System Model and Constraints

The network consists of multiple BSs, each transmitting frames divided into time/frequency resource blocks called power-zones (PZs). These PZs are maintained at fixed transmit powers. The scheduling challenge is to assign users to these resources across the network to maximize total utility while adhering to two critical practical constraints:

  1. C1: A user can only be served by a single base station at any given time to avoid the overhead of joint signal processing.
  2. C2: Each individual power-zone can serve exactly one user.
Network configuration and frame structure for the coordinated C-RAN downlink.

Graph-Theoretical Methodology

The authors propose a novel graph-theoretical reformulation of the scheduling problem. By representing every possible association—a triplet of (User, Base Station, Power-Zone)—as a vertex in a scheduling graph, the allocation problem is transformed into a Maximum Weight Clique (MWC) problem.

In this graph, edges connect vertices that are "compatible" according to constraints C1 and C2. For instance, two vertices representing the same user associated with different base stations are not connected. The weight of each vertex represents the benefit (e.g., achievable data rate) of that association. Finding the optimal schedule thus becomes equivalent to finding the heaviest clique in the graph.

To address the NP-hard nature of the MWC problem, the paper introduces two heuristics:

  • HEU-SHD: A greedy algorithm that iteratively selects the highest-weight vertex and prunes incompatible ones.
  • p-SHD: A pruned version that considers only the top $p$ fraction of associations, significantly reducing computational complexity.

Performance Evaluation

The proposed algorithms were evaluated using synthetic simulations in a hexagonal cellular layout with 3 to 21 base stations, utilizing the SUI-3 Terrain type B channel model. Key parameters included a 10 MHz bandwidth and a cell-to-cell distance of 500 meters.

Sum rate performance as a function of the fraction of considered associations p.

Key Results

  • Near-Optimality: The greedy HEU-SHD heuristic performs remarkably close to the optimal solution (OPT-SHD), particularly in low-shadowing environments where interference patterns are more predictable.
  • The 30% Rule: Results for the $p$-SHD heuristic indicate that considering only the top 30% ($p=0.3$) of possible associations yields performance nearly identical to the full graph search. This represents a massive win for computational efficiency in real-time systems.
  • Scalability: In larger networks (e.g., 21 BSs), the $p$-SHD algorithm maintained high performance even when considering as little as 7% of possible associations, showing negligible performance drops.

Conclusion

Scheduling-level coordination offers a compelling middle ground between uncoordinated networks and high-cost signal-level coordination. By mapping wireless optimization to well-understood graph problems, this research provides a scalable framework for interference mitigation. Future work may explore joint power control and scheduling, as well as the impact of backhaul latency on large-scale deployments.

Summary updated

Abstract

This paper addresses the coordinated scheduling problem in cloud-enabled networks. Consider the downlink of a cloud-radio access network (C-RAN), where the cloud is only responsible for the scheduling policy and the synchronization of the transmit frames across the connected base-stations (BS). The transmitted frame of every BS consists of several time/frequency blocks, called power-zones (PZ), maintained at fixed transmit power. The paper considers the problem of scheduling users to PZs and BSs in a coordinated fashion across the network, by maximizing a network-wide utility under the practical constraint that each user cannot be served by more than one base-station, but can be served by one or more power-zone within each base-station frame. The paper solves the problem using a graph theoretical approach by introducing the scheduling graph in which each vertex represents an association of users, PZs and BSs. The problem is formulated as a maximum weight clique, in which the weight of each vertex is the benefit of the association represented by that vertex. The paper further presents heuristic algorithms with low computational complexity. Simulation results show the performance of the proposed algorithms and suggest that the heuristics perform near optimal in low shadowing environments
BibTeX
@inproceedings{douik2015coordinated,
  author = {Ahmed Douik and Hayssam Dahrouj and Tareq Y. Al-Naffouri and Mohamed-Slim Alouini},
  title = {{Coordinated Scheduling for the Downlink of Cloud Radio-Access Networks}},
  booktitle = {ICC},
  year = {2015},
  url = {https://openreview.net/forum?id=rHys0rS7v9S},
}
Figure