（计算机软件与理论专业论文）面向机器人导航控制分布式计算的任务调度方法研究.pdf

中南大学硕士学位论文摘要 摘要 未知环境下移动机器人的导航控制涉及大量的图像数据处理。 为保证导航控制系统的有效性与实时性，需要使用分布式计算系统对 图像进行并行处理。 任务调度是分布式计算系统的关键问题之一，常用的任务调度算 法如表调度、b a c k f i l l i n g 、f c f s 等在系统轻负载时能到达较好的效果， 但在重负载时调度效果并不理想。为此需要对调度算法加以改进，以 更好地满足系统有效性和实时性的要求。 本文提出了一种基于代理的分布式计算框架一一n c d c s ( n a v i g a t i o na n dc o n t r o ld i s t r i b u t e dc o m p u t i n gs y s t e m ) 。该计算框架 采用分层的结构，将系统划分为资源层、代理层、用户层。资源层由 众多的计算节点构成；代理层包括有两类代理，资源代理和资源信息 服务代理；用户层主要由客户节点构成，n c d c s 系统上运行的任务 由客户节点提交。n c d c s 系统采用o p e n l d a p 结合j a v a r m i 、j a v a s o c k e t 编程实现。 本文提出了一种任务调度方法一一s a g m b ( s c h e d u l i n g a l g o r i t h mb a s e do ng e n e t i ca l g o r i t h ma n dm u l t i p l e q u e u eb a c k f i l l i n g ) ， 该算法首先运用j r p a ( j o b sr u n t i m e p r e d i c t i o na l g o r i t h m ) 任务预测算 法对任务执行时间进行预测，再根据系统中各个主机的系统资源利用 率自适应地运用遗传算法结合多队列b a c k f i l l i n g 方法进行任务调度。 通过在n c d c s 系统上对多队列b a c k f i l l i n g 、f c f s 和s a g m b 任务调度算法的性能测试表明，三种调度算法在轻负载时性能相当， 但在重负载下s a g m b 调度算法相对于其他两种算法性能有明显的 提高，并且在重负载下该系统的加速比也比较理想。 综上所述，采用s a g m b 调度算法的n c d c s 系统能够实现资源 的优化分配，减少任务的平均执行时间，从而为整个移动机器人导航 控制系统高效实时的运行提供了保证。 关键词导航控制，分布式计算，任务调度算法，遗传算法，b a c k f i l l i n g ， 中南大学硕士学位论文摘要 a bs t r a c t al a r g en u m b e ro fi m a g ed a t a c o n t r o l l i n gam o b i l er o b o ti nu n k n o w n m u s tb e p r o c e s s e dt i m e l y f o r e n v i r o n m e n t i no r d e rt oe n s u r e n a v i g a t i o na n dc o n t r o ls y s t e m sr e a lt i m ea n dh i g h p e r f o r m a n c e ，t h e i m a g ed a t as h o u l db ep a r a l l e lp r o c e s s i n gi nad i s t r i b u t e dw a y t a s ks c h e d u l i n gi so n eo fk e yp r o b l e m si nd i s t r i b u t e dc o m p u t i n g s y s t e m s o m ep o p u l a rs c h e d u l i n ga l g o r i t h m s ，s u c ha st a b l es c h e d u l i n g ， b a c k f i l l i n ga n df c f s ，c a no b t a i nag o o d r e s u l tw h e nt h el o a di sl i g h t ，b u t w h e nt h el o a dg r o w s ，t h es c h e d u l i n gr e s u l ti su n s a t i s f a c t o r yb e c a u s et h e y c a nn o to p t i m i z et h er e s o u r c ed i s t r i b u t i o n s ow em u s ti m p r o v et h e s c h e d u l i n ga l g o r i t h m t ow o r ko u tac o r r e c ts o l u t i o nt om a s si n f o r m a t i o n p l e n t i f u lt a s k si n t h e n a v i g a t i o n c o n t r o ls y s t e m ，n c d c s ( n a v i g a t i o na n dc o n t r o l d i s t r i b u t e dc o m p u t i n gs y s t e m ) h a sb e e np u tf o r w a r di nt h i st h e s i s ，w h i c h i sb a s e do nr e s o u r c eb r o k e r t h es y s t e mi sh i e r a r c h i c a ls t r u c t u r e w h i c h d i v i d e di n t ot h r e el a y e r s r e s o u r c el a y e r , b r o k e rl a y e r , u s e rl a y e r r e s o u r c el a y e rc o n s i s t so fl o t so fc o m p u t en o d e s ；b r o k e rl a y e ri n c l u d e s r e s o u r c eb r o k e ra n dr e s o u r c ei n f o r m a t i o ns e r v i c e ；u s e r l a y e ri s c o m p o s e do fc l i e n tn o d e s w h i c hc a ns u b m i tt a s k st on c d c s n c d c si s i m p l e m e n t e d w i t ho p e n l d a p , j a v ar 量a n dj a v as o c k e t s a g m b ( s c h e d u l i n ga l g o r i t h mb a s e do ng e n e t i ca l g o r i t h ma n d m u l t i p l e - q u e u eb a c k f i l l i n g ) h a sb e e nd e v e l o p e df o rn c d c s i nt h i st h e s i s f i r s t l y , t h es c h e d u l i n ga l g o r i t h mp r e d i c t st h ej o b s r u n t i m ei nj p r a ( j o b s r u n t i m ep r e d i c t i o na l g o r i t h m ) ，t h e n a d a p t i v e s c h e d u l e st a s k su s e d g e n e t i ca l g o r i t h mc o m b i n i n gw i t hm u l t i p l e q u e u eb a c k f i l l i n g t h ep e r f o r m a n c et r i a lo fb a c k f i l l i n g f c f sa n ds a g m bi nn c d c s s h o w st h a tt h es c h e d u l er e s u l ti sc l o s ew h e nl o a di sl i g h t 。b u ts a g m b s p e r f o r m a n c ei m p r o v e sg r e a t l yw h e nl o a di sh e a v y i naw o r d ，n c d c sw i t l ls a g m bc a no p t i m i z et h er e s o u r c e d i s t r i b u t i o n ，r e d u c et h ea v e r a g et a s k sr u n - t i m e ，t h e r e b yi tc a ne n s u r et h e h i g hp e r f o r m a n c ea n dr e a lt i m e o fn a v i g a t i o nc o n t r o ls y s t e m i i 中南大学硕士学位论文摘要 k e yw o r d s ：n a v i g a t i o nc o n t r o l ，d i s t r i b u t e dc o m p u t i n g ，j o bs c h e d u l i n g a l g o r i t h m ，g e n e t i ca l g o r i t h m ，b a c k f i l l i n g i i i 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢 的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不 包含为获得中南大学或其他单位的学位或证书而使用过的材料。与我 共同工作的同志对本研究所作的贡献均已在论文中作了明确的说明。 作者签名： 关于学位论文使用授权说明 本人了解中南大学有关保留、使用学位论文的规定，即：学校 有权保留学位论文，允许学位论文被查阅和借阅；学校可以公布学位 论文的全部或部分内容，可以采用复印、缩印或其它手段保存学位论 文；学校可根据国家或湖南省有关部门规定送交学位论文。 作者签名：导师签名超墨日期：竺年月兰日 中南大学硕士学位论文第一章绪论 1 1 研究背景与意义 1 1 1 移动机器人导航控制 第一章绪论 随着科学技术的发展，人类研究和活动的领域有了很大的扩展，从海洋、陆 地到太空都有了人类的足迹。利用移动机器人对太空或海底等未知环境进行探测 已经成了开采与探测的一项重要技术。未知环境下移动机器人的导航控制。也就 成了亟待解决的关键问题。未知环境下移动机器人的导航控制主要包括环境建 模、定位、导航控制器的学习与优化、故障诊断、在线运动规划与控制等问题， 这些问题中都需要处理大量的数据，特别是在环境建模和运动规划过程中要涉及 到大量的图像处理，如图像边缘检测，全景图匹配和生成以及运动目标的检测等。 图像处理方面有一个长期困扰图像界的棘手难题，那就是速度问题，这主要是由 图像数据的特点和图像处理算法的复杂性引起的【5 “。图像并行处理技术就是在这 样的环境下出现和发展起来的。图像并行处理技术可以克服传统单处理器处理图 像时的一些缺陷，较大地提高图像处理的速度。并且图像并行处理技术在军事、 工业自动化、科学研究等领域都有着很大的应用空间。在高性能大型计算机缺乏， 单台主机又不足以处理的情况下，为了要达到在线控制和实时控制的要求就必须 寻找其他替代方案，分布式计算系统自然就成了解决该类问题的首选。 1 1 2 分布式处理技术 计算机网络的迅速发展以及海量数据应用的不断增加使得分布式并行计算 越来越普及。同时，由于微处理器性能的迅速增强，以及高性能网络的不断出现， 使得基于网络的计算比传统的基于多处理器的计算具有更好性能和实用价值。 集群系统和分布式处理系统是两种常见的基于网络计算的系统。集群计算系 统是利用高速通信网络将一组高性能工组站或p c 按某种结构连接起来，在并行 程序设计和可视化人机交互集成环境支持下，统一调度，协调处理，实现高效并 行处理的系统【17 1 。但是对于用户来说，集群计算系统由于需要较多软、硬件支持， 如快速通信协议和服务，高性能网络( 如千兆以太网或m y r i n e t ) 等，仍然是一 。国家自然科学基金重点项目“未知环境下移动机器人自主导航控制的理论与方法的研究”( n o6 0 2 3 4 0 3 0 ) 。 1 中南大学硕士学位论文第一章绪论 个比较昂贵的系统；而且还需要专用的中间件或并行程序开发软件包，如p v m ， m p i 等的支持。分布式计算系统与集群系统不同，它建立在现有网络的基础上， 充分利用网络资源可支持的各种服务，不需要再增加额外的硬件开支，因此它的 适用范围比集群系统更广泛7 】。除了上述两类系统外，还存在一些其他的解决方 案，如高性能并行处理计算机，计算网格等。对于高性能并行处理计算机，价格 过于昂贵一个巨大使用障碍：计算网格虽然是分布式计算的最新发展方向，但其 主要专注于大规模资源整合与共享，进行小规模分布式计算，网格系统效率并不 很高。 目前已有许多利用分布式计算系统进行计算的项目，例如：r s a f a c t o r i n g w e b 项目用于破译r s a 密码；g i m p 项目利用i n t e r n e t 发现 m e r s e n n e 素数；z u r i c h 大学计算机科学系的v s t r a n m p e n 利用i n t e m e t 解决 分子系列分析问题；s e t i h o m e 项目，致力于寻找外星空间智能1 4 2 1 。 从上面列举的项目可以看到，使用工作站和个人计算机进行分布式并行计算 处理是一个非常有前景的途径。当然，分布式计算也提出了大量困难的课题，例 如系统的架构、并行算法的设计、任务的划分、通信的协调和同步、任务的调度 等1 4 2 】。这些问题解决的好坏直接关系着分布式计算系统的成败。 在上述分布式计算系统面临的各种问题中，任务调度是最为主要的问题之 一。它主要解决当个任务分解为一组可并行运行的子任务后，合理和优化的分 配到分布式系统中的各个处理单元。分布式系统的任务调度问题如果得不到很好 的解决，则有可能导致分布式系统计算效率低下，甚至导致整个计算失败。任务 调度这一步骤对发挥系统的并行计算能力、提高系统吞吐量具有非常重要的影 响。良好的调度算法可以充分运用系统中每个处理机的计算能力。 1 2 研究现状 分布式计算系统经过较长时期的发展，已经存在一些常用的框架模型，主要 包括客户n 务器模型、多层分布式模型以及对等模型等【b l 。其中客户n 务器模 型是分布式处理系统中十分常用的体系结构，也是历史上重要的体系结构，现在 仍被广泛使用，但随着网络业务的不断增多，传统的客户n 务器体系模型在运 行效率、系统网络安全性和系统升级能力等方面显示出很大的局限性【1 5 】。多层分 布式结构是为了解决传统客户服务器模式中的不足而提出来的新分布式计算构 架，该模型引入了中间层服务器，以增强软件系统间的互操作能力【1 4 】。在对等模 型结构中，为了完成一项分布式活动或计算，所有的进程扮演相同的角色，作为 对等方进行协作交互，不区分客户和服务器。对等模型是一种用于不同p c 用户 之间、不经过中继设备直接交换数据或服务的技术。它打破了传统的客户n 务 中南大学硕士学位论文第一章绪论 器模式，在对等网络中，每个节点的地位都是相同的，具备客户端和服务器双重 特性，可以同时作为服务使用者和服务提供者。 除了对分布式计算系统的架构研究外，调度问题作为分布式计算的核心问题 之一，其研究工作在国内外也都十分活跃。很多研究者使用了d a g 作为任务的 描述工具，国内也已经有关于用d a g 描述任务的文献【2 】1 3 1 。另外，p e t r i 网5 】【6 】 是一种通用模型，国内外已经有了将p e t r i 网用于资源管理和任务调度的研究( 国 家自然科学基金项目( 6 9 8 7 3 0 1 2 ) “资源管理和任务调度的随机p e t r i 网模型”，项 目主持人林闯，1 9 9 9 年1 月- - 2 0 0 1 年1 2 月) 。在这两种方法中，用d a g 描述 任务简单明了，层次结构清晰：p e t r i 网便于描述存在于条件与事件问的关系，在 描述和研究具有并行、异步、分布式和随机性等特征的信息方面功能强大。一般 说来，d a g 和p e t r i 网适合解决静态特点问题，属于静态调度范畴。目前动态调 度的研究重点已从静态调度的编译程序转移到处理机在执行任务时动态负载平 衡上来，已提出了发送者主动和接收者主动以及双向主动算法。使用发送者主动 算法，过载的节点即负载过多的节点，可以把一个或多个任务传给低载节点；使 用接收者主动算法，低载的节点主动向过载的节点请求任务；使用双向主动算法 则是发送者和接收者都可以启动负载的传送【7j 。 在动态调度中，调度算法自身的消耗会直接影响到系统的性能，因此一个重 要的问题时调度算法在什么地方执行、调度信息存储在什么地方以及调度算法所 使用的技术到底有多复杂。基于这种考虑，有的学者把调度问题分为分布调度和 集中调度两种情况【s j 【”。 在分布式调度中，调度任务和调度信息是分布在各处理机的存储器中。发送 者主动和接收主动的分布调度策略都采用一个处理机缓冲池来接受邻接处理机 的信息。分布调度策略还普遍采用一种方法，允许空闲处理机执行同一个任务， 使用这种方法时必须使用某种同步机制来限制在某一时刻只能有一个处理机来 存取这个队列。虽然访问共享队列和从共享队列中删除一个或多个任务增加了调 度系统的耗费，但从调度质量中挽回了一些损失。 集中调度技术把全局信息存储在一个中心位置，使用这种技术要牺牲一个或 多个处理机资源，但能够做出比较全面的调度。现有的集中调度技术的缺点是存 取共享信息和请求任务执行时存在冲突问题，这种冲突使得完成集中调度的处理 机成为系统的瓶颈，文献【1 0 l 提出了一种分级调度结构，减少了瓶颈现象。 1 3 研究内容 分布式系统经过较长时期的发展，已经存在一些常用的框架模型，主要包括 客p n 务器模型、多层分布式模型以及对等模型等1 3 】。但是这些框架模型不是 中南大学硕士学位论文 第一章绪论 一成不变的，也不是所有的问题都可以直接套用的。为了达到较好的处理效果， 必须针对具体的问题设计相应的分布式框架模型。 针对移动机器人导航控制中信息处理量大、任务多，依靠单台主机不能满足 整个系统速度和性能要求的情况，本文提出了一种基于代理的分布式计算框架一 i n c d c s ( n a v i g a t i o na n dc o n t r o ld i s t r i b u t e dc o m p u t i n gs y s t e m ) 。n c d c s 分为 三个层次，资源层、代理层、用户层。资源层由众多的计算节点构成；代理层包 括有两类代理，资源代理( r e s o u r c eb r o k e r ) 和资源信息服务代理( r e s o u r c e i n f o m m i o ns e r v i c e ) ，资源代理是运行任务调度算法的场所资源信息服务代理 主要负责收集各个计算节点的各种状态信息，如处理器利用率信息，内存使用信 息等1 4 1 。 对于任务调度，除少数小规模问题存在p 算法外，大量调度问题属于n p 完 全问题1 3 “，至今没有找到可以精确求得最优解的多项式时间算法，鉴于构造性方 法质量较差且缺少柔性，遗传算法就成了解决此类问题的首选。当然遗传算法还 存在本身开销较大，执行时间较长等问题。为此本文提出一种基于遗传算法的任 务调度方法一s a g m b i i 叫fs c h e d u l i n ga l g o r i t h m b a s e do ng e n e t i ca l g o r i t h ma n d m u l t i p l e q u e u eb a c k f i l l i n g ) 。该调度算法属于动态调度算法的范畴，其以资源代 理为基础，首先运用j r p a ( j o b sr u n t i m ep r e d i c t i o n a i g o r i t h m ) 任务预测算法对任 务执行时间进行预测，该预测算法利用历史任务的执行时间来预测现行任务的执 行时间，首先通过模板和相似度来对历史任务进行分类，然后利用模板确定现行 任务所属的类别，最后用此类任务执行时间的平均值作为预测值。确定了任务的 执行时间后，再根据系统中各个主机的系统资源利用率自适应的运用遗传算法结 合多队列b a c k f i l l i n g 方法进行任务调度，达到最小化任务执行时间( m i n i m u m e x e c u t i o nt i m e ) 的要求，最终实现资源的优化分配，较好的满足了机器人导航 控制中的实时性要求。课题研究的内容来源于国家自然科学基金重点项目“未知 环境下移动机器人自主导航控制的理论与方法的研究”( 批准号：6 0 2 3 4 0 3 0 ) 。 1 4 论文结构 本文的结构安排如下： 第一章主要介绍了论文的研究背景、意义，研究现状，本文所做的主要工作 以及论文的结构安排。 第二章着重介绍导航控制分布式计算系统_ n c d c s 的研究与设计。本章 首先介绍和比较了现有几种常用进行并行计算的方法，然后详细介绍了本文所提 出的基于资源代理的分布式计算系统的架构_ n c d c s 的设计。 第三章主要讨论n c d c s 系统的任务调度方法s a g m b 。本章在n c d c s 中南大学硕士学位论文 第一章绪论 系统的基础上，提出了一个适合于该系统的任务调度方法s a g m b 。该方法 以资源代理为基础，首先对任务执行时间进行预测，然后运用遗传算法结合多队 列b a c k f i l l i n g 方法进行任务调度，达到最小化任务执行时间( m i n i m u me x e c u t i o n t i m e ) 的要求，最终实现资源的优化分配，满足了机器人导航控制中的实时性要 求。 第四章主妻介绍了n c d c s 系统的实现。本章着重讨论了实现过程中所采用 的技术以及设计方案。 第五章在全面概括本文所开展的工作的同时还对该系统中存在的一些不足 以及将来所需要开展的工作做了总结和展望。 2 1 并行处理系统综述 在实际应用中，经常需要比串行计算机所提供的能力更强的计算能力。为了 提供更强大的计算能力，一种方法是提高处理器和其他运算部件的运算速度。但 是，由于处理器和其他各种运算部件的发展受到光学、热力学定律等各方面的限 制，这个方法只在一定程度上可行。另一个可行的办法就是将多个处理器连接起 来，使用它们合在一起的计算能力。这种系统就是并行计算系统，它将计算任务 分布在多个处理器上运行。 正如p f i s t e r 所指出的，改善系统性能的途径有三条1 1 7 】： 更努力的工作 更有创造性的工作 获得帮助 其中更努力的工作指的就是使用高性能的处理器和运行部件：而更有创造性 的工作指的是改进解决某一问题的算法和技术；获得帮助主要就是使用多计算机 来协同解决特定的任务。 本小节主要介绍p f i s t e r 所提出的并行处理的方法，并对现有的几种并行处理 系统，如集群计算系统，分布式处理系统的研究现状及其发展进行介绍。 2 1 1 集群计算系统 集群是一种并行或分布式处理系统，由很多连接在一起的独立计算机节点 组成，像一个单独集成的计算机资源一样协同工作。 组成集群的计算机节点可以是一个单处理器或多处理器的系统( 如p c 、工 作站或s m p 等) ，拥有内存、i 0 设备和操作系统。一个集群一般是连接在一起 的两个或多个计算机节点，这些计算机节点在物理上可以是集中的也可以是分散 而且通过网络连接在一起的。一个连接在一起的计算机集群对于甩户和应用稔序 中南大学硕士学位论文第二章n c d c s 的研究与设计 来说像一个单一的系统。这样的系统可以提供一种价格合理的并可获得所需性能 和优势的解决方法，这在以往只能通过共享内存系统来达到。典型的集群系统的 结构如图2 - 1 所示。 e 重面 二巫垂巫二 从图2 1 可以了解到构成一个计算机集群系统需要以下一些必要的部件： 计算节点( 多个) 高性能网络( 如千兆以太网或m y n n e t ) 网络接口卡 快速通信协议和服务 集群中间件 并行编译环境和工具( 如p v m 和m p i 技术) 其中计算节点可以是常见的p c ，或者工作站以及s m p 等，这些节点是执行 集群任务的场所；网络接口卡则担当着通信处理器的任务，主要负责计算节点间 通过高性能网络传送和接收数据包的任务。 集群之问通信的一个基本要求是快速、高效，但一般说来，操作系统在源和 目标之间的通信包含了复杂的操作，如在不同层之间消息的传递、数据复制、保 护性检查和可靠性通信检测等，这些操作消耗较多的时间。所以必须通过专门的 通信协议和软件以及专用的网络来提供快速而可靠的节点间数据通信的手段，并 且集群需要能够通过网络接口和通信协议，提供绕过操作系统的，可以由用户直 接访问的接口。应用这些通信接口集群就可以大大降低了操作系统对通信速度的 额外影响，达到高效，可靠的目的。 下面简要介绍集群相关的一些技术1 7 】： 1 集群互联 集群节点间可以通过使用标准网络协议( 如t c p d p ) 或低层协议( 活动消 息) 来进行通信。但在大多数情况下通过标准以太网( 带宽1 0 m b s ，延迟1 0 0 u s 左右) 进行集群间通信，并不足以提供足够的性能。特别是普通的以太网在带宽 中南大学硕士学位论文第二章n c d c s 的研究与设计 和延时上都不能和目前工作站的计算能力相平衡。为了要提高性通常需要用到以 下几种新型的高性能的网络。 ( 1 ) 快速以太网和千兆以太网 快速以太网是标准以太网的改进，提供1 0 0 m b s 的带宽，并为现有以太网提 供路径。现在最高性能的以太网是千兆以太网，它有两个突出的特点。一是它继 承了以太网简单，可以平滑的过渡到千兆每秒的速度。二是它提供了非常高的带 宽来支持多个快速以太网段，支持高速服务器连接、开关基干网、高速工作组网 络。 ( 2 ) m y r i n e t 网络 m y r i n e t 是m y i c o m 提供的1 2 8 g s 全双工内部连接网络，是一个专用的、高 性能的内部连接。m y r i n e t 使用低延迟开通式路由开关，通过自动映射网络配置 来提供容错。m y r i n e t 支持l i n u x 和n t 。除了对t c p i p 支持，还支持m p i 和 m p i c h 运行，如b e r k e l e y 的活动消息，它提供低于1 0 微秒的延迟。比起快速以 太网来说，m y r i n e t 价格稍贵，但它拥有一些以太不具备的优点：极低的延迟、 高吞吐量等。 2 集群资源管理与调度 集群资源管理和调度是使计算机间分布式应用程序达到最大吞吐量的操作， 它使资源的有效和高效利用成为可能。执行资源管理与调度的软件包括两个部 分：资源管理器和资源调度器。资源管理器主要处理资源定位和计算资源的配置、 验证以及进程生成和迁移等。资源调度器部件着重处理应用程序队列等任务以及 资源分配。 集群中的资源管理与调度结构是客户一服务器系统。简单的说，每个计算机 共享运行服务器守护进程的计算资源。这些守护进程中保存着最新的资源列表， 列表中存储它所在的管理和调度环境信息。 资源管理和调度系统提供对用户的中间件服务，使工作站、s m p 和专用并 行平台的多种环境可以方便而有效的使用。其提供的服务包括有： 负载平衡 在一个特定的结构中作业可以分布在所有可用的计算平台，这使资源得以 有效的利用。 进程迁移 使进程可以在系统中的多个计算节点之间移动。 检查点 这是程序执行状态的一个瞬时图，使程序在必要的时候可以在同一点重新开 始执行。 中南大学硕士学位论文第二章n c d c s 的研究与l 设计 容错 通过对作业和资源的管理，系统可以提供不同层次的容错，容错可以使发生 故障的作业再启动，保证了作业的完成。 3 编程环境和工具 集群的并行计算编程通常都需要标准的编程工具和语言。消息传递库使程序 可以为分布式存储系统编写有效的并行程序。该库提供了创建和配置消息环境以 及发送和接收数据包的常用程序。现在，最常用的两个消息传递系统是o a kr i g e 国家实验室的p v m ( 并行虚拟机) 和m p i 研讨会定义的m p i ( 消息传递接口) 。 p v m 既是应用环境又是消息传递库，可以用来从高端的超级计算机到工作 站集群的各种环境中运行并行程序。m p i 标准融合了大部分在当时被认为是最常 用的消息传递系统中的最优秀的部分。m p i 设计的目的是可移植性、有效性和功 能性。该标准只定义了消息库，而将其他如进程的初始化和控制等留给了开发者 去定义。 集群技术的研究已经较为成熟，目前已有一些实用的集群系统，其中主要包 括有b e r k e l e y 的n o w ( n e t w o r k so fw o r k s t a t i o n ) 1 7 l 项目，高性能虚拟机项目 ( h p v m ) ，b e o w u l f 项目以及s o l a f i sm c 项目等。 这些集群计算项目中最为主要的问题是解决运行并行应用程序所引起的瓶 颈问题。在不出现故障的情况下，主要的瓶颈不是计算资源，而是怎样提供低延 迟，高带宽的连接和怎样以有效的低层通信来提供高层a p i 。由于集群系统对于 互联的网络有较高的要求，并且需要专门的编程环境和工具，价格也较为昂贵。 2 1 2 分布式处理系统 分布式处理系统是组件分布在网络计算机上且通过消息传递进行通信和动 作协调的系统【1 3 1 。资源共享是形成分布式系统的主要动力。资源可以由服务器管 理并由客户访问，或封装成对象，由其他客户访问。 系统组件( 应用、服务器和其他进程) 之间的责任的划分和网络上计算机组 件的放置是分布式系统设计最重要的方面。这些对系统的最终性能、可靠性和安 全性有较大的影响。下面将讨论几种常见的分布式处理系统模型【”】。 1 客户朋艮务器模型 客户朋艮务器模型是分布式处理系统中最常用的体系结构，也是历史上最重 要的体系结构，现在仍被广泛使用。图2 2 给出了客户访问由服务器管理的资源 时，客户进程与在单独主机上的服务器进程交互的简单结构。 在客户服务器体系中，客户请求服务，服务器提供服务。当然服务器也可 以是其他服务器的客户。在当今的i n t e m e t 上，存在大量的服务器w e b 服务 9 中南大学硕士学位论文 第二章n c d c s 的研究与设计 _ _ _ _ _ _ _ - _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ - _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ - - - _ - _ _ _ _ - - _ _ _ _ _ - _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ - - _ _ h - _ ，_ _ _ _ _ _ 一 器，邮件服务器，f t p 服务器等等。 图2 - 2 客户j t & 务器模型 随着基于网络业务的不断增多，传统的客户服务器体系的分布式应用方式在 运行效率、系统网络安全性和系统升级能力等方面显示出很大的局限性【1 5 】。 2 多层分布式模型 为了解决分布式计算环境( d c b ，d i s t r i b u t e dc o m p u t ee n v i r o n m e n t ) 中不同硬 件设备和软件系统的互联，增强网络间软件的互操作性，解决传统客户服务器模 式中的不足等问题，提出了新的分布式计算构架多层分布式结构，引入了中 间层服务器，以增强软件系统问的互操作能力，使构造灵活的分布式应用系统成 为可能。采用这种结构的好处，除了增加企业对象的重复使用性外，整个系统的 维护升级成本都立刻降低下来了。 多层分布式结构中最为常见的一种是三层结构计算模型，其在客户与服务器 之间插入了一个中间层应用服务器。中间层除了能响应客户端的各种请求 外，还能进行负载平衡等其他高级功能【1 4 1 。其结构模型如图2 3 所示。 尉2 - 3 三层结构计算模型 3 对等模型 在对等模型结构中，为了完成一项分布式活动或计算，所有的进程扮演相同 的角色，作为对等方进行协作交互，不区分客户和服务器。图2 - 4 给出了对等进 程的结构模型的网络通信方式。 对等模型是一种用于不同p c 用户之间、不经过中继设备直接交换数据或服 务的技术。它打破了传统的客户j l e 务器模式，在对等网络中，每个节点的地位 都是相同的，具备客户端和服务器双重特性，可以同时作为服务使用者和服务提 中南大学硕士学位论文第二章n c d c s 的研究与设计 供者。由于对等模型的飞速发展，互联网的存储模式将由目前的“内容位于中心” 模式转变为“内容位于边缘”模式，改变i m e m e t 现在的以大网站为中心的状态， 重返“非中心化”，将权力交还给用户。 图2 - 4 对等结构模型 对等模式的变化经历了集中式、分布式和混合式3 个阶段【2 1 1 。对等模式技术 起源于文件交换技术( 即p 2 p 技术1 2 1 1 ) ，在其发展过程中，文件交换技术的演变 最具代表性，下面我们就以典型的p 2 p ( p e e rt op e e r ) 文件交换软件为例来研究对 等模式的几种主要形式。 ( 1 ) 集中式对等网络 集中式p 2 p 模式由一个中心服务器来负责记录共享信息以及反馈对这些信 息的查询；每一个对等实体要对它所需共享的信息以及进行的通信负责，根据需 要下载其他对等实体上的信息。这种形式具有中心化的特点，但是它不同于传统 意义上的c l i e n t s e r v e r 模式。因为传统意义上的c l i e n t s e r v e r 模式采用的是种 垄断的手段，所有资料都存放在服务器上，客户机只能被动地从服务器上读取信 息，并且客户机之间不具有交互能力；而集中式p 2 p 模式则是所有网上提供的资 料都存放在提供该资料的客户机上，服务器上只保留索引信息，此外服务器与对 等实体以及对等实体之间都具有交互能力。 集中目录式p 2 p 模型存在一些问题，主要表现为： 中央服务器的瘫痪容易导致整个网络的崩溃，可靠性和安全性较低； 随着网络规模的扩大，中央目录服务器维护和更新的费用将急剧增加， 所需成本过高； 缺乏有效的强制共享机制，资源可用性差。 ( 2 ) 分布式对等网络 在分布式对等网中，对等机通过与相邻对等机之间的连接遍历整个网络体 系。每个对等机在功能上都是相似的，并没有专门的服务器，而对等机必须依靠 它们所在的分布网络来查找文件和定位其他对等机。 分布式对等网络模型也存在很多弊端，主要表现在以下方面： 搜索请求要经过整个网络或者至少是一个很大的范围才能得到结果， 中南大学硕士学位论文第二章n c d c s 的研究与设计 因此，这种模式占用很多带宽，而且需要花费很长时间才能有返回结 果。 随着网络规模的扩大，通过扩散方式定位对等点及查询信息的方法将 会造成网络流量急剧增加，从而导致网络拥塞，最终使总个网络被分 片，使得查询访问只能在网络很小的范围内进行，因此，网络的可扩 展性不好，不适合大型网络。 纯分布式的p 2 p 模式很难被企业所利用，因为它缺少对网络上的用户 节点数以及对他们提供的资源的一个整体把握。 安全性不高，易遭受恶意攻击，如攻击者发送垃圾查询信息，造成网 络拥塞等。 这种无中心、纯分布式系统不再是简单的点到点通信，而是更高效、更复杂 的网络通信；e d o n k e y 和e m u l e 等软件引入了强制共享机制，在一定程度上避免 了第一代p 2 p 纯个人服务器管理带来的随意性和低效率。 ( 3 ) 混合p 2 p 网络 集中式p 2 p 有利于网络资源的快速检索，并且只要服务器能力足够强大就可 以无限扩展，但是其中心化的模式容易遭到直接的攻击；分布式p 2 p 解决了抗攻 击问题，但是又缺乏快速搜索和可扩展性。混合式p 2 p 结合了集中式和分布式 p 2 p 的优点，在设计思想和处理能力上都得到了进一步的优化。它在分布式模式 的基础上，将用户节点按能力进行分类，使某些节点担任特殊的任务。这些节点 共分为3 种： 用户节点：普通节点，它不具有任何特殊的功能。 搜索节点：处理搜索请求，从它们的“孩子”节点中搜索文件列表。 索引节点：连接速度快、内存充足的节点可以作为索引节点。索引节点 用于保存可以利用的搜索节点信息，并搜集状态信息，维护网络结构信 息。 一个节点可以既是搜索节点又是索引节点。用户节点可以选择搜索节点作为 它的“父”节点，如果“父”节点接受该用户节点作为它的“孩子”的话，那么 该用户节点就可以提交其所要共享的列表给它的“父”节点。在第三代p 2 p 的软 件体系结构中，采用了混合式p 2 p 。这种模式的关键之一是引入了索弓f 节点，索 引节点不会直接连接到有版权的资料上，它就像搜索引擎一样，只是搜索和所需 资料相关的地址，至于用户到底连接下载了什么内容则和它无关。这种模式的关 键之二是引入搜索节点，搜索节点管理着所属用户的文件列表。用户节点通过索 引节点获得搜索节点信息，之后用户节点就与获得的搜索节点相连，每一次查询 都通过该搜索节点进行。当用户发出搜索请求后，如果和用户节点直接相连的搜 中南大学硕士学位论文 第二章n c d c s 的研究与设计 索节点查询结果达到某个上限就停止；如果不足这个上限，就向相邻的搜索节点 发出请求，如果查询结果还不够，就继续向外快速发散，直到所有的搜索节点都 被搜索到为止。若所有的搜索节点都被访问过，就意味着整个网络上的节点都被 搜索到了，其速度要其它p 2 p 模式要快【2 0 i 。 2 2n c d c s 系统设计 对于需要处理大量数据的应用，最为常见的两种解决方法是上文提到过的集 群系统和分布式计算系统。从2 1 1 小节可知集群系统需要较多软、硬件支持， 如快速通信协议和服务，高性能网络( 如千兆以太网或m y r i n e t ) 等，代价较为 昂贵；而且需要专用的中间件和并行程序开发包如p v m ，m p i 等，可移植性和 可编程性不好。当然除了上述集群系统外，还存在一些其他的解决方案，如巨型 并行处理计算机，计算网格等。对于巨型机，价格过于昂贵是一个巨大使用屏障： 计算网格虽然是分布式计算的最新发展方向，但其主要专注于大规模资源整合， 进行小规模分布式计算，网格系统效率不高。唯有分布式计算系统可以充分利用 现有网络资源，不需要很多额外硬件支持，可扩展性和实用性都较好。 分布式系统经过较长时期的发展，已经存在一些常用的框架模型( 如2 1 2 所述) 。但是这些框架模型不是一成不变的，也不是所有的问题都可以直接套用 的。为了达到较好的处理效果，必须针对具体的问题设计相应的分布式框架模型。 本文针对移动机器人导航控制提出了一种基于代理的分布式计算框架一一 n c d c s ( n a v i g a t i o na n dc o n t r o ld i s t r i b u t e dc o m p u t i n gs y s t e m ) ，该框架自底向 上分为三个层次，资源层、代理层、用户层。本节将从结构模型，故障模型和安 全模型【l3 】三个方面详细讨论该分布式框架模型。 2 2 1n c d c s 结构模型 n c d c s 自底向上分为三个层次，资源层、代理层、用户层。资源层由众多 的计算节点构成，计算节点需要定期向资源信息服务代理发送k e e p a l i v e 信息 ( h e a r t b e a t 技术【i9 j ) ，已表明自身处于活动状态，为了降低计算节点与资源代理之 间的通信量，在k e e p a l i v e 信息中可捎带资源负载信息( k e e p a l i v e 消息发送间隔 时间的设置在故障模型中详细讨论) 。当资源信息服务代理收到计算节点的 k e e p a l i v e 信息时，它不仅能知道资源处于活动状态，还可以了解资源的各项负载 信息( 如c p u 资源利用率，内存使用情况以及系统中已运行的任务数等) 。这些 负载信息将保存在资源信息服务代理的资源列表中( 采用l d a p 协议实现存储) ， 在资源代理进行任务调度和负载平衡时需要用到。 中南大学硕士学位论文 第二章n c d c s 的研究与设计 代理层包括有两类代理，资源代理( r e s o u r c eb r o k e r ) 和资源信息服务代理 ( r e s o u r c ei n f o r m a t i o ns e r v i c e ) 。 对于单信息服务代理的系统，当有计算节点申请加入分布式计算系统时，在 进行简单的认证后( 在安全模型中详细介绍认证方法) ，对应的计算节点