Proximity neighbor selection for a DHT in wireless multi-hop networks

A mobile ad hoc network (MANET) is a multi-hop wireless network having no infrastructure. Thus, the mobile nodes have to perform basic control tasks, such as routing, and higher-level tasks, such as service discovery, in a cooperative and distributed way. Originally conceived as a peer-to-peer application for the Internet, distributed hash tables (DHTs) are data structures offering both, scalable routing and a convenient abstraction for the design of applications in large, dynamic networks. Hence, DHTs and MANETs seem to be a good match, and both have to cope with dynamic, self-organizing networks. DHTs form a virtual control structure oblivious to the underlying network. Several techniques to improve the performance of DHTs in wired networks have been established in the literature. A particularly efficient one is proximity neighbor selection (PNS). PNS has to continuously adapt the virtual network to the physical network, incurring control traffic. The applicability of PNS and DHTs for MANETs commonly is regarded as hard because of this control traffic, the complexity of the adaptation algorithms, and the dynamics of a MANET. Using simulations supported by analytical methods, we show that by making a minor addition to PNS, it is also applicable for MANETs. We additionally show that the specifics of a MANET make PNS an easy exercise there. Thus, DHTs deliver good performance in MANETs.