基于CAN FD 總線的動靜態調度算法研究

趙雅文，周美嬌，吳俊鵬

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

0 引言

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

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

1 CAN FD 總線概述

1.1 CAN FD 總線協議

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

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

Fig.1 CAN FD extends data frames圖1 CAN FD 擴展數據幀

1.2 幀編碼

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

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

1.3 標識符編碼

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

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

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

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

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

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

1.4 最壞響應時間

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

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

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

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

2 FPS 調度與EDF調度

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

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

EDF 是一種動態搶占式調度算法［19］，其報文優先級計算方式是對報文截止時間進行編碼，采用不同編碼方式得出的計算結果會有所不同，通常采用以下平均分區編碼方式。

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

Fig.3 Schematic diagram of mean zoning圖3 平均分區示意圖

3 實驗仿真

3.1 仿真模型

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

Fig.4 CAN FD system network planning圖4 CAN FD 系統網絡規劃

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

3.2 實驗結果

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

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

Table 1 Message parameters表1 報文參數單位：ms

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

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

Fig.5 Message scheduling results of BCM and IPC圖5 電池管理節點與儀表節點報文調度結果

Fig.6 Message scheduling results of Gateway and Switch圖6 網關節點與開關節點報文結果

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

4 結語

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