趙雅文，周美嬌，吳俊鵬

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

0 引言

目前國內(nèi)外主流調(diào)度算法大致分為3 種：①靜態(tài)調(diào)度算法，如固定優(yōu)先級算法（Fixed Priority Schedule Algorithm，F(xiàn)PA）［5］；②動態(tài)調(diào)度算法，如最早截止期優(yōu)先算法（Earli?est-Deadline-First，EDF）［6］和最小松弛優(yōu)先算 法（Least-Laxity-First，LLF）［7］；③混合調(diào)度算法（Mixed Traffic Sched?uler，MTS）［8］。根據(jù)報文調(diào)度過程中的不同要求，可選擇合適的算法進行調(diào)度。

以上文獻中關(guān)于報文響應(yīng)時間的研究為本文分析CAN FD 報文的最壞響應(yīng)時間奠定了一定基礎(chǔ)，但均未將具體的調(diào)度算法應(yīng)用到CAN FD 總線網(wǎng)絡(luò)中進行驗證，以對比不同調(diào)度算法的優(yōu)劣。本文采用固定優(yōu)先級算法和最早截止期優(yōu)先算法對CAN FD 總線報文進行調(diào)度研究，通過CANoe 仿真平臺搭建仿真模型，對兩種算法進行仿真對比實驗。實驗結(jié)果表明，最早截止期優(yōu)先算法對報文的優(yōu)先級分配更加靈活，在低速傳輸情況下，報文可以實現(xiàn)全部傳輸。

1 CAN FD 總線概述

1.1 CAN FD 總線協(xié)議

CAN FD 總線是一種基于CAN2.0 協(xié)議，且與CAN 共享物理層的現(xiàn)場總線，遵循ISO/OSI 網(wǎng)絡(luò)標準模型。其彌補了CAN 總線通信速率低的缺點，同時具有基于事件觸發(fā)、采用短幀格式、遵循非破壞性逐位仲裁規(guī)則等特點。CAN FD 總線采用載波監(jiān)聽多路訪問/沖突避免（Carrier Sense Multiple Access with Collision Avoidance，CSMA/CA）的媒體訪問方式，還可以設(shè)置多種拓撲結(jié)構(gòu)，目前在汽車行業(yè)應(yīng)用最多的是總線型拓撲結(jié)構(gòu)。

CAN FD 總線具有3 種報文幀格式，即數(shù)據(jù)幀、出錯幀和超載幀，按照標識符長度又可分為標準幀和擴展幀。CAN FD 數(shù)據(jù)幀相較于CAN 數(shù)據(jù)幀新增了擴展數(shù)據(jù)長度位（EDL 位）、比特率開關(guān)位（BRS 位）和錯誤狀態(tài)指示位（ESI位），同時采用了新的DLC 編碼方式與CRC 算法（CRC 場可擴展至17、21、26 位）。CAN FD 總線以非常高的安全水平支持分布式實時控制，在新一代汽車應(yīng)用中發(fā)揮著重要作用［9］。本文基于具有29 位標識符的擴展數(shù)據(jù)幀進行研究，CAN FD 擴展數(shù)據(jù)幀格式如圖1 所示。

Fig.1 CAN FD extends data frames圖1 CAN FD 擴展數(shù)據(jù)幀

1.2 幀編碼

不歸零（No Return Zero，NRZ）是目前使用較為廣泛的一種編碼方式，CAN FD 總線便是采用該種編碼方式。此外，為避免總線連續(xù)接收到相同的比特位而造成收發(fā)雙方無法同步，在NRZ 編碼時會使用位填充方法對幀起始與CRC 分隔符之間進行編碼，即當(dāng)發(fā)送的比特流中有連續(xù)5位極性相同的比特位出現(xiàn)時，便會在第5 位后插入1 個極性相反的填充進行界定，以預(yù)防突發(fā)錯誤，保證接收方有足夠時間進行同步。

CAN FD 總線在CRC 序列中采用新的位填充規(guī)則［10］，即在固定位置插入填充位。具體填充方法為：首先在CRC序列第1 位之前的固定位置填充1 位，然后在CRC 序列每4位后插入1 個填充位，填充位的極性與前1 位相反。接收器在接收到比特流時，應(yīng)主動將填充位從比特流中丟棄以進行CRC 校驗。如果填充位具有與其前1 位相同的極性，則應(yīng)檢測出填充錯誤。CAN FD 總線中CRC 序列的固定填充位數(shù)等于CAN 總線所產(chǎn)生的最大填充位數(shù)。

1.3 標識符編碼

