基于蝙蝠算法的云计算资源分配

1、蝙蝠算法在云计算资源分配中的研究朱莹1)1)东北大学秦皇岛分校 计算机与通信工程学院，河北 秦皇岛 摘 要 目前云计算面临着庞大的资源分配且具有动态性等特点，如果只从权衡资源分配策略的优劣出发已经不能满足需求。针对这一问题，从用户和资源提供者两个方面出发，将蝙蝠算法引入资源分配策略中，提出了以任务完成时间较短且成本最低为约束条件的调度模型。通过 CloudSim 平台进行模拟仿真表明，该资源分配算法能有效地兼顾完成时间和成本，在缩短任务完成时间的同时保证成本最小，提高了资源利用率。关键词 云计算; 资源调度; 蝙蝠算法; CloudSim 平台Study on Bat Algorithm in

2、 Cloud Computing Resources AllocationZhu Ying1)1)Computer and Communication Engineering of Northeastern University at Qinhuangdao ChinaAbstract: Because cloud computing faces the characteristics such as massive resource allocation and dynamic， it no longer meets the demand of weighing the pros and c

3、ons from single aspect From two aspects of users and resource providers to solve the above problems，this paper proposed a scheduling model with constraint conditions of shorter task-completion time and lower cost It brought the bat algorithm into resource allocation policy and modified its code desi

4、gn to improve the capacity of global optimization Finally，the simulation results depending on CloudSim platform show that the resource allocation algorithm can effectively take account of completion time and cost It improves resource utilization by shortening the time to complete the task while ensu

5、ring minimum cost，compared with particle swarm optimization algorithmKey words: cloud computing; resource scheduling; bat algorithm; CloudSim platform云计算是继分布式计算、网格计算、对等计算之后的一种新型计算模式，作为一种新型商业计算模式，是分布式并行处理和 网格计算等多种技术的拓展和延伸，代表了当前并行计算技术发展的新阶段。作为新兴产物，云计算涉及到的很多问题 并没有真正解决，资源调度便是其中的一个难题。资源调度作为云计算技术的一个重要组成部分

6、，其效率直接影响整个云计算环境的工作性能。由于云计算环境下的任务调度是一个 NP 完全问题，启发式智能算法在该领域研究是一个重要的方向之一。本文根据云环境对于资源分配的要求出发，通过深入地研究蝙蝠算法，结合云环境下任务调度的实际特点，首先建立了以时间和成本为双约束条件的资源调度模型，然后将蝙蝠算法应用在调度模型中，结果表明蝙蝠算法能够更有效地解决云计算中的资源调度问题。1 蝙蝠算法蝙蝠算法(Bat Algorithm，BA) 是由剑桥大学的Yang于2010 年提出的一种模拟蝙蝠捕食过程中所采用的回声定位原理的启发式智能算法。与现在诸多优化算法类似，蝙蝠算法也是一种基于种群的随机优化算法，蝙蝠

7、个体是蝙蝠算法的基本单元，在具体问题中赋以具体意义。Yang 在阐述蝙蝠算法基本思想的同时，提出了 蝙蝠算法基本假设条件。 1) 所有蝙蝠粒子利用自身回声定位感知与目 标之间的距离，同时以一种神秘的方式辨别目标和背景障碍物的不同。 2) 蝙蝠的位置为 xi，以速度 vi 任意地飞行，以 固定的频率 fmin、可变的波长 和响度 A0 搜寻目标。 它们可以判断自己与猎物之间的距离并自动地调整脉冲的波长( 亦或频率) ，同时在接近目标时调整脉冲的频度 r 0， 1。 3) 响度的变化方式有很多，这里假设它是从最 大的值( 正) A0 变化到固定的最小值 Amin。新型仿生智能算法蝙蝠算法( BA)

