基于Cloudsim平台上的启发式融合资源动态调度算法

摘 要：基于Cloudsim云平台，针对其自带的资源调度算法的缺陷和现存已与Cloudsim结合的智能优化算法的不足，本文将根据食品安全预警本体模型规则，结合乳制品的分类处理，提出一种新型的启发式融合资源动态调度算法，实现在云平台的资源动态调度，实现优化的作业资源调度，旨在减少云端任务所执行的时间，提高效率，在保证负载相对平衡的前提下，提出一种云资源调度方法，该方法具有较快的调度速度，实现资源调度算法的优化。

关键词：云平台;Cloudsim;资源调度;启发式算法

中图分类号：F062.5      文獻标识码：A      文章编号：1008-4428（2018）07-0139-02

一、 引言

随着科技的发展创新和商业模式的转变，传统的计算平台日渐不能满足人们的要求。于是云计算应运而生，它是在网格计算基础上发展起来的一种新兴商业计算模型，可以为用户提供计算、存储资源等各类服务，是一种新的基于服务的资源提供模式。近些年随着社交网络和各种智能移动端的飞速普及，人们的日常需求也逐渐由单纯的设备功能性转变为对互联网的可接入性、开放性、共享性、易用性和安全性等方面的服务质量追求，来确保可以随时随地地使用智能移动设备获得所需服务，并能够在信息未受到威胁和制约的情况下，方便通畅地实现沟通共享。因此，我们称云计算是在社会新需求的推动下应运而生，另外它的用时付费商业模式不仅恰当地适应了这种社会新需求的转变，而且具有良好的经济效益优势，从而使它成了国内外重点研究主题之一。

随着用户对互联网需求的剧增，云计算的规模也逐渐扩大，达到海量的用户群体。在此基础上，适应用户动态的需求变化并实现高效率低成本的资源合理分配成为云计算现阶段的研究热点。其中资源分配的关键是选择合理的资源分配算法，合理的资源分配算法不仅可以提高计算和传输速度，而且能够减轻云计算网络的负荷和能耗，快速平衡网络负载，从而提升系统性能。在云计算中，资源具有动态性、异构性和大规模性等特点，如何根据云计算的实际特点制定合适的资源分配策略是亟待解决的难题。云计算目前发展并不成熟，但很多具有高度并行、自组织、自适应等特性的智能优化算法已被广泛用于解决云计算的资源分配问题。云环境下研究任务调度算法学术与现实意义并存，不恰当的任务调度策略一方面浪费云资源，另一方面也无法满足用户服务质量需求。于是本文探讨云计算下的资源分配问题，对现有的资源分配算法存在的问题进行了分析，在此基础上提出改进的资源分配算法，有利于对现有问题的解决，有很大现实意义。

二、 文献综述

作为一种新型的计算服务模式，云计算得到越来越多国内外学者的关注。云计算资源分配问题是一个NP难问题：在满足任务完成的条件前提下，最大化资源利用率，并均衡系统负载。目前大多从最优跨度、负载均衡、服务质量、经济原则四个角度去衡量云计算调度算法。云环境下资源分配策略存在多种，现阶段主要通过智能优化算法实现云计算资源合理分配。结合云计算自身特性，目前只有智能优化算法才能很好地适应云计算平台，于是智能优化算法被广泛推广到云环境中。

熊聪聪（2012）以遗传算法为基础，搭建了新的任务调度模型，引入染色体匹配率参数来避免早熟，引入服务质量标准改进适应度函数，但仍然存在搜索全局最优解的能力较低、调度目标单一等问题。Zhu

K（2014）结合多代理的遗传算法，选择一种负载均衡的模型应用到遗传算法，提高了资源执行效率，但存在后期易陷入局部最优的问题。刘万军（2011）改进了粒子群算法，引入动态多群体协作和变异粒子逆向飞行因素，但并未考虑惯性权重、学习因子对负载平衡的影响。宣豪骏（2016）创新性地结合多种优化智能算法提出新的融合算法，与模拟退火、蚁群和遗传算法对比，能实现更优的资源分配。王登科（2013）基于粒子群优化与蚁群优化，提出全新的云计算任务调度算法，算法中吸收了粒子群算法的快速收敛和蚁群算法的寻优能力，缩短了系统处理调度的时间和总的任务执行时间，提高了云计算任务调度的效率。徐浙君（2017）提出膜计算和改进蚁群算法的融合算法在云计算资源调度中的研究，并提高了算法的整体性能，仿真实验说明在网络、成本、能量消耗上有了明显的降低，也提高了资源分配效率。

