1. Classification of Routing Protocols

1. Classification of Routing Protocols
A number of routing protocols have been proposed for MANETs. These protocols can be classified into three different groups: global, or proactive; on demand, or reactive; and hybrid.
In proactive routing protocols, the routes to all the destinations (or parts of the network) are determined at the start-up and maintained by using a periodic route update process.
In reactive protocols, routes are determined when they are required by the source using a route discovery process.
Hybrid routing protocols combine the basic properties of two classes of protocols into one. That is, they are both reactive and proactive in nature. Each group has a number of different routing strategies, which employ a flat or a hierarchical routing structure.
Classification methods are required to help researchers and designers to study, compare and analyze mobile ad hoc routing protocols. These characteristics mainly are related to the information exploited for routing, when this information is acquired, and the roles that nodes may take in the routing process.

A. Proactive, Reactive, and Hybrid Routing
One of the most popular methods to distinguish mobile ad hoc net work routing protocols is based on how routing information is acquired and maintained by mobile nodes. Using this method, mobile ad hoc network routing protocols can be divided into proactive routing, reactive routing, and hybrid routing.

In a proactive routing protocol, nodes in the network calculate routes to all reachable nodes a priori and try to maintain consistent, up-to-date routing information. A proactive routing protocol is also called a “table-driven” protocol. Therefore, a source node can get a routing path immediately if it needs one. In proactive routing protocols, all nodes have to maintain the information about the network topology. For any change that occurs in the network topology, the updates must be propagated throughout the network to communicate the change. Most proactive routing protocols proposed for mobile ad hoc networks have inherited most of the properties from algorithms used in wired networks. To adapt to the dynamic features of mobile ad hoc networks, necessary modifications have been made on traditional wired network routing protocols.
The major overhead of proactive routing algorithms is whether the request is there or not; regardless, up-to-date network topology is maintained. In the next section, we introduce several typical proactive mobile ad hoc network routing protocols, such as the wireless routing protocol (WRP), the DSDV protocol, and the fisheye state routing (FSR) protocol.

Reactive routing protocols for mobile ad hoc networks are also called “on-demand” routing protocols. In a reactive routing protocol, routing paths are searched only when necessary. A route discovery operation invokes a route-determination procedure. The discovery procedure terminates when either a route has been found or no route is available after examination for all route permutations. In reactive routing protocols, less control overhead will be there as the routes will not be calculated a priori. Reactive protocols have better scalability than proactive routing protocols as the route calculation is done when the request is made. In a mobile ad hoc network, active routes may be disconnected due to node mobility. Therefore, route maintenance is an important operation of reactive routing protocols. However, when using reactive routing protocols, source nodes may suffer from long delays for route searching before they can forward data packets. The Dynamic source routing (DSR) and ad hoc on-demand distance vector routing (AODV) are examples for reactive routing protocols for mobile ad hoc networks.

In hybrid routing protocols, the merits of both proactive and reactive routing protocols are combined. In hybrid routing protocols for mobile ad hoc networks, proactive routing approaches are exploited in hierarchical network architectures and reactive routing approaches are exploited in different hierarchical levels. In this chapter, the zone routing protocol (ZRP), zone-based hierarchical link-state (ZHLS) routing protocol, and hybrid ad hoc routing protocol (HARP) will be introduced and analyzed as examples of hybrid routing protocols for mobile ad hoc networks.

B. Structuring and Delegating the Routing Task

Another classification method is based on the roles that nodes may have in a routing scheme. In a uniform routing protocol, all mobile nodes have the same role, importance, and functionality. Examples of uniform routing protocols include WRP, DSR, AODV, and DSDV. Uniform routing protocols normally assume a flat network structure.
In a nonuniform routing protocol for mobile ad hoc networks, some nodes carry out distinct management and/or routing functions. Normally, distributed algorithms are exploited to select these special nodes. In these routing protocols, routing approaches are related to hierarchical network structures to facilitate node organization and management. These protocols can be further divided based on the way the organization of the nodes is done and management and routing functions are performed. Following these criteria, nonuniform routing protocols for mobile ad hoc networks are divided into zone-based hierarchical routing, cluster-based hierarchical routing, and corenode-based routing.
In zone-based routing protocols, different zone constructing algorithms are exploited for node organization (e.g., some zone constructing algorithms use geographical information). Dividing the network into zones effectively reduces the overhead for routing information maintenance. Mobile nodes in the same zone know how to reach each other with smaller cost compared to maintaining routing information for all nodes in the whole network. In some zone-based routing protocols, specific nodes act as gateway nodes and carry out interzone communication. The ZRP and ZHLS are zone-based hierarchical routing protocols for mobile ad hoc networks.
A cluster-based routing protocol uses specific clustering algorithms for cluster head election. Mobile nodes are grouped into clusters and cluster heads take the responsibility for membership management and routing functions. CGSR will be introduced in a future section as an example of cluster-based mobile ad hoc network routing protocols. Some cluster-based mobile ad hoc network routing protocols potentially support a multilevel cluster structure, such as hierarchical state routing (HSR).
In core-node-based routing protocols, critical nodes are selected dynamically and carry out special functions, such as routing path construction and control or data packet propagation. Core-extraction distributed ad hoc routing (CEDAR) is a typical core-node-based mobile ad hoc network routing protocol.

C. Exploiting Network Metrics for Routing
Most of the routing protocols in MANET’s use “hop number” as a metric for classifying the routing protocols. This means that if multiple routes are available for the same path, then the path with lowest hop number will be considered. If all wireless links in the network have the same failure probability, short routing paths are more stable than the long ones and can obviously decrease traffic overhead and reduce packet collisions. Different mobile applications have different QOS requirements for different characteristics like packet routing and forwarding. QOS routing protocols can use metrics that are used in wired networks, such as bandwidth, delay, delay jitter, packet loss rate, etc. As an example, bandwidth and link stability are used in CEDAR as metrics for routing path construction.

D. Evaluating Topology, Destination, and Location for Routing
In a topology-based routing protocol for mobile ad hoc networks, nodes collect network topology information for making routing decisions. Other than topology-based routing protocols, there are some destination-based routing protocols proposed in mobile ad hoc networks. In a destination-based routing protocol, a node only needs to know the next hop along the routing path when forwarding a packet to the destination. For example, DSR is a topology-based routing protocol. AODV and DSDV are destination-based routing protocols.
The availability of global positioning system (GPS) or similar locating systems allows mobile nodes to access geographical information easily. In location-based routing protocols, the distance between a packet forwarding node and the destination, along with the node mobility, can be used in both route discovery and packet forwarding.
Existing location-based routing approaches for mobile ad hoc networks can be divided into two schemes. In the first case, the nodes send packets to the destination based on the corresponding node’s location information and they will not use any extra information. In the second case, the protocols use both location information and topology information. Location aided routing (LAR) and the distance routing effect algorithm for mobility (DREAM) are typical location-based routing protocols proposed for mobile ad hoc networks.