时间敏感网络中基于EDWF-MTTF的启发式调度算法

doi:10.11959/j.issn.1000-0801.2024009

电信科学 ›› 2024, Vol. 40 ›› Issue (2): 22-37.doi: 10.11959/j.issn.1000-0801.2024009

• 研究与开发 • 上一篇

时间敏感网络中基于EDWF-MTTF的启发式调度算法

李传煌¹^,², 廖君虎¹, 宣家栋¹, 徐琪², 张慧峰², 朱俊², 邹涛², 张汝云²

¹ 浙江工商大学信息与电子工程学院（萨塞克斯人工智能学院），浙江杭州 310018
² 之江实验室，浙江杭州 311121

修回日期:2024-01-11 出版日期:2024-02-01 发布日期:2024-02-01
作者简介:李传煌（1980- ），男，博士，浙江工商大学教授、硕士生导师，之江实验室双聘专家，主要研究方向为新一代网络技术、边缘计算、人工智能应用
廖君虎（1998- ），男，浙江工商大学硕士生，主要研究方向为软件定义网络、移动网络优先等
宣家栋（1998- ），男，硕士，浙江工商大学毕业生，主要研究方向为软件定义网络、时间敏感网络等
徐琪（1992- ），男，博士，之江实验室副研究员，主要研究方向为多模态网络、软件定义网络、时间敏感网络等
张慧峰（1992- ），女，博士，之江实验室助理研究员，主要研究方向为多模态网络、新型网络拓扑结构、时间敏感网络等
朱俊（1981- ），男，博士，之江实验室高级工程师，主要研究方向为新型网络架构、软件定义网络、网络管理与控制技术、网络协议设计与优化、卫星网络等
邹涛（1974- ），男，博士，之江实验室研究员，主要研究方向为多模态网络技术和新型网络体系架构
张汝云（1973- ），男，博士，之江实验室研究员，主要研究方向为多模态网络技术、工业互联网和网络通信安全
基金资助:
国家自然科学基金资助项目(U22A2005);国家自然科学基金资助项目(61871468);国家自然科学基金资助项目(62111540270);之江实验室科研攻关项目(2021LE0AC02);“慧眼行动”资助项目(D4DAC0D6);浙江省自然科学基金资助项目(LZ23F010003);浙江省自然科学基金资助项目(LQ23F010009);浙江省新型网络标准与应用技术重点实验室资助项目(2013E10012)

EDWF-MTTF-based heuristic scheduling algorithm in time-sensitive networks

Chuanhuang LI¹^,², Junhu LIAO¹, Jiadong XUAN¹, Qi XU², Huifeng ZHANG², Jun ZHU², Tao ZOU², Ruyun ZHANG²

¹ School of Information and Electronic Engineering (Sussex Artificial Intelligence Institute), Zhejiang Gongshang University, Hangzhou 310018, China
² Zhejiang Lab, Hangzhou 311121, China

Revised:2024-01-11 Online:2024-02-01 Published:2024-02-01
Supported by:
The National Natural Science Foundation of China(U22A2005);The National Natural Science Foundation of China(61871468);The National Natural Science Foundation of China(62111540270);The Key Research Project of Zhejiang Lab(2021LE0AC02);“Operation Wise Eyes” Project(D4DAC0D6);The Zhejiang Provincial Natural Science Foundation(LZ23F010003);The Zhejiang Provincial Natural Science Foundation(LQ23F010009);Zhejiang Provincial Key Laboratory of New Network Standards and Technologies (NNST)(2013E10012)

摘要/Abstract

摘要：

随着工业控制和信息网络的快速融合发展，基于以太网的时间敏感网络受到了广泛关注。时间敏感网络采用时间触发通信调度来保证数据传输的确定性。然而，现有调度算法难以快速计算大规模周期性流量的调度表。因此，设计了基于带权重的最早截止时间-最大传输时间优先的启发式调度算法，通过灵活适配流量排序权重以及回溯增强等方法，可以在较短时间内解决工业自动化场景中大规模流量的调度问题。实验结果表明，相比经典整数线性规划方法，带权重的最早截止时间-最大传输时间优先的启发式调度算法能更快地计算出大规模周期性流量调度表的较优解。

