基于Pareto熵的多目標虛擬網絡映射算法

劉 穎,王 聰,苑 迎,蔣國佳,劉珂禎,王翠榮

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

0 概述

自20世紀60年代以來,互聯網得到飛速發展,已成為現代社會的重要基礎設施。目前中國網民數量已達到8.02億[1],用戶數量、接入網絡應用軟件數量的激增,對互聯網性能提出更高的要求。現有的互聯網架構在服務質量、響應速度等方面很難滿足這些要求，在某種程度上呈現出“僵化”現象。為此，研究人員提出網絡虛擬化技術，通過應用現有的互聯網架構，將底層物理網絡的硬件和軟件資源進行整合，提高了網絡資源利用率。該技術在未來互聯網發展中極具應用前景[2]。虛擬網絡映射是網絡虛擬化技術的一個重要部分,其可在滿足節點和鏈路資源約束的基礎上將虛擬網絡映射到物理網絡,從而實現底層資源的高效利用[3]。

在虛擬網絡映射問題的求解過程中,元啟發式算法應用廣泛[4]。文獻[4]采用一種從大粒子到大粒子、小粒子到小粒子的粒子位置初始化策略,以達到更好的算法收斂性和底層網絡負載平衡。文獻[5]采用多條路徑以提供更好的鏈路映射方案,并將粒子群優化算法和遺傳算法相結合,在不斷迭代的基礎上尋找映射方案。文獻[6]針對網絡拓撲圖分解生成的環和樹結構,提出一種基于多元映射算法的改進蟻群算法。文獻[7]提出拓撲預配置機制,在映射前先修剪虛擬拓撲以提高映射的接受率。文獻[8]提出一種面向鏈路映射的蟻群系統算法,根據相連的鏈路資源屬性對節點進行排序,并在蟻群系統中引入具有連接感知能力的鏈路啟發式信息,有效地節省了帶寬。

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

本文從多目標優化角度出發,提出一種基于Pareto熵的虛擬網絡映射VEN-MOPSO算法。使用目標空間變換方法[16]計算當前最優解集的Pareto熵,并以每次迭代后最優解集的變化引發的差熵為依據評估種群的進化狀態,進而設計動態自適應的粒子運動參數策略,控制粒子群搜索的過程,以提高解的優化程度。

1 多目標虛擬網絡映射問題

1.1 虛擬網絡映射問題描述

底層網絡(Substrate Network,SN)用加權無向圖表示為:

(1)

虛擬網絡(Virtual Network,VN)用加權無向圖表示為:

(2)

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

1.2 底層網絡能耗

映射過程能耗包括以下兩方面:

1)節點能耗

網絡節點即服務器節點,網絡節點能耗與該節點承載的虛擬網絡節點總和成正比[13],第i個底層節點能耗定義為:

(3)

其中,Pb為底層物理節點能耗的基本值,Pm為底層物理節點能耗的最大值,u為處理器利用率。

2)鏈路能耗

在網絡虛擬化環境中具有減負引擎裝置,因而網絡設備對流量負荷的能耗不敏感[18]。物理鏈路能耗通常被視為常量[19],第j條鏈路能耗定義為:

(4)

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

1.3 多目標優化虛擬網絡映射問題建模

虛擬網絡映射優化目標為映射成本和能耗最小化。用戶的每個虛擬網絡請求映射模型為:

(5)

其中,f1為網絡資源開銷,cpu(nv)為虛擬節點nv所需的計算能力值,bw(lv)為虛擬鏈路lv所需的帶寬能力值,α為計算資源相對權重,β為帶寬資源相對權重,且α+β=1,φlv為用來判斷lv是否被映射到物理鏈路上的二進制變量,f2為映射能耗,ti為節點i開啟的時間,tj為鏈路j開啟的時間。

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

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

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

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

(6)

其中,pS為映射后物理節點和物理鏈路集合,ni為目標物理節點,nv為映射的虛擬節點,ni的可用節點資源不能小于nv所請求的節點資源,lV為虛擬鏈路,pS為虛擬鏈路所映射的物理路徑,lj為虛擬鏈路所映射物理路徑的每條物理鏈路,lj的空閑帶寬不能小于lV所請求的帶寬。

