1.3 Routing Techniques in MWNs
The routing protocols in MWNs can be classified into different categories using different criteria. For example, they can be classified into link-state routing (e.g. OLSR—Jacquet et al. 2001) and distance-vector routing (e.g. AODV—Perkins and Royer 2001). They can also be categorized as proactive (e.g. DSDV—Perkins and Bhagwat 1994) and reactive (on-demand) (e.g. DSR—Johnson et al. 2001—and TORA—Park and Corson 1997) routing. For a better understanding of the difference between opportunistic routing and other state-of-the-art routing protocols in MWNs, we would like to classify the routing protocols as traditional and opportunistic routing.
1.3.1 Traditional Routing
Traditional routing protocols (Johnson et al. 2001; Perkins and Bhagwat 2001; Perkins and Royer 2001) for multihop wireless networks have followed the concept of routing in wired networks by abstracting the wireless links as wired links, and finding the shortest, least cost, or highest throughput path(s) between a source and destination. Most routing protocols rely on the consistent and stable behavior of individual links, so the intermittent behavior of wireless links can result in poor performance such as low packet delivery ratio and high control overhead. On the other hand, this abstraction ignores the unique broadcast nature and spacial diversity of the wireless medium. We introduce several well known traditional routing protocols in MWNs as follows.
AODV
The Ad hoc On Demand Distance Vector (AODV) routing protocol (Perkins and Royer 2001) is designed for routing in MANETs. It is called, on demand, because it builds routes between the source and destination nodes only when source nodes request it. It maintains and updates the route as long as it is needed by the source node. AODV uses sequence numbers to ensure the freshness of routes. It is loop-free, self-starting, and scales to large numbers of mobile nodes.
AODV establishes routes using a route request and route reply discovery cycle. When a source node requires a route to a destination for which it does not already have a route, it broadcasts a route request (RREQ) message throughout the network. The RREQ message contains the source node's IP address, current sequence number, a broadcast ID, and the most recent sequence number for the destination of which the source node is aware. Intermediate nodes that receive the RREQ update their information for the source node and set up backwards pointers to the source node in their routing tables. A node receiving the RREQ will unicast a route reply (RREP) message back to the source if it is either the destination or if it knows a route to the destination with corresponding sequence number no smaller than that contained in the RREQ. Otherwise, it rebroadcasts the RREQ. Nodes keep track of the RREQ's source IP address and broadcast ID, and discard the RREQ that they have received recently and do not forward it.
As the RREP message is relayed back to the source node along the reversing path, nodes on the path set up forward pointers to the destination. Once the source node receives the RREP, it may begin to forward data packets to the destination along the path. If the source later receives a RREP containing a greater sequence number or contains the same sequence number with a smaller hop count, it may update its routing information for that destination and begin using the new route. In this sense, AODV tries to find the shortest path with fewest hops.
The route is active and maintained as long as there are data packets routed through it. Once the source node stops sending the data packets, the links on the path will time out and eventually be deleted from the intermediate nodes' routing tables. If a link break occurs while the route is active, the upstream node of the break link propagates a route error (RERR) message to the source node to inform it of this broken link. After receiving the RERR, if the source node still desires a route, it will initiate a route discovery again.
The advantage of AODV lies in that due to its on-demand (reactive) nature, it can handle highly dynamic topology change in MANETs. However, it possesses several disadvantages. First, AODV lacks support for high throughput routing metrics. It is designed to support the shortest hop-count metric, thus favoring long and low-bandwidth links over short and high-bandwidth links. Second, it may incur long route discovery latency. AODV does not discover a route until a flow is initiated. This route-discovery latency can be high in large-scale networks. Third, it may introduce broadcast storm problems in bandwidth-limited MWNs. Each network node participates in the route discovery process by rebroadcasting RREQ messages, which leads to redundant rebroadcasts, contention and packet collision.
DSR
Dynamic Source Routing (DSR) (Johnson et al. 2001) is another well known on-demand routing protocol. It is similar to the AODV in that it forms a route on demand when a source node requests it. However, it uses source routing instead of relying on the routing table at each intermediate node.
In the route-discovery phase, like AODV, DSR uses RREQ and RREP messages. When the source node needs to send data packets to a destination and it does not know a route to it, it initiates a route discovery by broadcasting a RREQ message. The RREQ identifies the initiator (source) and target (destination) of the route discovery and contains a unique request ID. It also contains a record listing the address of each intermediate node through which this particular copy of RREQ has been forwarded. The route record is initialized to an empty list by the initiator.
When a node receives a RREQ, it checks if it is itself the target of this RREQ. If this is the case, the node returns a RREP, which contains the accumulated route record from the RREQ to the initiator. If it is not the case and it is the first time the node receives the RREQ, it appends its own address to the route record in the RREQ message and rebroadcast the RREQ. The node will drop the RREQ message if it is a duplicated one or when the node finds that its own address has already been in the route record.
When the source node receives a RREP message, it catches the route carried in the message and sends subsequent data packets to the destination along this route.
Dynamic source routing shares the same advantage as AODV: it is reactive, thus eliminating the need to flood the network periodically to update the routing table in a dynamic network. It actually does not maintain a routing table at each node but it maintains the whole path information to a destination at the source node. It is beaconless and hence does not require periodic Hello packet (beacon) transmissions, which saves bandwidth.
The disadvantage of DSR is that the route-maintenance mechanism does not repair a broken link locally. It may introduce a long connection setup delay due to its on-demand nature. Even though DSR performs well in static and low-mobility environments, the performance degrades rapidly with increasing mobility. Furthermore, a considerable routing overhead is involved due to the source-routing mechanism. This routing overhead is directly proportional to the path length. DSR also tends to find the shortest hop count path, which contains long and unreliable wireless links.
OLSR
Optimized Link State Routing (OLSR) (Jacquet et al. 2001) is a proactive link-state routing protocol, which uses Hello and Topology Control (TC) messages to discover and then disseminate link state information throughout the MWNs. Each node maintains the global topology information of the network, and computes the next hop for all the other nodes in the network using shortest hop forwarding paths.
The OLSR protocol discovers two-hop neighbor information for each node through one-hop Hello packet broadcasts. In order to minimize the topology information flooding overhead, OLSR performs a distributed election of a set of multipoint relays (MPRs). Each node selects its MPR set among its one-hop neighbors such that the set covers all the nodes that are two hops away. These MPR nodes generate and forward topology control (TC) messages that contain the MPR selectors. The TC messages are generated periodically. The neighbors that are not in the MPR set read and process the TC message but do not rebroadcast the message. The information diffused in the network by the TC messages helps each node to build its topology table and the routing table is calculated based on this. This functioning of MPRs makes OLSR different from other link state routing protocols in several ways. Only a subset of the network nodes generates link-state information and not all the links of a node are advertised—only those that represent MPR selections.
The advantage of OLSR over reactive routing protocols (such as AODV and DRS) is that it does not introduce route-discovery delay for a flow because the route is computed in a proactive way. This favors situations where route requests for new destinations are very frequent. The OLSR protocol is adapted to the network, which is dense and where communication is assumed to occur frequently between a large number of nodes.
The drawback of OLSR is that it maintains the routing table for all the destinations at each node, which may not be necessary. When the number of the nodes increases, the overhead from the control messages also increases. By only using MPRs to flood topology information, OLSR removes some of the redundancy of the flooding process, which may be a problem in networks with weak wireless links.
1.3.2 Opportunistic Routing
In a wireless network, when a packet is unicast to a specific next-hop node of the sender at the network layer, all the neighboring nodes in the effective communication range of the sender may be able to overhear the packet at the physical layer. It is possible that some of the neighbors may have received the packet correctly while the designated next-hop node did not. Based on this observation, a new routing paradigm, known as opportunistic routing (OR) (Ai et al. 2006; Biswas and Morris 2005; Bletsas et al. 2006; Fussler et al. 2003; Larsson 2001; Shah et al. 2004; Zhao and Valenti 2005; Zorzi and Rao 2003a,b) has recently been proposed. Opportunistic routing integrates the network and MAC layers. Instead of deterministically picking one node to forward a packet to, the network layer selects a set of candidate nodes to forward a packet to and at the MAC layer one node is selected dynamically as the actual forwarder based on the instantaneous wireless channel condition and node availability at the time of transmission. Opportunistic routing takes advantages of the spacial diversity and broadcast nature of wireless communications and is an efficient mechanism to combat the time-varying links. It improves the network throughput (Fussler et al. 2003; Biswas and Morris 2005; Zeng et al. 2008; 2007a,c) and energy efficiency (Zorzi and Rao 2003a; Zeng et al. 2007b) compared to traditional routing.
Some variants of opportunistic routing, such as ExOR (Biswas and Morris 2005) and opportunistic any-path forwarding (Zhong et al. 2006; Dubois-Ferriere et al. 2007; Zhong and Nelakuditi 2007), rely on the path-cost information or global knowledge of the network to select candidates and prioritize them. Another variant of OR is geographic opportunistic routing (GOR) (Fussler et al. 2003; Zorzi and Rao 2003a; Shah et al. 2004) which uses the location information of nodes to define the candidate set and relay priority. In GeRaF (Zorzi and Rao 2003a), the next-hop neighbors of the current forwarding node are divided into sets of priority regions with nodes closer to the destination having higher relay priorities. Like GeRaF, in (Shah et al. 2004), the network layer specifies a set of nodes by defining a forwarding region in space that consists of the candidate nodes. The data-link layer selects the first node available from that set to be the next hop node. (Fussler et al. 2003) discussed three suppression strategies of contention-based forwarding to avoid packet duplication in mobile ad hoc networks. We will discuss state-of-the-art opportunistic routing protocols in Chapter 6.
The performance of OR depends on several key issues. The first key issue is the selection of forwarding candidates. Although the most effective way seems to be to involve all the neighbors with smaller cost to the destination, the overhead is expected to grow with the increase of the number of forwarding candidates. In dense networks, this overhead might potentially be even higher than cost incurred due to repeated transmissions (Shah et al. 2005). The prioritization of the candidates is the second key issue that affects the performance. In general, we want to forward the packet along the “shortest” path. The lower priority forwarding candidates are essentially the backup to the node that is on the “shortest” path. However, due to the opportunistic nature of OR, the “distance” from a certain node to its multihop away destination will no longer be the same as that obtained by traditional shortest path routing. The path cost also depends on the spacial diversity opportunities along the path. How to quantify and incorporate the spacial diversity opportunities in OR has not been well understood. The third key issue is candidate coordination in the MAC layer, which ensures the multiple receivers of a packet to agree upon a next-hop forwarder in a distributed fashion (Choudhury and Vaidya 2004; Larsson 2001; Souryal and Moayeri 2005; Zhao and Valenti 2005; Zhong et al. 2005; Zorzi and Rao 2003a,b).
Although opportunistic routing has shown its effectiveness in achieving better energy efficiency (Zorzi and Rao 2003a,b) and higher throughput (Biswas and Morris 2005) than traditional routing, many important issues in OR remain unanswered or not well understood. First, none of the existing works provides a thorough understanding of how well the opportunistic routing can perform and how the selection of the forwarding candidate set will affect the routing efficiency. Questions, such as “a. how many and which neighbor nodes should be involved in the local forwarding?” and “b. What are the selection criteria and how do they affect the relay priority among the forwarding candidates?” remain unanswered. Second, there is a lack of theoretical analysis on the throughput bounds achievable by OR. Third, one of the current trends in wireless communication is to enable devices to operate using multiple transmission rates. For example, many existing wireless networking standards such as IEEE 802.11a/b/g include this multirate capability. The inherent rate–distance tradeoff of multirate transmissions has shown its impact on the throughput performance of traditional routing (Awerbuch et al. 2006; Zhai and Fang 2006a,b). Generally, low-rate communication covers a long transmission range, whereas high-rate communication must occur at short range. It is intuitive to expect that this rate–distance tradeoff will also affect the throughput of OR. Because different transmission ranges also imply different neighboring node sets, this results in different spacial diversity opportunities. The rate–distance–diversity tradeoffs in OR are not well studied. Furthermore, existing OR coordination schemes have some inherent inefficiencies such as high time delay and potential duplicate forwarding. An improperly designed coordination scheme will aggravate these problems and even overwhelm the potential gain provided by OR. It is necessary to design more efficient candidate coordination schemes. Finally, most state-of-the-art OR protocols (Biswas and Morris 2005; Zeng et al. 2007c) rely on link quality (packet reception ratio) information to select and prioritize forwarding candidates. It is important to measure the link quality accurately in order to make OR operate optimally. However, the existing link quality measurement mechanisms are subject to malicious attacks. Thus they may not be able to provide accurate link quality information for OR and other link state-based traditional routing.
This book carries out a comprehensive study on the capacity, energy efficiency, throughput, and security issues in OR and the associated multirate, candidate selection, prioritization, and coordination problems. Our goal is to understand fully the principles, the tradeoffs, the gains of the node collaboration and its associated cost to provide insightful analysis and guidance for the design of more efficient routing protocols.