优化人工蜂群算法的跨域虚拟网络映射算法

顾艳林（内蒙古财经大学计算机信息管理学院，内蒙古呼和浩特010020）

优化人工蜂群算法的跨域虚拟网络映射算法

顾艳林
（内蒙古财经大学计算机信息管理学院，内蒙古呼和浩特010020）

针对跨域虚拟网络映射问题，提出一种基于优化人工蜂群算法的跨域虚拟网络映射算法.该算法采用集中管理、分布控制的方式实现物理网络资源的有效利用，并就人工蜂群算法收敛速度慢、局部最优缺点，提出寻优能力更强的优化人工蜂群算法进行域间映射请求的划分.实验结果表明：与LID－MVNE算法、Policy－MVNE算法、GA－MVNE算法相比，所提算法能够以更小的额外开销、更少的划分时间实现更高的接受率.

人工蜂群；虚拟网络；自治域；服务代理

虚拟网络作为一种新颖的互联网体系架构，能够有效地解决互联网体系架构的“僵化”问题［1］.在网络虚拟环境下，基础设施提供商（InP）负责物理网络的管理和运营，并且能向服务提供商（SP）提供网络资源租赁服务，而被租赁的网络资源被映射为虚拟网络，从而实现个性化的可订制的端到端服务［2］.其中，具有链路和节点资源约束的虚拟网络到物理网络的映射问题，被称为虚拟网络映射（VNE）问题［3］.随着在线游戏、云计算、IPTV等新兴网络业务的迅猛发展，单个自治域难以很好地支撑这些新兴的网络业务.跨域虚拟网络映射（MVNE）算法就是用于解决多自治域下虚拟网络到物理网络的映射问题［4］.Dietrich等［5］提出了LID－MVNE算法，采用整数规划把虚拟网络拓扑分解成由不同自治域负责的多个虚拟子网路，再通过域内映射完成子网络的映射.Chowdhury等［6］提出了Policy－MVNE算法，把VNE请求交由位置最近的自治域进行处理，如果该自治域无法完成VNE，则该VNE请求转交由相邻的自治域处理.上述两种算法存在复杂度高、平均划分时间长的缺点.Xiao等［7］提出了GA－MVNE算法，通过遗传算法完成虚拟子网络的划分，但是GA－MVNE算法并没有对域内链路开销进行考虑.因此，本文提出了一种基于优化人工蜂群算法的跨域虚拟网络映射（OABC－MVNE）算法.

1 MVNE模型

物理网络由多个自治域构成，每个自治域中都有一个区域服务代理（regional service agent，RSA）负责域内状态采集以及域内VNE.同时，物理网络中有一个全局服务代理（global service agent，GSA）负责域间拓扑状态的采集、域间VNE的划分以及与RSA的通信，以掌握自治域的资源使用情况.为了实现集中管理和分布控制，MVNE的工作流程如下.1）RSA负责接收域内用户的VNE请求，如果能完成VNE，那么，其通过单域VNE算法响应该请求；否则，在GSA轮询到该RSA时，把该请求转交由GSA处理.2）在处理RSA提交的VNE请求的过程中，GSA把VNE请求放入FIFO队列中，并按照先到先服务的原则串行处理每个VNE请求，并按照制定的域间划分算法把域间请求划分为若干个域内请求，交由相应的RSA处理.

2 优化目标

由于尽量减少虚拟链路所消耗的链路资源就能以最小的代价完成MVNE.因此，MVNE算法的优化目标函数为

式（1）中：li，j为虚拟链路；rcd为li，j对应的物理路径；ls为li，j中的物理链路；m为虚拟网络的节点数；n为物理网络的节点数；D（ls）为ls的时延；λ为单位时延开销；xi为li，j的类型，其表达式为

同时，表达式还应满足2个约束条件，即

式（3）说明物理链路ls的剩余带宽Re s（B（ls））能够满足虚拟链路的li，j带宽需求.而式（4）说明路径rcd的时延不大于虚拟链路li，j的时延约束.

3 算法实现

