一種分簇無線傳感網絡的節(jié)點自診斷算法

劉亞紅，劉 昊

(西安電子科技大學 理學院，陜西 西安710071)

無線傳感網絡是由部署在監(jiān)測區(qū)域內的大量依靠微型電池供電的傳感器節(jié)點構成，通過無線通信方式組成的多跳自組織網絡系統(tǒng)。其目的是協(xié)作地感知、采集和處理網絡覆蓋區(qū)域中感知對象的信息，并發(fā)送給觀察者［1］。為了提高網絡的性能以及延長傳感網絡的壽命，大多網絡都使用分簇協(xié)議［2］。然而網絡運行中，節(jié)點難免會出現各種故障。

無線傳感器網絡的節(jié)點故障類型通常分為兩類［3］:硬故障和軟故障。所謂硬故障，是指傳感器節(jié)點的某一模塊發(fā)生故障，以至不能與其節(jié)點通信;所謂軟故障，指傳感器節(jié)點雖然發(fā)生故障，但仍可繼續(xù)工作并與其他節(jié)點通信，但節(jié)點所感知或傳送的數據不正確。

本文主要針對節(jié)點軟故障的檢測且不考慮瞬時故障［4］，假設N個節(jié)點隨機部署在預設的區(qū)域內，并都具有相同的傳輸距離。定義p為本文的軟故障率。

節(jié)點信息的空間相似性最早被KrishnamachariB.and lyenga等人在［5－7］中提出，該文獻指出了相鄰節(jié)點之間可以利用信息相似性作比較來進行節(jié)點自診斷。文獻［8～9］提出節(jié)點狀態(tài)的判斷要在給定閾值的基礎上，通過多次比較鄰居節(jié)點的信息來確定自身的狀態(tài)。文獻［10～11］主要研究了給定閾值的大小對整個區(qū)域中利用相鄰節(jié)點之間的感應信息進行診斷的影響。算法仿真結果說明當閾值近似等于區(qū)域的節(jié)點度時，診斷效果最優(yōu)，然而當節(jié)點度較低時，診斷效果極據下降。文獻［12～14］提出了分簇節(jié)點自診斷算法，簇頭的選擇都是建立在各種方法的診斷或眾多輪篩選來確定，在保證正確的簇頭基礎上再分簇進行簇內診斷。然而很多網絡最初就是以滿足分簇協(xié)議來傳播信息的，所以故障出現要直接進行診斷。本文算法就是針對簇間診斷設計的，由于簇頭之間要進行通信，及形成簇間連通圖，利用鄰居簇頭節(jié)點的信息空間相似性進行節(jié)點自診斷，再以給定的閾值為判斷標準，本文引用［10］中的自診斷方法及閾值結論來診斷簇頭的狀態(tài)，然而在文獻［10］中網絡空間中可能會出現兩層內相鄰簇頭節(jié)點均出現故障的情況以及節(jié)點度較低的情況，該種情況通過其診斷算法難以保證診斷效果。所以本文引用診斷之后在對節(jié)點狀態(tài)檢驗進行二次調整，確保節(jié)點的準確性較高。

1 網絡故障診斷

1.1 通過鄰居節(jié)點比較診斷

無線傳感網絡中，節(jié)點的測量值都是空間相關的，即相鄰節(jié)點之間有著相似的信息值。根據這一性質，將引用到文中的簇頭節(jié)點診斷中，假設簇頭節(jié)點形成一個連通網絡G，將診斷簇頭節(jié)點通過相鄰簇頭節(jié)點之間的信息進行比較。本文列出符號定義如表1所示。

表1 相關定義

如表2所述，假設節(jié)點v1，v2，…，vj是vi的鄰居簇頭節(jié)點，比較vi與vj，如果滿足條件，則表示其兩信息相似，記為cij=0，其中cij的情況只有表2所示的4種。則繼續(xù)比較vi與其他鄰居節(jié)點的信息。記Ci為簇頭節(jié)點vi與鄰居節(jié)點所測的cij=0的個數，假如，則表示簇頭節(jié)點vi的狀態(tài)正常，記為Fi=0。