关键词: 时间敏感网络, 周期性流量, 流量调度, 启发式算法, 回溯法

Abstract:

With the rapid integration and development of industrial control and information networks, time-sensitive networks based on ethernet have received widespread attention.In these networks, time-triggered communication scheduling is adopted to ensure the determinacy of data transmission.However, existing scheduling algorithms have struggled to rapidly calculate the scheduling tables for large-scale periodic traffic.Therefore, a heuristic scheduling algorithm based on the earliest deadline with weight first-maximum transfer time first was designed.This algorithm, by flexibly adapting traffic sorting weights and enhancing backtracking methods, could resolve the scheduling issues of large-scale traffic in industrial automation scenarios in a relatively short time.Experimental results show that compared to the classic integer linear programming method, the earliest deadline with weight first-maximum transfer time first heuristic scheduling algorithm is able to calculate a more optimal solution for the scheduling table of large-scale periodic traffic more swiftly.

Key words: time-sensitive network, periodic traffic, traffic scheduling, heuristic algorithm, backtracking algorithm

中图分类号:

TP393

李传煌, 廖君虎, 宣家栋, 徐琪, 张慧峰, 朱俊, 邹涛, 张汝云. 时间敏感网络中基于EDWF-MTTF的启发式调度算法[J]. 电信科学, 2024, 40(2): 22-37.

Chuanhuang LI, Junhu LIAO, Jiadong XUAN, Qi XU, Huifeng ZHANG, Jun ZHU, Tao ZOU, Ruyun ZHANG. EDWF-MTTF-based heuristic scheduling algorithm in time-sensitive networks[J]. Telecommunications Science, 2024, 40(2): 22-37.

图/表 14

图1

图2

表1

模型中的参数定义"

参数	含义
V	节点集合
ε	链路集合
$D_{v_{a}}$	交换节点时延
$D_{e_{a, b}}$	链路时延
$C_{e_{a, b}}$	链路传输速率
F	流量集合
org_i	流i的发送节点
trg_i	流i的目标节点
T_i	流i的传输周期
p_i	流i的大小
r_i	流i在源节点最早的发送时间
${\tilde{d}}_{i}$	流i在目标节点最迟的接收时间
HP	超周期，所有流周期的最小公倍数
$t_{i}^{e_{a, b}}$	流i在链路(v_a,v_b)上的传输时间
$F_{e_{a, b}}$	通过链路(v_a,v_b)的所有流量集合
$f_{i, k}^{e_{a, b}}$	流i在链路(v_a,v_b)上传输的第k个帧
$s_{i, k}^{e_{a, b}}$	流i在链路(v_a,v_b) 上传输的第k 个帧的传输开始时间
R_i	流i的传输路径集合

表1

图3

图4

图5

图6

表2

表3

图7

图8

图9

图10

图11

参考文献 27

