基于Pareto熵的多目標(biāo)虛擬網(wǎng)絡(luò)映射算法

劉 穎,王 聰,苑 迎,蔣國(guó)佳,劉珂禎,王翠榮

(東北大學(xué) 秦皇島分校 計(jì)算機(jī)與通信工程學(xué)院,河北 秦皇島 066004)

0 概述

自20世紀(jì)60年代以來(lái),互聯(lián)網(wǎng)得到飛速發(fā)展,已成為現(xiàn)代社會(huì)的重要基礎(chǔ)設(shè)施。目前中國(guó)網(wǎng)民數(shù)量已達(dá)到8.02億[1],用戶數(shù)量、接入網(wǎng)絡(luò)應(yīng)用軟件數(shù)量的激增,對(duì)互聯(lián)網(wǎng)性能提出更高的要求。現(xiàn)有的互聯(lián)網(wǎng)架構(gòu)在服務(wù)質(zhì)量、響應(yīng)速度等方面很難滿足這些要求，在某種程度上呈現(xiàn)出“僵化”現(xiàn)象。為此，研究人員提出網(wǎng)絡(luò)虛擬化技術(shù)，通過(guò)應(yīng)用現(xiàn)有的互聯(lián)網(wǎng)架構(gòu)，將底層物理網(wǎng)絡(luò)的硬件和軟件資源進(jìn)行整合，提高了網(wǎng)絡(luò)資源利用率。該技術(shù)在未來(lái)互聯(lián)網(wǎng)發(fā)展中極具應(yīng)用前景[2]。虛擬網(wǎng)絡(luò)映射是網(wǎng)絡(luò)虛擬化技術(shù)的一個(gè)重要部分,其可在滿足節(jié)點(diǎn)和鏈路資源約束的基礎(chǔ)上將虛擬網(wǎng)絡(luò)映射到物理網(wǎng)絡(luò),從而實(shí)現(xiàn)底層資源的高效利用[3]。

在虛擬網(wǎng)絡(luò)映射問(wèn)題的求解過(guò)程中,元啟發(fā)式算法應(yīng)用廣泛[4]。文獻(xiàn)[4]采用一種從大粒子到大粒子、小粒子到小粒子的粒子位置初始化策略,以達(dá)到更好的算法收斂性和底層網(wǎng)絡(luò)負(fù)載平衡。文獻(xiàn)[5]采用多條路徑以提供更好的鏈路映射方案,并將粒子群優(yōu)化算法和遺傳算法相結(jié)合,在不斷迭代的基礎(chǔ)上尋找映射方案。文獻(xiàn)[6]針對(duì)網(wǎng)絡(luò)拓?fù)鋱D分解生成的環(huán)和樹結(jié)構(gòu),提出一種基于多元映射算法的改進(jìn)蟻群算法。文獻(xiàn)[7]提出拓?fù)漕A(yù)配置機(jī)制,在映射前先修剪虛擬拓?fù)湟蕴岣哂成涞慕邮苈省Ｎ墨I(xiàn)[8]提出一種面向鏈路映射的蟻群系統(tǒng)算法,根據(jù)相連的鏈路資源屬性對(duì)節(jié)點(diǎn)進(jìn)行排序,并在蟻群系統(tǒng)中引入具有連接感知能力的鏈路啟發(fā)式信息,有效地節(jié)省了帶寬。

