徐向华，高学勇，万 健

(杭州电子科技大学计算机学院，网格与服务计算技术实验室，杭州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．