A Survey on Routing Protocols in Mobile Ad Hoc Networks (MANETs)

A Survey on Routing Protocols in Mobile Ad Hoc Networks (MANETs)

E. Nagarajan BE., V. G. Sridevi M.Tech.,

Dept. of Electronics and Communication, Dept. of Electronics and communication, PET Engineering College, PET Engineering College,

Vallioor, India. Vallioor, India.

AbstractMobile Ad hoc network is a wireless communication networkconsistinga number of mobile nodes. The mobile node communicates with each other without centralized control or existing infrastructure. Mobile nodes that are not within the direct transmission require intermediate nodes to transfer the data. Therefore, routing in mobile ad hoc network is a difficult one due to dynamic environment. This paper provides a survey of several routing protocols such as Optimized link state routing (OLSR), Dynamic source routing (DSR), Ad hoc on demand distance vector routing (AODV), Destination sequenced distance- vector routing (DSDV) and Proactive source routing protocol (PSR). This paper gives characteristics, functionality, benefits and limitations of these baseline routing protocols. The performance of these baseline protocols are analyzed by using various network parameters.

Keywords—MANET, Routing protocols, OLSR, DSR, DSDV, AODV, PSR.

1. Routing

2. Quality of service

3. Security

4. Power management

   1. INTRODUCTION

      Two types of wireless networks are there, one is infrastructured and another one is infrastructure less. In infrastructured wireless networks, the base stations are fixed and the node that lies within the range directly communicates with the base station. The base stations are also communicated with the nearest base station. A typical application of infrastructured wireless network is wireless local area networks (WLANs). In infrastructure less wireless networks, there is no fixed base station. It is also called as Ad hoc networks. Due to no stationary infrastructure, all the nodes in the network act as a router and create its own dynamic network. These types of networks are mainly used in military applications, disaster relief applications, interactive lectures, conferences etc. Mobile Ad hoc networks (MANETs) is the best example of infrastructure less networks.

      In mobile Ad hoc networks, all the nodes are free to move arbitrarily and configure themselves to create its own temporary network. Each node in the MANET acts both as a router and as a host. So the topology of the network can be reconfigured anytime. Some of the challenges in MANETs are,

      Fig.1: Mobile Ad hoc network

      In MANET, finding a path between two hosts is called as Routing. Routing is a network layer function. In order to standardize the routing procedure, several routing protocols are designed for MANETs. Designing of routing protocols must satisfy the following criteria,

      1. Fully distributed routing

      2. Stable topology

      3. Loop free routing

      4. Adaptive routing

      The following section explains several routing protocols characteristics.

   2. ROUTING PROTOCOLS

Routing protocols are used to transmit the data from source node to destination node via the number of intermediate nodes. Routing protocols in MANET depends on various factors like mobility, bandwidth, resource constraint, hidden and exposed terminal problems etc. Many routing protocols have been proposed for MANETs that can be classified into two types as (a) Proactive routing protocols, (b) Reactive routing protocols

1. Proactive routing protocols

   It is also known as table driven routing protocol. In proactive source routing protocols each node maintains one or more routing tables containing routing information to every other node in the MANET. All the nodes in the network maintain valid routes all the time. Some examples of proactive source routing protocols are OLSR (Optimized link state routing), DSDV (Destination sequenced distance vector routing) and PSR (Proactive source routing protocol).

2. Reactive routing protocols

It is also known as On Demand source routing protocol. In this protocol, routes are determined when they are required by the source node. When a transmission occurs from source to destination, it initiates the route discovery procedure. The route remains valid until the transmission competition. Examples of reactive source routing protocols are DSR (Dynamic source routing protocol) and AODV (Ad hoc on demand distance vector routing).

MANET routing protocols

Proactive or Table driven

Reactive or On demand

OLSR

DSR

DSDV

AODV

PSR

Fig.2: Classification of routing protocols

The following sub section explains OLSR, DSDV, DSR, AODV, TORA protocols functionality, benefits and limitations

