A Review On MANET Routing Protocol Categories

A Review On MANET Routing Protocol Categories

Nidhi Gupta 1, Keshawanand Singh 2, Keshav Goyal 3

M.Tech Scholars, School of Computer Science & Engineering, Galgotias University, Greater Noida

Abstract

Mobile Ad hoc Network is a collection of mobile nodes that make use of transmission range for communication. When source node wishes to send the packet to a node that is not in its transmission range, it has to rely on the intermediate nodes for communication. Routing is required to forward the packets to the intermediate/destination node. Due to the frequent change in topology and other constraints like limited bandwidth, limited resources, routing in MANETs is a very challenging task. Routing mechanism must provide security and privacy. It also should take care of various qualities of service parameters. This survey presents a state of art overview of the different categories of protocols and their advantages and disadvantages in tabular form.

1. Introduction

   Mobile Ad hoc Network (MANET) represents a network which is composed of mobile nodes without having fixed infrastructure. As there is transmission range restriction, a sender has to depend on intermediate nodes to forward data packets to a destination which is not positioned in its radio range. This type of open environment is not preferable as malicious intermediate nodes might be a threat to the security in the communication of mobile nodes (with each other).

   The security problems in MANETs is greater when compared with the security of the Wired Network world as there are some basic differences exists between these two Networks. MANET has many enormous applications, e.g., battlefield operations, emergency rescues, mobile conferencing, home and community networking, and sensor dust [1].

   In Ad-Hoc network, the task of a routing protocol is to set up routes between different nodes. Routing protocols are difficult to design in an ad hoc network. The mobile nodes change the network topology very often. And there is a need to operate efficiently with limited resources, such as network bandwidth and the

   limited memory and battery power of the individual nodes in the network. Routing protocols in Ad-Hoc networks do not extent adequately because of frequent changes in network topology, lack of predefined infrastructure like routers, peer-to peer mode of transmission and limited range [2] of radio transmission. MANET routing protocols can be divided into four categories: topology-based, position-based, geocast-based and cluster-based.

   The rest of the paper is organized in order to explain different categories of routing protocols (with some examples) as shown in figure 1

