聶晨華，高 西，董榮勝

（桂林電子科技大學(xué) 廣西可信軟件重點實驗室，廣西 桂林541004）

0 引 言

故障樹分析 （fault tree analysis，F(xiàn)TA）是一種分析無線傳感器網(wǎng)絡(luò) （wireless sensor network，WSN）［1］可靠性的方法之一。Kim 等提供了一個基于簇型的三層WSN 模型上的一種綜合可靠性評估方法：頂層是WSN 的網(wǎng)絡(luò)故障樹模型，中間層是傳感器節(jié)點的故障樹模型，底層是傳感器節(jié)點組件的馬爾科夫鏈模型，并使用SHARPE 軟件工具計算了傳感器節(jié)點以及WSN 的可靠度［2］；Bruneo提供了一種基于Non－Markovian 隨機Petri網(wǎng) （NMSPN）分析方法，研究了在WSN 可靠性中能量控制的問題，提供了用故障樹來計算WSN 失效概率的方法［3］；Silva等用SHARPE 動態(tài)生成故障樹，并用不交和 （SDP）的方法對故障樹中的最小割集進行處理來計算WSN 的可靠度［4］。

由于應(yīng)用不交和 （SDP）的方法在故障樹上計算系統(tǒng)可靠度，存在最小割集 （MCS）的不交化處理過程，該過程是一個NP－h(huán)ard問題?；谙戕r(nóng)分解的BDD （binary decision diagram）本身具有不交化的特性，能夠有效控制故障樹不交化處理過程中的組合爆炸，BDD 表示的故障樹包含了其所有的MCSs［5］。為此本文將BDD 技術(shù)引入到基于故障樹求WSN 可靠性的處理中，以應(yīng)用通信可靠性 （application communication reliability，ACR）［6］的通信模式為背景，利用故障樹模型中的事件元素與邏輯門元素，建立基于故障樹的WSN 可靠性結(jié)構(gòu)。采用BDD 技術(shù)，利用BDD 中的ite操作技術(shù)，用遞歸的方法給出從WSN 可靠性結(jié)構(gòu)轉(zhuǎn)換到BDD 結(jié)構(gòu)的算法，遍歷BDD 計算WSN 的可靠度，優(yōu)化可靠度計算過程，降低WSN 可靠度計算的復(fù)雜性。以分層簇型網(wǎng)絡(luò)中可用路徑以及節(jié)點冗余下的應(yīng)用通信可靠性問題為例，給出其可靠性結(jié)構(gòu)，通過給出的算法轉(zhuǎn)換為BDD 結(jié)構(gòu)，并計算以上兩種情況下的WSN 可靠度。

1 基于故障樹的WSN 可靠性結(jié)構(gòu)

1.1 WSN 拓撲模型

社會、經(jīng)濟和技術(shù)方面很多的系統(tǒng)結(jié)構(gòu)都可以抽象成網(wǎng)絡(luò)形式，可以用節(jié)點表示系統(tǒng)實體，邊表示系統(tǒng)實體之間的物理鏈路或相關(guān)鏈路。

最基本的WSN 拓撲模型是用一個二元組表示的網(wǎng)絡(luò)拓撲結(jié)構(gòu)圖。

定義1 G ＝（V，E）表示由n 個節(jié)點和m 條邊組成的網(wǎng)絡(luò)的拓撲結(jié)構(gòu)圖，V ＝（v1，v2，…，vn）表示網(wǎng)絡(luò)的節(jié)點集合，E ＝（e1，e2，…，em）表示網(wǎng)絡(luò)中邊的集合且E V×V 。

1.2 基于加權(quán)圖的WSN 可靠性模型

一般采用加權(quán)圖 （probabilistic weighted network，PWN）對網(wǎng)絡(luò)中與節(jié)點或邊有關(guān)的屬性構(gòu)造網(wǎng)絡(luò)模型進行研究。

