基于CAN FD 總線的動(dòng)靜態(tài)調(diào)度算法研究

趙雅文，周美嬌，吳俊鵬

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

0 引言

目前國(guó)內(nèi)外主流調(diào)度算法大致分為3 種：①靜態(tài)調(diào)度算法，如固定優(yōu)先級(jí)算法（Fixed Priority Schedule Algorithm，F(xiàn)PA）［5］；②動(dòng)態(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ù)報(bào)文調(diào)度過(guò)程中的不同要求，可選擇合適的算法進(jìn)行調(diào)度。

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

1 CAN FD 總線概述

1.1 CAN FD 總線協(xié)議

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

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

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

1.2 幀編碼

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

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

1.3 標(biāo)識(shí)符編碼

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

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

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

Fig.2 CAN FD identifier encoding圖2 CAN FD 標(biāo)識(shí)符編碼

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

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

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

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

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

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

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

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

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

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

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

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

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

3 實(shí)驗(yàn)仿真

3.1 仿真模型

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

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

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

3.2 實(shí)驗(yàn)結(jié)果

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

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

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

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

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

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

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

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

4 結(jié)語(yǔ)

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