结合DM-KM分组的TAS机制增量式调度方法

doi:10.7527/S1000-6893.2025.32097

Abstract

Abstract:

In large-scale， time-sensitive networking applications for spacecraft， the Time-Aware Scheduling （TAS） scheduling often faces challenges such as relatively low solving scale and slow speed. This paper proposes a DM-KM traffic grouping algorithm based on a distance matrix and K-means clustering， and integrated with it， designs an incremental TAS scheduling method. First， a traffic network model is constructed， using a weighted comprehensive distance matrix based on the entropy weight method to represent the correlations between traffic flows. Then， an incremental scheduling algorithm combined with DM-KM traffic grouping is designed and implemented. The proposed grouping method achieves high intra-group similarity and low inter-group similarity， which effectively improves the solving speed of the incremental scheduling. Experimental results show that compared with the existing DoC-KM and CILP-KM grouping algorithms， the DM-KM algorithm achieves better schedulability while maintaining a high solving speed in a 1000-traffic scheduling scenario. Compared with other scheduling algorithms， the solving scale can be improved by up to 32.36%， providing a grouping and incremental scheduling solution for Time-Sensitive Networking （TSN） in large-scale spacecraft networks.

Key words: Time-Sensitive Network (TSN), Time-Aware Shaper (TAS), flow grouping, incremental solving framework, on-board network

CLC Number:

V443

Shilong JING, Rui SHI, Xuan ZHOU, Jiawei YAN, Feng HE. Incremental TAS scheduling method with DM-KM grouping[J]. Acta Aeronautica et Astronautica Sinica, 2026, 47(2): 332097.

Figures/Tables 9

Fig.1

Table 1

Symbol table

符号	意义
$τ$	单条TT流量
$T$	流量周期
$L$	流量帧长
$P$	流量路由
$O$	首次转发偏置时刻
$h$	路由跳数
$F$	流量集合
$e$	流量节点之间的相关性
$s i m i i n t r a$	组内相似性
$s i m i i n t e r$	组间相似性

Table 1

Fig.2

Fig.3

Fig.4

Fig.5

Fig.6

Table 2

Table 3

References 20

[1]	IEEE. IEEE Approved Draft Standard for Local and metropolitan area networks--Bridges and Bridged Networks： P802.1 ［S］. Piscataway： IEEE，2016.
[2]	ZHENG W， YANG Y， LIU MY， et al. Development of data bus technology in next generation spacecraft［C］∥ CSAA/IET International Conference on Aircraft Utility Systems （AUS 2020）. London： IET， 2020： 109-114.
[3]	赵国锋，卢奕杉，徐川，等. 面向航天器有线无线混合场景的流调度机制研究［J］. 电子与信息学报， 2023， 45（2）： 464-471.
	ZHAO G F， LU Y S， XU C， et al. Research on flow scheduling mechanism for spacecraft wired wireless hybrid scenario［J］. Journal of Electronics & Information Technology， 2023， 45（2）： 464-471 （in Chinese）.
