移动ad hoc网络中对AODV路由协议的改进研究

摘要：在Ad hoc网络中，AODV协议是一种重要协议，但是由于AODV协议为单一路径协议，因而其传输效率不高。在AODV协议的基础上，提出一种以时延为参数的多径路由协议AODV-T，AODV-T协议能够同时以最短路径和次短路径进行传输信息。仿真测试表明，该路由协议在分组传输率、平均端到端时延、网络开销方面较AODV协议而言，均有所改善。

关键词：ad hoc网络；AODV协议；多径路由

中图分类号：TP393文献标识码：A文章编号：1672-7800（2012）012-0134-03

1移动ad hoc网络相关知识

移动ad hoc网络是一种特殊无线移动通信的网络。它与一般无线移动通信网络的不同之处在于，移动ad hoc网络不需要依赖任何基础设施，整个网络是由节点组成。在移动ad hoc网络中，所有节点地位都是平等的，每一个节点即能够接受消息，也能够转发消息。即每个节点都同时具有移动终端和路由转发的功能。

移动ad hoc网络最早起源于美国DARPA（Defense Advanced Research Project Agency）的分组无线网（PRNET，Packet Radio NETwork）项目，研究分组无线网在战场环境下数据通信中的应用。因此，移动ad hoc网络最早也只限于军事领域中的应用。随着技术的发展与成熟，移动ad hoc网络现在应用得越来越广泛，ad hoc网络现广泛应用于军事、灾后重建、个人生活以及将其作为一个无线多跳接入网与其它网络进行连接的应用。

移动网络由于其自身的特殊性，具有以下特点：①无中心性，移动ad hoc网络由于其所有节点地位相等，所以其为一个对等性网络；②自组性，移动ad hoc网络中，只要节点的距离在一定范围内，就能够自发地通过某种算法组成网络；③链路带宽及能量有限性，移动ad hoc网络采用的是无线传输，所以其信道带宽有限，且移动ad hoc中的每个节点都具有转发信息的能力，所以一般节点都要以电池作为其动力，其节点能量也非常有限；④动态拓扑性，由于移动ad hoc网络中的节点经常发生变动，所以其网络拓扑结构也会经常发生变化。

2移动ad hoc网络中的AODV协议

在移动ad hoc网络中，一个好的路由协议至关重要。ad hoc网络中，一般有2种划分路由协议的方法。一种是分为按需路由和按时间路由，按需路由只在需要路由信息时，才发起路由请求过程，从而达到在路由开销相对较小的情况下提供路由；而按时间路由中，每个节点都采用周期性发送信息包以达到更新路由表的目的，从而以相对较大的开销来寻找最优路径（主要指距离最短，即所经过跳数最少的路径）。另外一种划分方法是按通信模型，分为单径路由和多径路由。单径路由在路由发现中只有一条信息通道；而多径路由中，信息通道最少有两条或者两条以上。协议无线自组网是按需平面距离矢量路由协议（Ad hoc On-demand Distance Vector Routing，AODV），是一种典型的按需单径路由协议。

Aodv协议的传输过程为：在ad hoc网络中，每个节点都会维护一张自己的路由表，当源节点（S节点）需要向目的节点（D节点）发送数据信息时，首先检查自己的路由表，查看是否有到达目的节点的路由信息。如果有，则直接按照路由表上的路径发送；如果没有，则向周围节点广播一个RREQ用来请求路由信息。当中间节点收到RREQ后，首先同样会检查自己的路由表是否有到达目的节点的路由信息。如果有，则按此路径进行发送；如果没有，中间节点将在此RREQ消息中加入自己的信息后，继续向其周围节点转发此RREQ请求包，直到找到有到达目的节点路径的中间节点或者目的节点D节点本身为止。在有到达目的节点路径的中间节点或者目的节点本身收到该RREQ后（此RREQ含有源节点到目的节点的反向地址信息），会回复一个与之对应的应答信息包RREP。这样，RREP沿着对应的RREQ的反向路径信息到达源节点，从而更新源节点到目的节点的正向路径。

需要指出的是，为了避免路由环路和网络负载过重，中间节点和目的节点在收到相同的RREQ信息包时，会立即将其丢弃。这样在一定程度上避免了路由环路，减轻了网络负担。但是也正是由于此种机制，使得网络传输效率不高。特别是在节点不停移动，链路容易发生断裂的移动ad hoc网络中。因此，提出一种对AODV协议进行改进的路由协议AODV-T（Ad hoc On-Demand Distance Vector Routing-Time，AODV-T），旨在进一步提高ad hoc网络中的传输效率。

3AODV-T的算法数据结构

3.1RREQ消息的数据结构

在RREQ消息中新增加了RREQ第一跳、路由记录、RREQ时延。其具体格式如表1所示。其中，RREQ第一跳是记录RREQ消息从源节点到目的节点路径的第一跳，只要RREQ第一跳不相同，就是链路不相交路径。路由记录则为记录经过的多条路径。RREQ时延则是记录发出一个RREQ消息后，到接收到对应的RREP消息的时间。

3.2RREP消息的数据结构

同样，在RREP消息中也增添了相对应的最大时延、路由记录、RREP时延选项。其中，最大时延是设定一个时延最大值，当等待RREQ的时间超过此最大值时，默认丢弃掉后来的RREQ消息。路由记录与RREQ相同，从对应的RREQ消息包中拷贝过来。RREP时延则是记录RREQ到达目的节点的时间，其结构如表2所示。

4对AODV协议的改进

