卫星网络时隙分配算法与路由规划优化

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

系统工程与电子技术 ›› 2022, Vol. 44 ›› Issue (4): 1343-1353.doi: 10.12305/j.issn.1001-506X.2022.04.33

卫星网络时隙分配算法与路由规划优化

王瑞松¹, 马若飞¹, 王琦², 钟志聪¹, 刘功亮^1,*, 张杨³

1. 哈尔滨工业大学(威海)信息科学与工程学院, 山东威海 264209
2. 北京跟踪与通信技术研究所, 北京 100094
3. 航天东方红卫星有限公司, 北京 100094

收稿日期:2021-02-03 出版日期:2022-04-01 发布日期:2022-04-01
通讯作者: 刘功亮
作者简介:王瑞松(1996—), 男, 博士研究生, 主要研究方向为卫星通信、网络编码、资源优化分配|马若飞(1984—), 男, 副教授, 博士, 主要研究方向为D2D通信、智能互联车辆、水下通信和网络|王琦(1984—), 女, 助理研究员, 硕士, 主要研究方向为星间链路技术|钟志聪(1997—), 男, 硕士研究生, 主要研究方向为卫星通信、网络编码|刘功亮(1979—), 男, 教授, 博士, 主要研究方向为无线通信与网络、卫星通信、水下通信|张杨(1981—), 女, 工程师, 硕士, 主要研究方向为卫星通信
基金资助:
国家自然科学基金(61971156);国家自然科学基金(61801144);山东省自然科学基金(ZR2019MF035);山东省自然科学基金(ZR2019QF003);山东省自然科学基金(ZR2020MF141);中央高校基本科研业务费专项(HIT.NSRIF.2019081);哈尔滨工业大学(威海)科研创新基金(2019KYCXJJYB06)

Optimization of time slot allocation algorithm and routing scheduling for satellite network

Ruisong WANG¹, Ruofei MA¹, Qi WANG², Zhicong ZHONG¹, Gongliang LIU^1,*, Yang ZHANG³

1. School of Information Science and Engineering, Harbin Institute of Technology, Weihai 264209, China
2. Beijing Institute of Tracking and Telecommunications Technology, Beijing 100094, China
3. Aerospace Dongfanghong Satellite Co., Ltd., Beijing 100094, China

Received:2021-02-03 Online:2022-04-01 Published:2022-04-01
Contact: Gongliang LIU

摘要/Abstract

摘要：

星间链路的应用在增加网络连通性和提升网络性能方面是至关重要的。然而, 对于大规模、高动态的卫星网络, 实时的星间链路设计和路由规划变得非常有挑战性。为了克服这个难点, 本文研究了动态卫星网络中的时隙分配与路由规划问题, 并将其建模为一个整数线性规划问题。为了降低问题求解的复杂度, 该问题被近似地分解为两个独立的子问题, 包括时隙分配问题与路由规划问题。第一个子问题仍然是一个整数规划问题, 本文结合匹配理论与拉格朗日松弛方法设计了一个低复杂度但是高效的求解算法。然后, 针对第二个子问题, 考虑业务的优先级, 设计了一个低花费的路由算法。最后, 仿真结果验证了方法的可行性与有效性。

关键词: 卫星网络, 拉格朗日松弛, 时隙分配, 路由规划

Abstract:

The inter-satellite links play a crucial role in increasing network connectivity and improving network performance. However, it is very challenging to design the real time inter-satellite links and routing scheme for large scale and high dynamic satellite networks. To overcome this difficulty, this paper studies the time slot allocation and routing scheduling problem for dynamic satellite networks, and then formulates it as an integer linear programming problem. To decrease the solving complexity, the proposed problem is approximatively decomposed into two independent subproblems, namely, the time slot allocation problem and the routing scheduling problem. To deal with the integer programming in the first subproblem, the matching theory and the Lagrangian relaxation method are used to design a low complexity but efficient algorithm. Moreover, for the second subproblem, we design a low cost routing algorithm considering the priorities of the missions. Finally, the simulation results verify the feasibility and effectiveness of the proposed method.

