602 IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 15, NO. 3, JUNE 2007 A Generalized Random Mobility Model for
Wireless Ad Hoc Networks and Its Analysis:
Denizhan N. Alparslan and Khosrow Sohraby, Senior Member, IEEE Abstract—In wireless ad hoc networks, the ability to analytically characterize the spatial distribution of terminals plays a key role in understanding fundamental network QoS measures such as throughput per source to destination pair, probability of successful transmission, and connectivity. Consequently, mobility models that are general enough to capture the major characteristics of a realistic movement profile, and yet are simple enough to formulate its long-run behavior, are highly desirable.
We propose a generalized random mobility model capable of capturing several mobility scenarios and give a mathematical framework for its exact analysis over one-dimensional mobility terrains. The model provides the flexibility to capture hotspots where mobiles accumulate with higher probability and spend more time. The selection process of hotspots is random and correlations between the consecutive hotspot decisions are successfully modeled. Furthermore, the times spent at the destinations can be dependent on the location of destination point, the speed of movement can be a function of distance that is being traveled, and the acceleration characteristics of vehicles can be incorporated into the model. Our solution framework formulates the model as a semi-Markov process using a special discretization technique. We provide long-run location and speed distributions by closed-form expressions for one-dimensional regions (e.g., a highway). Index Terms—Ad hoc networks, long-run analysis, mobility
modeling, semi-Markov processes.
WIRELESS ad hoc networks are comprised of wireless
mobile nodes that can dynamically form a network in a self-organizing manner without the need for a pre-existing fixed infrastructure. Nodes in an ad hoc network can move according to many different mobility profiles. Therefore, mobility models that dictate the movement behavior of a mobile terminal play a key role in the simulation or analytical based analysis of the impact of dynamically changing topology on the performance of these networks. In this paper, we consider a generalized random mobility model that is flexible enough to capture different mobility scenarios, and provide its long-run location and speed distributions by closed form expressions for one-dimensional mobility terrains.
In what follows, we categorize the existing mobility models for wireless ad hoc networks, and briefly summarize their assumptions. Traditionally, a mobility model governs the changes
Manuscript received December 3, 2004; revised April 6, 2006; approved by IEEE/ACM TRANSACTIONS ON NETWORKING Editor N. Shroff.
D. N. Alparslan is with The MathWorks, Inc., Natick, MA 01760 USA. K. Sohraby is with the School of Computing and Engineering, University of Missouri-Kansas City, Kansas City, MO 64110 USA.
Digital Object Identifier 10.1109/TNET.2007.893235
in the moving direction and speed of terminals according to a deterministic approach or a random process. In the former case, movement path of terminals can be restricted to predetermined paths. For ad hoc environments, such mobility models are impractical since wireless ad hoc networks are created “on the fly”,
and collecting data to generate the paths for all situations can be very complicated. Thus, a mobility model that dictates the movement of hosts due to a random process, that is, random mobility model, is more appropriate for the performance evaluation of these networks. Surveys for both models are presented in  and .
In general, random mobility models formulate the movement pattern of mobile hosts by consecutive random length intervals called movement epochs. During each epoch, mobile terminal moves at a constant speed, and at a constant direction for a random amount of time. The speed and direction choice for each epoch may or may not be correlated with their values in the previous epochs, and mobility characteristics of other terminals. For instance, according to the randomwalk mobility model , each terminal movement is uncorrelated with other’s movement,
and the speed and direction choices for each epoch are also uncorrelated with their previous choices. The random waypoint mobility model  includes pauses at the end of movement epochs in the random walk model to make it more applicable to different scenarios. More formally, according to the random waypoint mobility model, a mobile node determines a destination point that is distributed uniformly within the physical terrain and moves in the direction of that destination at a constant speed. This speed is selected uniformly from
where , and it is independent from the destination and starting points of the movement epoch, and also the distance that is going to be traveled. After reaching the destination, mobile pauses for a random amount of time, which has the same distribution for all destination points, and the same movement process is repeated by selecting a new destination and speed pair independently
from the same pair of the previous movement epoch.
A shortcoming of the random mobility models is that the
movement profiles that are generated with respect to them may not be consistent with the major characteristics of a realistic scenario. For instance, as it also mentioned in , the random walk and the random waypoint mobility models may generate unrealistic movement patterns such as “sudden stops” and “sharp
turns”. In –, the authors propose models that can capture correlation between the speed and the direction choices of consecutive movement epochs and therefore these models may generate
a pattern which is smoother with less sharp turns. Furthermore, as it is also criticized in  and , selecting speed independently from the distance that is going to be traveled may
1063-6692/$25.00 . 2007 IEEE
ALPARSLAN AND SOHRABY: GENERALIZED RANDOM MOBILITY MODEL FOR WIRELESS AD HOC NETWORKS
AND ITS ANALYSIS: 1-D CASE 603
end up in unrealistic mobility profiles where mobiles travel long distances with low speeds.
A common limitation of the random mobility models described above is that one cannot model a scenario which incorporates predefined pathways that mobiles must follow and specific destinations on those paths where mobiles accumulate with higher probability. The models presented in ,  focuses on this problem by taking a more deterministic approach that can capture obstacles and predefined pathways between them on the physical terrain.
In the analytical studies for the performance analysis of wireless ad hoc networks, closed form expressions for the spatial node distribution are very desirable to understand long-run behavior of the network spatial behavior. For instance, the analyses that are presented in – to estimate the capacity
per source to destination pair of these networks are significantly dependent on the spatial distribution of mobile nodes. Additionally, for some scenarios in which terminals can be highly mobile on a wide region, the spatial distribution of offered traffic may not be ignored in determining the capacity of asynchronous MAC layer protocols. Observe that the analysis of this case requires an accurate knowledge of the spatial distribution of nodes. Also, the analytical work presented in  considers the station locations for the MAC layer throughput analysis but the terminals are assumed to be uniformly distributed in the region. Clearly, the uniform distribution assumption may not be valid for different mobility scenarios. Moreover, this knowledge can be also used in evaluating the connectivity properties of ad hoc networks, which have been extensively studied in  and . In addition to these, the distribution of link distance between mobile terminals, which is an important characteristic of wireless ad hoc networks , , can be obtained from the spatial distribution of terminals.
Hence in this paper we propose a generalized random mobility model that is general enough to capture the major characteristics of a realistic movement profile, and yet is simple
enough to mathematically formulate its long-run behavior with analytical expressions. The mobility pattern of a terminal that moves according to this generalized model is composed consecutive movement epochs in a closed region, and it is independent with the movement behavior of other terminals. During each movement epoch, mobile terminal firstly moves on the finite
line segment joining the starting and destination points of the epoch at a random speed and then it pauses at the destination for a random amount of time. The generality of our model is actually originating from the approach that we took to determine the destination point, movement speed, and pause time at the destination, and can be explained as follows:
. The distribution of the destination points are assumed to be general and can be conditionally dependent on the starting point of the movement epoch.
. The random speed for each epoch is drawn from a general distribution function that can be conditionally dependent on the starting and destination locations of the movement epoch, and the current location of mobile terminal if necessary. . The pause time at each destination is selected randomly from a distribution that is dependent on the location of the destination point.
The fact that we make the mobility modeling with respect to these generalized approaches has a number of advantages. First, since destinations are selected from a general distribution, amovement scenario in which terminals select some specific locations, for example, hotspots, as destination with higher probability, can be easily captured. Furthermore, some mobility scenarios may require a Markovian dependency between the destination points of consecutive movement epochs. For instance,
the probability of selecting a hotspot as destination can be different for different starting points. This case can be naturally incorporated into our model by employing a distribution function
for destinations that is conditionally dependent on the starting points.
Second, the generic approach for determining speed provides a unique opportunity to select speed according to the distance that is going to be traveled, and also a method to model variable speed during movement epochs. Clearly, if the speed of the terminal can vary during moving, then our model can even be used to capture different acceleration characteristics of vehicles. Finally, by employing a pause time distribution for each epoch that is a function of destination coordinate, we reached to the flexibility of pausing different times at different locations.
For some sophisticated mobility models, performing its long-run analysis first over one-dimensional regions will be useful in gaining some insight into the methodology that has to be followed for the analysis of higher dimensions. Thus, in this paper, we concentrate our analysis to one-dimensional regions, and develop an analytical framework that provide closed form
expressions for the long-run location and speed distributions. We also believe that the analytical results presented can provide a methodology to analytically formulate the fundamental properties of wireless ad hoc networks for number sophisticated
mobility scenarios (e.g., capacity, connectivity).
A. Related Work
There have been a number of works attempting to obtain spatial node distribution for the ad hoc environments where terminals move according to random walk or random waypoint
mobility models. The simulation studies that are presented in  and  for the random waypoint mobility model showed that the long-run spatial distribution of mobiles is independent from their initial placement in the simulation area, and also observed that resulting distribution is more accumulated at the center of the region. In , the movement pattern of the same mobility model is characterized as a stochastic process, and analytical expressions for the long-run location distribution are derived. In , authors not only concentrate on the analytical expressions for long-run spatial distribution of random waypoint
model, but also on the limiting distribution of speed and procedures for the accurate simulation of this mobility model as well. The simulation study presented in  also concentrated in the same model, and examined average node speed at the steady-state. They pointed out that the closer to zero, the more time it takes for the simulation of the mobility model to reach stability. In , this work is extended by analytical studies and authors provided steady-state average speed distribution for several random mobility models in which the speed for a movement epoch is chosen independently from the destination of that epoch. For these mobility models, as a byproduct