Opportunistic routing in communications networks via learnable state-augmented policies

1 Introduction

The rapid growth of digital communications and smart infrastructures has led to an increase in demand for reliable, high bandwidth wireless systems. This introduced challenges in scalability, robustness, and QoS, particularly in applications like IoT, autonomous transportation, and massive MIMO systems. Traditional networks struggle to meet these demands, but Artificial Intelligence (AI), especially machine learning (ML), offers promising solutions to previously unattainable communication problems Mao et al. (2018). As wireless networks face growing traffic, uncertain conditions, and risks of packet loss and delays Rozner et al. (2009), efficient routing becomes critical. Conventional routing relies on predefined paths and standardized protocols to ensure packet delivery Medhi and Ramasamy (2018), whereas opportunistic routing (OR) exploits the broadcast nature of wireless media to enable multiple dynamic paths Biswas and Morris (2005). In recent times, opportunistic routing (OR) has become prevalent in wireless networks as it benefits especially in mobile scenarios like VANETs and MANETs. However, OR’s reliance on flooding and sensitivity to topology changes incur high control overhead Kaviani et al. (2023). To tackle these issues, this study proposes a deep learning-based solution using Graph Neural Networks (GNNs) to jointly optimize routing and scheduling in packet-based opportunistic networks. Even though OR is frequently motivated by dynamic channels like MANET and VANETs, its major advantage lies in its use of the broadcast nature of wireless channels, rather than the lack of knowledge about the network topology. Even in fixed topology wireless networks, link success or failure can vary significantly due to fading, interference, and other external factors, which make OR forwarding approaches beneficial compared to conventional routing schemes.

Communication networks incorporate advanced mechanisms such as radio resource allocation, congestion management, and queue management, which significantly affect system performance. Numerous studies explored these challenges through stochastic network utility maximization (NUM) Liu et al. (2015), traffic engineering and routing Xia et al. (2018); Zargham et al. (2013); Gao et al. (2022); Das et al. (2025a), radio resource management (RRM) Eisen and Ribeiro (2020); NaderiAlizadeh et al. (2023); NaderiAlizadeh et al. (2022), and link scheduling Xia and Wang (2017); Xia (2014). These works typically model the problems as constrained optimization tasks involving a utility function while considering the stochastic nature of user traffic and variations in wireless channel conditions. Machine learning techniques have been widely leveraged in diverse signal processing domains, including wireless resource optimization Mao et al. (2018), biometric recognition Saleem et al. (2020), and image restoration tasks Khan et al. (2021). These applications demonstrate the versatility of data-driven models in handling high-dimensional structured signals under complex constraints. Mao et al. provide an in-depth analysis of how ML techniques can enhance network operations, including resource allocation, path optimization, traffic management, and data compression Mao et al. (2018). Of late supervised learning has proven effective at mimicking system heuristics using training datasets Sun et al. (2017); Xu et al. (2019); Van Chien et al. (2019), unfortunately it requires constant data collection and may not always surpass heuristic approaches. In contrast, this paper employs unsupervised learning, treating the network optimization as a statistical regression problem to solve the problem directly without depending on training sets, which can outperform heuristic solutions Eisen and Ribeiro (2020); Meng et al. (2020); Cui et al. (2019). Earlier, fully connected neural networks (FCNN) were widely adopted due to their universal approximation ability Sun et al. (2017); Eisen and Ribeiro (2020), followed by convolutional neural networks (CNN) for their scalability in time and space. However, CNNs struggle on large-scale networks and lack generalization due to permutation invariance Zhang et al. (2023); Shen et al. (2022). This motivates us to use GNN for communication scenarios, which offer scalability, transferability and permutation equivariance Bernárdez et al. (2023); Henaff et al. (2015); Gama et al. (2018).

This paper addresses the challenge of network utility maximization under multiple constraints, drawing inspiration from methods presented in prior studies Eisen and Ribeiro (2020); NaderiAlizadeh et al. (2023); NaderiAlizadeh et al. (2022); Xia et al. (2018); Zargham et al. (2013); Uslu et al. (2024); Xia (2014). Our focus is on improving packet-based routing and scheduling to enhance the average performance of network nodes, ensuring stable queue lengths over time and maintaining node stability. We desire to achieve queue length stability because unbounded queue growth can lead to persistent congestion, which in turn can result in large end-to-end delays, buffer overflow and potential packet drops. In our setting, stability refers to maintaining the per-node per-flow queue bounded over time and avoiding backlog build-up. The optimization framework requires strict adherence to constraints to preserve system feasibility. These types of problems are often addressed by transitioning to the Lagrangian domain, in which one single objective function is optimized with respect to primal variables while being minimized over dual variables. The primal variables are associated with the main objective, whereas the dual variables correspond to the constraints of the network optimization problem. Although primal-dual methods can theoretically provide optimal solutions, in practice they suffer from slow convergence and can produce infeasible intermediate iterates Bertsekas and Tsitsiklis (2015); Chatzipanagiotis and Zavlanos (2017). Moreover, when the underlying problem is nonconvex or policy parameterized, challenges such as residual duality gaps and constraint violation remain significant obstacles Das et al. (2025a); NaderiAlizadeh et al. (2022). To address these challenges, we propose a constrained learning approach based on state augmentation, which incorporates dual variables to capture the extent of constraint satisfaction or violation over time Calvo-Fullana et al. (2021). In this framework, we enhance the standard network state by appending dual multipliers at every time step, using them as continuous inputs for the network routing policy. This integration of dual multipliers into the network routing policy facilitates the model to adjust its decisions in response to real-time channel conditions while ensuring that the system adheres to the imposed constraints.

Unlike our previous work in Das et al. (2025a), which is limited to routing in wired networks, this work extends the problem in several fundamental directions ¹ . First, we adapt the routing formulation to opportunistic wireless networks by using two coupled variables representing transmission probabilities as well as packet acceptance on broadcast reception. Second, the wireless setting incorporates stochastic link success probabilities derived from packet delivery ratio (PDR) measurements and queue dynamics under broadcast-based reception, capturing the opportunistic nature of wireless channels. Third, this paper validates our approach using traditional simulation, on real-world network topologies as well as a physical Raspberry Pi-based testbed for wireless mesh networks. Recent work has explored learning based approaches for routing optimization in different networking settings Das et al. (2025a); Bernárdez et al. (2023). Most of the machine learning frameworks directly learn forwarding heuristics or optimize long-term rewards, whereas our framework leverages dual variables arising from constrained network optimization directly into the instantaneous channel state. This state-augmented mechanism enables the GNN to mimic the behavior of the Method of Multipliers, which yields routing decisions that are near-optimal and satisfy constraints after a finite iterations while avoiding long convergence horizons. Moreover, direct approaches that match our settings of opportunistic wireless routing, combined with a distributed, state-augmented GNN policy and validated on a real-time testbed, are limited. In this work, we focus on fixed topology wireless systems to study the advantages of learning opportunistic routing and scheduling policies under stochastic link conditions. To provide a better analytical positioning of the proposed framework, Table 1 summarizes representative routing approaches with respect to learning architecture, constraint handling, and validation characteristics. We can summarize our contributions to the paper as below:

