MVB網絡實時性算法綜述

徐進權， 王宏志， 胡黃水

（長春工業大學 計算機科學與工程學院，吉林 長春 130012）

0 引 言

多功能車輛總線是一種用于列車車輛內部各功能設備之間實現互連的網絡總線，是應用于車輛控制這一特定場合的現場總線［1－2］。列車通信網絡標準IEC61375－1是國際電工委員會為車載數據通信制定的一項國際標準，其明確指出MVB網絡通信必須滿足列車對數據傳輸提出的實時性要求，實時性直接影響著整個列車的控制性能。因此，認真研究MVB網絡實時性相關技術是十分必要的，以便形成MVB網絡實時調度機制、實時性能評價等方面的理論模型和分析方法。在國際標準中對MVB數據傳輸的實時性要求有明確規定。如何保證網絡傳輸的實時性要求，學術界進行了研究，并提出了許多相應的算法［3－5］。

文中對當前關于MVB網絡實時性算法的研究現狀和存在的問題與發展方向等方面進行了闡述。

1 MVB網絡

1.1 周期掃描表

周期掃描表定義了周期發送的主幀，以及在輪回中每一基本周期內留給偶發相的剩余時，在周期查詢中，主設備按照周期掃描表發送一個預先定義好的主幀序列［6］。在周期輪詢中，主設備按照周期掃描表發送一個預先定義好的主幀序列。

1.2 過程數據和消息數據

周期數據主要是過程數據；非周期數據主要是消息數據。過程數據幀的長度較短，但實時性要求強，傳輸時間確定有界，周期性發送，沒有流控制和差錯恢復，是無需確認的廣播通信。過程數據一般用于列車控制［7］。過程數據是基于時間觸發的周期性數據，而消息數據是基于事件觸發的偶發性數據。由于消息數據的偶發性和MVB總線的主從工作方式，消息數據的通信分為3個步驟：設備事件掛起；主設備輪詢；主設備指定的設備開始傳輸消息數據。

1.3 MVB幀格式

MVB主幀長度固定，共33位：9位主起始分界符，16位幀數據，8位校驗序列，終止分界符［8］。主幀格式如圖1所示。

圖1 主幀格式圖

MVB從幀長度不固定，存在5種類型：9位從起始分界符，接著為16、32、64、128和256位幀數據。通信過程是主設備發出主幀，從設備發出從幀響應該主幀［9］，從幀格式如圖2所示。

圖2 從幀格式圖

1.4 MVB實時性要求

MVB數據傳輸實時性的目標是在可靠性、準確性的情況下盡可能快速地傳輸數據。

根據國際標準IEC61375－1［10］，信號產生速度應為1.5Mbit±0.01%／s。任何兩個設備之間的響應延時都不應大于42.7μs。兩個相鄰主幀之間的時間間隔應大于9.0BT。對于MVB總線上所有重要變量，從一個應用到另一應用的確定性傳送必須保證在16ms內完成。周期掃描表中最長的特征周期不能超過1 024.0ms。

2 實時性算法研究現狀

根據MVB網絡傳輸數據的類型，將現有的實時算法分為周期數據實時性算法和非周期數據實時性算法。

2.1 周期數據傳輸實時算法

對于周期數據，主要是過程數據，MVB網絡數據傳輸的主要方式是主設備根據周期掃描表尋址源設備。周期數據傳輸實時算法依據周期掃描表的輪詢方式分為3類，如圖3所示。

圖3 周期數據傳輸實時算法

2.1.1 實時調度算法

