An Analysis of Link Disjoint and Node Disjoint Multipath Routing for Mobile Ad Hoc Network

Published Online March 2016 in MECS DOI: 10.5815/ijcnis.2016.03.07

A Mobile Ad hoc Network is a collection mobile device that can communicate with each other without using any fixed network infrastructure through wireless medium [1]. Mobile nodes can communicate with each other directly or through intermediate nodes and form a multi hop communication. If nodes are fall in each other transmission coverage can communicate without intermediate node. The challenging characteristics of this network are: frequent changes in the network topology, frequent link breakage. This is occurs in the network due to depleted battery power may leads to mobile nodes are die in the network or mobile nodes frequently leave the coverage area from each other. In this situation data delivery between source and destination node with a single path is very difficult or sometimes it may not be possible. The packet drop is very high in such network scenarios. To cope up from such situation multipath data delivery is very effective. In multipath routing more than one path discovered between source and destination node. Data packet can be send concurrently in all path or data packet can be send by selecting path one after another. Routing algorithm need to select path tactfully to deliver data efficiently [6, 7]. To deliver data packets through node disjoint and link disjoint path may be one way to achieve fault tolerant path. This is one of the major advantages of using multipath routing data delivery. If some path is fails still there are other paths available to cope with failure. The application of such network is very wide like battle field, disaster management, under water network etc.

In this paper, a variant of well-known AOMDV protocol node disjoint and link disjoint multipath routing is simulated and analyzed. We have computed various QoS matrices i.e. throughput, average end-to-end delay, routing overhead with variable node density and pause time. To the best of our knowledge and so far literature studied no such analysis is exist in the context of Mobile Ad Hoc Networks.

The rest of the paper is organized as follows. In section II we have discussed the works related to multipath routing protocols. Section III included brief discussion about node disjoint and link disjoint path and AOMDV protocol. Simulation work and results analysis is presented in Section IV and finally, we have concluded the work in Section V.

• II.    Related Works

Due to numerous benefits of multipath routing over single path data delivery has attracted lots of attention. The main target of multipath routing protocols is to reduces the use of scarce network resources i.e. battery power, bandwidth. Further, it may also reduce fault occurrence, minimize average end-to-end delay, distribute load or traffic to various paths and ensure the guarantee of message delivery. This way multipath routing protocol maintains various QoS parameters of any network. Here we have discussed some of the multipath routing protocols work on node disjoint and link disjoint multipath techniques.

