（计算机科学与技术专业论文）基于资源可靠性的移动网格任务调度研究.pdf

武汉理工人学硕士学位论文 摘要 移动网格的产生得益于网格计算和移动计算技术的迅猛发展，它继承了传 统网格的特性，能够为网格用户提供多样化、可靠的网格服务。同时，移动网 格加入了对移动设备的支持，不仅可以使用它们访问网格资源，而且也能够利 用移动设备为用户提供网格服务。移动设备存在一些共性，如移动性、能量受 限和网络连接不稳定等。它们加入到网格中之后也带来一系列的问题，尤其是 增加了网格资源管理的难度，任务调度作为资源资源管理的核心部分也面临极 大的挑战。 网格任务调度的过程实际是完成任务到资源的映射，不仅要保证用户的需 求，而且要能够合理的使用资源。在任务调度过程中，如何选择恰当的资源是 一个十分关键和困难的问题，在移动网格中也是同样如此。因为移动网格中资 源多数为移动设备，它们在多方面都受到了限制。如何权衡一个资源的可靠性 就成了一个重要的问题了。对于移动网格任务调度的相关研究主要集中在移动 性、能量消耗和间断性网络连接等几个方面。现有的任务调度算法都是从某一 个方面考查资源，很少会考查资源多方面的约束。本文定义了资源可靠性并结 合用户移动性，综合多方面的因素为用户筛选合适的网格资源，提出一种基于 资源可靠性的移动网格任务调度算法。 本文的主要研究工作及创新性体现在以下几个方面： 1 、分析移动网格中资源管理的特点以及任务调度过程出现的问题。根据移 动网格中节点运动规律建立一个简单的移动模型，用此模型确定任务提交者可 能停留的网格区域，从而能够就近选择资源执行任务，减少网络延时。 2 、针对网络连接不稳定问题，提出一种计算资源断网时间的方法，从而能 够确定资源完成任务的时间。根据任务的执行过程，计算资源执行任务时的能 量消耗。从任务完成时间和能量消耗两方面定义资源的可靠性概念，并给出计 算资源的可靠性的方法。在计算资源可靠性时，把任务分为紧急任务和非紧急 任务，采用不同的参数计算可靠性，使之符合实际的调度环境。 3 、结合节点移动模型和资源可靠性提出一种基于资源可靠性的任务调度算 法。此算法首先根据节点移动模型确定任务提交者停留的网格区域，然后根据 资源的可靠性从该网格中选取最可靠的资源执行任务，算法的目标是最大限度 的保证任务能够被成功的执行。 武汉理上人学硕+ 学位论文 4 、对本文提出的调度算法进行仿真实验，并与已有的算法进行对比实验。 实验结果表明本文提出的基于资源可靠性的任务调度算法具有较好的性能，能 够保证较高的任务执行成功率和资源利用率。 本论文得到了国家自然科学基金( 批准号：6 0 9 7 0 0 6 4 ，6 0 7 7 3 2 1 1 ) ，湖北省 杰出青年人才基金( 批准号：2 0 0 8 c d b 3 3 5 ) ，教育部新世纪优秀人才支持计划( 批 准号：n c e t 一0 8 一0 8 0 6 ) ，国家软件开发环境重点实验室开放基金课题( 批准号： s k l s d e 一2 0 0 9 k f 一2 0 2 ) ，霍英东高校青年教师基金基础性研究课题( 批准号： 1 2 1 0 6 7 ) 及武汉市科技攻关项目( 批准号：2 0 1 0 1 0 6 2 1 2 0 7 ) 的资助。 关键词：移动网格，任务调度，移动性，资源可靠性，n s 2 n 武汉理f 大学硕七学位论文 a b s t r a c t m o b i l eg r i di sd u et 0t h er a p i dd e v e l o p m e mo fg r i dc o m p m i n ga i l dm o b i l e c o m p u t i n gt e c l l i l o l o 阱i ti sa 向l li n h e i l i t o ro ft r a d i t i o n a l 嘶dt h a tc a l lp r o v i d ev a r i o u s r e l i a b l e 铲i ds e n ，e r sf o r 酊du s e r s m e a l l w r h i l e ，m o b i l e 黟i dc a i ls u p p o r tt h em o b i l e d e v i c e s ，w h i c hc a nb et r e a t e da s 鲥di n t e r f a c eo rg r i dr e s o u r c e m o b i l ed e v i c e sh a v e s o m ec o m m o nc h a r a c t e r i s t i c s ，s u c ha s m o b i l i 劬l i m i t e de n e 玛ya 1 1 di n t e m i t t e n t n e 铆o r kc o 肌e c t i o n sa i l ds oo n ，w h i c hi n t r o d u c es o m ep r o b l e m si n t om o b i l e 鲥d sa n d e s p e c i a l l ym a k et t l e 鲥dr e s o u r c em a n a g e m e n tt ob em o r ec o m p l e x t h et a s k s c h e d u l i n gt h a ti st h ec o r eo fr e s o u r c em a l l a g e m e n tf a c e s 黟e a tc h a l l e n g e s t h e 研dt a s ks c h e d u l i n gi sa c t u a l l yt h ep r o c e s so fm 印p i n gm a n yt a s k st om a n y r e s o u r c e s ，w h i c hs h o u l dn o to n l ys a t i s 矽t h eu s e r s ，b u ta l s oe n s u r et h er e s o u r c e u t i l i z a t i o n i ts e e m st ob eac r i t i c a la i l dd i m c u l ti s s u et os e l e c tag o o dr e s o u r c ef o r t h e t a s ki nt h em o b i l e 西d b e c a u s et h er e s o u r c e si nm o b i l eg r i da r em o s t l yt h em o b i l e d e v i c e s ，m e ya r el i m i t e di nm a r l y 弱p e c t s i tb e c o m e sa ni m p o r t a n ti s s u et h a th o wt o 、i 曲t h er e s o u r c er e l i a b i l i 够a tp r e s e n t ，t h er e s e a r c h e so fm o b i l e 妤dt a s k s c h e d u l i n gm a i l l l yf o c u so nm o b i l i 吼e i l e 玛yc o n s u i i l p t i o na i l di n t e m l i t t e n tn e t 、o r k c o n n e c t i o n s 1 1 1 ee x i s t i n gs c h e d u l i n ga l g o r i t sm o s t l yp a ya n e n t i o nt oo n ea s p e c to f r e s o u r c e i nt h i st h e s i s ，、) l ，ed e f i n et l l er e s o u r c er e l i a b i l i t y 锄dp r o p o s et h em o b i l e 鲥d t a s ks c h e d u l i n ga l g o r i t h mb a s e do nr e s o u r c er e l ia _ b i l i t y ，w h i c ha l s oi n v o l v e st l l eu s e r m o b i l i 够 7 n l el e a d i n gr e s e a r c ha i l di m l 0 v a t i o no fm i st h e s i sa r e 雒f o l l o w ： f i r s t l y “锄a l y z e st l l ec h a r a c t e r i s t i c so fm o b i l e 西dr e s o u r c em a n a g e m e n t 锄d t l l ec h a l l e n 舀n gi s s u ei nt a s ks c h e d u l i n g as i m p l en o d em o b i l em o d e li sp m p o s e d b a s e do nt i l em l eo fn o d em o b i l i 吼w h i c hc 锄b eu s e dt od e c i d ew h e r et 1 1 eu s e r 谢n g o t h e nt l l en e a r b yr e s o u r c e sw i l lb es e l e c t e dt op r o c e s st h et a s ki l lo r d e rt or e d u c i n g 圮玳婀旧r k d e l a y s e c o n d l y ，i tp r o v i d e sam e t l l o dt 0c o m p u t et h ed i s c o m l e c t i o nt i m e ，s ot h et a s k c o m p l e t i o nt i i l l ec a nb ei d e n t i f i e d a c c o r d i n gt ot 1 1 et a s ki m p l e m e m a t i o n ，m ee n e 唱y c o i l s u m p t i o ni sc a l c u l a t e d t h er e s o u r c er e l i a b i l i 锣i si nr e l e v a i l c et 0b o t l lt 嬲k c o m p l e t i o nt i i n ea i l dr e s o u r c ee n e r g yc o n s u j n p t i o n i i lt l l i st 1 1 e s i s ，t ：h et 硒k sa r ed i v i d e d n i 武汉理工人学硕士学位论文 i n t ou 玛e n tt a s ka n dn o r m a lt a s k ，w h i c ha d o p td i f r e r e n tm e t h o d st oc a l c u l a t et h e r e s o u r c er e l i a b i l i 吼 t h i r d l y ；t h i st h e s i sp r o p o s e sam o b i l eg r i dt a s ks c h e d u l i n ga l g o r i t h mb a s e do n t h er e s o u r c er e l i a b i l i t y n l e p r o p o s e da l g o r i t h mi n v o l v e sb o t hu s e rm o b i l i t ) ra i l d r e s o u r c er e l i a b i l i 哆n 丘r s u yd e t e m i n e st h e 鲥da r e ao fu s e ra c c o r d i n gt ot h em o b i l i t y m o d e l ，a i l dm e ns e l e c t st h em o s tr e l i a b l er e s o u r c ei nm eu s e rg r i df o rt a s k s t h e a l g o r i t h ma i m st oe n s u r et h a tt h et a s k sw i l lb ep r o c e s ss u c c e s s 如l l y l a s t l y ，m ep r o p o s e da l g o r i t h mi ss i m u l a t e di nm o b i l e 鲥de n v i r 0 i l i l l e ma n di s c o m p a r e dw i t ha i le x i s t i n gs c h e d u l i n ga l g o r i t h m t h es i m u l a t i o ns u g g e s t st h a tt h e p r o p o s e da l g o r i t h mh a sg o o dp e 墒r m a n c e 锄di ss u i t a b l ef o rt h em o b i l eg r i dt a s k s c h e d u l i n g 7 m st h e s i si ss u p p o n e db yn a t i o n a ln a t u 同s c i e n c ef o u n d a t i o no fc h i m ( n s f ) u r l d e rg r a i l t ( n o 6 0 7 7 3 21 1 ，n o 6 0 9 7 0 0 6 4 ) 、n a t u r a ls c i e n c ef o u n d a t i o no fh u b e i p r o v i n c em l d e r ( 融( n o 2 0 0 8 c d b 3 3 5 ) 、p r o 掣锄f o rn e wc e n t u r ye x c e l l e n t 1 a l e n t si nu n i v e r s i t y ，c h i n au n d e r 铲a n t ( n c e t - 0 8 - 0 8 0 6 ) 、o p e nf u l l do ft h es t a t e k b yl a b o r a t o r ) ro fs o 脚a r ed e v e l o p m e me n v i r 0 衄e n t ( n o ：s k l s d e 一2 0 0 9 k f - 2 - 0 2 ) 、f o k n g - t 0 n ge d u c a t i o nf o u n d a t i o nf o ry 曲n gt e a c h e r s i nh i 曲e r e d u c a t i o ni n s t i t u t i o i l so fc h i n a( n o ：1 2l0 6 7 )a i l d m u m c i p a l i t ) r s c i e n c ea 1 1 d t e c l l i l o l o g yi nt h ew u i l a i lo 虢n d sp a s si t e m ( n o ：2 0 1 0 1 0 6 2 1 2 0 7 ) k e y w o r d s ：m o b i l eg r i d ，t a s ks c h e d u l i n g ，m o b i l i 饥r i e s o u r c e r e l i a b i l i 何n s 2 独创性声明 本人声明，所呈交的论文是本人在导师指导下进行的研究工作及 取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得 武汉理工大学或其它教育机构的学位或证书而使用过的材料。与我一 同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说 明并表示了谢意。 签名：堑l 盘日期：塑l 鱼：2 壑 学位论文使用授权书 本人完全了解武汉理工大学有关保留、使用学位论文的规定，即： 学校有权保留并向国家有关部门或机构送交论文的复印件和电子版， 允许论文被查阅和借阅。本人授权武汉理工大学可以将本学位论文的 全部内容编入有关数据库进行检索，可以采用影印、缩印或其他复制 手段保存或汇编本学位论文。同时授权经武汉理工大学认可的国家有 关机构或论文数据库使用或收录本学位论文，并向社会公众提供信息 服务。 ( 保密的论文在解密后应遵守此规定) 研究生c 签名) 奏1 磊导师( 签名) 笏杯日期叭s 武汉理ji ：人学硕士学位论文 第1 章绪论 1 1 本课题的来源及研究意义 在移动网格( m o b i l e 嘶d ) 中，移动设备不仅能够访问有线网格资源，而且也 能够充当网格资源，为用户提供网格服务。虽然移动设备的种类繁多( 如p d a 、 智能手机和l a p t o p 等) ，但是它们都具备一些共同的特性：移动性、有限的能量 和不稳定的网络连接等。移动设备的这些特性，特别是在它们充当网格资源时 将会给网格任务调度带来新的挑战，因为它们相对于固定网格中的资源是不可 靠的。在任务调度过程中，需要从多个方面去权衡一个资源的可靠性( r e s o u r c e i 沁l i a b i l i t y ) 。 移动网格中的资源和用户都可以由移动设备构成，它们之问采用的是不稳 定的无线连接，这将使移动设备与网格系统的连接呈现间断性。因此在计算任 务完成时间时，首先就要确定由于网络断连所造成的网格延时，从而才能得到 较为准确的任务完成时间。再者，移动设备可以随处移动，如果能够确定移动 设备的活动区域，将有利于通信的稳定性，减少网络延时。对于移动设备能量 消耗也是一个值得关注的问题。由于移动设备是由电池提供电能，它们不可能 使设备长时间的处于电力充沛的状态。一旦移动设备失去电能，它将与网格系 统断开连接终止它正在进行的工作。因此在任务调度中，就需要计算移动设备 的能量消耗从而能够选择具备足够能量的资源执行任务。 在进行任务调度时，如果出现资源的能量不足或者网络连接断开这都将会 对调度产生影响。但要完全避免上述情况也是不可能的，这是由移动网格的特 性所决定。因此，我们应该设法把不利的因素所带来的影响降到最低程度，保 证任务能够被顺利完成。本课题所研究的内容正是基于这一点考虑，试图找出 最可靠的资源去执行网格任务。 本文主要从两个方面去衡量资源的可靠性( r e s o u r c er e i i a b i l 时) ： 一是资源执行任务所需要的时间。由于移动设备的连接呈现间断性，等待 网络连接会产生延时，这将会增加任务的完成时间。由于不同的资源网络连接 状况也是不一样的，在任务调度中要尽可能的把任务分配到执行速度较快的资 源上，保证任务能够在规定期限内被完成。 武汉理工大学硕士学位论文 二是资源执行任务过程中的能量消耗。在把任务分配给资源之前，首先要 确保资源是具备足够的能量。其次，要选择那些消耗能量较少的资源，使整个 网格系统的能量消耗较少。 本文中提出的资源可靠性( r e s o u r c er e l i a b i l i t ) r ) 概念是根据资源执行任务的 时间和能量消耗进行衡量。另外，针对不同类型的网格任务，计算资源可靠性 的方法是不同的。在任务调度过程中，调度者应该选择消耗能量少而且任务完 成时间较短的资源去执行任务，减小任务执行失败的几率。不仅能够节省移动 网格中的节点的能量使网格节点能够有更长的生命周期，而且能够缩短任务完 成时间。 本论文得到了国家自然科学基金( 批准号：6 0 9 7 0 0 6 4 ) ，国家自然科学基金 ( 批准号：6 0 7 7 3 2 1 1 ) ，湖北省杰出青年人才基金( 批准号：2 0 0 8 c d b 3 3 5 ) ，教 育部新世纪优秀人才支持计划( 批准号：n c e t - 0 8 0 8 0 6 ) ，国家软件开发环境重点 实验室开放基金课题( 批准号：s k l s d e 2 0 0 9 k f 2 0 2 ) ，霍英东高校青年教师基金 基础性研究课题( 批准号：1 2 1 0 6 7 ) 及武汉市科技攻关项目( 批准号：2 0 1 0 1 0 6 2 1 2 0 7 ) 的资助。 1 2 移动网格背景知识 1 2 1 移动网格简介 网格计算( g r i dc o m p u t i n g ) 是把分布在计算机网络上众多的计算资源、 存储资源、硬软件资源、信息资源等整合成一个逻辑整体，构成一台“超级计 算机 为网格用户提供可靠的信息应用服务。近年来，随着无线技术和移动技 术的进步，出现了各式各样的移动设备，如智能手机、p d a 和l a p t o p 等，而且 它们的数量相当可观，同时也能够提供一定的计算能力。移动设备在某种程度 上能够满足网格系统对计算能力的需求，因此它们也正在被纳入到网格系统中 成为网格的组成部分。 移动网格在继承传统网格计算的基础上也融入了一些新的特性，它以一种 无缝、透明、安全和高效的方式来支持移动用户和移动资源【2 】。在由固定设备所 组成的传统网格中，加入对移动设备的支持就可以构成一个移动网格。移动网 格包括了移动的网格资源和用户和固定的网格资源和用户，移动用户可与网格 资源进行动态连接，实现对网格资源透明、无缝、分布式的访问。另外，移动 2 武汉理工人学硕士学位论文 设备的加入也给网格计算带来了不少的挑战。在移动网格中将要采用新的策略 满足网格用户新的需求，例如在间断网络连接下的互操作问题以及移动设备的 能量消耗和移动性问题等。 移动设备在移动网格中可以扮演两种角色：一是作为访问网格资源的接口 ( g r i di n t e r f a c e ) ；二是作为网格资源( g r i dr e s o u r c e ) 。前者是利用移动设备去访问 固定的网格资源；而后者则是把移动设备自身作为网格资源为其他用户提供网 格服务。由于移动网格中的用户和资源不同于传统网格，它们具备一些新的特 性( 移动性、能量有限和不稳定网络连接等) 使得移动网格的资源管理将更加 复杂化，特别是移动网格任务调度将面临更多的挑战。 1 2 2 相关技术介绍 移动网格是网格技术与移动计算技术的结合体，为了更好的理解移动网格， 下面简要对相关的技术作一个介绍。 ( 1 ) 移动计算( m o b i l ec o m p u t i n g ) 移动计算【3 j 主要是针对小型便携式设备的无线计算和通信的应用。移动计算 是一个通用的术语，描述了小型便携式设备在无线计算和通讯方面的应用。这 些设备主要包括采用无线局域网( w l a n ) 的l a p t o p ，移动电话以及使用蓝牙 或红外连接的个人数字助理( p d a ) 等。移动计算强调的是在任何地点任何时 问通过适当的方式都能够访问到所需的信息和服务。但是，要实现这一点并不 那么容易，它需要对更改现有的通信方式，同时对计算机网络、操作系统和应 用程序作相应的修改。移动性虽然带来了便利，同时也对移动资源造成了多方 面的制约。实际上，移动网格的出现也利益于移动计算技术的发展。 ( 2 ) 分布式计算( d i s t r i b u t e dc o m p u t i n g ) 分布式计算是人们提出的一种新的计算模式，它就是在两个或多个软件上 共享信息，这些软件既可以在同一台计算机上运行，也分布在网络上的多台计 算机上。分布式计算与其它计算方式相比而言具有以下优势：一是稀有资源可 以共享；二是可以在多台计算机上平衡计算负载；三是可以把程序放在最适合 运行它的计算机上。分布式计算的核心体现在前两点上。网格计算实际上也属 于分布式计算，它的实质就是组合与共享资源并确保系统安全。 ( 3 ) 普适计算( p e r v a s i v e 舢b i q u i t o u sc o m p u t i n g ) 普适计算指的是无所不在的、随时随地可以进行计算的一种方式，无论何 3 武汉理1 ：人学硕士学位论文 时何地，只要需要，就可以通过某种设备访问到所需的信息f 4 l 。普适计算所涉及 的技术很多，如移动通信技术、小型计算设备制造技术、小型计算设备上的操 作系统技术等。普适计算技术在现在的软件技术中将占据着越来越重要的位置， 其主要应用方向有三个：一是嵌入式技术( 除笔记本电脑和台式电脑外的具有 c p u 能进行一定的数据计算的电器如手机，m p 3 等) ；二是网络连接技术( 包 括3 g ，a d s l 等网络连接技术) ；三是基于w e b 的软件服务构架( 通过传统的 b s 构架提供各种服务) 。网络连接的问断性与轻量计算( 即计算资源相对有限) 是普适计算最重要的两个特征。把网格技术和普适计算结合起来，就产生了一 种新的计算模式，即普适网格( p e f v a s i v eg r i d ) i 列。 ( 4 ) 云计算( c l o u dc o m p u t i n g ) 云计算是一种商业计算模型，它将计算任务分布在大量计算机构成的资源 池上，使各种应用系统能够根据需要获取计算力、存储空间和各种软件服纠6 | 。 云计算是并行计算( p a r a l l e lc o m p u t i n g ) 、分布式计算( d i s t 曲u t e dc o m p u t i n g ) 和网 格计算( g r i dc o m p u t i n g ) 的发展，或者说是这些计算机科学概念的商业实现。在 动态变化、由多个机构组成的虚拟组织中协调资源共享和求解问题。云计算与 网格计算有相同之处，但是也存在许多不同点。表1 1 给出二者的异同点。 表1 1 网格计算与云计算比较 网格计算云计算 异构资源同构资源 不同机构单一机构 虚拟组织虚拟机 科学计算为主数据处理为主 高性能计算机服务器尸c 紧耦合问题 松耦合问题 标准化尚无标准 科学界商业社会 1 3 移动网格研究的现状 网格技术的研究始于9 0 年代初期，研究内容是关于干兆网试验床以及一些 4 武汉理1 ：人学硕士学位论文 元计算方面的工作【。在9 0 中晚期，研究者作了一些早期的试验，得出一些比 较重要的开创性和奠基性的研究成果。9 0 年代晚期，美国的阿贡实验室酋次提 出了计算机网格的概念【8 j 。从9 0 年代晚期至今，网格计算得到了迅速发展，同 时也得到了很多研究者的重视。在这段时期，出现了大量与网格研究、丌发和 应用相关的项目和组织，如全球网格论坛g g f 。同时，网格计算也不局限于科 学研究，逐步在各个领域中得到了推广。移动通信技术是近几年通信各领域中 发展最快的领域之一，同时移动设备的相关技术也得到了飞速的发展，出现了 各式各样的移动设备，这些移动资源数量非常巨大并呈现上升趋势。随着网格 技术和移动计算技术的发展出现了移动网格，它在继承传统网格计算的同时加 入了对移动用户和移动资源的支持。 1 3 1 国内外研究项目 在国内，有一些高校已经参与了有关移动网格的研究，并制定了相应的构 架。在国外，也有很多i t 公司和机构热衷于移动网格的相关研究，例如m i c r o s o 矗、 0 r a c l e 等。惠普( h p ) 公司对移动网格也作了较多的研究并且制定了g r i dl i t e 构架f 9 】。 移动网格正引起各国研究人员的重视，政府也投入了较多的人力和财力在 网格的相关研究项目上。下面介绍几个具有代表性的移动网格项目。 ( 1 ) s i m d a t 项目：2 0 0 4 年欧洲委员会投资5 2 0 0 万欧元用于该项目的研 究，旨在推进欧盟各成员国的网格技术，它主要包括四个子项目：s i m d a t 的目 标用户是在工业和服务业使用网格技术的用户，它主要是使用数值模拟方法进 行过程产品开发的数据网格技术。c o i 也g r j d 是为了将现有的网格研究团体聚 合在一起。n e x t g r i d 则是试图在未来十年内开发出一种新的网格计算体系。 a k o g r j m 0 f j0 】项目主要是研究移动网格的相关技术，它的目标是通过移动网格 提供无所不在的资源共享，建立移动的、动态的虚拟组织，并应用在电子学习 和电子医疗等领域。现在已经开发出一些在手机和p d a 上运行的开源软件。 ( 2 ) g l o 对a d 项目：它建立在北半球的光纤环网之上，便于不同地方的 使用者进行信息交换与共享，移动网格是它研究的一个重要内容。此项目由中 国、美国、俄罗斯等国家共同承担，其目的是为了促进国与国之间在各方面的 协作。 ( 3 ) k g r i d 项目：此项目由韩国政府支持，它旨在为工业和学术界提供一 5 武汉理j ：人学硕十学位论文 个强大的研究坏境。它利用移动设备的闲置资源构建移动网格，并开发相应的 软件平台。研究范围主要集中在对无线移动网络和无线网格需求的分析，另一 个研究内容是设计和实现基于p d a 和无线l a n 技术的移动网格平台。 ( 4 ) 全球信息网格g i g 【l ，它由美国军方所支持，主要应用在国家军事领 域，并支持所有的防御部门、国防安全以及相关的智能社团。 总体上来看，移动网格的相关项目在数量上要比传统网格项目要少。但是， 随着研究的深入以及应用领域的扩大，与之相关的研究项目也将越来越多，具 备较好的应用价值和发展前景。 1 3 2 移动网格中任务调度研究现状 任务调度系统是网格系统的重要组成部分，它根据任务q o s 需求，采用合 适的策略把不同的任务分配到相应的资源节点上去执行，它在一般形式下是一 个n p 完全问题1 12 。由于网格系统的异构性和动态性，以及运行于网格系统之中 的应用程序对于资源的不同q o s 需求，使得任务调度变得极其复杂。网格调度 算法分为静态调度算法和动态调度算法【1 3 】。常用的任务调度算法有：0 l b 、m e t 、 m c t 、m i n m i n 、m a ) 【一m i n 、d u p l e x 、g a 、s a 、g s a 、t a b u 、a 幸、s a 、k b p 等。在移动网格中任务调度算法也继承了传统调度算法的一些特点，不同的是 在调度算法中要考虑到移动网格出现的新特性。因此，对移动网格中任务调度 算法主要在节点能量优化、移动性以及考虑不稳定网络连接等几个方面开展研 究。 在移动网格中首先要考虑的就是节点的能量消耗问题，因为移动设备的能 量是有限的，它在进行通信和任务计算时都将消耗能量。如何计算移动设备执 行任务过程中能量消耗，以及如何优化能量消耗等与能量相关的问题得到了很 多研究者的重视。关于资源的能量消耗问题，可以由任务执行的不同阶段进行 计算。另外，也可以通过控制硬件的功耗实现能量的优化。不论是哪一种方法， 目标就是使移动网格中总的能量消耗最少，这样节点能够剩余更多的能量运行。 另方面，在移动网格中节点的网络连接可能呈现间断性。因为节点可以随处 漫游，而且它们之间网络连接不稳定所导致。研究者对于这个问题也进行了一 系列的研究，主要是在任务调度算法中估算网络延时以及运用模型预测节点的 位置。 在移动网格中，大部分的任务调度算法都是针对以上几点进行研究，然后 6 武汉理j l ：入学硕士学位论文 对现有的任务调度算法进行相应的改进。但是，大多数的算法都只考虑了资源 的某一个方面的约束条件( 如能量消耗、移动性预测) ，很少能够同时兼顾多 个方面的因素。在实际的移动网格环境中，综合考虑多方面的因素是很有必要 的，本文正是基于这一点设计并提出一种新的调度算法。 1 4 本文主要工作及创新 在移动网格中，网格资源和用户都与传统网格有所不同，它们主要由各种 各样的移动设备组成。移动设备具备一些固有的特性，如移动性、能量有限和 网络连接不稳定等，这些特性使它们的可靠性大大的降低了。这也会给移动网 格中资源管理带来较大的影响。特别是在任务调度过程中，只有充分到多方面 的因素才能选择可靠性较高的资源去执行任务，从而能够减少任务调度失败的 几率。 本文研究的重点是资源的可靠性( i k s o u r c er e l i a b i l 时) ，从资源的能量消 耗和任务完成时间两方面来衡量一个资源的可靠性。可靠性较高的资源优先去 执行网格任务。除了资源的可靠性，对于网格任务，特别关注了任务提交者( 用 户) 的移动性，在分配任务之前根据移动模型推测用户可能的网格区域，然后 再根据任务的可靠程度选择合适的资源。这样能够在一定程度上减少节点移动 性给任务调度带来的影响。 在计算资源可靠性时，根据任务的紧迫程度把任务进行分类。一类紧急任 务，它们对任务完成时间要求较高。对于这类任务，在计算可靠性的时候要考 虑任务的完成时间，再考虑能量。另一类是非紧急任务，它们对于完成时间要 求不高，只要能够在最迟完成时间d e a d l i n e 之前完成即可。对于这类任务，资 源的能量消耗将是评定可靠性的重要指标。把网格任务这样分类之后，在一定 程度上有利于系统的负载均衡。 综合以上几点，本文提出基于资源可靠性的移动网格任务调度算法 ( r r t s a ) 。在此算法中根据用户的移动性和资源的可靠性，选择可靠性较高 的资源去执行网格任务，最大限度的保证任务能够顺利完成。 本文主要研究工作及创新如下： ( 1 ) 通过分析移动网格的特点建立了节点的移动模型。此模型主要是根据 移动节点与基站间的平均距离来确定节点的活动范围，从而能够确定节点的位 置。在r r t s a 中主要是运用此模型推断任务提交者( 用户) 的所属的移动网格， 7 武汉理工人学硕士学位论文 以便能够选择合适的资源执行任务。 ( 2 ) 通过建立能量消耗模型来计算资源执行任务的能量消耗；通过对资源 断网时问进行预测得到到任务完成时问。从资源的能量消耗和任务完成时间来 综合评定一个资源的可靠性。可靠性高的资源能够在较短时间内消耗较少的能 量完成网格任务。把任务进行分类，根据任务的紧迫程度分为紧急任务和非紧 急任务。对于不同类型的任务采用不同的方法计算资源的可靠性。 ( 3 ) 根据用户的移动性和资源的可靠性，参照m i n m i n 算法的基本思想， 提出基于资源可靠性的任务调度算法( r r t s a ) 。对r r t s a 进行仿真实验并与相 关的算法进行比较，找出算法优点与不足之处。 1 5 论文结构 本文主要包括六个部分，其内容如下： 第l 章绪论介绍本课题的来源、研究目的及意义，同时还介绍了目前移 动网格的发展状况，最后说明了本论文所做的工作和创新。 第2 章移动网格概述介绍了移动网格的体系结构及特点。描述了网格资 源管理的相关概念，说明了网格资源管理的目的、功能及系统结构的形式，总 结了在移动网格资源管理中出现的问题。 第3 章移动网格任务调度及特点分析介绍了网格任务调度的相关概念， 包括目的、功能等，总结了网格任务调度的常用算法。最后分析了移动网格中 任务调度的特点及挑战。 第4 章基于资源可靠性的移动网格任务调度算法根据前文分析的移动网 格任务调度的特点，建立一个节点的移动模型，确定其移动范围。详细分析任 务完成时间和资源能量消耗的计算方法，提出了资源可靠性的具体计算方法。 根据网格用户的移动性预测方法以及资源可靠性，提出一种基于资源可靠性的 移动网格任务调度算法( r r t s a ) 。 第5 章仿真试验及结果分析针对r r t s a 算法进行仿真实验并与相关的算 法进行对比，分析r r t s a 算法的优缺点。 第6 章总结与展望根据仿真实验提出r r t s a 算法存在的不足之处，并确 定下一步研究的方向。 3 武汉理人学硕士学位论文 第2 章移动网格概述 2 1 移动网格的定义 网格可以被看作是一个分布式，高性能计算和数据处理基础设施，它集成 地理和组织上分散的，异构的资源( 计算系统，存储系统，仪器和其他实时数 据源，通信系统等) ，并规定常见的接口，所有这些资源，采用标准，开放， 通用的协议和接口4 。网格技术已经成功的应用于科学领域，主要是应用于大 量数据的处理和存储。由于潜在的网格用户是巨大的，因此网格较为适用于此 类应用。对于移动设备( 如l a p t o p 和p d a ) ，它们只拥有有限的资源( 较低的 处理能力，有限的能量和存储能力) ，如果能让移动设备也能够获取网络中其 它设备提供的可用资源，这将是十分有意义的事情。在移动网格中，移动用户 就可以通过这种技术得到所需的网格服务。移动网格建立在网格技术与移动计 算技术的基础之上，它支持移动用户和资源，使移动用户能够访问到所需要的 网格服务，同时也允许移动设备在网格中共享自己的闲置资源( 计算能力、存 储能力等) 。 在移动网格中网格用户和资源都可以具备移动性。移动设备可以作为网格 用户访问到固定网格中的资源。同时，它也作为网格资源成为网格的一部分。 无论是哪一种方式都存在一些局限性i l5 1 。移动设备仅仅作为访问网格的接口时， 网格为它们提供高可靠性、高性能和高效益的服务，移动设备可以在任何地点、 任何时间提交、监控和管理网格任务。对于网格服务必须能够适应移动设备所 具备的不足之处。另一方面，移动设备的性能已经得到了较大的提升，当多个 l a p t o p 或是p d a 等通过无线网络连接在一起组成一个网格，它们也能够提供相 当的计算能力。因此在资源比较匮乏的环境中，也可以通过网格提供所需要的 计算能力。 具体来讲，可以这样理解移动网格的概念。移动网格涵盖了网格技术和移 动计算技术，它是网格技术的继承者，同时也具备一些自身的新特性，以一种 无缝、透明、安全和高效的方式支持移动用户和资源。 本章以下内容将介绍移动网格的体系结构和特点，分析移动设备在移动网 格中充当的角色以及它对资源的管理所造成的影响。 9 武汉理工火学硕士学位论文 2 2 移动网格的体系结构 在移动网格中，根据网格用户与网格资源类型，可将其分为四种访问类型 【l6 j ：静止静止( s t a t i c s t a t i c ) ，它类似于传统的静态网格，网格用户和资源都是静 止的。静止移动( s t a t i c m o b i l e ) ，在这种形式中网格资源是可移动的，例如使用 个人p c 机去获取移动设备上的资源。移动一静止，它和上一种类型正好相反， 例如可通过无线设备如l a p t o p s ，p d a s 访问静止的网格资源。移动移动，它表示 用户和网格资源都是都处于移动状态，例如在移动网格中内部节点间的通信。 在图2 1 中描述了移动网格的体系结构，有线方式连接采用实线表示，无线 方式连接采用虚线表示。移动网格系统主要包括三个部分：有线网格部分，网 关，无线网格部分1 1 7 j 。根据设备的移动性，无线网格和有线网格是不同的。对 于无线网格部分，又可称之为动态网格( d y n 锄i c 酊d ) 或者无线网格( w i r e l e s s 咖d ) ；而有线网格部分则称之为静态网格( s 诅t i cg r i d ) 或者固定网格( f i x e dg r i d ) 。 图2 一l 移动网格体系结构 l o 武汉理= 人学硕士学位论文 网关将这两种网格连接起来。为了实现无线网格与有线网格之间的通信、 计算、数据缓存等功能，在它们之间设置有多个移动服务代理( m o b i l es e i c e a g e n t ) 。资源代理可分为多种，如移动静态资源代理，元数据服务器和注册服 务器等。 在动态( 无线) 网格中可以采用分布式或集中式的管理方式。在这两种方 式中，前者采用基于移动代理或基于网关中间件，后者可选用基于存储中心的 共享机制。移动资源代理( m o b i l er e s o u r c ea g e n t ) 处于动态网格的前端，它的作用 是进行服务查找、资源发现等。由于移动设备可以随时加入或者是离开网格系 统，为了监控移动资源的变动情况，就需要移动资源监控( m o b i l er e s o u 代ed a e m o n ) 来进行这项工作。对于静态网格可采用通用的网格体系结构，在静态网格与动 态网格连接处加入了静态资源代理( s t a t i cr e s o u r c ea g e n t ) 组件。它主要是处理网格 服务的认证与失效分析以及服务分发。静态网格的底层可以采用基于g l o b u s 【1 8 】 的框架实现。 2 3 移动网格的逻辑组成 移动网格包含了若干的功能组件：注册服务器，元数据服务器，静态资源 代理，移动服务代理和移动资源代理。其中，注册服务器的功能是统一管理网 格节点身份认证、节点授权等数据；元数据服务器的功能是对包括有线网格和 无线网格的节点状态、资源名称、类型、所有者等，实行层次化分级管理；静 态资源代理的功能是接收到达有线网格的请求，然后向有线网格申请资源、进 行资源定位，并返回计算结果给移动服务代理或原始请求节点。通过移动服务 代理可以接收无线设备或有线设备的请求，并且它还负责在移动节点暂时断连 时缓存请求或迁移任务到其它合适的资源节点。移动资源代理主要是负责对移 动服务代理收到请求进行资源的预测与分配和资源的定位与感知。 在移动网格内部可以采用基于移动代理l 憎1 ( m o b i l ea g e n t ) 的服务机制。通过 移动代理收集网格内部提供的各项服务，并报告给元数据服务器。元数据服务 器采用服务器集群，根据数据重要与否选择是否备份，在网格基于网关与服务 器集群的通信中，采取基于优先