基于代价函数的改进AODV协议

邱梦华　罗喜伶

摘 要： Ad Hoc网络中如何设计良好的路由协议使其网络均衡是当今研究的重点。针对网络负载和能量均衡等问题，提出了一种基于代价函数的改进按需距离矢量路由协议CF?AODV。该协议在路由建立过程中，通过能量阈值和缓存队列长度阈值进行RREQ转发判断；在目的节点选取路由时采用延迟应答方案，通过以路径长短、路径负载、路径剩余能量作为因子的代价函数进行判决来选取最佳路径。仿真结果表明，所提协议在网络负载和能量上得到了均衡，可以延长网络寿命，减轻网络拥塞，减少时延和丢包率。

关键词： Ad Hoc； AODV路由协议； 代价函数； 负载； 剩余能量

中图分类号： TN915.04 ?34； TP393 文献标识码： A 文章编号： 1004?373X（2015）05?0009?05

Improved AODV protocol based on cost function

QIU Meng?hua， LUO Xi?ling

（Beihang University， Beijing 100191， China）

Abstract： In Ad Hoc Network， how to design a good routing protocol to make network balancing is the focus of todays research. For network balancing issues of load and energy， an improved demand distance vector routing protocol CF?AODV based on cost function is proposed. The protocol is used to do RREQ forwarding judgment by energy threshold and buffer queue length threshold in the establishing routing process. The delayed response program is used when the destination node selects route. By taking length， load and residual energy of path as cost functions of factor， adjustment for optimal routing selection is made. Si?mulation results show that the proposed protocol can make the network balance on load and energy， extend the network lifetime， reduce network congestion， latency and packet loss rate.

Keywords： Ad Hoc； AODV routing protocol； cost function； load； residual energy

0 引 言

为了解决动态自组网和无法依靠基础设施等问题，提出了Ad Hoc解决方案。移动Ad Hoc网络是一种复杂的分布式网络系统，是自组织、自愈网络；无线移动节点可以动态的自组织成任意临时性的网络拓扑，从而允许人们和装置在没有预先存在的通信基础设施的环境中进行无缝的互联互通[1]。根据Ad Hoc双重功能节点、无中心自组织、能量和带宽有限等特点，设计良好的路由协议满足其动态变化的拓扑结构是当今研究的重点和难点。

Ad Hoc路由协议根据网络节点获取路由信息方法可分为表驱动路由协议（主动式路由协议）、按需驱动路由协议和混合路由协议三种。AODV[2]是经典按需距离矢量路由协议，包括路由建立和路由维护两个过程。优点在于能快速自适应动态链路状况，处理开销和存储开销低等，但是由于需要临时建立路径，会增大时延，路由请求较多时易造成广播风暴。目前AODV协议研究和改进主要在负载均衡、能量均衡、链路修复以及安全保障等方面，但是各种算法并不能同时在多方面显著改善协议性能。如何合理有效地选取中间方案，实现AODV协议各方面的均衡优化是当前研究的一个重点。

本文综合考虑了网络负载均衡和节点剩余能量，提出了基于代价函数的CF?AODV协议。对代价函数进行分析，阐述了CF?AODV协议的基本算法；构建仿真场景，进行了结果分析。

1 相关研究

1.1 负载

按需驱动路由协议在不频繁进行路由发现时，网络中控制分组较少，整个网络的负担较轻；但是如果网络中拓扑变化较快，路由信息跟着不断的变化，网络的负担就会加重。如果网络中选取路由时没有考虑到节点的负载情况，网络流量不均衡，会导致重负载节点出现，增加时延和丢包率。为了解决以上问题，关于负载均衡的路由协议应运而生。常见的判断节点负载的方法有：基于本地信息的、基于流的、基于时延的、基于传输速率的负载感知路由协议。在Ad Hoc网络中，节点负载反映该节点的繁忙程度，较重时可能导致包阻塞，使得端到端延时长，丢包率增大，通信链路的传输保障降低。

LWR[3]是基于本地信息的负载感知路由协议。该算法根据节点的负载情况判断对请求报文应采取的操作，其中节点的负载情况由信道使用率、队列长度、活动邻居节点数和退避定时器的值决定。MAC层接口等待队列缓存的数据包是经过过滤后由于竞争机制而未发出的数据包，可以准确实时地体现节点当前的拥塞程度。此方法能较准确地得出节点某时刻的流量，但是选取的参数太多，可能在接收RRRQ到发送RREQ期间内并不能全部得到，从而造成丢包。LBAR[4]是基于流的负载感知路由协议。该协议将经过节点和邻居节点的路由数作为负载，在路由寻找过程中统计总负载，选取最小的总负载路由。此做法可以预测节点的流量，但是并不能体现出节点当时拥塞程度。

1.2 节点剩余能量

