Link Scheduling using Graph Neural Networks

• URL: http://arxiv.org/abs/2109.05536v1
• Date: Sun, 12 Sep 2021 15:19:59 GMT
• Title: Link Scheduling using Graph Neural Networks
• Authors: Zhongyuan Zhao, Gunjan Verma, Chirag Rao, Ananthram Swami, Santiago Segarra
• Abstract summary: Efficient scheduling of transmissions is a key problem in wireless networks. We propose fast topological convolutional networks (GCNs) that can be implemented in centralized and distributed manners. Test results on medium-sized wireless networks show that a GCN-based centralized MWIS solver can reach a near-optimal solution quickly.
• Score: 28.835515501826546
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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. For practical link scheduling schemes, centralized and distributed greedy heuristics are commonly used to approximate the solution to the MWIS problem. However, these greedy schemes mostly 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 MWIS solver is based on tree search guided by a trainable GCN module and 1-step rollout. In our distributed MWIS solver, a trainable GCN module learns topology-aware node embeddings that are combined with the network weights before calling a distributed greedy solver. Test results on medium-sized wireless networks show that a GCN-based centralized MWIS solver can reach a near-optimal solution quickly. Moreover, we demonstrate that a shallow GCN-based distributed MWIS scheduler can reduce by nearly half the suboptimality gap of the distributed greedy solver with minimal increase in complexity. The proposed scheduling solutions also exhibit good generalizability across graph and weight distributions.

Related papers

• Decentralized Optimization in Time-Varying Networks with Arbitrary Delays [22.40154714677385]
  We consider a decentralized optimization problem for networks affected by communication delays. Examples of such networks include collaborative machine learning, sensor networks, and multi-agent systems. To mimic communication delays, we add virtual non-computing nodes to the network, resulting in directed graphs.
  arXiv  Detail & Related papers  (2024-05-29T20:51:38Z)
• Flex-Net: A Graph Neural Network Approach to Resource Management in Flexible Duplex Networks [11.89735327420275]
  This work investigates the sum-rate of flexible networks without static time scheduling. Motivated by the recent success of Graph Networks Networks (GNNs) in solving NP-hard wireless resource management problems, we propose a novel GNN architecture, named Flex-Net.
  arXiv  Detail & Related papers  (2023-01-20T12:49:21Z)
• State-Augmented Learnable Algorithms for Resource Management in Wireless Networks [124.89036526192268]
  We propose a state-augmented algorithm for solving resource management problems in wireless networks. We show that the proposed algorithm leads to feasible and near-optimal RRM decisions.
  arXiv  Detail & Related papers  (2022-07-05T18:02:54Z)
• Distributed Link Sparsification for Scalable Scheduling Using Graph Neural Networks [37.84368235950714]
  We propose a distributed scheme for link sparsification with graph convolutional networks (GCNs) In medium-sized wireless networks, our proposed sparse scheduler beats threshold-based sparsification policies by retaining almost $70%$ of the total capacity achieved by a greedy scheduler.
  arXiv  Detail & Related papers  (2022-03-27T16:02:12Z)
• Learning Resilient Radio Resource Management Policies with Graph Neural Networks [124.89036526192268]
  We formulate a resilient radio resource management problem with per-user minimum-capacity constraints. We show that we can parameterize the user selection and power control policies using a finite set of parameters. Thanks to such adaptation, our proposed method achieves a superior tradeoff between the average rate and the 5th percentile rate.
  arXiv  Detail & Related papers  (2022-03-07T19:40:39Z)
• Learning Autonomy in Management of Wireless Random Networks [102.02142856863563]
  This paper presents a machine learning strategy that tackles a distributed optimization task in a wireless network with an arbitrary number of randomly interconnected nodes. We develop a flexible deep neural network formalism termed distributed message-passing neural network (DMPNN) with forward and backward computations independent of the network topology.
  arXiv  Detail & Related papers  (2021-06-15T09:03:28Z)
• Decentralized Control with Graph Neural Networks [147.84766857793247]
  We propose a novel framework using graph neural networks (GNNs) to learn decentralized controllers. GNNs are well-suited for the task since they are naturally distributed architectures and exhibit good scalability and transferability properties. The problems of flocking and multi-agent path planning are explored to illustrate the potential of GNNs in learning decentralized controllers.
  arXiv  Detail & Related papers  (2020-12-29T18:59:14Z)
• Distributed Scheduling using Graph Neural Networks [38.74504118887024]
  A fundamental problem in the design of wireless networks is to efficiently schedule transmission in a distributed manner. 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.
  arXiv  Detail & Related papers  (2020-11-18T18:00:45Z)
• Graph Neural Networks for Scalable Radio Resource Management: Architecture Design and Theoretical Analysis [31.372548374969387]
  We propose to apply graph neural networks (GNNs) to solve large-scale radio resource management problems. The proposed method is highly scalable and can solve the beamforming problem in an interference channel with $1000$ transceiver pairs within $6$ milliseconds on a single GPU.
  arXiv  Detail & Related papers  (2020-07-15T11:43:32Z)
• Resource Allocation via Graph Neural Networks in Free Space Optical Fronthaul Networks [119.81868223344173]
  This paper investigates the optimal resource allocation in free space optical (FSO) fronthaul networks. We consider the graph neural network (GNN) for the policy parameterization to exploit the FSO network structure. The primal-dual learning algorithm is developed to train the GNN in a model-free manner, where the knowledge of system models is not required.
  arXiv  Detail & Related papers  (2020-06-26T14:20:48Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.