改进的粒子群算法在虚拟网映射中的应用*

2014-09-13胡颖，庄雷

计算机工程与科学 2014年11期

关键词：花费链路调整

胡颖，庄雷

(郑州大学信息工程学院，河南郑州 450000)

改进的粒子群算法在虚拟网映射中的应用*

胡颖，庄雷

(郑州大学信息工程学院，河南郑州 450000)

应用粒子群算法解决虚拟网映射问题，可以大大减少网络资源的消耗，却也容易出现早熟的现象。通过增加随机因素、沿原方向飞行操作和改变原历史因素对搜索过程的指导等方式，既保留了历史因素对搜索的指导，又在此基础上加大了搜索范围，一定程度上减少了早熟收敛带来的问题。最终实验结果表明，改进的粒子群算法能够应用于虚拟网映射，和原粒子群算法相比，能够更有效减少资源消耗。

虚拟网映射；早熟收敛；粒子群算法

1 引言

虚拟网是公认解决网络僵化问题的较有前途的体系结构[1～5]。在虚拟网中较有挑战性的操作便是虚拟网映射操作，即如何将虚拟网络需求映射到物理网络上。

粒子群算法是一种仿生随机搜索算法[6]，其特点是使用一种群体搜索机制取代传统的个体搜索，算法简单，适应性广，是一种非常鲁棒的算法，尤其适用于传统方法难以处理的各种NP完全问题或NP难问题。在文献[7]的基础上，本文针对早熟收敛问题，改进粒子群算法在虚拟映射问题上的应用。

本文的主要贡献如下：

考虑到原粒子群算法的早熟收敛等问题，通过增加随机因素、沿原方向飞行操作和改变原历史因素对搜索过程的指导方式等办法，改进粒子群算法在虚拟网映射问题的应用。

对在线虚拟请求映射的实验结果表明，改进的粒子群算法能够应用于虚拟节点映射，和原粒子群算法相比，能够有效减少资源消耗。

2 虚拟映射研究概况

虚拟网映射问题是NP难问题[8]，早期的虚拟映射问题解决方案多限制问题空间，文献[9]在离线模式下忽略节点资源限制，文献[10]在在线模式下忽略节点资源限制。不限制问题空间的解决方案又可分为一阶段映射算法[11,12]、两阶段映射算法[11,13,14]和迭代的映射算法[15,16]。文献[12]基于子图匹配，采用回溯方法映射；文献[11]利用拓扑属性选节点，采用基于广度优先顺序回溯映射。文献[13]将映射分为完全独立的两阶段，使用多路径实现链路映射；文献[14]增加两个映射阶段的联系，利用链路需求选择节点；文献[11]利用拓扑属性优化节点的选择。文献[15，16]的映射策略包括采用粒子群优化和人工鱼群的启发式算法，都基于随机方法和两阶段映射算法。

3 虚拟映射问题

(1)底层物理网络。使用带权值的无向图代表底层物理网络。其中，无向图的点代表物理网络节点，线代表物理链路。点有两个权值，分别代表物理节点的位置和CPU计算能力。线的权值代表物理链路的带宽。

(2)虚拟网络请求。使用带权无向图代表虚拟网络请求。其中，点代表虚拟节点，线代表虚拟链路。点的两个权值分别代表虚拟节点可映射域的圆心和虚拟节点的CPU计算能力大小，线的权值代表请求的链路带宽大小。每个虚拟网请求另有三个属性，一个指定虚拟节点可映射域的半径，另两个指定虚拟请求的到达时间和持续时间。

(3)虚拟网映射问题。虚拟网映射问题是指由物理网满足虚拟网需求。其中，一个虚拟节点只能映射到一个物理节点上，一个物理节点也只能承载该虚拟请求的一个虚拟节点，而一个物理节点可以承载多个虚拟请求的节点映射；物理节点映射应满足位置和CPU资源约束。在虚拟链路的两个虚拟端点已映射至物理网络后，在确定的两个物理节点间确定一条物理路径，该路径上的任一条链路都应满足虚拟链路的带宽需求。