近年來(lái),隨著能源成本增長(zhǎng)和人類生態(tài)意識(shí)的提高,網(wǎng)絡(luò)提供商、研究機(jī)構(gòu)和互聯(lián)網(wǎng)組件制造商等都試圖從各方面降低互聯(lián)網(wǎng)組件(如軟件)的能耗[9],這在求解虛擬網(wǎng)絡(luò)的映射方案上也有充分體現(xiàn)。文獻(xiàn)[10]針對(duì)底層網(wǎng)絡(luò)節(jié)點(diǎn)的異構(gòu)性,優(yōu)選具有最強(qiáng)資源能力的物理節(jié)點(diǎn),將具有最低能耗的路徑用于鏈路映射。文獻(xiàn)[11]針對(duì)大規(guī)模云系統(tǒng)提出整體方案,其中多個(gè)數(shù)據(jù)中心通過(guò)骨干網(wǎng)絡(luò)互連提供云服務(wù),并提出虛擬機(jī)配置的混合整形線性規(guī)劃公式,最大限度地減少虛擬骨干網(wǎng)的功耗和數(shù)據(jù)中心資源使用。文獻(xiàn)[12]提出一種優(yōu)化模型研究數(shù)據(jù)中心的映射節(jié)能問(wèn)題,同步考慮了與工作負(fù)載有關(guān)和無(wú)關(guān)的能耗,并引入用于虛擬網(wǎng)絡(luò)配置的啟發(fā)式方法,在遵守服務(wù)級(jí)別協(xié)議的同時(shí)降低了能耗。文獻(xiàn)[13]基于虛擬網(wǎng)絡(luò)的動(dòng)態(tài)特性提出多反饋控制模型,通過(guò)關(guān)閉活動(dòng)節(jié)點(diǎn)和活動(dòng)鏈路,顯著降低了系統(tǒng)能耗。 文獻(xiàn)[14]優(yōu)先將相鄰虛擬節(jié)點(diǎn)映射到相鄰物理節(jié)點(diǎn)以保持拓?fù)湟恢滦?并減小映射范圍,從而有效地降低了映射成本和系統(tǒng)能耗。研究人員在用于虛擬網(wǎng)絡(luò)資源分配的基本映射方法及映射過(guò)程中的能量需求、拓?fù)浣Y(jié)構(gòu)等研究方面已取得一定成果[15],然而大部分研究都圍繞著網(wǎng)絡(luò)資源分配的單個(gè)目標(biāo)進(jìn)行優(yōu)化,在虛擬網(wǎng)絡(luò)資源的實(shí)際分配中,通常需要同時(shí)考慮映射成本、收益、能耗、服務(wù)質(zhì)量(Quality of Service,QoS)等多目標(biāo)問(wèn)題。

本文從多目標(biāo)優(yōu)化角度出發(fā),提出一種基于Pareto熵的虛擬網(wǎng)絡(luò)映射VEN-MOPSO算法。使用目標(biāo)空間變換方法[16]計(jì)算當(dāng)前最優(yōu)解集的Pareto熵,并以每次迭代后最優(yōu)解集的變化引發(fā)的差熵為依據(jù)評(píng)估種群的進(jìn)化狀態(tài),進(jìn)而設(shè)計(jì)動(dòng)態(tài)自適應(yīng)的粒子運(yùn)動(dòng)參數(shù)策略,控制粒子群搜索的過(guò)程,以提高解的優(yōu)化程度。

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

1.1 虛擬網(wǎng)絡(luò)映射問(wèn)題描述

底層網(wǎng)絡(luò)(Substrate Network,SN)用加權(quán)無(wú)向圖表示為:

(1)

虛擬網(wǎng)絡(luò)(Virtual Network,VN)用加權(quán)無(wú)向圖表示為:

(2)

虛擬網(wǎng)絡(luò)映射問(wèn)題(Virtual Network Mapping Problem,VNMP)是將 VN 映射到 SN 的過(guò)程,可以形式化地定義為從GV到GS子集的映射[17]。映射過(guò)程包括節(jié)點(diǎn)映射過(guò)程和鏈路映射過(guò)程。

1.2 底層網(wǎng)絡(luò)能耗

映射過(guò)程能耗包括以下兩方面:

1)節(jié)點(diǎn)能耗

網(wǎng)絡(luò)節(jié)點(diǎn)即服務(wù)器節(jié)點(diǎn),網(wǎng)絡(luò)節(jié)點(diǎn)能耗與該節(jié)點(diǎn)承載的虛擬網(wǎng)絡(luò)節(jié)點(diǎn)總和成正比[13],第i個(gè)底層節(jié)點(diǎn)能耗定義為:

(3)

其中,Pb為底層物理節(jié)點(diǎn)能耗的基本值,Pm為底層物理節(jié)點(diǎn)能耗的最大值,u為處理器利用率。

2)鏈路能耗

在網(wǎng)絡(luò)虛擬化環(huán)境中具有減負(fù)引擎裝置,因而網(wǎng)絡(luò)設(shè)備對(duì)流量負(fù)荷的能耗不敏感[18]。物理鏈路能耗通常被視為常量[19],第j條鏈路能耗定義為:

