一种基于路径信息的WSN路由协议*

韩江洪 ，江 月 ，马学森 ，官骏鸣 ,3

（1.合肥工业大学计算机与信息学院 合肥 230009；2.安全关键工业测控技术教育部工程研究中心 合肥 230009；3.黄山学院信息工程学院 黄山 245021）

1 引言

WSN（wireless sensor network，无线传感器网络）是一种无基础设施的网络，它由一组具备无线收发能力的传感器节点以自组织方式构成，其目的是协作感知和处理网络覆盖地理区域中感知对象的信息，并将这些信息传送给需要的用户。MANET（mobile Ad Hoc network，移动 Ad Hoc 网络）是由一组无线移动节点组成的一种不需要依靠现有固定通信网络基础设施的、能够迅速展开使用的、具有自组织功能的网络。就网络传输技术而言，WSN和MANET没有太大的本质区别，在MANET终端上配置传感器处理单元就是WSN，因此WSN和MANET被统称为自组织网络。但从路由的角度看，WSN并不完全等同于MANET，它有自己的特点：如节点不移动或很少移动，节点的能量有限、通信能力较弱等[1,2]。WSN的固有特性使得MANET的路由协议并不完全适用于WSN。

AODV（Ad Hoc on-demanding distance vector，Ad Hoc 按需距离矢量）是MANET中应用最广泛的按需路由协议。它定义了路由请求（RREQ）、路由应答（RREP）和路由错误（RERR）3种控制消息。当一个源节点需要一条路由到达某个目的节点，但是没有现成可用路由或者以前到达该目的节点的有效路由为无效的时候，该源节点就广播一个RREQ分组。如果在限定的等待时间内没有收到相应的RREP分组，那么源节点重新广播RREQ分组，直到找到一条新路由或者重复寻找的次数达到限定的最大值。节点接收到RREQ分组后，首先确定自己是否已经接收过这样的RREQ分组，如果是，就丢弃该RREQ分组；否则，在路由表中创建一个到达源节点的反向路由条目，并继续广播该RREQ分组。如果该节点本身就是所请求的目的节点，或者该节点是一个中间节点且有一条“足够新”的路由到达所请求的目的节点，那么它将产生一个RREP分组，并以单播方式将该RREP分组发送给源节点。源节点在收到RREP分组后开始向目的节点发送数据[2～5]。

AODV协议在多种不同的拓扑和环境下经历了严格的测试，具有较高的正确性和强壮性。与其他协议相比，AODV协议提供对动态链路状况的快速自适应，处理开销和存储开销较低，因此在WSN的研究中常常借用AODV协议[1,6]。但是，AODV协议在路由查找过程中采用洪泛方式向全网广播RREQ分组，若在节点密度大、能量有限的WSN中直接使用，则会造成网络开销过大、平均端到端时延过长等问题。针对WSN的特点，本文提出了一种基于路径信息的WSN路由协议——IAODV（improved AODV），该协议可以有效地解决上述问题。

2 IAODV协议的设计

IAODV协议的设计目标是在保留AODV协议的强壮性、高效性和良好的自组织性等优点的前提下，对其基于洪泛的路由查找机制进行改进，使其成为适合WSN的低开销、低时延的路由协议。

WSN中的节点在部署完成之后大部分不会再移动，虽然部分节点因调度机制或失效等原因而出现网络拓扑改变的情况，但这些变化具有明显的周期性和间歇性，所以WSN的拓扑可以认为是准静态的。此外，WSN的工作模式通常是网络中的所有节点将数据汇聚到Sink节点，即多对一的通信，节点之间几乎不会发生消息交换[1]。

