一種新型時間觸發CAN消息動態調度算法的設計及實現*

魏 磊，戴宗賢

（1.阜陽師范大學物理與電子工程學院，安徽阜陽 236037；2.重慶市計量質量檢測研究院，重慶 401123）

0 引言

CAN現場總線在汽車、工業現場、樓宇自動化等領域得到廣泛應用[1-4]。CAN總線采用非破壞性仲裁進行消息調度，同一總線網絡中所有消息都可競爭總線控制權，最高優先級的消息獲勝并被發送至總線。該仲裁機制確保了高優先級的消息實時性。但是，因總線競爭、消息碰撞導致低優先級消息傳輸延遲，甚至被阻塞，消息傳輸至目標設備的時刻具有不確定性，制約了CAN總線技術在高實時性場合的應用。

針對該問題，Bosch公司推出了基于時間觸發的TTCAN協議，該協議將消息劃分為周期性消息和事件性消息。周期性消息由預先制定的調度表調度，其發送活動是在各自的獨占窗內進行，在此期間總線不會被其他消息搶占，確保了周期性消息的延遲確定性和實時性，提高了總線利用率[5]。但是，TTCAN協議依然存在如下弊端[6-8]：一是在一個基本周期的所有獨占窗時段內，事件性消息無法獲得總線控制權，該類消息傳輸延遲大大增加，且具有不確定性。特別是在高負載率時，事件性消息的傳輸延遲問題將尤為突出。然而，事件性消息往往是系統中具有緊迫性的硬實時消息，該類消息傳輸延遲的不確定性將增加網絡通訊的風險。二是一幀周期性消息的傳輸時間不能充滿獨占窗，但剩余的時間片內又不允許事件性消息控制總線，存在對總線資源的浪費。

針對上述問題，本文提出一種新的基于時間觸發的CAN總線動態調度算法，旨在確保周期性消息傳輸實時性的基礎上，大大減少事件性消息的延遲。此外，針對算法在嵌入式系統上實現的關鍵技術問題進行了探討，討論基于STM32單片機的算法實現方法。

1 新型時間觸發CAN消息調度算法

1.1 算法基本思想

算法基本思想包括以下兩點。

（1）改變TTCAN協議中用于周期性消息發送窗口的獨占模式，并將其重構。整合TTCAN中一個基本周內的所有獨占窗為一個整體（而非像TTCAN中，各獨占窗彼此獨立），該時間段稱之為周期性時段。在周期性時段內，周期性消息采用基于時間觸發的機制進行調度。但是，在該時間段內，事件性消息可參與總線仲裁。

（2）為防止低優先級事件性消息被長時間阻塞，對事件性消息采用最低松弛度優先調度算法（Least Laxity First Scheduling Algorithm，LLF算法）進行調度。

1.2 調度矩陣

算法分為靜態調度和動態調度兩部分，靜態調度基于TTCAN協議中的調度矩陣，其矩陣結構如圖1所示。

圖1 系統調度矩陣結構

一個矩陣周期由若干基本周期（Basic Cycle，BC）組成，基本周期由若干消息窗口組成。每個基本周期開始于由主節點發出的同步消息，同步消息用于同步各從節點的調度時鐘。在各個周期標志到來的時刻，預設的周期性消息被發送至總線，而且每個消息窗口只有一個周期性消息被發送至總線。特別強調，周期性窗口內事件性消息的發送不受限制。因而，可以在兩個相鄰周期性消息發送的間隙發送事件性消息，從而大大降低事件性消息的排隊等待時間，具體如圖2所示。

圖2 事件性消息發送過程

從圖中可知，假設有一事件性消息在t1時刻產生，根據TTCAN協議，消息至少要延遲到t4時刻發送，則其延遲時間至少為t4-t1。根據本文算法，則t1時刻即可發送。在周期性消息的空閑事件片內發送事件性消息，不僅增加了總線利用率，而且大大降低了事件性消息的延遲。

隨之而來的問題是，取消TTCAN的獨占窗模式可能會使周期性消息的傳輸被延遲。如圖2所示，假設在t2時刻產生了事件性消息，該消息將占用總線控制權，且在t3時刻才能完成消息發送，周期性消息B將會被延遲。為保證周期性消息的實時性，設定周期性消息的優先級高于事件性消息，那么事件性消息最多阻塞周期性消息一幀的時間，這種延遲是可以接受的。

1.2.1 調度矩陣參數計算

調度矩陣是本文算法的核心，調度矩陣設計由矩陣規模的設計和周期性消息在矩陣內排列的設計兩部分組成。矩陣規模的設計需要計算的參數分別是：矩陣周期、基本周期、矩陣行數、矩陣列數，各參數由如下方法確定。

設CAN總線中的所有周期性消息的周期按照從小到大的順序排列，得到一個周期集合{ }T1，T2，T3，…，Tm。

（1）矩陣周期

矩陣取上述周期集合的最小公倍數，矩陣周期用TMC表示。

式中：[]為取最小公倍數。

這樣，每個周期性消息在一個矩陣周期內被調度次數為整數。

