無線傳感器網絡中故障容忍的事件定位算法*

徐向華，高學勇，萬 健

(杭州電子科技大學計算機學院，網格與服務計算技術實驗室，杭州310037)

無線傳感器網絡通常是由分布在某一指定區域的具有計算與通信能力的微小傳感器節點組成。大量傳感器節點通過互相協作完成各種復雜的任務，例如，生態環境監測，基礎設施保護，事件定位，目標跟蹤等[2]。無線傳感器網絡可能由于節點故障、節點電池耗盡、環境影響、傳感器故障等原因，導致節點死亡、采集數據發生較大的偏差。例如，文獻[3]提到的無線傳感器網絡數據采集實際應用中，節點采集的數據中有40%—60%是錯誤的。因此，傳感器故障容忍在無線傳感器監測網絡應用中顯得尤為重要。

本文主要研究無線傳感器監測網絡中故障容忍的事件檢測與定位方法。假定在節點隨機布置的無線傳感網絡監測區域范圍內，且節點位置確定，事件源持續向周圍發出某種信號或者釋放某種物質，該信號強度或者物質濃度隨距離衰減;事件源附近檢測到一定信號強度的傳感器節點定期向中心節點匯報檢測到的信息;中心節點依據所有報警節點的匯報信息確定事件源的位置。該無線傳感器網絡可以具體應用于聲源定位，污染源的定位等場景。

目前，最大似然估計是無線傳感器網絡中常用的一種事件定位方法[4－6]。文獻[1]提出一種使用傳感器節點匯報到Sink節點的二元數據(Binary Data)進行事件定位的最大似然估計方法SNAP(Subtract on Negative Add on Positive)。其基本思想是Sink節點根據傳感器節點匯報的二元觀測值，通過在以該節點為中心的一個固定大小區域簡單的+1和－1構建似然矩陣。具體地說，在匯報二進制數據1的節點周圍區域+1;保持沉默的節點，Sink節點認為它沒有檢測到事件，在其周圍區域－1。最后，矩陣中值最大的元素對應的單元格即為事件發生的位置。

本文提出的MSNAP(Modified Subtract on Negative Add on Positive)算法是對SNAP算法進行改進，以提高事件定位精度。其算法思想為:假定部署在監測區域內的所有傳感器節點位置已知，每個傳感器節點將監測到的觀測值與設定的閾值進行比較，如果大于閾值，節點將觀測值發送給Sink節點;然后，Sink節點根據收到的某個節點的觀測值——事件信號強度，以該節點為中心估計事件傳播覆蓋的區域大小，在該區域+1;反之，如果小于閾值，節點保持沉默狀態，采樣周期內Sink節點沒有收到該節點發送過來的數據包，則認為該節點沒有檢測到事件的發生，因此，Sink節點估計事件不會發生在以該節點為中心的某個區域，在該區域－1。最后，我們認為似然矩陣中值最大的元素對應的單元格即為事件發生的位置。

SNAP算法根據節點匯報與否按照事先確定的固定區域大小+1/－1構造似然矩陣，本文提出的MSNAP算法根據節點匯報的觀測值，動態地調整事件可能發生網格區域的大小。觀測值越大，說明事件源離該節點越近，估計事件發生的區域越小;反之，估計事件發生的區域越大。理論分析和仿真實驗表明:在同樣節點布置和節點故障率的情況下，MSNAP比SNAP的定位精度有較大提高。

本文的組織結構如下:第1節描述無線傳感器網路中事件定位技術的相關工作，第2節介紹數據模型，故障模型以及假設條件，第3節詳細介紹MSNAP算法，第4節理論分析比較SNAP和MSNAP算法，第5節MSNAP算法與其他幾種估計算法仿真實驗結果以及比較，最后是本文總結。

1 相關工作

近年來，用于聲源跟蹤和事件定位的定位技術已經引起廣泛的關注和重視。相關定位方法大致可分為4類[7]:(1)基于信號到達角度的定位方法(AOA)[8];(2)基于信號到達時間的定位方法(TOA)[9－10]，(3)基于信號到達時間差的定位方法(TDOA)[11];(4)基于信號能量的定位方法[12－14]。上述4類定位方法中，基于信號能量的定位方法更加適用于節點資源和能量有限的無線傳感器網絡，因為:一是該方法僅通過測量信號強度達到事件的定位，降低了對節點硬件的要求;二是不需要節點間精確的時間同步，節省了通信能耗。

