0 引言

    時間觸發(fā)以太網(wǎng)^[1]能夠很好地滿足工業(yè)的實時通信，以其較強的實時特性和確定性引起了航空電子技術(shù)領(lǐng)域的廣泛關(guān)注^[2]。時間觸發(fā)以太網(wǎng)中，時間觸發(fā)（TT）消息由離線生成的通信調(diào)度表控制發(fā)送，調(diào)度表生成的好壞直接影響到網(wǎng)絡(luò)通信的質(zhì)量。正常狀態(tài)下，調(diào)度表離線生成無法實現(xiàn)實時的重新調(diào)度，但網(wǎng)絡(luò)中任一系統(tǒng)的變化都將需要新的調(diào)度表。從之前研究的成果來看^[3-5]，由于調(diào)度表生成其指數(shù)級增長的時間復(fù)雜度，表的變化將引起災(zāi)難性的情況，直接影響航空器的飛行和任務(wù)安全。避免已生成的調(diào)度表變化，重新在預(yù)留時間段進行消息調(diào)度就可以妥善解決TTE中TT消息的靈活調(diào)度問題，由此需要一種能夠快速準確地尋找全局最優(yōu)解的調(diào)度表生成方法降低已有消息的時間占用，以實現(xiàn)預(yù)留資源，應(yīng)對隨機產(chǎn)生的網(wǎng)絡(luò)結(jié)構(gòu)異變。

    遺傳算法是一種利用自然選擇理論和自然遺傳理論設(shè)計的優(yōu)化算法。在模擬自然界生物進化的過程中表現(xiàn)出很好的全局搜索能力，實現(xiàn)特定方向的最優(yōu)化結(jié)果^[6-8]。通過對問題的深入分析，將調(diào)度問題轉(zhuǎn)化為典型裝箱問題并用相關(guān)算法進行求解，可以進一步提升對解的局部搜索能力，更快更為準確地找到全局最優(yōu)解。

1 基本概念和模型定義

    參考STEINER W^[3]的模型設(shè)計并加以轉(zhuǎn)化，將雙向消息幀和虛鏈路作為重點考慮的因素，下面對TTE網(wǎng)絡(luò)模型的具體概念進行定義。圖1所示是一個簡單的TTE示例網(wǎng)絡(luò)，其中粗實線表示網(wǎng)絡(luò)連接的實際物理線路，帶箭頭的細實線表示消息幀的發(fā)送鏈路，具有從起點到目的節(jié)點的方向性。

    數(shù)據(jù)流鏈接表示為l_ij=[v_i，v_j]，其中v_i和v_j分別表示鏈路兩端的源節(jié)點和目的節(jié)點。P表示消息傳輸路徑，是消息傳輸過程所需要的全部數(shù)據(jù)流鏈接矢量加和，如下式：

    虛鏈路由多個數(shù)據(jù)流路徑P組成，在拓撲結(jié)構(gòu)中，同一虛鏈路vl中的路徑P具有相同的起始端節(jié)點和部分重合的消息傳輸鏈路，數(shù)學符號表述虛鏈路vl如下式：

    為準確描述時間觸發(fā)消息在網(wǎng)絡(luò)中的行為，下面對時間觸發(fā)消息幀的傳輸參數(shù)進行定義：f{id，period，source，destin，timepoint，length}，其中id是幀的標識，period表示自源節(jié)點source至目的節(jié)點destin的時間觸發(fā)消息發(fā)送周期。消息幀的調(diào)度用幀發(fā)送時刻進行描述，因此定義TT消息幀的在某一節(jié)點發(fā)送的發(fā)送時刻為參數(shù)timepoint，同時以時間單位為度量定義幀的長度length。參數(shù)包括id、source、destin和length等是由消息幀傳輸路徑?jīng)Q定的常數(shù)。時間觸發(fā)網(wǎng)絡(luò)的TT消息調(diào)度即為對TT消息幀在節(jié)點處發(fā)送時刻的調(diào)度安排。

2 問題轉(zhuǎn)化和算法設(shè)計

    為解決消息調(diào)度問題，將時間觸發(fā)消息調(diào)度問題轉(zhuǎn)化為典型的裝箱問題，利用裝箱算法可以實現(xiàn)原有遺傳算法在解域局部搜索效率的大幅提高，形成混合遺傳算法。

