【摘要】針對所有傳輸流量采用最短路徑時，網(wǎng)絡可調(diào)度性降低的問題，提出了一種針對時間觸發(fā)流的流屬性感知評估函數(shù)和冗余路由調(diào)度方法。該方法通過啟發(fā)式算法求解評估函數(shù)最大的路由方案，利用整數(shù)線性規(guī)劃求解調(diào)度。仿真驗證結(jié)果表明：在面向區(qū)域的電子電氣架構(gòu)網(wǎng)絡拓撲中，相較于K最短路徑（KSP）、沖突程度（DoC）路由方案，所提出的方案在保證網(wǎng)絡可靠性的同時，調(diào)度成功率分別提升了38.9%和14%，進一步驗證了該方法的有效性。

主題詞：車載以太網(wǎng) 時間敏感網(wǎng)絡 路由調(diào)度 冗余

中圖分類號：U463.6" "文獻標志碼：A" "DOI： 10.19620/j.cnki.1000-3703.20240638

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

Zhong Xu， Zhu Yuan， Lu Ke

（Tongji University， Shanghai 201804）

【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

【引用格式】 鐘旭， 朱元， 陸科. 時間敏感網(wǎng)絡中時間觸發(fā)流冗余路由與調(diào)度研究[J]. 汽車技術(shù)， 2024（10）： 38-42.

ZHONG X， ZHU Y， LU K. Flow Attribute-Aware Redundant Routing and Scheduling for Time-Triggered Flows in Time-Sensitive Networking[J]. Automobile Technology， 2024（10）： 38-42.

1 前言

隨著高級駕駛輔助系統(tǒng)、自適應前照燈系統(tǒng)等的廣泛應用，以太網(wǎng)以其高帶寬被引入車載網(wǎng)絡，然而傳統(tǒng)以太網(wǎng)采用盡力而為的傳輸機制，無法保證傳輸服務質(zhì)量（Quality of Service，QoS）[1]。因此，時間敏感網(wǎng)絡（Time-Sensitive Networking，TSN）作為傳統(tǒng)以太網(wǎng)的補充與增強，對車載以太網(wǎng)的確定性傳輸具有重要意義。

時間敏感網(wǎng)絡的4個關(guān)鍵領(lǐng)域為時間同步、端到端有界延遲、高可靠性及網(wǎng)絡管理[2]。TSN的通信流量依據(jù)QoS可分為3種類型，分別為時間觸發(fā)流（Time-Triggered，TT）、音頻視頻流（Audio Video Bridging，AVB）和盡力而為流（Best Effort，BE）[3-4]。其中，針對TT流和AVB流，TSN規(guī)定了不同的流量調(diào)度整形器以保證QoS。

IEEE 802.1 Qca推薦采用最短路徑作為路由方案，但過多流在同一路徑傳輸，增加了網(wǎng)絡擁塞的可能性，降低了可調(diào)度性[5]。IEEE 802.1 CB規(guī)定了一種幀復制與消除機制（Frame Replication and Elimination for Reliability，F(xiàn)RER），該機制采用多條不相交路徑傳輸同一份報文，實現(xiàn)了空間冗余與可靠性，但會導致網(wǎng)絡流量倍增。Huang等[6-7]提出了在路由階段最小化沖突程度（Degree of Conflict，DoC），保證TT流可靠性的同時，提高了可調(diào)度性，但未考慮時間觸發(fā)流周期和截止時間對可調(diào)度性的深層影響。

為解決上述問題，本文提出了一種針對TT流的流屬性感知冗余路由（Flow Attribute-Aware Redundant Routing，F(xiàn)AARR）方法，保證TT流可靠性的同時，提高可調(diào)度性。

2 數(shù)學建模

2.1 車載以太網(wǎng)建模

傳統(tǒng)分布式汽車電子電氣架構(gòu)（Electrical/Electronic Architecture，EEA）存在超過100個電子控制單元（Electronic Control Unit，ECU），需執(zhí)行超過1.5×108行代碼，其網(wǎng)絡負載成本與軟件復雜度極高[8]。為了解決分布式架構(gòu)的局限性，汽車的EEA逐步向區(qū)域集中式發(fā)展[9]。

本文基于面向區(qū)域的EEA架構(gòu)，搭建具有冗余連接的網(wǎng)絡模型，如圖1所示。網(wǎng)絡拓撲建模使用有向圖G=（V，E），其中：V=ES∪SW為網(wǎng)絡中所有節(jié)點的集合；E為網(wǎng)絡中所有鏈路的集合；SW為網(wǎng)絡中所有TSN交換機的集合；ES為網(wǎng)絡中所有終端系統(tǒng)的集合，包括ECU、攝像頭、雷達等。