[4]	ALNAJIM A， SALEHI S， SHEN C C. Incremental path-selection and scheduling for time-sensitive networks［C］∥2019 IEEE Global Communications Conference （GLOBECOM）. Piscataway： IEEE Press， 2019： 1-6.
[5]	NAYAK N G， DÜRR F， ROTHERMEL K. Incremental flow scheduling and routing in time-sensitive software-defined networks［J］. IEEE Transactions on Industrial Informatics， 2018， 14（5）： 2066-2075.
[6]	CRACIUNAS S S， OLIVER R S， CHMELÍK M， et al. Scheduling real-time communication in IEEE 802.1Qbv time sensitive networks［C］∥ Proceedings of the 24th International Conference on Real-Time Networks and Systems. New York： ACM， 2016： 183-192.
[7]	ZHANG Y Z， XU Q M， XU L， et al. Efficient flow scheduling for industrial time-sensitive networking： a divisibility theory-based method［J］. IEEE Transactions on Industrial Informatics， 2022， 18（12）： 9312-9323.
[8]	ZHOU X， HE F， ZHAO L X， et al. Hybrid scheduling of tasks and messages for TSN-based avionics systems［J］. IEEE Transactions on Industrial Informatics， 2024， 20（2）： 1081-1092.
[9]	STÜBER T， OSSWALD L， LINDNER S， et al. A survey of scheduling algorithms for the time-aware shaper in time-sensitive networking （TSN）［J］. IEEE Access， 2023， 11： 61192-61233.
[10]	ZHANG Y Z， CHEN C L， XU Q M， et al. Scalable scheduling for industrial time-sensitive networking： A hyper-flow graph-based scheme［J］. IEEE/ACM Transactions on Networking， 2024， 32（6）： 4810-4825.
[11]	YAN J L， QUAN W， JIANG X Y， et al. Injection time planning： Making CQF practical in time-sensitive networking［C］∥IEEE INFOCOM 2020-IEEE Conference on Computer Communications. Piscataway： IEEE Press， 2020： 616-625.
[12]	YU W H， RUAN K， TANG H， et al. Routing hypergraph convolutional recurrent network for network traffic prediction［J］. Applied Intelligence， 2023， 53（12）： 16126-16137.
[13]	YU Q H， GU M. Adaptive group routing and scheduling in multicast time-sensitive networks［J］. IEEE Access， 2020， 8： 37855-37865.
[14]	ATALLAH A A， HAMAD G B， MOHAMED O A. Routing and scheduling of time-triggered traffic in time-sensitive networks［J］. IEEE Transactions on Industrial Informatics， 2020， 16（7）： 4525-4534.
[15]	LI C， ZHANG Z Y， ZHENG W， et al. Joint routing and scheduling for dynamic applications in multicast time-sensitive networks［C］∥2021 IEEE International Conference on Communications Workshops（ICC Workshops）.Piscataway： IEEE Press， 2021： 1-6.
[16]	XU L， XU Q M， TU J Z， et al. Learning-based scalable scheduling and routing co-design with stream similarity partitioning for time-sensitive networking［J］. IEEE Internet of Things Journal， 2022， 9（15）： 13353-13363.
[17]	TU J Z， XU Q M， XU L， et al. SSL-SP： A semi-supervised-learning-based stream partitioning method for scale iterated scheduling in time-sensitive networks［C］∥ 2021 22nd IEEE International Conference on Industrial Technology （ICIT）. Piscataway： IEEE Press， 2021： 1182-1187.
[18]	PANG Z Y， HUANG X， LI Z H， et al. Flow scheduling for conflict-free network updates in time-sensitive software-defined networks［J］. IEEE Transactions on Industrial Informatics， 2021， 17（3）： 1668-1678.
[19]	何锋，周璇，赵长啸，等. 航空电子系统机载网络实时性能评价技术［J］. 北京航空航天大学学报， 2020， 46（4）： 651-665.
	HE F， ZHOU X， ZHAO C X， et al. Real-time performance evaluation technology of airborne network for avionics system［J］. Journal of Beijing University of Aeronautics and Astronautics， 2020， 46（4）： 651-665 （in Chinese）.
[20]	程博文，刘伟伟，何熊文，等. 猎户座飞船电子系统设计特点分析与启示［J］. 航天器工程， 2016， 25（4）： 102-107.
	CHENG B W， LIU W W， HE X W， et al. Research on Orion electronic system［J］. Spacecraft Engineering， 2016， 25（4）： 102-107 （in Chinese）.

案例	DM-KM	DoC-KM	CILP-KM
200	0.843 8	0.006 0	0.004 3
400	0.217 6	0.003 0	0.002 5
600	0.143 9	0.002 0	0.003 0
800	0.150 1	0.002 0	0.003 3
1 000	0.102 6	0.002 0	0.003 5