(4)虚拟网映射的目标。本文的目标是使得收益最大化和费用最小化。收益最大化是在有限的物理网资源上，映射尽可能多的虚拟网。费用最小化是使每个虚拟请求占用的物理网资源最小化。

费用可包括占用的物理节点资源和物理链路资源。对于确定的虚拟请求，虚拟节点和物理节点的映射关系是一对一的，于是在映射前，映射占用的物理节点资源就是确定的。由于虚拟链路映射到的物理路径可长可短，因此费用最小化，主要是指使其占用物理链路资源最少。当虚拟链路的映射策略已定(目前普遍使用k最短路径算法或多商品流算法)的情况下，如何映射虚拟节点，使得最终占用的链路资源最小，将是虚拟网映射的目标。

4 对虚拟网映射问题应用粒子群算法的改进

文献[9]采用的粒子群算法(本节中简称原算法)是一种智能的随机搜索算法，它初始化为一群随机解，然后通过迭代寻找最优解。在每一次迭代中，粒子通过跟踪两个极值来更新自己，一个是粒子本身找到的最优解，即个体极值；一个是整个种群目前找到的最优解，即全局极值。

粒子群算法的优点是搜索速度快、效率高、算法简单，但由于每次迭代都跟踪极值，造成处理离散优化问题时，容易陷入局部最优，即早熟收敛问题。要在全局开拓与局部搜索之间平衡，算法既要使用历史轨迹智能地引导搜索，又要改进搜索策略来加强全局开拓。

4.1 引入优势群体

原算法为每一个粒子设置历史最优解，每个粒子的变化将参考该粒子的历史最优解，这样，加强了局部搜索，提高了局部收敛速度，但是也使得搜索易于陷入局部最优解。为了加强全局开拓和提高全局收敛速度，原算法为全部粒子设置了一个全局最优解，使每个粒子变化时都会参考全局最优解。随着粒子群体不断进化，粒子群体逐渐向群体最优点聚集，随着聚集程度越来越强，粒子群算法的多样性就会降低，粒子群算法的全局开拓能力就会减弱。因此，这里将取粒子群飞行轨迹的多个最优值，即优势群体，来引导每个粒子的飞行趋向。

4.2 引入随机调整因素

原算法使用惰性因子、局部最优解和全局最优解三个部分来确定调整概率。这样，只有历史轨迹和当前位置引导粒子变化，使得粒子变化的原因单一，易陷入局部最优。于是，引入了随机调整概率。将随机生成的一个随机调整概率与上述历史因素确定的调整概率作比较，取较大值作为调整概率。

4.3 增加随机扰动

当原算法在搜索过程中一直不能得到更优的解时，就意味着算法搜索过程结束。这个搜索轨迹由历史因素引导，很容易局部收敛。为了增大对全局的搜索，就需要增加扰动，即将粒子以一定的概率随机分配位置，而不总是由历史因素指导分配。

4.4 粒子保持飞行方向

原算法中，粒子每次变化调整后，不管调整结果是否较好，都不影响下一次的调整，使得调整结果好的变化方向不能得到继承。因此，这里对于上次调整结果好的粒子继续调整，直到调整结果不好，或者对该粒子连续调整的次数已达到事先设定的一个最大值。

5 改进粒子群算法的具体解决方案

5.1 算法思路

和文献[9]一样，设置每个粒子为一个向量，每个分量代表一个虚拟节点映射到的物理节点，那么，对于某个虚拟网，虚拟节点的个数就决定了向量的长度，虚拟节点的编号决定了分量的位置，虚拟节点所映射到的物理节点序号决定了分量的值。这样，每个粒子就代表了一个虚拟网节点映射方案。有历史因素引导的情况下，是否对位置向量进行调整，由方向向量决定，方向向量中分量和位置向量的分量是一一对应的，其分量可取值0或1，为1代表对位置向量的该分量进行调整，为0，不调整；当进行扰动时，可以随机生成位置向量。