针对WSN的特性，研究人员提出了很多AODV协议改进方案，LAR（location-aided routing，位置辅助路由）协议就是典型的代表。LAR协议使用地理位置信息为AODV限定了一个路由请求区域，称为寻找域，只有位于寻找域内的节点才可以转发RREQ分组，从而有效地减少了路由寻找开销。在LAR中，当源节点向目的节点发起路由请求时，先将一个以源节点和目的节点之间的连线为对角线的矩形区域定义为寻找域 （另一种常用的算法是将距离目的节点较近的节点所在的区域定义为寻找域），如果在限定的生存时间内没有找到新的路由，源节点将进一步扩大寻找域，重新发起路由搜索[1,7]。在WSN中，由于节点不移动或很少移动，使用GPS能够很容易地确定节点自身的位置，并且目的节点大多数情况下是惟一固定的，这就免除了对目的节点位置信息的维护，因此LAR协议可以较好地运用在WSN中。但是，由于WSN的节点分布情况根据不同的应用复杂多样，源节点到目的节点的路径走向及其范围难以控制，用LAR协议源节点往往需要多次增大寻找域，重新进行查找尝试，从而大大增加了时延和网络开销。因此，如何较快地确定适合具体应用的寻找域，是提高协议性能的关键。IAODV协议的设计就是着眼于这一关键问题。

基于WSN准静态的拓扑和多对一的工作模式，不但可以认为WSN的目的节点是惟一、固定的，而且源节点到这一固定目的节点的传输路径也可以视作准静态的，因此IAODV协议考虑利用路径信息对AODV协议基于洪泛的路由查找机制进行改进。先用AODV协议寻找路由进行数据传输，当原先的路由走不通或路由期满失效时，基于WSN的准静态性，新的路由和原来的路由应该相差不大，可以原来的路由为基准进行新的路由查找。具体地说，就是将原传输路径近似看作一条基准传输路径，并将其附近的一个特定范围定义为寻找域，将路由查找限制在该寻找域内，即在路由查找过程中，只有位于该寻找域内的节点才可以广播RREQ分组。例如，将查找控制在基准传输路径的最大传输范围内，如图1所示，S为源节点，D为目的节点，实心节点代表基准传输路径中包含的节点，实线代表基准传输路径，虚线圆表示相应圆心节点的最大传输范围，相邻圆的重叠区域即为寻找域。为了摆脱对GPS的依赖，IAODV协议采用跳数作为寻找域大小的计量单位，即将距离基准传输路径K跳的范围定义为寻找域，其中K值在源节点第一次发起路由查找时设置为某一固定的经验值。当路由查找超时，需要重新发起路由查找时，源节点可以通过增大K值很方便地扩大寻找域，而不需要任何复杂的算法。

图1 以基准传输路径的最大传输范围为寻找域

将保存在节点中的原路由信息定义为基准路径信息Pstd，为了在路由查找过程中利用基准路径信息Pstd，可以借鉴 DSR（dynamic source routing protocol，源动态路由协议），采用在RREQ分组中携带完整的基准传输路径信息的方式。这样做虽然能够方便地利用路径信息，但是增加了RREQ分组长度，大大增加了网络开销[8,9]。为了节省网络开销，IAODV协议借鉴有线网络中虚电路的分组交换实现方式，用特定的目的节点和虚电路号来标识相应的基准路径信息Pstd。当所请求的目的节点接收到RREQ分组时，该目的节点通过将已有的最大虚电路号加1的方式生成一个新的虚电路号，并将其标识在RREP分组中，再按照单播的方式将该RREP分组发送给源节点。如果产生RREP分组的节点是中间节点，则将该中间节点到达所请求的目的节点的虚电路号直接标识在RREP分组中。当一个中间节点收到该RREP分组时，先读出RREP分组中的虚电路号，并将其同对应的目的节点记录下来，作为一条基准路径信息Pstd保存在节点中。当源节点再次发起到目的节点的路由查找时，只要在RREQ分组中携带到达该目的节点的虚电路号，就可以方便地在路由查找过程中利用路径信息。由于虚电路号是一个unsigned型的整数，仅一个字节的虚电路号就可以标识255条不同的路径 （预留0号标识尚未建立基准路径的情况），已经基本可以满足一般规模的WSN的应用要求，因此在具体实现时可以通过重新定义原RREQ和RREP分组中的保留字段来标识相应的虚电路号，从而既达到了携带所需的路径信息的目的，又不会增加控制分组长度。

