（计算机科学与技术专业论文）adhoc网格的生命周期最大化算法.pdf

独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研 究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人 已经发表或撰写过的研究成果，也不包含为获褥迸姿基鲎或其他教育机构的学 位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论 文中作了明确的说明并表示谢意。 学位论文作者签名：楼骥洲签字日期：2 0 0 6 年3 月4 日 学位论文版权使用授权书 本学位论文作者完全了解逝姿盘鲎有关保留、使用学位论文的规定，有 权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。 本人授权澎鎏盘堂可以将学位论文的全部或部分内容编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：楼骥洲导师签名 签字日期：2 0 0 6 年3 月4 日签字日期：年月日 学位论文作者毕业后去向： 工作单位：深圳市腾讯计算机系统有限公司 通讯地址：深圳市南山区高新科技园南区飞亚达大厦 电话：1 3 8 6 7 4 8 2 5 4 3 邮编：5 1 8 0 5 7 摘要 本文主要研究的是a d h o c 网格的生命周期最大化算法。由于a d h o c 网格内节 点用电池供电这一特性，如何节约节点电能就成了当下研究的热点。在a d - h o c 网格 中，通讯是节点能量消耗的主要原因，而节能的路由算法能够最明显地降低网格通 讯消耗的能量。 本文首先介绍了网格和a d h o c 网格的相关知识，随后介绍了网格的一些路由 算法，并提出了设计a d h o c 网格节能路由算法的重要性。接着，我们讨论了整个 a d h o c 网格系统的节能方式。在整个a d h o c 系统中，能量消耗既包括节点用来本地 计算的能量消耗，又包括节点间用来通讯的能量消耗。对节点的本地计算，c p u 频 率的动态调节可以部分地节约能量。对节点间的网络通讯，设计节能的路由算法是 最显著的途径，同时当节点不参与通讯时，把它及时地切换到睡眠状态也是节约节 点能量的有效途径。另外，在本地进行一项计算或把它发送到远程节点进行计算消 耗的能量也不同，这就需要我们合理衡量在何处进行计算能更实现节约能量的效果。 针对节能的路由算法，我们设计了一种基于一步前瞻的生命周期最大化算法。该算 法以节点剩余能量可以维持的通讯时间为计算路径的权值，以此时间为权值就可以 很直观地反映节点剩余能量的多少，从而在选择路由时尽可能选择剩余能量多的节 点，从而达到平均网络负载，实现a d h o c 网格生命周期最大化的目的。我们研究了 a d h o c 网格单播、广播、多播下该一步前瞻算法的具体实现，在多播的情况下，我 们妥善地处理了路径重用的问题，从而减少唤醒的睡眠节点数，最大限度地节约节 点能量。最后，我们用n s 2 模拟了我们的生命周期最大化算法，达到了另我们满 意的效果。 基于一步前瞻的生命周期晟大化算法在节能路由算法领域提出了前瞻这一新 的思路。虽然由于路由表设计，甚至算法本身在理论上还存在纰漏，使本算法在目 前还不能在性能上有效地超越当前国际上先进的节能路由算法，但随着技术的成熟， 我们相信本算法会对a d h o c 网格的节能路由算法研究起到一定的推动作用。 关键字：a d h o c 网格，节能，路由算法，生命周期最大化，前瞻 a b s t r a c t t h i sp a p e rm a i n l ys t u d i e st h el i f e t i m em a x i m i z a t i o nr o u t i n ga l g o r i t h mi na d h o c n e t w o r k s i nm o s ta d - h o cn e t w o r k s ，n o d e sa r es u p p l i e db yb a t t e r i e s ，t h es t u d yo fp o w e r s a v i n gp r o b l e mt h u sb e c o m e sah o t f i e l d c o m m u n i c a t i o ni st h em a i np o w e rc o n s u m p t i o n o fa d - h o cn e t w o r k s a n de n e r g ya w a r er o u t i n gi st h em o s te f f i c i e n tw a yt os a v ep o w e ro f c o m m u n i c a t i o n t h i sp a p e rb e g i n sw i t ht h er e l a t e dk n o w l e d g eo fg r i da n da d - h o cn e t w o r k s ，i n t r o d u c e s s o m ea d - h o cr o u t i n ga l g o r i t h m ，a n dr e f e r st ot h e i m p o r t a n c eo fp o w e ra w a r er o u t i n g a l g o r i t h mo fa d h o cn e t w o r k s t h e n ，w cd i s c u s st h ep o w e rs a v i n gm e t h o do ft h ew h o l e a d h o cs y s t e m i na na d - h o cs y s t e m , t h ep o w e ri se i t h e rc o n s u m e db yl o c a lc o m p u t i n go f u s e db yc o m m u n i c a t i o nb e t w e e nn o d e s d y n a m i cc p u f r e q u e n c ys e t t i n gc a np a r t l ys a v e t h ep o w e ri nl o c a lc o m p u t i n g f o rt h ec o m m u n i c a t i o nb e t w e e nn o d e s ，p o w e ra w a r e r o u t i n gi st h em o s te f f i c i e n tw a y i na d d i t i o n ，s w i t c ht h en o d e st h a ta r en o tu s e df o r c u r r e n tc o m m u n i c a t i o nt os l e e pc a na l s os a v ep o w e rc o n s u m p t i o ns i g n i f i c a n t l y t h e r e a l s oe x i s t sab a l a i c eb e t w e e nl o c a lc o m p u t i n ga n dc o m m u n i c a t i o n s o m et a s k sm a yb e l o wp o w e rc o n s u m p t i o nw h e nc o m p u t e dl o c a l l y , b u to t h e r ss u i t st oc o m p u t e r e m o t e l y t o t h ep o i n to fp o w e ra w a r er o u t i n g , w eb r i n gf o r w a r dal i f e t i m em a x i m i z a t i o na l g o r i t h m w i t ho n en o d el o o k a h e a d t h i sa l g o r i t h mi sw e i g h t e db yt h et i m et h a tan o d ec a nk e e p w o r k i n g ，s u c ht i m em e t r i cc a nr e f l e c tt h er e m a i n i n ge n e r g yo fn o d e so b v i o u s l y w h e nw e c h o o s ear o u t e ，t h en o d ew i t hm a x i m u ml e f tp o w e rw i l lb ec h o s e n s oa st ob a l a n t et h e l t a do fn e t w o r k s ，i m p l e m e n tt h ea i mo fn e t w o r kl i f c r i m em a x i m i z a t i o n w ed i s c u s st h e o n en o d el o o k - a h e a da l g o r i t h mu n d e ru n i c a s t ，b r o a d c a s ta n dm u l t i c a s t ，a n dp r o p e r l ys o l v e t h ep r o b l e mo fr o u t eo v e r l a pu n d e rm u l t i c a s t ，a tl a s t ，w eu s en s 2t os i m u l a t eo u r a l g o r i t h m ，a n dg e tas a t i s f a c t o r yr e s u l t o n en o d el o o k 。a h e a dn e t w o r kl i f e t i m em a x i m i z a t i o na l g o r i t h mb r i n g sf o r w a r dan e w t h o u g h ti nt h ef i e l do fp o w e ra w a r er o u t i n g b e c a u s eo ft h ej u v e n i l i t yi ns o m ea s p e c t so f t h ea l g o r i t h m ，w ec a n ts u r p a s ss o m em o s ta d v a n c e da l g o r i t h mi np e r f o r m a n c ei nt h e w o r l d ，b u to u ra l g o r i t h mw i l lb em a t u r i t yg r a d u a l l y , w eb e l i e v eo u ra l g o r i t h mw i l l a d v a n c et h er e s e a r c ho fp o w e ra w a r er o u t i n go fa d - h o cn e t w o r k s k e y w o r d s ：a d - h o c , p o w e ra w a r e ，l i f e t i m e , r o u t i n g ，l o o k - a h e a d 4 1 1 网格 1 1 1 网格和网格计算的概念 第一章序论 像电力供应的实用模型一样，网格是一个概念，它意在通过网络向用户提供可 随时按需利用计算资源和信息资源的环境。如果要更严格地定义，网格则是指一个 环境，在这一环境中，分布于网络上的多种多样的计算资源和信息资源( 计算机、存 储装置、视觉化装置、大型实验观测装置) ，可以被一个虚拟组织的成员用作一台虚 拟计算机”。通过每一站点的计算机的内置网格中间件，虚拟计算机的功能得以实现。 这样，用户既可以利用自己的程序执行任一想要的计算( 计算服务) ，又可以利用高 级程序和从其它站点得到的数据获得必要的处理好的数据( 应用服务) 。基于网格的 问题的求解就是网格计算。 构筑这样的网格有很多好处。首先，它向科研人员提供一种工具，使他们可以 在分散的环境中有效地进行合作研究。例如，在欧盟资助的嚏据网格”项目中，世 界各地的3 0 0 0 名高能物理学家在网格上共同开发并共享数据和程序，因而提高了研 究效率，同时加强了研究活动的竞争。在大科学研究方面，实验设备和数据的大规 模化显然需要大规模计算，为了提高研究效率，研究资源需要共享。 第二，网格技术为有效利用分布式资源提供方便。例如，集中利用分布在网上 的闲置资源，就可获得相当于一台超级计算机的计算能力。一个组织难以实现的超 大容量，可以通过网络连接分布式资源共享来实现。然而，要利用高速计算能力， 确保数据快速传输的高速网络也是必不可少的。 第三，分摊负载和提高可靠性。由于资源是分布式的，即使单台计算机上出现 大负载，也可以将负载分散到网络上的其它装置上。这样，每一台计算机都不必为 系统准备峰值载量，只要整个网络装备了峰值载量设备就可以了。而且，即使有一 台计算机出错，也不会耽误整个系统的运行，可靠性得以提高。当系统的某一部分 受到网络袭击时，服务也不会中断，只要断开受到袭击的部分，系统其余部分就能 支持这一业务服务，这为风险管理提供了一种有效的方案。 值得注意的是，网格技术不是提高计算机本身性能的技术，而是一项计算机的 应用技术。“有了网格就不需要超级计算机”和“有了超级计算机就不需要网格”的说 法都是错误的。有很多计算虽然借助网络但计算效枣却很低，所以，我们仍需要努 力提高超级计算机本身的性能。就网格而言，只要提高单台高性能计算机的性能， 网格整体的计算能力就会得以提高。 网格计算系统( g r i dc o m p u t i n gs y s t e m ) 与分布式系统和并行系统相比有很多 相同的特征，但是与二者又有着非常重要的区别。与分布式系统类似，位于多个管 理域下的超级计算机通过不可靠的网络进行连接，并且需要对广域分布的动态资源 进行集成，但是网格计算系统对高性能的要求使其编程模型及接口与分布式系统有 极大的差别。网格计算系统作为并行系统还需要进行超级计算机之间的通信调度以 满足应用对性能的要求，然而由于网格计算系统的异构性以及动态性，现有的并行 计算技术不能够很好地适应这种需求。 一般而言网格计算系统具有以下几个特征： ( 1 ) 扩展性：网格计算系统初期的规模较小，随着超级计算机系统的不断加入， 系统的规模随之扩大。 ( 2 ) 系统多层次的异构性：构成网格计算系统的超级计算机有多种类型，不同 类型的超级计算机在体系结构、操作系统及应用软件等多个层次上具有不同的结构。 ( 3 ) 结构的不可预测性：与一般的局域网系统和单机的结构不同，网格计算系 统由于其地域分布和系统的复杂使其整体结构经常发生变化。 ( 4 ) 动态和不可预测的系统行为 占的，因此系统的行为是可以预测的， 系统行为和系统性能经常变化。 在传统的高性能计算系统中，计算资源是独 而在网格计算系统中，由于资源的共享造成 ( 5 ) 多级管理域：由于构成网格计算系统的超级计算机资源通常属于不同的机 构或组织并且使用不同的安全机制，因此需要各个机构或组织共同参与解决多级管 理域的问题。 对于网格计算系统来说，最根本的问题是实时获得系统的结构和状态信息，通 过这些信息对网格应用进行配置，并能实时获得计算资源的状态信息。 网格和集群有着很大的区别。集群的思想是把大量现成的p c 直接放上机架， 用高速网络连接在一起，构成一台超级计算机。而不像大型计算机需要专门研制集 成电路板，这大大缩减了制造的时间和成本。集群能仅仅通过增加服务器满足增长 的需求。然而，集群的服务器数量、以及由此导致的集群性能是有限的：互连网络 容量。也就是说如果一味地想通过扩大规模来提高集群计算机的性能，它的性价比 8 会相应下降，这意味着我们不可能无限制地扩大集群的规模。网格虚拟出空前的超 级计算机，不受规模的限制，成为下一代i n t e m e t 的发展方向。集群和网格最大的 区别是集群只是一个备份技术，而网格计算是现在只要看到任何一个地方有闲置就 自动利用资源，任何一个资源消失的时候就释放这个资源使用，使负载去到其他地 方。网格和集群的区别包括： 1 、异构性：集群内在很多情况下是通过局域网将性能、配置基本相同的多个机 器连接起来的。从这个层面上讲，网格的很多特型在集群内并没有得到解决：如果 机器之间不是通过局域网链接起来怎么办? 需要考虑网络使用和性能问题。如果机 器之间性能差距很大怎么办? 需要考虑工作调度问题。如果机器之间软件版本、甚 至操作系统版本不一样怎么办? 需要考虑异构集成问题。 2 、安全性和用户访问：在一个集群内，若干台计算机可以通过统一的安全机制 ( 如校园网防火墙) 进行保护。在网格下，必须假设机器之间是有防火墙存在的， 而且这些防火墙设置很可能完全不同。对于一个在网格上的计算机来说，如何信任、 接受和运行远程请求的任务，是需要一套安全机制的( 如u s e r h o s tc e r t i f i c a t e ) ，但 是在集群内，可以适当简化。 网格系统可分为：资源层、中间件层( 网格操作系统层) 、工具环境层、应用 层： ( 1 ) 网格资源( g r i dr e s o u r c e ) 是构成网格系统的基础设施，主要包括网格结点 和宽带网络系统。网格结点包括各种计算资源，如超级计算机、集群系统、贵重仪 器、可视化设备、现有应用软件、数据库等，这些计算资源通过网络设备连接起来， 具有分布和异构特性，而宽带网络系统是在网格系统中提供高性能通信的必要手段。 ( 2 ) 网格中间件( g r i dm i d d l e w a r e ) 是指一系列协议和服务软件，其功能是屏 蔽网格资源层中计算资源的分布、异构特性，向网格应用层提供透明、一致的使用 接口，网格中间件层也称为网格操作系统( g r i do p e r a t i n gs y s t e m ) ，其核心服务包 括：网格资源的管理分配、信息优化、任务调度、存储访问、安全控制、质量服务 ( q o s ) 等。还需提供a p i 和相应的环境，以支持网格应用开发。 ( 3 ) 网格必须提供良好的应用开发工具环境( 酣dt o o l s ) ，如c + + 、f o r t r a n 以 及j a v a 等语言，m p i 、p v m 等应用开发界面，并支持消息传递、分布共享内存等多 种编程模型。 ( 4 ) 网格应用( g r i da p p l i c a t i o n ) 是用户需求的具体体现，是各种应用软件的研 究。在网格操作系统的支持下，网格用户可以使用其提供的可视化工具或环境开发 各种应用系统。 1 1 2 , 网格系统的关键技术 网格计算系统的关键技术包括以下几个方面： ( 1 ) 网络技术 研究提高网络的性能、可靠性和容错性，为桌面机提供一个高带宽的通信系统， 高速通信协议和通信服务质量保证技术对网格计算系统的研究都非常重要。 ( 2 ) 高效可扩展的分布式并行计算系统 为了使用户能够透明地使用网络资源，需要建立一个高效的、可扩展的分布式 并行计算环境，并以此为基础提供各种高级的服务。 ( 3 ) 面向用户的程序设计模型 为了能够充分发挥网格计算系统的特点，需要为网格系统设计有效的程序设计 模型来充分利用资源。面向对象技术将会是丰要的实现技术之一，基于c o r b a 、j a v a 或者w e b 等技术的分布式对象技术适合于建造复杂的计算对象和移动计算对象。 ( 4 ) 可视化技术 在网格计算中的可视化技术使用图形、图像等手段来描述网格系统中资源和任 务的行为、状态和结构，为网格计算系统的资源管理、作业调度和数据传输提供帮 助。 ( 5 ) 大型科学应用计算研究 网格计算系统的目的是充分利用网络上的各种资源来支持大型的并行分布式计 算，因此，对应用的研究也应同时展开，由应用驱动来提出对网格计算系统的功能 和技术要求，并验证其技术途径和技术实现的有效性。 ( 6 ) 高效的程序编译模型和执行引擎 传统情况下，应用程序在执行前需要编译成面向某平台的可执行代码，这些本 地码的平台相关性决定了它们不能跨平台执行，这使得程序在异构环境下的执行和 资源的使用受到了一定的限制。解决这个问题的方法是使用平台无关的中间代码， 由于中间代码通常是解释执行的，因而执行的效率比较低。为了解决这些问题，需 各种应用系统。 1 1 2 网格系统的关键技术 网格计算系统的关键技术包括以下几个方面： ( 1 ) 网络技术 研究提高刚络的性能、可靠性和容错性，为桌面机提供一个商带宽的通信系统， 高速通信协泌和通信服务质量保证技术对网格计算系统的研究都非常重要。 ( 2 ) i 岳效可扩展的分布式并行计算系统 为了使用户能够透明地使用网络资源，需要建立一个高效的、可扩展的分布式 并行计算环境，并以此为基础提供各种高级的服务。 ( 3 ) 而同用户的程序设计模型 为了能够充分发挥网格计算系统的特点，需要为网格系统设计有效的程序设计 模型来充分利用资源。面向对象技术将会是主要的实现技术之一，基于c o r b a 、j a v a 或者w e b 等技术的分布式对象技术适合于建造复杂的计算对象和移动计算对象。 ( 4 3 可视化技术 在网格计算中的可视化技术使用图形、图像等手段来描述网格系统中资源和任 务的行为、状态和结构，为网格计算系统的资源管理、作业调度和数据传输提供帮 助。 ( 5 ) 大型科学应用计算研究 网格计算系统的目的是充分利用网络上的各种资源来支持大型的并行分布式计 算，因此，对应用的研究也应同时展开由应用驱动来提出对网格计算系统的功能 和技术要求，并验证其技术途径和技术实现的有效性。 ( 6 ) 高效的程序编译模型和执行引擎 传统情况下，应用程序在执行前需要编译成面向某平台的可执行代码，这些奉 地码的平台相关性执定了它们不能跨平台执行，这使得程序在异构环境下的执行和 资源的使用受到了一定的限制。解决这个问题的方泣是使用平台无关的中间代码， 由于中间代码通常是解释执行的，因而执行的效率比较低。为了解决这些问题，需 由于中间代码通常是解释执行的，因而执行的效率比较低。为了解决这些问题，需 要对程序的编译模型和执行g i 擎进行研究，解决平台无关陛和执行效率之间的矛盾。 1 1 3 网格系统的应用和现状 当前网格显著发展的主要动力是技术本身的成长和应用需求的增加。从技术开 发来看，最近的互联网主干网提供国内1 0 g b p s 级和国际1 g b p s 级的存取，宽带时代 己经到来。而且，随着耳联网的扩大。网络速度和可靠性都有所提高，网格通过互 联网可以提供便于应用的分布式计算环境。 此外，在应用方面，网格开始被视为信息技术、生物技术和纳米技术等科学中 利用l t 的活动所必要的研究工具。并且，高能物理、空间科学等大科学想将网格作 为支持研究活动的基础设施，通过共享昂贵的特殊实验设备和数据分析来提高研究 效率。 以下介绍网格的各种可能应用实例。 1 元计算 可以同时利用分布在一个网络上的超级计算机等多台高性能计算机，执行单台 计算机无法实现的大规模计算。目的是创建一个虚拟的大型计算机。网格上执行的 计算有两种类型：一是单程序计算降内部计算分散到平行的多台计算机进行； 二是平行计算将同一程序安装到多台计算机上，给予每一台计算机不同的数据 集，并将每一台计算机的计算结果( 参数扫描) 集中起来。 2 研究网格f 虚拟实验室) 建立一个由研究人员和研究机构组成的社区，每一个参加者都可以通过网络获 得该社区的计算资源、数据资源和实验装置。除了共享数据以外，各个研究人员还 可以将他们的应用程序与他人的应用程序结合起来进行复杂的仿真。在以往的远程 存取中，各站点拥有自己的软件。网格为远程存取提供共用的界面，因此可实现更 广泛的连接，也更易于建立。 3 存取网格 存取网格提供一种环境，在这一环境中，相距遥远的研究人员共用相同的画面 和计算结果，可以顺利迅速地推进共同研究项目。借助高速网利用多播通信，画质 比电视会议系统好，除此之外，存取网格还提供其它工具如文件共享等，以便高效 地进行共同作业。 4 数据网格 数据网格也称为数据密集计算，靠它可通过网络进行远程数据存取，这些数据 不是量太大，一处存储不下，就是分散在各个地点。数据网格技术的研究在进行中， 课题有大数据集的高效存储和读取以及互联网的大容量通信等。这里应注意的是数 据的传输时间。因为即使在超高速网络上传输大量数据所需时间也很长，所以要在 数据生成点进行初步分析和计算。例如，在欧洲核子研究中- l , ( c e r n ) 的大型加速器 实验项目中，5 0 0 家研究机构的7 0 0 0 名研究人员每年要进行几亿次实验，会产生6 皮 8 皮字节的数据。欧洲的欧盟数据网格和美国的网格物理网计划都在开发网格技术， 以分析高能物理实验数据并实现研究人员之间的数据共享。此外，网格技术也可以 用于空间研究，所以，网格可以提高大科学研究的效率。 5 计算机服务网格 在这一环境中，利用一个组织的网格按需要提供计算能力，而用户没有意识到 计算服务器的类型。计算服务网格像虚拟计算中心一样工作。东京工业大学的校园 网格就是一例。它由分散在校园内的个人计算机群( 总计8 0 0 台处理器) 和2 5 太字节的 存储器构成，通过高速校园网可以利用计算机群和存储器。 6 网格a s p o 直用服务提供商1 网格a s p 提供的服务使远程用户可以借助网络发送数据并取得结果，网络靠运 行在高性能计算机上的应用程序运作。在上述的计算服务网格中，用户需要自己编 写程序，面网格a s p 利用已经编好的有用的程序。并且利用基因组数据等有用的数 据集提供服务。例如，由于医疗数据涉及隐私保护，不能外泄，但是通过网格可以 在数据库站点运行分析程序并且最后仅获得结果。 7 桌面刚格计算 家用个人计算机大部分时间是闲置的，桌面网格计算意在集中这些闲置时间的 计算能力去执行某些计算。由于参与者通常无偿地提供其闲置的计算能力，因此也 称作无偿计算。例如空间观测数据分析以及治疗癌症、艾滋病和白血病的新药开发 等。在空间观测数据分析中，有4 0 0 万人无偿提供了个人计算机的闲置时间，获得了 相当于具备4 0 太次浮点性能的超级计算机的计算能力。在桌面网格计算中，各台参 加的计算机的处理能力不大，又通过速度很慢的网络连接，所以限定了计算的类型。 针对大量不同的输入参数进行相同的计算处理的参数扫描型是理想的类型。而且还 需要软件升级、安全、隐私保护和故障排除等对策。 最近，一些企业利用企业内的个人计算机的闲置计算能力，建立订购管理系统。 因为计算机连在企业的内部网上，所以可以避免安全和费用问题。 8 传感器网格 在未来无处不在的计算环境中，传感器网格是网格的一种最终形式。安装在任 何地方的传感器都被连到瓦联网上，因此可以随地存取数据。例如，通过收集并分 析安置在世界各地的众多传感器的数据，可以监控全球的环境。 由于网格计算环境可以连接广域范围内不同标准的异构“孤岛”，形成庞大的全 球性计算体系，是i n t e m e t 发展的高级形式，因此，受到世界各国和组织的高度重视， 己经开展了许多论坛( h t t p ：w w w g r i d f o r u m o r g ) 、实验环境和研究项目，它们大 多数都是在网上共享的，极大地方便了人们研究和利用有关资源。较有代表性的网 格计算项目包括：实验床、g l o b u s 项目、l e g i o n 项耳、g l o b e 项目、n e t s o l v e 项目、 j a v a l i n 项目等。 这些项目可简单地分成有代表性的两类： f 1 ) g l o b u s 项目 提供基础的软件，集成分散的异构资源，形成一个单一的计算环境。其核心是 g l o b u s 网格计算工具包，这是一个构筑网格计算环境的中间件。提供基本的资源定 位、管理、通信和安全等服务。该计算工具包是模块化的，允许用户按自己的需要 定制环境。 ( 2 ) 基于j a v a 的网格计算 j a v a 语言利相关技术成功地解决了困扰网格计算的几个关键问题，如异构性和 安全性，另一个重要的优势是j a v a 程序的最小执行环境可以在w e b 浏览器中执行而 不需要另外安装软件，理论上全球任意一台装有w e b 浏览器的机器都可以进行全球 计算。尽管j a v a 平台还存在效率低等问题，但它无疑将大大影响网格计算模式的发 展，使实现全球分布式计算已不再是一个梦想。 当前的研究普遍停留在对网格计算前端上，并有不少可投入使用的系统。这些 系统的普遍模型是：以某一个或几个超级计算机作为计算资源，在这些超级计算机 上有一些预登记的计算应用程序；在整个广域网上的用户和这些超级计算机之间提 供一个中间件，使得使用不同硬件环境、操作系统环境的各个用户能够透明而安全 地提交自己的计算请求；由中间件将这些计算请求转换成超级计算机上预登记应用 程序所要求的形式，交给超级计算机进行计算。 在上述网格计算模型中，基本上没有针对网格计算内核做什么工作，随着j i n i 技术的出现，前端技术的研究变得更为简单，而内核技术的研究则相对落后。高性 能计算由局域网范围扩展到广域网时缺乏适合广域网计算并行程序编程模型和统一 的、与编程模型相协调的计算资源管理模型。 针对网格计算系统的特点及目前研究的实际情况，一些研究单位将网络计算的 前端与内核统一看待，研究网格计算系统资源的异构与动态特性、计算资源与并行 任务充分匹配的资源管理模型，提出并研究一种不依赖用户身份的网格计算系统， 并且给出安全、可靠、低开销的可定制资源保护策略，使网格计算系统资源管理与 资源保护更加实用科学。 分析网格计算系统的特点及目前研究的实际情况，网格技术未来的研究可能集 中在如下几个方面： ( 1 ) 动态自适应性研究 研究网格计算系统的动态自适应性，使得网格计算系统能够自动适应环境的变 化。网格计算系统中某一资源出现故障或失败的可能性较高，系统的资源会不断扩 大、应用会不断增长，系统的整体结构和整体性能会不断地发生变化，并且随时有 不可预测的系统行为发牛- ，这就要求资源管理程序能够动态监视和管理网格资源， 从目前可利用的资源中选取最佳资源服务，尽量减小由于这种故障或失败、整体结 构和整体性能发生变化或不可预测的系统行为等问题对网格整体性能的影响。 ( 2 ) 安全管理研究 研究网格计算系统的安全管理机制，确保网格计算系统管理和使用的安全性。 建立全网格的帐号管理和记账系统，使得任何用户能够从任何连在网格的计算机上， 安全登录并有效使用网格资源；确定适用于网格计算系统的信息加密机制和信息传 输机制；确定网格计算系统的管理层次体系，将管理域按照区域层次划分，并且决 定管理信息流的流向；能够为不同级别的系统管理员提供强有力的工具或界面监视 系统资源和系统的运行情况。 ( 3 ) 应用计算研究 研究可使用网格计算系统进行计算的新应用，充分利用网络上的各种资源来支 持大型的并行分布式计算，由应用驱动来提出对网格计算系统的功能和技术要求， 并验证其技术途径和技术实现的有效性。 ( 4 ) 高效的程序编译模型和执行引擎研究 研究解决平台无关的中间代码执行效率低下的问题，对程序的编译模型和执行 引擎进行研究，解决平台无关性和执行效率之间的矛盾，最终能够提供一种或几种 解决方案，使得程序能够顺利地在异构环境下执行和使用系统资源。 网格技术同时仍面临着巨大的挑战，在技术方面，其研究重点是网格软件技术 的研究和实现，并以网格系统软件为主要研究对象。人们需要建立一个具有开放的 体系结构、标准和协议，以形成信息获取、传输、访问、共享和处理的单一开放的 信息处理基础设施平台，需要克服虚拟组织的管理和协同工作问题，需要解决网格 的可用性和可开发性障碍，并解决系统安全问题。网格作为基础设施，除了技术上 的挑战外，一些社会、政治因素对网格的普及也至关重要，应当建立资源的外包、 数据的保密等法律保护机制。 1 2 a d h o c 网格 1 2 1 a dh o c 网络的概念 a dh o c 网络是一种没有有线基础设施支持的移动网络，网络中的节点均由移动 丰机构成。a dh o c 网络最初应用于军事领域，它的研究起源于战场环境下分组无线 网数据通信项目，其后，又在1 9 8 3 年和1 9 9 4 年进行了抗毁可适应网络s u r a n ( s u r v i v a b l e a d a p t i v en e t w o r k ) 和全球移动信息系统g l o m o ( g l o b a li n f o r m a t i o n s y s t e m ) 项目的研究。由于无线通信和终端技术的不断发展，a dh o c 网络在民用环 境下也得到了发展，如需要在没有有线基础设施的地区进行临时通信时，可以很方 便地通过搭建a dh o c 网络实现。 在a dh o c 网络中，当两个移动主机在彼此的通信覆盖范围内时，它们可以直接 通信。但是由于移动主机的通信覆盖范围有限，如果两个相距较远的主机要进行通 信，则需要通过它们之间的移动主机的转发才能实现。因此在a dh o c 网络中，主机 同时还是路由器，担负着寻找路由和转发报文的工作。在a dh o c 网络中，每个丰机 的通信范围有限，因此路由一般都由多跳组成，数据通过多个丰机的转发才能到达 目的地。故a dh o c 网络也被称为多跳无线网络。 a d h o c 网络可以看作是移动通信和计算机网络的交叉。在a d h o c 网络中，使用 计算机网络的分组交换机制，而不是电路交换机制。通信的主机一般是便携式计算 机、个人数字助理( pda ) 等移动终端设备。a dh o e 网络不同于目前因特网环境 中的移动i p 网络。在移动i p n 络中，移动主机可以通过固定有线网络、无线链路和 拨号线路等方式接入网络，而在a dh o c 网络中只存在无线链路一种连接方式。在移 动i p 网络中，移动主机通过相邻的基站等有线设施的支持才能通信，在基站和基站 ( 代理和代理) 之间均为有线网络，仍然使用因特网的传统路由协议。而a dh o e 网 络没有这些设施的支持。此外，在移动l p 网络中移动丰机不具备路由功能，只是一 个普通的通信终端。当移动主机从一个区移动到另一个区时并不改变网络拓扑结构， 而a dh o c 网络中移动丰机的移动将会导致拓扑结构的改变。 a dh o c 网络作为一种新的组网方式，具有以下特点： 1 、网络的独立性 a dh o c 网络相对常规通信网络而言，最大的区别就是可以在任何时刻、任何地 点不需要硬件基础网络设施的支持，快速构建起一个移动通信网络。它的建立不依 赖于现有的网络通信设施，具有一定的独立性。a dh o c 网络的这种特点很适合灾难 救助、偏远地区通信等应用。 2 、动态变化的网络拓扑结构 在a dh o c 网络中，移动主机可以在网中随意移动。主机的移动会导致主机之间 的链路增加或消失，主机之间的关系不断发生变化。在自组网中，主机可能同时还 是路由器，因此，移动会使网络拓扑结构不断发生变化，而且变化的方式和速度都 是不可预测的。对于常规网络而言，网络拓扑结构则相对较为稳定。 3 、有限的无线通信带宽 在a dh o c 网络中没有有线基础设施的支持，因此，主机之间的通信均通过无线 传输来完成。由于无线信道本身的物理特性，它提供的网络带宽相对有线信道要低 得多。除此以外，考虑到竞争共享无线信道产生的碰撞、信号衰减、噪音干扰等多 种因素，移动终端可得到的实际带宽远远小于理论中的最大带宽值。 4 、有限的主机能源 在a dh o c 网络中，丰机均是一些移动设备，如pda 、便携计算机或掌上电脑。 由于主机可能处在不停的移动状态下，主机的能源主要由电池提供，因此a dh o c 网 络有能源有限的特点。 5 、网络的分布式特性 在a dh o c 网络中没有中心控制节点，丰机通过分布式协议互联。一旦网络的某 个或某些节点发生故障，其余的节点仍然能够正常工作。 6 、牛存周期短 a dh o c 网络主要用于临时的通信需求，相对与有线网络，它的生存时间一般比 较短。 7 、有限的物理安全 移动网络通常比固定网络更容易受到物理安全攻击，易于遭受窃听、欺骗和拒 绝服务等攻击。现有的链路安全技术有些已应用于无线网络中来减小安全攻击。不 过a dh o c 网络的分布式特性相对于集中式的网络具有一定的抗毁性。 1 2 2a d h o c 网络的应用 由于a dh o c 网络的特殊性，它的应用领域与普通的通信网络有着显著的区别。 它适合被用于无法或不便预先铺设网络设施的场合、需快速自动组网的场合等。针 对a dh o c 网络的研究是因国事应用而发起的。因此，军事应用仍是a dh o c 网络的主 要应用领域，但是民用方面，a dh o c 网络也有非常广泛的应用前景。它的应用场合 主要有以下几类： 1 、军事应用：军事应用是a dh o c 网络技术的主要应用领域。因其特有的无需架 设网络设施、可快速展开、抗毁性强等特点，它是数字人战场通信的首选技术。a d h o c 网络技术已经成为美军战术互联网的核心技术。美军的近期数字电台和无线互联 网控制器等主要通信装备都使用了a dh o c 网络技术。 2 、传感器网络：传感器网络是a dh o c 网络技术的另一大应用领域。对于很多应 用场合来说传感器网络只能使用无线通信技术。而考虑到体积和节能等因素，传感 器的发射功率不可能很大。使用a dh o c 网络实现多跳通信是非常实用的解决方法。 分散在各处的传感器组成a dh o c 网络，可以实现传感器之间和与控制中心之间的通 信。这在爆炸残留物检测等领域具有非常广阔的应用前景。 3 、紧急和临时场合：在发生了地震、水灾、强热带风暴或遭受其他灾难打击后， 固定的通信网络设施( 如有线通信网络、蜂窝移动通信网络的基站等网络设旖、卫 星通信地球站以及微波接力站等) 可能被全部摧毁或无法正常工作，对于抢险救灾 来说，这时就需要a dh o c 网络这种不依赖任何固定网络设施又能快速布设的自组织 网络技术。类似地，处于边远或偏僻野外地区时，同样无法依赖固定或预设的网络 设施进行通信。a dh o c 网络技术的独立组网能力和自组织特点，是这些场合通信的 最佳选择。 4 、个人通信：个人局域网( p a n ，p e r s o n a la r e an e t w o r k ) 是a dh o c 网络技术的 另一应用领域。不仅可用于实现p d a 、手机、手提电脑等个人电子通信设备之间的 通信，还可用于个人局域网之间的多跳通信。蓝牙技术中的超网( s c a t t e r n e t ) 就是 一个典型的例子。 5 、与移动通信系统的结合：a dh o c 网络还可以与蜂窝移动通信系统相结合，利 用移动台的多跳转发能力扩大蜂窝移动通信系统的覆盖范围、均衡相邻小区的业务、 提高小区边缘的数据速率等。 在实际应用中，a dh o c 网络除了可以单独组网实现局部的通信外，它带可以作 为末端子网通过接入点接入其他的固定或移动通信网络，与a dh o c 网络以外的丰机 进行通信。因此，a dh o c 网络也可以作为各种通信网络的无线接入手段之一。 1 2 3 a d h o c 网络与其他移动通信系统的比较 1 、蜂窝系统 蜂窝系统是覆盖范围最广的陆地公用移动通信系统。在蜂窝系统中，覆盖区域 一般被划分为类似蜂窝的多个小区。每个小区内设置固定的基站，为用户提供接入 和信息转发服务。移动用户之间以及移动用户和非移动用户之间的通信均需通过基 站进行。基站则一般通过有线线路连接到主要由交换机构成的骨干交换网络。蜂窝 系统是一种有连接网络，一旦一个信道被分配给某个用户，通常此信道可一直被此 用户使用。蜂窝系统一般用于语音通信。 2 、集群系统 集群系统与蜂窝系统类似，也是一种有连接的网络，一般属于专用网络，规模 不大，主要为移动用户提供语音通信。 3 、卫星通信系统 卫星通信系统的通信范围最广，可以为全球每个角落的用户提供通信服务。在 此系统中，卫星起着与基站类似的功能。卫星通信系统按卫星所处位置可分为静止 轨道、中轨道和低轨道3 种。卫星通信系统存在成本高、传输延时大、传输带宽有限 等不足。 上述移动通信系统都需要有线网络通信基础设施的支持，如基站、交换机、卫 星等。这些设施的建立和运转需要大量的人力和物力，因此成本比较高，同时建设 的周期也长。a dh o e 网络不需要基站的支持，由主机自己组网，因此，网络建立的 成本低，同时时间短，一般只要几秒钟或几分钟。上述通信系统中。移动终端之间 并不直接通信，并且移动终端只具备收发功能，不具备转发功能。而a dh o c 网络由 移动主机构成，移动主机之间可以直接通信，而移动主机不仅收发数据，同时还转 发数据。此外目前的移动通信系统主要为用户提供语音通信功能，通常采用电路交 换，拓扑结构比较稳定。而a dh o c 网络使用分组转发技术，主要为用户提供数据通 信服务，拓扑结构易于变化。 1 3a d h o e 网格节能问题 a d h o c 网格通常使用电池供电，这使得a d h o c 网格的节能问题变得非常重要。 a d h o c 网格的节能问题就是要在满足用户所希望的性能的同肘，让网格在电池耗尽 前完成尽可能多的工作。 a d h o c 网格的节能方式有很多方面。构成a d h o c 网格能量消耗的两个主要部分 是本地计算和通信，其中一个节能方式就是找到这两部分能量消耗的最佳平衡点。 也就是说，对于节点的某项计算，是在节点本地完成还是传送到其他节点去完成更 节约能量的问题。问题的答案取决于这项计算的相对执行时间，以及用来计算和通 讯所需要的能量。 a d h o c 网格的一个非常重要的节能方式是节能路由。节能的路由算