Routing Algorithm Based on Link and Node Multi-Attribute Fusion for Low Earth Orbit Satellite Network

doi:10.3778/j.issn.1002-8331.2306-0261

Abstract

Abstract: To address the issue of low earth orbit (LEO) satellite network with high performance loss, communication delays and packet loss rates against disruptive events, a multi-path routing algorithm based on multiple attributes is proposed. In low-orbit satellite constellation simulated with the virtual topology scheme, multiple feasible paths between source nodes and target nodes are calculated. The algorithm constructs a transmission cost model of path by fusing attributes of inter-satellite links and adjacent satellite nodes, adaptively adjusts the weight of two types of attributes on transmission cost. Each satellite normalizes the path transmission cost as the probability of forwarding packets through the path and independently performed distributed routing. Compared with classical multi-path routing algorithms for LEO satellite networks, the proposed algorithm has slower performance degradation as well as lower packet loss rate and average end-to-end delay, regardless of whether the network is heavily loaded or under disruptive events, provides excellent load balancing capability and effectively enhances the availability of routing.

Key words: low earth orbit (LEO) satellite network, multi-path routing, inter-satellite link attribute, satellite attribute, load balancing

摘要： 针对低轨卫星网络面对破坏性事件系统性能损失多、通信延迟和丢包率高的问题，提出了基于多属性的低轨卫星网络多路径路由算法。在采用虚拟拓扑方案仿真的低轨卫星星座中，计算源节点与目标节点之间的多条可行路径，该算法融合卫星间链路属性和相邻卫星节点属性构建路径的传输成本模型，自适应调整两类属性对传输成本的影响权重，每颗卫星将路径传输成本的归一化结果作为通过该路径转发报文的概率，并独立进行分布式的路由选择。仿真结果表明，与经典的低轨卫星网络多路径路由算法相比，无论网络负载较大发生拥塞时，还是卫星遭受网络攻击或出现故障时，该算法性能下降缓慢，丢包率和平均端到端延迟更低，且具有良好的负载均衡能力，有效增强了路由的可用性。

关键词: 低轨卫星网络, 多路径路由, 链路属性, 卫星属性, 负载均衡

SUN Zhengyang, DU Ye, LI Guiling, LI Meihong. Routing Algorithm Based on Link and Node Multi-Attribute Fusion for Low Earth Orbit Satellite Network[J]. Computer Engineering and Applications, 2024, 60(18): 266-274.

孙正阳, 杜晔, 李桂领, 黎妹红. 链路及节点多属性融合的低轨卫星网络路由算法[J]. 计算机工程与应用, 2024, 60(18): 266-274.

References

