基于自适应协同进化粒子群算法的虚拟网节能映射研究

胡 颖 庄 雷 兰巨龙 马 丁③



基于自适应协同进化粒子群算法的虚拟网节能映射研究

胡 颖*①庄 雷①兰巨龙②马 丁①③

①(郑州大学信息工程学院 郑州 450000)②(解放军信息工程大学国家数字交换系统工程技术研究中心 郑州 450002)③(河南工业大学信息科学与工程学院 郑州 450000)

该文针对虚拟网节能映射问题提出自适应的协同进化粒子群算法。首先，为虚拟网节能映射问题设置了聚合度，该聚合度被用于自适应地选择粒子的搜索方式，即随机搜索、种内搜索或种外搜索。其次，根据粒子群的进化结果，自适应地确定是否终止对子群的搜索。最后，在常用的测试环境下进行了仿真实验，对映射的能耗效果对比了结果，实验结果表明了所提算法的高效性。

虚拟网节能映射；协同进化；自适应算法；粒子群算法

1 引言

当前互联网自身结构“僵化”，可扩展性差，新功能的增加和新业务的部署非常困难；以及OTT (Over The Top)业务飞速发展给网络运营商带来了巨大的挑战。种种迹象表明，需要一种革命式的新型互联网体系结构。网络虚拟化技术是形成新型互联网体系结构的重要手段[1]。网络虚拟化屏蔽了物理层的实现细节，在技术上，为在物理网络上运行多样化的协议和异构的应用提供了可能，使网络具有更好的开放性和灵活性；在运行维护上，使得物理网络具有了弹性特征，这对网络故障恢复、网络负载均衡都具有较大意义；在经济上，通过共享底层基础设施避免了服务提供商对基础设施的重复购买，并降低了能耗和运维成本，提高了资源的利用率。网络虚拟化既可以应用在未来互联网的中心，也可以应用在互联网的边缘，如数据中心[2]，移动网络[3]等。因此，网络虚拟化是未来互联网、云计算和软件定义网络的重要技术[1]。该技术通过整合网络基础设施资源，能够合理有效地使用能量，使得智能能量感知的网络部署成为可能。

随着电力成本的不断上涨，商家已经意识到能耗管理的重要性。当前网络为高峰负荷而设计，资源的超量供给确保了网络的正常运行，但也导致了资源利用率的低下。据统计，大型ISP骨干网的平均链路利用率大约为30%~40%[4]，数据中心服务器的平均利用率为11%~50%[5,6]，过低的资源利用率造成了电能的巨大浪费，促使绿色网络研究的兴起，网络能耗问题成为研究的热点[7,8]。虚拟网映射技术根据虚拟网请求的拓扑结构及节点、链路的资源需求，分配底层网络资源构建虚拟网，因此，该技术是网络虚拟化技术实施的基础和关键。以节能为目标的虚拟网映射应在满足当前虚拟网请求的前提下，最小化能耗，如何在这种场景下对虚拟网请求进行以节能为目标的映射，成为降低系统能耗以减少商家开销的关键问题。

当前已有一些学者对虚拟网节能映射问题进行了很有意义的研究。文献[9]从节能和资源最小化两个角度对虚拟网映射问题建立了整数线性规划模型，并分别以其一为主要目标，另一个为次要目标进行了解决和分析；文献[10]从能耗、请求优先级和请求的位置限制等3个条件来限制虚拟网节能映射问题，分析并得到了较优的结果；文献[11]为数据中心网络的虚拟网节能映射问题建立了模型，从实际因素出发，在计算资源和网络资源两个角度对问题进行了分析讨论；文献[12]应用最优化理论为虚拟网节能映射问题建立了模型；文献[13]为云计算网络的虚拟网节能映射问题建立了混合整数线性规划模型；文献[14]从节能，负载均衡等多个目标设计虚拟网映射模型，并针对云计算网络中的节点或链路故障问题，提出了一个容错的映射算法。

在映射算法上，对文献[15]的算法根据虚拟网映射问题的特点进行改进，并针对虚拟网映射这个具有离散解空间的混合整数规划问题，设计出多种群的自适应粒子群算法。该算法为避免粒子群算法自身的缺陷，比如易造成早熟停滞等问题，加入了随机搜索方式、种群内部精英指导搜索方式、种群外部的精英粒子指导搜索方式以及在多种搜索方式(包括粒子群固有的)间自适应切换等因素。最终提出了自适应的协同进化粒子群算法(Particle Swarm Optimization Algorithm based on Adaptive Cooperative Coevolution, PSOAACC)。实验结果表明，PSOAACC算法在节能映射上有较好的性能。

