面向高动态大规模卫星网络的层次稳定路由算法

doi:10.3778/j.issn.1673-9418.2501040

摘要/Abstract

摘要： 大规模低轨卫星星座的部署将为全球提供高速、稳定的互联网服务，在满足未来6G网络对低时延和高可靠性需求方面发挥关键作用。然而，低轨卫星的高速移动，其相对位置和星间链路频繁变化，导致网络拓扑持续动态调整，引发路由更新频繁、数据传输不稳定等问题，难以满足互联网通信对稳定性和可靠性的要求。为了解决上述问题，提出了一种低轨卫星网络中的稳定路由算法，通过引入稳定路径问题模型，综合考虑路由稳定性和通信性能，计算跨时隙路由变化最少的卫星稳定路径，从而降低路由的更新频率。针对大规模网络中路由求解复杂度高、更新代价显著增加的问题，进一步设计了一种适用于高动态大规模卫星网络的层次稳定路由架构。该架构将卫星网络划分为多个逻辑域，在域间采用稳定路由策略保障全局路由的连续性，在域内结合区域流量特征采用选择性路由策略，有效降低稳定路由计算复杂度。为应对快速变化的网络拓扑，架构进一步结合增量式局部重算与拓扑预测性更新机制，增强路径计算的及时性与准确性，确保层次架构下的路由响应能够满足高动态环境的实时需求。仿真实验结果表明，与现有方法相比，所提出的层次稳定路由算法使路由更新频率降低69%，平均传输时延降低14%，总体网络开销降低44%。

关键词: 低轨卫星网络, 星间链路切换, 层次分域, 稳定路由

Abstract: The deployment of large-scale low earth orbit (LEO) satellite constellations offers high-speed and stable Internet services globally, playing a critical role in meeting the low-latency and high-reliability requirements of future 6G networks. However, the high-speed movement of LEO satellites leads to frequent changes in their relative positions and inter-satellite links (ISLs), resulting in continuous network topology adjustments, frequent route updates, unstable data transmission, and other challenges. These issues make it difficult to achieve the stability and reliability required for Internet communication. To address these challenges, this paper proposes a stable routing algorithm for LEO satellite networks. By introducing a stable path problem model that considers both routing stability and communication performance, the algorithm calculates the most stable satellite path with minimal changes across time slots, thereby reducing routing update frequency. Furthermore, a hierarchical stable routing architecture tailored for highly dynamic, large-scale satellite networks is designed to tackle the challenges of high routing complexity and significantly increased update costs in large-scale networks. This architecture divides the satellite network into hierarchical domains, reducing the computational complexity of stable routing and enhancing inter-satellite transmission efficiency. It employs an inter-domain stable routing strategy to ensure global stability and an intra-domain selective routing strategy to accommodate regional traffic characteristics. To cope with rapidly changing network topologies, the architecture further combines incremental local recalculation and topology predictive update mechanisms to enhance the timeliness and accuracy of path computation, ensuring that routing responses under hierarchical architecture can meet the real-time requirements of high dynamic environments. Simulation results demonstrate that, compared with related algorithms, the proposed hierarchical stable routing algorithm reduces satellite routing update frequency by 69%, average transmission delay by 14%, and overall network overhead by 44%.

Key words: low earth orbit (LEO) satellite network, inter-satellite links handover, hierarchical domain, stable routing

桑环宇, 杨雅婷, 陈东惠, 嵩天. 面向高动态大规模卫星网络的层次稳定路由算法[J]. 计算机科学与探索, 2025, 19(10): 2831-2843.

SANG Huanyu, YANG Yating, CHEN Donghui, SONG Tian. Hierarchical Stable Routing Algorithm for High Dynamic Large-Scale Satellite Networks[J]. Journal of Frontiers of Computer Science and Technology, 2025, 19(10): 2831-2843.

参考文献

