基于增强型向日葵优化算法的云任务调度的研究

⃝可在www.sciencedirect.com上在线获取ScienceDirectICTExpress 8（2022）97www.elsevier.com/locate/icte基于增强型向日葵优化算法的云任务调度霍贾特·埃马米伊朗博纳卜大学计算机工程系接收日期：2020年12月1日;接收日期：2021年6月11日;接受日期：2021年8月2日2021年8月12日在线提供摘要云任务调度的目标是在共享资源上划分任务，以最小化能耗和最大完工时间。近年来，提出了几种任务调度的元算法，并取得了令人鼓舞的成果。然而，他们的表现却与理想状态，需要进一步改进。本文介绍了一种增强型向日葵优化（ESFO）算法，以改善现有的任务调度性能。它在多项式时间内找到最优调度。实验表明，ESFO优于其对应物。与最优方案相比，在最大完工时间和能耗方面分别提高了0.73%和2.24%。c2021韩国通信和信息科学研究所（KICS）。出版社：Elsevier B.V.这是一个开放的访问CC BY-NC-ND许可证下的文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。关键词：云计算;任务调度;能耗;增强型向日葵优化算法1. 介绍云计算作为分布式计算的一个重要分支，允许用户通过互联网访问按需计算服务，包括存储、服务器、数据库和软件[1]。如图1、要使用服务，用户将其请求提交给任务管理器模块。任务调度器从任务管理器获取请求，在资源信息服务器的帮助下分析可用资源，并使用任务调度算法在虚拟机（VM）之间划分任务。有效的任务调度方法允许SP最大化资源利用率。任务调度是一个NP难问题[2]。最近，已经提出了几种任务调度算法[3]。现有的算法可以分为三类[4]：基于博弈论的方法，动态方法和Meta启发式。表1列出了云计算中任务调度的一些最新算法。基于博弈论的调度算法将调度过程建模为博弈，并定义效用函数来评估节点的性能，平衡多个节点的资源利用率。动态调度算法关注于可用资源、任务的实时定位以及电子邮件地址：emami@ubonab.ac.ir。同行评审由韩国通信和信息科学研究所（KICS）负责https://doi.org/10.1016/j.icte.2021.08.001计划任务[4]。元算法是解决NP难问题的有效选择。他们将任务调度表述为一个优化问题。元分析不是孤立地寻找最佳解决方案，而是以最小的复杂性提供接近最佳的解决方案。大多数基于元启发式的方法取得了令人鼓舞的结果，然而，它们遭受陷入局部最优，并且它们的性能离理想状态还很远。为了提高基于元启发式调度的性能，我们提出了一个ESFO算法，以找到一个最佳的调度计划，以最小的搜索复杂度。通过对多个任务调度基准测试，本文提出的ESFO算法在能量消耗和最大完工时间方面都比同类算法有明显的改善。概括而言，我们的贡献如下：介绍了解决云环境下任务调度问题的ESFO算法。在ESFO中，我们引入了一种新的授粉策略，以提高开发和勘探能力。使用不同的任务调度基准评估所提出的ESFO算法，以识别潜力和弱点。仿真结果表明，与同类算法相比，ESFO算法的优越性，在能源消耗和最大完工时间措施。2405-9595/2021韩国通信和信息科学研究所（KICS）。出版社：Elsevier B.V.这是一个开放的访问CC BY-NC-ND许可证下的文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。··H. EmamiICT Express 8（2022）9798：→={个={个=--=−我N×Mi=1j= 1−+我我我图1.一、云 计算任务调度架构概述[2]。表1文献中的任务调度算法类型算法参考灰狼优化（GWO）[2]配子在运动阶段，向日葵采取随意的步骤，以最好的向日葵，这被认为是太阳。正确探索解空间是找到优化问题全局最优解的最重要因素。为了实现这个问题，我们引入了一个增强版本的SFO，即ESFO算法。ESFO配备了一个新的授粉操作员，在开发和勘探能力之间提供了适当的平衡。在下文中，我们描述如何将ESFO算法应用于任务调度。创建种群：初始种群由Z向日葵。Pop={S1，S2，...，SZ}（ 3）蚁群优化（ACO）[4]粒子群优化（PSO）[5]每个向日葵Si={si，1，si，2，。. .，s i，M在人口中元启发式萤火虫群优化（GSO）[6]遗传算法（GA）[7]人工蜂群（ABC）[8]烟花算法（FWA）[9]由M个数字组成，每个数字表示任务在其上运行的VMsij定义为si j=smin+φi j（smax−smin）（4）动态动态两阶段调度[10]Q学习调度[11][12]第十二届中国国际汽车工业展览会[13]2. 问题陈述设Vv1，v2，. . .，vN是虚拟机（VM）的集合，并且T t1，t2，. . . M是要执行的M个任务的集合。每个任务都可以由两台机器中的任何一台来处理。调度被定义为函数f不的第五号将任务映射到VM。主要目标是 找到 一 个 最小 复 杂 度的 时 间 表， 使 最大 完 工 时间（makespan）和能量消耗最小化[2]。最大完工时间计算如下：其中φij是范围[0，1]中的均匀随机数，smin和smax分别是sij的下限和上限。对于任务调度，smin和smax分别初始化为 1和M.假设有六个任务t1、t2、t3、t4、t5、t6和两个VM。一种可能的解决方案是Si[1， 2， 2， 2， 1， 1]，其将任务t1，t5，t6映射到第一VM，并且将t2，t3，t4映射到第二VM。在任务分配过程中需要满足两个约束条件每个任务都应该包含在调度过程中，并且每个任务只能出现一次。由于任务调度是一个离散的问题，任务和虚拟机的指数是正整数。为了将ESFO应用于任务调度，向日葵的元素被四舍五入为离散数。功效计算：使用等式（1）计算每个向日葵Si（1）Eq.（二）、在任务调度问题中经过幂次计算，向日葵的成本f1=mNax ⎧⎨∑M x（i，j）×P（i，j）（一）（S）被认为是太阳。授粉：为了模拟授粉过程，标准i=1j=1SFO从种群中随机选择p×Z向日葵，P（i， j）是机器i上任务j的处理时间，x（i， j）是布尔变量，用于标识任务是否然后将每个选定的向日葵更新为S t+1=r i. （S t−S t）+S t（五）j是否由机器i处理。 由于虚拟机工作在i j j同样，解决方案的最大完工时间对应于其中p表示授粉率。 t和t是一种...I jVM的最大执行时间。能耗对应于CPU利用率，计算如下：迭代t时向日葵i和j的解。ri是范围[0，1]中的随机数。在标准SFO中，p0的情况。五是使用。在ESFO中，我们提出了以下方程来模拟N M 授粉期f2=1∑ ∑Eij（2）St+1=t×A+（1−t）×B不不Eij是第i个VM在执行A=Sj+U（−1，+1）×（Si−Sj）B=St+β×（S−St）（六）j任务。3. 任务调度向日葵优化（SFO）算法[14]模拟向日葵吸收太阳辐射的运动。SFO由授粉和移动两个阶段组成。在授粉阶段，向日葵合作产生花粉α不αH. EmamiICT Express 8（2022）9799其中αt是迭代t时的切换概率，它控制局部和全局授粉的比例。向日葵是目前发现的最好的向日葵。U（1，1）在[1，1]范围内生成一个均匀的随机数，它增加了一些延迟以增加围绕向日葵Si的搜索，β是控制搜索方向幅度的缩放因子（S−St）。我们使用值β=3.λ，其中λ∈H. EmamiICT Express 8（2022）97100-×我⏐={个=={个=（0，1）是一个标准的正态随机数。我们定义αt如下：表2模拟参数。αt=αMax不— I（αMax— αmin）（7）参数值数据中心数量5其中I是最大迭代次数。αmax和αmin分别设置为0.6和0.4。这里的想法是ESFO在开始迭代时进行更多的全局搜索，并在接近结束时进行更多的局部搜索引入新的授粉算子的主要动机是同时改善探索和探索。方程中的项A（6）通过模拟当地的授粉过程，提高了ESFO的利用率。方程中的项B（6）通过模拟全球授粉机制来改进探索。移动：在此阶段，选择（1p）Z向日葵并更新如下：VM数量（M）50虚拟机策略时间共享虚拟CPU数量[1VM RAM大小[512虚拟CPU容量[500任务数量（N）[100St+1St+rS−St（八）i= i。不S当量（8）模拟向日葵Si的方向变化太阳的方向，最后，最适合的向日葵被发现，并与太阳取代。S=S k P（S k）> P（S j）j=1，2，.， 中文（简体）该算法运行，直到达到最大迭代次数。算法1展示了如何使用ESFO进行任务调度。算法1：用于任务调度的ESFO输入：ESFO参数;M个 任务，Tt1，t2，...，t M;N个虚拟机，Vv1，v2，...，vN;输出量：任务调度通过等式初始化向日葵的种群。（3）和（4）;评估的权力向日葵方程。（1）或（2）;t0;while（t I）< do计算向日葵授粉方程。（6）计算向日葵的运动方程。（8）;评估的权力向日葵方程。（1）或（2）;通过等式更新太阳S（9）;t=1;端返回太阳S光作为最佳解决方案;4. 实验和分析为了模拟云环境，我们使用了Cloudsim工具包，并在MATLAB release 2017a中实 现了 核心 流程 。所 提出 的ESFO与三种算法进行了比较：平均灰狼优化（MGWO）[2]，混合萤火虫群优化（HGSO）[6]和标准SFO [14]。种群大小（Z）和最大迭代图二、 基于完工时间度量的算法比较。图3.第三章。能 耗 方面的算法比较。对于所有算法，数（I）分别被认为是20和30。比较算法的具体控制参数的选择如其作者所报告的。模拟参数在表2中给出。这些任务是随机初始化的，因为在实际情况下，这些任务的配置是不同的;例如，它们的长度不可能是一致的。所有算法运行30次，并计算平均性能。图图2和图3分别显示了算法在最大完工时间和能耗度量方面的性能。按100、200、300和400的最大完工时间计算，ESFO的性能分别为58、147、188和271 s任务ESFO消耗8.95、11、15.1和19.65 KWH能量分别为100、200、300和400个任务。ESFO在大多数情况下获得了更好的性能，超过或匹配其他算法报告的最佳结果。表3总结了ESFO与其他算法相比的改进。ESFO在所有基准中均显著优于SFO。当任务数大于200时，它比HGSO和MGWO获得更好的结果。与其他算法相比，MGWO在任务数=100时获得了更好的性能。这表明ESFO对于大量任务具有高性能。 ESFO在解决方案我H. EmamiICT Express 8（2022）97101表3与其他算法相比，ESFO算法有了改进。业绩指标ESFO与的任务HGSO实验，带头撰写手稿，提供关键反馈，并帮助形成研究，分析和手稿。完工时间MGWO −0.69 −0.18 1.00 1.453.76作者声明，他们没有已知的可能影响本文所报告工作引用[1] M.B. Gawali，S.K. Shinde，使用启发式方法的云计算中的任务调度 和 资 源 分 配 ， J. Cloud Comput. ： Adv.系 统 Appl. 7 （ 4 ）（2018）1[2] G. Natesan，A. Chokkalingam，使用平均灰狼优化算法的异构云环境中的任务调度，ICTExpress 5（2019）110-114。[3] A.R. Arunarani，D. Manjula，V. Sugumaran，云计算中的任务调度技术：文献调查，未来一代。Comput. 系统91（2019）407-415。[4] X. Wei ，基于改进蚁群算法的云计算任务调度优化策略，J.Ambient Intell. Humaniz. Comput.（2020）1-12.图四、4 0 0 个 任 务 的 算 法 收敛性能。空间，并在寻找最佳解决方案时在开发和探索之间提供适当的平衡。图图4示出了对于任务=400的情况，算法在30次模拟运行上的平均收敛。算法使用（1）中给出的适应度函数来评估解。如图4所示，ESFO在其他算法中获得最佳排名。5. 结论本文介绍了云计算中的一个关键问题--任务调度的ESFO算法。ESFO算法改进了传统SFO算法的授粉算子，使其能够更好地搜索解空间。该算法能找到一个时间复杂度为多项式的最优任务调度问题.通过对多个测试用例的测试，证明了ESFO算法相对于标准SFO算法和其他同类算法有明显的改进。CRediT作者贡献声明Hojjat Emami：提出了ESFO优化算法的思想，实现了ESO算法并将其应用于任务调度问题，执行并监督了[5] N. Mandarin，B.M.H. Zade，M.M.基于改进粒子群优化和模糊理论的云计算混合任务调度策略，Comput. 印第安纳Eng. 130（4）（2019）597[6] J. Zhou，Sh. Dong，用于云环境中任务调度的混合萤火虫群优化，Eng. Optim。50（6）（2018）949-964。[7] S. Velliangiri等人，混合电子搜索与遗传算法用于云计算中的任务调度，Ain Shams Eng. J. 12（1）（2020）631-639。[8] J. Meshkati，F.云计算中基于粒子群优化和人工蜂群算法的能量感知资源利用，J。超级计算机75（5）（2019）2455[9] 工作单位Khan等人，烟花启发式范例的可靠处理非线性有源噪声控制，应用新的应用。146（2019）246-260.[10] 张平，赵孟初，基于两阶段策略的动态云任务调度，IEEE Trans.Autom. Sci. 15（2）（2017）772-783。[11] D. Ding等人，基于Q-learning的节能云计算动态任务调度，FutureGener。Comput. 108（2020）361-371.[12] J.Yang等人，提出了一种基于博弈论的云计算能量管理任务调度算法。Comput. 105（2020）985-992.[13] J. Xiao等人，提出了 一 种 基 于 博 弈 论 的 云 制 造 多 任 务 调 度 算法。Eng. 27（4）（2019）314[14] G. Ferreira Gomes，S.S. da Cunha，A.张文，复合材料层合板损伤识别的一种向日葵优化算法。Comput. 35（2）（2019）619100200300400−0.170.341.570.73竞合利益期货条例1.692.001.161.81HGSO0.560.452.582.24能耗MGWOSFO−0.340.903.081.372.141.453.20