調度的實質是資源的分配，而實時調度強調的是任務的時間約束［11］。實時調度算法中常見的是基于優先級驅動的調度算法，一般分為靜態優先級調度和動態優先級調度［12］。靜態優先級調度算法的代表是單調速率算法（Rate Monotonic，RM）［13－14］；動態優先級調度算法的代表是最早截止期優先算法（Earliest Deadline First，EDF）［15］。不論是何種調度算法，在進行實時調度時都要在周期輪詢之前進行可調度性能分析，即判斷調度算法是否能夠滿足系統的實時性、可靠性［16］?，F在常采用基于系統利用率和任務響應兩種方法進行可調度算法性能分析。前者計算精確度不夠，但計算開銷小，可以用于新任務的接入控制；后者計算開銷大，但可以得到每個任務的響應時間。

RM算法是一種靜態固定分配算法。RM算法根據任務執行周期的長短來決定優先級高低，執行周期短的任務優先級高，執行周期長的任務優先級低。即速率越高，優先級越高。EDF算法是一種基于動態優先級的調度算法［17］，按照數據的截止時間來確定優先級。任務的截止時間越小，優先級越高；任務的截止時間越大，優先級越低［18］。在每一個可調度時刻，數據任務的優先級都需要動態調整。

對于RM算法，前文中提到的兩種調度性能分析的方法都無法直接應用，且靈活性、自適應性較差。對于EDF算法，適應性強，但調度工作量大。有專家提出，將RM算法和EDF算法合理結合，可以得到一種含閾值的多處理器實時任務調度方法［19］，該方法可以使任務在閾值范圍內在各處理器上進行遷移，避免了部分處理器處于空閑，部分處理器過于繁忙導致的任務被掛起現象，保證各處理器利用率相對平衡，從而實現提高系統的實時性。

2.1.2 報文定時無關的周期掃描表優化設計

列車通信網絡協議指出，如果在周期輪詢中能夠均勻地安排循環周期，就能得到更好的實時性。而要想實現均勻的安排循環，就要盡可能減低周期掃描表的陡度和寬度。利用基本規則［6］生成的周期掃描表陡度較大，周期數據分布不夠均勻。利用逐步填空法［6］可以生成報文定時無關的周期掃描表，陡度較小，周期數據較為均勻，從而實時性更好。

2.1.3 報文定時相關的周期掃描表優化設計

分析報文定時的周期掃描表時，隨著數據數量的不斷增加，如何快速合理地分配周期數據在周期掃描表中的位置是一個很難解決的問題，基本規則和逐步填空算法都達不到理想要求。報文定時相關的周期掃描表優化的實質是典型的組合優化問題［20］。為了找到求解組合優化問題的最合適方法，相關學者提出了近似算法（Approximate Algorithm，AA）［21］、啟發式算法（Heurisc Algorithm，HA）［22］、群體智能優化算法（Population－based Intelligent Optimization，PIO）［23－24］等方法。AA算法的計算結果與最優結果之間是有最優度保證的，但近似算法沒有可遵循的框架，設計復雜，實際操作較為困難；HA算法比較容易實現，可以應用在非常廣泛的問題上，但是該算法要求對每一個問題都要建立一個特殊的啟發式規則，此類規則不具備通用性，不能保證效率；PIO算法是基于群體智能理論的一種新型演化計算技術，具有較強的通用性和全局尋優的特點。

遺傳算法是群體智能優化算法的一種，是一種全局搜索算法。其局部搜索能力較差，具有“早熟”問題，所以比較費時，在進化后期搜索效率較低?；旌线z傳算法［25－26］是在遺傳算法的基礎上引入其它優化算法（如局部搜索能力強的算法），以保證遺傳算法在全局性能的基礎上大大減小計算量來提高收斂速度，以保證周期通信的實時性。

2.1.4 算法比較分析

對于MVB周期數據的實時性優化，實際是周期掃描表的優化。對周期掃描表進行優化的目標是使周期數據能夠均勻分布在周期掃描表中，這就要求周期掃描表的寬度和陡度很小。無論是RM算法還是EDF算法，在實現調度之前，需要進行調度性分析。RM算法和EDF算法都有其局限性，如何結合兩種算法的優勢，揚長避短，是未來研究的一個重要方向。

