基于聚類中值比較的WSNs故障檢測算法*

張 成

(北京交通大學(xué) 電子信息工程學(xué)院,北京 100044)

基于聚類中值比較的WSNs故障檢測算法*

張 成

(北京交通大學(xué) 電子信息工程學(xué)院,北京 100044)

無線傳感器網(wǎng)絡(luò)(WSNs)中的傳感器件容易失效而導(dǎo)致測量數(shù)據(jù)不準(zhǔn)確，因而，高效、實用的故障檢測算法對于保證WSNs的感知質(zhì)量非常重要。提出一種基于聚類中值比較(CBMC)的故障檢測算法。不同于傳統(tǒng)的中值比較的思想，該算法引入聚類方法對待檢測節(jié)點的鄰居節(jié)點測量數(shù)據(jù)進(jìn)行分組，根據(jù)分組信息計算該節(jié)點狀態(tài)。仿真實驗表明:CBMC算法具有較高的故障檢測率(DR)和較低的故障誤檢率(FPR)。

無線傳感器網(wǎng)絡(luò)； 聚類中值比較； 故障診斷； 故障檢測； 故障容錯

0 引 言

最近幾年，隨著無線傳感器網(wǎng)絡(luò)(WSNs)研究的深入，故障檢測和容錯逐漸成為研究熱點[1～13]。Ruiz L B等人提出一個基于事件驅(qū)動的故障管理框架MANNA[1]。該框架是第一個比較完整的WSNs管理解決方案，詳細(xì)分析WSNs故障管理的需求、目標(biāo)、體系結(jié)構(gòu)等,但是該框架采用集中式管理方式，能量消耗較大,對于能量有限的WSNs，該方案存在較大局限。Chessas S和Santi P在研究了Ad Hoc網(wǎng)絡(luò)故障診斷[2]的基礎(chǔ)上，提出了基于WSNDiag協(xié)議的故障定位算法[3]。這種方法可以很好地解決WSNs崩潰故障的診斷，但對于非崩潰型故障是不適用的，特別是對于傳感器件的故障，適用性較差。Krishnamachari B等人基于WSNs測量的空間連續(xù)性假設(shè)和節(jié)點故障的獨立性假設(shè)[4]，提出了隨機(jī)決策算法、門限決策算法和最優(yōu)門限決策算法(optimal threshold detection scheme，OTDS)等3種檢測算法[5]。其中，故障檢測效果最好的OTDS在本質(zhì)上是一種多數(shù)表決策略。 Luo X W等人對上述方法做了進(jìn)一步分析和改進(jìn)，考慮如何解決噪音環(huán)境下測量錯誤和傳感器故障并發(fā)狀況下的故障檢測問題，并提出確定最佳鄰居數(shù)目的算法[6]。Ding M等人提出了本地診斷算法[7]，采用中值策略，通過鄰居節(jié)點的讀數(shù)來校驗節(jié)點的狀態(tài)。這種方法的特點是節(jié)省能耗、分布式本地檢測，但算法的檢測性能還需要進(jìn)一步提高。Tian Q J等人和高建良等人各自獨立地提出了基于加權(quán)中值的故障檢測算法[8，9](weighted fault median detection scheme，WFMDS)。該算法在中值故障檢測算法的基礎(chǔ)上，降低疑似故障節(jié)點的分析權(quán)重，改進(jìn)了檢測效果。

本文提出一種基于聚類中值比較(clusting-based medium comparison,CBMC)的故障檢測算法。該算法的創(chuàng)新性在于提出基于聚類的節(jié)點測量數(shù)據(jù)的組織方法，并根據(jù)聚類結(jié)果產(chǎn)生的組與組數(shù)確定節(jié)點的狀態(tài)。基于聚類的非監(jiān)督分類方法降低了故障檢測策略對異常數(shù)值和數(shù)據(jù)偏度的敏感度，這在很大程度上提高了故障檢測性能。

1 WSNs模型

WSNs中可能發(fā)生的故障有多種，按故障發(fā)生范圍，可分為器件級、節(jié)點級、網(wǎng)絡(luò)級故障[10,11]。后兩類故障常導(dǎo)致節(jié)點間無法正常通信，可通過拓?fù)渌惴ê吐酚伤惴òl(fā)現(xiàn)，因此,本文不考慮這兩類故障。在WSNs組成部件中，計算、存儲、通信、電池等器件的故障檢測和容錯技術(shù)相對比較成熟，故障概率相對較小，而對于直接暴露于外界環(huán)境負(fù)責(zé)感知測量的低成本的傳感器件則更容易出錯。傳感器件處于故障狀態(tài)時，通常表現(xiàn)為測量數(shù)據(jù)錯誤或偏移,這使WSNs監(jiān)測結(jié)果出現(xiàn)重大偏差，甚至無法使用。本文以傳感器件故障作為研究對象。

