基于AODV的平面多径路由协议

姬兴民, 李金龙, 卢光跃, 冯景瑜,2

(1. 西安邮电大学 无线网络安全技术国家工程实验室， 陕西 西安 710121;2. 中国科学院大学 计算机与控制学院, 北京 100049)

基于AODV的平面多径路由协议

姬兴民1, 李金龙1, 卢光跃1, 冯景瑜1,2

(1. 西安邮电大学 无线网络安全技术国家工程实验室， 陕西 西安 710121;2. 中国科学院大学 计算机与控制学院, 北京 100049)

将AODV单径路由修改为多径路由能提高随建即连网络(Ad Hoc)的容错性和稳定性。在洪泛广播时，节点首次收到路径请求才会转发数据，重复收到则不转发，避免出现路由环路。在数据转发时，以多个邻居节点为上跳节点，形成多路径传输，避免负载过大出现路径断裂。采用NS2进行仿真，结果显示多径路由与AODV相比端到端时延降低了30%～50%，剩余能量提高了20%～40%，另外通过吞吐量的比较发现，多径路由使能量的分配更加均衡，从而使网络的稳定性得到提高。

路由协议；负载均衡；随建即连网络(Ad Hoc)

Ad Hoc网络的路由协议主要由先验式和反应式两种组成，先验式路由协议里面，最经典的是DSDV路由协议[1]，而在反应式中最经典的是AODV路由协议[2]和DSR路由协议[3]。反应式路由协议相对先验式路由协议虽然数据报传递时延大，但路由开销较小、分组投递率高，更符合目前的自组网络[4]。三种经典路由协议中，AODV路由协议在剩余能量、传输时延、路由开销、吞吐量等方面性能更加优化，一直是Ad Hoc网络研究的重点。

AODV协议的节点与节点之间通过单路径单向转发数据，属于简单的端到端的通信[5],若在此过程中发生数据包丢失[6]、节点失效、路径拥塞[7]等问题，数据传送将无法完成。AOMDV路由协议[8]是基于AODV单经路由协议提出的一种平面多径路由协议。分析比较AODV协议和AOMDV协议可知[9]，AOMDV协议的路由发现频率、平均时延都优于AODV协议，但是归一化路由开销却明显增大。多径路由协议的研究目前还不够完善，需要进一步研究与改进。

为了解决AODV路由协议单路径传输问题，本文拟基于负载均衡原理[10]，提出一种新的平面多径路由协议 (Flat Multiple Path Routing Protocol, FMR)，以改善单径路由的缺点，提高Ad Hoc网络的性能。

1 AODV路由协议分析

AODV路由协议是反应式路由协议，也称为按需矢量路由协议，它综合使用了先验式路由DSDV目标序列号和反应式路由DSR的路由发现技术，其过程主要包括路由发现和路由维护。

路由发现过程是源节点与其他节点通信，但没有到该节点的路由时，广播路由请求RREQ，假设另外节点接收RREQ，先观察有没有接收过RREQ，若有，则删除，若无，则通过RREQ创建一个反向路由。若中间节点已经有路由到目的节点，那么就给源节点发路由应答RREP，如没有就广播这个RREQ。若RREQ的目的节点接收到RREQ，同样建立反向路由，然后向源节点发送RREP。路由维护的节点通过周期性的广播hello消息来确定链路状态，如果该节点连续3次收不到hello响应，那么认为链路被破坏，相应删除掉下一个路由信息，并发起路由错误报文(RERR)，通知相邻节点和上游节点删除目的节点不可达的路由信息。

AODV路由协议虽然已经相当完善，但它只是一种单径路由协议，无法适应Ad Hoc网络的实际动态拓扑的发展速度。

以下根据AODV协议的原理，给出一种多径路由协议的设计原理与实现过程。

2 基于AODV的多径路由协议FMR

2.1 算法原理分析

