胡 穎，莊 雷

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

改進(jìn)的粒子群算法在虛擬網(wǎng)映射中的應(yīng)用*

胡 穎，莊 雷

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

應(yīng)用粒子群算法解決虛擬網(wǎng)映射問(wèn)題，可以大大減少網(wǎng)絡(luò)資源的消耗，卻也容易出現(xiàn)早熟的現(xiàn)象。通過(guò)增加隨機(jī)因素、沿原方向飛行操作和改變?cè)瓪v史因素對(duì)搜索過(guò)程的指導(dǎo)等方式，既保留了歷史因素對(duì)搜索的指導(dǎo)，又在此基礎(chǔ)上加大了搜索范圍，一定程度上減少了早熟收斂帶來(lái)的問(wèn)題。最終實(shí)驗(yàn)結(jié)果表明，改進(jìn)的粒子群算法能夠應(yīng)用于虛擬網(wǎng)映射，和原粒子群算法相比，能夠更有效減少資源消耗。

虛擬網(wǎng)映射；早熟收斂；粒子群算法

1 引言

虛擬網(wǎng)是公認(rèn)解決網(wǎng)絡(luò)僵化問(wèn)題的較有前途的體系結(jié)構(gòu)[1～5]。在虛擬網(wǎng)中較有挑戰(zhàn)性的操作便是虛擬網(wǎng)映射操作，即如何將虛擬網(wǎng)絡(luò)需求映射到物理網(wǎng)絡(luò)上。

粒子群算法是一種仿生隨機(jī)搜索算法[6]，其特點(diǎn)是使用一種群體搜索機(jī)制取代傳統(tǒng)的個(gè)體搜索，算法簡(jiǎn)單，適應(yīng)性廣，是一種非常魯棒的算法，尤其適用于傳統(tǒng)方法難以處理的各種NP完全問(wèn)題或NP難問(wèn)題。在文獻(xiàn)[7]的基礎(chǔ)上，本文針對(duì)早熟收斂問(wèn)題，改進(jìn)粒子群算法在虛擬映射問(wèn)題上的應(yīng)用。

本文的主要貢獻(xiàn)如下：

考慮到原粒子群算法的早熟收斂等問(wèn)題，通過(guò)增加隨機(jī)因素、沿原方向飛行操作和改變?cè)瓪v史因素對(duì)搜索過(guò)程的指導(dǎo)方式等辦法，改進(jìn)粒子群算法在虛擬網(wǎng)映射問(wèn)題的應(yīng)用。

對(duì)在線虛擬請(qǐng)求映射的實(shí)驗(yàn)結(jié)果表明，改進(jìn)的粒子群算法能夠應(yīng)用于虛擬節(jié)點(diǎn)映射，和原粒子群算法相比，能夠有效減少資源消耗。

2 虛擬映射研究概況

虛擬網(wǎng)映射問(wèn)題是NP難問(wèn)題[8]，早期的虛擬映射問(wèn)題解決方案多限制問(wèn)題空間，文獻(xiàn)[9]在離線模式下忽略節(jié)點(diǎn)資源限制，文獻(xiàn)[10]在在線模式下忽略節(jié)點(diǎn)資源限制。不限制問(wèn)題空間的解決方案又可分為一階段映射算法[11,12]、兩階段映射算法[11,13,14]和迭代的映射算法[15,16]。文獻(xiàn)[12]基于子圖匹配，采用回溯方法映射；文獻(xiàn)[11]利用拓?fù)鋵傩赃x節(jié)點(diǎn)，采用基于廣度優(yōu)先順序回溯映射。文獻(xiàn)[13]將映射分為完全獨(dú)立的兩階段，使用多路徑實(shí)現(xiàn)鏈路映射；文獻(xiàn)[14]增加兩個(gè)映射階段的聯(lián)系，利用鏈路需求選擇節(jié)點(diǎn)；文獻(xiàn)[11]利用拓?fù)鋵傩詢?yōu)化節(jié)點(diǎn)的選擇。文獻(xiàn)[15，16]的映射策略包括采用粒子群優(yōu)化和人工魚群的啟發(fā)式算法，都基于隨機(jī)方法和兩階段映射算法。

