分布式系統TTCAN調度優化算法研究

葉彥斐,劉之境,劉 帥,趙金玉

(河海大學 能源與電氣學院， 南京 211100)

0 引言

CAN(controller area network)總線作為應用最廣泛的現場總線之一，為分布式控制系統實現各節點之間實時、可靠的數據通訊提供了強有力的支持[1]。隨著總線技術的發展，線纜測試儀也逐漸產生了分布式、信息化及網絡化發展的新需求。在分布式線纜測試儀實際工作中，數千條測試線路數據需要同時傳輸、通信，其中不僅包括諸如通斷檢測狀態、絕緣檢測狀態等需要優先處理的消息，也包括主機設置、信息查詢、節點自檢等等非周期性消息，從而對總線的穩定性及通訊效率提出了更高的要求。因此，需要設計或改進優化一種更高效、更可靠的基于CAN總線的應用層通訊協議，來更好地滿足分布式線纜測試儀的需求。

TTCAN(Time-Triggered CAN)是一種以系統矩陣為核心，基于時間觸發的總線協議。論文采用TTCAN作為分布式線纜測試儀中數據傳輸的應用層協議，針對TTCAN的系統矩陣進行優化設計，采用遺傳算法、差分進化算法和動態優先級算法分別為線纜測試儀的周期性和非周期性消息調度策略進行設計及優化，以實現提高系統穩定性及總線傳輸效率的目標。

1 TTCAN的系統分析

TTCAN協議的核心是其獨有的系統矩陣，其完整的傳輸周期被稱為系統矩陣周期MP(Matrix Period)[2]，一個MP具有多個基本周期BP(Basic Period)。單個基本周期BP由一個參考消息開始，對應系統矩陣中的一行。分布式線纜測試儀的系統矩陣中會存在若干周期性或非周期性消息，如圖1所示。

圖1 TTCAN的系統矩陣周期

2 TTCAN調度計劃分析

2.1 TTCAN消息分析

一般來說，通訊系統中的消息被分為兩種:時間觸發消息和事件觸發消息,這種分類隱藏了一個很重要的特征：消息的真實時間需求。

在通信系統中，按照任務的時延需求可以將消息分為3個種類[3]：硬實時消息、普通實時消息以及軟實時消息，而在分布式線纜測試儀中，不同的消息種類對于時間延遲的要求也不同，諸如線纜通斷、絕緣以及振動測試結果，必須及時從從站傳輸到主站，屬于優先級最高的硬實時消息，必須安排在獨占窗口中進行即時通訊。而諸如線纜測試啟動、測試結束等按鍵指令，為了保證操作的流暢度，也應有較高的優先級。諸如各種設置、查詢類消息屬于普通實時消息，雖然也需要及時處理，但在測試過程中并不是特別重要，所以可以安排至仲裁窗口或自由窗口中。主機自檢、LED自檢等功能則劃歸為軟實時消息，僅需在機器空閑時進行即可，不需要嚴格的響應時間要求。

對線纜測試儀的消息分析表明，一些比較重要的消息也可能被分配到仲裁窗口中，那么這類消息的通訊效率就會受到仲裁機制的影響，仲裁窗口中的其它普通消息也需要減少傳輸延遲。綜上，擴大仲裁窗口的傳輸時間有利于整個系統性能的提高。論文的主要工作是保證硬實時消息及時傳輸的同時，最大限度地提高仲裁窗口傳輸時間。

2.2 構建初始矩陣

PSA(標致雪鐵龍集團)消息集常用于基于現場總線的分布式系統的基準測試[4]，論文選擇PSA消息集模擬線纜測試中可能出現的消息通信情況，以驗證通信優化方法的可行性，并增加了一些延時約束使其更符合實際情況。