2. Topology Based Routing Protocol

   These routing protocols utilize information about links existing in the network to forward the packets. These protocols can be classied into three dierent groups: global/proactive, on demand/reactive and hybrid. In

   proactive routing protocols, the routes to the entire destination 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 the above two classes of protocols into one. That is, they are both reactive and proactive in nature. Each group has a number of dierent routing strategies, which make use of a at or a hierarchical routing structure.

   2.1.1 Proactive routing Protocol: These protocols are similar to wired networks and the conventional routing schemes and follows conventional routing schemes. Each node has to maintain one or more routing tables having the information of the next node. For the entry of new node in the network, table is updated periodically. It does not work for large topology network. More overhead and more bandwidth consumption are main drawbacks of this protocol. Table driven protocols differ from their changes in topology spreads through all nodes in the networks .We describe some of the following proactive routing protocols in MANET.

   1. DSDV (Destination-Sequenced Distance Vector): This algorithm [3] is an alteration of DBF [4], which guarantees loop free routes. By using the distance vector shortest path routing algorithm, it selects a single path to a destination. Two types of update packets are used, to reduce the amount of overhead transmitted through the network. These are referred to as a full dump and incremental packets. The full dump packet carries all the available routing information and the incremental packet carries only the information changed since the last full dump. The full dump packets are sent less frequently than the incremental update messages.

   2. OLSR (Optimized Link State Routing):P. Jacquet described that due to the nature of Pro-active the routes information is available when needed. To reduce the size of control packets, MPR (Multi point relay selectors) is used to declare only a subset of links with its neighbours who are its MPR. Benefit of the MPR is large subset of nodes are communicating with each other, its leads to offer services to large and dense networks. OLSR performs the hop-by-hop routing.

      The flooding of broadcast retransmission in the same region is minimized by MPR. HELLO messages which contain information about its neighbours and their link status are disseminated to each node,

      periodically. Each node constructs its MPR Selector table with the nodes who have selected it as multipoint relay. The link state as MPR implies that link with neighbour node is bi-directional and that node is also selected as multipoint relay by this local node.

      Link state routing protocols specially designed for ad-hoc networks. To reduces the control flooding by declaring the links of neighbours within its MPRs instead of all links. Several extensions of OLSR are available that correspond to different network scenario such as faster change topology and security. Compare with DSDV Protocol control overhead is higher than link state. Qos routing mechanism is better than the reactive routing protocols. In [5] for security purpose in OLSR, digital signature added into the transmission of OLSR.

   1. Reactive Routing Protocol

      In this kind of routing protocol, every node maintains information of only active paths to the destination nodes. For achieving this purpose a route search is needed for every new destination. This reduces the communication overhead but at the cost of delay to search the route. Rapidly changing wireless network topology may break active route and cause subsequent route search [6]. Some of the following reactive routing protocols in MANET are described below.

      1. AODV (Ad-hoc on demand Distance Vector): AODV is distance vector type routing in which only the nodes on only active path are involved to maintain routes to destination. As long as end points are valid AODV does not play its part. Different route messages like Route Request RREQ), Route Replies (RREP) and Route Errors (RERR) are used to discover and maintain links. It uses UDP/IP to receive and transmit messages. AODV uses a destination sequence number for each route created by destination node for any request to the nodes. A route with maximum sequence number is selected.

         To find a new route the source node starts the route discovery message by sending RREQ to the neighbours till destination is reached or a node with fresh route is found. Then Route Reply is sent back to the source node. The nodes on active route commnicate with each other by passing hello messages periodically to its immediate neighbour. If a no reply is received then it deletes the node from its list and sends Route Error to all the members in the active members in the route. AODV does not allow unidirectional link [7].

      2. DSR (Dynamic Source Routing protocol): DSR is a pure reactive routing protocol based on the concept of source routing. DSR protocol is composed of two important phases: route discovery and route maintenance. DSR does not employ any periodic routing advertisement packets, link status sensing or neighbour detection packets [8]. Therefore, the routing packet overhead is less because of its on-demand nature.

         A route cache is maintained by every node to store recently discovered paths. Whenever a route is required for a particular destination then that particular node will check its route cache to determine whether there already exists a route to the destination or not. If active path is available then that route will be used otherwise a route discovery process is initiated by broadcasting the route request packet (RREQ). After receiving RREQ packet, the receiver node will check its route cache or from their neighbours whether it knows a route to the destination. If there is no path, the node will add its own address to the route record of the packet and forwards it to their neighbours. Otherwise; a route reply packet (RREP) is generated that is unicast back to the original source. Due to dynamic nature of the environment, any route can fail anytime. Therefore, the route maintenance process will constantly monitors the network and notify the other nodes with the help of route error packets as well as route cache would be updated [9, 10].

   2. Hybrid Routing Protocol

      Hybrid routing protocols are a new generation of protocol, which are both proactive and reactive in nature. These protocols are designed by combining the good features of reactive and proactive routing protocols, to increase scalability and to reduce the route discovery overheads. This is mostly achieved by proactively maintaining routes to nearby nodes and determining routes to far away nodes using a route discovery procedure.

      1. ZRP (Zone Routing Protocol): In ZRP [11], the nodes have a routing zone, which dene a range (in hops) that each node is required to maintain network connectivity proactively. Therefore, if the destination is within the routing zone, routes are immediately available. For the destination nodes that do not lie within routing zone routing zone, routes are determined on-demand (i.e. reactively), and any on-demand routing protocol can be utilized to determine a route to the required destination. The advantage of this protocol

         is that it has signicantly reduced the amount of communication overhead when compared to pure proactive protocols. It also has reduced the delays associated with pure reactive protocols such as DSR, by discovering the routes faster. This happens because, it only need to determine a route to a node outside the routing zone, the routing only has to travel to a node which lies on the boundaries (edge of the routing zone) of the required destination. Since the boundary node would proactively maintain routes to the destination. The disadvantage of ZRP is that for small values of routing zone the protocol can behave like a pure reactive protocol, while for large values it behaves like a proactive protocol.

      2. TORA (Temporally Ordered Routing Algorithm): The Temporally Ordered Routing Algorithm (TORA) is a highly adaptive, efficient and scalable distributed routing algorithm based on the concept of link reversal. TORA is proposed for highly dynamic mobile, multi-hop wireless networks. It is a source-initiated on-demand routing protocol. It finds multiple routes from a source node to a destination node. The main feature of TORA is that the control messages are localized to a very small set of nodes near the occurrence of a topological change. To achieve this, the nodes maintain routing information about adjacent nodes. The protocol has three basic functions: Route creation, Route maintenance and Route erasure. TORA can suffer from unbounded worst-case convergence time for very stressful scenarios. TORA has a unique feature of maintaining multiple routes to the destination so that topological changes do not require any reaction at all. The protocol reacts only when all routes to the destination are lost. In the event of network partitions the protocol is able to detect the partition and erase all invalid routes.

   Table 1:Topoplogy based protocols

   Protocol	Advantages	Disadvantages
   Proactive	All time	As Routing
   	availability of	information is
   	information &	flooded in the
   	Latency is	whole network
   	reduced.	Overhead is high
   Reactive	Path available	Latency is
   	when required,	increased in the
   	overhead is low	network
   	& free from
   	loops

   Hybrid	Suitable for	Increment in
   	large networks	complexity
   	and up to date
   	information is
   	available

