汪 清，伍晨邦，陳 鵬，周 虎，吳芝亮

集約型時(shí)間觸發(fā)以太網(wǎng)拓?fù)鋬?yōu)化方法

汪 清1，伍晨邦2，陳 鵬1，周 虎3，吳芝亮4

(1. 天津大學(xué)電氣自動(dòng)化與信息工程學(xué)院，天津 300072；2. 天津大學(xué)國(guó)際工程師學(xué)院，天津 300072；3. 北京航天自動(dòng)控制研究所，北京 100070；4. 天津大學(xué)機(jī)械工程學(xué)院，天津 300072)

時(shí)間觸發(fā)以太網(wǎng)(time-triggered ethernet，TTE)是一種時(shí)間業(yè)務(wù)與事件業(yè)務(wù)混合技術(shù)，其在兼容標(biāo)準(zhǔn)以太網(wǎng)基礎(chǔ)上，保障時(shí)間觸發(fā)(time-triggered，TT)業(yè)務(wù)的確定性和可靠性，在航天通信領(lǐng)域具有顯著的優(yōu)勢(shì)．但由于航天網(wǎng)絡(luò)的高成本問題，在很大程度上限制了TTE的發(fā)展，因此研究集約型網(wǎng)絡(luò)拓?fù)淇山档拖到y(tǒng)架構(gòu)成本．本文首先引入復(fù)雜網(wǎng)絡(luò)理論，在滿足速率約束(rate-constrained，RC)消息延遲界門限的前提下，建立簡(jiǎn)化網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的問題模型．其次提出最小介數(shù)節(jié)點(diǎn)刪除及混合策略恢復(fù)的集約型拓?fù)鋬?yōu)化算法，通過對(duì)節(jié)點(diǎn)和邊的交替迭代收斂到目標(biāo)函數(shù)最小化的狀態(tài)．最后，在優(yōu)化后的集約型網(wǎng)絡(luò)基礎(chǔ)上設(shè)計(jì)雙冗余結(jié)構(gòu)，提高時(shí)間觸發(fā)業(yè)務(wù)的可靠性．實(shí)例的優(yōu)化前后結(jié)果表明，不同恢復(fù)策略在不同網(wǎng)絡(luò)結(jié)構(gòu)下性能不同，說明所提出混合策略的優(yōu)勢(shì)．通過優(yōu)化目標(biāo)函數(shù)對(duì)比表明所提出的方法能兼顧時(shí)延的前提下簡(jiǎn)化網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，降低架構(gòu)成本．本研究給出了基于TTE的實(shí)時(shí)航天通信的設(shè)備部署優(yōu)化算法及恢復(fù)策略，可用于舊網(wǎng)絡(luò)的升級(jí)與改造．通過實(shí)例給出了在隨機(jī)的BA無標(biāo)度網(wǎng)絡(luò)中，實(shí)現(xiàn)模型建立和拓?fù)鋬?yōu)化的過程，其算法思路和設(shè)計(jì)方法可進(jìn)一步應(yīng)用于更大規(guī)模的網(wǎng)絡(luò)拓?fù)鋬?yōu)化，為航天通信網(wǎng)絡(luò)優(yōu)化提供了參考．

時(shí)間觸發(fā)以太網(wǎng)；拓?fù)鋬?yōu)化；架構(gòu)成本；網(wǎng)絡(luò)時(shí)延；雙冗余設(shè)計(jì)

對(duì)于分布式航空電子系統(tǒng)而言，其系統(tǒng)實(shí)現(xiàn)的關(guān)鍵在于節(jié)點(diǎn)間通信的實(shí)時(shí)性和確定性．時(shí)間觸發(fā)以太網(wǎng)(time-triggered ethernet，TTE)將時(shí)間觸發(fā)技術(shù)的實(shí)時(shí)性、確定性、容錯(cuò)性同普通以太網(wǎng)的靈活性、動(dòng)態(tài)性和“盡力傳”相結(jié)合，為同步的、高度可靠嵌入式計(jì)算與網(wǎng)絡(luò)、容錯(cuò)設(shè)計(jì)提供支持，在航天航空領(lǐng)域得到了廣泛的應(yīng)用[1-2]．

航天總線的設(shè)計(jì)和部署需要面對(duì)機(jī)載內(nèi)部可利用空間狹小、架構(gòu)復(fù)雜且成本高昂的問題，研究拓?fù)鋬?yōu)化算法具有重要的實(shí)用價(jià)值．

拓?fù)鋬?yōu)化是在某些約束下為了滿足某些目標(biāo)對(duì)結(jié)構(gòu)設(shè)計(jì)的優(yōu)化．多數(shù)情況下需要對(duì)沖突的多子目標(biāo)求取Pareto最優(yōu)解[3]．Beshley等[4]證明了固定網(wǎng)絡(luò)拓?fù)湎驴梢酝ㄟ^路由管理提高網(wǎng)絡(luò)性能．Lee等[5]提出了通過資源偏好感知路由算法平衡網(wǎng)絡(luò)使用資源，提高了路由請(qǐng)求的性能瓶頸．Noman等[6]設(shè)計(jì)了線性控制器根據(jù)負(fù)載分配來緩解網(wǎng)絡(luò)擁塞問題，Zhang等[7]研究了基于相對(duì)延遲和實(shí)時(shí)約束的設(shè)備分配問題，同時(shí)，提出了一種基于模擬退火的優(yōu)化方法和雙冗余拓?fù)浣Y(jié)構(gòu)．王紅春[8]設(shè)計(jì)了考慮負(fù)載均衡和架構(gòu)成本的目標(biāo)函數(shù)來優(yōu)化拓?fù)洌瓵bdel等[9]提出了一種處理多目標(biāo)優(yōu)化問題的均衡優(yōu)化算法(MEOA)求取折衷的解．

