基于灰色預測的分布式傳感器網絡故障檢測方法*

張 健

(1.北京工業大學嵌入式軟件與系統研究所，北京100124；2.北京建筑大學理學院，北京100044)

基于灰色預測的分布式傳感器網絡故障檢測方法*

張 健1，2*

(1.北京工業大學嵌入式軟件與系統研究所，北京100124；2.北京建筑大學理學院，北京100044)

針對無線傳感器網絡節點故障原因復雜，基于灰色預測理論，提出一種故障檢測方法。算法通過分析在某一采樣間隔內，觀測節點數據變化趨勢是否與鄰居節點變化趨勢一致，從而確定節點是否異常。仿真實驗表明，算法故障檢測能力較強，且避免了節點瞬間失效情況的出現。同時該算法設計簡單，易于硬件實現。

無線傳感器網絡；故障檢測；灰色預測；分布式

無線傳感器網絡是一種由大量分布的傳感節點組成的多跳、自組織型網絡，由于其體積小、靈活性強、價格低廉、無人值守等特性，被廣泛應用于環境監測、醫療衛生、智能家居和軍事等領域。但同時，也由于其自身資源的限制、尤其是能量、內存及計算能力等方面的限制，以及外部環境的影響，傳感器節點特別容易發生故障。因此需要有效的容錯設計技術來滿足其可靠性要求。無線傳感器網絡容錯設計需要考慮三個方面：故障模型、故障檢測與診斷、修復機制［1］。從整體而言，故障可分為三個層次：部件級、節點級和網絡級［2］。故障發生的位置不同，表現形式不同，容錯設計也不盡相同。本文側重傳感器節點的故障檢測問題。考慮到無線傳感器網絡自身的限制，檢測算法必須使得節點能量消耗最小化以及整個網絡壽命極大化。

鄰居協作是無線傳感器網絡的一種有效被動式檢測方法，高建良等提出一種基于加權中值的故障檢測算法(WMDFS)，對于每個節點引入信任等級的概念，定義鄰居節點的權重，根據節點的測量值與鄰居節點的加權中值之間的差異，判斷節點是否失效［3］。Yim等在文獻［4］中提出DFD故障節點檢測方案的改進算法(IDFD)［5］，算法中首先引入衡量某時刻相鄰節點測量差異dij的閾值θ1和衡量相鄰時刻相鄰節點測量差分Δdij的閾值θ2，如果相鄰節點不能同時滿足兩個閾值的條件，則至少有一個節點失效，然后通過節點與鄰居節點中可能存在失效風險的個數，預判定節點是否為故障節點，最后通過與鄰居節點中預判定故障節點的個數，給出最終的判定方案。文獻［6，7］中，通過歷史數據引入可信節點的概念，通過與可信鄰居集合節點的比對，判定故障節點。文獻［8］中，首次提出“偽故障節點”的概念，提出一種具有故障容忍的檢測方案(CSFD)。

本文在充分分析無線傳感器網絡特點的基礎上，結合上述算法的信任等級、偽故障節點等概念，將集中式網絡檢測算法推廣到分布式網絡檢測算法，提出基于灰色預測的分布式傳感器網絡故障檢測方法（GFD）。

1 網絡及故障模型

圖1 基于分簇的無線傳感器網絡結構

考慮如圖1所示的基于分簇的無線傳感器網絡，假設大量的傳感器節點被隨機部署在同質的應用環境中，所有傳感器節點時間同步，且具有相同的通信范圍，可表示為無線傳感器網絡圖G(V,E)，其中V={V1,V2,…,Vn}為無線傳感器節點集合，E為通信邊集合，若Distance(Vi,Vj)≤l，則Edge(Vi,Vj)∈E，這里l為傳感器節點的通信半徑，Vi,Vj互為鄰居節點。由于傳感器節點部署較為密集，相鄰的節點監測數據的變化趨勢近似相同，監測結果也應相近［9］。

根據文獻［2］中指出故障可能發生在無線傳感器網絡的不同層，比如物理層、硬件層、系統軟件層和中間件，本文對此并不關心，我們假設當故障發生時，傳感器節點仍然能夠完成指定任務，但結果卻與實際產生較大偏差。

2 灰色系統基本理論簡介［10］

在政治生活中，人民群眾提出增加“透明度”，用以某一決策形成的過程，維護大眾權益。一般習慣用“黑—灰—白”三種顏色表示信息透明狀態。灰色系統理論研究的是“部分信息已知、部分信息未知”的“小樣本”、“貧信息”不確定性系統，它通過對“部分”已知信息的生成、開發實現對現實世界的確切描述和認識。例如，給定原始數據序列

如圖2(a)所示，X(0)的曲線是擺動的，震蕩幅度較大，本身沒有任何明顯的規律。但如果對原始數據做一次累加生成新的序列記為X(1)，則