靜態優先級調度算法可以依靠時間屬性分配優先級，可控性較強，而動態優先級調度算法在資源分配和調度時，靈活性較強。AA算法實際操作困難、HA算法通用性較差、遺傳算法不具備全局收斂性。鑒于此，有學者又提出了改進的混合遺傳算法，但是混合遺傳算法也有不足，如計算量很大。對于周期掃描表的優化，群體智能優化統一框架下的算法是未來研究實時性的一個重要方向和領域。算法具體性能對比見表1。

表1 算法性能對比

2.2 非周期數據傳輸實時性算法

非周期數據主要是消息數據，是按需傳送的，屬偶發性數據，一般用于任務診斷。消息數據的傳遞是通過MVB主設備發送事件請求來實現的。在偶發相中，總線主設備告知有事件的設備。主設備發布一個一般事件輪詢開始事件巡回，要求所有設備報告事件，當幾個設備同時掛起時，會有多個響應產生，發生碰撞。因此需要采用MVB事件仲裁機制對事件進行仲裁分辨［27］。在IEC協議中，說明了3種仲裁方法：首次仲裁、向下仲裁、向上仲裁。仲裁調度的過程是系統資源分配的過程，也就是對消息數據按照一定規則進行合理調度的過程。消息數據傳輸實時算法根據縮短延時的方法，可以分成3類，如圖4所示。

2.2.1 典型事件搜索算法

典型事件仲裁算法按照折半查找法對網絡設備進行搜索查找。折半查找是一種簡單常用的方法，并且當每個記錄的查找概率相等時，折半查找算法的性能是最優的［28］，由于折半查找法是將查找的范圍不斷縮小一半，所以查找效率較高，但計算開銷大。當主設備發送組事件請求之后，如果收到單個響應，則主設備返回此響應；主設備將組地址的最低有效位取反并發送組事件請求。如果產生碰撞，主設備將對具有公共地址的上次組中的半數設備形成一個新組，發送一個組事件請求。如果組事件請求響應為寂靜主設備再次發送的組事件請求尋址范圍為前一次的一半。具體流程如圖5所示。

圖4 非周期數據傳輸實時算法

圖5 事件仲裁流程圖

針對查找范圍變化很大而又相對穩定的查找對象，人們又提出了一種改進的基于區間控制的折半查找算法，當后一個查找對象在前一個查找對象附近時，在最壞狀態和平均狀態下，該算法查找速度更快，實現代價更?。?9］。

2.2.2 二叉樹仲裁

首先明確兩個概念：當節點數目相同時，完全二叉樹的路徑長度最短；樹的帶權路徑長度最小的二叉樹稱為最優二叉樹，即哈夫曼樹，相應的算法稱為哈夫曼算法［30］。根據組地址的定義及相關特點，可以引入仲裁二叉樹來實現事件仲裁。引入仲裁二叉樹后，根據連續分配地址方式，生成了一顆完全二叉樹。連續分配方式產生的完全二叉樹的缺點是此類二叉樹不是任意條件下的最優二叉樹。當設備延時相同，連續分配方式生成的是最優二叉樹；當設備延時不同，只有通過最優二叉樹算法分配地址才能保證時間仲裁時延最優化。

最優二叉樹通常有兩種生成算法，分別是哈弗曼算法和逆推調位算法［31］。逆推調位算法利用遞推算法的逆推原理，根據被處理結點位置移動產生的權的變化值確定各個結點的精確位置。由于逆遞推調位算法在運算過程中的比較次數少，所以使得運算的整體速度比哈夫曼算法更快。即在空間復雜度上，哈弗曼算法比逆推調位算法簡單；在時間復雜度上，逆推調位算法比較簡單。因為仲裁二叉樹是有限深度的，所以仲裁二叉樹的生成算法一般選擇哈弗曼算法［32－33］。

2.2.3 優先級配置算法