本文針對(duì)航天總線系統(tǒng)集約化設(shè)計(jì)的需求，優(yōu)化TTE網(wǎng)絡(luò)拓?fù)洌诒ＷC延遲性能的前提下最小化架構(gòu)成本．首先，為研究網(wǎng)絡(luò)性能，引入復(fù)雜網(wǎng)絡(luò)量化性能表現(xiàn)，復(fù)雜網(wǎng)絡(luò)包含4種拓?fù)浣Y(jié)構(gòu)調(diào)整方式：刪除節(jié)點(diǎn)或邊[10]、新增節(jié)點(diǎn)或邊[11]、重連邊[12]和邊有向化[13]．接著，采用網(wǎng)絡(luò)演算方法分析速率約束(rate-constrained，RC)消息的延遲上界[14-16]．分析延遲上界是為了確保節(jié)點(diǎn)通信的確定性．然后，提出刪除節(jié)點(diǎn)或邊和新增邊的方式優(yōu)化拓?fù)?，在保證時(shí)間觸發(fā)(time-triggered，TT)消息實(shí)時(shí)性、確定性前提下，考慮介數(shù)最小節(jié)點(diǎn)刪除和混合拓?fù)浠謴?fù)策略，使得優(yōu)化后的拓?fù)浣Y(jié)構(gòu)能夠滿足網(wǎng)絡(luò)延遲的要求，提高RC消息的確定性．最后在上述基礎(chǔ)上設(shè)計(jì)成雙冗余拓?fù)浣Y(jié)構(gòu)提高TT消息的可靠性．

1 集約型拓?fù)鋬?yōu)化系統(tǒng)模型與問題描述

為了建立網(wǎng)絡(luò)拓?fù)鋬?yōu)化問題模型，首先將實(shí)際拓?fù)涑橄鬄閳D的形式，方便計(jì)算網(wǎng)絡(luò)參數(shù)，如節(jié)點(diǎn)介數(shù)、邊介數(shù)等．將交換機(jī)和終端作為節(jié)點(diǎn)，雙向物理鏈路作為無向邊．時(shí)間觸發(fā)網(wǎng)絡(luò)的實(shí)際拓?fù)淙鐖D1(a)所示，物理鏈路采用全雙工傳輸，圖中帶箭頭的實(shí)線表示業(yè)務(wù)傳輸?shù)倪壿嫹较颍橄蠛蟮耐負(fù)浣Y(jié)構(gòu)如圖1(b)所示．

圖1 拓?fù)浣Y(jié)構(gòu)到網(wǎng)絡(luò)模型的抽象

1.1 基于網(wǎng)絡(luò)演算的延遲界

雖然時(shí)間調(diào)度表可以保證TT消息的時(shí)間確定性，但是由于RC消息需要經(jīng)過多級(jí)復(fù)用排隊(duì)，因此RC消息時(shí)延的確定性界限變得復(fù)雜且無法保證．但是航天系統(tǒng)又必須保證所有的消息延遲在可控范圍內(nèi)，這樣才能確保整個(gè)通信系統(tǒng)的確定性[17]．因此時(shí)對(duì)于實(shí)時(shí)網(wǎng)絡(luò)而言，通信消息的端到端延遲的可預(yù)測(cè)性或延遲上界比統(tǒng)計(jì)特性更重要[18]．此外，由于BE 消息的優(yōu)先級(jí)低于RC消息，因此用RC消息的延遲狀況表示網(wǎng)絡(luò)延遲，可反應(yīng)網(wǎng)絡(luò)通信狀況．

網(wǎng)絡(luò)演算方法指的是以最小加代數(shù)和最大加代數(shù)為基礎(chǔ)，分析網(wǎng)絡(luò)性能的最壞邊界．在確定的網(wǎng)絡(luò)拓?fù)浜蜆I(yè)務(wù)模型下，可用網(wǎng)絡(luò)演算方法[19]分析流量在最壞情況下的端到端延遲作為網(wǎng)絡(luò)的性能指標(biāo)．按照最壞情況下的端到端進(jìn)行延遲計(jì)算，RC流量在網(wǎng)絡(luò)中的延遲上界是其所有訪問過的節(jié)點(diǎn)上可能的最大延遲和抖動(dòng)之和．

圖2 到達(dá)曲線與服務(wù)曲線的最大水平距離計(jì)算

假設(shè)在網(wǎng)絡(luò)拓?fù)渲性炊税l(fā)送條RC消息，目的端不定，且源端受到最大幀長(zhǎng)與最小幀間隔的限制，即源端的個(gè)RC消息的最壞延遲[21]為

1.2 架構(gòu)成本

成本對(duì)于網(wǎng)絡(luò)的廣泛應(yīng)用一直是一個(gè)重要的限制因素，降低成本是網(wǎng)絡(luò)部署的重要目標(biāo)之一．對(duì)于一個(gè)給定的網(wǎng)絡(luò)拓?fù)洌豢紤]通信開銷和架構(gòu)維護(hù)開銷，成本主要由終端、交換機(jī)、鏈路三者的成本組成．在拓?fù)鋬?yōu)化過程中，終端是固定的，因此主要對(duì)交換機(jī)和鏈路的架構(gòu)成本進(jìn)行優(yōu)化．

1.3 目標(biāo)函數(shù)

2 最小介數(shù)節(jié)點(diǎn)刪除及混合策略恢復(fù)

