Opportunistic Routing in Wireless Networks

Wireless multi-hop networks have become an important part of many modern communication systems. Opportunistic routing aims to overcome the deficiencies of conventional routing on wireless multi-hop networks, by specifically utilizing wireless broadcast opportunities and receiver diversity. Opportunistic routing algorithms, which are specifically optimized to incorporate into the routing decisions a model of wireless transmission, take advantage of scheduling, multi-user, and receiver diversity gains and result in significant reduction in the expected cost of routing per packet. The ability of the algorithm to take advantage of the aspects of wireless transmission, however, depends on the scalability and the additional overhead associated with the opportunistic routing as well as the availability of side information regarding wireless channel statistics, topology, etc. This manuscript sheds light on the performance gains associated with incorporating into the routing strategy the nature of wireless transmission and devises algorithms and solutions to realize these gains in a scalable, practical, and low cost manner. This manuscript first provides an overview of various opportunistic distance-vector algorithms that have been developed to incorporate wireless transmission and routing opportunities. Furthermore, an optimal opportunistic distance metric is proposed whose construction follows from a dynamic programming characterization of the problem. The performance of the optimal routing is then examined against the performance of several other known routing algorithms. To allow for a scalable and distributed solution, the distributed computation of this optimal distance-metric is provided. The performance of a distributed implementation of the optimal opportunistic routing algorithm is also examined via simulation. In addition to the construction of the opportunistic schemes in centralized and distributed fashions, this manuscript also addresses how learning the wireless medium can be efficiently incorporated in the structure of routing algorithm. Finally, this manuscript examines the dynamic congestion-based distance metric and its performance against other congestion aware solutions in the literature.