定義2 G＝（V，E，W），其中G，V，E 的含義與定義1相同，W ＝（f（v），g（e）），v∈V，e∈E，f 表示與節(jié)點有關(guān)的權(quán)的函數(shù)，g 表示與邊有關(guān)的權(quán)的函數(shù)。

在研究與節(jié)點或邊有關(guān)的可靠性問題時，常把與節(jié)點和邊有關(guān)的可靠性屬性作為權(quán)值，用加權(quán)圖構(gòu)造具有可靠性屬性的模型?；诩訖?quán)圖的可靠性屬性模型依托WSN 原有的拓撲結(jié)構(gòu)。為了更加直觀地反映WSN 可靠性問題本身的結(jié)構(gòu)性，本文引入故障樹中事件與邏輯門兩種表示方式來構(gòu)造基于故障樹的WSN 可靠性結(jié)構(gòu)。接下來先介紹一般故障樹模型的形式化定義，然后給出基于故障樹的WSN 可靠性結(jié)構(gòu)的形式化定義。

1.3 一般故障樹模型

故障樹用圖形和數(shù)學(xué)相結(jié)合的方法表示系統(tǒng)發(fā)生故障的事件之間的邏輯關(guān)系。故障樹分為靜態(tài)故障樹和動態(tài)故障樹兩種類型，本文選擇靜態(tài)故障樹進行建模。一般靜態(tài)故障樹形式化定義為：

定義3 Ftree＝（T，L），其中T＝（tt，tm，tx）表示故障樹事件的集合，事件的狀態(tài)值為 ｛0，1｝，其中tt為頂事件，在文中指WSN 系統(tǒng)的工作狀態(tài)，tm為中間事件，tx為底事件。L ＝（AND，OR，n＿out＿m），AND 是與門，OR是或門，n－out－of－m 是異或門。

1.4 基于故障樹的WSN 可靠性結(jié)構(gòu)

WSN 的網(wǎng)絡(luò)拓撲結(jié)構(gòu)會對網(wǎng)絡(luò)的連通性和組織結(jié)構(gòu)產(chǎn)生影響。目前，作為典型的WSN 拓撲結(jié)構(gòu)有星型，mesh型和簇型結(jié)構(gòu)［7］。研究網(wǎng)絡(luò)可靠性，在節(jié)點或邊上加入相應(yīng)的可靠性屬性，形成一個網(wǎng)絡(luò)靠性模型。本文從WSN 的拓撲結(jié)構(gòu)出發(fā)，利用故障樹的事件和邏輯門元素，建立基于故障樹的一種直觀WSN 的可靠性結(jié)構(gòu)。

WSN 可靠性結(jié)構(gòu)的形式化定義：

定義4 F－WSN＝（V，F(xiàn)tree，F(xiàn)d＿i，Op，F(xiàn)v，Pop＿v）

（1）Vnode，表示W(wǎng)SN 系統(tǒng)中的各類節(jié)點Node，Vnode＝（sink；CH1，…，CHi；Gw1，…，Gwj；S1，…，Sm），其中sink是匯聚節(jié)點，CH 是簇頭節(jié)點，Gw 是網(wǎng)關(guān)節(jié)點，S是普通傳感器節(jié)點Sensor nodes，下文中都用這些縮寫字母表示，且本文約定節(jié)點Node的狀態(tài)只有正常和失效兩種，并假設(shè)相鄰節(jié)點之間的鏈路是可靠的。

（2）Ftree＝ （T，L），其中T ＝（tt，tm，tx）表示故障樹事件的集合，事件的狀態(tài)取值為 ｛0，1｝，其中tt為頂事件，在文中指WSN 系統(tǒng)的工作狀態(tài)，tm為中間事件，tx為底事件。L ＝（AND，OR，n＿out＿m），AND 是與門，OR是或門，n－out－of－m 是異或門。在WSN 故障樹模型中底事件tx由網(wǎng)絡(luò)中的各類節(jié)點Node的狀態(tài)構(gòu)成。

