基于两跳邻居信息的 AODV 路由修复机制.doc

《基于两跳邻居信息的 AODV 路由修复机制.doc》由会员分享，可在线阅读，更多相关《基于两跳邻居信息的 AODV 路由修复机制.doc（7页珍藏版）》请在三一办公上搜索。

1、精品论文推荐基于两跳邻居信息的 AODV 路由修复机制张学成，马立香 电子科技大学通信学院，成都(610054) E-mail：xuechengzh摘要：文提出一种基于两跳邻居信息的 AODV 路由修复机制。发现断路节点通过邻居信 息判断是否发起到达下两跳节点的路由修复，有效的避免了发起修复节点因为周围没有有效 的中继节点而造成盲等的情况，降低了修复延迟。如果发现断路节点不满足修复条件，由先驱节点根据自身邻居信息判断是否发起补充路由修复，提高了路由修复成功率。通过理论分析和仿真实验证明，改进后的修复机制能够有效的提高数据分组接收率并降低数据传输延 迟。关键词：邻居信息；下两跳节点；先驱节点修复

2、 中图分类号：A1.引言移动自组网(Mobile Ad hoc Network, MANET)是由一组移动节点组成的自治系统，和传 统的有线网络相比,MANET 具有拓扑结构动态变化、链路带宽受限、节点能量受限、安全性 差等特点。有线网络中的传统路由协议不能适应移动自组网的特点，因此路由协议的设计称 为 MANET 中最具有挑战的问题之一。AODV 路由协议是 MANET 中广泛应用的按需路由协议之一。为了找到通往目的节点 的路由，源节点首先广播到达目的节点的请求分组(RREQ)。中间节点收到 RREQ 后进行转 发，并建立到达源节点的路由。当目的节点收到 RREQ 后，则向源节点回复应答分组

3、(RREP) 。RREP 沿着刚刚建立的反向路由向源节点传送，到达源节点后，即建立到达目的 节点的正向路由。当节点检测到链路中断时，会在本地发起路由修复。如果修复失败，通知 所有利用该链路的上游相邻节点，通告该链路已经失效。目前对 AODV 路由协议的研究主要集中在路由维护阶段。当链路出现失效时，如何快 速修复路由并控制报文开销，提高数据分组递交率、降低传输延迟成为研究的重点。本文在AODV 本地路由修复基础上，结合现有的路由修复研究，提出一种基于邻居信息的路由修 复算法，在不增加控制报文数量的情况下，提高路由修复成功率，缩短路由修复时间，提升 协议性能。2.AODV 本地修复及研究2.1 A

4、ODV 路由修复当一条活动有效路由发生一条链路中断时，为了避免由源节点重新发起到达目的节点的 路由（以下称源路由），如果链路中断处离目的节点的跳数小于 MAX-REPAIR-TTL(最大修 复长度)跳，发生中断处的上一个节点可以选择在本地修复这条中断链路。本地修复的尝试 对于源(发起者)节点通常是不可见的，然后发起修复的节点发送到达目的节点的 RREQ，等 待一段寻找周期时间，以便接受该 RREQ 分组的响应分组 RREP。如果在路由请求周期结束 的时候，修复节点仍然没有接收到目的节点发送来的响应分组 RREP，就认为本地路由修复 失败，并向目的节点发送一条 RERR(错误分组)消息，通告目的

5、节点不可达。如果路由请求 周期内收到 RREP，则更新路由表，继续使用修复后的路由1。- 7 -2.2 路由修复已有研究2 中提出了一种对路由表中下两跳节点进行修复的新的 AODV 修复方法（称为 improved AODV）。学者认为链路失效主要发生在较小范围，因此发起到达失效路由下两跳 节点的路由修复比发起到达目的节点的路由修复可以减小修复延迟和报文开销。通过在 RREQ 和 RREP 报文中添加下（上）两跳节点信息，在建立路由表项时添加下两跳节点信息。 如果链路中断，首先发起到达下两跳节点的修复，如果不成功，在执行 AODV 本地修复。 3提出了一种递归的路由修复方法。当链路失效时，首先

