李 貞，鄭向偉，張 輝

(1.山東師范大學(xué) 信息科學(xué)與工程學(xué)院，濟南 250000； 2.山東省分布式計算機軟件新技術(shù)重點實驗室，濟南 250014) (*通信作者電子郵箱xwzhengcn@163.com)

基于多目標(biāo)粒子群優(yōu)化的虛擬網(wǎng)絡(luò)映射算法

李 貞1,2，鄭向偉1,2*，張 輝1,2

(1.山東師范大學(xué) 信息科學(xué)與工程學(xué)院，濟南 250000； 2.山東省分布式計算機軟件新技術(shù)重點實驗室，濟南 250014) (*通信作者電子郵箱xwzhengcn@163.com)

在虛擬網(wǎng)絡(luò)映射中，多數(shù)研究只考慮一個映射目標(biāo)，不能體現(xiàn)多方的利益。為此，將多目標(biāo)算法和粒子群算法結(jié)合，提出了一種基于多目標(biāo)粒子群優(yōu)化(PSO)的虛擬網(wǎng)絡(luò)映射算法(VNE-MOPSO)。首先，在基本的粒子群算法中引入交叉算子，擴大了種群優(yōu)化的搜索空間；其次，在多目標(biāo)優(yōu)化算法中引入非支配排序、擁擠距離排序，從而加快種群的收斂；最后，以同時最小化成本和節(jié)點負載均衡度為虛擬網(wǎng)絡(luò)映射目標(biāo)函數(shù)，采用多目標(biāo)粒子群優(yōu)化算法求解虛擬網(wǎng)絡(luò)映射問題(VNMP)。實驗結(jié)果表明，采用該算法求解虛擬網(wǎng)絡(luò)映射問題，在網(wǎng)絡(luò)請求接受率、平均成本、平均節(jié)點負載均衡度、基礎(chǔ)設(shè)施提供商的收益等方面具有優(yōu)勢。

虛擬網(wǎng)絡(luò)映射；多目標(biāo)優(yōu)化算法；粒子群優(yōu)化算法；非支配排序；擁擠距離排序；交叉算子

0 引言

互聯(lián)網(wǎng)以其通用性和方便性等特征吸引越來越多用戶的同時，使得用戶呈現(xiàn)出爆炸式增長的趨勢，最終互聯(lián)網(wǎng)的僵化現(xiàn)象日趨嚴重[1]。為使用戶方便快捷地使用網(wǎng)絡(luò)信息資源，網(wǎng)絡(luò)虛擬化[2]技術(shù)應(yīng)運而生，網(wǎng)絡(luò)虛擬化技術(shù)主動適應(yīng)新型網(wǎng)絡(luò)架構(gòu)，其方便性體現(xiàn)在將多個虛擬網(wǎng)絡(luò)請求映射到有限的共享物理網(wǎng)絡(luò)之上，從而滿足用戶的多樣化需求。其中虛擬網(wǎng)絡(luò)映射問題(Virtual Network Mapping Problem, VNMP)[3-6]是實現(xiàn)網(wǎng)絡(luò)虛擬化的一個重要環(huán)節(jié)。

虛擬網(wǎng)絡(luò)映射問題是一個NP-hard問題[5]。在網(wǎng)絡(luò)虛擬化中，不同的角色承擔(dān)不同的任務(wù)，基礎(chǔ)設(shè)施提供商(Infrastructure Provider, InP)和服務(wù)提供商(Service Provider, SP)分別承擔(dān)不同的任務(wù)：InP主要的任務(wù)是管理物理基礎(chǔ)設(shè)施資源；而SP主要的任務(wù)是從InP那里獲得可用的物理網(wǎng)絡(luò)資源創(chuàng)造虛擬網(wǎng)絡(luò)并提供端到端的服務(wù)[7]。所以虛擬網(wǎng)絡(luò)映射問題的解決方案，應(yīng)該從各個方面反映利益需求。

