一種虛擬傳感器網(wǎng)絡(luò)中事件監(jiān)測的容錯(cuò)機(jī)制

孫智彥

（南京郵電大學(xué)通信與信息工程學(xué)院，江蘇南京210003）

一種虛擬傳感器網(wǎng)絡(luò)中事件監(jiān)測的容錯(cuò)機(jī)制

孫智彥

（南京郵電大學(xué)通信與信息工程學(xué)院，江蘇南京210003）

事件監(jiān)測是無線傳感器網(wǎng)絡(luò)中的重要應(yīng)用之一，而準(zhǔn)確檢測出故障節(jié)點(diǎn)是提高事件監(jiān)測效率的前提。為了實(shí)現(xiàn)多應(yīng)用目標(biāo)傳感器網(wǎng)絡(luò)中較高的節(jié)點(diǎn)故障識(shí)別率，在基于簇狀樹的虛擬傳感網(wǎng)架構(gòu)上，提出一種基于節(jié)點(diǎn)鄰域中值的事件監(jiān)測容錯(cuò)算法。該算法充分利用了無線傳感網(wǎng)節(jié)點(diǎn)之間的空間相關(guān)性，融合鄰域各節(jié)點(diǎn)的測量值，通過節(jié)點(diǎn)的數(shù)值與鄰域中值之間的差值來判斷節(jié)點(diǎn)狀態(tài)。仿真實(shí)驗(yàn)結(jié)果表明，即使是在節(jié)點(diǎn)故障概率比較高的情況下，該算法依然具有優(yōu)越的容錯(cuò)性能。

容錯(cuò)；虛擬傳感器網(wǎng)絡(luò)；事件監(jiān)測

0 引言

目前大多數(shù)無線傳感器網(wǎng)絡(luò)的部署都是為特定的應(yīng)用服務(wù)，為每個(gè)應(yīng)用部署相應(yīng)的專用傳感器網(wǎng)絡(luò)往往成本過高，效率低下。虛擬傳感器網(wǎng)絡(luò)（Virtual Sensor Networks，VSN）則從一系列傳感器當(dāng)中挑選出若干節(jié)點(diǎn)形成一種邏輯網(wǎng)絡(luò)，為某類特定的應(yīng)用服務(wù)，其基本概念與在物理拓?fù)渲辖⒎?wù)于特定用戶的虛擬網(wǎng)絡(luò)技術(shù)有異曲同工之妙。部署在相同地理區(qū)域內(nèi)，并且互相協(xié)作的傳感器節(jié)點(diǎn)可以根據(jù)不同的監(jiān)測任務(wù)，在邏輯上構(gòu)成多個(gè)不同的VSN[1]。

在傳統(tǒng)的無線傳感網(wǎng)事件監(jiān)測過程中，往往由于節(jié)點(diǎn)的質(zhì)量較差、被損壞以及無線通信受噪聲干擾等問題，導(dǎo)致節(jié)點(diǎn)故障，產(chǎn)生錯(cuò)誤的采樣數(shù)值，降低事件監(jiān)測的準(zhǔn)確性。實(shí)現(xiàn)準(zhǔn)確度較高的事件監(jiān)測，良好的容錯(cuò)算法必不可少。然而，在虛擬傳感網(wǎng)架構(gòu)中，傳感節(jié)點(diǎn)的容錯(cuò)需求除了檢測出故障節(jié)點(diǎn)外，還要考慮在VSN內(nèi)的故障節(jié)點(diǎn)拓?fù)涔芾韱栴}，這是傳統(tǒng)無線傳感網(wǎng)容錯(cuò)算法所欠缺的。因此，本文的主要研究目標(biāo)是提出適用于虛擬傳感網(wǎng)架構(gòu)，且具有優(yōu)越性能的容錯(cuò)算法。

1 相關(guān)成果

[2]提出了一種利用節(jié)點(diǎn)測量值的平均值來消除噪聲對傳感器讀數(shù)干擾的容錯(cuò)算法。但是該算法僅適用于節(jié)點(diǎn)故障率較低的傳感網(wǎng)。參考文獻(xiàn)[3]同時(shí)考慮到了事件的時(shí)間、空間相關(guān)性，提出了一種分布式的事件區(qū)域檢測容錯(cuò)算法，但該算法僅局限于固定事件區(qū)域的監(jiān)測。而在虛擬傳感器網(wǎng)絡(luò)架構(gòu)下的容錯(cuò)處理方面，僅有參考文獻(xiàn)[1]利用隨機(jī)過程描述事件的時(shí)間相關(guān)性，提出了一種基于統(tǒng)計(jì)假設(shè)檢驗(yàn)的容錯(cuò)策略，通過檢驗(yàn)本地采樣數(shù)據(jù)構(gòu)成的時(shí)間序列與事件統(tǒng)計(jì)特征的符合程度來判斷節(jié)點(diǎn)是否發(fā)生錯(cuò)誤。

