The k -Nearest Neighbors ( k 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 l -distant k -nearest-neighbors ( l - k NN) query, which finds the k sensor nodes nearest to a query point that are also at l 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 l - k NN query can be used in most k NN applications for the case of well distributed query results. To process an l - k NN query, we must discover all sets of k NN sensor nodes and then find all pairs of sensor nodes in each set that are separated by at least a distance l . Given the limited battery and computing power of sensor nodes, this l - k NN query processing is problematically expensive in terms of energy consumption. In this paper, we propose a greedy approach for l - k 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 l . By selecting k sensor nodes from the other subspaces near the query point, we guarantee accurate query results for l - k NN. In our experiments, we show that the proposed method exhibits superior performance compared with a post-processing based method using the k NN query in terms of energy efficiency, query latency, and accuracy.
展开▼
