AODV协议局部修复机制改进
2016-11-09韩林呈陈喜春
韩林呈，陈喜春
AODV协议局部修复机制改进
韩林呈，陈喜春
AODV协议是Ad Hoc网络中典型的按需路由协议在详细分析AODV局部修复机制的基础上，提出了一种针对局部修复引发竞争问题的改进方法，即当多个断路发生时，分配每个修复进程优先级以避免竞争问题。仿真表明，该机制能够有效避免竞争并提升网络性能。
AODV；Ad Hoc；局部修复；竞争问题；优先级
0 引言
Ad Hoc[1]网络节点的快速移动及电量限制等原因可能会导致通讯链路中断。因此，在Ad Hoc网中如何进行有效地路由维护是国内外学者争相研究的重点。DSR[2]和AODV[3]是典型的按需路由协议，可以建立从源节点到目标节点的最短路由。当网络拓扑结构快速变化需频繁重建路由时，局部修复相对于全局修复能够以更短的时间和更小的代价达到修复损坏路由的目的。因此很多路由协议例如AODV和ABR[4]等都采用了局部修复[3,4,5]机制。但是，通常局部修复对于源节点是不可知的，自发和分散的局部修复很可能会导致竞争问题并降低网络性能。因此，本文在详细分析原协议的运行机制的基础上，深入阐述其断路的局部修复所引发的问题，并提出一种新的改进算法。文中最后通过仿真数据，直观说明改进后协议在路由修复开销、数据包投递率和端到端平均时延上的优越性。
1 AODV的局部修复机制
AODV路由协议采用Hello消息机制进行链路连通性管理，对有效路由进行维护。具有有效路由的节点每隔固定时间T便广播一个特殊的RREP包，即Hello消息。邻节点收到Hello消息，可对各自的相应路由进行建立或更新。若节点在连续的几个T的时间内未收到有效路由中相邻节点的Hello消息便认为该链路中断，并发送RERR至相关路由的节点。当发现链路断开时，可以由源节点重新发出RREQ查找路由。但是，目前多用局部修复，即断开处的节点试图修复断开的活跃路由，如果一次修复尝试失败则由源节点重新发出RREQ查找路由。当发现链路断开后，如果断链处的上游节点与目的节点之间的距离大于MAX-REPAIR-TTL跳[6,7]，则上游节点发送一个RERR(Route Error)到源节点以启动全局修复；否则该节点启用生存时间比较小的RREQ广播来局部修复路由。如表1所示：
表1 RREQ格式
局部修复与全局修复的RREQ格式相同。Originator代表泛洪发送RREQ消息的节点。
J, R: reserved for multicast
G: Gratuitous RREP flag
D: Destination only flag (indicates only the destination may respond to this RREQ)
U: Unknown sequence number
2 局部修复引发的竞争问题
由于局部修复通常是自发的并且是分散的，这就很难把握修复时其他链路的状况。如果路由协议既有全局修复机制又有局部修复机制(例如AODV)，则在全局修复和局部修复之间也可能会产生冲突。这种竞争会对路由修复产生负面影响。产生这种竞争的时间条件如图1所示：
图1 局部修复引发竞争的时间条件
当某些节点移动较快时，产生的断路故障可能会触发多个修复进程。若这时有两个局部修复发生在同一条路由线路，临近目标节点的某些节点可能会收到两个RREQ消息，竞争冲突也就产生了。这种冲突通常会导致局部修复失败并产生冗余的无效路由。如图2所示：
图2 RREQ（M1）被丢弃过程
S为源节点D为目的节点，S到D之间有一条线路S-M1-M2-M3-M4-D，数据由此路由线路传送。当M1-M2和M3-M4中断时，M1节点发起一个局部修复，泛洪广播RREQ(记为RREQ(M1))，几乎在同一时刻，M3节点同样发起局部修复，泛洪广播RREQ(记为RREQ(M3))。RREQ(M3)首先到达节点N3，N3在路由表中增加一条以源节点S为目标的反向路由字段，其中M3为此条路由的下一条节点。然后，N3继续泛洪广播RREQ(M3)。很快，RREQ(M1)消息也到达N3节点。然而，由于此时N3存有的以S为目标的路由字段的SrcSeqNo和RREQ(M1)的相等，并且RREQ(M1)的Hop Count(由M1到S的跳数)不小于此条路由字段的Hop Count，因此RREQ(M1)被忽视并且丢弃。
这种情况导致的后果如图3所示：
图3 RREP无法传送到源节点
节点D收到RREQ（M3）后返回RREP消息，当RREP依次由N5、N4、N3、M3传送到M2时，因为由源节点S到M2的路由线路很可能尚未修复，因此使得此次局部修复失败。在稍后的时间，M1将会注意到它的局部修复失败并通知源节点S。最终，S会以较大的TTL值泛洪发送RREQ消息启动全局修复。这样不仅增加了延时，而且，在全局修复完成之前，数据传输停止，一条冗余的路由线路M3-N3-N4-N5-D会一直被维护。
3 优化策略
竞争问题会使得离源节点最近的损坏链路无法修复。因此，当竞争冲突发生时，赋予离源节点最近的（即离目标节点最远）损坏链路最高局部修复优先级，其他局部修复赋予较低优先级，或者直接丢弃。
每一个节点要有以下功能：
有一个Repair Control Table(RC Table)，记录修复进程的历史管理信息。
竞争侦测功能
竞争解决功能
在局部修复消息中增加以下信息：
指定源节点和目标节点
指定新路由线路
指定路由中损坏链路位置
RREQ消息格式如表2所示：
表2 改进AODV RREQ消息格式
阴影部分是与AODV不相同的部分。OD hop count是由侦测到链路损坏的节点(即Originator)到目的节点的跳数。在全局修复的情况下，OD hop count赋值INFINITY以区分局部修复。
RC Table消息格式如表3所示：
表3 RC Table格式
当节点收到局部修复消息后，将损坏链路的位置信息存储在RC Table中。根据RC Table，节点判断同一条路由是否执行了多个局部修复进程。对于正在修复的路由线路，节点收到一个RREQ消息，若此消息中的Destination IP与该节点RC Table存有的Destination IP相同，且具有相等的Destination Sequence Number，则认为冲突发生。那么必须对这些有冲突的修复进程分配优先级。如果此修复进程是全局修复，则赋予其较高优先级。如果是局部修复且其OD hop count比RC Table存有的OD hop count大(即在之前某一时刻进行的局部修复的OD hop count)，则同样赋予其较高优先级。否则赋予此修复进程较低优先级。有较高优先级的RREQ随之将更新相应的路由表项及RC Table。修复策略的算法框图如图4所示：
图4 修复策略的算法框图
4 仿真实验分析
选择OPNET modeler 10.5[8]作为仿真工具，对AODV和改进后的AODV进行仿真测试。为表述方便，现做如下定义：
GR AODV：仅具备全局修复机制的AODV协议。
Proposed Method 1：具备全局修复和局部修复机制的AODV协议，即RFC 3561中的AODV协议。
Proposed Method 2：具备全局修复和局部修复机制，且能够避免竞争冲突的AODV协议，即本文提出的改进后的AODV协议。
仿真的基本参数设置如表4所示：
表4 仿真的基本参数设置
对以上描述的几个协议分别收集以下性能评价参数来比较分析：路由修复开销、数据包投递率和端到端平均时延，分别定义如下：
数据包投递率：数据包到达目的节点次数/数据包发送次数
端到端平均时延：到达目的节点时间-发送时间
随着网络吞吐量的增大，3种路由算法的修复开销逐渐增大，如图5所示：
图5 路由修复开销仿真结果
其中GR AODV的开销最大，这是因为GR AODV并不具备局部修复能力，每次断链都会从源节点发起全局修复；Proposed Method 1的修复代价也很大，在达到69kb/s时甚至和GR AODV一样；而Proposed Method 2的代价最小。3种路由算法在网络负载加大的情况下，数据包投递率呈下降趋势，而端到端平均时延逐渐增加，如图6图7所示：
图6 数据包投递率仿真结果
图7 数端到端平均时延仿真结果
其中Proposed Method 1的性能较差，在超过40kb/s时甚至不如GR AODV，这是因为Proposed Method 1虽然具备局部修复机制，但由于不能避免竞争冲突，使得当多处断链频繁发生时，离源节点较远的节点发出大量无用的数据包，影响投递率，并且延后能够成功修复路由的其他局部修复或全局修复，增大端到端平均时延。由于Proposed Method 2能够有效避免由于竞争问题导致的局部修复失败，并减少无效的数据包，因此其无论在数据包投递率还是端到端平均时延都有较好表现。
5 总结
局部修复相对于全局修复能够以较小的开销达到修复损坏路由的目的。但是，另一方面，全局修复却可以得到跳数最少的路由线路。因此，AODV采取了全局修复和局部修复相结合的方式。但是，由于AODV没有解决竞争冲突机制，因此，使得其在处理多处断链时性能较低。本文在原有的AODV路由算法基础上，提出了一种新的改进的局部修复算法，它采用分配每个修复进程优先级的方法来避免竞争问题。从仿真的结果看，新的修复机制降低了路由修复开销和端到端平均时延，提高了数据包投递率，使路由协议的性能有所提高，对于深入了解Ad hoc网络的路由机制具有一定的意义。
参考文献：
[1] 郑少仁,王海涛,赵志峰等.Ad Hoc网络技术[M].北京,人民邮电出版社,2005:1-13,64-79
[2] Johnson, D.B.. Maltz D.A, “Dynamic Source Routing in Ad Hoc Wireless Networks”[M], in Mobile Computing, ed. By T.imielinski and H.korth, Kluwer Academic Publishers, 1996.
[3] RFC3561，Ad hoe On—Demand Distance Vector(AODV) Routing[S]．
[4] .Toh, C.-K “Associativity-based routing for ad-hoc mob-ile networks”[J], Wireless Pers.Commun.J., vol.4, no.2, pp.103-139, March 1997.
[5] Srinath Perur, Abhilash P. and Sridhar Iyer, “Router handoff: a preemptive route repair strategy for AODV”[M], IEEE Intel. Conference on Personal Wireless Computing, New Delhi,Dec, 2002.
[6] 袁培燕,李静,史向阳.AODV路由协议局部修复机制的改进[J]. 河南师范大学学报(自然科学版),2008,36(5):29-31
[7] 葛文英,李腊元.AODV路由协议局部修复机制的优化与仿真研究[J]. 武汉理工大学学报.2007,31(6):464-467
[8] Anipakala Suresh .Performance Analysis of Ad hoc On-demand Distance Vector routing (AODV) using OPNET Simulator[M], Bremen, 11th April 2005
Improvement of Local Repair Mechanism in AODV Protocol
Han Lincheng, Chen Xichun
(Combat Training Experiment Center, Mechanized Infantry Academy, Shijiazhuang 050083, China)
AODV protocol is a typical on-demand routing protocol in Ad Hoc networks. Based on the detailed analysis of the mechanism of local repair in AODV, this paper proposes an improved method to solve the race problem caused by local repair, that when multiple open circuit occurs, priority will be distributed to every repair process to avoid the problem of competition. Simulations show that the proposed mechanism can effectively avoid the competition and improve the network performance.
AODV; Ad Hoc; Local Repair; Race Problem; Priority
1007-757X(2016)04-0065-03
TP183
A
（2015.09.07）
韩林呈（1984-），男，河北石家庄人，机械化步兵学院教研部作战训练实验中心，助教，硕士，研究方向：计算机仿真及人工智能，石家庄，050083。
陈喜春（1971-），男，河南新乡人，机械化步兵学院教研部作战训练实验中心，讲师，硕士，研究方向：计算机仿真，石家庄，050083。
