Fully-Distributed Dynamic Packet Routing for LEO Satellite Networks: A GNN-Enhanced Multi-Agent Reinforcement Learning Approach

An efficient routing strategy in Low Earth Orbit (LEO) satellite networks is critical for air-space-ground integrated communication towards 6G. However, the existing terrestrial routing algorithms cannot well handle the high-speed movement issue of satellites, while the existing satellite routing algorithms usually suffer from high communication overhead or high computational complexity. To address the above issues, we propose a fully distributed dynamic packet routing algorithm based on Graph Neural Network (GNN)-enhanced Multi-Agent Deep Reinforcement Learning (MADRL), named GraphPR. In GraphPR, the satellite routing problem is modeled as a Partially Observable Markov Decision Process (POMDP), where each satellite only needs to share the information with one-hop neighbors. Then, Graph Attention Network (GAT) is leveraged to encode the perceived one-hop information and derive a hidden representation implicitly consisting of multi-hop satellite information. Subsequently, MADRL is employed to build a fully distributed optimization framework and make routing decisions. In addition, a special mechanism called Residual Shortest Path Hops (RSPH) is designed to guide the routing selection and avoid routing loops. Finally, the experimental results illustrate that GraphPR has better performance in terms of packet loss rate, average delivery time, throughput, and average queuing length than the baseline algorithms.