arXiv CSopen access

Ant Backpressure Routing for Dynamic Wireless Multi-hop Networks with Mixed Traffic Patterns

Ant Backpressure Routing for Dynamic Wireless Multi-hop Networks with Mixed Traffic Patterns Negar Erfaniantaghvayia , Zhongyuan Zhaoa,∗ , Kevin Chanb , Ananthram Swamib and Santiago Segarraa,∗,1 a Department of Electrical and Computer Engineering, Rice University, 6100 Main Street, Houston, 77005, TX, USA

arXiv:2605.24235v1 [cs.NI] 22 May 2026

b DEVCOM Army Research Laboratory, 2800 Powder Mill Road, Adelphi, 20783, MD, USA

ARTICLE INFO

ABSTRACT

Keywords: Mobile ad-hoc networks Biased Backpressure Virtual routing Ant colony optimization Multi-commodity min-cost flow

Backpressure (BP) routing and its shortest-path biased variant (SP-BP) provide powerful congestionaware multipath resource allocation for wireless multi-hop networks, but they rely on per-commodity queueing and slot-by-slot control that may be difficult to realize under practical or legacy forwarding architectures. Moreover, even state-of-the-art SP-BP still suffers from the last-packet problem when short-lived traffic coexists with streaming flows. To address these limitations, we propose Ant Backpressure (Ant-BP), a periodic and fully distributed routing scheme that decouples route learning from packet forwarding. Ant-BP uses virtual SP-BP to construct pheromone-based forwarding probabilities, while actual packets are forwarded through per-neighbor first-in-first-out (FIFO) queues with probabilistic next-hop selection. This architecture enables link-capacity sharing across commodities, mitigates starvation of short-lived traffic, and extends the benefits of SP-BP to network architectures based on per-neighbor FIFO forwarding. Through periodic virtual updates, Ant-BP also adapts to transient link failures and mobility-induced topology changes. Our theoretical analysis and simulations show that, compared with conventional ant colony optimization (ACO) routing, virtual SP-BP enables Ant-BP to establish higher-quality forwarding policies with lower overhead. As a result, Ant-BP improves latency and delivery ratio over SP-BP and ACO-based baselines under mixed streaming and bursty traffic, achieves throughput comparable to SP-BP at low and medium traffic load, and remains robust to mismatched virtual-traffic assumptions, transient link failures, and node mobility.

1. Introduction Wireless multi-hop networks have transcended their traditional applications in military communications, disaster relief, and wireless sensor networks, emerging as an enabler of next-generation (xG) networks. Infrastructure-light architectures are now essential to emerging paradigms in highly dynamic environments, such as integrated access and backhaul (IAB), non-terrestrial networks, device-to-device and massive machine-type communications, connected vehicles, and robotic swarms [2–7]. To ensure scalability and adaptivity, these applications increasingly rely on self-organizing, distributed solutions for resource allocation and network orchestration. Backpressure (BP) routing and its variants [8– 19] have emerged as promising solutions in this domain. In BP schemes, packets destined for a specific node constitute a commodity, requiring per-commodity queues at each node. In contrast to traditional decoupled protocols, BP makes joint routing and scheduling decisions through MaxWeight scheduling driven entirely by local queue differentials (pressure) [8]. By activating non-conflicting links that maximize instantaneous network pressure, BP dynamically ∗ Corresponding authors.

[email protected] (N. Erfaniantaghvayi); [email protected] (Z. Zhao); [email protected] (K. Chan); [email protected] (A. Swami); [email protected] (S. Segarra) ORCID (s): 0000-0002-8049-0067 (N. Erfaniantaghvayi); 0000-0003-0346-8015 (Z. Zhao); 0000-0002-6425-5403 (K. Chan); 0000-0003-1439-332X (A. Swami); 0000-0002-8408-9633 (S. Segarra) 1 Preliminary results were presented in IEEE MILCOM 2024 [1].

Erfaniantaghvayi et al.: Preprint submitted to Elsevier

forwards traffic along congestion gradients, effectively exploring all possible routes. Rooted in Lyapunov drift theory, this approach mathematically guarantees maximum queue stability [8, 10, 11, 14], providing the critical adaptivity needed to absorb demand shocks. Furthermore, with fully distributed greedy schedulers [20, 21], BP schemes enable self-organizing architectures solely relying on local interactions among neighboring nodes. Despite its theoretical elegance, the real-world deployment of classical BP routing is hindered by its high latency and cross-layer requirements. BP suffers latency degradation under low-to-medium traffic loads due to well-documented drawbacks: slow startup, random walks, and the last-packet problem [15–18]. While recent advances in shortest-path biased BP (SP-BP) routing have successfully mitigated the slow startup and random walk issues by shaping routes via distance bias fields [10–14], three structural challenges remain. First, short-lived traffic that lacks a persistent congestion gradient can be starved in the presence of heavy streaming flows (the last-packet problem). Second, the exclusive commodity selection in BP under-utilizes link capacity under low-to-medium traffic [15–18, 22]. More critically, its cross-layer operation and memory-intensive percommodity queueing system conflict with legacy network protocols with decoupled forwarding and route optimization, creating massive architectural friction [16, 23, 24].

Page 1 of 14

Ant Backpressure Routing for Dynamic Wireless Multi-hop Networks

Real-world networks predominantly rely on standard forwarding architectures originally designed for stable wired infrastructure. Legacy Internet protocols (IP) [25] and SoftwareDefined Networks (SDNs) [26, 27] utilize simplified, perneighbor first-in-first-out (FIFO) queues driven by shortestpath routing or centralized traffic engineering [28]. While perfectly suited for the reliable links of wired domains, their direct adoption into dynamic wireless multi-hop networks exposes severe limitations. Traditional IP and SDN assume static network topology and fast control plane, which break down quickly in mobile ad hoc networks (MANETs) [29– 33]. Alternatively, bio-inspired distributed algorithms like Ant Colony Optimization (ACO) [34–37] enable probabilistic multipath routing, but suffer from prohibitively high control overhead and slow convergence during link failures or node mobility [32, 33]. To tackle these challenges, we propose Ant Backpressure (Ant-BP) routing, a hybrid approach that incorporates the effectiveness of SP-BP in gradient-based route discovery into standard forwarding architectures [1]. A lightweight SPBP in the virtual plane periodically maintains pheromone policies for probabilistic forwarding, by exchanging only packet counts–without requiring feedback trips of scout ants in conventional ACO [34–37]. Real data packets are then forwarded through standard per-neighbor FIFO queues, enabling link-capacity sharing across commodities. Furthermore, by mapping bursty flows in data plane into streaming virtual traffic, Ant-BP effectively mitigates the last-packet problem in both virtual and data planes. Compared to conventional ACO, the gradient-based route discovery of AntBP incurs significantly lower overhead, making it adaptive to transient link failures and node mobility. Contribution. The contributions of this paper are fourfold: 1. Decoupled hybrid architecture: We propose Ant-BP, a distributed routing scheme that combines the gradientdriven route learning of SP-BP with lightweight, probabilistic packet forwarding. By using virtual SP-BP to construct pheromone policies and per-neighbor FIFO queues for physical forwarding, Ant-BP mitigates short-flow starvation and extends SP-BP-style intelligence to legacycompatible network architectures. 2. Theoretical interpretation: We theoretically ground AntBP by relating SP-BP to a stochastic cost-minimization problem in the fully dynamic regime. We demonstrate that Ant-BP heuristically approximates the corresponding long-term routing objective under a restricted FIFO forwarding regime, trading a reduced strict stability region for practical implementability. 3. Adaptive mechanisms for network dynamics: We design mechanisms to make Ant-BP robust in dynamic wireless environments. These include periodic virtual route reestimation, pheromone penalization to handle transient link failures, and mobility adaptation through remapping of stranded physical packets into the virtual state. 4. Comprehensive numerical evaluation: Through extensive simulations, we show that Ant-BP improves end-to-end Erfaniantaghvayi et al.: Preprint submitted to Elsevier

latency and delivery ratios over SP-BP and ACO-based baselines under mixed streaming and bursty traffic. Furthermore, it achieves throughput comparable to SP-BP at low-to-medium loads and remains highly robust to mismatched virtual-traffic assumptions, link failures, and mobility-induced topology changes. Notation. Operators (⋅)⊤ , ⊙, and | ⋅ | represent the transpose operator, Hadamard (element-wise) product operator, and the cardinality of a set. 1(⋅) is the indicator function. Upright bold lower-case symbol, e.g., 𝐳, denotes a column vector, and 𝐳𝑖 denotes the 𝑖-th element of vector 𝐳. Upright bold uppercase symbol 𝐙 denotes a matrix, whose element at row 𝑖 and column 𝑗 is denoted by 𝐙𝑖𝑗 , the entire row 𝑖 by 𝐙𝑖∗ , and the entire column 𝑗 by 𝐙∗𝑗 . A capital calligraphic letter denotes a set, queue, or graph.  (𝑖) represents the set of immediate neighbors of node 𝑖 on graph .

2. Related Work Real-world wireless multi-hop networks often struggle to adopt standard forwarding architectures—such as legacy IP or Software-Defined Networks (SDNs)—because their reliance on static topologies and centralized control breaks down under intermittent connectivity. To address this, early work focused on topology-based routing protocols designed specifically for mobile ad hoc networks (MANETs) [29, 30]. Representative examples include Dynamic Source Routing (DSR) [38–40] and Ad hoc On-demand Distance Vector (AODV) [41–44], which establish routes through ondemand route discovery and maintain them using control messages. While such protocols are simple and scalable, they rely on predetermined, rigid paths that suffer from severe performance degradation in dynamic environments where link rates and congestion levels change rapidly [32, 33]. To improve robustness against such channel variability, opportunistic routing techniques were later proposed to dynamically select forwarding nodes based on link quality, congestion conditions, and priority [45–47]. Protocols such as ExOR [48] and CORMAN [49] exploit the broadcast nature of the wireless medium to dynamically select nexthop relays, while subsequent congestion-aware variants like D-ORCD [50–52] select forwarding nodes based on expected draining times. However, while these heuristic approaches increase transmission reliability, they lack the rigorous mathematical framework required to guarantee maximum network-wide queue stability under heavy congestion. Another important class of routing strategies relies on bio-inspired swarm intelligence, particularly ACO [34–37], which discovers and maintains multiple paths in a distributed, probabilistic manner. Protocols like AntHocNet [34] combine reactive path discovery with proactive route maintenance, where artificial ants explore the network and update pheromone routing tables [37]. While various extensions attempt to improve path stability, delay performance, and energy efficiency in dynamic wireless environments [36, 53], conventional ACO algorithms face severe structural limitations. Specifically, because route exploration Page 2 of 14