在虛擬網(wǎng)絡(luò)映射問題中，大多數(shù)的研究圍繞在單個目標(biāo)的優(yōu)化求解問題上，但實際上平衡多個目標(biāo)的優(yōu)化問題在現(xiàn)實世界中普遍存在，在虛擬網(wǎng)絡(luò)映射的背景下也不例外，對一個目標(biāo)最優(yōu)的解無法保證對另一個目標(biāo)也是最優(yōu)的，這就需要尋找一個折中的解決方案，使每個目標(biāo)函數(shù)同時得到優(yōu)化，最終得到綜合優(yōu)化的解集，像這樣的解集本文稱為Pareto最優(yōu)解集(Pareto-optimal Set)[8]。在多目標(biāo)優(yōu)化問題中，隨著目標(biāo)個數(shù)的增加，占優(yōu)阻力(Dominance Resistance)[9-11]將逐漸增大，抗占優(yōu)解(Dominance Resistant Solution, DRS)[9-12]的數(shù)量也隨之增加，從而使得Pareto熵逼近最優(yōu)解的難度也逐漸增加。

多目標(biāo)優(yōu)化問題通常通過加權(quán)值的方法轉(zhuǎn)化為單目標(biāo)問題進行求解[13-14]，但是權(quán)值的數(shù)值分配并不明確，得出的效果不是很好。目標(biāo)約束化處理也是一種常用的解決方法[15]，這些傳統(tǒng)的數(shù)學(xué)規(guī)劃方法往往效率較低，對于權(quán)值確定和目標(biāo)順序較敏感，因此，傳統(tǒng)的優(yōu)化算法對于解決實際問題中的多目標(biāo)問題并沒有起到較好的效果。進化算法作為一類成功應(yīng)用于多目標(biāo)優(yōu)化領(lǐng)域的啟發(fā)式搜索算法，受到越來越多的關(guān)注。

2002年，Deb等[16]提出非常經(jīng)典的多目標(biāo)算法：NSGA-Ⅱ，采用新型的解集選擇策略，保留精英集以使父代中的優(yōu)良個體直接進入下一代，提高解集質(zhì)量。本文在此基礎(chǔ)上改進算法，結(jié)合粒子群優(yōu)化算法，提出了一種多目標(biāo)粒子群優(yōu)化的虛擬網(wǎng)絡(luò)映射算法(Virtual Network Embedding algorithm based on Multi-objective Particle Swarm Optimization, VNE-MOPSO)：融入遺傳算法中的交叉算子思想，利用非支配排序、擁擠距離排序?qū)饧瘎澐指鱾€等級，精英保留機制選擇每代的優(yōu)良個體進入子代直至得到需要的解集。本文確立了兩個目標(biāo)函數(shù)：成本和節(jié)點負載均衡度，采用基于VNE-MOPSO方法求解。與其他方法相比，本文方法主要有三個特點：

1)以最小化成本和最小化節(jié)點負載均衡度為目標(biāo)函數(shù)，既保證了較小的映射成本，又為虛擬網(wǎng)絡(luò)映射提供了一個更為均衡的底層物理網(wǎng)絡(luò)。

2)采用基于非支配排序、擁擠距離排序的多目標(biāo)優(yōu)化算法求解。精英保留機制有效提高解集的質(zhì)量，促進了Pareto解集的快速收斂。

3)改進基本的粒子群優(yōu)化算法。在尋優(yōu)過程中融入了交叉算子的思想，并應(yīng)用在虛擬網(wǎng)絡(luò)映射中。在迭代過程中，以一定的概率將全局最優(yōu)解和自身最優(yōu)解交叉互換，從而擴大了解的搜索空間，在保證快速收斂的前提下有效避免了種群優(yōu)化陷入局部最優(yōu)。

1 多目標(biāo)虛擬網(wǎng)絡(luò)映射問題描述

1.1 網(wǎng)絡(luò)模型

虛擬網(wǎng)絡(luò)映射 虛擬網(wǎng)絡(luò)的映射過程是將虛擬請求Gv部署到底層物理網(wǎng)絡(luò)Gs的子集上，并且符合Gv對節(jié)點CPU、位置和鏈路帶寬約束的過程。通常，虛擬網(wǎng)絡(luò)映射可分為節(jié)點映射階段fN和鏈路映射階段fE。

