（计算机应用技术专业论文）基于gapso混合算法的网格工作流调度研究.pdf

t h e s i sf o rm a s t e rd e g r e e ，eastch i nanorma lu n i v e r s i t yr e s e a r c ho ng r i d 侈勿r k f l 0 ws c h e d u l i n gb a s e do ng a p s oa l g o r i t h md e p a r t m e n t ：q 幽丛! 星! 星堕! 星! q s ! gm a j o r ：r e s e a r c ha r e a ：迎坠鲤卫! i 堡丛q 堕显曼丛q ! q 蚁s u p e r v i s o r ：q i 坠g 墨q 坠g1 堑墨星坠i q ! 垦坠g i 坠星星!c a n d i d a t e ：n o v e m b e r , 2 010s h a n g h a i华东师范大学学位论文原创性声明郑重声明：本人呈交的学位论文基于g a p s o 混合算法的网格工作流调度研究，是在华东师范大学攻读絮严博士( 请勾选) 学位期间，在导师的指导下进行的研究工作及取得的研究成果。除文中已经注明引用的内容外，本论文不包含其他个人已经发表或撰写过的研究成果。对本文的研究做出重要贡献的个人和集体，均已在文中作了明确说明并表示谢意。作者签名：日期：7 2 , 1 。年ff 月狮华东师范大学学位论文著作权使用声明基于g a p s o 混合算法的网格工作流调度研究系本人在华东师范大学攻读学位期间在导师指导下完成的硕芷博士( 请勾选) 学位论文，本论文的研究成果归华东师范大学所有。本人同意华东师范大学根据相关规定保留和使用此学位论文，并向主管部门和相关机构如国家图书馆、中信所和“知网”送交学位论文的印刷版和电子版；允许学位论文进入华东师范大学图书馆及数据库被查阅、借阅；同意学校将学位论文加入全国博士、硕士学位论文共建单位数据库进行检索，将学位论文的标题和摘要汇编出版，采用影印、缩印或者其它方式合理复制学位论文。本学位论文属于( 请勾选)() 1 经华东师范大学相关部门审查核定的“内部”或“涉密”学位论文 ，于年月日解密，解密后适用上述授权。本人签名伽f o 年f1 月 - c 牛hi幸“涉密”学位论文应是已经华东师范大学学位评定委员会办公室或保密委员会审定过的学位论文( 需附获批的华东师范大学研究生申请学位论文“涉密”审批表方为有效) ，未经上述部门审定的学位论文均为公开学位论文。此声明栏不填写的，默认为公开学位论文，均适用上述授权) 。硕士学位论文答辩委员会成员名单姓名职称单位备注主席杨宗源教授华东师范火学信息学院朱敏高工华东师范人学信息学院陈志云副教授华东师范人学信息学院华东师范人学2 0 1l 厢研究生顾十学位论文论文摘要网格计算自从上一世纪九十年代中期出现以来，逐渐被认为是支持广域并行和分布式计算的下一代主流计算平台，可以实现计算、信息、数据、存储、知识等资源的全面共享。网格工作流将工作流管理和网格计算结合起来，提供了一种分布式协作的工作流系统解决方案。目前情况来看，网格技术更注重于研究面向服务技术方面。在工作流执行过程中，服务质量( q o s ) 的应用，促使调度者根据服务质量来选择成员服务，这样网格中的资源可以更好地按照用户的需求来进行组织和分配。网格工作流调度侧重于研究广泛分布的资源及任务调度，直接影响着网格工作流执行的成功率及其效率，可以说是一个非常复杂且具有挑战性的问题。本文通过对网格工作流进行建模并改进其任务调度算法，来提高网格工作流的性能。诸如选择路由、并行路由等多种复杂情况存在于实际工作流中，基于d a g图简单直观的特点，本文选择d a g 建模来表明网格工作流任务调度过程。网格工作流执行过程中的任务或者状态表示为d a g 图的结点，任务之间的时序依赖关系表示为有向弧，而一些属性和参数则表示为弧上的权值。接下来为了解决网格工作流任务调度过程中多目标优化问题，本文提出了多q o s 条件下网格工作流调度模型，定义了多维度的q o s 参数标准体系结构，并对各个参数进行重新定义，重点分析了网格工作流环境下各种不同约束关系的结构中服务质量的计算方式。本文在基于遗传算法( g a ) 和粒子群算法( p s o ) 基础上，提出了遗传粒子群r g a p s o ) 混合算法，引用了特殊的适应度函数，在遗传算法部分设定了动态的交叉和变异概率，并提出了动态切换算法和终止算法的方法，同时也改进了粒子群算法中惯性权重的设置以及对粒子进行离散化。结合各自算法的优势，在算法运行初期利用遗传算法的全局搜索能力进行优化搜索，在后期利用粒子群算法快速收敛能力提高算法的运行速度。本文通过m a t l a b i 具进行仿真，共设计了三组实验。首先为了减少参数的取值对算法性能带来的误差，选取不同的混合算法切换系数s ，根据它们在相同的初始种群数量范围内末代种群平均适应度值变化情况，来选择最优的s 值；然后在一个具体的工作流实例中求解满足服务质量的最优解，证明通过改进的g a p s o 混合调度算法求解的最优解满足该工作流实例中不同用户对服务质量的要求，符合计算网格工作流中的复杂环境；最后比较了应用于网格工作流任务优化调度的改进的g a p s o 算法和其它调度算法在不同服务个数情况下，寻找到最华东师范人学2 0 1l 届研究生硕 j 学位论文优解时算法的执行时间，证明了混合算法的优越性。实验结果表明本文提出的改进的g a p s o 混合算法在网格工作流调度方面具有更高的效率，能更有效地解决网格工作流调度问题。关键词：遗传算法，粒子群算法，网格工作流，q o s ，仿真i i华东师范大学2 0 1 1 届研究生硕i ：学位论文a b s t r a c tg r i dc o m p u t i n gh a sb e e nr e c o g n i z e da st h en e x tm a j o rc o m p u t i n gp l a t f o r mf o rw i d e - a r e ap a r a l l e la n dd i s t r i b u t e dc o m p u t i n gs i n c et h em i dn i n e t i e so ft h el a s tc e n t u r y ,y o uc a na c h i e v ef u l ls h a r ef o rc o m p u t i n g ，i n f o r m a t i o n ，d a t a ，s t o r a g e ，k n o w l e d g ea n do t h e rr e s o u r c e s t h ec o m b i n a t i o no fg r i dc o m p u t i n ga n dw o r k f l o wm a n a g e m e n th a sl e dt ot h ep o w e r f u lc o n c e p to fg r i dw o r k f l o w , w h i c hi sn o wb e c o m i n gt h ed r i v i n gf o r c ef o rt h es o l u t i o n so ft h en e x tg e n e r a t i o no fd i s t r i b u t e da n dc o l l a b o r a t i v ew o r k f l o ws y s t e m i nt h el a s tf e wy e a r s ，t h es e r v i c e - o r i e n t e dt e c h n o l o g yr e s e a r c hh a sb e c a m et h et r e n di ng r i dt e c h n o l o g y t h ei n t r o d u c t i o no fq o si n t og d dw o r k f l o wa l l o w st h eg r i dr e s o u r c e st ob eo r g a n i z e da n dd i s t r i b u t e da c c o r d i n gt ot h eu s e r sr e q u i r e m e n t s d u r i n gt h ee x e c u t i o no ft h ew o r k f l o w , t h es c h e d u l e rc h o o s e sm e m b e rs e r v i c e sb a s e do nq o s c o n c e r n e da b o u tt h el a r g e s c a l er e s o u r c e sa n dt a s k s ，g r i dw o r k f l o ws c h e d u l i n gi so n eo ft h em o s tc o m p l e xa n dc h a l l e n g i n gi s s u e s ，w h i c hd i r e c t l ya f f e c t st h es u c c e s sa n de f f i c i e n c yo fg d dw o r k f l o we x e c u t i o n t h i st h e s i sc o n s i d e r si m p r o v i n gt h eg d dw o r k f l o wp e r f o r m a n c eb yt w oa s p e c t s ：m o d e l i n go f 鲥dw o r k f l o wa n dt h ei m p r o v i n go ft h ea l g o r i t h mo ft h eg r i djo bs c h e d u l i n g m u l t i p l es i t u a t i o n sl i k es e l e c t i o nr o u t ea n dp a r a l l e lr o u t ee x i s ti nt h ep r a c t i c a lw o r k f l o w i nt h et h e s i s ，d a gm o d e l i n gw a su s e dt oi n d i c a t et h ej o bs c h e d u l i n gp r o c e s so fg r i dw o r k f l o wb a s e do ns i m p l e ，i n t u i t i v et r a i to fd a gi nt h ew o r k f l o wb a s e do nd a g , n o d ei n d i c a t e dt h ea c t i v i t yo rs t a t u s ，d i r e c t e da r ci n d i c a t e dt h et i m i n gd e p e n d e n c er e l a t i o n s h i pb e t w e e nn o d e s ，t h ew e i g h to fa r ci n d i c a t e da t t r i b u t e sa n dp a r a m e t e r i no r d e rt or e s o l v et h em u l t i p l eo p t i m i z a t i o np r o b l e mi nt h ej o bs c h e d u l i n gp r o c e s so fg r i dw o r k f l o w , ak i n do fa r c h i t e c t u r eb a s e do nm u l t i p l eq o ss t a n d a r dw a sp r o p o s e d ，t h ep a r a m e t e ro fq o sw a sr e d e f i n e da n da na n a l y s i so fq o sm e a s u r e m e n tw i t hd i f f e r e n tr e s t r a i n tr e l a t i o n s h i ps t r u c t u r ew a sf o c u s e do n b e s i d e st h a t ，ag a p s oh y b r i da l g o r i t h mw a sp r o p o s e db a s e do nt h eg e n e t i ca l g o r i t h m s ( g a ) a n dp a r t i c l es w a r mo p t i m i z a t i o n ( p s o ) w i t h i nt h eh y b r i da l g o r i t h m ，as p e c i a lf i t n e s sf u n c t i o ni sq u o t e d ，c r o s s o v e ra n dm u t a t i o np r o b a b i l i t yi nt h ep a r to fg aa r es e td y n a m i c a l l y ,m e t h o d so fd y n a m i c a l l ys w i t c h i n gb e t w e e na l g o r i t h m sa n dt e r m i n a t i o no ft h ew h o l ea l g o r i t h ma r ep r o p o s e d ，a sw e l la st h es e r i n go fi n e r t i a lw e i g h tw a si m p r o v e da n daw a yo fp a r t i c l ed i s p e r s i o nw a sp r o p o s e di nt h ep s op a r t c o m b i n i n gt h ea d v a n t a g e si l l华东师范大学2 0 1 l 届研究生硕j ：学位论文o ft h et w oa l g o r i t h m s ，t h eh y b r i da l g o r i t h mu s e st h eg l o b a ls e a r c ha b i l i t yo fg at oo p t i m i z et h es e a r c hi nt h eb e g i n n i n g ，a n du s e st h ef a s t s p e e dc o n v e r g e n c ea b i l i t yo fp s ot os p e e du pt h ec o n v e r g e n c er a t ei nt h el a t t e rp a r t i nt h i st h e s i s ，m a t l a bw a su s e dt os i m u l a t e ，a n dt h r e ee x p e r i m e n t sw e r ed e s i g n e d f i r s to fa l l ，i no r d e rt or e d u c et h ee r r o rr e s u l t e df r o mp a r a m e t e rv a l u e ，b a s e do nt h es a m ei n i t i a lg e n e r a t i o np o p u l a t i o n ，d i f f e r e n th y b r i da l g o r i t h ms w i t c hc o e f f i c i e n t sw e r et r i e dt oe v a l u a t et h ea v e r a g ef i t n e s sv a l u eo fl a s tg e n e r a t i o np o p u l a t i o n ，t h e nc h o o s et h eo p t i m a lv a l u e s e c o n d l y , as p e c i f i cg r i dw o r k f l o wc a s ew a sh y p o t h e s i z e da n dt h es o l v i n go ft h eo p t i m a ls o l u t i o nw a sp r o o fo ft h ea l g o r i t h m ，w h i c hw a sb e t t e rt of i tt h ec o m p l e x i t yo ft h eg d de n v i r o n m e n ta n dc o u l dm e e tt h ed i f f e r e n tn e e d sf r o mc u s t o m e r s a tt h el a s t ，c o m p a r e dt oo t h e ra l g o r i t h m sa p p l i e di nt h eg r i dw o r k f l o ws c h e d u l i n g ，w i t ht h es i t u a t i o no fd i f f e r e n ts e r v i c e s ，t h eg a p s oh a st h ea d v a n t a g eo nt i m ee x e c u t i o n t h ee x p e r i m e n tr e s u l t si n d i c a t e dt h eh y b r i da l g o r i t h mh a s t h ea b i l i t yt oa d d r e s s 鲥dw o r k f l o ws c h e d u l i n gp r o b l e mm o r ee f f e c t i v e l ya n de f f i c i e n t l y k e y w o r d s ：g e n e t i ca l g o r i t h m sp a r t i c l es w a r mo p t i m i z a t i o ng r i dw o r k f l o wi v华东师范人学2 0 1l 届研究生硕十= 学位论文第一章绪论。目录1 1研究背景11 2网格工作流研究现状11 2 1 网格工作流规范21 2 2 网格工作流管理项目31 3网格工作流研究中存在的问题以及本文主要工作51 4论文的组织与结构6第二章相关技术背景研究2 1网格概述72 1 1 网格的概念和特点72 1 2 网格体系结构82 1 3 网格调度目标一1 42 1 4 网格任务调度模型和策略1 42 2网格工作流相关技术研究1 72 2 1 传统工作流定义及工作流管理一l72 2 2 网格工作流概述一1 82 2 3 网格工作流与传统工作流区别一1 92 2 4 网格工作流执行过程1 92 2 5 网格工作流研究面临的挑战2 l2 3小结2 2第三章多q o s 条件下网格工作流调度模型的研究2 33 1工作流模型基本概念2 33 2工作流模型建模方式2 33 3网格工作流服务质量( q o s ) 2 53 3 1q o s 概述2 53 3 2q o s 参数2 63 3 3 网格工作流q o s 参数体系2 73 4多q o s 条件下网格工作流调度问题的建模2 83 5，j 、结3 4第四章基于g a p a 0 混合算法的网格工作流调度问题的设计4 1网格工作流调度算法简介3 54 1 1 遗传算法3 64 1 2 粒子群算法4 04 2改进的遗传粒子群混合算法4 2华东师范人学2 0 1 1 届研究生硕1 ：学位论文4 2 1 遗传算法部分4 34 2 2 混合算法切换点的设置4 44 2 3 粒子群算法部分4 54 2 4 混合算法截止条件的设定4 64 3多q o s 条件下的网格工作流混合调度算法流程一4 64 4，j 、结4 8第五章仿真实验。4 95 1仿真环境4 95 1 1 仿真环境4 95 1 2m a t l a b 语寺介绍4 95 2仿真实验和结果分析4 95 2 1 多q o s 条件下网格工作流的一个具体实例一4 95 2 2g a p s o 混合算法参数的设定5 15 2 3 网格工作流具体实例中求解最优值5 25 2 4g a p s o 混合算法与其它调度算法的比较5 35 3小结5 4第六章总结与展望6 1总结5 56 2展埋5 5参考文献攻读学位期间发表的学术论文致谢5 76 2华东师范人学2 0 1l 届研究生硕l j 学位论文1 1研究背景第一章绪论随着人类探索自然活动的深度、广度不断拓展，人们迫切需要功能更强、速度更快的计算机系统，来提高计算的效率和生产力。网格【1 1 就是在这种背景下出现的一种新型网格计算平台，目的是为用户提供各种资源的基础设施的全面共享。网格计算自从上一世纪九十年代中期出现以来，逐渐被认为是支持广域并行和分布式计算的下一代主流计算平台【2 1 。用户可以通过网格使用所需的资源但并不需要了解该资源的具体情况。网格系统并没有很好的方式来有效地构建并处理网格应用，因此网格工作流的概念被提出。工作流是一组并列的( 并行的和或顺序的) 过程行为，这些过程行为为了达到一个共同的业务目标而联系在一起。在网格环境中，资源共享是其中的一个重要实现，并且要对共享资源开展协同工作，达到网格应用自动或者半自动执行的目的，特别是在网格应用的逻辑过程比较复杂并且具有各种优化目标的情况下，网格工作流能够有效地构建、执行和监管这些网格资源，使得网格应用能够高效地自动化执行【3 1 。目前，对于网格工作流的研究受到的关注越来越多，调度问题直接影响着网格工作流执行的成功率及其效率，随之成为其中最重要的问题之一。高效的调度算法能够充分利用网格系统的执行能力，在任务和资源之间做出合理的匹配，使任务能够高效地运行，应用程序的性能也能够随之提高。1 2网格工作流研究现状：目前，对于网格工作流的研究主要包括两个方面的内容【4 1 ，一是相关联盟和研究组织提出的关于网格工作流的建议和规范，另一方面是利用具有工作流特征的服务来构建和管理复杂网格应用或者采用网格工作流作为单独的系统来支持网格应用。华东师范人学2 0 11 届研究生硕i 二学位论文1 2 1 网格工作流规范g s f l ( g r i ds e r v i c e sf l o wl a n g u a g e ) 5 】是基于w s f l ( w e bs e r v i c ef l o wl a n g u a g e ) t 6 1 技术，用于与o g s “7 1 兼容的网格服务组合的流语言。g s f l 尝试通过w s f l 与网格服务( g r i ds e r v i c e s ) t 踟相结合来处理网格服务流程；g s f l 通过把已有的网格服务作为其它网格服务中的组成部分或者直接集成新的网格服务，来描述网格服务之间的交互以及时序关系。图1 1 表明- j g s f l 的大体架构。g s f l 定义n a m e ，t a r g e tn a m e s p a c e ，s c o p e输入模型l i s to fi m p o r t s ：n a m e s p a c e ，l o c a t i o n服务提供程序l i s to fp r o v i d e r s ：n a m e ，t y p e ，l o c a t e r活动模型l i s to fa c t i v i t i e s ：n a m e ，s o u r c e输出模型。组合模型输出的活动a c t i v 时i n f o通知模型控制模型数据模秘c o n t r o ji nd a t a i n d a t a o u tn o t i f i c a t i o nl i n k sc o n t r o ll i n k sd a t al i n k s生命周期模型服务生命周期活动牛命周期p r e c e d e n c el i n k sp r e c e d e n c el i n k s图1 - 1g s f l 的大体架构g w a ( g i r dw o r k f l o wa r c h i t e c t u r e ) 9 1 是一个网格工作流管理系统体系结构，阐述了网格所提供的公共服务和终端服务之间的关系，确定了一套研究网格工作流管理的公共问题以及网格工作流生命周期：w p d ( i 作流过程描述) 的创建，w p d 的验证，w c d ( i 作流实例描述) 的创建以及实例的执行。图1 2 表明了g w a的基础架构。g r i dw o r k f l o w 2 】是关于网格工作流描述语言的推荐规范，由g g f 组织提出。针对网格环境特征，该规范利用x m l 语言的易读性、规范性、工具支持、多种字符集支持以及环境无关性，定义了网格工作流的属性和内容；并定义了具体的词法，例如控制流、工作流、网格输出变量、计算、数据传输、环境参数、软件请求、计算属性、监控等。2华东师范人学2 0 1 l 届研究生硕i ：学位论文w o r k f l o ws e r v i c e 是在o g s a q b 提出的相应服务【】0 j 。工作流服务支持多个应用程序任务在多个分布式网格资源上协调执行，其所提供的构件可用于实现多种高级网格服务。1 2 2 网格工作流管理项目图1 - 2g w a 基础架构在国外，从2 0 0 3 年开始，美国和欧洲相继开展了网格工作流项引4 1 。他们侧重于研究并开发一种高级的抽象方法，用来更加方便、高效地集成复杂的工作流与底层组件和服务。目前来看，比较著名的有g s f l ，i c e n i 1 ，b i o p i p e 1 2 1 ，m y g r i d l l 3 1 ，g r i d f l o w 1 4 1 ，g r i d a n t t l5 1 ，d a g m a n 1 6 】等等。i c e n i 为服务组合提供了基于g u i 的工作流工具，它支持空间组合和时间组合。在工件组合中，组成一个应用的所有组件同时出现，并且带有一些信息来说明它们之间如何相互关联和交互，组件之间没有顺序。在时间组合中，所有租价是按时间相关性排序的。存在的并发性是显式的。每一个组件都附有工作流信息，其包含一个图，图中的有向弧边表示了时间依赖性。i c e n i - i - 作流支持工作流活动的条件、循环和并行执行。b i o p i p e 是一个集群级的工作流框架，主要用于解决有关实现大规模生物信息分析的复杂问题。b i o p i p e 的主要思想是让用户把来自不同地方的数据集成到华东师范人学2 0 1l 届研究生硕士学位论文一个通用的解析框架中。b i o p i p e 用x m l 来定义流水线，其中包括工作流定义、输入输出。它为工作流结构提供了g u i 。m y g r i d 项目的主要目标是开发开源的、高级的、面向服务的中间件。m y g r i d工程为可视化的构造、编辑和浏览工作流提供了一个工作流工作台。工作台包括外部w e b 服务和工作流定义的简单输入，能把工作流直接提交给工作流运行者来执行。运行者将协调工作流中并行和连续的活动的执行，也支持数据迭代和嵌套的工作流。g r i d f l o w 是基于a r m s ( 以种基于代理的资源管理系统) 、t i t a n ( 一种资源调度系统) 和p a c e ( 一种性能预测工具) 的工作流管理系统。g r i d f l o w 的用户门户提供了g u i ，可促进工作流构建的组合和附加服务的访问。网格工作流用x m l 描述，它通过全局工作流管理系统进行语法分析，进行仿真、执行和监控。g r i d f l o w 中的工作流管理可在多个层次上执行：任务调度，使用t i t a n 实现，它集中于管理和调度的子工作流和工作流；子工作流，是和任务密切相关的流，它能以预定义的序列在一个局部集群环境中的资源上执行；工作流，网格应用程序可表现为几个不同活动的流，每一个活动可由一个子工作流表现出来，这些活动是松散耦合的，可能需要多站点的网格资源。g r i d a n t 为映射复杂的客户端工作流提供了支持，但是也作为简单化的客户端来测试不同网格服务的功能。g r i d a n t 帮助网格应用将g t 2 平滑转化为g t 3 。g r i d a n t 本质上包括以下4 个组件：工作流引擎，它是中心控制器，可以处理故障修复、任务依赖性、进程同步和性能分析；运行时环境，提供了一个全局可访的白板风格的通信模型，能集成任意的数据结构，可以被单个的g r i d a n t 任务来读或写，并支持常量、算术表达式等重要的结构；工作流词汇，指定了一套预定义的活动或任务，在此基础上可开发复杂的工作流；工作流监控，g r i d a n t 中的工作流用x m l 指定，x m l 可用任何文本编辑器来编辑，或者可转载到一个可视化工具中来监控工作流中元素的执行。在国内，多个重点高校已经对网格工作流展开一定的研究，并在其基础架构、描述语言以及资源的分配与调度等方面取得了一些成果【4 】。如清华大学、同济大学、浙江大学、香港大学等9 所著名高校联合进行的“网格工作流过程的语义分析与验证理论研究”项目；复旦大学的“支持输入反馈和健壮性增强的网格工作流自动生成”项目；武汉大学进行的在o g s i ( o p e ng r i ds e r v i c ei n f r a s t r u c t u r e ) 下网格工作流描述语言的研究；华中科技大学的“基于服务的网格工作流应用开发”项目；4华东师范大学2 0 1 1 届研究生硕l = 学位论文国防科技大学在进行的“多域环境下网格工作流语言和机制的研究项目”等。1 3网格工作流研究中存在的问题以及本文主要工作从网格工作流研究现状来看，虽然在国际和国内上已经取得了很大的进展，但是对于网格来说，工作流系统的本质是十分复杂的，因此也就面临着许多挑战，在以下方面存在着有待解决的问题【4 】：( 1 ) 网格工作流建模方面。网格工作流模型是通过某种建模方式对网格应用进行分析并抽象，以达到使网格工作流更好地支持网格应用的目的。这种抽象一般侧重于对网格应用所处的组织环境、处理过程以及所需资源进行建模，从而得到相应的网格工作流组织模型、过程模型和资源模型。网格工作流调度侧重于研究海量数据处理及任务调度，但对关联应用的关注过少，也并没有提供适当的建模和验证工具，针对网格工作流动态、异构、日益复杂的执行环境，网格工作流项目的设计和实施受到了很大的阻碍。r( 2 ) 网格工作流执行问题。判断网格工作流系统能否成功地执行某一个特定的网格工作流应用，不仅依赖于工作流设计是否合理，还需要解决工作流的调度问题，保证工作流的执行性能。网格工作流调度问题关注于网格工作流的资鬈源管理，影响着网格工作流执行的成功率和效率。近年来有关工作流调度算法的研究文献很多，侧重点和考虑的角度各有不同，多数算法尚处于理论探索阶段。另外实际网格工作流的调度任务之间一般有时序或因果关系，但大部分算法侧重于调度任务之间没有关联的情况。在这一方面，还需要进行更深入的研究。( 3 ) 网格工作流的验证和优化。通常要结合业务建模方式和具体应用特点来完成，可以通过引入规划方法和知识工程中的一些技术来完成。传统工作流的一些方法和技术并不适应网格的分布性、动态性、自治性和异构性，也就不能处理网格环境中的相关问题，本文结合网格资源和网格应用的特点，主要研究内容和贡献如下：( 1 ) 网格工作流的研究：主要研究了网格工作流的基本过程以及该领域的关键问题；( 2 ) 建模方式的选择。诸如选择路由、并行路由等多种情况存在于实际工作流中，基于d a g 图简单直观的特点，本文中网格工作流任务调度过程用d a g 建模来表示。网格工作流执行过程中的任务或者状态表示为d a g 图的结点，任务之间华东师范人学2 0 1l 届研究生硕一 ：学位论文的时序依赖关系表示为有向弧，而一些属性和参数则表示为弧上的权值。( 3 ) 为解决网格工作流任务调度过程中多目标优化问题，提出了多q o s 条件下网格工作流调度模型，定义了多维度的q o s 参数标准，并对各个参数进行重新定义，重点分析了网格工作流中各种不同约束关系的结构中服务质量计算方式。( 4 ) 适用于网格工作流调度问题的算法的改进。在遗传算法和粒了群算法基础上提出了两者的混合算法，主要在以下方面改进：适应度函数的设置；遗传算法中使用动态的交叉、变异概率进行操作；粒了群算法的参数惯性权重的改进、粒了的离散化；混合算法切换点的设置；算法终止条件的设置。( 5 ) 仿真和实验分析，证明算法的优越性。首先为了减少参数的取值对算法性能带来的误差，选取不同的混合算法切换系数s ，根据它们在相同的初始种群数量范围内末代种群平均适应度值变化情况，来选择最优的s 值；然后在一个具体的工作流实例中通过改进的g a p s o 混合调度算法求解的最优解满足该工作流实例中不同用户对服务质量的要求，符合网格计工作流的复杂环境；最后验证了在不同服务个数范围内，应用于网格工作流任务调度的改进的g a p s o 算法相对于其它调度算法，执行时间更短。1 4论文的组织与结构本论文共分为六个章节，具体章节安排如下：第一章总体介绍选题背景，分析了网格工作流研究现状以及所面临的问题以及本文主要工作。第二章对与本文所研究领域相关的文献资料进行了总结。第三章提出了网格工作流任务调度模型。重点分析了多q o s 条件下，网格工作流任务调度问题。第四章提出了一个基于遗传算法和粒子群算法的混合算法，并进行改进，应用到第三章所建立的模型中。第五章通过仿真实验选择合适的参数，求解多目标优化的最优值，并将本文提出的算法与基本算法进行对比，证明本文所提出算法的优越性。第六章论文总结以及应用前景展望。对全文进行了总结，并结合目前的研究情况和网格的发展趋势，提出了进一步的研究工作和方向。华东师范人学2 0 1 l 屈研究生硕 ：学位论文2 1网格概述第二章相关技术背景研究2 1 1 网格的概念和特点网格是一类基础设施，可以集成地理位置上分散的资源。用户可以通过网格使用所需的资源但并不需要了解该资源的具体情况。网格的物理基础包括通信网络以及分布式资源，而资源又包括计算机、集群、计算机池、仪器设备、传感器、存储设备等实体以及这些实体工作时所需的数据和软件。目前网格研究还不够成熟，对于网格概念还没有达成统一。早期的网格用来互联美国各个实验室和大学之间的高性能设备，i a nf o s t e r 和c a r lk e s s e l m a n 于1 9 9 8 年在他们编著的书中将该网格定义如下：计算网格是一个提供可靠的、一致的、无所不在的、便宜的硬件和软件基础结构，用来进行高端计算f l 丌。2 0 0 1 年，l a nf o s t e r 等人再一次定义网格为：协作资源共享，在动态的多机构的虚拟结构中解决问题【18 1 。i b m 从商业角度把网格定义为：基于标准的应用资源共享结构，使得它能够透明地为异构系统和应用去共享、计算和存储资源【l9 1 。从这些定义能够看出网格最重要的功能为实现资源共享，而共享总是与条件和基本因素相关联，并需要考虑很多方面，比如信任、基于资源的策略以及支付方式等。同时网格也需要解决在简单的客户服务器模式上的各种问题，例如分布式数据分析的综合、计算和协作。从网格的概念可以总结出，网格是一个在地理位置上广泛分布的基础发施，资源千差万别，应用功能繁多，用户数量巨大，需求种类各异。网格要给用户、资源提供畅通的渠道，以及安全、高效、高质量的服务，必须具备如下基本特点：( 1 ) 分布与共享网格的分布性也就是网格资源和计算的分布性。在网格这一分布式环境下，需要解决任务与资源之间的调度问题、人与系统以及人与人之间的交互问题、突发性保障问题、安全传输与通信问题等等。网格资源虽然是分布的，但是它们却是可以充分共享的。网格是一个提供资源共享的场所，用户可以共享使用其中的各种资源。不仅网格中的多个资源能被一个用户同时使用，并且一个资源也能够被多个网格用户同时使用。( 2 ) 虚拟性网格资源对外提供的只是一个虚拟化的结构，网格用户与物理资源之间是相7华东师范火学2 0 1l 届研究生硕j ：学位论文互看不见的。只要通过标准、通用、开放的协议及界面，网格用户就可以访问网格资源。这就要求虚拟化网格中的资源和用户，并把实际的资源和用户抽象为网格资源和用户。( 3 ) 自治性与协商性网格的自治性是指网格自主的管理能力。大多数情况下网格系统的资源所属的组织或机构各异，这时网格资源拥有者对其资源具有最大管理权限。同时网格也支持资源的协商利用，请求者和提供者通过协商建立特殊的服务通道来提供专用的服务。通过协商，资源请求者和提供者也可以获取不同质量的服务来满足不| 一用户的需求。这样系统的整体功能将大于其各个组成部分的功能之和。( 4 ) 动态性和多样性网格的整体结构经常因为网格的分布性和其系统的复杂性而发生变化，所以网格资源必须能够动态的增加和减少。网格资源是异构和多样的，在网格环境中存在的计算机系统和资源种类各异、结构千差万别，因此网格系统必须要具备解决这些异构多样资源之间的通信和互操作的能力。2 1 2 网格体系结构网格体系结构一直以来都是网格研究的热点，是网格的架构和核心。网格体系结构重点研究如何构建网格，它指出了网格中各组成部分之间的关系和整合方式、网格的基本构成和功能以及网格的有效运行机制。目前情况来看，主流网格体系结构有三种：一是五层沙漏结构【l8 1 ，i 主t f o s t e r 在2 0 0 1 年提出；二是f o s t e r 等人在i b m 为代表的工业界的影响下，在对w e b 技术的发展与影响考虑之后，结合了w e bs e r v i c e s 提出的开放网格服务结构o g s a 及其最初的基础设施o g s i ( o p e ng r i ds e r v i c e sa r c h i t e c t u r e ) ；三是w e b l 艮务资源框架( w s w ，w e bs e r v i c e sr e s o u r c ef r a m e w o r k ) t 2 0 1 ，2 0 0 4 年初i 由g l o b u s 联盟、i b m 和h p 共同提出，它同样是基于o g s a框架的。1 五层沙漏结构五层沙漏结构是一种影响十分广泛的机构，该结构最重要的思想就是以“协议”为中心，也十分强调服务与a p i 和s d k 的重要性，不过该结构主要侧重于定性的描述而不是具体的协议定义。五层沙漏结构中每个层次所包含的对共享资源进行使用、操作和管理的功能不同，其根据各部分与共享资源之间的距离远近来分层。下层部分与物理的共享华东师范人学2 0 1l 届研究生硕十学位论文资源关系更贴近，更相关于特定资源；上层部分就逐渐感觉不到共享资源的细节特征。五层沙漏结构中各部分的协议数量并不相同，其中核心协议发挥着巨大作用，在所有支持网格计算的地点都应该得到支持，既要实现上层各种协议向核心协议的映射，又要实现核心协议向下层各种协议的映射。所以核一t l , 协议的数量要控制在一定的范围之内，但同时这个限制对于层次结构来说就成为了一个劣势。五层沙漏结构最底层为构造层，接着为连接层，然后为资源层、汇聚层，最后为应用层，图2 1 更清晰地展示了网格的五层沙漏结构模型。图2 1五层沙漏结构模型( 1 ) 构造层把本地资源与上层结构连接起来，其提供的统一接i s l 可用于上层结构访问本地资源，并消除资源的异构性，通过管理具体资源，进而向上层提供对这些资源的管理界面；( 2 ) 连接层定义了一些通信和认证协议以及加密的安全机制，分别用于核心网格事务处理以及用户和资源的识别。( 3 ) 资源层协议通过调用构造层的功能来实现对本地资源的访问和控制，反映了局部资源的抽象特征；( 4 ) 汇聚层主要是处理大量资源之间的协调问题；( 5 ) 应用层通过某一层次定义的服务所构造，存在于虚拟组织中。每一层的a p i都可以理解为与特定服务交换协议信息的结果，并且应用可以调用高层次的a p i 库及框架。2 开放服务网格体系结构o g s a 及其o g s i9华东师范人学2 0 1 1 届研究生硕上学位论文图2 2面i 右j o g s i 的开放网格服务网格体系结构o g s a( 1 ) 资源层。资源包括物理资源和逻辑资源，其概念无论对于网格计算还是o g s a来说都是十分重要的。物理资源包括网络、服务器和存储器，为了实现更广泛的功能，逻辑资源聚合物理层的资源并使用了虚拟化技术。( 2 ) w e b e 务以及对网格服务的o g s i 扩展的定义。对网格资源建模离不开w e b服务，因此o g s i 对w e b 服务的定义作了更深入的补充，提供了有状态的、动态的和可管理的w e b 服务的能力。( 3 ) 基于o g s a 架构的服务。一些基础设施，如基于架构的网格服务由w e b 服务层及其o g s i 扩展向下一层提供。o g s a 将随着这些新架构服务的出现，在可用性、面向服务方面作进一步提高。( 4 ) 网格应用程序。o g s a 架构的最高层由一些应用程序构成。而这些应用程序是基于一个或者多个网格架构服务。随着时代的发展，研究人员开发了越来越多的服务来支持网格架构。o g s a 最突出的思想就是以“服务”为中心。网格环境中的所有资源，包括计算机、仪器设备、程序、数据等在o g s a 中都被理解为服务。在这种前提下，管理和使用网格就可以通过统一的标准接口来实现。o g s a