摘要：CAN總線以非破壞性仲裁方式，保證了高優(yōu)先級信息的優(yōu)先傳輸，大量報文的傳輸，增加了總線負載率的同時也導(dǎo)致出現(xiàn)了饑餓報文，各節(jié)點的實時性需要無法得到滿足。CAN總線調(diào)度算法通過優(yōu)化調(diào)整報文優(yōu)先級，保證了數(shù)據(jù)傳輸?shù)膶崟r性。因此，本文首先介紹了CAN總線的基本結(jié)構(gòu)，其次分析了導(dǎo)致饑餓報文出現(xiàn)的原因，最后總結(jié)了近年CAN總線調(diào)度算法的研究現(xiàn)狀。

關(guān)鍵詞：CAN總線；調(diào)度算法；饑餓報文；仲裁

一、引言

控制局域網(wǎng)絡(luò)（Controller Area Net， CAN）總線通信協(xié)議是一種國際標準化串行通信協(xié)議，能夠?qū)﹄姎庠O(shè)備實現(xiàn)分布式實時控制，道路車輛行業(yè)應(yīng)用最廣泛。廠商為了提高車輛的舒適度以及駕駛安全性，在車身上增加了大量的電控元件、傳感器和執(zhí)行器，眾多元器件的加入增加了CAN總線的負載率，影響了CAN總線數(shù)據(jù)傳輸?shù)膶崟r性。因此，合理的算法調(diào)度對于提高CAN總線工作效率和實時性至關(guān)重要。近年來，對CAN總線調(diào)度的算法研究較多，本文主要介紹近年來國內(nèi)外CAN總線調(diào)度算法的研究。

二、CAN總線

（一）CAN總線介紹

國際化標準組織提出了開放式通信系統(tǒng)互聯(lián)參考的OSI模型定義了7層模型，包括：物理層、數(shù)據(jù)鏈路層、網(wǎng)絡(luò)層、傳輸層、會話層、表示層、應(yīng)用層。在OSI模型中，CAN總線位于第1層物理層以及第2層數(shù)據(jù)鏈路層。

（二）CAN節(jié)點結(jié)構(gòu)

CAN節(jié)點包括CAN收發(fā)器和CAN控制器，收發(fā)器之間通過CAN_H 和CAN_L端口連接， CAN_H和CAN_L之間的電壓差值稱為差分電壓，從而形成數(shù)據(jù)傳輸?shù)牟罘中盘?。收發(fā)器和控制器之間通過TTL電平信號進行數(shù)據(jù)傳輸。

（三）饑餓報文

CAN總線報文數(shù)據(jù)通過標識符確定的優(yōu)先級參與總線競爭，重要數(shù)據(jù)采用高優(yōu)先級進行數(shù)據(jù)傳輸，非重要數(shù)據(jù)采用低優(yōu)先級進行數(shù)據(jù)傳輸，當總線中存在多個節(jié)點同時參與數(shù)據(jù)傳輸時，優(yōu)先級高的節(jié)點數(shù)據(jù)總是能夠順利傳輸，而優(yōu)先級低的節(jié)點數(shù)據(jù)在總線空閑的狀態(tài)下才能夠進行傳輸。因此，導(dǎo)致低優(yōu)先級節(jié)點長時間保持沉默，從而形成饑餓報文。饑餓報文會導(dǎo)致節(jié)點數(shù)據(jù)丟失，因此需要合適的算法進行調(diào)度，保證高優(yōu)先級報文不喪失其優(yōu)先傳輸權(quán)限的情況下，同時滿足低優(yōu)先級數(shù)據(jù)的傳輸。

三、CAN總線的調(diào)度算法

針對CAN總線優(yōu)先級調(diào)度的問題，學(xué)者們已經(jīng)進行了大量的研究。目前的CAN總線優(yōu)先級調(diào)度算法分為靜態(tài)調(diào)度算法、動態(tài)調(diào)度算法以及混合調(diào)度算法，其中靜態(tài)調(diào)度算法包括單調(diào)速率優(yōu)先級算法、截止期單調(diào)優(yōu)先級算法及分布式TTCAN算法等，動態(tài)調(diào)度算法包括最早截止期優(yōu)先級算法、最小松弛優(yōu)先級算法等，混合調(diào)度算法將靜態(tài)調(diào)度算法和動態(tài)調(diào)度算法進行組合，不同的算法在調(diào)度邏輯上也存在不同。

