A Mobile Ad Hoc Network Routing Protocols: A Comparative Study

Abstract

Mobile Ad hoc NETworks (MANET), are complex and distributed networks that are dynamic. Which are infrastructure less and multi-hop in nature. The communication of a node can be either direct or through intermediate nodes without a fixed and dedicated infrastructure. Hence it is necessary to design an efficient routing protocol for ad hoc network which can address the issues of MANET efficiently. In ad hoc, routing algorithms are classified into nine categories namely: source-initiated (reactive), table-driven (proactive), hybrid, hierarchical, multipath, multicast, location-aware, geographical-multicast and power-aware. This paper presents a survey and to review a comparative study about various routing protocols under each of these categories. Additionally, brief discussions about major routing issues are addressed. This survey paper focuses on the taxonomy related to ad hoc routing techniques and compares the features of routing protocols.

1. Introduction

A wireless network can work under two modes namely infrastructure and infrastructureless. In the “ad hoc” topology, the user does not rely on fixed infrastructure where the nodes are self-configured and self-managed. On the other hand in “infrastructure “topology, the nodes are under the control of a centralized authority called base station. Wireless multi-hop networks, also known as ad hoc networks have been used in many applications like military, disaster relief communications and emergency. An ad hoc network is a self-organizing multi-hop wireless network, which is independent neither on fixed infrastructure nor on predetermined connectivity. It is a collection of nodes, which communicate with each other using radio transmissions. In ad hoc network, there is no base station to act as router. The intermediate nodes will act as a router; source node will use these nodes for routing their message. Thus, each and every of the node forwards packets on behalf of other nodes until the packet is received by the destination from its sender. Therefore, data should be forwarded from source to destination through multiple hops. Ad hoc networks rely on multi-hop transmissions among the nodes in the same channel. Nodes communicate with each other through the intermediate nodes. So, the efficient performance and availability of each node is important in ad hoc network environment. Hence an efficient routing protocol is required to enhance the communication in MANET.

Thus routing becomes a major challenging task in MANET. In this paper, a review about the technologies, characteristics, advantages and disadvantages of the routing protocols in ad hoc network are provided.

The paper continues as follows, Section 2 summarizes the issues involved in ad hoc routing protocols. In Section 3 the routing protocols are organized as follows.

• Reactive (on-demand) (Section 3.1).

• Proactive (table-driven) (Section 3.2).

• Hybrid (Section 3.3).

• Hierarchical (Section 3.4).

• Multipath (Section 3.5).

• Multicast (Section 3.6).

• Geographical (location-aware) (Section 3.7)

• Geographical multicast (Section 3.8).

• Power-aware (Section 3.9).

Finally, Section 4 provides the conclusion for this paper.

2. Issues with ad hoc routing protocols

Due to the highly dynamic nature of mobile ad hoc network, it results in frequent and unpredictable changes in network topology and hence makes routing among the mobile nodes as a complex and difficult task. The challenges and complexities together with the importance of routing protocols make the routing process, as the most active and innovative research area in the MANET domain. The issues in routing techniques includes the large area of flooding, greedy forwarding, flat addressing and widely distributed information, large power consumption, interference and load balancing [1] (Table 1).

Issues	Protocol	Approach
Large area of flooding—flooding is a routing technique used to forward packets from the source to destination during the route discovery phase or in a recovery phase.	1. Distance routing effect algorithm for mobility (DREAM) [2]	Flooding area is reduced by limiting number of neighbors that can forward a route request message.
	2. Location aided routing (LAR) [3]	Nodes location information is used for routing the packets. Limiting the flooding area into “request zone”.
	3. Location based multicast (LBM) [4]	Similar to LAR, limiting the flooding area into “forwarding zone”
	4. Geographical distance routing (GEDIR) [5]	Greedy forwarding approach is used.
	5. Temporally-ordered routing algorithm (TORA) [6]	DAG is constructed rooted at destination and ordered routing scheme is used
	6. Geographical GRID (GeoGRID) [7]	The process of portioning the geographical area of the network into smaller areas called grids.
	7. Geographical TORA (GeoTORA) [8]	Uses any-cast any group-cast forwarding approach
	8. Zone routing protocol (ZRP) [9]	Overlapped zone are created based on the separation distance between the mobile nodes. Peripheral nodes are selected to forward the control packets within the zone.
	9. Mobile just-in-time multicasting (MOBICAST) [10]	Routing area is divided into two parts namely: a delivery zone and forwarding zone.
Greedy forwarding—greedy forwarding (GF) is one the routing technique that relies on only single path from the source to its destination which is discovered. By using GF, the major challenges encounter is defined as ‘GF empty neighbor set problem’. The forwarding process reaches a dead end, when a node cannot find any neighbor which is closer to the destination then itself.	1. FACE routing protocol [11]	Unit graph approach is utilized: two nodes communicated with each other if the Euclidean distance between them is less than some fixed amount.
	2. Geographical routing without location information (GRLI) [12]	Extended ring search: this search process continues until a node closes to destination is identified else if not found, the search is extended until a predetermined a TTL
	3. Bounded Voronoi greedy forwarding (BVGF) [13]	Greedy routing decision is based on the location of the direct neighbors of each node.
	4. Greedy distributed spanning tree routing (GDSTR) [14]	Hull tree approach is used
	5. Greedy perimeter stateless routing (GPSR) [15]	Greedy forwarding and perimeter forwarding approach are used