Ant Backpressure Routing for Dynamic Wireless Multi-hop Networks

Figure 1: Ant backpressure routing system diagram: queueing system design, operations, and timelines.

and maintenance require the continuous transmission of payload-heavy physical scout ants that must traverse the network and return to their sources, these protocols suffer from prohibitively high control overhead and slow convergence [35] in MANETs with transient link failures or node mobility. In parallel with these approaches, queue-based routing frameworks [54, 55]–most notably BP routing [8– 19]–emerged to jointly address routing and scheduling under wireless interference constraints. Due to the theoretical stability guarantees of BP, extensive research has focused on mitigating its high latency [9–19]. Proposed solutions include incorporating delay-based backlogs into pressure calculation and scheduling [15, 56, 57], using LIFO queues [16], employing multi-stage scheduling with shortest-path metrics [58], and introducing (delay-aware) shortest-path bias fields to shape routing behaviors [10–14]. Furthermore, to address the architectural friction of percommodity queues, virtual or shadow queue architectures were proposed to mathematically decouple optimal route calculation from physical packet queues [23, 24]. Despite these advances, fundamental structural issues prevent real-world adoption. First, the last-packet problem persists due to per-commodity queue design [1, 15–18] which becomes more significant as short-lived traffic dominates machine-type communications. More critically, the requirement of cross-layer control significantly hinders the deployment of BP schemes in networks relying on standard low-level network protocols (e.g., Ethernet) based on simple per-neighbor FIFO forwarding [59]. To close the gap between these disjointed paradigms, we propose to combine the lightweight multipath route establishment of SP-BP with the FIFO-based probabilistic packet forwarding for dynamic wireless multi-hop networks.

Erfaniantaghvayi et al.: Preprint submitted to Elsevier

3. System Model 3.1. Connectivity and Conflict Topologies We represent a wireless multi-hop network by a directed connectivity graph 𝑛 = (, ), in which a node 𝑖 ∈  denotes a transceiver in the network, and a directed link 𝑒 = (𝑖, 𝑗) ∈ , where 𝑖, 𝑗 ∈ , indicates that packets can be transmitted from node 𝑖 to node 𝑗 over the air. We assume 𝑛 to be connected, ensuring that any two nodes within the network can reach each other. We use a conflict graph, 𝑐 = (, ), to model the orthogonal access constraint among wireless links as follows: each vertex 𝑒 ∈  corresponds to a wireless link in the network 𝑛 , and the presence of an undirected edge (𝑒1 , 𝑒2 ) ∈  indicates that links 𝑒1 and 𝑒2 cannot be activated simultaneously, due to interface conflict (two links sharing the same radio transceiver), or radio interference (e.g., two links located within certain distance interfere with each other if activated at the same time). For the rest of this paper, we assume the conflict graph 𝑐 to be known, either through direct monitoring of the wireless channel by each link or through more advanced estimation as in [21, 60].

3.2. Data Plane Architecture We consider a time-slotted medium access control (MAC) system with orthogonal multiple access. Each time slot 𝑡 comprises a resource allocation (routing and scheduling) ̀ stage, followed by data transmission. Vector 𝐫(𝑡) = [𝐫̀ 𝑒 (𝑡) ∣ 𝑒 ∈ ] ∈ ℝ|| gathers the real-time link rates in time slot 𝑡, where entry 𝐫̀ 𝑒 (𝑡) denotes the number of packets that can ̀ traverse link 𝑒 ∈  during time slot 𝑡. Vector 𝐫 = 𝔼𝑡 [𝐫(𝑡)] ∈ ℝ|| collects the long-term average link rates. The packets destined for node 𝑐 ∈  are designated as commodity 𝑐, 𝐴(𝑐) 𝑖 (𝑡) denotes the exogenous arrival of commodity 𝑐 on node 𝑖 during slot 𝑡, and the arrival rate [ (𝑐) ] 𝜆(𝑐) 𝑖 = 𝔼 𝐴𝑖 (𝑡) . The network follows a decoupled routing and scheduling architecture illustrated in Fig. 1, which abstracts many real-world wireless ad-hoc or mesh networks, Page 3 of 14

Ant Backpressure Routing for Dynamic Wireless Multi-hop Networks

and is similar to the Max-Pressure [61, 62] in road networks. In particular, a commodity-blind Max-Weight link scheduling activates a set of non-conflicting, most congested links in each time slot, for maximum queue stability under an independent, probabilistic packet routing policy. Per-neighbor queueing system: Each device 𝑖 ∈  hosts per-neighbor queues, denoted as 𝑖𝑗 , which buffers packets to be sent to each neighboring device 𝑗 ∈ 𝑛 (𝑖). In addition, we use queue 𝑖𝑖 to buffer newly arrived exogenous (injected by user 𝑖) and endogenous (from neighbors) packets of which the next hops are undecided yet. All the queues follow the FIFO principle, and the queue length of 𝑖𝑗 at the beginning of time slot 𝑡 is denoted by 𝑞𝑖𝑗 (𝑡). To facilitate our proposed virtual queue solution and theoretical analysis, we also denote the backlog size of a commodity 𝑐 on device 𝑖 with 𝑄(𝑐) 𝑖 (𝑡), e.g., as packet counts under the data-plane per-neighbor queues. Probabilistic forwarding: At the beginning of a time slot 𝑡 and on each node 𝑖 ∈ , every packet from 𝑖𝑖 is independently sent to queue 𝑖𝑗 associated with one of its neighbors 𝑗 ∈ 𝑛 (𝑖) according to an established per-commodity [ ] probabilistic routing policy, 𝑝(𝑐) 𝑖𝑗 (𝑡) ∣ 𝑗 ∈ 𝑛 (𝑖), 𝑐 ∈  , ∑ (𝑐) where 0 ≤ 𝑝(𝑐) 𝑖𝑗 (𝑡) ≤ 1, 𝑗∈𝑛 (𝑖) 𝑝𝑖𝑗 (𝑡) = 1. MaxWeight scheduling: After forwarding, the utility vector || 𝐮(𝑡) ∈ ℝ+ is computed, where per-link utility is 𝑢𝑖𝑗 (𝑡) = 𝑞𝑖𝑗 (𝑡)𝐫̀ 𝑖𝑗 (𝑡) ,

(1)

∀(𝑖, 𝑗) ∈ .

Next, Max-Weight scheduling finds the schedule 𝐬(𝑡) based on the utility vector 𝐮(𝑡) and conflict graph 𝑐 = (, ), (2a)

𝐬(𝑡) = argmax 𝐬(𝑡)⊤ 𝐮(𝑡), 𝐬̃ (𝑡)∈{0,1}||

s.t. 𝑠̃𝑒1 (𝑡) + 𝑠̃𝑒2 (𝑡) ≤ 1, ∀ (𝑒1 , 𝑒2 ) ∈  .

(2b)

Notice that the Max-Weight scheduling in (2) involves solving a maximum weighted independent set (MWIS) problem on the conflict graph, which is NP-hard [63]. Therefore, in practice, (2) is solved approximately by heuristics, such as centralized greedy maximal scheduler (GMS), distributed local greedy scheduler (LGS) [20], and GNN-enhanced LGS [21]. In this paper, we choose LGS [20] as our distributed Max-Weight scheduler for its simplicity. The number of packets to be transmitted on link (𝑖, 𝑗) in time slot 𝑡 is 𝜇𝑖𝑗 (𝑡) = 𝑠𝑖𝑗 (𝑡) min{𝑞𝑖𝑗 (𝑡), 𝐫̀ 𝑖𝑗 (𝑡)}. The queue lengths 𝑞𝑖𝑗 (𝑡) are initialized as 𝑞𝑖𝑗 (0) = 0 and evolve such that, at each time slot 𝑡, the queue length 𝑞𝑖𝑗 (𝑡) increases by the number of packets routed from node 𝑖 to queue 𝑖𝑗 under the probabilistic routing policy, and decreases by 𝜇𝑖𝑗 (𝑡) packets transmitted over link (𝑖, 𝑗). Route optimization under the decoupled routing and scheduling architecture can be stated as follows: Problem 1. We seek to establish a probabilistic policy, [ ] 𝑃 = 𝑝(𝑐) 𝑖𝑗 (𝑡) ∣ (𝑖, 𝑗) ∈ , 𝑐 ∈  , Erfaniantaghvayi et al.: Preprint submitted to Elsevier

that forwards packets into per-neighbor FIFO queues, which are scheduled for transmissions by a MaxWeight scheduler defined in (1) and (2). The goal is to balance multicommodity traffic across the network for maximum throughput, minimum end-to-end latency, and rapid adaptation to dynamics such as link failures and node mobility. A formal formulation is detailed in Section 5, equations (12) and (16). Unlike routing in wired networks that can be solved efficiently using all-pairs shortest path algorithms or linear multi-commodity min-cost flow (MCMCF) formulations, route optimization in wireless networks is subject to conflict constraints modeled by 𝑐 , e.g., MaxWeight scheduling in (2) is NP-hard. This makes it an NP-hard nonlinear MCMCF problem where link capacity and unit cost depend on the decision variables, i.e., flow rate assignments. As a result, heuristics like ACO routing (Appendix A) are studied. While bio-inspired ACO routing can operate in a fully distributed manner, it suffers from low convergence, limited adaptivity to node mobility, and lack of mathematical rigor in route optimization.

4. Ant Backpressure To address the slow convergence of ACO, Ant-BP adopts a per-commodity routing policy similar to (18), (𝑐) 𝑝𝑖𝑗 (𝑡) = ∑

𝜌(𝑐) 𝑖𝑗 (𝑡) (𝑐) 𝑙∈𝑛 (𝑖) 𝜌𝑖𝑙 (𝑡)

,

∀𝑖, 𝑐 ∈  ,

(3)

while updating the pheromone intensity 𝜌(𝑐) 𝑖𝑗 (𝑡) periodically via virtual routing described in Sections 4.1 and 4.2, which remains the same until its next update. Ant-BP seeks to address the establishment of pheromone policy in a fully distributed manner with fast convergence.