相比于LAR利用节点的位置信息确定寻找域的方式，IAODV协议利用路径信息确定寻找域的方式依据WSN的具体应用中节点和路径分布的情况，能够更快地获得符合具体应用的合适的寻找域，并且摆脱了对GPS的依赖，免除了相关的额外开销，具体实现算法也更简单，从而更加有效地限制AODV路由查找的范围，加快路由算法的收敛速度，减少网络的开销，实现低开销、低时延的设计目标。

3 IAODV协议的实现

根据上述设计方案，IAODV协议在AODV协议的基础上进行了以下改进。

（1）在每个节点中存储一张路径列表，记录其到各个目的节点的虚电路号即基准路径信息Pstd以及定义寻找域的K值

显然，这里的路径列表长度等于WSN中Sink节点的个数。由于WSN采用多对一的工作模式，通常即使是一个覆盖范围很广、节点数量众多的WSN，其中Sink节点的数量都是相当有限的，因此路径列表所占存储空间很少，且搜索列表所需时间在计算传输时延中基本可以忽略不计。

（2）对RREQ分组和RREP分组进行扩展，并在路由查找过程中增加与之相关的处理

对RREQ分组进行扩展，增加Standard Path、Threshold和Counter字段。Standard Path字段用于记录到达所请求的目的节点的虚电路号；Threshold字段用于记录定义寻找域的K值；Counter字段用于记录新路由距离基准传输路径的跳数。当节点需要发起路由查找时，如果本地路径列表中有到所请求的目的节点的表项，则将该表项中的虚电路号和K值分别填入RREQ分组中的Standard Path字段和Threshold字段，Counter字段置为0，并且源节点每进行一次路由寻找尝试，Threshold加1；否则，将Standard Path字段置为0，表示尚未建立起相应的基准传输路径，此时Threshold字段和Counter字段的值无效。当节点接收到RREQ分组时，如果其中的Standard Path字段为0，则不做任何变动，否则根据其中的目的节点地址和Standard Path字段搜索本地路径列表，通过查找包含相同基准路径信息Pstd的表项来判断本节点是否在基准传输路径上。如果在，则将RREQ分组中的Counter字段归零，否则将Counter字段值加1。如果Counter字段数值不大于Threshold字段数值，则继续广播该RREQ分组，否则将该RREQ分组丢弃。

对RREP分组进行扩展，增加一个Standard Path字段，用于记录建立的虚电路号。当所请求的目的节点或具有一条“足够新”的路由到达所请求的目的节点的一个中间节点接收到RREQ分组，如果该RREQ分组中的Standard Path字段不为0，则将其填入RREP分组中的Standard Path字段；否则考虑以下两种情况：如果该节点是所请求的目的节点，则将现有的到该目的节点的最大虚电路号加1作为新路径的虚电路号，然后填入RREP分组的Standard Path字段；如果该节点是一个有一条“足够新”的路由到达所请求的目的节点的中间节点，则将其路径列表中到达所请求的目的节点的虚电路号填入RREP分组的Standard Path字段。

4 仿真及分析

4.1 仿真场景设置

通过在NS2[10]仿真软件中对由30个源节点和3个Sink节点构成的WSN进行多次模拟实验来比较AODV和IAODV两种协议的性能。为了对比在不同业务量条件下两种协议的性能，分别对由不同的源节点数据采集上传周期构成的业务模型进行了测试。业务模型的主要参数如下：业务类型为CBR；数据采集上传周期分别为 0.5 s、1 s、2 s、3 s、4 s、5 s、6 s；仿真时间为 100 s；网络范围为 90 m×50 m。所有仿真数据均为3次不同种子条件所得到的平均值。

4.2 性能评价参数

通过分组投递率、平均端到端时延和标准路由开销3个参数来比较IAODV和AODV协议的性能。分组投递率定义为交付到目的节点的数据分组数量与源节点发送的数据分组数量之比；平均端到端时延定义为一个数据分组成功到达目的节点所需的时间平均值；标准路由开销定义为每接收到一个数据分组需要传递的路由分组的数目[11]。

