TTE 網(wǎng)絡(luò)通信鏈路自動(dòng)規(guī)劃方法研究*

鄭小鵬，張濤，王小輝

(1.中國(guó)運(yùn)載火箭技術(shù)研究院研究發(fā)展部，北京 100076；2.西北工業(yè)大學(xué) 軟件學(xué)院，陜西 西安 710072)

0 引言

在航空航天、武器裝備等領(lǐng)域，由于通信數(shù)據(jù)量呈現(xiàn)逐漸增大的趨勢(shì)，傳統(tǒng)的低傳輸總線已無(wú)法滿足現(xiàn)有高端領(lǐng)域的發(fā)展需求。時(shí)間觸發(fā)以太網(wǎng)在保留傳統(tǒng)以太網(wǎng)優(yōu)良特性的基礎(chǔ)上，同時(shí)確保了實(shí)時(shí)傳輸業(yè)務(wù)的確定性和可靠性。

TTE 網(wǎng)絡(luò)中的調(diào)度表用于對(duì)時(shí)間觸發(fā)業(yè)務(wù)進(jìn)行提前調(diào)度規(guī)劃，以保證時(shí)間確定性業(yè)務(wù)的高效無(wú)誤傳輸。然而對(duì)于消息調(diào)度中的調(diào)度表生成，目前缺少自動(dòng)化部署方案的產(chǎn)生，仍處于比較落后的人工手動(dòng)配置階段；同時(shí)，在對(duì)實(shí)時(shí)性消息的鏈路規(guī)劃方面也缺少相應(yīng)的自動(dòng)化規(guī)劃方法，消息調(diào)度和鏈路規(guī)劃過(guò)程效率底下。因此，在時(shí)間觸發(fā)消息的調(diào)度中，如何設(shè)計(jì)更為可行有效的自動(dòng)化部署方案來(lái)代替?zhèn)鹘y(tǒng)手工配置，是TTE 網(wǎng)絡(luò)當(dāng)下的研究熱點(diǎn)之一。

在國(guó)外，Long等[1]提出了一種動(dòng)態(tài)路徑規(guī)劃方案，該方案可以動(dòng)態(tài)實(shí)時(shí)調(diào)整消息傳輸過(guò)程中的路由轉(zhuǎn)發(fā)路徑。文獻(xiàn)[2]提出的多路徑傳輸方案可以給每條消息計(jì)算近似最優(yōu)的傳輸路徑；全局負(fù)載均衡(Global Load Balancing，GLB)[3]算法可以選擇每條消息傳輸?shù)淖顑?yōu)路徑，它的性能優(yōu)于動(dòng)態(tài)負(fù)載均衡(Dynamic Load Balancing，DLB)[4]算法。同時(shí)，文獻(xiàn)[5]提出的算法也可以為新消息分配最優(yōu)傳輸路徑，該算法結(jié)合了傳統(tǒng)多路徑傳輸方案和速率適配機(jī)制。文獻(xiàn)[6]圍繞多跳時(shí)間觸發(fā)以太網(wǎng)的調(diào)度優(yōu)化機(jī)制與算法進(jìn)行了深入研究，提出一種適用于時(shí)間觸發(fā)以太網(wǎng)的可調(diào)節(jié)時(shí)隙的高效調(diào)度算法,并通過(guò)時(shí)間觸發(fā)以太網(wǎng)網(wǎng)絡(luò)模型進(jìn)行演示和驗(yàn)證，提高網(wǎng)絡(luò)帶寬資源利用率。除此以外，有很多啟發(fā)式算法也用于負(fù)載均衡的研究。文獻(xiàn)[7]提出了一種改進(jìn)遺傳算法來(lái)解決多協(xié)議標(biāo)簽交換網(wǎng)絡(luò)(Multi-Protocol Label Switch，MPLS)的負(fù)載均衡問(wèn)題。文獻(xiàn)[8]提出了一種基于負(fù)載均衡的時(shí)間觸發(fā)以太網(wǎng)消息調(diào)度表生成方法，為改善機(jī)載網(wǎng)絡(luò)的消息調(diào)度性能提供了一種可行方案。

