基于帕累托效率的高效免疫克隆算法

付凡成

(南昌理工學院 計算機信息工程學院，江西 南昌 330044)

0 引 言

虛鏈路如何被采用一直是構建覆蓋網絡的關鍵難題之一。為了提高物理網絡中相關特征能力，同時也為了滿足上層應用需求，從物理網絡中擇取一部分關鍵節點，基于虛鏈路關聯成一個虛擬的邏輯網絡，這種網絡稱之為覆蓋網絡。覆蓋網絡的形式種類多樣，針對不同類別的覆蓋網絡，其虛鏈路在采用過程中需要關注的因子、網絡拓撲的構造特點以及實現的算法等均不一樣。

在各種點對點網絡中，為了滿足網絡節點的動態添加與刪除，文獻[1]提出分布式算法實現的選取策略，用來建立動態變化的覆蓋網絡拓撲。當對網絡節點進行添加與刪除之后，余下網絡節點會依據分布式算法實現路由指標項的動態調節，即虛鏈路的動態添加或者移除。文獻[2]基于覆蓋網絡服務體系，采取集中式算法，以網絡帶寬大小作為約束條件，在虛鏈路采用問題上實現了基于多數據流的線性框架的構建，其用處是為了在成本最優化情況下符合全部終端節點的流量要求。此框架是針對一組固定網絡節點建立的覆蓋網絡，適合于大規模覆蓋網絡應用場景。在虛擬計算應用環境下，文獻[3]提出一種覆蓋網絡拓撲構建算法，該算法基于Kautz圖理論基礎，將流量擁塞情況、網絡節點度數、負載均衡等考慮到虛鏈路采用問題中，選取分布式算法實現，從而實現覆蓋網絡拓撲的動態調整與變化。

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

1 虛鏈路采用問題模型構建

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

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

覆蓋網絡的實模型使用三元圖GON=(S,L,L’)描述，其中特殊網絡節點集合使用S表示，實鏈路集合由L描述，覆蓋網絡鏈路使用L’描述。

定義2l’(i,j)→path(i,j)={l1,l2,…,lk}用以描述某一條虛鏈路對應的最優化實路徑，其最優化即網絡帶寬最大、延遲最小或者實鏈路網絡節點跳數最少等多種因子的總體最好狀態。此最優化實路徑是k條實鏈路的有序隊列，其中某一條實鏈路使用li∈L描述。

定義3b(i,j)用于描述覆蓋網絡虛鏈路l’(i,j)的帶寬，其大小數值由l’(i,j)對應的實路徑path(i,j)決定。

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

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

(1)

(2)

(3)

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

(4)

2 多目標免疫克隆算法P-IC

虛鏈路采用問題是一個多目標約束優化問題[6]，其問題時間復雜度與覆蓋網絡規模大小成正比關系。此處使用免疫克隆算法，引入人工免疫系統中克隆、變異以及選擇等處理機制解決虛鏈路采用問題[7]。

2.1 約束處理機制

(5)

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

2.2 抗體編碼分析

2.3 抗體群操作處理

(6)

(7)

(8)

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

(9)

(10)

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

(11)

(12)

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

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

(13)

(14)

多目標免疫克隆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 算法復雜度分析

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

3 仿真測試與結果分析

本文驗證實驗在Waxmax算法基礎上，使用Brite工具構造一個覆蓋網絡拓撲圖，模擬實際覆蓋網絡特性。假定特殊網絡節點有10個，任意一個網絡節點平均度數d=4,α=0.15，β=0.2。網絡鏈路帶寬使用邊權值eb∈[5,100]表示；網絡鏈路的維護成本使用ec∈[10,50]表示；對于10個特殊網絡節點搭建的全連通圖的每條邊(虛鏈路)依次從1到45按序編號。

依據多目標免疫克隆P-IC算法，抗體群規模大小原始值是10；抗體編碼長度是45；假定正常的nc數值，讓克隆處理之后的抗體群規模大小N保持在30上下；單個抗體基因變異概率是一半，即1/2；P-IC算法的最大進化代數是100，不同處理類別實驗模擬20次為一個周期，選取平均值作為最終結果。

虛鏈路最小帶寬的優化情況如圖1所示。其中橫坐標代表進化代數，縱坐標表示虛鏈路最小帶寬，每個黑圓點的分布位置表示某一代進化過程中某一個粒子所采用的虛鏈路中最小帶寬。可知，在最原始生成的粒子中，最小帶寬大小在5到20范圍內，在進化過程中，P-IC算法會采用越來越高帶寬的網絡鏈路，在60到70代之間大概能趨于優化目標，其虛鏈路最小帶寬無限趨向于35。

圖1 虛鏈路最小帶寬的優化情況

圖2 虛鏈路總體維護成本的優化情況

虛鏈路維護成本的優化情況如圖2所示。盡管部分粒子在原始階段有較低的維護成本，然而結合圖1可知，對應當時的虛鏈路帶寬也不高，并且采用的虛鏈路并不能保證覆蓋網絡的全連通性。隨著進化過程，全部粒子對應解的維護成本將趨向正常化。

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

圖3 虛鏈路采用問題獲取的帕累托最優解集

4 結束語

虛鏈路采用問題是構建覆蓋網絡的重點問題之一，由于覆蓋網絡類型的多樣性，虛鏈路采用過程中需要考慮的實現算法、參數因子以及網絡拓撲特征各不相同。對于移動化網格覆蓋網絡的構建而言，是在一組固定的覆蓋網絡節點之間采用部分虛鏈路，并綜合考慮了虛鏈路的帶寬大小、網絡連通性、實際鏈路帶寬大小以及維護成本等因子。此處將虛鏈路采用問題抽象表述成約束條件下的多目標優化問題，在求解中，通過對約束條件進行轉換，變成優化目標，并提出一種P-IC算法，以此進行求解。考慮到優化問題的求解手段不一，最優求解方法有待于進一步研究分析[10]。

參考文獻：

[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目標特征提取與識別[J].紅外與毫米波學報,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].科技通報,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虛擬鏈路層實現方法[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).[盛萬興,張波,邸宏宇,等.一種基于動態抗體記憶庫的免疫優化算法在自動需求響應中的應用[J].中國電機工程學報,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網絡虛擬鏈路的路由配置算法[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).[戚玉濤,劉芳,常偉遠,等.求解多目標問題的Memetic免疫優化算法[J].軟件學報,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.