在總線通信過程中，需要對報文標識符進行編碼設(shè)計以保證CAN FD 總線通信的實時性，該步驟是應(yīng)用層協(xié)議與應(yīng)用系統(tǒng)設(shè)計的重要內(nèi)容之一。報文標識符的作用主要體現(xiàn)在兩方面：一是在接收時過濾報文，二是定義報文分配優(yōu)先級，用于總線競爭。CAN FD 報文標識符的編碼設(shè)計需遵循以下原則［11］：①每個報文的標識符是唯一的；②預(yù)留的節(jié)點設(shè)備應(yīng)能滿足總線上的最大節(jié)點個數(shù)，報文空間也要能容納相應(yīng)節(jié)點內(nèi)的報文個數(shù)；③編碼方式應(yīng)簡單實用；④編碼后的標識符能夠與應(yīng)用層協(xié)議相兼容；⑤優(yōu)先級越高的報文標識符值越小；⑥遵從CAN2.0A 和CAN2.0B 規(guī)范，7 個最高位必須不能全都是1。

本文研究對象是具有29 位標識符的擴展CAN FD 數(shù)據(jù)幀，分別對擴展幀的高11 位以及低18 位進行編碼配置（見圖2），具體方案設(shè)計如下：

基于對亞洲航線郵輪通關(guān)相關(guān)的現(xiàn)狀分析、政策及制度總結(jié)、模型構(gòu)建以及歸納整理，給出以下七點我國航線郵輪運營便利化建議如下：

Fig.2 CAN FD identifier encoding圖2 CAN FD 標識符編碼

首先，對可變優(yōu)先級的高11 位標識符進行配置。預(yù)留最高兩位標識符用于判斷報文類型，同時要滿足高7 位不能全為1 的設(shè)計規(guī)則。本文假設(shè)00 表示強實時報文，01 表示弱實時報文，10 表示非實時報文。第26 至18 位用于表示報文的優(yōu)先級提升段，根據(jù)報文的截止時間采用動態(tài)編碼方式進行配置。

其次，標識符的第17 至13 位用于表示節(jié)點號，第12 至9 位用于表示報文號，余下6 位用于表示目的地址，最后3位作為保留位，至此完成標識符編碼。

1.4 最壞響應(yīng)時間

由于多個節(jié)點的存在，單路CAN FD 總線在報文傳輸過程中遇到節(jié)點同時訪問總線時，會不可避免地發(fā)生沖突。此時報文傳輸需要根據(jù)自身優(yōu)先級競爭總線，獲得總線使用權(quán)，因此會導(dǎo)致報文延遲傳送。CAN FD 總線的報文傳輸延時主要受4 個方面影響：報文幀、控制器、軟件與媒體訪問［12］。由于控制器和軟件造成的延時微乎其微，可以不用在報文響應(yīng)時間中體現(xiàn)，因此本文主要分析幀延時與媒體訪問延時。

幀延時即報文的傳輸延遲，是一種由信息串行化導(dǎo)致的延時，時延長度由幀長度和總線傳輸速率決定，其中幀延時=幀長度/波特率［13］。這種延時在傳輸少量報文時對報文的最壞響應(yīng)時間影響最大。媒體訪問延時分為兩種情況，一是總線在使用中且仍要被占用的時間，另一種是總線被高優(yōu)先級報文占用，低優(yōu)先級報文等待釋放的時間，即排隊延遲。

對于擴展幀格式的CAN FD 報文，其最壞情況響應(yīng)時間主要針對傳輸時遇到位填充的場景。最壞情況下即按照位填充的規(guī)則，每4 位后填充1 位，直至CRC 分隔符。長度為p 個字節(jié)的報文幀的最壞響應(yīng)時間為：

其中，τcan為CAN 總線的位傳輸速率，τfd為CAN FD 總線的位傳輸速率。

2 FPS 調(diào)度與EDF調(diào)度

固定優(yōu)先級調(diào)度算法（Fixed Priority Scheduling，F(xiàn)PS）由靜態(tài)調(diào)度算法演變而來［14］，是總線調(diào)度時經(jīng)常用到的一種算法。該算法根據(jù)報文周期或截止期，在報文調(diào)度前分配好優(yōu)先級，保證按照優(yōu)先級進行調(diào)度。應(yīng)用較多的固定優(yōu)先級算法為單調(diào)速率算法（Rate Monotonic Scheduling，RMS）［15］和截止期單調(diào)算法（Deadline Monotonic Schedul?ing，DMS）［16］兩種，具有額外開銷小和實現(xiàn)簡單的優(yōu)點，但存在對事件觸發(fā)的報文處理不靈活、容錯能力差的缺點［17］。

最早截止期優(yōu)先調(diào)度算法（Earliest-Deadline-First，EDF）根據(jù)報文的絕對截止時間動態(tài)分配優(yōu)先級，絕對截止時間越小則分配優(yōu)先級越高，該算法目前較為常用［18］。EDF 調(diào)度算法在報文調(diào)度時能實時計算報文優(yōu)先級，滿足系統(tǒng)對信息傳遞的實時性要求。

EDF 是一種動態(tài)搶占式調(diào)度算法［19］，其報文優(yōu)先級計算方式是對報文截止時間進行編碼，采用不同編碼方式得出的計算結(jié)果會有所不同，通常采用以下平均分區(qū)編碼方式。

