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

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

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

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

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

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

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

1 基于交換式以太網(wǎng)的列車通信網(wǎng)絡

1.1 列車通信網(wǎng)絡三層拓撲結構

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

圖1 列車通信網(wǎng)絡拓撲結構

1.2 列車通信數(shù)據(jù)

根據(jù)數(shù)據(jù)類型和實時性要求，在列車通信網(wǎng)絡中傳輸?shù)耐ㄐ艛?shù)據(jù)分為以下5類：

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

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

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

(4)流數(shù)據(jù)，包括車輛運行中傳輸?shù)囊曨l或語音流等數(shù)據(jù)，屬于非周期弱實時任務。

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

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

2 基于優(yōu)先級的調度算法研究

2.1 調度算法分析

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

圖2 MVB通信訪問方式

圖3 基于優(yōu)先級的分層調度算法模型

這種調度方式的優(yōu)點是在一個基本周期內可以發(fā)送所有類型的數(shù)據(jù)。但隨著列車控制系統(tǒng)的發(fā)展，傳輸?shù)牧熊囃ㄐ艛?shù)據(jù)量不斷增大，現(xiàn)有MVB通信方式難以在一個基本周期內發(fā)送所有類型的數(shù)據(jù)。所以在基于以太網(wǎng)的列車通信網(wǎng)絡中，應采用更合適的調度算法來保證列車通信數(shù)據(jù)傳輸?shù)膶崟r性[12]。

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

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

表1 各數(shù)據(jù)的服務參數(shù)值

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

表2 傳輸數(shù)據(jù)的優(yōu)先級分配

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

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

2.2 基于優(yōu)先級的分層調度算法

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

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

圖4 以太網(wǎng)幀封裝

圖5 封裝好的以太網(wǎng)幀格式

由于以太網(wǎng)幀封裝是在高層數(shù)據(jù)中添加DSCP字段和Deadline字段，且字段長度小，所以其對整個系統(tǒng)的時延影響較小，取決于發(fā)送節(jié)點封裝和接收節(jié)點解封處理速率。

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

數(shù)據(jù)傳輸過程：在交換機中按靜態(tài)優(yōu)先級傳輸4個隊列的數(shù)據(jù)，同一隊列中的數(shù)據(jù)再計算絕對截止期，根據(jù)動態(tài)優(yōu)先級從高到低傳輸。使用分層調度算法既能夠保證數(shù)據(jù)傳輸?shù)挠行?，又能夠細分?shù)據(jù)優(yōu)先級，保證強實時任務的實時性。

2.3 可調度性驗證

圖6 任務的最大響應時間

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

(1)

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

Cj，則

(2)

(3)

(4)

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

表3 任務參數(shù)

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

表4 任務τ1的響應時間

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

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

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

3 列車通信數(shù)據(jù)時延分析

在本文提出的列車通信網(wǎng)絡模型中，數(shù)據(jù)幀從源節(jié)點發(fā)出，經(jīng)過交換機服務后到終端節(jié)點被接收，其所經(jīng)歷的端到端時延分為以下幾部分：

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

(2)發(fā)送節(jié)點時延Tsc-prcs，代表以太網(wǎng)數(shù)據(jù)幀的發(fā)送延遲。

(3)物理鏈路時延TLink，代表電信號在物理鏈路上傳輸?shù)臅r間。

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

(5)接收節(jié)點幀處理時延Trcv-prcs，代表以太網(wǎng)數(shù)據(jù)幀的接收時間和協(xié)議棧處理時間。

通信數(shù)據(jù)的整體端到端時延為

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

∑Tswitch+Trcv-prcs

(5)

3.1 基于網(wǎng)絡演算理論的時延分析

(6)

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

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

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

(7)

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

αi(t)=rit+bi

(8)

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

(9)

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

(10)

3.2 實例計算

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

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

α7(t)=8 400t+84

(11)

過程數(shù)據(jù)的到達曲線為

α5(t)=4 200t+84

(12)

消息數(shù)據(jù)和流數(shù)據(jù)一般比較大，取最大數(shù)據(jù)幀1 542 octets，其發(fā)送速率為監(jiān)督數(shù)據(jù)的0.2倍，發(fā)送一個數(shù)據(jù)幀，其到達曲線為

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

(13)

最大努力數(shù)據(jù)為非實時數(shù)據(jù)，其到達曲線為

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

(14)

以過程數(shù)據(jù)隊列(靜態(tài)優(yōu)先級Pi為5)中的一個微數(shù)據(jù)流為例(各參數(shù)見表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)

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

3.2.1 分層調度算法

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

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

3.2.2 固定優(yōu)先級調度算法

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

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

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

3.2.3 結果對比

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

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

由表6可以看出，對任務集τ，使用分層調度算法可以降低其整體平均時延，提高數(shù)據(jù)傳輸?shù)膶崟r性。

4 基于OPNET的列車通信網(wǎng)絡實時性仿真

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

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

(2)拓撲模型和網(wǎng)絡節(jié)點數(shù)據(jù)同場景(1)，交換機使用基于固定優(yōu)先級的FCFS調度算法。

4.1 鏈路吞吐量

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

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

4.2 端到端時延

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

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

圖9 采用固定優(yōu)先級調度算法端到端時延

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

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

5 結論

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