依照參考文獻(xiàn)[1]，傳感器錯(cuò)誤分為如下兩類[3]：一是誤判錯(cuò)誤，即監(jiān)測環(huán)境處于正常狀態(tài)時(shí)，傳感器節(jié)點(diǎn)卻報(bào)告有相應(yīng)事件發(fā)生；二是失判錯(cuò)誤，即事件發(fā)生時(shí)，傳感器節(jié)點(diǎn)卻沒有報(bào)告。如果節(jié)點(diǎn)失判，由于鄰居節(jié)點(diǎn)大多都正常工作，已監(jiān)測到了該事件，所以參考文獻(xiàn)[1]認(rèn)為出現(xiàn)失判無關(guān)緊要而不做處理；如果節(jié)點(diǎn)發(fā)生誤判，則不再接受此節(jié)點(diǎn)消息。參考文獻(xiàn)[1]的容錯(cuò)策略不當(dāng)之處在于：（1）很多傳感網(wǎng)應(yīng)用并不是僅僅以監(jiān)測到事件發(fā)生為最終目的，還需要將采集到的數(shù)據(jù)匯總并進(jìn)行運(yùn)算處理。失判情況下，如果放任錯(cuò)誤數(shù)據(jù)不管，對傳感網(wǎng)應(yīng)用的結(jié)果準(zhǔn)確度會(huì)產(chǎn)生影響；（2）節(jié)點(diǎn)故障狀況中存在瞬時(shí)測量值故障[4]，即由于監(jiān)測環(huán)境的突然變化使得傳感節(jié)點(diǎn)極短時(shí)間內(nèi)采樣數(shù)據(jù)異常。這樣的故障是暫時(shí)的、可恢復(fù)的。若因?yàn)橐淮嗡矔r(shí)測量值故障，就再不采用該節(jié)點(diǎn)所傳輸?shù)臄?shù)據(jù)，會(huì)降低傳感網(wǎng)的效率。

2 事件監(jiān)測的容錯(cuò)算法

2.1 基于節(jié)點(diǎn)鄰域中值的容錯(cuò)算法

在發(fā)生例如森林火災(zāi)、化工毒氣泄漏的監(jiān)測區(qū)域中，鄰居節(jié)點(diǎn)間在正常情況下的測量數(shù)值是相同或者相近的，則稱該區(qū)域內(nèi)的節(jié)點(diǎn)測量值具有空間相關(guān)性[5]。但節(jié)點(diǎn)誤判或者失判通常是視為隨機(jī)獨(dú)立的，不具有空間相關(guān)性。本文利用采集數(shù)據(jù)之間的空間相關(guān)性，對可能存在錯(cuò)誤的傳感數(shù)據(jù)進(jìn)行處理。

假設(shè)在傳感節(jié)點(diǎn)Si的通信半徑范圍內(nèi)共有m-1個(gè)鄰居節(jié)點(diǎn)，這m個(gè)節(jié)點(diǎn)的集合構(gòu)成了Si的節(jié)點(diǎn)鄰域，記為N（Si）。其中，Si的第k個(gè)鄰居節(jié)點(diǎn)記為Sik，1≤k≤m-1，其在某時(shí)刻所采集到的數(shù)據(jù)記為D（Sik）。因?yàn)楣?jié)點(diǎn)采樣值中有可能會(huì)出現(xiàn)與正常數(shù)據(jù)偏差極大的錯(cuò)誤值，所以如果用樣本均值來估計(jì)中心節(jié)點(diǎn)鄰域內(nèi)的總體狀態(tài)是不合理的。因此，本文用鄰域數(shù)據(jù)中值來反映樣本中心。令N（Si）的中值為M（Si），假設(shè)Si的鄰域N（Si）中，各個(gè)鄰居節(jié)點(diǎn)所采集的數(shù)據(jù)按照數(shù)值大小升序排列，D（Si）≤D（Si1）≤…≤D（Si（m-1）），中值M（Si）的計(jì)算公式如下：

