Outlier Detection In Sensor Networks

With the development of microelectronic, computing, wireless communication and other relative technologies, low-power and multi-function sensors gain much evolution. The sensor networks comprising a large number of sensors are used to sample and deal with all kinds of information in the monitoring area. In the application of monitoring, users are more interested in abnormal values (Outliers) indicating some unexpected events, rather than normal values. Therefore, how to detect outliers (including data outliers and node outliers) becomes our new challenge.For data outlier detection, we present an algorithm for both snapshot and continuous queries, which can be used to unsupervisedly detect global top n data outliers. We design a commit-disseminate-verify mechanism for outlier detection in aggregation tree and define two novel concepts: modifier set and candidate set for the global outliers. Using this mechanism and these two concepts, the global top n data outliers can be detected through exchanging short messages in aggregation tree. Theoretically, we prove the correctness of our algorithm. The experiment results show that our algorithm consumes less communication and has lower latency.For node outlier detection, we present an algorithm to detect node outliers in spatio-temporal model. We strictly define the spatio-temporal node outlier. The definition we give has fully considered the instability of sensor networks and the similarity of data in time and space. We design an approach (Time-limit Free Matching) to compute the similarity of the time series generated by two nodes, which is suitable for sensor network environment. And we compute nodes'deviation rank through weighting the similarity of two nodes by their spatial distance. The algorithm we give computes the upper bound and lower bound of node's deviation rank by only using a few eigenvalues of the sample, and then judges whether a node is a node outlier or not. The experiment results show that usually, our approach can significantly reduce the communication for node outlier detection.