K NN Query Processing Methods in Mobile Ad Hoc Networks

• Published in: IEEE transactions on mobile computing 2014-05, Vol.13 (5), p.1090-1103
• Main Authors: Komai, Yuka, Sasaki, Yuya, Hara, Takahiro, Nishio, Shojiro
• Format: Magazinearticle
• Language: English
• Subjects: Accuracy; Ad hoc networks; Distributed databases; Mobile computing; Mobile nodes; Query processing; Spatial databases; Spirals
• ISSN: 1536-1233; 1558-0660
• DOI: 10.1109/TMC.2013.133

In this paper, we propose two beacon-less kNN query processing methods for reducing traffic and maintaining high accuracy of the query result in mobile ad hoc networks (MANETs). In these methods, the query-issuing node first forwards a kNN query using geo-routing to the nearest node from the point specified by the query (query point). Then, the nearest node from the query point forwards the query to other nodes close to the query point, and each node receiving the query replies with the information on itself. In this process, we adopt two different approaches: the Explosion (EXP) method and the Spiral (SPI) method. In the EXP method, the nearest node from the query point floods the query to nodes within a specific circular region, and each node receiving the query replies with information on itself. In the SPI method, the nearest node from the query point forwards the query to other nodes in a spiral manner, and the node that collects a satisfactory kNN result transmits the result to the query-issuing node. Experimental results show that our proposed methods reduce traffic and achieve high accuracy of the query result, in comparison with existing methods.