应用粒子群优化的绿色虚拟网络映射算法

2016-11-20曲桦樊斌郭涯王力赵季红

电信科学 2016年1期

关键词：底层复杂度链路

曲桦，樊斌，郭涯，王力，赵季红，2

(1.西安交通大学电子与信息工程学院，陕西西安 710049;2.西安邮电大学通信工程系，陕西西安 710061)

应用粒子群优化的绿色虚拟网络映射算法

曲桦1，樊斌1，郭涯1，王力1，赵季红1，2

(1.西安交通大学电子与信息工程学院，陕西西安 710049;2.西安邮电大学通信工程系，陕西西安 710061)

绿色网络是近年来网络技术研究的热点，以节能为优化目标的虚拟网络映射算法成为基于网络虚拟化技术中资源分配研究的重点。提出了应用粒子群优化的绿色虚拟网络映射算法，重定义粒子群优化算法中的参数和粒子进化行为，以关闭底层网络节点和链路数量最多为适应度函数，在较低的算法复杂度条件下，获得绿色虚拟网络映射的最优解。仿真结果表明，与对比算法相比，静态环境下所提算法的运行时间大幅度降低;动态环境下所提算法的节点关闭率、链路关闭率、虚拟网络请求接受率均有所提升，算法运行时间也大大缩短。

网络虚拟化;绿色网络;虚拟网络映射算法;粒子群优化

1 引言

现有的网络设计存在着过度供应的理念，为了保证高峰期网络的性能，网络的资源供应都是依照高峰期的资源消耗而设计［1］。大型ISP骨干网的平均链路利用率为30%～40%，数据中心服务器的平均利用率为 11%～50%［2］，导致信息通信行业(ICT)能耗逐年增加。过低的利用率造成了巨大的能源浪费，绿色网络成为网络技术研究的热点［3，4］。

网络虚拟化技术能够在物理网络中共享多个相互隔离的虚拟网络［5］，实现网络资源共享，是提高网络能效、实现绿色网络的有效途径。而虚拟网络映射是实例化虚拟网络、实现虚拟网络资源分配的重要手段［6］。因此，绿色虚拟网络映射算法成为网络技术研究的重点。

目前，对虚拟网络映射的研究基本都是从运营商的角度出发，虚拟网络映射算法多为基于代价的，即以最小化底层资源代价为虚拟网络映射目标，以此获得更多的底层物理资源，进而提高虚拟网络接收率与系统收益［2］，少有考虑节能问题，与绿色网络的概念相悖。

针对该现象，参考文献［7］对设备能量分布进行评估，考虑到机箱能耗比路由能耗低的特点，提出流量巩固的节能方法，但有较大局限性，只适合负载敏感的设备;参考文献［8］提出了基于能量感知的虚拟网络映射算法，建立混合整数规划模型，但其时间复杂度呈指数增长，难以适应大规模网络基础设施的虚拟网络映射。为降低时间复杂度，不同的研究人员采取了不同的方式，参考文献［2］通过建立一定的虚拟网络映射字典库进行，虽然有一定效果，但网络映射仍然是静态的模型，与实际网络具有的寿命特性不符。而参考文献［9］在云数据中心中应用蚁群优化算法来求解虚拟网络节能映射问题，在建立虚拟网络映射模型时参数多，算法复杂度比较高。参考文献［10］提出可以通过启发式方法对虚拟网络映射进行重配置，达到降低能耗的目的，并未进行深入探究。针对以上各算法的不足:运行速度慢，效率低;虚拟网络映射是静态的过程;虚拟网络的到达时间和存活时间与实际不符等，本文对算法进行了更深入的研究和改进。

本文提出了一种应用粒子群优化的绿色虚拟网络映射(GVNE-PSO)算法。该算法首先重定义了粒子群优化算法中的参数和粒子进化行为，将虚拟网络映射中的映射方案编码为粒子群中粒子的位置;其次，以关闭底层网络节点和链路数量最多为适应度函数;最后，每个粒子都在迭代的过程中，根据个体最优位置信息和全局最优位置信息来调整自己的运动趋势，求得绿色虚拟网络映射的全局最优解。

2 绿色虚拟网络映射模型

