基于人工蜂群的云计算负载均衡算法

贾 嘉,慕德俊

(1.西北工业大学自动化学院，西安 710072;2.西北工业大学网络空间安全学院，西安 710072)

云计算将所有的计算资源及计算任务都托管在云上，通过互联网向用户提供计算服务。云计算环境中的处理单元被称为虚拟机(virtual machine,VM),调度器负责检查虚拟机是否计算负载过高或过低,或者是否有任务闲置[1]，并通过任务的迁移使得各个虚拟机上的计算负载尽可能平均。负载均衡是云计算的主要问题之一，目前已有大量用于寻求负载均衡的算法。云计算负载平衡算法可分为三大类别：通用负载均衡算法、基于体系结构的负载均衡算法、基于人工智能的负载均衡算法。

通用负载均衡算法在不考虑具体的云计算体系结构的前提下，提出适用面较广的算法。此类算法类似计算机操作系统中的资源分配与调度方法，例如：轮询、先到先服务、最短服务时间方法等。文献[2]提出了加权的轮询算法(weighted round-bin)、最短期望延迟算法(shortest expected delay) 等经典的通用算法，并对比了其性能。Gupta等[3]根据虚拟机每秒钟执行的机器指令数(machine instruction per second,MIPS)和故障率两个指标设计了负载均衡算法。文献[4]将云系统中的处理器核作为计算资源调度的基本单位来实现负载平衡。Wang等[5]为三层结构的云计算系统提出了一种两阶段的负载调度与均衡算法。

基于体系结构的负载均衡算法关注某种具体云系统架构下的负载均衡问题。此类算法往往不是显式实现负载均衡的，而是通过设计云系统的各模块及其相互关系来隐式达成负载均衡。文献[6]构建了一种云系统架构，此架构包含两种最主要的模块：资源管理模块和消息管理模块。资源管理模块定期收集处于活跃状态的计算资源的负载情况以及用户对计算资源的请求情况。而在响应用户请求的过程中，消息管理器直接与客户发生交互、并发挥核心作用。Xu等[7]将一个公共云系统划分成若干个分片，云系统整体上设置一个总控制器，各分片分别设置一个调度器。总控制器通过与各调度器的实时信息交换来刷新各调度器所掌握的负载信息，各调度器根据上述信息展开调度、实现负载均衡。

将人工智能算法应用于云系统负载平衡是学术界近年来的研究趋势[8]。其中，软计算方法模拟自然界的生物行为设计算法，解决科学与工程优化问题，已成为目前的研究热点[9]。与前述两种类型的负载均衡算法相比，基于软计算的负载均衡算法能够更加高效地处理不精确性、不确定性和不完整性[10]。与现有的典型软计算方法，如遗传算法(genetic algorithm,GA)差分演化算法(differential evolution,DE)和粒子群优化算法(particle swarm optimization,PSO)等相比，人工蜂群算法具有以下优势：①算法易于实现；②适用范围广：不要求优化目标函数解析式已知，也不要求优化目标函数连续或可微；即便优化目标函数十分复杂，算法仍可以高效执行，且在离散或连续情况下均适用；③算法性能不依赖于算法初始化技巧；④适合在分布式/并行计算平台上实现；⑤算法不宜过早收敛，且易于收敛到全局最优点。

1 云计算负载均衡与人工蜂群算法

1.1 云计算负载均衡概述

云计算根据用户或系统的不同需求提供虚拟机的动态资源池。如何接受和响应各种服务请求，取决于云计算系统的管理策略，而此策略是基于各服务器的负载情况的。在云计算系统中，负载均衡技术用于增强资源利用的并行性，通过恰当地为计算任务选择虚拟机来缩短响应时间。

诸如PSO等负载均衡算法，其主要目标是从逻辑上将全体虚拟机节点的计算资源作为一个整体，为计算任务分配虚拟机节点，并允许计算任务在虚拟机节点间迁移，最大限度地缩短完成时间并减少故障次数[11]。

1.2 人工蜂群算法

Karaboga等[12]提出了人工蜂群算法，用于解决工程优化问题。在该算法中，每个蜜蜂都是一个代理，也是优化问题的一个可能的解，它通过交换信息以协作解决复杂的组合优化问题。

该算法主要步骤可以描述如下：

(1)在觅食过程的第一步，派出若干只蜜蜂作为侦察峰开始随机探索环境以寻找花蜜来源。

