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

doi:10.11959/j.issn.1000-0801.2024009

您当前的位置：

首页 >

文章列表页 >

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

Research and Development | 更新时间：2024-06-05

- EDWF-MTTF-based heuristic scheduling algorithm in time-sensitive networks
- Telecommunications Science Vol. 40, Issue 2, Pages: 22-37(2024)
- 作者机构：
  
  1. 浙江工商大学信息与电子工程学院（萨塞克斯人工智能学院），浙江杭州 310018
  2. 之江实验室，浙江杭州 311121
- 作者简介：
- 基金信息：
  
  Zhejiang Key Laboratory of New Network Standards and Application Technology(2013E10012)
- DOI：10.11959/j.issn.1000-0801.2024009
  CLC： TP393
- Published Online：2024-02，
  
  Published：20 February 2024
- 稿件说明：
移动端阅览
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：

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 .

Views

173

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

User allocation technology for multi-dimensional resource optimization of LEO satellite

Delay-sensitive traffic intellisense scheduling based on optimal decision tree

Application of step area algorithm in IDC traffic billing

Analysis on the application necessity of time-sensitive network technology in the field of industrial interconnection

A survey of key protocol and application scenario of time-sensitive network

Related Author

PENG Mugen

ZHAO Yafei

ZHOU Jiaen

Zhengzhi TANG

Liang ZHANG

Jianbo ZHU

Xuerong WANG

Yinchuan LI

Related Institution

State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications

Research Institute of China Telecom Co., Ltd.

Beijing Huawei Digital Technologies Co., Ltd.

China Academy of Information and Communication Technology

Beijing HELPGO Electric Technology Co.,Ltd.

⁰