管銀鳳，張鳳登，張海濤，張宇輝

(上海理工大學(xué) 光電信息與計算機(jī)工程學(xué)院，上海 200093)

隨著新型汽車產(chǎn)業(yè)的發(fā)展，汽車上的電子控制裝置數(shù)量急劇增加，眾多傳感器和執(zhí)行器之間進(jìn)行通信傳輸?shù)男盘柫恳泊蠓仍龆?，?dǎo)致傳統(tǒng)的CAN(Controller Area Network)總線已無法完全滿足新型汽車產(chǎn)業(yè)對通信總線的要求[1]。CAN FD(CAN with Flexible Data rate)總線的帶寬大，其傳輸速率可達(dá)CAN總線的3～8倍，且能夠降低錯誤幀漏檢率，將會成為今后汽車電子領(lǐng)域的一個重要研究方向[2-4]。與此同時，為了保證傳感器與執(zhí)行器之間信號量傳輸?shù)膶?shí)時性，采用合適的調(diào)度算法對眾多信號量進(jìn)行快速、高效地調(diào)度，對汽車系統(tǒng)的安全及穩(wěn)定起著至關(guān)重要的作用[5]。因此，利用CAN FD總線來快速、準(zhǔn)確、實(shí)時地傳遞信息，對汽車內(nèi)信息進(jìn)行調(diào)度的研究具有重要的意義與價值[6]。目前基于優(yōu)先級的調(diào)度算法大體可分為靜態(tài)調(diào)度、動態(tài)調(diào)度和混合調(diào)度等[7]。其中，靜態(tài)算法包括單調(diào)速率調(diào)度算法(Rate Monotonic，RM)和截止期單調(diào)調(diào)度算法(Deadline Monotonic，DM)[8]。然而這兩種算法均對總線利用率較低且對事件觸發(fā)的報文處理不夠靈活[9]。動態(tài)算法包括最早截止期優(yōu)先算法(Earliest Deadline First，EDF)和最小松弛優(yōu)先算法(Least Laxity First，LLF)[10]，這兩種算法分別以消息的截止時期和剩余時間長短來分配任務(wù)優(yōu)先級，提高了網(wǎng)絡(luò)的利用率。為了適應(yīng)不可搶占任務(wù)的需要，文獻(xiàn)[11]給出了不可搶占式EDF調(diào)度算法的可調(diào)度性判定方法。文獻(xiàn)[12]提出了一種分解算法來對應(yīng)用在多核處理器上的最早截止期優(yōu)先算法進(jìn)行優(yōu)化。文獻(xiàn)[13]通過使用調(diào)度技術(shù)減少了網(wǎng)絡(luò)引起的延遲，確定了CAN、以太網(wǎng)、TDMA(Time Division Multiple Access)以及F-DMA(Frequency Division Multiple Access)之間適合用于EDF調(diào)度的PID(Proportional Integral Derivative)控制網(wǎng)絡(luò)，并通過該算法減少了時延問題。文獻(xiàn)[14]中將EDF算法和LST(Least Slace Time First)算法相結(jié)合，提高了實(shí)時任務(wù)的調(diào)度性能。文獻(xiàn)[15]對編碼動態(tài)更新和優(yōu)先級反轉(zhuǎn)的問題提出了優(yōu)化方法。其通過利用EDF算法來提高消息的實(shí)時性，且解決截止期編碼問題時，可以采用不同的分區(qū)編碼方式把變化范圍較大的截止期表示出來[16-17]。在綜合考慮截止期和價值度兩方面影響后，文獻(xiàn)[18]提出了基于截止期價值度優(yōu)先的DVF(Deadline Value First)算法，即在滿足消息的截止期的前提下，盡量讓價值度更高的消息優(yōu)先發(fā)送。

本文在對平均分區(qū)EDF調(diào)度算法研究的基礎(chǔ)上，改進(jìn)了適用于CAN FD通信的EDF調(diào)度算法。利用指數(shù)-冪函數(shù)的動態(tài)編碼分區(qū)方法擴(kuò)大了截止期的編碼范圍，降低了出現(xiàn)優(yōu)先級反轉(zhuǎn)的概率，并合理分配了網(wǎng)絡(luò)帶寬，降低了總線負(fù)載，適當(dāng)提高了帶寬利用率。

1 EDF算法

1.1 平均分區(qū)EDF算法

