Distance-Constraint k-Nearest Neighbor Searching in Mobile Sensor Networks

The [Formula: see text]-Nearest Neighbors ([Formula: see text] NN) query is an important spatial query in mobile sensor networks. In this work we extend kNN to include a distance constraint, calling it a [Formula: see text]-distant [Formula: see text]-nearest-neighbors ([Formula: see text]- [Formula: see text] NN) query, which finds the [Formula: see text] sensor nodes nearest to a query point that are also at [Formula: see text] or greater distance from each other. The query results indicate the objects nearest to the area of interest that are scattered from each other by at least distance l. The [Formula: see text]- [Formula: see text] NN query can be used in most [Formula: see text] NN applications for the case of well distributed query results. To process an [Formula: see text]- [Formula: see text] NN query, we must discover all sets of [Formula: see text] NN sensor nodes and then find all pairs of sensor nodes in each set that are separated by at least a distance [Formula: see text]. Given the limited battery and computing power of sensor nodes, this [Formula: see text]- [Formula: see text] NN query processing is problematically expensive in terms of energy consumption. In this paper, we propose a greedy approach for [Formula: see text]- [Formula: see text] NN query processing in mobile sensor networks. The key idea of the proposed approach is to divide the search space into subspaces whose all sides are [Formula: see text]. By selecting [Formula: see text] sensor nodes from the other subspaces near the query point, we guarantee accurate query results for [Formula: see text]- [Formula: see text] NN. In our experiments, we show that the proposed method exhibits superior performance compared with a post-processing based method using the [Formula: see text] NN query in terms of energy efficiency, query latency, and accuracy.