论文部分内容阅读
[摘 要]在云计算环境中，存在非常多的用户，因而系统处理存在非常大的任务量。为了实现系统能够对服务请求的高效执行，云计算研究的重点问题就是任务调度问题。文章提出了一种基于粒子群优化和蚁群优化的任务调度算法，在CloudSim 平台进行了仿真实验之后，发现这一算法的实时性和寻优能力很好，是有效的调度算法。
[关键词]粒子群优化；蚁群优化；云计算；任务调度
中图分类号：TP301.6 文献标识码：A 文章编号：1009-914X（2015）30-0127-01
云计算发展融合了传统计算机和网络技术，是一种商业实现。基于互联网的计算服务模式，针对一些共享可配置计算资源实现了方便、按需访问；这些资源可借助非常小的管理代价或与服务提供者的交互被快速地准备和实现按需使用[1]。目前用于求解云计算任务调度问题的算法有遗传算法、粒子群优化算法和蚁群算法。在前人研究的基础上提出一种基于粒子群优化与蚁群优化的云计算任务调度算法。
1 云计算任务调度的设计
粒子群优化算法是1995年Kennedy和Eberhart提出的，是受启发于鸟群觅食行为的的一种仿生优化算法。因为该算法简单、易实现且参数少，因而可以实现良好的连续优化和离散优化效果。蚁群算法是上世纪90年代DorigoMacro等人提出的，受启发于模拟蚂蚁群体觅食行为，也是一种仿生优化算法。这两种算法也存在一些不足之处。本文与两种算法的优势相结合，提出基于两种算法的一种云计算任务调度算法。这一算法先是借助粒子群优化算法的快速收敛性迅速生成初始解，接下来依据调度结果生成蚁群算法的初始信息素分布，最后是借助蚁群算法来将任务调度的最优解求出来。
1.1 粒子群算法
云计算任务调度问题是离散问题，而粒子群优化算法对于连续优化问题的解决比较适用。在离散版的粒子群算法中，将粒子位置向量每一位值取0或1，粒子速度不是对连续空间中粒子飞行的速度的表示，而且表示计算粒子位置向量取值为0或1的概率。
1.2 蚁群算法
以云计算任务调度的任务与资源分配关系矩阵X为参照，定义{xij}m×n为节点集，组成一个无向完全图G（V，E）。通过蚁群算法从集合{xij}m×n中选出一组节点{xy11，xy22，…，xyjj，…，xynn}，yj∈{1，2，…，m}，从而实现最小的Cmax值。
1.3 算法流程
在粒子群优化和蚁群优化基础上提出的云计算任务调度算法，其基本步骤是
这样的：
Step1对云计算任务调度目标函数进行定义。
Step2针对该调度算法，进行相关参数和算法结束条件的设定。
Step3随即初始化粒子群的位置和速度。
Step4对每个粒子的适应值进行计算，将粒子个体最优位置和群体最优位
置找出来。
Step5按照式（6）、式（7）来更新粒子速度和位置。
Step6没有动作。
Step7若是已达设定迭代次数，将云计算任务调度的初始调度结果输出，并转到Step8。要不然就跳转至Step4。
Step8按照粒子群算法得出的初始调度结果来初始化蚁群算法的信息素进。
Step9随机放置若干只蚂蚁到节点上并搜索。
Step10每只蚂蚁按照式（8）进行下一节点的选择，并按照式（10）、式
（11）对局部信息素进行更新，将调度列表中加入所选节点。
Step11完成全部任务调度后，按照任务调度列表对调度结果的适应值进行
计算，同时按照式（12）、式（13）对全局信息素进行更新。
2 实验与分析
CloudSim是澳大利亚RajkumarBuyya博士领导团队开发出来的一个云计算仿真平台。其主要是对云环境进行模拟，针对不同的调度策略做性能测试。本文也是采用CloudSim平台来进行云环境的模拟，对任务调度算法进行模拟仿真。为了对本文调度算法的性能进行有效检验，分别于5个虚拟计算资源、50个子任务和5个虚拟计算资源、500个子任务两种调度规模下，分别进行对比实验，包括粒子群优化算法（PSO）、蚁群算法（ACO）和本文算法（PSO-ACO）[2]。在实验中，各虚拟计算资源的处理能力是{400MIPs，600MIPs，800MIPs，1000MIPs，1200MIPs}；子任务长度范围是[400MI，1000MI]。分别对算法的参数进行设置：本文算法的粒子群算法部分，群体规模size=100，c1=c2=2，迭代次数为40，蚁群算法部分，群体规模size=100，α=1，β=1，ρ=0.2，迭代次数为160。粒子群算法、蚁群算法的参数与以上分别对应相同，迭代次数是200。对各算法进行了20次重复运行。最终的实验结果见图1和图2。
从以上实验结果我们能看出，本文的PSO-ACO任务调度算法对两种算法的优点进行了有效结合。在迭代之初，PSO-ACO任务调度的优化效果比ACO要好，且总任务完成时间比ACO调度少；PSO-ACO的调度效果要比PSO和ACO好，可实现最优解，总任务完成时间最小。与此同时，我们也看到，PSO-ACO可以在较小的代数内找到的调度效果比PSO和ACO更好。从图中能看出，PSO的调度优化效果在迭代初期较为明显，总任务完成时间要少于ACO。然而随着迭代次数的变多，就弱化了自身的优化效果，总任务完成曲线渐渐变得平缓。这是因为PSO存在的不足正是初期收敛速度快，后期局部缺乏搜索能力。基于两种调度规模的仿真实验，结果表明本文的调度算法使得系统处理调度问题的时间大大缩短了，总任务的完成时间也减少了，很好的实现了时间性能和优化性能效果。
3 结语
本文主要就云计算任务调度问题进行了探究，提出了一种新的云计算任务调度法，这是基于粒子群优化和蚁群优化。在经过了仿真实验之后，可以看出这一算法的实时性和寻优能力都是很好的，作为一种调度算法是十分有效的。本文在算法方面主要只是对任务调度的时间因素加以考虑，但是在实际应用过程中往往存在比较复杂的情况以及诸多的干扰和影响因素，需要思考计算成本、节能灯方面的问题，所以还需要进一步深入研究，从而促使云计算任务的调度能够达到最佳综合性能。
参考文献
[1] 朱近之.智慧的云计算[M].北京：电子工业出版社，2010.
[2] 陈全，邓倩妮.云计算及关键技术[J].计算机应用，2009，9（29）：2562-2567.
基金项目
湖南省教育厅高校科研项目（12C0822）。
[关键词]粒子群优化；蚁群优化；云计算；任务调度
中图分类号：TP301.6 文献标识码：A 文章编号：1009-914X（2015）30-0127-01
云计算发展融合了传统计算机和网络技术，是一种商业实现。基于互联网的计算服务模式，针对一些共享可配置计算资源实现了方便、按需访问；这些资源可借助非常小的管理代价或与服务提供者的交互被快速地准备和实现按需使用[1]。目前用于求解云计算任务调度问题的算法有遗传算法、粒子群优化算法和蚁群算法。在前人研究的基础上提出一种基于粒子群优化与蚁群优化的云计算任务调度算法。
1 云计算任务调度的设计
粒子群优化算法是1995年Kennedy和Eberhart提出的，是受启发于鸟群觅食行为的的一种仿生优化算法。因为该算法简单、易实现且参数少，因而可以实现良好的连续优化和离散优化效果。蚁群算法是上世纪90年代DorigoMacro等人提出的，受启发于模拟蚂蚁群体觅食行为，也是一种仿生优化算法。这两种算法也存在一些不足之处。本文与两种算法的优势相结合，提出基于两种算法的一种云计算任务调度算法。这一算法先是借助粒子群优化算法的快速收敛性迅速生成初始解，接下来依据调度结果生成蚁群算法的初始信息素分布，最后是借助蚁群算法来将任务调度的最优解求出来。
1.1 粒子群算法
云计算任务调度问题是离散问题，而粒子群优化算法对于连续优化问题的解决比较适用。在离散版的粒子群算法中，将粒子位置向量每一位值取0或1，粒子速度不是对连续空间中粒子飞行的速度的表示，而且表示计算粒子位置向量取值为0或1的概率。
1.2 蚁群算法
以云计算任务调度的任务与资源分配关系矩阵X为参照，定义{xij}m×n为节点集，组成一个无向完全图G（V，E）。通过蚁群算法从集合{xij}m×n中选出一组节点{xy11，xy22，…，xyjj，…，xynn}，yj∈{1，2，…，m}，从而实现最小的Cmax值。
1.3 算法流程
在粒子群优化和蚁群优化基础上提出的云计算任务调度算法，其基本步骤是
这样的：
Step1对云计算任务调度目标函数进行定义。
Step2针对该调度算法，进行相关参数和算法结束条件的设定。
Step3随即初始化粒子群的位置和速度。
Step4对每个粒子的适应值进行计算，将粒子个体最优位置和群体最优位
置找出来。
Step5按照式（6）、式（7）来更新粒子速度和位置。
Step6没有动作。
Step7若是已达设定迭代次数，将云计算任务调度的初始调度结果输出，并转到Step8。要不然就跳转至Step4。
Step8按照粒子群算法得出的初始调度结果来初始化蚁群算法的信息素进。
Step9随机放置若干只蚂蚁到节点上并搜索。
Step10每只蚂蚁按照式（8）进行下一节点的选择，并按照式（10）、式
（11）对局部信息素进行更新，将调度列表中加入所选节点。
Step11完成全部任务调度后，按照任务调度列表对调度结果的适应值进行
计算，同时按照式（12）、式（13）对全局信息素进行更新。
2 实验与分析
CloudSim是澳大利亚RajkumarBuyya博士领导团队开发出来的一个云计算仿真平台。其主要是对云环境进行模拟，针对不同的调度策略做性能测试。本文也是采用CloudSim平台来进行云环境的模拟，对任务调度算法进行模拟仿真。为了对本文调度算法的性能进行有效检验，分别于5个虚拟计算资源、50个子任务和5个虚拟计算资源、500个子任务两种调度规模下，分别进行对比实验，包括粒子群优化算法（PSO）、蚁群算法（ACO）和本文算法（PSO-ACO）[2]。在实验中，各虚拟计算资源的处理能力是{400MIPs，600MIPs，800MIPs，1000MIPs，1200MIPs}；子任务长度范围是[400MI，1000MI]。分别对算法的参数进行设置：本文算法的粒子群算法部分，群体规模size=100，c1=c2=2，迭代次数为40，蚁群算法部分，群体规模size=100，α=1，β=1，ρ=0.2，迭代次数为160。粒子群算法、蚁群算法的参数与以上分别对应相同，迭代次数是200。对各算法进行了20次重复运行。最终的实验结果见图1和图2。
从以上实验结果我们能看出，本文的PSO-ACO任务调度算法对两种算法的优点进行了有效结合。在迭代之初，PSO-ACO任务调度的优化效果比ACO要好，且总任务完成时间比ACO调度少；PSO-ACO的调度效果要比PSO和ACO好，可实现最优解，总任务完成时间最小。与此同时，我们也看到，PSO-ACO可以在较小的代数内找到的调度效果比PSO和ACO更好。从图中能看出，PSO的调度优化效果在迭代初期较为明显，总任务完成时间要少于ACO。然而随着迭代次数的变多，就弱化了自身的优化效果，总任务完成曲线渐渐变得平缓。这是因为PSO存在的不足正是初期收敛速度快，后期局部缺乏搜索能力。基于两种调度规模的仿真实验，结果表明本文的调度算法使得系统处理调度问题的时间大大缩短了，总任务的完成时间也减少了，很好的实现了时间性能和优化性能效果。
3 结语
本文主要就云计算任务调度问题进行了探究，提出了一种新的云计算任务调度法，这是基于粒子群优化和蚁群优化。在经过了仿真实验之后，可以看出这一算法的实时性和寻优能力都是很好的，作为一种调度算法是十分有效的。本文在算法方面主要只是对任务调度的时间因素加以考虑，但是在实际应用过程中往往存在比较复杂的情况以及诸多的干扰和影响因素，需要思考计算成本、节能灯方面的问题，所以还需要进一步深入研究，从而促使云计算任务的调度能够达到最佳综合性能。
参考文献
[1] 朱近之.智慧的云计算[M].北京：电子工业出版社，2010.
[2] 陈全，邓倩妮.云计算及关键技术[J].计算机应用，2009，9（29）：2562-2567.
基金项目
湖南省教育厅高校科研项目（12C0822）。