采用圖G=(V，E)作為WSNs模型，其中,V為所有節(jié)點集合，E由節(jié)點間距離在節(jié)點通信范圍內(nèi)的可相互通信的節(jié)點對組成。設(shè)WSNs所有節(jié)點具有相同的通信半徑，節(jié)點狀態(tài)可分為正常態(tài)和故障態(tài)。當(dāng)節(jié)點故障時，相比于正常時測量值會偏高或偏低。

為簡化研究，忽略無關(guān)細(xì)節(jié)，采用與現(xiàn)有研究類似的假設(shè)前提：WSNs密集部署，處于事件區(qū)域邊界的節(jié)點可忽略；監(jiān)測對象的測量值具有空間連續(xù)性，節(jié)點與鄰居節(jié)點在正常態(tài)時具有近似測量值[4]；各節(jié)點傳感故障的發(fā)生具有獨立性；節(jié)點處于故障態(tài)時感知的測量值比其處于正常態(tài)時偏高或偏低，其差異明顯可區(qū)分。

2 WSNs故障檢測算法

2.1 問題定義

設(shè)WSNs中任一節(jié)點vi，其感知區(qū)域的真實值為γi，節(jié)點的測量值為M(vi)，節(jié)點故障概率為pi，求節(jié)點狀態(tài)判決函數(shù)D(vi)。理想的D(vi)函數(shù)，在vi處于正常態(tài)時返回True，在vi處于故障態(tài)時返回False。設(shè)與vi在通信距離內(nèi)的可相互通信的所有節(jié)點為鄰居節(jié)點，用N(vi)表示，N(vi)={vj|(vi,vj)∈E}。鄰居節(jié)點數(shù)量|N(vi)| 用n表示。N(vi)構(gòu)成vi所在的“社區(qū)”。設(shè)鄰居節(jié)點vj∈N(vi)，1≤j≤n的真實值為γij，節(jié)點測量值M(vj)=xij。對于所有vj∈N(vi)，M(vj)組成節(jié)點vi的社區(qū)測量值，用C(vi)表示。C(vi)={M(vj)|?vj∈N)vi)}={xi1,xi2,…,xin}，其中設(shè)xi1,xi2,…,xin為n個鄰居節(jié)點讀數(shù)按照從低到高升序排列。

為節(jié)省能量，WSNs采用本地判決策略，基本原理是：在密集部署的WSNs中，目標(biāo)節(jié)點所感知區(qū)域的真實值與其各個鄰居節(jié)點的測量值相近,因此,可由節(jié)點所在社區(qū)的狀態(tài)近似確定節(jié)點狀態(tài)。通過一定策略和算法，分析目標(biāo)節(jié)點vi的所有鄰居N(vi)的測量值C(vi)，從而形成目標(biāo)節(jié)點所在區(qū)域測量值的社區(qū)參考值R(vi)。注意，社區(qū)測量值C(vi)是一組值，社區(qū)參考值R(vi)是一個值。根據(jù)C(vi)計算R(vi)時采用的策略通常包括均值策略、中值策略、加權(quán)中值策略、多數(shù)表決策略等。

2.2 CBMC算法

CBMC算法基本思想如下：目標(biāo)節(jié)點vi通過將自身測量值M(vi)與其社區(qū)參考值R(vi)進(jìn)行比較，以獲取對自身測量值是否準(zhǔn)確的判斷，進(jìn)而確定節(jié)點自身狀態(tài)是否正常。如果兩者差異在某一門限α之內(nèi)，則認(rèn)為目標(biāo)節(jié)點vi狀態(tài)正常。與傳統(tǒng)的均值檢測、中值檢測、多數(shù)表決等策略不同，本文提出一種新的CBMC的檢測策略。通過聚類算法對社區(qū)測量值M(vi)分析后產(chǎn)生m組數(shù)據(jù)(異常值或高或低于正常值，因而,1≤m≤3)，需要從中尋找可以代表正常狀態(tài)的組，取其均值用以計算R(vi)。

CBMC算法的輸入包括：WSNs的模型G=(V，E)、待檢測節(jié)點vi、節(jié)點狀態(tài)差異門限α;算法輸出為D(vi)=TrueorFalse。

