（计算机应用技术专业论文）ad+hoc网络路由协议性能优化研究.pdf

硕士学位论文摘要 学科、专业：工科、计算机应用技术 研究方向：计算机通信与网间互连技术 作者：盟级硕士研究生王至玲 题目：a dh o c 网络路由协议性能优化研究 英文题目：r e s e a r c ho np e r f o r m a n c eo p t i m i z a t i o no fr o u t i n g p r o t o c 0 1 i na dh o cn e t w o r k 主题词：a dh o e 网络，路由协议，d s r ，t c p , 网络编码 k e y w o r d s ：a dh o cn e t w o r k ，r o u t i n gp r o t o c o l ，d s r ，t c p ， n e t w o r kc o d i n g 南京邮电大学硕e 研究生学位论文摘要 摘要 a dh o e 网络是由组带有无线收发装置的移动节点组成的一个无线移动通信网络，由于组网快 速、灵活，使用方便，目前已经得到了国际学术界和工业界的广泛关注。a dh o c 的这些特点也使得 基于传统网络设计的路由协议无法在a dh o c 网络环境下正常工作，因此i e t f 成立了一个专门的 m a n e t ( m o b i l e a d h o c n e t w o r k s ) 工作组来研究和开发a d h o c 网络的路由算法。 本文首先介绍了a dh o e 网络的研究背景和意义，对其概念和关键技术进行了描述。然后把重 点放在a dh o c 网络路由协议上。 其次，分析传统t c p 协议在a dh o c 网络环境中遇到的问题和研究现状。针对a dh o c 网络路由 协议影响t c p 性能的因素，提出个改进的e - d s r 路由协议。该协议在路由选路中综合考虑路径 的稳定性和路由负载均衡，并且根据路径的生存时间主动维护路由，为传输层提供了可靠的链路和 快速的路由收敛机制。n s 2 仿真结果表明，相比于d s r ，e - d s r 协议能提高t c p 在a dh o c 网络中 的吞吐率，改善网络| 生能。 最后，本文介绍了网络编码的基本原理和研究现状，针对传统无线a dh o c 网络路由协议不能 很好支持网络编码及无线网络编码方法c o p e 被动等待编码机会的不足，提出一种主动网络编码感 知的路由协议c a - d s r 。该协议综合考虑路由跳数，编码机会以及路由发现延迟来选择最佳传输路 径。n s 2 仿真结果表明，改进的路由协议能够有效地发现编码机会，提高网络吞吐量。 关键词：a dh o c 网络，路由协议，d s r ，t c p ，网络编码 南京邮电大学硕一l ：研究生学位论文 a b s t r a c t a b s t r a c t a dh o ei saw i r e l e s sm o b i l ec o m m u n i c a t i o nn e t w o r kc o m p o s e do fag r o u po fm o b i l en o d e sw i t h w i r e l e s st r a n s m i t t e r - r e c e i v e rs e bb e c a u s ei tc a nb ee a s i l ya n dn e a t l yd e p l o y e d , e a s yt oo p e r a t e , h a sa l r e a d y r e c e i v e di n c r e a s i n ga t t e n t i o n sf r o mi n t e r n a t i o n a la c a d e m i cc i r c l e sa n di n d u s t r ya tp r e s e n t t h e s ec h r f a c t e r so f a dh o en e t w o r k sm a k em u t i n gp r o t o c o lb a s e do nt r a d i t i o n a ln e t w o r k sg a l l th eu s e da ta dh o en e t w o r k s s o i e t fe s t a b l i s h e das p e c i a lm a n e t w o r k i n gg r o u pt os c u d ya n dd e v e l o pt h em u t i n ga l g o f i t h mo f a dh o e f i r s tt h eb a c k g r o u n d , t h ep r e s e n ts i t u a t i o na sw e l la st h er e s e a r c hs i g n i f i c a n c eo f a dh o en e t w o r k sw e r e i n t r o d u c e di nt h e 珲i p 既a l s oi t sc o n c e p ta n dt h ee s s e n t i a lt e c h n o b g ys t n l c t u r ew e r ed e s c r i b e d a f t e rt h a t , m u t i n gp r o t o c o l so f a dh o cn e t w o r k sw e r ef o c u s e do ni nt h i st h e s i s s e c o n d l y , t h ep r o b l e m st h a t t h et r a d i t i o n a lt c pp r o t o c o le n c o u n t e r e di nt h ea dh o en e t w o r k e n v i r o n m e n ta n dt h es t u d ys t a t u sw e r ea n a l y s e d a c c o r d i n gt ot h ef a c t o r st h a tt c pp e 墒m l a n c ew a s i n f l u e n c e db ya dh o em u t i n gp r o t o c o l s a ni m p r o v e dm u t i n gp r o t o c o ln a m e de - d s r ( e n h a n c e dd s r ) w a s p r e s e n t e d t h i sp r o t o c o lc o n s i d e r e dt h em u t es t a b i l i t ya n dr o u t e 位哂cl o a db a l a n c ea st h er o u t es e l e c t i o n c r i t e r i a , a l s om a i n t a i n e dt h er o u t ea c c o r d i n gt ot h el i f e t i m eo f t h er o u t e , a i r m e da tp r o v i d i n gr e l i a b l el i n ka n d v a p i dm u t i n gc o n v e r g e n c em e c h a n i s mf o rt h et r a n s m i s s i o nl e v e l n s 2s i m u l a t i o nr e s u l t ss h o wt h a te - d s r m u t i n gp r o t o c o lc a l li m p r o v et c p st h r o u g h p u ta n dt h ep e r f o r m a n c ei na dh o en e t w o r kc o m p a r e dw i t h d s r f i n a l l yt h en e t w o r kc o d i n gb a s i cp r i n c i p l ea n dt h er e s e a r c hp r e s e n ts i t u a t i o nw e r ei n t r o d u c e di nt h e p a p e r i na l l u s i o nt ot h el i m i t a t i o nt h a tt r a d i t i o n a lw i r e l e s sa dh o em u t i n gp m t o e o lc a l l n ts u p p o r tn e t w o r k c o d i n gw e l la n dn e t w o r kc o d i n gs y s t e mc o p ep a s s i v d yw a i t sf o rc o d i n go p p o r t t m i t i e s ，a ni m p r o v e d c a - d s r ( c o d i n ga w a r e - d s r ) p r o t o c o li sp r e s e n t e d t h i sp r o t o c o lc o n s i d e r e dt h e c o d i n go p p o r t u n i t i e s , f i n d i n gt h es h o r t e s tp a t ha n dn e a t l ya v o i d i n gl o n gm u t ed e l a yc o m p r e h e n s i v e l ya st h e m u t es e l e c t i o nc r i t e r i a t h en s 2s i m u l a t i o nr e s u l ts h o w st h a tt h ei m p r o v e dr o u t ep r o t o c o lc a nd i s c o v e rt h e c o d eo p p o r t u n i t ye f f e c t i v e l ya n di m p r o v et h en e t w o r kt h r o u g h p u t k e y w o r d s ：a d h o e n e t w o r k ，r o u t i n gp r o t o c o l ，d s r ，t c p ，n e t w o r kc o d i n g i i 南京邮i 毡大学硕上研究生学位论文 目录 目录 摘要。一1 0 l e 懿罗r i 己4 0 c t 。 缩略词。一。一v 第章绪论。一。一l 1 1 研究背景1 12 基础知识1 1 3 研究内容和组织结构4 第二章a d h o c 网络路由协议分析。一。一一。一。5 2 1a dh o c 路由协议概述5 2 2a dh o e 网络路由协议分类6 2 3 典型按需路由协议性能分析7 2 3 1a o d v 路由协议7 2 3 2d s r 路由协议。8 2 3 3a o d v 和d s r 的比较1 2 2 4 本章小结1 3 第三章基于跨层协作改善t c p 性能的路由协议。1 4 3 1t c p 传输控制协议1 4 3 1 1t c p 基本工作原理急1 4 3 1 2 常见的t c p 版本1 9 3 2 无线a dh o e 网络环境对t c p 性能的影响2 0 3 2 1 网络拥塞2 0 3 2 2 比特误码2 0 3 2 3 节点移动2l 3 2 4m a c 层不公平问题2 2 3 3a dh o c 网络中t c p 性能研究现、枕2 3 3 3 1 现有的解决方案2 3 3 3 2 现有方案存在的问题。2 5 3 4 种改进的e - d s r 路由协议肌2 6 3 4 1 路由发现过程2 7 3 4 2 路由维护过程2 9 3 5 仿真和性能分析3 2 3 5 1 仿真环境及参数设置3 2 3 5 2 仿真结果及分析3 4 3 6 本章小结3 7 南京邮电人学硕上研究生学位论文 目录 第四章主动网络编码感知的路由协泌。3 8 4 1 网络编码3 8 4 1 1 网络编码基本原理3 9 4 1 2 常见的网络编码方法4 0 4 2 无线a d1 i i 网络编码4 2 4 2 1 无线a dh e c 网络编码的特性和研究方向一4 2 4 2 2 基于网络编码的无线a dh o c 路由协议4 3 4 3 一种基于d s r 的主动网络编码感知的路由协议4 6 4 3 1 路由发现过程4 6 4 3 2 路由维护过程5 0 4 3 3 网络编码过程。51 4 4 仿真和性能分j 阮5 2 4 4 1 仿真环境和参数设置5 2 4 4 2 仿真结果及分析5 4 4 5 本章小维一5 5 总结与展望5 6 参劳学文献。5 8 本人已发表的论文 至l 谢。6 4 i v 南京邮电大学硕- l 研究生学位论文 缩略词 缩略词 缩略词英文全称译文 搬 a s s o c i a t i v i t y - b a s e dr o u t i n g 基丁相互关系的路由协议 a o d v按需距离矢量路由协议 a dh o co nd e m a n dv e c t o rr o u t i n g p r o t o c o l b e rb i te r r o rr a t e 误比畴率 c a - i 踩 c o d i n g a w a r em u t i n gb a s e do nd s r基于d s r 的编码感知路由仂议 c g 跟 c l u s t e r - h e a d a ys w i t c h 分群网关蝴由 r o u 劬g d s d v d e s t i n a t i o n - s e q u e n c e d 目的：肖点序歹l 盥| ! 离向量 d i s t a n c e - v e c t o rr o u t i n g d 陬 d y n a m i cs o u r c er o u t i n gp r o t o c o l 动态源路由协议 e c x e x p e c t e dc o d e dt r a n s m i s s i o nc o u n t 期望的编码传输数目 e 加i s r e n h a n c e dd s r 增强的d s r 路由协议 e l f n e x p l i c i tl i n kf a i l u r e n o t i f i e a f i o n 显式路由失效通知 耵x e x p e c t e dt r a n s m i s s i o nc o u n t期望传输次数 m a n 垂m o b i l ea dh o cn e t w o r k s 移动白组织网络 m s sm a x i m u m s e g m e n ts i z e 最人报文段 r e r r r o u t ee r r o r 路由错误 r n c r a n d o mn e t w o r kc o d i n g随机网络编码 r l 砸pr o u t er e p l y 路由响应 r r e q r o u t e rr e q u i r e m e n t s路由请求 i h o r e t m n s m i t 1 i m e o u t计时器超时时重传 t o r a t e m p o r a l l yo r d e r e dr o u t i n g 临时排序的路由算法 a i g o r i t h m v 南京邮电人学硕l 研究生学位论文第一章绪论 第一章绪论 本章首先概述无线a dh o c 网络的研究背景，以及当前国内外对a dh o c 网络的主要研究热点和 存在的各种问题，说明本文选题的依据。在此基础上阐述本文主要研究内容以及完成的主要工作， 最后给出学位论文的组织结构。 1 j 研究背景 随着移动通信、个人通信和计算机网络的发展，无线通信网络技术正成为当前信息技术最活跃 的一个研究领域，新技术不断涌现。然而，我们经常提及的移动通信技术一般都要依赖于中心控制 点来实行集中控制。它们通常需要基于预先架设的网络基础设施才能运行。但在某些场合，这类有 中心的移动通信技术却未必能f 洼任。例如，发生水灾、地震或火灾等大型灾害的营救，边远地区执 行任务、偏远矿山作业以及临时组织的会议，a - i t , f d 上部队的快速推进等。这些场合的通信不能依赖 于任何预先架设的网络基础设施，而需要一种能眵陕速自动组网的通信技术。为了满足这些需求， a dh o c 网络技术应运而生。同时也将个新的无线网络世界展现在我们眼耐。a dh o c 网络可以 通过临时组网的方式在恶劣环境中支持移动节点之间的数据、语音、图像和图形等多种业务的无线 传输，应用范围可以覆盖工业、商业、医疗、家庭、办公环境、军事等各种场合，因此，关于a dh o e 网络相关技术的研究不仅具有重要的社会和经济意义，也具有十分重要的战略意义，从而也成为新 轮的研究热点 2 1 。 1 2 基础知识 a dh o c 网络是由一组带有无线收发装置的移动终端组成的一个多跳的临时自治系统，是一种新 型的无线移动通信网络。a dh o c 网络中每个节点可以随f , r l j - i ：b _ , 移动，可以通过无线连接组成任意的网 络拓扑结构。这些节点除了具备普通的终端功能外，而且还具有路由和报文转发的功能。作为种 新型的无线网络，一些在传统的有线和无线网络中的技术都不能直接被运用到其中，特别是在协议 。 设计方面要面对很多新的问题。 南京邮电大学硕：l 研究生学位论文第一章绪论 由于a dh o c 网络在协议设计和组网方面都有着与现有的有线网络显著的差异，综合而言，目 前a dh o e 网络的研究中，主要集中在以下门l 爪方面： ( ) m a c 机制 m a c 协议主要是解决a dh o c 网络中的信道接入问题，它控制网络中节点如何接入无线信道， 对a dh o e 网络的性能起着决定性的作用。由于a dh o e 网络的无线信道不同于一般网络的信道，它 是多跳共享的信道。所以就带来其特有的隐藏终端和暴露终端等问题，这些问题需要通过设计专门 的m a c 协议来解决【3 】o 但是目前m a c 协议方面戮以形成标准化，将i e e e 8 0 2 1 1 协议娴于a d h o e 网络中是一个主要的研究方向。 ( 二) 路由协议 路由协议是a dh o c 网络的重要组成部分。要实现多跳路由，必须要有路由协议的支持。无线 a dh o c 网络中节点既是主机，也是路由器，每个节点在使用网络资源的同时，也承担着构造网络连 接进行存储转发的任务。因此，有效的单播和多播路由协议是实现无线a dh o e 网络的关键技术 之一。已有的常规路由协议周期性的路由更新消耗大量的网络带宽和节点能源，路由建立更新过程 对拓扑变化的收敛比较慢，不能适合a dh o c 网络的要求【4 】。a dh o e 路由面临的主要挑战是传统的 保存在节点中的分布式路由数据库如何适应网络拓扑的动态变化。新协议一般以广播或组播方式建 立网络路由，核心是尽量减少广播风暴。目前，路由协议的研究仍然是a dh o e 网络成果最集中的 部分。不过，这些协议仍有这样或那样的缺陷，不能满足广泛应用的要求。因此实现寻找种快速 收敛，控制管理开销小，适应a dh o e 网络动态变化，支持单向信道的路由协议具有重要的意义， 既涉及到信息传输策略问题，也涉及到网络拓扑的管理问题。 ( 三) t c p 性能问题 t c p 协议是针对网络链路可靠性高的有线网络设计的，因此传统的t c p 协议应用于无线网络将 会面临挑战。在a dh o e 网络中，链路的高误码率和节点的移动等因素会造成数据包的丢失，这将 严重影响t c p 性能。已有的理论分析和仿真实科5 】均表明为有线网络环境定制的t c p 协议无法为无 线a dh o e 网络提供满意的吞吐率，特别是当无线节点移动频繁时。t c p 没有考虑非拥塞因素丢包 因素，将其也当作是网络拥y a 4 8 , , g ，从而错误地进入拥塞控制，这将导致严重的| 生能问题。 因此，针对a dh o c 网络中t c p 性能的研究和改进是非常有必要的。 基于此，学术界提出了一些研究方案，这些研究方案主要有两种：采用跨层设计的思想从 m a c 层，网络层等低层为传输层提供准确的网络链路信息，让发送端清楚网络的真实状态；在 终端根据分组的传送情况来对网络状态进行判断，主要是利用启发式算法【q 。 2 南京邮电人学硕l 研究生学位论文 第一章绪论 ( 四) 网络编码 网络编e 瓢n e t w o r kc o d i n g ) 使得网络节点既实现路由功能又实现编码功能，已被证明是可以逗& 丘 网络容量理论传输极限的有效方法。2 0 0 0 年，r a h l s w e d e 等人发表了“n e t w o r ki n f o r m a t i o nf l o w ” 7 1 证明了组播网络在网络编码传输模式下可以达到极大流容量理论上限。网络编码刚提出的几年，研 究工作主要集中在网络编码的理论以及构造和应用等研究。从2 0 0 5 年后，许多国外学者开始研究无 线网络中的网络编码，然而网络编码在无线网络( 包括无线自组织网络、无线m e s h 网络、无线传感 器网络) 的研究和应用还处于起步的阶段。 无线网络与有线网络中的网络编码的理论和应用有着显著的差别，这主要是由无线网络的结构 特征决定的。而无线网络环境也是网络编码非常适宜的个应用领域。因为无线链路的不可靠性和 物理层广播特性非常适合使用编码的方法。相对于传统网络编码机制来说，无线网络中的网络编码 尤其能够增加单播流的吞吐量，这也是无线网络编码与传统网络编码主要区别之一，这同样得益于 无线介质的广播特性。 编码最初是在物理层，在高层是不i c - 1 白i 一1 b 2 , 带来好处一直以来是有争议的 8 1 ，而网络路由的传统操作 是尽可能避免数据流的碰撞，但最近研究显示，在多播环境下与单一路由相比，如果允许中间节点 处理信息可明显提高传输速率1 7 j 。网络编码的核心思想就是允许并提倡网络中间节点对信息进行融 合。路由本身则被视为一种特殊的编码，即节点的输出是输入的组数字排列。 网络编码主要优势在于如果已知网络的链路性能，就可以计算出源点到多个终点的最大信息吞 吐量，它可以使资源得到充分利用，并且能使网络资源利用达到理论上限。这有赖于网络节点( 比如 路由器) 在转发信息前对接收数据进行编码。具备了网络编码功能的节点砂各个输入链路获得信息， 并进行编码，然后把信息传送给所有输出链足卯。 ( 五) 节能问题 能耗问题是a dh o c 网络能否被大规模应用的个重要问题。网络中移动节点般使用电池供 电，而电池容量在短期内很难得到大规模提高。所以采用合适的路由算法、使用功耗小的硬件来减 少节点的能量消耗，对a dh o c 网络尤为重要f 1 0 1 。可以采用自动功率控制机制来调整移动节点的功 率，以便在传输范围和干扰之间进行折衷，还可以利用智能休眠机制。采用功率感知路由和使用功 耗很小的硬件来减! 埔邑量的消耗。 南京邮电大学硕士研究生学位论文第一章绪论 1 3 研究内容和组织结构 根据a dh o c 网络的特点，研究适合这种网络的高效路由协议成为当前移动自组网络中亟待解 决的问题，所以路由协议是当前a dh o e 网络研究最集中的部分。本课题选择路由协议作为研究对 象，对当前几种比较常见的a dh o c 网络路由协议进行了研究、学习、分析和比较。并且结合了t c p 的工作原理和机制，在d s r 路由协议的基础上提出了种改进的路由协议e o d s r ；结合无线网络 编码的理论和工作机制，在d s r 和a o d v 的基础上提出种改进的主动网络编码感知网络编码的 路由协议c a - d s r 。并对其用仿真工具n s 2 进行仿真，对仿真结果进行了分析。 本论文的章节安排如下： 第章是绪论，论述了本文课题的研究背景，简要介绍了无线a dh o e 网络的概念，研究的关 键技术等基础知识，指出了路由协议对a dh o e 网络的重要性。并阐述了本文的主要研究内容以及 完成的主要工作。 第二章主要研究了a dh o c 网络路由协议，描述其特性和主要分类。重点阐述在后续章节中使 用的两个经典的按需路由协议按需距离矢量路由协议( a o d v ，a dh o eo nd e m a n dv e c t o r r o u t i n gp m t o c 0 1 ) ) f l l 动态源路由协议( d s r ，d y n a m i cs o u r c er o u t i n gp r o t o c 0 1 ) ，并对它们进- i t l t , 较。 第三章阐述了t c p 的基本工作原理，结合a dh o c 网络分析影响t c p 性能的若干因素，研究现 状，改进思路以及存在的问题，重点讨论了网络层协议对t c p 的影响。在此基础上提出了种考虑 稳定性和链路负载平衡的改进的路由协议e - d s r ( e n h a n c e dd s r ) ，仿真结果表明e - d s r 能有效地提 高路由的稳定性，为源端提供最新的路由信息，有效减少了传输层因链路中断后路由收敛慢而导致 的延迟和低吞吐率，提高了t c p 的性能。 第四章结合当前无线网络领域网络编码新技术，介绍了网络编码的基本概念、原理、常见的网 络编码方法、研究现状和应用领域，并重点介绍了基于网络编码的无线网络路由协议。针对目前存 在的网络编码方法c o p e 的优缺点，以及a dh o c 网络路由协议不能很好支持网络编码的现状，结 合无线a dh o c 网络中经典的a o d v 和d s r 路由协议，提出一种新的主动网络编码感知的 c a - d s r ( c o d ea w a r e - d s r ) 路由协泌在路由发现的过程中借助路由表和邻居节点信息主动地寻找 出拥有编码机会的节点，综合考虑最短路径，编码机会以及路由发现延迟来选择最佳传输路径。仿 真实验表明，与传统路由协议相比，c a - d s r 能够充分发现编码节点和编码机会，有效地缓解网络 拥塞并提高网络吞吐量。 第五章是展望和总结。 4 南京邮电大学硕l 研究生学位论文第二章a dh o c 网络路由协议分析 第二章a dh o c 网络路由协议分析 a dh o c 网络是一种移动的无线网络。一方面，“移动 意味着网络中的终端可以任意在网络中 随意移动并可能随时关闭。各个终端的发送装置天线类型多种多样，发送功率也各不相同，这就要 求网络拓扑结构和节点相邻关系不断变化，协议控制信息交换就要更加频繁，否则节点中的网络状 态信息就会滞后。另一方面，“无线”的特性意味着链路带宽的有限性。a dh o c 网络采用无线传输 技术作为底层通信手段，由于无线信道本身的物理特性，其能提供的网络带宽相对有线信道要低得 多。同时，由于无线信道传输高误码率、衰落、冲突、信号衰减等原因，移动终端获得的实际带宽 远小于理论带宽，带宽资源就更为宝贵【4 j 。所以，在无线环境中，协议设计的主要要求是尽量碱沙 不必要的带宽资源浪费。同时由于在a dh o c 网络中节点具有路由功能，在这种动态的网络中如何 建立、维护和选择路由，提高网络的连通陛和效率，最大限度地利用宝贵的无线资源是a dh o c 网 络的个根本问题】。本论文提出的路由算法，就是针对a dh o c 网络已有的路由协议进行相应的 改进，该算法的有效实现离不丌己有路由协议的有效工作，因此本章专门介绍a dh o c 网络的路由 协议。 2 1a dh o c 路由协议概述 移动自组网的路由协议主要包括路径产生、路径选择以及路径维护三项核心功能。其中，路径 产生是指根据集中式或分布式的网络状态信息和用户业务需求生成路径，网络状态信息和用户业务 状态信息的收集与分发是该过程的主要内容。路径选择是指根据网络状态信息和用户业务状态信息 选择最合适的路径，在自组网路由协议中，路径产生和路径选择这两项功能通常合在起成为路由 发现。路径维护是指对所选路径进行维护。由于a dh o c 网络是一种没有基础设施的网络，它工作 于无线环境中，通信带宽受限，且节点具有移动性，因此路由协议还必须考虑以下这些因素所造成 的影响【1 2 j 。 动态变化的网络拓扑。结构动念变化的拓扑结构是自组网最显著的特点。因此路由协议应该尽 可能快地为连接请求提供最新的路由信息。这就要求路由算法收敛要迅速。 南京邮电人学硕：e 研究生学位论文第二章a dh o c 网络路由协议分析 单向信道的存在。在采用无线信道的自组网环境中，由于发射功率或地理位置等凶素的影u | 句， 可能存在单向信道，因此移动a dh o c 路由协议应当具备识别和利用单向链路的能力。 周斯i 生的广播拓扑信息会占用大量的无线信道资源，耗费电池能量，这将会严重刚氐系统的性 能。因此要求路由算法简单有效，降低控制管理开销，尽可能缩短发射时间和减少发射的数据量， 以节约能源。 a dh o e 网络路由面临的主要挑战是：传统的保存在节点中的分布式路由数据库，如何适应网络 拓扑的动态变化。新协议一般以广播或组播方式建立网络路由，核心是减少广播风暴。目前，a dh o e 网络工作组己提出许多协议草案，_ 般普遍得到认可的代表性成果有d s d v ( d e s t i n a t i o n - s e q u e n c e d d i s t a n c e - v e c t o rr o u t i n g ，目的节点序列距离向量) 1 3 1 、c g s r ( c l u s t e r - h e a dg a t e w a ys w i t c hr o u t i n g ，分群网关交换路由) 1 4 1 、a o d v ( a dh o eo n - d e m a n dd i s t a n c ev e c t o rr o u t i n gp r o t o c o l ，按需距离 矢量路由协议) 1 5 l 、d s r ( d y n a m i cs o u r c er o u t i n gp r o t o c o l ，动态源路由协议) 【1 6 1 、t o r a ( t e m p o r a l l y o r d e r e dr o u t i n ga l g o r i l h m ，临时排序的路由算法) 【1 7 】和a b r ( a s s o c i a t i v i t y - b a s e dr o u t i n g ，基于相互 关系的路由协议) f l 翻等。源头性的创新研究主要集中在2 0 0 1 年以前，后续的成果多为这些协议的改 进，目前，路由协议的研究仍然是a dh o c 网络成果最集中的部分。研究人员发表了许多关于a dh o c 网络路由协议的学术论文，对a dh o c 路由协议进行设计主要包括以下几种思路： ( 1 ) 根据a dh o c 网络特点所创建的、与传统路由协议完全不同的方法，如d s r ； ( 2 ) 根据原来已经存在的路由方法进行改进、使之适应a dh o c 网络对路由的需求，如d s d v ； ( 3 ) 将前面两者的优点结合在_ 起而形成的新的路由协议，如a o d v 。 另外，还有一些路由协议是由节点收集网络的资源隋况，选择一条可能满足用户特定需求的路 由。 2 2a dh o c 网络路由协议分类 多年来，研究者们己提出数十种m a n e - q 路由协议方案，可从不同角度对这些协议进行分类。 根据路由发现策略的不同，可将其分为表驱动路由( t a b l e - d r i v e np r o t o c o l s ) 、按需驱动路由( o n - d e m a n dd r i v e np r o t o c o l s ) 和混合路由；根据网络拓扑结构的差异，可将其分为平面结构路由( f l a tp r o t o c o l s ) 和分簇路由( c t u s t e r e dp r o t o c o l s ) ；根据是否使用g p s 系统作为路由辅助条件，可将 其分为地理定位辅助路由和无地理定位辅助路由。e 述几种协议类别间的关系，如图二1 所示。 6 南京邮电大学顶- ：研究生学位论文 第- 二章a dh o e 网络路由协议分析 a dh o c 路由协议 j 懋翌宾乎一 + 辅助路由 地理定位 辅助路由 图2 - l 路由协议分类 平面路由 分簇路由 路由 其中，表驱动路由协议又称为主动式( 或先验式) 路由协议( p m a c t i v ep r o t o c o l s ) 。该路由协议 试图维护网络中从各个节点到所有其余节点的最新路由信息，所有路由信息保持致。每个节点都 维护一张或几张到网络中其他节点的路由信息表。目前常见的有c e p e r k i n s 在1 9 9 4 年提出的d s d v 路由协议等。这类路由协议通常是通过修改常规的i n t e m e t 路由协议以适应移动a dh o e 网络环境， 如d s d v 协议是在r i p 协议的基础上，通过引a 0 - 芋歹u 号机制解决了“路由环路”和“无穷计数”的 问题：通过采用“时间驱动”和“事件驱动”机制来更新路由信息，尽量减少路由等控制信息对无 线信道的占用，以提高系统效率。 在主动式路由协议中，每个节点需要实时地维护路由信息。这样来，在网络规模较大、拓扑 变化较快的环境中，大量的拓扑更新消息会占用过多的信道资源，使得系统效率下降。为此，1 9 9 6 年卡耐基梅隆大学的d a v i db j o h n s o n 在d s r 协议中提出了种新的路由选择原则：按需路由协议 。按需路由协议又称为反应式路由协议( r e a c t i v ep r o t o c o l s ) 。它是种被动式的路由协议，与主动 式路由协议相比，在这类协议中，节点平时并不实时地维护网络路由，只有在节点有数据需要发送 时，从激活路由发现机制寻找到达目的地的路由。根据i 虱际上目前研究的结果【1 9 】可知，在各种不同 的情况下比较时，如数据源数、节点的移动性、自组织网络模型以及网络负载等，基于按需方式的 路由算法要比基于表驱动方式的路由算法在性能上有着明显的优势。 2 3 典型按需路由协议性能分析 a o d v 路由协渺是一种改进的距离向量路由协议，同时具有按需路由协议的特点。在a o d v 路由协议中，网络中的每个节点在需要进行通信时才发送路由分组，而不会周期性地交互路由信息 以得到所有其它主机的路由；同时，也具有距离向量路由协议的些特点，即各节点路由表只维护 本节点到其他节点的路由，而无需掌握全网拓扑结构。 7 南京邮电大学硕一l 研究生学位论文第二章a dh o c 网络路由协议分析 a o d v 路由协议中有三种类型的消息控制帧：路由请求r r e q ( r o u t er e q u e s t ) ，路由应答r r e p ( r o u t er e p l y ) 和路由错误r e r r ( r o u t ee r r o r ) 消息。当源节点需要发送数据而又没有到目的节 点的有效路由时，启动个路由发现过程：向网络广播一个路由请求分组r r e q ，a o d v 允许中间 节点响应r r e q ，当收到请求的中间节点或目的节点有一条“足够新”的路由到达目的节点时( “ 足够新”是指这条路由对应的目的序列号大于或等于r r e q 中的目的序列号) ，中问节点或目的节 点以单播的方式向源节点返回相应的r r e p 分组，r r e p 沿着刚建立的逆向路径传输回源节点，源 节点收到该r r e p 后则开始向对应目的节点发送数据。在数据传输过程中，当中间节点检测到一条 正在传输数据的活动路由的下跳链路断开或者节点收到去往某个目的地节点的数据报文，而节点 没有到达该目的地节点的有效路由时，中间节点向源节点单播或多播路由错误消息r e r r ，源节点 收到r e r r 后就知道存在路由错误，并根据r e r r 中指示的不可达目的地重新找路。在r e r r 中 有一条链表，这条链表是由因为某条链路断了而导致无法到达的所有目的节点组成的。每个接收 到r r e q 的节点智j 保存到源节点的路由，当到目的节点的路由找到时就能用单播将r r e p 传回源 节点吼 对照理想路由协议标准，a o d v 协议主要具有以下优点【2 l 】：通过使用序列号来避免出现路由 环路，且易于通过编程实现；支持中间节点应答，能使源节点陕速获得路由，有效减少了广播分组 数；按需驱动，节点只存储所需要的路由，减少了内存需求；分组头不需携带路径，减少了路由分 组对信道的占用，提高了带宽利用率；能陕速向应活跃路径上的断链；具有良好的可扩展性。 对照理想路由协议标准，a o d v 协议主要还存在着以下不足【2 l 】：没有路由安全保护机制；不支 持存在单向链路的路由发现；没有支持设备睡眠操作等节能策略；周期性的广播h e l l o 分组以维 持路由，需消耗一定的能源和带宽；面向目的节点查找路由的方式，一定程度上限制了源节点发现 路由的能力。 2 3 2d s r 路由协议 d s r 四】是一种典型的按需驱动路由协议，不需要周期性的发送更新报文。协议还较好的支持主 机睡眠功能，节省了路由开销和电池能量，对于负载小的a dh o e 网络有较好的性能表现。协议的 另外一个优点是支持路由缓存和中间主机应答，有利于快速建立路由并在一定程度上减少泛洪报文 的开销。当然，缓存的引入会增加网络的开销，中间应答机制还会产生过时路由的问题。就整体陛 能而言，d s r 是比较成功的a dh o e 路由协议之一，在开销和时延及数据成功传输率等方面都有较 好的表现。 r 南京邮电大学硕士研究生学位论文 第二章a dh o e 网络路由协 义