27 Routing Protocols in Mobile Ad hoc Networks (MANETs)

Suchit Purohit

epgp books

 

Classification of Routing Protocols

 

An ad hoc routing protocol is a convention, or standard, that controls how nodes decide which way to route packets between computing devices in a mobile ad hoc network. In ad hoc networks, nodes do not start out familiar with the topology of their networks; instead, they have to discover it. The basic idea is that a new node may announce its presence and should listen for announcements broadcast by its neighbors. Each node learns about nodes nearby and how to reach them, and may announce that it, too, can reach them.

 

One of the most popular methods to distinguish mobile ad hoc network 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, as discussed above, into proactive routing, reactive routing, and hybrid routing.

 

Optimized Link State Routing (OLSR) Protocol

 

OLSR is a table-driven, proactive routing protocol and is based on traditional link state routing algorithm. The typical operation of it is that each node locally monitors the network situation, and periodically floods its local view over the network. By combining all received local views, each node can get a complete picture of the network, and calculate shortest paths to all destinations based on it. The main advantage of link state routing is that it converges faster to correct routing information. However, it is not more robust than distance vector routing (things can go quite wrong when routing updates get lost), and is not necessarily more scalable, because, even though routing update messages are smaller, they need to be flooded over the whole network, and nodes need to locally build a complete picture of the whole network.

 

Each node selects a set of its neighbor nodes as “multipoint relays” (MPR). In OLSR, only nodes, selected as such MPRs, are responsible for forwarding control traffic, intended for diffusion into the entire network. MPRs provide an efficient mechanism for flooding control traffic by reducing the number of transmissions required. Nodes, selected as MPRs, also have a special responsibility when declaring link state information in the network. Indeed, the only requirement for OLSR to provide shortest path routes to all destinations is that MPR nodes declare link state information for their MPR selectors. Additional available link state information may be utilized, for example for redundancy. Nodes which have been selected as multipoint relays  by  some  neighbor node(s)  announce  this  information  periodically  in  their  control messages. Thereby, a node announces to the network that it has reachability to the nodes which have selected it as an MPR.

 

As a proactive protocol, OLSR is also suitable for scenarios where the communicating pairs change over time: no additional control traffic is generated in this situation because routes are maintained for all known destinations at all times.

 

Multipoint Relays (MPRs)

 

The idea of multipoint relays is to minimize the overhead of flooding messages in the network by reducing redundant retransmissions in the same region. Each node in the network selects a set of nodes in its symmetric one-hop neighborhood, which may retransmit its messages. This set of selected neighbor nodes is called the MPR set of that node. The neighbors of node N which are not in its MPR set receive and process broadcast messages but do not retransmit broadcast messages received from node N. Each node selects its MPR set from among its one-hop symmetric neighbors. This set is selected such that it covers all symmetric strict two-hop nodes. The MPR set of N, denoted as MPR (N), is then an arbitrary subset of the symmetric one-hop neighborhood of N which satisfies the following condition: every node in the symmetric strict two-hop neighborhood of N must have a symmetric link toward MPR (N). Each node maintains information about the set of neighbors that have selected it as an MPR. This set is called the “MPR selector set” of a node. A node obtains this information from periodic Hello messages received from the neighbors. Upon receipt of this MPR selector information, each node calculates and updates its route to each destination.

 

Protocol Functioning

 

OLSR is modularized into a “core” of functionality, which is always required, for the protocol to operate, and a set of auxiliary functions. The core specifies, in its own right, a protocol able to provide routing in a stand-alone MANET. Each auxiliary function provides additional functionality, which may be applicable in specific scenarios (e.g., in case a node is providing connectivity between the MANET and another routing domain). All auxiliary functions are compatible, to the extent where any (sub-) set of auxiliary functions may be implemented with the core. Furthermore, the protocol allows heterogeneous nodes—that is, nodes which implement different subsets of the auxiliary functions—to coexist in the network. The purpose of dividing the functioning of OLSR into core functionality and a set of auxiliary functions is to provide a simple and easy-to-comprehend protocol, and to provide a way of only adding complexity where specific additional functionality is required.

 

