MOBILITY MODELS IN ADHOC NETWORKS

S; eep Kaur; Harpreet Singh; Taranjit Singh; Yadvinder Singh

MOBILITY MODELS IN ADHOC NETWORKS

Sandeep Kaur^*1, Harpreet Singh²and Taranjit Singh³, Yadvinder Singh⁴

CSE, BGIET, Sangrur, Punjab, India
CSE, BGIET, Sangrur, Punjab, India
CSE, BGIET, Sangrur, Punjab, India
CSE, BGIET, Sangrur, Punjab, India

Corresponding Author: Sandeep Kaur, E-mail: sandeepk_327@yahoo.co.in

Related article at Pubmed, Scholar Google

Visit for more related articles at Journal of Global Research in Computer Sciences

Abstract

In Ad-hoc wireless networks, mobility management faces many challenges. Mobility of the nodes causes the network topology to change. The routing protocols must dynamically re-adjust to these changes in order to keep the accurate routes. Therefore, the routing updates traffic overhead is very much high. Generally, different types of mobility patterns have different impact on the network protocols or applications. Thus, the network performance is strongly affected by the nature of mobility pattern. In this paper, we present a survey of various mobility models in ad-hoc networks. One of the main purpose of this paper is to investigate the impact of the mobility model on the performance of a specific network protocol or application. The results indicate that different mobility patterns affect the various protocols in different ways. Specifically, the ranking of routing algorithms is influenced by the choice of mobility pattern.

INTRODUCTION