M．Ding等提出了質心估計的定位算法CE(Centroid Estimator)[15]。CE算法對報警節點的N次抽樣取中間值的方法，過濾掉由于瞬時故障引起的錯誤數據;然后，計算所有報警節點坐標的平均值，即質心位置。該算法估計事件發生的位置即為質心的位置。用(xn，yn)，n=1，2，…，P(p ＜ =N)表示所有報警節點的位置，則CE算法估計的事件位置為:

然而，節點的假陽性故障(事件影響范圍之外的節點錯誤報警)對該算法的精度影響很大。尤其是發生故障的節點遠離事件源位置時，該算法的估計誤差較大。

Niu Ruixin等提出了最大似然估計的方法ML(Maximum Likelihood)[16]。該方法將傳感器監測值轉化位0或1(表示沉默、報警)的二元值，構造似然函數實現事件位置估計的。其似然函數為:

其中，In，t為節點二進制讀數，Sn(θ)為節點在沒有噪音情況下的信號觀測值。該算法在節點發生假陰性故障(即檢測到事件的節點沒有發出報警)時，容錯性較差。尤其是發生故障的節點靠近事件源位置時，算法的定位誤差很大。

SNAP[1]方法使用傳感器節點匯報的二元數據進行事件定位。其基本思想是Sink節點根據傳感器節點匯報的二元觀測值，通過在以該節點為中心的一個固定大小區域簡單的加1和減1構建似然矩陣。具體地說，在匯報二進制數據1的節點周圍區域加1;保持沉默的節點，Sink節點認為它沒有檢測到事件，在其周圍區域減1。最后，矩陣中值最大的元素對應的單元格即為事件發生的位置。

本文提出的MSNAP算法是對SNAP算法進行改進，與SNAP的不同之處為:傳感節點匯報實際觀測值而不是0、1二元值，根據節點匯報的觀測值，動態的調整事件可能發生區域的大小。觀測值越大，說明事件源離該節點越近，我們估計事件發生的區域越小。因此，本文提出的算法具有更高的定位精度和容錯性能。

2 模型與假設

針對本文研究的無線傳感器網絡的事件定位問題，給出以下模型與假設說明:

(1)N個傳感器節點隨機均勻分布在一個矩形區域A內。節點位置固定，且位置信息已知，表示為:(xn，yn)，n=1，2，…，N。

(2)區域A內僅有一個事件源(xs，ys)，事件源的位置隨機布置。

(3)事件源持續不斷地發出某種信號，且向各方向傳播一致。信號的衰減與節點到事件源的距離滿足一定的關系，而且環境因素不影響它的傳播模型。

(4)檢測到事件的節點(報警節點)向Sink發送一個信號測量值，否則，節點保持沉默狀態。

假設被測信號在事件源位置的信號強度為c，該信號的衰減與傳感器節點到事件源距離的α(α∈R+)次冪成反比例。位于(xn，yn)的傳感器節點n，在第t次的測量值，我們使用文獻[1]中給出的數據模型表示:

其中，

在式(4)中的Vmax和γ是傳感器的特定參數(Vmax表示傳感器的最大測量范圍，γ表示對應于傳感器增益的比例參數)。rn是傳感器節點到事件源位置的距離:

根據上述信號傳播模型式(3)和式(4)以及噪聲模型式(5)，給出事件源的信號影響范圍 ROI(Region of Influence)用半徑為Rc的圓確定:

如圖1所示。

假定每個傳感器節點被預先設定了相同的閾值T，由此確定報警和非報警節點:

圖1 80個節點隨機分布在85×85的方形區域。事件源位于(20，20)，ROI為半徑為20的圓形區域

①λ報警節點:Zn，t≥T，即觀測值大等于閾值的節點。

②λ非報警節點:Zn，t＜T，即觀測值小于閾值的節點。

本文假設存在兩種故障類型:

①λ假陽性:在事件影響區域之外的節點報警，并向Sink發送自己的觀測值。

②λ假陰性:在事件影響區域之內的節點沒有報警，并保持沉默狀態。

3 MSNAP算法描述

MSNAP算法由以下四個步驟組成:

(1)網格劃分 將整個監測區域劃分成網格。

(2)確定節點的覆蓋區域ROC(Region of Coverage) 即節點估計事件發生的區域或者不會發生事件的區域。在網格狀的區域中，節點的ROC即為該節點所在單元格為中心的方形區域。根據節點觀測值的不同，方形區域的大小不同，即覆蓋單元格的數量不同。

