Research on KNN Query Algorithm in Wireless Sensor Database System

• 1、Institute of Systems Engineering, Tianjin University
• 2、Fok Ying Tung Graduate School, Hong Kong University of Science and Technology
• 3、School of Electrical Engineering and Automation, Tianjin University

Abstract：Efficient search for k nearest neighbors to the given point q (called KNN search) is an important spatial query problem in Wireless Sensor Network (WSN). Based on two types of KNN query algorithms, we introduce a KNN query algorithm which is based on the hybrid index structure. The core idea of the hybrid index structure is as follows: first, the query package is transferred to the given point q using the GPSR geographic routing algorithm which is not based on the index structure; second, after receiving the query package, the point q estimate the search radius based on the number k; finally, the interesting data within the search radius is retrieved using the R-Tree structure search approach. We also present a kind of radius estimation algorithm to optimize query radius and a heuristic KNN query algorithm for dynamic topology structure in mobile WSN applications. The simulation results show that hybrid index structure yields a good tradeoff between index structure and non-index structure, achieving low energy consumption and high query accuracy.

Keywords： Wireless Sensor Network Spatial Query KNN Index Structure