1.2 目標(biāo)函數(shù)定義

多目標(biāo)的虛擬網(wǎng)絡(luò)映射問題定義如下：

(1)

資源容量約束：

(2)

(3)

連通性約束：

(?j∈Ns)(?luv∈Lv):

(4)

變量值范圍約束：

(5)

(6)

2 VNE-MOPSO

2.1PSO算法

粒子群優(yōu)化算法(ParticleSwarmOptimization,PSO)[17]是計算智能領(lǐng)域，除了蟻群算法、魚群算法之外的一種群體智能優(yōu)化算法。由Eberhart和Kennedy在1995年提出，源于對鳥群捕食行為的研究。PSO算法是從這種生物種群行為特征中得到啟發(fā)并用于求解優(yōu)化問題的，每個粒子都有自己的位置和速度，粒子的速度決定了粒子移動的方向和距離，速度隨自身及其他粒子的移動經(jīng)驗進行動態(tài)調(diào)整，逐漸向全局歷史最優(yōu)位置Xgb和自身歷史最優(yōu)位置Xpb移動，從而實現(xiàn)個體在可解空間中的尋優(yōu)。

PSO的速度和位置更新計算式如下：

Vi+1=ωVi+c1r1(Xpb-Xi)+c2r2(Xgb-Xi)

(7)

Xi+1=Xi+Vi+1

(8)

其中:Xi為粒子當(dāng)前的位置向量，Vi為粒子當(dāng)前的速度向量。ω表示粒子的慣性權(quán)重，表示粒子保持現(xiàn)有速度的慣性，r1和r2為0～1的隨機數(shù)，c1和c2為學(xué)習(xí)因子，代表粒子分別向局部最優(yōu)位置和全局最優(yōu)位置移動的趨勢。

2.2PSO算子重定義

原始粒子群算法具有執(zhí)行速度快、效率高的優(yōu)點，主要用于解決連續(xù)域內(nèi)的優(yōu)化問題，其實現(xiàn)過程是粒子以一定的速度向自身歷史最佳位置Xpb和全局粒子最佳位置Xgb聚集，從而不斷優(yōu)化得到最優(yōu)解。

但是，虛擬網(wǎng)絡(luò)映射問題是一個離散域問題，算法中每個粒子都代表問題的一個潛在解，每個粒子對應(yīng)一個由適應(yīng)度函數(shù)決定的適應(yīng)度值，需要根據(jù)具體問題對算法的參數(shù)和相關(guān)操作進行重新定義。

定義3 減法?。Xi?Xj用于計算兩種映射方案的差異性。如果映射方案在同一維上有相同的值，則差值的結(jié)果為1;否則為0。

定義4 加法⊕。PiVi⊕PjVj用于獲得映射方案的調(diào)整決策，其中PiVi和PjVj分別以Pi的概率Vi維持各維的值和以Pj的概率Vj維持各維的值，Pi+Pj=1(0≤P≤1)。

定義5 乘法?。Xi?Xj用于獲得新的映射方案，映射方案Xi按照調(diào)整決策Xj對其虛擬節(jié)點方案進行調(diào)整。

因此將式(7)和(8)重定義后的粒子群優(yōu)化算法的位置和速度更新基本公式如下：

Vi+1=P1Vi⊕P2(Xpb?Xi)⊕P3(Xgb?Xi)

(9)

Xi+1=Xi?Vi+1

(10)

其中:P1、P2和P3隨機產(chǎn)生，P1+P2+P3=1。

2.3VNE-MOPSO描述

第1.2節(jié)對多目標(biāo)虛擬網(wǎng)絡(luò)映射問題建立了模型。針對求解該問題，本文提出了一種基于多目標(biāo)粒子群優(yōu)化的虛擬網(wǎng)絡(luò)映射算法，即VNE-MOPSO。將每次經(jīng)過PSO算法產(chǎn)生的種群和自身最優(yōu)種群合并后，進行非支配和擁擠距離排序，由此得到種群的全局最優(yōu)解。PSO算法應(yīng)用到虛擬網(wǎng)絡(luò)映射中時，融入了交叉算子的思想，具體實現(xiàn)就是將全局最優(yōu)解與個體最優(yōu)解以一定的概率(本文中設(shè)置概率為0.9)進行交換，然后進行迭代求解，因此該算法有效提高所求解的多樣性并提高收斂速度。

