A Survey of MANET Reactive Routing Protocols Under Different Mobility Models

M.K. Jeya Kumar¹ and R.S. Rajesh²

¹ M.G.R University, Chennai, Tamilnadu, (India).

²Faculty of Computer Science and Engineering, M.S University, Tirunelveli, Tamilnadu (India).

ABSTRACT:

Ad Hoc Networks is a multi - hop wireless network with dynamically changing network connectivity owing to mobility. It consists of a collection of wireless mobile nodes it will act without the use of any existing infrastructure or centralized administration. With this flexibility, networks can be formed anywhere, at any time, as long as two or more wireless users are willing to communicate. In such a dynamic network routing is a challenging problem Different routing protocols are designed assuming certain mobility patterns of the mobile nodes in the network. However the choice of mobility pattern may favor certain protocols over the others. Hence it is necessary to study the performance of different routing protocols under different mobility models. In this work two mobility models with high mobility and Low mobility constraints have been considered which mirror the realistic mobility patterns of the mobility nodes with high mobility and low mobility. The two reactive protocols AODV and DSR are examined based on the traces derived for each of these mobility models for various speed of the mobile nodes, Traffic and Node Density in the network. An analysis of the results obtained from the simulations shows that the AODV protocols in Boundless Simulation Area model performs better than DSR. Based on the observations, it is to suggest that AODV routing protocol can be used under high mobility since it outperforms DSR protocols.

KEYWORDS: Ad Hoc Networks; Mobility Models; AODV; TORA; Routing Protocols

Copy the following to cite this article: Kumar M. K. J, Rajesh R. S. A Survey of MANET Reactive Routing Protocols Under Different Mobility Models. Orient. J. Comp. Sci. and Technol;1(1)

Copy the following to cite this URL: Kumar M. K. J, Rajesh R. S. A Survey of MANET Reactive Routing Protocols Under Different Mobility Models. Orient. J. Comp. Sci. and Technol;1(1). Available from: http://www.computerscijournal.org/?p=2092

Introduction

A mobile ad hoc network (MANET) is an autonomous system of mobile hosts connected by wireless links. There is no static infrastructure such as base stations. Each node in the network also acts as a router, forwarding data packets for other nodes. Any number of people could conceivably enter a conference room and agree to support communication links⁶ between themselves, without necessarily engaging the services of any pre-existing equipment in the room. Thus, it is a temporary network with no wires and no administration intervention required.

A central challenge in the design of ad hoc networks is the development of dynamic routing protocols⁶ that can efficiently find routes between two communicating nodes. The routing protocols must be able to cope up with the high degree of node mobility¹¹ that often changes the network topology drastically and unpredictably.

The various ad hoc routing protocols have their unique characteristics. Hence, in order to find out the most adaptive and efficient routing protocol for the highly dynamic topology in ad hoc networks, the routing protocols behavior has to be analyzed using varying node mobility speed, Traffic and network size. Thus, the goal is to carry out a systematic performance comparison of ad hoc routing protocols⁵ under mobility models.

The main aim of this paper is :

• Acquiring the detailed understanding of ad hoc routing protocols such as AODV and DSR
• Implementing the Mobility models such as Probabilistic Random Walk and Boundless simulation Area
• Analyzing the performance differentials of routing protocols under mobility.

The simulator used to simulate the ad hoc routing protocols in random mobility model is Network Simulator 2¹⁰ from Berkeley. NS is a object-oriented, discrete event driven network simulator developed at Barkely written in C++ and OTcl. NS is object – orieted Tcl (OTcl) script interpreter that has simulation event scheduler and network component object libraries.

The organization of the paper is as follows. Section 2 discusses the major mobile Ad hoc routing protocols used in this evaluation study. Section 3 presents the mobility models used in this analysis. The simulation results, followed by their interpretations are presented in section 4. The concluding session is discussed in section 5.

Mobile Ad-hoc Networking Protocols

The main problem with ad-hoc networking is how to send a message from one node to another with no direct link. The nodes in the network are moving around unpredictably, and it is very challenging which nodes that are directly linked together.. The topology of an ad-hoc network is constantly changing and it is very difficult for routing process. There are two main approaches for routing process in ad hoc networks. The first approach is a pro-active approach which is table driven and uses periodic protocols. This means that all nodes have tables with routing information which are updated at intervals. The second approach is re-active, source-initiated or on-demand. This means that every time a message is sent it first has to find a path by searching the entire network. There are many different protocols that are in accordance with the two different routing approaches. Different protocols are specialized in different aspects of the routing. Other aspects than finding a short path are low overhead communication and load-balancing.

