Delay-aware Backpressure Routing Using Graph Neural Networks
This work addresses delay reduction in routing for wireless multi-hop networks, offering an incremental improvement over existing biased backpressure algorithms.
The paper tackled the problem of poor delay performance in classical backpressure routing for wireless multi-hop networks by introducing a throughput-optimal biased backpressure algorithm that uses a graph neural network to predict link duty cycle for bias, resulting in improved delay performance compared to classical and existing bias-based methods while being adaptive to interference density.
We propose a throughput-optimal biased backpressure (BP) algorithm for routing, where the bias is learned through a graph neural network that seeks to minimize end-to-end delay. Classical BP routing provides a simple yet powerful distributed solution for resource allocation in wireless multi-hop networks but has poor delay performance. A low-cost approach to improve this delay performance is to favor shorter paths by incorporating pre-defined biases in the BP computation, such as a bias based on the shortest path (hop) distance to the destination. In this work, we improve upon the widely-used metric of hop distance (and its variants) for the shortest path bias by introducing a bias based on the link duty cycle, which we predict using a graph convolutional neural network. Numerical results show that our approach can improve the delay performance compared to classical BP and existing BP alternatives based on pre-defined bias while being adaptive to interference density. In terms of complexity, our distributed implementation only introduces a one-time overhead (linear in the number of devices in the network) compared to classical BP, and a constant overhead compared to the lowest-complexity existing bias-based BP algorithms.