由以上分析可以看出，在負(fù)載均衡領(lǐng)域，面對(duì)不同的需求以及應(yīng)用場(chǎng)景的復(fù)雜化，對(duì)負(fù)載均衡的需求也越來(lái)越多，要求也越來(lái)越高。有些傳統(tǒng)算法無(wú)法解決的問(wèn)題，啟發(fā)式算法也被加入用于負(fù)載均衡的應(yīng)用，有非常高的應(yīng)用價(jià)值，很好地解決了負(fù)載均衡問(wèn)題。

本文使用頭腦風(fēng)暴優(yōu)化算法對(duì)TTE 網(wǎng)絡(luò)的通信鏈路規(guī)劃算法進(jìn)行了設(shè)計(jì)，對(duì)算法的理論基礎(chǔ)和實(shí)現(xiàn)流程做了詳細(xì)闡述，并仿真實(shí)現(xiàn)了基于頭腦風(fēng)暴優(yōu)化算法的TTE 網(wǎng)絡(luò)通信鏈路自動(dòng)規(guī)劃方法。在負(fù)載均衡研究方向，本文主要研究基于物理鏈路的負(fù)載均衡，即對(duì)于網(wǎng)絡(luò)中的鏈路傳輸，保證各個(gè)鏈路可以達(dá)到一種均衡的狀態(tài)，避免出現(xiàn)有些鏈路過(guò)載而有些鏈路輕載的情況。

1 TTE 網(wǎng)絡(luò)鏈路規(guī)劃模型

對(duì)于TTE 網(wǎng)絡(luò)而言，鏈路規(guī)劃實(shí)際上就是在通信任務(wù)確定的情況下對(duì)所有通信任務(wù)的路徑進(jìn)行規(guī)劃。

1.1 TTE 網(wǎng)路拓?fù)浣Y(jié)構(gòu)

本文采用環(huán)形網(wǎng)絡(luò)拓?fù)浼軜?gòu)。交換機(jī)之間互相連接形成環(huán)狀結(jié)構(gòu)，該結(jié)構(gòu)不僅可以承載不同業(yè)務(wù)信息，且具有很好的容錯(cuò)性，如圖1 所示。

圖1 TTE 網(wǎng)絡(luò)架構(gòu)拓?fù)?/p>

本文將以圖1 的網(wǎng)絡(luò)拓?fù)錇槔M(jìn)行鏈路規(guī)劃算法的設(shè)計(jì)，運(yùn)用圖論知識(shí)，將圖1 建模為無(wú)向圖Graph=(V，E)。圖1 中TTE 網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中包含了3 種物理設(shè)備類(lèi)型，分別是ES、NS 和Link，用NP 表示網(wǎng)絡(luò)中所有的ES和NS集合，NP=(ES，NS)={p1，p2，…，pnp}，np為節(jié)點(diǎn)數(shù)量。物理鏈路Link的集合定義為L(zhǎng)，例如節(jié)點(diǎn)pi到pj之間的鏈路l(l∈L)可以表示為lij，i≠j。圖2 為抽象后所形成的拓?fù)浣Y(jié)構(gòu)。

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

采用鄰接矩陣C=(cij)np×np定義節(jié)點(diǎn)之間的連通關(guān)系，cij表示為：

其中，cij=1 表示pi到pj之間有連接，cij=0 則表示pi到pj之間無(wú)連接。

定義通信流傳輸路徑為Pathij：

式(2)用一個(gè)有序的鏈路序列代表通信流傳輸路徑，i 表示通信流起始端點(diǎn)，j 表示通信流的接收端點(diǎn)。定義虛擬鏈路(Virtual Link，VL)為拓?fù)渲兴型ㄐ帕髀窂降牟⒓饺缡?3)所示：

1.2 約束條件

在給定網(wǎng)路拓?fù)浜屯ㄐ湃蝿?wù)情況下，為了衡量整個(gè)網(wǎng)絡(luò)的負(fù)載情況，避免網(wǎng)絡(luò)擁塞，參考文獻(xiàn)[9]做出如下定義：

