Processing k Nearest Neighbor Queries for Location-Dependent Data in MANETs

摘要

KNN queries, which retrieve the k nearest data items associated with a location (location-dependent data) from the location of the query issuer, are available for location-based services (LBSs) in mobile environments. Key challenges in designing system protocols for MANETs include low-overhead adaptability to network topology changes due to node mobility, and query processing that achieves high accuracy of the query result without a centralized server. In this paper, we propose the Filling Area (FA) method to process a kNN query in MANETs. To achieve a small search area, data items remain at nodes near the locations with which the items are associated, and nodes cache data items whose locations are near their own. When a node issues a query, neighboring nodes send back their copies, which will likely include the query result.