1.4.1 Opportunistic Techniques
Cooperative Communication
While opportunistic routing aims to harvest the diversity gain at the packet level, cooperative communication studies the diversity gain at the signal level. The idea of user cooperation diversity is usually attributed to Sendonaris, Erkip, and Aazhang in Sendonaris et al. (1998) but can also be traced back to the relay channel model first introduced in Meulen (1971). The relay channel generalizes the notion of a simple point-to-point channel with a single source and destination to include a relay whose sole purpose is to help transfer information from the source to the destination.
Cover and Gamal (1979) and Cover and Thomas (1991) are credited with developing most of the information theory results on relay channels. They analyzed the capacity of the relay channel under the assumption that all nodes operate in the same band. Under this assumption, the system can be decomposed into a broadcast channel from the viewpoint of the source and a multiple access channel from the viewpoint of the destination. The idea of user cooperation diversity first attracted the attention of the information theory after the paper by communit Sendonaris et al. (1998) was presented at the 1998 International Symposium on Information Theory. Many of the ideas and results that appeared in the literature shortly after Sendonaris et al. (1998) can be traced to Cover and Gamal (1979).
Sendonaris, Erkip, and Aazhang followed up on Sendonaris et al. (1998) with a more detailed information theory study of two-source transmission cooperation in a mobile uplink scenario in (Sendonaris et al. 2003a,b). This work was important in that it also exposed several practical implementation issues in cooperative transmission systems and attracted the interest of the communications and signal-processing communities. Also noteworthy are the contributions of Laneman and Wornell (2002); Laneman (2002); and Laneman et al. (2004) for studying the performance of several practical cooperative transmission protocols in fading environments. Yet another important set of contributions came in the form of novel information theory results and new insights into information theory coding in Kramer et al. (2005). New information theory results and results on power control were also presented in Host-Madsen and Zhang (2005); Wang et al. (2005a). A variety of contributions to relaying including new bounds, cut-set theorems, power control strategies, LDPC relay code designs and some of the earliest results on half-duplex relaying were proposed in Khojastepour (2004). Researchers realized that relaying can mimic multiple-antenna systems even when the communicating entities were incapable of supporting multiple antennas. Prominent literature on the use of space-time codes with relays includes Laneman and Wornell (2002); Mitran et al. (2005); Nabar et al. (2004). Other interesting contributions are Boyer et al. (2004); Hasna and Alouini (2003); Liang and Veeravalli (2005); Toumpis and Goldsmith (2003).
The research in cooperative communication mainly focuses on the theoretical capacity under strict assumptions about user synchronization at the signal level. It is difficult to implement the proposed cooperative communication schemes in the real system. Opportunistic routing realizes the gains of cooperative diversity at the packet level, so it can be implemented in the standard radio hardware such as IEEE 802.11 devices.
Opportunistic Scheduling
Opportunistic scheduling aims to improve network utilization by taking advantage of the wireless channel fading across users and time. Knopp and Humblet (1995) showed that by scheduling transmission to the network user experiencing the best channel condition at the moment in cellular networks, significant system level gains can be realized. Thus fading essentially gives an opportunity for the network to ride on the peak channel condition at all times. However, opportunistic scheduling has its own costs and limitations (Liu et al. n.d.). In all the opportunistic scheduling schemes, signaling costs are unavoidable, because scheduling decisions inherently depend on channel conditions (and/or queuing status). Users need to estimate their channel conditions constantly and report to the base station. Hence, the actual scheduling gain should take into account the signaling costs. Furthermore, the timescale of channel fading plays an important role in opportunistic scheduling. The fluctuation of channels should be slow enough for user to estimate it and exploit it. On the other hand, the fluctuation should be fast enough, so that users do not experience extreme long delays.
In short, opportunistic routing is different from opportunistic scheduling in the following aspects. First, they target different problems. Opportunistic routing tries to improve packet forwarding reliability in multihop wireless networks by taking advantage of the spacial (user) diversity and the broadcast nature of the wireless medium whereas opportunistic scheduling aims to improve the system resource utilization by exploiting the channel fluctuations due to fading. Second, they are used in different networks. Opportunistic routing is used in multihop wireless networks whereas opportunistic scheduling is mainly used in single-hop cellular networks. Third, they are implemented at different layers. Opportunistic routing is a cross-layer design that is implemented at the network and MAC layers. In Chapter 7, we will see by integrating network coding, the opportunistic routing can be just implemented at network layer. While opportunistic scheduling is usually implemented at MAC layer with physical layer channel-state information.
AP Collaborations
Protocols like MRD (Miu et al. 2005), SOFT (Woo et al. 2007) and Link-Alike (Jakubczak et al. 2009) all exploit different aspects of the same concept: multiple receiver diversity in WLANs. Consider, for example, a sender that has poor connectivity to multiple nearby APs. A transmitted packet is unlikely to reach any specified AP; any bit in the packet is likely to be received by at least one AP. All the above protocols exploit this receiver diversity by allowing APs to combine received bits or packets over the wired network and hence can increase uplink reliability without any retransmissions.
However, none of these schemes can similarly address a lossy downlink without expending medium time on retransmissions. SourceSync (Rahul et al. 2010) complements all these protocols by harnessing sender diversity to increase downlink reliability without any retransmissions, analogous to existing receiver diversity mechanisms on the uplink. Specifically, instead of requiring that a client receive packets from only one AP at a time, in SourceSync, multiple neighboring APs can transmit simultaneously to the client, and increase throughput.
In this category of research, the main focus is on how to improve the last-hop uplink or downlink transmission reliability, while routing is not a major concern. In opportunistic routing, the forwarding candidate selection and prioritization are not only dependent on the local one-hop instant link quality but also affected by the cost/distance from the candidates to the destination. Therefore, in comparison with AP collaborations, opportunistic routing faces more challenges.
1.4.2 Network Coding
Candidate coordination is a challenging problem introduced by opportunistic routing. If the forwarding candidates are not well coordinated, multiple nodes may hear a packet and forward the same packet unnecessarily, which in turn degrades the network throughput. Fortunately, network coding can effectively alleviate this problem. Next we introduce the basic concepts of network coding, and then explain why it can be used to improve the routing performance in MWNs.
Network coding disposes of the traditional end-to-end packet forwarding paradigm, and enables intermediate nodes to mix the received packets and has the potential to increase network throughput. Intuitively, by combining received packets, a coded packet sent by an intermediate node could benefit multiple receivers simultaneously, thus improving the bandwidth efficiency. In the seminal paper by Ahlswede et al. (2000) it was shown that, for a butterfly network topology, the multicast capacity can be achieved by performing network coding at the routers. Later, Li et al. (2003) showed that linear codes are enough to achieve the maximum multicast capacity bounds under the same network topology, while Ho et al. (2006) extended their results to random linear codes. For unicast traffic, Li and Li (2004) showed that network coding results in higher throughput than pure forwarding for specific unicast topologies. The above results are for general networks; in the following, we give a brief review of how network coding can be applied to multicast/broadcast/unicast sessions with emphasis on multihop wireless networks and its advantages and limitations in both theory and practice.
From the theoretical viewpoint, Lun et al. (2008) proved that random linear network coding can be used to construct a capacity-approaching scheme for multicast over lossy wireless networks. Adjih et al. (2007) showed that by using a simple broadcast rate selection strategy, network coding can ensure that every transmission has a high probability of being useful. Fragouli et al. (2008) studied network coding-based efficient broadcast from both theoretical and practical points of view. They showed that network coding is able to increase the bandwidth/energy efficiency by a constant factor in fixed networks. They also proposed a probabilistic forwarding-based algorithm for random networks, which shows a significant reduction in the total transmission count compared with probabilistic flooding.
To bridge the gap between theory and practice, Chachulski et al. (2007) proposed MORE, which is the first practical network coding-based opportunistic routing protocol that achieves high throughput for both unicast and multicast sessions. The main motivation of MORE is to solve the candidate coordination challenge of opportunistic routing (Biswas and Morris 2005). Its idea is to combine opportunistic routing with network coding. By randomly mixing packets before forwarding them, MORE ensures that the routers hearing the same transmission do not forward the same packet. In this way, MORE eliminates the need of complicated coordination mechanism between multiple forwarders in pure opportunistic routing. However, MORE is inefficient when applied to multicast or broadcast, since almost every node in the network may become a forwarding node, which can cause heavy congestion (Koutsonikolas et al. 2009). Moreover, in mobile MWNs, traditional tree-based multicast schemes fall short in that they incur large overhead in maintenance of the tree structure as the topology changes very fast.
Recently, a special type of network coding, symbol-level network coding (SLNC) (Katti et al. 2008) is proposed. Taking a step further beyond the usual packet-level network coding (PLNC) method which processes information in the unit of packets, SLNC enables a node to combine information in the smaller granularity of “symbol”, which may consist of several physical layer symbols. The immediate advantages brought by SLNC are enhanced error and interference tolerance, whereas the benefits of network coding are automatically inherited. In addition, SLNC also possesses the potential to enhance spacial reuse by encouraging concurrent transmissions, and it has been shown to be able to significantly improve the throughput of unicast in wireless mesh networks compared with PLNC (Katti et al. 2008). However, how and how much SLNC can improve the bandwidth efficiency in mobile WMNs is still not well understood.
In this book (Chapter 7), we exploit network coding and opportunistic listening in designing high-performance broadcast protocols in mobile MWNs, especially vehicular ad hoc network (VANET). In order to resolve the challenges posed by lossy links and fast-changing topology, SLNC is combined with a novel push-based broadcast method where the relay nodes (forwarders) are selected in a dynamic, opportunistic, and fully distributed manner, in contrast with the traditional tree-based multicast method in fixed MWNs. The coordination among relay nodes can be greatly simplified through the use of network coding. The gains of using SLNC and the opportunistic relay selection method are characterized, which again demonstrates the importance of being opportunistic (in the mobile setting).
1.4.3 Opportunistic Forwarding in Opportunistic Networks
Opportunistic networks are an important class of Delay/Disruption Tolerant Networks (DTNs) in which contacts (time-windows when data can be exchanged) appear opportunistically without any prior information (Wang et al. 2005b). In opportunistic networks, source and destination nodes might never be fully connected at the same time. That is, there is no guarantee on the existence of a complete path between two nodes wishing to communicate. Examples of such networks are sparse mobile ad hoc networks, such as ZebraNet (Juang et al. 2002). Packet forwarding or routing in such networks is the most compelling issue. Nodes are not always connected to each other, so the forwarding algorithms in such networks follow a store-carry-forward paradigm. Typical algorithms differ based on their decisions as to who forwards the data, at what time the data is forwarded, and to whom the data is sent.
In general, the packet forwarding algorithms can be classified into three categories: flooding, simple replication, and history based.
In flooding algorithms, each node forwards any nonduplicated messages to any other node that it encounters. A representative protocol in this category is the epidemic routing protocol (Vahdat and Becker 2000), where messages diffuse in the network similarly to diseases or viruses, i.e., by means of pair wise contacts between individuals/nodes. The dissemination process is bounded because each message when generated is assigned a hop-count limit giving the maximum number of hops that the message is allowed to traverse before reaching the destination. The flooding algorithm delivers messages with the minimum delay but consumes a lot of bandwidth and node storage.
For simple replication algorithms, identical copies of the message are sent over the first k contacts. Only the source of the message sends multiple copies. The relay nodes are allowed to send only to the destination; they cannot forward it to another relay. This leads to small overhead as the message flooding is controlled to take place only near the source. This class of forwarding algorithms is also known as the two-hop relay algorithm (Chaintreau et al. 2005; Grossglauser and Tse 2002b). There is a natural tradeoff between overhead and data-delivery latency. A higher k leads to more storage/transmissions but has lower delays.
A history-based algorithm estimates the probability of delivery using the historical data forwarding record. Each node keeps track of the probability that a given node will deliver its messages. k highest ranked relays (based on delivery probability) are selected as forwarding nodes (Juang et al. 2002).
We should differentiate between the opportunistic forwarding in opportunistic networks and the opportunistic routing we study in this book. The former considers the node encounter probability as the opportunity, and store, carry, and forward the packet in a not completely connected network. It still abstracts each wireless link as a wired link, and does not consider exploiting spacial diversity to improve per-hop transmission reliability. The latter considers the broadcast nature of wireless medium as an opportunity and exploits the spacial node diversity in each transmission to improve the per-hop transmission reliability.
1.4.4 Geographic Routing
Owing to its scalability, statelessness, and low maintenance overhead, geographical routing is considered as an efficient paradigm for data forwarding in multi-hop wireless ad hoc and sensor networks. Early work (Finn 1987; Karp and Kung 2000; Kuhn et al. 2003) on geographic routing exploited the concept of maximum advancement towards the destination to route packets in a greedy manner. However, recent empirical measurements (Couto et al. 2003; Zhao and Govindan 2003) have proved that the unit disk connectivity model, on which these solutions are based, often fails in real settings. More recent works on geographic routing are focused on lossy channel situations. Seada et al. (2004) articulated the distance–hop energy tradeoff for geographic routing. They concluded that packet advancement times packet reception ratio, the EPA, is an optimal metric for making localized geographic routing decisions in lossy wireless networks with ARQ (Automatic Repeat reQuest) mechanisms, and is also a good metric for Non-ARQ scenarios. Zorzi and Armaroli (2003) also independently proposed the same link metric. Lee et al. (2005) presented a more general framework called normalized advance (NADV) to normalize various types of link cost such as transmission times, delay and power consumption. Unfortunately, NADV only applies to geographic routing which involves a single forwarding candidate and cannot be directly used for geographic opportunistic routing.
1.4.5 Multirate Routing
Multirate wireless networks have started attracting research attention recently. Draves et al. (2004) proposed using the weighted cumulative expected transmission time (WCETT) as a routing metric. Awerbuch et al. (2006) adopted the medium time metric (MTM). Zhai and Fang (2006b) studied the impact of multirate on carrier sensing range and spacial reuse ratio and demonstrated that the bandwidth distance product and the end-to-end transmission delay (the same as the medium time) are better routing metrics than the hop count. Zhai and Fang (2006a) also proposed the metric of interference clique transmission time to achieve a high path throughput. However, these metrics or protocols were proposed for routing on a fixed path following the concept of the traditional routing. In this book, we propose a framework to compute the end-to-end throughput bound of OR for different OR schemes in multiradio, multichannel and multirate networks. The throughput bound derived in this book is the upper bound of the achievable throughput of the proposed and investigated OR schemes. We also study the impact of the protocol overhead and multirate capability on the performance of GOR under contention-based medium access protocols.
1.4.6 Energy-Aware Routing
Energy-aware routing has received significant attention over the past few years (Chang and Tassiulas 2000; Kar et al. 2003; Li et al. 2001; Singh et al. 1998). Singh et al. (1998) proposed five energy aware metrics such as maximizing time to partition and minimizing maximum node cost. These are important metrics for energy efficient routing. However, it is difficult to directly implement them in a local algorithm when even the global version of the same problem is NP-complete. Chang and Tassiulas (2000) proposed a class of flow-augmentation algorithms and a flow-redirection algorithm, which balances the energy consumption rates among the nodes in proportion to the energy reserves. The limitation of this approach is that it requires prior knowledge of the information generation rates at the origin nodes. Li et al. (2001) proposed an “online” power-aware routing and a zone-based routing, which maximizes the network lifetime without knowing the message generation rate. Following Li et al. (2001), another “online” routing algorithm was proposed in Kar et al. (2003), which aims to maximize the total number of successfully delivered messages. In this book, we study the energy efficiency of OR to tradeoff the routing performance and energy efficiency in terms of maximizing the bit advancement per unit energy consumption.
1.4.7 Capacity of MWNs
Theoretical work on the capacity of MWNs mainly focuses on two aspects. One is the asymptotic bounds of the network capacity (Grossglauser and Tse 2002a; Gupta and Kumar 2000). These works study the capacity trend with regard to the size of a wireless network under specific assumptions or scenarios. The other aspect of work on wireless network capacity is the computation of the exact performance bounds for a given network. Jain et al. (2003) proposed a framework to calculate the throughput bounds of traditional routing between a pair of nodes by adding wireless interference constraints into the maximum flow formulations. Zhai and Fang (2006a) studied the path capacity of traditional routing in a multirate scenario. Our work falls into this direction. However, distinct from the previous works, we propose a method to compute the end-to-end throughput bounds of opportunistic routing, which is different from the traditional routing in that we construct the transmitter (associated with multiple forwarding candidates) based conflict graph instead of a link conflict graph to capture the local broadcast nature of OR. Our framework can be used as a tool to calculate the end-to-end throughput bound of different OR variants, and is an important theoretical foundation for the performance study of OR. There has been recent work (Alicherry et al. 2005; Kodialam and Nandagopal 2005; Zhang et al. 2005) on capacity bound computation in multiradio multichannel networks. However, they are all based on the assumption that traditional routing is used at the network layer, where one transmitter can only deliver traffic to one receiver.
1.4.8 Link-Quality Measurement
The existing LQM mechanisms proposed in the literature (Couto et al. 2003; Kim and Shin 2006; Sang et al. 2007) can be generally classified into three types: active, passive and cooperative (Kim and Shin 2006). For broadcast-based active probing (Couto et al. 2003), each node periodically broadcasts Hello/probing packets and its neighbors record the number of received packets to calculate the packet reception ratios (PRRs) from the node to themselves. In passive probing (Kim and Shin 2006), the real traffic generated in the network is used as probing packets without introducing extra overheads. For cooperative probing (Kim and Shin 2006), a node overhears the transmissions of its neighbor to estimate the link quality from the neighbor to itself. However, for any of the existing LQM mechanisms, the inherent common fact is that a node's knowledge about the forward PRR from itself to its neighbor is informed by the neighbor. Since MWNs are generally deployed in an ad hoc style or in untrusted environments, nodes may be compromised and act maliciously. This receiver-dependent measurement opens up a door for malicious attackers to report a false measurement result and disturb the routing decision for all the PRR-based protocols.