表2 信息比較結果

對所有di≥θ的簇頭節(jié)點按上述方法診斷出狀態(tài)，然后判斷得出的狀態(tài)與簇頭節(jié)點之間的cij值是否吻合。如簇頭節(jié)點vi的狀態(tài)根據上述方法診斷出正常，簇頭節(jié)點vj被診斷出故障，而其的cij=0，則表示實際中信息相似，而狀態(tài)診斷卻不同，因此不吻合。出現這種情況算法中將引用第二步檢驗，如果節(jié)點vi的狀態(tài)與cij的值不吻合個數大于鄰居節(jié)點個數的1/2，則將改變節(jié)點vi的狀態(tài)為相反狀態(tài)。

1.2 算法描述

文獻［10］中的算法如表3所示，此算法主要是解決大面積區(qū)域且節(jié)點部署密集的情況，由于分簇網絡中首先要診斷簇頭節(jié)點確保簇頭節(jié)點的診斷精度高，簇頭連通圖中節(jié)點個數少，區(qū)域的節(jié)點度低。故用此算法對于簇頭間的診斷效果較低。而本文提出算法診斷簇頭節(jié)點效果較好。

表3 原算法

文中算法描述如下:

步驟1對每個被檢測簇頭節(jié)點vi，生成該簇頭節(jié)點的鄰簇簇頭節(jié)點集N(vi)，求出簇頭節(jié)點di以及簇頭節(jié)點構成連通圖的d，初始化Fi=0，初始化θ。

2 仿真算例

2.1 數值例子

本文通過Matlab隨機形成一個分簇網絡如圖1所示，作為特例來說明本算法。

圖1 分簇網絡

簇頭節(jié)點圖放大圖如圖2所示。

圖2 簇頭連通圖

假設實際故障節(jié)點為5、16、17、18、20。根據本文算法，首先假設20個節(jié)點初步為正常狀態(tài)，并求出平均節(jié)點度3.7，直接令θ=［d］=3，然后根據算法步驟2～步驟3，可初步診斷出節(jié)點F1=2，F2=0，F3=0，F4=0，F5=1，F6=1，F8=0，F9=0，F10=0，F11=0，F12=0，F14=0，F15=1，F16=1，F17=0，F18=1，F20=1。

初步診斷得到的節(jié)點重新構成新的連通子圖如圖3所示。

圖3 二步診斷圖

便于理解，在圖中用T來表示Ft=0，F來表示Ft=1。根據步驟5可知，節(jié)點17與鄰居節(jié)點經檢驗共有3個信息不匹配，所以節(jié)點17的最終狀態(tài)由正常變?yōu)楣收螰17=1，同理可得F1=0，F2=0，F3=0，F4=0，F5=1，F8=0，F9=0，F10=0，F11=0，F14=0，F15=0，F16=1，F17=1，F20=1。根據步驟6由于F8=0，且C8，6=0，所以可知F6=0，同理可得F12=0，F18=1;在返回到原圖G中，由于C11，13=0，且F11=0，根據步驟7可得F13=1，同理可依次得出F7=0，F19=0。

通過以上數值舉例分析可看出，本文算法解決了節(jié)點誤診斷錯誤的情況，且可解決當閾值取低節(jié)點度時，診斷率依然能夠保持較高，比較結果如圖4和圖5所示。

2.2 仿真結果

2.2.1 簇頭節(jié)點診斷結果

通過Matlab對上述比例的簇頭節(jié)點(20個)按診斷算法與故障診斷原算法［14］分別在節(jié)點故障率p為0.05，0.10，0.15，0.20，0.25，0.30，0.35下進行20次仿真得到的診斷精確率，如圖4和圖5所示。如圖4在對其故障診斷精確率和原算法的診斷率進行比較時得到故障率為0.35時，新算法仍能保持83.35%的診斷精度，而原算法診斷精度卻為75%。

圖4 故障診斷率比較結果

圖5 故障虛警率比較結果

2.2.2 整個區(qū)域節(jié)點診斷結果