5.2 适应度函数

每次节点映射的好坏由适应度(Fitness Value)函数衡量，由下式作为适应度函数：

(1)

即由节点映射方案所得到的链路映射结果决定适应度的值。其中，LEN(u,v)是指虚拟链路(u,v)所映射的物理路径长度(跳数)；BW(u,v)是指虚拟链路的带宽。

5.3 算法主要流程

基于改进的粒子群算法的虚拟网映射算法：

(1)初始化位置向量及其它变量，迭代次数z=0，迭代面积q=0。

(2)根据方向调整操作(见5.4节)得到方向向量，根据方向向量使用位置调整操作(见5.5节)对位置向量进行调整，生成一套新的位置向量。

(3)根据k-最短路径算法计算每条虚拟链路对应物理节点对之间的所有可用最短路径。若映射物理链路成功，转入步骤(4)；如果映射链路失败，且没超过最大回退次数，转入步骤(2)，如果达到最大回退次数，返回链路映射失败。

(4)根据式(1)得到此位置向量下的适应值。

(5)对适应值进行评估，判断是否小于当前的优势群体的某个个体，如果小于且新节点向量不在优势群体，则更新当前优势群体。

(6)比较新适应值与该粒子的前适应值，若新适应值较低，且在该方向飞行次数小于最大保持方向飞行次数Ns，转步骤(7)；否则，进入下一次迭代，转步骤(2)。

(7)根据已确定的方向向量，调用位置调整操作(见5.5节)，转步骤(8)。

(8)根据k-最短路径算法计算每条虚拟链路对应物理节点对之间的可用最短路径。若映射物理链路成功，转步骤(4)；如果映射链路失败，且没超过最大回退次数，转步骤(7)；如果达到最大回退次数，转步骤(9)。

(9)z=z+1，判定是否达到迭代次数，如果是，转步骤(10)；如果否，转步骤(2)。

(10)q=q+1，判定是否达到迭代面积，如果是，转步骤(11)；如果否，进行位置向量扰动操作(见5.6节)，然后转步骤(2)。

(11) 算法结束。

5.4 方向调整操作

(2)

5.5 位置调整操作

位置调整操作是指重新确定粒子i的位置，即对于位置向量的各分量j(对应虚拟节点j)，重新选择要映射到的物理节点。这里仍采用文献[9]选择物理节点的原则，使可用资源较多的物理节点被选中的概率较大。

5.6 位置向量扰动操作

按概率Ped扰动每个个体，即以概率Ped确定是否随机产生位置向量(新个体)。

6 实验性能分析

6.1 实验设置

实验主机配置如下：双处理器Intel(R)Xeon(R)CPU3.07GHz，内存(RAM)为12GB，操作系统是MicrosoftWindows7 旗舰版ServicePack1。采用标准C++编程实现相关算法。

使用GT-ITM[12]工具生成100个物理节点的底层网络拓扑，以及2 000个虚拟映射请求。底层网络的节点资源和链路资源在[50,100]内均匀分布，节点连接概率是0.5。虚拟映射请求节点数在[2,9]均匀分布，节点和链路资源请求在[0,30]均匀分布。虚拟映射请求的到达过程服从泊松分布，每个虚拟映射的生命周期服从指数分布。

对粒子参数的设置如下：粒子个数S为30，迭代次数Nz为4，沿同方向调整的最大次数Ns为3，迭代面积Nq为 4，扰动操作概率Ped为0.25，优势群体个数bestnumber为6，学习速率α为0.6。

总的迭代次数是30×4×3=480。

6.2 参与评价的指标

(1)映射时间。每个虚拟请求映射成功需要的时间。

(2)花费。映射成功后，所有虚拟链路对应物理链路的带宽和，即：

(3)