(2)在第二阶段，找到食物来源后，侦察蜂成为引领蜂，并从已发现的花蜜来源获取花蜜。引领蜂回到蜂巢并且卸下花蜜后，可以直接返回到它发现花蜜的地点，或者通过摇摆舞姿来分享花蜜来源信息。

(3)在第三阶段，旁观者蜜蜂在蜂巢内观看摇摆舞姿，摇摆舞持续时间越长则表明花蜜来源质量越高。旁观者蜜蜂根据质量选择一个花蜜来源并前往获取花蜜，这种蜜蜂角色称为跟随蜂。

(4)如果一个引领蜂的花蜜来源枯竭，它会重新成为一只侦察峰，并开始随机搜索新的花蜜来源。

2 基于人工蜂群的负载均衡算法

将计算任务视为“蜜蜂”、虚拟机作为“花蜜源”，人工蜂群算法的基本思想可用于解决云计算负载均衡问题。

2.1 基本思想

在云系统中，全体虚拟机被依照其负载高低做降序排列。如果某个虚拟机负载过重，那么需要将若干个计算任务从该虚拟机上移除。当移除的任务被迁移至负载较低的虚拟机时，它们会记录当前所在虚拟机的负载情况及该虚拟机上各任务的优先级等信息，并将这些信息广播至等待队列中的全体计算任务。等待队列中的计算任务根据所接收到的信息来选择虚拟机。

每当有高优先级任务将要被迁移时，算法应从全体低负载虚拟机中选择包含高优先级任务最少的虚拟机作为迁移目的地，以便保证被迁移的任务能尽早得到执行。

实质上，计算任务扮演了蜜蜂角色，虚拟机是花蜜来源。为计算任务选择恰当的虚拟机来执行，类似于蜜蜂搜寻花蜜来源。虚拟机过载，象征某个花蜜来源枯竭；选择负载较低的虚拟机作为计算任务的迁移目的地，类似于蜜蜂寻找新的花蜜来源。被迁移的任务向等待队列中的任务广播虚拟机的状态信息，类似于侦察蜂通过摇摆舞姿将花蜜来源信息告知旁观者蜜蜂。根据虚拟机的状态信息来确定等待队列中的哪个任务应该分配给哪个虚拟机，类似于旁观者蜜蜂根据摇摆舞姿选择花蜜来源。

基于上述基本思想，针对云计算负载均衡问题建立数学模型，并将负载均衡算法设计为以下三个主要步骤：负载均衡决策、虚拟机分组、计算任务调度。

2.2 数学模型

令VM={VM1,VM2,…,VMm}为云系统上全体虚拟机的集合，C={C1,C2,…,Cn}为需要执行的全体计算任务的集合。全部n个任务都将以非抢占方式执行，即任务一旦开始执行不能被停止(但允许一个任务在完成部分计算量后，被迁移至其他虚拟机)，直至执行完毕，且暂不考虑任务执行因故障而中断的情况。

2.2.1 最大完工时间

以最大完工时间表示全体任务执行完毕所用的时间开销，记为Makespan。以第一个任务开始执行作为计时起点，令TEij代表任务i在虚拟机j上执行完成的时刻，那么有：

Makespan=max{TEij|i=1,2,…,n;j=1,

2,…,m}

(1)

负载均衡算法的目标为：令Makespan的值尽可能小。

2.2.2 虚拟机容量

定义虚拟机j的容量：

Capj=p_numj×p_powerj+bandwidthj

(2)

式(2)中：p_numj是虚拟机j具有的处理器个数；p_power是单个处理器的处理能力(以单位时间内执行的指令数衡量)；bandwidthj是虚拟机j具有的网络通信带宽。

定义整个云系统的容量：

(3)

2.2.3 虚拟机的负载

计算任务完成时长虚拟机j在t时刻的负载：

(4)

式(4)中：task_numberj,t是t时刻虚拟机j等待队列中的任务总数；service_ratej,t是t时刻虚拟机j的服务率(单位时间内能完成的计算任务个数)。

虚拟机j完成等待队列中的任务需要的时长(按t时刻的状态计算)：

(5)

整个云系统的负载：

(6)

整个云系统完成等待队列中的任务需要的时长：

(7)

2.2.4 任务完成时长标准差

任务完成时长的标准差定义为

(8)

标准差越大则说明负载在各虚拟机上的分布越不均衡。

