基于故障树的无线传感器网络可靠度符号计算

聂晨华，高 西，董荣胜

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

0 引 言

故障树分析 （fault tree analysis，FTA）是一种分析无线传感器网络 （wireless sensor network，WSN）［1］可靠性的方法之一。Kim 等提供了一个基于簇型的三层WSN 模型上的一种综合可靠性评估方法：顶层是WSN 的网络故障树模型，中间层是传感器节点的故障树模型，底层是传感器节点组件的马尔科夫链模型，并使用SHARPE 软件工具计算了传感器节点以及WSN 的可靠度［2］；Bruneo提供了一种基于Non－Markovian 随机Petri网 （NMSPN）分析方法，研究了在WSN 可靠性中能量控制的问题，提供了用故障树来计算WSN 失效概率的方法［3］；Silva等用SHARPE 动态生成故障树，并用不交和 （SDP）的方法对故障树中的最小割集进行处理来计算WSN 的可靠度［4］。

由于应用不交和 （SDP）的方法在故障树上计算系统可靠度，存在最小割集 （MCS）的不交化处理过程，该过程是一个NP－hard问题。基于香农分解的BDD （binary decision diagram）本身具有不交化的特性，能够有效控制故障树不交化处理过程中的组合爆炸，BDD 表示的故障树包含了其所有的MCSs［5］。为此本文将BDD 技术引入到基于故障树求WSN 可靠性的处理中，以应用通信可靠性 （application communication reliability，ACR）［6］的通信模式为背景，利用故障树模型中的事件元素与逻辑门元素，建立基于故障树的WSN 可靠性结构。采用BDD 技术，利用BDD 中的ite操作技术，用递归的方法给出从WSN 可靠性结构转换到BDD 结构的算法，遍历BDD 计算WSN 的可靠度，优化可靠度计算过程，降低WSN 可靠度计算的复杂性。以分层簇型网络中可用路径以及节点冗余下的应用通信可靠性问题为例，给出其可靠性结构，通过给出的算法转换为BDD 结构，并计算以上两种情况下的WSN 可靠度。

1 基于故障树的WSN 可靠性结构

1.1 WSN 拓扑模型

社会、经济和技术方面很多的系统结构都可以抽象成网络形式，可以用节点表示系统实体，边表示系统实体之间的物理链路或相关链路。

最基本的WSN 拓扑模型是用一个二元组表示的网络拓扑结构图。

定义1 G ＝（V，E）表示由n 个节点和m 条边组成的网络的拓扑结构图，V ＝（v1，v2，…，vn）表示网络的节点集合，E ＝（e1，e2，…，em）表示网络中边的集合且E V×V 。

1.2 基于加权图的WSN 可靠性模型

一般采用加权图 （probabilistic weighted network，PWN）对网络中与节点或边有关的属性构造网络模型进行研究。

定义2 G＝（V，E，W），其中G，V，E 的含义与定义1相同，W ＝（f（v），g（e）），v∈V，e∈E，f 表示与节点有关的权的函数，g 表示与边有关的权的函数。

在研究与节点或边有关的可靠性问题时，常把与节点和边有关的可靠性属性作为权值，用加权图构造具有可靠性属性的模型。基于加权图的可靠性属性模型依托WSN 原有的拓扑结构。为了更加直观地反映WSN 可靠性问题本身的结构性，本文引入故障树中事件与逻辑门两种表示方式来构造基于故障树的WSN 可靠性结构。接下来先介绍一般故障树模型的形式化定义，然后给出基于故障树的WSN 可靠性结构的形式化定义。

1.3 一般故障树模型

故障树用图形和数学相结合的方法表示系统发生故障的事件之间的逻辑关系。故障树分为静态故障树和动态故障树两种类型，本文选择静态故障树进行建模。一般静态故障树形式化定义为：

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

1.4 基于故障树的WSN 可靠性结构