VNE-MOPSO步驟如下。

1)虛擬網(wǎng)絡(luò)請求到達；

2)初始化解集，用最短路徑方法生成映射方案，計算每種映射方案的目標(biāo)函數(shù)值f1、f2；

3)每種映射方案自身作為個體最優(yōu)解，對解集進行非支配排序，得到等級為k1,k2，…，kp，p個等級的解，將等級為k1的非支配解集進行擁擠距離排序，取擁擠距離最大的映射方案作為當(dāng)前的全局最優(yōu)解；

4)WHILE(t未達到最大迭代次數(shù)T)

①根據(jù)種群的個體最優(yōu)解和全局最優(yōu)解按照式(9)、(10)得到一個映射方案集oldpop(t)；

②將這個映射方案集oldpop(t)與上一次迭代更新后的個體最優(yōu)映射方案集pbpop(t-1)的每個解進行支配對比，并將pbpop(t-1)中的被支配解更新為oldpop(t)的對應(yīng)解，最終得到當(dāng)前迭代的個體最優(yōu)映射方案集pbpop(t)；

③將②中提到的oldpop(t)與pbpop(t)合并，進行非支配排序、擁擠距離排序，得到gbpop(t)，進而得到全局最優(yōu)解；

④隨機產(chǎn)生一個概率r，設(shè)定如果r>0.9,將全局最優(yōu)解與任意一個個體最優(yōu)解交換；

⑤t=t+1；

END WHILE

5)根據(jù)用戶需求輸出映射方案。

根據(jù)本節(jié)提到的算法對多目標(biāo)虛擬網(wǎng)絡(luò)映射問題進行求解，本文采用基于非支配排序、擁擠距離排序的多目標(biāo)優(yōu)化算法求解，提高解集的質(zhì)量，促進了Pareto解集的快速收斂；改進的基本粒子群優(yōu)化算法，融入交叉算子，在虛擬網(wǎng)絡(luò)映射中得以應(yīng)用，擴大了解的搜索空間，增加解集的多樣性。在多目標(biāo)虛擬網(wǎng)絡(luò)映射尋優(yōu)過程中，不是輸出一個映射方案，而是以解集的形式輸出結(jié)果，即得到一個Pareto解集，解集中的各個解都是互相非支配的。

3 仿真實驗結(jié)果及分析

3.1 實驗設(shè)置

在ViNE-Yard平臺下對算法進行測試。在實驗中，通過GT-ITM工具產(chǎn)生基礎(chǔ)設(shè)施網(wǎng)絡(luò)(SubstrateNetwork,SN)及虛擬網(wǎng)絡(luò)(VirtualNetwork,VN)的拓撲。其中底層網(wǎng)絡(luò)拓撲包含100個物理節(jié)點，各節(jié)點的鏈接概率為0.5，底層節(jié)點的CPU資源和鏈路的帶寬資源均服從[0, 100]均勻分布。對于每個虛擬網(wǎng)絡(luò)請求，節(jié)點數(shù)為均勻分布在[2, 10]的隨機數(shù)，其CPU需求為分布在[0, 20]的隨機整數(shù)。虛擬鏈路請求的帶寬要求為均勻分布在[0, 25]的隨機數(shù)。所有算法通過C++語言在Linux系統(tǒng)下實現(xiàn)。在實驗中，將會產(chǎn)生100個虛擬網(wǎng)絡(luò)請求, 各虛擬請求按照泊松過程到達,同時，設(shè)置算法的種群大小為20，進行30次迭代后產(chǎn)生映射方案。

3.2 評價指標(biāo)

為了有效評估算法的性能，本文主要采用以下指標(biāo)對算法進行評價。

