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

(1. 蘇州大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，江蘇 蘇州 215006；2. 江蘇省現(xiàn)代企業(yè)信息化應(yīng)用支撐軟件工程技術(shù)研發(fā)中心，江蘇 蘇州 215104)

1 引言

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

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

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

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

針對目前在上述方面研究的不足，本文提出了一種基于融合樹的事件區(qū)域檢測容錯算法，改算法分為2個階段。首先，構(gòu)建分布式融合樹，每個感知節(jié)點僅報告自己的感知數(shù)據(jù)到最鄰近的樹節(jié)點，樹節(jié)點執(zhí)行多元線性回歸，獲得事件區(qū)域檢測的估計值，傳輸?shù)氖敲枋鍪录^(qū)域檢測的多元回歸模型的系數(shù)，而不是實際的感知數(shù)據(jù)，Sink通過直接查詢根節(jié)點就可獲的感興趣區(qū)域內(nèi)任一位置的感知值，減少了事件區(qū)域檢測的通信代價和復(fù)雜性。其次，在所構(gòu)建融合樹的基礎(chǔ)上，可以對單個或多個同時發(fā)生的事件進行容錯檢測，識別有故障的傳感器節(jié)點和發(fā)生在邊界區(qū)域的事件，快速把檢測讀數(shù)傳給基站，減少數(shù)據(jù)傳輸?shù)哪芰肯暮脱舆t。

2 融合樹的構(gòu)建

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

2.1 網(wǎng)絡(luò)模型

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

圖1 網(wǎng)絡(luò)模型

2.2 樹的生成

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

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

即平面上所有Voronoi多邊形的集合，而Delaunay三角網(wǎng)絡(luò)則為連接所有相鄰的 V-多邊形的生長中心所形成。Delaunay 三角網(wǎng)具有很多重要的性質(zhì)[17]，通過Delaunay 表達不僅可以獲得每個節(jié)點的鄰節(jié)點信息，而且可以用來查找最接近的節(jié)點?；趥鞲衅骶W(wǎng)絡(luò)的 Delaunay 描述，構(gòu)建以事件中心節(jié)點為根的伸展樹。設(shè)目標(biāo)區(qū)域為A，區(qū)域中的感知節(jié)點集為

其中，(xi，yi)為節(jié)點si的位置坐標(biāo)。由節(jié)點集S構(gòu)成網(wǎng)絡(luò)對應(yīng)的加權(quán)無向圖為G，各邊所對應(yīng)的權(quán)值為節(jié)點間距離。并設(shè)感知區(qū)域外存在點集K={ki(xi，yi) | ki?A}，則目標(biāo)區(qū)域中以節(jié)點si為中心相對于點集K的節(jié)點伸展樹定義為T，有：

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

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

圖2 消息交換構(gòu)建融合樹

1) Beacon消息。

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

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

圖3 節(jié)點的Beacon通知消息處理過程

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

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

這個區(qū)域的節(jié)點數(shù)為

其中，p為樹的深度。按如下的二項式分布，選擇區(qū)域內(nèi)概率為p′的2個節(jié)點作為它們的父節(jié)點。

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

2) Probe消息。

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

3) Join 消息

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

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

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

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

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

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

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

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

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

6) Mi發(fā)送 Probe 包到 ni；

7) ni等待 NWAIT 時刻(恰當(dāng)?shù)臅r間周期)從選擇ni作為父節(jié)點的Mi接受Probe包。

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

2.3 數(shù)據(jù)融合

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

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

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

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

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

其矩陣形式為

經(jīng)化簡得如下方程：

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

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

其中，

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

圖4 融合過程中邊界區(qū)域的計算

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

其節(jié)點的數(shù)據(jù)被讀??；

執(zhí)行多元線性回歸，其系數(shù) β0，β1,…,β8被存儲；

2) 初始樹的深度為2p

While 當(dāng) p ＞0 時

sum = level + 2p-1

k = level

while k ＜ sum

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

4) 計算新的(βi0, βi1,…,βi8)和(β(i+1)0,β(i+1)1,…,β(i+1)8) ,添加到節(jié)點k的信息中，然后調(diào)用回歸函數(shù)計算(βk0,…,βk8) ,傳輸?shù)剿母腹?jié)點；

5) 轉(zhuǎn)到下一級深度繼續(xù)。

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

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

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

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

其中，t為樹節(jié)點總數(shù)，lt為葉子節(jié)點數(shù)。

3 事件區(qū)域檢測

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

3.1 事件區(qū)域檢測的性質(zhì)

設(shè)傳感器節(jié)點對某一區(qū)域的檢測讀數(shù)，有以下性質(zhì)：

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

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

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

