付凡成

(南昌理工學(xué)院 計(jì)算機(jī)信息工程學(xué)院，江西 南昌 330044)

0 引 言

虛鏈路如何被采用一直是構(gòu)建覆蓋網(wǎng)絡(luò)的關(guān)鍵難題之一。為了提高物理網(wǎng)絡(luò)中相關(guān)特征能力，同時也為了滿足上層應(yīng)用需求，從物理網(wǎng)絡(luò)中擇取一部分關(guān)鍵節(jié)點(diǎn)，基于虛鏈路關(guān)聯(lián)成一個虛擬的邏輯網(wǎng)絡(luò)，這種網(wǎng)絡(luò)稱之為覆蓋網(wǎng)絡(luò)。覆蓋網(wǎng)絡(luò)的形式種類多樣，針對不同類別的覆蓋網(wǎng)絡(luò)，其虛鏈路在采用過程中需要關(guān)注的因子、網(wǎng)絡(luò)拓?fù)涞臉?gòu)造特點(diǎn)以及實(shí)現(xiàn)的算法等均不一樣。

在各種點(diǎn)對點(diǎn)網(wǎng)絡(luò)中，為了滿足網(wǎng)絡(luò)節(jié)點(diǎn)的動態(tài)添加與刪除，文獻(xiàn)[1]提出分布式算法實(shí)現(xiàn)的選取策略，用來建立動態(tài)變化的覆蓋網(wǎng)絡(luò)拓?fù)?。?dāng)對網(wǎng)絡(luò)節(jié)點(diǎn)進(jìn)行添加與刪除之后，余下網(wǎng)絡(luò)節(jié)點(diǎn)會依據(jù)分布式算法實(shí)現(xiàn)路由指標(biāo)項(xiàng)的動態(tài)調(diào)節(jié)，即虛鏈路的動態(tài)添加或者移除。文獻(xiàn)[2]基于覆蓋網(wǎng)絡(luò)服務(wù)體系，采取集中式算法，以網(wǎng)絡(luò)帶寬大小作為約束條件，在虛鏈路采用問題上實(shí)現(xiàn)了基于多數(shù)據(jù)流的線性框架的構(gòu)建，其用處是為了在成本最優(yōu)化情況下符合全部終端節(jié)點(diǎn)的流量要求。此框架是針對一組固定網(wǎng)絡(luò)節(jié)點(diǎn)建立的覆蓋網(wǎng)絡(luò)，適合于大規(guī)模覆蓋網(wǎng)絡(luò)應(yīng)用場景。在虛擬計(jì)算應(yīng)用環(huán)境下，文獻(xiàn)[3]提出一種覆蓋網(wǎng)絡(luò)拓?fù)錁?gòu)建算法，該算法基于Kautz圖理論基礎(chǔ)，將流量擁塞情況、網(wǎng)絡(luò)節(jié)點(diǎn)度數(shù)、負(fù)載均衡等考慮到虛鏈路采用問題中，選取分布式算法實(shí)現(xiàn)，從而實(shí)現(xiàn)覆蓋網(wǎng)絡(luò)拓?fù)涞膭討B(tài)調(diào)整與變化。

基于覆蓋網(wǎng)絡(luò)技術(shù)，移動化網(wǎng)格的設(shè)計(jì)與構(gòu)建得以實(shí)現(xiàn)，然而考慮到特定場景的網(wǎng)絡(luò)性質(zhì)，其虛鏈路的采用受到特定因子影響。移動化網(wǎng)格的設(shè)計(jì)原理是將網(wǎng)絡(luò)節(jié)點(diǎn)智能劃分成一般節(jié)點(diǎn)與特殊節(jié)點(diǎn)，通過在特殊節(jié)點(diǎn)之間采用虛鏈路構(gòu)建覆蓋網(wǎng)絡(luò)進(jìn)行分布式資源協(xié)調(diào)。針對由n個特殊節(jié)點(diǎn)組成的覆蓋網(wǎng)絡(luò)，虛鏈路存在條數(shù)理論上等于n(n-1)/2。若覆蓋網(wǎng)絡(luò)拓?fù)溥x用全部連通模式，其任何一個特殊節(jié)點(diǎn)均需對余下所有特殊節(jié)點(diǎn)的狀態(tài)信息進(jìn)行維護(hù)，從而帶給特殊節(jié)點(diǎn)較高的負(fù)載壓力，影響覆蓋網(wǎng)絡(luò)擴(kuò)展性；除此之外，相對一部分覆蓋網(wǎng)絡(luò)節(jié)點(diǎn)之間的直接連通路由成本比間接連通路由成本要高。所以，如何采取符合條件的虛鏈路將對覆蓋網(wǎng)絡(luò)負(fù)載能力與成本費(fèi)用產(chǎn)生較大影響。

