基于混合进化算法的卫星网络星间数传方法

doi:10.12305/j.issn.1001-506X.2023.09.33

摘要/Abstract

摘要：

星间链路在卫星网络数据传输中发挥着非常重要的作用, 可以解决我国地面站布局受限的问题。然而, 卫星网络拓扑时变, 网络资源有限, 使得星间数据传输具有很大的挑战性。为了克服这个难点, 首先利用存储时间聚合图建模卫星网络, 在考虑网络资源约束的条件下, 构建了数据传输整数规划模型。然后, 设计了知识型混合进化算法(knowledge-guided hybrid evolutionary algorithm, KGHEA)对模型进行求解, 该算法融合了局部搜索算法、路径流量分配算法, 以及多种知识型算子。最后, 设计了仿真实验, 验证了KGHEA的性能, 并分析了各项参数对数据传输性能的影响, 为星间网络建设提供参考。

关键词: 混合进化算法, 遗传算法, 卫星网络, 延迟容忍网络, 星间数传

Abstract:

Inter-satellite links play a very important role in satellite network data transmission, which can solve the problem of limited layout of ground stations in China. However, the satellite network topology is time-varying, and the inter-satellite links have intermittent connectivity, which make inter-satellite data transmission a great challenge. In order to overcome this difficulty, firstly, the satellite network is modeled by using the storage time aggregation graph. Under the condition of considering the resource constraints on the satellite, an integer programming model of data transmission is constructed. Then, a knowledge-guided hybrid evolutionary algorithm (KGHEA), which integrated local search algorithm, path traffic allocation algorithm and a variety of knowledge operators, is designed to solve the model. Finally, a simulation experiment is designed to verify the performance of the KGHEA algorithm, and the impact of various parameters on the data transmission performance is analyzed to provide a reference for the construction of inter-satellite network.

Key words: hybrid evolutionary algorithm, genetic algorithm, satellite network, delay tolerant network, inter-satellite data transmission

中图分类号:

TP18

邓勇, 姚锋, 邢立宁, 何磊. 基于混合进化算法的卫星网络星间数传方法[J]. 系统工程与电子技术, 2023, 45(9): 2931-2940.

Yong DENG, Feng YAO, Lining XING, Lei HE. Inter-satellite data transmission method in satellite network based on hybrid evolutionary algorithm[J]. Systems Engineering and Electronics, 2023, 45(9): 2931-2940.

图/表 11

图1

图2

图3

图4

图5

表1

图6

图7

图8

图9

图10

参考文献 34

1	SHI K Y , ZHANG X S , ZHANG S , et al. Time-expanded graph based energy-efficient delay-bounded multicast over satellite networks[J]. IEEE Trans. on Vehicular Technology, 2020, 69 (9): 10380- 10384. doi: 10.1109/TVT.2020.2988023
2	CHENG N , HE J C , YIN Z S , et al. 6G service-oriented space-air-ground integrated network: a survey[J]. Chinese Journal of Aeronautics, 2022, 35 (9): 1- 18. doi: 10.1016/j.cja.2021.12.013
3	YANG H T , LIU W , LI H Y , et al. Maximum flow routing strategy for space information network with service function constraints[J]. IEEE Trans. on Wireless Communications, 2022, 21 (5): 2909- 2923. doi: 10.1109/TWC.2021.3116983
4	SHENG M , WANG Y , LI J D , et al. Toward a flexible and reconfigurable broadband satellite network: resource management architecture and strategies[J]. IEEE Wireless Communications, 2017, 24 (4): 127- 133. doi: 10.1109/MWC.2017.1600173
5	FERRE R M , LOHAN E S , KUUSNIEMI H , et al. Is LEO-based positioning with mega-constellations the answer for future equal access localization?[J]. IEEE Communications Magazine, 2022, 60 (6): 40- 46. doi: 10.1109/MCOM.001.2100841
6	INIGO D P , BRUCE G C , EDWARD F C . A technical comparison of three low earth orbit satellite constellation systems to provide global broadband[J]. Acta Astronautica, 2019, 159, 123- 135. doi: 10.1016/j.actaastro.2019.03.040
7	孙晨华, 肖永伟, 赵伟松, 等. 天地一体化信息网络低轨移动及宽带通信星座发展设想[J]. 电信科学, 2017, 33 (12): 43- 52.
	SUN C H , XIAO Y W , ZHAO W S , et al. Development conception of space-ground inteyrated information network LEO mobile and broadband internet constellation[J]. Telecommunications Science, 2017, 33 (12): 43- 52.
8	高贺, 王玲, 黄文德, 等. 北斗全球卫星导航系统境外星数据快速回传的路由优化方法[J]. 中国空间科学技术, 2018, 38 (2): 9- 15. doi: 10.16708/j.cnki.1000-758x.2018.0002
	GAO H , WANG L , HUANG W D , et al. Routing optimization method for fast return of data on overseas satellites in Beidou global navigation satellite system[J]. Chinese Space Science and Technology, 2018, 38 (2): 9- 15. doi: 10.16708/j.cnki.1000-758x.2018.0002
