汽车技术

时间敏感网络中时间触发流冗余路由与调度研究^*

PDF下载

钟旭 , 朱元 , 陆科

汽车技术 | 车联网通信性能优化与安全技术专题 2024,(10): 38-42

收起

汽车技术 | 车联网通信性能优化与安全技术专题 2024, (10): 38-42

时间敏感网络中时间触发流冗余路由与调度研究^*

全屏

钟旭, 朱元, 陆科

作者信息

同济大学，上海 201804

Flow Attribute-Aware Redundant Routing and Scheduling for Time-Triggered Flows in Time-Sensitive Networking

Xu Zhong, Yuan Zhu, Ke Lu

Affiliations

Tongji University, Shanghai 201804

出版时间: 2024-10-24 doi: 10.19620/j.cnki.1000-3703.20240638

文章导航

摘要

收起

针对所有传输流量采用最短路径时，网络可调度性降低的问题，提出了一种针对时间触发流的流属性感知评估函数和冗余路由调度方法。该方法通过启发式算法求解评估函数最大的路由方案，利用整数线性规划求解调度。仿真验证结果表明：在面向区域的电子电气架构网络拓扑中，相较于K最短路径（KSP）、冲突程度（DoC）路由方案，所提出的方案在保证网络可靠性的同时，调度成功率分别提升了38.9%和14%，进一步验证了该方法的有效性。

关键词

车载以太网 / 时间敏感网络 / 路由调度 / 冗余

Abstract

收起

To address the issue of reduced network schedulability when the shortest path is adopted for all transmission traffic, a flow attribute-aware evaluation function and redundant routing scheduling method for time-triggered flows are proposed. The heuristic algorithm is used to solve the routing scheme with the largest evaluation function, and the integer linear programming is used to solve the scheduling. The simulation experiment results demonstrate that, in the region-oriented electronic and electrical architecture network topology, compared with the K Shortest Path (KSP) and Degree of Conflict (DoC) routing schemes, the proposed scheme enhances the success rate of scheduling by 38.9% and 14% respectively while guaranteeing network reliability, and further validates the effectiveness of this method.

Key words

In-vehicle ethernet / Time-Sensitive Networking (TSN) / Routing and scheduling / Redundant

引用本文

钟旭, 朱元, 陆科. 时间敏感网络中时间触发流冗余路由与调度研究^*. 汽车技术, 2024 , (10) : 38 -42 . DOI: 10.19620/j.cnki.1000-3703.20240638

Xu Zhong, Yuan Zhu, Ke Lu. Flow Attribute-Aware Redundant Routing and Scheduling for Time-Triggered Flows in Time-Sensitive Networking[J]. Automobile Technology, 2024 , (10) : 38 -42 . DOI: 10.19620/j.cnki.1000-3703.20240638

正文

收起

1 前言

收起

随着高级驾驶辅助系统、自适应前照灯系统等的广泛应用，以太网以其高带宽被引入车载网络，然而传统以太网采用尽力而为的传输机制，无法保证传输服务质量（Quality of Service，QoS）^[1]。因此，时间敏感网络（Time-Sensitive Networking，TSN）作为传统以太网的补充与增强，对车载以太网的确定性传输具有重要意义。

时间敏感网络的4个关键领域为时间同步、端到端有界延迟、高可靠性及网络管理^[2]。TSN的通信流量依据QoS可分为3种类型，分别为时间触发流（Time-Triggered，TT）、音频视频流（Audio Video Bridging，AVB）和尽力而为流（Best Effort，BE）^[3-4]。其中，针对TT流和AVB流，TSN规定了不同的流量调度整形器以保证QoS。

IEEE 802.1 Qca推荐采用最短路径作为路由方案，但过多流在同一路径传输，增加了网络拥塞的可能性，降低了可调度性^[5]。IEEE 802.1 CB规定了一种帧复制与消除机制（Frame Replication and Elimination for Reliability，FRER），该机制采用多条不相交路径传输同一份报文，实现了空间冗余与可靠性，但会导致网络流量倍增。Huang等^[6-7]提出了在路由阶段最小化冲突程度（Degree of Conflict，DoC），保证TT流可靠性的同时，提高了可调度性，但未考虑时间触发流周期和截止时间对可调度性的深层影响。

为解决上述问题，本文提出了一种针对TT流的流属性感知冗余路由（Flow Attribute-Aware Redundant Routing，FAARR）方法，保证TT流可靠性的同时，提高可调度性。