式中，n 是網(wǎng)絡(luò)拓?fù)渲械逆溌窋?shù)量總和，Load 計(jì)算的是網(wǎng)路上所有鏈路的負(fù)載總和。

式中，參數(shù)φ 為拓?fù)渲兴墟溌返南⒇?fù)載平均值，計(jì)算方式為拓?fù)淇傌?fù)載除以總的鏈路數(shù)量。Dk表示第k 條鏈路上所有消息負(fù)載的均方差。

式(8)計(jì)算了網(wǎng)絡(luò)上的所有鏈路的方差，即是整個(gè)網(wǎng)絡(luò)拓?fù)涞姆讲睢Ｔ谀繕?biāo)函數(shù)的選擇中，將以式(8)中的均方差來(lái)表征網(wǎng)絡(luò)中負(fù)載均衡程度。

在每一次算法執(zhí)行之后，對(duì)每一個(gè)規(guī)劃好的鏈路都乘以當(dāng)前拓?fù)渲械南⒖偺鴶?shù)，用以衡量當(dāng)前規(guī)劃結(jié)果的最短路徑約束：

式中，解集x=(x1，x1，…，xn)，表示規(guī)劃好的每一條鏈路，其中xi表示第i 條鏈路上規(guī)劃的消息。

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

在算法執(zhí)行時(shí)需要使用適應(yīng)度函數(shù)來(lái)描述當(dāng)前規(guī)劃結(jié)果的優(yōu)劣，適應(yīng)度高的個(gè)體更有可能會(huì)被保留下來(lái)，繼續(xù)后續(xù)的迭代。適應(yīng)度函數(shù)的描述方式需要提前根據(jù)應(yīng)用場(chǎng)景進(jìn)行計(jì)算，本節(jié)將推導(dǎo)出本文使用的目標(biāo)函數(shù)，用于適應(yīng)度函數(shù)的計(jì)算。

本文約束下負(fù)載均衡的描述方程表示為D(x)，最短路徑的描述方程為R(x)。此時(shí)，目標(biāo)函數(shù)的約束方程為：

F(x)=D(x)·R(x)(10)

由于網(wǎng)絡(luò)拓?fù)渲忻織l鏈路的帶寬必須符合相應(yīng)的最大限度帶寬要求，因此，懲罰函數(shù)是在進(jìn)行鏈路規(guī)劃時(shí)的鏈路帶寬約束條件，可以將鏈路最大帶寬限制的最優(yōu)化問(wèn)題轉(zhuǎn)化為帶有懲罰函數(shù)的無(wú)約束限制問(wèn)題，以便于問(wèn)題的求解，同時(shí)懲罰函數(shù)可以對(duì)非可行解進(jìn)行相應(yīng)處理。具體計(jì)算公式如下：

式中，bwk、bwmaxk用來(lái)描述帶寬，前者是第k 條鏈路上目前被占用的帶寬，后者是鏈路最大帶寬；參數(shù)H 是一個(gè)無(wú)限大的正整數(shù)。當(dāng)滿足拓?fù)渲墟溌穾挼募s束限制條件時(shí)，則有bwk-bwmaxk≤0 恒成立，此時(shí)的目標(biāo)函數(shù)為G(x)=F(x)+H×0，此即為可行解的目標(biāo)函數(shù)值。

2 基于頭腦風(fēng)暴優(yōu)化算法的TTE 鏈路規(guī)劃

2.1 種群初始化

假設(shè)TTE 鏈路中通信流集合為Q，其中一個(gè)通信流的所有可行路徑集合為Qi，它的最大路徑編號(hào)為Nqi。例如在圖2 所示的網(wǎng)絡(luò)拓?fù)渲羞x出3 條通信流，定義為Message1、Message2、Messag3，它們的起始節(jié)點(diǎn)分別是0、1、2，終止節(jié)點(diǎn)分別是5、4、9，可行路徑及相關(guān)信息如表1 所示。此時(shí)，Q 即為3 條通信流所有的可行路徑集合，Qi是Messagei 的所有可行路徑集合，Nqi是Messagei的所有可行路徑數(shù)目。

