基于改进的蝙蝠算法在云计算资源调度中的研究

李天朝，李蜀瑜

（陕西师范大学 计算机科学学院，陕西 西安 710062）

基于改进的蝙蝠算法在云计算资源调度中的研究

李天朝，李蜀瑜

（陕西师范大学 计算机科学学院，陕西 西安 710062）

本文对云计算中资源调度进行了深入的研究，针对云计算的资源调度模型，提出一种基于和声算法和蝙蝠算法调度算法。在该求解方法中，通过改进蝙蝠的位置的平均响度，来减小的迭代次数。这一改进能够提供易于调节的蝙蝠算法离散优化问题，提高算法的收敛速度，缩短算法的运行时间。实现了蝙蝠算法对优化问题的处理结果。通过仿真实验表明，该算法是一种云计算环境下有效的任务调度算法。

元计算；蝙蝠算法；和声算法；资源调度

云计算是一种商业模式和服务模式，是分布式计算、并行处理和网格计算等多种技术的拓展和延伸[1]。资源调度是云计算的核心问题，其效率直接影响整个云计算环境的工作性能，在云计算环境下，怎样找到一个完善、高效的计算资源调度模型是至关重要的，它决定了云计算的性能，已经成为当前一个重要研究方向之一[2]。

文献[3]中对云计算下的资源池模型做了介绍，分析了云计算调度资源流程和云计算环境下实体之间的关系。建立了一种云计算环境中资源调度算法，综合考虑了云计算资源池中各种资源的综合负载情况，采用人工加自动的虚拟机迁移技术实现云计算中物理服务器的负载均衡。文献[4]使用了马尔可夫链模型并提出一种控制算法，在特定的QoS约束条件下最大化每两次虚拟机迁移的时间，从而决定哪些服务器是资源过载的。文献[5]提出了一种基于克隆选择算法的云集群资源调度方法。首先，定义了云环境下以最小化执行时间跨度和负载均衡因子的集群资源调度模型，然后设计了抗体的编码方式，抗体与抗原之间的亲和度函数、抗体之间的亲和度函数、克隆算子、退火交叉算子和高斯变异算子，并定义了基于克隆选择算法的云计算集群资源调度方法。文献[6]提出了CL-PSO算法，是以综合置信度最优解为目标函数，文化粒子群算法 （CulturalParticleSwarm Optimization，CPSO）是文化算法（CA）和PSO算法相结合的组合算法，较好地克服了标准PSO算法存在的缺陷，为云计算资源调度提供了一种新的研究方法。文献[7]针对现行资源调度算法存在算法效率低等弊端，提出一种新的云计算资源调度模型（IABC），基于利用改进人工蜂群算法的云计算资源调度模型，改进了传统资源调度算法的缺陷，大幅度消减了任务的完成的时间，并且提高了云计算资源利用率。文献[8]使用一种更先进、更精确的方法来预测虚拟机的CPU使用情况。建立了每个虚拟机的数据模型，利用了一种分布式决策支持系统（rDSS）作为云计算应用来预测虚拟机的CPU使用率。

文中提出了一种改进的蝙蝠算法，通过改进蝙蝠的位置的平均响度，来减小的迭代次数。这一改进能够提供易于调节的蝙蝠算法离散优化问题，提高算法的收敛速度，减少了算法的执行时间，实现了蝙蝠算法对优化问题的处理结果。

1 云计算资源调度模型

云计算资源调度是云计算技术的一个重要组成基础，它的目标是研究用户提交的任务分配计算节点、计算节点间进行动态扩展及在满足用户服务质量要求并且执行时间最短的前提下，虚拟机利用率最高，它的效能直接影响所有云计算环境的工作能效。在云计算资源调度中，就是尽可能的在短时间内完成任务最多，目标值调度时间最小，系统利用率最高。云计算资源调度模型如下：■

其中，xij表示任务i占用虚拟节点 j，1表示占用，0则表示未占用；tij表示任务i在虚拟节点j上使用的时间，cij表示任务i占用虚拟节点j上的费用，sij表示任务i占用虚拟节点j上的资源利用率，kij表示任务i占用虚拟节点j上的调度开销。i表示虚拟节点的个数，j表示虚拟节点，T表示资源调度的目标函数值，要求达到min S。

2 蝙蝠算法

蝙蝠算法 （Bat Algorithm，BA）[9-11]是剑桥大学Xin-She Yang教授在2010年提出的一种启发式群智能优化算法，它是利用蝙蝠回声定位搜索捕食猎物模拟出的算法。蝙蝠算法是通过自然界中蝙蝠找寻食物的活动，通过使用回声中的声波定位去搜索它们的猎物，回声中的声波是由指定的脉冲速率和频率获得，通过迭代搜索得到最优解，并且在生成的最优解周围进行局部搜索，直至找到最优解。蝙蝠算法作为一种新颖的群智优化算法，收敛速度快，参数少，模型简单等优点，已经成功运用于多种问题中[12]。