FMR算法是一种多径负载均衡分担的算法，相当于从源头到目的的多队列模型。在这种多队列模型中，如果路径上不交叉，网络中的节点的能量相对比较均衡。但如果多队列模型[11]出现了路径上的交叉，则会造成网络中局部的瓶颈现象。

根据路由路径稳定性的原理[12]，提出多径分担方法，假定一条路径由多条链路构成，先构造链路的权重因子s，然后是路径的权重因子Sp。链路的权重因子通过链路维持时间来获取。当两节点在彼此传输半径内，则路径的权重通过该链路的权重因子s积来判断。路径的负载均衡度由Sp来决定，Sp越大，代表路径的负载越大；Sp越小，代表路径的负载越小。

无线Ad Hoc网络的节点传输模型如图1所示。路径1是由节点A通过节点B、C、D将信息传送到节点F，假设节点A除了通过节点B、C、D将信息传送到节点F，还有路径2通过节点G、H到达节点F。每两个节点间的链路代表网络的有效链路，有效链路指双向链路，即组成链路的2个节点i和j在对方的覆盖范围内。Ri为节点i的辐射半径。

图1 邻居节点传输路径

构造节点i在时刻tk的位置为

pst(i,tk)=(xi,yi,zj),

(1)

节点i和节点j在时刻tk的位置向量为

pst(i,j,tk)=pst(i,tk)-pst(j,tk),

(2)

设节点i和节点j在时刻tk的坐标位置分别为[xi(tk),yi(tk)]和[xj(tk),yj(tk)]，则在T=tk-tk-1这段时间内，相邻节点的位置变化量为

Δsij=pst(i,j,T)=‖pst(i,j,tk)‖-‖pst(i,j,tk-1)‖,

(3)

其中‖pst(i,j,tk)‖为节点i和节点j在tk时的相对距离。取R=min{Ri,Rj},由图1可知

-R≤pst(i,j,T)≤R,

|Δsij|=pst(i,j,T)≤R。

(4)

设图1中区间(-R,R)上的链路权重因子

(5)

若将链路权重因子依次记为sk(k=1,2,…,n),从源节点到目的节点的负载均衡度

(6)

由式(6)知路径1的负载均衡度为

Sp=s1s2s3s4s5。

(7)

当路径2存在时，其负载均衡度为

Sp=Sp1+Sp2。

(8)

由于来自于节点A的负载是不变的，因多径的存在，路径1的权重被路径2分担，故在链路A-B-C-D-E-F的网络负载均衡度被减小,这说明多径的存在减轻了单路径的负载过重导致路径断裂的问题。

2.2 FMR路由协议的设计流程

多径路由协议的实现主要包括两个过程：基站到其他节点的泛洪广播过程，数据包转发和路由维护过程。

2.2.1 基站到其他节点的泛洪广播

节点接收路径请求广播包处理流程如图2所示。

当在监测环境中设置好网络节点以后，首先就是由基站先发起路由请求，为在数据传送至基站的多条路由作准备。路径请求的跳数如为第1次接收路径请求广播包，跳数为原来路径请求中的跳数字段加1。它可以被用来确定从基站到节点的距离，为以后的路由修复作准备。注意，节点在收到路径请求RREQ时，除了比较跳数，还比较节点的上一跳是否为自己，如果节点的上一跳为自己，则不添加此节点为自己的邻居，从而避免在数据发送过程中出现环路问题。

图2 节点接收路径请求广播包处理流程

2.2.2 数据包发送和路径维护

(1) 数据包发送过程

当组网完成之后，网路中的节点就开始向基站转发数据包。数据包转发分为二种情形。

情形1 节点本身作为源头发送数据，此源头选择跳数小于或等于1跳的邻居，从而形成上一跳的数据传输，则呈现多路径路由协议性能。

情形2 节点不为数据发送的源头，而仅只是转发的中继节点或基站。如果为基站，则进行接收此数据包；如果为中继节点，则以在广播过程中形成的上一跳为自己的目的地址，从而转发数据包。

