趙國承，張鳳登

（上海理工大學光電信息與計算機工程學院，上海 200093）

0 引言

控制器局域網(wǎng)絡(luò)（Controller Area Network，CAN）總線是用于連接電子控制單元（Electronic Control Unit，ECU）的多主機廣播串行總線標準，CAN 總線上每個節(jié)點都能夠發(fā)送和接收報文，但不能同時發(fā)送和接收報文［1］。在CAN 總線中，任何具有高優(yōu)先級的報文要在短時間內(nèi)高頻率占用總線，都有可能造成低優(yōu)先級報文饑餓［2］。

解決CAN 總線中低優(yōu)先級報文饑餓問題的研究較多。Murtaza 等［3］提出在CAN 總線上增加一個主節(jié)點，以防止其他低優(yōu)先級節(jié)點出現(xiàn)阻塞問題。主節(jié)點必須嘗試檢測饑餓節(jié)點，并確保饑餓節(jié)點保持參與通信。主節(jié)點始終監(jiān)視CAN 網(wǎng)絡(luò)，并在收到來自所有節(jié)點的報文時保持沉默。如果主節(jié)點發(fā)現(xiàn)來自某些節(jié)點的報文沒有參與通信，則該主節(jié)點將變?yōu)榛顒訝顟B(tài)，這確保了來自這些節(jié)點的報文可以在下一輪仲裁中訪問以進行廣播。雖然該方案可以防止啟動問題，但由于需要額外的節(jié)點支持，因此該方案需要更高的負擔。文獻［4］提出基于使用優(yōu)先級和先入先出FIFO（First Input First Output）隊列的CAN 總線報文調(diào)度方法，但其只關(guān)注了可行調(diào)度表的生成，卻因此忽略了CAN總線中存在的饑餓問題。文獻［5］開發(fā)了一種無饑餓模型，當存在任務(wù)發(fā)送失敗的次數(shù)大于設(shè)置的閾值時，會使用優(yōu)先級反轉(zhuǎn)將該任務(wù)反轉(zhuǎn)為最高優(yōu)先級。文獻［6］提出了一種新的無饑餓CAN 總線仲裁模型，其特點是利用報文標識符的最高兩位動態(tài)反轉(zhuǎn)實現(xiàn)優(yōu)先級上升。Kimm 等［7］提出一種避免饑餓的CAN 總線調(diào)度方案，通過將每輪仲裁中發(fā)送失敗的報文優(yōu)先級反轉(zhuǎn)為更高的優(yōu)先級來避免饑餓問題。

以上研究注重將優(yōu)先級低的任務(wù)在CAN 總線仲裁中動態(tài)變?yōu)楦邇?yōu)先級任務(wù)，但這種方法存在弊端，當CAN 總線存在非常緊急的報文需要立刻發(fā)送時，很有可能得不到及時發(fā)送。本文更多地考慮將優(yōu)先級高的任務(wù)在一定條件下進行優(yōu)先級反轉(zhuǎn)，動態(tài)降低其優(yōu)先級，因此不會出現(xiàn)CAN 總線不能立刻發(fā)送非常緊急的報文問題，而且能有效避免CAN 總線固定優(yōu)先級調(diào)度造成的饑餓問題。

1 CAN 總線幀格式和仲裁方式

自從德國Bosch 公司在汽車工程師協(xié)會（Society of Automotive Engineers，SAE）大會上引入串行總線系統(tǒng)以來，CAN 總線已經(jīng)逐漸成為最成功的數(shù)據(jù)通信協(xié)議之一［8］。CAN 總線采用載波監(jiān)聽多路訪問/沖突避免（Carrier Sense Multiple Access with Collision Avoid，CSMA/CA）協(xié) 議［9-10］，所以CAN 總線的訪問是無沖突、按位仲裁的［11］。無沖突意味著總是更高優(yōu)先級的報文在仲裁中獲勝并發(fā)送，且在發(fā)送過程中禁止其它報文發(fā)送。按位仲裁可以理解為，如果有兩個或多個節(jié)點同時進行傳輸，且有顯性位和隱形位同時發(fā)送，這時規(guī)定顯性位的權(quán)重大于隱形位，故顯性位可以覆蓋隱形位。

