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

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

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

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

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

1 CAN總線仲裁機制

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

圖1 報文的數(shù)據(jù)幀結(jié)構(gòu)

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

實際上采用CSMA/CD非破壞優(yōu)先權(quán)逐位仲裁規(guī)則時，沖突的過程是優(yōu)先權(quán)小的幀逐位淘汰，而優(yōu)先權(quán)大的幀非破壞性地逐位勝出，優(yōu)先權(quán)大的幀先占用總線得到發(fā)送。

2 分級決策動態(tài)均衡調(diào)度算法

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

第1級:消息傳輸緊急性的權(quán)值分配公式為

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

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

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

式中:Di為節(jié)點i的截止期;tstart為節(jié)點消息需要傳輸時的起始時間;tFrame為單幀傳輸?shù)钠骄鶗r間。

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

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

表1 不同截止期消息的優(yōu)先權(quán)映射關(guān)系

第3級:同一類型且具有相同相對截止期消息的權(quán)值動態(tài)分配［8］。

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

表2 各節(jié)點ID標志符動態(tài)改變過程

3 算法的實現(xiàn)

3．1 協(xié)議制定

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

圖2 改進的CAN協(xié)議擴展幀格式

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

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

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

表3 實際車輛不同截止期消息的優(yōu)先權(quán)值分配

對于非實時消息，可以規(guī)定其截止期映射的優(yōu)先權(quán)值為111，即取其權(quán)值為最大值7。

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

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

3．2 算法實現(xiàn)流程

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

4 試驗驗證

4．1 試驗平臺

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

圖3“分級決策動態(tài)均衡”算法實現(xiàn)流程

圖4 試驗平臺框架

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

4．2 通信速率測試

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

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

4．3 算法驗證對比

4．3．1 原有“固定優(yōu)先級”算法驗證

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

圖6 靜態(tài)優(yōu)先級上位機接收200個消息記錄界面

圖7 靜態(tài)優(yōu)先級CAN總線競爭時延

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

4．3．2 “均衡調(diào)度”算法驗證

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

圖8 動態(tài)優(yōu)先級上位機接收200個消息記錄界面

圖9 動態(tài)優(yōu)先級CAN總線競爭時延

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

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

4．3．3 “分級決策動態(tài)均衡”混合調(diào)度算法驗證

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

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

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

5 結(jié)論

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

［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］ 宋小慶．軍用車輛綜合電子系統(tǒng)總線網(wǎng)絡［M］．北京:國防工業(yè)出版社，2010:120-122．

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

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

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