（微电子学与固体电子学专业论文）移动ad+hoc路由网络在微系统中的应用.pdf

上海交通大学硕士学位论文 - - i - 移动移动 ad hoc 路由网络在微系统中的应用路由网络在微系统中的应用 摘摘 要要 ad hoc 网络具有无中心和自组织的特性，能在没有固定设施或设 施被破坏的情况下，快速便捷地组建网络，实现随时随地联网通信， 因而受到广泛关注。路由协议作为网络的组网策略，是其内部节点得 以互连的基础。它控制着整个网络的组织运行，是 ad hoc 网络研究 的热点。 根据项目实际要求，需要路由协议具有网络延迟小、健壮可靠的 特点， 在分析现存各种路由协议后， 选取 mmrp(mobile mesh routing protocol)路由协议作为研究内容。它很好地满足项目技术要求，采用 主动式、链路状态路由方式，控制网络数据的传输与分发，在低移动 性，低容量的拓扑环境下表现良好。 在移动 pc 机上，使用无线网卡，模拟网络移动节点的组网过程。 基于 tcp/ip 网络模型，使用 windows socket 进行网络编程，并制作 界面显示程序。实验验证了 mmrp 协议的技术特点：在无中心节点 的情况下，能自行组网通信，节点间基于路由表信息多跳传输，实现 数据分发。当网络拓扑结构发生变化时，协议能快速准确地对变化做 出响应， 更新路由表。 实验结果证明 mmrp 是一种高效实用的 ad hoc 路由协议。 在此基础上，选用 arm7tdmi 硬件平台来实现 mmrp。比较 上海交通大学硕士学位论文 - - ii - tcp/ip，bluetooth 和 zigbee 协议栈，zigbee 协议具有低功耗、代码 实现简单和源码公开的优点，被选取用来实现无线通道的可靠传输。 将 zigbee 协议代码移植到 arm7 上，配合使用支持 zigbee 协议 的无线 rf 芯片 cc2420，组建网络。现已实现 3 个节点之间的组网。 关键字：关键字：ad hoc，mmrp，路由，arm，zigbee 上海交通大学硕士学位论文 - - iii - application of mobile ad hoc routing network in the micro-system abstract due to the specialty of non-infrastructure and self-organize, people are paying more and more attentions on ad hoc network. ad hoc network allow people and devices to access to internet in areas with no pre-existing infrastructure, and realize the expectation of communicate with each other anywhere and at anytime. as the strategy of network system, routing protocols are the principle of the interaction of the nodes in the network. in charge of the networks organization, they are the hottest field of the ad hoc network research. according to the requirement of the project, those protocols need to have short delay and to be robust. after analyzing different kinds of exiting routing protocols, we select mmrp as our research interest, which well meets the requirement of our project. mmrp is s a proactive and link-state based protocol. it decides the direction of the datagrams transmission and distribution, and works well in low-mobility and low-load circumstance. 上海交通大学硕士学位论文 - - iv - on laptops, we simulated the process of the organization of mobile nodes by using the nic (network interface card). we program with windows socket, base on tcp/ip module. mmrp was well reflected in the gui (graphical user interface). it proves the technical features: nodes can form a network system themselves without centralized control and the data packets are transferred in multi-hop manner according to the route table. also, routing protocol can quickly and correctly react to the topology changes in updating the route table. to realize the mmrp, we choose the arm7 for hardware board. compared with tcp/ip and bluetooth, the characteristics of low energy-consuming, easy realization and open source code, make zigbee the preference of reliable transmission on wireless channels the codes of the zigbee are transported on the arm7 board. up to now, with the help of cc2420 which supports the zigbee protocol, we have constructed the wireless personal area network, consisting of 3 nodes. key words：ad hoc，mmrp，routing，arm，zigbee 上海交通大学上海交通大学 学位论文原创性声明学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究工作所取 得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人或集体已经发 表或撰写过的作品成果。对本文的研究做出重要贡献的个人和集体，均已在文中以明 确方式标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：于于 慰慰 日期： 2007 年 1 月 26 日 上海交通大学上海交通大学 学位论文版权使用授权书学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向国 家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权上 海交通大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用 影印、缩印或扫描等复制手段保存和汇编本学位论文。 保密保密，在 年解密后适用本授权书。 本学位论文属于 不保密 不保密。 （请在以上方框内打“” ） 学位论文作者签名：于于 慰慰 指导教师签名：李李 振振 波波 日期： 2007 年 1 月 26 日 日期： 2007 年 1 月 26 日 上海交通大学硕士学位论文 - - 1 - 第一章 绪 论 第一章 绪 论 1. 研究背景 1. 研究背景 近年来，网络正日益进入人们的生活，人们对网络通信的要求也不断提高， 希望能随时随地联网通信。移动计算通信设备，如手机、手提电脑，的广泛使用 正在改变我们这个社会的生活方式。 无处不在的移动终端使无线网络成为最佳选 择，它克服了传统网络技术的不足，真正体现方便、迅速的要求。 (1) ad hoc 网络的发展及研究现状 (1) ad hoc 网络的发展及研究现状 无线网络，是以无线信道作为传输媒介的计算机网络，自从二十世纪七十年 代出现以来，它已逐渐成为计算机网络中一个至关重要的组成部分。当前存在两 种无线网络： (1)一种是有基础设施(infrastructured)的网络， 如蜂窝移动通信网络， 无线局域网(wireless local area network)。 该网络由若干移动节点和被称之为 “基 站”的基础设施组成，其拓扑结构为“星形” ，网中的移动节点通过基站转发数 据才能与网内其他节点通信，它必须要有固定网络设施支持。同时，如果基站通 过有线连接其他网络，网内节点便能通过基站访问其他网络，如 internet。(2)而 另一种无线局域网是无基础设施的，通常称为 ad hoc 网络。它组网灵活、快捷， 可广泛应用于军事或救援等无法或没有预先铺设网络设施的场合。 不需要预先的 网络设计规划、布线、设备的安装调试，随时随地立即组网是移动 ad hoc 网络 的突出特点和优势所在。随着社会信息化进程和互联网的飞速发展，人们对无线 网络的移动性要求越来越高，ad hoc 网络由于其方便灵活的特点越来越受到人 们的重视，关于该网络的多种研究课题都已成为热点。 经典的 ad hoc 网络的前身是分组无线网(packet radio network) 1。早在 1972 年，美国国防部 darpa 就启动了分组无线网项目 prnet，研究在战场环 境下利用分组无线网进行数据通信。 之后， darpa 于 1983 年启动了高残存性自 适应网络项目 suran ( survivable adaptive network) 2，研究如何将 prnet 的 研究成果加以扩展，以支持更大规模的网络。1994 年，darpa 又启动了全球移 上海交通大学硕士学位论文 - - 2 - 动信息系统 glomo (global mobile information systems)项目3,旨在对能够满足 军事应用需要的、可快速展开、高抗毁性的移动信息系统进行全面深入的研究。 成立于 1991 年的 ieee802.11 标准委员会4采用了“ad hoc 网络”一词来描述 这种特殊的自组织对等式多跳移动通信网络，ad hoc 网络就此诞生。ietf 也将 ad hoc 网络称为 manet(mobile ad hoc network)5。 ad hoc 的意思是“for this”引申为“for this purpose only” ，即“为某种目的 设置的，特别的”意思，即 ad hoc 网络是一种有特殊用途的网络。ad hoc 网络 是由一组带有无线收发装置的移动终端组成的一个多跳临时性自治系统6。移 动终端具有路由功能，可以通过无线连接构成任意的网络拓扑。在 ad hoc 网络 中，每个移动终端兼备路由器和主机两种功能：作为主机，终端需要运行面向用 户的应用程序， 完成移动终端的功能， 包括人机接口、 数据处理等； 作为路由器， 终端需要运行相应的路由协议，负责维护网络的拓扑结构和路由信息，根据路由 策略和路由表参与分组转发和路由维护工作。在 ad hoc 中，由于无线终端的无 线传输范围有限， 两个无法直接通信的终端节点往往要通过多个中间节点的转发 来实现通信13。所以它又被称为多跳网络(multi-hop network)或自组织网络 (self-organized network)。 由此可见， ad hoc 网络中的路由协议是其内部节点得以 互连的基础，是 ad hoc 网络研究的重点。由此引出下面部分：ad hoc 网络路由。 (2) ad hoc 网络路由网络路由 适用于动态拓扑结构的高效实用的无线路由协议是移动 ad hoc 网络的关 键和难点。internet 工程任务组(ietf)专门成立了一个移动 ad hoc 网络工作组 (manet)，其主要工作就是针对无线 ad hoc 多跳网络的开发和研究。 ad hoc 网络是一种无中心网络，这意味着网络中的所有节点都需要发送， 接收以及中继数据报，这就需要路由协议来控制管理。而这些路由协议也必须与 manet 网络的特点相适应：时变的拓扑，多跳，能源限制等。 过去十几年中，manet 技术的研究主要集中在动态路由方面，已有几十种 算法提出，如 dsr7，aodv8，dsdv9，和 mmrp10等，而且新路由协 议，新处理方法不断涌现。为了让 ad hoc 网内节点之间的业务传输更加可靠， 当前已经有很多人针对这些协议做了大量的性能分析、研究和改进，如 j.broch 上海交通大学硕士学位论文 - - 3 - 等分析了特定移动和业务场景下 dsdv, dsr, aodv 和 tora 四种协议在丢包 率、路由信息开销和路径长度方面的特性11。路由协议就将下章具体说明。 2. 选题背景和问题描述选题背景和问题描述 本课题是国家自然科学基金（10477013）资助项目。实现具有自组织能 力、移动路由的无线互联网络是该课题的主要目的。 该项目应用于微系统通信中，各个微系统智能单元作为ad hoc网络的网 络节点在没有中心接入点的情况下参与网络的构建。各智能单元是对等的， 通过分布式算法协调各自的行为，监控网络拓扑的变化，交换路由信息，产 生、选择和维护路由。并根据选择的路径转发数据，提供网络的连通性，达 到即时联网通信的效果。 微系统的运行环境特点及技术要求决定着路由协议的选取以及运行。微系统 智能单元具有如下特点： (1) 移动性要求不是很高。 微系统智能单元由于自身原因，运动速度不是很高， 虽然有些节点可能会往任意方向移动，网络拓扑结构随着发生变化，但网络拓扑 变化造成的影响对整个网络系统很小，因为很多情况是：虽然节点的位置发生了 变化但路由协议选择的旧路径仍然有用。 并且更多节点在大部分时间还是相对静 止的。因此整个网络的拓扑结构变化不大，在某段特定时间内，可以看成是静止 的，或者是近乎静止的。 (2) 实时性要求。 系统需要即时的对可能出现的情况做出反应，因此，对路由 协议的实时性提出更高的要求，那些能达到快速准确地实现源-目标节点间通信 的路由协议将被考虑。 (3) 节点数不是很多。 网络的节点数大约在 20-30 个之间。 同时，ad hoc 网络固有的网络协议要求，如网络负载小，能量消耗，可靠传 输等技术要求也是在考虑范围之内。最后我们通过比较分析，选取 mmrp 路由 协议作为我们的项目研究内容，详细说明请看下章分析解释。 3. 论文工作论文工作 结合上面提到的项目，广泛阅读相关领域文献资料。在了解 ad hoc 网络特 上海交通大学硕士学位论文 - - 4 - 性的基础上，考虑实际项目的要求，理解掌握 mmrp 协议的原理和处理方法， 在 pc 机上通过无线网卡模拟实现了 mmrp 路由协议，并对试验结果进行认真 分析。在此基础上，选取 arm7+zigbee rf 芯片的方式实现移动终端。具体工作 主要分为 2 部分： (1) pc机无线网卡模拟实现： 主要包括选取、 掌握路由协议mmrp， 掌握tcp/ip 与 ieee 802.11 协议并通过 windows socket()编程做出 demo 程序，实现 mmrp 路由协议。在 57 个网络节点中实践了自组织运行和多跳传输等特性。 (2) armrf 模块的实现： 主要包括 arm7 微处理器和 cc2420 rf 模块的选用， 比较 bluetooth 协议、ieee 802.11 和 zigbee 协议，选用 zigbee 协议作为无线传 输控制协议。将 zigbee 协议代码移植到 arm 平台，并欲实现与应用层的连接。 现已初步实现 3 个节点的组网传输。 4. 论文架构论文架构 论文共分五章，结构如下： 第一章 绪论，介绍 ad hoc 网络的概念，发展历程和研究背景，阐述了路由 协议的重要性，并结合项目需求，提出本文的选题背景。 第二章 主要介绍了ad hoc网络路由协议的概况， 即ad hoc网络的技术特点、 应用、存在的问题以及分类，并对四种典型的路由协议 mmrp，dsdv，dsr， aodv 做简要的描述和性能评估。在此基础上选择了实验研究内容 mmrp 路由 协议。 第三章 在 pc 机上模拟实现 mmrp 协议的运行， 包括 mmrp 协议簇之间的 分工与合作，并对实验结果进行分析说明。 第四章 在协议实现的基础上，考虑协议在移动终端上的实现。选取 arm7 处理器以及支持 zigbee 协议的芯片，达到实现 ad hoc 移动节点的意愿。 第五章 总结本文的工作，并对下一步的工作进行了展望。 上海交通大学硕士学位论文 - - 5 - 第二章 ad hoc 网络路由协议分析与协议选择 1. ad hoc 网络的介绍网络的介绍 ad hoc 网络，是指由一组移动节点，不需要集中式的接入点或者现存的基 础设施，就可以聚集起来的协力通信的网络。网络的连接是动态变化的，并且移 动节点只能通过邻近节点的转发分组进行数据通信。 由于节点能在网络中自由移 动， 连接很容易中断和发生改变， 因为这种网络的链路本身就具有临时性。 ad hoc 网络最初主要应用在军事以及一些紧急的环境下， 因为它具有极大的灵活性和极 好的抗毁性等优越性。我们习惯把 ad hoc network 称为自组网。自组网技术提 出的最大目的： 实现网络终端在移动过程中适应网络拓扑结构的变化而不至于中 断通信。这样在一些由于没有可利用的设备或者某些因素限制下的特殊环境中， 可通过终端的自组网来完成用户之间的信息交流和协同工作， 从而弥补基础设施 (infrastructured)网络的缺陷，或者作为有线网络的无线延伸。 (1)ad hoc 网络特点网络特点14 ad hoc 网络是一种新型的无线网络。 与常用的蜂窝网络和无线局域网不同， 它采取的是分布式管理策略，不需要固定基站或控制中心，能动态适应网络拓扑 的变化。网络中各节点通过分层协议和分布式算法协调各自的行为，可快速、自 行组成一个独立的网络。每个节点都具有数据转发的能力，同时扮演着终端和路 由器的角色。由于节点自由移动，加入/离开网络，或者发生故障等造成的网络 拓扑结构发生变化， 不会影响整个网络的运行， 因而具有很强的健壮性和抗毁性。 与普通的移动网络和固定网络相比，具有以下特点： 1) 无中心：ad hoc 网络没有严格的控制中心。所有节点的地位平等，是一个对 等式网络。网络中没有绝对的控制中心。网络的布设或展开无需依赖于任何预设 的网络设施，结点可以随时加入或离开网络，任意结点的故障不会影响整个网络 的运行，与有中心网络相比，具有很强的抗毁性。无中心和自组织特点使得 ad hoc 网络可以实现快速自动组网。 2) 自组织：自组织是 ad hoc 网络的基本特征，节点必须检测其它节点以及它们 上海交通大学硕士学位论文 - - 6 - 可以提供的服务。节点通过分布式算法协调各自的行为，快速组网。由于网络动 态变化，自组织过程需要确保网络能够正常工作。 3) 多跳路由：由于结点发射功率的限制，结点的覆盖范围是有限的。当节点需 要与其覆盖范围之外的节点进行通信时，需要中间节点的多跳转发。与固定网络 的多跳不同，ad hoc 网络中的多跳路由是由普通的网络节点完成的，而不是由 专用的路由设备（如路由器）完成的。反过来，如果可以使用多跳路由，结点的 发射功率可以很低， 从而达到节省电能延长电池工作时间的目的。 如图 2-1 所示， 节点 b 在节点 a，c 发射范围之内，而 a，c 节点都不在彼此的辐射范围内，因 此节点 a，c 之间通信需要节点 b 转发。 4) 动态拓扑：ad hoc 网络是一个动态的网络。网络节点可以随时随地移动，也 可以随时开机和关机， 这些都会使网络的拓扑结构以不可预测的方式随机快速地 发生变化。这些特点使得 ad hoc 网络在体系结构、网络组织、协议设计等方 面都与普通的蜂窝移动通信网络和固定通信网络有着显著的区别。 5)无线传输：ad hoc 网络采用无线传输技术，由于无线信道本身的特性，它所 能提供的网络带宽相对于有线信道要低得多，并且无线信道的质量较差。考虑到 竞争共享无线信道产生的冲突、信号衰减、噪声和信道之间干扰等因素，移动终 端获得的实际带宽远远小于理论上的最大带宽，并且会随时间动态变化。 6)有限的安全： 由于无线传输是面向开放空间的，所以它易受到安全攻击，比 如窃听、伪造、拒绝服务，如何提高 ad hoc 网络的安全性正成为人们关心的问 题。 a b c 图 2-1 多跳技术 fig. 2-1 multi-hop 上海交通大学硕士学位论文 - - 7 - (2)ad hoc 网络的应用领域网络的应用领域 移动 ad hoc 网络是一种具有高度动态拓扑结构、节点任意移动的自组织网 络，具有较高的灵活性和良好的适应能力，受到军方人士的青睐。ad hoc 网络 适合被用于无法或不便预先铺设网络设施的场合、需要快速自动组网的场合等。 针对 ad hoc 网络的研究是因军事应用而发起的，因此军事应用仍是 ad hoc 网络的主要应用领域。随着技术的进步和社会的发展，特别是人们对个人通信日 益增长的需求，使得移动 ad hoc 网络的应用范围正逐步扩大。其应用场合主要 有以下几类： 1) 军事应用：军事应用是 ad hoc 网络技术的主要应用领域。因其特有的无需 架设网络设施、可快速展开、抗毁性强等特点，成为战场通信的首选技术，它可 以支持野外联络、独立战斗群和舰队战斗群通信、无人侦察与情报传输等。具有 代表性的例子是，ad hoc 网络技术已成为美军战术互联网的核心技术。 2) 传感器网络：传感器网络是 ad hoc 网络技术的另一大应用领域。对于很多 应用场合来说探测网络只能使用无线通信技术。 由于探测网络往往由各式各样的 传感器构成，而考虑到体积和节能等因素，传感器的发射功率不可能很大，使用 ad hoc 网络实现多跳通信是是解决探测节点传输距离受限的有效方法。分散在 各处的传感器组成 ad hoc 网络，可以实现传感器之间和与控制中心之间的通 信。 3) 紧急和临时场合：这是 ad hoc 网络潜在的应用场合。在发生地震、水灾、强 热带风暴或遭受其他灾难打击后，固定的通信网络设施(如蜂窝移动通信网络的 基站等网络设施、卫星通信地球站等)可能被全部摧毁或无法正常工作，这时就 需要 ad hoc 网络这种不依赖任何固定网络设施又能快速布设的自组织网络技 术。类似地，处于边远或偏僻野外地区时，同样无法依赖固定或预设的网络设施 进行通信。ad hoc 网络技术的独立组网能力和自组织特点，成为这些场合通信 的最佳选择。 4) 个人通信：个人局域网(personal area network)是 ad hoc 网络技术的另一应 用领域，可用于实现 pda、手机、手提电脑等个人电子通信设备之间的通信。 samsung 公司已经开发出具有 ad hoc 网络通信功能的智能手机。 5) 与移动通信系统的结合：ad hoc 网络与蜂窝移动通信系统相结合，利用移动 上海交通大学硕士学位论文 - - 8 - 台的多跳转发能力扩大蜂窝移动通信系统的覆盖范围。在实际应用中，ad hoc 网络除单独组网实现局部的通信外， 还可以作为末端子网通过接入点接入其他的 固定或移动通信网络，与 ad hoc 网络以外的主机进行通信。 (3)面临的挑战面临的挑战 路由协议是 ad hoc 网络的重要组成部分。要实现无线多跳路由，必须要有 专用路由协议的支持。源头性的创新性研究主要集中在 2001 年以前，后续的成 果多为这些协议的改进。ad hoc 路由面临的主要挑战是：传统的保存在结点的 分布式路由数据库如何适应网络拓扑的动态变化。 新协议一般以广播或组播方式 建立网络路由，因此核心目标是如何减少广播风暴。这些协议的算法在信道共享 的前提下，都有相当大的组网开销。而且 manet 中各节点处于平等地位，除 了自身的数据通信工作，还要承担网络组织、路由计算和分组转发的任务，其负 担沉重；特别是当参与动态路由的节点数量较多时，路由开销大大增加，网络性 能下降严重。 目前 ad hoc 网络尚未达到完全实用阶段，大部分工作仍处在仿真和实验阶 段，仿真规模在数百至数千节点，实验规模在几十个节点左右。 2. 网络路由协议的设计网络路由协议的设计 (1)路由协议的设计要求路由协议的设计要求 ad hoc 网络中，移动终端能够以任意速度和移动模式移动，并且可以随时 关闭电台，加上无线发送装置的天线类型多种多样、发送功率的变化、无线信道 间的互相干扰、地形和天气等综合因素的影响，移动终端间通过无线信道形成的 网络拓扑随时可能发生变化，而且变化的方式和速度都难以预测。在网络拓扑图 中，这些变化主要体现在结点和链路的数量及分布的变化，而相对于传统有线网 络，网络的拓扑结构较为稳定。 传统的距离向量和链路状态路由协议并不适用于拓扑结构高度动态变化的 ad hoc 网络。理想的 ad hoc 网络的路由协议应该具有以下性能：分布式运行； 自组织；维护多跳路由；考虑安全性；高效地利用电池能量。 上海交通大学硕士学位论文 - - 9 - (2) 网络常识网络常识 为更好理解 manet 网络的路由规则， 熟悉传统路由算法常识， 如长度矢量， 链路状态，泛洪以及源节点路由等，是非常有帮助的，这是因为 manet 的路由 协议与这些算法有相同的概念。 长度矢量长度矢量1219 长度矢量技术是基于每个节点都保存有一张到网络所有节点最优路径的路 由表。在每一个特定的时间间隔内，网络消息被发送到所有邻居节点。然后这些 节点比较自有路由表和接收的数据包， 如果接收的路由表节点间的长度小于相应 存储的路由表节点长度，则节点用接收的路由表更新自己的数据库。如果接收数 据的源节点发送更新鲜的路由表信息时， 节点更新路由表而不管路由表信息的值 是否大于存储量。这个过程一直进行着，由此每个节点都能用最短路径更新自己 的路由表。 泛洪泛洪 通过使用泛洪技术，每个数据包被发送到网络的各个节点。每个接受该数据 报的节点把它广播到所有的邻居节点，除了那些已经接受过它的。同时，邻居节 点也做相同的事情。为了避免重复发送同一个数据包两次，每个数据包头都包含 有源节点地址和序列号sequence number两个信息量，通过使用这两个量，每 个节点跟踪自己已经发送出去的数据报。 链路状态链路状态1219 链路状态路由与长度矢量路由运行情况类似。他们的不同之处在于路由表的 更新方式。链路状态生成一张路由表，通过这个信息表，每个节点能了解这个网 络的所有节点信息。 每个节点可以使用最短路径算法来决定哪条链路是通往目的 节点的最短路径以及传输的下一跳节点。 如果网络有变化，比如节点的加入或者离开，数据报会被传输以提示网络的 这个变化。这个数据报以泛洪的方式在网络中传播，所有接受这个数据报的节点 相应地更新自己的路由表。与长度矢量方式比较，链路状态方式更可靠，更容易 检测到错误和占用带宽。 这是因为链路状态使用事件触发而不是像长度矢量那样 周期性更新。 上海交通大学硕士学位论文 - - 10 - 源节点路由源节点路由 存在有两种源节点路由：严格源节点路由和松散源节点路由。严格源节点路 由在发送节点需要确定确切路由路径的时候才会用到， 路由信息被放置在数据报 头中。这个技术很少用到。用的更普遍的是松散源节点路由，节点只确定一部分 数据需要传输经过的节点。源节点路由需要每个节点了解整个网络拓扑结构。 (3) 路由协议的分类路由协议的分类 分类一：主动式分类一：主动式(proactive) vs 反应式反应式 (reactive) 121314 在主动式路由协议中，每个节点都试图维护到所有已知目的节点的最新路由 表。当网络拓扑结构出现变化时，网络路由消息得到即时响应。节点之间周期地 或在网络拓扑发生变化时交换路由信息， 这样当路由请求发生时能立即提供路由 通路。 在反应式路由协议中， 每个主机“按需”计算到特定目的节点的路由路径。 路径维护处理程序保存这个路径直到目的节点不再存在。 反应式路由一般包括路 由发现和路由维护两个过程。 主动式(proactive)： 优点： 获取路由路径的延迟时间短， 节点能立即判断目的节点的可达性. 缺点： 产生更多的控制流量； 消耗很多带宽； 产生网络拥挤。 反应式 (reactive)： 优点：只需要较低的带宽去保持路由表； 能量消耗低； 更高效的路由存储，只需要较小的存储空间。 缺点：路由发现过程的费用比较昂贵，路径寻找过程需要很长的网络延 迟，同时当节点数量很大的时候，反应式路由协议面临网络容量的问题。 主动式路由算法的核心是不断地评估当前到达网络中其他节点的路由，这样 当需要向某个目的节点路由分组时节点已经存有相关的路由信息。典型的 manet 主动式路由算法有 dsdv (destination sequenced distance vector)， 上海交通大学硕士学位论文 - - 11 - mmrp(mobile mesh routing protocol)等。 主动式路由协议的目标在于维持到网络中所有节点的最新的路由信息。每个 节点需要维护一张或多张表格，这些表格记录着到达网络中其它节点的路由信 息。主动式路由的路由发现策略与传统路由协议类似，它依赖于周期性广播路由 分组来及时地维护掌握整个网络拓扑结构的路由表。 同时当检测到网络拓扑结构 发生变化时， 节点在网络中发送更新消息； 收到更新消息的节点更新自己的表格， 以维护一致的、及时的、准确的路由信息，所以路由表可以准确地反映网络的拓 扑结构。当需要发送报文时，通过路由表中的信息、就可以找到通往目标节点的 路径。正是因为所有的路由过程都是在路由表的指导下完成的，所以又被称为表 驱动(table-driven)路由协议。 主动式路由在并不需要路由的情况下主动寻找到网络节点的路由，所以路由 的优点就是当节点需要发送某个数据分组时，只要路由存在，通过查找路由表， 就能找到现成的路径，从而发送分组的延时很短。当然其缺点也很明显，任何节 点的相对位置的变化引起的网络拓扑结构的变化都必须通知其它所有的节点， 路 由协议需花费很高代价(如带宽、电源、cpu 资源等)，使路由表能够跟上当前网 络拓扑结构的变化。 而往往花较大代价得到的网络边缘信息对大多数节点来说并 没有实际的价值。特别还有一点，主动式算法需要时间使所有节点保存的拓扑信 息收敛到一个稳定而正确的状态，当网络节点移动速度较快时，路由协议将始终 处于不收敛的状态。 反应式路由算法则不同，只有当需要向某个目的节点路由分组时，节点才会 发起一个路由发现过程来寻找相关的路由信息。典型的 manet 反应式路由算 法有 aodv (ad-hoc on-demand distance vector routing)，dsr(dynamic source routing)等。反应式路由算法由于不需要全网的同步，所以协议的开销小于主动 式算法。但是开销的降低是以路由的延迟加大为代价的。 按需路由认为在动态变化的自组网中，没有必要去维护去往其他所有节点的 路由。 它仅在没有去往目的节点路由存在的时候才 “按需” 进行路由发现。 因此， 拓扑结构和路由表内容是按需建立的，它可能仅仅是整个拓扑结构信息的一部 分。它的优点是不需要周期性的路由信息广播，节省了网络资源；缺点是发送数 据分组时，如果没有去往目的节点的路由，数据分组需要等待因路由发现而引起 上海交通大学硕士学位论文 - - 12 - 的延时。 反应式/按需路由协议通常有路由发现和维护两个过程组成。 当源节点发现没 有去往目的节点的路由时，触发路由发现过程。这个过程类似于有线网络中建立 电路连接的协商过程。 当拓扑结构发生变化时， 通过路由维护过程删除失效路由， 重新发起路由请求过程。 路由维护通常依靠底层提供的链路失效检测机制进行触 发。 按需路由协议中，建议使用路由缓存机制提高网络性能，允许中间节点响应 路由请求以加速路由发现进程11。 同时当网络规模变大时，路由分组的目的地址的不确定性增大，需要路由发 现的分组就会增多，同时每次路由发现过程的开销增大，所以总体协议的开销会 显著上升。 由以上的分析可知，无论主动式路由和反应式路由对较大规模的自组织网络 的支持都不是很好，随着网络规模的扩大，路由协议开销增大，算法收敛困难， 路由延迟增大等问题都会出现，网络性能严重下降。 分类二：链路状态分类二：链路状态(link state) vs 长度矢量长度矢量(distance vector)15 链路状态路由特点： (1)测量到邻居节点的距离 (2) 与网络中所有节点交换网 络信息。 链路状态路由基于整个网络的拓扑结构， 产生路由表， 通过这个信息表， 每个节点能了解这个网络的所有节点信息。 每个节点可以使用最短路径算法来决 定通往目的节点的最短路径及下一跳节点地址。 长度矢量路由的特点：(1) 计算到网络所有节点的距离 (2) 只与邻居节点交 互网络信息。 长度矢量路由基于每个节点都存有到网络所有节点的最优路径的路 由表。网络消息被发送到所有邻居节点，然后这些节点比较自有路有表和接收的 数据包，更新自己的数据库，每个节点能用最短路径更新自己的路由表。 分类三：水平式分类三：水平式(flat) vs 层级式层级式(hierarchical) 水平式路由：如图 2-2 所示。 优点：鲁棒性和存活性好，是因为(1) 没有单点失败影响 (no single point of failure) 和(2) 网络存在多条路由； 存在最优路径； 更好的适应性； 上海交通大学硕士学位论文 - - 13 - 更好的负载均衡性； 所有节点都是同类设备； 没有单点失败影响，也就是单节点消失不会对整个网络造成影响，这个要求 对于数据的传输至关重要。这也就是说假如有节点消失，余下的网络可以照常运 行良好。而在层级式路由中却是另外一回事，如果一个网络簇头消失，网络的一 部分区域将不能从另外一个区域发送和接收信息。 同时也要提一下：水平式网络的网络扩容性不好，当网络变大时，路由负载 会急剧增加。因此有人提出采用虚主干(virtual backbone)技术可以大幅度地减少 无线网络的路由开销14。 层级式路由：如图 2-3 所示。 优点：更简单的移动管理程序； 可管理性增强。 3. 典型网络协议的特性比较典型网络协议的特性比较1114151617 这儿， 我们挑选列举4种典型的ad hoc网络路由协议， 分别是dsdv， mmrp， dsr 和 aodv。 其中，前两种协议是主动式/表驱动路由协议，后两种是反应式 /按需驱动路由协议，这 4 种协议代表了现存在的绝对多数协议的特点，具有普 遍意义。 (1) 目的节点排序距离矢量路由目的节点排序距离矢量路由(dsdv) 目 的 节 点 排 序 距 离 矢 量 路 由 协 议dsdv(destination-sequenced distance-vector routing protocol)是一种基于传统 bellman-ford 路由选择算法改 进得到的路由协议，也是最先出现的 ad hoc 网络协议。它的工作原理与传统网 络的 dvr(distance-vector routing)基本相同，本质区别在于引进了序列号 (sequence number)机制，以防止路由环路(loop)的产生，加快路由收敛的速度， 图 2-2 水平式 fig. 2-2 flat routing 图 2-3 层级式 fig. 2-4 hierarchical routing 上海交通大学硕士学位论文 - - 14 - 并减少控制报文的负载。 dsdv 是一种主动式、 逐跳(hop-to-hop)距离矢量路由协议， 需要每个节点进 行周期性地广播来进行路由更新。网络中每个节点都维护着一张路由表，其中记 录着网络中所有的可到达的目的节点、 到这些节点的纪跳数以及目的节点的序列 号。一方面，为了维持路由表的一致性，网络节点需要周期性广播路由表来维护 路由表的即时性；另一方面，当网络中出现重大改变时将也会广播路由表，以使 重大变化信息能够得到最快传播。所以，dsdv 的更新是基于时间驱动和事件驱 动两者同时的。路由表的更新有两种途径：完全存储更新模式(full dump)和增量 更新模式(incremental)。完全存储更新模式发布的是整个路由表，需要多个网络 协议数据单元(pdu)的支持。而增量更新模式，传送的是那些从最近一次完全存 储更新之后改变的信息。当网络相对稳定时，增量更新比较多；当网络拓扑结构 变化较快时，则完全存储更新就会多于增量更新。 dsdv 采用序列号机制来区分路由信息的新旧程度，防止可能出现的路由环 路。它用自有序列号来标识路由表中的路由，该序列号是单调增加的。在路由更 新分组中包含了以下内容：目的节点的地址，到达目的节点的跳数，目的节点的 信息的序列号， 以及此次广播的本节点的序列号。 通过交换路由表中的路由信息， 如果到达同一目的节点的路由 r的序列号大于原路由 r 的序列号，或者两者序 列号相同但 r的距离小于 r 的距离时，就用 r取代 r。当节点 s 发现到节点 d 的链路中断时，就广播一个到节点 d 的路由，且将序列号加 1，这样接收到该信 息的节点对路由表作相应调整，直到收到更高序列号的路由信息。 由于 dsdv 依靠周期性的广播机制进行路由，所以在一条有效路由的建立是 需要收敛时间的。如果在静止的网络中，该收敛时间可以忽略不计。然而在拓扑 变化频繁的 ad hoc 网络中，收敛时间会明显增加，从而导致在路由建立之前会 丢失一部分报文。另外，当网络规模增大时，周期性的广播会导致网络负载的急 剧增加。 (2) 移动网格路由协议移动网格路由协议(mmrp)1016 移动网格路由协议是一种健壮的，可容易扩展的，有效的移动 ad hoc 网络 路由协议。mmrp 由一组相关的移动网格协议组成的协议簇，包括移动网格链 上海交通大学硕士学位论文 - - 15 - 路发现协议(mmldp)和移动网格边界发现协议(mmbdp)。它们组成了一个可靠 的，延展性强的路由机制。 mmrp 协议是基于链路状态 (link state)信息的主动式路由协议。网络节点 接口(interface)周期性地广播 lsp 数据报，接收到 lsp 的节点在数据报到达后的 指定时间内中继。由此，网络的每个节点都保存有整个网络的拓扑信息。通过节 点的拓扑数据库，使用 djykstra 链路状态算法，每个节点都能计算出到 ad hoc 网络各个节点的最短传播路径。移动终端在发送数据时，通过查询本地路由表信 息，找出到达目标节点的最短传播路径并沿该路径发送，最终到达目的节点。 同时，协议也针对 ad hoc 网络的特点对协议作了很多改进，比如使用鱼眼 技术降低路由风暴。 (3) 动态源路由动态源路由(dsr) 动态源路由 dsr(dynamic source routing)是基于源路由概念的按需路由协 议。dsr 使用路由缓存(route cache)来记录源节点寻找到的到网络节点的路由， 并根据获取到的新的路由来更新路由缓存器。 dsr 由两个主要的机制组成：路由发现(route discovery)和路由维护(route maintenance)，二者协同工作使得节点能够发现和维护到达 ad hoc 网络中任意目 的节点的路由。当源节点需要传送数据给某个目的节点时，它首先查找其路由缓 存来确定是否存在现有路由。如果有，就使用此条路径传递数据；如果没有，就 通过广播路由请求包(route request packet)启用路由发现机制，在请求数据包中包 含目的地址，源地址和 id 号。收到请求包的节点会检查自己的路由缓存是否存 在到请求包中的目的节点的路径，如果有，就将此段路径和请求包中记录的路径 写入路由应答并传给源节点；如果没有，就将自己的地址也记录到请求包中并传 递给下一节点。节点只在以下两种情况下转发请求：(1)没有收到过此包，(2)自 己的地址没有记录在路由请求中。当目的节点或是中间节点给出路由应答时，则 会根据路由应答中的路由记录(route record)来将路径传给源节点，否则启用新 的路由请求来捎带(piggyback)源节点到目的节点的路径。 路由维护是通过使用路由错误包和确认机制来完成的。 在无线网络中，两个节点之间的链接也许并不能在两个方向上都工作得同样 上海交通大学硕士学位论文 - - 16 - 好，这是由于不同的天线或传播模式或者是干扰造成的。dsr 允许在需要时使 用这样的单向链接， 这改善了整体性能和系统中网络的连接性， 而不同于 aodv 只支持双向链路。 dsr 的优点是中间节点不用维护去往所有节点的路由信息，而且可以避免 出现路由环路。 它的缺点是每个数据分组都携带