虚拟网络 (virtual network，VN)拓扑可以用带权值的无向图 GVk=(NVk，LVk)表示，其中 NVk和 LVk分别是虚拟节点(virtual node)和虚拟链路(virtual link)的集合［6］。对于任意虚拟节点nVk，cpu(nVk)表示第k个虚拟节点的需求，对于任意链路(ik，jk)，LRBW(ik，jk)表示其所需的带宽资源。同理，底层网络(substrate network，SN)拓扑用带权值的无向图GS=(NS，LS)来表示，其中，NS和 LS分别是底层节点(substrate node)和底层链路(substrate link)的集合［6］。对于任意底层节点，表示底层网络能够提供的最大容量，对于任意链路(i，j)，LDBW(i，j)表示底层网络链路能够提供的最大带宽容量。MaxDegree表示底层节点最大的节点度数。NOi和LOi，j分别表示映射物理节点和物理链路的状态，为0表示不活动，为 1 表示活动［8］。

图1描述了一个虚拟网络请求的实例，图1(a)表示一个虚拟网络请求实例，节点附近矩形框中数值代表节点请求的CPU资源，链路附近的数字表示链路所需的带宽资源，图1(b)表示映射前的底层网络拓扑，图1(c)表示映射后的底层网络拓扑。实例中节点的映射方案为｛a→A，b→E，c→G｝，链路的映射方案为｛(a，b)→(A，D，E)，(a，c)→(A，D，F，G)，(b，c)→(E，G)｝。虚拟网络请求中的节点可以映射到同一个底层节点上，但同一虚拟网络请求中节点间如果有链路，则不能映射到同一节点上。

图1 虚拟网络映射实例

2.1 GVNE-PSO变量

xiik表示虚拟节点ik是否成功映射到物理节点i上，若成功取值为1，否则为0;αi表示映射后物理节点i的状态，若活动则取 1，否则取 0;ρ(i，j)表示映射后物理链路(i，j)的状态，若活动则取 1，否则取 0。i′，j′f(i，j)表示物理节点 i′，j′通过链路 (i，j)的带宽资源表示映射理节点(i，j)上的虚拟链路带宽需求［8］。

2.2 目标函数

虚拟网络映射请求资源不变，但不同的映射方案消耗的底层资源会发生变化，使能够关闭的最大节点和链路发生变化，将式(1)作为模型的目标函数:

2.3 约束条件

2.3.1 连接性约束

(1)源流

(2)目标流

(3)输入输出流

2.3.2 节点和链路约束

(1)CPU和链路带宽容量限制

(2)活动底层节点

连接性约束是网络流相关限制，确保在虚拟网络映射的底层网络中，网络流只能在源节点产生，在目的节点流入，而中间节点只负责转发，没有净网络流的输入和输出［1］;节点和链路约束分别确保所有虚拟节点的CPU请求不能超过其底层节点的CPU容量，每条虚拟链路的带宽请求不能超过底层链路的带宽资源;活动底层节点指出了映射后链路状态和节点状态之间的关系，若一个节点是活动的，那么至少一条入链路或出链路是活动的［8］(MaxDegree表示节点度数，是指与该阶段相关联的边的条数)。

3 应用粒子群优化的绿色虚拟网络映射算法

3.1 粒子群优化算法

粒子群优化算法是一种进化计算方法。由Eberhart和Kennedy在1995年提出，源于对鸟群捕食行为的研究。它是一种随机全局搜索优化技术，通过群体中各粒子间自身搜索和相互通信，发现复杂搜索空间中的最优区域。在该算法中，每个粒子以一定的速度在其解空间范围内向其全局历史最优位置Xgb和自身历史最优位置Xpb聚集，实现对解位置的进化，最终寻到最优解的位置。其速度和位置更新计算式如下:

其中，Xi为粒子当前的位置向量，Vi为粒子当前的速度向量。w表示粒子的惯性权重，表示粒子保持现有速度的惯性，r1和r2为0～1的随机数，c1和c2为学习因子，代表粒子分别向局部最优位置和全局最优位置移动的趋势［11］。

r1和 r2设置为0～1的随机数，c1和 c2设置为 0.25时，粒子群优化算法是收敛的，粒子速度或者不断减少到0，或者一直以初始化速度迭代到算法结束。c1和c2值设置为2.05(权衡得出的数值)，既能保证粒子向局部最优解和全局最优解迭代的速度，又能保证收敛速度［12］。

