基于改进的AODV多路径路由算法建模分析

王洁　李明明　刘建生　熊小峰　乐光学

摘要：为进一步有效地利用网络资源，减小网络开销，在AODV路由协议的基础上扩展多路径路由协议，根据路由信息请求、回复、保存过程中存在的网络能量损失为目标函数，得到基于多路径选择的路由算法来建立数学模型。通过仿真实验，对比分析已有经典的改进路由算法，具有更低网络能量损失、平均端到端时延和较高网络数据转发率。

关键词：AODV；数学建模；数据转发率；端到端时延

中图分类号：TP393 文献标识码：A 文章编号：1009-3044（2015）07-0052-05

1引言

无线Mesh网络（Wireless Mesh Network， WMN），也称作多跳网络，网络中所有节点自动组建立子网并维护网络的连通性。对比Ad Hoc网络，无线Mesh网络更具优势，如表1所示[1]。但是无线Mesh网络对路由性能的要求也随之而升高，如何提高路由协议的有效性，将成为无线Mesh网络路由协议的主要研究重点之一。

由于无线Mesh网络传播条件的突变，网络拓扑上不可预测的突发状况容易导致通信链路断裂[2]。而一旦链路发生断裂，需要重启路由或者寻找新的通信链路完成通信，以降低路由开销[3]。针对无线Mesh网络的路由不稳定性，宋文等人提出了公平感知路由算法，有效解决了目的节点的拥塞和延时问题，以网络节点传输的拥塞控制状态作为路由协议的评价指标，该路由算法基于DSR协议[4]。而已有的DSR路由协议仅考虑“最短路径”忽视了路径上的业务通信量。根据按需路由机制对比分析DSR、AODV，其中AODV为主动式距离矢量路由协议（Ad Hoc on-demand distance vector，AODV），在中继节点缓存路由请求和响应记录，能够有效降低协议的开销。如何在无线Mesh网络中利用AOVD路由协议思想，降低协议开销，成为无线Mesh网络路由协议的研究重点。

传统的按需距离矢量（Ad Hoc on-demand distance vector，AODV）路由算法主要适用于单路径路由协议设计中[5]，为了进一步优化路由协议，保证网络稳定性，国内外学者对AODV协议进行改进和扩展，成果显著。王忠恒等人提出了AODV-BR协议，该协议增强了AODV路由维护的功能，算法优势在于有效降低网络链路中断率和丢包率[1]。洪利等人提出了基于链路可用性预测的AODV路由协议，该协议提高了分组的投递率并降低了分组端到端平均传输延时，提升了路由协议的可靠性[2]。清华大学网络实验室于2008年提出了以信任模型可用性为前提的AODV路由协议，针对MANET安全机制，改进传统的AODV协议，提出ATAODV（Availability trust AODV）路由协议，该协议有效降低了丢包率[3]。杜青松等人针对在MANET网络环境下的性能缺陷问题设计了优化的AODV路由协议O-AODV协议，增加了路由冗余度，提高了路由发现的效率，加快路由的本地修复能力[5]。王龙峰针对平均队列长度来预测拥塞情况，提出了RAODV路由协议[9]，该协议在收敛条件下有效降低了端到端平均时延和提高数据转发率。如何基于改进的AODV路由协议有效降低无线Mesh网络的丢包率，提升数据转发率，以满足多路径的无线Mesh网络节点的通信要求，成为本文研究重点。

无线Mesh网络中节点的多路径路由问题如图1所示，假设在某一时刻路径1-5-4正在传输数据包，节点5的负载已经很大，而此时节点2还要与节点6通信，依据跳数最小建立的路径为2-5-6 ，这将导致网络局部拥塞。路径2-4-6，路径2-5-6都是依据最小条数的路径，若4和5两个节点的带宽一样，此时依据路径的负载程度可以明显得出选择路径2-4-6比路径2-5-6好。

多路径路由协议，分为多路径路由协议、备份路由协议两种。其中备份路由协议为在多条路径中选取一条路径作为主路径，其他路径作为备份路径。当主路径不可用时，则备用路径代替主路径来传输数据包。多路径路由协议避免了重启开启路由发现的开销和路由本地修复时间，提升了网络稳定性。基于该路由协议，卢锡城等人提出了在移动自主网络中基于簇的QoS多路径路由协议（CQMRP， Cluster-based QoS multipath routing protocol），该协议以局部路由信息的服务节点为指标，展开服务质量约束评价，算法有效降低了路由开销，提升了网络的多路径服务质量[7]。RAODV协议采用了在多路径环境下增加路由跳数来降低平均时延[9]。文献[11]提出了有效避免路由断裂的ARB-AODV路由算法，该算法对比传统AODV路由有效提升了数据转发率并降低了网络端到端时延。文献[13]提出了基于链路可用时间的LAT-AODV路由算法，该路由算法在路由请求方面增加了备用路由的选择函数，有效提升了数据转发率和缩短了平均时延。

本文将基于改进的AODV路由协议设计路由协议，增加路由查找过程，通过分析服务节点的网络能量损失情况，选择最优路径，增加多路径查找功能，防止路由重启产生的网络开销，以提升网络吞吐量。仿真实验增加网络带宽的冗余度验证算法有效性。

2 AODV路由算法性能分析

2.1 算法性能分析

