A Distributed Hash Table for Wireless Ad Hoc Networks

F. Araújo, L. Rodrigues, J. Kaiser, C. Liu, and C. Mitidieri

Selected sections of this report were published in the Proceedings of the Fourth International Workshop on Distributed Event-Based Systems (DEBS'05), in conjuction with the 25th International Conference on Distributed Computing Systems (ICDCS-25), Columbus, Ohio, USA, June 2005.


This paper focuses on the problem of implementing a distributed hash table (DHT) in wireless ad hoc networks. Scarceness of resources and node mobility turn routing into a challenging problem and therefore, we claim that building a DHT as an overlay network (like in wired environments) is not the best option. Hence, we present a proof-of-concept DHT, called Cell Hash Routing (CHR), designed from scratch to cope with problems like limited available energy, communication range or node mobility. CHR overcomes these problems, by using position information to organize a DHT of clusters instead of individual nodes. By using position-based routing on top of these clusters, CHR is very efficient. Furthermore, its localized routing and its load sharing schemes, make CHR very scalable in respect to network size and density. For these reasons, we believe that CHR is a simple and yet powerful adaptation of the DHT concept for wireless ad hoc environments.

Also available extended report (pdf) .

Luís Rodrigues