對于一組報文{m1,m2,m3,…,mn}，假設(shè)它們的相對截止時間從小到大依次排列為{d1,d2,d3,…,dmax}，以報文的最大相對截止時間dmax為上限將時間軸均分成k段，則每段區(qū)間長為dmax/k。平均分區(qū)情況如圖3 所示。

Fig.3 Schematic diagram of mean zoning圖3 平均分區(qū)示意圖

3 實驗仿真

3.1 仿真模型

本文采用實驗對比分析CAN FD 網(wǎng)絡(luò)在FPS 算法和EDF 算法下的調(diào)度效果。通過CANoe 軟件搭建CAN FD 網(wǎng)絡(luò)模型［20］，由4 個節(jié)點組成，分別為電池管理節(jié)點（BCM）、網(wǎng)關(guān)節(jié)點（Gateway）、儀表節(jié)點（IPC）以及開關(guān)節(jié)點（Switch），均在1 條CAN FD 總線上，具體如圖4 所示。

Fig.4 CAN FD system network planning圖4 CAN FD 系統(tǒng)網(wǎng)絡(luò)規(guī)劃

各個節(jié)點根據(jù)功能不同共傳遞15 個報文。電池管理節(jié)點包含3 個電池狀態(tài)報文，均為周期性報文。網(wǎng)關(guān)節(jié)點包含前后左右車門狀態(tài)4 個報文以及車燈、車速2 個周期性報文。儀表節(jié)點包含引擎轉(zhuǎn)速、溫度、油量以及引擎錯誤狀態(tài)4 個周期性報文。在仿真周期性報文時只考慮其最壞相應(yīng)傳輸時間，開關(guān)節(jié)點只收發(fā)開和關(guān)2 個非周期性報文。所有周期性報文數(shù)據(jù)長度均設(shè)置為8 字節(jié)，非周期性報文數(shù)據(jù)長度為1 字節(jié)。具體報文參數(shù)如表1 所示。

3.2 實驗結(jié)果

根據(jù)報文參數(shù)構(gòu)造仿真數(shù)據(jù)庫中的報文與信號，編寫CAPL（CAN Access Programming Language）腳本，在傳輸速率為250Kbit/s 和500Kbit/s 的情況下分別進行仿真實驗。FPS 算法下報文實際傳輸結(jié)果如表2 所示，EDF 算法下報文實際傳輸結(jié)果如表3 所示。

從表2、表3 結(jié)果可以看出，當(dāng)采用FPS 算法進行調(diào)度時，Vehicle 類報文由于事先分配的報文優(yōu)先級較低，在優(yōu)先級仲裁獲取總線訪問權(quán)時一直失敗，無法占用CAN FD總線，最終導(dǎo)致發(fā)送失敗，錯過報文截止期。而當(dāng)采用EDF調(diào)度算法時，所有報文都可以被合理地安排優(yōu)先級，可占用總線且均能在截止期前正確發(fā)出，滿足了報文的實時性要求。電池管理節(jié)點與儀表節(jié)點報文傳送結(jié)果與實時顯示如圖5 所示，網(wǎng)關(guān)節(jié)點與開關(guān)節(jié)點報文傳送結(jié)果如圖6所示。

Table 1 Message parameters表1 報文參數(shù)單位：ms

Table 2 Message transmission results of FPS algorithm表2 FPS 算法下報文傳輸結(jié)果

Table 3 Message transmission results of EDF algorithm表3 EDF 算法下報文傳輸結(jié)果

Fig.5 Message scheduling results of BCM and IPC圖5 電池管理節(jié)點與儀表節(jié)點報文調(diào)度結(jié)果

Fig.6 Message scheduling results of Gateway and Switch圖6 網(wǎng)關(guān)節(jié)點與開關(guān)節(jié)點報文結(jié)果

由圖中可知，在CAN FD 總線系統(tǒng)中，相較于靜態(tài)調(diào)度算法FPS，采用動態(tài)調(diào)度算法EDF 進行調(diào)度時靈活性更高，能夠使報文在截止期前發(fā)出，保證報文傳送實時性。

4 結(jié)語

本文以CAN FD 總線傳輸理論為基礎(chǔ)，分析了報文傳輸時的最壞響應(yīng)時間。通過CANoe 仿真平臺，分別對FPS算法和EDF 算法在波特率為250Kbit/s 和500Kbit/s 的情況下進行多次仿真實驗。結(jié)果顯示，采用FPS 算法時15 個報文最佳情況下只能正常傳送8 個（53%），而采用EDF 算法可以確保15 個報文100%傳輸。相較于FPS 算法，EDF 算法在報文優(yōu)先級分配時更加靈活有效，能夠避免因錯過報文截止期而無法進行調(diào)度的情況。此外，CAN FD 總線因具有數(shù)據(jù)傳輸速率快、總線利用率高等優(yōu)點，非常適合當(dāng)今智能汽車產(chǎn)業(yè)需傳輸大量信號的要求。然而，本文仿真實驗是建立在比較理想的條件上，缺乏硬件節(jié)點的實際驗證，今后需加深該方面研究。