Time Sensitive Network Scheduling Method Based on Genetic Algorithm

doi:10.12141/j.issn.1000-565X.230032

Abstract

Abstract:

With the progress of network technology, applications such as vehicle networks, industrial Internet of Things and 5G ultra-reliable low-delay communication (uRLLC) all require TSN to ensure ultra-low delay deterministic data transmission. TSN traffic scheduling requires a fast and accurate scheduling algorithm. The existing accurate solution methods are of high complexity and cannot meet the real-time requirements in large-scale joint scheduling. This paper designed a routing optimization genetic algorithm (Routing-GA) with better performance. Combining routing and traffic scheduling constraints, it can improve the efficiency of scheduling algorithm by optimizing routing and provide services for link load balancing scheduling. This strategy increases the space and flexibility of scheduling, and has the characteristics of fast near-optimal solution of meta-heuristic algorithm. It can deal with large-scale TSN routing constraint joint scheduling problem simply and effectively. Routing-GA takes the minimum end-to-end delay of time-sensitive flow as the optimization objective, considers Routing and TSN constraints jointly, and provides a genetic algorithm coding method with low complexity, high efficiency and high scalability according to the characteristics of TSN transmission problems. In addition, in order to improve the performance of the scheduling algorithm, a crossover mutation mechanism was proposed to optimize the route length and link load balancing. The experimental results show that the realized Routing-GA can effectively reduce the end-to-end delay and significantly improve the solution quality. The evolution rate can reach 24.42%, and the average iteration time of traditional genetic algorithm (GA) is only 12%. It can effectively improve the performance of the algorithm and meet the constraint requirements of TSN scheduling.

Key words: time-sensitive network, genetic algorithm, joint scheduling optimization strategy, link load balancing

CLC Number:

TP393.0

LU Yiqin, HUANG Chenghai, CHEN Jiarui, et al. Time Sensitive Network Scheduling Method Based on Genetic Algorithm[J]. Journal of South China University of Technology(Natural Science Edition), 2024, 52(2): 1-12.

Figures/Tables 15

Fig.1

Fig.2

Fig.3

Fig.4

Fig.5

Fig.6

Fig.7

Fig.8

Fig.9

Fig.10

Table 1

Table 2

Fig.11

Fig.12

Fig.13

References 18

1	IEEE 802.1 GroupWorking．Institute of electrical and electronics engineers，time-sensitive networking［EB/OL］．［2022-12-25］．.
2	韩运实.装箱问题方法研究及其集成应用［D］．青岛：中国海洋大学，2004.
3	STEINER W ．An evaluation of SMT-based schedule synthesis for time-triggered multi-hop networks［C］∥Proceedings of the 2010 31st IEEE Real-Time Systems Symposium．San Diego，CA：IEEE，2010：375-384.
4	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 International Conference on Real-time Networks & Systems．Brest：ACM，2016：183-192.
5	YU N， YAEGASHI R， NGUYEN A，et al ．Real-time reconfiguration of time-aware shaper for ULL transmission in dynamic conditions［J］．IEEE Access，2021，9：115246-115255.
6	PAHLEVAN H M， TABASSAM N， OBERMAISSER R ．Heuristic list scheduler for time triggered traffic in time sensitive networks［J］．ACM SIGBED Review，2019，16（1）：15-20.
7	PAHLEVAN H M， OBERMAISSER R ．Genetic algorithm for scheduling time-triggered traffic in time-sensitive net-works［C］∥Proceedings of the IEEE 23rd International Conference on Emerging Technologies and Factory Automation（ETFA）．Politecnico Torino，Torino：IEEE，2018：337-344.
8	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．Brest：ACM，2016：203-212.
9	IEEE 802.1 GroupWorking．IEEE standard for local and metropolitan area networks-bridges and bridged networks-amendment 25：enhancements for scheduled traffic［EB/OL］．（2016-08-30）［2022-12-25］．.
10	YU Q H， WAN H， ZHAO X，et al ．Online scheduling for dynamic VM migration in multicast time-sensitive networks［J］．IEEE Transactions on Industrial Informatics，2020，16（6）：3778-3788.
11	ARESTOVA A， HIELSCHER K S J， GERMAN R ．Design of a hybrid genetic algorithm for time-sensitive networking［C］∥Proceedings of the 20th International GI/ITG Conference on Measurement，Modelling and Evaluation of Computing Systems． Saarbrucken：Springer，2020：99-117.
12	HEILMANN F， FOHLER G ．Size-based queuing：an approach to improve bandwidth utilization in TSN networks［J］．ACM SIGBED Review，2019，16（1）：9-14.
13	NASRALLAH A， BALASUBRAMANIAN V， THYAGATURU A，et al ．Reconfiguration algorithms for high precision communications in time sensitive networks ［C］∥Proceedings of the 2019 IEEE Globecom Workshops．Waikoloa，HI：IEEE，2019：1-6.
14	NASRALLAH A， THYAGATURU A S， ALHARBI Z，et al ．Performance comparison of IEEE 802.1 TSN time aware shaper （TAS） and asynchronous traffic shaper （ATS）［J］．IEEE Access，2019，7：44165-44181.
15	SAID S B H， TRUONG Q H，BOC M ．SDN-based configuration solution for IEEE 802.1 time sensitive net-working （TSN）［J］．ACM SIGBED Review，2019，16（1）：27-32.
16	VLK M， HANZALEK Z， BREJCHOVA K，et al ．Enhancing schedulability and throughput of time-triggered traffic in IEEE 802.1Qbv time-sensitive networks［J］．IEEE Transactions on Communications，2020，11：5-13.
17	ENNS R， BJÖRKLUND M， BIERMAN A，et al ．Network configuration protocol （NETCONF）［EB/OL］．（2011-06-01）［2023-01-15］．.
18	高亮，张国辉，王晓娟．柔性作业车间调度智能算法及其应用［M］∥李培根．先进生产规划与调度理论研究．武汉：华中科技大学出版社，2012：70-163.

