ISSN ONLINE(2320-9801) PRINT (2320-9798)

All submissions of the EM system will be redirected to Online Manuscript Submission System. Authors are requested to submit articles directly to Online Manuscript Submission System of respective journal.

A Study on Routing Protocols for Mobile Adhoc Networks

R.Logambal1 and Dr.K.Chitra2
  1. Research Scholar, Dept of Computer Science, Bharathiar University, Coimbatore, India
  2. Asst. Professor, Govt Arts College, Melur, Madurai Dt, India
Related article at Pubmed, Scholar Google

Visit for more related articles at International Journal of Innovative Research in Computer and Communication Engineering

Abstract

The mobile adhoc network is highly dynamic and the nodes are mobile. It is a challenge to develop routing protocol that can meet different application needs and optimize routing paths according to the topology change in mobile adhoc networks. Basing their forwarding decisions only on the local topology, geographic routing protocols have drawn a lot of attentions in recent years. Providing reliable broadcasting is a challenging task. This paper analyses about various routing protocols available for routing packets between mobile nodes in Mobile Adhoc Network.



Keywords

Mobile Adhoc Network, Topology, Routing Protocol

INTRODUCTION

Today’s Internet is very fast and effective. Currently many network researchers are working on networks based on modern communication techniques, particularly wireless communications. Without the constraints of wired connections, wireless networks allow their hosts to roam. Mobile users can move around but still they are staying connected to the network. Notebook computer connectivity, Handheld personal computer connectivity, vehicle and ship networks are applications of this kind of network. We can deploy a wireless network quickly and easily. Such networks play vital role in both military and civilian systems [1].
A Mobile Ad Hoc Network (MANET) is a set of nodes which can communicate with each other using multihop wireless links. A node can directly communicate with only those nodes which are in its communication range [2]. The intermediate nodes which are in between the source node and the destination node forward messages to the nodes that are more than one hop distance from the source. Since the nodes are mobile, this network topology is ever changing. Hence in Mobile Ad hoc networks, the development of effective routing protocols that provide high quality communication is an important challenge. This paper discusses about the various routing protocols available for routing packets between mobile nodes in Mobile Adhoc Network.
The remaining sections are organized as follows. Section 2 presents summarizes the limitations of MANET routing protocols, section 3 analyzes and briefly discusses about the MANET routing protocols for their efficiency and performance. Section 4 summarizes the paper.

LIMITATIONS OF MANET

The nodes in MANET have limited communication resources such as buffer space, bandwidth, battery power etc. These resource constraints in MANET require the traffic to be properly distributed among the mobile host. A routing protocol in MANET should fairly distribute the routing tasks among the mobile hosts. Hosts and routers in a wireless network can move around. Therefore, the network topology can be dynamic and unpredictable. Traditional routing protocols used for wired networks cannot be directly applied to most wireless networks because some common assumptions are not valid in this kind of dynamic network [3]. For example, one assumption is that a node can receive any broadcast message sent by others in the same subnet. However, this may not be true for nodes in a wireless mobile network. The bandwidth in this kind of network is usually limited. Thus, this network model introduces great challenges for routing protocols. MANET applications usually have bandwidth and, often, power constraints. Therefore, overhead is an important issue for routing protocols in MANETs.
A. Applications of MANETs
Mobile AdHoc Network can be applied to the following areas:
• Virtual classrooms
• Military communications
• Emergency search and rescue-operation
• Data acquisition in hostile environments
• Communication set-up in exhibitions, conferences, presentations, meetings, lectures, etc.

ANALYSIS ON MANET ROUTING PROTOCOLS