3 虛擬映射問(wèn)題

(1)底層物理網(wǎng)絡(luò)。使用帶權(quán)值的無(wú)向圖代表底層物理網(wǎng)絡(luò)。其中，無(wú)向圖的點(diǎn)代表物理網(wǎng)絡(luò)節(jié)點(diǎn)，線代表物理鏈路。點(diǎn)有兩個(gè)權(quán)值，分別代表物理節(jié)點(diǎn)的位置和CPU計(jì)算能力。線的權(quán)值代表物理鏈路的帶寬。

(2)虛擬網(wǎng)絡(luò)請(qǐng)求。使用帶權(quán)無(wú)向圖代表虛擬網(wǎng)絡(luò)請(qǐng)求。其中，點(diǎn)代表虛擬節(jié)點(diǎn)，線代表虛擬鏈路。點(diǎn)的兩個(gè)權(quán)值分別代表虛擬節(jié)點(diǎn)可映射域的圓心和虛擬節(jié)點(diǎn)的CPU計(jì)算能力大小，線的權(quán)值代表請(qǐng)求的鏈路帶寬大小。每個(gè)虛擬網(wǎng)請(qǐng)求另有三個(gè)屬性，一個(gè)指定虛擬節(jié)點(diǎn)可映射域的半徑，另兩個(gè)指定虛擬請(qǐng)求的到達(dá)時(shí)間和持續(xù)時(shí)間。

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

(4)虛擬網(wǎng)映射的目標(biāo)。本文的目標(biāo)是使得收益最大化和費(fèi)用最小化。收益最大化是在有限的物理網(wǎng)資源上，映射盡可能多的虛擬網(wǎng)。費(fèi)用最小化是使每個(gè)虛擬請(qǐng)求占用的物理網(wǎng)資源最小化。

費(fèi)用可包括占用的物理節(jié)點(diǎn)資源和物理鏈路資源。對(duì)于確定的虛擬請(qǐng)求，虛擬節(jié)點(diǎn)和物理節(jié)點(diǎn)的映射關(guān)系是一對(duì)一的，于是在映射前，映射占用的物理節(jié)點(diǎn)資源就是確定的。由于虛擬鏈路映射到的物理路徑可長(zhǎng)可短，因此費(fèi)用最小化，主要是指使其占用物理鏈路資源最少。當(dāng)虛擬鏈路的映射策略已定(目前普遍使用k最短路徑算法或多商品流算法)的情況下，如何映射虛擬節(jié)點(diǎn)，使得最終占用的鏈路資源最小，將是虛擬網(wǎng)映射的目標(biāo)。

4 對(duì)虛擬網(wǎng)映射問(wèn)題應(yīng)用粒子群算法的改進(jìn)

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

粒子群算法的優(yōu)點(diǎn)是搜索速度快、效率高、算法簡(jiǎn)單，但由于每次迭代都跟蹤極值，造成處理離散優(yōu)化問(wèn)題時(shí)，容易陷入局部最優(yōu)，即早熟收斂問(wèn)題。要在全局開拓與局部搜索之間平衡，算法既要使用歷史軌跡智能地引導(dǎo)搜索，又要改進(jìn)搜索策略來(lái)加強(qiáng)全局開拓。

4.1 引入優(yōu)勢(shì)群體

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

4.2 引入隨機(jī)調(diào)整因素

原算法使用惰性因子、局部最優(yōu)解和全局最優(yōu)解三個(gè)部分來(lái)確定調(diào)整概率。這樣，只有歷史軌跡和當(dāng)前位置引導(dǎo)粒子變化，使得粒子變化的原因單一，易陷入局部最優(yōu)。于是，引入了隨機(jī)調(diào)整概率。將隨機(jī)生成的一個(gè)隨機(jī)調(diào)整概率與上述歷史因素確定的調(diào)整概率作比較，取較大值作為調(diào)整概率。