4.3 仿真结果及分析

（1）分组投递率

图2显示了IAODV协议和AODV协议分别在源节点数据采集上传周期为 0.5 s、1 s、2 s、3 s、4 s、5 s和 6 s情况下的分组投递率，可以看出IAODV协议能够获得比AODV协议更高的分组投递率，并且随着源节点数据采集上传周期的减小，IAODV协议的分组投递率下降幅度小于AODV协议。这是因为随着源节点数据采集上传周期的减小，网络负载渐渐加大，网络拥塞逐步加剧。IAODV协议限制了RREQ分组广播范围，有效节省了带宽，缓解了网络拥塞情况，因此IAODV协议可以在网络负载较大的情况下取得较高的分组投递率。

图2 IAODV和AODV协议在不同数据采集上传周期下的分组投递率

（2）平均端到端时延

图3显示了IAODV协议和AODV协议在不同情况下的数据分组平均端到端时延，可以看出IAODV协议的分组平均时延比AODV协议小很多，并且随着网络负载的减小，IAODV协议的分组平均时延下降幅度远远大于AODV协议。因为IAODV协议的路由查找收敛速度大于AODV协议，因此分组平均时延会大大降低。另外，IAODV协议在数据采集上传周期为3 s时，平均时延达到最小，然后随着周期的继续增大，平均时延开始增大。这是由于数据采集上传周期过大，当源节点再次要求向Sink节点上传数据时，原路由已经期满失效，必须查找一条新的路由。

图3 IAODV和AODV协议在不同数据采集上传周期下的平均端到端时延

（3）标准路由开销

图4显示了IAODV协议和AODV协议在不同情况下的标准路由开销，可以看出，不论网络负载大小，IAODV协议的标准路由开销都明显小于AODV协议。IAODV协议通过限制RREQ分组的广播范围大大减少了路由分组数量，减小了路由开销。

图4 IAODV和AODV协议在不同数据采集上传周期下的标准路由开销

5 结束语

AODV协议在路由发现时选择短路径，IAODV协议将AODV寻找到的传输路径作为基准传输路径的做法可以满足对实时性要求比较高的应用的需求，但是对于具有较高的节能要求的应用就需要选择一条平均每跳距离较短的路径作为基准传输路径，以尽可能降低节点的能耗，因此下一步的工作重点是研究如何找到一条能够同时满足实时性和节能性要求的路径作为IAODV协议的基准传输路径。

1 李晓维.无线传感器网络技术.北京：北京理工大学出版社，2007

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

3 王斌.无线传感器网络AODV路由协议的实现.计算机与现代化，2009（1）:86～89

4 IETF RFC 3561.Ad hoc on-demand distance vector(AODV)routing,2003

5 Chen Canfeng,Ma Jian.Simulation study of AODV performance over IEEE 802.15.4 MAC in WSN with mobile sinks.In:21st International Conference on Advanced Information Networking and Applications Workshops,2007（2）:159～164

6 郑凯，王能，刘爱芳.一个基于AODV的渐进式分簇路由策略.通信学报，2006，27（1）:132～139

7 Ko Y B,Vaidya N H.Location-aided routing (LAR)in mobile ad hoc networks.Wireless Networks,2000,6（4）:307～321

8 喻勇，刘凯歌，胡军.可自扩展的DSR路由协议的性能分析与仿真.计算机工程与设计，2007，28（19）:4652～4654

9 Johnson D B,Maltz D A,Hu Yinchun.The dynamic source routing protocol for mobile Ad Hoc networks,http://www.ietf.org/internet-drafts/draft-ieft-manet-dsr-10.txt

10 徐雷鸣，庞博，赵耀.NS与网络模拟.北京：人民邮电出版社,2003

11 官骏鸣，陆阳，盛锋等.基于节点接入能力的Ad Hoc网络按需路由协议.通信学报,2007,28（10）:32～37