0 引言

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

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

1 基本概念和模型定義

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

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

    虛鏈路由多個(gè)數(shù)據(jù)流路徑P組成,，在拓?fù)浣Y(jié)構(gòu)中,，同一虛鏈路vl中的路徑P具有相同的起始端節(jié)點(diǎn)和部分重合的消息傳輸鏈路，數(shù)學(xué)符號(hào)表述虛鏈路vl如下式：

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

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

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

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

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

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

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

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

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

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

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

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

2.2.1 個(gè)體設(shè)計(jì)

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

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

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

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

    (1)避免沖突約束

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

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

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

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

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

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

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

    (3)起點(diǎn)端到終點(diǎn)端約束

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

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

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

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

2.2.3 遺傳算子設(shè)計(jì)

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

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

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

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

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

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

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

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

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

4 結(jié)論

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

參考文獻(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網(wǎng)絡(luò)的時(shí)間調(diào)度系統(tǒng)矩陣[J].航空計(jì)算技術(shù),，2004,，34(4)：24-27.

[7] 朱智林,，劉曉華，韓俊剛.TTCAN周期性任務(wù)的優(yōu)化調(diào)度算法[J].蘭州大學(xué)學(xué)報(bào),，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.