Ad Hoc多径路由算法

高永贵，龙昭华，张 林

（重庆邮电大学计算机科学与技术学院，重庆400065）

0 引 言

由于Ad Hoc网络连接的不稳定性和动态的网络拓扑结构，单路径的网络路由协议已不能满足网络的性能需求［1］。由于多径路由的优势，其成为当前Ad Hoc网络中研究的热点，多径的主要思想是在一次路由进程中，发现多条可用路径，利用多条路径进行并行或备份的方式传输数据，提高网络的稳定性和资源利用率。使用多径路由传输业务数据，一定程度上减少了数据传输在带宽方面的限制；随着多媒体业务在Ad Hoc网中广泛应用，多路径在延迟和链路稳定性方面更满足多媒体业务的QoS需求［2］。

如果路由的开销过大，多径的优势就会明显减弱［3］，因此开发更简洁、高效的多径路由协议有着重要意义。同时动态的拓扑结构导致多次路由发现过程耗费大量时间和网络资源，不利于当前的多媒体业务的需求。信息熵作为不确定性因素的度量［3］，和Ad Hoc中移动节点的不确定性移动有着相似的对应关系，将熵的概念应用到Ad Hoc网络中，对于发现可靠性的路径有着显著作用。本文在分析Ad Hoc网络特点的基础上，利用熵与自组织网络的共性分析问题，基于高效、简洁多径路由协议的开发思想，提出了一种联合熵的开销最小多径路由协议ENDMAODV，该算法有效改进了分组投送率、平均控制开销和端到端延迟。

1 相关工作

自组织网络可以表示为带权的有向图G（V，E）［4］，其中V 表示移动节点的集合，E 表示可连接的节点间的链路集合。在研究Ad Hoc网络时，使用R 表示节点间链路的属性结合，如i，j两可连接节点，则＜i，j＞链路的属性可表现为带宽、时延、代价、链路持续时间等等。

Perkins、Belding－Roryer等人提出了AODV 路由 （基于距离矢量的按需路由）协议［5］。AODV 是一种单径路由协议，主要有路由发现和路由维护2 个阶段和RREQ、RREP、RRER、HELLO 这4 种报文组成。AODV 实质上是DSR［6］和DSDV［7］的结合，借用了DSR 中路由发现和维护的机制，以及DSDV 逐跳路由和目的节点序列号的周期更新机制的思想，以DSDV 为基础，结合DSR 按需的思想进行改进而来。AODV 中每个节点隐式保存了路由请求和应答的结果，利用扩展环搜索的思想限制RREQ 的传播范围。AODV 使用目的节点序列号实现了路由的无环，并提高了算法的收敛速度。

AOMDV （按需多径路由）协议［8］是基于AODV 扩展的多径路由协议，AOMDV 修改了AODV 的路由发现方式并引入了广播跳数的概念来替换原来的跳数。仍使用目的节点序列号来确保无环和路由更新。为了存储多条可用的路由路径，参照AODV 的选择算法在多条无环不相交路径中进行选择，每一个目的节点路由中都记录了下一个转发列表和跳数。

MSR 协议 （分离多径路由）［9］是基于DSR 的扩展的一种多径路由协议，该算法能够发现并使用最大不相交的2条路由路径，并选择其中一条性能优秀的路径作为传输的主路由，另外一条作为备份路由使用，这样一种主从备份的方式，有效的提高了路由利用率，减少了启动路由发现的次数和网络时延，提高了网络的整体分组投送率。

2 路径稳定性度量

B.An和S.Papavassiliou最早在移动自组织网络中应用熵评价路径的稳定性［3］。由于自组织网络的节点移动性，找到相对稳定的路由路径能够显著的减少路由重构的时间、减少了时延，进而对于业务的传输有着重要的作用。在移动Ad Hoc 网络中，网络节点的状态可以用节点位置Positon（i）和速度V（i）来表示。可以这样认为对于网络中的任意节点m，其特征向量am，n表示如下所示

式中：Position（m，n，t）——m 节点和n 节点的相对位置。V（m，n，t）——m 节点和n 节点在t时刻的相对速度。二者的计算表示形式如下 （执行向量运算）所示

基于上述，则构造可连接移动节点对（m，n）在时间间隔内的特征向量如下所示

式中：R——节点的传输半径，N ——在Δt时间间隔内离散时刻ti的总个数，即每间隔时间Δt，相对位置向量和速度向量被更新和计算的次数。基于此，我们定义熵

在式 （5）的基础上，进行求导去负对数的方法，得到式 （6）

式（6）可以看出，P’（m，n）的值越小，节点对（m，n）之间路径越稳定，由此得到评价路径稳定性的度量。

3 基于AODV的多径路由算法

3.1 修改的控制结构及路由建立

本文在深入研究AODV 路由协议的基础上，为了实现使用最小开销找到源目的节点对之间的多条节点不相交路径路由，对AODV 协议中的RREQ 控制包结构、RREP控制包结构和节点缓存路由表信息进行了修改，同时修改路由表的相关信息，使其有能力存储多条路径和周期性的熵的计算值。（其中文中选择的多路径条数条数为2）。

