一种面向车载时间敏感网络的联合路由与时隙调度负载均衡算法

论文标题

中文标题：一种面向车载时间敏感网络的联合路由与时隙调度负载均衡算法
英文标题：A Joint Routing and Time-Slot Scheduling Load Balancing Algorithm for In-Vehicle TSN

作者信息

Bo Xu, Xinrui Chang, Dongyang Xu, Shuo Wang, Uzair Aslam Bhatti*, Hao Tang*

论文出处

本文发表于《IEEE Transactions on Consumer Electronics》，DOI: 10.1109/TCE.2025.3540890。本文为作者版本，尚未经过完整编辑，内容可能在最终出版前有所变化。

---

摘要

本文针对高级驾驶辅助系统（ADAS）中多种数据帧的实时传输挑战，提出了一种基于时间敏感网络（TSN）的车载以太网传输技术。现有的基于最短路径的路由算法常导致负载不平衡，而基于固定路径的时隙调度无法确保车联网络中多样化数据流的可靠传输。为此，本文提出了一种联合路由与时隙调度算法，通过扩展路径规划的可行空间，更好地平衡网络负载并优化时隙分配，从而提高网络传输的可靠性和稳定性。实验结果表明，与基于最短路径的时隙调度方案相比，所提算法能够有效实现网络链路负载均衡，并优化TSN的端到端延迟。此外，该算法通过与5G技术的结合，为未来的车联网和自动驾驶技术提供了精确的时序控制和高可靠的数据传输。

一、引言

随着智能车辆对性能、安全性和舒适性需求的增加，车辆内部的电子控制单元（ECU）数量急剧增加，传统CAN总线技术已无法满足未来智能网联车辆的需求。以太网技术因其高带宽、低成本和易于与互联网集成等优势，成为未来汽车总线技术的重要发展方向。然而，以太网采用尽力而为的传输方式，无法满足汽车网络中对实时性和可靠性的要求，例如ADAS或自动驾驶系统。为此，时间敏感网络（TSN）在以太网基础上引入了严格的时间同步和流量调度机制，旨在实现确定性传输。TSN通过路由规划和时隙分配有效分配网络资源，但经典的最短路径算法可能导致负载不平衡和潜在的故障点，从而引发网络拥塞。因此，本文提出了一种基于循环队列转发（CQF）的路由调度优化算法，以改善负载平衡和资源利用率。

二、相关理论

A. TSN基本理论

TSN是一种支持实时和非实时流量混合通信的网络技术，旨在实现不同优先级流量的共存。TSN协议定义了一套流量整形和调度标准，以提高网络的可靠性和效率。TSN通过优先级队列分离时间敏感流量，并通过路由规划或时隙分配进一步隔离时间敏感流量，从而实现低延迟传输。TSN采用时间分割复用方法，为每个数据流分配时隙以确保及时传输。时隙分配问题是NP-hard问题，需要识别合适的调度机制，并收集流量大小、延迟要求和网络拓扑信息以构建时隙分配模型。

B. 网络与数据流模型

TSN网络由终端系统、交换机和链路组成，通过有向图G(V, E)描述网络拓扑结构和数据流动态。终端系统负责生成或接收时间敏感数据流并将其传输到网络中；交换机负责路由和转发数据；链路则连接终端系统和交换机。本文关注时间触发（TT）流和音视频桥接（AVB）流，数据流模型用元组表示，包括源节点、目的节点、传输路径、传输偏移、传输周期、传输长度和截止时间等信息。

C. 问题描述

为了实现以太网上数据包的可预测和可靠传输，TSN采用门控、时间同步和流量调度机制来满足确定性实时通信的需求。流量调度机制处理数据流传输的路由和时隙分配，既要考虑空间上的路径规划，也要考虑时间上的时隙分配。然而，基于固定路径的时隙调度容易导致网络拥塞和冲突，无法解决车联网络中多种数据流的传输问题。因此，本文提出的问题是在ADAS网络拓扑结构下，如何通过有效的路由机制和时隙调度，确保数据流以最小延迟沿最优路径传输，从而提高数据传输的可靠性和稳定性。

三、提出的解决方案