以區(qū)域控制單元（Zone Control Unit，ZCU）和中央計算單元（Central Control Unit，CCU）中的TSN交換機建模，所有的物理連接均為以太網(wǎng)全雙工連接。（vi，vj）∈E，vi、vj分別為發(fā)送節(jié)點、接收節(jié)點，其中，vi、vj∈V。如圖1b中，路徑p從發(fā)送節(jié)點[vb∈V]到接收節(jié)點[vd∈V]的有序序列，流s1的一條冗余路徑為[p1s2]=[ES1，SW1，SW3，ZCU3]。

2.2 時間觸發(fā)信息流建模

時間觸發(fā)信息流為一系列周期性流量，每條時間觸發(fā)流s的屬性可用七元組來描述：

[s≡（vb，vd，T，Dsz，Te，Rl，C）] （1）

式中：vb為發(fā)送節(jié)點，vd為接收節(jié)點，T為周期，Dsz為幀數(shù)據(jù)大小，Te為截止時間，Rl為冗余等級，C為優(yōu)先級。

2.3 冗余路徑建模

基于FRER機制計算冗余路徑候選集，不相交路徑為：

[us={p1s…pRls|?1≤m，n≤Rl，m≠n，Ems∩Ens={[vb，vfirst]，[vlast，vd]}}] （2）

式中：us為流s的一條不相交路徑，[Eis]為路徑[pis]包含的所有鏈路的集合，vfirst、vlast分別為路徑ps經(jīng)過的第一個和最后一個TSN交換機。

因此，最終的單播冗余路徑候選集（Unicast Redundant Path Candidate Set，URPCS）為SURPCS=[{u1s…uts}]，該候選集所包含的不相交路徑的數(shù)量取決于網(wǎng)路拓撲和用戶需求。

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

本文基于K最短路徑（K Shortest Path，KSP）算法計算冗余路徑候選集，用于減少后續(xù)啟發(fā)式算法的搜索空間。為提升路由方案的可調(diào)度性，定量分析流屬性感知的評估函數(shù)，并基于具有精英策略的遺傳算法最大化評估函數(shù)得到最終冗余路由方案。

3.1 冗余路徑候選集計算

單播冗余路徑候選集算法如圖2所示，使用KSP算法[10]計算發(fā)送節(jié)點vb至接收節(jié)點vd的k條路徑，再根據(jù)冗余等級計算k條最短路徑的所有組合，將組合中滿足單播不相交路徑的組合添加至結(jié)果中。鑒于不相交路徑差會影響流調(diào)度[11]，因此，在篩選路徑組合時，將不相交路徑的最大路徑差作為篩選條件，本文中最大路徑差為2。

3.2 流屬性感知的評估函數(shù)構(gòu)建

當多個流在共享鏈路傳輸中發(fā)送沖突，沖突程度可表示為[6]：

[nDoC=Es1∩Es2?Dsz1?Dsz2T1?T2] （3）

式中：Es為路徑ps包含的所有鏈路的集合。

由于DoC未考慮流的截止時間，且未定量分析幀數(shù)據(jù)和周期對流調(diào)度的影響。為彌補上述不足，可將兩條流在共享鏈路傳輸時發(fā)生沖突的概率定義為：假設(shè)流s1在共享鏈路上傳輸，且0時刻傳輸?shù)?幀，流s2經(jīng)過該共享鏈路并與流s1發(fā)生沖突時，流s2的第1幀傳輸時間范圍與滿足流s2截止時間的第1幀傳輸時間范圍的比值。

假設(shè)流s1的第x幀與流s2的第y幀在某條共享鏈路上發(fā)生沖突，如圖3所示。其中：流s1的周期為T1，幀數(shù)據(jù)大小為Dsz1，截止時間為Te1；流s2的周期為T2，幀數(shù)據(jù)大小為Dsz2，截止時間為Te2。

發(fā)生沖突時，流s2第1幀的發(fā)送時間范圍為：

[Tconf=tt+y?T2gt;x?T1-Dsz2wt+y?T2lt;x?T1+Dsz1w=ttgt;x?T1-y?T2-Dsz2wtlt;x?T1-y?T2+Dsz1w]" （4）

式中：t為流s2第1幀發(fā)送時間，w為鏈路帶寬。

假設(shè)T1和T2的最大公約數(shù)為d，即：

[gcdT1， T2=dT1=d?a， T2=d?b， gcda，b=1] （5）

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

[Tconf=ttgt;（ax-by）d-Dsz2wtlt;（ax-by）d+Dsz1w] （6）

因此，可通過ax-by確定發(fā)生沖突的時間范圍。由于式（5）中g(shù)cd（a，b）=1，根據(jù)裴蜀定理，ax-by可取任意整數(shù)。為了滿足流s2的截止時間要求，即第1幀必須在截止時間前到達目的地，第1幀發(fā)送時間t的范圍為：

