卫星网络动态资源图多QoS约束路由算法

doi:10.7527/S10006893.2021.26422

Abstract

Abstract:

To address the problems of available path failure during network update caused by topology change of high dynamic satellite network and difficulty in meeting QoS requirements， a Dynamic Resource Graph of Virtual Node multi-QoS constraint Routing algorithm （DRGVN-QR） is proposed based on the SDN architecture. According to the information including switching state， cache of the nodes and remaining bandwidth， and delay of the link， as well as the network topology of the virtual node， a dynamic resource graph model of the virtual node is established. According to the resource graph model， an optimization model of the minimum path cost is established. The Ant Colony Algorithm （ACO） is used to concurrently find the optimal path set within a period of time for each connection request， and the value of the pheromone volatilization coefficient is discussed to improve the path quality and algorithm performance. Finally， to adapt to the time variability of satellite networks， an idempotent weighting formula is designed to find the optimal path in a period of time. Simulation results show that the algorithm proposed can avoid the transmission interruption caused by path failure， and improve the QoS of network. Compared with other algorithms， this algorithm reduces the average end-to-end delay， network packet loss rate and delay jitter.

Key words: satellite network, Software Defined Network (SDN), dynamic resource graph, multi-objective optimization, ant colony algorithm

CLC Number:

V474.2