[1]	LO BELLO L , STEINER W . A perspective on IEEE time- sensitive networking for industrial communication and automation systems[J]. Proceedings of the IEEE, 2019,107(6): 1094-1120.
[2]	NASRALLAH A , THYAGATURU A S , ALHARBI Z ,et al. Ultra-low latency (ULL) networks:the IEEE TSN and IETF DetNet standards and related 5G ULL research[J]. IEEE Communications Surveys ＆ Tutorials, 2019,21(1): 88-145.
[3]	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 Press, 2016: 183-192.
[4]	POP P , RAAGAARD M L , CRACIUNAS S S ,et al. Design optimisation of cyber-physical distributed systems using IEEE time-sensitive networks[J]. IET Cyber-Physical Systems:Theory ＆ Applications, 2016,1(1): 86-94.
[5]	CRACIUNAS S S , OLIVER R S , STEINER W . Formal scheduling constraints for time-sensitive networks[J]. arXiv preprint, 2017,arXiv:1712.02246.
[6]	DOS SANTOS A C T , SCHNEIDER B , NIGAM V . TSNSCHED:automated schedule generation for time sensitive networking[C]// Proceedings of the 2019 Formal Methods in Computer Aided Design (FMCAD). Piscataway:IEEE Press, 2019: 69-77.
[7]	LI Q , LI D , JIN X ,et al. A simple and efficient time-sensitive networking traffic scheduling method for industrial scenarios[J]. Electronics, 2020,9(12): 2131.
[8]	HOUTAN B , ASHJAEI M , DANESHTALAB M ,et al. Synthesising schedules to improve QoS of best-effort traffic in TSN networks[C]// Proceedings of the 29th International Conference on Real-Time Networks and Systems. New York:ACM Press, 2021: 68-77.
[9]	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.
[10]	HELLMANNS D , HAUG L , HILDEBRAND M ,et al. How to optimize joint routing and scheduling models for TSN using integer linear programming[C]// Proceedings of the 29th International Conference on Real-Time Networks and Systems. New York:ACM Press, 2021: 100-111.
[11]	VLK M , HANZáLEK Z , BREJCHOVá K ,et al. Enhancing schedulability and throughput of time-triggered traffic in IEEE 802.1Qbv time-sensitive networks[J]. IEEE Transactions on Communications, 2020,68(11): 7023-7038.
[12]	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. New York:ACM Press, 2016: 203-212.
[13]	RAAGAARD M L , POP P , GUTIéRREZ M ,et al. Runtime reconfiguration of time-sensitive networking (TSN) schedules for fog computing[C]// Proceedings of the 2017 IEEE Fog World Congress (FWC). Piscataway:IEEE Press, 2017: 1-6.
[14]	PAHLEVAN 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.
[15]	PAHLEVAN M , OBERMAISSER R . Genetic algorithm for scheduling time-triggered traffic in time-sensitive networks[C]// Proceedings of the 2018 IEEE 23rd International Conference on Emerging Technologies and Factory Automation (ETFA). Piscataway:IEEE Press, 2018: 337-344.
[16]	ARESTOVA A , HIELSCHER K S J , GERMAN R . Design of a hybrid genetic algorithm for time-sensitive networking[C]// Proceedings of International Conference on Measurement,Modelling and Evaluation of Computing Systems. Cham:Springer, 2020: 99-117.
[17]	曹志鹏, 刘勤让, 刘冬培 ,等. 面向时间敏感网络的流量调度方法[J]. 计算机工程, 2021,47(7): 168-175,182.
	CAO Z P , LIU Q R , LIU D P ,et al. Traffic scheduling method for time-sensitive network[J]. Computer Engineering, 2021,47(7): 168-175,182.
[18]	JIA H Z , NEE A Y C , FUH J Y H ,et al. A modified genetic algorithm for distributed scheduling problems[J]. Journal of Intelligent Manufacturing, 2003,14(3): 351-362.
[19]	WANG Y , CHEN J D , NING W ,et al. A time-sensitive network scheduling algorithm based on improved ant colony optimization[J]. Alexandria Engineering Journal, 2021,60(1): 107-114.
[20]	GAVRILU? V , ZHAO L X , RAAGAARD M L ,et al. AVB-aware routing and scheduling of time-triggered traffic for TSN[J]. IEEE Access, 2018,6: 75229-75243.
[21]	GAVRILU? V , POP P . Scheduling in time sensitive networks (TSN) for mixed-criticality industrial applications[C]// Proceedings of the 2018 14th IEEE International Workshop on Factory Communication Systems (WFCS). Piscataway:IEEE Press, 2018: 1-4.
[22]	YEN J Y . Finding the K shortest loopless paths in a network[J]. Management Science, 1971,17(11): 712-716.
[23]	FEO T A , RESENDE M G C . Greedy randomized adaptive search procedures[J]. Journal of Global Optimization, 1995,6(2): 109-133.
[24]	曹旭, 周学哲, 宋亚平 ,等. 基于时延抖动与信道使用量约束的供热网络无线 TSN 流量调度算法[J]. 移动通信, 2023,47(8): 28-32,45.
	CAO X , ZHOU X Z , SONG Y P ,et al. A traffic scheduling algorithm for wireless TSN in heating networks based on delay jitter and channel usage constraints[J]. Mobile Communications, 2023,47(8): 28-32,45.
