无线传感器网络协作事件检测研究

ＣＮ４３—１２５８／ＴＰ　ＩＳＳＮ　１００７—１３０Ｘ　计算机工程与科学　ＣＯＭＰＵＴＥＲ　ＥＮＧＩＮＥＥＲＩＮＧ　８Ｌ　ＳＣＩＥＮＣＥ　２００８年第３０卷第１Ｏ期　ＶＯ１．３０，Ｎｏ．１０，２００８　文章编号：１００７－１３０Ｘ（２００８）１０－００１１—０４　无线传感器网络协作事件检测研究　Ｅｖｅｎｔ　Ｄｅｔｅｃｔｉｏｎ　ｗｉｔｈ　Ｃｏｌｌａｂｏｒａｔｉｏｎ　Ｍｏｄｅｌｓ　ｉｎ　Ｗｉｒｅｌｅｓｓ　Ｓｅｎｓｏｒ　Ｎｅｔｗｏｒｋｓ　康雅斌　，田锐。。程冬梅　ＫＡＮＧＹａ－ｂｉｎ１，ＴＩＡＮＲｕｉ　，ＣＩ－ＩＦ￣ＧＤｏｎｇ－ｍｅｉ　（１．中国人民解放军第３０５医院计算机中心，北京１０００１７；２．中国科学院计算技术研究所，北京１００１９０）　（１．Ｃｏｍｐｕｔｅｒ　Ｃｅｎｔｅｒ，ＰＬＡ　３０５　Ｈｏｓｐｉｔａｌ，Ｂｅｉｊｉｎｇ　１０００１７；２．Ｉｎｓｔｉｔｕｔｅ　ｏｆ　Ｃｏｍｐｕｔｉｎｇ　Ｔｅｃｈｎｏｌｏｇｙ，　Ｃｈｉｎｅｓｅ　Ａｃａｄｅｍｙ　ｏｆ　Ｓｃｉｅｎｃｅｓ，Ｂｅｉｊｉｎｇ　１００１９０，Ｃｈｉｎａ）　摘要：事件检测是无线传感器网络的重要应用之一。由于传感器节点廉价、易损，无线通信链路不稳定、易受干扰等　特点，检测精度受到很大的限制。所以，利用传感器节点密集分布独立感知的特性进行协作事件检测很有必要。本文针对　应用场景相关和网络维护相关两类事件的协作检测机制现状进行研究，并对各类协作模式下不同检测算法的优缺点进行　了比较。　Ａｂｓｔｒａｃｔ：Ｅｖｅｎｔ　ｄｅｔｅｃｔｉｏｎ　ｉｓ　ｏｎｅ　ｏｆ　ｔｈｅ　ｉｍｐｏｒｔａｎｔ　ａｐｐｌｉｃａｔｉｏｎｓ　ｏｆ　ｗｉｒｅｌｅｓｓ　ｓｅｎｓｏｒ　ｎｅｔｗｏｒｋｓ．Ｈ０ｗｅｖＰｒ　ｅｃｔｉｏｎ　ａｃｃｕ—　ｒａｃｙ　ｉｓ　ｌｉｍｉｔｅｄ　ｂｙ　ｔｈｅ　ａｍｏｕｎｔ　ｏｆ　ｎｏｉｓｅ　ａｓｓｏｃｉａｔｅｄ　ｗｉｔｈ　ｔｈｅ　ｍｅａｓｕｒｅｍｅｎｔ　ａｎｄ　ｔｈｅ　ｒｅｌｉａｂｉｌｉｔｙ　ｏｆ　ＵＳ１Ａ　”ｌｏｗ—ｅｎ（ｉ　ｉｎｅｘｐｅｎｓｉｖｅ　ｓｅｎ—　ｓｏｒ　ｎｏｄｅｓ．Ｉｔ　ｉｓ　ｎｅｃｅｓｓａｒｙ　ｔＯ　ｔａｋｅ　ｕｓｅ　ｏｆ　ｔｈｅ　ｅｈａｒａｃｔｅｒｉｓｔｉｃｓ　ｏｆ　ｔｈｅ　ＷＳＮ　ｗｈｏｓｅ　ｎｏｄｅｓ　ａｒｅ　ＵＳＵ３．Ｙ　ｄｅｎｓｅｌｙ　ｄｉｓｔｒｉｂｕｔｅｄ　ａｎｄ　ｃａｎ　ｐｅｒｃｅｐｔ　ｔｈｅ　ｅｎｖｉｒｏｎｍｅｎｔ　ｉｎｄｅｐｅｎｄｅｎｔｌｙ　ｔｏ　ｅｏｌｌａｂｏｒａｔｉｖｅｌｙ　ｄｅｔｅｃｔ　ｅｖｅｎｔｓ．Ｔｈｉｓ　ｐａｐｅｒ　ｓｕｍｍａｒｉｚｅｓ　ｔｈｅ　ｓｔｕｄｉｅｓ　ｏｎ　ｔｈｅ　ｄｅｔｅｃｔｉｏｎ　ｏｆ　ｔｈｅ　ａｐｐｌｉｃａｔｉｏｎ－ｒｅｌａｔｅｄ　ａｎｄ　ｎｅｔｗｏｒｋ－ｍａｉｎｔｅｎａｎｃｅ－ｒｅｌａｔｅｄ　ｅｖｅｎｔｓ　ａｎｄ　ｆｉｎａｌｌｙ　ｓｈｏｗｓ　ｔｈｅ　ｍｅｒｉｔｓ　ａｎｄ　ｄｅｍｅｒｉｔｓ　ｏｆ　ｄｉｆｆｅｒｅｎｔ　ｋｉｎｄｓ　ｏｆ　ｄｅｔｅｃｔｉｏｎ　ａｌｇｏｒｉｔｈｍｓ　ｗｉｔｈ　ｄｉｆｆｅｒｅｎｔ　ｃｏｌｌａｂｏｒａｔｉｏｎ　ｍｏｄｅｌｓ．　关键词：事件检测；边界检测；错误检测；分布式协作　Ｋｅｙ　ｗｏｒｄｓ：ｅｖｅｎｔ　ｄｅｔｅｃｔｉｏｎ；ｂｏｕｎｄａｒｙ　ｄｅｔｅｃｔｉｏｎ；ｆａｕｌｔ　ｄｅｔｅｃｔｉｏｎ；ｄｉｓｔｒｉｂｕｔｅｄ　ｃｏｌｌａｂｏｒａｔｉｏｎ　中图分类号：ＴＰ３９３．０３　文献标识码：Ａ　１　引言　无线传感器网络（以下称作传感器网络）作为一种获取　现实世界信息的手段正受到越来越多的重视。事件检测是　传感器网络的重要应用之一。本文所面向的应用是对突发　事件进行二元值形式的汇报。事件的发生对应于测量数据　的跳变，而通常的事件可分为应用场景相关与网络维护相　关两类。其中，用户感兴趣的是第一类事件，泛指检测环境　中外部因素的改变，以下称作事件检测；而第二类事件包括　节点失效和通信链路故障等，是网络维护人员所感兴趣的，　以下称作错误检测。一个高效的传感器网络系统，需要在　考虑多种影响因素的条件下同时提供关于上述两类事件的　准确汇报。　作为典型的分布式系统，传感器网络在协同处理方面　有着天生的优势：首先，传感器节点都有自己的独立感知与　计算能力，可以在不受其他节点影响的条件下获得对观测　现象的判断；其次，传感器节点往往密集分布，测量数据之　问存在较强的空间相关性，这一特性可作为协同处理的依　据。但是，传感网络也有着自身的不足，带宽、能量受限，通　信干扰与节点失效频发等诸多因素都要求对协作检测机制　进行精心的设计。　２节点协同事件检测算法　现存的协作检测机制主要包括两种协作模式：对等实　体的协作与通过第三方实体参与的协作。第一类协作模式　常见于全分布式的系统，如图１ａ所示，其中实体Ａ与Ｂ处　收稿日期：２００８—０４—１４；修订日期：２００８—０７—０１　．　．　作者简介：康雅斌（１９７４一），男，陕西宝鸡人，硕士生，研究方向为数字医学信号的采集与处理、无线网络等；田锐，博士生，研究方向　为无线传感器网络；程冬梅，本科，研究方向为医院信息系统、无线网络等。　通讯地址：１０００１７北京市西城区文津街甲１３号中国人民解放军第３０５医院计算机中心；Ｔｅｌ：（０１０）６３０９８１３４；Ｅ－ｍａｉｌ：ｋｙｂ５０８０＠ｓｉ—　ｎａ．ｃｏｒｎ　Ａｄｄｒｅｓｓ：Ｃｏｍｐｕｔｅｒ　Ｃｅｎｔｅｒ，Ａ１３　Ｗｅｎｊｉｎ　Ｓｔ，Ｘｉｃｈｅｎｇ　Ｄｉｓｔｒｉｃｔ，Ｂｅｉｊｉｎｇ　１０００１７，Ｐ．Ｒ　Ｃｈｉｎａ　

