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

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

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

CLC Number:

TN927

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.

Figures/Tables 10

Fig.1

Fig.2

Fig.3

Table 1

Fig.4

Fig.5

Fig.6

Fig.7

Fig.8

Fig.9

References 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]	Gaosai LIU, Xinglong JIANG, Huawang LI, Guang LIANG. Large-scale LEO constellation distributed routing algorithm based on location awareness [J]. Systems Engineering and Electronics, 2022, 44(11): 3529-3536.
[2]	Xiaodong SHI, Yongjun LI, Shanghong ZHAO, Weilong WANG, Xingyu WANG. Multi-QoS objective optimization routing algorithm of satellite network based on SDN [J]. Systems Engineering and Electronics, 2020, 42(6): 1395-1401.
[3]	ZHOU Jian, ZHANG Shengdong, WANG Juan, HAN Chong, SUN Lijuan. Routing strategy for satellite networks based on uncertain link parameters [J]. Systems Engineering and Electronics, 2019, 41(5): 1143-1148.
[4]	ZHOU Jian, SUN Lijuan, HAN Chong, GUO Xiaohai, WANG Juan. Channel resources management strategy for multilayer satellite network [J]. Systems Engineering and Electronics, 2017, 39(8): 1857-1863.
[5]	ZHU Lin, FANG Shengliang, HU Qing, LUO Sheng, FAN Fuhua. Evaluation method for time-varying satellite topology network node importance [J]. Systems Engineering and Electronics, 2017, 39(6): 1274-1279.
[6]	WANG Juan, GUO Yu-jiang, SUN Li-juan, ZHOU Jian, HAN Chong. Load balancing algorithm for multi-traffic in double layered satellite network [J]. Systems Engineering and Electronics, 2016, 38(9): 2156-2161.
[7]	HU Hua-quan， WU Ling-da， YANG Chao， YU Rong-huan， SONG Han-chen. Multiple view framework of visual analytics for time varying satellite topology network [J]. Systems Engineering and Electronics, 2014, 36(2): 312-316.
[8]	XIAO Nan, LIANG Jun, ZHANG Hengyang, WANG Yi, YIN Yi. Statistical prediction mechanism for channel reservationapplicable to satellite network [J]. Systems Engineering and Electronics, 2014, 36(12): 2518-2525.
[9]	GAO Li-juan，JIANG Tai-jie. Analysis on degree of satellite network connection and an improved efficient routing algorithm [J]. Systems Engineering and Electronics, 2014, 36(10): 2071-2075.
[10]	HU Hua-quan，WU Ling-da，YANG Chao，SONG Han-chen. Visual analysis for time-varying topologies of satellite networks based on graph sequence [J]. Systems Engineering and Electronics, 2014, 36(10): 2065-2070.
[11]	SUN Li-juan, CAI Dong, XIAO Fu, YE Xiao-guo, WANG Ru-chuan. Improved algorithm of concurrent multi-path transfer for satellite networks [J]. Journal of Systems Engineering and Electronics, 2012, 34(3): 582-587.
[12]	SUN Li-, XIE Hui-ting, XIAO Fu, YE Xiao-guo, WANG Ruchuan. Prioritybased active queue management algorithm for satellite networks [J]. Journal of Systems Engineering and Electronics, 2011, 33(9): 2090-2095.

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

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 10

References 31

Related Articles 12

Recommended Articles

Metrics

Comments