基于能量均衡和拥塞程度的改进AODV路由协议

陈书旺,宋树丽,宋彤彤,王真真,尹晓伟,黄 涛

(1.河北科技大学信息科学与工程学院，石家庄 050000；2.河北科技大学教务处，石家庄 050000)

无线自组网(wireless Ad Hoc network)是由一组移动节点动态形成的网络，以无线链路的方式进行数据传输，且不需基础设施的临时性网络[1]。并且具有无中心性、拓扑动态性、抗毁性等特点。主要应用在军事和民用方面，尤其是应用在通信设施资源匮乏的场合中。而自组网节点进行通信的前提是路由协议，因此路由协议成为目前自组网体系结构中的热门研究对象。中外的一些学者提出了许多路由协议标准，路由协议的性能不同导致所适用的环境不同。根据路由发现策略的不同分为两类：①反应式表驱动路由协议，如DSDV(destination sequenced distance vector routing)、WRP(wireless routing protocol)等；②反应式按需基于源端路由协议，如DSR(dynamic source routing)[2]、AODV等[3]；其中表驱动路由协议需要周期性地广播路由更新消息，这类路由协议需要较高的资源代价，路由成本大、能量利用率较低。而按需路由协议非常适用于自组网，不需要实时维护路由消息。可以节省网络资源，提高能量利用率，减少拥塞，适应网络的拓扑变化，延长网络的生存时间。

AODV[4-5](Ad Hoc on demand distance vector routing)是一种典型的按需路由协议，包括路由发现和路由维护两个阶段。当源节点需要与目的节点建立通信链路时，首先要在通信范围内广播RREQ(routing request)，中间节点会根据是否是首次收到RREQ来决定是否转发，目的节点收到RREQ后需要向源节点回复RREP(routing reply)。报文RREP会经过中间节点回到源节点，此时就建立了路由路径。通信过程中在遇到链路中断时AODV会发起本地路由修复进行维护。

相比于其他路由协议，AODV路由协议的只有在需要时才会发起路由寻找，这样提高了网络资源利用率，减少延迟。AODV路由协议能快速响应网路的拓扑变化，并且不会形成环路。由于人们对网络性能的要求不断提高，近年来许多学者对AODV路由协议在不同方面进行了优化。Ranjan等[6]提出了IOAS-AODV(improved optimum angle selection-AODV)一种新的路由算法，通过基于象限位置，电池状态，队列长度，选择一组交替路径的有限节点来避免拥塞和修复断链。陆伟等[7]对于能量损耗提出了一种新的改进机制，构造了一种数学模型，其中包含节点的信号属性。根据链路质量和能量的消耗情况来选择路径。此协议在通信中不仅能保证能量消耗最小还能选择最优的路径。何王吉等[8]提出了一种电量估算策略，将复合期望传输次数和节点的剩余能量作为路由度量。改进后的算法有效减少能量损耗,延长网络生存时间。文献[9]针对拥塞问题提出了一种新的机制，根据路由度量得到函数拟合曲线，根据拟合曲线来设定不同的阈值。由平均队列与阈值的关系决定是否丢弃报文。这种新的机制在路由性能方面都优于传统的AODV。李爱武等[10]对路由协议在拥塞方面进行了优化，在平均队列的基础上提出了动态检测的方式，根据拥塞程度向相邻节点发出信号，邻居节点尝试找出一条可替代的路径来进行通信。这种改进的算法提高了路由协议的性能。文献[11]针对拥塞提出了两种优化协议：EDAODV(early detection congestion and control routing protocol)和AODV-I(improved Ad-Hoc on-demand distance vector routing protocol)，其中EDAODV采用双向路径发现，预先检测拥塞，而AODV-I协议在RREQ中添加了拥塞处理，可以避免选择忙路由，同时RREQ还添加了路由修复机制，这种改进使资源能充分利用。

自组网中由于每个无线节点的能量可用性有限，在通信过程中节点的能量会不断减少直至耗尽，所以在数据转发过程中考虑能量是非常必要的。而保证链路稳定传输就必须要考虑拥塞问题，拥塞的后果会导致数据丢失甚至网络发生崩溃。因此路由度量的选择对于通信质量至关重要。AODV路由协议只将跳数作为选择路径的标准，学者们在选择路径时只加入了能量或拥塞因素，这使得路径的选择变得局限。

基于以上的背景和分析，以AODV协议为基础，将路径拥塞和能量损耗同时考虑在内，并且将能量状态和拥塞状态分成不同的等级并用不同的跳数来表示。引入了跳数代价和路径判断因子，根据跳数代价和实际跳数得出每段路径的总跳数，最后利用路径判断的公式将每段路径的跳数累加得到最终的跳数，选择跳数最少的路径进行数据的传输。改进后的路由协议有效地减少网络拥塞，减少延迟，提高节点的存活率。

