Modeling and Analysis of Opportunistic Routing in Multi-hop Wireless Networks

Opportunistic Routing (OR) takes advantage of the broadcast nature of the wireless medium to increase reliability in communications. Instead of selecting one node as the next-hop forwarder, OR selects a set of candidates to forward the packet. In this way, if one of them does not receive the packet from the source, another candidate will be able to do it, this avoids the need for a re-transmission from the source. To increase the successful delivery ratio, we can increase the size of the candidate set or the number of re-transmissions, but, we must take into account the impact on the use of the network resources. In this paper, we propose a Markov chain as a general model for OR that can be applied to any kind of network topology and any candidate selection algorithm without any constraint. The only input parameters needed are: i) the candidate list of each node, ii) the link delivery probability between nodes, and, iii) the maximum number of re-transmissions in each node. Taking this data into account, our model allows for the evaluation of the performance of different candidate selection algorithms according to different metrics, such as the expected number of transmissions (ExNT), which is one of the most relevant metrics in OR. Our model also enables an evaluation of the influence of the number of candidates, its relation to the number of re-transmissions and how these two parameters together contribute to the successful delivery of data packets.