基于模因优化和循环调度的多目标负载均衡技术

罗 宁 李 璐 唐 忠

1(广西经贸职业技术学院网络与现代教育技术中心 广西 南宁 530021)2(广西医科大学信息与管理学院 广西 南宁 530021)

0 引 言

云计算是目前计算机领域内技术发展的焦点之一，它是将传统的分布式计算、并行计算、网格计算融为一体的数据服务系统[1]。由于云环境的动态特性，虚拟机(Virtual Machine，VM)会出现负载不平衡的问题[2]。因此，任务调度器需要通过将总负载分配给云系统中的所有可用节点来平衡负载。平衡负载的主要目标是最大限度地利用资源，提高服务质量。在云环境中，计算资源服务质量的好坏是衡量云计算效果的一个重要指标，因此，如何有效地降低云计算中的负载均衡、提升计算资源利用率是当前研究的热点问题。

负载均衡的概念在2001年由Zomaya提出，是指将任务分摊到多个操作单元上执行的过程[3]，其避免产生系统瓶颈或者资源浪费。迄今为止，国内外研究学者已经开发出许多传统算法、启发式和元启发式算法等用来解决任务负载优化问题。经典的Min-Min与Max-Min算法通过优先安排计算量过小或过大的任务方式缩短总任务完成时间，但是这类算法的负载均衡较差[4]。启发式算法[5]包括蚁群算法、遗传算法、粒子群算法和萤火虫算法等算法以及相关的改进融合算法。这类方法具备操作简单、鲁棒性强和扩充性好的特点，能够有效地缩短任务完成时间，解决资源负载均衡的问题。Tseng等[6]提出了一种动态预测云数据中心资源利用率和能耗的多目标遗传算法，用于云数据中心的动态资源预测和任务分配。但是，在遇到用户请求激增的突发情况时，负载平衡性能较差。Chou等[7]提出了基于粒子群优化算法的动态节能资源分配机制，利用最小二乘回归方法对物理机资源利用率进行预测，实现动态节电资源分配，但是，该方法没有考虑云环境中带宽、内存等其他资源的利用率。Zuo等[8]提出了一种基于蚁群优化(mosaco)的面向任务的多目标调度方法，根据时间期限和成本约束，对混合云计算环境中公共和私有计算资源的有限池进行优化。Vakilinia[9]提出了基于时间负载感知的资源调度算法，通过服务器功耗、网络通信和迁移成本的联合优化，减少数据中心的资源使用成本，提高利用率。

针对现有多目标调度方法所需处理时间较长以及处理突发情况时性能降低的问题，提出一种基于模因优化和循环调度的多目标负载均衡技术。本文的主要创新之处在于在考虑云服务器多目标调度问题时，将工作状态区分为两种模式：若工作状态为突发，选择加权多目标模因优化循环调度算法；若工作负载状态为正常，则采用阈值多目标模因优化技术调度任务。这样可以通过选择不同的负载平衡算法来提高任务调度效率，实现以更高的效率和最短的时间来平衡云中虚拟机之间的工作负载的目标。

1 模因算法

模因算法(Memetic Algorithm，MA)在1989年由Moscato提出[10]，灵感源于达尔文和拉马克的基因遗传理论。该算法是将遗传算法和局部搜索策略相结合的智能算法，具有全局优化能力和局部优化能力。由于MA存在局部搜索机制，即使初始种群的个体与最优解相差很大，也能在单次迭代过程中达到个体局部最优，可行解在剔除适应度很差个体的同时，向最优解不断逼近，从而显示其较强的寻优效率及极高的容错能力。

模因算法可以应用于单目标优化问题，也能够在多目标优化问题中取得很好的效果。图1给出了模因算法在单目标、多目标优化问题中的搜索过程。MA在最优解搜索过程中，全局搜索用于在特征空间内定位最优解的潜在区域，局部搜索是在潜在区域内进行精确定位。

