郝 剛

（煤炭科學(xué)研究總院沈陽研究院，沈陽 113001）

1 引言

CAN（Controller Area Network）總線因其低成本、抗干擾等優(yōu)點(diǎn)已廣泛應(yīng)用于工業(yè)自動(dòng)化領(lǐng)域，國內(nèi)2005年開始將CAN應(yīng)用于刨煤機(jī)組監(jiān)控網(wǎng)絡(luò)，當(dāng)前采用的固定優(yōu)先級(jí)調(diào)度機(jī)制存在傳輸不可預(yù)知、低優(yōu)先級(jí)信息易死鎖等不足，為了保證信息實(shí)時(shí)性，CAN實(shí)時(shí)系統(tǒng)中總線利用率只能達(dá)到30%左右。隨著CAN應(yīng)用的不斷加深及刨煤機(jī)組分布式實(shí)時(shí)系統(tǒng)中相互連接器件的日漸增多，系統(tǒng)要交換的數(shù)據(jù)逐步增加，現(xiàn)有的帶寬資源越顯有限。動(dòng)態(tài)優(yōu)先級(jí)實(shí)時(shí)調(diào)度策略如LLF、EDF（Earliest Deadline First），相比靜態(tài)調(diào)度具有較高的資源利用率，保證時(shí)間最緊迫的任務(wù)贏得資源，可提高低優(yōu)先級(jí)信息網(wǎng)絡(luò)競(jìng)爭(zhēng)能力，使得網(wǎng)絡(luò)實(shí)時(shí)信息有較好的時(shí)間響應(yīng)特性[1]。目前，基于CAN的動(dòng)態(tài)調(diào)度已成為應(yīng)用研究中的熱點(diǎn)[1-6]。

在CAN總線中實(shí)施基于信息時(shí)間約束的動(dòng)態(tài)優(yōu)先級(jí)調(diào)度面臨以下困難：①總線消息時(shí)間約束差別較大，且隨著時(shí)間越來越大，需要越來越多的CAN標(biāo)識(shí)符位來編碼信息的截止期，難以用有限的標(biāo)識(shí)符實(shí)現(xiàn)；②需要網(wǎng)絡(luò)中節(jié)點(diǎn)之間有嚴(yán)格的時(shí)間同步機(jī)制。為解決以上問題，文獻(xiàn)[2,3]采用主節(jié)點(diǎn)調(diào)度形式來實(shí)現(xiàn)動(dòng)態(tài)調(diào)度。文獻(xiàn)[5,6]提出的EDF調(diào)度，在保證時(shí)間同步的基礎(chǔ)上，將時(shí)間分為若干的小段時(shí)間域，根據(jù)消息截止期所落的域不同來決定優(yōu)先級(jí)，每隔一段時(shí)間（如文獻(xiàn)[5]中1ms）更新消息優(yōu)先級(jí)。

本文以信息的松弛時(shí)間（除去自身傳輸用時(shí)之外距離信息截止期限的時(shí)間）為參數(shù)，通過將信息的松弛量化為可傳輸幀數(shù)，用有限的CAN幀標(biāo)識(shí)符位實(shí)現(xiàn)信息的時(shí)間約束編碼，信息參與總線仲裁時(shí)更新其松弛優(yōu)先級(jí)，充分利用了CAN總線固有的仲裁機(jī)制。

2 CAN及LLF調(diào)度算法

2.1 LLF調(diào)度中CAN信息優(yōu)先級(jí)規(guī)劃

CAN有兩種不同的幀格式，分別為含有11位標(biāo)識(shí)符的標(biāo)準(zhǔn)幀和含有29位標(biāo)識(shí)符的擴(kuò)展幀，本文采用擴(kuò)展幀格式。

記信息m的優(yōu)先級(jí)為PmR，各個(gè)信號(hào)的優(yōu)先級(jí)由控制優(yōu)先級(jí)Pm-C、松弛優(yōu)先級(jí)Pm-S和截止期單調(diào)（DM）優(yōu)先級(jí)Pm-DM共同決定，如圖1所示。

