Peer-to-peer bichromatic reverse nearest neighbours in mobile ad-hoc networks

Thao Nghiem, Kiki Maulana Adhinugraha, Kinh Nguyen, David Geoffrey Green, Agustinus Borgy Waluyo, David Taniar

    Research output: Contribution to journalArticleResearchpeer-review

    11 Citations (Scopus)


    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 Neighbour (RNN). An RNN query returns all objects that consider the query object as their nearest neighbour. Existing methods mostly rely on a centralised base station. However, mobile P2P systems offer many benefits, including self-organisation, fault-tolerance and load-balancing. In this study, we propose and evaluate 3 distinct P2P algorithms focusing on bichromatic RNN queries, in which mobile query peers and static objects of interest are of two different categories, based on a time-out mechanism and a boundary polygon around the mobile query peers. The Brute-Force Search Algorithm provides a naive approach to exploit shared information among peers whereas two other Boundary Search Algorithms filter a number of peers involved in query processing. The algorithms are evaluated in the MiXiM simulation framework with both real and synthetic datasets. The results show the practical feasibility of the P2P approach for solving bichromatic RNN queries for mobile networks.

    Original languageEnglish
    Pages (from-to)3128-3140
    Number of pages13
    JournalJournal of Parallel and Distributed Computing
    Issue number11
    Publication statusPublished - 2014


    • Collaborative caching
    • Mobile ad-hoc networks
    • Mobile database
    • P2P spatial queries
    • Reverse nearest neighbours

    Cite this