能量高效的无线传感器网络AODV路由协议研究

金仁成，孟丽莎，韦 宁，李东旭

(大连理工大学，辽宁省微纳米技术及系统工程重点实验室，辽宁 大连 116024)

0 引言

无线传感器网络(WSNs，wireless sensor networks)是由众多具有传感、数据处理和短距离无线通信能力的传感器通过无线方式连接，相互协作，同物理世界进行交互，共同完成特定的应用任务。WSNs在军事国防、环境监测、生物医疗、抢险救灾及商业应用等领域具有广阔的应用前景[1]。

路由协议是无线传感器网络关键技术之一，无线传感器网络路由协议有多种分类方法，其中主动型和按需型是最基本的分类方法[2]。主动型路由继承了传统的距离矢量路由，但在消除路由环路和过期路由等方面做了适应于自组网特性的改进[3]。按需型路由协议中节点并不维护尚未需要的路由，因此所产生的路由控制开销比主动型协议少得多，更有利于扩展推广[4]。AODV路由协议属于典型的按需型路由协议，易于实现[5]，但是传统的 AODV存在能耗大、较易产生通信冲突等不足，本文针对这些不足提出了改进方案，并在自主开发的ZigBee节点平台上进行了相应的性能测试。

1 AODV路由协议

AODV[6]路由协议(Ad-Hoc On-Demand Distance Vector Algorithm)是最经典和最广泛被研究的按需路由协议之一。当一个节点需要到达目的节点的路由时，启动一个路由发现过程，广播路由请求消息(RREQ，route request)。中间节点收到这个路由请求消息时若有RREQ所查找的有效路由，或者就是目的节点，就产生并发送路由应答消息(RREP，route reply)返回路由发起节点。路由建立后，路由中的每个节点在规定的有效时间内，都要维护活动路由的下一跳和上一跳信息，直到该路由不再被使用而删除相关信息。路由中的每个节点都保留了一个路由表，该路由表保存了到达目的节点的路由中把自己作为下一跳节点的相邻节点。在AODV协议中，源节点到目的节点路由的逐跳次数被用来度量路由的优劣。AODV协议依赖网络中的每个节点都拥有并维护自身的目的序列号来避免到该节点的所有路由出现环路。节点每当接收到目的节点新的信息时，立即增加它自身的序列号。

在AODV路由中按需路由协议的路由查找、路由回复、路由错误和数据转发都得以实现，而AODV和其他的按需路由协议(如DSR、LAR路由协议)一个主要的改进是加入了路由表，尽管路由表有一个生存时间，一旦时间到了就被删除，但是AODV路由协议还是被称为是把按需路由和表路由结合起来的一种新型路由算法[7]。AODV协议路由建立过程，如图1所示。

图1 AODV路由算法简介

(1)假设节点N8有数据要发往目标节点N0，首先源节点检查路由表，如果没有找到目的节点或路由表已过期，源节点将广播一个路由请求消息RREQ，RREQ报文里携带以下信息字段:源地址、源序列号、广播ID、目的地址、目的序列号和路由损耗等。

(2)中间节点(N3、N6和 N7等)收到 RREQ后，首先查找路由表中是否有到目的节点的路由，如果有到达目的节点的路由，则回复路由响应RREP;反之，判断其目的地址是否是本节点地址，如果不是，继续向它们周围的邻居节点转发该路由请求RREQ。同时中间节点也会记住这个路由信息，包括源节点、目的节点、上一跳地址和路由损耗等。

(3)经过多跳广播后，目标节点N0收到这个RREQ报文，同样，判断其目的地址是否是本节点，如果是，则回复路由响应RREP报文，RREP沿反向路由到达源节点N8，并建立前向路由。

源节点通过广播一个路由请求分组发现了一条通往目标节点的路径，然后把要传输的数据沿着找到的路径传送出去，中间节点也会动态地维护该路径，以便正确转发数据。源节点N8到目的节点N0有多条路径，但AODV是基于最小跳数的，所以路由选择N8-N3-N1-N0。

虽然AODV协议有较好的性能表现，但也存在一些问题:在路由发现过程中，AODV使用洪泛机制实现，而在大规模的WSNs中若直接使用AODV协议会造成很大的网络开销，并且在实际应用中发现RREQ报文的冲突几率也很高。