Chao LIANG, Li YANG, Chengsheng PAN, Yaowen QI. Multi-QoS constraints routing algorithm based on satellite network dynamic resource graph[J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2023, 44(1): 326422-326422.

Figures/Tables 9

Fig. 1

Fig. 2

Table 1

Dynamic resource information

时刻	切换状态	剩余带宽/MB	传输时延/ms	节点缓存/MB	占用缓存/MB
$t 0$	$S v (t 0)$	$B u, v (t 0)$	$D u, v p (t 0)$	$B u f v$	$U v (t 0)$
$t 0 + Δ t$	$S v (t 0 + Δ t)$	$B u, v (t 0 + Δ t)$	$D u, v p (t 0 + Δ t)$	$B u f v$	$U v (t 0 + Δ t)$
︙	︙	︙	︙	︙	︙
$t 0 + n Δ t$	$S v (t 0 + n Δ t)$	$B u, v (t 0 + n Δ t)$	$D u, v p (t 0 + n Δ t)$	$B u f v$	$U v (t 0 + n Δ t)$

Table 1

Fig. 3

Fig. 4

Fig. 5

Fig. 6

Fig. 7

Fig. 8

References 23

1	汪春霆. 专刊: 天地一体化信息网络内容导读[J]. 无线电通信技术, 2020, 46(5): 491-492.
	WANG C T. Special issue: Introduction to the content of the information network of the integration of heaven and earth[J]. Radio Communications Technology, 2020, 46(5): 491-492 (in Chinese).
2	RUIZ DE AZÚA J A, CALVERAS A, CAMPS A. Internet of satellites (IoSat): Analysis of network models and routing protocol requirements[J]. IEEE Access,2018, 6: 20390-20411.
3	潘成胜, 行贵轩, 戚耀文, 等. 多状态空间信息网络拓扑生成优化算法[J]. 航空学报, 2020, 41(4): 323546.
	PAN C S, XING G X, QI Y W, et al. Topological generation and optimization method in multi-state space information network[J]. Acta Aeronautica et Astronautica Sinica, 2020, 41(4): 323546 (in Chinese).
4	LI J, LU H C, XUE K P, et al. Temporal netgrid model-based dynamic routing in large-scale small satellite networks[J]. IEEE Transactions on Vehicular Technology, 2019, 68(6): 6009-6021.
5	ZHANG H, WANG C F. Research on routing control with delay constraint based on contact plan for integrated satellite terrestrial network[C]∥2020 IEEE 8th International Conference on Information, Communication and Networks. Piscataway: IEEE Press, 2020: 155-159.
6	HUANG Z F, ZHANG Q, XIN X J, et al. DTN routing algorithm based on service probability and limited copy for satellite networks[C]∥2017 16th International Conference on Optical Communications and Networks (ICOCN). Piscataway: IEEE Press, 2017: 1-3.
7	ZHANG L, YAN F, ZHANG Y Y, et al. A routing algorithm based on link state information for LEO satellite networks[C]∥2020 IEEE Globecom Workshops (GC Wkshps. Piscataway: IEEE Press, 2020: 1-6.
8	JIANG F, ZHANG Q Y, YANG Z H, et al. A space–time graph based multipath routing in disruption-tolerant earth-observing satellite networks[J]. IEEE Transactions on Aerospace and Electronic Systems, 2019, 55(5): 2592-2603.
9	TANG F L, ZHANG H T, YANG L T. Multipath cooperative routing with efficient acknowledgement for LEO satellite networks[J]. IEEE Transactions on Mobile Computing, 2019, 18(1): 179-192.
10	MARCHESE M, PATRONE F. E-CGR: Energy-aware contact graph routing over nanosatellite networks[J]. IEEE Transactions on Green Communications and Networking, 2020, 4(3): 890-902.
11	WANG J, 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.
12	YAOWEN Q, LI Y, CHENGSHENG P, et al. CGR-QV: A virtual topology DTN routing algorithm based on queue scheduling[J]. China Communications, 2020, 17(7): 113-123.
13	LIU W, TAO Y, LIU L. Load-balancing routing algorithm based on segment routing for traffic return in LEO satellite networks[J]. IEEE Access, 2019, 7: 112044-112053.
14	ZHANG T, LI H Y, ZHANG S, et al. STAG-based QoS support routing strategy for multiple missions over the satellite networks[J]. IEEE Transactions on Communications, 2019, 67(10): 6912-6924.
15	RATHEE M, KUMAR S, GANDOMI A H, et al. Ant colony optimization based quality of service aware energy balancing secure routing algorithm for wireless sensor networks[J]. IEEE Transactions on Engineering Management, 2021, 68(1): 170-182.
16	魏德宾, 刘健, 潘成胜, 等. 卫星网络中基于多QoS约束的蚁群优化路由算法[J]. 计算机工程, 2019, 45(7): 114-120.
	WEI D B, LIU J, PAN C S, et al. Ant colony optimization routing algorithm based on multi-QoS constraints in satellite networks[J]. Computer Engineering, 2019, 45(7): 114-120 (in Chinese).
17	杨林峰. 基于蚁群优化算法的SDN负载均衡研究[D]. 哈尔滨: 哈尔滨工程大学, 2019: 32-35.
	YANG L F. Research on SDN load balancing based on ant colony optimization algorithm[D]. Harbin: Harbin Engineering University, 2019: 32-35 (in Chinese).
18	吕娜, 陈坤, 陈柯帆, 等. 适应拓扑变化的拥塞最小化网络更新策略[J]. 航空学报, 2020, 41(7): 323661.
	LYU N, CHEN K, CHEN K F, et al. Congestion-minimization network update strategy for topology changes[J]. Acta Aeronautica et Astronautica Sinica, 2020, 41(7): 323661 (in Chinese).
19	叶晓国, 肖甫, 孙力娟, 等. 卫星移动通信网络切换算法的研究[J]. 计算机科学, 2009, 36(9): 79-82.
	YE X G, XIAO F, SUN L J, et al. Research on handover algorithm of satellite mobile communication network[J]. Computer Science, 2009, 36(9): 79-82 (in Chinese).
20	GUO A D, ZHAO C L, XU F M, et al. LEO satellite routing algorithm in software defined space terrestrial integrated network[C]∥2017 17th International Symposium on Communications and Information Technologies (ISCIT). Piscataway: IEEE Press, 2017: 1-6.
21	WANG H T, WEN G L, LIU N J, et al. A load balanced routing algorithm based on congestion prediction for LEO satellite networks[J]. Cluster Computing, 2019, 22(4): 8025-8033.
22	刘闻. 蚁群算法及其应用研究[D]. 北京: 北京邮电大学, 2014: 24-28.
	LIU W. Research on the ant colony optimization algorithm and its applications[D]. Beijing: Beijing University of Posts and Telecommunications, 2014: 24-28 (in Chinese).
23	周雅, 谢卓辰, 刘沛龙, 等. 基于区域分流的低轨卫星星座星间负载均衡路由算法[J]. 中国科学院大学学报, 2021, 38(5): 687-695.
	ZHOU Y, XIE Z C, LIU P L, et al. Inter-satellite load balancing routing algorithm for LEO satellite constellation based on regional-traffic-detour[J]. Journal of University of Chinese Academy of Sciences, 2021, 38(5): 687-695 (in Chinese).

[1]	Qian YANG, Haoran ZHENG, Xianda CHENG, Wei DONG. Optimization design method for hot air anti⁃icing system based on bleed air control [J]. Acta Aeronautica et Astronautica Sinica, 2023, 44(S2): 729285-729285.
[2]	Jiezhong DONG, Wuli CHU, Haoguang ZHANG, Bo LUO, Song YAN. Flow control mechanism of diffuser cascade with wavy leading⁃edge based on causal network analysis [J]. Acta Aeronautica et Astronautica Sinica, 2023, 44(19): 128336-128336.
[3]	Debin WEI, Yu CAO, Li YANG, Chengsheng PAN. A routing strategy for LEO satellite network based on space⁃time⁃level [J]. Acta Aeronautica et Astronautica Sinica, 2023, 44(16): 327994-327994.
[4]	ZOU Ziyuan, CHEN Qifeng. Decision tree-based target assignment for confrontation of multiple space vehicles [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2022, 43(S1): 726910-726910.
[5]	HAN Kai, DONG Richang, SHAO Fengwei, GONG Wenbin, CHANG Jiachao. Dynamic topology optimization of navigation satellite inter-satellite links network based on improved genetic algorithm [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2022, 43(9): 326095-326095.
[6]	SUN Gang, PENG Shuang, CHEN Hao, WU Jiangjiang, LI Jun. Multi-objective optimization method oriented to integrated scenario of TT & C resources and data transmission resources [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2022, 43(9): 326114-326114.
[7]	ZHENG Shuai, WANG Zihan, ZHAO Haoran, YANG Pengtao, HONG Jun. Layout optimization method of aircraft fuel gauging sensor based on differential evolution algorithm [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2022, 43(8): 125809-125809.
[8]	JING Tao, TIAN Xitian. Multi-objective optimization method for aircraft tolerance allocation based on Monte Carlo-adaptive differential evolution algorithm [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2022, 43(3): 425278-425278.
[9]	CAI Ruiyan, LIU Yanhong, WEI Debin. k-terminal reliability analysis of satellite network based on QoS guarantee [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2022, 43(1): 326020-326020.
[10]	LUO Qing, ZHANG Tao, SHAN Peng, ZHANG Wentao, LIU Zihao. Generating reconfiguration blueprints for IMA systems based on improved Q-learning [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2021, 42(8): 525792-525792.
[11]	ZHANG Junfeng, YOU Lubao, YANG Chunwei, HU Rong. Arrival sequencing and scheduling based on multi-objective Imperialist competitive algorithm [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2021, 42(6): 324439-324439.
[12]	SUN Gang, CHEN Hao, PENG Shuang, DU Chun, LI Jun. Multi-objective optimization algorithm for satellite range scheduling based on preference MOEA [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2021, 42(4): 524475-524475.
[13]	HE Cheng, MA Dongli, JIA Yuhong, YANG Muqing, CHEN Gang. Multi-objective optimization design for joined-wing SensorCraft [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2021, 42(12): 224761-224761.
[14]	LI Xianqiang, MA Rong, ZHANG Shen, HOU Yanze, PEI Yifei. Improved design of ant colony algorithm and its application in path planning [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2020, 41(S2): 724381-724381.
[15]	LIU Jixin, JIANG Hao, DONG Xinfang, LAN Sijie, WANG Haozhe. Dynamic collaborative sequencing method for arrival flights based on air traffic density [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2020, 41(7): 323717-323717.

Multi-QoS constraints routing algorithm based on satellite network dynamic resource graph

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 9

References 23

Related Articles 15

Recommended Articles

Metrics

Comments