[1] 叶进, 陈贵豪, 韦姿蓉, 等. 一种增量部署太赫兹链路的巨型近地轨道星座网络路由算法[J]. 电子与信息学报, 2023, 45(8): 2876-2884.
YE J, CHEN G H, WEI Z R, et al. A routing algorithm on low earth orbit mega-constellation network with incremental deployment of terahertz links[J]. Journal of Electronics & Information Technology, 2023, 45(8): 2876-2884.
[2] 李晗. 卫星星座网络星间路由算法研究[D]. 哈尔滨: 哈尔滨工业大学, 2022.
LI H. Research on inter-satellite routing algorithm of satellite constellation network[D]. Harbin: Harbin Institute of Technology, 2022.
[3] 罗政杰. 面向低轨卫星网络动态拓扑的稳定路由生成算法[D]. 北京: 北京邮电大学, 2023.
LUO Z J. Stable route algorithm for dynamic topology of LEO satellite network[D]. Beijing: Beijing University of Posts and Telecommunications, 2023.
[4] 郑爽, 张兴, 王文博. 低轨卫星通信网络路由技术综述[J]. 天地一体化信息网络, 2022, 3(3): 97-105.
ZHENG S, ZHANG X, WANG W B. Survey of low earth orbit satellite communication network routing technology[J]. Space-Integrated-Ground Information Networks, 2022, 3(3): 97-105.
[5] TAN H C, ZHU L D. A novel routing algorithm based on virtual topology snapshot in LEO satellite networks[C]//Proceedings of the 2014 IEEE 17th International Conference on Computational Science and Engineering. Piscataway: IEEE, 2014: 357-361.
[6] 杨子健. 大规模低轨卫星网络动态路由算法及其安全技术研究[D]. 上海: 中国科学院大学(中国科学院微小卫星创新研究院), 2023.
YANG Z J. Research on dynamic routing algorithm and security technology of large-scale low earth orbit constellation[D]. Shanghai: University of Chinese Academy of Sciences（Innovation Academy for Microsatellites of CAS）, 2023.
[7] 谭海超, 朱立东, 李雄飞, 等. 低轨卫星通信网络路由优化研究[J]. 计算机仿真, 2015, 32(9): 80-85.
TAN H C, ZHU L D, LI X F, et al. Routing optimization of low earth orbit satellite communication network[J]. Computer Simulation, 2015, 32(9): 80-85.
[8] LIU J, LUO R Z, HUANG T, et al. A load balancing routing strategy for LEO satellite network[J]. IEEE Access, 2020, 8: 155136-155144.
[9] LIU X M, YAN X M, JIANG Z Q, et al. A low-complexity routing algorithm based on load balancing for LEO satellite networks[C]//Proceedings of the 2015 IEEE 82nd Vehicular Technology Conference. Piscataway: IEEE, 2015: 1-5.
[10] LUO Z J, PAN T, SONG E G, et al. A refined Dijkstra??s algorithm with stable route generation for topology-varying satellite networks[C]//Proceedings of the 2021 IEEE 41st International Conference on Distributed Computing Systems. Piscataway: IEEE, 2021: 1146-1147.
[11] ZHANG S Y, YEUNG K L. Scalable routing in low-earth orbit satellite constellations: architecture and algorithms[J]. Computer Communications, 2022, 188: 26-38.
[12] SUN X H, SHEN Y F, ZHANG H B. A stable satellite routing algorithm based on a-star algorithm in dynamic networks[J]. Journal of Physics: Conference Series, 2024, 2807(1): 012026.
[13] WERNER M. A dynamic routing concept for ATM-based satellite personal communication networks[J]. IEEE Journal on Selected Areas in Communications, 1997, 15(8): 1636-1648.
[14] 倪少杰, 岳洋, 左勇, 等. 卫星网络路由技术现状及展望[J]. 电子与信息学报, 2023, 45(2): 383-395.
NI S J, YUE Y, ZUO Y, et al. The status quo and prospect of satellite network routing technology[J]. Journal of Electronics & Information Technology, 2023, 45(2): 383-395.
[15] 李勇, 张安安, 程子敬, 等. 卫星网络最短路径路由机制的仿真分析与评估[J]. 武汉大学学报(工学版), 2015, 48(6): 848-851.
LI Y, ZHANG A A, CHENG Z J, et al. Performance evaluation of tactics of shortest-path routing in satellite communication networks[J]. Engineering Journal of Wuhan University, 2015, 48(6): 848-851.
[16] XIAO Y L, ZHANG T, LIU L. Addressing subnet division based on geographical information for satellite-ground integrated network[J]. IEEE Access, 2018, 6: 75824-75833.
[17] GRIFFIN T G, SHEPHERD F B, WILFONG G. The stable paths problem and interdomain routing[J]. IEEE/ACM Transactions on Networking, 2002, 10(2): 232-243.
[18] CHENG Y C, LUO N, ZHANG J X, et al. Looking for the maximum independent set: a new perspective on the stable path problem[C]//Proceedings of the 40th IEEE Conference on Computer Communications. Piscataway: IEEE, 2021: 1-10.
[19] WU Q H, HAO J K. A review on algorithms for maximum clique problems[J]. European Journal of Operational Research, 2015, 242(3): 693-709.
[20] 崔荣芳, 徐湛, 职如昕. 低轨卫星星座快速响应链路损毁路由算法[J]. 电讯技术, 2023, 63(8): 1165-1172.
CUI R F, XU Z, ZHI R X. A quick-response link destruction routing algorithm for LEO satellite constellation[J]. Telecommunication Engineering, 2023, 63(8): 1165-1172.
[21] HE Y Z, CHEN H J, MA C S. A cross-domain aggregation routing based on lightweight OSPF protocol for the GEO satellite-ground integrated network[C]//Proceedings of the 2022 2nd International Conference on Computer Science, Electronic Information Engineering and Intelligent Control Technology. Piscataway: IEEE, 2022: 459-463.
[22] CUI M. Introduction to the k-means clustering algorithm based on the elbow method[J]. Accounting, Auditing and Finance, 2020, 1(1): 5-8.