Ad Hoc网络是一种特殊的无线移动网络，网络中的所有节点地位平等，无需设置任何中心控制节点，既可以快速、自动地组成一个独立的网络运行，也可以作为当前具有固定设施网络的一种补充形式[1]。在军事、抢险救灾等领域应用前景广阔。

与现有的有线网络和有基站的无线网络有很大不同，Ad Hoc网络无中心、自组织、动态拓扑和能量有限的特点，使得现有的路由协议(RIP、OSPF)不再适应Ad Hoc网络,因此路由技术一直是自组网的研究重点之一。目前主要有按需路由和表驱动路由两类[2]，其中按需路由协议不必维护到达所有节点的路由,有效地节省了网络资源，能够较好地适应节点移动带来的动态拓扑问题，得到了广泛应用，其典型代表是AODV[3-4]协议。本文在AODV路由协议的基础上，提出基于链路中断预测的路由算法(RP-AODV), 能够降低广播开销,提高网络性能。
1 研究现状
针对路由可能发生中断的问题，路由修复算法被提出。最简单的修复算法是由源节点重新发起新的路由发现过程，显然这会带来极大的网络开销。参考文献[3]认为路由断裂时，断裂处上游的节点会率先发现路径失效，此时直接由该节点发起到目的节点的路径修复过程。如果收到目标节点的应答，则说明路径重建成功；如果路由发现规定时间内没有收到目的节点返回的RREP，则向其上游节点发送该目的节点的RERR，直到通知到该路由的源节点，然后再由源节点进行新一轮的路由发现。
参考文献[5]提出一种两跳范围局部修复改进算法，当节点A到节点B失效时,在断链的附近可能存在A、B的邻居节点，因此由断链的上游节点发送两跳路由请求分组寻找下一跳节点B，使得修复限制在两跳范围内，路由开销将会减少，寻路时间减短。
2 基于链路中断预测的AODV路由算法设计
2.1 算法思想
从降低开销的角度，最理想的是路径不中断，但因为节点的移动性，即使采用稳定路由策略获取的路由也会发生路径中断。而当路径中断之后再去修复，都会带来较大的额外开销，同时增大时延。如果在路径中断之前，能够预测到即将中断，提前采取措施寻找备用路由，则可以实现平滑的路径切换，当链路中断不可避免时，不必返回源节点搜索，而是逐层由上游节点展开局部搜索，在保证传输时延的同时使得路由开销最小。
节点的移动导致节点间链路中断，但在较短时间内，节点并不会走远，仍在原位置附近，在较短时间内节点的活动范围也往往是以短途和小范围为主[6-7]。同时链路中断处也存在其他的邻居节点。因此当链路中断时可以在断点附近展开链路修复，没必要全网重新开始新的路由。如图1所示，链路中断一般有多种情况，图1(a)中源节点S和目的节点D，经由A、B、C三个中间节点组成一条链路。随着节点的移动，链路出现断裂，如图1(b)所示，B节点移动出了A的覆盖范围，A与C之间失去了联系，但是存在E节点可以同时连接A和C，则可以选择E取代B。如果E节点不能同时覆盖到A和C，但可以覆盖到A和B，如图1(c)所示，则可以在原链路中增加一个E节点，链路变为S-A-E-B-C-D。如果B和E都移动出了A的覆盖区域，如图1(d)所示，则A到下游节点的链路完全中断了，必须由它的上游节点开始新的链路搜索。

