A LightWeight Fault-Tolerant Event Detection Method in Wireless Sensor Networks*

DONG Chuanming，LIU Kezhong，*，LUO Guang，JIN Huting

(1.School of Navigation，Wuhan University of Technology，Wuhan 430063，China;2.School of Information Engineering，Wuhan University of Technology，Wuhan 430070，China;3.Zhejiang Institute of Communications，Hangzhou 311112，China)

A LightWeight Fault-Tolerant Event Detection Method in Wireless Sensor Networks*

DONG Chuanming1，LIU Kezhong1，2*，LUO Guang2，JIN Huting3

(1.School of Navigation，Wuhan University of Technology，Wuhan 430063，China;2.School of Information Engineering，Wuhan University of Technology，Wuhan 430070，China;3.Zhejiang Institute of Communications，Hangzhou 311112，China)

Due to harsh environment and limited resources，nodes are prone to missed alarm and false alarm errors when in the process of running，so fault－tolerant event detection methods attractmuch attention in recent years.But traditional algorithms showed high computational complexity and high energy consumption.Aim at this，we adopt the Cth/m detection idea in radar target detection，and propose a detection method based on spatial－temporal characteristics.By observing the agreement between sample’s changing rate and the spatial－temporal characteristics，nodes can determine whether event happens or error occurs.During the detecting process，nodes are only required to dom times distance comparison and one time neighbor query，then it canmake decision，reflecting the lightweighting and low power consumption characteristics of themethod.Simulation results show that themethod also has low missed alarm rate and false alarm rate，and high fault recognition rate.In addition，as credibility adaptive adjustmentmechanism is introduced，the method can ensure event detection probability maintained at a high level in the iterative process and not deteriorate over time.

wireless sensor networks;event detection;fault tolerant;spatial－temporal characteristics

無線傳感器網(wǎng)絡(luò)因價(jià)格低廉、配置靈活、抗毀性強(qiáng)等一系列特點(diǎn)［1］被廣泛應(yīng)用于眾多事件檢測，如火災(zāi)檢測、化學(xué)物質(zhì)泄漏檢測等。但由于網(wǎng)絡(luò)通常部署無人看守的地方，節(jié)點(diǎn)容易受惡劣環(huán)境的干擾，加之節(jié)點(diǎn)自身資源的有限性，往往會(huì)引起節(jié)點(diǎn)信息采集錯(cuò)誤。傳感器節(jié)點(diǎn)容易產(chǎn)生的錯(cuò)誤主要有漏警錯(cuò)誤和虛警錯(cuò)誤。漏警錯(cuò)誤指事件發(fā)生了但節(jié)點(diǎn)未檢測到;虛警錯(cuò)誤指事件未發(fā)生但節(jié)點(diǎn)虛報(bào)有事件發(fā)生。在實(shí)際應(yīng)用中，我們期望這兩類錯(cuò)誤越小越好。

在無線傳感器網(wǎng)絡(luò)用于事件檢測時(shí)，確保采集數(shù)據(jù)的可靠性和消除檢測錯(cuò)誤的干擾，是事件檢測需要解決的一個(gè)關(guān)鍵問題。張樹奎等［2］提出了一種新的分布式容錯(cuò)檢測算法，通過構(gòu)建的融合樹獲得事件檢測的屬性值，將檢測錯(cuò)誤率控制在可接受的范圍內(nèi)。Nguyen－Thanh N等［3］基于證據(jù)理論設(shè)計(jì)了一種自適應(yīng)的事件探測器，該探測器通過比較采樣數(shù)據(jù)與經(jīng)驗(yàn)分布對(duì)比，根據(jù)其符合程度來驗(yàn)證事件發(fā)生的假設(shè)成立與否，從而實(shí)現(xiàn)事件檢測。文獻(xiàn)［4］針對(duì)感興趣的事件周圍失效節(jié)點(diǎn)的識(shí)別問題，提出局部失效節(jié)點(diǎn)識(shí)別和可容錯(cuò)的事件邊緣監(jiān)測算法。這些方法能夠獲得較好的檢測效果，對(duì)事件區(qū)域檢測具有一定的借鑒意義，但這些方法未考慮數(shù)據(jù)在容錯(cuò)檢測過程中的計(jì)算復(fù)雜度，以及如何在保證糾錯(cuò)效果的同時(shí)延長網(wǎng)絡(luò)的生存周期等問題。