2.3 算法流程

下面给出本文算法详细流程。

1 计算负载情况：

根据式(2)～式(4)、式(6)计算各虚拟机负载即系统整体负载。根据式(5)、式(7)、式(8)计算负载方差δ；如果δ

2 负载平衡决策：

当前时刻，若Loadt>Cap[式(3)、式(6)]，那么系统整体过载，算法退出；否则自动进行负载平衡。

3 虚拟机分组：

将所有虚拟机分为高负载、负载已平衡、低负载三个分组，依次记为Grouph、Groupb、Groupl。将Grouph中的虚拟机按负载高低做降序排列，Groupl中的虚拟机按负载高低做升序排列

4 虚拟机调度：

while Grouph≠φ且Groupl≠φ

for VMs∈Grouph

按优先级对VMs等待队列中的任务做降序排列；

依照式(9)～式(11)依次为VMs中的任务选择目的地虚拟机VMd并迁移；

每当一个任务迁移完成后重新计算VMs和VMd的负载；

如果需要，调整VMs和VMd所属分组。

end

将Grouph中的虚拟机按负载高低重新做降序排列；

Groupl中的虚拟机按负载高低重新做升序排列。

end

2.4 负载均衡决策

在基于数学模型计算得到工作负载和标准差后，云系统应该决定是否进行负载平衡。具体地，应考虑两方面因素：判断云系统整体上是否过载(即整个系统的计算负载已饱和)；判断云系统整体上否负载均衡。只有在系统未饱和的状态下，负载均衡才是有意义的。

当云系统的计算负载[式(6)]超过该系统的最大容量[式(3)]时，系统整体过载。如果云平台的负载标准偏差[式(8)]低于或等于设定的阈值threshold，那么系统是平衡的[13]；否则系统处于不平衡状态。但仅凭标准差的值无法判断整个系统处在超载或负载不足状态。

2.5 虚拟机分组

根据负载情况对虚拟机分组，包括三种类型的分组：过载的虚拟机分组、低负载虚拟机分组、负载平衡的虚拟分组。当需要从属于过载组的虚拟机上向外迁移任务时，必须根据低负载虚拟机分组的负载情况，决定把哪个低负载虚拟机作为迁移目的地。

在本文算法中，需迁移的任务扮演了侦察蜂角色，低负荷的虚拟机则是尚未枯竭的花蜜源。被迁移的任务向等待队列中的任务广播的信息包括：任务原来所在虚拟机的负载、其他所有虚拟机的负载、各虚拟机上任务的优先级、各虚拟机等待队列中任务数量、每个虚拟机分组中的虚拟机数量。负载平衡的虚拟机不会被用作任务迁移的起点或目的地。一旦任务迁移结束，那么新进入负载平衡状态的虚拟机将被归入负载平衡虚拟机分组。当全体虚拟机都被归入负载平衡分组时，系统整体负载平衡。

2.6 计算任务调度

如果决定要平衡负载，那么寻找低负载的虚拟机作为任务迁移的目的地。选择目的地的重要影响因素是任务的优先级。目的地虚拟机选择规则如下。

以UnderLoad代表低负载的虚拟机集合，high(VMj)、middle(VMj)、low(VMj)分别代表虚拟机j等待队列中高优先级任务、中优先级任务、低优先级任务的数量。

如果被迁移的是高优先级任务，那么目的地虚拟机应为

VMh,destination=VMd|VMd∈UnderLoad,

(9)

如果被迁移的是中优先级任务，那么目的地虚拟机应为

VMm,destination=VMd|VMd∈UnderLoad,

middle(VMk)]

(10)

如果被迁移的是低优先级任务，那么目的地虚拟机应为

VMl,destination=VMd|VMd∈UnderLoad,

middle(VMk)+low(VMk)]

(11)

3 实验分析

采用CloudSim[14]作为仿真环境，验证了所设计算法的性能。虚拟机个数为6，除特别说明外，仿真环境参数设置均取默认值。程序运行于一台个人计算机，内存1.75 GB，CPU为3.0 GHz。