(3)構造似然矩陣 與網格區域相對應的是一個似然矩陣L。矩陣中的元素和區域中的網格一一對應。基于每個傳感器節點的觀測值，Sink節點為該節點的ROC對應的矩陣元素加上某個值(報警節點加1，非報警節點減1)。

(4)求解極大值 似然矩陣中，值最大的元素對應的單元格，即為我們估計的事件發生的位置。

下面將詳細介紹該算法。

3．1 網格劃分

將監測區域劃分成G×G的網格，網格分辨率為g。例如，圖1將85×85的區域劃分成17×17的網格，分辨率 g=5。用 C(i，j)(其中，i，j=1，2…，G)表示監測區域中的單元格。分辨率的大小可以根據估計精度和計算復雜度的要求決定。每個傳感器節點根據其所在位置對應一個單元格(一個單元格中可能有多個節點或者沒有任何節點)。對于劃分好的網格區域，定義一個和G×G對應的似然矩陣L。

3．2 確定節點的覆蓋區域ROC

節點的監測覆蓋范圍由事件的信號影響范圍決定，最大覆蓋范圍ROC=ROI。由于節點的觀測值越大，表示節點距離事件源位置越近。因此，本文根據節點匯報的觀測值動態的調整節點的覆蓋范圍，以提高事件定位精度。在沒有噪聲干擾和不出現故障的情況下，由式(4)得節點與事件的距離為因此，我們定義ROC如下:

為了抵消噪聲的影響，將報警節點的節點覆蓋區域適當增大K，確保節點ROC覆蓋到發生事件的區域，但是保證不大于ROI。

3．3 構造似然矩陣

根據公式(7)確定的節點覆蓋范圍，每個報警節點將矩陣中對應于它所覆蓋單元格的元素加1，而每個不報警的節點將矩陣中對應于它所覆蓋單元格的元素減1。因此，得到似然矩陣L的元素值:

ROCn即為節點n的覆蓋區域。

3．4 求解極大值

用L(i*，j*)表示矩陣中值最大的元素，則 L(i*，j*)≥L(i，j)，?i，j=1，…，G。即矩陣中元素最大值對應的單元格就是我們估計的事件發生的位置。如果最大值的元素有多個，則我們認為它們對應的單元格的中心就是事件發生的位置。

3．5 例子

為了說明MSNAP算法，我們通過圖2所示的例子來說明。假設根據公式(7)計算的最大覆蓋范圍ROC為5×5單元格的方形矩陣圖2(a)，報警節點的ROC根據其實際觀測值動態變化。觀測值大于某個值的報警節點的ROC為3×3個單元格方形區域圖2(b)，其余報警節點的ROC為5×5個單元格方形矩陣。沒有報警的傳感器節點n的ROC是以該節點所在單元格(i，j)為中心的5×5個單元格的方形區域圖2(c)。為了構建似然矩陣L，報警節點在它ROC對應的矩陣元素上加上1，同樣，不報警的節點在它ROC對應的矩陣元素上減1。

圖2 節點的覆蓋范圍ROC(a)(b)是報警節點的ROC(c)是非報警節點的ROC

圖3所示似然矩陣是由六個傳感器節點通過在它們的ROC對應的矩陣元素上加1和減1構成。矩陣中值最大的元素3對應的單元格就是事件發生的位置。

圖3 由六個傳感器節點根據MSNAP算法構造的似然矩陣L，三個實心圓表示報警的節點，五角星表示事件發生的位置。

4 MSNAP算法和SNAP算法的分析對比

SNAP算法是一種最大似然估計的方法，僅通過事件ROI內的節點匯報的數據構造似然函數。假設事件ROI中存在K個節點，其匯報的數據用Ik表示。Ik?I={Ik，t:rk≤Rc}，rk是節點 k 到事件源的距離。給定指示函數

似然函數的形式如下:

θ為事件源所在位置，根據修正的似然函數p'(Ik|θ)=102KMp(Ik|θ)，兩邊取對數，得到:

因此，可得SNAP算法的估計量:

對于本文提出的MSNAP算法，其似然函數為:

因為在沒有噪音出現的情況下，由式(7)得到，當 Zn，t≥ T 時，由公式(2)得到，s'k(θ)＞ sk(θ);同樣，當 Zn，t＜ T 時，因此，lg p(I|θ)＞Mklg p(Ik|θ)，即當觀測值大于閾值時，我們縮小了估計的范圍Rc，但是事件發生在該區域的概率并沒有降低，所以提高了定位的精度。