圖1 LLF調(diào)度中優(yōu)先級(jí)規(guī)劃

CAN總線采用“線與”邏輯來仲裁信息競(jìng)爭(zhēng)，所以信息標(biāo)識(shí)符越小則優(yōu)先級(jí)越高，總線仲裁從幀起始位開始逐位向后對(duì)比進(jìn)行仲裁?？刂苾?yōu)先級(jí)為0、松弛優(yōu)先級(jí)越小的信息優(yōu)先級(jí)越高，松弛優(yōu)先級(jí)相同時(shí)則根據(jù)DM固定優(yōu)先級(jí)仲裁。

LLF調(diào)度的核心是動(dòng)態(tài)更新松弛優(yōu)先級(jí)，為實(shí)現(xiàn)動(dòng)態(tài)優(yōu)先級(jí)調(diào)度，將信息優(yōu)先級(jí)規(guī)劃分4個(gè)步驟：

（1）考慮松弛優(yōu)先級(jí)的動(dòng)態(tài)提升，在29位標(biāo)識(shí)符中除Pm-C位之外的28位中，將前WS位規(guī)劃為松弛優(yōu)先級(jí)域，松弛優(yōu)先級(jí)用來動(dòng)態(tài)記錄信息的剩余松弛，到達(dá)其截止期前還可以經(jīng)歷多少次仲裁；將WDM位規(guī)劃為DM優(yōu)先級(jí)域，DM優(yōu)先級(jí)按信息截止期分配，截止期越小優(yōu)先級(jí)越高，各信息具有總線上唯一的DM優(yōu)先級(jí)。DM優(yōu)先級(jí)屬于固定優(yōu)先級(jí)，用于接收濾波以及當(dāng)兩信息松弛優(yōu)先級(jí)相同時(shí)予以區(qū)分。仲裁域結(jié)構(gòu)規(guī)劃如圖2所示。

圖2 LLF調(diào)度中CAN幀仲裁域結(jié)構(gòu)

（2）確定用于將信息松弛量化為剩余仲裁數(shù)的量化幀的大小?？紤]位填充及傳輸過程中附加的3位幀間空間，其大小應(yīng)滿足公式（1）[7]。

q為量化幀的大小，tCm為系統(tǒng)所有信息的總線最長傳輸用時(shí)，fbaud為波特率，dm為擴(kuò)展信息幀數(shù)據(jù)域的字節(jié)數(shù)。

（3）確定松弛優(yōu)先級(jí)域的位數(shù)WS和DM優(yōu)先級(jí)域的位數(shù)WDM。

其中，Q為所調(diào)度信息的個(gè)數(shù)。

（4）初始化優(yōu)先級(jí)域

當(dāng)松弛優(yōu)先級(jí)位數(shù)能夠滿足信息松弛編碼要求時(shí)，置控制優(yōu)先級(jí)Pm-C＝0，否則Pm-C＝1，通過將控制優(yōu)先級(jí)置1將不能編碼的消息掛起，隨著信息的松弛不斷減少，當(dāng)滿足編碼要求時(shí)，再置Pm-C＝0，即

其中，tDm為信息m的相對(duì)截止期，即當(dāng)前時(shí)刻到信息截止期之間的時(shí)間，tJm為軟件的抖動(dòng)時(shí)間。

2.2 基于事件觸發(fā)的LLF動(dòng)態(tài)調(diào)度算法

LLF算法思想在于為每個(gè)信號(hào)引入隨總線仲裁動(dòng)態(tài)更新其松弛優(yōu)先級(jí)概念，每次信息競(jìng)爭(zhēng)總線失掉仲裁，松弛優(yōu)先級(jí)會(huì)動(dòng)態(tài)提升，本文定義每次提升步長為1，基于事件觸發(fā)的LLF算法步驟如下：