Flat addressing and widely-distributed information—In a MANET, due to the distribution of mobile nodes over the network and the restriction in transmission range of each node’s may cause some nodes to have poor knowledge about the network.	1. Grid location service (GLS) [16]	Based on distributed location servers (DLS) avoids the congestion in the node.
	2. Dynamic address routing (DART) [17]	Utilizes dynamic address scheme that ensures the scalability
	3. GPS ant-like routing algorithm (GPSAL) [18]	Based on ant colony optimization.; A specifically defined node namely ant node is responsible for collecting and forwarding the location information around the network.
	4. Augmented tree-based routing (ATR) [19]	Based on the structured address space.
Large power consumption—in a MANET, routing techniques depends upon the battery power of the node. Thus more power consumption will increase the overhead in the transmission.	1. Infra-structure AODV for infrastructure ad-hoc networks (ISAIAH) [20]	1. Modified forwarding approach: selecting the routes that pass through power base stations (PBSs) instead of through mobile nodes. Thus the amount of power utilized by each node can be reduced.; 2. Nodes are allowed to enter the power-saving mode for a fixed time period that will decrease the power consumed by the node.
	2. Power-aware routing optimization protocol (PARO) [21]	New forwarding node–redirectors are added on the routing path to reduce the transmission power of the intermediate nodes along the original path. The objective of PARO to increase the path length to reduce the total transmission power.
	3. Dynamic source routing power-aware (DSRPA) [22]	The routing metric battery freshness is considered in routing to achieve connectivity for the longest period of time.
	4. Power-aware multi-access protocol with signaling ad hoc networks (PAMAS) [23]	The battery usage is controlled based on the frequency of a node’s activities.
Inference and load balancing—Interference is a major problem factor that affects the performance of wireless networks. Routing in a wireless network is challenging due to the unpredictable nature of the wireless medium and due to the effect of interference on wireless link properties.	1. Source Routing for Roofnet (SrcRR) [24]	Expected transmission counts (ETX): is an interference-aware link-based routing metric that continuously measures the link loss rate in both directions between each node about its neighbors using periodic broadcasts. Link cost is estimated considering the number of retransmission attempts.
	2. Link quality source routing (LQSR) [25]	Weighted cumulative expected transmission time (WCETT).; WCETT is the sum all links costs (ETT) along the path and bottleneck channel which has the maximum sum of ETT.
	3. Load-balancing routing for mesh networks (LBRMN) [26, 27]	Metric of interference and channel-switching (MIC) and isotonic property.
	4. Interference-aware load-balancing routing (IALBR) [28]	Routing metric load value: defined as the load at node itself and its next hop node load.
	5. Load-balancing curveball routing (LBCR) [29]	Modified route metric based on greedy routing scheme.

Table 1.

Comparison of various issues in routing protocols and solutions to handle the issues.

3. Routing protocols

In this section, the categories of routing protocols are elaborated in detail manner and the overall performance of the routing protocols in ad hoc network are evaluated for each protocol under various routing categories by considering the following parameters such as route metrics, time complexity, computation complexity and route structure. One of the main features of routing protocols in ad hoc network is the routing metric, which is used to select the best route for forwarding packets. Time complexity (TC) is defined as the time required for the number of steps to perform a protocol operation, communication complexity (CC) is defined as the number of messages exchanged in performing a protocol operation and finally, route structure defines whether the structure and address scheme are flat or hierarchical. Figure 1 depicts the categories of ad hoc routing protocols.

Figure 1.

Categories of ad hoc routing protocols.

3.1 Reactive (on-demand) routing protocol

In reactive routing protocols, a node initiates a route discovery, only when it wants to send packet to its destination. They do not maintain or constantly update their route tables with the latest route topology.

Therefore, the communication overhead is reduced but the delay is increased due the on-demand route establishment process.

Dynamic source routing (DSR): DSR is a primary on-demand routing protocol proposed by Johnson et al. [30] DSR is a most widely known protocol that relays on source routing mechanism. The network bandwidth overhead is reduced by transmitting the routing message on-demand and battery power is harvested on the nodes since each of the nodes has to transmit the control packets whenever needed.

Adhocon-demand distance vector (AODV): Perkins et al. [31] proposed AODV to provide loop- free routes even under the condition of repairing the failure routes. The Time to Live (TTL), prevents the unnecessary forwarding of packets by a node hence reduces control overhead. Since, the performance depends on the bandwidth and end-end delay, so the route cache mechanism is not implemented in this protocol.

Temporally ordered routing algorithm (TORA): Park and Corson developed TORA [6] an adaptive and scalable routing algorithm. TORA is based on “link reversal” algorithm. This protocol is proposed to operate in a highly dynamic mobile wireless network environment. A directed acyclic graph (DAG) rooted at a destination is constructed by using a height as a metric.

Associativity based routing (ABR): Tohn [32] developed the ABR a simple and width efficient distributed routing algorithm. ABR exploits route stability as the criteria in selecting a best route. ABR algorithm uses a mechanism called associativity ticks to determine and maintain a “degree of associativity”. The protocol is loop-free, no deadlock condition, no duplicate of packets.

