11.1 Summary

The essential idea of opportunistic routing is to exploit the broadcast nature and space diversity provided by the wireless medium. By having multiple forwarding candidates, the successful rate of each transmission can be much improved. However, a good OR protocol is to decide which set of nodes (in contrast to which single node) are good to form the forwarding candidate set and how they should be prioritized. Although we are taking opportunities, we want the packets to be routed to the destination through a set of paths that are statistically optimal. In this book, we presented principles of the local behavior of OR, we analyzed the capacity, throughput and energy efficiency of OR, we developed a new candidate coordination scheme for OR, and we designed secure link quality measurement mechanism.

In Chapter 2, we found and proved properties of the local behavior of OR and the associated candidate selection and prioritization issues. In Chapter 3 we proposed an energy-efficient geographic opportunistic routing framework and corresponding local candidate selection and prioritization algorithms. The contributions of Chapters 4 and 5 present an analytical model to compute the end-to-end throughput bound and capacity of OR in multiradio, multichannel and multirate wireless networks. In Chapter 6, we presented a new, efficient candidate coordination scheme, which takes advantage of physical layer information. Chapter 7 demonstrated how network coding can be integrated with opportunistic routing. We studied the performance of multirate GOR under a contention-based medium-access scenario in Chapter 8. In Chapter 9, we presented a secure link quality measurement mechanism, which is able to prevent a malicious attacker from reporting a fake link quality. We further investigated the security issues about opportunistic routing. Opportunistic broadcast in VANETs is studied in Chapter 10. We summarize our results by chapter below.

