基于時間觸發(fā)DIMA架構(gòu)的網(wǎng)絡(luò)拓?fù)鋬?yōu)化

王紅春, 屈靜, 牛文生

(1.西安電子科技大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院, 陜西 西安 710071;2.西安電子科技大學(xué) 通信工程學(xué)院, 陜西 西安 710071;3.清華大學(xué)天津高端裝備研究院, 天津 300300; 4.西安航空計算技術(shù)研究所, 陜西 西安 710068)

面對未來信息化的作戰(zhàn)戰(zhàn)場和空-天-地“系統(tǒng)之系統(tǒng)”信息融合的需求，分布式綜合模塊化航空電子系統(tǒng)(distributed integrated modular avionics,DIMA)的概念于近年內(nèi)浮出水面，并在航空和航天領(lǐng)域得到了極大關(guān)注和重視[1-2]。對于DIMA 航電系統(tǒng)，涉及到多個子功能區(qū)域的分布式集成，更加強(qiáng)調(diào)任務(wù)關(guān)鍵和安全關(guān)鍵等性能保障機(jī)制在系統(tǒng)集成過程中的一致性性能。在DIMA這種實時分布式系統(tǒng)中，采用時間觸發(fā)(time-triggered,TT)的通信方式可以避免數(shù)據(jù)幀爭用物理鏈路，保證數(shù)據(jù)交換的實時性和準(zhǔn)確性，提高離線通信任務(wù)負(fù)載均衡分配的效果[3-4]。而在時間觸發(fā)以太網(wǎng)(time-triggered ethernet,TTE)場景中，用于安全關(guān)鍵的路由一般都是靜態(tài)的，它們在拓?fù)湓O(shè)計階段就被加載到終端和交換機(jī)中，在運(yùn)行階段不會因為檢測到網(wǎng)絡(luò)故障而動態(tài)重組，以避免幀丟失等錯誤的發(fā)生。由此可見，拓?fù)浣Y(jié)構(gòu)的優(yōu)化設(shè)計對于TTE網(wǎng)絡(luò)而言是至關(guān)重要的。

在網(wǎng)絡(luò)可靠性和拓?fù)湓O(shè)計方面有很多學(xué)者開展了研究工作，提出了幾個衡量網(wǎng)絡(luò)可靠性的度量，如：連通性、恢復(fù)力及可執(zhí)行性，并提出了解決拓?fù)湓O(shè)計問題的幾種方法：啟發(fā)式、元啟發(fā)式和基于數(shù)學(xué)規(guī)劃的精確求解法[5-6]。然而，這些方法不能被TTE直接利用，原因是傳統(tǒng)的拓?fù)湓O(shè)計算法是在拓?fù)湟阎那疤釛l件下，由通信業(yè)務(wù)選擇路徑進(jìn)而完成通信任務(wù)，而在基于時間觸發(fā)以太網(wǎng)的DIMA系統(tǒng)中，是根據(jù)已知業(yè)務(wù)，通過調(diào)整節(jié)點與交換機(jī)的互連關(guān)系來進(jìn)行設(shè)計。并且在傳統(tǒng)的設(shè)計算法中，并沒有考慮路徑選擇和負(fù)載均衡對拓?fù)浣Y(jié)構(gòu)設(shè)計產(chǎn)生的影響。

為了進(jìn)一步改善現(xiàn)有的拓?fù)湓O(shè)計算法，針對TTE網(wǎng)絡(luò)拓?fù)溥M(jìn)行優(yōu)化設(shè)計。考慮到TTE網(wǎng)絡(luò)的拓?fù)鋬?yōu)化是典型的NP問題，很難采用某種固定的解析方法得到最優(yōu)解，而模擬退火算法在啟發(fā)式算法中，具有應(yīng)對復(fù)雜系統(tǒng)的非線性不連續(xù)解集的能力，且通過其具體的應(yīng)用可以在全局最優(yōu)和局部最優(yōu)之間權(quán)衡，這些特點非常適用于本文所關(guān)注的課題[7]。因此，研究了Floyd算法和模擬退火算法，優(yōu)化目標(biāo)是使該網(wǎng)絡(luò)可以在給定通信任務(wù)情況下，生成一個通信路徑短、負(fù)載均衡兼顧低成本架構(gòu)的拓?fù)渚W(wǎng)絡(luò)，從而可以使得整體網(wǎng)絡(luò)拓?fù)浼軜?gòu)成本更低，整個網(wǎng)絡(luò)的節(jié)點以及鏈路上的流量分布更加均勻，更好的緩解在精確時間流情況下網(wǎng)絡(luò)擁塞問題。

