1.5 Book Contribution

The main contributions of this book are as follows:

• Chapter 2
  • We generalize the definition of 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 higher relay priorities to the forwarding candidates closer to the destination. This proof 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 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 find that given a set of M nodes that are available as next-hop neighbors, the candidate set achieving the maximum EPA with r (r ≤ M − 1) nodes is contained in at least one candidate set achieving the maximum EPA with r + 1 nodes.
  • We prove that the maximum EPA of selecting r(r ≤ M) nodes is a strictly increasing and concave function of r. This property indicates that although involving more forwarding candidates in GOR will increase the maximum EPA, the extra EPA gained by doing so becomes less significant.
• Chapter 3
  • We investigate the energy efficiency of GOR and propose 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 of the transmitter. The algorithms efficiently determine the optimal forwarding candidate set with respect to the EPA per unit of energy consumption.
  • We propose an energy-efficient geographic opportunistic routing (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 very good routing performance. Our simulation results also show that the number of forwarding candidates necessary to achieve the maximum energy efficiency is mainly affected by the reception to transmission energy ratio but not by the node density under a uniform node distribution. Only a very small number of forwarding candidates (around 2) is needed on average. This is true even when the energy consumption of reception is far less than that of transmission.
• Chapter 4
  • We propose a new method of constructing transmission conflict graphs, and present a methodology for computing the end-to-end throughput bounds (capacity) of OR. We formulate the maximum end-to-end throughput problem of OR as a maximum-flow linear programming problem subject to the transmission conflict constraints and effective forwarding rate on each link. To the best of our knowledge, this is the first theoretical work on capacity problem of OR for multihop and multirate wireless networks.
  • We propose two metrics for OR under multirate scenario: one is expected medium time (EMT) and the other is expected advancement rate (EAR). Based on these metrics we propose two distributed and local rate and candidate selection schemes: least medium time OR (LMTOR) and multirate GOR (MGOR), respectively.
  • We show that OR has great potential to improve the end-to-end throughput under different settings, and our proposed multirate OR schemes achieve higher throughput bound than any single-rate GOR.
  • We make some observations about OR: 1. the end-to-end capacity gained decreases when the number of forwarding candidates is increased. When the number of forwarding candidates is larger than three, 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, vice versa. The threshold is about 5.5 and 10.9 neighbors per node on 12 mbps for line and square topologies, respectively.
• Chapter 5
  • We propose a unified framework to compute the capacity of opportunistic routing between two end nodes in single/multi-radio/channel multihop wireless networks by allowing dynamic forwarding strategies.
  • We discuss the radio/channel and interference constraints when constructing concurrent transmission sets, and study the capacity region of an opportunistic module.
  • We propose an LP approach and a heuristic algorithm to obtain an opportunistic forwarding and scheduling strategy that satisfies a traffic demand vector.
  • Leveraging our analytical model, we find that OR can achieve comparable or even better performance than TR by using fewer radio resources.
• Chapter 6
  • We propose a new scheme “fast slotted acknowledgment” for candidate coordination in OR, which adopts single ACK to confirm successful reception and suppress other candidates' attempts to forward the data packet with the help of a channel-sensing technique.
  • Simulation shows that FSA can decrease the average end-to-end delay by up to 50% when the traffic is relatively light and can improve the throughput by up to 20% under heavy traffic load where other coordination schemes are already unable to delivery all the data packets.
  • The simulation results also validate that FSA can achieve performance similar to ideal coordination where relay priority can be ensured and duplicate packet forwarding is avoided.
• Chapter 7
  • We investigate the integration of network coding with opportunistic routing for easing the coordination in OR, and review MORE, a state-of-the-art MAC-layer independent OR protocol based on network coding.
  • We formulate the problem of mobile content distribution in a vehicular ad hoc network (VANET) and propose two mobile content broadcast schemes by leveraging symbol level network coding (SLNC) and combining it with opportunistic listening at the same time.
  • We propose two push-based broadcast protocols to exploit the benefits of SLNC fully, in which the content sources simply “pushes” information into the VANET actively, while a dynamic subset of temporary relay nodes from all the vehicles is determined in a fully distributed and localized way.
  • We observe that, in addition to the advantage brought by network coding in simplifying the transmission scheduling in MORE, by using symbol-level network coding, another benefit is gained for the broadcast. That is, due to the higher error and interference tolerance from symbol-level diversity, the hidden terminal problem can be alleviated, which yields the possibility of using much simpler coordination mechanism in medium access, i.e., carrier sensing. In contrast, the traditional packet-level network coding does not achieve best performance under the same coordination method due to the interference from hidden terminals.
  • Simulation shows that the proposed broadcast schemes achieve significant gains compared with state-of-the-art content distribution schemes in VANETs, where one important part of it comes from the use of SLNC and the other is attributed to the new push-based protocol design.
• Chapter 8
  • We investigate the impact of transmission rate and forwarding strategies (candidate selection, prioritization and coordination) on throughput of OR under a contention-based medium-access scenario.
  • We propose a local metric, Opportunistic Effective One-hop Throughput (OEOT), to characterize the tradeoff between the packet advancement and one-hop packet forwarding time under different data rates.
  • We propose a rate-adaptation and candidate-selection algorithm to approach the local optimum of this metric.
  • We propose a multirate link quality measurement mechanism.
  • We 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, which indicates that OEOT is a good local metric to achieve high end-to-end throughput and low delay for MGOR.
• Chapter 9
  • We discuss possible attacks on opportunistic routing protocols and propose countermeasures.
  • We analyze the security vulnerabilities in the existing LQM mechanisms and propose an efficient broadcast-based secure LQM (SLQM) mechanism, which prevents the malicious receiver from reporting a higher PRR than the actual one.
  • We analyze the security strength, the cost and applicability of the proposed mechanism.
• Chapter 10
  • We study opportunistic broadcasting in vehicular networks, where we apply the concept of opportunistic routing to the design of a broadcast protocol.
  • In particular, we propose a multi hop opportunistic broadcast scheme, a fully distributed protocol that simultaneously achieves high reliability and fast message propagation while incurring low transmission overheads.
  • We propose a distributed opportunistic broadcast coordination mechanism to let the recipients of a single broadcast determine the “best” relay nodes in a localized manner. The proposed transmission coordination mechanism exploits the idea of opportunistic forwarding to enhance the reception reliability and reduce the hop delay in each single transmission.
  • Simulation results show that the proposed scheme achieves better performance than the state-of-the-art solutions and we characterize the tradeoff between broadcast reception reliability, end-to-end delay and transmission overhead.