1. OLSR (Optimized link state routing protocol)

   It is a proactive routing protocol. In OLSR, the routes are available all the time, whenever the node needed for routing. The protocol performs hop by hop routing, where each node uses its most recent routing information to route a packet. First, it reduces the control packet size in neighbors subset links. Second, it reduces the flooding of control traffic in the selected nodes, called multipoint relays. The protocol does not generate extra traffic except control message. It does not require a reliable transmission of control packets. For

   example, due to collision or other transmission problems, the packet loss occurs. But it does not affect the performance of OLSR. Two main functions of OLSR routing protocols are node sensing and multipoint relaying.

   1. Node sensing

      Each node searches the neighbornodes via communication links. All the links must be checked in both directions in order to validate the route. Each node periodically broadcasts its HELLO messages to each neighbor node. The HELLO message contains the information like neighbor node address and other link status. These HELLO messages will help to learn about the knowledge of neighborhood nodes. From this information, each node performs the selection of its multipoint relays.

   2. Multipoint relaying

      The multipoint relaying techniques minimizes the flooding of extra traffic in the network. It reduces the duplicate transmission in the same region. Each node in the network, select the set of nodes in its neighborhood. The set of selected neighbor nodes called as a MPR (Multipoint relay) of that node. The neighbors of any node which are not in the MPR set receive and process the packet but do not retransmit the packet. Each node constructs its own MPR selector table using the HELLO messages that are received from the other nodes. The smaller in the MPR set, the more optimal in the routing table.

   3. Benefits and Limitations of OLSR

      OLSR is an optimization of pure link state protocol.By multipoint relaying, it reduces the number of retransmissionof control packet. It provides optimal routes in terms of number of nodes, which are immediately available when needed. It is suitable for large and dense ad hoc networks. The limitation of the OLSR is the size of the routing table and topology update information is increased with the density of the network. Also it consumes more resources than other protocols.

2. DSDV (Destination sequenced distance vector)

   DSDV is a table driven proactive protocol. Thus it maintains a routing table with entries for all the nodes in the network. The changes are propagated though periodic and trigger update mechanisms. To eliminate routing loops, ech update from the node is tagged with a sequence number. The sequence number from each node is independently chosen but it must be incremented each time a periodic update is made by a node. The sequence number of normal update must be an even number, since each time a periodic update is made the node increments its sequence number by 2 and adds its update to the routing message its transmits. The node cannot change the sequence number of other nodes. If a node wants to send an update for an expired route to its neighbors. Only then it increment the sequence number of the disconnected node by 1. The nodes receiving this update will then look at the sequence number and if it is odd, will remove the corresponding entry from the routing table.

   1. Header

      DSDV header is 12 bytes long and 32 bit wide. It supports packet routing for large networks. Header contains IP address, sequence number and hop count.

   2. Routing table

      It creates an entry for every node based on IP addresses. Every entry stores the following attributes of a node: its IP address, interface address, sequence number, hop count, time for last update received and setting time. DSDV maintains to routing table: a permanent routing table and an advertising routing table. Permanent routing table used for stable routes. Advertising routing table used for unstable routes. The settling time determines the stability of the routs.

   3. Routing advertisements

      DSDV sends both periodic update messages and routing update messages. Periodic updates broadcast entire routing table. Messages sent for every periodic update interval. Periodic update modified using attributes PeriodicUpdateInterval. The triggered updates broadcast the changes since last periodic update interval. To reduce the overhead DSDV uses the route aggregation. The optimal feature enables multiple update messages to be sent out as a single update messages. The period over which routes are aggregated can be modified by RoutingAggregationime attribute.

   4. Processing updates

      The packet may contain multiple DSDV update messages. New updates may be rebroadcasts every time. However if the sequence number is valid, it has three cases,

      • Received > local: The protocol verifies the received hop count with the local value of the hop count. If they are not equal, the node updates its local entries and waits for settling time. If they are not equal, the node does not wait for settling time.

      • Received = local: If the received hop count is less than the local value, the local value is updated and the protocol is waiting for the settling time. However if the received hop count is greater than or equal to local hop count value, the message is discarded.

      • Received < local: The protocol discards this update message as it already has a most recent update from that destination.

   5. Benefits and Limitations of DSDV

      In DSDV, Routes to all destinations are readily available at every node at all times. Neighbor nodes use missing transmissions to detect the broken links in the topology. When a broken link is found, it assigned a metric value of infinity and the node that detected broken link broadcasted an updated packet, to inform other that the link is chosen. The limitation is that DSDV overhead increases as the node density increases. It further affects the network performance.

