WSN中面向非均匀形状事件的动态检测方案

邓定胜

0 引言

综合了无线通信技术、传感器技术、嵌入式计算技术和分布式信息处理技术的无线传感器网络（Wireless sensor network,简称WSN）[1]，是目前国际上前沿热点的研究领域。在石油泄露检测、地下水污染监测等应用领域，无线传感器网络具有重要作用。例如，液体扩散监控等应用领域，传统的基于数值液体传输模型的液体预测技术，需要数小时的运行时间，计算量太大。为了实现事件的实时跟踪，需要将模型分解，使计算任务在各传感器节点间分布式执行，以实现计算的并行化。通过对每一个事件进行分布式检测跟踪，对于保证无线传感器网络应用的可靠性具有重要意义。

文献[2]给出一种统计方法，在事件检测时不需先验判断便可实现对广义同质区域的检测和跟踪。文献[3]提出的新的区域事件边缘检测算法利用了对偶空间技术。该算法本质上是集中式算法，但仍可以在双层架构主干节点间分布式运行。文献[4]中提出的DCTC方案使用“动态护航树（dynamic convoy tree）”协议来同时实现事件跟踪和通信架构维护。当前研究的主要不足在于，人们普遍假设事件既不会合而为一，也不会分裂成多个更小事件。许多情况下，该假设并不成立。再次比如地下化学品泄露问题。如果流体从多个地点喷涌而出，多处羽流将会相遇、混合。此时，它们便成为一个更大的羽流而失去各自的形态。相反，它们在流动时途径媒介所发生的变化，可能会导致流体沿着个别路径流动而被拆散成多个规模更小的流体。实际上，对污染物的扩张、收缩、分裂和汇合进行动态跟踪，对污染物治理决策具有非常重要的作用。鉴于此，本文在现有工作的基础上，提出了一种改进的动态事件检测和跟踪方案，并通过仿真实验验证了本文方法的有效性。

1 系统模型

1.1 事件质心

事件的质心描述了事件的位置。它是一个广义位置坐标，可以作为事件分裂/融合检测等重要行为的参考点。

定义1质量函数 质量值mn,t表示节点n在时间t时事件读数的“密度”。它是传感器计数的有界非负实数。质量函数的确切表达式与具体应用场合有关。此处采用一个默认的二进制事件检测规则：m=0表示未检测。

定义2事件质心 事件的质心是指检测到事件的所有节点以其质量为权重而得的平均位置。设e为目标事件。Ne(t) N为在时间t检测到事件e的传感器节点集合。Me(t)是总质量。设 hn是覆盖节点n感应区域任意点的附近节点的不同感应区域数量均值。设向量 1n=[ xn,yn,zn]为节点n的三维位置向量，则时间t事件e的质心 1M( e, t)的计算方法如公式（1）：

节点密度nh用于确保事件质心不会由于该区域刚好存在较多节点而偏向于低密度区域。确定nh的一种方法就是估计给定节点平均感应区域的形状。在实际部署时，使用数值融合技术来计算每个节点感应区域多重覆盖期望值。

1.2 节点动量

为了跟踪事件分裂和融合情况，我们认为：如果有大量事件计数与事件质心相距甚远，则这些计数应该被视为自主事件。相反，如果两个独立事件非常接近，以致它们的主要计数已经无法区分，则这些事件应该合而为一。这些观点表明了到底需要哪些信息才能检测事件分割和融合。首先，我们必须考虑读数强度及该读数与事件质心的距离。其次，在弄清是否分割某一事件及在何处分割时，必须为距离补充方向性信息，因此需要一个矢量。于是，我们对物理学领域的另一个物理概念“动量”进行了借鉴。

一个节点的动量指其相对事件质心的位置向量，并受其自身质量读数调节。

1.3 分割和融合决策规则

定义 4事件分裂判定 设TC为用户定义的以距离为单位的内凝阈值。如果下述判定成立，则发生事件分裂。

事件融合判定与上述内容相对称。此时，对两个事件中的每个节点，计算节点相对两个事件综合起来的综合质心的动量矢量。该综合质心称为联合质心，定义如下：