（1）選擇波特率。

（2）信息產(chǎn)生，初始化信息優(yōu)先級(jí)Pm。

（3）Pm＝concat( Pm-C,Pm-S,Pm-DM)。

（4）監(jiān)聽總線，總線空閑則申請(qǐng)發(fā)送。

（5）if 贏得總線仲裁。

開始傳輸數(shù)據(jù)，完成后返回第二步；

else if Pm-DM＞1

Pm-DM＝Pm-DM-1，返回第三步。

（6）結(jié)束。

2.3 LLF調(diào)度算法的可調(diào)度性分析

根據(jù)上述算法原理進(jìn)行信息傳輸?shù)目烧{(diào)度性分析。當(dāng)所有信息同時(shí)競(jìng)爭(zhēng)總線是總線的最壞傳輸條件，信息m在最壞傳輸條件下的傳輸時(shí)間稱為最糟糕響應(yīng)時(shí)間tRm。信息m的傳輸時(shí)間特性滿足式（6）、（7），則該信息可調(diào)度

U為總線利用率，Ti為信息的傳輸周期（隨機(jī)信息為最小時(shí)間間隔），tWm為信息m從申請(qǐng)發(fā)送到獲得總線使用權(quán)所等待的時(shí)間，TDm為信息m的截止期，τbit為總線傳輸一位數(shù)據(jù)占用時(shí)間。

3 實(shí)例分析

3.1 自動(dòng)刨煤機(jī)組監(jiān)控系統(tǒng)

自動(dòng)刨煤機(jī)組監(jiān)控系統(tǒng)由刨煤系統(tǒng)、輸送系統(tǒng)、破碎系統(tǒng)、支護(hù)系統(tǒng)、冷卻與除塵系統(tǒng)、中央控制室、控制系統(tǒng)、視頻監(jiān)控系統(tǒng)、和設(shè)備列車組成，各子系統(tǒng)之間通過CAN總線連接組建網(wǎng)絡(luò)。

本文以機(jī)組監(jiān)控系統(tǒng)中33個(gè)實(shí)時(shí)信號(hào)a1～a33為調(diào)度對(duì)象，每個(gè)信號(hào)攜帶2個(gè)字節(jié)控制數(shù)據(jù)，a1～a5、a6～a30、a31～a33周期分別為100ms、200ms、300ms 100ms，為了滿足實(shí)時(shí)性要求，網(wǎng)絡(luò)信息的傳輸截止期限應(yīng)不大于信息周期，取刨煤機(jī)組CAN網(wǎng)絡(luò)位速率為125kbps。

為了體現(xiàn)采用固定優(yōu)先級(jí)調(diào)度時(shí)，新產(chǎn)生的高優(yōu)先級(jí)信息（松弛較大）將阻礙排隊(duì)等待的低優(yōu)先級(jí)信息（臨近其截止期、松弛很?。┑那闆r，本文做以下假設(shè)：a1～a5、a8～a22、a31～a33由t=0開始周期發(fā)送，a6～a7、a23～a30在t=70m s時(shí)開始發(fā)送。

3.2 調(diào)度算法在刨煤機(jī)組監(jiān)控系統(tǒng)中的應(yīng)用

采用DM固定優(yōu)先級(jí)調(diào)度方案和本文提出的LLF動(dòng)態(tài)優(yōu)先級(jí)調(diào)度方案對(duì)33個(gè)信息一個(gè)周期循環(huán)600ms共111個(gè)信息進(jìn)行調(diào)度設(shè)計(jì)。

（1）基于DM算法的信息調(diào)度設(shè)計(jì)

傳統(tǒng)設(shè)計(jì)通常采用DM截止期單調(diào)算法對(duì)CAN傳輸信息進(jìn)行優(yōu)先級(jí)分配P，任務(wù)以信息的截止期大小排序被賦予不同的固定優(yōu)先級(jí)。截止期越小的任務(wù)獲得的優(yōu)先級(jí)越高。采用DM調(diào)度方法的優(yōu)先級(jí)規(guī)劃結(jié)果如表1所示。

表1 自動(dòng)刨煤機(jī)組信息集DM及LLF調(diào)度設(shè)計(jì)

（2）基于LLF算法的信息調(diào)度設(shè)計(jì)

考慮現(xiàn)場(chǎng)因素取軟件抖動(dòng)tJm＝1ms，fbaud＝125kb/s，則q＝0.76ms，WDM＝6位，WS＝22位，信息松弛初始值為

需要松弛優(yōu)先級(jí)位數(shù)為8位，則可實(shí)現(xiàn)信息松弛編碼，即Pm-C＝0，LLF調(diào)度中優(yōu)先級(jí)規(guī)劃結(jié)果如表1所示。

3.3 刨煤機(jī)組監(jiān)控系統(tǒng)的網(wǎng)絡(luò)性能分析

為了對(duì)網(wǎng)絡(luò)的可調(diào)度性、資源效率進(jìn)行分析，本文采用以下總線特性參數(shù)：

（1）信息組丟失死限信息個(gè)數(shù)。

（2）總線利用率。

在總線信息參數(shù)不變的情況下，通過調(diào)節(jié)波特率來模擬總線利用率的變化，編程分別對(duì)DM、LLF算法進(jìn)行仿真，得到兩種算法調(diào)度下的CAN總線網(wǎng)絡(luò)性能分析結(jié)果如圖3所示。

由仿真知，DM調(diào)度下丟失死限的信息均為低優(yōu)先級(jí)信息。由圖3可見，同樣的負(fù)載條件下LLF調(diào)度丟失死限的信息個(gè)數(shù)明顯少于DM調(diào)度，LLF算法總線利用率比DM提高了24%。

圖3 刨煤機(jī)組信息集DM與LLF調(diào)度結(jié)果

4 結(jié)論

本文提出了基于事件觸發(fā)的LLF調(diào)度策略，不需要各節(jié)點(diǎn)附加的的時(shí)間同步機(jī)制，充分利用了CAN協(xié)議的非破壞性仲裁機(jī)制。對(duì)自動(dòng)刨煤機(jī)組控制信息調(diào)度結(jié)果表明：LLF算法可達(dá)到較高的總線利用率，有效解決了低優(yōu)先級(jí)信息的死鎖問題，兼顧了低優(yōu)先級(jí)信息的公平性。

[1] Giorgio C Buttazzo, “Rate monotonic vs EDF:judgment day,” Real-Time Systems, 2005,29(1):5-26.

[2] Margull U, Diederichs C, Margull U, et al, “An application based EDF scheduler for osek/vdx,”Proceedings of the conference on Design, automation and test in Europe, Munich, Germany, 2008:1045-1050.

[3] Pedreiras P, A lmeida L, “EDF message scheduling on controller area network,” Computing & Control Engineering Journal, 2002,13(4):163-170.

[4] Fuster S, Rodríguez F, Bonastre A, “Software based EDF Message Scheduling on CAN Networks,”Proceedings of the Second International Conference on Embedded Software and Systems, Washington DC,USA, 2005:450-455.

[5] K. M. Zuberi, K. G. Shin, “Non-preemptive scheduling of messages on controller area network for real-time control applications,” in proc.Real-Time Technology and Applications Symposium,1995:240-249.

[6] Natale M D. Scheduling the CAN bus with earliest deadline techniques. Proc of the 21st IEEE Real time System s Sym posium, Orlando, 2000: 259-268.

[7] Tindell K, Burns A, Wellings AJ, “Calculating controller area network (can) message response times,”Control Engineering Practice, 1995,3(8):1163-1169.

[8] 16 bit Single-Chip Micro cont rollers-C167CR User’s manual, V3.3. Siemens AG, Munich, 2005.