想要滿足非周期數據傳輸的實時要求，也可以利用優先級配置方法［2］，即利用物理地址優先級和事件優先級兩種方法來縮短仲裁延時。

物理地址優先級：仲裁過程一般是從設備的物理地址最低位開始逐位搜索，因此在安排設備物理地址時，從1開始定義，逐位增加，連續分配。這樣地址越小，則其優先級越高。

事件類型優先級：在一般事件請求幀中有4位用來定義事件類型，可以最多定義16種優先級類型。但國際標準中僅使用最低位定義了兩種事件優先級類型：高優先級和低優先級。當設備較多時，發生沖突碰撞的概率就會增加。因此，可以根據事件的重要性設置多種優先級，以減小碰撞發生的概率。

2.2.4 算法比較分析

事件仲裁是事件輪詢機制的核心部分。提高消息數據傳輸的實時性，實質上是對沖突事件進行合理調度，從而減少仲裁時延。經典算法和典型時間搜索算法是比較基礎的仲裁算法，在此基礎上，可以提出諸多改進算法，以提升數據傳輸的實時性能。折半查找算法是一種常見的算法，計算開銷大，不適宜大范圍查找。改進的折半查找算法相對來講在速度和計算復雜度方面有所提高。二者都適用于過程控制中的實時查找。仲裁二叉樹算法的提出為仲裁過程的分析實現提供了又一方法思路。對二叉樹模型進一步改進優化，即利用設備地址分配方式提出的有限深度最優二叉樹算法得到的分配方式比連續分配方式有明顯的優勢，有限深度最優二叉樹算法改進了連續分配方式產生的二叉樹的不足，進一步減少了仲裁延時。

算法的性能對比見表2。

表2 算法性能對比

3 結 語

按照周期數據傳輸和非周期數據傳輸兩個方面對MVB網絡實時性算法研究的現狀進行了總結，并對當前研究中存在的普遍問題進行了分析和概括。從目前的研究現狀來看，已經提出了許多有效算法來改善系統的實時性，如遺傳算法、最優二叉樹算法等。

總體來說，提高MVB網絡實時性要盡量使周期掃描表中數據分布均勻、減小算法復雜度、提高計算精確度、提高介質傳輸速率、減少仲裁延時。同時，通過減少響應時間、提高反應速率、縮小仲裁延時，改善MVB網絡實時性?？梢?，MVB網絡實時性算法還有許多領域可以進一步研究。

［1］ 周俊，姬長英.智能車輛橫向控制研究［J］.機器人，2003，25（1）：26－30.

［2］ 聶曉波，王立德，申萍.軌道車輛MVB網絡實時性能分析與優化研究［J］.鐵道學報，2011，33（9）：40－44.

［3］ 王濤，王立德，周潔瓊.MVB網絡周期輪詢算法優化與仿真研究［J］.機車電傳動，2013（6）：40－45.

［4］ 朱俊，李芳，王麗芳.基于蟻群算法的多功能車輛周期掃描表的優化設計［J］.鐵道學報，2013，35（7）：57－62.

［5］ 戴嘉瑋，韋巍.基于多功能車輛總線事件仲裁的優化設計［J］.鐵道學報，2013，35（4）：66－70.

［6］ 王永翔，王立德.多功能車輛總線周期掃描表的最優化設計［J］.鐵道學報，2009，31（6）：46－52.

［7］ 王永翔，王立德.基于廣義隨機Petri網的MVB網絡吞吐性能分析［J］.北京交通大學學報：自然科學版，2008，32（5）：98－101.

［8］ 陳特放，曾秋芬.列車微機與網絡控制技術及應用［M］.北京：科學出版社，2012.

［9］ 劉建偉，王蕾，譚南林，等.軌道車輛MVB通信網絡的實施特性［J］.中國鐵道科學，2006，27（6）：79－82.