（一）靜態(tài)調(diào)度算法

靜態(tài)調(diào)度算法的邏輯是在CAN總線節(jié)點未開始工作前，根據(jù)節(jié)點信息重要性先定義好每個節(jié)點的優(yōu)先級。在CAN總線工作時，按照預(yù)先定義好的節(jié)點優(yōu)先級發(fā)送報文，這種工作方式雖然預(yù)配置簡單方便，但報文優(yōu)先級變動時修改繁瑣。

1.RM算法

RM算法是Liu等人提出的一種搶占式、針對周期性任務(wù)的算法[1]，根據(jù)周期進行優(yōu)先級分配，其截止期等于周期，周期越小，優(yōu)先級越高。對于周期性任務(wù)，在傳輸過程中有兩個參數(shù)：傳輸周期T和傳輸時間t。傳輸周期T即傳輸間隔，表示任務(wù)多久完成下一次傳輸，傳輸時間t表示傳輸一次任務(wù)需要的時間。

假設(shè)有兩組報文M1和M 2，M1的傳輸周期和傳輸時間分別為T1和t1，M 2的傳輸周期和傳輸時間分別為T2和t2，規(guī)定T1＜T2，且t1＜t2，同組報文傳輸時間小于傳輸周期，即報文必須在周期內(nèi)傳輸完成，執(zhí)行示意圖如圖1所示。

由于M1周期小，因此M1優(yōu)先級高于M 2，M1優(yōu)先傳輸，在t1時刻，M1的第一次報文M11傳輸完成，此時將M1在T1周期內(nèi)的剩余時間分配給M 2的第一次傳輸M 21，當M1周期再次到來時，由于優(yōu)先級的仲裁，M12將會搶占正在傳輸?shù)腗 21進行傳輸，直至M12傳輸完畢，系統(tǒng)將優(yōu)先級再次給到M 21進行傳輸。

RM算法只能對周期性任務(wù)進行調(diào)度，但在實際工況中，非周期性任務(wù)也大量存在，馮紅艷等人對RM算法進行優(yōu)化[2]，將系統(tǒng)中的非周期任務(wù)臨時轉(zhuǎn)化為周期性任務(wù)，通過預(yù)先約定的優(yōu)先級規(guī)則將其插入到就緒列隊相應(yīng)的位置，并且完成調(diào)度。

2.DM算法

DM算法是RM算法的進一步優(yōu)化，與RM不同的是，DM對于調(diào)度的任務(wù)均設(shè)置了確定的截止期D和周期T，且截止期D小于周期T，截止期越短，其調(diào)度任務(wù)優(yōu)先級越高，截止期越長，其調(diào)度任務(wù)優(yōu)先級越低，DM算法的任務(wù)在其截止期內(nèi)完成，能夠保證系統(tǒng)的實時性。

3.TTCAN算法

TTCAN是一種以系統(tǒng)矩陣為核心、基于時間觸發(fā)的CAN總線協(xié)議的高層協(xié)議。TTCAN的系統(tǒng)矩陣在任務(wù)調(diào)度開始前預(yù)定義完成，每個系統(tǒng)矩陣由多個周期組成，每個周期由多個時間窗口組成，時間窗口分為獨占時間窗口、自由時間窗口以及仲裁時間窗口。

由于TTCAN基于時間觸發(fā)，因此對于周期性任務(wù)傳輸具有極大優(yōu)勢，同時也能夠?qū)⒎侵芷谛匀蝿?wù)進行轉(zhuǎn)化傳輸，其任務(wù)調(diào)度是在系統(tǒng)矩陣內(nèi)進行預(yù)定義的，因此傳輸實時性高，但對于有變化節(jié)點的傳輸環(huán)境中，TTCAN的調(diào)度性能將變得極差，甚至需要重新進行任務(wù)調(diào)度定義。

