Local Graph-Aware Hop-by-Hop Routing for Dynamic LEO Satellite Networks

Abstract

Low Earth orbit (LEO) satellite networks exhibit rapidly changing topology and time-varying traffic hotspots, which makes hop-by-hop routing highly sensitive to local congestion and state staleness. Existing routing methods either rely on global path computation or use plain local observations, while graph-enhanced approaches often focus on generic neighborhood representation rather than direct comparison among candidate next hops. To address this issue, this paper proposes a Local Graph-Aware Routing method (LGAR) for dynamic LEO satellite networks. LGAR organizes the current node, reachable candidate neighbors, and candidate links into a local graph, and then constructs structured action representations through node encoding, relation message extraction, and attention-based context aggregation. The resulting representations are integrated into an off-policy actor-critic framework to support adaptive hop-by-hop routing decisions. Experiments under the hub-inversion setting show that LGAR achieves an average total delay of 47.64 ms and an average queueing delay of 5.81 ms while maintaining a delivery rate of 99.93%. Compared with MATMR, LGAR-NoGraph, and GRLR, LGAR reduces the average total delay by 12.38%, 12.85%, and 30.75%, respectively. Additional scenario, ablation, and scalability results further show that LGAR generalizes beyond the main setting and that its gain mainly comes from local graph modeling and relation-aware action encoding.