图1对比了不采用负载均衡(计算任务先到先服务策略，且从集合VM中轮流选择虚拟机提供服务)、和采用人工蜂群算法做负载平衡两种策略的最大完工时间。横轴代表系统中任务总数，纵轴代表最大完工时间(Makespan)。由图1可见，当计算任务总数较少时，两种情况下，系统完工时间的差异也并非十分显著。其原因在于此时系统整体上处于低负载状态，即使不进行负载均衡也不易出现某个虚拟机负载过重的情况，各虚拟机的完工时间的标准差[式(8)]较小。然而，在不采用负载均衡的策略下，计算任务一旦被分配至虚拟机就无法迁移，随着任务数增多，易进入负载不均衡状态，导致高负载虚拟机完工时间变长而低负载虚拟机的部分计算资源被闲置，最终使得系统最大完工时间变长。而人工蜂群均衡算法通过“侦察蜂广播机制”，实时探查各虚拟机的负载情况，并在系统出现负载失衡时将高负载虚拟机的部分任务迁移至低负载虚拟机，这使得系统最大完工时间关于任务总数的增长率显著降低。

图1 三种算法最大完工时间对比Fig.1 Comparison of Makespan of three algorithms

如表1所示对比了粒子群算法和人工蜂群算法的最大完工时间随Cloudlet总数的变化趋势。Cloudlet是一种为处于云上移动设备的计算任务增速的模式。Cloudlet将移动设备上的计算任务迁移到同一个局域网下的服务器上执行。一个Cloudlet可以被视作为移动端计算任务实时定制的虚拟服务器。Cloudlet总数增多意味着从移动端迁移到虚拟服务器的计算任务增多。显然，人工蜂群算法具备更有的最大完工时间。

图2给出了智能蜂群负载均衡算法和粒子群负载均衡算法[15]在反应时间上的对比。很显然，前者具有更短的反应时间。

表1 最大完工时间关于Cloudlet总数的变化趋势对比：粒子群算法与人工蜂群算法Table 1 Comparison of the change trend of the maximum completion time with respect to the total number of Cloudlets

图2 粒子群算法与人工蜂群算法系统反应时间对比Fig.2 System response time comparison:between particle swarm optimization algorithm and artificial bee colony algorithm

图1也显示了粒子群算法和人工蜂群算法的Makespan比较，可以清楚地看出，与粒子群算法相比，人工蜂群算法更有效。

比较了两种算法的负载不平衡度。负载不平衡度由式(12)给出：

(12)

不平衡度越大则说明负载在各虚拟机之间的分布越不平衡。图3对比了不采用负载均衡策略和采用人工蜂群负载均衡算法两种情况下的不平衡度。在不采用负载均衡策略的情况下，M个虚拟机依次接收计算任务，且不能动态迁移计算任务，负载不平衡度较高且出现明显的波动。采用人工蜂群算法做负载平衡后，可以实时地更新各虚拟机的负载状态并将计算任务分配到负载较低的虚拟机上执行，这显著降低了不平衡度，也显著减缓了不平衡度随计算任务增加而出现的波动。此外，图3也显示了人工蜂群算法的不平衡度明显低于粒子群算法的不平衡度。

尽管任务迁移有助于系统整体的负载平衡，但是任务迁移会带来计算环境切换、网络通信等时间开销。如果迁移次数过多，也会影响系统的性能。负载均衡算法必须从全局角度考虑任务调度，尽可能减少任务迁移。本文算法优先选择低优先级的任务进行迁移，从而尽可能避免任务迁导致移高优先级任务被拖延。图4对比了粒子群算法与人工蜂群算法的任务迁移次数。显然，本文方法有助于减少不必要的任务迁移。

图3 三种算法的不平衡度对比Fig.3 Imbalance comparison three algorithms

图4 粒子群算法与人工蜂群算法的任务迁移次数对比Fig.4 Comparison of task migration times between particle swarm optimization algorithm and artificial bee colony algorithm

4 结论

源自自然现象的算法往往能为动态优化问题提供高效的解决方案。将人工蜂群算法用于云计算系统负载均衡。此算法利用群体智能来从过载的虚拟机中移除任务，并将这些移除的任务提交给最适合的低负载虚拟机。算法不仅平衡了负载，而且在迁移任务的过程中考虑了等待队列中任务的优先级。选择具有最低优先级的任务进行迁移以减少不平衡。实验结果表明，该算法在最大完工时间、反应时间、不平衡度、任务迁移次数等指标上均具有较优的性能。

未来进一步的工作将关注如何将蚁群优化(ACO)、粒子群优化(PSO)等算法的优势融入人工蜂群算法，以进一步提高算法效率。