WSN 的网络拓扑结构会对网络的连通性和组织结构产生影响。目前，作为典型的WSN 拓扑结构有星型，mesh型和簇型结构［7］。研究网络可靠性，在节点或边上加入相应的可靠性属性，形成一个网络靠性模型。本文从WSN 的拓扑结构出发，利用故障树的事件和逻辑门元素，建立基于故障树的一种直观WSN 的可靠性结构。

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

定义4 F－WSN＝（V，Ftree，Fd＿i，Op，Fv，Pop＿v）

（1）Vnode，表示WSN 系统中的各类节点Node，Vnode＝（sink；CH1，…，CHi；Gw1，…，Gwj；S1，…，Sm），其中sink是汇聚节点，CH 是簇头节点，Gw 是网关节点，S是普通传感器节点Sensor nodes，下文中都用这些缩写字母表示，且本文约定节点Node的状态只有正常和失效两种，并假设相邻节点之间的链路是可靠的。

（2）Ftree＝ （T，L），其中T ＝（tt，tm，tx）表示故障树事件的集合，事件的状态取值为 ｛0，1｝，其中tt为顶事件，在文中指WSN 系统的工作状态，tm为中间事件，tx为底事件。L ＝（AND，OR，n＿out＿m），AND 是与门，OR是或门，n－out－of－m 是异或门。在WSN 故障树模型中底事件tx由网络中的各类节点Node的状态构成。

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

（4）Op＝（op＿1，op＿2，…op＿i）表示网络中节点的可用路径集合。其中op＿i表示第i条可用路径。

（5）Fv＝（Fv1，Fv2，…Fvi）表示网络中的节点设备失效率集合，其中Fvi表示节点vi的失效概率，失效的原因是由节点自身设备故障导致，Rvi＝1－Fvi表示节点vi的可靠度。

（6）Pop＿v＝（Pop＿v1，Pop＿v2，…，Pop＿vi）表示网络中节点的可用路径的失效率集合，其中Pop＿vi表示节点vi的可用路径的失效概率，Rop＿vi＝1－Pop＿vi表示节点vi到目标节点可用路径的可靠度。

本文以单播模式下的应用通信可靠性 （ACR）研究为背景，建立基于簇型拓扑 （hierarchical clustering topology）特性下的WSN 可靠性模型。基于簇的分层拓扑中，所有传感器节点S都处于最底层level－0 （第0层），传感器节点S通过自组织与周围的节点形成若干个簇Ci（i＝1，2，…m），并按分簇算法为每个簇选出一个簇头，用表示level－k的簇头节点。在level－0 的基础上选出来的所有又形成高一级的簇level－1，再在这个level－1 簇中再选出一个簇头，簇中的网关节点Gwi也是同样分层，这个过程反复执行，直到选出处于网络体系中最高层的。最高层的CH（t）i往往是离sink较近的节点，t表示WSN 体系中的最高层level－t。分层簇形拓扑节点之间的通信包含了多跳的meth网路由，以及簇和簇之间的通信要经过中间的路由节点即网关节点Gwi。选择从传感器节点到sink节点的数据传播路径步骤是：处于level－0中的传感器节点S要将数据传输给sink节点，首先它要将信息通过多跳的方式发送给本簇中的，然后再将信息以同样的方式发送给本簇中的网关节点，在与处在高一层簇中的网关节点通信，再将信息发送给，最后直接送入sink节点。根据以上簇型拓扑的特性给出分层簇WSN 失效定义。

（1）含有m 个簇的WSN，若m 中有多于s个簇失效，则WSN失效；一个簇中含有n个传感器节点S，若有多于k个S失效，或者该簇中的簇头CH（0）i失效，则么该簇失效。

（2）sink失效，则WSN 失效。

（3）与sink直接通信的簇中若n 个传感器节点S中有多于k个节点失效或簇头失效，则WSN 失效。

（4）每个簇中所有的网关节点失效则该簇失效，与sink直接通信的簇中的所有网关失效，则WSN失效。