1 基于TTE的 DIMA系統(tǒng)模型

在分布式綜合模塊化航空電子系統(tǒng)中，采用交換機(jī)骨干網(wǎng)絡(luò)將具有處理資源的嵌入式終端系統(tǒng)通過全雙工的通信方式將全局同步機(jī)制和時間觸發(fā)的數(shù)據(jù)流量添加到星型拓?fù)湟蕴W(wǎng)中，同時保持與SAE AS6802標(biāo)準(zhǔn)的兼容性[8]。對于TTE網(wǎng)絡(luò)，可以從物理拓?fù)浜土髁刻摂M拓?fù)?個方面來描述。物理拓?fù)滹@示了物理設(shè)備之間的TTE網(wǎng)絡(luò)互連，虛擬拓?fù)涿枋隽?種不同類型的通信流之間的TTE網(wǎng)絡(luò)通信鏈路，如時間觸發(fā)通信流、速率約束(rate constraint,RC)通信流和“盡力傳”(best effort,BE)通信流[9-11]。從而使得TTE網(wǎng)絡(luò)在一個物理網(wǎng)絡(luò)上可支持具有不同的實時性和安全性需求的應(yīng)用之間的通信。值得注意的是，討論的拓?fù)鋬?yōu)化問題是在集群層進(jìn)行的。

圖1 DIMA架構(gòu)下的TTE網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)

如圖1所示，從初始節(jié)點vi到目的節(jié)點vj的數(shù)據(jù)流鏈路可以表示為eij,即

eij=[vi,vj]

(1)

且節(jié)點vi和vj可以是端系統(tǒng)(end system,ES)或交換機(jī)(network switch,NS)。并對數(shù)據(jù)流路徑進(jìn)行如下定義:

Pij=eii1+ei1i2+…+einj

(2)

數(shù)據(jù)流路徑Pij是一個有序的數(shù)據(jù)流鏈路序列,連接一個發(fā)送端到一個接收端,在圖1中,數(shù)據(jù)流路徑P13將終端ES1連接到終端ES3,而P14將終端ES1連接到終端ES4。此外,根據(jù)ARINC 664part7規(guī)范,將虛擬鏈路(virtual links,VL)定義為網(wǎng)絡(luò)拓?fù)渲腥繑?shù)據(jù)流路徑Pij的一個并集[12],其數(shù)學(xué)表達(dá)式如(3)式

Vlink=∪Pij

(3)

2 拓?fù)浣Y(jié)構(gòu)設(shè)計問題描述

網(wǎng)絡(luò)拓?fù)湓O(shè)計問題,對于TTE網(wǎng)絡(luò)而言,實際上就是在給定通信業(yè)務(wù)的情況下,生成一個具體的網(wǎng)絡(luò)路徑,使業(yè)務(wù)可以準(zhǔn)時準(zhǔn)確地到達(dá)目的地。針對這一問題,本文主要從路徑短、負(fù)載均衡和低價構(gòu)成本這幾方面來進(jìn)行考慮,從而設(shè)計出優(yōu)秀的網(wǎng)絡(luò)拓?fù)洹?/p>

