基于遗传算法的时间敏感网络调度方法

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

华南理工大学学报(自然科学版) ›› 2024, Vol. 52 ›› Issue (2): 1-12.doi: 10.12141/j.issn.1000-565X.230032

基于遗传算法的时间敏感网络调度方法

陆以勤¹^,² 黄成海³ 陈嘉睿¹ 王海瀚¹ 覃健诚¹ 方婷¹

^1.华南理工大学电子与信息学院, 广东广州 510640
^2.华南理工大学信息网络工程研究中心, 广东广州 510640
^3.华南理工大学微电子学院, 广东广州 511442

收稿日期:2023-02-02 出版日期:2024-02-25 发布日期:2023-05-15
作者简介:陆以勤（1968-），男，教授，博士生导师，主要从事SDN、网络功能虚拟化、网络安全研究。E-mail：eeyqlu@scut.edu.cn
基金资助:
国家重点研发计划项目(2020YFB1805300)

Time Sensitive Network Scheduling Method Based on Genetic Algorithm

LU Yiqin¹^,² HUANG Chenghai³ CHEN Jiarui¹ WANG Haihan¹ QIN Jiancheng¹ FANG Ting¹

^1.School of Electronic and Information Engineering，South China University of Technology，Guangzhou 510640，Guangdong，China
^2.Information and Network Engineering and Research Center，South China University of Technology，Guangzhou 510640，Guangdong，China
^3.School of Microelectronics，South China University of Technology，Guangzhou 511442，Guangdong，China

Received:2023-02-02 Online:2024-02-25 Published:2023-05-15
About author:陆以勤（1968-），男，教授，博士生导师，主要从事SDN、网络功能虚拟化、网络安全研究。E-mail：eeyqlu@scut.edu.cn
Supported by:
the National Key R&D Program of China(2020YFB1805300)

摘要/Abstract

摘要：

随着网络技术的进步，车载网、工业物联网以及5G超高可靠低时延通信（uRLLC）等应用都需要时间敏感网络（TSN）来保证超低延时的确定性数据传输。TSN流量调度需要快速且精确的调度算法，现有的精确式求解方法复杂度高，在大规模联合调度时无法满足实时性。文中设计了一种性能更优的路由优化遗传算法（Routing-GA），结合路由和流量调度约束，能通过优化路由来提高调度算法求解效率，为链路负载均衡调度提供服务。该策略增加了调度的求解空间以及求解灵活性，具备元启发式算法的快速求近最优解特点，能够简单有效地处理大规模TSN路由约束联合调度问题。Routing-GA以时间敏感流最小端到端时延作为优化目标，联合考虑路由和TSN约束，并针对TSN传输问题特性提供一种低复杂度、高效率和高拓展性的遗传算法编码方式。此外，为了提高调度算法的性能，提出针对路由长度及链路负载均衡进行优化的交叉变异机制。实验结果表明所实现的Routing-GA能有效减少端到端时延，显著提高求解质量，进化率可以达到24.42%，平均只需要传统遗传算法（GA）迭代运行时间的12%，从而有效提高了算法的求解性能，满足TSN调度的约束要求。

关键词: 时间敏感网络, 遗传算法, 联合调度优化策略, 链路负载均衡

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

中图分类号:

TP393.0

陆以勤, 黄成海, 陈嘉睿, 等. 基于遗传算法的时间敏感网络调度方法[J]. 华南理工大学学报(自然科学版), 2024, 52(2): 1-12.

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.

图/表 15

图1

图2

图3

图4

图5

图6

图7

图8

图9

图10

表1

表2

图11

图12

图13

参考文献 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]	邱宇东, 王湛, 谢志燊. 基于混合算法的半刚性连接钢框架结构优化[J]. 华南理工大学学报(自然科学版), 2023, 51(6): 72-77.
[2]	陆以勤, 谢文静, 王海瀚, 等. 面向时间敏感网络的安全感知调度方法[J]. 华南理工大学学报(自然科学版), 2023, 51(5): 1-12.
[3]	陆以勤, 熊欣, 王猛, 等. TSN中基于链路负载均衡的AVB流量带宽分配方法[J]. 华南理工大学学报(自然科学版), 2023, 51(11): 1-9.
[4]	翁剑成, 王茂林, 林鹏飞, 等. 基于客流特征鉴别的公交跨线组合调度优化方法[J]. 华南理工大学学报(自然科学版), 2022, 50(9): 39-48.
[5]	秦雅琴, 钱正富, 谢济铭, 等. 基于社会力的交织区突发瓶颈段协同换道决策模型[J]. 华南理工大学学报(自然科学版), 2022, 50(7): 66-75.
[6]	郑亚晶, 李耀辉, 靳文舟. 考虑换乘客流的城市轨道交通网络末班车衔接优化研究[J]. 华南理工大学学报(自然科学版), 2022, 50(5): 32-39,72.
[7]	夏琴香, 李凯, 马骏, 等. 基于遗传算法的模具电极调度问题求解[J]. 华南理工大学学报(自然科学版), 2022, 50(3): 80-87.
[8]	周中, 邓卓湘, 陈云, 等. 基于GA-BP神经网络的泡沫轻质土强度预测[J]. 华南理工大学学报(自然科学版), 2022, 50(11): 125-132.
[9]	刘璇, 王子航, 张桐瑞, 等. 港口重载AGV横向稳定的优化控制策略[J]. 华南理工大学学报(自然科学版), 2021, 49(8): 113-121.
[10]	李静王晨张家旭. 基于UniTire轮胎模型的汽车行驶速度估计[J]. 华南理工大学学报（自然科学版）, 2021, 49(5): 47-55.
[11]	罗玉涛, 周天阳, 许晓通. 基于遗传算法的四轮转向－驱动汽车时变 LQR 控制[J]. 华南理工大学学报（自然科学版）, 2021, 49(3): 114-122.
[12]	晋刚何志豪王英俊. 基于遗传算法的5G频率选择表面形状优化方法[J]. 华南理工大学学报（自然科学版）, 2021, 49(11): 95-105.
[13]	李家乐刘真伯王雪菲. 智能电网下支持充放电策略的电动汽车配送路径优化[J]. 华南理工大学学报（自然科学版）, 2021, 49(10): 31-40.
[14]	靳文舟胡为洋邓嘉怡, 等. 基于混合算法的需求响应公交灵活调度模型 [J]. 华南理工大学学报（自然科学版）, 2021, 49(1): 123-133.
[15]	刘刚, 郭德明, 郑文成, 等. 基于轴向热路模型的架空地线与预绞丝接触端面接触电阻的计算[J]. 华南理工大学学报（自然科学版）, 2020, 48(7): 9-19.

基于遗传算法的时间敏感网络调度方法

Time Sensitive Network Scheduling Method Based on Genetic Algorithm

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 15

参考文献 18

相关文章 15

编辑推荐

Metrics

本文评价