4.1. Virtual SP-BP for Pheromone Establishment The pheromone in (3) is established by SP-BP routing [10–14] on a virtual plane, which operates on a virtual (shadow) per-commodity queuing system, denoted as {̃ 𝑖(𝑐) | 𝑖, 𝑐 ∈ }, where ̃ (𝑐) 𝑖 is the virtual queue hosted on device 𝑖 for commodity 𝑐. A virtual queue ̃ 𝑖(𝑐) only counts the number of packets for its commodity 𝑐 in the virtual plane without storing any payload, and its queue length at virtual time step 𝜏 is denoted as 𝑄̃ (𝑐) 𝑖 (𝜏). Here, 𝜏, rather than 𝑡, is adopted as virtual routing operates on a time scale different from the physical time slot 𝑡. To illustrate the operations of SP-BP, we define biased pressure as 𝑈̃ 𝑖𝑗(𝑐) (𝜏) = 𝑈̃ 𝑖(𝑐) (𝜏) − 𝑈̃ 𝑗(𝑐) (𝜏), where 𝑈̃ 𝑖(𝑐) (𝜏) = (𝑐) (𝑐) 𝑄̃ (𝑐) 𝑖 (𝜏) + 𝐵𝑖 , and 𝐵𝑖 ≥ 0 is a queue-agnostic bias representing the shortest path distance from node 𝑖 to 𝑐 on (edge weighted) graph 𝑛 . The bias field {𝐵𝑖(𝑐) |𝑖, 𝑐 ∈ } is established through all-pairs-shortest-path (APSP)[algorithm] on the connectivity graph 𝑛 with edge weights 𝛿𝑒 |𝑒 ∈  defined by link features [12–14]. To accommodate network mobility, {𝐵𝑖(𝑐) |𝑖, 𝑐 ∈ } can be updated periodically. Page 4 of 14

Ant Backpressure Routing for Dynamic Wireless Multi-hop Networks

In each time 𝜏, the virtual SP-BP operates in four steps: Step 1: the optimal commodity 𝑐𝑖𝑗∗ (𝜏) for each link (𝑖, 𝑗) is selected as the one with the maximal pressure: 𝑐𝑖𝑗∗ (𝜏) = argmax {𝑈̃ 𝑖𝑗(𝑐) (𝜏)} .

(4)

𝑐∈

Step 2: the utility of each link (𝑖, 𝑗) is found as [14]

4.2. Virtual Traffic Configuration