3.2 粒子群优化算法相关参数和操作的重定义

由于粒子群算法最初主要解决连续域内多目标函数的最优化问题，而本文中的虚拟网络映射方案是离散域内的最优化问题，为了解决该问题，需要对粒子群算法中的相关参数和操作进行重定义，本文对粒子群中的位置向量、速度向量、全局和局部最优解进行重定义。

定义1(粒子的位置向量)粒子的位置向量定义为］，M 表示虚拟网络中节点的个数，i表示虚拟网络映射的第i种方案。代表虚拟网络中第k个虚拟节点在映射方案中选择的底层候选节点的编号［13］。映射节点与候选节点编号的对应］，其中，N表示底层网络节点的个数

定义2(粒子的速度向量)粒子的速度向量定义为用来牵引粒子向更优的解方案映射，以便向最优的方案聚集。的形式同，其中每个元素数值设定在最大值Vmax=4和最小值Vmin=-4之间，最大最小速度±4是粒子群算法中速度的常设数值，可使尽可能多的速度值被考虑，同时保证其收敛速度。然后进行归一化(除以4)。越接近Vmax或Vmin的数值，表示目前粒子位置与局部最优和全局最优位置差异越大，则会指导当前映射位置进行调整;越接近0的数值，表示当前粒子位置与局部最优和全局最优位置差异较小，则越会保持当前映射位置。如果存在差异值最大且相同时，则将该值与其前后值取绝对值进行求和后平均，选择较大的。例如，若位置参数为，而归一化后速度参数为其中有两个 1，因此对求平均之后，前面为0.5，后面为，因此对其则调整后

定义 3(减法“-”)定义为比较映射的差异性，两种映射方案在同一维上具有相同的值，则差值为0，否则差值为1。如有5个虚拟节点、20个物理节点，两种映射方案 X1=［1，4，3，7，12］，X2=［1，5，4，7，20］，则差异 X1-X2=［0，1，1，0，1］。

定义4(粒子的全局最优解)定义为所有粒子的适应度函数fitness自映射开始到当前时间的最小值。

定义5(粒子的局部最优解)定义为每个粒子的适应度函数fitness自映射开始到当前时间的最小值。

本文中，c1和c2设置为 2.05。

3.3 应用粒子群优化的虚拟网络映射算法

GVNE-PSO算法的适应度函数设为映射中能够关闭底层节点和链路和的最大值，函数的表达式f(X)如式(1)所示。静态时，虚拟网络请求没有寿命，在同一时间内，全部映射;动态时虚拟网络按照泊松分布依次映射。

3.3.1 映射路径的选择

映射路径的选择分为两步:选择满足带宽约束条件的链路，组成集合;在集合中选择利用改进迪杰斯特拉算法选择路径跳数最小且资源充足的链路。

为了充分利用底层资源，并且增加映射后底层链路的均衡性，虚拟网络链路映射到底层链路满足以下条件:满足链路的约束条件;在链路带宽充足的条件下，尽可能选择路径跳数较少的链路。满足这些条件，将底层链路剩余带宽作为链路权值是不合理的，会导致所有的映射链路选择剩余带宽较少的，而非资源最充足的，从而造成底层网络资源均衡性越来越差，不利于之后虚拟网络的映射。因此必须对迪杰斯特拉算法中原有链路权值进行重定义:底层链路剩余带宽的倒数作为权值，在选择的过程中选择权值较小的。

为了说明重定义的优点，以图1中节点映射｛a→A，b→E｝为例。对比底层节点A到E间3种路径选择方案A→B→E、A→B→D→E和 A→D→E，第一、三种方案路径跳数都为2，第二种路径跳数为3，其倒数和为第二种方案与第一种方案相比，虽然路径跳数更多，但其链路资源更丰富，为了保证底层链路均衡性，算法倾向于选择第二种;而第三种方案与第二种方案对比，当资源和相同时，算法更倾向于选择跳数较少的链路。

3.3.2 映射方案的优化

将截至当前时刻，所有虚拟网络映射的不同方案视作不同粒子，映射方案的优化即粒子的优化。计算满足约束条件的方案的适应度函数f(X)值，若不满足约束条件，f(X)的值视作无穷大，本文将其设置为20 000。

