计算机科学 ›› 2015, Vol. 42 ›› Issue (4): 89-93.doi: 10.11896/j.issn.1002-137X.2015.04.017

• 网络与通信 • 上一篇    下一篇

一种改进的WSN异常检测和定位算法研究

赖 锴,王新兵   

  1. 河南财经政法大学计算机与信息工程学院 郑州450002,上海交通大学电子信息与电气工程学院 上海200240
  • 出版日期:2018-11-14 发布日期:2018-11-14
  • 基金资助:
    本文受国家自然科学基金重点项目:无线网络资源分配与性能评价(61325012/F020809)资助

Research on Improved Anomaly Detection and Localization Algorithm in Wireless Sensor Networks

LAI Kai and WANG Xin-bing   

  • Online:2018-11-14 Published:2018-11-14

摘要: 异常快速检测和定位对于保证无线传感器网络的有效运行具有重要作用。提出了一种改进的传感器网络异常检测和定位方法。该方法通过两个阶段的探查来收集端到端测量数据以实现异常检测和定位。第1阶段探查的目的是选择可以覆盖最大数量异常链路的探点,缩小可疑区域范围,供第2阶段探查,这一阶段的探点选择问题被建模为预算有限条件下的覆盖范围最大化问题,提出一种基于对偶线性规划的高效近似方法来求解此问题。第2阶段的目的是以最小的通信代价,定位出导致观察到的端到端异常现象的具体链路,并根据多环置信度传播算法(LBP)来预测诊断质量。在不同网络设置下展开实验,结果表明,相比于精确求解方法,提出的算法性能略有下降但运行速度更快。

关键词: 无线传感器网络,异常检测,定位,测量数据,探点,线性规划

Abstract: Fast anomaly detection and localization are critical to ensure effective functioning of wireless sensor networks.This paper presented an improved anomaly detection and localization algorithm in wireless sensor networks,where network heterogeneity is exploited for better bandwidth and energy efficiency.End-to-end measurements are collected through a two-phase probing.The goal of the first phase probing is to select probes that can cover as many anoma-lous links as possible and narrow down suspicious areas to be examined in the second phase.The probe selection pro-blem in this phase is formulated as a budgeted maximum coverage problem.We proposed an efficient approximation algorithm to solve it based on linear programming duality.The second phase probing is aimed at locating individual links that are responsible for the observed end-to-end anomalies with minimum communication cost.The prediction of diagnosis quality is carried out using the loopy belief propagation (LBP) algorithm.Experimental results show that our algorithm is much faster than the exact solution at the cost of slight performance degradation.

Key words: Wireless sensor networks,Anomaly detection,Localization,Measurements,Probe,Linear programming

[1] 钱志鸿,王义君.面向物联网的无线传感器网络综述[J].电子与信息学报,2013,35(1):215-227
[2] 张鹏,冯欣,周建国.无线传感器网络中基于空间关联性的聚类异常检测算法[J].计算机应用研究,2013,30(5):1370-1372
[3] 姜旭宝,李光耀,连朔.基于变宽直方图的无线传感器网络异常数据检测算法[J].计算机应用,2011,31(3):694-697
[4] 肖政宏,陈志刚,李庆华.WSN中基于分布式机器学习的异常检测仿真研究[J].系统仿真学报,2011,23(1):121-127
[5] 朱翠涛,瞿毅.基于压缩感知的稀疏事件检测[J].中南民族大学学报:自然科学版,2011,30(1):81-83
[6] Yigal Bejerano.Coverage Verification without Location Information [J].IEEE Transactions on Mobile Computing,2012,1(4):631-643
[7] 张玉琴,秦拯.无线传感器网络中基于分簇的节点定位异常检测[J].计算机应用,2010,27(3):1139-1141
[8] 杨黎斌,慕德俊,蔡晓妍.基于核聚类的无线传感器网络异常检测方案[J].传感技术学报,2008,21(8):1442-1447
[9] Lu K,Qian Y,Guizani M,et al.A framework for a distributed key management scheme in heterogeneous wireless sensor networks [J].IEEE Transactions on Wireless Communications,2008,7(2):639-647
[10] Cheng L,Qiu X,Meng L,et al.efficient active probing for fault diagnosis in large scale and noisy networks[C]∥INFOCOM,2010 Proceedings IEEE.IEEE,2010:1-9
[11] Jsang A,Ismail R.The beta reputation system[C]∥Proceedings of the 15th Bled Electronic Commerce Conference.2002:41-55
[12] Khuller S,Moss A,Naor J S.The budgeted maximum coverage problem [J].Information Processing Letters,1999,70(1):39-45
[13] Golovin D,Krause A.Adaptive Sub-modularity:A New Ap-proach to Active Learning and Stochastic Optimization[C]∥COLT.2010:333-345
[14] Zheng A X,Rish I,Beygelzimer A.Efficient test selection in active diagnosis via entropy approximation [J].arXiv preprint arXiv:1207.1418,2012
[15] Murphy K.The bayes net toolbox for matlab [J].Computing science and statistics,2001,33(2):1024-1034

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!