• We perform opportunistic routing using GNN to learn efficient opportunistic routing strategies for wireless communication networks of varying sizes and validated them on real time wireless ad hoc networks.
• We leverage the GNNs to implement decentralized communication networks of varying sizes by mimicking the Method of Multipliers (MoM) which is faster than standard dual descent methods.
• We utilize State Augmentation methods to learn near-optimal solutions with a finite number of iterations unlike other iterative algorithms with longer convergence time.
• We validated the trained GNN models on real time wireless ad hoc networks which demonstrated excellent transferability of the GNN models.

TABLE 1. Taxonomy and positioning of related routing approaches.

Subsequent sections of the paper are organized as follows. Section 2 introduces the problem, where we frame it as a network utility optimization problem subject to multiple constraints. Sections 3 and 4 provide an overview of standard optimization techniques. Section 5 details the process of parameterizing the learning algorithm using GNNs. Section 6 explores the key concepts of the augmented Lagrangian method and GNN learning, highlighting their relevance to the problem. Section 7 outlines the proposed state-augmented algorithm for optimizing routing decisions in the network. The simulation results and related discussions are presented in Section 8 and Section 9. Finally we conclude the article in Section 10.

2 Problem statement

Let’s represent the communication network state as a graph G = ( V, E ). Here V denotes the set of communicating nodes, while E ⊆ V × V represents the edges connecting these nodes. The neighborhood of a node i is defined as N i = { j ∈ V | ( i , j ) ∈ E }, which includes all nodes j that have direct communication links with i. Information packets are exchanged between nodes across various flows, with K denoting the set of flows. Each flow k ∈ K has a designated destination node o k ∈ V. For a particular time instant t, a node i ≠ o k produces a certain number of random packets, a 0 i k ( t ), intended for the destination o k. These random variables a 0 i k ( t ) are assumed to be independent and identically distributed (iid) over time, with their mean value given by E [ a 0 i k ( t ) ] = a 0 i k. Considering the link state conditions, the probability that node i successfully decodes a packet sent by node j is represented by R i j, an element of the channel state probability matrix R ∈ R | V | × | V |, which captures channel state probability between pairs of communicating nodes.

Since we perform OR by taking advantage of the broadcast nature of the wireless medium, we consider two different routing variables. We consider the first routing variable T i k, to denote the probability that node i in the network decides to transmit a packet to its neighbors over flow k. Once the broadcasted packets arrive at node i for flow k, the probability that node i decides to keep the packet from node j be denoted using the second routing variable as K i j k. Thus at a given time instant and flow k, the number of packets received from node j to node i can be given as the product of the above probabilities times the number of packets generated at node j, which is T j k ( t ) R i j ( t ) K i j k ( t ) a 0 j k ( t ). Each node i can transmit a fixed number of packets based on its capacity, denoted as C i. The balance between the total packets received, which include a 0 i k ( t ) and ∑ j ∈ n i T j k ( t ) R i j ( t ) K i j k ( t ) a 0 j k ( t ), and the total packets transmitted, T i k ( t ) C i, determines the change in the local queue. If the balance is positive, it is added to the queue; if negative, packets are subtracted. Consequently, the queue length for flow k at node i, denoted by q i k ( t ), evolves iteratively based on the equation below:Here, the projection onto the non-negative orthant ensures that the queue length remains non-negative. It is important to note that Equation 1 applies to all nodes i ≠ o k, as the packets that reach their destination o k are removed from the system. The proposed routing policy can be implemented in a fully distributed manner. At time t, every node i requires only: (i) its locally generated packets a 0 i k ( t ), (ii) link state information to its one-hop neighbors { R i j ( t ) : j ∈ N i }, generally obtained from conventional PHY/MAC-layer measurements such as PDR/RSSI/SNR, acknowledgment (ACK) statistics, and (iii) its local dual variables μ i k, can be updated using locally available constraint residuals.

q i k t + 1 = q i k t + a 0 i k t + ∑ j ∈ n i T j k t R i j t K i j k t a 0 j k t − T i k t C i + . (1)

2.1 Problem design

This study examines a communication network over a sequence of time instants t ∈ { 0,1 , . , T − 1 }. At each time instant t, let’s denote the network state, specifically the set of channel probabilities, as R t ∈ R. For any particular network state, let us denote the routing decision vectors as p ( R t ) and b ( R t ). Here p : R → R n × n × F maps the network state to routing decisions regarding acceptance of the packets at a given node. On the other hand, b : R → R n × F maps the network state to routing decisions regarding the transmission of packets from a particular node. These routing decisions influence the network’s performance which can be expressed as a vector f ( R t , p ( R t ) , b ( R t ) ) ∈ R b, with f : R × R n × n × F × R n × F → R b being the network’s performance function. Throughout, n = | V | is the number of nodes, F = | K | is the number of flows, and R t is the (channel) state matrix whose entry R i j ( t ) denotes the link success probability from node i to node j.

An auxiliary optimization variable, let’s say a i k ( t ) ≥ a 0 i k ( t ) is introduced to maximize packet generation for flow k at node i. Here, a 0 i k ( t ) represents the true number of packets in the network at time t, which is essential for updating the length of the queues in the network, as described in Equation 1. Following the general framework in NaderiAlizadeh et al. (2022); Das et al. (2025a), “a concave utility function”, U : R x → R along with a given number of constraints g : R x → R y are considered. The network routing formulation is now formulated as:

max p R t , b R t t = 0 T − 1 U 1 T ∑ t = 0 T − 1 f R t , p R t , b R t (2a)

s.t. g 1 T ∑ t = 0 T − 1 f R t , p R t , b R t ≥ 0 . (2b)

Here both the objective function Equation (2a) as well as the set of constraints Equation (2b) are established on the ergodic average of the system performance; 1 T ∑ t = 0 T − 1 f ( R t , p ( R t ) , b ( R t ) ). Thus the goal of the network routing algorithm is to find out the optimal routing decision vectors p ( R t ) and b ( R t ) for any given network state R t ∈ R.

In order to address the network optimization problem at hand, we begin from the network utility function which aims to maximize the information packets at every node i and across all flows k. Now we can formulate the concave objective function as:

U 1 T ∑ t = 0 T − 1 f R t , p R t , b R t = ∑ k ∈ K ∑ i ∈ V log 1 T ∑ t = 0 T − 1 a i k t . (3)

The optimization problem includes three types of constraints based on the current network state:

• Routing Constraints: The total packets received and local packets a i k ( t ) at node i must not exceed the total transmitted packets from node i:

