王焱
（汉江师范学院教育系，湖北十堰442000）
基于K-means和蝙蝠算法的云计算虚拟机智能调度
王焱
（汉江师范学院教育系，湖北十堰442000）
针对云计算虚拟机调度中存在的资源分配不均衡问题，提出了一种基于K-means和蝙蝠算法的云计算虚拟机智能调度方法。该方法充分考虑物理节点空闲资源和虚拟机所需资源的互补性，以物理节点作为初始聚类中心，使用资源的相关性定义二者的距离，利用蝙蝠算法的全局寻优能力迭代寻优，达到合理调度虚拟机的目的。模拟实验仿真的结果表明，该方法在降低物理节点数量和提高资源利用率方面具有一定的优势，是一种可行的方法。
K-means；蝙蝠算法；云计算；虚拟机；调度
0 引言
云计算是一种新型的商业计算模式，是分布式处理、并行处理和网络计算的拓展和延伸，已成为工业界和学术界的研究热点。云计算的本质是以虚拟化技术为基础，实现数据共享和服务共享。云平台通过虚拟机的方式，通过高速的互联网互连，形成虚拟资源池。虚拟机调度问题是云计算的关键技术之一，主要实现将虚拟机有效映射到相应的物理机上，达到物理机的负载均衡，有效利用现有资源。由于虚拟机需求量与物理集群的异构，可行部署空间增大，使云计算虚拟机调度成为一个NP-hard问题。本文主要基于K-means和蝙蝠混合算法研究了云计算虚拟机调度问题，实现了资源的高效平衡分配。
1 相关研究
云计算中虚拟机调度策略对云系统的性能具有很大的影响，能够提高资源的利用率，最大化满足用户的需求。目前已有不少学者对云计算的虚拟机调度机制进行了研究。文献[1]提出了一种基于多属性层次分析的虚拟机部署与调度策略，该算法将虚拟机按资源特点进行分类量化，根据量化后的权向量和服务器资源的使用记录，实现虚拟机的调度。文献[2]在分组遗传算法的基础上，提出了基于多维资源协同聚合的虚拟机调度策略，对均衡资源分配具有一定的优势。文献[3]提出了云计算的改进的credit调度算法，根据空闲率、缓存等因素选择与其相关的任务，能提高缓存效率和增加延迟敏感型任务的响应速度。文献[4]提出基于能耗比例模型的虚拟机调度算法，并采用“最近最小能耗比例优先”的策略进行调度，提高了云系统的能效。文献[5]提出了基于改进NSGAⅡ的虚拟机调度算法，将该模型的求解转化为一个多目标优化问题，在任务执行时间、负载均衡和能量消耗方面具有一定的进步。本文在以上研究的基础上提出基于K-means和蝙蝠混合算法的云计算虚拟机调度方法，将虚拟机分配到与其资源互补的物理机上，充分利用物理机上的资源，达到最优化目标。
2 蝙蝠算法和K均值算法
2.1蝙蝠算法
蝙蝠算法是剑桥大学学者Xin-She Yang于2010年提出的一种新型优化算法，主要是受自然界中的蝙蝠搜寻、捕食行为启发形成的新型优化算法，每个优化问题的解是搜索可行空间的一个蝙蝠[6-8]。
（1）蝙蝠的运动
蝙蝠算法在d维空间中定义了蝙蝠的位置和速度的变化情况，蝙蝠i在t时刻的位置和速度的变化通过下列公式描述：
式中：β表示在[0，1]之间的随机变量；x*表示当前全局最优位置；fi为频率大小，根据要搜索的范围大小确定其最大值和最小值。局部搜索时，蝙蝠位置的更新公式为：
式中：ε∈[-1,1]是随机数；At是所有蝙蝠在同一时间段的平均音量。
（2）音量和脉冲发生率
当蝙蝠i找到目标时，音量Ai就会降低，同时脉冲发生率ri就会增加，其更新公式如下：
式中：α和γ为常量，为简化变化过程通常取α=γ=0.9。
2.2K-means算法
K-means算法以K为参数，把n个对象分为K个类，通过距离大小衡量聚类结果的优劣，聚类的距离越近，说明其相似度就越大，聚类效果越好[9-10]。聚类结果中在同一类中的对象相似度较高，而不同聚类中的对象相似度较小，其基本思想是在数据空间中任意选择K个数据对象作为初始聚类中心，根据其余数据与对应聚类中心的相似度进行聚类划分，然后再计算新的聚类中心，不断重复执行这一聚类过程，即可得到最终类别划分结果。聚类结果实际上是寻找数据集的划分过程，各聚类本身尽可能的紧凑，而各聚类之间尽可能的分开。
3 云计算虚拟机智能调度模型
云计算数据中心有m个物理节点，有n个虚拟机发送调度请求，每个物理节点的资源向量分为已使用的资源向量和空闲的资源向量，物量节点上的资源是多维的，包括CPU、内存、带宽和I/O等，每个物理节点已使用的资源等于分配到该节点的虚拟机资源之和[11-12]。设虚拟机集合为V={VMi|1≤i≤n}，物理节点集合为M={PMj|1≤j≤m}，虚拟机调度的目的是利用最少的物理节点获得最大的资源利用率，并且保证物理节点分配的资源利用率不超过其资源的最大容量，其可以建立如下的目标和约束条件：
（1）目标函数：
式中：ui表示第i个物理节点是否使用；ui,j表示物理节点在第j维度的利用率；qi,k表示虚拟机对资源k的需求量。
4 基于K-means和蝙蝠算法的虚拟机调度方法
4.1调度思想
本文提出的虚拟机调度方法的基本思想是将每个虚拟机分配到距离最近的物理节点上，通过多次迭代，每个虚拟机都与所在的物理节点最近。在本文中虚拟机与物理节点的距离用资源相关系数表示，相关系数越小，说明虚拟机所需资源与物理节点拥有的资源之间具有更多的互补，在空闲资源满足条件的情况下，将其分配到相关系数小的物理节点，有利于更充分地利用资源。虚拟资源与物理节点之间的相关性采用皮尔逊相关系数表示，取值范围为[-1，1]：
将虚拟机与物理节点的距离定义为：
则虚拟机与物理节点的距离取值范围为[0，1]。本文将虚拟机到不活跃物理节点的距离定义为最大，将其取为1，表示只有当虚拟机无法放置时才分配到新物理节点。
4.2蝙蝠编码规则
蝙蝠算法采用实数据编码，一个编码对应一个可行解。本文采用m个物理节点为初始聚类中心，这样聚类对应的物理节点限定了聚类的大小，简化了对资源的考虑，并且确定的聚类减少了迁移的次数，使资源的分配更加稳定。
每个蝙蝠由m个聚类中心构成。设当前虚拟机分为m类，每个数据为d维特征，用于实数进行编码，以K均值聚类中心作为寻优变量，每个可行解是由m个聚类中心构成，由于解的维数是d维，这里可行解的位置是m×d维向量，可行解的编码示例，其结构如下：
其中Zm1,Zm2,…,Zmd代表第m类的d维聚类中心。
4.3虚拟机调度步骤
（1）蝙蝠初始化：给定含有n个虚拟机对象的数据集T和物理节点数m，基于蝙蝠算法的K-means聚类方法，将每类的聚类中心作为蝙蝠的位置编码，反复进行多次，生成N个初始蝙蝠。以上聚类中心方法执行多次，生成含有n个蝙蝠的初始化种群XI(I=1,2,…,n)，其目标函数为f(X)，X=(x1,x2,…,xd)T。
（2）初始化蝙蝠种群的速度、脉冲频率、脉冲响度和脉冲发射速率。
（3）根据适应度公式计算每个蝙蝠的适应度值，保留最优解，并利用速度和位置公式对其他蝙蝠进行更新。
（4）产生一个随机数rand1，if（rand1>ri），则对当前群体中最佳蝙蝠位置进行随机扰动得到替换当前蝙蝠的位置。
（5）通过随意飞行产生新解，产生随机数rand2，if（rand2
（6）利用K-means方法对蝙蝠位置进行优化，按照最近邻近法原则确定对应的聚类划分，并重新计算聚类中心，更新蝙蝠的适应度，根据适应度函数排列蝙蝠，找到当前最佳位置，如果达到结束条件（满足条件的位置或最大迭代次数）则聚类完成，转到步骤（7），否则转到步骤（3）。
（7）输出最优的蝙蝠位置对应的数据聚类结果。
5 仿真实验
采用CloudSim 3.0云平台软件对本文提出的调度方法进行模拟仿真，CloudSim是澳大利亚墨尔本大学的网格实验室和Gridbus项目宣布推出的云计算仿真软件。本仿真实验将虚拟机分别设置为100，200，300， 400，500，每个实例取10次运算的平均值，将所需物理节点数量和系统资源综合利用率两方面与K-means调度方法进行比较。
（1）物理节点数据对比
物理节点使用数量的对比情况见图1，可以看出，本文调度方法的物量节点的数量比K-means调度方法平均降低12%左右，有效地减少了资金投入，物理机节点的能耗也降低，使数据中心具有高密度、低成本的优点。主要原因是本文调度方法通过聚类方法将虚拟机分配到服务器中，并且将虚拟机到不活跃物理节点的距离设置为最大，表示只有当虚拟机无法放置时才分配到新的物理节点，这样有效地提高了数据中心物理节点的分配密度，降低了物理节点的节点数量。
图1 物理节点使用数量对比
（2）系统资源综合利用率比较
系统资源综合利用率对比见图2，可以看出本文调度方法系统资源综合利用率比K-means调度方法平均提高了11%左右，有效地提高了资源的综合利用率。主要是因为本文调度方法在调度时考虑了虚拟机与服务器资源的互补性，有效地防止了一种资源过于饱和导致其他资源不能使用的情况，通过资源互补分配虚拟机有效地提高了资源的综合利用率。
图2 系统资源综合利用率对比
6 结语
在开放的云计算环境下，合理的虚拟机调度策略有利于提高资源的综合利用率，并有效地降低能耗。本文提出了一种云计算环境中使用的虚拟机智能调度方法，考虑了虚拟机与服务器资源的互补性，降低了云服务提供者的运营成本，仿真实验表明该方法在节省物理节点和提高综合资源利用率方面都取得了较好的效果，是一种可行的方法。
[1]庄威，桂小林，林建材，等.云环境下基于多属性层次分析的虚拟机部署与调度策略[J].西安交通大学学报，2013，47（2）：28-32.
[2]袁爱平，万灿军.云环境下基于改进遗传算法的虚拟机调度策略[J].计算机应用，2014，34（2）：357-359．
[3]暴锡文.一种云计算环境下基于Xen的虚拟机调度机制[J].计算机测量与控制，2014，22（10）：3381-3384.
[4]肖鹏，刘洞波，屈喜龙.云计算中基于能耗比例模型的虚拟机调度算法[J].电子学报，2015，43（2）：305-310.
[5]殷小龙，李君，万明祥.云环境下基于改进NSGAII的虚拟机调度算法[J].计算机技术与发展，2014，24（8）：71-75.
[6]李煜，马良.新型全局优化蝙蝠算法[J].计算机科学，2013，40（9）：225-228.
[7]金伟健，王春枝.基于蝙蝠算法的云计算资源分配研究[J].计算机应用研究，2015，32（4）：1184-1187．
[8]全雪姣，孟凡荣，王志晓.对K-mean初始聚类中心的优化[J].计算机工程与设计，2011（8）：165-167.
[9]吴夙慧，成颖，郑彦宁，等.K-means算法研究综述[J].现代图书情报技术，2011，31（5）：30-35.
[10]宋旭东，朱文辉，邱占芝.大数据K-Means聚类挖掘优化算法[J].大连交通大学学报，2015，36（3）：91-94.
[11]李乔，郑啸.云计算研究现状综述[J].计算机科学，2011，38（4）：32-37．
[12]徐文忠，彭志平，左敬龙.基于遗传算法的云计算资源调度策略研究[J].计算机测量与控制，2015，23（5）：1653-1656．
Cloud computing virtual machine intelligent scheduling based on K-means and bat algorithm
WANG Yan
（Department of Education，Hanjiang Normal University，Shiyan 442000，China）
To solve the resource allocation imbalance problem existing in cloud computing virtual machine scheduling，a cloud computing virtual machine intelligent scheduling method based on K-means and bat algorithm is proposed.The method fully considers the complementarity of the physical node idle resource and the resource needed by virtual machine，selects the physical node as the initial clustering center，and uses the resource correlation to define the distance between them.The global searching ability of bat algorithm is used for iterative optimization to achieve the goal of reasonable virtual machine scheduling. The scheduling method was simulated.The experiment results show that the method has certain advantages in reducing the quantity of physical nodes and improving the resource utilization，and is an effective method.
K-means；bat algorithm；cloud computing；virtual machine；scheduling
TN911-34；TP391
A
1004-373X（2016）21-0021-03
10.16652/j.issn.1004-373x.2016.21.005
2015-12-02
湖北省教育科学“十二五”规划项目（2012B453）
王焱（1980—），女，硕士，副教授。主要从事现代教育技术及信息管理等方面的教学与研究。
