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

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

doi:10.11959/j.issn.1000-0801.2024009

您当前的位置：

首页 >

文章列表页 >

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

研究与开发 | 更新时间：2024-06-05

- 时间敏感网络中基于EDWF-MTTF的启发式调度算法
- EDWF-MTTF-based heuristic scheduling algorithm in time-sensitive networks
- 电信科学 2024年40卷第2期页码：22-37
- 作者机构：
  
  1. 浙江工商大学信息与电子工程学院（萨塞克斯人工智能学院），浙江杭州 310018
  2. 之江实验室，浙江杭州 311121
- 作者简介：
  
  [ "李传煌（1980- ），男，博士，浙江工商大学教授、硕士生导师，之江实验室双聘专家，主要研究方向为新一代网络技术、边缘计算、人工智能应用" ]
  [ "廖君虎（1998- ），男，浙江工商大学硕士生，主要研究方向为软件定义网络、移动网络优先等" ]
  [ "宣家栋（1998- ），男，硕士，浙江工商大学毕业生，主要研究方向为软件定义网络、时间敏感网络等" ]
  [ "徐琪（1992- ），男，博士，之江实验室副研究员，主要研究方向为多模态网络、软件定义网络、时间敏感网络等" ]
  [ "张慧峰（1992- ），女，博士，之江实验室助理研究员，主要研究方向为多模态网络、新型网络拓扑结构、时间敏感网络等" ]
  [ "朱俊（1981- ），男，博士，之江实验室高级工程师，主要研究方向为新型网络架构、软件定义网络、网络管理与控制技术、网络协议设计与优化、卫星网络等" ]
  [ "邹涛（1974- ），男，博士，之江实验室研究员，主要研究方向为多模态网络技术和新型网络体系架构" ]
  [ "张汝云（1973- ），男，博士，之江实验室研究员，主要研究方向为多模态网络技术、工业互联网和网络通信安全" ]
- 基金信息：
  
  国家自然科学基金资助项目;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);浙江省新型网络标准与应用技术重点实验室项目(2013E10012)
- DOI：10.11959/j.issn.1000-0801.2024009
  中图分类号： TP393
- 网络出版日期：2024-02，
  
  纸质出版日期：2024-02-20
- 稿件说明：
移动端阅览
李传煌, 廖君虎, 宣家栋, 等. 时间敏感网络中基于EDWF-MTTF的启发式调度算法[J]. 电信科学, 2024,40(2):22-37.

Chuanhuang LI, Junhu LIAO, Jiadong XUAN, et al. EDWF-MTTF-based heuristic scheduling algorithm in time-sensitive networks[J]. Telecommunications science, 2024, 40(2): 22-37.
李传煌, 廖君虎, 宣家栋, 等. 时间敏感网络中基于EDWF-MTTF的启发式调度算法[J]. 电信科学, 2024,40(2):22-37. DOI： 10.11959/j.issn.1000-0801.2024009.

Chuanhuang LI, Junhu LIAO, Jiadong XUAN, et al. EDWF-MTTF-based heuristic scheduling algorithm in time-sensitive networks[J]. Telecommunications science, 2024, 40(2): 22-37. DOI： 10.11959/j.issn.1000-0801.2024009.

摘要

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

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.

关键词

Keywords

references

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 .

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 .

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 .

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 .

CRACIUNAS S S , OLIVER R S , STEINER W . Formal scheduling constraints for time-sensitive networks [J ] . arXiv preprint , 2017 ,arXiv:1712.02246.

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 .

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 .

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 .

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 .

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 .

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 .

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 .

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 .

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 .

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 .

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 .

曹志鹏 , 刘勤让 , 刘冬培 , 等 . 面向时间敏感网络的流量调度方法 [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 .

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 .

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 .

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 .

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 .

YEN J Y . Finding the K shortest loopless paths in a network [J ] . Management Science , 1971 , 17 ( 11 ): 712 - 716 .

FEO T A , RESENDE M G C . Greedy randomized adaptive search procedures [J ] . Journal of Global Optimization , 1995 , 6 ( 2 ): 109 - 133 .

曹旭 , 周学哲 , 宋亚平 , 等 . 基于时延抖动与信道使用量约束的供热网络无线 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 .

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 .

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 .

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 .

浏览量

173

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

面向低轨卫星多维资源优化的用户分配技术

基于优化决策树的时延敏感流智能感知调度

阶梯面积算法在IDC流量计费中的应用研究

时间敏感网络技术在工业互联网领域应用必要性分析

时间敏感网络的关键协议及应用场景综述