Opportunistic routing in wireless ad hoc networks: Upper bounds for the packet propagation speed

Classical routing strategies for mobile ad hoc networks forward packets on a pre-defined route (typically obtained by a shortest path routing protocol). Research has high-lighted the interest in developing opportunistic routing schemes, where the next relay is selected dynamically for each packet and each hop. This allows each packet to take advantage of the local pattern of transmissions at any time. The objective of such opportunistic routing schemes is to minimize the end-to-end delay required to carry a packet from the source to the destination. In this paper, we provide upper bounds on the packet propagation speed for opportunistic routing, in a realistic network model where link conditions are variable. We analyze the performance of various opportunistic routing strategies and we compare them with classical routing schemes. The analysis and simulations show that opportunistic routing performs significantly better. We also investigate the effects of mobility. Finally, we present numerical simulations that confirm the accuracy of our bounds.