Performance analysis of MANET protocols in different mobility patterns.
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.
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, TORA and DSR are source-initiated or on-demand routing protocols and DSDV is a table driven protocol. The ad hoc routing protocols considered in this study are explained below.
A. Destination - Sequenced Distance Vector - DSDV
DSDV (2) belongs to the class of pro-active routing protocols. This protocol is based on the classical Bellman-Ford routing algorithm (2) to apply to mobile ad hoc networks. DSDV also has the feature of the distance-vector protocol (3) in that each node holds a routing table including the next-hop information for each possible destination. Each entry has a sequence number. If a new entry is obtained, the protocol prefers to select the entry having the largest sequence number. If their sequence number is the same, the protocol selects the metric with the lowest value.
Routing information is transmitted by broadcast. Updates have to be transmitted periodically or immediately when any significant topology change is available. Sequence numbers are assigned by destination, means the destination gives a sort of default even sequence number, and the emitter has to send out the next update with this number.
Packets are transmitted between the stations of the network by using routing tables which are stored at each station of the network. Each routing table, at each of the stations, lists all available destinations, and the number of hops to each. Each route table entry is tagged with a sequence number which is originated by the destination station. To maintain the consistency of routing tables in a dynamically topology, each station periodically transmits updates, and transmits updates immediately when significant new information is available.
Routing information is advertised by broadcasting or multicasting the packets which are transmitted periodically and incrementally as topological changes are detected-for instance, when stations move within the network. Data is also kept about the length of time between arrival of the first and the arrival of best route for each destination. Based on this data, a decision may be made to delay advertising routes which are about to change soon, thus damping fluctuations of the route tables.
B. Ad-Hoc On Demand Distance Vector Routing--AODV
The Ad-hoc On-demand Distance Vector routing protocol (7) (1) 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.
C. Temporally-Ordered Routing Algorithm--TORA
TORA protocol (10) belongs to the class of reactive protocols. The protocol is highly adaptive, efficient and it is used to establish the "temporal order" of topological change events which is used to structure the reaction to topological changes. The protocol is designed to minimize reaction to topological changes. The protocol is distributed in that nodes need only maintain information about adjacent nodes. The protocol is "source initiated" and quickly creates a set of routes to a given destination only when desired.
The protocol accomplishes three functions through the use of three distinct control packets (8) such as query (QRY), update (UPD) and clear (CLR). QRY packets are used for both creating and maintaining routes, and CLR packets are used for erasing routes.
D. Dynamic Source Routing-DSR
Dynamic Source Routing (DSR) (5), 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.
Random Mobility Model
The mobility model (8) plays a very important role in determining the protocol performance in mobile Ad Hoc Network. Hence, this work is done using the random mobility models like Random Waypoint, Random Walk and Random Direction. These models with various parameters reflect the realistic traveling pattern of the mobile nodes. The following are the three models with the traveling pattern of the mobile nodes during the simulation time.
A. Random Waypoint
The Random Way Point Mobility Model includes pauses between changes in direction and/or speed. A Mobile node begins by staying in one location for a certain period of time (i.e. pause). Once this time expires, the mobile node chooses a random destination in the simulation area and a speed that is uniformly distributed between [min-speed, max-speed]. The mobile node then travels toward the newly chosen destination at the selected speed. Upon arrival, the mobile node pauses for a specified period of time starting the process again. The random waypoint model is a commonly used mobility model in the simulation of ad hoc networks. It is known that the spatial distribution of network nodes moving according to this model is nonuniform. However, a closed-form expression of this distribution and an in-depth investigation is still missing. This fact impairs the accuracy of the current simulation methodology of ad hoc networks and makes it impossible to relate simulation-based performance results to corresponding analytical results. To overcome these problems, it is presented a detailed analytical study of the spatial node distribution generated by random waypoint mobility. The movement trace of a mobile node using the Random Waypoint model is shown in figure 1. It is considered that a generalization of the model in which the pause time of the mobile nodes is chosen arbitrarily in each waypoint and a fraction of nodes may remain static for the entire simulation time.
[FIGURE 1 OMITTED]
B. Random Walk
In this mobility model, a mobile node moves from its current location to a new location by randomly choosing a direction and speed in which to travel. The new speed and direction are both chosen from pre-defined ranges, [min-speed, max-speed] and [0, 2*pi] respectively. Each movement in the Random Walk Mobility Model occurs in either a constant time interval 't' or a constant traveled 'd' distance, at the end of which a new direction and speed are calculated. The movement trace of a mobile node using the Random Walk model is shown in figure 2.
[FIGURE 2 OMITTED]
Since many entities in nature move in extremely unpredictable ways, the Random Walk Mobility Model was developed to mimic this erratic movement. An MN moves from its current location to anew location by randomly choosing a direction and speed in which to travel. The new speed and direction are both chosen from pre-defined ranges, [speedmin, speedmax] and [0, 2*pi] respectively. Each movement in the Random Walk Mobility Model occurs in either a constant time interval 't' or a constant distance traveled 'd', at the end of which a new direction and speed are calculated. If an MN which moves according to this model reaches a simulation boundary, it bounces off the simulation border with an angle determined by the incoming direction. The MN then continues along this new path. random walk on a one or two-dimensional surface returns to the origin with complete certainty, i.e., a probability of 1.0. This characteristic ensures that the random walk represents a mobility model that tests the movements of entities around their starting points, without worry of the entities wandering away never to return. Random Walk is a memory-less mobility pattern. This characteristic can generate unrealistic movements such as sudden stops and sharp turns.
C. Random Direction
A mobile node chooses a random direction in which to travel similar to the Random Walk Mobility Model. The node then travels to the border of the simulation area in that direction. Once the simulation boundary is reached, the node pauses for a specified time, chooses another angular direction (between 0 and 180 degrees) and continues the process.
The Random Direction Mobility Model was created to overcome clustering of nodes in one part of the simulation area. produced by the Random Waypoint Mobility Model. In the case of the Random Waypoint Mobility Model, this clustering occurs near the center of the simulation area. In the Random Waypoint Mobility Model, the probability of an MN choosing a new destination that is located in the center of the simulation area, or a destination which requires travel through the middle of the simulation area, is high. In this model, MNs choose a random direction in which to travel similar to the Random Walk Mobility Model. An MN then travels to the border of the simulation area in that direction. Once the simulation boundary is reached, the MN pauses for a specified time, chooses another angular direction [0, 180] and continues the process. In a slightly modified version MNs continue to choose random directions but they are no longer forced to travel to the simulation boundary before stopping to change direction. Instead, an MN chooses a random direction and selects a destination any where along that direction of travel. The movement trace of a mobile node using the Random Direction model is shown in figure 3.
[FIGURE 3 OMITTED]
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 random-based mobility model: Random Waypoint, Random Walk and Random direction models. The protocols considered for analysis are AODV, DSDV, TORA and DSR.
A. 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 figure 4.
[FIGURE 4 OMITTED]
In Random Way point model, packet delivery ratios produced by all the protocols are very close when the speed is low. The slight difference in the ratio is produced for with 10 connections and 20 connections. When the speed is increased to 20 m/s. the packet delivery ratio s produced by the protocols differ sharply and this difference becomes more with 20 connections. In the case of Random walk and and Random Direction mobility models, the packet delivery ratio differ heavily for lower mobility and higher mobility.
B. Traffic vs Packet delivery fraction
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 figure 5.
[FIGURE 5 OMITTED]
The packet delivery ratos obtained from the simulation sho sharp decrease when the number of packets is increased from 1 to 4 and number of connections is increased form 10 to 20. The differences in packet delivery ratios produced by the routing protocols are very less in Random Waypoint mobility model. Larger differences in packet delivery ratio are obtained in Random walk and random Direction mobility models.
C. 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 figure 6.
[FIGURE 6 OMITTED]
In this a higher packet delivery ratio for higher density of nodes and decreases when the when the node density becomes sparse. In Random waypoint mobility model AODV produces higher packet delivery ratio and DSDV, TORA, and DSR produces lower packet delivery ratio.
D. 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 figure 7.
[FIGURE 7 OMITTED]
With Random waypoint and Random direction mobility models all the The protocols in random waypoint takes less time to deliver the packets compared to Random walk and Random Direction mobility model. The difference in time used by DSDV, TORA and DSR is very high in Random Walk and Random Direction, but its not so high in Random waypoint.
E. 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 figure 8.
[FIGURE 8 OMITTED]
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. AODV spends much lesser time than other protocols under random walk and Random direction mobility models
F. 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 figure 9.
[FIGURE 9 OMITTED]
The end-to-end delay is very less with higher node density and increases heavily when the node becomes sparse. For the varying node density the end-to-end delay produced by the protocols in Random waypoint is very less and very high in Random walk and Random Direction Model. AODV in Random Way point model Performs better than other mobility models.
Random Waypoint model: Most of the times the nodes choose destination closer to the centre of the simulation area and thus producing a dense wave near the centre and stays back there for the specified pause time, also having more neighbors to the nodes in the centre. This will give minimal hop distance between the source-destination pairs. When the network becomes sparse or the traffic load becomes high the performance produced by DSR and TORA decreases sharply.. DSDV protocol's performance is nearer to AODV under network size metric. TORA protocol's performance was not so good under this mobility model. Hence, AODV protocol can be chosen as the routing protocol in this type of mobility conditions.
Random Walk model: This model creates a high mobility scenario with larger travel time the nodes will travel almost to all the areas. Since there is no pause time between change of speed and direction, the need for a protocol that updates the routing information quickly as uses the fresh information about the routing becomes mandatory. The simulation results show that the AODV performs better than DSR, TORA and DSDV. One of the reason here is the average hop distance between the source-destination becomes high, and this will increase packet overhead. The usage of the fresh route information and quickly adapting nature of AODV are reasons for better results produced by the AODV. DSDV produces better results than TORA and can be used as the routing protocol under low mobility conditions. Thus, AODV is the best and suitable choice under this high mobility model.
Random Direction Model is an unrealistic model because it is unlikely that people would spread themselves evenly throughout an area. The nodes choose pause times only at the boundaries and no change of speed and direction before reaching the boundary. This will create a topography in which most of the times most of the nodes are in the boundary and the centre of the area becomes very sparse. Here the average number of hop distance becomes higher and gives lesser number of alternative paths. AODV protocol produces better results than DSDV, TORA and DSR. When the network size is large, DSDV produces better results than TORA and DSR. This observed that AODV is the best choice under this mobility model.
M.K. Jeya Kumar (1) and R.S. Rajesh (2)
(1) Research Scholar, Dr.M.G.R University, Chennai, Tamilnadu, India.
(2) Dept. of Computer Science & Engg., Manonmaniam Sundaranar University, Tirunelveli, Tamilnadu, India,
(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) 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.
(3) Jochen Schiller "Mobile Communications", Addision Wesley Longman Pvt.Ltd, India. 2000.
(4) Johanson P, Larsson.T, Hedman N, Mielczarek and degrermark M., "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.
(5) Perkins C. and Royer.E. "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.
(6) Perkins C.E. and P. Bhagwat, "Highly Dynamic Destination-Sequenced Distance Vector Routing (DSDV) for Mobile Computers", Computer Communications Review, pages 234-244, October 1994.
(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) 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.
(10) 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.
(11) Vanessa Ann Davies, "A Thesis on "Evaluating Mobility Models within an ad-hoc networks", Colaroda School of Mines, 2000.
(12) Vincent D Park and M Scott Corson, "A Highly Adaptive Distributed Routing Algorithm for Mobile Wireless Networks", Proceedings of IEEE Conference INFOCOM'97 on Computer Communications, pp. 1405-1413, April 7-12, 1997.
First Author: Received his MCA degree from Bharathidasan University, Trichirappalli in the year 1993. He fetched his M.Tech. degree from Manonmaniam Sundaranar University, Tirunelveli in the year 2005. His area of interests are Computer Networks and Mobile Computing.. He is currently pursuing his Ph.D degree in Wireless Ad Hoc Networks in Dr.M.G.R University, Chennai under the able guidance of Dr. R.S.Rajesh. At present he is working as an Assistant Professor in the Department of Computer Applications, Noorul Islam College of Engineering, Kumaracoil, India. He has more than 14 years of Teaching experience at P.G. level.
Second Author: Received his B.E and M.E degrees in Electronics and Communication Engineering from Madurai Kamaraj University, Madurai, in the year 1988 and 1989 respectively, and completed his Ph.D in Computer Science and Engineering from Manonmaniam Sundaranar University in the year 2004. In September 1992 he joined in Manonmaniam Sundaranar University where he is currently working as Reader in the Department of Computer Science and Engineering. He is has more than 18 years of PG teaching and Research experience. His current research interests include, Wireless networks, Pervasive computing, Digital image processing and Parallel Computing.
|Printer friendly Cite/link Email Feedback|
|Title Annotation:||mobile ad hoc network|
|Author:||Kumar, M.K. Jeya; Rajesh, R.S.|
|Publication:||International Journal of Computational Intelligence Research|
|Date:||Apr 1, 2009|
|Previous Article:||Mobile agent optimization analysis of Least Time approach Versus V-agent.|
|Next Article:||Statistical analysis of fingerprint pattern.|