分布式系統(tǒng)TTCAN調(diào)度優(yōu)化算法研究

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

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

0 引言

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

TTCAN(Time-Triggered CAN)是一種以系統(tǒng)矩陣為核心，基于時間觸發(fā)的總線協(xié)議。論文采用TTCAN作為分布式線纜測試儀中數(shù)據(jù)傳輸?shù)膽?yīng)用層協(xié)議，針對TTCAN的系統(tǒng)矩陣進行優(yōu)化設(shè)計，采用遺傳算法、差分進化算法和動態(tài)優(yōu)先級算法分別為線纜測試儀的周期性和非周期性消息調(diào)度策略進行設(shè)計及優(yōu)化，以實現(xiàn)提高系統(tǒng)穩(wěn)定性及總線傳輸效率的目標。

1 TTCAN的系統(tǒng)分析

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

圖1 TTCAN的系統(tǒng)矩陣周期

2 TTCAN調(diào)度計劃分析

2.1 TTCAN消息分析

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

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

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

2.2 構(gòu)建初始矩陣

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

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

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

表1 PSA消息集

圖2 初始系統(tǒng)矩陣

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

3 消息調(diào)度優(yōu)化算法

3.1 周期性消息優(yōu)化

3.1.1 編碼

首先對矩陣進行編碼：

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

圖3 矩陣編碼

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

3.1.2 優(yōu)化目標

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

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

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

(1)

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

(2)

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

(3)

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

3.1.3 條件約束

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

(4)

設(shè)：

(5)

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

(6)

Cmin和Cmax指的是表1消息集中最小和最大傳輸時間，Cj2為消息j2的傳輸時間，Td為兩消息之間的最大網(wǎng)絡(luò)延遲，設(shè)：

(7)

3.1.4 目標函數(shù)

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

(8)

其中：

(9)

p1在i2>i1時為:

(10)

在i2

(11)

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

3.2 差分進化優(yōu)化算法改進

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

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

1≤k≤θ

(12)

若偏差φ(θ)滿足:

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

(13)

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

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

(14)

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

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

(15)

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

(16)

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

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

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

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

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

(17)

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

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

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

(18)

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

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

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

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

(19)

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

3.3 非周期性消息優(yōu)化

3.3.1 松弛度

LLF(Least Laxity First)算法根據(jù)消息的松弛度(緊急程度)評估優(yōu)先級，松弛度越低的消息優(yōu)先級越高。設(shè)Δtp為有效生存期，即消息從生成到截止的時間，設(shè)消息從搶占總線到發(fā)送成功所需的時間為ti，則消息的松弛度ΔtL=Δtp-ti?？偩€內(nèi)的各通訊消息因松弛度不同，優(yōu)先級會被動態(tài)調(diào)整。

3.3.2 動態(tài)標識符

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

3.3.3 實際應(yīng)用

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

設(shè)總線所有消息的最大有效生存期為Δtpmax，動態(tài)部分數(shù)值大小為IDdynamic，則由總線各節(jié)點完成計算：

(20)

為確保有效生存期最小的消息也能夠?qū)崟r發(fā)送，應(yīng)保持調(diào)整周期應(yīng)小于所有消息傳輸時間的最小值對動態(tài)ID進行調(diào)節(jié)。該功能通過STM32芯片的定時器實現(xiàn)。

4 仿真結(jié)果分析

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

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

圖4 遺傳算法優(yōu)化結(jié)果圖

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

圖5 優(yōu)化的系統(tǒng)矩陣

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

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

圖6 差分進化算法優(yōu)化結(jié)果圖

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

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

圖7 系統(tǒng)切換次數(shù)仿真圖

圖7顯示，在使用優(yōu)化算法后系統(tǒng)的切換次數(shù)較使用優(yōu)化算法前有明顯降低，證明了優(yōu)化算法可以有效地減少系統(tǒng)搶占現(xiàn)象，可以顯著提高總線傳輸效率。

5 結(jié)束語

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