基于局部择优随机爬坡算法的云计算负载策略研究

李霞，彭浩

（郑州轻工业学院计算机与通信工程学院，郑州　450001）

基于局部择优随机爬坡算法的云计算负载策略研究

李霞，彭浩

（郑州轻工业学院计算机与通信工程学院，郑州450001）

0　引言

随着互联网技术快速发展且和广泛应用，云计算作为一种新兴的计算体系正逐渐成为工业界和学术界的热门话题，云计算旨在提供一种能够满足普通社会团体日常需要的计算功能。在全世界范围内云计算的的基础设施被商业与个人用户用来获取应用服务，因此云计算代表动态提供计算服务的新范式。通常来说云计算服务是由大量网络虚拟机组成的顶级数据中心来提供支持，云计算是一个分布式的计算机制，这种机制利用高速网络将作业由个人PC端转移至远端计算机集群来进行数据处理。

虽然云计算的前景很乐观，但许多关键性问题仍需要解决来使云计算变为现实。负载均衡问题是其中之一，负载均衡为整个云分配任务量，在实现云计算的过程中他扮演一个非常重要的角色已经成为不可或缺的部分。云服务提供商的负载均衡机制是能够达到为消费者构建一个低成本且无限制的资源池并且具备组织计算资源的能力，这种能力表现在部署于数据中心的应用上以及响应用户分配应用请求上。

学界已经有很多有关负载均衡算法的文章。Min-Min［2］调度算法在最小执行时间（MET）内运用随机命令将任务分配在能够最快执行的节点上，算法的核心思想是为每一个非计划任务估算最小完成时间，然后这些任务将被分配到能够以最短时间完成的节点上。轮询调度算法（RR）［3］简单分配所有位于数据中心和处理单元的进程。文章为负载均衡提出的局部择优随机爬坡算法能够使可用资源最大限度最优化的使用。运用云分析软件CloudSim［4-5］对上述算法进行模拟和分析，从与轮训调度算法和先来先服务算法的对比研究结果中证明局部择优随机爬坡算法的优势。

1　云仿真软件CloudSim简介

1.1云计算仿真实验存在的问题

云计算要求将大规模的应用部署变得更简洁便宜，这就为研究者制造了很多新问题。测试新问题需要一些测试平台。并且云基础设施是分布式的，应用程序也部署在不同的地理位置。对系统规模、资源调度分配策略和性能等指标进行重复可伸缩的试验来对不同应用模式进行量化、评价是非常困难的［4］。为此，需要一个云计算环境的分布式系统模拟器来实现云计算试验的模拟，降低研究测试门槛和成本。

1.2CloudSim的优势及其基础架构

CloudSim提供云计算的特性，支持云计算资源的管理和调度模拟。云计算最大的特点是：采用成熟的虚拟化技术，将数据中心的资源虚拟化为资源池，打包对外象用户提供服务。CloudSim恰好体现此特点，扩展部分实现一系列接口，提供基于数据中心的虚拟化技术、虚拟化云的建模和仿真功能。此外CloudSim将仿真实验练习和编程实现分离，因此研究人员可以更多的关注仿真的复杂性而不需要在编程技巧上花费太多的时间。云仿真工具包的体系架构如图1所示。

图1　Simulation configuration

2　基于局部择优随机爬坡算法的负载均衡

负载均衡是依靠将总负载重新分到集成系统的各个节点上来提升资源利用率的过程，也是提高作业时间的过程。负载均衡开发策略的要点是对负载的预测、负载的对比比较以及不同系统的稳定性、系统性能、节点间的交互、作业属性的转换、节点的选择等方面的优化。这种负载被认为是CPU负荷、内存使用量、延迟和网络负载。

负载均衡算法可以是分布式的也可以是集中的。我们的算法采用集中方式：算法依靠系统中的核心节点来执行［6］。该节点独立负责整个系统的负载。其他节点与核心节点相互作用，相对于分布式的方案，由于系统中总体交互量的大幅度降低，集中式的负载均衡方案能够以更少的信息量来传达指令。然而存在两个缺点：第一，集中式算法在中心节点会引发系统瓶颈，第二，一旦中心节点崩溃，负载均衡进程就会出现不可用状态。第一个缺点的解决方案是将负载分布地更加有效即在可用服务器之间分配负载以获得最有效的吞吐量的优化问题。