(2) 路径维护过程

如图3所示，在节点发送数据包的过程中，当节点发现自己的上一跳失效时，则发送路径出错包请求，先将数据包缓存，让其它的网络节点中继。

图3 节点路径出错广播包处理过程

节点的路由修复，必须满足以下条件：首先，节点的跳数比发送数据源到基站的跳数少或相等；其次，为了避免环路问题，其上一跳不能为失效的节点。节点收到路径应答广播包的处理流程如图4所示。

图4 节点收到路径应答广播包的处理流程

注意，节点作路由修复的机制是使用中间节点作路由修复，发送路径出错的节点，选取第一次接收路径应答的源地址作为自己的上一跳。

3 仿真及结果分析

采用NS2进行仿真，主要涉及数据传输的吞吐量、节点端到端时延、节点剩余能量[13]等参数。

3.1 仿真参数设置

(1)场景设计：场景参数如表1所示。

表1 节点发送数据包到达基站参数设置

(2)脚本设计：基站成功的接收每个节点发送过来的数据包，来模拟网络的建立过程，初始能量为100 J。

3.2 节点发送数据到基站的仿真

(1) 端到端的时延对比

FMR与AODV端到端的时延对比情形如图5所示，从中可以看出，FMR与AODV相比，端到端时延更小。FMR侧重于多对一通信，而AODV侧重于一对一通信，其广播开销比较大，故端到端时延比较大。

图5 FMR与AODV端到端的时延对比

(2) 节点剩余能量的对比

FMR与AODV节点剩余能量对比情形如图6所示，从中可以看出，AODV寻找路径所花费的时间较长，路由控制包较多，每个节点都要发送查询路径，然后再发送数据，故延时大，节点的能量消耗也大。而FMR多跳路由协议，一次组网，数据即可传送基站，故端到端的延时更小，对其它节点的消耗能量也比较小。

图6 FMR与AODV节点剩余能量对比

(3) 吞吐量的比较

使用NS2中的AWK工具来分析提取二种不同协议接收数据包的比值,结果如表2所示。

表2 多次转发数据吞吐量的对比

从转发的数据包的数量可以看出FMR使用网络中的节点更频繁，使网络中的能量更均衡[14]，避免了网络中的节点能量主要消耗在一条路径上。

4 总结

从仿真实验结果看出，在节点传数据包到达基站的过程中，可以得出FMR在端到端的时延、节点的剩余能量、吞吐量等方面都优于AODV。另外相对AODV协议来说，FMR协议网络均衡性能更好，使网络中的能量分配更加均衡。总的来说，新提出的FMR多径路由协议提升了Ad Hoc网络的鲁棒性和容错性。

[1] 周莉,张燕,许璐蕾,等.Ad Hoc网络路由协议DSDV的仿真研究与实现[J].福建电脑，2012,28(11)：93-95.

[2] 李琼,张亮.基于NS2的AODV路由协议仿真及分析[J].计算机与现代化，2012,22(7):79-82.

[3] 张简丽,许洪光.基于DSR的路由协议综述[J].通信技术，2009,42(1):137-139.

[4] 吴敬敬,李忠民,李建坤.Ad-Hoc网络中3种典型路由协议的仿真分析与比较[J].南昌航空大学学报：自然科学版，2012,26(4):100-105.

[5] 张登银, 王军玲.改进的AODV路由协议性能比较研究[J].计算机技术与发展，2010,20(1):65-73.

[6] 冯景瑜, 卢光跃, 包志强. 认知无线电安全研究综述[J]. 西安邮电学院学报, 2012, 17(2): 47-52.

[7] Barma M K D, Chowdhuri R, Debbarma N, et al. Enhancing the Performance of AODV using Node Remaining Energy and Aggregate Interface Queue Length[C]//2013 International Symposium on Computational and Business Intelligence. New Delhi:IEEE,2013: 77-80.

