聂晨华，高 西，董荣胜

（桂林电子科技大学 广西可信软件重点实验室，广西 桂林541004）

0 引 言

为 确 保 无 线 传 感 器 网 络 （wireless sensor network，WSN）可靠安全，关键在于资源受限的传感器节点设备的性能以及它们之间的通信可靠性［2］。由于传感器资源有限且通常部署在恶劣的环境中，使得传感器容易发生故障而导致失效。一种提高系统可靠性的方法是采用容错 （fault tolerance，FT）［3］技术。特别是采用具有可修复功能的传感器节点能够避免因发生故障而直接丢弃所带来的不必要浪费，一定程度上有效地延长其寿命，并且可以减少节点的冗余度从而降低网络设施的成本，同时增强WSN 的可靠性，使得WSN 在部分节点失效的情况下继续保持其功能。

关于容错技术的研究成果已经被广泛运用到WSN 中。Alwan等提供一种冗余编码数据片的方式实现容错技术，这种故障容错技术是对原始数据包进行分片编码，再进行多路径传输［4］；文献 ［5－7］关注多路径容错，即在源节点和目的节点之间建立冗余路由来对源节点所在的路由发生故障时进行容错；肖伟等针对资源受限的传感器节点的数据聚集的容错要求，提出了基于事件簇的一种高效的容错数据聚集机制EFSA［8］。目前国内外针对具有自我修复功能WSN 的研究主要集中在协议以及拓扑等方面。袁慎芳等针对WSN 的自我维护问题，提出了一种基于FPAA 的自修复智能无线传感器节点的实现方法［9］；Silva等研究了具有不同修复率的传感器节点对簇型网络的瞬时可用度的影响［10］；苏金树等关注容错分簇算法，提出了一个负载均衡感知的无线传感器网络的分簇算法，能够有效减少网络能耗并提高网络可靠性［11］。由于传感器节点是WSN 的重要组成，节点本身具有可修复性也是提高WSN 安全性和可靠性研究的重要部分。

本文关注硬件水平上具有容错机制的无线传感器网络的可靠性研究。具有可修复功能的节点能使其在部分硬件模块发生故障的情况下，修复相应故障，在一定程度上可以避免因长期布置于野外无人维护而发生故障的传感器节点被直接丢弃带来的不必要浪费。同时具有修复功能的节点能够有效地延长其寿命，从而直接影响了整个网络的寿命。此外，目前节点上的容错技术往往由硬件或信息冗余完成，具有可修复能力的节点可以有效地减少设备上的冗余度，从而降低了网络设施的成本。因此研究可修复节点的可靠性对WSN 鲁棒性和可靠性的提高具有重要的意义。在本文利用动态故障树模型中的事件元素与逻辑门元素建立WSN 可靠性结构，研究容错技术中可修复传感器节点背景下的WSN 可靠性，其中对可修复节点建立容错动态逻辑门模型。该容错节点模型是一种具有可修复属性以及在硬件水平上具有冗余属性的模型。基于马尔科夫随机过程，评估该种容错可修复节点模型下的可靠性。针对簇型WSN应 用 通 信 可 靠 性 （application communication reliability，ACR）［12］问题，将给出的容错可修复传感器节点模型应用在该簇型WSN 可靠性结构上，以便计算WSN 可靠度。基于故障树的WSN 可靠性结构应用不交和 （SDP）的方法在故障树上计算系统可靠度，存在最小割集 （MCS）的不交化处理过程，该过程是一个NP－hard问题。基于香农分解的BDD （binary decision diagram）本身具有不交化的特性，能够有效控制故障树不交化处理过程中的组合爆炸。为此本文将BDD 技术引入到基于故障树求WSN 可靠性的处理中，用递归的方法给出从WSN 可靠性结构转换到BDD 结构的算法，然后遍历BDD 计算WSN 的可靠度，优化可靠度计算过程，降低WSN 可靠度计算的复杂性。

1 容错节点模型及其可靠性