GVNE-PSO算法分6个步骤，分别如下。

(1)设置粒子群的种群规模为N，算法最大可迭代的次数为MG，初始化粒子的位置参数Xi，速度参数 Vi为随机值。

(2)计算粒子的当前的适应度函数f(Xi)，初步得到个体最优初始位置Xpb和全局最优初始位置Xgb。

(3)对于满足式(5)和式(6)的粒子分别进行位置更新和速度更新，对于不满足约束条件的粒子进行重映射，生成其位置参数和速度参数。

(4)对∀Xi，判断f(Xi)的值，若连续几次不再发生变化，则执行步骤(6)，若 f(Xi)＜f(Xpb)，则 Xpb=Xi;若 f(Xpb)＜f(Xgb)，则Xgb=Xpb。

(5)检查算法的迭代次数，如果小于MG，则执行步骤(3)，否则执行步骤(6)。

(6)输出最优的虚拟网络映射方案以及此时的适应度函数值。

3.3.3 GVNE-PSO时间复杂度分析

虚拟网络映射中，映射后寻找节点和链路最优解的问题是NP难问题。对于PSO算法，其每一次迭代中粒子的数量不变，假设第 i步迭代中粒子的数量为 Ni，其中i=1，2，…，m，m表示最大的迭代次数，因此有N1=N2=…=N3=N。假设每个粒子每一次迭代需要的时间运算为TT，则可以得出PSO算法进行优化所需要总的时间为NmTT。粒子的最大迭代次数和粒子的数量不变，因此时间复杂度只与每次的迭代时间TT有关。而TT∝M(M表示截至当前时刻虚拟网络个数)，这是由于GVNE-PSO算法的优化过程是靠粒子间相互作用完成的，增加的虚拟网络只是随机映射的，从而大大降低了虚拟网络映射问题的时间复杂度。而参考文献［8］中VNE-EA使用线性规划的方法，每增加一个虚拟网络，均需要遍历底层所有的节点和链路，筛选出最优解，时间复杂度随着节点和链路的增加呈指数形式增长。因此相比GVNE-PSO，VNE-EA的时间复杂度更高。

4 实验性能评估和分析

为了验证GVNE-PSO的有效性，将所提算法在动态和静态时分别与参考文献［8］中算法进行比较。

4.1 仿真环境设置

在GVNE-PSO的仿真实现中，网络参数的设置如下:底层网络拓扑和虚拟网络拓扑分别设置为15个和5个节点，节点间均以0.25的概率相连。虚拟网络请求的个数设置为30个。底层网络节点的CPU资源和链路的带宽资源设置为0～100的随机均匀分布函数。而虚拟网络请求节点的CPU资源和链路的带宽资源在20～90分为8个等级，对应负载等级Load=0.2～0.9。

粒子群参数设置如下:粒子群种群规模设置为30个，最大迭代次数设置为300次，粒子的初始位置由首次映射成功的位置随机确定，粒子的速度设置-4～4。

4.2 算法评价指标

仿真采用随机化实验，在每个网络映射流程中随机产生30个虚拟网络，静态时同时映射到底层网络上，动态时映射间隔时间按照泊松分布逐一映射到底层网络上。算法从以下4个方面进行评价。

(1)虚拟网络映射后可关闭节点的个数(不活动节点的个数)

(2)虚拟网络映射后可关闭链路的条数(不活动链路的条数)

(3)每个虚拟网络映射所需要时间

其中，t表示算法运行的时间。

(4)虚拟网络请求接受率

其中，分子表示从0到当前时刻T内，成功映射的网络虚拟个数;而分母表示从0到当前时刻T内总共映射的虚拟网络个数。

4.3 仿真结果分析

针对参考文献［8］中的虚拟网络映射请求是静态过程，虚拟网络没有到达时间和寿命，本文首先将虚拟网络映射请求设置为静态过程，然后再设置为动态过程，动态时，虚拟网络的到达时间服从λ=20的泊松分布，持续时间服从具有寿命分布特性的λ=100的指数分布，仿真得到的结果对比如下。

图2 虚拟网络映射中可关闭的节点率对比