(4)

其中,Pn為物理鏈路的能耗。

1.3 多目標(biāo)優(yōu)化虛擬網(wǎng)絡(luò)映射問(wèn)題建模

虛擬網(wǎng)絡(luò)映射優(yōu)化目標(biāo)為映射成本和能耗最小化。用戶的每個(gè)虛擬網(wǎng)絡(luò)請(qǐng)求映射模型為:

(5)

其中,f1為網(wǎng)絡(luò)資源開銷,cpu(nv)為虛擬節(jié)點(diǎn)nv所需的計(jì)算能力值,bw(lv)為虛擬鏈路lv所需的帶寬能力值,α為計(jì)算資源相對(duì)權(quán)重,β為帶寬資源相對(duì)權(quán)重,且α+β=1,φl(shuí)v為用來(lái)判斷l(xiāng)v是否被映射到物理鏈路上的二進(jìn)制變量,f2為映射能耗,ti為節(jié)點(diǎn)i開啟的時(shí)間,tj為鏈路j開啟的時(shí)間。

映射過(guò)程還需滿足CUP處理器資源和帶寬資源的約束條件,如式(6)所示:

s.t.?nv∈NV,?ni∈pS,nv→ni,

Ccpu(ni)-∑Ccpu(nv)≥Rcpu(nv)

?lv∈LV,?lj∈pS,lv→lj,

(6)

其中,pS為映射后物理節(jié)點(diǎn)和物理鏈路集合,ni為目標(biāo)物理節(jié)點(diǎn),nv為映射的虛擬節(jié)點(diǎn),ni的可用節(jié)點(diǎn)資源不能小于nv所請(qǐng)求的節(jié)點(diǎn)資源,lV為虛擬鏈路,pS為虛擬鏈路所映射的物理路徑,lj為虛擬鏈路所映射物理路徑的每條物理鏈路,lj的空閑帶寬不能小于lV所請(qǐng)求的帶寬。

2 VNE-MOPSO算法

由于上述優(yōu)化模型的最優(yōu)解不唯一,因此還需進(jìn)一步設(shè)計(jì)映射方案選擇策略。在VNE-MOPSO算法中,每當(dāng)尋找到一個(gè)質(zhì)量更高的可行解時(shí),外部最優(yōu)解集(Pareto最優(yōu)解集、外部檔案)就會(huì)進(jìn)行更新。根據(jù)外部最優(yōu)解集的更新情況和差熵等信息,設(shè)計(jì)出自適應(yīng)的粒子參數(shù)策略,可促使算法尋找到更多高質(zhì)量的解。以下分別對(duì)Pareto最優(yōu)和Pareto熵的相關(guān)定義、外部最優(yōu)解集更新算法、自適應(yīng)粒子參數(shù)策略、VNE-PSO算法的整體流程進(jìn)行介紹。

2.1 Pareto最優(yōu)相關(guān)定義

定義1對(duì)于任意兩個(gè)向量u,v∈Ω,稱u占優(yōu)v(或v被u占優(yōu),即Pareto占優(yōu)),記作u?v,當(dāng)且僅當(dāng)?i=1,2,…,m,ui≤vi∧ ?j=1,2,…,m,uj

定義2一個(gè)解x*∈Ω被稱為Pareto最優(yōu)解或非占優(yōu)解,當(dāng)且僅當(dāng)?x∈Ω:x?x*[16]。所有的Pareto最優(yōu)解的集合PS={x*|?x∈Ω:x?x*)}稱為Pareto最優(yōu)解集。

定義3所有Pareto最優(yōu)解對(duì)應(yīng)的目標(biāo)函數(shù)值所形成的區(qū)域PF={F(x*)|x*)∈PS}稱為Pareto前端、Pareto前沿或Pareto均衡面[16]。

2.2 Pareto熵多目標(biāo)優(yōu)化模型及進(jìn)化狀態(tài)

