大学教授团队开发了云仿真器cloudsim来模拟云环境下的任务调度与资源分配。
1 问题的描述
云计算中的任务调度是一个非确定性多项式（nondeterministic polynomical，缩写NP-hard）的问题。其调度策略的优劣对系统的整体性能有重要的影响。现有的任务调度算法大体可以分为两大类：早期传统的任务调度算法：先来先服务（First Come First Served，FCFS），有向非循环图（Directed Acyclic Graph），轮询法等。后期的启发式算法：遗传算法（Genetic Algorithm，GA），蚁群算法，粒子群算法，模拟退火算法，神经网络，禁忌搜索，免疫算法，max-max，max-min，min-min等。然而这些传统算法都存在问题包括，描述复杂，正确性不高，收敛性差，调度策略单一，并不能直接用于云计算环境中。为了提高云计算任务调度的服务质量，一些新的任务调度算法被提出。文献[3]提出了在遗传算法产生新个体的过程中引入模拟退火算子，该算法在一定程度上改善了算法的性能；文献[4]提出了一种动态规划的云任务分配算法，避免了子问题的重复计算，提高了时间复杂度；袁平鹏[5]等人依据cache中所存放的最近访问过的资源信息来减少不必要的延迟，在任务响应时间的平滑性、任务的吞吐率要比传统的算法好。
2 智能算法的研究
2.1 模拟退火算法
模拟退火算法是一种基于概率的算法，最早于1953年由N.Metropolis等人提出重要性采样法，以概率接受新状态，被称为Metropolis准则。1983年，Kirkpatrick等提出模拟退火算法，并将其应用于组合优化问题的求解。模拟退火算法起源于物理退火的过程，其基本思想是：将固体加温至非常高的温度，再让其慢慢的冷却。加温时固体内部的粒子呈现出无序状，内能增大，而在冷却时粒子渐渐有序，每个温度都达到平衡状态，最后在常温时达到基态，俗称等温过程。最后，算法的一个重要参数叫做冷却进度表，它控制参数的初值和衰减函数对应于马尔尔科夫链的长度和终止条件，这也叫做冷却过程。而根据Metropolis准则[7]，粒子在温度T时趋于平衡的概率为e-ΔE/（KT），其中E为温度T时刻的内能，ΔE为其该变量，K为Boltzmann常数。
2.2 粒子群算法
基本粒子群算法[6]（Patricle Swarm Optimization，PSO）其根源于对鸟群觅食行为的研究。粒子群算法主要解决连续优化的问题。它的具体描述如下：设在一个n维空间中，粒子群中有X个粒子组成，每个粒子都是这n维空间中的一个可能解。每个粒子表示为：Xi=（Xi1，Xi2，…，Xiq）；每个粒子对应的速度可以表示为Vi=（Vi1，Vi2，…，Viq）；每个粒子在进行搜索时要考虑的两个因素：自己搜索到的历史最优值和全部粒子搜索到的最优值。
2.3 遗传算法
遗传算法（Genetic Algorithm）是一种模拟生物进化论中自然选择过程的计算模型，是较经典的搜索最优解的方法。在遗传算法中，首先会生成一组候选解，然后根据适应度函数计算每个候选解的适应度，并根据适应度的大小对种群进行选择操作，适应度大者生存，适应度小者被淘汰。最后，对保留的个体进行交叉、变异操作，以产生出更优的个体。传统遗传算法具有全局解空间搜索和并行性两个显著优点，同时也存在早熟等现象。
3 混合调度与最优性原理
任务的最优性是指：不论是在批处理系统还是在分时系统中，对于前面决策所造成的某一阶段的状态，其后阶段的决策必须构成最优的策略。
随着科学研究，工程管理等技术的发展，单一的某种算法在研究一类具体问题的时候达不到人们预期的效果。而算法之间的混合往往事半功倍。根据实际情况做出如下定义：
种群的规模为S，任务集合task={task1，task2，…，taskn}，n个任务，资源的数量为resource，每个粒子初始化的位置由向量来定义，记做Xi；初始化的向量坐标为[-（resource-1），resource+1]之间的整数。算法描述如下：
第一步：种群规模S中随机出现的X0进行调度，得到调度结果F（X0）；从而计算出作业的总完成时间（SumTaskTime）和平均完成时间（AvgTasktime）。且标记为X*；
第二步：所找向量横向移动；同样计算出一个新的调度结果F（X1）；
第三步：比较F（Xi）与F（Xi+1），差值记做M（x）；
第四步：若M（x）>0，则F（Xi+1）替换F（Xi），反之不变；
第五步：重复迭代若干次，对每次得到的最优解组成新的解集合g（x），对g（x）用模拟退火进行训练；
第六步：对训练后的种群再进行选择，交叉，变异的操作；
第七步：从局部解中概率性进行解的跳出从而达到全局最优解；
第八步：得到混合算法的最优解。
4 算法仿真结果与分析
实验共创建个4个数据中心，4台主机，8个虚拟机，任务的数量分别为4，8，10，20，40，60，80，160，200，其参数见表1。cloudsim模拟的虚拟机参数列表见表2。
实验根据任务数相同，虚拟机数不同以及任务数不同虚拟机数相同来进行划分，各自独立运行20次，取其平均值来进行比较。
虚拟机数为4个时，任务数分别为20，40，80，160时，粒子群算法，模拟退火算法，遗传算法和混合算法所产生的总的费用如表3所示。
虚拟机个数不同时，产生的总费用如表4所示。
5 小结与展望
本文所描述的任务调度是面向异构平台的，系统是非抢占式的，数据中心已经将虚拟机资源进行封装，虚拟机资源的情况是根据平台的实际情况而设置的。由实验可以得出在任务数较多时，混合算法具有明显的优势。但由于云计算资源的网络结构没有拓扑，不可预测的网络情况很多。由于平台的局限性，无法得到资源的故障率，虚拟机费用的计算因为平台与仿真程序的通信约束变得更为复杂。
在本文中所设计的资源选择约束条件中，对用户QOS限制因素考虑的不全面，只考虑了任务的执行时间和完成时间这两个典型的因素。若继续研究可以考虑怎么样结合其他的QOS因素，在最大化用户和数据中心经济效益时同时提高资源的利用率。
参考文献：
[1]米勒，姜进磊.云计算[M].北京：机械工业出版社，2009.
[2]刘鹏.云计算[M].二版.北京：电子工业出版社，2011.
[3]黄璐.基于遗传算法的云计算任务调度算法研究[D].2014.
[4]赵立慧.基于cloudsim平台的云任务分配策略研究[D].2013.
[5]袁平鹏，曹文治，邝坪.一种基于Cache的网格任务反馈调度方法[J].软件学报，2006（11）.
[6]Kennedy J，Eberii Artrc. Particle Swarm Optimization[C]//proceeding of IEEE International Conference on Neural Networks Perth：IEEE Press， 1995， 4：1942-1948.
[7]周一可.云计算下MapReduce编程模型可用性的研究与优化[D].2011.
[8]虚拟化.http：//baike.baidu.com/view/13605.htm[EB/OL].
相关热词搜索： 调度 算法 智能 研究 Cloudsim
