基于K-means和蝙蝠算法的云计算虚拟机智能调度

2016-12-01 09:55王焱

现代电子技术 2016年21期

关键词：蝙蝠利用率聚类

王焱

（汉江师范学院教育系，湖北十堰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）输出最优的蝙蝠位置对应的数据聚类结果。