Kejia Zhang et al. in [8] analyzed effect of disjoint paths exists between pair of sensor nodes which may increase the various network parameters like robustness, throughput, and load balancing. They proposed an efficient distributed algorithm known as DFDP (Distributedly finding disjoint paths) to find k disjoint paths exist between pair of node. Natarajan Meghanathan in [9] proposed link-disjoint, node-disjoint and zone-disjoint multi-path algorithms focusing on the trade-off between lifetime and hop count of routes for MANET. Through these three techniques successive multipath discoveries and the number of disjoint paths, hop count per multipath are thoroughly analyzed. The number of zone disjoint paths per multipath is minimum compare to others. Also, time elapsed in path discoveries process zone disjoint techniques outperforms others. X. Huang et al. in [10] evaluated the applicability of node disjoint multipath in the context of VANETs and compare the same with single path. Through simulation results author’s shows the node disjoint multipath techniques can be used in VANETs, because it improves the packet delivery ratio and reduces the delay in packet delivery. W. Almobaideen et al. in [11] proposed a modified form of AOMDV known as Maximally Spatial Disjoint Multipath routing protocol (MSDM) for MANETs. The data delivered through multiple paths which are mostly spatially separated and node-disjoint paths. Results show that spatially node-disjoint routes perform better than AOMDV which selects only link-disjoint paths. Abhishek et al. [12] proposed NMN-AODV protocol which is based on AODV. In this protocol only two node-disjoint routes between source and destination node are established for data transmission. As compare to MP-AODV this protocol uses minimum number of control packet exchange and establish node disjoint path faster than the MP-AODV. Resulting end-to-end delay is less than the MP-AODV. S. Waharte et al. [13] proposed a 2-path routing protocol which is a special case of multipath routing. They have shown the benefits of spreading traffic over multiple paths to improve overall network performance. This protocol evaluated in a static and nonenergy-constrained network. One of the important parameter called interference among paths is bad effect the network performance. They also studied the effect of interference on single and multiple source-destination pair scenarios. In the presence of interference network capacity is degraded and voids the benefits of multipath routing. The 2-path protocol identifies two paths between source and destination. All the node participated in path-1 and path-2 form a connected graph. There is no edge shared between path-1 and path-2, which ensure that path discovered is free from interference. V. Kudachi et al. [14] proposed a node disjoint multipath routing protocol based on AODV. They addressed residual energy of nodes and discovery of multiple node disjoint paths with low routing overhead. M.Nagaratna et al. [15] addressed the frequent path breakage in MANET due to which network performance is not good. They have computed multiple paths between source and destination pair using node disjoint methodology. An improvement is shown when data delivered through multiple paths in term of reliability, Route Request Frequency and end-to-end delay. V.K. Barbudhe et al. [16] proposed a node disjoint multipath protocol based on AODV with additional features data security during transmission and link failure. This protocol reduces routing overhead significantly because through a single flooding of a RREQ message route discovery and maintenance process completes. S. Upadhayaya et al. [17] proposed a Node Disjoint Multipath Routing Considering Link and Node Stability (NDMLNR). They mainly focused on QoS routing in MANETs but no experimental analysis is discussed in the paper only theoretical analysis is presented. P.Periyasamy [21] presented a survey on three categories of multipath routing protocols along with their comparison. In [22] P.Periyasamy et al. compare the performance of various existing routing protocols like AOMDV, OLSR and ZRP with different network scenarios. The network scenarios are created from various well known mobility models. Also, they have evaluated these protocols based on two different traffic sources are TCP and CBR. In [23] authors address the security issues on AOMDV routing protocol. The simulation results shows security attacks effects the network throughput and delay but packet loss remain unaffected. Finally, security attacks need to be address with better counter measure for great applicability of multipath routing protocol. P.Periyasamy et al. in [24] proposed energy optimized multipath protocol. They preserve energy by modifying route update information of MMRE-AODV protocol named as OMMRE-AOMDV protocol. This protocol not reduces energy consumption, it also minimize average end-to-end delay, routing overhead. Also, improves packet delivery and throughput of the network. Koffka Khan and Wayne Goodridge [25] address fault tolerance issue for Wireless Sensor Networks. The protocol proposed known as Multi Criteria AOMDV evaluated in lossy environments in node disjoint manner. A new path loss metric is included in the routing table. The main advantage of this protocol it avoids such paths facing with high packet drop or paths are very dynamic in nature. Jing Yang et al., [26] proposed a multipath routing incorporating dynamic clustering and any colony optimization. The routing protocol is designed to address energy consumption issue by nodes in the network. The cluster head are selected based on residual energy. The ACO is to find multiple paths between cluster head and destination node. Final selection of route is based on energy consumption of individual paths by cluster heads. This novel technique increases the network lifetime by reducing node energy consumption. Dhriti Sundar Maity and Subhrananda Goswami [28] use ACO for MTSP and Swarm Inspired Multipath data transmission. The congestion control issue in MANET is address nicely. In the proposed protocols paths are continuously get updated using path pheromone scents. The congestion measures using total queue length and hop distance. The data delivery through congested route is avoided. S. Saqaeeyan and M. Roshanzadeh [29] reliability and load balancing issues are considered in a wireless sensor network. This protocol also ensures that data delivery to the destination some extend guaranteed.

The routing selection is based on remaining energy of nodes within the transmission of any sender node. The simulations results show that reliability is improved and it helps in increasing overall network life time.

• III.    System and Network Model