1 虛鏈路采用問題模型構(gòu)建

在移動化網(wǎng)格中，覆蓋網(wǎng)絡(luò)需要承擔(dān)任務(wù)配置、資源搜索以及路由轉(zhuǎn)換等作用[4]，所以特殊網(wǎng)絡(luò)節(jié)點(diǎn)之間盡可能采用帶寬流量較高的鏈路。除此之外，覆蓋網(wǎng)絡(luò)中的虛鏈路與實(shí)鏈路是一對多的關(guān)系，一條虛鏈路可能對應(yīng)一條或者多條物理網(wǎng)絡(luò)真實(shí)路徑，一條真實(shí)路徑又對應(yīng)多條實(shí)鏈路，所以實(shí)鏈路很大程度上直接影響虛鏈路的路由維護(hù)成本以及帶寬流量大小。

網(wǎng)絡(luò)中所需維護(hù)的虛鏈路條數(shù)與網(wǎng)絡(luò)性能成正比關(guān)系，虛鏈路條數(shù)越多，其覆蓋網(wǎng)絡(luò)性能越好，然而對應(yīng)的維護(hù)成本越大，所以在覆蓋網(wǎng)絡(luò)作為一個全連通網(wǎng)絡(luò)的前提下，虛鏈路如何采用就需要深入考慮網(wǎng)絡(luò)性能與維護(hù)成本兩個變化因素[5]。虛鏈路采用問題抽象形式化描述如下：

覆蓋網(wǎng)絡(luò)的實(shí)模型使用三元圖GON=(S,L,L’)描述，其中特殊網(wǎng)絡(luò)節(jié)點(diǎn)集合使用S表示，實(shí)鏈路集合由L描述，覆蓋網(wǎng)絡(luò)鏈路使用L’描述。

定義2l’(i,j)→path(i,j)={l1,l2,…,lk}用以描述某一條虛鏈路對應(yīng)的最優(yōu)化實(shí)路徑，其最優(yōu)化即網(wǎng)絡(luò)帶寬最大、延遲最小或者實(shí)鏈路網(wǎng)絡(luò)節(jié)點(diǎn)跳數(shù)最少等多種因子的總體最好狀態(tài)。此最優(yōu)化實(shí)路徑是k條實(shí)鏈路的有序隊(duì)列，其中某一條實(shí)鏈路使用li∈L描述。

定義3b(i,j)用于描述覆蓋網(wǎng)絡(luò)虛鏈路l’(i,j)的帶寬，其大小數(shù)值由l’(i,j)對應(yīng)的實(shí)路徑path(i,j)決定。

覆蓋網(wǎng)絡(luò)必須是一個全連通網(wǎng)絡(luò)，這是虛鏈路采用的一個關(guān)鍵前提，也就是說在覆蓋網(wǎng)絡(luò)中對于任意兩個網(wǎng)絡(luò)節(jié)點(diǎn)si, sj∈S,至少擁有一條網(wǎng)絡(luò)路徑(si, si1, si2,…, sik, sj), si, si1, si2,…, sik, sj∈S且互不相同，使得

在覆蓋網(wǎng)絡(luò)的全連通性得到保證的情況下，其虛鏈路采用問題則是盡量采用高帶寬虛鏈路，并讓網(wǎng)絡(luò)鏈路總體維護(hù)成本最小，即如下

(1)

(2)

(3)

x(i,j)={0,1}

(4)

2 多目標(biāo)免疫克隆算法P-IC

虛鏈路采用問題是一個多目標(biāo)約束優(yōu)化問題[6]，其問題時間復(fù)雜度與覆蓋網(wǎng)絡(luò)規(guī)模大小成正比關(guān)系。此處使用免疫克隆算法，引入人工免疫系統(tǒng)中克隆、變異以及選擇等處理機(jī)制解決虛鏈路采用問題[7]。

2.1 約束處理機(jī)制

(5)

其中，x=[x(i,j)]n×n∈X∈[0,1]n×n，X表示一個n×n維決策空間，x(i,j)用以描述覆蓋網(wǎng)絡(luò)核心網(wǎng)絡(luò)節(jié)點(diǎn)si與sj之間的虛鏈路是否被采用。

2.2 抗體編碼分析

2.3 抗體群操作處理

(6)

(7)

(8)

通過克隆、基因重組處理之后，抗體種群轉(zhuǎn)換成

(9)

(10)