下面给出WSN 网络可靠度定义及其它相关定义。

定义5 节点设备可靠度：节点设备可靠度针对的是节点的软件和硬件功能正常工作的概率。

用一个非负随机变量X 来描述节点v 的寿命，X 相应的分布函数为Fv（t）＝P｛X ≤t｝（t≥0），Fv（t）称为节点v的失效函数，即t时刻时的失效概率，那么在时刻t以前都不失效的概率即网络节点在时刻t 的生存概率Rv（t）＝P｛X＞t｝＝1－Fv（t）＝（t），式中Rv（t）称为节点设备在时刻t的可靠度函数或可靠度。

定义6 可用路径失效Op：在具有多跳路由的WSN中，可用路径是源节点和目标节点保持连通的路径，即从一个节点到目标节点的路径上经过的每一个节点都是必不可少的，若路径上经过的任何一个节点因为其设备发生故障，源节点和目标节点都不连通，即认为此条路径失效。

定义7 节点失效：当节点的设备出现永久性故障或者在该节点和目标节点之间不存在可用路径而无法进行通信的情况下认为该节点失效。

定义8 WSN 可靠度：WSN 可靠度记为RWSN是衡量WSN 网络可靠性的一个重要指标，那么WSN 失效概率为PWSN＝1－RWSN。本文中计算的WSN 失效概率PWSN指WSN 在特定的拓扑结构下，根据其失效条件发生网络的整体失效而无法正常工作的概率。

根据以上给出的节点失效定义和可用路径Op失效的定义来构建WSN 网络节点的故障树模型如图1所示，图中的Node可以是节点CH，Gw，S。Fd＿0 表示该节点的冗余度为0。

网络节点易失效，这种失效往往能够被冗余设备所容纳，并且当节点发生故障时，冗余设备可以替代原节点完成原有功能，且冗余设备与原节点具有相同的失效概率。其故障树模型如图2 所示，图中的Node可以是节点CH，Gw，S。Fd＿0…Fd＿j表示该节点共有j个冗余设备。

图1 不含冗余设备的节点故樟树

图2 含有冗余设备的节点故樟树

根据上文中的形式化模型和相关定义给出一个分层簇型的WSN 的例子。含有3个簇的2层WSN 拓扑图如图3所示，其基于故障树的可靠性结构如图4所示。其中传感器节点S，簇头节点CH，网关节点Gw 是中间事件，这些节点的故障树模型如图1或图2所示。

图3 WSN 分层簇型拓扑

2 WSN 节点和可用路径失效概率的计算

根据节点设备可靠度定义，由于节点的设备发生故障，可以引起的节点的失效，假设组成WSN 的4 种节点（sink，CH，Gw，S）的失效函数都符合指数分布，由于它们在网络中的位置和功能的不同，因此各种节点设备的失效率λ 是不同的，普通的传感器节点S 的失效率最高，Gw，CH，sink的失效率依次降低，并且可以通过平均寿命MTTF 计算出节点设备失效率，根据

式中：λ——节点设备的失效率，当MTTF（hours）为2年时，λ5e－5，将以上的计算出来的节点设备失效率λ作为传感器节点S的失效率，Gw，CH，Sink的失效率依次降低一个数量级，然后将各节点的失效率λ带入指数分布函数F（t）＝1－e－λt，λ＞0，t≥0中就可以计算出时刻t下的节点设备失效概率。

图4 基于故障树的分层簇型WSN 可靠性结构

根据可用路径Op的定义，引起节点所在的可用路径失效Op的原因是路径上的存在由于设备故障引起的失效节点，计算可用路径Op的失效概率时，运用组合数学中的容斥原理，首先要枚举源节点v 到目标节点的所有可用路径Op，然后运用容斥原理进行不交化求解，得到可用路径Op可靠度Rop＿v，那么Op的失效概率即Pop＿v＝1－Rop＿v。设opi表示节点v 到达目的节点的第i条可用路径，若节点v到达目的节点有n 条可用路径，则这n条可用路径中至少有一条可用的概率为