为了应对上述问题，本文提出了一种面向车载TSN的联合路由与时隙规划负载均衡调度算法。首先，提出了一种基于K最短路径（KSP）的负载均衡路由算法（LB-KPR），通过设计考虑路径长度和负载的代价函数，选择最优传输路径。其次，提出了一种基于遗传算法的时隙分配算法，优化数据流的传输偏移和端到端延迟，以产生最终的调度结果。

A. 基于K最短路径的路由算法

为了提高网络的容错性和鲁棒性，本文使用K最短路径算法生成一组候选路径，然后通过代价函数评估这些路径，选择代价函数最小的路径作为最优路径。K最短路径算法通过迭代移除现有最短路径并应用偏移操作来获得新路径。代价函数结合路径长度和负载来评估路径质量，路径长度越短，传输时间越短，但仅考虑路径长度会导致负载不平衡。因此，本文引入负载作为路径性能的衡量指标，负载定义为路径上所有链路穿越的数据流总数。最终选择代价函数最小的路径作为最优传输路径。

B. 基于遗传算法的时隙分配算法

TSN网络流调度的本质是安排数据流的传输顺序，以确保它们有序、无冲突地传输，并满足实时性要求。本文使用遗传算法解决TSN时隙分配问题。遗传算法通过模拟自然选择过程，在大搜索空间中寻找最优解，平衡解的质量和计算效率。本文中，遗传算法的输入是通过KSP算法获得的候选路径集，输出是数据流的时隙分配方案。遗传算法通过选择、交叉和变异操作逐步优化时隙分配，最终选择最优个体作为最终的传输方案。

四、实验比较与分析

为了评估所提算法的性能，本文构建了多种典型的ADAS网络拓扑结构，通过改变数据流的数量调整网络负载，并设计了四个验证实验。实验1比较了SPR算法、LB-DDR算法、KSP算法和所提LB-KPR算法在不同负载场景下的性能，使用网络链路数据流分布的标准差（σx）作为负载均衡评估指标。实验2探索了随机最优路由算法与所提LB-KPR算法组合在不同负载条件下的性能。实验3分析了联合路由和时隙调度算法对数据流实时性能的影响。实验4扩展了实验3的设置，研究了不同调度算法的运行时间。

A. 实验场景设置

本文构建了基于ADAS的网络拓扑结构，包括16个节点（6个交换机、8个摄像头传感器、1个中央控制器和1个控制单元）。为了验证算法在不同网络拓扑结构下的适应性，还设计了20个节点和24个节点的扩展拓扑结构。

B. 负载性能实验

实验1和实验2分别比较了不同路由算法在不同负载场景下的负载性能。实验结果表明，所提LB-KPR算法在所有场景中均实现了最优的负载性能，标准差σx显著低于其他算法。此外，随着网络拓扑中节点数量的增加，算法的负载性能进一步改善，表明该算法能够有效避免复杂网络环境中的网络拥塞问题。

C. 实时性能实验

实验3分析了不同路由和时隙分配方案对数据流实时性能的影响。结果表明，所提LB-KPR+GA方案在端到端延迟方面优于其他方案，尽管其延迟略高于KSP+GA和LB-DDR+GA方案，但在实际应用中能够有效避免拥塞链路，降低丢包率，并确保传输的可靠性和稳定性。实验4进一步比较了不同算法的运行时间，结果表明，所提LB-KPR+GA方案的运行时间与SPR+GA、LB-DDR+GA和KSP+GA方案相当，表明该算法在优化网络负载平衡的同时，保持了较好的运行效率。

五、结论

本文提出了一种面向车载TSN的负载均衡调度算法，通过联合优化路由和时隙分配，有效解决了传统最短路径算法导致的链路负载不平衡问题。实验结果表明，所提算法在负载均衡和实时性能方面均优于现有方案，能够满足ADAS对复杂动态网络拓扑的要求。未来工作将探索增加流量类别对可调度性的影响，并基于模拟器和TSN交换机联合部署不同的车载网络拓扑结构，以进一步评估TSN协议的实际应用性能，推动TSN技术在车联网和自动驾驶领域的应用。