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

集約型時間觸發(fā)以太網(wǎng)拓撲優(yōu)化方法

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

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

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

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

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

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

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

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

1 集約型拓撲優(yōu)化系統(tǒng)模型與問題描述

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

圖1 拓撲結(jié)構(gòu)到網(wǎng)絡(luò)模型的抽象

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

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

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

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

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

1.2 架構(gòu)成本

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

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

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

網(wǎng)絡(luò)拓撲的優(yōu)化問題，本質(zhì)上是基于消息流和網(wǎng)絡(luò)組件特性所設(shè)計的一種多目標(biāo)優(yōu)化問題．網(wǎng)絡(luò)拓撲優(yōu)化問題不同于路由選擇問題，路由算法是在拓撲已知的前提條件下，按照業(yè)務(wù)需要選擇合適的路由路徑．本文重點研究的是TTE網(wǎng)絡(luò)的拓撲優(yōu)化問題，具體來說，是在給定TT流量任務(wù)的情況下，考慮RC流最大延遲和網(wǎng)絡(luò)的成本，通過調(diào)整交換機與鏈路，設(shè)計集約化的網(wǎng)絡(luò)拓撲．所提出的TTE拓撲優(yōu)化算法如圖3所示．由于TT流是事先規(guī)劃的，已經(jīng)離線設(shè)計好了調(diào)度表，在優(yōu)化過程中不刪減TT流量涉及到的交換機和鏈路，無需改變調(diào)度表，僅對RC流量涉及到的路由和拓撲進行調(diào)整．首先，根據(jù)給定的TT業(yè)務(wù)和RC業(yè)務(wù)設(shè)計能實現(xiàn)所有業(yè)務(wù)路由功能的任意拓撲及其路由方式，得到初始拓撲和初始路由表．然后，設(shè)計綜合考慮架構(gòu)成本和延遲性能的目標(biāo)函數(shù)(6)，將目標(biāo)函數(shù)作為拓撲的量化評價標(biāo)準，篩選出網(wǎng)絡(luò)延遲盡可能低，架構(gòu)盡可能更簡單的拓撲方案．優(yōu)化過程分為目標(biāo)交換機刪除及拓撲恢復(fù)、混合策略擇優(yōu)及鏈路去冗余3部分．最后，為了保證TT消息的可靠性，在優(yōu)化后拓撲的基礎(chǔ)上進行TT的雙冗余備份(見第3節(jié))，得到最終拓撲方案．

圖3 TTE拓撲優(yōu)化流程

2.1 目標(biāo)交換機刪除及拓撲恢復(fù)

由于交換機的成本和重要性高于物理鏈路，因此在獲得初始拓撲和路由表后，優(yōu)先優(yōu)化交換機，目標(biāo)是盡可能減少交換機數(shù)量．交換機優(yōu)化流程如下．

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

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

1) 恢復(fù)策略1

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

2) 恢復(fù)策略2

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

3) 恢復(fù)策略3

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

完成拓撲恢復(fù)后，計算可行拓撲的目標(biāo)函數(shù)值．如果目標(biāo)函數(shù)值小于初始拓撲或優(yōu)于上一輪結(jié)果，則用當(dāng)前優(yōu)化結(jié)果更新拓撲和路由．若仍有目標(biāo)交換機可以優(yōu)化，則進入下一輪目標(biāo)交換機的刪除和拓撲恢復(fù)過程．如果目標(biāo)函數(shù)值均大于初始拓撲和上一輪結(jié)果，則此輪不能優(yōu)化，選擇上一輪的結(jié)果并結(jié)束優(yōu)化過程．

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

圖4 初始路由表和拓撲示例1

刪減S1后，初始拓撲中的交換機S1及與S1相連的鏈路都會刪除．交換機刪除與拓撲恢復(fù)示例1如圖5所示．如圖5(a)所示，黃色虛線部分為刪減的交換機和物理鏈路，此時路由RC1、RC2和RC3將受到影響．

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

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