起初必须确定N维的搜索空间，蝙蝠的响度是A，频率范围为[fmin，fmax]，脉冲频率为r，对应波长的范围是[λmin，λmax]，指定第i只蝙蝠在t时刻的速度vti和位置lti的更新公式如下：

其中，fi表示蝙蝠频率，β∈[0，1]它代表的随机变量，服从均匀分布。x*表示通过每一次迭代得到的最佳位置。针对λf是一个增量，在本文中固定波长λ，而针对f进行调整，在进行部分搜索的期间，从现在的局部搜索中生成一个最优解，每只蝙蝠将随机生成一个新的位置。

在以上公式中，假设α和κ取值在[0，1]。随着蝙蝠的速度和响度的不断更新，象征着蝙蝠可以继续飞向最优解。

3 基于和声搜索算法的蝙蝠算法的改进

对于基本蝙蝠算法种群中的每只蝙蝠在一个小范围内搜索能力比较强，但是整个群体缺乏有效的变异机制因为该算法采用种群向当前最优个体学习的机制，一旦被某个局部极值吸引，由于没有有效的变异机制，使得整个种群都可能陷入局部最优解。此外，蝙蝠算法也存在一些问题，例如后期收敛速度慢、难以摆脱局部最优，种群迅速聚集到超个体，全局搜索能力较差等。

3.1 和声搜索算法

和声搜索（Harmony Search，HS）算法[13]是 2001年韩国学者Z.W.Geem等人提出的一种新的智能优化算法，算法模拟了乐师们在音乐作曲中凭借自己的记忆，通过重复调整乐队中各乐器的音调，最终能获得一个优美的和声状态的过程。HS算法将乐器声调的和声类比于优化问题的解向量，评价即是各对应的目标函数值。算法引入两个主要参数，即微调概率 （Pitch Adjusting Rate，PAR）和记忆库取值概率（Harmony Memory Considering Rate，HMCR）[14]。

3.2 对蝙蝠算法的改进

蝙蝠算法有一个很好的搜索能力。但是，它需要通过大量的迭代才能产生产生这种令人满意的结果。在这里，我们定义动态比例系数参数θ，它是限制步长的随机漫步的本地搜索的一个因素，改进提出了这个算法。适当的调整，从计算时间来看该参数减小了的迭代次数。此外，这一改进能够提供易于调节的蝙蝠算法离散优化问题。动态比例因子θ参数可以定义为：

这个公式定义了和声搜索算法中宽带参数之间的关系。取代了用公式（4），进一步演化的公式可以表述如下：

在上述的公式中，iter指代当前迭代过程。为了解决收敛实例，上述这种增强版的方程式还是会用上的。在连续优化问题中，θmax和θmin应该可以分别被取作1和0.001。同时在离散优化问题中，θmax和θmin可以分别被取作10和0.01。但是，这些数值通常在优化问题中的参数整定时才会被推荐使用；同时，在遇到一些参数和问题高度紧密联系，但是这些问题又需要得到较好调整的情况下，这些数值也会被推荐使用。

3.3 蝙蝠个体的编码方式

云计算资源调度即是对所有可能的调度序列进行搜索，最后找到一个最好调度的方案。在处理云计算资源调度运用蝙蝠算法算法时，需要对资源进行划分和蝙蝠个体进行编码。为了便于计算，提高蝙蝠算法的搜索效果，文中采用二进制方式编码作为蝙蝠个体的蝙蝠方式，即蝙蝠个体对应每个任务的资源，每一个编码后的蝙蝠个体实际上都与每一个资源相对应。

改进的蝙蝠算法在云计算资源调度的优化步骤：

1）初始化蝙蝠种群的位置x（i），速度v（i），脉冲发射速率r（i），脉冲响度A（i）和脉冲频率f（i）；

2）初始化当前区域中的蝙蝠数量xi（i∈{1…n}）。

3）根据个体不同的适应值采用不同的频率生成策略；

4）利用公式（2）~（4）计算蝙蝠飞行速度和空位方位；

5）评估新解，若满足条件则更新位置和速度，同时利用公式（9）、公式（6）更新脉冲响度A（i）和发射速率r（i）；

6）判断算法终止条件，若满足搜素精度w或者达到搜素次数，则退出，并输出最终结果，否则返回2）。

7）输出最优极值和个体。

4 算法仿真

文中将云计算中的任务调度的个数模拟为蝙蝠的个数，将资源优化调度看成是蝙蝠个体搜索的过程，将满足资源调度公式（1）模拟为蝙蝠所处的位置的优劣。文中算法采用CloudSim[15]平台测试，CloudSim是由澳大利亚墨尔本大学和Gridbus共同推出的云计算仿真软件平台，实验环境为Windows 7操作系统，硬件主要包括i7CPU和8G DRR3，设定参数虚拟任务为500个，虚拟节点为8个，设置迭代次数为500，并将本文算法与PSO、GA在云计算模型中进行对比。