(a) 单目标优化问题 (b) 多目标优化问题图1 模因算法在单/多目标优化问题的搜索过程

MA的大致流程如算法1所示。

算法1模因算法

Begin

t=0；

种群初始化：随机选择初始种群P(t)；

评价种群P(t)中的每个个体；

while(中止条件) do

在种群P(t)中的全部/部分个体进行局部搜索；

评价种群P(t)中的每个个体；

复制种群P(t)得到临时种群P′(t)；

对种群P′(t)使用重组、变异等随机操作；

合并种群R(t)=P(t)∪P′(t)；

从R(t)中选择个体产生下一代新种群P(t+1)；

t=t+1；

end while

end

目前，模因算法在单目标优化问题的搜索性能上表现优良，在多目标优化问题(Multi-Objective Optimization Problems，MOOP)中的应用还没有被广泛讨论。MOOP需要在单目标优化问题的基础上，解决局部搜索中最优解的排序问题。一般而言，处理这个问题存在两种方式：采用聚合函数或Pareto排序。由于基于聚合函数的方法在优化效果方面明显高于基于Pareto排序的方法，因此，大多数学者采用聚合函数求解MOOP问题。Chen等[11]给出了模因算法在局部搜索中采用不同聚合函数时多目标优化问题的解，该模型中的Pareto前沿具有良好收敛性和确定性，从而验证了模因算法在MOOP问题上也具备很强的适应性。

2 算法设计

云数据中心由一系列连接到互联网的服务器组成。因此，任务调度器需要安排调度云环境内的任务执行顺序。一个优越的调度器使用较少的资源(如能耗、带宽、内存和时间)来完成用户任务。针对云资源管理的多目标问题，本文采用改进的模因算法和循环调度方法[12]，将用户请求任务调度到资源最佳的虚拟机上，在最少的时间内实现负载均衡。

图2给出了本文算法在云环境中平衡负载以获得增强任务调度性能的整个过程。首先利用检测器判断用户发送请求数量。如果在很短的时间内接收到大量的请求，会导致突发，并影响负载平衡性能。本文选择不同的负载平衡算法来提高任务调度效率，当突发检测器(Burst Detector，BD)发现工作负载状态为突发时，选择加权多目标模因优化循环调度算法，将用户任务分配给云中资源最优的虚拟机；如果该工作负载状态为正常，则采用阈值多目标模因优化技术调度任务，从而实现以更高的效率和最短的时间来平衡云中虚拟机之间的工作负载的目标。

图2 本文算法的架构示意图

2.1 突发检测器

突发检测器用于识别云环境服务器的工作负载变化，然后通过预设阈值来确定工作负载的状态。当用户请求到达云服务器时，BD将用户请求的速率与阈值进行比较。如果用户请求数量在短时间内激增，即任务到达时间t的速率大于阈值，则定义此时工作负载状态为突发。否则，工作负荷状态为正常。通过考虑突发检测器的输出结果，提出的技术选择合适的负载平衡方法来调度用户任务。

2.2 负载平衡算法

本文设计了两种负载平衡算法，即阈值多目标模因优化算法和加权多目标模因优化循环调度算法，分别应用于正常和突发工作负载条件下的用户任务调度。

2.2.1阈值多目标模因优化算法

阈值多目标模因优化算法是结合遗传算法和局部搜索策略的智能算法，根据适应值与基于退火选择、离散交叉和翻转变异等进化运算原理来确定有效任务调度的最优虚拟机。阈值多目标模因优化算法的流程如图3所示。算法首先从云服务器中的虚拟机数量填充种群开始。其次计算每个群体的模因适应值，以确定分配给用户任务的最佳虚拟机。然后使用退火选择从群体中挑取好的解决方案，接着将离散交叉应用于通过组合选定的解决方案来创建新的解决方案。交叉后，通过随机改变解的方式对解进行翻转突变。最后，采用局部搜索算法，获得当前迭代中最佳的云负载平衡解决方案。通过设定迭代阈值后，输出多次迭代的结果，并作为全局最优解。

