Distributed Scheduling using Graph Neural Networks
This work provides an incremental improvement for wireless network designers seeking more efficient distributed scheduling algorithms.
This paper tackles the problem of distributed scheduling in wireless networks, which is equivalent to solving the NP-hard Maximum Weighted Independent Set (MWIS) problem. The authors propose a Graph Neural Network (GNN)-based approach that reduces the suboptimality gap of distributed greedy solvers by half in small to medium-sized networks.
A fundamental problem in the design of wireless networks is to efficiently schedule transmission in a distributed manner. The main challenge stems from the fact that optimal link scheduling involves solving a maximum weighted independent set (MWIS) problem, which is NP-hard. For practical link scheduling schemes, distributed greedy approaches are commonly used to approximate the solution of the MWIS problem. However, these greedy schemes mostly ignore important topological information of the wireless networks. To overcome this limitation, we propose a distributed MWIS solver based on graph convolutional networks (GCNs). In a nutshell, a trainable GCN module learns topology-aware node embeddings that are combined with the network weights before calling a greedy solver. In small- to middle-sized wireless networks with tens of links, even a shallow GCN-based MWIS scheduler can leverage the topological information of the graph to reduce in half the suboptimality gap of the distributed greedy solver with good generalizability across graphs and minimal increase in complexity.