在CAN 總線中有數(shù)據(jù)幀、遠程幀、錯誤幀和過載幀4 種不同的幀［12］，其中數(shù)據(jù)幀能夠?qū)?shù)據(jù)從發(fā)生端廣播至接收端，數(shù)據(jù)幀格式如圖1 所示，攜帶有標識符的遠程幀用來請求另一節(jié)點發(fā)送具有相同標識符的數(shù)據(jù)幀；錯誤幀發(fā)送總線中出現(xiàn)錯誤的指示；當數(shù)據(jù)幀與相鄰的一個數(shù)據(jù)幀或遠程幀之間出現(xiàn)額外延遲時，過載幀將被發(fā)送。在CAN 總線空閑時，CAN 總線上任何一個節(jié)點都能在CAN 總線上發(fā)送報文，無需獲得總線上其他節(jié)點許可［13］。

Fig.1 Data frame format圖1 數(shù)據(jù)幀格式

數(shù)據(jù)幀分為標準格式和擴展格式兩種。其中標準格式的標識符長度為11 位，擴展格式標識符有29 位［14］。本文對標準格式進行論述，對數(shù)據(jù)幀中仲裁場的標識符進行分析。

當CAN 總線上有多個節(jié)點同時發(fā)送時，通過對總線進行監(jiān)控，可以確定每個節(jié)點當前正在傳輸?shù)膱笪膬?yōu)先級高低。若在仲裁中某一節(jié)點勝出，那么該節(jié)點繼續(xù)傳輸其報文的剩余部分，此時仲裁失敗的節(jié)點均退出并繼續(xù)等待下一次仲裁開始［15-17］。同時，因為CAN 總線沒有全局時鐘，所以節(jié)點需要在每次報文傳輸時重新同步，并且每個節(jié)點必須與首先開始傳輸?shù)墓?jié)點同步，以便總線仲裁能夠正常工作［18-19］。

2 反轉(zhuǎn)算法設(shè)計

2.1 算法思路

本算法中11 位報文標識符設(shè)計為1 位動態(tài)反轉(zhuǎn)標識位、1 位級別位和9 位靜態(tài)位3 部分，如圖2 報文標識符ID劃分所示。當然這僅僅是在標準格式中的劃分，除此之外還可根據(jù)需要應(yīng)用在擴展格式中。靜態(tài)標識位（ID0-ID8）從優(yōu)先級最低的111111111 開始，以最高優(yōu)先級的0 位000000000 結(jié)束。級別標識位ID9用來區(qū)分高優(yōu)先級組和低優(yōu)先級組，其中高優(yōu)先級組的級別標識位為0，低優(yōu)先級組的級別標識位為1，動態(tài)反轉(zhuǎn)標識位ID10默認為0 未反轉(zhuǎn)，當高優(yōu)先級組存在報文滿足反轉(zhuǎn)條件時會動態(tài)反轉(zhuǎn)為1。

Fig.2 Message identifier ID partition圖2 報文標識符ID 劃分

CAN 總線上發(fā)送的報文由節(jié)點生成，為不同的報文分配優(yōu)先級時，這些報文的優(yōu)先級將伴隨著報文同樣保存在節(jié)點中。由于報文發(fā)送基于固定優(yōu)先級的CAN 總線調(diào)度，因此，當CAN 總線上的節(jié)點發(fā)送報文時，該報文所獲得的優(yōu)先級會一直固定不變，而且每一個報文的優(yōu)先級都是獨一無二的，不能出現(xiàn)重復的優(yōu)先級，否則很有可能造成死鎖。

本文選擇非搶占式的單調(diào)速率（Rate Monotonic，RM）算法進行報文優(yōu)先級分配。選擇非搶占式的RM 算法調(diào)度原因如下：①如圖3 所示，非搶占式調(diào)度方法可以確保一旦發(fā)送某一報文就能夠一直發(fā)送直到發(fā)送完畢，在此期間不能被其它高優(yōu)先級報文打斷，發(fā)送過程中上下文切換開銷忽略不計；②RM 算法是根據(jù)報文的周期來分配優(yōu)先級，其特點是報文發(fā)送的周期越短優(yōu)先級越高［20］，反之報文的發(fā)送周期越長優(yōu)先級越低，要求在報文開始發(fā)送之前便分配完畢且運行過程中始終固定。

