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

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

（重慶大學(xué) 機(jī)械傳動(dòng)國(guó)家重點(diǎn)實(shí)驗(yàn)室，重慶 400030）

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

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

（重慶大學(xué) 機(jī)械傳動(dòng)國(guó)家重點(diǎn)實(shí)驗(yàn)室，重慶 400030）

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

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

0 引言

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

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

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

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

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

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

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

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

1.2 算法設(shè)計(jì)

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

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

1.2.1 價(jià)值度影響因子大小的確定

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

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

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

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

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

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

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

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

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

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

2 實(shí)驗(yàn)及算法性能分析

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

2.1 定義

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

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

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

2.2 實(shí)驗(yàn)條件

實(shí)驗(yàn)只考慮周期性實(shí)時(shí)消息的影響，其中α=1，V=7，數(shù)據(jù)幀數(shù)據(jù)域?yàn)?個(gè)字節(jié)。網(wǎng)絡(luò)中各節(jié)點(diǎn)向總線上發(fā)送的消息情況都相同，任意節(jié)點(diǎn)發(fā)送的消息Mj都可以表示為Mj=｛Tj，dr，vj｝，Tj為周期，單位為ms，消息Mj在任意時(shí)刻的發(fā)送概率服從其各自周期上的均勻分布；dr是消息的相對(duì)截止期；vj是消息的價(jià)值度。那么各節(jié)點(diǎn)發(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é)點(diǎn)個(gè)數(shù)來改變網(wǎng)絡(luò)負(fù)載率。每種負(fù)載率下程序時(shí)間為30000·tfs，每種調(diào)度算法運(yùn)行10次取其平均值。

2.3 實(shí)驗(yàn)結(jié)果與算法性能分析

2.3.1 丟幀率分析

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

圖1 丟幀率比較

2.3.2 丟失價(jià)值率分析

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

圖2 丟失價(jià)值率比較

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

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

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

圖3 消息1的相對(duì)傳輸延遲

圖4 消息2的相對(duì)傳輸延遲

3 結(jié)束語

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

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

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

［3］王書舉，張?zhí)靷b，張國(guó)勝.汽車TTCAN實(shí)時(shí)性分析及其可視化研究［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］張杰.最早截止期有限實(shí)時(shí)調(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消息的動(dòng)態(tài)調(diào)度截止期選取研究［J］.合肥工業(yè)大學(xué)學(xué)報(bào)，2010，33（5）：644-651.

［8］王俊波，胥布工.CAN報(bào)文實(shí)時(shí)性分析與在線評(píng)估［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

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

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