<<

. 74
( 87 .)



>>

model [3, 13]. It is completely unpredictable and it has the memoryless property for
speed and direction. This means that current speed and direction are not related to
the speed and direction history, and speed and direction are completely uncorrelated
(i.e., two independent, stochastic processes) [3]. Many mobile users adopting such
motion model result in completely uncorrelated mobility, and the mobility pattern is
quite unrealistic. This is a typical worst-case modeling assumption, for example,
when the analysis demonstrates that the adaptive protocols™ performance does not
rely on any motion correlation and/or predictable-position assumptions. This model
can be used for vehicular and large-scale environments, and can be implemented in
many ways. Assuming a 2-D motion, one possible implementation is the following:
every MH moves from a current location to its new location defined by a uniformly
distributed pseudorandom choice of a new direction in the polar angle interval
[0, 2 [, and by a uniformly distributed pseudorandom choice of a speed value s in
[minSpeed, maxSpeed]. The speed and direction are maintained for constant time
values ts and td, respectively (this is a good implementation for simulations with
slotted-time management). If time management is not slotted, an equivalent choice
is to uniformly generate direction and speed s to be maintained for a constant dis-
tance ds and dd, respectively. This can be a good choice when the system to be mod-
eled has underlying grid topologies, for example, cells, and every single cell migra-
tion is a relevant event. Given a similar choice, the “next move” events are not
synchronous in the simulation. This can result in additional problems and computa-
tion needs: if it is required to obtain the position of neighbor MHs before every
move, then every neighbor MHs™ position would need to be interpolated. Dealing
with the simulated area boundaries, if the area limit is “bouncing” off the MHs, e.g.,
with a direction proportional to the angle of incidence, in 1-D and 2-D there is an
interesting property: every MH will randomly move around its initial position [13].
This also represents a pitfall for this model: if the initial allocation of MHs is not
uniform, and the average speed is low, then the “memory effect” of the initial distri-
bution would be persistent, and clusters of MHs could be maintained, despite the
randomness of the motion model. This behavior may affect the assumptions about
the average degree (i.e., number of neighbors) of a mobile host during the simula-
tion. If the time values ts and td are long, given the bouncing behavior of area
boundaries, the average distribution of MHs would be concentrated in the middle of
388 SIMULATION AND MODELING OF WIRELESS, MOBILE, AND AD HOC NETWORKS


the simulated area (because when a mobile host is near the boundaries, it has a high
probability to be reflected or to choose a new direction toward the center of the
area) [3, 13]. If ts or the average speed is great, the node density could be made
quite uniform with a torus border area policy [3]. Many additional choices or as-
sumptions can be made for this model. The main factors to define for analysis based
on this model are the speed ranges and average speed values. The speed factor de-
fines how far a mobile host can roam away from its initial position, and should be
dependent on what is intended to be simulated (e.g., micromobility within one
room, macromobility between cells, etc.) and on time management factors as well,
such as slot duration, for instance. Any biased distribution for speed and direction
might lead to a different implementation of the model. Special attention is required
regarding the MHs™ density assumption, and initial distribution of MHs™ positions
[13, 54].
Restricted Random Model. The restricted random model usually introduces some
kind of autocorrelation or biasing in the “randomness” of the uniform distribution
of random model parameters [13]. For example, the speed selection s or the direc-
tion can be updated up to a limited amount based on current values, s [s “ k, s +
k], [ “ /4, + /4]. This model defines a preferred direction and a preferred
speed range for all users (or for every single user), and smoothed curves and accel-
erations. The main factors to define for analysis based on this model are the direc-
tion and speed ranges, and the admitted tolerance for variations.
Smooth Random Mobility Model. This was proposed in [3, 5] and can be seen as an
extended Random Mobility Model. It is defined with two stochastic processes for
correlated speed and direction management. In [28], a criticism of the random mod-
els used for MANET simulation was based on the unrealistic movement behavior
caused by sudden and uncorrelated speed and direction changes. Restricted random
models introduce autocorrelation. In the Smooth Random Model, correlation is in-
troduced together with a set of tunable parameters concerning “node classes,” char-
acterized by acceleration and deceleration parameters, target speed, and smoothed
direction changes. The proposed model is able to implement realistic behavior of
nodes in many scenarios, from urban (Manhattan-like) to large-scale, with accept-
able additional computation required [3].
Random Waypoint Model. This is similar to the Random Mobility Model, but it adds
the epoch and pause concepts to make the random model a little bit more similar to
realistic user mobility [4, 12]. A MH executes a sequence of epochs, each one de-
fined as a motion interval followed by a pause interval. At the beginning of a motion
interval, the MH selects the new destination coordinates (x, y) (not the direction as
in the Random Mobility Model), uniformly distributed in the simulated area. Any
border policy is equivalent with this motion model, since MHs can only touch, nev-
er hit, the area boundaries. Speed is uniformly distributed in [minSpeed, maxSpeed].
At the end of a motion interval, a given “pause time” pt is defined, uniformly dis-
tributed in [0, maxPauseTime]. If pt = 0, something really similar to the Random
Mobility Model is obtained. Intuitively, this motion model is the behavior of the
“walking philosophers” (walk, think). This model is of widespread use in many sim-
ulations of wireless mobile systems [4, 12, 64]. All of the considerations regarding
the Random Mobility Model are still valid, for example, uncorrelated and unpre-
dictable mobility, and memoryless property for speed and direction [4]. The pitfall
389
14.2 DESIGN AND MODELING OF WIRELESS AND MOBILE AD HOC NETWORKS


of MHs™ concentration in the center of the simulated area is still present. This means
that MHs are often moving toward the high-density center of the simulated area, and
sometimes move temporarily to the sparse boundary areas [5, 54]. Any initial distri-
bution of MHs is not relevant for the steady-state distribution of MHs, because the
next position is always a random point in the simulated area. Transient effects from
the initial distribution of nodes can be quickly eliminated, in order to avoid biasing
in the steady-state simulation results. Some problems can be caused by the model
factors: speed and pause time. Currently, Random Waypoint is subject to criticism
[64], mainly for the speed distribution of nodes and for the risk of density concen-
tration of MHs in the center of the simulated area [54]. A nontrivial relationship be-
tween average speed and average pause time has been reported in many scenarios,
depending on the objective of the simulation [13]. If the network stability and link
reliability are under analysis, the average pause time sometimes has a prevailing ef-
fect with respect to average speed of MHs [13].
Random Direction Model. This is a small variation of Random Waypoint epochs, de-
fined in order to avoid the MH concentration in the center of the simulated area. To
obtain a uniform number of neighbors (i.e., degree) for each MH, the modeler should
be careful about the model parameters. The model is similar to Random Waypoint:
before a motion period, a speed and a direction (as in the Random Mobility Model) is
uniformly selected, to be maintained up to the area boundaries will be reached [54].
Once on the boundary, a pause time is selected, then a new epoch starts. Given the re-
duced density distribution, network partitions are more probable in this model [13].
Another variation is the Modified Random Direction Model, in which the selected di-
rection is followed up to a given distance d, without necessarily reaching the area
boundaries. This model would be quite similar to a hybrid Random Mobility Model
with pause times, and to the Random Waypoint Model.
Boundless Simulation Model. This is similar to a vector-based implementation of
the Restricted Random Mobility Model, implemented over a torus-like simulation
area [13].
Gauss“Markov Mobility Model. This model uses a tuning parameter [0, 1] to
vary the degree of “randomness” and self-correlation of speed and direction in a
Random Mobility Model [13]. = 0 returns a Random Mobility Model, whereas
= 1 returns a linear motion in the initial direction and speed [13].
Mobility Vector Model. This model uses a base vector, a deviation vector, and an ac-
celeration parameter to define the mobility vector for every MH. Given the mo-
bility vector definition, the extension to a 3-D space model is straightforward, and
the vector model defined can be considered as a framework for many models™ im-
plementation [27].
City Section Mobility Model. This is a hybrid model merging the Random Waypoint
Model and Manhattan-like scenarios. The urban constraints are defined as usual
(streets, one-ways, crossings, walls, etc.). Every MH randomly selects a destination,
then it travels towards the destination by following the most linear route. Once arrived
at its destination, the MH pauses for a random time, then it chooses another destina-
tion [13]. The model may introduce some additional issues to be managed, like speed
limits, traffic lights, and traffic laws. This may require a significant computation.
Graph-Based Mobility Model. This model has some similarities with the City Sec-
tion Model. Every MH moves following the edges of a graph defining the infra-
390 SIMULATION AND MODELING OF WIRELESS, MOBILE, AND AD HOC NETWORKS


structure of the area. The target destination is one vertex of the graph, randomly se-
lected, and the route is always the shortest path [60].
Random (Manhattan) Drunk Mobility Model. This is similar to the City Section
Mobility Model, but it does not define a target point to reach. Every time a new
crossing is reached, a new direction is selected from the available ones, according to
any distribution probability. Speed can be changed as a separated stochastic
process, or according to scenario constraints [3].

Among the synthetic mobility models, the group mobility models belong to a new class
of models that can be used for MANET modeling and simulation purposes [13, 28, 61].
The main difference for such models is given by the idea that MHs™ decisions about their
movements would mainly depend upon other MHs in their group or common factors in
the scenario. This introduces a motion-correlation effect among MHs belonging to the
same logical group. This effect should be evaluated as unacceptable if the assumption for
the analysis requires uncorrelated mobility. It may happen, for example, that the relative
mobility of MHs within the same group is really low, thereby favoring intragroup commu-
nication and routing. The analysis of a given routing protocol under this mobility model
should not be considered as a generalized result for general scenarios, because it is biased
in a significant way by the adopted mobility model correlation. Group partition and defi-
nition is out of the scope of this presentation. It may be related to position, host speed
(walk, car, train), and scenario characteristics (e.g., highway lane). The group mobility
models can be roughly classified as gravity models, location-dependent models, targeting
models, and random group mobility models [13]:

Gravity Model. This model can be used in scenarios where MHs may tend to move
toward some destinations (e.g., signal sources) named attraction points. Intuitively,
every MH is assigned a positive charge, and attraction points are assigned a nega-
tive charge. Opposite charges attract each other, while same charges repel each oth-
er. MHs with no charge have no gravity effects [13, 27].
Reference Point Group Mobility (RPGM) Model. This is the most general group mo-
bility model. Specifically, the Column Model, Nomadic Community Model, and
Pursue Model can be implemented as special cases of the RPGM model [28]. A log-
ical center for the group is defined, and each MH defines a reference point fixed
with respect to the group™s logical center. The logical center moves according to a
group™s motion vector (GMV), randomly chosen or predefined, and every MH adds
a random motion vector (RMV) to its reference point [28].
Reference Velocity Group Mobility (RVGM) Model. This model can be used when
the group shares velocity and direction characteristics, rather than proximity [61]. A
group velocity vector defines the dominant velocity characteristic of the group, and
a random local velocity deviation vector is composed with the group velocity to de-
termine the single host velocity vector. This can be thought of as the time derivative
of the position-based group representation in the RPGM model [61].
Exponential Correlated Random Mobility (ECRM) Model. This model introduces a
quite complex motion function that can be used to define the MH movements,
where a parameter defines the mobility factor, and a random Gaussian variable
with parameter is included in the formula [28]. The main problem with this mod-
el is to find appropriate values for the model parameters.
391
14.2 DESIGN AND MODELING OF WIRELESS AND MOBILE AD HOC NETWORKS


Column Model. This model defines a mobility pattern similar to a column of not-
well-trained soldiers marching in line. Every MH has a reference point in the col-
umn and moves randomly around that point. All reference points (i.e., the column)
move together based on the common advance vector definition [13].
Nomadic Community Model. This model defines a mobility pattern similar to a
group of students on a guided visit to a museum. It is a hybrid random-/targeting-
group mobility model. The whole group of MHs (students) has a common single
reference point (the guide), which is moving according to a given random mobility
model (e.g., similar to Random Waypoint). Every single MH is free to move around
the group™s reference point, according to a random mobility model [13].
Pursue Model. This is another targeting-group mobility model based on the defini-
tion of a single target moving according to a random mobility model. The tracking
MHs define their group mobility based on the straight direction from their position
to the target, biased by a random offset vector.

Other complex and mathematically intractable motion models can be defined to cap-
ture more realistic user mobility patterns to be used in simulation. This is an ongoing re-
search activity. One of the challenges for the research is to find efficient techniques for
the implementations of the proposed models. Additional efforts should be made to study
models whose implementation can be supported efficiently in the adoption of the distrib-
uted simulation paradigm.
Many commercial and freely distributed simulation tools support mobility models
and complex scenarios. Recently, some application tools have been proposed for known
simulation tools and models. CAD-HOC [55] is a tool used to generate mobility bench-
marks and ad hoc scenarios to feed the network simulator ns-2 [45]. Bonn-Motion is a
mobility, scenario-generation, and analysis tool, written in Java, that can be used to de-
fine Tcl scripts feeding ns-2. FraSiMo [20] is a research project to model mobile ad hoc
networks with Omnet++ [46]. A commercial tool, OPNET [47], defines a complete set
of facilities to model complex mobility scenarios and propagation models for ad hoc
networks.

14.2.1.6 Traffic Workload. The workload characterization for MANETs, that is, the
amount of data to be transmitted between MHs, is another relevant point for the modeling
definition. Workload is relevant for the evaluation of the supported Quality of Service
(QoS) and service reliability for the application and user needs. The network traffic char-
acterization is a problem that has been analyzed for years, dealing with the self-similarity,
bursty nature, and correlation of packet-arrival processes, among other things [56].
Trace-based workload models are widely used in many simulations, data and video
transmission, for instance. In MANETs, currently nobody knows what would be the killer
application, so we can only speculate about the workload characterization of such sys-
tems. Usually, as a worst-case scenario, the simulation analysis can be performed under
asymptotic workload conditions. This means that the assumption for the system is that the
sources of traffic in the network always have full transmission buffers. This hypothesis is
good for testing the stability and congestion reaction of a given network, or to evaluate the
scalable behavior and asymptotical throughput metrics for the system.2

2
Note that this is a worst-case scenario, and maybe an unrealistic condition.
392 SIMULATION AND MODELING OF WIRELESS, MOBILE, AND AD HOC NETWORKS


Underload conditions can be defined by adopting other commonly used, parameterized
models. Another widely adopted traffic model for MANET simulation analysis is the
Constant Bit Rate (CBR) Traffic Model, in which every source (sender) of traffic gener-
ates a constant flow of packets. This can be obtained simply by assuming that a given
amount of data is generated at constant time intervals. This model is commonly used to
approximate the workload generated by voice-based applications. This model can also be
extended in many ways, in order to make it much more realistic.
The Variable Bit Rate (VBR) Traffic Model can be adopted to approximate the work-
load generated by data and video applications [41]. It is defined by traffic sources gener-
ating a variable amount of data, as a function of time, depending on many packet-interar-
rival-distribution parameters.

14.2.2 Mobile Ad Hoc Network Simulation
Computer-based discrete-event simulation is one of the most flexible methods for the per-
formance evaluation of complex systems such as MANETs. The goal of a simulation
study is the construction of a simulator that mimics the system state transitions and, by
collecting and analyzing data during simulation runs, estimates the performance metrics
of the systems under analysis. An orthodox simulation study is based on several steps
whose characteristics and number can vary with respect to the nature of the system ana-
lyzed and the objectives of the study. The key steps in establishing the kernel of any simu-
lation study are (1) problem formulation, (2) workload characterization, (3) model defini-
tion and validation, (4) construction and verification of the simulator, (5) design of
experiments, and (6) analysis of the simulation results or output analysis [29].
In this section, we discuss the main system characteristics and performance figures of
interest for mobile ad hoc network simulations. Regardless of the applications and the
protocol layers considered for the analysis, many critical features contribute to deter-
mine the efficiency, reliability, and effectiveness of MANETs. MANET networks are
characterized by dynamic topologies, requiring adaptive, multihop routing protocols,
dealing with bidirectional and unidirectional links [18]. Links are bandwidth constrained
compared to typical wired networks, and they offer variable capacity and delay times,
due to the effect of highly variable scenario conditions. Mobile hosts are energy con-

<<

. 74
( 87 .)



>>