Pareto熵多目標(biāo)優(yōu)化模型以兩次迭代的Pareto差熵為優(yōu)化依據(jù)。首先將存儲(chǔ)在外部最優(yōu)解集中的多維Pareto解以目標(biāo)空間轉(zhuǎn)換方式映射到二維平面,然后求出每個(gè)Pareto解的平行格坐標(biāo)以及近似Pareto前端的Pareto熵。當(dāng)外部最優(yōu)解集更新時(shí),會(huì)導(dǎo)致近似Pareto前端的Pareto熵發(fā)生變化,即產(chǎn)生差熵。差熵是控制優(yōu)化過(guò)程的有效信息。

將多維Pareto解按照平行坐標(biāo)方式轉(zhuǎn)化到二維平面中,其映射的整數(shù)值坐標(biāo)即為平行格坐標(biāo)[16],計(jì)算公式為:

(7)

在第t次迭代過(guò)程中,外部最優(yōu)解集近似Pareto前端的Pareto熵Entropy(t)[16]的計(jì)算公式為:

(8)

其中,Cellk,m(t)為Pareto解的格坐標(biāo)分量落在平行格坐標(biāo)系統(tǒng)第k行第m列方格的個(gè)數(shù)。

當(dāng)外部最優(yōu)解集容量已滿時(shí),再次更新需評(píng)估解的個(gè)體密度。根據(jù)式(7),將外部最優(yōu)解集的成員映射到平行格坐標(biāo)系統(tǒng)后,任意解的個(gè)體密度[16]的計(jì)算公式為:

(9)

(10)

其中,Pi為任意解,Density(Pi)為任意解的個(gè)體密度,i,j=1,2,…,K(K為外部最優(yōu)解集中成員個(gè)數(shù)),Pj為外部最優(yōu)解集中除Pi之外的Pareto解,PCD(Pi,Pj)為Pi和Pj之間的平行格距離。

隨著粒子群不斷搜索到新解,外部最優(yōu)解集不斷更新。VNE-PSO算法在每次迭代中的進(jìn)化狀態(tài)包括以下3種:

1)停滯狀態(tài):VNE-PSO算法得到的新解被外部最優(yōu)解集拒絕。

2)多樣化狀態(tài):VNE-PSO算法得到的新解取代外部最優(yōu)解集中質(zhì)量較差的舊解。

3)收斂狀態(tài):在目標(biāo)空間中VNE-PSO算法產(chǎn)生的Pareto前端向真實(shí)的Pareto前端靠近。

2.3 外部最優(yōu)解集更新算法

外部最優(yōu)解集的更新過(guò)程包括5種情形,各種情形對(duì)應(yīng)的進(jìn)化狀態(tài)和差熵如表1所示,其中M為優(yōu)化目標(biāo)個(gè)數(shù),K為外部最優(yōu)解集最大容量。

表1 外部最優(yōu)解集更新過(guò)程分析Table 1 Updating process analysis of external optimal solution set

根據(jù)上述5種情形可得出外部最優(yōu)解集更新算法如下:

算法1外部最優(yōu)解集更新算法

輸入

待更新的外部最優(yōu)解集A

外部最優(yōu)解集的最大容量K

進(jìn)化算法獲得的新解P

輸出

更新后的外部最優(yōu)解集A′

進(jìn)化狀態(tài)state(取值0,1,2.分別表示停滯狀態(tài),多樣化狀態(tài),收斂狀態(tài))

差熵ΔEntropy

1.If (A=?){

A′={P};state=2;ΔEntropy=log M;

ReturnA′,state,ΔEntropy;} /* 情形 I:外部最優(yōu)解集為空集,收斂狀態(tài)*/

2.If (P被A中的任意一個(gè)成員ai∈A占優(yōu)) {

state=0;ΔEntropy=0;

ReturnA,state,ΔEntropy;} /* 情形 II:新解被舊解占優(yōu),停滯狀態(tài) */