4.3 增加隨機(jī)擾動(dòng)

當(dāng)原算法在搜索過(guò)程中一直不能得到更優(yōu)的解時(shí)，就意味著算法搜索過(guò)程結(jié)束。這個(gè)搜索軌跡由歷史因素引導(dǎo)，很容易局部收斂。為了增大對(duì)全局的搜索，就需要增加擾動(dòng)，即將粒子以一定的概率隨機(jī)分配位置，而不總是由歷史因素指導(dǎo)分配。

4.4 粒子保持飛行方向

原算法中，粒子每次變化調(diào)整后，不管調(diào)整結(jié)果是否較好，都不影響下一次的調(diào)整，使得調(diào)整結(jié)果好的變化方向不能得到繼承。因此，這里對(duì)于上次調(diào)整結(jié)果好的粒子繼續(xù)調(diào)整，直到調(diào)整結(jié)果不好，或者對(duì)該粒子連續(xù)調(diào)整的次數(shù)已達(dá)到事先設(shè)定的一個(gè)最大值。

5 改進(jìn)粒子群算法的具體解決方案

5.1 算法思路

和文獻(xiàn)[9]一樣，設(shè)置每個(gè)粒子為一個(gè)向量，每個(gè)分量代表一個(gè)虛擬節(jié)點(diǎn)映射到的物理節(jié)點(diǎn)，那么，對(duì)于某個(gè)虛擬網(wǎng)，虛擬節(jié)點(diǎn)的個(gè)數(shù)就決定了向量的長(zhǎng)度，虛擬節(jié)點(diǎn)的編號(hào)決定了分量的位置，虛擬節(jié)點(diǎn)所映射到的物理節(jié)點(diǎn)序號(hào)決定了分量的值。這樣，每個(gè)粒子就代表了一個(gè)虛擬網(wǎng)節(jié)點(diǎn)映射方案。有歷史因素引導(dǎo)的情況下，是否對(duì)位置向量進(jìn)行調(diào)整，由方向向量決定，方向向量中分量和位置向量的分量是一一對(duì)應(yīng)的，其分量可取值0或1，為1代表對(duì)位置向量的該分量進(jìn)行調(diào)整，為0，不調(diào)整；當(dāng)進(jìn)行擾動(dòng)時(shí)，可以隨機(jī)生成位置向量。

5.2 適應(yīng)度函數(shù)

每次節(jié)點(diǎn)映射的好壞由適應(yīng)度(Fitness Value)函數(shù)衡量，由下式作為適應(yīng)度函數(shù)：

(1)

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

5.3 算法主要流程

基于改進(jìn)的粒子群算法的虛擬網(wǎng)映射算法：

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

(2)根據(jù)方向調(diào)整操作(見(jiàn)5.4節(jié))得到方向向量，根據(jù)方向向量使用位置調(diào)整操作(見(jiàn)5.5節(jié))對(duì)位置向量進(jìn)行調(diào)整，生成一套新的位置向量。

(3)根據(jù)k-最短路徑算法計(jì)算每條虛擬鏈路對(duì)應(yīng)物理節(jié)點(diǎn)對(duì)之間的所有可用最短路徑。若映射物理鏈路成功，轉(zhuǎn)入步驟(4)；如果映射鏈路失敗，且沒(méi)超過(guò)最大回退次數(shù)，轉(zhuǎn)入步驟(2)，如果達(dá)到最大回退次數(shù)，返回鏈路映射失敗。

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

(5)對(duì)適應(yīng)值進(jìn)行評(píng)估，判斷是否小于當(dāng)前的優(yōu)勢(shì)群體的某個(gè)個(gè)體，如果小于且新節(jié)點(diǎn)向量不在優(yōu)勢(shì)群體，則更新當(dāng)前優(yōu)勢(shì)群體。

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

