（计算机应用技术专业论文）网格资源分配中混合并行蚁群算法方式研究.pdf

中文摘要 随着网络技术和网络应用的飞速发展，网络设备和网络资源变得越来越繁杂， 网络应用需求日益朝着高性能、大规模的方向发展，网格技术就是将地理上分布的、 异构的各种网络资源、存储资源、数据资源和其它特殊资源通过高速网络连接起来， 共同完成重大应用问题。网格技术不同于一般传统的分布式计算，它着重于大规模 的资源共享和协同工作，并在一定情况下定位于高性能计算，已经成为一个重要领 域。在网格环境中，资源具有的异构性、分布性和动态性，使得网格资源的管理和 分配成为一个n p - h a r d 问题，而传统的资源分配方法在网格环境中的效率并不高。 于此同时，一些模拟自然生态机制的智能算法在求解复杂的组合优化问题中取得了 很好的效果，如人工免疫算法，遗传算法，蚁群算法都有很好的自适应性。尤其是 蚁群算法的提出，为解决具有n p o h a r d 性的组合优化问题开辟了新的研究方向。 本文针对网格中资源管理和分配的特点，主要利用蚁群算法在求解组合问题中 的优越性来解决网格中资源分配问题。通过对蚁群算法原理的分析和深入探讨，设 计了基于蚁群算法的网格资源分配模型。利用实验仿真得到的结果也充分说明了蚁 群算法在网格资源分配中的应用是十分成功的。在对算法改进的过程中，也极大的 丰富了现有的蚁群算法。本文主要在一下几个方面进行了一些研究： 1 介绍了网格技术及网格资源分配和调度的相关研究和发展趋势。 2 介绍了基本蚁群算法和几种蚁群算法模型 3 阐述了传统的网格资源分配的特点，结合蚁群算法设计了基于蚁群算法的 网格资源分配模型。 4 针对网格资源分配的不足，介绍7 资源分配中的智能优化算法一蚊群算 法。并说明优化算法在资源分配中的应用效果。 5 提出改进的蚁群算法和混合并行蚁群算法求解资源分配问题，并分析算法 的实验仿真结果和性能。 本论文在最后部分给出了结论并指出网格资源分配进一步研究的方向。 关键词：网格，资源分配，蚂蚁算法，混合并行蚁群算法 a b s t r a c t w i t ht h ed e v e l o p m e n to fn e t w o r kt e c h n o l o g ya n da p p l i c a t i o na te x p r e s ss p e e d ， n e t w o r ke q u i p m e n ta n dr e s o u r c eb e c o m em o r ea n dm o r en u m e r o u sa n dv a r i o u s t h e n e e df o rn e t w o r ka p p l i c a t i o nd e v e l o p st o w a r d sh i 曲p e r f o r m a n c ea n dl a r g e s c a l e g r i d t e c h n o l o g yi st oc o n n e c tv a r i o u sn e t w o r kr e s o u r c e s ，s t o r e dr e s o u r c e ，d a t ar e s o u r c ea n d o t h e rs p e c i a lr e s o u r c ed i s t r i b u t e dh e t e r o g e n e o u si ng e o l o g yb yh i g h s p e e dn e t w o r ki n o r d e rt oc o m p l e t ei m p o r t a n ti s s u e so na p p l i c a t i o n g r i dt e c h n o l o g yi sd i f f e r e n tf r o m t r a d i t i o n a ld i s t r i b u t e dc o m p u t i n g i tf o c u s e so nl a r g e - s e a l e dr e s o u r c es h a r ea n dw o r ki n c o o r d i n a t i o n , a n do r i e n t a t e si nh i 【g h - p e r f o r m a n c ec o m p u t i n gi ns o m ec a s e ，w h i c hh a s b e c a m ea ni m p o r t a n tf i e l d i n 鲥de n v i r o n m e n t , r e s o u r c eo w l s h e t e r o g e n e o u s ， d i s t r i b u t e da n dd y n a m i cc h a r a c t e r i s t i c ，w h i c hm a k e st h em a n a g e m e n ta n da l l o c a t i o no f g r i dr e s o u r c eb e c o m ean p h a r dp r o b l e m h o w e v e r , t h et r a d i t i o n a lm e t h o df o rr e s o u r c e a l l o c a t i o nu s e di ng r i de n v i r o n m e n th a sal o we f f i c i e n c y a tt h es a l n et i m e ，s o m en e w i n t e l l i g e n tc a l c u l a t i o nm e t h o dw h i c hi s u s e dt or e s o l v ec o m p l i c a t e do p t i m i z a t i o n p r o b l e m sb ys i m u l a t i n gn a t u r a le c o l o g i c a lm e c h a n i s m s o e ha sa r t i f i c i a li m m u n i t y a l g o r i t h m , g e n e t i ca l g o r i t h ma n da n tc o l o n ya l g o r i t h mh a v eg a i n e dg o o de f f e c tb e c a u s e o fs e l f - a d a p t i v e a m o n gt h e s ea l g o r i t h m s ，a n tc o l o n ya l g o r i t h ms t a r t san e wr e s e a r c h f i e l df o rs o l v i n gp r o b l e m sa b o u to p t i m i z a t i o ng r o u p i n gw i t hn p h a r df e a t u r e s t h et h e s i sm a i n l ym a k e su s eo ft h es u p e r i o r i t yo fa n tc o l o n ya l g o r i t h mi ns o l v i n g g r o u p i n gp r o b l e m st os e t t l et h eq u e s t i o no fg r i dr e s o u r c ea l l o c a t i o ni na c c o r d a n c ew i t h t h ef e a t u r eo fr e s o u r c em a n a g e m e n ta n da l l o c a t i o ni ng r i d t h o u g ht h ea n a l y s i so fa n d d e e pi n s i g h ti n t ot h ep r i n c i p l eo fa n tc o l o n ya l g o r i t h i l , t h ea u t h o rd e s i g n st h em o d e lo f g r i dr 韶o u r e ea l l o c a t i o nb a s e do na n tc o l o n ya l g o r i t h m t h er e s u l tg e t t i n gf i o mt h e s t i m u l a t e de x p e r i m e n ta l s of u l l yp m v e st h a tt h ea p p l i c a t i o no fa n tc o l o n ya l g o r i t h mi n g r i dr e s o u r c ea l l o c a t i o ni sv e r ys u c c e s s f u l t h ei m p r o v e m e n to ft h ea l g o r i t h ma l s o e n r i c h e st h ep r e s e n ta n tc o l o n ya l g o r i t h m t h et h e s i sm a i n l yh a st h er e s e a r c hi nt h e f o l l o w i n gi s s u e s 1 m a k eal i t e r a t u r er e v i e wa n di n t r o d u c et h ed e v e l o p m e n tt e n d e n c yo fn e t w o r k t e c h n o l o g ya n dr e s o u r c ea l l o c a t i o na n dd i s p a t c h 2 i n t r o d u c et h eb a s i ca n tc o l o n ya l g o r i t h ma n ds o m ep r o t o t y p e so f i t 3 e x p l a i nt h ef e a t u r eo ft r a d i t i o n a lg r i dr e s o u r c ea l l o c a t i o n d e s i g nt h em o d e lo f g r i dr e s o u r c ea l l o c a t i o nb a s e do na n tc o l o n ya l g o r i t h m 4 a i m i n ga tt h ed i f f i c u l tp o i n ti ng r i dr e s o u r c ea l l o c a t i o n , i n t r o d u c et h ei n t e l l i g e n t o p t i m i z a t i o na l g o r i t h mi nr e s o u r c ea l l o c a t i o n - - a n tc o l o n ya l g o r i t h m a n dd i r e c t i o n si t s a p p l i c a t i o ne f f e c to nr e s o u r c ea l l o c a t i o n 5 p u tf o r w a r dt h er e f o r m e da n tc o l o n ya l g o r i t h ma n dh y b r i d p a r a l l e la n tc o l o n y a l g o r i t h mt os o l v et h ep r o b l e mo fr e s o u r c ea l l o c a t i o na n da n a l y z et h er e s u l ta n d p e r f o r m a n c eo f t h ea l g o r i t h mi ns i m u l a t e de x p e r i m e n t t h et h e s i sm a k e sac o n c l u s i o na n dp o i n t so u tt h ed i r e c t i o nf o rt h ef u t u r er e s e a r c hi n g r i dr e s o u r c ea l i o c a t i o ni nt h e1 a s tp a r t k e yw o r d s ：g r i d ；r e s o u r c ea l l o c a t i o n ；a n tc o l o n ya l g o r i t h m ； h y b r i dp a r a l l e la n tc o l o n ya l g o r i t h m 硕士擘位论文 m a s t e r st h e s i s 华中师范大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立进行研究工作 所取得的研究成果。除文中已经标明引用的内容外，本论文不包含任何其他个人或 集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在 文中以明确方式标明。本声明的法律结果由本人承担。 作者签名：扫皮绎 日期：伽7 年善月i o b 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有权 保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借 阅。本人授权华中师范大学可以将本学位论文的全部或部分内容编入有关数据库进 行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。同时授权 中国科学技术信息研究所将本学位论文收录到中国学位论文全文数据库，并通 过网络向社会公众提供信息服务。 作者签名：杠递华 日期：御年6b o 日 本人已经认真阅读“c a l i s 高校学位论文全文数据库发布章程”，同意将本人的 学位论文提交“c a l i s 高校学位论文全文数据库”中全文发布，并可按“章程”中的 规定享受相关权益。囤壶诠塞握銮后进卮! 旦圭生；旦= 生；旦三生蕴查! 作者签名：松也垆 日期：伽年z 月f d 日 导师签名 日期： 硕士擘位论文 m a s t e r st h e s i s 1 1 研究背景 第一章绪论 随着计算机性能的不断提高和网络通讯技术的迅猛发展，应用需求日益朝着高 性能、大规模、多样性、多功能的方向发展，要求将地理上分布的、异构的各种高 性能计算资源、存储资源、数据资源和其它特殊资源通过高速网络连接起来，实现 高性能联合计算，共同完成重大应用问题，即广域高性能的元计算技术【”，也称为 网格计算技术【2 3 】1 4 1 。网格不同于一般传统的分布式计算，网格计算着重于大规模的 资源共享、创新应用，并在一定情况下定位于高性能计算，已经成为一个重要领域。 在网格计算环境中，资源是分散在各个不同地域和管理域中，由不同的组织拥有和 操作，并且在使用策略和安全机制上各不相同，即不同站点可能会使用不同的局部 资源管理系统。同时，很多应用需要同时使用多个站点上的资源，站点自治性和分 配资源时可能出现的故障需要一种特殊机制来同时分配位于多个站点上的资源。因 此，如何对网格计算环境中的资源进行合理管理和有效分配是实现高性能联合计 算，共同完成重大应用问题的关键。 资源管理是网格计算的核心问题1 5 l ，而资源分配以及资源分配算法又是资源管 理的关键技术和核心问题1 6 1 。从为用户提供方便、高效的服务的角度来看，资源管 理系统模型应具有三个部分的功能：作业管理，资源目录管理和资源分配。由于网 格系统的分布性、异构性和动态性，使得网格资源管理比分布式计算环境或集群计 算环境下的资源管理更加复杂，不仅要支持跨组织或管理域的资源调度，实时监控 资源的状态，而且要维护局部的站点资源自治。因此要提高这种复杂系统的性能， 很大程度上要提高资源管理的效率和设计好的资源分配算法，从而满足网格系统的 用户服务需求和为网格系统其它服务组件提供支持。由此可见，网格资源的分配对 于网格资源管理起着重要雨关键的作用，同样对网格这一复杂系统来说，网格资源 分配器和资源调度算法都是核心关键部件，所以对网格资源分配的研究和分配算法 的研究是极具有挑战和很有意义的。 另一方面，自从8 0 年代以来，尤其是最近几年，通过模拟自然生态机制求解复 杂优化问题的新型计算智能方法，如神经网络，遗传算法，蚁群算法，免疫算法等 相继出现，使得很大一类n p - h a r d 优化问题应用有了很好的智能优化算法，大大地丰 富了最优化技术。模拟自然生物的方法具有很好的自适应性，其中从意大利学者 m d o r i g o ，a c o l o r n i 和v m a n i e z z o ( 1 9 9 1 ) 等提出的蚂蚁算法【刀( 卸ta l g o r i t h m ) 开始，该算法对具有n p h a r d 性的组合优化的调度问题有很好求解。同时，n p h a r d 问题也成为蚁群系统研究的一个重要研究方向。如何将蚁群算法引用到网格环境下 的资源分配是本文要研究的重点。 1 2 网格概述 1 1 1 网格定义 网格( g r i d ) 一词来自于电力网( e l e c t r i c p o w e r g r i d ) ，网格的最终目的是希望用户 在使用网格计算能力时，就如同在使用电力一样方便【3 】。我们在使用电力时，不需 要知道它是从哪个发电站输送出来的。也不需要知道该电力是通过什么样的发电机 产生的，不管是水力发电，还是通过核反应发电，我们使用的是一种统一形式的。电 能”。同样，我们也不需要考虑我们使用电力做什么，不管是照明，取暖，还是给 电动机或仪器供电，我们都只需将插头插入带电的插座即可。网格希望把整个互联 网虚拟为一台超级计算机，给最终的使用者提供一种与地理位置无关、与具体的计 算设旌无关的通用计算能力。 网格是构筑在互联网上的一组新兴技术，它将高速互联网、计算机、大型数据 库、传感器、远程设备等融为一体，为科技人员和普通用户提供更多的资源、功能 和服务。网格把用通信手段连接起来的资源无缝集成为一个有机的整体。它给用户 提供一种基于i n t c r n e t 的新型计算平台，在这个平台上对来自客户的请求和所提供 资源的能力之间进行合理的匹配，为用户的请求选择合适的资源服务，可实现广域 范围的资源共享。网格把分布的资源集成为一台能力巨大的超级计算机，提供计算 资源、存储资源、数据资源、信息资源、知识资源、专家资源、设备资源的全面共 享。资源荚享是网格的根本特征，消除资源孤岛是网格的奋斗目标【蜘。 从美国、日本及欧洲的发达国家到印度这样的发展中国家都启动了大型网格研 究计划，并得到了产业界的大力支持。网格的发展到目前为止基本上可以划分为以 下三个阶段 9 1 ： 一是萌芽阶段：在上个世纪9 0 年代初期，主要是千兆网的测试床以及一些元 计算的实篪。 二是早期实验阶段：在上个世纪9 0 年代中期到晚期，如i - w a y 项目0 0 l ，还包 括一些学术性的软件项目，例如g l o b t m l l l 】1 1 2 】【1 3 】、l e g i o n t 】等。 三是飞速发展阶段：2 0 0 2 年以来，出现了大量的应用社团和项目，主要基础市 2 硕士学位论文 m a $ t e r st h e $ i s 话的开发和使用，工业界对网格计算的兴趣在增长，例如m m 、p l a t f o r m 、m i c r o s o f t 、 s u n 、c o m p a q 等重要的公司。同时也出现了一比较显著的技术基础，如g l o b u s t o o l k i t ，形成了具有相当规模和世界影响的全球网格论坛o g f ( g l o b a lg r i df o r u m ) 组织。 关于网格以及两格计算本身还没有一个公认的定义。以下是网格研究权威专家 i a nf o s t e r 2 0 0 2 年从三个方面给网格下了一个比较明确的定义，他认为网格是具备有 以下三个条件【1 5 】的系统： ( 1 ) 网格能协调非集中式控制的资源，能集成和协调资源与用户在不同控制 域内的活动，能解决包括安全、策略，认证、支 寸和成员资格等各种问题。 ( 2 ) 网格使用标准的、开放的、通用的协议和接口，网格是根据多用途协议 和接口来构建的，该协议和接口能解决诸如鉴别、授权、资源发现和资源访问等一 系歹 3 基本溺题。 ( 3 ) 网格提供高质量的服务，允许按协作的方式来使用其成分资源，以及协 作配置多重资源类型以满足复杂用户的需要。 1 1 2 鼹格体系结梅 网格体系结构包括两个层次的内涵。一是要标识出网格系统由哪些部分组成， 清晰地描述出各个部分的功能、目的和特点。二是要描述网格各个组成部分之间的 关系，如 可将各个部分有机地结合在一起。形成完整的网格系统，从而保证网格有 效地运转，也就是将各个部分进行集成的方式或方法。网格技术的权威f a nf o s t e r 将网格体系结构定义为“划分系统基本组件，指定系统组件的目的与功能，说明组 件之间如何相互作用的技术”。显然，网格体系结构是网格的骨架，只有建立合理 的网格体系结构，才能设计和构建好网格。 网格体系结构要考虑到是如何向用户提供一个接口，通过该接口接收来自用户 的请求，发送来自网格的信息。用户可以将所使用的网格看作是一个黑盒子，不必 知道其内部如何实现用户请求的服务。实际上，网掺系统中是由一系列的基本功能 模块协作，向用户提供服务的，网格系统的基本功能模块如图1 - 1 所示。 硕士荦位论丈 m a s t e r st h e s i s 图卜1 网格系统的基本功能模块示意图 网格用户通过用户界面实现与网格之间的信息交互，实现诸如用户作业提交、 结果返回等输入输出功能。网格在提供服务之前要知道哪个资源当前可以向用户提 供服务，这就需要网格中信息管理模块提供相应的信息。选定合适的资源后，网格 需要把该资源分配给用户使用，并对使用的过程中的资源进行管理，这些是资源管 理的功能。网格在提供服务的过程中需要网格数据管理功能模块将远程数据传输到 所需节点，作业运行过程中由作业管理模块提供作业的运行情况汇报。使用网格的 用户及其使用时间和费用等的管理则由用户和记账管理模块实现，用户使用网格的 整个过程中都需要q o s ( q l j a l i t yo f s e i c e ，服务质量) 保证、通信和安全保障，以 提供安全可靠，高性能的服务。 五层沙漏体系结构1 1 6 1 是由i a nf o s t e r 等提出的一种具有代表性的网格体系结构， 其影响十分广泛，它的特点就是简单，主要侧重于定性的描述两不是具体的协议定 义，容易从整体上进行理解。在五层沙漏体系结构中，最基本的思想就是：以协议 为中心，强调服务与a p i 和s d k 的重要性 五层沙漏结构的设计原则就是要保持参与的开销最小，即作为基础的核心协议 较少，类似于o s 内核，以方便移植。另外，沙漏结构管辖多种资源，允许局部控 制，可用来构建高层的、特定领域的应用服务，支持广泛的适应性。 五层沙漏结构根据该结构中各组成部分与共享资源的距离，将对共享资源进行 操作、管理和使用的功能分散在五个不同的层次，由下至上分别为构造层( f a b r i c ) 、 连接层( c o n n e c t i v i t y ) 、资源层( r e s o u r c e ) 、汇聚层( c o l l e c t i v e ) 和应用层 ( a p p l i c a t i o n ) ，如图1 2 所示。 4 1垂兰墨! ! ! 兰：!i 图1 - 2 沙漏形状的五层结构 在五层结构中，资源层和连接层共同组成了瓶颈部分，使得该结构呈沙漏形状。 其内在的含义就是各部分协议的数量是不同的，对于其最核心的部分，要能够实现 上层各种协议向核心协议的映射，同时实现核心协议向下层各种协议的映射，核心 协议在所有支持网格计算的地点都应该得到支持，因此核心协议的数量不应该太 多，这样核心协议就形成了协议层次结构中的一个瓶颈。 构造层( f a b r i c ) 的基本功能就是控制局部的资源，包括查询机制( 发现资源的 结构和状态等信息) 、控制服务质量的资源管理能力等，并向上提供访问这些资 源的接口。构造层资源是非常广泛的，可以是计算资源、存储系统、目录、网 络资源以及传感器等等。构造层资源提供的功能越丰富，则构造层资源可以支 持的高级共享操作就越多，例如如果资源层支持提前预约功能，则很容易在高 层实现资源的协同调度服务，否则在高层实现这样的服务就会有较大的额外开 销。 连接层的基本功能就是实现相互的透信。它定义了核心的通信和认证协议，用 于网格的网络事务处理。通信协议允许在构造层资源之间交换数据，要求包括 传输、路由、命名等功能。在实际中这些协议大部分是从t c p 佃协议栈中抽取 出的。认证协议建立在通信服务之上，提供的功能包括；单一登录、代理、与 局部安全方法的集成、基于用户的信任机制。 资源层的主要功能就是实现对单个资源的共享。资源层定义的协议包括安全初 始化、监视、控制单个资源的共享操作、审计以及付费等。它忽略了全局状态 和跨越分布资源集合的原子操作。 汇聚层的主要功能是协调多种资源的共享。汇聚层协议与服务描述的是资源的 共性，包括目录服务、协同分配和调度以及代理服务、监控和诊断服务、数据 硕士学位论文 m a s t e r st h e s i s 复制服务、网格支持下的编程系统、负载管理系统与协同分配工作框架、软件 发现服务、协作服务等。它们说明了不同资源集合之问是如何相互作用的，但 不涉及到资源的具体特征。 应用层是在虚拟组织环境中存在的。应用可以根据任一层次上定义的服务来构 造。每一层都定义了协议，以提供对相关服务的访问，这些服务包括资源管理、 数据存取、资源发现等。在每一层，可以将a p i 定义为与执行特定活动的服务 交换协议信息的具体实现。 1 1 3 两格研究现状 目前，m m 是网格系统和服务方面的领先供应商，已经为很多科技团体、政府 机构、商业化用户的网格系统提供了产品和服务，其中包括英国国家网格、荷兰国 家各、北卡州的生物网格等等。美国太阳微系统公司2 0 0 2 年发布了“网格引擎” 企业版的测试版。h p 公司也提出了u t i l i t yc o m p u t i n g 计划和u t i l i t yd a t ac e n t e r 产 品。o r a c l e 公司2 0 0 2 年1 1 月推出面向网格的基于g l o b u s 的数据库应用工具。2 0 0 8 年北京奥运会的计算机信息处理系统将应用网格，m m 、o r a c l e 、s u n 、n p 都已推 出了一系列可应用网格的产品。日本文部科学省2 0 0 3 年5 月决定投资7 0 0 亿日元 开发超大型网格计算机，它出现在世界上运算速度最快的计算机还快近l o 倍，将 达每秒3 0 0 万亿次。 下一代互联网技术是完全崭新的，从光纤到路由器、交换机、上层服务器、操 作系统、各种系统软件和应用软件都将产生革命性的变革。因而，在网格的发展道 路上，g l o b u s 和它的各种替代版本将面临巨大障碍。为实现网格的广泛应用，还必 须解决下列问题： ( 1 ) 标准是成功关键。就像t c p f i p 协议是互联网的核心一样，构建网格计算 也需要对标准协议和服务进行定义。迄今为止，网格计算还没有正式的标准，但在 核心技术上，g l o b u s t o o l k i t 已成为网格计算事实上的标准。 ( 2 ) 网格资源动态分配问题。如何在动态、异构虚拟组织间实现协同的资源 共享以及协同是网格中非常重要的问题。已有的一些并行和分布计算系统的资源分 配技术，并不能很好地适应计算网格资源分配问题的特点。 ( 3 ) 数据通过因特网时形成的延迟问题。目前互联网的数据传输能力不足问 题。进一步解决入机结合问题，使网格更加个性化、智能化和科学化。通过法律的 手段解决网上资源共享中的智能产权、相互信任和报酬等问题以及如何保障网格计 算的安全性、认证和可靠性等。 6 项士擘位论文 m a s t e r st h e s i s 尽管网格技术还远不如互联网和w e b 技术那么成熟，但已经在一些公司和研究 所进入了使用或试验阶段。美国能源部的山地亚国家实验室最近宣布，他们的“先 进战略计算创新计划网格( a s c ig r i d ) ”主要用于核武器研究。美国国防部和欧洲能 源机构等都在两三年前先后开始采用网格技术。m m 公司部署了一个内部研究网 格，以便于分散在美国、以色列、瑞士、等地的i b m 研究人员共享计算资源。医药、 化工、通信、电子、汽车等领域的一些大公司，如辉瑞、爱立信、日立、宝马、联 合利华，葛兰素威康、史克必成等，都已经开始构造和使用内部网格。 我国家在九五期间就资助了“8 6 3 ”重点项目“国家高性能计算环境”t i t l 。该 项日由中科院计算所联合了十几家科研单位共同参与，其目标是建立一个分布式环 境下支持异构平台的计算网格示范系统，它把我国的8 个高性能计算中心通过 i n t e r n e t 连接起来，进行统一的资源管理、信息管理和用户管理，并在此基础上开发 了多个计算型的网格应用系统，取得了一系列研究成果。十五期问，国家设立了 “8 6 3 ”重大专项“高性能计算及其核心软件”，计划在2 0 0 2 年到2 0 0 5 年期间投资 “8 6 3 ”计划经费l 亿元，并吸引地方政府、应用部门和产业界2 3 倍的配套资金。 目前，正在进行的比较大的网格项目有五个。 中国国家网格l l 町专项由国家8 6 3 高技术研究发展计划资助，旨在建立面向企业、 高等院校、科研机构、政府部门的国家高性能计算环境。主节点采用自行研制的、 面向网格的高性能计算机。若干工业、服务业、科学研究以及资源环境领域的网格 应用投入运行，实现资源共享、协同工作。专项的主要任务包括：建设中国国家网 格实验床( c n g r i d ) ；建立具有4 万亿次以上计算能力的网格主节点：支持网格应用 以及维护网格系统运行的网格软件；开发具有代表性的网格生产性应用。 中国教育科研网格( c h i n a g r i d ) t 1 9 】计划是教育部“十五”2 1 1 工程公共服务体系 建设的重大专项，受国家高技术研究发展计划( 8 5 3 计划) 项目支持。它是迄今为止 由政府推出的最宏大的网格工程，该项目由1 2 所大学联合推出，到网格建成时， 它将在教育科研网上把全国1 0 0 所2 1 1 建设重点大学的资源广泛共享。中国教育科 研网格的目标是将广泛分布在中国教育科研网c e r n e t 和高校中的异构海量资源 集成起来，实现c e r n e t 环境下资源的有效共享，消除资源孤岛，提供有效的服务， 形成为国家科研教学服务的大平台。 我国网格研究还应用与其他的许多行业。如能源、交通、气象、水利、农林、 环保等对高性能计算网格即信息网格的需求是非常巨大的。 7 硕士擘住论文 m a s t e r st h e s i s 1 3 网格资源管理平台 网格资源管理是网格的核心。而资源分配的研究对网格资源管理又起着相当重 要的作用1 2 0 】。如何在基于网格计算的信息资源海洋中快速发现有用的资源，探索更 有效的资源分配机制与技术已经是信息工业，乃至整个计算机产业最重要的研究领 域之一。而未来的网格环境下的资源将比今天的网络环境下更为丰富，更加多样， 如果能够探索研究发明出更加先进高效的资源分配机制和技术，必将产生巨大的社 会贡献和经济效益。设计好的资源分配算法已经成为网格资源管理的关键技术之 一 1 3 1 网格资源的基本特征 网格作为一种新出现的重要的网络基础设施，和其他的系统相比，它的资源有 四个特点：分布性；动态性；异构性；自治性与管理的多重性 ( 1 ) 分布性指网格的资源是分布的。不同计算能力的计算机，各种类型的数 据库乃至电子图书馆，以及其他各种分布在不同地理位置的设备与资源，都是网格 资源。 c 2 ) 动态特性是指网格的资源或服务的动态加入或减少的。由于网格是多种 资源和服务的汇集，其本身的可扩展性和动态性决定了其资源也一定具有动态性。 ( 3 ) 异构性是指网格中的资源可能存在不同体系结构的计算机系统中，网格 必须解决这些不同结构、不同资源之问的通信和互操作问题。 ( 4 ) 自治性是指网格资源的拥有者对该资源具有最高管理权限，网格允许资 源拥有者对它的资源有自主的管理能力。同时，网格资源又是一个网格的局部，它 必然要接受统一管理，否则，就无法实现共享和互操作。网格资源管理的多重性就 体现在它的自主管理同时还要接受统一管理。 1 3 2 网格资源管理模型分类 由于网格在逻辑上连接了属于不同的所有者或组织的多重资源，因而选择合适 的资源管理体系结构模型在最终网格是否成功上起着重要的作用。 最主要的三种网格中的资源管理体系结构模型是：分层模型、抽象所有者模型 以及计算经济模型i 列1 1 2 2 。 分层模型是g l o b u s ，l e g i o n ，n i n f 等网格系统所使用的资源管理模型。它较好 地解决了网格计算环境给资源管理所带来的一些挑战性问题，如：站点的自治性、 8 硕士学位论文 m a s t e r st h e s i s 底层的异构性、以及联合分配问题等。 抽象所有者模型在资源共享过程中遵循类似于快餐店的订购与交货模式，由资 源经纪人( 抽象所有者) 代表资源所有者与用户进行交互和协商。 计算经济模型将经济的概念引入网格资源管理中，它应用了市场经济中的供求 原则来对资源的所有者和使用者进行调节以保证双方均获取最大利益，建立以用户 为中心，而不是系统为中心的调度政策，提供了资源分配和管理的有效机制。 1 3 3 现有的成熟的资源管理系统 资源管理是网格研究的一个核心问题。针对网格资源管理的特点，国外一些网 格研究项目根据自己的目标设计了不同的系统。大体上可以分为基于g l o b u s 的和基 于j a v a 的两大类。 第一类是弼格系统中比较广泛的g l o b u s 项目。它是当之无愧的现在国际上最有 影响力的与网格计算相关的项目，是由来自世界各地关注网格技术的研究人员和开 发人员共同努力的成果。g l o b u s 追求计算网格的构建，提供一个软件框架，可以将 分布异构的计算资源看为一个单一的虚拟组织【4 】【”1 g l o b u s 系统的一个核心元素是 g l o b u s 工具集，它定义了基本的服务和构建计算网格的能力。该工具由一系列的组 件构成，以实现安全、资源定位、资源管理、数据管理、资源预约和通信等基本服 务。工具箱提供了大量的服务，从可选择的开发专用的工具或应用，以满足他们特 殊的要求。g l o b u s 构建一个分层的结构，高层可以调用底层的服务。 在g l o b u s 项目中，资源和状态信息有一个基于l d a p ( 轻量级目录访问协议1 的 m d s ( 元目录服务) 组成。m d s 由g i s ( ! 丽i 格检索服务) 和g r i s ( 网格信息服务) 两个组 件组成。g r i s 实现了一个为了查询网格中资源提供者的当前状态、能力和配置的 统一接口。g i s 从多个g r i s 中提取信息并集成一个单一的一致的资源信息数据库。 资源信息提供者使用一个p u s h 协议更新g r i s 。 在g l o b u s 项目中，m d s ( 源目录服务) 在资源发现和分配方面同时使用p u s h 和 p u l l 协议。高层工具如资源代理通过查询m d s 执行资源发现。m d s 名字空间以树 结构分层组织。g l o b u s 以资源预约方式提供q o s 。g l o b u s 提供调度组件，但不提供 相应的调度策略。g l o b u s 被用于开发许多全局调度器，包括n i m r o d - g ，a p p l e s 和 c o n d o r - g 。 现有的较为成熟的g l o b u s 项目有： a p p l e s ( a p p l e s ，a p p l i c a t i o nl e v e ls c h e d u l e r ) 1 2 3 】【2 4 1 项目是由加利福尼亚大学 圣迭戈分校开发的，主要用于在生产网格的个人应用的调度代理。它使用网际气象 9 硕士学位论文 m a s t e r st h e s i s 服务n w s ( n e t w o r kw j a t l l e rs e r v i c e ) 的服务动态监视资源性能的变化。a p p l e s 项目 遵从由底层网格中间件系统提供资源管理模型的框架。是一个有预测性的启发式的 状态估计模型，可在线重调度和面向应用的调度策略。 c o n d o r - g i 茚l l 拍i 是由威斯康星麦迪逊大学开发的一个高吞吐量计算环境，可以 管理大量的象由不同个体拥有的p c s 、工作站和集群计算集。尽管c o n d o r 被普遍认 为是利用周期窃取窃取方式，但它可以被配置成资源共享模式。c o n d o r 环境同样遵 循分层的体系结构，为并行和顺序应用提供强大和灵活的资源管理服务。c o n d e r 系 统特别关注计算机主人对资源的控制和分配给c o n d o r 池的控制能力。但它不提供 q o s 支持。 下面是基于几个i a v a 的网格项目： j a v e l i n l 2 7 j 是一个基于j a v a 的框架，用于内部网的并行计算的网格项目，是一 个高吞吐量的网格计算系统。j a v e l i n 系统的三个关键组件是客户或应用、主机和代 理。c l i e n t 是一个执行搜索计算资源的进程。h o s t 是提供计算资源的进程。b r o k e 是一个协调分配资源的迸程。j a v e l i n 支持计算的计件和分支跳跃模型。j a v e l i n 使用 的一个分布调度方法可实现负载平衡。j a v e l i n 使用层次型体系结构，每个代理组织 一个主机树。资源被简单的固定在一个树状名字空间的对象上。信息存储是一个由 j a v e i i n b n s 实现的网络目录。作为调度结果，主机和代理相互更新。因此，j a v e l i n 使用需求资源分发。资源发现和分配使用基于路径的分布查询。 l e g i o n l 勰1 是由维吉尼亚大学( r g 随a ) 开发的一个面向对象的元系统或网格操 作系统。l e g i o n 提供了一个能使异构的、地理上分布的、高性能的机器可以实现无 缝的互操作的软件框架它给应用用户提供一个单一的、一致的、虚拟的机器。它 的对象代表了所有的网格组件。它的体系结构时遵从分层模型。能控制主机的负载 并为应用级调度提供资源预约以执行周期和批调度。l e g i o n 的资源管理体系是分层 的而调度策略是分布的。 1 。4 本文的主要工作 本文针对网格系统中资源分配和管理以及资源分配算法问题，研究其中的网格 资源分配系统的资源的分配调度算法，特别是结合现有的蚁群算法提出了新的网格 资源分配模型，并且改迸现有的蚁群算法，设计了自适应蚁群算法以及并行的蚁群 算法，并模拟两种算法在网格资源分配中的应用。论文主要从以下几个方面做了一 定的工作： i o l 、结合网格资源管理和分配的特点，提出了结合蚁群优化算法的网格资源分 配系统。 2 、提出并设计了基于自适应的蚁群算法的网格资源分配算法，在改进了现有 的蚁群算法的基础上采用新的资源分配策略，满足了网格对分配系统全局最优调度 的需求。 3 、提出了一种混合并行的蚁群算法，主要针对蚁群算法早期搜索信息素不足 而提出，利用遗传算法，综合考虑了算法的局部早熟、迭代速度和收敛性等因素， 通过一个新的资源分配策略实现了时间代价的最优化，提高了资源分配的效率。 4 、对提出的算法进行了模拟仿真和结果分析，进一步论证算法的可靠性、高 效性和并行可扩展性。 1 5 论文的组织结构 第1 章介绍了网格以及网格资源管理等基本知识，包括网格的体系结构，网格 资源管理的基本特征和现有的资源管理系统。同时也说明了选题的依据和文章研究 的重要意义。 第2 章介绍了的蚁群原理和几种常用的蚁群系统，并对几种成熟的蚁群算法进 行了对比分析。一方面看到了蚁群算法在解决组合问题时取得了较好的结果，另一 方面也发现蚁群算法在求解n p - h a r d 中的不足。 第3 章结合网格资源分配组合问题和蚁群算法在组合问题中求解的特点，设计 了新的网格资源分配模型和问题求解思路。蚁群系统和网格资源管理和分配其实是 具有相通之处的，使用蚁群算法来优化资源的分配有着很好的切合点。 第4 章提出了自适应的蚁群算法，并模拟仿真自适应的蚁群算法思想是在原 有的蚁群算法的基础上加入动态参数的思想来改进现有的蚁群算法，使得改进算法 比较快的收敛于预期的结果。 第5 章克服蚁群算法信息素难以收集的问题，提出了混合的并行蚁群算法。蚁 群算法早期对信息素的收集比较困难，为此加入另一种全局搜索算法一遗传算 法，该算法既可以克服信息素难以收集困难的问题，有可以提高蚁群算法求解的并 行性。 第6 章总结了文章所做的主要工作和贡献，特别是引入智能优化算法来解决网 格资源分配问题；另一方面也对进一步深入研究提出了思路和展望。 第二章蚁