结合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). |
/
| 〈 |
|
〉 |