AOMDV多路径协议的研究和改进

李子璇　童孟军　江浩然

摘 要： 由于WSN网络中每个节点的能量都是有限的，并且很难对电池充电再使用，所以能量就成为衡量一个网络好坏的关键因素。针对节点间通信问题，传统的AOMDV协议仅仅考虑了时延最短因素，常常导致某些节点局部死亡，甚至会导致整个网络被分割。为此，提出一种新的协议RED-AOMDV，会考虑端到端时延的因素，会根据每条路径的最大剩余能量来选择最优路径。改进协议综合考虑每个节点中的能量值和时延，让已有的多路径均衡地承担转发数据的任务。实验结果表明，改进协议在节点能耗、投递率和网络生命周期等方面都较之前的协议有了较大的提高。

关键词： 多路径协议； 节点能耗； 最优路径； 时延

中图分类号：TP393 文献标志码：A 文章编号：1006-8228（2016）08-07-06

Abstract： Since the energy of each node in WSN network is limited， and it is difficult to recharge the battery， so the energy becomes a key factor to measure the network performance. For inter-node communication problems， the traditional AOMDV（Ad hoc On-demand Multipath Distance Vector Routing） protocol considers only the shortest delay， which often leads some nodes to the local death， or even causes the entire network to be divided into many small networks. This paper proposes a new protocol RED-AOMDV， will consider the end to end delay factors， and will choose the optimal path according to the maximum residual energy of each path. The improved protocol considers the energy value and delay of each node to allow the data forwarding in between the existing multiple paths in a balanced way. The experimental results show that the proposed protocol has been greatly improved in terms of energy consumption， delivery ratio and network lifetime.

Key words： multipath protocol； the energy consumption of nodes； optimal path； delay

0 引言

在WSN中，节点扮演一个路由器的角色。这样的网络具有以下特点：拓扑易变化、带宽约束、能源受限，而且易出现安全问题。鉴于以上情况，路由将会是WSN中一个很重要的问题。

每个参与路由维护和数据转发的节点都支持端到端通信。这些节点通常是小电池供电的设备，能够感测、存储、数据处理以及通过无线电节点与其他节点通信。在许多应用领域中，想要为节点充电或者是更换电池是不切实际的，因此网络能量效率最大化是设计节点的关键所在。

最初的路由协议使用跳步数作为主要指标参数[1-2]，但延迟往往间接影响路由选择[1]。更多新的协议使用一些其他的度量值，比如信号强度[3]、网络稳定性[4]和负载均衡[5-6]，这些新的度量值都会影响性能并且间接的消耗能源。能量也可以用于作为路由选择路径的一个参考标准，通过它可以最大程度地降低能源消耗或者避免选择那些即将因为能源不足而死亡的节点。设计路由协议最大的挑战就是能源的有限使用率。相比有线网络，无线网络中能源的有限性是显而易见的。节能通信是提高WSN的生命周期的关键所在。

之前Radhika等[7]已经提出了一种基于AODV（Ad hoc on-demand distance vector routing）的能量感知路由协议，通过所有节点的最小剩余能量来确定一条最优的路径。该协议综合考虑了跳步数和能耗两个方面。Soo-Bum Kim等[8]在AOMDV基础上评估了能量感知的性能[9]。

在AODVEA（AODV Energy Aware）协议中，将会选择路由的最小剩余能量作为度量值。拥有最小剩余能量的节点被标记出来，而最大的剩余能量的那条路径将会被选中。所以在协议设计过程中，将会在RREQ（RouteRequest）和RREP（RouteReply）结构中添加一个Min-RE（Minimum Remaining Energy）字段。该字段将会记录所在路径的最低能量剩余值。

AODVM（AOMDV Modified）协议是在AODVEA基础上在Min-RE字段中添加一个每跳能量值，并加入到RREQ和RREP的结构中。当中间节点收到一个RREQ包，跳步数会加一并且重新改变Min-RE字段中最小剩余能量的值。

当目的节点收到所有信息后，它将决定一条最佳路径，并通过这条路径以单播的方式发送RREP包给源节点。AODVM中度量值的计算公式如式⑴：

目的节点根据收到的所有路由信息并计算出α值，并且选择α最大值的那条路径为最优路径。

本文进一步改进之前的协议，通过充分利用节点的剩余能量来选择一条最适合的路径并且考虑整个网络端到端时延问题的解决方案，进而优化现有的路由策略。

1 能量消耗模型