图3 阈值多目标模因优化算法流程

云环境下的用户i(i=1,2,…，n)发送请求到云服务器(Cloud Server，CS)，CS根据用户请求到达的时间和数据中心中虚拟机利用率的详细信息来向资源利用率较低的终端用户提供不同的服务。考虑一个数据中心，具有n个虚拟机VM，通过计算能耗、任务完成时间、带宽和内存消耗等多个目标来衡量虚拟机VMi的资源利用率。能耗指虚拟机在云环境中为用户提供所需服务使用的能量，VM的能耗为：

EVM=pow(UR)×t

(1)

式中：EVM表示VM的能量消耗;pow(UR)表示为云用户提供所需服务使用的能量；t表示服务时间。

虚拟机任务完成时间为：

TVM=ts-te

(2)

式中：ts和te分别表示处理任务的开始和结束时间。

VM的带宽消耗通过可用带宽ba和未使用带宽bu之间的差异计算：

BVM=ba-bu

(3)

虚拟机处理用户任务所需的存储空间量可被定义为：

MVM=Ts-us

(4)

式中：MVM表示虚拟机的内存利用率；Ts和us分别表示总空间和未使用空间。

在阈值多目标模因优化算法中，首先利用VMi(i=1,2,…,n)初始化种群，根据下面的多目标问题计算所有VM的模因适应值FVM：

FVM={EVM,TVM,BVM,MVM}

(5)

利用退火选择(Annealed Selection，AS)挑取具有模因适合度高的种群(即VM)用于下一代，进而找到用于云中任务调度和负载平衡的最佳VM。当种群生成出现变化时，每个种群的模因适合度值和选择概率也会发生变化。种群选择的概率在数学上被估计为：

(6)

式中：Fi表示种群的平均适合度；N表示种群数量。

离散交叉(Discrete Crossover，DC)是使用随机实数来生成一个后代，随机实数决定从哪个父母那里取出后代的模因。离散交叉过程如图4所示，DC选择P和Q作为父母，R是P和Q生成的后代，其模因可从父母中选择。

图4 离散交叉过程

翻转突变(Flip Mutation，FM)如图5所示，通过修改染色体中的0和1达到翻转突变的目的。对于突变染色体中的1，父染色体中的后续位被翻转来构建子染色体。

图5 翻转突变过程

在完成突变过程后，应用局部搜索，选择具有较高适合度值的VM作为执行用户任务的最佳虚拟机。局部搜索(Local Search，LS)在数学上定义为：

(7)

式中：FVM和FT分别表示VM和阈值的模因适度值。

通过使用式(7)，阈值多目标模因优化算法利用模因适度值的局部寻优，在多个VM之中找到最佳VM用于调度任务。阈值多目标模因优化算法适用于非突发条件下的云中VM工作负载平衡问题。

2.2.2加权多目标模因优化循环调度算法

加权多目标模因优化循环调度算法旨在优化突发工作负载情况下的具有不同处理能力的VM。该算法首先通过计算当前VM的能耗、带宽、内存、任务完成时间，以及负载情况来确定模因适合度，然后根据适合度为每个VM分配权重，最后该算法根据权重系数安排完成用户任务VM的顺序及响应次数。例如，如果VM1和VM2的权重是3、5，则该算法采用循环调度的方式将3个用户请求转发到VM1上处理，将5个用户请求转发到VM2上。

在加权多目标模因优化循环调度算法中，同样利用VMi(i=1,2,…，n)初始化种群，根据多目标问题计算所有VM的模因适应值FVM：

(8)

式中：LVM表示VM的当前负载。

(9)

式中：T表示VM的总容量；Nt表示在当前VM上运行的用户任务的数量。

VM的权重系数为：

(10)

