WSN中面向非均勻形狀事件的動態檢測方案

鄧定勝

0 引言

綜合了無線通信技術、傳感器技術、嵌入式計算技術和分布式信息處理技術的無線傳感器網絡（Wireless sensor network,簡稱WSN）[1]，是目前國際上前沿熱點的研究領域。在石油泄露檢測、地下水污染監測等應用領域，無線傳感器網絡具有重要作用。例如，液體擴散監控等應用領域，傳統的基于數值液體傳輸模型的液體預測技術，需要數小時的運行時間，計算量太大。為了實現事件的實時跟蹤，需要將模型分解，使計算任務在各傳感器節點間分布式執行，以實現計算的并行化。通過對每一個事件進行分布式檢測跟蹤，對于保證無線傳感器網絡應用的可靠性具有重要意義。

文獻[2]給出一種統計方法，在事件檢測時不需先驗判斷便可實現對廣義同質區域的檢測和跟蹤。文獻[3]提出的新的區域事件邊緣檢測算法利用了對偶空間技術。該算法本質上是集中式算法，但仍可以在雙層架構主干節點間分布式運行。文獻[4]中提出的DCTC方案使用“動態護航樹（dynamic convoy tree）”協議來同時實現事件跟蹤和通信架構維護。當前研究的主要不足在于，人們普遍假設事件既不會合而為一，也不會分裂成多個更小事件。許多情況下，該假設并不成立。再次比如地下化學品泄露問題。如果流體從多個地點噴涌而出，多處羽流將會相遇、混合。此時，它們便成為一個更大的羽流而失去各自的形態。相反，它們在流動時途徑媒介所發生的變化，可能會導致流體沿著個別路徑流動而被拆散成多個規模更小的流體。實際上，對污染物的擴張、收縮、分裂和匯合進行動態跟蹤，對污染物治理決策具有非常重要的作用。鑒于此，本文在現有工作的基礎上，提出了一種改進的動態事件檢測和跟蹤方案，并通過仿真實驗驗證了本文方法的有效性。

1 系統模型

1.1 事件質心

事件的質心描述了事件的位置。它是一個廣義位置坐標，可以作為事件分裂/融合檢測等重要行為的參考點。

定義1質量函數 質量值mn,t表示節點n在時間t時事件讀數的“密度”。它是傳感器計數的有界非負實數。質量函數的確切表達式與具體應用場合有關。此處采用一個默認的二進制事件檢測規則：m=0表示未檢測。

定義2事件質心 事件的質心是指檢測到事件的所有節點以其質量為權重而得的平均位置。設e為目標事件。Ne(t) N為在時間t檢測到事件e的傳感器節點集合。Me(t)是總質量。設 hn是覆蓋節點n感應區域任意點的附近節點的不同感應區域數量均值。設向量 1n=[ xn,yn,zn]為節點n的三維位置向量，則時間t事件e的質心 1M( e, t)的計算方法如公式（1）：

節點密度nh用于確保事件質心不會由于該區域剛好存在較多節點而偏向于低密度區域。確定nh的一種方法就是估計給定節點平均感應區域的形狀。在實際部署時，使用數值融合技術來計算每個節點感應區域多重覆蓋期望值。

1.2 節點動量

為了跟蹤事件分裂和融合情況，我們認為：如果有大量事件計數與事件質心相距甚遠，則這些計數應該被視為自主事件。相反，如果兩個獨立事件非常接近，以致它們的主要計數已經無法區分，則這些事件應該合而為一。這些觀點表明了到底需要哪些信息才能檢測事件分割和融合。首先，我們必須考慮讀數強度及該讀數與事件質心的距離。其次，在弄清是否分割某一事件及在何處分割時，必須為距離補充方向性信息，因此需要一個矢量。于是，我們對物理學領域的另一個物理概念“動量”進行了借鑒。

一個節點的動量指其相對事件質心的位置向量，并受其自身質量讀數調節。

1.3 分割和融合決策規則

定義 4事件分裂判定 設TC為用戶定義的以距離為單位的內凝閾值。如果下述判定成立，則發生事件分裂。

事件融合判定與上述內容相對稱。此時，對兩個事件中的每個節點，計算節點相對兩個事件綜合起來的綜合質心的動量矢量。該綜合質心稱為聯合質心，定義如下：

節點n相對該聯合質心的動量稱為聯合動量。

定義7事件融合判定 設E為網絡中的事件集合。如果以下條件滿足，則事件e1和e2發生融合如公式（4）：

