基于故障樹的無線傳感器網(wǎng)絡(luò)可靠度符號(hào)計(jì)算

聶晨華，高 西，董榮勝

（桂林電子科技大學(xué) 廣西可信軟件重點(diǎn)實(shí)驗(yàn)室，廣西 桂林541004）

0 引 言

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

由于應(yīng)用不交和 （SDP）的方法在故障樹上計(jì)算系統(tǒng)可靠度，存在最小割集 （MCS）的不交化處理過程，該過程是一個(gè)NP－h(huán)ard問題。基于香農(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 計(jì)算WSN 的可靠度，優(yōu)化可靠度計(jì)算過程，降低WSN 可靠度計(jì)算的復(fù)雜性。以分層簇型網(wǎng)絡(luò)中可用路徑以及節(jié)點(diǎn)冗余下的應(yīng)用通信可靠性問題為例，給出其可靠性結(jié)構(gòu)，通過給出的算法轉(zhuǎn)換為BDD 結(jié)構(gòu)，并計(jì)算以上兩種情況下的WSN 可靠度。

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

1.1 WSN 拓?fù)淠Ｐ?/h3>

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

最基本的WSN 拓?fù)淠Ｐ褪怯靡粋€(gè)二元組表示的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖。

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

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

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

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

在研究與節(jié)點(diǎn)或邊有關(guān)的可靠性問題時(shí)，常把與節(jié)點(diǎn)和邊有關(guān)的可靠性屬性作為權(quán)值，用加權(quán)圖構(gòu)造具有可靠性屬性的模型。基于加權(quán)圖的可靠性屬性模型依托WSN 原有的拓?fù)浣Y(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)故障樹和動(dòng)態(tài)故障樹兩種類型，本文選擇靜態(tài)故障樹進(jìn)行建模。一般靜態(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ò)拓?fù)浣Y(jié)構(gòu)會(huì)對(duì)網(wǎng)絡(luò)的連通性和組織結(jié)構(gòu)產(chǎn)生影響。目前，作為典型的WSN 拓?fù)浣Y(jié)構(gòu)有星型，mesh型和簇型結(jié)構(gòu)［7］。研究網(wǎng)絡(luò)可靠性，在節(jié)點(diǎn)或邊上加入相應(yīng)的可靠性屬性，形成一個(gè)網(wǎng)絡(luò)靠性模型。本文從WSN 的拓?fù)浣Y(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é)點(diǎn)Node，Vnode＝（sink；CH1，…，CHi；Gw1，…，Gwj；S1，…，Sm），其中sink是匯聚節(jié)點(diǎn)，CH 是簇頭節(jié)點(diǎn)，Gw 是網(wǎng)關(guān)節(jié)點(diǎn)，S是普通傳感器節(jié)點(diǎn)Sensor nodes，下文中都用這些縮寫字母表示，且本文約定節(jié)點(diǎn)Node的狀態(tài)只有正常和失效兩種，并假設(shè)相鄰節(jié)點(diǎn)之間的鏈路是可靠的。

（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é)點(diǎn)Node的狀態(tài)構(gòu)成。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖3 WSN 分層簇型拓?fù)?/p>

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

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

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

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

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

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

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

3.1 二元決策圖 （BDD）

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

偽碼如下：r

4 算法實(shí)例

下面以圖5所示的一個(gè)簡單例子，構(gòu)建對(duì)應(yīng)的BDD 結(jié)構(gòu)，并計(jì)算網(wǎng)絡(luò)失效概率。模型中的頂事件TOP 為WSN失效。分別給它們分配一個(gè)序列號(hào)：S1，S2，Gw，CH，S3，S4分別對(duì)應(yīng)于x1，x2，x3，x4，x5，x6。在 運(yùn) 用 遞 歸 法 時(shí)，首 先選擇底事件的指標(biāo)順序，假設(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)對(duì)應(yīng)的BDD 結(jié)構(gòu)

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

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

5 實(shí)驗(yàn)及分析

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

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

圖7中，可用路徑越多網(wǎng)絡(luò)的失效概率就越小。增加節(jié)點(diǎn)之間的路徑數(shù)能夠有效地降低網(wǎng)絡(luò)的失效概率，因?yàn)槁窂皆缴伲坏╂溌肥茏瑁筒粫?huì)有其它的路徑通往目的節(jié)點(diǎn)，而簇型網(wǎng)絡(luò)的Mesh結(jié)構(gòu)能提供多跳的冗余路徑，因此具有較高的容錯(cuò)性。若路由節(jié)點(diǎn)失效或者是兩個(gè)節(jié)點(diǎn)之間的鏈路不可用，則網(wǎng)絡(luò)自動(dòng)重新配置失效組件的路徑。由于重新配置路由時(shí)會(huì)增加節(jié)點(diǎn)能量和資源的消耗，從而使系統(tǒng)的開銷增加。

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

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

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

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

6 結(jié)束語

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