得出中值后，再計(jì)算出Si的采樣數(shù)值與M（Si）的差值pi。

得出差值pi后，根據(jù)式（3）計(jì)算出pi的均值與方差。

之后再由式（4）對傳感節(jié)點(diǎn)數(shù)值與中值的差值pi進(jìn)行標(biāo)準(zhǔn)化處理。

本文假設(shè)在應(yīng)用場景中，所部署的各個(gè)傳感器的采樣數(shù)值都是獨(dú)立同正態(tài)分布的，這意味著理論上N（Si）的均值與中值相同，但中值相比于均值能更為準(zhǔn)確地反映出樣本中心。而當(dāng)樣本數(shù)目i足夠大時(shí)，經(jīng)過標(biāo)準(zhǔn)化的中值差值序列g(shù)1，g2…gi可視為服從N（0，1）標(biāo)準(zhǔn)正態(tài)分布的一個(gè)樣本。

最后，根據(jù)式（5）來檢測Si是否出現(xiàn)故障。將經(jīng)過標(biāo)準(zhǔn)化的gi與預(yù)先給定的閾值θ相比較，其中θ＞1。

如果|gi|-θ≥0，則Ri=1，表明Si發(fā)生故障。查詢標(biāo)準(zhǔn)正態(tài)分布表，如果設(shè)定判決閾值θ為1.65，則|gi|-θ≥0的概率大約是10%，這意味著如果某些偏離正常采樣值范圍的極值出現(xiàn)概率不超過10%，則可視作節(jié)點(diǎn)故障。其他節(jié)點(diǎn)故障率與對應(yīng)的判決閾值如表1所示。

表1 節(jié)點(diǎn)故障率與判決閾值對應(yīng)表

2.2 節(jié)點(diǎn)信譽(yù)機(jī)制

為了解決瞬時(shí)測量值故障導(dǎo)致傳感網(wǎng)效率降低的問題，本文提出了節(jié)點(diǎn)信譽(yù)機(jī)制。首先，定義變量LTC和STC，分別代表Si的長期信譽(yù)和短期信譽(yù)，假設(shè)max（LTC）為5，max（STC）為3，初始值都為0。status為節(jié)點(diǎn)暫時(shí)狀態(tài)，正常時(shí)為0，故障時(shí)為1，表示正處于考察階段。final_status為節(jié)點(diǎn)最終狀態(tài)，若為1，則永不采用其采樣值。sample為節(jié)點(diǎn)信譽(yù)未破產(chǎn)階段的采樣許可標(biāo)識(shí)，值為1時(shí)正常采樣，值為0且final_status為0時(shí)采樣數(shù)據(jù)仍參與節(jié)點(diǎn)故障檢測，但僅對此采樣數(shù)據(jù)的對錯(cuò)進(jìn)行判斷，并不采用。算法偽代碼如下：

一旦該節(jié)點(diǎn)發(fā)生故障，則LTC加1，STC無論為何值都重新歸零。在Si標(biāo)識(shí)為故障節(jié)點(diǎn)期間仍然可以傳輸其他節(jié)點(diǎn)數(shù)據(jù)，并且其之后的采樣數(shù)據(jù)仍參與節(jié)點(diǎn)故障檢測，但僅對此采樣數(shù)據(jù)的對錯(cuò)進(jìn)行判斷，并不采用。如果之后的采樣數(shù)據(jù)在正常范圍內(nèi)，則STC加1，直到STC等于3時(shí)撤銷對節(jié)點(diǎn)Si的故障標(biāo)識(shí)，并正常采用其采樣數(shù)據(jù)。這樣可以有效規(guī)避因某一時(shí)刻的瞬時(shí)測量值故障而使得節(jié)點(diǎn)不再被信任。如果LTC累加到5，可視為Si信譽(yù)破產(chǎn)，不再與Si進(jìn)行任何數(shù)據(jù)交換，更不會(huì)采用其采樣值。

3 容錯(cuò)處理流程

參考文獻(xiàn)[6]提出了一種基于自頂向下的簇樹狀結(jié)構(gòu)的VSN組建算法，使得傳感網(wǎng)部署區(qū)域內(nèi)監(jiān)測到相同事件的節(jié)點(diǎn)構(gòu)成一個(gè)VSN。

