一種新型時(shí)間觸發(fā)CAN消息動(dòng)態(tài)調(diào)度算法的設(shè)計(jì)及實(shí)現(xiàn)*

魏 磊，戴宗賢

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

0 引言

CAN現(xiàn)場總線在汽車、工業(yè)現(xiàn)場、樓宇自動(dòng)化等領(lǐng)域得到廣泛應(yīng)用[1-4]。CAN總線采用非破壞性仲裁進(jìn)行消息調(diào)度，同一總線網(wǎng)絡(luò)中所有消息都可競爭總線控制權(quán)，最高優(yōu)先級(jí)的消息獲勝并被發(fā)送至總線。該仲裁機(jī)制確保了高優(yōu)先級(jí)的消息實(shí)時(shí)性。但是，因總線競爭、消息碰撞導(dǎo)致低優(yōu)先級(jí)消息傳輸延遲，甚至被阻塞，消息傳輸至目標(biāo)設(shè)備的時(shí)刻具有不確定性，制約了CAN總線技術(shù)在高實(shí)時(shí)性場合的應(yīng)用。

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

針對(duì)上述問題，本文提出一種新的基于時(shí)間觸發(fā)的CAN總線動(dòng)態(tài)調(diào)度算法，旨在確保周期性消息傳輸實(shí)時(shí)性的基礎(chǔ)上，大大減少事件性消息的延遲。此外，針對(duì)算法在嵌入式系統(tǒng)上實(shí)現(xiàn)的關(guān)鍵技術(shù)問題進(jìn)行了探討，討論基于STM32單片機(jī)的算法實(shí)現(xiàn)方法。

1 新型時(shí)間觸發(fā)CAN消息調(diào)度算法

1.1 算法基本思想

算法基本思想包括以下兩點(diǎn)。

（1）改變TTCAN協(xié)議中用于周期性消息發(fā)送窗口的獨(dú)占模式，并將其重構(gòu)。整合TTCAN中一個(gè)基本周內(nèi)的所有獨(dú)占窗為一個(gè)整體（而非像TTCAN中，各獨(dú)占窗彼此獨(dú)立），該時(shí)間段稱之為周期性時(shí)段。在周期性時(shí)段內(nèi)，周期性消息采用基于時(shí)間觸發(fā)的機(jī)制進(jìn)行調(diào)度。但是，在該時(shí)間段內(nèi)，事件性消息可參與總線仲裁。

（2）為防止低優(yōu)先級(jí)事件性消息被長時(shí)間阻塞，對(duì)事件性消息采用最低松弛度優(yōu)先調(diào)度算法（Least Laxity First Scheduling Algorithm，LLF算法）進(jìn)行調(diào)度。

1.2 調(diào)度矩陣

算法分為靜態(tài)調(diào)度和動(dòng)態(tài)調(diào)度兩部分，靜態(tài)調(diào)度基于TTCAN協(xié)議中的調(diào)度矩陣，其矩陣結(jié)構(gòu)如圖1所示。

圖1 系統(tǒng)調(diào)度矩陣結(jié)構(gòu)

一個(gè)矩陣周期由若干基本周期（Basic Cycle，BC）組成，基本周期由若干消息窗口組成。每個(gè)基本周期開始于由主節(jié)點(diǎn)發(fā)出的同步消息，同步消息用于同步各從節(jié)點(diǎn)的調(diào)度時(shí)鐘。在各個(gè)周期標(biāo)志到來的時(shí)刻，預(yù)設(shè)的周期性消息被發(fā)送至總線，而且每個(gè)消息窗口只有一個(gè)周期性消息被發(fā)送至總線。特別強(qiáng)調(diào)，周期性窗口內(nèi)事件性消息的發(fā)送不受限制。因而，可以在兩個(gè)相鄰周期性消息發(fā)送的間隙發(fā)送事件性消息，從而大大降低事件性消息的排隊(duì)等待時(shí)間，具體如圖2所示。

圖2 事件性消息發(fā)送過程

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

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

1.2.1 調(diào)度矩陣參數(shù)計(jì)算

調(diào)度矩陣是本文算法的核心，調(diào)度矩陣設(shè)計(jì)由矩陣規(guī)模的設(shè)計(jì)和周期性消息在矩陣內(nèi)排列的設(shè)計(jì)兩部分組成。矩陣規(guī)模的設(shè)計(jì)需要計(jì)算的參數(shù)分別是：矩陣周期、基本周期、矩陣行數(shù)、矩陣列數(shù)，各參數(shù)由如下方法確定。

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

（1）矩陣周期

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

式中：[]為取最小公倍數(shù)。