一般情況下，檢測環(huán)境在短時(shí)間內(nèi)不會(huì)發(fā)生改變，傳感器節(jié)點(diǎn)在較短時(shí)間內(nèi)的檢測值也是彼此相關(guān)的。因而可以利用節(jié)點(diǎn)的時(shí)間相關(guān)性對(duì)節(jié)點(diǎn)出現(xiàn)的錯(cuò)誤信息進(jìn)行容錯(cuò)處理。Ould－Ahmed－Vall E等［5］考慮了一種容錯(cuò)的事件檢測方法，節(jié)點(diǎn)通過統(tǒng)計(jì)歷史數(shù)據(jù)來確定自己的出錯(cuò)概率，從而決定自己在鄰域投票中所占的權(quán)重。但是，利用時(shí)間容錯(cuò)檢測也有一定的局限性，它只能對(duì)暫時(shí)性錯(cuò)誤進(jìn)行糾正，而對(duì)于永久性錯(cuò)誤的節(jié)點(diǎn)產(chǎn)生的錯(cuò)誤束手無策;同時(shí)，由于節(jié)點(diǎn)是離散分布在事件檢測區(qū)域，而時(shí)間相關(guān)性是針對(duì)每一節(jié)點(diǎn)的容錯(cuò)處理，單個(gè)節(jié)點(diǎn)有時(shí)不能對(duì)事件信息進(jìn)行完整表達(dá)，因而時(shí)間相關(guān)性的容錯(cuò)只能算是數(shù)據(jù)的預(yù)處理，不能達(dá)到事件容錯(cuò)的目的。

相鄰節(jié)點(diǎn)在檢測環(huán)境中是具有空間相關(guān)性，利用相鄰節(jié)點(diǎn)間的相關(guān)的冗余信息對(duì)節(jié)點(diǎn)事件檢測進(jìn)行容錯(cuò)處理。文獻(xiàn)［6－7］都利用鄰居節(jié)點(diǎn)協(xié)作，通過共同決策形成具有故障容忍能力的故障檢測方法。黃日茂等［8］采用一種基于鄰居節(jié)點(diǎn)數(shù)據(jù)分析的WSN故障檢測方法，將節(jié)點(diǎn)數(shù)據(jù)與覆蓋范圍內(nèi)可信鄰居節(jié)點(diǎn)的數(shù)據(jù)進(jìn)行比較分析，判定節(jié)點(diǎn)是否故障。文獻(xiàn)［9］提出了一種空間相關(guān)的事件容錯(cuò)檢測方法，當(dāng)某節(jié)點(diǎn)檢測到數(shù)據(jù)偏離了正常值，或者鄰居節(jié)點(diǎn)的檢測數(shù)據(jù)超過了預(yù)定的閾值，則可能是某事件發(fā)生或是節(jié)點(diǎn)出現(xiàn)故障。以上算法要求鄰居節(jié)點(diǎn)間相互通信，會(huì)消耗較多的能量，尤其在算法較為復(fù)雜時(shí)，網(wǎng)絡(luò)壽命會(huì)受到嚴(yán)重影響。

隨著時(shí)間的變化，當(dāng)節(jié)點(diǎn)采集到的數(shù)據(jù)保持平穩(wěn)，一般認(rèn)為該區(qū)域?qū)鞲衅魇录z測來說是時(shí)空相關(guān)的［10］，本文提出一種分布式的輕量級(jí)的事件容錯(cuò)檢測方法，該方法通過匹配節(jié)點(diǎn)采樣值變化率與時(shí)間特性的相似度來實(shí)現(xiàn)事件檢測。方法實(shí)現(xiàn)過程中，節(jié)點(diǎn)只需要進(jìn)行m次距離比較并詢問一次鄰居節(jié)點(diǎn)就可以實(shí)現(xiàn)檢測，因此算法是輕量級(jí)的。在詢問鄰居過程中，由于節(jié)點(diǎn)是m個(gè)采樣間隔才交換一次數(shù)據(jù)且每次交換的數(shù)據(jù)是節(jié)點(diǎn)決策后的二元信息，所以算法是高能效的。

1 事件檢測的過程

事件是指每個(gè)事件都可以看作由若干個(gè)事件屬性組合而成的，如火災(zāi)這個(gè)事件由溫度、煙霧濃度、光照強(qiáng)度等屬性組成。事件屬性是事件本身固有的性質(zhì)，是事件最基本的、必然的、不可再分的特性，它可以從某個(gè)方面表現(xiàn)事件。火災(zāi)事件中，溫度、煙霧濃度、光照強(qiáng)度是不可再分的火災(zāi)事件本身的特性，溫度升高，煙霧濃度升高，光照強(qiáng)度的變化都是火災(zāi)的表現(xiàn)。本文對(duì)事件的檢測是一個(gè)從模糊到清晰過程，其分為3個(gè)步驟:發(fā)現(xiàn)準(zhǔn)事件，基本認(rèn)定事件，核實(shí)精確事件。

因此，事件檢測程序包括3個(gè)環(huán)節(jié)，第1個(gè)環(huán)節(jié)為發(fā)現(xiàn)準(zhǔn)事件，節(jié)點(diǎn)自身檢測環(huán)節(jié)，節(jié)點(diǎn)通過匹配采樣值變化率與模式的關(guān)系初步判斷事件是否發(fā)生。為了進(jìn)一步確認(rèn)事件，節(jié)點(diǎn)還要詢問鄰居，節(jié)點(diǎn)根據(jù)鄰居狀態(tài)和自身的狀態(tài)確定是事件發(fā)生還是自身出錯(cuò)，即第2環(huán)節(jié)。第3環(huán)節(jié)為節(jié)點(diǎn)可信度調(diào)整環(huán)節(jié)。可信度指節(jié)點(diǎn)檢測到的數(shù)據(jù)可靠程度，可信度越大的節(jié)點(diǎn)對(duì)鄰居決策貢獻(xiàn)越大，可信度越小的節(jié)點(diǎn)對(duì)鄰居決策貢獻(xiàn)越小。可信度調(diào)整的原則為:若節(jié)點(diǎn)正確地檢測到了事件，就增加其可信度，否則就減小其可信度。

