（计算机科学与技术专业论文）移动网格中基于时间优化的任务调度研究.pdf

武汉理工大学硕士学位论文 摘要 网格将网络上分散在不同部门的资源组织在一起，构成一台虚拟的超级计 算机，实现异构资源的全面共享和协同解决问题。它充分利用了网络上的闲置 资源，提高了资源的利用率。而移动网格是近年来兴起的新技术研究热点，它 是在传统固定网格中加入移动设备，如移动电话、p d a 、l a p t o p 等构成，是移动 计算技术与网格技术相结合的产物。在移动网格中，目前大多数研究都是将移 动设备作为与网格系统交互的接口，用户通过移动设备向网格请求服务，利用 网格资源来完成任务，并从网格中获得任务执行结果；但随着移动设备性能的 不断增强，移动设备也逐渐作为网格的资源参与到网格任务中，作为网格服务 的提供者，本文重点研究后者。 现有的网格任务调度算法要么只为实现任务执行时间最小，要么只为达到 能量消耗最少，基于时间和能量同时考虑的算法研究不多。在移动网格中，移 动资源具有能量受限和移动性等特征，在调度算法中有必要在能量优化的同时 也考虑时间优化。在研究移动网格自身以及现有调度算法特征的基础上，基于 移动网格资源多方面约束，本文将能量优化放在移动资源管理模型中考虑，而 任务调度算法的主要目标是实现时间优化。 本课题的主要研究工作及创新性体现在以下几个方面： 1 1 移动资源管理模型的研究。移动网格系统不适合采用单一的集中式管理 模式，因为集中式管理容易引起单点故障；而全分散式需要各个资源之间频繁 的通信，消耗移动资源大量的电池能量，因此也不可取。移动网格中资源不会 一直停留在某个固定位置，但是它注册的服务在一段时间内是不变的，基于移 动网格这两个方面的特征，本文提出一种新的网格资源管理模型三层组织 模型。该模型的特征表现在两个方面：一是尽量减少移动资源不必要的能量消 耗，如位置更新和查找工作由专门代理完成；二是实现移动设备与其注册的服 务分离，即所有移动设备注册的服务都组织在资源信息层，资源选择和任务调 度都在该层进行，而移动资源的实际物理位置对于调度者来说是透明的。 2 ) 根据资源移动的局部性特征，提出利用带阀值的指针推进策略对移动资 源的位置进行管理。该策略一方面能减少频繁地进行位置更新带来的能量消耗； 另一方面能减少任务调度时查找资源的时| 日j 。 武汉理工大学硕士学位论文 3 ) 深入分析m i n m i n 算法在移动网格应用中的不足之后，提出一种新的基于 时间优化的移动网格任务调度算法，即m g m i n m i n 算法，目标是实现任务调度 完成时间的最小化。算法中重新定义m a k e s p a n 为任务提交时资源查找时间+ 任务 执行时间+ 任务执行后的资源查找时间，忽略网络传输时间。算法中考虑到移动 资源能量有限，在任务完成时，由分配任务时的域代理主动发送移动代理去寻 找目标资源并取回任务执行结果，这样节省了移动资源发送任务执行结果的能 量和时间消耗。 4 ) 对移动网格仿真的研究。分析了典型的网格仿真工具及其特点并选择 n s 2 作为本研究的仿真平台，对典型m i n m i n 算法和本文提出的m g m i n m i n 算法进行仿真，通过几组对比实验，对这两种算法从多角度进行分析和比较， 结果证明本文提出的m g 。m i n - m i n 算法在移动网格中的优越性。 本论文得到了国家自然科学基金( 批准号：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 ) ，霍英东高校青年教师基金基础性研究课题( 批准号： 12 10 6 7 ) ， 武汉市科技攻关项目( 批准号：2 0 10 10 6 2 12 0 7 ) 的资助。 关键词：网格计算，任务调度，m i n m i n 算法，移动资源，网格仿真 i i 武汉理工大学硕士学位论文 a b s t r a c t t h e 面di m e 伊a t e sa l lm er e s o u r c e st l l a tc o m ef r o md i 脓e md e p a r h l l t si n t 0 o n eh u g e “v i n l j a lm a c l l i n c ，i no r d c rt 0p r o v i d e 趾e x c e l l e n ti n f a s 讯l c t l l r e 锄d p l a t f o n l lf o rr e s o u r c es h 撕n ga n dc o o p e r a t i o n 锄o n gd i s t 曲u t e dc o m p u t e r s s om a l ( e m eb e s tu s eo fm ei d l er e s o u r c e so fn e m o r ka i l di m p r o v em er e s o u r c e su t i l i z a t i o n r a t e m o b i l e 鲥di san e wt e c l l i l o l o g yr e s e a r c _ hh o t s p o ts p m n gu pi n r e c e n ty e a r s ， w r h i c hi sc o m p o s e do fm o b i l ed e v i c e s ，s u c ha sm o b i l et e l 印h o n e ，p d a ，l 印t o pa 1 1 ds o o n nd e d i c a t e st ot h es h 撕n ga l l ds c h e d u l i n go fm o b i l er c s o l l r c e s c u r r e n t l y ，t h e r ei s 1 i t t e rr e s e a r c hf o c u so nm o b i l ed e 、，i c e s 弱r e s o u r c ep m v i d e ri l lm o b i l e 鲥d a w i r o n m e n t ，a l m o s ta l lt l l er e s e a r c h e sp a ya t t 饥t i o nt ou s em o b i l ed e v i c e 勰a na c c 韶s p o i n tt o 班ds y s t e m ，酣du s e rc 觚a s kf o r 鲥ds e 耐c eb ym o b i l ed e v i c e 锄dr e c e i v e m et a s ke x e c u t er e s u l t 丘o m 鲥d h o w e v w i mt h ep 柏m a i l c eo f 廿1 em o b i l e d e v i c eb e 百nt l i 曲e ra n dh i g h e r ，t a k i n gm em o b i l ed e 讥c e 舔m o b i l e 乎i dr e s o u r c e 觚d t a k i n gp a r ti n 酊dt a s ki sg e t t i n gt o oi m p a t i e n tt ow a i t t h em e s i sw i l lf o c u so nm e r e s e a r c ha b o u tm o b i l ed e v i c ea sa 鲥ds e r v i c ep r o v i d 既 a m o n g a l lo fs c h e d u l i n ga l g o r i t h i i l ，s o m ew o r kf o c u so ne i l e 唱yc o n s u m p t i o n ， s o m ew o r kf o c u so nd e a d l i n ec o n s t r a i n e ds c h e d u l i n g ，f e ww o r ki n 鲥ds c h e d u l i n g c o n s i d e rb o t he n e r g ya n dd e a d l i n ea sc o n s t r a i n t s t i l i sm e s i sw i l ln o to n l yd e a lw i t h e 1 1 e r g yc o n s 仃a i n i n gb u ta l s o d e a lw i mm ed e a d l i n cp r o b l 锄i nm o b i l e 面d i t s p r i m a r yo b j e c t i v ei st o1 1 1 i i l i m i z em e t o t a lb a t t e 巧e 1 1 e r g yi nt h er e s o u r c em a j l a g 锄e 1 1 t m o d e la sw e l la st oo p t i m i z et 1 1 es c h e d u l i n gt i m ei nt h et a s ks c h e d u l i n ga l g o r i t l l m t h em a 证r c s e a r c ha n di 蚰o v a t i o no ft h i sm e s i si si n c l u d e di nm ef o l l o w i n g a r e a s ： f i r s t l y ，t h ei d e ao fm o b i l e 嘶da n dr e l a t e di n 丘a s t r u c t u r ea r ep r o p o s c da i l d d e s c 打b e d ，w l l i c h i sd e d i c a t e dt ot h es h 耐n go fm o b i l er e s o u r c e s b e c a u s em e c e n t r a l i z e dm a i l a g e rc a i lr e s u l ti ns i n 西e 仃0 u b l ea n dt l l ed e c e n 仃a l i z c dm a l l a g e rm a y c o n s 啪eal o to fb a t t e 巧e n 哪甄s 0t h e s e 俩ol 【i n d so fm a i l a g e n l e n tm o d ea r en o t s u i t a b l ef o rm o b i l e 酣dr e s o u r c em a n a g 锄e n t t h i st h e s i si n t r o d u c e dan e wk i n do f m o b i l er e s o u r c em a n a g e l e n t - t h r e el e v e l sr e s o u r c eo r g a i l i z a t i o nm o d e ，w h i c h i 武汉理工大学硕士学位论文 i ss u i t a b l ef 0 rm o b i l e 鲥d 酬r 0 砌锄t s e c o n d l y b 嬲e do nm ec h a r a c t 耐s t i c so ft h er 髓o u r c 懿i i lm o b i l e 鲥d an o v d l o c 撕o nm a i l a g e i i l e l l ts 仃a t e g y - ks t 印sp o i i l t e ra d v 孤c e ds 仃a t e g yw a s p r o p o s e d o no n eh 锄d ，t 1 1 es t i a t e g yc 锄r e d u c ee n e 嗡，c o n s 啪i n gc a u s e db yu p d a t i n gm e r e s o u r c e s1 0 c a t i o n 丘e q u e l l mo nm eo m e rh 趾d ，i tc a l lr e d u c en l er e s o u r c el o o k i n g u pt i m ed 嘶n gt a s ks c h e d u l i n g n l i r d l 弘b a s e do n l el i m i t a t i o no ft y p i c a lm i n m i na l g o 打t h m ，an e wa l g o r i t h m i sp r o p o s e di i lt l l i sn l e s i s ，、汕i c hn a m e d 嬲m g m i n m i na l g o d t h i n ，t 1 1 ea l g o r i t h m r e d e 矗n e st h em a l ( e s p a na sm es u mo ft h ee x p e c t l e dc o m p l e t e dt i m ea n dt h ef i n d i n g r e s o u r c e st i m e ，a n di ti 鳃o r e st l l en e t 、v o r kt r a i l s m i s s i o nt i m e t h em a i no b j e c t i v eo f m ea l g o d t h mi st om i n i m i z et h em a k e s p a i l ；m ee i l e f g yo p t i m i z a t i o nw i l lb er e f l e c t e d i nm er e s o u r c em a n a g e m e i l tm o d e l f i n a l l y ，as 嘶e so fe x p 醯n e i l t sw e r ed e s i g n e da i l ds t u d ym ee 任融o nt l l e m g - m i n m i na l g o r i 吼a n dm em i n - m i l la 1 9 0 r i t h mb a s e dd i 侬獭tp 姗e t e r s ，t h e i l c o m p a r em es i m u l a t i o nr e s u l t sw 油t 1 1 e o r e t i c a la i l a l y s i s ，a st h er e s u l t ss h o w ，m e m g m i n - m i na l g o r i t h mt u m e do u tt ob em o r es u i t a b l e 南rt l l em o b i l e 鲥d e n v i r o 胁e i l tb e c a u s ei th a sc o n s i d e r e dm em o b i l i t yo ft h e 酽dr e s o u r c e 锄di tc 锄 g e tl e s sm a l ( e s p a l lt h a i lm i n m i l la l g o r i t h m 。 t h i st h e s i si ss u p p o r t e db yn a t i o n a ln a t u r a ls c i e n c ef o u n d a t i o no fc h i n a ( n o ：6 0 7 7 3 2 1 1 ，6 0 9 7 0 0 6 4 ) ，t h en a t i o n a ls c i e n c ef o u n d a t i o no fh u b e ip r o 、，i n c e u n d e r g r a n tn o 2 0 0 8 c d b 3 3 5 ，n e wc e n t l l r ye x c e e n t1 1 a l e n t si nu n “e r s i 够 州o ：n c e t 0 8 - 0 8 0 6 ) ，o p e nf u n do ft h es t a t ek e yl a b o r a t o r yo fs o f h a r e d e v e i o p m e n te n v i 阳n m e n t ( n o ：s k l s d e - 2 0 0 9 k f - 2 - 0 2 ) ， f o k m g - 1 o n g e d u c a t i o nf o u n d a t i o nf o ry b u n g7 r e a c h e r si nh i g h e re d u c a t i o ni n s t i t u t i o n so f c h i n a ( n o ：1 2 1 0 6 7 ) ，n s fo f w u h 柚m u n i c i p a h 锣州o ：2 0 1 0 1 0 6 2 1 2 0 7 ) k e y w o r d s ：g r i dc o m p u t i n g ，协ks c h e d u l i n g ，m i n - m i i la l g o d t h m ，m o b i l er e s o u r c e ， g d ds i m u l a t i o n 独创性声明 本人声明，所呈交的论文是本人在导师指导下进行的研究工作及 取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得 武汉理工大学或其他教育机构的学位或证书而使用过的材料。与我一 同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说 明并表示了谢意。 签名： 扣 学位论文使用授权书 本人完全了解武汉理工大学有关保留、使用学位论文的规定，即 学校有权保留并向国家有关部门或机构送交论文的复印件和电子版， 允许论文被查阅和借阅。本人授权武汉理工大学可以将本学位论文的 全部内容编入有关数据库进行检索，可以采用影印、缩印或其他复制 手段保存或汇编本学位论文。同时授权经武汉理工大学认可的国家有 关机构或论文数据库使用或收录本学位论文，并向社会公众提供信息 服务。 ( 保密的论文在解密后应遵守此规定) 研究生( 蒜者么导师( 彩桫期珧f i 蝎 武汉理工大学硕士学位论文 第1 章绪论 1 1 本课题的来源及研究意义 目前一些普通的移动设备，如便携式计算机、个人数字助理( p d a ) 、移动 手机等已经越来越大众化，其配置也越来越高端化，其能力也超过几十年前的 大型主机。网格的目标是实现各种资源的共享和协同解决问题，但是目前网格 研究的资源都是固定的，显然这不是长久之计。研究者设想在移动设备上部署 网格中间件，构成一个动态的，多制度的移动设备的虚拟组织，即移动网格 ( m o b i l e “d ) 。移动网格实现了移动设备和网格系统二者的结合，一方面，使 得移动设备依赖于网格平台，实现了移动资源共享；另一方面，网格通过移动 设备扩展了应用的范围。与固定网格相比，移动网格更加贴近每一个普通人的 实际应用。 移动网格作为一种异构动态的计算环境，其任务之一是根据各个资源节点 的状态、网络通信性能、系统负载等参数，把不同的任务分配到合理的资源上 去完成，这也就是所谓的任务调度。在移动网格中，资源的组织模型对网格资 源调度的性能有直接影响。不管是资源还是用户都是可以自由移动，再加上网 格任务计算规模越来越大，固定网格资源已经不能满足所有需求，有必要将各 种移动设备的空闲资源充分利用起来。但是这些资源存在各种缺陷，如能量有 限等，如何有效地组织这些具有多方面限制但又不可忽视的移动资源，是移动 网格资源管理必须要解决的关键问题之一。 与传统网格中的任务调度相比，移动网格中的任务分配更加复杂，必须考 虑资源的移动性或任务的移动性给调度性能带来的影响，如移动资源查找时间、 电池能量的消耗以及花费的代价等问题。有效的任务调度算法要求能根据任务 的多服务质量( q o s ) 需求选择合适的可用资源，尽量实现最优跨度、负载均 衡等目标，提高资源的利用率。现有的调度算法在固定网格中都实现了预期的 目标，但这些算法在资源选择时都没有考虑由于资源的移动性而带来资源电池 能量消耗以及定位移动资源的时间等约束，将现有的任务调度算法应用在移动 网格中不能实现网格任务顺畅、安全、高效的完成。本文基于资源移动性考虑， 分析任务对资源的各种需求，首先建立移动资源三层组织模型，分析在该模型 下移动资源的移动性管理策略；然后在该模型下对现有的经典网格任务调度算 武汉理工大学硕士学位论文 法进行适当的改进，使其适用于移动网格环境的任务调度。该算法对实际移动 网格应用有十分重要的意义。 1 2 移动网格的背景及发展 1 2 1 移动网格问题 随着无线技术和移动技术的发展，出现了各式各样的移动设备，如智能手 机、p d a 和l a p t o p 等，而且它们的数量相当可观，它们也能够提供一定的计算 能力，在一定程度上能够满足网格系统的需求，因此，移动设备也正在被纳入 到网格系统中成为网格的组成部分，形成了移动网格( m o b i l eg r i d ) 。移动网格 在继承传统网格计算的基础上也融入了一些新的特性，它以一种无缝、透明、 安全和高效的方式来支持移动用户和移动资源【l 】。移动网格是由移动设备和固 定p c 服务器等共同组建而成，网格中的无线用户可与网格资源进行动态连接， 从而能够实现对网格资源透明、无缝、分布式的访问，实现更高级别的资源共 享。移动网格也给网格计算带来了新的挑战，在移动网格中将要部署新的基础 设施以满足新的需求，提供一些端到端的功能并且更强调q o s 需求和网格安全 问题，如在间断网络连接下的互操作问题。在这样一个大规模、异构的分布式 环境中，加强安全策略和措施是很有必要的。 在移动网格中，移动设备可以充当两种角色【2 】：一是作为访问网格资源的 接口；二是作为网格资源。前者是利用移动设备去访问现有的网格资源；而后 者则是把移动设备自身作为网格资源可以为其他用户提供网格服务。移动网格 中的用户和资源不同于传统网格，它们具有一些新的特性如移动性、能量受限 性等等使得移动网格的资源管理变得更加复杂化了。 1 2 2 移动网格的应用 移动设备具有分布广泛和自由移动的特点，移动网格的目标就是通过网格 平台实现各种移动资源的共享。移动网格具有以下几个方面的应用。 1 ) 消除网格孤岛 现有的网格应用大多是基于大型主机的强大处理能力之上，所用的网格中 间件巨大而且复杂，在小型的移动设备上无法部署【3 】，网格中的移动资源不仅具 有高动态性还具有移动性等特点，在现有网格中，不管是资源管理模型，还是 任务调度算法，对以上特点都没有给出很好的处理方法。导致移动设备既不能 2 武汉理工大学硕士学位论文 较好地利用网格中的资源，也不能共享自身的资源，与网格系统完全隔离，形 成真正意义上的网格孤岛( s o l a t e di s l 觚d ) 。利用移动网格不需要在移动设备上安 装网格中间件就可以使以上问题迎刃而解，实现移动设备能访问网格中的资源 或者在网格中注册自身的资源，从而实现移动设备真j 下嵌入在网格系统中。 2 ) 实现普适计算 施乐公司p a l oa 1 t o 研究中心的首席技术官m a 出w 萌s e r 最早提出普适计算 ( p e a s i v ec o m p u t i n 曲，或者称为无所不在的计算( u b i q u i t o u sc o m p u t i n 曲4 】的概 念，这种新的计算模式能实现用户方便地访问各种信息和得到各种计算服务。 普适计算模式一直得到了工业界和学术界的认可，它是以人为中心的计算模式， 目前已成为一个重要的研究和应用领域。文献 5 】基于普适计算的概念提出了如 何利用无线设备进行合作解决问题，而网格面向资源的特性更适合普适计算。 因此移动网格的提出适应了普适计算模式，它为普适计算提供各种需要的资源。 通过对移动网格的深入研究，可以为普适计算的实现做铺垫。 3 ) 建立移动虚拟组织 移动网格的出现，使得移动设备可以超越时间和空间的限制，在移动过程 中进行市场交易；在医院里，医生可以通过便携式和移动式设备来监测在急救 车上病人病情；在学校罩，教师上课时可以通过自己的p d a 向学生的p d a 发送 电子课件，共享教学资源。以上这些都可以称为移动虚拟组织的应用。移动网 格可以构造各种各样的虚拟组织，比如移动虚拟市场、移动虚拟医院、移动虚 拟校园等。 具体说，移动网格适合的应用环境有【6 】：嵌入式军事超级计算应用，如坦 克、飞机、船只需要利用无线网络连接起来收集相关数据，然后传送到网格上 的其它节点，使用分布式算法来作出决策；石油钻探中的感应器地震监测或 预测中的感应器和监视器，紧急事件智能预报，如飓风，比如，在不同城市的 科学家之间收集地震数据并使用并行算法来预测未来的地震活动等。虽然数据 资源分散在各个移动节点上，但这些应用可以在一个网格系统上执行；另外， 这些移动节点空闲的c p u 周期也可被利用。因此，不管是在现代计算领域还 是在移动网络系统中，移动网格计算会起着非常重要的作用。 1 3 国内外研究现状及应用 1 3 1 移动网格的研究现状 我国现有网格计算研究主要集中于中科院计算所、国防科大、清华大学等 武汉理工大学硕士学位论文 几家在高性能计算方面有较强实力的科研单位。国内具有代表性的网格研究项 引7 】主要有：由中科院牵头的“国家高性能计算环境n h p c e ( n a t i o n a lh i 窖l l p e r f o m a i l c ec o m p u t i n ge n v 由的i l i i l e i l t ) 。清华大学牵头并由教育部支持的“先进 计算基础设施a c i 工程 ，还有一个是“织女星计划 。最后一个是上海网格， 上海市政府与i b m 公司合作建立“城市网格 ，目的是整合全市范围内的政府 信息资源，提高政府的公共服务能力和效率。国内也有不少高校已经参与了有 关移动网格的研究，也制定了相应的构架。据解放军报报道，中国首家军事网 格研究中心2 0 0 4 年5 月2 8 日在南京理工大学正式挂牌成立，它是由各种通 信卫星、通信飞机、作战地域网等通信和计算机设施组成的广域分布、无缝连 接、动态开放的互联网络，是移动网格具体的应用。 在国外，许多公司和机构都非常热衷于移动网格的研究，如o r a c l e 、微软 等，h p 公司对移动网格也做了比较深入的研究，并制定了嘶dl i t e 构架。国外 信息产业界的大公司也相继公布了与网格目标一致的研究开发计划【8 】，比如： 微软、s u n 、惠普、i b m 等公司取得共识，支持x m l 、s o a p 、u d d i 等万维 网标准，开发出新一代的网络应用，即万维网服务( w 曲s e r v i c e ) ，其目的是将 因特网上的资源和信息汇集在一起，组合成企业和消费者所需要的服务。随着 移动设备配置越来越高端化，传统有线网格f 逐步走向民用，网格以后的发展 趋势是向民用领域发展，为大众提供各种各样的服务和业务。而要对传统网格 的功能进行延伸，就不得不研究移动网格，使网格成为真j 下意义上的第三代互 联网【7 1 。随着开放网格服务体系结构o g s a 【9 】和w 曲服务资源框架w s r f 的提 出，单纯面向科学活动的网格计算也已经真正开始转向面向服务的信息网格。 在工业界，以i b m 、h p 、s l l i l 、o r a c l e 等为代表的大型企业积极推出自己的网 格计算方案和产品。其中与移动网格项目有关的，值得关注的项目有【6 】： 1 ) 2 0 0 4 年，欧洲委员会投资5 2 0 0 万欧元用于研发网格项目，旨在推进其 2 5 个成员国之间的网格计算技术。其中大部分资金将投向四个项目：s i m d a t 是运用数值模拟方法进行过程产品丌发的数据网格技术，着重于汽车、宇航及 制药行业。n e x t g r i d 着力于在未来十年内开发出一种新的网格计算体系。 c o r e g r i d 是为了将现有的网格研究团体聚合在一起。而a k o g r i m o 【9 j 项目 由1 4 个国家组织参与，专门研究移动网格，目标是通过移动网格提供无所不在 的资源共享，建立移动的、动态的虚拟组织，将其应用于电子学习和电子医疗。 2 ) 美国n s f 项目w i r e l e s sg r id 【l0 1 ，由，工业界和学术界合作申请，重点在 于研究无线资源的共享以及无线网络安全，致力于建立无线的虚拟市场，已取 4 武汉理工大学硕士学位论文 得一定的成果。 3 ) 全球六国合作项目g l o r i a d 【u 】，并得到美国n s f 资助，移动网格是 其中的重要部分，目前在弱连接处理方面取得了一定的成果。 4 ) 韩国信息与通信部支持的k 木g r i d 项目，它的目标是为工业界和学术界 提供一个强大的研究环境。在此项目中，对移动网格技术的研究是构建在对 大量移动设备闲置资源的利用之上，并开发一个移动网格平台，研究范围包括： 对无线移动网络、设备和技术、无线网格需求的分析，基于p d a 和无线l a n 技 术的移动网格平台的设计和实现。 移动网格实现了移动设备和网格系统二者的结合【2 】：一方面，移动设备依 赖于网格的平台，实现了移动资源共享；另一方面，网格通过移动设备扩展了 应用的范围。综上所述，移动网格具有重大的研究价值和良好的应用前景。 1 3 2 移动网格中任务调度研究现状 网格中的任务调度就是实现任务与资源之间的匹配，使得总任务的完成时 间最小以及资源的利用率达到最高，它是一个n p 完全问题。任务调度的目标 就是要对用户提交的作业实现最优调度，几个典型的目标是最优跨度、服务质 量、负载均衡、经济原则等【1 2 1 。网格调度算法分为静态调度算法和动态调度算 法。常见的任务调度算法有：o l b 、m e t 、m c t 、m i n m i n 、m a x 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 等。在移动网格中任务调度算法也继承 了传统调度算法的一些特点，不同的是在调度算法中要考虑到移动网格的一些 新特性。移动网格中任务调度算法主要在节点能量优化、移动性以及不稳定网 络连接等几个方面展开研究。 在移动网格中首先要考虑的就是节点的移动问题，因为由于资源的移动， 会使其位置发生变化，调度中心在原来位置无法找到该资源，导致网格任务调 度失败；而且，由于资源的移动，调度者查找资源需要时间，如果将这一因素 加入o o s 考虑的话，那么现有的典型的任务调度算法如m i n m i n 调度算法不能 实现最优跨度的目标，因为每个资源的移动模式不是一样的，有的频繁，有的 比较稳定，选择资源时应该尽量选择比较稳定的资源，减少查找资源的时间代 价。关于如何尽量减少查找资源时间代价问题，可以根据资源的移动模式建立 合理移动资源管理模型，在该模型下采用最优的查找策略；至于如何在任务调 度时考虑这一因素，可以将该因素作为资源选择的一个q o s 参数。其次要考虑 武汉理工大学硕士学位论文 的是移动设备的能量问题，移动资源在进行通信和任务计算以及移动时都会消 耗能量。如何保证资源在移动情况下有充足的能量来完成任务也一直得到了很 多研究者的重视。最后在移动网格中，各个节点的网络连接可能呈现间断性， 研究者对这种由于资源的移动导致不稳定的网络连接问题也进行了一系列的研 究，主要是在任务调度算法中建立相应的模型对网络延时和移动性进行预测。 虽然目前国内外已经提出了很多的任务调度算法，有些调度方法也考虑q o s 以及能量约束，在固定网格中都实现了期望的目标即达到最小完成时间，但是 这些算法都没有考虑移动网格中资源的移动特性。资源的移动性对任务调度成 功与否有着密切的关系，轻则使该任务调度所花费的时间超过了截止时间，消 耗的能量也过多，重则导致任务执行结果无法返回，任务调度失败。这在实时 系统中需要实时处理的任务是不容许发生的。所以现有的网格任务调度方法在 移动网格中并不能实现最小完成时间的目标，必须对其优化，即在满足资源移 动的限制条件下，将任务合理地分配到相应资源节点上，以达到最小调度时间。 1 4 本文的主要工作及创新 由于移动网格环境下资源的多样性、动态性和移动性，一些传统的资源管 理和调度策略不再适合移动网格。为了能够更好地利用网格中的各种移动终端 提供的资源，本文在对移动网格中资源的移动特性进行深入学习和研究的基础 上，建立适合移动网格的三层资源管理模型，在该模型下，引入带阀值的移动 资源位置更新策略；在传统q o s 约束中加入资源的剩余电池能量约束和对移动 资源定位查找时间，对传统的任务调度算法m i n m i n 进行改进，提出适合移动 网格环境下的m i n m i n 算法即m o b i l eg r i d 。m i n m i n 算法，简称m g m i n m i n ， 实现网格任务顺畅、安全、高效执行的同时提高网格中移动资源的利用率。 本文所做的主要研究工作及创新性体现在以下几个方面： 1 ) 资源管理模型的研究。由于移动资源电池能量有限，集中式管理容易引 起单点故障；而全分散式需要各个资源之间频繁的通信，消耗移动资源大量的 电池能量，因此也不可取。本文采用集中式与分散式相结合提出一种新的网格 资源管理模型三层组织模型。该模型的特征一是尽量减少移动资源不必要 的能量消耗，如位置更新和查找工作都由专门代理完成；二是实现移动设备与 其注册的资源分离，即所有移动设备注册的资源都组织在资源信息层，资源选 择和任务调度都在该层进行，而移动资源的实际物理位置对于调度者来说是透 6 武汉理工大学硕士学位论文 明的。 2 ) 在提出的资源组织模型下将资源和任务在资源信息层根据类型分组，资 源调度是面向服务类型的且在多个组内并行调度，缩短调度时间。资源信息层 屏蔽了资源物理层中资源的具体物理位置，实现了资源的具体位置对用户的透 明性。有新服务注册时，资源管理系统会根据服务类型将其归属到相应组中， 不影响其它组中的任务调度，这样能提高资源的利用率。 3 ) 根据移动网格的特点以及资源移动的局部性特征，提出利用带阀值的指 针推进策略对移动资源的位置进行管理。该策略一方面能减少频繁进行位置更 新的能量消耗；另一方面能减少任务调度时查找资源的时间。 4 ) 任务调度算法的研究。分析了移动网格中资源的特点以及现有任务调度 算法的特点及不足，综合考虑移动资源的电池能量以及系统对移动资源的定位 查找时间等因素，对m i n - m i n 调度算法进行改进，提出适合移动网格环境的调 度算法m g m i n m i n 调度算法。并选择n s 2 作为仿真平台，对m i n - m i n 算法和 m g m i n m i i l 算法进行仿真，从多方面比较和分析这两种算法，结果证明 m g m i n m i n 算法更适合移动网格环境，具有更短的m a l ( e s p a i l 。 1 5 论文结构 本论文内容一共分7 部分，每个部分具体介绍如下： 第1 章绪论部分介绍论文课题的来源、研究目的、意义和国内外研究现 状，以及本论文所做的工作和创新。 第2 章移动网格概述及关键技术研究详细给出了移动网格的定义、体系 结构和特点；分析了与网格计算相关计算技术的发展，描述了移动网格中核心 技术研究。 第3 章移动网格资源管理及任务调度对移动性管理的理论进行了概述， 分析了现有常见的位置管理策略在移动网格中的应用；阐述了移动网格中的任 务调度，重点分析了典型m i n m i n 算法和改进的m i n m i n 算法的特点及不足。 第4 章移动网格中资源管理模型优化提出基于域代理的移动网格体系结 构和三层资源组织模型，在该模型下，基于第3 章的位置管理分析提出带阀值 的指针推进管理策略。 第5 章基于时i 、日j 优化的任务调度算法设计与分析首先对算法中的资源和 任务以及用到的参数和假设条件进行了描述；然后重新定义算法中m a k e s p a j l ， 7 武汉理工大学硕士学位论文 分析了任务调度时资源查找的过程及算法中相关公式的计算；最后给出了算法 的实现步骤、伪代码和流程图，并用一个实例来描述算法的实现过程。 第6 章仿真实验针对第4 章提出的移动网格资源管理模型以及第5 章提 出的网格任务调度算法，选择在n s 2 平台上进行模拟试验，分析、论证算法的 试验结果，对算法性能进行评价。 第7 章总结与展望总结本文的研究成果，并对未来的研究目标及其研究 趋势进行一定的展望。 武汉理工大学硕士学位论文 第2 章移动网格相关概述 2 1 计算技术的发展 “计算”这个概念大家都不陌生，在小学老师就教我们如何计算。按照一 定的规则把己知的符号串变成另一个符号串，这个过程就是计算。而符号串的 变换规则就是算法。我们接触的都是一些简单的计算，随着科学技术的发展， 计算已经渗透到多个领域，在计算机领域，也先后出现了分布计算、移动计算、 网格计算和普适计算，这些计算之间既相互联系又相互区别。 2 1 1 分布计算 p c 机和局域网相结合就产生了分布计算( d i s 劬m e dc o m p u t i n g ) 。在分布 计算系统中，各个资源分布在不同的地理位置但能高度共享。从上个世纪7 0 年 代中期到9 0 年代初期，分布计算研究的领域已经取得了深入的研究成果，包括： 远程通信( r e m o t ec o i i l l l l u n i c a t i o n ) 、安全性( s e c u r i t y ) 、远程信息访问( r e m o t e i n f o m a t i o na c c e s s ) 和容错( f a u l tt o l 删l c e ) 等等。分布式计算与其它计算方 式相比具有三个优点【 】：一是稀有资源可以共享；二是可以在多台计算机上平 衡计算负载；三是可以把程序放在最适合运行它的计算机上；分布式计算的核 心体现在前两点上。网格计算实际上也属于分布式计算，它的实质就是组合与 共享资源并确保系统安全。 2 1 2 移动计算 2 0 世纪9 0 年代初期，随着无线局域网和功能强大的便携计算机的出现， 如何建立一个带有移动计算机的分布计算系统成为学者研究的一个难题。于是， 移动计算( m o b i l ec o m p u t i n g ) 应运而生。关于移动计算的概念有很多版本， 下面给出一些典型的概念【l4 】： 1 ) a c m 给出的移动计算概念是：移动计算就是用户在任何时间、任何位置 都能不问断地获得网络服务，包括数据服务以及计算服务等。 2 ) 遥感信息中给出的定义是：移动计算就是各种移动终端通过无线通 9 武汉理工大学硕士学位论文 信网络与远程服务器交换数据的分布式计算。 3 ) m o b i l ec o m p u t i n g 一书中给出：移动计算是一种规程，即用户在离 开固定设施时，利用计算机和通信技术，也能在不间断工作的情况下创建业务 解决方案。 4 ) 商场现代化认为：移动计算是在任何地点和运动状态下，持便携式 设备的用户都能通过相应的网络设施从数据源处获得信息和服务。 虽然分布计算系统的一些基本原理在移动计算系统中仍然适用，但是移动 计算系统应该有自己独有的功能来支持因节点的移动性而带来的许多问题。在 移动计算的研究领域内，移动位置【l5 】服务在市场上已经成为移动用户的首选业 务，包括移动定位和地理信息系统等方面的技术，应用前景非常广阔。 2 1 3 网格计算 随着计算机和分布式技术的高速发展，网格技术目前已经主宰着复杂科学 计算领域，它实现了各种异构、动态资源的全面共享和协同解决问题，为科研 带来了巨大的革新。但是传统的网格是以超级巨型计算机为中心的计算模式， 虽然它是一台处理能力强大的“巨无霸”，要搭建一个网格环境造价极高，通常 只有一些国家级的部门，如航天、气象等部门才有能力配置相应的设备，实现 网格应用，导致网格技术不能普及【l6 1 。随着人们遇到的商业计算越来越复杂， 对计算机的数据处理能力要求越来越强大，现有的超级计算机虽然满足要求， 但是价格显然阻止了它进入普通的商业应用领域，因此，在上个世纪9 0 年代中 期，互联网技术广泛应用于电子商务，迫切需求寻找一种数据处理能力超强而 造价低廉的计算模式，这一新的计算模式就是网格计算【7 】( g r i d c o m p u t i n g ) ，掀起了继传统互联网( i n t e r n e t ) 、万维网( w e b ) 之后的第三次浪潮， 并且为信息产业带来了无限商机。网格计算的目的是为用户提供一种包括各种 资源全面共享的基础设施，通过这种基础设施【j 1 7 1 ，用户不需要了解这个基础设施 上资源的具体细节就可以获得自己需要的资源。 2 1 4 普适计算 目前计算技术有两大特点：以计算机为中心和桌面计算。以计算机为中心 是指人们通常按照计算机本身实现的方便去设计和使用计算机，需要用鼠标或 者键盘等设备来完成信息的输入，与人们的习惯( 依靠语音和视觉交互) 不符 l o 武汉理工大学硕士学位论文 合，现在用户是去适应计算机的习惯而不是按照自己的习惯来使用计算机。所 谓桌面计算是说人们