云计算资源分配中蚁群算法研究

蚁群算法在云计算资源分配中的应用研究张春艳（中国矿业大学计算机科学与技术学院, 徐州221116）摘要：针对目前已提出的云计算资源调度模型，提出一种基于蚁群算法的资源分配策略。分配云计算资源时，首先在云计算网络中发现社团，探测可用节点的计算能力，然后根据云计 算服务模式特点，通过分析诸如网络带宽占用、线路质量、响应时间、任务费用、可靠性等 因素对资源分配的影响，利用蚁群算法得到一组最优的计算资源。通过在 CloudSim 环境下 的仿真进行分析和比较，这种算法能在满足云计算服务模式的情况下，获得比其他一些针对 网络的的分配算法更短的响应时间和更强的工作质量，从而更加适合在云环境中使用。 关键词： 云计算；蚁群算法；服务模式；调度中图分类号：TPApplied research of ant colony algorithm in computing clouds resources allocationZHANG Chunyan(Computer science and technology School, Cumt,Xuzhou221116)Abstract: In view of the present scheduling model of cloudscomputing resources, a resource allocation strategy based on ant colony algorithm is proposed. Distributing cloud calculative resources,first find societies in computing clouds network, detect usable node computing power, and then based on the cloud calculative service mode, through the analysis of the characteristic such as networkbandwidth, line quality, response time, task expenses, other factors on the reliability of resource allocation influence, using the ant colony algorithm to get a set of optimal computing resources.Through analysis and comparison in the simulation under CloudSim environment, this algorithm can satisfy the cloud calculative service mode of the circumstances, get shorter response time and strongerwork quality than some other in network of distribution algorithm, and thereby more suitable for use in the cloud environment.Key words: Cloud computing; ant algorithm; service mode; schedule0引言由于信息化技术的迅速发展，网络上数据逐渐复杂庞大，传统的并行技术等已不能为满 足人类日益增长的办公和科研发展的需要。一些网络模式应运而生，云计算作为一种新型的 并行计算技术也出现在网络上。云计算作为一种基于互联网的新计算模式，是分布式计算(Distributed Computing)、并行 计算(Parallel Computing)和网格计算(Grid Computing)的进一步发展， 也是这些计算机科学 概念的商业实现。它将计算任务分布在大量计算机构成的资源池上，使各种应用系统能够根 据需要获取计算力、存储空间和各种软件服务。云计算的资源是动态易扩展而且虚拟化的， 通过互联网提供云计算是基于互联网的超级计算模式，通过架构一个分布的、可全球访问的 资源结构，使数据中心在类似互联网的环境下运行计算，即把存储于个人电脑、移动电话和 其他设备上的大量信息和处理器资源集中在一起，协同工作。主要包括三种层次的服务：基础设施即服务（IaaS）、平台即服务（PaaS）和软件即服务（SaaS）1。作者简介：张春艳（1985-），女，工科硕士，主要研究方向：云计算和蚁群算法. E-mail: 6 / 6文档可自由编辑打印近年来，虚拟化作为云计算的基石，也一直是一个炙手可热的研究领域。虚拟化的浪潮席卷服务器、存储、网络、PC 机等各个领域。虚拟化最突出的优势就是节省资金、整合服 务器、最大化资源利用率。本文提出的蚁群算法分配策略，综合考虑了云计算分布的一系列特点，以期实现在这种 环境中能够满足用户作业分配合适资源的需求。1云计算服务模式在云计算服务模式中，用户交互接口以 Web Service 方式为各种用户提供访问接口，以 获取用户需求；配置工具用以在分配的节点上准备任务运行环境；系统管理模块负责管理和 分配所有可用的资源，其核心是保证负载均衡；服务目录是用户可以访问的服务清单；监视 统计模块负责监视节点的运行状态，并完成用户使用节点情况的统计。用户交互接口允许用 户从目录中选择并调用一个服务，将请求传递给系统管理模块后，它将为用户分配合适的资 源, 然后调用配置工具为用户准备运行环境。在云服务器端, 所有的计算及存储资源分布在 不同的节点上，系统管理员主要是使用一些配置工具和系统管理软件，一方面可以方便快捷 地为用户提供计算和存储资源，另一方面可以对这些计算存储资源进行高效管理，提高资源 利用率。对于云计算服务提供商来说, 其核心技术是如何对用户申请的计算资源进行分配和管 理，其效率直接影响整个云计算环境的工作性能。由于云计算中资源具有自治性、虚拟化等 独特的特点，使得原有的针对单纯分布式、网格计算资源分配和调度算法已无法在该环境中 有效工作。在云计算中，资源分配的效率非常重要，对云计算平台的系统综合性能影响很大。2算法描述基于上述云环境的特点及服务模式，我们提出以下资源分配算法。2.1资源分配流程参考 Map/Reduce 计算系统2，云环境中的每个单元可以分为两大角色：Master 和 Slave， 前者主要配置 NameNode 和 JobTracker 节点，后者配置 DataNode 和 TaskTracker 节点。在 资源分配时由该单元的主作业调度节点（master JobTracker）和该单位所辖各个节点集群中 的从任务分配节点（slave TaskTracker）共同完成。因此我们可以将云环境的所有单元中的 节点分为两大社团结构3，所有的主节点 master JobTracker 和从节点 slave TaskTracker 分别 作为一类社团结构。主节点负责调度构成一个作业的所有任务，这些任务的数据资源分布在 不同的用户镜像分片中，而用户镜像分片处在从节点存储资源上，主节点监控任务执行，重 新执行失败的任务或做错误处理。从节点负责执行由主节点分派的任务。从节点在接到主节 点的分派后，从节点开始寻找合适的计算节点为其下属的存储节点准备。首先，该从节点开 始检测自己的计算资源用量，如果其剩下的计算资源能够满足用户提交作业使用量，则分配 自身的计算资源，如果剩余的资源不足以满足需要给用户的最小计算资源量，则开始搜索云 计算环境中其他合适的计算资源。下面介绍的蚁群分配算法将在这一环节中实现。搜索工作 在一定范围内进行，目的是为了防止增加所带来的网络开销。若仍旧找不到合适资源，则从 节点向主作业调度节点提出请求移走该节点集群中的用户数据镜像分片。2.2模型及其考虑参数将 slave 节点域作为一个无向图 G（V, E），其中 V 是区域 Area 中所有 slave 节点的集合，E 是连接各 slave 节点的网络集合。在云计算网络中均匀地划分成若干个子区域，然后给每个区域分配相同个数的蚂蚁，每个组的蚂蚁只在各自的区域进行搜索。其度量标准要考 虑的有如下参数：预计执行时间：time_cost(e)，指路径 e 尽头的的计算资源处理这样作业要消耗的时间。 网络延迟，delay(e)，指路径 e 产生的最大网络延迟。网络带宽：bandwidth(e)，指路径 e 所提供的网络最大带宽。 用户对云计算资源需求的多样性与偏好性，如何作 Qos 保证。 将预计执行时间和网络延时综合后用变量 td in (t, e) 表示在 t 时间段内该 e 尽头为 i 计算资源的所用量。假设某虚拟机资源VM i 的特征集合：Ri = ri1 , ri 2 , ri 3 , ri 4 , rim , m 1,5其中，rim 表示一个 K 维对角矩阵，分别表示 CPU、内存的个数，带宽、费用及故障率的倒数。资源VM i 的性能描述矩阵向量是：VM i = Ei1 , Ei 2 , Ei 3 , Ei 4 , Eim , m 1,5其中 Eim 表示 rim 对应的特征值。任务的 QoS 描述通常可以采用任务完成时间、网络带宽、费用、可靠性等参数指标来 量化 QoS，如任务完成时间的 QoS 描述包括开始时间、全部完成时间、结束时间等，使用 时可选取任务全部完成时间作为评判指标。通常第 i 类任务的一般期待向量可以描述为：Ei = ei1 , ei 2 , ei 3 , ei 4 , eim , m 1,5m其中 eim 分别表示 CPU、内存、带宽等的一般期待，且满足：2.3蚁群算法寻找最优计算资源描述 eij = 1j =1由于在云计算环境中，资源的具体情况不可知，且网络没有一个固定的拓扑结构，所以 整个云环境的结构和资源分布及其实际情况不可预知在这种情况下，计算资源的位置和质 量对数据节点来说是不可知的 利用蚁群算法，能够在未知的网络拓扑中查找出计算资源，并选择最合适的一个或者几 个分配给用户作业，直到满足用户需求当查找开始时，由 slave 节点发出查询消息，这些消 息扮演着蚁群算法中蚂蚁的角色，所有的蚂蚁都遵从信息素多的节点概率大，信息素少的节点概率少的原则选择下一跳的节点，并在经过的路径节点上留下信息素设资源选择的约束函数为 (t )ninj =(E (t) , q q0（1）td in (t) 由公式(2)计算, q q0jij(t ) (E (t )td ij (t )P=kij(t ) (E (t ) , j avid (k )（2） in n navod (k ) td in (t)0, otherwise time _ cos t (t ) EL.bandwidth（3）其中，delay(e) DL ij (t ) 为 t 时刻，前向蚂蚁在 i 节点上观察到 j 节点的信息索强度，P 为 k 号蚂Cdelay(eij )蚁在 i 点选择 j 点的概率, avid (k ) 为蚂蚁是的回避列表， td ij =为从节点Bbandwidth(eij )0i 到节点 j 的线路质量， , 和 为信息素、线路质量和计算能力预测值的相对权重为防 止结果过快地收敛在局部最优解上，设定随机系数 q 0,1 ，常数 q 0,1 ， q0 为 QoS 标准，选择资源和路径的过程就是在不满足 QoS 的情况下寻找满足限定条件（3）的尽量大的 j 值或者在满足 QoS 的情况下寻找满足条件（3）的 P 值。这两个值和公式(1)用来控制蚂蚁直接选择信息素一线路质量比最大相邻节点的概率3算法调度工作流程首先，对用户的任务按优先级进行排序，然后进行分类，分类体现了用户任务对不 同 QoS 的要求和偏好，并依据 QoS 分类利用蚁群算法实施资源分配与调度，并将任务与资 源绑定，运行任务。 其流程如下图所示：图 1 算法调度工作流程Fig. 1 Algorithm scheduling workflow4实验仿真用云计算仿真模拟工具 CloudSim 来模拟一个云计算的局部域4，以检查本算法在这种 特殊的网格环境中的运行情况。该软件支持模拟新兴的云计算基础设施和管理服务：1)支持建模和安装大规模云计算基础设施，包括在单一物理计算节点和 java 虚拟机上 的数据中心。2)可对数据中心，服务代理，调度和分配策略进行建模。3)提供虚拟引擎，有助于在一个数据中心节点上创建和管理多个，独立和协同的虚拟服 务。4)可以灵活地在共享空间和共享时间分配的处理核心之间切换。 在体系结构上，CloudSim 仿真器采用分层的结构，自底向上由 SimJava，GridSim，CloudSim，用户代码四个层次组成。 下图分别为使用该算法和最优算法任务完成时间、计算能力偏好类任务及带宽偏好类任务比较图。完成时间/s60004000200006000 10000 12000 作业任务数/个最优时间算法 本文算法图 2 任务完成时间比较图Fig.2 Task completion time comparison chart6CPU个数/颗543210ID0ID1ID2ID3 子任务标识号/个最优时间算法 本文算法图 3 计算能力偏好类任务比较图Fig.3 Computing power preference class task comparison chart4000带宽/Mb/s3000200010000ID4 ID5 ID6ID7 子任务标识号/个最优时间算法 本文算法图 4 带宽偏好类任务比较图Fig.4 Bandwidth preference class task comparison chart5结论本文提出将基于 QoS 任务分类和蚁群算法用于解决云计算平台下的资源分配与调度问 题，扩展了 CloudSim 源代码并进行重新编译和生成，并在此扩展的仿真平台上对算法进行 了仿真分析。通过将仿真实验结果与最优完成时间算法的仿真结果对比，表明本文提出的算 法可以有效的执行用户的任务，并表现出更好的公平性和用户满意度。参考文献 (References)1 蒋海鸥，王希斌. 云计算中存储资源管理策略的探究J. 程序员，2010，5（75）2 林清滢. 基于 Hadoop 的云计算模型J. 现代计算机，2010，7（114）3 宋智玲. 蚁群算法优化结点和聚类技术在复杂网络中发现社团的研究J. 实验室研究与探索，2010，29（7）4 GRIDS Laboratory . A Novel Framework for Modeling and Simulation of Cloud Computing Infrastructures and Services OL. 2010.3 5 李秋云，朱庆保，马卫. 用于连续域寻优的分组蚁群算法J. 计算机工程与应用，2010，46（30）：4649.6 胡毅，龚斌，王风宇. 网格资源调度中基于云模型的蚁群算法J. 华中科技大学学报，2010，38（I）：6467.