（通信与信息系统专业论文）aodv协议本地修复和多路径路由的研究.pdf

摘要 摘要 a dh o c 网络( m o b i l ea dh o cn e t w o r k ，m a n e t ) ，是一种不依赖固定基础通信 设施的分布式多跳无线网络，具有组网灵活、搭建迅速、节点移动自由、抗毁性 强等优点，在军事和民用上都得到了广泛应用。但是，由于节点共享无线信道、 拓扑动态变化、安全性较弱等特点，给a dh o e 网络技术的研究提出了挑战。 本文主要针对a dh o c 网络拓扑快速变换导致链路中断的问题，对现有路由协 议进行深入研究，寻找路由失效时快速重建路由恢复通信的方法，达到降低数据 报文丢包率的目的。本文以a o d v 协议为基础，分别对本地修复和多路径备份两 个方面进行改进，提出新的路由算法a o d v n b 和a m p l r 。 a o d v n b ( a o d vn e i g h b o r - b a s e dp r o t o c 0 1 ) 针对本地修复中备份路由修复和被 动路由修复存在的不足，提出了一种分区域的混合修复算法：通过邻居信息维持 到达下两跳节点的小范围路由备份，实现域内快速修复；两跳范围外进行到达目 的节点的域外修复：同时引入先驱节点补充修复，提高路由修复几率。域内的两 跳备份路由修复解决了现有到达目的节点备份修复中备份路由实时性低、可靠性 有限的问题，同时避免了发送路由请求和等待路由应答的等待延迟，提高修复的 成功率，实现快速修复；域外修复通过t t l 延伸机制降低请求报文广播频率，减 少路由重建耗时。 a m p l r ( a o d vm u l t i p a t h sw i t hl o c a lr e p a i r ) 是一种节点不相关多路径备份路 由协议。a m p l r 针对多路径协议a o d v m 中路由隐藏、路由覆盖问题进行改进， 提高发现多路径的能力和维护多路径独立性的能力。a m p l r 提出双向路由修复算 法，修复后的路由可以继续作为备份路由使用，降低路由请求频率，同时修复后 的路由可以用于转发缓存在发现断路节点的数据报文，达到降低数据报文丢包率 的目的。 本文在o p n e t 仿真平台上实现a o d v n b 和a m p l r 的仿真。在多种网络场 景下，通过a o d v n b 与a o d v 、i m p r o v e da o d v 协议性能进行比较，证明 a o d v n b 能够在网络拓扑变化较快时降低数据报文端到端延迟和丢包率，得出 a o d v n b 适用于拓扑快速变化场景的结论。通过a m p l r 与a o d v 、a o d v m 协 议性能进行比较，证明a m p l r 协议性能与节点密度密切相关，并且在网络拓扑 变化较快时有效降低控制报文开销和提高数据报文递交率，得出a m p l r 协议适 摘要 用于节点密度较大、拓扑变化较快的网络场景。 关键词：a o d v 协议，a o d v n b ，a m p l r ，路由修复，多路径备份 a b s t r a c t a b s t r a c t m o b i l ea dh o cn e t w o r k si sad i s t i l b u t e d - c o n t r o la n dm u l t i h o p sn e t w o r kw i t h o u t s p e c i f i cf i x e dc o m m u n i c a t i o nf a c i l i t i e s s i n c et h ea d v a n t a g e so fi n d e p e n d e n c eo f f i x e d f a c i l i t i e sa n dr o b u s ts t a b i l i t y ，i ti sw i d e l ya d o p t e db o t hi nm i l i t a r ya n dc i v i la f f a i r s b e c a u s et h en o d e ss h a r et h ew a r l e s sc h a n n e l ，t h en e t w o r kt o p o l o g yc h a n g e sr a p i d l ya n d t h el i n k - l a y e ri sn o ts e c u r i t ye n o u g h ，a dh o cn e t w o r kf a c em a n yc h a l l e n g e s t h i sd i s s e r t a t i o nf o c u so nt h el i n kf a i l u r ep r o b l e md u et ot h er a p i dc h a n g eo f t o p o l o g y ，t r yt of r e dam e t h o dt or e c o v e rt h ef a i l e dr o u t eq u i c k l yw h i c hc o u l dd e c r e a s e t h ep r o b a b i l i t yo fd a t ap a c k e t sl o s s t h i sd i s s e r t a t i o nb a s e so nt h ea o d vp r o t o c o l ， p r o p o s et w on e wp r o t o c o l ：a o d v n b ( a o d vn e i g h b o r - b a s e dp r o t o c 0 1 ) a n da m p l r ( a o d vm u l i t p a t h s 、丽ml o c a lr e p a i r ) a o d v n bt a k i n gt h ea d v a n t a g e so fp a s s i v el o c a lr e p a i ra n db a c k u pl o c a lr e p a i r ， b r i n go u tan e w m i x e dr e p a i r - m e c h a n i s m 。i ns m a l la r e a , i tt a k e sb a c k u pr o u t et or a p i d r e p a i r ；w h e nb a c k - u pr e p a i rf a i l ，i te m p l o yt h et t l e x t e n s i o nm e c h a n i s mt od e c r e a s e t h ed e l a yo fr o u t er e b u i l d p r e c u r s o r sr e p a i rh a sa l s ob e e ni n t r o d u c e di nt h i sa l g o r i t h mt o e n h a n c et h i sp r o t o c 0 1 t h ei n t r a - a r e ab a c k - u pr e p a i rs o l v et h er e l i a b i l i t yp r o b l e mo f p r e s e n tp r o t o c o l ，i ta l s ov o i dt h ed e l a yo ft h er o u t er e q u e s ta n dr e p l y ，r e a l i z et h er a p i d r o u t er e p a i r t h ee x t r a - a r e ar e p a i re x t e n dt h et t lo fr r e qa c c o r d i n gt ot h en e i g h b o r s i n f o r m a t i o n ，c o n t r o lt h eo v e r h e a da n dd e c r e a s et h ed e l a yo ft h er e p a i rt od e s t i n a t i o n a m p l ri san e wn o d e - d i s jo i n tm u l i t - p a t hp r o t o c 0 1 i ts o l v et h ep r o b l e mi nt h e r o o t i n gd i s c o v e rp h a s e a n dm a i n t a i np h a s ei na o d v mi n s p e c t i v e ，i m p r o v et h e c a p a b i l i t yo ft h em u l t i - p a t h sd i s c o v e r ya n dm a i n t e n a n c e t h e r ei sa n o t h e rl o c a lr e p a i r a l g o r i t h mi si n c l u d e di na m p l ra c c o r d i n gt ot h em u l t i p a t h - r o u t i n gc h a r a c t e r i s t i c s t h er e p a i r e dr o u t ec a nb eu s e da sb a c k u pr o u t e ，t od e c r e a s et h ef r e q u e n c yo fr o u t e d i s c o v e r y ；i ta l s oc a nu s et h er e p a i r e dr o u t et of o r w a r dt h ed a t ap a c k e t s ，s oi td e c r e a s e t h ep r o b a b i l i t yo fd a t ap a c k e t sl o s s t h i sp a p e rh a sr e a l i z e dt h es i m u l a t i o no fa o d v n ba n da m p l ro no p n e t s y s t e m s i m u l a t i o n p l a t f o r m u n d e r d i f f e r e n tn e t w o r ke n v i r o n m e n t s ，w i t ht h e i i i a b s t r a c t c o m p a r i s o no f t h ep e r f o r m a n c eo ft h et r a d i t i o n a la o d vp r o t o c o la n dr e l a t e d r e s e a r c h e s ，t h es i m u l a t i o nr e s u l tv e r i f yt h ep e r f o r m a n c ei m p r o v e m e n to ft h e s et w o p r o t o c o l s k e yw o r d ： a d h 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 g ，a o d v n b ，l o c a lr o u t e r e p a i r ，a m p l r ，m u l t i - p a t hr o u t i n g i v 缩略语 缩略语 a o d v a d h o co n d e m a n dd i s t a n c e v e c t o rr o u t i n g a o d v - b r a o d v - b a c k u pr o u t i n g 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 e - v e c t o rr o u t i n g d s r m - a n e t a o d v m a o m d v 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 m o b i l ea dh o c n e t w o r k i n g a o d v - m u l i t p a t h a dh o co n - d e m a n d m u l t i p a t hd i s t a n c ev e c t o r m n h m u l t i p l en e x th o p sr o u t i n gp r o t o c o l o l s r i u 冱q r r e p i 也r r z i 心 o p t i m i z e dl i n ks t a t er o u t i n g r o u t er e q u e s t r o u t er e p l y r o u t ee r r o r z o n er o u t i n gp r o t o c o l x 按需距离矢量路由 协议 按需距离矢量的后 备路由协议 目的序列距离矢量 路由协议 源路由协议 移动自组织网络 多路径a o d v 协议 按需距离矢量路由 协议 多重下一跳路由协 议 最优链路状态路由 协议 路由请求 路由应答 路由错误 域路由协议 图目录 图1 1 图2 1 图2 2 图2 3 图3 1 图3 2 图3 3 图3 4 图3 5 图3 - 6 图3 7 图3 8 图3 - 9 图3 1 0 图3 1 l 图3 1 2 图3 1 3 图3 1 4 图3 1 5 图3 1 6 图3 1 7 图3 1 8 图3 1 9 图3 2 0 图3 2 1 图3 2 2 图3 2 3 图3 2 4 图3 2 5 图4 1 图4 2 图4 3 图4 4 图4 5 图4 6 图4 7 图目录 无线网络协议分类2 到下两跳地址的本地修复l o a o d v - b r 备份路由l l 多路径路由分类1 3 备份路由过期示意图18 h e l l o 消息通告邻居信息示意图1 9 域内备份修复示意图2 0 先驱节点修复示意图2 l t t l 延伸示意图2 2 发现断路节点修复和先驱节点修复示意图2 3 a o d v n b 协议h e l l o 报文2 7 a o d v n b 邻居表2 7 邻居通告滞后问题2 8 a o d 、i b 路由发现过程2 9 a o d v n b 路由回复过程3 0 路由修复流程图3 0 域内修复时报文交互过程3 1 域外路由修复时报文交互3 2 a o d v n b 路由表3 3 a o d v n b 中r r e q 报文格式3 4 a o d v n b 中rr r e q 报文格式3 5 a o d v n b 中砒也p 报文格式3 5 m a n n e ts t a t i o n 节点模型3 8 i p进程模块38dispatch a o d vr t e 进程模块3 9 2 0 个移动节点随机分布场景4 0 2 0 个节点场景数据报文递交率、延迟和控制报文开销4 2 3 0 个节点场景数据报文递交率、延迟和控制报文开销4 4 4 0 个节点场景数据报文递交率、延迟和控制报文开销4 6 多路径中路由隐藏问题4 9 a m p l r 路由发现过程5 0 多路径中路由覆盖问题5 1 本地修复时多路径独立性问题5 3 单向修复问题5 4 双向修复示意图5 5 路由表格式5 7 v 图目录 图4 8 图4 - 9 图4 1 0 图4 1 1 图4 1 2 图4 1 3 图4 1 4 图4 1 5 图4 1 6 图4 1 7 路由请求表格式5 7 a m p l r 中r r e q 报文格式5 8 中间节点处理r r e q 流程5 9 a m p l r 中r r e p 报文格式6 0 r r e p 回复流程。6 0 a m p l r 修复报文格式6 3 r e r r 报文格式6 4 a o d vr t e 进程6 5 2 5 个节点场景数据报文延迟、递交率和控制报文开销6 8 5 0 个节点场景数据报文延迟、递交率和控制报文开销7 0 v i i i 表目录 表3 表3 表4 表4 表目录 仿真场景设置4 0 协议相关参数设置4 0 a m p l r 场景设置6 6 m p l r 设置相关参数6 7 i x 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作 及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为 获得电子科技大学或其它教育机构的学位或证书而使用过的材料。与 我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的 说明并表示谢意。 签名： 关于论文使用授权的说明 r r1 3e l 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘， 允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文的全 部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描 等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：丝! 堂筮 导师签名：璧兰盘 日期渺产，月f 弓日 第一章绪论 1 1 研究背景 第一章绪论 无线自组织网( 又称为a dh o c 网络) 是一组具有路由功能的节点组成的分布 式无线多跳网络。无线自组网作为一种新的组网方式，可以在任何时刻、任何地 点不需要硬件基础网络设施的支持，快速构建起一个移动通信网络，具有较高的 独立性。同时无线自组织网是一个分布式网络，网络中单个节点的失效不会影响 整体网络的数据传输，具有较强的抗毁性和健壮性。由于无线自组网在快速组网、 节点移动组网等方面的应用不可代替，对无线自组网的研究已经成为移动通信技 术研究的热点。 同时，无线自组织网面临着许多特有的问题：节点的自由移动或失效常常使 链路不稳定，导致网络拓扑动态变化；无线带宽资源有限，由于信号衰减、噪声 干扰、信号碰撞等因素的影响，有效带宽进一步减小；无线传输导致链路层容易 受到攻击，安全性较弱等。近年来，学者为了提高链路利用率、高效安全使用无 线资源，分别在网络架构、m a c 技术、路由技术等方面做的大量分析研究，取得 了一定的研究成果。 本文主要针对无线自组织网拓扑动态变化导致链路中断的问题进行分析研 究，提出相应的路由改进算法，达到特定网络环境中降低数据丢包率和端到端延 迟的目的。 1 2 无线自组织网的路由协议概述 由于无线自组织网中节点的传输范围有限，源节点在向目的节点发送数据时， 需要其他节点辅助传输数据，因此路由技术成为无线自组织网中非常重要的部分。 本节主要介绍现有无线路由协议的分类和典型的路由协议。 1 2 1 路由协议分类 目前存在数十种a dh o e 网络路由协议，可以从不同的角度进行分类【3 】。按是 否使用g p s ( g l o b a lp o s i t i o ns y s t e m ) 系统划分，可以分为地理定位辅助路由与 电子科技大学硕士学位论文 无地理定位辅助路由：按路由查找策略划分，可分为反应式路由( 又称被动路由 或者按需路由) 、先应式路由( 又称主动路由) 和混合式路由：按网络逻辑视图划分， 可分为分级路由和平面路由。图1 - l 表示了a dh o c 网络按照查找策略划分的三类 路由协议。 d s d v o l s rf s rd s ra o d v t o r az r pc g s rh s r 图卜l无线网络协议分类 1 先应式路由 先应式路由又称为表驱动( t a b l ed r i v e n ) 路由。其路由发现策略与有线网络 路由协议相似，网络中各个节点维护到其它所有节点的路由信息。节点通过周期 性广播通告报文交换路由信息，主动发现路由。同时，节点实时维护和更新到达 全网所有节点的路由。先应式路由的优点是节点掌握全网的拓扑信息，当节点需 要发送数据报文时，只需要查询路由表中到达目的节点的表项，即可转发报文， 路由时延小。缺点是维护全网的路由信息需要花费较大的开销，并且拓扑结构的 快速变化可能导致路由协议始终不能完全收敛。典型的先应式路由协议有d s d v 【5 】 ( 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 e v e c t o rr o u t i n g ) 、o l s r 6 1 ( o p t i m i z e dl i n ks t a t e r o u t i n g ) 、t b r p f l7 。( t o p o l o g yd i s s e m i n a t i o nb a s e do nr e v e r s e - p a t hf o r w a r d i n g ) 等。 2 反应式路由 反应式路由又称按需( o nd e m a n d ) 路由，仅在需要路由时才由源节点发起路 由请求，路由表项是按需建立的，仅仅是整个网络拓扑的一部分信息。节点在通 信过程中维护路由表项，通信完毕后不再继续进行维护。反应式路由协议由于不 需要周期性的广播路由信息，节省了一定的无线带宽资源和节点能量；但是节点 在发送数据报文时，如果路由表中没有通往目的节点的相关表项，路由发现会带 来较大的时延。反应式路由协议主要有d s r 9 1 0 1 ( d y n a m i cs o u r c er o u t i n g ) 、 a o d v t l1 】【1 2 1 ( a dh o co n - d e m a n dv e c t o rr o u t i n g ) 等。 3 混合式路由 混合式路由协议结合了反应式路由和先应式路由的优点，把节点划分为不同 2 第一章绪论 的域，对域内域外的节点指定不同的功能，其主要目的有两个：一是减少参与路 由计算的节点数，减少节点路由表的大小，降低维护路由表所需的内存开销和交 换路由信息时需的通信开销；二是通过分域的策略，在域内产生一个较稳定的拓 扑区域，减少拓扑结构变化对路由协议带来的影响。典型的混合路由协议有z r p 1 3 】 ( z o n er o u t i n 【gp r o t o c 0 1 ) 、h s r 1 4 ( h i e r a r c h i c a ls t a t er o u t i n g ) 、c g s r 1 5 ( c l u s t e r h e a d g a t e w a ys w i t c hr o u t i n g ) 等。 1 2 2 几种典型的路由协议 1 最优化链路状态( 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 ，o l s r ) 协议是表驱动，主 动式路由协议，通过有规律地与网络中其他节点交换拓扑信息，达到掌握网络拓 扑的目的【羽。每个节点从其邻节点中选择一组节点作为“多点中继( m u l t i p o i n t r e l a y ，m p r ) ，降低链路状态通告时的控制报文开销。 o l s r 协议周期性的交互邻居信息，通过h e l l o 消息的交互保证每个节点掌 握本地链路信息。通过缩短发送控制消息的最大间隔时间来优化对o l s r 协议对 拓扑变化的反应。同时，o l s r 会发送全网的拓扑信息，用于保证每个节点正确掌 握拓扑信息。o l s r 连续维护到达网络中所有目的节点的路由，有利于多个大节点 子集之间的通信。o l s r 协议适用于规模大密度高的网络，在链路状态感知和链路 优化方面表现较好。 2 动态源路由协议( d s r ) 【9 】1 1 0 】 源动态路由协议( 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 ，d s r ) 得路由发现机制和 路由维护机制均是完全按需发起的。d s r 不依靠任何周期性的路由广播分组、链 路状态检测分组或者邻居节点探测分组来通告邻居信息，而且d s r 对于当前正在 使用的路由是否影响网络拓扑变化也并不关心。 d s r 路由协议使用“源路由的思想，所发送的每个数据报文携带其将要通 过的一个完整的、按序列排列的节点序列。在d s r 协议中采用储存旁听路由信息， 即任何一个转发节点或者是旁听到一个分组的节点都要把分组中所有可用的路由 信息添加到自己的路由表中，在一条路由失效的时候，源节点可以使用旁听的路 由，或者是重新发起路由发现过程。即d s r 协议通过旁听可以储存到达目的节点 的备用路由，因此在路由本地快速修复方面有比较好的表现。 3 按需距离矢量路由协议( a o d v ) 【1 1 】【1 2 】 电子科技大学硕士学位论文 按需距离矢量路由协议( a d h o co n d e m a n dd i s t a n c ev e c t o rr o u t i n g ) 中，当 有数据分组需要发送但没有可用的路由时，源节点广播一个路由请求( r r e q ) 分 组，其邻居节点收到广播后继续转发该g g f q ( 丢弃重复的对汪q ) ，依此类推， 直到目的节点或具有能够到达目的节点最新路由的中间节点收到该g g e q 为止， 然后由目的节点或拥有到达目的节点的中间节点向源节点发送路由回复( 砌也p ) ， 完成路由建立。a o d v 利用序列号来确保所有的路由没有环路，并保证中间节点 只应答最新的信息。 a o d v 使用的广播发现路由的方式代替了d s r 中的源路由方式，使用中继节 点的动态路由表来转发数据。对于规模较大的网络，每个数据报文不需要携带源 路由的信息，只需通过查找目的节点和目的节点序号，即可找到到达目的节点的 最新路由，因此比d s r 协议节约了控制报文开销。a o d v 协议发现链路中断时， 不需要有源节点发起路由重建，而是在发现断路节点发起本地修复，某些情况下 可以降低报文端到端延迟和丢包率。 4 域问路由协议( z i 冲) 1 3 1 域问路由协议( z o n er o u t i n gp r o c o t 0 1 ) 是混合路由协议，一方面，节点在相 邻的较小区域内使用先应式路由协议，每个节点通过先应机制维护到达附近邻居 节点的路由；另一个方面，当需要搜索的目的节点不在邻居内时，则发起到达源 节点的源路由，而不需要掌握整个网络的拓扑信息。 在z r p 中，节点主动维护到达本地相邻区域内的目的节点的路由，这个本地 相邻区域叫做路由选择域。z r p 以跳数定义路由选择域的半径，而不是物理上的 传输距离。节点通过本地主动方式获得路由选择域的拓扑结构，称为域内路由协 议( i n t r a z o n er o u t i n gp r o t o c o l ，i a r p ) 。而对于域外的节点，采用了基于返洪的 查询应答机制。作为混合路由协议，z r p 协议比较好的结合了先应式协议和反应 式协议的优点。 1 3 本文的研究内容和目标 本文针对自组网拓扑快速变化和链路不稳定导致数据报文丢失的问题进行分 析，研究了现有的本地修复策略和多路径备份机制的研究成果，以a o d v 协议为 基础，设计两种新的路由协议a o d v n b 和a m p l r ，期望到达网络拓扑快速变化 时降低数据报文丢包率的目的。 a o d v n b ( a o d vn e i g h b o r - b a s e dp r o t o c 0 1 ) 协议主要对单径路由中链路中断 4 第一章绪论 时的本地路由修复策略进行研究，分析了现有分区域修复机制和备份路由修复机 制的优点和不足，提出一种在发现断路节点进行域内备份路由修复、域外被动路 由修复，在先驱节点进行补充路由修复的本地修复策略，期望达到快速修复失效 链路，降低数据报文丢包率和端到端延迟的目的。 a m p l r ( a o d vm u l t i p a t h s 晰t hl o c a lr e p a i r ) 协议针对现有节点独立多路径 协议a o d v m 中存在的路由隐藏和路由覆盖问题，改进了多路径的路由发现和路 由维护机制，提高了多路径的发现能力，降低了拓扑变化对多路径独立性的影响。 同时a m p l r 引入双向路由修复机制，通过抢救缓存在发现断路节点数据报文达 到降低丢包率的目的。a m p l r 协议通过建立多条备份路由减少路由重建次数，期 望达到提高数据报文递交率和降低控制报文开销的目的。 本文在o p n e t 仿真平台上分别实现了a o d v n b 和a m p l r 协议，并通过多 个场景的仿真对比，验证改进后协议的性能和适用场景。本文设计了新的路由修 复算法( a o d 呵b ) 和多路径备份路由算法( a m p l r ) ，分别针对路由修复和多 径路由中存在的问题设计了相应的解决方案，为移动a dh o e 网络中某些应用和网 络性能的改进提供重要的参考和依据。 1 4 章节安排 本论文的章节安排如下： 第一章介绍了无线自组织网络的特点和不足，路由协议的分类和典型的路由 协议，以及课题的背景，目的和任务。 第二章分析了a o d v 协议及相关研究。主要包括两方面内容：本地修复策略 和基于a o d v 的多路径协议。首先介绍了a o d v 本地修复策略及现有的改进算法， 分析了各种本地修复机制的优缺点和适用场景：然后介绍了基于a o d v 协议的三 种典型多路径协议，分析了各种协议的特点和存在的不足，为以后章节打下基础。 第三章首先分析了现有分区域修复协议i m p r o v e da o d v 和备份路由修复协议 a o d v - b r 中存在的问题，提出了基于邻居信息的分区域本地修复算法a o d v n b 。 并通过仿真验证协议性能和适用场景。 第四章首先分析现有节点独立多路径备份协议a o d v m 中路由隐藏和路由覆 盖的问题，提出相应的解决方案；然后提出保持路径独立性的双向路由修复机制。 最后提出了带本地修复的节点独立多路径备份协议a m p l r ( a o d vm u l t i p a t h s p r o t o c o lw i t hl o c a lr e p a i rm e c h a n i s m ) ，并通过仿真验证协议性能和适用场景。 电子科技大学硕士学位论文 第五章对全文进行总结。 6 第二章a o d v 路由协议及研究现状 第二章a o d v 路由协议及研究现状 a o d v 协议是本文的研究基础。本章介绍了a o d v 协议以及相关研究成果， 深入分析了现有本地修复机制和多路径备份机制的优点和不足，为本文对a o d v 协议的改进打下基础。 2 1a o d v 路由协议概述 a o d v 协议作为平面a dh o c 中的反应式路由协议之一，由于路由开销小，实 现简单，协议性能优秀，一直是a dh o c 网络路由协议研究的重点。 2 1 1a o d v 协议基本思想 a o d v 是一个按需的路由协议，它根据业务需求建立和维护路由。在a o d v 协议中，如果有数据报文要发往目的节点并且没有相关路由表项，就会启动路由 发现过程：源节点广播一个路由请求分组( r r e q ) ，收到请求分组的节点根据 r r e q 中的信息，建立到达源节点的路由( 称为“反向路由”) 。如果该节点不存在 到达目的节点足够新的路由，继续广播r r e q ；如果该节点存在到达目的节点足够 新的路由，或者该节点就是目的节点，则通过单播方式发送路由应答分组( 砒汪p ) 给源节点。r r e p 沿着刚刚建立的反向路由向源节点传送。在此过程中，收到r r e p 的节点建立到达目的节点的路由( 称为“正向路由”) 。当r r e p 到达源节点后， 即建立了源节点到达目的节点的双向路由。 路由表项建立后，路由中的每个节点都要维护、管理路由表。在维护路由表 的过程中，当路由无效时，节点会从路由表中删除相应的表项。同时，节点会监 视活动路由中下游节点的状况，当发现链路断开时，会根据发现断链的位置判断 是否发起本地路由修复，或向上游节点发出路由错误分组( r e r r ) ，通知上游节 点到达某目的节点的路由失效。 2 1 2a o d v 协议中的关键技术 a o d v 协议通过三种关键技术保证协议性能，分别是“目的节点序列号”技 7 电子科技大学硕士学位论文 术、h e l l o 消息机制、扩展环搜索技术。 a o d v 借鉴d s d v 协议中“目的节点序列号 保证获取的路由信息最新，同 时避免路由环路。节点收到一条消息，首先比较其中的目的节点序列号与自己知 道的该节点的序列号：如果前者大，说明收到的消息比自己了解到的关于目的节 点的信息更新，能反应最新的网络情况，更新自己已知的路由表；反之，收到的 消息已经过时，不进行处理。a o d v 协议利用了目的节点序列号确保了所有路径 都不存在环路和所有路由信息都最新，同时避免了传统距离矢量路由算法中存在 的无穷计数问题【l 7 1 。 a o d v 可以采用h e l l o 消息机制进行链路连通性管理。正在进行通信的节点 在一段时间内如果没有发送任何数据，就主动在自己通信范围内广播一个消息， 通知邻居节点自己的存在，这个消息称为“h e l l o ”消息；收到h e l l o 消息的 节点更新相应邻居节点的生存期，如果h e l l o 消息来自一个新的邻居，则在邻居 列表中增加一个邻居记录：节点周期行的检测邻居节点的有效性，若在连续的几 个h e l l oi n t e r v a l 时间内未收到某邻居节点的任何消息，那么该节点认为到 达这个邻居节点的链路中断。 a o d v 协议在进行路由请求时会广播路由请求报文( r r e q ) 。如果r r e q 中 生存期( t t l ) 较长，则r r e q 广播范围较大，导致控制报文在不必要的范围传 播，增加控制报文开销；如果生存期较短，广播范围较小，不能送达目的节点， 导致路由建立失败。为了有效的控制报文开销，同时满足建立路由的目的，a o d v 协议引入了扩展环搜索技术。 在扩展环搜索中，发起者节点在r r e q 报文的口头中最初使用的t t l 值为 t t ls t a r t ，并将接收r r e p 的超时时间设置为n e tt r a v e r s a lt i m e 微秒。 如果r r e q 超时而没有一个对应的r r e p ，发起者再一次广播r r e q ，此时t t l 值增加t t li n c r e m e n t 。如此过程进行反复，直到r r e q 中t t l 的直到达了生 存期门限( t t lt h i 迮s h o l d ) ，超过这个值之后的每一次尝试t t l 值都使用 t t ld e a m e t e r 。通过扩展环搜索技术，有效的减少了路由请求或路由修复时 r r e q 报文的发送，降低了协议控制报文开销。 2 2a o d v 协议中的修复策略 a o d v 协议在路由维护过程中，当链路中断时，将采用本地修复策略快速恢 复路由。由于发现断路节点比源节点更接近目的节点，本地修复时控制报文开销 8 第二章a o d v 路由协议及研究现状 更小、路由重建延迟更低。为了更好的提升a o d v 协议的性能，学者在本地修复 方面做了大量研究，取得了一定成果。 2 2 1a o d v 本地修复 在a o d v 协议中，当一条活动路由发生中断的时候，如果链路中断处离目的 节点距离不大于最大修复跳数，那么链路中断处的上游节点可以选择修复这条路 由【l l 】。 为了避免源节点重新发起路由请求，发现断路节点增加目的节点序列号，然 后广播关于目的节点的r r e q 。当中间节点存在到达目的节点足够新的路由，或者 目的节点收到r r e q 后，回复r r e p 报文。当r r e p 报文到达发现断路节点时， 即可建立到达目的节点的新路由。由于发现断路节点比源节点距离目的节点更近， 因此本地修复能降低路由重建延迟，减少控制报文开销。 对路由中的链路中断进行本地修复有时候会导致到目的节点的路径长度增 加。a o d v 协议为了避免路由因本地修复导致长度不断增加的情况，规定当修复 后的路由长度大于原路由长度时，可以由源节点发起到达目的节点的路由修复( 源 修复) 。但是不要求源节点一定要重建这条路由，因为源节点很可能已经结束或者 即将结束数据会话。 2 2 2a o d v 本地修复改进 a o d v 协议本地修复策略降低了链路中断时路由重建延迟，减少了路由请求 开销，众多学者也在a o d v 协议基础上提出多种修复改进方法，提高a o d v 协议 在不同网络拓扑中的性能。本地修复主要分为三类：被动路由修复、备份路由修 复和链路预测修复。 2 2 2 1 被动路由修复 被动路由修复指当节点发现链路失效后才发起路由修复。a o d v 协议的本地 修复方法就属于被动路由修复范畴。很多学者在a o d v 原修复方法基础上进行改 进，主要集中在两个方面：一是修复范围的控制；二是修复位置的选择。 ( a ) 修复范围控制【1 8 】【1 9 】【2 0 】【2 1 】 当节点发现到下一跳节点的链路中断时，节点会发送到失效路由目的节点的 路由修复请求。但是当修复节点到目的节点距离比较远的时候，会造成本地修复 的控制开销较大、时延比较长的问题。文献 1 8 】通过研究发现，当链路失效时影响 9 电子科技大学硕士学位论文 的范围往往是局部的，为了降低修复延迟和控制报文开销，提出一种到达失效路 由中下两跳地址的修复算法一i m p r o v e d _ a o d v 。 r 印n i r _ _ r r e q - + r e p a i r _ r r e p 一一卜 图2 一l到下两跳地址的本地修复 如图2 1 所示，当节点a 发现a b 链路失效后，首先发起到下两跳节点c 的 路由请求，如果超时未收到c 回复的r r e p ，在发起到达目的节点的路由修复作为 补充。i m p r o v e d 协议限制了路由本地修复的范围，缩短了修复的时延。如aodv 果两跳范围修复成功率不高，路由修复延迟和控制报文开销不但没有降低，反而 由于两跳范围修复的失败而增加了。因此这种改进方法只适合于节点密度较大的 网络拓扑。 文献【2 0 f 2 1 】针对修复范围进行讨论，通过仿真实验验证当修复范围在2 3 跳 时，控制报文开销与修复成功率的性价比最高，修复性能最好，从另一个方面验 证了小范围修复的正确性。 ( b ) 修复位置选择【2 2 1 【2 3 1 a o d v 协议中的本地修复往往由发现断路的节点发起，如果修复失败，通知 失效路由的源节点，发起源修复。这种方法直接剥夺了发现断路节点到源节点之 间的中间节点进行修复的机会。如果修复失败后，由发现断路节点到源节点之间 的中间节点发起修复，因为距离目的节点更近，路由修复的代价和延迟小于源修 复。 文献