基于改進(jìn)型遺傳算法的動態(tài)更新TTCAN系統(tǒng)技術(shù)

王飛平，洪 慧

(杭州電子科技大學(xué) 微電子CAD研究所，浙江 杭州 310018)

?

基于改進(jìn)型遺傳算法的動態(tài)更新TTCAN系統(tǒng)技術(shù)

王飛平，洪 慧

(杭州電子科技大學(xué) 微電子CAD研究所，浙江 杭州 310018)

作為CAN協(xié)議的擴展，TTCAN顯著提升了總線的實時性和可靠性，但其運用的靜態(tài)調(diào)度表在實際應(yīng)用中靈活性較差，無法應(yīng)用于網(wǎng)絡(luò)頻繁改變的動態(tài)系統(tǒng)。針對該缺陷，文中提出了一種基于改進(jìn)型遺傳算法的動態(tài)構(gòu)造和更新TTCAN系統(tǒng)矩陣技術(shù)。改進(jìn)了遺傳算法編碼、初始種群生成、突變步驟來優(yōu)化TTCAN系統(tǒng)矩陣，并且特別適合在網(wǎng)絡(luò)發(fā)生改變時動態(tài)在線更新系統(tǒng)矩陣。仿真和實際測試結(jié)果表明，改進(jìn)型優(yōu)化技術(shù)在動態(tài)網(wǎng)絡(luò)中可以使總線帶寬利用率始終保持在較高水平。

TTCAN；帶寬利用率；動態(tài)更新；遺傳算法

CAN總線基于事件觸發(fā)，無法滿足實時性要求較高的系統(tǒng)，因而實時性系統(tǒng)一般采用時間觸發(fā)的TTCAN協(xié)議。TTCAN中周期型的消息的隊列延遲為0，事件型的消息的隊列延遲是由TTCAN調(diào)度表中消息窗口的分布所決定的，因而建立一個高效的時間調(diào)度表是優(yōu)化TTCAN協(xié)議的關(guān)鍵[1-3]。但在實際總線系統(tǒng)中，網(wǎng)絡(luò)經(jīng)常需要發(fā)生改變，TTCAN的靜態(tài)調(diào)度表在此時無法滿足實際需要。

本文設(shè)計了一種在線動態(tài)更新TTCAN系統(tǒng)矩陣的方法，并針對該方法的實現(xiàn)改進(jìn)了生成TTCAN系統(tǒng)矩陣的遺傳算法。最后采用PSA消息集，以帶寬利用率為性能指標(biāo)驗證了改進(jìn)型遺傳算法優(yōu)化TTCAN系統(tǒng)矩陣的性能，并將算法應(yīng)用于實際的動態(tài)網(wǎng)絡(luò)中，驗證了該算法的實際使用性能。

1 TTCAN系統(tǒng)矩陣

1.1 TTCAN協(xié)議結(jié)構(gòu)

TTCAN 協(xié)議在CAN協(xié)議基礎(chǔ)上，采用以時間為基準(zhǔn)來控制網(wǎng)絡(luò)中節(jié)點消息傳輸。在系統(tǒng)運行前生成靜態(tài)調(diào)度表，可以保證在任一時間總線上只有一個周期消息在傳輸，避免由于競爭失敗導(dǎo)致低優(yōu)先級消息產(chǎn)生延時，消息的傳輸時間是確定可控的。系統(tǒng)運行時，TTCAN協(xié)議中的時間主節(jié)點發(fā)送參考消息，其余從節(jié)點在接受到參考消息時，開始同步自身的系統(tǒng)時鐘。然后按照事先設(shè)定好的時間調(diào)度表，在指定的時間窗口內(nèi)進(jìn)行自身的消息傳輸，這個時間調(diào)度表就是TTCAN的系統(tǒng)矩陣(SM)。系統(tǒng)矩陣分為3種窗口：(1)獨占窗。在該窗口范圍內(nèi)，只能有一個節(jié)點的一個消息在總線上傳輸；(2)仲裁窗。在該窗口內(nèi)，可能有多個節(jié)點的消息準(zhǔn)備發(fā)送，采用傳統(tǒng)CAN總線的幀ID優(yōu)先級仲裁決定發(fā)送次序；(3)自由窗。不傳送任何消息，留待以后擴展總線使用。