容错被定义为容忍可能发生于节点布置、拓扑控制、目标和事件监测、数据聚合、路由和信息处理上的错误。故障树用图形和数学相结合的方法表示系统发生故障的事件之间的逻辑关系。传统的故障树仅仅通过应用与门（AND），或门 （OR）和异或门 （n－out－of－m）逻辑门来描述系统失效事件之间的关系。Dugan等对传统故障树的功能进行了扩展，定义了动态故障树 （DFT）的逻辑门类型，包括优先与门 （PAND），功能相关门 （PDEP），热备件门（HSP），冷备件门 （CSP）和温备件门 （WSP）以及顺序相关门 （SEQ）。这些动态门是根据某种顺序或者是相互依赖关系以及冗余机制来建立的容错模型。本文中对无线传感器网络的可修复节点应用动态故障树的动态逻辑门建模：热备件门和冷备件门。并且该容错节点模型具有可修复属性和冗余属性。下文中首先研究冗余属性，给出热贮备节点和冷贮备节点两种具有冗余属性的容错模型，并分析其可靠性，在此基础上进一步考虑可修复属性，给出可修复节点模型及其可靠性。文中假设所有的传感器节点都是同一类型的（包括冗余传感器设备）并且都具有相同的失效率λ。

1.1 冗余节点容错模型及其可靠性

（1）热贮备节点容错模型及其可靠性

一个具有n个冗余设备 （A1，A2，…An）的传感器节点A0，A0的所有冗余设备和A0的性质及功能完全相同，其DFT 模型为热备件门如图1 （a）所示。热贮备节点的特点是在初始时刻，节点A0工作，其余的n个备用节点作为冗余设备，当A0发生故障时，冗余设备逐个去替换故障节点开始工作，但是这些冗余设备在不工作的情况下也具有和A0相同的失效率。Ai设备从正常工作状态以概率λ转变为故障状态的过程可用马尔科夫链来表示如图1 （b）所示。

图1 热贮备节点容错模型及状态转移过程

设P0（t）和P1（t）为Ai在时刻t处于状态0 （正常工作）以状态1 （故障状态）的概率。则Ai在时刻（t＋Δt）处于状态0的概率以及处于状态1的概率为

由状态转移可得Ai的故障概率为

对于HSP由于在初始时刻（t＝0）所有的冗余设备都是新的，所以热贮备节点系统的可靠度为

式中：n——冗余的设备数。

（2）冷贮备节点容错模型及其可靠性

具有n个冗余设备 （A1，A2，…An）的传感器节点A0，A0的所有冗余设备和A0的性质及功能完全相同，其DFT 模型为冷备件门如图2 （a）所示。冷贮备节点的特点是其冗余设备在没有工作的时候不会发生失效或劣化的情况。节点A0一开始就进入工作状态，而其它备用设备则是一开始不工作只是作为A0替代备件，当A0发生故障冗余设备逐个替代进行工作。

图2 冷贮备节点容错模型及状态转移过程

最简单的冷贮备系统由一个基本传感器节点A0和一个冗余设备A1构成。该冷贮备系统在如下情况下正常工作：A0正常工作；A0在时间t内故障冗余设备A1取代发挥功能。冷贮备系统的状态转移的马尔科夫链表示如图2 （b）。冷贮备系统可靠度是以下概率的和：A0在时刻t前工作正常的概率；A0在某一时刻τ（0＜τ ＜1）故障并且A1取代A0在时间τ～t内发挥功能的概率，即

那么

利用洛必达法则将式 （5）对λ2求导，有因为传感器设备的失效率λ恒定，所以令λ1＝λ，并求极限λ2→λ，得

将上面介绍的单备份扩展为 （n－1）个冗余设备的情况且失效率λ 恒定，则多冗余设备的冷贮备系统的可靠度为

1.2 可修复节点模型及其可靠性

（1）可修复热贮备节点模型及其可靠性

单个的可修复节点是最简单的可修系统，文中假设单个传感器节点的失效率为λ，它以修复率μ 被修复。可用度是可修系统最重要的性能指标之一，可用度A（t）指系统在任意时刻t可以使用的概率。对于不可修复的系统则有A（t）＝R（t）。如果失效率λ和修复率μ 都是恒定的，且节点的寿命符合指数分布时，那么A（t）可以由下面的公式得到

在不可修复节点的基础上实现可修复的节点可以用一个热贮备系统。可修复热贮备节点的模型表示和图1 （a）的HSP相同，区别在于Ai是可修复的，修复率为μ，系统的状态变换可以用如图3 所示的马儿科夫链过程来表示。图3中显示了具有一个冗余备份的可修复热贮备节点的状态转换过程。

图3 可修热贮备状态转移的马尔可夫链

根据状态转移可以写出转移率矩阵

设Pj（t）处于状态j的概率 （j＝0，1，2），且初始状态为P0（0）＝1，P1（0）＝P2（0）＝0，满足微分方程组

（2）可修复冷贮备节点模型及其可靠性

