17-09-2016, 02:59 PM
1455169232-confff.docx (Size: 56.11 KB / Downloads: 4)
ABSTRACT
Mobile Adhoc Network (MANET) is a system of wireless mobile nodes without any pre-installed or centralized infrastructure which is capable of performing autonomous operation. These nodes move arbitrarily causing changes in the network topology. Each of the individual nodes acts as an independent router and performs routing tasks for efficient and reliable communication. This paper is a survey on the different types of routing protocols for MANET since new challenges exist because of the lack of consistency in MANET application environments thereby making it difficult for one to choose a proper routing protocol for the given MANET application.
Keywords:
MANET, Routing protocols, Proactive, Reactive and Hybrid protocols.
1. INTRODUCTION
MANET is a self-configuring, decentralized wireless systems connected by wireless links which are deployed without need for any infrastructure. Independent nodes communicate with each other via. Radio waves. The nodes can directly communicate with each other when they are within the radio range, others have to rely on the intermediate nodes in order to route their packets in the network. Mobile nodes has only limited resources such as memory, battery, processing power [5]
The main goal of the routing protocols is to decrease the routing overhead, find the shortest and the stable route. The routing protocols are mainly used to provide a set of rules that governs how the message packets move from a source to destination in a network. Routing protocols are applied based on the circumstances [3]
CLASSIFICATION OF ROUTING PROTOCOLS:
2.1. REACTIVE PROTOCOLS:
Reactive protocols known as On Demand Routing Protocols establish routes from source to destination only when source node requests for a route to destination. There will be no periodic transmission of topological information within the network. It is based on query-reply dialog. Reactive protocols have less overhead and more latency [2].
Examples: Dynamic Source Routing (DSR), Associativity Based Routing (ABR), Lightweight Mobile Routing (LMR), Adhoc On-demand Vector Routing (AODV).
The two major processes involved in reactive protocols are Route Discovery and Route Maintenance processes.
2.1.1. ROUTE DISCOVERY:
Route Discovery is based on demand basis. Initially the source node consults if any route cache is available from source to destination else initiates the route discovery.
2.1.2. ROUTE MAINTENANCE:
Route maintenance is essential because during the transmission of packets in the network there may occur link breakage causing Route Failure. It is done using Acknowledgment mechanism.
2.2. PROACTIVE PROTOCOLS:
Proactive protocols [2] are known as Table Driven Protocol since all the information are stored in routing tables. These protocols are used to maintain up-to-date topological information from source node to every other neighboring node in the network. The routing table undergoes periodic update and maintains topology changes in the network. This is not suitable for large networks because each of the node entries have to be maintained. They have large overhead and less latency. If there is a frequent change in the network topology then the network maintenance cost will be too high. On the other hand, if there is low network activity then the topological information might go unused.
Examples: Wireless Routing Protocols (WRP), Fisheye State Routing (FSR), Destination Sequenced Distance Vector Routing (DSDV), Cluster Gateway Switch Routing Protocol (CGSR).
2.3. HYBRID PROTOCOLS:
Hybrid protocols are new generation protocols which combines the advantages of both proactive and reactive protocols to yield better solution. It makes use of the route discovery mechanism of reactive routing protocols and table maintenance of proactive routing protocols to avoid latency and overhead. These are mainly designed to increase scalability of the networks [2].
Examples: Zone Routing Protocol (ZRP), Temporally Ordered Routing Algorithm (TORA), Zone Based Hierarchical Link State (ZHLS).
3. CLASSIFICATION OF MANET ROUTING PROTOCOLS BASED ON THE METHOD OF DELIVERY OF PACKETS:
3.1. UNICAST ROUTING PROTOCOLS:
It sends information packets from a single source to single destination.
3.2. MULTICAST ROUTING PROTOCOLS:
It delivers information simultaneously to a group of destinations. The two types of multicast protocols:
• Tree based multicast protocol which maintains one path.
• Mesh based multicast protocol which uses several routes to reach the destination.
4. PROACTIVE ROUTING PROTOCOLS:
4.1. DSDV- Dynamic Destination Sequenced Distance Vector Routing Protocol (Perkins and Bhagwat , 1994):
This is a distance vector routing protocol which is designed to solve routing loop problem by tagging each routing table with a sequence number. DSDV protocol is based on Bellman-Ford algorithm with slight alterations. Each DSDV node in the network maintains a routing table containing: destination node, next hop address and number of hops along with the sequence numbers. If an update is received with high sequence number it will replace the existing route which will eliminate the chances of forming routing loops. The potency of routing information updates are either periodic or event driven. Routing table undergoes periodic updates which help in maintaining the topology [1]. Updates of the routing table are sent in two ways:
• Full dump
• Incremental
Full dump will be performed when a major change in the topology is discovered, which will add significant overhead to the network. The neighboring nodes will receive the entire routing table. Routing table updates are sent periodically as incremental dumps limited to size of 1 packet containing only new information.
4.2. WRP- Wireless Routing Protocol (Murthy and Garcia-Luna-Aceves, 1995):
Wireless routing protocol belongs to general class of path finding algorithms. These algorithms are used to eliminate the counting-to-infinity problem of distributed Bellman-Ford algorithm using the predecessor information thus detects routing loops. WRP has a complicated table structure. Each node in the network maintains four tables: A Routing table indicating the next hop node, A Distance table which indicates the number of hops between source and its destination, A Link-Cost table gives the delay associated with a particular link, Message Retransmission List (MRL) which contains one or more retransmission entries, WRP uses periodic update messages to neighbors. The nodes in the response list of update message should send acknowledgements. The nodes can decide whether to update its table or not. If there is no change from last update, the nodes should send idle hello messages to ensure connectivity. The node performs continuous check to avoid count-to-infinity problem and converges faster [9].
4.3. CGSR- Cluster Gateway Switch Routing Protocol (Chiang, Wu, Liu and Gerla):
CGSR is a cluster based hierarchical routing protocol that uses a clusterhead selection algorithm called Least Clusterhead Change (LCC) which partitions a whole network into clusters. Then for constructing a network into separate but consistent groups, cluster heads are elected. By creating several clusters it will be able to achieve distributed processing mechanism in the network. CGSR uses DSDV as its fundamental routing scheme with some modifications i.e. by using a classified cluster-head-to-gateway routing methods which helps in routing traffic from source to destination [1].
The major advantages of CGSR are that it reduces the routing table size compared to the DV protocols. Since only one entry is needed by nodes of the same cluster, the broadcast packet size of the routing table gets reduced. Some of the disadvantages of CGSR is that it is difficult to maintain the cluster of the cluster, frequent selection or change of cluster heads disturbs the routing performance, LCC algorithm introduces additional overhead and poses complexity in the maintenance of clusters.
5. REACTIVE ROUTING PROTOCOLS:
5.1. AODV- Ad Hoc On-Demand Distance Vector Routing (Charles E Perkins, Elizabeth M Royer,1999):
AODV [1] is an improvement of DSDV, but it is reactive and not proactive. It creates routes on-demand-by reducing the number of broadcasts thus eliminating the need for periodically system wide broadcasts. When a node wants to send packet from source to destination it broadcasts a Route Request (RREQ) packet. Each of the other nodes broadcasts the packet to its neighbors and the process is continued till the packet reaches the exact destination. The intermediate nodes records address of the neighbour from which the first copy of broadcast packet is received. These records are stored in the routing table to establish reverse paths. This is done so that when some additional copies of the same RREQ packet is received later then these packets will be discarded. The major features of AODV are it is capable of broadcasting route discovery mechanism, efficient bandwidth, Loop free routing.
5.2. DSR- Dynamic Source Routing (D.B.Johnson and D.A.Maltz, 1996):
DSR a reactive routing protocol is used to dynamically discover a source route across multiple hops to destination in a network [9]. Each node maintains a route cache and it gets updated when any new route is known. It has two mechanisms that work together: Route discovery and Route Maintenance.
During the route discovery mechanism, the source node will broadcast the Route Request (RREQ) packet. Each packet will contain a unique request identification. A neighboring node on receiving a packet discards it when:
• It receives a RREQ message with same request ID and destination address.
• Its own address is already listed in the route record.
Else appends its own address and broadcasts it. Then when the packet reaches the destination it returns a Route Reply (RREP) message to the source. The source will cache the route in its route cache. Route maintenance is done when a node is unable to forward a packet to the next hop. It will return a Route Error (RERR) message to the source so that the source will remove the broken link from the cache.
5.3. ABR- Associativity-Based Routing (C.K.Toh, 1996):
ABR [1] clarifies a new type of routing metric “degree of association stability” for MANET. It is source initiated on-demand routing protocol. Route is selected particularly based on the degree of association stability of mobile nodes. Selects the best route based on stability and associativity ticks. Each node occasionally generates beacon to announce the existence of the node. On receiving the beacon, the neighboring node apprises its own associativity table. The associativity tick of the receiving node is enlarged for each beacon received. Beaconing node means node is static when there is a high value of associativity tick. This tick is rest when any neighboring node moves Out of the neighbourhood of other node. Routing decisions are performed at the destination and only best route will be selected while other routes remain passive. The distinct feature of ABR is the use of associativity ticks. There are three phases
• Route discovery- The route discovery phase uses Broadcast Query messages BQ and await reply BQREPLY messages
• Route reconstruction/repair-This phase starts when one of the source ,destination or intermediate node moves the route.
• Route deletion- Route deletion is used when a source no longer requires a route.
Advantages of ABR protocol are it is free from loops, deadlock and packet duplicates. The major drawback is the short beaconing interval to reflect association degree precisely.
6. HYBRID PROTOCOLS:
6.1. ZRP- Zone Routing Protocol (Z.J.Haas and M.R.Pearlman, 1998):
ZRP [4] is a hybrid of table driven and on demand protocol. Query-reply mechanism is used for route creations. Each node in the network is associated with a zone specifying a zone radius in terms of hops. Size of a zone can affect the communication performance. Three sub-protocols: Intrazone Routing Protocol (IARP), Interzone Routing Protocol (IERP), Bordercast Resolution Protocol (BRP).
For creating different zones in the network, a node must know its neighbors.Within a zone it is table driven and in interzone it uses on demand routing. During forwarding of packets a node identifies whether the packets are coming from the neighboring node. If its yes it marks all as it’s known neighboring node. Then the destination sends reply message through reverse path and creates a route. Here route discovery is done by “Broadercast” instead of neighbour broadcast. Here the route requests are sent to broader nodes. For route accumulation ZRP uses Neighbor discovery/Maintenance (NMD), Broader Resolution Protocol (BRP) used for query control and route accumulation.
6.2. SHARP- Sharp Hybrid Adaptive Routing Protocol:
Sharp protocol adapts between reactive and proactive protocols. This protocol defines proactive zones around some of the zones. Zones acts as collectors of packets, forwards the packets efficiently to reach the destination.The number of nodes are determined by node-specific zone radius. All the nodes that lie within the zone radius become a member of that particular proactive zone. Proactive zones are created automatically if some destinations are frequently addressed within the network. If the node is not present within that particular proactive zone, inorder to establish a route the query-reply mechanism is used [4].
6.3. OPHMR- Optimized Polymorphic Hybrid Multicast Routing Protocol :
It is polymorphic because of both hybrid and adaptive empowered with different operations proactive or reactive. OPHMR’s reactive behaviour is based on the On-Demand Multicast Routing Protocol (ODMRP). Its proactive behaviour is based on Multicast Zone Routing (MZR) protocol. For added efficiency, OPHMR uses an optimizing scheme from Optimized Link State Routing protocol. It defines four different behavioural modes. Change in behaviour is to improve the metrics like maximizing battery life, reducing communication delays. This protocol addresses issues like power efficiency, latency and overhead [4].
7. CONCLUSION:
In this paper we have discussed about the three MANET routing protocols, classification by giving a few examples of each. When there is a change in the topology all the paths are altered substantially. Hence routing is very essential in MANET. The major use of routing protocols is to provide more efficient and secure routing. Choosing the apt protocol is difficult, so based on the circumstances a particular protocol can be chosen. But is seen that rather than sticking to strictly proactive or reactive protocols, we can go for hybrid protocols which combines the advantages of both. Therefore, there is scope in future for developing more efficient and secure routing protocols.