案例	DM-KM	DoC-KM	CILP-KM
200	0.081 5	0.032 9	0.027 4
400	0.025 3	0.017 7	0.016 2
600	0.010 3	0.010 4	0.016 4
800	0.005 5	0.014 1	0.019 0
1 000	0.000 3	0.010 5	0.018 2

Incremental TAS scheduling method with DM-KM grouping

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 9

References 20

Related Articles 15

Recommended Articles

Metrics

Comments

[1]	Jidong SU, Weilin XU, Shenghua ZHAI, Wei WANG, Yating HE. Practice and prospect of space AD hoc network technology [J]. Acta Aeronautica et Astronautica Sinica, 2024, 45(5): 529912-529912.
[2]	Xiaoping LI, Min YANG, Bo YAO, Yanming LIU, Lei SHI, Haoyan LIU, Chengguang LI. Reliable communication technologies of reusable launch vehicles in cooperation with satellite during re-entry [J]. Acta Aeronautica et Astronautica Sinica, 2023, 44(23): 628906-628906.
[3]	Bo CHEN, Luyao GUO, Baozhu LIANG, Ze JIANG, Ming LI, Yundou XU, Yongsheng ZHAO. A two-way flat plate folding unit mechanism and motion process analysis [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2023, 44(2): 426720-426720.
[4]	HAN Bo, XU Yundou, YAO Jiantao, ZHENG Dong, ZHANG Shuo, ZHAO Yongsheng. Kinematic characteristics analysis and assembly application of a spatial symmetric 7R mechanism [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2019, 40(4): 422536-422536.
[5]	LIU Jingyu, CUI Yufu, XU Meng, HE Hongyan, YIN Huan, WANG Yu. Image restoration method for TDICCD camera with micro vibration [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2018, 39(S1): 722230-722230.
[6]	ZHOU Wangwang, YAO Peiyang, ZHANG Jieyong, WANG Xun, WEI Shuai. Combat intention recognition for aerial targets based on deep neural network [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2018, 39(11): 322468-322476.
[7]	WANG Hongwei, FAN Xiangyu, CHEN You, SONG Haifang, YANG Yuanzhi. Recognition method of multiple LFM signals with WHT based on entropy of slice [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2017, 38(1): 320023-320023.
[8]	HOU Yi, LIU Rongke, PENG Hao, ZHAO Ling, XIONG Qingxu. High-throughput GPU-based LDPC decoder architecture for space communication [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2017, 38(1): 320107-320107.
[9]	NIU Xiaoji, BAN Yalong, ZHANG Tisheng, LIU Jingnan. Research progress and prospects of GNSS/INS deep integration [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2016, 37(10): 2895-2908.
[10]	ZHANG Ke, LIU Zengjun, NIE Junwei, ZHU Xiangwei, SUN Guangfu. Spatial power combining based on distributed antennas in Earth station [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2016, 37(6): 1912-1920.
[11]	XIAO Yongsheng, ZHOU Jianjiang, HUANG Lizhen, ZHANG Xiangyang. Radio frequency stealth radar signal design based on OTR and SHT [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2016, 37(6): 1931-1939.
[12]	FAN Huaitao, ZHANG Zhimin, LI Ning, WEI Yunlong. Target geo-location method in airborne TOPSAR mode based on IMU [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2016, 37(5): 1587-1594.
[13]	HE Weikun, ZHAI Qiuping, WANG Xiaoliang, WU Renbiao. Wind turbine clutter detection and mitigation in scanning ATC surveillance radar [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2016, 37(4): 1316-1326.
[14]	SONG Qingping, LIU Rongke. A symbol rate estimation algorithm for autonomous radio in deep space [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2015, 36(7): 2301-2309.
[15]	CHEN Siyuan, ZHANG Xiaoling, SHI Jun, ZHANG Hai. A novel model of spin aircraft 3D SAR imaging and height measurement [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2015, 36(4): 1240-1249.