Key words: satellite network, Lagrange relaxation, time slot allocation, routing scheduling

中图分类号:

TN927

王瑞松, 马若飞, 王琦, 钟志聪, 刘功亮, 张杨. 卫星网络时隙分配算法与路由规划优化[J]. 系统工程与电子技术, 2022, 44(4): 1343-1353.

Ruisong WANG, Ruofei MA, Qi WANG, Zhicong ZHONG, Gongliang LIU, Yang ZHANG. Optimization of time slot allocation algorithm and routing scheduling for satellite network[J]. Systems Engineering and Electronics, 2022, 44(4): 1343-1353.

图/表 10

图1

图2

图3

表1

图4

图5

图6

图7

图8

图9

参考文献 31

1	LIU S J , LIN J K , XU L X , et al. A dynamic beam shut off algorithm for LEO multibeam satellite constellation networks[J]. IEEE Wireless Communications Letters, 2020, 9 (10): 1730- 1733. doi: 10.1109/LWC.2020.3002846
2	WANG R S , KANG W J , LIU G L , et al. Admission control and power allocation for NOMA-based satellite multi-beam network[J]. IEEE Access, 2020, 8, 33631- 33643. doi: 10.1109/ACCESS.2020.2973395
3	ZHU X M , JIANG C X , KUANG L L , et al. Non-orthogonal multiple access based integrated terrestrial-satellite networks[J]. IEEE Journal on Selected Areas in Communications, 2017, 35 (10): 2253- 2267. doi: 10.1109/JSAC.2017.2724478
4	HOU Z W , YI X Q , ZHANG Y H , et al. Satellite-ground link planning for LEO satellite navigation augmentation networks[J]. IEEE Access, 2019, 7, 98715- 98724. doi: 10.1109/ACCESS.2019.2930626
5	WANG J J , DEMEULEMEESTER E , HU X J , et al. Exact and heuristic scheduling algorithms for multiple earth observation satellites under uncertainties of clouds[J]. IEEE Systems Journal, 2019, 13 (3): 3556- 3567. doi: 10.1109/JSYST.2018.2874223
6	WANG Y , SHENG M , ZHUANG W H , et al. Multi-resource coordinate scheduling for earth observation in space information networks[J]. IEEE Journal on Selected Areas in Communications, 2018, 36 (2): 268- 279. doi: 10.1109/JSAC.2018.2804045
7	LIU R Z , SHENG M , LUI K S , et al. An analytical framework for resource-limited small satellite networks[J]. IEEE Communications Letters, 2016, 20 (2): 388- 391. doi: 10.1109/LCOMM.2015.2509993
8	LIU R Z , SHENG M , XU C , et al. Antenna slewing time aware mission scheduling in space networks[J]. IEEE Communications Letters, 2017, 21 (3): 5516- 5519.
9	ZHOU D , SHENG M , WANG X J , et al. Mission aware contact plan design in resource-limited small satellite networks[J]. IEEE Trans.on Communications, 2017, 65 (6): 2451- 2466. doi: 10.1109/TCOMM.2017.2685383
10	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 Network, 2017, 59, 63- 70. doi: 10.1016/j.adhoc.2017.01.006
11	ZHANG T , LI H Y , LI J D , et al. A dynamic combined flow algorithm for the two-commodity max-flow problem over delay-tolerant networks[J]. IEEE Trans.on Wireless Communications, 2018, 17 (2): 7879- 7893.
12	CHEN Q , GIAMBENE G , YANG L , et al. Analysis of inter-satellite link paths for LEO-mega-constellation networks[J]. IEEE Trans.on Vehicular Technology, 2021, 70 (3): 2743- 2755. doi: 10.1109/TVT.2021.3058126
13	JIA X H , LYV 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
14	YAN Z B , GU G Y , ZHAO K L , et al. Integer linear programming based topology design for GNSSs with inter-satellite links[J]. IEEE Wireless Communications Letters, 2021, 10 (2): 286- 290. doi: 10.1109/LWC.2020.3028464
15	CHEN Q , GUO J M , YANG L , et al. Topology virtualization and dynamics shielding method for LEO satellite networks[J]. IEEE Communications Letters, 2020, 24 (2): 433- 437. doi: 10.1109/LCOMM.2019.2958132
16	LIU X F , YANG L , CHEN Q , et al. An analytic method of wavelength requirements in dynamic optical satellite networks[J]. IEEE Communications Letters, 2020, 24 (11): 2569- 2573. doi: 10.1109/LCOMM.2020.3009211
17	SUN X , CAO S Z . A routing and wavelength assignment algorithm based on two types of LEO constellations in optical satellite networks[J]. Journal of Light Wave Technology, 2020, 38 (8): 2106- 2113. doi: 10.1109/JLT.2020.2965185
18	WANG H , CHANG Q , XU Y , et al. Adaptive narrow-band interference suppression and performance evaluation based on code-aided in GNSS inter-satellite links[J]. IEEE Systems Journal, 2020, 14 (1): 538- 547. doi: 10.1109/JSYST.2019.2918055
19	LI J , LU H C , XUE K P , et al. Temporal net grid model-based dynamic routing in large-scale small satellite networks[J]. IEEE Trans.on Vehicular Technology, 2019, 68 (6): 6009- 6021. doi: 10.1109/TVT.2019.2910570
20	TANG F L , ZHANG H T , YANG L T , et al. Multipath cooperative routing with efficient acknowledgement for LEO satellite networks[J]. IEEE Trans.on Mobile Computing, 2019, 18 (1): 179- 192. doi: 10.1109/TMC.2018.2831679
21	CHOI J P , CHANG S H , CHAN V W S . Cross-layer routing and scheduling for onboard processing satellites with phased array antenna[J]. IEEE Trans.on Wireless Communications, 2017, 16 (1): 180- 192. doi: 10.1109/TWC.2016.2621039
22	LU Y , ZHAO Y J , SUN F C , et al. Complexity of routing in store-and-forward LEO satellite networks[J]. IEEE Communications Letters, 2016, 20 (1): 89- 92. doi: 10.1109/LCOMM.2015.2501399
23	YANG Y , XU M W , WANG D , et al. Towards energy-efficient routing in satellite networks[J]. IEEE Journal on Selected Areas in Communications, 2016, 34 (12): 3869- 3886. doi: 10.1109/JSAC.2016.2611860
24	WANG J A , ZHANG R N , YUAN J P , et al. A 3-D energy-harvesting-aware routing scheme for space nanosatellite networks[J]. IEEE Internet of Things Journal, 2018, 5 (4): 2729- 2740. doi: 10.1109/JIOT.2018.2803111
25	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
26	HAN C , HUO L Y , TONG X H , et al. Spatial anti-jamming scheme for internet of satellites based on the deep reinforcement learning and stackelberg game[J]. IEEE Trans.on Vehicular Technology, 2020, 69 (5): 5331- 5342. doi: 10.1109/TVT.2020.2982672
27	ADAMS V , PECK M . A scalable packet routing mechanism for chip-satellites in coplanar orbits[J]. IEEE Trans.on Aerospace and Electronic Systems, 2020, 56 (5): 3516- 3528. doi: 10.1109/TAES.2020.2977791
28	MUHAMMAD M , GIAMBENE G , DE COLA T . QoS support in SGD-based high throughput satellite networks[J]. IEEE Trans.on Wireless Communications, 2016, 15 (12): 8477- 8491. doi: 10.1109/TWC.2016.2615618
29	YARR N , CERIOTTI M . Optimization of intersatellite routing for real-time data download[J]. IEEE Trans.on Aerospace and Electronic Systems, 2018, 54 (5): 2356- 2369. doi: 10.1109/TAES.2018.2815880
30	ASUQUO P , CRUICKSHANK H , OGAH C P A , et al. A distributed trust management scheme for data forwarding in satellite DTN emergency communications[J]. IEEE Journal on Selected Areas in Communications, 2018, 36 (2): 246- 256. doi: 10.1109/JSAC.2018.2804098
31	WANG J J , JIANG C X , WEI Z X , et al. Joint UAV hovering altitude and power control for space-air-ground IOT networks[J]. IEEE Internet of Things Journal, 2019, 6 (2): 1741- 1753. doi: 10.1109/JIOT.2018.2875493

