0 引言

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

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

1 基本概念和模型定義

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

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

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

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

2 問題轉化和算法設計

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

2.1 調度問題的描述和轉化

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

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

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

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

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

2.2 混合遺傳算法設計

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

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

2.2.1 個體設計

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

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

2.2.2 適應度函數

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

    (1)避免沖突約束

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

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

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

    (2)路徑和內存約束

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

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

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

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

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

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

    為實現妥當的時間觸發消息流安排，式（14）中得到的函數值Cost能很好地反映調度方案的綜合性能表現。

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

2.2.3 遺傳算子設計

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

3 仿真及結果分析

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

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

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

    遺傳算法與裝箱算法融合產生的混合遺傳算法克服了傳統過早收斂于某一局部解的問題，并實現了全局最優解的快速搜索。

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

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

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

4 結論

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

參考文獻

[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] 王慶祥，陳家琪.利用遺傳算法優化TTCAN網絡的時間調度系統矩陣[J].航空計算技術，2004，34(4)：24-27.

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