6、发起到达目的节点的路由修复， 如果不成功，将缓存的数据分组回传给先驱节点，在由先驱节点发起到达目的节点的本地路 由；如果仍然不成功，继续回传缓存的数据分组，并由上游节点继续进行修复，以此类推， 直到修复成功或数据分组回传给源节点。4提出一种由先驱节点进行修复的算法。当预测 到链路即将失效时，向周围广播一个 HANDOFF 报文，里面包括先驱节点和失效路由的下 一跳节点。收到 HANDOFF 报文的节点如果同时可达报文中包括的先驱节点和下一跳节点， 就向先驱节点发送一个确认报文，通告存在到达下一跳节点的有效链路，由先驱节点进行路 由修复。5中提出一种本地修复时限制 RREQ 广播范围的方法，减小

7、控制报文开销。通过仿真证明改进后的路由修复算法都能在特定场景提高 AODV 协议性能，但是仍然 有一些不足：1.）发起修复的节点不进行邻居信息判断，直接发起路由修复。如果修复成功，可以减 小修复延迟；如果修复超时，向源节点发送 RERR 报文，通知源节点发起源修复，反而会增加重建路由的时间。2.）修复后的到达目的节点的跳数可能大于修复前路由的总跳数，触发源节点重新发起 到达目的节点的路由请求，进行源修复1。3.基于邻居信息的路由修复机制本文提出一种改进的路由修复方法AODV-NB（Neighbor Based AODV），通过两 跳邻居信息判断是否在失效节点发起本地路由修复或在先驱节点发起补充

8、修复，达到提高路 由修复成功率，降低修复延迟的目的。AODV-NB 通过 HELLO 报文信息，使节点掌握以自身为中心的两跳范围拓扑信息。当 发现失效链路时，发现断路节点首先根据两跳邻居信息判断是否发起到达路由表中下两跳节 点的路由修复（以下称快速修复）。如果符合快速修复条件，并且修复成功，则更新路由表； 如果不满足快速修复条件或者快速修复失败，则根据一跳邻居信息和先驱节点信息，判断是 否发起到达目的节点的路由修复（以下称原始修复）。如果原始修复成功，跟新路由表，如 果不符合原始修复条件或者原始修复失败，则向先驱节点发送 RERR 报文，通告到达目的 节点的路由失效。先驱节点根据自身的邻居信息

9、，判断是否发起到达目的节点的补充修复。 如果先驱节点不满足修复条件，则继续向上游节点发送 RERR 报文，直至源节点，由源节 点判断是否进行源修复。3.1 邻居信息在本文中，AODV-NB 在 HELLO 报文中添加了邻居节点数目和所有一跳邻居节点地址， 并且改进邻居表，针对每一个一跳邻居增加一个指针，记录通过该一跳邻居可以到达的两跳 邻居地址。节点接收 HELLO 报文时，可以同时了解到一跳邻居信息（HELLO 报文中的源节点）和通过该邻居到达的两跳邻居信息（HELLO 报文中携带的邻居信息）。当一个节点接收到所有邻居节点发送的 HELLO 报文后，就可以了解到以本节点为中心的两跳范围所有

10、节点拓扑信息。AODV-NB 中两跳范围邻居信息为链路失效时是否发起路由修复提供判断依据。链路失 效时，只有当发现断路节点两跳邻居表中存在失效路由下两跳地址时，才发起快速修复，提 高了快速修复成功率；同时，在发起原始修复之前判断失效路由先驱节点数目是否小于邻居 表中一跳邻居数目，避免因缺少有效中继节点造成的路由修复失败。以邻居信息作为判断发 起路由修复的依据，可以提高路由修复成功率，减小因修复失败造成的控制报文开销，降低 数据分组传输延迟。3.2 本地路由修复AODV-NB 的本地修复指发现失效链路节点发起的路由修复，包括两阶段：首先发起到 达失效路由中下两跳地址的快速修复，如果不成功，再发起

11、到达目的节点的原始修复。如图 1，当节点 A 发现 A-B 链路失效时，首先根据邻居信息判断是否满足快速修复条 件。节点 A 首先在路由表中找到找到失效路由中的下两跳节点 C 的地址，然后在邻居表中 查找节点 C 是否为自己的一跳邻居或者两跳邻居。节点 A 的邻居表中存在节点 C 的信息， 说明有到达节点 C 的中继节点，满足快速修复条件，发起到达节点 C 的快速修复。节点 A 向节点 D 单播目的地址为 C 的 RREQ（RREQ 中包含目的节点 Dest 的地址和序列号），节 点 C 收到 RREQ 后，判断到达目的节点 Dest 的路由仍然后效，向节点 A 发送 RREP。节点 A 收到

