A Per-Action Structured D3QN-Based Hierarchical Routing Algorithm for LEO Mega-Constellation Networks
TL;DR
This paper fuses deterministic inter-domain planning with DRL-based intra-domain forwarding in a single hierarchical framework and develops a greedy–beam–Dijkstra fallback ladder that guarantees reachability whenever the subgraph stays connected.
Abstract
Low Earth orbit (LEO) mega-constellations demand scalable routing that survives time-varying topologies, constrained onboard resources, and dynamic traffic. Deterministic shortest-path routing guarantees optimal paths but adapts poorly to real-time loads; distributed deep reinforcement learning (DRL) can introduce loops and inconsistent end-to-end decisions. This paper fuses deterministic inter-domain planning with DRL-based intra-domain forwarding in a single hierarchical framework. An evolutionary greedy algorithm partitions the constellation into compact domains. Dijkstra’s algorithm then computes backbone paths on the domain-level graph. Inside each domain, a context-enhanced Per-Action Dueling Double Deep Q-Network encodes individual neighbors through a weight-shared encoder and summarizes the valid-neighbor set via masked mean pooling. This design lets the policy compare a candidate against the current alternative set without injecting input-order bias. Local one- and two-hop topological features drive decentralized inference. A greedy–beam–Dijkstra fallback ladder guarantees reachability whenever the subgraph stays connected. On a 1584-satellite Starlink Gen1-1 topology, all 21 domain sizes and six inter-domain strategies reach 100% of test pairs; the best average hop count sits at 1.16× the global Dijkstra benchmark. Under an identical 52-dimensional state and training pipeline on 1000 held-out source–destination pairs, Context Per-Action uses 75.8% fewer parameters than a flat multilayer perceptron (MLP), lifts greedy success from 74.6% to 83.5%, and lifts greedy-plus-beam success from 88.3% to 94.5% (means over three independent training seeds). Centralized load-aware routing under dynamic traffic cuts high-load packet loss from 34–73% to 0–9.5% in the adopted flow-level model and preserves 99.2% reachability despite 30% link failures. Zero-shot transfer from ideal Walker topologies to real two-line element (TLE) snapshots and purely local load adaptation remain open; multi-snapshot training or online adaptation is the necessary next step.