文獻標識碼: A
DOI:10.16157/j.issn.0258-7998.2016.10.025
中文引用格式: 李炳乾,王勇,譚小虎,等. 基于混合遺傳算法的TTE靜態(tài)調(diào)度表生成設(shè)計[J].電子技術(shù)應用,2016,42(10):96-99,103.
英文引用格式: Li Bingqian,Wang Yong,Tan Xiaohu,et al. Hybrid-GA based static schedule generation for time-triggered Ethernet[J].Application of Electronic Technique,2016,42(10):96-99,103.
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ù)級增長的時間復雜度,表的變化將引起災難性的情況,直接影響航空器的飛行和任務(wù)安全。避免已生成的調(diào)度表變化,重新在預留時間段進行消息調(diào)度就可以妥善解決TTE中TT消息的靈活調(diào)度問題,由此需要一種能夠快速準確地尋找全局最優(yōu)解的調(diào)度表生成方法降低已有消息的時間占用,以實現(xiàn)預留資源,應對隨機產(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ù)流鏈接表示為lij=[vi,vj],其中vi和vj分別表示鏈路兩端的源節(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)化
在一相對復雜的拓撲結(jié)構(gòu)中,時間觸發(fā)消息調(diào)度即為對于時間資源的調(diào)度利用,可以被轉(zhuǎn)化為二維裝箱問題。
用參數(shù)periodmin表示需要調(diào)度消息的最小消息周期。在AS6802協(xié)議[9]中的簇周期(cluster cycle)用LCM(period)表示,即為所有消息周期的最小公倍數(shù),簇周期在整個消息傳輸過程中周期性地重復實現(xiàn)時間觸發(fā)消息的連續(xù)傳輸。同時設(shè)置所有消息周期的最大公約數(shù),用GCD(period)表示。通過折疊未進行資源分配的一維時間軸線(如圖2),將問題轉(zhuǎn)化為二維圖形[5],見圖3(a)、(b)。
為簡化模型,引入時間片(time slot)的概念,假設(shè)在每一鏈路l中,消息最多利用一個時間片即可實現(xiàn)長度length的全部傳輸,設(shè)置時間片長度為TSTS,由此可以得出時間段的時間片個數(shù)為NSTS:
當拓撲結(jié)構(gòu)中兩條路徑Pa和Pb之間任一傳輸鏈接均不產(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問題,無法通過準確的解法解決,遺傳算法在復雜系統(tǒng)優(yōu)化計算中的高效搜索可以適應大規(guī)模非線性不連續(xù)多模態(tài)功能[10]。通過將遺傳算法和裝箱算法相融合,可以達到算法的全局和局部搜索能力的平衡。
圖4是混合遺傳算法的流程圖,包括初始化和遺傳迭代的簡要過程描述,下面將就混合遺傳算法的具體實現(xiàn)進行詳細描述。
2.2.1 個體設(shè)計
個體參數(shù)應當包括以下幾個關(guān)鍵數(shù)據(jù):時間片分配、每一節(jié)點的時間分配、節(jié)點狀態(tài)、目標函數(shù)值和適應度函數(shù)值等。
在算法起始進行參數(shù)設(shè)置時應當對個體進行初始化,節(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 適應度函數(shù)
利用懲罰函數(shù)對調(diào)度條件進行約束,實現(xiàn)適應度函數(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)生相應的延時,控制中繼鏈路節(jié)點在消息傳輸過程中的幀派發(fā)時間和存儲延遲時間對于描述通信模型十分重要,利用式(8)~(10)描述消息幀通過某一節(jié)點的收發(fā)時刻保持在一定范圍。
max(hopdelay)表示消息經(jīng)過節(jié)點的最大延遲上限,[vertexx,vertexj]和[vertexj,vertexy]分別表示某一傳輸路徑中兩個毗鄰的鏈路端點特征,它們共享一個公共節(jié)點vertexj。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ù)Pnlt3,見式(13),其中參數(shù)c是大于1的常數(shù)。
為實現(xiàn)妥當?shù)臅r間觸發(fā)消息流安排,式(14)中得到的函數(shù)值Cost能很好地反映調(diào)度方案的綜合性能表現(xiàn)。
其中,參數(shù)ω1、ω2和ω3是調(diào)整3個懲罰函數(shù)影響比例的和為1的常數(shù)。從設(shè)計目標可知,Cost越大,遺傳算法中基因保留在子代的可能性越小,因此設(shè)置適應度函數(shù)如式(15),個體適應度越大,表示越適應外部環(huán)境的需求。
2.2.3 遺傳算子設(shè)計
基于比例的選擇算子設(shè)計保證了遺傳概率和適應度函數(shù)的正相關(guān)。交叉算子根據(jù)遺傳算法為下一代更好地遺傳父代基因所設(shè)計,選擇個體生成子代之前,使個體根據(jù)適應度值降序排列為一列。接著,個體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)較為復雜,見圖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個。
此外,對單純遺傳算法和混合遺傳算法的適應性函數(shù)最終收斂情況進行比較,遺傳代數(shù)和適應函數(shù)的關(guān)系可以清楚地反映在圖7中。混合遺傳算法在收斂速度較快,很快收斂到最優(yōu)解附近,而遺傳算法則收斂至局部解附近,收斂速度不佳。在遺傳2 000代時,混合遺傳算法收斂于適應函數(shù)值79.68,遺傳算法2 000代時則收斂于適應函數(shù)值83.54。
遺傳算法與裝箱算法融合產(chǎn)生的混合遺傳算法克服了傳統(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 結(jié)論
為實現(xiàn)時間資源的預留,保證網(wǎng)絡(luò)傳輸靈活性,提出了一種基于混合遺傳算法的TT消息調(diào)度表生成方法。通過問題轉(zhuǎn)化和算法在解域空間的優(yōu)化搜索,得到最優(yōu)的調(diào)度方案。仿真實驗對單純遺傳算法和混合遺傳算法進行比較,混合遺傳算法在搜索結(jié)果、收斂速度和時間片占用上都超越了純遺傳算法性能,能夠滿足靈活性設(shè)計要求,適應未來機載航空環(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.