针对航天器大规模时间敏感组网应用中面临的时间感知调度（TAS）调度求解规模较低，速度较慢的问题，本文提出了一种基于基于距离矩阵和K-means聚类分组的DM-KM流量分组算法，并完成与之结合的增量式TAS调度方法设计。首先，构建流量网络模型，使用基于熵权法的加权综合距离矩阵表示流量之间的相关性。其次，设计并实现了结合DM-KM流量分组的增量式调度算法。本文提出的分组方法具有较大的组内相似性和较低的组间相似性，流量分组能够有效提升增量式调度求解速度。实验结果表明：与现有DoC-KM和CILP-KM分组算法相比，在1000条流量调度场景下，DM-KM算法在维持较高求解速度的基础上，拥有较好的可调度性。相较于其他调度算法，求解规模提升最大可达32.36%，为TSN网络在航天器大规模组网提供了分组增量式的调度解决方案。
In large-scale, time-sensitive networking applications for spacecraft, the Time-Aware Scheduling (TAS) scheduling problem 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 designs an incremental TAS scheduling method integrated with it. 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 Standard for Local and Metropolitan Area Networks - Bridges and Bridged Networks - Amendment 25: Enhancements for Scheduled Traffic[S].IEEE 802.1Qbv, 2016, pp. 1-57.
[2]赵国锋, 卢奕杉, 徐川等.面向航天器有线无线混合场景的流调度机制研究[J][J].电子与信息学报, 2023, 45(2):465-471
[3]Z Wei, Y Yi, L Mengyu, et al.Development of data bus technology in next generation spacecraft[C]. CSAA/IET International Conference on Aircraft Utility Systems, 2021. 109-114.
[4]ALNAJIM A, SALEHI S, SHEN Chien-Chung.Incremental path-selection and scheduling for time-sensitive networks[C]. IEEE Global Communications Conference. IEEE, 2019. p. 1-6.
[5]NAYAK N G, DüRR, F, ROTHERMEL K.Incremental flow scheduling and routing in time-sensitive software-defined networks[J][J].IEEE Transactions on Industrial Informatics, 2017, 14(5):2066-2075
[6]CRACIUNAS S S, Oliver R S, Steiner W.Scheduling Real-Time Communication in IEEE 802.1Qbv Time Sensitive Networks[C]. Proceedings of the 24th International Conference on Real-Time Networks and Systems. 2016.
[7]ZHANG Yanzhou, XU Qimin, Xu Lei, et al.Efficient Flow Scheduling for Industrial Time-Sensitive Networking: A Divisibility Theory-Based Method[J][J].IEEE Trans, 2022, 18(12):9312-9323
[8]ZHOU Xuan, HE Feng, ZHAO Luxi, et al.Hybrid Scheduling of Tasks and Messages for TSN-Based Avionics Systems[J].[J].IEEE Transactions on Industrial Informatics, 2023, 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].[J].IEEE Access, 2023, 11(1):61192-61233
[10]ZHANG, Yanzhou, CHEN Cailian, XU Qimin, et al.Scalable Scheduling for Industrial Time-Sensitive Networking: A Hyper-Flow Graph-Based Scheme[J].[J].IEEE/ACM Transactions on Networking, 2024, 6(32):4810-4825
[11]YAN Jinli, QUAN Wei, JIANG Xuyan, et al.Injection Time Planning: Making CQF Practical in Time-Sensitive Networking[C]. IEEE INFOCOM 2020-IEEE Conference on Computer Communications. IEEE, 2020.
[12]YU Weihao, RUAN Ke, TANG Hong, et al.Routing hypergraph convolutional recurrent network for network traffic prediction[J].[J].Applied Intelligence, 2023, 53(12):16126-16137
[13]YU Qinghan; GU Ming.Adaptive group routing and scheduling in multicast time-sensitive networks[J].[J].IEEE Access, 2020, 8(1):37855-37865
[14]ATALLAH A A, HAMAD G B, MOHAMED O A.Routing and Scheduling of Time-Triggered Traffic in Time-Sensitive Networks[J].[J].IEEE Transactions on Industrial Informatics, 2019, 16(7):4525-4534
[15]WANG Xiaolong, YAO Haipeng, MAI Tianle, et al.Joint Routing and Scheduling With Cyclic Queuing and Forwarding for Time-Sensitive Networks[J].[J].IEEE Transactions on Vehicular Technology, 2022, 72(3):3793-3804
[16]XU Lei, XU Qimin, TU Jingzheng, et al.Learning-based scalable scheduling and routing codesign with stream similarity partitioning for time-sensitive networking[J].[J].IEEE Internet of Things Journal, 2022, 9(15):13353-13363
[17]TU Jingzheng, XU Qimin, XU Lei, 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). Vol. 1. IEEE, 2021.Dürr F, NAYAK N G. No-wait Packet Scheduling for IEEE Time-sensitive Networks (TSN)[C]. Proceedings of the 24th international conference on real-time networks and systems. 2016.
[18]PANG Zaiyu, HUANG Xiao, LI Zonghui, et al.Flow Scheduling for Conflict-Free Network Updates in Time-Sensitive Software-Defined Networks[J].[J].IEEE Transactions on Industrial Informatics, 2020, 17(3):1668-1678
[19]何锋, 周璇, 赵长啸等.航空电子系统机载网络实时性能评价技术北京航空航天大学学报[J].Journal of Beijing University of Aeronautics and Astronautics, 2020, 46(4):651-665
CJA