WSN中基于对偶线性规划的异常检测和定位算法

Anomaly Detection and Localization Algorithm Based on Linear Programming Duality in Wireless Sensor Networks[HS)]

摘要:

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

Abstract:

In this paper, we present 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 anomalous links as possible and narrow down suspicious areas to be examined in the second phase. The probe selection problem in this phase is formulated as a budgeted maximum coverage problem, and we propose 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 the missed detection rate of our algorithm is the same with the exact solution, but the speed of our algorithm is much faster than the exact solution.