流分类	长度/byte	周期/μs
1	350~1 350	750
3	1 350~3 350	500
4	1 350~3 350	1 500

迭代次数	时间敏感流数量	端到端时延/μs		进化率/%
迭代次数	时间敏感流数量	传统GA	Routing-GA	传统GA	Routing-GA
100	20	1 402	1 276	11.65	14.41
	30	3 074	2 581	15.14	19.73
	40	4 975	3 897	16.53	20.71
	50	7 014	5 463	9.58	18.55
200	20	1 349	1 159	11.92	16.94
	30	2 820	2 226	19.85	19.62
	40	4 725	3 611	16.87	24.42
	50	6 847	5 158	14.95	20.54

[1]	QIU Yudong, WANG Zhan, XIE Zhishen. Optimization for Steel Frames with Semirigid Connections Based on Hybrid Algorithms [J]. Journal of South China University of Technology(Natural Science Edition), 2023, 51(6): 72-77.
[2]	LU Yiqin, XIE Wenjing, WANG Haihan, et al. Security-Aware Scheduling Method for Time-Sensitive Networking [J]. Journal of South China University of Technology(Natural Science Edition), 2023, 51(5): 1-12.
[3]	LU Yiqin, XIONG Xin, WANG Meng, et al.. A Bandwidth Allocation Method of AVB Traffic Based on Link Load Balancing in TSN [J]. Journal of South China University of Technology(Natural Science Edition), 2023, 51(11): 1-9.
[4]	WENG Jiancheng, WANG Maolin, LIN Pengfei, et al. Cross-line Combined Bus Scheduling Optimization Method Based on Passenger Flow Characteristic Identification [J]. Journal of South China University of Technology(Natural Science Edition), 2022, 50(9): 39-48.
[5]	QIN Yaqin, QIAN Zhengfu, XIE Jiming, et al. Cooperative Lane Change Decision-Making Model of Bottleneck Emergency Section in Weaving Area Based on Social Force [J]. Journal of South China University of Technology(Natural Science Edition), 2022, 50(7): 66-75.
[6]	ZHENG Yajing, LI Yaohui, JIN Wenzhou. Connection Scheme Optimization of Last Trains of Urban Mass Transit Network Based on Considering the Transfer Passengers [J]. Journal of South China University of Technology(Natural Science Edition), 2022, 50(5): 32-39,72.
[7]	XIA Qinxiang, LI Kai, MA Jun, et al. Die Electrode Scheduling Problem Solution Based on Genetic Algorithm [J]. Journal of South China University of Technology(Natural Science Edition), 2022, 50(3): 80-87.
[8]	ZHOU Zhong, DENG Zhuoxiang, CHEN Yun, et al. Strength Prediction of Foam Light Soil Based on GA-BP Neural Network [J]. Journal of South China University of Technology(Natural Science Edition), 2022, 50(11): 125-132.
[9]	LIU Xuan, WANG Zihang, ZHANG Tongrui, et al. Optimal Control Strategy for Lateral Stability of Port Heavy-Duty AGV [J]. Journal of South China University of Technology(Natural Science Edition), 2021, 49(8): 113-121.
[10]	LI Jing WANG Chen ZHANG Jiaxu. Vehicle Speed Estimation Based on UniTire Model [J]. Journal of South China University of Technology (Natural Science Edition), 2021, 49(5): 47-55.
[11]	LUO Yutao, ZHOU Tianyang, XU Xiaotong. Time-Varying LQR Control of Four-Wheel Steer /Drive Vehicle Based on Genetic Algorithm [J]. Journal of South China University of Technology (Natural Science Edition), 2021, 49(3): 114-122.
[12]	JIN Gang HE Zhihao WANG Yingjun. 5G Frequency Selection Surface Shape Optimization Method Based on Genetic Algorithm [J]. Journal of South China University of Technology (Natural Science Edition), 2021, 49(11): 95-105.
[13]	LI Jiale LIU Zhenbo WANG Xuefei. Distribution Path Optimization of Electric Vehicles Considering Charging and Discharging Strategy in Smart Grid [J]. Journal of South China University of Technology (Natural Science Edition), 2021, 49(10): 31-40.
[14]	JIN Wenzhou, HU Weiyang, DENG Jiayi, et al. Flexible Scheduling Model of Demand Ｒesponse Transit Based on Hybrid Algorithm [J]. Journal of South China University of Technology (Natural Science Edition), 2021, 49(1): 123-133.
[15]	LIU Gang, GUO Deming, ZHENG Wencheng, et al. Axial Thermal Circuit Model-Based Calculation of Contact Ｒesistance of Contact Surface Between the Overhead Ground Wire and Armor Rod [J]. Journal of South China University of Technology (Natural Science Edition), 2020, 48(7): 9-19.