（3）Fd＿i，F(xiàn)d表示傳感器節(jié)點的軟硬件設(shè)備，且該節(jié)點的冗余度為i。

（4）Op＝（op＿1，op＿2，…op＿i）表示網(wǎng)絡(luò)中節(jié)點的可用路徑集合。其中op＿i表示第i條可用路徑。

（5）Fv＝（Fv1，F(xiàn)v2，…Fvi）表示網(wǎng)絡(luò)中的節(jié)點設(shè)備失效率集合，其中Fvi表示節(jié)點vi的失效概率，失效的原因是由節(jié)點自身設(shè)備故障導(dǎo)致，Rvi＝1－Fvi表示節(jié)點vi的可靠度。

（6）Pop＿v＝（Pop＿v1，Pop＿v2，…，Pop＿vi）表示網(wǎng)絡(luò)中節(jié)點的可用路徑的失效率集合，其中Pop＿vi表示節(jié)點vi的可用路徑的失效概率，Rop＿vi＝1－Pop＿vi表示節(jié)點vi到目標節(jié)點可用路徑的可靠度。

本文以單播模式下的應(yīng)用通信可靠性 （ACR）研究為背景，建立基于簇型拓撲 （hierarchical clustering topology）特性下的WSN 可靠性模型?；诖氐姆謱油負渲?，所有傳感器節(jié)點S都處于最底層level－0 （第0層），傳感器節(jié)點S通過自組織與周圍的節(jié)點形成若干個簇Ci（i＝1，2，…m），并按分簇算法為每個簇選出一個簇頭，用表示level－k的簇頭節(jié)點。在level－0 的基礎(chǔ)上選出來的所有又形成高一級的簇level－1，再在這個level－1 簇中再選出一個簇頭，簇中的網(wǎng)關(guān)節(jié)點Gwi也是同樣分層，這個過程反復(fù)執(zhí)行，直到選出處于網(wǎng)絡(luò)體系中最高層的。最高層的CH（t）i往往是離sink較近的節(jié)點，t表示W(wǎng)SN 體系中的最高層level－t。分層簇形拓撲節(jié)點之間的通信包含了多跳的meth網(wǎng)路由，以及簇和簇之間的通信要經(jīng)過中間的路由節(jié)點即網(wǎng)關(guān)節(jié)點Gwi。選擇從傳感器節(jié)點到sink節(jié)點的數(shù)據(jù)傳播路徑步驟是：處于level－0中的傳感器節(jié)點S要將數(shù)據(jù)傳輸給sink節(jié)點，首先它要將信息通過多跳的方式發(fā)送給本簇中的，然后再將信息以同樣的方式發(fā)送給本簇中的網(wǎng)關(guān)節(jié)點，在與處在高一層簇中的網(wǎng)關(guān)節(jié)點通信，再將信息發(fā)送給，最后直接送入sink節(jié)點。根據(jù)以上簇型拓撲的特性給出分層簇WSN 失效定義。

（1）含有m 個簇的WSN，若m 中有多于s個簇失效，則WSN失效；一個簇中含有n個傳感器節(jié)點S，若有多于k個S失效，或者該簇中的簇頭CH（0）i失效，則么該簇失效。

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

（3）與sink直接通信的簇中若n 個傳感器節(jié)點S中有多于k個節(jié)點失效或簇頭失效，則WSN 失效。

（4）每個簇中所有的網(wǎng)關(guān)節(jié)點失效則該簇失效，與sink直接通信的簇中的所有網(wǎng)關(guān)失效，則WSN失效。

下面給出WSN 網(wǎng)絡(luò)可靠度定義及其它相關(guān)定義。

定義5 節(jié)點設(shè)備可靠度：節(jié)點設(shè)備可靠度針對的是節(jié)點的軟件和硬件功能正常工作的概率。

