Proceedings of the 9th WSEAS International Conference on APPLIED INFORMATICS AND COMMUNICATIONS (AIC ’09)
MANET Routing Protocols vs. Mobility Models: Performance Analysis and Comparison
VALENTINA TIMCENKO, MIRJANA STOJANOVIC, SLAVICA BOSTJANCIC RAKAS Institute Mihailo Pupin
Volgina 15, 11060 Belgrade
SERBIA
valentina@kondor.imp.bg.ac.yu http://www.institutepupin.com
Abstract: – This paper considers performance of mobile ad hoc network (MANET) routing protocols with respect to group and entity mobility models. The three widely used routing protocols have been investigated and compared: Destination Sequenced Distance Vector (DSDV), Ad-hoc On-demand Distance Vector (AODV) and Dynamic Source Routing (DSR). Mobility models encompass: Reference Point Group Mobility (RPGM), Random Waypoint (RW), Gauss-Markov (GM) and Manhattan Grid (MG). Simulations have been carried out using Network Simulator version 2 (NS2) and its associated tools for animation and analysis of results. We have developed a set of specific simulation scripts that are applicable for a wide range of MANET scenarios. Comparative analysis of simulation results includes network performance with respect to mobile node speeds and network size.
Key-Words: – MANET, DSDV, AODV, DSR, Group
1 Introduction
A mobile ad hoc network (MANET) is an autonomous, self-configuring network of mobile nodes that can be formed without the need of any pre-established infrastructure or centralized administration. MANETs are extremely flexible and each node is free to move independently, in any random direction. Each node in MANET maintains continuously the information required to properly route traffic.
Simulation studies of MANET routing protocols have mostly assumed Random Waypoint (RW) as a reference mobility model [1], [2]. In order to examine many different MANET applications there is a need to provide additional mobility models. Typical examples are modeling a movement in city streets environment, university campuses and movement of groups of nodes, e.g. for specific military purposes. Recently, a performance comparison of DSR and AODV protocols based on Manhattan Grid (MG) model has been published [3]. A performance study of DSR and AODV considering probabilistic random walk and boundless simulation area has been presented in [4]. A performance evaluation of DSDV and AODV using scenario based mobility models has been presented in [5]. A comparative analysis of DSR and DSDV protocols, considering RW, Group Mobility, Freeway and MG models can be found in [6].
mobility model, Entity mobility model
The objective of this work is to provide a systematic and comprehensive comparative analysis of the three typical representatives of MANET routing protocols, one proactive protocol (DSDV) and two reactive protocols (AODV and DSR), with respect to the four mobility models. They include one group model and three entity models. Performance analysis and comparison encompasses packet delivery fraction, end-to-end delay and routing protocol overhead with respect to different node speeds and network size. The analysis covers a wide range of MANET scenarios and aims to be useful in a variety of applications, for purpose of network research, design and implementation.
2 Overview of Routing Protocols
Considering procedures for route establishment and update, MANET routing protocols can be classified into proactive, reactive and hybrid protocols. Proactive or table-driven protocols attempt to maintain consistent up-to-date routing information from each node to every other node in the network. Each node maintains tables to store routing information, and any changes in network topology need to be reflected by propagating updates throughout the network. Reactive or on demand protocols are based on source-initiated on-demand reactive routing. This type of routing creates routes only when a node requires a route to a destination.
ISSN: 1790-5109
271 ISBN: 978-960-474-107-6
Proceedings of the 9th WSEAS International Conference on APPLIED INFORMATICS AND COMMUNICATIONS (AIC ’09)
Then, it initiates a route discovery process, which ends when the route is found. Hybrid protocols combine proactive and reactive schemes.
DSDV is a proactive routing protocol based on the Bellman-Ford algorithm. Each mobile node maintains a routing table in which all the possible destinations and the number of hops to them in the network are stored. The entries in the table may change extremely dynamically so the advertisements might be made quite often.
AODV is a reactive protocol that improves the DSDV in the sense of minimizing the number of required broadcasts by creating routes on a demand basis, as opposed to maintaining a complete list of routes.
DSR is a reactive protocol, in which each mobile node keeps track of the routes of which it is aware in a route cache. Upon receiving a search request for path, it refers to its route cache to investigate if it contains the required information. DSR uses more memory while reducing the route discovery delay in the system.
3 Mobility Models
A mobility model should attempt to emulate the movements of real mobile nodes. Mobility models are based on setting out different parameters related to node movement. Basic parameters are the starting location of mobile nodes, their movement direction, velocity range, speed changes over time. Mobility models can be classified to entity and group models [7]. Entity models cover scenarios when mobile nodes move completely independently from each other, while in group models nodes are dependent on each other or on some predefined leader node.
Reference Point Group Mobility (RPGM)
model represents the random motion of a group of
mobile nodes and their random individual motion
within the group. All group members follow a
logical group center that determines the group
motion behavior. The entity mobility models should
be specified to handle the movement of the
individual mobile nodes within the group. Purpose
of logical group center is to guide group of nodes
continuously calculating group motion vector GM , and this way defining behavior, speeds and directions for mobile nodes. Once the updated reference point RP(t+1) has been updatedrthey are
combined with random motion vector RM values to represent the random motion of each mobile node around its reference point.
Random Waypoint (RW) model assumes that each host is initially placed at a random position
within the simulation area. As the simulation progresses, each host pauses at its current location for a determinable period called the pause time. RW model assumes the possibility of setting cut-of phase, scenario duration, width and height of the area (x,y), minimum and maximum speed ( vmin and
vmax ), as well as maximum pause time. RW model
includes pause times between changes in direction and/or speed. Pause is used to overcome abrupt stopping and starting in the random walk model. Upon expiry of this pause, the node arbitrary selects a new location to move towards and a new speed which is uniformly randomly selected from the interval [vmin,vmax].
Gauss-Markov (GM) model enables different levels of randomness by setting only one parameter. Initially, each mobile node has preset speed and direction parameter values. This model captures the velocity correlation of a mobile node in time and represents random movement without sudden stops and sharp turns. At fixed intervals of time movement occurs by updating the speed and direction of each node. At each iteration, the new parameter values are calculated depending respectively on the current speed and direction and on a random variable.
Manhattan Grid (MG) model has originally been developed to emulate the Manhattan street network, i.e. a city section which is only crossed by vertical and horizontal streets. The trajectories of mobile nodes are confined to a grid topology. The MG model can be described by the following parameters: mean speed, minimum speed (with a defined standard deviation for speed), a probability to change speed at position update, and a probability to turn at cross junctions.
4 Simulation and Results
Simulations have been carried out by the Network Simulator version 2 (NS2) [8]. Hardware and operating system (OS) configuration for performing simulations is specified in Table 1. The basic mobility scenario generation tool is BonnMotion [9]. The analysis of simulation results has been performed by means of the Trace Graph [10].
r
Table 1 HW and OS configuration
Processor
Pentium 4, CPU 1.8 GHz
RAM
480 MB
OS
Linux, RedHat distribution
Kernel
Fedora 6, kernel 2.6
Simulator
NS2 2.32, NAM 1.13
ISSN: 1790-5109 272
ISBN: 978-960-474-107-6
Proceedings of the 9th WSEAS International Conference on APPLIED INFORMATICS AND COMMUNICATIONS (AIC ’09)
The studied scenarios of MANET networks consist of 20 and 100 mobile nodes, with parameters defined in Table 2.
Table 2 Simulation parameter values
model. In all cases, the worst results are obtained for the MG model. This happens due to severe restriction of the node movement, irrespective of their density. Additionally, when two nodes diverge, the probability of traffic signal breaking up increases.
Duration
200s
Traffic sources
CBR, packets 512 Byte, interarrival time 0.2s
Transport protocol
UDP
MAC protocol
MAC/802.11
Network interface
Phy/WirelessPhy
Propagation model
Two ray ground
Radius of node
250m
Antenna
OmniAntenna
Area size
500m x 500m
100.0% 80.0% 60.0% 40.0% 20.0%
0.0%
100.0% 80.0% 60.0% 40.0% 20.0%
0.0%
DSDV
AODV
Routing protocol
DSR
Parameters of the investigated mobility models are presented in Table 3.
Table 3 Parameters of mobility models
a) 20 nodes
Model
Parameter settings
RPGM
GroupSize = 5
Max. pause = 10.0s
RW
Max. pause = 10.0s
GM
UpdateFrequency = 2.5
SpeedStDev = 0.5
MG
X, Y axis blocks = 10, 10
Update distance = 5.0m
Turn probability = 0.5
Max. pause = 10.0s
ISSN: 1790-5109 273
ISBN: 978-960-474-107-6
DSDV
AODV
Routing protocol
DSR
MG
b) 100 nodes
RPGM RW GM
4.1 Packet delivery fraction
Packet delivery fraction, pdf , is defined as a ratio of
delivered and sent packets. The node speed has been varied in the range 5 – 10 m/s. Simulation results are presented in Fig. 1. In 20 node network, the group model RPGM is superior compared to entity models. This happens because the entire communication takes place between a few groups (four groups, each with five nodes). Additionally, in 20 node network reactive protocols perform better than DSDV.
With RPGM, in 100 node network the sparse network effect disappears (20 groups, each with five nodes). There is higher probability that sources and destinations are located in different groups and their distances might become greater. More nodes and groups on the path between source and destination contribute to increased packet loss.
In contrast, RW model performs better for higher density networks, due to higher probability of generating correct routes and maintaining them since there are no space constraints as in RPGM
Fig. 1 Packet delivery fraction vs. routing protocol for different mobility models
4.2 Average end-to-end delay
In the second experiment, we have investigated average end-to-end (e2e) delay of data packets. Node speeds are in the range 1.5 – 25 m/s. Simulation results, considering network size of 20 mobile nodes, are presented in Fig. 2.
Considering routing protocols, DSDV gives the most stable results. This happens because each mobile node maintains the complete routing table, with all possible destinations and number of hops for reaching them. Since the routes are known, DSDV experiences lower latency than the two reactive protocols AODV and DSR. Irrespective of the applied mobility model, DSR suffers from high delay, when increasing the mobile node speed.
pdf [%] pdf [%]
Proceedings of the 9th WSEAS International Conference on APPLIED INFORMATICS AND COMMUNICATIONS (AIC ’09)
1.0 0.8 0.6 0.4 0.2 0.0
DSDV
AODV
DSR
1.5 5 10 15 20 25 Mobile node speed [m/s]
1.0 0.8 0.6 0.4 0.2 0.0
DSDV
AODV
DSR
1.5 5 10 15 20 25 Mobile node speed [m/s]
a) RPGM b) RW
1.0 0.8 0.6 0.4 0.2 0.0
DSDV
AODV
DSR
1.5 5 10 15 20 25 Mobile node speed [m/s]
1.0 0.8 0.6 0.4 0.2 0.0
DSDV
AODV
DSR
1.5 5 10 15 20 25 Mobile node speed [m/s]
c) GM d) MG
Fig. 2 Average end-to-end delay vs. mobile node speed, 20 nodes
2.5 2.0 1.5 1.0 0.5 0.0
DSDV
AODV
DSR
1.5 5 10 15 20 25 Mobile node speed [m/s]
2.5 2.0 1.5 1.0 0.5 0.0
DSDV
AODV
DSR
1.5 5 10 15 20 25 Mobile node speed [m/s]
a) RPGM b) RW
2.5 2.0 1.5 1.0 0.5 0.0
DSDV
AODV
DSR
1.5 5 10 15 20 25 Mobile node speed [m/s]
2.5 2.0 1.5 1.0 0.5 0.0
DSDV
AODV
DSR
1.5 5 10 15 20 25 Mobile node speed [m/s]
ISSN: 1790-5109
274 ISBN: 978-960-474-107-6
c) GM d) MG
Fig. 3 Average end-to-end delay vs. mobile node speed, 100 nodes
Average delay [ms] Average delay [ms] Average delay [ms] Average delay [ms]
Average delay [ms]
Average delay [ms] Average delay [ms] Average delay [ms]
Proceedings of the 9th WSEAS International Conference on APPLIED INFORMATICS AND COMMUNICATIONS (AIC ’09)
3.00 2.50 2.00 1.50 1.00 0.50 0.00
DSDV
AODV
DSR
1.5 5 10 15 20 25 Mobile node speed [m/s]
3.00 2.50 2.00 1.50 1.00 0.50 0.00
DSDV
AODV
DSR
1.5 5 10 15 20 25 Mobile node speed [m/s]
a) RPGM b) RW
3.00 2.50 2.00 1.50 1.00 0.50 0.00
DSDV
AODV
DSR
1.5 5 10 15 20 25 Mobile node speed [m/s]
3.00 2.50 2.00 1.50 1.00 0.50 0.00
DSDV
AODV
DSR
1.5 5 10 15 20 25 Mobile node speed [m/s]
c) GM d) MG
Fig. 4 Routing Protocol Overhead vs. mobile node speed, 100 nodes
For lower speed values, AODV suffers from higher delays than the DSR. This happens because AODV has periodic activities (exchange of HELLO messages) and does not use cache to store the routes. With the increase of speed, the routes change more frequently and there is a strong need of finding new routes in DSR as well. In that case the presence of cache becomes insufficient and potentially can become invalid.
Simulation results, considering network size of 100 mobile nodes, are presented in Fig. 3. With the group model, RPGM, delay performance improves with the increase of network size. The network with 20 mobile nodes is much sparser and the entire communication takes place between a few groups. The delay performance suffers from transient partitions that exist in a sparse network. When increasing the number of mobile nodes the sparse network effect disappears and RPGM becomes the most recommendable mobility model.
Among entity models, RW demonstrates the most stable results, irrespectively of network size and routing protocols.
The GM model assumes only slight changes of speed and direction. When the speed is high, it is very likely that the node will continue moving at high speeds, thus generating frequent links breaks. In the case of low initial node speed, the frequency of link breakage is also lower. In the 20 nodes
network, AODV performs better than the DSDV at lower speeds because of its on-demand nature. Consequently, the topology changes are less frequent and AODV sends less routing messages. In 100 nodes network AODV experiences higher e2e delays than DSDV for higher node speeds. Higher network density involves more nodes on the paths, which results in higher frequency of finding new routes.
However, the MG model experiences considerably higher average delays with the increase of network size. This happens because MG model has high spatial and temporal dependence. It presumes that nodes can move only in four possible directions with predefined probabilities to change direction to any other when being at the intersection points. There is also a problem of street blocks which can disable the possibility of communication between nodes when they are not close enough.
4.3 Routing protocol overhead
In the third experiment, we have investigated routing protocol overhead (RPO) in the network with 100 mobile nodes (Fig. 4). RPO is defined as the ratio of generated routing messages and received data packets. Node speeds are in the range 1.5 – 25 m/s. Compared with the AODV and DSDV, DSR demonstrates the lowest RPO for all mobility
ISSN: 1790-5109
275 ISBN: 978-960-474-107-6
RPO RPO
RPO RPO
Proceedings of the 9th WSEAS International Conference on APPLIED INFORMATICS AND COMMUNICATIONS (AIC ’09)
models. This happens because DSR uses caching; hence it is more likely to find a route in cache and perform the route discovery less frequently than with AODV. On the other side, DSDV periodically transmits updates to maintain routing tables. There are also event triggered routing table exchanges through incremental dumps. This exchange is mostly present in case of higher mobility. Continuous updates contribute to a relatively stable RPO, irrespective of node speed.
With AODV, RPO considerably varies depending on the node speed. AODV performs better than DSDV at the lowest speed level because it is on-demand protocol. For higher speeds, there are more route changes and AODV has to generate more routing packets than DSDV.
When nodes are moving fast there is higher rate of disconnections, which produces more route errors and frequent needs for re-initialization of route discovery process. Due to restriction of the node movement, this problem is most obvious in the case of MG model.
RPGM and RW have similar RPO performance while in the case of GM, when speeds reach 5m/s, AODV protocol suffers from highest RPO as the topology changes are very frequent. In that case AODV produces more routing messages compared to other two protocols.
5 Conclusion
This paper studied performance of the three widely used MANET routing protocols (DSDV, AODV and DSR) with respect to group (RPGM) and entity (RW, GM and MG) mobility models. We have developed a set of simulation scripts for the NS2 simulation environment merged with the BonnMotion scenario generation tools.
Simulation results have indicated that the relative ranking of routing protocols may vary depending on mobility model. The relative ranking also depends on the node speed as the presence of the mobility implies frequent link failures and each routing protocol reacts differently during link failures.
The proactive protocol DSDV experiences the most stable performance with all mobility models. This protocol performs best with entity models that have lower level of randomness (GM and, particularly, MG).
AODV performs best with the group model RPGM. With entity models, AODV experiences the highest routing overhead with the increase of node speed, but has acceptable average delays.
DSR experiences the lowest routing protocol overhead, on the count of higher average delays, particularly with MG and GM models, at higher node speeds. This protocol performs best with the RW model. Future work should be focused to extending set of the experiments by taking into consideration energy-consumption reduction, different propagation models and MAC protocols.
Acknowledgement
This paper has been partially financed by Serbian Ministry of Science (R&D project TR 11002).
References:
[1] S. Sesay et al., “Simulation Comparison of Four Wireless Ad Hoc Routing Protocols”, Information Technology Journal 3(3), 2004, pp: 219-226.
[2] S. Shah et al, “Performance Evaluation of Ad Hoc Routing Protocols Using NS2 Simulation”, Conf. of Mobile and Pervasive Computing, 2008
[3] G. Jayakumar, G. Gopinath, “Performance Comparison of MANET Protocol Based on Manhattan Grid Model”, Journal of Mobile Communications, vol. 2, no. 1, pp. 18-26, 2008.
[4] M. K. Jeya Kumar, R.S. Rajesh, “A Survey of MANET Routing Protocols in Mobility Models”, Int. Journal of Soft Computing 4(3), 2009, pp. 136-141.
[5] Sham-ul-Arfeen et al, “Performance Evaluation of MANET Routing Protocols Using Scenario Based Mobility Models”, Innovative Algorithms and Techniques in Automation, Industrial Electronics and Telecommunications, Springer, 2007. pp. 419-424.
[6] B. Divecha et al, “Impact of Node Mobility on MANET Routing Protocols Models”, Journal of Digital Information Management, February 2007.
[7] T. Camp et al., “A Survey of Mobility Models for Ad Hoc Network Research”, Wireless Comm. & Mobile Computing: Special issue on Mobile Ad Hoc Networking: Research, Trends and Applications, vol. 2, pp. 483-502, 2002.
[8] Network Simulator NS2 and Network Animator NAM. [Online]. Available:
http://www.isi.edu/nsnam.
[9] M. Gerharz, C. de Waal, “BonnMotion – a
mobility scenario generation tool”, University of Bonn, [Online]. Available:
www.cs.uni-bonn.de/IV/BonnMotion/.
[10]J. Malek, “Trace Graph – NS Trace Files
Analyzer”, 2003. [Online]. Available: http://www.geocites.com/tracegraph.
ISSN: 1790-5109
276 ISBN: 978-960-474-107-6