a i k t + ∑ j ∈ n i T j k t R i j t K i j k t a j k t ≤ T i k t C i . (4)

• 2. Minimum Constraints: Each node i must maintain a minimum number of local packets for faithful transmission to other communicating nodes in the network:

a i k t ≥ a 0 i k t . (5)

• 3. Capacity Constraints: This defines the maximum probability of transmitting packets from a node, i.e., the total sum of probabilities of transmitted packets from node i can not exceed the maximum probability which is 1:

∑ k ∈ K T i k t ≤ 1 . (6)

By incorporating these constraints Equations 3-6 into the defined formula in Equation 2a, the network utility maximization problem can be expressed below:

max a i k t , T i k t , K i j k t t = 0 T − 1 ∑ k ∈ K ∑ i ∈ V log 1 T ∑ t = 0 T − 1 a i k t (7a)

T i k t C i − a i k t − ∑ j ∈ n i T j k t R i j t K i j k t a j k t ≥ 0 (7b)

a i k t − a 0 i k t ≥ 0 (7c)

∑ k ∈ K T i k t ≤ 1 (7d)

3 Gradient based solutions for network routing: dual domain

Given that the network maximization challenge in Equation 7a consists of a concave utility function, the standardized gradient-based dual descent algorithm is a desirable approach. We consider a set of dual multipliers (also called Lagrangian multipliers), which are nonnegative variables introduced to penalize constraint violations. These Lagrangian duals, μ ∈ R + c, are associated with the constraint Equation 7b. Furthermore, the constraints Equations 7c, d are kept implicit, and for simplicity in our analysis, we set the total time, T = 1. The Lagrangian can now be formulated as Equation 8:We can maximize the above Lagrangian in Equation 8 using a standardized gradient-based algorithm. Specifically, a primal-dual learning algorithm, a variant of dual-descent algorithm, aims at maximizing L over the primal variables a, T ² and K, while minimizing over the dual multipliers μ concurrently Equation 9.For each iteration m ∈ { 1,2 , . , M }, the primary variables are updated as per the following equations in Equation 10.

L a , T , K , μ = ∑ i ∑ k log a i k + ∑ i × ∑ k μ i k T i k C i − a i k − ∑ j ∈ n i T j k R i j K i j k a j k . (8)

L * = min μ max a , T , K L a , T , K , μ (9)

a i k m + 1 = a i k m + γ ϕ ∇ ϕ L a , T , K , μ , (10a)

T i k m + 1 = T i k m + γ ϕ ∇ ϕ L a , T , K , μ , (10b)

K i j k m + 1 = K i j k m + γ ϕ ∇ ϕ L a , T , K , μ . (10c)

The gradient descent update of the dual variable is given by μ m + 1 = μ m − γ μ ∇ ϕ L ( a , T , K , μ ). Due to the linearity of the Lagrangian with respect tp μ, its gradient is much easier to calculate, allowing for recursive updates of μ as Equation 11:Here, [ . ] + generally expressed as [ d ] + = max ( d , 0 ), denotes projection onto the non-negative orthant. The constants γ μ and γ ϕ are the learning rates for the dual variable μ and the primal variables (a, T, K), respectively. Introducing dual variables into the Lagrangian enables the algorithm to achieve near-optimal and feasible results for this dual relaxation over an adequate number of iterations. Unlike standard primal-dual methods that may yield infeasible decisions, this method can guarantee feasibility of the routing algorithm in Equations 10, 11. However, its main limitation is slow convergence, urging us to explore the Method of Multipliers in the next section.

μ m + 1 = μ m − γ μ T i k C i − a i k − ∑ j ∈ n i T j k R i j K i j k a j k + . (11)

4 Solution via method of multipliers (MOM)

While addressing any network utility optimization within the framework of Lagrangian dual, the dual descent method is often a sensible starting point for finding an optimal solution. However, this method has well documented disadvantages, which includes its very slow rate of convergence and the requirement for a strictly convex objective function Bertsekas and Tsitsiklis (2015). Thus, we resort to the Augmented Lagrangian, also known as MoM, which is a superior alternative for mitigating the shortcomings of the dual descent method similar to our previous work in Das et al. (2025a). The algorithm begins by converting the inequality constraint in Equation 7b into an equality constraint, as follows Equation 12:where z i k ≥ 0 is an auxiliary variable introduced to help with the inequality. The Augmented Lagrangian of the above network utility optimization in Equation 7a is hence formulated as Equation 13:where ρ > 0 is the penalty factor while μ ∈ R + n × F is the dual variable corresponding to the routing constraint in Equation 7b. Note that constraints Equations 7c, d are implicitly enforced by ensuring that the solutions of the given optimization problem satisfy the constraints inherently. This penalty method tackles the above network optimization by iteratively varying μ and ρ Equation 14a.

T i k t C i − a i k t − ∑ j ∈ n i T j k t R i j t K i j k t a j k t − z i k t = 0 , (12)

L ρ a , T , K , z , μ = ∑ k ∈ K ∑ i ∈ V 1 T ∑ t = 0 T − 1 log a i k + ∑ k ∈ K ∑ i ∈ V 1 T ∑ t = 0 T − 1 × { μ i k T i k C i − a i k − ∑ j ∈ n i T j k R i j K i j k a j k − z i k + ρ 2 ‖ T i k C i − a i k − ∑ j ∈ n i T j k R i j K i j k a j k − z i k ‖ 2 } , (13)

a m + 1 , T m + 1 , K m + 1 , z m + 1 = arg max a , T , K , z L ρ a , T , K , z , μ m (14a)

μ m + 1 = arg min ν L ρ a m + 1 , T m + 1 , K m + 1 , z m + 1 , μ m . (14b)

As we observe that L ρ ( a , T , K , μ ) is linear in μ, we can perform the minimization step for μ from Equation 14b via the gradient descent Equation 15:

μ i k m + 1 = μ i k m − ρ m T i k C i − ∑ j ∈ n i T j k R i j K i j k a j k − a i k m + . (15)

The MoM algorithm is guaranteed to converge under specific conditions, particularly once the maximization operation across z outputs a optimal solution irrespective of its initial value Chatzipanagiotis and Zavlanos (2017). Despite its effectiveness, the primary limitation of MoM is the loss of decomposability, which can hinder its application in large-scale distributed systems. This challenge can be mitigated using a variant of MoM known as the Alternating Direction Method of Multipliers (ADMM). However, for real-time applications, a more versatile framework is required to address diverse scenarios effectively. To this end, we propose employing GNNs so as to approximate the solutions given by MoM, thereby achieve possibly better performance compared to conventional optimization methods.

5 Network routing optimization using graph neural networks parameterization

