Impact of node mobility on MANET routing protocols models.
Categories and Subject Descriptors
C.2.1[Network Architecture and Design]; Wirelss communication: C.2.2[Network Protocols];Routing protocols:
Mobile networks, Network protocol, Wireless networks
Key words: Mobile adhoc networks, MANET, Mobility models
A Mobile Ad-Hoc Network (MANET) is a self-configuring network of mobile nodes connected by wireless links, to form an arbitrary topology. The nodes are free to move randomly. Thus the network's wireless topology may be unpredictable and may change rapidly. Minimal configuration, quick deployment and absence of a central governing authority make ad hoc networks suitable for emergency situations like natural disasters, military conflicts, emergency medical situations etc  . Many previous studies have used Random Waypoint as reference model  . However, in future MANETs are expected to be used in various applications with diverse topography and node configuration. Widely varying mobility characteristics are expected to have a significant impact on the performance of the routing protocols like DSR and DSDV. The overall performance of any wireless protocol depends on the duration of interconnections between any two nodes transferring data as well on the duration of interconnections between nodes of a data path containing n-nodes. We will call these parameters averaged over entire network as "Average Connected Paths".
The mobility of the nodes affects the number of average connected paths, which in turn affect the performance of the routing algorithm. We have also studied the impact of node density on routing performance. With very sparsely populated network the number of possible connection between any two nodes is very less and hence the performance is poor. It is expected that if the node density is increased the throughput of the network shall increase, but beyond a certain level if density is increased the performance degrades in some protocol. We have also studied the effect of number of hops on the protocol performance    .
[FIGURE 1 OMITTED]
2. Description of Routing Protocol
A. Destination-Sequenced Distance-Vector (DSDV)
Destination-Sequenced Distance-Vector Routing protocol is a proactive table driven algorithm based on classic Bellman-Ford routing. In proactive protocols, all nodes learn the network topology before a forward request comes in. In DSDV protocol each node maintains routing information for all known destinations. The routing information is updated periodically. Each node maintains a table, which contains information for all available destinations, the next node to reach the destination, number of hops to reach the destination and sequence number. The nodes periodically send this table to all neighbors to maintain the topology, which adds to the network overhead. Each entry in the routing table is marked with a sequence number assigned by the destination node. The sequence numbers enable the mobile nodes to distinguish stale routes from new ones, there by avoiding the formation of routing loops .
B. Dynamic Source Routing (DSR)
Dynamic Source Routing protocol is a reactive protocol i.e. it determines the proper route only when a packet needs to be forwarded. The node floods the network with a route-request and builds the required route from the responses it receives. DSR allows the network to be completely self-configuring without the need for any existing network infrastructure or administration. The DSR protocol is composed of two main mechanisms that work together to allow the discovery and maintenance of source routes in the ad hoc network. All aspects of protocol operate entirely on-demand allowing routing packet overhead of DSR to scale up automatically.
Route Discovery: When a source node S wishes to send a packet to the destination node D, it obtains a route to D. This is called Route Discovery. Route Discovery is used only when S attempts to send a packet to D and has no information on a route to D.
Route Maintenance: When there is a change in the network topology, the existing routes can no longer be used. In such a scenario, the source S can use an alternative route to the destination D, if it knows one, or invoke Route Discovery. This is called Route Maintenance  .
3. Mobility Models
Different mobility models can be differentiated according to their spatial and temporal dependencies.
Spatial dependency: It is a measure of how two nodes are dependent in their motion. If two nodes are moving in same direction then they have high spatial dependency.
Temporal dependency: It is a measure of how current velocity (magnitude and direction) are related to previous velocity. Nodes having same velocity have high temporal dependency. Given below are the descriptions of four mobility models with detailed explanation for how they emulate real world scenario. NAM is a graphical simulation display tool. It has a GUI similar to that of a CD player (play, fast forward, rewind, pause and so on), and also has a display speed controller. All the simulations are performed on Network Simulator Version 2.27 which generates an output NAM file.
A. Random Waypoint
The Random Waypoint model is the most commonly used mobility model in research community. At every instant, a node randomly chooses a destination and moves towards it with a velocity chosen randomly from a uniform distribution [0,V_max], where V_max is the maximum allowable velocity for every mobile node. After reaching the destination, the node stops for a duration defined by the 'pause time' parameter. After this duration, it again chooses a random destination and repeats the whole process until the simulation ends. Figure 2 illustrates examples of a topography showing the movement of nodes for Random Mobility Model.
[FIGURE 2 OMITTED]
B. Random Point Group Mobility (RPGM)
Random point group mobility can be used in military battlefield communication. Here each group has a logical centre (group leader) that determines the group's motion behavior. Initially each member of the group is uniformly distributed in the neighborhood of the group leader. Subsequently, at each instant, every node has speed and direction that is derived by randomly deviating from that of the group leader. Given below is example topography showing the movement of nodes for Random Point Group Mobility Model. The scenario contains sixteen nodes with Node 1 and Node 9 as group leaders.
Important Characteristics: Each node deviates from its velocity (both speed and direction) randomly from that of the leader. The movement in group mobility can be characterized as follows:
[absolute value of [V.sub.member] (t)] = [absolute value of [V.sub.leader] (t)] + random () x SDR x max_speed (1)
[absolute value of [e.sub.member] (t)] = [absolute value of [e.sub.leader] (t)] + random () x ADR x max_angle (2)
where 0 <<ADR, SDR<< 1. SDR is the Speed Deviation Ratio and ADR is the Angle Deviation Ratio. SDR and ADR are used to control the deviation of the velocity (magnitude and direction) of group members from that of the leader. Since the group leader mainly decides the mobility of group members, group mobility pattern is expected to have high spatial dependence for small values of SDR and ADR .
[FIGURE 3 OMITTED]
C. Freeway Mobility Model
This model emulates the motion behavior of mobile nodes on a freeway. It can be used in exchanging traffic status or tracking a vehicle on a freeway. Each mobile node is restricted to its lane on the freeway. The velocity of mobile node is temporally dependent on its previous velocity.
Given below is example topography showing the movement of nodes for Freeway Mobility Model with thirteen nodes.
[FIGURE 4 OMITTED]
Important Characteristics: In this model we use maps. There are several freeways on the map and each freeway has lanes in both directions. The differences between Random Waypoint and Freeway are the following:
(a) Each mobile node is restricted to its lane on the freeway.
(b) The velocity of mobile node is temporally dependent on its previous velocity. Formally,
[absolute value of [V.sub.i] (t+1)] = [absolute value of [V.sub.i] (t)] + random () x [absolute value of [a.sub.i] (t)] (3)
(c) If two mobile nodes on the same freeway lane are within the Safety Distance (SD), the velocity of the following node cannot exceed the velocity of preceding node.
Formally, [[for all].sub.i], [[for all].sub.j], [[for all].sub.t], [D.sub.ij](t) < SD [??] [absolute value of [V.sub.i](t)] < [absolute value of [V.sub.j](t)] (4)
if j is ahead of i in its lane.
Due to the above relationships, the Freeway mobility pattern is expected to have high spatial dependence and high temporal dependence. It also imposes strict geographic restrictions on the node movement by not allowing a node to change its lane.
D. Manhattan Mobility Model
We introduce the Manhattan model to emulate the movement pattern of mobile nodes on streets. It can be useful in modeling movement in an urban area. The scenario is composed of a number of horizontal and vertical streets.
Given below is example topography showing the movement of nodes for Manhattan Mobility Model with seventeen nodes. The map defines the roads along the nodes can move.
[FIGURE 5 OMITTED]
Important Characteristics: Maps are used in this model too. However, the map is composed of a number of horizontal and vertical streets. The mobile node is allowed to move along the grid of horizontal and vertical streets on the map. At an intersection of a horizontal and a vertical street, the mobile node can turn left, right or go straight with certain probability. Except the above difference, the inter-node and intra-node relationships involved in the Manhattan model are the same as in the Freeway model. It too imposes geographic restrictions on node mobility. 
4. Simulation and Results
A. Scenario for Different Speed in Mobility Models
We have compared the performance of DSDV and DSR for different mobility models namely (Random Waypoint, Freeway, RPGM and Manhattan) in terms of data rate (Bytes per second) for varying speeds . The routing protocol used for the simulation is available with NS-2 (version 2.27). For each of these scenarios, movements were generated using a software called Mobility Generator  which is based on a frame work called Important (Impact of Mobility Patterns On Routing in Ad-hoc NeTworks, from University of Southern California) which upon inputs of number of nodes, mobility model and scale (area) generates the TCL script for mobility. Background traffic, using TCL script is also employed along with the traffic, which we have monitored. Standard 802.11 MAC layer was used and transmission range in each simulation was 250 mtr. All the nodes in simulation had omni directional antennas. Standard CMUPri model for queue of buffer size 50 was used. Simulation had 40 nodes and is run for 500 secs. Flat 1000x1000 mtr scenario was created in all the mobility cases except for Freeway Model where the scenario is of 20000x2000. No motion in z-direction was allowed thus whole topology was two-dimensional. Trace generated was User Datagram.
Protocol (UDP) type trace. Using UDP, programs on networked computers can send short messages known as datagrams to one another. UDP does not provide the reliability and ordering of datagrams. For each of the mobility models we have varied the maximum allowed velocity (Vmax) and obtained averaged throughput.
In Random Waypoint mobility is defined as Vmax. Thus scenario having higher Vmax is highly mobile. To calculate the performance, 10 data connections are monitored and averaged.
In RPGM mobility model mobility is defined as Vmax of leader's, because the leader is highly mobile, other nodes in the group are spatially and temporally correlated to the motion of the leader. In RPGM four groups were formed randomly with 10 nodes each. Randomly one node in each group was elected as leader. All the nodes in the group remain within 100 mtr radius the leader. To calculate the performance, 10 data connections are monitored and averaged, irrespective of group membership.
In Freeway mobility model the mobility is defined as maximum allowed velocity of medium lane and fast and slow lane velocity +10 mtr/sec and -10 mtr/sec of medium lane velocity. Thus increasing velocity of middle lane the velocity of whole scenario can be increased. Initially all the nodes were distributed randomly in all the three lanes. To calculate the performance, 10 data connections are monitored and averaged.
In case of Manhattan mobility model each node can have any velocity from 0 to Vmax and moves with this velocity whole time thus Vmax is defined as mobility parameter of the scenario. To calculate the performance, 10 data connections are monitored and averaged.
B. Scenario for Different Number of Nodes
Performance of DSDV and DSR is also tested in terms of data rate (Bytes per second) for different number of nodes in the system, namely (20, 40, 60, 80, 100) nodes. The mobility model selected in this scenario is Random Waypoint and background traffic is also added. Standard 802.11 MAC layer was used and transmission range in each simulation was 250 mtr. All the nodes in simulation had omni directional antennas. Standard CMUPri model for queue of buffer size 50 was used. Simulation has varying number of nodes and is run for 500 secs. Flat 700x700 mtr scenario was created in all the mobility cases. No motion in z-direction was allowed thus whole topology was two-dimensional. Trace generated was UDP type trace.
C. Scenario for Different Number of Hops
As it is very difficult to predict exact number of hops the route will take, we have compared the performances of DSDV and DSR in terms of data rate (bytes per second) and averaged it for less than 5 hops and more than 5 hops. We have used Random Mobility model with 50 mobile nodes for this comparison. In such a scenario, maximum number hops for any data path is around 10. If we consider a larger scenario with higher number of nodes then we can compare the performance for an even higher number of hops. Standard 802.11 MAC layer was used and transmission range in each simulation was 250 mtr. All the nodes in simulation had omni directional antennas. Standard CMUPri model for queue of buffer size 50 was used. Simulation is run for 500 secs in all the cases.
We have randomly considered various connections, some of which are below 5 hops and others are above 5 hops and averaged the throughput thus obtained. Flat 1600x1600 mtr scenario was created with 50 mobile nodes with V_max as 20 mtr/sec. No motion in z - direction was allowed thus whole topology was two-dimensional. The Trace generated was UDP type trace.
5. Experiment Results and Discussions
A. Random Waypoint mobility model:
[FIGURE 6 OMITTED]
B. Random Point Group Mobility:
[FIGURE 7 OMITTED]
C. Freeway mobility model:
[FIGURE 8 OMITTED]
D. Manhattan mobility model:
[FIGURE 9 OMITTED]
E. DSR Vs DSDV for different number of nodes
[FIGURE 10 OMITTED]
A. Performance of DSR and DSDV for varying speed on different mobility models
In all the four mobility models we have increased the mobility and recorded the performance. We did this simulation for 500 secs with 10 udp connections. Readings were taken for different mobility (Max speed 10, 20, 30, 40, 50 mtrs/sec). The total throughput of the system was averaged. From the results it is evident that as the mobility increases; the performance of both DSR and DSDV deteriorates. But in all the four cases, DSR performs better then DSDV. High mobility nature suggests that rather looking for a shorter path in routing, we must stress on more stable path to reduce overheads.
B. Performance of DSR and DSDV for varying node density: In our simulation for varying number of nodes we can see that performance of DSR is much better than DSDV. We did this simulation for 300 secs with 6 udp connections. From the results it is clear that when number of nodes in our scenario is very low (sparse topology) , the performance is poor (low throughput, high packet losses) because there are less number of connections due to sparse nature of topology. As the number of nodes is increased the performance becomes more or less constant but if density is too large, more and more of nodes try to access the common medium, thus number of collisions increase thereby increasing packet loss and decreasing the throughput. DSR performs better than DSDV because of its adaptive nature. Also from the graph we can see that performance of DSR does not deteriorate too much even after increase in number of nodes.
C. Performance of DSR and DSDV for varying number of hops:
In our simulation for varying number of hops, we see that the performance of DSDV deteriorates very badly for higher number of hops. But performance of DSR is much better than DSDV for both the cases considered. Here the maximum number of hops for any data path is nine. If we consider a larger scenario with higher number of nodes then we can compare performance for larger routes (higher hops). From the results we can see that if we compare the performance for higher number hops it will deteriorate in both the cases but much faster in case of DSR than DSDV. Route maintenance is much better in DSR as compared to DSDV. The reduction in performance may be attributed to link breakage, which is more probable as the length of the route increases. In case of DSDV re-establishment of new routes does not take place till there is a route table information packet coming from its neighbor nodes. But in case of DSR, when route breakage takes place, packets are cached and route repair takes place. This improves the overall through put of the system.
6. Conclusions and Future Work
Empirical results illustrate that the performance of a routing protocol varies widely across different mobility models and hence the study results from one model cannot be applied to other model. Hence we have to consider the mobility of an application while selecting a routing protocol. DSR gives better performance for highly mobile networks than DSDV. DSR is faster in discovering new route to the destination when the old route is broken as it invokes route repair mechanism locally whereas in DSDV there is no route repair mechanism. In DSDV, if no route is found to the destination, the packets are dropped.
Future study should be conducted to compare protocols in low mobility environment, where routes do not break to too often. Proactive protocols may give better performance for near stable environment. Performance of other routing protocol can be evaluated over various mobility models taking in to consideration number of average connected paths to gain greater insights into the relationship between them. Designing scenarios which depict real world applications more accurately can be designed through in-depth study of the application.
Received 17 November 2006; Revised and accepted 27 Jan. 2007
 Corson, S., Macker, J (1999). Mobile Ad hoc Networking (MANET): Routing Protocol Performance Issues and Evaluation Considerations, RFC: 2501.
 Kopp, Carlo (1999) Ad Hoc Networking, Systems Journal, 33-40.
 Lin, Guolong., Noubir, Guevara., Rajaraman, Rajmohan (2004). Mobility Models for Ad hoc Network Simulation, In: Proceedings of IEEE INFOCOM 2004, Volume 1, p. 7-11.
 Camp, Tracy., Boleng, Jeff ., Davies, Vanessa (2002). A Survey of Mobility Models for Ad Hoc Network, Special issue on Mobile Ad Hoc Networking: Research, Trends and Applications, 2 (5) 483-50 .
 Bai, F., Helmy, A (2004). The IMPORTANT Framework for Analyzing and Modeling the Impact of Mobility in Wireless Adhoc Networks, In: Wireless Ad Hoc and Sensor Networks, Kluwer Academic Publishers.
 Bai, F., Helmy, A (2004). A Survey of Mobility Modeling and Analysis In: Wireless Adhoc Networks, Kluwer Academic Publishers.
 Bai, F., Bhaskara, G., Helmy, A (2004). Building the Blocks of Protocol Design and Analysis--Challenges and Lessons Learned from Case Studies on Mobile Adhoc Routing and Micro-Mobility Protocols, ACM Computer Communication Review 34 (3) 57-70.
 Bai, F., Sadagopan, N., Helmy, A (2003). IMPORTANT: A framework to systematically analyze the Impact of Mobility on Performance of Routing protocols for Adhoc Networks, IEEE INFOCOM, p. 825-835.
 Perkins, Charles E., Bhagwat, Pravin (1994). Highly Dynamic Destination Sequenced Distance Vector Routing (DSDV) for Mobile Computers", SIGCOMM 94, p. 234-244.
 Johnson, David B., Maltz, David. A., Hu, Yih-Chun (2004).The Dynamic Source Routing (DSR) Protocol for Mobile Ad Hoc Networks.draft-ietf-manet-dsr-10.txt, July 2004
 Johnson, David B., Maltz, David. A (1996). "Dynamic Source Routing in Ad Hoc Wireless Networks". In: Mobile Computing, edited by Tomasz Imielinski and Hank Korth, Chapter 5, pages 153-181, Kluwer Academic Publishers.
 Zhou, Biao., Xu, Kaixin., Gerla, Mario (1994). Group and Swarm Mobility Models for Ad Hoc Network Scenarios Using Virtual Tracks, In: Proceedings of MILCOM'2004, Volume 1, p. 289- 294.
 User Manual for IMPORTANT Mobility Tool Generator in NS-2 Simulator. http://nile.usc.edu/important/software.htm , Release Date: February 2004
 Mobility Generator (version 1.0) from the site, http:// nile.usc.edu/important/software.htm, February 2004