表1 編碼示例

表1 中分別示例了每條消息的兩條可行路徑以及各個(gè)路徑的權(quán)重因子?？尚新窂绞峭ㄟ^(guò)深度優(yōu)先搜索得到的可行路由，每一條通信流含有多條路徑可以選擇，數(shù)字1、2…代表了當(dāng)前路徑的編號(hào)。因此對(duì)于每一條消息，可以將每一個(gè)路徑編碼為自然數(shù)1、2、3…，那么經(jīng)過(guò)編碼后的個(gè)體可以是111、121、222 等。

2.2 劃分聚類(lèi)

在初始種群產(chǎn)生之后，需要進(jìn)行劃分聚類(lèi)，將產(chǎn)生的N 個(gè)個(gè)體劃分為k 個(gè)類(lèi)。聚類(lèi)操作可以在一組數(shù)據(jù)中發(fā)現(xiàn)不同數(shù)據(jù)之間的聯(lián)系，將一組信息進(jìn)行分類(lèi)，類(lèi)內(nèi)的相似性越大，個(gè)體越相似，類(lèi)間差別也越大，代表聚類(lèi)效果越好。

在聚類(lèi)時(shí)，按照種群中個(gè)體之間歐式距離的大小，將個(gè)體劃分為k 個(gè)類(lèi)，此時(shí)具有更加相似特征的個(gè)體會(huì)被分為同一個(gè)類(lèi)。假設(shè)種群為：

其中，xi是d 維數(shù)據(jù)，將種群分為k類(lèi)，即C={c1，c2，…，ct，…，ck}類(lèi)，第t 個(gè)類(lèi)的聚類(lèi)中心為ctj。在本文進(jìn)行聚類(lèi)劃分時(shí)，使用負(fù)載均衡和最短路徑兩個(gè)數(shù)據(jù)進(jìn)行衡量。即種群中個(gè)體xi對(duì)應(yīng)的適應(yīng)值G(xi)是二維數(shù)據(jù)，第一維表示負(fù)載均衡的大小，第二維表示最短路徑的大小，其表示為：

種群X 中的個(gè)體xi與聚類(lèi)中心ctj的距離用dist(xi，ctj)表示。聚類(lèi)中心的衡量標(biāo)準(zhǔn)用以下函數(shù)表示：

式中，E 是所有類(lèi)內(nèi)距離之和；dist(xi，ctj)計(jì)算的是當(dāng)前個(gè)體與聚類(lèi)中心之間的距離，在本文中距離的計(jì)算方式采用歐式距離，公式如式(15)所示。E 越小聚類(lèi)效果越好。

聚類(lèi)操作可以改善搜索區(qū)域，算法一般采用K-means、fuzzy-C-means 等。頭腦風(fēng)暴算法中采用的是K-means算法，聚類(lèi)函數(shù)通常選用均方差的形式，公式如下：

其中，xi表示種群中的個(gè)體，vi是類(lèi)ct中個(gè)體的均值，E是種群中個(gè)體均方差的和。

由于目標(biāo)函數(shù)值為G(x)，當(dāng)它的值越大時(shí)，得到的個(gè)體越差。但是為了易于理解，一般適應(yīng)度越大，該個(gè)體的表現(xiàn)越好，因此，可以對(duì)目標(biāo)函數(shù)值G(x)進(jìn)行取倒數(shù)操作，取倒數(shù)之后的目標(biāo)函數(shù)值即是適應(yīng)度函數(shù)。

即適應(yīng)度函數(shù)定義為：

其中，xi表示第i 個(gè)個(gè)體對(duì)應(yīng)的解空間，adapt(xi)是該個(gè)體對(duì)應(yīng)的適應(yīng)值。此時(shí)，適應(yīng)度值越高則表示想法越好，越容易被延續(xù)至下一代。

2.3 更新想法