针对无线Mesh网络中的路由发现过程，首先展开路由信息的分类，包括三种路由信息查询，路由请求（RREQ）消息去发现从源节点到目的节点的路径，目的节点收到RREQ（最新的），则向源节点发送路由响应（RREP），源节点收到RREP消息后，启动RREQ缓存定时器，在这段时间内收到的所有不同的RREP进行缓存，并对其进行排序，确定主路径，然后通知应用层开始发送数据。当主路径拥塞，导致主路径长时间未响应，则切换优先级高的有效路径。

2.2 节点随机模型

3 仿真分析

基于文献[9-13]的路由算法分析结果，本文选择ARB-AODV、LAT-AODV、ARB-AODV、AODV四种路由算法作为对比算法。通过对比实验，分别从网络能量损失情况、移动数据转发率、网络端到端平均时延来验证本文路由算法的有效性。实验采用1000mx1000m网络拓扑，随机选择40个节点，以最大跳数为20跳，在最大速度为10m/s～50m/s范围内转发路由信息。

3.1 基于ADOV的多路径协议路径能量损失仿真分析

以网络能量损失为路由协议算法的度量值，对比分析ARB-AODV、LAT-AODV、ARB-AODV协议，仿真结果如图2所示。

实验结果表明：

（1）随着网络节点速度的增加，网络能量归一化值逐渐提升，网络能量损失逐渐增加。

（2）当节点移动速度低于30m/s时，网络能量损失：LAT-AODV>AODV>ARB-AODV>本文算法；当节点移动速度高于30m/s时，网络能量损失：AODV>LAT-AODV>ARB-AODV>=本文算法。

（3）单路径的路由算法AODV、LAT-AODV、ARB-AODV网络能量归一化值高于多路径算法，本文路由算法得到的网络能量损失低于其他算法。

3.2 基于ADOV的多路径协议路径数据转发率分析

实验结果表明：

（1）随着网络节点速度的提升，网络数据转发率持续下降。传统路由算法AODV在节点速度为30m/s～40m/s时，数据转发率没有变化，其他算法数据转发率均稳定下降。

（2）在节点移动速度低于40m/s时，网络数据转发率下降速度：本文算法3.3 基于ADOV的多路径算法平均时延分析

实验结果表明：

（1）随着网络节点速度的提升，网络平均端到端时延逐渐升高。传统路由算法AODV的平均端到端时延高于其它路由算法。

（2）端到端时延稳定性：本文算法（OURS）>ARB-AODV>LAT-AODV>AODV。

4 结论

本文基于路由选择改进AODV路由协议，提出了改进的AODV算法的数学模型，以网络能量损失为目标函数，根据不同冗余度计算公式得到的路由选择结果，即路由请求并得到回复的数据信息。仿真实验结果表明，本文算法较ARB-AODV、LAT-AODV、AODV协议，具有较低网络能量损失、较高数据转发率、较低网络平均端到端时延。本文存在的不足，对于节点路由信息在转发过程中存在的冗余度还未进行详细实验。

参考文献：

[1] 王忠恒，张曦煌.移动Ad Hoc网络AODV路由协议的改进[J].计算机应用，2010，30（2）： 333-336.

[2] 洪利，黄庭培，邹卫霞，等.基于链路可用性预测的AODV路由协议研究[J].通信学报，2008，29（7）：118-123.

[3] 游之洋，龚伟，赵曦滨，等.基于可用性信任模型的AODV路由协议改进[J].清华大学学报，2010，50（5）：735-738.

[4] 宋文，方旭明.无线Mesh网络公平感知路由算法设计与仿真[J].系统仿真学报，2007，19（18）：4320-4325.

[5] 杜青松，朱江，张尔扬.基于闲时逆寻和路由学习机制的优化AODV路由协议[J].通信学报，2011，32（8）：64-71.

[6] 邝祝芳，陈志刚，刘蕙.一种认知无线Mesh网络中负载均衡的组播路由算法[J].计算机学报，2013，36（3）：523-531.

[7] 卢锡城，安辉耀，彭宇行，等.大规模移动自主网络中基于簇的QoS多路径路由[J].软件学报，2007，18（7）：1786-1798.

[8] 李国强，勒浩，武穆清.Ad Hoc网络中一种新的多径路由机制研究[J].信息传输与接入技术，2008，34（1）：22-24.

[9] 王龙峰.RAODV：一种基于拥塞跳数改进的AODV路由协议[J].计算机与现代化，2013，216（8）：133-136.

[10] 张菡.Ad Hoc网络中一种改进的AODV路由协议[J].无线互联科技，2008：254-258.

[11] 李向丽，荆瑞霞，何一涵.避免路由断裂的优化AODV路由协议[J].计算机应用，2014， 34（9）：2468-2471.

[12] 庄雷，孙智军.一种增加时限和延迟的AODV协议改进方法[J].微电子学与计算机， 2007，24（8）：180-182.

[13] 周胶，田杰，戴晨铖，等.战术MANET中基于链路可用时间的AODV路由协议研究[J]. 2013，35（12）：96-101.

[14] GONG XuDong，XIONG Yan，LU Qiwei et al.A Trusted Ad Hoc Routing Protocol Based on Fuzzy Mathematics[J].Chinese Journal of Electronics，2013，22（1）：155-159.