2.1 調(diào)度問題的描述和轉(zhuǎn)化

    在一相對復(fù)雜的拓撲結(jié)構(gòu)中，時間觸發(fā)消息調(diào)度即為對于時間資源的調(diào)度利用，可以被轉(zhuǎn)化為二維裝箱問題。

    用參數(shù)periodmin表示需要調(diào)度消息的最小消息周期。在AS6802協(xié)議^[9]中的簇周期（cluster cycle）用LCM(period)表示，即為所有消息周期的最小公倍數(shù)，簇周期在整個消息傳輸過程中周期性地重復(fù)實現(xiàn)時間觸發(fā)消息的連續(xù)傳輸。同時設(shè)置所有消息周期的最大公約數(shù)，用GCD(period)表示。通過折疊未進行資源分配的一維時間軸線(如圖2)，將問題轉(zhuǎn)化為二維圖形^[5]，見圖3(a)、(b)。

    為簡化模型，引入時間片（time slot）的概念，假設(shè)在每一鏈路l中，消息最多利用一個時間片即可實現(xiàn)長度length的全部傳輸，設(shè)置時間片長度為T_STS，由此可以得出時間段的時間片個數(shù)為N_STS：

    當拓撲結(jié)構(gòu)中兩條路徑P_a和P_b之間任一傳輸鏈接均不產(chǎn)生重合，節(jié)點就可以實現(xiàn)幀的同時傳輸。在時域范圍內(nèi)，假使將這樣路徑中的節(jié)點消息分為不同區(qū)域，時間片就可以實現(xiàn)交疊或部分交疊。問題轉(zhuǎn)化的關(guān)鍵在于將路徑不交疊可同時傳輸?shù)南⑦M行派發(fā)，這需要對拓撲結(jié)構(gòu)進行分區(qū)操作。對于討論的星形和樹型拓撲結(jié)構(gòu)，定義了組（Group）的概念,在某一時刻根據(jù)消息傳輸?shù)姆植紝⒒ハ嗦?lián)系的節(jié)點組成集合，以便于對網(wǎng)絡(luò)拓撲結(jié)構(gòu)的節(jié)點進行分區(qū)操作。在兩個同屬一個組的兩個子組之間，若子組內(nèi)的消息傳輸相互獨立且不經(jīng)過上層中心節(jié)點，則兩子組內(nèi)消息可以共享時域資源，實現(xiàn)同時傳輸，避免消息沖突的發(fā)生。

    對消息調(diào)度問題的轉(zhuǎn)化減少了時間觸發(fā)以太網(wǎng)中靜態(tài)段消息傳輸?shù)臅r間資源利用，同時很好地避免了消息傳輸沖突的發(fā)生，見圖3(c)。

2.2 混合遺傳算法設(shè)計

    裝箱問題是一個典型的NP問題，無法通過準確的解法解決，遺傳算法在復(fù)雜系統(tǒng)優(yōu)化計算中的高效搜索可以適應(yīng)大規(guī)模非線性不連續(xù)多模態(tài)功能^[10]。通過將遺傳算法和裝箱算法相融合，可以達到算法的全局和局部搜索能力的平衡。

    圖4是混合遺傳算法的流程圖，包括初始化和遺傳迭代的簡要過程描述，下面將就混合遺傳算法的具體實現(xiàn)進行詳細描述。

