Time-aware traffic scheduling algorithm based on maximum matching for in-vehicle time-sensitive networks

ZHENG Ling; WEI Guodong; PAN Weitao; ZHANG Keyao; CHU Hongyun

doi:10.11959/j.issn.2096-3750.2025.00431

您当前的位置：

首页 >

文章列表页 >

Time-aware traffic scheduling algorithm based on maximum matching for in-vehicle time-sensitive networks

Theory and Technology | 更新时间：2026-01-26

- Time-aware traffic scheduling algorithm based on maximum matching for in-vehicle time-sensitive networks
- Chinese Journal on Internet of Things Vol. 9, Issue 3, Pages: 48-59(2025)
- 作者机构：
  
  1.西安邮电大学通信与信息工程学院，陕西西安 710061
  2.西安电子科技大学空天地一体化综合业务网全国重点实验室，陕西西安 710071
- 作者简介：
- 基金信息：
  
  The National Natural Science Foundation of China(62102314);Natural Science Basic Research Program of Shaanxi Province(2021JQ-708;2022JQ-635)
- DOI：10.11959/j.issn.2096-3750.2025.00431
  CLC： TN915.08
- Received：22 August 2024，
  
  Revised：2025-04-30，
  
  Published：10 September 2025
- 稿件说明：
移动端阅览
郑凌,魏国栋,潘伟涛等.面向车载时间敏感网络的时间感知最大匹配流量调度算法[J].物联网学报,2025,09(03):48-59.

ZHENG Ling,WEI Guodong,PAN Weitao,et al.Time-aware traffic scheduling algorithm based on maximum matching for in-vehicle time-sensitive networks[J].Chinese Journal on Internet of Things,2025,09(03):48-59.
郑凌,魏国栋,潘伟涛等.面向车载时间敏感网络的时间感知最大匹配流量调度算法[J].物联网学报,2025,09(03):48-59. DOI： 10.11959/j.issn.2096-3750.2025.00431.

ZHENG Ling,WEI Guodong,PAN Weitao,et al.Time-aware traffic scheduling algorithm based on maximum matching for in-vehicle time-sensitive networks[J].Chinese Journal on Internet of Things,2025,09(03):48-59. DOI： 10.11959/j.issn.2096-3750.2025.00431.

摘要

随着车联网技术的逐步应用，对车内网络数据传输的实时性、确定性及可靠性提出了更高的要求。针对车载网络中数据转发不及时、分组传输时延大、调度算法复杂度高等问题，提出了一种时间感知的最大匹配流量调度算法。该算法将输入排队的调度问题转化为具有截止期保障的最大流匹配的问题，并逐时隙实现最大权重匹配调度。在调度集合中含有两种或多种截止期的调度任务中，充分利用空闲链路和空闲时隙资源，预推送截止期较大的分组。该算法有效地提高了交换系统的吞吐率，降低了分组的平均时延。仿真结果表明，所提算法相较于传统调度算法吞吐率性能提升了5%~15%、分组平均时延性能提升了15%~46%。

Abstract

With the application of the Internet of vehicles

the real-time

deterministic

and reliable data transmission for the in-vehicle networks become crucial. In response to the issues of untimely data forwarding

high packet transmission delay

and high complexity of scheduling algorithms in-vehicle time-sensitive networks

a time-aware traffic scheduling algorithm based on maximum matching was proposed. This algorithm transformed the input queuing scheduling problem into a maximum flow matching problem with deadline guarantees and achieved maximum weight matching scheduling on a per-slot basis. In scheduling sets containing tasks with two or more deadlines

idle link and slot resources were fully utilized to pre-push packets with larger deadlines. This effectively improved the throughput of the switching system and reduced the average packet delay. Simulation results demonstrate that compared with traditional scheduling algorithms

the proposed algorithm achieves 5%~15% throughput performance improvement and 15%~46% average packet delay performance improvement.

关键词

Keywords

references