用一個非負隨機變量X 來描述節(jié)點v 的壽命，X 相應(yīng)的分布函數(shù)為Fv（t）＝P｛X ≤t｝（t≥0），F(xiàn)v（t）稱為節(jié)點v的失效函數(shù)，即t時刻時的失效概率，那么在時刻t以前都不失效的概率即網(wǎng)絡(luò)節(jié)點在時刻t 的生存概率Rv（t）＝P｛X＞t｝＝1－Fv（t）＝（t），式中Rv（t）稱為節(jié)點設(shè)備在時刻t的可靠度函數(shù)或可靠度。

定義6 可用路徑失效Op：在具有多跳路由的WSN中，可用路徑是源節(jié)點和目標節(jié)點保持連通的路徑，即從一個節(jié)點到目標節(jié)點的路徑上經(jīng)過的每一個節(jié)點都是必不可少的，若路徑上經(jīng)過的任何一個節(jié)點因為其設(shè)備發(fā)生故障，源節(jié)點和目標節(jié)點都不連通，即認為此條路徑失效。

定義7 節(jié)點失效：當(dāng)節(jié)點的設(shè)備出現(xiàn)永久性故障或者在該節(jié)點和目標節(jié)點之間不存在可用路徑而無法進行通信的情況下認為該節(jié)點失效。

定義8 WSN 可靠度：WSN 可靠度記為RWSN是衡量WSN 網(wǎng)絡(luò)可靠性的一個重要指標，那么WSN 失效概率為PWSN＝1－RWSN。本文中計算的WSN 失效概率PWSN指WSN 在特定的拓撲結(jié)構(gòu)下，根據(jù)其失效條件發(fā)生網(wǎng)絡(luò)的整體失效而無法正常工作的概率。

根據(jù)以上給出的節(jié)點失效定義和可用路徑Op失效的定義來構(gòu)建WSN 網(wǎng)絡(luò)節(jié)點的故障樹模型如圖1所示，圖中的Node可以是節(jié)點CH，Gw，S。Fd＿0 表示該節(jié)點的冗余度為0。

網(wǎng)絡(luò)節(jié)點易失效，這種失效往往能夠被冗余設(shè)備所容納，并且當(dāng)節(jié)點發(fā)生故障時，冗余設(shè)備可以替代原節(jié)點完成原有功能，且冗余設(shè)備與原節(jié)點具有相同的失效概率。其故障樹模型如圖2 所示，圖中的Node可以是節(jié)點CH，Gw，S。Fd＿0…Fd＿j表示該節(jié)點共有j個冗余設(shè)備。

圖1 不含冗余設(shè)備的節(jié)點故樟樹

圖2 含有冗余設(shè)備的節(jié)點故樟樹

根據(jù)上文中的形式化模型和相關(guān)定義給出一個分層簇型的WSN 的例子。含有3個簇的2層WSN 拓撲圖如圖3所示，其基于故障樹的可靠性結(jié)構(gòu)如圖4所示。其中傳感器節(jié)點S，簇頭節(jié)點CH，網(wǎng)關(guān)節(jié)點Gw 是中間事件，這些節(jié)點的故障樹模型如圖1或圖2所示。

圖3 WSN 分層簇型拓撲

2 WSN 節(jié)點和可用路徑失效概率的計算

根據(jù)節(jié)點設(shè)備可靠度定義，由于節(jié)點的設(shè)備發(fā)生故障，可以引起的節(jié)點的失效，假設(shè)組成WSN 的4 種節(jié)點（sink，CH，Gw，S）的失效函數(shù)都符合指數(shù)分布，由于它們在網(wǎng)絡(luò)中的位置和功能的不同，因此各種節(jié)點設(shè)備的失效率λ 是不同的，普通的傳感器節(jié)點S 的失效率最高，Gw，CH，sink的失效率依次降低，并且可以通過平均壽命MTTF 計算出節(jié)點設(shè)備失效率，根據(jù)