We have analyzed nine well known routing protocols for MANET. Before discussing the routing protocols’ performance analysis and results, in this section we briefly mention the operational methods and major features of these protocols.
A. Open Shortest Path First (OSPF)
Open Shortest Path First (OSPF) [4] is a link state routing protocol. It is a mature proactive routing protocol widely used in today’s wired networks. An identical topology database is maintained in all routers so that each node can build its own local routing tables. Since the routing tables are built based on shortest path tree, a route identified by OSPF is acyclic and always the shortest path. It maintains routes to all possible destinations continuously. Hence, it is favourable for networks where many number of hosts in one subnet always communicate with hosts in other subnets. It is a complex routing algorithm. OSPF is the overhead for control packets which are needed to maintain the link state database.
Two major operations in OSPF are
1. Determining adjacency
2. Synchronizing the link state database
Five types of route control packets are used to support the above said two operations:
(i) Hello packets
(ii) Database description packets
(iii) Link state request packets
(iv) Link state update packets
(v) Link state acknowledgement packets
B. Dynamic Destination-Sequenced Distance-Vector Routing Protocol (DSDV)
Based on Bellman-Ford routing algorithm, DSDV is developed. It is a proactive routing protocol. Each mobile node keeps a routing table which contains the list of all available destinations and the number of hops to each destination. Routing table entry is labelled with a sequence number originated by the destination node.
Any update in the routing table is periodically transmitted and any new significant change is transmitted immediately (periodic or event-driven). It helps to maintain the topology information of the network. Each mobile node in DSDV advertises its own routing table to its neighbours. This advertisement is either broadcasted or multicasted [5]. By doing this, the neighbouring nodes know about the changes happened in the network due to the movements of nodes.
Any updates in the routing table can be sent in two ways:
1. Full dump
2. Incremental
In full dump update method, the whole routing table is sent to the neighbours. In incremental update, only the entries that require changes are sent. When there is no movement of nodes, full dump is transmitted less frequently. The incremental update method is more appropriate when the network is stable so that extra traffic can be avoided. But, when the movements of nodes occur often, the incremental updates sizes become large and approach the Network Protocol Data Unit (NPDU). Hence, in such cases full dump method must be used. Transmitter assigns a sequence number to each route update packet. In order to update the routing information in a node, the update packet with the highest sequence number is used that means the most recent update packet. Each node will wait for some time interval to advertise to its neighbours. Hence the latest information of better route to a destination will be informed to its neighbours.
C. Temporally-Ordered Routing Algorithm (TORA)
Temporally-Ordered Routing Algorithm is an adaptive routing protocol used in multihop networks [6]. It combines reactive and proactive routing. It is a distributed algorithm. Hence the routers need to maintain knowledge about their neighbours only. On a predestination basis, TORA maintains states. Source node initiates route requests in a reactive mode and simultaneously selected destinations can start proactive operations to construct routing tables. Normally, routes to these destinations may be frequently or consistently required such routes are routes to servers or gateways. TORA adapts to network topology changes as it supports multiple path routing. Since multiple paths are used in TORA, routes may not be the shortest ones always.
TORA uses the routing metric height associated with particular destinations. Routers with higher heights forward packet to neighbours with lower heights just like water flows in the pipes. As an independent copy of TORA runs for each possible destination, routers may have different heights and links can have different directions.
TORA allocates directions to links ‘upstream’ or ‘downstream’. A link is an upstream link when neighbouring router is “lower” and downstream link for the “higher” neighbouring router.
When compared with DSR, TORA is a complex algorithm. It has four operations:
(i) Routes Creation
(ii) Routes Maintenance
(iii) Routes Removal
(iv) Routes Optimization
Route creation operation selects proper heights for routers and forms a directed sequence of links which leads to the destination in a previously undirected network. Route maintenance procedure responds to network topology changes. Route removal sets the routers’ heights = NULL and makes the links undirected. Routes optimization procedure adjusts the heights of routers to improve routing performance. There are 4 packets used to perform the above said operations: Update (UPD), Query (QRY), Clear (CLR) and Optimize (OPT).
While maintaining routes, if a partition of the network is identified, the router with no downstream links executes the procedures to remove routes. The node broadcasts CLR packet with the related destination and relevant parameters. Once the removal procedure to erase routes is executed, routers heights and link directions are reset.
D. Dynamic Source Routing (DSR)
Dynamic Source Routing is a reactive routing protocol that allows the nodes in MANET to dynamically identify a source route through multiple network hops to any destination. The mobile nodes keep the known routes in the route caches. Whenever a new route is known, it must be updated in the cache.
In DSR, routing is done in two stages: route discovery and maintenance. When a node needs to send packets to any destination, it searches its route cache to identify whether already known route to the destination available or not. If there is such an entry to the particular destination, the source node uses that route to send the packet [7]. Otherwise it broadcasts a route request. It includes the source address, destination address and unique identification number. Each intermediate node checks whether it knows the destination or not. If the intermediate node does not know about the destination, it forwards the packet. Eventually this route request packet reaches the destination. Any intermediate node processes the route request packet only if its address does not exist in the route record of the packet and it has not previously processed the packet. When any node knows the route to reach the destination, a route reply packet is created and sent to the source node. Sometimes it may be sent by the destination itself or by of the intermediate nodes.
E. Ad Hoc On-Demand Distance Vector Routing (AODV)
Ad Hoc On-Demand Distance Vector Routing [6] is basically an enhancement of Dynamic Destination- Sequenced Distance-Vector (DSDV) routing protocol. But, it is a reactive routing protocol rather than being proactive. It creates routes based on the demand hence it minimizes the number of broadcasts which is not the case in DSDV. When a source node wants to send packet to any destination, it broadcasts a route request (RREQ) packet [1]. In turn the neighbouring nodes broadcast the packet to their neighbour nodes and this process continues till RREQ reaches the destination. While forwarding the route request, the intermediate nodes record the address of the neighbour from which it receives the first copy of RREQ. This information is stored in their route tables to establish a reverse path. If same copies of RREQ are received later, those packets are discarded. The reply is sent using the reverse path. For maintaining routes, when a source node moves, it reinitiates route discovery process. If any intermediate node moves within a particular route, the neighbour of the floated node detects the link failure and it sends this failure notification to its upstream neighbour. It continues till the failure notification reaches the source node. The source node may decide to reinitiate the route discovery phase based on the received information.
F. Optimized Link State Routing Protocol (OLSR)
Optimized Link State Routing protocol is a proactive link state routing protocol used in MANET. Comparing with pure flooding mechanisms, OLSR, using Multi Point Relays (MPR), reduces control overhead by reducing the number of broadcasts [3]. During the flooding process, MPR uses only selected routers to forward broadcast messages. Every router declares only a small subset of all of its neighbors in order to reduce the size of broadcast messages. OLSR is particularly suitable for huge and dense networks [3].
In route discovery procedures, Multi Point Relays act as intermediate routers. Hence, the path identified by OLSR may not be the shortest path. This is a major disadvantage of OLSR.
It has three functions:
1. Packet forwarding
2. Neighbor sensing
3. Topology discovery
G. Topology Broadcast Based on Reverse-Path Forwarding (TBRPF)
The Topology Broadcast Based on Reverse-Path Forwarding (TBRPF) protocol is a link state, proactive routing protocol used in MANETs [4]. Each router in this protocol constructs a source tree to all possible destinations using partial topology information which is locally stored. It is the shortest path tree. In TBRPF the routers only broadcast part of their source tree to their neighbours to reduce overhead. The partial source tree is called the reportable tree. In the local copy of network topology, if a link is in the shortest path tree, this link cost is equal to the actual value. Otherwise, the cost is greater than or equal to the real value. TBRPF is said to work better in dense networks [7].
The reportable tree at a router is generated as follows:
Links that are in this router’s shortest path tree are checked
If the link is in the neighbors’ shortest path trees, it is added to the reportable tree
There are two modules in TBRPF:
1. The neighbor discovery (TND) module
2. The topology discovery and route computation module
TND uses differential HELLO messages which report only status changes in the neighbours [48]. It reduces the size of HELLO packets. The HELLO packet contains three lists of router IDs in three different formats:
1. Neighbour Request
2. Neighbour Reply
3. Neighbour Lost
Reportable trees are built in all routers. When these are broadcast, link information is propagated to all routers in this network. If a router spots a link failure or detects a new link, it notifies its neighbours and its source tree is affected by the changed new link. TBRPF may guarantee that correct shortest path trees in all routers are built using redundant estimations.
H. Landmark Routing Protocol (LANMAR)
LANMAR is a proactive protocol for large-scale ad hoc networks. It uses the idea of logical subnets where the members have common interest and are likely to move as a group [5]. In LANMAR, a router is elected as the landmark in a subnet. It must have the knowledge of all the members in its group. This notion of LANMAR looks similar to the designated router in broadcast network used in the OSPF protocol. Each router has to maintain distance vector to landmarks in every subnet. In LANMAR, landmarks are elected based on the weight of routers such as the degree in one subnet. If a tie occurs, the router with the lowest ID is selected.
LANMAR relies on a proactive routing protocol within each subnet. This protocol provides scoped routing i.e. maximum number of hops in each subnet. It works with LANMAR and produces information about other routers in the scoped area during the selection of a landmark.
I. Fisheye State Routing Protocol (FSR)
The Fisheye State Routing protocol [6] is used as the underlying protocol for LANMAR. It uses various update frequencies based on the distance to that destination. A router uses the underlying protocol to periodically update the routing information for destinations within the same subnet. For the routers lying outside the scoped area, landmarks update the routing information with a non-zero frequency. Other routers use the route toward the landmark of their subnet as the default route to a remote host or group if they do not have a direct connection to the remote destination. Routes between subnets are not optimal because the landmark in one subnet is not guaranteed to be in the shortest path from one router in this subnet to a destination outside of this subnet.
J. Zone Routing Protocol (ZRP)
The Zone Routing Protocol is a prototype routing protocol. It is created using two sub-protocols,
1. Intrazone Routing Protocol (IARP)
2. Interzone Routing Protocol (IERP)
Intrazone Routing Protocol is a limited scope proactive routing protocol used to improve the performance of globally existing reactive routing protocols [7]. It relies on neighbour discovery protocol (NDP) for neighbour information. IARP uses the Time-To-Live (TTL) field in IP packets to control the zone range. When a packet passes through a router, TTL is decremented by 1 and then it is rebroadcast. When TTL equals to ‘0’, the packet is not rebroadcast.
Interzone Routing Protocol is the reactive routing protocol of ZRP [5]. It does the job of detecting a global path. ZRP has the advantages of both proactive and reactive routing protocols. But it lacks in route optimization.
K. Mobile IP
Mobile IP let its hosts and routers to roam seamlessly among IP subnetworks without any addressing constraints. In this routing protocol there are two agents
1. Home Agent (HA)
2. Foreign Agent (FA)
When a mobile node is away from its home network, Home Agent keeps information about the current location of the mobile node and delivers packets through tunnelling. When a mobile node enters a new network, it has to register with a Foreign Agent through which it gets services. The tunnelled packets from a HA will be detunnelled by a Foreign Agent and forwards it to the mobile node. But to apply Mobile IP to MANET requires additional features and investigation.

