 Computer Science and Application 计算机科学与应用, 2012, 2, 227-231 http://dx.doi.org/10.12677/csa.2012.24040 Published Online October 2012 (http://www.hanspub.org/journal/csa.html) Task Scheduling in Cloud Environment Based on Improved PSO Algorithm* Tingwei Chen, Yi Wei# Department of Information, Liaoning University, Shenyang Email: #Weiyi_811@126.com Received: Sep. 6th, 2012; revised: Sep. 27th, 2012; accepted: Oct. 7th, 2012 Abstract: In a cloud environment, how to map between tasks and resources efficiently has been a hot research topic. Bionic algorithm is widely used in task scheduling optimization, particle swarm optimization algorithm has been paid more attention by virtue of its simple structure, less parameters and easy to achieve. Standard particle swarm optimiza- tion algorithm, however, there are more local extreme in cloud computing environment, is prone to make the problem of “premature”, which is due to the lack of population diversity. Therefore, it is very important to maintain the diversity of the population in the search process, the paper put forward the idea of a “separatist”, the experiments show that the method can solve the problem of “premature” well, it is effective to maintain the diversity of the population, and reduce the completion time of the task effectively. Keywords: Cloud Computing; Task Scheduling; Particle Swarm Optimization; Division; Precocious 云环境下基于改进 PSO 算法的任务调度策略* 陈廷伟，韦 祎# 辽宁大学信息学院，沈阳 Email: #Weiyi_811@126.com 收稿日期：2012 年9月6日；修回日期：2012年9月27 日；录用日期：2012年10月7日 摘 要：在云环境中，如何高效的实现任务与资源之间的映射一直是研究的热点问题。仿生算法被广泛的应用 于任务调度的优化，其中粒子群优化算法凭借其结构简单、参数少和易实现的优点而受到大力重视。但是，标 准的粒子群优化算法对于存在较多局部极值云计算环境，很容易出现“早熟”的问题，这是由于种群多样性的 匮乏所致。因此，在搜寻过程中能够保持种群的多样性十分重要，本文提出了“分裂”的思想，经过实验证明， 该方法能够很好的解决“早熟”的问题，有效的保持种群多样性，并能有效的减少任务的完成时间。 关键词：云计算；任务调度；粒子群优化算法；分裂；早熟 1. 引言 云计算作为一种新兴的并行计算技术，是分布式 处理、并行处理、网格计算的发展和延伸，是这些计 算机科学概念的商业实现，适合当今巨型信息化处理 需求[1]。云计算提供了更可靠、更安全的存储和计算 数据能力、简化计算交付、降低成本、具有更高的扩 展性和灵活性。 云计算环境与网格计算环境还有着较大的差别， 云的规模较大，其云计算技术的硬件基础设施构建在 大规模的廉价服务器集群之上，所以各个节点的计算 能力稍低。如何利用有限的资源为用户提供高质量的 服务，是云计算需要解决的重要问题。因此，任务调 度是云计算的一个重要组成部分。如何高效且快速实 现任务与资源之间的映射是研究的重点所在。 *基金项目：辽宁省教育厅科学研究一般项目(L2011004)。 #通讯作者。 Copyright © 2012 Hanspub 227  云环境下基于改进 PSO 算法的任务调度策略 2. 改进的 PSO 算法 粒子群优化算法(Particle Swarm Optimization，简 称PSO)最早是由Eber hart和Kennedy 模拟自然界的 生物群体觅食而提出的一种优化方法[2]。PSO 算法是 一种基于群体的自适应搜索优化算法，其核心思想是 群体中个体之间的信息共享有助于整体进化[3]。 在算法中，这些称为“群(Swarm)”的无体积无 质量的小粒子都具有记忆的能力，能对自身位置和记 忆中经历过的最佳位置进行调整，进而能够调整自身 的运动轨迹，同时能够朝着自己以前经历过的最佳位 置和整个群体粒子曾经经历过的最佳位置飞行，通过 迭代越来越接近最佳位置，最终得到最优解。它具有 参数少、易实现的优点，但是，粒子群优化算法也具 有自身的不足，该算法在优化过程中容易出现早熟的 问题，这主要是由于在粒子群优化的后期由于各个粒 子的速度更新能力不足，使得粒子在一定位置紧密聚 集而无法进行更大程度、更细致的全局搜索，从种群 多样性而言，此时种群的多样性匮乏，各个粒子之间 的差别很小，无法促使粒子群发展变化[4]。 因此，我将“分裂”的思想引入到了PSO 算法中， 用以保持种群的多样性，防止算法过早产生收敛。 假设有 N个粒子在 D维空间进行搜索，则粒子i 的速度和位置可以采用如下形式表示[5]： 12 12 ,,, ,,, iii id iii id vvv v x xx x 其中，1 ≤ i ≤ N，1 ≤ d ≤ D。 算法步骤如下： 1) 初始化每个粒子的速度 和位置 i vi x 。当前位 置i x 则为该粒子目前为止本身最优位置 。根据适应 度函数可以得到当前的全局最优位置 i p g p。 2) 判断 和 i p g p之间的欧式距离 和适应度函 数差值与阈值之间的关系。 1 d 当二者之间距离过大且适应度函数的差值很小 时，证明在距离当前全局最优位置很远的地方也有一 个十分优秀的解存在。为了避免陷入局部最优和保持 种群的多样性，此时可以将粒子“分裂”为二，一个 朝着全局最优位置的方向运动，另一个朝着粒子本身 的最优位置的方向运动。 1 是限定 与 i p g p之间欧式距离 1的阈值。d2 是 限定适应度函数之间差值的阈值。 在标准 PSO 算法中的速度更新公式如下： 1 112 2 tt ttt ididid idgd id vvcrpxcrpx t (1) 其中 1 ≤ d ≤ D，1 ≤ I ≤ N，是 t时刻粒子本身的最 优位置的第 d维变量， t id p t g d 0 0 p 2 c 1 2 c 是t时刻粒子群全局最优 位置的第d维变量，和是学习因子， 和是(0,1) 区间上的随机数。如果 c，则粒 子只“向社会 学 习”，收敛速度可能很快但容易陷入局部最优，导致 “早熟”的问题。如果 ，则粒子只“向本身学 习”，粒子之间将没有信息交流，导致得到解的几率 很小[4]。 1 c1 r2 r 当s > 1 且适应度函数的差值小于2 时，该粒子 “分裂”为两个粒子。分别令和等于0来采用不 同的速度更新公式，使其分别向全局最优位置和本身 最优位置的方向运动。 1 c2 c 1 22 tt t ididgd id vvcrpx t t 1 (2) 1 11 tt t ididid id vvcrpx (3) 其它情况时，则采取标准PSO 算法中的更新公式 (1)进行更新。 3) 更新粒子的位置： 1ttt idid id x xv (4) 4) 判断是否符合结束条件。如果适应度函数的值 小于允许误差或达到最大迭代次数则停止迭代，输出 最优解。否则，重复步骤2)和3)。 3. 基于改进 PSO 算法的云任务调度策略 云环境下的任务调度是以任务为出发点，其实质 是将相互独立的任务映射到多个可用的资源上，使任 务能够高效率高质量的完成。 目前，大部分云计算平台都采用Google 提出的 Map/Reduce编程模型，用于大规模数据集的并行计 算。通过Map和Reduce 两个阶段，将较大的任务分 割成为多个较小的子任务，然后分配给多个资源并行 执行，并得到最终的运行结果。在 Map/Reduce编程 模型下，如何对数量众多的子任务进行调度是个复杂 的问题[6]。PSO 算法是一种群智能算法[7]，能够很好 的解决云环境下的任务调度这一复杂的问题。 Copyright © 2012 Hanspub 228  云环境下基于改进 PSO 算法的任务调度策略 3.1. 云中任务和资源的描述形式 用户提交的任务T划分为 m个子任务，1 ≤ i ≤ m。则任务 T可表示为 。每一个子任 务都应该有对资源的需求条件，则 ，分别表示其对资源节点 cpu、内存、网卡、硬盘和带宽的要求， 为该子任 务所产生的含有n个粒子的粒子群，表示为 ，1 ≤ j ≤ n， ，表示第 i个子任务产生 的第 j个粒子。 是该粒子的本身最优位置， i t i p 12 ,, , m Tttt , t i tP ij p ,,,, iicpu imen ina iio ine ttttt 12 ,,, iii ij ppp p ,,, ijiijijij i pthopexvp ij i pij x 和 表示第 i个子任务产生的第 j个粒子的位置和速度： ij v 12 ,,, ijijijij d vvv v 12 ,,, ijijijijd xxx x 云中资源节点集合为 12 ,, , q Ssss , t ilocation s i ，q为资源 节点个数。每个资源节点表示为 ，其 中i = 1,2,…,q， 分别用来描述该资源节点的cpu 处理能力、内存、网 卡、硬盘和带宽属性。资源 ,,,, iicpu imem inaiioine ssssss s 在D维空间中的位置表 示为： , id12 ,, ilocationii s sss。 云环境中粒子和资源之间的距离表示为 ： 2 d 2 2 1 d ij ij j dxs (5) 3.2. 云中任务调度问题的适应度函数 根据子任务对资源各个属性的需求情况，可以得 到子任务 对资源的综合期望： i t 22 222 icpuimem inaiio inet i atbtctdt et thope abcde (6) 其中，a、b、c、d、e为对应的权值，满足条件a + b + c + d + e = 1。 云中每个资源 i s 的资源综合性能可以表示为： 22 222 icpuimem inaiioinet i s ssss sproperty (7) 其中，α、β、γ、χ、δ分别为对应权值，满足条件α + β + γ + χ + δ = 1。 在云环境下任务调度这一问题中，适应度函数应 该把任务与资源之间的匹配程度作为衡量标准，所以 函数如下： 23 min i di F thope sproperty (8) 其中， 3 是限制粒子与资源之间距离的阈值。 3.3. 云中任务调度的具体步骤 在云计算环境中，在采用基于“分裂”思想的 PSO 算法进行任务调度时，具体步骤可以划分为如下五 步： 1) 接收用户提交的任务，并把每个任务划分为 m 个子任务，为每个子任务生成粒子群。 2) 初始化粒子群中每个粒子的速度 和位置 ij v ij x 。在当前时刻，第 i个子任务的第 j个粒子的本身 最优位置 ij iij px 。利用上述适应度函数(8)，可 以 得 到当前第 i个子任务产生的所有粒子的全局最优位置 i pg 。 3) 判断 ij i p 和ig p 之间的欧式距离 和适应度 函数差值与阈值 1 d 1 、2 之间的关系。 当1 d1 且F之差 2 时，开始“分裂”为两个 粒子，分别采用新的速度更行公式： 1 22 tt tt ij dij di gdijd vvcrpx 1 (9) 1 11 tt tt ij dij diji dijd vvcrpx (10) 其它情况时，则采取标准PSO 算法中的速度更新 公式： 1 11 22 tt tt ij dij diji dijd tt igd ijd vvcrpx cr px (11) 4) 更新每个粒子的位置，公式如下： 1ttt ij dij dij d x xv (12) 5) 判断是否满足结束条件。 如果 20d 且4 F (4 是适应度函数的最大允 许误差)，表示粒子到达了一个合适资源的位置，即已 经找到合适的资源，则把任务分配到该资源节点执 行，结束搜寻。 如果迭代次数超过最大迭代次数 5 ，则也结束搜 寻，重新初始化粒子群，重复步骤2)、3)和4)。 如果上述两个条件都不满足，则继续迭代，重复 步骤 2)、3)和4)。 Copyright © 2012 Hanspub 229  云环境下基于改进 PSO 算法的任务调度策略 4. 仿真实验结果 为了验证改进后的基于“分裂”思想的 PSO算法， 采用了 CloudSim[8]做模拟，并将其与标准PSO 算法、 遗传算法和蚁群算法进行比较。 采用 30个资源节点来模拟实验，cpu度量为频率 系数，内存度量为容量系数，硬盘为I/O 读取系数， 网卡为通信速度系数，带宽为带宽系数(如表1所示)。 权值 a、b、c、d、e、α、β、γ、χ和σ均取 0.2。 经过反复多次试验，最终选取各个阈值的值如下： Table 1. the description of resource node attribute parameter 表1. 资源节点的属性参数描述 资源节 点编号 cpu(G) Mem(G) na(m/s) i/o(m/s) Net(m/s) 1 2.4 1 100 300 100 2 1.6 1 100 300 100 3 1.6 1 100 300 100 4 2.2 1 100 300 100 5 4.2 1 100 300 100 6 4.2 1 100 300 100 7 1.6 0.5 100 300 100 8 1.8 0.5 100 300 100 9 1.8 0.5 100 300 100 10 4.2 1 100 300 100 11 7.2 3.6 100 300 100 12 7.2 3.6 100 300 100 13 4.4 1 100 300 100 14 4.4 1 100 300 100 15 4.4 0.5 1000 300 100 16 4.6 1 1000 150 100 17 4.6 1 1000 150 100 18 4.6 1 1000 150 100 19 1.6 0.5 100 150 100 20 4.2 1 1000 150 100 21 4 0.25 100 150 100 22 3 0.25 100 150 100 23 3 0.25 100 150 100 24 2.8 0.25 100 150 100 25 4.6 1 100 150 100 26 3 0.5 100 150 100 27 3 0.5 100 150 100 28 2.8 1 100 150 100 29 3 0.5 100 150 100 30 3 0.5 100 150 100 131 4 24 5 100, 4.025.0, 0.2, 20.4, 30 提交任务大小为200 M，划分为 10个子任务进行 处理，为每个子任务生成 10 个粒子，随机初始化每 个粒子的位置和速度。 4.1. 与标准 PSO 算法在解决早熟问题上的比较 如图 1所示，标准PSO 算法在迭代到第 14 次时， 适应度函数的值小于允许误差而停止迭代，最优资源 的适应度函数值为0.17。改进后的基于“分裂”思想 的PSO 算法在迭代 13 次时找到了最优资源，适应度 函数值为 0.12，可见该资源优于标准PSO 算法找到的 资源。为了验证改进后的基于“分裂”思想的 PSO 算 法没有造成“早熟”，对其又进行了10 次迭代，发现 适应度函数的值没有发生变化，这证明改进后的算法 在解决“早熟”问题上十分有效，很好的保持了种群 的多样性。 4.2. 与标准 PSO 算法、遗传算法和蚁群算法 在任务完成时间方面的比较 提交五个任务大小分别为：50 M、100 M、150 M、 200 M和250 M。分别采用不同的算法，记录 5个任 务的完成时间。 如图 2所示，改进后的基于“分裂”思想的 PSO 算法与其他三种算法相比在完成时间上有明显的减 少。由于改进后的算法在特定情况下将粒子一分为 二，从而增加了粒子的数目，粒子之间的共享信息也 有所增加，这将有利于提高搜寻的速度，搜索时间也 有所减少。 0 2 4 6 8 10 12 14 16 18 20 0510 1520 25 30 迭代次数 适应度函数值 标准PSO 分裂PSO Figure 1. Comparison of the “Separatist” PSO algorithm and standard PSO algorithm on the problem of “premature” 图1. “分裂”PSO 算法与标准 PSO 算法在“早熟”问题上的比 较 Copyright © 2012 Hanspub 230  云环境下基于改进 PSO 算法的任务调度策略 Copyright © 2012 Hanspub 231 6. 致谢 0 50 100 150 200 250 300 350 400 450 500 50100 150200 250 任务大小/M 完成时间/ms 遗传 蚁群 标准PSO “分裂”PSO 本文获得了“辽宁省教育厅科学研究一般项目 (L2011004)”基金项目的支持，在此深表感谢。 参考文献 (References) [1] 郭本俊, 王鹏, 陈高云等 . 基于 MPI 的云计算模型[J]. 计算 机工程, 2009, 35(24): 84-86. Figure 2. Comparison of the “Separatist” PSO algorithm, the standard PSO algorithm, genetic algorithm and ant colony algorithm in task completion time [2] J. Kenney, R. C. Eberhart. Particle swarm optimization. Institute of Electrical and Electronics Engineers, 1995, 11: 1942-1948. [3] 李丽, 牛奔. 粒子群优化算法[M]. 北京: 冶金工业出版社, 2009: 10-26. 图2. “分裂”PSO 算法与标准 PSO 算法、遗传算法和蚁群算法 在任务完成时间方面的比较 [4] 毛恒. 粒子群优化算法的改进及应用研究[D]. 华侨大学, 2007. [5] 韦杏琼, 周永权, 黄华娟等. 云自适应粒子群算法[J]. 计算 机工程与应用, 2009, 45(1): 48-50. 5. 结论 [6] S. Chemawat, H. Gobioff and T. Shun. The google file system. ACMSIGOPS Operating Systems Review, 2003, 37(5): 29-43. 通过实验可以验证，基于“分裂”思想的 PSO算 法很好的解决了标准PSO 算法容易“早熟”的问题， 有效的保持了种群的多样性。这将有利于提高任务和 资源之间的匹配度和缩小完成任务的时间。与其他仿 生算法相比，基于“分裂”思想的 PSO 算法能够比遗 传算法和蚁群算法更快的完成任务与资源节点之间 的映射。 [7] 高尚, 杨静宇. 群智能算法及其应用[M]. 北京: 中国水利水 电出版社, 2006: 1-2. [8] R. N. Calheriros, R. Ranjan and R. Buyya. CloudSim: A novel framework for modeling and simulation of cloud computing in- frastructures and services. Melbourne: Grid Computing and Dis- tributed Systems Laboratory, The University of Melbourne, 2009. |