基于混合粒子群的虚拟网络映射算法

贾晓光

摘要：虚拟网络映射的目标是为用户的虚拟网络合理分配底层物理资源，是虚拟资源分配领域的热点问题。针对粒子群算法在求解映射可行解时可能产生的早熟收敛、局部寻优能力差等问题，该文将粒子群优化算法与禁忌搜索算法和模拟退火算法相结合，利用禁忌列表和退火过程来解决早熟收敛问题，进而提出混合粒子群优化的虚拟网络映射算法。仿真实验结果表明，我们所提出的算法在虚拟网络接受率和收益/成本比方面相较已有算法有一定提升。

关键词：虚拟化；虚拟网络映射；粒子群算法；退火算法

中图分类号：TP312 文献标识码：A 文章编号：1009-3044（2018）07-0210-04

网络虚拟化[1]技术允许在共享的底层物理网络基础设施之上共存多重异构的虚拟网络。为用戶带有节点（CPU、内存、存储）和链路资源（带宽）约束条件的虚拟网络请求分配底层物理网络资源的问题称为虚拟网络映射（Virtual Network Embedding， VNE）问题[2]。虚拟网络映射问题已经被证明是NP 难问题，即使在所有的虚拟节点已被映射后，映射带有带宽资源约束的虚拟链路仍然是NP 难的[3]。因此，目前已有的研究成果大都采用智能算法解决虚拟网络映射问题[4]。

离散粒子群（Discrete PSO， DPSO）算法是基于群体智能的启发式全局优化技术，群体中的每一个粒子代表待解决问题的一个候选解，算法通过粒子间信息素的交互作用发现复杂搜索空间中的最优区域，其具有收敛速度快、算法简单、搜索效率高等特点[5]。但在实际应用中，采用单一的智能算法解决虚拟网络映射问题是不够的，单纯基于粒子群算法的映射方案在运行一段时间后会产生收敛于局部优化解的问题。因此，本文基于TS算法和SA算法提出了混合粒子群优化算法，HPTS-VNE-PSO（Hybrid of Particle swarm optimization，Tabu search and Simulated annealing about Virtual Network Embedding Based on Particle Swarm），算法利用了禁忌搜索算法中的禁忌列表以及模拟退火算法中的退火过程来解决寻优过程中出现的早熟收敛问题。

1 Related works

在不对虚拟网络映射问题约束进行任何限制的情况下，文献[5]提出了一种允许底物网络支持路径分离的方法从而使映射算法更有效地利用资源，从而简化了虚拟链路的映射问题。文献[6] 将底层物理网络和虚拟网络的拓扑都看作一个有向图，提出了基于子图同构的映射算法，该算法在同时映射节点和链路。该算法可以被看作是经典的VF图形匹配算法[7]的扩展版本，但该算法没有考虑到虚拟节点的位置约束。文献[8] 项等应用粒子群优化求解虚拟网络映射问题，利用粒子群算法简单，代码执行效率高的特点，将虚拟节点映射结果用粒子的位置表示，并利用底物网络的资源消耗作为适应度函数来评估当前解的优劣。在迭代的过程中，每个粒子根据个体和全局最优信息来调整它们的飞行速度，以获得最优的虚拟网络映射。

苑迎等人[9]提出的基于DPSO负载可控的虚拟网络映射算法，同样是采用粒子群优化算法，针对多租赁模式下的虚拟网络映射问题，提出了物理节点可复用、负载可控制的MLB-VNE-SDPSO算法。该算法兼顾了CPU主机资源利用率，节约了物理链路的带宽资源，缩短了虚拟链路的映射时间。缺点是未考虑粒子群算法的早熟问题以及链路中中间节点的资源消耗。

PSO算法是独立于问题的，也就是说不需要知道过多与问题相关的特定知识，只需要知道每个解的适应度值就可以方便地进行寻优操作，这种优势使得PSO算法比许多其他搜索算法更健壮。然而，由于粒子群算法是一种随机搜索算法，它被证明是不确定的全局搜索。如果问题的求解是十分困难而复杂的，PSO算法可能找不到所需的最佳解决方案。禁忌搜索（Tabu Search，TS）和模拟退火（Simulated Annealing，SA）算法能够从某种程度上避免陷入局部最优，搜索过程可以由冷却策略得到控制。通过设计TS算法和SA算法的邻域结构和冷却策略从而控制搜索过程，可以有效地避免个体陷入局部最优。因此，我们提出HPTS-VNE-PSO算法，从横向和纵向水平上扩展搜索范围。

2 基于混合粒子群的虚拟网络映射算法设计