节点n相对该联合质心的动量称为联合动量。

定义7事件融合判定 设E为网络中的事件集合。如果以下条件满足，则事件e1和e2发生融合如公式（4）：

如果某事件不满足分裂判定，则认为其单独稳定。类似地，如果两个事件没有满足融合判定，则认为它们联合稳定。在实际部署时，传感器读数和节点位置数值只是近似值。为了避免事件件分割和融合判判定对噪声过于于敏感，我们可以以对内凝阈值TC设置容限。

2 算法描描述

通过使使用上述定义的的基本概念，我们们设计了分布式式算法DRAGON，对动态变化的的不确定性事件件进行检测和跟跟踪。

我们假假设网络分为多多个簇。每个簇只只有一个节点或或簇头作为该簇的的本地数据汇点点。DRAGON算算法将会运行于于各个簇头上。如如果事件完全位位于一个簇内，则则该簇头完全本本地化运行DRAAGON算法。当当事件横跨多个簇簇时，必须允许许簇头相互通信。。当决策可以融融合当前哪些事事件时，还需要全全局统筹。因此，我们定义了““主干树”概念。通过簇（头））间链路来形成主主干树的链路。任一簇头可以作为树的根，只只要树被连接并且且包括所有的簇簇头即可，树的的形成方法并不不重要。底层的簇协协议可以对簇头头进行轮流循环环，以平衡能量量消耗。也有可能网网络中的簇头由由资源充足的节节点担任。

为了进进一步阐述DRRAGON算法的分布式特性，我我们希望该算法只只涉及实际跟踪踪事件的网络区区域，以利用本地地特性并节约能源源。为此，通过过“活跃子树本地化”对主干树树进行改进。这一一步骤始终在主主要算法运行前前进行，内容如下下：首先，树根向向整个树发送少少量消息，询问每每个簇头是处于于活跃状态还是休休眠状态。节点点处于活跃状态还还是休眠状态取取决于该簇头在主主干树中是叶节节点还是内节点点。叶节点当且仅仅当它有成员节点点感知到事件时时才处于活跃状状态；内节点当且且仅当自身活跃或或有子节点活跃跃时才处于活跃跃状态。叶节点首首先对根请求做出出响应。活跃簇簇将会参与到DDRAGON算法中中，休眠节点将在在算法运行期间间继续保持休眠眠。

2.1 算法主主要阶段

DRAGGON算法的效效能和需求决定了了算法存在3个个运行阶段概述、、分割、融合，如图1所示：

图1 DRAA GON算法的三个阶段

如前文文阐述，必需的的决策判断需要要3种统计量：质心，总质量，节节点数量。在活活跃子树本地化后，概述阶段对对每个事件计算这这3种统计量，然后把它们分分配给所有活跃簇簇。要对融合做出出?

决策，必须要要有所有事件的相关信息。事件件分割和融合阶段段的任务，分别别是对事件分割和和融合进行检验验和执行。

在定义义事件分割和融融合阶段间的关关系时，我们定义义：如果两个事件件联合稳定，则则由并集衍生的事件，其自身具具有稳定性。因此此，事件融合后后并不需要检测测是否需要事件件分割。为了支持多多路分割和融合合，我们允许正常常的双路分割和和融合阶段运行多多次迭代。

DRAGON算算法的重要特点就就是，该算法的的3个阶段均遵守守状态传输、消消息传输和计算算的单种统一模式式。它主要包含了了3种状态：开开始、融合、更更新、如图2所所示：

图2 DRAGON元元程序状态机

2.2 算法细节

我们现在结合合算法3个阶段段，详细讨论元元程序子线程：localProcess, fuse,finalizePhase和和processUpdatte。