（二）動態(tài)調(diào)度算法

動態(tài)調(diào)度算法的邏輯是在CAN總線節(jié)點工作時，根據(jù)預(yù)先定義好的任務(wù)調(diào)度邏輯，實時調(diào)整節(jié)點任務(wù)的優(yōu)先級，以此來避免CAN總線饑餓報文的出現(xiàn)，同時可以充分利用處理器的處理性能。

1.EDF算法

EDF算法是根據(jù)任務(wù)的截止期進行優(yōu)先級，其邏輯為截止期越早的任務(wù)，優(yōu)先級越高。在非搶占式任務(wù)調(diào)度中，只考慮任務(wù)截止期，對于在某一截止期內(nèi)到來的任務(wù)，直接按照截止期進行優(yōu)先級分配，截止期越小，任務(wù)優(yōu)先級越高。 在搶占式任務(wù)調(diào)度中，EDF算法雖然也是通過截止期判定優(yōu)先級，但EDF算法在周期性任務(wù)中需要根據(jù)截止期以及任務(wù)到達時間進行優(yōu)先級動態(tài)調(diào)整。如圖2所示，假設(shè)有兩組報文M1和M 2，傳輸時間分別為t1和t2，截止期分別為D1和D2，規(guī)定D1lt;D2，t1lt;t2，且同組報文傳輸時間小于截止期。當M1和M 2同時進行傳輸時，由于M1截止期早，因此M1的初始優(yōu)先級高，當M1的第一次任務(wù)M11傳輸完成后，M 2的第一次任務(wù)M 21開始傳輸。在M 21傳輸過程中，M1的第一次截止期結(jié)束，進入第二次截止期，但由于此時M 2的第一次截止期末結(jié)束，所以M 2的截止期早于M1的第二次截止期，因此此時M 2的優(yōu)先級高于M1的優(yōu)先級，M 2的傳輸任務(wù)不會被M1搶占，可以傳輸完成。

在EDF算法中，弱化了周期對任務(wù)調(diào)度的影響，同時由于動態(tài)優(yōu)先級的分配，理想狀態(tài)下任務(wù)調(diào)度率可以達到100%。因此，Livani對EDF的限定條件以及截止期進行了優(yōu)化[3]，諶教授等人針對任務(wù)實時性提出了基于指數(shù)分區(qū)的EDF算法[4]，王浩等人基于平均分區(qū)的EDF算法[5]，提出了基于雙冪函數(shù)分區(qū)的EDF算法，將任務(wù)分區(qū)為母區(qū)間和子區(qū)間，克服了平均分區(qū)算法下優(yōu)先級反轉(zhuǎn)現(xiàn)象頻出的問題，提高了系統(tǒng)的實時性。

2.LLF算法

LLF算法根據(jù)任務(wù)的重要性進行優(yōu)先級定義，以松弛度表示任務(wù)的重要性，松弛度越小的任務(wù)越重要，其優(yōu)先級越高，計算公式為：

松弛度S=傳輸周期T-傳輸時間ｔ-當前時間τ（1）

假如有兩組報文M1和M 2，傳輸周期分別為T1=20和T2=50，傳輸時間分別為t1=10和t2=25，根據(jù)公式（1），M1和M 2 的調(diào)度如圖3所示.

在τ=0時刻，報文傳輸任務(wù)開始，此時M1的松弛度S11=10，M 2的松弛度S21=25，由于初始M1的松弛度因此M1首先開始傳輸M11，在τ=10時刻，M11傳輸完成，此時M1的松弛度S12=20，M 2的第一次周期尚未結(jié)束，所以M 2的松弛度S21=15，S12gt;S21，開始執(zhí)行M 2的第一次任務(wù)M 21的傳輸，以此邏輯進行調(diào)度。

LLF算法通過優(yōu)先級搶占保證了傳輸?shù)膶崟r性，能夠在截止期前檢驗優(yōu)先級的時間沖突，但調(diào)度增大了系統(tǒng)開銷，同時在某些特殊情況下會產(chǎn)生抖動。