性質(zhì) 1）說明傳感器獨立地檢測環(huán)境變化，性質(zhì) 2）說明正常傳感器讀數(shù)的變化范圍，性質(zhì) 3）說明，傳感器檢測讀數(shù)的變化空間，由適合正態(tài)分布的應(yīng)用事例確定，如每日氣溫、風(fēng)速等。本文對正常與錯誤讀數(shù)的判定條件如下。

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

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

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

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

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

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

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

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

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

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

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

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

3.2 單事件檢測

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

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

3.3 多事件檢測

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

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

圖5 2個事件發(fā)生的檢測

3.4 故障節(jié)點檢測及錯誤讀數(shù)的控制

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

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

圖6 故障節(jié)點的檢測與報告

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

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

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

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

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

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

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

4 影響性能的因素

1) 構(gòu)建AT的影響。

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

2) 多項式次數(shù)的影響。

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

3) 故障傳感器的影響。

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

4)τth的影響。

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

5 仿真實驗與討論

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

表1 仿真實驗參數(shù)設(shè)置

此外，ns由前面設(shè)定，即感知節(jié)點向樹節(jié)點報告的平均數(shù)，子區(qū)域里節(jié)點數(shù)U的上界為[15]

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

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

5.1 性能評估測度

在800×800平方單元區(qū)域R內(nèi)，隨機部署250個節(jié)點，溫度變化 30℃～35℃是正?，F(xiàn)象，溫度變化在 39℃～49℃時為異常，可能是該區(qū)域發(fā)生了火災(zāi)。樹的深度設(shè)置為 4。在無事件發(fā)生時，檢測的溫度值服從正態(tài)分布φ(i)。Cmin、Cmax和E(i)分別為30、35和32.5，φ(i)的變化是1.2。單個事件Pevernt1在中心發(fā)生，事件區(qū)域稱為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。當(dāng)事件發(fā)生時，讀取的數(shù)據(jù)通過NT節(jié)點傳輸?shù)阶罱臉涔?jié)點，通過10輪實驗評估以下性能指標(biāo)。前提是假設(shè)查詢已經(jīng)廣播到融合樹的所有葉節(jié)點。

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

5.2 仿真結(jié)果與討論

5.2.1 壓縮比

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

圖7 壓縮比與樹深度的關(guān)系

5.2.2 根節(jié)點輸出數(shù)據(jù)分組的大小

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

圖8 數(shù)據(jù)融合與未融合的通信量對比

5.2.3 邊界檢測

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

圖9 ATERD檢測的事件邊界

5.2.4 錯誤率

圖 10顯示了融合樹的深度與錯誤率的關(guān)系?？梢钥闯觯S著融合樹深度的增加，樹節(jié)點覆蓋的范圍會更大，從而使得整個區(qū)域能被更好地感知檢測，同時近似數(shù)據(jù)的平均誤差及錯誤率也穩(wěn)步下降，這正是所期望的。樹深度為1時，錯誤率達到最大值，是由于這棵樹僅有3個節(jié)點（區(qū)域內(nèi)的大多數(shù)傳感節(jié)點被分散，不在樹節(jié)點的感知范圍內(nèi)，因此無法向AT傳送）檢測該區(qū)域范圍。圖11顯示樹的深度為4時，錯誤率漸進增大達到最大值5.64。選取381個讀數(shù)，發(fā)現(xiàn)最初部分集中了接近估值的最大數(shù)目點。當(dāng)樹的深度為4時，錯誤率最大值為5.64%，大部分節(jié)點都有它們各自的誤差但限于一個較小的范圍0%～1.68%。

圖10 錯誤率與樹深度的關(guān)系

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

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

圖12 通信范圍、節(jié)點密度與錯誤率的關(guān)系

5.2.5 檢測延遲

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

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

5.2.6 識別延遲

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

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

圖14 故障傳感器識別延遲

5.2.7 負載

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

圖15 分組負載與網(wǎng)絡(luò)密度的關(guān)系

5.2.8 命中率

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

圖16 節(jié)點密度與命中率的關(guān)系

6 結(jié)束語

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

[1] 李建中, 李金寶, 石勝飛.傳感器網(wǎng)絡(luò)及其數(shù)據(jù)管理的概念問題與進展[J]. 軟件學(xué)報,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] 曹冬磊, 曹建農(nóng), 金蓓弘.一種無線傳感器網(wǎng)絡(luò)中事件區(qū)域檢測的容錯算法[J].計算機學(xué)報,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] 任豐原,黃海寧,林闖.無線傳感器網(wǎng)絡(luò)[J].軟件學(xué)報,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.