基于云计算环境的蚁群优化计算资源分配算法

　第１期２０１０年１月华东师范大学学报（自然科学版）ＪｏｕｒｎａｌｏｆＥａｓｔＣｈｉｎａＮｏｒｍａｌＵｎｉｖｅｒｓｉｔｙ（ＮａｔｕｒａｌＳｃｉｅｎｃｅ）Ｎｏ．１　Ｊａｎ．２０１０文章编号：１０００５６４１（２０１０）０１０１２７０８基于云计算环境的蚁群优化计算资源分配算法华夏渝，　郑　骏，　胡文心（华东师范大学计算中心，上海　２００２４１）摘要：提出一种基于蚁群优化（ＡｎｔＣｏｌｏｎｙＯｐｔｉｍｉｚａｔｉｏｎ）的计算资源分配算法．分配计算资源时，首先预测潜在可用节点的计算质量，然后根据云计算环境的特点，通过分析诸如带宽占用、线路质量和响应时间等因素对分配的影响，利用蚁群优化算法得到一组最优的计算资源．通过在Ｇｒｉｄｓｉｍ环境下的仿真分析和比较，这种算法能够在满足云计算环境要求的前提下，获得比其他一些针对网格的分配算法更短的响应时间和更好的运行质量，因而更加适合于云环境．关键词：云计算；　网格；　蚁群；　资源分配中图分类号：ＴＰ３１６　　文献标识码：Ａ　收稿日期：２００９０６　第一作者：华夏渝，男，硕士，主要研究方向为ｗｅｂ应用．　通讯作者：郑骏，男，高级工程师，主要研究方向为ｗｅｂ应用．Ｅｍａｉｌ：[e-mail]．犃狀狋犮狅犾狅狀狔狅狆狋犻犿犻狕犪狋犻狅狀犪犾犵狅狉犻狋犺犿犳狅狉犮狅犿狆狌狋犻狀犵狉犲狊狅狌狉犮犲犪犾犾狅犮犪狋犻狅狀犫犪狊犲犱狅狀犮犾狅狌犱犮狅犿狆狌狋犻狀犵犲狀狏犻狉狅狀犿犲狀狋ＨＵＡＸｉａｙｕ，　ＺＨＥＮＧＪｕｎ，　ＨＵＷｅｎｘｉｎ（犆狅犿狆狌狋犲狉犆犲狀狋犲狉，犈犪狊狋犆犺犻狀犪犖狅狉犿犪犾犝狀犻狏犲狉狊犻狋狔，犛犺犪狀犵犺犪犻　２００２４１，犆犺犻狀犪）犃犫狊狋狉犪犮狋：　ＡｎｅｗａｌｌｏｃａｔｉｏｎａｌｇｏｒｉｔｈｍｂａｓｅｄｏｎＡｎｔＣｏｌｏｎｙＯｐｔｉｍｉｚａｔｉｏｎ（ＡＣＯ）ｗａｓｅｓｔａｂｌｉｓｈｅｄｔｏｓａｔｉｓｆｙｔｈｅｐｒｏｐｅｒｔｙｏｆｃｌｏｕｄｃｏｍｐｕｔｉｎｇ．Ｗｈｅｎｓｔａｒｔ，ｔｈｉｓａｌｇｏｒｉｔｈｍｆｉｒｓｔｐｒｏｇｎｏｓｔｉｃａｔｅｄｔｈｅｃａｐａｂｉｌｉｔｙｏｆｔｈｅｐｏｔｅｎｔｉａｌａｖａｉｌａｂｌｅｒｅｓｏｕｒｃｅｎｏｄｅｓ，ｔｈｅｎａｎａｌｙｚｅｄｓｏｍｅｆａｃｔｏｒｓｓｕｃｈａｓｎｅｔｗｏｒｋｑｕａｌｉｔｉｅｓｏｒｒｅｓｐｏｎｓｅｔｉｍｅｓｔｏａｃｑｕｉｒｅａｓｅｔｏｆｏｐｔｉｍａｌｃｏｍｐｕｔｅｒｅｓｏｕｒｃｅｓ．Ｔｈｉｓａｌｇｏｒｉｔｈｍｍｅｔｔｈｅｎｅｅｄｓｏｆｃｌｏｕｄｃｏｍｐｕｔｉｎｇｍｏｒｅｔｈａｎｏｔｈｅｒｓｆｏｒｇｒｉｄｅｎｖｉｒｏｎｍｅｎｔｗｉｔｈｓｈｏｒｔｅｒｒｅｓｐｏｎｓｅｔｉｍｅａｎｄｂｅｔｔｅｒｐｅｒｆｏｒｍａｎｃｅ，ｗｈｉｃｈｗｅｒｅｐｒｏｖｅｄｂｙｔｈｅｓｉｍｕｌａｔｉｏｎｒｅｓｕｌｔｓｉｎｔｈｅＧｒｉｄｓｉｍｅｎｖｉｒｏｎｍｅｎｔ．犓犲狔狑狅狉犱狊：　ｃｌｏｕｄｃｏｍｐｕｔｉｎｇ；　ｇｒｉｄ；　ａｎｔｃｏｌｏｎｙｏｐｔｉｍｉｚａｔｉｏｎ；　ｒｅｓｏｕｒｃｅａｌｌｏｃａｔｉｏｎ０　引　　言云计算（ｃｌｏｕｄｃｏｍｐｕｔｉｎｇ）是指通过互联网连接的超级计算模式，包含了分布式处理（ｄｉｓｔｒｉｂｕｔｅｄｃｏｍｐｕｔｉｎｇ）、并行处理（ｐａｒａｌｌｅｌｃｏｍｐｕｔｉｎｇ）和网格计算（ｇｒｉｄｃｏｍｐｕｔｉｎｇ）的相关技术，或者说是这些计算机科学概念的商业实现．云计算是一种新型的共享基础架构，可以将巨大的系统池连接在一起，以运营商和客户的华东师范大学学报（自然科学版）２０１０年方式，通过互联网为用户提供各种存储和计算资源．在云计算环境中，用户将自己的个人电脑，ＰＤＡ或移动电话等终端设备上的大量信息和处理器资源集中在一起，协同工作．这是一个大规模的分布式计算模式，该模式由运营商的经济规模决定，并且是抽象的，虚拟化的以及规模动态可变的．云计算的主要内容为受管理的计算能力、存储、平台和服务．这些内容通过互联网，按需分配给外部用户，其重要意义在于将计算能力作为一种商品在互联网上进行流通．云计算的主要优势：迅速地降低硬件成本和提升计算能力以及存储容量，用户可以以极低的成本投入获得极高的计算品质，而不用再投资购买昂贵的硬件设备，进行频繁的保养与升级．计算资源分配是云计算技术的一个重要组成部分，其效率直接影响整个云计算环境的工作性能．由于云计算有很多独特的性质，使得原有的针对网格计算的资源分配和调度算法已无法在该环境中有效工作．本文提出的蚁群优化分配算法，综合考虑了云计算的一系列特点，以期在这种环境中能够高效地为用户作业分配合适的计算资源．１　问题描述云计算由网格计算演变而来，并将网格计算作为其骨干和基本结构．可以说，云计算是网格计算的一种更高级的形式．但是，这两者之间在现实中存在着巨大的区别，具体可以参见文献［１］．云计算提供了更多抽象的资源和服务．这些资源和服务可划分为三个层次，分别是软件即服务（ＳｏｆｔｗａｒｅａｓａＳｅｒｖｉｃｅ），平台即服务（ＰｌａｔｆｏｒｍａｓａＳｅｒｖｉｃｅ）和设施即服务（ＩｎｆｒａｓｔｒｕｃｔｕｒｅａｓａＳｅｒｖｉｃｅ）［２，３］．在软件即服务（ＳａａＳ）中，用户会得到一个特殊用途的客户端，该客户端允许用户通过互联网进行远程访问，并且基于使用情况来收取费用．在平台即服务（ＰａａＳ）中，运营商提供一个高等级的综合环境来生成、测试以及部署用户定义的应用．这种综合环境是一种对抽象开发环境和对有效服务负载的封装．在设施即服务（ＩａａＳ）中，运营商参照和用户达成的服务品质协议（ＳｅｒｖｉｃｅＬｅｖｅｌＡｇｒｅｅｍｅｎｔ），通过提供硬件、软件和设备（主要是在统一资源层，不过同样也能在组织层）来提供一个完整的软件应用环境，并以资源使用量及时间来收费．该级别的服务，根据云计算环境弹性的特点，提供设备的规模会根据用户对资源的需求量来动态地增大或者缩小．比如用户需要用Ｔ个进程，云计算环境就分配给该用户Ｒ的计算资源；如果用户将进程数增加到２Ｔ，则用户的计算资源占有量将动态地扩展到２Ｒ．本文论述的计算资源分配策略，也充分考虑了云计算的这一特性．在设施即服务这一级别中，用户的所有数据和配置被封装成为用户镜像［２］，分散存储在云环境的各个存储节点上．由于可运营性的约束，云计算环境的网络可用带宽远比网格环境小得多．比如，一个传统的企业级计算设施一般都拥有１０ＧＢ的超高速以太网，高性能计算资源将通过该网络直接和存储区域网络（ＳｔｏｒａｇｅＡｒｅａＮｅｔｗｏｒｋ）相连．而在云计算环境中，比如Ａｍａｚｏｎ公司的ＥＣ２（ＥｌａｓｔｉｃＣｏｍｐｕｔｅＣｌｏｕｄ）［４］系统只提供了２５０ＭＢ的可用带宽，并且所有的虚拟服务器都通过单一的一条２５０ＭＢ连接来访问其存储系统Ｓ３（ＳｉｍｐｌｅＳｔｏｒａｇｅＳｅｒｖｉｃｅ）［５］．所以，在云计算环境中，带宽需要被充分地利用，一个行之有效的方法便是尽量为存储节点的数据资源分配本地的计算资源．对于本文论述的算法来说，就是尽量为存有用户镜像的存储节点分配本地或邻近带宽需求少的计算节点．云计算环境的运营目标之一是将计算能力作为服务来供用户购买．企业与个人用户无８２１第１期华夏渝，等：基于云计算环境的蚁群优化计算资源分配算法需再投入昂贵的硬件购置成本，只需要通过互联网来购买或租赁计算力，把自己的计算机当作接入口，一切都通过互联网连接到云计算环境中，完成对计算能力的获取．但是，这也预示着云计算的规模会非常巨大．同时，区别于网格的独占式的资源分配模式，整个云域中的资源将会被所有的用户同时共享，以保证对延迟敏感的作业在云上也能够很好地运行．这意味着在云计算中用户的作业将被划分为进程甚至是线程的粒度级别．所以，云计算对计算资源分配算法有着苛刻的要求．本文重点论述的计算资源分配算法，就是要通过对存储节点分配最合适的计算资源，来最大程度的提高云计算环境的效率．２　算法描述基于上述云计算环境的特点，我们提出以下资源分配算法．２．１　计算资源的分配流程参照Ｍａｐ／Ｒｅｄｕｃｅ提出的云计算框架［６，７］，云环境中的每个单元由一个单独的主作业调度节点（ｍａｓｔｅｒＪｏｂＴｒａｃｋｅｒ）和该单元所辖各个节点集群中的一个从任务分配节点（ｓｌａｖｅＴａｓｋＴｒａｃｋｅｒ）共同组成．主节点负责调度构成一个作业的所有任务，这些任务的数据资源分布在不同从节点的存储资源上的用户镜像分片中，主节点监控它们的执行，重新执行已经失败的任务，或者是做错误处理．从节点仅负责执行由主节点指派的任务．在接到主节点的指派之后，从节点开始为其下属的存储节点寻找合适的计算节点．首先，该从节点开始检测自身的计算资源余量，如果其剩余计算资源足以满足用户提交作业的用量，则优先分配自身的计算资源，如果资源已经耗尽或者已不足以满足承诺给用户的最小计算资源量，则开始搜寻云环境中其他合适的计算资源．本文介绍的蚁群分配算法将在这一环节中实现．搜索在一定范围内进行，目的是为了减小所带来的网络开销．如果仍然没有合适资源，则从节点报请主作业调度节点移走该节点集群中的用户数据镜像分片．２．２　计算资源优劣度评判条件将ｓｌａｖｅ节点域看作是一个无向图Ｇ（Ｖ，Ｅ），其中Ｖ是区域Ａｒｅａ中所有ｓｌａｖｅ节点的集合，Ｅ是连接各ｓｌａｖｅ节点的网络集合．寻找合适的计算节点，也就是在Ｅ中寻找一条最优的路径犲∈Ａｒｅａ，其度量标准可以考虑如下几个因素．①预计执行时间：ｔｉｍｅ＿ｃｏｓｔ（犲），指路径犲尽头的计算资源处理该作业预计的耗费时间．②网络带宽：ｂａｎｄｗｉｄｔｈ（犲），指路径犲所提供的网络最大带宽．③网络延迟：ｄｅｌａｙ（犲），指路径犲产生的最大网络延迟．设资源选择的约束函数为ｒｅｓ（犲）＝Ａｔｉｍｅ＿ｃｏｓｔ（犲）＋Ｃｄｅｌａｙ（犲）Ｂｂａｎｄｗｉｄｔｈ（犲），（１）ｓ．ｔ．　ｔｉｍｅ＿ｃｏｓｔ（犲）＜ＴＬｂａｎｄｗｉｄｔｈ（犲）＞ＥＬｄｅｌａｙ（犲）＜烅烄烆烍烌烎ＤＬ．（２）　　选择资源和路径的过程就是寻找满足限制条件（２）的尽量小的ｒｅｓ（犲）的路径和资源的过程，其中Ａ，Ｂ，Ｃ为三个约束条件的权重；ＴＬ，ＥＬ和ＤＬ为其边界限制条件．不同的云计算环境可能会有不同的取值．９２１华东师范大学学报（自然科学版）２０１０年２．３　对各个计算资源完成本次作业执行速度的预测由于在整个云环境中，异构是其非常重要的一个特点．也就是说，每个节点的结构、软硬件环境、容量和吞吐量等性能都会不同．同时，网络的情况也比较复杂，任意线路在任意时候的负载将不可预知．由于云计算环境中的网络带宽远比传统的网格环境带宽低，网络的情况也会有不可预期的大幅度变化．因此，对节点完成工作的执行速度的计算将会非常困难．但是，在云计算中，把任务分配给效率最高，开销最少的计算资源将会极大地提高整体的性能．所以，在分配中需要对潜在的可分配节点进行执行速度预估．针对云计算异构和变化的特点，我们通过文献［８］中的预测算法，设计了一个通过积累历史值来推算下一任务执行速度的预测模型．该模型对每一个节点完成下一个工作的效率时间进行单独的预测，希望无论计算资源处在怎样的负载程度，都能凭借这个模型得到相对精确的预测．由于每个计算节点当前的负载程度已知，并且上一次完成作业时的平均负载程度也能够查阅，所以，我们用如下模型来预测执行速度：犈犞犪犽＋１犿（犽＋１）＝犪犽＋１犪犽（１ρ）犈犞犪犽犿（犽）＋ρ犚犞犪犽犿（犽（））．（３）其中犈犞犪犽犿（犽）是指第犿号计算资源第犽次预测执行速度，单位可以为ＭＩＰＳ，犪犽为第犽次预测时的系统负载程度，犚犞犪犽犿（犽）指第犿号计算第犽次实际的执行速度，ρ是一个调节参数，用来在不同云环境中调节经验值和预测值的比重，以使该模型的预测达到最优．在每一个计算节点上，每完成一个作业，该节点自身将会记录本次作业完成的实际速度，并结合上次的预测结果来推算下次作业可能的执行速度．同时，系统负载犪被一并记录，这是一个重要的参数，一般可以有几个量化指标，比如ＣＰＵ的实际使用率、作业数或者线程数等．２．４　使用蚁群算法寻找最合适的计算资源由于在云计算环境中，资源的具体情况不可知，且网络没有一个固定的