1.1 節(jié)點(diǎn)自身檢測

通過先驗(yàn)學(xué)習(xí)，抽象出檢測區(qū)域中感興趣的事件的主要的事件屬性—時(shí)間特性。當(dāng)事件發(fā)生時(shí)，將節(jié)點(diǎn)采樣值變化率與樣本時(shí)間特性進(jìn)行匹配。假設(shè)n個(gè)傳感器節(jié)點(diǎn)均勻分布在感興趣的區(qū)域，用于檢測某個(gè)特定事件。特定事件的時(shí)間序列為{s(ΔT)，s(2ΔT)，…，s(k)}，k=ΔT，2ΔT，…，nΔT時(shí)間序列在k時(shí)刻的數(shù)據(jù)變化率(斜率)記為r(k)，則r(k)=(s(k)－s(k－ΔT))/ΔT。根據(jù)先驗(yàn)經(jīng)驗(yàn)，r(k)作為事件的時(shí)間特性通常是可以預(yù)知的，且在節(jié)點(diǎn)部署前已保存在節(jié)點(diǎn)的內(nèi)存中。

節(jié)點(diǎn)以ΔT為時(shí)間間隔進(jìn)行均勻采樣，并建立緩存隊(duì)列保存當(dāng)前采樣值s(k)和前一時(shí)刻s(k－ΔT)。當(dāng)s(k)超過閾值Sth，說明特定事件發(fā)生或節(jié)點(diǎn)發(fā)生錯(cuò)誤，這時(shí)節(jié)點(diǎn)啟動(dòng)事件檢測程序，并記當(dāng)前時(shí)刻為k=0。

當(dāng)s(k)超過閾值Sth，節(jié)點(diǎn)啟動(dòng)事件檢測程序。如果是事件發(fā)生且節(jié)點(diǎn)可靠，那么節(jié)點(diǎn)采樣值在k時(shí)刻的變化率與r(k)應(yīng)該相差不大，即滿足式(1)。但由于節(jié)點(diǎn)的不可靠性，正常節(jié)點(diǎn)采樣值的變化率在少數(shù)情況下無法滿足式(1)，而故障節(jié)點(diǎn)采樣值的變化率少數(shù)情況下能夠滿足式(1)。

為減小以上情況的影響，本文引入雷達(dá)目標(biāo)檢測中Cth/m的檢測思想［10］，即節(jié)點(diǎn)連續(xù)檢測m次，若節(jié)點(diǎn)采樣值每次都大于Sth且變化率滿足式(1)的次數(shù)(記為C)超過Cth，那么節(jié)點(diǎn)初步認(rèn)為自己檢測到了事件，否則節(jié)點(diǎn)初步認(rèn)為自己發(fā)生了錯(cuò)誤。為方便描述，記正常狀態(tài)下的節(jié)點(diǎn)狀態(tài)為Normal，記初步檢測到事件的節(jié)點(diǎn)狀態(tài)為SE，記初步發(fā)生錯(cuò)誤的節(jié)點(diǎn)狀態(tài)為SF。節(jié)點(diǎn)自身檢測算法描述見算法1。

算法1:節(jié)點(diǎn)自身檢測

輸入:節(jié)點(diǎn)采樣值;輸出:節(jié)點(diǎn)初步檢測狀態(tài)

%for each node

status=Normal;C=0;

while(s(·)≤Sth);%do nothing until sample exceeds threshold %start event detection procedure

BufferLast=s(·);%create buffer

k=0;

%phase one:local detection

while(everyΔT time)do

k=k+1;

Buffer Current=s(k);

if s(k)＞Sth＆＆|(BufferCurrent－BufferLast)/ΔT－r(k)|≤δ

C=C+1;

end

BufferLast=BufferCurrent;

if k==m

break; end

end

if C≥Cth

status=SE;

else

status=SF;

end

1.2 事件決策