节点因数据包转发而损失能量有以下两种方式：发送数据包和接收数据包，而这两种方式所造成的能量损失是不同的。RT（Packet Retransmission）表示重新发送报文，PF（Packet Failure）表示数据报文被丢弃，AF（Acknowledgement Failure）表示收到链路因为各种原因不能正常工作。因此对于数据发送和数据接收所损失的能量模型公式如式⑵和⑶。

其中，带有Success的表示成功接收/发送数据所损失的能量，带有AF和PF的表示由于数据传输过程中遇到丢弃或者链路故障所导致的能量损耗；i表示节点硬件工作时的电流值，Lpack表示数据的长度。式中的能量损耗考虑了无线通道使用指数路径损耗和特征路径损耗。节点的状态转换由图1表示。

其中，PD和Idle状态属于当前闲置状态，而RX和TX两个状态属于真正的数据传输状态。

2 改进的RED-AMODV协议

2.1 RED-AOMDV协议介绍

AOMDV协议选择源节点最先接收到来自目的节点发来的RREP报文的路径为转发数据的路径。研究结果表明，拥塞少的路径相比跳步数少的路径而言，具有更短的端到端的时延。RED-AOMDV（Remaining Energy Delay for Ad hoc on-demand multipath distance vector routing）协议主要是针对节点能源的有限性和节点间频繁的中断这些问题而设计的一种多路径路由协议。

2.2 RED-AOMDV协议报文改进设计

RED-AOMDV协议新添加了两个字段：received time（Tr）和transmission delay（Delay）。Tr字段表明收到RREQ报文的时间，Delay表明本节点和上一个节点收到RREQ包的时延。在原有的RREP报文的基础上，新添加了一个字段：remaining_energy（Er），用来标识每个节点的剩余能量。新改进的RREQ和RREP报文结构如图2、图3所示。

S-IP—源节点的IP地址。

D-IP—目的节点的IP地址。

Sequence Number—节点自身的序列号。

hopcount—跳步数，RREQ包类型的跳步计数初始值为0。

Timeout—时间戳。

Tr—节点收到RREQ报文的时间。

Delay—节点收到RREQ包的时延。

Er—节点的剩余能量。

2.3 RED-AOMDV中RREQ报文发送

如果有数据要从节点S发送到指定节点D，S必须判断本节点有没有直接到达D的转发路径。

当中间节点N1收到来自源节点的RREQ报文，N1会将此时的时间记录到Tr字段中保存下来，然后将RREQ报文转发给邻居节点。邻居节点N2收到RREQ时，会根据此时的时间和RREQ报文中所记录上一个节点（N1）的时间计算出RREQ报文从N1转发到N2的时间间隔，计算公式如式⑷：

中间节点N1自己会定义一个时延门阈值[9]，如果时延超过这个阈值就表明两者之间不可达，并且在N1不能发送任何相关的报文；否则，节点首先将自己收到RREQ报文的时间记录到Tr字段中，并且计算出时延值记录到Delay字段中，并将该RREQ报文转发出去。当目的节点收到RREQ报文时，目的节点会将整条路径的总时延值计算出来。根据RREQ包的时延数据，利用式⑸来计算出数据报文传输的时延值：

2.4 RED-AOMDV协议RREP报文发送

目的节点接收相应的报文后，生成一个对应的应答报文RREP，并且通过RREQ来的路径反向发送出去。当中间节点收到RREP报文时，会将节点自己的剩余能量记录到RREP中的Er字段中，并将RREP报文前向发送给邻居节点。当源节点收到RREP报文时，该报文记录了该条路径上所有节点的剩余能量。源节点根据式⑹来选择最适宜的转发路径

En表明路径中参与数据传输的节点的剩余能量， Delay（i，j）表明节点i与节点j之间数据传输的时延。数据传输过程中，传感器节点可能因为能源不足导致不能进行转发，所以每个节点需设置一个最低能量值，如果当前节点的能量值低于这个门阈值，说明该节点不可用，经过这个节点的路径都标识为无效路径，并且向源节点发送RRER分组，源节点会从路由表中删除所有不可达的路由，防止数据传输中因为能耗原因发生丢包情况。

2.5 RED-AOMDV协议路由表结构

RED-AOMDV协议新添加了两个字段：delay字段和remaining_energy字段。具体路由结构如图4所示。

每个节点会根据remaining_energy字段的值进行降序排列。

2.6 RED-AOMDV算法流程图

RED-AOMDV协议RREQ算法流程如图5所示。

2.7 RED-AOMDV算法开销分析

路由开销的大小直接影响数据传输的性能。RED-AOMDV协议是按需的，其开销主要是路由发现过程中的消耗和当链路失效时进行的检测控制分组，主要包括RREQ、RREP和RERR等。