2 节能映射模型与评价标准

2.1虚拟网节能映射模型

虚拟网节能映射的目标是最小化能耗量，即使得映射和运行每个虚拟网请求所增加的能耗量减至最低。由文献[16]中底层网络的节点和链路能耗模型，设置虚拟网节能映射的目标：

约束：虚拟网节能映射的约束同文献[16]，包括容量约束、传输约束、一个虚拟节点只能映射到一个物理节点以及相同虚拟网请求的虚拟节点不能映射到同一个底层节点的约束。

2.2节能映射评价标准

在选择节点和路径时，为了更有效地利用资源，除了节能这一主要目标，加入对最小化资源量(即最大化收益成本比)的考虑。

2.2.1节点评价标准 应优先选择已被开启，剩余资源量较大，且CPU资源能力较大的节点作为宿主节点。定义节点节能度,值越大，节点被选中的概率越高。

2.2.2链路评价标准 在路径选择时，要兼顾物理路径长度和物理路径中物理链路的开启量。本文通过定义路径耗能度来对虚拟链路的可用物理路径进行评价，值越小，对的评价越好。

3 自适应的协同进化粒子群算法

3.1 适应度函数

在式(1)中给出了虚拟网节能映射的目标函数，函数值越小，节能效果越好，该问题是最小化问题，于是可直接设置目标函数为适应度函数，即

3.2自适应协同进化粒子群算法的实现

PSOAACC算法模型分上下两层，底层为多个子种群，高层为精英粒子。底层各子种群采用具有合作机制的自适应的粒子群算法分别进化。在进化过程中，从底层的多个种群中提出适应度值最低的粒子组成高层精英粒子，精英粒子连同自身的历史最优粒子参与对底层各子种群的指导操作，即种间的指导搜索；若子种群使用本群的历史最优粒子以及自身粒子的历史最优粒子作为指导搜索，即为种内的指导搜索；另外，为了尽量避免种群陷入局部最优，这里使粒子适时进行随机搜索。

3.2.1子种群的聚集程度 子种群中粒子各分量上取值的集中程度决定了子种群的聚集程度，且各分量上取值越多样化，子种群越分散。

为衡量子种群某时刻的聚集程度，可将其与聚集程度的极端情况相比较。子种群的两个极端情况分别是所有个体都相同和个体各分量均匀地分散。当均匀分散时，要么取值为，要么取值为。其中，取值为的个数为

当所有位置都均匀分散时，由式(6)和式(9)，得到子种群在均匀分散情况下的聚集度为

3.2.2子种群种内外学习的方式 已知，当子种群的聚集程度较大时，应增大子种群的学习范围，向着扩散的方向进化，因此，此时应进行种间指导搜索；否则，应进行种内指导搜索。设置阈值，若，进行种间学习；否则，进行种内学习。

进行种内学习时，要使用种内最优个体指导粒子的方向。对分量调整的概率：

种间学习时，需要使用种间的精英粒子(即整体的最优粒子)对粒子方向的指导。于是，对种群中粒子的分量调整的概率为

3.2.3随机搜索的方式 根据式(2)为每个可用物理节点计算出节能度，和文献[15]中对粒子随机初始化的方式类似，根据节能度得到依次增大的权重和。生成随机数，随机数落到哪个区间即选择那个物理节点作为映射节点。这样，节能度大的节点具有较高的选中概率。

3.2.4确定粒子将进行随机搜索或学习搜索 当聚集程度较大，应增加随机搜索个体的数量，使种群向着扩散的方向进化。可定义随机搜索的个体数为

3.2.5种群进化搜索终止条件 若子种群不再进化，即连续次没有更新子种群的最优个体，说明结果已接近最优值，或难以跳出局部优值，此时，可终止对该子种群的进化搜索。当所有子种群都被停止时，便可终止整个种群的进化搜索。为避免出现搜索时间过长的情况。

3.3 自适应的协同进化粒子群算法流程

以上分析了PSOAACC算法的主要思想，下面就具体算法实现流程描述如表1。

表1自适应的协同进化粒子群算法流程

(1)初始化参数；