顯然 X(1)具有了明顯的遞增趨勢，如圖2(b)所示。

圖2 灰色序列生成示意圖

2.1 累加生成算子

累加生成一種常用的由灰變白的方法，在灰色系統理論中占有極其重要的地位。

定義1 累加生成算子

設X(0)為原始序列Τ為序列算子，

式中：

則稱Τ為 X(0)的一次累加生成算子，記為1-AGO(accumulating generation operator)。稱r階算子Τr為X(0)的r次累加生成算子，記為r-AGO。習慣上，記

一般地

其中

定理表明，當r充分大時，序列X(r)充分光滑。

2.2 GM(1,1)模型

設X(0)為非負序列

其中，x(0)(k)≥0(k=1,2,…,n)。 X(1)為 X(0)的1-AGO序列，Z(1)為X(1)的緊鄰均值生成序列，

其中

稱

為GM(1,1)模型的基本形式，其中參數-a稱作發展系數，反映了序列的發展態勢，b稱作灰色作用量，反映數據變化的關系。

稱

為GM(1,1)模型的白化方程，也叫影子方程。

則GM(1,1)模型的最小二乘估計參數列滿足［11］

相應地，白化方程的解也稱時間響應函數為

GM(1,1)模型的時間響應序列為

還原值

3 基于灰色預測的故障檢測算法(GFD)

3.1 符號說明

表1 相關符號說明

3.2 問題提出

考慮節點Vi，每隔Δk時間，收集測量數據，經過M時刻觀測后，收集到節點Vi的測量數據集構建節點Vi的鄰居節點集合N(Vi)，根據收集到的N(Vi)的測量數據集，判定節點Vi是否為故障節點。

3.3 GFD算法

表2 GFD算法步驟

3.4 幾點解釋：

①選用灰色預測模型算法，原因基于無線傳感器節點部署環境非常復雜，我們很難分析影響測量結果的眾多因素，灰色預測是一種對含有不確定因素系統的進行預測的方法，且算法計算簡單，計算量小，適用于無線傳感器網絡。

②算法中選擇預測數據序列的平均誤差作為節點信任等級變化的標準，避免的節點“瞬時故障”的問題。

③算法中對鄰居節點預測值進行了加權，大大降低了信任等級低的節點的影響。

④對于無線傳感器網絡中的能力消耗的多少主要取決于節點間的通信，本算法中每個周期內，僅傳遞M+1時刻的預測值X?M+1及節點的信任等級λ，對網絡不會帶來較大負擔。

⑤本算法不僅僅適用于如圖1的網絡結構，同樣對各種結構的傳感器網絡均適用。

4 仿真實驗

4.1 算法特性驗證

本文利用Matlab軟件進行仿真實驗設計，通過改變傳感器節點的通信半徑，考慮在鄰居節點個數及節點故障率的不同水平下，GFD算法的故障檢測精度問題以及節點觀測窗口M的大小對故障檢測精度的影響。實驗仿真了WSN監測區域為30×30單元的區域，隨機部署200個傳感器節點，為保證算法的有效性，重復進行若干次［13］。下圖給出當故障率p為10%，鄰居節點平均個數k為10時，GFD算法檢測效果，表3給出了不同p,k,M下GDF算法檢測精度。

圖3 p=0.1k=10，GFD算法檢測前后對比

表3 不同p，k，m下GDF算法檢測精度

從圖4中可以看出，當每一周期樣本容量固定時，GFD算法檢測精度隨傳感器網絡節點故障率p的增大而降低，隨鄰居節點個數k的增加而提高。圖5說明，當傳感器網絡故障率p一定時，GFD算法精度會隨著鄰居節點個數的增加以及周期采樣節點個數的增加而提高。圖6給出了k=10，k=20時，GFD算法在不同故障率p、不同采樣間隔M下的對照圖，同樣可以得出，GFD算法精度與故障率p成反比、與采樣間隔M成正比。

圖4 M=15 GFD算法檢測結果對比圖

圖5 p不同情況下GDF算法檢測結果對比圖

圖6 k不同情況下GDF算法檢測結果對比圖

4.2 算法性能驗證

為了驗證算法的有效性，對比文獻［4］，在32×32的區域內隨機部署1024個監測點，如圖7所示；選取兩個性能指標故障檢出率和錯誤告警率，其中故障檢出率為檢出的故障數量與總體故障數量的比值，錯誤告警率為被誤判為故障的數量與正常節點數量的比值。

圖7 隨機部署1 024個傳感節點示意圖

圖8和圖9選取采樣周期M=15，對比文獻［4］中的算法發現，在平均鄰居節點為15和20時，在故障檢出率和錯誤告警率兩個方面，基于灰色預測的故障檢測算法表現出優勢。由此可見，GFD算法比較適用于傳感器節點部署較為密集的環境中。