1.2 TTCAN系統(tǒng)矩陣構(gòu)造

本文算法分為兩部分，首先是確定矩陣的基本參數(shù)，然后將矩陣的基本參數(shù)傳入算法中運行，生成目標(biāo)矩陣。為了更加直觀，本文用國際標(biāo)準(zhǔn)PSA消息集[4]來驗證。在構(gòu)造系統(tǒng)矩陣前，需要確定以下系統(tǒng)矩陣基本參數(shù)，其中MG={M1,M2…M11,M12}表示消息集合,dm表示周期消息的截止期，pm代表消息的傳輸周期。dm≤pm表示每個消息的截止周期最大不超過其傳輸周期[5-6]。

(1)基本循環(huán)周期BC。有BC=pmin=Min{p1,p2…p12}，即選擇消息集中所有消息的最小傳輸周期作為BC；

(2)系統(tǒng)矩陣時間T。由多個BC組成的調(diào)度表稱為TTCAN系統(tǒng)矩陣，本文用符號T來表示一個系統(tǒng)矩陣從開始到結(jié)束的總時間，有T=LCM{p1,p2…p12}，其中，LCM表示最小公倍數(shù)?？梢员ＷC在一個系統(tǒng)矩陣內(nèi)，所有消息的等待時間都不會超過其截止期；

(3)矩陣行數(shù)Row。根據(jù)TTCAN協(xié)議Row=2n(n≤6)，又有T=BC×Row，可得Row=8；

(4)矩陣列數(shù)Col。矩陣列數(shù)等于周期型的消息所需列數(shù)加上仲裁窗的列數(shù)，根據(jù)TTCAN標(biāo)準(zhǔn)，多個相鄰的仲裁窗可以合并成一個，本文把系統(tǒng)矩陣最后一列設(shè)為仲裁窗。所以Col=Cmin+1，其中Cmin表示周期型的消息所需的列數(shù)，如式(1)所示

(1)

根據(jù)以上參數(shù)，構(gòu)造的初始系統(tǒng)矩陣如圖1所示。其中Part 1部分表示傳輸周期等于BC的消息，該部分的每一列只能放置一種消息；Part 2部分表示傳輸周期不等于BC的消息，由圖可以看出，由于該部分的每一列中存放的消息的傳輸時間不同，導(dǎo)致該部分窗口有空閑的部分，通過優(yōu)化矩陣中消息的分布，可以減少空閑部分，提高帶寬利用率，這也是本文提出的算法優(yōu)化的目標(biāo)[7-9]。

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

2 改進(jìn)型遺傳算法

隨著消息個數(shù)的增加，TTCAN系統(tǒng)矩陣組合的數(shù)量指數(shù)性增加。構(gòu)造系統(tǒng)矩陣屬于NPC 問題，適合采用遺傳算法來解決[10]。TTCAN系統(tǒng)矩陣的優(yōu)化目標(biāo)明確，就是減小獨占窗部分的寬度，增加仲裁窗的寬度，從而提高圖1中Part 2部分的帶寬利用率。本文算法采用帶寬利用率作為適應(yīng)度函數(shù)來控制進(jìn)化方向，考慮到算法需滿足TTCAN系統(tǒng)矩陣的約束條件，改進(jìn)了遺傳算法的初始種群生成、交叉和突變步驟。同時為了適用于動態(tài)更新系統(tǒng)矩陣的需求，采用矩陣編碼和實數(shù)編碼相結(jié)合的機制。下面分別介紹改進(jìn)型TTCAN系統(tǒng)矩陣優(yōu)化算法的幾個關(guān)鍵步驟。

2.1 編碼