(4)按3.2.3节对该粒子进行随机搜索，生成映射的物理节点序列；

表2 Sub_ep(,,if_terminate_)程序

(13) 按3.2.2节对该粒子种间指导搜索，生成映射的物理节点序列；

(17) Else

(18) 按3.2.3节对该粒子进行随机搜索，生成映射的物理节点序列；

(22) End if

4 实验

4.1实验环境

本实验在双核CPU 3.4 GHz, 4 G内存的PC机上运行。底层网络拓扑和虚拟网请求拓扑由GT- ITM[18]工具生成，实验设置同文献[19]：底层网络共包含50个节点，每两节点间连接的概率为0.5。底层节点的计算资源和底层链路的带宽资源取值在[50,100]内均匀分布。虚拟网请求的到达时刻服从平均100个时间单元到达4个请求的泊松过程，即到达时刻服从均值为25的泊松分布。持续时间服从均值为1000的指数分布。每个请求的节点个数在[2,10]内均匀分布，节点连接率为0.5，虚拟节点请求的CPU资源取值在[0,20]，虚拟链路请求的带宽资源取值在[0,50]之间均匀分布。虚拟网请求共计1000个，实验共运行25000个左右的时间单元。

PSOAACC是以节能为目标的智能搜索算法，实验选取的比较对象有两个：较经典的同样以节能为目标的贪婪映射算法EAVNE[20]和基于粒子群的映射算法PSO[15]。

在参数设置上，同文献[18,21-23]中的设置，得到节点和链路能耗中常数的值为：为150 W;为300 W;为15 W。由于链路功耗差异较大，和文献[16]中设置一样，这里比较了链路功耗在1 W, 15 W和30 W下的网络总能耗，如图1(d)所示。PSOAACC算法的参数设置为子种群个体数= 30，最大迭代次数=5，子种群数=3；其它的参数设置为=3,=0.5,=1,=1,=1,,,=5,=0.1,=0.2和=0.7，物理节点已开启时设置=100，物理节点尚未被开启时=1,=5。PSO算法的参数设置为种群个体数是30，最大迭代次数为15。

图1 运行结果

为提高实验结果的可信度，所有实验运行10组不同的虚拟网请求，取平均值作为实验结果。

4.2 节能比较

本文的虚拟网节能映射方法降低了底层网络节点和链路的开启数量，很大程度地减少了底层网络能耗，并使得运行中的平均能耗增长较不明显。

为方便分析描述，首先作如下定义：

定义1 如果在某个时间段内，底层网络上没有发生虚拟网请求的到达或离开事件，称此时段的底层网络处于稳定状态。

定义2 如果在某时刻发生了虚拟网请求的映射或离开事件(这里认为映射和离开事件的发生时间忽略不计)，称该时刻为分裂点。

定义3 相邻两个分裂点间的时间段，称为有效时间片。

由以上定义可知，在有效时间片内，底层网络处于稳定状态；在不同的有效时间片间，底层网络单位能耗量不同。于是，对底层网络计算总能耗前应先确定所有分裂点，由各分裂点将运行时间分为多个有效时间片，在各个有效时间片内分别计算底层网络的能耗，底层网络的总能耗即各有效时间片的能耗总和：

在有效时间片内，物理网络设备稳定运行，底层网络能耗即各类设备的能耗之和：

定义平均节点开启量(Average Number of Open Nodes, ANON)、平均链路开启量(Average Number of Open Links, ANOL)和平均能耗量(Average Amount of Energy Consumption, AAEC)为总和与有效时间片个数之商(时间段均从初始时刻起)。

图1(a)，图1(b)和图1(c)表示节点和链路的平均开启量以及底层网络的平均能耗量随时间变化的情况。图中表明在开启节点数量，开启的链路数量和能耗量上，PSOAACC算法较PSO和EAVNE有较为明显的优势。

底层网络物理链路功耗参数对底层网络运行总能耗的有影响，但本文算法PSOAACC和粒子群算法PSO相比在各种情况下均有效降低了能耗。

图1(d)给出底层链路功耗参数分别取1 W, 15W和30 W的底层网络总能耗(根据式(17))情况。图1(d)表明PSOAACC算法在不同的链路能耗下都能取得较好的节能效果。当链路功耗为1 W时，PSO较EAVNE的底层网络总能耗降低了35.8% , PSOAACC较PSO的底层网络总能耗降低了7.72%；当链路功耗为15 W时，PSO较EAVNE的底层网络总能耗降低了29.31%, PSOAACC较PSO的底层网络总能耗降低了10.53%；当链路功耗为30 W时，PSO较EAVNE的底层网络总能耗降低了15.49%, PSOAACC较PSO的底层网络总能耗降低了12.59%。