在ZigBee网络建立之初，有节点会率先成为簇头，以该簇头为中心，其他节点由自组网算法关联组成一棵逻辑树。其局部网络结构，如图2所示。这时，如果节点N4需要簇头节点N0的路由，节点N4首先会向其周围广播RREQ报文。因为AODV使用洪泛机制，因此节点N6、N7、N8等节点在接收到RREQ报文后会向其周围继续广播该报文，直到达到路由损耗的上限。但显然节点N6、N7、N8等节点并不需要参与路由的发现过程。由于WSNs中节点的能量十分有限，且节点大部分能耗来自于无线通信消耗，因此如何在建立路由的过程中减少通信开销成为路由协议设计的重要目标。并且一般情况下发送数据所消耗的能量与发送距离的平方成正比[8]，因此在基于最小跳数的路由选择中，也要考虑距离因素。针对这些问题，本文在AODV路由协议基础上进行了一些改进。

图2 WSNs局部逻辑结构

2 AODV路由协议改进方案

2.1 ZigBee组网技术

ZigBee网络建立之初，当前未加入任何网络的节点会建立一个新的ZigBee网络，这个发起建立网络的节点就是该网络的簇首节点。簇首节点首先进行IEEE802.15.4中的能量探测扫描 (energy detection scan)和主动扫描 (active scan)，选择一个空闲信道建立网络，并确定自己的16 bit网络地址、网络的PAN标识符等，其中PAN ID是网络在此信道中的唯一标识。各项参数选定后，簇头节点便可以接受其他节点加入该网络。

当一个未加入网络的节点想要加入当前网络时，便向网络中的节点发送关联请求，收到关联请求的节点如果有能力接受其他节点为其子节点，就为此节点分配一个网络中唯一的16 bit网络地址，并发出关联应答，收到关联应答后，此节点成功加入网络，并可以接受其他节点的关联。节点加入网络后，将自己的PAN ID标识设为与簇首节点相同的标识。一个节点是否具有接受其他节点与其关联的能力，主要取决于此节点可利用的资源，如存储空间、能量等。

2.2 基于路径深度的AODV路由协议优化

ZigBee网络建立之初，节点通过自组网算法关联组成一棵逻辑树。当网络中的节点允许一个新节点通过它加入网络时，它们之间就形成了父子关系，每个进入网络的节点都会从父节点分配到网络中唯一的16bit网络地址，其地址分配算法为

式中，Cskip(d)为路径深度为d的路由节点的地址空间;Cm为汇聚节点最大子节点数，取值为20;Lm为汇聚节点最大路径深度，取值为10;Rm为汇聚节点最大路由节点数，取值为6。因为实际系统中各个相关参数是定值，因此Cskip(d)也都是常值。

当一个路由节点的Cskip(d)为0时，不再具备为子节点分配地址的能力;反之，则可以接受其他节点为它的子节点。它会为第一个与它关联的路由节点分配比自己大1的地址，之后与之关联的路由节点的地址之间都相隔偏移量Cskip(d)。假设父节点的地址为Aparent，则第n个与之关联的子节点地址为An

由于簇头的地址默认采用0x0000，因此根据式(2)可得出第一代孩子节点的地址，即路径深度d=1的节点地址为

可得出任意节点的地址与路径深度d之间的关系为

因为RREQ报文中携带源地址和目的地址，因此可通过式(4)计算出源地址及目标地址的路径深度d，并与自身路径深度比较，路由节点只有在自身路径深度在源节点路径深度和目标节点路径深度范围之内时，才进行RREQ报文的转发。在图2中，节点N7的路径深度d=3，并不在源节点N4和目的节点N0的路径深度范围[0～2]之内，因此节点N7不会参与到节点N4向节点N0的路由建立过程，减少了相应节点(N6、N7和N8等)的转发RREQ报文的通信开销。

2.3 AODV 路由维护

路由维护是网络层的一个重要的功能，在节点经过路由查找找到一条合适的路径之后，会把这条路径保存在路由表中。由于节点自身资源的限制，其存储器的空间有限，如果在一个区域内布置大量的传感器节点，那么其路由表所占的空间将会是一个很大的开销。由于这个原因，节点的路由表不会一直存在，在建立路由表时，会启动一个定时器。经过一定的时间，路由表中的某些表项如果不用，就会被删除，以防止路由表不断增大，从而节省资源。

如果源节点是移动的，或者路由表中的相应表项被删除，如果有数据要发送至目的节点时，它就要向目的节点重新发起一次路由发现过程，建立新的路由。

2.4 基于RSSI的最短路径选择

节点硬件由LPC2138作为主控制器，由TI公司的CC2420组成的射频模块作为通信模块。CC2420内部集成了可用于实现节点测距功能的数字RSSI模块，通信距离越远，RSSI值相对越低。CC2420支持八个不同的发送功率等级，通过大量实验，选择第五功率作为节点通讯的发射功率。第五功率下RSSI随距离变化的趋势，如图3所示。RSSI单位为dbm，距离单位为m。可以看出，采用第五功率时，在通信距离为0～15 m范围内RSSI逐渐减小，波动较少。