首先從網(wǎng)絡(luò)拓?fù)溟_始闡述這一問題,物理拓?fù)溆呻p向物理通信鏈路和包括端系統(tǒng)(end system,ES)和交換機(jī)(network switch,NS)的網(wǎng)絡(luò)節(jié)點構(gòu)成,運(yùn)用圖論的相關(guān)知識,將圖1中的TTE集群建模為無向圖G=(V,E),其中,V=VES+VNS表示網(wǎng)絡(luò)節(jié)點集合,V=(v1,v2…vN),下標(biāo)N為節(jié)點數(shù)量。E是連接節(jié)點的物理鏈路的集合,M是鏈路數(shù)量。節(jié)點vi到節(jié)點vj的鏈路e(e∈E)可以表示eij。圖1抽象后所形成的的拓?fù)浣Y(jié)構(gòu)，如圖2所示。

圖2 抽象出的拓?fù)浣Y(jié)構(gòu)

采用連接矩陣X=(xij)N·N定義節(jié)點之間的連通關(guān)系,其中xij如下:

(4)

式中，xij=1表示節(jié)點vi到節(jié)點vj之間有鏈路連接,xij=0則表示無連接。

2.1 負(fù)載均衡

由于TTE網(wǎng)絡(luò)通信本身所具有的時間確定性,并且在TTE網(wǎng)絡(luò)中節(jié)點和鏈路上的負(fù)載均衡可以顯著降低離線調(diào)度表生成的不可行的概率,同時也能保證整個網(wǎng)絡(luò)中的各個部分都能有足夠的閑時片剩余,以保證RC和BE任務(wù)的正常傳輸,所以負(fù)載均衡對于拓?fù)鋬?yōu)化設(shè)計非常重要[13]。因而本文使用TTE網(wǎng)絡(luò)中節(jié)點和鏈路上的負(fù)載均衡程度來作為拓?fù)湓O(shè)計的約束條件。

由于在給定的通信任務(wù)下,通過各節(jié)點和鏈路上的通信流可能存在不均勻情況,則需要通過定義如下的指標(biāo)對整網(wǎng)的負(fù)載情況進(jìn)行衡量:

(5)

(6)

(7)

(8)

式中,Li是消息i的幀長,Gi是消息i的周期,N是一條鏈路上的消息數(shù),M是拓?fù)渲械逆溌窋?shù),U(i)是在一條鏈路上傳輸?shù)乃邢⒌呢?fù)載,U(i,j)是網(wǎng)絡(luò)上所有鏈路的負(fù)載,U/M是流經(jīng)所有鏈路的負(fù)載均值,D(i,j)是負(fù)載的方差。以TTE網(wǎng)絡(luò)中各節(jié)點上負(fù)載的方差作為衡量負(fù)載均衡的指標(biāo),這個值越小,則說明其負(fù)載均衡度越好。

2.2 通信路徑的選擇

盡管每個任務(wù)都有其特定的發(fā)送端和接收端,但在同一個網(wǎng)絡(luò)拓?fù)渲袀鬏斅窂饺匀挥袔讉€可能的解決方案。因此需要用路徑生成算法來找出最優(yōu)的傳輸路徑[14]。圖3描述了具有10個節(jié)點(6個終端系統(tǒng)和4個交換機(jī))的TTE網(wǎng)絡(luò)拓?fù)涞氖纠?/p>

圖3 TTE網(wǎng)絡(luò)中的拓?fù)溥B接

從圖3我們可以看到,從ES2發(fā)送到ES5的TT流有5個可能的傳輸路徑:

1) ES2→NS1→NS4→ES5

2) ES2→NS1→NS2→NS4→ES5

3) ES2→NS1→NS3→NS4→ES5

4) ES2→NS1→NS2→NS3→NS4→ES5

5) ES2→NS1→NS3→NS2→NS4→ES5

路徑1)是需要跳數(shù)最少的路徑,只有2跳,路徑2)和3)是3跳,路徑4)和5)使用4跳來完成傳輸。更多的跳數(shù)意味著更多的通信流將會在物理通信鏈路上傳輸,從而導(dǎo)致網(wǎng)絡(luò)上更大的負(fù)載。但是,對于整個TTE網(wǎng)絡(luò)來說,如果每個消息都選擇跳數(shù)最少的路徑作為傳輸路徑,可能會導(dǎo)致少量鏈路的負(fù)載過大,導(dǎo)致整個TTE網(wǎng)絡(luò)的傳輸性能下降。

