（电路与系统专业论文）基于移动速度的自适应区域路由协议[电路与系统专业优秀论文].pdf

摘要 基于移动速度的自适应区域路由协议 专业： 硕士生： 指导教师： 摘要 电路与系统 程毓良 周杰英副教授 移动a dh o e 网络区域路由协议f z 0 n er o u t i n gp r o t o c o l ，z a v ) 是现有移动 a dh o c 网络典型路由协议之一。z r p 是一种本地主动、全网按需的混合式路由 协议，该协议中每个节点主动地广播固定跳数的链路状态信息，这个固定跳数 就是区域半径。这些本地通告能够给每一个节点提供其路由区域内所有节点以 及区域外可到达链路的信息。路由区域边界上的节点称为边界节点，这些节点 用于按需发现区域外的路由信息。z r p 的目标是使主动维护路由区域和按需路 出查找的路由控制开销之和达到最小。 z r p 设计中假设所有节点使用统一的移动速度。而从对区域路由协议z r p 的仿真中，发现区域路由协议的性能在移动节点使用不同移动速度的多个场景 中表现出巨大的差异。针对移动节点使用不统一的移动速度的网络场景，为了 得到更好更稳定的路由性能，本文在z r p 路由协议的基础上，提出一种基于移 动速度自适应调节区域大小的路由协议v b a z r p ( v e l o c i t yb a s e da d a p t i v ez o n e r o u t i n gp r o t o c 0 1 ) ，该协议允许不同节点根据各自的移动速度来选择一个不同的 区域半径值。 根据新协议的要求，本协议修改了从属于区域路由协议z r p 的区域内路由 协议( i a r p ) 和边播解析协议( b r p ) ，提出一个新的区域内路由协议v b a - 认，这个协议利用非对称请求应答机制和对称相互更新机制来主动维护一个节 点的路由区域，以及一个新的边播解析协议v b a b ，这个协议利用节点之间的 包含关系能将查询包高效地转发到网络中其他地方。 本论文完成了v b a z r p 协议的详细设计，并在o p n e t 网络仿真软件上对 该协议进行仿真，提取其性能曲线并作性能评估。仿真结果显示，基于移动速 度的自适应区域路由协议v b a z r p 相比原始的区域路由协议z r p ，更能适应节 点以不同速度移动的更复杂和现实的网络场景。 关键词：a dh o c ，z r p ，移动速度，区域半径，路由区域 a b s t r a c t v e l o c i t yb a s e da d a p t i v ez o n er o u t i n gp r o t o c o l m a j o r ：c i r c u i ta n ds y s t e m n a m e ：y u l i a n gc h e n g 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 rj i e y i n gz h o u a dh o cn e t w o r kz o n em u t i n gp r o t o c o l ( z r p ) i so n eo ft h ee x i s t e dt y p i c a la dh o c r o u t i n gp r o t o c o l s z r pi sah y b r i dr o u t i n gp r o t o c o lw h i c hi sl o c a l l yp r o a c t i v ea n d g l o b a l l yr e a c t i v e i nz r p ，e a c hn o d ep r o a c t i v e l ya d v e a l s e si t sl i n ks t a t ei n f o r m a t i o n o v e raf i x e dn u m b e ro fh o p sc a l l e dz o n er a d i u s t h e s el o c a la d v e r t i s e m e n t sc a n p r o v i d ee a c hn o d ew i t ht h e1 i n k so fa l ln o d e sw i t h i nt h er o u t i n gz o n ea n dt h a ta r e r e a c h a b l eo u t s i d eo ft h ez o n e t h en o d e so nt h eb o u n d a r yo ft h er o u t i n gz o n ea r e c a l l e dp e r i p h e r a ln o d e sw h i c ha r eu s e dt of i n dt h er o u t i n gi n f o r m a t i o no u t s i d eo ft h e z o n er e a c t i v e l y t h eg o a lo fz r pi sm i n i m i z i n gt h es u mo ft h ep r o a c t i v ea n dr e a c t i v e c o n t r o lo v e r h e a d t h ed e s i g no fz r ph a sa s s u m e dt h a ta l ln o d e sh a v eu n i f o r mm o b i l i t y t h r o u g ht h e s i m u l a t i o no nz r p ，w ef i n dt h a tt h ep e r f o r m a n c e so fz r pi nm u l t i p l es c e n a r i o sw h e r e m o b i l en o d e sm o v ew i t hd i f f e r e n tm o b i l i t yp u tu pg r e a td i f f e r e n c e s t og a i nab e t t e r a n dm o r es t a b l er o u t i n gp e r f o r m a n c ei na n ys c e n a r i ow h e r em o b i l en o d e sm o v ew i t h n o n - u n i f o r mm o b i l i t y , o nt h eb a s i so fz r p ，an e wz o n er o u t i n gp r o t o c o ln a m e d v b a z r p ( v e l o c i t yb a s e da d a p t i v ez o n er o u t i n gp r o t o c 0 1 ) i sp r e s e n t e di nt h i sp a p e r w h i c ha u o w sd i f f e r e n tn o d e sc h o o s ed i f f e r e n tz o n er a d i u sa c c o r d i n gt oe a c hn o d e s m o b i l i t y t of u l f i l lt h ed e m a n do ft h en e wp r o t o c o l , t h ei 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 ) a n db o r d e r c a s tr e s o l u t i o np r o t o c o l ( b r p ) o fz r pa r em o d i f i e d v b a z r pp r o t o c o l p r e s e n t san e wi a r pn a m e dv b a - i aw h i c hu s e sa s y m m e t r i cr e q u e s ta n dr e p l y m e c h a n i s ma n ds y m m e t r i cm u t u a lu p d a t em e c h a n i s mt om a i n t a i nan o d e sr o u t i n g z o n ep r o a c t i v e l ya n dan e wb r pn a m e dv b a - bw h i c hc a nf o r w a r dr o u t i n gq u e r y e f f i c i e n t l yo u t s i d ez o n e sb yv i r t u eo f i n c l u d i n gr e l a t i o n s h i pb e t w e e nn o d e s t h i sp a p e rd e s i g n sv b a z r p ，p r e s e n t sa n da n a l y s e st h es i m u l a t i o nr e s u l t so ft h e v b a z r pw h i c ha r eg o to no p n e t t h es i m u l a t i o nr e s u l t ss h o wt h a tv b a z r pc a n a d a p tw e l lt ot h em o r ec o m p l i c a t e da n dr e a l i s t i es c e n a r i o si nw h i c ht h en o d e sm o v e w i t hd i f f e r e n ts p e e dt h a no r i g i n a lz r p p r o t o c 0 1 k e yw o r d s ：a dh o c , z r p ，v e l o c i t y , z o n er a d i u s ，r o u t i n gz o n e 第1 章 1 1a dh o c 网络简介1 】【2 1 第1 章绪论 二十世纪七十年代，美国国防部远景规划局( d a r p a ) 出于军事需要，开 始研究分组无线网p r n e t ( p a c k e tr a d i on e t 、o r k ) 在战场情况下数据通信的应 用，这种无线分组网的发展就是现在的无线a dh o c 网络。 无线a dh o c 网络由于不需要固定的基础设施，能够快速地自动组网，因而 与需要基站的无线网络相比，它显得灵活、健壮、投资少，在军事战场、航空 航海、自然灾害、紧急救助、临时会议和野外场景等情况下，a dh o c 网络有着 非常广泛的应用，并已被逐渐扩展到民用和商用领域，可用于城市交通、环境 监测、旅游探险、移动机器人和家庭安全控制等领域。例如利用i e e e8 0 2 1 1 规 范和b l u e t o o t h 物理传输技术构建的无线自组织网络可用于组建w p a n ( w i r e l e s s p e r s o n a la r e an e t w o r k ) 和w h a n ( w i r e l e s sh o m ea r e an e t w o r k ) 。 无线移动a dh o c 网络已成为近年来国际上前沿和热点的研究领域，并已成 为无线网络通信技术的一个新的发展方向。目前移动a dh o c 网络研究主要集中 在路由技术方面。i e t f ( i m 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 cn e t w o r k i n g ) 工作组，负责路由协议及相关标准的 制定工作。目前正对各种a dh o e 路由协议的建议进行评估，但难于达成一致， 还没有一个相关的标准形成。 1 2a dh o c 网络中路由协议设计面l 晦的主要问题 3 1 1 4 1 有线网络路由协议主要基于两种形式的路由思想：距离向量算法( d v a ， d i s t a n c ev e c t o ra l g o r i t h m ) 和链路状态算法( l s a ，l i n ks t a t ea l g o r i t h m ) 。但 是，d v a 和l s a 都不适合在a dh o c 网络环境下运行。这是因为a dh o c 网络的 特性为路由协议的设计提出了新的问题和挑战，主要包括以下几个方面。 1 1 由于移动a dh o e 网络拓扑结构动态变化，直接运行有线网络路由协议需要 7 花费很长的时间和较大的代价才能到达收敛状态。 2 】无线传输设备功率的差异以及无线信道中大量干扰导致单向信道的存在。 中山大学硕士论文 3 ) 有线网络路由算法中周期性广播路由更新分组会消耗大量的网络带宽。 4 1移动终端固有的特性，如采用电池一类可耗尽能源提供电源，内存较小， c p u 性能较低等，要求路由算法简单有效。 1 3 课题内容 本文在详细分析当前a dh o c 网络各种路由协议之后，选择区域路由协议 z r p 5 】为研究对象。z r p 协议设计以所有节点使用统一的移动速度为假设，这 个假设导致协议性能在移动节点使用不同移动速度的多个场景中表现出巨大的 差异。然而，现实场景中节点的移动速度是不统一的，因此针对移动节点使用 不统一移动速度的网络场景，为了能够得到更好更稳定的路由性能，本文提出 了节点根据自己移动速度来选择不同的区域半径值的基于速度的自适应区域路 由协议一- - v b a z r p ( v e l o c i t yb a s e da d a p t i v ez o n er o u t i n gp r o t o c 0 1 ) 。 由于节点区域大小不同，z r p 协议中使用的区域内主动路由协议算法和边 播解析协议算法皆不能胜任新协议的要求，因此本文就是对这两个算法进行了 重新设计，通过仿真实验，看到新算法不仅能够适应包含各种移动速度节点的 网络场景的需要，而且减少了主动维护和按需查找的路由开销，缩短了路由发 现的延迟，增大了投递分组的成功率。 本文给出了v b a z r p 协议的详细设计方案，阐述了每个节点如何主动维护 自己路由区域内的路由信息，以及如何查找区域外节点的路由信息，并且给出 了减少路由查找开销的几种查询控制机制，最后通过o p n e t1 0 5 a 网络仿真软 件对该协议进行仿真，提取其各项性能指标。 1 4 论文结构 本文结构安排如下：第一章为论文的前言部分；第二章介绍a dh o c 网络特 性、几个典型的路由协议、以及这几个路由协议之间的比较：第三章介绍与 v b a z r p 协议相关的理论基础。阐述了v b a z r p 协议的详细设计方案；第四章 详细叙述v b a z r p 协议仿真实现过程；第五章是仿真结果、分析和实验结论； 第六章是总结和展望。 2 第2 章 第2 章a dh o c 网络特点及路由协议 2 1a dh o c 网络的特点【2 】f 3 】 无线a dh o c 网络是不依赖任何基础设施的移动节点之间的短时间互连，又 叫移动自组织网络或多跳无线网。由于无线电波的衰减特性，其覆盖范围十分 有限，两个无法直接进行通信的节点需要借助于其他节点来转发分组，一次通 信需要若干次中继才能完成。节点通过分层的网络协议和分布式算法相互协 调，实现了网络的自动组织和运行。 无线a dh o c 网络在很多方面区别于其他通信网络，主要有以下几点： 1 )移动自组织。移动节点既是终端设备，又充当路由器的角色，因此节 点可以随时加入和离开网络，实现快速自动组网。 2 )动态拓扑。移动终端能够以各种速度和移动模式移动，并且无线发射 装置的天线类型多样，性能各异，加上无线信道间的相互干扰等各种影响，导 致了网络拓扑结构频繁变化。 3 1无线多跳通信。由于节点发射功率的限制，节点的无线覆盖范围是有 限的。当要与其覆盖范围之外的节点进行通信时，需要中间节点的转发。 钔完全分布式。无线a dh o c 网络是对等节点构成的网络，不存在中心控 制，这样管理和组网都非常简单灵活。 5 1严格的资源限制。有限的带宽和能源是所有无线网络的普遍特征，但 由于无线a dh o c 网络没有基站的支持，依靠有限能量的电池提供路由转发功 能，因此资源限制更为严峻。 2 2a dh o c 路由协议分类4 1 传统的路由协议无法适应a dh o e 网络的需要，因此必须选择或设计适用于 a dh o c 网络环境特点的路由协议。经过多年研究，许多路由协议方案相继被提 出。除了m a n e tw g 发布的a o d v * 1 、d s r 、z r p 等路由协议草案外，研究 人员还发表了许多关于a dh o e 网络路由协议的学术论文，比如d s d v 7 1 、 f s r t 8 1 、s s r 9 i 、l a r l l 0 1 、l a n m a r 儿1 、o l s r l l 2 1 等。 3 中山大学顶士论文 这些a dh o c 网络路由协议根据不同的角度可以进行不同的分类。根据发现 路由的策略，可以分为主动路由协议和按需路由协议；根据网络逻辑视图，可 以分为平面路由和分级路由，另外根据是否使用g p s ( g l o b a lp o s i t i o n i n g s y s t e m ) 系统，可以分为地理定位辅助路由和无地理定位辅助路由，如图2 - 1 所示。 按需路由如：d s r 、a o d v 、 一平面路由一 s s r 主动路由 如：d s d v 、o l s r 、 无地理定位- j f s r 产辅助路由i a d h o c 分层路由如：z r p 、l a n m a r 路由协_ 从 i 地理定位辅如：l a r 助路由 图2 - 1 路由协议分类 2 3 典型路由协议及其比较 以上介绍无线a dh o c 网络的特点，并对已有的一些路由协议做了简单的分 类。下面从发现路由策略的角度，按照不同类型介绍一些典型的a dh o c 网络路 由协议，并比较它们的性能。 2 3 1o l s r 4 1 2 】协议 优化的链路状态协议( 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 协议缩短了链路状态更新 消息分组的大小，为了获得路由信息，节点间需要有规律地交换网络拓扑信 息。o l s r 采用了多点中继技术( m p r ，m u l t i p o i n tr e l a y ) ，被邻节点选为多 点中继的节点需要周期性地向网络广播控制信息，控制信息中包含了把它选为 m p r 的那些节点的信息，以告诉网络中其他节点与这些节点直接相连。只有 m p r 节点被用做路由节点，非m p r 节点不参与路由计算。o l s r 还利用m p r 节点有效地广播控制信息，非m p r 节点不需广播控制信息，把链路状态更新消 息重传行动限制在部分邻居节点中进行。不过，这样做的后果可能导致通信负 4 第2 章 荷过分集中在m p r 节点上。o l s r 比较适合节点密度大的a dh o e 网络，但 m p r 节点的选择带来了额外的丌销。 2 3 2d s r 1 3 】协议 动态源路由协议( 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 ) 是简单的基于 一种“源路由”的按需路由协议。采用这种算法数据包可以很方便地沿着定义 好的路径进行传输，而且当一条路由断开时，节点可以在高速缓冲区中找到预 备的路由。但每个数据报文的头部都需要携带路由信息，数据包的额外开销较 大。 d s r 仅在没有去往目的节点路由的时候才按需进行路由发现。它主要包括 两个过程：路由发现和路由维护。图2 2 说明了d s r 算法的路由探测过程。 图2 2d s r 算法路由探测过程 当源节点1 要发送一个数据包到目的节点6 时，首先查询它的路由表是否 有到达目的节点的有效路由，若有就直接发送数据包。如果没有，那么源节点 会向它的所有邻近节点发送一个路由请求信息( i 滚e q ) 进行路由探测。融疆q 包含源和目的节点地址以及唯一的标志号，中间节点收到r r e q 后，附上自己 的节点标识并将该消息转发。当r r e q 消息到达目的节点6 或任何一个有到目 的节点路由的中间节点时( 此时，r r e q 中已记录了从1 到6 或该中间节点的 所经过的节点标识) ，6 或该中间节点将向1 发送路由应答消息( r r e p ) ，该 消息中将包含1 到6 的路由信息，并反转1 到6 的路由供r r e p 消息使用。此 外，中间节点也可以使用路由缓存技术来对协议作进一步优化。 2 3 3z r p 协议 中山大学硕士论文 区域路由协议( z r p ，z o n er o u t i n gp r o t o c 0 1 ) 是混合使用按需和主动路由 策略的a dh o c 网络路由协议。在z r p 中，每个节点都主动维护一个区域，区 域的形成算法比较简单，是通过一个重要的协议参数一一区域半径1 3 】( 以跳数 为单位) ，指定每个节点维护的区域大小，即所有距离不超过区域半径的节点 都属于该区域。一个节点可能同时从属于多个区域。 区域半径设置将直接影响z r p 路由的效率，因此如何根据网络的实际通信 环境，例如节点密度、节点速度等，设置一个最佳的区域半径是决定z r p 效率 的重要因素。 2 3 4 路由协议比较 下面对已介绍的几种路由协议各自的特点进行比较，如表2 - 1 所示。 表2 1 路由协议特点比较 协议0 l s rd s rz r p 周期性报文需要无区域内链路状态包 路由维护策略全网更新通知源 通知源或局部修复 结构平面式 平面式等级式 混合驱动( 域内主 驱动类型主动按需 动，域问按需) 使用的路由表数一( 路由c a c h e 表) 研究表明，混合式路由协议z r p 具有更好的扩展能力，能够适应各种规模 场景的需要；能够提供冗余的路由，在路由错误时，不仅可以通知源节点选择 其他的路由而且也可以局部修复，增加了网络的健壮性；它恰当地在主动式路 由协议需要大量控制开销和按需式路由协议路由发现会产生比较大迟延之间进 行折中，一方面减少了控制开销，另一方面降低了迟延，实现了可靠性和高效 性。 第3 章 第3 章v b a z r p 协议及其理论背景 v b a z r p ( v e l o c i t yb a s e da d a p t i v ez o n er o u t i n gp r o t o c 0 1 ) 协议是对移动 a dh o c 网络中区域路由协议的扩展，使得这种混合式路由协议可适应网络可扩 展性和节点移动性的需要。本章中先对z r p 协议进行一个总体介绍，然后介绍 基于移动速度的自适应思想，并分析了在节点的半径不再统一时，原z r p 协议 部分算法也相应不再适用的原因，在此基础上给出了修改后的算法，最后为了 更高效地进行路由发现，给出了三种重要的路由查询机制。 3 1 区域路由协议z 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 a s 教授和m a r cr p e a r l m a n 等人开发的混合使用主动和按需路由策略的移 动a dh o c 网络路由协议。z r p 是一个分区路由协议，将整个网络分成若干个以 节点为中心、一定跳数为半径的路由区域。与一般的分缴路由协议不同，区域 内的节点数与设定的区域半径有关，因此z r p 的区域重叠程度很高，许多节点 可能同时属于多个区域，每个区域的半径长度由用户设定。 3 1 1 基本概念【1 5 1 1 1 6 1 路由区域：对任意给定的节点，该节点通过一个本地化的主动路由协议能 检测到一些和其具有连通性的所有节点的集合。 内部节点：位于路由区域内部的节点，一个路由区域成员要么是内部节 点，要么是边界节点。 边界节点：位于路由区域边缘的节点。 区域半径：以跳数( h o p s ) 为单位计量，一个节点到其路由区域边界节点 的距离。 边播树：一棵以某节点为根节点，以未覆盖边界节点为叶子节点的组播 树。 已覆盖节点：某边播查询包节点路由区域的节点。 7 中山大学硕士论文 图3 - 1 显示了以半径为2 跳的路由区域。这个区域属于节点s ，节点a k 是其路由区域成员。距离节点s 为3 跳的节点l ，处于s 路由区域的外部，节 点a f 为s 的内部节点，节点g k 为s 的边界节点。 3 1 2 体系结构 图3 - 1 半径为2 跳的路由区域 z r p 协议是包含主动路由和被动路由的混合式路由协议，它的体系结构【5 j 如图3 - 2 中虚线矩形框内所示。 图3 - 2z r p 协议的体系结构 z r p 协议包含三个子协议，分别是： i a r p ( 区域内路由协议，i n t r a z o n er o u t i n gp r o r o c 0 1 ) b r p ( 边播解析协议，b o r d e r c a s tr e s o l u t i o np r o t o c 0 1 ) 第3 章 i 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 ) i a r p 子协议可以使用各种能够维护全网路由的主动式链路状态路由协议， 比如o s p f ”】，t b r p f l l 8 】，或者o l s r 1 2 】。通过交换路由更新包，主动维护自 身的路由区域拓扑，链路更新是由m a c 层的邻居发现协议n d p ( n e i g h b o r d i s c o v e r yp r o t o c 0 1 ) 触发的，n d p 发现邻居之间链路的建立和连接，然后通告 给i a r p 。 i e r p 通过使用一种“请求一应答”机制，按需地获得路由区域之外的节点 的路由，它使用边播解析协议b r p 提供的边播传递服务来转发查询包。 b r p 利用l a p & 提供的区域内路由信息，构建一棵边播树，查询包从源节 点出发，沿着边播树向网络中未曾查询过的区域高效地转发。 3 1 3z r p 协议结构与分级结构的差别【1 9 】 i a r p 和i e r p 之间的关系让z r p 看起来像是分级路由协议，事实上，z r p 只是在表面上和分级路由协议有些相似。分级路由协议依靠网关节点或者是标 记节点的战略分配，为整个网络建立一个层次式的子网，要访问这个子网则要 先通过子网的网关节点或者标记节点，这样就使得属于不同子网的两个节点要 相互通信的话，必须将数据包发送给两个节点能共同到达的某一层次子网，这 种局限经常导致次优路由的产生。相反，要访问一个z r p 路由区域，则不需要 单独的网关节点或者标记节点，而是通过多个边界节点中“最好的”一个节点 来选择路由。区域间节点经过一种“对等式”的部分区域重叠的方式进行通 信，而不像分级路由那样通过拥有更大覆盖能力的高一级节点。这样，z r p 协 议由于可以选择到目标节点的最优路由，避免了和分级路由协议相关的路由低 效性，并增加了无线频谱的重利用。因此将z r p 归类为平面式路由协议，而不 是分级式路由协议。 3 1 4z r p 协议三个子协议概要 3 1 。4 1 i a r p 子协议 2 0 】 i a r p 协议是指一类能够满足i a r p 基本要求的主动式路由协议。传统的主 9 中山大学颁十论文 。冬s 多p - - l i ) 一恺、j i 一 一 3 1 4 2 b r p 子协议【1 9 】 在z r p 中，高效的路由查询是以话由区域为基础，通过边播协议来实现 的，它不是“邻居一邻居”式的盲目地泛洪路由查询，而是要求查询包沿着通 1 0 第3 章 向所有边界节点的边播树转发。因此要实现边播，必须要先建立边播树。由于 一棵完整的边播树是从根节点延伸到路由区域所有的边界节点，所以根节点利 用自己维护的区域拓扑信息来构建这棵树，这棵树的叶子节点是所有没有被查 询覆盖的边界节点。如图3 - 4 所示。 图3 - 4 根节点构建的边播树 3 1 4 3 i e r p 子协议 2 1 2 2 2 3 】 i e r p 协议负责按需地发现目的节点在区域外的路由。按需路由发现协议包 括两个阶段，分别是路由请求阶段和路由应答阶段。 1 路由请求 当一个节点需要到目标节点的路由，但是在自己的区域内路由表中没有存 储这条路由的时候，启动路由请求。源节点生成一个请求包，并把这个包沿着 边播树转发，收到请求包的节点，检查自己的路由表，如果存在目标节点的路 由，则该节点给源节点返回一个应答包，否则，节点将自己的地址以及链路度 量添加到该请求包中，再次将该包沿着自己的边播树转发。一个节点如果重复 收到某路由请求包，则认为这个包是多余的，并将其丢弃。 2 路由应答 当一个被查询节点能够提供到达目标节点的路由时，该节点产生一个包含 已发现路由信息在内的应答包，并返回给源节点。为了让中间节点能够转发应 答包，路由请求包必须记录它在网络查找过程中所经过的中间节点。这一系列 1 1 ，山大学硕士论文 中问节点经过反转以后可以用来向源节点发送应答包，在返回应答包的过程 中，不再向已经变得较长的包中添加节点地址，这样节省了传输带宽资源。 3 举例说明 图3 5 i e r p 操作示例 在图3 5 中，源节点s 为了给目的节点d 发送数据包，s 检查路由表后知 道d 不在自己的区域内，因此s 构建了一棵到边界节点b 和f 的边播树，然后 s 可以直接发送路由请求包到b 和f ：b 和f 收到该包后检查自己路由表都发现 d 不在自己的区域内，b 和f 构建自己的边播树，b 把请求包转发到e 和g ，f 把请求包转发到c 和h ；d 处于节点c 和e 的区域内，于是c 和e 都产生应答 包，并转发回到源节点s 。s 得到了两条路由，一条是s a b c e d ， 另外一条是s a f g c e d ，源节点可以根据两条路由中跳数最小原 则选择第一条路由。 3 2 基于移动速度的自适应思想 在文章【5 】【1 9 】【2 4 】【2 5 】【2 6 】中，关于区域路由协议的讨论和研究，都是基于 统一的节点移动速度，然而在实际应用环境中，移动节点在网络中的移动速度 是互不相同的。比如说，城市里面公交车的移动速度就要比环城路上的汽车， 或者是空中的直升飞机移动速度慢很多。在这样的情况下，每一个移动节点都 使用相同的区域半径是不适合的，因此半径大小的设置成为z r p 协议性能表现 的关键问题。 研究【1 9 】【2 l l 表明，小的区域半径适合于高速的移动性和较少的路由发现需 求，而大的区域半径则适合于慢速的移动性和较多的路由发现需求。维护区域 第3 章 的主动控制信息随着半径的增加而增加，按需在区域外查找路由的控制信息则 随着半径的增加而减少；另外，按需查找路由的控制信息也和节点的移动速度 密切相关。针对这些因素，本文设计了一种基于节点移动速度的自适应区域路 由协议。 3 3v b a z r p 协议概述 在本协议中，按照节点移动速度的不同，将速度在3 0 - 4 0 r n s 的节点定义 为快速节点( f n ，f a s tn o d e ) ，半径设置为1 ；将速度在1 0 - - 3 0 m s 的节点定 义为中速节点( m n ，m i d d l en o d e ) ，半径设置为2 ；将速度在o 一1 0 m s 的节 点定义为慢速节点( s n ，s l o wn o d e ) ，半径设置为3 。 v b a z r p 协议是根据节点移动速度快慢来确定一个半径值，因此节点区域 大小不同，基于这样的着眼点，原z r p 协议中使用的区域内主动维护路由算法 和区域闻路由发现算法都不再适用，因此本文针对这两个问题，通过对原有算 法的修改和扩展，使得新的白适应算法具有更好的适应复杂网络场景的能力。 事实上，z r p 协议可以看作是本协议的一种特殊情况。在v b a z r p 协议 中，当网络中所有节点移动速度相同的时候就成为了z r p 协议。因此，可以认 为v b a z r p 是对原z r p 协议的进一步扩展。 3 3 1 协议基本假设 v b a z r p 协议的设计是基于以下假设的： 1 1 通信节点使用当前大多数无线设备采用的全向天线； 通信链路是双向的：即若一个节点可以收到它的邻节点的消息，则它 的邻节点同样能收到该节点发出的消息； 3 ) 所采用的信道是广播信道。 3 3 2 邻居发现协议【1 2 】( n d p ) 由图3 2 可以看出n d p ( n e i g h b o rd i s c o v e r yp r o t o c 0 1 ) 实际上不属于z r p 的范畴，但是它却是z r p 的基础，它是m a c 层的一部分。通过n d p 协议，两 个节点可以知道彼此是否互为邻居。原z r p 协议中，节点通过n d p 协议仅仅 1 3 山大学硕十论文 ( 错。) 8 3 3 3 自适应区域内路由协议( v b a 一认) a i a 是v e l o c i t yb a s e da d a p t i v ei 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 协议的修改和扩展。 3 3 3 1i a r p 存在的问题 在区域路由协议中，节点为了维护自己的路由区域，它必须接收到所有区 域成员节点发来的链路状态包。由于i a r p 协议中所有节点的半径设置相同， 那么每个节点广播的链路状态包的t r l 域设置的数值是一样的，因此每个节点 都可以接收到自己路由区域成员广播的链路状态包。 但是在v b a i a 协议中，由于节点半径不同，导致节点路由区域大小不 同，那么一个节点就不知道自己路由区域内所有成员的路由区域大小，也就是 说，一个节点不知道自己属于哪些节点路由区域的成员，因此这个节点给不同 的源节点发送链路状态包时，也不知道如何恰当设置1 t r l 域，才能让自己的链 路包刚好到达源节点，而不是超出源节点或者还没有转发到源节点就停止转发 了。如图，3 7 所示。 1 4 第3 章 半径为3 跳的节点 半径为2 眺的节点 半径为世的节点 ( a ) i a r pc o ) v b a - i a 图3 7i a r p 区域和v b a - - i a 区域的差别 l 图3 7 ( a ) 中五个节点的半径为r = 2 ，b 是a 的边界节点，a 也是b 的边 界节点，d 和e 是c 的边界节点。c 广播t r l = r - - 1 ( = 为赋值符号) 的链路 状态包( 包含了c 的邻居节点，即a 和b ) ，a 接收到，那么处理后a 就维护 了到b 的路由，并且t t l 等于o ，不再转发；同理，b 接收到，b 就维护了到 a 的路由。b 广播t r l = r 一1 的链路状态包，c 收到后，经过处理c 就维护了 到d 和e 的路由，并且t 1 1 j 等于0 ，不再转发。 但是在( b ) 中，s 的半径为3 ，它有一个边界节点是a ，s 却不是a 的边 界节点，s 为了维护到a 的路由，它必须要接收到d 发来的链路状态包( d 发 出的链路状态包中包含a 的信息) ，那么d 的1 f r l 必须设置为2 ；同对，a 为 了维护到b 的路由，也必须接收到d 发来的链路状态包，这时1 几只要设置为 1 就可以。因此在这种情况下，d 不知道自己是否需要广播链路状态包，即使知 道需要广播链路状态包，按照i a r p 协议提供的算法设置t t l 域之后不能实现 既能满足s 和a 的不同需求，又不会带来无效开销这样的目标。 3 3 ，3 2v b a - - i a 协议概要 v b a i a 协议作为主动式路由协议，它收集了区域内所有节点的路由信 息，这些路由信息的维护决定了v b a z r p 路由选择的及时性。 为了减少z r p 协议中，每个节点因为周期广播链路状态包带来的路由维护 开销，本协议只要求慢速节点s n 和没有被淹没的中速节点m n 周期广播链路 状态包。 1 基本概念 中山大学硕士论文 在v b a i a 协议中，由于节点的半径大小不同，产生了不同大小的路由区 域。如图3 8 所示，慢速节点s 的路由区域最大，然后是中速节点a 的路由区 域，因此本协议定义s 淹没了a ，或者a 被s 淹没。图中虚线表示的不是节点 的无线传输范围，而是以半径大小计算的路由区域范围。当节点a 成为s 的邻 居节点的时候，那么a 就不再维护路由区域，之前存储的路由表项过期后直接 删除，这样同时减少了路由开销和信道竞争。 半径为3 跳的节点 半径为2 跳的节点 图3 - 8 淹没的定义 2 算法描述 链路状态包中包含了发送节点的i d ，序列号，半径，t 1 l ，还有邻居列 表，其中节点i d 和序列号可以唯一确定网络中的个链路状态包。 慢速节点s n 和没有被淹没的中速节点m n 周期广播链路状态包，转发次 数由链路包中t r l 值确定，为了进一步减少链路包被转发的次数，规定： 位= r j ( 3 1 ) 口簟j 是链路包的生存期，即t i m et ol i v e ：r 是节点的半径，之所以可咀 这样做，是因为链路状态包已经包含源节点的邻居列表。节点收到一个链路状 态包之后，取出链路状态包的相关参数值，将”凡值减去1 ，然后比较自己的 半径和链路状态包中的半径大小，当发现自己的半径比源节点的半径小的时 候，说明自己是源节点的路由区域成员，并且自己和源节点不是平等关系，因 此节点必须向源节点发出自己的链路状态包，如果半径相等，那么节点之间是 平等关系，那么就能够接收到彼此周期广播的链路状态包，最后根据t t l 是否 大于零来决定是否转发。 快速节点f n 和被淹没的中速节点m n 不需要主动周期地广播链路状态 包，它只是按需地向s n 和m n 返回自己的链路状态包。 第3 章 3 3 3 3 举例说明 半径为3 跣的节点 半径为2 跣的节点 衅径麓兰y ：、 一一一。 - ， i 一、 、 i i ， ， ， ， ， ， 一一一一7 图3 - 9v b a 一蛤算法示意图 根据图3 9 ，分别解释三种典型节点x ，a ，b 维护自身路由区域的过程。 1 节点x 维护自己路由区域的过程 节点x 的半径为3 ，它需要周期广播链路状态包，包中的r r l 设置为2 ， 并且含有自己的邻居列表节点a 和c ： 邻居节点a 和c 收到x 的链路状态包之后，检查半径和t t l ，发现半径为 3 ，知道是慢速节点发起的路由区域更新包，将t t l 减1 后等于l ，大于零，所 以a 和c 把这个链路状态包的1 几设置为l ，再次广播： 节点m 和e 收到c 转发的链路状态包，b 收到a 转发的链路状态包，然后 m ，e ，b 检查收到的链路状态包： 节点e 检查这个链路状态包的源节点半径和自己相同，并且1 f r l 减1 后变 为o ，因此不再转发，e 记录下自己的路由区域成员节点x 和边界节点a 的路 由，丢弃该链路状态包，同样道理，x 收到e 主动发来的链路状态包，x 也就 知道了自己路由区域节点e 和边界节点f 的路由； m ，b 检查收到的链路状态包，取出r r l 减1 后等于0 ，因此不再转发， 发现自己的半径比链路状态包的源节点半径小，知道是慢速节点发起的路由区 域更新包，因此这两个节点生成自己的链路状态包，t r l 设置为节点x 的半径 减l ，在这里就是2 ，然后向邻居广播，这样经过c 和a 的转发，x 就可以维 护m ，b 以及对应边界节点p ，q 。k ，y 的路由信息。 中山大学硕士论文 2 节点a 维护自己路由区域的过程 节点a 半径为2 ，广播链路状态包之前，检查自己的邻居列表，发现邻居 节点中有半径为3 的节点，因此知道自己被淹没，为了减小开销，a 不维护路 由区域，所以a 不广播链路状态包。 3 节点b 维护自己路由区域的过程 节点b 半径为2 ，检查邻居列表后，发现自己没有被淹没，因此它广播 m 为1 的链路状态包，邻居节点a ，y ，k 收到后，t r l 减1 等于0 ，不再转 发，a 和y 由于都被淹没，所以他们虽然不主动周期发链路状态包，但是在这 里它们需要响应b 发出的链路状态包，所以邻居节点a ，y ，k 都广播t r l 为 1 的链路状态包，这样b 就能维护到边界节点x ，z ，l 的路由信息。 3 3 3 4 进一步减少路由开销的两个方法 1 方法一 一个小半径节点可能在很短时间内收到很多大半径节点发来的链路状态更 新包，那么这个节点必须一响应，这样会产生大量的开销。因此解决方法是 为半径为2 和1 的节点都设定一个计时变量，用来存储自己上次响应链路状态 包的时间，每次需要响应之前计算当前时间和上次响应的时间差，如果这个时 问差大于链路有效期( 链路有效期要不小于链路状态包广播周期但是不能太 长，太长会导致路由失效率增大，本文在仿真实验时设置为链路状态包广播周 期)