可修復節點無線傳感器網絡可靠性符號計算

聶晨華，高 西，董榮勝

（桂林電子科技大學 廣西可信軟件重點實驗室，廣西 桂林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 可靠性，其中對可修復節點建立容錯動態邏輯門模型。該容錯節點模型是一種具有可修復屬性以及在硬件水平上具有冗余屬性的模型?；隈R爾科夫隨機過程，評估該種容錯可修復節點模型下的可靠性。針對簇型WSN應 用 通 信 可 靠 性 （application communication reliability，ACR）［12］問題，將給出的容錯可修復傳感器節點模型應用在該簇型WSN 可靠性結構上，以便計算WSN 可靠度?；诠收蠘涞腤SN 可靠性結構應用不交和 （SDP）的方法在故障樹上計算系統可靠度，存在最小割集 （MCS）的不交化處理過程，該過程是一個NP－hard問題?；谙戕r分解的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）可修復熱貯備節點模型及其可靠性

單個的可修復節點是最簡單的可修系統，文中假設單個傳感器節點的失效率為λ，它以修復率μ 被修復?？捎枚仁强尚尴到y最重要的性能指標之一，可用度A（t）指系統在任意時刻t可以使用的概率。對于不可修復的系統則有A（t）＝R（t）。如果失效率λ和修復率μ 都是恒定的，且節點的壽命符合指數分布時，那么A（t）可以由下面的公式得到

在不可修復節點的基礎上實現可修復的節點可以用一個熱貯備系統?？尚迯蜔豳A備節點的模型表示和圖1 （a）的HSP相同，區別在于Ai是可修復的，修復率為μ，系統的狀態變換可以用如圖3 所示的馬兒科夫鏈過程來表示。圖3中顯示了具有一個冗余備份的可修復熱貯備節點的狀態轉換過程。

圖3 可修熱貯備狀態轉移的馬爾可夫鏈

根據狀態轉移可以寫出轉移率矩陣

設Pj（t）處于狀態j的概率 （j＝0，1，2），且初始狀態為P0（0）＝1，P1（0）＝P2（0）＝0，滿足微分方程組

（2）可修復冷貯備節點模型及其可靠性

在不可修復節點的基礎上實現可修復節點也可以用一個冷貯備系統?？尚蘩滟A備節點模型在動態故障樹中的用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表示與邊有關的權的函數?；诩訖鄨D的可靠性屬性模型依托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.