Fig.3 Non-preemptive scheduling圖3 非搶占式調(diào)度

算法實現(xiàn)如下：在CAN 總線中，當高優(yōu)先級組在一定時間內(nèi)出現(xiàn)某一報文發(fā)送的次數(shù)大于設(shè)置的固定值時，則在下一次繼續(xù)參與CAN 總線仲裁之前將其動態(tài)反轉(zhuǎn)到標識位ID10，進行反轉(zhuǎn)由0 變?yōu)?，從而使其比低優(yōu)先級組里的報文優(yōu)先級還低，此時處于饑餓中的報文得到機會發(fā)送，實現(xiàn)避免饑餓目的；當其動態(tài)反轉(zhuǎn)標識位變?yōu)? 時，并不意味其喪失繼續(xù)參與本次CAN 總線仲裁的資格，而是進一步判斷當前CAN 總線是否處于空閑狀態(tài)。如果總線空閑，則該反轉(zhuǎn)后的報文正常發(fā)送，否則不會發(fā)送，這樣可以避免當總線擁擠時，反轉(zhuǎn)后發(fā)送的高優(yōu)先級報文經(jīng)過多次仲裁都不能占用總線的問題，避免報文發(fā)送的順序錯亂；最后，不管本次是否發(fā)送成功，都會在下一次參與CAN 總線仲裁之前將其動態(tài)反轉(zhuǎn)標識位變?yōu)?，重新恢復其高優(yōu)先級。有了1 位動態(tài)反轉(zhuǎn)標識位，任何具有高優(yōu)先級的報文在短時間內(nèi)高頻率占用總線一定次數(shù)后都會被中斷。本文使用的11 位ID 動態(tài)反轉(zhuǎn)標識位開始均為0，級別標識位可在0與1之間進行劃分，靜態(tài)標識位內(nèi)數(shù)字可任意選取。

2.2 任務(wù)模型

模型如圖4 所示。在本模型中，設(shè)被調(diào)度的報文組為｛M1，M2，…，Mn｝，Mi是其中的一個報文，i=1，2，…n。避免饑餓的高優(yōu)先級反轉(zhuǎn)模型主要由2 個參數(shù)Ttc和TMax決定，其中Ttc代表檢測報文發(fā)送次數(shù)的時間，TMax代表在Ttc時間內(nèi)發(fā)送報文的次數(shù)。同時進行如下定義：

Fig.4 High priority inversion model to avoid starvation圖4 避免饑餓的高優(yōu)先級反轉(zhuǎn)模型

定義1報文Mi的傳輸周期等于其截止時間

其中，Pi為報文Mi傳輸周期，Di為報文Mi截止時間。

定義2CAN 總線利用率U定義為：

其中，K為報文Mi執(zhí)行時間，P為報文Mi傳輸周期，i=1，2，…n。

定義3報文Mi的響應(yīng)時間T定義為：

其中，t1為報文Mi的激活時間，t2為報文Mi的發(fā)送完成時間。

其中，n為報文數(shù)量，i=1，2，…n。

定義4到達率S定義為：

其中，R指單位時間內(nèi)實際發(fā)送報文的數(shù)量，C為預計發(fā)送報文的數(shù)量。

本算法實現(xiàn)檢測報文發(fā)送次數(shù)并防止遺漏、到達規(guī)定次數(shù)以后進行反轉(zhuǎn)，以及未反轉(zhuǎn)報文的發(fā)送功能。算法部分代碼如下：

3 實驗仿真

本文使用Vector CANoe 平臺實現(xiàn)避免饑餓的高優(yōu)先級反轉(zhuǎn)算法。CANoe 是一種軟件開發(fā)和測試工具，主要用于通信網(wǎng)絡(luò)和ECU的開發(fā)、分析、仿真、測試、診斷和啟動，編程語言CAPL 用于編寫測試腳本和仿真模型［21］。實驗開始所有報文均在0 時刻釋放，本文設(shè)置兩組周期報文隊列，分別為高優(yōu)先級組和低優(yōu)先級組，兩組報文的截止日期均等于報文的發(fā)送周期，實驗將每組設(shè)置為2 個報文。