在VSN中，監(jiān)測到事件后需要將消息上傳到根節(jié)點(diǎn)，每個(gè)簇頭節(jié)點(diǎn)都在VSN簇樹構(gòu)建過程中向路由表內(nèi)添加條目建立路由，連通監(jiān)測到相同事件的所有節(jié)點(diǎn)。簇頭節(jié)點(diǎn)處理VSN構(gòu)建消息的流程圖如圖1所示。

圖1 簇頭處理VSN構(gòu)建消息流程圖

根據(jù)參考文獻(xiàn)[6]所提出的虛擬傳感網(wǎng)架構(gòu)，當(dāng)VSN內(nèi)某傳感節(jié)點(diǎn)經(jīng)本文第2節(jié)容錯(cuò)算法確認(rèn)為故障節(jié)點(diǎn)時(shí)，就會(huì)進(jìn)行如圖2所示容錯(cuò)處理流程。

圖2 故障節(jié)點(diǎn)處理流程

如果Si是VSN簇頭節(jié)點(diǎn)（Cluster Head，CH），當(dāng)CH失判時(shí)，簇內(nèi)節(jié)點(diǎn)只要有一個(gè)監(jiān)測到了事件，都會(huì)上報(bào)給CH，并將CH納入VSN事件內(nèi)。因此，CH失判對事件能否被監(jiān)測到影響并不大，但是為了保證失判時(shí)CH所提交的錯(cuò)誤數(shù)據(jù)不影響匯總數(shù)據(jù)的精確性，無論失判還是誤判，都需要及時(shí)刪除并重新選擇CH。

4 仿真結(jié)果與性能分析

在仿真實(shí)驗(yàn)中，將總數(shù)n=5 000個(gè)傳感節(jié)點(diǎn)隨機(jī)均勻地部署在500 m×500 m的平面區(qū)域內(nèi)，sink節(jié)點(diǎn)部署在區(qū)域中央。每個(gè)節(jié)點(diǎn)有8個(gè)鄰居節(jié)點(diǎn)，節(jié)點(diǎn)采樣頻率為10 Hz，max（LTC）=3，max（STC）=3。判決閾值θ= 1.96?？紤]同一監(jiān)測事件發(fā)生在單個(gè)區(qū)域和三個(gè)不同區(qū)域內(nèi)兩種情況。事件區(qū)域內(nèi)節(jié)點(diǎn)測量值服從正態(tài)分布N（100，10），故障節(jié)點(diǎn)測量值服從均勻分布U（40，100），正常區(qū)域節(jié)點(diǎn)測量值服從正態(tài)分布N（40，10）。比較本文算法與參考文獻(xiàn)[1]基于統(tǒng)計(jì)假設(shè)檢驗(yàn)的容錯(cuò)算法在不同節(jié)點(diǎn)故障率下的性能優(yōu)劣。節(jié)點(diǎn)故障率與錯(cuò)誤節(jié)點(diǎn)數(shù)目對應(yīng)關(guān)系如表2所示。其中，num（Identify）指檢測出來的錯(cuò)誤節(jié)點(diǎn)數(shù)目，num（fault）指錯(cuò)誤節(jié)點(diǎn)總數(shù)。事件監(jiān)測準(zhǔn)確率

節(jié)點(diǎn)故障率/ %錯(cuò)誤節(jié)點(diǎn)數(shù)5 2 5 0 1 0 5 0 0 1 5 7 5 0 2 0 1 0 0 0 2 5 1 2 5 0

容錯(cuò)準(zhǔn)確率其中，num（IEvent）指監(jiān)測到事件的傳感節(jié)點(diǎn)數(shù)目，num（Event）指位于事件區(qū)域內(nèi)的傳感節(jié)點(diǎn)數(shù)目。

圖3顯示了在同事件單區(qū)域和多區(qū)域的場景中，相同傳感節(jié)點(diǎn)錯(cuò)誤率的情況下，本文算法與參考文獻(xiàn)[1]算法的容錯(cuò)準(zhǔn)確率。圖4則顯示了兩種應(yīng)用場景中，兩種算法事件監(jiān)測準(zhǔn)確率隨節(jié)點(diǎn)錯(cuò)誤率的變化。圖中，標(biāo)有空心菱形節(jié)點(diǎn)的scheme1是參考文獻(xiàn)[1]算法性能曲線，標(biāo)有空心圓節(jié)點(diǎn)的scheme2是本文算法性能曲線。由圖3、圖4可以看出，本文所提出的基于節(jié)點(diǎn)鄰域中值的事件監(jiān)測容錯(cuò)算法無論在單目標(biāo)區(qū)域還是多目標(biāo)區(qū)域的事件監(jiān)測場景中，性能都要比參考文獻(xiàn)[1]基于統(tǒng)計(jì)假設(shè)檢驗(yàn)的容錯(cuò)算法更為優(yōu)越。