The AODV and DSR are source-initiated or on-demand routing protocols¹³. The two ad hoc routing protocols considered in this study are explained below.

Ad-Hoc On Demand Distance Vector Routing – AODV

The Ad-hoc On-demand Distance Vector routing protocol^1,3,7 enables multihop routing between the participating mobile nodes wishing to establish and maintain an ad-hoc network. AODV is a reactive protocol based upon the distance vector algorithm.

The algorithm uses different messages to discover and maintain links. Whenever a node wants to try and find a route to another node it broadcasts a Route Request (RREQ) to all it’s neighbors. The RREQ propagates through the network until it reaches the destination or the node with a fresh enough route to the destination. Then the route is made available by uncasing a RREP back to the source.

The algorithm uses hello messages (a special RREP) that are broadcasted periodically to the immediate neighbors. These hello messages are local advertisements for the continued presence of the node, and neighbors using routes through the broadcasting node will continue to mark the routes as valid. If hello messages stop coming from a particular node, the neighbor can assume that the node has moved away and mark that link to the node as broken and notify the affected set of nodes by sending a link failure notification (a special RREP) to that set of nodes.

Dynamic Source Routing-DSR

Dynamic Source Routing(DSR),⁴ belongs to the class of reactive protocols and allows to dynamically discover a route across multiple network hops to any destination. Source routing means that each packet in its header carries the complete ordered list of nodes through which the packet must pass. DSR uses no periodic routing of messages., there by reducing network bandwidth overhead, conserving battery power and avoiding large routing updates throughout the ad-hoc network. Instead DSR relies on support from the MAC layer.

Mobility Models

The mobility models considered in this evaluation is Probabilistic Random Walk and Boundless Simulation Area are explained below.

Probabilistic Random Walk

Chiang’s mobility mode¹² utilizes a probability matrix to determine the position of a particular MN in the next time step, which is represented by three different states. State 0 represents the current location of given MN, state 1 represents the MN’s next position, and state 2 represents the MN’s next location if the MN moves forward. The probability matrix used is

where each entry P(a,b) represents the probability that an MN will go from state a to state b. Here state 0 denotes the current location, state 1 denotes the previous location and state 2 denotes the next location. In Chiang’s simulator each node moves randomly with a preset average speed. This implementation produces probabilistic rather than purely random movements which may yield more realistic behaviors. The mobility patterns for the mobility of nodes with probability matrix P is given here. For each chosen probability value the node travels for a distance of 10 meters with a constant velocity of 10 m/s

Boundless Simulation Area

In the Boundless Simulation Area Mobility Model, a relationship between the previous direction of travel and velocity of an MN with its current direction of travel and velocity exists⁹. A velocity vector v = (v,θ ) is used to describe an MN’s velocity v as well as its direction θ; the MN’s position is represented as (x; y). Both the velocity vector and the position are updated at every ∆t time steps according to the following formulas:

x(t +∆t)= x(t)+ v(t) * cosθ (t);

This ^[vy⁽(^tt^{* t),}tt))^*min[max(^t]yt)t)^v(v^t(⁾;t) *^vsin^,0),V(^max];t);

where V_max is the maximum velocity defined in the simulation, ∆_v is the change in velocity which is uniformly distributed between [-A_max *∆t, A_max * ∆t], A_max is the maximum acceleration of a given MN, ∆ θ is the change in direction which is uniformly distributed between , and α is the maximum angular change in the direction an MN is traveling.

The Boundless Simulation Area Mobility Model is also different in how the boundary of a simulation area is handled. In all the mobility models previously mentioned, MNs reflect off or stop moving once they reach a simulation boundary. In the Boundless Simulation Area Mobility Model, MNs that reach one side of the simulation area continue traveling and reappear on the opposite side of the simulation area. When the node encounters the simulation boundary, it appears on the opposite side of the simulation area and continues traveling at the same angle and velocity. When ∆t time steps finish, the MN chooses a new direction and velocity evaluated based on the previous direction and velocity and begins traveling again. In effect, this technique creates a torus-shaped simulation area that are allowing MNs to travel unobstructed. The node reaching the boundary reappears on the opposite side of the simulation area. When it reappears, the MNs parameters like the speed, direction are not changed and also the MNs does not stop there. This will generate mobility without any sharp turns or sudden increase/decrease of velocity of the MN. Also the distribution will be uniform which will ensure constant number of neighbors for all the MNs.