𝑢̀ 𝑖𝑗 (𝜏) = 𝐫̀ 𝑖𝑗 (𝜏)𝑤𝑖𝑗 (𝜏) , (5a) ] } [ ∗ { ∗ (𝑐 (𝜏)) (𝑐 (𝜏)) 𝑤𝑖𝑗 (𝜏) = max 𝑈̃ 𝑖𝑗 𝑖𝑗 (𝜏), 0 ⋅1 𝑄̃ 𝑖 𝑖𝑗 (𝜏) > 0 , (5b) ̀ where vector 𝐫(𝜏) collects the virtual real-time link rate of all links at step 𝜏, and 𝐫̀ 𝑒 (𝜏) is generated from the same distribution as 𝐫̀ 𝑒 (𝑡) to reflect the characteristics of underlying wireless channel. Step 3: Max-Weight scheduling finds the schedule 𝐬̀ (𝜏) ∈ {0, 1}|| to activate a set of non-conflicting links as, ̀ 𝐬̀ (𝜏) = argmax 𝐬(𝜏)⊤ 𝐮(𝜏), 𝐬̃ (𝜏)∈{0,1}||

s.t. 𝑠̃𝑒1 (𝜏) + 𝑠̃𝑒2 (𝜏) ≤ 1, ∀ (𝑒1 , 𝑒2 ) ∈  .

(6a) (6b)

The Max-Weight scheduler is also selected as LGS in [20]. Step 4: all of the virtual real-time link rate 𝐫̀ 𝑖𝑗 (𝜏) of a scheduled link is allocated to its optimal commodity 𝑐𝑖𝑗∗ (𝜏). The final transmission assignments of commodity 𝑐 ∈  on link (𝑖, 𝑗) is ̀ ̀ 𝜇𝑖𝑗(𝑐) (𝜏) = min{𝑄̃ (𝑐) 𝑖 (𝜏), 𝐫𝑖𝑗 (𝜏)} ⋅ 𝐬𝑖𝑗 (𝜏) ⋅ 1{𝑐 = 𝑐𝑖𝑗∗ (𝜏)} ⋅ 1{𝑤𝑖𝑗 (𝜏) > 0} .

(7)

Pheromone establishment: The pheromone intensity in (3) is then established as (𝑐) (𝑐) 𝜌(𝑐) 𝑖𝑗 (𝜏) = max{𝑛𝑖𝑗 (𝜏) − 𝑛𝑗𝑖 (𝜏), 0} + 𝜖 ,

(8)

where the small constant 𝜖 > 0 ensures 𝑝(𝑐) 𝑖𝑗 (𝜏) = 1∕|𝑛 (𝑖)| when the first term in (8) is zero for all 𝑙 ∈ 𝑛 (𝑖). In (8), 𝑛(𝑐) 𝑖𝑗 is the cumulative number of virtual packets of commodity 𝑐 that have traveled across link (𝑖, 𝑗) during virtual SP-BP routing, computed as: 𝑛(𝑐) 𝑖𝑗 (0) = 0, and (𝑐) (𝑐) 𝑛(𝑐) 𝑖𝑗 (𝜏) = (1 − 𝜀) ⋅ 𝑛𝑖𝑗 (𝜏 − 1) + 𝜇𝑖𝑗 (𝜏),

where the evaporation rate is typically set as zero (𝜀 = 0). Similarly, all virtual queues are initialized as empty, i.e., 𝑄̃ (𝑐) 𝑖 (0) = 0 at the beginning of virtual SP-BP. In virtual SP-BP routing, no packets are actually generated or transmitted, but only the number of virtual packets of each commodity at each node 𝑖 ∈  and transmitted over each link (𝑖, 𝑗) is tracked and exchanged across the network. As a result, the data transmission of virtual routing can be compressed into a very short duration, such that tens or hundreds of time steps of virtual SP-BP routing can be Erfaniantaghvayi et al.: Preprint submitted to Elsevier

finished in a single physical time slot. This allows our routing policy to be established within a few time slots, as illustrated by the timelines in Fig. 1. The required number of time steps for virtual SP-BP routing to establish our routing policy is denoted as 𝐾 and configured as a system parameter via trial-and-error. In virtual routing, each physical traffic demand (e.g.,

𝜆(𝑐) 𝑖 ) is mapped to a virtual packet injection sharing the

same source and destination. However, their temporal profiles (rates and durations) can be deliberately decoupled. Depending on our knowledge of the physical traffic, we configure the virtual plane using one of two strategies: either perfectly replicating the exact physical rates and durations, or generalizing all injections as continuous streaming traffic (e.g., mapping a short-lived physical burst to a persistent virtual stream). Moreover, because virtual routing strictly precedes physical transmission, exact slot-by-slot arrival sequences are fundamentally unknowable a priori. Therefore, in Ant-BP, virtual packets are generated at the source nodes via a Poisson process matching the configured target rate. Because SP-BP route optimization is inherently agnostic to exact arrival processes [64], this implementation simplifies virtual generation while still establishing a robust, high-quality routing policy.

4.3. Dynamic Network Adaptation In dynamic networks, link availability fluctuates due to various environmental and physical factors. We introduce additional measures to make Ant-BP adaptive to transient link failure and topology-altering network mobility. While both disrupt packet transmission, their differing timescales and structural impacts necessitate distinct treatments. Transient Link Failure: A transient link failure is a temporary loss of channel capacity on an existing link 𝑒, causing scheduled transmissions to momentarily fail. Despite this disruption, the affected link 𝑒 remains a valid edge on the connectivity graph 𝑛 and is expected to recover. To capture the impact of interference and channel fading, these failure events are modeled as a stochastic process characterized by Poisson arrivals and random durations. When a transmission fails, the packets scheduled on the affected outgoing link are reset to an unscheduled state for that time step. Furthermore, the pheromone level on the failed outgoing link is decayed by a tunable parameter (e.g., 5%), discouraging its selection in subsequent slots. Network Mobility: Network mobility involves the physical movement of nodes, that can potentially lead to permanent topology changes, i.e., existing links break and/or new links form on the connectivity graph 𝑛 . To manage the disruptions caused by these topological shifts, our protocol reacts at both the link and packet levels. Structurally, broken links are immediately discarded from the routing pool, while newly established links are initialized with a small constant pheromone value 𝜖 > 0. If a packet

Page 5 of 14

Ant Backpressure Routing for Dynamic Wireless Multi-hop Networks

is scheduled on a link that subsequently breaks, its status is immediately reverted to undecided and moved back to 𝑖𝑖 . However, simply unscheduling packets can lead to severe queuing delays or leave packets stranded at affected nodes. To prevent this, we treat commodities stranded at these nodes as virtual sources during the subsequent periodic virtual SPBP phase to establish new pheromone policies towards their destinations. This process enables the system to organically discover new routes for stranded packets, integrate newly formed links, and adapt to the shifted traffic load. While our focus is on spatial node movement, this approach extends naturally to mobility events involving node addition or removal, with the caveat that packets buffered at removed nodes are unavoidably lost.

5. Theoretical Analysis Depending on the network architecture, routing policies process network state information differently. Fully dynamic routing, such as SP-BP, utilizes per-commodity queues to make routing and scheduling decisions that are distinctly per-commodity and slot-by-slot, driven by instantaneous queueing states. In contrast, Ant-BP decouples route discovery from packet forwarding. It periodically updates a stationary probabilistic forwarding policy, and applies this policy to a constrained per-neighbor FIFO queueing architecture.

5.1. Fully Dynamic Routing To theoretically ground Ant-BP, we first formulate the joint routing and scheduling task under the fully dynamic regime as a stochastic cost minimization problem. While Ant-BP addresses mixed traffic patterns, we restrict this formulation to strictly streaming traffic to preserve the analytical tractability. Let 𝑄(𝑐) 𝑖 (𝑡) be the per-commodity queue length at node 𝑖. Assuming that packets reaching their destinations are consumed immediately, i.e., 𝑄(𝑐) 𝑐 (𝑡) = 0, the queue dynamics on a non-destination node 𝑖 ≠ 𝑐 follows: ∑ (𝑐) ∑ (𝑐) (𝑐) 𝜇𝑖𝑗 (𝑡) + 𝑄(𝑐) 𝜇𝑗𝑖 (𝑡) + 𝐴(𝑐) 𝑖 (𝑡 + 1) = 𝑄𝑖 (𝑡) − 𝑖 (𝑡), (9) 𝑗∈𝑛 (𝑖)

𝑗∈𝑛 (𝑖)

where 𝐴(𝑐) 𝑖 (𝑡) is the exogenous arrivals of commodity 𝑐 on device 𝑖, and the decision variables at each time step 𝑡 is the commodity-link rate assignment collected in [ ] 𝐌(𝑡) = 𝜇𝑖𝑗(𝑐) (𝑡) ∈ 𝚷, (𝑖,𝑗)∈, 𝑐∈

where 𝚷 denotes the feasible solution space under scheduling constraints, e.g., flow conservation, link capacity, and non-conflicting schedules as follows: ∑ 𝜇𝑖𝑗(𝑐)(𝑡) ≤ 𝑄(𝑐) 𝑖 (𝑡) , ∀𝑐 ∈ , (𝑖, 𝑗) ∈ , (10a) 𝑗∈𝑛 (𝑖)

∑

𝜇𝑖𝑗(𝑐)(𝑡) ≤ 𝐫̀ 𝑖𝑗 (𝑡) , ∀(𝑖, 𝑗) ∈ ,

(10b)

𝑠𝑒1 (𝑡) + 𝑠𝑒2 (𝑡) ≤ 1 , ∀ (𝑒1 , 𝑒2 ) ∈ ,

(10c)

𝑐∈

Erfaniantaghvayi et al.: Preprint submitted to Elsevier

where 𝑠𝑒 (𝑡) ∈ {0, 1} indicates if link 𝑒 is scheduled at step 𝑡 [ ] ∑ 𝑠𝑒 (𝑡) = 1 𝜇𝑒(𝑐) (𝑡) . 𝑐∈

We define the routing cost at time step 𝑡 as ∑ ∑ (𝑐) (𝑐) 𝑔(𝑡) = 𝜇𝑖𝑗 (𝑡) 𝐵𝑗𝑖 ,

(11)

(𝑖,𝑗)∈ 𝑐∈ (𝑐) where 𝐵𝑗𝑖 = 𝐵𝑗(𝑐) − 𝐵𝑖(𝑐) represents the change in the remaining distance of commodity 𝑐 (towards its destination 𝑐) transmitted from 𝑖 to 𝑗 (negative values correspond to distance reduction), and 𝑔(𝑡) is the change in the total remaining distance of all packets from decisions 𝐌(𝑡). Stochastic Cost Minimization Formulation. For a given demand profile 𝝀 within the network capacity region, i.e., [ ] 𝝀 = 𝜆(𝑐) 𝑖 𝑖,𝑐∈ ∈ int(Λ), the optimal routing and scheduling policy 𝜋 ∗ is formulated as one that minimizes time-average cost under stability and scheduling constraints:

1 ∑ 𝔼[𝑔(𝑡) ∣ 𝜋] 𝑇 𝑡=0 𝑇 −1

min 𝜋

s.t.

𝑔(𝜋) ̄ ≜ lim sup 𝑇 →∞

(12a)

{𝑄(𝑐) (12b) 𝑖 (𝑡)} are strongly stable, [ ] (𝑐),𝜋 𝐌𝜋 (𝑡) = 𝜇𝑖𝑗 (𝑡) ∈ 𝚷, ∀𝑡, (12c) (𝑖,𝑗)∈, 𝑐∈ ( ) 𝐌𝜋 (𝑡) = 𝜋 𝐐(𝑡), 𝐫̀ ∗ (𝑡) ∣ 𝜆, 𝑛 , 𝑐 , (𝑡−1) , (12d)

{ } where (𝑡−1) = 𝐐(𝑡′ ), 𝐫̀ ∗,𝑡′ , 𝐌𝜋 (𝑡′ ) 𝑡′ =0,…,𝑡−1 encloses the trajectories of past queueing states, link rates, and decisions. Notice that (𝑡 − 1) is optional for policy 𝜋. Proposition 1. For Problem (12) in the fully dynamic regime, the SP-BP policy 𝜋 𝑠 is near-optimal for any fixed admissible demand profile 𝜆 ∈ int(Λ). (𝑐) Proof. Let 𝑈𝑖(𝑐) (𝑡) = 𝑄(𝑐) 𝑖 (𝑡) + 𝐵𝑖 denote biased backlog, 𝑈𝑖𝑗(𝑐) (𝑡) = 𝑈𝑖(𝑐) (𝑡) − 𝑈𝑗(𝑐) (𝑡) as biased pressure, and 𝐐(𝑡) = [ (𝑐) ] 𝑄𝑖 (𝑡) 𝑖,𝑐∈ as the queueing state at step 𝑡. We define onestep conditional drift of the Lyapunov function as:

Δ(𝑡) = 𝔼[(𝑡 + 1) − (𝑡) ∣ 𝐐(𝑡)], (𝑡) =

1 ∑ (𝑐) 2 𝑄 (𝑡) . 2 𝑖,𝑐∈ 𝑖

̃ The biased drift Δ(𝑡) can be defined similarly based on biased backlogs {𝑈𝑖(𝑐) (𝑡)}. Based on Lyapunov theory for biased BP [14, Theorem 1] and its drift-plus-penalty (DPP) interpretation [22], the policy of SP-BP (𝜋 𝑠 ) is formulated as solving a MaxWeight problem, which minimizes the upper bound of DPP objective at each time step 𝑡: ∑ ∑ (𝑐) 𝑠 𝐌𝜋 (𝑡) = argmax 𝜇𝑖𝑗 (𝑡)𝑈𝑖𝑗(𝑐) (𝑡) (13a) 𝐌(𝑡)∈𝚷 (𝑖,𝑗)∈ 𝑐∈

[ ] ̃ = argmin UB Δ(𝑡)

(13b)

𝐌(𝑡)∈𝚷

Page 6 of 14

Ant Backpressure Routing for Dynamic Wireless Multi-hop Networks

= argmin UB [Δ(𝑡) + 𝑔(𝑡)] ,

(13c)

𝐌(𝑡)∈𝚷

where UB(⋅) stands for the upper bound. It has been proven in [14, Theorem 1] that (13a) guarantees strong stability for all 𝝀 ∈ int(Λ), defined as [10, 11, 15, 64] 𝑇∑ −1 ∑

[

𝜋

]

1 lim sup 𝔼 𝑄(𝑐) 𝑖 (𝑡) < ∞ . 𝑇 →∞ 𝑇 𝑡=0 𝑖,𝑐∈

(14)

This optimality gap arise from the bias field scaling tradeoff in (13c) and the tightness of the drift upper bound when a heuristic MaxWeight scheduler is applied. In practice, optimality is further limited by the finite virtual routing horizon, node mobility, and virtual-physical mismatches in both demand profiles and instantaneous link rates.

5.2. Stationary Policy in Restricted Regime Definition 1. For any stabilizing policy 𝜋, define the induced time-average (expected) commodity flow rates for an arbitrary admissible demand profile 𝜆 ∈ int(Λ) as:

𝑇 →∞

𝑇 −1 1 ∑ [ (𝑐),𝜋 ] 𝔼 𝜇𝑖𝑗 (𝑡) , 𝑇 𝑡=0

∀(𝑖, 𝑗) ∈ , 𝑐 ∈ . (15)

This induced time-average commodity flows represents the long-term behavior of a stabilizing policy under 𝝀. Lemma 1. The time-average commodity flows induced by a stabilizing policy satisfy flow conservation. Proof. Applying strong stability of queues in (14) and instantaneous flow conversation in (10a) to the telescopic sum of queue dynamics in (9) leads to flow conservation ∑ ∑ 𝑓𝑖𝑗(𝑐),𝜋 − 𝑓𝑗𝑖(𝑐),𝜋 = 𝜆(𝑐) ∀𝑖, 𝑐 ∈  . 𝑖 , 𝑗∈𝑛 (𝑖)

𝑗∈𝑛 (𝑖)

𝐀𝐟

= 𝐝(𝑐) ,

(16b)

∀𝑐 ∈ ,

𝐌 (𝑡) ∈ 𝚷, ∀𝑡, ( ) 𝐌𝜋 (𝑡) = 𝜋 𝑎 𝐫̀ ∗ (𝑡) ∣ 𝜆, 𝑛 , 𝑐 , 𝐅𝜋 , [ ] where matrix 𝐅𝜋 = 𝑓𝑖𝑗(𝑐),𝜋

(𝑖,𝑗)∈,𝑐∈

(16c) (16d)

collects all commodity

flows. (16d) defines the restricted policy regime: probabilistic forwarding, per-neighbor FIFO queues, and commodityblind MaxWeight scheduling in (2). Proof. Apply time average to (11), and by linearity of expectation, the objectives in (12a) and (16a) are identical ∑ ∑ (𝑐),𝜋 (𝑐) 𝑓𝑖𝑗 ⋅ 𝐵𝑗𝑖 𝑔(𝜋) ̄ = . (𝑖,𝑗)∈ 𝑐∈

Based on Lemma 1, constraint (16b) is equivalent to (12b). Constraints (16c) and (12c) are identical. Remark 1. Ant-BP approximates the optimal policy for Problem (16) in the restricted regime. Ant-BP constructs a pheromone routing policy in (8) through virtual SP-BP in (4)–(7), and therefore heuristically approximate the constrained MCMCF problem in (16) under restricted per-neighbor FIFO queue architecture. However, since the MaxWeight objective in (13a) can no longer be optimized slot-by-slot under this restricted regime, the stability region of Ant-BP is generally reduced. Through experiments in Section 6, we demonstrate that the pheromone policy established from virtual streaming traffic generalizes well to scenarios with short-lived traffic and mismatched traffic loads.

6. Numerical Experiments We evaluate the effectiveness, robustness, and tradeoffs of Ant-BP in both route optimization and last-packet problem mitigation, by comparing it against state-of-the-art SP-BP [14] and ACO routing under challenging scenarios, such as mixed streaming and bursty traffic, uncertain arrival rates, transient link failures, and mobility.

6.1. Test Setup and Baselines

With node-edge incidence matrix 𝐀 of graph 𝑛 , we have: [ ] 𝐀𝐟 (𝑐),𝜋 = 𝐝(𝑐) , 𝐟 (𝑐),𝜋 = 𝑓𝑖𝑗(𝑐),𝜋 , ∀𝑐 ∈ , (𝑖,𝑗)∈

(𝑐) (𝑐) where 𝐝(𝑐) 𝑖 = 𝜆𝑖 and 𝐝𝑐 = −

s.t.

(𝑖,𝑗)∈ 𝑐∈ (𝑐),𝜋

𝜋

Since minimizing the drift bound UB[Δ(𝑡)] at each step 𝑡 guarantees strong stability of queues for demands 𝝀 ∈ int(Λ) [10, 11], by the standard DPP framework [64, Theorem 4.8], the per-slot drift bound minimization in (13c) yields a policy that achieves near-optimal time-average cost 𝑔(𝜋) ̄ and queue stability in (12), with the tradeoff governed by the scaling of the bias field {𝐵𝑖(𝑐) }. Therefore, the DPP minimization of SP-BP in (13c) can be interpreted as an online Lagrangian for Problem (12). With a properly scaled bias field [14], SP-BP thus serves as a near-optimal policy for Problem (12) with any demands 𝝀 ∈ int(Λ).

𝑓𝑖𝑗(𝑐),𝜋 ≜ lim sup

Proposition 2. Under a policy regime defined by stationary probabilistic forwarding and per-neighbor FIFO queues, Problem (12) is equivalent to a constrained multi-commodity min-cost flow (MCMCF) problem for demand 𝝀 ∈ int(Λ′ ): ∑ ∑ (𝑐),𝜋 (𝑐) min 𝑓𝑖𝑗 ⋅ 𝐵𝑗𝑖 (16a)

∑

(𝑐) 𝑖≠𝑐 𝜆𝑖 .

Erfaniantaghvayi et al.: Preprint submitted to Elsevier

We simulate wireless ad-hoc networks of || = 100 nodes generated from a 2D point process with a uniform density of 8∕𝜋 in a square area. Assuming beamforming antennas and uniform transmit power, we adopt a unit-disk graph model, in which two nodes are connected if their distance ≤ 1. This unitless graph abstraction is frequency-agnostic and ensures broad applicability across various physical layer specifications. By mitigating radio interference, this setup Page 7 of 14

Ant Backpressure Routing for Dynamic Wireless Multi-hop Networks

1

2

3 4 5 6 7 8 Bursty traffic load (Lb)

(a)

9

10

(b)

(Ls, Lb)

.0)

.0)

) 5.0

) 2.0

