基于优化粒子群算法的虚拟机部署策略_董德坤.pdf

2023 年第 3 期计算机与数字工程收稿日期：2022年8月2日，修回日期：2022年9月10日作者简介：董德坤，男，硕士研究生，研究方向：云计算。张亚钦，女，硕士研究生，研究方向：智慧医疗。徐克祥，男，硕士研究生，研究方向：云计算。1引言云计算是一种利用互联网实现随时随地、按需便捷地访问共享资源池（如计算设施、存储设备、应用程序等）的计算模式，本文关注的是物理服务器的虚拟化。由于云基础设施依赖于虚拟化技术，云计算的大规模使用将增加更多的虚拟机请求，从而增加虚拟化基础设施的压力，因此需要一个有效的虚拟机调度策略。本文提出一种改进的粒子群算法，该算法迭代过程初期引入混沌策略，使粒子群分布有着良好的遍历均匀性；使用随机分组策略，作为改进粒子群的核心过程，设置两个目标函数，利用欧氏距离寻求多目标粒子群优化算法的最优解。将改进后的算法应用到云计算虚拟机部署，以物理机资源利用率、虚拟机迁移量为目标函数。基于优化粒子群算法的虚拟机部署策略董德坤张亚钦徐克祥（中国石油大学（华东）计算机科学与技术学院青岛266580）摘要随着云计算规模的增大，能耗已经成为云系统中重要的成本，因此节能问题成为了云系统面临的主要问题之一。在满足物理机资源阈值的约束下，最大化物理机资源利用率，减少虚拟机迁移数量，是实现数据中心节能的一种有效手段。论文提出一种改进的粒子群算法（EPSO），算法初期引入混沌策略，使用随机分组策略，设置两个目标函数，利用欧氏距离寻求多目标粒子群优化算法的最优解。与其他算法相比，该算法初期群体有着良好的遍历均匀性，提高了粒子群的寻优精度和寻优效率。基于 CloudSim仿真平台实验结果显示，该算法在改善物理机资源利用，减少资源浪费等方面具有高效性，优化了云系统性能。关键词云计算；粒子群算法；资源分配；虚拟机部署中图分类号TP311；TP18DOI：10.3969/j.issn.1672-9722.2023.03.011Virtual Machine Deployment Strategy Based on Optimized ParticleSwarm AlgorithmDONG DekunZHANG YaqinXU Kexiang（College of Computer Science and Technology，China University of Petroleum（East China），Qingdao266580）AbstractEnergy consumption has been an important cost given the growth of computing power，thereby energy conservationhas become one of the major problems faced by cloud system.How to maximize the utilization of physical machines and reduce thenumber of virtual machine migrations under the constraints of physical machine resource thresholds is an effective means to implement energy saving in data center.In the paper，an improved particle swarm optimization algorithm（EPSO）is proposed.The algorithm introduces chaotic strategy into the initial stage of the iterative process，uses random grouping strategy，sets two objectivefunctions，and uses Euclidean metric to find the optimal solution of the multi-objective particle swarm optimization algorithm.Compared with other algorithms，the algorithm has better ergodicity into the initial stage，improves the optimization precision and optimization efficiency of the particle swarm.The experimental results based on CloudSim simulation platform show that the algorithm is effective at improving physical machine resource utilization，reducing resource waste.Key Wordscloud computing，particle swarm optimization algorithm，resource reservation，virtual machine deploymentClass NumberTP311，TP18总第 401期2023 年第 3期计算机与数字工程Computer&Digital EngineeringVol.51No.3595第 51 卷2相关工作虚拟机部署是将虚拟机映射到物理机的过程。由于云基础设施是完全虚拟的，虚拟机的部署成为云系统的核心问题。为此，人们进行了大量有关优化虚拟机部署的研究工作，Xu等1针对云计算环境下虚拟机的动态部署问题，提出了虚拟机动态部署的多目标综合评价模型和改进的多目标粒子群优化算法（IMOPSO）。胥小波等2提出了一种新的混沌粒子群优化算法，不同于已有的混沌粒子群算法的简单粒子序列替换，该算法将混沌融入到粒子运动过程中，使粒子群在混沌与稳定之间交替运动，逐步向最优点靠近。朱亚会等3提出一种基于资源利用率均衡的虚拟机调度模型。该模型将虚拟机调度问题抽象为不定维向量装箱模型。杨靖等4引入多种群进化模式提高算法收敛速度，并在此基础上加入高斯学习策略避免局部最优，提出了一种多种群高斯学习粒子群优化（MGL-PSO）算法。张笑燕5等提出了一种虚拟机部署方案，该方案的目的是减少主机上的资源碎片。曹盟盟等6在算法中引入分组思想，通过对初始种群进行随机分组，避免算法陷入早熟现象。经典的智能算法有蚁群算法、遗传算法、微分进化算法等，Garg79等利用遗传算法（GA）、蚁群算法、微分进化（DE）相结合的粒子群优化算法，保持了多种算法的优点。Zhao10提出了一种基于 PSO的改进算法，根据云计算环境中资源的使用成本来解决任务调度问题。Dashti等11利用粒子群优化（PSO）在过载的PMs中重新分配 vm，并合并负载不足的 PMs以节省电能。3资源浪费模型3.1问题描述本文的研究内容是基于粒子群算法提出一种虚拟机部署方案，通过合理地部署虚拟机以减少云系统能耗。在云系统中，虚拟机分为已部署的虚拟机和新请求的虚拟机，系统图如图1所示。图1系统图本文提出的虚拟机部署方案对物理主机CPU、内存和网络带宽三种资源的负载情况进行监控。假设云环境中有 n 个物理机，物理机阈值表示为Rj=RCj,RMj,RBj。m个虚拟机，虚拟机需求表示为Vi=VCi,VMi,VBi。虚拟机的部署情况由矩阵Xmxn表示，xij值为1表示第i个虚拟机部署在第j个物理机上。3.2目标函数和约束函数目标函数如下：Max f1=(i=1mVCij=1nRCj+i=1mVMij=1nRMj+i=1mVBij=1nRBj)/3（1）Min f2=i=1mmi（2）约束函数如下：j=1nxij=1（3）i=1mVCj.xijRCj（4）i=1mVMj.xijRMj（5）i=1mVBj.xijRBj（6）其中，式（1）表示虚拟机利用率。式（2）表示虚拟机的迁移数量。式（3）表示同一虚拟机只能部署在同一物理机上。式（4）、（5）、（6）分别表示多个虚拟机部署在物理机上时，虚拟机CPU、内存、带宽资源需求量不超过物理机CPU、内存、带宽阈值。4改进算法设计4.1传统粒子群算法粒子群算法是进化算法的一种，在每一次迭代中，粒子通过跟踪两个“极值”来更新自己。式（7）为粒子速度更新公式，式（8）为粒子位置更新公式。在 d 维空间的第 i 个粒子，位置表示为Xid=(xi1,xi2,xid)，速度表示为Vid=(vi1,vi2,vid)。Vid(t+1)=Vid(t)+r1.c1.(Pid(t)Xid(t)+r2.c2.(Pgd(t)Xid(t)（7）Xid(t+1)=Vid(t)+Xid(t)（8）4.2改进的多目标粒子群算法设计Kennedy认为，具有大邻域的粒子群优化算法在处理简单问题时表现得更好，而具有小邻域的粒子群优化算法在处理复杂问题时表现得更好12。本文对传统粒子群算法进行改进，首先引入混沌算法对粒子群初始化，迭代过程使用随机分组策略。董德坤等：基于优化粒子群算法的虚拟机部署策略5962023 年第 3 期计算机与数字工程1）混沌映射利用混沌映射初值敏感性、遍历性特点，随机初始化一个粒子，并通过混沌映射得到多个粒子的初始值，改变初始粒子群的提取过程。利用混沌映射扩大初始粒子群，得到寻优粒子群，使得种群粒子多样化。Tent映射结构简单，具有很好的遍历性，公式如下。xn+1=2xn,0 xn0.52()1xn，0.5xn1（9）2）惯性权重ww是影响算法搜索结果和收敛速度的关键参数，w过大有利于全局寻优，w过小有利于局部寻优。根据w取值对搜索结果的影响，本文采用线性递减方式设定w值。如下所示。=max(maxmin)t/iteration（10）3）随机分组粒子群算法迭代过程通过随机分组策略更新，3个粒子组成一个小群体，每隔5代各小群体间粒子进行随机重组。群体间两个粒子不足以构成一个良好的群体，而五个粒子具有较好的局部搜索能力和较弱的全局搜索能力。三个粒子实现了它们之间的平衡，群体显示出更好的全局搜索能力13。4）最优解设计通过欧氏距离法1更新目标函数和粒子群，策略步骤表示如下。（1）群体内粒子利用组内信息更新速度和位置。目标函数 f1和 f2单独更新，从每次迭代结果中，选择两个群体最优值f-Opt 1 和f-Opt 2。（2）计算两个群体最优间的距离。df=i=12(fOptif)2（3）个体最优值的确定。如果dl i df，取二者平均值作为个体最优。（4）更新至迭代结束。5）虚拟机编码粒子群算法中，设共有p个粒子。云系统中，将粒子的速度和位置维数设置为物理机数目n，并将物理机编号为1到n。粒子的位置向量的每一项表示虚拟机i在该物理机上，粒子位置向量的值表示虚拟机的一种部署策略。5实验本文选择CloudSim仿真平台进行仿真实验，用基本 CloudSim 类中的继承类实现 EPSO 算法。实验环境如下，编译环境 JDK 1.8，编译软件 Eclipse4.6，仿真云计算环境 CloudSim 3.0，物理机的数量为100，虚拟机的数量为200。所有服务器都有相同的资源分配：10个处理单元的CPU、20GB内存和100M带宽。设计仿真实验，与经典粒子群算法进行对比。我们比较了多目标粒子群算法与传统的粒子群算法PSO，分别从资源利用率f1，虚拟机迁移数f2两方面进行对比分析。其中PSO对两个目标的关注度一致。在CloudSim平台上，进行仿真实验记录相关数据，将实验结果数据进行对比分析，最后得出两种算法的实验效果分布图。图2表示了在不同服务请求下算法的资源利用率，证明我们提出的改进算法是有效的，资源利用率高于其他算法。图3表示了虚拟机的迁移次数，PSO算法下虚拟机迁移了73次，EPSO算法下虚拟机迁移了51次，所