1)接受率。定義為在t時間段內(nèi)，被成功接收的虛擬網(wǎng)絡(luò)請求數(shù)目與虛擬網(wǎng)絡(luò)請求的總數(shù)目的比值：

(11)

其中：acCount表示一段時間內(nèi)接收的虛擬網(wǎng)絡(luò)請求數(shù)目；total_ac表示該時間段內(nèi)總的需要處理的虛擬網(wǎng)絡(luò)請求數(shù)目。

2)平均收益。收益可以定義為接收一個虛擬請求的節(jié)點CPU資源和鏈路帶寬資源的總和；平均收益就是指在t時間內(nèi)的請求資源總和的平均值：

(12)

3)平均成本。成本可以定義為接收一個虛擬請求時分得的物理資源的總和。平均成本就是指平均一個虛擬請求的成本：

(13)

4)節(jié)點負載均衡度：

(14)

3.3 實驗結(jié)果及分析

在初始化的節(jié)點映射階段，本文采用一種在滿足虛擬節(jié)點請求的距離約束范圍內(nèi)的情況下，虛擬節(jié)點對應(yīng)的滿足條件的候選物理節(jié)點少的優(yōu)先選擇映射的映射策略。鏈路映射則采用了R-Vine映射算法[18]中的虛擬網(wǎng)絡(luò)映射方案。然后結(jié)合本文提到的算法，將多目標(biāo)粒子群映射算法VNE-MOPSO分別與以成本為目標(biāo)函數(shù)的單目標(biāo)粒子群映射算法PSO(cost)-VNE，以節(jié)點負載均衡度為目標(biāo)函數(shù)的單目標(biāo)粒子群映射算法PSO(load)-VNE進行比較分析。

圖1比較的是VNE-MOPSO與以成本為目標(biāo)函數(shù)的粒子群優(yōu)化算法PSO(cost)-VNE和以節(jié)點負載均衡度為目標(biāo)函數(shù)的粒子群優(yōu)化算法PSO(load)-VNE的虛擬網(wǎng)絡(luò)的接受率對比。由圖1可知，代表PSO(cost)-VNE算法和PSO(load)-VNE算法的兩條曲線表明兩種算法的接受率效果基本一致，而均低于經(jīng)過改進的VNE-MOPSO的接受率。PSO(cost)-VNE算法和PSO(load)-VNE算法都是單目標(biāo)粒子群算法，即使選擇不同的目標(biāo)函數(shù)，接受率結(jié)果也并未有明顯差別，VNE-MOPSO均衡考慮兩種目標(biāo)函數(shù)，在同一時間段內(nèi)接收的虛擬網(wǎng)絡(luò)的個數(shù)相對多一些。

圖1 VNE-MOPSO與以成本或節(jié)點負載為目標(biāo)函數(shù)的PSO-VNE接受率對比

通過圖2可以發(fā)現(xiàn)，最初隨著虛擬請求的到來，虛擬網(wǎng)絡(luò)隨之開始接收符合條件的虛擬請求，物理資源的使用相應(yīng)增加，這樣就會在初始短時間內(nèi)迅速產(chǎn)生成本消耗。PSO(load)-VNE算法重點考慮網(wǎng)絡(luò)均衡度，在資源充足的初始映射階段產(chǎn)生的成本消耗相對很少，隨著虛擬請求的不斷到來，成本消耗趨于穩(wěn)定。由于VNE-MOPSO需要平衡成本和節(jié)點負載均衡度這兩方面的目標(biāo)函數(shù)，而PSO(cost)-VNE算法僅僅考慮成本這一目標(biāo)函數(shù)，相比VNE-MOPSO消耗了更多的底層資源。VNE-MOPSO在成本方面的優(yōu)勢隨后得以體現(xiàn)，當(dāng)虛擬請求的到來與離開平衡時，平均成本雖有波動但整體趨于平穩(wěn)。且VNE-MOPSO的平均成本低于PSO(cost)-VNE算法的平均成本。VNE-MOPSO和PSO(load)-VNE算法的平均成本消耗雖然有高有低，但總體上是趨于一致的，在VNE-MOPSO兼顧考慮成本和節(jié)點負載均衡度的情況下，與只考慮節(jié)點負載均衡度來進行映射的PSO(load)-VNE算法相比，雖然平均成本沒有優(yōu)化，但在其他方面產(chǎn)生了優(yōu)化。