Ad Hoc网络节点的能量通常是有限的，如果网络中的某些节点能量快速耗尽，有可能使得源节点不能以较短的路径到达目的节点，增大了数据传输时间以及丢包率等。MTPR[5]以路径节点传输总能量的消耗最小为主，但没有考虑节点剩余能量，容易造成网络分割。MMBCR[6]克服MTPR的缺点，却忽略了跳数、延迟等因素，不能保证链路总体能量的消耗是最小的。MRL[7]路由算法提出在节点剩余能量基础上，考虑节点能量消耗速率，选择生存时间较长的路由，但是也未能考虑到节点负载和延迟等因素。

1.3 代价函数分析

基于以上分析，本文在路由建立过程中，关于负载和能量的工作主要包括如下：

（1） 节点的负载主要依据经过该节点、其邻居节点的活动总路由数和活动的邻居节点数来决定。

（2） 设定负载阈值L0和能量阈值E0。节点收到RREQ时读取MAC层接口缓存队列长度L和节点剩余能量E。若L超过L0，将其视为重负载节点，丢弃收到的请求报文，不考虑其为中间节点； 若E小于E0，则丢弃收到的请求报文。

（3） 在RREQ消息和路由表中加入路径负载总和和负载最大值这两项；每次转发控制消息时，将该节点的负载值与接收的控制消息的负载值相加，更新负载最大值，进行转发控制消息。

在路由选取时，本文采用目的节点延迟应答方案，从所有路径中根据代价函数选出最佳路径。代价函数的因子包括路径长短、路径负载、路径剩余能量，如下：

[C=w1i=1N-1di-i+1+w2i=2N-1LOADi+w31i=2N-1Pi] （1）

式中：N为所选路径的节点总数；[di-i+1]为两节点之间的距离；[LOADi]为节点i的负载；[Pi]为节点i的剩余能量；wi为各项的权值。

剩余节点能量则根据节点的剩余电池量得到。节点负载大小采用公式（2）计算：

[LOADi=0.5×rt_live_numberrt_all_number+0.5×NEAR_nodesN_nodes] （2）

式中：rt_live_number为节点当前活动路由数目；rt_all_ number为经过该节点和其邻居节点的路由数总数；NEAR_nodes为邻居活动节点数；N_nodes为节点总数。

rt_live_number与rt_all_number比值可以体现该节点与其邻居节点的业务繁忙情况；NEAR_nodes与N_nodes比值直接说明了该节点是否处于密集区，同时可间接预测该节点随着时间变化的流量。

在目的节点进行路由选取的时候，本文以代价函数最小化为原则。[wi]为可调参数，决定链路中各因子所占比例，根据实际情况进行取值。当节点剩余能量越多，[1Pi]越小，且负载越小，则C越小，路径选取可能性越大。根据代价函数，路由选取过程中可选取一条路径较短，节点剩余能量较多，预测流量较小的路由，从理论上分析改进协议可以延长网络寿命，减少时延，降低丢包率。

2 CF?AODV算法实现

2.1 扩展CF?AODV协议消息

（1） RREQ消息的扩展如表1所示。

路由请求识别码是一个序列号，与源节点IP地址惟一确定一条路由；目的节点序列号为源节点接收到的，到达目的节点的最新序列号；源节点序列号则是源节点正在使用的路由条目中的当前序列号。跳数为从源节点开始达到本节点之间的转发跳数。在此基础上，本文在RREQ中新添加节点负载最大值LOADmax、路径负载总和LOAD?sum、节点剩余能量最小值[Emin]和路径剩余能量总和Energy?sum字段，其余不变。

（2） 路由表的扩展如表2所示。

每个节点维护一张AODV路由表，该表包括很多个路由条目，每条路由条目都包含：目的节点IP地址、目的节点序列号、目的节点序列号有效标志、其他状态标志、网络接口、到达目的节点跳数、下一跳节点IP、预发送节点列表、寿命（本条路由生存时间）等。网络接口为接收分组的无线接口；预发送节点列表里面存储这个节点作为中间节点时的所有上个节点的IP地址。本文在路由表中新添加LOADmax_rt和Emin_rt，用以存储到本节点所经过的所有节点的最大负载和最小剩余能量。

2.2 路由发现过程

如果源目节点间没有活动路由时，启动路由发现过程，广播RREQ消息。在协议实行过程中，每个节点实时监控自身的MAC层接口队列长度和节点剩余能量。

在图1所示的网络拓扑中，存在10个中间节点，每个节点的剩余能量、负载、活动路由数如表3所示，设定能量阈值E0=0.05，L0=50。每个节点的邻居节点由其通信半径R确定，在R内的为邻居节点。路由发现过程如下：

（1） 源节点S到目的节点d之间没有活动路由，S发动路由请求过程，向外广播发送RREQ。节点2收到RREQ，计算LOAD、LOAD?sum和Energy?sum，更新RREQ，向外广播。

