基于融合樹的事件區域檢測容錯算法

張書奎，王宜懷，崔志明，樊建席

(1. 蘇州大學 計算機科學與技術學院，江蘇 蘇州 215006；2. 江蘇省現代企業信息化應用支撐軟件工程技術研發中心，江蘇 蘇州 215104)

1 引言

部署在檢測區域中由大量節點組成的無線傳感器網絡，每個節點都具有一定的計算、感知能力以及有限的能量，目的是協作地感知、采集和處理網絡覆蓋區域中感興趣事件發生的信息，并發送給觀察者。某事件的發生認為是環境狀態的異常改變，它可能以多種方式出現。隨著時間的推移，若傳感器讀數保持平穩，則認為此環境對傳感器檢測來說是時空關聯的[1]，可見，位于同一區域中鄰近傳感器的讀數關系密切。當某時段傳感器感知的讀數偏離了正常值，或者鄰居節點的讀數大大超過了預定義的閾值，則可能是某事件發生或是傳感器產生了故障[2,3]。但是，傳感器節點報告錯誤讀數的原因是多方面的(如與鄰居傳感器的讀數不同或雖然沒有超過預先設定的閾值但卻與它在上一時間間隔感知讀數不同等）。若發生了通信或硬件故障，這些錯誤會導致節點無效，意外破壞或惡意通信線路的改變也會導致無效節點的產生。環境受其他因素的影響，傳感器也可能產生瞬時的錯誤讀數。特別是部署在粗糙環境中的動態傳感器網絡進行感興趣事件的檢測，由于網絡拓撲結構發生變化，也會導致錯誤讀數的產生。一般來說，傳感器的錯誤一般可分為兩類[2]：一類是誤判錯誤，即當環境處于正常狀況時，傳感器卻報告有事件發生；另一類是失判錯誤，即當有特定的事件發生時，傳感器卻沒有報告事件的發生。所以，在無線傳感器網絡中，保證原始數據的可信性，消除錯誤讀數的影響，是事件區域檢測需要解決的關鍵問題之一。

文獻[4]提出了事件區域檢測的一種局部分布式算法。該算法假設事件是空間相關而錯誤是空間不相關的，且每個傳感器發生錯誤的概率相同。作為一種局部算法，它僅需要每個傳感器與自己的鄰居交換讀數，從而獲得鄰居節點檢測事件發生的統計概率，利用Bayesian分析，判定發生的是故障還是事件。文獻[5]則改進了文獻[4]的算法，考慮了傳感器誤差和錯誤引起的對事件判斷的影響以及如何選擇合適的鄰居數目，達到容錯的同時減少數據交換的目的。文獻[4～8]都是基于概率分析的方法，而且需要傳感器進行復雜的運算。文獻[9]提出了一種相對簡單非概率的檢測算法，通過兩輪投票以及少數服從多數原則，確定發生的是故障還是事件。

關于事件邊界檢測的研究，文獻[10,11]認為，事件的邊界是指事件區域與正常區域的分界線。如果一個傳感器的鄰居中既有異常的讀數，又有正常的讀數，那么就認為該傳感器位于事件區域的邊界。已有的事件邊界檢測算法依然是基于事件是空間相關的假設，同時采用概率分析的方法。還有一類工作關注于錯誤診斷[12]，這類工作關注的是如何確定錯誤發生的范圍或者引發錯誤的錯誤源，而不是事件發生的范圍。文獻[13]介紹了一種基于簇頭構建四叉樹的方法進行邊界檢測，每片葉子與長方形區域相對應。與四叉樹的聚類方法不同，本文構建了一種易擴展的二叉查詢樹，該查詢樹可以覆蓋整個感興趣的區域，能快速將事件發生的信息從感知節點傳輸到Sink。文獻[14]是使用一種基于分類的邊緣檢測機制，由線性多項式描述事件邊界，由此判定事件是在檢測區域的里面還是外面。然而，一個線性多項式不可能獲取事件發生的精確細節。而本文是通過構建多元回歸模型來近似檢測區域的感知值，沒有洪泛而是使用融合樹進行事件邊界檢測，以事件的時空關聯特性檢測整個區域，而不是通過2個事件之間的邊界來判定事件的發生。

分布式核回歸文獻[15]與本文的算法有相似之處，但也存在著較大不同。前者，任何一個節點都含有它局部區域范圍內的近似參數，因而，它不能正確回答自己局部區域之外的查詢， 每個節點發送含有一個向量（向量用來描述覆蓋它的局部區域）的信息，這個向量的大小隨著大量的和它共享核變量的鄰居節點的增加而增長，這對于資源受限的傳感器節點來說，是難以忍受的。

針對目前在上述方面研究的不足，本文提出了一種基于融合樹的事件區域檢測容錯算法，改算法分為2個階段。首先，構建分布式融合樹，每個感知節點僅報告自己的感知數據到最鄰近的樹節點，樹節點執行多元線性回歸，獲得事件區域檢測的估計值，傳輸的是描述事件區域檢測的多元回歸模型的系數，而不是實際的感知數據，Sink通過直接查詢根節點就可獲的感興趣區域內任一位置的感知值，減少了事件區域檢測的通信代價和復雜性。其次，在所構建融合樹的基礎上，可以對單個或多個同時發生的事件進行容錯檢測，識別有故障的傳感器節點和發生在邊界區域的事件，快速把檢測讀數傳給基站，減少數據傳輸的能量消耗和延遲。

2 融合樹的構建

融合樹（AT, aggregation tree）的構建是事件區域檢測過程的基礎。其目標是減少數據傳輸量，提高檢測精度。對數據融合算法的理論分析表明[16]，在完全融合的情況下，尋找最優融合樹的問題等同于求解最小Steiner樹的NP完全問題。為此，需要在計算處理能耗與傳輸能耗之間進行權衡。下面討論融合樹的構建過程。

2.1 網絡模型

設N個資源受限的靜態傳感器節點隨機地部署在檢測區域R=(r×r)內，用集合S=(s1,s2,…,sn)描述，其中si表示第i個傳感器，如圖1所示。每個節點通過三角剖分[14]都有它的位置信息，節點si位置用(xi，yi)表示，且每個節點具有唯一的ID、相同的計算通信能力和能量資源。節點通過時間同步服務[15]達到寬松的時間同步，通信接入采用CSMA/CA以減小信道沖突。本文的目標是在此N個節點的網絡中構建融合樹，AT由Nt個節點組成，叫作樹節點，樹節點用于接收并融合數據，其余(N-Nt)個節點叫作非樹節點(NT, not tree node)，每個NT節點感知指定區域事件屬性的變化，并將感知數據傳輸到它最鄰近的樹節點。構建的AT擴展到整個網絡，以便Nt個樹節點均勻一致地分布在網絡中，這樣，可以確保檢測屬性值以盡可能小的跳數由NT節點傳送到對應的樹節點，從而延長網絡的壽命。為簡便起見，Pevent(在圖1中矩形框里的虛線表示)代表事件，Revent表示事件區域且ReventR?。正常情況下，AT覆蓋檢測區域里所有的事件。R＇定義為R中沒有被覆蓋的部分，即R′= R-Revent。

圖1 網絡模型

2.2 樹的生成

某事件的發生會觸發網絡中的部分節點使其讀數異常，這可能是一個孤立點，也可能是多個。為確保AT擴散到整個網絡，感知值由傳感節點通過較小的跳數傳輸到相應的樹節點，盡可能保持分散節點的拓撲穩定性以維持原有較好的感知覆蓋范圍，為此引入了Voronoi圖以及相關Delaunay三角網絡來描述感知網絡拓撲[17]，并基于 Delaunay三角定義，構建以事件中心節點為根的感知網絡融合樹——伸展樹。伸展樹是一種二叉樹，其優點在于不需要記錄用于平衡樹的冗余信息。設e為平面上的點，則

稱為Voronoi多邊形。則Voronoi圖定義為

即平面上所有Voronoi多邊形的集合，而Delaunay三角網絡則為連接所有相鄰的 V-多邊形的生長中心所形成。Delaunay 三角網具有很多重要的性質[17]，通過Delaunay 表達不僅可以獲得每個節點的鄰節點信息，而且可以用來查找最接近的節點。基于傳感器網絡的 Delaunay 描述，構建以事件中心節點為根的伸展樹。設目標區域為A，區域中的感知節點集為

其中，(xi，yi)為節點si的位置坐標。由節點集S構成網絡對應的加權無向圖為G，各邊所對應的權值為節點間距離。并設感知區域外存在點集K={ki(xi，yi) | ki?A}，則目標區域中以節點si為中心相對于點集K的節點伸展樹定義為T，有：

其中， p ath( si-＞ ki)為無向圖G中從si到ki的節點間的最大跨度路徑，其長度為l。在此路徑上，各節點間的最小距離大于或等于G中任何其他從si到ki路徑上節點間的最小距離。最大跨度路徑反映了兩節點之間具有伸展性的一條通路。需要指出的是，在一個特定的無向圖G 中，兩點間的最大跨度路徑并不唯一，可能存在多條。而對于不同的域外節點集，相應的以根節點為中心的伸展樹也并不唯一。

設樹的深度為p，樹節點存儲感知的屬性值， 這樣的樹被認為是平衡的，它減少了數據丟失增加了數據融合的精確性[15]。算法Form_AT是由給定的深度創建伸展樹。每當一個節點要選擇它的2個孩子時，就選擇跨度最大的2個節點，可確保樹在擴散時覆蓋盡可能多的感興趣區域，伸展樹形成后，各子區域中所有剩余節點向距離自己最近的樹節點發送數據。本文通過3種消息即Beacon、Probe和Join實現樹的構建。圖2描述了消息交換構建融合樹的過程。

圖2 消息交換構建融合樹

1) Beacon消息。