隨機(jī)思考主要用于跳出局部最優(yōu)解，是聚類(lèi)中心獨(dú)有的操作。隨機(jī)思考的過(guò)程為，首先產(chǎn)生一個(gè)在0～1 之間的隨機(jī)數(shù)，根據(jù)這個(gè)隨機(jī)數(shù)和概率Pc的大小判斷是否進(jìn)行隨機(jī)思考，若Pc大于隨機(jī)數(shù)，則隨機(jī)選擇一個(gè)類(lèi)，將該類(lèi)的聚類(lèi)中心進(jìn)行替換，替換的個(gè)體可以是解空間的任何一個(gè)解。

隨機(jī)思考完成之后，算法會(huì)以一定的概率選擇獨(dú)立思考還是融合思考。假設(shè)該概率為Pot，首先產(chǎn)生一個(gè)隨機(jī)數(shù)，若Pot大于隨機(jī)數(shù)，則進(jìn)行獨(dú)立思考，否則融合他人。

獨(dú)立思考是一個(gè)類(lèi)內(nèi)變異操作。在獨(dú)立思考時(shí)，算法首先會(huì)根據(jù)概率Po選擇需要對(duì)哪一個(gè)類(lèi)進(jìn)行變異。概率Po的計(jì)算公式如下：

式中，j 代表當(dāng)前選擇的類(lèi)，numj代表第j 個(gè)類(lèi)中個(gè)體的個(gè)數(shù)，N 代表種群中個(gè)體的數(shù)量。Po(j)則表示每個(gè)類(lèi)中的想法占總想法的比重。

在選擇好進(jìn)行獨(dú)立思考的類(lèi)之后，需要選擇使用類(lèi)中哪個(gè)個(gè)體進(jìn)行獨(dú)立思考。此時(shí)，概率Pco決定了是否選擇聚類(lèi)中心作為獨(dú)立思考的個(gè)體。將Pco的值與隨機(jī)數(shù)進(jìn)行比較，若大于隨機(jī)數(shù)則選擇聚類(lèi)中心，否則選擇除聚類(lèi)中心外的其他任何一個(gè)個(gè)體。需要獨(dú)立思考的個(gè)體選擇完成之后，執(zhí)行產(chǎn)生新個(gè)體的操作。在產(chǎn)生新個(gè)體時(shí)，根據(jù)如下公式進(jìn)行選擇：

其中，maxiter是最大迭代次數(shù)，curiter是當(dāng)前迭代次數(shù)；kslope 表示對(duì)數(shù)函數(shù)的斜率，一般取值為20；rand()是一個(gè)0～1 之間的隨機(jī)數(shù)。logsin()是一個(gè)對(duì)數(shù)傳遞函數(shù)，它的表達(dá)式如下：

除獨(dú)立思考以外，當(dāng)概率Pot大于隨機(jī)值的時(shí)候，使用融合他人的方式產(chǎn)生新個(gè)體。融合他人的方式表示選擇兩個(gè)個(gè)體生成新個(gè)體，在選擇個(gè)體時(shí)，可以選擇兩個(gè)聚類(lèi)中心進(jìn)行融合，也可以選擇隨機(jī)兩個(gè)個(gè)體進(jìn)行融合，具體選擇那種個(gè)體取決于概率Pct和隨機(jī)值的大小，若Pct大于0～1 之間的隨機(jī)值則選擇隨機(jī)兩個(gè)聚類(lèi)中心進(jìn)行融合，否則選擇類(lèi)中隨機(jī)兩個(gè)個(gè)體進(jìn)行融合。融合規(guī)則如下：

其中，xcombined是融合后的想法；xA和xB表示兩個(gè)類(lèi)中的想法；λ 是0～1 之間的隨機(jī)數(shù)，是混合的權(quán)重系數(shù)。假設(shè)當(dāng)前選中要融合的兩個(gè)個(gè)體為N1和N2，N1的第一條通信流的權(quán)重系數(shù)為(0，10，7)，個(gè)體N2的第一條通信流的權(quán)重系數(shù)為(4，9，2)，將兩個(gè)個(gè)體的第一條通信流的權(quán)重因子根據(jù)式(22)進(jìn)行融合，此時(shí)會(huì)產(chǎn)生一組新的權(quán)重系 數(shù)(0·λ+4·(1-λ)，10·λ+9·(1-λ)，7·λ+2·(1-λ))，選出該組權(quán)重系數(shù)中的最大值作為新的個(gè)體的第一條通信流權(quán)重，選擇它相應(yīng)的編碼作為新個(gè)體的編碼。對(duì)于每一條通信流都進(jìn)行這樣的操作之后，融合后的新個(gè)體就產(chǎn)生了。

