一種在線容錯和鄰居協(xié)作的傳感器節(jié)點故障診斷算法

魏甜甜,曾雅麗,馬夢瑩,陳志德,2,3

1(福建師范大學 數(shù)學與信息學院,福州 350108)2(網(wǎng)絡安全與密碼技術福建省高校重點實驗室,福州 350108)3(中國科學院 信息工程研究所 中國科學院網(wǎng)絡測評技術重點實驗室,北京 100093)

1 引 言

無線傳感器網(wǎng)絡(Wireless Sensor Networks,WSNs)常被部署在惡劣的環(huán)境中,導致網(wǎng)絡中的傳感器節(jié)點相對于其它網(wǎng)絡更易發(fā)生故障從而影響整個無線傳感器服務性能.WSNs節(jié)點故障[1]分為硬故障和軟故障兩類,硬故障是指傳感器節(jié)點不能和其它節(jié)點通信,軟故障是指傳感器節(jié)點硬件部分正常,但感知或傳送的數(shù)據(jù)不正確.

在WSNs故障診斷方面,研究人員已經(jīng)做了很多相關的研究,并取得了很多成就.故障診斷主要有集中式和分布式兩種主要方法.集中式主要是節(jié)點將數(shù)據(jù)信息傳輸?shù)絪ink節(jié)點進行相關判斷,因此導致靠近sink節(jié)點的傳感器能量消耗巨大,縮短傳感器節(jié)點生命周期[2].傳感器具有數(shù)據(jù)存儲、簡單計算和節(jié)點通信的功能[3],并且與計算相比,節(jié)點通信耗能更大.分布式節(jié)點故障診斷算法是基于節(jié)點自身及其鄰居節(jié)點數(shù)據(jù)信息進行故障診斷,有效地避免了集中式診斷的不足.一些經(jīng)典的分布式故障檢測算法,如基于k-means聚類的WSNs分布式故障檢測算法[4],基于加權距離的容錯(DFWD)的故障檢測算法[5],分布式貝葉斯(Distributed Bayesian)故障檢測算法[6],基于隱馬爾可夫模型(HMM)的WSNs分布式故障檢測算法[7],分布式故障診斷算(Distributed Fault Detection,DFD)[8]都是利用鄰居節(jié)點數(shù)據(jù)的相似性對節(jié)點進行故障檢測與診斷,存在鄰居節(jié)點過少,故障發(fā)生率高時故障診斷正確率不高的問題.Muhamm-ed T等人[9]對節(jié)點數(shù)據(jù)進行建模分析,對節(jié)點數(shù)據(jù)預測分析,進而對節(jié)點狀態(tài)進行判斷.Panda M等人[10]提出基于概率知識的故障檢測算法,該算法僅和鄰居節(jié)點交換一次數(shù)據(jù),判斷正確率高.Ould-Ahmed-Vall 等人[11]提出了一個通用容錯事件檢測方案,僅適用于考慮事件高度本地化的檢測.Ding M等人[12]提出并分析了兩種用于故障傳感器識別和容錯事件邊界檢測的新算法,但對檢測效率存在延遲.季賽等人[13]采用時間冗余的方法結合節(jié)點歷史數(shù)據(jù)對節(jié)點進行狀態(tài)判定.Lo C等人[14]則設計一種基于模型的分布式在線故障診斷,但僅對特定的故障類型做出診斷.Mahapatro A等人[15]提出一種在線分布式算法,通過比較相鄰節(jié)點產(chǎn)生的數(shù)據(jù)和傳播每個節(jié)點的決策來實現(xiàn)故障診斷.以上方法都受到鄰居節(jié)點個數(shù)和故障發(fā)生率的影響,并且需要鄰居節(jié)點不斷交換數(shù)據(jù),造成傳感器節(jié)點的能量耗損嚴重.現(xiàn)有的關于故障診斷方面的研究工作中還存在以下兩個問題尚未得到很好的解決:

1) 如何在鄰居節(jié)點較少,故障發(fā)生率較高的情況下仍有較高的故障診斷正確率;