圖2 VNE-MOPSO與以成本或節(jié)點負載為目標(biāo)函數(shù)的PSO-VNE平均成本對比

如圖3所示，在節(jié)點負載均衡度方面，VNE-MOPSO均優(yōu)于PSO(cost)-VNE算法和PSO(load)-VNE算法。

通過圖4可以看出，VNE-MOPSO的平均收益整體較優(yōu)于PSO(cost)-VNE算法和PSO(load)-VNE算法。因為接受率測試結(jié)果很相近，所以它們的平均收益也有基本一致的結(jié)果。

將算法VNE-MOPSO與加權(quán)值的粒子群映射算法PSO(weight)-VNE進行比較分析。設(shè)置五條曲線“weight=1/9”，“weight=3/7”，“weight=1/1”，“weight=7/3”，“weight=9/1”，圖5～8分別為相應(yīng)的接受率、成本、節(jié)點負載均衡度和收益對比。

圖3 VNE-MOPSO與以成本或節(jié)點負載為目標(biāo)函數(shù)的PSO-VNE節(jié)點負載均衡度對比

圖4 VNE-MOPSO與以成本或節(jié)點負載為目標(biāo)函數(shù)的

圖5 VNE-MOPSO與以不同比例成本和節(jié)點負載均衡度為目標(biāo)函數(shù)的PSO-VNE接受率對比

圖6 VNE-MOPSO與以不同比例成本和節(jié)點負載均衡度為目標(biāo)函數(shù)的PSO-VNE平均成本對比

圖5～8中比如“weight=1/9”表示目標(biāo)函數(shù)中成本和節(jié)點負載均衡度以1:9的比例構(gòu)成，以此類推其他設(shè)置權(quán)值。由圖5可知，雖然VNE-MOPSO在開始階段的短時間內(nèi)與其他測試結(jié)果有一致的接受率，但是時間約為4 500后明顯高于其他曲線。此圖表明VNE-MOPSO與加權(quán)值的粒子群映射算法PSO(weight)-VNE相比接受率有一定的優(yōu)越性。如圖6所示，VNE-MOPSO的平均成本均高于加權(quán)值的粒子群映射算法PSO(weight)-VNE的幾個結(jié)果，因為更高的接受率意味著需要進行更多的虛擬網(wǎng)絡(luò)映射，也會導(dǎo)致總映射成本的增加，但仍在可接受范圍內(nèi)。通過圖7和圖8可知，VNE-MOPSO相比其他結(jié)果有較好的節(jié)點負載均衡度和收益。

圖7 VNE-MOPSO與以不同比例成本和節(jié)點負載均衡度為目標(biāo)函數(shù)的PSO-VNE節(jié)點負載均衡度對比

圖8 VNE-MOPSO與以不同比例成本和節(jié)點負載均衡度為目標(biāo)函數(shù)的PSO-VNE平均收益對比

當(dāng)weight=7/3時，PSO(weight)-VNE算法的接受率測試結(jié)果與VNE-MOPSO的最接近，但是還是低于該算法的接受率。此時由圖7可知節(jié)點負載均衡度是最高的，平均收益略低于VNE-MOPSO的，所以總體看來當(dāng)weight=7/3時,PSO(weight)-VNE算法運行出的解決方案質(zhì)量略差。當(dāng)weight=3/7時，PSO(weight)-VNE算法的節(jié)點負載均衡度與VNE-MOPSO的最接近，但接受率和收益并沒有很好的效果。加權(quán)值的算法首要難點就是權(quán)值確定，有時還需要有高的精確度，取值比例分配情況多樣，在實際應(yīng)用中，最終取值不一定是一種優(yōu)秀的方案。

4 結(jié)語