式中：λ——節(jié)點設(shè)備的失效率，當(dāng)MTTF（hours）為2年時，λ5e－5，將以上的計算出來的節(jié)點設(shè)備失效率λ作為傳感器節(jié)點S的失效率，Gw，CH，Sink的失效率依次降低一個數(shù)量級，然后將各節(jié)點的失效率λ帶入指數(shù)分布函數(shù)F（t）＝1－e－λt，λ＞0，t≥0中就可以計算出時刻t下的節(jié)點設(shè)備失效概率。

圖4 基于故障樹的分層簇型WSN 可靠性結(jié)構(gòu)

根據(jù)可用路徑Op的定義，引起節(jié)點所在的可用路徑失效Op的原因是路徑上的存在由于設(shè)備故障引起的失效節(jié)點，計算可用路徑Op的失效概率時，運用組合數(shù)學(xué)中的容斥原理，首先要枚舉源節(jié)點v 到目標節(jié)點的所有可用路徑Op，然后運用容斥原理進行不交化求解，得到可用路徑Op可靠度Rop＿v，那么Op的失效概率即Pop＿v＝1－Rop＿v。設(shè)opi表示節(jié)點v 到達目的節(jié)點的第i條可用路徑，若節(jié)點v到達目的節(jié)點有n 條可用路徑，則這n條可用路徑中至少有一條可用的概率為

那么節(jié)點v 的可用路徑opv全部失效的概率Pop＿v＝1－Rop＿v。

3 基于故障樹WSN 可靠性結(jié)構(gòu)的BDD 算法

3.1 二元決策圖 （BDD）

BDD 可以實現(xiàn)狀態(tài)空間或者變量組合的隱式表示和搜索，減緩或者部分程度上避免狀態(tài)空間爆炸問題［8］。

定義9 OBDD：一個有序二叉決策圖 （OBDD）表示一簇從｛0，1｝n到｛0，1｝的布爾函數(shù)f（x1，x2，…，xi，…，xn）的有向無環(huán)圖，其形式化定義可以用一個八元組來表示［9］：

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

新的BDD 的生成，通常采用已有的BDD 通過故障樹中的邏輯門如AND，OR，EX－OR 等來進行連接。若給一個給定的故障樹來構(gòu)造它的BDD，首先要為每個基本事件構(gòu)建BDD，然后解析連接基本事件的邏輯關(guān)系，將已有的BDD 進行連接形成新的組合BDD。這個過程可以用三元邏輯運算工具ite（If－Then－Else）來實現(xiàn)。

定義10 ite：若布爾變量x，y，z 滿足關(guān)系式：xy ＋，則定義映射法則ite 使

ite（If－Then－Else）是一個含有3 個布爾變量的操作，描述了布爾變量x 以兩種可能狀態(tài) （可以理解為事件的正常狀態(tài)和和故障狀態(tài)）傳遞給子節(jié)點y 和z。由于BDD 的基本依據(jù)是香農(nóng)分解原理，布爾函數(shù)的BDD 表示實質(zhì)就是一個三元組（xi；fxi＝0；fxi＝1）的遞歸表示，而香農(nóng)分解原理f＝xi·fxi＝1＋·fxi＝0又可寫成ite操作的形式，即可以將一個布爾函數(shù)描述為f ＝ite（xi；fxi＝0；fxi＝1），其中fxi＝0，fxi＝1可以繼續(xù)用ite 操作遞歸地分解下去，所以ite 操作也是BDD 的一個基本操作。若知道了兩個BDD 結(jié)構(gòu)，則可以通過下面兩個重要的ite連接規(guī)則來將某種邏輯操作下的兩個子BDD 連接起來。

定理1 ite 連接規(guī)則：設(shè)兩個子BDD 結(jié)構(gòu)分別為M＝ite（xi，A1，A2）和N ＝ite（xj，B1，B2），則

式中： “◇”——任意邏輯運算 （如 “且AND/或OR”）。運用該規(guī)則關(guān)鍵要判斷兩個子BDD 根節(jié)點的排序大小。

