面向车载时间敏感网络的时间感知最大匹配流量调度算法

郑凌; 魏国栋; 潘伟涛; 张科遥; 褚宏云

doi:10.11959/j.issn.2096-3750.2025.00431

您当前的位置：

首页 >

文章列表页 >

面向车载时间敏感网络的时间感知最大匹配流量调度算法

理论与技术 | 更新时间：2026-01-26

- 面向车载时间敏感网络的时间感知最大匹配流量调度算法
- Time-aware traffic scheduling algorithm based on maximum matching for in-vehicle time-sensitive networks
- 物联网学报 2025年9卷第3期页码：48-59
- 作者机构：
  
  1.西安邮电大学通信与信息工程学院，陕西西安 710061
  2.西安电子科技大学空天地一体化综合业务网全国重点实验室，陕西西安 710071
- 作者简介：
  
  [ "郑凌（1989‒ ），男，博士，西安邮电大学通信与信息工程学院讲师，西安电子科技大学空天地一体化综合业务网全国重点实验室博士后，主要研究方向为确定性网络、高性能路由交换、光计算赋能的智能信息处理、基于FPGA的人工智能算法硬件加速。" ]
  [ "魏国栋（2000‒ ），男，西安邮电大学通信与信息工程学院硕士生，主要研究方向为时间敏感网络、高性能交换。" ]
  [ "潘伟涛（1981‒ ），男，博士，西安电子科技大学空天地一体化综合业务网全国重点实验室副教授，主要研究方向为与高速可编程网络相关的FPGA及芯片实现、网络协议卸载加速、RDMA网卡、星载路由器、星载数字透明处理器、时间触发以太网/TSN FPGA及芯片实现。" ]
  [ "张科遥（2000‒ ），男，西安邮电大学通信与信息工程学院硕士生，主要研究方向为时间敏感网络、高性能交换。" ]
  [ "褚宏云（1984‒ ），女，博士，西安邮电大学通信与信息工程学院讲师，主要研究方向为无线通信系统、电磁信号处理、图像信号处理。" ]
- 基金信息：
  
  国家自然科学基金资助项目(62102314);陕西省自然科学基础研究计划项目(2021JQ-708;2022JQ-635)
- DOI：10.11959/j.issn.2096-3750.2025.00431
  中图分类号： TN915.08
- 收稿：2024-08-22，
  
  修回：2025-04-30，
  
  纸质出版：2025-09-10
- 稿件说明：
移动端阅览
郑凌,魏国栋,潘伟涛等.面向车载时间敏感网络的时间感知最大匹配流量调度算法[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 .

浏览量

121

下载量

CSCD

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

提交

工具集

关联资源

一种应用于大规模时间敏感网络的混合流量调度机制

一种结合入队整形的TSN流量调度算法