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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

對(duì) Ni取整，記為 ni=［Ni］，則有

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

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

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

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

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

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

3．1 協(xié)議制定

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4．2 通信速率測(cè)試

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

圖5 示波器捕獲的CAN總線信號(hào)波形

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

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

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

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

圖7 靜態(tài)優(yōu)先級(jí)CAN總線競(jìng)爭(zhēng)時(shí)延

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

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

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

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

圖9 動(dòng)態(tài)優(yōu)先級(jí)CAN總線競(jìng)爭(zhēng)時(shí)延

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

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

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

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

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

表4 3種算法傳輸消息時(shí)延對(duì)比

5 結(jié)論

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

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

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

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