Mobility models are needed in the design of strategies for location updating and paging, radio resource management (e.g., dynamic channel allocation schemes) and technical network planning and design (e.g., cell and location area layout and network dimensioning). The purpose of mobility models is to describe typical terminal movement so that the analysis for these purposes can be made. Thus, the movement pattern of users plays an important role in performance analysis of mobile and wireless networks, especially in third-generation mobile communications (Jonahing Kim, 2005). Currently, there are two types of mobility models used in the simulation of networks: traces and synthetic models (Camp et al., 2002). 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. 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. 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 (Camp et al., 2002). One frequently used mobility model in Mobile Adhoc Network (MANET) simulations is the Random Waypoint model (Broch et al., 1998), 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. We provide a categorization for Geographic Restriction Mobility Models (GRMM) into three classes based on their specific mobility characteristics as shown in Fig. 1 where the movement of nodes is bounded by streets, freeways or obstacles (Bai and Helmy, 2004). In this model, Mobile Nodes (MNs) can only move along the predefined graph including vertexes and arcs generated based on a real city map. City Section, Freeway, Manhattan, Obstacle and Graph-based Mobility Models belong to this category.
Random waypoint mobility model: In random-based mobility models, the
mobile nodes move randomly and freely without restrictions.
||The categories of geographic restriction mobility models in
mobile Ad hoc network
||Example of node movement in the random waypoint model
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. One frequently used mobility model, the Random Waypoint model. The
Random Waypoint Model became a benchmark mobility model to evaluate the MANET
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.
The Random Waypoint Mobility Model includes pause times between changes in direction
and/or speed. An MN begins by staying in one location for a certain period of
time. Once this time expires, the MN chooses a random destination in the simulation
area and a speed that is uniformly distributed between [minspeed, maxspeed].
The MN then travels toward the newly chosen destination at the selected speed.
Upon arrival, the MN pauses for a specified time period before starting the
process again. Figure 2 shows an example traveling pattern
of an MN using the Random Waypoint Mobility Model starting at a randomly chosen
point or position; the speed of the MN in this figure is uniformly chosen between
minimum and maximum speed (Camp, 2002). In the Random Waypoint model, the speed
and pause time are the two key parameters that determine the mobility behavior
of nodes. If the speed is small and the pause time is long, the topology of
Ad Hoc network becomes relatively stable. On the other hand, if the node moves
fast and the pause time is small, the topology is expected to be highly dynamic.
Varying these two parameters, especially the speed parameter, the Random Waypoint
model can generate various mobility scenarios with different levels of nodal
speed. Therefore, it seems necessary to quantify the nodal speed.
The Random Waypoint model and its variants are designed to mimic the movement of mobile nodes in a simplified way. Because of its simplicity of implementation and analysis, they are widely accepted. However, they may not adequately capture certain mobility characteristics of some realistic scenarios, including temporal dependency, spatial dependency and geographic restriction:
Temporal dependency of velocity: In Random Waypoint and other random models, the velocity of mobile node is a memoryless random process, i.e., the velocity at current epoch is independent of the previous epoch. Thus, some extreme mobility behavior, such as sudden stop, sudden acceleration and sharp turn, may frequently occur in the trace generated by the Random Waypoint model. However, in many real life scenarios, the speed of vehicles and pedestrians will accelerate incrementally. In addition, the direction change is also smooth.
Spatial dependency of velocity: In Random Waypoint and other random models, the mobile node is considered as an entity that moves independently of other nodes. However, in some scenarios including battlefield communication and museum touring, the movement pattern of a mobile node may be influenced by certain specific leader node in its neighborhood. Hence, the mobility of various nodes is indeed correlated.
Geographic restrictions of movement: In Random Waypoint and other random models, the mobile nodes can move freely within simulation field without any restrictions. However, in many realistic cases, especially for the applications used in urban areas, the movement of a mobile node may be bounded by obstacles, buildings, streets or freeways. Random Waypoint model and its variants fail to represent some mobility characteristics likely to exist in Mobile Ad Hoc networks. Thus, several other mobility models were proposed. In the following few sections, we shall discuss those models, according to the classification in Fig. 1(Bai and Helmy, 2004).
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 as following:
City section model: In City Section Mobility Model, the modeled area is a street network that represents a section of a city. All MNs must follow predefined paths and behavior guidelines (e.g., traffic laws). Without regard to obstacles and traffic regulations, MNs do not have the ability to roam freely in the real world. The streets and speed limits on the streets are based on the type of city being simulated. For example, the streets may form a grid in the downtown area of the city with a high-speed highway near the border of the simulation area to represent a loop around the city. Each MN begins the simulation at a defined point on some street and then randomly chooses a destination, which is also predefined by a point on some street. The node travels to a destination through the shortest path between two points. Upon reaching the destination, the node pauses for a specified time, then chooses another destination and repeats the process. This model, as well as the rest of the graph-based models discussed here, does not account for traffic lights or congestion. That is, nodes are allowed to drive through each other (Camp et al., 2002; Kraaier and Killat, 2005).
City map model: Tian et al. (2002) 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. 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 T pause time and again chooses a new destination for the
next movement. This procedure is repeated until the end of simulation.
Unlike the Random Waypoint model where the nodes can move freely, the mobile nodes in this model are only allowed to travel on the pathways. However, since the destination of each motion phase is randomly chosen, a certain level of randomness still exists for this model. So, in this graph based mobility model, the nodes are traveling in a pseudo-random fashion on the pathways. Similarly, in the Freeway mobility model and Manhattan mobility models (Bai et al., 2003), the movement of mobile node is also restricted to the pathway in the simulation field. The freeway map consists of several freeways and each has lanes in both directions. The Manhattan map consists of a number of horizontal and vertical streets forming a grid and each street has two lanes in each direction. At an intersection of a horizontal and a vertical street, the node can turn left with the probability of 0.25, right with 0.25 and go straight with 0.5. The Freeway model does not allow a node to change the lane it is driving in, while the Manhattan model gives a node some freedom to change its direction. Like the City Section Model, these models do not account for inter-node and intra-node relationships in both models. However, these models do not enforce node speed limits. Figure 3 illustrates the maps used for Freeway, Manhattan and Pathway models.
Obstacle mobility model: Obstacle Mobility Model allows a user to define
the positions of obstacles (e.g., buildings). The movement graph, which is a
set of pathways along which the mobile nodes move, is defined by the Voronoi
Diagram of the obstacle corners and Voronoi graph with obstacle as shown in
Fig. 4 and 5, respectively. This model uses
the shortest path routing policy to move the nodes between two locations in
the movement graph. The algorithm of movements of MNs is based on Random Waypoint
Mobility Model. An important distinction between this model and City Section
model is that the City Section can consider a real city. The Manhattan model
considers an idealized city that has a perfect grid layout.
||a) Freeway model, b) manhattan model and c) Pathway graph
|| Voronoi diagram of the obstacle corners
|| Voronoi path and obstacles
However, the Obstacle Mobility Model places buildings at random locations,
hence blocks does not exist and streets are never straight (Tian, 2002). The
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 system 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.
(Johansson et al., 1999) develop three realistic mobility scenarios to
depict the movement of mobile users in real life, including Conference scenario
consisted of 50 people attending a conference. Most of them are static and a
small number of people are moving with low mobility. Event Coverage scenarios
where a group of highly mobile people or vehicles are modeled. Those mobile
nodes are frequently changing their positions. Disaster Relief scenarios where
some nodes move very fast and others move very slowly. In all the above scenarios,
obstacles in the form of rectangular boxes are randomly placed on the simulation
|| Example terrain and pathways
The mobile node is required to choose a proper movement trajectory to avoid
running into such obstacles. Moreover, when the radio propagates through an
obstacle, the signal is assumed to be fully absorbed by the obstacle. More specifically,
if an obstacle is in between two nodes, the link between these nodes is considered
broken until one moves out of the shadowed area of the other. Due to these effects,
the three proposed mobility scenarios seem to differ from the commonly used
Random Waypoint model. Jardosh (2003) also investigate the impact of obstacles
on mobility modeling in details. After considering the effects of obstacles
into the mobility model, both the movement trajectories and the radio propagation
of mobile nodes are somehow restricted. In the simulation field as shown in
Fig. 7, a number of obstacles will place to model the buildings
within the environment. The authors realize that people in real life may follow
the predefined the pathways between buildings, instead of walking randomly and
reflecting off of the buildings. Thus, based on the locations of those building
or obstacles, a Voronoi graph (de Bergg et al., 2000) is computed to
construct the pathways. The mobile nodes are only allowed to move on the pathways
that interconnect the buildings. The Voronoi graph constructs pathways that
are equidistant from the nearby buildings. This observation is consistent with
the common sense that the pathwys tend to lie halfway in-between the adjacent
buildings. Moreover, in this model, the nodes (e.g., students on campus) are
allowed to enter and exit buildings.
Once the pathway graph is defined, the movements of mobile nodes are restricted on the pathways as shown in Fig. 6, s1-s7 Border sites, s8-s15 Intersection sites s16-s20 Voronoi generated sites. Thus, the mobile nodes are likely to travel in a semi-definitive (i.e., pseudo random) way. After the mobile node randomly chooses a new destination on the pathway graph, it moves towards it by following the shortest path through the predefined pathway graph. This shortest path is calculated by the Dijikstra's algorithm in the Voronoi Diagram. Voronoi graphs actually mimic real paths.
|| Voronoi graph in simulation field
Here, we have discussed an Obstacle Mobility model that enables the inclusion of obstacles in ad hoc network simulations that are used both to define the movement pathways of the mobile nodes by Voronoi graph tessellations and to obstruct the transmission of the nodes. The signal propagation model determines the reduction of signal power that takes place when communicating pairs of nodes must transmit through obstacles. There are a number of ways to further extend this work. The first of these relates to the combination of movement characteristics of various mobility models to create a more diverse and comprehensive mobility model. For instance, multiple people may move to a destination as a group. This movement variation allows the combination of Obstacle Mobility Model and the Group Mobility Model. In another scenario, people may follow well-defined pathways to travel to their destination, such as a conference hall. Once they arrive at the hall, these people follow random movement. This scenario involves the combination of the Obstacle Mobility Model to define pathway movement and the Random Mobility Model after a node reaches its destination. The obstacles are used both to define the movement pathways of the mobile nodes and to obstruct the transmission of the nodes. Each time a node transmits a packet, the model determines whether the intended recipient of the packet is within the obstruction set of the transmitting node. If so, reception of the packet is blocked. In this model each destination site has a nonzero probability of being selected by a given node. In reality, it is often the case that people travel most frequently between buildings located physically close to each other and travel less frequently to buildings further away. To model this phenomenon, destination selection could be exponential based on the distance between the potential destination and the nodes current position. In the current model, the intersecting sites are determined by the Voronoi computation. This can result in occurrences of non-optimal doorway placement, for instance where two doorways are located on the same side of an object. To enable realistic doorway placement, or to exactly model existing buildings, the user should be allowed to indicate the placement of the doorways on the object sides. Finally, this study can also be improved through higher granularity modeling of transmissions through and around buildings. This model, assumed to be that buildings are opaque and completely block signal propagation. In reality, many buildings do permit the propagation of wireless signals through their exterior walls. The quality of the signal penetration is a function of the composition and the thickness of the wall. Non-blocking walls would be likely to have a significant impact on the network topology characteristics.
Graph-based mobility model: This model uses a graph to model the movement of the graph represents locations that the users might visit and the edges model the connections between these locations, e.g., streets or train connections. The graph is connected, i.e., there is a path form any vertex to any other vertices in the graph. Each mobile node is initialized at a random vertex in the graph and moves towards another vertex, which is selected randomly as its destination. The node moves to the destination always on the shortest possible path. After the node reaches its destination, it makes a short pause for a randomly selected period and then picks out another destination from other vertices randomly for the next movement. Although a certain grade of randomness still exists in this model, this model provides a realistic balance between completely deterministic and completely random mobility models (Tian et al., 2002). Figure 8 shows an example of graph model.
|| Example of graph model
Here we have discussed a graph-based mobility model that reflects the constraints of movement given by the spatial environment in the real world. In this model, the nodes do not move randomly, but always along the edges of a graph that models the given infrastructure. The spatial constraints have a big impact on the performance of mobile ad hoc routing protocol. A graph of this model has been extracted from external spatial data to represent the realistic movement constraints of pedestrians walking in the city. This model does not including obstacles to make this model more realistic an obstacle should be added to it. We can also include movement profiles of distinct nodes in the model. Graph-based mobility model has been using to evaluate the routing protocols that do not use location information, so it is possible using to evaluate the location aware routing protocols like LAR (Jardosh, 2003) and GPSR (Bittner et al., 2005) with graph walk model in the future. Another topic of the future research will be the study of additional scenarios
Importance of choosing a mobility model: Here, 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 results presented illustrate
the importance of choosing an appropriate mobility model (or models) for the
performance evaluation of a given ad hoc network protocol. The following graphs
show us the performance of the some of Geographic Restriction Mobility Model
(GRMM) and the Random Mobility Model (RMM). In our comparison GRMM and RMM,
we consider the following performance metrics: Data packet delivery ratio, end-to-end
delay, throughput and protocol overhead. Figure 9-14
shows the performance (i.e., throughput and routing overhead) of DSDV, AODV
and DSR between Manhattan, Freeway and Random waypoint. We can see the effect
of mobility of protocol performance. As shown in Fig. 9-14,
DSR, DSDV and AODV incur low throughput and high overhead with both Manhattan
and freeway models. In terms of routing overhead seems to depend on the underlying
mobility model as shown in Figures. DSR incurs the least routing overhead in
most cases, while DSDV has a lower overhead than DSR in the Freeway and Manhattan
models as shown in Fig. 13 and 14. In
the Freeway model, DSDV seems to have the least throughput and the least overhead
AODV seems to be higher routing overhead in the Manhattan and freeway model
than RWP. The above reasoning can be explained as follows: For a given relative
speed, if a mobility pattern has a high degree of spatial dependence, an already
existing link between two nodes is expected to remain stable for a longer period
of time as the nodes are likely to move together.
|| RWP throughput
|| Freeway throughput
|| Manhattan throughput
Thus fewer packets will be dropped due to link breakage leading to higher
throughput. At the same time, the control overhead is lower as little effort
is needed to repair the seldom broken link. For a given spatial dependence,
if a mobility pattern has a high relative speed, the nodes might move out of
range more quickly. Thus an already existing link may remain stable for a relatively
|| RWP routing overhead
|| Freeway routing overhead
|| Manhattan routing overhead
This may lead to more packets being dropped due to link breakage, resulting
in lower throughput. Higher control overhead is needed to repair the more frequently
broken link. We also note that the Freeway and Manhattan mobility patterns have
high relative speed and low degree of spatial dependence leading to the worst
performance of all the protocols while using this model.
|| Data packet reception
|| Control packet overhead
All the protocols had a higher throughput and lower overhead for Random Waypoint
than the Freeway and Manhattan models. The reason for this observation with
the same degree of spatial dependency, between Freeway/Manhattan and Random
Waypoint, high relative speed (for Freeway/Manhattan) means lower link duration,
which will result in lower throughput and higher overhead. The number of data
packets received using the obstacle model is significantly lowers than that
using the random waypoint model. This is due to the inability for routes to
be discovered between sources that are interior (exterior) to an obstacle and
destinations that are exterior (interior) to an obstacle. When the source and
destination are either not both exterior to all obstacles or not both interior
to the same obstacle, it is impossible for the two nodes to find a path to each
other The total number of data packets received by their destinations is shown
in Fig. 15. The control packet overhead is shown in Fig.
|| End-to-end delay
|| Data packet delay
The graph shows that the number of control packets transmitted by the obstacle
model is significantly lower than in the random waypoint. This result is directly
correlated with the number of failed data sessions. Because many data sessions
are aborted, fewer sessions are maintained throughout the simulation; resulting
in fewer overheads Figure 17 shows the end-to-end data packet
delivery delay. This measurement includes route acquisition latencies for discovering
the route. Figure 9 shows that the data delivery delay for
the obstacle model is significantly lower than in the random waypoint model.
Figure 18 shows that AODV achieve lower delay in graph walk
than in random walk. This is because of the different major factors impacting
the delay time: while the delay of AODV is mainly caused by the buffering of
undeliverable packets. Figure 19 shows that AODV in the graph
scenario achieve highest delivery rate than random walk. There is not a large
difference in routing protocol packet overhead between graph walk and random
walk models as shown in Fig. 20.
|| Data delivery rate
|| Protocol packet overhead
AODV shows an approximately linear increase of the protocol overhead in short
ranges for both graph and random walk. For higher radio ranges both random and
graph walk behave similarly because the number of neighbors are about the same
for both cases. The routing packet overhead decreases in AODV with high radio
ranges. AODV achieved lower average end-to-end delay in the graph walk model
than in the random work model. AODV protocol delivered significant more packets
in the graph walk model than in the random walk model in short radio ranges.
AODV achieved slightly more routing packet overhead in the graph walk model
than in the random walk model within short radio ranges. Moreover, AODV achieved
less overhead with increasing radio range.
The performance of an ad hoc network protocol can vary significantly with different
mobility models. The above Figures illustrate the performance of ad hoc network
routing protocol with different mobility models. As shown, the performance of
the protocol is greatly affected by the mobility model. 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.
In this study, we have discussed three mobility models considering the geographic
constraints of node movement. Same as pedestrians and vehicles in the real world,
the mobile nodes in the Pathway mobility model are confined to the pathways.
Even in the obstacle model, the nodes are also moving along the pathways calculated
from the locations of obstacles. Therefore, the predefined pathway graph is
an important factor determining the motion behavior of mobile nodes. For mobility
models with geographic restrictions, those pathways are supposed to restrict
and partly define the movement trajectories of nodes, even though certain level
of randomness appears to exist.
Realizing that the pathway of the map is one key element for the characteristic of geographic constraint of mobility models, we present in this surveying three mobility models (Pathway mobility model, graph-based mobility model and obstacle mobility model). The routing protocols performed quite differently in graph walk model from the random walk model. To improve the graph model we must include obstacles in the model to prevent the radio propagation and to include the movement profiles of distinct nodes in model. Some of authors using some scenarios to get an understanding on how the protocols behave in a realistic environment. They have used an obstacle-approach by adding some obstacles in the scenario to prevent radio propagation. If the straight line between any two nodes is crossed by an obstacle, a link between these nodes is considered broken until the nodes move out of the shadowed area of obstacle. Although this obstacle-approach has made the radio propagation more realistic, its focus was not to improve the modeling of the movement of mobile nodes. As a result, although the predefined graph is more or less based on a real map, all the mobility models mentioned in this study still use Random Waypoint or Random Walk Mobility Model as the algorithm of movements of MNs (with the restriction that nodes must remain on the graph) and hence the models are not realistic.