如表1中所示的修改的PSA消息集可以模擬線纜測試過程中可能出現的周期性消息通訊情況，共有12個硬實時消息需要進行處理，每個消息所需要的傳輸時間各不相同，并且由于同一條線纜的多項測試結果應在較短時間內完成傳輸，所以一些消息之間會構成控制環路。為了保證線纜測試系統的時效性，需要使所有消息的傳輸時間以及消息間形成的控制環路都得到滿足。

根據表1中的消息集，可以得到矩陣的系統周期TMP為80 000 μs，基本周期TBP為10 000 μs，共存在8個基本周期[5]，那么初始矩陣為8行；按各消息周期時間計算得到在一個系統周期內總共需傳輸的消息數為52，至少需要7列進行消息集傳遞，加上每行第一列參考消息和最后一列仲裁窗口，初始矩陣選9列。用相對簡單的裝箱算法可以得到初始矩陣，如圖2所示。

表1 PSA消息集

圖2 初始系統矩陣

矩陣單列須滿足該列中所有消息的傳輸時間需求，則單列列寬須大于或等于該列所有消息傳輸時間的最大值，這導致矩陣的獨占窗口中存在很多空白區域，這些空白顯然會造成總線傳輸效率的下降[6]。論文通過設計、優化消息調度策略，對系統矩陣中各個消息的合理安排，盡量縮短整個獨占窗口的通訊時間，以擴大仲裁窗口、提高總線通訊效率。

3 消息調度優化算法

3.1 周期性消息優化

3.1.1 編碼

首先對矩陣進行編碼：

如圖3(a)所示，將M1至M7所處的列數作為消息編碼，如M1處在矩陣第1列，那么M1的編碼就是1，可得到圖3(b)中M1至M7在矩陣中的編碼為[1,1,2,3,2,3,3]。

圖3 矩陣編碼

同理可得到圖2初始系統矩陣中M1至M12編碼為：[1,2,5,3,5,6,4,6,6,7,7,7]。

3.1.2 優化目標

設j表示表1中各消息的序號，i表示圖2初始系統矩陣的列數。xij根據對應序號為j的消息在某列是否存在取值1或0，若第k列存在，則xkj的值取1，否則取0。

例如，j=3時，消息3存在于第5列，則x53為1，x13、x23…為0。

由于同一個消息只會在矩陣的同一列出現，且每行最多出現一次，可得：

(1)

優化目標可分為兩部分，一部分表示獨占窗口所占用時間的最小化，另一部分表示總線的利用率。Cj表示消息j所需的傳輸時間，通過Cjxij表示消息j在某一列中所占用的傳輸時間因為必須保證任意一列的所有消息都可以正常傳輸，所以矩陣列寬取該列所有消息的最大值。則最小化獨占窗口時間可表示為：

(2)

同時將總線的利用率表示為：

(3)

Tj為消息j的傳輸周期，將式(2)和式(3)疊加可得到目標函數，以達到減小獨占窗口傳輸時間的同時總線利用率最大化的效果。

3.1.3 條件約束

初始矩陣生成后，矩陣的總行數是固定的，必須對矩陣進行適當的約束，確保整個矩陣每一列消息的數量不能超過該列的初始行數，即單個消息j在矩陣中出現的次數必須小于等于矩陣的行數[7]，可得如下的表達式：

(4)

設：

(5)

同時總線須滿足延時約束，需要保證控制環路的延時在設定的范圍內，根據實際線纜測試情況，若控制環路對應的兩個消息的序號分別為j1、j2,其周期都為BCT，對應的列為i1、i2，最大網絡延遲可表示為：

(6)

Cmin和Cmax指的是表1消息集中最小和最大傳輸時間，Cj2為消息j2的傳輸時間，Td為兩消息之間的最大網絡延遲，設：

(7)

3.1.4 目標函數

經過總線通訊調度優化，將獨占窗口占用時間最小化，總線利用率最大化，同時還需要滿足矩陣行數約束和控制環路延遲約束。引入罰函數法對約束條件進行處理，將不等式以罰函數的形式融入目標函數，可以降低優化難度，提高優化效率[8]。將總線利用率取倒數并調整數量級以匹配獨占窗口占用時間的數量級，可得到目標函數表達式：