［10］ International electrotechnical commission.IEC61375－1：1999，part 1：Train communication network［S］.Genva，1999.

［11］ 夏家莉，陳輝，楊兵.一種動態優先級實時任務調度算法［J］.計算機學報，2012，35（12）：2684－2694.［12］ 吳星.多處理器實時任務調度策略的研究［D］.昆明：昆明理工大學，2013.

［13］ 王愛平，張功營，劉方.一個基于R M的弱硬實時調度算法［J］.東北大學學報：自然科學版，2006，27（7）：743－746.

［14］ Giorgio C Buttazzo.Rate monotonic vs.EDF：judgmentn Day［J］.Real－Time Systems，2005，29（1）：5－26.

［15］ 程禹，趙宏偉，龍曼麗，等.最早截止期優先調度算法的改進［J］.吉林大學學報：工學版，2013，43（5）：1338－1342.

［16］ 朱琴躍，謝偉達，譚喜堂，等.MVB周期信息的實時調度［J］.計算機應用，2007，27（12）：3108－3115.

［17］ 張惠娟，周利華.一種基于EDF算法的多處理器實時調度算法［J］.計算機工程與應用，2003，39（30）：16－17.

［18］ 袁暋，檀明，周晶晶.EDF調度算法可調度性分析方法的改進研究［J］.計算機應用研究，2013，30（8）：2429－2431.

［19］ 王異奇.多處理器實時調度算法實現及模擬框架研究［D］.大連：遼寧師范大學，2011.

［20］ 王永翔，王立德.多功能車輛總線周期掃描表的最優化設計［J］.鐵道學報，2009，31（6）：46－52.

［21］ Zi Xu，Xinming Wu.A new hybrid stochastic approximation algorithm［J］.Optimization Letters，2013，7（3）：5593－5606.

［22］ 江有福，吳偉志.動態拓撲網絡最短路徑啟發式算法［J］.計算機應用與軟件，2008，25（5）：36－44.

［23］ Schmitt，Lothar M.Theory of genetic algorithm［J］.Theoretical Computer Science，2001，259（1）：51－61.

［24］ Wang Yan，Shan Xin－xin，Sun Yan－ming.Study on the application of genetic algorithms in the optimization of wireless network［J］.Procedia Engineering，2011，16：181－231.

［25］ 樊春天.基于經典優化算法的混合遺傳算法的研究與應用［D］.合肥：安徽理工大學，2013.

［26］ G Vivó－Truyols，J R Torres－Lapasió，A Garrido－Frenich，et al.A hybrid genetic algorithm with local search［J］.Chemometrics and Intelligent Laboratory Systems，2001，59（1）：107－120.

［27］ 朱琴躍，謝偉達，譚喜堂.MVB協議一致性測試研究與實現［J］.鐵道學報，2007，29（4）：115－120.

［28］ 時百勝.基于概念的折半查找算法［J］.計算機科學，2009，36（6）：235－158.

［29］ 王靜，譚祥爽，宋現鋒，等.一種GPS航跡線的自適應折半查找化簡算法［J］.西安電子科技大學學報，2014，41（5）：176－182.

［30］ Hiroshi Fujiwara，Tobias Jacobs.On the Huffman and alphabetic tree problem with general cost functions［J］.Algorithmica，2014，69（3）：582－604.

［31］ 楊琳，王從慶，繆鵬，等.基于Huffman最優二叉樹支持向量機的艙音記錄器背景信號識別［J］.宇航學報，2011，32（6）：1428－1434.

［32］ 郭建光，張衛杰，楊健，等.基于廣義規范Huffman樹的高效編解碼算法［J］.清華大學學報：自然科學版，2009，49（1）：73－77.

［33］ Yih－Kai Lin，Shu－Chien Huang，Cheng－Hsing Yang.A fast algorithm for Huffman decoding based on a recursion Huffman tree［J］.The Journal of Systems ＆Software，2012，85（4）：974－980.