（计算机软件与理论专业论文）ad+hoc网络中aodvi协议的研究与实现.pdf

， jo yl _ 。爨奠。o；： o， 、1一1 ， 艮l1， 、_广耄蠢。；飞1-、 ； ， ， 融 b & f at h e s i sf o rt h ed e g r e eo fm a s t e ri nc o m p u t e r s o a w a 陀a n d t h e o r y r e s e a r c ha n d i m p l e m e n t a t i o no f a o d v - ip r o t o c o li n a dh o cn e t w o r k b yl i uz h a o h u i s u p e r v i s o r ：a s s o c i a t ep r o f e s s o rx i al i n o r t h e a s t e r nu n i v e r s i t y m a y 2 0 0 8 l_i，l蕾f，0h耵_ppf卜 一 独创性声明 本人声明，所呈交的学位论文是在导师的指导下完成的。论文中取得 的研究成果除加以标注和致谢的地方外，不包含其他人己经发表或撰写过 的研究成果，也不包括本人为获得其他学位而使用过的材料。与我一同工 作的同志对本研究所做的任何贡献均己在论文中作了明确的说明并表示谢 皇； 恧。 学位论文作者签名： 1 彝竹 日 期：哪- b 乃。 学位论文版权使用授权书 本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论 文的规定：即学校有权保留并向国家有关部门或机构送交论文的复印件和 磁盘，允许论文被查阅和借阅。本人同意东北大学可以将学位论文的全部 或部分内容编入有关数据库进行检索、交流。 作者和导师同意网上交流的时间为作者获得学位后： p ，半“一年口一年半口两年口 l 学位论文作者签名司纳坪 签字日期：炒子、6 、弓。l 导师签名： 签字日期： 篓7 侈加参6 弓侈 1 一 一硝l 摘要 中a o d v - i 协议的研究与实现 摘要 a dh o e 网络是一个多跳的、自组织、无中心的网络，它由一组带有无线收发装置 的移动终端组成的，无需任何固定的基础设施便能实现网络的快速部署，因此非常适合 于军事、救灾、个人通信、无线传感器网络等领域。由于a dh o c 网络拓扑频繁变化， 传统的因特网路由协议不能满足其需求，因而路由协议成为a dh o c 网络的研究重点。 本文对a dh o e 按需路由协议( a o d v ) 进行了深入的研究，探讨了其路由发现过程中 存在的问题：路由请求( r r e q ) 消息的处理缺乏拥塞控制，路由应答( r r e p ) 消息缺乏保 障机制。本文针对这两个问题提出一个a o d v 改进协议a o d v - i 。a o d v - i 协议对r r e q 消息的处理添加了拥塞控制，在建立新的路由时能够自动选择网络中相对空闲的节点； 对r r e p 消息的转发过程中添加了路由修复机制，使得在路由断裂情况下该r r e p 消息 仍能够返回到路由请求源节点，从而避免不必要的新一轮路由请求。通过对a o d v 协 议的改进，能够减少网络丢包率和端到端延迟并提高网络资源的利用率。 本文介绍了a dh o e 网络典型的路由协议及其优缺点；深入研究了a o d v 路由协议， 探讨了其路由发现过程中存在的两个问题，并针对这两点问题提出了改进方案；修改 n s 代码，实现改进后协议的功能。最后，分析仿真结果及实验数据，验证所提出方案 的性能。 关键词：a dh o e ；a o d v ；按需路由；a o d v i i i 论文 a n di m p l e m e n t a t i o no fa o d v - ip r o t o c o li na dh o c n e t w o r k a b s t r a c t a dh o cn e t w o r ki sam u l t i h o p ，a u t o n o m o u s ，a c e n t r i cs y s t e m ，w h i c hc o n s i s t so fm o b i l e t e r m i n a l 、析t hw i r e l e s st r a n s c e i v e r , a n di tc a nb ed e p l o y e dr a p i d l yw i t h o u tr e l y i n go na n y p r e e s t a b l i s h e di n f r a s t r u c t u r e ，s oi t i sq u i t es u i t a b l et os o m es p e c i a lf i e l ds u c ha sb a t t l e f i e l d ， d i s a s t e rr e l i e f , p e r s o n a lc o m m u n i c a t i o na n dw i r e l e s ss e n s o rn e t w o r ke r e t h et r a d i t i o n a l i n t e m e tr o u t i n gp r o t o c o l sc a n tm e e tt h ed e m a n do ff r e q u e n tt o p o l o g yc h a n g e si na dh o e n e t w o r k ，s ot h er o u t i n gp r o t o c o l sb e c o m ea l li m p o r t a n tr e s e a r c hi s s u e t h i sp a p e rc o n d u c t sad e e pr e s e a r c ho na o d vp r o t o c o la n dd i s c u s s e st w op r o b l e m si n i t sr o u t ed i s c o v e r yp r o c e s s ：l a c k i n gc o n g e s t i o nc o n t r o lo nr r e qm e s s a g es e n d i n gb yt h e r e q u e s t i n gn o d ea n dn og u a r a n t e em e c h a n i s mo fr r e pm e s s a g er e t u r n i n gt ot h er e q u e s t i n g n o d e t h i sp a p e rp r o p o s e sa l li m p r o v e m e n tp r o t o c o la o d v - ib a s e do nt h ei n v e s t i g a t i o n a b o v e ，i nw h i c hc o n g e s t i o nc o n t r o li nr r e qm e s s a g et r a n s m i t t i n gp r o c e s si sa d o p t e da n d r o u t er e p a i rm e c h a n i s mi nr r e pm e s s a g ef o r w a r d i n gp r o c e s si su t i l i z e d t h ea o d v - ic a l l c h o o s et h er e l a t i v e l yi d l en o d ea u t o m a t i c a l l yw h e ne s t a b l i s h i n gan e wr o u t e ，a n da l s om a k e s u r et h a tt h er r e pm e s s a g er e t u l t t st ot h er e q u e s t i n gn o d eu n d e rt h ec i r c u m s t a n c eo fr o u t e f a u l t ，t h u sa v o i d i n ga n o t h e ru n n e c e s s a r yr o u t er e q u e s t w i t ht h e s ei m p r o v e m e n t st oa o d v p r o t o c o l ，i ti sp o s s i b l et or e d u c et h er a t eo fp a c k e tl o s sa sw e l l 嬲e n d - t o - e n dd e l a ya n d i n c r e a s en e t w o r kr e s o u r c eu t i l i z a t i o n t h i sp a p e ri n t r o d u c e ss e v e r a l t y p i c a lr o u t i n gp r o t o c o l s ，a n da n a l y z e st h e i ra d v a n t a g e s a n dd i s a d v a n t a g e s t h r o u g ht h ed e e pr e s e a r c ho nt h ea o d vp r o t o c o l ，t w op r o b l e m si nt h e r o u t i n gd i s c o v e r yp r o c e s sa r ed i s c u s s e da n di m p r o v e ds c h e m e s a l ep u tf o r w a r d t h ei m p r o v e d s c h e m e sa r ei m p l e m e n t e db ym o d i f y i n gt h ec o d ei nn s f i n a l l y , t h er e s u l to fe m u l a t i o ni s a n a l y z e dt ov e r i f yt h ef e a s i b i l i t yo ft h es c h e m e k e y w o r d s ：a dh o e ；a o d v , o nd e m a n dr o u t i n g ；a o d v - i i i i 哎iltl， 东北大学硕士学位论文目录 目录 独创性声明。i 摘要i i a b s t r a c t i i i 第1 章绪论：1 1 1 研究背景1 1 2 国内外研究现状。1 1 3 本文的主要工作3 第2 章a dh o c 路由协议5 2 1a dh o c 路由协议设计要求5 2 2a dh o c 路由协议：。6 2 2 1 表驱动路由协议6 2 2 2 按需驱动路由协议1 0 2 3d 、结1 4 第3 章a o d v 协议的研究与改进1 5 3 1a o d v 协议1 5 3 1 1 路由发现一1 6 3 1 2 路由维护2 1 3 2a o d v - i 仂议2 4 3 2 1 针对r r e q 消息处理的改进2 4 3 2 2 针对r r e p 消息处理的改进2 7 3 3 小结3 2 第4 章a o d v 协议及其改进的实现3 3 4 1n s 网络仿真平台3 3 4 1 1n s 简介3 3 4 1 2n s 的类体系结构3 4 4 1 3n s 的主要组件3 5 4 1 4 使用n s 进行网络仿真的方法和步骤3 5 4 1 5n s 的无线模块一3 7 4 2a o d v 及a o d v - i 的实现3 7 东北大学硕士学位论文目录 4 2 1 消息格式3 8 4 2 2 数据包接收4 1 4 2 3 数据包转发4 5 4 2 4 数据包发送4 6 4 2 5 定时器4 6 4 3 小结4 8 第5 章仿真及结果分析。4 9 5 1 仿真场景介绍。4 9 5 2 不同的c b r 流数目4 9 5 3 不同的c b r 流发送速率5 1 5 4 不同的节点最大移动速率5 2 5 5 不同的节点间歇停留时间5 2 5 6d 、结。5 3 第6 章结论5 5 参考文献5 7 至j 【谢6 1 v 一：；li， 一f*妇矗f 东北大学硕士学位论文第1 章绪论 第l 章绪论 1 1 研究背景 随着科技的不断进步，人们对无线通信技术的要求也与日俱增，在一些特殊环境或 紧急情况下，如发生自然灾害，野外科学考察及探险，激烈作战的战场等不可能有预先 安置好的固定接入设备的环境下，迫切需要一个能够动态的、能够快速部署的、不依赖 或很少依赖现有的有线网络设备，并且能够临时快速自动组网的移动通讯技术，这也就 形成了另一类无线通信网络技术即a dh o c 网络技术【1 5 】。 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 路由协议 中，a o d v 6 】协议是最早通过i e t f 批准成为r f c 文档的移动自组网按需控制路由协议， 它具有理想的移动自组网路由协议所应具有的大部分性能特点，如：通过使用序列号来 避免出现路由环路；支持中间节点应答，能使源节点快速获得路由；消息头部不需携带 路径，提高了带宽利用率；节点只存储需要的路由，减少了内存需求；能快速响应活跃 路径上的断链；具有良好的可扩展性等。因此a o d v 协议很可能在未来移动a dh o c 网 络的应用中占据重要地位。 1 2 国内外研究现状 目前对a dh o c 网络的研究工作主要集中在美国。1 9 9 7 年，i n t e r n e t 工程任务组( m t v ) 成立了一个专门研究m a n e t ( m o b i l ea dh o cn e t w o r k ，m a n e t ) 5 in ：i ：作组，负责a d 东北大学硕士学位论文第1 章绪论 h o c 路由协议的研究和标准化工作，但该项工作非常艰巨，首先要制定路由协议的评价 标准，然后对每一个路由协议进行基于模拟或试验平台的分析测试，最后找出最优路由 协议。另外一些研究方面较为活跃的研究机构和学术会议也对m a n e t 的发展起了推动 作用。 a dh o e 路由面临的主要挑战是：传统的保存在结点中的分布式路由数据库如何适 应网络拓扑的动态变化。新协议一般以广播或组播方式建立网络路由，核心是减少广播 风暴。目前，一般普遍得到认可的代表性成果有a o d v 6 1 、o l s r t 7 】、t b r p f 8 、d s d v l 9 1 、 w r p 1 0 1 、d s r 1 1 1 、t o r a t l 刁和z r p 1 3 】等。源头性的创新性研究主要集中在2 0 0 1 年以前， 后续的成果多为这些协议的改进，目前，路由协议的研究仍然是a dh o c 网络成果最集 中的部分。不过，这些协议仍有这样或那样的缺陷，仍不能满足广泛应用的要求。 目前，国际上在移动a dh o c 网络方面研究较为活跃的几个研究机构有：加州大学 洛杉矶分校m a r i og e r l a 教授所领导的“无线自适应移动性实验室 ( w i r e l e s sa d a p t i v e m o b i l i t yl a b ) 。研究方向包括a dh o c 网络路由协议、多播协议、多跳网络q o s 、m a c 协议、功率控制、蓝牙网络等。康奈尔大学z y g m u n tj h a s s 教授所领导的“无线网络实 验室”( w i r e l e s sn e t w o r k sl a b o r a t o r y ) 。研究方向包括a dh o e 网络重构、m a c 协议、路 由协议、网络安全等。马里兰大学s a t i s hk t r i p a t h i 教授所领导的“移动计算与多媒体 实验室”( t h em o b i l ec o m p u t i n ga n dm u l t i m e d i al a b o r a t o r y ) ，研究方向包括j i a y s t a r 网络 路由协议、q o s 等。加州大学圣巴巴拉分校e l i z a b e t hm b e l d i n g r o y e r 教授所领导的“移 动性管理和联网实验室 ( t h em o b i l i t ym a n a g e m e n ta n dn e t w o r k i n g ) 。研究方向包括 j i a y s t a r 网络路由协议、多播协议、地址重构、安全性、q o s 、可伸缩性和适应性等。 其他比较活跃的机构还包括美国陆军、海军和一些企业的研究机构。国内学者所发 表的a dh o e 网络的研究成果较少。从2 0 0 1 年起，开始有少量成果发表，主要成果基本 上集中在路由协议的一些改进，少量成果涉及m a c 协议的研究。可以说国内在该研究 领域基本上是刚刚起步。 结合国内外研究现状，移动a dh o e 网络的成果主要在以下几个方面： ( 1 ) 无线信道资源问题：即媒体接入控n ( m a c ) 协议。m a c 协议的好坏直接影响到 网络吞吐量、时延等性能指标。在m a c 协议设计首先要解决隐藏终端和暴露终端问题， 其次是信道资源的公平接入问题，以保证网络中各种业务的服务质量、降低功耗等。目 前比较成熟的协议有m a c a 1 4 1 、f a m a t l 5 】等，这些协议都是基于随机竞争接入机制的， 节点在需要发起业务时以竞争方式获得信道的使用权，在无业务时处于侦听状态，这种 方式对突发数据业务能提供较好的支持，但对实时业务的支持较为困难。 ( 2 ) 路由技术问题：从功能上讲，路由协议是通信网络中的一套将业务数据从源节 2 一；。0t， 第1 章绪论 拓扑结构的动态变化、无线传播带宽有限、移动节点能力有限、分布式控制方式、安全 性差等问题，使得路由协议的设计相对复杂，目前路由协议的研究仍然是a dh o c 网络 研究成果最集中的部分，不过这些协议离实用性还有一定的差距。本文的主要内容也是 路由技术。 ( 3 ) 自组网安全性问题：由于自组网自身的特殊性，使其容易受到假冒、窃听、篡 改等攻击；移动节点在漫游中可能被俘获，使自组网还会面临来自内部节点的攻击，节点 的信任关系也随之变化。传统的安全机制不再适用于自组网。目前的研究主要从安全体 系结构、安全模型、安全路由、认证协议、密钥管理、和入侵检测等方面进行分析，已 经提出的一些解决方案包括：安全路由协议s r p t l 6 1 、s a o d v 1 7 , i s 安全路由协议等等， 但总体还不是很成熟，存在很多困难和挑战。 ( 4 ) 自组网与蜂窝移动通信系统互联：利用自组网的特点可以有效解决蜂窝系统的 一些难点问题。首先，可以弥补蜂窝系统中存在的覆盖缺陷；其次，自组网的动态中继 转发功能可以有效的调整热点区域的流量，实现流量的动态分配，提高服务能力和质量； 第三，在引入自组网之后，在蜂窝系统中引入了一种新的通信方式“局域网”方式。 目前，国内外己经就这方面的问题展开了一些研究，主要包括：o d m a 1 9 1 、s o p r a n o 2 0 等。该方向己经成为移动通信领域的热点问题之一。 ( 5 ) 自组网与传感器网络：传感器网由具有感知能力、计算能力、和通信能力的大 量微型传感器节点组成，能够处理收集到的探测数据，并以无线传输方式发送到基地台。 从通信角度而言，它们都采用无固定基础设施的多跳、分布式控制的无线通信方式、每 个节点都有转发能力。但是自组网的技术还不能直接应用到传感器网络中去，国内的研 究还刚刚起步，相信不久的将来会有巨大的应用前景。 ( 6 ) 蓝牙a dh o c 网络与超宽带a dh o c 网络：这些网络都是基于移动a dh o c 网络 刚刚兴起的网络，利用蓝牙和超宽带技术可以很好的解决自组网的一些问题，但同时也 带来了一些新的问题，需要去解决。 1 3 本文的主要工作 本文对a dh o c 网络按需路由协议a o d v 进行了深入的研究，探讨a o d v 协议路 由发现过程存在的两个问题：对路由请求( 也q ) 消息的处理缺乏拥塞控制，即建立新 - 3 - 东北大学硕士学位论文笫1 章绪论 路由时，不能自动避开繁忙的节点，结果是网络中繁忙的节点变得更繁忙，造成网络性 能下降；路由应答( r r e p ) 消息缺乏保障机制，即r r e p 消息由于返回路由断裂，不能成 功返回到请求的源节点而简单的丢弃，这使得路由请求过程中传播请求消息所做的努力 将赴之东流，并且引发新一轮路由请求，其广播范围更宽。本文针对这两个问题提出了 一个a o d v 的改进协议a o d v - i 。a o d v - i 协议对r r e q 消息的处理添加了拥塞控制， 在建立新的路由时能够自动选择网络中相对空闲的节点；对r r e p 消息的转发过程中添 加了路由修复机制，使得在路由断裂情况下该r r e p 消息仍能够返回到路由请求源节点， 从而避免不必要的新一轮路由请求。通过对a o d v 协议的改进，能够减少网络丢包率 和端到端延迟并提高网络资源的利用率。最后通过几组仿真实验，对比a o d v - i 协议和 a o d v 协议的性能。 论文组织结构如下： 第二章首先介绍了a dh o e 网络路由协议的设计要求，然后对几种典型的表驱动路 由协议和按需驱动路由协议进行分析，并指出它们的优缺点。，| 、 第三章首先研究了a o d v 路由协议的基本动作：路由发现和路由维护，探讨了路 由发现过程中存在的两点问题，并对这两个问题分别提出了改进方案，在此基础上提出 了a o d v - i 路由协议。 + 一 一 第四章首先介绍了n s 网络模拟环境以及使用n s 进行网络协议模拟的一般过程， 然后详细说明了a o d v 协议及a o d v - i 协议在n s 网络模拟环境下的实现。 第五章在不同的场景下对a o d v - i 协议和a o d v 协议进行仿真实验，分析仿真结 果及实验数据，对两个协议的网络性能进行对比分析。 一 、 第六章结论部分是对整个论文工作的总结以及下一步工作的展望，指出工作中有待 改进的地方，同时指明进一步的研究方向。 4 ， 东北大学硕士学位论文第2 章a d h o c 路由协议 第2 章a dh o e 路由协议 设计良好的路由协议是建立a dh o c 网络的首要问题，同时也是主要的研究热点和 难点。传统的距离矢量和链路状态路由协议并不适用于拓扑结构高度动态变化的a dh o c 网络。开发一种能有效地找到节点问路由的动态路由协议就成为无线a dh o e 网络设计 的关键。它应具有以下功能：能感知网络拓扑结构的变化、维护网络拓扑的连接、高度 自适应的路由。本章首先介绍a dh o e 网络协议的设计要求，然后介绍现有的a dh o c 路由协议，最后介绍了下一章将要重点研究和改进的对象a o d v 协议。 2 1a dh o c 路由协议设计要求 由于a dh o c 网络具有动态拓扑、有限带宽、终端受限、存在单向信道等特点，对 在其上运行的路由协议便提出了许多具体而严格的要求。相对于有线网络，有些要求是 a dh o c 网络特有的，这些要求主要有： ( 1 ) 收敛迅速：自组网的拓扑结构是动态的，随时处于变化之中，这就要求路由协 议必须对拓扑的变化具有快速反应能力，在计算路由时能够快速收敛，及时获得有效路 由，避免出现目的节点不可达的情况。 ( 2 ) 提供无环路由：无论在有线网络还是无线网络，提供无环路由是路由协议的一 项基本要求。但在a dh o c 网络中，由于拓扑结构动态变化会导致大量已有路由信息在 短时间内作废，从而更容易产生路由环路。在a dh o c 网络中提供无环路由就显得尤为 重要而且更难做到。 ( 3 ) 避免无穷计算：经典的距离矢量算法在某条链路失效时，有可能出现无穷计算 的情况。a dh o c 网络中，链路失败是经常发生的，这就要求在a dh o c 网络中运行的路 由协议必须能够避免无穷计算。 ( 4 ) 控制管理开销小：a dh o c 网络中无线传输带宽有限，传送控制管理分组不可避 免的会消耗掉一部分带宽资源。为了更有效地利用宝贵的带宽资源，需要尽可能地减小 控制管理的开销。 ( 5 ) 对终端性能无过高要求：无线移动终端使用可耗尽能源，c p u 性能、内存大小、 外部存储容量等都低于固定的有线终端，因此，在a dh o e 网络中不能对终端性能要求 过高。有线网络中用计算的复杂度来换取路由协议性能的做法，在a dh o c 网络中不再 适用。 ( 6 ) 支持单向信道：在a dh o c 网络中，经常有可能出现单向信道。支持单向信道， - 5 东北大学硕士学位论文第2 章a dh o c 路由协议 也是对路由协议的要求之一。 2 2a dh o c 路由协议 目前针对a dh o e 网络提出的路由协议可以分为表驱动( t a b l e d r i v e n ) 路由和按需路 i 主l ( d e m a n d b a s e d ) 两大类。下面将分别介绍这两类路由协议。 2 2 1 表驱动路由协议 表驱动路由协议又称为先应式( p r o a c t i v e ) 路由协议，它的目的是为网络中的每一个 节点维护到所有其它节点的一致和最新的路由信息，因而要求每个节点维护一个或多个 路由表来保存这些信息。当网络拓扑发生变化( 事件驱动) 时，相关的节点在整个网络中 发布更新信息，来确保路由信息的一致性。此外，即使网络拓扑没有发生变化，每个节 点也需要周期性地( 时间驱动) 广播它的路由表。表驱动路由协议的优点是它减少了节点 获得路由的延迟，使源节点能够立即判断目的节点的可达性，缺点是消费了较多的网络 资源，此外它完全浪费了一些资源来建立和重建那些根本没有被使用的路由。 主要的表驱动协议有：d s d v ，w r p ，c g s r ，o l s r ，f s r 。下面分别对这几个表 驱动路由协议进行介绍，并重点介绍d s d v 和o l s r 。 ( 1 ) d s d v ( d e s t i n a t i o n s e q u e n c e dd i s t a n c ev e c t o r ，目的序列距离矢量协议) 【5 】 d s d v 基于经典b e l l m a n - f o r d 路由选择过程的改进型表驱动路由算法，即它解决了 d v ( d i s t a n c ev e c t o r 距离矢量) 中的循环和无限计数问题，又保持了d v 的简单性，对拓 扑变化反应快【2 1 倒。其路由表中包含如下信息：目的地址、下一跳地址、路由跳数 ( m e t r i c ) 、目的节点的序列号以及路由建立时间、路由稳定时间、稳定数据指针。下面 对d s d v 路由算法进行描述。 路由表的建立：在组建网络阶段或有新节点加入时，节点通过广播来告诉其他节点 自己的存在，邻居节点收到这个广播包后就将信息插入到路由表，并立即发送新的路由 表，这样，经过一段时间后，每个节点就可以建立一个完整的路由表，表中包括了到网 络内部所有可能的目的节点的路由。 。 路由表的维护：d s d v 中路由表的维护是个很重要的问题。节点之间主要是传播路 由更新分组来维护路由。每个节点周期性地在全网广播路由更新分组，把完整的路由信 息发送给邻居节点。不管网络拓扑有没有改变，这种周期性的广播都会发生，这一点和 按需路由是不同的。除了周期性的广播，当网络结构发生变化时，也需要立即维护路由， 各节点马上广播路由更新分组，接到该分组的节点，确认是新的信息就将其m e t r i c 加l 后再发送，该过程一直持续，直到每个节点都收到该分组的一个拷9 q ( m e t r i c 不尽相同) 。 6 一 东北大学硕士学位论文第2 章a dh o e 路由协议 考虑到节点收到的更新信息可能是过期的，因此在目的节点端，每个路由表项都被 赋予一个序列号( s e q u e n c en u m b e r ) 。节点广播路由更新分组时，将自己的序列号加偶数 再发出去( 比如加2 ) ，邻居节点收到更新分组后，先来比较一下序列号，如果序列号大 于路由表中相应目的节点的序列号，则删除旧的信息，添加这条新的信息，如果相等， 就比较m e t r i c 值，选择m e t r i c 小的，否则，忽略此更新分组，保留原路由表。新的路 由广播包括目的节点的地址、到目的节点的跳数、请求信息包的序列号和新的发送序列 号。一 路由更新分组可以采用两种形式。第一种是全更新( f u l ld u m p ) ，它包含该节点的所 有路由表项，需要适配多个网络协议数据单元( n p d u ) ，在节点移动速度不高的网络中， 这种数据包很少被发送o 另一种是较小的“增进型( i n c r e m e n t a l ) 数据包，用来转发那 些最新的f u l ld u m p 后有变化的信息，即两次广播之间，如果有更新信息则用小的 i n c r e m e n t a l 数据包传送。 链路断开时路由表同样需要维护。可以通过两个方面来检测链路中断，一种是通信 硬件检测，另外还可以通过时间推断，即节点在过了一段时间还没收到前一节点的信息 就推断出链路中断，并使用m e t r i c 为无限大来描述断开的链路。此时，检测出链路断开 的节点就发一个更新分组，这个信息有一个新的序列号，此序列号是不可达节点的序列 号加个奇数( 比如加1 ) ，m e t r i c 为无限大。这会引起路由表的刷新，只有当再次收到丢 失节点的信息后新的路由才会重新建立起来。 当加入网络的节点越来越多，路由表的容量和带宽也相应增加，这是d s d v 的主要 缺点。只要拓扑改变，d s d v 就不稳定一直要到更新信息在全网广播。如果节点的移动 率较高，则d s d v 处理起来就更困难。 ( 2 ) w r p ( w i r e l e s sr o u t i n gp r o t o c o l ，无线路由协议) h o j w r p 路由协议是一个以在网络中所有节点中都保存路由信息为目标的表驱动型路 由协议。每个节点保存在路由表中的信息如下：距离、路由、链路开销和重传消息的列 表( m e s s a g er e t r a n s m i s s i o nl i s t ，m r l ) 。节点都通过这些保存着所有邻近节点与该节点 的连接状态。通过其相邻节点的最短路径生成树s s t ( s h o r t e s t - p a t hs p a n n i n gt r e e ) ，生成 自己的s s t ，然后再向邻居节点传送更新消息。如果一个节点没有消息需要发送，节点 间通过定期发送h e l l o 报文来探测链路是否正常或者是否有新的节点加入。m r l 记录关 于消息序列号、重传计数器、每一个邻居节点正确应答所需的标识和更新消息的更新列 表等信息。这就使得节点可以决定何时发送更新消息以及发送给哪个节点。更新消息包 括目的节点的地址、到目的节点的距离和目的节点的上游节点然后邻居节点就修改自己 的路由表并试图通过预备的节点建立新的路由。m r l 通过强迫每个节点必须对其所有 7 东北大学硕士学位论文第2 章a dh o c 路由协议 邻居节点发来的消息进行抑制性检查来避免无限重复计数的问题，从而减少了当路径中 断时出现循环的情况并加速了路由收敛。w r p 的优点就是当一个节点试图执行路径计 划算法时，可以通过目的节点的上游节点所保存的信息和邻居节点所保存的信息来限制 算法，使得算法收敛得更快并避免路由当中的环路。 ( 3 ) c g s r ( c l u s t e r e dg a t e w a ys w i t c hr o u t i n g ，簇头网关交换路由协议) 幽】 c g s r 是在d s d v 协议基础上融合分层次的思想设计的。协议采用l c c ( l e a s t c l u s t e rc h a n g e ) 算法，把移动自组织网络划分成若干个簇，并根据簇首对网络进行簇的 划分，每一个簇中有一个“簇首 ( c l u s t e rh e a d ) ，而同时位于多个簇的节点被称为网关。 簇首负责簇内节点的路由与通信，簇首与簇首之间通过网关进行通信。 簇首并不固定，簇首与簇成员在一定条件下可以互相转化，具体方法由簇首选择算 法来决定。每个节点维护两种数据结构：路由表和簇成员表。节点使用d s d v 协议，周 期性地与同簇内的邻居节点交换簇成员表，更新表信息。当一个节点要与其它簇内节点 通信时，数据包首先传递给自己所在簇的簇首，然后通过网关到达另外一个簇首，以此 种方法穿过中间的分簇，到达目的节点所在簇的簇首，然后再转发给目的节点。其中每 一跳的通信应用的仍然是d s d v 协议。c g s r 协议将d s d v 协议作为底层的路由协议， 每个簇首维护一个簇成员表，并周期性的更新表中成员消息。 c g s r 通过分簇，大大减少了维护路由表所需要的信息量。该协议采用了分层的路 由查找机制，当网络规模较大时避免了大量路由查找报文的洪泛，绝大多数报文只在簇 首间进行转发，一定程度上降低了查找报文的开销，并具有良好的可扩展性。缺点是引 入了簇的概念，增加了算法复杂度和簇首的维护开销，在网络规模较小时优势并不明显。 另外，因为路由的性能依赖于特定的节点( 群首、网关或普通节点) ，与群首有关的链路 故障造成的时间复杂度要比d s d v 高，需要额外的时间进行群首的选择。另外，c g s r 的群首是网络的脆弱点，抗毁性差，对于军事应用这是一个关键问题。当然，分级路由 也有优点，它的扩展性强，便于构建规模较大的网络。 ( 4 ) o l s r ( o p t i m i z e dl i n ks t a t er o u t i n g ，优化链路状态路由协议) 【7 】 o l s r 是一种先应式的链路状态路由协议，它是在传统链路状态协议的基础上针对 a dh o e 网络的特点发展而来的【2 5 2 6 。o l s r 协议对链路状态协议所做的优化有： 采用仅选择部分节点作为控制分组的中继节点的方式以减小控制分组t c ( t o p o l o g y c o n t r 0 1 ) 的泛洪( f l o o d i n g ) 范围：任意节点仅选择部分邻居节点作为它的中继节点，全网 范围内都只有选定的中继节点才转发控制分组，其它邻居节点收到该节点发送的控制分 组时，只进行处理而不转发。这样就显著地减少了网络中广播的控制分组数量。这类节 点被称为多点中继节点( m r p ：m u l t i p o i n tr e l a y s ) 。 _ 8 一。t? 东北大学硕士学位论文第2 章a dh o e 路由协议 缩减了控制分组的大小：节点并不发布与所有邻居节点相连的链路信息，而只发布 它与部分邻居的链路子集，这些邻居是它的多点中继选择节点( m p rs e l e c t o r ) ，也就是 节点只发布它与m p rs e l e c t o r 间的链路。 m p r 节点承担在全网中通告链路状态的责任。为了计算到目的节点的最短路由， 只需在链路状态信息中包含m p r 节点与其m s ( m p rs e l e c t o r ) 节点之间的链路状态信息 就足够了。但同时也可以为了冗余的需要附加一些其它可用的链路状态信息。 m p r 节点周期性的洪泛t c 控制消息：m p r 节点向全网洪泛自己产生的包含与其 m s 节点之间链路信息的t c 控制消息；m p r 节点转发收到的来自其它m p r 节点的t c 控制消息。在第一种情况下，m p r 节点还需要在t c 控制分组中附加自己被邻居节点选 举成为m p r 节点的信息，这样随着t c 控制消息周期性的发出，m p r 节点自身的m p r 身份信息也周期性的洪泛到全网。洪泛t c 控制消息的过程，其本质就是m p r 节点向 全网宣告自己的m s 节点通过自己是可达到的。在路由计算中也利用m p r 节点来计算 到达目的节点的路由。 节点在一跳邻居节点中选举那些同自己之间至少拥有一条对称双向链路的节点作 为自己的m p r 节点。这样就使得m p r 机制天然地避免了在无线网络中传输数据时的单 向链路问题。o l s r 路由协议不对下层协议作任何特殊的要求，不依赖于其它任何协议。 在o l s r 中，节点周期地交换信息来维护网络拓扑。该协议要求每一个节点保存它 到网络中所有可达目的节点的路由，因此它特别适用于网络规模大、节点分布密集的网 络。无线网络中，由于冲突或其它传输问题会导致数据分组的丢失。运行o l s r 路由协 议的节点周期性地发送自己的控制信息，在接收端，根据序列号的大小就可以区分新旧 信息，所以不要求传送控制分组。o l s r 逐跳查找路由，它要求节点周期地发送t c 分 组来发布m r ps e l e c t o r 信息，以帮助其它节点建立到它的路由。需要根据与邻节点的链 路变化率，增加或减小发送t c 分组的时间间隔。 ( 5 ) f s r ( f i s h e y es t a t er o u t i n g ，鱼眼状态路由协议) 【2 7 ，2 8 】 f s r 是先验式链路状态路由协议，其目的是通过鱼眼效应( 近处的物体清晰，远处 的物体模糊) 减少信息流量它对传统的链路状态算法进行了修改