3. DSR (Dynamic source routing)

   Dynamic source routing is a reactive source routing protocol. The routes are initiated by the source node. The protocol consists of two main parts, one is route discovery and another one is route maintenance. Every node has the cache to store the recently discovered paths. When a node desires to send a packet to some other node, first it checks its entry in the cache. If it is there, it uses that path, otherwise it asking for a path by sending a route request packets to all the nodes.

   1. Route discovery

      Route discovery used to discover the routes between any hosts in the ad hoc network. A host initiating route discovery process by sending a route request packet to all the nodes that are within the transmission range of it.When any host receives route request packet. Itprocesses the request according to the following steps:

      • If the initiator address and route request ids are already in the route request record then the host discards the route request process.

      • If this hosts address is already listed in the route record, then discard the route request packet and do not process it further

      • If the destination of the request matches the host address, then route record in the packet contains the route by which the request reached this host from the initiator of the route request. Return a copy of this route in a route reply packet to the initiator.

      • Otherwise, append this hosts own address to the route record in the route request packet, and re-broadcast the request.

   2. Route maintenance

      The node will maintain the route information of the entry so as to know whether the cache is fresh or not. When a data packet is received by any intermediate node, it first checks whether the packet is meant for itself or not. If it is meant for itself (i.e. the intermediate node is the destination), the packet is received otherwise the same will be forwarded using the path attached on the data packet. Since in MANET, any link might fail any time. Therefore, route maintenance process will contentlymonitor and will also notify the nodes if there is any failure in the path. Consequently the nodes will change the entries of their route cache.

   3. Benefits and limitation of DSR

      One of the main benefit of DSR protocol is that there is no need to keep routing table so as to route a given data packet as the entire route is contained in the packet header. The limitations of DSR protocols is that this is not scalable to large networks and even requires significantly more processing resources than most other protocols. Basically, in order to obtain the route information, each node must spend a lot of time to process any control data it receives, even if it is not the intended recipient.

4. AODV (Ad hoc on demand distance vector)

   AODV is collectively based on DSDV and DSR routing protocol. It uses an on-demand approaching for finding a route. It does not maintain the route all the time.The routes are discovered when they needed and maintained as long as they required by the nodes.

   1. Route discovery

      When a node initiates the data transmission it first checks the routing table for the route to current destination is available or not. If it is there, the data packet is forwarded to the appropriate node toward the destination. If it is not there, the route discovery process is initiated by the source node. AODV initiates a route discovery process using route request (RREQ) and route reply (RREP) messages. The source node will create a RREQ packet. The RREQ transmitted to the neighbor nodes, its called as forward path setup. The route request packet contains source IP address, sequence number, destination IP address, destination last sequence number and broadcast ID. The broadcast ID is incremented each time when the source node initiates RREQ. The neighbors accept the route by sending the RREP back to the source node. Its called as reverse path setup.

   2. Setting up reverse path

      The route request packet contains two sequence numbers. One is source sequence number and another one is last destination sequence number. The source sequence number contains the latest or new information about the reverse route to the source. The destination sequence number specifies the updated reverse path information. Before sending the route reply messages, the node records the information about the source.

   3. Forward path set up

      When an intermediate node with desired route to destination receves the RREQ, it creates a RREP and sends it to the source node through where it receives the RREQ. When RREP is routed back along the reverse path and received by an intermediate node, it sets up a forward path entry to the destination in its routing table when the route reply reaches the source node, it means a route from source to the destination has been established and the source node can begin the data transmission.

   4. Path maintenance

      The source node and destination node maintains the path as long as they needed for data transmission. If a source node moves during data transmission, the source node again initiates the route discovery procedure by sending the RREQ packet to establish a new route. Conversely, if the destination node or intermediate node moves, the upstream nodes sends route error (RERR) message to the destination or intermediate nodes.. When the RERR is received by the source node, it can either stop sending the packet or reinitiate the route discovery mechanism.

   5. Benefits and limitations of AODV

   The benefits of AODV protocol are, it provides least congested route and it supports unicast and multicast data transmission in constant network. It also responds very quickly whenever the change occurs in the topology. AODV does not put any additional overheads on data packet. The limitation of AODV protocol is that the node needs to detect the broadcast of other nodes in the broadcast medium. There is a possible that a valid route is expired whenever the mobile nodes changes their data rates and moves dynamically in the network. The performance of the protocol decreases whenever the network size increaseAODV is vulnerable to various kinds of security attacks, because each node requires the cooperation of other nodes in the broadcast medium.