那么节点v 的可用路径opv全部失效的概率Pop＿v＝1－Rop＿v。

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

3.1 二元决策图 （BDD）

BDD 可以实现状态空间或者变量组合的隐式表示和搜索，减缓或者部分程度上避免状态空间爆炸问题［8］。

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

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

新的BDD 的生成，通常采用已有的BDD 通过故障树中的逻辑门如AND，OR，EX－OR 等来进行连接。若给一个给定的故障树来构造它的BDD，首先要为每个基本事件构建BDD，然后解析连接基本事件的逻辑关系，将已有的BDD 进行连接形成新的组合BDD。这个过程可以用三元逻辑运算工具ite（If－Then－Else）来实现。

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

ite（If－Then－Else）是一个含有3 个布尔变量的操作，描述了布尔变量x 以两种可能状态 （可以理解为事件的正常状态和和故障状态）传递给子节点y 和z。由于BDD 的基本依据是香农分解原理，布尔函数的BDD 表示实质就是一个三元组（xi；fxi＝0；fxi＝1）的递归表示，而香农分解原理f＝xi·fxi＝1＋·fxi＝0又可写成ite操作的形式，即可以将一个布尔函数描述为f ＝ite（xi；fxi＝0；fxi＝1），其中fxi＝0，fxi＝1可以继续用ite 操作递归地分解下去，所以ite 操作也是BDD 的一个基本操作。若知道了两个BDD 结构，则可以通过下面两个重要的ite连接规则来将某种逻辑操作下的两个子BDD 连接起来。

定理1 ite 连接规则：设两个子BDD 结构分别为M＝ite（xi，A1，A2）和N ＝ite（xj，B1，B2），则

式中： “◇”——任意逻辑运算 （如 “且AND/或OR”）。运用该规则关键要判断两个子BDD 根节点的排序大小。

3.2 WSN 可靠性结构BDD＿Faulttree算法

本文基于故障树的WSN 可靠性结构给出BDD＿Faulttree算法，以分层簇拓扑结构下的WSN 可靠性为例分析。该算法分为两步，首先用递归法实现WSN 可靠性结构向BDD 的转化，然后遍历BDD 计算WSN 可靠度。本文利用Colorado大学的CUDD 软件包［10］中ite 操作给出用递归方法实现构建WSN 可靠性结构的BDD 算法。此外，将故障树转换为BDD 之前，须对基本事件进行排序，本文采用的是深度优先 （DFS）的方式搜索WSN 可靠性结构来确定基本事件的顺序。

基于递归法的BDD＿Faulttree算法是将基本事件用ite表示，形成一个基本事件的BDD 结构，然后解析最低一层的逻辑门事件，并用ite 的连接规则将每一层逻辑门事件的BDD 结构进行连接，以此类推，由下至上递归置换，最后可以得到WSN 可靠性结构的BDD 结构。

WSN 系统的BDD 结构精确地描述了基本事件 （网络节点的工作状态）影响顶事件 （WSN 系统）的状态及路径。在BDD 中，顶事件的所有从根节点到叶子节点值为“1”，并且不包括叶节点的路径就是故障树的不交化割集（MCS）。用深度优先搜索 （DFS）的方法可以找到所有的不交路径，WSN 系统失效的发生概率就等于BDD 上所有的不交路径之和。通过深度优先 （DFS）搜索遍历BDD 求WSN 系统的失效概率，应用下述公式

在构造好的BDD 结构中会存在相同结构的BDD 子图，因此在遍历BDD 的过程中，会在这些子图上重复遍历并计算可靠性，这样会造成大量的冗余计算。为此在算法中应用哈希表的结构，把已计算好的下一层子节点上的失效概率值存储在哈希表中，使算法的时间复杂度降为O（n），提高了算法的效率。

给定F－WSN 算法步骤如下：

