Chapter 2

Taxonomy of Opportunistic Routing: Principles and Behaviors

This chapter analyzes the principles of the local behavior of GOR. We then introduce the least cost opportunistic/anypath routing, and present some of its important properties. Finally, we describe two polynomial-time algorithms that select the optimal forwarding candidates at each hop to achieve the shortest anypath cost from a source to a destination.

For GOR, we first generalize the definition of expected packet advancement (EPA) for an arbitrary number of forwarding candidates that follow a specific priority rule to relay the packet in OR. Through theoretical analysis, we prove that the maximum EPA can only be achieved by giving the forwarding candidates closer to the destination higher relay priorities. This relay priority rule convinces us that given a forwarding candidate set, the relay priority among the candidates is only relevant to the advancement achieved by the candidate to the destination, but is irrelevant to the packet delivery ratio between the transmitter and the forwarding candidate. The analysis result is the upper bound of the EPA that any GOR can achieve. We further prove that, given a set of M nodes that are available as next-hop neighbors, a subset of the available next-hop neighbors with r (r < M) nodes achieving the maximum EPA is contained in a subset with more nodes achieving the maximum EPA. Leveraging the containing property, we demonstrate that the maximum EPA of selecting r(r ≤ M) nodes is a strictly increasing and concave function of r. This property indicates that although getting more forwarding candidates involved in GOR will increase the maximum EPA, the extra EPA gained by doing so becomes less significant. It also implies consistency between EPA and reliability. These principles of GOR will help us analyze the capacity of OR in Chapters 4 and 5, and design efficient local candidate selection and prioritization algorithms for achieving energy and throughput efficiency in Chapters 3 and 8, respectively.