基因變異處理采取自適應(yīng)方式[10]，也就是在單一抗體外圍生成一個變異的解群體，采用局部搜索使得抗體與抗原的親和度盡可能得到提高。自適應(yīng)方式的基因變異將解質(zhì)量的好壞與查找區(qū)域互相關(guān)聯(lián)，從而讓自適應(yīng)數(shù)值較大的抗體在較小區(qū)域內(nèi)查找，反之自適應(yīng)數(shù)值較小的抗體在較大區(qū)域內(nèi)查找。

(11)

(12)

其中，rnd(2)表示隨機(jī)發(fā)生器生成的整數(shù)模2所獲取的結(jié)果，T是基因變異溫度，另外Δ(x,y)描述如下

Δ(x,y)=y(1-rxλ)

(13)

(14)

多目標(biāo)免疫克隆P-IC算法描述如下：

Algorithm P-IC( )

Input: Physical network topology and bandwidth parameters of super nodes

Output: Virtual links between super nodes and bandwidth

Step1: Set algorithm ternination condition;

Set the size of antibody population;

Initialize evolution algebra k=1;

Max iterations is Kmax=100;

Randornly generate initial antibody popution

Step2: Use clone perator on antibody population Bk

Step5: Let k=k+1, if k=Kmax, stop iteration, output Bk+1;

else return Step2

End

2.4 算法復(fù)雜度分析

考慮到N、Nnon與m是同階，因此P-IC算法的時間復(fù)雜度下限最差是O(m2)。

3 仿真測試與結(jié)果分析

本文驗(yàn)證實(shí)驗(yàn)在Waxmax算法基礎(chǔ)上，使用Brite工具構(gòu)造一個覆蓋網(wǎng)絡(luò)拓?fù)鋱D，模擬實(shí)際覆蓋網(wǎng)絡(luò)特性。假定特殊網(wǎng)絡(luò)節(jié)點(diǎn)有10個，任意一個網(wǎng)絡(luò)節(jié)點(diǎn)平均度數(shù)d=4,α=0.15，β=0.2。網(wǎng)絡(luò)鏈路帶寬使用邊權(quán)值eb∈[5,100]表示；網(wǎng)絡(luò)鏈路的維護(hù)成本使用ec∈[10,50]表示；對于10個特殊網(wǎng)絡(luò)節(jié)點(diǎn)搭建的全連通圖的每條邊(虛鏈路)依次從1到45按序編號。

依據(jù)多目標(biāo)免疫克隆P-IC算法，抗體群規(guī)模大小原始值是10；抗體編碼長度是45；假定正常的nc數(shù)值，讓克隆處理之后的抗體群規(guī)模大小N保持在30上下；單個抗體基因變異概率是一半，即1/2；P-IC算法的最大進(jìn)化代數(shù)是100，不同處理類別實(shí)驗(yàn)?zāi)M20次為一個周期，選取平均值作為最終結(jié)果。

虛鏈路最小帶寬的優(yōu)化情況如圖1所示。其中橫坐標(biāo)代表進(jìn)化代數(shù)，縱坐標(biāo)表示虛鏈路最小帶寬，每個黑圓點(diǎn)的分布位置表示某一代進(jìn)化過程中某一個粒子所采用的虛鏈路中最小帶寬?？芍谧钤忌傻牧Ｗ又?，最小帶寬大小在5到20范圍內(nèi)，在進(jìn)化過程中，P-IC算法會采用越來越高帶寬的網(wǎng)絡(luò)鏈路，在60到70代之間大概能趨于優(yōu)化目標(biāo)，其虛鏈路最小帶寬無限趨向于35。

圖1 虛鏈路最小帶寬的優(yōu)化情況

圖2 虛鏈路總體維護(hù)成本的優(yōu)化情況

虛鏈路維護(hù)成本的優(yōu)化情況如圖2所示。盡管部分粒子在原始階段有較低的維護(hù)成本，然而結(jié)合圖1可知，對應(yīng)當(dāng)時的虛鏈路帶寬也不高，并且采用的虛鏈路并不能保證覆蓋網(wǎng)絡(luò)的全連通性。隨著進(jìn)化過程，全部粒子對應(yīng)解的維護(hù)成本將趨向正常化。

虛鏈路采用問題獲取的帕累托最優(yōu)解集如圖3所示。在獲取的3個最優(yōu)解中，依據(jù)對約束條件的轉(zhuǎn)換，其中連通性是1的解說明是不連通的，所以定義為不可行解。剩下兩個解則是可行解，覆蓋網(wǎng)絡(luò)虛鏈路可從中采用一個即可。

圖3 虛鏈路采用問題獲取的帕累托最優(yōu)解集

