基于模拟退火算法的云计算资源调度模型

袁晓林　施化吉

摘要摘要：针对云计算平台的特征，提出基于模拟退火算法建立云计算资源调度模型。模拟退火算法在保证用户公平性的前提下，以缩短总任务的完成时间及提高用户满意度为目标。通过仿真实验，在相同硬件环境下对比分析模拟退火算法与传统遗传算法的资源调度性能。结果表明，模拟退火算法在收敛速度和用户满意度方面均优于传统遗传算法，更加适应云计算环境。

关键词关键词：云计算；模拟退火算法；资源调度模型；算法仿真

DOIDOI：10.11907/rjdk.143838

中图分类号：TP311.5

文献标识码：A文章编号文章编号：16727800（2015）002006803

基金项目基金项目：

作者简介作者简介：袁晓林（1987-），男，山西长治人，江苏大学计算机科学与通信工程学院硕士研究生，研究方向为软件工程。

0引言

云计算是近年来信息科学领域的研究热点，集成了网格计算、并行处理等多种技术，通过网络将各种资源打包成服务，为各类用户提供多种可用资源和服务，这样要求云计算资源分配方式能够满足不同用户的需求，使用户能够获得良好的服务质量，因此设计性能优异、科学合理的云计算资源调度算法至关重要＼[2＼]。

已有许多学者对云计算资源调度问题进行了相应研

究。张雨等＼[3＼]提出了一种融合遗传算法与蚁群算法的混合调度算法，认为其能有效完成云计算任务调度；卓涛等＼[4＼]利用基于改进人工蜂群算法的云计算资源调度模型，改善了传统资源调度算法存在的缺陷，提高了云计算资源利用率，并且大幅度减少了任务的完成时间；封良良等＼[5＼]利用于改进粒子群的任务调度算法，采用间接编码方式对每个子任务占用的资源进行编码，给出解码方式，定义了考虑时间和成本的适应度函数，确立了粒子位置和速度的更新方法，认为在相同的条件设置下，该算法的总任务完成时间和总任务完成成本小于传统粒子群优化算法。然而，这些调度算法均存在各自的不足，如在不同云计算环境下算法性能差异性大、易陷入局部最优，或者在搜索效率上有待提高。

模拟退火算法（Simulated Annealing， SA） 最早由N·Metropolis等人于1953年提出，1983 年，S·Kirkpatrick等尝试将退火思想运用于组合优化算法设计，如今模拟退火算法已成功应用于组合优化、生产调度、控制工程等领域。模拟退火算法是一种允许在一定限度内接受非最优解，从而有效避免陷入局部最优解的优化算法＼[6＼]。本文将基于带记忆功能的模拟退火算法，构建云计算资源调度模型，以期获得较高的作业调度效率。

1云计算任务调度模型

1.1任务调度模型

云计算系统在保证资源得到最大利用的同时，尽可能为用户提供高质量服务，但云计算系统资源有限，经常出现资源竞争现象，只能采用资源调度算法将任务合理进行分配，从而防止出现一个资源被多个任务争抢的现象。云计算平台任务调度模型结构如图1所示。

图1云计算平台任务调度模型结构

1.2任务调度算法评价指标

云计算的单个用户任务可用十元数组表示，如式（1）：

T={ID，PE，L，Input，ET，EBW，EF，EP，J}（1）

式（1）中，J为该任务的用户完成离散度。J直接决定云计算平台完成执行该任务后用户的满意度。当J>0时，该用户对任务需求的实际获取值要大于期待值；反之，当J<0时，该用户对任务需求的实际获取值要小于期待值。|J|越小，表明云计算系统为用户提供可以接受的服务的同时，所调用的资源越少，即表明采用的云计算任务调度算法越优化。

2模拟退火算法

2.1模拟退火算法基本原理

模拟退火算法源于对固体退火过程的模拟，先将固体加温，在熔融温度下，固体粒子能量的非均匀性被破坏，并会达到新的平衡，系统能量增大；然后让其徐徐降温，让系统在每一温度下都达到平衡值，系统能量也逐渐降低；当温度达到结晶温度后，固体结晶，系统能量达到最小值。

2.2算法执行

设组合优化问题的一个解i及其目标函数f（i）分别与固体的一个微观状态i及其能量E（i）等价。令随算法进程递减的控制参数t担当固体退火过程中温度T的角色，温度由一个冷却进度表控制。

在某控制参数T（称为温度）下，当前解为i，对应的目标函数为E（i），在邻域产生新解j，对应的目标函数为E（j），模拟退火算法接受新解j的准则称为Metropolis准则，可描述如下：若E（j）

若E（j）>E（i），如果e（E（i）-E（j））/T>rand（0，1），则也以j取代i作为当前解；

其它条件下，以i作为当前解。

其中，rand（0，1）为0～1之间均匀分布的随机数。