圖8 算法的故障檢出率

圖9 算法的錯誤告警率

5 結語

本文提出基于灰色預測的分布式傳感器網絡故障檢測方法（GFD），該算法充分利用了灰色預測對含有不確定因素系統的進行預測的特點，較傳統的基于數據挖掘理論的故障檢測算法［14-15］，計算量大大減小，算法設計更簡單，易于硬件實現，文中進行了數值仿真，證明了算法的有效性。

［1］李曉維.無線傳感器網絡技術［M］.北京：北京理工大學出版社，2007.

［2］Koushanfar F，Potkonjak M，Sangiovanni-Vincentelli A.Fault-Tolerance in Sensor Networks［M］.Handbook of Sensor Networks.CRC Press，2004.

［3］Gao J L，Xu Y J，Li X W.Weighted-Median Based Distributed Fault Detection for Wirelesssensor Networks［J］.J Softw，2007 (18)：1208-1217.

［4］Chen J R，Kher S，Somani A.Distributed Fault Detection of Wireless Sensor Networks［C］//Proceedings of the International Conference on Mobile Computing and Networkings，LosAngeles，CA，USA；ACM：New York，USA，2006：65-72.

［5］Yim S J，Choi Y H.An Adaptive Fault-Tolerant Event Detection Scheme for Wireless Sensor Networks［J］.Sensors，2010，10(3)：2332-2347.

［6］黃日茂，邱雪松，高志鵬，等.無線傳感器網絡中鄰居數據分析的故障檢測方法［J］.北京郵電大學學報，2011，34(3)：31-34.

［7］黃日茂.無線傳感器網絡故障管理機制與算法［D］.北京：北京郵電大學，2012.

［8］Wang T Y，Chang L Y，Dun D R，et al.Distributed Fault-Tolerant Detection Via Sensor Fault Detection in Sensor Networks［C］//Proceedings of the IEEE 10th International Conference on Information Fusion，Quebec，Canada，2007：1-6.

［9］Kar S，Moura J M F，Ramanan K.Distributed Parameter Estimation in Sensor Networks：Nonlinear Observation Modelsand Imperfect Communication［J］.IEEE Trans.Information Theory，2012，58：3575-3605.

［10］劉思峰，黨耀國，方志耕，等.灰色系統理論及其應用［M］.北京：科學出版社，2010.

［11］王能超.數值分析建模教程［M］.北京：高等教育出版社，2010.

［12］Rajasegarar S，Leckie C，Palaniswami M，et al.Distributed Anomaly Detectionin Wireless Sensor Networks［C］//Proceedings of the IEEE International Conference on Communications Systems，ICCS，Singapore，2006.

［13］Lee M H，Choi Y H.Fault Detection of Wireless Sensor Networks［J］.Comput Commun，2008，31：3469-3475.

［14］胡志鵬，魏立線，申軍偉，等.基于核Fisher判別分析的無線傳感器網絡入侵檢測算法［J］.傳感技術學報，2012，25(2)：246-250.

［15］趙錫恒，何小敏，許搖亮，等.基于免疫危險理論的無線傳感器網絡節點故障診斷［J］.傳感技術學報，2014，27(5)：658-663

張 健（1980-），女，山東德州人，北京工業大學博士研究生，北京建筑大學講師，主要研究領域為無線傳感器網絡、數據挖掘技術。

A Gray-Forecast Algorithm of Fault Detection for Wireless Sensor Networks*

ZHANG Jian1，2*
(1.Embedded Software and Systems Institute，Beijing University of Technology，Beijing 100124，China；2.School of Science，Beijing University of Civil Engineering and Architecture，Beijing 100044，China)

Wireless Sensor Networks(WSNs)are widely used in environmental monitoring，health care，smart home，military fields，and so on，because of its small，flexibility，low cost and unattended.And faults are common due to the bad environment and unattended.In order to ensure WSNs’service is normal，it is necessary to detect the faults.According to the complex reasons of wireless sensor network nodes failure，this paper presents a new fault detection algorithm based on based on gray prediction theory.The algorithm is that within a sample interval，it is analyzed that the observed node’s data trend is consistent with the trend of changed in the neighbour nodes to determine whether the node is abnormal.The experiment shows fault detection precision is very high，and the algorithm avoid the node instant failure.Meanwhile，the algorithm is simple，easily implemented in hardware.

wireless sensor network(WSNs)；fault detection；gray-forecast；distributed

TP393

A

1004-1699(2015)08-1188-06

??7230

10.3969/j.issn.1004-1699.2015.08.015

項目來源：北京建筑大學科學研究基金項目（00331614047）

2014-09-29 修改日期：2015-05-04