CONCLUSION

We have analysed various routing protocols that are applicable for Mobile Adhoc Networks. Among these protocols some are reactive protocols and some are proactive protocols and some are combination of proactive and reactive namely hybrid protocols. These routing protocols have different criteria for route selection and to optimize the use of MANET resources and to improve MANET performance. With the selection of appropriate routing protocol, Mobile Adhoc Network can maximize packet delivery ratio, mobile nodes lifetime, throughput and minimize traffic congestion and load unbalance. Hence the end-to-end packet delivery delay can be minimized and network energy consumption can be balanced.

Figures at a glance

Figure 1
Figure 1
 

References


  1. Jun Zhao Sun and J. Sauvola, “On Fundamental Concept of Mobility for Mobile Communications”, Proc. Of 13th IEEE InternationalSymposium on Personal, Indoor and Mobile Radio Communication, Lisbon, Portugal, vol. 2, pp. 799-803, 2002.

  2. C. Siva Ram Murthy and B.S. Manoj, “Ad Hoc Wireless Networks Architecture and Protocols”, Pearson Education, 2005.

  3. C. E. Perkins, P. Bhagwat, “Highly Dynamic Destination Sequenced Distance Vector Routing for Mobile Computers”, Proc. Of ComputerCommunication Rev. (1994), vol. 1, pp. 234-244.

  4. S. Murthy, J. J. Garcia-Luna-Aceves, “An Efficient Routing Protocol for Wireless Networks”, ACM/Baltzer Mobile Networks andApplications (1996), vol. 1, no. 2, pp. 183-197.

  5. G. Pei, M. Gerla, T-W. Chen, “Fisheye State Routing: a routing scheme for Ad Hoc Wireless Networks”, IEEE International Conferenceon Communications (2000), vol. 1, pp. 70-74.

  6. S. Basagni, I. Chlamtac, V. R. Syrotivk, B. A. Woodward, “A Distace Routing Effect Algorithm for Mobility (DREAM)”, Proc. of fourthannual ACM/IEEE International Conference on Mobile Computing and Networking Mobicom’98, Dallas, Tx. (1998), pp. 76-84.