一種裝甲車輛CAN總線混合調度算法

宋小慶，陳永星，趙梓旭，張 健，朱昀炤

(裝甲兵工程學院控制工程系，北京100072)

CAN總線作為軍用總線廣泛應用于裝甲車輛在數字化戰場信息的傳輸，其采用CSMA/CD非破壞性仲裁機制按照優先級大小進行信息傳輸。然而在總線負載率較高、高優先級報文占用總線時，這種機制使得系統中優先級較低的報文一直處于監聽總線狀態而不能獲取總線使用權，有時甚至可能因為多次發送不出去產生發送錯誤而自動退出總線，導致總線實時性較差。當有緊急消息需要傳輸時，可能由于該消息所在節點優先級較低，而延緩甚至退出緊急消息的發送，對車輛作戰性能發揮有很大的影響。因此，對CAN總線網絡上節點消息進行合理分類與調度，使各類信息實時、公平、有效地傳輸，對裝甲車輛總線信息的傳輸非常重要。

目前，國內外學者在CAN總線非破壞仲裁的基礎上，提出了很多CAN總線調度算法，總體上分為靜態調度算法和動態調度算法2類。靜態調度算法大致有3類:基于優先級的比率單調算法［1］、基于截止期的截止期單調調度算法［2］、基于時間調度表的TTCAN調度算法等。前2種算法對非周期性報文的調度效率較低，且當高優先級報文傳輸增多時，低優先級報文由于獲取不了總線使用權而長時間處于等待狀態。TTCAN雖然建立了窗口機制，根據調度表決定報文發送順序，解決了節點不公平競爭問題，但存在調度表構建時間花銷大、與CAN格式不兼容、不允許出錯重發以及誤幀率較大等方面的不足。動態調度算法大致有2類:最小松弛優先(Least Laxity First，LLF)算法［3］和最早截止期優先(Earliest Deadline First，EDF)算法［4］等。LLF 算法在網絡負載較大時，調度過程復雜、調度效率較低;而EDF算法報文的平均等待時延較長。

本文結合當前裝甲車輛網絡消息特點，按照優先級分層設計、截止期實時調度、同級別公平競爭的原則，提出了一種“分級決策動態均衡”的總線調度算法，改進了當前總線調度方案的實時性與網絡利用率等方面的不足。

1 CAN總線仲裁機制

CAN總線網絡的仲裁機制為CSMA/CD非破壞性仲裁技術［5］。CAN總線的位中，邏輯“0”被稱作顯性位，邏輯“1”被稱作隱性位。在總線上，當顯性位和隱性位進行比較時，隱性位在競爭中退出。CAN總線數據幀結構如圖1所示。

圖1 報文的數據幀結構

SOF由一個顯性位構成，標志著幀的開始。所有要發送幀的節點必須同步于首先發送報文節點的幀起始前沿;仲裁場由標志符和RTR位構成，仲裁場的標志符可用于總線仲裁(即優先級高低判斷)，RTR位用于判斷此幀是遠程幀還是數據幀。

實際上采用CSMA/CD非破壞優先權逐位仲裁規則時，沖突的過程是優先權小的幀逐位淘汰，而優先權大的幀非破壞性地逐位勝出，優先權大的幀先占用總線得到發送。

2 分級決策動態均衡調度算法

目前關于CAN總線調度算法的改進，基本上都是局限于周期型消息的處理，而在實際裝甲車輛上有很多報警、故障等突發消息，同類消息中不同周期也對應不同的重要程度，現有算法不能很好地處理這些消息。因此，本文采用均衡調度［6］與最早截止期調度［7］相結合的“分級決策動態均衡”的混合調度算法，按照“分層處理”原則對總線傳輸消息種類進行了劃分，從發送需求及消息重要程度方面對信息進行權值分配，具體分級如下。

第1級:消息傳輸緊急性的權值分配公式為

式中:Wi為信息的緊急性，i為緊急性權值所占的位數，Wi值越小，代表消息的緊急程度越強。

第2級:同一類型但具有不同相對截止期消息的權值分配。

由于節點發送消息緊急程度、重要程度與截止期有關，節點截止期時限長度越小，節點消息越需要發送出去，對于同一類別而截止期不同的消息，可以按照截止期Di由小到大的順序映射出節點優先級的大小，從而確定節點優先級，節點i的碰撞次數Ni為