其中高優(yōu)先級組的兩個報文為M1和M2，低優(yōu)先級組的兩個報文為M3和M4，高優(yōu)先級組得到報文優(yōu)先級遠遠大于低優(yōu)先級組。為了進一步驗證避免饑餓的高優(yōu)先級反轉(zhuǎn)模型與正常固定優(yōu)先級的優(yōu)勢，實驗分別進行CAN 總線正常工作、CAN 總線滿利用率工作、CAN 總線產(chǎn)生饑餓以及將報文數(shù)量擴大仿真。

3.1 CAN 總線正常工作

設(shè)報文M1的發(fā)送周期為2ms，優(yōu)先級設(shè)置為0x01，報文M2的發(fā)送周期為4ms，優(yōu)先級設(shè)置為0x02，報文M3的發(fā)送周期為8ms，優(yōu)先級設(shè)置為0x201，報文M4的發(fā)送周期為12ms，優(yōu)先級設(shè)置為0x202。規(guī)定兩組報文的執(zhí)行時間K均設(shè)置為1ms，檢測時間Ttc設(shè)置為8ms，檢測報文發(fā)送次數(shù)TMax設(shè)置為3。如圖5 所示，通過對比未進行反轉(zhuǎn)的固定優(yōu)先級調(diào)度和有反轉(zhuǎn)的非搶占式RM 算法調(diào)度在CAN 總線的發(fā)送隊列可知，未進行反轉(zhuǎn)的固定優(yōu)先級調(diào)度和有反轉(zhuǎn)的非搶占式RM 算法調(diào)度雖然均能將報文正常發(fā)送，但是使用了反轉(zhuǎn)的非搶占式RM 算法調(diào)度能夠較好地降低低優(yōu)先級組報文的響應(yīng)時間T，例如報文M4。其中反轉(zhuǎn)報文----M1是報文M1的反轉(zhuǎn)，根據(jù)避免饑餓的高優(yōu)先級反轉(zhuǎn)模型可知，其優(yōu)先級反轉(zhuǎn)為0×401，遠遠小于低優(yōu)先級組的兩個報文的優(yōu)先級，因此反轉(zhuǎn)后報文M4可以在反轉(zhuǎn)報文----M1的前面執(zhí)行。此時CAN 總線上的報文均得到機會發(fā)送，故低優(yōu)先級組的到達率S 始終為1。

3.2 CAN 總線滿利用率工作

除了將報文M3的發(fā)送周期設(shè)置為6ms 以外，其它所有實驗參數(shù)均與CAN 總線正常工作時一樣。通過觀察圖6 可知，未進行反轉(zhuǎn)的固定優(yōu)先級調(diào)度恰好能夠?qū)⑺袌笪脑谄渲芷趦?nèi)發(fā)送，而此時有反轉(zhuǎn)的非搶占式RM 算法調(diào)度則很明顯地降低了低優(yōu)先級組報文的響應(yīng)時間T，此時CAN總線上的報文恰好均能發(fā)送，故低優(yōu)先級組的到達率S 始終為1。

3.3 CAN 總線產(chǎn)生饑餓

將高優(yōu)先級組報文M2的發(fā)送周期改為3ms，低優(yōu)先級組報文M3的發(fā)送周期為改6ms，其它所有實驗參數(shù)均與CAN 總線正常工作時一樣。如圖7 所示，未進行反轉(zhuǎn)的固定優(yōu)先級調(diào)度在實驗中產(chǎn)生饑餓，導致低優(yōu)先級組報文M4一直沒有占用總線的機會，一直處于饑餓當中，故低優(yōu)先級組報文的到達率S 小于1。而此時有反轉(zhuǎn)的非搶占式RM算法調(diào)度能夠避免CAN 總線中低優(yōu)先級報文產(chǎn)生饑餓問題，使得兩組報文在其周期內(nèi)均能得到占用總線的機會。此時低優(yōu)先級組報文的響應(yīng)時間T 得到明顯降低，低優(yōu)先級組的到達率S 仍保持為1。

Fig.5 Reverse transmission queue situation when CAN bus works normally圖5 CAN 總線正常工作時有無反轉(zhuǎn)發(fā)送隊列情況