（1）概述阶段段。每个簇头执执行的localProccess线程，只针对对直接位于相应应簇内的部分事事件，计算质心、总质量和节点数数量。fuse线程程与子节点和母母节点计算方法类类似，对每个事件件的本地质心、本地总质量和和本地节点数量进进行合计，并且利利用均值与求求和操作对其进进行综合。finaalizePhase和proocessUpdate线程分别负责发送送和接收网络所所有事件的完整汇汇总信息。然后后，簇头内部数数据结构进行更新新。对网络中的所所有事件来说，每个带有入口的活跃簇均需要要一张汇总信息表表。于是，分割割和融合计算可在在树上分布式进进行的同时保持准准确性。

（2）分割阶段段。这一阶段的的localProcess线线程负责识别目标标簇内的分割群群组。首先对事事件e，确定动量量满足分割判断的的所有节点，然然后按照节点动动量大小降序排列列。这些节点重复复执行算法，每每次执行形成一一个分割群组。对对满足分割判断的的每个节点，对对以下群组形成成判定进行检验验。

设对节点n，考虑是否将其其加入分割群组JJ。设已经在分割割群组J中的的所有节点的的总质量为，定义为相对在在时间t测得的事事件e的质心，群组J所有节点点 的平均动量。距离为d。群组组J的节点数量量为。用TS表示相对群组规模，对节点点动量矢量与群群组平均动量距离离进行控制的分分离阈值。群组组形成判定定义义如公式（5）：

如果该判定成成立，则将考虑虑中的节点加入分分割群组，同时对群组的质心、总质量和平均动量值进行相应的更新。然后，将节点从考虑节点列表中去除。对所有节点考察完毕后，我们便认为群组构建完毕，下一群组开始。这一过程一直持续，直到所有考虑中的节点加入群组为止。

这一阶段的 fuse线程对子节点和母节点确定的分割群组进行扫描，对对应于单分割现象的群组进行融合。两个群组的融合过程与 localprocess将节点加入群组方式类似。finalizePhase线程负责从众多潜在群组中选择一个群组从整体中分离。选择标准是选择距离事件主体最远的分割群组。这一比较过程的参考点是分割群组的质心，及将该群组脱离后初始事件剩余部分的质心。processUpdate线程命令簇头针对它正在跟踪的事件，对群组进行检查，以确定是否已经包括了它的部分簇。如果包括，则对每个相关分割事件，我们认为检测到了包括相关节点的新的事件。同时对所有事件的数据结构进行更新。

3 性能评估

本节将对本文提出的事件检测方案采用 matlab2012仿真工具进行性能评估。

3.1 事件模型

本文使用基本的几何形状对事件建模。区域事件用正方形建模，点状事件用圆形建模。对简单的事件，我们支持事件重叠，因此我们不仅可以分割和融合，还可以通过混合简单的几何形状来创建更为复杂的有趣的事件形状。区域事件只有两种读取等级，外带质量值0.5和内部高地质量值1.0。点状事件的质量读数以点的位置1.0开始，然后呈线性迅速下降至边缘处的0.0。在运行时，事件在500m区域内的500m处以完全均匀随机的初始位置开始，初始运动方向也设为均匀随机。事件以直线运动，运动方向做必要的随机变动以避开区域边缘。运动速度为预先定义数值，且保持不变。

3.2 性能指标和参数

我们从能耗和运行时间两方面衡量通信开销。所有计算基于TelosB节点平台[5]。网络建模为无损无冲突网络。另一重要指标是事件检测和跟踪准确率，以将DRAGON输出与客观标准进行对比。在本文模拟中，负责统计数据收集的模块已经直接掌握了这些底层事件形状和变化情况（被模拟的跟踪算法并未掌握），也就是说掌握了实际状况。准确度指标必须：（1）确定DRAGON是否成功检测到了网络中的所有事件；（2）确定对每个事件的描述是否恰当。第一个指标仅仅是描述DRAGON结果与实际情况间的事件数量差异。第二个指标定量描述事件形状的正确度。我们与数据挖掘领域中的Jaccard系数类似，只使用一种称为事件成员相似度的指标[6]。该指标定义为正确匹配与所有节点的比值（也就是正确匹配、虚警和漏警之和）。所有节点部署于500m*500m区域内。5种独立变量及各变量的值域如表 1所示：