The optimization in Equation 7a is infinite-dimensional, as it requires determining a i k and r i j k for all possible channel states R t and inputs a 0 i k ( t ), which is generally infeasible. Instead, we propose a GNN-based parameterized model that maps R t and a 0 i k ( t ) to decisions a i k ( t ), T i k ( t ), and K i j k ( t ). GNNs are neural architectures designed for graph-structured data Wu et al. (2020), offering permutation equivariance, scalability, and transferability across network types Eisen and Ribeiro (2020); NaderiAlizadeh et al. (2023); NaderiAlizadeh et al. (2022); Lee et al. (2020); Shen et al. (2019). In the context of our network optimization problem, the network can be denoted by graph G = ( V , E , z t , w t ) at a particular time instant t. Here V = [ 1,2 , … , n ] denotes the set of graph nodes where every node corresponds to a communicating node in the network while E ⊆ V × V represents the set of directed edges between these nodes. z t are the initial node features and E → R maps each edge to the corresponding weight at a given time t, where the weight between a set of 2 interacting nodes is the normalized transmission probability of delivering packets in our optimization problem, i.e., w i j ( t ) = R i j ( t ).

Now considering a single time step t and slightly abusing the notation, once can treat the channel probability matrix R t ∈ R n × n to be an adjacency matrix of the network graph, that establishes connections between node i and node j. In this context, initial node feature, z t serves as the signal associated with the nodes of the network, i = 1 , . , n. Now the GNNs serve as the graph convolutional filter by processing z t ∈ R n with the graph structure represented by R t. Since we are dealing with a filter, let us denote h : = { h 0 , … , h K − 1 } to represent the set of K filter coefficients. The function ϕ ( R t ) is defined as the graph filter, and it is basically a polynomial applied linearly to input signal z t on the graph representation Sandryhaila and Moura (2014). The outcome of this convolution process can be expressed as Equation 16:It can be noted observed that the filter ϕ ( R t ) functions as a linear shift-invariant filter, hence the graph R t is referred to as Graph Shift Operator (GSO). In a GNN, the input node along with the edge features are processed through L layers where the node features from the previous layer l − 1, denoted as Y t l − 1 ∈ R m × F l − 1, are transformed into the node features for the current layer l, denoted as Y t l ∈ R m × F l. The filter at layer l is then fed to the output of layer l − 1 to generate the current layer feature y t l, that is now expressed in Equation 17 as:Subsequently, a pointwise non-linearity σ is then applied to the intermediate features to produce the output of the l t h layer:

y t = ϕ R t z t = ∑ k = 0 K − 1 h k R t k z t . (16)

y t l = ϕ l R t z t l − 1 = ∑ k = 0 K l − 1 h l k R t k z t l − 1 . (17)

z t l = σ y t l = σ ∑ k = 0 K l − 1 h l k R t k z t l − 1 . (18)

The GNN recursively applies graph convolution as in Equation 18, where non-linearity σ (e.g., ReLU, sigmoid, or absolute value Gama et al. (2018); Henaff et al. (2015)) is applied element wise at each layer. While the above equations of GNNs focused on a single graph filter, the GNN’s expressive power can be enhanced by implementing a bank of F l graph filters Eisen and Ribeiro (2020). More specifically, this approach allows for the generation of multiple features at each layer, with each feature being processed by a separate filter bank. For instance, the output from layer l − 1, comprising F l features, serves as the input for layer l and each of these features is then processed by the F l filters, ϕ l f g ( R t ). Subsequently, the intermediate feature of the l t h layer, after applying these filters, can be represented as:The expression Equation 19 delineates that layer l produces F l − 1 × F l intermediate features y t , f g l. In order to prevent the potential exponential increase of these features, they are linearly aggregated and processed through the non-linearity function defined by σ to yield output of layer l. Therefore, the output, z t l at l t h layer is expressed as:In our experiments, we use Equation 20 recurrently to generate the GNNs. The filter coefficients are compiled into the filter tensor ϕ = [ h l k f g ] l , k , f , g, now the GNN operator can be defined as Ψ ( R t , x t ; ϕ ) = z t L. Here x = z t 0 is the initial input feature to the GNN network at the first layer, i.e., l = 1. Depending on our specific algorithms discussed later, we can vary the number of input features, F 0. Thus, the output layer produces the GNN result, which is expressed as:The output of Equation 21 generates a ( n × F L ) vector, which after being multiplied to an intermediary matrix w r ∈ R F L × F L, helps in determining the packet acceptance decisions K i j k ( t ). To guarantee that the values in the routing decision matrix fall within the probabilistic range of 0–1, we process this matrix through a Softmax filter as in Equation 22 where Softmax ( d ) i = exp ( d i ) ∑ j = 1 K ⁡ exp ( d j ) for i = 1,2 , … , K and d = ( d 1 , d 2 , … , d K ) ∈ R K. To better understand the construction of the reception matrix, let Y = y out ∈ R n × F L be the node-level embeddings produced by the final GNN layer. The bilinear product Y W r Y T produces a pairwise compatibility matrix S ∈ R n × n, where each entry S i j represents the compatibility between transmitter node i and potential receiver node j. The entries corresponding to non-neighboring nodes are masked based on the adjacency defined by R t, ensuring that only one-hop neighbors are considered. A row-wise Softmax is then applied to the valid neighbor entries to obtain the reception probabilities K i j k ( t ), such that ∑ j ∈ N i K i j k ( t ) = 1.

y t , f g l = ϕ l f g R t z t , f l − 1 = ∑ k = 0 K l − 1 h l k f g R t k z t , f l − 1 . (19)

z t l = σ l ∑ f = 1 F l y t , f g l = σ l ∑ f = 1 F l ϕ l f g R t z t , f l − 1 . (20)

y out = Y t L ∈ R n × F L . (21)

p R t , x t ; ϕ = Softmax y out w r y out T , (22)

The intermediate square matrix w r, of dimensions ( F L × F L ), plays a key role in generating the final reception matrix K, which has dimensions ( n × n ). We then multiply the output of Equation 21 with another intermediary matrix w s ∈ R F L to obtain the final transmit matrix T. The product matrix is then passed through another Softmax filter Equation 23 to ascertain the values in the probabilistic range of 0–1, i.e.,

b R t , x t ; ϕ = Softmax y out w s . (23)

In a similar fashion, we determine the auxiliary packets a i k by relaying the GNN output via an additional linear layer. This involves multiplying the output to a column vector denoted by w a ∈ R F L, yielding Equation 24:The resultant output a i k ( t ) is further passed through a ReLU filter to ensure the non-negativity of the packets generated at the nodes, reflecting the fact that the number of packet cannot be negative. Note that the GNN is this study differs from our previous work Das et al. (2025a) in that it provides two decision variables for the case of OR instead of just one.

a i k t = a 0 i k t + y out w a + . (24)

6 Method of multipliers using graph neural network parameterization