Signal stability-based adaptive routing (SSBR): SSBR, by Dube et al. [33] is a distributed adaptive routing protocol designed for ad hoc network by considering the signal strength and location stability as the routing criteria. Thus, the final path from source to destination consists of only strong link. If multiple paths are available, then the destination selects one route among them.

The ant colony based routing algorithm (ARA): Gunes et al. [34] proposed an innovative mechanism for on-demand, multi hop ad hoc routing, based on swarm intelligence and the ant colony meta heuristic. ARA is designed with a primary objective to reduce the overhead without any direct link among the participants the complex optimization and collaboration problem are solved by this type of algorithm.

Labeled distance routing (LDR): Luna-Aceves et al. [35] presented an on-demand, loop free routing protocol. LDR utilizes distance labels to ensure loop free path in the network rather than using sequence number as other routing algorithms. LDR exploits a RouteRequest, RouteReply and RouteError packet as.

Dynamic backup routes routing protocol (DBR²P): DBR²P, an on-demand routing protocol by Wang and Chao [36]. The special unique feature about DBR²P is, it does not require any routing table as other routing protocols.

AdhocQoS on-demand routing (AQOR): AQOR, an on-demand routing protocol enabling QoS support in terms of bandwidth and end-end delay is developed by Xue and Ganz [37]. AQOR mechanism estimates the bandwidth and end-end delay requirements and exploits these metrics to determine accurate admission control and resource reservation decision. TTL, prevents the unnecessary forwarding of packets by a node hence reduces control overhead.

Distributed ant routing (DAR): DAR, a distributed algorithm developed by Rosati et al. [38] DAR is based on the ant behaviour in colonies. The goal of DAR is to reduce the computation complexity. Each node maintains a routing table. Forward ants are used to find new route. A node selects the next hop node based on weighted probabilities.

Routing on-demand a cyclic multipath (ROAM): Raju and Garcia-Luna-Aceves [39] proposed ROAM, based upon the directed acyclic graphs (DAG).

Gathering based routing protocol (GRP): GRP by Ahn [40] collects network information during route discovery process. The source node uses the network information collected during route discovery process to forward the packets even if the current route is failed. The source node computes the optimal path based on the collected network information. Then, through the optimal path data packets are forwarded.

Hint based probabilistic protocol: Beraldi et al. [41] in this protocol, the nodes of the network uses a set of meta-information defined as hints to discover a route to the destination. This protocol has lower control overheads.

Preemptive routing in ad hoc networks: Goffe et al. [42] developed a routing algorithm. The algorithm initiate the route discovery process to discovery an alternative route before the probable current route failure.

Labeled successor routing (LSR): Rangarajan and Garcia-Luna-Aceves [43] presented LSR. According, to authors view many on-demand protocols are built on top of AODV, by exploiting sequence number. Table 2 illustrates the comparative analysis of reactive routing protocols.

Protocol	RS	Beacons	Route metrics	Route repository	Route reconfiguration strategy	CC	TC
DSR	F	No	Hop-count	RC	SN and new route	O(2n)	O(2d)
AODV	F	Yes	Hop-count	RT	SN and new route	O(2n)	O(2d)
TORA	F	No	Hop-count	RT	Link reversal and route repair	O(2n)—during route discovery; O(2a)—during route maintenance	O(2d)
ABR	F	Yes	Degree of association stability	RT	Local broad cast query	O(n + y)—during route discovery; O(x + y)—during route maintenance	O(d + z)—during route discovery; O(l + z)—during route maintenance
SSBR	F	Yes	Strong signal strength	RT	SN and new route	O(n + y)—during route discovery; O(x + y)—during route maintenance	O(d + z)—during route discovery; O(l + z)—during route maintenance
GoFF et al.	F	Yes	Signal strength	RT	New path discovery before route failure	O(2n)	O(2d)
AQOR	F	Yes	Bandwidth	RT	Initiate from destination	O(2n)	O(2d)
ARA	F	No	Hop-count	RT	Alternate route or back track until new route is identified	O(n + r)—during route discovery; O(n + a)—during route maintenance	O(d + p)
ROAM	F	No	Hop-count	RT	Erase route and start a new search to get new route	O(|e|)—during route discovery; O(6Ga)—during route maintenance	O(d)—during route discovery; O(x)—during route maintenance
DAR	F	No	Weighted probabilities	Stochastic RT	New route by forward ant	O(2n)	O(2d)
LSR	F	No	Relay sequence label	RT	SN and new route/local repair	O(2n)	O(2d)
GRP	F	No	Hop-count	RC	Route backup	O(2n)	O(2d + 1)
LDR	F	No	Hop-count	RT	SN and new route/local repair	O(2n)	O(2d)
DBR2P	F	No	Hop-count	None	Local repair	O(2n)	O(2d)
Beraldi et al.	F	Yes	Hint value	RC	Local broadcast query	O(2n)	O(2d)

Table 2.

Comparative analysis of reactive routing protocols.

RS = routing structure; H = hierarchical; F = flat routing repository; RC = route cache; RT = route table; RM = route metric; SP = shortest path; CC = communication complexity; TC = time complexity; n = number of nodes in the network, d = diameter of the network, |e| = number of edges on the network, g = maximum degree of the router, z = diameter of the directed path where the REPLY packet transits, l = diameter of the affected network segment, y = total number of nodes forming the directed path where the Reply packet transmits, p = diameter of direct path of the reply, x = number of clusters.