節(jié)點(diǎn)自身檢測是節(jié)點(diǎn)的自身行為，而自身檢測并不能將固有錯(cuò)誤消除，其檢測結(jié)果仍存在著不可靠性。由于通常事件都會(huì)覆蓋一定的區(qū)域和多數(shù)節(jié)點(diǎn)，于是節(jié)點(diǎn)可以通過詢問鄰居狀態(tài)來確認(rèn)事件是否真實(shí)發(fā)生。鄰居節(jié)點(diǎn)是指某一節(jié)點(diǎn)檢測范圍內(nèi)的節(jié)點(diǎn)的集合，本文假設(shè)節(jié)點(diǎn)的檢測范圍是相同的，且不隨能量變化而變化。在某一檢測區(qū)域中，當(dāng)一個(gè)節(jié)點(diǎn)接受到另一節(jié)點(diǎn)作為鄰居節(jié)點(diǎn)的請(qǐng)求后，將會(huì)拒絕做其他節(jié)點(diǎn)的鄰居節(jié)點(diǎn)。當(dāng)該節(jié)點(diǎn)同時(shí)收到兩個(gè)或兩個(gè)以上的節(jié)點(diǎn)尋求鄰居的請(qǐng)求時(shí)，節(jié)點(diǎn)優(yōu)先選擇與自己距離較近的節(jié)點(diǎn)成為鄰居，如果存在與兩個(gè)或兩個(gè)以上節(jié)點(diǎn)的距離相等的情況，那么該節(jié)點(diǎn)隨機(jī)選擇一個(gè)節(jié)點(diǎn)作為其鄰居。本文假設(shè)檢測區(qū)域的節(jié)點(diǎn)布置較為密集，任一鄰居節(jié)點(diǎn)集合都有2個(gè)以上的鄰居節(jié)點(diǎn)。

鄰居節(jié)點(diǎn)在返回的數(shù)據(jù)包中會(huì)包含其自身檢測狀態(tài)和數(shù)據(jù)可信度。節(jié)點(diǎn)收到這些數(shù)據(jù)包后，做以下運(yùn)算:

其中，N為節(jié)點(diǎn)鄰居的個(gè)數(shù);εi反映了鄰居的狀態(tài)，如果鄰居為SE狀態(tài)，那么εi取1，如果為SF狀態(tài)就取0;CR(i)為鄰居節(jié)點(diǎn)i的可信度，CRself為節(jié)點(diǎn)自身可信度。處理完鄰居的信息，節(jié)點(diǎn)得到處理值W。

根據(jù)節(jié)點(diǎn)間協(xié)作檢測的原則［11］，如果節(jié)點(diǎn)自身狀態(tài)為SE且W＞CRself·N/2，那么節(jié)點(diǎn)認(rèn)為自己正確檢測到了事件，狀態(tài)轉(zhuǎn)移為Event;否則認(rèn)為自己發(fā)生了虛警錯(cuò)誤，狀態(tài)轉(zhuǎn)移為Fault。如果節(jié)點(diǎn)自身狀態(tài)為SF且W＞CRself·N/2，那么節(jié)點(diǎn)認(rèn)為自己發(fā)生了漏警錯(cuò)誤，狀態(tài)轉(zhuǎn)移為Fault;否則認(rèn)為沒有事件發(fā)生，狀態(tài)轉(zhuǎn)移為Normal。檢測到事件的節(jié)點(diǎn)隨著事件的消亡也會(huì)逐漸恢復(fù)正常狀態(tài)，檢測偶爾出錯(cuò)的節(jié)點(diǎn)能夠回歸正常狀態(tài)，而永久錯(cuò)誤節(jié)點(diǎn)會(huì)被淘汰或棄用。節(jié)點(diǎn)狀態(tài)轉(zhuǎn)移如圖1所示。

圖1 節(jié)點(diǎn)狀態(tài)轉(zhuǎn)移圖

1.3 節(jié)點(diǎn)可信度調(diào)整

可信度模型是指局部網(wǎng)絡(luò)區(qū)域中節(jié)點(diǎn)與鄰居節(jié)點(diǎn)間可信度的建立、更新和整合的一套機(jī)制，根據(jù)可信度的分布狀況確定節(jié)點(diǎn)所處的檢測狀態(tài)，然后根據(jù)節(jié)點(diǎn)檢測狀態(tài)和能量狀態(tài)更新節(jié)點(diǎn)的可信度。對(duì)于正確檢測到事件的節(jié)點(diǎn)，增加其可信度;對(duì)于發(fā)生虛警錯(cuò)誤和漏警錯(cuò)誤的節(jié)點(diǎn)，減小其可信度。同時(shí)，隨著節(jié)點(diǎn)能量的消耗，其可信度值也隨著下降?？尚哦鹊挠?jì)算遵照式(3)和式(4):

其中，ycurr為節(jié)點(diǎn)的故障函數(shù)，其最初值為0，ylast為ycurr的上一步的值;q為節(jié)點(diǎn)平均出錯(cuò)概率，也即故障節(jié)點(diǎn)在所有節(jié)點(diǎn)中所占的比例;CR(i)的取值范圍為(0，1);ψ為歸一化系數(shù);Ec/Eint為節(jié)點(diǎn)的能量狀態(tài)，Ec當(dāng)前剩余能量，Eint初始能量;s1，s2，s3，s4分別表示圖1中狀態(tài)判定的邏輯變量，TURE表示狀態(tài)發(fā)生。