2.3 目標(biāo)函數(shù)的確定

網(wǎng)絡(luò)體系結(jié)構(gòu)的成本定義為拓?fù)渲兴形锢礞溌返某杀綜dt與交換機(jī)成本CNS之和,本文暫不考慮設(shè)備安裝費(fèi)用、通信信道費(fèi)用如信道的距離,建立和維護(hù)等開銷[15]。

(9)

在實際問題中,對于網(wǎng)絡(luò)拓?fù)涞墓こ淘O(shè)計方案要評價其優(yōu)劣,往往需要考慮多方面因素的影響,因此本文以TTE網(wǎng)絡(luò)中的拓?fù)浼軜?gòu)成本和負(fù)載方差作為目標(biāo)函數(shù),根據(jù)實際工程需求引入一個參數(shù)m,使得在架構(gòu)成本和負(fù)載均衡之間做出權(quán)衡,最終設(shè)計方案應(yīng)使得目標(biāo)函數(shù)盡可能小,即拓?fù)湓O(shè)計方案的成本更低,負(fù)載更均衡。

minf(X)=C(X)+m*D(i,j)

(10)

由于網(wǎng)絡(luò)拓?fù)渲忻總€節(jié)點的處理能力以及各條鏈路的帶寬必須符合相應(yīng)的限制要求,在進(jìn)行拓?fù)鋬?yōu)化時要考慮到各節(jié)點和鏈路的約束條件,因而本文采用罰函數(shù)法將有約束最優(yōu)化問題轉(zhuǎn)化為無約束的帶有罰函數(shù)的優(yōu)化問題來進(jìn)行求解,并對非可行解進(jìn)行相應(yīng)處理。

(11)

式中,bk是傳輸通信流所使用的帶寬,bmaxk是拓?fù)渲型ㄐ沛溌返淖畲髱?。參?shù)P是一個遠(yuǎn)大于目標(biāo)函數(shù)值的正整數(shù)。當(dāng)滿足拓?fù)渲泄?jié)點和鏈路的約束條件時,則有bk-bmaxk≤0恒成立,此時的目標(biāo)函數(shù)則有為G(X)=f(X)+P×0,此即為可行解所得的目標(biāo)函數(shù)值。

根據(jù)以上幾方面,考慮圖4中的例子,圖4描述了具有8個節(jié)點(4個ES節(jié)點和4個NS節(jié)點)的TTE網(wǎng)絡(luò)拓?fù)涞氖纠?個通信任務(wù)分配情況為:消息m1從ES1到ES4,消息m2從ES1到ES3,消息m3從ES2到ES4。

圖4 TTE拓?fù)鋬?yōu)化示例

在TTE網(wǎng)絡(luò)拓?fù)湓O(shè)計中,常用的方法是初步生成一個過度設(shè)計的拓?fù)?然后利用一些優(yōu)化算法進(jìn)行優(yōu)化設(shè)計。這類方法已經(jīng)被廣泛的應(yīng)用。圖4a)為一個初始過度設(shè)計的拓?fù)?假設(shè)消息m1和m3是RC幀,m2是TT幀,并且消息的時序?qū)傩?幀長決定傳輸時間,周期和截止時間)使得消息是可調(diào)度的即負(fù)載均勻分布。假設(shè)每個NS是20個單位成本和每條物理鏈接是10個單位成本,圖4a)具有總成本數(shù)為180(C(a)=4×20+10×10)。