当需要发送数据时，源节点首先检查路由表中是否有达到目的节点的可用路由，若有则直接发送，否则通过广播RREQ分组发起路由发现过程。其他节点收到RREQ分组后，会检查源地址和标识号是否已经收到过，如果收到，则丢弃这个分组。如果路由表中有到目的节点的路由，则复制路由记录表到RREP分组中，并反向发送到源节点。否则将自己的地址加入到路由记录表，重新广播这个RREQ分组，知道源节点收到目的节点的RREP分组，将路由信息存入路由缓冲器中，路由发现过程结束。在这一过程中，各种分组的转发将会消耗一定的能量。

在按需路由协议中，路由维护和路由发现一样，会增大整体开销。当数据分组在传输过程中检测到链路失效，链路上游节点则向源节点回传一个RERR分组，收到RERR分组后，源节点从路由缓冲条目中删除所有不可达的路由。此时，若路由表中没有备用路由，源节点将重新启动新的路由发现过程。此外，RED-AOMDV协议自身的HELLO分组机制同样会带来一定的开销。

3 仿真环境及RED-AOMDV协议仿真分析

本次实验是在ubuntu10.04操作系统下，通过NS2模拟软件[10]进行仿真实验。

3.1 协议添加

在NS2中，我们需要添加RED-AOMDV协议。添加一个新的协议模块需要如下几个步骤：添加协议类、定义协议分组头结构、编译代码。下面是RED-AOMDV协议中的几个主要文件：

～ns/RED-AOMDV/RED-AOMDV.cc

～ns/RED-AOMDV/RED-AOMDV_pkt.h

～ns/RED-AOMDV/RED-AOMDV_queue.cc

最后对新添加好的协议进行编译，如果编译成功，那么说明协议添加成功。

3.2 仿真场景和参数设置

节点移动模型为random waypoint模型[11-12]，节点在最小速度和最大速度间以一个随机速度向目的节点运动。一些仿真系统初始化环境参数如表1所示。

3.3 实验结果及性能分析

通过NS2实验仿真，将实验数据保存到trace文件中，再编写相应的awk脚本得到所需数据。下面从三个角度对协议进行比较分析。

⑴ 网络生命周期

节点的正常生存是整个网络能够正常工作的最基本的前提，如果节点死亡，那么整个网络就没有任何研究价值，因此，节点在网络中生存时间的长短是网络性能的一个很重要的衡量值。许多文献给出了不同的网络生命周期的定义，为了便于比较分析，本次实验使用网络中第一个节点耗尽能量的生命周期。

图6表明节点在AOMDV、RED-AOMDV、AODV协议中，首个节点死亡时间随着节点数量变化而变化。总体来看网络中随着节点数量增多，网络生命周期有逐渐变小的趋势。这是因为在计算路由时会消耗很多的能量。当网络中节点数量较少时，路由表中路由条目较少，路由控制包较小，其能量花费较少。随着网络节点数增多，每个节点的路由表项会变的很多，二期路由控制包也变大，那么能量消耗速度更快，网络生命周期都变小。根据图6来看，AODV中的节点生存时间最短，AOMDV生存时间次之，而改进后的协议RED-AOMDV中的节点生存时间最长。由于AODV协议只是单路径路由协议，如果该路径断开后，有新的数据发送时，就会重新发起一次寻路过程，在这个过程中，会消耗节点的能源，导致节点过早死亡；而AOMDV协议是多路径路由协议，当转发路径断开后，可以立即启用备用路径，减少了因再次发起路由寻找过程而消耗的能量；RED-AOMDV协议中，考虑了能量和时延这两个参数，由于AOMDV协议在没有其他影响的情况下，一般是由于转发路径上的节点能量耗尽才会导致该条路径不可用，但是RED-AOMDV协议不会等到节点能量即将耗尽时才切换链路，保证了节点的生存时间，因此RED-AOMDV协议中的节点生存时间最长。

⑵ 分组投递率

接收信息是无线传感器网络的一个最终目的，因此接收的数据量的多少也就成为衡量这个网络的重要标准。接收报文数与发送报文数的比值越高说明收到的数据报文就越多，表明整个网络的性能越好，反之则越差。