（2）基本周期

基本周期為各個周期的最大公約數，用TBC表示。

式中：()為取最大公約數。

（3）矩陣行數

矩陣行數用L表示。

（4）矩陣周期列數

設周期性消息總數為n，周期性消息中最長消息的傳輸時間為tmax，則各參數應滿足：

否則，需要增大波特率。

設周期性消息平均傳輸時間為ta，事件性消息總傳輸時間為tc，同步消息傳輸時間為ts，則極端情況下，基本周期內事件性消息的可傳輸率為：

若λ值太小，會使得在負載量較高時事件性消息的傳輸延遲增大，甚至不可調度，這時需要增大波特率以增大?值，為事件性消息預留更多總線帶寬。

1.2 .2周期性消息裝載

矩陣周期規模確定后，就要考慮周期性消息在調度矩陣中的排列，即周期性消息的裝載，裝載原則為周期性消息在各基本周期的數目基本一致，以避免總線負載率的較大波動。具體裝載方法如下。首先將周期性消息按照周期大小進行分類，把相同周期的消息分為一組，分組后的消息集合為：中，消息Mki的周期為Tk，設Tk TBC=ak。消息的裝載根據周期大小，從小到大依次開始進行，對于周期為Tk的消息，每隔ak個基本周期裝載1次。相同周期的消息均勻分布在不同的基本周期內，使得各基本周期的負載率基本一致。

為了讓同步消息能夠及時地發送到總線上，在每個基本周期的末尾設置一個空閑窗口，在空閑窗口內從節點禁止消息發送，以等待接收來自主節點的同步消息。

2 事件性消息動態調度及嵌入式實現方法

在CAN總線的負載量較高時，低優先級事件性消息可能會被阻塞而錯過截止期，為保證其實時性，本文采用LLF算法對事件性消息進行實時調度。LLF算法根據消息的緊急程度（松弛度）確定消息的優先級，松弛度越低的消息優先級越高[9]。消息的松弛度為ΔtL，定義消息的生成時刻與截止時刻之間的時間段長度為有效生存期，用Δtp表示，消息從搶占總線到發送成功所需的時間為ti，則消息的松弛度ΔtL=Δtp-ti。

同時，競爭總線的消息因松弛度不同，各消息的優先級會被動態調整。CAN消息是基于標識符仲裁進行調度的，事件性消息的動態調度需要動態調整其標識符。但是，CAN消息的標識符是消息的ID，是對消息種類及功能識別的標識，也是各節點的CAN收發器進行消息濾波的依據，對標識符的更改將影響這些功能。如何統籌CAN標識符的動態變化和消息的識別及濾波，是LLF算法在CAN總線應用的關鍵。本文基于STM32單片機論述LLF算法在嵌入式CAN總線中實現的方法。

嵌入式系統以低成本、高效便捷的優勢廣泛應用在現場總線的各個領域[10-12]。STM32是基于ARMCortex-M3內核的一款高性能嵌入式微控制器，已在各個領域得到廣泛應用。STM32內部自帶bxCAN收發控制器。bxCAN具有3個發送郵箱和2個三級深度的接收FIFO，并且具有可屏蔽、位寬可變的消息過濾器組，用于對總線消息的硬件過濾，這種硬件過濾機制大大節約了CPU開銷。過濾器組具有對CAN消息標識符的部分位進行選擇性過濾能力，即可以只過濾某些指定的位，而不關心其余位的標識符能否與過濾器匹配。借助該功能可實現LLF算法對CAN消息的調度。

因事件性消息可在周期性消息窗口內發送，為了防止事件性消息長時間阻塞周期性消息，周期性消息的優先級要高于事件性消息，設定周期性消息標識符的最高位為0，事件性消息標識符的最高位為1。將余下的標識符位分為兩部分，后M位設定為固定部分，用于CAN收發器過濾器組的過濾及消息功能識別，那么系統中可調度的消息數目為2M。其余標識符位可變部分，定義由這些可變位組成的數值大小為IDdynamic，用于LLF算法的動態調整。

設系統中所有消息的最大有效生存期為Δtpmax，則：

IDdynamic的計算由CAN網絡中各個子節點自行調度。為保證最低松弛度的消息能夠被及時地發送，對消息動態ID部分的調整應保持一定頻率，而且應確保即使具有最小有效生存期的消息也能夠被多次提升優先級，以保證其實時發送。消息ID的調整周期應設定得比所有消息傳輸時間的最小值還要小。對事件性消息標識符的動態調整由STM32的定時器控制。

3 結束語

本文提出了一種新型基于時間觸發CAN消息實時調度算法，該算法在繼承了TTCAN時間觸發機制優勢的基礎上，對其不足之處進行改進，將其用于周期性消息發送的獨占窗改進為事件性消息也可調度的周期性消息窗，大大降低了事件性消息的延遲，并詳細論述了調度矩陣的設計方法。此外，將動態調度思想引入TTCAN協議，對事件性消息采用LLF動態調度算法，以確保CAN總線能夠適用于瞬時負載率較大的場合。