通過進(jìn)一步優(yōu)化得到圖4b)所示拓?fù)?其成本數(shù)為110(C(b)=2×20+7×10)。該拓?fù)湄?fù)載是不均衡的。即所有消息都必須通過NS1。假設(shè)最壞情況時,m3必須等待m1和m2傳輸完后,才能繼續(xù)傳輸,這將導(dǎo)致m3錯過其最后期限,發(fā)生超時傳輸。然而,通過進(jìn)一步優(yōu)化網(wǎng)絡(luò)拓?fù)?可得圖4c)中的拓?fù)?其具有與圖4b)拓?fù)湎嗤牡统杀?并且它是可調(diào)度的。此時,消息m3通過NS2到達(dá)ES4而不是經(jīng)過擁塞的NS1,因此它能夠達(dá)到其最終期限。

3 網(wǎng)絡(luò)拓?fù)涞膬?yōu)化方法

3.1 算法設(shè)計思想

網(wǎng)絡(luò)拓?fù)鋬?yōu)化設(shè)計的本質(zhì)是路徑優(yōu)化的問題,我們所考慮的就是負(fù)載和路徑最短之間的平衡,從而使得通過整個網(wǎng)絡(luò)中的通信流處于相對均衡狀態(tài)[15]?？紤]到TTE網(wǎng)絡(luò)具有的拓?fù)淙我庑蕴攸c,在對通信任務(wù)路徑進(jìn)行選擇時,既不能只按照路徑最短準(zhǔn)則選擇通路,又不能只按照負(fù)載最低準(zhǔn)則選擇通路。原因是前者可能會導(dǎo)致部分鏈路上的負(fù)載過大,影響整網(wǎng)的負(fù)載均衡;后者則會導(dǎo)致傳輸路徑較長,最終引起整網(wǎng)負(fù)載增大的弊端。同時,由于每次計算目標(biāo)函數(shù)時都需要對通信路徑進(jìn)行選擇,可見在拓?fù)鋬?yōu)化問題中選擇適當(dāng)路徑算法的關(guān)鍵作用。在目標(biāo)函數(shù)的約束條件較為復(fù)雜的情況下,考慮到TTE網(wǎng)絡(luò)拓?fù)淇筛鶕?jù)通信業(yè)務(wù),通過調(diào)整節(jié)點與交換機(jī)的互連關(guān)系進(jìn)行設(shè)計的特點。正是這種拓?fù)浣Y(jié)構(gòu)的任意性使得拓?fù)鋬?yōu)化問題很難采用某種解析方法去解決,而啟發(fā)式算法能在有限的計算時間內(nèi)尋找次優(yōu)解的特點適用于對此問題的求解[16]。因此,本文將Floyd算法和模擬退火算法相結(jié)合,解決拓?fù)鋬?yōu)化問題。首先在采用路徑選擇算法求出給定通信任務(wù)下的最短距離和最短路徑的基礎(chǔ)上,進(jìn)一步使用模擬退火算法啟發(fā)式地對TTE網(wǎng)絡(luò)拓?fù)渲械慕粨Q機(jī)和鏈路進(jìn)行增刪操作,最終確定出路徑短、負(fù)載均衡兼顧成本低的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。

3.2 設(shè)計轉(zhuǎn)換操作

拓?fù)鋬?yōu)化算法通過從當(dāng)前拓?fù)湓O(shè)計方案移動到鄰近拓?fù)湓O(shè)計方案來探索局部搜索空間。鄰近拓?fù)湓O(shè)計方案是在當(dāng)前拓?fù)湓O(shè)計方案的基礎(chǔ)上通過使用設(shè)計轉(zhuǎn)換操作來確定的,使得生成的每個鄰近拓?fù)湓O(shè)計方案都使用目標(biāo)函數(shù)來進(jìn)行評估。

為了進(jìn)一步說明算法中的設(shè)計轉(zhuǎn)換操作,我們使用2.3節(jié)中圖4的TTE拓?fù)浒咐?。圖4a)給出了拓?fù)鋬?yōu)化算法的初始拓?fù)浞桨?。幀f1和f2是m1消息的2個幀,f3和f4分別用于m2和m3消息。4個幀初始的虛擬連路(VL)分配情況如下:

