搜索
蝙蝠算法在云计算资源分配中的研究朱莹1)1)东北大学秦皇岛分校计算机与通信工程学院，河北秦皇岛066004摘要目前云计算面临着庞大的资源分配且具有动态性等特点，如果只从权衡资源分配策略的优劣出发已经不能满足需求。针对这一问题，从用户和资源提供者两个方面出发，将蝙蝠算法引入资源分配策略中，提出了以任务完成时间较短且成本最低为约束条件的调度模型。通过CloudSim平台进行模拟仿真表明，该资源分配算法能有效地兼顾完成时间和成本，在缩短任务完成时间的同时保证成本最小，提高了资源利用率。关键词云计算;资源调度;蝙蝠算法;CloudSim平台StudyonBatAlgorithminCloudComputingResourcesAllocationZhuYing1)1)ComputerandCommunicationEngineeringofNortheasternUniversityatQinhuangdao066004ChinaAbstract:Becausecloudcomputingfacesthecharacteristicssuchasmassiveresourceallocationanddynamic，itnolongermeetsthedemandofweighingtheprosandconsfromsingleaspect．Fromtwoaspectsofusersandresourceproviderstosolvetheaboveproblems，thispaperproposedaschedulingmodelwithconstraintconditionsofshortertask-completiontimeandlowercost．Itbroughtthebatalgorithmintoresourceallocationpolicyandmodifieditscodedesigntoimprovethecapacityofglobaloptimization．Finally，thesimulationresultsdependingonCloudSimplatformshowthattheresourceallocationalgorithmcaneffectivelytakeaccountofcompletiontimeandcost．Itimprovesresourceutilizationbyshorteningthetimetocompletethetaskwhileensuringminimumcost，comparedwithparticleswarmoptimizationalgorithm．Keywords:cloudcomputing;resourcescheduling;batalgorithm;CloudSimplatform云计算是继分布式计算、网格计算、对等计算之后的一种新型计算模式，作为一种新型商业计算模式，是分布式并行处理和网格计算等多种技术的拓展和延伸，代表了当前并行计算技术发展的新阶段。作为新兴产物，云计算涉及到的很多问题并没有真正解决，资源调度便是其中的一个难题。资源调度作为云计算技术的一个重要组成部分，其效率直接影响整个云计算环境的工作性能。由于云计算环境下的任务调度是一个NP完全问题，启发式智能算法在该领域研究是一个重要的方向之一。本文根据云环境对于资源分配的要求出发，通过深入地研究蝙蝠算法，结合云环境下任务调度的实际特点，首先建立了以时间和成本为双约束条件的资源调度模型，然后将蝙蝠算法应用在调度模型中，结果表明蝙蝠算法能够更有效地解决云计算中的资源调度问题。1蝙蝠算法蝙蝠算法(BatAlgorithm，BA)是由剑桥大学的Yang于2010年提出的一种模拟蝙蝠捕食过程中所采用的回声定位原理的启发式智能算法。与现在诸多优化算法类似，蝙蝠算法也是一种基于种群的随机优化算法，蝙蝠个体是蝙蝠算法的基本单元，在具体问题中赋以具体意义。Yang在阐述蝙蝠算法基本思想的同时，提出了蝙蝠算法基本假设条件。1)所有蝙蝠粒子利用自身回声定位感知与目标之间的距离，同时以一种神秘的方式辨别目标和背景障碍物的不同。2)蝙蝠的位置为xi，以速度vi任意地飞行，以固定的频率fmin、可变的波长λ和响度A0搜寻目标。它们可以判断自己与猎物之间的距离并自动地调整脉冲的波长(亦或频率)，同时在接近目标时调整脉冲的频度r∈［0，1］。3)响度的变化方式有很多，这里假设它是从最大的值(正)A0变化到固定的最小值Amin。新型仿生智能算法－蝙蝠算法(BA)的步骤用伪代码概括如下。目标函数为f(x)，x=(x1，…，xd)T;初始化随机数rand；初始蝙蝠种群粒子xi(i=1，2，…，n)和vi;定义的脉冲的频率为fiatxi;脉冲的频度----R(i)响度----Ai初始化。While(t＜T最大迭代次数)，调整频率产生新解并更新位置和速度。if(rand＞R(i))从最佳解的集合中选一个最佳解，从最佳解附近形成一个局部的最优解，else(rand＜R(i)&&f(xi)＜f(x*))接纳这个全新的解。增大R(i)，并减小A(i)，排列当前蝙蝠粒子并找到当前最佳x*，整理结果并且可视化。图1蝙蝠算法模块化示意图1.1蝙蝠的速度更新和位置更新假设搜索空间为d维，第i只蝙蝠在t时刻的位置为𝑥𝑖𝑡，速度为𝑣𝑖𝑡，则在t+1时刻的位置𝑥𝑖𝑡+1和速度𝑣𝑖𝑡+1更新式为𝑥𝑖𝑡𝑓𝑖=𝑓𝑚𝑖𝑛+(𝑓𝑚𝑎𝑥－𝑓𝑚𝑖𝑛)β⑴𝑣𝑖𝑡+1=𝑣𝑖𝑡+(𝑥𝑖𝑡－x∗)𝑓𝑖⑵𝑥𝑖𝑡+1=𝑥𝑖𝑡+𝑣𝑖𝑡+1⑶其中:𝑓𝑖、𝑓𝑚𝑎𝑥和𝑓𝑚𝑖𝑛分别表示第i只蝙蝠在当前时刻发出的声波的频率、声波频率的最大值和最小值;β∈［0，1］是随机产生的数;x∗表示当前全局最优解。一旦从现有最优解集中选择一个解(蝙蝠)，这个解所在的新位置可通过式(4)产生:𝑥𝑛𝑒𝑤(𝑖)=𝑥𝑜𝑙𝑑+𝜀𝐴𝑡⑷这可以被理解成局部搜索，即在选择的解临近区域产生一个新解。其中，𝑥𝑜𝑙𝑑表示从当前最优解集中随机选择的一个解，𝐴𝑡表示当前代蝙蝠种群响度的平均值𝜀为属于[-1,1]的d维随机向量。1.2响度和脉冲速率蝙蝠粒子发射的脉冲频度R(i)和响度A(i)的更新要随着迭代的进行而进行。通常，在不断靠近最优解时，响度会逐渐降低，脉冲发射的速率会逐渐提高，A(i)=0时表明蝙蝠i正好搜索到一个最优解，不再发出探测信号。式(5)(6)为脉冲响度和发射速率的更新方程。𝐴𝑡+1(𝑖)=𝛼𝐴𝑡(𝑖)⑸𝑅𝑡+1(𝑖)=𝑅0(𝑖)×[1−𝑒𝑥𝑝(−𝛾𝑡)]⑹其中:0＜𝛼＜1，𝛾＞0，均为常量。蝙蝠算法中，脉冲频度增加系数𝛾、脉冲音强衰减系数𝛼对算法性能有重要影响。蝙蝠个体当前空间状态的改变方式按照表达式β＞R(i)的真假来判定，其中β∈［0，1］是一个随机变量，R(i)是蝙蝠个体i当前的搜索脉冲频度，其计算方式由式(6)可得。如果β＞R(i)成立，则第i只蝙蝠当前的空间状态由当前空间中最优解的附近产生;如果β＞R(i)不成立，则第i只蝙蝠当前的空间状态由式(5)计算得到。2云环境下的资源分配现状云环境下的资源调度简单说来是通过择优选择，建立用户请求列表到资源列表的映射。资源调度算法通常由优化目标函数、选择和搜索过程组成，优化目标函数通常包括时间跨度、经济代价和资源利用情况等;选择和搜索过程是指在众多的可选服务、资源映射方案中选择能使目标函数最优的那组值。这里重点关注任务调度和调度策略的实现。传统的任务调度往往只考虑任务的响应时间或者是资源的利用率。这些调度算法在某些方面的表现优异，但系统运行时效率并不高。如何有效地利用云计算中的资源，使用户的需求在最大限度得到满足的情况下，让系统的性能保持最佳成为一个亟待解决的关键问题。虚拟化技术的广泛使用使得云计算中的资源呈现出动态多变、结构复杂等特点，在此分析基础上，将云计算环境下用户提交的任务作下列两条假设:a)用户提交的任务在虚拟机上处理时需要被分解为多个子任务，每个子任务大致相等。b)子任务的处理远多于虚拟机的个数，即任务需要按照一定的调度顺序逐个处理。表1表示的是虚拟机上的处理时间和处理成本。其中：𝑛𝑖是用户提交任务的编号；𝑚𝑗是任务处理虚拟机的编号；time(𝑛𝑖，𝑚𝑗)是第i个用户任务在第j个虚拟机上进行计算处理所花费的时间；cost(𝑛𝑖，𝑚𝑗)是第i个任务在第j个虚拟机上处理所花费的成本。这个成本是多方面的，比如内存大小和带宽损耗等。通常处理时间是针对用户，而处理成本则是针对资源提供方，寻求二者的一个均衡是处理任务调度的一个重要方向。表1任务在虚拟机上的处理时间和处理成本任务虚拟机处理时间处理成本𝒏𝟏𝑚1time(𝑛1，𝑚1)cost(𝑛1，𝑚1)𝒏𝟐𝑚2time(𝑛2，𝑚2)cost(𝑛2，𝑚2)…………𝒏𝒊𝑚𝑗time(𝑛𝑖，𝑚𝑗)cost(𝑛𝑖，𝑚𝑗)3蝙蝠算法在云计算下资源分配模型设图G=(V，E)是一个有向完全图(directedacyclicgraph，DAG)，其中V是计算任务v的集合，E是表示任务之间优先约束关系的边e的集合。节点𝑣𝑖的权值表示任务𝑣𝑖的计算量。假设云计算资源中有m个不同的虚拟机，，且虚拟机𝑚𝑗的计算能力不同。每个任务可以在不同的虚拟机上执行，记t(𝑣𝑖，𝑚𝑗)表示任务𝑣𝑖在虚拟机𝑚𝑗上的执行时间。t(𝑣𝑖，𝑚𝑗)=任务vi的计算量虚拟机𝑚𝑗的计算能力⑺若任务执行方式是非抢占式的，则任务𝑣𝑖的平均执行时间为：𝑇𝑣𝑖=∑t(𝑣𝑖，𝑚𝑗)𝑚𝑚𝑗=1⑻记有向边〈𝑣𝑖，𝑣𝑘〉的权重为𝑐𝑡𝑣𝑖，𝑣𝑘，表示任务𝑣𝑖和任务𝑣𝑘的通信时间。如果𝑣𝑖和𝑣𝑘在同一个虚拟机执行，则𝑐𝑡𝑣𝑖，𝑣𝑘=0。任务𝑣𝑖的调度优先权的计算依赖DAG的逆向递推，即从最后一个节点开始，设𝑣𝑘是任务𝑣𝑖的后继集合，有𝑃𝑣𝑖=𝑇𝑣𝑖+𝑚𝑎𝑥(𝑐𝑡𝑣𝑖，𝑣𝑘+𝑃𝑣𝑘)⑼从公式可以看出:𝑣𝑘是任务𝑣𝑖的后继集合;𝑣𝑖的平均执行时间越长，且与𝑣𝑖后继节点中最大通信时间越久，优先权越低。通过计算优先权可以得到整个图的关键路径，即整个资源分配调度关键任务的调度顺序。对云计算服务提供者来说，计算资源如虚拟机等，拥有不同的计算能力和付费模式，而成本消耗主要取决于CPU的计算能力、内存的大小和带宽等因素。这里以CPU处理能力作为指标，选取线性模型来衡量成本消耗。任务vi在虚拟机mj上执行花费的成本：c(𝑣𝑖，𝑚𝑗)=t(𝑣𝑖，𝑚𝑗)×标准CPU的基本计费×虚拟机𝑚𝑗CPU的计算能力标准CPU的计算能力⑽对于整个任务执行调度，兼顾其运行时间和成本最小的约束函数为min{ω×time+(1－ω)×cost}⑾其中:ω∈［0，1］是权重因子，用来衡量用户和资源提供者的偏好，即对执行时间和成本消耗的偏重比例。当ω=0或ω=1时，问题退化为单纯的以任务完成时间最短或资源花费最少的单目标约束问题。4蝙蝠算法在云计算任务调度中的研究4.1任务划分在当前的云计算环境中，谷歌公司提出的MapReduce调度机制被广泛地应用在各个平台中，用以处理大规模并行任务，其中Map的过程就是把一个大作业分解成多个子任务进行处理，而任务划分的主要目标是尽可能地消除处理机之间的通信开销，一般要求尽可能使并行化最大，而任务之间的关联最小。4.2云任务调度的具体步骤在云任务调度环境中，采用蝙蝠算法进行任务调度时，具体的步骤可以划分为如下七步:a)接收用户提交的任务，并把每个任务划分为多个子任务，每个子任务的规模大