3.If (對(duì)任意ai∈A,ai被P占優(yōu)) {

被P占優(yōu)的舊解個(gè)數(shù)記為r,當(dāng)前A的成員個(gè)數(shù)記為|A|,首先令A(yù)=A/{ai}。

Else if (1

4.If (|A|

A′=A∪{P};state=2;

Return A′,state,ΔEntropy;} /* 情形 III:新解占優(yōu)舊解,收斂狀態(tài)*/

5.Else if (|A|==K) {

6.令 B=A∪{P},對(duì)B中每一個(gè)成員bi∈B,評(píng)估bi的個(gè)體密度。

7.查找B中具有最大個(gè)體密度的成員 bmax。

8.If (P==bmax) {

A′=A;state=0;ΔEntropy=0;

Return A′,state,ΔEntropy;} /* 情形 IV:新解質(zhì)量最差,停滯狀態(tài)*/

9.Else {

Return A′,state,ΔEntropy;} /* 情形 V:新解替換質(zhì)量最差的舊解,多樣化狀態(tài) */

}

2.4 粒子群優(yōu)化算法

Vi+1=ωVi+c1(pBesti-Xi)+c2(gBesti-Xi)

(11)

Xi+1=Xi+Vi+1

(12)

其中,ω為慣性權(quán)重,c1為學(xué)習(xí)權(quán)重,c2為群體權(quán)重,且ω、c1、c2均大于0,位置向量pBesti為個(gè)體最優(yōu)解,位置向量gBesti為整個(gè)群體的全局最優(yōu)解。

2.5 自適應(yīng)粒子運(yùn)動(dòng)參數(shù)策略

為了更好地控制進(jìn)化過(guò)程,需要持續(xù)從進(jìn)化環(huán)境中獲取實(shí)時(shí)反饋信息,可通過(guò)調(diào)整粒子運(yùn)動(dòng)參數(shù)ω、c1、c2調(diào)控搜索趨向。將進(jìn)化狀態(tài)和差熵作為運(yùn)動(dòng)參數(shù)的因變量:

(13)

(14)

(15)

其中,Lenω為ω的區(qū)間長(zhǎng)度,Lenc1為c1的區(qū)間長(zhǎng)度,Lenc2為c2的區(qū)間長(zhǎng)度,按照文獻(xiàn)[20],ω、c1和c2的取值范圍分別為[0.4,0.9]、[0.5,2.5]和[0.5,2.5],即區(qū)間長(zhǎng)度分別為0.5、2.0和2.0。

2.6 VNE-MOPSO算法整體流程

VNE-MOPSO算法的整體流程為:對(duì)于每一個(gè)虛擬網(wǎng)絡(luò)請(qǐng)求,首先隨機(jī)生成粒子的初始位置,每獲得一個(gè)新位置就判斷其是否可行,再更新外部最優(yōu)解集以獲得進(jìn)化狀態(tài)和差熵,并由自適應(yīng)粒子運(yùn)動(dòng)參數(shù)策略更新粒子速度和位置,直到迭代結(jié)束。其中,通過(guò)式(11)位置減法進(jìn)行同或運(yùn)算,得到的速度向量Vi+1采用概率映射方式轉(zhuǎn)化為二進(jìn)制數(shù)值,具體做法為:使用sigmoid函數(shù)將Vi+1映射到[0,1]區(qū)間作為概率,如果該概率大于或等于隨機(jī)生成的[0,1]區(qū)間的小數(shù),則下一步速度取值為1,否則取值為0,如式(16)所示:

(16)

通過(guò)式(12) 更新粒子位置,將速度分量值為1的虛擬節(jié)點(diǎn)重新隨機(jī)映射到一個(gè)滿足節(jié)點(diǎn)約束條件的物理節(jié)點(diǎn)上。

VNE-MOPSO算法偽代碼算法如下:

算法2基于Pareto熵的虛擬網(wǎng)絡(luò)映射算法(VNE-MOPSO)

輸入虛擬網(wǎng)絡(luò)Gv,物理網(wǎng)絡(luò)Gs

輸出映射方案 solution

1.獲得Gs中實(shí)時(shí)空閑資源的節(jié)點(diǎn)隊(duì)列和鏈路隊(duì)列;

2.對(duì)于群體中的每個(gè)粒子,初始化其位置。

3.初始化令全局外部最優(yōu)解集gArchive=?,令個(gè)體外部最優(yōu)解集pArchive=?;

4.For (int i=0;i < MaxItCount;i++){

5.If (當(dāng)前位置可行){

6.用最短路徑方式得出映射方案,計(jì)算相應(yīng)的目標(biāo)函數(shù)值f1、f2;

7.對(duì)每個(gè)粒子調(diào)用算法1,更新gArchive,保存此時(shí)的進(jìn)化狀態(tài)、差熵;

8.對(duì)每個(gè)粒子調(diào)用算法1,更新pArchive;

9.從gArchive中隨機(jī)地選取一個(gè)解,作為群體最優(yōu)解gBest;

10.從pArchive中選取距群體最優(yōu)解gBest最近的一個(gè)解,作為個(gè)體最優(yōu)解pBest;

11.根據(jù)式(11),由進(jìn)化狀態(tài)、差熵,計(jì)算ω、c1、c2的值;

12.根據(jù)式(9)、式(10)、式(12),更新粒子的速度和位置;}

13.Else if (當(dāng)前位置不可行){ 隨機(jī)調(diào)整粒子位置;}

14.If (gArchive連續(xù)8輪不變){ 算法終止;}

}

15.If (gArchive≠?){從gArchive中隨機(jī)選出一個(gè)解作為映射方案。}

3 仿真結(jié)果與分析

本文分別采用VNE-MOPSO算法與文獻(xiàn)[4]中單目標(biāo)映射VNE-UEPSO算法通過(guò)CloudSim3.0.3軟件平臺(tái)進(jìn)行2組仿實(shí)驗(yàn)。第1組實(shí)驗(yàn)將不同虛擬鏈路帶寬容量下由兩種算法得到的物理網(wǎng)絡(luò)映射成本和能耗進(jìn)行對(duì)比;第2組實(shí)驗(yàn)將虛擬鏈路帶寬容量為600～3 000時(shí)由兩種算法得到的物理網(wǎng)絡(luò)節(jié)點(diǎn)利用率和長(zhǎng)期平均收益進(jìn)行對(duì)比。2組實(shí)驗(yàn)分別對(duì)2 000個(gè)虛擬網(wǎng)絡(luò)請(qǐng)求進(jìn)行測(cè)試。為保證拓?fù)涠鄻有?使用節(jié)點(diǎn)數(shù)量范圍、節(jié)點(diǎn)連通度、資源范圍等為參數(shù)生成隨機(jī)拓?fù)渚W(wǎng)絡(luò)。計(jì)算資源和帶寬資源的相對(duì)權(quán)重比均為1∶1,運(yùn)動(dòng)參數(shù)ω、c1、c2初值分別為0.85、0.7、2.3,能耗參數(shù)Pm、Pb、Pn分別為300、150、15,外部最優(yōu)解集最大容量為5。物理網(wǎng)絡(luò)和虛擬網(wǎng)絡(luò)的具體實(shí)驗(yàn)參數(shù)如表2所示。