2.4 算法終止條件

在獨(dú)立思考和融合思考中，保留的是適應(yīng)度較高的個(gè)體。例如獨(dú)立思考中產(chǎn)生的新個(gè)體xnew的適應(yīng)度高于原來(lái)的個(gè)體xold，則使用新個(gè)體替換原來(lái)的個(gè)體；否則種群不發(fā)生變化，還是保留原來(lái)的個(gè)體xold。若融合方式產(chǎn)生的新個(gè)體xcombined的適應(yīng)度高于個(gè)體xA，則對(duì)個(gè)體xA進(jìn)行替換；否則再比較個(gè)體xB。

每一輪迭代結(jié)束之后，判斷是否達(dá)到預(yù)先設(shè)置的最大迭代次數(shù)。若是，算法結(jié)束，此時(shí)適應(yīng)度最高的個(gè)體即是算法最優(yōu)解；否則繼續(xù)下一次迭代，下一輪迭代仍然從隨機(jī)思考開(kāi)始。同時(shí)，算法迭代次數(shù)需要選擇一個(gè)合適的值，若迭代次數(shù)過(guò)少，可能解還未成熟就已經(jīng)結(jié)束，只能得到次優(yōu)解，影響算法的解的質(zhì)量；若迭代次數(shù)過(guò)多，則會(huì)造成算法執(zhí)行時(shí)間過(guò)長(zhǎng)，影響算法整體效能。

3 仿真結(jié)果及對(duì)比分析

3.1 實(shí)驗(yàn)環(huán)境

拓?fù)洵h(huán)境如圖3所示，圖中包含13個(gè)節(jié)點(diǎn)，其中0、1、2、4、5、9、11、12表示為端系統(tǒng)，3、6、7、8、10表示為交換機(jī)。為了便于鏈路負(fù)載的計(jì)算，同時(shí)將鏈路也進(jìn)行標(biāo)號(hào)，表示為1～16的數(shù)字。每一條鏈路都是雙向通信。同時(shí)，本文預(yù)先設(shè)定了500條通信流，部分通信流信息如表2所示。TT消息的一般幀長(zhǎng)范圍是(Lmin=64 B，Lmax=1 518 B)，在本文實(shí)驗(yàn)中，每個(gè)消息幀長(zhǎng)設(shè)為不同的值，周期均為T(mén)=4 ms，暫不考慮其他約束條件，例如由擁塞引起的時(shí)延等。同時(shí)，每一條消息均是單源單目，即每條消息只含有一個(gè)起始節(jié)點(diǎn)和一個(gè)目的節(jié)點(diǎn)。

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

在本文中，設(shè)置通信流個(gè)數(shù)為500，每個(gè)通信流含有的可行路由數(shù)routecount 是一個(gè)不定值，每條通信流都有不同的可行路由數(shù)目。將通信流Messagei 簡(jiǎn)寫(xiě)為Mi，表2 列出了10 條通信流的源節(jié)點(diǎn)和目的節(jié)點(diǎn)。

表2 TTE 網(wǎng)絡(luò)拓?fù)涞耐ㄐ帕?/p>

由此，通過(guò)深度優(yōu)先搜索便可以得到500 條通信流的所有可行路徑，作為算法的可行解集合。

在算法環(huán)境的配置中，種群大小設(shè)為popsize，聚類(lèi)個(gè)數(shù)k=5。即一個(gè)種群中含有popsize 個(gè)個(gè)體，每一個(gè)個(gè)體都含有500 條通信流的某一個(gè)可行路徑，隨機(jī)數(shù)由1+rand()%routecount 確定，其中，rand()函數(shù)是用來(lái)取隨機(jī)值的函數(shù)，該式可以產(chǎn)生1～routecount 隨機(jī)數(shù)。并且在聚類(lèi)劃分時(shí)將種群分為5 類(lèi)進(jìn)行迭代。

