鄧定勝

0 引言

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

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

1 系統(tǒng)模型

1.1 事件質(zhì)心

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

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

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

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

1.2 節(jié)點動量

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

一個節(jié)點的動量指其相對事件質(zhì)心的位置向量，并受其自身質(zhì)量讀數(shù)調(diào)節(jié)。

1.3 分割和融合決策規(guī)則

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

事件融合判定與上述內(nèi)容相對稱。此時，對兩個事件中的每個節(jié)點，計算節(jié)點相對兩個事件綜合起來的綜合質(zhì)心的動量矢量。該綜合質(zhì)心稱為聯(lián)合質(zhì)心，定義如下：

節(jié)點n相對該聯(lián)合質(zhì)心的動量稱為聯(lián)合動量。

定義7事件融合判定 設(shè)E為網(wǎng)絡(luò)中的事件集合。如果以下條件滿足，則事件e1和e2發(fā)生融合如公式（4）：

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

2 算法描描述

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

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

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

2.1 算法主主要階段

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

圖1 DRAA GON算法的三個階段

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

決策，必須要要有所有事件的相關(guān)信息。事件件分割和融合階段段的任務(wù)，分別別是對事件分割和和融合進行檢驗驗和執(zhí)行。

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

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

圖2 DRAGON元元程序狀態(tài)機

2.2 算法細節(jié)

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

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

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

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

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

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

3 性能評估

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

3.1 事件模型

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

3.2 性能指標和參數(shù)

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

表1 主要變量參數(shù)

每個節(jié)點的傳輸范圍為20米。

3.3 實驗結(jié)果

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

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

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

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

圖3 性能評估VS事件大小

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

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

圖4 性能比較VS事件數(shù)量

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

4 總結(jié)

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

[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