簡 毅，魏 磊，楊亞聯(lián)，劉其鑫

（重慶大學(xué) 機械傳動國家重點實驗室，重慶 400030）

基于截止期價值度優(yōu)先的CAN消息實時調(diào)度算法*

簡 毅，魏 磊，楊亞聯(lián)，劉其鑫

（重慶大學(xué) 機械傳動國家重點實驗室，重慶 400030）

為了保證CAN總線網(wǎng)絡(luò)中實時性消息的截止期，同時減小緊迫性消息的傳輸延遲，綜合考慮了CAN網(wǎng)絡(luò)中實時消息的截止期和價值度兩個參數(shù)，提出了截止期-價值度優(yōu)先（Deadline-Value First）實時調(diào)度算法，簡稱DVF算法。給出了算法遵循原則和設(shè)計過程，對截止期因素進行分段線性處理的方法，使得算法在保證消息截止期的前提下盡量讓關(guān)鍵性消息優(yōu)先發(fā)送。以EDF算法和HVF（higest value first）算法為基準(zhǔn)，從關(guān)鍵消息的相對延遲、丟幀率和丟失價值率這三個方面對DVF算法進行性能分析，實驗表明DVF算法相比于EDF算法和HVF算法有很大改善。

CAN總線網(wǎng)絡(luò)；截止期；價值度丟失率；丟幀率；相對傳輸延遲

0 引言

CAN總線在混合動力汽車、船舶、工業(yè)自動化等領(lǐng)域得到廣泛的應(yīng)用。作為實時控制網(wǎng)絡(luò)，我們總是期望CAN網(wǎng)絡(luò)中緊迫性程度高的消息能盡可能快的傳輸?shù)侥繕?biāo)設(shè)備上，而對于其他實時周期性消息應(yīng)該能夠在截止期之前完成發(fā)送。CAN網(wǎng)絡(luò)為多主網(wǎng)絡(luò)，消息幀采用基于標(biāo)識符仲裁的方式競爭總線，標(biāo)識符越小的消息優(yōu)先級就會越高，能夠優(yōu)先發(fā)送。在網(wǎng)絡(luò)負(fù)載率較高的情況下總線上消息的碰撞頻率增加，優(yōu)先級低的消息將因競爭總線失敗而被延遲發(fā)送，甚至錯過其截止期［1］。因而CAN總線網(wǎng)絡(luò)消息調(diào)度不僅要考慮緊迫性消息的發(fā)送延遲，還要保證實時性消息在截止期之前完成發(fā)送。采用怎樣的調(diào)度策略，提高消息的調(diào)度效率，是CAN總線網(wǎng)絡(luò)需要考慮的核心問題。

時間觸發(fā)CAN協(xié)議（TTCAN協(xié)議）作為靜態(tài)調(diào)度算法，對周期性消息的調(diào)度能起到很好的效果，在網(wǎng)絡(luò)中節(jié)點數(shù)目改變時此算法顯得不夠靈活，而且負(fù)載率增加時，該算法調(diào)度的非周期性消息的延遲明顯增加［2-3］，這對偶發(fā)性消息的實時發(fā)送是相當(dāng)不利的。文獻［4］證明了動態(tài)調(diào)度算法比靜態(tài)調(diào)度算法具有較高的可調(diào)度性。文獻［5］證明了EDF（earliest deadline first）算法可以在負(fù)載率為100%的情況下實現(xiàn)可靠的調(diào)度。文獻［6］表明EDF算法在非過載情況下的最優(yōu)性。文獻［7］對CAN標(biāo)識符的截止期采用指數(shù)方式編碼，提高了可調(diào)度性，其實這種編碼方式使得越靠近截止期的消息，其優(yōu)先級提升的越快。但是EDF算法對消息幀優(yōu)先級的衡量標(biāo)準(zhǔn)僅為截止期這一個參數(shù)，在一個復(fù)雜的CAN網(wǎng)絡(luò)系統(tǒng)中截止期最小的消息未必是緊迫性最高的消息。CAN網(wǎng)絡(luò)中存在系統(tǒng)負(fù)載率瞬間升高甚至過載的情況，而且對于一個高負(fù)載率的CAN網(wǎng)絡(luò)而言消息的平均延遲增加，這些情況下必須確保關(guān)鍵性程度高的消息能夠優(yōu)先發(fā)送；因而，應(yīng)該把消息幀的關(guān)鍵性程度作為度量消息優(yōu)先級的參數(shù)之一。

