改進的粒子群算法在虛擬網映射中的應用*

胡 穎，莊 雷

(鄭州大學信息工程學院，河南 鄭州 450000)

改進的粒子群算法在虛擬網映射中的應用*

胡 穎，莊 雷

(鄭州大學信息工程學院，河南 鄭州 450000)

應用粒子群算法解決虛擬網映射問題，可以大大減少網絡資源的消耗，卻也容易出現早熟的現象。通過增加隨機因素、沿原方向飛行操作和改變原歷史因素對搜索過程的指導等方式，既保留了歷史因素對搜索的指導，又在此基礎上加大了搜索范圍，一定程度上減少了早熟收斂帶來的問題。最終實驗結果表明，改進的粒子群算法能夠應用于虛擬網映射，和原粒子群算法相比，能夠更有效減少資源消耗。

虛擬網映射；早熟收斂；粒子群算法

1 引言

虛擬網是公認解決網絡僵化問題的較有前途的體系結構[1～5]。在虛擬網中較有挑戰性的操作便是虛擬網映射操作，即如何將虛擬網絡需求映射到物理網絡上。

粒子群算法是一種仿生隨機搜索算法[6]，其特點是使用一種群體搜索機制取代傳統的個體搜索，算法簡單，適應性廣，是一種非常魯棒的算法，尤其適用于傳統方法難以處理的各種NP完全問題或NP難問題。在文獻[7]的基礎上，本文針對早熟收斂問題，改進粒子群算法在虛擬映射問題上的應用。

本文的主要貢獻如下：

考慮到原粒子群算法的早熟收斂等問題，通過增加隨機因素、沿原方向飛行操作和改變原歷史因素對搜索過程的指導方式等辦法，改進粒子群算法在虛擬網映射問題的應用。

對在線虛擬請求映射的實驗結果表明，改進的粒子群算法能夠應用于虛擬節點映射，和原粒子群算法相比，能夠有效減少資源消耗。

2 虛擬映射研究概況

虛擬網映射問題是NP難問題[8]，早期的虛擬映射問題解決方案多限制問題空間，文獻[9]在離線模式下忽略節點資源限制，文獻[10]在在線模式下忽略節點資源限制。不限制問題空間的解決方案又可分為一階段映射算法[11,12]、兩階段映射算法[11,13,14]和迭代的映射算法[15,16]。文獻[12]基于子圖匹配，采用回溯方法映射；文獻[11]利用拓撲屬性選節點，采用基于廣度優先順序回溯映射。文獻[13]將映射分為完全獨立的兩階段，使用多路徑實現鏈路映射；文獻[14]增加兩個映射階段的聯系，利用鏈路需求選擇節點；文獻[11]利用拓撲屬性優化節點的選擇。文獻[15，16]的映射策略包括采用粒子群優化和人工魚群的啟發式算法，都基于隨機方法和兩階段映射算法。

3 虛擬映射問題

(1)底層物理網絡。使用帶權值的無向圖代表底層物理網絡。其中，無向圖的點代表物理網絡節點，線代表物理鏈路。點有兩個權值，分別代表物理節點的位置和CPU計算能力。線的權值代表物理鏈路的帶寬。

(2)虛擬網絡請求。使用帶權無向圖代表虛擬網絡請求。其中，點代表虛擬節點，線代表虛擬鏈路。點的兩個權值分別代表虛擬節點可映射域的圓心和虛擬節點的CPU計算能力大小，線的權值代表請求的鏈路帶寬大小。每個虛擬網請求另有三個屬性，一個指定虛擬節點可映射域的半徑，另兩個指定虛擬請求的到達時間和持續時間。

(3)虛擬網映射問題。虛擬網映射問題是指由物理網滿足虛擬網需求。其中，一個虛擬節點只能映射到一個物理節點上，一個物理節點也只能承載該虛擬請求的一個虛擬節點，而一個物理節點可以承載多個虛擬請求的節點映射；物理節點映射應滿足位置和CPU資源約束。在虛擬鏈路的兩個虛擬端點已映射至物理網絡后，在確定的兩個物理節點間確定一條物理路徑，該路徑上的任一條鏈路都應滿足虛擬鏈路的帶寬需求。