可見，如果節(jié)點(diǎn)持續(xù)錯(cuò)誤，其可信度將一直減小;如果節(jié)點(diǎn)發(fā)生偶然錯(cuò)誤，其可信度將很快恢復(fù)正常值。同時(shí)，隨著能量的消耗，節(jié)點(diǎn)的可信度也會(huì)降低。當(dāng)CRself的值低于閾值εerror時(shí)，說明節(jié)點(diǎn)的能量消耗過大或節(jié)點(diǎn)經(jīng)常發(fā)生錯(cuò)誤，我們認(rèn)為該節(jié)點(diǎn)為無效節(jié)點(diǎn)，節(jié)點(diǎn)從此不再參與事件檢測。

節(jié)點(diǎn)事件決策和可信度調(diào)整的算法描述見算法2。

算法2:事件決策和可信度調(diào)整

輸入:節(jié)點(diǎn)初步檢測狀態(tài);輸出:事件

W=0;y=0;

%phase two:query neighbor

query and receive neighbor’s status and credit…

for i=1:N

if neighbor’s status==SE

W=W+e－y;%y presents neighbor’s credit

end

end

%phase three:make decision and adjust credit

if status==SE

status=Event;%event is detected

if ylast≤q%ylastpresents neighbor’s last step credit

y=0;%y presents node’s own credit

else

y=ylast－q;

end

else

status=Fault;%false alarm

y=ylast+1－q;

end

end

if status==SF

status=Fault;%missed alarm

y=ylast+1－q;

else

status=Normal;%no event happens

end

end

2 算法性能分析及參數(shù)討論

由算法1可以看出，節(jié)點(diǎn)在自身檢測中會(huì)出現(xiàn)兩類錯(cuò)誤。第1類錯(cuò)誤為將檢測到事件的節(jié)點(diǎn)認(rèn)定為故障節(jié)點(diǎn)，即偽故障錯(cuò)誤;第2類錯(cuò)誤為將故障節(jié)點(diǎn)認(rèn)定為檢測到事件的節(jié)點(diǎn)，即偽正常錯(cuò)誤。通常我們都希望這兩類錯(cuò)誤越小越好。

產(chǎn)生第1類錯(cuò)誤的原因是，在m次連續(xù)采樣中，節(jié)點(diǎn)采樣值變化率滿足式(1)的次數(shù)未達(dá)到Cth次，即至多有Cth－1次滿足式(1)。如果記

那么第1類錯(cuò)誤可以表示為

結(jié)論1:當(dāng)節(jié)點(diǎn)通過自身檢測的采樣值斜率與r(k)匹配次數(shù)的閾值Cth越小，同時(shí)節(jié)點(diǎn)與r(k)相匹配的區(qū)分度δ越大，偽故障錯(cuò)誤發(fā)生的概率越小。

產(chǎn)生第2類錯(cuò)誤的原因是，在m次連續(xù)采樣中，節(jié)點(diǎn)采樣值變化率滿足式(1)的次數(shù)超過Cth次。如果記故障節(jié)點(diǎn)的采樣值為s'(k)，并記

那么第2錯(cuò)誤可以表示為

結(jié)論2:當(dāng)節(jié)點(diǎn)通過自身檢測的采樣值斜率與r(k)匹配次數(shù)的閾值Cth越大，同時(shí)節(jié)點(diǎn)與r(k)相匹配的區(qū)分度δ越小，偽正常錯(cuò)誤發(fā)生概率越小。

由結(jié)論1和結(jié)論2可以看出，偽故障錯(cuò)誤與偽正常錯(cuò)誤是互斥的。由于通常正常節(jié)點(diǎn)比故障節(jié)點(diǎn)多，因此應(yīng)該優(yōu)先考慮降低偽故障錯(cuò)誤。

Cth和δ的取值與實(shí)際需求和s(k)服從的分布有關(guān)。s(k)作為節(jié)點(diǎn)的采樣值，一般與sm(k)偏離不大，可以認(rèn)為s(k)服從以sm(k)為均值、以σ2為方差的正態(tài)分布，同理s(k－ΔT)服從N(sm(k－ΔT)，σ2)。由于s(k)與s(k－ΔT)的均值不同，可以認(rèn)為s(k)與s(k－ΔT)相互獨(dú)立。如果記

結(jié)論3:當(dāng)給定偽故障錯(cuò)誤概率θ，即p1＜θ，根據(jù)式(5)就可以求出Cth和p，進(jìn)而解得δ。

p2的取值與s'(k)服從的分布有關(guān)。由于故障節(jié)點(diǎn)在功能上發(fā)生了問題，其產(chǎn)生的采樣值是隨機(jī)的，因此可以認(rèn)為故障節(jié)點(diǎn)的采樣值服從［a，b］上的均勻分布，且所有的采樣值相互獨(dú)立。如果記

那么可以得到Z的概率密度函數(shù)為

進(jìn)一步計(jì)算得到

p'在區(qū)間(0，+∞)上先單調(diào)遞增后單調(diào)遞減，在ΔT ·δ+(ΔT·r2(k))/δ處取得最大值。

結(jié)論4:如果要求偽正確錯(cuò)誤的概率越小，b－a就應(yīng)該越大。當(dāng)取定δ后，可以算出p'，再結(jié)合Cth就可以得到p2。

3 仿真實(shí)驗(yàn)

3.1 實(shí)驗(yàn)參數(shù)