由于此算法是建立在簇頭的連通圖上，簇頭被準確診斷后，再延伸到簇內，根據簇頭節(jié)點與簇內節(jié)點之間的相似值來診斷簇內節(jié)點。通過Matlab對其算法進行仿真，在簇頭通信半徑為30，簇內通信半徑為20的情況下，分別在節(jié)點故障率p為0.05，0.10，0.15，0.20，0.25，0.30，0.35下對算法分別執(zhí)行20次后得到的故障診斷精度和故障虛警率如圖6所示。由此可看出此算法延伸到整個區(qū)域的準確性較高。

圖6 整個網絡的故障診斷效果圖

3 結束語

對于分簇傳感網絡來說，簇頭節(jié)點數目通常較少，而現有研究未能提供一個合理的算法使簇頭節(jié)點有較高的診斷精度。文中提出了基于分簇節(jié)點自診斷無線傳感網絡故障診斷的算法，此算法能夠精確診斷出簇頭節(jié)點狀態(tài)。同時，由于簇頭節(jié)點得到了精確的診斷，簇內診斷的精確率便得到保障。仿真結果顯示整個網絡的診斷效果良好。但本文仍然存在一些問題，例如簇頭節(jié)點大面積出現故障的情況下，診斷精度急速下降，這將是今后研究的重點。

［1］ZHU Chunsheng，SHU Lei，TAKAHIRO H，et al.A survey on communication and data management issues in mobile sensor networks［J］.Wireless Cmmunications and Mobile Computing Wiley，2011，21(3):110－114.

［2］ 沈波，張世永，鐘亦平.無線傳感器網絡分簇路由協(xié)議［J］.Journal of Software，2006，17(7):1588－1600.

［3］CHESSA S，SANTI P.Comparison based system level fault di－agnosis in ad hoc networks［C］.New Orleans:Proc.of IEEE 20th Symp.on Reliable Disrributed Systems(SRDS)，2001:257－266.

［4］CAO Donglei，CAO Jiannong，JIN Beihong.A fault tolerrant algorithm for event region detection in wireless sensor networks［J］.Chinese Journal of Computers，2007，30(10):1770－1776.

［5］KRISHNAMACHARI B，LYENGAR S.Distributed bayesian algorithms for fault－tolerant event region detection in wireless sensor networks［J］.IEEE Transsactions on Computers，2004，53(3):241－250.

［6］CHEN Qinggchun，LAM K Y，FAN Pingzhi.Comments on distributed bayesian algorithms for eault－tolerant event region detection in wireless sensor networks［J］.IEEE Transactions on Computers，2005，55(1):58－70.

［7］LUO X，FAN DONG M，HUANG Y.On distributed faulttolerant detection in wireless sensor networks［J］.IEEE Transactions on Computers，2006，55(1):58－70.

［8］CHEN J R，SHUBNA K，ARUN S.Distributed fault detection of wireless sensor networks［C］.Losangeles，CA，USA:In Proceedings of the International Conference on Mobile Computing and Networkings，2006:65－72.

［9］JIANG P.A new method for node fault detection in wireless sensor networks［J］.Sensors，2009，9(2):1282－1294.

［10］MYEONG H L，YOON H C.Fault detection of wireless sensor networks［J］.Computer Communications，2008，31(14):3469－3475.

［11］季賽，袁慎芳，李含光.WSN中故障診斷性能與平均節(jié)點度研究［J］.計算機工程，2010，36(7):14－16.

［12］WANG Zhaoxing，WEN Qiaoyan，ZHANG Yisunhua.A fault detection scheme based on self－clustering nodes sets for wireless sensor networks［C］.IEEE 12th International Conference on Computer and Information Technology，2012.

［13］LIU Wenjun，ZHANG Shukui，FAN Jianxi.A diagnosisbased clustering and multipath routing protocol for wireless sensor networks［C］.International Journal of Distributed Sensor Networks Volume，2012.

［14］劉凱，彭力.一種改進分簇式無線傳感網器絡節(jié)點故障診斷算法研究［J］.傳感器與微生態(tài)，2011(4):37－40.