基于控制报文修改的改进AODV路由协议

计成超，糜正琨，陈桂林，赵生慧

（1.南京邮电大学 宽带无线通信与传感网技术教育部重点实验室，江苏 南京210003；2.滁州学院 计算机与信息工程学院，安徽 滁州 239012）

基于控制报文修改的改进AODV路由协议

计成超1，2，糜正琨1，陈桂林2，赵生慧2

（1.南京邮电大学 宽带无线通信与传感网技术教育部重点实验室，江苏 南京210003；2.滁州学院 计算机与信息工程学院，安徽 滁州 239012）

移动自组织网络具有无需基础设施，使用带宽受限的无线链路，并且拓扑结构频繁变化的特点。AODV（Ad－hoc On Demand Distance Vector Routing）是移动自组织网络中的一种典型路由算法。本文在其基础上提出一种改进方法，充分利用RREQ和RREP携带网络节点路由信息，存放到后续经过的中间节点的路由表中，从而抑制路由请求广播，提升协议性能。

MANET；路由协议；AODV；控制包

近年来随着无线技术的快速发展，无线网络正在日益得到广泛应用：如无线网络设备已经成为了笔记本电脑、手机等的标准配置。为使移动中的用户之间能够进行通信，可以使用2种接入方案：第一，借助于移动运营商的已有无线蜂窝网络设施转发数据。这种方案的主要问题是费用问题，由于现有无线蜂窝网络设置是由移动运营商建立，使用其设备需要交纳一定的费用。另外一个问题是切换问题，用户从一个基站移动到另外一个基站时在不影响时延和数据包丢失前提下需能够平稳切换；第二种接入方案是，将所有需要进行通信的无线网络组织成一个移动自组织网络（Mobile Ad hoc Network，MANET），参与其中的用户之间互相帮助转发来自其他节点发送的数据包。

相比较第一种方案来说，第二种方案具有一些优点：MANET网络不需要预先建立基础设施，可以快速部署到任何地方，如灾害发生地以及具有一定危险性的场所。另外，MANET可以在学术会议场地或校园、办公楼等地方临时组织成一个网络，借助于手机等无线网络设备组织在一起。MANET节点之间在能够传递数据包的前提下，为达到更好的传递效果，需要路由协议来帮助确定传递路径。

1 研究现状

科研工作者已经提出了一些适用于不同场景的MANET路由协议，但是到目前为止还没有一个标准的路由协议能够适合所有的MANET网络，已有的路由协议主要分为两类［1］：主动式路由协议（Proactive Protocol）和反应式（Reactive Protocol）。主动式路由协议中，每个节点预先建立一个全网的路由表，当节点需要发送数据包时，节点从其维护的路由表中查询待发送数据包的目的地址以及路由后，立即将数据包发送出去。而在反应式路由协议，只在有数据包需要传递时，启动一个全局、泛洪式的路由搜索过程，然后沿着搜索到的路由将数据发送出去。

1.1 主动式路由协议

主动式路由协议，又称为路由表驱动的路由协议（Table Driven Routing Protocols），节点中保存本节点到网络中其他节点的路由信息。为了使网络的拓扑结构发生变化时能够及时更新到路由表中，节点需要周期性查询网络路由信息和拓扑状态。

目的序列距离向量（Destination Sequenced Distance Vector，DSDV）［2］协议是一个典型的主动式路由协议，基于Bellman Ford算法来维护到每个节点的最短距离。路由表周期性的或者如果拓扑结构发生了改变，则更新一次。主动式路由协议的优点是由于预先建立了全网的路由，因此，在有数据包需要发送时，能够立即将数据包发送出去，无需查询当前节点到达目的节点的路由，减少了网络时延。其缺点是，需要周期性收集到达每个移动节点的路由信息，降低了网络的利用率。

1.2 反应式路由协议

反应式路由协议，又称为按需路由协议（On Demand Routing Protocol）。采用这种协议，节点不需要维护到达其他节点的实时路由信息，只在节点需要一条到目的节点的路由时，才启动路由发现过程查找到达目的节点的路由。一旦一条路由建立起来，它通过维护进程维护路由信息，直到不再需要该路由。

反应式路由协议也可分为两类［1］：源路由（source routing）和逐跳路由（hop－by－hop routing）。在源路由中每个数据包携带从源节点到目的节点之间的完整路由信息，每个中间节点按照每个数据包头中包含的信息转发数据即可。典型的源路由协议有动态源路由协议（Dynamic Source Routing，DSR）［3］。