其中，u、v是虚拟链路两端点，LEN(u,v)为映射的物理链路长度，BW(u,v)为虚拟链路请求带宽。如前所述，耗费链路资源越少，虚拟请求的花费越少，相应的映射算法性能越优。

(3)收益花费比。收益指虚拟请求的资源需求，由两部分组成。节点资源映射前后没有变化(同一虚拟请求中的虚拟节点可以且只可以映射到一个物理节点)，这里只取链路资源部分：

(4)

其中，Lv是虚拟链路，BW(Lv)是Lv的带宽需求。

那么收益花费比表示为：

ratio=Revenue/Cost

(5)

式(5)中，分子的值是确定的，分母部分是不确定的，花费越少，其值越小，收益花费比越大，相应的映射算法性能越优。由式(3)和式(4)可以看出，收益花费比的最大值为1。

(4)请求接受率。虚拟请求映射成功与否的情况。

6.3 性能分析

由于本文是对文献[9]所采用的粒子群算法的改进，因此这里主要和文献[9]的算法做对比；为了说明采用粒子群算法的必要性，还与文献[14]的最大匹配算法进行了实验对比。

粒子群算法的参数设置与文献[9]保持一致，取迭代次数为100，粒子群个体数为5，那么总的迭代次数为500，与改进粒子群算法的迭代次数(480)近似。最大匹配算法是在每个维度(每个虚拟节点)上所有可用物理节点集合中，选取剩余资源最多的节点作为映射节点。

在线运行了2 000个虚拟映射请求，三个算法全部接受，说明请求接受率还是较高的。然而，在实际运行环境下，随着请求的增加，有限的资源不一定能够满足所有请求。由于粒子群算法和改进的粒子群算法在解空间进行了大量的搜索工作，因此最终找到解的概率应是较大的。又由于改进的粒子群算法比原粒子群算法搜索广度上更大，因此找到解的概率应是最大的。

虚拟请求的花费情况见图1和图2，其中，图1是每100个虚拟请求映射成功的资源平均花费。图1中，纵轴是取得的花费的平均值，横轴是被取平均值的100个虚拟请求，那么，每个点代表对纵轴所指定的这100个请求取得的平均花费值。图2是各个虚拟请求的收益花费比。其中，纵轴为收益花费比值，横轴指定各个虚拟请求ID，每个点代表一个虚拟映射请求的收益花费比。从图1和图2可以看出，改进的粒子群算法在耗费资源方面，映射效果最优。

Figure 1 Average cost of every hundred virtual network requests图1 每100个虚拟请求的平均花费

Figure 2 Income cost ratio of eachvirtual network request图2 各个虚拟请求的收益花费比

改进的粒子群算法和粒子群算法的各个虚拟请求的映射时间如图3所示。图3中，横轴为各个虚拟请求ID，纵轴为映射时间值(单位为ms)，那么每个点代表一个虚拟请求的映射时间。

表1是各算法对2 000个请求的平均映射时间。从表1中可以看出，相对于最大匹配算法，改进的粒子群算法和粒子群算法耗费的时间较长。

Figure 3 Mapping time of each virtual network request图3 各个虚拟请求映射时间

粒子群改进的粒子群最大匹配平均映射时间/s23.43335.0090.054

从上述实验数据可以看出，采用改进粒子群算法可提高映射质量，花费时间较长，但从长远考虑，应用改进粒子群算法是有意义的。

7 结束语

本文确定映射目标为减少占用资源。在实际应用中，目标还可能是使得负载更加均衡；或者面对灾难或者突发流量网络更健壮；或者面对攻击网络更安全等等。因此，应从多个角度完善虚拟网映射，使网络虚拟化更好地应用到下一代网络。

[1] Shenker S, Peterson L, Turner J. Overcoming the Internet impasse through virtualization[C]∥Proc of the 3rd ACM Workshop on Hot Topics in Networks, 2004:34-41.

[2] Turner J,Taylor D. Diversifying the Internet[C]∥Proc of IEEE GLOBECOM’05, 2005:755-760.