1 改进的路由选择算法的度量指标

1.1 拥塞度量——跳数

当链路发生拥塞时会造成丢包率增加、端到端时延增加、吞吐量下降等问题。用缓冲区占有率(buffer occupation rate,BOR)来衡量拥塞程度，缓存占用率表示：某一时间段此链路的队列长度与链路最大可承载长度的比值。拥塞度(congestion degree,CD)的表示方法：

(1)

式(1)中：Lt为某一时间内链路的队列长度；Lm表示链路最大可承载的长度。其中，Lt为一个不断变化的值，Lm为一个定值。AODV协议中，路径的选择是以跳数的大小为标准。所以提出将拥塞以跳数的形式表示，引入一个拥塞因子C(hhops)。将拥塞度转化为跳数分为以下三种情形。

(1)CD≤20%时，表示链路处于稳定的状态，基本上不会发生拥塞，数据可以正常通信，此时跳数代价为0，即：

C(hhops)=0

(2)

(2)20%

C(hhops)=3

(3)

(3)CD≥60%时，数据缓冲区已经要达到饱和状态，开始处于丢包阶段，丢弃数据包，增加端到端的时间。此时的跳数代价为6，即：

C(hhops)=6

(4)

1.2 剩余能量——跳数

在复杂的网络环境中，考虑能量因素是至关重要的，由于AODV的重传次数增加，会引起网络风暴，造成不必要的能量消耗。选择剩余能量大的节点进行数据的接收和发送，可以延长网络的生存时间。剩余能量等级表示为

(5)

式(5)中：Ei为节点i的剩余能量；Es为节点的初始能量。为了将能量以跳数的形式表示出来，引入一个能量因子E(hhops)。分以下四种情况讨论。

(1)当Er≥0.5时，表明节点剩余大量能量，可以正常通信，接收和转发数据。此时的跳数代价为0，即：

E(hhops)=0

(6)

(2)当0.2

E(hhops)=3

(7)

(3)当0.1≤Er≤0.2时，表明节点能量损耗大部分，所剩无几了，为了在数据传输的时候尽量地减少时延，防止此类节点参与通信传输。跳数代价设为6，即：

E(hhops)=6

(8)

(4)当Er<0.1时，表明节点已经接近枯竭，只能作为目的节点来接收数据。

1.3 路径判断因子ω

在CE-AODV-H协议中，定义了判断因子ω作为路由选择的判定依据：

ω=ω0+ω1+…+ωi

(9)

式(9)中：ω0～ωi分别表示每段路径的稳定判断因子，ωi表示AODV路由在选择路径时的综合考量，其表达式为

ωi=αC(hhops)+βE(hhops)+μhhops

(10)

式(10)中：α、β、μ为权重因子，均为小于1的正整数，且α+β+μ=1，可以根据自组网的具体应用场景来设定。根据式(9)计算最后的ω。选择ω最小且目的节点序列号最新的链路进行通信。如果ω相同，选择最先到达目的节点的链路。

2 最优路径的发现和建立

(1)改进后的路由协议在路由表中增加了三个字段，CD、Er和ω。

(2)在路由请求RREQ中增加ω0字段。作为选择路径的依据。

(3)运行路由协议前对α、β、μ进行赋值。

2.1 路由发现

源节点需要向目的节点发送数据包时，首先要检查路由表中是否有到达目的节点的的有效路由，如果没有就执行路由发现过程，在发送数据前，计算的节点CD和Er算出ω0，填入RREQ报文中的ω0字段处。

2.2 中间节点对RREQ的处理

中间节点在接收到RREQ包时，首先建立一个用于记录反向路径的表项，先不分配有效序列号，如果是第一次收到RREQ首先要判断节点剩余能量的等级Er。

(1)如果Er<0.1时，则直接丢弃该节点。

(2)如果能量-跳数代价为式(6)～式(8)情况下记录此时的跳数，其次判断拥塞度，并记录此时的总跳数ωi。然后继续RREQ的数据转发。中间节点转发流程图如图1所示。

图1 中间节点转发流程Fig.1 Intermediate node forwarding process

2.3 目的节点对RREQ的处理

为了选择最优的路径，目的节点同样需要对路径进行能量和拥塞的判断，当RREQ到达目的节点后，设定等待时间的上限，超过等待时间，此时要更新该节点的路由表信息，根据路由表携带的跳数、拥塞、能量计算路径的ωi，最后选择ω最小的路径进行RREP的转发。