2 数学建模

收起

2.1 车载以太网建模

传统分布式汽车电子电气架构（Electrical/Electronic Architecture，EEA）存在超过100个电子控制单元（Electronic Control Unit，ECU），需执行超过1.5×10⁸行代码，其网络负载成本与软件复杂度极高^[8]。为了解决分布式架构的局限性，汽车的EEA逐步向区域集中式发展^[9]。

本文基于面向区域的EEA架构，搭建具有冗余连接的网络模型，如图1所示。网络拓扑建模使用有向图G=(V,E)，其中：V=ES∪SW为网络中所有节点的集合；E为网络中所有链路的集合；SW为网络中所有TSN交换机的集合；ES为网络中所有终端系统的集合，包括ECU、摄像头、雷达等。

以区域控制单元（Zone Control Unit，ZCU）和中央计算单元（Central Control Unit，CCU）中的TSN交换机建模，所有的物理连接均为以太网全双工连接。(v_i,v_j)∈E，v_i、v_j分别为发送节点、接收节点，其中，v_i、v_j∈V。如图1b中，路径p从发送节点

v b ∈ V

到接收节点

v d ∈ V

的有序序列，流s₁的一条冗余路径为

p s 2 1

=[ES1,SW1,SW3,ZCU3]。

2.2 时间触发信息流建模

时间触发信息流为一系列周期性流量，每条时间触发流s的属性可用七元组来描述：

（1）

s ≡ (v b, v d, T, D s z, T e, R l, C)

式中：v_b为发送节点，v_d为接收节点，T为周期，D_sz为帧数据大小，T_e为截止时间，R_l为冗余等级，C为优先级。

2.3 冗余路径建模

基于FRER机制计算冗余路径候选集，不相交路径为：

（2）

u s = {p s 1 … p s R l | ∀ 1 ≤ m, n ≤ R l, m ≠ n, E s m ⋂ E s n = {[v b, v f i r s t], [v l a s t, v d]}}

式中：u_s为流s的一条不相交路径，

E s i

为路径

p s i

包含的所有链路的集合，v_first、v_last分别为路径p_s经过的第一个和最后一个TSN交换机。

因此，最终的单播冗余路径候选集（Unicast Redundant Path Candidate Set，URPCS）为S_URPCS=

{u s 1 … u s t}

，该候选集所包含的不相交路径的数量取决于网路拓扑和用户需求。

3 流属性感知的冗余路由方法

收起

本文基于K最短路径（K Shortest Path，KSP）算法计算冗余路径候选集，用于减少后续启发式算法的搜索空间。为提升路由方案的可调度性，定量分析流属性感知的评估函数，并基于具有精英策略的遗传算法最大化评估函数得到最终冗余路由方案。

3.1 冗余路径候选集计算

单播冗余路径候选集算法如图2所示，使用KSP算法^[10]计算发送节点v_b至接收节点v_d的k条路径，再根据冗余等级计算k条最短路径的所有组合，将组合中满足单播不相交路径的组合添加至结果中。鉴于不相交路径差会影响流调度^[11]，因此，在筛选路径组合时，将不相交路径的最大路径差作为筛选条件，本文中最大路径差为2。

3.2 流属性感知的评估函数构建

当多个流在共享链路传输中发送冲突，冲突程度可表示为^[6]：

（3）

n D o C = E s 1 ⋂ E s 2 ∙ D s z 1 ∙ D s z 2 T 1 ∙ T 2

式中：E_s为路径p_s包含的所有链路的集合。

由于DoC未考虑流的截止时间，且未定量分析帧数据和周期对流调度的影响。为弥补上述不足，可将两条流在共享链路传输时发生冲突的概率定义为：假设流s₁在共享链路上传输，且0时刻传输第1帧，流s₂经过该共享链路并与流s₁发生冲突时，流s₂的第1帧传输时间范围与满足流s₂截止时间的第1帧传输时间范围的比值。

假设流s₁的第x帧与流s₂的第y帧在某条共享链路上发生冲突，如图3所示。其中：流s₁的周期为T₁，帧数据大小为D_sz1，截止时间为T_e1；流s₂的周期为T₂，帧数据大小为D_sz2，截止时间为T_e2。

发生冲突时，流s₂第1帧的发送时间范围为：

（4）

