Opportunistic routing in communications networks via learnable state-augmented policies

This paper addresses the challenge of packet-based information routing in large-scale communication networks. The problem is framed as a constrained statistical learning task, where each network node operates using only local information. Opportunistic routing exploits the broadcast nature of wireless communication to dynamically select optimal forwarding nodes, enabling the information to reach the destination through multiple relay nodes simultaneously. To solve this, we propose a State Augmentation (SA) based distributed optimization approach aimed at maximizing the total information handled by the source nodes in the network. The problem formulation leverages Graph Neural Networks (GNNs), which perform graph convolutions based on the topological connections between network nodes. Using an unsupervised learning paradigm, we extract routing policies from the GNN architecture, enabling optimal decisions for source nodes across various flows. Through extensive simulation studies on random graphs, the proposed state-augmented GNN reduces queue lengths by atleast 20% compared to dual-descent and ExOR baselines while maintaining comparable network utility. The approach is further validated on a wireless ad hoc testbed with upto 10 nodes and demonstrates the robustness and transferability of GNNs without any re-training.