基于分層調度算法的列車通信網絡實時性研究

賀德強，王亞松，陳彥君，姚曉陽

(1. 廣西大學 機械工程學院，廣西 南寧 530004; 2. 中車株洲電力機車研究所有限公司，湖南 株洲 412001)

列車通信網絡是現代軌道交通列車控制系統中的關鍵技術之一，主要用于傳輸列車運行狀態信息、控制信息、監視信息、故障信息和乘客信息等重要數據。隨著軌道交通朝著智能化方向發展，列車通信網絡技術將更加重要。傳統的列車通信網絡，如LonWorks、CAN、MVB和WTB，因通信速率低，難以滿足日益增長的列車通信量對高傳輸速率的要求[1]。為保障列車通信數據傳輸的實時性，基于全雙工的交換式以太網技術被引入到列車通信網絡中，它既能滿足大通信數據量的要求，又能降低傳統共享式以太網的非確定性[2]。

目前以太網在列車通信領域的研究已取得了一定的成果。文獻[3]研究了基于交換式以太網的列車通信網絡拓撲結構，并提出采用混合調度算法來改善實時性，但并未詳細說明混合調度算法的具體實現。文獻[4]研究了基于交換式以太網列車通信網絡與隨機Petri網模型，并采用了優先級調度，但對列車通信數據的優先級分配只按照數據類型分為三類，沒有考慮發送同優先級數據的沖突，無法滿足大通信數據量下列車對傳輸數據實時性的要求。文獻[5]研究了高可用性無縫冗余在列車通信網絡中的應用，但沒有對列車通信數據實時性進行量化研究。

為保障以太網列車通信網絡數據的實時性，需要對通信鏈路調度算法進行優化[6-7]。文獻[8]提出一種基于指數分區的最小截止期優先(Earliest Deadline First，EDF)調度算法，來提高CAN總線的實時性，可以改善網絡擁堵時低優先級不可調度的問題，但沒有對高優先級的實時性是否變化加以說明，而在實時系統中必須優先保證高優先級數據的實時性[9]。文獻[10]研究了如何使用EDF算法和最低松弛度優先算法實現最大延遲的最小化，但并未解決高優先級調度的問題。文獻[11]研究了EDF算法可調度性的改進方法，提出在任務截止期不大于其周期的基礎上，引入新的可調度性測試條件，減少測試所需的檢查點數量，使算法提前結束，但該算法在任務總利用率較高時改進效果有限。

本文綜合考慮列車通信數據對大容量數據和高實時性的要求，構建了基于全雙工交換式以太網的列車通信網絡三層拓撲結構；又根據列車通信數據對實時性的要求不同，結合上述拓撲結構，提出了基于優先級的分層調度算法，使用動態與靜態優先級結合的方式對列車通信數據進行調度；最后使用網絡演算理論和OPNET建模模擬，對分層調度算法的優越性進行仿真驗證。

1 基于交換式以太網的列車通信網絡

1.1 列車通信網絡三層拓撲結構

本文設計的列車通信網絡拓撲結構見圖1。它分為三層：第一層為列車級網絡，由各節車輛中的列車級交換機互聯組成環形拓撲列車級骨干網(Ethernet Train Backbone，ETB)，列車級交換機實現車載接入節點的數據處理和整車網絡管理；第二層為車輛級網絡，在每節車輛中以車輛級交換機為中心節點，采用星型拓撲部署各車載網絡節點；第三層為設備控制層，由每節車輛中各終端設備組成，數據經由端口傳入發送端系統，再由發送端系統將數據進行以太網幀封裝，送至交換機進行調度。每節車輛中的車輛級交換機和所有網絡節點構成一個車輛級局域網(Ethernet Vehicle Network，EVN)，整個局域網通過列車級網關與列車級交換機連接，構成完整的通信鏈路。網關實現對局域網的管理和列車級與車輛級網絡之間的協議轉換。每節車輛中配置一個車輛控制單元(Vehicle Control Unit，VCU)，對本節車輛的車輛級局域網節點進行管理。首尾司機室各配置一個列車中央控制單元(Center Control Unit，CCU)，與車輛控制單元進行數據交互。

圖1 列車通信網絡拓撲結構

1.2 列車通信數據

根據數據類型和實時性要求，在列車通信網絡中傳輸的通信數據分為以下5類：

(1)過程數據，表示車輛的實時運行狀態和控制指令，幀長度較小，屬于周期性強實時任務。

(2)消息數據，監視診斷信息和乘客信息，是按需傳送的偶發性數據，幀長度較大，屬于非周期性弱實時任務。