(4)虛擬網映射的目標。本文的目標是使得收益最大化和費用最小化。收益最大化是在有限的物理網資源上，映射盡可能多的虛擬網。費用最小化是使每個虛擬請求占用的物理網資源最小化。

費用可包括占用的物理節點資源和物理鏈路資源。對于確定的虛擬請求，虛擬節點和物理節點的映射關系是一對一的，于是在映射前，映射占用的物理節點資源就是確定的。由于虛擬鏈路映射到的物理路徑可長可短，因此費用最小化，主要是指使其占用物理鏈路資源最少。當虛擬鏈路的映射策略已定(目前普遍使用k最短路徑算法或多商品流算法)的情況下，如何映射虛擬節點，使得最終占用的鏈路資源最小，將是虛擬網映射的目標。

4 對虛擬網映射問題應用粒子群算法的改進

文獻[9]采用的粒子群算法(本節中簡稱原算法)是一種智能的隨機搜索算法，它初始化為一群隨機解，然后通過迭代尋找最優解。在每一次迭代中，粒子通過跟蹤兩個極值來更新自己，一個是粒子本身找到的最優解，即個體極值；一個是整個種群目前找到的最優解，即全局極值。

粒子群算法的優點是搜索速度快、效率高、算法簡單，但由于每次迭代都跟蹤極值，造成處理離散優化問題時，容易陷入局部最優，即早熟收斂問題。要在全局開拓與局部搜索之間平衡，算法既要使用歷史軌跡智能地引導搜索，又要改進搜索策略來加強全局開拓。

4.1 引入優勢群體

原算法為每一個粒子設置歷史最優解，每個粒子的變化將參考該粒子的歷史最優解，這樣，加強了局部搜索，提高了局部收斂速度，但是也使得搜索易于陷入局部最優解。為了加強全局開拓和提高全局收斂速度，原算法為全部粒子設置了一個全局最優解，使每個粒子變化時都會參考全局最優解。隨著粒子群體不斷進化，粒子群體逐漸向群體最優點聚集，隨著聚集程度越來越強，粒子群算法的多樣性就會降低，粒子群算法的全局開拓能力就會減弱。因此，這里將取粒子群飛行軌跡的多個最優值，即優勢群體，來引導每個粒子的飛行趨向。

4.2 引入隨機調整因素

原算法使用惰性因子、局部最優解和全局最優解三個部分來確定調整概率。這樣，只有歷史軌跡和當前位置引導粒子變化，使得粒子變化的原因單一，易陷入局部最優。于是，引入了隨機調整概率。將隨機生成的一個隨機調整概率與上述歷史因素確定的調整概率作比較，取較大值作為調整概率。

4.3 增加隨機擾動

當原算法在搜索過程中一直不能得到更優的解時，就意味著算法搜索過程結束。這個搜索軌跡由歷史因素引導，很容易局部收斂。為了增大對全局的搜索，就需要增加擾動，即將粒子以一定的概率隨機分配位置，而不總是由歷史因素指導分配。

4.4 粒子保持飛行方向

原算法中，粒子每次變化調整后，不管調整結果是否較好，都不影響下一次的調整，使得調整結果好的變化方向不能得到繼承。因此，這里對于上次調整結果好的粒子繼續調整，直到調整結果不好，或者對該粒子連續調整的次數已達到事先設定的一個最大值。

5 改進粒子群算法的具體解決方案

5.1 算法思路

和文獻[9]一樣，設置每個粒子為一個向量，每個分量代表一個虛擬節點映射到的物理節點，那么，對于某個虛擬網，虛擬節點的個數就決定了向量的長度，虛擬節點的編號決定了分量的位置，虛擬節點所映射到的物理節點序號決定了分量的值。這樣，每個粒子就代表了一個虛擬網節點映射方案。有歷史因素引導的情況下，是否對位置向量進行調整，由方向向量決定，方向向量中分量和位置向量的分量是一一對應的，其分量可取值0或1，為1代表對位置向量的該分量進行調整，為0，不調整；當進行擾動時，可以隨機生成位置向量。