表1 主要变量参数

每个节点的传输范围为20米。

3.3 实验结果

我们选择经过优化的DCTC[7]作为比较算法。这是因为该算法的总体操作是基于生成树的重新配置，以覆盖检测到事件的节点。同样地，它代表了现实世界面临的事件跟踪问题大多数最基本最简单的“模板式”解决方案。同时，通过在重新配置树结构时纳入老节点修剪过程和新节点加入过程，并且不对事件形状做任何假设，我们将 DCTC拓展至R-DCTC，以支持一般的事件形状。

在我们第一类实验中，更改每个独立参数，确定DRAGON正确的内凝阈值（TC）和分离阈值（TS）。由于准确性是我们考虑的一个重要方面，我们只从事件数量差异和事件成员相似度方面对阈值进行优化。我们对稀疏网络发现， TC=0.8且 TS= 0.9时跟踪准确率最高，此时有3个事件，每个事件以 20m/s速度移动。对中等密度分布网络，最优TC=1.3， TS= 1.2。对密集分布网络，最优 TC=1.4， TS= 1.2。我们还发现，最优簇大小为2（也就是说，每个成员节点距离簇头最多为2跳），最佳行为触发器是阈值为3的节点飘移。在这些结果中，曲线变化缓慢，且有一个性能较优的高地。这意味着实际上存在着较宽的间隔，使阈值支持优异的性能结果。参数敏感度不高。我们也可以轻松找到与实际应用最匹配的参数。同时，各种部署情况下，最优参数的差异并不很大。这也印证了DRAGON运行与节点密度无关这一结论。

我们的第二组实验主要是对DRAGON与DCTC（点状事件）及R-DCTC（区域事件）进行对比性测试。我们研究了部署类型、事件大小、事件速度、事件数量和事件类型的影响。以下结果描述了 95%的置信区间，每个数据点为 10次运行取均值。

（1）事件大小影响。我们对不同事件大小条件下的两种协议性能进行评估；实验条件为稀疏网络，3个可融合区域事件以20m/s的速度运动如图3所示：

图3 性能评估VS事件大小

图3a表明，DRAGON的事件数量差异非常理想，而R-DCTC对不同事件大小时经常出错。图3b表明，DRAGON的事件成员相似度在80%左右，但是R-DCTC一直不理想。对图3c和图3d，我们必须承认，DRAGON的成本明显较高。总体来说，DRAGON的准确度更优，虽然在时间和能效方面的成本较高，但是可拓展性很强。还有另一重要结论：更为重要的是，我们发现，当事件大小上升时，DRAGON在时间和能效方面的成本在对数和线性水平之间。

（2）事件数量影响。为了评估两个协议面对大量事件时的性能，我们考虑可融合区域事件，宽度为150m，在稀疏网络上以20m/s速度运动如图4所示：

图4 性能比较VS事件数量

图4a和4b表明，DRAGON的准确度一直较高，即使事件数量上升也不会有显著下降。同时，R-DCTC的准确度出现迄今最差水平，当事件数量上升时继续恶化。然而，最有趣的结果出现在图 4c和 4d中。当事件数量上升时，DRAGON在能耗和时间复杂度方面明显呈线性上升。同时，R-DCTC的能耗和运行时间呈轻微的线性上升趋势，基本保持平稳。但是两种协议间的渐进性能差异并不算个问题 。实际上，我们正希望出现这一现象，因为在处理事件分割和融合时，DRAGON的计算和通信必须明确考虑网络中的事件数量。成本也会相应上升。

4 总结

本文提出了一种改进的通用事件检测和跟踪方案（DRAGON），可在事件分割和融合情况下运行。仿真实验结果表明，该方案在各种条件下均有很高的准确度。不论部事件大小和事件数量如何，它始终可以确定正确的事件数量，给出正确的事件形状。我们下一步研究工作的重点是采用压缩感知理论对无线传感器网络中的异常事件检测问题进行建模，以进一步提高事件检测的能效，延长网络寿命。

[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