目前，新兴的元启发式优化算法（包括萤火虫算法、蝙蝠算法、布谷鸟搜索算法等）还未应用到云平台中实现资源调度。现阶段还处于对新兴的优化算法改进和融合阶段，李煜（2012），刘长平（2013），周永权（2012）分别对布谷鸟搜索算法进行实现和测试;结合蝙蝠算法的缺点提出基于逻辑自映射的变尺度混沌蝙蝠优化算法，改善了蝙蝠算法摆脱局部极值点的能力，提高了算法收敛性和寻优精度;萤火虫算法与C2Opt算子相结合，设计了求解TSP的一种新的高效人工萤火虫群优化算法，且在求解较大规模TSP问题时非常奏效，具有收敛速度快、精度高等特点。

基于以上，本文发现智能优化算法良好的灵活性、可移植性和易于实现的特点对于解决大规模的云计算资源分配问题很有效。目前智能优化算法在解决云计算资源分配问题上已取得了一些成果，但在云计算资源分配模型的约束条件、适应度函数等方面还有很大的研究空间，即现阶段已实现的智能算法与Cloudsim的结合并不是最优，因此本文将结合新兴的元启发式优化算法，建立新的云计算资源调度模型，实现更优的资源调度。

三、 启发式融合资源动态调度算法

（一）问题描述及现状分析

目前，对于Cloudsim的资源调度算法的研究主要是云平台与元启发式智能优化算法的结合，提高资源调度效率。现阶段的研究，大多基于遗传算法、模拟退火算法、蚁群算法等的改进和融合，但目前的算法都仍有改进空间，如遗传算法虽有快速随机全局搜索能力，但参数较多，编程较复杂，易陷入局部最优;粒子群算法初期收敛速度快，后期局部搜索能力不足，收敛速度缓慢，但同遗传算法相比，粒子群算法收敛速度快，优化性能比遗传算法好，且编程易实现，需调整的参数少;而蚁群算法虽有较好的寻优能力，但初期信息素匮乏，收敛速度慢。目前的研究中智能算法与Cloudsim的结合并不是最优，仍有改善空间，因此本文提出一种新型的启发式融合算法改进云平台的资源调度问题。

（二）算法说明

本文在食品安全预警本体模型的支持下，减少云端任务所执行的时间，提高效率，提出一种基于多资源的任务调度算法，该方法具有较快的调度速度，实现资源调度算法的优化，该算法能在多资源下大大缩短所有任务的平均完成时间，也能一定程度上保证负载均衡。启发式融合资源动态调度算法流程如下图1所示：

结合本体规则及乳制品分类处理的特性，具体算法步骤如下：

·对分类算法库S中随机出现的X0进行调度，得到调度结果f（X0）;从而计算出作业的总完成时间和平均完成时间;

·将所找向量X0横向移动;同样计算出一个新的调度结果f（X1）;

·比较f（X0）与f（X1），差值记做M（x）;

·若M（x）>0，則f（X1）替换f（X0），反之不变;

·重复迭代，每次得到的最优解组成新的解集合f（X′），对通过f（X′）更新公式进行训练;

·对训练后的分类方法库集合再进行随机游走操作;

·从局部最优中多次随机游走从而达到全局最优解;

·得到改进融合算法的最优解，选择最优的分类处理算法。

上述算法的迭代过程主要通过目标函数f（X）=f（X0）×e-βr2实现，其中，f（X0）表示初始选择分类方法的分类时间，β表示吸收系数（为固定值），r表示分类算法间的距离。

（三）算法实现

本算法主要涉及在食品安全预警本体模型支持下的融合算法的实现，算法实现过程：

1.

初始化输入：分类处理算法库的规模为S，分类任务集合task={task1，task2，…，taskn}，n个任务，分类算法库资源的数量为resource，初始化输入由向量来定义，记初始化的向量坐标为[-（resource-1），resource+1]之间的整数。

2. 初始迭代过程：初始化分类算法 Xi（i=1，2，…，n）

最优目标的迭代：Xj=Xi+γ0e-βγ2ij+ζεi。其中，Xi，Xj表示i，j两种分类方法的状态，ξ是一个随机参数，遵循正态分布。

