Localized Outlying and Boundary Data Detection in Sensor Networks
- 25 June 2007
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Knowledge and Data Engineering
- Vol. 19 (8), 1145-1157
- https://doi.org/10.1109/tkde.2007.1067
Abstract
This paper targets the identification of outlying sensors (that is, outlying reading sensors) and the detection of the reach of events in sensor networks. Typical applications include the detection of the transportation front line of some vegetation or animalcule's growth over a certain geographical region. We propose and analyze two novel algorithms for outlying sensor identification and event boundary detection. These algorithms are purely localized and, thus, scale well to large sensor networks. Their computational overhead is low, since only simple numerical operations are involved. Simulation results indicate that these algorithms can clearly detect the event boundary and can identify outlying sensors with a high accuracy and a low false alarm rate when as many as 20 percent sensors report outlying readings. Our work is exploratory in that the proposed algorithms can accept any kind of scalar values as inputs-a dramatic improvement over existing work, which takes only 0/1 decision predicates. Therefore, our algorithms are generic. They can be applied as long as "events" can be modeled by numerical numbers. Though designed for sensor networks, our algorithms can be applied to the outlier detection and regional data analysis in spatial data mining.Keywords
This publication has 13 references indexed in Scilit:
- On the complexity of approximating tsp with neighborhoods and related problemscomputational complexity, 2006
- TSP with neighborhoods of varying sizeJournal of Algorithms, 2005
- Evolutionary Optimization in Uncertain Environments—A SurveyIEEE Transactions on Evolutionary Computation, 2005
- Approximation Algorithms for Euclidean Group TSPLecture Notes in Computer Science, 2005
- Approximation algorithms for TSP with neighborhoods in the planeJournal of Algorithms, 2003
- Wireless sensor networks: a surveyComputer Networks, 2002
- Completely Derandomized Self-Adaptation in Evolution StrategiesEvolutionary Computation, 2001
- A Fast Approximation Algorithm for TSP with Neighborhoods and Red-Blue SeparationLecture Notes in Computer Science, 1999
- Approximation algorithms for the geometric covering salesman problemDiscrete Applied Mathematics, 1994
- The Euclidean travelling salesman problem is NP-completeTheoretical Computer Science, 1977