一種裝甲車輛CAN總線混合調(diào)度算法

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

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

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

目前，國內(nèi)外學(xué)者在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)度效率較低，且當(dāng)高優(yōu)先級報文傳輸增多時，低優(yōu)先級報文由于獲取不了總線使用權(quán)而長時間處于等待狀態(tài)。TTCAN雖然建立了窗口機(jī)制，根據(jù)調(diào)度表決定報文發(fā)送順序，解決了節(jié)點(diǎn)不公平競爭問題，但存在調(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)絡(luò)負(fù)載較大時，調(diào)度過程復(fù)雜、調(diào)度效率較低;而EDF算法報文的平均等待時延較長。

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

1 CAN總線仲裁機(jī)制

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

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

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

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

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

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

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

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

式中:Di為節(jié)點(diǎn)i的截止期;tstart為節(jié)點(diǎn)消息需要傳輸時的起始時間;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)度算法進(jìn)行消息權(quán)值分配。如當(dāng)有5個初始優(yōu)先級分別為50、49、48、47、46的節(jié)點(diǎn)都向總線發(fā)送消息時，若按照動態(tài)均衡調(diào)度算法在消息競爭過程中將各節(jié)點(diǎn)ID動態(tài)改變，便可將各節(jié)點(diǎn)消息公平有效地發(fā)送出去，各節(jié)點(diǎn)ID標(biāo)志符動態(tài)改變過程如表2所示。

表2 各節(jié)點(diǎn)ID標(biāo)志符動態(tài)改變過程

3 算法的實(shí)現(xiàn)

3．1 協(xié)議制定

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

圖2 改進(jìn)的CAN協(xié)議擴(kuò)展幀格式

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

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

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

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

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

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

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

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

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

4 試驗(yàn)驗(yàn)證

4．1 試驗(yàn)平臺

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

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

圖4 試驗(yàn)平臺框架

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

4．2 通信速率測試

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

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

4．3 算法驗(yàn)證對比

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)論

當(dāng)前裝甲車輛綜合電子系統(tǒng)消息的緊急程度、重要程度各不相同，在實(shí)車中的實(shí)時性要求也不同。本文針對某型裝甲車輛的實(shí)時性要求，對CAN協(xié)議進(jìn)行3層劃分，提出了“分級決策動態(tài)均衡”的混合調(diào)度算法，并通過試驗(yàn)驗(yàn)證了算法的可行性，對實(shí)際裝甲車輛綜合電子系統(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)絡(luò)［M］．北京:國防工業(yè)出版社，2010:120-122．

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

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

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