图2为虚拟网络映射过程中关闭的节点数对比。在30个虚拟网络映射后，静态时，GVNE-PSO(S)较VNE-EA，在关闭节点率方面要低一些，平均在12.5%，当负载较低时，两者相差比较大，随着负载的升高，差距逐渐变小。动态时，GVNE-PSO(D)要比VNE-EA可关闭的节点率高，平均高出50%以上，在高负载(Load=0.5～0.9)时更加明显，能够节省更多的能源。

图3为虚拟网络映射后可关闭的链路率对比。静态时，GVNE-PSO相对VNE-EA约低15%。动态时，GVNE-PSO较VNE-EA在关闭的底层网络链路率平均高出50%以上，负载较低时两者之间的差距较大，负载较高时差距较小。

对不活动节点和不活动链路曲线的分析:GVNE-PSO是在底层网络中用群体智能的方法有目的地选择出最优方案，而非遍历所有的节点和链路，这是由算法的特性所决定的，因此得到的最优解在能够关闭的最多链路和节点较VNE-EA少。随着负载升高，两种算法节点不活动率的差距减小，这是由于虚拟网络映射方案的解空间变小，得到最优解的精度会增加。虚拟网络映射请求为动态时，虚拟网络请求满足寿命分布函数，其节点和链路的不活动率会更高。在负载较高时，这种现象会更加明显，甚至还会有些许回升现象，这是由于后期虚拟网络请求负载升高，虚拟请求接受率会下降，而前期已映射的虚拟网络仍然会离开，这就导致节点和链路资源的释放出现回升。

图4为虚拟网络请求接受率的对比。低负载时，动态和静态情况下，GVNE-PSO均高于VNE-EA。负载较低时相差不多，负载较高时，GVNE-PSO请求接受率下降得更快，这是由于GVNE-PSO算法底层网络中的节点和链路均衡性相对较差，在负载较低时，节点和链路的不活动率低，必然导致请求接受率相对较高。动态时，由于有虚拟网络的离开，会释放一些节点和链路，导致请求接受率升高。由此，动态过程相对于其他两个算法过程都好。

图4 虚拟网络映射后虚拟请求接受率对比

图5为GVNE-PSO和VNE-EA在时间复杂度方面的比较，由于随着虚拟网络请求数目的增加，GVNE-PSO时间复杂度呈线性增加，而VNE-EA由于需要遍历底层所有节点和链路，时间复杂度增加更快，因此只需要模拟一个虚拟网络映射即可。图5中的曲线模拟的是一个虚拟网络请求寻找最优解的时间，可见，GVNE-PSO在时间复杂度方面的性能非常优越，求解的时间也相对比较稳定，有利于虚拟网络映射寻求合适资源，体现了粒子群优化算法在求解组合优化问题上速度快、效率高等特点。随着负载的升高，时间复杂度呈现下降趋势，这是由于负载升高时，请求接受率会下降。寻求最优解的虚拟网络数目减少，降低了求解时间。另外，动态的GVNE-PSO过程相对于静态的GVNE-PSO算法较高。

图5 虚拟网络映射中时间复杂度的对比

5 结束语

本文以降低虚拟网络映射中的能源消耗为目标，在底层网络不支持节点分割和路径分裂的前提下，分别建立了静态的虚拟网络映射模型和具有流程概念的动态虚拟网络映射模型，并在粒子群优化算法的基础上，提出了改进的虚拟网映射算法。该算法重新对粒子群优化算法中的参数和操作进行了重定义。模拟实验结果表明，无论是动态还是静态，该算法都可以大幅降低时间复杂度，并在动态时有效提高节点和链路的关闭率。

［1］王文鼐，张寅翔.成本与能效优化的虚拟网络算法研究［D］.南京:南京邮电大学，2013:13-25.WANG W N，ZHANG Y X.Study on optimal virtual network embedding algorithm for cost and energy efficiency［D］.Nanjing:Nanjing University of Posts and Telecommunications，2013:13-25.

［2］陈晓华，李春芝，陈良育，等.主动休眠节点链路的高效节能虚拟网络映射［J］.软件学报，2014(7):1416-1419.CHEN X H，LI C Z，CHEN L Y，et al.Energy efficient virtual network embedding based on actively hibernating substrate nodes and links［J］.Journal of Software，2014(7):1416-1419.

［3］LIN C，TIAN Y，YAO M.Green network and green evaluation:mechanism，modeling and evaluation ［J］.Chinese Journal of Computers，2011，34(4):593-612.