解决优化问题较为完整的算法必须具备这样的特征：能够保证找到一个可用的赋值给变量或者能够证明没有这样的赋值存在；性能高效稳定并且能够为所有用户的输入提供一个准确的和最优的的答案。但是缺点在于，当工作环境比较恶劣的情况下这些算法的执行时间呈指数级的增长，在云计算领域这是不能够被接受的。其他的不完整的算法不能够保证为所有用户输入提供正确答案，但这些方法能够以较高概率针对可解问题找到满足条件的赋值。近年来这些算法应用很普及源于他们简洁、快速以及在解决特定问题时所表现出的客观效能。爬坡算法的变体局部择优随机爬坡算法是解决此类优化问题的一种不完全的算法。随机局部优化算法是一个值持续不断增加的向上的环［7］。当值达到顶峰时周围没有更高值出现时停止。在爬坡运动和选择概率的随机性上，多样化选择会随着爬坡运动的梯度变化而变化。因此局部择优随机爬坡算法通过对原始任务进行细微的改变来将任务分配到一组作业中去，这组作业中的每个元素根据既定的条件来进行评测并向有效进程靠近以提高此种状态下的评测值，该组作业中最优的元素被定为下一个要执行的任务，以上过程被重复执行直到找到解决方案或者达到停止条件［8］。因此局部择优随机爬坡算法包含两个组件，一个是备选生成器能够将备选解决方案匹配给一组可能的继任者，另一个是评测条件生成器能够将每个有效的解决方案划分等级，如此，这种评测机制能够找到更好的解决方案。

上述算法的描述过程如下：

（1）维护虚拟机的索引表和虚拟机的工作状态（忙碌/可用），开始时所有虚拟机都是可用状态。

（2）新任务进入云任务池［9］。

（3）为下一个分配生成查询。

（4）随机产生一个虚拟机ID。

（5）如果虚拟机已经被分配，就分析配置表来获取特定虚拟机的状态。

①返回虚拟机ID。

②发送请求给由ID标识的虚拟机。

③如果虚拟机已经被分配则根据分配情况来更新配置表。

④运用随机函数来生成一个随机虚拟机。

⑤依据概率因子为任务分配虚拟机，如此能够更有效的处理任务。

⑥如果已分配虚拟机的性能不如预期则记录下来，在下一次迭代中降低分配该虚拟机的概率。

⑦当虚拟机完成请求处理并且微云接收到处理结果时生成已撤销虚拟机分配的通知。

⑧从第二步开始重复执行为下一次分配准备。

3　仿真结果分析

云仿真软件用于算法测试，考虑到位于云端的应用将运行在电子竞拍和社交网站如Facebook、google+等大型网站上，设计相应的仿真配置。

3.1仿真配置

选定来自世界六个主要大陆用户群表1，为了简便起见每个用户群都在一个时区内并且假设该用户群中已注册的用户有超过5%的在高峰时间段同时在线，只有10%的用户在非高峰时间段内在线，此外每个用户每5分钟发送一次请求，每个仿真数据中心都寄宿于特定数量的虚拟机上，这些虚拟机为应用程序服务。虚拟机的配置：4GB RAM、100GB Storage、4CPUs。实验用户群的规格描述如表1。

表1

3.2仿真场景

为了达到仿真目标，应该考虑多个仿真场景，从单一集中式云开始，数据中心是社交网络的载体，因此全球范围内的用户的请求都被这唯一一个数据中心处理。数据中心有25、50和70台虚拟机分布于各种云配置的应用上。这种仿真场景如表2（a）所示。

在第二种场景中，我们考虑两个数据中心，期初每个数据中心在三种云配置下分别为应用部署25、50、75台虚拟机。然后每个数据中心在三种云配置下分别为应用部署25和50台虚拟机；25台和75虚拟机；50和75台虚拟机如表表2（b）所示。在考虑三个数据中心的情况下，期初每个数据中心在三种云配置下分别部署25、50、75台虚拟机。此外分别为每个数据中心混合部署25、50和75台虚拟机。如表3（a）。

表2

第四种情况与第三种情况相似，只是在六个数据中心的情况下进行。如表3（b），表4（a）和表4（b）中显示。

表3

表4

3.3结果