（1）定义函数dfstraverse＿Faulttree深度遍历故障树确定作为基本事件的节点序列。

（2）根据节点的序列号从根节点开始，初始化故障树每个节点FaultTree.node［i］的索引号 （作为在BDD 中的标记），子节点个数，操作逻辑，和构建当前节点的孩子节点队列，若是叶子节点则标记其操作逻辑为－1，如果是非叶子节点则 “OR”操作标记为0， “AND”操作标记为1，定义函数buildFaultTree构建WSN 的故障树，最后返回故障树根节点地址。

（3）从故障树中获取节点FaultTree.node［i］，定义函数BDD＿Faulttree为将故障树转换为BDD 结构，判断当前节点是否是叶子节点，若是则利用CUDD 包中的Cudd＿bddIthVar函数构造叶子节点的BDD 结构并将该叶子节点的索引号CTree.node［i］.data一起存入所构造的BDD 中，并返回BDD，否则继续下一步操作。

（4）如果当前节点FaultTree.node［i］操作逻辑为“OR”门，则跳转到 （3），则继续访问该节点的子节点，将返回值存入集合set1，并用ite＿or操作：Cudd＿bddite将set1中的BDD 进行 “or”连接否则继续下一步操作。

（5）若当前节点操作逻辑为 “AND”门，则跳转到（3），则继续访问该节点的子节点，将返回值存入集合set2，并用ite＿and操作：Cudd＿bddite将set2 中的BDD进行 “and”连接，否则继续下一步操作。

（6）故障树的BDD 的地址附给指针变量root，为BDD中节点构造哈希表HashTable并初始化。

（7）定义计算节点失效率函数computeFailureRate，从root开始深度遍历访问节点，若当前访问的是叶子节点为左孩子，则返回1；如果叶子节点为右孩子，则返回0，如果为非叶子节点则继续下一步。

（8）根据当前节点的地址作为Key在哈希表中查找，若有记录，则返回哈希表中当前节点的失效概率，否则继续下一步。

（9）根据下面的公式计算当前节点两个分支上的失效概率，然后用当前节点的地址作为Key，将失效率存入哈希表中，并返回该节点失效概率。

p ＝p＊computeFailureRate（T，1，failureRateAll）＋（1－p）＊computeFailureRate（E，0，failureRateAll）

伪码如下：r

4 算法实例

下面以图5所示的一个简单例子，构建对应的BDD 结构，并计算网络失效概率。模型中的顶事件TOP 为WSN失效。分别给它们分配一个序列号：S1，S2，Gw，CH，S3，S4分别对应于x1，x2，x3，x4，x5，x6。在 运 用 递 归 法 时，首 先选择底事件的指标顺序，假设所选用的顺序是：x1＜x2＜x3＜x4＜x5＜x6，每一层的BDD 构造过程如下：

图5 WSN 可靠性的一般结构

由顶事件的ite 结构得到的BDD 结构如图6所示。

图6 WSN 可靠性结构对应的BDD 结构

深度遍历BDD 结构求不交化割集为顶事件的所有从根节点到叶子节点值为 “1”，不包括叶节点的路径，路径中经过节点的0－分支，则记为，表示基本事件xi没有发生，实例中的不交割集为：

顶事件WSN 的发生概率等于BDD 上所有的不交路径之和，网络失效概率计算如下，Fxi为各个序列号对应节点的失效概率

5 实验及分析

定量分析分层簇型WSN 可靠性结构上的可靠度，应用上文介绍的BDD＿Faulttree算法假设WSN 有3 个簇，每个簇含有15个S，2个Gw 和1个CH，并假设节点间的通信路径有一定的路由支持。簇形拓扑的特点在于节点间信息的传播是多路径的，从直观上讲，通信节点间不同路径条数会影响网络的可靠性，下面的实验中各节点失效率λ 取在MTTF－2年，假设信息从S节点传输到CH，CH 到Gw，以及Gw到处在最高层簇的CH 这些过程中通信节点间都为两跳，但原节点到目的节点间的可用路径条数Op不同。Op分别为1条，2条，3条时的网络失效情况如图7所示。