Link disjoint paths are the path between source and destination pair where no link is common between source and destination node [6, 7].

Node disjoint paths are path between source and destination pair where no node is common except source and destination [6, 7]. The node disjoint path is always link disjoints in nature because in node disjoint path no link is common between source and destination node. But link disjoint not necessarily node joint because node may be shared by various link. In fig.1 three different link disjoint paths shown between S (source) and D (Destination) node are S-a-b-c-d-D , S -i-k-e-g-D and S-m-e-f-D. The last two paths share the node e. In Fig.2 there are two node disjoint paths shown between S and D node are S-a-b-c-d-D and S-e-f-g-h-D does not share any node.

Fig.1. Link Disjoint Path disjoint routes are also link disjoint). The destination node replies with only k copies out of many link-disjoint paths, i.e. Route Request (RREQ) packets arrive through unique neighbors and nodes apart from the first hop are replied. Further, to avoid loop ‘advertised hop count’ is used in the routing table of nodes. The protocol only accepts alternate route with hop count less than the advertised hop count. A node can receive a routing update via a RREQ or Route Reply (RREP) packet either forming or updating a forward or reverse path. Routing updates received via RREQ and RREP are routing advertisement messages.

• IV.    Simulation Setup and Results Analysis

We carried out the simulation works on NS-2.34 [18]. The table 1 shows different simulation parameters and Table 2 shows the different simulation parameters values considered for the simulation work. Here, we varied the number of nodes and node pause time. The Random Waypoint Mobility model is considered for node movement. This model is widely accepted and used in simulation of ad hoc network as well sensor networks. In this model node randomly chooses new destination and move towards it. Node moves towards destination with velocity between 0 to max. Further, node stay at particular location for certain time period known as pause time. This means a time epoch for which a node will stay in particular location. After expire of time epoch nodes are moving towards new destination within the simulation area [19].This process continue until simulation time. For the performance analysis we have computed average end-to-end delay, routing overhead and throughput. The results are computed from several simulation runs. The results are analyzed using Matlab [20] and awk programming.

Fig.2. Node Disjoint Path

Table 1. Simulation Parameters

Parameter	Specifications
MAC Protocol	IEEE 802.11 DCF
Radio Propagation Model	Two-ray ground reflection model
Channel type	Wireless channel
Mobility Model	Random Way Point
Antenna model	Omni-directional
Traffic Source	CBR
Routing Protocol	Node Disjoint AOMDV Link Disjoint AOMDV

• A. Ad Hoc on Demand Multipath Distance Vector (AOMDV)

