Abstract: In this study, we present and visit the limitation of Random mobility model, the unconstraint motion of mobile node. Mobile nodes, in the Random Waypoint and Random walk mobility models, are allowed to move freely and randomly anywhere in the simulation field. However, 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.
INTRODUCTION
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.
| Fig. 1: | The categories of geographic restriction mobility models in mobile Ad hoc network |
| Fig. 2: | 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.
DISCUSSION
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.
| Fig. 3: | a) Freeway model, b) manhattan model and c) Pathway graph |
| Fig. 4: | Voronoi diagram of the obstacle corners |
| Fig. 5: | 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 field.
| Fig. 6: | 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.
| Fig. 7: | Voronoi graph in simulation field |
DISCUSSION
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 node’s 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.
| Fig. 8: | Example of graph model |
DISCUSSION
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.
| Fig. 9: | RWP throughput |
| Fig. 10: | Freeway throughput |
| Fig. 11: | 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 shorter duration.
| Fig. 12: | RWP routing overhead |
| Fig. 13: | Freeway routing overhead |
| Fig. 14: | 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.
| Fig. 15: | Data packet reception |
| Fig. 16: | 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. 16.
| Fig. 17: | End-to-end delay |
| Fig. 18: | 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.
| Fig. 19: | Data delivery rate |
| Fig. 20: | 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.
CONCLUSIONS
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.