在d-跳鄰居發現過程中每個節點u在d-跳范圍內廣播Beacon消息NMu={Message，u，Hop}，其中 Message為消息類型， u為節點 ID，Hop字段為消息跳數計數，初始為0，接收到NMu的節點v將u加入自己的d-跳鄰居列表對接收到的一份或多份冗余 NMu，v選擇 Hop值最小的NMu， 將其Hop字段加1并更新Hopu,v=Hop，如果Hop＜d則繼續向鄰居廣播，然后v進入等待狀態。如果v在等待狀態時又偵聽到Hop+1＜Hopu,v的NMu，則記錄該消息并將Hop字段加1重復上述過程；否則v不作任何動作直到計時器超時。這里計時器時長可以設為網絡初始化階段時長。

對于來自不同節點的Beacon消息，接收節點v都執行相同的過程。圖3是Beacon消息處理過程的自動機表示。通過Beacon消息廣播每個節點v可以獲得 d-跳范圍內節點集合，Hopu,v表示由這種帶跳數更新的廣播重傳過程所得到的節點u，v之間的近似最短路徑跳數。由于傳感器網絡靜態部署，對每個節點u，是穩定的。這里即為所有可能樹節點成員的集合。在 j層的每一個節點向它所有的下一跳鄰居廣播一個Beacon包，這樣，j+1層的節點從j層接收到多個Beacon包，從中隨機選取一個概率值p′ ＞ p′的節點作為它們的父節點，并向它發送一個Probe包。

圖3 節點的Beacon通知消息處理過程

從圖2可以看出，節點d從A和B接收Beacon，p′（該算法的一個輸入）的值按如下方法優化。

設父節點i以通信半徑 r，向圓心角為120°的扇形區域廣播它的 Beacon消息，該扇形區的面積為

這個區域的節點數為

其中，p為樹的深度。按如下的二項式分布，選擇區域內概率為p′的2個節點作為它們的父節點。

如果一個節點從預期的父節點那里接收到了多個Beacon消息，那么它們的ID將會被新選擇的父節點所保存，以便于在節點失敗的情況下快速恢復。

2) Probe消息。

選定的父節點等待從它的孩子節點處接收Probe分組，之后，決定選擇哪2個作為它的孩子節點。一旦它收到了它的下一跳j+1層所有節點的消息，就會選擇離它最遠的2個節點作為它的孩子。那些沒有被任何父節點所選擇的節點將不再嘗試成為AT的成員而轉化為感知節點，這樣，樹(因為傳感通信的代價遠大于存儲的代價)的大小能適當減小。從圖2可以看出，節點d選擇B作為它的父節點，并向它發送一個Probe分組，而后，節點A向節點a、b、c和d發送Beacon消息但是僅從節點a、b和c接收到Probe分組。

3) Join 消息

父節點在選擇了孩子之后，向它們發送一個Join消息，宣布將它們加入該樹。從圖2可以看出，A選擇節點a和c作為它們的孩子，而a和c距離A比a和b或者b和c都遠。