式中:Di為節點i的截止期;tstart為節點消息需要傳輸時的起始時間;tFrame為單幀傳輸的平均時間。

對 Ni取整，記為 ni=［Ni］，則有

ni由小到大排列，n→f(i)可得到不同截止期消息的優先權映射關系，如表1所示。

表1 不同截止期消息的優先權映射關系

第3級:同一類型且具有相同相對截止期消息的權值動態分配［8］。

該級利用均衡調度算法進行消息權值分配。如當有5個初始優先級分別為50、49、48、47、46的節點都向總線發送消息時，若按照動態均衡調度算法在消息競爭過程中將各節點ID動態改變，便可將各節點消息公平有效地發送出去，各節點ID標志符動態改變過程如表2所示。

表2 各節點ID標志符動態改變過程

3 算法的實現

3．1 協議制定

以CAN 2．0B擴展幀格式為例，對裝甲車輛CAN總線ID標志符進行重新定義，解決消息傳輸實時性、帶寬分配不均帶來的網絡利用率不高等問題。具體定義如圖2所示。

圖2 改進的CAN協議擴展幀格式

根據某型裝甲車輛消息種類及不同消息的不同截止期，對應分級決策動態均衡算法，可對協議進行如下劃分。

1)取消息緊急度標志符為p=2來劃分消息種類，實際定義為:“00”代表嚴重故障類等緊急消息;“01”代表控制類等實時消息;“10”代表命令、節點狀態類等實時消息;“11”代表圖像、聲音等非實時消息。其他車型可根據實際消息類型對p取值。

2)實際裝甲車輛各類消息的相對截止期有10，50，100，200，1 000 ms，共計 5 種截止期，故取截止期分級標志符為m=3對不同截止期消息的優先權值進行分配，具體優先權映射關系如表3所示。

表3 實際車輛不同截止期消息的優先權值分配

對于非實時消息，可以規定其截止期映射的優先權值為111，即取其權值為最大值7。

3)實車上同一類型、同一截止期最多有50個消息需要傳輸，取動態均衡算法標志符q=6來對相同截止周期消息的優先級進行動態公平分配，具體權值可按表2進行分配。

4)報文標志符取18位，可根據實際需要定義。

3．2 算法實現流程

本文提出的車輛總線信息調度方案采用均衡調度、最早截止期調度2種算法相結合的“分級決策動態均衡”的混合調度算法，既保證了系統傳輸信息的實時性，又合理分配了網絡帶寬，還減小了系統的開銷成本，其算法實現流程如圖3所示。

4 試驗驗證

4．1 試驗平臺

本試驗平臺由2部分組成:1)節點消息發送終端(共5個)，用于發送各類消息;2)上位機信息接收端，用于接收各節點終端發送的消息，同時進行相關性能參數指標的統計，其組成框架如圖4所示。

圖3“分級決策動態均衡”算法實現流程

圖4 試驗平臺框架

本試驗通信平臺采用CAN通信總線進行數據傳輸，設置通信速率為10 kbit/s，從節點可設置發送消息個數，上位機接收端有5個信息接收儀表顯示端，可統計計算節點在總線上的傳輸時延，通過對比不同節點的傳輸時延，即可驗證“分級決策動態均衡”混合調度算法的有效性。

4．2 通信速率測試

圖5為數據傳輸過程中示波器捕獲的CAN總線信號波形。由圖5可以觀測出總線數據傳輸1 bit所用時間為100μs，即總線通信速率為10 kbit/s，與設定值一致。

圖5 示波器捕獲的CAN總線信號波形

4．3 算法驗證對比

4．3．1 原有“固定優先級”算法驗證

設定每個節點分別發送緊急程度與截止期均相同的消息組，每個消息組消息個數相同且每個消息數據字長為2B，上位機接收到不同節點的消息后，對傳輸時延進行統計計算。圖6為每個節點發送200個消息的上位機接收記錄界面，同理，設定每個節點分別發送50、100、400個消息進行測試并記錄，繪出不同節點發送不同消息組的傳輸時延對比曲線，如圖7所示。

圖6 靜態優先級上位機接收200個消息記錄界面

圖7 靜態優先級CAN總線競爭時延