3. Position Based Routing Protocol

   Position-based routing algorithms have eliminated some of the restrictions of topology-based routing by using additional information about the physical position of the participating nodes in the network. Each node makes use of GPS or some other type of positioning service to determine its own position. Position based routing mainly focuses on two issues first, a location service (to be used by the sender of a packet to determine the position of the destination and to include it in the packet's destination address) and second, a forwarding strategy needed to forward the packets.

   1. DREAM (Distance Routing Eect Algorithm for Mobility)

      The DREAM routing protocol [12] employs a dierent approach for routing as compared to the routing protocols described so far. In DREAM, each node is aware of its geographical coordinates through a GPS. Each node maintains a routing table (called a location table). Geographical coordinates of nodes are periodically exchanged between each node and stored in the location table. This protocol consumes less bandwidth because of exchanging location information consumes signicantly less bandwidth than exchanging complete link state or distance vector information. Hence, DREAM is more scalable protocol. In DREAM, routing overhead is further reduced, by making the frequency at which update messages are disseminated proportional to mobility and the distance eect. This means that only mobile nodes need to send update messages and it does not require stationary nodes 3.2 ARP (Angular Routing Protocol)

      Another scalable position-based routing protocol is Angular Routing protocol (ARP) [13]. In ARP, nodes emit a hello packet on a need-basis (non-periodic) at a rate proportional to their speeds. These hello packets enable each node to maintain a one hop neighbour table. In ARP, geographic forwarding is used to route packets to the destinaion. In case of failure of geographic forwarding, an angle-based forwarding scheme is used to circumvent voids in sparse networks. There is no need of any link-layer feedbacks like GPSR

      in ARP. If a source wishes to disseminate a packet to a particular destination, it selects as the next hop the node among its neighbours geographically closest to the destination. Each intermediate node follows this next hop selection criterion. Thus, at each hop the packet progresses towards the destination by a distance 0.9 R, where R is the radio range of the node. This is done to avoid the problem of leaving the next hop node out from the transmission range of the current node. A neighbouring node that creates a minimum angle, among available neighbours is selected, if no node is closer to the destination than the source node, or any intermediate node.

4. Geocast Based Protocol

   The goal of a geocasting protocol is to deliver a packet to a set of nodes within a specified geographical area, i.e., the geo cast region. For example, during a rescue/ emergency operation, consider the benefits of delivering a message, which states immediate help is needed at 950 Illinois Street, to all rescue personnel in the 900 block of Illinois Street. In geocasting, the nodes are eligible to receive packets that are implicitly specified by a physical region, membership in a geocast group changes whenever an MN moves in or out of the geo cast region. We require knowledge of geographical locations, as geographical areas are defined. Hence, the existence of some location information system is assumed, such as the Global Positioning System (GPS), to obtain this information.

   1. LBM (Location-Based Multicast)

      The Location-Based Multicast (LBM) protocol [14, 15] is a restricted flooding approach for geocasting. LBM is derived from a previous unicast protocol by the same authors, i.e., the Location-Aided Routing (LAR) protocol [15]. LBM is essentially identical to flooding data packets, with the modification that a node determines whether to forward a geocast packet via one of two schemes.

      1. LBM Scheme 1: When a node receives a geocast packet, it will forward the packet to its neighbours if it is within a forwarding zone; otherwise, it will discard the packet. A BOX forwarding zone is the smallest rectangle that covers both the source node and the geocast region. The authors of LBM mention that additional control on the size of the forwarding zone is possible using a parameter d > 0 [7, 8]. When d > 0, the forwarding zone is extended such that each side of the forwarding zone increases by 2d. We implement a

         BOX forwarding zone for LBM. Thus, we refer to LBM Scheme 1 as LBM-box.

      2. LBM Scheme 2: When a node A receives a geocast packet from node B, node A will forward the packet if node A is at least d closer to the centre of the geocast region than node B [14, 15].

   2. GAMER (Geocast Adaptive Mesh Environment for Routing)

   The Geocast Adaptive Mesh Environment for Routing (GAMER) protocol attempts to create redundant routes from a source to a geocast region. Due to the movement f nodes, a single route from a source to a geocast region is breakable in MANETs. Thus, the authors of GAMER

   [12] propose a mesh based geocast protocol that provides redundant paths between the source and the geocast region. A source that wants to disseminate packets to a geocast region will first flood JOIN- DEMAND packets in a forwarding zone. A JOIN- DEMAND packet is forwarded in the forwarding zone until it reaches a node in the geocast region. This node unicasts a JOIN-TABLE packet back to the source following the reverse route taken by the JOIN- DEMAND packet. After receiving its first JOIN- TABLE packet, source node can begin sending geocast packets via the mesh to the geocast region. GAMER adapts to the current network environment by dynamically changing the size of the forwarding zone, which dynamically changes the density of the mesh in real-time [16]. For highly mobile nodes, a dense mesh is created and when nodes are moving slowly, a sparse mesh is created. Three candidates CONE, CORRIDOR and FLOOD forwarding zones can be chosen by source node in GAMER. The authors of GAMER propose two versions of GAMER: passive GAMER and active GAMER. In passive GAMER, the JOIN-DEMAND packets are transmitted at a fixed frequency. In other words, a JOIN-DEMAND packet is sent at every JOIN- DEMAND packet interval regardless of whether a JOIN-TABLE packet is received. In Active GAMER, the JOIN-DEMAND packets are transmitted at the same fixed frequency and at a higher rate if a JOINTABLE packet is not returned within a given timeout period (i.e., SWITCH-TIMER).

5. Cluster based Routing Protocol

   Clustering is the process of dividing the network into interconnected substructure and the interconnected substructures are called clusters. The cluster head (CH) of each cluster act as a coordinator within the substructure. Each CH acts as a temporary base station

   within its zone or cluster. It also communicates with other CHs [17]. The Cluster based routing provides an answer to address nodes heterogeneity, and to limit the amount of routing information that propagates inside the network. The grouping of network nodes into a number of overlapping clusters is the main idea behind clustering. A hierarchical routing is possible by clustering in which paths are recorded between clusters instead of between nodes. It increases the routes lifetime, thus decreasing the amount of routing control overhead. The cluster head coordinates the cluster activities inside the cluster. The ordinary nodes in cluster have direct access only to cluster head and gateways. The nodes that can hear two or more cluster heads are called gateways [18].

   1. CLACR (Core Location-Aided Cluster- Based Routing Protocol)

      In [19] Tzay-Farn Shih and Hsu Chun Yen have proposed a cluster-based routing protocol, named Core Location-Aided Cluster-based Routing protocol (CLACR). The characteristics of CLACR are stated as the entire network is partitioned into square clusters. In each cluster, the selection of cluster head is done using a cluster head election algorithm. With the usage of the number of nodes responsible for routing and data transfer is decreased considerably. It has decreased the routing overhead and increased the route lifetime massively. Dijkstra algorithm is used for computing the path in a cluster-by-cluster basis by the CLACR.

   2. CIDR (Cluster-Based Inter-Domain Routing (CIDR) Protocol

   Cluster-based inter-domain routing (CIDR) protocol was proposed by Biao Zhou et al. [20] in 2008. The author further stated that clusters are created by the close interaction of geography, motion, or task. The advertising protocol acts as the Border Gateway protocol which provides a standard mechanism for inter-domain routing among heterogeneous domains and the principle of BGP is to enable opaque interoperations. The experiment conducted in extent literatures, showed that the planned inter-domain routing can achieve the scalability in large network, mobility robustness, and the independency of underlying intra-domain routing protocols.

6. Comparison

   The comparison among the different types of routing protocols is shown in Table 2.

   Table 2: Comparison of Protocols

   Vol. 2 Issue 6, June – 2013

   S. N	Protocol	Category	Single Path/ Multi Path	Advantage			Disadvantage
   1. DSDV		Proactive (Topology Based)	Single Path	Information is always available.			DSDV is not suitable for highly dynamic networks.
   2. OLSR		Proactive (Topology Based)	Multi Path	Low connection setup time.			Routing overhead is high.
   3.	AODV	Reactive (Topology Based)	Single Path	Routes are discovered only when demanded.			Unnecessary consumption.	bandwidth
   4. DSR		Reactive (Topology Based)	Single Path	Maintains a route cache to reduce control overhead.			Performance degrades with increasing mobility.
   5. ZRP		Hybrid (Topology Based)	Multi Path	Reduces requirement.	the	storage	Additional overhead incurred in the creation of zone level topology.
   6. TORA		Hybrid (Topology Based)	Multi Path	TORA reduces the control messages in the network			Takes huge amount of bandwidth in the network.
   7.	DREAM	Position Based	Multi Path	This kind effectively delivery.	of	forwarding guarantees	Packet loss ratio is higher than GPSR.
   8. ARP		Position Based	Multi Path	Higher packet delivery rate, low overhead			More Delay
   9. LBM		Geocast Based	Single Path	Heightens efficiency.		transfer	Packet data transmission overhead increases by Forwarding zone extension.
   10. GAMER		Geocast Based	Single Path	Intermediate nodes do not need to maintain routing state about other nodes.			Overhead that occurs for each data packet to carry the full route to the destination
   11. CLACR		Cluster Based	Single Path	Route life time increases, Collision probability reduced.			Higher overhead
   12. CIDR		Cluster Based	Single Path	Scalable, robust to mobility			Higher overhead

7. Conclusion and Future Scope

   Due to the dynamic topology, routing in MANETs is very challenging task. Researchers and authors have made big progress on ad hoc network routing, both in theory and in practical implementation but it is still difficult to determine which of them has overall better performance in MANET. In this paper an effort has been made on the comparative study of different categories of routing protocols. These categories are topology based, position based, geocast based and cluster based protocols. A comparison of different protocols under these categories has been presented in the form of table.

   Various advantages and disadvantages of these protocols are also presented in the table. There are various shortcomings in different routing protocols and it is difficult to choose routing protocol for different situations as there is trade-off between various protocols. The field of mobile ad hoc networks is very vast and there are various challenges that need to be met, so these networks are going to have widespread use in the future. For future work, simulation of some of these protocols for some quality of service parameters like throughput, delay and packet delivery ratio (PDR) can be considered.

   Vol. 2 Issue 6, June – 2013

8. References

1. C. E. Perkins, Ad hoc networking, An introduction, Charles E. Perkins, editor, Ad Hoc

   Networking, chapter 1, Addison-Wesley, 2001.

2. V. Giruka, M. Singhal, Angular Routing Protocol for Mobile Ad-hoc Networks, 25th IEEE International Conference on Distributed Computing Systems Workshops (ICDCSW05), 2005, pp. 551- 557.

3. C.E. Perkins, T.J. Watson, Highly dynamic destination sequenced distance vector routing (DSDV) for mobile computers, ACM SIGCOMM94 Conference on Communications Architectures, London, UK, 1994.

4. L.R. Ford, D.R. Fulkerson, Flows in Networks, Princeton University Press, Princeton, NJ, 1962.

[5]. T. Clausen and P. Jacquet, OptimizedLink State Routing Protocol (OLSR) RFC 3626, IETF Network Working Group, October 2003.

1. Mario Joa-Ng, A Peer-to-Peer Zone-Based Two- Level Link State Routing for Mobile Ad Hoc Networks, IEEE Journal on selected areas in communications, 17(8), Aug-1999.

2. Eitan Altman and Tamia Jimenez, NS for Beginners http://www-sop.inria.fr/maestro/personnel/Eitan.Altman/ COURS-NS/n3.pdf, Jan-2002.

[8]. C.K. Toh, Ad Hoc Mobile Wireless Networks Protocols and Systems, Pearson Education, 2007.

[9]. S. Taneja, A. Kush, A Survey of Routing Protocols in Mobile Ad hoc Networks, International Journal of Innovation, Management and Technology, 1(3), August 2010.

[10]. DSR, internet draft, http://tools.ietf.org/html/draft- ietfmanet-dsr-10.

1. Z.J. Hass, R. Pearlman, Zone routing protocol for ad-hoc networks, Internet Draft, draft-ietf-manet-zrp- 02.txt, work in progress, 1999.

2. S. Basagni, I. Chlamtac, V.R. Syrotivk, B.A. Woodward, A distance eect algorithm for mobility (DREAM), Fourth Annual ACM/IEEE International Conference on Mobile Computing and Networking (Mobicom98), Dallas, TX, 1998.

3. Y. Ko and N.H. Vaidya., Location-aided routing (LAR) in mobile ad hoc network, ACM/IEEE International Conference on Mobile Computing and Networking (MOBICOM), 1998, pages 66-75.

4. Y. Ko and N.H. Vaidya, Geocasting in mobile ad hoc networks: Location-based multicast algorithms, 2nd IEEE Workshop on Mobile Computing Systems and Applications (WMCSA), 1999, 101-110.

5. Y. Ko and N.H. Vaidya, Flooding-based geocasting protocols for mobile ad hoc networks, Journal of Mobile Networks and Applications, 7(6), 2002, 471-480.

6. T. Camp and Y. Liu, An adaptive mesh-based protocol for geocast routing, Journal of Parallel and Distributed Computing: Special Issue on Routing in Mobile and Wireless Ad Hoc Networks, 62(2), 2003, 196- 213.

7. M. Rezaee and M. Yaghmaee, Cluster based Routing Protocol for Mobile Ad Hoc Networks, INFOCOMP Journal of computer Science, 8(5), 2009, 30-36.

8. R. Agarwal and M. Motwani, Survey of clustering algorithms for MANET, International Journal on Computer Science and Engineering, 1(2), 2009, pp. 98- 104.

9. T.F. Shih and H.C. Yen, Core Location-Aided Cluster-Based Routing Protocol for Mobile Ad Hoc Networks, WSEAS ICC 06 Vouliagmeni, Athens,2006, 223-228.

10. Zhou, B., Caoan, Z., Gerla, M., Cluster-based Inter- domain Routing (CIDR) Protocol for MANETs, Sixth IEEE International Conference on Wireless On-Demand Network Systems and Services, WONS, 2009.