4 結(jié)束語

虛鏈路采用問題是構(gòu)建覆蓋網(wǎng)絡(luò)的重點(diǎn)問題之一，由于覆蓋網(wǎng)絡(luò)類型的多樣性，虛鏈路采用過程中需要考慮的實(shí)現(xiàn)算法、參數(shù)因子以及網(wǎng)絡(luò)拓?fù)涮卣鞲鞑幌嗤?。對于移動化網(wǎng)格覆蓋網(wǎng)絡(luò)的構(gòu)建而言，是在一組固定的覆蓋網(wǎng)絡(luò)節(jié)點(diǎn)之間采用部分虛鏈路，并綜合考慮了虛鏈路的帶寬大小、網(wǎng)絡(luò)連通性、實(shí)際鏈路帶寬大小以及維護(hù)成本等因子。此處將虛鏈路采用問題抽象表述成約束條件下的多目標(biāo)優(yōu)化問題，在求解中，通過對約束條件進(jìn)行轉(zhuǎn)換，變成優(yōu)化目標(biāo)，并提出一種P-IC算法，以此進(jìn)行求解。考慮到優(yōu)化問題的求解手段不一，最優(yōu)求解方法有待于進(jìn)一步研究分析[10]。

參考文獻(xiàn)：

[1]Yin Xunrui,Wang Yan.Min-cost multicast networks in Euclidean space[C]//Proceedings of the IEEE International Symposium on Information Theory-ISIT,2012:1316-1320.

[2]ZHANG Xiangrong,HOU Limin,LI Yangyang,et al.SAR feature extraction and recognition based on immune clone Gaussian process hidden variables model[J].Journal of Infrared and Millimeter Wave,2013,32(3):110-116(in Chinese).[張向榮,緱麗敏,李陽陽,等.基于免疫克隆高斯過程隱變量模型的SAR目標(biāo)特征提取與識別[J].紅外與毫米波學(xué)報(bào),2013,32(3):110-116.]

[3]NI Zhiping,YU Ling,QIN Xi.Solution model of TSP problem based on chaotic immune clonal selection algorithm[J].Science and Technology Bulletin, 2016,32(10):93-97(in Chinese).[倪志平,余玲,覃溪.基于混沌免疫克隆選擇算法的TSP問題求解模型[J].科技通報(bào),2016,32(10):93-97.]

[4]Mishra M,Tripathy S,Peri S.SEPastry:Security enhanced pastry[C]//Proceedings of the Second International Confe-rence on Advances in Computing and Information Technology,2012:789-795.

[5]LIU Xiaosheng,LIU Jianping,LIU Bo.Implementation of AFDX virtual link layer based on FPGA[J].Computer Engineering,2012,38(19):233-237(in Chinese).[劉曉勝,劉建平,劉博.基于FPGA的AFDX虛擬鏈路層實(shí)現(xiàn)方法[J].計(jì)算機(jī)工程,2012,38(19):233-237.]

[6]Rong-hua S,Li-cheng J.A novel immune clonal algorithm for MO problems[J].IEEE Transactions on Evolutionary Computation,2012,16(1):35-50.

[7]SHENG Wanxing,ZHANG Bo,DI Hongyu,et al.Application of immune optimization algorithm based on dynamic antibody memory in automatic demand response[J].Journal of China Electromechanical Engineering,2014,34(25):4199-4206(in Chinese).[盛萬興,張波,邸宏宇,等.一種基于動態(tài)抗體記憶庫的免疫優(yōu)化算法在自動需求響應(yīng)中的應(yīng)用[J].中國電機(jī)工程學(xué)報(bào),2014,34(25):4199-4206.]

[8]LIU Cheng,HE Feng,WANG Tong,et al.A routing algorithm for virtual link of AFDX network[J].Electro-Optical and Control,2014,17(12):211-215(in Chinese).[劉成,何鋒,王彤,等.一種AFDX網(wǎng)絡(luò)虛擬鏈路的路由配置算法[J].電光與控制,2014,17(12):211-215.]

[9]QI Yutao,LIU Fang,CHANG Weiyuan,et al.Memetic immune optimization algorithm for solving multi-objective problems[J].Journal of Software,2013,12(7):322-327(in Chinese).[戚玉濤,劉芳,常偉遠(yuǎn),等.求解多目標(biāo)問題的Memetic免疫優(yōu)化算法[J].軟件學(xué)報(bào),2013,12(7):322-327.]

[10]Pallis G.Improving content delivery by exploiting the utility of CDN servers[C]//Proceedings of the 5th International Conference Data Management in Cloud,Grid and P2P Systems,2012:88-99.