Scalable hypergrid k-NN-based online anomaly detection in wireless sensor networks

Miao Xie, Jiankun Hu, Song Han, Hsiao-Hwa Chen

Research output: Contribution to journalArticlepeer-review

82 Citations (Scopus)


Online anomaly detection (AD) is an important technique for monitoring wireless sensor networks (WSNs), which protects WSNs from cyberattacks and random faults. As a scalable and parameter-free unsupervised AD technique, (k)-nearest neighbor (kNN) algorithm has attracted a lot of attention for its applications in computer networks and WSNs. However, the nature of lazy-learning makes the kNN-based AD schemes difficult to be used in an online manner, especially when communication cost is constrained. In this paper, a new kNN-based AD scheme based on hypergrid intuition is proposed for WSN applications to overcome the lazy-learning problem. Through redefining anomaly from a hypersphere detection region (DR) to a hypercube DR, the computational complexity is reduced significantly. At the same time, an attached coefficient is used to convert a hypergrid structure into a positive coordinate space in order to retain the redundancy for online update and tailor for bit operation. In addition, distributed computing is taken into account, and position of the hypercube is encoded by a few bits only using the bit operation. As a result, the new scheme is able to work successfully in any environment without human interventions. Finally, the experiments with a real WSN data set demonstrate that the proposed scheme is effective and robust.

Original languageEnglish
Article number6295612
Pages (from-to)1661-1670
Number of pages10
JournalIEEE Transactions on Parallel and Distributed Systems
Issue number8
Publication statusPublished - 2013 Jul 17

All Science Journal Classification (ASJC) codes

  • Signal Processing
  • Hardware and Architecture
  • Computational Theory and Mathematics


Dive into the research topics of 'Scalable hypergrid k-NN-based online anomaly detection in wireless sensor networks'. Together they form a unique fingerprint.

Cite this