融合樹構建算法Form_AT(p，p")描述如下。

輸入：樹的深度p和父節點選擇概率。

輸出：深度為p的二叉樹Tc且每一個節點分配唯一的ID

1) 對于第j層，深度從0到p-1的每一個節點i從 1到2j；

2) Mi是j +1層的一個節點；

3) ni是在j層上的一個節點；

4) 在Mi的通信范圍內的節點ni(Mi＜ r),發送包含其ID 的Beacon包到Mi；/* r為通信半徑 */

5) 對于大于p"且跨越路徑長度最大的節點ni,Mi選擇它作為其父節點；

6) Mi發送 Probe 包到 ni；

7) ni等待 NWAIT 時刻(恰當的時間周期)從選擇ni作為父節點的Mi接受Probe包。

對于傳感器網絡來說，在最大跨度路徑上的節點具有較好的分散性，減少了由于覆蓋重疊而對網絡感知能力所造成的影響，因此這些分散性好的節點需要保持。通過節點伸展樹的定義，確定了傳感器網絡中需要保持的節點集。基于此節點集，對于覆蓋重疊節點也可有效地提高網絡整體的感知能力。

2.3 數據融合

基于伸展樹的數據融合算法的主要思想是采用傳輸能夠擬合較多的檢測數據的模型 M 來代替傳輸節點的檢測數據，其目的是為了減少數據傳輸量，從而節省傳感器節點的能量。因此需要考慮回傳以參數表示的模型的代價和其可擬合的數據量之間的關系。傳輸模型的代價越小其能夠表示的數據越多，節點就越節省能量。由于節點檢測值往往要受多個因素的影響，期望用最小代價模型擬合最多的數據，且計算簡單，而多元線性回歸模型恰好符合這一目標。

融合樹中的每個節點接收并存儲由最近的非樹節點周期性報告給它的數據，即NT節點負責感知而AT節點負責存儲，將存儲在AT節點里的值看作是輸入x-y坐標的函數值，此過程由三元組(f，x，y)描述，這里 f為位于(x，y)處節點的感知估計值，由AT中存儲在節點i的數據及其子節點發送的多元回歸模型的系數執行多元線性函數回歸生成。下面討論這種數據融合過程。

設多元線性回歸模型形式如下[18]：

其中，Y為感知估計值，Xj(j=1, 2, …，k)為對感知估計值Y發生作用的影響因子，βj(j=0, 1, 2, …, k)為k+1個未知回歸參數，μ為隨機誤差項。由于參數βj(j=0, 1, 2, …, k)都是未知的，可以利用樣本觀測值(x1i, x2i, …, xki；Yi)對它們進行估計，由此得到的參數估計值為用參數估計值替代回歸模型的未知參數βj(j=0, 1, 2,…, k)，則得到多元線性樣本回歸方程為

將上述k+1個方程化簡得下列方程組：

其矩陣形式為

經化簡得如下方程：

設R(X)=K+1， XtX為(K+1)階方陣，則 XtX滿秩，其逆矩陣存在，所以β的最小二乘估計向量為

運用多項式回歸，得到如下方程：

其中，

數據融合算法SPAT(p, ns)描述如下：/* ns為感知節點向樹節點報告的平均數*/

圖4 融合過程中邊界區域的計算

1) 對于樹中的每一個葉節點i

其節點的數據被讀取；

執行多元線性回歸，其系數 β0，β1,…,β8被存儲；

2) 初始樹的深度為2p

While 當 p ＞0 時

sum = level + 2p-1

k = level

while k ＜ sum

3) 對于樹中的每個非葉節點 k，在(xmin, ymin)和(xmax, ymax)的范圍內計算其位置x-y點報告給它的2個孩子節點i 和i+l；

4) 計算新的(βi0, βi1,…,βi8)和(β(i+1)0,β(i+1)1,…,β(i+1)8) ,添加到節點k的信息中，然后調用回歸函數計算(βk0,…,βk8) ,傳輸到它的父節點；

5) 轉到下一級深度繼續。

相對于傳輸原始數據到 Sink節點的能量消耗和時延，通過SPAT融合過程報告數據更為有效。在AT中，設壓縮比定義為將原始數據壓縮之后再傳送的字節數與原始數據之比。設深度為 p的AT共有 t = 2(p+1)- 1個樹節點，每個大小為wi字節的數據分組包含感知讀數和該讀數所對應的位置坐標。這樣，輸入到每個葉子節點的字節數大小為nswi，其中ns為感知節點向樹節點報告的平均數。所以，傳輸到葉節點的字節數

除了從感知節點讀取檢測值以外，每個非葉節點用從它的2個孩子那里得到值作為輸入來更新系數和區域邊界的x-y值。所以，輸入到非葉子節點的字節總數Tnl為

從樹節點獲得大小為(wx+ wy+ wc)字節的輸出分組(包括系數和x-y的范圍)。

從所有節點輸出的字節總數 T0= ( wx+ wy+wc)× (2p-1- 1 )s，那么壓縮比為

其中，t為樹節點總數，lt為葉子節點數。

3 事件區域檢測

在許多應用中，使用函數 σ (i, t)=F (v1, v2,…,vk)來描述檢測區域的狀態信息(如溫度，濕氣等)，這些信息由感知傳感器 i∈N在時刻 t獲得，其中 vk是影響傳感器讀數的參數。一般來說，由于已知或未知因素的影響，很難得到準確的函數表達形式。除一些特例外，時間變化以及線性或非線性的其他因素也可能會影響檢測讀數，而這些因素很難形式化表示。例如，一個溫度傳感器的讀數受很多因素的影響，如地點、天氣、時間等。本文不是設法得到一個確切的函數表示，而是形式化函數F的基本屬性，從而分析傳感器的讀數σ(i,t) 。

3.1 事件區域檢測的性質

設傳感器節點對某一區域的檢測讀數，有以下性質：

1) 每個傳感器節點是獨立的；

2) 存在 2個常量 Cmin和 Cmax(Cmin≤σ(i, t)≤ Cmax)，分別是傳感器檢測獲得讀數的最小和最大值；

3) 在[Cmin, Cmax]內，σ(i, t)連續且服從密度函數為φ(i)的正態分布，期望值為