9	JIA M , ZHU S Y , WANG L F , et al. Routing algorithm with virtual topology toward to huge numbers of LEO mobile satellite network based on SDN[J]. Mobile Networks and Applications, 2017, 23 (2): 285- 300.
10	ZHANG J W , XING L N , PENG G S , et al. A large-scale multiobjective satellite data transmission scheduling algorithm based on SVM+NSGA-Ⅱ[J]. Swarm and Evolutionary Computation, 2019, 50, 100560. doi: 10.1016/j.swevo.2019.100560
11	CHEN Y G , CHEN M , WEN J , et al. An adaptive large neighborhood search algorithm for the satellite data transmission scheduling problem[J]. International Journal of Aerospace Engineering, 2020, 5243749.
12	ZHANG J W , XING L N . An improved genetic algorithm for the integrated satellite imaging and data transmission scheduling problem[J]. Computers & Operations Research, 2022, 139, 105626.
13	QU Q Y , LIU K X LI X J , et al. Satellite observation and data-transmission scheduling using imitation learning based on mixed integer linear programming[J]. IEEE Trans. on Aerospace and Electronic Systems, 2022, doi: 10.1109/TAES.2022.3210073
14	JIA X H , LV T , HE F , et al. Collaborative data downloading by using inter-satellite links in LEO satellite networks[J]. IEEE Trans. on Wireless Communications, 2017, 16 (3): 1523- 1532. doi: 10.1109/TWC.2017.2647805
15	DU Y H , WANG L , XING L N , et al. Data-driven heuristic assisted memetic algorithm for efficient inter-satellite link scheduling in the Beidou navigation satellite system[J]. IEEE/ CAA Journal of Automatica Sinica, 2021, 8 (11): 1800- 1816. doi: 10.1109/JAS.2021.1004174
16	YAN Z B , ZHAO K L , LI W F , et al. Topology design for GNSSs under polling mechanism considering both inter-satellite links and ground-satellite links[J]. IEEE Trans. on Vehicular Technology, 2022, 71 (2): 2084- 2097. doi: 10.1109/TVT.2021.3135563
17	王瑞松, 马若飞, 王琦, 等. 卫星网络时隙分配算法与路由规划优化[J]. 系统工程与电子技术, 2022, 44 (4): 1343- 1353.
	WANG R S , MA R F , WANG Q , et al. Optimization of time slot allocation algorithm and routing scheduling for satellite network[J]. Systems Engineering and Electronics, 2022, 44 (4): 1343- 1353.
18	LIU J M , XING L N , WANG L , et al. A data-driven parallel adaptive large neighbor-hood search algorithm for a large-scale inter-satellite link scheduling problem[J]. Swarm and Evolutionary Computation, 2022, 74, 101124. doi: 10.1016/j.swevo.2022.101124
19	LIANG Q Z , FAN Y Y , YAN X S . An algorithm based on differential evolution for satellite data transmission scheduling[J]. International Journal of Computational Science and Engineering, 2018, 18 (3): 279- 285.
20	FRAIRE J A , FINOCHIETTO J M . Routing-aware fair contact plan design for predictable delay tolerant networks[J]. Ad Hoc Networks, 2015, 25, 1570- 8705.
21	YAN H C, ZHANG Q J, SUN Y, et al. Contact plan design for navigation satellite network based on simulated annealing[C]//Proc. of the IEEE International Conference on Communication Software and Networks, 2015: 12-16.
22	CAINI C , CRUICKSHANK H , FARRELL S , et al. Delay and disruption tolerant networking (DTN): an alternative solution for future satellite networking applications[J]. Proceedings of the IEEE, 2011, 99 (11): 1980- 1997. doi: 10.1109/JPROC.2011.2158378
23	HUANG M S , CHEN S Y , ZHU Y , et al. Topology control for time-evolving and predictable delay tolerant networks[J]. IEEE Trans. on Computers, 2013, 62 (11): 2308- 2321. doi: 10.1109/TC.2012.220
24	LI H Y , ZHANG T , ZHANG Y K , et al. A maximum flow algorithm based on storage time aggregated graph for delay-tolerant networks[J]. Ad Hoc Networks, 2017, 59, 63- 70. doi: 10.1016/j.adhoc.2017.01.006
25	ZHANG T , LI H Y , ZHANG S , et al. STAG-based QoS support routing strategy for multiple missions over the Satellite networks[J]. IEEE Trans. on Communications, 2019, 67 (10): 6912- 6924. doi: 10.1109/TCOMM.2019.2929757
26	MARCHESE M , PATRONE F . E-CGR: energy-aware contact graph routing over nanosatellite networks[J]. IEEE Trans. on Green Communications and Networking, 2020, 4 (3): 890- 902. doi: 10.1109/TGCN.2020.2978296
27	AHMADIAN M M , SALEHIPOUR A , CHENG T C E . A meta-heuristic to solve the just-in-time job-shop scheduling problem[J]. European Journal of Operational Research, 2021, 288 (1): 14- 29. doi: 10.1016/j.ejor.2020.04.017
28	YAHYAOUI H , KAABACHI I , KRICHEN S , et al. Two metaheuristic approaches for solving the multi-compartment vehicle routing problem[J]. Operational Research, 2020, 20, 2085- 2108. doi: 10.1007/s12351-018-0403-4
29	GAO K Z , ZHANG L , CHEN Z H , et al. A review on swarm intelligence and evolutionary algorithms for solving flexible job shop scheduling problems[J]. IEEE/CAA Journal of Automatica Sinica, 2019, 6 (4): 904- 916. doi: 10.1109/JAS.2019.1911540
30	PRAKASH A , CHAN F T S , DESHMUKH S G . FMS scheduling with knowledge based genetic algorithm approach[J]. Expert Systems with Applications, 2011, 38 (4): 3161- 3171. doi: 10.1016/j.eswa.2010.09.002
31	GHAHRAMANI M , QIAO Y , ZHOU M C , et al. AI-based modeling and data-driven evaluation for smart manufacturing processes[J]. IEEE/CAA Journal of Automatica Sinica, 2020, 7 (4): 1026- 1037. doi: 10.1109/JAS.2020.1003114
32	PAN Z X , LEI D M , WANG L . A knowledge-based two-population optimization algorithm for distributed energy-efficient parallel machines scheduling[J]. IEEE Trans. on Cybernetics, 2022, 52 (6): 5051- 5063. doi: 10.1109/TCYB.2020.3026571
33	CPLEX Optimization Studio . CPLEX user's manual[M]. New York, USA: IBM Corporation, 2015.
34	FRAIRE J A. Introducing contact plan designer: a planning tool for DTN based space-terrestrial networks[C]//Proc. of the 6th International Conference on Space Mission Challenges for Information Technology, 2017: 124-127.