假設(shè)1 024個(gè)節(jié)點(diǎn)網(wǎng)格化部署在32 m×32 m的區(qū)域中，節(jié)點(diǎn)通信半徑為m，事件區(qū)域?yàn)橐?18.5，20.5)中心、半徑為8 m的圓形區(qū)域，如圖2所示。圖中虛線交叉點(diǎn)為正常節(jié)點(diǎn)，實(shí)心點(diǎn)為故障節(jié)點(diǎn)，圓圈所示區(qū)域表示事件區(qū)域。

圖2 一次實(shí)驗(yàn)快照(故障節(jié)點(diǎn)率為0.1)

假設(shè)節(jié)點(diǎn)采樣頻率ΔT=1，s(k)服從的正態(tài)分布的方差σ2=1。如果要求第1類錯(cuò)誤的概率小于0.05，那么意味著p1的最大值要小于0.05。由于事件發(fā)生后大部分節(jié)點(diǎn)能以較大概率檢測到事件，即p較大(接近1)，此時(shí)p1為i的增函數(shù)，因此當(dāng)i=Cth－1時(shí)，p1取最大值。如果節(jié)點(diǎn)每采樣10次做一次自身檢測，即m=10，要使p1＜0.05，那么只要CCth－110·pCth－1·(1－p)11－Cth＜0.05即可，解得0.91≤p≤0.96和1≤Cth≤8。本文中取p=0.95，Cth= 8。依據(jù)式(7)，進(jìn)一步解得δ=2.771 4。

假設(shè)模式序列的變化率r(k)=1。為有效降低第2類錯(cuò)誤，取a=Sth，b－a=10，即故障節(jié)點(diǎn)服從均勻分布U(Sth，Sth+10)。為保證故障節(jié)點(diǎn)快速得到排除，取節(jié)點(diǎn)可信度閾值εerror=0.3。

3.2 實(shí)驗(yàn)與結(jié)果分析

為驗(yàn)證算法性能，下面進(jìn)行3組實(shí)驗(yàn)。

第1組實(shí)驗(yàn)考察節(jié)點(diǎn)在空間上的協(xié)同對(duì)漏警率、故障識(shí)別率和虛警率的影響。漏警率定義為事件發(fā)生時(shí)未檢測到事件的節(jié)點(diǎn)的數(shù)目與事件區(qū)域總節(jié)點(diǎn)數(shù)目的比值，故障識(shí)別率定義為最終狀態(tài)為Fault的故障節(jié)點(diǎn)的數(shù)目與事件區(qū)域內(nèi)總故障節(jié)點(diǎn)數(shù)目的比值，虛警率定義為事件未發(fā)生時(shí)虛稱檢測到事件的節(jié)點(diǎn)的數(shù)目與事件區(qū)域總節(jié)點(diǎn)數(shù)目的比值。

從圖3可以看到，當(dāng)節(jié)點(diǎn)故障率低于0.1時(shí)，基于時(shí)間和基于時(shí)空的方法的漏警率都低于0.08，即事件檢測概率都大于0.92。但隨著節(jié)點(diǎn)故障率的增加，利用時(shí)空相關(guān)性進(jìn)行檢測時(shí)的漏警率偏大，這是因?yàn)槌醪綑z測到事件的節(jié)點(diǎn)受到鄰居未檢測到事件節(jié)點(diǎn)的影響，尤其是在節(jié)點(diǎn)故障率較大的情況下，初步檢測到事件的節(jié)點(diǎn)容易轉(zhuǎn)換為Fault狀態(tài)。

圖3 節(jié)點(diǎn)故障率與漏警率的關(guān)系

從圖4可以看出，當(dāng)節(jié)點(diǎn)故障率低于0.2時(shí)，兩種方法的故障節(jié)點(diǎn)識(shí)別率都能達(dá)到0.93以上，且性能相差不大，這是因?yàn)榇蟛糠止收瞎?jié)點(diǎn)通過節(jié)點(diǎn)自身檢測被濾除掉了。但隨著故障率的增加，基于時(shí)空相關(guān)性的事件檢測方法性能下降，這是因?yàn)楣收瞎?jié)點(diǎn)受到鄰居未檢測到事件節(jié)點(diǎn)的影響，誤認(rèn)為沒有事件發(fā)生，而轉(zhuǎn)換為Normal狀態(tài)了。

圖4 節(jié)點(diǎn)故障率與故障識(shí)別率的關(guān)系

從圖5可以看出，利用時(shí)空相關(guān)性進(jìn)行事件檢測的虛警率遠(yuǎn)遠(yuǎn)低于利用時(shí)間相關(guān)性的，這是因?yàn)樘摲Q有事件發(fā)生的節(jié)點(diǎn)被鄰居節(jié)點(diǎn)糾正了。

圖5 節(jié)點(diǎn)故障率與虛警率的關(guān)系