5 结束语

本文研究了网络虚拟化环境下的系统能耗问题，根据节能运行的实际需要，设计自适应的协同进化粒子群算法(PSOAACC)，把虚拟网映射在一个较小的节点和链路集合中，提高休眠的节点链路数量，以实现高效节能。实验结果表明了PSOAACC算法能够有效降低底层网络的能量消耗，与经典节能算法相比，提高了收益成本比。这里将问题限定在集中方式下的单域虚拟网节能映射问题，下一步将对跨域映射问题进行进一步的研究。

参考文献

[1] ANDERSON T, PETERSON L, SHENKER S,. Overcoming the internet impasse through virtualization[J]., 2005, 38(4): 34-41. doi: 10.1109/MC.2005.136.

[2] CORREA E S, FLETSCHER L A, and BOTERO J F. Virtual data center embedding: a survey [J]., 2015, 13(5): 1661-1670. doi: 10.1109/ TLA.2015.7112029.

[3] CHOCHLIDAKIS G and FRIDERIKOS V. Robust virtual network embedding for mobile networks[C]. 2015 IEEE 26th Annual International Symposium on Personal, Indoor and Mobile Radio Communications, Hong Kong, China, 2015: 1867-1871. doi: 10.1109/PIMRC.2015.7343603.

[4] FISHER W, SUCHARA M, and REXFORD J. Greening backbone networks: Reducing energy consumption by shutting off cables in bundled links[C]. ACM SIGCOMM Workshop on Green Networking, India, 2010: 29-34. doi: 10.1145/1851290. 1851297.

[5] BARROSO L and HOLZLE U. The case for energy- proportional computing[J]., 2007, 40(12): 33-37. doi: 10.1109/MC.2007.443.

[6] BOHRER P, ELNOZAHY E N, KELLER T,The Case for Power Management in Web Servers[M]. New York, NY , USA, Kluwer Academic/Plenum Publishers, 2002: 261-289.

[7] 林闯, 田源, 姚敏. 绿色网络和绿色评价: 节能机制、模型和评价[J]. 计算机学报, 2011, 34(4): 593-612. doi: 10.3724/ SP.J.1016.2011.00593.

LIN Chuang, TIAN Yuan, and YAO Min. Green network and green evaluation: mechanism, modeling and evaluation[J]., 2011, 34(4): 593-612. doi: 10. 3724/SP.J.1016.2011.00593.

[8] 叶可江, 吴朝晖, 姜晓红, 等. 虚拟化云计算平台的能耗管理[J]. 计算机学报, 2012, 35(6): 1262-1285. doi: 10.3724/SP.J. 1016.2012.01262.

YE Kejiang, WU Zhaohui, JIANG Xiaohong,Power management of virtualized cloud computing platform[J]., 2012, 35(6): 1262-1285. doi: 10.3724/SP.J.1016.2012.01262.

[9] MELO M, SARGENTO S, KILLAT U,. Optimal virtual network embedding: Energy aware formulation[J]., 2015, 91: 184-195. doi: 10.1016/j.comnet.2015. 08.011.

[10] TRIKI N, KARA N, BARACHI M E,. A green energy-aware hybrid virtual network embedding approach[J]., 2015, 91: 712-737. dio: 10.1016/j. comnet.2015.08.016.

[11] GUAN X J, CHOI B Y, and SONG S. Energy efficient virtual network embedding for green data centers using data center topology and future migration[J]., 2015, 69(9): 50-59. doi: 10.1016/j.comcom.2015.05.003.

[12] CHEN Xiaohua, LI Chunzhi, and JIANG Yunliang. Optimization model and algorithm for energy efficient virtual node embedding[J]., 2015, 19(8): 1327-1330. doi: 10.1109/LCOMM.2015.2442575.

[13] NONDE L, El-GORASHI T E H, and ELMIRGHANI J M H. Energy efficient virtual network embedding for cloud networks[J]., 2015, 33(9): 1828-1849. doi: 10.1109/JLT.2014.2380777.