［4］YE K J，WU Z H，JIANG X H，et al.Power management of virtualized cloud computing platform ［J］.Chinese Journal of Computers，2012(5):1262-1285.

［5］FISCHER A，BOTERO J F，BECK M T，et al.Virtual network embedding:a survey ［J］.IEEE Communications Surveys&Tutorials，2013，15(4):1888-1906.

［6］杨宇，陈山枝.网络虚拟化资源管理及虚拟网络应用研究［D］.北京:北京邮电大学，2013:25-45.YANG Y，CHEN S Z.Research on the resource management for network virtualization and virtualnetwork application ［D］.Beijing:Beijing University of Posts and Telecommunications，2013:25-45.

［7］FISCHER A，BOTERO J F，DUELLI M，et al.ALEVIN-a framework to develop，compare，and analyze virtual network embedding algorithms ［J］.Electronic Communications of the EASST，2011(37):1-12.

［8］BOTERO J F，HESSELBACH X，DUELLI M，et al.Energy efficient virtual network embedding ［J］.IEEE Communications Letters，2012，16(5):756-759.

［9］刘光远，苏森.面向底层单节点失效的轻量级可靠虚拟网络映射算法［J］.电子与信息学报，2013(11):2644-2650.LIU G Y，SU S.Less stringent reliable virtual network mapping algorithm for substrate single node failure ［J］.Journal of Electronics and Information Technology，2013(11):2644-2650.

［10］程祥，张忠宝，苏森，等. 虚拟网络映射问题研究综述［J］.通信学报，2011，32(10):143-149.CHENG X，ZHANG Z B，Su S，et al.Survey of virtual network embedding problem［J］.Journal on Communication，2011，32(10):143-149.

［11］段海滨，张祥银，徐春芳.仿生智能计算［M］.北京:科学出版社，2011.DUAN H B，ZHANG X Y，XU C F.Bio-Inspired Computing［M］.Beijing:Science Press，2011.

［12］FU Y G，ZHOU C P，DING M Y.Convergence analysis of standard particle swarm optimization algorithm ［J］.Mathematica Application，2011，24(1):187-194.

［13］程祥，张忠宝，苏森，等.基于粒子群优化的虚拟网络映射算法［J］.电子学报，2011，39(10):2240-2244.CHEN X，ZHANG Z B，SU S，et al.Virtual network embedding based on particle swarm optimization ［J］.Chinese Journal of Electronics，2011，39(10):2240-2244.

Green virtual network embedding algorithm based on particle swarm optimization

QU Hua1，FAN Bin1，GUO Ya1，WANG Li1，ZHAO Jihong1，2
1.School of Electronics and Information Engineering，Xi'an Jiaotong University，Xi'an 710049，China 2.Department of Communication Engineering，Xi'an University of Posts and Telecommunications，Xi'an 710061，China

Green network is a hotspot in network research recent years，virtual network embedding (VNE)algorithm which focuses on saving energy，becomes very important in resource allocation in the network virtualization.A green VNE algorithm which applies swarm particle optimization (GVNE-PSO)was proposed，the evolution behaviors and parameters of each particle was redefined，and the number of nodes and links that could be switched off as the fitness function were considered，the optimum solution of green VNE in a low time complexity was achieved.The results show that compared to the exiting algorithm，it greatly reduced the time complexity offline，when online，it also raised the rate of virtual network acceptance，and the same with nodes and links that can be switched off，what's more，the performance period are shorter.

network virtualization，green network，virtual network embedding algorithm，particle swarm

s:The National Natural Science Foundation of China(No.61371087，No.61371087)，The National High Technology Research and Development Program of China(863 Program)(No.2015AA015702)，Jiangsu Future Networks Innovation Institute “Prospective Research Project on Future Networks”(No.BY2013095-1-14)

TP393

10.11959/j.issn.1000-0801.2016002

2015-07-24;

2015-12-15

国家自然科学基金资助项目(No.61531013，No.61371087);国家高技术研究发展计划(“863”计划)基金资助项目(No.2015AA015702);江苏省未来网络创新研究院“未来网络前瞻性研究项目”(No.BY2013095-1-14)

曲桦(1961-)，男，博士，西安交通大学教授、博士生导师，主要研究方向为现代通信网、计算机网络体系结构。