時間敏感網絡中時間觸發流冗余路由與調度研究

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

主題詞：車載以太網 時間敏感網絡 路由調度 冗余

中圖分類號：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

【引用格式】 鐘旭， 朱元， 陸科. 時間敏感網絡中時間觸發流冗余路由與調度研究[J]. 汽車技術， 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 前言

隨著高級駕駛輔助系統、自適應前照燈系統等的廣泛應用，以太網以其高帶寬被引入車載網絡，然而傳統以太網采用盡力而為的傳輸機制，無法保證傳輸服務質量（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×108行代碼，其網絡負載成本與軟件復雜度極高[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交換機建模，所有的物理連接均為以太網全雙工連接。（vi，vj）∈E，vi、vj分別為發送節點、接收節點，其中，vi、vj∈V。如圖1b中，路徑p從發送節點[vb∈V]到接收節點[vd∈V]的有序序列，流s1的一條冗余路徑為[p1s2]=[ES1，SW1，SW3，ZCU3]。

2.2 時間觸發信息流建模

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

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

式中：vb為發送節點，vd為接收節點，T為周期，Dsz為幀數據大小，Te為截止時間，Rl為冗余等級，C為優先級。

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經過的第一個和最后一個TSN交換機。

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

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

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

3.1 冗余路徑候選集計算

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

3.2 流屬性感知的評估函數構建

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

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

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

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

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

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

[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幀發送時間，w為鏈路帶寬。

假設T1和T2的最大公約數為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確定發生沖突的時間范圍。由于式（5）中gcd（a，b）=1，根據裴蜀定理，ax-by可取任意整數。為了滿足流s2的截止時間要求，即第1幀必須在截止時間前到達目的地，第1幀發送時間t的范圍為：

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

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

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

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

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

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

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

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

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

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

4 基于整數線性規劃的無等待調度

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

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

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

式中：Ns為流s在一個超周期內傳輸的幀數量。

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

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

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

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

4.1 時延約束

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

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

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

4.2 無等待約束

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

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

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

4.3 無沖突約束

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

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

b.先發送流s2的第k幀，后發送流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 目標函數

定義一個超周期內所有流中的最大延遲為：

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

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

因此，ILP求解的目標函數為fObject=minTd 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流的在線增量路由與調度。

參 考 文 獻

[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] 鄒淵， 孫文景， 張旭東， 等. 面向時間敏感網絡的車載以太網網絡架構多目標優化[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日。