图7 节点间路径数不同时WSN 失效率

图7中，可用路径越多网络的失效概率就越小。增加节点之间的路径数能够有效地降低网络的失效概率，因为路径越少，一旦链路受阻，就不会有其它的路径通往目的节点，而簇型网络的Mesh结构能提供多跳的冗余路径，因此具有较高的容错性。若路由节点失效或者是两个节点之间的链路不可用，则网络自动重新配置失效组件的路径。由于重新配置路由时会增加节点能量和资源的消耗，从而使系统的开销增加。

若给节点提供冗余，则选择给不同类型的节点增设冗余对网络的可靠性影响是不同的。实验中选择一类节点为其增设一个冗余设备 （1r），其它种类的节点不增设，对比网络整体的失效情况，节点的平均失效时间仍为MTTF－2年，结果如图8所示。

图8中，在0 至1000h 内，分别给S 节点，Gw 以及CH 增设一个冗余设备时，网络的失效情况基本相同。在1000h到2500h之间，为CH 增设冗余设备时，WSN 网络的失效概率要比另外两个稍低一些。在2500h以后三者出现了明显的区别，随着时间的延长，给S节点增设冗余设备时网络的失效概率和给CH 节点及Gw 节点增设冗余设

图8 含有不同冗余节点的WSN 失效概率

备相差越来越大，最大的失效概率相差3倍以上。虽然给S节点增设冗余能够大幅度地降低网络的失效概率，但由于S节点数量较多，所以增加冗余设备的代价要比CH 和Gw要大。2500h以后，分别给Gw 和CH 增设冗余的网络失效情况基本呈平行状，给S节点增设冗余设备网络的失效概率最低。

6 结束语

WSN 可靠性分析是WSN 网络设计、部署、验证和维护的一个重要环节。本文基于故障树建立了WSN 可靠性结构，形成对WSN 可靠性问题研究的整体框架的基础模型。针对WSN 可靠性问题引入BDD 方法，将基于故障树的可靠性结构转换为BDD 结构，从而避免一般故障树分析方法中存在不交化处理过程，进而形成一种新的WSN 可靠性问题研究的思路，文中还给出了利用以上思路计算WSN 应用通信可靠性 （ACR）背景下分层簇型拓扑结构WSN 可靠度的应用。

［1］AboElFotoh H M F，Iyengar S S，Chakrabarty K.Computing reliability and message delay for cooperative wireless distributed sensor networks subject to random failures［J］.IEEE Transactions on Reliability，2005，54 （1）：145－155.

［2］Kim D S，Ghosh R，Trivedi K S.A hierarchical model for reliability analysis of sensor networks ［C］//IEEE 16th Pacific Rim International Symposium on Dependable Computing，2010：247－248.

［3］Bruneo D，Puliafito A，Scarpa M.Dependability analysis of wireless sensor networks with active－sleep cycles and redundant nodes［C］//Proceedings of the First Workshop on Dynamic Aspects in Dependability Models for Fault－Tolerant Systems.ACM，2010：25－30.

［4］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.

［5］Contini S，Matuzas V.Analysis of large fault trees based on functional decomposition ［J］.Reliability Engineering ＆ System Safety，2011，96 （3）：383－390.

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

［7］Bruneo D，Puliafito A，Scarpa M.Dependability evaluation of wireless sensor networks：Redundancy and topological aspects［C］//Sensors.IEEE，2010：1827－1831.

［8］Gu T，Xu Z，Yang Z.Symbolic OBDD representations for mechanical assembly sequences ［J］.Computer－Aided Design，2008，40 （4）：411－421.

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

［10］Somenzi F.CUDD：CU decision diagram package－release2.5.0［CP/OL］.［2012－02－04］.http：//vlsi.colorado.edu/～fabio/CUDD/cuddIntro.html.