圖5 交換機刪除與拓撲恢復(fù)示例1

圖5(d)所示為按恢復(fù)策略3(局部廣度優(yōu)先路由恢復(fù))得到的拓撲．依次判斷受影響的RC任務(wù)是否能夠找到路徑進行傳輸，如對于RC1而言，如圖中紅色部分所示，發(fā)送端為E1，接收端為R2，E1的鄰居節(jié)點僅S2，S2的鄰居節(jié)點只有E2、E1、R1．在S1交換機被刪除后，找不到任何一條路徑使得路由RC1能夠從E1出發(fā)，最終到達R2，因此在圖5(d)所示的拓撲結(jié)構(gòu)上進行路由調(diào)整，無法滿足RC任務(wù)的需求，該策略不可行．

如圖6和圖7(a)所示給定初始路由表和初始拓撲，記為示例2．圖7(a)中的綠色部分的交換機和鏈路是被刪除的部分．通過3種恢復(fù)策略得到7(b)，7(c)和7(d)．與示例1相同，策略1選擇最小跳數(shù)按照初始路徑添加物理鏈路得到，策略2通過尋找“邊緣節(jié)點”添加物理鏈路得到．與示例1不同，示例2通過策略3可以找到路由滿足RC任務(wù)的路由調(diào)整方案，如圖中綠色部分所示．刪除交換機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，此時策略3可行．

圖6 示例2的初始路由

圖7 交換機刪除與拓撲恢復(fù)示例2

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

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

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

2.3 鏈路去冗余

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

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

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

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

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

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

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

圖8 示例1 的鏈路去冗余

3 雙冗余設(shè)計

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

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

圖9 雙冗余拓撲結(jié)構(gòu)

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

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

4 結(jié)果及分析

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

給定網(wǎng)絡(luò)參數(shù)如表1所示，用于計算目標(biāo)函數(shù)的值，評價拓撲方案的網(wǎng)絡(luò)延遲性能與架構(gòu)成本的綜合表現(xiàn)．

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

表2 RC流量帶寬分配間隔

4.2 恢復(fù)策略對比

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

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

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

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

4.3 拓撲算法優(yōu)化結(jié)果

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

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

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

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

5 結(jié) 語

本文提出了一種針對TTE網(wǎng)絡(luò)的集約型拓撲優(yōu)化方法．首先基于網(wǎng)絡(luò)演算推導(dǎo)RC消息延遲上界，設(shè)計能綜合評價延遲性能和架構(gòu)成本的目標(biāo)函數(shù)．然后提出最小介數(shù)節(jié)點刪除及混合策略恢復(fù)的拓撲優(yōu)化算法，并證明恢復(fù)策略性能與網(wǎng)絡(luò)初始拓撲和路由有關(guān)，從而說明混合策略的優(yōu)勢．此外，通過目標(biāo)函數(shù)篩選出最優(yōu)的拓撲優(yōu)化方案，并進行去冗余操作．最后，在優(yōu)化后的集約拓撲基礎(chǔ)上進行TT消息的雙冗余設(shè)計，進一步保障TT消息可靠性并實現(xiàn)RC消息的分流傳輸．此方法結(jié)合了確定性網(wǎng)絡(luò)的時延分析和冗余網(wǎng)絡(luò)的優(yōu)化策略，在保證TT消息準時傳輸和RC消息及時傳輸?shù)那闆r下，簡化網(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)拓撲優(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)用的時間觸發(fā)以太網(wǎng)性能優(yōu)化與評估技術(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］ 趙露茜，李 峭，林晚晴，等. 基于隨機網(wǎng)絡(luò)演算的TTE網(wǎng)絡(luò)時延分析[J]. 航空學(xué)報，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ù)研基金資助項目.

the Advanced Research Foundation of Civil Aerospace.

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