类型	轨道参数
MEO	Walker 24/3/1, 轨道高度: 21 528 km, 轨道倾角: 55°
GEO	轨道高度: 35 786 km, 经度: 80°, 110.5°, 140°
IGEO	轨道高度: 35 786 km, 轨道倾角: 55°

[1]	马维宁, 胡起伟, 曹文斌, 贾希胜. 考虑维修任务分配的装备选择性维修决策优化[J]. 系统工程与电子技术, 2023, 45(6): 1902-1910.
[2]	毕可心, 吴明功, 温祥西, 张文斌, 杨文达. 基于飞行冲突网络和遗传算法的冲突解脱策略[J]. 系统工程与电子技术, 2023, 45(5): 1429-1440.
[3]	吕晓峰, 杨东泽, 马羚. 舰载机模块化弹药调度方案优化设计[J]. 系统工程与电子技术, 2023, 45(2): 465-471.
[4]	骆天溯, 赵灵峰, 冯蕴雯, 薛小锋, 路成. 基于METRIC理论的超大规模卫星星座多级备份策略[J]. 系统工程与电子技术, 2022, 44(7): 2181-2190.
[5]	李波, 周家豪, 刘民岷, 朱品朝. 基于改进NSGA3的焊接缺陷评估特征选择[J]. 系统工程与电子技术, 2022, 44(7): 2211-2218.
[6]	冯豪博, 胡桥, 赵振轶. 基于精英族系遗传算法的AUV集群路径规划[J]. 系统工程与电子技术, 2022, 44(7): 2251-2262.
[7]	杨少龙, 黄金, 向先波, 李伟超. 基于置信椭圆的无人艇区域覆盖搜寻规划优化[J]. 系统工程与电子技术, 2022, 44(7): 2263-2269.
[8]	冯蕴雯, 陈俊宇, 路成. 民用飞机多地域航材支援网络模型研究[J]. 系统工程与电子技术, 2022, 44(5): 1553-1561.
[9]	靳鹏, 唐晓茜. 考虑合成机制的多星应急任务调度[J]. 系统工程与电子技术, 2022, 44(4): 1270-1281.
[10]	王瑞松, 马若飞, 王琦, 钟志聪, 刘功亮, 张杨. 卫星网络时隙分配算法与路由规划优化[J]. 系统工程与电子技术, 2022, 44(4): 1343-1353.
[11]	孙剑炜, 王超, 施庆展, 任文博, 尧泽昆, 袁乃昌. 基于遗传算法的相位调制波形智能优化[J]. 系统工程与电子技术, 2022, 44(3): 722-729.
[12]	刘高赛, 姜兴龙, 李华旺, 梁广. 基于位置感知的大规模LEO星座分布式路由算法[J]. 系统工程与电子技术, 2022, 44(11): 3529-3536.
[13]	薛乃阳, 丁丹, 王红敏, 刘步花. 基于改进遗传算法的多类测控资源调度方法[J]. 系统工程与电子技术, 2021, 43(9): 2535-2543.
[14]	陈云翔, 饶益, 蔡忠义, 王泽洲. 基于改进相似性的装备部件剩余寿命预测及经济性储备策略[J]. 系统工程与电子技术, 2021, 43(9): 2688-2696.
[15]	赵禄达, 王斌, 曾威. 进攻战斗电子对抗兵力需求的三层规划模型[J]. 系统工程与电子技术, 2021, 43(6): 1564-1571.