編碼是將一個問題可能的解從其解的空間轉(zhuǎn)換到遺傳算法所能處理的搜索空間[10-12]。針對于利用遺傳算法動態(tài)更新系統(tǒng)矩陣問題，不能采用傳統(tǒng)的符號、二進(jìn)制等編碼。這里采用矩陣編碼和實數(shù)編碼相結(jié)合的編碼方案，矩陣編碼可以用最直接的方法將個體基因的組合情況表示出來，具有比一維數(shù)據(jù)結(jié)構(gòu)更大的數(shù)據(jù)存儲空間[13]。實數(shù)結(jié)構(gòu)體存儲了網(wǎng)絡(luò)中節(jié)點的所有信息，通過主節(jié)點發(fā)送輪詢信息獲得，當(dāng)節(jié)點發(fā)生更新時，更新對應(yīng)的數(shù)據(jù)即可重新運行算法生成一個系統(tǒng)矩陣。圖2是采用矩陣編碼代表一個系統(tǒng)矩陣的染色體，其中Mes代表周期型消息；Arb代表仲裁窗；Free代表自由窗。其中每個Mes消息體的結(jié)構(gòu)如圖3所示。

圖2 染色體結(jié)構(gòu)

圖3 Mes 消息結(jié)構(gòu)體

2.2 隨機生成初始種群

圖4 初始種群生成流程圖

圖4中Popsize為種群中個體數(shù)量；Row為矩陣行數(shù)；Col為列數(shù)；R，J，I表示當(dāng)前的行數(shù)，列數(shù)和個體數(shù)。按照圖5的流程圖可以保證生成的個體滿足TTCAN系統(tǒng)矩陣的3個約束條件。

2.3 適應(yīng)度函數(shù)

遺傳算法在進(jìn)化搜索中基本不利用外部信息，僅以種群中每個個體的適應(yīng)度值來進(jìn)行搜索，從而確定進(jìn)行交叉突變操作的個體，因此適應(yīng)度函數(shù)的選取至關(guān)重要。本文選取Part 2部分總線帶寬利用率U和Part 2部分所需的最小列數(shù)Cmin相加之和作為適應(yīng)度函數(shù)[6]。適應(yīng)度函數(shù)為

(2)

其中，帶寬利用率部分只考慮系統(tǒng)矩陣獨占窗部分，即獨占窗中周期消息的傳輸總時間與獨占窗的總寬度的比值。CLi表示第i列的列寬，取該列所有消息中最大的傳輸時間，在實際應(yīng)用中，列寬應(yīng)略>CLi，以確保消息傳輸完全，n為系統(tǒng)矩陣的列數(shù)。

2.4 交叉

交叉是傳統(tǒng)遺傳算法的關(guān)鍵步驟，將隨機選擇而來的兩個個體部分基因進(jìn)行交叉操作，從而產(chǎn)生新的個體。對于TTCAN系統(tǒng)矩陣，該操作不能進(jìn)行，因為上文提到的系統(tǒng)矩陣限制，當(dāng)進(jìn)行交叉操作后系統(tǒng)矩陣就不能再滿足要求[14]。

2.5 突變

在傳統(tǒng)遺傳算法中突變操作是按照突變率隨機選擇一個或多個基因，在合理的范圍內(nèi)隨機的突變成另一個值。對于本文采用的矩陣編碼染色體，影響適應(yīng)度的因素是基因在系統(tǒng)矩陣的分布，改變其位置就會改變適應(yīng)度值，所以本文采用的突變操作是隨機選取兩個消息，但兩者的截止期和傳輸周期都要相同，然后交換它們的位置。

3 動態(tài)更新系統(tǒng)矩陣

TTCAN協(xié)議中的系統(tǒng)矩陣是靜態(tài)離線構(gòu)建的，當(dāng)網(wǎng)絡(luò)發(fā)生以下3種改變時，靜態(tài)調(diào)度表的工作會受到影響，具體如下：(1)如果網(wǎng)絡(luò)中新加入節(jié)點，當(dāng)靜態(tài)調(diào)度表中預(yù)留的自由窗口無法滿足新增加節(jié)點的需求，則系統(tǒng)矩陣就無法再使用，只有關(guān)閉系統(tǒng)重新部署調(diào)度表；(2)如果網(wǎng)絡(luò)中節(jié)點被刪除，靜態(tài)調(diào)度表只能將被刪除節(jié)點所屬的窗口閑置，導(dǎo)致帶寬利用率降低；(3)節(jié)點的周期或者傳輸時間發(fā)生改變，會出現(xiàn)總線沖突導(dǎo)致靜態(tài)調(diào)度表無法繼續(xù)工作。為克服TTCAN的以上3種缺陷，本文設(shè)計了基于遺傳算法的在線動態(tài)更新系統(tǒng)矩陣算法，流程如圖5所示。