5. PSR (Proactive source routing protocol)

   PSR is a proactive source routing protocol. PSR uses a breadth first spanning tree (BFSR) to maintain a stable network topology. The BFSR is shared with neighbors for updated network topology. The PSR allows a node to have full path information of the entire network.

   1. Route update

      The network with undirected graph and edges are converted into spanning tree. At the beginning, the root node is only aware of the existence of itself. That means there is an only one node in the BFST. By exchanging the network information in each iteration, the network is converted into union graph. If the network contains n number of node means, n number of iteration performed to reach the destination node. This technique does not increase the overhead of the control message because one routing message is always sent per update interval.

   2. Neighborhood trimming

      The route update message double as hello message is transmitted to neighbor nodes. If a neighbour is deemed lost or out of communication range means, the network trigger the process of neighbourhood trimming. That means the contribution of node in the network should be removed. The neighborhood trimming process triggered for following cases,

      • No routing update or data packet has been received from this neighbor for a given period of time

      • The data transmission to node has failed, as reported by the link layer.

   3. Streamlined differential update

      Streamlined differential update reduces the routing overhead. It uses two techniques, first one is a compact tree representation and second technique is a stable BFST.

      1. Compact tree representation: The full BFST information stored at each node is converted into a short packet. To do that, the spanning tree is converted into the binary tree. As such as, the size of the message is half compared to traditional approach.

      2. Stable BFST: To maintain a stable BFST, only a small portion of the tree needs to be change, whenever changes are detected in the network.

   4. Benefits and limitations of PSR

One of the benefits of PSR is that the overhead is very small compared to other baseline routing protocols. The strong source routing with the reduced overhead increases the performance of the network. PSR also supports traditional IP forwarding. The limitations of the PSR are, the data rate decreases with the increasing of density of the network. When network grows, it consumes more resources than other baseline protocol.

1. PERFORMANCE ANALYSIS

   The number of network parameters is used to compare the performance of MANET routing protocols. The performance can be analysed by following qualitative metrics

   1. Overhead

      This metric describes how many routing packets or topology information for route discovery and route maintenance need to be sent so as to propagate the data packets.

   2. End to end delay

      End to end delay refers to the time taken for a packet to be transmitted across a network from source node to destination node.

   3. Throughput

      This metric represents the total number of bits forwarded to higher layers per second. It is measured in bps. It can also be defined as the total amount of data a receiver actually receives from sender divided by the time taken by the receiver to obtain the last packet.

   4. Packet delivery ratio

      The ratio between the amount of incoming data packets and actually received data packets.

      The performanceof various MANET routing protocols (OLSR, DSDV, DSR, AODV and PSR) are listed on the basis of above mentioned performance metrics. The results have been taken for maximum of 20 nodes in the network. It has been observed that the performance of all protocols studied was almost stable in sparse medium with low traffic. OLSR performs better in packet delivery owing to selection of better routes using acyclic graph. It also provides the excellent throughput when increasing the density of the network. The end to end delay is similar to all the baseline protocols. The overhead of the proactive routing protocols is small when compared to the reactive protocols. AODV is still better in Route updating and maintenance process. PSR overtakes all protocol in terms of overhead reduction. It also yields similar or better data transportation performance than these baseline protocols.

2. CONCLUSION

In this research paper, an effort has been made to concentrate on the comparative study and performance analysis of various routing protocols. It has been concluded that due to the dynamically changing topology and infrastructure less, decentralized characteristics, source routing with proactive table driven scheme is difficult to achieve in mobile ad hoc networks. Hence, proactive source routing mechanisms should be designed in order to control the overhead in the network. The focus of the study is on these issues in the future research work and effort will be made to propose a solution for reducing overhead size in Ad Hoc networks by tackling these techniques of source routing with table driven scheme.