参数	数值
轨道数目	4
轨道高度/km	25 000
轨道倾角/(°)	60
每个轨道上卫星数目	8
升交点赤经/(°)	78、268、258、348
平近点角度间隔/(°)	45
平近点角度初始值/(°)	0
偏心率	0
近地点幅角/(°)	0
数据包长度/kB	10
链路容量/kB	300
时隙长度/s	3
最大迭代次数	100
收敛门限	0.001

[1]	刘高赛, 姜兴龙, 李华旺, 梁广. 基于位置感知的大规模LEO星座分布式路由算法[J]. 系统工程与电子技术, 2022, 44(11): 3529-3536.
[2]	林静然, 陈英, 杨金泰, 张伟, 杨健, 江志浩. 面向OFDM无线中继系统的功率分配算法[J]. 系统工程与电子技术, 2021, 43(2): 537-545.
[3]	石晓东, 李勇军, 赵尚弘, 王蔚龙, 王星宇. 基于SDN的卫星网络多QoS目标优化路由算法[J]. 系统工程与电子技术, 2020, 42(6): 1395-1401.
[4]	周剑, 张胜东, 王娟, 韩崇, 孙力娟. 基于不确定链路参数的卫星网络路由算法[J]. 系统工程与电子技术, 2019, 41(5): 1143-1148.
[5]	周剑, 孙力娟, 韩崇, 郭小海, 王娟. 面向多层卫星网络的信道资源管理方法[J]. 系统工程与电子技术, 2017, 39(8): 1857-1863.
[6]	朱林, 方胜良, 胡卿, 骆盛, 樊甫华. 卫星时变拓扑网络节点重要度评估方法[J]. 系统工程与电子技术, 2017, 39(6): 1274-1279.
[7]	王娟, 郭俞江, 孙力娟, 周剑, 韩崇. 面向双层卫星网络的多业务负载均衡算法[J]. 系统工程与电子技术, 2016, 38(9): 2156-2161.
[8]	胡华全，吴玲达，杨超，于荣欢，宋汉辰. 卫星时变拓扑网络多视图可视化分析框架[J]. 系统工程与电子技术, 2014, 36(2): 312-316.
[9]	肖楠, 梁俊, 张衡阳, 王轶, 尹译. 一种适用于卫星网络信道预约的统计预测机制[J]. 系统工程与电子技术, 2014, 36(12): 2518-2525.
[10]	高丽娟，蒋太杰. 卫星网络连接度与高效路由算法分析与改进[J]. 系统工程与电子技术, 2014, 36(10): 2071-2075.
[11]	胡华全，吴玲达，杨超，宋汉辰. 基于图序列的卫星网络时变拓扑可视分析[J]. 系统工程与电子技术, 2014, 36(10): 2065-2070.
[12]	孙力娟, 蔡冬, 肖甫, 叶晓国, 王汝传. 改进的卫星网络多路径并行传输算法[J]. Journal of Systems Engineering and Electronics, 2012, 34(3): 582-587.
[13]	孙力娟, 谢慧婷1, 肖甫, 叶晓国, 王汝传. 一种基于优先级的卫星网络AQM算法[J]. Journal of Systems Engineering and Electronics, 2011, 33(9): 2090-2095.
[14]	李远，苏菲，朱华勇，沈林成. 部分可观条件下空对地打击中的动态资源分配[J]. Journal of Systems Engineering and Electronics, 2010, 32(9): 1931-1936.

卫星网络时隙分配算法与路由规划优化

Optimization of time slot allocation algorithm and routing scheduling for satellite network

RichHTML

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

图/表 10

参考文献 31

相关文章 14

编辑推荐

Metrics

本文评价