3.2 WSN 可靠性結(jié)構(gòu)BDD＿Faulttree算法

本文基于故障樹的WSN 可靠性結(jié)構(gòu)給出BDD＿Faulttree算法，以分層簇拓撲結(jié)構(gòu)下的WSN 可靠性為例分析。該算法分為兩步，首先用遞歸法實現(xiàn)WSN 可靠性結(jié)構(gòu)向BDD 的轉(zhuǎn)化，然后遍歷BDD 計算WSN 可靠度。本文利用Colorado大學(xué)的CUDD 軟件包［10］中ite 操作給出用遞歸方法實現(xiàn)構(gòu)建WSN 可靠性結(jié)構(gòu)的BDD 算法。此外，將故障樹轉(zhuǎn)換為BDD 之前，須對基本事件進行排序，本文采用的是深度優(yōu)先 （DFS）的方式搜索WSN 可靠性結(jié)構(gòu)來確定基本事件的順序。

基于遞歸法的BDD＿Faulttree算法是將基本事件用ite表示，形成一個基本事件的BDD 結(jié)構(gòu)，然后解析最低一層的邏輯門事件，并用ite 的連接規(guī)則將每一層邏輯門事件的BDD 結(jié)構(gòu)進行連接，以此類推，由下至上遞歸置換，最后可以得到WSN 可靠性結(jié)構(gòu)的BDD 結(jié)構(gòu)。

WSN 系統(tǒng)的BDD 結(jié)構(gòu)精確地描述了基本事件 （網(wǎng)絡(luò)節(jié)點的工作狀態(tài)）影響頂事件 （WSN 系統(tǒng)）的狀態(tài)及路徑。在BDD 中，頂事件的所有從根節(jié)點到葉子節(jié)點值為“1”，并且不包括葉節(jié)點的路徑就是故障樹的不交化割集（MCS）。用深度優(yōu)先搜索 （DFS）的方法可以找到所有的不交路徑，WSN 系統(tǒng)失效的發(fā)生概率就等于BDD 上所有的不交路徑之和。通過深度優(yōu)先 （DFS）搜索遍歷BDD 求WSN 系統(tǒng)的失效概率，應(yīng)用下述公式

在構(gòu)造好的BDD 結(jié)構(gòu)中會存在相同結(jié)構(gòu)的BDD 子圖，因此在遍歷BDD 的過程中，會在這些子圖上重復(fù)遍歷并計算可靠性，這樣會造成大量的冗余計算。為此在算法中應(yīng)用哈希表的結(jié)構(gòu)，把已計算好的下一層子節(jié)點上的失效概率值存儲在哈希表中，使算法的時間復(fù)雜度降為O（n），提高了算法的效率。

給定F－WSN 算法步驟如下：

（1）定義函數(shù)dfstraverse＿Faulttree深度遍歷故障樹確定作為基本事件的節(jié)點序列。

（2）根據(jù)節(jié)點的序列號從根節(jié)點開始，初始化故障樹每個節(jié)點FaultTree.node［i］的索引號 （作為在BDD 中的標記），子節(jié)點個數(shù)，操作邏輯，和構(gòu)建當(dāng)前節(jié)點的孩子節(jié)點隊列，若是葉子節(jié)點則標記其操作邏輯為－1，如果是非葉子節(jié)點則 “OR”操作標記為0， “AND”操作標記為1，定義函數(shù)buildFaultTree構(gòu)建WSN 的故障樹，最后返回故障樹根節(jié)點地址。

（3）從故障樹中獲取節(jié)點FaultTree.node［i］，定義函數(shù)BDD＿Faulttree為將故障樹轉(zhuǎn)換為BDD 結(jié)構(gòu)，判斷當(dāng)前節(jié)點是否是葉子節(jié)點，若是則利用CUDD 包中的Cudd＿bddIthVar函數(shù)構(gòu)造葉子節(jié)點的BDD 結(jié)構(gòu)并將該葉子節(jié)點的索引號CTree.node［i］.data一起存入所構(gòu)造的BDD 中，并返回BDD，否則繼續(xù)下一步操作。