Table 1: Performance analysis

REFERENCES

1. Ashwani Kush, Phalguni Gupta, Ram Kumar, Performance Comparison of Wireless Routing Protocols, Journal of the CSI, Vol. 35 No.2, April-June 2005

2. Anne Aaron JieWeng, Performance Comparison of Ad- hocRouting Protocols for Networks with Node Energy Constraints, available at http://ivms.stanford.edu

3. Charles Perkins, Elizabeth Royer, Samir Das, Mahesh Marina, Performance of two on-demand Routing Protocols for Ad-hoc Networks, IEEE Personal Communications, February 2001, pp.16-28.

4. C. Perkins, E. B. Royer, S. Das, Ad hoc On-Demand Distance Vector (AODV) Routing – Internet Draft, RFC 3561, IETF Network Working Group, July 2003.

5. C. E. Perkins and E. M. Royer, Ad-Hoc On Demand Distance Vector Routing, Proceedings of the 2nd IEEE Workshop on Mobile Computing Systems and Applications (WMCSA), New Orleans, LA, 1999, pp. 90-100.

6. C. E. Perkins and P. Bhagwat, Highly dynamic destination- sequenced distance vector routing (DSDV) for mobile computers, Proceedings of ACM SIGCOMM 94, 1994, pp. 34 244.

7. D. Bertsekas and R. Gallager, Data Networks Prentice Hall Publ., New Jersey, 2002.

8. D. B. Johnson, D. A. Maltz, Y.C. Hu, The Dynamic Source Routing Protocol for Mobile Ad Hoc Networks (DSR), IETF Draft, April 2003, work in progress.http://www.ietf.org/internet- drafts/draft-ietf-manet-dsr-09.txt

9. D. B. Johnson and D. A. Maltz, "Dynamic Source Routing in Ad Hoc Networks", Mobile Computing, T. Imielinski and H. Korth, Eds., Kulwer Publ., 1996, pp. 152-81.

10. David A. Maltz, On-Demand Routing in Multi-hop Wireless Mobile Ad Hoc Networks, May 2001, available at www.monarch.cs.rice.edu.

11. E.M.Rover, C.K.Toh, A review of current routing protocols for ad hoc networks, IEEE Communications, vol 6, 1999, pp 46- 55.

12. F. Bertocchi, P. Bergamo, G. Mazzin, Performance Comparison of Routing Protocols for Ad hoc Networks, IEEE GLOBECOM 2003.

13. Farhat Anwar, Md. Saiful Azad, Md. ArafaturRahman, Mohammad MosheeUddin, Performance Analysis of Ad hoc Routing Protocols in Mobile WiMAX Environment, IAENG International Journal of Computer Science, 35:3, IJCS_35_3_13

14. H. Ehsan and Z. A. Uzmi (2004), Performance Comparison of Ad HocWireless Network Routing Protocols, IEEE 8th International Multitopic Conference, Proceedingsof INMIC, December 2004, pp.457 465.

15. IskraDjonovaPopova, A PowerPoint presentation on Routing in Ad-hoc Networks, 9th CEENet Workshop on Network Technology, Budapest 2004.

16. J. Broch, D.A. Maltz, D. B. Johnson, Y-C. Hu, J. Jetcheva, A performance comparison of Multi-hop wireless ad- hocnetworking routing protocols, in the proceedings of the 4th International Conference on Mobile Computing and Networking (ACM MOBICOM 98), October 1998, pages 85-97.

17. Md. GolamKaosar, Hafiz M. Asif, Tarek R. Sheltami, Ashraf S. Hasan Mahmoud, Simulation-Based Comparative Study of On Demand Routing Protocols for MANET, available at http://www.lancs.ac.uk

18. Per Johansson, Tony Larsson, NicklasHedman, BartoszMielczarek, Routing protocols for mobile ad- hoc networks a comparative performance analysis, in the proceedings of the 5th International Conference on Mobile Computing and Networking (ACM MOBICOM 99), August 1999, pages 195-206.