2) 如何有效地降低傳感器節(jié)點由于故障檢測而造成的能量消耗.本文針對這兩個問題提出基于在線容錯和鄰居協(xié)作的故障診斷算法(A Sensor Fault Diagnosis Algorit-hm Using Online Fault-tolerant and Neighbor- cooperation,FDOFN),與分布式診斷算法DSFD[10]和經(jīng)典算法DFD[8]的對比結果表明本文所提出的FDOFN在故障診斷正確率和通信代價上都有明顯的優(yōu)勢.

2 系統(tǒng)模型

2.1 模型假設

1)假設所有傳感器節(jié)點都只發(fā)生軟故障,即均可接收和發(fā)送數(shù)據(jù).

2)假設傳感器節(jié)點可以確定自己的地理位置.

3)傳感器節(jié)點具有相同的結構,感知相似的數(shù)據(jù).

4)正常傳感器節(jié)點數(shù)據(jù)在短時間內穩(wěn)定變化,且不同節(jié)點同一時刻的測量數(shù)據(jù)服從正態(tài)分布.

2.2 網(wǎng)絡模型及定義

設無線傳感器網(wǎng)絡可表示為G(V,E),其中V為傳感器節(jié)點的集合,E為鏈路集合.設任意節(jié)點vi和vj的位置分別為(xi,yi),(xj,yj),則節(jié)點vi和vj之間的歐氏距離可以表示為:

(1)

當相鄰的節(jié)點vi和vj之間的歐氏距離dist(vi,vj)小于通信半徑R時,稱這兩節(jié)點在G(V,E)存在鏈路.對任意節(jié)點vi∈V的鄰居節(jié)點集合可以表示為:

NEI(vi)={vj|vj∈V(vi,vj)∈E}

(2)

3 無線傳感器節(jié)點故障檢測算法

3.1 在線容錯故障檢測算法

由于在一個WSNs的檢測環(huán)境中,傳感器節(jié)點是連續(xù)采集數(shù)據(jù)的,傳感器節(jié)點的數(shù)據(jù)是帶有時間的數(shù)據(jù),因此可以表示為時間序列.同一節(jié)點所收集到的數(shù)據(jù)在較短時間內應該是穩(wěn)定變化的,也即相鄰時刻之間的時間序列應是相似的.對于時間序列的相似性我們采用歐氏距離進行計算.

記節(jié)點vi在t-1時刻及其之前的m個數(shù)據(jù)的時間序列為Xt-1=(x1,x2,…,xm),t時刻及其之前的m個數(shù)據(jù)的時間序列為Xt=(x2,x3,…,xm+1),Xt-1與Xt的時間序列的歐氏距離為:

(3)

Xt與Xt+1的時間序列的歐氏距離為:

(4)

由于節(jié)點時間序列應是相似的,為此兩者之間的歐氏距離之差應在一定的范圍內,即|DXt-1,t-DXt,t+1|

為便于表示我們用dt+1=|DXt-1,t-DXt,t+1|表示在時刻t+1時的兩時間序列之差.則在時刻t時的時間序列歐式距離之差為dt=|DXt-2,t-1-DXt-1,t|.

考慮到復雜多變的無線傳感器網(wǎng)絡環(huán)境影響以及數(shù)據(jù)的正常波動,只要不滿足條件就向鄰居節(jié)點發(fā)出反饋是不現(xiàn)實的,同時會加大節(jié)點能量的耗損,為此引入節(jié)點可容忍度值rmax.定義節(jié)點初始值r=1,若dt+1

算法1.在線容錯故障檢測算法

輸入:傳感器節(jié)點vi在某段時間的時間序列數(shù)據(jù)Xit及其鄰居節(jié)點數(shù)據(jù)NEIXit;r0,rmax;閾值d0;

輸出:節(jié)點診斷狀態(tài)(Fvi=0正常 orFvi=2可疑)

1) fori←1NEIXit//遍歷所有鄰居節(jié)點

2) 計算Xit的自身歐氏距離DXt-1,t和DXt,t+1

3)d=|DXt-1,t-DXt,t+1|

4) ifd

5)r=r0;Fvi=0;

6) else ifd≥d0&r0

7)r=r+1;Fvi=0

8) else ifd

9)r=r-1;Fvi=0

10) else ifd≥d0&r≥rmax

11)Fvi=2,啟動基于鄰居協(xié)作故障診斷機制

12) end

3.2 鄰居協(xié)作故障診斷機制