[3] Anderson T, Peterson L, Shenker S, et al. Overcoming the Internet impasse through virtualization[J]. IEEE Computer, 2005,38(4):34-41.

[4] Feamster N, Gao L, Rexford J. How to lease the Internet in your spare time[J]. ACM SIGCOMM Computer Communications Review, 2007,37(1):61-64.

[5] Chowdhury N K, Boutaba R. Network virtualization:State of the art and research challenges[J]. IEEE Communications Magazine, 2009, 47(7):20-26.

[6] Andersen D G. Theoretical approaches to node assignment[Z].Pittsburgh:Carnegie Mellon University, 2002.

[7] Yu M, Yi Y, Rexford J, et al. Rethinking virtual network embedding:Substrate support for path splitting and migration[J]. ACM SIGCOMM Computer Communication Review, 2008, 38(2):17-29.

[8] James K,Eberhart R.Particle swarm optimization[C]∥Proc of IEEE International Conference on Neural Networks, 1995:1942-1948.

[9] Cheng X, Su S, Zhang Z, et al. Virtual network embedding through topology awareness and optimization[J]. Computer Networks, 2012, 56(6):1797-1813.

[10] Lu J, Turner J. Efficient mapping of virtual networks onto a shared substrate[R]. Technical Report WUCSE-2006-35. Washington:Washington University, 2006.

[11] Fan J, Ammar M H. Dynamic topology configuration in service overlay networks:A study of reconfiguration policies[C]∥Proc of INFOCOM’06, 2006:1.

[12] Lischka J, Karl H. A virtual network mapping algorithm based on subgraph isomorphism detection[C]∥Proc of the 1st ACM Workshop on Virtualized Infrastructure Systems and Architectures, 2009:81-88.

[13] Cheng X, Su S, Zhang Z, et al. Virtual network embedding through topology-aware node ranking[J]. ACM SIGCOMM Computer Communication Review, 2011, 41(2):38-47.

[14] Chowdhury N M M K, Rahman M R, Boutaba R. Virtual network embedding with coordinated node and link mapping[C]∥Proc of INFOCOM’09, 2009:783-791.

[15] Zhang Z, Cheng X, Su S, et al. A unified enhanced particle swarm optimization-based virtual network embedding algorithm[J]. International Journal of Communication Systems, 2013, 26(8):1054-1073.

[16] Zhu Qiang, Wang Hui-qiang, Lü Hong-wu, et al. VNE-AFS:Virtual network embedding based on artificial fish swarm[J]. Journal on Communications, 2012,33(Z1):170-177.

附中文参考文献：

[16] 朱强, 王慧强, 吕宏武, 等. VNE-AFS:基于人工鱼群的网络虚拟化映射算法[J]. 通信学报, 2012,33(Z1):170-177.

HUYing,born in 1982,PhD candidate,lecturer,CCF member(E200041081G)，her research interest includes virtual network embedding.

Applyinganimprovedparticleswarmoptimizationalgorithminvirtualnetworkmapping

HU Ying,ZHUANG Lei

(College of Information and Engineering,Zhengzhou University,Zhengzhou 450000,China)

Using the Particle Swarm Optimization (PSO) algorithm to solve the problem of virtual network embedding can reduce the consumption of network resource, but it also brings premature convergence.An improved PSO algorithm is proposed,which adds random factors,operates along the original direction, and changes the introduction of history factors to the search process.The proposal not only keeps the instruction of history factors to the search process but also increases the search range,thus relieving, the premature convergence problems to a certain extent.The experimental results demonstrate that the improved PSO algorithm can be applied to virtual network mapping and effectively reduce resource consumption in comparison with the original PSO algorithm.

virtual network mapping;premature convergence;particle swarm optimization (PSO)

1007-130X(2014)11-2169-05

2014-07-08;

：2014-09-10

国家973计划资助项目(2012CB315901)

TP393.01

：A

10.3969/j.issn.1007-130X.2014.11.020