Fig.6 Reverse transmission queue situation when CAN bus works at full utilization圖6 CAN 總線滿利用率工作時有無反轉(zhuǎn)發(fā)送隊列情況

Fig.7 Reverse transmission queue situation when CAN is in starvation圖7 CAN 產(chǎn)生饑餓時有無反轉(zhuǎn)發(fā)送隊列情況

3.4 擴大仿真

為進一步驗證避免饑餓的高優(yōu)先級反轉(zhuǎn)模型與正常固定優(yōu)先級的優(yōu)勢，將實驗中的報文數(shù)量擴大，設(shè)置報文數(shù)量n 為20，每組報文數(shù)量設(shè)置為10，仿真時間為1s，對比低優(yōu)先級組在未進行反轉(zhuǎn)的固定優(yōu)先級調(diào)度和有反轉(zhuǎn)的非搶占式RM 算法調(diào)度下的到達率和平均響應(yīng)時間。

平均響應(yīng)時間如圖8 所示，分別驗證在不同CAN 總線利用率下有反轉(zhuǎn)的非搶占式RM 算法調(diào)度和無反轉(zhuǎn)的CAN總線固定優(yōu)先級調(diào)度對低優(yōu)先級組平均響應(yīng)時間的影響。當CAN 總線利用率逐漸增加時，不管低優(yōu)先級組處于未進行反轉(zhuǎn)的固定優(yōu)先級調(diào)度，還是有反轉(zhuǎn)的非搶占式RM 算法調(diào)度，其平均響應(yīng)時間都在不斷增加，但是有反轉(zhuǎn)的非搶占式RM 算法調(diào)度的平均響應(yīng)時間總是小于未反轉(zhuǎn)的CAN 總線正常調(diào)度的平均響應(yīng)時間。

到達率實驗如圖9 所示，對CAN 總線由正常到產(chǎn)生饑餓、有反轉(zhuǎn)的非搶占式RM 算法調(diào)度和無反轉(zhuǎn)的CAN 總線固定優(yōu)先級調(diào)度對低優(yōu)先級組到達率的影響進行分析。若CAN 總線利用率小于等于100 時，有無反轉(zhuǎn)對低優(yōu)先級組的到達率無顯著影響；當CAN 總線利用率大于100 時，CAN 總線存在處于饑餓狀態(tài)報文。當CAN 總線利用率逐漸增加時，無反轉(zhuǎn)的CAN 總線固定優(yōu)先級調(diào)度下的低優(yōu)先級組到達率持續(xù)減少，直到為0，此時低優(yōu)先級組中沒有一個報文能夠再占用CAN 總線。與之相反，在有反轉(zhuǎn)的非搶占式RM 算法調(diào)度下的低優(yōu)先級組到達率則基本維持不變。

Fig.8 Average response time of low priority group with or without inversion圖8 低優(yōu)先級組有無反轉(zhuǎn)的平均響應(yīng)時間

Fig.9 Arrival rate of low priority group with or without inversion圖9 低優(yōu)先級組有無反轉(zhuǎn)的到達率情況

4 結(jié)語

針對CAN 總線存在的饑餓問題，本文提出一個避免饑餓的高優(yōu)先級反轉(zhuǎn)算法并建立模型。在滿足優(yōu)先級反轉(zhuǎn)條件下使高優(yōu)先級反轉(zhuǎn)為低優(yōu)先級。仿真實驗結(jié)果表明，在不同的CAN 總線利用率下，該模型能夠通過改善CAN 總線中周期任務(wù)的平均響應(yīng)時間來減少饑餓。當CAN 總線利用率超過100 時，有反轉(zhuǎn)的低優(yōu)先級組到達率能夠保持正常，表明避免饑餓的高優(yōu)先級反轉(zhuǎn)算法工作良好。

避免饑餓的高優(yōu)先級反轉(zhuǎn)算法雖然有效，但高優(yōu)先級組在一定時間內(nèi)的發(fā)送次數(shù)是固定值，大于該固定值后才能進行動態(tài)反轉(zhuǎn)，在此期間沒有考慮低優(yōu)先級組的饑餓程度。后續(xù)可圍繞該固定值與低優(yōu)先級組饑餓程度的關(guān)系進行研究。