Link Scheduling using Graph Neural Networks

Zhongyuan Zhao, Gunjan Verma, Chirag Rao, Ananthram Swami, Santiago Segarra

Abstract

Efficient scheduling of transmissions is a key problem in wireless networks. The main challenge stems from the fact that optimal link scheduling involves solving a maximum weighted independent set (MWIS) problem, which is known to be NP-hard. In practical schedulers, centralized and distributed greedy heuristics are commonly used to approximately solve the MWIS problem. However, most of these greedy heuristics ignore important topological information of the wireless network. To overcome this limitation, we propose fast heuristics based on graph convolutional networks (GCNs) that can be implemented in centralized and distributed manners. Our centralized heuristic is based on tree search guided by a GCN and 1-step rollout. In our distributed MWIS solver, a GCN generates topology-aware node embeddings that are combined with per-link utilities before invoking a distributed greedy solver. Moreover, a novel reinforcement learning scheme is developed to train the GCN in a non-differentiable pipeline. Test results on medium-sized wireless networks show that our centralized heuristic can reach a near-optimal solution quickly, and our distributed heuristic based on a shallow GCN can reduce by nearly half the suboptimality gap of the distributed greedy solver with minimal increase in complexity. The proposed schedulers also exhibit good generalizability across graph and weight distributions.

Introduction

In wireless multihop networks, simultaneous transmissions on nearby links using the same frequency lead to interference and data loss. Link scheduling aims to determine an optimal set of non-interfering links to activate at any given time to maximize total network utility. This problem is mathematically equivalent to finding the Maximum Weighted Independent Set (MWIS) on a conflict graph, where nodes represent links and edges represent interference.

Since MWIS is NP-hard, existing systems typically use greedy heuristics. However, these methods are "topology-blind," often selecting high-weight links that block numerous other beneficial transmissions. This paper proposes using Graph Convolutional Networks (GCNs) to incorporate network topology into scheduling decisions.

Proposed Architectures

The authors introduce two GCN-based frameworks tailored for different network environments:

Centralized Scheduling (GCN-CRS)

GCN-CRS (Centralized Rollout Search) utilizes a GCN to guide a tree search process. The GCN predicts the probability of a node being part of the optimal independent set. To maintain computational efficiency, the search is augmented with a "1-step rollout"—a fast heuristic that estimates the value of future states. This allows the scheduler to find near-optimal solutions without the exponential complexity of exhaustive search.

Centralized GCN-CRS architecture using tree search guided by GCN predictions.

Distributed Scheduling (GCN-LGS)

For ad-hoc networks lacking a central controller, GCN-LGS (Local Greedy Solver) is proposed. Each node employs a local GCN to generate a topology-aware embedding ($z$). This embedding acts as a scaling factor for the node's raw utility ($u$), resulting in a new weight ($w = z \cdot u$). This mechanism effectively penalizes links in high-interference areas and prioritizes those in "quiet" regions. A standard Local Greedy Solver then operates on these modified weights.

Distributed GCN-LGS architecture where GCN generates topology-aware node embeddings.

Training via Reinforcement Learning

A significant challenge in training these models is that the greedy solvers are non-differentiable. To address this, the authors developed a custom Reinforcement Learning (RL) scheme using a deterministic policy gradient. The GCN is rewarded based on the performance improvement of its output relative to a standard greedy baseline.

Evaluation and Results

The models were tested on synthetic random graphs (Erdős-Rényi and Barabási-Albert) and realistic wireless simulations with Poisson traffic and fading.

Key findings include:

  • Performance Gains: The distributed GCN-LGS reduced the suboptimality gap of traditional greedy solvers by approximately 50%.
  • Efficiency: Centralized GCN-CRS achieved approximation ratios exceeding 0.98 significantly faster than prior GNN-based search methods.
  • Generalization: Models trained on simple random graphs generalized well to complex, larger-scale topologies, indicating that the GCN successfully learns fundamental geometric interference patterns.
  • Network Stability: In dynamic simulations, GCN-based scheduling significantly reduced average queue lengths compared to traditional baselines.

Conclusion

By integrating GCNs into link scheduling, this work demonstrates that topology-aware heuristics can significantly outperform traditional greedy methods. The proposed solutions offer a balance between optimality and real-time feasibility, with the distributed approach requiring only shallow GCNs to minimize communication overhead. Future research will explore non-orthogonal channels and online adaptation to dynamic network conditions.

Summary updated

Abstract

Efficient scheduling of transmissions is a key problem in wireless networks. The main challenge stems from the fact that optimal link scheduling involves solving a maximum weighted independent set (MWIS) problem, which is known to be NP-hard. In practical schedulers, centralized and distributed greedy heuristics are commonly used to approximately solve the MWIS problem. However, most of these greedy heuristics ignore important topological information of the wireless network. To overcome this limitation, we propose fast heuristics based on graph convolutional networks (GCNs) that can be implemented in centralized and distributed manners. Our centralized heuristic is based on tree search guided by a GCN and 1-step rollout. In our distributed MWIS solver, a GCN generates topology-aware node embeddings that are combined with per-link utilities before invoking a distributed greedy solver. Moreover, a novel reinforcement learning scheme is developed to train the GCN in a non-differentiable pipeline. Test results on medium-sized wireless networks show that our centralized heuristic can reach a near-optimal solution quickly, and our distributed heuristic based on a shallow GCN can reduce by nearly half the suboptimality gap of the distributed greedy solver with minimal increase in complexity. The proposed schedulers also exhibit good generalizability across graph and weight distributions.
BibTeX
@article{zhao2023link,
  author = {Zhongyuan Zhao and Gunjan Verma and Chirag Rao and Ananthram Swami and Santiago Segarra},
  title = {{Link Scheduling using Graph Neural Networks}},
  journal = {IEEE Trans. Wireless Communications},
  year = {2023},
  url = {https://openreview.net/forum?id=CNyRHT5cWe},
}
Figure