綜合以上可以看出，當(dāng)節(jié)點(diǎn)故障率較小(＜0.15)時(shí)，兩種方法在漏警率和故障識(shí)別率上相差不大，但由于基于時(shí)空相關(guān)性的事件檢測方法在虛警率上遠(yuǎn)勝于基于時(shí)間相關(guān)性的，因此基于時(shí)空相關(guān)性的事件檢測方法略勝一籌。但當(dāng)節(jié)點(diǎn)故障率較大(＞0.15)時(shí)，就需要根據(jù)實(shí)際需求進(jìn)行選擇了。由于虛警率和漏警率難以同時(shí)達(dá)到最優(yōu)，此時(shí)若用戶更關(guān)注漏警率，那么可以選擇基于時(shí)間相關(guān)性的事件檢測方法;若更關(guān)注虛警率，那么可以選擇基于時(shí)空相關(guān)性的事件檢測方法。

第2組實(shí)驗(yàn)考察引入節(jié)點(diǎn)可信度機(jī)制對(duì)事件檢測概率的影響。仿真中，設(shè)定節(jié)點(diǎn)故障率為0.1。

由圖6可見，引入節(jié)點(diǎn)可信度機(jī)制的事件檢測方法在事件檢測概率上一直保持在90%左右;而未引入節(jié)點(diǎn)可信度機(jī)制的事件檢測方法，其事件檢測概率在第6次迭代后就開始下降，最后趨近于零。這是因?yàn)榍罢叻椒ㄔ诘^程中將無效節(jié)點(diǎn)不斷的排除掉了，由于剩下的節(jié)點(diǎn)都是有效節(jié)點(diǎn)，所以事件檢測概率能保持較高的值。排除掉的節(jié)點(diǎn)與故障節(jié)點(diǎn)的關(guān)系如圖7所示。

圖6 引入節(jié)點(diǎn)可信度機(jī)制與未引入的比較

由圖7可見，在前19次迭代過程中，事件區(qū)域內(nèi)剩余有效節(jié)點(diǎn)比例曲線下降比較快，而且排除掉的故障節(jié)點(diǎn)占排除掉的節(jié)點(diǎn)達(dá)70%以上的比例，這說明大部分故障節(jié)點(diǎn)都得到了排除。第19次迭代后，由于故障節(jié)點(diǎn)所占比例越來越小，事件區(qū)域內(nèi)剩余有效節(jié)點(diǎn)比例曲線下降變緩。

圖7 故障節(jié)點(diǎn)與無效節(jié)點(diǎn)的關(guān)系

第3組實(shí)驗(yàn)考察網(wǎng)絡(luò)能耗。網(wǎng)絡(luò)能耗與節(jié)點(diǎn)個(gè)數(shù)n、信息交換頻率f、鄰居節(jié)點(diǎn)個(gè)數(shù)N和數(shù)據(jù)序列長度L有關(guān)。傳統(tǒng)算法中，節(jié)點(diǎn)采集到數(shù)據(jù)后就與鄰居交換進(jìn)行事件判斷，因此能量消耗為n·f·N·L;有些算法在數(shù)據(jù)交換上采用了數(shù)據(jù)壓縮的策略［12］，其能量消耗為n·f·N·(αL)，0＜α＜1;本文中節(jié)點(diǎn)與鄰居交換的是決策后的信息，即二元決策，其數(shù)據(jù)長度為1，且本文數(shù)據(jù)交換頻率為f/m(m為時(shí)間特性匹配的次數(shù))，因此本文方法的能量消耗為n·(f/m)·N·1。從圖8對(duì)比可見，本文的方法是高能效的。

圖8 不同算法節(jié)點(diǎn)能量消耗對(duì)比圖

4 結(jié)論

本文討論了無線傳感器網(wǎng)絡(luò)下一種分布式的輕量級(jí)的事件檢測方法，該方法充分利用了節(jié)點(diǎn)在時(shí)間和空間上的相關(guān)性。當(dāng)節(jié)點(diǎn)故障率較小的時(shí)候，該方法能夠獲得較低漏警率和虛警率以及較高的故障識(shí)別率。由于引入了節(jié)點(diǎn)可信度機(jī)制，通過不斷排除故障節(jié)點(diǎn)，該方法能夠一直保持較高的事件檢測概率。仿真還表明，本文提出的算法是高能效的。

［1］Yick J，Mukherjee B，Ghosal D.Wireless Sensor Network Survey［J］.Computer Networks，2008，52(12):2292－2330.

［2］張書奎，崔志明，樊建席，等.基于伸展樹的無線傳感器網(wǎng)絡(luò)事件區(qū)域檢測［J］.電子學(xué)報(bào)，2010，38(B02):194－201.

［3］Nguyen－Thanh N，Koo I.Empirical Distribution－Based Event Detection in Wireless Sensor Networks:An Approach Based on Evidence Theory［J］.Sensors Journal，IEEE，2012，12(6): 2222－2228.

［4］Ding M，Chen D，Xing K，et al.Localized Fault－Tolerant Event Boundary Detection in Sensor Networks［C］//INFOCOM2005.24th Annual JointConference of the IEEEComputer and Communications Societies.Proceedings IEEE.IEEE，2005，2:902－913.

