ACTA AERONAUTICAET ASTRONAUTICA SINICA >
Incremental TAS scheduling method with DM-KM grouping
Received date: 2025-04-09
Revised date: 2025-05-06
Accepted date: 2025-06-16
Online published: 2025-07-25
Supported by
National Natural Foundation of China(U2333213)
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.
Shilong JING , Rui SHI , Xuan ZHOU , Jiawei YAN , Feng HE . Incremental TAS scheduling method with DM-KM grouping[J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2026 , 47(2) : 332097 -332097 . DOI: 10.7527/S1000-6893.2025.32097
| [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）. |
/
| 〈 |
|
〉 |
CJA