TS[10]算法作为一种元启发式算法，某种程度上是模拟人类行为的智能搜索方式。不同于遗传算法和模拟退火算法等特点的智能随机算法，TS算法通过采用禁忌策略克服搜索过程中过早地陷入早熟收敛从而达到全局最优，本文利用了TS算法的这一特点，借鉴该算法的禁忌列表来避免重复搜索，提高收敛效率。SA[11]引入了物理系统中退火降温过程的自然机理， 在迭代过程中不仅接受使适应度值变“好”的试探点，还以一定的几率接受使适应度值变“坏”的试探点，随着温度的下降接受的概率也将逐渐减小。这种搜索策略能够有效避免搜索过程因陷入局部最优解而无法挣脱的现象发生，从而提高求得全局最优解的可靠性。

我们将PSO算法，TS算法和SA算法结合，设计了HPTS-VNE-PSO算法。如图1所示，PSO算法通过结合本地搜索（自我经验）与全局搜索（邻居经验）达到较高的搜索效率。TS算法则通过记忆功能来避免被困在局部最优（水平方向上的计算）。SA算法的搜索过程由退火过程（也称为垂直方向的计算）进行控制，以一定的概率避免陷入局部最优。

2.1 问题定义

HPTS-VNE-PSO算法的设计上存在几个关键技术：1）搜索空间 、2）PSO算法框架、3）邻居搜索、4）禁忌列表、5）适应度函数、6）冷却控制，下面依次进行阐述：

1）搜索空间

假设虚拟节点数目为N，那么粒子群搜索范围为N维空间。设定初始粒子群数目为m。由于虚拟网络映射问题属于离散问题，我们采用离散粒子群优化算法，并重新定义第[i]个粒子的位置、速度、个体最优位置以及全局最优位置如下：

在一个粒子群中，“认知”权重[c1]和“社会”权重[c2]控制着粒子移动的范围，通常我们将其设置为2.0。本文采用的粒子速度的更新公式参照4.2式和4.3式。

3）邻居搜索

为不断拓展搜索空间禁忌搜索需要不断进行邻居移动，邻居移动即在当前解的基础上，按照某种特定的移动策略产生出一定数目的新解，称为邻居解。邻居搜索对于局部搜索是十分有效的，一般来说没必要的和不可行的移动必须终止。目前最著名的邻居结构是基于“块”的。我们的算法邻居结构设为数组形式。

4）禁忌列表

禁忌列表中存放的是禁忌对象，被放入禁忌表中的禁忌对象在解禁之前不能被再次搜索。本文使用的禁忌列表是数组，禁忌对象为已经搜索过的粒子。

禁忌长度指的是禁忌对象在禁忌列表中的生存时间。当一个禁忌对象加入到禁忌列表时，设置其任期为禁忌长度值，HTPS-VNE-PSO算法设置种群大小为禁忌长度。搜索过程中禁忌长度是动态变化的，本文设置为每迭代一次则禁忌表中的禁忌对象的任期自动减1，当某一禁忌对象任期为0时，则将其从禁忌列表中删除，任期大于0的禁忌对象被设为禁忌状态，搜索过程不可以被选为新解。

5）适应度函数

评价函数可以计算解对应的评价函数值，通过评价函数来评价禁忌搜索空间中的解。评价函数值的大小代表了解的优劣程度，它是评价粒子群的性能指标，通过比较评价函数值的大小确定当前解是否更优。解的评价函数，又称为适应度函数适应度函数，我们使用带宽开销最小化作为适应度函数：[Minluv→lijfuvijb（luv）]，其值越小越好，这也是VNE问题的典型目标。

6）冷却控制

SA算法模块可以通过冷却策略进行控制。冷却策略的初始温度[T0=Δfmax]，其中[Δfmax]表示任意两个邻居解适应度值的最大差值。温度的变化公式为：[Tk=B×Tk-1（k=1，2，3...）]，下降因子B小于1。

2.2 HPTS-VNE-PSO 算法實现

如图2所示，HTPS-VNE-PSO的主要思想是利用PSO算法逐轮生成粒子位置，即可能的映射方案；然后采用弗洛伊德最短路径算法为虚拟链路寻找最短路径，并为其分配链路；将初始粒子信息加入到禁忌列表中；对每个粒子计算适应度值、gbest、pbest得到最优解；根据特定规则为最优解创造邻居解，然后从不在禁忌列表中的邻居解集中找到最好邻居作为当前解进行存储，更新禁忌列表。在模拟退火部分。我们首先选定初始温度，当温度不足够低时，用当前解继续生成邻居解，并计算其适应度值，如果达到终止条件则更新gbest，将其加入到禁忌列表中，并降低温度。当温度降到一定程度则返回最优解，否则继续降温过程。

PSO算法操作过程为HPTS-VNE-PSO算法提供了初始粒子，并构成了整个算法的外围框架，其伪代码如下所示：

3 实验结果及分析

