（模式识别与智能系统专业论文）多机器人通讯网络的路由协议的研究.pdf

南京理工大学硕士学位论文多机器人通讯网络的路由协议的研究 摘要 近年来，多机器人因能更好的协同完成复杂任务而成为机器人学研究的热点。在 多机器人系统中，通讯是其协调运行的基础。本文涉及的多机器人系统具有移动通信、 动态组网的特点并且通常工作在没有现成无线网络基础设施的地方。自组网是解决这 类多机器八通讯问题的种有效途径。自组网路由协议的研究，是自组网研究领域的 热点之一，也是解决多机器人系统通讯的一个重点。本文为更好地解决多机器人系统 的通讯问题进行了研究与探索。 本文首先研究了新型网络自组网，并比较了它与目前常用的蜂窝移动通信网 络的区别。随后研究了两种目前常用的自组网路由协议d s r 和a o d v ，并对它们进 行了定性分析。在借鉴a o d v 路由机制的基础上提出了适用于多机器人通讯网络的 m r c s r p 路由协议。m r c s r p 协议在路由发现时采用源路由思想，而在传输数据包 时没有将完整的路径放到数据包中，而是依赖中间节点动态建立路由。m r c s r p 协 议利用广播包和监听到的数据包来维护本地连接，它利用序列号机制来避免路由环的 产生。随后，本文对协议提出了一些优化方法并对协议进行了定性分析。最后，本文 对协议进行了仿真实验，实验证明，本文提出的m r c s r p 协议是可行的。通过它与 a o d v 性能的比较，更进一步说明m r c s r p 是更适用于多机器人通讯网络的路由协 议。 关链词：多机器人系统无线通讯自组网路由协议a o d v a b s t r a c t硕士论文 a b s t r a c t w i t ht h ed e v e l o p m e n to fr o b o tt e c h n o l o g y , p e o p l ep a ym o r ea n dm o r ea t t e n t i o nt ot h e m u l t i - r o b o t i cs y s t e m i ti sp r o v e dt h a tu s i n gm u l t i - r o b o t i cs y s t e mc a l la c h i e v ec o m p l i c a t e d t a s kb e t t e r c o m m u n i c a t i o ni st h eb a s eo fm u l t i r o b o t i cs y s t e m a dh o cn e t w o r ki sag o o d w a yt os o l v et h ec o m m u n i c a t i o no ft h em u l t i m b o t i cs y s t e mt h ep a p e rs t u d i e s t h em u t i n g p r o t o c o li si m p o r t a n tt ob o t ha dh o cn e t w o r ka n dt h ec o m m u n i c a t i o no ft h em u l t i r o b o t i c s y s t e m ， i no r d e rt 0s o l v et h ec o m m u n i c a t i o no ft h em u l t i m b o t i c s y s t e m t h ep a p e rf i r s t s t u d i e st h ea t t r i b u t e so fa dh o cn e t w o r ka n d c o m p a r e si tw i t hg s m a n dg p r s s e c o n d ，t h e p a p e rs t u d i e st w or o u t i n gp r o t o c o l su s e di na dh o cd s r a n da o d v t h e nan e wa l g o r i t h m f o rr o u t i n g ，w h i c hi sn a m e dm r c s r pi sp r o p o s e d r o u t ed i s c o v e r yo fm r c s r pu s e s s o u r c em u t i n g ，b u tt h en o d ed o e s n tk e e pt h ew h o l er o u t e si ni t sr o u t et a b l ea n dm r c s r p r e l i e so nd y n a m i c a j j ye s t a b l i s h i n gr o u t et a b l ee n t r i e sa ti n t e r m e d i a t en o d e s t h en o d eu s e s t h eb r o a d c a s t sf r o mi t s n e i g h b o r sa n dt h ed a t ap a c k e t si t h e a r st om a n a g et h el o c a l c o n n e c t i v i t y i tu s e sad e s t i n a t i o ns e q u e n c en u m b e rf o re a c hr o u t ee n t r y u s i n gd e s t i n a t i o n s e q u e n c en u m b e r se n s u r e sl o o p - f r e em u t i n g s o m eo p t i r r d z a t i o n sa r ea l s op r o p o s e di nt h e p a p e r t h ep a p e ra l s oi n c l u d e sa ne v a l u a t i o nm e t h o d o l o g ya n ds i m u l a t i o nr e s u l t st ov e r i f y t h eo p e r a t i o no fm r c s r p b yc o m p a r i n gt h ep e r f o r m a n c eo fm r c s r pa n da o d vi t s h o w sm r c s r ps u i t st h em u l t i r o b o t i cs y s t e mb e t t e r k e yw o r d s ：m u l t i r o b o t i cs y s t e m ，w i r e l e s sc o m m u n i c a t i o n ，a dh o c ，m u t i n gp r o t o c o l a o d v i i 声明 本学位论文是我在导师的指导下取得的研究成果，尽我所知，在 本学位论文中，除了加以标注和致谢的部分外，不包含其他人已经发 表或公布过的研究成果，也不包含我为获得任何教育机构的学位或学 历而使用过的材料。与我一同工作的同事对本学位论文做出的贡献均 已在论文中作了明确的说明。 年月日 学位论文使用授权声明 南京理工大学有权保存本学位论文的电子和纸质文档，可以借阅 或上网公布本学位论文的全部或部分内容，可以向有关部门或机构送 交并授权其保存、错阅或上网公布本学位论文的全部或部分内容。对 于保密论文，按保密的有关规定和程序处理。 年月 日 南京理工大学硕士学位论文 多机器人通讯网络的路由协议的研究 1 绪论 1 , 1 选题的背景及意义 多机器人系统的研究始于2 0 世纪7 0 年代。随着机器人应用领域的不断拓展、机器 人工作环境复杂度、任务的加重，对机器人的要求不再局限于单个机器人，多机器人 的研究己经成为机器人学研究的一个热点。多机器人系统不是多个单机器人的简单堆 砌，而是多个机器入的有机组合，它有效的避免了单机器人的不足，充分发挥了群体 机器人的优势。 与单机器人相比，多机器人系统具有以下特点 1 】【1 8 1 ： 1 ) 适合完成复杂任务：对于可分解的复杂的任务及大范围的环境，利用多机器 人系统，可把复杂的任务分解成多个简单的子任务，利用多个机器人协调工作，可以 有效地完成任务，这比单个机器人顺序的完成所有的子任务要快得多： 2 ) 时空分布性：多个机器人可分布在不同的区域内同时作业，也可在不同分布 时间内执行任务，可提高完成任务的效率； 3 ) 功能分布性：在多个机器人中，机器人的功能可以不同，它们的目标任务不 同，但它们可协调工作； 4 ) 感知分布性：在一个区域较大的环境中，多个机器人分布在环境中，各自感 知周围的环境，通过共享感知到的信息，大大扩展了机器人系统对环境的感知范围。 通过成员之间的信息交换，多机器人系统可以更有效和更精确地进行定位，这对于野 外作业的机器人尤其重要； 5 ) 较高的系统可靠性：采用多机器人系统可以将其中的各个成员设计成完成某 项任务的“专家”，而不是设计成完成所有任务的“通才”，这大大降低了单个机器人 设计复杂度，提高了单个机器人的可靠性。而机器人数量上的冗余，也能提高整个系 统的可靠性，不会因为个别机器人的故障导致整个系统的瘫痪。 对于由多个个体机器人组成的群体系统，通信是必不可少的。多机器人系统在执 行某项任务时，为了实现协调与合作，个体机器人的传感器必须提供足够的环境描述 信息以及其他机器人的相关信息，因此机器人个体与个体之间或者上层控制和下层合 作之间的通信是必要的。目前，多机器人系统的通信主要采用广播的方式，即个体机 器人将自己的位置信息和传感器信息以及自己从事的工作信息广播出去，其他个体机 器人可以按自己的需要选择信息，或由主控机器人通过广播分配任务口 。 计算机网络是把各种计算机及网络设备通过通信链路或传输介质连接在一起，以 协议及网络硬件、网络软件使计算机或网络设备进行相互通信，实现信息的通信和资 l 绪论 硕士论文 源的共享【2 斟计算机网络从2 0 世纪6 0 年代开始发展至今，已形成从小型局域网到全 球性的广域网的规模。在过去的2 0 多年星，计算机网络技术取得了惊人的发展。 计算机网络的发展为多机器人系统通讯提供了基本解决方案，也促进了多机器人 系统的发展。目前，很多从事多机器人系统研究的机构都开始利用和改进现有的网络 技术，试图利用现有的网络技术来解决多机器人系统的通讯问题。 自组网是一种有特殊用途的对等式网络，又被称为多跳网络、无固定基础设施的 网络或者自组织网络【2 9 】。自组网是由一组带有无线收发装置的移动节点组成的一个多 跳的、临时性的自治系统【3 ”。在自组网中，移动终端同时承担主机和路由器两种功能。 也就是说参与自组网的移动终端之间存在着某种协同工作的关系，这种关系使得每个 终端都要承担为其它终端进行分组转发的义务，也就是需要运行合适的路由协议 3 4 】。 自组网路由协议的研究，作为自组网研究领域的热点之一，一直受到了广泛的关 注。其路由选择问题比传统的相关问题更加富有挑战性 3 4 】。 本文结合国防科工委预研基金项目，对多机器人系统通讯进行初步研究。本文涉 及的多机器人系统具有移动通信、动态组网的特点，而且通常在野外没有现成网络基 础设施的地方工作。自组网是解决这类多机器人通讯问题的一种有效途径，它能够为 需要协同工作的多个机器人提供种通信支撑环境。 本文以自组网理论为基础，结合多机器人系统的特点，研究适用于多机器人通讯 网络的路由协议。本文在对目前自缉网路由协议研究分析的基础上，提出了m r c s r p 路由协议，并通过仿真实验验证了协议的可行性同时比较了它与a o d v 的性能差别。 1 2 研究现状 自8 0 年代以来，多机器人系统受到国内外普遍的关注。近年来，在i e e er & a 、 i r o s 等著名的国际机器人学术会议上，几乎每次会议都有多机器人系统通讯的专题。 一些机器入学术刊物出版了有关多机器人系统的专刊。许多研究机构都开展了这方面 的研究，代表性的研究项目有：c e b o t 系统【4 j ，m a r t h a 系统【7 、gb e n i 研究的 s w a r m 系统口j 【刮等系统。 f u k u d a 研究的c e b o t ( c e l l u l a rr o b o t i cs y s t e m ) 被认为是对机器人团队协同工作 的首次尝试。它是一个自组织的机器人系统。它由众多的、功能简单的、被称为细胞 元( c e l l ) 的单元组成。c e b o t 能够根据特定的任务和环境来重组织自身，并能够形成 集体的或者说是大量的智能【4 】。 m a r r i h a “用于搬运的多自主机器人系统( m u l t i p l ea u t o n o m o u sr o b o t ss y s t e m f o rt r a n s p o r ta n dh a n d i n ga p p l i c a t i o n ) ”是欧盟设立的一个专门进行多机器人系统研究 的课题。它计划组建一支由1 0 到1 0 0 个自主移动机器人组成的庞大的搬运队伍用于 在港口、机场等地完成搬运工作。m a r t h a 的一个研究目标就是使机器人群体在一 2 南京理工大学硕士学位论文多机器人通讯网络的路由协议的研究 个开放的环境下工作而尽可能少的用到中心控制。目前，他们正在研究如何使机器人 在应对突发事件和障碍时具有更高的自主性【”。多机器人的通讯问题是其中的关键。 因此，他们正在对多机器人的通讯问题进行深入研究，寻求较好的解决方案。 从理论上讲，多机器人通信( m u l t i p l em o b i l er o b o t sc o m m u n i c a t i o n ) 就是多点对多 点的通信，它是由多个机器人组成的局域通信网。目前，很多机构都根据多机器人通 信系统体积小、功耗低的特点，对有线局域网、无线局域网和自组网做适当的改进来 组建多机器人通信网络。有线局域网和无线局域网技术在工业机器人领域已经得到广 泛应用。自组网作为一种新型网络，也开始受到机器人研究机构的重视。c m u 的机 器入研究所已经开始尝试使用自组网来解决他们的多机器人的通讯问题并展开了相 关研究。 当前，自组网的研究成果主要集中在美国。c m u 的m o n a r c h 工程组对自组 网进行了深入研究，提出了一些权威的路由协议如d s r ，并对目前主流的网络模拟 器n s 进行了扩展，使其能更好的用来测试、评价自组网路由协议。目前m o n a r c h 工程组已经建立起了移动自组网的实验床 3 0 1 。他们的实验床由5 个移动车载节点和两 个固定节点组成。他们使用实验床对d s r 协议进行了实验分析 3 。此外，c h a r l e se p e r k i n s 和e l i z a b e h tm r o y e r 提出的另一种自组网路由协议a o d v 已经成为r f c 草 案。另外，t f ( 因特网工程任务组) 也已经成立了专门的研究小组m a n e t 工作 组，负责移动自组网的相关协议的标准化工作 2 9 。此外，欧洲也已经开始考虑将自组 网作为中继，以扩大第二代和第三代移动通信系统的覆盖范围，提高在网络或链路故 障时系统的健壮性，目前已经建立了a g s m 实验系统 3 2 1 。 1 3 本文结构 本文共分五章，内容安排如下： 第一章介绍了多机器人通讯网络的路由协议研究的选题背景和意义，讨论当前国 内外的研究现状。 第二章研究了自组网技术，包括其特点、关键技术和研究现状并比较了它与常用 移动蜂窝通讯网络的区别。 第三章阐述了自组网路由协议的特点，并研究了两种目前常用的自组网路由协议。 第四章首先分析了目前常用自组网路由协议的优缺点，随后详细阐述了本文提出 的m r c s r p 路由协议并提出了相应的优化方法，然后按照r f c 2 5 0 1 标准对m r c s r p 路由协议进行了定性分析。 第五章详细介绍了仿真实验，根据实验结果对m r c s r p 协议进行了定量分析并 比较了m r c s r p 与a o d v 的性能差别。 2 自组网技术硕士论文 2 自组阿技术 自组网的前身为分组无线网( p a c k e tr a d i o ) ，是1 9 7 0 年由美国国防部远景规划局 ( d a r p r ) 启动的一个研究项目，起初仅仅是为了满足军事应用需求，主要研究抗毁的、 自适应的网络研究计划，低开销的分组无线网络研究计划等。经过多年的技术储备， d a r p a 在联合战术无线系统( y r r s ) 中扩大技术规模，并计划在今后5 年内投人使用。 自组网技术在军事领域发展的同时也引起了商用领域的极大兴趣。近年亲，自组网的 商业价值逐渐受到重视，它能满足野外活动和救灾时的通信需求，可用于战斗单位、 救灾工作系统以及城市车辆之间的通信，还可用于某些需要临时快速建立通信网络的 场合。另一个有影响力的研究分支因特网任务工程组( n 3 t f ) 成立了专门的m a n e t 工 作组，自组网的设计思路也由传统的单一技术体系过渡到基于p 的多技术体系，从 而使自组网更具有开放性、适应性和灵活性，提高了开发速度( t o l 1 3j 。 自组网( a dh o c ) 是一种无线移动通信网络。它是一个多跳的临时性自治系统，整 个网络没有固定的基础设施，由一系列带有无线收发装置的移动节点构成，节点同时 具备主机与路由器两种功能【3 1 】。在任意时刻，任一节点可向任意方向以任意速度运动， 即节点间的运动是自主的。因此对于不同时刻的网络，其拓扑结构也随之发生变化。 当通信双方在彼此的通信范围内时，自组网中的两个通信节点之间可直接进行无线通 信。由于终端的无线覆盖范围的有限性，当通信双方间的距离超过彼此的通信范围时， 用户终端可以借助于其它节点进行分组转发。每一个节点都可以说是一个路由器，它 们要能完成发现和维持到其它节点路由的功能。因此，自组网通常是一个多跳 ( m u l t i h o p ) 的无线移动网络。典型例子有交互式讲演，可以共享信息的商业会议，战 场上的信息中继以及紧急通信需要【l o j i ” 。图2 1 描述了一个由三个主机构成的一个简 单的自组网。主机a 不在主机c 的通讯范围内( a 外面的圆圈表示主机a 的通讯范围) ， 主机c 也不在主机a 的通讯范围内，当主机a 需要和主机c 进行通讯时，需要主机 b 来为它们进行分组转发，因为主机b 同时在主机a 和c 的通讯范围里。 d 图2 1 自组网示例 南京理工大学硕士学位论文多机器人通讯网络的路由协议的研究 2 1 白组网的特点 无线自组网是没有固定网络结构的、由移动主机构成的自主系统，主要具有以下 特征【l i j ： ( 1 ) 网络自主性 相对常规通信网而言，自组网最大的区别就是可以在任何时刻、任何地点不需要 现有的基础网络设施就可以搭建起来。它仅由一些充当主机与路由器的移动终端组 成，网络搬迁非常方便。 ( 2 ) 生存时间短 自组网一般是临时搭建的，任务完成后立即撤除。 ( 3 ) 动态拓扑 从网络层来看，在自组网中，移动节点可以以任意速度和方向在网络中移动，加 上无线发送装置发送功率的变化、无线信道间的相互干扰、地形因素等的影响，节点 间通过无线信道形成的网络拓扑结构随时会发生变化。 ( 4 ) 带宽限制和变化的链路容量 自组网采用无线传输技术作为底层通信手段，由于无线信道本身的物理特性，其 相对于有线信道具有较低的容量；并且由于多路访问、多径衰落、噪声和信号干扰等 多种因素，使得移动节点的实际带宽小于理论上的最大带宽值。 ( 5 ) 可能存在单向通信 节点的发射功率、电池能量以及地理位置等可能存在单向链路。例如，若主机节 点a 、b 的发射功率不同，a 发射的信号b 能收到，但b 发射的信号a 却不能收到， 这时a ，b 之间存在的就是单向链路。 ( 6 ) 能量限制节点 移动节点依靠电池提供工作所需的能量。减少功耗将是影响网络协议设计的一个 非常重要的因素。 ( 7 ) 多跳通信 由于无线收发机的信号传播范围有限，自组网要求支持多跳通信。多种多跳通信 由此也带来了隐藏终端、暴露终端和公平性等问题。 ( 8 ) 分布式控制 自组网中的用户节点都兼备独立路由和主机功能，还存在一个网络中心控制点， 用户节点之间的地位是平等的，网络路由协议通常采用分布式控制方式，因而具有很 强的独立性和抗毁性。而在常规通信网络中，由于存在基站、网控中心或路由器这样 一类集中控制的设备，用户终端与它们所处的地位不是对等的，而且基站、网控中心 或路由器的损毁将可能导致整个通讯网络的瘫痪。自组网是无集中控制中心的完全分 5 2 自组厨技术硕士论文 布式的通讯网络，故当某节点出故障时，并不一定会使整个网络瘫痪。 ( 9 ) 有限的安全性 通常移动无线网络由于采用无线信道、有限电源、分布式控制等原因，会比有线 网络更易受到安全性的威胁。这些安全性的攻击包括窃听、电子欺骗和拒绝服务等攻 击手段。 2 2 自组网的关键技术 ( 1 ) 自组网的路由技术 在自组网里，移动节点通过多跳无线链路实现相互间的通信。整个网络没有固定 的基础设施，比如基站。网内每一个节点都具有路由器的功能，可以向其它节点转发 数据分组。由于动态变化的网络拓扑结构，节点不可能永远的保存其他节点的路径信 息，这使得开发自组网的路由协议比起其他网络的路由协议来说更富有挑战性。因而， 开发一种能有效地找到节点问路由的动态路由协议成为自组网设计的关键1 4 t 。 ( 2 ) 自组网的安全问题 与传统的无线网不同，自组网作为一种新型的无线移动网络，不依赖于任何固定 漫施，而是通过移动节点间的相互协作保持网络互联。由于该网络的独特性，它正逐 步运用于商业环境。设计这种网络面临的一个主要挑战就是它易受到安全攻击，比如 受到窃听、伪造、拒绝服务等攻击 1 ”。 在自组网中没有基站或中心节点，所有节点都是移动的，网络的拓扑结构动态变 化。节点问通过无线信道相连，没有专门的路由器，由节点自身充当路由器，同时也 没有命名服务、目录服务等网络功能。这就导致了在传统网络中的安全机制不再适用 于自组网，所以应提出专门针对自组网的安全机制。目前提出的安全策略有：基于口 令的认证协议，它与传统的口令认证不同的地方是密钥和口令的产生是由多台机器决 定，而不是集中由台机器产生，并且还提供了一种完善的口令更新机制；“复活鸭 子”的安全模式，它主要针对传感器网络里，传感器与控制者之间可能存在的不安全 问题，提出传感器在“死亡”之前，只受其拥有者的控制：异步的分布式密钥管理， 它提出密钥管理服务是由多个节点( 一个集合) 来管理，而不是单个节点来管理 1 d j 。 t 3 ) 自组尉网际互联 自组网是一种多跳网，目前，大部分的路由算法都是用于单个自组网网内的，现 在大多数研究也都集中在这个方面，很少涉及如何把多个自组网子网联接成一个大网 以及如何与有线i n t e m e t 相结合。通过使用网关路由器，可以实现将几个自组网互联 以及网内节点可以访问互联网的功能。这种形式可以向位于多个分散地理位置上的工 作小组提供协同通信能力【1 4 】。 自组网与i n t e m e t 和广域网的互联，从外部来看，可以认为自组网是一个m 子网。 6 南京理工大学硕士学位论文多机器人通讯网络的路由协议的研究 网内部分分组的传送是由网内路由协议完成( 分组到达目的地可能要经过多跳) ，而当 分组进入或离开子网时，采用标准m 路由机制。这就要求网关节点要能运行多种路 由协议n4 1 。 2 3 自组两的研究现状 9 0 年代以来，自组网的研究在世界范围内方兴未艾，已经从无线通信领域中的 一个小分支逐渐扩大到相对较独立的领域。目前，无论在国际上还是在区域上( 欧洲 和亚洲等地区) ，周期性的自组网学术会议日益增多。自组网的研究现状和成果主要 在以下几个方面【l “： ( 1 ) 提出新的路由协议。自组网路由面临的主要挑战是：传统的保存在节点中的 分布式路由数据库如何适应网络拓扑的动态变化。新协议一般以广播或组播方式建立 网络路由，核心是减少广播风暴。目前，一般普遍得到认可的代表性成果有d s d v 、 w r p 、a o d v 、d s r 、t o r a 和z r p 等。不过，从实现的难度来看，这些协议离现 实应用还有一定的距离。 ( 2 ) 基于自组网的媒体接入控带i j ( m a c ) 协议。主要是解决隐藏终端和暴露终端问 题，影响比较大的有m a c a 协议，即r 1 s c t s a c k 方案，控制信道和数据信道分 裂的双信道方案和基于定向天线的m a c 协议，以及一些改进类的m a c 协议。有一 些研究则是侧重于将i e e e s 0 2 1 1 的m a c 协议移植到自组网中。基于定向天线的m a c 协议在理论上性能较为优越，但在技术上实现的难度较大。 ( 3 ) 自组网与蜂窝网的互连互通。有人研究并提出了一种i c a r ( i n t e m e tc e l l u l a r a n da dh o cr e l a y ) 系统，提供蜂窝小区内信号的补盲。从结果看，该系统只是针对目 前的2 g 系统，尚无法联系到基于口方式的分组网络。 ( 4 ) 基于自组网的多播组播协议、t c p 协议、地址分配、功率( 节能) 控制、安全 性问题、分布式算法、q o s 等方面有一些研究成果，但这些部分并没有成为研究的热 点。 2 4 自组网与常规移动通讯两络的区别 常规移动无线通信网络通常是以蜂窝移动通信网络方式出现。在目前的蜂窝移动 通信网络中，移动终端和固定基站相互通信，移动交换机负责路由和交换功能，同时 充当网关，通过有线方式接入固定网，移动终端不具备路由功能。自组网与常规移动 通讯网络的区别主要有： 1 ) 自组网无通讯基础设施的支持 对于常用的蜂窝移动通信网络，如g s m 、g p r s 等，都需要有诸如基站等固定 2 自组婀技术硕士论文 设施的支持。用户终端通过基站进行通讯，彼此间不能直接进行通讯。基站和用户终 端不是平等的，即在有基站的蜂窝移动通信网络中采用集中控制的方式。而自组网的 特点就是不需要任何现成的网络设施的支持，它可以在需要时快速构建。在自组网中， 各主机是相互平等的，整个网络采用全分布式的控制方式。 2 ) 自组网的网络结构不停的发生变化 在常用的蜂窝移动通信网络中，虽然终端也不停的移动，但其固定设施没有移动， 所以总的来说，其网络拓扑结构还是比较稳定的。在自组网中，任何节点的移动都将 造成网络拓扑结构的实质性变化。 3 ) 业务类型不同 目前的蜂窝移动通信网络通常提供语音、数据及多媒体业务1 3 3 1 ，而自组网主要提 供数据业务。 4 ) 提供的服务可靠性不同 常用的蜂窝移动通信网络提供的很多服务都存在着延迟、误码率高的不足，而自 组网提供的服务相对来说可靠性比较高、网络延迟也比较短。 2 5 本章小结 为了更好的研究多机器人系统通讯问题，本章对自组网进行了一个简单的介绍。 其中包括自组网的基本概念、自组网的特点、自组网的关键技术和它的研究现状。最 后对自组网与目前常用的蜂窝移动通讯网络进行了比较。 南京理工大学硕士学位论文 多机器人通讯网络的路由协议的研究 3 自组网路由协议 在自组网里，移动节点通过多跳无线链路实现相互间的通信。整个网络没有固定 的基础设施。网内每一个节点既是终端又是路由器。开发一种能有效地寻找节点间路 由的动态路由协议成为自组网网络设计的关键，也是更好的解决多机器人系统通讯问 题的关键。本章首先对自组网路由协议进行概括性介绍，然后阐述了两种目前常用的 自组网路由协议的基本原理。 3 1 自组网路由协议概述 3 1 1 自组孵路由协议设计要求 多跳、移动通信、动态组网是自组网的基本特征，也是自组网路由协议设计的前 提和基础。因而，自组网路由协议需要能够实现以下的功能： ( 1 ) 能感知网络拓扑结构的变化 自组网路由协议要能够检测到网络拓扑的动态变化。因为自组网网络需要进行多 跳通信，所以路由协议必须确保路径中的链路具有很强的连接性。自组网网络中的节 点必须知道它的周围环境和可以与它直接进行通信的节点。自组网网络里提供网络连 接的方法主要有两种：平面路由网络结构和分层路由网络结构。在平面路由网络结构 中，所有的节点都是平等的，分组路由是基于对等连接的。但是在分层路由结构中， 较低层至少要有一个节点作为与高层联系的网关【l ”。 平面路由网络结构分层路由网络结构 图3 1 1 1 自组网里的网络连接方式 ( 2 ) 维护网络拓扑连接 因为每个移动主机都可以随时改变位置，所以网络拓扑是频繁变化的。这样，自 组网路由协议为了维持节点之间的链路具有较强的连接性，它必须动态更新链路状态 9 3 自组网路由协议硕士论文 和对自己重新配置。如果采用中心控制的路由算法，为把节点链路状态的改变传送到 所有的节点，就会消耗掉节点过多的时间和精力，显然是不适合的。所以自组网的路 由算法应是全分布的c l “。 ( 3 ) 高度自适应的路由 相对予有线网络里的静态节点，自组网网络要求一个高度自适应的路由机制来处 理快速的拓扑变化。而传统的路由协议，如距离向量算法和链路状态算法，都要求在 指定路由器润定期交换大量路由信息，这在自组网里是不能有效工作的。所以必须针 对自组网的特点，提出新的路由算法或对现有的路由算法进行有效的改进【j ”。 3 1 2 自组网路由协议的概况 自从2 0 世纪7 0 年代初d a r p a 提出数据包无线电网络( p a c k e t r a d i on e t w o r k s ) 起， 就开始陆续出现一些专门为自组网设计的路由协议。这些协议必须能够处理自组网的 一些固有的局限性，比如较高的能源消耗、低带宽和高误码率。实质上，自组网路由 协议就是分布式系统中的最短路径问题。每一个数据包在它的包头里存放着目的节点 的m 。当某一节点收到数据包时，它根据自己的路由表将该数据包转发给通往目的 节点的下一跳节点。数据包一直的被转发，直到到达目的节点。不同的路由协议在路 由表的构造、维护和更新上彼此不同。然而，总的来说路由协议都希望达到一个共同 的目的，那就是使用最优路径来传输数据。目前，路由协议大体上可以分为两类：( 1 ) 表驱动路由协议，( 2 ) 源驱动按需路由协议。尽管这两类协议是为同一种网络设计的， 但是它们之间却存在着明显的差别。 ( 1 ) 表驱动路由协议 表驱动路由协议要求网络中的每一个节点保存通往网络中其他所有节点的持续 的、实时的路由信息。这类协议需要节点保存一张甚至数量更多的路由表用来存储路 由信息。为了维护持续的网络结构图，节点周期性的在整个网络内广播更新信息。同 时，节点也通过周期性的广播来对网络拓扑结构的变化做出反映。表驱动路由与传输 数据包时的无连接方法相似。节点不管某条路径是否需要，什么时候需要以及对该路 径需要的频繁程度，它都在自己的路由表中保存这样一条路径信息。从根本上说，表 驱动路由依赖于路由表更新机制，这种更新机制包含了路由信息的经常性广播。在表 驱动路由协议中，因为路由信息被周期性的广播和保存，所以，对某节点来说，不论 这些路径是否需要，它总是保存着通往整个网络中其他任何节点的路径。这种特性尽 管对于自带路径信息的数据流也是有用的，但它却招致了实质性的网络负载和能量消 耗。由于带宽和电池能量对于移动计算机是非常稀缺的，这种特性成了一种非常严重 的局限性。 ( 2 ) 源驱动按需路由协议 1 0 南京瑾工丈学硕士学位论文多机器人通讯隔络的路由协议的研究 源驱动按需路由协议仅在源节点需要通往某一节点的路由时才发起路由请求进 行寻径。当某一节点需要通往某一目的地的路由信息时，它在整个网络内进行路由发 现。当一条路径被找到或者所有可能路径都被尝试过后，路由发现过程结束。某条路 径一旦被建立，它将被某种路由维护机制所保持直到对源节点来说目的节点变的不可 到达或者这条路径不再需要。源驱动按需路由不需要周期性的广播路由信息，这大大 节省了网络带宽和节点能量。使用按需路由协议的节点不知道通往网络中某一节点的 路由除非它需要这样的路由信息。当一个使用按需路由协议的节点需要向某一新的目 的地发送数据时，它将等待路由发现过程为它寻找一条合适的路径。 在接下来的两小节中，介绍两种常用的自组网动态按需路由协议。 3 2 d s r 3 2 1d s r 榻述 为了向另一个节点发送数据，源节点在数据包的包头里构建源路由，源路由里包 含了通往目的节点的完整的路径信息。源节点把数据包发往源路由里的第一个节点。 当主机收到数据包后，如果它不是目的节点，那它仅仅按照源路由提供的路径把包转 发给下一跳节点而不做任何处理。数据包一直被转发直到到达目的节点 3 5 】。 自组网中的每个节点都保存着一张路由表，路由表中存放着节点知道的路径信 息。当节点需要向另一个节点发送数据时，它首先查看自己的路由表。如果找到需要 的路径，它就用该路径发送数据；如果没有找到需要的路径，节点利用路由发现机制 寻找通往目的节点的路径。在等待路由发现的过程中，节点正常处理其他事件，比如 接收和转发数据包。在路由发现过程中，节点根据上层协议的要求缓存数据包待需要 的路径找到后发送数据包或者直接将它丢弃。路由表中的每一项都标注一个到期时 间，时间到后相应的表项就被删除【3 。 当节点正在使用某条路径时，它监控这条路径是否完好。例如：源节点或者是目 的节点或者是路径中的其他中间节点移出了它的上一跳或是下一跳节点的通讯范围， 则这条通往相应目的节点的路径就变得不可用了。路径中的任何节点出现故障后，此 路径就不再能使用。这种监控正在使用的路由的完好性称为路由维护。当路由维护发 现正在使用的路由出现问题而不再能用时，节点将再次进行路由发现来寻找一条新 的、正确的通往目的节点的路径瞄“。 3 2 2 路由发现 自组网里的每个节点利用路由发现机制动态的寻找去往任何节点的路径。发起路 由发现的节点向它的邻居节点广播路由请求包。路由请求包中包含了这次路由发现的 1 1 3 自组网路由协议 硕士论文 目的节点。如果路由发现成功的话，源节点会收到路由回复包，回复包里列出了通往 目的节点的路径所包含的各个中间节点。 请求包里除了含有源节点地址和目的节点地址夕 ，还有一个路由记录项。在路由 记录项里保存着路由发现过程中转发请求包的所有节点。每个请求包都有一个由源节 点产生的惟一的请求i d 。为了检测到请求包的副本，每个节点保存着它最近处理过的 ( 源节点地址，请求i d ) 对。 当节点收到路由请求包时，它按照下面的过程处理请求包0 6 ： 图3 2 2 1 请求包的处理过程 路由请求包在整个网络内不停的被转发，直到它到达目的节点，由目的节点向源 节点发送回复包。源节点广播的路由请求包仅被它的邻居节点收到，这些节点若本身 不是目的节点并黾这个请求包对它来说也不是冗余的，它继续广播请求包。若节点已 经出现在路由记录项中便不再处理该请求包，这样可以有效的防止路由环的产生。同 样，节点对于已经处理过的请求包也不再处理。 为了向源节点发送路由回复包，目的节点要有去往源节点的路径。如果目的节点 的路由表里有去往源节点的路径，它用这条路径和发送其他数据包样发送回复包。 1 2 南京理工大学硕士学位论文多机器人通讯网络的路由协议的研究 否则，目的节点反转请求包路由记录项里的路径，并用反转路径来发送回复包。利用 反转路径发回复包时，要求网络支持双向链路。另外一种可供选择的方法是，目的节 点重新进行路由请求，它把回复包放在请求包中一起广播出去。 3 2 3 路由维护 传统的路由协议通过周期性的广播路由信息把路由发现和路由维护集成在一起。 如果链路或者节点发生改变，周期性的路由广播最终能使得所有节点都知道这种改 变，这也将导致新路由的出现。然而，使用路由发现机制后就没有周期性的广播消息。 相反，当一条路径正在被使用时，路由维护机制监测路径的完好性，并告诉源节点任 何可能的错误“。 由于无线网络天生就没有有线网络可靠，许多网络为了尽早检测到包丢失和包冲 突以便进行重传而利用数据链路层的点对点确认。在这样的网络中，路由维护很容易 实现，因为对于每一个节点，主机往下一节点传输包时很容易知道下一节点是否正常 工作。如果数据链路层报告一个它无法修复的传输故障( 比如已经超过了它所允许的 最大重传次数) ，节点就向源节点发送一个错误包告诉源节点路径出现了错误。路由 错误包包括链路断开的两端的节点：检测到错误的节点和它试图传输数据的下一跳节 点。节点收到路由错误包后，发生错误的节点被从路由表中删去，并且所有包含这一 跳的路由都被标记为无效。 如果无线网络不支持这样的底层确认，在很多情况下，可以获得一个等价的确认。 如果节点可以在网络接口处采用p r o m i s c u o u s 模式，则节点往下一跳传输包后，它可 以监听下一跳节点是否沿着即定的路径传输包。此外，源节点的可用的传输层或是应 用层的回复或确认可以用来确认某条路径是否依旧可用。最后一种确认方法是将包头 的一位用作确认位，要求下一跳节点收到包后往回发送一个确认信息。如果在一段时 间内，没有收到下一夥节点发来的任何确认信息，节点可以利用这一位来方便的探测 下一跳节点的状态。 为了向源节点发送错误包，节点必须知道去往源节点的路径。如果节点的路由表 里保存着到源节点的路径，它就用这条路径来发送错误包。否则，节点将数据包中的 路径反转后利用反转路径发送错误包，或者重新发起路由请求，并将错误包放在路由 请求包中一起发送出去。圄发错误包的另一种方法，节点暂时缓存错误包，同时，节 点利用路由发现寻找通往源节点的路径，待路径找到后，节点沿该路径发送错误包。 然而，这种方法不能用来发送路由回复包，因为如果两边节点的路由表中都没有通往 对方的路径，那么两边的节点都不能顺利完成路由发现。 如果网络中存在单向链路，路由维护也经常使用端到端的确认，而不是上面提到 的点到点的确认。只要两个节点阃存在某些路径，路由维护就有可能。在这种情况下， 】3 3 自组网路由协议硕士论文 现有的源节点传输层或是应用层的回复或是确认或者是明确的网络层确认可用来确 定另个节点的状态。利用点到点确认，错误包明确指出哪个节点出现了故障，而利 用端到端确认，源节点只能假设通往目的地节点的最后一跳节点出现了故障翊。 3 3 a o d v 3 3 1a o d v 的概述 另一种常用的自组网路由协议是a o d v 。a o d v 是纯粹的按需路由获得系统， 不处于活动路径上的节点既不维护任何路由信息也不参与任何路由表信息的周期性 交换。更进一步说，仅当两个节点需要进行通讯，或者是节点作为另两个节点的中继 为它们进行数据转发时，节点才寻找和维护去往另一个节点的路径【3 ”。 当节点想要知道它的邻居节点时，节点可以通过好几种方法来感知它们，其中包 括周期性的发送h e l l o 报文。邻居节点的路由表被组织起来以对本地移动的响应时间 进行优化并为新的路由建立提供更快的响应时间。 a o d v 借鉴了d s r 的广播路由发现机制。然而，a o d v 没有采用源路由思想， 而是依赖于中间节点动态的建立路由表。它与d s r 的这种区别在节点较多的网络里 显得非常有用，因为它减少了每个数据包里携带的大量控制信息。为了维护节点间最 新的路由信息并防止路由环的产生、a o d v 借鉴了d s d v 的目的节点序列号思想。 然而，与d s d v 不同的是，每个节点维护一个单一增加的序列号计数器，并用它来 剔除陈旧的路由信息。a o d v 正是结合了这些技术而产生的一种新的路由协议。 a o d v 通过减少网络负担从而有效的利用带宽，它对网络拓扑变化能快速做出反映 并且确保无环路由。 3 3 2 路由发现 当个节点需要和另一个节点通讯，而它的路由表里又没有相应的路由信息时， 节点进行路由发现来寻找路径。每个节点维护两个相互独立的计数器：节点序列号计 数器和广播i d 计数器。源节点通过向邻居节点广播路由请求包( r r e q ) 来进行路由发 现跚。r r e q 的结构如下： 源节点地址源节点序列号广播目的节点地址目的节点序列跳数 i d ( 源节点地址，广播i d ) 对唯一的标识r r e q 。源节点每次产生新的r r e q ，广播 i d 就自增l 。邻居节点要么满足r r e q 而向源节点发送一个路由回复( r r e p ) 要么把 1 4 南京理工大学硕士学位论文多机器人通讯网络的路由协议的研究 r r e q 里的跳数增加1 后向自己的邻居节点广播。注意到一点，节点可能从不同的邻 居那收到同一路由广播包的若干个副本。当中间节点收到一个r r e q 后，如果它已 经收到过具有相同源节点地址和广播i d 的r r e q ，那么它将这个r r e q 丢弃而不再 广播它。如果节点不能满足r r e q 的要求，为了建立反转路径，也为了传输r r e p 时建立向前路径，它将记录如下信息：目的节点口地址、源节点p 地址、广播i d 、 反转路径的过期时间和源节点序列号。 3 3 2 1 建立反转路径 在r r e q 里除了广播i d 之外还有两个序列号：源节点序列号和源节点知道的最 新的目的节点序列号。源节点序列号用来维护反转路径的新信息，目的节点序列号用 来在路径被源节点采用之前更新去往目的节点的路径。 当r r e q 从源节点到达不同的目的节点时，它自动的建立起指向源节点的反转 路径。为了建立反转路径，节点记录第一个发给它r r e q 的节点。这些反转路径的 信息被保存足够长的时间以使得r r e q 能够在整个网络范围内被传播并由相应的节 点给源节点产生一个回复【3 7 】。 d 建立反转路径 3 , 3 2 2 建立向前路径 d 建立向前路径 图3 3 2 1 1向前路径和反转路径的建立 r r e q 最终到达能够产生去往目的地的路径的节点，多数情况是到达目的节点。 收到r r e q 的节点首先检