Time Delay on-Demand Multipath Routing Protocol in Manets

Time Delay on-Demand Multipath Routing Protocol in Manets

Dhanraj D. Walunj ME(computer II Year) Siddhant College of Engg.

Pune University, India

P.B. Kumbharkar

Assistant Professor, HOD Computer Dept.

Siddhant College of Engg. Pune University, India

ABSTRACT

Mobile ad hoc networks (MANETs) nodes are typically distinguished by their limited power, processing, and memory resources as well as high degree of mobility. In such networks, the wireless mobile nodes may dynamically enter the network as well as leave the network. Due to the limited transmission range of wireless network nodes, multiple hops are usually needed for a node to exchange information with any other node in the network. Thus routing is a crucial issue to the design of a MANET.

This paper proposes a novel energy-aware multipath ad hoc routing protocol to equalize the energy consumption, thus, to extend the network lifetime of each node in MANETs. The proposed Time Delay On-demand Multipath (TIDOM) routing protocol accommodates the time delay function in flooding RREQ packets. The time delay function is inversely proportional to the residual battery capacity of intermediate nodes themselves. This function avoids nodes with poor residual battery capacity, and promotes nodes with good residual battery capacity joining the routes. Simulation results show that TIDOM improves the network lifetime, energy consumption, and additionally packet delivery ratio over the Ad hoc On-demand Multipath Distance Vector (AOMDV).

Keywords

TIDOM (Time Delay On-demand Multipath), AOMDV (Ad Hoc On-Demand Multipath Distance Vector), AODV (Ad Hoc On-Demand Distance Vector), RREQ (Receive Request), RREP (Receive Reply)

1. INTRODUCTION

   MANET consists of a set of mobile nodes, which communicate over radio regardless of the presence of infrastructure. Such networks are suitable for several kinds of applications and are very flexible. Communication has to be relayed over intermediate nodes most of the time due to limited transmission range of wireless interfaces, thus each node has to behave as a router in such multi-hop networks. Mobile Ad hoc Networks (MANETs) [1] are composed of mobile nodes, having limited resources and extreme mobility, and exchanging data through wireless communication without any fixed infrastructures. Due to shorter radio transmission range, multiple hops are essentially needed for communication. Further, node mobility causes the topology of the networks to be dynamically changed, frequently reinitiating the route discovery procedure. Thus, the design of an efficient routing protocol is one of main topics in MANET, and many researchers have studied this area.

   MANETs have several salient characteristics: 1)Dynamic topologies 2) Bandwidth constrained, variable capacity links

   3) Energy-constrained operation 4) Limited physical security. Therefore the routing protocols used in ordinary wired networks are not well suited for this kind of dynamic environment. Routing algorithms [2] are often difficult to be formalized into mathematics they are instead tested using extensive simulation. Recently more attention has been paid to use specific network parameters when specifying routing metrics. Examples might include delay of the network, link capacity, link stability or identifying low mobility nodes. These schemes are generally based on previous work, which is then enhanced with the new metrics. Recently many researchers have attended multipath routing protocol for MANETs, which can acquire multiple paths through one route discovery procedure [3]. Multipath routing protocols provide fault tolerance for minimizing re-initiation of route discovery, and load balancing for extending limited bandwidth. Additionally, load balancing makes MANETs equalizing energy consumption [4]. The most popular protocol is the Ad hoc On-demand Multipath Distance Vector (AOMDV) [5] which is an extension of Ad hoc On-demand Distance Vector (AODV) [6]. A source node floods a RREQ to the entire network in order to find routes to the destination, and when the destination node receives the RREQ via different neighbors, it transmits multiple route reply (RREP) packets to the source node. Lee [7] proposed a multiple routing protocol considering the residual battery capacity of route candidate nodes based on AOMDV. When a destination node replies RREP packets to the source, intermediate nodes add their current battery status to the sum of the battery capacity field in the RREP packet in order to select data transmission route. Liu [8] introduced a threshold of the battery status of nodes. When the residual battery of intermediate nodes becomes under the threshold, they stop to flood RREQ packets, and the source node switches to another route among candidates to extend network lifetime. However, these studies almost select multiple routes among previously established routes according to the link condition, but the energy status of each node in the initial phase of route request (RREQ) finding is not considered.

   In the paper, we present a Time Delay On-demand Multipath (TIDOM) routing protocol which is extended from AOMDV protocol. Our protocol aims to acquire multiple routes having good energy condition of nodes in RREQ flooding phase. When a RREQ packet arrives at the destination at first, the sum of residual battery capacity of intermediate nodes should be maximized, and nodes with poor residual battery condition should avoid joining the route. In order to do this, intermediate nodes intentionally delay

   flooding the RREQ in inverse proportion to their residual battery capacity, thus, the route with first-arrived RREQ at the destination node has the smallest time delay. It has the highest sum of the residual battery capacity of nodes. The route of the second-arrived RREQ has the second-highest residual battery capacity, and so forth. The destination has only to reply the RREP sequentially for multiple times. The source node receives multiple RREPs having good residual battery capacity. Our protocol is expected to have good characteristics in terms of energy efficiency and network lifetime because nodes consume the battery energy equally.

   To evaluate our protocol, we use NS-2 simulator [9] and carry out extensive simulations with respect to AOMDV. As a consequence, the evaluation results show that TIDOM outperforms AOMDV in terms of the network lifetime, energy consumption, and packet delivery ratio.