5 實驗結果及性能分析

本文的所有實驗均在仿真環境中實現，表1給出了實驗用到的參數及其默認值。實驗中如果沒有對使用參數進行特別說明，則使用表中的默認值。因此，傳感器節點的觀測值可以用下面的表達式表示:

節點的覆蓋范圍ROC可以用式(16)表示:本文令K=1。

表1 相關參數及其默認值

我們利用多次實驗的均方根誤差(RMS Error)作為算法的性能評價標準。對于每次實驗，假定事件源隨機分布的位置，通過估計算法估計的事件源位置為，則RMS Error可用以下表達式表達:

本文取B=500，即每個實驗做500次。每次實驗，傳感器節點分布固定，事件源隨機布置。

為了分析對比各種定位算法的優缺點，本文所有實驗，在相同條件下，分析對比 MSNAP，SNAP，AP，CE四種算法的性能。

5．1 節點存活數對算法性能的影響

由于電池電量的耗盡或者環境因素的影響，部署在實際環境中的傳感器節點會逐漸失去效用。本實驗研究節點存活數對MSNAP算法以及SNAP、AP、CE等算法影響和性能比較。圖4給出了網絡中存活節點數目的變化時，四種算法的性能表現。隨著存活節點數目的不斷減少，檢測到事件的節點數變少，Sink節點獲取的信息減少，因此，定位估計的誤差變大。從圖中可以看出，在相同數量節點失效時，MSNAP算法的定位精度明顯優于其他三種算法。

圖4 存活節點數目的變化對事件定位算法精度的影響

5．2 傳感器監測錯誤對算法性能的影響

針對存在兩種傳感器故障類型:一類是假陰性，即節點處在事件影響區域之內，但是其觀測值小于閾值T，沒有發出報警;另一類是:假陽性，即節點處在事件影響區域之外，但是其觀測值(我們假定該值是介于閾值T和事件源位置的信號強度c之間的一個隨機值)大于閾值T，發出報警。為了分析定位算法的容錯性能，在0～0．5的節點監測故障概率情況下，比較算法的定位誤差。圖5顯示了四種估計算法的故障容忍性能。圖5(a)、5(b)、5(c)、5(d)分別為事件源信號強度c=1 000、c=2 000 、c=3 000、c=4 000 時的實驗結果。

圖5 事件源位置信號強度不同的情況下，四種事件定位算法的故障容忍性能對比

從圖5可以看出，在不同故障率的情況下，MSNAP算法的定位精度好于其他三種算法。事件源的信號強度越大，報警節點的比例越大，MSNAP算法的定位精度越高。當故障率小于0．3的時候，MSNAP算法和SNAP算法表現出了較好的容錯性能，仍然具有較高的定位精度。這是因為似然矩陣的構造使得單個傳感器節點發生故障不會對整個估計結果產生很大的影響。盡管SNAP算法和AP算法的估計誤差大于MSNAP算法，但是，他們對于故障容忍表現出了相同的性能趨勢。當故障率小于0．4的時候，CE算法的故障容忍性能最差。

5．2．1 假陰性故障對算法性能的影響

本實驗研究節點發生假陰性故障時，對四種事件定位算法的影響。部署在實際環境中的無線傳感器網絡，常常由于節點發生丟包而產生假陰性故障。由于本文提出的算法要求檢測到事件的節點向Sink節點發送一個數據包，沒有檢測到的節點保持沉默狀態，因此，當檢測到事件的節點發送的數據包丟失時，Sink節點沒有收到該節點發送過來的數據包，則認為該節點沒有檢測到事件。為了研究丟包率對四種估計算法的影響，我們假定網絡中節點沒有故障，檢測到事件的節點發生丟包的概率為Pd。

圖6顯示了丟包率或者假陰性故障對四種定位算法的影響。從圖中可以看出，當丟包率小于0．25的時候，MSNAP算法的定位誤差較小。當丟包率大于0．3的時候，CE算法和AP算法的性能最好，定位精度最高。CE算法和AP算法的性能幾乎不受丟包率的影響，而SNAP算法和MSNAP算法卻受影響較大。這是因為SNAP算法和MSNAP算法考慮了不報警節點對事件定位的影響。當丟包率增大時，發生丟包的節點增多，則它們的負面影響抵消了正常報警節點的正面影響，因此，估計誤差增大。而CE算法和AP算法僅僅考慮報警節點的影響，忽略非報警節點的影響，因此，算法性能受丟包率的影響較小。

