王紅春, 屈靜, 牛文生

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

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

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

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

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

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

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

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

eij=[vi,vj]

(1)

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

Pij=eii1+ei1i2+…+einj

(2)

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

Vlink=∪Pij

(3)

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

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

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

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

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

(4)

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

2.1 負(fù)載均衡

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

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

(5)

(6)

(7)

(8)

式中,Li是消息i的幀長(zhǎng),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é)點(diǎn)上負(fù)載的方差作為衡量負(fù)載均衡的指標(biāo),這個(gè)值越小,則說(shuō)明其負(fù)載均衡度越好。

2.2 通信路徑的選擇

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

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

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

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跳來(lái)完成傳輸。更多的跳數(shù)意味著更多的通信流將會(huì)在物理通信鏈路上傳輸,從而導(dǎo)致網(wǎng)絡(luò)上更大的負(fù)載。但是,對(duì)于整個(gè)TTE網(wǎng)絡(luò)來(lái)說(shuō),如果每個(gè)消息都選擇跳數(shù)最少的路徑作為傳輸路徑,可能會(huì)導(dǎo)致少量鏈路的負(fù)載過(guò)大,導(dǎo)致整個(gè)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)

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

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

(10)

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

(11)

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

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

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

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

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

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

3.1 算法設(shè)計(jì)思想

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

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

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

為了進(jìn)一步說(shuō)明算法中的設(shè)計(jì)轉(zhuǎn)換操作,我們使用2.3節(jié)中圖4的TTE拓?fù)浒咐?。圖4a)給出了拓?fù)鋬?yōu)化算法的初始拓?fù)浞桨浮琭1和f2是m1消息的2個(gè)幀,f3和f4分別用于m2和m3消息。4個(gè)幀初始的虛擬連路(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è)計(jì)方案是在圖5a)中呈現(xiàn)的拓?fù)?其中f2在VL2為ES1→NS2→ES4上路由,其他虛擬鏈路由保持不變。

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

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

例如,如果從圖5a)中呈現(xiàn)的拓?fù)浣Y(jié)構(gòu)刪除NS3,則在刪除之后應(yīng)添加物理鏈路以確保m1消息的實(shí)時(shí)傳輸,例如添加鏈路NS1→ES4。拓?fù)浣Y(jié)構(gòu)“修復(fù)”后,通過(guò)刪除組件的幀將重路由。因此,將上述刪除操作應(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è)計(jì)轉(zhuǎn)換操作是根據(jù)負(fù)載情況對(duì)攜帶消息幀的VL進(jìn)行重新路由。此操作使得幀從源節(jié)點(diǎn)到目的節(jié)點(diǎn)會(huì)經(jīng)過(guò)不同的數(shù)據(jù)流鏈接和交換機(jī)。

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

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

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

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

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

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

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

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

步驟2.2根據(jù)動(dòng)態(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);

即對(duì)所有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è)計(jì)轉(zhuǎn)換操作啟發(fā)式地增刪交換機(jī)和鏈路以確定最終拓?fù)?。如圖6所示,由初始解X和溫度初值T0開始,根據(jù)Metropolis準(zhǔn)則,以概率e接受新解X→XNEW,對(duì)當(dāng)前解重復(fù)“產(chǎn)生新解→計(jì)算目標(biāo)函數(shù)差→接受或丟棄”的迭代,并逐步衰減T0值,從而跳出局部最優(yōu)解,算法終止時(shí)的當(dāng)前解即為所得全局近似最優(yōu)解。

圖6 模擬退火算法流程

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

4 案例研究與仿真分析

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

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

節(jié)點(diǎn)標(biāo)號(hào)123456 1002513 2000221 3000112 4213020 5101000 6141100

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

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

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

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

5 結(jié) 論

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