Bichromatic Reverse Nearest Neighbors in mobile peer-to-peer networks

摘要

The increasing use of mobile communications has raised many issues of decision support and resource allocation. A crucial problem is how to solve queries of Reverse Nearest Neighbor (RNN). An RNN query returns all objects that consider the query object as their nearest neighbor. Existing methods mostly rely on a centralized base station. However, mobile P2P systems offer many benefits, including self-organization, fault-tolerance and load-balancing. In this study, we propose two P2P algorithms focusing on bichromatic RNN queries, in which mobile query objects and static objects of interest are of two different categories, based on a boundary polygon around the mobile query object. The Exhaustive Search Algorithm makes use of all information from the peers to aim at high accuracy rate while the Optimized Search Algorithm reduces the number of queried peers. The algorithms are evaluated in MiXiM simulation framework with a real dataset. The results show the practical feasibility of the P2P approach in solving bichromatic RNN queries for mobile networks.