本文提出了截止期-價值度優(yōu)先調(diào)度算法（Deadline-Value first），簡稱DVF算法。實驗表明，該算法綜合性能優(yōu)于EDF算法和HVF算法。該算法綜合考慮了消息的截止期和價值度兩個參數(shù)對消息幀的影響，其中價值度代表了消息的關(guān)鍵性程度。根據(jù)CAN協(xié)議，消息幀在傳輸過程中不被中斷，因而該算法是非搶占式算法。

1 截止期-價值度優(yōu)先算法

1.1 CAN標(biāo)識符規(guī)劃及消息幀的參數(shù)

CAN網(wǎng)絡(luò)中不同節(jié)點的消息優(yōu)先級不能相同，也就是標(biāo)識符不能相同，而動態(tài)調(diào)度算法需要動態(tài)的調(diào)整消息標(biāo)識符的優(yōu)先級，為了調(diào)整的靈活性和避免標(biāo)識符的重復(fù)，這里對標(biāo)識符作如下規(guī)劃：采用29位擴展標(biāo)識符，其中低11位為固定部分，該部分用于CAN控制器的過濾器對消息的選擇性接收，而且還要包含節(jié)點ID信息，不同的節(jié)點其ID值不相同；高18位為可變部分，用于算法對標(biāo)識符的動態(tài)調(diào)整。這樣截止期-價值度優(yōu)先調(diào)度算法可以統(tǒng)一調(diào)度整個CAN網(wǎng)絡(luò)中所有節(jié)點的消息，同時標(biāo)識符固定部分由于節(jié)點ID不同而不會出現(xiàn)重復(fù)的情況，這樣也避免了不同節(jié)點發(fā)送的消息其標(biāo)識符彼此相等而沖突的情形。

此處只考慮周期實時性消息，對于任意實時性消息Mj其參數(shù)可描述為Mj=｛Tj，tja，Dj，vj｝；其中：Tj是消息的發(fā)送周期，tja是消息的到達(dá)時間；Dj是消息幀的絕對截止期；vj是消息的價值度。

一些參數(shù)的定義如下：絕對截止期是隨著時間的推移而不斷增加的量，其數(shù)值太大不方便計算，這里用相對截止期dr表示，dr=Dj-tja。定義消息的松弛度為dj，其大小表示為dj=Dj-tS，其中ts為系統(tǒng)當(dāng)前時間，所以dj的范圍為（0，dr）。CAN網(wǎng)絡(luò)中每個節(jié)點單獨計時而非采用統(tǒng)一時鐘，采用定時器加標(biāo)志變量的方式來表示到達(dá)時間tja、系統(tǒng)當(dāng)前時間ts和絕對截止期Dj。

1.2 算法設(shè)計

DVF算法遵循如下原則：①保證消息滿足截止期的情況下，盡量讓價值度高的消息優(yōu)先發(fā)送；②在消息距離其發(fā)生截止期較遠(yuǎn)時，消息的價值度對優(yōu)先級的高低起主要作用，而接近截止期時消息，消息的松弛度對優(yōu)先級高低起主要作用。這樣價值度高的消息可以優(yōu)先發(fā)送，同時保證了消息在截止期之前發(fā)送成功。而具體如何量化處理上述問題將在下面進行闡述，CAN消息的優(yōu)先級與標(biāo)識符綁定，設(shè)18位動態(tài)變化部分的標(biāo)識符大小用pj表示，pj由截止期影響因子與價值度影響因子相乘得到：

其中φ（dj）為截止期影響因子，ρj為價值度影響因子。

1.2.1 價值度影響因子大小的確定

對任意節(jié)點S的所有消息，按照價值度從低到高依次排序，相同價值度的消息作為一組，結(jié)果為S=｛M1，（M2，M3），…，（Mi，Mi+1，…，Mj），…，Mk｝；小括號內(nèi)為相同價值度的消息，其價值度依次為1、2、…、K。消息的價值度因子的大小為