Ad Hoc on Demand Multipath Distance Vector (AOMDV) [2, 3, 4, 5] protocol is a multipath variation of AODV protocol. The main objective of this protocol is to achieve efficient fault tolerance i.e. quick recovery from route failure. The protocol computes multiple links disjoint loop free paths per route discovery. If one path fails the protocol switches to other available paths. However, only link disjoint routes are selected (node

Table 2. Values of Simulation Parameters

Parameter	Values
Simulation Time	1000s
Simulation Area (X *Y )	1500 m x1500 m
Packet Size	512 bytes
Packet Rate	4 packets/sec.
Transmission Range	250 m
Bandwidth	2 Mbps
No. of Nodes	10,20,30,40,50,100
Pause time	2,5,10,15
Max. speed of nodes ( m/s)	10

A. Throughput

Fig.3 shows the throughput of Node Disjoint AOMDV with varying node density and node pause time. Throughput gradually increases with increasing node pause time and number of nodes till 40 nodes. The throughput is almost become stable at 40 nodes onwards till 100 nodes when pause time is 15s. The overall throughput is good in pause time 2s. The maximum achievable throughput is 160.43 kbps.

B. End-to-End delay

20 ^

□  - Pause time 2 sec

Pause time 5 sec

Pause time 10 sec

Pause time 15 sec

Number of Nodes

Fig.5. End-to-End delay Node Disjoint Multipath

0t--------i---------£---------:---------£---------£---------:---------£---------£---------£

10     20     30     40     50     60     70     80     90     100

Number of Nodes

Fig.3. Throughput of Node Disjoint Multipath

Fig.4 shows the throughput of Link Disjoint AOMDV with varying node density and pause time. Throughput gradually increases with increasing number of nodes till 40 nodes and node pause time similar to Node Disjoint AOMDV. The throughput is decreases 40 nodes onwards in all pause time till 70 nodes. At 80 nodes slight increases in throughput is noticed except node pause time 10s. The maximum achievable throughput is 165.39 kbps.

Fig.5 shows the end-to-end delay of Node Disjoint AOMDV with varying node density and node pause time. When number of node moves from 10 to 20 for all pause time end-to-end delay is decreases, and afterward delay gradually increases with increasing number of nodes till 40 nodes and node pause time. Delay is further decreases 90 nodes onwards except at pause time 5s. The delay at pause time 2s and 10s achieves the minimum delay for number of node is 100.

7’

0t--------------[--------------£--------------C--------------£--------------£--------------£--------------£--------------£--------------[

10     20     30     40     50     60     70     80     90     100

Number of Nodes

Fig.6. End-to-End delay Link Disjoint Multipath

60 F

Pause time 5 sec

-o - Pause time 10 sec

Pause time 15 sec

20>У

0---------------:-----------------r-----------------r-----------------r-----------------r-----------------r-----------------r-----------------■

10     20     30     40     50     60     70     80     90

Number of Nodes

Fig.4. Throughput of Link Disjoint Multipath

Fig.6 shows the End-to-End delay of Link Disjoint AOMDV with varying node density and node pause time. When number of node moves 10 to 20 for all pause time end-to-end delay is decreases, and afterward delay gradually increases with increasing number of nodes till 50 nodes and node pause time except pause time 15s. Except at node pause time 5s delay increases when nodes

move from 50 to 60. From 50 nodes onwards gradually delay decreases till 100 nodes except at pause time 2s and 5s. The delay at pause time 10s achieves the minimum delay i.e. 66.6179 for number of node is 20.

C. Routing Overhead

Routing overhead gives count of total number of routing packets generated during simulation by routing protocol.

Number of Nodes

Fig.7. Routing Overhead Node Disjoint Multipath

Fig.7 shows the routing overhead of Node Disjoint AOMDV with varying node density and node pause time. At pause time 5s for number of node 70 noticed minimum routing overhead. But routing overhead is gradually increases with increasing number of nodes and node pause time. The overall routing overhead is good when node pause time is 10s. The routing overhead is maximum at node pause time 5s for number of nodes 100.

Pause time 2 sec

Pause time 5 sec

Pause time 10 sec

Pause time 15 sec

Number of Nodes

Fig.8. Routing Overhead Link Disjoint Multipath

Fig.8 shows the routing overhead of Link Disjoint AOMDV with varying node density and node pause time. Similar to node disjoint with pause time 5s for 70 nodes noticed minimum routing overhead. But routing overhead is gradually increases with increasing number of nodes and node pause time. The overall routing overhead is good when node pause time is 2s. The routing overhead is maximum at node pause time 5s for number of nodes 100.

• V.    Conclusion and Future Works

We have evaluated the performance between Link Disjoint and Node Disjoint Multipath variant of AOMDV protocol. These protocols investigated with varying node density and pause time. Pause time play very vital role on the performance of routing protocols. If pause time increases gradually it seems the network become more static and connectivity among nodes is more stable. The small pause time indicate dynamic network. Various QoS matrices are computed to analyze the performance. It is evident from the results that node disjoint multipath performs better as compare to link disjoint multipath routing technique. Theoretically, also we have noticed that node disjoint is better compare to link disjoint and simulation results also justified the same. We have only considered random way point mobility model for this analysis. In future, Link Disjoint and Node Disjoint Multipath AOMDV protocols may be investigate with other node mobility models and other network scenarios for better insight understanding.