在不可修复节点的基础上实现可修复节点也可以用一个冷贮备系统。可修冷贮备节点模型在动态故障树中的用CSP表示和图2 （a）相同，不同的是Ai是可修复的，修复率为μ，图4中显示了具有一个冗余的冷贮备节点的马儿科夫链状态转换过程。

图4 可修冷贮备状态转移的马尔可夫链

根据状态转移可以写出转移率矩阵

A（t）＝设Pj（t）处于状态j的概率 （j＝0，1，2），且初始状态为P0（0）＝1，P1（0）＝P2（0）＝0，满足微分方程组

根据系统的可用度定理，可得可用度A（t）为

其中

为了比较在可修复容错机制下的节点可靠性性能，图5显示了在节点可修复的情况下没有冗余设备，热贮备，冷贮备3种容错机制下，在不同失效率λ和修复率μ 下的可用度的比较。热贮备，冷贮备节点各自具有1 个冗余 （1r）。其中rate1失效率取0.0008修复率为0.001，rate2失效率0.003修复率为0.0006。实验结果显示相同时间内可修复的HSP可用性是较好的。

2 基于动态故障树的WSN 可靠性结构

2.1 基本WSN 拓扑模型及加权WSN 可靠性模型

许多社会、经济和技术方面的系统结构都可以抽象成网络形式，其中节点表示系统实体，边表示系统实体之间的物理链路或相关链路。最基本的WSN 拓扑模型是用一个二元组G ＝（V，E）来表示网络拓扑结构图。通常在研究与节点或边有关的可靠性问题时，把与节点和边有关的可靠性属性作为权值，用加权图 （probabilistic weighted net－work，PWN）构造具有可靠性属性的模型，其形式化定义为G ＝（V，E，W）W ＝（f（v），g（e）），v∈V，e∈E，f 表示与节点有关的权的函数，g表示与边有关的权的函数。基于加权图的可靠性属性模型依托WSN 原有的拓扑结构。

图5 可修系统下不同容错机制的比较

2.2 动态故障树模型

动态故障树中的逻辑门是根据某种顺序或者是相互依赖关系的动态门。本文给出的可修复传感器节点模型使用的是动态故障树中的冷备件门和热备件门，因此属于动态故障树类型，下面给出一般动态故障树形式化定义。

定义1 DFtree＝（T，L），其中T ＝（tt，tm，tx）表示故障树事件的集合，事件的状态值为 ｛0，1｝，其中tt为顶事件，在文中指WSN 系统的工作状态，tm为中间事件，tx为底事件。L ＝ （AND，OR，n＿out＿m，HSP，CSP），AND 是与 门，OR 是 或 门，n－out－of－m 是 异 或 门，HSP 是热备件门，CSP是冷备件门。

2.3 基于动态故障树的WSN 可靠性结构

研究网络可靠性，在节点或边上加入相应的可靠性属性，形成一个网络靠性模型。为了更加直观地反映WSN 可靠性问题本身的结构性，本文从WSN 的拓扑结构出发，研究容错技术中可修复传感器节点下的WSN 可靠性，其中对可修复节点建立容错动态逻辑门模型，故引入动态故障树中事件与逻辑门两种表示方式，构造一种直观的基于动态故障树的WSN 可靠性结构。

WSN 可靠性结构的形式化定义

（1）V，表示WSN 系统中的传感器节点集合V＝｛S1，S2，…Sm｝，并且本文约定节点Sm的状态只有正常和失效两种，并假设相邻节点之间的链路是可靠的。下文中都用Si表示传感器节点；

（2）DFtree＝ （T，L），其中T ＝（tt，tm，tx）表示动态故障树事件的集合，事件的状态取值为 ｛0，1｝，其中tt为顶事件，在文中指WSN 系统的工作状态，tm为中间事件tx为底事件。L 是逻辑门，L ＝ （AND，OR，n＿out＿m，HSP，CSP）；

（3）Fd＿i，Fd表示传感器节点设备，且该节点的冗余度为i；

（4）Fv＝（Fv1，Fv2，…Fvi）表示网络中的节点设备失效率集合，其中Fvi表示节点vi的失效概率，失效的原因是由节点自设备故障导致，不考虑CCF 等外界因素并且Rvi＝1－Fvi表示节点vi的可靠度；