在逐跳路由协议中每个数据包只携带数据包的目的地址和下一跳地址。在通向目的地址路径上的每个中间节点在接收到数据包后，首先查找自身路由表，根据查找到的路由信息向目的节点转发数据包。典型的逐跳路由协议有按需距离向量协议（Ad hoc on－Demand Distant Vector，AODV）［4］。

AODV是在DSR和DSDV的基础上发展来的，它借助了DSR的按需路由发现机制：通过发送路由请求数据包（RREQ）泛洪整个网络的方式发现到达目的节点的路由。每个节点接收到这个RREQ数据包后，如果本节点是该RREQ数据包请求的目标节点或具有到达RREQ所请求的目标节点的路由，则返回一个路由回复包（RREP）给RREQ的源节点，否则本节点就继续广播接收到的RREQ。但是，AODV同时采用一个与DSR不同的维护路由信息的方法，它借助于DSDV协议的逐跳路由机制，引用序列号机制防止过时路由和避免形成路由环。

图1 AODV路由发现过程示意图

如图1所示，当节点A有数据包需要传递给节点E，首先查询自己的路由表，若没有到达E的路由，则发起一个RREQ泛洪，向全网搜索通向E节点的路由。RREQ查询包到达B和C节点，若B和C也没有到达E的路由，则继续转发接收到的RREQ，经过一段时间以后，RREQ查询包到达节点E。在RREQ经过的每个中间节点上，都会建立到达RREQ的起始节点A的路由。此时每个中间节点的路由表内容如图2所示。节点E接收到该RREQ后，向节点A发送一个RREP回复包，沿着中间节点建立的通向A的路由转发该回复包，最终到达节点A。此时每个中间节点的路由表内容如图3所示。

图2 RREQ查询后的各节点路由表

图3 RREP到达源节点后的各节点路由表

2 改进的AODV路由协议

在AODV中，源节点向目标节点发送数据前，首先需要查找一条到达目的节点的路由信息。如果接收到的RREQ的中间节点具有一条到达目的节点的路由，则直接将该路由信息回复给源节点，不需要将RREQ传递到目的节点，否则将继续转发RREQ包，查询过程在源节点收到RREP数据包时结束。如图3所示，一次路由查询结束后，源节点A获得了到达目的节点E的路由，E获得了到达A的路由，中间节点B、C、D分别获得到达A和E的路由。这种方式存在的问题是：如果后续再有数据需要从A节点发送给C或D节点，尽管在前一次的路由查询中，C或D节点已经参与传递A发送的数据包，但是由于A没有到达该节点的路由，因此A仍然需要再次发起一次路由查询过程，增加了路由控制开销。

由于源节点采用泛洪的方式发送RREQ查询数据包，是主要的路由控制开销。因此，保存曾经参与传递数据的节点的路由信息，可以减少RREQ发送机会，提高路由性能。

经过分析发现，通过允许接收和转发RREQ或RREP数据包的节点记录本节点信息到数据包中，其他接收到该数据包的节点从数据包中提取携带的节点信息的方法，减少后续再次发起的路由发现过程，从而降低路由控制开销。

在原AODV协议基础上，具体改进如下：

1.源节点产生RREQ查询数据包（目的节点或包括有到达目的节点路由的中间节点产生RREP回复数据包）；

2.中间节点接收到RREQ或RREP；

3.检查该数据包依次经过的中间节点，并将这些节点加入或更新到本节点的路由表中；

4.若需要转发接收到的RREQ或RREP，则在转发前将本节点信息加入到数据包中，再将数据包转发出去。

为避免路由陈旧带来的路由失效问题，数据包中对应经过的每个中间节点的路由仍然包括一个序列号，该序列号等于数据包携带的源或目的路由序列号。

图4 改进的RREQ查询后的各节点路由表

如图4所示，改进后，RREQ数据包到达节点E时，其中包括有A、B、C、D四个节点的信息，此时节点E将这四个节点全部加入（更新）到其路由表中。数据包所经过的其他节点也将所携带的路由信息更新到自己的路由表中，并在转发RREQ之前将本节点信息加入到RREQ数据包中。

图5 改进的RREP到达源节点后的各节点路由表

改进后，RREP从节点E传递到节点A过程中，和RREQ传递相似，每个接收到数据包的节点均从其中提取携带的路由信息，更新到自己的路由表中，同时将自己的节点信息增加的RREP包中。

路由发现过程结束后，在RREQ和RREP经过的所有节点中均已包括到达其他节点的路由信息。每个节点收集了更全面的路由信息以后，可以抑制后续潜在的路由发现过程，减少路由控制信息的开销。