温度由冷却进度表控制，由高到低逐渐下降至接近0，可赋予一个初值T0，衰减函数，终值Tf，也可以用一组数列Ti取代衰减函数。产生新解并且进行一次Metropolis判断的过程称为一次尝试，在某个相同温度下进行的若干次尝试序列称为一个Mapkob链，若干个Mapkob链序列组成一个完整的模拟退火过程。

模拟退火算法的收敛速度取决于参数和Mapkob链长度的选择。此外，Metropolis算法的有效实现亦是关键所在。

2.3算法优化

模拟退火算法的有效实现需要控制参数的合理选择，为了提高算法优化效果，对原方法作了一些改进：

（1）模拟退火算法如果要真正收敛于全局最优，则需要温度的徐徐下降，并在每一个温度下达到平衡，最终温度要趋近于零。如此则Mapkob链无限长，这是在实际情况中无法达到的。为克服此问题，可多次退火寻优或者多次加温退火（即当温度降到最低时，升温然后继续退火）。

（2）往往搜索到一个较好的解，但是由于温度较高将其舍去，因而最后解往往比舍弃的解更差。本文算法记录了所有尝试的最优解，在最后退火结束时如果记忆中舍去的解比退火最后解更优，则将其作为全局最优解。这在程序结束时进行，以避免破坏退火进程。

（3）在退火过程中，有时几乎接近最优解，然而温度过高，搜索过程可能离开此处向其它方向搜索，从而失去全局最优解。而在某一局部寻找局部最优正是局部搜索法的特点，因此在退火的某一时段，在某个解周围进行局部搜索，局部搜索结束后在暂停处继续退火进程，将会提高解的质量。需要注意的是，局部搜索阶段必须设置一个终止规则，因为计算机双精度数据有效位数很大，目标函数可能由于不断地减小而陷入死循环。

3实验仿真与结果分析

本文基于MATLAB软件模拟的云计算环境，对传统遗传算法与模拟退火算法进行仿真实验，在相同硬件环境下对比这两种算法，并分析实验结果。云计算完成全部任务的总时间和全部任务完成后任务完成离散度是仿真实验中主要考虑的两个评价因素。

本文采用的模拟退火算法和传统遗传算法均是参数最优化估计的非线性算法。仿真实验结果显示，模拟退火算法在任务完成时间和用户满意度两个方面均优于传统遗传算法。实验中对两种算法在5台虚拟机构成的云计算平台上对100个云计算任务的任务调度性能进行了分别测试，实验仿真时的各项参数如表1所示，实验仿真结果如图2、图3所示。

表1仿真实验主要参数

算法[]参数及取值

[]种群大小N=200

传统遗传算法[]k1=0.450

[]k2=0.880

[]k3=0.075

[]起始温度T=200℃

模拟退火算法[]终止温度T=1.0℃

[]退火系数K=0.950

在云计算平台执行所有用户任务的总时间上，两种算法总任务完成时间相近，模拟退火算法略优。同时，实验结果证明，模拟退火算法能够更快达到收敛，并有效避免

陷入局部最优解的现象。结果表明，模拟退火算法能够在一定的范围内接受恶化解，有效防止遗传算法容易出现的陷入局部最优解现象，提高云计算作业任务调度算法的总体性能。在用户对云计算平台所提供服务的用户满意度上，由于模拟退火算法有效避免了局部收敛现象，其最终任务完成离散度较传统遗传算法小。

图3用户任务完成离散度分布

4结语

本文提出利用带有记忆功能的模拟退火算法建立云计算资源调度模型。该算法针对基于云计算平台的多用户多任务特征，对不同任务调用的计算资源进行优化分配，以缩短总任务的完成时间，并增加用户满意度。仿真实验结果表明，该算法在满足用户要求的同时能够缩短总任务的完成时间，是云计算平台下的一种有效调度算法。

参考文献参考文献：

＼[1＼]过敏意.绿色计算：内涵及趋势＼[J＼].计算机工程， 2010，36（10）： 17.

＼[2＼]DAI W，MILENKOVIC O.Subspace pursuit for compressive sensing signal reconstruction＼[J＼].IEEE Transactions on Information Theory， 2009， 55（5）：22302249.

＼[3＼]张雨，李芳，周涛.云计算环境下基于遗传蚁群算法的任务调度研究＼[J＼].计算机工程与应用，2014（6）：5155.

＼[4＼]卓涛，詹颖.改进人工蜂群算法的云计算资源调度模型＼[J＼].微电子学与计算机，2014（7）：147150，155.

＼[5＼]封良良，张陶，贾振红，等.云计算环境下基于改进粒子群的任务调度算法＼[J＼].计算机工程，2013（5）：183186，191.

＼[6＼]遆鸣，陈俊杰，强彦.基于模拟退火的Map Reduce调度算法＼[J＼].计算机工程，2012（19）：4548.

责任编辑（责任编辑：孙娟）