（2） 源节点S丢弃收到的节点2转发的自己广播的RREQ消息；节点3能量小于阈值E0，丢弃节点2发送的包；节点1、4更新RREQ，继续广播，但节点1的全部邻居节点都已经接收到相同序列号的RREQ消息，所以节点1没有下一跳节点。此时节点4转播的RREQ：LOADmax=0.35，Emin=0.45，LOAD?sum=0.68，Energy?sum=1.20。

（3） 节点6的接口缓存队列长度大于L0，丢弃接收到的包；节点5继续广播更新后的RREQ。此时节点5转发的RREQ：LOADmax=0.49，Emin=0.45，LOAD?sum=1.15，Energy?sum=1.90。

（4） 节点7、8接收节点5发送的消息，更新RREQ，继续广播RREQ。

节点7转发的RREQ：LOADmax=0.49，Emin=0.45，LOAD?sum=1.44，Energy?sum=2.35；

节点8转发的RREQ：LOADmax=0.49，Emin=0.45，LOAD?sum=1.47，Energy?sum=2.55。

（5） 节点9、10继续广播RREQ，目的节点收到来自源节点发送的RREQ，缓存两条路由。

节点9转发的RREQ：LOADmax=0.49，Emin=0.45，LOAD?sum=1.82，Energy?sum=2.85；

节点10转发的RREQ：LOADmax=0.49，Emin=0.45，LOAD?sum=1.85，Energy?sum=3.25。

根据以上分析，节点收到RREQ时的处理流程如下：

Begin

读取E（i）、MAC层接口缓存队列长度L（i）、路由表中路由数、路由表中邻居节点数和其对应的路由数量

if（E（i）L0）

丢弃该RREQ，返回；

else

{寻找到源节点的反向路由；

if（未找到反向路由）

建立反向路由；

if（RREQ_ID>路由表中存储或LOADmax_rt < LOADmax或 Emin_rt

更新路由表相关项；

if（本机是目的节点）

缓存该RREQ；

else{

if（存在到目的节点的路由）

发送RREP；

else{

计算LOAD（i）；

If（LOAD（i）>LOADmax） LOADmax = LOAD（i）；

If（E（i）< Emin） Emin = E（i）；

LOAD_sum=LOAD_sum+LOAD（i）；

Energy_sum=Energy_sum+ E（i）；

转发该RREQ；

}

}

}

2.3 路由选择过程

目的节点采用延迟应答方案，接收第一个相同序列号的RREQ消息时启动一个计时器，负责记录当前时间。时间达到后，向源节点发送RREP消息。在这段时间内，到达的RREQ消息存储在目的节点缓存项中，每个消息对应一条路由。在图1所示拓扑中，目的节点缓存项中存在两条路由，即：

路径1：S→2→4→5→7→9→d；

路径2：S→2→4→5→8→10→d；

在代价函数公式中，令[w1]=[w2=13，][di-i+1]为跳数，两条路径都为6跳。将剩余能量总和归一化处理，令[w3=63，]则路径1中，C=3.31；路径2中，C=3.23。根据代价函数取小值，选择路径2作为最优路径。

根据以上分析，设[Si]表示从源节点到目的节点的所有可能路由，i=1，2，3，[…]；路由选择算法程序如下：

Begin

For（缓存中的每一个RREQ消息）

{A=Hop Count的最小值；}

For（缓存中的每一个RREQ消息）

{if（Hop Count>=A且Hop Count<=A+3）

该RREQ消息放入集合G1；}

For（G1中的RREQ消息）

{根据代价函数计算Ci，则Min（Ci）；

将Ci最小的RREQ放入集合G2；}

If（G2只有一个）

发送RREP消息；

Else

{比较Emin，选取Emin最大的RREQ消息；

If（只有一个）发送RREP；

Else

{比较Loadmax，选取最小值；

发送RREP消息；}

}

3 实验仿真与结果分析

本文在Matlab平台上对CF?AODV协议进行仿真。整个网络的工作机制如下：通过设置50个网络节点，在1 000[×]2 000的场景中，进行节点随机坐标的分布，设置整个网络的仿真时间（轮数）为200轮；不同节点之间信息传递的信道模型根据节点距离选择Free space[8]和Two?ray ground reflection[9]；路由协议设置AODV和AODV改进两种类型。参数设置完成后整个网络按轮数开始运作，每一轮将剩余的节点数随机排列组合配对，按照不同的协议生成相应的路径，并开始发送数据。每个节点的能量消耗根据能量损耗模型计算，负载按照公式（2）计算，节点当前活动路由数为该轮中该节点所在路径的总数。期间，路径搜索时节点的能量和负载实时变化。每一轮结束后，该轮的所有路径清空，下一轮重新统计。在仿真时间结束后，得到某个时刻路径显示、网络能耗、死亡节点数、标准化路由载荷、无效路由数等指标。