Core Functioning

 

The core functionality of OLSR specifies the behavior of a node, equipped with OLSR interfaces participating in the MANET and running OLSR as a routing protocol. This includes a universal specification of OLSR protocol messages and their transmission through the network, as well as link sensing, topology diffusion, and route calculation. Specifically, the core is made up from the following components.

 

Packet Format and Forwarding

 

A universal specification of the packet format and an optimized flooding mechanism serves as the transport mechanism for all OLSR control traffic.

 

Link Sensing

 

Link sensing is accomplished through periodic emission of Hello messages over the interfaces through which connectivity is checked. A separate Hello message is generated for each interface. Resulting from link sensing is a local link set describing links between “local interfaces” and “remote interfaces,” that is, interfaces on neighbor nodes. If sufficient information is provided by the link layer, this may be utilized to populate the local link set instead of a Hello message exchange.

 

Neighbor Detection

 

Given a network with only single interface nodes, a node may deduct the neighbour set directly from the information exchanged as part of link sensing. In a network with multiple interface nodes, additional information is required to map interface addresses to main addresses (and, thereby, to nodes). This additional information is acquired through Multiple Interface Declaration (MID) messages.

 

MPR Selection and MPR Signaling

 

The objective of MPR selection is for a node to select a subset of its neighbours such that a broadcast message, retransmitted by these selected neighbors, will be received by all nodes two hops away. The MPR set of a node is computed such that it, for each interface, satisfies this condition. The information required to perform this calculation is acquired through the periodic exchange of Hello messages.

 

The MPR selection Algorithm follows below mentioned two steps:

  • Goal: Select in the 1-neighborhood of u (N1(u)) a set of nodes as small as possible which covers the whole 2-neighborhood of u(N2(u))
  • Step -1: Select nodes of N1(u) which cover isolated point of N2(u)
  • Step-2: Select among the nodes of N1(u) not selected at the first step, the node which covers the highest number of points of  N2(u) and go on till every points of N2(u) are covered.

Topology Control Message Diffusion

 

Topology control (TC) messages are diffused with the purpose of providing each node in the network with sufficient link state information to allow route calculation.

 

 

TC message contains MPR selector table and the sequence number. Each node maintains a Topology Table based on TC messages which let it to calculate the Routing Table. Upon receipt of a TC message, if there is some entry to the same destination with higher Sequence Number, the TC message is ignored but if there is some entry to the same destination with lower Sequence Number, the topology entry is removed and the new one is recorded. If the entry is the same as in the TC message, then the holding time of this entry is refreshed.

 

Route Calculation

 

Given the link state information acquired through periodic message exchange, as well as the interface configuration of the nodes, the routing table for each node can be computed. A routing table contains Destination address, next hop address and Distance. It is recalculated after every change in neighborhood table or in topological table.

 

Ad hoc On demand Distance Vector (AODV) Protocol

 

AODV is an on-demand routing protocol, which initiates a route discovery process only when desired by a source node. When a source node wants to send data packets to a destination node but cannot find a route in its routing table, it broadcasts a Route Request (RREQ) message to its neighbors. Its neighbors then rebroadcast the RREQ message to their neighbors if they do not have a fresh enough route to the destination node. This process continues until the RREQ message reaches the destination node or an intermediate node that has a fresh enough route. Every node has its own sequence number and RREQ ID. Below figure depicts the fundamental Route Discovery Process of AODV.

 

 

 

AODV uses sequence numbers to guarantee that all routes are loop-free and contain the most recent routing information. RREQ ID in conjunction with source IP address uniquely identifies a particular RREQ message. The destination node or an intermediate node only accepts the first copy of a RREQ message, and drops the duplicated copies of the same RREQ message. After accepting a RREQ message, the destination or intermediate node updates its reverse route to the source node using the neighbor from which it receives the RREQ message. The reverse route will be used to send the corresponding Route Reply (RREP) message to the source node. Meanwhile, it updates the sequence number of the source node in its routing table to the maximum of the one in its routing table and the one in the RREQ message.

 