3 仿真分析

为了评估修改后的路由协议的性能，在NS2中对原AODV和改进后的协议（MyAODV）进行仿真，并在不同情况下对比了两者的性能［5，6］。

3.1 仿真参数的设定

仿真参数如表1所示：

表1 仿真参数

3.2 实验分析

本节仿真实验在不同节点运动速度和不同节点数情况下，对比分析原AODV路由协议和本文提出改进后的MyAODV路由协议的时延和路由负载情况。

3.2.1 时延

数据包的端到端时延，数据包从源节点到目的节点的时间差。时延包括路由发现，数据队列和重传时间。

在改进后的路由协议，发送一次路由查询过程，RREQ和RREP可以更广泛地传播节点的拓扑信息。当再次需要查询相关节点的路由信息时，不再需要新的路由查询过程，节省了数据传输的总时延。

图6，7分别展现原AODV协议和改进算法后的路由协议在不同节点个数和运动速度情况下的网络时延情况。从图中可以看出，在绝大多数情况下，改进后的协议都比原路由协议具有较低的网络时延。

图6 不同节点个数情况下的时延

图7 不同节点运动速度情况下的时延

3.2.2 路由负载

首先对路由负载进行归一化，即，目标节点接收到一个数据包，平均需要的路由包的数量。

由于减少了路由查询过程，减少了RREQ和RREP数据包在网络中传输的总量，降低了网络的路由负载。如图8和图9所示，相对原AODV来说，改进后的协议减少了路由负载。

图8 不同节点个数情况下的归一化路由负载

图9 不同节点运动速度情况下的归一化路由负载

4 结束语

本文基于AODV路由协议控制包，提出一个改进的路由信息传递方法，即：利用RREQ路由查询数据包和RREP路由回复数据包携带所经过的中间节点信息，在接收到RREQ和RREP的节点中提取所携带的节点信息，并将节点信息转化为路由信息。

改进的路由协议比原AODV更有效的传播路由信息，避免不必要的路由发现过程，降低了数据传递的总时延，减轻了MANET中路由负载。

［1］Latiff，L.A.and N.Fisal.Routing protocols in wireless mobile ad hoc network － a review［C］.in Communications，2003.APCC 2003.The 9th Asia－Pacific Conference on，2003.

［2］Perkins，C.E.and P.Bhagwat，Highly dynamic destinationsequenced distance－vector routing（DSDV）for mobile computers［C］.ACMSIGCOMMComputer Communication Review，1994，24（4）：234－244.

［3］Johnson，D.B.，D.A.Maltz，and J.Broch，DSR：the dynamic source routing protocol for multihop wireless ad hoc networks［J］，in Ad hoc networking.2001，Addison－ Wesley Longman Publishing Co.，Inc.139－172.

［4］Perkins，C.E.，E.Royer，and S.Das，Ad hoc on demand distance vector（aodv）routing［S］.IETF RFC，3561，2003.

［5］Rani，P.，N.Sharma，and P.K.Singh.Performance Comparison of VANET Routing Protocols.in Wireless Communications ［C］， Networking and Mobile Computing（WiCOM），2011 7th International Conference on，2011.

［6］许富龙，刘明，李建平.延迟评估的车载自组织网络数据传输协议［J］.计算机工程与应用，2011，47（3）：23－26.

An improved AODV routing protocol based on modified control messages.

JI Chengchao，MI Zhengkun，CHEN Guilin，ZHAO Shenghui

Mobile Ad hoc Network （MANET）is characterized by absence of infrastructure，limited bandwidth of wireless links and frequent topological changes.AODV（Ad hoc On Demand Distance Vector Routing）is a conventional routing protocol for it.An improved method is proposed to use RREQ／RREQ carrying routing information of the nodes on the path，which will then be stored in the routing tables of subsequent intermediate nodes travelled by RREQ／RREP.The number of routing request broadcasting is reduced and the protocol performance is enhanced.

MANET；routing protocol；AODV；control message

TP393

A

1673-1794（2012）02-0032-04

计成超（1980－），男，安徽全椒人，博士生，讲师，主要研究领域为车载自组织网络，延迟容忍网络；通讯作者：糜正琨（1946－），男，教授，博导，主要研究领域为下一代网络技术。

安徽省高等学校优秀青年人才基金资助项目（2012SQRL152，2012SQRL153）；滁州学院基金资助项目（2010kj020B，2011kj019B）

2012-02-12