(8)

其中：

(9)

p1在i2>i1時為:

(10)

在i2

(11)

a0和a1為懲罰因子，一般取較大的常數值。論文中a0取值400，a1取值5 000，不符合約束條件的F值會因此數值過大而被算法淘汰。

3.2 差分進化優化算法改進

差分進化算法可以有效規避算法陷入局部循環的問題，其主要用于求解連續域上的優化問題，論文主要是整數優化，屬于離散優化，所以可以借鑒0～1規劃中對于差分進化算法的改進[9]。

佳點集法是一種用更少的試驗次數產生更加均勻的點序列、更逼近被積函數曲線[10]的初始種群生成方法。該方法有效避免了隨機生成初始種群的弊端，且通過佳點集生成的種群精度與維數無關，有效提高了函數的運算效率。因此論文采用佳點集法生成初始種群，其定義為：設Gs為S維歐氏空間中的單位立方體[11]，如果r∈Gs，形為:

1≤k≤θ

(12)

若偏差φ(θ)滿足:

φ(θ)=C(r,ε)θ-1+ε

(13)

其中:C(r,ε)是只與r,ε(ε>0)有關的常數，則稱pθ(k)為佳點集[12]，r稱為佳點。取:

r={2cos(2πk/p)},1≤k≤s

(14)

p為滿足(p-s)/2≥s的最小素數，或:

rk={exp(k)},1≤k≤s

(15)

{a}表示a的小數部分。用任意給定的θ個點的函數值構成的任何加權和來近似計算函數在S維歐氏空間單位立方體Gs上的積分時，取θ個佳點所得的誤差是最小的[13]，此時最小誤差為:

(16)

其中:pθ(k)是一個包含有θ個點的佳點集。

其次，為提高算法的局部搜索能力和全局搜索能力，加快收斂速度，采用自適應的變異因子及交叉因子。

變異是差分進化算法的重要步驟，常用變異操作有隨機變異法和最優變異法。

隨機變異法如式(17)所示選取隨機個體變異：

υα,β(t+1)=xα,β(t)+F(xp1,β(t)-xp2,β(t))

(17)

xα,β表示第α個個體的第β個分量,α=1,2,…,M,β=1,2,…,n。其中p1,p2為[1,M]中任意選取的互相不等的隨機整數，M為父代個體總數，F為變異因子，t為當前進化代數，υα,β(t+1)為暫量，參與差分進化算法接下來的交叉、選擇操作。

最優變異法如式(18)所示選取最優個體變異：

υαβ(t+1)=xbest,β(t)+F(xp1,β(t)-xp2,β(t))

(18)

隨機變異法全局搜索能力較強，但收斂速度較慢；最優變異法一定程度上提高了局部搜索能力，但會使算法更容易陷入局部循環。

根據這兩種變異的特點，論文提出了漸進的變異策略，如式(19)：

υαβ(t+1)=λxαβ(t)+(1-λ)xbest,β(t)+

F(xp1,β(t)-xp2,β(t))

(19)

最后針對整數優化，對變異和交叉后的個體取整并求絕對值，以保證算法的解為整數。

3.3 非周期性消息優化

3.3.1 松弛度

LLF(Least Laxity First)算法根據消息的松弛度(緊急程度)評估優先級，松弛度越低的消息優先級越高。設Δtp為有效生存期，即消息從生成到截止的時間，設消息從搶占總線到發送成功所需的時間為ti，則消息的松弛度ΔtL=Δtp-ti。總線內的各通訊消息因松弛度不同，優先級會被動態調整。

3.3.2 動態標識符

總線通過對標識符進行仲裁實現消息調度功能，動態調度非周期性消息需要動態調整其標識符。對消息標識符ID的更改會影響其標記消息種類和功能以及作為各節點消息濾波憑據的作用。STM32芯片內部自帶bxCAN收發控制器。bxCAN內置的消息過濾器組可屏蔽、位寬可變，可以實現總線消息傳輸的硬件過濾功能，節約了CPU開銷的同時，過濾器組可以選擇性過濾標識符ID的部分位[16]。LLF算法對總線非周期性消息的調度通過該功能實現。