图1 3种资源负载算法任务完成时间比较

图2 3种资源负载算法能量消耗时间比较

从图1~3中可以看出，该算法在本文中的任务完成时间一开始差别不太明显。然而，随伴着任务数量的增加，所花费的时间比其他算法，在能量消耗方面明显减少，伴随着任务数量的不断增多，差异明显。在3种算法的资源开销方面，文中算法的时间开销优于其他的两种算法，并在一定程度上节省了资源分配的时间。

图3 3种资源负载算法开销时间比较

5 结束语

云计算环境资源分配是云计算效率的关键，文中是基于云计算环境下的资源分配研究，针对当前云计算资源调度算法存在收敛速度慢，资源利用率不足等缺陷，利用蝙蝠算法控制参数少、易于实现、计算简单等优点，提出了一种基于和声搜素算法的蝙蝠算法的云计算资源调度模型．仿真结果表明，相对于遗传算法和粒子群算法，文中算法不仅找到了理想的云计算资调度方案，任务完成时间急剧减少，而且克服了当前云计算资源调度算法存在的不足，提高了云计算资源利用率，在现代大规模云计算中有着广泛的应用前景。

[1]林伟伟，齐德昱.云计算资源调度研究综述[J].计算机科学，2012（10）:1-6.

[2]薛玉.云计算环境下的资源调度优化模型研究[J].计算机仿真，2013（5）:362-365.

[3]刘赛，李绪蓉，万麟瑞，等.云环境下资源调度模型研究[J].计算机工程与科学，2013（3）:48-51.

[4]Beloglazov A，Buyya R.Managing overloaded hosts for dynamic consolidation of virtual machines in cloud data centers underquality ofservice constraints[J].IEEE Transactions on Parallel& Distributed Systems，2013，24（7）:1366-1379.

[5]朱利华，李春华，吴宽仁.基于改进克隆选择算法的云计算集群资源调度[J].科学技术与工程，2013（13）:3642-3646.

[6]罗丹.云计算资源调度算法仿真[J].计算机仿真，2013（7）:280-283.

[7]孟令玺，李洪亮.基于CA-PSO算法的云计算资源调度策略[J].计算机仿真，2013（10）:406-410.

[8]Li-Hua G，Liying S，Sotaro C.Provisioning of requests for virtual machine sets with placement constraints in IaaS clouds[C].Integrated Network Management（IM 2013），2013 IFIP/IEEE International Symposium on.IEEE，2013:499-505.

[9]Yang X S.A new metaheuristic bat-Inspired algorithm[J].Science，2010（284）:65-74.

[10]Mirjalili S，Mirjalili S M，Yang X S.Binary bat algorithm[J].Neural Computing&Applications，2014，25（3-4）:663-681.

[11]Gandomi A H，Yang X S，Alavi A H，et al.Bat algorithm for constrained optimization tasks[J]. Neural Computing&Applications，2013，22（6）: 1239-1255.

[12]屈迟文，傅彦铭，侯勇顺.融合入侵杂草算子的蝙蝠算法[J].计算机应用与软件，2015（4）:243-246.

[13]Zong W G，Kim J H，Loganathan G V.A new heuristic optimization algorithm:harmony search. [J].Simulation Transactions of the Society for Modeling&Simulation International，2001，76（2）:60-68.

[14]雍龙泉.一种全局和声搜索算法求解绝对值方程[J].计算机应用研究，2013，30（11）:3276-3279.

[15]Calheiros R N，Ranjan R，De Rose C A F，et al. Cloudsim:A novel framework for modeling and simulation of cloud computing infrastructures and services[R].Technical report，Grids-TR-2009-1，Grid computing and distributed system laboratory，The University of Melbourne，Australia，2009.

Resource scheduling in cloud computing based on improved bat algorithm

LI Tian-chao，LI Shu-yu
（College of Computer Science，Shaanxi Normal University，Xi’an 710062，China）

In this paper，after in-depth research cloud computing task scheduling strategy in cloud computing environments，for cloud computing resource scheduling model，we propose a scheduling algorithm harmony algorithms and bat algorithm.In the solving process，by improving the average loudness bat position，to reduce the number of iterations.This improvement can be easily adjusted to provide discrete optimization problems bat algorithm to improve the convergence speed，shorten the running time of the algorithm.Realized bat algorithm optimization problem processing results.Simulation results show that the algorithm is effective scheduling algorithm in a cloud computing environment.

cloud computing；resource scheduling；bat algorithm；harmony algorithms

TN99

：A

：1674－6236（2017）01-0043-04

2016-01-14稿件编号：201601097

李天朝（1982—），男，陕西大荔人，硕士研究生。研究方向：云计算。