图3 RSSI随距离变化趋势图

由于节点可以检测RSSI值，如图4所示，节点N5到N0的路由广播时，路由节点(如节点N3、N4)收到RREQ报文后并不是立即转发，而是延迟一个适当的与节点测得的RSSI值成反比的时间转发，也就是节点间距离越远，延迟时间越长。这样RREQ会选择一个较短的路径优先达到目的节点，目的节点收到最先到达的RREQ后回复RREP，从而建立路由，而路由回复则不进行时间延迟。其他的路径较长的RREQ，由于到达目的节点时，目的节点已经建立了路由，因此不会进行路由回复。图4中，选择的最短路径是N5-N3-N1-N0。基于RSSI的时间延迟，即可以通过不同的延迟时间避免节点间的RREQ的冲突，也可以选择一个距离较短的路径以减少通信消耗。

图4 基于RSSI的RREQ报文转发

3 协议实验及结果、性能分析

协议使用自主开发的节点平台[9]进行了实验，节点及节点分布，如图5所示。簇头节点通过串口与上位机连接，通过上位机的界面程序，监测无线传感器网络状态。

图5 节点及节点分布

基于路径深度的AODV路由协议优化实验模拟的结构，如图2所示。使节点N4向节点N0发送数据，计算机通过串口与节点N7连接，监测节点N7的状态。通过节点N7的串口输出，可了解到节点N7在接收到N4发送的RREQ报文之后，通过源节点与目的节点路径深度计算，没有继续向周围转发RREQ报文，收到的消息量也明显减少。而在相同结构下的原AODV路由协议中，节点N7则会把RREQ报文转发出去。因为其他节点(节点N6、N8等)也会进行相同的操作，因此节点N7会收到很多相同的RREQ。在节点规模达到20个以上时，也会出现报文冲突现象。

基于RSSI的最短路径选择实验，如图6所示，圆点之间的虚线表示节点间的逻辑关系。节点间的距离在4～5 m之间。从图6中可看出基于RSSI的路径选择会优先选择最短路径，节点5的组网数据通过路径5-4-2-0发送到簇头节点，而原AODV路由协议的路径选择，随机性比较大。

图6 上位机演示图

4 结语

在AODV路由协议基础上，考虑了节点的路径深度及路由选择的距离因素。在中间节点收到RREQ报文时，使不在源节点和目的节点之间的节点停止路由转发，减少了参与路由发现过程的节点数，以此减少了WSNs的能耗。在转发RREQ报文时延迟了一个与测得的RSSI成反比的时间，减少了RREQ报文的冲突，并最大可能地选择距离短的路径作为传输路径，减少了无线通信消耗。对于实时性要求不高的网络，有很好的应用价值。实验表明，经过改进的路由协议具有更优的性能，明显减少了通信量。

[1]AKYILDIZ IF，SU WEI-LIAN，SANKARASUBRAMANIAM Y，et al.A Survey on Sensor Networks[J].IEEE Communications Magazine，2002，40(8):102-114.

[2]任雄伟.无线移动自组网中路由度量和路由策略的研究[D].武汉:华中科技大学，2005.

[3]YOUNIS O，FAHMY S.A Hybrid，Energy-Efficient，Distributed Clustering Approach for Ad-Hoc Sensor Networks[J].IEEE Transaction on Mobile Computing，2004，3(4):660-669.

[4]李庆，刘聪，江汉红，等.Ad Hoc网络中AODV路由协议的优化[J].计算机工程.2008，34(13):107-109.

[5]吴丽杰，钱雪忠，窦维江.基于AODV的能量有效路由协议[J].微电子学与计算机.2006，23(10):219-221.

[6]PERK NS C E，ROYER E，DAS S.RFC 3561，Ad Hoc On-Demand Distance Vector(AODV)Routing[S].2003.

[7]郑少仁，王海涛，赵志峰，等.Ad Hoc网络技术[M].北京:人民邮电出版社，2005.

[8]HEINZELMAN W R，CHANDRAKASAN A，Balakrishnan H.An Application-Specific Protocol Architecture for Wire-less Microsensor Networks[J].IEEE Trans.on Wireless Communications，2002，1(4):660-670.

[9]高英明，金仁成，王宏斌，等.基于ARM7的无线传感器网络节点能量管理初探[J].微纳电子技术，2007(8):450-452.