5．2．2 假陽性故障對算法性能的影響

圖6 丟包率對四種事件定位算法的影響

本實驗研究節點發生假陽性故障時，對四種事件定位算法的影響。部署在實際環境中的傳感器節點由于長時間工作，板子過熱，導致錯誤的報警。假定網絡中非報警節點發生錯誤報警的概率為P0。圖7顯示了節點發生假陽性故障對四種事件定位算法的影響。從圖中可以看出:隨著節點發生假陽性故障概率的增大，CE算法的性能越來越差。當發生故障的節點離事件源越遠，該算法估計的事件位置誤差越大。和AP算法相比，SNAP算法和MSNAP算法具有更好的魯棒性。這是因為上述兩種算法通過非報警節點的作用抵消了部分報警節點產生的影響。MSNAP算法受假陽性故障的影響較小，保持了很高的定位精度。

圖7 假陽性故障對四種事件定位算法的影響

6 總結

本文針對無線傳感器網絡的事件定位問題，提出了對SNAP的改進算法MSNAP，通過報警節點匯報的觀測值大小動態確定覆蓋區域大小，構建似然矩陣，估計事件發生的位置。在相同情況下，與SNAP算法相比，它的定位精度更高，容錯性能更好。MSNAP算法更加適用于對定位精度和容錯性能要求較高的應用場景。下一步，我們計劃考慮能耗、帶寬等因素，進一步改進事件定位算法的性能。

[1]Michaelides M P，Panayiotou C G，SNAP:Fault Tolerant Event Location Estimation in Sensor Networks Using Binary Data[J]．IEEE Transactions on Computers，2009，58(9):1185 －1197．

[2]孫利民，李建中，陳渝，等．無線傳感器網絡[M]．北京:清華大學出版社，2005．

[3]Ni K．Sensor Network Data Fault Types[J]．ACM Transactions on Sensor Networks，2009，5(3):1 －29．

[4]Vijayakumaran S，Levinbook Y，Wong T．Maximum Likelihood Localization of a Diffusive Point Source Using Binary Observations[J]．IEEE Transactions on Signal Processing，2007．55(2):665 －676．

[5]Sheng X，Hu Y．Maximum Likelihood Multiple-Source Localization Using Acoustic Energy Measurements with Wireless Sensor Networks[J]．IEEE Transactions on Signal Processing，2005，53(1):44－53．

[6]Chen J，Hudson R，Yao K．A Maximum-Likelihood Parametric Approach to Source Localizations[C]//Proceedings of IEEE International Conference on Acoustics，Speech，and Signal Processing，2001:3013－3016．

[7]Mao G，Fidan B，Anderson B D O．Wireless Sensor Network Localization Techniques[J]．Computer Networks，2007，51(10):2529 －2553．

[8]Niculescu D，Badri N．Ad Hoc Positioning System(APS)Using AOA[C]//Proceedings of IEEE Infocom，2003:1734 －1743．

[9]焦磊，邢建平，張軍，等．一種非視距環境下具有魯棒特性TOA無線傳感網絡定位算法[J]．傳感技術學報，2007，20(7):1626－1630．

[10]Girod L，Estrin D．Robust Range Estimation Using Acoustic and Multimodal Sensing[C]//Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems(IROS 2001)，2001:1312－1320．

[11]Savvides A，Han C C，Strivastava M B．Dynamic Fine-Grained Localization in Ad-Hoc Networks of Sensors[C]//Proceedings of the 7th Annual International Conference on Mobile Computing and Networking，2001:166 －175．

[12]趙昭，陳小惠．無線傳感器網絡中基于 RSSI的改進定位算法[J]．傳感技術學報，2009，22(3):391 －394．

[13]田增山，羅磊，何維，等．一種分布式無線傳感器網絡節點定位算法[J]．傳感技術學報，2009，22(3):387 －390．

[14]Meesookho C，Mitra U，Narayanan S．On Energy-Based Acoustic Source Localization for Sensor Networks[J]．IEEE Transactions on Signal Processing，2008，56(1):365 －377．

[15]Ding M．Fault-Tolerant Target Localization in Sensor Networks[J]．Eurasip Journal on Wireless Communications and Networking，2007:1－9．

[16]Niu R，Varshney P．Target Location Estimation in Wireless Sensor Networks Using Binary Data[C]//Proceedings of the 38th Annual Conference on Information Sciences and Systems，2004．