星型网络是最简单的一种WSN 网络拓扑结构，它的特点是由一组传感器节点作为外围节点，以sink节点或簇头CH 节点为中心节点构成的网络，每个传感器节点和中心节点进行点对点通信［13］。位于不同区域或功能的星型网络可以作为簇组织在一起形成一个含有若干个簇的簇型网络。根据以上簇型拓扑的特性给出簇型WSN 失效定义：①含有m 个簇的WSN，如果m 中有s 个簇失效，则WSN 失效；一个簇中含有n 个传感器节点，如果有多于k 各个传感器节点失效，那么该簇失效；②簇头节点CH 失效，则根据一定的网络协议在传感器节点中重新选出一个簇头节点来。

图6是一个含有3个簇的WSN，其中每个簇都是含有一个簇头CH 节点的星型网络。其中传感器节点和簇头CH是点对点通信，簇头CH 和sink 节点进行直接通信。该WSN 基于故障树的可靠性结构如图7所示。其中图7 （a）中传感器节点Si为中间事件，根据可修复节点模型，Si故障树结构如图7 （b）和图7 （c）所示，其中Fd＿Si表示节点Si本身，Fd＿i表示节点Si的第i个冗余。如果节点没有容错机制，则节点Si为底事件。

图6 簇型WSN 拓扑

图7 簇型WSN 可靠性结构及节点模型

3 基于动态故障树WSN 可靠性结构的BDD 算法

3.1 二元决策图 （BDD）及ITE操作

OBDD是一有向无环图，是表示和操作布尔函数的一种有效技术。

定义2 OBDD：一个有序二叉决策图（OBDD）表示一簇从｛0，1｝n到｛0，1｝的布尔函数f（x1，x2，…，xi，…，xn）的有向无环图，其形式化定义可以用一个八元组来表示［14］：

OBDD ＝（Root，Node，T，var，fu，u.high，u.low，π）

定义3 ite：如果布尔变量x，y，z 满足关系式：xy ＋z，则定义映射法则ite 使

ite（If－Then－Else）是一个含有3 个布尔 变量的操 作，描述了布尔变量x 以两种可能状态 （可以理解为事件的正常状态和和故障状态）传递给子节点y 和z。

3.2 基于容错节点模型下的WSN 可靠性评估算法

以图6的簇型WSN 拓扑结构为例，将可修复节点作为簇型WSN 的节点，构建WSN 基于动态故障树的可靠性结构，使用BDD＿Faulttree算法评估不同的容错模型下的网络可靠性。该算法分两步，首先用递归法实现WSN 可靠性结构向BDD 结构的转化，然后遍历BDD 计算WSN 可靠度。算法流程如图8所示。

图8 BDD＿Faulttre算法流程

4 实验及分析

本文利用Colorado大学的CUDD 软件包［15］，在运行平台Window XP，Intel Core 2Duo CPU，2.80GHz，3.25GB内存环境下。以图6WSN 拓扑模型为例，应用BDD＿Faulttree算法，计算和比较了在不可修复节点模型下的WSN 和可修复节点模型下的WSN 可靠性。其中WSN 拓扑网络中含有3个簇，每个簇含有30个传感器节点和一个簇头CH。根据WSN 失效定义，假设每个簇中有一半以上的传感器节点发生失效则这个簇失效；如果有两个簇同时失效则WSN整体失效。传感器件节点的故障率λ取0.0008，当传感器节点是不可修复时，分别计算无冗余节点，含有一个冗余（1r）的热贮备节点和含有一个冗余 （1r）的冷贮备节点3种情况下的WSN 失效概率，实验结果如图9所示。

图9 不可修复节点的WSN 可靠性

图9的结果表明节点在冷贮备容错机制下构成的WSN 的可靠性相对没有冗余和热贮备的WSN，其可靠性是较高的。

当传感器节点可修复时，在传感器的故障率λ 为0.0008的基础上，修复率μ取0.001，对3种不同的传感器节点类型组成的WSN 计算其失效概率：第一种是不含有冗余设备的节点类型；第二种是含有1 个冗余 （1r）设备的热贮备节点类型；第三种是含有一个冗余 （1r）设备的冷贮备节点类型。实验结果如图10 所示。相比之下，3000h之前含有1个冗余设备的冷贮备节点构成的WSN 可靠性较高；3000h以后含有1 个冗余设备的热贮备节点构成的WSN 可靠性较高。由于修复率μ 在本实验中假设是恒定不变的，所以图中的WSN 故障率随着时间的延长趋于稳定。

5 结束语

图10 可修复节点的WSN 可靠性