Research has gained a significant advance in the development of routing protocols for wireless ad hoc networks[1], [2].A manet consists of a number of mobile devices that come together to form a network as needed, without any support from any existing Internet infrastructure or any other kind of fixed stations. Formally, a manet can be defined as an autonomous system of nodes or MSs (also serving as routers connected by wireless links, the union of which forms a communication network modeled in the form of an arbitrary communication graph. In such environment, Neighbor nodes communicate directly with each others while communication between non-neighbor nodes performed via the intermediate nodes which act as routers.

As the network topology changes frequently because of node mobility and power limitations, efficient routing protocols are necessary to organize and maintain communication between the nodes. In order to thoroughly simulate a new protocol for an ad hoc network, it is imperative to use a mobility model that accurately represents the mobile nodes (MNs) that will eventually utilize the given protocol. Only in this type of scenario is it possible to determine whether or not the proposed protocol will be useful when implemented. Currently there are two types of mobility models used in the simulation of networks: traces and synthetic models. Traces are those mobility patterns that are observed in real life systems. Traces provide accurate information, especially when they involve a large number of participants and an appropriately long observation period [3]. However, new network environments (e.g. ad hoc networks) are not easily modeled if traces have not yet been created. In this type of situation it is necessary to use synthetic models. Synthetic models attempt to realistically represent the behaviors of MNs without the use of traces.

In this paper, we present several synthetic mobility models that have been proposed for (or used in) the performance evaluation of ad hoc network protocols. A mobility model should attempt to mimic the movements of real MNs. Changes in speed and direction must occur and they must occur in reasonable time slots. For example, we would not want MNs to travel in straight lines at constant speeds throughout the course of the entire simulation because real MNs would not travel in such a restricted manner.

The mobility model is designed to describe the movement pattern of mobile users, and how their location, velocity and acceleration change over time [4]. Since mobility patterns may play a significant role in determining the protocol performance, it is desirable for mobility models to emulate the movement pattern of targeted real life applications in a reasonable way. Otherwise, the observations made and the conclusions drawn from the simulation studies may be misleading. Thus, when evaluating MANET protocols, it is necessary to choose the proper underlying mobility model. For example, the nodes in Random Waypoint model behave quite differently as compared to nodes moving in groups. It is not appropriate to evaluate the applications where nodes tend to move together using Random Waypoint model. Therefore, there is a real need for developing a deeper understanding of mobility models and their impact on protocol performance.

One intuitive method to create realistic mobility patterns would be to construct trace-based mobility models, in which accurate information about the mobility traces of users could be provided. However, since MANETs have not been implemented and deployed on a wide scale, obtaining real mobility traces becomes a major challenge. Therefore, various researchers proposed different kinds of mobility models, attempting to capture various characteristics of mobility and represent mobility in a somewhat 'realistic' fashion. Much of the current research has focused on the so-called synthetic mobility models that are not trace-driven.

In the previous studies on mobility patterns in wireless cellular networks, researchers mainly focus on the movement of users relative to a particular area (i.e., a cell) at a macroscopic level, such as cell change rate, handover traffic and blocking probability. However, to model and analyze the mobility models in MANET, we are more interested in the movement of individual nodes at the microscopic-level, including node location and velocity relative to other nodes, because these factors directly determine when the links are formed and broken since communication is peer-to-peer.

LITERATURE SURVEY

The Mobility Models are mainly categorized into four parts as per shown in the diagram drawn below. A categorization for various mobility models into several classes based on their specific mobility characteristics is provided. For some mobility models, the movement of a mobile node is likely to be affected by its movement history. This type of mobility model is referred as mobility model with temporal dependency. In some mobility scenarios, the mobile nodes tend to travel in a correlated manner. Such type of mobility models are known as mobility models with spatial dependency. Another class is the mobility model with geographic restriction, where the movement of nodes is bounded by streets, freeways or obstacles. The various categories [4] of mobility models are shown below:

One frequently used mobility model in MANET simulations is the Random Waypoint model, in which nodes move independently to a randomly chosen destination with a randomly selected velocity. The simplicity of Random Waypoint model may have been one reason for its widespread use in simulations. However, MANETs may be used in different applications where complex mobility patterns exist. Hence, recent research has started to focus on the alternative mobility models with different mobility characteristics. In these models, the movement of a node is more or less restricted by its history, or other nodes in the neighborhood or the environment.

RANDOM-BASED MOBILITY MODELS

In random-based mobility models, the mobile nodes move randomly and freely without restrictions [5]. To be more specific, the destination, speed and direction are all chosen randomly and independently of other nodes. This kind of model has been used in many simulation studies.

The Random Waypoint Model:

The Random Waypoint Model was first proposed by Johnson and Maltz. Soon, it became a 'benchmark' mobility model to evaluate the MANET routing protocols, because of its simplicity and wide availability. To generate the node trace of the Random Waypoint model the setdest tool from the CMU Monarch group may be used. This tool is included in the widely used network simulator ns-2.

As the simulation starts, each mobile node randomly selects one location in the simulation field as the destination. It then travels towards this destination with constant velocity chosen uniformly and randomly from [0,Vmax], where the parameter Vmax is the maximum allowable velocity for every mobile node. The velocity and direction of a node are chosen independently of other nodes. Upon reaching the destination, the node stops for a duration defined by the ‘pause time’ parameter Tpause. If Tpause=0, this leads to continuous mobility. After this duration, it again chooses another random destination in the simulation field and moves towards it. The whole process is repeated again and again until the simulation ends.

In the Random Waypoint model, Vmax and Tpause are the two key parameters that determine the mobility behavior of nodes. If the Vmax is small and the pause time Tpause is long, the topology of Ad Hoc network becomes relatively stable. On the other hand, if the node moves fast (i.e., is large) and the pause time Tpause is small, the topology is expected to be highly dynamic.

Random Walk Model:

The Random Walk model was originally proposed to emulate the unpredictable movement of particles in physics. It is also referred to as the Brownian Motion[6]. Because some mobile nodes are believed to move in an unexpected way, Random Walk mobility model is proposed to mimic their movement behavior. The Random Walk model has similarities with the Random Waypoint model because the node movement has strong randomness in both models. We can think the Random Walk model as the specific Random Waypoint model with zero pause time.

The Random Walk model is a memory-less mobility process where the information about the previous status is not used for the future decision. That is to say, the current velocity is independent with its previous velocity and the future velocity is also independent with its current velocity.

Random Direction Model:

In line with the observation that distribution of movement angle is not uniform in Random Waypoint model, the Random Direction model based on similar intuition is proposed by Royer, Melliar-Smith and Mose[7]r. This model is able to overcome the non-uniform spatial distribution and density wave problems. Instead of selecting a random destination within the simulation field, in the Random Direction model the node randomly and uniformly chooses a direction by which to move along until it reaches the boundary. After the node reaches the boundary of the simulation field and stops with a pause time Tpause, it then randomly and uniformly chooses another direction to travel. This way, the nodes are uniformly distributed within the simulation field.

Another variant of the Random Direction model is the Modified Random Direction model that allows a node to stop and choose another new direction before it reaches the boundary of the simulation field. For both versions of

Random Direction model, Royer, Melliar-Smith and Moser report that the Random Direction model incurs less fluctuation in node density than the Random Waypoint model.

MOBILITY MODELS WITH TEMPORAL DEPENDENCY

Mobility of a node may be constrained and limited by the physical laws of acceleration, velocity and rate of change of direction. Hence, the current velocity of a mobile node may depend on its previous velocity. Thus the velocities of single node at different time slots are ‘correlated'. We call this mobility characteristic the Temporal Dependency of velocity.

However, the memoryless nature of Random Walk model, Random Waypoint model and other variants render them inadequate to capture this temporal dependency behavior. As a result, various mobility models considering temporal dependency are proposed like, Gauss-Markov Mobility Model and Smooth Random Mobility Model.

Gauss-Markov Mobility Model:

The Gauss-Markov Mobility Model was first introduced by Liang and Haas[8] and widely utilized[9]. In this model, the velocity of mobile node is assumed to be correlated over time and modeled as a Gauss-Markov stochastic process. It creates movements which are dependent on node’s current speed and direction. The idea is to eliminate the sharp and sudden turns present in the Random Walk and Random Waypoint even by keeping a certain degree of randomness. At fixed intervals of time n new direction dn and speed sn are chosen as:

In the Gauss-Markov model, the temporal dependency plays a key role in determining the mobility behavior.

MOBILITY MODELS WITH SPATIAL DEPENDENCY

In the Random Waypoint model and other random models, a mobile node moves independently of other nodes, i.e., the location, speed and movement direction of mobile node are not affected by other nodes in the neighborhood. Therefore, the mobility of mobile node could be influenced by other neighboring nodes. Since the velocities of different nodes are 'correlated' in space, thus we call this characteristic as the Spatial Dependency of velocity. Various mobility models that falls in this category are like, Reference Point Group Mobility Model[10], a set of spatially correlated mobility models including Column Mobility Model, Pursue Mobility Model and Nomadic Community Mobility Model.

Reference Point Group Mobility Model:

In the RPGM model, each group has a center, which is either a logical center or a group leader node. For the sake of simplicity, we assume that the center is the group leader. Thus, each group is composed of one leader and a number of members. The movement of the group leader determines the mobility behavior of the entire group.

In line with the observation that the mobile nodes in MANET tend to coordinate their movement, the Reference Point Group Mobility (RPGM) Model is proposed. One example of such mobility is that a number of soldiers may move together in a group or platoon. Another example is during disaster relief where various rescue crews (e.g., firemen, policemen and medical assistants) form different groups and work cooperatively.

RPGM model is able to represent various mobility scenarios including:

In-Place Mobility Model: The entire field is divided into several adjacent regions. Each region is exclusively occupied by a single group. One such example is battlefield communication.

Overlap Mobility Model: Different groups with different tasks travel on the same field in an overlapping manner. Disaster relief is a good example.

Convention Mobility Model[11]: This scenario is to emulate the mobility behavior in the conference. The area is also divided into several regions while some groups are allowed to travel between regions.

Column Mobility Model:

The Column Mobility Model represents a set of mobile nodes (e.g., robots) that move in a certain fixed direction. This mobility model can be used in searching and scanning activity, such as destroying mines by military robots. Reference points change:

New_ref_point=Old_ref_point+ advance_vector

When the mobile node is about to travel beyond the boundary of a simulation field, the movement direction is then flipped 180 degree. Thus, the mobile node is able to move towards the center of simulation field in the new direction.

Pursue Mobility Model:

The Pursue Mobility Model emulates scenarios where several nodes attempt to capture single mobile node ahead. This mobility model could be used in target tracking and law enforcement. The node being pursued (i.e., target node) moves freely according to the Random Waypoint model.

When the reference point changes, all MNs in the group travel to the new area defined by the reference point and then begin roaming around the new reference point.

Nomadic Community Mobility model:

The Nomadic Mobility Model is to represent the mobility scenarios where a group of nodes move together. This model could be applied in mobile communication in a conference or military application. The whole group of mobile nodes moves randomly from one location to another. Then, the reference point of each node is determined based on the general movement of this group.

Compared to the Column Mobility Model which also relies on the reference grid, it is observed that the Nomadic Community Mobility Model shares the same reference grid while in Column Mobility Model each column has its own reference point. Moreover, the movement in the Nomadic Community Model is sporadic while the movement is more or less constant in Column Mobility Model.

MOBILITY MODELS WITH GEOGRAPHIC RESTRICTION

In most real life applications, we observe that a node’s movement is subject to the environment. In particular, the motions of vehicles are bounded to the freeways or local streets in the urban area, and on campus the pedestrians may be blocked by the buildings and other obstacles. Therefore, the nodes may move in a pseudo-random way on predefined pathways in the simulation field. Some recent works address this characteristic and integrate the paths and obstacles into mobility models. We call this kind of mobility model a mobility model with geographic restriction.

Pathway Mobility Model:

One simple way to integrate geographic constraints into the mobility model is to restrict the node movement to the pathways in the map. The map is predefined in the simulation field. Tian, Hahner and Becker et al.[12] utilize a random graph to model the map of city. This graph can be either randomly generated or carefully defined based on certain map of a real city. The vertices of the graph represent the buildings of the city, and the edges model the streets and freeways between those buildings.

Initially, the nodes are placed randomly on the edges of the graph. Then for each node a destination is randomly chosen and the node moves towards this destination through the shortest path along the edges. Upon arrival, the node pauses for Tpause time and again chooses a new destination for the next movement. This procedure is repeated until the end of simulation.

Similarly, in the Freeway mobility model and Manhattan mobility model, the movement of mobile node is also restricted to the pathway.

Obstacle Mobility Model:

Another geographic constraint playing an important role in mobility modeling includes the obstacles in the simulation field. To avoid the obstacles on the way, the mobile node is required to change its trajectory. Therefore, obstacles do affect the movement behavior of mobile nodes. Moreover, the obstacles also impact the way radio propagates. For example, for the indoor environment, typically, the radio system could not propagate the signal through obstacles without severe attenuation. For the outdoor environment, the radio is also subject to the radio shadowing effect. When integrating obstacles into mobility model, both its effect on node mobility and on radio propagation should be considered.

COMPARISON OFVARIOUSMOBILITYMODELS

By studying various mobility models, we attempt to conduct a survey of the mobility modeling and analysis techniques in a thorough and systematic manner. Beside the Random Waypoint model and its variants, many other mobility models with unique characteristics such as temporal dependency, spatial dependency or geographic restriction are discussed and studied in this chapter. We believe that the set of mobility models included herein reasonably reflect the state-of-art researches and technologies in this field.

Having examined those mobility models, we observe that the mobility models may have various properties and exhibit different mobility characteristics. As a consequence, we expected that those mobility models behave differently and influence the protocol performance in different ways. Therefore, to thoroughly evaluate ad hoc protocol performance, it is imperative to use a rich set of mobility models instead of single Random Waypoint model. Each model in the set has its own unique and specific mobility characteristics. Hence, a method to choose a suitable set of mobility models is needed.

In IMPORTANT (Impact of Mobility on the Performance Of RouTing protocols in Adhoc NeTworks) framework, the mobility space is viewed as a multi-dimensional space, where each dimension represents a specific and unique mobility characteristic. By properly choosing mobility models with different characteristics, we are able to produce set of various mobility scenarios spanning the mobility space. We list the set of mobility models used in the IMPORTANT framework and their characteristics in Table 1. The performance of an ad hoc network protocol should be evaluated with the mobility model that most closely matches the expected real-world scenario. In fact, the anticipated real-world scenario can aid the development of the ad hoc network protocol significantly. However, since the development of ad hoc networks is relatively new, we do not yet know what a realistic model is for a given scenario.

CONCLUSIONS&FUTURE SCOPE

In this survey paper, various mobility models of mobile adhoc networks are studied. In this section, we illustrate that the choice of a mobility model can have a significant effect on the performance investigation of an ad hoc network protocol. The performance of an ad hoc network protocol can vary significantly when the same mobility model is used with different parameters.

The selection of a mobility model may require a data traffic pattern which significantly influences protocol performance. For instance, if a group mobility model is simulated, then protocol evaluation should be done with a portion of the traffic local to the group. If the expected real-world scenario is unknown, then researchers should make an informed choice about the mobility model to use.

The Column, Nomadic Community, and Pursue Mobility Models are useful group mobility models for specific realistic scenarios. The movement patterns provided by these three mobility models can be obtained by changing the parameters associated with the Reference Point Group Mobility Model. The Reference Point Group Mobility Model (RPGM) is a generic method for handling group mobility. An entity mobility model (or models) needs to be specified to handle both the movement of a group of MNs and the movement of the individual MNs within the group.

In summary, if a group mobility model is desired, it is recommended to use the Reference Point Group Mobility Model with appropriate parameters. If an entity mobility model is desired, either the Random Waypoint Mobility Model, the Random Walk Mobility Model (if clustering in the middle of the simulation area is undesired), or the Gauss-Markov Mobility Model should be used. However, a preferred entity mobility model combines the strengths of the current entity mobility model. Further research on mobility models for ad hoc network protocol evaluation is needed. One avenue of future work is to devote further effort in examining the movements of entities in the real world to produce accurate mobility models. A second avenue is to develop a new model that combines the best attributes of some of the models. A third avenue is to develop a minimum mobility model standard for performance evaluation. This minimum standard would allow us to evaluate different mobility models more thoroughly. Lastly, we should examine the method used to choose a future MN location. In other words, the similarities and differences between mobility models that randomly select directions and mobility models that randomly select specific locations should be analyzed.

References

C. E. Perkins and E. M. Royer. “The ad hoc on-demand distance vector protocol,” Ad Hoc Networking, Addison-Wesley, pp. 173-219, 2001.
D. B. Johnson, D. A. Maltz, and J. Broch, “DSR: the dynamic source routing protocol for multi-hop wireless ad hoc networks,” in Ad Hoc Networking, Addison-Wesley, 2001, pp. 139-172.
Tracy Camp, Jeff Boleng, Vanessa Davies. A survey of mobility for ad hoc network research. Dept. of Math. and Computer Sciences Colorado School of Mines,September 2002. http://reference.kfupm.edu.sa/content/s/u/a_survey_of_mobility_models_for_ad_hoc_n_81745.pdf
F. Bai, N. Sadagopan, A. Helmy, A framework to systematically the impact of mobility on performance of routing protocols for AdHoc networks. IEEE Infocom 2003.
Fan Bai and Ahmed Helmy, A SURVEY OF MOBILITY MODELS in Wireless Adhoc Networks, University of Southern California,U.S.A. http://www.cise.ufl.edu/~helmy/papers/Survey-Mobility-Chapter-1.pdf
Deepanshu Shukla, “Mobility Models in Adhoc Networks”, KReSIT-IIT Bombay, 2001.
E. M. Royer, P. M. Melliar-Smith, and L. E. Moser. An Analysis of the Optimum Node Density for Ad hoc Mobile Networks, in Proceedings of the IEEE International Conference on Communications(ICC), Helsinki, Finland, June 2001.
B. Liang, Z. J. Haas, Predictive Distance-Based Mobility Management for PCS Networks, in Proceedings of IEEE Information Communications Conference (INFOCOM 1999), Apr. 1999.
Y.-C. Hu and D. B. Johnson. Caching Strategies in On-Demand Routing Protocols for Wireless Ad Hoc Networks, in Proceedings of the Sixth Annual International Conference on Mobile Computing and Networking (MobiCom 2000), ACM, Boston, MA, August 2000.
B. Liang, Z. J. Haas, Predictive Distance-Based Mobility Management for PCS Networks, in Proceedings of IEEE Information Communications Conference (INFOCOM 1999), Apr. 1999.
Y.-C. Hu and D. B. Johnson. Caching Strategies in On-Demand Routing Protocols for Wireless Ad Hoc Networks, in Proceedings of the Sixth Annual International Conference on Mobile Computing and Networking (MobiCom 2000), ACM, Boston, MA, August 2000.
J. Tian, J. Hahner, C. Becker, I. Stepanov and K. Rothermel. Graph-based Mobility Model for Mobile Ad Hoc Network Simulation, in the Proceedings of 35th Annual Simulation Symposium, in cooperation with the IEEE Computer Society and ACM. San Diego, California. April 2002.