f1: VL1為ES1→NS1→NS3→ES4

f2: VL2為ES1→NS2→NS4→ES4

f3: VL3為ES1→NS1→NS3→ES3

f4: VL4為ES2→NS1→NS3→NS4

我們假設(shè)直接設(shè)計方案是在圖5a)中呈現(xiàn)的拓?fù)?其中f2在VL2為ES1→NS2→ES4上路由,其他虛擬鏈路由保持不變。

圖5 設(shè)計轉(zhuǎn)換示例

第一組設(shè)計轉(zhuǎn)換操作涉及NS,即根據(jù)網(wǎng)絡(luò)中的負(fù)載情況插入和刪除NS。插入操作意味著創(chuàng)建一個新的NS并添加到當(dāng)前的拓?fù)浞桨钢幸跃徑獠糠止?jié)點處過大的網(wǎng)絡(luò)負(fù)載。此時,所有節(jié)點以一定的概率與這個新插入節(jié)點連接,直到其1/2的端口被占用之后,在與新的NS連接的節(jié)點上路由的幀再進(jìn)行重路由操作。對于刪除操作,將根據(jù)網(wǎng)絡(luò)負(fù)載情況,選取一個負(fù)載較小的NS,刪除它及與其直接相連的鏈路。在NS被刪除后,考慮涉及的所有鏈路。對于每個中斷的路徑,應(yīng)用一個有門限約束的回溯跟蹤,以便找到另一條連續(xù)路徑,從源節(jié)點開始,盡可能遵循舊路徑,創(chuàng)建部分路徑。并在路徑短的約束下探索其鄰近,搜索到目的節(jié)點的另一條路徑。如果找不到替代路徑,則應(yīng)用后退移動,并將最后一條物理鏈接從部分路徑中移除。探索替代路徑,直到找到滿足連續(xù)性和距離短條件的路徑或者直到部分路徑變空為止。如果從初始部分路徑的一組NS中不存在這樣的替代路徑,則選擇具有可用端口的路徑,創(chuàng)建此NS與目標(biāo)之間的新連接,使路徑變得連續(xù)。如果產(chǎn)生的解決方案不能使目標(biāo)函數(shù)更優(yōu),則它將被拒絕,即這種解決方案不會被接收。

例如,如果從圖5a)中呈現(xiàn)的拓?fù)浣Y(jié)構(gòu)刪除NS3,則在刪除之后應(yīng)添加物理鏈路以確保m1消息的實時傳輸,例如添加鏈路NS1→ES4。拓?fù)浣Y(jié)構(gòu)“修復(fù)”后,通過刪除組件的幀將重路由。因此,將上述刪除操作應(yīng)用于當(dāng)前的解決方案,得到圖5b)中的拓?fù)浣Y(jié)構(gòu)和路由:

f1: VL1為ES1→NS1→ES4

f3: VL3為ES1→NS1→ES3

f4: VL4為ES2→NS1→NS4

f2幀被進(jìn)一步分配給VL2。

第二組設(shè)計轉(zhuǎn)換操作是根據(jù)負(fù)載情況對攜帶消息幀的VL進(jìn)行重新路由。此操作使得幀從源節(jié)點到目的節(jié)點會經(jīng)過不同的數(shù)據(jù)流鏈接和交換機(jī)。

將這一操作應(yīng)用于圖5b),我們得到圖5c)中的拓?fù)浞桨?。假設(shè)這一操作是先隨機(jī)選擇重路由f1的VL1,由圖可知VL1須通過擁塞的NS1(VL1,VL3和VL4通過)。但是,由于無法找到與f2的路由不相交的另一個不擁塞的路徑,因此f1不會被重路由。如果移動選擇f2,它不經(jīng)過擁擠路徑,也將被忽略。如果f3被重路由,則找到另一個非擁塞路徑,即VL3為ES1→NS2→ES3。因此VL3將在此路徑上重新路由。