當節(jié)點被標記為可疑節(jié)點之后,需要通過基于鄰居節(jié)點的數(shù)據(jù)的空間相關性進一步確定該節(jié)點的真實狀態(tài).為此本文利用節(jié)點數(shù)據(jù)空間相似性,建立鄰居協(xié)作故障診斷機制.當節(jié)點vi為可疑節(jié)點時,根據(jù)鄰居協(xié)作故障診斷機制,診斷向其鄰居節(jié)點NEI(vi)發(fā)送請求,鄰居節(jié)點收到故障請求之后,鄰居節(jié)點根據(jù)自身狀態(tài)做出回復:

a.如果vj∈NEI(vi)為正常節(jié)點,則發(fā)送該時刻感知數(shù)據(jù)給節(jié)點vi;

b.如果vj∈NEI(vi)為可疑節(jié)點,則發(fā)送該時刻感知數(shù)據(jù)給節(jié)點vi,并在下一時刻發(fā)送故障請求給節(jié)點vj的鄰居節(jié)點NEI(vj);

c.如果vj∈NEI(vi)為故障節(jié)點,則不發(fā)送感知數(shù)據(jù)給節(jié)點vi,僅發(fā)送一個表示節(jié)點發(fā)生故障的消息′f′給節(jié)點vi.

(5)

記Ni為節(jié)點vi非故障節(jié)點的鄰居節(jié)點的個數(shù),節(jié)點vi鄰居節(jié)點的感知數(shù)據(jù)為NEIvxi(k),其中:

NEIvxi(k)={xvj(k)|vj∈NEI(vi),j=1,2,…,Ni}

(6)

(7)

(8)

N(k)={xv1(k),xv2(k),…,xvNi+1(k)}

(9)

(10)

(11)

其中med{|N(k)-medi|}表示N(k)中各個元素xvi(k),i=1,2,…,Ni+1與中值medi的差的絕對值的中位數(shù).

則節(jié)點狀態(tài)判定準則為:

具體實現(xiàn)如算法2所示.

算法2.鄰居協(xié)作故障診斷機制算法

輸入:vi在Fvi=2狀態(tài)k時刻的數(shù)據(jù)vxi(k),NEIvxi在k時刻數(shù)據(jù)NEIvxi(k)及對應的節(jié)點狀態(tài).

輸出:節(jié)點診斷狀態(tài)Fvi=0正常 orFvi=1故障.

1) fori←1toNEIXit//遍歷所有的鄰居節(jié)點k時刻數(shù)據(jù)

2) ifFvi=0 orFvi=2

3)N(k)=NEIvxi(k)∪vxi(k)//構造非故障節(jié)點數(shù)據(jù)集

4) else

5) break

6) end

7) end

8) sortN(k)//升序排列集合N(k)

9) 計算集合N(k)中位數(shù)medi

10)mad=med{|N(k)-medi|}//計算中值絕對偏差的中位數(shù)

13) iftvi>3

14)Fvi=1//節(jié)點故障

15) else

16)Fvi=0//節(jié)點正常

17) end

綜合在線容錯檢測階段和鄰居協(xié)作故障診斷從而完成對節(jié)點的最終狀態(tài)的判定.節(jié)點狀態(tài)判斷整個流程如圖1所示.

圖1 故障診斷流程圖Fig.1 Flow chart of fault diagnosis algorithms

4 實驗結果及分析

本實驗利用python3.0模擬在100*100m2的矩形區(qū)域內,通過隨機函數(shù)部署一定數(shù)量的傳感器節(jié)點.假設節(jié)點的測量數(shù)據(jù)為某個時刻的溫度測量值,設傳感器每隔時間T采集一次數(shù)據(jù),其中正常節(jié)點的數(shù)據(jù)為[15.0-19.0]之間,發(fā)生故障的數(shù)據(jù)為[0-100]隨機變化,同時考慮傳感器節(jié)點所處環(huán)境復雜多變,在同一時刻數(shù)據(jù)加入5%的噪聲數(shù)據(jù).設置在線容錯故障檢測階段參數(shù)d0=1.從故障診斷正確率和能量消耗(通信次數(shù))兩個因素衡量算法的性能.