3.3.3 實際應用

由于獨占窗口中存在一些空閑時間，可將部分非周期性消息通過該窗口進行通訊。將周期性消息標識符最高位設置為1，非周期性消息最高位標識符設置為0，使其優先級低于周期性消息，避免出現堵塞現象。將剩余標識符位中后Y位設定為固定部分用于消息過濾及功能識別，其余位中可變部分設為動態部分，可得系統中可調度的消息數量為2Y。

設總線所有消息的最大有效生存期為Δtpmax，動態部分數值大小為IDdynamic，則由總線各節點完成計算：

(20)

為確保有效生存期最小的消息也能夠實時發送，應保持調整周期應小于所有消息傳輸時間的最小值對動態ID進行調節。該功能通過STM32芯片的定時器實現。

4 仿真結果分析

針對周期性消息，在MATLAB中先使用遺傳算法進行程序設計，以便與改進型差分進化算法進行對比。

首先隨機生成初始種群，種群大小選擇2 000并用式(8)所示目標函數計算個體適應度。接著采用輪盤賭選擇法進行個體選擇并進行交叉步驟，交叉后代比例選擇0.8[17]。然后進行復制、變異，選擇精英數目為50，并將適應度函數值偏差設為e-100[18]，迭代結果如圖4所示。

圖4 遺傳算法優化結果圖

得到的結果通過矩陣排列如圖5所示。

圖5 優化的系統矩陣

可以看到獨占窗口的通訊時間由圖2中的初始化矩陣中所示的5 600 ms降低到了5 448 ms，傳輸同樣的消息量所需時間縮短了2.7%，起到了良好的優化效果。

接著使用上文所述的改進型差分算法對矩陣進行優化，首先通過佳點集法生成初始種群，接著采用式(19)所示漸進變異法對初始種群進行變異，然后引入自適應的交叉指數pc=et-T/T進行交叉操作，最后通過式(9)計算適應度后進行選擇操作，通過迭代可以得到結果如圖6所示。

圖6 差分進化算法優化結果圖

可以看到函數在迭代至68代時就已經收斂到了遺傳算法計算出的最優值，得到了相同的優化效果。通過比較遺傳算法和差分進化算法的進化曲線，發現改進型差分算法收斂速度較快。且在實際的多次實驗中發現差分進化算法收斂穩定性高，不容易陷入局部循環。遺傳算法已經可以達到對周期消息矩陣進行優化的效果，但是優化速度仍然不夠理想，且經常會出現陷入局部循環的現象，而差分進化算法可以有效地規避這樣的問題。

非周期消息通訊采用了搶占多任務的結構，在滿足任務實時調度的同時，搶占多任務會帶來CPU資源的浪費和內存總開銷的增加[19]。因此在保證調度質量的前提下，任務切換的頻繁程度可以用來評估系統的通信效率，切換越頻繁，通信效率越低[20]。通過MATLAB程序仿真比較相同時間內應用算法前后整個總線系統切換次數如圖7所示。

圖7 系統切換次數仿真圖

圖7顯示，在使用優化算法后系統的切換次數較使用優化算法前有明顯降低，證明了優化算法可以有效地減少系統搶占現象，可以顯著提高總線傳輸效率。

5 結束語

論文針對分布式線纜測試儀這一分布式系統的實際應用中可能出現的時滯問題，分別對周期性消息和非周期性消息提出了不同的優化方案，將周期性消息的調度問題轉化為整數優化問題，并通過改進型的差分進化算法進行了有效的優化，得到了優化的系統矩陣，提高了總線利用率；對于非周期性偶發消息，通過基于松弛度的動態優先級調度方案，保證了偶發性消息的可靠傳輸。