An efficient decentralized keyword lookup scheme for MANETs

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.