(3)監督數據，列車初運行數據或網絡冗余控制數據，只有在網絡重構或初始化時才被傳輸，屬于偶發任務，但是在列車初運行時監督數據屬于強實時任務。

(4)流數據，包括車輛運行中傳輸的視頻或語音流等數據，屬于非周期弱實時任務。

(5)最大努力數據，屬于非實時數據。

以上5類數據的數據幀長度和對實時性的要求均不相同，所以服務要求也有所區別。在列車通信網絡中傳輸時，應采用合理的調度算法來保證各類數據的服務要求。

2 基于優先級的調度算法研究

2.1 調度算法分析

目前在列車中廣泛使用的MVB/WTB總線均采用主從方式控制總線介質訪問，通過主設備將訪問權分配給從設備來實現調度。特征輪詢周期是基本周期的2n倍。每個基本周期可分為4個相：周期相、監視相、事件相和保護相。其中監視相、事件相和保護相構成偶發相。過程數據在周期相內發送，監督數據和消息數據在偶發相內發送。輪詢周期結束之后主權可依次輪換。MVB通信訪問方式見圖2。

圖2 MVB通信訪問方式

圖3 基于優先級的分層調度算法模型

這種調度方式的優點是在一個基本周期內可以發送所有類型的數據。但隨著列車控制系統的發展，傳輸的列車通信數據量不斷增大，現有MVB通信方式難以在一個基本周期內發送所有類型的數據。所以在基于以太網的列車通信網絡中，應采用更合適的調度算法來保證列車通信數據傳輸的實時性[12]。

在基于交換式以太網的實時系統中，要保證傳輸數據的實時性，不僅要考慮鏈路帶寬和吞吐量，還應該在調度算法上將所傳輸數據進行合理分類，實時性要求高、重要的數據優先發送，實時性低的數據其次，非實時性的數據最后發送，這點可以通過分配靜態優先級實現。

IEC 61375-3-4標準[13]對各個數據服務參數值的定義見表1。

表1 各數據的服務參數值

IEEE 802.1D[14]中規定，優先級分為0～7共8個組，最高優先級為7，最低優先級為0。根據通信數據的數據類型和優先級要求，可將數據在交換機中的傳輸隊列分為4個：0～1，2～3，4～5，6～7。數據優先級分配見表2。

表2 傳輸數據的優先級分配

發送端系統將數據包封裝為以太網數據幀時，應根據其數據類型分配靜態優先級，終端設備應使用RFC 2474[15]中定義的IP數據報中的差分服務代碼點(Differentiated Services Code Point，DSCP)字段。DSCP字段的二進制為LLL000，其中LLL為靜態優先級設定。

在基于靜態優先級調度下，同類型數據的優先級相同，可能出現如下情況：①兩條同種類型的數據流A和B同時到達處理器，產生沖突，數據立即停止發送，等待一個隨機時間R×51.2 μs后重新發送；②兩條同種類型的數據流A和B依次到達處理器，數據流B的截止期要比A早，等數據流A處理完畢后再處理數據流B，此時有可能已經超過了數據流B的截止期，則該數據失效。以上兩種情況在實時系統中均不可靠，所以要保證數據的實時性，還應在分配靜態優先級的基礎上進行動態優先級調度。

2.2 基于優先級的分層調度算法

根據上述分析，本文提出基于優先級的分層調度算法，其算法模型見圖3。

以太網幀封裝采用TCP/IP四層模型，見圖4。四層模型中分別添加DSCP字段(LLL000)、截止期(Deadline)字段、TCP首部、IP首部、幀頭和幀尾，最終封裝成以太網數據幀[16]。封裝好的以太網幀格式見圖5。

圖4 以太網幀封裝

圖5 封裝好的以太網幀格式

由于以太網幀封裝是在高層數據中添加DSCP字段和Deadline字段，且字段長度小，所以其對整個系統的時延影響較小，取決于發送節點封裝和接收節點解封處理速率。

在終端系統將數據進行以太網幀封裝后，按分配好的靜態優先級分為4個隊列，然后經過交換機進行動態優先級調度。本文采用EDF算法[17]作為動態優先級調度算法。EDF算法根據任務的絕對截止期分配動態優先級，截止期越小，優先級越高。

數據傳輸過程：在交換機中按靜態優先級傳輸4個隊列的數據，同一隊列中的數據再計算絕對截止期，根據動態優先級從高到低傳輸。使用分層調度算法既能夠保證數據傳輸的有效性，又能夠細分數據優先級，保證強實時任務的實時性。

2.3 可調度性驗證

圖6 任務的最大響應時間

由上述分析可知，忙碌期的長度L(a)等于[t1,t2]時刻內完成所有任務的執行時間之和，且所有任務至少被執行一次，則

(1)