為了提高單處理器系統(tǒng)的處理器利用率，EDF算法是動態(tài)搶占式調(diào)度算法中非常重要的算法[19]。該算法根據(jù)報文的絕對截止時間Dm的大小動態(tài)分配優(yōu)先級。報文的絕對截止時間越小，其優(yōu)先級越高。然而隨著時間的增加，報文的絕對截止時間也隨之增大，此時標(biāo)識符的表示范圍將無法涵蓋所有的截止期。因此，為了有效地減少標(biāo)識符ID(Identifier)中用來表示優(yōu)先級的位數(shù)，本文引入相對截止時間dm=Dm-tstart，其中tstart為總線仲裁開始時間。此外，通過對報文的截止時間進(jìn)行編碼來計算報文的優(yōu)先級，而采用不同的標(biāo)識符編碼方式得出的優(yōu)先級計算結(jié)果也會相應(yīng)不同，通常在EDF算法中采用如下所示的平均分區(qū)編碼方式。

對于一組報文{m1，m2，…，mn}，假設(shè)它們的相對截止時間從小到大排列為{d1，d2，…，dmax}。采用平均分區(qū)的方式是將時間軸以報文的最大相對截止時間dmax為上限等分成k段，則每段區(qū)間長為dmax/k。假設(shè)對任意兩個報文mi與mj，其相對截止時間分別為di與dj且di

圖1 平均分區(qū)示意圖Figure 1. Schematic diagram of average partition

根據(jù)EDF調(diào)度算法，在每輪調(diào)度時，報文的優(yōu)先級根據(jù)其相對截止時間確定。圖1中報文mi與mj的相對截止時間di與dj被劃分在一個區(qū)間，即二者具有相同的優(yōu)先級。這與根據(jù)標(biāo)識符判定mi的優(yōu)先級高于mj的實(shí)際情況不符。因此，根據(jù)上述分區(qū)，會導(dǎo)致報文mi被mj推遲占用總線的優(yōu)先級反轉(zhuǎn)問題[20]。

1.2 可調(diào)度性判定

由于CAN FD總線屬于非搶占式總線，故參考信號調(diào)度中非搶占式調(diào)度理論對報文的可調(diào)度性判定進(jìn)行分析。首先給出定理1，以確?？偩€利用率滿足要求，接著用定理2給出非搶占截止期調(diào)度策略的可調(diào)度性判定。

定理1[11]由n個報文組成的報文集合{m1，m2，…，mn}，當(dāng)且僅當(dāng)在所有報文均滿足式(1)時，則稱其為可調(diào)度的

(1)

式中，Cm和Tm分別為報文m的傳輸時間和請求周期。

定理2[11]對實(shí)時任務(wù)τm=(Tm，Cm，dm)，m=1，2，…，n，當(dāng)且僅當(dāng)其滿足以下計算式時，非搶占截止期調(diào)度策略是可調(diào)度的

(2)

式中，dmin=min{dm:1≤m≤n}；Cp代表報文所需的最長通信時間。

上述兩個定理成立的條件已在文獻(xiàn)[19]中得到證明。為了簡化判定條件，假設(shè)報文傳輸在最壞情況下(即最壞的阻塞情況)發(fā)生，所有報文在同一時間t=0時釋放。由于任務(wù)執(zhí)行時是非搶占的，即此時無論請求執(zhí)行的新任務(wù)的優(yōu)先級高低，正在執(zhí)行的任務(wù)都無法被中斷，而新任務(wù)則必須在該任務(wù)執(zhí)行結(jié)束后才有機(jī)會使用總線。針對上述情況，可調(diào)度性的判定應(yīng)將高優(yōu)先級報文被低優(yōu)先級報文阻塞的時間包含在內(nèi)，如引理1所示。

引理1[21]假設(shè)由n個報文組成的報文集合{m1，m2，…，mn}。該消息集合在滿足式(3)時，可被EDF算法調(diào)度

(3)

式中，Cm、Tm、Bm分別為報文m傳輸時間、周期及最大阻塞時間。

2 改進(jìn)的EDF算法

2.1 指數(shù)分區(qū)的母區(qū)間

針對指數(shù)分區(qū)的方式，若使接近仲裁開始時間的區(qū)間較小，則精度會增高；而離仲裁開始時間遠(yuǎn)的區(qū)間較大，精度也會有所降低。因此，在這種分區(qū)方式下，能夠在較大程度上減少截止期相近的兩個報文被分到同一個母區(qū)間內(nèi)的概率，從而更好地保證報文的實(shí)時性[16]。本文對母區(qū)間采用指數(shù)分區(qū)的方式，其具體過程如下：

步驟1將報文集合中的各相對截止期dm按大小排列，取截止期中的最大值dmax作為截止期分區(qū)的上限值；