2. MANET ROUTING PROTOCOLS

   Routing protocols for Mobile ad hoc networks can be broadly classified into two main categories:

   Proactive or table-driven routing protocols Reactive or on-demand routing protocols.

   1. Table Driven Routing Protocols (Proactive)

      In proactive or table-driven routing protocols, each node continuously maintains up-to-date routes to every other node in the network. Routing information is periodically transmitted throughout the network in order to maintain routing table consistency. Thus, if a route has already existed before traffic arrives, transmission occurs without delay. Otherwise, traffic packets should wait in queue until the node receives routing information corresponding to its destination. However, for highly dynamic network topology, the proactive schemes require a significant amount of resources to keep routing information up-to-date and reliable. Certain proactive routing protocols are Destination Sequenced Distance Vector (DSDV), Wireless Routing Protocol (WRP), Global State Routing (GSR) and Clusterhead Gateway Switch Routing (CGSR).

      2.1 On-Demand Routing Protocols (Reactive)

      In contrast to proactive approach, in reactive or on demand protocols, a node initiates a route discovery throughout the network, only when it wants to send packets to its destination. For this purpose, a node initiates a route discovery process through the network. This process is completed once a route is determined or all possible permutations have been examined. Once a route has been established, it is maintained by a route maintenance process until either the destination becomes inaccessible along every path from the source or until the route is no longer desired. In reactive schemes, nodes maintain the routes to active destinations. A route search is needed for every unknown destination. Therefore, theoretically the communication overhead is reduced at expense of delay due to route research. Some reactive protocols are Cluster Based Routing Protocol (CBRP), Ad hoc On-Demand Distance Vector (AODV) [11], Dynamic Source Routing (DSR) [2], Temporally Ordered Routing Algorithm (TORA), Associatively-Based Routing (ABR), Signal Stability Routing (SSR) and Location Aided Routing (LAR).