式中：?x-|表示對x向下取整。

Cj，則

(2)

(3)

(4)

假設任務集中有4個任務，任務參數見表3。

表3 任務參數

可計算初始值L0(a)=7 ms，再計算a取不同值時任務τ1的響應時間Lm(a)-a，見表4。

表4 任務τ1的響應時間

由表4可以看出，任務τ1的最大響應時間tworst-1為6 ms。同理可得其他任務的最大響應時間，見表5。

表5 各任務的最大響應時間

表5中最大響應時間均小于表3中最小截止時間，所以該任務集可調度。

3 列車通信數據時延分析

在本文提出的列車通信網絡模型中，數據幀從源節點發出，經過交換機服務后到終端節點被接收，其所經歷的端到端時延分為以下幾部分：

(1)幀處理時延TFrm-prcs，代表源節點對數據的以太網幀封裝時間，與數據幀長度有關。

(2)發送節點時延Tsc-prcs，代表以太網數據幀的發送延遲。

(3)物理鏈路時延TLink，代表電信號在物理鏈路上傳輸的時間。

(4)交換機處理時延Tswitch，代表交換機內部的排隊時間和幀轉發時間。

(5)接收節點幀處理時延Trcv-prcs，代表以太網數據幀的接收時間和協議棧處理時間。

通信數據的整體端到端時延為

Tdelay=TFrm-prcs+Tsc-prcs+∑TLink+

∑Tswitch+Trcv-prcs

(5)

3.1 基于網絡演算理論的時延分析

(6)

以下采用確定性網絡演算理論對列車實時數據的端到端時延進行分析。確定性網絡演算是網絡演算理論中的一類，將最小加代數與到達曲線和服務曲線等演算工具相結合，來求解網絡性能邊界的確定性絕對值大小，網絡端到端時延上界由到達曲線和服務曲線的距離所決定[19]。

考慮數據幀的大小，交換機可以提供的總服務曲線[20]為

β(t)=[St-L(t)]+

(7)

設數據流i的服務曲線為仿射到達曲線[21]，即

αi(t)=rit+bi

(8)

式中：ri為平均生成速率；bi為突發容忍度。則交換機提供給數據流i的服務曲線為

(9)

交換機對數據流i的服務能力Ri和服務時延Ti[22]分別為

(10)

3.2 實例計算

采用如圖1的網絡拓撲結構；列車級交換機和車輛級交換機帶寬均為100 Mbit/s；每節車輛配置15個網絡節點，包括中間車輛的車輛控制單元和首尾司機室的中央控制單元；車輛長度取26 m，電纜長度取車輛長度的1.5倍[23]，即39 m；滿足以太網100 m的傳輸距離要求，信號在物理介質中傳輸速度為2.0×108m/s；以太網的幀長度為84～1 542 octets。

假定監督數據和過程數據均采用最小數據幀84 octets，取每個周期(監督數據為10 ms，過程數據為20 ms)發送一個數據幀，則監督數據的到達曲線為

α7(t)=8 400t+84

(11)

過程數據的到達曲線為

α5(t)=4 200t+84

(12)

消息數據和流數據一般比較大，取最大數據幀1 542 octets，其發送速率為監督數據的0.2倍，發送一個數據幀，其到達曲線為

α3(t)=1 680t+1 542

(13)

最大努力數據為非實時數據，其到達曲線為

α1(t)=1 680t+15 420

(14)

以過程數據隊列(靜態優先級Pi為5)中的一個微數據流為例(各參數見表3，已驗證過其可調度性)，

τ={τi(Ti,Ci,Di,Pi,ti),i=1,2,3，…，n}=

{τ1(20,1,6,5,0),τ2(20,2,4,5,0),

τ3(20,2,5,5,4),τ4(20,2,8,5,6)}

(15)

另外，監督數據的優先級比過程數據高，假設監督數據隊列發送一個數據幀，以下分別采用分層調度算法和固定優先級調度算法對其進行端到端時延計算。固定優先級調度算法指不使用分層調度算法，只按照靜態優先級的高低進行隊列排序，交換機按照最基本的先來先服務(First Come First Serve，FCFS)原則接收處理任務集信息，只處理位于隊列首位的數據。

3.2.1 分層調度算法

假設發送節點以太網幀封裝速率為10 Mbit/s，接受節點的協議棧處理時間取50 μs，數據從設備輸出端口至中央控制單元最遠要通過7個交換機和8段鏈路，再將T5-3及其他數據代入式(5)得到任務τ3的端到端時延為

同理可求任務τ1、τ2、τ4的端到端時延。

3.2.2 固定優先級調度算法