3.2 算法結(jié)果對(duì)比分析

本文設(shè)置不同的種群數(shù)量，觀察在不同的種群數(shù)量下頭腦風(fēng)暴優(yōu)化算法和傳統(tǒng)遺傳算法呈現(xiàn)的變化趨勢(shì)。分別給出了兩種算法初始種群和最終種群中最佳個(gè)體適應(yīng)度、均方差和經(jīng)過(guò)的鏈路跳數(shù)的變化，進(jìn)行了算法內(nèi)部縱向比較，驗(yàn)證兩種算法的優(yōu)化效果。同時(shí)，在一定的種群數(shù)量下，給出了兩種算法規(guī)劃后在拓?fù)浜诵膮^(qū)域消息的分配情況，表征算法最優(yōu)解在拓?fù)渲械姆植记闆r。最后根據(jù)算法迭代中適應(yīng)度變化曲線對(duì)兩種算法的收斂趨勢(shì)進(jìn)行對(duì)比分析。

頭腦風(fēng)暴優(yōu)化算法和傳統(tǒng)遺傳算法在算法執(zhí)行前后種群中最佳個(gè)體的適應(yīng)度、均方差和經(jīng)過(guò)鏈路數(shù)量的變化百分比如表3 所示。

表3 算法得迭代前后個(gè)體指標(biāo)變化表

圖4 和圖5 是在抽象拓?fù)渲姓故玖水?dāng)種群數(shù)量為200時(shí)，頭腦風(fēng)暴算法和遺傳算法鏈路的負(fù)載情況。其中0、1、2、4、5、9、11、12 表示端系統(tǒng)，端系統(tǒng)沒(méi)有負(fù)載均衡的意義，因?yàn)閷?duì)于每一條通信流，從端系統(tǒng)出發(fā)到達(dá)下一個(gè)節(jié)點(diǎn)之間的鏈路是唯一的，由通信流起始和終止節(jié)點(diǎn)決定，因此從端系統(tǒng)出發(fā)的線段都標(biāo)記為淺灰色，不做區(qū)分。虛線框區(qū)域是由交換機(jī)組成的主干網(wǎng)絡(luò)，所有通信流都必須經(jīng)由這里到達(dá)其他節(jié)點(diǎn)，這里是負(fù)載均衡的核心區(qū)域。圖中灰色線段的深淺表示了這條鏈路的負(fù)載情況。

圖4 遺傳算法最優(yōu)個(gè)體負(fù)載分布

圖5 頭腦風(fēng)暴算法最優(yōu)個(gè)體負(fù)載分布

可以看出，頭腦風(fēng)暴算法在經(jīng)過(guò)迭代后，此區(qū)域的負(fù)載已經(jīng)趨近于均衡，鏈路上所經(jīng)過(guò)的負(fù)載大部分都分布在590～690 之間。而遺傳算法，負(fù)載分布在540～780之間，較頭腦風(fēng)暴優(yōu)化算法的結(jié)果稍差。

4 結(jié)論

雖然TTE 網(wǎng)絡(luò)目前在國(guó)外的研究已經(jīng)處于非常成熟的階段，但是目前國(guó)內(nèi)還處于研究起步階段，特別是針對(duì)TTE 網(wǎng)絡(luò)的鏈路規(guī)劃還鮮少有研究成果的發(fā)表。本文提出將頭腦風(fēng)暴優(yōu)化算法應(yīng)用于TTE 網(wǎng)絡(luò)的鏈路調(diào)度規(guī)劃，克服了手工配置的缺點(diǎn)，利用算法本身的自適應(yīng)性，自動(dòng)地對(duì)于拓?fù)洵h(huán)境下的TTE 消息進(jìn)行了路徑規(guī)劃，提升了TTE 網(wǎng)絡(luò)傳輸?shù)男?，也增?qiáng)了TTE 網(wǎng)絡(luò)的實(shí)時(shí)性和可靠性。