WSN 可靠性分析是WSN 网络设计、部署、验证和维护的一个重要环节。设计具有容错属性的WSN 能使网络在部分节点失效的情况下保持其功能。本文研究了容错技术中可修复节点背景下的WSN 可靠性问题。在硬件的层次上考虑了可修复热贮备节点和可修复冷贮备节点两种容错模型。以簇型WSN 拓扑结构为例，构建了WSN 可靠性问题研究整体框架的基础模型，并将以上两类可修复节点模型应用在该WSN 可靠性结构上。针对WSN 可靠性计算复杂度问题使用BDD 方法，将基于故障树的可靠性结构转换为BDD 结构，从而避免一般故障树分析方法中存在的复杂度为NP－hard不交化处理问题，降低了计算的时间，节省了能量的消耗，设计的方法具有较高的可实现性。

［1］Paradis L，Han Q.A survey of fault management in wireless sensor networks ［J］.Journal of Network and Systems Management，2007，15 （2）：171－190.

［2］Shrestha A，Xing L，Sun Y，et al.Infrastructure communication reliability of wireless sensor networks considering commoncause failures［J］.International Journal of Performability Engineering，2012，8 （2）：141－150.

［3］Venkatesan L，Shanmugavel S，Subramaniam C.A survey on modeling and enhancing reliability of wireless sensor network［J］.Wireless Sensor Network，2013，5 （3）：41－51.

［4］Alwan H，Agarwal A.A survey on fault tolerant routing techniques in wireless sensor networks ［C］／／Third International Conference on Sensor Technologies and Applications.IEEE，2009：366－371.

［5］Kavitha C，Viswanatha K V.An energy efficient fault tolerant multipath （EEFTM）routing protocol for wireless sensor networks ［C］／／Proc of IEEE International Advance Computing Conference，2009：746－751.

［6］Challal Y，Ouadjaout A，Lasla N，et al.Secure and efficient disjoint multipath construction for fault tolerant routing in wireless sensor networks ［J］.Journal of Network and Computer Applications，2011，34 （4）：1380－1397.

［7］Che－Aron Z，Al－Khateeb W F M，Anwar F.An enhancement of fault－tolerant routing protocol for wireless sensor network［C］／／International Conference on Computer and Communication Engineering.IEEE，2010：1－3.

［8］XIAO Wei，XU Ming，LV Pin，et al.Fault tolerant scheme for data aggregation in even cluster over wireless sensor network ［J］.Journal on Communications，2010，31 （6）：112－118 （in Chinese）.［肖伟，徐明，吕品，等.无线传感器网络事件簇的数据聚集容错机制［J］.通信学报，2010，31 （6）：112－118.］

［9］YUAN Shenfang，QIU Lei，TONG Yao，et al.FPAA based selfrepairing wireless sensor network node ［J］.Chinese Journal of Scientific Instrument，2012，33 （7）：1588－1593 （in Chinese）.［袁慎芳，邱雷，童瑶，等.基于FPAA 的自修复智能无线传感器节点［J］.仪器仪表学报，2012，33 （7）：1588－1593.］

［10］Silva I，Guedes L A，Portugal P，et al.Reliability and availability evaluation of wireless sensor networks for industrial applications［J］.Sensors，2012，12 （1）：806－838.

［11］SU Jinshu，GUO Wenzhong，YU Chaolong，et al.Faulttolerance clustering algorithm with load－balance aware in wireless sensor network ［J］.Chinese Journal of Computers，2014，37 （2）：445－456 （in Chinese）.［苏金树，郭文忠，余朝龙，等.负载均衡感知的无线传感器网络容错分簇算法［J］.计算机学报，2014，37 （2）：445－456.］

［12］Shrestha A，Xing L.Quantifying application communication reliability of wireless sensor networks［J］.International Journal of Performability Engineering，2008，4 （1）：43－56.

［13］Shrestha A，Xing L.A performance comparison of different topologies for wireless sensor networks ［C］／／IEEE Conference on Technologies for Homeland Security，2007：280－285.

［14］GU Tianlong，XU Zhoubo.Ordered binary decision diagram and its application ［M］.Beijing：Science Press，2009 （in Chinese）.［古天龙，徐周波.有序二叉决策图及应用 ［M］.北京：科学出版社，2009.］

［15］Somenzi F.CUDD：CU decision diagram package－release 2.5.0［CP／OL］.［2012－02－04］.http：／／vlsi.colorado.edu／～fabio／CUDD／cuddIntro.html.