這樣，每個(gè)周期性消息在一個(gè)矩陣周期內(nèi)被調(diào)度次數(shù)為整數(shù)。

（2）基本周期

基本周期為各個(gè)周期的最大公約數(shù)，用TBC表示。

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

（3）矩陣行數(shù)

矩陣行數(shù)用L表示。

（4）矩陣周期列數(shù)

設(shè)周期性消息總數(shù)為n，周期性消息中最長消息的傳輸時(shí)間為tmax，則各參數(shù)應(yīng)滿足：

否則，需要增大波特率。

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

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

1.2 .2周期性消息裝載

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

為了讓同步消息能夠及時(shí)地發(fā)送到總線上，在每個(gè)基本周期的末尾設(shè)置一個(gè)空閑窗口，在空閑窗口內(nèi)從節(jié)點(diǎn)禁止消息發(fā)送，以等待接收來自主節(jié)點(diǎn)的同步消息。

2 事件性消息動(dòng)態(tài)調(diào)度及嵌入式實(shí)現(xiàn)方法

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

同時(shí)，競爭總線的消息因松弛度不同，各消息的優(yōu)先級(jí)會(huì)被動(dòng)態(tài)調(diào)整。CAN消息是基于標(biāo)識(shí)符仲裁進(jìn)行調(diào)度的，事件性消息的動(dòng)態(tài)調(diào)度需要?jiǎng)討B(tài)調(diào)整其標(biāo)識(shí)符。但是，CAN消息的標(biāo)識(shí)符是消息的ID，是對(duì)消息種類及功能識(shí)別的標(biāo)識(shí)，也是各節(jié)點(diǎn)的CAN收發(fā)器進(jìn)行消息濾波的依據(jù)，對(duì)標(biāo)識(shí)符的更改將影響這些功能。如何統(tǒng)籌CAN標(biāo)識(shí)符的動(dòng)態(tài)變化和消息的識(shí)別及濾波，是LLF算法在CAN總線應(yīng)用的關(guān)鍵。本文基于STM32單片機(jī)論述LLF算法在嵌入式CAN總線中實(shí)現(xiàn)的方法。

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

因事件性消息可在周期性消息窗口內(nèi)發(fā)送，為了防止事件性消息長時(shí)間阻塞周期性消息，周期性消息的優(yōu)先級(jí)要高于事件性消息，設(shè)定周期性消息標(biāo)識(shí)符的最高位為0，事件性消息標(biāo)識(shí)符的最高位為1。將余下的標(biāo)識(shí)符位分為兩部分，后M位設(shè)定為固定部分，用于CAN收發(fā)器過濾器組的過濾及消息功能識(shí)別，那么系統(tǒng)中可調(diào)度的消息數(shù)目為2M。其余標(biāo)識(shí)符位可變部分，定義由這些可變位組成的數(shù)值大小為IDdynamic，用于LLF算法的動(dòng)態(tài)調(diào)整。

設(shè)系統(tǒng)中所有消息的最大有效生存期為Δtpmax，則：

IDdynamic的計(jì)算由CAN網(wǎng)絡(luò)中各個(gè)子節(jié)點(diǎn)自行調(diào)度。為保證最低松弛度的消息能夠被及時(shí)地發(fā)送，對(duì)消息動(dòng)態(tài)ID部分的調(diào)整應(yīng)保持一定頻率，而且應(yīng)確保即使具有最小有效生存期的消息也能夠被多次提升優(yōu)先級(jí)，以保證其實(shí)時(shí)發(fā)送。消息ID的調(diào)整周期應(yīng)設(shè)定得比所有消息傳輸時(shí)間的最小值還要小。對(duì)事件性消息標(biāo)識(shí)符的動(dòng)態(tài)調(diào)整由STM32的定時(shí)器控制。

3 結(jié)束語

本文提出了一種新型基于時(shí)間觸發(fā)CAN消息實(shí)時(shí)調(diào)度算法，該算法在繼承了TTCAN時(shí)間觸發(fā)機(jī)制優(yōu)勢的基礎(chǔ)上，對(duì)其不足之處進(jìn)行改進(jìn)，將其用于周期性消息發(fā)送的獨(dú)占窗改進(jìn)為事件性消息也可調(diào)度的周期性消息窗，大大降低了事件性消息的延遲，并詳細(xì)論述了調(diào)度矩陣的設(shè)計(jì)方法。此外，將動(dòng)態(tài)調(diào)度思想引入TTCAN協(xié)議，對(duì)事件性消息采用LLF動(dòng)態(tài)調(diào)度算法，以確保CAN總線能夠適用于瞬時(shí)負(fù)載率較大的場合。