AODV协议虽然能满足一定要求的ad hoc网络需求，但其并不是质量很高的一种路由协议。首先，AODV是单径路由，在带宽有限的移动ad hoc网络中，单径路由往往不能满足业务传输要求；其次，AODV协议的各种路由指标参数并不高。因此，对AODV可以进行适当改进，AODV-T相对于AODV协议，主要在两方面进行了改善。

一是在路由路径数目方面，不再只是寻找一条路径进行路由，而是同时以最短路径和次短路径同时进行路由。这里多条路径记录方法参考AOMDV协议。不同的是在AOMDV多径路由协议中，是在一次路由发现中，找到多条路径（一般不会超过3条）。在这多条传输路径下以一条最短路径为主路径，以其它路径为备份路径进行传输。这样在实际传输中，往往只有一条路径在进行信息传输。而AODV-T协议则是根据时延，同时选择最短路径和次短路径进行传输。时延最小的为最短路径，时延次之的为次短路径。时延是指从源节点发起路由寻找的RREQ时刻开始，到接收对应目的节点回复的RREP数据包为止所经历的时间。时延在一定程度上反应了当前网络状况的好坏，特别是在网络负载量较大的情况下，跳数最短的路径往往不是最优路径，而用时最少的路径才是最优路径，即时延最少的路径。

二是AODV-T协议同时提供QOS保障，必须在源节点与目的节点之间寻找必要资源以满足QOS要求的路由。为了找到合适的QOS路径，选择以该路径的时延作为基本判断参数，来确定该路径是否满足QOS要求。根据MSR均衡负载的方法，对源节点搜索的3条（如果存在）路径按照权值进行业务分配。使用路由过程中RREQ-I的时延，即从源节点发送一个RREQ-I的数据包到接收到该数据包对应的RREP-I回复数据包的时间。这个时间反映出了该条链路的状态，即越稳定越近的链路，其RREQ-I时延就越小。所以，该条链路的可用带宽与RREQ时延成反比关系，可以通过Wi=min{dmax/di，A}表示。其中，Wi为路径权值，dmax为到源节点的多条路径的RREQ-I的最大时延，di为路径i的RREQ-I时延，A是设定的一个边界值，是为了防止一条路径负载过重。从公式中可以看出，对于时延越小的路径，其权值越大，即路径的稳定性就越高，可用带宽就越大，其分配的负载业务相对其它条路径就越大。

5仿真结果分析

选择网络仿真工具为NS2，操作系统是在Linux环境下进行的。其它仿真的各项参数为：网络节点数量选取为50个，网络拓扑范围设置为长500m、宽500m的正方形区域，网络中的最大连接数为30个，仿真持续时间设为100s。在相同的仿真环境下，改变节点的移动速度，分别对AODV协议和改进的AODV-T协议的分组投递率、平均端到端时延、网络开销进行分析比较。

图1分组投递率随节点最大移动速度的变化

从图1可以看出，在节点移动速度较低的情况下，两种路由协议能较好地将信息传递给目的节点，而随着节点移动速度的增大，分组投递率出现下降。而AODV-T的分组投递率比AODV要高，这是因为AODV-T采用双信道传输，当一条路径传输因节点移动速度过快而断裂时，仍然有一条备份路径进行传输信息。

图2时延随节点最大移动速度的变化

从图2可以看出，随着节点移动速度的增大，端到端时延明显增大。而AODV-T协议时延大概比AODV协议低3%左右。这是由于AODV-T选择以时延作为路径选择参数，优先考虑时延较小的路径作为信息传输路径，从而降低端到端时延。

从图3可以看出，随着节点移动速度的增加，路由开销不断增大。这是由于节点移动速度增加，使链路断裂几率增大，从而增加路由寻找次数，增大路由开销。由于AODV-T采用的是最短路径和次短路径两条路径进行传输，只有两条路径同时失效时，才发起路由寻找请求，从而降低路由请求次数，降低路由开销。

图3路由开销随节点最大移动速度的变化

6结语

本文针对AODV的不足，提出了一种以时延为参数的改进多径路由协议AODV-T。此路由协议根据网络当前状况同时以最短路径和次短路径传输信息。经过仿真测试表明，该路由协议在分组传输率、平均端到端时延、网络开销方面较AODV协议而言，均有所改善。

参考文献：

[1]郑相全.无线自组网技术实用教程[M].北京：清华大学出版社，2004.

[2]C. K TOH.Ad hoc mobile wireless networks：protocols and system[M].New Jersey：Prentice-Hall PTR，2006.

[3]IEEE Computer Society LAN/MAN Standards Committee.IEEE standard for wireless LAN medium access control（MAC） and physical layer（PHY） specifications[S].1997.

[4]D work address translator （NAT）-friendly application design guidelines[S].Internet Engineering TaskForce （IETF），2002.

[5]石晶林.移动自组织通信网络技术概况及未来前景[J].信息技术快报，2004（7）.

[6]舒炎泰，高德云，王雷.无线ad hoc网络中的多径源路由[J].电子学报，2002（2）.

[7]李洪刚，周洲.Ad Hoc网络中的路由机制[J].信息技术，2002（7）.

Research on the Improving of AODV Routing Protocol in

Mobile ad Hoc Networks

Abstract：Ad hoc networks，AODV protocol is an important agreement.AODV is due to a single path protocol transmission efficiency is not very high.In this article in AODV are based on，proposed a multi-path routing protocol the AODV-T，AODV-T protocol can transmit information at the same time to the shortest path and the second shortest path delay parameters.After the simulation tests show that the routing protocol AODV protocol with respect to the packet transmission rate，the average end-to-end delay and network overhead，are improved.

Key Words： Ad hoc Network； the AODV； Multi-path Routing