1) 跟踪精度提高。本文算法通过实时修正模型转移概率，使与目标运动匹配的模型概率增大，加快模型切换速度，最终提高了精度，如图1所示。从表2可以看出，在全航路，距离精度提高8.2%，速度精度提高12.9%；尤其是在匀速段，速度精度提升26.9%。另一方面，在图2中，细实线表示IMM3-EKF算法，由于IMM3中存在模型竞争，实际滤波效果比本文算法还差。

修改的RREQ 控制包结构，见表1。

表1 修改的RREQ 控制包结构

修改的RREP控制包结构，见表2。

表2 修改的RREP控制包结构

表3 中，S＿address和Broadcast＿id 标志位来源于RREQ 控制包，作为每次请求的独立标示。Jusr＿flag标志位的初值为FALSE。在本算法中，为了确保发现节点不相交的多条路径，规定，任何中间节点不回复RREQ 路由请求包，而是按照AODV 协议中没有目的节点路由的中间节点的方式和后文算法1的方式处理RREQ 控制包。算法2显示RREP控制包的处理过程。

表3 节点处增加的Justtable结构

算法1 RREQ 控制包处理进程

在执行算法1之前，当节点有数据需要发送时，首先检查是否缓存有到目的节点的有效路由，如果有，则直接发送。启动路由发现过程，初始化RREQ 包，Justtable表和缓存路由表。算法2中，当源节点收到RREP 路由控制包时，将缓存这些RREP 包，等待时间T，等待时间结束后，前所有收到的RREP 包按照Entropy 字段进行排序，从中选择Entropy字段最小的2条路径。

算法2 RREP控制包处理进程

图1中，结合具体的实例简单描述了算法的执行过程。如图1所示，假如S为源节点，D 为目的节点，当S有数据需要发送时，启动路由发现过程，洪泛RREQ 包，根据算法1，中间节点或是丢弃RREQ 或是更新熵字段的值并广播RREQ，假如当目的节点D 在t1时刻收到了来至节点I的RREQ 包，目的节点初始化RREP1包，并通过反向路径D－＞I－＞H－＞B－＞S传播，当中间节点收到RREP，检查Just＿flag 标志位是否为FALSE，是，则重置为TRUE，并建立正向路由，形成了一条S－＞B－＞H－＞I－＞D 的路由路径。假如D 在t2时刻收到了来至J的RREQ 包，初始化RREP2包，同上建立了S－＞A－＞F－＞J－＞D 的路由路径。在t3 时刻，D 收到了来至K 的RREQ 包，D 初始化RREP3包，RREP3包通过K 到达J，节点J检查Just＿table标志位为TRUE，则认为收到了重复的RREP包，丢弃RREP3。在t4时刻，节点D 收到了来至M 的RREQ 包，初始化RREP4包，同上建立了S－＞C－＞E－＞L－＞M－＞D 的路由路径。

图1 多径路由发现过程

当源节点S在等待的T 时刻内，收到了多个 （此处是3个）RREP包，按照RREP中的Entropy值进行排序，选择其中最小2条路径。

3.2 多径路由的维护与失效

在上述的多径路由选择中，选择熵值最小，也即是最稳定的路径最为主路径，另外一条作为从路径，形成主从备份的路由形式。

路由差错报告阶段，当正在进行的数据传输的链路断开时，并不立即发送RRER 控制包进行差错报告，而是节点检测是否存在第2条路由，若存在，则将数据传输链路切换到另外一条链路，若不存在第2条路由或第2条路由断开或失效，则发送RREQ 控制包，通知受影响的节点，同时启动路由发现过程。图1中，当正在传输数据的路径S－＞A－＞F－＞J－＞D 中J－＞D 链路断开时，并不立即启动RRER 过程，而是切换路径为J－＞K－＞D，进而形成S－＞A－＞F－＞J－＞K－＞D 路径进行传输，当此路径再次断开时才启动RRER 过程。

3.3 正确性证明

定理 选择的路由路径是无环的

证明：算法是在AODV 路由协议的基础上进行改进，AODV 协议RREQ 阶段的无环性保证了该算法RREQ 阶段的无环性。当节点收到路由的RREP应答包后，检查Justtable表中的Just＿flag二进制位字段，看是否被置位，如被置位则丢弃相应RREP 控制包；否则保存记录转发RREP控制包。由此看出，该算法选择的路由路径是无环的。

4 仿真分析

为了评价文中提出的路由算法的有效性和性能。在NS2［11］仿真环境下，实验中，20 个节点分布在1000 m×1000m 的场景中，节点最大移动速度为10m／s，数据包的大小为512bytes，数据源是CBR，MAC 层使用802.11，仿真运行时间500s，节点的传输范围为200m，节点按照Waypoint模型随机运动。主要从路径重构次数、平均分组投送率和平均控制开销、端到端时延4个方面来分析 （如式7）和验证本文提出的ENDM－AODV 算法