3. MULTIPATH ROUTING PROTOCOL IN MANET

   Standard routing protocols in ad hoc wireless networks, such as AODV and DSR, are mainly intended to discover a single route between a source and destination node. Multipath routing consists of finding multiple routes between a source and destination node. These multiple paths between source and destination node pairs can be used to compensate for the dynamic and unpredictable nature of ad hoc networks. Multiple paths can provide load balancing, fault-tolerance, and higher aggregate bandwidth. Load balancing can be achieved by spreading the traffic along multiple routes. This can alleviate congestion and bottlenecks. From a fault tolerance perspective, multipath routing can provide route resilience.

   1. AOMDV (Ad hoc On-demand Multipath Distance Vector)

      AOMDV [10] is an extension to the AODV protocol for computing multiple loop-free and link-disjoint paths. To keep track of multiple routes, the routing entries for each destination contain a list of the next-hops along with the corresponding hop counts. All the next hops have the same sequence number. For each destination, a node maintains the advertised hop count, which is defined as the maximum hop count for all the paths. This is the hop count used for sending route advertisements of the destination. Each duplicate route advertisement received by a node defines an alternate path to the destination. To ensure loop freedom, a node only accepts an alternate path to the destination if it has a lower hop count than the advertised hop count for that destination. Because the maximum hop count is used, the advertised hop count therefore does not change for the same sequence number. When a route advertisement is received for a destination with a greater sequence number, the next-hop list and advertised hop count are reinitialized.

      AODVM [10] is an extension to AODV [11] for finding multiple node disjoint paths. Intermediate nodes are not allowed to send a route reply directly to the source. Also, duplicate RREQ packets are not discarded by intermediate nodes. Instead, all received RREQ packets are recorded in an RREQ table at the intermediate nodes. The destination sends an RREP for all the received RREQ packets. An intermediate node forwards a received RREP packet to the neighbor in the RREQ table that is along the shortest path to the source. To ensure that nodes do not participate in more than one route, whenever a node overhears one of its neighbors broadcasting an RREP packet, it deletes that neighbor from its RREQ table. Because a node cannot participate in more than one route, the discovered routes must be node-disjoint.

   2. TIDOM (Time Delay On-Demand Multipath Routing Algorithm)

      We propose a protocol named Time Delay On-Demand Multipath routing protocol which is an extension of AOMDV. It obtains energy-efficient multiple routes with a distributed method. The procedure of route finding is similar with AOMDV except intermediate nodes delay flooding a RREQ in inverse proportion to their residual battery capacity. The delay time in flooding RREQs reflects nodes residual battery capacity. If a node has good residual battery capacity, it is promoted to join the route, and if not, it is avoided to join the route. Therefore, the status of residual battery capacity can be represented to a time delay function for the RREQ packet flooding.

      TIDOM produces the time delay for the RREQ flooding which we proposed in [12], and selects multiple routes that

      have totally minimum time delay among the candidate routes as follows;

      Where Di (t) is the time delay function of node i at time t, and is inversely proportional to residual battery capacity of node i=1,, k on the routes j= 1,, m such that Di (t) 1/ Ci (t) where Ci (t) is the residual battery capacity of node i at time t.

      When a source node needs a route to send data packets but does not have any routing information about a destination node, the source node issues RREQ packets to find multiple routes to the destination. The intermediate nodes in the network rebroadcast the RREQ packets to their neighbors if they are not the destination node or do not have routing information. In contrast to AOMDV where it relays the route request packets immediately, the intermediate nodes of TIDOM wait for some time in inverse proportion with its residual battery capacity in order to delay the RREQ packet. Intermediate nodes drop the late-arrived RREQ packets with the same source node and destination sequence number.

      Figure 1. Time Delay On-Demand Multipath Routing Algorithm (TIDOM)

      Figure 1 shows an example of a mobile network. The number beside a node ID denotes the normalized current residual battery capacity against full battery capacity. The maximum charged battery capacity sets 1. We assume that one time step of this example network is 10 % of maximum battery capacity. We show relative time order from to The source node S floods a RREQ packet to the neighbor node A and B at time . In this example, the node A and B have same residual battery capacity of 90 %, thus, after receiving RREQ they wait for the same duration of one t step, then re-flood the packet to their neighbours at time T2 simultaneously. Nodes C and E receive the same RREQs at same time from node A and B respectively. After one t step later, node C transmits RREQ at time T3. Node E transmits the packet at time T4. Node A and B drops the late-arrived RREQ packets to prevent loops. Finally, the destination receives three RREQ packets with same the sequence number from node F, G, and H sequentially for some duration. The first route which the destination obtains is (S-A-C-F-D) because it has totally 2.7 residual battery capacities. The second is (S-B-E-G-D) which has 2.6, and the last is (S-A-C-H- D) which has 2.5.

      When the destination repeatedly replies RREP packets to the neighbors which sent the RREQ packet to the destination previously, they relay the RREP packet till the source node receives it. Figure 2 shows the sequence of the RREP packets

      unicasting. To provide the node-disjoint route, the

      Figure 2. Time Delay On-Demand Multipath Routing Algorithm (TIDOM)

      intermediate nodes receiving RREP packet continuously verify whether they already sent the RREP having the same source sequence number. If the node has already transmitted the same RREP, it drops the packet in order to guarantee the node-disjoint routes. In Figure 2, node C receives two RREP packets; the first comes from node F, and the later comes from node H. Thus, because node C has already relayed the RREP coming from node F, it drops the late-arrived RREP from node H. Accordingly, the source node acquires two node- disjoint routes (S-A-C-F-D) and (S-B-E-G-D). The source node starts to transmit data packets by switching

      . Figure 3. RREQ flooding procedure

      candidate routes in order to guarantee maximum throughput of data packet and apprpriate load-balance. Figure 3 and 4

      Figure 4. RREP unicasting procedure

      show a procedure of RREQ flooding and RREP unicasting respectively. In Figure 3, we set the number three (k=3) for multiple routes because alternate routes more than two routes does not have big effects on performance advantages [13]. We need a correlation between the delay time and the ratio of residual to maximum battery capacity in order for routing layer to send time-delayed RREQ packet messages to MAC layer. Figure 5 shows the relation the delay time and the radio, which can set up an equation like as:

      carrying out extreme simulations in order to balance between minimizing the side effect due to the time delay of RREQ flooding and extending the network lifetime. Finally, Tmax and Tmin are fixed to 200 and 1 msec, respectively, in this paper.

      Figure 5. The relation between residual battery capacity and RREQ packet delay time (Tmax = 200 msec, Tmin =1 msec)

      TIDOM adopts AOMDVs route maintenance algorithm. The source node starts to transmit data packets through the route in which the route reply packet is arrived at the source node first. If the source node has several candidate routes later, it uses the round robin method to switch routes.

