劉亞紅，劉 昊

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

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

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

本文主要針對(duì)節(jié)點(diǎn)軟故障的檢測(cè)且不考慮瞬時(shí)故障［4］，假設(shè)N個(gè)節(jié)點(diǎn)隨機(jī)部署在預(yù)設(shè)的區(qū)域內(nèi)，并都具有相同的傳輸距離。定義p為本文的軟故障率。

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

1 網(wǎng)絡(luò)故障診斷

1.1 通過(guò)鄰居節(jié)點(diǎn)比較診斷

無(wú)線傳感網(wǎng)絡(luò)中，節(jié)點(diǎn)的測(cè)量值都是空間相關(guān)的，即相鄰節(jié)點(diǎn)之間有著相似的信息值。根據(jù)這一性質(zhì)，將引用到文中的簇頭節(jié)點(diǎn)診斷中，假設(shè)簇頭節(jié)點(diǎn)形成一個(gè)連通網(wǎng)絡(luò)G，將診斷簇頭節(jié)點(diǎn)通過(guò)相鄰簇頭節(jié)點(diǎn)之間的信息進(jìn)行比較。本文列出符號(hào)定義如表1所示。

表1 相關(guān)定義

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

表2 信息比較結(jié)果

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

1.2 算法描述

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

表3 原算法

文中算法描述如下:

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

2 仿真算例

2.1 數(shù)值例子

本文通過(guò)Matlab隨機(jī)形成一個(gè)分簇網(wǎng)絡(luò)如圖1所示，作為特例來(lái)說(shuō)明本算法。

圖1 分簇網(wǎng)絡(luò)

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

圖2 簇頭連通圖

假設(shè)實(shí)際故障節(jié)點(diǎn)為5、16、17、18、20。根據(jù)本文算法，首先假設(shè)20個(gè)節(jié)點(diǎn)初步為正常狀態(tài)，并求出平均節(jié)點(diǎn)度3.7，直接令θ=［d］=3，然后根據(jù)算法步驟2～步驟3，可初步診斷出節(jié)點(diǎn)F1=2，F(xiàn)2=0，F(xiàn)3=0，F(xiàn)4=0，F(xiàn)5=1，F(xiàn)6=1，F(xiàn)8=0，F(xiàn)9=0，F(xiàn)10=0，F(xiàn)11=0，F(xiàn)12=0，F(xiàn)14=0，F(xiàn)15=1，F(xiàn)16=1，F(xiàn)17=0，F(xiàn)18=1，F(xiàn)20=1。

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

圖3 二步診斷圖

便于理解，在圖中用T來(lái)表示Ft=0，F(xiàn)來(lái)表示Ft=1。根據(jù)步驟5可知，節(jié)點(diǎn)17與鄰居節(jié)點(diǎn)經(jīng)檢驗(yàn)共有3個(gè)信息不匹配，所以節(jié)點(diǎn)17的最終狀態(tài)由正常變?yōu)楣收螰17=1，同理可得F1=0，F(xiàn)2=0，F(xiàn)3=0，F(xiàn)4=0，F(xiàn)5=1，F(xiàn)8=0，F(xiàn)9=0，F(xiàn)10=0，F(xiàn)11=0，F(xiàn)14=0，F(xiàn)15=0，F(xiàn)16=1，F(xiàn)17=1，F(xiàn)20=1。根據(jù)步驟6由于F8=0，且C8，6=0，所以可知F6=0，同理可得F12=0，F(xiàn)18=1;在返回到原圖G中，由于C11，13=0，且F11=0，根據(jù)步驟7可得F13=1，同理可依次得出F7=0，F(xiàn)19=0。

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

2.2 仿真結(jié)果

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

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

圖4 故障診斷率比較結(jié)果

圖5 故障虛警率比較結(jié)果

2.2.2 整個(gè)區(qū)域節(jié)點(diǎn)診斷結(jié)果

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

圖6 整個(gè)網(wǎng)絡(luò)的故障診斷效果圖

3 結(jié)束語(yǔ)

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

［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］ 沈波，張世永，鐘亦平.無(wú)線傳感器網(wǎng)絡(luò)分簇路由協(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，F(xiàn)AN 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，F(xiàn)AN 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é)點(diǎn)度研究［J］.計(jì)算機(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，F(xiàn)AN Jianxi.A diagnosisbased clustering and multipath routing protocol for wireless sensor networks［C］.International Journal of Distributed Sensor Networks Volume，2012.

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