Double indirect access: Efficient peer-to-peer object lookup protocol in location-aware mobile ad hoc networks

Abstract

Geographic distributed hash table (DHT) protocols are considered to be efficient for P2P object sharing in mobile ad-hoc networks. These protocols assume that the set of (key, value) pairs, called indexes, should be distributed among nodes according to the following hashing mapping rule: A key hashes into a geographic coordinate, and the corresponding index is stored at the node closest to the key's hash value. Therefore, when a node changes its position, some indexes have to be redistributed to other nodes in order to keep the hashing mapping rule consistent. The overhead of index redistribution may be high enough to impact the normal lookup operation if each node contains a large number of indexes. In this paper, we propose an efficient lookup protocol, called Double Indirect Access, that dispenses with index redistribution to improve lookup performance. The main idea is to determine the mapping from an index to a node not by the node's position, but by the node's static identifier that is obtained by hashing its MAC address into a geographic coordinate. However, a key lookup request will be routed to some node based on the key's hash value, resulting in failure of locating the index. In Double Indirect Access, the node to which a key lookup request has been routed is named as an indirection server, and it is responsible for relaying the lookup request to the node storing the corresponding index. In order for the indirection server to find out the correct destination node for the lookup request, it maintains a list of nodes' static identifiers whose values (i.e., geographic coordinates) are close to the location of the indirection server. Simulation results show that, when the average number of objects per node is more than 256, our approach is able to reduce the number of packet transmissions by about a half compared to the conventional geographical DHT protocol. It is also shown that, even when the average number of objects per node is about 9-16, the overhead of our approach is comparable with the conventional protocol.