4. SIMULATION BASED PERFORMANCE EVALUATION

This section provides details of simulation parameters used in simulation of protocols in various simulators like OPNET, NS-2, GloboSim, etc. mentioned earlier. The description consists of simulation parameters, effect of mobility, workload and performance results.

We analyze the two protocols of AOMDV and TIDOM by NS-2 simulator, for which we adapt the Glomosim version source code of AOMDV [13]. TIDOMs code is modified from this. In order to avoid contention between neighbour nodes by transmit packet simultaneously, AOMDV uses jittering techniques which intentionally generate random time delay from 0 to 100 msec. In wireless ad hoc networks, transmission of control packets is very important for route discovery. So, most scheduling algorithms give higher priority to control packets than data packets, by separating control packet queues from those of data packets [14]. Therefore, in order to transmit timely the packet according to the time delay function, TIDOM minimizes the jittering time for the RREQ packet flooding from 0 to 0.1 msec. Therefore, the total delay time of TIDOM is the sum of the time delay Di (t), plus jittering time, Tjitter

We adapt a user defined energy model, where transmitter consumes 600 mA, receiver consumes 350 mA, and node consumes 35 mA when it idles, according to general IEEE

802.11 chipsets. The initial battery capacities are assigned to different values with each scenario which run for 1000 simulation time. In this simulation, the source node use up to three multiple routes (k = 3), and data packets are transmitted via the round-robin method. The number of nodes are 100, uniformly distributed in the network area where the size is 1500m x 1500m. The PHY/MAC layer model is IEEE802.11a. The application layer uses CBR (constant-bit- rate) to send packets with 5 packets per second. The simulation is repeated 5 times with same variables and different random seed, and the outputs are averaged.

Major performance metrics to evaluate both protocols are the network lifetime, the number of death nodes, route length, packet delivery ratio, energy consumption, energy consumption distribution, broken link, and discovery overhead. We define the network lifetime as the time when any node exhausts the battery of itself at first among the network. And, we adapt the number of death nodes with the simulation time to verify characteristics of battery consumption between both protocols.