When the source or an intermediate node receives a RREP message, it updates its forward route to the destination node using the neighbor from which it receives the RREP message. It also updates the sequence number of the destination node in its routing table to the maximum of the one in its routing table and the one in the RREP message. A Route Reply Acknowledgement (RREP-ACK) message is used to acknowledge receipt of a RREP message. Though not required, AODV may utilize the HELLO message to maintain the local connectivity of a node. Route maintenance is done with Route Error (RERR) messages. If a node detects a link break in an active route, it sends out a RERR message to its upstream neighbors that use it as the next hop in the broken route. When a node receives a RERR message from its neighbor, it further forwards the RERR message to its upstream neighbors.

 

AODV is a stateless protocol; the source node or an intermediate node updates its routing table if it receives a RREP message, regardless of whether it has sent or forwarded a corresponding RREQ message before. If it cannot find the next hop in the reverse routing table, it simply drops the RREP message. Otherwise, it unicasts the RREP message to the next hop in the reverse route. In general, a node may update the sequence numbers in its routing table whenever it receives RREQ, RREP, RERR, or RREP-ACK messages from its neighbors.

 

Zone Routing Protocol (ZRP)

 

The ZRP Protocol being a hybrid protocol combines the advantages of the proactive and reactive approaches by maintaining an up-to-date topological map of a zone centered on each node. Within the zone, routes are immediately available. For destinations outside the zone, ZRP employs a route discovery procedure, which can benefit from the local routing information of the zones. Proactive routing uses excess bandwidth to maintain routing information, while reactive routing involves long route request delays. Reactive routing also inefficiently floods the entire network for route determination. ZRP aims to address the problems by combining the best properties of both approaches.

 

Architecture

 

The Zone Routing Protocol, as its name implies, is based on the concept of zones. A routing zone is defined for each node separately, and the zones of neighboring nodes overlap. The routing zone has a radius ρ expressed in h hops. The zone thus includes the nodes, whose distance from the node in question is at most h hops. An example of a routing zone is shown below, where the routing zone of S includes the nodes A–I, but not K. In the illustrations, the radius is marked as a circle around the node in question. It should, however, be noted that the zone is defined in hops, not as a physical distance. The nodes of a zone are divided into peripheral nodes and interior nodes. Peripheral nodes are nodes whose minimum distance to the central node is exactly equal to the zone radius ρ. The nodes whose minimum distance is less than ρ are interior nodes.

 

In above figure of a routing zone having radius 2, the nodes A–F are interior nodes, the nodes G– J are peripheral nodes, and the node K is outside the routing zone. Note that node H can be reached by two paths, one with a length of two hops and one with a length of three hops. The node is, however, within the zone, because the shortest path is less than or equal to the zone radius. The number of nodes in the routing zone can be regulated by adjusting the transmission power of the nodes. Lowering the power reduces the number of nodes within direct reach and vice versa. The number of neighboring nodes should be sufficient to provide adequate reachability and redundancy.

 

On the other hand, a too large coverage results in many zone members, and the update traffic becomes excessive. Further, large transmission coverage adds to the probability of local contention. ZRP refers to the locally proactive routing component as the Intrazone Routing Protocol (IARP). The globally reactive routing component is named the Interzone Routing Protocol (IERP). IERP and IARP are not specific routing protocols. Instead, IARP is a family of limited-depth, proactive, link state routing protocols. IARP maintains routing information for nodes that are within the routing zone of the node. Correspondingly, IERP is a family of reactive routing protocols that offer enhanced route discovery and route maintenance services based on local connectivity monitored by IARP.

 