圖5 動態(tài)更新系統(tǒng)流程圖

系統(tǒng)開始運行時，啟動并行監(jiān)測網(wǎng)絡(luò)的狀態(tài)，一旦網(wǎng)絡(luò)發(fā)生改變時，處理器會啟用動態(tài)更新機制，利用當(dāng)前 TTCAN 的空閑窗口發(fā)送網(wǎng)絡(luò)輪詢消息獲得當(dāng)前網(wǎng)絡(luò)節(jié)點的參數(shù)信息，然后后臺調(diào)用遺傳算法計算新的調(diào)度表，計算完成后利用空閑窗發(fā)送網(wǎng)絡(luò)更新消息，節(jié)點更新完畢后，開始運行新的系統(tǒng)矩陣。

4 實驗

根據(jù)以上設(shè)計的改進(jìn)型TTCAN系統(tǒng)矩陣優(yōu)化算法，這里對其進(jìn)行了性能評估和參數(shù)對比分析。首先，使用Matlab驗證了遺傳算法對于提高CAN總線帶寬利用率的性能，算法參數(shù)中的種群個數(shù)選擇50個，進(jìn)化次數(shù)選擇100次，突變率為8%。仿真結(jié)果如圖6所示，其中橫坐標(biāo)代表種群進(jìn)化的代數(shù)，縱坐標(biāo)表示每代種群所有個體的平均適應(yīng)度。如圖6所示從最初一代到最后一代，種群的適應(yīng)度穩(wěn)步增加，最后趨于穩(wěn)定。Part 2 部分的帶寬利用率增加了4.3%，對于PSA消息集的TTCAN系統(tǒng)矩陣型的消息的實時性不變的情況下，減小了仲裁窗中發(fā)生總線競爭的幾率，提高了總線的可靠性。并且算法對于帶寬利用率的提高會隨著網(wǎng)絡(luò)節(jié)點數(shù)量的增加而增大。來說，意味著每秒增加了9.56 ms的仲裁窗時間，可以多發(fā)送73個非周期型的報文。

圖6 種群適應(yīng)度變化趨勢圖

圖7 實際系統(tǒng)運行圖

圖8 節(jié)點增刪時算法運行圖

圖7是采用改進(jìn)型算法搭建的實際系統(tǒng)，主節(jié)點采用TQ3358開發(fā)板，從節(jié)點采用STM32F105芯片，系統(tǒng)有2路CAN總線冗余備份。在此硬件系統(tǒng)平臺，模擬了網(wǎng)絡(luò)發(fā)生改變時的性能測試。由圖8所示，當(dāng)網(wǎng)絡(luò)中發(fā)生了節(jié)點的增刪時，本文算法會根據(jù)網(wǎng)絡(luò)中節(jié)點的改變自動重新生成新的系統(tǒng)矩陣，可以避免由于節(jié)點改變，系統(tǒng)矩陣中出現(xiàn)窗口閑置或者發(fā)生節(jié)點沖突，保證網(wǎng)絡(luò)的正常運行。當(dāng)節(jié)點增加時，改進(jìn)型算法可以在線重新生成系統(tǒng)矩陣。但在傳統(tǒng)靜態(tài)調(diào)度表中，如果預(yù)留的自由窗口不滿足新增消息的需求，則必須停止系統(tǒng)然后重新生成調(diào)度表。當(dāng)刪除節(jié)點時，改進(jìn)型算法可以使總線帶寬利用率保持在較高的水平，而傳統(tǒng)算法只能閑置被刪節(jié)點的窗口，導(dǎo)致帶寬利用率降低。

5 結(jié)束語