Figure 6. Network lifetime between AOMDV and TIDOM with varying mobility, fixing 7 connections and

5 packets/s data transmission

The packet delivery ratio can be represented as the ratio of an amount of successive received packets of a destination to an amount of transmitted packets by a source node during the simulation time. The discovery overhead includes the RREQs and RREPs generated by route discovery.

4.1 Varying Node Mobility

We fix the number of connection and traffic load at 7 and 5 packets per second respectively, and vary node mobility from 0, 2.5, 5, 7.5 to 10 m/sec. These simulations focus on the performance related on the network lifetime according to node mobility. We set up the initial battery capacity as 30 mAh and run the simulation for 1000 seconds. Figure 6 shows simulation results of the network lifetime. TIDOM outperforms AOMDV, particularly, improving 16 % at the static network. Furthermore, within simulation time, death nodes are decreased in all mobility as shown in Figure 7 and

8. We observed that the time to appear the first dead node of AOMDV is 777 second whereas that of TIDOM is 844 second at node mobility of 5 m/s as shown in Figure 7. Notably, when

simulation time is 900 second, the number of dead nodes in TIDOM is reduced to 12 from 34 of AOMDV. Likewise,

Figure 7. Death nodes between AOMDV and TIDOM with 5 m/s mobility, fixing 7 connections and 5 packets/s data transmission.

Figure 8 shows the number of dead nodes as a function of simulation time at node mobility of 10 m/sec. The gap between two protocols tends to diminish but TIDOM still shows better performance. This is because TIDOM finds routes in consideration with nodes energy status; thus, the nodes network lifetime in TIDOM is longer than that in AOMDV which is unaware of nodes energy conditions.

Figure 8. Death nodes between AOMDV and TIDOM with 10 m/s mobility, fixing 7 connections and 5 packets/s data transmission.

Figure 9 shows the average route length of two protocols. As we have expected, TIDOM has slightly longer route length because TIDOM does not use shortest hop distance metric but uses minimum battery cost, leading to selection of any route with lower total cost. Increasing route length makes the physical distance between neighbor nodes shorter, increasing communication time to delivery packets stably. Therefore, as shown in Figure 10, the TIDOM delivery data packets more

Figure 9. Average route length between AOMDV and TIDOM with varying mobility, fixing 7 connections and 5 packets/s data transmission.

Figure 10. Packet delivery ratio between AOMDV and TIDOM with varying mobility, fixing 7 connections and 5 packets/s data transmission.

Figure 10. Energy consumption between AOMDV and TIDOM with varying mobility, fixing 7 connections and 5packet/s data transmission

than AOMDV over average 17.6 % in all mobility. Though TIDOM consumes energy in delivery data packets, due to less broken link, it decease energy consumption because of decreasing discovery overheads. Consequently, TIDOM consumes less total energy which is composed of transmit, receive and idle energy as shown in Figure 11.

1. CONCLUSION

   This paper presents proposed Time Delay On-demand Multipath (TIDOM) routing protocol accommodates the time delay function in flooding RREQ packets. The function is inversely proportional to residual battery capacity of intermediate nodes themselves. This function avoids, or promotes nodes joining the routes with the condition of residual battery capacity. TIDOM is extended from AOMDV by applying this function. Minimum and maximum delay times of this function are determined by balancing the performance improvement related to energy consumption and side effects of time delayed flooding. Simulation results show that TIDOM improves the network lifetime in all mobility spans. The number of death nodes exhausting their battery is greatly diminished by TIDOM. Nodes of TIDOM have more residual battery capacity than AOMDV after finishing simulation. In additionally, TIDOM increases the packet delivery radio because the TIDOMs lifetime of links becomes longer, which can be inferred by route lengths of TIDOM. Longer lifetime of links causes TIDOM to decrease he energy consumption and discovery overhead compared with AOMDV.

   As a special type of network, Mobile Ad hoc Networks (MANETs) have received increasing research attention in recent years. There are many active research projects concerned with MANETs. Mobile ad hoc networks are wireless networks that use multi-hop routing instead of static networks infrastructure to provide network connectivity. MANETs have applications in rapidly deployed and dynamic military and civilian systems. The network topology in MANETs usually changes with time. Therefore, there are new challenges for routing protocols in MANETs since traditional routing protocols may not be suitable for MANETs. Researchers are designing new MANETs routing protocols, comparing and improving existing MANETs routing protocols before any routing protocols are standardized using simulations. This work is an attempt towards a comprehensive performance evaluation of AOMDV and proposed TIDOM routing protocol.