網(wǎng)絡(luò)拓?fù)涞膬?yōu)化問題，本質(zhì)上是基于消息流和網(wǎng)絡(luò)組件特性所設(shè)計(jì)的一種多目標(biāo)優(yōu)化問題．網(wǎng)絡(luò)拓?fù)鋬?yōu)化問題不同于路由選擇問題，路由算法是在拓?fù)湟阎那疤釛l件下，按照業(yè)務(wù)需要選擇合適的路由路徑．本文重點(diǎn)研究的是TTE網(wǎng)絡(luò)的拓?fù)鋬?yōu)化問題，具體來說，是在給定TT流量任務(wù)的情況下，考慮RC流最大延遲和網(wǎng)絡(luò)的成本，通過調(diào)整交換機(jī)與鏈路，設(shè)計(jì)集約化的網(wǎng)絡(luò)拓?fù)洌岢龅腡TE拓?fù)鋬?yōu)化算法如圖3所示．由于TT流是事先規(guī)劃的，已經(jīng)離線設(shè)計(jì)好了調(diào)度表，在優(yōu)化過程中不刪減TT流量涉及到的交換機(jī)和鏈路，無需改變調(diào)度表，僅對(duì)RC流量涉及到的路由和拓?fù)溥M(jìn)行調(diào)整．首先，根據(jù)給定的TT業(yè)務(wù)和RC業(yè)務(wù)設(shè)計(jì)能實(shí)現(xiàn)所有業(yè)務(wù)路由功能的任意拓?fù)浼捌渎酚煞绞?，得到初始拓?fù)浜统跏悸酚杀恚缓?，設(shè)計(jì)綜合考慮架構(gòu)成本和延遲性能的目標(biāo)函數(shù)(6)，將目標(biāo)函數(shù)作為拓?fù)涞牧炕u(píng)價(jià)標(biāo)準(zhǔn)，篩選出網(wǎng)絡(luò)延遲盡可能低，架構(gòu)盡可能更簡(jiǎn)單的拓?fù)浞桨福畠?yōu)化過程分為目標(biāo)交換機(jī)刪除及拓?fù)浠謴?fù)、混合策略擇優(yōu)及鏈路去冗余3部分．最后，為了保證TT消息的可靠性，在優(yōu)化后拓?fù)涞幕A(chǔ)上進(jìn)行TT的雙冗余備份(見第3節(jié))，得到最終拓?fù)浞桨福?/p>

圖3 TTE拓?fù)鋬?yōu)化流程

2.1 目標(biāo)交換機(jī)刪除及拓?fù)浠謴?fù)

由于交換機(jī)的成本和重要性高于物理鏈路，因此在獲得初始拓?fù)浜吐酚杀砗螅瑑?yōu)先優(yōu)化交換機(jī)，目標(biāo)是盡可能減少交換機(jī)數(shù)量．交換機(jī)優(yōu)化流程如下．

首先，識(shí)別是主動(dòng)優(yōu)化還是被動(dòng)優(yōu)化．主動(dòng)優(yōu)化對(duì)交換機(jī)按照重要性進(jìn)行排序，然后從低到高選擇目標(biāo)，節(jié)點(diǎn)交換機(jī)的重要性根據(jù)其節(jié)點(diǎn)的介數(shù)值衡量，即通過該節(jié)點(diǎn)的路由路徑的數(shù)量越多，該節(jié)點(diǎn)交換機(jī)越重要．被動(dòng)優(yōu)化隨機(jī)選擇一個(gè)交換機(jī)作為目標(biāo)交換機(jī)．

其次，選中目標(biāo)交換機(jī)后進(jìn)行刪除和拓?fù)浠謴?fù)．刪除之前需要先判斷目標(biāo)交換機(jī)是否是TT流量經(jīng)過的交換機(jī)．如果刪減會(huì)影響到TT任務(wù)的傳輸調(diào)度，則不能刪除，此時(shí)如果還存在其他可優(yōu)化的交換機(jī)，選擇下一個(gè)目標(biāo)交換機(jī)開始交換機(jī)的優(yōu)化刪減，如果不存在其他可優(yōu)化的交換機(jī)，則交換機(jī)優(yōu)化終止．如果目標(biāo)交換機(jī)不承載TT流量，則可對(duì)其進(jìn)行刪減．隨后調(diào)用3種恢復(fù)策略進(jìn)行拓?fù)浠謴?fù)，其中恢復(fù)策略1和恢復(fù)策略2是添加物理鏈路進(jìn)行鏈路重構(gòu)，恢復(fù)策略3是直接進(jìn)行路由調(diào)整，但可能無法滿足RC任務(wù)的需求．

1) 恢復(fù)策略1

從刪除的目標(biāo)節(jié)點(diǎn)出發(fā)，將目標(biāo)交換機(jī)的前后節(jié)點(diǎn)直接連接．前后節(jié)點(diǎn)優(yōu)先選擇最小跳數(shù)按照初始路徑進(jìn)行鏈路重構(gòu)．

2) 恢復(fù)策略2

從刪除的目標(biāo)節(jié)點(diǎn)出發(fā)，選擇目標(biāo)節(jié)點(diǎn)前后的邊緣節(jié)點(diǎn)進(jìn)行連接．邊緣性的強(qiáng)度通過節(jié)點(diǎn)介數(shù)值衡量，節(jié)點(diǎn)介數(shù)的值越低，交換機(jī)的邊緣性越高．由于邊緣性強(qiáng)的節(jié)點(diǎn)上通過的路由路徑數(shù)量更少，發(fā)生擁塞的概率更低，因此對(duì)篩選出被刪除的目標(biāo)節(jié)點(diǎn)前后節(jié)點(diǎn)中邊緣性最強(qiáng)的兩個(gè)節(jié)點(diǎn)進(jìn)行連接，其他節(jié)點(diǎn)與這兩個(gè)邊緣性最強(qiáng)的節(jié)點(diǎn)連接，實(shí)現(xiàn)間接連接．

3) 恢復(fù)策略3