步驟2選取指數(shù)分區(qū)時的分區(qū)因子a，即采用以a為底的指數(shù)方式對相對截止時間范圍[0，dmax)進(jìn)行分區(qū)時，首先需要明確底數(shù)a的大小。由于分區(qū)因子a的大小和報文的數(shù)量有關(guān)，在本文中為了計算簡單清晰故取a=2；

步驟3根據(jù)上述的指數(shù)分區(qū)方案，假設(shè)報文在0時刻釋放，將以0時刻為起始至dmax/2k的范圍定義為母區(qū)間0，則共計k+1個母區(qū)間，以{I0，I1，I2，…，Ik-1，Ik}形式表示，即分區(qū)后第1個母區(qū)間I0的范圍為[0，dmax/2k)，第2個母區(qū)間I1的范圍為[dmax/2k，dmax/2k-1)。以此類推，第i個指數(shù)分區(qū)Ii的范圍為[dmax/2k+1-i，dmax/2k-i)，最后1個母區(qū)間Ik的范圍為[dmax/2，dmax)。綜上，其區(qū)間范圍表示為

(4)

則第i個母區(qū)間的大小如式(5)所示。

(5)

母區(qū)間具體劃分如圖2所示，按照上述方法劃分出多個母區(qū)間，且各個母區(qū)間的長度均不同。這種分區(qū)的優(yōu)點(diǎn)是能在一定程度降低截止期相近的報文在傳輸時分配同一優(yōu)先級的可能性，可以有效避免優(yōu)先級反轉(zhuǎn)的情況出現(xiàn)。

圖2 母區(qū)間指數(shù)分區(qū)Figure 2. Parent interval of exponential function partition

2.2 冪函數(shù)分區(qū)的子區(qū)間

在采用指數(shù)函數(shù)將截止期分成多個母區(qū)間后，本文將采用冪函數(shù)分區(qū)方式將每個母區(qū)間再細(xì)分成多個子區(qū)間。該操作的目的是再次在有限的范圍內(nèi)細(xì)分出不同長度的截止期區(qū)間，以便在滿足不同報文的截止期要求的前提下，進(jìn)一步降低優(yōu)先級反轉(zhuǎn)出現(xiàn)的概率。假設(shè)對每個母區(qū)間Ii按照冪函數(shù)的方法再劃分出q個子區(qū)間，其中選取冪函數(shù)的冪次為1。圖3中給出在第i個母區(qū)間中劃分為q個子區(qū)間的分區(qū)情況。

圖3 子區(qū)間冪函數(shù)分區(qū)Figure 3. Subintervalof power function partition

經(jīng)過上述指數(shù)函數(shù)的分區(qū)后，在對每個母區(qū)間內(nèi)劃分子區(qū)間時，子區(qū)間的實(shí)際表示范圍需要考慮到母區(qū)間的起始下限值。因此，在第i個母區(qū)間的第1個子區(qū)間的范圍為[dmax/2k+1-i， (q+1)×dmax/q×2k+1-i)，第2個子區(qū)間的范圍為[(q+1)×dmax/q×2k+1-i，q×dmax/(q-1)×2k+1-i)。以此類推，即可得出第i個母區(qū)間的第j個子區(qū)間的范圍為

(6)

式中，i=0，1，2，…，k；j=2，3…，q。第i個母區(qū)間的最后1個子區(qū)間的范圍為[3×dmax/2k+2-i，dmax/2k-i)。

根據(jù)上式，將每個子區(qū)間稱為基本時間單元U，則第i個母區(qū)間的子區(qū)間j可利用基本時間單元Uij表示，而Uij的大小可以根據(jù)式(7)求出。

(7)

經(jīng)過分區(qū)編碼后，現(xiàn)存網(wǎng)絡(luò)中就有q×(k+1)個優(yōu)先級的信息。假設(shè)CAN FD總線的標(biāo)識符編碼位共有n位，如果要涵蓋所有的優(yōu)先級則必須滿足2n≥q×(k+1)。

2.3 優(yōu)先級的計算

假設(shè)所有報文的相對截止時間已知，且報文m的相對截止時間為dm，且dm≤dmax，則根據(jù)dm的大小及分區(qū)方式可以求出其所在的母區(qū)間和子區(qū)間，進(jìn)而求出報文m所對應(yīng)的優(yōu)先級。具體計算過程如下所示：

步驟1先計算出dm所在的母區(qū)間的區(qū)間號i。任一報文的截止期按照此分區(qū)方式進(jìn)行劃分，必定位于劃分的某個母區(qū)間范圍內(nèi)，即滿足

