李 貞，鄭向偉，張 輝

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

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

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

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

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

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

0 引言

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

虛擬網(wǎng)絡(luò)映射問題是一個(gè)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)該從各個(gè)方面反映利益需求。

在虛擬網(wǎng)絡(luò)映射問題中，大多數(shù)的研究圍繞在單個(gè)目標(biāo)的優(yōu)化求解問題上，但實(shí)際上平衡多個(gè)目標(biāo)的優(yōu)化問題在現(xiàn)實(shí)世界中普遍存在，在虛擬網(wǎng)絡(luò)映射的背景下也不例外，對一個(gè)目標(biāo)最優(yōu)的解無法保證對另一個(gè)目標(biāo)也是最優(yōu)的，這就需要尋找一個(gè)折中的解決方案，使每個(gè)目標(biāo)函數(shù)同時(shí)得到優(yōu)化，最終得到綜合優(yōu)化的解集，像這樣的解集本文稱為Pareto最優(yōu)解集(Pareto-optimal Set)[8]。在多目標(biāo)優(yōu)化問題中，隨著目標(biāo)個(gè)數(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)問題進(jìn)行求解[13-14]，但是權(quán)值的數(shù)值分配并不明確，得出的效果不是很好。目標(biāo)約束化處理也是一種常用的解決方法[15]，這些傳統(tǒng)的數(shù)學(xué)規(guī)劃方法往往效率較低，對于權(quán)值確定和目標(biāo)順序較敏感，因此，傳統(tǒng)的優(yōu)化算法對于解決實(shí)際問題中的多目標(biāo)問題并沒有起到較好的效果。進(jìn)化算法作為一類成功應(yīng)用于多目標(biāo)優(yōu)化領(lǐng)域的啟發(fā)式搜索算法，受到越來越多的關(guān)注。

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

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

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

3)改進(jìn)基本的粒子群優(yōu)化算法。在尋優(yōu)過程中融入了交叉算子的思想，并應(yīng)用在虛擬網(wǎng)絡(luò)映射中。在迭代過程中，以一定的概率將全局最優(yōu)解和自身最優(yōu)解交叉互換，從而擴(kuò)大了解的搜索空間，在保證快速收斂的前提下有效避免了種群優(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é)點(diǎn)CPU、位置和鏈路帶寬約束的過程。通常，虛擬網(wǎng)絡(luò)映射可分為節(jié)點(diǎn)映射階段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]是計(jì)算智能領(lǐng)域，除了蟻群算法、魚群算法之外的一種群體智能優(yōu)化算法。由Eberhart和Kennedy在1995年提出，源于對鳥群捕食行為的研究。PSO算法是從這種生物種群行為特征中得到啟發(fā)并用于求解優(yōu)化問題的，每個(gè)粒子都有自己的位置和速度，粒子的速度決定了粒子移動(dòng)的方向和距離，速度隨自身及其他粒子的移動(dòng)經(jīng)驗(yàn)進(jìn)行動(dòng)態(tài)調(diào)整，逐漸向全局歷史最優(yōu)位置Xgb和自身歷史最優(yōu)位置Xpb移動(dòng)，從而實(shí)現(xiàn)個(gè)體在可解空間中的尋優(yōu)。

PSO的速度和位置更新計(jì)算式如下：

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的隨機(jī)數(shù)，c1和c2為學(xué)習(xí)因子，代表粒子分別向局部最優(yōu)位置和全局最優(yōu)位置移動(dòng)的趨勢。

2.2PSO算子重定義

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

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

定義3 減法?。Xi?Xj用于計(jì)算兩種映射方案的差異性。如果映射方案在同一維上有相同的值，則差值的結(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ǎn)方案進(jìn)行調(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隨機(jī)產(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)種群合并后，進(jìn)行非支配和擁擠距離排序，由此得到種群的全局最優(yōu)解。PSO算法應(yīng)用到虛擬網(wǎng)絡(luò)映射中時(shí)，融入了交叉算子的思想，具體實(shí)現(xiàn)就是將全局最優(yōu)解與個(gè)體最優(yōu)解以一定的概率(本文中設(shè)置概率為0.9)進(jìn)行交換，然后進(jìn)行迭代求解，因此該算法有效提高所求解的多樣性并提高收斂速度。

VNE-MOPSO步驟如下。

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

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

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

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

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

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

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

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

⑤t=t+1；

END WHILE

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

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

3 仿真實(shí)驗(yàn)結(jié)果及分析

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

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

3.2 評價(jià)指標(biāo)

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

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

(11)

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

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

(12)

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

(13)

4)節(jié)點(diǎn)負(fù)載均衡度：

(14)

3.3 實(shí)驗(yàn)結(jié)果及分析

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)語

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

一個(gè)好的虛擬網(wǎng)絡(luò)映射方案，需要考慮的因素是多方面的。在虛擬網(wǎng)絡(luò)映射中，本文提出的算法考慮平衡兩個(gè)目標(biāo)函數(shù)對虛擬映射的影響，因此，下一步的工作是嘗試平衡三個(gè)目標(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。 基金項(xiàng)目:國家自然科學(xué)基金資助項(xiàng)目(61373149)。

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

1001- 9081(2017)03- 0755- 05

10.11772/j.issn.1001- 9081.2017.03.755

TP

A