On the Effectiveness of the 2-hop Routing Strategy in Mobile Ad Hoc Networks

In this paper, we study the performance of the 2-hop routing scheme proposed for ad hoc wireless networks with mobile nodes, considering realistic node mobility patterns. First, we provide a formal definition of optimal routing maximizing the throughput of a mobile ad hoc network, in terms of a multi-commodity flow problem over the associated contact graph. Then, we relate the effectiveness of the 2-hop routing strategy to structural properties of the contact graph. We present experimental results showing that, in real networks, contact times among the nodes are largely inhomogeneous. Our results show that, in networks with inhomogeneous contact times, the 2-hop routing strategy can result strongly inefficient in terms of network throughput.