最簡(jiǎn)單的是直接進(jìn)行路由調(diào)整，重新對(duì)刪除目標(biāo)節(jié)點(diǎn)后的網(wǎng)絡(luò)進(jìn)行路由．路由恢復(fù)采取局部廣度優(yōu)先遍歷的方法．若重新規(guī)劃的路由表能夠滿足RC任務(wù)的需要，那么無需添加鏈路即可得到可行拓?fù)洌匦乱?guī)劃的路由可能無法滿足RC任務(wù)的需求，例如無法建立RC任務(wù)的源-目邏輯鏈路，則只能采用恢復(fù)策略1或恢復(fù)策略2進(jìn)行鏈路重構(gòu)，獲取可行拓?fù)浣Y(jié)構(gòu)．

完成拓?fù)浠謴?fù)后，計(jì)算可行拓?fù)涞哪繕?biāo)函數(shù)值．如果目標(biāo)函數(shù)值小于初始拓?fù)浠騼?yōu)于上一輪結(jié)果，則用當(dāng)前優(yōu)化結(jié)果更新拓?fù)浜吐酚桑羧杂心繕?biāo)交換機(jī)可以優(yōu)化，則進(jìn)入下一輪目標(biāo)交換機(jī)的刪除和拓?fù)浠謴?fù)過程．如果目標(biāo)函數(shù)值均大于初始拓?fù)浜蜕弦惠喗Y(jié)果，則此輪不能優(yōu)化，選擇上一輪的結(jié)果并結(jié)束優(yōu)化過程．

以下通過實(shí)例介紹交換機(jī)刪除及拓?fù)浠謴?fù)的實(shí)現(xiàn)過程，給定如圖4所示的初始拓?fù)浜吐酚?，記為示?．考慮主動(dòng)優(yōu)化的情況，根據(jù)路由表，按照節(jié)點(diǎn)介數(shù)計(jì)算各交換機(jī)的重要性，如TT1經(jīng)過交換機(jī)1和交換機(jī)3，交換機(jī)1和3分別“加1”，得到各交換機(jī)上的節(jié)點(diǎn)介數(shù)從低到高排序?yàn)閧S1：3，S5：4，S7：5，S3：5，S2：6，S4：8}．對(duì)交換機(jī)按照重要性從低到高進(jìn)行優(yōu)化刪減，第一個(gè)待刪除的目標(biāo)交換機(jī)為S1．按照S1、S5、S7、S3、S2、S4的順序優(yōu)化刪減．

圖4 初始路由表和拓?fù)涫纠?

刪減S1后，初始拓?fù)渲械慕粨Q機(jī)S1及與S1相連的鏈路都會(huì)刪除．交換機(jī)刪除與拓?fù)浠謴?fù)示例1如圖5所示．如圖5(a)所示，黃色虛線部分為刪減的交換機(jī)和物理鏈路，此時(shí)路由RC1、RC2和RC3將受到影響．

圖5(b)所示為按恢復(fù)策略1(最小跳數(shù)優(yōu)先鏈路重構(gòu))得到的拓?fù)洌粨Q機(jī)S1的鄰居節(jié)點(diǎn)包括S2、S3和E1，目標(biāo)交換機(jī)前端路徑為E1→S1，后端路徑為S1→S2和S1→S3，刪減交換機(jī)S1后，策略1選擇最小跳數(shù)的方式直接按照初始路徑進(jìn)行鏈路重構(gòu)并連接目標(biāo)交換機(jī)的前后節(jié)點(diǎn)．E1位于前端，S2和S3位于后端，重構(gòu)的鏈路為E1→S2和E1→S3，如圖中橙色部分所示．

圖5(c)所示為按恢復(fù)策略2(邊緣節(jié)點(diǎn)優(yōu)先鏈路重構(gòu))得到的拓?fù)洌x擇邊緣節(jié)點(diǎn)進(jìn)行鏈路重構(gòu)，邊緣性大小與節(jié)點(diǎn)介數(shù)大小成反比．目標(biāo)節(jié)點(diǎn)后端的節(jié)點(diǎn)S2與S3的介數(shù)分別是6和5，S3更邊緣，因此目標(biāo)節(jié)點(diǎn)后端選擇S3，目標(biāo)節(jié)點(diǎn)前端僅有E1一個(gè)節(jié)點(diǎn)，且為發(fā)送端節(jié)點(diǎn)，因此直接選擇E1作為前端的邊緣節(jié)點(diǎn)．鏈路重構(gòu)策略為E1→S3、S3→S2、E1通過S3到達(dá)S2，如圖中橙色部分所示．

圖5 交換機(jī)刪除與拓?fù)浠謴?fù)示例1

圖5(d)所示為按恢復(fù)策略3(局部廣度優(yōu)先路由恢復(fù))得到的拓?fù)洌来闻袛嗍苡绊懙腞C任務(wù)是否能夠找到路徑進(jìn)行傳輸，如對(duì)于RC1而言，如圖中紅色部分所示，發(fā)送端為E1，接收端為R2，E1的鄰居節(jié)點(diǎn)僅S2，S2的鄰居節(jié)點(diǎn)只有E2、E1、R1．在S1交換機(jī)被刪除后，找不到任何一條路徑使得路由RC1能夠從E1出發(fā)，最終到達(dá)R2，因此在圖5(d)所示的拓?fù)浣Y(jié)構(gòu)上進(jìn)行路由調(diào)整，無法滿足RC任務(wù)的需求，該策略不可行．

如圖6和圖7(a)所示給定初始路由表和初始拓?fù)洌洖槭纠?．圖7(a)中的綠色部分的交換機(jī)和鏈路是被刪除的部分．通過3種恢復(fù)策略得到7(b)，7(c)和7(d)．與示例1相同，策略1選擇最小跳數(shù)按照初始路徑添加物理鏈路得到，策略2通過尋找“邊緣節(jié)點(diǎn)”添加物理鏈路得到．與示例1不同，示例2通過策略3可以找到路由滿足RC任務(wù)的路由調(diào)整方案，如圖中綠色部分所示．刪除交換機(jī)S2后，受影響的RC路由包括RC4與RC5，RC4從E2→S2→S5→R1調(diào)整為E2→S3→S5→R1，RC從E2→S2→S3→S4→S5→S7→R2調(diào)整為E2→S3→S4→S5→S7→R2，此時(shí)策略3可行．