其中k為價值度，即它們在集合中的順序號。α為價值度在算法中所占的權(quán)重，根據(jù)具體應(yīng)用而設(shè)定。當(dāng)α≠0時，價值度越大的消息，其價值度因子越小，那么其標(biāo)識符數(shù)值就越小優(yōu)先級就越高。當(dāng)α=0時ρj恒等于1，這時算法就演變成了EDF算法。當(dāng)α取值較大時，算法就更接近于HVF算法。

1.2.2 截止期影響因子大小的確定

對于截止期影響因子φ（dj）的確定原則為分段計算，具體如下：消息的松弛度較大時，松弛度的變化對消息優(yōu)先級的影響較小，而消息將要到達(dá)截止期時，松弛度的變化對消息優(yōu)先級的影響增大。這里采用分段直線的方式求取截止期因子φ（dj）。設(shè)CAN標(biāo)識符中留給DVF算法可以動態(tài)調(diào)整的有N位，標(biāo)識符動態(tài)變化部分表示的范圍為（0，2N-1）。設(shè)tfs為CAN最大幀時間，那么其值為［8］

其中0≤Sm≤8且取整數(shù)。

為了確保消息在其截止期之前發(fā)送成功，在dj= tfs時，消息優(yōu)先級應(yīng)該最高，這樣消息將在下一次總線仲裁時發(fā)送。

實時CAN總線網(wǎng)絡(luò)中往往存在一些緊迫性很高的偶發(fā)性消息，這樣消息需要最短的響應(yīng)時間，消息一旦產(chǎn)生就要理立即發(fā)送出去，為了滿足這類消息的實時性要求，預(yù)留出m個優(yōu)先級給這類偶發(fā)性消息，即0到m-1為預(yù)留優(yōu)先級。那么為了確保實時性周期消息的截止期要求，在消息的松弛度dj=tfs時截止期因子φ（dj）應(yīng)該等于m。

設(shè)某網(wǎng)絡(luò)節(jié)點中有L個節(jié)點，定義轉(zhuǎn)折截止期為dtr=L·tfs，這樣即使在最壞的情況下所有L個節(jié)點在同一時刻都向總線上發(fā)送了消息，依然可以保證這些消息在截止期之前發(fā)送成功。設(shè)網(wǎng)絡(luò)中所有消息的相對截止期最大值為dmax，網(wǎng)絡(luò)中所有節(jié)點消息價值度因子的最大值為ρmax，為了不超出標(biāo)識符可變部分表示的范圍，令

由式（1）～式（4）得出消息Mj在松弛度為dj時可變標(biāo)識符的數(shù)值p（ dj）如下：

一般CAN網(wǎng)絡(luò)中的dmax與dtr相差較大，因而當(dāng)dmax＜dj＜dtr時，φ（dj）函數(shù)曲線的斜率較小，此時DVF算法更接近于HVF算法，當(dāng)dj≤dtr時φ（dj）函數(shù)曲線的斜率明顯增大，此時DVF算法更接近于EDF算法，那么通過選取適當(dāng)?shù)摩林档玫胶线m的價值度因子ρj，使算法達(dá)到最好的性能。

2 實驗及算法性能分析

為了衡量DVF算法的性能，我們將其與EDF算法和HVF算法進行比較，以系統(tǒng)消息的丟失價值率、丟幀率、關(guān)鍵性消息的相對傳輸延遲這三個參數(shù)作為標(biāo)準(zhǔn)，以此來衡量算法性能，這三個參數(shù)定義如下：

2.1 定義

定義1（丟失價值率）：網(wǎng)絡(luò)各個節(jié)點中所有錯過截止期的消息所對應(yīng)的價值度與網(wǎng)絡(luò)中所有節(jié)點發(fā)送的消息的價值度比值稱為丟失價值率。丟失價值率越小的調(diào)度算法其性能越好。

定義2（丟幀率）：CAN網(wǎng)絡(luò)中所有錯過截止期的消息個數(shù)與所有節(jié)點發(fā)送的消息個數(shù)的比值稱為丟幀率，丟幀率越小的調(diào)度算法其保證整個網(wǎng)絡(luò)范圍內(nèi)的所有消息滿足消息截止期的能力越好。

定義3（相對傳輸延遲）：設(shè)消息發(fā)送周期為Tj，到達(dá)時刻為taj，成功發(fā)送時刻為tsj，那么發(fā)送延遲與消息周期的比值為相對傳輸延遲，記作RTD；即RTD=（tsj-taj）/Tj，這樣傳輸延遲的值就不依賴于程序運行的硬件條件，而僅僅與算法有關(guān)。相對傳輸延遲小的消息，其發(fā)送延遲就小，因此可以用此參數(shù)來衡量關(guān)鍵性程度高的消息的發(fā)送延遲。