基于这样一种思想，将路由维护的过程分解为两个步骤：(1)监听路由中各个链路的联通情况，判断链路是否会中断或者是否有更短链路的出现。(2)寻找保持链路联通的备用节点，当链路出现中断时，备用节点迅速启动。如果找不到可用路由，则逐层由更上游节点发起路由发现过程，而并不是返回源节点。
2.2 算法设计
链路的中断是由节点的移动导致的，但链路的中断最终是由信号质量下降引起。因此判断链路中断最有效的方法是监测链路信号质量。无线信号在传输过程中存在着慢衰落和快衰落，多种因素会引起信号质量的起伏，为了避免频繁的链路切换，可以取一个时间窗口，在这个窗口中取均值，作为判断依据。
AODV的路由机制中上游节点路由表中存有下一跳节点的信息，而下游节点不知道上游节点，这就决定了当链路中断时，只能由上游节点决定去寻找哪个节点。而不在原链路上的节点可以监听到周围链路的信号质量，能够知道自己是否可以修补链路 (如图1(c)中的情况)，但是无法知道自己何时插入原链路，也无法知道是否可以缩短原链路(如图1(b)、图1(e)的情况)。因此需要修改AODV协议中的路由表，使之存有下面两跳路由信息，即存放下游链路的两个节点，这样周围节点可以通过检测周边链路信号情况，判断自己是否处在有用链路上。
根据链路断裂的不同情况，路由维护分为以下几类：
(1)由周围节点自己判断是否能够缩短原链路长度，如果能则由该节点主动联系上游和下游节点，确认后启动新链路。
(2)链路可能断裂处的上游节点通过监听反向路径的信号质量，判断链路当前的状况，然后向周围节点发起备用节点查询，找到后确认新链路。
　(3)周边没有备用节点的情况，由上游节点向更上游节点发送断链请求，从而启动新的路由搜索过程。在搜索备用节点的过程中，采用扩展环的方法，在网络层分组的报头部分设计一个字段TTL，限定为3，表示分组可以被转发的次数，收到该分组的节点每次将TTL值减1，减至0则停止转发。
2.3 算法流程
　路由维护的过程主要由链路上游节点和周边节点完成，通过监听各个链路质量，判断链路是否会中断或者是否有更短链路的出现，然后寻找保持链路联通的备用节点，并迅速启动。找不到备用节点时，链路会断裂，此时启动ERS算法在3跳之内进行局部路由修复。如果仍然不成功，则由更上游的节点启动路由发现。算法流程描述如下：
(1)节点从收到数据包中获取下游两跳节点路由信息;
(2)监听信号质量，更新时间窗口信息，计算均值，并与设定的阈值比较，判断链路中断概率;
(3)上游节点判断链路可能中断则会启动ERS搜索， 发起路由修复过程;
(4)周边节点判断可以接续原链路或者缩短路由长度，
则会向上下游节点发送应答;
(5)上游节点收到应答信息，则更新路由表；在规定时间内没有收到应答，则会向更上游中间节点发送重新路由请求，启动新的路由发现过程。
3 仿真分析
3.1 仿真模型
用NS2作为仿真软件进行了模拟实验，将本文提出的基于链路中断预测的AODV算法(RP-AODV)与标准AODV协议进行比较，重点关注数据包投递率、归一化路由开销和端到端的平均延迟等3个性能指标。
数据包投递率：成功到达的数据包和全部发出数据包的比率。
归一化路由开销：每发送一个DATA数据分组需要的控制消息分组数，其中路由分组每一跳的传输均认为是一个新的控制消息分组，反映了网络的拥塞程度和路由效率。
端到端的平均延迟：每个数据包从源节点到目标节点间的传送时延。
在仿真场景中，100个节点随机分布在1 500 m×1 000 m 的矩形区域内，每个节点采用IEEE 802.11无线网络接口，无线传输半径为250 m，单一增益的全向天线，信道容量为2 Mb/s。每次仿真随机选择10对源-目的节点传输数据，通信源是CBR流，数据包大小为512 B，每秒发送2个包，队列长度为50。采用Random Way Point 运动模型， 节点最大移动速度Vmax分别为5 m/s、10 m/s、15 m/s、20 m/s、25 m/s，暂停时间为30 s，实验反复运行50次，每次仿真1 000 s，实验结果取平均值。
3.2 仿真结果分析
3.2.1归一化路由开销
　由图2可以看出，在不同的最大移动速度下，RP-AODV的路由开销最小，总体上比AODV减低了40%。说明通过新算法有效控制了链路中断的次数，减小了路由发现的频次，从而降低了路由开销。在速度较低时路径中断的概率较小，随着速度的增加，节点的移动性增强，路径中断概率增大，路由修复过程出现频繁，路由开销都有所增加，但是RP-AODV优势显现。当节点移动速度超过20 m/s以后，优势缩小，主要是因为节点的移定性增强之后，链路预测和备份链路的选择的准确性也会随之下降，增加了路由开销。总体上来看，RP-AODV相比传统AODV算法归一化路由开销降低40%左右。

