基于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解集的更新状况调整粒子运动参数,控制搜索过程,最终降低映射成本和能耗,同时实现良好的长期平均收益。 仿真结果表明,该算法在收益、能耗和求解效率方面较单目标优化算法均有所提升。下一步将在本文算法的基础上引入虚拟网络服务质量作为额外参数,以实现更多目标的同时优化。