2.2 實驗條件

實驗只考慮周期性實時消息的影響，其中α=1，V=7，數(shù)據(jù)幀數(shù)據(jù)域為8個字節(jié)。網(wǎng)絡(luò)中各節(jié)點向總線上發(fā)送的消息情況都相同，任意節(jié)點發(fā)送的消息Mj都可以表示為Mj=｛Tj，dr，vj｝，Tj為周期，單位為ms，消息Mj在任意時刻的發(fā)送概率服從其各自周期上的均勻分布；dr是消息的相對截止期；vj是消息的價值度。那么各節(jié)點發(fā)送的消息情況如下：M1=｛100，100，6｝，M2=｛40，20，5｝，M3=｛40，20，4｝，M4=｛20，20，3｝，M5=｛20，20，2｝，M6=｛500，10，1｝，通過改變網(wǎng)絡(luò)中節(jié)點個數(shù)來改變網(wǎng)絡(luò)負(fù)載率。每種負(fù)載率下程序時間為30000·tfs，每種調(diào)度算法運行10次取其平均值。

2.3 實驗結(jié)果與算法性能分析

2.3.1 丟幀率分析

圖1給出了DVF算法、EDF算法、HVF算法在不同負(fù)載率下的截止期錯過率的變化趨勢。從圖中可見，在整個負(fù)載率情況下DVF算法與EDF算法的截止期錯過率相當(dāng)；但是HVF即使在負(fù)載率為75%時也有6%的消息錯過截止期，這是由于即使在價值度高的消息其距離截止期還很遠(yuǎn)，而低價值度的消息將要錯過截止期的情況下，HVF算法依然還會先發(fā)送價值度高的消息，價值度低的消息將被延遲甚至錯過截止期限?？梢奃VF在保證實時性消息的截止期方面，明顯優(yōu)于HVF算法。

圖1 丟幀率比較

2.3.2 丟失價值率分析

圖2給出了DVF算法、EDF算法、HVF算法在不同負(fù)載率下的丟失價值率的變化趨勢。從圖中可以看出在整個負(fù)載率情況下DVF算法丟失價值率最低，在非過載的情況下EDF算法的丟失價值率小于HVF算法，這是由于HVF算法在正常網(wǎng)絡(luò)負(fù)載的情況下依然存在消息消息錯過截止期，導(dǎo)致HVF算法的總體價值丟失偏大；在系統(tǒng)超載的情況下DVF算法的丟失價值率逐漸接近HVF算法，但是明顯小于EDF算法?？梢奃VF算法在保證網(wǎng)絡(luò)整體價值度上相對于EDF算法和HVF算法都有很大的改進。

圖2 丟失價值率比較

2.3.3 關(guān)鍵性消息的相對傳輸延遲分析

圖3和圖4為價值度v=1和v=2關(guān)鍵消息的相對延遲在不同負(fù)載率下的變化趨勢。從圖中可見，在系統(tǒng)非過載的情況下，基于DVF算法的關(guān)鍵性消息的相對傳輸延遲和HVF算法基本相當(dāng)，而在系統(tǒng)超載的情況下，其值要明顯小于基于EDF算法的關(guān)鍵性消息相對傳輸延遲，但趨勢線基本與其平行。

總之，EDF算法是依據(jù)消息的截止期大小進行調(diào)度，總是優(yōu)先發(fā)送相對截止期最小的消息，但是EDF算法會導(dǎo)致關(guān)鍵性消的延遲增大，隨著負(fù)載率的增加這種情況加劇。HVF算法只依據(jù)消息的價值度進行任務(wù)調(diào)度，而未考慮消息的截止期，可能某些將要達(dá)到截止期的消息因其價值度低而不能得到總線控制權(quán)，從而錯過了截止期。而DVF算法兼顧截止期和價值度兩個參數(shù)，在正常網(wǎng)絡(luò)負(fù)載下，可以保證消息的優(yōu)先級在錯過截止期之前達(dá)到最高。通過合理的選擇k和α的值可以使算法達(dá)到很好的性能。

圖3 消息1的相對傳輸延遲