首先,考慮參數(shù)rmax對實驗結果的影響,分別模擬在100個節(jié)點,150個節(jié)點,200個節(jié)點時,通過改變通信半徑分別實現(xiàn)平均鄰居節(jié)點數(shù)目為k=5,k=10,k=15,k=20時在節(jié)點故障率為0.30時 FDOFN算法rmax對故障檢測正確率的影響,經(jīng)過多次實驗,實驗結果如圖2(a)所示.圖2(a)中x軸表示rmax的取值,y軸表示故障診斷正確率.

由圖2(a)可知,當rmax<5時,節(jié)點故障診斷正確率變化不大.而在rmax=1,rmax=2時相對rmax=3,rmax=4時故障診斷正確率略低.原因是當rmax=1時,相當于節(jié)點基本沒有執(zhí)行在線故障檢測機制,一旦節(jié)點數(shù)據(jù)發(fā)生異常就將節(jié)點標記為可疑節(jié)點,若此時可疑節(jié)點為故障節(jié)點,在鄰居協(xié)作節(jié)點故障診斷階段是初步診斷為可疑節(jié)點或者正常節(jié)點的集合,因此經(jīng)過鄰居節(jié)點故障診斷機制診斷,最終可能會將可疑節(jié)點診斷為正常節(jié)點或者故障節(jié)點.若此時可疑節(jié)點為正常節(jié)點,同樣節(jié)點最終可能會被診斷為故障節(jié)點或者正常節(jié)點.特別是在鄰居節(jié)點為5時,節(jié)點被標記為可疑節(jié)點之后,最終結果得到正確判定的可能性就更低.rmax=2時,節(jié)點故障診斷率略有提高,這是由于排除了當節(jié)點為正常節(jié)點時,由于噪聲數(shù)據(jù)的影響,將節(jié)點誤判為故障節(jié)點的情況.當rmax=3,rmax=4時,故障診斷正確率都相對達到最高,這是因為此時經(jīng)過在線階段的初步檢測,可以將連續(xù)多次發(fā)生數(shù)據(jù)異常數(shù)據(jù)被標記為可疑節(jié)點的節(jié)點狀態(tài)本身為故障節(jié)點的可能性更高,而此時又可以將故障節(jié)點有效標記為可疑節(jié)點,不至于由于rmax的影響,導致某些故障節(jié)點不能轉化為可疑節(jié)點而造成將故障節(jié)點診斷為正常節(jié)點,造成故障診斷正確率的下降.當5≤rmax<8時,故障診斷正確率隨著rmax值的增加而減小,這是因為由于節(jié)點在連續(xù)出現(xiàn)數(shù)據(jù)異常時,此時rmax值會增大,隨著rmax值的增加,在線故障檢測階段需要連續(xù)數(shù)據(jù)異常的次數(shù)m就隨之增加,也就是節(jié)點必須要連續(xù)m次發(fā)生數(shù)據(jù)異常,節(jié)點才有可能標記為異常節(jié)點.rmax值越大,節(jié)點標記為可疑節(jié)點的條件就越高,導致發(fā)生故障的節(jié)點不能轉化為可疑節(jié)點,從而無法執(zhí)行鄰居節(jié)點故障檢測機制,此時會導致故障節(jié)點的最終診斷狀態(tài)為正常節(jié)點.rmax值越大,故障節(jié)點不能轉化為可疑節(jié)點的可能性就越大,此時故障診斷正確率就越低.當rmax≥8時,部分故障節(jié)點基本不能轉化為可疑節(jié)點,此時節(jié)點狀態(tài)將錯誤判定為正常節(jié)點,而一些永久故障節(jié)點則隨著時間的延續(xù),最終轉化為可疑節(jié)點,經(jīng)過鄰居協(xié)作階段得以正確判定其狀態(tài).而正常的節(jié)點由于可容忍度值的增大,不會轉化為可疑節(jié)點,即正常節(jié)點狀態(tài)仍為正常節(jié)點,因此故障診斷正確率基本保持不變.而rmax=3和rmax=4節(jié)點故障診斷正確率基本一樣,為減少節(jié)點能量通信次數(shù),為此在本文中采用rmax=4為在線容錯檢測階段的可容忍故障能力參數(shù).

圖2 Fig.2