拓?fù)鋬?yōu)化算法中使用的最后一組設(shè)計轉(zhuǎn)換是增減鏈路。與之前的移動類似,可以根據(jù)負(fù)載分布情況從當(dāng)前解決方案中插入或刪除鏈路,以便將它連接到臨近的2個隨機(jī)選擇的節(jié)點,其中最多有一個是ES。之后,應(yīng)用重路由策略。

例如,若在圖5b)中添加一個新的鏈路,則最可能的位置是在ES2和NS2之間。此外,考慮到拓?fù)浞桨副唤邮懿⑶覄h除鏈路操作被應(yīng)用,可能的刪除是鏈接ES2→NS1。 在這一系列移動中,刪除不會被拒絕,因為ES2沒有斷開連接。經(jīng)過這一操作,f4通過VL4為ES2→NS2→ES4重新路由,產(chǎn)生圖5c)中的拓?fù)浞桨浮?/p>

3.3 拓?fù)鋬?yōu)化算法設(shè)計

基于3.1節(jié)的算法設(shè)計思想,給出具體算法步驟如下:

步驟1獲取網(wǎng)絡(luò)的初始拓?fù)浣Y(jié)構(gòu)、通信任務(wù)分配情況及網(wǎng)絡(luò)節(jié)點和鏈路的約束條件,并將初始拓?fù)溆脠D的鄰接矩陣a(i,j)表示;

步驟2采用Floyd算法求給定通信任務(wù)的最短距離矩陣d(i,j)和最短路徑矩陣p(i,j);

步驟2.1賦初值:對所有i和j,d(i,j)=a(i,j),當(dāng)a(i,j)=無窮大,p(i,j)=0,否則為p(i,j)=j;k=1;

步驟2.2根據(jù)動態(tài)轉(zhuǎn)移方程:

d[k][i][j]=min(d[k-1][i][j],d[k-1][i][k]+d[k-1][k][j]),更新d(i,j)和p(i,j);

即對所有i和j,若d(i,k)+d(k,j)>=d(i,j),則轉(zhuǎn)子步驟2.3，否則d(i,k)+d(k,j)=d(i,j),p(i,j)=p(i,k),k=k+l,轉(zhuǎn)子步驟2.3；

步驟2.3重復(fù)執(zhí)行子步驟2.2直到k=n+l。

步驟3設(shè)定模擬退火法的相關(guān)控制參數(shù)。如初始溫度T0、控制降溫速度的衰減因子α,以及同一T值下的迭代次數(shù)N。

步驟4使用模擬退火算法運(yùn)用3種設(shè)計轉(zhuǎn)換操作啟發(fā)式地增刪交換機(jī)和鏈路以確定最終拓?fù)洹Ｈ鐖D6所示,由初始解X和溫度初值T0開始,根據(jù)Metropolis準(zhǔn)則,以概率e接受新解X→XNEW,對當(dāng)前解重復(fù)“產(chǎn)生新解→計算目標(biāo)函數(shù)差→接受或丟棄”的迭代,并逐步衰減T0值,從而跳出局部最優(yōu)解,算法終止時的當(dāng)前解即為所得全局近似最優(yōu)解。

圖6 模擬退火算法流程

這種拓?fù)鋬?yōu)化算法均衡地考慮了網(wǎng)絡(luò)拓?fù)渲新窂胶徒?jīng)過各節(jié)點的負(fù)載情況,較好地解決了兩者之間的矛盾且算法的復(fù)雜程度較低,可以根據(jù)通信任務(wù)較快地得到相對距離近的通信路徑,非常適合于在TTE網(wǎng)絡(luò)拓?fù)渲惺褂谩?/p>

4 案例研究與仿真分析

