摘 要: 事件監(jiān)測是無線傳感器網絡中的重要應用之一,而準確檢測出故障節(jié)點是提高事件監(jiān)測效率的前提。為了實現多應用目標傳感器網絡中較高的節(jié)點故障識別率,在基于簇狀樹的虛擬傳感網架構上,提出一種基于節(jié)點鄰域中值的事件監(jiān)測容錯算法。該算法充分利用了無線傳感網節(jié)點之間的空間相關性,融合鄰域各節(jié)點的測量值,通過節(jié)點的數值與鄰域中值之間的差值來判斷節(jié)點狀態(tài)。仿真實驗結果表明,即使是在節(jié)點故障概率比較高的情況下,該算法依然具有優(yōu)越的容錯性能。
關鍵詞: 容錯;虛擬傳感器網絡;事件監(jiān)測
0 引言
目前大多數無線傳感器網絡的部署都是為特定的應用服務,為每個應用部署相應的專用傳感器網絡往往成本過高,效率低下。虛擬傳感器網絡(Virtual Sensor Networks,VSN)則從一系列傳感器當中挑選出若干節(jié)點形成一種邏輯網絡,為某類特定的應用服務,其基本概念與在物理拓撲之上建立服務于特定用戶的虛擬網絡技術有異曲同工之妙。部署在相同地理區(qū)域內,并且互相協作的傳感器節(jié)點可以根據不同的監(jiān)測任務,在邏輯上構成多個不同的VSN[1]。
在傳統的無線傳感網事件監(jiān)測過程中,往往由于節(jié)點的質量較差、被損壞以及無線通信受噪聲干擾等問題,導致節(jié)點故障,產生錯誤的采樣數值,降低事件監(jiān)測的準確性。實現準確度較高的事件監(jiān)測,良好的容錯算法必不可少。然而,在虛擬傳感網架構中,傳感節(jié)點的容錯需求除了檢測出故障節(jié)點外,還要考慮在VSN內的故障節(jié)點拓撲管理問題,這是傳統無線傳感網容錯算法所欠缺的。因此,本文的主要研究目標是提出適用于虛擬傳感網架構,且具有優(yōu)越性能的容錯算法。
1 相關成果
參考文獻[2]提出了一種利用節(jié)點測量值的平均值來消除噪聲對傳感器讀數干擾的容錯算法。但是該算法僅適用于節(jié)點故障率較低的傳感網。參考文獻[3]同時考慮到了事件的時間、空間相關性,提出了一種分布式的事件區(qū)域檢測容錯算法,但該算法僅局限于固定事件區(qū)域的監(jiān)測。而在虛擬傳感器網絡架構下的容錯處理方面,僅有參考文獻[1]利用隨機過程描述事件的時間相關性,提出了一種基于統計假設檢驗的容錯策略,通過檢驗本地采樣數據構成的時間序列與事件統計特征的符合程度來判斷節(jié)點是否發(fā)生錯誤。
依照參考文獻[1],傳感器錯誤分為如下兩類[3]:一是誤判錯誤,即監(jiān)測環(huán)境處于正常狀態(tài)時,傳感器節(jié)點卻報告有相應事件發(fā)生;二是失判錯誤,即事件發(fā)生時,傳感器節(jié)點卻沒有報告。如果節(jié)點失判,由于鄰居節(jié)點大多都正常工作,已監(jiān)測到了該事件,所以參考文獻[1]認為出現失判無關緊要而不做處理;如果節(jié)點發(fā)生誤判,則不再接受此節(jié)點消息。參考文獻[1]的容錯策略不當之處在于:(1)很多傳感網應用并不是僅僅以監(jiān)測到事件發(fā)生為最終目的,還需要將采集到的數據匯總并進行運算處理。失判情況下,如果放任錯誤數據不管,對傳感網應用的結果準確度會產生影響;(2)節(jié)點故障狀況中存在瞬時測量值故障[4],即由于監(jiān)測環(huán)境的突然變化使得傳感節(jié)點極短時間內采樣數據異常。這樣的故障是暫時的、可恢復的。若因為一次瞬時測量值故障,就再不采用該節(jié)點所傳輸的數據,會降低傳感網的效率。
2 事件監(jiān)測的容錯算法
2.1 基于節(jié)點鄰域中值的容錯算法
在發(fā)生例如森林火災、化工毒氣泄漏的監(jiān)測區(qū)域中,鄰居節(jié)點間在正常情況下的測量數值是相同或者相近的,則稱該區(qū)域內的節(jié)點測量值具有空間相關性[5]。但節(jié)點誤判或者失判通常是視為隨機獨立的,不具有空間相關性。本文利用采集數據之間的空間相關性,對可能存在錯誤的傳感數據進行處理。
假設在傳感節(jié)點Si的通信半徑范圍內共有m-1個鄰居節(jié)點,這m個節(jié)點的集合構成了Si的節(jié)點鄰域,記為N(Si)。其中,Si的第k個鄰居節(jié)點記為Sik,1≤k≤m-1,其在某時刻所采集到的數據記為D(Sik)。因為節(jié)點采樣值中有可能會出現與正常數據偏差極大的錯誤值,所以如果用樣本均值來估計中心節(jié)點鄰域內的總體狀態(tài)是不合理的。因此,本文用鄰域數據中值來反映樣本中心。令N(Si)的中值為M(Si),假設Si的鄰域N(Si)中,各個鄰居節(jié)點所采集的數據按照數值大小升序排列,D(Si)≤D(Si1)≤…≤D(Si(m-1)),中值M(Si)的計算公式如下:
M(Si)=D(Si(m-1)/2),m為奇數[D(Si(m/2)+D(Si(m/2-1))]/2,m為偶數(1)
得出中值后,再計算出Si的采樣數值與M(Si)的差值pi。
pi=|D(Si)-M(Si)|(2)
得出差值pi后,根據式(3)計算出pi的均值與方差。
之后再由式(4)對傳感節(jié)點數值與中值的差值pi進行標準化處理。
本文假設在應用場景中,所部署的各個傳感器的采樣數值都是獨立同正態(tài)分布的,這意味著理論上N(Si)的均值與中值相同,但中值相比于均值能更為準確地反映出樣本中心。而當樣本數目i足夠大時,經過標準化的中值差值序列g1,g2…gi可視為服從N(0,1)標準正態(tài)分布的一個樣本。
最后,根據式(5)來檢測Si是否出現故障。將經過標準化的gi與預先給定的閾值θ相比較,其中θ>1。
如果|gi|-θ≥0,則Ri=1,表明Si發(fā)生故障。查詢標準正態(tài)分布表,如果設定判決閾值θ為1.65,則|gi|-θ≥0的概率大約是10%,這意味著如果某些偏離正常采樣值范圍的極值出現概率不超過10%,則可視作節(jié)點故障。其他節(jié)點故障率與對應的判決閾值如表1所示。
2.2 節(jié)點信譽機制
為了解決瞬時測量值故障導致傳感網效率降低的問題,本文提出了節(jié)點信譽機制。首先,定義變量LTC和STC,分別代表Si的長期信譽和短期信譽,假設max(LTC)為5,max(STC)為3,初始值都為0。status為節(jié)點暫時狀態(tài),正常時為0,故障時為1,表示正處于考察階段。final_status為節(jié)點最終狀態(tài),若為1,則永不采用其采樣值。sample為節(jié)點信譽未破產階段的采樣許可標識,值為1時正常采樣,值為0且final_status為0時采樣數據仍參與節(jié)點故障檢測,但僅對此采樣數據的對錯進行判斷,并不采用。算法偽代碼如下:
max(LTC)=5;max(STC)=3;
LTC=0;STC=0;
status=0;final_status=0;sample=1;
WHILE(final_status!=1)
{
IF(LTC==5)
{
final_status=1;
}
IF(status==1)
{
LTC++;
STC=0;
sample=0;
}
ELSE
IF(status==0&<C!=0)
{
STC++;
IF(STC==3)
{
sample=1;
}
}
}
一旦該節(jié)點發(fā)生故障,則LTC加1,STC無論為何值都重新歸零。在Si標識為故障節(jié)點期間仍然可以傳輸其他節(jié)點數據,并且其之后的采樣數據仍參與節(jié)點故障檢測,但僅對此采樣數據的對錯進行判斷,并不采用。如果之后的采樣數據在正常范圍內,則STC加1,直到STC等于3時撤銷對節(jié)點Si的故障標識,并正常采用其采樣數據。這樣可以有效規(guī)避因某一時刻的瞬時測量值故障而使得節(jié)點不再被信任。如果LTC累加到5,可視為Si信譽破產,不再與Si進行任何數據交換,更不會采用其采樣值。
3 容錯處理流程
參考文獻[6]提出了一種基于自頂向下的簇樹狀結構的VSN組建算法,使得傳感網部署區(qū)域內監(jiān)測到相同事件的節(jié)點構成一個VSN。
在VSN中,監(jiān)測到事件后需要將消息上傳到根節(jié)點,每個簇頭節(jié)點都在VSN簇樹構建過程中向路由表內添加條目建立路由,連通監(jiān)測到相同事件的所有節(jié)點。簇頭節(jié)點處理VSN構建消息的流程圖如圖1所示。
根據參考文獻[6]所提出的虛擬傳感網架構,當VSN內某傳感節(jié)點經本文第2節(jié)容錯算法確認為故障節(jié)點時,就會進行如圖2所示容錯處理流程。
如果Si是VSN簇頭節(jié)點(Cluster Head,CH),當CH失判時,簇內節(jié)點只要有一個監(jiān)測到了事件,都會上報給CH,并將CH納入VSN事件內。因此,CH失判對事件能否被監(jiān)測到影響并不大,但是為了保證失判時CH所提交的錯誤數據不影響匯總數據的精確性,無論失判還是誤判,都需要及時刪除并重新選擇CH。
4 仿真結果與性能分析
在仿真實驗中,將總數n=5 000個傳感節(jié)點隨機均勻地部署在500 m×500 m的平面區(qū)域內,sink節(jié)點部署在區(qū)域中央。每個節(jié)點有8個鄰居節(jié)點,節(jié)點采樣頻率為10 Hz,max(LTC)=3,max(STC)=3。判決閾值θ= 1.96??紤]同一監(jiān)測事件發(fā)生在單個區(qū)域和三個不同區(qū)域內兩種情況。事件區(qū)域內節(jié)點測量值服從正態(tài)分布N(100,10),故障節(jié)點測量值服從均勻分布U(40,100),正常區(qū)域節(jié)點測量值服從正態(tài)分布N(40,10)。比較本文算法與參考文獻[1]基于統計假設檢驗的容錯算法在不同節(jié)點故障率下的性能優(yōu)劣。節(jié)點故障率與錯誤節(jié)點數目對應關系如表2所示。
容錯準確率=,其中,num(Identify)指檢測出來的錯誤節(jié)點數目,num(fault)指錯誤節(jié)點總數。事件監(jiān)測準確率=
,其中,num(IEvent)指監(jiān)測到事件的傳感節(jié)點數目,num(Event)指位于事件區(qū)域內的傳感節(jié)點數目。
圖3顯示了在同事件單區(qū)域和多區(qū)域的場景中,相同傳感節(jié)點錯誤率的情況下,本文算法與參考文獻[1]算法的容錯準確率。圖4則顯示了兩種應用場景中,兩種算法事件監(jiān)測準確率隨節(jié)點錯誤率的變化。圖中,標有空心菱形節(jié)點的scheme1是參考文獻[1]算法性能曲線,標有空心圓節(jié)點的scheme2是本文算法性能曲線。由圖3、圖4可以看出,本文所提出的基于節(jié)點鄰域中值的事件監(jiān)測容錯算法無論在單目標區(qū)域還是多目標區(qū)域的事件監(jiān)測場景中,性能都要比參考文獻[1]基于統計假設檢驗的容錯算法更為優(yōu)越。
5 結束語
本文研究了虛擬傳感器網絡架構下的事件監(jiān)測容錯問題,組建了相應的網絡模型,提出了一種基于節(jié)點鄰域中值的事件監(jiān)測容錯算法,利用鄰域節(jié)點采樣值之間的空間相關性,對節(jié)點的觀測數值的正誤進行判斷,最后提出了節(jié)點信譽機制,有效規(guī)避了因瞬時測量值故障導致相應節(jié)點被棄用而使得傳感網效率降低的問題。仿真實驗結果表明,即便是在節(jié)點故障概率比較高的情況下,本文提出的算法依然具有優(yōu)越的容錯性能。
參考文獻
[1] 宋欣,王翠榮.基于統計假設檢驗的虛擬傳感網容錯策略[J].東北大學學報(自然科學版),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] 曹冬磊,曹建農,金蓓弘.一種無線傳感器網絡中事件區(qū)域檢測的容錯算法[J].計算機學報,2007,30(10):1770-1776.
[4] 徐小龍,耿衛(wèi)建,楊庚,等.高效容錯的無線傳感網事件及其邊界檢測算法[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.