结合DM-KM分组的TAS机制增量式调度方法
收稿日期: 2025-04-09
修回日期: 2025-05-06
录用日期: 2025-06-16
网络出版日期: 2025-07-25
基金资助
国家自然科学基金(U2333213);国家自然科学基金(62301014);国家自然科学基金(62071023)
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)
针对航天器大规模时间敏感组网应用中面临的时间感知调度（TAS）调度求解规模较低、速度较慢的问题，提出了一种基于距离矩阵和K-means聚类分组的DM-KM流量分组算法，并完成与之结合的增量式TAS调度方法设计。首先，构建流量网络模型，使用基于熵权法的加权综合距离矩阵表示流量之间的相关性。在该模型的基础上，设计并实现了结合DM-KM流量分组的增量式调度算法。所提出的分组方法具有较大的组内相似性和较低的组间相似性，流量分组能够有效提升增量式调度求解速度。实验结果表明：与现有DoC-KM和CILP-KM分组算法相比，在1 000条流量调度场景下，DM-KM算法在维持较高求解速度的基础上，拥有较好的可调度性。相较于其他调度算法，求解规模提升最大可达32.36%，为TSN网络在航天器大规模组网提供了分组增量式的调度解决方案。
关键词： 时间敏感网络（TSN）; 时间感知调度（TAS）; 流量分组; 增量式求解框架; 箭载网络
景世龙 , 施睿 , 周璇 , 闫嘉伟 , 何锋 . 结合DM-KM分组的TAS机制增量式调度方法[J]. 航空学报, 2026 , 47(2) : 332097 -332097 . DOI: 10.7527/S1000-6893.2025.32097
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.
| [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