通过使用式(10)来确定每个VM的权重值。然后加权多目标模因优化循环调度算法通过执行AS、DC、FM和LC在多个虚拟机中选取较高权重的VM，以便处理用户请求的任务。当云计算中遇到突发性工作负载情况时，通过引入权重值，加权多目标模因优化循环调度算法在每轮中将用户请求任务分配给已识别的最佳VM，以最小的资源利用率在云中平衡突发性工作负载。

2.3 帕累托前沿

多目标优化问题的解决方案在数学上以非支配点表示，即只有当解决方案在所有标准中具有优越性能时，解决方案才占优势。如果解决方案不能被搜索空间中可用的任何其他解决方案所支配，则称该解决方案是帕累托最优。所有帕累托最优解的集合被称为帕累托集，其在客观空间中的图像称为帕累托前沿[13]。

云中的工作流调度可以被视为多目标优化问题，其目标是找到一组良好的权衡解决方案，使用户能够在目标之间选择所需的权衡。本文算法目的是从初始群体中找出帕累托最优集合以调度用户请求的任务，即开始于一群随机生成的候选解决方案，并在更多的生成或迭代次数上向更好的解决方案集(帕累托最优解决方案)发展。图6给出了本文算法的帕累托前沿。其中：X轴表示种群初始化值(即不同数量的用户请求任务)；Y轴表示用于平衡云中工作负荷的帕累托最优集(即为调度任务正确选择的最佳VM的数量)。

图6 本文算法的帕累托前沿

3 实验结果与分析

为了评价本文算法的性能，使用Amazon EC2数据集通过CloudSim仿真器以Java语言进行测试实验，它是一项基于Web的服务，允许用户在Amazon Web Services(AWS)公共云中运行应用程序。为了对比性能，本文算法在相同条件下与多目标遗传算法(MGA)[6]和动态节能资源分配(DPRA)[7]等现有的负载平衡方法的测试结果进行比较。

Amazon EC2数据集[14]为发送请求的用户提供必需的服务。Amazon EC2数据集包含以下属性：名称、API名称、内存、计算单位、核心、存储、Arch、网络性能、最大带宽、最大IP、Linux成本和Windows成本。Amazon EC2数据集允许开发人员使用虚拟机VM，VM为与全球AWS数据中心一起运行的IT项目和云工作负载提供计算能力。测试数据考虑在25～250范围内的不同数量的用户请求任务来执行实验评估。本文仿真实验的运行环境为Windows10系统下Intel(R) Core(TM) i7-7700HQ处理器。

采用调度效率，调度时间和能耗三个性能评价指标来评估本文方法的性能。调度效率是计算正确调度到最佳VM的用户请求任务数与用户请求总数的比率：

(11)

式中：N表示用户请求总数量；NURs表示正确调度到最佳VM的用户请求的任务数。

调度时间是指将用户请求任务调度到最佳VM所需的时间：

ST=N×t(SSUR)

(12)

式中：t(SSUR)表示调度单个用户请求所用的时间。

能量消耗是估计虚拟机执行用户请求任务时所需要的能量：

EC=N×E(SSP)

(13)

式中：E(SSP)指执行单个用户请求任务所需的能量。

图7-图9给出了三种方法用于平衡云服务器中的工作负载时的调度效率、调度时间和能耗对比。可以看出，利用本文技术处理云中的突发和非突发工作负载时的调度效率都非常高，调度时间和能耗则是随着用户请求数量的增加而递增。此外，本文算法在调度效率、调度时间和能耗方面的性能明显优于其他算法。

图7 不同用户请求时的调度效率对比

图8 不同用户请求时的调度时间对比

图9 不同用户请求时的能耗对比

4 结 语

为了在正常和突发工作负载条件下提高云中用户任务的调度效率，本文提出一种基于模因优化和循环调度的多目标负载均衡算法。通过设计阈值多目标模因优化算法和加权多目标模因优化循环调度算法来应对云计算中正常负载和突发负载时的用户请求任务的调度工作。实验结果表明，与其他算法相比，本文方法在调度效率、调度时间和能耗方面具有明显的优势。