刘 韬，李天瑞，谭 颖

(1.西南交通大学 信息科学与技术学院，四川 成都610031;2.西南民族大学 计算机科学与技术学院，四川 成都610041)

0 引 言

根据数据汇报方式，无线传感器网络可以分为事件驱动型和周期汇报型两类网络［1］。在事件驱动型网络中，节点很少产生数据，仅在待监测的事件发生时才产生事件报告。而在周期汇报型网络中，所有节点周期性地向汇聚节点报告采集到的信息。

两类网络对性能的需求存在较大的差异:周期汇报型网络由于需要传输的数据量大，要求尽可能降低节点的能耗，对时延性能的要求相对不高;事件驱动型网络中节点的报告需要及时地被传输到汇聚节点，否则，可能会产生灾难性的后果，所以，这种网络对时延性能要求较高，而该型网络由于数据量少，对节约能耗的要求不高。现有的绝大部分针对路由的研究都着眼于如何提高网络的能量利用效率，降低和平衡节点的能耗。显然，此类研究并没有考虑数据在路由过程中的时延问题，其成果并不适用于事件驱动型传感器网络。

文献［2］则主要关注事件驱动型网络，提出了一种时延受限且能量高效的跨层路由协议，该协议虽然将端到端的时延控制在一定的范围内，但并没有优化时延。文献［3］提出了一种能量多路径路由机制，同时优化能耗与时延性能，但此机制开销大，算法复杂，维护困难。PRTR协议［4］则基于节点梯度与缓冲队列占空比建成的复合势场来保证数据具有较小的网络时延，但该协议会过度使用最短路径上的节点，从而降低了网络寿命。文献［5］在文献［4］的基础上提出了一种保障时延、能量高效的路由(DGEER)协议，该协议将数据分为时延敏感数据和非时延敏感数据，分别使用不同的路径发送到汇聚节点。该协议缓解了最短路径的过度使用问题，但是它要求事先确定每个节点到达汇聚节点的最短路径，这显然增加了网络开销。文献［6］使用RTS/CTS(请求发送/允许发送)消息机制建立节点路由，减少了节点计算路由的开销，但该协议并没有对时延性能进行优化。

针对现有研究的不足，本文提出了一种专用于事件驱动型无线传感器网络的最小时延路由(minimun delay routing，MDR)协议。MDR 协议利用RTS/CTS 消息机制建立路由，并最小化数据包发到汇聚节点的时延。该协议的计算开销小，维护简单。

1 网络模型

整个网络由一个汇聚节点(Sink)和多个传感器节点组成，节点均匀分布于监控区域内，分布密度为ρ;每个节点可以通过GPS 装置或定位算法获得自身的地理位置信息;所有传感器节点平时不发送数据，只有当所监测的事件发生时才向Sink 发送报告;所有节点具有相同的最大无线传输半径r。

2 MDR 协议及其优化

数据包的时延是指从源节点产生数据包，一直到Sink接收该数据包所经过的时间［6］。本文的研究对象为事件驱动型传感器网络，优化时延性能是本协议所要解决的问题。由于节点极少发送数据，本文忽略不同路由的能耗差异对网络性能的影响，也不考虑信号冲突与干扰。

2.1 MDR 协议概述

MDR 协议中，若网络中任一节点A 有感应数据包要发送，它先广播一个RTS 消息。本文把既位于节点A 的通信范围，又将A 离Sink 距离近的区域称之为节点A 的下一跳可达区域，如图1 的阴影区域所示。只有位于节点A 的下一跳可达区域的节点，接收到来自节点A 的RTS 消息才准备回复CTS。

图1 源节点下一跳可达区域与目的节点竞争机制图Fig 1 Reachable area of source node next hop and competition mechanism of destination

为了使节点每跳路由能够前进尽可能远的距离，把节点的下一跳可达区域按照到Sink 的距离划分为k(k≥2)个长度为d 的子区域，即Ui，i=1，...，k，如图1 所示，并给每个子区域分配一个后退窗口，窗口时间长度为T。位于子区域Ui的节点必须先等待k-i 个窗口时间，再在［0，T］时间段内的任一时间发送CTS 消息，即只能选择［(k-i)T，(k-i)T+T］时间段内的时间发送CTS 消息。该过程将节点A 的邻居节点按地理位置划分为回复CTS 消息的多个优先级组，即先由最外层子区域的节点在相应的时间段内发送CTS 消息，其余子区域的节点等待;若最外层子区域没有节点发送CTS 消息，再由次外层子区域的节点发送CTS 消息;…，以此类推，直至第1 层。其中，任一节点发送CTS 消息，其余节点侦听到此CTS 消息后取消自己发送CTS，竞争过程结束，而成功发送CTS 消息的节点成为节点A 的下一跳目的节点。