Hildebrandt J等人采用一種調(diào)度協(xié)處理器增強LLF算法[6]，消除了LLF算法在復(fù)雜調(diào)度時的抖動問題。Sabeghi M等人通過模糊調(diào)度[7]，將截止期作為模糊參數(shù)優(yōu)化了LLF算法，提高了CPU的利用率和搶占性能。

（三）混合調(diào)度算法

根據(jù)實時性，CAN總線消息可以劃分為三類：硬實時信息、軟實時信息和非實時信息?；旌险{(diào)度算法對于硬實時消息給予高優(yōu)先級，并設(shè)置為固定優(yōu)先級進行優(yōu)先調(diào)度，對于軟實時信息和非實時信息給予低優(yōu)先級，并設(shè)置為動態(tài)優(yōu)先級進行調(diào)度。

尹安東等人采用EDF和DM算法混合的調(diào)度策略[8]，設(shè)計了基于截止期公差遞增區(qū)分策略的混合調(diào)度算法，消除調(diào)度時的不確定性缺陷和低優(yōu)先級信號易鎖死現(xiàn)象。江杰等人提出一種結(jié)合TTCAN和動態(tài)晉升機制的調(diào)度算法[9]，解決了調(diào)度任務(wù)實時性和數(shù)據(jù)發(fā)送沖突的問題。

四、存在的問題與展望

隨著研究的不斷深入，CAN總線調(diào)度算法已經(jīng)在工業(yè)領(lǐng)域應(yīng)用。然而，調(diào)度算法解決饑餓報文的同時，也帶來了調(diào)度時時間開銷的問題。此外，隨著設(shè)備的智能化發(fā)展，需要面對的網(wǎng)絡(luò)安全問題也越來越多。目前，急需解決CAN總線調(diào)度算法存在的問題，在未來的研究中，需要考慮CAN總線調(diào)度算法的執(zhí)行效率、傳輸安全等問題的權(quán)重，使算法更加合理。

作者單位：李英松 劉劍奇 馮浩然 孫晶 李慧美

中機生產(chǎn)力促進中心有限公司

參考文獻

[1]Liu C L . Scheduling Algorithms for Multiprogramming in a Hard Real-Time Environment[J]. Journal of the ACM， 1973， 20.

[2]馮艷紅，張玉明，徐美華.實時調(diào)度算法分類研究[J].微型電腦應(yīng)用，2005，（07）：12-14+1.

[3]Livani M A， Kaiser J. EDF consensus on CAN bus access for dynamic real-time applications[C]//Parallel and Distributed Processing： 10 IPPS/SPDP'98 Workshops Held in Conjunction with the 12th International Parallel Processing Symposium and 9th Symposium on Parallel and Distributed Processing Orlando， Florida， USA， March 30–April 3， 1998 Proceedings 12. Springer Berlin Heidelberg， 1998： 1088-1097.

[4]諶介人，彭軍，吳敏，等.CAN總線中EDF調(diào)度算法的研究與改進[J].計算機測量與控制，2008，16（11）：4.

[5]王浩，張鳳登.CAN總線中改進的EDF調(diào)度算法可調(diào)度性分析[J].計算機測量與控制，2020.

[6]Hildebrandt J ，" Golatowski F ，" Timmermann D . Scheduling coprocessor for enhanced least-laxity-first scheduling in hard real-time systems[C]// Euromicro Conference on Real-time Systems. IEEE， 1999.

[7]Sabeghi M ，" Bertels K ，" Naghibzadeh M . Deadline vs. Laxity as a Decision Parameter in Fuzzy Real-Time Scheduling." 2006.

[8]尹安東，朱云驍，江昊，等.CAN總線混合調(diào)度算法在HEV控制系統(tǒng)中的應(yīng)用[J].電子測量與儀器學(xué)報，2012，26（01）：31-36.

[9]江杰，胡文江，范宇.一種“動靜結(jié)合”的CAN總線調(diào)度算法在汽車電子控制網(wǎng)絡(luò)中的研究與應(yīng)用[J].電子技術(shù)應(yīng)用，2007，（06）：127-128.