為了驗證上述拓?fù)鋬?yōu)化算法的正確性,對實驗仿真環(huán)境進(jìn)行如下設(shè)置:對圖3抽象得到如圖7所示的拓?fù)鋱D,其中包括10個節(jié)點(節(jié)點1至6為ES,節(jié)點7至10為NS),指定的通信任務(wù)分配情況如表1所示,共31個通信任務(wù)。表中的數(shù)字表示對應(yīng)行節(jié)點到列節(jié)點之間的消息數(shù)目，如從節(jié)點1到節(jié)點4之間有5條消息幀(單向)傳輸。針對拓?fù)湟?guī)模,設(shè)定合適的退火參數(shù),T0=500,衰減因子α=0.99,及同一T值下的迭代次數(shù)N=20。由于時間觸發(fā)消息實際幀長范圍是[64 byte,1 518 byte][13],因此,在本次仿真中,每個消息幀長設(shè)為相同值Lk=256 byte,周期設(shè)為G=4 ms,設(shè)每個NS有16個端口、20個單位成本,每條物理鏈路是10個單位成本,暫不考慮網(wǎng)絡(luò)擁塞及其所引起的時延問題。

圖7 抽象出的TTE網(wǎng)絡(luò)拓?fù)?/p>

節(jié)點標(biāo)號123456 1002513 2000221 3000112 4213020 5101000 6141100

本次仿真基于Visual Studio2015的仿真平臺,利用計算機(jī)編程仿真的方法對本文提出的TTE網(wǎng)絡(luò)拓?fù)鋬?yōu)化設(shè)計算法進(jìn)行分析。通過詳細(xì)比較直接連接方案和在此基礎(chǔ)上采用優(yōu)化算法所得的優(yōu)化設(shè)計方案,得到了圖8及表2中的數(shù)據(jù)。

圖8 拓?fù)鋬?yōu)化仿真結(jié)果對比圖

方案交換機(jī)數(shù)/臺鏈路數(shù)/條負(fù)載均值/幀負(fù)載方差/幀網(wǎng)絡(luò)體系代價/單位 直接設(shè)計41218.5226.754×20+12×10=200 優(yōu)化設(shè)計3923.6713.553×20+9×10=150

由上述數(shù)據(jù)可以看出，與直接設(shè)計方案相比較，本文提出的優(yōu)化算法所得到的設(shè)計方案通過采用3種設(shè)計轉(zhuǎn)換使得交換機(jī)數(shù)量和鏈路數(shù)量有所減少，網(wǎng)絡(luò)體系代價相比直接連接方案有了明顯降低，負(fù)載方差從26.75降至13.55，表明負(fù)載均衡度有了很大改善，網(wǎng)絡(luò)中的流量分布更加均勻，避免了網(wǎng)絡(luò)擁塞的出現(xiàn)?？傊?，本文的優(yōu)化算法所得到的拓?fù)浞桨羔槍TE網(wǎng)絡(luò)可根據(jù)通信業(yè)務(wù)來調(diào)整節(jié)點與交換機(jī)的互連關(guān)系的特點進(jìn)行設(shè)計使得最終的拓?fù)浣Y(jié)構(gòu)得到優(yōu)化，更加有利于實際工程應(yīng)用。

5 結(jié) 論

以時間觸發(fā)以太網(wǎng)為互連基礎(chǔ)設(shè)施的DIMA系統(tǒng)為研究背景，提出了一種將Floyd算法和模擬退火算法結(jié)合的拓?fù)鋬?yōu)化算法，在進(jìn)行通信任務(wù)的快速路徑選擇基礎(chǔ)上，結(jié)合模擬退火算法較強(qiáng)的局部搜索能力，生成一個負(fù)載均衡兼顧低成本架構(gòu)的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。案例研究表明，該拓?fù)鋬?yōu)化算法充分考慮了TTE網(wǎng)絡(luò)通信本身具有的時間確定性和網(wǎng)絡(luò)拓?fù)涞娜我庑裕梢允沟谜w網(wǎng)絡(luò)拓?fù)浼軜?gòu)成本更低，整個網(wǎng)絡(luò)的結(jié)點以及鏈路上的負(fù)載分布更加均勻，更好地緩解在精確時間流情況下的網(wǎng)絡(luò)擁塞問題，為DIMA系統(tǒng)提供了高性能且更可靠的通信環(huán)境。