[硕士论文精品]多机器人通讯网络的路由协议的研究

南京理工大学硕士学位论文多机器人通讯网络的路由协议的研究摘要近年来，多机器人因能更好的协同完成复杂任务而成为机器人学研究的热点。在多机器人系统中，通讯是其协调运行的基础。本文涉及的多机器人系统具有移动通信、动态组网的特点并且通常工作在没有现成无线网络基础设施的地方。自组网是解决这类多机器八通讯问题的种有效途径。自组网路由协议的研究，是自组网研究领域的热点之一，也是解决多机器人系统通讯的一个重点。本文为更好地解决多机器人系统的通讯问题进行了研究与探索。本文首先研究了新型网络自组网，并比较了它与目前常用的蜂窝移动通信网络的区别。随后研究了两种目前常用的自组网路由协议DSR和AODV，并对它们进行了定性分析。在借鉴AODV路由机制的基础上提出了适用于多机器人通讯网络的MRCSRP路由协议。MRCSRP协议在路由发现时采用源路由思想，而在传输数据包时没有将完整的路径放到数据包中，而是依赖中间节点动态建立路由。MRCSRP协议利用广播包和监听到的数据包来维护本地连接，它利用序列号机制来避免路由环的产生。随后，本文对协议提出了一些优化方法并对协议进行了定性分析。最后，本文对协议进行了仿真实验，实验证明，本文提出的MRCSRP协议是可行的。通过它与AODV性能的比较，更进一步说明MRCSRP是更适用于多机器人通讯网络的路由协议。关链词多机器人系统无线通讯自组网路由协议AODVABSTRACT硕士论文ABSTRACTWITHTHEDEVELOPMENTOFROBOTTECHNOLOGY,PEOPLEPAYMOREANDMOREATTENTIONTOTHEMULTIROBOTICSYSTEMITISPROVEDTHATUSINGMULTIROBOTICSYSTEMCALLACHIEVECOMPLICATEDTASKBETTERCOMMUNICATIONISTHEBASEOFMULTIROBOTICSYSTEMADHOCNETWORKISAGOODWAYTOSOLVETHECOMMUNICATIONOFTHEMULTIMBOTICSYSTEMTHEPAPERSTUDIESTHEMUTINGPROTOCOLISIMPORTANTTOBOTHADHOCNETWORKANDTHECOMMUNICATIONOFTHEMULTIROBOTICSYSTEM，INORDERT0SOLVETHECOMMUNICATIONOFTHEMULTIMBOTICSYSTEMTHEPAPERFIRSTSTUDIESTHEATTRIBUTESOFADHOCNETWORKANDCOMPARESITWITHGSMANDGPRSSECOND，THEPAPERSTUDIESTWOROUTINGPROTOCOLSUSEDINADHOCDSRANDAODVTHENANEWALGORITHMFORROUTING，WHICHISNAMEDMRCSRPISPROPOSEDROUTEDISCOVERYOFMRCSRPUSESSOURCEMUTING，BUTTHENODEDOESNTKEEPTHEWHOLEROUTESINITSROUTETABLEANDMRCSRPRELIESONDYNAMICAJJYESTABLISHINGROUTETABLEENTRIESATINTERMEDIATENODESTHENODEUSESTHEBROADCASTSFROMITSNEIGHBORSANDTHEDATAPACKETSITHEARSTOMANAGETHELOCALCONNECTIVITYITUSESADESTINATIONSEQUENCENUMBERFOREACHROUTEENTRYUSINGDESTINATIONSEQUENCENUMBERSENSURESLOOPFREEMUTINGSOMEOPTIRRDZATIONSAREALSOPROPOSEDINTHEPAPERTHEPAPERALSOINCLUDESANEVALUATIONMETHODOLOGYANDSIMULATIONRESULTSTOVERIFYTHEOPERATIONOFMRCSRPBYCOMPARINGTHEPERFORMANCEOFMRCSRPANDAODVITSHOWSMRCSRPSUITSTHEMULTIROBOTICSYSTEMBETTERKEYWORDSMULTIROBOTICSYSTEM，WIRELESSCOMMUNICATION，ADHOC，MUTINGPROTOCOLAODVII声明本学位论文是我在导师的指导下取得的研究成果，尽我所知，在本学位论文中，除了加以标注和致谢的部分外，不包含其他人已经发表或公布过的研究成果，也不包含我为获得任何教育机构的学位或学历而使用过的材料。与我一同工作的同事对本学位论文做出的贡献均已在论文中作了明确的说明。年月日学位论文使用授权声明南京理工大学有权保存本学位论文的电子和纸质文档，可以借阅或上网公布本学位论文的全部或部分内容，可以向有关部门或机构送交并授权其保存、错阅或上网公布本学位论文的全部或部分内容。对于保密论文，按保密的有关规定和程序处理。年月日南京理工大学硕士学位论文多机器人通讯网络的路由协议的研究1绪论1,1选题的背景及意义多机器人系统的研究始于20世纪70年代。随着机器人应用领域的不断拓展、机器人工作环境复杂度、任务的加重，对机器人的要求不再局限于单个机器人，多机器人的研究己经成为机器人学研究的一个热点。多机器人系统不是多个单机器人的简单堆砌，而是多个机器入的有机组合，它有效的避免了单机器人的不足，充分发挥了群体机器人的优势。与单机器人相比，多机器人系统具有以下特点1】【1811适合完成复杂任务对于可分解的复杂的任务及大范围的环境，利用多机器人系统，可把复杂的任务分解成多个简单的子任务，利用多个机器人协调工作，可以有效地完成任务，这比单个机器人顺序的完成所有的子任务要快得多2时空分布性多个机器人可分布在不同的区域内同时作业，也可在不同分布时间内执行任务，可提高完成任务的效率；3功能分布性在多个机器人中，机器人的功能可以不同，它们的目标任务不同，但它们可协调工作；4感知分布性在一个区域较大的环境中，多个机器人分布在环境中，各自感知周围的环境，通过共享感知到的信息，大大扩展了机器人系统对环境的感知范围。通过成员之间的信息交换，多机器人系统可以更有效和更精确地进行定位，这对于野外作业的机器人尤其重要；5较高的系统可靠性采用多机器人系统可以将其中的各个成员设计成完成某项任务的“专家”，而不是设计成完成所有任务的“通才”，这大大降低了单个机器人设计复杂度，提高了单个机器人的可靠性。而机器人数量上的冗余，也能提高整个系统的可靠性，不会因为个别机器人的故障导致整个系统的瘫痪。对于由多个个体机器人组成的群体系统，通信是必不可少的。多机器人系统在执行某项任务时，为了实现协调与合作，个体机器人的传感器必须提供足够的环境描述信息以及其他机器人的相关信息，因此机器人个体与个体之间或者上层控制和下层合作之间的通信是必要的。目前，多机器人系统的通信主要采用广播的方式，即个体机器人将自己的位置信息和传感器信息以及自己从事的工作信息广播出去，其他个体机器人可以按自己的需要选择信息，或由主控机器人通过广播分配任务口。计算机网络是把各种计算机及网络设备通过通信链路或传输介质连接在一起，以协议及网络硬件、网络软件使计算机或网络设备进行相互通信，实现信息的通信和资L绪论硕士论文源的共享【2斟计算机网络从20世纪60年代开始发展至今，已形成从小型局域网到全球性的广域网的规模。在过去的20多年星，计算机网络技术取得了惊人的发展。计算机网络的发展为多机器人系统通讯提供了基本解决方案，也促进了多机器人系统的发展。目前，很多从事多机器人系统研究的机构都开始利用和改进现有的网络技术，试图利用现有的网络技术来解决多机器人系统的通讯问题。自组网是一种有特殊用途的对等式网络，又被称为多跳网络、无固定基础设施的网络或者自组织网络【29】。自组网是由一组带有无线收发装置的移动节点组成的一个多跳的、临时性的自治系统【3”。在自组网中，移动终端同时承担主机和路由器两种功能。也就是说参与自组网的移动终端之间存在着某种协同工作的关系，这种关系使得每个终端都要承担为其它终端进行分组转发的义务，也就是需要运行合适的路由协议34】。自组网路由协议的研究，作为自组网研究领域的热点之一，一直受到了广泛的关注。其路由选择问题比传统的相关问题更加富有挑战性34】。本文结合国防科工委预研基金项目，对多机器人系统通讯进行初步研究。本文涉及的多机器人系统具有移动通信、动态组网的特点，而且通常在野外没有现成网络基础设施的地方工作。自组网是解决这类多机器人通讯问题的一种有效途径，它能够为需要协同工作的多个机器人提供种通信支撑环境。本文以自组网理论为基础，结合多机器人系统的特点，研究适用于多机器人通讯网络的路由协议。本文在对目前自缉网路由协议研究分析的基础上，提出了MRCSRP路由协议，并通过仿真实验验证了协议的可行性同时比较了它与AODV的性能差别。12研究现状自80年代以来，多机器人系统受到国内外普遍的关注。近年来，在IEEERA、IROS等著名的国际机器人学术会议上，几乎每次会议都有多机器人系统通讯的专题。一些机器入学术刊物出版了有关多机器人系统的专刊。许多研究机构都开展了这方面的研究，代表性的研究项目有CEBOT系统【4J，MARTHA系统【7、GBENI研究的SWARM系统口J【刮等系统。FUKUDA研究的CEBOTCELLULARROBOTICSYSTEM被认为是对机器人团队协同工作的首次尝试。它是一个自组织的机器人系统。它由众多的、功能简单的、被称为细胞元CELL的单元组成。CEBOT能够根据特定的任务和环境来重组织自身，并能够形成集体的或者说是大量的智能【4】。MARRIHA“用于搬运的多自主机器人系统MULTIPLEAUTONOMOUSROBOTSSYSTEMFORTRANSPORTANDHANDINGAPPLICATION”是欧盟设立的一个专门进行多机器人系统研究的课题。它计划组建一支由10到100个自主移动机器人组成的庞大的搬运队伍用于在港口、机场等地完成搬运工作。MARTHA的一个研究目标就是使机器人群体在一2南京理工大学硕士学位论文多机器人通讯网络的路由协议的研究个开放的环境下工作而尽可能少的用到中心控制。目前，他们正在研究如何使机器人在应对突发事件和障碍时具有更高的自主性【”。多机器人的通讯问题是其中的关键。因此，他们正在对多机器人的通讯问题进行深入研究，寻求较好的解决方案。从理论上讲，多机器人通信MULTIPLEMOBILEROBOTSCOMMUNICATION就是多点对多点的通信，它是由多个机器人组成的局域通信网。目前，很多机构都根据多机器人通信系统体积小、功耗低的特点，对有线局域网、无线局域网和自组网做适当的改进来组建多机器人通信网络。有线局域网和无线局域网技术在工业机器人领域已经得到广泛应用。自组网作为一种新型网络，也开始受到机器人研究机构的重视。CMU的机器入研究所已经开始尝试使用自组网来解决他们的多机器人的通讯问题并展开了相关研究。当前，自组网的研究成果主要集中在美国。CMU的MONARCH工程组对自组网进行了深入研究，提出了一些权威的路由协议如DSR，并对目前主流的网络模拟器NS进行了扩展，使其能更好的用来测试、评价自组网路由协议。目前MONARCH工程组已经建立起了移动自组网的实验床301。他们的实验床由5个移动车载节点和两个固定节点组成。他们使用实验床对DSR协议进行了实验分析3。此外，CHARLESEPERKINS和ELIZABEHTMROYER提出的另一种自组网路由协议AODV已经成为RFC草案。另外，TF因特网工程任务组也已经成立了专门的研究小组MANET工作组，负责移动自组网的相关协议的标准化工作29。此外，欧洲也已经开始考虑将自组网作为中继，以扩大第二代和第三代移动通信系统的覆盖范围，提高在网络或链路故障时系统的健壮性，目前已经建立了AGSM实验系统321。13本文结构本文共分五章，内容安排如下第一章介绍了多机器人通讯网络的路由协议研究的选题背景和意义，讨论当前国内外的研究现状。第二章研究了自组网技术，包括其特点、关键技术和研究现状并比较了它与常用移动蜂窝通讯网络的区别。第三章阐述了自组网路由协议的特点，并研究了两种目前常用的自组网路由协议。第四章首先分析了目前常用自组网路由协议的优缺点，随后详细阐述了本文提出的MRCSRP路由协议并提出了相应的优化方法，然后按照RFC2501标准对MRCSRP路由协议进行了定性分析。第五章详细介绍了仿真实验，根据实验结果对MRCSRP协议进行了定量分析并比较了MRCSRP与AODV的性能差别。2自组网技术硕士论文2自组阿技术自组网的前身为分组无线网PACKETRADIO，是1970年由美国国防部远景规划局DARPR启动的一个研究项目，起初仅仅是为了满足军事应用需求，主要研究抗毁的、自适应的网络研究计划，低开销的分组无线网络研究计划等。经过多年的技术储备，DARPA在联合战术无线系统YRRS中扩大技术规模，并计划在今后5年内投人使用。自组网技术在军事领域发展的同时也引起了商用领域的极大兴趣。近年亲，自组网的商业价值逐渐受到重视，它能满足野外活动和救灾时的通信需求，可用于战斗单位、救灾工作系统以及城市车辆之间的通信，还可用于某些需要临时快速建立通信网络的场合。另一个有影响力的研究分支因特网任务工程组N3TF成立了专门的MANET工作组，自组网的设计思路也由传统的单一技术体系过渡到基于P的多技术体系，从而使自组网更具有开放性、适应性和灵活性，提高了开发速度TOL13J。自组网ADHOC是一种无线移动通信网络。它是一个多跳的临时性自治系统，整个网络没有固定的基础设施，由一系列带有无线收发装置的移动节点构成，节点同时具备主机与路由器两种功能【31】。在任意时刻，任一节点可向任意方向以任意速度运动，即节点间的运动是自主的。因此对于不同时刻的网络，其拓扑结构也随之发生变化。当通信双方在彼此的通信范围内时，自组网中的两个通信节点之间可直接进行无线通信。由于终端的无线覆盖范围的有限性，当通信双方间的距离超过彼此的通信范围时，用户终端可以借助于其它节点进行分组转发。每一个节点都可以说是一个路由器，它们要能完成发现和维持到其它节点路由的功能。因此，自组网通常是一个多跳MULTIHOP的无线移动网络。典型例子有交互式讲演，可以共享信息的商业会议，战场上的信息中继以及紧急通信需要【LOJI”。图21描述了一个由三个主机构成的一个简单的自组网。主机A不在主机C的通讯范围内A外面的圆圈表示主机A的通讯范围，主机C也不在主机A的通讯范围内，当主机A需要和主机C进行通讯时，需要主机B来为它们进行分组转发，因为主机B同时在主机A和C的通讯范围里。D图21自组网示例南京理工大学硕士学位论文多机器人通讯网络的路由协议的研究21白组网的特点无线自组网是没有固定网络结构的、由移动主机构成的自主系统，主要具有以下特征【LIJ1网络自主性相对常规通信网而言，自组网最大的区别就是可以在任何时刻、任何地点不需要现有的基础网络设施就可以搭建起来。它仅由一些充当主机与路由器的移动终端组成，网络搬迁非常方便。2生存时间短自组网一般是临时搭建的，任务完成后立即撤除。3动态拓扑从网络层来看，在自组网中，移动节点可以以任意速度和方向在网络中移动，加上无线发送装置发送功率的变化、无线信道间的相互干扰、地形因素等的影响，节点间通过无线信道形成的网络拓扑结构随时会发生变化。4带宽限制和变化的链路容量自组网采用无线传输技术作为底层通信手段，由于无线信道本身的物理特性，其相对于有线信道具有较低的容量；并且由于多路访问、多径衰落、噪声和信号干扰等多种因素，使得移动节点的实际带宽小于理论上的最大带宽值。5可能存在单向通信节点的发射功率、电池能量以及地理位置等可能存在单向链路。例如，若主机节点A、B的发射功率不同，A发射的信号B能收到，但B发射的信号A却不能收到，这时A，B之间存在的就是单向链路。6能量限制节点移动节点依靠电池提供工作所需的能量。减少功耗将是影响网络协议设计的一个非常重要的因素。7多跳通信由于无线收发机的信号传播范围有限，自组网要求支持多跳通信。多种多跳通信由此也带来了隐藏终端、暴露终端和公平性等问题。8分布式控制自组网中的用户节点都兼备独立路由和主机功能，还存在一个网络中心控制点，用户节点之间的地位是平等的，网络路由协议通常采用分布式控制方式，因而具有很强的独立性和抗毁性。而在常规通信网络中，由于存在基站、网控中心或路由器这样一类集中控制的设备，用户终端与它们所处的地位不是对等的，而且基站、网控中心或路由器的损毁将可能导致整个通讯网络的瘫痪。自组网是无集中控制中心的完全分52自组厨技术硕士论文布式的通讯网络，故当某节点出故障时，并不一定会使整个网络瘫痪。9有限的安全性通常移动无线网络由于采用无线信道、有限电源、分布式控制等原因，会比有线网络更易受到安全性的威胁。这些安全性的攻击包括窃听、电子欺骗和拒绝服务等攻击手段。22自组网的关键技术1自组网的路由技术在自组网里，移动节点通过多跳无线链路实现相互间的通信。整个网络没有固定的基础设施，比如基站。网内每一个节点都具有路由器的功能，可以向其它节点转发数据分组。由于动态变化的网络拓扑结构，节点不可能永远的保存其他节点的路径信息，这使得开发自组网的路由协议比起其他网络的路由协议来说更富有挑战性。因而，开发一种能有效地找到节点问路由的动态路由协议成为自组网设计的关键14T。2自组网的安全问题与传统的无线网不同，自组网作为一种新型的无线移动网络，不依赖于任何固定漫施，而是通过移动节点间的相互协作保持网络互联。由于该网络的独特性，它正逐步运用于商业环境。设计这种网络面临的一个主要挑战就是它易受到安全攻击，比如受到窃听、伪造、拒绝服务等攻击1”。在自组网中没有基站或中心节点，所有节点都是移动的，网络的拓扑结构动态变化。节点问通过无线信道相连，没有专门的路由器，由节点自身充当路由器，同时也没有命名服务、目录服务等网络功能。这就导致了在传统网络中的安全机制不再适用于自组网，所以应提出专门针对自组网的安全机制。目前提出的安全策略有基于口令的认证协议，它与传统的口令认证不同的地方是密钥和口令的产生是由多台机器决定，而不是集中由台机器产生，并且还提供了一种完善的口令更新机制；“复活鸭子”的安全模式，它主要针对传感器网络里，传感器与控制者之间可能存在的不安全问题，提出传感器在“死亡”之前，只受其拥有者的控制异步的分布式密钥管理，它提出密钥管理服务是由多个节点一个集合来管理，而不是单个节点来管理1DJ。T3自组尉网际互联自组网是一种多跳网，目前，大部分的路由算法都是用于单个自组网网内的，现在大多数研究也都集中在这个方面，很少涉及如何把多个自组网子网联接成一个大网以及如何与有线INTEMET相结合。通过使用网关路由器，可以实现将几个自组网互联以及网内节点可以访问互联网的功能。这种形式可以向位于多个分散地理位置上的工作小组提供协同通信能力【14】。自组网与INTEMET和广域网的互联，从外部来看，可以认为自组网是一个M子网。6南京理工大学硕士学位论文多机器人通讯网络的路由协议的研究网内部分分组的传送是由网内路由协议完成分组到达目的地可能要经过多跳，而当分组进入或离开子网时，采用标准M路由机制。这就要求网关节点要能运行多种路由协议N41。23自组两的研究现状90年代以来，自组网的研究在世界范围内方兴未艾，已经从无线通信领域中的一个小分支逐渐扩大到相对较独立的领域。目前，无论在国际上还是在区域上欧洲和亚洲等地区，周期性的自组网学术会议日益增多。自组网的研究现状和成果主要在以下几个方面【L“1提出新的路由协议。自组网路由面临的主要挑战是传统的保存在节点中的分布式路由数据库如何适应网络拓扑的动态变化。新协议一般以广播或组播方式建立网络路由，核心是减少广播风暴。目前，一般普遍得到认可的代表性成果有DSDV、WRP、AODV、DSR、TORA和ZRP等。不过，从实现的难度来看，这些协议离现实应用还有一定的距离。2基于自组网的媒体接入控带IJMAC协议。主要是解决隐藏终端和暴露终端问题，影响比较大的有MACA协议，即R1SCTSACK方案，控制信道和数据信道分裂的双信道方案和基于定向天线的MAC协议，以及一些改进类的MAC协议。有一些研究则是侧重于将IEEES0211的MAC协议移植到自组网中。基于定向天线的MAC协议在理论上性能较为优越，但在技术上实现的难度较大。3自组网与蜂窝网的互连互通。有人研究并提出了一种ICARINTEMETCELLULARANDADHOCRELAY系统，提供蜂窝小区内信号的补盲。从结果看，该系统只是针对目前的2G系统，尚无法联系到基于口方式的分组网络。4基于自组网的多播组播协议、TCP协议、地址分配、功率节能控制、安全性问题、分布式算法、QOS等方面有一些研究成果，但这些部分并没有成为研究的热点。24自组网与常规移动通讯两络的区别常规移动无线通信网络通常是以蜂窝移动通信网络方式出现。在目前的蜂窝移动通信网络中，移动终端和固定基站相互通信，移动交换机负责路由和交换功能，同时充当网关，通过有线方式接入固定网，移动终端不具备路由功能。自组网与常规移动通讯网络的区别主要有1自组网无通讯基础设施的支持对于常用的蜂窝移动通信网络，如GSM、GPRS等，都需要有诸如基站等固定2自组婀技术硕士论文设施的支持。用户终端通过基站进行通讯，彼此间不能直接进行通讯。基站和用户终端不是平等的，即在有基站的蜂窝移动通信网络中采用集中控制的方式。而自组网的特点就是不需要任何现成的网络设施的支持，它可以在需要时快速构建。在自组网中，各主机是相互平等的，整个网络采用全分布式的控制方式。2自组网的网络结构不停的发生变化在常用的蜂窝移动通信网络中，虽然终端也不停的移动，但其固定设施没有移动，所以总的来说，其网络拓扑结构还是比较稳定的。在自组网中，任何节点的移动都将造成网络拓扑结构的实质性变化。3业务类型不同目前的蜂窝移动通信网络通常提供语音、数据及多媒体业务1331，而自组网主要提供数据业务。4提供的服务可靠性不同常用的蜂窝移动通信网络提供的很多服务都存在着延迟、误码率高的不足，而自组网提供的服务相对来说可靠性比较高、网络延迟也比较短。25本章小结为了更好的研究多机器人系统通讯问题，本章对自组网进行了一个简单的介绍。其中包括自组网的基本概念、自组网的特点、自组网的关键技术和它的研究现状。最后对自组网与目前常用的蜂窝移动通讯网络进行了比较。南京理工大学硕士学位论文多机器人通讯网络的路由协议的研究3自组网路由协议在自组网里，移动节点通过多跳无线链路实现相互间的通信。整个网络没有固定的基础设施。网内每一个节点既是终端又是路由器。开发一种能有效地寻找节点间路由的动态路由协议成为自组网网络设计的关键，也是更好的解决多机器人系统通讯问题的关键。本章首先对自组网路由协议进行概括性介绍，然后阐述了两种目前常用的自组网路由协议的基本原理。31自组网路由协议概述311自组孵路由协议设计要求多跳、移动通信、动态组网是自组网的基本特征，也是自组网路由协议设计的前提和基础。因而，自组网路由协议需要能够实现以下的功能1能感知网络拓扑结构的变化自组网路由协议要能够检测到网络拓扑的动态变化。因为自组网网络需要进行多跳通信，所以路由协议必须确保路径中的链路具有很强的连接性。自组网网络中的节点必须知道它的周围环境和可以与它直接进行通信的节点。自组网网络里提供网络连接的方法主要有两种平面路由网络结构和分层路由网络结构。在平面路由网络结构中，所有的节点都是平等的，分组路由是基于对等连接的。但是在分层路由结构中，较低层至少要有一个节点作为与高层联系的网关【L”。平面路由网络结构分层路由网络结构图3111自组网里的网络连接方式2维护网络拓扑连接因为每个移动主机都可以随时改变位置，所以网络拓扑是频繁变化的。这样，自组网路由协议为了维持节点之间的链路具有较强的连接性，它必须动态更新链路状态93自组网路由协议硕士论文和对自己重新配置。如果采用中心控制的路由算法，为把节点链路状态的改变传送到所有的节点，就会消耗掉节点过多的时间和精力，显然是不适合的。所以自组网的路由算法应是全分布的CL“。3高度自适应的路由相对予有线网络里的静态节点，自组网网络要求一个高度自适应的路由机制来处理快速的拓扑变化。而传统的路由协议，如距离向量算法和链路状态算法，都要求在指定路由器润定期交换大量路由信息，这在自组网里是不能有效工作的。所以必须针对自组网的特点，提出新的路由算法或对现有的路由算法进行有效的改进【J”。312自组网路由协议的概况自从20世纪70年代初DARPA提出数据包无线电网络PACKETRADIONETWORKS起，就开始陆续出现一些专门为自组网设计的路由协议。这些协议必须能够处理自组网的一些固有的局限性，比如较高的能源消耗、低带宽和高误码率。实质上，自组网路由协议就是分布式系统中的最短路径问题。每一个数据包在它的包头里存放着目的节点的M。当某一节点收到数据包时，它根据自己的路由表将该数据包转发给通往目的节点的下一跳节点。数据包一直的被转发，直到到达目的节点。不同的路由协议在路由表的构造、维护和更新上彼此不同。然而，总的来说路由协议都希望达到一个共同的目的，那就是使用最优路径来传输数据。目前，路由协议大体上可以分为两类1表驱动路由协议，2源驱动按需路由协议。尽管这两类协议是为同一种网络设计的，但是它们之间却存在着明显的差别。1表驱动路由协议表驱动路由协议要求网络中的每一个节点保存通往网络中其他所有节点的持续的、实时的路由信息。这类协议需要节点保存一张甚至数量更多的路由表用来存储路由信息。为了维护持续的网络结构图，节点周期性的在整个网络内广播更新信息。同时，节点也通过周期性的广播来对网络拓扑结构的变化做出反映。表驱动路由与传输数据包时的无连接方法相似。节点不管某条路径是否需要，什么时候需要以及对该路径需要的频繁程度，它都在自己的路由表中保存这样一条路径信息。从根本上说，表驱动路由依赖于路由表更新机制，这种更新机制包含了路由信息的经常性广播。在表驱动路由协议中，因为路由信息被周期性的广播和保存，所以，对某节点来说，不论这些路径是否需要，它总是保存着通往整个网络中其他任何节点的路径。这种特性尽管对于自带路径信息的数据流也是有用的，但它却招致了实质性的网络负载和能量消耗。由于带宽和电池能量对于移动计算机是非常稀缺的，这种特性成了一种非常严重的局限性。2源驱动按需路由协议10南京瑾工丈学硕士学位论文多机器人通讯隔络的路由协议的研究源驱动按需路由协议仅在源节点需要通往某一节点的路由时才发起路由请求进行寻径。当某一节点需要通往某一目的地的路由信息时，它在整个网络内进行路由发现。当一条路径被找到或者所有可能路径都被尝试过后，路由发现过程结束。某条路径一旦被建立，它将被某种路由维护机制所保持直到对源节点来说目的节点变的不可到达或者这条路径不再需要。源驱动按需路由不需要周期性的广播路由信息，这大大节省了网络带宽和节点能量。使用按需路由协议的节点不知道通往网络中某一节点的路由除非它需要这样的路由信息。当一个使用按需路由协议的节点需要向某一新的目的地发送数据时，它将等待路由发现过程为它寻找一条合适的路径。在接下来的两小节中，介绍两种常用的自组网动态按需路由协议。32DSR321DSR榻述为了向另一个节点发送数据，源节点在数据包的包头里构建源路由，源路由里包含了通往目的节点的完整的路径信息。源节点把数据包发往源路由里的第一个节点。当主机收到数据包后，如果它不是目的节点，那它仅仅按照源路由提供的路径把包转发给下一跳节点而不做任何处理。数据包一直被转发直到到达目的节点35】。自组网中的每个节点都保存着一张路由表，路由表中存放着节点知道的路径信息。当节点需要向另一个节点发送数据时，它首先查看自己的路由表。如果找到需要的路径，它就用该路径发送数据；如果没有找到需要的路径，节点利用路由发现机制寻找通往目的节点的路径。在等待路由发现的过程中，节点正常处理其他事件，比如接收和转发数据包。在路由发现过程中，节点根据上层协议的要求缓存数据包待需要的路径找到后发送数据包或者直接将它丢弃。路由表中的每一项都标注一个到期时间，时间到后相应的表项就被删除【3。当节点正在使用某条路径时，它监控这条路径是否完好。例如源节点或者是目的节点或者是路径中的其他中间节点移出了它的上一跳或是下一跳节点的通讯范围，则这条通往相应目的节点的路径就变得不可用了。路径中的任何节点出现故障后，此路径就不再能使用。这种监控正在使用的路由的完好性称为路由维护。当路由维护发现正在使用的路由出现问题而不再能用时，节点将再次进行路由发现来寻找一条新的、正确的通往目的节点的路径瞄“。322路由发现自组网里的每个节点利用路由发现机制动态的寻找去往任何节点的路径。发起路由发现的节点向它的邻居节点广播路由请求包。路由请求包中包含了这次路由发现的113自组网路由协议硕士论文目的节点。如果路由发现成功的话，源节点会收到路由回复包，回复包里列出了通往目的节点的路径所包含的各个中间节点。请求包里除了含有源节点地址和目的节点地址夕，还有一个路由记录项。在路由记录项里保存着路由发现过程中转发请求包的所有节点。每个请求包都有一个由源节点产生的惟一的请求ID。为了检测到请求包的副本，每个节点保存着它最近处理过的源节点地址，请求ID对。当节点收到路由请求包时，它按照下面的过程处理请求包06图3221请求包的处理过程路由请求包在整个网络内不停的被转发，直到它到达目的节点，由目的节点向源节点发送回复包。源节点广播的路由请求包仅被它的邻居节点收到，这些节点若本身不是目的节点并黾这个请求包对它来说也不是冗余的，它继续广播请求包。若节点已经出现在路由记录项中便不再处理该请求包，这样可以有效的防止路由环的产生。同样，节点对于已经处理过的请求包也不再处理。为了向源节点发送路由回复包，目的节点要有去往源节点的路径。如果目的节点的路由表里有去往源节点的路径，它用这条路径和发送其他数据包样发送回复包。12南京理工大学硕士学位论文多机器人通讯网络的路由协议的研究否则，目的节点反转请求包路由记录项里的路径，并用反转路径来发送回复包。利用反转路径发回复包时，要求网络支持双向链路。另外一种可供选择的方法是，目的节点重新进行路由请求，它把回复包放在请求包中一起广播出去。323路由维护传统的路由协议通过周期性的广播路由信息把路由发现和路由维护集成在一起。如果链路或者节点发生改变，周期性的路由广播最终能使得所有节点都知道这种改变，这也将导致新路由的出现。然而，使用路由发现机制后就没有周期性的广播消息。相反，当一条路径正在被使用时，路由维护机制监测路径的完好性，并告诉源节点任何可能的错误“。由于无线网络天生就没有有线网络可靠，许多网络为了尽早检测到包丢失和包冲突以便进行重传而利用数据链路层的点对点确认。在这样的网络中，路由维护很容易实现，因为对于每一个节点，主机往下一节点传输包时很容易知道下一节点是否正常工作。如果数据链路层报告一个它无法修复的传输故障比如已经超过了它所允许的最大重传次数，节点就向源节点发送一个错误包告诉源节点路径出现了错误。路由错误包包括链路断开的两端的节点检测到错误的节点和它试图传输数据的下一跳节点。节点收到路由错误包后，发生错误的节点被从路由表中删去，并且所有包含这一跳的路由都被标记为无效。如果无线网络不支持这样的底层确认，在很多情况下，可以获得一个等价的确认。如果节点可以在网络接口处采用PROMISCUOUS模式，则节点往下一跳传输包后，它可以监听下一跳节点是否沿着即定的路径传输包。此外，源节点的可用的传输层或是应用层的回复或确认可以用来确认某条路径是否依旧可用。最后一种确认方法是将包头的一位用作确认位，要求下一跳节点收到包后往回发送一个确认信息。如果在一段时间内，没有收到下一夥节点发来的任何确认信息，节点可以利用这一位来方便的探测下一跳节点的状态。为了向源节点发送错误包，节点必须知道去往源节点的路径。如果节点的路由表里保存着到源节点的路径，它就用这条路径来发送错误包。否则，节点将数据包中的路径反转后利用反转路径发送错误包，或者重新发起路由请求，并将错误包放在路由请求包中一起发送出去。圄发错误包的另一种方法，节点暂时缓存错误包，同时，节点利用路由发现寻找通往源节点的路径，待路径找到后，节点沿该路径发送错误包。然而，这种方法不能用来发送路由回复包，因为如果两边节点的路由表中都没有通往对方的路径，那么两边的节点都不能顺利完成路由发现。如果网络中存在单向链路，路由维护也经常使用端到端的确认，而不是上面提到的点到点的确认。只要两个节点阃存在某些路径，路由维护就有可能。在这种情况下，】33自组网路由协议硕士论文现有的源节点传输层或是应用层的回复或是确认或者是明确的网络层确认可用来确定另个节点的状态。利用点到点确认，错误包明确指出哪个节点出现了故障，而利用端到端确认，源节点只能假设通往目的地节点的最后一跳节点出现了故障翊。33AODV331AODV的概述另一种常用的自组网路由协议是AODV。AODV是纯粹的按需路由获得系统，不处于活动路径上的节点既不维护任何路由信息也不参与任何路由表信息的周期性交换。更进一步说，仅当两个节点需要进行通讯，或者是节点作为另两个节点的中继为它们进行数据转发时，节点才寻找和维护去往另一个节点的路径【3”。当节点想要知道它的邻居节点时，节点可以通过好几种方法来感知它们，其中包括周期性的发送HELLO报文。邻居节点的路由表被组织起来以对本地移动的响应时间进行优化并为新的路由建立提供更快的响应时间。AODV借鉴了DSR的广播路由发现机制。然而，AODV没有采用源路由思想，而是依赖于中间节点动态的建立路由表。它与DSR的这种区别在节点较多的网络里显得非常有用，因为它减少了每个数据包里携带的大量控制信息。为了维护节点间最新的路由信息并防止路由环的产生、AODV借鉴了DSDV的目的节点序列号思想。然而，与DSDV不同的是，每个节点维护一个单一增加的序列号计数器，并用它来剔除陈旧的路由信息。AODV正是结合了这些技术而产生的一种新的路由协议。AODV通过减少网络负担从而有效的利用带宽，它对网络拓扑变化能快速做出反映并且确保无环路由。332路由发现当个节点需要和另一个节点通讯，而它的路由表里又没有相应的路由信息时，节点进行路由发现来寻找路径。每个节点维护两个相互独立的计数器节点序列号计数器和广播ID计数器。源节点通过向邻居节点广播路由请求包RREQ来进行路由发现跚。RREQ的结构如下源节点地址源节点序列号广播目的节点地址目的节点序列跳数ID源节点地址，广播ID对唯一的标识RREQ。源节点每次产生新的RREQ，广播ID就自增L。邻居节点要么满足RREQ而向源节点发送一个路由回复RREP要么把14南京理工大学硕士学位论文多机器人通讯网络的路由协议的研究RREQ里的跳数增加1后向自己的邻居节点广播。注意到一点，节点可能从不同的邻居那收到同一路由广播包的若干个副本。当中间节点收到一个RREQ后，如果它已经收到过具有相同源节点地址和广播ID的RREQ，那么它将这个RREQ丢弃而不再广播它。如果节点不能满足RREQ的要求，为了建立反转路径，也为了传输RREP时建立向前路径，它将记录如下信息目的节点口地址、源节点P地址、广播ID、反转路径的过期时间和源节点序列号。3321建立反转路径在RREQ里除了广播ID之外还有两个序列号源节点序列号和源节点知道的最新的目的节点序列号。源节点序列号用来维护反转路径的新信息，目的节点序列号用来在路径被源节点采用之前更新去往目的节点的路径。当RREQ从源节点到达不同的目的节点时，它自动的建立起指向源节点的反转路径。为了建立反转路径，节点记录第一个发给它RREQ的节点。这些反转路径的信息被保存足够长的时间以使得RREQ能够在整个网络范围内被传播并由相应的节点给源节点产生一个回复【37】。D建立反转路径3,322建立向前路径D建立向前路径图33211向前路径和反转路径的建立RREQ最终到达能够产生去往目的地的路径的节点，多数情况是到达目的节点。收到RREQ的节点首先检查RREQ是否是通过双向路径传过来的。如果中间节点的路由表中有去往目的节点的路径，它通过比较自己路由表中表项的目的节点序列号和RREQ的目的节点序列号来判断自己路由表中的路由信息是否够新。如果RREQ的序3自组网路由协议硕士论文列号比中间节点路由表中的序列号大，中间节点就不能用自己路由表里路由信息的来回复RE,EQ，中间节点重新广播RREQ。仅当节点路由表中的目的节点序列号比RREQ大或者两者相等时，中间节点才产生回复包。当节点路由表中有一条当前路径信息，并且节点之前没有处理过此RREQ时，它向发给它RREQ的节点单播路由回复包。RREP的结构如下当请求包到达可以提供去往目的地节点路径的节点时，通往RP,EQ源节点的路径已经建立。当RREP被传回源节点时，路径上的每个节点建立起指向前一节点的指针，更新相应路由表项的过期时间并且记录目的节点的最新的节点序列号。不在RREP传输路径上的节点在等待ACTIVE_ROULETIMEOUT时间后删除反转指针。收到RREP的节点对特定的节点广播RREP。当节点再次收到了RREP时，仅当这个RREP具有较新节点序列号或者相同节点序列号但路径更短时，它才更新自己的路由表并广播RREP。节点抑制了所有它收到的其他RREP。这减少了发往源节点的RREP的广播数量，同时又保证源节点能够收到更新、更短的路径。源节点收到第一个RREP后就开始传输数据，在它获知更好路径后更新自己的路由表。333路由表管理在路由表里，除了源节点和目的节点的序列号之外，还记录了其他一些有用信息，这些信息被称为与表项有关的软状态信息。与路由表中反转路径有关的是一个路由请求过期记时器。这个记时器是为了清除不在从源节点到目的节点的路径上的节点的反转路径表项而设置的。过期时间的长短取决于自组网的大小。与路由表项有关的另一个重要的参数是路由缓存过期时间，或者是一个时间点，在这时间点之后该路由表项就被认为是无效的“。在每个路由表项里还保存着活动邻居节点。活动邻居节点通过该节点往某些蜀的节点发送数据。在最近的ACTIVE_TIMEOUT时间段内，邻居至少发起或者转发去往目的节点的一个数据包，那它才被认为是活动邻居节点。活动邻居节点的信息被保存，所以在去往目的节点的路径发生链路断开时，所有的活动邻居节点都被告之。节点路由表中的路径被任何活动邻居节点使用时，它就被认为是活动路径的。注意到一点，与DSDV一样，路由表中所有的路径都由目的节点序列号标识，这有效的防止了路由环的产生。甚至是在包无序传输和节点移动速度很快这样的极端情况下，也不会产生路由环。路径每次被使用后，表项的过期时间就被重新设置为当前时间加上16南京理工大学硕士学位论文多机器人通讯网络的路由协议的研究ACTIVE_ROUTE_TIMEOUT。当节点收到新的路由信息时，它比较新路径的目的节点序列号和当前路径的目的节点序列号。节点选择具有较新节点序列号的路径。当两者的序列号相同时，节点选择跳数较少的路径。334路由维护AODV利用路由维护策略来维护正在使用的路径。不处在活动路径上的节点的移动不会影响去往目的地的路径。如果源节点在一次活动会话中移动出了下一跳节点的通讯范围，它可以重新进行路由发现寻找去往目的节点的新的路径。当路径中的中间节点或是目的节点移动后，一个特殊的RREP包将被发送到受影响的源节点。周期性的HELLO报文可用来保证双向链路的畅通并且检测链路是否完好。用来检测链路状态的另外一种可供选择的并且具有较少传输时延的方法是利用数据链路层的确认UACKS。当往下一跳节点发送数据失败时，链路错误也被检测到【3”。当下一跳节点变的不可到达时，链路断开处的上游节点主动广播一个特殊的RREP。这个RREP具有较新的节点序列号比它所知道的目的节点序列号大并且跳数为“无穷大”。那些节点随后向他们的活动邻居转发RREP。RREP一直被转发直到所有的活动源节点都知道这个消息。因为AODV是无环的而且自组网的节点数目有限，RREP被转发的过程最终会结束。在收到链路断开的消息后，源节点如果还需要去往目的节点的路径，它将重新进行路由发现。为了决定路径是否还需要，节点检查该路径最近是否被用过，并且检查上层协议对该路径的链接是否依旧保持。如果源节点或者路径上的其它节点决定需要重建该路径的话，节点将重发RREQ，这个RREQ具有比已知的目的节点序列号更大的目的节点序列号。这是为了确保建立一条更新的、有效的路由。如果其他节点认为之前的路径依旧有效的话，没有节点会回复这个RREQ。335本地连接管理节点可以通过两种方法知道他们的邻居。当节点收到邻居的广播包时，它更新它的本地连接信息来确保该节点在它的邻居节点表里。若节点在HELLOINTERVAL时隙内没有发送过任何广播包，它将发送一个HELLO报文，其中包括它自己的身份标识和序列号。在HEILO报文的传输过程中，节点序列号保持不变。HELLO报文的生存时间被设为1从而有效的防止HELLO报文被再次广播。邻居收到HELLO报文后，更新自己的本地连接信息。收到一个新邻居的广播包或HELLO报文，或者在ALLOWED_HEUOLOSS时隙内没有收到旧邻居的HELLO报文都被认为是本地连接改变的指示。没有收到不活跃邻居的HELLO报文不会触发协议的任何事件。使用HELLO报文来管理本地连接也可以用来确认3自组网路由协议硕士论文只有拥有双向链路的节点才是邻居。出于这个目的，节点发送的HELLO报文里还包含了向它发送HELLO报文的节点。每个节点通过检查来确认它所使用的路径是通过能收到它的HELLO报文的邻居节点。为了节省带宽，仅在两个节点明确要求时，才进行这样的检查1371。34本章小结自组网路由协议已经成为目前自组网研究的热点，也是解决本文研究的多机器人系统通讯问题的重点。本章首先介绍了自组网路由协议的设计要求和研究现状。在此基础上，阐述了两种目前常用的自组网按需路由协议DSR和AODV的基本原理。这两种路由协议都是典型的动态按需路由协议，但它们在路由表的维护和更新、路由发现和路由维护机制上各不相同。通过对它们的研究，为本文提出用于多机器人通讯网络的路由协议做好了准备。南京理工大学硕士学位论文多机器人通讯网络的路由协议的研究4MRCSRP协议为了能更好的解决多机器人系统的通讯问题，本文提出了一种专门用于多机器人通讯网络的路由协议一一MRCSRPMULTIROBOTICCOLNMLLNICATIONSYSTEMMUTINGPROTOC01。该协议针对多机器人系统动态组网、移动通讯、数据传输量比较大的特点而设计，支持多机器人系统在动态环境下的各种应用。从理论上说，多机器人通讯网络可以抽象成自组网。MRCS