目标函数：f（X）=f（X0）×e-βr2。f（X0）表示初始选择分类方法的分类时间，β表示吸收系数（为固定值），r表示分类算法间的距离。

经过多次迭代后得到初始迭代最优解集合记为f（X′）。

3. 训练过程：通过更新公式实现对初始迭代最优解的解集合实现训练。

更新公式：Xt+1i=Xti+aLevy（λ）。其中Xti和Xt+1i分别表示第i个分类方法在第t次和第t+1次的分类状态，a表示步长控制量，为点对点乘法，Levy（λ）为Levy飞行随机搜索的跳跃路径，并且Levy～u=t-λ，（1<λ<3）。

4.随机游走迭代：Xnew=X+εAt。其中ε为[-1，1]中的随机数，x为从当前训练集中集中随机选择的一个解，At=为全体算法在迭代次数为t时的平均时间效率。

在上述算法的迭代过程，根据食品安全预警本体模型规则中的阈值，设置算法的终止条件，记为θ，完成算法迭代之后得到最优解X*。

5.启发式融合算法伪代码如下：

目标函数：f（X），X=（X1，X2，…，Xm）Τ。初始化分类方法库 xi（i=1，2，…，n）。

初始化基本参数β，γ0，MaxG（迭代次数），本体规则阈值θ。

While（t

for i=1：n

  for j=1：i

计算分类方法i的调度时间

if （Ii

算法i向算法j移动

  end if

  计算更新的调度时间

end

end

对所有分类算法的调度时间进行排序，找出当前最优解

End

为了验证本发明提出的在食品安全预警本体模型的支持下的新型启发式融合算法在云资源调度中的有效性，将模型在Cloudsim云计算模拟器上进行了仿真实验，所有实验都基于Eclipse环境中实现的，如图2所示。

四、 总结

本文涉及云计算的资源调度算法，属于人工智能和云计算领域。在本体规则库的基础上，本发明涉及布谷鸟搜索算法、蝙蝠算法和萤火虫算法，以及云计算、Couldsim

云计算模拟器，旨在实现一种新型的启发式融合算法，对比分析任务执行所花费的时间，在食品安全预警本体模型的支持下，得到最优化的云计算资源调度方案。

基于Cloudsim云平台，针对其自带的资源调度算法的缺陷和现存已与Cloudsim结合的智能优化算法的不足，根据食品安全预警本体模型规则，结合乳制品的分类处理，提出了一种新型的启发式融合资源动态调度算法，实现在云平台的资源动态调度，实现优化的作业资源调度。本算法旨在减少云端任务所执行的时间，提高效率，在保证负载相对平衡的前提下，提出一种云资源调度方法，该方法具有较快的调度速度，实现资源调度算法的优化。

参考文献：

[1]熊聪聪，冯龙，陈丽仙，苏静.云计算中基于遗传算法的任务调度算法研究[J].华中科技大学学报（自然科学版），2012（S1）：1-4.

[2]Zhu K， Song H， Liu L， et al. Hybrid Genetic Algorithm for Cloud Computing Applications[C]∥ IEEE Asia-Pacific Services Computing Conference， Apscc 2011， Jeju， Korea.

DBLP，2014：182-187.

[3]刘万军，张孟华，郭文越.基于MPSO算法的云计算资源调度策略[J].计算机工程，2011（11）：43-44+48.

[4]宣豪骏，姜瑛.Cloudsim中基于智能算法的任务调度研究[J].价值工程，2016（10）：162-163.

[5]王登科，李忠.基于粒子群优化与蚁群优化的云计算任务调度算法[J].计算机应用与软件，2013（1）：290-293.

[6]徐浙君，陈善雄.基于膜计算和蚁群算法的融合算法在云计算资源调度中的研究[J].计算机测量与控制，2017（1）：127-130.

[7]李煜，马良.新型元启发式布谷鸟搜索算法[J].系统工程，2012（8）：64-69.

[8]刘长平，叶春明.具有混沌搜索策略的蝙蝠优化算法及性能仿真[J].系统仿真学报，2013（6）：1183-1188+1195.

[9]周永权，黄正新.求解TSP的人工萤火虫群优化算法[J].控制与决策，2012（12）：1816-1821.

作者简介：

张慧中，女，安徽池州人，南京财经大学管理科学与工程专业在读研究生，研究方向：质量管理、资源匹配。