虚拟网络划分问题已被证明是NP－hard问题，为了得到该问题的近似最优解，OABC－MVNE算法使用优化人工蜂群（optimized artificial bee colony，OABC）算法完成域间请求到域内请求的划分.

蜜源的位置通常用Xi＝（xi，1，…，xi，d）表示，而在寻找蜜源的过程中，表示为

式（5），（6）中：SN为蜂群数；k和j为随机数，且k∈｛1，2，…，SN｝，j＝｛1，2，…，d｝，k≠i；ri，j为［－1，1］上的随机数；vi，j为新蜜源的位置；pi为雇佣蜂被选中的概率.

定义1 蜜源位置.域间请求到域内请求的划分的解对应着蜜源位置，而一个蜜源只对应着一个雇佣蜂，即Xi＝（xi，1，xi，2，…，xi，m）T.式中：m为VNE请求中的虚拟节点数；行向量xi，j为边界节点与虚拟节点的映射关系；i为第i个蜜源.

定义2 蜜源的适应度.由于蜜源的好坏直接由蜜源的适应度fit（Xi）决定，因此，以MVNE算法的优化目标函数为参考设定fit（Xi），其值为

定义3 位置调整准则.基本ABC算法只进行单维变量搜索，从而存在算法收敛速度慢的缺点.针对这个问题，OABC算法引入蜜源历史最优位置加速搜索速度.因此，式（5）改写为

式（8）中：φi，j为［－1，1］上的随机数；xbesti，j为蜜源历史最优位置.

定义4 蜜源选择准则.基本ABC算法会导致蜂群快速向好蜜源靠近，导致局部最优.为了增加种群的多样性，式（6）改写为

定义5 随机搜索准则.如果观察蜂在蜜源邻域搜索l次后，蜜源适应度值的变化值小于阀值ε，那么，通过杂交操作生成新的蜜源.杂交公式为

式（10）中：α为［－1，1］上的随机数；j∈｛1，2，…，SN｝，j≠i；Xbestj为Xj的当前最佳位置.

OABC算法的工作流程：1）设置蜂群规模SN，最大迭代次数M，最大搜索次数l，阀值ε，随机生成SN个初始蜜源；2）计算所有蜜源的适应度，并按照从大到小的顺序排序，选择前［SN／2］个作为蜜源，蜜源与雇佣蜂一一对应；3）雇佣蜂根据位置调整准则来寻找新的蜜源，并比较新旧蜜源的适应度值，如果fit（XNew）＜fit（Xi），保留旧蜜源，否则，留下新蜜源；4）根据雇佣蜂释放的信息，观察蜂以式（9）进行蜜源选择，并按照位置调整准则进行更优蜜源的搜索；5）如果经过l搜索后，蜜源适应度值的变化量小于ε，对其进行杂交操作；6）如果迭代次数小于M，跳到步骤2），否则，算法结束，输出最优解.

4 仿真分析

仿真实验在Intel Xeon E5－2650CPU 2.0GHz，内存16G的联想Think Station C30工作站上进行.物理网络由10个自治域构成，每个自治域包含50个节点，其中，边界节点2个，并且边界节点之间是全连接.其他仿真参数，如表1所示.表1中：t1为仿真时间.

表1 仿真参数表Tab.1 Simulation parameter

4种算法的平均划分时间（t）随虚拟节点数（n）的变化，如图1所示.随着虚拟节点数的增加，4种算法的平均划分时间都变大.这是因为虚拟节点数越多，虚拟网络结构越复杂，需要花更多的时间完成虚拟网络的划分.其中，OABC－MVNE算法所需的平均划分时间最小，这是由于OABC－MVNE算法使用OABC算法进行域间映射划分，从而避免了复杂的数学运算，实现了平均划分时间的减少.

3种算法的额外映射开销（η）随虚拟节点数（n）的变化，如图2所示.由图2可知：Policy－MVNE算法的额外开销是最大的，这是因为在边界节点信息未知的情况下，Policy－MVNE算法并没有对跨域开销进行优化.图2中：OABC－MVNE算法和GA－MVNE算法的额外开销都始终小于5%.这是因为2种算法在边界节点信息已知的情况下以最小资源开销为目标进行了跨域开销的优化.由于OABC－MVNE算法的寻优能力更强，因此，其额外开销小于GA－MVNE算法.