3.2 Proactive (table driven) routing protocol

In proactive routing, each node has one or more tables that contain the latest information of the routes to any node in the network.

Destination sequenced distance vector routing (DSDV): DSDV, based on BellmanFord routing mechanism is a table-driven routing protocol was developed by Perkins and Bhagwat [44].

Optimized link state routing (OLSR): Clausen et al. [45] proposed the OLSR, a proactive routing protocol based on the link state routing.

OLSR with quality of service (QOLSR): QOLSR, proposed by Munaretto and Fonseca [46] is based on the traditional OLSR.

Hierarchical proactive routing mechanism for mobile ad hoc networks (HOLSR): Villasensor-Gonzalez et al. [47] proposed HOLSR protocol, which was developed based on OLSR by organizing node in a hierarchical structure to overcome the inefficiency faced by the flat routing protocol in exploiting the nodes with higher source like bandwidth, transmission range etc.

Wireless routing protocol (WRP): WRP protocol by Murthy and Garcia-Luna Aceres [48] uses the properties of the distributed Bellman-Ford algorithm. Route is chosen by selecting a neighbor node that would minimize the path cost.

Source tree adaptive routing protocol (STAR): STAR proposed by Garcia-Luna Aceves and Spohn [49]. Using a source tree structure each node defines and store the preferred route to all possible destinations. ORA and LORA are two distinct approaches proposed under STAR protocol. ORA approach is preferred to obtain the optimal path with respect to metric (i.e.) number of hops. With ORA it is possible to obtain feasible paths with fewer packets overhead, but with LORA route do not guarantees to be optimal.

Cluster head gateway switch routing protocols (CGSR): CGSR employs a hierarchical network topology, proposed by Chiag et al. [50] CGSR is based on a distributed algorithm namely least cluster change (LCC). Cluster head is elected by using LCC. LCC algorithm is considered to be stable algorithm for cluster head election. Clustering enables an effective way for channel allocation.

Table 3 describes the comparative analysis of proactive routing protocols.

Protocol	RS	Routing tables	No. of tables	HM	Update frequency	Critical node	RM	CC	TC
DSDV	F	Yes	2	Yes	Periodic	No	Hop-count	O(n)	O(d)
R-DSDV	F	Yes	2	Yes	Probalastic	NO	Hop-count	O(n)	O(d)
OLSR	F	Yes	3	Yes	Periodic	No	Hop-count	O(n)	O(d)
HOLSR	H	Yes	3	Yes	Periodic	Yes, cluster head	Hop-count	O(n)	O(d)
CGSR	H	Yes	2	No	Periodic	Yes, cluster head	Hop-count	O(n)	O(d)
QOLSR	H	Yes	3	Yes	Periodic	No	Delay, bandwidth, hop-count	O(n)	O(d)
WRP	F	Yes	4	Yes	Periodic	No	Hop-count	O(n)	O(d)
GSR	F	Yes	3	No	Periodic with neighbor	No	Hop-count	O(n)	O(d)
STAR	H	Yes	1	No	Only at specific events	No	Hop-count	O(n)	O(d)

Table 3.

Comparative analysis of proactive routing protocols.

RS = routing structure; H = hierarchical; F = flat; CC = communication complexity; TC = time complexity; n = number of nodes in the network; d = diameter of the network.

3.3 Hybrid routing protocols

Hybrid routing protocols are designed with the route discovery mechanism and the table maintenance mechanism features of reactive and proactive respectively. Hybrid protocol is suitable for ad hoc network where large numbers of nodes are present. The protocols discussed in this section overcome the drawbacks of both proactive and reactive routing protocols such as latency and overhead problems in the network.

Zone routing protocol (ZRP): ZRP proposed by Samer et al. [51] is a hybrid routing protocol. This protocol has features of both proactive and reactive mechanism. In ZRP two different routing approaches are exploited: intrazone routing protocol (IARP) and interzone routing protocol (IERP).

Zone based hierarchical link state routing protocol (ZHLS): ZHLS by Joa-Ng and Lu [52] developed network which is divided into non-overlapping zones based on geographical information.

Landmark ad hoc routing (LANMAR): LANMAR by Pei et al. [53] is a novel routing protocol. LANMAR have combined features of both FSR and Landmark routing. A subnet, set of nodes are grouped together as a single unit are likely to move as a group.

Relative distance micro-discovery ad hoc routing (RDMAR): RDMAR proposed by Aggelous and Tafazoli [54] is loop-free highly adaptive, efficient and scalable protocol. RDMAR consists of two main algorithms: the route discovery algorithm and route maintenance algorithm.

Distributed spanning tree (DST) routing: DST by Radhakrishnan et al. [55] proposed a routing algorithm based on the distributed spanning trees. DST proposes two different routing strategies to determine a route between a source and a destination pair namely: (1) Hybrid tree flooding (HFT) and (2) Distributed spanning tree (DST) shuttling.

Distributed dynamic routing (DDR) algorithm: DDR by Nikaein et al. [56] is a tree based routing protocol. In DDR the trees do not require a root node. In this algorithm the tree are constructed by exchanging the periodic beacon messages among neighbors’ nodes.

Fisheye state routing (FSR): FSR based on link state routing algorithm, designed by Pei et al. [57]. FSR maintains the accurate distance and path quality information about the immediate neighboring nodes. FSR are more scalable to large networks.

