Abstract

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 monograph sheds light on the performance gains associated with incorporating into the routing strategy the nature of wireless transmission. This monograph 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 performance is examined against the performance of several routing algorithms from the literature. The performance is examined first in analytical examples, then via simulation to identify the strengths of the optimal opportunist routing algorithm. 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 monograph also addresses how learning the wireless medium can be efficiently incorporated in the structure of routing algorithm. Finally, this monograph examines the dynamic congestion-based distance metric and its performance against other congestion aware solutions in the literature.

Opportunistic Routing in Wireless Networks

Wireless multi-hop networks have become an important part of many modern communication systems. Some of the earliest examples were military communication networks utilizing wireless relays in remote areas. More recently, many industries have used wireless multi-hop networks to create a multitude of fascinating tools and systems.

Motivated by classical routing solutions in the Internet, conventional routing attempts to find a fixed path along which the packets are forwarded. Such fixed path schemes fail to take advantage of the broadcast nature and opportunities provided by the wireless medium, and result in unnecessary packet retransmissions. In opportunistic routing, decisions are made in an online manner by choosing the next relay based on the actual transmission outcomes as well as a rank ordering of neighboring nodes.

Opportunistic Routing in Wireless Networks provides the motivation for opportunistic routing, and presents several different algorithms which achieve better performance, in most scenarios, than conventional shortest path routing. This comprehensive survey provides a starting point for all researchers and students wishing to learn the background and technical details of opportunistic routing.