圖3 節(jié)點(diǎn)故障識(shí)別率隨節(jié)點(diǎn)錯(cuò)誤概率變化曲線

圖4 事件監(jiān)測率隨節(jié)點(diǎn)錯(cuò)誤概率變化曲線

5 結(jié)束語

本文研究了虛擬傳感器網(wǎng)絡(luò)架構(gòu)下的事件監(jiān)測容錯(cuò)問題，組建了相應(yīng)的網(wǎng)絡(luò)模型，提出了一種基于節(jié)點(diǎn)鄰域中值的事件監(jiān)測容錯(cuò)算法，利用鄰域節(jié)點(diǎn)采樣值之間的空間相關(guān)性，對節(jié)點(diǎn)的觀測數(shù)值的正誤進(jìn)行判斷，最后提出了節(jié)點(diǎn)信譽(yù)機(jī)制，有效規(guī)避了因瞬時(shí)測量值故障導(dǎo)致相應(yīng)節(jié)點(diǎn)被棄用而使得傳感網(wǎng)效率降低的問題。仿真實(shí)驗(yàn)結(jié)果表明，即便是在節(jié)點(diǎn)故障概率比較高的情況下，本文提出的算法依然具有優(yōu)越的容錯(cuò)性能。

參考文獻(xiàn)

[1]宋欣，王翠榮.基于統(tǒng)計(jì)假設(shè)檢驗(yàn)的虛擬傳感網(wǎng)容錯(cuò)策略[J].東北大學(xué)學(xué)報(bào)（自然科學(xué)版），2012，33（3）：361-364.

[2]JIN G，NITTEL S.Ned：an efficient noise-tolerant event and event boundary detection algorithm in wireless sensor networks[C].Mobile Data Management，2006.7th International Conference on.IEEE，2006：153-153.

[3]曹冬磊，曹建農(nóng)，金蓓弘.一種無線傳感器網(wǎng)絡(luò)中事件區(qū)域檢測的容錯(cuò)算法[J].計(jì)算機(jī)學(xué)報(bào)，2007，30（10）：1770-1776.

[4]徐小龍，耿衛(wèi)建，楊庚，等.高效容錯(cuò)的無線傳感網(wǎng)事件及其邊界檢測算法[J].計(jì)算機(jī)研究與發(fā)展，2014，51（5）：997-1008.

[5]JI S，YUAN S F，MA T H，et al.Distributed fault detection for wireless sensor based on weighted average[C].Networks Security Wireless Communications and Trusted Computing（NSWCTC），2010 Second International Conference on.IEEE，2010：57-60.

[6]BANDARA H M N D，JAYASUMANA A P，ILLANGASEKARE T H.Cluster tree based self organization of virtual sensor networks[C].GLOBECOM Workshops，2008 IEEE.2008：1-6.

A fault-tolerant scheme for event detection in virtual sensor networks

Sun Zhiyan
（College of Telecommunication and Information Engineering，Nanjing University of Posts and Telecommunications，Nanjing 210003，China）

The event detection is one of the most significant applications of wireless sensor networks.While the premise of improving the efficiency of event detection is to detect the node fault accurately.In order to realize high fault sensor nodes recognition rate of multi-target monitoring sensor networks，a fault-tolerant algorithm based on median information on the cluster tree based virtual sensor networks is presented.The algorithm fully exploits the spatial correlation among the nodes，collects their data，and judges the state of the node by the difference value of nodes′data and their median.Simulation experimental results show that the algorithm has good performance even in the conditions of high fault probabilities.

fault-tolerant；virtual sensor networks；event detection

TP393

A

1674-7720（2015）19-0067-04

2015-06-04）

孫智彥（1991-），男，碩士研究生，主要研究方向：無線傳感網(wǎng)。

孫智彥.一種虛擬傳感器網(wǎng)絡(luò)中事件監(jiān)測的容錯(cuò)機(jī)制[J].微型機(jī)與應(yīng)用，2015，34（19）：67-70.