如果某事件不滿足分裂判定，則認為其單獨穩定。類似地，如果兩個事件沒有滿足融合判定，則認為它們聯合穩定。在實際部署時，傳感器讀數和節點位置數值只是近似值。為了避免事件件分割和融合判判定對噪聲過于于敏感，我們可以以對內凝閾值TC設置容限。

2 算法描描述

通過使使用上述定義的的基本概念，我們們設計了分布式式算法DRAGON，對動態變化的的不確定性事件件進行檢測和跟跟蹤。

我們假假設網絡分為多多個簇。每個簇只只有一個節點或或簇頭作為該簇的的本地數據匯點點。DRAGON算算法將會運行于于各個簇頭上。如如果事件完全位位于一個簇內，則則該簇頭完全本本地化運行DRAAGON算法。當當事件橫跨多個簇簇時，必須允許許簇頭相互通信。。當決策可以融融合當前哪些事事件時，還需要全全局統籌。因此，我們定義了““主干樹”概念。通過簇（頭））間鏈路來形成主主干樹的鏈路。任一簇頭可以作為樹的根，只只要樹被連接并且且包括所有的簇簇頭即可，樹的的形成方法并不不重要。底層的簇協協議可以對簇頭頭進行輪流循環環，以平衡能量量消耗。也有可能網網絡中的簇頭由由資源充足的節節點擔任。

為了進進一步闡述DRRAGON算法的分布式特性，我我們希望該算法只只涉及實際跟蹤蹤事件的網絡區區域，以利用本地地特性并節約能源源。為此，通過過“活躍子樹本地化”對主干樹樹進行改進。這一一步驟始終在主主要算法運行前前進行，內容如下下：首先，樹根向向整個樹發送少少量消息，詢問每每個簇頭是處于于活躍狀態還是休休眠狀態。節點點處于活躍狀態還還是休眠狀態取取決于該簇頭在主主干樹中是葉節節點還是內節點點。葉節點當且僅僅當它有成員節點點感知到事件時時才處于活躍狀狀態；內節點當且且僅當自身活躍或或有子節點活躍躍時才處于活躍躍狀態。葉節點首首先對根請求做出出響應。活躍簇簇將會參與到DDRAGON算法中中，休眠節點將在在算法運行期間間繼續保持休眠眠。

2.1 算法主主要階段

DRAGGON算法的效效能和需求決定了了算法存在3個個運行階段概述、、分割、融合，如圖1所示：

圖1 DRAA GON算法的三個階段

如前文文闡述，必需的的決策判斷需要要3種統計量：質心，總質量，節節點數量。在活活躍子樹本地化后，概述階段對對每個事件計算這這3種統計量，然后把它們分分配給所有活躍簇簇。要對融合做出出?

決策，必須要要有所有事件的相關信息。事件件分割和融合階段段的任務，分別別是對事件分割和和融合進行檢驗驗和執行。

在定義義事件分割和融融合階段間的關關系時，我們定義義：如果兩個事件件聯合穩定，則則由并集衍生的事件，其自身具具有穩定性。因此此，事件融合后后并不需要檢測測是否需要事件件分割。為了支持多多路分割和融合合，我們允許正常常的雙路分割和和融合階段運行多多次迭代。

DRAGON算算法的重要特點就就是，該算法的的3個階段均遵守守狀態傳輸、消消息傳輸和計算算的單種統一模式式。它主要包含了了3種狀態：開開始、融合、更更新、如圖2所所示：

圖2 DRAGON元元程序狀態機

2.2 算法細節

我們現在結合合算法3個階段段，詳細討論元元程序子線程：localProcess, fuse,finalizePhase和和processUpdatte。

（1）概述階段段。每個簇頭執執行的localProccess線程，只針對對直接位于相應應簇內的部分事事件，計算質心、總質量和節點數數量。fuse線程程與子節點和母母節點計算方法類類似，對每個事件件的本地質心、本地總質量和和本地節點數量進進行合計，并且利利用均值與求求和操作對其進進行綜合。finaalizePhase和proocessUpdate線程分別負責發送送和接收網絡所所有事件的完整匯匯總信息。然后后，簇頭內部數數據結構進行更新新。對網絡中的所所有事件來說，每個帶有入口的活躍簇均需要要一張匯總信息表表。于是，分割割和融合計算可在在樹上分布式進進行的同時保持準準確性。

（2）分割階段段。這一階段的的localProcess線線程負責識別目標標簇內的分割群群組。首先對事事件e，確定動量量滿足分割判斷的的所有節點，然然后按照節點動動量大小降序排列列。這些節點重復復執行算法，每每次執行形成一一個分割群組。對對滿足分割判斷的的每個節點，對對以下群組形成成判定進行檢驗驗。

