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

    9 Citations (Scopus)

    Abstract

    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
    Volume74
    Issue number11
    DOIs
    Publication statusPublished - 2014

    Keywords

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

    Cite this

    Nghiem, Thao ; Adhinugraha, Kiki Maulana ; Nguyen, Kinh ; Green, David Geoffrey ; Waluyo, Agustinus Borgy ; Taniar, David. / Peer-to-peer bichromatic reverse nearest neighbours in mobile ad-hoc networks. In: Journal of Parallel and Distributed Computing. 2014 ; Vol. 74, No. 11. pp. 3128-3140.
    @article{4024c8019a114f05b4887061b3025ef0,
    title = "Peer-to-peer bichromatic reverse nearest neighbours in mobile ad-hoc networks",
    abstract = "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.",
    keywords = "Collaborative caching, Mobile ad-hoc networks, Mobile database, P2P spatial queries, Reverse nearest neighbours",
    author = "Thao Nghiem and Adhinugraha, {Kiki Maulana} and Kinh Nguyen and Green, {David Geoffrey} and Waluyo, {Agustinus Borgy} and David Taniar",
    year = "2014",
    doi = "10.1016/j.jpdc.2014.07.007",
    language = "English",
    volume = "74",
    pages = "3128--3140",
    journal = "Journal of Parallel and Distributed Computing",
    issn = "0743-7315",
    publisher = "Elsevier",
    number = "11",

    }

    Peer-to-peer bichromatic reverse nearest neighbours in mobile ad-hoc networks. / Nghiem, Thao; Adhinugraha, Kiki Maulana; Nguyen, Kinh; Green, David Geoffrey; Waluyo, Agustinus Borgy; Taniar, David.

    In: Journal of Parallel and Distributed Computing, Vol. 74, No. 11, 2014, p. 3128-3140.

    Research output: Contribution to journalArticleResearchpeer-review

    TY - JOUR

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

    AU - Nghiem, Thao

    AU - Adhinugraha, Kiki Maulana

    AU - Nguyen, Kinh

    AU - Green, David Geoffrey

    AU - Waluyo, Agustinus Borgy

    AU - Taniar, David

    PY - 2014

    Y1 - 2014

    N2 - 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.

    AB - 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.

    KW - Collaborative caching

    KW - Mobile ad-hoc networks

    KW - Mobile database

    KW - P2P spatial queries

    KW - Reverse nearest neighbours

    UR - http://www.scopus.com/inward/record.url?scp=85027933295&partnerID=8YFLogxK

    U2 - 10.1016/j.jpdc.2014.07.007

    DO - 10.1016/j.jpdc.2014.07.007

    M3 - Article

    VL - 74

    SP - 3128

    EP - 3140

    JO - Journal of Parallel and Distributed Computing

    JF - Journal of Parallel and Distributed Computing

    SN - 0743-7315

    IS - 11

    ER -