李宗辉 , 杨思琪 , 喻敬海 , 等 . 时间敏感网络中确定性传输技术综述 [J ] . 软件学报 , 2022 , 33 ( 11 ): 4334 - 4355 .

LI Z H , YANG S Q , YU J H , et al . State-of-the-art survey on deterministic transmission technologies in time-sensitive networking [J ] . Journal of Software , 2022 , 33 ( 11 ): 4334 - 4355 .

HUANG C J , CHENG H-W , LIEN Y H , et al . A survey on video streaming for next-generation vehicular networks [J ] . Electronics , 2024 , 13 ( 3 ): 649 .

PRAKASH J , MURALI L , MANIKANDAN N , et al . A vehicular network based intelligent transport system for smart cities using machine learning algorithms [J ] . Scientific Reports , 2024 , 14 ( 1 ): 468 .

KIM H J , CHOI M H , KIM M H , et al . Development of an Ethernet-based heuristic time-sensitive networking scheduling algorithm for real-time in-vehicle data transmission [J ] . Electronics , 2021 , 10 ( 2 ): 157 .

FANG Z W , LIANG J H , TAN C P , et al . Enhancing robust driver assistance control in distributed drive electric vehicles through integrated AFS and DYC technology [J ] . IEEE Transactions on Intelligent Vehicles , 2024 , PP( 99 ): 1 - 14 .

LIANG M F , SU J C , SCHULTER S , et al . AIDE: an automatic data engine for object detection in autonomous driving [C ] // Proceedings of the 2024 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR) . Piscataway : IEEE Press , 2024 : 14695 - 14706 .

FENG Z W , CAI M Y , DENG Q X . An efficient pro-active fault-tolerance scheduling of IEEE 802.1Qbv time-sensitive network [J ] . IEEE Internet of Things Journal , 2022 , 9 ( 16 ): 14501 - 14510 .

SUN W J , ZOU Y , ZHANG X D , et al . Optimization design framework for in-vehicle time-sensitive networking architecture [J ] . IEEE Internet of Things Journal , 2024 , 11 ( 16 ): 27840 - 27853 .

DENG L B , XIAO X R , LIU H , et al . A low-delay AVB flow scheduling method occupying the guard band in time-sensitive networking [J ] . Journal of Systems Architecture , 2022 , 129 : 102586 .

PATTI G , BELLO L L , LEONARDI L . Deadline-aware online scheduling of TSN flows for automotive applications [J ] . IEEE Transactions on Industrial Informatics , 2023 , 19 ( 4 ): 5774 - 5784 .

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 .

CHANG C S , CHEN W J , HUANG H Y . Birkhoff-von Neumann input buffered crossbar switches [C ] // Proceedings of the Proceedings IEEE INFOCOM 2000 . Conference on Computer Communications. Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies . Piscataway : IEEE Press , 2000 : 1614 - 1623 .

ZHANG B X , WAN X L , LUO J Z , et al . A nearly optimal packet scheduling algorithm for input queued switches with deadline guarantees [J ] . IEEE Transactions on Computers , 2015 , 64 ( 6 ): 1548 - 1563 .

ATAR R , SHADMI Y . Fluid limits for earliest-deadline-first networks [J ] . Stochastic Processes and Their Applications , 2023 , 157 : 279 - 307 .

ZHANG Y W , MA J P , ZHENG H , et al . Criticality-aware EDF scheduling for constrained-deadline imprecise mixed-criticality systems [J ] . IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems , 2024 , 43 ( 2 ): 480 - 491 .

CHETTO M , EL OSTA R . Earliest deadline first scheduling for real-time computing in sustainable sensors [J ] . Sustainability , 2023 , 15 ( 5 ): 3972 .

CHEN N J , KURNIAWAN C , NAKAHIRA Y , et al . Smoothed least-laxity-first algorithm for electric vehicle charging: online decision and performance analysis with resource augmentation [J ] . IEEE Transactions on Smart Grid , 2022 , 13 ( 3 ): 2209 - 2217 .