2 VNE-MOPSO算法

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

2.1 Pareto最優相關定義

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

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

定義3所有Pareto最優解對應的目標函數值所形成的區域PF={F(x*)|x*)∈PS}稱為Pareto前端、Pareto前沿或Pareto均衡面[16]。

2.2 Pareto熵多目標優化模型及進化狀態

Pareto熵多目標優化模型以兩次迭代的Pareto差熵為優化依據。首先將存儲在外部最優解集中的多維Pareto解以目標空間轉換方式映射到二維平面,然后求出每個Pareto解的平行格坐標以及近似Pareto前端的Pareto熵。當外部最優解集更新時,會導致近似Pareto前端的Pareto熵發生變化,即產生差熵。差熵是控制優化過程的有效信息。

將多維Pareto解按照平行坐標方式轉化到二維平面中,其映射的整數值坐標即為平行格坐標[16],計算公式為:

(7)

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

(8)

其中,Cellk,m(t)為Pareto解的格坐標分量落在平行格坐標系統第k行第m列方格的個數。

當外部最優解集容量已滿時,再次更新需評估解的個體密度。根據式(7),將外部最優解集的成員映射到平行格坐標系統后,任意解的個體密度[16]的計算公式為:

(9)

(10)

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

隨著粒子群不斷搜索到新解,外部最優解集不斷更新。VNE-PSO算法在每次迭代中的進化狀態包括以下3種:

1)停滯狀態:VNE-PSO算法得到的新解被外部最優解集拒絕。

2)多樣化狀態:VNE-PSO算法得到的新解取代外部最優解集中質量較差的舊解。

3)收斂狀態:在目標空間中VNE-PSO算法產生的Pareto前端向真實的Pareto前端靠近。

2.3 外部最優解集更新算法

外部最優解集的更新過程包括5種情形,各種情形對應的進化狀態和差熵如表1所示,其中M為優化目標個數,K為外部最優解集最大容量。

表1 外部最優解集更新過程分析Table 1 Updating process analysis of external optimal solution set

根據上述5種情形可得出外部最優解集更新算法如下:

算法1外部最優解集更新算法

輸入

待更新的外部最優解集A

外部最優解集的最大容量K

進化算法獲得的新解P

輸出

更新后的外部最優解集A′

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

差熵ΔEntropy

1.If (A=?){

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

ReturnA′,state,ΔEntropy;} /* 情形 I:外部最優解集為空集,收斂狀態*/

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

state=0;ΔEntropy=0;

ReturnA,state,ΔEntropy;} /* 情形 II:新解被舊解占優,停滯狀態 */