設對節點n，考慮是否將其其加入分割群組JJ。設已經在分割割群組J中的的所有節點的的總質量為，定義為相對在在時間t測得的事事件e的質心，群組J所有節點點 的平均動量。距離為d。群組組J的節點數量量為。用TS表示相對群組規模，對節點點動量矢量與群群組平均動量距離離進行控制的分分離閾值。群組組形成判定定義義如公式（5）：

如果該判定成成立，則將考慮慮中的節點加入分分割群組，同時對群組的質心、總質量和平均動量值進行相應的更新。然后，將節點從考慮節點列表中去除。對所有節點考察完畢后，我們便認為群組構建完畢，下一群組開始。這一過程一直持續，直到所有考慮中的節點加入群組為止。

這一階段的 fuse線程對子節點和母節點確定的分割群組進行掃描，對對應于單分割現象的群組進行融合。兩個群組的融合過程與 localprocess將節點加入群組方式類似。finalizePhase線程負責從眾多潛在群組中選擇一個群組從整體中分離。選擇標準是選擇距離事件主體最遠的分割群組。這一比較過程的參考點是分割群組的質心，及將該群組脫離后初始事件剩余部分的質心。processUpdate線程命令簇頭針對它正在跟蹤的事件，對群組進行檢查，以確定是否已經包括了它的部分簇。如果包括，則對每個相關分割事件，我們認為檢測到了包括相關節點的新的事件。同時對所有事件的數據結構進行更新。

3 性能評估

本節將對本文提出的事件檢測方案采用 matlab2012仿真工具進行性能評估。

3.1 事件模型

本文使用基本的幾何形狀對事件建模。區域事件用正方形建模，點狀事件用圓形建模。對簡單的事件，我們支持事件重疊，因此我們不僅可以分割和融合，還可以通過混合簡單的幾何形狀來創建更為復雜的有趣的事件形狀。區域事件只有兩種讀取等級，外帶質量值0.5和內部高地質量值1.0。點狀事件的質量讀數以點的位置1.0開始，然后呈線性迅速下降至邊緣處的0.0。在運行時，事件在500m區域內的500m處以完全均勻隨機的初始位置開始，初始運動方向也設為均勻隨機。事件以直線運動，運動方向做必要的隨機變動以避開區域邊緣。運動速度為預先定義數值，且保持不變。

3.2 性能指標和參數

我們從能耗和運行時間兩方面衡量通信開銷。所有計算基于TelosB節點平臺[5]。網絡建模為無損無沖突網絡。另一重要指標是事件檢測和跟蹤準確率，以將DRAGON輸出與客觀標準進行對比。在本文模擬中，負責統計數據收集的模塊已經直接掌握了這些底層事件形狀和變化情況（被模擬的跟蹤算法并未掌握），也就是說掌握了實際狀況。準確度指標必須：（1）確定DRAGON是否成功檢測到了網絡中的所有事件；（2）確定對每個事件的描述是否恰當。第一個指標僅僅是描述DRAGON結果與實際情況間的事件數量差異。第二個指標定量描述事件形狀的正確度。我們與數據挖掘領域中的Jaccard系數類似，只使用一種稱為事件成員相似度的指標[6]。該指標定義為正確匹配與所有節點的比值（也就是正確匹配、虛警和漏警之和）。所有節點部署于500m*500m區域內。5種獨立變量及各變量的值域如表 1所示：

表1 主要變量參數

每個節點的傳輸范圍為20米。

3.3 實驗結果

我們選擇經過優化的DCTC[7]作為比較算法。這是因為該算法的總體操作是基于生成樹的重新配置，以覆蓋檢測到事件的節點。同樣地，它代表了現實世界面臨的事件跟蹤問題大多數最基本最簡單的“模板式”解決方案。同時，通過在重新配置樹結構時納入老節點修剪過程和新節點加入過程，并且不對事件形狀做任何假設，我們將 DCTC拓展至R-DCTC，以支持一般的事件形狀。