• Chapter 2. In this Chapter, we generalized the definition of EPA for an arbitrary number of forwarding candidates in GOR. Through theoretical analysis, we showed that the maximum EPA can only be achieved by giving the forwarding candidates closer to the destination higher relay priorities when a forwarding candidate set is given. We give the analytical result of the upper bound of the EPA that any GOR can achieve. We also showed that giving an available next-hop neighbor set with M nodes, the maximum EPA achieved by selecting r (1 ≤ r ≤ M) nodes is a strictly increasing and concave function of r. We proved that a feasible subset of the available next-hop neighbor set that achieves that maximum EPA is contained in at least one feasible subset with more nodes. We also showed that increasing the maximum EPA is consistent with increasing the one-hop reliability. Least-cost opportunistic routing is introduced and important properties about it are presented. Then two polynomial time algorithms that find the least-cost opportunistic path are introduced.
• Chapter 3. In this chapter, we studied the geographic opportunistic routing strategy with both routing and energy efficiencies as the major concerns. We proposed a new routing metric, which evaluates EPA per unit of energy consumption so that energy efficiency can be taken into consideration in routing. By leveraging the proved findings in Chapter 2, we proposed two localized candidate-selection algorithms with O(M3) and O(M2) running time in the worst case, respectively, and Ω(M) in the best case, where M is the number of available next-hop neighbors. The algorithms efficiently determine the forwarding candidate set that maximizes the proposed new metric for energy efficiency, namely, the EPA per unit of energy consumption. We further proposed an EGOR framework applying the node selection algorithms to achieve the energy efficiency. Simulation results show that EGOR achieves better energy efficiency than geographic routing and blind opportunistic protocols in all the cases while maintaining a very good routing performance. Our simulation results also show that the number of forwarding candidates necessary to achieve maximum energy efficiency is mainly affected by the reception to transmission energy ratio but not by the node density under a uniform node distribution. Although the EPA can be maximized by involving the greatest number of nodes in GOR, in terms of energy efficiency, only a very small number of forwarding candidates (around two) are needed on average. This is true even when the energy consumption of reception is far less than that of transmission.
• Chapter 4. Taking into consideration wireless interference and the unique properties of OR, we proposed a new method of constructing transmission conflict graphs and presented a methodology for computing the end-to-end throughput bounds (capacity) of OR, giving forwarding strategies. We formulate the maximum end-to-end throughput problem of OR as a maximum-flow linear programming subject to the transmission conflict constraints and effective forwarding rate constraints on each link in different concurrent transmission sets. We also proposed two metrics for OR under multirate scenarios. One is expected medium time (EMT) and the other is expected advancement rate (EAR). Based on these metrics, we proposed the distributed and local rate and candidate selection schemes: LMTOR and MGOR, respectively. We validated the analysis results by simulation, and compared the throughput capacity of multirate OR with single-rate ones under different settings, such as different topologies, source–destination distances, the number of forwarding candidates and node densities. We showed that OR has great potential to improve end-to-end throughput under different settings, and our proposed multirate OR schemes achieved higher throughput bound than any single-rate GOR. We observed some features of OR: 1. the gain in end-to-end capacity decreases when the number of forwarding candidates is increased. When the number of forwarding candidates is larger than 3, the throughput almost remains unchanged; 2. there exists a node density threshold, higher than which 24 mbps GOR performs better than 12 mbps GOR, and lower than which the opposite is the case. The threshold is about 5.5 and 10.9 neighbors per node at 12 mbps for line and square topologies, respectively.
• Chapter 5. We proposed a unified framework to compute the capacity of opportunistic routing between two end nodes in single/multiradio/channel multihop wireless networks by allowing dynamic forwarding strategies. Our model accurately captures the unique property of OR that multiple outgoing links sharing the same transmitter can be virtually scheduled at the same time under particular rate constraints. We also studied the necessary and sufficient conditions for the schedulability of a flow demand vector associated with a transmitter to its forwarding candidates in a concurrent transmission set. We further proposed an LP approach and a heuristic algorithm to obtain an opportunistic forwarding strategy scheduling that satisfies a flow demand vector. Our methodology can not only be used to calculate the end-to-end throughput bound of OR and TR in multiradio/channel multihop wireless networks, but can also be used to study OR behaviors (such as candidate selection and prioritization) in multiradio multichannel systems. Leveraging our analytical model, we found that OR can achieve comparable or even better performance than TR using less radio resources.
• Chapter 6. We analyzed the candidate coordination problem in opportunistic routing and, based on these analyses, we proposed a new coordination scheme “fast slotted acknowledgment” (FSA), which takes full advantage of the channel-detection approach to reach an agreement among multiple candidates. We compared FSA with state-of-the-art schemes and simulation results show that it achieves better performance in all the metrics, especially in time delay. The simulation also validated that FSA can achieve a similar level of performance as ideal coordination where relay priority can be ensured and duplicate packet forwarding is avoided.
• Chapter 7. We further investigated the transmission coordination problem in opportunistic routing and studied how the strict coordination requirement in ExOR can be greatly eased using network coding. First, we reviewed MORE, a well-known state-of-the-art MAC-independent opportunistic routing protocol. After identifying the inadequacy of MORE in dealing with multicast and broadcast, we demonstrated how network coding can be integrated with opportunistic listening in wireless broadcast. In particular, we looked into a class of challenging problem—mobile content distribution (MCD) in VANET, where large files are broadcasted proactively from a few APs to vehicles inside an interested area. To combat the lossy wireless transmissions in VANETs, we leveraged symbol-level network coding (SLNC), which exploits symbol-level diversity to achieve better error tolerance compared with traditional packet-level network coding (PLNC). We then quantitatively characterized the advantages of SLNC compared with PLNC from two aspects, namely higher throughput and spacial-reusability. Using two typical MCD applications as examples—popular content distribution and live multimedia streaming, we presented two novel push-based broadcast schemes—CodeOn and CodePlay, respectively. The common ideas underlying the two schemes included a prioritized relay selection algorithm that opportunistically maximizes the usefulness of transmitted content and a simple transmission coordination mechanism which exploits the higher spacial reusability brought by SLNC. Compared with state-of-the-art pull-based contend distribution protocols, CodeOn and CodePlay both achieve significant performance gains. Through simulation study, the gain can be partly attributed to the use of SLNC and partly attributed to the new push-based protocol design. Thanks to the use of opportunistic listening and network coding (especially SLNC) the challenging problem of designing a MCD protocol in VANETs is solved elegantly.
• Chapter 8. We studied multirate geographic opportunistic routing (MGOR) in a contention-based scenario, and examined the factors that affect its throughput, which includes multirate capability, candidate selection, prioritization, and coordination. Based on our analysis, we proposed the local metric, the Opportunistic Effective One-hop Throughput (OEOT), to characterize the tradeoff between the packet advancement and medium time cost under different data rates. We further proposed a rate and candidate selection algorithm to approach the local optimum of this metric. We also presented a multirate link quality-measurement mechanism. Simulation results show that MGOR incorporating our algorithm achieves better throughput and delay performance than the corresponding opportunistic routing and geographic routing operating at any single rate. It indicates that OEOT is a good local metric to achieve high end-to-end throughput and low delay for MGOR.
• Chapter 9. We identified attacks on opportunistic routing and proposed countermeasures. We investigated the existing link quality measurement mechanisms, and analyzed the security vulnerabilities in them. A common fact in all the existing LQM mechanisms is that a node's knowledge about the forward PRR from itself to its neighbors is informed by its neighbors. We then proposed a broadcast-based secure LQM mechanism that prevents a neighboring node from maliciously claiming a higher measurement result. Our mechanism has very low computation, storage, and communication overheads and thus can be implemented in resource-constraint sensor networks as well as mesh networks. Our SLQM mechanism can be applied easily to unicast-based and cooperative LQM with slight modifications. We further discussed attacks on existing opportunistic routing protocols and studied the resilience of opportunistic routing on packet dropping attacks.
• Chapter 10. We studied the opportunistic broadcast of event-driven warning messages (WMs) in VANETs. The multi-hop broadcast of WMs needs to satisfy multiple stringent performance requirements such as high reliability (packet-reception ratio), low end-to-end latency and low transmission overheads, which is especially challenging to achieve due to the lossy wireless environment and fast-changing topology in VANETs. Thus, we proposed a fully distributed opportunistic broadcast protocol (OppCast) for multihop dissemination of WMs in VANETs. With the aim of achieving high WM reception reliability and fast dissemination in a resource-efficient way, the concept of opportunistic routing is exploited in the link layer at each hop to enhance reception reliability and provide small hop delay. In particular, we used explicit broadcast acknowledgements (BACK) in rebroadcast contention so that the optimal relays can always be selected with a high probability. Meanwhile, at the network layer, we proposed a double-phase broadcast method, in which fast propagation is ensured by one phase and the desired reliability level is ensured by the other. Through extensive simulations we showed that, compared with state-of-the-art protocols, OppCast achieved higher WM packet reception ratio, higher dissemination rate using smaller amount of transmissions. Our results reveal the intrinsic tradeoff and intricate interplay between WM reception reliability, dissemination rate and overhead and we believe it will provide valuable guidelines to protocol design in VANETs and mobile WMNs.