性質 1）說明傳感器獨立地檢測環境變化，性質 2）說明正常傳感器讀數的變化范圍，性質 3）說明，傳感器檢測讀數的變化空間，由適合正態分布的應用事例確定，如每日氣溫、風速等。本文對正常與錯誤讀數的判定條件如下。

正常讀數：通常情況下，檢測讀數σ(i, t)在[Cmin,Cmax]內且服從正態分布φ(i)，若存在τ1＞0，使得檢測讀數滿足 |σ (i, t) - E (i )|≥τ1，說明傳感器讀數超出了正常范圍。滿足該條件的節點越多，事件發生的可能性就越大。

錯誤讀數：對于傳感器i，φ(i)滿足以下3個條件中的任一個，該傳感器可能為故障傳感器，其檢測產生的讀數為錯誤讀數。

1) 若存在τ1，τth且τth＞τ1＞0，對于? t, | σ(i, t)-E(i)|≥τth，說明傳感器的讀數超出了正常范圍，它很可能是有故障的。如果傳感器頻繁或者持續報告這樣的讀數，那么認為這個傳感器是有故障的。

2) 在事件報告的幾個連續時期，有|σ(i,( t+1)-σ( i, t )|≈ 0 ，若存在常數c，使得節點i的鄰居傳感器 i′滿足|σ(i′,(t+1 ) - σ (i′, t )|＞c，即鄰居傳感器 i′讀數隨著時間的推移發生變化，而傳感器i的讀數卻是恒定的，那么傳感器i是有故障的。同理，在一個特定的階段，有|σ(i',(t+1 )-σ (i', t )|≈ 0 ，如果一個傳感器 i的鄰居傳感器 i'檢測到一個很小的讀數變化，傳感器i的讀數卻有很大的變化，那么這個傳感器i是有故障的。

3) ?t ,Cmin＜ σ (i, t) ＜ Cmax, σ( i,t+1) ＞ τ2,Cmin＜σ( i, t + 2 )＜Cmax, σ(i, t + 3 ) ＞τ2,這個條件表明傳感器的讀數呈不規則變化，那么傳感器i是有故障的。例如，傳感器的讀數周期性地或間歇地從正常讀數變化到事件讀數，再變化到正常讀數。

為提高檢測讀數的準確性，首先要識別有故障的傳感器。由性質1)可知，通過對當前讀數σ(i, t)與期望值E(i)進行比較判定i是否發生了故障，設樹節點的數量 nt總是滿足條件 nt? 3 nnmax+1，其中ntmax表示故障樹節點的最大數量，該條件確保有故障的傳感器能被有效識別[10]。另一方面，為增加有故障節點事件檢測的置信度，每隔一個時間間隔，對可疑傳感器是否為故障點進行判斷，一旦檢測到故障節點，立即隔離。設ri是函數σ(i, t)的一個實例，這里σ(i, t)表示在一個特定時刻傳感器的讀數(如溫度、聲音，氧氣密度等)。在沒有錯誤的檢測數據時，事件定義為傳感器的異常讀數，有如下定理。

定理 1 當事件發生時，存在σ＞ 0，使|ri- E (rr) |＞ σ 。

證明 (反證法)如果|ri- E (rr)|= 0，那么傳感器的讀數與期望值相同。這表明在沒有事件發生的時，ri不變，這與事件的定義矛盾。

為了使樹節點獲取它周圍NT節點讀數的特征值，定義di作為樹節點在時刻t從它周圍的NT節點獲得讀數的平均值。由性質 1）知，每個傳感器的讀數不依賴于其他節點，由性質 3）知傳感器讀數服從正態分布，如事件沒有發生，檢測讀數di仍然服從正態分布 φ ( di)，這樣， φ ( di)的期望值其中是向樹節點發送報告的平均數。

定理2 當事件發生時，存在τ1≥0，有|di-E(di)|≥τ1，且隨著τ1的增加，事件發生的概率也增加。

證明 根據正態分布，當|ri- E (ri)|=0時，事件ri發生的概率很低，當φ(i)遠離E(ri)時ri發生的概率很高。有 ns個傳感器時，有這樣，當τ1= 0時，事件發生的概率最低，且隨τ1的增加而增加。

從理論上說，通過概率分布函數(φ(i)或φ( di))，可以計算期望值。然而，在現實世界中，一個傳感器事先獲知參數φ(i)或φ( di)是不現實的。當沒有事件發生時，讀數di在一定范圍之內是隨機分布的。所以，di可以從隨機選擇事例的讀數中抽樣。從抽樣讀數集合中計算漸進的 E(di)，E(di) =(d1+d2+…+dn)/N，其中N是歷史數據樣本的大小。這樣，將錯誤讀數的條件1)也可改為 |σ (i, t) - E (di)|＞τ2，在條件2)，用di替換σ(i, t)。通過比較當前讀數di與期望數據 E(di)檢測事件的發生。注意到，在|di-E(di)|＞τ1且τ1＞0的情況下，即使沒有事件發生，| di- E (di)|＞ τ1也可以被滿足，但不能說明某事件已經發生。然而，如定理2所述，如果增加τ1的值，以該值為閾值，事件發生的概率增加到接近100%。

3.2 單事件檢測

當一個葉節點從它周圍的 NT節點接收讀數時，依賴于thτ是否超界來計算事件的多元回歸方程fevent或正常現象的多元回歸方程f。當一個父節點從它的孩子節點處接收讀數時，同時也從它自己的NT節點周圍采集數據并確定在它的區域范圍內是否有事件發生。多項式可以是fevent或f，取決于父節點是否位于該事件區域，如果父節點同它的孩子節點位于同一區域，那么它將更新孩子節點的數據，并用它自己的接收數據計算一個新的多項式；如果父節點和相應的孩子節點處于不同的事件區域，那么孩子節點的數據不改變。這個過程一直繼續，直到根節點接收到2個多項式和相對應的范圍信息。按照從孩子節點接收的fevent和相對應的范圍，根節點就可以根據事件位置信息估計事件的邊界及Pevent的覆蓋范圍。