T c o n f = t t + y ∙ T 2 x ∙ T 1 - D s z 2 w t + y ∙ T 2 x ∙ T 1 + D s z 1 w = t t x ∙ T 1 - y ∙ T 2 - D s z 2 w t x ∙ T 1 - y ∙ T 2 + D s z 1 w

式中：t为流s₂第1帧发送时间，w为链路带宽。

假设T₁和T₂的最大公约数为d，即：

（5）

g c d T 1, T 2 = d T 1 = d ∙ a, T 2 = d ∙ b, g c d a, b = 1

将式（5）代入式（4）中，得到：

（6）

T c o n f = t t (a x - b y) d - D s z 2 w t (a x - b y) d + D s z 1 w

因此，可通过ax-by确定发生冲突的时间范围。由于式（5）中gcd(a,b)=1，根据裴蜀定理，ax-by可取任意整数。为了满足流s₂的截止时间要求，即第1帧必须在截止时间前到达目的地，第1帧发送时间t的范围为：

（7）

T a l l = t | t ∈ [0, T e 2 - D s z 2 w]

向上取整，

k = (T e 2 - D s z 2 w) / d

，则式（6）与式（7）存在交集的取值范围为

T c o n f' = ∪ a x - b y = - 1 a x - b y = k T c o n f

。在共享链路中，当流s₁存在时，流s₂加入时发生冲突的概率为

p (s 2 | s 1) c o n f = T c o n f' ⋂ T a l l T a l l

，所以周期的最大公约数、流截止时间和帧数据为影响流冲突概率的关键因素。

为了消除流顺序的影响，考虑流s₁与s₂在路径上的所有共享链路，定义两条流在所有共享链路上不发生冲突的评估函数为：

（8）

f s c h e d s 1, s 2 = (1 - p s 2 | s 1 c o n f + p s 1 | s 2 c o n f 2) / E s 1 ⋂ E s 2

因此，n条流的流属性感知的评估函数为：

（9）

F = ∑ i ≠ j f s c h e d s i, s j

公式的时间复杂度为O(n²)，为了提升路由方案的可调度性，应该最大化F。

3.3 基于遗传算法的流属性感知的冗余路由方法

从冗余路径候选集中筛选评估函数F最大的路由方案，可视为组合优化问题。遗传算法（Genetic Algorithm，GA）^[12]是模拟生物逻辑进化的随机搜索技术，具有较强的全局搜索能力。因此，本文采用具备精英选择策略的遗传算法求解最大评估函数的路由方案，算法流程如图4所示。

遗传算法主要包含基因编码、选择算子、交叉算子、变异算子和保留精英操作。假设存在n条流，则一个染色体包含n个基因，各基因为该流冗余路径候选集选取的下标，最小值为1，最大值为该流冗余路径候选集的数量。例如，编码15表示两条流，其中一条流选择候选集中第1个冗余路由方案，则另一条流选择候选集中第5个冗余路由方案。本文采用轮盘赌选择算子、均匀交叉及以搜索域为中心的均匀变异，个体适应度（即评估函数）越大，被选中的概率越大。

4 基于整数线性规划的无等待调度

收起

IEEE 802.1 Qbv协议的时间感知整形器（Time Aware Shaper，TAS）通过门控列表（Gate Control List，GCL）保证网络确定性低延迟，其机制如图5所示。

各TSN交换机输出端口均配置了GCL，列表中每一行表示一次操作，每一列表示对应门在该时刻的状态，且该状态持续到下一次操作。只有门处于打开状态时，关联的队列数据才能被传输。若同一时刻多个门处于打开状态，将根据传输选择算法决定流量传输。

为了验证FAARR的有效性，本文提出基于整数线性规划（Integer Linear Programming，ILP）的无等待调度方法。TAS通过循环执行GCL，对流量进行调度。其中，循环周期为超周期P，即所有流量周期的最小公倍数：

（10）

N s = P T s, P = l c m T 1, T 2, …, T n

式中：N_s为流s在一个超周期内传输的帧数量。

流量调度是在一个超周期内为所有流量的每一帧合理分配传输时间，使其满足所有网络约束和流量约束。为了便于建模，定义传输偏移变量为：

（11）

X s i, j = t ， s ∈ S

式中：X_s(i, j)为流s的第i帧、第j条链路，S为待调度流量集合。

因此，流量调度问题可理解为：已知网络拓扑G、待调度流量集合S、路由方案R，求解满足相关约束，同时目标函数取最值的所有流量的X_s(i, j)。