[Tall=t|t∈[0，Te2-Dsz2w]] （7）

向上取整，[k=（Te2-Dsz2w）/d]，則式（6）與式（7）存在交集的取值范圍為[T'conf=ax-by=-1ax-by=kTconf]。在共享鏈路中，當流s1存在時，流s2加入時發(fā)生沖突的概率為[p（s2|s1）conf=T'conf∩TallTall]，所以周期的最大公約數(shù)、流截止時間和幀數(shù)據(jù)為影響流沖突概率的關(guān)鍵因素。

為了消除流順序的影響，考慮流s1與s2在路徑上的所有共享鏈路，定義兩條流在所有共享鏈路上不發(fā)生沖突的評估函數(shù)為：

[fs1，s2sched=（1-ps2|s1conf+ps1|s2conf2）/Es1∩Es2]" "（8）

因此，n條流的流屬性感知的評估函數(shù)為：

[F=i≠j fsi，sjsched] （9）

公式的時間復雜度為O（n2），為了提升路由方案的可調(diào)度性，應該最大化F。

3.3 基于遺傳算法的流屬性感知的冗余路由方法

從冗余路徑候選集中篩選評估函數(shù)F最大的路由方案，可視為組合優(yōu)化問題。遺傳算法（Genetic Algorithm，GA）[12]是模擬生物邏輯進化的隨機搜索技術(shù)，具有較強的全局搜索能力。因此，本文采用具備精英選擇策略的遺傳算法求解最大評估函數(shù)的路由方案，算法流程如圖4所示。

遺傳算法主要包含基因編碼、選擇算子、交叉算子、變異算子和保留精英操作。假設(shè)存在n條流，則一個染色體包含n個基因，各基因為該流冗余路徑候選集選取的下標，最小值為1，最大值為該流冗余路徑候選集的數(shù)量。例如，編碼15表示兩條流，其中一條流選擇候選集中第1個冗余路由方案，則另一條流選擇候選集中第5個冗余路由方案。本文采用輪盤賭選擇算子、均勻交叉及以搜索域為中心的均勻變異，個體適應度（即評估函數(shù)）越大，被選中的概率越大。

4 基于整數(shù)線性規(guī)劃的無等待調(diào)度

各TSN交換機輸出端口均配置了GCL，列表中每一行表示一次操作，每一列表示對應門在該時刻的狀態(tài)，且該狀態(tài)持續(xù)到下一次操作。只有門處于打開狀態(tài)時，關(guān)聯(lián)的隊列數(shù)據(jù)才能被傳輸。若同一時刻多個門處于打開狀態(tài)，將根據(jù)傳輸選擇算法決定流量傳輸。

為了驗證FAARR的有效性，本文提出基于整數(shù)線性規(guī)劃（Integer Linear Programming，ILP）的無等待調(diào)度方法。TAS通過循環(huán)執(zhí)行GCL，對流量進行調(diào)度。其中，循環(huán)周期為超周期P，即所有流量周期的最小公倍數(shù)：

[Ns=PTs， P=lcmT1，T2，…，Tn] （10）

式中：Ns為流s在一個超周期內(nèi)傳輸?shù)膸瑪?shù)量。

流量調(diào)度是在一個超周期內(nèi)為所有流量的每一幀合理分配傳輸時間，使其滿足所有網(wǎng)絡約束和流量約束。為了便于建模，定義傳輸偏移變量為：

[Xsi， j=t，s∈S] （11）

式中：Xs（i， j）為流s的第i幀、第j條鏈路，S為待調(diào)度流量集合。

因此，流量調(diào)度問題可理解為：已知網(wǎng)絡拓撲G、待調(diào)度流量集合S、路由方案R，求解滿足相關(guān)約束，同時目標函數(shù)取最值的所有流量的Xs（i， j）。

4.1 時延約束

時延約束需保證每條TT流均能夠在截止時間之前到達目的地。由于流具有周期性，所以僅需保證第一幀在截止時間之前到達，后續(xù)幀發(fā)送時間為前一幀發(fā)送時間加上一個周期：

[?s∈S，?ej∈Es，?i∈2，3…NsXs1， j∈0，Te s-Dsz swXsi， j=Xsi-1， j+Ts] （12）

式中：ej為流s經(jīng)過的第j條鏈路。

4.2 無等待約束

GCL控制所有隊列狀態(tài)（打開或關(guān)閉）的時間，當門關(guān)閉時，隊列中可能存在待傳輸流量。

無等待調(diào)度是指交換機在接收到數(shù)據(jù)后立刻轉(zhuǎn)發(fā)，從而減少數(shù)據(jù)在隊列中的等待時間，但實際操作中，交換機存在處理延遲Td。由于流具有周期性，同理，僅需要對第1幀建立約束，則無等待約束為：

[?s∈S，?ej∈Es， jgt;1Xs1， j-Xs1， j-1=Td] （13）