[14] HOUIDI I, LOUATI W, and ZEGHLACHE D. Exact multi-objective virtual network embedding in cloud environments[J]., 2015, 58(3): 403-415. doi: 10.1093/comjnl/bxu154.

[15] ZHANG Zhongbao, CHENG Xiang, SU Sen,. A unified enhanced particle swarm optimization-based virtual network embedding algorithm[J].2013, 26(8): 1054-1073. doi: 10. 1002/dac.1399.

[16] 陈晓华, 李春芝, 陈良育, 等. 主动休眠节点链路的高效节能虚拟网络映射[J]. 软件学报, 2014, 25(7): 1416-1431.

CHEN Xiaohua, LI Chunzhi, CHEN Liangyu,. Energy efficient virtual network embedding based on actively hibernating substrate nodes and links[J]., 2014, 25(7): 1416-1431.

[17] EPPATEIN D. Finding theshortest paths[J]., 1998, 28(2): 652-673. doi: 10.1137/ S0097539795290477.

[18] ZEGURA E W, CALVERT K L, and BHATTACHARJEE S. How to model an Internetwork[C]. Proceedings of IEEE INFOCOM,96. Conference on Computer Communications, San Francisco, CA, USA, 1996: 594-602. doi: 10.1109/ INFCOM.1996.493353.

[19] CHOWDHURY N M M K, RAHMAN M R, and BOUTABA R. Virtual network embedding with coordinated node and link mapping[C]. 2009 IEEE INFOCOM 28th International Conference on Computer Communications, Rio de Janeiro, Brazil, 2009: 783-791. doi: 10.1109/INFCOM.2009.5061987.

[20] SU Sen, ZHANG Zhongbao, CHENG Xiang,. Energy- aware virtual network embedding through consolidation[C]. IEEE Conference on Computer Communications, Orlando, FL, USA, 2012: 127-132. doi: 10.1109/INFOCOMM. 2012. 6193473.

[21] SIVARAMAN V, VISHWANATH A, ZHAO Z,Profiling per-packet and per-byte energy consumption in the NetFPGA Gigabit router[C]. IEEE INFOCOM 2011 - IEEE Conference on Computer Communications Workshops, Shanghai, China, 2011: 331-336. doi: 10.1109/INFCOMW. 2011.5928833

[22] UNNIKRISHNAN D, VADLAMANI R, LIAO Y,Scalable network virtualization using FPGAs[C]. 18th ACM International Symposium on Field-Programmable Gate Arrays, Monterey, CA , USA, 2010: 219-228.

[23] BARROSO L A, CLIDARAS J, and HOLZLE U. The Datacenter as A Computer: An Introduction to the Design of Warehouse-scale Machines[M]. San Rafael, CA, USA, Morgan & Claypool Publishers, 2013: 1-154.

Energy Aware Virtual Network Embedding Using Particle Swarm Optimization Algorithm Based on Adaptive Cooperative Coevolution

HU Ying①ZHUANG Lei①LAN Julong②MA Ding①③

①(,,450000,)②(&,,450002,)③(,,450000,)

A novel adaptive co-evolutionary particle swarm optimization algorithm is presented for energy aware virtual network embedding problem. The polymerization degree is designed, which is used to adaptively select searching method, namely variation search, internal search or external search. Second, the algorithm adaptively determine whether to terminate the searching process of particle swarm according to the evolution result. Moreover, extensive simulation under common test environment compares results in energy consumption performing goal, and the results indicate the efficiency of the proposed algorithm.

Energy aware virtual network embedding; Co-evolution; Adaptive algorithm; Particle swarm optimization algorithm

TP311

A

1009-5896(2016)10-2660-07

10.11999/JEIT151434

2015-12-17；改回日期：2016-07-01；网络出版：2016-08-26

胡颖 huying_yx@126.com

国家973计划(2012CB315901)，国家自然科学基金(61379079)，河南省科技厅攻关项目(122102210042)

The National 973 Program of China (2012CB315901), The National Natural Science Foundation of China (61379079), The Science and Technology Key Project of Henan Province (122102210042)

胡 颖： 女，1982年生，讲师，研究方向为网络虚拟化.

庄 雷： 女，1963年生，教授，研究方向为网络和自动机.

兰巨龙： 男，1962年生，教授，研究方向为新一代信息网络关机理论和技术.

马 丁： 男，1978年生，讲师，研究方向为服务路径组合和网络虚拟化.