8、 的步骤用伪代码概括如下。 目标函数为 f( x) ， x =( x1， xd) T;初始化随机数rand；初始蝙蝠种群粒子 xi( i =1， 2， n) 和 vi;定义的脉冲的频率为 fi at xi;脉冲的频度- R(i) 响度-Ai 初始化。 While( t T 最大迭代次数) ，调整频率产生新解并更新位置和速度。 if ( rand R(i) 从最佳解的集合中选一个最佳解，从最佳解附近形成一个局部的最优解， else ( rand R(i) & f( xi) f( x* ) )接纳这个全新的解。 增大 R(i)，并减小 A(i)，排列当前蝙蝠粒子并找到当前最佳 x* ， 整理结果并

9、且可视化。 图1 蝙蝠算法模块化示意图1.1 蝙蝠的速度更新和位置更新假设搜索空间为 d 维，第 i 只蝙蝠在 t 时刻的位置为xit，速 度为vit，则在t+1 时刻的位置xit+1 和速度vit+1更新式为xitfi = fmin +( fmax fmin) vit+1 =vit +( xit x* ) fi xit+1= xit+ vit+1 其中: fi、 fmax和 fmin分别表示第 i 只蝙蝠在当前时刻发出的声波的频率、声波频率的最大值和最小值; 0，1是随机产生的数; x* 表示当前全局最优解。一旦从现有最优解集中选择一个解( 蝙蝠) ，这个解所在的新位置可通过式( 4) 产生

10、:xnewi=xold+At 这可以被理解成局部搜索，即在选择的解临近区域产生一个新解。其中， xold表示从当前最优解集中随机选择的一个解，At表示当前代蝙蝠种群响度的平均值为属于-1,1的 d 维随机向量。1.2响度和脉冲速率蝙蝠粒子发射的脉冲频度R(i) 和响度A(i) 的更新要随着迭代的进行而进行。通常，在不断靠近最优解时，响度会逐渐降低，脉冲发射的速率会逐渐提高， A(i) = 0 时表明蝙蝠 i 正好搜索到一个最优解，不再发出探测信号。式( 5) ( 6) 为脉冲响度和发射速率的更新方程。 At+1i=Ati Rt+1i=R0i1-exp-t 其中:0 1， 0，均为常量。 蝙蝠算

11、法中，脉冲频度增加系数 、脉冲音强衰减系数 对算法性能有重要影响。蝙蝠个体当前空间状态的改变方式 按照表达式 R ( i) 的真假来判定，其中 0， 1是一个随 机变量， R ( i) 是蝙蝠个体 i 当前的搜索脉冲频度，其计算方式 由式( 6) 可得。如果 R ( i) 成立，则第 i 只蝙蝠当前的空间状态由当前空间中最优解的附近产生; 如果 R ( i) 不成立， 则第 i 只蝙蝠当前的空间状态由式(5) 计算得到。2云环境下的资源分配现状云环境下的资源调度简单说来是通过择优选择，建立用户 请求列表到资源列表的映射。资源调度算法通常由优化目标 函数、选择和搜索过程组成，优化目标函数通常包括

12、时间跨度、 经济代价和资源利用情况等;选择和搜索过程是指在众多的可 选服务、资源映射方案中选择能使目标函数最优的那组值。这里重点关注任务调度和调度策略的实现。传统的任务调度往往只考虑任务的响应时间 或者是资源的利用率。这些调度算法在某些方面的表现优异，但系统运行时效率并不高。如何有效地利用云计算中的资源，使用户的需求在最大限度得到满足的情况下，让系统的性能保持最佳 成为一个亟待解决的关键问题。虚拟化技术的广泛使用使得云 计算中的资源呈现出动态多变、结构复杂等特点，在此分析基础 上，将云计算环境下用户提交的任务作下列两条假设: a) 用户提交的任务在虚拟机上处理时需要被分解为多个子任务，每个子任

13、务大致相等。b) 子任务的处理远多于虚拟机的个数，即任务需要按照 一定的调度顺序逐个处理。表1 表示的是虚拟机上的处理时间和处理成本。其中： ni 是用户提交任务的编号； mj 是任务处理虚拟机的编号； time (ni，mj ) 是第 i 个用户任务在第j个虚拟机上进行计算处理所花费的时间； cost(ni，mj ) 是第 i 个任务在第 j 个虚拟机上处理 所花费的成本。这个成本是多方面的，比如内存大小和带宽损 耗等。通常处理时间是针对用户，而处理成本则是针对资源提 供方，寻求二者的一个均衡是处理任务调度的一个重要方向。 表1 任务在虚拟机上的处理时间和处理成本任务虚拟机处理时间处理成本n