3.If (對任意ai∈A,ai被P占優) {

被P占優的舊解個數記為r,當前A的成員個數記為|A|,首先令A=A/{ai}。

Else if (1

4.If (|A|

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

Return A′,state,ΔEntropy;} /* 情形 III:新解占優舊解,收斂狀態*/

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

6.令 B=A∪{P},對B中每一個成員bi∈B,評估bi的個體密度。

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

8.If (P==bmax) {

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

Return A′,state,ΔEntropy;} /* 情形 IV:新解質量最差,停滯狀態*/

9.Else {

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

}

2.4 粒子群優化算法

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

(11)

Xi+1=Xi+Vi+1

(12)

其中,ω為慣性權重,c1為學習權重,c2為群體權重,且ω、c1、c2均大于0,位置向量pBesti為個體最優解,位置向量gBesti為整個群體的全局最優解。

2.5 自適應粒子運動參數策略

為了更好地控制進化過程,需要持續從進化環境中獲取實時反饋信息,可通過調整粒子運動參數ω、c1、c2調控搜索趨向。將進化狀態和差熵作為運動參數的因變量:

(13)

(14)

(15)

其中,Lenω為ω的區間長度,Lenc1為c1的區間長度,Lenc2為c2的區間長度,按照文獻[20],ω、c1和c2的取值范圍分別為[0.4,0.9]、[0.5,2.5]和[0.5,2.5],即區間長度分別為0.5、2.0和2.0。

2.6 VNE-MOPSO算法整體流程

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

(16)

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

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

算法2基于Pareto熵的虛擬網絡映射算法(VNE-MOPSO)

輸入虛擬網絡Gv,物理網絡Gs

輸出映射方案 solution

1.獲得Gs中實時空閑資源的節點隊列和鏈路隊列;

2.對于群體中的每個粒子,初始化其位置。

3.初始化令全局外部最優解集gArchive=?,令個體外部最優解集pArchive=?;

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

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

6.用最短路徑方式得出映射方案,計算相應的目標函數值f1、f2;

7.對每個粒子調用算法1,更新gArchive,保存此時的進化狀態、差熵;

8.對每個粒子調用算法1,更新pArchive;

9.從gArchive中隨機地選取一個解,作為群體最優解gBest;

10.從pArchive中選取距群體最優解gBest最近的一個解,作為個體最優解pBest;

11.根據式(11),由進化狀態、差熵,計算ω、c1、c2的值;

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

13.Else if (當前位置不可行){ 隨機調整粒子位置;}

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

}

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

3 仿真結果與分析

本文分別采用VNE-MOPSO算法與文獻[4]中單目標映射VNE-UEPSO算法通過CloudSim3.0.3軟件平臺進行2組仿實驗。第1組實驗將不同虛擬鏈路帶寬容量下由兩種算法得到的物理網絡映射成本和能耗進行對比;第2組實驗將虛擬鏈路帶寬容量為600～3 000時由兩種算法得到的物理網絡節點利用率和長期平均收益進行對比。2組實驗分別對2 000個虛擬網絡請求進行測試。為保證拓撲多樣性,使用節點數量范圍、節點連通度、資源范圍等為參數生成隨機拓撲網絡。計算資源和帶寬資源的相對權重比均為1∶1,運動參數ω、c1、c2初值分別為0.85、0.7、2.3,能耗參數Pm、Pb、Pn分別為300、150、15,外部最優解集最大容量為5。物理網絡和虛擬網絡的具體實驗參數如表2所示。

表2 不同網絡的實驗參數Table 2 Experimental parameters of different networks

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

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

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

此外,隨著虛擬鏈路帶寬容量的增大,采用兩種算法得到的物理網絡映射成本越高,VNE-MOPSO算法對映射成本的優化效果越好。當虛擬鏈路帶寬容量為200～1 000時,物理網絡的能耗比虛擬鏈路帶寬容量為600～3 000時要高,這是因為物理網絡能耗由已開啟的物理節點和鏈路數量、物理節點負載情況共同決定,能耗與虛擬鏈路的帶寬容量無關。

由圖3可以看出,在不同虛擬鏈路帶寬容量下,采用VNE-MOPSO算法的運行時間比采用VNE-UEPSO算法更少,映射效率也更高。這是因為VNE-MOPSO算法具有根據外部最優解集反饋動態調整粒子群算法運動參數的機制,在迭代過程中不斷促進種群進行更加有效地搜索,從而能提高尋找最優解的效率。

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

由圖4和圖5可以看出,隨著運行時間的增加,采用VNE-MOPSO算法得到的物理網絡節點利用率和長期平均收益比采用VNE-UEPSO算法得到的更高。這是因為VNE-MOPSO算法以減少物理網絡的映射成本和能耗為優化目標,在進化過程中兼顧Pareto前端的多樣性和收斂性,節省物理網絡資源,并加快映射速度。由圖5還可以看出,在運行初期,隨著運行時間的增加,采用兩種算法得到的物理網絡長期平均收益均呈現下降趨勢。這是因為在運行初期底層物理網絡資源充足,映射效率較高,收益較高;隨著運行時間的增加,底層物理網絡資源逐漸減少,映射效率降低,收益下降;當占用物理資源、釋放物理資源的過程逐漸達到平穩時,長期平均收益趨于穩定。

圖4 采用不同算法得到的物理網絡節點資源利用率隨運行時間變化曲線Fig.4 Resource utilization rate of physical network nodes vs running time curve using different algorithms

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

4 結束語

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