In order to address the optimization challenge presented in Equation 7a, which involves the concave objective function, let’s apply the MoM. This method aims at finding the optimal solution by leveraging our GNN parameterization as outlined in the previous section. In this setup, we consider z t = a 0 i k ( t ) to be the input node feature for our GNN framework, aiming to determine optimal routing policies p ( R t , x t ; ϕ ) and b ( R t , x t ; ϕ ). By integrating the GNN parameterization expressed in Equations 21, 22, 23, we can now reformulate the parameterized network maximization problem initially mentioned in Equation 7a as:

max ϕ , w r , w s , w a U 1 T ∑ t = 0 T − 1 f R t , p R t ; ϕ , b R t ; ϕ (25a)

s . t . g 1 T ∑ t = 0 T − 1 f R t , p R t ; ϕ , b R t ; ϕ ≥ 0 . (25b)

Accordingly, the Augmented Lagrangian for the network optimization in (25) can be expressed as Equation 26:To facilitate the training of the model parameters ϕ t, we consider an iterative period T 0, representing the number of time steps between successive updates of the model parameters. Abusing the notation for time t slightly, let’s consider an iteration index m ∈ { 0,1 , … , M − 1 }, with M = ⌊ T / T 0 ⌋. The parameters of the model can now be updated as follows:Subsequently, dual variables μ can be updated recursively:

L ϕ , μ = U 1 T ∑ t = 0 T − 1 f R t , p R t ; ϕ , b R t ; ϕ + μ T g 1 T ∑ t = 0 T − 1 f R t , p R t ; ϕ , b R t ; ϕ + ρ 2 g 1 T ∑ t = 0 T − 1 f R t , p R t ; ϕ , b R t ; ϕ 2 . (26)

ϕ m = arg max ϕ ∈ Φ L ϕ , μ m . (27)

μ m + 1 = μ m − ρ g 1 T ∑ t = m T 0 m + 1 T 0 − 1 f R t , p R t ; ϕ , b R t ; ϕ + . (28)

Here ρ is the penalty parameter that denotes the learning step size for updating the dual variable. It can be observed that the updates are structured to maximize the Lagrangian L with respect to ϕ, while ensuring the dual variables μ are adjusted appropriately at each iteration. When run over a sufficiently extended series of time steps, the described routing algorithm is capable of delivering decisions, which are both feasible and nearly optimal. It is worth mentioning that conventional dual descent approaches, such as Primal-Dual algorithm, may not always ensure feasibility for the set of routing decisions because the algorithm, as outlined in Equations 27, 28, continuously adjusts the routing policy with respect to changes in the dual variables at each iteration. However, such parameterized policies often come with inherent limitations, highlighting the necessity of refining the approach to derive truly optimal routing decisions.

7 The state augmentation algorithm

As highlighted earlier, the iterative optimization in Equations 27, 28, though theoretically feasible, poses several practical bottlenecks. It requires a priori (non-causal) knowledge of the system state at t = k T 0, which is feasible during training but not during the testing or execution phase. Moreover, convergence to near-optimal performance typically requires an infinite time horizon T and this prevents conclusion after finite iterations during training. Some iterations may also fail to yield a feasible or optimal ϕ m, and recomputing parameters for each μ m incurs significant computational overhead, especially during the execution stage. To overcome this, we propose a state-augmentation routing algorithm, inspired by NaderiAlizadeh et al. (2022); Das et al. (2025a); Calvo-Fullana et al. (2021), where the current network state R t is augmented with the corresponding dual variables μ ⌊ t / T 0 ⌋. These, along with the input node features a 0 i k ( t ), are fed into a parameterized GNN model to compute routing decisions. Thus, the GNN input dimension becomes F 0 = 2. Next, let’s consider a unique parameterization to characterize the above state-augmented algorithm, in which expected routing decisions, p ( R ) and b ( R ) are expressed as p ( R , μ ; θ ) and b ( R , μ ; θ ), respectively. Here, the θ ∈ Θ represents collection of GNN filter tensors that define the state-augmented routing decisions. Figure 1 depicts the overall structure of the proposed state-augmented routing algorithm. This process begins with formulation of the augmented Lagrangian, as outlined in Equations 25a, b for a given set of dual variables μ ∈ R + c:

L μ θ = U 1 T ∑ t = 0 T − 1 f R t , p R t , μ ; θ , b R t , μ ; θ + μ T g 1 T ∑ t = 0 T − 1 f R t , p R t , μ ; θ , b R t , μ ; θ + ρ 2 g 1 T ∑ t = 0 T − 1 f R t , p R t , μ ; θ , b R t , μ ; θ 2 . (29)

After obtaining the functional values from network optimization problem in Equation 7a, the augmented Lagrangian form is Equation 30:

L μ θ = ∑ k ∑ i log 1 T ∑ t = 0 T − 1 a i k t + μ i k 1 T ∑ t = 0 T − 1 T i k t C i t − a i k t − ∑ j ∈ n i T j k t R i j t K i j k t a j k t − z i k t − ρ 2 T i k t C i t − a i k t − ∑ j ∈ n i T j k t R i j t K i j k t a j k t − z i k t 2 . (30)

Here the Lagrangian multipliers μ i k correspond to the flow constraint (Equation 7b) while and the constraints Equations 7c, d are implicitly maintained. We then consider the dual variables drawn from a probability distribution p μ. The state-augmented routing policy can now be defined as the one that maximizes the expected value of the augmented Lagrangian over the probability distribution of all parameters, i.e.,

θ * = arg max θ ∈ Θ E μ ∼ p μ L μ θ . (31)

This state-augmented policy, which is now parameterized by θ *, facilitates the search for optimal Lagrangian-maximized routing decisions p ( R , μ ; θ ) and b ( R , μ ; θ ) for each iteration of the dual variable μ = μ m. Utilizing this concept, the update for dual variable at iteration m in Equation 31 can be expressed as in Equation 32:During the execution phase, the update for the dual variable, based on the network optimization problem in Equation 7a, is calculated as:

μ m + 1 = μ m − γ μ × g 1 T 0 ∑ t = m T 0 m + 1 T 0 − 1 f R t , p R t , μ m ; θ * , b R t , μ m ; θ * + . (32)

μ i k t m + 1 = μ i k t m − γ μ [ 1 T ∑ t = 0 T − 1 T i k t C i t − a i k t − ∑ j ∈ n i T j k t R i j t K i j k t a j k t ] . (33)

The equation above facilitates simultaneous learning of a parameterized model and the derivation of the optimal state-augmented routing policy, as outlined in Equation 31. This process effectively mirrors the gradient descent steps characteristic of traditional dual descent algorithms. As shown schematically in Figure 1, the dual variables updated according to Equation 33 are incorporated into the GNN model at the subsequent time steps. This enables the routing policy to adapt to constraint violations over time. Given that the resulting routing matrices are derived from localized information processed on channel probability matrices, this operation is best interpreted within the framework of graph signal processing. Basically, the proposed state-augmented framework operates in two separate phases. The offline training focuses on maximizing the augmented Lagrangian over the sample of network states and dual variables to optimize the GNN parameters θ. The resulting parameters θ * are then saved once the training converges. Subsequently, they are utilized in the evaluation phase where the dual variables are updated iteratively according to Equation 33. No further retraining is required during implementation unless there is a substantial shift in the long-term traffic conditions or channel statistics.