圖6 示例2的初始路由

圖7 交換機(jī)刪除與拓?fù)浠謴?fù)示例2

2.2 混合策略擇優(yōu)

混合策略擇優(yōu)指交換機(jī)刪減后通過3種恢復(fù)策略進(jìn)行拓?fù)浠謴?fù)，并對(duì)目標(biāo)函數(shù)進(jìn)行評(píng)價(jià)和擇優(yōu)．第1.3節(jié)設(shè)計(jì)的目標(biāo)函數(shù)綜合考慮架構(gòu)成本和延遲性能，通過計(jì)算策略恢復(fù)后可行拓?fù)浣Y(jié)構(gòu)的目標(biāo)函數(shù)，量化各個(gè)拓?fù)浣Y(jié)構(gòu)在網(wǎng)絡(luò)延遲和架構(gòu)成本上的表現(xiàn)，在可行拓?fù)浞桨钢羞x擇目標(biāo)函數(shù)值最小的拓?fù)浣Y(jié)構(gòu).

如果最小的目標(biāo)函數(shù)值小于初始拓?fù)涞哪繕?biāo)函數(shù)值，則將這個(gè)拓?fù)浣Y(jié)構(gòu)作為交換機(jī)刪除和恢復(fù)后的拓?fù)洌捎谀繕?biāo)函數(shù)中對(duì)超過RC延遲的情況加了懲罰項(xiàng)，一旦出現(xiàn)RC延遲無法滿足需求的情況，目標(biāo)函數(shù)值會(huì)遠(yuǎn)大于滿足網(wǎng)絡(luò)情況．考慮到每一輪優(yōu)化都是貪婪的，因此將停止迭代的條件設(shè)為目標(biāo)函數(shù)值大于初始拓?fù)涞哪繕?biāo)函數(shù)值或目標(biāo)函數(shù)值不再較上一輪減少，此時(shí)表明目標(biāo)交換機(jī)不能再刪減，拓?fù)浞桨笐?yīng)取上一輪優(yōu)化后得到的結(jié)果．經(jīng)過盡可能多輪的交換機(jī)刪除和拓?fù)浠謴?fù)后，構(gòu)建出滿足延遲約束的集約化拓?fù)浣Y(jié)構(gòu)．

2.3 鏈路去冗余

由于在交換機(jī)刪除與拓?fù)浠謴?fù)過程中引入了添加鏈路的重構(gòu)策略(恢復(fù)策略1和恢復(fù)策略2)，可能會(huì)導(dǎo)致鏈路存在冗余，需要在后續(xù)執(zhí)行鏈路去冗余．

由于TT任務(wù)傳輸?shù)膶?shí)時(shí)性和確定性需求，在鏈路的去冗余操作時(shí)，不優(yōu)化影響到TT任務(wù)的物理 鏈路．

鏈路去冗余流程過程如下．首先，按照鏈路重要性進(jìn)行排序，重要性通過邊介數(shù)衡量，即每條物理鏈路上經(jīng)過的路由的數(shù)量．然后，按照鏈路的重要性從低到高選擇目標(biāo)鏈路，進(jìn)行去冗余刪除．

如果在某條目標(biāo)鏈路刪除后，路由調(diào)整無法完成所有的RC任務(wù)(路由不通)，則重新選擇下一條目標(biāo)鏈路．

刪除目標(biāo)鏈路之后，先進(jìn)行路由調(diào)整完成拓?fù)浠謴?fù)，若能調(diào)整成功，則計(jì)算調(diào)整后的目標(biāo)函數(shù)值，小于初始拓?fù)浠騼?yōu)于上一輪結(jié)果，更新鏈路刪除后的拓?fù)浜吐酚?，進(jìn)入下一條目標(biāo)鏈路的去冗余優(yōu)化．

如果在某條目標(biāo)鏈路刪除后，目標(biāo)函數(shù)值大于初始拓?fù)?RC延遲界超過門限)，則停止優(yōu)化，上一輪的結(jié)果即為鏈路優(yōu)化的結(jié)果．

仍以圖4所給出的示例1為例，進(jìn)行鏈路優(yōu)化．交換機(jī)優(yōu)化過程中刪減了S1與S5，當(dāng)繼續(xù)刪減S7后，拓?fù)浠謴?fù)后的目標(biāo)函數(shù)值會(huì)大于初始拓?fù)?，因此交換機(jī)優(yōu)化的結(jié)果是刪除S1與S5，如圖8(a)所示，圖中黃線部分為按最優(yōu)恢復(fù)策略(恢復(fù)策略1)所添加的鏈路．接下來進(jìn)行的鏈路優(yōu)化，圖中綠線虛線S7→S3為重要性最低的鏈路，是最先被刪除的鏈路．圖中紅色實(shí)線S4→S3為重要性次低的鏈路，但是在刪減這條鏈路后，計(jì)算得到的目標(biāo)函數(shù)超過了上一輪，因此不能刪除該鏈路，最終優(yōu)化后的結(jié)果刪除了綠線虛線S7→S3，結(jié)果如圖8(b)所示．

圖8 示例1 的鏈路去冗余

3 雙冗余設(shè)計(jì)

通過TTE協(xié)議調(diào)度表有效保證了TT消息傳輸?shù)膶?shí)時(shí)性和確定性．但是，除高實(shí)時(shí)性及高確定性外，TT消息傳輸還需要高可靠性．因此，本文還設(shè)計(jì)了雙冗余以保證TT消息的可靠傳輸．