CBMC算法具體步驟如下：

1)在WSNs中，任選一待檢測節(jié)點vi，獲得測量值為M(vi)，鄰居節(jié)點測量值的集合為C(vi)。

2)采用聚類算法Cluster(M(vi))，進(jìn)行分組，形成由低到高的S1,S2,…,Sm等m個組，1≤m≤3。

對m的數(shù)值進(jìn)行判斷：

m=1：R(vi)=mean(Sm)；∥mean取中值;

m=2：將M(vi)按順序插入C(vi)，重新調(diào)用聚類算法Cluster(M(vi))分組，形成由低到高的S1,S2,…,Sm′等m′個組，1≤m′≤3。

①若m′為1，則R(i)=mean(Sm′)；

②若m′為2，并且|Sm′/2|>|S(m′/2+1)|, 則R(i)=mean(Sm′/2);否則,R(i)=mean(S(m′/2+1));

③若m′為3，則R(i)=mean(S(m′+1)/2),m=3:R(i)=mean(S(m+1)/2).

3)節(jié)點狀態(tài)判斷：通過節(jié)點vi將自身測量值M(vi)與R(vi)比較來求解D(vi)：如果|M(vi)-R(vi)|/M(vi)≤α，則D(vi)=Ture，vi為正常節(jié)點；否則,D(vi)=False，vi為故障節(jié)點。

Cluster(M(vi))算法描述如下：

1)將M(vi)中的數(shù)據(jù)從低到高排序，不妨設(shè)順序為：xi1,xi2,…,xin；

2)設(shè)θj=(xi,(j+1)-xij)/xij，根據(jù)斜率θj的高低判斷數(shù)據(jù)分組，得到θ1,θ2,…,θn-1。

3)從θ1到θn-1遍歷，如果θj≥α，則θj為組邊界節(jié)點(新組的開始)。按照組邊界節(jié)點的劃分形成分組S1,S2,…,Sm。

4)如果m>3，則α=1.1α，跳轉(zhuǎn)至步驟(3)；

5)輸出分組信息：S1,S2,…,Sm。

在聚類算法Cluster(M(vi))的第4步中，由于已經(jīng)分析得出1≤m≤3,如果出現(xiàn)m>3，說明算法中的α門限值設(shè)置過低，有必要進(jìn)行少量上調(diào)，可以設(shè)置為1.1α。Cluster(M(vi))輸出的不同的組數(shù)m代表的意義不同：當(dāng)m=1，則這一組數(shù)據(jù)可能都是正常的，或偏高故障的，或偏低故障的；當(dāng)m=2，則這2組的數(shù)目可能是正常+偏高，或正常+偏低,或偏高+偏低；當(dāng)m=3，則這些數(shù)據(jù)中包括正常、偏高、偏低各種情況，而居中的那組數(shù)據(jù)很可能是正常數(shù)據(jù)。

2.3 參數(shù)分析

CBMC算法中涉及節(jié)點狀態(tài)差異門限 。該參數(shù)是用來區(qū)分正常態(tài)下的測量值與故障態(tài)下的測量值(包括故障態(tài)偏高測量值和故障態(tài)偏低測量值)。該值過大與過小都會對算法造成影響，過大，則無法區(qū)分正常態(tài)下的測量值與故障態(tài)下的測量值;過小，則可能造成誤判，即把同處正常態(tài)(或故障態(tài))的測量值，錯誤地分開。

設(shè)正常態(tài)、故障態(tài)偏高、故障態(tài)偏低等情況的測量值分別為隨機(jī)變量ηn,ηh,ηl，則

Δαhn=(min(ηh)-max(ηn))/max(ηn)，

Δαnl=(min(ηn)-max(ηl))/min(ηn)，

Δαh=(max(ηh)-min(ηh))/min(ηh)，

Δαn=(max(ηn)-min(ηn))/min(ηn)，

Δαl=(max(ηl)-min(ηl))/min(ηl),

于是有

max(Δαn,Δαh,Δαl)≤α≤min(Δαhn,Δαnl).

(1)

理想的α應(yīng)滿足式(1)。在應(yīng)用中，考慮到隨機(jī)變量中ηn,ηh,ηl可能存在某些小概率極端值，可能沒有滿足式(1)的解。因此,在進(jìn)行max，min運算時，必要時需要對隨機(jī)變量ηn,ηh,ηl的取樣進(jìn)行處理，以避免極端值的影響，即剔除發(fā)生概率非常小的極端樣本。在本文的仿真實驗中，α設(shè)為0.4。