5.2 適應度函數

每次節點映射的好壞由適應度(Fitness Value)函數衡量，由下式作為適應度函數：

(1)

即由節點映射方案所得到的鏈路映射結果決定適應度的值。其中，LEN(u,v)是指虛擬鏈路(u,v)所映射的物理路徑長度(跳數)；BW(u,v)是指虛擬鏈路的帶寬。

5.3 算法主要流程

基于改進的粒子群算法的虛擬網映射算法：

(1)初始化位置向量及其它變量，迭代次數z=0，迭代面積q=0。

(2)根據方向調整操作(見5.4節)得到方向向量，根據方向向量使用位置調整操作(見5.5節)對位置向量進行調整，生成一套新的位置向量。

(3)根據k-最短路徑算法計算每條虛擬鏈路對應物理節點對之間的所有可用最短路徑。若映射物理鏈路成功，轉入步驟(4)；如果映射鏈路失敗，且沒超過最大回退次數，轉入步驟(2)，如果達到最大回退次數，返回鏈路映射失敗。

(4)根據式(1)得到此位置向量下的適應值。

(5)對適應值進行評估，判斷是否小于當前的優勢群體的某個個體，如果小于且新節點向量不在優勢群體，則更新當前優勢群體。

(6)比較新適應值與該粒子的前適應值，若新適應值較低，且在該方向飛行次數小于最大保持方向飛行次數Ns，轉步驟(7)；否則，進入下一次迭代，轉步驟(2)。

(7)根據已確定的方向向量，調用位置調整操作(見5.5節)，轉步驟(8)。

(8)根據k-最短路徑算法計算每條虛擬鏈路對應物理節點對之間的可用最短路徑。若映射物理鏈路成功，轉步驟(4)；如果映射鏈路失敗，且沒超過最大回退次數，轉步驟(7)；如果達到最大回退次數，轉步驟(9)。

(9)z=z+1，判定是否達到迭代次數，如果是，轉步驟(10)；如果否，轉步驟(2)。

(10)q=q+1，判定是否達到迭代面積，如果是，轉步驟(11)；如果否，進行位置向量擾動操作(見5.6節)，然后轉步驟(2)。

(11) 算法結束。

5.4 方向調整操作

(2)

5.5 位置調整操作

位置調整操作是指重新確定粒子i的位置，即對于位置向量的各分量j(對應虛擬節點j)，重新選擇要映射到的物理節點。這里仍采用文獻[9]選擇物理節點的原則，使可用資源較多的物理節點被選中的概率較大。

5.6 位置向量擾動操作

按概率Ped擾動每個個體，即以概率Ped確定是否隨機產生位置向量(新個體)。

6 實驗性能分析

6.1 實驗設置

實驗主機配置如下：雙處理器Intel(R)Xeon(R)CPU3.07GHz，內存(RAM)為12GB，操作系統是MicrosoftWindows7 旗艦版ServicePack1。采用標準C++編程實現相關算法。

使用GT-ITM[12]工具生成100個物理節點的底層網絡拓撲，以及2 000個虛擬映射請求。底層網絡的節點資源和鏈路資源在[50,100]內均勻分布，節點連接概率是0.5。虛擬映射請求節點數在[2,9]均勻分布，節點和鏈路資源請求在[0,30]均勻分布。虛擬映射請求的到達過程服從泊松分布，每個虛擬映射的生命周期服從指數分布。

對粒子參數的設置如下：粒子個數S為30，迭代次數Nz為4，沿同方向調整的最大次數Ns為3，迭代面積Nq為 4，擾動操作概率Ped為0.25，優勢群體個數bestnumber為6，學習速率α為0.6。

總的迭代次數是30×4×3=480。

6.2 參與評價的指標

(1)映射時間。每個虛擬請求映射成功需要的時間。

(2)花費。映射成功后，所有虛擬鏈路對應物理鏈路的帶寬和，即：

(3)

其中，u、v是虛擬鏈路兩端點，LEN(u,v)為映射的物理鏈路長度，BW(u,v)為虛擬鏈路請求帶寬。如前所述，耗費鏈路資源越少，虛擬請求的花費越少，相應的映射算法性能越優。