Performance Results

This section discusses the various predominance metrics used and the Performance differentials analyzed.⁸ The performance metrics analyzed are the fraction of packets delivered at the destination and the packet delivery ratio for various speeds of mobility, Traffic and Network Size.

The simulation is done with different nodes in wireless sensor networks with respect to the Probabilistic random walk mobility model and Boundless Simulation Area mobility models. The protocols considered for analysis are AODV and DSR.

Speed vs Packet Delivery Fraction

The Performance of the routing protocols in terms of packet delivery ratio is examined with respect to the mobility of nodes.⁶ Tow different network traffic density scenarios² are considered one with 10 connections and another with 20 connections. The simulation results are shown in the Fig. 1.

The differences in packet delivery ratios produced by probabilistic Random Walk and Boundless simulation area are very less. The result produced by AODV is almost stable for low and high mobility. In probabilistic Random Walk and Boundless simulation area, AODV Protocols perform better than DSR in lower and higher mobility status.

Figure 1: Packet Delivery Fraction for varying speed Click here to View figure

 

Speed vs End-to-End delay

The performance of the routing protocols in terms of End-to-End Delay is examined with respect to mobility of the nodes. End-to-end delay are considered for 10 connections and 20 connections traffic density. The results are shown in the Fig. 2.

The end-to-end delay difference in Probabilistic Random Walk and Boundless Simulation Area is very less. The AODV in probabilistic Random walk model perform best in low mobility and high mobility conditions. In Boundless simulation Area DSR perform better than AODV in low mobility and AODV performs best in higher mobility status.

Figure 2: Speed vs End-to-end Delay Click here to View figure

 

Traffic vs Packet Delivery Ratio

The performance of the routing protocols in terms of packet delivery ratio is examined with respect to traffic load. Tow different network traffic density scenarios are considered one with 10 connections and another with 20 connections. The simulation results are shown in the Fig. 3.

The packet delivery ratio obtained from the simulation show sharp decrease when the number of packets is increased from 1 to 4 and number of connections is increased form 10 to 20. In Probabilistic Random Walk Model, there is a slight difference in packet delivery ratio, where it is static in Boundless simulation area mobility model. AODV Protocols performs better than DSR in low traffic and high traffic conditions.

Figure 3: Traffic vs Packet Delivery Ratio Click here to View figure

 

Traffic vs End-to-End Delay

The performance of the routing protocols in terms of End-to-End Delay is examined with respect to traffic load. End-to-end delay are considered for 10 connections and 20 connections traffic density scenarios. The simulation results are shown in the Fig. 4.

In all mobility models the routing protocols consume less time to deliver packets with 10 connections and 1 packets per second/connections protocols. More time is spend to deliver packets when the number of packets and connections are increased. The difference in the time spends by both the protocols under probabilistic Random Walk and Boundless Simulation Area is very less. AODV Performs better than DSR in Probabilistic Random Walk model in low and high traffic. In low traffic condition AODV performs best in Boundless Simulation Area and DSR performs best in higher traffic conditions.

Figure 4: Traffic vs End-to- Delay Click here to View figure

 

Node density Vs Packet Delivery Fraction

The performance of the Routing protocols in terms of packet delivery ratio is examined with respect to the area in which the nodes are likely to move. Packet delivery ratios are considered for 10 connections and 20 connections traffic density. The simulation results are shown in the Fig. 5.

In Probabilistic random Walk and Boundless Simulation area, the packets delivery ratio generated by both the protocols do not show any considerable difference. In both the mobility models AODV Protocols performs best in lower and higher Node Density status.

Figure 5 :Node Density vs Packet Delivery Ratio Click here to View figure

 

Node Density vs End-to-End Delay

The performance of the routing protocols in terms of end-to-end delay is examined with respect to the area with in which the nodes are likely to move.. Two traffic density scenarios are considered- one with 10 connections and another with 20 connections. The results are shown graphically in Fig. 6.

The end-to-end delay is very less with higher node density and increases heavily when the node becomes sparse. The delay time consumed by DSR in Boundless Simulation Area is lesser than AODV in high and slightly higher in lesser node density.

