An Efficient Decentralized Keyword Lookup Scheme For Manets


Geographic Hashing; Geographic Routing; Keyword lookup; Location-based Services; Mobile Ad hoc Networks


This paper considers the keyword lookup problem, which is essential for enabling keyword-based information sharing applications, such as file sharing, in Mobile Ad hoc Networks (MANET). In keyword-based information sharing applications, a data item is described by an index pair (key, value). To publish the data item, the corresponding index pair is inserted into the network. A node looking for a data item can now query the network using keywords (key) to obtain the reference of the data item (value). While a number of data dissemination protocols have been proposed for MANETs, our problem is unique in that we focus on finding a decentralized keyword lookup solution by utilizing location information of participating nodes. Our solution embeds a virtual grid structure on the geographic area, and relies upon two foundations: a geographic hash function, and an underlying geographic routing protocol. An index pair is hashed to a virtual square grid using the geographic hash function. Insertion and lookup messages are routed by the geographic routing protocol. Using analytical and simulation-based evaluations, we show that the system is able to answer keyword lookup queries with high success rate, requires reasonable communication overhead, and handles network dynamics well under pragmatic assumptions.

Publication Date


Publication Title

Proceedings of the 2005 International Conference on Wireless Networks, ICWN'05

Number of Pages


Document Type

Article; Proceedings Paper

Personal Identifier


Socpus ID

60749134475 (Scopus)

Source API URL


This document is currently not available here.