14、1m1time (n1，m1 )cost(n1，m1 )n2m2time (n2，m2 )cost(n2，m2 )nimjtime (ni，mj )cost(ni，mj )3 蝙蝠算法在云计算下资源分配模型设图 G =( V，E) 是一个有向完全图( directed acyclic graph，DAG) ，其中 V 是计算任务 v 的集合， E 是表示任务之间优先约束关系的边e的集合。节点 vi的权值表示任务 vi 的计算量。假设云计算资源中有 m 个不同的虚拟机，且虚拟机 mj的计算能力不同。每个任务可以在不同的虚拟机上执行，记 t(vi， mj) 表示任务 vi在虚拟机 mj上的执行时间

15、。 tvi， mj=任务vi的计算量虚拟机mj的计算能力 若任务执行方式是非抢占式的，则任务vi的平均执行时间为： Tvi=j=1mtvi， mjm 记有向边vi，vk的权重为 ctvi，vk，表示任务 vi 和任务vk的通信时间。如果 vi 和 vk 在同一个虚拟机执行，则 ctvi，vk = 0。任务 vi 的调度优先权的计算依赖 DAG 的逆向递推，即从最后一个节点开始，设vk是任务 vi的后继集合，有 Pvi=Tvi+maxctvi，vk+Pvk 从公式可以看出: vk是任务 vi的后继集合; vi的平均执行时间越长，且与vi后继节点中最大通信时间越久，优先权越低。通过计算优先权可以得

16、到整个图的关键路径，即整个资源分配调度关键任务的调度顺序。对云计算服务提供者来说，计算资源如虚拟机等，拥有不 同的计算能力和付费模式，而成本消耗主要取决于 CPU 的计算能力、内存的大小和带宽等因素。这里以 CPU 处理能力作为指标，选取线性模型来衡量成本消耗。任务 vi 在虚拟机 mj 上执行花费的成本： cvi， mj=tvi， mj标准CPU的基本计费 虚拟机mjCPU的计算能力标准CPU的计算能力 对于整个任务执行调度，兼顾其运行时间和成本最小的约束函数为 min time +( 1 ) cost 其中: 0， 1是权重因子，用来衡量用户和资源提供者的偏 好，即对执行时间和成本消耗的偏

17、重比例。当 = 0 或 = 1 时，问题退化为单纯的以任务完成时间最短或资源花费最少的 单目标约束问题。4 蝙蝠算法在云计算任务调度中的研究4.1 任务划分在当前的云计算环境中，谷歌公司提出的 MapReduce 调度机制被广泛地应用在各个平台中，用以处理大规模并行任务，其中 Map 的过程就是把一个大作业分解成多个子任务进 行处理，而任务划分的主要目标是尽可能地消除处理机之间的通信开销，一般要求尽可能使并行化最大，而任务之间的关联最小。4.2 云任务调度的具体步骤在云任务调度环境中，采用蝙蝠算法进行任务调度时，具体的步骤可以划分为如下七步:a) 接收用户提交的任务，并把每个任务划分为多个子任

18、务，每个子任务的规模大致相等，为每个子任务生成蝙蝠种群。b) 初始化蝙蝠种群中每个蝙蝠的脉冲频率 fi 和位置 xi， 搜索脉冲频率范围 fmin， fmax，音强衰减系数 ，频度增加系数 ，最大迭代次数。 c) 计算当前所有任务的优先权，并将任务按照优先权降序排列，对任务进行编码，根据式(2) 计算蝙蝠的飞行速度 vi，根据式(3) 更新蝙蝠的空间位置 xi。d) 产生随机数 ，如果 R ( i) ，则从当前最佳解集中选 取一个解，在选择的最佳解附近形成一个局部解，通过随机飞行产生一个新解。 e) 如果 R (i) 并且 f( xi) f( x* ) ，则接受这个新解，然 后增大 R (i)

