异构云中面向集群负载均衡任务调度策略

1、异构云中面向集群负载均衡任务调度策略摘要：负载均衡是提高资源利用率和系统稳定性的重要手段。基于改进的自适应变异粒子群算法，提出了 种异构环境下面向集群负载均衡的任务调度策略。在调度策 略的设计中，融入了经济学“二八”定律，通过把握用户对 集群节点安全性和可靠性的偏好程度并预估任务的负载信 息，在保证系统负载尽量均衡的前提下，最小化任务执行时 间的同时提高大客户满意度。仿真实验显示，改进的自适应 变异粒子群算法比未改进的自适应变异粒子群算法和基本 粒子群算法在收敛速度和跳出局部最优两个方面都有更好 的表现。结果表明，改进的自适应变异粒子群算法在保证集 群负载均衡的同时可以更好地提高云服务提供商的

2、利润空 间。关键词：负载均衡；任务调度；“二八”定律；异构； 自适应变异粒子群中图分类号：tp393. 027； tp18文献标志码：a0引言负载均衡是提高资源利用率和系统稳定性的重要手段， 是云计算相关研究的重点。负载均衡就是将系统流量按照节 点的实际情况均衡分配，使集群中资源的利用率得到提高目前针对负载均衡应用最多的两类策略是基于rr (round robin)算法和遗传算法(genetic algorithm, ga) 实现的2。其中rr算法通过将任务按照顺序依次分配给不 同的节点执行，具有简单快速的优点，但却因为无法随着系统负载的动态变化而自我调整，所以只适合于规模不大的任务调度3。使

3、用智能算法解决大规模系统的负载均衡问题 是近年来研究的热点，其中包括遗传算法、蚁群算法和粒子 群算法45 o文献6-7提出了用遗传算法来解决异构分布式系统中的调度问题。然而,遗传算法对新空间的探索能力是有限的，很容易收敛到局部最优解，出现“早熟”现象8。当涉及到大量个体的计算时，因为牵扯到交叉变异等复杂操作，使得算法无法在短时间内结束。与遗传算法相比, 粒子群算法具有更快的收敛速度，但也同样存在“早熟”现 象，尤其是处理多峰优化问题时9。文献10提出了使用 关系矩阵编码的粒子群算法解决负载均衡问题。在此基础 上，自适应变异粒子群算法(adaptive mutation particle swa

4、rm optimization, ampso)通过对全局最优位置 gbest 进行自适应变异操作，一定程度上增加了算法跳出局部最优 的能力，然而由于变异的随机性，使得很大程度上变异后的 解不如变异前的解更优，因此其跳出局部最优的能力也是有 限的。"二八”定律是经济学经典定律，由意大利经济学家帕 累托提出，它认为在任何一组东西中，最重要的只占其中一 小部分，约20%,其余的80%尽管是多数，却是次要的。与 此定律吻合，云服务提供商大多数的利润来源于一小部分长 期使用的客户，这部分客户可以称为大客户。在云计算中，“二八”定律强调了大客户的重要性，认为通过提高大客户 的满意度，能更好地增加

5、提供商的收益。因此，大客户满意 度在任务调度中是不容忽视的。此外，任务的执行时间反映 了任务的执行效率，所以缩短任务的执行时间也是任务调度 追求的目标之一。针对上述问题及相关启示，本文在自适应变异粒子群算 法的基础之上对其进行了改进，提出了一种异构集群环境中 面向集群负载均衡的任务调度模型和策略，通过在合适的时 机对合适的粒子进行变异，从而更大程度上增加了算法跳出 局部最优的能力。2. 2.2算法步骤将目标函数(6)作为粒子的适应度函数，对于不满足 约束的粒子，采用保留pbest值并重新初始化的方式对粒子 进行修复。基于此前的模型和描述，任务调度的步骤描述为:1) 为sjob集合中的每个任务分

6、配资源最适配的虚拟机, 指定代表大客户的用户等级1和可接受的负载方差上限oc。2) 在约束(7)和(8)允许的范围内，初始化各个粒 子的位置和速度，将粒子的pbest设置为当前位置，gbest 设置为初始粒子群中最佳粒子的位置。3）判断算法终止条件是否满足，如果满足则跳到10）, 否则执行4）。4）对每个粒子根据式（9）和（10）更新速度和位置， 通过式（4）计算当前调度方案下的集群负载方差。5）判断更新后的粒子是否满足约束（7）和（8）,如果 满足，则跳到7）,否则执行6）。6）保留该粒子的pbest值，对其循环进行重新初始化, 直到满足约束（7）和（8）时停止。7）通过式（6）计算粒子的适

7、应度，如果粒子适应度优 于pbest的适应度，则将pbest设置为新位置；如果粒子群 中最髙适应度优于gbest的适应度，则将gbest设置为新位 置。8）根据式（11）和（12）计算粒子群适应度方差o2, 根据式（13）计算变异概率pm。9）随机产生数rg0, 1,如果r但本文的重心放在了新模型和策略的阐述上，并没有对可以实现此策略的 其他算法进行深入的研究和比较，故无法得出一个最适合本 模型和策略的实现算法，这将是以后重点研究的方向。参考文献：1 刘晔，沈潇军，刘摩西，等基于云模式的资源调度 与负载均衡研究j电脑知识与技术，2011, 7 ( 33 )： 8208-8210.2 杨锦，李肯

8、立，吴帆，等异构分布式系统的负载均 衡调度算法j.计算机工程，2012, 38 (2)： 166-168.3 凌云，周华锋.面向异构集群系统的动态负载均衡技 术研究j计算机工程与设计,2008, 29 (12)： 3068-3070.4 张春艳，刘清林，孟珂，等基于蚁群优化算法的云 计算任务分配j计算机应用，2012, 32 (5)： 1418-1420.5 李建锋，彭舰.云计算环境下基于改进遗传算法的任 务调度算法j.计算机应用，2011, 31 (1)： 184-186.6 martino d, mililotti m. sub optimal scheduling in a grid u

9、sing genetic algorithmsj. parallel computing, 2004, 30 (5)： 553-565.7 andrew p , thomas n. framework for task scheduling in heterogeneous distributed computing using genetic algorithms j artificial intelligence review, 2005,24 (3)： 415-429.8 张铃，张钱.遗传算法机理的研究j.软件学报， 2000, 11 (7)： 945-9529 吕振肃，侯志荣.自适应变

10、异的粒子群优化算法j. 电子学报，2004, 32 (3)： 416-420.10 秦勇，宋继光，蔡昭权，等基于关系矩阵编码的 粒子群负载均衡算法研究j计算机应用与软件，2011, 28 (5)： 126-128.11jqin x , xie t. an availabi 1 ityaware task scheduling strategy for heterogeneous systems j ieee transactions on computers, 2008, 57(2)： 188-199.12fang y q, wang f, ge j w. a task scheduling

11、algorithm based on load balancing in cloud computing c/ web information systems and mining, lncs 6318 berlin： springer, 2010： 271-277.131tianwh, zhao y, zhong y l, et al. adynamic and integrated loadbalancing scheduling algorithm for cloud dat ace nt ers c / ccis 2011 ： proceedings of the 2011 ieee international conference on cloud computing and intelligence systems. piscataway： ieee, 2011： 311-315.14 hu j h, gu j h, sun g f, et al. a schedulingstrategy on load balancing of virtua.1 machine resources in cloud computing environment c/ paap 2010 :