4.1 时延约束

时延约束需保证每条TT流均能够在截止时间之前到达目的地。由于流具有周期性，所以仅需保证第一帧在截止时间之前到达，后续帧发送时间为前一帧发送时间加上一个周期：

（12）

∀ s ∈ S, ∀ e j ∈ E s, ∀ i ∈ 2,3 … N s X s 1, j ∈ 0, T e s - D s z s w X s i, j = X s i - 1, j + T s

式中：e_j为流s经过的第j条链路。

4.2 无等待约束

GCL控制所有队列状态（打开或关闭）的时间，当门关闭时，队列中可能存在待传输流量。

无等待调度是指交换机在接收到数据后立刻转发，从而减少数据在队列中的等待时间，但实际操作中，交换机存在处理延迟T_d。由于流具有周期性，同理，仅需要对第1帧建立约束，则无等待约束为：

（13）

∀ s ∈ S, ∀ e j ∈ E s, j 1 X s 1, j - X s 1, j - 1 = T d

4.3 无冲突约束

当流具有共享链路时，同一时刻只能有一条流传输数据，否则会发生冲突。而对于具有共享链路的两条流s₁的第x帧和s₂的第y帧，需要满足以下约束，两者选择其一即可：

a.先发送流s₁的第g帧，后发送流s₂的第k帧。

b.先发送流s₂的第k帧，后发送流s₁的第g帧。

由于冗余链路为不相交链路，因此，需在具有共享链路的流之间建立无冲突约束：

（14）

∀ s m, s n ∈ S, ∀ e j ∈ E s m ⋂ E s n ∀ g ∈ 1,2 … N s m, ∀ k ∈ 1,2 … N s n X s m g, j + D s z s m w ≤ X s n k, j 或 X s n k, j + D s z s n w ≤ X s m g, j

式中：m为第m条流量，n为第n条流量。

4.4 目标函数

定义一个超周期内所有流中的最大延迟为：

（15）

∀ s ∈ S, T d m a x = m a x {X s N s, j l a s t + D s z s w}

式中：N_s为流s在超周期内的最后一帧，j_last为流s传输路径上的最后一条链路。

因此，ILP求解的目标函数为f_Object=minT_{d max}。

5 仿真试验

收起

本文试验网络拓扑基于面向区域的EEA模型，网络带宽为100 Mbit/s，GA的迭代次数为100次，ILP求解器使用Gurobi，仿真流程如图6所示。

比较KSP、DoC及FAARR路由方案对于不同流数量的调度成功次数，流数量分别为15条、20条、25条、30条和35条。根据文献[13]，周期在10 ms、20 ms、30 ms、40 ms、60 ms、80 ms、120 ms中随机选择，帧数据大小从10~20 KB中随机选择，发送节点和接收节点分别从ES、CCU、ZCU中随机选择，冗余等级设置为2。

若基于ILP求解时存在可行解，即所有流量均满足前文的调度约束，则调度成功。本文各方案调度次数为100次，试验结果如图7所示。

结果表明：随着流数量的增加，各方案的调度成功率均下降。传输相同流数量时，FAARR相较于KSP和DoC方案，成功率均有提升。15条流量时，由于流量较低，全部选择最短路径的冲突较少；流数量为25条时，FAARR调度成功率提升显著；流量增加至35条时，由于流量过高，每条链路发生冲突的概率增加，因而所有路由方案的调度成功率都很低，此时，应该增加网络拓扑连通度或网络带宽。

综上所述，本文提出的流属性感知的冗余路由方法在保证可靠性的同时，相较于KSP方案调度成功率平均提升了38.9%，相较于DoC方案平均提升了14%。目前，智能网联汽车一般配备4~11个摄像头，6~12个超声波雷达，1~3个毫米波雷达，0~1个激光雷达。流量数量在11至27条之间时，即使在高流量区间下，本文方案改善效果显著。

6 结束语

收起

本文提出了基于GA的流属性感知的冗余路由方法，并通过基于ILP的调度验证了其有效性。此外，本文主要关注离线路由与调度，对于算法运行时间要求不高，因此采用GA获得更好的全局最优性。未来，将以流属性感知的评估函数为指导，降低算法复杂度来实现TT流的在线增量路由与调度。

基金

收起

*南昌市汽车智能与新能源研究所前瞻技术研究(TPD-TC202211-07)

参考文献

收起

文献