然后考慮在節(jié)點個數(shù)相對更少的情況下,rmax對故障診斷正確率的影響.模擬僅有50個節(jié)點的情況下,通過改變通信半徑,多次試驗使得平均鄰居節(jié)點位于2到5之間,分別考慮在故障率分別為0.05,0.10,0.15,0.20,0.25,0.30情況下,故障診斷正確率結果如圖2(b)所示.當故障發(fā)生率為0.05時,節(jié)點故障診斷正確率尚能保持較高的故障診斷正確率,但當節(jié)點故障率升高時,特別是在節(jié)點故障率為0.25,0.3時節(jié)點診斷正確率無論在rmax取何值都有相對較低的故障診斷正確率.為此該算法在節(jié)點特別稀疏的場景下,和其他算法一樣相比并不具備良好的優(yōu)勢,仍不能很好的適應節(jié)點鄰居節(jié)點個數(shù)小于5的情況.這是因為本文算法FDOFN在鄰居協(xié)作診斷機制方面,對鄰居節(jié)點數(shù)據(jù)依賴較大,特別是當鄰居節(jié)點個數(shù)小于5時,故障率發(fā)生較高時,由于可參照的正常節(jié)點個數(shù)較少,節(jié)點狀態(tài)容易發(fā)生狀態(tài)的誤判.

為此綜合以上實驗,本文將考慮平均鄰居節(jié)點個數(shù)為5以上的情形下,多次實驗考慮本文算法性能.固定參數(shù)d0=1,rmax=4,在100*100m2范圍內均勻分布200個節(jié)點,改變節(jié)點故障率和平均鄰居節(jié)點數(shù)目,多次實驗得到FDOFN故障診斷正確率如圖3所示.從圖中可知,該算法在鄰居節(jié)較少、故障率較高時仍能達到較高的故障診斷正確率.這是由于本文算法FDOFN則通過在線容錯檢測的檢測,降低了將正常節(jié)點誤判為故障節(jié)點的概率.同時提高了將故障節(jié)點診斷為故障節(jié)點的可能性.若節(jié)點vi為故障節(jié)點,則節(jié)點vi必然會連續(xù)出現(xiàn)數(shù)據(jù)異常,從而此時節(jié)點為可疑節(jié)點,進入鄰居協(xié)作故障診斷,而鄰居協(xié)作故障檢測階段,數(shù)據(jù)均為初步診斷為非故障節(jié)點的數(shù)據(jù)(正常節(jié)點或者可疑節(jié)點),并且經(jīng)過t值的判斷,又很好的排除了極值的影響,從而節(jié)點vi被判定為故障節(jié)點,節(jié)點狀態(tài)得以正確判定.若節(jié)點vi為正常節(jié)點,則只有當節(jié)點vi連續(xù)多次出現(xiàn)數(shù)據(jù)異常時才會將該節(jié)點判定為可疑節(jié)點,而由于在線容錯節(jié)點可容忍度rmax的引入,將這種情況出現(xiàn)的概率大大降低.為此本文算法這種雙重診斷的方法,極大的提高了故障診斷正確率.

圖3 FDOFN算法故障診斷正確率Fig.3 Effects of fault probablity on the fault diagnosis accuracy of FDOFN

其次,考慮本文算法FDOFN和DSFD算法[10]、DFD算法[8]在不同節(jié)點故障率和不同平均節(jié)點個數(shù)的情況下的故障診斷正確率.實驗結果圖4、圖5、圖6、圖7分別表示在平均鄰居節(jié)點個數(shù)為5、10、15、20的四種情況下,不同節(jié)點故障率對故障診斷正確率的影響.由圖4可知,在平均鄰居節(jié)點個數(shù)k=5時,FDOFN算法比其他兩種算法表現(xiàn)出更好的故障診斷正確率.而在鄰居節(jié)點分別為為10,15,20時,FDOFN算法也仍保持了較高的故障診斷正確率.DSFD算法是基于統(tǒng)計學的3σ準則的原理,僅僅依靠某一時刻鄰居節(jié)點的數(shù)據(jù)進行判斷,當部分鄰居節(jié)點在某時刻受到異常數(shù)據(jù)的影響時,故障檢測的正確率也在一定程度上受到異常數(shù)據(jù)的影響.同時當故障率升高時,故障檢測正確率也有所下降.DFD算法則是采用相鄰節(jié)點在兩個臨近時刻感知的數(shù)據(jù)的差值做出判斷,對于一個正常的節(jié)點vi,若其鄰居節(jié)點中初步診斷狀態(tài)為正常的節(jié)點個數(shù)小于其鄰居節(jié)點的個數(shù)的一半時,會將該正常節(jié)點的狀態(tài)誤判為故障節(jié)點.特別是在鄰居節(jié)點個數(shù)較少時,或在故障率發(fā)生較高的情況下,更容易出現(xiàn)初步診斷狀態(tài)為正常的節(jié)點個數(shù)小于其鄰居節(jié)點個數(shù)的一半的情況,此時節(jié)點狀態(tài)會得到錯誤的判斷.而本文算法FDOFN則克服了以上算法的不足,通過在線容錯檢測的檢測,降低了將正常節(jié)點誤判為故障節(jié)點的概率,同時提高了將故障節(jié)點診斷為故障節(jié)點的可能性,從而比其他算法更具有優(yōu)勢.

