基于快速检测和恢复的无线传感器网络路由协议研究

高秀娥，万兵，刘长征

（1大连大学信息工程学院计算机系，大连116622；2大连大学网络重点实验室，大连116622；3石河子大学信息科学与技术学院，石河子832003）

无线传感器网络中的每个传感器节点具备信号采集、数据处理、相互通信的功能，具有很大的灵活性，因此，该网络在军事、环境监测等方面有很大的潜在应用价值［1－2］。由于在无人监测或环境恶劣的条件下，加上节点有限的能量的消耗，无线传感器网络很容易出现故障［1－5］。因此，容错问题是设计无线传感器网络路由协议时必须考虑的重要因素。

随着对无线传感器网络研究的深入，很多相关的路由协议［3－6］被提出，其中定向扩散（directed diffusion，DD）路由协议是最早提出的无线传感器网络路由协议之一。但是，由于DD路由协议不能检测出故障的具体节点，也不能将出现故障的节点及其路径从无线传感器网络中完全移除，使得还有信息继续传向这些节点，导致大量节点能量浪费和信息数据丢失。

目前，在无线传感器网络路由协议中，有关对故障路径进行快速检测和恢复的协议方面的报道很少。基于此，本文提出了主路径节点故障快速检测和恢复（FDFR）的无线传感器网络路由协议，该协议针对节点的具体故障原因进行快速检测并恢复主路径，能将故障节点及其相关路径从网络中完全移除，旨在避免能量的浪费和数据信息的丢失。

1 DD路由协议的容错

1．1 DD路由协议容错的优点

DD路由协议［2］中的最大特点就是利用加强机制。主路径上的中间节点可以在此主路径出现故障后利用加强信号进行局部修复，出现路径故障的原因有节点能量耗尽、安全攻击、环境因素（比如出现障碍物）等。若主路径上某节点发现来自上游节点的信息数据速率突然减小，或者发现周围节点的信息传输速率突然增加，即此路径发生故障，然后此节点便会发送否定加强信号直到source节点。如图1a所示，当sink节点发现此主路径发生故障时，便会沿着主路径发送否定加强信息，主路径上的每个节点接收到否定加强信息后，便会将原来建立的加强的梯度消除。

图1 DD路由协议中移除故障节点Fig．1Removing fault node in DD protocol

1．2 DD路由协议的缺陷

然而如图1b所示，当否定加强信息传到故障节点时，由于该节点已经发生故障，不能将此否定加强信息继续传播，因此，由于没有把从source到故障节点的路径删除，source节点还会继续向此路径发送数据信息，导致大量信息数据的丢失和能量的浪费。

此外，由于DD路由协议中，当出现路径故障时，不能立即检测到故障节点并重新选取新的主路径，而是必须等到下一次探索信息泛洪时，才能重新找到主路径，即：

式（1）中，Tr表示恢复故障所需时间，Te表示source节点下一次发送探索信息的时间，Tf表示出现故障时的时间。从式（1）中可以看出，若故障出现在刚发送了探索信息之后，则整个网络必须等待很长时间才能找到新的主路径，而在这段时间内，将会有大量的信息数据丢失和节点能量的浪费。

因此，在无线传感器网络中，出现节点故障的主要原因有：节点能量耗尽、安全攻击、环境因素等。由于主路径上的节点传输信息数据量大、频繁、能量消耗迅速，能量耗尽是路径故障的一个很重要因素。DD路由协议的缺点是不能快速的检测节点错误，为了能够减少故障恢复时间，降低数据传输的丢失率，需要对DD路由协议进行改进。

2 FDFR路由协议的提出

针对于DD路由协议容错的不足，本文提出的FDFR路由协议能够及时确定该节点，并快速纠错和重新选取新路径。其可利用能量阈值实现节点故障的自身检测；而对于安全攻击，环境因素等造成的故障，由于节点已经失去了和其它节点通信的功能，则采用后节点检测方法。

2．1 自身检测法

在设定能量阈值的自身检测方法中，首先将主路径上的传感器节点设定一个能量阈值En，En的大小为该节点发送信息回到source节点所需要的能量与该节点转发1次信息数据包所需能量之和。节点在每次转发数据前，都要将所剩能量Eava和En进行比较。若Eava＜En，则该节点停止转发信息数据，并由主路径发送请求探索信息（ExploreRequest）直到source节点（图2a）。当source节点接收到请求探索信息后，停止向该路径发送信息数据，并立即发送探索信息（exploratory data）以重新寻找主路径；另一方面，为了将故障路径和节点完全从网络中删除，首先，发送请求探索信息时，该故障节点把与下游节点相连的梯度删除，当请求探索信息到达某一节点时，便会检查该节点是否有与故障节点相连的梯度，若有，便将该梯度删除（图2b）。

图2 设定能量值的节点检测Fig．2Detecting node according to set energy

2．2 后节点检测法

当某个节点出现故障时，便不能转发信息数据。后节点检测法的主要思想是让主路径上的每一个节点为其前一个节点设置一个时间限制Tim，如果定时器时间到了Tim而此节点仍未接收到来自上游节点的信息数据，此节点便会判断其上游节点发生故障，紧接着，该节点便会泛洪发送ExploreRequest直到source节点，当source节点接收到请求探索信息后便会立即全网泛洪发送exploratory data寻找新的主路径。另外，当节点接收到请求探索信息时，也会将与故障节点相连的梯度删除。

传感器节点发送信息数据是通过无线电通信技术。由于无线电通信过程容易发生错误导致信息数据包丢失，后节点检测法必须把节点被破坏（安全攻击，环境因素等）导致的发送失败和无线电故障导致的间接性发送失败区分开来。事实上，由无线电故障导致的间歇性发送失败是应该被容忍的。因此，决定时间限制Tim大小的因素主要有：无线电通信故障发生的时间长度、探索信息的发送时间间隔、加强信息发送的时间间隔。由于要容忍由无线电通讯故障导致的信息数据包丢失，时间限制Tim必须大于无线电通讯故障时间长度（Trad）。

