張 健

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

基于灰色預(yù)測的分布式傳感器網(wǎng)絡(luò)故障檢測方法*

張 健1，2*

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

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

無線傳感器網(wǎng)絡(luò)；故障檢測；灰色預(yù)測；分布式

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

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

本文在充分分析無線傳感器網(wǎng)絡(luò)特點(diǎn)的基礎(chǔ)上，結(jié)合上述算法的信任等級、偽故障節(jié)點(diǎn)等概念，將集中式網(wǎng)絡(luò)檢測算法推廣到分布式網(wǎng)絡(luò)檢測算法，提出基于灰色預(yù)測的分布式傳感器網(wǎng)絡(luò)故障檢測方法（GFD）。

1 網(wǎng)絡(luò)及故障模型

圖1 基于分簇的無線傳感器網(wǎng)絡(luò)結(jié)構(gòu)

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

根據(jù)文獻(xiàn)［2］中指出故障可能發(fā)生在無線傳感器網(wǎng)絡(luò)的不同層，比如物理層、硬件層、系統(tǒng)軟件層和中間件，本文對此并不關(guān)心，我們假設(shè)當(dāng)故障發(fā)生時(shí)，傳感器節(jié)點(diǎn)仍然能夠完成指定任務(wù)，但結(jié)果卻與實(shí)際產(chǎn)生較大偏差。

2 灰色系統(tǒng)基本理論簡介［10］

在政治生活中，人民群眾提出增加“透明度”，用以某一決策形成的過程，維護(hù)大眾權(quán)益。一般習(xí)慣用“黑—灰—白”三種顏色表示信息透明狀態(tài)?；疑到y(tǒng)理論研究的是“部分信息已知、部分信息未知”的“小樣本”、“貧信息”不確定性系統(tǒng)，它通過對“部分”已知信息的生成、開發(fā)實(shí)現(xiàn)對現(xiàn)實(shí)世界的確切描述和認(rèn)識。例如，給定原始數(shù)據(jù)序列

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

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

圖2 灰色序列生成示意圖

2.1 累加生成算子

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

定義1 累加生成算子

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

式中：

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

一般地

其中

定理表明，當(dāng)r充分大時(shí)，序列X(r)充分光滑。

2.2 GM(1,1)模型

設(shè)X(0)為非負(fù)序列

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

其中

稱

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

稱

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

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

相應(yīng)地，白化方程的解也稱時(shí)間響應(yīng)函數(shù)為

GM(1,1)模型的時(shí)間響應(yīng)序列為

還原值

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

3.1 符號說明

表1 相關(guān)符號說明

3.2 問題提出

考慮節(jié)點(diǎn)Vi，每隔Δk時(shí)間，收集測量數(shù)據(jù)，經(jīng)過M時(shí)刻觀測后，收集到節(jié)點(diǎn)Vi的測量數(shù)據(jù)集構(gòu)建節(jié)點(diǎn)Vi的鄰居節(jié)點(diǎn)集合N(Vi)，根據(jù)收集到的N(Vi)的測量數(shù)據(jù)集，判定節(jié)點(diǎn)Vi是否為故障節(jié)點(diǎn)。

3.3 GFD算法

表2 GFD算法步驟

3.4 幾點(diǎn)解釋：

①選用灰色預(yù)測模型算法，原因基于無線傳感器節(jié)點(diǎn)部署環(huán)境非常復(fù)雜，我們很難分析影響測量結(jié)果的眾多因素，灰色預(yù)測是一種對含有不確定因素系統(tǒng)的進(jìn)行預(yù)測的方法，且算法計(jì)算簡單，計(jì)算量小，適用于無線傳感器網(wǎng)絡(luò)。

②算法中選擇預(yù)測數(shù)據(jù)序列的平均誤差作為節(jié)點(diǎn)信任等級變化的標(biāo)準(zhǔn)，避免的節(jié)點(diǎn)“瞬時(shí)故障”的問題。

③算法中對鄰居節(jié)點(diǎn)預(yù)測值進(jìn)行了加權(quán)，大大降低了信任等級低的節(jié)點(diǎn)的影響。

④對于無線傳感器網(wǎng)絡(luò)中的能力消耗的多少主要取決于節(jié)點(diǎn)間的通信，本算法中每個(gè)周期內(nèi)，僅傳遞M+1時(shí)刻的預(yù)測值X?M+1及節(jié)點(diǎn)的信任等級λ，對網(wǎng)絡(luò)不會(huì)帶來較大負(fù)擔(dān)。

⑤本算法不僅僅適用于如圖1的網(wǎng)絡(luò)結(jié)構(gòu)，同樣對各種結(jié)構(gòu)的傳感器網(wǎng)絡(luò)均適用。

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

4.1 算法特性驗(yàn)證

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

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

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

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

圖4 M=15 GFD算法檢測結(jié)果對比圖

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

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

4.2 算法性能驗(yàn)證

為了驗(yàn)證算法的有效性，對比文獻(xiàn)［4］，在32×32的區(qū)域內(nèi)隨機(jī)部署1024個(gè)監(jiān)測點(diǎn)，如圖7所示；選取兩個(gè)性能指標(biāo)故障檢出率和錯(cuò)誤告警率，其中故障檢出率為檢出的故障數(shù)量與總體故障數(shù)量的比值，錯(cuò)誤告警率為被誤判為故障的數(shù)量與正常節(jié)點(diǎn)數(shù)量的比值。

圖7 隨機(jī)部署1 024個(gè)傳感節(jié)點(diǎn)示意圖

圖8和圖9選取采樣周期M=15，對比文獻(xiàn)［4］中的算法發(fā)現(xiàn)，在平均鄰居節(jié)點(diǎn)為15和20時(shí)，在故障檢出率和錯(cuò)誤告警率兩個(gè)方面，基于灰色預(yù)測的故障檢測算法表現(xiàn)出優(yōu)勢。由此可見，GFD算法比較適用于傳感器節(jié)點(diǎn)部署較為密集的環(huán)境中。

圖8 算法的故障檢出率

圖9 算法的錯(cuò)誤告警率

5 結(jié)語

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

［1］李曉維.無線傳感器網(wǎng)絡(luò)技術(shù)［M］.北京：北京理工大學(xué)出版社，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］黃日茂，邱雪松，高志鵬，等.無線傳感器網(wǎng)絡(luò)中鄰居數(shù)據(jù)分析的故障檢測方法［J］.北京郵電大學(xué)學(xué)報(bào)，2011，34(3)：31-34.

［7］黃日茂.無線傳感器網(wǎng)絡(luò)故障管理機(jī)制與算法［D］.北京：北京郵電大學(xué)，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］劉思峰，黨耀國，方志耕，等.灰色系統(tǒng)理論及其應(yīng)用［M］.北京：科學(xué)出版社，2010.

［11］王能超.數(shù)值分析建模教程［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判別分析的無線傳感器網(wǎng)絡(luò)入侵檢測算法［J］.傳感技術(shù)學(xué)報(bào)，2012，25(2)：246-250.

［15］趙錫恒，何小敏，許搖亮，等.基于免疫危險(xiǎn)理論的無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)故障診斷［J］.傳感技術(shù)學(xué)報(bào)，2014，27(5)：658-663

張 ?。?980-），女，山東德州人，北京工業(yè)大學(xué)博士研究生，北京建筑大學(xué)講師，主要研究領(lǐng)域?yàn)闊o線傳感器網(wǎng)絡(luò)、數(shù)據(jù)挖掘技術(shù)。

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

項(xiàng)目來源：北京建筑大學(xué)科學(xué)研究基金項(xiàng)目（00331614047）

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