圖4 消息2的相對傳輸延遲

3 結(jié)束語

研究表明，在實時CAN總線網(wǎng)絡(luò)中應(yīng)該綜合考慮消息的截止期和價值度兩個因素。本文提出了DVF算法，采用了分段處理的方法處理截止期因素，在消息距離截止期較遠(yuǎn)時，消息的優(yōu)先級主要由價值度決定，為了保證消息不錯過截止期，在接近截止期時消息的優(yōu)先級高低主要由消息的松弛度決定。圖2、圖3和圖4表明DVF算法在低負(fù)載率時接近EDF算法，在高負(fù)載率時接近HVF算法，但是綜合性能均優(yōu)于EDF算法和HVF算法。因此，采用DVF算法調(diào)度的CAN總線網(wǎng)絡(luò)，在系統(tǒng)出現(xiàn)錯誤幀或者瞬時過載時，仍然可以保證最多的實時消息在截止期之前成功發(fā)送到總線上，而且保證了關(guān)鍵性消息優(yōu)先發(fā)送，從而使得系統(tǒng)價值度收益最大。

［1］佟為明，高洪偉，陳培友.CAN總線傳輸延時特性研究［J］.儀器儀表學(xué)報，2007，28（4）：295-297.

［2］李佳，朱元，田光宇.CAN與TTCAN通信延遲時間的分析［J］.清華大學(xué)學(xué)報，2006，46（3）：261-265.

［3］王書舉，張?zhí)靷b，張國勝.汽車TTCAN實時性分析及其可視化研究［J］.汽車工程，2011，33（2）：172-175.

［4］Zuberi K M，Shin KG.Scheduling messages on controller area network for real-time CIM application［J］.IEEE Transaction on Robotics and Automation，1997，13（2）：310-314.

［5］張杰.最早截止期有限實時調(diào)度算法研究［D］.武漢：華中科技大學(xué)，2009.

［6］G Buttazzo，M Spuri，F(xiàn) Sensini.Va-lue vs.deadline scheduling in overload conditions［A］.Proceeding of 16thIEEE Real-Time Systems Symposium［C］.Los La-mitos，California：IEEE Computer Society 1995.

［7］王躍飛，張偉偉，嚴(yán)剛.CAN消息的動態(tài)調(diào)度截止期選取研究［J］.合肥工業(yè)大學(xué)學(xué)報，2010，33（5）：644-651.

［8］王俊波，胥布工.CAN報文實時性分析與在線評估［J］.控制與決策，2007，22（4）：448-452.

（編輯 李秀敏）

Real-time Scheduling Algorithm of CAN Bus Message Based on Dead line-value First

JIAN Yi，WEI Lei，YANG Ya-lian，LIU Qi-xin
（State Key Laboratory of Mechanical Transmission，Chong Qing University，Chongqing 400030，China）

In order to guarantee the deadline of real-time message in CAN network and reduce the transmission delay of Emergency messages，a real-time scheduling algorithm named DVF（Deadline-Value First）is proposed，Considered deadline and value of real-time message in CAN network.The Principle and way of the algorithm is given.By disposing the deadline element in subsection-linear method，this algorithm can send the most critical message firstly with no loss of other message's deadline.The performance of the DVF（deadline-value first）algorithms is analyzed by comparing it with EDF（earliest deadline first）algorithm and HVF（highest value first）algorithm based on value lose ratio，miss message ratio and relative transmission delay.The experiment shows that HVF algorithms can improve the performance compared to the classical EDF algorithm and HVF algorithm under all workload conditions.

CAN bus network；deadline；value lose ratio；deadline miss ratio；relative transmission delay

TH166；TG659

A

1001-2265（2015）01-0157-04 DOI：10.13462/j.cnki.mmtamt.2015.01.044

2014-04-10

國家自然科學(xué)基金：ISG速度多段耦合混合動力傳動系統(tǒng)物理仿真及綜合換擋控制策略研究（51075411）

簡毅（1968—），男，重慶人，重慶大學(xué)副教授，碩士生導(dǎo)師，研究方向為機電系統(tǒng)、智能控制；通訊作者：魏磊（1987—），男，安徽人，重慶大學(xué)碩士研究生，研究方向為智能控制與計算機協(xié)同監(jiān)控，（E-mail）happyhm527@163.com。