Hybrid ant colony optimization (HOPNET): Wang et al. [58] proposed a hybrid ant colony optimization (HOPNET) based on nature–inspired algorithm such as ant colony based optimization (ACO) and zone routing.

Fisheye zone routing protocol (FZRP): FZRP presented by Yang and Treng [59] inherits the idea of fisheye state routing in ZRP.

Link reliability based hybrid routing (LRHR): Xiaochuan et al. [60] proposed a novel hybrid routing protocol namely, LRHR. LRHR achieves the dynamic switching between table driven and on demand routing strategies due to the frequent topology changes in the network.

Mobility aware protocol synthesis for efficient routing: Bamis et al. [61] proposed a new stability metric to determine the mobility level of nodes in a network. Based upon this metric the nodes can be classified into different mobility classes in turn determines the most suitable routing techniques for a particular source to destination pair. Table 4 illustrates the comparative analysis of hybrid routing protocols.

Protocol	RS	Multiple routes	Beacons	RM	Route repository	Route rebuilding	Critical node	CC	TC
ZRP	F	No	Yes	Through put, end-end delay, packet loss percentage	Intrazone and interzone RT	Route repair at failure point	Yes	Intra-O(ZN); Inter-O(N + V)	Intra-O(I); Inter-O(2D)
FSR	F	No	No	Scope range	RT	SN	No	O(N)	O(D)
LANMAR	H	No	Yes	Hop count	RT at landmark node	SN	Yes	O(N)	O(D)
RDMAR	F	No	No	Hop count	RT	SN and new route	No	O(N)	O(D)
SLURP	H	Yes	No	Power consumed	location Cache	SN	Yes	During route discovery; Intra-O(2ZD); Inter-O(2D)b; During route maintenance; Intra-O(2N/M); Inter-O(2Y)	Intra-O(2 N/M); Inter-O(2Y)
ZHLS	H	Yes	No	End-end delay, packet loss percentage	Intrazone and interzone RT	Location request sent	Yes	During route discovery; Intra-O(N/M); Inter-O(N + V); During route maintenance; Intra-O(N/M)^a; Inter-O(N + V)	Intra-O(I); Inter-O(D)
DST	H	Yes	No	Power consumed, hop count	RT	Holding time or shuttling	Yes	Intra-O(ZN); Inter-O(N)	Intra-O(ZD); Inter-O(D)
DDR	H	Yes	Yes	Stable routing	Intrazone and interzone RT	SN	Yes	Intra-O(ZN); Inter-O(N + V)	Intra-O(I); Inter-O(2D)
HOPNET	H	No	No	Hop-count	Intrazone and interzone RT	Route repair at failure point	Yes	O(n)	O(D)
LRHR	F	Yes	Yes	Edge weight	RC,RT	New route discovery	No	O(n)	O(D)
FZRP	H	No	Yes	Hop-count	Intrazone and interzone RT	Route repair at failure point	Yes	O(n)	O(D)

Table 4.

Comparative analysis of hybrid routing protocols.

3.4 Hierarchical routing protocols

Hierarchical routing protocols apply clustering techniques to build a hierarchy of nodes. Nodes are organized into groups called zones (or) clusters. Each cluster consists of one or more clusters and gateways. Hierarchical routing protocols are developed with an ability to address scalability issues in ad hoc network environment and to minimize excessive overhead. This on the other side increases the tediousness of the routing techniques used by these protocols.

Core-extraction distributed ad hoc routing (CEDAR): Sivakumar et al. [62] introduced CEDAR, an QoS routing algorithm. In CEDAR a subset of nodes are grouped as the core of the network.

Hierarchical state routing (HSR): HSR is a dynamic, distributed multilevel cluster based hierarchical protocol, proposed by Iwata et al. [63] In HSR clustering schema play a vital role. The primary objective of clustering is to have the efficient utilization of radio channel resource and the reduction of routing overhead, Thus the network performance can be enhanced.

Dynamic address approach: Eriksson et al. [64] introduced a dynamic addressing scheme that can enhance scalability in ad hoc network. Under this scheme a geographical location based dynamic address is added to the nodes permanent identifier.

Hierarchical landmark routing (H-LANMAR): H-LANMAR [65] uses, backbone network mechanism, improve the scalability of the network. In H-LANMAR, nodes in the network are grouped into dynamic multihop clusters. Cluster head is referred as backbone node (BN). In case of backbone failure LANMAR schema is used for packet transmission.

Table 5 illustrates the comparative analysis of hierarchical routing protocols.

Protocol	Routing tables	No. of routing tables	Update frequency	Hello message	Critical node
HSR	Yes	2	Periodic, within each subset	Yes	Yes, cluster head
CEDAR	Yes	1	On demand	No	Yes
Eriksson et al.	Yes	2	Periodic	No	No
H-LANMAR	Yes	2	Periodic	No	Yes

Table 5.

Comparative analysis of hierarchical routing protocols.

3.5 Multipath routing protocols

The multipath routing protocols are designed with primary objectives to provide reliable communication and to ensure load balancing as well as to improve quality of service (QoS) of ad hoc environment. Multipath routing protocols address issues such as multiple paths discovery and maintaining these paths.