2.4 改进算法路径选择实现

图2为改进算法的路径选择过程，将拥塞和能量考虑在内。从图2中可以看出，从源节点S到目的节点D共有三条路径，L1：S→A→B→D；L2：S→A→C→E→D；L3：S→F→G→D。由于此网络对能量比较敏感，所以将β赋值为0.5，α设为0.2，μ为0.3。设定节点初始能量为100 J,链路最大可承受长度为50。某一时刻节点状态：L1路径：实际跳数为2，节点A的剩余能量为60 J，拥塞度为2/5，节点B的剩余能量为20 J，拥塞度为3/5。L2路径：实际跳数为3，节点A的剩余能量为60 J，拥塞度为2/5，节点C的剩余能量为50 J，拥塞度为1/5，节点E的剩余能量为40 J，拥塞度为1/5。L3路径：实际跳数为2，节点F的剩余能量为30 J，拥塞为2/5，节点G的剩余能量为9 J，拥塞为3/5。

图2 路由建立过程Fig.2 Route establishment process

传统的AODV会选择L1I路径或L3路径，但将能量和拥塞考虑在内，在选择路径时，由于节点G的剩余能量等级Er<0.1,所以丢弃该节点，排除路径L3。根据式(9)、式(10)计算链路的ω的值，得出路径L2的ω大于路径L3的ω。最终选择L2路径为最优路径进行传输数据。

3 仿真与结果分析

使用仿真平台为网络仿真器NS2(network simulator-2,NS2.35)。仿真参数设置：①区域面积： 1 000 m×500 m；②节点移动速度：0～10 m/s；③模拟时间：100 s；④移动模型：随机路点模型；⑤无线模型mac：802.11；⑥连接数：10；⑦数据包尺寸：512 B；⑧字节初始能量：100 J；⑨暂停时间：0、25、50、75、100 s。

衡量路由协议的标准为路由开销、数据包投递率、节点存活率和端到端时延。路由开销指路由消息数与节点发送数据包的比值。反映了网络的路由效率。数据包投递率表示目的节点所接收的数据包与源节点发送的数据包之比，反映了网络传输的可靠性。端到端时延即包的延时就是指包的接收时间与包的发送时间差。节点存活率指模拟时间结束所存活的节点与总节点数的比值。通过改变暂停时间来仿真AODV、CE-AODV-H和AODV-I路由协议。

图3 端到端的时延Fig.3 End-to-end delay

图3表明CE-AODV-H、AODV和AODV-I三种路由协议的端到端时延整体上随着暂停时间的增大而减少，在暂停时间较小时，节点移动速度快，网络拓扑结构变化迅速，节点的能量消耗快，链路队列易发生拥塞。AODV-I路由协议只将拥塞考虑在内，在端到端时延方面由于AODV协议，而提出的路由协议中，选取剩余能量大的节点传输，控制队列长度能有效地缓解拥塞，比AODV-I和AODV路由协议的时延都小。

图4、图5表明改进后的路由协议CE-AODV-H在数据包投递率和路由开销方面方面优于AODV和AODV-I路由协议，暂停时间增加，节点移动变慢，路由转发次数减少，路由开销也就减少，数据不易发生丢包，数据包投递率增加，改进的协议引入了能量和拥塞的等级来选择最短路径，有效地提高了数据包投递率。

图4 数据包投递率Fig.4 Packet delivery rate

图5 路由开销Fig.5 Routing overhead

图6 节点存活率Fig.6 Node survival rate

图6为在整个仿真时间内节点的存活情况，随着暂停时间的不断增加，节点的存活率也不断增加。在仿真的过程中用跳数来表示能量的等级，剩余能量大，跳数代价小，参与通信时可以更好地避免节点死亡，因此相比于AODV和AODV-I路由协议，CE-SODV-H可以更好地提高节点的存活率。

4 结论

针对数据传输过程中能量消耗过大导致节点死亡、队列长度过长导致拥塞，提出了CE-AODV-H改进路由协议，通过缓冲区占有率将拥塞分成不同的等级，同时将剩余能量也划分等级，丢弃能量小的节点，不同的等级用不同的跳数代价表示。基于能量和拥塞跳数最小建立路由，同时还考虑了权重因子α、β、μ的配置问题，可以根据不同的场景灵活的配置，更好地满足路由需求。仿真结果表明，CE-AODV-H路由协议相比于普通的AODV路由协议减少了路由开销和端到端的时延，提高了数据包投递率和节点的存活率。路由性能进一步得到了改善。