2. REFERENCES

1. Mobile ad hoc networks (MANET).http:

   //www.ietf.org/html.charters/manet-charter.html, 1997.

   IETF Working Group Charter

2. Vincent D. Park and M.Scott Corson. A highly adaptive Distributed routing algorithm for mobile wireless networks. In Proceedings of INFOCOM 1997, 1997.

3. S. Mueller, R.P. Tsang, and D. Ghosal, Multipath routing in mobile ad hoc networks: Issues and challenges, Performance Tools and Applications to Networked Systems, 2004, p. 209234.

4. Jiazi Yi , Asmaa Adnane, Sylvain David, and Benoît Parrein, Multipath optimized link state routing for mobile ad hoc networks , Ad Hoc Networks 9, 2011, pp. 28-47.

5. M.K. Marina and S.R. Das, Ad hoc on-demand multipath distance vector routing, Wireless

   Communications and Mobile Computing, vol. 6, Nov. 2006, pp. 969-988.

6. C. Perkins, E. Belding-Royer, S. Das, Ad hoc On- Demand Distance Vector (AODV) Routing, rfc3561.txt (2003).

7. J. Lee, and S. Kim, Power-aware Dynamic Path Selection Scheme in AOMDV (Ad hoc On-demand Multipath Distance Vector), Journal of the Institute of Electronics Engineers of Korea, 2008, pp. 42-50.

8. J. Liu, J. Chen, and Y. Kuo, Multipath Routing Protocol for Networks Lifetime Maximization in Ad-Hoc Networks, 2009 5th International Conference on Wireless Communications, Networking and Mobile Computing, Sep. 2009, pp. 1-4.

9. NS-2 Network simulator http://www.isi.edu/nsnam/ns.

10. Nasipuri and R. Castañeda, Performance of Multipath Routing for On-Demand Protocols in Mobile Ad Hoc Networks , Mobile Networks and Applications, 2001, pp. 339-349.C. E. Perkins and E. M. Royer, Ad Hoc

    On-demand Distance Vector Routing, In Proceedings of the 2nd IEEE Workshop on Mobile Computing Systems and Applications, New Orleans, LA, February 1999, pp. 90- 100.

11. C. Perkins, Ad hoc On demand Distance Vector (AODV) routing, IETF Internet draft (1997), http://www.ietf.org/internet-drafts/draftietf-manet-aodv-

    00.txt.

12. W. Cho and S.-lyun Kim, A fully distributed routing algorithm for maximizing lifetime of a wireless ad hoc network, 4th International Workshop on Mobile and Wireless Communications Network, pp. 670- 674.

13. http://www.icis.ntu.edu.sg/wagio/simtools.html.

14. S. R. Das, C. E. Perkins and E. E. Royer, "Performance comparison of two on-demand routing protocols for ad hoc networks," in Proc. IEEE INFOCOM, pp. 3-12, 2000.

Authors profile:

Mr. Dhanraj Walunj is post graduate student in the Department of Computer Engineering, Siddhant college of engineering, Pune university, Maharashtra, India. He obtained his BE from SVPMs College of Engineering, Baramati, Pune University. His area of interest includes wireless communications and networking.

Prof. P. B. Kumbharkar received the Masters degree

M.E in Computer Engineering. He is currently working as Assistant Professor and Head of the department of Computer Engineering in Siddhant College of engineering, Pune University, Maharashtra, India. He published several papers in National and International Journals. His current research is focused on Computer Networks, Multimedia and Streaming Technology.