Figure 6: Node Density vs End-to-End Delay Click here to View figure

 

Conclusion

In the probabilistic Random walk model the mobility pattern does not show any sharp turn and sudden stops. The number of neighbors becomes average and hop distance is minimum. This reduces the delay and increases packet delivery ratio. AODV yields good performance for high/low mobility, high/low traffic and sparse/dense network. But the performance of DSR is good for low traffic and low mobility.

In Boundless simulation area lets the node to be traveled unobstructed throughout the entire simulation area and avoid the edge efforts caused in all the remaining models. The traveling pattern of the mobile nodes is smoother and speed and direction to travel in each step depends on the previous speed and direction. The simulation results show that performance produced by both the protocols can be used but AODV may be advisable for sparse distribution.

The main future enhancement of this paper is as follows. In this paper only considered the number of nodes as constant throughout the simulation. But this could be varied dynamically so as to make the network becomes a scalable network and thus the network becomes scalable. The various parameters used for propagation model, Link layer, MAC Layer, Interface Queue and the antenna type in the Mobile Ad Hoc nodes can also be modified so as to evaluate more practical mobile networks.

References

1. Amir R.Das, Charles E.Perkins and Elizabeth M.Royer. “An Implementation Study of the AODV routing protocol”, Proceedings of the IEEE Wireless Communication and Networking Conference(INFOCOM), Tel Aviv, Isrel, pp 3-12, March (2000).
2. B.L. Agba , F. Gagnon, A. Kouki, “Scenarios generator for ad hoc networks” International Symposium on Industrial Electronics, July 2006, Montreal, Canada (2006).
3. C. Perkins and E. Royer. “Ad Hoc On-Demand Distance Vector Routing”. The 2nd IEEE workshop on Mobile Computing Systems and Applications(WMCSA ’99), New Orleans, pp 90-100, February (1999).
4. Jochen Schiller “Mobile Communications”, Addision Wesley Longman Pvt.Ltd, India. (2000).
5. Josh Broch, David A.Maltz, David B. Johnson Yih-Chen Hu and Jorjeta Jetcheva, “A Performance Comparison of Multihop Wireless Ad Hoc Network Routing Protocols”, ACM MOBICOM 98, Dallas, Texas. pp 25-30, October (1998).
6. P. Johanson , T. Larsson, N. Hedman , Mielczarek and M.Degrermark., “Routing Protocols for Mobile Ad Hoc Networks – a comparative performance analysis”, Proceedings of the ACM/IEEE International Conference on Mobile Computing and Networking(MOBICOM), Seattle, WA, pp 195-206, august (1999).
7. Samir. R. Das, R. Castaneda and J.Yan. “Simulation based Performance Evaluation of Routing Protocols for Mobile Ad-hoc Networks”ACM/Baltzer Mobile Networks and Applications (MONET), pp 179-189, (2000).
8. Samir R. Das, Robert Castaneda, Jiangtao Yan, Rimli Sengupta, “Comparative Performance Evaluation of Routing Protocols for Mobile Ad Hoc Networks”, 7th International Conference on on Computer Communication and networks( IC3N, pp 153-161, October (1998).
9. The VINT Project, The Network Simulator – ns-2, URL: http://www.isi.edu/nsnam/ns/. Page accessed on April 12th, (2003).
10. Tony Larsson, Nicklar Hedman, “Routing Protocols in Wireless Ad Hoc Networks – A Simulation Study”, Masters thesis in Computer Science and Engineering, Stockholm, Lulea University of Technology, (1998).
11. Tracy Camp, Jeff Boleng, Vanessa Davies, “A Survey of Mobility Models in Wireless Ad-hoc Networks” Wireless Communications & Mobile Computing (WCMC): Special issue on Mobile Ad Hoc Networking: Research, Trends and Applications, vol. 2, no. 5, pp. 483-502, April (2002).
12. Vanessa Ann Davies, “A Thesis on “Evaluating Mobility Models within an ad-hoc networks”, Colaroda School of Mines, (2000).
13. Z. Haas,. A new routing protocol for reconfigurable wireless networks. In Proceedings of the IEEE International Conference on Universal Personal Communications (ICUPC), pages 562-565, Oct. (1997).

---

This work is licensed under a Creative Commons Attribution 4.0 International License.