M.-S.: Diknn: an itinerary-based knn query processing algorithm for mobile sensor networks. ICDE’07

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 dis-tributed 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 re-sponse 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 ar-eas in parallel. The design of the DIKNN scheme also takes into account challenging issues such as the the dy-namic adjustment of the search radius (in terms of number of hops) according to spatial irregularity or mobility of sen-sor nodes. The simulation results show that DIKNN yields substantially better performance and scalability over previ-ous work, both as k increases and as the sensor node mo-bility increases. It outperforms the second runner with up to 50 % saving in energy consumption and up to 40 % reduc-tion in query response time, while rendering the same level of query result accuracy.