圖1顯示了通過融合樹 AT檢測 Pevent的一部分，Pevent發生在Revent的內部，在R的一個角落，父節點A和它的2個孩子節點B與C所在子樹位于Revent事件區域內，此時，B和C從NT節點那里接收到的讀數其偏差遠大于τth(即|di- E ( di)|＞ τth)。另外，B的孩子節點也在Revent中。因此，B節點從它的2個孩子節點處接收到了回歸方程的系數。因為B節點本身也從最近的NT節點接收到了偏差遠大于邊界的數據，所以它產生了一個自己的報告和更新數據后的新fevent，然后把新的fevent和相應的范圍值傳給它的父節點A。在父節點為C的子樹中，其中一個孩子D在Revent中，而另一個孩子E卻在R中。C接收多項式 fevent(從節點 D)、f(從節點 E)及相應的坐標范圍{xdmin，ydmin，xdmax，ydmax}和{xemin，yemin，xemax，yemax}。通過觀察由它本身和它的2個孩子傳送數據的近似區域，C得出這樣一個結論：D和它位于同一個區域內。因此，D節點更新數據再結合它自己的檢測數據產生一個新的fevent，然后C把fevent及D的坐標范圍、未變化的f及E的坐標范圍傳送給A。這樣當它沿著AT映射到Revent中包含多個樹節點的區域時，這些范圍不斷被更新。當根節點接收一個子節點處的范圍和fevent，根據事件Pevent和它的域范圍得到一個估計值。

3.3 多事件檢測

相對單事件而言，多事件發生時樹節點之間交換的數據分組、計算復雜性都將提高，隨著事件源的增加，每個事件影響程度卻會減小[17]。考慮到這種現象，本文設計的檢測方法其基本思路如下：當數據分組被傳輸到樹節點時，如果其中一個子節點有與父節點相同或相近的數據集，則結合2個數據集形成一個新的多項式；如果沒有子節點同父節點相同的數據集，則通過數據變換以及范圍變換來構建融合樹；如果2個子節點數值接近，則合并它們的檢測范圍得到一個更大的區域。

設在某矩形區域里，存在2個異常事件和一種正常現象。如圖5所示，在區域R里發生了2個事件 Pevent1和Pevent2。B檢測事件Pevent2，而它的孩子節點C和D分別檢測Pevent1和一種正常現象，在這種情況下，C和D把它們各自的多項式與坐標范圍{xcmin，ycmin，ycmax}以及{xdmin，ydmin，xdmax，ydmax}一起傳輸到B。B計算2個節點接收數據的最小值和最大值，得到它們的數據范圍。B將Scmax，Scmin，(Scmin，Scmax分別表示最小和最大的事件屬性值)C的坐標范圍以及 Sdmin，Sdmax，D的坐標范圍一起變換到 A。如果使用單一事件檢測方法，則需要6個數據分組，其中3個與3個多項式相對應，另外3個與3個區域范圍對應。此外，A的其他孩子節點G和D的讀數比較接近，所以，A把它們的范圍結合在一起，感知同一個事件Pevent2。然后，A創建新的多項式，將它的系數、區域范圍和事件屬性的最大最小值傳輸到它的父節點H，M的估計值同A發送的也一樣，結合N產生的數據之后，發送它的系數到根。由于H和I在R內，H沒有修改Pevent2事件的區域范圍且不加修改地傳送到根，由此確定了事件區域及其邊界。這樣，事件Pevent1和Pevent2都通過有限的計算檢測到了，且每棵樹僅執行了一次多項式回歸。

圖5 2個事件發生的檢測

3.4 故障節點檢測及錯誤讀數的控制

前面討論了基于融合樹方法完成事件區域檢測過程。但是，這個過程忽略了某些隱藏在事件區域內的故障傳感器產生的錯誤讀數。由于傳感器的讀數在計算最后的多項式fevent時被樹節點結合成一體并代表事件的特征，錯誤讀數必定影響這個結果的準確性。這一部分，分析在網絡模型里如何檢測故障傳感器節點。

由融合樹的構造過程可以看出，R中的AT分布廣泛，以至于從網絡的所有角落都能夠接收數據，這樣可確保更好的空間逼近，因為樹中的每個節點選擇2個離它最遠的節點作為孩子，對密度較大的網絡而言，如果NT節點是有故障的，將向最近的樹節點報告錯誤讀數。從文獻[6]獲知，除非傳感器位于事件的邊界，否則節點k的鄰居節點的讀數與節點k的讀數近似。圖6描述了故障傳感器的檢測過程，圓形表示節點的傳感區域，此方法可以被擴展到檢測多個故障點。

圖6 故障節點的檢測與報告

設M是有故障的NT節點，將讀數傳輸到離它最近的樹節點G，如圖6(b)所示。M四周的傳感節點正在傳送正確的溫度，節點M的異常讀數81，此時|σ(i, t) - E(di)|＞τth。由于M 4個方向的鄰節點傳送正確的可接受的讀數(除了M)，因此M被看成是有故障的節點。如果M在接下來的幾次連續報告讀數，滿足|σ(i, t) - E(di)|＞τth時，它將被禁止傳輸數據。因此，為了預防錯誤數據影響最終多項式構建，M發出的讀數將在檢測進程中被剔除。

需要說明的是，樹節點本身不能做出正確的判定，判定是通過每一個樹節點傳播它的位置(x, y)及其函數值f(x,y)到AT中的其他節點經計算形成的。為保證傳輸信息量可控，按以下步驟交換故障 NT節點信息。

1) 從Sink開始，以Sink為中心，fevent被發送到所有的樹節點，最壞情況下需要(nt-1)次的數據分組傳送。

2) 對當前的樹節點j，接收M發送的數據并且驗證M是否是故障節點，正向路徑轉發(x, y)和f(x,y)到所有j在樹中的鄰節點。

3) 當收到這樣一個數據分組時，節點i首先轉發該數據分組到它的鄰節點，發送分組的節點除外。接著，節點i更新M在4個方向上的鄰節點位置，并且使用它們的多項式重新生成在這些位置上的數據值。使用這些數據值，通過檢查是否滿足判定錯誤讀數的3個條件之一，i作出M是有故障的還是正常的判斷。當M落在2個事件區域邊界時，存在2種不同的讀數，雖然正常但還是被拒絕。

4) 相對以前的正向路徑，以反方向通過節點i傳播M是故障節點或是正常節點的消息。每一個節點接收到M的消息后，作為主要依據更新自身的判定。然后，它再一次以反方向轉發它的判定，最后，節點j作出拒絕或接受M節點讀數的決定。