图2 中给出了AOMDV 和ENDM－ADOV 路由算法的路由重构次数的比较。可以看出，相对于AOMDV 而言，ENDM－ADOV 算法的重构次数明显减少，这是因为算法中基于熵找到了相对稳定的2条路径，同时另外一条路由作为备份路由使用，只要当2条路由同时失效的时候，才启动路由发现进程，如此一来，进一步减少了路由重构次数。

图3给出了在不同的移动速度下AOMDV 和ENDMAODV 算法的分组投送率的比较，可以看出，随着节点移动速度的增大，分组投送率都持续下降。总体ENDM－AODV算法有着明显的优势。这是因为中间找到了多条路由路径（可能超过2条）同时选择相对较可靠的路径进行数据传输，整体上提高了ENDM－AODV路由协议的分组投送率。

图2 路径重构次数比较

图3 分组投送率比较

图4给出了平均控制开销的比较，分析2种不同的算法看出，ENDM－AODV 使用简单的标志位信息进行控制包传输中的比较与处理，相对于AOMDV 而言减少了开销信息，且在路由维护阶段，中间节点可能存在2条到目的的路径，一旦某条出现问题，则可以切换到另外一条，减少了修复的开销。

图4 平均控制开销的比较

图5给出了2种协议的端到端时延的比较，可以看出，随着移动节点的速度增加，2 种算法的端到端的时延都增加较快。从图中还可以看出对于AOMDV 算法，ENDMAODV 协议随着节点移动速度的增加端到端的要低。这是因为在很小的开销情况下，ENDM－AODV 就获得了较稳定的路由路径。

图5 端到端时延的比较

5 结束语

本文在深入分析AODV 单径路由协议的基础上，通过引入标志位的方式，设计了一种多径路由算法ENDMAODV，算法中结合信息熵的概念，在发现的多条路径中选择稳定性最好的2条路径形成主从备份路由路径。简单的标志位处理方式，极大的较少了路由的整体开销，信息熵的引入，减少了路由重构的次数，进而能更好的保证动态拓扑的Ad Hoc网络中数据传输率。仿真的结果表明，ENDM－AODV 协议优化了分组投送率、端到端延迟和平均节点控制开销。ENDM－ADOV 协议的提出为设计和优化多径路由协议提供了一种新的思路。

在未来的研究中，将结合多QoS的相关概念和节点移动模型更加全面的考虑和优化算法在自组网中的性能，提高组织网的网络利用率。

［1］Chhagan LalA，Vijay Laxmi.A rate adaptive and multi－path routing protocol to support video streaming in MANETs［C］／／Proc of International Conference on Advances in Computing，Communications and Informatic，2012：262－268.

［2］Ron Banner，Ariel Orda.Multi－path routing algorithms for con－gestion minimization ［J］.IEEE／ACM Trangsactions on Networking，2007，15 （2）：413－418.

［3］SUN Baoling，GUI Chao.Multi－path on－demand routing and routing algorithm based on entropy in Ad Hoc［J］.Journal of Software，2008，19 （12）：112－120 （in Chinese）. ［孙宝林，桂超.Ad Hoc网络多路径需求路由及路径熵选择算法 ［J］.软件学报，2008，19 （12）：112－120.］

［4］LI Mingzhe.Graph theory and algorithms［M］.Beijing：China Machine Press，2010：1－242 （in Chinese）.［李明哲.图论及算法 ［M］.北京：机械工业出版社，2010：1－242.］

［5］Midhun Kalyan Anantapall，Li Wei.Multi－path multi－hop routing analysis in mobile Ad Hoc networks［J］.Wireless Netw，2010，16 （1）：573－575.

［6］Li Ming，Prabhakaran B.On supporting reliable Qos in multihop multi－rate mobile Ad Hoc networke［J］.Wireless Netw，2010，16 （1）：813－827.

［7］Hemanth Narra，Cheng Yufei.Destination－sequenced distance vector （DSDV）routing protocol implementation in ns－3［C］／／Proc of 4th Internation ICST Conference on Simulation Tools and Techniques，2011：439－446.

［8］LIU Jingwei，LEI Tao.The research and design of multi－path routing protocol in Ad Hoc ［J］.Computer Engineering and Design，2007，28 （17）：1415－1418 （in Chinese）. ［刘经纬，雷涛.Ad－hoc网络多径路由协议的研究与设计 ［J］.计算机工程与设计，2007，28 （17）：1415－1418.］

［9］Bahador Amiri，Hamid R Sadjapour.Outage optimum routing for wireless Ad Hoc networks ［C］／／Proc of 7th Internation Conference of Wireless Communications and Mobile Computing，2011：1576－1587.

［10］Chen Quanjun，Salil S Kanhere.Adaptive positon update for geographic routing in mobile Ad Hoc networks ［J］.IEEE Transactions on Mobile Computing，2013，12 （2）：489－501.

［11］Teerawat Issariyakul，Ekram Hossain.Introduction to Network Simulator NS2 ［M］.Springer Publishing Company，2010：1－400.