Preface
Advances in communication and networking technologies are rapidly making ubiquitous network connectivity a reality. Wireless networks are indispensable for supporting such access anywhere and at any time. Among various types of wireless networks, multihop wireless networks (MWNs) have been attracting increasing attention for decades due to its broad civilian and military applications. Basically, a MWN is a network of nodes connected by wireless communication links. Due to the limited transmission range of the radio, many pairs of nodes in MWNs may not be able to communicate directly, hence they need other intermediate nodes to forward packets for them. Routing in such networks is an important issue and it poses great challenges.
On the one hand, due to its open-air nature, the wireless environment presents great challenges when attempting to ensure good routing performance. The wireless channel is unreliable due to fading and interference, which makes it hard to maintain a quality path between a source and a destination. A node's mobility also incurs frequent topology changes, which bring significant overheads on maintaining and recalculating paths. Furthermore, mobile devices and sensors are usually constrained by battery capacity and communication and computation capability, which imposes limitations on the functionality of routing protocols. On the other hand, the wireless medium possesses inherent unique characteristics, which can be exploited to enhance transmission reliability and routing performance. Opportunistic routing (OR) is one promising technique that takes advantages of the spacial diversity and broadcast nature of the wireless medium to improve the packet-forwarding reliability in multihop wireless networks. It combats the unreliable wireless links by involving multiple neighboring nodes (forwarding candidates) for packet relay. This book studies the properties, energy efficiency, capacity, throughput, protocol design and security issues related to OR in multihop wireless networks.
This book is intended for networking professionals working in wireless networks and communications, who are familiar with the fundamentals of networking and wireless communications. It may also be used as a supplement to graduate courses in wireless networking, mobile computing, and wireless communications.
The contents of each chapter are described as follows.
Chapter 1 presents the case for opportunistic routing and related work. We first introduce the background of multihop wireless networks (mesh networks, sensor networks, mobile ad hoc networks, vehicular networks, etc.). Next, we discuss general wireless multihop routing, including traditional routing (AODV, DSR, etc.), geographic routing, context-based routing and opportunistic routing. We will discuss the motivation of these routing techniques, how they evolved, and their advantages and disadvantages. We will then discuss related opportunistic and collaborative techniques, including cooperative communication, opportunistic scheduling, network coding and multiple access point (AP) collaboration. We will also introduce related issues about opportunistic routing, including capacity studies of multihop wireless networks, multirate routing, energy-efficient routing, and link quality measurement, etc.
Chapter 2 of this book presents the principles and properties of the local behaviors of opportunistic routing (including geographic and link state based opportunistic routing). We will demonstrate how the performance gain changes according to the selection, prioritization, and coordination of forwarding candidates in opportunistic routing. We will discuss in what scenario or situation, opportunistic routing will work or make sense. We will also present two polynomial algorithms to compute least cost opportunistic routing paths (anypath), and introduce properties of least cost anypath.
Chapter 3 of this book studies the energy efficiency of geographic opportunistic routing (GOR). First, we motivate the energy efficiency issues of opportunistic routing in the context of sensor networks. Next, we propose a metric, Expected Packet Advancement (EPA) per unit energy consumption, in order to balance the packet advancement, reliability and energy consumption of GOR. By leveraging the proved principles in Chapter 2, we then propose two efficient algorithms that select a feasible candidate set that maximizes this local metric. We validate our analysis results by simulations and justify the effectiveness of the new metric by comparing the performance of our GOR with those of the existing geographic and opportunistic routing schemes.
Chapter 4 of this book analyzes the throughput bound and capacity of opportunistic routing given the routing strategy, i.e. the forwarding candidates of each node and the corresponding relay priority. We will first give a brief introduction on computing end-to-end throughput of traditional routing and explain why the corresponding methodology cannot directly apply to opportunistic routing, which motivates the proposed framework and methodology. The maximum end-to-end throughput problem is formulated as a maximum-flow linear programming (LP) problem subject to the constraints of forwarding candidate set conflicts. The methodology establishes a theoretical foundation for the evaluation of the performance limits of variants of opportunistic routing protocols and strategies.
Chapter 5 extends the framework proposed in Chapter 4 to deal with dynamic opportunistic routing strategies and multi-radio, multi-channel scenario. An LP approach and a heuristic algorithm is proposed to obtain an opportunistic forwarding strategy scheduling that satisfies a traffic demand vector for a hyperlink, which contains all the outgoing links from a transmitter to all its forwarding candidates.
Chapter 6 of the book investigates the state-of-the-art of the candidate coordination schemes of opportunistic routing at the medium access control layer. These schemes include GeRaF collision avoidance MAC, contention-based forwarding, ExOR batch-based MAC, slotted acknowledgment (ACK), and compressed slotted ACK. A new scheme, called “fast slotted acknowledgment (FSA)”, is described in detail. The scheme adopts a single ACK to confirm the successful reception and suppress other candidates' attempts to forward the data packet with the help of a channel-sensing technique.
Chapter 7 shows how network coding can help ease the candidate coordination in opportunistic routing. It will include an introduction on network coding, how it can help ease the candidate coordination, and on integrating opportunistic routing/broadcast with network coding. A classical work integrating opportunistic routing and network coding, MORE, will be introduced. Recent advancements on integrating symbol-level network coding and opportunistic routing in wireless broadcast are introduced.
Chapter 8 of this book studies the impacts of multirate, candidate selection, prioritization, and coordination on the throughput of GOR under a contention-based medium-access scenario. It will also introduce distributed algorithms to compute the optimal path and transmission rate in multirate opportunistic routing.
Chapter 9 of the book discusses possible attacks on opportunistic routing and countermeasures. We analyze the security vulnerabilities of the existing link quality-measurement mechanisms, and their impacts on opportunistic routing and traditional routing. We present a broadcast-based secure link quality measurement mechanism that prevents a neighboring node from maliciously claiming a higher measurement result. The secure link quality measurement helps to secure the link-state-based opportunistic routing and traditional routing.
Chapter 10 studies the opportunistic broadcast in vehicular networks. Traditional connected dominant set-based broadcast or multi-point relay-based broadcast both suffer from unreliable wireless links in the similar way as that in traditional unicast routing. The broadcast performance can also be improved by introducing the concept of opportunistic forwarding.
Chapter 11 presents the conclusion of this book and discusses some future research topics related to opportunistic routing.