云计算环境下基于非均匀窗口蚁群行为的负载平衡算法
2016-08-06张少辉崔仲远韩秋英
张少辉，崔仲远，韩秋英
(周口师范学院 计算机科学与技术学院，河南 周口，466001)
云计算环境下基于非均匀窗口蚁群行为的负载平衡算法
张少辉，崔仲远，韩秋英
(周口师范学院 计算机科学与技术学院，河南 周口，466001)
摘要：针对云计算环境下可能面临请求过载和较长响应时间的问题，在非均匀窗口蚁群行为思想的启发下，提出一种负载平衡算法。假设云环境下任何时候虚拟机都处于过载状态，即服务提供者不得不分配资源。根据该假设，对可利用的资源合理优化，优化过程中动态代理和静态代理同时进行，其中蚁群行为被用于负载平衡，通过加载资源到所有的虚拟机上来实现系统平衡。利用CloudSim仿真器模拟云计算环境进行实验分析，实验结果表明，与容错分簇的负载均衡感知(tolerant cluster-aware，TCLB)、基于博弈论的负载均衡算法(scheduling strategy on load balancing，SSLB)和基于蜜蜂行为的负载均衡算法(honey bee behavior inspired load balancing，HBB-LB)相比，提出的算法分别节省了37%，8%和4%的响应时间，最大完成时间也大幅度降低，整体性能有所提高。
关键词：云计算；负载平衡；代理；蚁群行为；响应时间；最大完成时间
0引言
在高度可靠的大型网络中，云计算[1]是一种基于分布式互联网用于远程分享、使用不同资源与服务的设计模式，如存储、计算能力和应用程序等。然而，由于动态传入的请求，在此过程中需要进行动态资源分配，云计算领域固有的动态性需要高效的负载平衡机制，即资源分布在不同用户或者统一的请求方式中，没有节点是处于过载状态或处于闲置状态[2-3]。负载平衡是云计算的一个重要方面，在没有提供负载平衡的情况下，一些过载节点的效率就可能大幅下降，最终导致违反服务等级协议[4](service level agreement，SLA)。
传统的分布式计算、 并行计算和网格计算环境下负载平衡算法分为静态、动态或混合调度算法[5]，云计算环境下的算法是动态负载平衡算法，即重点是减少通信延迟和执行时间，满足用户的动态服务，同时优化负载平衡。
1相关工作
负载平衡是各种计算机网络中最重要的问题之一。为了解决这个问题，已有很多学者对其进行研究。
文献[6]提出在公共负载平衡中引入一种博弈论的模型。该算法根据负载程度把云划分为3类，分别是空闲云、正常云、过载云。零负载的云代表空闲云，如果处于零和最高值之间就是正常云，否则就是过载云。但这种负荷度范围的选择问题一直都没有得到解决。
文献[7]提出了一种利用虚拟调度机制的遗传算法来达到虚拟服务器之间的负载平衡。以种群粒子优劣为依据自适应调整惯性权重，这种机制选择负载最小的虚拟机(virtual machine，VM)来提供负载传输和优化高昂的迁移成本。然而由于数据中心大量的虚拟机和频繁的服务请求，可能导致服务调度效率低下。
文献[8]提出了2种云环境下的动态算法。第1种是针对机会主义负载平衡，即由节点传入任务时具有最小执行时间；第2种是维持最小负载平衡以提高资源利用率。然而这2种算法均不适合抄送环境。抄送环境需要提前将所需虚拟资源部署在系统中，选择一个影响最小的解决方案，达到最佳负载平衡，同时减少或避免动态迁移，而文献[8]的2种算法均无法提前部署资源。
文献[9]提出了一种利用分形方法触发的策略和多准则决策的方法。分形方法避免了瞬时峰值的迁移问题，多准则决策的方法是为了解决对不同物理资源分配的决策问题，虽然在资源选择方面更加均衡，但该模型在提交任务过程中需要较多的响应时间。
文献[10]将遗传算法思想加入到分布式负载均衡算法中，获取对不同目标的权重运算，提出了一种面向云计算的负载均衡算法，为大型云系统的负载均衡问题提供了潜在的可行方案，减少了物理节点的使用数量和迁移次数，然而，该算法的资源利用率不高。为了提高资源利用率，文献[11]研究了蜜蜂觅食方案并检测了分布式随机抽样方法，该方法通过加载近乎全局的均值测量来维护各个节点。
文献[12]提出了一种工作在2个相位的机制，在第1相位可以确定CPU的利用率和每个实例所开销的内存，同时，也能知道每个虚拟机的内存可供开销的量；在第2相位，比较可用资源和所需资源，如果所需资源可以获取，则进一步确定是否丢弃请求，但这种机制的缺点在于缺乏可扩展性。
从上述方法可以看出，人工智能机制如遗传算法、蜜蜂算法、博弈论和智能代理等都能应用于云计算中的负载平衡，但诸如此类负载平衡算法的动态特性缺乏可扩展性和可靠性。因此，需要一种具有良好可扩展性和可靠性的算法，即尽可能地提供动态资源调度、最大化资源优化配置、最大化吞吐能力、最小化响应时间。
2平衡算法组件
负载平衡算法具有5个主要原则[5]及功能，如表1所示。算法提供效率的依据有5点[5]。
1)可靠性。算法必须是可靠的，因为将工作从一个位置转移到其他位置时，进程失败可能增加等待时间、导致客户不满意。
2)适应性。算法必须能够适应动态变化的用户请求并在最短的时间内提供任务分配。
3)容错。算法必须确保容错能力，从而在系统总负荷出现问题的情况下维持平衡机制不间断工作。
4)吞吐量。算法必须确保以最小代价增加吞吐量，若负载平衡算法没有增加系统的吞吐量，则表明没有达到目的。
5)轮候时间。算法应尽量减少某项任务分配资源等待时间。
表1 负载平衡各个原则及功能
3本文的负载平衡算法
本文提出的自主代理是基于负载平衡算法解决最大化的资源优化配置、最大化的吞吐能力、最少的响应时间、动态资源调度。若满足任何时候虚拟机处于过载状态，则服务提供者不得不分配资源，服务提供者将对可用的资源合理优化，由所有虚拟机共同承担负载，从而保持平衡，否则服务提供者分配资源将不确定，因此，本文假设虚拟机都处于过载状态。
3.1非均匀窗口蚁群算法
蚁群算法[13]有3个最重要的准则，即转移概率准则、局部调整准则、全局信息素调整规则。
采用非均匀窗口蚁群是为了克服一般蚁群算法的搜索时间长、容易陷入局部最优的缺点[14-15]，主要策略是在算法初期给出一个可以接受的群体最小进化率Gmin，设置较小蚂蚁窗口值win，最大限度地缩小蚂蚁移动范围以减少搜索时间，群体的进化率定义为
(1)
(2)
(2)式中，k表示蚂蚁下一步所能到达的节点数。
从(2)式可以看出，蚁群窗口进行调整时，群体进化率越小，win越大，其搜索空间进行了拓展，有利于更快地找到最优解。同时无需根据优化的具体问题反复确定窗口的大小，提高了通用性。
3.2应用于负载平衡
众所周知，蚁群算法是一种生物启发算法，利用路径遗留的信息素、信息素浓度和扩散机制来吸引蚂蚁选择觅食路径，由于非均匀窗口蚁群算法能快速选择最短或最佳路径，因此，本文将其应用于解决负载问题。非均匀窗口蚁群算法最吸引人的地方，除了能最快选择最佳路径外，非常适用于负载平衡，即蚂蚁从出发到目的地执行任务无需再回到出发地，而是在抵达目的地后自己毁灭掉，从而在网络中减少不合适的路线。既然负载平衡在抄送中需要搜索底层的负载服务器和资源，蚁群算法完全能满足这种目的，且不会增加网络的额外负载。
负载平衡由3部分代理组成：负载代理、信道代理和迁移代理。负载和信道代理都是静态代理，迁移代理是动态代理[16]。
负载代理控制着信息原则以及维持数据中心的所有细节。其主要工作是在数据中心分配新任务后计算每个可利用的虚拟机上的负荷，所支持的表称为虚拟机负载适合度表。虚拟机负载适合度表主要用于维持记录数据中心所有虚拟机中特定部分的记录。它包含了虚拟机ID、内存消耗状态、CPU的效率、适合度值、所有虚拟机的负载状态。它的结构如表2所示。表2中，μ表示内存使用百分比，λ是CPU使用效率百分比，v是虚拟机适合度值。
表2 虚拟机负载适合度表
信道代理控制着传输原则、选择原则和定位原则，接收到来自负载代理的请求后，信道代理将会启动一些迁移代理到其他的数据中心，在相同配置的虚拟机上进行搜索。它也会按顺序持续保存来自响应表中这些代理的所有信息记录，其响应表如表3所示，其中，*A表示适用，即发现相似的配置，**NA表示不适用，即未发现相似的配置。
表3 响应表
迁移代理由信道代理发动，它将会移动到其他的数据中心，并会和那个数据中心负载代理进行信息交流来查询虚拟机当前的状态，找到理想的配置。接收到请求信息后，利用同样的方式与父级信道代理沟通。然而，它将会停留在目的地的位置，静候来自于父级信道代理的自毁信息。这个迁移代理的状态基于其适用性可能会存活，也有可能被摧毁。
负载平衡是利用虚拟机的负载状态，依据可使用内存、可利用的CPU使用率以及期待的响应时间，周期性地决定虚拟机的工作负载，计算出每台虚拟机的适合度，具体由(3)—(4)式给出。
(3)
(4)
适合度百分数将给出虚拟机的状态
(5)
无论何时的请求到达数据中心，在完成资源分配后，负载代理都会对反映当前所有虚拟机状态的虚拟机适合度表进行升级。这些因子影响传入请求的进程后，负载代理就会计算出μ和λ百分数。再基于μ可利用的值，就能得到每个节点的适合度v。只要每个节点的v值大于25%的阈值，在此情形下，虚拟机的状态就是正常的。当虚拟机的适合度小于或等于阈值时，则需执行负载平衡。
类似于蚁群算法，到达目的地数据中心后，迁移代理首先将告知信息发送给父级信道代理；然后，它将核实那个数据中心的负载代理是否存在所需相似配置的虚拟机可供使用。若没有可用虚拟机，迁移代理就会发送一条不适用的指令信息返回到父级信道代理，同时等待来自父级信道代理的自毁指令；若有一个或者多个可用虚拟机，迁移代理将会进一步核实他们的μ和ν，并将他们发送到信道代理。接收到来自各种迁移代理的响应后，信道代理将其记录在响应分析表中，具体如表4所示。
表4 虚拟机负载适合度表
数据中心接收新的请求后，负载代理就会映射可使用的虚拟机参数规格。若虚拟机的适合度值正常，负载代理继续进行未来的分配；否则，负载代理将会请求信道代理透视数据中心是否有相似配置的虚拟服务器进行负载平衡。此时，信道代理扫描响应分析表，并找出
图1 负载平衡算法框架图Fig.1 Frames of algorithm of load balancing
算法1迁移代理()。
Input：来自信道代理(VMinitialization)的VMconfigure；
Output：寻找来自另外的数据中心相似的VM
{接收来自信道代理(VMinitialization)的VMconfigure；
寻找 一个数据中心；
核实 VM负载表；
If(确定能找到)
Return(A)
Else
Return(NA)；
正在等待接收(自毁指令)；
结束进程 (MAi)；}
算法2负载代理()。
Input: 接收用户请求；
Output:利用A2LB分配资源；
CaseI：{
If(虚拟机负载表==空)
那么分配请求资源；维持虚拟机负载表；
μavailable=μtotal-μused
If(v>25)then
{ 分配状态:=正常；}
Else
{分配状态：=临界；
初始化 信道代理(VMinitialization)；}
CaseII：
If(虚拟机负载表≠空)
扫描虚拟机负载表；
If(负载状态(VMi)==临界)
{请求信道代理(VMload-balance)；
接收
请求传输到 DCid；}
Else
请求分配到 VMid；
升级 虚拟机负载表；}
算法3信道代理(VMinitialization)。
Input：接收来自于负载代理的VMi配置信息；
Output：响应分析列表，虚拟机ID；
接收来自负载代理的VMi；
初始化迁移代理；
接收来自于迁移代理的通知；
维持响应表；
If(响应==NA)
{ 发出指令自毁(MAi)；}
Else
{ 接收v(MAi)； 维持响应分析表；
周期性更新响应分析表；}
信道代理(VMload-balance)：
正传入请求：
{ 扫描响应分析表；
准备匹配的VMi列表；
L1：fori=1ton
Large=0；
If(v(VMi>Large))
Large=v(VMi)；
vold=vi；
更新MAi信息；
If(vold==vi)
Return(
Else转到L1；}
4实验与分析
实验在英特尔酷睿II双核处理器，2.45GHzCPU，4.0GByteRAM和微软WindowsVista平台上实现，编程工具为Java。根据CloudSim上的仿真结果分析了本文算法的性能，将CloudSim模拟器[17]的级别进行扩展，将本文提出的非均匀窗口蚁群负载均衡算法(loadbalancebasedonnon-uniformwindowantcolonybehavior，NWACB-LB)与文献[6]提出的基于博弈论的负载均衡算法(schedulingstrategyonloadbalancing，SSLB)、文献[7]提出的容错分簇的负载均衡感知算法(tolerantcluster-aware，TCLB)、文献[11]提出的基于蜜蜂行为的负载均衡算法(honeybeebehaviorinspiredloadbalancing，HBB-LB)进行比较。
4.1最大完成时间和响应时间比较
表5为本文算法负载前后完成时间对比，可以看出，随着任务数增加，最大完成时间明显增加，动态负载均衡后最大完成时间明显减少。
表5 负载均衡前后的最大完成时间
图2为分别采用HBB-LB，SSLB，TCLB和NWACB-LB算法在短时间内信道代理VM的响应时间图。实验结果表明，相比TCLB，SSLB和HBB-LB算法，本文算法的平均响应时间至少分别节省了37%，8%，4%，表明本文算法更加有效。
图2 短时间内VM对各个算法的响应时间Fig.2 Response time of VM for each algorithm in short time
图3为分别采用HBB-LB，SSLB，TCLB和NWACB-LB算法的最大完成时间图。从图3可以看出，相比HBB-LB，SSLB和TCLB算法，本文算法明显减少了最大完成时间，因为当适合度值低于一定阈值时，信道代理就会被激活，并开始搜寻有相同配置的虚拟机，完成时间明显缩短。
4.2不平衡的负载级别比较
使用大约500个任务进行实验，对所有4种算法中VM间负载的不平衡级别进行比较。其中，VM间负载的不平衡级别定义为
(10)
(10)式中：Tmax和Tmin分别表示所有VM中最大Ti和最小Ti，其中，Ti表示负载均衡后第i个任务完成时间；Tavg为VM中所有Ti的平均值。
图3 各个算法的最大完成时间Fig.3 Maximum completion time of four algorithms
NWACB-LB在负载均衡前后VM间的不平衡级别如图4所示。从图4可以看出，NWACB-LB负载均衡后，明显降低了不平衡级别。所有4种算法不平衡级别的对比结果如图5所示，NWACB-LB与其他3种算法相比，更加有效地降低了不平衡的级别，很大程度上归功于负载适合度表在移动代理响应中的作用。
图4 本文算法在负载均衡前后VM间不平衡级别Fig.4 Imbalanced levels between VM before and after load balancing in the proposed algorithm
对VM间迁移任务的平衡进行比较，迁移任务是指VM间被重新分配的任务数量，4种算法在3—5种VM间进行变化时，相应的迁移任务的走势如图6—图8所示。从图6—图8可以看出，在不考虑VM数量的情况下，本文算法中的迁移任务数量均小于其他3种算法，可见本文算法在容错和适应性方面更加有效。
图5 各个算法的不平衡等级与任务数量关系Fig.5 Relationship between imbalanced levels and the number of tasks in four algorithms
图6 3种VM情况下，各算法迁移任务数比较Fig.6 Comparison of numbers of migrations for four algorithms in the case of three VM
图7 4种VM情况下，各算法迁移任务数比较Fig.7 Comparison of numbers of migrations for four algorithms in the case of four VM
图8 5种VM情况下，各算法迁移任务数比较Fig.8 Comparison of numbers of migrations for four algorithms in the case of five VM
5结论
在非均匀窗口的蚁群算法基础上，本文提出了一种云计算环境下的负载平衡算法，为云环境提供了动态的负载平衡。该算法的主要贡献在于负载代理可以从其他目的地数据中心启动类似于蚁群算法的搜索虚拟机，具有比一般蚁群算法更快的搜索速度，实验结果表明了本文算法的整体性能有所提高。
参考文献：
[1]邓茹月, 覃川, 谢显中. 移动云计算的应用现状及存在问题分析[J]. 重庆邮电大学学报：自然科学版, 2012, 24(6): 716-723
DENG Ruyue, TAN Chuan, XIE Xianzhong.Application Status and Problem Analysis of Mobile Cloud Computing [J]. Journal of Chongqing University of Posts and Telecommunications ：Natural Science Edition, 2012, 24(6): 716-723.
[2]王鹏, 黄焱, 李坤,等. 云计算集群相空间负载均衡度优先调度算法研究[J]. 计算机研究与发展, 2014, 51(5):1095-1107.
WANG Peng, HUANG Yan, LI Kun, et al. Load Balancing Degree First Algorithm on Phase Space for Cloud Computing Cluster[J]. Journal of Computer Research and Development, 2014, 51(5): 1095-1107.
[3]蔡嵩. 云环境中基于朴素贝叶斯负载均衡技术的研究与实现[D]. 镇江：江苏大学, 2014.
CAI Song.Research and Implementation of the Load Balancing Technology Based on Native Bayes Algorithm in Cloud Computing Environment [D].Zhenjiang：Jiangsu University, 2014.
[4]DHORE S R, SINHA P K. Multi-agent Optimized Load Balancing Using Spanning Tree for Mobile Services[J]. International Journal of Computer Applications, 2010, (6):33-40.
[5]BHASKAR. R, DEEPU S R, SHYLAJA B S. Dynamic Allocation Method For Efficient Load Balancing In Virtual Machines For Cloud Computing Environment[J].Advanced Computing：An International Journal,2012,3(5):53-61.
[6]HU J, GU J, SUN G, et al. A scheduling strategy on load balancing of virtual machine resources in cloud computing environment[C]//IEEE.Parallel Architectures, Algorithms and Programming (PAAP), 2010 Third International Symposium on. New York：IEEE, 2010: 89-96.
[7]苏金树, 郭文忠, 余朝龙, 等. 负载均衡感知的无线传感器网络容错分簇算法[J]. 计算机学报, 2014, 37(2): 445-456.
SU Jinlong, GUO Wenzhong, YU Chaolong,et al. Fault-Tolerance Clustering Algorithm with Load-Balance Aware in Wireless Sensor Network [J]. Chinese Journal of Computers, 2014, 37(2): 445-456.
[8]AMAR M, ANURAG K, RAKESH K, et al. SLA Driven Load Balancing For Web Applications in Cloud Computing Environment[J].Information and Knowledge Management. 2011, 1(1): 10-17.
[9]施杨斌. 云计算环境下一种基于虚拟机动态迁移的负载均衡算法[D]. 上海：复旦大学, 2011.
SHI Yangbin. Load Balancing Algorithm Based on Virtual Machine Dynamic Migration in Cloud Computing Environment[D]. Shanghai：Fudan University, 2011.
[10] 李强, 郝沁汾, 肖利民,等. 云计算中虚拟机放置的自适应管理与多目标优化[J]. 计算机学报, 2011, 34(12): 2253-2264.
LI Qiang, HAO Mifen, XIAO Limin,et al. Adaptive Management and Multi-Objective Optimization for Virtual Machine Placement in Cloud Computing [J]. Chinese Journal of Computers, 2011, 34(12): 2253-2264.
[11] KRISHNA P V. Honey bee behavior inspired load balancing of tasks in cloud computing environments[J]. Applied Soft Computing, 2013, 13(5): 2292-2303.
[12] ALAM M G R, BISWAS C, NOWER N. A Semi-Distributed and Mobile Agent based architecture for load balancing of heterogeneous wireless networks[C]//IEEE. Computer and Information Technology (ICCIT), 2011 14th International Conference on. New York：IEEE, 2011, 4(1): 139-144.
[13] LI S H, HWANG J I G. Bidirectional Ant Colony Optimization Algorithm for Cloud Load Balancing[C]//IEEE. Proceedings of the 2nd International Conference on Intelligent Technologies and Engineering Systems (ICITES2013).Kaohsiung,Taiwan,China:Springer International Publishing, 2014: 907-913.
[14] 梁旭，黄明 .现代智能优化混合算法及其应用[M]. 北京:电子工业出版社，2011.
LIANG Xu, HUANG Ming. Modern Hybrid Intelligent Optimization Algorithm and Its Application[M].Beijing: Electronic Industry Press , 2011.
[15] 殷洪海. 云环境下基于改进蚁群算法的资源调度策略[D].成都：电子科技大学, 2014.
YIN Honghai. Resource Scheduling Policy Based on Improved Ant Colony Algorithm in A Cloud Environment [D].Chengdu：University of Electronic Science and Technology of China, 2014.
[16] 唐道红. 云环境下基于虚拟机动态迁移的资源调度策略研究[D]. 重庆：重庆邮电大学, 2012.
TANG Daohong. Research on Resources Scheduling Strategy Based on Dynamic Migration of Virtual Machine in Cloud Computing[D].Chongqing：Chongqing University of Posts and Telecommunications, 2012.
[17] ALAM M G R, BISWAS C, NOWER N. A Semi-Distributed and Mobile Agent based architecture for load balancing of heterogeneous wireless networks[C]//IEEE. Computer and Information Technology (ICCIT), 2011 14th International Conference on. New York：IEEE, 2011: 139-144.
DOI：10.3979/j.issn.1673-825X.2016.04.019
收稿日期：2015-06-19
修订日期：2016-04-07通讯作者：张少辉zhangsh_email@126.com
基金项目：河南省科技厅软科学研究计划项目(142400411213)；河南省高等学校重点科研项目(15A520118)
Foundation Items：The Soft Science Research Project from Science and Technology Department of Henan Province (142400411213); The High School Key Research Projects of Henan Province (15A520118)
中图分类号：TP391
文献标志码：A
文章编号：1673-825X(2016)04-0567-08
作者简介：
张少辉(1982-)，男，河南郑州人，讲师，硕士，研究领域为云计算、智能算法等。E-mail：zhangsh_email@126.com。
崔仲远(1982-)，男，河南濮阳人，讲师，硕士，研究领域为云计算、智能算法。
韩秋英(1981-)，女，河南沈丘人，讲师，硕士，研究领域为云计算、计算机应用等。
(编辑：王敏琦)
Load balancing algorithm based on non-uniform window ant colony behavior in cloud computing environment
ZHANG Shaohui, CUI Zhongyuan, HAN Qiuying
(College of Computer Science and Technology, Zhoukou Normal University, Zhoukou 466001, P.R.China)
Abstract:In view of request overloading and high response time in cloud computing environments, inspired by the idea of the non-uniform window ant colony behavior, a new load balancing algorithm is proposed. We introduce a working hypothesis that any virtual machine is under the condition of overloading, that is, the service provider has to allocate resources. According to the assumption, the available resources are optimized, where the dynamic and static agents are processed at the same time, and the ant colony behavior is used for load balance. System balance is achieved by means of loading resources into all virtual machines. The CloudSim simulation is used to emulator cloud environment for experiment analysis. Experimental results show that compared with load balancing of fault-tolerant cluster-aware(TCLB), scheduling strategy on load balancing(SSLB) and honey bee behavior inspired load balancing(HBB-LB)，the responsible time of the proposed algorithm is less than that of TCLB, SSLB and HBB-LB by 37%, 8% and 4% respectively. And the maximum completion time is also reduced significantly with overall improved performance.
Keywords：cloud computing; load balancing; agents; ant colony behavior; responsible time; maximum completion time
