云计算环境中基于自适应PSO的任务调度方法研究

摘要:负载均衡任务调度可以提高云计算系统性能，为实现负载任务最优调度，本文提出了一种基于粒子群优化(PSO)的自适应任务调度方法，通过引入了一种自适应惯性权重策略，即线性递减和自适应惯性权重(LDAIW)，在局部搜索和全局搜索之间实现了更好的平衡，从而优化了任务调度。实验结果表明提出的方法与其他金典方法相比，在时间跨度，提高吞吐量和平均资源利用率方面有显著提高。

关键词：负载均衡、自适应惯性权重、时间跨度、吞吐量、平均资源利用率

中图分类号：TP301.6

引言

云计算给计算技术带来了革命性的变化，通过互联网全球都可以访问计算资源[1]。目前基于蜂群智能的元启发式算法被认为更适用于云调度和负载平衡。基于蜂群智能的元启发式算法的优化过程包括两个主要部分，即局部搜索和全局搜索。[2]本文提出了一种基于粒子群优化（PSO）的自适应任务调度方法，克服了 PSO 算法局部搜索能力较弱，不能更多关注局部子空间的搜索的局限性，实现有效调整了PSO 惯性权重。所提出的调度方法在局部搜索和全局搜索之间实现了更好的平衡，最大限度地缩短任务执行时间，提高云资源利用率和吞吐量。通过实验将拟议方法与其他经典方法进行了比较，深入研究和分析基于元启发式算法的最新云任务调度方案，对基于PSO算法的最突出和最先进的惯性策略进行经验评估。

1. 方法

1.1 POS模型

PSO 算法是一种基于全局搜索的自适应优化方法[3]。这种方法是基于群体的调度技术，依赖于粒子的社会行为。这是一种基于群体智能的方法，其灵感来自鱼群和鸟群的社会行为。蜂群种群由世代和粒子组成，世代显示了获得优化解决方案所需的迭代总数,每一代都有多个粒子，一代中的每个粒子都显示一个解决方案。[4]代数和粒子数因情况而异，通过调整可获得更优化的解决方案。每个粒子都有位置、速度、个人最优 (pBest) 和全局最优 (gBest)。个人最优显示的是一个粒子的最优解，而全局最优显示的是所有粒子的最优解。每次迭代都会根据粒子的惯性权重、pBest和gBest更新所有粒子的速度和位置。假设D代表解决方案空间的维度，其中Xi是一个向量，代表粒子在搜索空间中的位置，公式如下：

       (1)

在每次迭代中，粒子都会不断改变自己的位置，寻找更合适的解决方案Pbi，可用如下公式表示：

      (2)

Vi表示粒子的速度，公式如下：

        (3)

如果新值优于当前值，则会在所有迭代中更新每个粒子的 pBest 值。基于PSO的启发式方法会计算并记录粒子群中所有个体的最佳值,即等式 (4) 所示的 gBest。

   (4)

使用基于PSO的启发式方法解决任务调度问题，并将调度作为搜索解决方案输入，在 PSO 粒子和问题解决方案之间确定合适的映射。PSO 的每个粒子都会指出任务与虚拟机映射的可能解决方案。在此映射中，使用了五个具有不同处理能力（单位为每秒百万指令数（MIPS））的虚拟机。VM1的计算能力为50 MIPS，VM2、VM3、VM4和VM5的计算能力分别为100MIPS、200MIPS、350MIPS和500 MIPS。

1.2 系统模型

任务调度方案的目标是在云资源上选择优化的任务映射策略，从而缩短任务执行时间，提高平均资源利用率(ARUR )和云吞吐量。考虑到用户的应用程序由一组D个独立的计算密集型任务（即 Tsks = Tsk1、Tsk2、Tsk3、......、Tskd）组成，需要在一组M个虚拟机（即Ts = T1、T2、T3、......、Td）上进行调度，其计算能力以 MIPS 为单位，其计算需求以 MI 为单位。当任务TD映射到 VMj时，分配任务的预期完成时间 (ETC) 将通过如下公式计算得出：

       (5)

其中RTj是VMj的就绪时间，即VM完成已分配工作负载所需的时间。EETdj 是任务TskD在VMj上的预期执行时间（EET），由任务计算需求（以MI为单位）除以虚拟机计算能力（以MIPS 为单位）得出，其公式如下所示：

     (6)

Makespan是所有虚拟机的最大完成时间，计算公式如下所示。

    (7)

1.3 PSO 模型的惯性权重策略

所有基于蜂群智能的元启发式算法的优化过程都包括两个主要阶段,这两个阶段包括局部搜索和全局搜索。[6]全局搜索和局部搜索的平衡对找到最优解起着关键作用。理想情况下，在搜索程序开始时，全局搜索空间的支持应大于局部搜索空间。这可以让基于群体的元启发式算法在开始时探索更多的搜索空间，然后更谨慎地找到全局最优位置。惯性权重是保持局部搜索和全局搜索平衡的最强控制因素。

文献[7]研究表明，许多研究人员都致力于惯性权重选择策略，以平衡粒子的局部搜索和全局搜索。然而，仍有必要改进这种平衡。研究人员提出了多种惯性权重策略、不过，其中一些惯性权重在研究界很受欢迎。这些惯性权重策略包括简单随机惯性权重（SRIW）、混沌惯性权重（CIW）、混沌随机惯性权重（CRIW）、线性下降惯性权重（LDIW）和自适应惯性权重（AIW）。