在前面所描述的方案和配置下，随机爬坡算法、轮训调度算法、先进先服务算法的总体平均响应时间的结果在表2（a），2（b），3（a），3（b），4（a），4（b）中显示。表2（a），2（b），3（a），3（b），4（a），4（b）以图形综述的形式描绘了随机爬坡算法与轮训调度算法的性能对比。在大部分的实例中随机爬坡算法的性能表现都优异于另外两种算法。

4　结语

本文研究了将爬坡算法的改进算法局部择优随机爬坡算法应用于云计算负载均衡策略中，在四种不同虚拟机部署场景中将此改进算法与传统调度算法轮询调度（RR）与先到先服务算法（FCFS）横向对比实验得出三种算法下虚拟机响应时间数据如图2，通过数据可以证明局部择优随机爬坡算法在一个数据中心的情况下响应时间优势不明显，但随着数据中心的增加响应时间相较另外两种算法优势显著，响应时间大幅度降低，效能提升可观。

图2

［1］杨靖琦.云化业务平台可伸缩性研究［D］.北京.北京邮电大学，2014.

［2］张澜.网格环境下Min-Min调度算法改进与实现［D］.郑州.信息工程学院，2008.

［3］Karapici，Alban，Feka.The simulation of round robin and priority scheduling algorithm［C］.In Proceeding of the 12th International Conference on Information Technology-New Generations（ITNG），2015.

［4］王霞俊.基于CLOUDSIM平台的云任务分配策略研究［J］.上海：微型电脑应用，2013：59-60.

［5］查英华，杨静丽.云计算仿真平台CloudSim在资源分配研究中的应用［J］.武汉：软件导刊，2012：58-59.

［6］杨际祥，谭国真.一种大规模分布式计算负载均衡策略［J］.北京：电子学报，2012：2226-2227.

［7］单冬冬，吕强.贝叶斯网学习中一种有效的爬山算法［J］.沈阳：小微型计算机系统，2009：2458-2459.

［8］Shams，B.，Khansari，M.Immunization of complex networks using stochastic hill-climbing algorithm［C］.In Proceeding of the 3th Computer and Knowledge Engineering（ICCKE），2013.

［9］陈波.云计算环境下负载均衡技术的研究［D］.无锡：江南大学，2014.

Cloud Computing;Loding Balance;Soft Computing;Stochastic Hill Climbing;CloudAnalyst

Load Balancing in Cloud Computing Using Stochastic Hill Climbing-A Approach
LI Xia，PENG Hao

（College of Computer and Communication Engineering，Zhengzhou University of Light Industry，Zhengzhou 450001）

1007-1423（2015）28-0003-06

10.3969/j.issn.1007-1423.2015.28.001

李霞（1962-），女，教授，研究方向为云计算、分布式网格计算

2015-09-19

2015-09-29

以云计算的方式来执行任务的过程中负载节点的选择是非常关键的环节，从挖掘资源有效性的角度出发，负载节点必须根据任务属性来合理选择，提出一种负载均衡算法——局部择优的随机爬坡算法，该算法用来为虚拟机或服务器分配即将运行的调度作业，用云分析软件对算法的性能进行定量和定性的分析。将局部择优随机爬坡算法与轮训调度算法和先进先服务算法进行对比分析来反映局部择优随机爬坡算法在选择负载节点优化配置计算资源的优越性。

云计算；负载均衡；软计算；随机爬坡算法；云分析

河南省科技攻关项目“智慧校园建设”（豫财政【2014】124号）

彭浩（1988-），男，河南信阳人，硕士研究生，研究方向为云计算

Utilizes the computing resources on the network to facilitate the execution of complicated tasks that requires large-scale computation.Se-lects nodes（load balancing）is crucial for executing a task in the cloud computing，and to exploit the effectiveness of the resources，they have to be properly selected according to the properties of the task.Proposes a soft computing based load balancing approach，uses a lo-cal optimization approach Stochastic Hill climbing for allocation of incoming jobs to the servers or virtual machines（VMs）.Analyzes per-formance of the algorithm both qualitatively and quantitatively using CloudAnalyst.Makes a comparison with Round Robin and First Come First Serve（FCFS）algorithms.The comparison reflect the advantage of local optimization approach Stochastic Hill climbing in se-lecting load balance node.