Caching and multipath routing protocol (CHAMP): CHAMP protocol, proposed by Valera et al. [66] exploits data caching and shortest multipath routing. The main design goal is to minimize the packet drops that occur due to the frequent route breakages.

Secure multipath routing (secMR): SecMR, secure an on-demand multipath routing protocol is designed by Mavropodi et al. [67]. Many security enhancement techniques are imposed in this protocol to present security attacks of collaborating malicious nodes. A centralized Certifying Authority (CA) issues a certificate to the secret keys.

Energy and mobility aware geographical multipath routing protocols (EM-GMR): Liang and Ren [68] developed energy and mobility aware geographical multipath routing protocol, a fuzzy logic mechanism based multipath routing protocol. According to EM-GMR, while choosing the next hop, a mobile node should consider the following constraints namely: the remaining battery capacity, mobility and distance between that next hop to the destination. A fuzzy logic system is developed and applied to the next hop selection mechanism. Thus the authors developed 27 rules for the fuzzy logic set to select the next hop node.

Braided multipath routing (BMR): Ganesan et al. [69] proposed braided multipath routing protocol. In BMR protocol each node discovers alternate best paths from a source to a destination during the route discovery process.

Truth multipath routing protocol (TMRP): Wang et al. [70] proposed TMRP that can be suitable for network with non-cooperative nodes referred as selfish nodes depending upon the resource availability at each node, the cost of forwarding a packet is measured.

Ad hoc on-demand multipath distance vector routing (AOMDV): AOMDV based on traditional AODV was proposed by Marina and Das [71]. The main objective of this protocol is to establish a multiple loop free and link-disjoint paths. The proposed metric namely “advertise hop count “is used in this protocol. The advertised hop count for a node is defined as the maximum acceptable hop count for any path recorded at the node.

Disjoint multipath routing using colored trees: Ramasubramanian et al. [72] developed a loopfree multipath routing protocol using a pair of trees that are red and blue in colors. Thus, a pair of colored trees is constructed by this process.

Scalable multipath on-demand routing (SMORT): SMORT was developed by Reddy and Raghavan [73]. The major objective of this protocol is to minimize the routing overhead occurred during route break recovery and to increase the scalability.

Split multipath routing (SMR): Lee et al., [74] proposed SMR protocol that forms and uses multiple routes of maximally disjoint paths. The overhead caused by route recovery process is minimized by establishing a multiple path from source to destination. Table 6 illustrates the comparative analysis of multipath routing protocols.

Protocol	Proactive/reactive	Loops	Route metrics	Route cache
CHAMP	Reactive	Yes	Shortest path	Yes
AOMDV	Reactive	No	Advertised hop count	No
SMR	Reactive	No	Least delay	No
TMRP	Reactive	No	Auction winner	No
SMORT	Reactive	No	Shortest path	Yes
Ramasubramanian et al.	Proactive	No	Preferred neighbor	Route table

Table 6.

Comparative analysis of multipath routing protocols.

3.6 Multicast routing protocols

In multicasting routing, the data are transmitted from one source to multiple destinations. Multicast protocols can be categorized into two types, namely tree-based multicast and mesh based multicast. The tree based multicast routing protocols utilize the network resource in efficient manner. Mesh based protocols are robust due to formation of many redundant paths between the nodes and in high packet delivery ratio.

Ad hoc multicast routing protocol (AMRoute): Xie et al. [75] developed AMRoute, with main design objective are: scalability and robustness. In ad hoc network with highly dynamic mobile nodes, the control packets overhead are high due to maintenance of multi cast tree.

Adaptive demand-driver multicast routing (ADMR): ADMR, on-demand multicast routing algorithm, developed by Jetchera and Johnson [76]. This protocol does not support any non on-demand components. ADMR, uses a source based forwarding trees and monitors the traffic pattern and rate of the source. ADMR navigates back to the normal mode, when the mobility of the node is reduced.

Differential destination multicast (DDM): Ji and Corson [77] proposed the DDM algorithm. DDM has two important characteristics features: 1. the sender node will have full control over the members of group nodes. 2. Source node, encodes the address within each data packets header on an in-band fashion.

Dynamic core based multicast routing (DCMP): Das et al. [78] proposed DCMP source initiated multicast protocol with an objective to increase the scalability and efficiency as well as to decrease the overhead. In this protocol the source as been classified into active, core active and passive. A core active source can support up to maximum of MaxPassSize passive resource and the hop distance between them is limited by the MaxHop parameter.

Adhoc QoS multicasting (AQM): AQM protocols developed by Bur and Ersoy [79]. In this protocol QoS of the neighboring node monitored and maintained as well as used for efficient multicast routing. Node announces the QoS status during the session initiation phase to join a session, the nodes executes request-reply–reverse procedure, ensures the QoS information is updated and a possible route is chosen session is initiated by a session initiator node.

Content based multicast (CBM): CBM developed by Zhou and Singh [80]. In CBM the nodes collect information about threats and resource at a time period t and distance d away from the location of the node.

Energy efficient multicast routing: Li et al. [81] proposed an energy efficient multicast routing protocol. The authors constructed a weighted network graph by considering the transmission power of each node as a weight between edges. Each node has only information regarding their neighbors. The objective of minimum energy multicast (MEM), problem is to develop the multicast tree with a minimum total energy cost. In this approach, multicast tree is formed by nodes within the highest energy efficiency.