（4）如果當(dāng)前節(jié)點FaultTree.node［i］操作邏輯為“OR”門，則跳轉(zhuǎn)到 （3），則繼續(xù)訪問該節(jié)點的子節(jié)點，將返回值存入集合set1，并用ite＿or操作：Cudd＿bddite將set1中的BDD 進行 “or”連接否則繼續(xù)下一步操作。

（5）若當(dāng)前節(jié)點操作邏輯為 “AND”門，則跳轉(zhuǎn)到（3），則繼續(xù)訪問該節(jié)點的子節(jié)點，將返回值存入集合set2，并用ite＿and操作：Cudd＿bddite將set2 中的BDD進行 “and”連接，否則繼續(xù)下一步操作。

（6）故障樹的BDD 的地址附給指針變量root，為BDD中節(jié)點構(gòu)造哈希表HashTable并初始化。

（7）定義計算節(jié)點失效率函數(shù)computeFailureRate，從root開始深度遍歷訪問節(jié)點，若當(dāng)前訪問的是葉子節(jié)點為左孩子，則返回1；如果葉子節(jié)點為右孩子，則返回0，如果為非葉子節(jié)點則繼續(xù)下一步。

（8）根據(jù)當(dāng)前節(jié)點的地址作為Key在哈希表中查找，若有記錄，則返回哈希表中當(dāng)前節(jié)點的失效概率，否則繼續(xù)下一步。

（9）根據(jù)下面的公式計算當(dāng)前節(jié)點兩個分支上的失效概率，然后用當(dāng)前節(jié)點的地址作為Key，將失效率存入哈希表中，并返回該節(jié)點失效概率。

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

偽碼如下：r

4 算法實例

下面以圖5所示的一個簡單例子，構(gòu)建對應(yīng)的BDD 結(jié)構(gòu)，并計算網(wǎng)絡(luò)失效概率。模型中的頂事件TOP 為WSN失效。分別給它們分配一個序列號：S1，S2，Gw，CH，S3，S4分別對應(yīng)于x1，x2，x3，x4，x5，x6。在 運 用 遞 歸 法 時，首 先選擇底事件的指標順序，假設(shè)所選用的順序是：x1＜x2＜x3＜x4＜x5＜x6，每一層的BDD 構(gòu)造過程如下：

圖5 WSN 可靠性的一般結(jié)構(gòu)

由頂事件的ite 結(jié)構(gòu)得到的BDD 結(jié)構(gòu)如圖6所示。

圖6 WSN 可靠性結(jié)構(gòu)對應(yīng)的BDD 結(jié)構(gòu)

深度遍歷BDD 結(jié)構(gòu)求不交化割集為頂事件的所有從根節(jié)點到葉子節(jié)點值為 “1”，不包括葉節(jié)點的路徑，路徑中經(jīng)過節(jié)點的0－分支，則記為，表示基本事件xi沒有發(fā)生，實例中的不交割集為：

頂事件WSN 的發(fā)生概率等于BDD 上所有的不交路徑之和，網(wǎng)絡(luò)失效概率計算如下，F(xiàn)xi為各個序列號對應(yīng)節(jié)點的失效概率

5 實驗及分析

定量分析分層簇型WSN 可靠性結(jié)構(gòu)上的可靠度，應(yīng)用上文介紹的BDD＿Faulttree算法假設(shè)WSN 有3 個簇，每個簇含有15個S，2個Gw 和1個CH，并假設(shè)節(jié)點間的通信路徑有一定的路由支持。簇形拓撲的特點在于節(jié)點間信息的傳播是多路徑的，從直觀上講，通信節(jié)點間不同路徑條數(shù)會影響網(wǎng)絡(luò)的可靠性，下面的實驗中各節(jié)點失效率λ 取在MTTF－2年，假設(shè)信息從S節(jié)點傳輸?shù)紺H，CH 到Gw，以及Gw到處在最高層簇的CH 這些過程中通信節(jié)點間都為兩跳，但原節(jié)點到目的節(jié)點間的可用路徑條數(shù)Op不同。Op分別為1條，2條，3條時的網(wǎng)絡(luò)失效情況如圖7所示。

