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

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

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

1 引 言

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

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

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

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

2 系統模型

2.1 模型假設

1)假設所有傳感器節點都只發生軟故障,即均可接收和發送數據.

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

3)傳感器節點具有相同的結構,感知相似的數據.

4)正常傳感器節點數據在短時間內穩定變化,且不同節點同一時刻的測量數據服從正態分布.

2.2 網絡模型及定義

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

(1)

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

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

(2)

3 無線傳感器節點故障檢測算法

3.1 在線容錯故障檢測算法

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

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

(3)

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

(4)

由于節點時間序列應是相似的,為此兩者之間的歐氏距離之差應在一定的范圍內,即|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|.

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

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

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

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

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

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,啟動基于鄰居協作故障診斷機制

12) end

3.2 鄰居協作故障診斷機制

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

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

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

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

(5)

記Ni為節點vi非故障節點的鄰居節點的個數,節點vi鄰居節點的感知數據為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的差的絕對值的中位數.

則節點狀態判定準則為:

具體實現如算法2所示.

算法2.鄰居協作故障診斷機制算法

輸入:vi在Fvi=2狀態k時刻的數據vxi(k),NEIvxi在k時刻數據NEIvxi(k)及對應的節點狀態.

輸出:節點診斷狀態Fvi=0正常 orFvi=1故障.

1) fori←1toNEIXit//遍歷所有的鄰居節點k時刻數據

2) ifFvi=0 orFvi=2

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

4) else

5) break

6) end

7) end

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

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

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

13) iftvi>3

14)Fvi=1//節點故障

15) else

16)Fvi=0//節點正常

17) end

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

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

4 實驗結果及分析

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

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

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

圖2 Fig.2

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

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

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

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

圖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

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

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

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

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

5 結 論

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