雙冗余方案如圖9所示，節(jié)點(diǎn)和節(jié)點(diǎn)上有需要周期發(fā)送的TT消息．發(fā)送端在設(shè)計(jì)報(bào)文格式時(shí)，在以太網(wǎng)報(bào)文的數(shù)據(jù)區(qū)中加入報(bào)文的時(shí)間標(biāo)簽，然后分別通過初始通道和備用通道傳輸．對(duì)TT消息的物理通道采用雙冗余備份傳輸，在初始通道和備用通道上發(fā)送相同的TT消息，可以保證當(dāng)某條通道出現(xiàn)故障時(shí)重要的TT消息不丟失．接收端接收數(shù)據(jù)包后，根據(jù)時(shí)間標(biāo)簽過濾冗余數(shù)據(jù)，進(jìn)行去冗余處理．通過上述的雙冗余設(shè)計(jì)可以保證TT消息的可靠傳輸．

圖9 雙冗余拓?fù)浣Y(jié)構(gòu)

通過第2節(jié)的交換機(jī)優(yōu)化和鏈路優(yōu)化，得到優(yōu)化后的集約結(jié)構(gòu)，然后進(jìn)行雙冗余設(shè)計(jì)保證TT消息的可靠性．以圖10(a)所示的結(jié)構(gòu)為例，優(yōu)化后的集約結(jié)構(gòu)中含有兩組TT流量(TT流涉及的交換機(jī)和路由在虛線框內(nèi))，分別是TT1：E1→S1→E3和TT2：E2→S2→S3→E4．使用節(jié)點(diǎn)冗余實(shí)現(xiàn)雙冗余結(jié)構(gòu)，如10(b)所示，以E1和E3為冗余節(jié)點(diǎn)，得到備用通道E1→S1′→E3，同理得到E2→S2′→S3′→E4．采用節(jié)點(diǎn)冗余方案的網(wǎng)絡(luò)，調(diào)度表無需調(diào)整，能夠保證TT消息的實(shí)時(shí)性和確定性．TT消息通過兩條物理通道同時(shí)傳輸，TT1：E1→S1→E3；E1→S1′→E3和TT2：E2→S2→S3→E4；E2→S2′→S3′→E4．同時(shí)，非TT消息可以雙通道分散傳輸．以E1和E3為源節(jié)點(diǎn)和目的節(jié)點(diǎn)的RC消息有：RC1、RC3、RC4．以E2和E4為源節(jié)點(diǎn)和目的節(jié)點(diǎn)的RC消息有：RC6．這4條RC消息可以在備用通道中傳輸，調(diào)整后RC消息的路由變?yōu)椋篟C3：E1→S1′→E3，RC4：E1→S1′→E3，RC6：E2→S2′→S3′→E4，RC1不改變．

圖10 TTE雙冗余設(shè)計(jì)

對(duì)于雙冗余的TTE網(wǎng)絡(luò)，TT消息采用備份傳輸，非TT消息采用雙通道分散傳輸．當(dāng)雙冗余的TTE網(wǎng)絡(luò)發(fā)生故障時(shí)，可以自適應(yīng)地實(shí)現(xiàn)具有零故障恢復(fù)時(shí)間的信息傳輸，無需網(wǎng)絡(luò)故障冗余鏈路切換且丟棄窗口對(duì)網(wǎng)絡(luò)延遲的影響可以忽略，從而可提高系統(tǒng)的實(shí)時(shí)性．

4 結(jié)果及分析

4.1 參數(shù)設(shè)置

給定網(wǎng)絡(luò)參數(shù)如表1所示，用于計(jì)算目標(biāo)函數(shù)的值，評(píng)價(jià)拓?fù)浞桨傅木W(wǎng)絡(luò)延遲性能與架構(gòu)成本的綜合表現(xiàn)．

表1 參數(shù)設(shè)置

表2 RC流量帶寬分配間隔

4.2 恢復(fù)策略對(duì)比

交換機(jī)刪減后有3種恢復(fù)策略，策略1選擇最小跳數(shù)按照初始路徑直接進(jìn)行鏈路重構(gòu)，策略2選擇被優(yōu)化交換機(jī)的發(fā)送側(cè)和目標(biāo)側(cè)的邊緣節(jié)點(diǎn)進(jìn)行鏈路重構(gòu)，策略3不添加鏈路，直接調(diào)整路由．本文最終的拓?fù)浠謴?fù)采用混合策略擇優(yōu)，即選擇3種恢復(fù)策略對(duì)應(yīng)目標(biāo)函數(shù)值最小的一種．

仍以圖4和圖6給定的示例1和示例2為例，比較3種恢復(fù)策略的優(yōu)劣．拓?fù)鋮?shù)及采用不同策略恢復(fù)后的目標(biāo)函數(shù)值如表3所示．示例1和示例2的通信任務(wù)相同，都包括3組TT任務(wù)和7組RC任務(wù)，TT任務(wù)和RC任務(wù)的源-目節(jié)點(diǎn)相同，例如3組TT任務(wù)的源-目對(duì)是E1→R1、E2→R1和E3→R3．此外，示例1和示例2的交換機(jī)數(shù)量和位置相同，但是鏈路的連接情況不同，示例1中交換機(jī)節(jié)點(diǎn)的介數(shù)的均值為5.17，介數(shù)方差為2.47，而示例2中的節(jié)點(diǎn)介數(shù)的均值為5.00，介數(shù)方差為6.67．由圖5和圖7可知，示例1的恢復(fù)策略3不可行，示例2的恢復(fù)策略3可行．3種恢復(fù)策略得到的拓?fù)浣Y(jié)構(gòu)目標(biāo)函數(shù)如表3所示．

表3 恢復(fù)策略對(duì)比