7.1 Practical assumptions for state-augmentation

Algorithm 1 State-augmented routing optimization: Training phase.

Algorithm 2 State-augmented routing optimization: Execution phase.

The maximization process described in Equation 31 is required to be performed during the offline training stage. The parameters of the GNN are trained through the unsupervised learning approach, in which the Augmented Lagrangian formulation defined in Equation 29 is used as the loss function. The goal of the training procedure is to maximize the Augmented Lagrangian formulation over the sampled network states and the corresponding dual variables to optimize the routing policies while satisfying the optimization constraints. In this phase, we leverage a regular gradient ascent method to identify and learn an optimal set of model parameters, i.e., θ *. Once the training phase is completed, these parameters are generally saved for use in the execution phase. Throughout the model training stage, a batch of dual variables, denoted as { μ b } b = 1 B, is processed. They are randomly drawn from the probability distribution p μ. Therefore, the practical mode of achieving the Lagrangian maximization specified in Equation 31 can be expressed in its empirical form as Equation 34 below.Similar to optimizing the primal variable in a primal-dual learning, the optimization problem in consideration can be solved iteratively via the method of gradient ascent. We begin this process by a random initialization of the model parameters, denoted as θ 0, which are then progressively updated throughout the iterations, indexed as n = 0 , … , N train − 1. The formula for updating the parameter θ is given as,where γ θ denotes the learning rate or step size for the model parameters θ. It is worth noting that these parameters correspond to the coefficients of graph filters within our defined GNN framework. Once the model parameters are optimized using Equation 35, the GNN follows to update the primal variables { a , T , K }. After the model’s training phase is complete, we save the resulting set of optimized parameters which have reached convergence, as θ *. In order to enhance the model’s capacity to generalize to random network states, we couple each set of dual variables, { μ b } b = 0 B − 1 with a uniquely sampled sequence of network states { R b , t } t = 0 T − 1. This approach significantly helps in optimizing the model across a family of network scenarios including time varying conditions. The detailed steps of this training methodology are comprehensively presented in Algorithm 1.

θ * = arg max θ ∈ Θ 1 B ∑ b = 1 B − 1 L μ b θ (34)

θ n + 1 = θ n + γ θ B ∑ b = 1 B − 1 ∇ θ L μ b θ n , (35)

Upon the completion of the training stage, we proceed to the execution phase, during which once can update the dual variables iteratively to compute the routing decisions based on the current channel state. At the start of the execution phase, we set the dual variables to zero, θ = θ 0. For each time instant { t } t = 0 T − 1, and for a specific network state R t, the optimal network decisions are delivered by above state-augmented policies p ( R t , x ⌊ t / T 0 ⌋ ; θ * ), as determined during Algorithm 1. Next, the dual multipliers follow an update at every T 0 time step in accordance with Equation 33. We can observe that the dynamics of the dual variables in the execution phase, as expressed in Equation 33, can facilitate the amenable satisfaction of the constraints. As detailed in Algorithm 2, optimal routing decisions generated at any given instant t leads to constraint satisfaction if the dual variables get minimized. Conversely, an increase of the dual variable values indicates a constraint violation, signaling the need for fine-tuning certain algorithm parameters during the execution phase. The methodologies illustrated in both algorithms are largely in line with those in NaderiAlizadeh et al. (2022); Das et al. (2025a), although with minor modifications designed to suit our specific problem setup. The convergence properties of the proposed updates follow from standard augmented Lagrangian and dual-descent theory under mild assumptions, as previously established in Bertsekas and Tsitsiklis (2015); NaderiAlizadeh et al. (2022). The proposed learning framework approximates these iterative updates in finite time using parameterized inference, while maintaining feasibility using dual updates.

Complexity Analysis: From a computational viewpoint, the online complexity of the proposed GNN-based routing policy scales linearly with the number of nodes. For each time step, the complexity per node is O ( K ⋅ | N j | ⋅ F ), K is the polynomial degree of the graph convolution layer, | N j | is the size of the local neighborhood, and F is the feature dimension. Since K and F are fixed constants in our settings, aggregating across all nodes, the total computational complexity scales as O ( N ) with network size. On the other hand, traditional opportunistic routing algorithms such as ExOR require processing candidate forwarder sets of size | N j | at each transmission. The worst-case computational complexity per node is O ( | N j | ), resulting in a total network complexity of O ( N k ) in sparse graphs. Thus, both approaches scale linearly with N in terms of computational complexity under bounded-degree assumptions. However, ExOR introduces additional communication overheads due to coordination and retransmission control, whereas our proposed GNN-based routing strategy only requires local inference once trained.

8 Numerical results and observations

8.1 Simulation setup and GNN model configurations

We simulate random geometric graphs with N = | V | wireless nodes uniformly placed within a unit circle and connected via the k-Nearest Neighbor (k-NN) method with k = 4. Each node has a transmission capacity C i = 100. For simplicity, we model the wireless link probability using a linear decay function:where d i j is the Euclidean distance and d c is a cutoff beyond which delivery probability drops to zero. Our model captures a declining trend in the link performance with increase in distance similar to more sophisticated probabilistic channel models like the ones used in Mox et al. (2020). For validation of our GNN models at this stage, we do not consider the issues of interference and mobility. Developing advanced learning models that incorporate these aspects is an interesting research direction for future work. The GNN is implemented using a Topology Adaptive Graph Convolution (TAGConv) operation from PyTorch Geometric library, which applies polynomial graph filters over the graph shift operator as demonstrated in Section 5. The GNN architecture consists of 3 layers with feature dimensions F 0 = 2, F 1 = 16, and F 2 = 8. ReLU activation functions are employed between the layers, and the output of the probabilities is achieved with the application of the Softmax function. We train the GNN models using the ADAM optimizer with a step size γ θ = 0.05 and penalty ρ = 0.005 (with exponential decay) for optimization of the model parameters. We run the model training in each epoch for T = 100 time steps, with updates every T 0 = 5.

R i j = 1 − d i j d c , (36)

The analysis of the state-augmented model parameters in the previous section consider the use of time-varying channel probabilities whereas we use a constant channel according to Equation 36. Therefore, the objective now is to determine the policy p ( R , x ; θ * ) for R ∈ R. For a network of given size, we generate 128 training samples and 16 testing samples, using a batch size of 16 samples in each batch. We sample the dual variables randomly from a uniform distribution U ( 1,5 ), which generates a fixed mean arrival rate while capturing variability in traffic requirements. Finally, we run the training iterations for 30 epochs. The packet arrivals a 0 i k ( t ) are not identical across nodes or time. They basically model stochastic traffic and are sampled independently for each node i, flow k, and time step t. Hyperparameters (learning rate γ θ, dual step size γ μ and penalty parameter ρ) were selected through initial fine tuning to ensure stable convergence and were then kept fixed across all experiments to avoid bias. The details of simulation and training parameters are summarized in Table 2.