QoS multicast routing protocols for clustering mobile ad hoc networks (QMRPCAH): QMRPCAH, QoS aware multicast routing protocol for clustered ad hoc network was developed by Layuan and Chunlin [82]. It enhances scalability and flexibility.

Epidemic-based reliable and adaptive multicast for mobile ad hoc networks (Eramobile): Eramobile, highly reliable and an adaptive multicast protocol proposed by Ozkasap et al. [83]. In this protocol bio-inspired epidemic methods are utilized in multicast operation in order to support dynamic and topology changes due the unpredictable mobility of the nodes in the network. Table 7 illustrates the comparative analysis of multicast routing protocol.

Protocol	RS	Core/broadcast	Route metrics	Forwarding strategy	Route repository	Critical node
DCMP	F	Core	New route	Source routing	RT	No
ADMR	H	Neither	Link breaks	Flooding/tree based	RT	Yes
AMRoute	H	Core	Unicast operation	Shared tree	Based upon algorithm	Yes
Li et al.	F	Neither	Minimum energy	Source routing	RC	No
QMRPCAH	H	Broadcast	QoS	Bordercast	RT	Yes
AQM	F	Core	QoS	Source routing	RT	No
CBM	F	Core	Threat arrival	Limited broadcast	RC	Yes
DDM	F	Neither	SP	Source routing	None	No
EraMobile	F	Neither	Randomly selected	Local broadcast	None	Yes

Table 7.

Comparative analysis of multicast routing protocols.

RS = routing structure; H = hierarchical; F = flat routing repository; RC = route cache; RT = route table.

3.7 Location-aware routing protocols

The geographical information about a node is collected by another node by using GPS mechanism. Location-aware routing protocols are efficiently supports to improve the scalability of the ad hoc network.

Location aided routing (LAR): Ko and Vaidya [3] presented the LAR protocol, is based on directed flooding strategies. Two different LAR schemes are proposed to determine whether a node is within the request zone.

Distance routing effect algorithm (DREAM): DREAM proposed by Basagni et al. [2] utilizes location information measured using GPS system and speed information of data packet for routing. The working principal of this protocol is a part proactive and reactive in nature.

Greedy perimeter stateless routing (GPSR): GPSR algorithm by Karp and Kung [15] supports scalability and mobility. The protocol exploits greedy forwarding strategies, a node forward the packet to neighbors that is closer to the destination than itself until the destination is reached.

Dynamic route maintenance (DRM) for geographical forwarding: Chou et al. [84] developed a dynamic beacon based geographical routing algorithm. Improvements to location-aided routing through directional count restrictions: Colagross et al. [85] defined a scheme using the count threshold value that keeps track of number of duplicate broadcast packet received by a node. The main objective is to minimize the control packets overhead by decreasing duplicate route discovery packets.

Adaptive location aided mobile ad hoc network routing (ALARM): ALARM algorithm proposed by Boleng and Camp [86], exploits link duration as mobility feedback for adaptation and for evaluating the performance improvement, location informed are used.

A region based routing protocol for wireless mobile ad hoc networks (REGR): REGR by Liu et al. [87] proposed dynamically established a pre-routing region between source-destination pair. The two main features about this protocol are: REGR route creation and REGR route update.

Maximum expectation within transmission range (MER): Kwin and Shroff [88] presented the MER, a location- aware protocol. Each node in the location aware routing use location monitoring tool namely GPS.

SOLAR: Ghosh et al. [89] proposed a framework called ORBIT to achieve the macro-level mobility. ORBIT is defined as an orbital movement pattern of mobile users along specific places called hubs.

Geographical landmark routing (GLR): Kim [90] described GLR algorithm, GLR gives solutions to two major routing issues namely blind detouring problem and the triangular routing problem.

Secure position based routing protocol: Song et al. [91] described a highly secure geographical forwarding (SGF) algorithm. SGF provides source authentication message authentication and message integrity.

On-demand geographical path routing (OGRP): OGRP is an efficient, stateless and scalable routing protocols by Giruka and Singhal [92]. OGRP exploits the features of greedy forwarding, reactive route discovery and source routing.

Location aided knowledge extraction routing for mobile ad hoc networks (LAKER): LAKER protocol proposed by Li and Mohapatra [93]. This protocol combines the features of caching strategy and limited flooding area to decrease the network overhead. Table 8 describes the comparative analysis of location-aware routing protocols.

Protocol	Forwarding mechanism	Loop	Route metric	Scalability	Robustness
LAR	Directional flooding	No	Hop count	No	No
DREAM	Flooding	No	Hop count	No	No
GPSR	Greedy flooding	Yes	SP	Yes	No
Colargrosso et al.	Directional flooding	No	Hop count	No	No
ALARM	Directional flooding	Yes	Hops and mobility	Yes	No
REGR	Directional flooding	Yes	SP	Yes	No
LAKER	Directional flooding	No	Hop count	No	No
OGPR	Source routing	Yes	SP	Yes	Yes
SOLAR	Greedy geographic forwarding	No	SP	No	No
GLR	Source routing	Yes	SP	Yes	No
MER	Greedy geographic forwarding	No	Maximum expectation	No	Yes

Table 8.

Comparative analysis of location-aware routing protocols.

Route Metric SP = shortest path; LSP = local shortest path; WDG = weighted distance gain; CC = communication complexity; H = high; M = medium; L = low.