(3)收益花費比。收益指虛擬請求的資源需求，由兩部分組成。節點資源映射前后沒有變化(同一虛擬請求中的虛擬節點可以且只可以映射到一個物理節點)，這里只取鏈路資源部分：

(4)

其中，Lv是虛擬鏈路，BW(Lv)是Lv的帶寬需求。

那么收益花費比表示為：

ratio=Revenue/Cost

(5)

式(5)中，分子的值是確定的，分母部分是不確定的，花費越少，其值越小，收益花費比越大，相應的映射算法性能越優。由式(3)和式(4)可以看出，收益花費比的最大值為1。

(4)請求接受率。虛擬請求映射成功與否的情況。

6.3 性能分析

由于本文是對文獻[9]所采用的粒子群算法的改進，因此這里主要和文獻[9]的算法做對比；為了說明采用粒子群算法的必要性，還與文獻[14]的最大匹配算法進行了實驗對比。

粒子群算法的參數設置與文獻[9]保持一致，取迭代次數為100，粒子群個體數為5，那么總的迭代次數為500，與改進粒子群算法的迭代次數(480)近似。最大匹配算法是在每個維度(每個虛擬節點)上所有可用物理節點集合中，選取剩余資源最多的節點作為映射節點。

在線運行了2 000個虛擬映射請求，三個算法全部接受，說明請求接受率還是較高的。然而，在實際運行環境下，隨著請求的增加，有限的資源不一定能夠滿足所有請求。由于粒子群算法和改進的粒子群算法在解空間進行了大量的搜索工作，因此最終找到解的概率應是較大的。又由于改進的粒子群算法比原粒子群算法搜索廣度上更大，因此找到解的概率應是最大的。

虛擬請求的花費情況見圖1和圖2，其中，圖1是每100個虛擬請求映射成功的資源平均花費。圖1中，縱軸是取得的花費的平均值，橫軸是被取平均值的100個虛擬請求，那么，每個點代表對縱軸所指定的這100個請求取得的平均花費值。圖2是各個虛擬請求的收益花費比。其中，縱軸為收益花費比值，橫軸指定各個虛擬請求ID，每個點代表一個虛擬映射請求的收益花費比。從圖1和圖2可以看出，改進的粒子群算法在耗費資源方面，映射效果最優。

Figure 1 Average cost of every hundred virtual network requests圖1 每100個虛擬請求的平均花費

Figure 2 Income cost ratio of eachvirtual network request圖2 各個虛擬請求的收益花費比

改進的粒子群算法和粒子群算法的各個虛擬請求的映射時間如圖3所示。圖3中，橫軸為各個虛擬請求ID，縱軸為映射時間值(單位為ms)，那么每個點代表一個虛擬請求的映射時間。

表1是各算法對2 000個請求的平均映射時間。從表1中可以看出，相對于最大匹配算法，改進的粒子群算法和粒子群算法耗費的時間較長。

Figure 3 Mapping time of each virtual network request圖3 各個虛擬請求映射時間

粒子群改進的粒子群最大匹配平均映射時間/s23.43335.0090.054

從上述實驗數據可以看出，采用改進粒子群算法可提高映射質量，花費時間較長，但從長遠考慮，應用改進粒子群算法是有意義的。

7 結束語

本文確定映射目標為減少占用資源。在實際應用中，目標還可能是使得負載更加均衡；或者面對災難或者突發流量網絡更健壯；或者面對攻擊網絡更安全等等。因此，應從多個角度完善虛擬網映射，使網絡虛擬化更好地應用到下一代網絡。

[1] Shenker S, Peterson L, Turner J. Overcoming the Internet impasse through virtualization[C]∥Proc of the 3rd ACM Workshop on Hot Topics in Networks, 2004:34-41.

[2] Turner J,Taylor D. Diversifying the Internet[C]∥Proc of IEEE GLOBECOM’05, 2005:755-760.

[3] Anderson T, Peterson L, Shenker S, et al. Overcoming the Internet impasse through virtualization[J]. IEEE Computer, 2005,38(4):34-41.