TABLE 2. Simulation and training parameters.

8.2 Performance between two unparameterized algorithms

We begin by evaluating the performance of two unparameterized optimization methods on networks consisting of N = 10 nodes and K = 4 flows. All simulation methods during training and execution are executed for 30 epochs with T = 1. Figure 2 illustrates the performance of the two unparameterized approaches: MoM and Dual Descent (DD). From the utility plot, it is evident that DD demonstrates slower convergence toward the optimal solution, whereas the augmented Lagrangian method (MoM) achieves better results because it maximizes the utility function while reducing the queue lengths. Although both methods reach similar utility values, the quadratic term in the augmented Lagrangian of MoM more aggressively enforces the routing constraints. This behavior is also reflected in the queue length performance, as slower convergence in DD leads to an accumulation of more packets in the node queues. We considered the case of MoM and DD as unparameterized baselines as they directly optimize the primal and dual variables ( a , T , K , μ ) via iterative updates without learning any state-to-action mapping. The above comparison motivates why we aim to combine MoM with a learned deployable policy.

MoM stabilizes the queues comprehensively quicker than DD due to the quadratic penalty term in the augmented Lagrangian, which enforces feasibility more aggressively. When we consider a longer time horizon (e.g., tens or hundreds of time steps), these queue differences will accumulate and directly influence future packet generation and routing decisions, leading to more pronounced utility gaps in favor of MoM. Thus, queue length stabilization provides an early and reliable signal of improved steady state performance, even when short-horizon utility differences are small.

8.3 Proposed state-augmentation vs. other approaches

Next, we evaluate the trained state-augmented GNN model on randomly generated networks consisting of 10 nodes and 4 flows for T = 100 time intervals. The performance of the GNN model is compared against the primal-dual algorithm based on the dual-descent method and the Extremely Opportunistic Routing (ExOR) protocol as baseline Biswas and Morris (2005). As illustrated in Figure 3, our model demonstrates superior performance compared to the traditional dual descent approach. Not only does our model nearly match the optimal utility achieved by primal-dual as shown in Figure 3a, it also surpasses primal-dual and ExOR protocol in reducing queue lengths, as seen in Figure 3b. Specifically, the proposed SA-GNN achieves a reduction in average steady-state queue length of around 20% compared to dual descent and nearly 90% compared to ExOR for the above scenario. The ExOR protocol being a conventional non-learning routing protocol fails to catch up with the increasing packet arrivals as the time progresses. The relatively poor performance of ExOR can be attributed to the lack of adaptive optimization under varying traffic and queue-related constraints. ExOR uses primarily broadcast diversity without the feedback of the queue states, which restricts its ability to stabilize queues under increasing load.

Next we increase the network size from 10 to 100 nodes and observe both the State Augmentation (SA) model and primal-dual learning show improved utility performance. Despite the increased variance observed with the parameterized SA model, its average performance remains comparably close to that of primal-dual method, as shown in Figure 4a. Across network sizes from 10 to 100 nodes, the average utility gap between SA-GNN and primal-dual remains within approximately 10%, while maintaining stable queue length behavior. A similar trend is observed in the queue length stability for both methods, as depicted in Figure 4b. It can be seen in Figures 4, 5 that, as the network size and number of flows increase, the state-augmented GNN model exhibits stable convergence without erratic divergence in queue lengths. Note that this scalability does not incur increased execution overhead, as the GNN inference depends only on local neighborhood information, rather than the global network size. These results validate that our proposed state-augmented GNN model scales effectively to larger networks while maintaining feasibility and stable queue lengths.

In another simulation, with a fixed network size of 50 nodes while increasing the number of flows from 4 to 16, we observe that both algorithms exhibit improved performance as the number of flows increases, with state augmentation maintaining performance levels close enough to the optimal results of primal-dual learning as shown in Figure 5a. The increase in the number of flows also results in larger queue sizes since it leads to increased accumulation of packets in the network as observed from Figure 5b. The above results showcase the acclaimed scalability properties of GNN-based solutions compared to traditional methods.

We further analyze the comparison of the state augmentation algorithm’s relative performance to dual descent algorithm in a network of 50 nodes and 4 flows. By varying the average of the input to the GNN, which is a 0 i k ( t ), across five different traffic conditions, we observe that the relative performance of state augmentation to dual descent decreases with increase in the traffic input, as shown in Figure 6a. This shows that the state-augmented GNN model has a reduced efficiency while handling increased traffic, thereby increasing the queue length stability, a fact that is supported by the plot in Figure 6b. This decrease in relative performance under a high traffic load condition implies that the GNN’s capacity is being challenged under these conditions, where constraint violations are more common. In these situations, dual descent methods appear relatively more competitive. Nevertheless, under moderate traffic conditions, SA-GNN achieves up to 20% improvement in queue stabilization relative to dual descent before performance degradation appears at extreme load levels.

8.4 Stability to perturbation

Another interesting characteristics of GNN to consider is the stability property. To evaluate this property, we first trained the GNN model on a set of randomly generated network graphs. During testing, we introduced perturbation to 50% of the nodes within a network, shifting their positions by 20% from the original ones. Note that such an adjustment led to a unanimous increase or decrease in the network edges, resulting in a newly structured graph for each sample. Importantly, the model is evaluated on the perturbed graph without further retraining.

As observed in Figure 7, the GNN model delivers commendable performance on these perturbed graphs with respect to the original ones, affirming its stability property. However, it is crucial to acknowledge that slight variances may occur as the node count may change due to the significant variation in the number of edge modifications. This scenario can be potentially applicable in dynamic network environments, such as in multi-agent systems where nodes are mobile and frequently change their locations. This demonstrates the GNN’s extensive ability to adapt to changing network structures while maintaining its performance even though the spatial configuration of the nodes varies.

8.5 Transference to unknown networks of different sizes

As discussed in Section 5, one of the key features of GNNs is their ability to generalize across different network sizes, a property often referred to as size invariance. This characteristic enables GNNs to operate effectively on networks that were not encountered during training. To evaluate this, a state-augmented GNN model was trained on a network with N = 20 nodes and K = 5 flows. The trained model was then tested on networks with node counts varying from 10 to 100.

As seen in Figure 8, it illustrates a 20 node network trained GNN model’s transferability properties to adapt to networks of previously unseen sizes. We observe superior performance of the already trained model particularly on larger graphs, although there is a slight increase in queue length for network with higher number of nodes. Additionally, tests conducted on a 20-node network demonstrate the GNN’s robust and consistent performance across different random graphs of the same size.