由圖7可知:由于CAN總線CSMA/CD仲裁機制的影響，采用靜態優先級算法，不管發送消息多少，優先級最高的節點1的消息優先發送，所用時間最短，而優先級最低的節點5的消息最后發送，所用時間最長，節點之間消息發送不公平。只是隨著總線負載增加，各節點發送消息傳輸時延在同步增加。

4．3．2 “均衡調度”算法驗證

采用動態優先級算法時，各節點發送消息前提條件與靜態優先級算法相同。圖8為每個節點發送200個消息的上位機接收記錄界面，不同節點發送50、100、200、400個消息的傳輸時延對比如圖9所示。

圖8 動態優先級上位機接收200個消息記錄界面

圖9 動態優先級CAN總線競爭時延

由圖9可知:采用動態優先級算法，各節點在發送緊急程度與截止期均相同的消息組時，由于消息ID標志符處于動態改變的過程中，即優先級由高到低循環發生變化，故各節點在總線的傳輸時延基本相同。

因此，相對靜態優先級而言，采用動態優先級算法，各節點消息公平傳輸，且優先級較低的節點傳輸時延明顯減少，提高了節點傳輸消息的公平性。

4．3．3 “分級決策動態均衡”混合調度算法驗證

當各節點發送消息的相對截止期不同時，可利用分級決策動態均衡混合調度算法進行消息的傳輸。設定各節點分別傳輸100個2B數據字的消息，假設節點2、5傳輸消息的截止期相同，記為D1，節點1、3、4傳輸消息的截止期相同，記為D2，且D1＜D2。分別采用3種算法時各節點傳輸100個消息的時延對比如表4所示。

由表4可知:傳輸消息截止期不同時，采用固定優先級算法時，節點消息依次傳輸，節點5所用時延可長至5．89 s，節點4、5優先級較低，當有緊急消息傳輸時，會導致消息不能及時傳輸，實時性不高;采用均衡調度算法時，各個節點消息的傳輸時延約為3．5 s，幾乎同時傳輸完畢，節點4、5消息的優先級得到提高，各節點消息公平傳輸;而采用混合調度算法時，由于節點2、5截止期相同且較短，優先進行消息的傳輸，兩節點內部采用動態均衡算法傳輸，所用時間為1．8 s左右，節點1、3、4截止期相同但相對較長，其內部同樣采用動態均衡算法，用時4．2 s左右，這樣既保證了截止期較小消息的優先傳送，又保證了消息傳輸的公平性。通過分析對比可知:相對固定優先級算法和均衡調度算法而言，分級決策動態均衡調度算法提高了節點通信網絡信息的傳輸效率，使得各類消息公平有序地傳輸。

表4 3種算法傳輸消息時延對比

5 結論

當前裝甲車輛綜合電子系統消息的緊急程度、重要程度各不相同，在實車中的實時性要求也不同。本文針對某型裝甲車輛的實時性要求，對CAN協議進行3層劃分，提出了“分級決策動態均衡”的混合調度算法，并通過試驗驗證了算法的可行性，對實際裝甲車輛綜合電子系統信息調度算法及總線性能研究具有重要意義。

［1］ Liu C L，Layland J W．Scheduling Algorithms for Multiprogramming in a Hard-real-time Environment［J］．Journal of ACM，1973，20(1):174-189．

［2］ Zuberi K M，Shin K G．Design and Implementation of Efficient Message Scheduling for Controller Area Network［J］．IEEE Transactions on Computers，2000，49(2):182-188．

［3］ George R，Kanayama Y．A Rate-monotonic Scheduler for the Real-time Control of Autonomous Robots［C］∥IEEE International Conference on Robotics and Automation．New York，USA:IEEE，1996:2804-2809．

［4］ Pedreiras P，Almeida L．EDF Message Scheduling on Controller Area Network［J］．Computing ＆ Control Engineering Journal，2002，13(4):163-170．

［5］ 宋小慶．軍用車輛綜合電子系統總線網絡［M］．北京:國防工業出版社，2010:120-122．

［6］ 劉向明，方建安．CAN總線網絡的實時性研究和改進［J］．現代電子技術，2011，34(22):46-49．

［7］ 諶介人，彭軍，吳敏，等．CAN總線中EDF調度算法的研究與改進［J］．計算機測量與控制，2008，18(16):1678-1681．

［8］ 袁遠，李紅信．CAN網絡實時性分析及改進［J］．電子設計工程，2010，18(6):110-112．