0 引言

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

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

1 基本概念和模型定義

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

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

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

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

2 問題轉化和算法設計

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

2.1 調度問題的描述和轉化

    在一相對復雜的拓撲結構中，時間觸發(fā)消息調度即為對于時間資源的調度利用，可以被轉化為二維裝箱問題。

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

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

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

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

2.2 混合遺傳算法設計

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

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

2.2.1 個體設計

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

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

2.2.2 適應度函數(shù)

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

    (1)避免沖突約束

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

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

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

    (2)路徑和內存約束

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

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

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

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

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

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

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

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

2.2.3 遺傳算子設計

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

3 仿真及結果分析

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

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

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

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

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

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

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

4 結論

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

參考文獻

[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網絡的時間調度系統(tǒng)矩陣[J].航空計算技術，2004，34(4)：24-27.

[7] 朱智林，劉曉華，韓俊剛.TTCAN周期性任務的優(yōu)化調度算法[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.