本文实验在CloudSim [12]中对比了VNE-R-PSO [9]和D-ViNE-SP[6]两种算法，这两种算法都是典型的基于粒子群的虚拟网络方法。实验首先·对CloudSim进行了二次开发，将其控制粒度从虚拟机修改为虚拟网络，并设计了一个拓扑生成器来生成虚拟和物理拓扑。生成器的参数包含节点的数量、连接概率和虚拟网络请求的任务持续时间。底物网络被设置为拥有100个节点和500条链路。物理节点CPU容量和物理链路带宽在[50， 100]区间随机均匀分布。实验中，虚拟网络请求的到达服从参数为5的泊松分布，最小时间间隔等于ColudSim中的100时间单位。每个虚拟网络的生命周期服从参数为400时间单位的指数分布。对于每个虚拟网络请求，其虚拟节点的数量在[2， 20]区间随进均匀分布，虚拟节点之间的链路生成概率是50%，虚拟网络节点CPU请求和虚拟带宽请求服从[3， 50]的随机均匀分布。每次实验运行50000时间单位，平均2500个虚拟网络请求被映射。三种算法粒子群迭代的最大次数都被设置为20次。实验比较了三种算法的虚拟网络接受率和收益成本比，具体结果如下。

图3所示是算法随着时钟节拍的增加虚拟网络请求接受率的变化曲线，负载因子[γ]取值均为1。从图中可以看出，随着时间推移HPTS-VNE-PSO算法虚拟网络请求接受率逐渐下降并趋于平缓，比其他算法效果要好。

图4所示是HPTS-VNE-PSO算法与表中另外2个算法在长期平均收益成本比方面的比较，负载因子[γ]取值均为1。从图中可以看出，几个算法的平均长期收益成本比波动都不大，大约在0.05范围以内，但随着时间推移HPTS-VNE-PSO，比另外2个算法的表现要好。

4 结论

本文通过引入禁忌搜索算法的禁忌列表和模拟退火算法的退火技术，提出了一种混合粒子群优化算法。禁忌搜索算法的禁忌列表可以避免重复搜索，扩大横向搜索范围，而模拟退火算法则在纵向水平上避免陷入局部寻优的困境，两者的结合能够在一定程度上解决单纯基于粒子群算法解决虚拟网络映射问题时容易陷入早熟的问题，从而获得了较好的虚拟网络接受率和收益成本比。

参考文献：

[1] Chowdhury NMMK， Boutaba R. Network virtualization： State of the art and research challenges[J].IEEE Communications Magazine， 2009， 47（7）： 20?26.

[2] Cheng Xiang， Zhang Zhong-bao， Su Sen， Yang Fang-chun. Survey of virtual network embedding proble[J]m. Journal on Communications， 2011， 32（10）： 143-141 （in Chinese）

[3] Zhi-ping C， Qiang L， Pin L， Nong X， Zhi-ying W. Virtual Network Mapping Model and Optimization Algorithms[J]. Journal of Software， 2012， 23（4）： 864?877.

[4] Beck MT， Fischer A， Botero JF， Linnhoff-Popien C， Meer HD. Distributed and scalable embedding of virtual networks[J]. Journal of Network and Computer Applications 2015， 56：124-136.

[5] Ma Xuan， Liu Qing. Particle Swarm Optimization for Multiple Multicast Routing Problem[J]. Journal of Computer Research and Development， 2013， 50（2）： 260-268.

[6] Lischka J， Karl H. A virtual network mapping algorithm based on subgraph isomorphism detection[C]//Proceedings of the 1st ACM workshop on Virtualized infrastructure systems and architectures， ACM， 2009： 81-88.

[7] Cordella L P， Foggia P， Sansone C， et al. An improved algorithm for matching large graphs[C]//3rd IAPR-TC15 workshop on graph-based representations in pattern recognition， 2001： 149-159.

[8] Xiang Cheng， Baozhong Zhang. Virtual Network Embedding Based on Particle Swarm Optimization[J]. Acta Electronica Sinica， 2011，39（10）：2240-2244.

[9] 苑迎， 王翠榮， 王聪， 等.基于DPSO负载可控的虚拟网络映射算法[J]. 东北大学学报， 2014， 35（1）： 10-14.

[10] Glover F. Future paths for Integer Programming and Links to Artificial Intelligence[J]. Comput Oper Res， 1986，13：533-549.

[11] Kirkpatrick S， Jr Gelatt C D，Vecchi MP.Optimization by simulated annealing[J]. Sciennce， 1983（11）： 650-671.

[12] Calheiros R N， Ranjan R， Beloglazov A，et al. Buyya， Cloudsim： a toolkit for modeling and simulation of cloud computing environments and evaluation of resource provisioning algorithms[J]. Software Practice and Experience，2011， 41（1）：23-50.