Pruning-Accelerated Quantum-Inspired QUBO Routing for Space-Air-Ground Integrated Networks
ID:98
Submission ID:48 View Protection:ATTENDEE
Updated Time:2026-10-04 23:39:53 Hits:171
In-person
Abstract
Routing in Space-Air-Ground Integrated Networks (SAGIN) demands multi-commodity optimization over fluid 3D topologies. Shortest-path heuristics treat links independently, incurring overlapping capacity penalties. Conversely, dense combinatorial formulations waste variables on edges outside communication range. We introduce Sparse-QUBO-Route, a QuantumInspired routing framework. Per epoch, it prunes distanceinfeasible edges using a Conformal Geometric Algebra (CGA) predicate. It encodes the remaining multi-commodity problem as a temporally regularized Quadratic Unconstrained Binary Optimization (QUBO) instance, which is solved by a warmstarted Quantum-Inspired Evolutionary Algorithm (QiEA). The framework is evaluated on a synthetic SAGIN testbed against OSPF, capacity-aware CSPF, and an unpruned Vanilla QUBO under a common True Cost metric, on grids up to N=50 nodes at K=2 and K=5 concurrent flows at N=26, with an exact bruteforce/MILP reference at N=5. Geometric pruning removes 25– 53% of QUBO variables, yielding 1.57×–2.72× runtime speedups (up to ≈ 3.3× at RUAV=40 km). Under bottleneck congestion (Ce=2), Sparse-QUBO-Route attains markedly lower True Cost than capacity-unaware OSPF (+12.15±2.32 vs. +40.51; 10 seeds, Wilcoxon p=0.002). However, capacity-aware CSPF achieves the lowest cost (−10.85 ± 2.63). Three findings are negative: warmstarting fails to improve route stability, the CGA filter is 7.9× slower per call than a Euclidean equivalent, and the QUBO advantage over OSPF vanishes on a less-congested multi-LEO topology. Pruning primarily buys runtime rather than route quality. The QUBO benefit is congestion-dependent, scoping Sparse-QUBO-Route to single-bottleneck backhauls where a capacity-aware sequential baseline is unavailable.
Keywords
Space-Air-Ground Integrated Networks (SAGIN),Quadratic Unconstrained Binary Optimization (QUBO),Quantum-Inspired Evolutionary Algorithm (QiEA),conformal geometric algebra (CGA),multi-commodity routing
Submission Author
Truong Duy Dinh
Posts and Telecommunications Institute of Technology
Phuc Hao Do
Danang Architecture University
Van Dai Pham
Swinburne Vietnam, FPT University
Thi Hong Dao
Posts and Telecommunications Institute of Technology
Tran Duc Le
University of Wisconsin-Stout Polytechnic
Comment submit