We continue with similar tests where a GNN model was trained on a network with N = 50 nodes and K = 10 flows and then evaluated on a 50-node network with varying numbers of flows. As shown in Figure 9, the model successfully maintained its performance across different flow configurations, thereby proving its robust transferability property. The network utility and queue length stability of the trained model were comparable to those achieved by the models which were initially trained on the same graph. Furthermore, scenario with 10 flows reinforces the GNN’s transferability to networks of the same size and flow count. This property of GNNs is particularly beneficial in real time applications, as it enables the training of models on smaller networks offline and their subsequent execution on larger networks online, thereby offering significant savings in computational resources.

8.6 Route formation and packet handling

An interesting observation is to find out the paths traced by the model to transmit the information packets from source node i to the destination node o k. We run the trained state-augmented GNN model on a sample test network with 100 nodes and 4 flows. As shown in Figure 10, we plot the normalized packet handled in the network for a particular flow at each node. It is evident that the GNN performs effectively in routing the packets from the source node through to the final destination node since majority of packets are handled by the nodes that lie in between the source and node.

8.7 Behavior of dual variable and stability of queue length

We analyze network samples with N = 20 nodes and K = 4 flows, training the model over T = 100 time steps to investigate the behavior of dual variables and their influence on network performance. Figure 11 provides a graphical representation of the queue lengths at each time step t alongside the associated dual variables μ ⌊ t / T 0 ⌋. In Figure 11, the stability of queue lengths for two selected nodes is depicted over the T = 100 time steps. It is evident that as the dual variables increase, the queue lengths at these nodes grow correspondingly. However, once the dual variables reach the steady state, they no longer exhibit persistent upward drift and the queue lengths also stabilize while remaining bounded.

8.8 Performance on network topology datasets

We further evaluated our proposed methodology on a range of real-world network configurations derived from the Internet Topology Zoo dataset Knight et al. (2011). Models were trained on four distinct network, namely, Abilene, Tinet, Sinet and Interoute, for 4 flows. To test the versatility of the GNN architecture, a model trained on a 50-node network with 4 flows using randomly generated data was applied to these real-world networks. As shown in Figure 12, while models trained and tested on the same network topologies demonstrate strong performance, the transferred model from the 50-node random data network delivers comparable results. On all evaluated real-world topologies, the transferred SA-GNN achieves performance within approximately 12% of topology-specific trained models. This observation demonstrates that our proposed model is generalized to effectively handle diverse datasets and network topologies.

8.9 Performance on real-time network testbed

Our final observation was to evaluate the validity of the trained GNN models on a real time wireless mesh network. We developed a wireless network testbed using Raspberry Pi’s which served as the nodes of the network. Our formulation focuses on packet rates and queue length evolution rather than link-layer packet design, hence we implemented a minimal packet structure to validate practical deployability of our GNN model. Each packet consists of a f l o w i d identifying the end-to-end flow and a unique p k t i d used for duplicate suppression. At each time step, the source nodes generate a random number of packets for their flow and enqueue them locally. Nodes communicate via one-hop UDP broadcast, i.e., when a node transmits, all neighbors may overhear the packet. Upon successful reception, each neighboring node leverages the learned GNN policy to decide whether to keep or discard the packet (based on K i j k). Subsequently, packets that are kept are added to the local queue only if the p k t i d has not been seen before. The node now makes a decision on whether to forward queued packets in the next time slot using the learned transmit policy T i k (i.e., forward if T i k exceeds a fixed threshold; otherwise hold). The dual variables are updated periodically via local constraint updates, as governed by the distributed method of multipliers method.

Within the limits of experimental resources, we constructed wireless ad hoc networks of size 8 nodes and 10 nodes for 3 flows in the laboratory of University of Pennsylvania. We evaluated the trained GNN models on these networks and transferred the model trained on 8 node network to the network with 10 nodes. As we can see in Figure 13, the model trained on a network with 8 nodes and 3 flows performs quite well as compared to the model which was already trained on the 10 node network. We note that the initial transient observed at the beginning of the 10 node network arises from a temporary dual variable warm-up phase which triggers corrective updates of the optimization variables before the system reaches steady state. We can attribute the strong performance of the transferred 8-node model to the smaller deployment which exhibits cleaner link statistics and reduced interference, resulting in more reliable estimates of R i j during training. This showcases that the proposed state-augmentation algorithm can indeed be implemented in practice as well the transferability properties of GNN models to larger and unseen networks.

9 Limitations and future work

Although the proposed framework demonstrates improved performance, several opportunities remain for further enhancement. First, the current wireless channel model adopts a distance-based success probability abstraction; extending it to incorporate interference, fading effects, and SINR-based modeling would enable analysis under dense and more realistic wireless environments. Second, packet arrivals are modeled as an i. i.d. random process, while practical network traffic often exhibits burstiness and temporal correlations. Incorporating such traffic characteristics could provide deeper insights into queue stability and system behavior under realistic workloads. Finally, the hardware evaluation has been conducted on small-scale testbeds; future work can explore larger industrial-scale deployments by addressing challenges related to synchronization, distributed model dissemination, and communication overhead.

10 Conclusion

This study addresses the problem of routing information packets in wireless networks by optimizing a global utility function under multiple constraints. Unlike the prior formulation, the present study considers the implications of broadcast-based forwarding decisions, wireless link models, real world topology validation, and physical testbed deployment for implementing the proposed wireless routing protocol. While learning-based methods outperformed traditional optimization approaches, unparameterized learning required infinite iterations and frequent re-optimization. To resolve this, we proposed a state-augmentation based routing algorithm, which demonstrated its ability to generate feasible, near-optimal decisions across diverse parameterizations. By implementing this approach with GNNs, we observed strong stability and transferability across various network configurations, including real-world datasets and wireless network testbeds. Future work can be extended to interference aware physical layers and scheduling, mobility and time-varying graphs with online adaptation to support richer traffic and bursty arrivals.

Generative AI statement

The author(s) declared that generative AI was not used in the creation of this manuscript.

Any alternative text (alt text) provided alongside figures in this article has been generated by Frontiers with the support of artificial intelligence and reasonable efforts have been made to ensure accuracy, including review by the authors wherever possible. If you identify any issues, please contact us.

Publisher’s note

All claims expressed in this article are solely those of the authors and do not necessarily represent those of their affiliated organizations, or those of the publisher, the editors and the reviewers. Any product that may be evaluated in this article, or claim that may be made by its manufacturer, is not guaranteed or endorsed by the publisher.

Footnotes

Edited by: Anandakumar Haldorai, Sri Eshwar College of Engineering, India

Reviewed by: Shahzad Ashraf, Gachon University, Republic of Korea

Vijayakumar K., Madras Engineering College, India

Footnotes

This work was presented in part at the 2025 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP) Das et al. (2025b).

T denotes transmission probability vector and T is total time duration.