針對虛擬網(wǎng)絡(luò)映射問題，本文提出了一種多目標(biāo)粒子群優(yōu)化算法，并在虛擬網(wǎng)絡(luò)映射中成功應(yīng)用。該算法引入遺傳算法中的交叉算子思想，以0.9的概率完成解集間的交換工作，同時有效結(jié)合非支配排序和擁擠距離排序方法。采用成本和節(jié)點負載均衡度作為需要處理的兩個目標(biāo)函數(shù)，同時考慮這兩種因素對虛擬網(wǎng)絡(luò)映射的影響。通過實驗表明，該算法具備一定的有效性，仿真結(jié)果達到較好的平衡。

一個好的虛擬網(wǎng)絡(luò)映射方案，需要考慮的因素是多方面的。在虛擬網(wǎng)絡(luò)映射中，本文提出的算法考慮平衡兩個目標(biāo)函數(shù)對虛擬映射的影響，因此，下一步的工作是嘗試平衡三個目標(biāo)函數(shù)的作用，將有利于得到更好的虛擬網(wǎng)絡(luò)映射處理方案。

)

[1]ANDERSONT,PETERSONL,SHENKERS,etal.OvercomingtheInternetimpassethroughvirtualization[J].Computer, 2005, 38(4): 34-41.

[2]XINGY,ZHANY.Virtualizationandcloudcomputing[M]//FutureWirelessNetworksandInformationSystems.Berlin:Springer, 2012: 305-312.

[3]CHOWDHURYNMMK,BOUTABAR.Asurveyofnetworkvirtualization[J].ComputerNetworks, 2010, 54(5): 862-876.

[4]HAIDERA,POTTERR,NAKAOA.Challengesinresourceallocationinnetworkvirtualization[EB/OL]. [2016- 01- 02].https://www.mendeley.com/catalog/challenges-resource-allocation-network-virtualization/.

[5]YUM,YIY,REXFORDJ,etal.Rethinkingvirtualnetworkembedding:substratesupportforpathsplittingandmigration[J].ACMSIGCOMMComputerCommunicationReview, 2008, 38(2): 17-29.

[6]CHOWDHURYM,SAMUELF.CS854projectproposal:virtualnetworkembeddingacrossmultipledomains[EB/OL]. [2016- 01- 02].http://xueshu.baidu.com/s?wd=paperuri%3A%2842c9715c74f264e3db036e8077f99561%29&filter=sc_long_sign&tn=SE_xueshusource_2kduw22v&sc_vurl=http%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fdownload%3Bjsessionid%3D6064D06E1F9447B0C75B00461AF72213%3Fdoi%3D10.1.1.294.1638%26rep%3Drep1%26type%3Dpdf&ie=utf-8&sc_us=18201165924731794338.

[7]FEAMSTERN,GAOL,REXFORDJ.Howtoleasetheinternetinyoursparetime[J].ACMSIGCOMMComputerCommunicationReview, 2007, 37(1): 61-64.

[8]GONGM,JIAOL,DUH,etal.Multiobjectiveimmunealgorithmwithnondominatedneighbor-basedselection[J].EvolutionaryComputation, 2008, 16(2): 225-255.

[9]PURSHOUSERC,FLEMINGPJ.Ontheevolutionaryoptimizationofmanyconflictingobjectives[J].IEEETransactionsonEvolutionaryComputation, 2007, 11(6): 770-784.

[10]ADRASF,FLEMINGPJ.Diversitymanagementinevolutionarymany-objectiveoptimization[J].IEEETransactionsonEvolutionaryComputation, 2011, 15(2): 183-195.

[11]L’OPEZA,COELLOCAC,OYAMAA,etal.Analternativepreferencerelationtodealwithmany-objectiveoptimizationproblems[C]//EvolutionaryMulti-CriterionOptimization,LNCS7811.Berlin:Springer, 2013: 291-306.

[12]BATISTALS,CAMPELOF,GUIMARESFG,etal.Acomparisonofdominancecriteriainmany-objectiveoptimizationproblems[C]//Proceedingsofthe2011IEEECongressonEvolutionaryComputation.Piscataway,NJ:IEEE, 2011: 2359-2366.