3.2.2 端到端平均时延
图3给出了平均端到端时延随节点不同移动速度的变化情况。随着节点移动速度的增加，RP-AODV和传统AODV协议的端到端时延都在增加，其中AODV增加的幅度更为明显。这是因为节点移动速度增加以后，链路断开的几率增大，路由修复频次增多，而路由修复过程中数据传输中断，数据包端到端时延增加，RP-AODV算法通过链路预测，启用备用节点，尽量减少路径断开的几率，即使链路断开，也会采用局部修复的方法，降低了路由修复时间，从而减小了端到端时延。总体上来看，RP-AODV相比传统AODV算法端到端时延降低25%左右。

3.2.3 数据包投递率
从图4中可看出，与传统AODV算法相比，改进的RP-AODV算法数据包投递率有所提高，在节点最大移动速度不大时，两者相差不大，这是因为节点移动较弱时，链路断开的几率较小，发起路由修复次数较少，数据包投递率差别不大。当最大移动速度较大时，传统AODV算法和算法投递率都有所下降，但RP-AODV仍然优于传统AODV。这主要是因为节点移动性提高之后，链路断开的几率增大，路由修复频次增多，修复不成功的几率也随之增加，从而导致数据包投递率有所下降。在路由修复过程中，RP-AODV能够快速地找到备用节点，尽最大可能地保持原路由有效，减少了路径中断次数，从而提高了数据包投递率。

本文针对传统AODV路由协议中的路由修复方法开销大、时延长这一问题，设计了一种基于链路中断预测的改进算法。通过监测链路质量，预测链路中断概率，及时启用备用节点，尽量避免路由修复；而当链路中断时，采用逐层由上游节点发起的局部路由搜索，减小控制开销的波及范围。算法在经典的AODV协议上实现(称之为RP-AODV)，并用NS2模拟软件进行了仿真。仿真结果表明，在多种场景下新算法都降低了路由开销，有效地提高了网络性能，与传统AODV相比控制开销降低了40%，端到端时延减少了25%。
参考文献
[1] CHLAMTAC I,CONTI M,LIU JN. Mobile Ad Hoc networking: imperatives and challenges[J]. Ad Hoc Networks,2003,1(1):13-64.
[2] 李世宝, 洪利. 基于距离预测的移动自组网路由发现算法[J].通信学报， 2010,31(11):180-187.
[3] PERKINS C, BELDING-ROYER E. AODV Ad Hoc Ondemand distance vector Routing[S]. The Internet Engineering Task Force, IETF, RFC 3561, 2003.
[4] NI S Y, TSENG Y C, CHEN Y S. The broadcast storm problem in a mobile ad hoc network[A]. the Fifth Annual ACM/IEEE International Conference on Mobile Computing and Networking (MOBICOM 99)[C]. Seattle, Washington, 1999:151-162.
[5] 丁绪星,吴青,谢方方.AODV 路由协议的本地修复算法[J]. 计算机工程, 2010,36(6):126-127.
[6] GONZALEZ M C, HIDALGO CA, BARABASI A L. Understanding individual human mobility patterns[J]. Nature, 2008,453:779-782.
[7] RHEE I, SHIN M, HONG S, et al. On the levy walk nature of human mobility[A]. INFOCOM 2008:the 27th Conference on Computer Communications[C]. Phoenix, AZ, 2008:924-932.