ｌ１　于同等地位并拥有同等的资源，两者之问通过交互各自得　到的信息进行协作；第二类协作模式常见子集中式的决策　结构，比如按簇划分的传感器网络，如图１ｂ所示，实体Ａ　与Ｂ将自己观测得到的信息发往实体ｃ，并由ｃ根据接收　到的消息做基于全局的判断。基于第一类协作模式的检测　算法往往依赖于节点之间的多次通信，减小了用于向远程　节点传递信息的带宽与能量开销，拥有全分布式的特点，适　用于同构的传感器网络；基于第二类协作模式的检测算法　虽然可以通过各种压缩算法减少数据发送行为、减小发送　的比特数，可以节省带宽并提高节点的能量效率，但却会造　成第三方节点的耗能不均，需要和特定的分簇算法搭配使　用。　针对事件检测算法的研究包括事件区域检测与事件边　界检测。判断某监视区域内是否有事件发生的过程称作事　件区域检测，而寻找发生事件边界的过程则称为事件边界　检测。　Ｃ［二　ａ第一类协作模式　ｂ第二类协作模式　图１两种协作模式　２．１事件区域检测　按照节点协同方式的不同，常见事件区域检测算法可　分为集中式检测与分布式检测两种。其中，集中式检测需　要中心节点参与来作最后的决策，而分布式检测则完全由　传感器节点在本地通过与邻居之间的信息交互完成。　２．１．１　集中式事件区域检测　图２是文献［１～３］中所使用的检测框架，也是关于事　件检测研究中最为广泛使用的检测框架。在文献Ｅ１］中，假　设对于观测未知假设的Ｎ个传感器，其观测值独立同分　布，则传感器可利用相同的局部判决规则产生Ｎ个二元判　定结果。这些最初的判定结果被传输到汇聚中心，基于一　定的全局判定规则，汇聚中心得到关于未知假设的最终判　定。　图２　ＤＤＳ事件检测框架　在该检测框架中，局部判决规则为：通过将　比　值与阈值　相比较得到第ｉ个传感器节点关于事件是否发　生的判断，即本地的二元决策碥。具体为：当瓮　＞Ａ　１２　时，Ｕｌ一１；当　＜　时，　一ｏ。　』０＼０　，　全局判断规则为：统计从子节点得到的决策１的个数，　与全局阈值ｋ相比较，得到事件是否发生的全局判断，即　：　’虮＿耽＿＿…－＿％　。显然，　值与ｋＵｏ　值的选择　｛　．　．　，　，。显　，＾但勺但利选倬　Ｉｏ，Ｕｌ十“２十…十％＜患　是该检测框架的核心内容。　通常，用来衡量事件检测机制性能的参数包括误检率　与检测率两种。文献１－１］就如何选择优化的　值与ｋ值以　最小化误检率和最大化检测率进行了探讨。在该文献中，　Ｚｈａｎｇ等人分别使用贝叶斯方法和奈曼一皮尔逊方法计算　了使平均误检率最小和在保证误检率较小的条件下使检测　概率最大的（　，　）组合。文献［２］则在文献１－１１的基础上做　了进一步的改进，将传感器故障概率引入到事件检测模型　中，提出了容错的贝叶斯检测机制，并给出了修正后的最优　（　，是）组合的计算方法。　在以上事件检测框架中，邻居节点数目　的选取也是　一个值得商榷的问题。当　过大时，通信开销增大，传感器　网络整体能耗增加；而当”过小时，少量邻居节点之间的协　同却难以消除环境噪声对检测结果带来的影响。文献［２］　得出证明，在给定误检率或检测率的需求下，存在最少数量　的邻居节点数目能使基于上述事件检测算法得出满足两种　需求的结果。此外，该文还给出了一种便于实现的用于确　定最小节点数的迭代计算方法。　在文献［３］中，Ｘｉａｏ等人为考虑噪声对事件检测机制　性能的影响，对文献［１，２］中的检测框架稍作修改，以确定　性信号ｄ与一　代替了原先的二元决策值“　，而后将上述　决策上传检测机制（Ｄｅｃｅｎｔｒａｌｉｚｅｄ　Ｄｅｔｅｃｔｉｏｎ　Ｓｃｈｅｍｅ，简称　ＤＤＳ）同检测精度最高的数据上传检测机制（Ｃｅｎｔｒａｌｉｚｅｄ　Ｄｅｔｅｃｔｉｏｎ　Ｓｃｈｅｍｅ，简称ＣＤＳ）的检测效率进行了比较，并进　行了定量计算，得出结论：在独立同分布的零均值的有限噪　声假设下，同具有　个节点的ＣＤＳ检测框架对比，为达到　，ｒ　ｒ—Ｌ　Ｊ、２　同样的检测效率，ＤＤＳ机制需要　×　个协同节点。　Ｕ　其中，Ｕ为噪声信号绝对值的上限。　决策上传的检测机制虽然在有效利用能量与带宽资源　方面有较大的优势，但其检测准确度毕竟低于数据上传的　检测方式。比如，文献［３］中就是以ＣＤＳ检测机制作为性　能衡量的参考。如果能适当降低该方案中用于数据上传的　资源开销，通过上传数据的集中检测方式在实际应用中也　会有很好的表现。文献［４］将懒惰思想应用到数据发送过　程中，当且仅当节点的测量数据变化超过一定阈值时才向　中心节点进行汇报。这种机制虽然减少了在网络中发送消　息的数据量，但当节点失效时却需要额外的控制开销来发　现这种异常。文献［５］则结合数据上传和决策上传两种检　测方式的优点，提出了一种复合能量驱动检测方案。在该　方案中，每个传感器节点起先依然送出１位的量化结果，当　中心节点根据这一量化结果无法得到满足预定检测准确度　（包括误检率和检测率）的全局决策时，则应要求原发送节　点改为传送最初收集到的真实数据。　２．１．２分布式事件区域检测　Ｋｒｉｓｈｎａ