[25]	BERISA A , ZHAO L X , CRACIUNAS S S ,et al. AVB-aware routing and scheduling for critical traffic in time-sensitive networks with preemption[C]// Proceedings of the 30th International Conference on Real-Time Networks and Systems. New York:ACM Press, 2022: 207-218.
[26]	SERNA OLIVER R , CRACIUNAS S S , STEINER W . IEEE 802.1Qbv gate control list synthesis using array theory encoding[C]// Proceedings of the 2018 IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS). Piscataway:IEEE Press, 2018: 13-24.
[27]	CRACIUNAS S S , OLIVER R S . Combined task- and network-level scheduling for distributed time-triggered systems[J]. Real-Time Systems, 2016,52(2): 161-200.

拓扑编号	拓扑结构	交换节点数	终端节点数	流数量
1	星形	1	4	{80,160,240}
2	星形	1	6	{100,200,300}
3	线型	2	6	{100,200,300}

流数量	客户端	服务端
流数量	客户端	node_1	node_2	node_3	node_4	node_5	node_6
100	node_1	0	3	3	3	4	3
	node_2	5	0	3	3	3	3
	node_3	3	4	0	3	4	3
	node_4	4	3	3	0	3	3
	node_5	3	4	3	3	0	3
	node_6	3	4	4	3	4	0
200	node_1	0	6	7	6	6	7
	node_2	7	0	7	7	7	6
	node_3	7	7	0	6	6	6
	node_4	7	6	7	0	6	7
	node_5	7	7	7	7	0	7
	node_6	6	7	7	7	7	0
300	node_1	0	10	10	10	11	10
	node_2	10	0	11	10	10	10
	node_3	10	10	0	10	9	10
	node_4	11	11	10	0	10	10
	node_5	10	8	10	10	0	10
	node_6	10	9	10	10	10	0

时间敏感网络中基于EDWF-MTTF的启发式调度算法

EDWF-MTTF-based heuristic scheduling algorithm in time-sensitive networks

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 14

参考文献 27

相关文章 11

Metrics

推荐阅读 0

[1]	彭紫梅, 寿国础, 郭梦杰, 刘雅琼, 胡怡红. 时间敏感网络中的冗余机制研究综述[J]. 电信科学, 2023, 39(8): 29-42.
[2]	王雪荣, 唐政治, 李银川, 齐美玉, 朱建波, 张亮. 基于优化决策树的时延敏感流智能感知调度[J]. 电信科学, 2023, 39(4): 120-132.
[3]	伏玉笋, 唐金辉. 使能未来工厂的5G能力综述[J]. 电信科学, 2022, 38(9): 18-35.
[4]	李世宗, 陈智海, 颜永明. 阶梯面积算法在IDC流量计费中的应用研究[J]. 电信科学, 2022, 38(7): 126-137.
[5]	信金灿, 许森, 张化, 熊尚坤, 许话. 面向时间敏感网络的5G无线网增强技术研究[J]. 电信科学, 2022, 38(5): 18-25.
[6]	许方敏,伍丽娇,杨帆,赵成林. 时间敏感网络（TSN）及无线TSN技术[J]. 电信科学, 2020, 36(8): 81-91.
[7]	朱瑾瑜,段世惠,张恒升,于学涛. 时间敏感网络技术在工业互联网领域应用必要性分析[J]. 电信科学, 2020, 36(5): 115-124.
[8]	丛培壮, 田野, 龚向阳, 阙喜戎, 王文东. 时间敏感网络的关键协议及应用场景综述[J]. 电信科学, 2019, 35(10): 31-42.
[9]	吕华辉,林志达,黄宏聪. 业务优先级感知的网络流量调度机制[J]. 电信科学, 2017, 33(7): 151-158.
[10]	罗雨佳,欧亮,莫志威,唐宏. 基于BGP增强的流量调度技术[J]. 电信科学, 2016, 32(3): 20-27.
[11]	卢研平,吕光宏. 双归属环形网络拓扑规划算法设计[J]. 电信科学, 2012, 28(8): 69-74.