由于无线电通信传输很容易出现故障，一个两种状态（故障和正常）的马尔可夫模型（图3）被Gilbert提出，即在每一次的发送信息数据间隔期间，无线电通讯信道都可能变成另一种状态。符合几何分布规律的变量BL表示逗留在故障状态的时间，因此，处在故障状态的平均时间E（BL）即为：

式（2）中，p表示连续2个信息数据包丢失的概率。

为了保证能够容忍由无线电故障导致的发送信息数据失败，计算无线电通讯故障时间长度Trad如下：

在计算Trad时，在平均故障时间的基础上加上了标准差，这样能保证后节点检测法能够容忍合理时间长度的无线电故障，也能够更好地将无线电故障同其它节点故障原因区分开来。

图3 Gilbert－Elliott模型Fig．3Gilbert－Elliott model

综合考虑无线电故障时间Trad，加强信息时间间隔Ir和探索信息时间间隔Ie，设定的时间限制Tim应为：

首先，利用式（4）计算出该无线传感器网络在当前环境下的Tim值。

当主路径上的每个传感器节点接收到第1个加强信息开始，便为其上游节点计时。当出现以下情况时，便重新开始计时：①节点接收到上游节点发送的信息数据包；②探索信息全网泛洪发生（表明正在寻找新的主路径）。

否则，如果Tim到达最大值，则说明该节点的上游节点发生故障。紧接着，该节点便会生成请求探索信息（包括故障节点ID信息等）并发送给所有周围邻居节点，以泛洪方式直到source节点。在泛洪的过程中，每到一个中间节点，便会检测该节点的所有相连路径是否含有故障节点，若有，则将此路径删除。当请求探索信息到达source节点后，source节点便会立即发送探索信息，当探索信息到达sink节点后，便选出了新的主路径（图4）。

图4 FDFR路由协议故障节点的删除和主路径的建立Fig．4Removement of the fault node and establishment of the main path in FDFR

在FDFR路由协议中，2种检测法同时作用在主路径上的节点中。当某节点由于能量消耗导致即将故障时，设定能量阈值的自身检测法便能检测出来，并立即执行恢复的步骤。而当安全攻击或环境因素等导致节点故障时，自身检测法便失效。此时，当过了Tim时间后，后节点检测法便能检测出错误并执行恢复过程。可见，自身检测法比后节点检测法略快，但是后节点检测法能够检测的故障更多。

3 仿真实验结果与分析

仿真实验条件：传感器节点均匀地分布在一个正方形的区域，故障节点分为两类，一类可以通信，但不能转发数据，使用自身检测法；另一类既不能通信，也不能转发数据，使用后节点检测法。采用信息数据包的丢失率和故障恢复时间来评价仿真的效果。

（1）信息数据包丢失率（Lr）。

式（5）中，Lp表示丢失的信息数据包数量，Rp表示Sink节点接收到信息数据包数量。

图5显示了FDFR路由协议和DD路由协议在不同节点数量时信息数据包丢失率的对比。可知，相同节点数量FDFR路由协议的信息丢失率比DD路由协议的丢失率低。这是因为当出现节点故障时，FDFR路由协议能够快速恢复，选择新的主路径，并且将故障路径从网络中删除，从而大大减少了信息数据包的丢失。

图5 信息数据包的丢失率对比Fig．5Comparison of information packet loss

图6 故障恢复时间对比Fig．6Comparison of fault recovery time

（2）故障恢复时间。

故障恢复时间即从故障发生到发现故障并重新选取主路径的时间。图6显示了50个故障节点的故障恢复时间。其中，Tim＝30s，Ie＝100s。从图中数据可算出，DD路由协议的平均恢复时间为57 s，而FDFR路由协议平均只需要22s。

4 结语

针对DD路由协议不能快速检测节点错误的缺点，本文提出了能够快速检测节点故障并恢复主路径的FDFR路由协议，介绍了根据设定能量阈值的自身检测法和设定时间限制的后节点检测法，根据导致故障的原因不同采取灵活的检错办法。仿真结果表明，FDFR路由协议减少了故障恢复的时间和降低了信息数据包的丢失率。在今后的研究中，将考虑能量、内存等因素对网络容错性能的影响，使FDFR路由协议适应复杂多变的无线传感器网络。

［1］陈彦明，王秋光，徐勇军．无线传感器网络容错技术综述［J］．计算机科学，2008，35（11）：87－90，175．

［2］曹冬磊，曹建农，金蓓弘．一种无线传感器网络中事件区域监测的容错算法［J］．计算机学报，2007，30（10）：1770－1776．

［3］L Carvalho，J Angeja，A Navarro．A new packet loss model of the ieee 802．11g wireless network for multimedia communications［J］．In Consumer Electronics，IEEE Transactions，2005，51：809－814．

［4］Zabin F S．Misra S，Woungang I，et al．REEP：data－centric，energy－efficient and reliable routing protocol for wireless sensor networks［J］．Communications，IET，2008，2（8）：995－1008．

［5］Chalermek Intanagonwiwat，Ramesh Govindan，Deborah Estrin．Directed diffusion for Wireless Sensor Networking［J］．IEEE／ACM Transactions on Networking，2003，11（1）：2－16．

［6］Boukerche A，Chatzigiannakisb I，Nikoletseas S．A new energy efficient and fault－tolerant protocol for data propagation in smart dust networks using varying transmission range［J］．Science Direct，2006，29（20）：477－489．