2.2.1 個體設(shè)計

    個體參數(shù)應(yīng)當包括以下幾個關(guān)鍵數(shù)據(jù)：時間片分配、每一節(jié)點的時間分配、節(jié)點狀態(tài)、目標函數(shù)值和適應(yīng)度函數(shù)值等。

    在算法起始進行參數(shù)設(shè)置時應(yīng)當對個體進行初始化，節(jié)點狀態(tài)初始設(shè)置為State_Idle狀態(tài)并且隨機分配任務(wù)。消息集中的不同消息根據(jù)其所屬組的ID分類安置，如果消息獨立于其他消息，則將其放入Message_of_independent_group陣列；如果消息與其他消息同屬某一組，則將其放入時間片進行資源分配。調(diào)度節(jié)點時間片分配，避免時間節(jié)點超出周期設(shè)置，最終確定節(jié)點所處工作狀態(tài)，完成初始化操作。

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

    利用懲罰函數(shù)對調(diào)度條件進行約束，實現(xiàn)適應(yīng)度函數(shù)功能，有向控制調(diào)節(jié)下一代子個體的生成。

    (1)避免沖突約束

    在時間觸發(fā)以太網(wǎng)調(diào)度表生成過程中，實現(xiàn)鏈路中數(shù)據(jù)流傳輸互斥，避免沖突是至關(guān)重要的。因此，在設(shè)計懲罰函數(shù)時必須考慮保證避免沖突約束的實現(xiàn)。利用上文定義的相關(guān)模型參數(shù)，完成避免沖突約束的定義如下：

    根據(jù)約束條件的公式描述，定義懲罰函數(shù)，公式描述如下：

    式(7)中的ε表示極小的正值常數(shù)，以保證分母非零且為正?？芍?，兩點間時刻間距越小，函數(shù)值隨著時刻差的降低成倒數(shù)形式增加。

    (2)路徑和內(nèi)存約束

    鏈路在消息傳輸和收發(fā)過程中必然會由于鏈路端點在分發(fā)和接收消息產(chǎn)生相應(yīng)的延時，控制中繼鏈路節(jié)點在消息傳輸過程中的幀派發(fā)時間和存儲延遲時間對于描述通信模型十分重要，利用式(8)～(10)描述消息幀通過某一節(jié)點的收發(fā)時刻保持在一定范圍。

    max(hopdelay)表示消息經(jīng)過節(jié)點的最大延遲上限，[vertex_x，vertex_j]和[vertex_j，vertex_y]分別表示某一傳輸路徑中兩個毗鄰的鏈路端點特征，它們共享一個公共節(jié)點vertex_j。Membound由已知硬件參數(shù)決定，這一約束是區(qū)別于異步觸發(fā)傳輸方式的時間觸發(fā)通信的特性。懲罰函數(shù)設(shè)置如下：

    式（11）中，為保證懲罰函數(shù)對算法產(chǎn)生正作用，參數(shù)a和b設(shè)置為大于1的常數(shù)。

    (3)起點端到終點端約束

    為避免生成未能實現(xiàn)消息送達的調(diào)度，設(shè)置約束規(guī)范由鏈路起點到終點間的時間延遲，保證調(diào)度方案在規(guī)定時間內(nèi)使TT消息送達。約束公式描述如下：

    根據(jù)算法設(shè)計需求，起點端到終點端約束的公式描述轉(zhuǎn)化為懲罰函數(shù)Pnlt₃，見式（13），其中參數(shù)c是大于1的常數(shù)。

    為實現(xiàn)妥當?shù)臅r間觸發(fā)消息流安排，式（14）中得到的函數(shù)值Cost能很好地反映調(diào)度方案的綜合性能表現(xiàn)。

其中，參數(shù)ω₁、ω₂和ω₃是調(diào)整3個懲罰函數(shù)影響比例的和為1的常數(shù)。從設(shè)計目標可知，Cost越大，遺傳算法中基因保留在子代的可能性越小，因此設(shè)置適應(yīng)度函數(shù)如式（15），個體適應(yīng)度越大，表示越適應(yīng)外部環(huán)境的需求。

2.2.3 遺傳算子設(shè)計

    基于比例的選擇算子設(shè)計保證了遺傳概率和適應(yīng)度函數(shù)的正相關(guān)。交叉算子根據(jù)遺傳算法為下一代更好地遺傳父代基因所設(shè)計，選擇個體生成子代之前，使個體根據(jù)適應(yīng)度值降序排列為一列。接著，個體j和個體j+1進行交配產(chǎn)生子代個體j，其中，參數(shù)j的范圍在1～(PopSize+1)/2之間。剩下的子代個體由父代個體j和父代個體(PopSize+1-j)交配生成，其中，參數(shù)j的范圍在1～(PopSize+1)/2之間。