PSO 算法的性能取决于最佳参数设置和惯性权重[9]。在搜索区域内寻找最优解时，惯性权重能在探索和利用之间取得平衡。本结合了LDIW和AIW策略的优势提出了一种新的惯性权重策略 “线性递减自适应惯性权重（LDAIW），具有 LDIW 的线性递减特性，并能根据AIW的反馈行为调整权重值，表示公式如下：

    (8)

由于 LDAIW 具有线性递减和自适应的特点，因此它在 Makespan、吞吐量和ARUR方面的表现优于其他先进方法。

2. 实验设置和模拟结果

为了评估和比较所提出的方法，拟议策略与五种不同惯性权重的PSO算法进行了比较。这些惯性权重策略包括 SRIW、CRIW、CIW、LDIW和 AIW。实验使用 makepan、吞吐量模拟优化后的解决方案。通过比较PSO与其他五种著名惯性权重策略生成的结果，验证了所提方法的结果。

2.1 参数初始化

搜索过程开始时，粒子被初始化到一些随机位置，如表1所示。对于任务到虚拟机的映射，在此阶段会将任务随机分配给虚拟机。

表1 初始化参数

在通过设置不同的最大迭代次数和粒子大小值进行全面微调后，固定了最大迭代次数和粒子数（200 次迭代和 20 个粒子）。下限和上限分别设置为零和虚拟机数量-1（VMCount-1）。

VMs-1 (VMCount-1)。w1和w2的值分别设置为 0.4和0.9。加速因子c1和c2的值分别初始化为2和1.49455。停止标准为最大迭代次数（MaxItr），即200次。

2.2 模拟环境

为了进行实验和评估所提出的调度技术，使用了仿真环境。这是因为，在仿真环境中，可以使用任何数量和类型、具有不同异构水平的资源来进行实验。这是因为在模拟环境中，可以使用具有不同异构水平的任何数量和类型的资源进行实验。此外，实验可以根据需要多次进行，不受时间和执行成本的限制。表2概述了实验所使用的实验装置。

表2 仿真环境配置

3. 实验执行和结果

作为随机优化方法，基于元启发式的算法需要运行多次，以实现有意义且更真实的统计评估。在本研究中，每种方法都针对HCSP 数据集的每个实例执行了5次，并计算这些运行的平均值，然后进行比较。

正常运行时间是性能评估的关键参数，也是云用户的最终需求。图1是AdPSO和现有先进方法在 HCSP 基准数据集的i_hilo、c_hilo、c_lohi和 i_lohi实例中的耗时结果。结果表明，SRIW、CRIW 方法在 HCSP 数据集的所有四个实例中都表现出了较差的时间跨度性能。CDIW 和 LDIW 方法在 HCSP 数据集的 c_hilo 和 i_hilo 实例中表现有所改善，而在 c_lohi 和 i_lohi 实例中表现稍差。与 HCSP 数据集的 c_lohi 和 i_lohi 实例相比，AIW方法在 c_hilo 和 i_hilo 实例中的表现更好。

图1时间跨度对比

比较AdPSO性能的另一个关键参数是吞吐量。图2显示了AdPSO技术的吞吐量结果，并比较了HCSP数据集的 c_hilo、i_hilo、c_lohi 和i_lohi实例。与makepan结果类似，所有比较方法的吞吐量结果也观察到类似的行为。所有比较方法的吞吐量结果也类似。图2显示，建议的调度器在执行c_hilo时的吞吐量提高了1-7%，在执i_hilo时的吞吐量提高了2-12%，在执行c_lohi时的吞吐量提高了1-6%。

图2吞吐量对比

4.  结论

PSO任务调度方法收敛速度快，易于实施，是一种更适合负载平衡任务调度的方法。惯性权重是在全局和局部搜索空间之间保持平衡的关键属性。本文利用基于PSO的调度器全面研究了五种惯性权重策略,对所提出方法的性能进行了评估，并与五种著名的基于PSO的惯性权重策略进行了比较。实验结果表明，与其他方法相比，所提出的方法在时间跨度、吞吐量和ARUR方面分别提高了10%、12%、30%。

参考文献

[1] 陈岩.关于云计算技术及其应用的探讨[J].黑龙江科技信息, 2013(25):1328-1348.

[2] 刘正伟,张海涛.云计算和云数据管理技术[J].计算机研究与发展,2012,49(S1):26-31.

[3] 钱敏.云计算背景下数据中心资源调度方法研究[J].信息技术,2022(05):188-192

[4] 邱亚,颜金尧,陈宇,耿俊杰.开源云计算资源调度策略优化研究[J].计算机技术与发展,2023,33(06):8-15.

[5] 朱国晖,史思潮,翟鹏宇.基于蚁群优化的数据中心网络负载均衡算法[J].西安邮电大学学报,2022,27(05):11-17

[6] 王镇道,张一鸣.基于竞争粒子群算法的云计算资源调度策略[J].湖南大学学报,2021,48(06):80-87

[7] 吴俊鹏,刘晓东.一种基于集群的动态负载均衡算法研究[J].电子设计工程.,2021,29(16):75-78

[8] 马卫国,邵诚.网络控制系统随机稳定性研究[J].自动化学报,2007(08):878-882

[9] 张佳乐.边缘计算数据安全与隐私保护研究综述[J].通信学报,2018,39(03):16-22