3.8 Geographical multicast (Geocast) routing protocols

Geocast routing protocols have the combined features of both geographical and multicast routing protocols. The major advantage of Geocast routing protocols are performance improvement and minimizing the control overhead.

Geocasting in mobile ad hoc networks (GeoTORA): Ko and Vaidya [8] proposed the GeoTORA protocol, is based upon the unicast TORA routing protocol.

Geocast protocol for mobile ad hoc network based on GRID (GEOGRID): GeoGRID routing protocol was developed by Liao et al. [7] GeoGrid extends on the unicasting routing protocol GRID. GeoGRID exploit location information in route discovery to define the forwarding zone or geographical area.

Direction guided routing (DGR): An and Papavassilliou [94] designed DGR algorithm based on clustering mechanism. In DGR, the nodes in the network are grouped into clusters and the cluster head is elected using the techniques such a mobile clustering algorithm (MCA).

Geocast adaptive mesh environment for routing (GAMER): GAMER protocol developed by Camp and Liu [95] is based on the mobility nature of nodes. This protocol exploits the mesh creation approach. Table 9 illustrates the Geocast routing protocols comparative analysis.

Protocol	RS	Core/broadcast	Route metrics	Forwarding strategy	Route repository	Critical node
DGR	H	Core	SP	Limited flooding	RC	Yes
GAMER	F	Core	SP	Source routing	RC	No
GeoGrid	H	Core	Hop count	Flooding or ticket based	None	No
GeoTora	H	Broadcast	SP	Limited flooding	RT	Yes

Table 9.

Geocast routing protocol comparison.

RS = routing structure; H = hierarchical; F = flat; SP = shortest path; RC = route cache; RT = route table.

3.9 Power-aware routing protocols

In ad hoc network, performance and lifetime of the nodes depends upon the power consumed by them. Thus energy efficiency is an important and challenging issue in designing power-aware routing protocols.

Device and energy aware routing (DEAR): DEAR, a power-aware protocol for heterogeneous network is proposed by Arun Avudainayagam et al. [96] The protocol is designed for heterogeneous network that consist of two different categories of nodes namely: battery powered nodes and externally powered nodes.

Routing and channel assignment for low power transmission in PCS: Scott and Bombos [97] gave a proposal for reducing the transmission power in PCS network. The author’s goal is to increase the network lifetime of the individual nodes.

Energy conserving routing in wireless ad hoc networks: Chang et al. [98] states that shortest route is the routes with the least energy cost. This leads to a conclusion, more energy will be consumed by the nodes along the shortest paths, whereas the battery power of the other nodes in the network remains unused.

CLUSTERPOW and MINPOW: Kawadia and Kumar [99] developed three different power-aware algorithms namely: CLUSTERPOW, tunneled CLUSTERPOW and MINPOW. A route chosen by this protocol guarantees that each hop in the route has a maximum transmit power capacity.

Interference aware cooperative routing: Mahmood and Comanicics [100] proposed two algorithms, with a goal to maximize the throughput and minimize energy consumption. The algorithms are designed specifically to CDMA based ad hoc sensor network.

Minimum energy hierarchical dynamic source routing (MEHDSR): Tarique and Tepa [101] developed two energy-aware protocols namely MEDSR and HMEDSR based on DSR, the traditional source initiated routing protocols.

Power conserving routing with entropy-constrained algorithm: Karayiannis and Nadella [102] present a routing algorithm with an objective to reduce the overhead involved with route discovery. The authors applied the concept of entropy to develop the power-aware routing algorithm. Thus, two specific implementations are discussed.

1. Single performance metrics: optimizing the route with link cost metrics.

2. Multiple performance metrics: optimizing the route with link cost and link reliability.

This algorithm proves that the entropy constrained algorithms can improve the network lifetime.

Table 10 illustrates the comparative analysis of power aware routing protocol comparison.

Protocol	RT	Type	Path strategy	Routing metrics	Scalability	Robustness	Critical node
DEAR	Yes	Global	Single-path	Based upon ‘device type’	No	Yes	No
Scott and Bombos	No	Centralized	Single-path	Multiple constrained SP	Yes	No	No
CLUSTERPOW	Yes	Clustered	Single-path	Total consumed power	Yes	Yes	Yes
Mahmood and Comaniciu	No	Distributed	Single-path	Energy and interference	No	No	No
MEHDSR	No	Global	Single-path	SP or next available link	Yes	No	No
Karayiannis and Nadella	No	Distributed	Single-path	Link cost and link reliability	Yes	No	No

Table 10.

Comparison of power aware routing protocols.

Routing metrics: SP = shortest path.

4. Conclusion

In this paper, a survey is performed on various routing algorithms including the traditional routing algorithms namely table-driven and source-initiated routing algorithms. Thus the ad hoc routing algorithm is divided into nine categories: (1) source-initiated (reactive or on-demand), (2) table-driven (proactive), (3) hybrid, (4) hierarchical, (5) multipath, (6) multicast, (7) location aware, (8) geographical multicast, (9) power-aware. Even though each protocol classes have different operational mechanism their all come under one roof by having common aim to minimize packet overhead, maximize throughput and minimize end-end delay. In this survey, the major routing issues faced by the routing protocols are discussed and effective study about the various categories of routing algorithm along with a comparative study is performed.