[13]CHOWDHURYNMMK,RAHMANMR,BOUTABAR.Virtualnetworkembeddingwithcoordinatednodeandlinkmapping[C]//ProceedingsoftheIEEEINFOCOM2009.Piscataway,NJ:IEEE, 2009: 783-791.

[14]RICCIR,ALFELDC,LEPREAUJ.Asolverforthenetworktestbedmappingproblem.ACMSIGCOMMComputerCommunicationReview, 2003, 33(2): 65-81.

[15] FRINCU M E, CRACIUN C. Multi-objective meta-heuristics for scheduling applications with high availability requirements and cost constraints in multi-cloud environments // Proceedings of the 2011 4th IEEE International Conference on Utility and Cloud Computing. Washington, DC: IEEE Computer Society, 2011: 267-274.

[16] DEB K, PRATAP A, AGARWAL S, et al. A fast and elitist multiobjective genetic algorithm: NSGA-Ⅱ . IEEE Transactions on Evolutionary Computation, 2002, 6(2): 182-197.

[17] KENNEDY J, EBERHART R. Particle swarm optimization [M]// Encyclopedia of Machine Learning. New York: Springer US, 2011: 760-766.

[18] CHOWDHURY M, RAHMAN M R, BOUTABA R. ViNEYard: virtual network embedding algorithms with coordinated node and link mapping [J]. IEEE/ACM Transactions on Networking, 2012, 20(1): 206-219.

This work is partially supported by the National Natural Science Foundation of China (61373149).

LI Zhen, born in 1991, M. S. candidate. Her research interests include cloud computing, network virtualization.

ZHENG Xiangwei, born in 1971, Ph. D., professor. His research interests include computational intelligence, cloud computing.

ZHANG Hui, born in 1991, M. S. candidate. His research interests include cloud computing, network virtualization.

Virtual network embedding algorithm based on multi-objective particle swarm optimization

LI Zhen1,2, ZHENG Xiangwei1,2*, ZHANG Hui1,2

(1.CollegeofInformationScienceandEngineering,ShandongNormalUniversity,JinanShandong250000,China; 2.ShandongProvincialKeyLaboratoryforDistributedComputerSoftwareNovelTechnology,JinanShandong250014,China)

In virtual network mapping, most studies only consider one mapping object, which can not reflect the interests of many aspects. To solve this problem, a Virtual Network Embedding algorithm based on Multi-objective Particle Swarm Optimization (VNE-MOPSO) was proposed by combining multi-objective algorithm and Particle Swarm Optimization (PSO) algorithm. Firstly, the crossover operator was introduced into the basic PSO algorithm to expand the search space of population optimization. Secondly, the non-dominated sorting and crowding distance sorting were introduced into the multi-objective optimization algorithm, which can speed up the population convergence. Finally, by minimizing both the cost and the node load balance degree as the virtual network mapping objective function, a multi-objective PSO algorithm was proposed to solve the Virtual Network Mapping Problem (VNMP). The experimental results show that the proposed algorithm can solve the VNMP, which has advantages in network request acceptance rate, average cost, average node load balance degree, and infrastructure provider’s profit.

virtual network mapping; multi-objective optimization algorithm; Particle Swarm Optimization (PSO) algorithm; non-dominated sorting; crowding distance sorting; crossover operator

2016- 08- 31;

2016- 11- 01。 基金項目:國家自然科學(xué)基金資助項目(61373149)。

李貞(1991—)，女，山東濟南人，碩士研究生，CCF會員，主要研究方向：云計算、網(wǎng)絡(luò)虛擬化； 鄭向偉(1971—)，男，山東泰安人，教授，博士，CCF會員，主要研究方向：計算智能、云計算； 張輝(1991—)，男，山東濰坊人，碩士研究生，CCF會員，主要研究方向：云計算、網(wǎng)絡(luò)虛擬化。

1001- 9081(2017)03- 0755- 05

10.11772/j.issn.1001- 9081.2017.03.755

TP

A