[4] Feamster N, Gao L, Rexford J. How to lease the Internet in your spare time[J]. ACM SIGCOMM Computer Communications Review, 2007,37(1):61-64.

[5] Chowdhury N K, Boutaba R. Network virtualization:State of the art and research challenges[J]. IEEE Communications Magazine, 2009, 47(7):20-26.

[6] Andersen D G. Theoretical approaches to node assignment[Z].Pittsburgh:Carnegie Mellon University, 2002.

[7] Yu M, Yi Y, Rexford J, et al. Rethinking virtual network embedding:Substrate support for path splitting and migration[J]. ACM SIGCOMM Computer Communication Review, 2008, 38(2):17-29.

[8] James K,Eberhart R.Particle swarm optimization[C]∥Proc of IEEE International Conference on Neural Networks, 1995:1942-1948.

[9] Cheng X, Su S, Zhang Z, et al. Virtual network embedding through topology awareness and optimization[J]. Computer Networks, 2012, 56(6):1797-1813.

[10] Lu J, Turner J. Efficient mapping of virtual networks onto a shared substrate[R]. Technical Report WUCSE-2006-35. Washington:Washington University, 2006.

[11] Fan J, Ammar M H. Dynamic topology configuration in service overlay networks:A study of reconfiguration policies[C]∥Proc of INFOCOM’06, 2006:1.

[12] Lischka J, Karl H. A virtual network mapping algorithm based on subgraph isomorphism detection[C]∥Proc of the 1st ACM Workshop on Virtualized Infrastructure Systems and Architectures, 2009:81-88.

[13] Cheng X, Su S, Zhang Z, et al. Virtual network embedding through topology-aware node ranking[J]. ACM SIGCOMM Computer Communication Review, 2011, 41(2):38-47.

[14] Chowdhury N M M K, Rahman M R, Boutaba R. Virtual network embedding with coordinated node and link mapping[C]∥Proc of INFOCOM’09, 2009:783-791.

[15] Zhang Z, Cheng X, Su S, et al. A unified enhanced particle swarm optimization-based virtual network embedding algorithm[J]. International Journal of Communication Systems, 2013, 26(8):1054-1073.

[16] Zhu Qiang, Wang Hui-qiang, Lü Hong-wu, et al. VNE-AFS:Virtual network embedding based on artificial fish swarm[J]. Journal on Communications, 2012,33(Z1):170-177.

附中文參考文獻：

[16] 朱強, 王慧強, 呂宏武, 等. VNE-AFS:基于人工魚群的網絡虛擬化映射算法[J]. 通信學報, 2012,33(Z1):170-177.

HUYing,born in 1982,PhD candidate,lecturer,CCF member(E200041081G)，her research interest includes virtual network embedding.

Applyinganimprovedparticleswarmoptimizationalgorithminvirtualnetworkmapping

HU Ying,ZHUANG Lei

(College of Information and Engineering,Zhengzhou University,Zhengzhou 450000,China)

Using the Particle Swarm Optimization (PSO) algorithm to solve the problem of virtual network embedding can reduce the consumption of network resource, but it also brings premature convergence.An improved PSO algorithm is proposed,which adds random factors,operates along the original direction, and changes the introduction of history factors to the search process.The proposal not only keeps the instruction of history factors to the search process but also increases the search range,thus relieving, the premature convergence problems to a certain extent.The experimental results demonstrate that the improved PSO algorithm can be applied to virtual network mapping and effectively reduce resource consumption in comparison with the original PSO algorithm.

virtual network mapping;premature convergence;particle swarm optimization (PSO)

1007-130X(2014)11-2169-05

2014-07-08;

：2014-09-10

國家973計劃資助項目(2012CB315901)

TP393.01

：A

10.3969/j.issn.1007-130X.2014.11.020

胡穎(1982),女,河南虞城人，博士生，講師，CCF會員(E200041081G)，研究方向為虛擬網映射。E-mail:3878105@qq.com

通信地址：450000 河南省鄭州市鄭州大學信息工程學院

Address:College of Information and Engineering,Zhengzhou University,Zhengzhou 450000,Henan,P.R.China