林晚晴 , 李峭 , 赵露茜 , 等 . 基于Crossbar的混合关键性流量调度算法 [J ] . 电光与控制 , 2016 , 23 ( 7 ): 6 .

LIN W Q , LI Q , ZHAO L X , et al . Mixed-criticality flows scheduling algorithm for crossbar switches [J ] . Electronics Optics & Control , 2016 , 23 ( 7 ): 6 .

吴俊 , 李斌 . 输入队列交换机中嵌套周期流优化调度问题的复杂性分析 [J ] . 计算机学报 , 2010 , 33 ( 1 ): 55 - 62 .

WU J , LI B . On the complexity of optimal scheduling multi-rate nested periodic traffic in an input-queued switch [J ] . Chinese Journal of Computers , 2010 , 33 ( 1 ): 55 - 62 .

MAJIDI S , OBERMAISSER R . Genetic algorithm for scheduling communication networks in time-triggered systems-of-systems [C ] // Proceedings of the 2021 IEEE International Symposium on Software Reliability Engineering Workshops (ISSREW) . Piscataway : IEEE Press , 2021 : 121 - 128 .

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 .

LEE Y , LOU J Y , LUO J Z , et al . An efficient packet scheduling algorithm with deadline guarantees for input-queued switches [J ] . IEEE/ACM Transactions on Networking , 2007 , 15 ( 1 ): 212 - 225 .

ASSADI S . A simple (1: ε )-approximation semi-streaming algorithm for maximum (weighted) matching [M ] // 2024 Symposium on Simplicity in Algorithms (SOSA) . Philadelphia, PA : Society for Industrial and Applied Mathematics , 2024 : 337 - 354 .

WEN Y , ZHANG X D , ZOU Y , et al . Modeling and traffic scheduling problems for in-vehicle time-sensitive network communication architectures [C ] // Proceedings of the 2023 8th International Conference on Intelligent Computing and Signal Processing (ICSP) . Piscataway : IEEE Press , 2023 : 1905 - 1908 .

GUO Y , LUO F , WANG Z T , et al . Research on automated testing of in-vehicle time-sensitive network time synchronization mechanism [J ] . SAE International Journal of Connected and Automated Vehicles , 2024 , 7 ( 4 ): 12-7- 04 - 0027 .

YOSHIMURA A , ITO Y . QoS evaluation of ATS in IEEE 802.1TSN on in-vehicle Ethernet by comparing with CBS and TAS [J ] . IEICE Communications Express , 2024 , 13 ( 9 ): 355 - 358 .

GONZALEZ MARIÑO A , FONS F , MORENO AROSTEGUI J M . Vehicular network processor design for scalability & automation: Elastic Gateway SoC concept & builder [J ] . Journal of Systems Architecture , 2024 , 146 : 103038 .

GALILEA TORRES-MACÍAS A , SEGARRA FLOR J , LUIS BRIZ VELASCO J , et al . Fast IEEE802.1Qbv gate scheduling through integer linear programming [J ] . IEEE Access , 2024 , 12 : 111239 - 111250 .

WU G , GAN X . MatchBG: a boundary subgraph-based maximal matching algorithm for bipartite graphs [C ] // Proceedings of the International Conference on Database Systems for Advanced Applications . Singapore : Springer Nature Singapore , 2024 : 463 - 473 .

WEI Q , LIU M , LIANG Z , et al . A performance simulation and verification method of packet scheduling algorithms for data stream based on QoS [J ] . Evolutionary Intelligence , 2020 : 1 - 6 .

Views

121

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

A hybrid traffic scheduling mechanism applied to large scale time-sensitive networking

A TSN traffic scheduling algorithm combined with enqueue shaping

Related Author

Yanjue LI

Wenxuan HAN

Hailong ZHU

Changchuan YIN

Xinxin HE

Related Institution

Beijing Laboratory of Advanced Information Networks, Beijing University of Posts and Telecommunications

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

⁰