2.4 能耗分析

由于WSNs的主要能耗來自于通信開銷，因而主要分析算法的通信開銷。對于社區(qū)測量值C(vi)的監(jiān)聽，采用共享的廣播信道，CBMC與OTDS,WMFDS算法等一樣，都需要接收社區(qū)測量值的通信開銷，開銷沒有區(qū)別。

然而在實際部署時，沒有必要實時地每次都去獲取臨近節(jié)點的節(jié)點狀態(tài)。鄰居節(jié)點之間節(jié)點狀態(tài)消息的傳送頻率，與節(jié)點故障發(fā)生的速率有關(guān)，即節(jié)點經(jīng)過多久才會發(fā)生故障。考慮到可以每隔一段時間節(jié)點依次交替地傳送最新的節(jié)點狀態(tài)，所以,CBMC算法的額外通信開銷是很小的。

3 仿真結(jié)果和分析

3.1 仿真實驗

為了驗證和比較CBMC算法的性能，采用文獻(xiàn)[12]的實驗環(huán)境和參數(shù)并通過Matlab加以實現(xiàn)。該實驗環(huán)境具體包括如下2個模塊：1)WSN—DEPLOY—NODE模塊:輸入?yún)?shù)為節(jié)點個數(shù)、部署類型(隨機(jī)部署或網(wǎng)格部署)、檢測區(qū)域、節(jié)點故障率。該模塊根據(jù)節(jié)點故障概率隨機(jī)生成故障節(jié)點；包括正常節(jié)點和故障節(jié)點的所有節(jié)點，周期性進(jìn)行環(huán)境監(jiān)測，所得讀數(shù)設(shè)置到節(jié)點讀數(shù)屬性。設(shè)節(jié)點vi所在區(qū)域的真實值為γi=100，當(dāng)節(jié)點處于正常狀態(tài)時，其測量值為M(vi)=γi+εn，當(dāng)節(jié)點處于測量值偏高的故障狀態(tài)時，設(shè)其測量值為M(vi)=γ+Δ+εh；當(dāng)節(jié)點處于測量值偏低的故障狀態(tài)時，設(shè)其測量值為M(vi)=γi-Δ+εl。其中，Δ=50，εn,εh,εl分別服從正態(tài)分布N(μ,δ)的測量噪聲μ=0，δ=20。實驗中WSNs節(jié)點數(shù)為32×32=1 024，采用網(wǎng)格方式部署。2)WSN—FIND—FAUT模塊:支持的算法包括MFDS基于中值的故障檢測算法、WMFDS基于加權(quán)中值的故障檢測算法、MEAN基于均值的故障檢測算法、OTDS基于多數(shù)表決的故障檢測算法、基于CBMC的故障檢測算法。

設(shè)WSNsG=(V,E)中，正常態(tài)節(jié)點的集合為VN，故障節(jié)點的集合VF，引入如下度量指標(biāo)：

1)節(jié)點故障檢測率(detection rate，DR)

2)節(jié)點故障誤檢率(false positive rate，F(xiàn)PR)

3.2 結(jié)果分析

下面給出WSNs通信半徑r=1.5(鄰居節(jié)點為4個節(jié)點的場景一)和r=2(鄰居節(jié)點為8個節(jié)點的場景二)兩類場景下的仿真結(jié)果。

場景一下的DR如圖1所示。CBMC算法的DR要高于OTDS算法，低于MEAN，MFDS,WMFDS算法。FPR如圖2所示,CBMC算法的FPR要明顯低于MFDS，WMFDS，MEAN，OTDS算法。可見在場景一下，CBMC算法具有較高的DR和相當(dāng)?shù)偷腇PR。當(dāng)DR達(dá)到一定程度后，F(xiàn)PR就格外重要，因而，CBMC算法具有明顯優(yōu)越性。這在一定程度上說明了基于聚類數(shù)據(jù)分組的故障檢測策略的有效性。

圖1 4個鄰居節(jié)點的DRsFig 1 DRs in 4-neighbour nodes

圖2 4個鄰居節(jié)點的FPRsFig 2 FPRs in 4-neighbour nodes

