DIKNN: An itinerary-based KNN query processing algorithm for mobile sensor networks

Shan Hung Wu, Kun-Ta Chuang, Chung Min Chen, Ming Syan Chen

Research output: Chapter in Book/Report/Conference proceedingConference contribution

42 Citations (Scopus)

Abstract

Current approaches to K Nearest Neighbor (KNN) search in mobile sensor networks require certain kind of indexing support. This index could be either a centralized spatial index or an in-network data structure that is distributed over the sensor nodes. Creation and maintenance of these index structures, to reflect the network dynamics due to sensor node mobility, may result in long query response time and low battery efficiency, thus limiting their practical use. In this paper, we propose a maintenance-free, itinerary-based approach called Density-aware Itinerary KNN query processing (DIKNN). The DIKNN divides the search area into multiple cone-shape areas centered at the query point. It then performs a query dissemination and response collection itinerary in each of the cone-shape areas in parallel. The design of the DIKNN scheme also takes into account challenging issues such as the the dynamic adjustment of the search radius (in terms of number of hops) according to spatial irregularity or mobility of sensor nodes. The simulation results show that DIKNN yields substantially better performance and scalability over previous work, both as k increases and as the sensor node mobility increases. It outperforms the second runner with up to 50% saving in energy consumption and up to 40% reduction in query response time, while rendering the same level of query result accuracy.

Original languageEnglish
Title of host publication23rd International Conference on Data Engineering, ICDE 2007
Pages456-465
Number of pages10
DOIs
Publication statusPublished - 2007 Sep 24
Event23rd International Conference on Data Engineering, ICDE 2007 - Istanbul, Turkey
Duration: 2007 Apr 152007 Apr 20

Publication series

NameProceedings - International Conference on Data Engineering
ISSN (Print)1084-4627

Other

Other23rd International Conference on Data Engineering, ICDE 2007
CountryTurkey
CityIstanbul
Period07-04-1507-04-20

All Science Journal Classification (ASJC) codes

  • Software
  • Signal Processing
  • Information Systems

Fingerprint Dive into the research topics of 'DIKNN: An itinerary-based KNN query processing algorithm for mobile sensor networks'. Together they form a unique fingerprint.

  • Cite this

    Wu, S. H., Chuang, K-T., Chen, C. M., & Chen, M. S. (2007). DIKNN: An itinerary-based KNN query processing algorithm for mobile sensor networks. In 23rd International Conference on Data Engineering, ICDE 2007 (pp. 456-465). [4221694] (Proceedings - International Conference on Data Engineering). https://doi.org/10.1109/ICDE.2007.367891