Algorithm Design for Opportunistic Routing Based on State Transition

Available Opportunistic Routing (OR) works adopted a relay scheme, which is derived from the traditional wireless routing algorithms. In such scheme, each node is assigned with a global metric or next-hop nodes set. In this paper, it is proved that the relay scheme can not always get the optimal performance by counterexample. The OR process is proposed to be regarded as a Markovian chain of different states from the perspective of state transition, where the states denote different set of nodes that have received the packet. Then the OR algorithms are modeled to help to investigate the intrinsic behavior of OR. It can be applied to the scenarios of multicast and multiple collision domains. Based on that, optimal algorithm named Shortest Opportunistic Routing (SOR) is proposed and proved, which can yield the least Expected Transmission Count (ETX) cost in both scenarios of multicast and multiple collision domain. Simulation results verify the superiority of SOR and show that the performance of SOR surpasses previous algorithms. The optimal OR strategy of wireless multi-hop networks can be selected and the minimal end-to-end ETX cost can be yielded by utilizing the proposed SOR.