收起

参考文献引证文献

排序方式：

[1]

COICHECI

, FILIP

. Self-Driving Vehicles:Current Status of Development and Technical Challenges to Overcome[C]// 2020 IEEE 14th International Symposium on Applied Computational Intelligence and Informatics (SACI). Timisoara, Romania: IEEE, 2020.

[2]

FARKAS

, BELLO

L L

, GUNTHER

. Time-Sensitive Networking Standards[J]. IEEE Communications Standards Magazine, 2018, 2(2): 20-21.

[3]

LAURSEN

S M

, POP

, STEINER

. Routing Optimization of AVB Streams in TSN Networks[J]. ACM SIGBED Review, 2016, 13(4): 43-48.

[4]

, YIN

Z Y

, MA

, et al. Heuristic Routing Algorithms for Time-Sensitive Networks in Smart Factories[J]. Sensors, 2022, 22(11): 4153.

[5]

OJEWALE

M A

, YOMSI

P M

. Routing Heuristics for Load-Balanced Transmission in TSN-Based Networks[J]. ACM SIGBED Review, 2020, 16(4): 20-25.

[6]

HUANG

, WAN

X M

, WANG

, et al. Reliability-Aware Multipath Routing of Time-Triggered Traffic in Time-Sensitive Networks[J]. Electronics, 2021, 10(2): 125.

[7]

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.

[8]

BANDUR

, SELIM

, PANTELIC

, et al. Making the Case for Centralized Automotive E/E Architectures[J]. IEEE Transactions on Vehicular Technology, 2021, 70(2): 1230-1245.

[9]

WANG

W W

, YU

S Y

, CAO

W K

, et al. Review of In-Vehicle Optical Fiber Communication Technology[J]. Automotive Innovation, 2022, 5(3): 272-284.

[10]

YEN

J Y

. An Algorithm for Finding Shortest Routes from All Source Nodes to A Given Destination in General Networks[J]. Quarterly of Applied Mathematics, 1970, 27(4): 526-530.

[11]

THOMAS

, MIFDAOUI

, LE

BOUDEC J Y

. Worst-Case Delay Bounds in Time-Sensitive Networks with Packet Replication and Elimination[J]. IEEE/ACM Transactions on Networking, 2022, 30(6): 2701-2715.

[12]

JOHN

H H

. Adaptation in Natural and Artificial Systems:An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence[M]. Cambridge: MIT Press, 1992.

[13]

邹渊, 孙文景, 张旭东, 等. 面向时间敏感网络的车载以太网网络架构多目标优化[J]. 汽车工程, 2023, 45(5): 746-758.

ZOU

, SUN

W J

, ZHANG

X D

, et al. Multi-Objective Optimization of In-Vehicle Ethernet Network Architecture for Time-Sensitive Network[J]. Automotive Engineering, 2023, 45(5): 746-758.

2024年第卷第10期

PDF下载

202

引用本文

BibTeX

文章信息

doi: 10.19620/j.cnki.1000-3703.20240638

首发时间：2025-12-22
出版时间：2024-10-24

补充材料

相关文章

文章信息

作者

出版历史

修回日期：2024-09-27

基金

*南昌市汽车智能与新能源研究所前瞻技术研究(TPD-TC202211-07)

作者信息

同济大学，上海 201804

参考文献

分享链接

https://castjournals.cast.org.cn/joweb/qcjs/CN/10.19620/j.cnki.1000-3703.20240638

分享至

全文二维码

扫描看全文

引用本文

BibTeX

本文的引用情况

2种不同金属材料的力学参数

科 Family	属数 Number of genus	种数 Number of species	占总种数比例 Percentage of total species (%)	属 Genus	种数 Number of species	占总种数比例 Percentage of total species (%)
鹅膏菌科Amanitaceae	2	11	5.26	鹅膏菌属 Amanita	10	4.78
小菇科 Mycenaceae	2	12	5.74	丝盖伞属 Inocybe	5	2.39
多孔菌科 Polyporaceae	8	14	6.70	蜡蘑属 Laccaria	5	2.39
红菇科 Russulaceae	3	23	11.00	小皮伞属 Marasmius	6	2.87
				小菇属 Mycena	11	5.26
				光柄菇属 Pluteus	5	2.39
				红菇属 Russula	17	8.13
				栓菌属 Trametes	5	2.39

关闭全屏

BibTeX
EndNote
RefWorks
TxT