本文以改進(jìn)型遺傳算法為基礎(chǔ)提出了動態(tài)在線更新TTCAN系統(tǒng)矩陣技術(shù)。不僅優(yōu)化了TTCAN的靜態(tài)調(diào)度表，同時滿足動態(tài)在線更新系統(tǒng)矩陣的需求。在網(wǎng)絡(luò)需要發(fā)生改變的動態(tài)系統(tǒng)中，克服了靜態(tài)調(diào)度表的缺陷，可以使得總線帶寬利用率始終保持在較高水平。在實際的總線系統(tǒng)中，為提高總線的資源利用率提供了參考。

[1] Wang S,Zhang T.Scheduling design of auto-motive TTCAN control system based on average loading[C].Jinan:Intelligent Control and Automation,2010.

[2] Jang D, Han S, Kang S, et al. Communication channel modeling of controller area network (CAN)[C].Taiyuan:Seventh International Conference on Ubiquitous and Future Networks,2015.

[3] 李佳,朱元.CAN與 TTCAN通信延遲 時間的分析[J].清華大學(xué)學(xué)報,2006,46(2):261-265.

[4] 李運生,竇金生.TTCAN 系統(tǒng)矩陣的優(yōu)化算法[J].自動化儀表,2012,33(6):8-11.

[5] 劉強,劉銀年.基于時間觸發(fā)的TTCAN協(xié)議[J].自動化儀表,2008,29(1):37-40.

[6] Schmidt K,Schmidt E G.Systematic message schedule construction for time-triggered CAN[J].IEEE Transactions on Vehicular Technology,2007,56(6):3431-3441.

[7] 夏鵬,朱琳,葉杰.變頻器監(jiān)控系統(tǒng)TTCAN調(diào)度優(yōu)化算法研究[J].電氣傳動,2015,45(3):72-76.

[8] 劉魯源,萬仁君.TTCAN 調(diào)度算法及其在汽車控制系統(tǒng)中的應(yīng)用[J].汽車工程,2005,25(1):60-63.

[9] 馮曉東,果艷紅.TTCAN動態(tài)調(diào)度算法實現(xiàn)與仿真[J].電子測量與儀器學(xué)報,2008,22(2):81-85.

[10] 劉鯖潔,陳桂明,劉小方.基于矩陣編碼的遺傳算法研究[J].計算機工程,2011,37(13):160-162.

[11] 任子武,傘冶.實數(shù)遺傳算法的改進(jìn)及性能研究[J].電子學(xué)報,2007,35(2): 269-274.

[12] 鄭權(quán),忻尚芝,錢建秋.基于改進(jìn)遺傳算法的PID參數(shù)研究[J].電子科技,2015,28(11):5-8.

[13] 張超群,鄭建國,錢潔.遺傳算法編碼方案比較[J].計算機應(yīng)用研究,2011,28(3):820-822.

[14] Qiao X, Wang K F, Sun Y, et al. A genetic algorithms based optimization for TTCAN[C].Beijing:IEEE International Conference on Vehicular Electronics and Safety. IEEE Xplore, 2008.

Dynamic Update TTCAN System Technique Based on Improved Genetic Algorithm

WANG Feiping，HONG Hui

( Institute of Microelectronic CAD, Hangzhou Dianzi University，Hangzhou 310018,China)

As an extension of the CAN protocol, TTCAN improves the real-time performance and reliability of the CAN bus significantly. However, its static scheduling table is not flexible to be applied in dynamic network. A dynamic construct and update TTCAN system matrix technique based on improved genetic algorithm is proposed to solve this defect. The improved coding, the initialization population generation and the mutation steps were modified to optimization of TTCAN system matrix, and suitable for the dynamic online update system when the network nodes were changed. Finally, the simulation and the actual test results showed that the improved optimization technique could keep the bandwidth utilization at a high level in the dynamic system.

TTCAN；bandwidth utilization ratio；dynamic update; genetic algorithm

2016- 10- 09

國家自然科學(xué)基金(61107025)

王飛平(1992-)，男，碩士研究生。研究方向：嵌入式系統(tǒng)。洪慧(1979-)，男，博士，副教授。研究方向：嵌入式系統(tǒng)。

10.16180/j.cnki.issn1007-7820.2017.08.011

TN926；TP336

A

1007-7820(2017)08-040-04