4.3 無沖突約束

當流具有共享鏈路時，同一時刻只能有一條流傳輸數(shù)據(jù)，否則會發(fā)生沖突。而對于具有共享鏈路的兩條流s1的第x幀和s2的第y幀，需要滿足以下約束，兩者選擇其一即可：

a.先發(fā)送流s1的第g幀，后發(fā)送流s2的第k幀。

b.先發(fā)送流s2的第k幀，后發(fā)送流s1的第g幀。

由于冗余鏈路為不相交鏈路，因此，需在具有共享鏈路的流之間建立無沖突約束：

[?sm，sn∈S，?ej∈Esm∩Esn?g∈1，2…Nsm，?k∈1，2…NsnXsmg， j+Dsz smw≤Xsnk， j或Xsnk， j+Dsz snw≤Xsmg， j] （14）

式中：m為第m條流量，n為第n條流量。

4.4 目標函數(shù)

定義一個超周期內(nèi)所有流中的最大延遲為：

[?s∈S，Td max=max {XsNs， jlast+Dsz sw}] （15）

式中：Ns為流s在超周期內(nèi)的最后一幀，jlast為流s傳輸路徑上的最后一條鏈路。

因此，ILP求解的目標函數(shù)為fObject=minTd max。

5 仿真試驗

本文試驗網(wǎng)絡拓撲基于面向區(qū)域的EEA模型，網(wǎng)絡帶寬為100 Mbit/s，GA的迭代次數(shù)為100次，ILP求解器使用Gurobi，仿真流程如圖6所示。

比較KSP、DoC及FAARR路由方案對于不同流數(shù)量的調(diào)度成功次數(shù)，流數(shù)量分別為15條、20條、25條、30條和35條。根據(jù)文獻[13]，周期在10 ms、20 ms、30 ms、40 ms、60 ms、80 ms、120 ms中隨機選擇，幀數(shù)據(jù)大小從10～20 KB中隨機選擇，發(fā)送節(jié)點和接收節(jié)點分別從ES、CCU、ZCU中隨機選擇，冗余等級設(shè)置為2。

若基于ILP求解時存在可行解，即所有流量均滿足前文的調(diào)度約束，則調(diào)度成功。本文各方案調(diào)度次數(shù)為100次，試驗結(jié)果如圖7所示。

結(jié)果表明：隨著流數(shù)量的增加，各方案的調(diào)度成功率均下降。傳輸相同流數(shù)量時，F(xiàn)AARR相較于KSP和DoC方案，成功率均有提升。15條流量時，由于流量較低，全部選擇最短路徑的沖突較少；流數(shù)量為25條時，F(xiàn)AARR調(diào)度成功率提升顯著；流量增加至35條時，由于流量過高，每條鏈路發(fā)生沖突的概率增加，因而所有路由方案的調(diào)度成功率都很低，此時，應該增加網(wǎng)絡拓撲連通度或網(wǎng)絡帶寬。

綜上所述，本文提出的流屬性感知的冗余路由方法在保證可靠性的同時，相較于KSP方案調(diào)度成功率平均提升了38.9%，相較于DoC方案平均提升了14%。目前，智能網(wǎng)聯(lián)汽車一般配備4～11個攝像頭，6～12個超聲波雷達，1～3個毫米波雷達，0～1個激光雷達。流量數(shù)量在11至27條之間時，即使在高流量區(qū)間下，本文方案改善效果顯著。

6 結(jié)束語

本文提出了基于GA的流屬性感知的冗余路由方法，并通過基于ILP的調(diào)度驗證了其有效性。此外，本文主要關(guān)注離線路由與調(diào)度，對于算法運行時間要求不高，因此采用GA獲得更好的全局最優(yōu)性。未來，將以流屬性感知的評估函數(shù)為指導，降低算法復雜度來實現(xiàn)TT流的在線增量路由與調(diào)度。

參 考 文 獻

[1] COICHECI S， FILIP I. 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 J， BELLO L L， GUNTHER C. Time-Sensitive Networking Standards[J]. IEEE Communications Standards Magazine， 2018， 2（2）： 20-21.

[3] LAURSEN S M， POP P， STEINER W. Routing Optimization of AVB Streams in TSN Networks[J]. ACM SIGBED Review， 2016， 13（4）： 43-48.

[4] LI Y， YIN Z Y， MA Y， 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 K， WAN X M， WANG K， 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 V， SELIM G， PANTELIC V， 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 L， MIFDAOUI A， 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] 鄒淵， 孫文景， 張旭東， 等. 面向時間敏感網(wǎng)絡的車載以太網(wǎng)網(wǎng)絡架構(gòu)多目標優(yōu)化[J]. 汽車工程， 2023， 45（5）： 746-758.

ZOU Y， 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年9月27日。