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.

本文提出了一种基于图卷积网络（GCN）的快速启发式调度策略，该策略可在集中式和分布式环境下实现。采用树搜索和 GCN 指导的一步展开的中心式启发式策略能快速的达到接近最优的解，基于浅层 GCN 的分布式启发式策略能减少近 50％的子最优解差距，且策略具有较好的推广性能。