由表3可知，示例1的最優(yōu)恢復(fù)策略是策略1，示例2的最優(yōu)恢復(fù)策略是策略2．表3中兩組示例的通信任務(wù)相同，交換機(jī)數(shù)量和位置也相同，但由于物理鏈路的連接方式不同，導(dǎo)致兩組示例的初始拓?fù)洳煌畠山M示例的節(jié)點(diǎn)介數(shù)的均值約為5，通過物理連接，使得兩組示例的節(jié)點(diǎn)介數(shù)的方差不同．示例1的方差小，各個(gè)節(jié)點(diǎn)發(fā)生擁塞的概率相差??；示例2的方差大，各個(gè)節(jié)點(diǎn)發(fā)生擁塞的概率相差大．示例2中恢復(fù)策略3占優(yōu)的原因在于示例2的初始拓?fù)涔?jié)點(diǎn)介數(shù)的方差比較大，通過策略2篩選出邊緣節(jié)點(diǎn)連接被刪除目標(biāo)交換機(jī)的前后節(jié)點(diǎn)，邊緣節(jié)點(diǎn)能夠分擔(dān)中心節(jié)點(diǎn)的傳輸壓力．而示例1中的方差比較小，使用策略3篩選的邊緣節(jié)點(diǎn)與中心節(jié)點(diǎn)的重要性相近，并不能起到很好的分擔(dān)效果，因此不如采用策略1按照最小跳數(shù)進(jìn)行鏈路重構(gòu)．而采用策略3不需要額外添加物理鏈路，架構(gòu)成本最為節(jié)省，但存在調(diào)整路由仍無法滿足RC任務(wù)的情況，而且即便策略3可行，其網(wǎng)絡(luò)延遲的表現(xiàn)是最差的．設(shè)計(jì)的算法采用混合策略，通過目標(biāo)函數(shù)篩選出最優(yōu)的恢復(fù)策略．

4.3 拓?fù)渌惴▋?yōu)化結(jié)果

由于恢復(fù)策略性能與網(wǎng)絡(luò)拓?fù)浜吐酚捎嘘P(guān)，因此全網(wǎng)的優(yōu)化采用混合策略，用最終優(yōu)化前后的目標(biāo)函數(shù)對(duì)比說明本文提出算法的有效性．選取10組初始 拓?fù)浜统跏悸酚?，其參?shù)和優(yōu)化前后的結(jié)果如表4 所示.

由表4可以看出，設(shè)計(jì)的最小介數(shù)節(jié)點(diǎn)刪除及混合策略恢復(fù)的拓?fù)鋬?yōu)化算法可以在滿足網(wǎng)絡(luò)延遲要求的前提下，犧牲少量的延遲性能，大幅降低架構(gòu)成本．優(yōu)化前后的總的目標(biāo)函數(shù)對(duì)比如圖11所示， 隨機(jī)選10組初始路由和拓?fù)?，?yàn)證所提算法的有效性.

表4 優(yōu)化前后結(jié)果對(duì)比

圖11 10組路由表優(yōu)化前后的目標(biāo)函數(shù)值

5 結(jié) 語

本文提出了一種針對(duì)TTE網(wǎng)絡(luò)的集約型拓?fù)鋬?yōu)化方法．首先基于網(wǎng)絡(luò)演算推導(dǎo)RC消息延遲上界，設(shè)計(jì)能綜合評(píng)價(jià)延遲性能和架構(gòu)成本的目標(biāo)函數(shù)．然后提出最小介數(shù)節(jié)點(diǎn)刪除及混合策略恢復(fù)的拓?fù)鋬?yōu)化算法，并證明恢復(fù)策略性能與網(wǎng)絡(luò)初始拓?fù)浜吐酚捎嘘P(guān)，從而說明混合策略的優(yōu)勢(shì)．此外，通過目標(biāo)函數(shù)篩選出最優(yōu)的拓?fù)鋬?yōu)化方案，并進(jìn)行去冗余操作．最后，在優(yōu)化后的集約拓?fù)浠A(chǔ)上進(jìn)行TT消息的雙冗余設(shè)計(jì)，進(jìn)一步保障TT消息可靠性并實(shí)現(xiàn)RC消息的分流傳輸．此方法結(jié)合了確定性網(wǎng)絡(luò)的時(shí)延分析和冗余網(wǎng)絡(luò)的優(yōu)化策略，在保證TT消息準(zhǔn)時(shí)傳輸和RC消息及時(shí)傳輸?shù)那闆r下，簡(jiǎn)化網(wǎng)絡(luò)，降低網(wǎng)絡(luò)物理成本．

［1］ Steiner W. TTEthernet specification[S]. Wien：TTTech Computertechnik AG，2008.

［2］ Wang Q，Teng L P，Cui X，et al. TTE scheduling method based on adaptive dual redundancy and performance analysis[J]. Chinese Journal of Engineering，2019，41(3)：393-400.

［3］ 陰書玉. 基于ESO算法的多目標(biāo)拓?fù)鋬?yōu)化及其應(yīng)用研究[D]. 太原：中北大學(xué)，2015.

Yin Shuyu. Research on Multi-objective Topology Optimization and Its Application Based on ESO Algorithm[D]. Taiyuan：North University of China，2015(in Chinese).

［4］ Beshley M，Seliuchenko M，Panchenko O，et al. Adaptive flow routing model in SDN[C]//2017 14th International Conference The Experience of Designing and Application of CAD Systems in Microelectronics (CADSM). Polyana，Ukraine，2017：298-302.

［5］ Lee D，Hong P，Li J. RPA-RA：A resource preference aware routing algorithm in software defined network [C]// 2015 IEEE Global Communications Conference (GLOBECOM). San Diego，USA，2015：1-6.

［6］ Noman H，Jasim M. A proposed linear multi-controller architecture to improve the performance of software defined networks[J]. Journal of Physics：Conference Series，2021，1773(1)：012008.