場景二下的DR如圖3所示。CBMC算法的DR要明顯優(yōu)于OTDS，MEAN，MFDS算法，在節(jié)點故障率為15 %～35 %時，CBMC算法的性能與WMFDS算法略低或基本相當(dāng)。在節(jié)點DR超過35 %時，CBMC算法的DR則要明顯優(yōu)于WMFDS算法。FPR如圖4所示。CBMC算法的FPR要明顯低于MFDS,WMFDS,MEAN,OTDS算法。CBMC算法在鄰居節(jié)點增多的情況下，表現(xiàn)出更好的故障檢測性能。較多的鄰居節(jié)點雖然可以增大故障的檢測效果，卻是以增加通信開銷和能耗為代價的。具體應(yīng)用時，需綜合考慮檢測性能與能耗，選擇合適的鄰居數(shù)目。

圖3 8個鄰居節(jié)點的DRsFig 3 DRs in 8-neighbour nodes

圖4 8個鄰居節(jié)點的FPRsFig 4 FPRs in 8-neighbour nodes

4 結(jié) 論

本文提出一種新的WSNs故障檢測的CBMC算法。該算法采用聚類的非監(jiān)督式分組機(jī)制，可以有效劃分和聚合測量數(shù)據(jù)，進(jìn)而評估節(jié)點所處狀態(tài)。該機(jī)制可以顯著提高算法性能，即使在節(jié)點故障概率較大的情況下，算法也具有非常理想的DR和FPR。WSNs實際部署環(huán)境中，故障的發(fā)生具有多樣性和復(fù)雜性。

[1] Ruiz L B,Nogueira J M,Loureiro A A F.MANNA:A management architecture for wireless sensor networks[J].IEEE Communications Magazine,2003,41(2):116-125.

[2] Chessas S,Santi P.Comparison-based system-level fault diagnosis in Ad Hoc networks[C]∥The 20th Symposium on Reliable Distributed Systems(SRDS),New Orleans,USA,2001:257-266.

[3] Chessas S,Santi P.Crash faults identification in wireless sensor networks[J].Computer Communications,2002,25(14):1273-1282.

[4] Vuran M C,Akan O B,Akyildiz I F.Spatio-temporal correlation:Theory and application for wireless sensor networks[J].The International Journal of Computer and Telecommunications Networking,2004,45(3):245-259.

[5] Krishnamachari B,Iyengar S.Distributed Bayesian algorithms for fault-tolerant event region detection in wireless sensor network-s[J].IEEE Transactions on Computers,2004,53(3):241-250.

[6] Luo X W,Dong M,Huang Y L.On distributed fault-tolerant detection in wireless sensor networks[J].IEEE Transactions on Computers,2006,55(1):58-70.

[7] Ding M,Chen D,Xing K,et al.Localized fault-tolerant event boundary detection in sensor networks[C]∥IEEE INFOCOM 2005,Miami,USA,2005:902-913.

[8] Tian Q J,Edward J Coyle.Optimal distributed detection in clustered wireless sensor network:The weighted median [C]∥IEEE INFOCOM 2007,Anchorage,Alaska,USA,2007:1-12.

[9] 高建良,徐勇軍,李曉維.基于加權(quán)中值的分布式傳感器網(wǎng)絡(luò)故障檢測[J].軟件學(xué)報,2007,18(5):1208-1217.

[10] Akbari A,Beikmahdavi N,Khosrozadeh A,et al.A survey cluster-based and cellular approach to fault detection and recovery in wireless sensor networks[J].World Applied Sciences Journal,2010,8(1):76-85.

[11] 劉 凱,彭 力.分簇式無線傳感器網(wǎng)絡(luò)節(jié)點故障診斷算法研究[J].傳感器與微系統(tǒng),2011,30(4):37-41.

Fault detection algorithm for WSNs clustering-based medium comparison*

ZHANG Cheng

(School of Electronic and Information Engineering,Beijing Jiaotong University,Beijing 100044,China)

The sensors in WSNs are prone to failure and results in inaccurate measurements,efficient and practical fault detection algorithms is very important to guarantee sensing quality of WSNs.A fault detection algorithm with clustering-based medium comparison(CBMC)is proposed.Different from traditional medium comparison idea,CBMC introduces clustering approach to determine the status by grouping and computing the measurements of neighbor nodes.Simulation results show that the algorithm achieves a high fault detection rate(DR) and a low false positive rate(FPR).

wireless sensor networks(WSNs); clustering medium comparison; fault diagnosis; fault detection; fault tolerant

2013—09—30

國家自然科學(xué)基金資助項目(60833002); 北京市自然科學(xué)基金資助項目(4091003)

TN 393

A

1000—9787(2014)04—0135—04

張 成(1976-),男,遼寧盤錦人,博士,研究領(lǐng)域為無線傳感器網(wǎng)絡(luò)、通信網(wǎng)絡(luò)、故障診斷。