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