表2 不同網(wǎng)絡(luò)的實(shí)驗(yàn)參數(shù)Table 2 Experimental parameters of different networks

由圖1和圖2可以看出,采用VNE-MOPSO算法能減少物理網(wǎng)絡(luò)的映射成本和能耗。在底層網(wǎng)絡(luò)空閑較多時(shí)(虛擬網(wǎng)絡(luò)請(qǐng)求數(shù)量為0～800),采用兩種算法得到的物理網(wǎng)絡(luò)映射成本和能耗差異不大,這是因?yàn)榍捌谖锢砭W(wǎng)絡(luò)資源充足,粒子群算法搜索能力強(qiáng),VNE-MOPSO算法的優(yōu)化效果不明顯。隨著虛擬網(wǎng)絡(luò)請(qǐng)求數(shù)量增多,VNE-MOPSO算法優(yōu)化效果不斷增強(qiáng),最終在帶寬容量為200～1 000和600～3 000下比采用VNE-UEPSO算法分別減少了6.88%、3.63%的映射成本和4.64%、9.81%的能耗。

圖1 不同虛擬鏈路帶寬容量下采用兩種算法得到的物理網(wǎng)絡(luò)映射成本Fig.1 Physical network mapping cost under different virtual link bandwidth capacity using two algorithms

圖2 不同虛擬鏈路帶寬容量下采用兩種算法得到的物理網(wǎng)絡(luò)能耗Fig.2 Physical network energy consumption under different virtual link bandwidth capacity using two algorithms