12、来自节点 C 的 RREP 后，快速修复完成，更新路由表。AODV-NB 通过邻居信息预测是否存在到达下两跳节点的中继节点，避免了 improved AODV 中因不存在有效中继节点而造成的快速修复不成功所带来的延迟。同时，根据 AODV-NB 进行快速修复后节点 A 到达节点 C 的跳数一定小于等于 2 跳，即修复后的路由 总跳数不会增加，从而避免了 improved AODV 中因修复后路由总跳数增加，而触发节点 Src 发起源路由的情况。A 的邻居表序号一跳邻居两跳邻居1BC2DC A 的路由表序号下一条下两跳目的节点1BCDest2Src图1 AODV-NB 快速修复示意图如果节点 A

13、 不满足快速修复条件，或者快速修复失败，那么节点 A 根据邻居信息判断是否发起原始修复。如果先驱节点数小于一跳邻居数，说明该节点周围有潜在的中继节点可以到达目的节点，可以发起修复；如果先驱节点数等于一跳邻居数，说明通过这些一跳邻居 只能到达已失效路由的源节点，而不能到达失效路由的目的节点，因此不发起路由修复。通过以上描述可以看出，根据两跳邻居信息判断是否发起本地修复的 AODV-NB 比AODV 和 improved AODV 具有更高的路由修复成功率，减小了路由重建的延时。3.3 先驱节点补充修复图 2 AODV-NB 补充修复示意图AODV_NB 中，如果发现断路节点不满足修复条件，未发起

14、本地修复，则向先驱节点发 送带标记的 RERR 报文，通知由先驱节点进行补充修复。当先驱节点收到带标记的 RERR 报文后，判断自己是否满足原始修复条件，如果满足就进行到达目的节点的路由修复；如果 不满足，继续转发 RERR 报文，并且取消 RERR 报文中未修复标记。如图 2，当节点 B 发现 B-C 链路失效时，由于不满足本地修复条件，将向节点 A 发送 RERR 报文，并标记为未修复。节点 A 收到 RERR 报文后，判断一跳邻居节点数目大于失 效路由先驱节点数，满足修复条件，发起到达目的节点 Dest 的补充路由修复，重新建立到 达目的节点 Dest 的路由，避免了由源节点 Src 发

15、起的源修复。AODV_NB 在先驱进行路由修复，作为对发现断路节点本地路由修复的一种补充，能在 一定程度上提高修复成功率，降低数据传输延迟。4.仿真分析4.1 仿真环境及参数本文主要对 AODV 协议、2中基于两跳路由修复的 improved_AODV 和本文提出的AODV_NB 三种协议性能进行比较。仿真采用 OPNET10.5。分别选择 30、40、50 个移动节点在 1000m*1000m 的区域内随 机移动，移动模型采用 Ramdom-Way-Point 移动模型。每个个节点分别产生一个数据流，每 个数据流目的节点在其他节点中随机选取。每个数据流中报文发送间隔服从指数分布，均值 为 0

16、.1 秒。每个报文大小也服从指出分布，均值为 128 字节。移动节点发送范围为 250 米， MAC 层采用 802.11 协议，速率为 11Mbps。仿真采用 5 个场景，节点移动速度分别为 5m/s，10m/s，15m/s，20m/s，25m/s，分别采集数据分组端到端延迟、数据分组递交率、控制报文 开销（控制报文数目和控制报文比特数）2。4.2 仿真结果仿真结果表明，当移动节点较多时，AODV_NB 协议在网络拓扑变化较快的场景中性能 提升较明显。以下是 50 个移动节点的仿真结果：10095数据分组递交率 (% )90数据分组递交率AODVimproved AODV AODV-BN85

17、807570655 10 15 20 25 30节点移动速度 (m/s )图 3 数据分组递交率数据分组端到端平均延迟0.50.4AODVimproved AODV AODV-NB平均延迟 (s )0.30.20.105 10 15 20 25 30节点移动速度 (m/s)图 4 数据分组端到端延迟图 3 显示了在不同移动速率下，全网数据分组的分组递交率，即全网正确接收到的数据 分组总数占全网发送数据分组总数的百分比。随着移动速率的增加，出现断路的几率提高， 发起本地修复和源修复的几率增大，AODV 协议性能下降较快，improved AODV 因为限制 了修复范围，修复成功率有所提升，协议性