ｍａｃｈａｒｉ等人在文献［６］中提出了一种分布式　的容错的贝叶斯事件检测机制。通过对周边邻居节点测量　数据的统计与节点故障概率的假设，按照贝叶斯公式，传感　器节点Ｓ　可以计算得到当前测量值的后验概率，从而判断　自己是否位于事件发生区域之中。此外，文献Ｅ６３还提出了　三种根据概率值进行判断的方法：将概率值同［Ｏ，１］内的随　机值进行比较、将概率值同某一固定门限。进行比较、直　接统计与ｓｉ有相同测量值的邻居数目是否超过邻居节点　总数的一半，并经过仿真得出结论：第三种最简单的判别方　法反而拥有最优的性能。　２．２事件边界检测　由于在集中式的区域检测机制中获得事件发生的边界　相对而言较为简单，所以传感器网络中针对事件边界检测　的研究绝大部分都为分布式检测。常见算法可归为三类：　基于统计的算法、基于图像处理的算法和基于分类的算　法川。　（１）基于统计的算法：计算某节点周边邻居中事件判定　为１的节点数目与事件判定为０的节点数目之差，如果差　值绝对值较小，则该节点可能处于事件边界。　（２）基于图像处理的算法：将传感器节点看作整幅图像　中的一个像素，将其读数视为对应像素的亮度或色彩信息，　然后通过滤波器仅仅保留图像中高频率的点，并计算这些　点的数据值沿不同方向的梯度，求其平方和，计算所得结果　较大者即为边沿节点。　（３）基于分类的算法：由于处于事件区域内部与外部的　传感器节点所提供的数据有明显的区别，因此在小型区域　内可以用经过某节点的随机曲线将邻居节点划分为两个部　分（一般选用直线）。通过计算，使两侧传感器节点集合测　量数值差异最大的曲线，可以得到事件的边界划分。　文献［７３对上述三种边界检测算法进行了比较，并得出　结论：基于分类的算法在检测精度上有着最好的表现，但需　要节点的位置信息。　在文献［８３中，Ｄｉｎｇ等人利用第三类算法取得了良好　的边界检测精度，在同类研究中具有一定的代表性。在这　篇文章中，作者使用基于值协作的检测方法取代基于决策　协作的检测方法，用被检测节点数据和邻居节点数据的中　值之差作为判断节点是否处于事件区域之中的标准，并用　直线对邻域进行随机划分，以逼近事件边界。　３分布式协作错误检测　在传感器节点的故障检测中，错误节点一般不具有空　间相关性，使用决策上传的集中式检测机制往往会由于噪　声的影响带来较大的检测误差。但是，考虑到节点故障的　永久性特征，可以通过保留各节点一段时间内的决策值以　消除瞬时错误及噪声的影响［ｇ］。　针对传感器网络中错误检测的研究更多的是使用数据　上传集中式检测与分布式检测两种方式。其中，前者由于　可以对数据进行分析处理，所以多用于对非明显错误节点　的检测；而后者则由于其局部交互、能量高效的特点，多用　于一般错误节点的检测。　在传感器网络应用中，数据上传过程中往往需要进行　多次数据融合，可是引入数据融合后的数据上传机制却存　在一个缺陷，即当传感器节点众多时，在数据融合过程中，　个别节点的错误数据可能会被大量的正常数据所掩盖，从　而使中心节点无法判断是否存在错误节点。在这种情况下　进行的错误检测称作非明显错误节点的检测。为解决这个　问题，文献［９］提出了一种通过主动的交叉验证的方法进行　错误检测。具体做法如下：首先，在传感器网络中由外界注　入检测矢量；然后，将原数据与经过多次融合后的数据进行　比较：若删除某个传感器节点的测量值可以提高融合数据　的一致性，那么就认为这个传感器产生了错误。然而，这种　通过外界注入检测矢量的做法仅仅适用于检测传感器节点　通信部件的错误，对于传感器部件失效的检测，则需要通过　改变外界环境来实现。这与传感器网络应用中尽量减少对　环境影响的初衷是相悖的。　还有一类做法则是通过对中心节点得到的数据集进行　分析来实现错误节点的检测。文献［１０￣１２］中均使用了主　成份分析（Ｐｒｉｍａｒｙ　Ｃｏｍｐｏｎｅｎｔ　Ａｎａｌｙｓｉｓ，简称ＰＣＡ）的方　法。主成份分析是一种去除数据冗余的技术，由于传感器　网络节点密度大，检测环境的变化也较为平缓，来自于不同　节点的数据集合中包含了太多的冗余信息，在这里使用主　成份分析能取得很好的效果。使用ＰＣＡ进行错误检测的　工作流程如图３所示，具体做法如下：首先维护一个ｍＸ　的数据矩阵（其中　为节点数目，ｍ为保留的来自于某个节　点的数据个数），通过矩阵变换提取该矩阵的前ｒ（ｒ＜　）个　主要成份，形成优ｘｒ的子空间，称作正常子空间（Ｎｏｒｍａｌ　Ｓｐａｃｅ），余下的ｍＸ（　—　子空间则称作异常子空间（Ａｂ—　ｎｏｒｍａｌ　Ｓｐａｃｅ）。当一组新的来自于ｎ个节点的数据被收集　到时，新的１×　行向量被更新到原ｍ×ｎ数据矩阵中并重　新进行主成份的计算。通过判断当前数据行向量是否对构　造的异常子空间造成较大波动，可以得知新的数据向量中　是否存在异常数据，并以此作为检测错误节点的依据。