Opportunistic routing with congestion diversity and tunable overhead

This paper considers the problem of routing packets across a multi-hop network consisting of multiple sources of traffic and wireless links with stochastic reliability and a broadcast nature. Opportunistic routing relies on the following principle. Each packet transmission can be overheard by a random subset of receiver nodes among which the next relay can be selected opportunistically. This paper surveys and revisits known opportunistic routing policies: Opportunistic variants of shortest path routing, such as extremely opportunistic routing (ExOR) and stochastic routing (SR), select the relay on the shortest path to the destination. The opportunistic variants of backpressure routing, such as diversity backpressure routing (DIVBAR), select the relay with the least queue backlog. In an enhanced version of DIVBAR (E-DIVBAR), a combination of queue backlogs and expected number of transmissions is used as the selection criterion. Finally, combining important aspects of shortest path routing with those of backpressure routing, opportunistic routing with congestion diversity (ORCD) uses a measure of draining time to opportunistically identify and route packets along the paths with an expected low overall congestion. One of the critical aspects of the design of opportunistic routing policies is the issue of control overhead. This paper considers the issue of performance in conjunction with the additional overhead cost. In particular, modifications of the routing policies for which overhead cost is traded-off with the performance, i.e. delay, are provided and compared via simulations. In addition to the overhead associated with opportunism, ORCD requires a high computation/control overhead associated with estimating the draining time. Various modifications to ORCD are also proposed and their performance and overhead are evaluated.