如圖1所示，一個故障NT節點M發送它的讀數到它最鄰近的節點N，N認為M是有故障的，則發送它的位置和讀數f(x，y)到它所有的鄰居節點。每一個鄰居節點收到消息后，產生一些與M近似的位置信息，同時通過它的多項式產生在這些位置的讀數。然后，把M的f(x，y)值與這些新產生的值比較，檢查是否滿足傳感器故障判定條件。接下來，它向在相反路徑中的所有節點廣播它的檢測報告，每一個樹節點接收它的鄰居節點發送的讀數，在收到大多數判定的基礎上，M被歸類為有故障的還是正常的。最后，在大多數來自鄰接樹節點讀數的基礎上，N作出關于M為故障節點的正確判定。

4 影響性能的因素

1) 構建AT的影響。

當增加融合樹AT的深度時，執行回歸次數增加，多項式可能偏離原始數據更多。為了避免這些影響，AT的孩子節點數量可進一步增加，而不增加樹的深度，使得AT度高而深度小。然而，由于孩子節點數量的增加也使每個父節點的計算時間增加，因此，事件檢測應該在AT的基礎上進行，這樣可在精確度和計算延遲之間達到平衡。由于每個樹節點融合了傳感器的讀數，計算開銷是O(n/nt)，這里，nt是樹節點的數量，如果nt與n同步增長，計算的開銷就可以保持不變[17～19]。

2) 多項式次數的影響。

多項式的次數對獲得的事件的邊界和區域信息有一定的影響。在某區域內，如果大量的傳感器(?20)向單一樹節點發送報告，就需要一個三次多項式來提高事件邊界的精確度。三次多項式將會有27個系數。具有27個系數的三次多項式與二次多項式的9個系數比較[18]，增大了樹節點向其父節點發送的數據分組的大小。然而，與大量的傳感器讀數相比較，27個系數是非常少的，因為傳感器讀數都被融合到若干系數中了。

3) 故障傳感器的影響。

在第4節用τ2表示故障傳感器檢測的閾值。如果錯誤的讀數沒有使|di-E(di)|超過τ2的定義值，樹節點就不會報告任何錯誤讀數，隱藏了故障傳感器的存在，將影響事件檢測的準確性。

4)τth的影響。

在事件區域檢測中，為事件檢測尋找一個合適的閾值是重要的。根據定理2，即使沒有事件發生，τth較小會導致頻繁的發送事件報告。相反，τth較大可能忽略事件的發生。在設置τth時應該考慮2個因素，一是正態分布密度函數 φ ( di)，一是樹節點樣本的大小nt。如第3節所述，σ(i, t)的最大和最小分別為Cmax和Cmin，樹節點從它周圍的傳感器收集數據時，di的最大值和最小值分別用 Cm′in和Cm′ax表示，沒有事件發生時，依照φ ( di)，di在限定范圍內服從正態分布，有 E(di)- Cm′in= Cm′ax-E(di)。設τth=E(di)-Cm′in。對任何給定的di，如果di＞τth，并且在nt個傳感器之中至少有一個傳感器是在邊界范圍之外，排除了故障傳感器，可以說事件發生了。

5 仿真實驗與討論

本文采用離散事件仿真平臺 NS2進行模擬實驗，通信接入采用CSMA/CA協議，選擇溫度屬性評估所提出方案的有效性，表1定義了所使用的參變量。設區域 A中節點總數為 D，則節點密度ρ=D/A，As是包含單一融合樹Tc的子區域，因此在子區域里節點的平均數U由As確定，對于二叉樹，節點總數為 t = 2(p+1)- 1 。

表1 仿真實驗參數設置

此外，ns由前面設定，即感知節點向樹節點報告的平均數，子區域里節點數U的上界為[15]

利用式(1)替換t，得AT深度的一個最優解：

設 D=1 630，A=800×800。有 ρ =1630/8002=0.0025,As= 4 00 × 4 00，則該區域內節點平均數為：U=0.002 469×400＋400=408。設樹的深度p=4，則節點數 Tc=t=2(4+1)-1=31，ns=12。此區域傳感節點總數=31×12=372。事實上，該區域內的節點總數 U=31+372=403＜408。因此，上面所定義的參數是有效的。

5.1 性能評估測度

在800×800平方單元區域R內，隨機部署250個節點，溫度變化 30℃～35℃是正常現象，溫度變化在 39℃～49℃時為異常，可能是該區域發生了火災。樹的深度設置為 4。在無事件發生時，檢測的溫度值服從正態分布φ(i)。Cmin、Cmax和E(i)分別為30、35和32.5，φ(i)的變化是1.2。單個事件Pevernt1在中心發生，事件區域稱為Revent，E(di)- Cmin= Cmax-E(di)=2.5，τ1為2.5，E(σ( i, t) ) - Cmin= Cmax-E(σ(i,t))=2.5且τ2=τth=4.5。當事件發生時，讀取的數據通過NT節點傳輸到最近的樹節點，通過10輪實驗評估以下性能指標。前提是假設查詢已經廣播到融合樹的所有葉節點。

1) 壓縮比(compress ratio)。2) 根節點輸出數據分組的大小。3) 事件邊界(event boundary)：將實際事件邊界(不同的形狀)和檢測到的事件邊界進行比較。4) 錯誤率(percentage error)：AT中根節點獲得的讀數與實際傳感器讀數的近似程度。由事件區域檢測的讀數與實際讀數產生的偏差E表示，其中εth=10%是指定的錯誤閾值，nb是在邊界傳感器的數量，為近似讀數，z為實際讀數。5) 事件識別延遲(event recognition delay)：事件發生的時間與在根節點計算的近似時間之間的間隔。6)通信代價(communication cost)：事件區域檢測傳輸數據分組的平均數。7) 故障點識別延遲(faulty sensor recognition delay)：從故障節點發送讀數到錯誤讀數在融合過程中被消除的時間，通過平均延遲和故障傳感器的百分率之比表示。8) 包負載(packet overhead)：檢測到故障節點時，樹節點向鄰近節點發送數據分組的總數。9) 讀數誤差(variance of sensor reading)：通過NT節點集（包括故障節點）報告的數據di與它們的平均值E(di)的差異來評估。10) 故障傳感器檢測命中率(faulty sensor detection hit ratio)：設nft表示網絡中發送數據到樹節點的故障傳感器數，nf表示網絡中故障傳感器的實際數目，檢測命中率為

5.2 仿真結果與討論

5.2.1 壓縮比