圖4 k=5時故障率對正確率的影響Fig.4 Effcets of fault probability on the fault diagnosis accuracy when k=5

圖5 k=10時故障率對正確率的影響Fig.5 Effcets of fault probability on the fault diagnosis accuracy when k=10

圖6 k=15時故障率對正確率的影響Fig.6 Effcets of fault probability on the fault diagnosis accuracy when k=15

最后進行通信代價的對比.由于傳感器節(jié)點消耗能量模塊主要包括傳感器模塊、處理器模塊和無線通信模塊[17],傳輸1bit的信息100m的距離所需要的能量大約相當于執(zhí)行3000條計算指令所消耗的能量.因此傳感器節(jié)點的耗能主要在于節(jié)點與節(jié)點之間的互相通信.本文通過通信次數(shù)來衡量故障診斷造成的能量消耗.固定200個傳感器節(jié)點,平均鄰居節(jié)數(shù)k=5考慮在一定時間段內,節(jié)點采集數(shù)據(jù)10次.假設節(jié)點在第4次數(shù)據(jù)采集時發(fā)生故障,考慮三種算法在10次數(shù)據(jù)采集時間段內在k=5而節(jié)點故障率不同時,通信次數(shù)的變化.如圖8所示,DSFD算法和DFD算法為對節(jié)點進行故障診斷,需一直同其鄰居節(jié)點進行數(shù)據(jù)通信,而本文算法FDOFN僅在節(jié)點標記為可疑節(jié)點時才和其鄰居節(jié)點進行通信,大大降低了節(jié)點之間的互相通信,因此其通信次數(shù)遠遠低于其他兩種算法.

圖7 k=20時故障率對正確率的影響Fig.7 Effcets of fault probability on the fault diagnosis accuracy when k=20

圖8 k=5時故障率對通信次數(shù)的影響Fig.8 Effect of fault probability on the number of communications when k=5

綜上可知,本文算法FDOFN在保持較高的故障檢測正確率的同時,還能夠極大地減少傳感器節(jié)點的能耗,延長網(wǎng)絡的生存周期.

5 結 論

通過分布式在線故障檢測進行節(jié)點的狀態(tài)判定是無線傳感器故障檢測的有效方法之一,本文方法的關鍵在于在線容錯故障檢測階段具有一定的容錯能力,降低了將正常節(jié)點診斷為故障節(jié)點的可能性,并且只在節(jié)點數(shù)據(jù)連續(xù)發(fā)生異常時才和鄰居進行通信,使節(jié)點之間的通信大大減少,從而有效地減少節(jié)點的能量耗損,從而提高了傳感器節(jié)點的使用壽命.同時基于鄰居協(xié)作故障診斷機制利用改進的3σ準則有效地避免了異常數(shù)據(jù)造成的故障診斷干擾,進一步提高故障診斷正確率.仿真實驗表明,該算法在有效地減少能量消耗的情況下,克服了傳統(tǒng)算法對鄰居節(jié)點較少、故障率高、故障診斷正確率低的缺點,對復雜的傳感器網(wǎng)絡環(huán)境也表現(xiàn)出良好的優(yōu)勢,并且適用于大規(guī)模無線傳感器網(wǎng)絡.