18、能下降较慢，而本文提出的 AODV-NB 根据邻 居信息判断是否进行本地修复，同时有先驱节点进行补充修复，提高了修复成功率，在移动 速度较快时协议性能优于 improved AODV。图 4 中显示了成功递交的数据分组端到端平均延迟。由于 AODV 始终发起到达目的节 点的路由修复，修复范围大，修复时间长，所以数据传输延迟较高。对于 improved AODV和 AODV_NB，随着移动速度的增加，网络拓扑变化加快，两跳内修复成功的几率逐渐降低， AODV-NB 修复根据邻居信息判断是否修复，确定发起修复的节点到下两跳节点可达是才进 行快速修复，提高了修复成功率，从而降低了数据报文的传输延迟。

19、240235230全网控制报文开销（一）AODVimproved AODV AODV-NB225220215控制报文开销 (pkts/s )2102055 10 15 20 25 30节点移动速度（m/s）图 5 全网控制报文开销（一）全网控制报文开销（二）9600控制报文开销 （bits/s ）94009200AODVimproved AODV AODV-NB9000880086008400820080005 10 15 20 25 30节点移动速度 (m/s )图 6 全网控制报文开销（二）图 5 显示了全网平均每秒发送发送控制分组数，图 6 显示了全网平均每秒发送控制报文 的比特数。随着

20、移动速度的增大，AODV-NB 发送控制报文分组数小于 AODV 和 improved AODV，是因为依据邻居信息判断是否发起路由修复，减少了无效控制报文开销。但是由于 AODV_NB 的 HELLO 报文中携带邻居信息，所以控制报文比特开销比较大。总体来讲，随着节点移动速度的增加，链路失效的频率增大，需要发起路由修复的次数 相应增加，AODV-NB 协议更能发挥优越性。因此，该协议较适合应用于节点移动速度相对 较快，网络拓扑变化小频繁的场景。5.总结本文针对 AODV 本地修复机制和已有的相关本地修复改进，提出了一种基于两跳邻居 信息的路由修复策略。根据邻居信息，判断是否在本地进行快速修复

21、，从而提高了本地路由 修复的成功率。同时，如果本地未进行修复，将修复的机会留给先驱节点，有先驱节点根据 自生情况判断是否进行补充修复。通过仿真验证 AODV-NB 性能较 AODV 协议和2中提出的 improved AODV 协议均有 提高。节点移动速度越高，拓扑变化越快，性能提升越明显。但是 AODV-NB 也有不足， 就是通过 HELLO 报文通告邻居信息会增大控制报文比特数。如何通过数据分组报文捎带邻 居信息，从而降低控制报文比特数将是下一步研究的重点。参考文献1 C. Perkins,E. Belding-Royer,S. Das. Ad hoc On-Demand Distance

22、 Vector (AODV) Routing. Request forComments: 3561. 2003.72 XIAO Bai-Long, GUO Wei, LIU Jun, ZHU Si-Lu . “An Improvement for Local Route Repair in Mobile AdHoc Networks” . 2006 6th International Conference on ITS Telecommunications Proceedings , pp691-695 ,20063 Jing Feng, Huaibei Zhou, Wuhan. “A Sel

23、f-Repair Algorithm for Ad Hoc On-Demand Distance VectorRouting” . International Conference on Personal Communication, 2006 .4 P. Abhilash, Srinath Perur, and Sridhar Iyer . “Router Handoff: A Preemptive Route Repair Strategy forAODV” . ICPWC 2002, pp168-171,2002.5 Genping Liu1, Kai Juan Wong1, Bu Su

24、ng Lee1, Boon Chong Seet2, Chuan Heng Foh1, Lijuan Zhu1. “PATCH: A Novel Local Recovery Mechanism for Mobile Ad-hoc Networks” . Mobihoc, 2003.6 陈敏. OPNET 网络仿真. 清华大学出版社，2002AODV repair mechanism based on neighbor informationZhang Xuecheng ，Ma LiXiangUniversity of Electronic Science and Technology of

25、China，Chengdu(610054)AbstractA novel AODV repair algorithm based on neighbors information has been proposed in this paper. Tocheck the neighbor information before the local repair, the origrator effectively avoid the delay caused by the fail of local repair due to no relay nodes. Meanwhile, if the n

26、odes detecting the link failure do not satisfy the repair condition, it will transimit a special RERR to the precusors and let the precusors to evoke the local repair. This algorithm increase the probability to repair the fail route. Simulation shows that this repair machanism brings about distinct performance improvement.Keywords: neighbor informationnext-next hopprecusors repair