The fact that the topology of the local zone of each node is known can be used to reduce traffic when global route discovery is needed. Instead of broadcasting packets, ZRP uses a concept called “bordercasting.” Bordercasting utilizes the topology information provided by IARP to direct query requests to the border of the zone. The bordercast packet delivery service  is provided by the Bordercast Resolution Protocol (BRP). BRP uses a map of an extended routing zone to construct bordercast trees for the query packets. Alternatively, it uses source routing based on the normal routing zone. By employing query control mechanisms, route requests can be directed away from areas of the network that already have been covered. To detect new neighbor nodes and link failures, ZRP relies on a Neighbor Discovery Protocol (NDP) provided by the MAC layer. NDP transmits Hello beacons at regular intervals. Upon receiving a beacon, the neighbor table is updated. Neighbors for which no beacon has been received within a specified time are removed from the table.

 

Routing

 

A node that has a packet to send first checks whether the destination is within its local zone using information provided by IARP. Reactive routing is used if the destination is outside the zone. The reactive routing process is divided into two phases: the route request phase and the route reply phase. In the route request phase, the source sends a route request packet to its peripheral nodes using BRP. If the receiver of a route request packet knows the destination, it responds by sending a route reply back to the source. Otherwise, it continues the process by border-casting the packet. The reply is sent by any node that can provide a route to the destination. To be able to send the reply back to the source node, routing information must be accumulated when the request is sent through the network. The information is recorded either in the route request packet or as next-hop addresses in the nodes along the path. In the first case, the nodes forwarding a route request packet append their address and relevant node or link metrics to the packet. When the packet reaches the destination, the sequence of addresses is reversed and copied to the route reply packet. The sequence is used to forward the reply back to the source. In the second case, the forwarding nodes record routing information as next-hop addresses, which are used when the reply is sent to the source.

 

The zone radius is an important property for the performance of ZRP. If a zone radius of one hop is used, routing is purely reactive and border-casting degenerates into flood searching. If the radius approaches infinity, routing is reactive. The selection of radius is a trade-off between the routing efficiency of proactive routing and the increasing traffic for maintaining the view of the zone.

you can view video on Routing Protocols in Mobile Ad hoc Networks (MANETs)

References

  1. Optimized Link State Routing Protocol (OLSR-RFC) by T. Clausen, Ed., P. Jacquet, Ed. Project Hipercom, INRIA. October 2003
  2. www.olsr.org/docs/wos3-olsr.pdf
  3. RFC3561 (AODV). 2003; http://www.ietf.org/rfc/rfc3561.txt
  4. Ad Hoc Networking with AODV by Charles E. Perkins;
  5. www.fdis.org/02/Perkins_AODV.ppt
  6. The Zone Routing Protocol (ZRP-RFC) for Ad Hoc Networks by  Zygmunt J. Haas & Marc Pearlman, Cornell University. http://tools.ietf.org/id/draft-ietf-manet-zone-zrp-04.txt
  7. Akshai Aggarwal, Savita Gandhi and Nirbhay Chaubey “Performance Analysis of AODV, DSDV and DSR in MANETs” Page No. 167-177 in International Journal of Distributed and Parallel Systems (IJDPS) ISSN : 0976 – 9757 [Online] ; 2229 – 3957 [Print] Vol.2, No.6, November 2011. http://airccse.org/journal/ijdps/papers/1111ijdps15.pdf
  8. Gandhi, S., Chaubey, N., Shah, P. and Sadhwani, M. 2012. Performance Evaluation of DSR, OLSR and ZRP Protocols in MANETs. In 2nd IEEE International Conference on Computer Communication and Informatics (ICCCI-2012), 10-12, January, 2012 at Sri Shakthi Institute of Engineering and Technology, Coimbatore, Tamilnadu, India; http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=6158841
  9. “AODVSEC: A Novel Approach to Secure Ad Hoc on-Demand Distance Vector (AODV) Routing Protocol from Insider Attacks in MANETs” by Akshai Aggarwal, Savita Gandhi, Nirbhay Chaubey, Pathik Shah, Madhvi Sadhwani, 2012 in International Journal of Computer Networks & Communications (IJCNC) Vol.4, No.4, July 2012, 191-210 https://arxiv.org/abs/1208.1959;