(8)

式中，i=0，1，2，…，k。

根據(jù)上式，利用截止期dm所在的范圍反求母區(qū)間i的范圍，化簡可得

(9)

由于優(yōu)先級越高其所在區(qū)間號i應(yīng)該越小。因此確定區(qū)間號時采用向下取整的方式以獲得更高的優(yōu)先級，此時求出i的值為

(10)

步驟2確定截止期dm所處子區(qū)間的區(qū)段號j。報文的相對截止期必定落在子區(qū)間j所處范圍內(nèi)，即

(11)

根據(jù)式(11)計算子區(qū)間區(qū)段號的大小，得

(12)

整理上式可得子區(qū)間區(qū)段號j為

(13)

步驟3根據(jù)計算式計算得到的母區(qū)間號i和子區(qū)間號j的值，隨后即可計算報文的優(yōu)先級p，至此完成將報文的絕對截止時間轉(zhuǎn)化為報文優(yōu)先級操作，計算式如下

p=j+(i-1)×q

(14)

將求得的優(yōu)先級p為十進(jìn)制，可將其二進(jìn)制化即為報文的標(biāo)識符。

2.4 誤差及可調(diào)度性分析

在采用上述指數(shù)-冪函數(shù)方式進(jìn)行分區(qū)時，以各個報文的相對截止時間為基準(zhǔn)，可以求得各個報文的優(yōu)先級，進(jìn)而完成對標(biāo)識符的動態(tài)編碼。然而，在計算優(yōu)先級的過程中對母區(qū)段號和子區(qū)段號的選取均為向下取整，這種做法不可避免地會產(chǎn)生誤差。將這種誤差定義為“量化誤差”[16，22]，記該誤差為Eij，式中，i=0，1，2，…，k；j=1，2，…，q，則其值為

(15)

根據(jù)上式中的誤差Eij，可以進(jìn)一步對EDF算法的可調(diào)度性判定引理1中的判別式進(jìn)行修正，得到式(16)，即

(16)

式中，Eij為正常傳輸過程中每個報文經(jīng)計算存在的誤差。量化誤差Eij一定為正且其大小不會超過基本時間單元Uij的大小，即0 ≤Eij≤Uij。在此誤差影響下，若要充分保證系統(tǒng)可調(diào)度，則可調(diào)度性判別式應(yīng)更新為式(17)，即

(17)

令Xf=Uij/Tm， 式中Xf≥0，f=1，2，…，k×q，化簡上式得

(18)

若取X=max{Xf}，則最終的可調(diào)度性判定式為式(19)。

(19)

通過上述的可調(diào)度性判別計算式可知，量化誤差的存在對報文的可調(diào)度性產(chǎn)生了影響，使報文的可調(diào)度性判別更加嚴(yán)格。

3 實(shí)驗結(jié)果及分析

3.1 模型設(shè)計

為達(dá)到良好的仿真效果，以下將從通信網(wǎng)絡(luò)定義、ECU(Electronic Control Unit)定義及報文、信號等層面詳細(xì)進(jìn)行網(wǎng)絡(luò)分析規(guī)劃。整個網(wǎng)絡(luò)由以下4個可選用CAN FD總線傳輸?shù)腅CU組成[23]，總計傳輸15個報文，具體為：(1)用于控制車載3個電池狀態(tài)的BCM(Battery Control Management)ECU，共計收發(fā)3個報文；(2)用于實(shí)現(xiàn)數(shù)據(jù)在儀表盤上顯示傳送發(fā)動機(jī)速度、狀態(tài)、溫度及油耗的電機(jī)狀態(tài)的IPC(Instrument Panel Cluster)ECU，共計收發(fā)4個報文；(3)用于控制車兩側(cè)的前后車門、車速、和車燈狀態(tài)的Gateway ECU，共計收發(fā)6個報文；(4)用于收發(fā)點(diǎn)火與熄火的開關(guān)Switch ECU，共計收發(fā)2個報文。網(wǎng)絡(luò)設(shè)計規(guī)劃如圖4，節(jié)點(diǎn)報文分配見表1。

表1 報文分配

圖4 CAN FD網(wǎng)絡(luò)規(guī)劃設(shè)計Figure 4. CAN FD network planning and design

3.2 仿真實(shí)驗設(shè)計

