（无线电物理专业论文）区域路由协议半径自适应性研究.pdf

区域路由协议半径自适应性研究 专业： 硕士生： 指导教师： 无线电物理 魏锡彦 丘海明副教授 摘要 a dh o e 网络是一种临时自组织的无线通信网络，它由不依赖于任何固定设 旌和管理支持的移动节点组成。网络中的节点不仅具有普通移动终端的功能，而 且具有分组转发能力。移动a dh o e 网络区域路由协议z r p 是a dh o c 典型的路 由协议之一。它是一种本地主动，全网按需的混合式路由协议，每个节点通过广 播固定跳数的链路状态信息来维护自己的区域半径，区域内通过表驱动路由协议 维护路由信息，区域外通过边界点采用按需反应式路由协议按需进行路由选择。 z r p 协议建立了一种混合路由模型，通过区域半径的概念来将表驱动与按需 驱动的特点相结合，以达到取长补短综合两者优势的目的；但最初的z r p 协议 的路由半径是经过预设后不能改变的，这样就限制了混合路由协议优势的发挥， 本文在原z r p 协议的基础上对于其关键参数区域半径提出一种根据节点的相对 移动速度来改变的算法。根据表驱动路由协议周期性维护区域内各节点链路状态 信息，在一定周期内由相对速度引起的邻居节点的变化来促使半径的改变。使表 驱动路由和按需驱动路由的范围根据节点的移动速度来变化，从而降低路由开 销，改善区域路由协议的性能，使其更加合理有效。 本文完成了半径具有自适应能力的改进z r p 协议的设计、分析、仿真工作， 并提取了其性能曲线作了相应评估，验证了其合理性和可行性。最后对z r p 协 议的发展作了展望。 关键词：a dh o e ，z r p ，相对速度，区域半径 ar e s e a r c ho na d a p t i v er a d i u sf o rz o n er o u t i n gp r o t o c o l m a j o r ：r a d i op h y s i c s n a m e ：x i y a nw e i s u p e p g i s o r ：a s s o c i a t ep r o f e s s o rh a l m i n gq i u a b s t r a c t a dh o en e t w o r k ( m a r q e r ) i sat e m p o r a r ys e l f - m a n a g i n gw i r e l e s sn e t w o r kc o n s i s t i n go f m o b i l en o d e sw i t h o u td e p e n d i n go nt h ee x i s t i n gf i x e di n f r a s t r u c t u r eo ra d m i n i s t r a t i v es u p p o r t t h e n o d e si nm a n e ta r en o to n l yc o m m o nm o b i l et e r m i n a l sb u ta l s oh a v et h ea b i l i t yo ff o r w a r d i n g z o n er o u t i n gp r o t o c o li so n eo ft h et y p i c a lm u t i n gp r o t o c o l si na dh o e i ti sh y b r i dr o u t i n g p r o t o c o lw h i c h l s l o c a l l yp r o a o d v ea n dg l o b a l l yr e a c t i v e e a c hn o d ew h i c he x i s t si nz r p p r o a e t i v e l ya d v e r t i s e si t sl i n ks t a t ei n f o r m a t i o nw i t hc o n s t a n th o p si no r d e rt om a i n t a i ni t sz o n e r a d i u s t a b l ed r i v e np r o t o c o lm a i n t a i nr o u t i n gi n f o r m a t i o ni ni n t mz o n e ，o nt h eo t h e rh a n db o r d e r n o d e s c h o o s ep a t h su s i n go nd e m a n dp r o t o c o li ni n t e rz o n e z r p d e s i g nah y b r i dr o u t i n gm o d e l w h i c hc o m b i n et h ea d v a n t a g eo fp r o a e t i v ea n dr e a c t i v e p r o t o c o lu s i n gt h er a d i u s 脚e t o r b u tz r pm o d e lo r i g i n a l l yd e s i g n e dj u s th a v eaf i x e dr a d i u s s o m e t i m e si tc o u l dn o ta d a p tt h em o b i l en o d e sf u t u r ea n dh a v en oi d e a lp e r f o r m a n c e i no r d e rt o o p t i m i z et h eg h e m e ，o nt h eb a s i so f z r eai m p m v e da l g o r i t h mi sp r e s e n t e di nt h i sp a p e rw h i c h a l l o w st h er a d i u sc o u l dc h a n g ea c c o r d i n gt or e l a t i v es p e e do fm o b i l en o d e p m a c t i v ep r o t o c o l p e r i o d i c a l l yu p a a t ei t sl i n ks t a t ei n f o r m a t i o n , a n db e c a u s ed i f f e r e n tr e l a t i v es p e e dl e a d t od i f f e r e n t n e i g h b e tn o d e s ，w ec a nu t i l i z et h i sf u t u r ec h a n g i n gt h er a d i u sf o re n a b l i n gt h ep r o t o c o lm o r ee f f e c t i v e a n dr e a s o n a b l e ，a n dl o w i n gt h ec o n t t o lo v e r h e a d t h i sp a p e rh a v es t u d i e dt h ei m p r o v e dp r o t o c o li n c l u d i n gd e s i g n , a n a l y s i s ，s i m u l a t i o n m o r e o v e r r v l a k es o m ee f f c c t st op r e s e ta n da n a l y s et h es i m u l a t i o nr e s u l t so ft h ea d a p t i v er a d i u sz r pa n d t h e nc o n f i r mt h i sa l g o r i t h mi st e c h n i c a l l yf e a s i b l e a tl a s t ，w ei l l u s t r a t es o m ep r o b l e m sw h i c hh a v e n o tf o u n ds o l u t i o n s s o m ep l a c e sw h i c ha l en o tf i n ep e r f o r m a n c ew en e e dt oi m p r o v et h e ma n d p e r f e c tt h i ss c h e m ei nt h ef u t u r e k e yw o r d s ：a dh o e 。z o n er o u t i n gp r o t o c o l ，r e l a t i v es p e e d z o n er a d i u s i i i 第1 章绪论 1 1a dh o c 网络背景与发展2 i 从2 0 世纪7 0 年代以来，计算机的出现，使网络的发展和人们的生活越来 越紧密。美国国防部远景规划局出于军事的需要，开发研究的分组无线网p k n e t ( p a c k e tr a d i on e t w o r k ) 随着不断的发展逐渐成型，成为一种特殊的对等式无线 移动网络。1 9 9 1 年成立的i e e e 8 0 2 1 i 标准委员会采用了“a dh o e 网络”一词来 描述这种节点具有分组转发能力的多跳自组无线网络。a dh o e 一词源于拉丁 语，是“特别地，专门地为某一即将发生的特定目标、事件或局势”的意思。这里 的a dh o e 技术所标称的是一种特定的无线网络结构，强调多跳、自组织、无 中心的概念。国内一般把基于a dh o e 技术的网络译为“自组网”，或者“多跳网络” 等等 a dh o e 网络不依赖于网络基础设施，能够快速地自动组网，因而与需要基 站的无线网络相比其更加便捷，灵活且投资少。在军事战场，航空航海，紧急救 援，临时会议场所显现出其它网络没有的独有优势，因此有着非常广泛的应用。 无线移动a dh o e 网络己成为近年来国际上前沿和热点的研究领域，并已成为无 线网络通信网络技术的一个新发展方向。目前移动a dh o e 网络研究主要集中在 路由技术方面。i e t f ( i n t e m e te n g i n e e r i n gt a s kf o r c e ) 1 9 9 7 年专门成立了一个 m a n e t ( m o b i l ea dh o en e t w o r k i n g ) i 作组，负责路由协议及相关标准的制定工 作。现在虽然对各种a dh o e 路由协议的建议进行了评估，但还没有达成一致， 没有一个相关的标准形成。尽管如此我们有理由相信，a dh o e 网络这种新颖， 便捷的无线组网机制有着广阔良好的发展前景：在不久的将来，它必将融入人们 的生活，促进通信系统的飞跃发展。 1 2a dh o e 路由协议现状和存在问题f 3 】 4 1 1 5 l a dh o e 网是一组具有路由功能的节点组成的分布式无线多跳网络，它不依 由山大学硕十学位论文 靠任何预设的网络基础设施。因为自组网中节点的传输范围有限，源节点在向目 的节点发送数据时，通常需要其它节点的帮助，所以路由协议是自组网中不可缺 少的一部分。从功能上讲，路由协议是通信网络中一套将业务数据从源节点引向 目的节点的机制。自组网的路由协议应该包括路径产生( p a t hg e n e r a t i o n ) 、路径 选择( p a t hs e l e c t i o n ) 和路径维护( p a t hm a i n t e n a n c e ) 三项核心功能。其中，路 径产生是指根据集中式或分布式的网络状态信息和用户业务需求生成路径，网络 状态信息和用户业务状态信息的收集与分发是该过程的主要内容：路径选择是指 根据网络状态信息和用户业务状态信息选择最恰当的路径路径产生和路径维护 合在一起称为路由发现。路由维护就是对所选路径进行维护。由于a dh o c 网络 本身节点位置不定。带宽受限的特点，i n t e m e t 设计的许多路由协议不能直接适 用于该网络，必须设计新的路由协议。理想的自组网路由协议应该具有以下特点： ( 1 ) 采用分布式路由算法 ( 2 ) 具有自适应能力，可适应快速变化的网络拓扑结构。 ( 3 ) 无环路 ( 4 ) 控制开销少 ( 5 ) 具有一定的可扩展性 以此为标准，近年来人们已经研究发展了多种适用于a d h o c 网络的路由协议。 这些路由协议从不同角度可以进行不同的分类。根据路由发现策略的角度不同， 可以分为表驱动路由( 包括d s d v 、w r p ) 和按需驱动路由( 包括d s r 、a o d v 和t o r a ) 。本文主要的研究点则是以两者为基础提出的混合路由模式下区域路 由协议的半径自适应问题，将在后面展开详细讨论。 1 3 论文主要内容 本文详细分析与比较了当前移动a dh o c 网络单播路由协议性能，在表驱动 路由与按需驱动路由相结合的混合式路由协议z r p 的基础上，对于其关键参数 区域半径分析提出一种根据节点的相对移动速度来改变区域半径的算法。根据表 驱动路由协议周期性维护区域内各节点链路状态信息原理，用在一定周期内由相 对速度引起的邻居节点的变化来促使半径的改变。使表驱动路由和按需驱动路由 的范围根据节点的移动速度更加合理，有效地改变，从而有效地降低路由开销 第1 巷绪论 改善区域路由协议的性能。 本文给出了区域路由协议半径自适应性机制的设计方案，在理论探讨的基础 上，为了验证该方案的可行性，提出了具有针对性的仿真模型，通过o p n e t l 0 5 网络仿真软件对该协议进行了仿真并提取关键性指标与原有的z r p 协议进行了 比较，虽然还没有达到理想的效果，且在理论推导，机制合理性上尚有许多待完 备的方面，但算法也有其可行之处和特点。 1 4 论文结构 本文在a dh o e 区域路由协议的基础上做了些许改进使关键参数区域半径根 据节点移动速度的变化有了可以调节的可能。自适应区域半径的区域路由算法为 自组网路由协议提出了一种新思路，根据论文的内容全文分六章： 第一章绪论部分介绍了a dh o e 网络的背景与发展，路由协议的现状和存在 的问题，最后简单介绍了本文的核心内容和文章结构安排。 第二章对a dh o e 网络及其路由协议进行了详细系统的介绍。并根据各自的 不同特点作了具体的描述，最后对它们的性能作了比较和分析。 第三章对原有z r p 协议机制思想进行了详细具体的描述，并详细描述了在 它基础上提出的半径具有自适应能力的z r p 区域路由协议的新思想。 第四章介绍了0 p n e t 网络仿真软件的原理机制，并利用o p n e t 对半径具 有自适应能力的z r p 协议进行仿真的过程，并对每个模块进行了简要的描述。 第五章对仿真结果进行了比较分析，对仿真性能进行了总结。 第六章全文的总结与展望 第2 章a dh o e 网络及其路由协议 2 1a dh o e 网络的特点2 1 6 1 a dh o e 网络是一种特殊的无线移动网络。网络中所有节点的地位平等，无 需任何预设的基础设施和任何的中心控制节点。网络中的节点不仅具有普通移动 终端的功能，而且具有分组转发能力。与固定网络和普通移动网络相比，a dh o e 网络具有以下特点： 1 ) 分布式控制：a dh o e 网络中的移动节点兼备主机和路由功能，不存在一个网 络中心控制点，用户节点之间的地位是平等的，节点可以随时加入和离开网络。 网络路由协议通常采用分布式控制方式，因而具有很强的健壮性和抗毁性，任何 节点发生故障都不会影响整个网络的运行。 2 ) 网络自主性：a dh o e 网络相对常规通信网络而言，最大的区别就是网络的部 署和展开无需依赖于任何预设的基础设施。节点通过分层协议和分布式算法协调 各自的行为，它们可以快速、自动地组成一个独立的网络。 3 ) 动态拓扑：a dh o e 网络是一个动态的网络。a dh o e 网络中的节点可以随处 移动，也可以随时开机和关机，这些都会使网络的拓扑结构随时发生变化。此外， 无线传播条件的不确定性，也导致了网络拓扑以不可预测的方式任意和快速地改 变。 4 ) 有限带宽：a dh o e 网络采用无线传输技术作为底层通信手段，相对于有线信 道，其容量较低。并且由于多信道竞争、多径衰落、噪声和信号干扰等多种因素， 使得移动节点的实际带宽更小。 5 ) 节点能量有限：移动节点依靠电池提供所需的能量，减少功耗是网络协议设 计需要考虑的一个非常重要的因素。 6 ) 多跳路由：当节点要与其信号覆盖范围之外的节点进行通信时，需要中间节 点迸行分组的多跳转发。与固定网络的多跳不同，a dh o e 网络中的多跳路由是 由普通的网络节点完成的，而不是由专用的路由设备( 如路由器) 完成的。 7 ) 有限的安全性：因为a dh o e 网络采用的是无线信道，所以它会比有线网络 葛2 牵a d h o e i q 络厦其路由冉议 更易受到安全性的威胁。这些安全性的攻击包括窃听、电子欺骗、拒绝服务等。 上述表明，a dh o e 网络在体系结构、网络组织、协议设计等方面都有其显著的 特点，与普通移动通信网络和固定网络有着显著的区别。 2 2a dh o e 网络路由协议分类与比较1 1 标准不同，自组网的路由协议有不同的分类方式。按照路由协议所依据的基 本路由算法不同，路由协议可分为基于链路状态( l s ) 的路由协议、基于距离 矢量( d v ) 的路由协议、源路由( s r ) 协议和反向链路( l r ) 协议：按照路由 建立的方式不同可分为表驱动路由协议( 先应式路由协议) 、按需驱动路由协议 和混合路由协议；按照路由协议所依据的网络逻辑结构不同，路由协议可分为平 面结构路由协议和分层结构路由协议；按照路由协议所适用的网络规模不同，可 分为中，小规模和大规模路由协议；按照接收业务数据的目的节点个数的不同， 路由协议可分为单播路由协议和多播路由协议。另外，还有一些路由协议，利用 地理位置信息来改善路由协议，某些路由协议具备提供一定程度的q o s 保证的 能力，还有一些路由协议称之为功率感知路由协议，专门设计用来节省网络功率 消耗，延长网络寿命。 下面从路由发现策略的角度，介绍一些典型的a dh o e 网络路由协议。由此 种角度路由协议可以分为表驱动路由协议( t a b l ed r i v e nr o u t i n gp r o t o c 0 1 ) ，按需 路由协议( o n d e m a n dr o u t i n gp r o t o c 0 1 ) 及混合路由协议( h y b r i dr o u t i n g p r o t o c 0 1 ) 。 2 2 1 表驱动路由协议和各自特点 表驱动路由的发现策略与传统路由协议类似，节点通过周期性地广播路由信 息分组，来交换路由信息。每个节点维护到达个网内所有节点的路由。表驱动路 由的优点是当节点需要发送一个到达其它节点的数据分组时，只要路由存在，发 送分组的延迟就很小；缺点是表驱动路由协议需花费较高代价，路由表不能跟上 当前网络拓扑结构的变化，且动态变化的拓扑结构又可能使高价得来的路由表中 内容变成无效信息使路由协议始终处于不收敛状态。在下面各种表驱动路由协议 的算法介绍描述中，我们将看到它们各自的特点和在传统网络路由协议基础上的 妇山欠学硕士学位论z 改进。 d s d v u l ( 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 r ) 协议是在d v a 基础上进 行改进设计的，它被认为是最早的自组网络路由协议。其优势在于使用了目的节 点序列号机制通过对每一条路由记录设置一个序列号来避免环路的产生。 d s d v 是典型的表驱动路由协议，每个使用d s d v 路由协议的节点都维护 一个路由表，路由表包含了关于所有已知目的节点的路由项。用来描述一条路由 的主要参数包括：目的节点、到达目的节点的路由跳数、下一跳节点和目的节点 序列号。d s d v 使用周期性( p e r i o d i c ) 路由更新和触发式( t r i g g e r e d ) 路由更新相 结合的方式来维护路由信息的一致性。当d s d v 在传输信息过程中发现网络拓 扑结构的变化时，会使用触发式路由更新。为了防止这种更新产生太大的网络业 务开销d s d v 定义了两种类型的路由分组，第一种路由分组称为“f u l ld u m p ， 这种路由分组中包含了所有的路由信息，而所有的路由信息可能需要使用若干个 网络协议数据单元：第二种路由分组中仅包含自上次f u l ld u m p 以来发生的路由 变化，而在绝大多数情况下自上次f u l ld u m p 以来发生的路由变化可以使用一个 网络协议数据单元来携带。这样就在很大程度上减少了由于路由信息更新而造成 的网络负载。 无线路由协议w r p l 0 1 ( w i r e l e s s r o u t e p r o t o c 0 1 ) 是一个较早的自组网表驱动 路由协议，在w r p 中每个节点维护四个表：距离表、路由表、链路开销表和报 文重传表，节点通过它们保存着所有邻近节点与该节点的连接状态。通过其相邻 节点的最短路径生成树s s t ( s h o r t e s tp a t hs p a n n i n gt r e e ) ，生成自己的s s t ，然后 再向邻居节点传送更新消息。如果一个节点没有消息需要发送，节点间通过定期 发送h e l l o 报文来探测链路是否正常或者是否有新的节点加入。w r p 中每个节 点必须对其所有邻居节点发送的消息进行强制性检查来避免无限重复计数的问 题，这样就减少了当路径中断时出现循环的情况并加速了路由收敛。w r p 要求 节点维护4 张路由表，这给节点带来负担，特别是节点较多的时候。由于利用 h e l l o 分组保持连通性，w r p 不允许节点处于睡眠( s l e e p ) 状态，这会耗费电池 能量。此外，网络的带宽也会被更新分组大量占用。w r p 比其他路径选择算法 优越之处在于：先驱节点( p r e d e c e s s o r ) 的纪录，可以有效地避免路由环路。由 于采用了h e l l o 机制，当网络中增加了新节点时w r p 的更新速度很快。 6 窀2 奄a d h o c 嘲络及硅路由讲渡 o l s r p lf o p t i m i z e dl i n ks t a t er o u t i n g ) 协议是为了适应自组网的需求，对链 路状态算法进行优化而形成的。采用多点中继机制减小了控制分组的洪泛范围， 节点选择部分邻节点作为它的多点中继( m p r ，m u l t i p o i n tr e l a y s ) 节点，转发 控制分组，其它节点只处理不转发；通过只发送节点与中继节点的信息有效的缩 减了控制信息的大小。o l s r 实质上是表驱动的，所以具有找路时延小的优点， 但它仅支持双向链路。在无线网络中，由于冲突或其它传输问题会导致数据分组 的丢失。运行o l s r 路由协议的节点周期地发送自己的控制信息，因此o l s r 允许丢失部分控制分组。此外，该路由协议中每个分组携带最新的序列号，在接 受端，根据序列号的大小就可以区分新旧信息，所以不要求按序传输控制分组。 o l s r 逐跳查找路由，它要求节点周期地发送t c ( t o p o l o g yc o n t r 0 1 ) 分组来发 布m p rs e l e c t o r 信息，以帮助其它节点建立到它的路由。需要根据与邻节点的 链路变化率，增加或减少t c 分组的时间间隔。 s t a r a 州( s y s t e ma n dt r a f f i cd e p e n d e n ta d a p t i v er o u t i n ga l g o r i t h m ) 协议 采用最短路径算法计算路径，但最短路由度量采用了平均时延时间，而不是常用 的跳数，也就是说s t a r a 在进行分组路由时，考虑了无线连路的容量和排队延 时等因素。每个节点i 采用改进的端到端确认协议为每一对源和目的节点( i ， d ) 计算平均延时。 2 2 2 按需驱动路由协议和各自特点 根据发送数据分组的需要进行路由发现，建立网络拓扑和路由表内容的路由 协议称为按需路由协议。与主动路由的表驱动路由协议相反，按需路由认为在动 态变化的自组网环境中，没有必要一直维护去往其它节点的路由。仅在没有去往 目的节点路由的时候才按需进行路由发现。它的优点是不需要周期性的路由信息 广播，节省了一定的网络资源，可以快速适应网络拓扑的变化；缺点是发送分组 时，如果没有去往目的节点的路由，数据分组需要等待因路由发现引起的时延， 在网络负载很重的情况下，性能较差。下面简单介绍下几种典型的按需路由协 议的路由策略，及它们各自的优缺点。 d s r t “1 ( d y n a m i cs o u r c er o u t i n g ) 动态源路由协议是一种基于源路由的按 需路由协议。设计d s r 的目的在于创建开销非常低同时又能快速响应网络变化 中山大学硕t 学位沦之 的路由协议，以高度反应式的服务确保数据分组在节点移动或者其它网络条件变 化的条件下仍然能够正确递交。d s r 使用源路由算法，每个给定路线的数据分 组都在报头带有完整、有序的此分组必经的节点列表。使用源路由可以保证无环 路，转发或者侦听分组的节点可以缓存分组中的路由信息己备后用，而且由于要 传输的数据分组已含有必要的路由信息，中间节点不必保存路由信息。 d s r 协议主要包括两个过程：路由建立和路由维护。这两个过程的工作都 是按需的。当节点s 向节点d 发送数据时，它首先检查缓存中是否存在到目的 节点d 的有效路由。如果存在，则直接使用，否则启动路由建立过程。具体过 程如下：源节点s 将使用洪泛发送路由请求消息( r r e q ) ，r r e q 包含源节点 地址、目的节点地址、唯一的标志号以及中间节点列表；中间节点转发r r e q ， 并附上自己的标识；当r r e q 消息到达目的节点d 或任何一个缓存有到目的节 点路由的中间节点时( 此时，r r e q 消息已记录了从节点s 到d 或该中间节点 的所经过的节点) ，节点d 或该中间节点将向s 发送路由应答消息( r r e p ) ，该 消息中将包含节点s 到d 的路由信息，并反转节点s 到d 的路由供r r e p 消息 使用；节点s 受到r r e p 后，路由建立过程结束，通信开始。在通信过程中，当 中间节点监测到通往目的节点的下一跳链路中断时，它将从自己的路由缓存中移 去包含该链路的路由并向该链路返回一个路由出错分组( i 冰e r ) 。节点s 收到 路由出错分组后，触发一次新的路由建立。 从上述算法机制中我们可以看出，d s r 路由协议具备源路由的优点，保证 路由无环路：不要求转发分组的中间节点存储路由信息，减少了协议开销：路由 缓存技术减少了路由建立开销；且保存到目的节点的多条路径；另外，它还可以 正确的计算出非双向链路的路由。当然协议也存在明显的不足，由于每个数据分 组的头部都要携带路由信息，数据分组的额外开销较大；路由请求采用洪泛方式 增大了重复广播的机率。 a o d v 卅( a dh o eo nd e m a n dd i s t a n c ev e c t o r ) 协议是在d s d v 协议基础 上结合d s r 中的按需路由机制提出的，与d s r 路由协议不同它是一种逐跳转发 分组方式的按需路由协议。在a o d v 协议中，为了找到通往目的节点的路由， 源节点将广播一个路由请求分组( r r e q ) ，收到r r e q 的中间节点根据r r e q 中的信息，建立到源节点的路由，在路由表中增加一个路由条目称为反向路由。 反向路由条目的目的节点是广播r r e q 的源节点，下一跳节点是将r r e q 发送 苇2 阜a d h o c i 叫络殷廷路由协议 给本节点的邻居节点。然后它在向周围节点广播此分组。如果目的节点收到 r r e q 则向源节点回复路由应答分组( r r e p ) ，r r e p 沿着刚刚建立的反向路由 向源节点传送，在此过程中，收到r r e p 的节点建立到目的节点的路由，在路由 表中增加一个路由条目，称为正向路由。正向路由条目的目的节点是r r e p 的源 节点，下一跳是将r r e p 发送给本节点的邻居节点。节点的移动可能导致原来的 路由不可用，针对以上情况，a o d v 协议中有两种处理方式：本地修复和源节 点重建路由。此外，a o d v 还加入了组播路由协议扩展，并支持q o s 。但是由 于基于双向信道的假设工作，路由回答要求直接沿着路由请求反方向回到源节 点，所以a o d v 不支持单向信道。 t o r a l i 叫( 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 t h m ) 协议是在有向无环图 ( d i r e c t e d a c y c l i cg r a p h i c ，d a g ) 算法叫的基础上提出的一种按需路由协议。 它分为路由发现、路由维护和路由消除三个过程。在t o r a 中路由的最优性是 次要的，为避免寻找新路由的开销经常会采用距离较长的路由。但t o r a 的路 由发现与其它按需路由协议一样，首先在网中扩散路由请求分组，在路由回答中， 采纳了d a g 算法。具体过程为：将每个节点分配一个相对于源节点的“高度值”， 其中目的节点的“高度值”最低，并根据相邻节点之间的“高度值”的比较从而形成 一条或多条的有向路经，方向是从“高度值”大的节点指向小节点。从图论的角度 来看，即为一棵根为目的节点的有向无环图。算法的具体实现是通过路由回答分 组再回到源节点的过程中完成的。为了在拓扑结构发生变化时能够迅速重新生成 路由，并将产生的协议分组限制在受到影响的节点中扩散，t o r a 协议仍然采用 上述算法重新构造失效的d a g 。t o r a 也有其固有的缺点，首先协议的有效性 依赖于网络的高连通度提供路由维护所需的多条备选路径：其次t o r a 协议需 要依靠i m e p ( i n t e r a c tm a n e te n c a p s u l a t i o np r o t o c 0 1 ) 协议提供邻居节点信息和 底层可靠有序传输等能；最后它也不支持单向信道。 a b r 引( a s s o c i a t i v i t yb a s e dr o u t i n g ) 基于稳定度路由协议是一种源节点发 起的按需路由协议。在自组网中，当源节点和目的节点之间存在多条路径时，通 常以最短路径作为路由选择的标准。这对网络容量的充分利用，降低业务的时延 有着重要的意义。然而，这一准则并不完全适用于无线移动自组网。在无线移动 自组网中，节点移动导致拓扑结构的变化，一个在时刻t 建立的最短路由可能在 9 串山大学硕卜学位论文 t + i 时刻己不再有效，此外，节点的电量缺乏等也会导致建立的路由不可用。 a b r 协议就是从路由的有效时间的角度来设计，采用路径有效时间的长短而不 是路径的长短，作为路由选择标准。它由以下三个阶段组成：路由建立阶段、路 由重建阶段和路由删除阶段。路由建立是基于洪泛的，源节点广播路径查询( b q ) 分组，收到8 q 分组的节点建立一条到源节点的路由，并在b q 分组中添加自己 的i d 和“稳定性信息”，然后继续广播8 q 分组。为了获得整条路由上的信息， 不允许中间节点回复路由应答分组。当目的节点受到第一个b q 分组后，等待一 段时间，以收到其它路径到达的8 q 分组的副本，然后选择一个a s s o c i a t i v i t y 值 最高的路由，如果两条路由具有相同的a s s o c i a t i v i t y ，则选择跳数少的路由。一 旦选定了一条路由，目的节点将沿选好的路径发送一个路由应答分组。当 a s s o c i a t i v i t y 值改变，则启动路由重建，首先节点试图从局部进行路由修复，如 果不成功，向上游节点发送r n ( r o u t en o t i f i c a t i o n ) 消息，在最坏的情况下，源 节点收到r n 消息后，启动一个新的路由建立过程。当源节点不再需要路由时， 它将启动路由删除过程，通过洪泛r d ( r o u t ed e l e c t i o n ) 分组完成；超时则自 动删除路由条目。a b r 协议的一个重要特点是它打破了基于最短路径的传统路 由体系，提出使用邻节点空间、时间、连接和功率特点来构建一条生存时间长的 路由。 图2 1a dh o c 网路路由协议分类 1 0 锖2 鼋a d h o c 州络殷其路由协波 2 2 3 混合路由协议和各自特点 在a dh o e 网络中单纯采用主动式或按需式路由协议都不能完全解决路由问 题。在高速动态的a d h o e 网络中，无论使用主动式表驱动路由还是按需式路由 协议最后的结果多不理想。所以目前对自组网的路由问题的研究着眼于对平面路 由的改进。混合路由、层次路由等方法上也是现在的一个热点。下面针对典型协 议分别进行简单介绍。 f s r i i 训( f i s h e y es t a t er o u t i n gp r o t o c 0 1 ) 鱼眼状态路由协议是一种主动的链 路状态协议。它基于一种鱼眼技术，模仿鱼眼的功能，通过对不同距离的节点采 用不同的路由更新频率，使得距离越近的节点，掌握的路由开销信息越准确。另 外它的路由更新分组仅在邻近节点之间交换，减少了用于路由控制的开销。 口准霸蜓缱 口授准确k 墟 f - 1 镁舞埏域 图2 2f s r 运行状态的路由区域 基于区域的路由协议z h i s 中网络被分割成不重叠的区域，区域与簇不同， 它没有首领且定义了两级拓扑：节点级和区域级。节点级拓扑指一个区域内的节 点的物理连接。区域级拓扑指各个区域如何相互连接。网络中存在两种链路状态 报文：节点链路状态报文和区域链路状态报文。节点链路状态报文包含了节点的 邻居信息，旨在区域内传播。区域链路状态报文包含了区域间的链路状态，在全 网传播。通过分区可以减少路由控制报文的个数。 随着定位技术的发展，节点可以方便的获得自己的地理位置信息，利用这些 位置信息，可以改善自组网的路由性能。如位置辅助的路由协议l a r 【l u ( l o c a t i o n a i d e dr o u t i n g ) 和基于位置信息的路由协议如贪婪路由( g r e e d y r o u t i n g ) ，定向洪泛( d i r e c t e df l o o d i n g ) 等都不同程度改善了路由协议的性能， 扫山夫学硕 学位论文 促进了a dh o c 网络路由协议的深入研究。在这里因为与论文的主题关系不太紧 密，暂且不做深入讨论。 区域路由协议z r p l l 刚( z o n er o u t i n gp r o t o c 0 1 ) 协议巧妙的结合了主动路由 和按需驱动路由协议的特点。网络内的所有节点都有一个以自己为中心的虚拟 区，区内的节点数与设定的区域半径有关。在区内使用主动路由算法，中心节点 使用区域内路由协议i a r p ( i n t r a z o n er o u t i n gp r o t o c o l s ) 维持一个到区域内其 它节点的路由表，对区域外节点的路由使用按需路由算法，利用区域外路由协议 e r p ( i n t e r z o n er o u t i n gp r o t o c 0 1 ) 建立临时的路由。z r p 的性能依赖于区域半 径参数值。区域半径应根据网络特征来确定。论文提出的算法就是在区域路由协 议的基础上提出的，详细内容将在下面对章节展开。 2 2 4 a dh o e 路由协议简单比较【2 1 0 9 1 每种路由算法各有其优缺点，不能严格地说哪种路由算法就一定优于其它算 法。由于a dh o e 是网络中较新的领域，并且随着大量便携通信设备和无线通信 的发展，a dh o e 网络的应用也大量增加，所以，必须充分地考虑到通信环境和 大量的移动设备来选用路由算法，有时还可以把某些路由结合起来使用以更好地 提供通信服务。无论是先应式表驱动还是按需路由协议，随着网络规模的扩大， 这些路由协议的开销( 包括控制开销、存储开销和计算开销等) 都会不断地增大， 导致网络性能不断下降。因为每个节点都要维护自己本身的路由表，主动路由协 议适用于网络规模小，网络节点移动比较慢的a dh o e 网络环境，当节点移动较 快时，更新频率跟不上拓扑变化速率，所以会导致路由质量迅速下降。同时现有 的大多数a dh o e 按需路由协议如d s r ，a o d v ，t o r a 中，路由发现仅根据路 由的新旧程度和路由跳数等参数进行路由选择，因此这在很大程度上增加了使用 不可靠路由的概率。使用不可靠路由就会导致频繁的路由失效，而路由失效将会 对协议的性能和网络服务质量造成不利的影响。现在我们通过表格来对典型的表 驱动路由协议和按需路由协议性能特点进行以下比较。 葛2 鼋a d h o c l 卅络硬其路由协汉 表2 - i 典型a dh o c 路由协议性能比较 聊8 攀“郴搿# gp “o # w ”4 。”8 湖 协议 瞬 w r p泓r a d s ra od _ v 。g ：r o r ai i 特性 蓊# 女# 辅 馨商式操露。2 。7 麓 是是是是是是 陵巧劈垂 是是是是是是 巨动缀霭 j l 主动主动主动按需按需按需 舞襄经鼹盎更蔹：是是是否h e l l o 分组否 陲护多条路出；否否是是否否 e0 巨持单薅链路i 否否是是否否 黟省能潆燕略 否否否否否否 陵缝转发极铡i逐跳逐跳逐跳源路由逐跳逐跳 巨供安釜魂割鬟 否否否否否否 彝由度量选簿j最短路径最短路径延时最小最短路径最短路径最短路径 眵在特殊节点 否否否否否否 目 酶殊硬锋要壤，。 否否否否否双信道g p s s 支鹭+ 。耋 否否是否否否 1 3 第3 章z r p 协议半径自适应机制 3 1z r p 路由协议架构及特点 区域路由协议( z r p ，z o n er o u t i n gp r o t o c 0 1 ) 是c o m e l l 大学的z y g m u n t j h a s s 教授和m a r erp e a r l m a n 等人开发的同时使用主动和按需路由策略的移动 a d h o c 网络路由协议。由第二章的论述可知表驱动路由协议移动性不强，业务 发起次数多的场合性能好，而按需路由协议在移动性强，业务发起次数少的场合 下性能好。一种最理想的机制是让它们分别工作在不同的范围内。拿使用a b 两个协议的框架来讲，假设它们分别属于表驱动路由协议和按需驱动路由协议。 协议a 可以以某节点为中心在一定区域内工作，而协议b 可以在此区域外利用 协议a 提供的信息来工作。网络整体性能通过改变协议a 的工作范围来实现。 在丽种极端的情况下，协议a 的范围扩大，以至于作用到整于通信范围，或协 议a 的范围缩小，以至于完全是协议b 来工作。这样就可以充分利用两类协议 各自的特点。z r p 就是采用这种思想，它是一个分区路由协议，以多范围 ( m u l t i s c o p e ) 技术为基础，提出了一个混合路由协议框架( z o n er o u t i n g f r a m e w o r k ) ，在区域内采用先应式表驱动路由协议，时刻维护着路由信息，区域 外采用反应式路由协议按需进行路由选择。且区域的大小可以进行调整，以适应 局部或暂时的网络变化，使网络的整体性能最佳。 3 1 1z r p 路由协议中的基本概念2 0 1 i 路由区域：对任意给定的节点，该节点通过一个本地化的主动路由协议能检测 到的所有节点的集合。 路由区域的定义如下： z ( k ，n ) = i i t t ( n ，f ) s k ) 3 - 1 其中z ( k ，疗) 代表节点n 的路由区域，k 代表以跳数计的区域半径，h ( h ，i ) 表示两 个节点之间的最短跳数。节点的路由区域由所有与该节点的最短跳数不大于k 的 节点组成，它描述的是节点间的连接关系，不关心实际的物理距离。 蔫3 葶z r p 胁议半径自适f 越机制 2 内部节点：位于路由区域内部的节点，一个路由区域成员要么是区域内部节点， 要么是边界节点。 3 边界节点：位于路由区域边缘的节点。 4 区域半径：以跳数为单位计量，一个节点到其路由区域边界节点的距离。 5 边播树：以某节点为根节点，以未覆盖边界节点为叶子节点的组播树。 6 已覆盖节点：某边播查询包节点路由区域的节点。 7i a r p ( i n t r a z o n er o u t i n gp r o t o c 0 1 ) ：区域内部路由协议，以表驱动路由协议为 基础 8i e r p ( i n t e r z o n er o u t i n gp r o t o c 0 1 ) ：区域问路由协议，以基于边界广播的按需 驱动路由协议为基础 图3 1 节点s 半径为2 的路由区域 在z r p 中，每个节点均有自己的路由区域，邻节点的路由区域彼此覆盖，图3 1 为节点s 的一个半径为2 的路由区域。与节点的距离等于区域半径的点就称为边 界点，如节点k 为s 的边界点。与节点可以直接通信，一跳可达的点称为邻节 点，如节点d 为s 的邻节点。a