[1] 朱沁雨, 曹延华, 陶海成, 等. 低轨星座网络拓扑的抗毁性研究进展[J]. 计算机工程与应用, 2022, 58(17): 1-12.
ZHU Q Y, CAO Y H, TAO H C, et al. Research progress on survivability of low-orbit constellation network topology[J]. Computer Engineering and Applications, 2022, 58(17): 1-12.
[2] MARKOVITZ O, SEGAL M. Seam-aware location-based random walk routing algorithms for low orbit satellite constellations[C]//2021 17th International Conference on Wireless and Mobile Computing, Networking and Communications (WiMob), 2021: 351-356.
[3] 杨力, 吴义, 魏德宾, 等. 基于时空相关性的卫星网络流量预测[J]. 计算机工程与应用, 2021, 57(7): 101-106.
YANG L, WU Y, WEI D B, et al. Satellite network traffic prediction based on spatiotemporal correlation[J]. Computer Engineering and Applications, 2021, 57(7): 101-106.
[4] YAN Y, HAN G, XU H. A survey on secure routing protocols for satellite network[J]. Journal of Network and Computer Applications, 2019, 145: 102415.
[5] CHEN R, BAO F, CHANG M J, et al. Dynamic trust management for delay tolerant networks and its application to secure routing[J]. IEEE Transactions on Parallel and Distributed Systems, 2013, 25(5): 1200-1210.
[6] 刘军, 杨青文, 王金涛, 等. 基于改进遗传算法的空间信息网恢复策略[J]. 东北大学学报 (自然科学版), 2021, 42(4): 524-530.
LIU J, YANG Q W, WANG J T, et al. Spatial information network restoration strategy based on improved genetic algorithm[J]. Journal of Northeastern University (Natural Science), 2021, 42(4): 524-530.
[7] MOHORCIC M, WERNER M, SVIGELJ A, et al. Adaptive routing for packet-oriented intersatellite link networks: performance in various traffic scenarios[J]. IEEE Transactions on Wireless Communications, 2002, 1(4): 808-818.
[8] HAN Z, ZHAO G, XING Y, et al. Dynamic routing for software-defined LEO satellite networks based on ISL attributes[C]//Proceedings of the 2021 IEEE Global Communications Conference (GLOBECOM), 2021: 1-6.
[9] ROTH M M H, BRANDT H, BISCHL H. Distributed SDN-based load-balanced routing for low earth orbit satellite constellation networks[C]//2022 11th Advanced Satellite Multimedia Systems Conference and the 17th Signal Processing for Space Communications Workshop (ASMS/SPSC), 2022: 1-8.
[10] ZHANG X, YANG Y, XU M, et al. ASER: scalable distributed routing protocol for LEO satellite networks[C]//2021 IEEE 46th Conference on Local Computer Networks (LCN), 2021: 65-72.
[11] RABJERG J W, LEYVA-MAYORGA I, SORET B, et al. Exploiting topology awareness for routing in LEO satellite constellations[C]//2021 IEEE Global Communications Conference (GLOBECOM), 2021: 1-6.
[12] HOU W, XIAN B, GUO L, et al. Novel routing algorithms in space information networks based on timeliness-aware data mining and time-space graph[C]//2015 International Conference on Wireless Communications & Signal Processing (WCSP), 2015: 1-5.
[13] BAI J J, LU X C, LU Z X, et al. Compact explicit multi-path routing for LEO satellite networks[C]//2005 Workshop on High Performance Switching and Routing, 2005: 386-390.
[14] TALEB T, MASHIMO D, JAMALIPOUR A, et al. Explicit load balancing technique for NGEO satellite IP networks with on-board processing capabilities[J]. IEEE/ACM Transactions on Networking, 2008, 17(1): 281-293.
[15] SONG G, CHAO M, YANG B, et al. TLR: a traffic-light-based intelligent routing strategy for NGEO satellite IP networks[J]. IEEE Transactions on Wireless Communications, 2014, 13(6): 3380-3393.
[16] 魏德宾, 操昱, 杨力, 等. 一种基于时空等级的LEO卫星网络路由策略[J]. 航空学报, 2023, 44(18): 327994.
WEI D B, CAO Y, YANG L, et al. A routing strategy for LEO satellite network based on space-time-level[J]. Acta Aeronautica et Astronautica Sinica, 2023, 44(18): 327994.
[17] DONG C, XU X, LIU A, et al. Load balancing routing algorithm based on extended link states in LEO constellation network[J]. China Communications, 2022, 19(2): 247-260.
[18] 杨明川, 薛冠昌, 李清毅. 基于邻居卫星负载状态的低轨卫星分布式路由算法[J]. 通信学报, 2021, 42(8): 43-51.
YANG M C, XUE G C, LI Q Y. Neighbor satellite load based low orbit satellite distributed routing algorithm[J]. Journal on Communications, 2021, 42(8): 43-51.
[19] TANG F L. Dynamically adaptive cooperation transmission among satellite-ground integrated networks[C]//IEEE INFOCOM 2020-IEEE Conference on Computer Communications, 2020: 1559-1568.
[20] QI H, GUO Y, HOU D, et al. SDN-based dynamic multi-path routing strategy for satellite networks[J]. Future Generation Computer Systems, 2022, 133: 254-265.
[21] WOOD L, CLERGET A, ANDRIKOPOULOS I, et al. IP routing issues in satellite constellation networks[J]. International Journal of Satellite Communications, 2001, 19(1): 69-92.
[22] SUZUKI R, YASUDA Y. Study on ISL network structure in LEO satellite communication systems[J]. Acta Astronautica, 2007, 61(7/8): 648-658.