圖 7顯示了壓縮比隨著樹的深度而變化的情況，正如所期望的那樣，幾乎為常量0.02。曲線的下降說明隨著深度的增加，壓縮比減小，樹的深度越深，壓縮程度越好，而且輸出量大大減少。高壓縮比減小了整體的信息量，因而節省了通信帶寬和總的能量。

圖7 壓縮比與樹深度的關系

5.2.2 根節點輸出數據分組的大小

圖8顯示了在根節點處通過SPAT算法進行數據融合之后的數據通信量以及根節點收到未融合數據而進行正常的一對多通信的情況。盡管樹的深度不同，但當融合樹中所有節點執行數據壓縮時，數據分組通過根節點傳送到 Sink的大小是恒定不變的，即固定(wx+wy+wc)個字節。從一個樹節點到另一個樹節點所傳送的數據分組大小幾乎是恒定的，且與網絡規模的大小無關，使得數據傳輸的總能量維持在合理的范圍。這印證了上面的假設，即每個樹節點傳送的數據分組僅包含系數和x-y坐標值到它的父節點，數據分組的大小獨立于樹中節點的數目。而傳統的多對一通信，所有的葉子節點都要向根節點發送數據，所以，當網絡節點增加時，通過根節點傳送的數據分組大小的增長不受限制。通過本算法執行數據壓縮時，與文獻[8]相比較，最大數據通信量減少85%。

圖8 數據融合與未融合的通信量對比

5.2.3 邊界檢測

當具有不同邊界的多事件同時發生時，為了討論基于融合樹的事件區域檢測性能，在R的角落里5℃～10℃變化范圍內引入第二個事件 Pevent2，圖 9所示。邊界檢測由虛邊矩形描述，圖中的黑色小圓點表示融合樹的樹節點。實驗結果表明，Pevent1與Pevent2的錯誤率分別為7.8%和8.5%。可以看出，通過檢測計算的事件區域（即虛邊矩形）與實際事件區域（即粗邊矩形和粗邊橢圓）是匹配的，這證實ATERD是有效的。然而，由于ATERD得出的事件區域總是一個矩形（由于事件區域是利用無數個小矩形迭代構建而成），若事件自身就是矩形的，其近似效果要比利用其他形狀（如橢圓）更接近原型。

圖9 ATERD檢測的事件邊界

5.2.4 錯誤率

圖 10顯示了融合樹的深度與錯誤率的關系。可以看出，隨著融合樹深度的增加，樹節點覆蓋的范圍會更大，從而使得整個區域能被更好地感知檢測，同時近似數據的平均誤差及錯誤率也穩步下降，這正是所期望的。樹深度為1時，錯誤率達到最大值，是由于這棵樹僅有3個節點（區域內的大多數傳感節點被分散，不在樹節點的感知范圍內，因此無法向AT傳送）檢測該區域范圍。圖11顯示樹的深度為4時，錯誤率漸進增大達到最大值5.64。選取381個讀數，發現最初部分集中了接近估值的最大數目點。當樹的深度為4時，錯誤率最大值為5.64%，大部分節點都有它們各自的誤差但限于一個較小的范圍0%～1.68%。

圖10 錯誤率與樹深度的關系

圖11 樹的深度為4時的錯誤率

當通信范圍變化時，對ATERD完成事件檢測的準確性進行分析，如圖12所示，兩事件ATERD的誤差率不足10%，采用多事件ATERD進行事件檢測（誤差范圍為6.8～8.9）比單ATERD 進行事件檢測(誤差范圍為 6.4～7.6)高出 6%，單事件檢測出現較小的誤差范圍，是由于近似邊界可以通過最后生成的fevent較好定位，而在多事件ATERD方法中是無法實現的。由圖 12可以看出，被檢測事件的錯誤級別隨通信范圍的增長呈不顯著變化，而文獻[11]中，隨著通信范圍的增加，在區域Reven里有更多的傳感器讀數被傳送到樹，錯誤級別卻隨通信范圍的增長急劇增加，在ATERD中，不同的讀數與不同的事件相對應，樹節點會生成不同的多項式，總體誤差率是獨立于各個傳感器的通信范圍的。從圖12還可以看出，隨著NT節點的增加，錯誤率緩慢增加，樹節點、NT節點位于事件邊界的可能性也會增加，回歸多項式的準確性也會增加，進而覆蓋到相對大的范圍和提供更加準確的傳感參數，錯誤率被控制在一個合適的范圍內。

圖12 通信范圍、節點密度與錯誤率的關系

5.2.5 檢測延遲

圖 13表明，事件檢測延遲隨節點密度的增加幾乎保持不變。導致事件檢測延遲的主要因素有 3個方面：事件識別延遲、多項式計算延遲和事件報告的傳輸延遲（稱為通信延遲）。從圖13可以看出，事件識別和多項式計算延遲遠遠小于通信延遲，通信延遲占總延遲的近77%。一旦融合樹確定，用于通信的延遲保持恒定并且獨立于NT節點的密度。當節點密度增加，圍繞每棵樹的NT節點數目也隨之增加。實驗結果表明，當節點數目 nnt增加時，事件識別、計算負載和多項式構造也維持恒定，這是由于節點數目的增加對 ns的影響不大。ATERD之所以能夠降低事件識別和事件報告的復雜度是由基于以下原因：首先，在ATERD中，事件識別和基于多項式的數據融合不含有任何復雜計算；其次，基于樹的網絡結構對事件識別進行了局部處理；再者，當網絡規模增加時，樹節點的數目也相應增加，因此ATERD是可擴展的。

圖13 事件檢測、節點密度對延遲的影響

5.2.6 識別延遲

從圖 14可以看出，隨著故障傳感器所占百分比的增加，檢測時延也會緩慢增加。盡管由于密度的加大，傳遞給每個樹節點的NT節點數會增多，但是檢測故障傳感器所花費的計算時長卻是一個常量，同時增加的時延與每個樹節點之間傳遞數據的傳輸時延相比是可以忽略的，從下面的關系式可以明顯地看出：

其中，T表示總的時延，Ttrans表示傳輸時延，Tcalc表示計算時延。因此，故障節點增加所帶來的計算時延同傳輸時延相比是可以忽略的，這里的傳輸時延同NT節點以及樹節點的密度有關，也與故障傳感器的數量有關。這使得隨著故障節點所占百分比的增加，T呈線性增加。在文獻[14]中，計算時延主要發生在傳感器正在移動以及最優線性規劃 LP的計算過程中。在文獻[11]中，隨著故障節點的增加，鄰接點數據計算的平均值也將成比例的增加，在文獻[11]和文獻[14]中，這種時延的增加超過50%。