［7］ Zhang L，Lampe M，Wang Z. Multi-objective topology design of industrial ethernet networks[J]. Frequenz，2012，66(5/6)：159-165.

［8］ 王紅春. 面向DIMA應(yīng)用的時(shí)間觸發(fā)以太網(wǎng)性能優(yōu)化與評(píng)估技術(shù)研究[D]. 西安：西安電子科技大學(xué)，2019.

Wang Hongchun. Research on Performance Optimization and Evaluation Technology of Time-Triggered Ethernet for DIMA Application[D]. Xi’an：Xidian University，2019(in Chinese).

［9］ Abdel B，Mohamed R，Abouhawwash M. Balanced multi-objective optimization algorithm using improvement based reference points approach[J]. Swarm and Evolutionary Computation，2021，60：100791.

［10］ Motter A E. Cascade control and defense in complex networks[J]. Physical Review Letters，2004，93(9)：098701.

［11］ Huang W，Chow T W S. Effective strategy of adding nodes and links for maximizing the traffic capacity of scale-free network[J]. Chaos An Interdiplinary Journal of Nonlinear Ence，2010，20(3)：033123.

［12］ Jiang Z Y，Liang M G，Guo D C. Improving network transport efficiency by edge rewiring[J]. Modern Physics Letters B，2013，27(8)：1350056.

［13］ Hu K，Liu C，Hu T，et al. Enhancing traffic capacity for scale-free networks by the one-way links[J]. Journal of Physics A—Mathematical & Theoretical，2010，43(17)：175101.

［14］ Nikolaus P，Schmitt J，Schütze M. H-mitigators：Improving your stochastic network calculus output bounds[J]. Computer Communications，2019，144：188-197.

［15］ Wang H，Hu J Q，Niu W S. RC performance analysis based on model optimization with the aid of network calculus[J]. Photonic Network Communication，2019，37(2)：253-260.

［16］ Zhao L X，Pop P，Li Q，et al. Timing analysis of rate-constrained traffic in TTEthernet using network calculus[J]. Real Time Systems，2017，53(2)：254-287.

［17］ Jin D，Ryu J，Park J，et al. Bounding end-to-end delay for real-time environmental monitoring in avionic systems[C]// 2013 27th International Conference on Advanced Information Networking and Applications Workshops. Barcelona，Spain，2013：132-137.

［18］ Gutiérrez J J，Palencia J C，Harbour M G. Holistic schedulability analysis for multipacket messages in AFDX networks[J]. Real-Time Systems，2014，50(2)：230-269.

［19］ Finzi A，Mifdaoui A，F(xiàn)rances F，et al. Network calculus-based timing analysis of AFDX networks with strict priority and TSN/BLS shapers[C]//2018 IEEE 13th International Symposium on Industrial Embedded Systems(SIES). Graz，Austria，2018：1-10.

［20］ Xiang Y，Wang W，Zhang X，et al. Performance research on time-triggered ethernet based on network calculus[J]. EURASIP Journal on Wireless Communications and Networking，2014，2014(1)：1-9.

［21］ 趙露茜，李 峭，林晚晴，等. 基于隨機(jī)網(wǎng)絡(luò)演算的TTE網(wǎng)絡(luò)時(shí)延分析[J]. 航空學(xué)報(bào)，2016，37(6)：1953-1962.

Zhao Luxi，Li Qiao，Lin Wanqing，et al. Stochastic network calculus for analysis of latency on TTEthernet network[J]. Acta Aeronautica et Astronautica Sinica，2016，37(6)：1953-1962(in Chinese).

Intensive Time-Triggered Ethernet Topology Optimization

Wang Qing1，Wu Chenbang2，Chen Peng1，Zhou Hu3，Wu Zhiliang4

(1. School of Electrical and Information Engineering，Tianjin University，Tianjin 300072，China；2. Tianjin International Engineering Institute，Tianjin University，Tianjin 300072，China；3. Beijing Aerospace Automatic Control Institute，Beijing 100070，China；4. School of Mechanical Engineering，Tianjin University，Tianjin 300072，China)

Time-triggered ethernet(TTE)is a new technology of ethernet network communication，combining time-triggered and event-triggered traffic. This technology is compatible with the standard ethernet protocol，guarantees the certainty and reliability of time-triggered traffic，and has significant advantages in aerospace communication applications. However，the high cost of space networks limited the development of TTE to a great extent. Therefore，the study of intensive network topology can reduce the cost of system architecture. First，this paper introduced the complex network theory and established the problem model of a simplified network topology through a rate-constrained message delay threshold. Then，a topology optimization algorithm based on the deletion of the minimum number of nodes and mixed strategy recovery was proposed，converging to a state where the objective function was minimized using alternating iterations of nodes and edges. Finally，a dual redundancy structure was designed based on the optimized intensive network，improving the reliability of the time-triggered business. The optimization of objective function comparison shows that the proposed method can simplify the network topology and reduce the architecture cost when considering the time delay. This research provides the optimization algorithm and recovery strategy of real-time aerospace communication equipment deployment based on TTE. The algorithm and the strategy can be used to upgrade and optimize the old network deployment. The modeling and topology optimization process in a random Barabási-Albert scale-free network is explained by examples. The algorithm idea and the design method can be further applied to network topology optimization on a larger scale，which provides references for space communication network optimization.

time-triggered ethernet；topological optimization；cost of architecture；network delay；double redundancy design

V19

A

0493-2137(2022)09-0942-11

10.11784/tdxbz202101025

2021-01-14；

2021-03-09.

汪 清（1982— ），女，博士，副教授，wangq@tju.edu.cn.

陳 鵬，Chenpeng_1997@tju.edu.cn.

民用航天預(yù)研基金資助項(xiàng)目.

the Advanced Research Foundation of Civil Aerospace.

(責(zé)任編輯：王曉燕)