2.2 时延性能优化

为了降低数据包从源节点发往Sink 的时延，需要从两方面优化MDR 协议:一是降低每跳路由的时延，二是减少数据包到达Sink 的路由跳数。

2.2.1 最小窗口时间

根据MDR 协议，缩短窗口时间T 可以显著降低每跳路由的时延。但是，若窗口时间长度过短，会增加因多个节点同时发送CTS 消息而冲突的概率。

位于子区域Ui的节点选择回复CTS 消息的时间为t，显然，t 在［(k-i)T，(k-i)T+T］上服从均匀分布，其概率密度为f(t)=1/T。

假设子区域Ui中的某一节点在时刻t 最先发出CTS消息，子区域Ui中的其它节点至少要经过τ 秒才能侦测到此CTS 消息，并取消自己发送CTS 消息。显然，子区域Ui中的其它节点原本发送CTS 消息的时间要安排在(t+τ，(k-i)T+T］时间段内才可以避免冲突。于是，子区域Ui中无冲突发生的概率p 为

其中，ni为子区域Ui中的节点数量，可以通过pSi计算，Si为子区域Ui的面积，其计算方法在下一小节阐述。因为子区域Ui中有ni个节点，那么该子区域不冲突的总概率P 为nip，结合公式(1)和f(t)=1/T，可得

假设不冲突概率的门限值为l，即要求满足P≥l，根据公式(2)可得

根据公式(3)，可以获得满足低冲突概率所需的最小后退窗口时间长度。如果子区域Ui中的节点数量较多，τ 与T 相差较大趋近于0，进而根据公式(3)得到

由于节点的下一跳可达区域的每个子区域所包含的节点数量不同，所以，根据式(3)或式(4)得出的每个子区域所需的最小T 的值不同。为简化，把其中最大的T 值设置为节点的后退窗口时间长度。

2.2.2 计算子区域Ui的面积

如图2 所示，D 为节点A 与Sink 的距离，阴影区域为以Sink 为圆心，以D-x 与D-x-dx 为半径所构成的两个圆与节点A 的传输范围所围成的图形，dx 是自变量x 的微分，该阴影区域的面积S(x)为

图2 子区域Ui 的面积Fig 2 Size of subarea Ui

通过公式(6)与积分，可以获得Ui的面积

2.2.3 每跳平均传输距离

要降低数据包到达Sink 的时延，还要减少数据包经多跳路由到达Sink 的过程中所经历的跳数，即提高数据包在每跳路由的前进距离。

假设任一节点A 发送RTS 消息，dist 为节点A 的数据包在单跳路由中朝向Sink 的前进距离，若节点A 的子区域Ui中的邻居节点首先发送CTS 消息回复，当宽度d 较小时，可以认为数据包在此跳路由的平均前进距离为(i-0.5)d。

根据文献［7］，因节点均匀分布，所以，节点的部署服从泊松分布，于是，节点在面积为S 的区域内没有节点分布的概率为e-ρS。若节点A 的下一跳可达区域划分为k 个子区域，根据MDR 协议，节点A 的数据包此跳前进距离dist的期望可计算为

2.2.4 数据包在单跳路由上的时延

这里使用delay 表示节点在单跳路由上的平均时延，包括节点发送RTS 消息花费的时间、等待CTS 消息的时间、接收CTS 和发送数据包所花费的时间。另外，如果节点先等待k-i 个窗口时间后，子区域Ui中有节点回复CTS。因回复CTS 消息的时间在［(k-i)T，(k-i)T+T］上服从均匀分布，则平均回复时间可以认为是(k-i)T +0.5T，那么，单跳路由上时延的期望可计算为

其中，tsend为节点发送RTS 消息、接收CTS 消息和发送感应数据包所花费的时间，它可以通过节点的数据发送速率和数据包长度来计算。

2.2.5 数据包发往Sink 的总时延

为了判断子区域的数量k 对总时延的影响，使用算法1来计算任一节点把数据包发往Sink 的平均总时延dtotal。该节点距离Sink 的距离为D。

算法1:计算数据包发往Sink 的总时延

1)dtotal=0;