［5］Ould－Ahmed－Vall E，Heck Ferri B，Riley G.Distributed Fault－Tolerance for Event Detection Using Heterogeneous Wireless Sensor Networks［J］.Mobile Computing，IEEE Transaction on，2012，11 (12):1994－2007.

［6］Wittenburg G，Dziengel N，Wartenburger C，etal.A System for Distributed Event Detection in Wireless Sensor Networks［C］//Proceedings of the 9th ACM/IEEE International Conference on Information Processing in Sensor Networks.ACM，2010:94－104.

［7］Yim S J，Choi Y H.An Adaptive Fault－Tolerant Event Detection Scheme forWireless Sensor Networks［J］.Sensors，2010，10(3): 2332－2347.

［8］黃日茂，邱雪松，高志鵬，等.無線傳感器網(wǎng)絡(luò)中鄰居數(shù)據(jù)分析的故障檢測方法［J］.北京郵電大學(xué)學(xué)報(bào)，2011，34(3):31－34.

［9］朱藝華，沈丹丹，吳萬登，等.無線傳感器網(wǎng)絡(luò)優(yōu)化生存時(shí)間的動(dòng)態(tài)路由算法［J］.電子學(xué)報(bào)，2009，37(5):1041－1045.

［10］李建中，李金寶，石勝飛.傳感器網(wǎng)絡(luò)及其數(shù)據(jù)管理的概念，問題與進(jìn)展［J］.軟件學(xué)報(bào)，2003，14(10):1717－1727.

［11］許小劍，黃培康.雷達(dá)系統(tǒng)及其信息處理［M］.電子工業(yè)出版社，2010.

［12］Krishnamachari B，Iyengar S.Distributed Bayesian Algorithms for Fault－Tolerant Event Region Detection in Wireless Sensor Networks［J］.IEEE Transactions on Computers，2004，53(3):241－250.

［13］張偉.無線傳感器網(wǎng)絡(luò)中復(fù)雜事件檢測關(guān)鍵技術(shù)的研究［D］.哈爾濱:哈爾濱工業(yè)大學(xué)，2012.

董傳明(1987－)，男，山東菏澤人，武漢理工大學(xué)碩士研究生，主要研究方向?yàn)闊o線傳感器網(wǎng)絡(luò)和交通信息工程;

劉克中(1975－)，男，湖北石首人，教授，博士，中國海事科技專家委員會(huì)信息分委會(huì)委員，主要研究方向?yàn)槠者m計(jì)算、無線傳感器網(wǎng)絡(luò)和交通信息工程。

無線傳感器網(wǎng)絡(luò)環(huán)境下的一種輕量級(jí)事件容錯(cuò)檢測算法*

董傳明1，劉克中1，2*，羅廣2，金湖庭3
(1.武漢理工大學(xué)航運(yùn)學(xué)院，武漢430063;2.武漢理工大學(xué)信息工程學(xué)院，武漢430070;浙江交通職業(yè)技術(shù)學(xué)院，杭州311112)

無線傳感器網(wǎng)絡(luò);事件檢測;容錯(cuò);時(shí)空特征

TP391.9

A

1004－1699(2014)01－0135－07

2013－10－08修改日期:2013－12－18

C:6150P

10.3969/j.issn.1004－1699.2014.01.025摘要:由于節(jié)點(diǎn)經(jīng)常布置于惡劣的環(huán)境中以及節(jié)點(diǎn)自身資源的有限性，節(jié)點(diǎn)在運(yùn)行過程中容易發(fā)生漏警錯(cuò)誤和虛警錯(cuò)誤，因此容錯(cuò)的事件檢測方法受到了廣泛的重視與研究。但傳統(tǒng)方法在性能上表現(xiàn)出計(jì)算復(fù)雜度高和能耗大的特點(diǎn)，針對(duì)此，引入雷達(dá)目標(biāo)檢測中Cth/m的檢測思想，提出一種基于時(shí)空特性的檢測方法。該方法通過觀察節(jié)點(diǎn)采樣值數(shù)據(jù)變化率與時(shí)間特性相似度來判斷是事件發(fā)生還是節(jié)點(diǎn)出錯(cuò)。方法在一次迭代過程中，節(jié)點(diǎn)只需做m次距離比較和一次鄰居狀態(tài)查詢，根據(jù)節(jié)點(diǎn)間的空間特性做出決策，表現(xiàn)出輕量級(jí)和低能耗的特點(diǎn)。仿真表明，方法還具有較低的漏警率和虛警率以及較高的故障識(shí)別率。此外，由于引入了節(jié)點(diǎn)可信度自適應(yīng)調(diào)整機(jī)制，方法能夠保證事件檢測概率在迭代過程中一直保持較高水平，而不隨時(shí)間惡化。

項(xiàng)目來源:國家自然科學(xué)基金項(xiàng)目(51279151);中央高校基本科研業(yè)務(wù)費(fèi)專項(xiàng)資金項(xiàng)目(2012－IV－28，2013－ZY－104);浙江省交通運(yùn)輸廳科技計(jì)劃項(xiàng)目(2012w05，2012w06)