3 仿真及結(jié)果分析

    為了進一步實現(xiàn)對混合遺傳算法在時間觸發(fā)消息調(diào)度的測試，對試驗仿真環(huán)境進行了設(shè)置，樹形的拓撲結(jié)構(gòu)較為復(fù)雜，見圖5(a)，能有效測試算法性能。

    圖5(a)中每個交叉點表示一個交換機或終端系統(tǒng)，從圖中可以看到，樹形結(jié)構(gòu)通過交換節(jié)點進行級聯(lián)，由此可以根據(jù)核心交換節(jié)點的位置，人工對拓撲結(jié)構(gòu)進行分區(qū)，見圖5(b)。經(jīng)過仿真得到用甘特圖表示的消息調(diào)度結(jié)果，見圖6。X軸表示時間片，Y軸表示樹形結(jié)構(gòu)的節(jié)點。在滿足實時性要求的情況下，消耗時間片降低到96個。

    此外，對單純遺傳算法和混合遺傳算法的適應(yīng)性函數(shù)最終收斂情況進行比較，遺傳代數(shù)和適應(yīng)函數(shù)的關(guān)系可以清楚地反映在圖7中?；旌线z傳算法在收斂速度較快，很快收斂到最優(yōu)解附近，而遺傳算法則收斂至局部解附近，收斂速度不佳。在遺傳2 000代時，混合遺傳算法收斂于適應(yīng)函數(shù)值79.68，遺傳算法2 000代時則收斂于適應(yīng)函數(shù)值83.54。

    遺傳算法與裝箱算法融合產(chǎn)生的混合遺傳算法克服了傳統(tǒng)過早收斂于某一局部解的問題，并實現(xiàn)了全局最優(yōu)解的快速搜索。

    每次仿真重復(fù)進行10次實驗，記錄如表1所示，可以看到，遺傳算法在13節(jié)點1 300消息數(shù)的情況下表現(xiàn)不佳，這是單純遺傳算法陷于局部最優(yōu)解和時間溢出造成的，反之混合遺傳算法表現(xiàn)良好，由此可以看出其具有能夠克服原有方法缺陷的特性。

    另外，通過表2的兩種算法消耗的時間片可以比較得出，混合遺傳算法較單純遺傳算法能利用更少的時間片實現(xiàn)完整TT消息通信功能。

    通過實驗得出的靜態(tài)段平均時間消耗統(tǒng)計對比，相對于遺傳算法，混合遺傳算法可以最大減少24.28%的時間資源浪費。

4 結(jié)論

    為實現(xiàn)時間資源的預(yù)留，保證網(wǎng)絡(luò)傳輸靈活性，提出了一種基于混合遺傳算法的TT消息調(diào)度表生成方法。通過問題轉(zhuǎn)化和算法在解域空間的優(yōu)化搜索，得到最優(yōu)的調(diào)度方案。仿真實驗對單純遺傳算法和混合遺傳算法進行比較，混合遺傳算法在搜索結(jié)果、收斂速度和時間片占用上都超越了純遺傳算法性能，能夠滿足靈活性設(shè)計要求，適應(yīng)未來機載航空環(huán)境的消息調(diào)度。下一階段將對TTE網(wǎng)絡(luò)靈活性配置，實現(xiàn)調(diào)度表變化等方面的進一步研究。

參考文獻

[1] KOPETZ H，ADEMAJ A，GRILLINGER P，et al.The time-triggered Ethernet(TTE) design[C].8th IEEE International Symposium on Object-oriented Realtime Distributed Computing(ISORC)．Seattle，Washington，2005：22-23.

[2] HATLEY D，IMTIAZ P.Strategies for real-time system specification[M].New York：Addison-Wesley，2013.

[3] STEINER W.An Evaluation of SMT-based schedule synthesis for time-triggered multi-hop networks[C].31st IEEE Real-Time Systems Symposium，2010：375-384.

[4] STEINER W，DUTERTRE B.SMT-based formal verification of a TTEthernet synchronization function[C].FMICS 2010，Verlag Berlin Heidelberg：Springer，2010：148-163.

[5] Huang Jia，BLECH J O，RAABE A，et al.Static scheduling of a time-triggered network-on-chip based on SMT solving[C].Proceedings of Design，Automation＆Test in Europe Conference＆ Exhibition，DATE．Piscata way，NJ：IEEE Press，2012：509-514.

[6] 王慶祥，陳家琪.利用遺傳算法優(yōu)化TTCAN網(wǎng)絡(luò)的時間調(diào)度系統(tǒng)矩陣[J].航空計算技術(shù)，2004，34(4)：24-27.

[7] 朱智林，劉曉華，韓俊剛.TTCAN周期性任務(wù)的優(yōu)化調(diào)度算法[J].蘭州大學學報，2005，41(4)：73-76.

[8] DING S，TOMIYAMA H，TAKADA H.An effective ga-based schedualing algorithm for flexray systems[J].Ieice Transactions on Ingormation and Systems，2008，91(8)：2115-2123.

[9] AREOSPACE S.AS6802：Aerospace standard Time-Triggered Ethernet[S]，2011.

[10] ROLICH T，DOMOVIC D，GRUNDLER D.Testing of sereval overlapping optimization methods for bin-packing problem[C].Information & Communication Technology Electronic & Microelectronics(MIPRO).Opatija：IEEE，2013：975-980.