圖14 故障傳感器識別延遲

5.2.7 負載

隨著節點密度的變化，將本文提出的算法與文獻[8]的方法進行比較，如圖15所示。可以看出，隨著節點密度的增加（假設故障節點的數目保持不變）對本文所提出的算法幾乎沒有影響，這是由于，融合樹算法識別故障傳感器節點數目保持不變，每個節點只發送故障傳感器的值(x, y, f(x, y))到其他樹節點，與節點密度的增加無關。與此相反，在文獻[8]，隨著節點密度的增加，每一故障傳感器的鄰接節點數目增加，識別故障傳感器的分組交換增多。另外，故障傳感器在源頭沒有被檢測到，并且會傳播給BS，同時還會導致數據負載的增加。

圖15 分組負載與網絡密度的關系

5.2.8 命中率

圖 16顯示了本文算法在檢測故障傳感器時的準確性。可以看出，隨著節點密度的增加，命中率平穩遞增，構建AT的速度更快，覆蓋的范圍更大，使得大部分NT節點都是可達的。因此，故障傳感器數量的增加（NT節點中的小部分）仍然可以確保大部分NT節點發送數據到最鄰近的樹節點，同時在早期就可以檢測故障節點。命中率可以達到94%。而文獻[8]的命中率只有62%。

圖16 節點密度與命中率的關系

6 結束語

本文針對無線傳感器網絡中容錯事件區域檢測問題，提出了一種新的分布式容錯檢測算法.首先，構建的融合樹，使得在缺少傳感節點的位置，利用被檢測事件的時空相關性，也能獲得事件檢測的屬性值，其錯誤率控制在可接受的范圍內。在此基礎上，提出一種基于融合樹的事件區域檢測容錯算法，該算法可以對多個事件進行檢測，識別發生在邊界區域的事件和有故障的傳感器節點，把檢測讀數傳給基站。另外，強調異常事件發生節點的重要性，使得事件區域檢測問題，以及事件區域邊界節點的錯誤修正問題得到較好的改善。

[1] 李建中, 李金寶, 石勝飛.傳感器網絡及其數據管理的概念問題與進展[J]. 軟件學報,2003,14(10)∶ 1717-1727.LI J Z, LI J B,SHI S F. Concepts, issues and advance of sensor networks and data management of sensor networks[J].Journal of Software,2003,14(10)∶1717-1727.

[2] 曹冬磊, 曹建農, 金蓓弘.一種無線傳感器網絡中事件區域檢測的容錯算法[J].計算機學報,2007,30(10)∶1770-1776.CAO D L,CAO J N,JIN B H.A fault-tolerant algorithm for event region detection in wireless sensor networks[J].Journal of Computer,2007,30(10)∶1770-1776.

[3] 任豐原,黃海寧,林闖.無線傳感器網絡[J].軟件學報,2003,14(7)∶1282-1291.REN F Y,HUANG H N,LIN C. Wireless sensor networks[J].Journal of Software, 2003,14(7)∶1282-1291.

[4] KRISHNAMACHARI B, IYENGAR S S. Distributed Bayesian algorithms for fault-tolerant event region detection in wireless sensor networks[J]. IEEE Trans on Computers, 2004,53(3)∶241-250.

[5] CHEN Q, LAM K Y, FAN P. Comments on, distributed Bayesian algorithms for fault tolerant event region detection in wireless sensor networks[J]. IEEE Transactions on Computers, 2005, 54(9)∶ 1182-1183.

[6] LUO X, DONG M, HUANG Y. On distributed fault-tolerant detection in wireless sensor networks[J]. IEEE Trans on Computers, 2006,55(1)∶58-70.

[7] KOUSHANFAR F, POTKONJAK M, SANGIOVANNI- VINCENTELLI A. On-line fault detection of sensor measurements[A]. Proc of the IEEE Sensors[C]. 2003.974-979.

[8] DING M, CHEN D, et al. Localized fault tolerant event boundary detection in sensor networks[A]. Proceedings of the Annual IEEE Conference on Computer Communications (INFOCOM)[C]. Miami,2005.902-913.

[9] KOUSHANFAR F, POTKONJAK M, SANGIOVANNI-VINCENTELLI A. Fault-Tolerance in Sensor Networks[M]. Handbook of Sensor Networks, CRC Press, 2004.

[10] REN K, ZENG K, LOU W J. Secure and fault-tolerant event boundary detection in wireless sensor networks[J]. IEEE Transactions on Wireless Communications, 2008, 7(1)∶ 354-363.

[11] CHEN J, KHER S, SOMANI A. Distributed fault detection of wireless sensor networks[A]. Proc of the 2006 Workshop on Dependability Issues in Wireless Ad Hoc Networks and Sensor Networks (DIWANS 2006)[C]. 2006.65-72.

[12] KOUSHANFAR F, POTKONJAK M, SANGIOVANNI- VINCENTELLI A. Error models for light sensors by statistical analysis of raw sensor measurements[A]. Proc of the IEEE Sensors[C]. 2004.1472-1475.

[13] NOWAK R, MITRA U. Boundary estimation in sensor networks∶theory and methods[A]. Proc of 2nd International Workshop on IPSN[C]. 2003.86-95.

[14] CHINTALAPUDI K K, GOVINDAN R. Localized edge detection in sensor fields[A]. Proc IEEE Workshop on Sensor Network Protocols and Applications[C]. Los Angeles, 2003.59-70.

[15] GUESTRIN C, BODI P, THIBAU R, et al. Distributed Regression∶ an Efficient Framework for Modeling Sensor Network Data[M]. IPSN New York, ACM Press, 2004.

[16] SHARAF A, BEAVER J, LABRINIDIS A, et al. Balancing energy efficiency and quality of aggregate data in sensor networks[J]. The VLDB Journal, 2004, 13(4)∶384-403.

[17] AURENHAMMERF, KLEIN R. Handbook of Computational Geometry[M]. Amsterdam, Netherlands∶ North-Holland, 2000.201-290.

[18] BERTHOLD M. Intelligent Data Analysis[M]. Springer Press,2nd Edition, 2007.

[19] VURAN M C, AKAN O B, AKYILDIZ I F. Spatio-temporal correlation∶ theory and application for wireless sensor networks[J]. Computer Networks, 2004,45∶245-259.