（计算机应用技术专业论文）无线mesh网络路由技术的研究.pdf

f h 删j l l l i i l l i f 1 1 1 0 y 1759。rl8 , l l l l , i 9 r n l l u5ll i l l l 独创性( 或创新性) 声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或其他 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示了谢意。 申请学位 本人签名 处，本人承担一切相关责任。 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即： 研究生在校攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借 阅；学校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它 复制手段保存、汇编学位论文。( 保密的学位论文在解密后遵守此规定) 保密论文注释：本学位论文属于保密在一年解密后适用本授权书。非保密论 文注释：本学位 本人签名： 导师签名： 适用本授权书。 日期：丝应盗星星! 墨堡 日期：叫q 血弛虬 i i a b j b , i - 1 隆 、 j 量塞邮电太堂亟硒究生堂僮i 金塞玉线璺h 圆终路由技丕的硒塞 无线m e s h 网络路由技术的研究 摘要 无线m e s h 网络是一种新型的无线网络，它是由无线链路、路由器 和终端设备组成。它有着多跳、自组织、自愈、高容量、高速率特点， 具有很好的应用前景。路由协议研究是目前无线m e s h 网络研究的一大 热点。本文主要研究m e s h 网络的路由技术。 论文针对目前的常用于按需路由协议中的节点时延统计方法的 缺点，提出一种综合考虑业务分组通过节点的时延以及节点中的队列 长度动态来进行节点的时延估计，这样能够更准确的估计出当前的节 点时延状况。并通过应用于已有的一种基于时延控制的按需式路由协 议( a o d c ) 来验证本节点时延统计算法的实用性。通过仿真，比较改 进后的路由协议a o d ci m p r o v e 和a o d c 的平均端到端时延以及网络丢 包率和吞吐量。经过仿真可以看到应用本节点时延统计算法的路由协 议a o d ci m p r o v e 在平均端到端时延、丢包率和吞吐量都有一定得改 蓥 仁了0 论文还针对于一些对端到端时延要求较高的并且业务量较大的 业务，设计了一种基于节点时延以及链路最小负载度的综合控制的一 种路由协议。该路由协议是基于a o d v 路由协议进行优化的，在寻路 的过程中，通过节点的时延来控制路由请求分组的转发速度，同时在 目的节点中最先到达的前几个请求分组中，选择所经过的路径中节点 韭塞韭虫太堂亟硒究生堂僮论塞 玉线曼h 圆终路由拉盔的硒究 负载度最小的一条链路作为路由。这样能够较好实现负载均衡，有效 的减小网络的端到端时延并且提高网络的吞吐量。通过仿真可以看 到，本协议在平均端到端时延、丢包率和网络吞吐量三个性能上和 a o d v 以及d l a r 路由协议相比，都有一定的改善。 关键字：节点时延节点负载时延控制负载均衡 l - _ 、 、 t 。 ： - 吖 眠 e j 匕塞邮虫太堂亟班究生堂僮i 金塞 玉线墨h 匦络路由技苤的研究 r e s e a r c ho nw i r i ，e s s 匝s hn e t w o r k r o u t 【n gt e c h n o l o g y a b s t r a c t w i r e l e s sm e s hn e t w o r kw h i c hi sc o m p r i s e do fw i r e l e s sr o u t e ra n d t e r m i n a le q u i p m e n ti san e wk i n do fw i r e l e s sa c c e s sn e t w o r k , w i t h m u l t i h o p ，s e l f - o r g a n i z a t i o n ，s e l f - h e a l i n ga n dh i g hc a p a c i t ya n dd a t er a t e ， i th a v eap r o m i s i n gf u t u r e t h er o u t i n gp r o t o c o lr e s e a r c hi so n eo ft h e m o s tp o p u l a rt o p i ci nw i r e l e s sm e s hn e t w o r kr e s e a r c h t h er o u t i n g t e c h n o l o g yw o u l db ed i s c u s s e di nt h i sp a p e r a c c o r d i n gt ot h ew e a k n e s so ft h ec u r r e n tr o u t i n gp r o t o c o l sb a s e do n d e m a n d i n g ，t h i sp a p e rp r o p o s e sam e t h o dw h i c hi sb a s e do na l li n t e g r a t e d s e r v i c ep a c k e td e l a ya n dq u e u el e n g t ho fn o d et on o d e i tc a n d y n a m i c a l l y e s t i m a t et h et i m e - d e l a yi no r d e rt oe s t i m a t et h ec u r r e n tn o d ed e l a y t h i s p a p e ru s e st h er o u t i n gp r o t o c o l ( a o d c ) b a s e do nd e l a y - d e m a n dt oc h e c k t h ep r a c t i c a b i l i t yo ft h ea l g o r i t h m t h ea v e r a g ee n dt oe n dd e l a ya n d n e t w o r kp a c k e tl o s sr a t ea n dt h r o u g h p u to ft h ea o d c _ i m p r o v ea n d a o d cr o u t i n gp r o t o c o l sa r es h o w ni nt h es i m u l a t i o na n dc o m p a r e s i o n a f t e rt h es i m u l a t i o n ，i tc o u l db ec o n c l u d et h a tt h ep r o p o s e d p r o t o c o ll e a d s i m p r o v e m e n to f t h ea v e r a g ed e l a y ，p a c k e tl o s sr a t ea n dt h r o u g h p u t m j e 塞邮电太堂亟班荭生堂僮i 金塞 玉绔韭圆络蹬由拉苤的班究 s o m el a r g ev o l u m eo fs e r v i c ed e m a n d se n dt oe n dd e l a y a i m p r o v e dr o u t i n gp r o t o c o lw h i c hi sb a s e do nn o d e - b a s e dd e l a ya n dt h e m i n i m u mc o n s u m eo fl i n ki sp r o p o s e d t h i sn o v e lp r o t o c o lc o n t r o lt h e s p e e do fr o u t er e q u e s tp a c k e t st h r o u g hn o d e - b a s e dd e l a y i ts e l e c t st h e l i n kw i t hm i n i m u mc o n s u m eo fn o d ea sr o u t ef r o mt h ef i r s t r e q u e s t s a r r i v i n gt ot h ed e s t i n a t i o nn o d e ，w h i c hc a l la c h i e v eb e t t e rl o a db a l a n c i n g ， d e c r e a s et h ee n dt oe n d d e l a y a n di n c r e a s en e t w o r kt h r o u g h p u t c o m p a r e dw i t ha o d va n dd l a ri nt h es i m u l a t i o np a r t ，t h ep r o p o s e d p r o t o c o lg i v e st h eh i g h e rt h r o u g h p u ta n dl o w e ra v e r a g ed e l a y , p a c k e tl o s s r a t et h a nt h eo t h e r s k e y w o r d ：n o d ed e l a y ，l o a do nt h en o d e ，d e l a yc o n t r o l ，l o a d b a l a n c i n g i v p 0 2 1 2 无线m e s h 网络的特点7 2 1 3 无线m e s h 网络与其他无线网络的比较8 2 1 4 无线m e s h 网络路由协议的分类9 2 2 经典的无线m e s h 网络的路由协议的简介1 0 2 2 1d s r 路由协议1 l 2 2 2 瞻d v 路由协议l l 2 2 3w r p 路由协议一1 2 2 2 4a o d v 路由协议。1 3 2 3 本章总结。2 3 第三章一种适用于无线m e s h 网络按需路由的节点时延估计的统计算法设计 3 1 问题的提出2 4 3 2 节点时延估计算法实现。2 6 3 2 1 新的节点时延估算的计算方法2 8 3 2 2 算法验分析2 9 3 3 基于新的节点时延估计算法的路由协议性能仿真3 3 3 3 1 新路由协议的简单设计方法3 3 3 3 2 仿真场景设置3 4 3 3 3 仿真结果及分析。3 4 3 4 本章小结3 9 第四章基于节点时延以及节点负载控制的路由协议 4 1 问题的提出4 0 4 2t la o d v 路由协议4 l 4 2 1t l _ a o d v 路由协议描述。4 l 4 2 2t l _ a o o v 路由协议的实现4 6 4 3t la o d v 路由协议的仿真以及性能分析4 9 4 3 1 仿真场景设置4 9 4 3 2 仿真结果4 9 4 3 2 仿真性能分析5 3 4 a 本章小结5 4 第五章本文总结与未来展望 v 一，_执 ，“ 、 l 参考文献 致谢 攻读学位期间发表的学术论文目录 v i 5 8 6 0 6 0 _ t i f j f、。 v “ - 1 1 研究背景 第一章绪论 近年来，随着无线通信技术的高速的发展，传统的无线网络在为用户提供语 音接入方面获得了巨大的成功。无线网络发展的下一步目标是为用户提供更高的 传输速率，以便支持各种宽带业务的接入，特别是高速因特网业务的接入。 蜂窝移动通信 q 2 1 的发展缓解了用户业务与系统资源的矛盾，它比较适合那 些比较固定的用户。对于移动性较大、不需要大功率的基站的场合，移动a dh o e 网络 3 1 1 4 1 5 】能得到很好的应用。但是因为a dh o e 的特殊性，不太适合直接应用到 民用通信领域。与此同时，w l a n 6 】在接入领域中也得到了迅速发展。但w l a n 因为接入点( a p ) 的覆盖范围较为有限，要在大范围内通信，需要大量的接入点， 会大大的提高成本。 基于w l a n 技术和移动a dh o c 网络技术的基础上，无线m e s h 网络 ( w i r e l e s sm e s hn e t w o r k s ) 7 1 应需而现。 无线m e s h 网络能够让网络中的每个节点都能实现发送和接收信号，从而使 传统的无线网络一直存在的扩展性低和健壮性差等诸多问题迎刃而解【2 】。 无线m e s h 网络能够有效的避免a dh o c 网络、无线局域网的一些限制，从 而了提高其性能。无线m e s h 网络可以有多种的应用：室内宽带网、校园网、企 业网、楼房自治n ( b u i l d i n ga u t o m a t i o n ) 、城域网络互联、智能交通系统网等。 目前，国内外对移动a dh o c 网络的自组织算法和路由算法有非常多的研究。 但在无线m e s h 网络上，还没有路由协议正式标准。无线m e s h 网络路由协议基 本与a dh o c 网络路由协议相同，所以a dh o c 网络中的路由协议可以应用到无 线m e s h 网络中。微软的无线m e s h 网络是基于动态源路由协议( d s r ) 【4 】【8 1 ，许多 其他的公司使用a o d v 路由协谢5 】【6 】。尽管有一些用于a dh o c 网络的路由协议 可用，无线m e s h 网络的路由协议设计依旧是一个热门的研究领域。 目前大部分对无线m e s h 网络的路由协议上面的研究都是基于这几种典型的 路由协议有：d s d v e 8 l 吲( 目的序列距离矢量路由协议) 、d s r ( 动态源路由协议) 、 a o d v ( a dh o c 按需距离矢量路由协议) 等。 1 2 本文的主要内容及意义 j 丝京邮电太堂殛班究生堂僮i 金塞玉线迪韭圆终蹬由拉苤敛班荭 本文主要针对无线m e s h 网络中的按需路由协议的特点【1 0 1 ，根据目前常用的 节点时延统计方法的缺点，提出一种节点时延估计的算法：首先根据统计时刻前 的数据分组经过该节点所需要的时间，可以得到统计时刻前的节点时延，然后根 据统计完成时刻时的节点业务分组队列的长度与之前统计的数据分组在进入本 节点时节点的业务队列的长度来进行比较，从而获得本节点统计完成时刻的节点 估计时延。用这种统计方法由于充分考虑了节点状态的动态变化，所以统计出来 的节点估计时延能够比较准确的反应出节点的真实时延，有利于应用在按需路由 协议中。 同时提出一种基于时延与负载的综合度量的a o d v 路由协议的优化扩展协 议t la o d v - 通过修改r r e q 分组，增加一个节点负载字段来记录链路中的最 大的节点负载，周期计算中间节点的时延，并且通过节点的时延来控制控制 r r e q 分组的转发时间，当本节点的节点时延较大的时候，延迟较大的时间再进 行转发r r e q 分组，这样在目的节点中最先收到的那些r r e q 分组将是经过较 短时延的节点到达的路由请求，根据他们能够选出一条或几条端到端时延较小的 路由；同时在目的节点中收集一段时间上传来的同一路由请求的r r e q 分组， 并且在这些r r e q 分组中选出一个r r e q 分组，其信息中负载度最小的一个， 并根据其建起的反向路由来实现r r e p 的回发，从而能在几条时延最短的路由中 选出一条负载最小的路由，进行业务传输。同时利用o p n e t 网络仿真工具【】【1 2 1 ， 创建仿真模型对改进路由协议迸行仿真测试，通过分析产生的结果，验证了改进 后的路由协议与原有路由协议相比，在平均端到端时延【1 3 1 ，吞吐量，以及丢包 率均有了一定改进，能够更好的适应无线m e s h 网络的环境。 1 3 本文的结构 全文的内容安排如下： 第一章为绪论。主要介绍无线m e s h 网络的研究背景及国内外的研究现状， 研究的意义和主要任务及章节安排。 第二章为无线m e s h 网络简介。简要介绍了无线m e s h 网络的定义和特点以 及无线m e s h 网络的路由技术；详细介绍了a o d v 路由协议的工作原理及特点。 第三章根据目前已有的一种节点时延的估计方法进行分析，提出一种更加准 确的节点时延的估计算法，并对算法进行仿真分析。同时利用现有的路由协议 a o d c ，利用新提出来的节点时延统计方法代替a o d c 原有节点时延统计方法， 并进行仿真。 第四章提出了一种基于时延和节点负载的综合控制的路由协议 2 i j - 仃l a o d v ) ，介绍了其路由原理，并用o p n e t 仿真软件进行仿真，通过与经典 的a o d v 路由协议以及一种现有的路由协议d l a r 相比较，通过仿真可以看到 t l a o d v 在端到端时延、丢包率和网络吞吐量均有一定得改善。 第五章为总结与展望。总结了本文所做的工作，并对今后的研究工作及研究 方向进行了展望。 3 第二章无线m e s h 网络及其路由协议 2 1 无线m e s h 网络的概述 无线m e s h 网络是一种多跳、具有自组织和自愈特点的新型宽带无线，它可 以看成是w l a n 和无线a dh o c 的一种结合体。作为一种新型网络结构形态， m e s h 结构己被纳入到i e e e 8 0 2 1 6 和i e e e 8 0 2 1 1 5 标准中。无线m e s h 网络可以 通过一些中间节点连接互相远离不能直接连接的无线路由器，是一种可以解决 “最后一公里 瓶颈问题的新型网络结构。 2 1 1 无线m e s h 网络的基本结构 无线m e s h 网络由m e s h 路由器和m e s h 终端设备用户两个部分构成，一般 说来无线m e s h 网络的基本结构【刀【1 4 】按照节点功能可以分为三种： 第一种，单层平面的无线m e s h 网络。如图2 1 所示，这是一种只有m e s h 终端设备构成的一种网络，每个节点都是对等的节点，各自都包含相同的m a c 、 路由、管理和安全协议，不单指具有客户端节点的功能，也具有能够实现路由功 能，可以完全的实现路由器的业务承载转发的功能。 4 。 _ 图2 - i 单层平面结构 通过对等节点的连接形成一个点到点的网络，两个无法直接通信的用户终端 可以借助其它用户终端的转发功能实现通信，不需要特别的准备中转设备。这是 一种随着网内节点任意移动而网络结构随意变化的网络。 第二种，多级无线m e s h 网络结构，又称基础设施m e s h 网络结构 7 1 。这是 一种由接入点( m e s h 路由器) 与移动客户终端组成的结构模式，无线m e s h 路由器 与移动客户终端之间形成星型网络拓扑，如图2 2 所示。 图2 2 多级无线m e s h 网络结构 移动客户终端通过无线链路与无线m e s h 路由器相连接，网关节点( 无线 m e s h 路由器) 通过路由选择及管理控制等功能为移动终端选择出到目的节点通 信的最佳路径，并而形成无线回路。同时，移动客户终端通过网关节点也可与其 它网络相连，实现无线宽带接入。传统以太网用户可以通过以太网链路有线接入 m e s h 网络。 这种结构降低了系统的建设成本，也提高了网络覆盖率和可靠性。但是，任 意两个移动客户终端节点之间只能在m e s h 路由器的协作下才能通信，不能想单 层网络中直接进行通信。 第三种，混合网络结构。这种结构是综合了单层平面m e s h 网络结构和多级 m e s h 网络结构，如图2 3 所示。 6 图2 - 3 混合网络结构 在这种结构中，移动客户终端节点已不是仅仅是一些支持w l a n 的普通设 备，而是增加了具有转发和路由功能的m e s h 设备，它是一种集路由器与客户终 端的一种设备，终端与终端之间可以像a sh o c 网络一样实现点到点的直接对等 通信。 这种网络结构综合了前两种无线m e s h 网络模式所具有优势，因此同时支持 两种模式的混合m e s h 网络将在一个广阔的区域内实现多跳无线通信。终端设备 既能与其它网络相连，实现无线宽带接入，又可以与其它用户直接通信，并可作 为路由器转发其它节点的数据，送往目的节点。 2 1 2 无线m e s h 网络的特点 与有线网络比，自组织网络有许多独特之处，比如网络拓扑结构的动态变化、 移动节点的能力有限、需要要采用分布式控制方式、安全性差等。属于无线移动 自组织网络的无线m e s h 网络定然也存在相同的问题。无线m e s h 网络的路由协 议采取了不同算法和技术来克服无线m e s h 网络路由环路，减小路由开销和保证 网络动态性、自愈性。路由环路避免在源路由协议中，由于路由信息标记在数据 7 j 量塞邮电太堂亟班宜生堂僮i 金塞五线韭匦终蹬由越盔的班荭 分组和路由控制分组的头部，本身具有环路避免特性；链路状态协议是在的到全 部网络拓扑信息的条件下进行路由计算的，所以也不会产生环路。另外，无线 m e s h 网络也使用信息标识技术来解决路由环路。一些的无线m e s h 网络适用的 路由协议中，每一个分组可用二元组( 源节点，序列号) 来唯一标识每条路由。 序列号是在源节点中和时间相关的唯一值，序列号越大表明分组越新。分组标识 可以很好的解决分组到达时发生的顺序颠倒和重复，保证过滤重复分组和有序处 理分组。 网络动态性适应无线m e s h 网络的网络拓扑动态性会导致路由失效的频繁。 在网络动态变化剧烈时，路由协议采取泛洪方式实现；在网络动态变化不太剧烈 时，通常以备份路由、路由失效节点通知源节点重新计算路由或在路由失效节点 进行局部路由修复。其中，局部修复技术是在保持路由联通性的前提下，减少路 由开支，缩短路由恢复时间，用放弃最优路径的选择来换取缩短抢修时间。 2 1 3 无线n e s h 网络与其他无线网络的比较 i 无线m e s h 网络与移动蜂窝网络的比较【1 4 】 网络拓扑结构区别： 无线m e s h 网络结构是的网状结构，一个节点能通过很多路径到达目的节点， 如果在通信过程中某一路径断开或是负载过高的时候，完全可以通过相应的技术 来切换到其他的链路中进行，这样能更有效的保证网络的传输质量；蜂窝移动通 信系统结构都是以基站为中心并且与客户端形成的星型的网络，如果基站出现问 题，基本上网络就要瘫痪了。相比之下无线m e s h 网络要比蜂窝移动系统相更加 的可靠。 传输速率区别： 无线m e s h 网络可以与其他宽带无线网络技术( 如w i f i ) 相结合，在理论上 来说可以达到5 4 m b i t s s 的速率，甚至更高；而以目前正在使用的3 g 技术，它 理论上的传输速率在高速移动环境中仅支持1 4 4 k b s ，步行慢速移动环境中支持 3 8 4 k b s ，在静止状态下才可达到2 m b i t s s 。以此来看，无线m e s h 网络能够为用 户提供更大的带宽，能承载更高质量的网络业务。 网络的配置区别： 无线m e s h 网络中的基础设备体积小巧，价格相对便宜；而蜂窝移动通信系 统中的基站等设备体积大，成本高，难维护。相比之下无线m e s h 网络的扩展性 要更好一些，成本也会相对低。 2 无线m e s h 网络与无线局域网的比较f 1 4 】 网络拓扑结构区别： 8 w l a n 是典型的点对多点网络，终端和a p 不是对等的，终端只能通过a p 才能和有线以太网相连，其数据是不可转发。而对于网状结构的无线m e s h 网络， 数据是可以通过m e s h 无线路由器进行转发。 覆盖范围区别： w l a n 的a p 覆盖范围一般在几百米左右，比较难在大范围内实现高速的业 务承载；无线m e s h 网络中的节点具有多跳性，这样能够有效地扩大覆盖范围。 协议区别： w l a n 的m a c 协议其主要功能是要实现本的是本地业务的接入；而在无线 m e s h 网络，因为其各节点是对等的，每个节点既要完成本地业务的接入，还要 实现对来自其它节点的业务进行转发。在上面的路由协议，w l a n 主要是采用 已有的静态的i n t e f n e t 路由协议加入部分移动i p ；而无线m e s h 网络则需要设计 自己的路由协议。 3 无线m e s h 网络与移动a dh o c 网络的比较【1 4 】 网络结构区别： 无线m e s h 网络在骨干网结构提供了大范围的信号覆盖与节点连接，网络健 壮性较好；而所有移动a dh o c 网络的节点都兼有独立路由和主机功能，节点地 位平等，网络连通性是依赖端节点的平等合作实现的，故移动a dh o c 网络的健 壮性比无线m e s h 网络差。 业务模式区别： 无线m e s h 网络主要是针对来自i n t e r n e t 网得业务；移动a dh o c 网络主要针 对于军事或其他专业通信。两者针对的业务方向不太一样。 2 1 4 无线m e s h 网络路由协议的分类 依据不同的标准，无线m e s h 网络的路由协议有不同的分类方式。 1 按基本路由算法分类 距离矢量算法 这是一种主要基于b e l l m a n - f o r d 的最短路径的分布式路由算法。距离矢量 算法中，每个节点都拥有一张到网络中所有已知节点的路由表，在这个路由表中， 每一条表项包括：目的节点地址，到目的节点所需要经过的下一跳节点的地址以 及到目的节点所要经过的最小距离。每个节点都会周期地向邻居节点广播自己所 知道的路由信息。目的序列号距离矢量( d e s t i n a t i o n s c q u e i l c c dd i s t a n c e v e c t o r , d s d v ) 协谢1 7 1 9 】是属于此类算法的典型协议。 源路由算法 在源路由算法中，最大的特点就是每个数据分组中都包含了源节点到目的节 9 点所要经过的说有节点的路由信息，源节点负责所有的源路由的建立和维护。常 见的动态源路由d s r 就是是属于此类算法的经典协议。 反向路由算法 在反向链路算法中，在路由建立的过程中，源节点泛洪请求分组，在接收到 泛洪分组的每个中间节点都根据泛洪分组建立起到源节点的反向路由， a o d v - s t ( a dh o co n d e m a n d e dv e c t o r - s p a n n i n gt r e e ) 2 0 】就是利用了这种算法 来建立网关到所在子网内所有节点的路径。 2 按节点路由信息获取和保持方式分类 先应式路由协议 先应式路由协议又被称为表驱动路由协议。在这种网络中，节点要实行周期 路由更新，通过周期把本节点的路由信息广播给邻居节点以让邻居节点获得最新 的路由信息。在两次的周期更新之间，如果网络发生变法，将会马上实现触发更 新，而不会等到下一次的周期更新时刻的到来。这样的网络节点能很快的实现业 务的发送。相邻节点通过“h d l o 一分组来实现信息交换。d s d v 是此类路由协 议。 按需路由协议 按需路由协议又被称为反应式路由。在这种网络中，节点不需要周期的广播 路由信息分组，当一个节点有业务要传输的时候，它将会查找自己的路由表，如 果本节点已经有了到业务需要到达的路由，将会根据已有路由进行业务转发。只 有当节点没有到达目的节点的路由时，该节点就会向整个网络广播路由请求分 组，直到找到目的节点，然后目的节点给源节点回复路由应答分组，这样中间节 点可以根据路由请求分组和路由应答分组建立起反向路由和正向。按需路由协议 包括d s r 、a o d v 、a b r 等无线m e s h 网络基本的路由协议。 混合型路由协议 混合型路由协议同时具有综合先应式路由协议和反应式路由协议的优点，克 服两者的缺点。这种协议一般会应用在分层网络结构。对于不同的层次应用不同 的不同的协议，能有有效的突出重点，发挥优势。a o d v - s t 是该类路由协议较 为成熟的应用。 2 2 经典的无线m e s h 网络的路由协议的简介 l o 2 z 1d s r 路由协议 d s r ( d y n a m i c s o u r c er o u t i n g ，动态源路由协议) ，这是一种使用源路由思想 的a dh o c 网络按需路由协议，d s r 路由协议包括路径发现与路由维护两部分。 在该协议中，每个数据分组的头部都包含该分组到目的节点的路径上所有节点的 有序序列，这样有利于中间节点收集路由信。这种方法的优点表现在：网络上的 中间节点不用专门维护它要转发的数据分组的路由，只要在收到分组的时候根据 源路由的地址表项选择下一节点，然后将分组转发到制定的节点即可。因为他不 需要像其它的协议那样周期的交换路由信息，从而很好的减少控制信息的开销， 能够更加有效的传输业务。 在一次的通信过程中，当某一节点需要传业务到另一节点的时候，它( 源节 点) 会先查看有没有到目的节点的路由，如果有就直接将业务分组发送出去；如 果没有，就需要向周围求助，广播路由请求( r r e q ，r o u t er e q u e s t ) 分组。该分组 中包含源地址、目的地址和一个路由记录，该路由记录记录着r r e q 分组在路 由发现过程中所经过的那些节点的序列。同时每一个r r e q 分组都有一个唯一 的请求d ，它是由源节点决定的。通过源地址和请求i d 的组合能够有效的避免 对同一r r e q 分组的的重复处理。 当一个主机接收到r r e q 包时，它将按照如下步骤对该请求进行处理： 1 ) 如果该分组已经被处理过，也就是之前就已经处理过包含有相同的( 发 起者地址，序列号) ，直接忽略该分组，不做处理。 2 ) 如果本主机已经有到目的节点的路由，将忽略该请求分组。 3 ) 如果本主机就是r r e q 的目的节点，那么可以从路由请求分组中的路由 记录来获得一条从源节点到目的节点的一条路径，并根据该路径进行路由应答 r r e p 的回复。 4 ) 如果都不是上面两中情况。那么该主机就会把自己的地址加到r r e q 分 组中并广播出去。 具有相同的一组源节点地址和请求d 的路由请求看做同一次的路由请求， 一个节点只处理最早收到的同一次的路由请求。 目的节点根据r r e q 分组所带的路由信息来对r r e p 分组的回复，中间节 点如果已经有了到目的节点的路由表项，会直接回复r r e p 分组。 2 2 2d s d v 路由协议 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 ，目的地址带序列号 的路径矢量路由协议) 是一个基于经典的贝尔曼福德路由机制的路由表算法， 韭塞邮电太堂亟班究生堂僮i 金塞五线逝韭圜终监由拉苤的班究 但是它做了相对的改进，能够避免出现路由环路。 在这种网络中，每个节点都有一个全网的拓扑路由表，表中的每一条表项都 有一个由目的节点维护的序列号、目的地址，跳数其中序列号是用来表示路由 信息的新旧状态，这样能有效地避免路由环路。 每个节点都会定时周期的交换路由信息状况，确保节点中的路由信息是正确 的。它有两种更新路由的方式：一种使用“f u l ld u m p 的分组，它会把节点中 所有的路由信息广播出去。另外一种使用“i n c r e m e n t a l 分组，该分组只携带在 网络中因为移动或其他原因而导致的变化的相关信息。 节点还维持着一个添加的表，专门存放更新路由信息数据分组中的相关信 息。一个新的路由信息分组中包含如下主要元素：到目标节点的跳数，本路由表 项的序列号，以及用于广播的最新序列号。节点总是相应最新的序列好的路由信 息。如果两个更新信息有相同的序列号时，将表示是来自同一次的路由信息更新， 节点将会选取条数最小的作为保存。 2 2 3 懈路由协议 w r p 4 也是这样的一种路由表协议：每个节点需要维护以下表：距离表、路 由表、线路花费表以及信息重传列表( m r l ) 。m r l 中的每一表项都有以下信息： 更新信息的序列号，一个重传计数标志，是否响应的标志量，以及相关的更新信 息。 每个节点都是通过路由信息分组的传送来告诉邻居节点的网络的拓扑变化 状况，以此来保证每个节点中的路由信息都是实时准确的。路由更新信息只会在 一跳内传播。当一个节点收到其他邻居节点发来的更新信息，它将向它的其他邻 居节点广播，这样其他的节点也能得到变化的路由信息，从而在整个网络中建立 起来新的收敛拓扑。 每个节点都是通过接收到邻居来的分组来确认邻居是否还存在。如果一个节 点在相对长的时间内没有数据分组要发送，就必须广播“h e l l o 数据分组给 他的所有邻居，让邻居知道自己还在工作中。否则，邻居节点会认为该节点已经 不能与自己通过一跳来实现连接了，一旦发生这种情况，节点将会广播路由错误 信息分组来告诉它的邻居：某一节点已经与自己断开了，而其他节点一旦收到这 样的错误路由信息分组，将会更新自己的路由表，并把错误信息接着告诉别人， 很快整个网络就能知道这一信息，这样网络再次收敛。 1 2 j 匕塞邮电太堂亟班究生堂僮i 金塞 无线墨b 圆络蹬自拉苤的研究 2 2 4 0 0 v 路由协议 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 g ) 是一种按需的改 进的距离向量路由协议，与表驱动路由协议不同，按需驱动路由协议只有 当源节点需要到目的节点的路由或者当某个节点希望加入一个多播组时才 寻找路径。当源节点需要一条通往目的节点的路径时，它在网络中发起一 次路径发现过程。当找到一条路径或者所有可能的路径都被检查过后，路 经发现过程结束。路径一经建立，就被路由表维护起来，直到路径不再需 要或者路由失效或者超过生存期。a o d v 使用广播的路由查找机制。除了 源路由，a o d v 还依靠中间节点来动态建立路由表项。该协议还借用d s d v 中的目的序列号机制，每个节点维护一个单调递增的序列号计数器，用它 来作为新路由代替缓存中的旧路由的判断标志。当网络拓扑结构发生变化时， 它能快速收敛，具有断路的自我修复功能。计算量小，存储资源消耗小，对网络 带宽占用小。 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 ) 消息分组。 广播的时候，使用的目的节点地址是受限的广播地址2 5 5 2 5 5 2 5 5 2 5 5 ，广播消息 分组通过使用了p 头部的兀l 域来限定广播帧的传播范围。 路由查找建立过程：当网络数据分组的源节点s 到目的节点d 之间存在有效 路由的时候，则a o d v 进程不起作用。当源节点s 没有到目的节点d 的有效路 由时，便启动查找建立路由过程，如图2 - 4 所示。源节点s 广播一个路由请求消 息( r r e q ) 。其中包含源节点地址、源节点序列号、目的节点地址、目的节点序 列号和跳数等参数。中间节点1 ，2 和3 收到r r e q 时，建立或更新到源节点l 的反向路由，若中间节点有r r e q 所查找的有效路由，并且r r e q 帧没有设置 d 标志，则向上一跳节点发回路由应答消，g ( r r e p ) ，其中包含源节点地址、目 的节点地址、目的节点序列号、跳数和生存时间参数，并经若干中间节点到达源 节点s 。否则中间节点继续广播r r e q 消息，直到目的节点d 收到r r e q 后， 向源节点s 发回r r e p 。经过若干中间节点转发后到达源节点，确认路由建立。 其中r r e q 沿多条路径传播，但r r e p 只沿最先到达的路径( s ，1 ，d ) 传回源节 点如图2 5 所示。即选择时间度量最短的路由。 掣_ r r e q 盯) j r r e q 、 ! 、 、 r r e j q、h 、r 、r e q ，一一、 、 、 二q ，! 、阳q ，r r e q 删 i t 92 - 4r r e q 分组的发送 r r e 卜q r r e p 、 图2 5r r e p 分组的回复 路由表项建立以后，路由中的每个节点都要执行路由维持、管理路由表的任 务。在维护路由表的过程中，当路由不再被使用时，节点就会从路由表中删除相 应项。同时，节点会监视一个活动路由中下一跳节点的状况，当发现有链路断开 的情况时，就发出路由错误( r e r r ) 消息通知其他节点以修复路由。在r e r r 消 息中，指明了由于断链而导致无法到达的目的节点。每个节点都保留了一个“先 驱列表 ( p r e c u r s o rl i s t ) 来帮助完成错误报告的功能，该列表中保存了把自己作 为到当前不可达节点的下一跳的相邻节点。a o d v 路由表必须包含短期有效的 临时路由。比如接收r r e q 帧的时候建立的临时路由。a o d v 路由协议使用的 相关术语 1 a o d v 路由协议主要涉及到以下术语 4 1 ： 活动路由( a c t i v er o u t e ) ： 1 4 又为有效路由，到达一个目的节点的一条路由，该路由表项标记为有效。只 有有效路由才可以用来转发用户数据分组。 广播( b r o a d c a s t ) 广播就是把报文发送至m 地址2 5 5 2 5 5 2 5 5 2 5 5 中去。一个广播报文不是盲 目转发的，对它的转发会有限制。但有时候需要将某些a o d v 协议分组广播发 送到全网。 目的节点地址( d e s t i n a t i o n ) 就是用户业务分组要被发送到的目的m 地址，有时候用这个地址来表示目 的节点。到目的节点的路由通过执行a o d v 协议算法获得，在路由发现协议帧 r r e p 中携带着到目的节点的路由。 转发节点( f o r w a r d i n gn o d e ) 就是在一条链路上的终结节点，业务可以通过这样的节点来转发到另一节 点。沿着路由查找过程已经建立好的路径，转发节点将用户数据分组转发到距离 目的节点较近的下一跳。 转发路由( f o r w a r dr o u t e ) 一条已经建立好了的路由，通过该条路由，业务分组能够传送到业务要到达 的目的节点。 无效路由( i n v a l i dr o u t e ) 一条己经过期的路由，这条路由表上上已经标记上了无效状态标识。无效路 由表项是不可以用来转发用户业务分组，但它仍然会将路由信息存储一段时间再 删除，它可以为路由修复，以及以后的r r e q 消息提供有用的信息。 源节点( o r i g i n a t i n gn o d e ) 一般可以认为是发起寻找路由动作的节点，发起寻找路由的信息分组经过其 他节点的时候会被处理，并转发。例如，发起路由查找过程中广播r r e q 协议 帧的节点就称为r r e q 的源节点。 反向路由( r e v e r s er o u t e ) 它是通过处理r r e q 协议分组来建立起来的，能为r r e p 协议分组从目的 节点转发至源节点，或者从具有到目的节点路由的中间节点转发至r r e q 的源 节点提供一条路由。 序列号( s e q u e n c en u m b e r ) 是由每个源节点维护的