Bhavyesh Divecha (1), Ajith Abraham (2), Crina Grosan (2), Sugata Sanyal (3)
(1) Mumbai University Mumbai India. firstname.lastname@example.org
(2) Centre for Quantifiable Quality of Service in Communication Systems Norwegian University of Science and Technology Norway. email@example.com, firstname.lastname@example.org
(3) School of Technology and Computer Science Tata Institute of Fundamental Research India. email@example.com
Bhavyesh Divecha is currently working with TATA Consultancy Services Limited, India. He did Bachelor in Computers Engineering from Veermata Jijabai Technological Institute, Mumbai University, India. His research interests include Security and Performance in Wireless and Distributed Processing.
Ajith Abraham is currently a Visiting Professor in the Centre for Quantifiable Quality of Service in Communication Systems, Norwegian University of Science and Technology, Norway. His primary research interests are in computational intelligence with a focus on using evolutionary computation techniques for designing intelligent paradigms. Application areas include network security, Web services, Web intelligence, financial modeling, multi criteria decision-making, data mining etc. He has authored/co-authored over 250 research publications in peer reviewed reputed journals, book chapters and conference proceedings of which five have won 'best paper' awards. He is an associate editor of the Journal of Digital information Management (JDIM) and also serves the editorial board of over a dozen International Journals and has also guest edited 18 special issues for reputed International Journals. Since 2001, he is actively involved in the Hybrid Intelligent Systems (HIS) the Intelligent Systems Design and Applications (ISDA) series of International conferences. During the last five years, he has also served the technical committee of over 100 International conferences and has also given a number of conference tutorials/plenary lectures. He is a senior member of IEEE and IEEE (CS) and a member of ACM, IEE (UK), IEAust and also works closely with several academic working groups like EvoNet, EUSFLAT, WFSC, etc. He received PhD degree from Monash University, Australia. More information at: http://www.softcomputing.net
Dr. Crina Grosan is currently a Research fellow in the Centre for Quantifiable Quality of Service in Communication Systems, Norwegian University of Science and Technology, Norway. She is also an Assistant Professor in the Computer Science Department of Babes-Bolyai University, Cluj-Napoca, Romania. She received PhD degree from Babes-Bolyai University, Romania. Her main research area is in Evolutionary Computation, with a focus on Evolutionary Multiobjective Optimization and Genetic Programming. She is also interested in Swarm Intelligence (Particle Swarm Optimization, Ant Colonies Systems), Bioinformatics, Financial Modeling, etc. Crina Grosan authored/co-authored over 70 papers in peer reviewed international journals, proceedings of the international conferences and book chapters. She is co-author of two books in programming languages. She is the Managing Editor of the International Journal of Computational Intelligence Research (IJCIR). Dr. Grosan is the co-editor for two books titled Swarm Intelligence in Data Mining, Stigmergic Optimization Hybrid Evolutionary Systems, which is published by published by Springer Verlag, Germany. She is currently editing two new books titled Hybrid Evolutionary Systems and Engineering Hybrid Evolutionary Systems, which will be also published by Springer Verlag, Germany.
Sugata Sanyal is in the Faculty of the School of Technology & Computer Science at the Tata Institute of Fundamental Research, India. He received his Ph.D. degree from Mumbai University, India, M. Tech. from IIT, Kharagpur, India and B.E. from Jadavpur University, India. His current research interests include Multi-Factor Security Issues, Security in Wireless and Mobile Ad Hoc Networks, Distributed Processing, and Scheduling techniques. He has published numerous papers in national and international journals and attended many conferences. He is in the editorial board of four International Journals. He is co-recipient of Vividhlaxi Audyogik Samsodhan Vikas Kendra Award (VASVIK) for Electrical and Electronics Science and Technologies (combined) for the year 1985. He was a Visiting Professor in the Department of Electrical and Computer Engineering and Computer Science in the University of Cincinnati, Ohio, USA in 2003. He delivered a series of lectures and also interacted with the Research Scholars in the area of Network Security in USA, in University of Cincinnati, University of Iowa, Iowa State University and Oklahoma State University. He has been an Honorary Member of Technical Board in UTI (Unit Trust of India), SIDBI (Small Industries Development Bank of India) and Coal Mines Provident Funds Organization (CMPFO). He has also been acting as a consultant to a number of leading industrial houses in India. More information about his activities is available at http://www.tifr.res.in/~sanyal
Table 1. Variation in UDP throughput with increase in number of hops for Random Waypoint Mobility model F. DSR Vs DSDV for different number of hops DSR DSDV (Bytes per Unit Time) (Bytes Per Unit Time) Less than 5 Hops 254.08 123.84 More than 5 Hops 193.92 24.96 (less than 9)
|Printer friendly Cite/link Email Feedback|
|Title Annotation:||Mobile Ad-Hoc Network|
|Author:||Divecha, Bhavyesh; Abraham, Ajith; Grosan, Crina; Sanyal, Sugata|
|Publication:||Journal of Digital Information Management|
|Date:||Feb 1, 2007|
|Previous Article:||A robust outlier detection scheme for collaborative sensor networks.|
|Next Article:||Indexing an intelligent video database using evolutionary control.|