图7表明三种协议的分组投递率随着移动速度的变化而变化。随着节点移动速度的逐渐变大，三种协议的分组投递率呈逐渐降低的趋势。从整个过程来看，RED-AOMDV协议的分组投递率最好，比AODV效率提高了约15%～19%，比AOMDV协议提高了约5%～10%。由于AODV是单路径转发数据，而另外两个协议都是多路径转发数据，因此在数据流比较大的时候，AODV协议的效率相比而言就比较低，另外，节点的高速移动导致链路的不稳定性概率增大，这也是导致AODV效率低下的一个原因。RED-AOMDV协议考虑到了数据传输时延并考虑了链路中节点的能量这两个因素，因此相比AODV、AOMDV这两个协议来说具有更好的投递率。

⑶ 路由开销

仿真中的路由开销是指每个节点平均收到一个报文时所需要的非数据报文的数目。平均需要的非数据报文数越少，表明整个网络越好。

图8表明三个协议中每个节点的能量消耗随着节点移动速度的变化而变化。随着节点移动速度的增大，三个协议中每个节点的能量消耗都呈逐渐递增的趋势，这主要是由于移动速度的增大，使得整个网络拓扑处于不稳定状态，所需要的控制报文也就会随之增多。从图8可知，RED-AOMDV协议的能量消耗低于AODV和AOMDV，并且其递增趋势也明显小于这两个协议。这主要是因为RED-AOMDV协议同时考虑了时延和能量这两个因素，减小了网络的拥塞。

4 结束语

针对传统的AOMDV协议仅提供多条传输路径且当前路径故障才启用备份链路，以及未考虑节点能量的弊端，本文研究了能量枯竭导致节点死亡这一问题，基于AOMDV协议提出了RED-AOMDV协议，该协议在选取传输路径时，综合考虑每个节点的能量值和时延，会根据每条路径的最大剩余能量来选择最优路径。RED-AOMDV协议主要是针对节点能源的有限性和节点间频繁的中断问题而设计的一种多路径路由协议。通过NS2仿真表明，改进后的RED-AOMDV协议相比AODV和AOMDV协议，在性能上有了较大提高，改善了网络通信的质量。

参考文献（References）：

[1] Ducksoo Shin， Jonghyup Lee， Jaesung Kim， Jooseok. A2OMDV： An adaptive ad hoc on-demand multipath distancevector routing protocol using dynamic route switching[J]. Journalof Engineering Science，2009.4（2）：171-183

[2] Yusuke Sakurai， Jiro Katto. AODV Multipath Extensionusing Source Route Lists with Optimized Route Estab-lishment[J]. International workshop on wireless ad hoc networks （IWWAN），2004.

[3] Sujata V.Mallapur， Sujata. Terdal.Enhanced Ad-Hoc on Demand Multipath Distance Vector Routing Potocol （EAOMDV[J]. （IJCSIS）International Journal of Computer Science and Information Security，2010.7（3）.

[4] Shuchita Upadhayaya， Charu Gandhi. QoS routing using link and node stability in mobile ad hoc networks[J]. Journal of Theoretical and Applied Information Technology，2009.6（4）.

[5] R. Vinod Kumar， R.D.Wahida Banu. Load-balancing Approach for AOMDV in Ad-hoc Networks[J]. IJC Special Issue on “Mobile Ad-hoc Networks”MANETs，2010.

[6] Gue H， Low K-S， Nguyen H-A. Optimizing the

localization of a wireless sensor network in real time based on a low-cost microcontroller[J]. IEEE Trans Ind Electron，2011.58（3）：741-749

[7] Radhika D. Joshi & Priti P.Rege. Energy Aware Routing in

Ad Hoc Networks[C]. 6th WSEAS International Conference on CIRCUITS， SYSTEMS， ELECTRONICS， CONTROL & SIGNAL PROCESSING， Cairo， Egypt，2007.12（8）：29-31

[8] Soo-Bum Kim， Ji-Hoon Lee， Seung-Yeon You， Sung-Wook Kim， Sung-Chun Kim. Power-aware Pat Selection Scheme for AOMDV[J]. Brain Korea21 Project I，2006.

[9] 童孟军，江浩然，郑拓.基于距离能量感知的 AOMDV协议研究[J].杭州电子科技大学学报，2014.34（2）：28-31

[10] 余本功，余超凡，刘刚.基于AODV和AOMDV路由协议的多移动节点通信分析[J].价值工程，2014.（15）：194-195

[11] Yang Tao， Oda Tetsuya. Performance evaluation of WSNs for different MAC protocols considering TwoRayGround radio model and AODV Routing Protocol[C]. Conference on Complex， Intelligent， and Software Intensive Systems，2012.

[12] Durrenbach Alban， Fourestie Benoit， Rault Maryna.Global shadowing margins for 3G Networks[C]. 57th IEEE Semiannual Vehicular Technology Conference，2003.2（57）：798-802