按照圖4網(wǎng)絡(luò)規(guī)劃將信號加入數(shù)據(jù)庫并搭建CANoe仿真實(shí)驗平臺，電機(jī)狀態(tài)(儀表)ECU和Switch ECU所產(chǎn)生的報文設(shè)置為非周期性報文，而網(wǎng)關(guān)ECU和車身ECU均為周期性報文。電池狀態(tài)報文周期為400 ms，車門狀態(tài)相關(guān)報文及車速、車燈報文周期設(shè)置為500 ms，電機(jī)轉(zhuǎn)速及溫度與狀態(tài)報文周期為1 000 ms。周期性報文傳輸時間設(shè)定為0.115 ms，非周期性報文為0.08 ms。設(shè)置報文釋放時間為零，即假定報文的相對截止時間與其周期相等，按照指數(shù)-冪函數(shù)分區(qū)方式進(jìn)行編碼，并根據(jù)報文的初始相對截止時間計算報文的起始ID，具體參數(shù)設(shè)定如表2所示。

表2 報文及參數(shù)設(shè)定

3.3 結(jié)果及分析

為驗證本文提出的方法的調(diào)度效果，分別對采用平均分區(qū)和指數(shù)-冪函數(shù)分區(qū)的EDF算法進(jìn)行仿真實(shí)驗。首先進(jìn)行可調(diào)度判定，任意截取一段報文傳輸?shù)木唧w數(shù)據(jù)如表3所示。表中第4列為報文的周期Ti，其最小值為400 ms；第5列為計算的報文傳輸時間，即式(2)中的Ci，本文此處以t=2.0 s時刻具體舉例說明。

表3 t=2.0 s時傳輸報文的具體數(shù)據(jù)

對表3中截取t=2.0 s傳輸?shù)膱笪臄?shù)據(jù)按照定理2進(jìn)行可調(diào)度性判定，即將所有Tm、Cm、dm、Cp數(shù)據(jù)帶入式(2)進(jìn)行計算。其中，最長傳輸阻塞時間Cp= 0.109 ms，則有

(20)

經(jīng)過上式計算，滿足定理2對于可調(diào)度性的判定，即傳輸?shù)膱笪募强烧{(diào)度的。

驗證可調(diào)度后，采用該組報文集進(jìn)行實(shí)驗。為了對比實(shí)驗，選定的報文傳輸速率分別為4 Mbit·s-1、8 Mbit·s-1，其中4 Mbit·s-1的波特率是Vector推薦的CAN FD的最佳傳輸速率。兩種分區(qū)方式下的調(diào)度結(jié)果如圖5和圖6所示。

(a)

(c)

根據(jù)仿真實(shí)驗結(jié)果計算在不同波特率下各自的總線負(fù)載可得：(1)采用傳輸速率為4 Mbit·s-1下的指數(shù)-冪函數(shù)編碼的總線負(fù)載為0.28%，而平均分區(qū)的總線負(fù)載為0.49%；(2)當(dāng)傳輸速率為8 Mbit·s-1時，兩者各自的總線負(fù)載分別為0.25%和0.43%。經(jīng)計算，采用本文提出的指數(shù)-冪函數(shù)編碼方法進(jìn)行調(diào)度時，總線負(fù)載分別降低了42.90%和46.50%，表明本文對EDF算法的改進(jìn)是可行的。此外，在傳輸速率為4 Mbit·s-1的仿真實(shí)驗過程中，報文被阻塞的最大時間為1.317 ms，最大誤差為31.25%。根據(jù)引理1可得

(21)

上式計算驗證了系統(tǒng)是可調(diào)度的，這與仿真實(shí)驗結(jié)果及定理2的判定結(jié)果一致。

4 結(jié)束語

本文在研究平均分區(qū)EDF調(diào)度算法的基礎(chǔ)上，提出了使用指數(shù)-冪函數(shù)的分區(qū)編碼方式改進(jìn)EDF算法。經(jīng)過仿真實(shí)驗，驗證了改進(jìn)后的算法通過劃分不同的母區(qū)間與子區(qū)間，使截止期各不相同的報文都能處在正確的區(qū)間內(nèi)，不僅可以優(yōu)化之前會出現(xiàn)的優(yōu)先級反轉(zhuǎn)問題，還能夠有效降低總線負(fù)載。但是本文的不足之處在于，對報文調(diào)度進(jìn)行的研究是假設(shè)系統(tǒng)處于一種理想狀況，忽略了報文傳輸延遲、釋放抖動以及傳輸時可能出錯的情況，從而存在一定誤差。日后可針對這種不足做出改進(jìn)，并可以搭建硬件節(jié)點(diǎn)進(jìn)行實(shí)物驗證。