在我們第一類實驗中，更改每個獨立參數，確定DRAGON正確的內凝閾值（TC）和分離閾值（TS）。由于準確性是我們考慮的一個重要方面，我們只從事件數量差異和事件成員相似度方面對閾值進行優化。我們對稀疏網絡發現， TC=0.8且 TS= 0.9時跟蹤準確率最高，此時有3個事件，每個事件以 20m/s速度移動。對中等密度分布網絡，最優TC=1.3， TS= 1.2。對密集分布網絡，最優 TC=1.4， TS= 1.2。我們還發現，最優簇大小為2（也就是說，每個成員節點距離簇頭最多為2跳），最佳行為觸發器是閾值為3的節點飄移。在這些結果中，曲線變化緩慢，且有一個性能較優的高地。這意味著實際上存在著較寬的間隔，使閾值支持優異的性能結果。參數敏感度不高。我們也可以輕松找到與實際應用最匹配的參數。同時，各種部署情況下，最優參數的差異并不很大。這也印證了DRAGON運行與節點密度無關這一結論。

我們的第二組實驗主要是對DRAGON與DCTC（點狀事件）及R-DCTC（區域事件）進行對比性測試。我們研究了部署類型、事件大小、事件速度、事件數量和事件類型的影響。以下結果描述了 95%的置信區間，每個數據點為 10次運行取均值。

（1）事件大小影響。我們對不同事件大小條件下的兩種協議性能進行評估；實驗條件為稀疏網絡，3個可融合區域事件以20m/s的速度運動如圖3所示：

圖3 性能評估VS事件大小

圖3a表明，DRAGON的事件數量差異非常理想，而R-DCTC對不同事件大小時經常出錯。圖3b表明，DRAGON的事件成員相似度在80%左右，但是R-DCTC一直不理想。對圖3c和圖3d，我們必須承認，DRAGON的成本明顯較高。總體來說，DRAGON的準確度更優，雖然在時間和能效方面的成本較高，但是可拓展性很強。還有另一重要結論：更為重要的是，我們發現，當事件大小上升時，DRAGON在時間和能效方面的成本在對數和線性水平之間。

（2）事件數量影響。為了評估兩個協議面對大量事件時的性能，我們考慮可融合區域事件，寬度為150m，在稀疏網絡上以20m/s速度運動如圖4所示：

圖4 性能比較VS事件數量

圖4a和4b表明，DRAGON的準確度一直較高，即使事件數量上升也不會有顯著下降。同時，R-DCTC的準確度出現迄今最差水平，當事件數量上升時繼續惡化。然而，最有趣的結果出現在圖 4c和 4d中。當事件數量上升時，DRAGON在能耗和時間復雜度方面明顯呈線性上升。同時，R-DCTC的能耗和運行時間呈輕微的線性上升趨勢，基本保持平穩。但是兩種協議間的漸進性能差異并不算個問題 。實際上，我們正希望出現這一現象，因為在處理事件分割和融合時，DRAGON的計算和通信必須明確考慮網絡中的事件數量。成本也會相應上升。

4 總結

本文提出了一種改進的通用事件檢測和跟蹤方案（DRAGON），可在事件分割和融合情況下運行。仿真實驗結果表明，該方案在各種條件下均有很高的準確度。不論部事件大小和事件數量如何，它始終可以確定正確的事件數量，給出正確的事件形狀。我們下一步研究工作的重點是采用壓縮感知理論對無線傳感器網絡中的異常事件檢測問題進行建模，以進一步提高事件檢測的能效，延長網絡壽命。

[1]Branch J W, Giannella C, Szymanski B, et al.In-network outlier detection in wireless sensor networks [J].Knowledge and information systems, 2013, 34(1): 23-54

[2]Subramaniam S, Kalogeraki V, Palpanas T.Distributed real-time detection and tracking of homogeneous regions in sensor networks[C].Real-Time Systems Symposium,2006.RTSS'06.27th IEEE International.IEEE, 2006:401-411

[3]Liu J, Zhao F, Cheung P, et al.Apply geometric duality to energy-efficient non-local phenomenon awareness using sensor networks [J].Wireless Communications, IEEE,2012, 11(6): 62-68

[4]Zhang W, Cao G.DCTC: dynamic convoy tree-based collaboration for target tracking in sensor networks [J].Wireless Communications, IEEE Transactions on, 2004,3(5): 1689-1701

[5]Bloessl B, Joerer S, Mauroner F, et al.Low-cost interferer detection and classification using TelosB sensor motes[J].ACM SIGMOBILE Mobile Computing and Communications Review, 2013, 16(4): 34-37

[6]Witten I H, Frank E, And Hall M A.Data Mining: Practical Machine Learning Tools and Techniques: Practical Machine Learning Tools and Techniques [M].Elsevier,2011

[7]Zhang W, Cao G.Optimizing tree reconfiguration for mobile target tracking in sensor networks[C].INFOCOM 2004.Twenty-third Annual Joint Conference of the IEEE Computer and Communications Societies.IEEE, 2004, 4:2434-2445