本文节点能量损耗模型[10]采用传感器能量消耗模型，且仅考虑消耗能量较大的无线通信模块，该模块如图2所示。

节点传输m b信息，传送距离为d时的能耗如下所示：

发送端能量消耗模型：

[ET（m，d）=mEelec+mεfsd2，ddc] （3）

接收端能量消耗模型：

[ER（m）=mEelec] （4）

式中：[Eelec]为单位比特数据电路耗能；[εfs]和[εtgr]为放大器传输单位比特数据耗能大小。其中[dc]为无线信道传输模型自由空间模型（Free Space）、双径地面反射模型（Two?ray Ground Reflection）的分界点。距离小于[dc]时使用自由空间模型，反之使用双径传播模型。[dc]计算式为：

[dc=sqrtεfsεtgr] （5）

整个网络的仿真参数设置如表4所示。

图3比较了两个路由协议的死亡节点数。死亡节点数为每轮结束后，从网络开始运行到该轮的全部能量为0的节点数量。刚开始时由于节点初始能量和负载一样，两种协议选择的路径基本一样，所以节点死亡速率也基本一样；随着仿真时间的推移，到某个时间点时，死亡节点数突增，节点死亡速率两者都增大，但是从图中可看出CF?AODV增长速率明显小于AODV，突增时间点也比AODV延后。这是因为CF?AODV在路径选择时首先进行了阈值判断，使得网络内RREQ消息广播数量比AODV少，节点消耗能量也减少；其次考虑了路径剩余能量和总负载，选择了路径剩余能量较高，负载较小的路径，避免了部分节点因为成为较多路径中间节点而能量损耗迅速，造成网络分割的情况发生，使整个网络的能量消耗比较均匀，延长了网络的生存时间。

图4比较了两种算法在不同时刻的标准化路由[1]。标准化路由载荷即每交付给目的节点一个数据分组所需要发送的路由分组的数量，作为评价路由的效率。路由载荷低，网络拥塞减轻。路由分组每当被传输一跳，则计算一次路由分组发送。从图4中可看出，在网络中剩余节点数差别不大的情况下，CF?AODV协议的标准化路由载荷相对于AODV来说较少，这是因为在路径选取过程中通过阈值的判断，减少了广播RREQ消息的数量，减轻了网络的负担。

4 结 论

本文提出了一种基于代价函数的AODV路由协议。在转发RREQ时通过设置能量阈值和缓存队列阈值，来选择剩余能量较高和当前拥塞程度较低的节点来保障链路的有效性，避免节点过早死亡而造成断路；同时减少控制信息的广播，避免广播风暴，减轻网络拥塞。目的节点采用延时应答方案，根据代价函数的值来选取一条能量、负载均衡的最佳路由，使整个网络消耗能量更为平均，同时避免部分节点任务过重，提高整个网络的性能。仿真结果表明，CF?AODV能延长网络寿命，改善网络拥塞。

参考文献

[1] 陈林星，曾曦，曹毅.移动Ad Hoc网络?自组织分组无线网络技术[M].北京：电子工业出版社，2006.

[2] PERKINS C， ROYER E. Ad?Hoc on demand distance vector routing [C]// Proceedings of IEEE WMCSA. New Orleans： IEEE， 1999： 90?100.

[3] YI Y， KWON T J， GERLA M. A load aware routing （LWR） based on local information [C]// Proceeding of the 12th IEEE International Symposium on Personal， Indoor and Mobile Radio Communications. San Diego， CA： IEEE， 2001： 65?69.

[4] ZHOU A， HASSANEIN H. Load ? balanced wireless ad hoc routing [C]// Canadian Conference on Electrical and Computer Engineering. Canada： [s.n.]， 2001， 2： 1157?1161.

[5] SCOTT K， BAMBOS N. Routing and channel assignment for low power transmission in PCS [C]// Proceeding of the 5th IEEE International Conference on Universal Personal Communications. Cambridge： IEEE， 1996： 498?502.

[6] SINGH S， WOO M， RAGHAVENDRA C S. Power?aware rou?ting in mobile Ad Hoc networks[C]// Proceeding of the 4th annual ACM/IEEE international conference on mobile computing and networking. Dallas： [s.n.]， 1998： 181?190.

[7] 刘大伟，金伟，王晓洁.一种节能的Ad Hoc网络路由协议[J].计算机工程与应用，2011（26）：93?94.

[8] 张力军，张宗橙，郑宝玉.数字通信[M].4版.北京：电子工业出版社，2003.

[9] RAPPAPORT T S. Wireless communications： principles and practice [M]. New Jersey： Prentic Hall PTR， 1996：40?60.

[10] 张伟伟.无线传感器网络仿真平台的设计与实现[D].合肥：中国科学技术大学，2009.