此外,隨著虛擬鏈路帶寬容量的增大,采用兩種算法得到的物理網(wǎng)絡(luò)映射成本越高,VNE-MOPSO算法對(duì)映射成本的優(yōu)化效果越好。當(dāng)虛擬鏈路帶寬容量為200～1 000時(shí),物理網(wǎng)絡(luò)的能耗比虛擬鏈路帶寬容量為600～3 000時(shí)要高,這是因?yàn)槲锢砭W(wǎng)絡(luò)能耗由已開啟的物理節(jié)點(diǎn)和鏈路數(shù)量、物理節(jié)點(diǎn)負(fù)載情況共同決定,能耗與虛擬鏈路的帶寬容量無(wú)關(guān)。

由圖3可以看出,在不同虛擬鏈路帶寬容量下,采用VNE-MOPSO算法的運(yùn)行時(shí)間比采用VNE-UEPSO算法更少,映射效率也更高。這是因?yàn)閂NE-MOPSO算法具有根據(jù)外部最優(yōu)解集反饋動(dòng)態(tài)調(diào)整粒子群算法運(yùn)動(dòng)參數(shù)的機(jī)制,在迭代過(guò)程中不斷促進(jìn)種群進(jìn)行更加有效地搜索,從而能提高尋找最優(yōu)解的效率。

圖3 不同虛擬鏈路帶寬容量下采用兩種算法得到的運(yùn)行時(shí)間Fig.3 Operation time under different virtual link bandwidth capacity using two algorithms

由圖4和圖5可以看出,隨著運(yùn)行時(shí)間的增加,采用VNE-MOPSO算法得到的物理網(wǎng)絡(luò)節(jié)點(diǎn)利用率和長(zhǎng)期平均收益比采用VNE-UEPSO算法得到的更高。這是因?yàn)閂NE-MOPSO算法以減少物理網(wǎng)絡(luò)的映射成本和能耗為優(yōu)化目標(biāo),在進(jìn)化過(guò)程中兼顧Pareto前端的多樣性和收斂性,節(jié)省物理網(wǎng)絡(luò)資源,并加快映射速度。由圖5還可以看出,在運(yùn)行初期,隨著運(yùn)行時(shí)間的增加,采用兩種算法得到的物理網(wǎng)絡(luò)長(zhǎng)期平均收益均呈現(xiàn)下降趨勢(shì)。這是因?yàn)樵谶\(yùn)行初期底層物理網(wǎng)絡(luò)資源充足,映射效率較高,收益較高;隨著運(yùn)行時(shí)間的增加,底層物理網(wǎng)絡(luò)資源逐漸減少,映射效率降低,收益下降;當(dāng)占用物理資源、釋放物理資源的過(guò)程逐漸達(dá)到平穩(wěn)時(shí),長(zhǎng)期平均收益趨于穩(wěn)定。

圖4 采用不同算法得到的物理網(wǎng)絡(luò)節(jié)點(diǎn)資源利用率隨運(yùn)行時(shí)間變化曲線Fig.4 Resource utilization rate of physical network nodes vs running time curve using different algorithms

圖5 采用不同算法得到的物理網(wǎng)絡(luò)長(zhǎng)期平均收益隨時(shí)間變化曲線Fig.5 Long term average income of physical network nodes vs running time curve using different algorithms

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

本文提出一種基于Pareto熵的多目標(biāo)粒子群優(yōu)化虛擬網(wǎng)絡(luò)映射算法。將Pareto熵多目標(biāo)優(yōu)化模型與粒子群算法相結(jié)合,在保證物理網(wǎng)絡(luò)資源租賃收益的同時(shí)兼顧能耗開銷,根據(jù)外部Pareto解集的更新狀況調(diào)整粒子運(yùn)動(dòng)參數(shù),控制搜索過(guò)程,最終降低映射成本和能耗,同時(shí)實(shí)現(xiàn)良好的長(zhǎng)期平均收益。 仿真結(jié)果表明,該算法在收益、能耗和求解效率方面較單目標(biāo)優(yōu)化算法均有所提升。下一步將在本文算法的基礎(chǔ)上引入虛擬網(wǎng)絡(luò)服務(wù)質(zhì)量作為額外參數(shù),以實(shí)現(xiàn)更多目標(biāo)的同時(shí)優(yōu)化。