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