0.5

)

0.9950

0

20

10

(2. 0,

9

10

8

(1. 0,

3 4 5 6 7 Bursty traffic load (Lb)

5,

2

(0.

1

0,

0

)

0.90

1.0

1.0000 0.9975

20 0

0.92

(2.

40

0.94

0,

60

0.96

(1.

80

0.98

5,

100

1.00 0.99 0.98 0.97 0.96 0.95 0.94 0.93

(0.

120

1.00

Flow bursty streaming

Delivery ratio

Algo SP-BP Ant-BP Ant-BP-mirror Ant-Baseline Ant-ideal

Delivery Ratio

End-to-End Delay (time slots)

140

(c)

Figure 2: The average (a) end-to-end latency and (b) delivery ratio of tested routing policies as a function of bursty flow load 𝐿𝑏 in 10 random instances of wireless networks of 100 nodes under mixed traffic setting with a constant streaming load 𝐿𝑠 = 2.0. (c) The average delivery ratio of tested routing schemes in wireless networks of 100 nodes under mixed traffic with different loads shown in the x-axis. For Ant-based schemes, routing policies are established based on virtual traffic flows of (1.0, 1.0) and (1.0, 10.0) for the left and right sides, respectively.

yields a moderate network density with an average conflict graph degree of 13.86. We generate 100 test instances derived from 10 random topologies, each paired with 10 random realizations of source-destination pairs and stochastic link rates. Each instance features a uniformly random number of flows between ⌊0.15||⌋ and ⌈0.30||⌉. To capture fading channels with lognormal shadowing, OFDM-like wide-band waveforms, and power control, long-term link rates are drawn from a uniformly distribution 𝐫𝑒 ∼ 𝕌(10, 42), while real-time link rates fluctuate as 𝐫̀ 𝑒 (𝑡) ∼ ℕ(𝐫𝑒 , 32 ), truncated to 𝐫𝑒 ± 9. Simulations run for 𝑇 = 1000 time steps.1 We define two traffic types: streaming and bursty, with exogenous packet arrivals following a Poisson process. Streaming flows have a constant rate 𝐿𝑠 𝜆𝑠 throughout the simulation, where 𝜆𝑠 ∈ 𝕌(0.2, 1.0) and 𝐿𝑠 is the streaming load. Bursty flows operate at a rate 𝐿𝑏 𝜆𝑏 (with 𝜆𝑏 ∈ 𝕌(0.2, 1.0) and load 𝐿𝑏 ) strictly within a short active window [𝑡𝑠 , 𝑡𝑠 + 30], and 𝜆𝑏 = 0 otherwise. The burst start time 𝑡𝑠 is drawn uniformly from [0, 𝑇 − 100] for physical routing, and 𝑡𝑠 = 0 for virtual routing. In mixed traffic settings, a flow is configured as bursty with probability 𝑃𝑏 = 0.5. We evaluate two variations of Ant-BP against three baselines. For all policies utilizing shortest path biases, the biases {𝐵𝑖(𝑐) |𝑖, 𝑐 ∈ } are established via APSP on 𝑛 with edge weights 𝛿𝑒 = 𝑟̄𝑟max ∕𝑟𝑒 , ∀𝑒 ∈  [14, Sec. IV-B]. All virtual routing phases run for 𝐾 = 1000 time steps. 1. Ant-BP: Virtual flows are configured strictly as streaming with load 𝐿𝑠 , ignoring actual physical traffic profiles. 2. Ant-BP-mirror: Virtual flows perfectly replicate the rate and traffic type of their corresponding physical flows. 3. SP-BP: State-of-the-art SP-BP [13, 14] running directly on physical traffic with per-commodity queues. 4. Ant-Baseline: Routing policy established via ACO routing (Appendix A) in virtual phase and frozen during physical routing. Pheromones are initialized as 𝜌(𝑐) 𝑖𝑗 (0) = 1.3 and 1 The implementation details and source code for this study are available at https://github.com/Negar-Erfanian/AntBP.git.

Erfaniantaghvayi et al.: Preprint submitted to Elsevier

(𝑐) updated per time step by a constant 𝜃𝑖𝑗,𝑘 (𝜏) = 0.01 (with evaporation 𝜀 = 0.002). To align with Ant-BP, virtual routing probabilities follow (18):

𝑝(𝑐) 𝑖𝑗 (𝜏) = ∑

𝜌(𝑐) 𝑖𝑗 (𝜏) + 𝐵𝑖𝑗 ], [ (𝑐) 𝜌 (𝜏) + 𝐵 𝑖𝑙 𝑙∈𝑛 (𝑖) 𝑖𝑙

(17)

where 𝐵𝑖𝑗 = 𝐵𝑖−𝐵𝑗 (Sec. 4.1) acts as a heuristic link cost. 5. Ant-Ideal: Pheromones are initialized like Ant-Baseline but actively maintained during physical routing by proactive ants (sent per 100 data packets, with a 10% uniform ( ) exploration probability). The path cost 𝜙 𝑘(𝑐) in (19b) is ant 𝑘’s end-to-end latency, and pheromones update (see (19a)) instantaneously upon delivery, without backward ant propagation. Crucially, despite sharing the same 𝐾 steps of virtual routing, Ant-BP incurs significantly lower physical overhead than Ant-Baseline and Ant-Ideal, as it only exchanges packet counts rather than sending out actual ant packets.

6.2. Performance under Mixed Traffic and Injection Rate Uncertainties To evaluate routing quality and bursty-flow handling under mixed traffic, we test all schemes with a moderate fixed streaming load 𝐿𝑠 = 2.0 and varying bursty loads 𝐿𝑏 ∈ {0.5, 1, … , 10}. Because bursts occupy only a small fraction of the total time horizon (30∕𝑇 ), increasing the bursty load 𝐿𝑏 contributes only a limited amount of additional traffic. As a result, the synthetic latency2 and delivery ratios of streaming flows remain stable as 𝐿𝑏 increases, as illustrated by dashed lines in Figs. 2(a) and 2(b). For streaming flows, Ant-BP-mirror and Ant-BP achieve the best and second-best latency and delivery ratios, followed by SP-BP, Ant-Ideal, and Ant-Baseline. Their respective average delivery ratios are 0.974, 0.971, 0.968, 0.958, and 0.952. The latency of bursty flows is consistently higher and more sensitive to 𝐿𝑏 than streaming flows (solid lines in 2 By default, latency of undelivered packets is treated as 𝑇 , except for Section 6.5, where it is residency time (𝑇 −injection time)

Page 8 of 14

Fig. 2(a)), as bursty traffic lacks the persistent congestion gradients to drive queue-based Max-Weight scheduling. However, because bursty packets arrive entirely within the a window of 30 time slots starting at 𝑡𝑠 , most of them have sufficient time to reach their destinations within the simulation horizon 𝑇 = 1000, resulting in higher delivery ratios than streaming traffic (Fig. 2(b)). Ant-BP and Ant-BPmirror consistently outperform the ACO baselines across both metrics, demonstrating the superiority of virtual SPBP pathfinding over traditional ACO. Furthermore, their performance gains over SP-BP highlight the effectiveness of per-neighbor FIFO queues and link capacity sharing in mitigating the last-packet problem. Lower burst loads (𝐿𝑏 ≤ 3) present the most challenging starvation regime, where performance degrades for all schemes as 𝐿𝑏 decreases. SP-BP suffers the most severe degradation (e.g., a latency of 131.5 and delivery ratio of 0.906 at 𝐿𝑏 = 0.5) because of its exclusive commodity selection based on instantaneous congestion gradients. Conversely, Ant-BP avoids this starvation by allowing different commodities to share link capacity and per-neighbor queues in a FIFO fashion, achieving the best delivery ratio (0.975) and second-best latency (44.7) at 𝐿𝑏 = 0.5. Ant-BP-mirror ranks best overall for 𝐿𝑏 ≥ 2 by perfectly leveraging exact bursty flow knowledge. However, at 𝐿𝑏 = 0.5, its delivery ratio drops significantly to 0.925 because its exact virtual traffic replica also suffers the last-packet problem. By configuring all virtual flows as streaming, Ant-BP eliminates this issue, managing lightweight bursty traffic highly effectively at the cost of slight performance degradation under heavier loads compared to Ant-BP-mirror. To evaluate robustness against imperfect physical flow rate estimation, we test the ant-based schemes under physical flow rates that are half or double those used for route establishment (𝐿𝑠 = 1.0, 𝐿𝑏 = 1.0 and 𝐿𝑠 = 1.0, 𝐿𝑏 = 10.0). We compare these against SP-BP operating with exact instantaneous queueing state information. Despite these mismatches, the delivery ratio trends and scheme rankings (Fig. 2(c)) remain consistent with the exact-knowledge scenario (Fig. 2(b)), with Ant-BP and Ant-BP-mirror maintaining their lead. In the extreme heavy-traffic case (𝐿𝑠 = 2.0, 𝐿𝑏 = 20.0), SP-BP achieves slightly lower latency for both streaming (41.2 vs. 47.6 and 44.1) and bursty flows (79.8 vs. 92.3 and 82.1) due to its slot-by-slot management. Nonetheless, its delivery ratios remain similar for streaming traffic and slightly worse for bursty flows compared to the Ant-BP variants. These results confirm that Ant-BP and AntBP-mirror routing policies are highly robust to mismatched virtual flow configurations.

6.3. Goodput under Streaming Stress Tests We evaluate network goodput (end-to-end throughput defined as total delivered packets per time slot) of four schemes under a pure streaming traffic setting (Ant-BPmirror and Ant-BP are equivalent in this setting), across

Erfaniantaghvayi et al.: Preprint submitted to Elsevier

Network Throughput (# pkts/slot)

Ant Backpressure Routing for Dynamic Wireless Multi-hop Networks

100 80

SP-BP Ant-BP Ant-Baseline Ant-ideal

60 40 20 0

40 30 20 10

0 1 2 3 4 5 6 7 8 9 10 11 12 Streaming traffic load (Ls)

Figure 3: Average network goodput (network-wide number of packets delivered per time slot) of routing schemes on wireless networks with 100 nodes under all streaming traffic as a function of traffic load 𝐿𝑠 .

loads 𝐿𝑠 ∈ {0.5, 1, 2, … , 12}. As shown in Fig. 3, AntBP achieves similar or slightly higher goodput than SPBP at lower loads (𝐿𝑠 ≤ 3), but averages only 84.4% of the goodput of SP-BP for 𝐿𝑠 > 3. This divergence occurs because Ant-BP’s link capacity sharing yields limited benefits for uniform streaming traffic, whereas the instantaneous queue-based resource allocation of SP-BP excels at managing heavy congestion. Combined with earlier results, this confirms that Ant-BP significantly improves bursty traffic handling without compromising goodput under low-tomedium streaming intensities. Additionally, Ant-Ideal surpasses Ant-BP in goodput at extreme loads (𝐿𝑠 ≥ 10) by leveraging cost-based pheromone deposits and continuous proactive route maintenance. This suggests that incorporating dynamic route maintenance into Ant-BP could further enhance its heavy-traffic scalability.

6.4. Resilience under Transient Link Failure We model transient link failure occurring after scheduling in (3) but before transmission, evaluating three disruption models. In All-Links, every link fails independently per time slot with a random probability 𝑝𝑒 ∈ 𝕌(0, 0.05) fixed throughout the simulation. In BW-Persist, we target the top 5% of links by edge betweenness centrality on the connectivity graph 𝑛 . Failure events on these critical links arrive via a Poisson process with rate 𝜆𝑒 = 𝑝𝑒∕𝐷avg , and persist for a normally distributed duration centered at 𝐷avg = 20 time slots. In such failure events, transmission fails at a fixed probability 𝑝𝑒 ∈ 𝕌(0, 0.05). In Local-Persist, this same stochastic failure pattern applies to all links within a randomly selected circular region encompassing 5 − 6% of network nodes. Upon any transmission failure, the affected packets revert to an unscheduled state for that time slot. For all ant-based schemes, the pheromone level on the failed link also decays by 5% to discourage their subsequent selections. To evaluate resilience, we simulate a mixed traffic setting with a fixed streaming load 𝐿𝑠 = 1.0 and varying bursty loads 𝐿𝑏 ∈ {0.5, 1, 2, … , 10}, and present their Page 9 of 14

80 60 40 20 0

1

2

3 4 5 6 7 Bursty traffic load (Lb)

8

9

End-to-End Delay (time slots)

175

100

End-to-End Delay (time slots)

End-to-End Delay (time slots)

Ant Backpressure Routing for Dynamic Wireless Multi-hop Networks

150 125 100

10

75 50 25 0

1

2

3 4 5 6 7 Bursty traffic load (Lb)

9

70 60 50 40 30 20 10

10

0

1

0.98

0.98

0.98

0.96

0.96

0.96

0.94 0.92

0.86 0

1

2

Algo SP-BP Ant-BP Ant-BP-mirror Ant-Baseline

Ant-ideal Flow bursty streaming

3 4 5 6 7 8 Bursty traffic load (Lb)

9

10

Delivery Ratio

1.00

0.88

3 4 5 6 7 Bursty traffic load (Lb)

8

9

10

3 4 5 6 7 8 Bursty traffic load (Lb)

9

10

(c)

1.00

0.90

2

(b)

1.00

Delivery Ratio

Delivery Ratio

(a)

8

80

0.94 0.92 0.90 0.88

0.94 0.92 0.90 0.88

0.86 0

1

2

3 4 5 6 7 8 Bursty traffic load (Lb)

(d)

9 10

0.86

0

1

2

(e)

(f)

Figure 4: The average (a, b, c) end-to-end latency and (d, e, f) delivery ratio of tested routing policies as a function of bursty flow load 𝐿𝑏 in 10 random instances of wireless networks of 100 nodes under mixed traffic setting with a constant streaming load 𝐿𝑠 = 1.0. Subfigures (a, d), (b, e), and (c, f) correspond to the All-Links, BW-Persist, and Local-Persist link failure scenarios, respectively.

average end-to-end latency and delivery ratios as a function of 𝐿𝑏 in Figs. 4. Across all three failure scenarios, Ant-BP and Ant-BP-mirror consistently experience the least performance degradation, maintaining significantly lower delays and higher delivery ratios than the baseline schemes. Under independent All-Links failures (Figs. 4(a) and 4(d)), the gradient-based pathfinding of Ant-BP and Ant-BPmirror yields decreasing delays and increasing delivery ratios for heavier bursty loads (𝐿𝑏 ≥ 7.0), comfortably outperforming the Ant-Baseline and Ant-Ideal. This stability advantage becomes highly pronounced under BW-Persist failures (Figs. 4(b) and 4(e)), where failures on critical links severely degrade the performance of Ant-Baseline and Ant-Ideal, underscoring their vulnerability to disruptions on critical paths. While the ACO baselines appear relatively robust to the randomized Local-Persist failures (Figs. 4(c) and 4(f)), the strictly gradient-dependent SP-BP suffers severe starvation at low bursty loads (𝐿𝑏 ≤ 3.0), causing significant performance drops. Conversely, at these extremely low burst loads (𝐿𝑏 ≤ 1.0), Ant-BP achieves higher bursty delivery rates than Ant-BP-mirror across all failure models. This confirms the structural advantage of mapping lightweight bursty traffic to continuous virtual streaming flows, which stabilizes path formation and significantly mitigates the lastpacket problem even in highly disruptive environments.

Erfaniantaghvayi et al.: Preprint submitted to Elsevier

Table 1 Link removal ratios across mobility levels. Mobile Nodes

10

20

30

40

50

60

Link Removal

16.6%

33.3%

48.5%

61.0%

71.6%

80.4%

6.5. Adaptation under Note Mobility We simulate node mobility using a constrained Gaussian random walk model, relocating a random subset of nodes (e.g., {10, 20, 30, 40, 50, 60}) during physical routing with 2D steps drawn from ℕ(𝟎, 0.12 𝐈). Crucially, these perturbations are bounded within the 2D square and restricted to preserve the connectedness of the network (e.g., 𝑛 ), while causing some existing links break and new ones form at high probabilities. The link removal ratios by mobility levels are listed in Table 1. Following the mobility adaptation mechanisms in Sec. 4.3, stranded packets are remapped as virtual sources during the subsequent virtual routing phase to adaptively redistribute traffic and backlogs across the updated topology. In our simulation horizon (𝑇 = 2000), mobility triggers at 𝑡 = 500, prompting the scheduled virtual routing phase at 𝑡 = 600. To account for signaling overhead, physical routing is paused for 𝑇 ′ = 10 time slots while virtual routing executes for 𝐾 = 1000 steps. During this pause, newly arriving exogenous packets are queued at their source nodes, and physical routing resumes at 𝑡 = 610 with the updated pheromones. The choice of 𝑇 ′ depends on the actual MaxWeight scheduling overhead. Page 10 of 14

102

End-to-End Delay (time slots)

Algo SP-BP Ant-BP Ant-BP-novirt Ant-Baseline Ant-ideal

102

102

0

10

20 30 40 Mobility Nodes

50

60

Arrival Time (mid-bin)

(a)

(b)

0 10 200 300 400 500 600 700 800 900 10 0 1100 1200 1300 1400 1500 00

101

0 10 0 20 300 400 500 600 700 800 900 10 0 1100 1200 1300 1400 1500 00

End to End Delay (time slots)

103

End-to-End Delay (time slots)

Ant Backpressure Routing for Dynamic Wireless Multi-hop Networks

Delivered Time (mid-bin) (c)

Figure 5: The average (a) end-to-end latency of all packets as a function of mobility level (number of mobile nodes), (b) end-to-end latency of delivered packets as a function of packet arrival time (binned in ranges of 50), and (c) end-to-end latency of delivered packets as a function of packet delivery time (binned in ranges of 50) for tested routing policies in 10 random instances of wireless networks of 100 nodes under streaming traffic setting with a constant streaming load 𝐿𝑠 = 0.5.

Although the evaluation only covers node movements in a single update cycle, this periodical process naturally extends to continuous long-term horizons and dynamic node churn (i.e., joining/leaving networks). In addition, pure streaming traffic is used and the number of flows is drawn uniformly between 15 and 30. We compare Ant-BP against SP-BP, Ant-Baseline, AntIdeal, and an ablation variant, Ant-BP-novirt, which lacks periodic virtual updates (new links instead initialize with the mean pheromone value, and 𝑇 ′ = 0). Fig. 5(a) presents the end-to-end delay in a logarithmic scale as a function of mobile nodes. The streaming load is 𝐿𝑠 = 0.5, and the latency of undelivered packets is set as their residency time (𝑇 − injection time). As expected, delay increases with the mobility degree, which induces link removal ratios ranging from 16.6% (10 mobile nodes) to 80.4% (60 mobile nodes). Ant-BP achieves the best performance across all mobility levels, whereas Ant-BP-novirt severely degrades even under mild mobility (delay of 358.5 time slots at 10 mobile nodes), isolating periodic virtual routing as the key mechanism for topology adaptation. While SP-BP and Ant-Ideal handle mild mobility well, their strict gradient reliance and pathdependent updates, respectively, cause them to falter at higher mobility degrees (> 20 and > 40 nodes), where AntBaseline slightly outperforms. In the extreme 60-node scenario, Ant-BP establishes the lowest delay (37.2), decisively outperforming Ant-Baseline (54.5), Ant-Ideal (61.7), SP-BP (61.9), and Ant-BP-novirt (1231.6). Unlike the immediate per-link updates of Ant-Baseline, Ant-Ideal relies on end-to-end path-cost evaluations via proactive ants, rendering its pheromone distributions highly sensitive to mobility-induced link breakages. Furthermore, Ant-Baseline’s superior resilience compared to SP-BP at higher mobility degrees underscores the inherent advantage of probabilistic multi-path routing over strictly gradientdependent methods in highly dynamic environments. We further analyze the temporal evolution of delivered packets in the extreme 60-node scenario, by presenting the end-to-end delay as a function of packet injection time (Fig. 5(b)) and delivery time (Fig. 5(c)). In these plots, the Erfaniantaghvayi et al.: Preprint submitted to Elsevier

time horizon is divided into discrete bins of 50 time slots (represented by their mid-bin values) to capture the moving average of routing delay across the adaptation timeline. In Fig. 5(b), all schemes exhibit a sharp delay peak for packets injected immediately prior to the 𝑡 = 500 topology shift. Following this event, the delay of AntBP-novirt remains permanently elevated, demonstrating the catastrophic failure of static probabilistic fields under topological changes. Conversely, the slot-by-slot dynamic SP-BP recovers quickly, showing a drop in delay for packets injected shortly after the shift, but ultimately plateaus at a persistently higher delay (≈ 34.4) post-adaptation. The periodic schemes (Ant-BP, Ant-Baseline, and Ant-Ideal) experience escalating delays for packets arriving during the 𝑡 ∈ [500, 600] window, but exhibit dramatic recovery for packets injected after the 𝑡 = 610 virtual update. Ultimately, Ant-BP achieves the absolute lowest delay for packets arriving post-adaptation (≈ 19.0), comfortably outperforming Ant-Baseline (≈ 27.2) and Ant-Ideal (≈ 27.4). From the perspective of delivery time (Fig. 5(c)), the delay surge for the periodic ant-based methods appears broader, spanning the 525 ≤ mid-bin ≤ 625 window. This prolonged hump reflects the gradual flushing of stranded packets that lingered in the network while awaiting the 𝑡 = 610 topology update, whereas the delivery delays of SP-BP remain entirely steady after its initial spike. However, once these transient backlogs clear post-adaptation, Ant-BP conclusively yields the lowest delivery delay, followed by AntBaseline, SP-BP, and Ant-Ideal. Collectively, these temporal dynamics reveal a fundamental routing trade-off: while strict gradient-based routing (SP-BP) provides immediate reactivity to mobility, it often settles into less efficient long-term paths. By absorbing temporary congestion while awaiting a structured virtual update, Ant-BP establishes superior, globally optimal routing probabilities that definitively minimize long-term latency in dynamic networks.

Page 11 of 14

Ant Backpressure Routing for Dynamic Wireless Multi-hop Networks

7. Conclusions and Future Work

CRediT authorship contribution statement

In this paper, we introduce Ant Backpressure (Ant-BP) routing, a distributed framework bridging the theoretical optimality and efficiency of gradient-based routing with the practical constraints of legacy forwarding architectures. By enabling efficient link-capacity sharing and mapping short-lived bursty traffic into virtual streaming flows, AntBP structurally eliminates the last-packet problem inherent to SP-BP. Furthermore, Ant-BP demonstrates superior resilience in highly dynamic mobile environments. It gracefully mitigates the disruptions from transient link failures that typically plague reactive protocols, and under extreme mobility scenarios, its periodic virtual routing mechanism trades temporary congestion for globally superior probabilistic paths. This yields significantly lower long-term latency than the myopic, slot-by-slot reactions of SP-BP. The primary trade-off for this architectural simplicity is a slight goodput reduction under heavy traffic compared to SP-BP. Future work will explore proactive route maintenance to enhance scalability and address continuous dynamic node churn in realistic deployments. Additionally, our approach to approximating constrained multi-commodity min-cost flow (MCMCF) problems sheds light on resolving non-linearity induced by resource contention, offering insights not only for wireless routing but also for broader domains such as edge computing.

Negar Erfaniantaghvayi: Methodology, software, investigation, validation, writing – original draft. Zhongyuan Zhao: Conceptualization, methodology, software, formal analysis, supervision, writing – original draft, writing – review & editing. Kevin Chan: Conceptualization, validation, writing – review & editing. Ananthram Swami: Conceptualization, resources, writing – review & editing. Santiago Segarra: Supervision, project administration, funding acquisition, writing – review & editing.

A. Ant Colony Optimization The baseline ACO heuristic updates routing policy as follows. At time step 𝑡, a data packet that has arrived at a nondestination node 𝑖 ∈  is assigned to one of its neighbors 𝑗 ∈ 𝑛 (𝑖) with probability 𝑝(𝑐) 𝑖𝑗 (𝑡) given by [36] 𝑝(𝑐) 𝑖𝑗 (𝑡) = ∑

[ (𝑐) ]𝛼 𝛽 𝜌𝑖𝑗 (𝑡) ⋅ ℎ𝑖𝑗 [ (𝑐) ]𝛼 𝛽 , 𝑙∈𝑛 (𝑖) 𝜌𝑖𝑙 (𝑡) ⋅ ℎ𝑖𝑙

(18)

where 𝜌(𝑐) 𝑖𝑗 (𝑡) is the pheromone intensity associated with commodity 𝑐 on link (𝑖, 𝑗) at time step 𝑡, ℎ𝑖𝑗 is a heuristic cost of link (𝑖, 𝑗), and 𝛼 and 𝛽 are parameters for tuning the importance of the pheromone intensity and cost. Assuming that 𝑚(𝑐, 𝑡) ants reach destination 𝑐 at time step 𝑡, the pheromone intensity is updated as [36] (𝑐) 𝜌(𝑐) 𝑖𝑗 (𝑡 + 1) = (1 − 𝜀) ⋅ 𝜌𝑖𝑗 (𝑡) +

𝑚(𝑐,𝑡) ∑

(𝑐) 𝜃𝑖𝑗,𝑘 (𝑡),

(19a)

𝑘=1

⎧[

]−1

( ) ⎪ 𝜙  (𝑐) (𝑐) 𝑘 𝜃𝑖𝑗,𝑘 (𝑡) = ⎨ ⎪0, ⎩

, if (𝑖, 𝑗) ∈ 𝑘(𝑐) if (𝑖, 𝑗) ∉ 𝑘(𝑐)

, (19b)

(𝑐) where 𝜀 is the evaporation rate, 𝜃𝑖𝑗,𝑘 (𝑡) is the amount of

pheromone deposited by the 𝑘th ant, 𝑘(𝑐) is the path of the ( ) 𝑘th ant, and 𝜙 𝑘(𝑐) is the cost function of path 𝑘(𝑐) . Erfaniantaghvayi et al.: Preprint submitted to Elsevier

Acknowledgments Research was sponsored by the U.S. Army Combat Capabilities Development Command (DEVCOM) Army Research Office and was accomplished under Cooperative Agreement Number W911NF-24-2-0008 and W911NF-192-0269. The views and conclusions contained in this document are those of the authors and should not be interpreted as representing the official policies, either expressed or implied, of the Army Research Office or the U.S. Government. The U.S. Government is authorized to reproduce and distribute reprints for Government purposes notwithstanding any copyright notation herein.

References [1] N. Erfaniantaghvayi, Z. Zhao, K. Chan, G. Verma, A. Swami, S. Segarra, Ant backpressure routing for wireless multi-hop networks with mixed traffic patterns, in: IEEE Military Communications Conference (MILCOM), Washington DC, USA, 2024, pp. 1174– 1179. doi:10.1109/MILCOM61039.2024.10774011. [2] X. Lin, N. B. Shroff, R. Srikant, A tutorial on cross-layer optimization in wireless networks, IEEE J. Sel. Areas Commun. 24 (2006) 1452– 1463. [3] S. K. Sarkar, T. G. Basavaraju, C. Puttamadappa, Ad hoc Mobile Wireless Networks: Principles, Protocols and Applications, CRC Press, 2013. [4] N. Patriciello, C. A. Grazia, J. Núñez-Martínez, J. Baranda, J. Mangues-Bafalluy, M. Casoni, Performance evaluation of backpressure routing in integrated satellite-terrestrial backhaul for PPDR networks, in: IEEE Intl. Conf. on Wireless and Mobile Computing, Netw. and Communs. (WiMob), 2016, pp. 1–8. doi:10.1109/WiMOB. 2016.7763187. [5] A. Kott, A. Swami, B. J. West, The internet of battle things, Computer 49 (2016) 70–75. [6] M. Cudak, A. Ghosh, A. Ghosh, J. Andrews, Integrated access and backhaul: A key enabler for 5G millimeter-wave deployments, IEEE Communications Magazine 59 (2021) 88–94. doi:10.1109/MCOM.001. 2000690. [7] I. F. Akyildiz, A. Kak, S. Nie, 6G and beyond: The future of wireless communications systems, IEEE Access 8 (2020) 133995–134030. [8] L. Tassiulas, A. Ephremides, Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks, in: IEEE Conf. on Decision and Control, IEEE, 1990, pp. 2130–2132. [9] J. Ryu, L. Ying, S. Shakkottai, Back-pressure routing for intermittently connected networks, in: 2010 Proceedings IEEE INFOCOM, IEEE, 2010, pp. 1–5. [10] L. Georgiadis, M. J. Neely, L. Tassiulas, Resource allocation and cross-layer control in wireless networks, Foundations and Trends® in Networking 1 (2006) 1–144.

Page 12 of 14

Ant Backpressure Routing for Dynamic Wireless Multi-hop Networks [11] M. J. Neely, E. Modiano, C. E. Rohrs, Dynamic power allocation and routing for time-varying wireless networks, IEEE J. Sel. Areas Commun. 23 (2005) 89–103. doi:10.1109/JSAC.2004.837349. [12] Z. Zhao, B. Radojicic, G. Verma, A. Swami, S. Segarra, Delay-aware backpressure routing using graph neural networks, in: IEEE Intl. Conf. on Acoustics, Speech and Signal Process. (ICASSP), 2023, pp. 4720–4724. [13] Z. Zhao, G. Verma, A. Swami, S. Segarra, Enhanced backpressure routing using wireless link features, in: IEEE Intl. Wrksp. Computat. Advances Multi-Sensor Adaptive Process. (CAMSAP), 2023, pp. 1– 5. doi:10.1109/CAMSAP58922.2023.10403470. [14] Z. Zhao, B. Radojičić, G. Verma, A. Swami, S. Segarra, Biased Backpressure routing using link features and graph neural networks, IEEE Transactions on Machine Learning in Communications and Networking (2024) 1424 – 1439. [15] Z. Jiao, B. Zhang, W. Gong, H. Mouftah, A virtual queue-based back-pressure scheduling algorithm for wireless sensor networks, EURASIP J. on Wireless Commun. and Netw. 2015 (2015) 1–9. [16] S. Moeller, A. Sridharan, B. Krishnamachari, O. Gnawali, Routing without routes: The backpressure collection protocol, in: Proceedings of the 9th ACM/IEEE International Conference on Information Processing in Sensor Networks, 2010, pp. 279–290. [17] M. Alresaini, K.-L. Wright, B. Krishnamachari, M. J. Neely, Backpressure delay enhancement for encounter-based mobile networks while sustaining throughput optimality, IEEE/ACM Trans. Netw. 24 (2016) 1196–1208. doi:10.1109/TNET.2015.2404331. [18] B. Ji, C. Joo, N. B. Shroff, Delay-based back-pressure scheduling in multihop wireless networks, IEEE/ACM Trans. Netw. 21 (2012) 1539–1552. [19] C. Liaskos, K. Alexandris, A. Das, S. Tang, L. Tassiulas, Analysis and evaluation of fully TCP-compatible backpressure-driven traffic engineering, IEEE Trans. on Netw. Science and Eng. 10 (2023) 4056– 4070. [20] C. Joo, N. B. Shroff, Local greedy approximation for scheduling in multihop wireless networks, IEEE Trans. Mobile Computing 11 (2011) 414–426. [21] Z. Zhao, G. Verma, C. Rao, A. Swami, S. Segarra, Link scheduling using graph neural networks, IEEE Trans. Wireless Commun. 22 (2023) 3997–4012. [22] Z. Zhao, Y. Ming, A. Swami, K. Chan, F. Dagefu, S. Segarra, Generalizing biased backpressure routing and scheduling to wireless multi-hop networks with advanced air-interfaces, arXiv preprint arXiv:2504.21721, 2025. Preprint. [23] L. X. Bui, R. Srikant, A. Stolyar, A novel architecture for reduction of delay and queueing structure complexity in the back-pressure algorithm, IEEE/ACM Trans. Netw 19 (2011) 1597–1609. doi:10. 1109/TNET.2011.2126593. [24] C. Liaskos, K. Alexandris, A. Das, S. Tang, L. Tassiulas, Analysis and evaluation of fully tcp-compatible backpressure-driven traffic engineering, IEEE Transactions on Network Science and Engineering 10 (2023) 4056–4070. doi:10.1109/TNSE.2023.3282642. [25] J. T. Moy, OSPF: anatomy of an Internet routing protocol, AddisonWesley Professional, 1998. [26] N. McKeown, T. Anderson, H. Balakrishnan, G. Parulkar, L. Peterson, J. Rexford, S. Shenker, J. Turner, Openflow: enabling innovation in campus networks, ACM SIGCOMM computer communication review 38 (2008) 69–74. [27] D. Kreutz, F. M. Ramos, P. E. Verissimo, C. E. Rothenberg, S. Azodolmolky, S. Uhlig, Software-defined networking: A comprehensive survey, Proceedings of the IEEE 103 (2014) 14–76. [28] C. A. Oliveira, P. M. Pardalos, et al., Mathematical aspects of network routing optimization, volume 53, Springer, 2011. [29] M. Abolhasan, T. Wysocki, E. Dutkiewicz, A review of routing protocols for mobile ad hoc networks, Ad hoc networks 2 (2004) 1–22. [30] I. Chlamtac, M. Conti, J. J.-N. Liu, Mobile ad hoc networking: imperatives and challenges, Ad hoc networks 1 (2003) 13–64.

Erfaniantaghvayi et al.: Preprint submitted to Elsevier

[31] I. T. Haque, N. Abu-Ghazaleh, Wireless software defined networking: A survey and taxonomy, IEEE Communications Surveys & Tutorials 18 (2016) 2713–2737. [32] P. Vinayakray-Jani, S. Sanyal, Routing protocols for mobile and vehicular ad-hoc networks: A comparative analysis, arXiv preprint arXiv:1206.1918 (2012). [33] A. Aggarwal, S. Gandhi, N. Chaubey, Performance analysis of AODV, DSDV and DSR in MANETs, International Journal of Distributed and Parallel Systems 2 (2011). [34] G. Di Caro, F. Ducatelle, L. M. Gambardella, AntHocNet: an adaptive nature-inspired algorithm for routing in mobile ad hoc networks, European Trans. Telecommunications 16 (2005) 443–455. [35] P. Purkayastha, J. S. Baras, Convergence results for ant routing algorithms via stochastic approximation, ACM Trans. Auton. Adapt. Syst. 8 (2013). URL: https://doi.org/10.1145/2451248.2451251. doi:10. 1145/2451248.2451251. [36] H. Zhang, X. Wang, P. Memarmoshrefi, D. Hogrefe, A survey of ant colony optimization based routing protocols for mobile ad hoc networks, IEEE Access 5 (2017) 24139–24161. [37] M. Dorigo, T. Stützle, Ant colony optimization: overview and recent advances, Springer, 2019. [38] D. B. Johnson, D. A. Maltz, Dynamic source routing in ad hoc wireless networks, in: Mobile computing, Springer, 1996, pp. 153– 181. [39] D. B. Johnson, D. A. Maltz, J. Broch, et al., Dsr: The dynamic source routing protocol for multi-hop wireless ad hoc networks, Ad hoc networking 5 (2001) 139–172. [40] R. Leung, J. Liu, E. Poon, A.-L. Chan, B. Li, Mp-dsr: a qosaware multi-path dynamic source routing protocol for wireless ad-hoc networks, in: Proceedings LCN 2001. 26th Annual IEEE Conference on Local Computer Networks, IEEE, 2001, pp. 132–141. [41] S.-J. Lee, E. M. Belding-Royer, C. E. Perkins, Scalability study of the ad hoc on-demand distance vector routing protocol, International journal of network management 13 (2003) 97–114. [42] T. Saravanan, N. Nithya, Modeling displacement and direction aware ad hoc on-demand distance vector routing standard for mobile ad hoc networks, Mobile Networks and Applications 24 (2019) 1804–1813. [43] M. K. Marina, S. R. Das, On-demand multipath distance vector routing in ad hoc networks, in: Proceedings ninth international conference on network protocols. ICNP 2001, IEEE, 2001, pp. 14–23. [44] E. M. Royer, C. E. Perkins, Multicast operation of the ad-hoc ondemand distance vector routing protocol, in: Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking, 1999, pp. 207–218. [45] A. A. Bhorkar, M. Naghshvar, T. Javidi, B. D. Rao, Adaptive opportunistic routing for wireless ad hoc networks, IEEE/ACM Transactions On Networking 20 (2011) 243–256. [46] Z. Zhang, R. Krishnan, An overview of opportunistic routing in mobile ad hoc networks, in: MILCOM 2013-2013 IEEE Military Communications Conference, IEEE, 2013, pp. 119–124. [47] N. Chakchouk, A survey on opportunistic routing in wireless communication networks, IEEE Communications Surveys & Tutorials 17 (2015) 2214–2241. [48] S. Biswas, R. Morris, Exor: Opportunistic multi-hop routing for wireless networks, in: Proceedings of the 2005 conference on Applications, technologies, architectures, and protocols for computer communications, 2005, pp. 133–144. [49] Z. Wang, Y. Chen, C. Li, Corman: A novel cooperative opportunistic routing scheme in mobile ad hoc networks, IEEE journal on selected areas in communications 30 (2012) 289–296. [50] A. Bhorkar, M. Naghshvar, T. Javidi, Opportunistic routing with congestion diversity in wireless ad hoc networks, IEEE/ACM Transactions on Networking 24 (2015) 1167–1180. [51] T. Kathiravelu, N. Ranasinghe, A. Pears, An enhanced congestion aware adaptive routing protocol for opportunistic networks, in: 2011 6th International Conference on Industrial and Information Systems, IEEE, 2011, pp. 210–215.

Page 13 of 14

Ant Backpressure Routing for Dynamic Wireless Multi-hop Networks [52] M. Shelke, A. Malhotra, P. N. Mahalle, Congestion-aware opportunistic routing protocol in wireless sensor networks, in: Smart Computing and Informatics: Proceedings of the First International Conference on SCI 2016, Volume 1, Springer, 2017, pp. 63–72. [53] I. Sharma, K. Ramkumar, A survey on aco based multipath routing algorithms for ad hoc networks, International Journal of Pervasive Computing and Communications 13 (2017) 370–385. [54] S. U. Rehman, M. A. Khan, T. A. Zia, A. Y. Zomaya, Joint rate and queue based routing for vehicular ad-hoc networks, in: 2016 IEEE 41st Conference on Local Computer Networks Workshops (LCN Workshops), IEEE, 2016, pp. 165–172. [55] M. Naseem, C. Kumar, Queue-based multiple path load balancing routing protocol for manets, International Journal of Communication Systems 30 (2017) e3141. [56] L. A. Maglaras, D. Katsaros, Delay efficient backpressure routing in wireless ad hoc networks, EAI Endorsed Transactions on Mobile Communications and Applications 1 (2014). [57] L. Hai, Q. Gao, J. Wang, H. Zhuang, P. Wang, Delay-optimal backpressure routing algorithm for multihop wireless networks, IEEE Transactions on Vehicular Technology 67 (2018) 2617–2630. [58] C. Shan, Y. Xia, Z. Guo, G. Wang, J. Zhang, Tsbs: A two-stage backpressure scheduling scheme over multihop wireless networks, Ad Hoc Networks 132 (2022) 102874. [59] V. Kawadia, P. R. Kumar, A cautionary perspective on cross-layer design, Wireless Commun. 12 (2005) 3–11. doi:10.1109/MWC.2005. 1404568. [60] J. Yang, S. C. Draper, R. Nowak, Learning the interference graph of a wireless network, IEEE Trans. Signal Inf. Process. Netw. 3 (2016) 631–646. [61] P. Varaiya, Max pressure control of a network of signalized intersections, Transportation Research Part C: Emerging Technologies 36 (2013) 177–195. [62] M. W. Levin, Max-pressure traffic signal timing: A summary of methodological and experimental results, Journal of Transportation Engineering, Part A: Systems 149 (2023) 03123001. doi:10.1061/ JTEPBS.TEENG-7578. [63] C. Joo, G. Sharma, N. B. Shroff, R. R. Mazumdar, On the complexity of scheduling in wireless networks, EURASIP J. on Wireless Commun. and Netw. 2010 (2010) 1–13. [64] M. Neely, Stochastic network optimization with application to communication and queueing systems, Morgan & Claypool Publishers, 2010.

Erfaniantaghvayi et al.: Preprint submitted to Elsevier

Page 14 of 14