2)while D ＞r

4) 通过式(3)或式(4)获得窗口时间长度T;

8)end while

9) dtotal=dtotal+最后一跳的时延。

其中，最后一跳的时延指的是最后一跳节点直接和Sink 进行通信的时延，此时节点无需发送RTS 消息，而是直接把数据包发给Sink。

在k 的取值范围内，分别使用算法1 计算k 取不同值时数据包发往Sink 的总时延，从而获得使得总时延最小时的k 值。

2.3 完善MDR 协议

网络初始化时，每个节点将自身的位置信息发给Sink。Sink 根据该位置信息计算出该节点与Sink 的距离D，然后使用算法1 获得使得该节点的数据包发往Sink 的总时延最小时的k 值和窗口时间长度T，并把此k 和T 值发消息通知给该节点。

网络开始运行后，当某节点探测到事件发生时，根据MDR 协议，发送RTS 消息，并捎带相应的k 值、节点的位置信息，以及窗口时间长度T;其它节点收到RTS 消息后，根据相关信息计算自己所对应的分区，然后按MDR 协议响应RTS 消息。

3 实 验

利用OPNET 作为仿真平台对MDR 协议的时延性能进行评估。如无特别指定，实验中的参数设置如下:D=200 m，r=20 m，ρ=0.05，l=0.005，τ=0.001，数据包的长度为80 bits，消息包的长度均为20 bits，节点的数据发送速率为20 kB/s。

图3 反映了网络采用MDR 协议，在参数k 的不同取值下，数据包从源节点发送到Sink 的总时延，从图3 可以看出:当k=6 时，时延最小。分析结果和模拟结果基本保持一致，从而证明了分析的正确性。图4 反映了在不同的参数k 下，数据包从源节点发送到Sink 所经历的路由总跳数。从图4 中可以看出:当k 变大时，数据包到达Sink 所经历的跳数不断减少，这是由于k 变大时，距离源节点远的节点会先回复CTS，这样，数据包在每跳路由前进距离变远，降低了总跳数。图5 反映了不同D 值下网络分别采用MDR 与PRTR［4］，XLP［6］三种协议时数据包发往Sink 的总时延。从图5 可以看出:网络采用MDR 协议时，时延最小。

图3 不同k 值下数据包到达Sink 的时延Fig 3 Time delay of data packets arriving at sink with different k value

图4 不同k 值下数据包到达Sink 的跳数Fig 4 Number of hops of data packets arriving at Sink with different k value

4 结 论

图5 网络时延性能比较Fig 5 Comparison of delay performances of networks

针对事件驱动型传感器网络，提出了一种MDR 协议。该协议利用了RTS/CTS 消息机制建立路由，通过控制节点的下一跳可达区域的子区域的数量和对应的窗口时间长度来优化网络的时延性能。实验结果表明:MDR 协议有效提高了网络的时延性能。

［1］ 王辛果，张信明，陈国良.时延受限且能量高效的无线传感器网络跨层路由［J］.软件学报，2011，22(7):1626-1640.

［2］ 王辛果，张信明，陈国良.时延受限且能量高效的无线传感器网络跨层路由［J］.软件学报，2011，22(7):1626-1640.

［3］ Pothuri K，Sarangan V，Thomas J P.Delay-constrained，energyefficient routing in wireless sensor networks through topology control［C］∥Proceedings of the 2006 IEEE International Conferance，Piscataway，NJ，USA:IEEE，2006:35-41.

［4］ Xu Yingsheng，Ren Fengyuan，He Tao.Building a potential field to provide real-time transmission in wireless sensor networks［C］∥Proceedings of the 13th ACM International Conference on Modeling，Analysis and Simulation of Wireless and Mobile Systems，New York，USA:ACM，2010:403-410.

［5］ 梁庆伟，姚道远，巩思亮.一种保障时延能量高效的无线传感器网络路由协议［J］.西安交通大学学报，2012，46(6):48-52.

［6］ Mehmet C Vuran，Ian F Akyildiz.XLP:A cross-layer protocol for efficient communication in wireless sensor networks［J］.IEEE Trans on Mobile Computing，2010，9(11):1578-1591.

［7］ Wang Y，Wang X D，Xie B，et al.Intrusion detection in homogeneous and heterogeneous wireless sensor networks［J］.IEEE Trans on Mobile Computing，2008，7(6):698-711.