(7)根據(jù)已確定的方向向量，調(diào)用位置調(diào)整操作(見(jiàn)5.5節(jié))，轉(zhuǎn)步驟(8)。

(8)根據(jù)k-最短路徑算法計(jì)算每條虛擬鏈路對(duì)應(yīng)物理節(jié)點(diǎn)對(duì)之間的可用最短路徑。若映射物理鏈路成功，轉(zhuǎn)步驟(4)；如果映射鏈路失敗，且沒(méi)超過(guò)最大回退次數(shù)，轉(zhuǎn)步驟(7)；如果達(dá)到最大回退次數(shù)，轉(zhuǎn)步驟(9)。

(9)z=z+1，判定是否達(dá)到迭代次數(shù)，如果是，轉(zhuǎn)步驟(10)；如果否，轉(zhuǎn)步驟(2)。

(10)q=q+1，判定是否達(dá)到迭代面積，如果是，轉(zhuǎn)步驟(11)；如果否，進(jìn)行位置向量擾動(dòng)操作(見(jiàn)5.6節(jié))，然后轉(zhuǎn)步驟(2)。

(11) 算法結(jié)束。

5.4 方向調(diào)整操作

(2)

5.5 位置調(diào)整操作

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

5.6 位置向量擾動(dòng)操作

按概率Ped擾動(dòng)每個(gè)個(gè)體，即以概率Ped確定是否隨機(jī)產(chǎn)生位置向量(新個(gè)體)。

6 實(shí)驗(yàn)性能分析

6.1 實(shí)驗(yàn)設(shè)置

實(shí)驗(yàn)主機(jī)配置如下：雙處理器Intel(R)Xeon(R)CPU3.07GHz，內(nèi)存(RAM)為12GB，操作系統(tǒng)是MicrosoftWindows7 旗艦版ServicePack1。采用標(biāo)準(zhǔn)C++編程實(shí)現(xiàn)相關(guān)算法。

使用GT-ITM[12]工具生成100個(gè)物理節(jié)點(diǎn)的底層網(wǎng)絡(luò)拓?fù)洌约? 000個(gè)虛擬映射請(qǐng)求。底層網(wǎng)絡(luò)的節(jié)點(diǎn)資源和鏈路資源在[50,100]內(nèi)均勻分布，節(jié)點(diǎn)連接概率是0.5。虛擬映射請(qǐng)求節(jié)點(diǎn)數(shù)在[2,9]均勻分布，節(jié)點(diǎn)和鏈路資源請(qǐng)求在[0,30]均勻分布。虛擬映射請(qǐng)求的到達(dá)過(guò)程服從泊松分布，每個(gè)虛擬映射的生命周期服從指數(shù)分布。

對(duì)粒子參數(shù)的設(shè)置如下：粒子個(gè)數(shù)S為30，迭代次數(shù)Nz為4，沿同方向調(diào)整的最大次數(shù)Ns為3，迭代面積Nq為 4，擾動(dòng)操作概率Ped為0.25，優(yōu)勢(shì)群體個(gè)數(shù)bestnumber為6，學(xué)習(xí)速率α為0.6。

總的迭代次數(shù)是30×4×3=480。

6.2 參與評(píng)價(jià)的指標(biāo)

(1)映射時(shí)間。每個(gè)虛擬請(qǐng)求映射成功需要的時(shí)間。

(2)花費(fèi)。映射成功后，所有虛擬鏈路對(duì)應(yīng)物理鏈路的帶寬和，即：

(3)

其中，u、v是虛擬鏈路兩端點(diǎn)，LEN(u,v)為映射的物理鏈路長(zhǎng)度，BW(u,v)為虛擬鏈路請(qǐng)求帶寬。如前所述，耗費(fèi)鏈路資源越少，虛擬請(qǐng)求的花費(fèi)越少，相應(yīng)的映射算法性能越優(yōu)。

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

(4)

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

那么收益花費(fèi)比表示為：

ratio=Revenue/Cost

(5)

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

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

6.3 性能分析