任務集τ中的4個任務靜態優先級Pi均等于5，所以在交換機中按照其到達時間順序先后τ1>τ2>τ3>τ4發送。但在t=0時刻，任務τ1和任務τ2同時到達，發生第一次沖突，須返回并等待一個隨機時間R×51.2 μs后再重新發送。R取0～(22-1)之間的一個隨機整數，令任務τ1等待2×51.2 μs，任務τ2等待3×51.2 μs，這樣不影響原來的發送順序。將各項參數代入式(10)可得交換機對任務τ1的服務能力和服務時延分別為9.999 16×107bit/s、0.115 8 ms。

再將結果代入式(5)，其他參數同上，可得任務τ1的端到端時延為0.929 6 ms。

同理可求任務τ2、τ3、τ4的端到端時延。

3.2.3 結果對比

對同一個任務集使用不同的調度算法，得出的各任務時延及平均時延見表6。

表6 使用不同調度算法的端到端時延

由表6可以看出，對任務集τ，使用分層調度算法可以降低其整體平均時延，提高數據傳輸的實時性。

4 基于OPNET的列車通信網絡實時性仿真

為驗證分層調度算法的優越性，采用OPNET Modeler仿真平臺搭建列車通信網絡仿真模型，仿真2個場景：

(1)以圖1中的網絡拓撲為模型，場景大小400 m×400 m，8個100 Mbit/s帶寬的24接口列車級交換機采用環形拓撲方式連接，交換機之間相距50 m，每個列車級交換機通過網關與車輛級交換機連接，再以車輛級交換機為中心，采用星型拓撲連接20個網絡節點發送所有類型數據，中間6個車輛級交換機再各連接一個VCU，發送和接收該節車輛數據，兩司機室的車輛級交換機再各連接一個CCU，同各VCU進行數據交換，交換機使用分層調度算法，參照3.2節為各個網絡節點配置通信數據。

(2)拓撲模型和網絡節點數據同場景(1)，交換機使用基于固定優先級的FCFS調度算法。

4.1 鏈路吞吐量

由于司機室的CCU對各個VCU進行控制，所以對CCU與VCU之間的鏈路吞吐量進行測量，測量結果見圖7。由圖7可以看出：仿真時間在0～100 s之間時，鏈路吞吐量達到了4.1×106bit/s，這是由于仿真開始時通信數據量較大，4種數據同時發送，在交換機中出現排隊積壓現象；仿真繼續進行，通信數據在隊列中趨于穩定，沒有突發性大容量產生，使得吞吐量趨于平緩，最終穩定在2.3×106bit/s左右。

圖7 CCU與VCU之間鏈路吞吐量

4.2 端到端時延

2個場景下的數據端到端時延仿真結果分別見圖8和圖9。在采用分層調度算法的情況下，4個隊列的數據時延分別為0.226、0.266、0.786、1.086 ms；在采用固定優先級調度算法的情況下，4個隊列的數據時延分別是0.590、0.698、0.852、0.990 ms。

圖8 采用分層調度算法端到端時延

圖9 采用固定優先級調度算法端到端時延

通過比較可以看出，兩種調度算法均可以區分不同優先級隊列的數據，并且能夠保證高優先級數據優先發送；相較于固定優先級調度，使用分層調度算法使監督數據和過程數據的時延分別降低61.7%和61.9%，消息數據和流數據的時延降低7.7%，最大努力數據的時延提高9.7%。使用分層調度算法后，對于高優先級數據，可以明顯提高實時性；對于低優先級實時數據，由于其數據幀較大，可以少量提高實時性；對于非實時數據，由于其數據幀大且排在最后隊列，會少量降低實時性，但是非實時數據的實時性不是重要因素，可以接受較高時延。再比較兩種調度算法下的各數據平均時延，由圖10可以得到結論，添加動態優先級調度對系統的時延影響較小，使用分層調度算法可以有效降低數據整體傳輸時延，且顯著提高了高優先級數據的實時性。

圖10 兩種調度算法的平均時延

5 結論

列車通信網絡的發展趨勢是大帶寬、高通信速率，基于以太網的列車通信網絡是其發展方向。在此背景下，本文提出了基于優先級的分層調度算法，根據數據類型和實時性需求分配靜態優先級，再使用EDF算法作為動態優先級調度，確定最終優先級。理論分析和仿真結果表明，采用該調度算法可以有效改善列車通信數據的整體實時性，滿足IEC 61375-3-4標準中對各數據最大延遲的要求；并且相較于固定優先級調度，該算法使優先級較高的監督數據和過程數據的實時性分別提高了61.7%和61.9%，顯著提高了高優先級數據的實時性，為大容量數據傳輸趨勢下的列車通信網絡提供了理論參考和可行方案。