图1 平均划分时间随虚拟节点数的变化Fig.1 Average time changing with the number of virtual nodes

图2 额外映射开销随虚拟节点数的变化Fig.2 Additional costs vary with the number of virtual nodes mapping

5 结束语

首先，对MVNE问题的基本概念与研究现状进行阐述，指出现有算法存在复杂度高、平均划分时间长、开销大等缺陷.然后，针对以上问题，提出了OABC－MVNE算法，并介绍了OABC－MVNE算法的实现过程.最后，通过仿真实现，从平均划分时间、平均接受率、平均额外开销3个方面，验证了OABCMVNE算法的有效性.

［1］ CHEN Zhong，GUAN Zhi，MENG Hongwei，et al.A survey of future internet architecture and security design［J］.Journal of Information Security Research，2015，6（2）：89－98.

［2］ LUO Juan，FU Shan，CHEN Lei，et al.Concurrent resource mapping in virtual network［J］.Journal of Computational ＆Theoretical Nanoscience，2014，11（5）：1264－1270.

［3］ FISCHER A，BOTERO J F，TILL BECK M，et al.Virtual network embedding：A survey［J］.IEEE Communications Surveys ＆Tutorials，2013，15（4）：1888－1906.

［4］ PITTARAS C，PAPAGOANNI C，HAM J V D，et al.Resource discovery and allocation for federated virtualized infrastructures［J］.Future Generation Computer Systems，2015，42（C）：55－63.

［5］ DIETRICH D，RIZK A，APADIMITRIOU P.Multi－domain virtual network embedding with limited information disclosure［C］∥Proceedings of IFTP Networking Conference.Brookyln：IEEE Press，2013：1－9.

［6］ CHOWDHURY M，SAMUEL F，BOUTABA R.PolyViNE：Policy－based virtual network embedding across multiple domains［J］.Journal of Internet Services and Applications，2013，6（4）：1－23.

［7］ XIAO Ailing，WANG Ying，MENG Luoming，et al.Knowledge description and genetic algorithm based multi－domain virtual network embedding［J］.Journal of Software，2014，25（10）：1289－2205.

［8］ RAZZAQ A.Virtual network embedding［J］.Journal of Electrical ＆Computer Engineering，2012，7（15）：762－771.

［9］ KARABOGA D，BASTURK B.On the performance of artificial bee colony（ABC）algorithm［J］.Applied Soft Computing，2008，8（1）：687－697.

［10］ 黄娴，谭鸽伟.人工蜂群算法结合PTS技术的PAPR降低方法［J］.华侨大学学报（自然科学版），2014，35（6）：631－635.

（责任编辑：黄晓楠 英文审校：吴逢铁）

Multi－Domain Virtual Network Mapping Algorithm Based on Optimized Artificial Bee Colony

GU Yanlin
（College of Computer Science and Technology，Inner Mongolia University of Finance and Economics，Huhehaote 361021，China）

Aiming at the problem of multi－domain virtual network embedding，a multi－domain virtual network mapping algorithm based on optimized artificial bee colony is proposed.The proposed algorithm can maximize the utilization of limited physical network resources through centralized management and distributed control.And to overcome the defaults of the local optimization and low convergence of the traditional artificial bee colony algorithm，an optimized artificial bee colony algorithm is proposed，which is used to deal with the division of cross－domain mapping request.The experimental result shows that compared with LID－MVNE，Policy－MVNE，GA－MVNE，the proposed algorithm can realize higher acceptance ratio with less extra cost and time division.

artificial bee colony；virtual network；autonomous domain；service agent

TP 393

A

1000－5013（2016）04－0507－04

10.11830／ISSN.1000－5013.201604023

2016－05－01

顾艳林（1971－），女，副教授，主要从事计算机应用及网络、程序设计的研究.E－mail：guyanlin5830908＠

126.com.

内蒙古自治区教育科学规划课题（GJ2011－51－02）