由于本文是對(duì)文獻(xiàn)[9]所采用的粒子群算法的改進(jìn)，因此這里主要和文獻(xiàn)[9]的算法做對(duì)比；為了說(shuō)明采用粒子群算法的必要性，還與文獻(xiàn)[14]的最大匹配算法進(jìn)行了實(shí)驗(yàn)對(duì)比。

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

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

虛擬請(qǐng)求的花費(fèi)情況見(jiàn)圖1和圖2，其中，圖1是每100個(gè)虛擬請(qǐng)求映射成功的資源平均花費(fèi)。圖1中，縱軸是取得的花費(fèi)的平均值，橫軸是被取平均值的100個(gè)虛擬請(qǐng)求，那么，每個(gè)點(diǎn)代表對(duì)縱軸所指定的這100個(gè)請(qǐng)求取得的平均花費(fèi)值。圖2是各個(gè)虛擬請(qǐng)求的收益花費(fèi)比。其中，縱軸為收益花費(fèi)比值，橫軸指定各個(gè)虛擬請(qǐng)求ID，每個(gè)點(diǎn)代表一個(gè)虛擬映射請(qǐng)求的收益花費(fèi)比。從圖1和圖2可以看出，改進(jìn)的粒子群算法在耗費(fèi)資源方面，映射效果最優(yōu)。

Figure 1 Average cost of every hundred virtual network requests圖1 每100個(gè)虛擬請(qǐng)求的平均花費(fèi)

Figure 2 Income cost ratio of eachvirtual network request圖2 各個(gè)虛擬請(qǐng)求的收益花費(fèi)比

改進(jìn)的粒子群算法和粒子群算法的各個(gè)虛擬請(qǐng)求的映射時(shí)間如圖3所示。圖3中，橫軸為各個(gè)虛擬請(qǐng)求ID，縱軸為映射時(shí)間值(單位為ms)，那么每個(gè)點(diǎn)代表一個(gè)虛擬請(qǐng)求的映射時(shí)間。

表1是各算法對(duì)2 000個(gè)請(qǐng)求的平均映射時(shí)間。從表1中可以看出，相對(duì)于最大匹配算法，改進(jìn)的粒子群算法和粒子群算法耗費(fèi)的時(shí)間較長(zhǎng)。

Figure 3 Mapping time of each virtual network request圖3 各個(gè)虛擬請(qǐng)求映射時(shí)間

粒子群改進(jìn)的粒子群最大匹配平均映射時(shí)間/s23.43335.0090.054

從上述實(shí)驗(yàn)數(shù)據(jù)可以看出，采用改進(jìn)粒子群算法可提高映射質(zhì)量，花費(fèi)時(shí)間較長(zhǎng)，但從長(zhǎng)遠(yuǎn)考慮，應(yīng)用改進(jìn)粒子群算法是有意義的。

7 結(jié)束語(yǔ)

本文確定映射目標(biāo)為減少占用資源。在實(shí)際應(yīng)用中，目標(biāo)還可能是使得負(fù)載更加均衡；或者面對(duì)災(zāi)難或者突發(fā)流量網(wǎng)絡(luò)更健壯；或者面對(duì)攻擊網(wǎng)絡(luò)更安全等等。因此，應(yīng)從多個(gè)角度完善虛擬網(wǎng)映射，使網(wǎng)絡(luò)虛擬化更好地應(yīng)用到下一代網(wǎng)絡(luò)。

[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.

附中文參考文獻(xiàn)：

[16] 朱強(qiáng), 王慧強(qiáng), 呂宏武, 等. VNE-AFS:基于人工魚群的網(wǎng)絡(luò)虛擬化映射算法[J]. 通信學(xué)報(bào), 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

國(guó)家973計(jì)劃資助項(xiàng)目(2012CB315901)

TP393.01

：A

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

胡穎(1982),女,河南虞城人，博士生，講師，CCF會(huì)員(E200041081G)，研究方向?yàn)樘摂M網(wǎng)映射。E-mail:3878105@qq.com

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

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