圖7 節(jié)點間路徑數(shù)不同時WSN 失效率

圖7中，可用路徑越多網(wǎng)絡(luò)的失效概率就越小。增加節(jié)點之間的路徑數(shù)能夠有效地降低網(wǎng)絡(luò)的失效概率，因為路徑越少，一旦鏈路受阻，就不會有其它的路徑通往目的節(jié)點，而簇型網(wǎng)絡(luò)的Mesh結(jié)構(gòu)能提供多跳的冗余路徑，因此具有較高的容錯性。若路由節(jié)點失效或者是兩個節(jié)點之間的鏈路不可用，則網(wǎng)絡(luò)自動重新配置失效組件的路徑。由于重新配置路由時會增加節(jié)點能量和資源的消耗，從而使系統(tǒng)的開銷增加。

若給節(jié)點提供冗余，則選擇給不同類型的節(jié)點增設(shè)冗余對網(wǎng)絡(luò)的可靠性影響是不同的。實驗中選擇一類節(jié)點為其增設(shè)一個冗余設(shè)備 （1r），其它種類的節(jié)點不增設(shè)，對比網(wǎng)絡(luò)整體的失效情況，節(jié)點的平均失效時間仍為MTTF－2年，結(jié)果如圖8所示。

圖8中，在0 至1000h 內(nèi)，分別給S 節(jié)點，Gw 以及CH 增設(shè)一個冗余設(shè)備時，網(wǎng)絡(luò)的失效情況基本相同。在1000h到2500h之間，為CH 增設(shè)冗余設(shè)備時，WSN 網(wǎng)絡(luò)的失效概率要比另外兩個稍低一些。在2500h以后三者出現(xiàn)了明顯的區(qū)別，隨著時間的延長，給S節(jié)點增設(shè)冗余設(shè)備時網(wǎng)絡(luò)的失效概率和給CH 節(jié)點及Gw 節(jié)點增設(shè)冗余設(shè)

圖8 含有不同冗余節(jié)點的WSN 失效概率

備相差越來越大，最大的失效概率相差3倍以上。雖然給S節(jié)點增設(shè)冗余能夠大幅度地降低網(wǎng)絡(luò)的失效概率，但由于S節(jié)點數(shù)量較多，所以增加冗余設(shè)備的代價要比CH 和Gw要大。2500h以后，分別給Gw 和CH 增設(shè)冗余的網(wǎng)絡(luò)失效情況基本呈平行狀，給S節(jié)點增設(shè)冗余設(shè)備網(wǎng)絡(luò)的失效概率最低。

6 結(jié)束語

WSN 可靠性分析是WSN 網(wǎng)絡(luò)設(shè)計、部署、驗證和維護的一個重要環(huán)節(jié)。本文基于故障樹建立了WSN 可靠性結(jié)構(gòu)，形成對WSN 可靠性問題研究的整體框架的基礎(chǔ)模型。針對WSN 可靠性問題引入BDD 方法，將基于故障樹的可靠性結(jié)構(gòu)轉(zhuǎn)換為BDD 結(jié)構(gòu)，從而避免一般故障樹分析方法中存在不交化處理過程，進而形成一種新的WSN 可靠性問題研究的思路，文中還給出了利用以上思路計算WSN 應(yīng)用通信可靠性 （ACR）背景下分層簇型拓撲結(jié)構(gòu)WSN 可靠度的應(yīng)用。

［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）.［古天龍，徐周波.有序二叉決策圖及應(yīng)用 ［M］.北京：科學(xué)出版社，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.