[8] Amaresh M. Usha G. Efficient malicious detection for AODV in mobile ad-hoc network[C]//2013 International Conference on Recent Trends in Information Technology. Chennai: IEEE, 2013:263-269.

[9] 王鲁光,贾智平,李新.AODV和AOMDV路由协议性能分析与比较[J].计算机应用,2010,30(3):740-744.

[10] 丛玉华.多链路出口负载均衡技术的研究及实现[J].计算机与数字工程, 2012,40(9):76-78.

[11] Ng Kok-Poh, Tsimenidis C. Energy-Balanced Dynamic Source Routing Protocol for Wireless Sensor Network[C]//2013 IEEE Conference on Wireless Sensor(ICWISE). Kuching: IEEE, 2013: 36-41.

[12] 严秋实,万晓榆,樊自甫. 基于路径稳定性的MAODV改进路由协议[J].计算机工程, 2010,36(20):93-95.

[13] Ghane M, Rajabzadeh A. Remaining Energy Based Routing Protocol for Wireless Sensor Network[C]//2010 15th CSI International Symposium on Computer Architecture and Digital Systems.Tehran:IEEE, 2010: 67-73.

[14] 张继荣,张斌.基于能量均衡的Zigbee增强型树路由协议[J]. 西安邮电大学学报, 2013, 18(5):19-22.

[责任编辑:瑞金]

《西安邮电大学学报》版权声明

为适应我国信息化建设的需要，扩大刊物影响，拓宽信息交流渠道，本刊已加入“中国知网CNKI系列期刊数据库”、“中国核心期刊(遴选)数据库”(万方数据——数字化期刊群)、“中国期刊网”等数据库。本刊已许可以上数据库以数字化方式复制、汇编、发行、信息网络传播本刊所载文章的全文信息。稿件一经刊登，将在本刊稿酬中一次性支付著作权使用报酬(包括印刷版、光盘版和网络版等各种使用方式的报酬)。作者向本刊提交文章的行为即视为同意我刊上述声明。

西安邮电大学学报编辑部

A flat multipath routing protocol based on AODV

JI Xingmin1, LI Jinlong1, LU Guangyue1， FENG Jingyu1,2

(1.National Engineering Laboratory for Wireless Security,Xi’an University of Posts and Telecommunications,Xi’an 710121,China;2.School of Computer and Control Engineering, University of Chinese Academy of Sciences, Beijing 100049, China)

Change the AODV single-path routing to multi-path routing modifications can improve the fault tolerance and stability of the Ad Hoc network. During the flooding broadcast, when node

the first path request then data will be forwarded, if not the first time then no forwarding. This will avoid routing loops. When data forwarding, with multiple neighboring nodes on the hop, then forming a multiplex transmission. This can avoid path breaking with overload. Simulations are carried out by NS2. The results of the multi-path protocol compared with AODV protocol show that, the end-to-end delay is reduced by 30%～50% and the node residual energy is increased by 20%～40%. In addition the throughput comparison, the multi-path protocol makes the energy distribution network is more balanced, so that the stability of the network is improved.

routing protocol, loading balance, Ad Hoc network

2014-10-20

国家自然科学基金资助项目(61271276, 61301091)；陕西省国际科技合作重点基金资助项目(2013KW01-03)；中国博士后科学基金资助项目(2013M541013)；陕西省自然科学基础研究计划资助项目((2014JQ8321)；陕西省教育厅科学研究计划资助项目(14JK1681)

姬兴民(1971-)，男，博士，教授，从事无线网络安全、密码学研究。E-mail:jxmin@xiyou.edu.cn 李金龙(1988-)，男，硕士研究生，研究方向为宽带无线通信技术。E-mail:547430773@qq.com

10.13682/j.issn.2095-6533.2015.02.005

TP393

A

2095-6533(2015)02-0021-05