19、 ，缩小 A(i) ，排列蝙蝠并找到当前最佳解 x* 。f) 判断是否满足终止条件，如果满足终止条件则转入 g) ， 否则转 c) 进行下一次搜索。 g) 输出全局最优解。 其中: R(i) 、 A(i) 、 f(xi) 分别表示第 i 只蝙蝠的发射 频度、脉冲的响度和当前位置目标函数的解。划分子任务，生成蝙蝠种群初始化蝙蝠种群中的参数并计算当前所有任务优先权当前迭代次数最大迭代次数 是 否更新位置和速度 输出当前解Xi 是 随机数 R ( i)增大 R (i)缩小 A(i) 否 输出最优解x* 是 是图2 蝙蝠算法在云计算资源分配示意图5 实验仿真CloudSim 是由澳大利亚墨尔本大学和

20、Gridbus 共同推出 的云计算仿真软件平台，目前最新版是CloudSim 3 0，本实验 就采用此平台进行模拟实验。通过对 bindCloudletToVm 方法的重写，实现不同的任务调度算法，对本文提出的基于蝙蝠算法的云计算任务调度算法进行仿真测试，并将结果与基于粒子 群算法的云任务调度结果进行比较。实验环境为 Windows 7 操作系统，处理器为英特尔 Core i5-2450M 2 50 GHz，内存为 4 GB。 为使本文提出的基于蝙蝠算法的调度方法和基于粒子群 算法的调度方法进行对比，本文先利用 CloudSim 对这两种调 度算法进行云计算环境下的实验模拟，然后在相同的实验平

21、台上对比这两种调度算法。算法各独立运行50 次。图1 反映的是线性模型情况下权重因子与最大完成时间 和成本之间的关系。从图中可以看出随着 w 的增加，最大完成时间呈递增趋势，而成本耗费呈递减趋势，这是因为 time 的 系数w 和cost 的系数是1w的原因。当w 在0 38 附近时，二 者达到一种兼顾均衡的状态。如果从博弈论的角度来考虑，对于用户和资源提供者而言，这是一种较优的理性状态，即最大完成时间和成本耗费的一个均衡态。图3 线性模型权重因子与时间和成本关系下面将比较PSO算法和BT算法在均衡状态下（即w=0.38）任务完成时间和任务完成消耗的比较。图2 反映的是权重因子 w = 0.3

22、8 时的任务完成总时间。图3 反映的是权重因子 w =0.38 时总任务完成成本消耗。图4 w=0.38 时的任务完成总时间 图5 w=0.38 时的任务完成成本综合图2、 3 可知，随着迭代次数的增加，PSO 算法与 BA 算法调度产生的总任务完成时间与总任务完成成本消耗都在逐渐减少，并且最终都收敛于某一特定值，但是在总任务完成时间以及总任务完成成本上，BA 调度算法产生的结果都要优于传统 PSO 算法的调度结果。6 结束语蝙蝠算法算是一种新型的仿生物学算法，将其与最近非常火的云计算相结合，简直闪瞎我这种小菜鸟的双眼。原谅我高中生物学得不好，对云计算的了解也只是蜻蜓点水，再此我还是要简单地概

23、述一下本文的中心思想，以及自己对BT算法核心的领悟。6.1 对BT算法核心的领悟把想象力打开，云计算中划分的子任务相当于一只只蝙蝠侠，处理任务的虚拟机相当于坏人，蝙蝠侠要不停的飞行去寻找一个凭自己的能力能解决的坏人，当他接近坏人时，就会慢慢的靠近，速度降低，翅膀震动的频率肯定要变高。给频率假定一个随机值（这个随机值可以理解为距自己心目中最佳坏人一定距离时翅膀震动频率），如果当前震动频率随机值，说明还没有达到抓坏人的最佳距离，就在周围区域找一个次最佳坏人（矬子里拔大个）；如果当前震动频率随机值，太好了，马上就要找到最佳坏人了，赶紧再飞慢点，频率接着增高，然后一点一点就抓到坏人了。6.2 中心思想-BT算法+图论=云计算资源分配路线BT算法大致意思弄明白了，我自己把公式一个一个敲出来，但是公式之间联系不是紧密。特别图论那部分我有点看