<<

. 75
( 87 .)



>>

strained, so MANETs privilege protocols dealing with energy reduction approaches, for
example, sleep-period management and adaptive power reduction. Due to host mobility,
MANETs™ scalability is a major problem to solve. This problem is complicated further
by the distributed management and distributed protocols™ implementation, which are
commonly adopted [24]. This makes it difficult to guarantee network behavior, reliabil-
ity, fairness and efficiency under every condition. Reduction of overheads to maintain
proper network functionality is a common problem: use of critical resources, like battery
energy, buffer memory, local CPU computation, and bandwidth for the transmission of
control packets should be minimized.

14.2.2.1 Performance Metrics. A large set of performance metrics could be de-
fined to evaluate MANETs, in order to understand the critical features of the considered
system. Some metrics can be considered relevant or significant only for a given protocol
layer. Other metrics can be general, even if they may be affected by a chain of interlayer
implications. Performance metrics can be roughly divided into the following three cate-
gories: user-performance metrics, resource-utilization metrics, and system metrics. User-
393
14.2 DESIGN AND MODELING OF WIRELESS AND MOBILE AD HOC NETWORKS


performance metrics include, but are not limited to, latency, delay, quality of service, pri-
orities, average and peak performance, reliability, and cost-efficiency metrics. Resource
utilization metrics include overheads, utilization, fairness, and efficiency, just to mention
a few. System metrics include scenario, stability, scalability, and context metrics (e.g.,
topology changes, network partitions, cluster life, mobility, density, load, path length,
etc.). As an example, given a task-process evaluation, interesting metrics can be defined
as average power consumed and communication overheads (which are both considered as
be resource utilization metrics) and task completion time (i.e., a user-satisfaction parame-
ter). Given a routing protocol evaluation, interesting metrics can be defined as average
end-to-end throughput, average end-to-end delay, average link utilization, average packet-
loss probability, energy efficiency, and protocol overheads, among other indices.
Now we will present a short list of generalized metrics that can be evaluated and adopt-
ed in the analysis of Medium Access Control, Routing, and Transport protocols for
MANETs [24, 18, 23]. In the analysis of the following metrics, mean values should be in-
vestigated together with variances or confidence intervals and distribution percentiles.

Access Delay. This is the time spent by a frame (or a packet) in the MAC (routing or
transport level) queue. It is defined from the instant the frame is queued (or de-
queued) until its transmission is successfully completed. Since delay depends on
protocol definition and also on system load and traffic model, every comparison
should be performed under the same conditions.
Channel Capacity. This is the maximum amount of data (e.g., bit rate C) that can be
transmitted over a single channel. The nominal bit rate can be reduced in the pres-
ence of noise and interference. Coding techniques scale in the number of bits/sym-
bols in order to contrast the noise, resulting in lower and lower bit rates.
Throughput and Utilization. The scope of any transmission protocol is to maximize
the number of transmitted bits while minimizing the average access delay. Through-
put T is defined as the average size S of a given frame (packet), divided by the cor-
responding average access delay D, that is, T = S/D. This index is related to the uti-
lization index U, which can be defined as the fraction of channel capacity C used
for successful data transmission.
Overheads. Every resource in the system that would not be strictly necessary to
transmit the payload of the communication can be considered as an overhead and
should be minimized (e.g., time, bandwidth, capacity, CPU time, energy, money).
Fairness. This is a concept related to service and resource sharing, rather than a per-
formance index. A transmission protocol is fair if it does not show any preference
for any single MH contending or waiting for resources or services. Fairness is the
opposite of prioritized access and scheduling policies, adopted to support QoS and
multimedia applications.
Stability. A stable system should not have any fluctuating behavior resulting in a re-
duction of the average throughput and utilization. Adaptive protocols should be
evaluated under the stability viewpoint. Many factors contribute to make the system
unstable.
Reliability. This concept defines a measure of the system reliability with respect to
many failures that can be expected, for example, network partition and broken
paths. The reliability can be evaluated as a probability measure of failures, and as a
measure of the failure-recovery delay.
394 SIMULATION AND MODELING OF WIRELESS, MOBILE, AND AD HOC NETWORKS


Scalability. A scalable system is obtained when protocols and management react
and adapt in an opportune way to changes in the system factors like load and num-
ber of MHs. A scalable system is a system in which performance scales with no col-
lapse. If a collapse occurs, it would be interesting to find information about the sat-
uration point, that is, the limit the system can sustain, and the recovery time from
saturation conditions. A typical example is given by congestion problems.
Power Consumption. Most MHs are battery powered, and maximum energy effi-
ciency is required for every task performed, including system maintenance, trans-
mission, and reception of data.


14.3 SIMULATION TECHNIQUES

In this section, we shall introduce the basic terminology and major issues pertaining to
simulation techniques. Before, we proceed further, we must draw distinctions between
different types of simulations: continuous, discrete, and hybrid.
Continuous simulation models the situation in which changes in state occur smoothly
and continuously in time, for example, the flow of liquid through a pipeline, weather mod-
eling, and circuit-level simulation of electronic components. Continuous simulation mod-
els often involve difference or differential equations that represent certain aspects of the
system. Discrete simulation refers to the modeling technique in which changes to the state
of the model can occur only at countable points in time [21, 57]. For example, in logic
simulation, the circuit is simulated by assuming that node voltages only take on values
from a finite set (say, 0 and 1) and that transitions between values are instantaneous; in
switch-level simulation, transistors are simulated as switches that can be either opened or
closed. Digital computing, communication, and queueing systems (such as used by bank
tellers and job shops) are other examples of discrete event systems. Many systems are hy-
brid, that is, they contain combinations of discrete and continuous characteristics. An ex-
ample of a hybrid system is an unloading dock where tankers queue up to unload their oil
through a pipeline. The decision of whether to use a discrete or continuous model for a
particular system depends on the specific objectives of the study. For example, a model of
traffic flow on a freeway would be discrete if the characteristics and movement of individ-
ual cars were important. Alternatively, if the cars can be treated in the “aggregate,” the
flow of traffic can be described by differential equations in a continuous model.
In this chapter, we are interested into discrete systems that can be simulated by dis-
crete-event simulations. In a discrete-event simulation, the model evolution is defined by
instantaneous events. Each event corresponds to a transition in a portion of the model
state, composed of state variables, each describing a characteristic of the model. Each
event also has a simulation time associated with it, called a timestamp, which defines its
occurrence time. Each event may in turn generate new future events.
The generation of new events and the dependency of their transitions on state variables
that previous events may have updated define a relation of causal order (a partial order)
among events. Related events are said to be causally dependent, whereas unrelated ones
are called concurrent. In order to guarantee the correctness of the simulation, concurrent
events may be safely processed in any order in a simulation, whereas causally dependent
events must be processed according to the causal order. Thus, to ensure the strict chrono-
logical order, events are processed one at a time, resulting in an (apparently) sequential
program. A typical template for a sequential simulation is given in Figure 14.5.
395
14.3 SIMULATION TECHNIQUES


While Not Empty (EventQueue) Do
dequeue (m) /* earliest event from EventQueue */
update (clock)
simulate (m)
enqueue() /* enqueue any events produced */
EndWhile

Figure 14.5. Basic Sequential Discrete Event Simulation Algorithm.


Discrete systems can be simulated by discrete-event simulations. Many methods have
been proposed in the literature for implementing discrete systems. They can be broadly
classified into two groups, the synchronous and the asynchronous methods. In synchro-
nous discrete event simulation, all objects in the simulation progress forward in simula-
tion time together, in synchrony, with no object ahead of any other in time. The usual
queue implementations for sequential simulation are all synchronous methods. In
contrast, an asynchronous method permits some objects to simulate ahead in time while
others lag behind. Of course, an asynchronous method must include some mechanism for
ensuring that when an object that is “behind” schedules an event for execution by an ob-
ject that is “ahead,” it does not cause any events to be executed in the wrong order.
In this chapter, we are interested into modeling and simulation of wireless and mobile
networks based upon asynchronous discrete event simulation tools.

14.3.1 Sequential Network Simulation Testbeds
In this section, we shall review several network simulators that have been widely used by
both academia and industry communities.
OPNET (Optimized Network Engineering Tool) [47] provides a comprehensive set of
simulation and modeling products for the development and performance analysis of
wired and wireless networks. For protocol and technology R&D space, their OPNET
Modeler product provides a high-fidelity discrete-event simulation environment using a
hierarchical modeling paradigm, in which each level of hierarchy represents different as-
pects of the complete model being simulated. It provides powerful tools to assist users
in building simulation models, and for output analysis. OPNET includes a highly opti-
mized discrete event simulation kernel, and has been used quite successfully within the
wired and wireless networks communities. To the best of our knowledge, scalability is a
major problem in most monolithic discrete event simulators, such as ns-2, and takes too
long to run the simulation, and one has to spend a large amount of time to understand
how to use them. OPNET is among a few commercial products that are reasonably easy
to use, and relatively scalable when compared to existing simulators. To further increase
its scalability, parallel simulation technology has been under development.
Recently, a federated simulation approach has been investigated to enhance and paral-
lelize OPNET. Each confederate is basically a sequential simulator modeling a subnet-
work of the simulated model. Although, recent results were quite encouraging, the work is
still at an early stage [63].
INSANE, a network simulator, was designed to test various IP-over-ATM algorithms
with realistic traffic load derived from empirical traffic measurements. Although the sim-
ulator provides an easy approach to check the progress of multiple running simulation
processes, we find it quite restrictive to ATM network simulations.
396 SIMULATION AND MODELING OF WIRELESS, MOBILE, AND AD HOC NETWORKS


NetSim is another network simulator. It was designed to provide detailed simulation of
the Ethernet, including realistic modeling of signal propagation, collision detection, and
handling process.
OMNeT++ [46] is a freely distributed, object-oriented, modular, discrete-event simula-
tor written in C++. It is designed for general-purpose discrete-event simulation, and pro-
vides some model libraries for communication protocols and network systems. NED, a
network descriptor language, can be used to assist the modeler in the model definition
based on system modules written in C++. OMNeT++ support for parallel execution and
parallel discrete event simulation is an ongoing research activity.
The network simulator ns-2 [45] is a discrete-event simulator that provides substan-
tial support for simulation of TCP, routing, and multicast protocols over wired, wireless
(local and satellite), and wireless multihop ad hoc networks. ns-2 began as a variant of
the REAL network simulator in 1989 and has evolved substantially over the past few
years. Since then, it has included substantial contributions from other researchers, in-
cluding wireless code from the UCB Daedelus and CMU Monarch projects and Sun
Microsystems. ns-2 is written in C++, and it uses OTcl, an object-oriented version of tcl,
as a command and configuration interface. The interface code to the OTcl interpreter is
separate from the main simulator, and complex objects are decomposed into simpler
components for greater flexibility and composability. Although ns-2 is widely in use
within the wireless networking communities, it is not a fine-tuned and finished product,
and it is still a result of an on-going effort of research and development. In particular,
bugs in the software are still being discovered and corrected. Users of ns are mainly
responsible for verifying for themselves that their simulations are not invalidated by
bugs.
Among all the existing network simulators, ns-2 is most popular tool used by both the
wireless and wired communities. It has also been extended to mobile ad hoc networks as
well. The major drawback of ns-2 is the execution time of the simulation, mainly due to
the sequential implementation of the discrete-event simulator. Although it is quite easy to
use, run, or modify preexisting models, it requires a large amount of time to study the in-
side of ns-2 before a simulation modeler develops new models.
A few researchers have investigated ways to speed up the running time of the simula-
tion using ns-2. We shall describe them in the next section.

14.3.2 Parallel and Distributed Simulation
Due to the enormous computational requirements of a sequential simulator for complex
wireless systems, parallel discrete-event simulation techniques [14, 39, 40, 43, 48, 65] are
often studied to reduce the execution time of the simulation models. Before, we proceed
further, let us introduce the basic terminology and major issues pertaining to parallel and
distributed simulation. A parallel or distributed simulation should provide the same solu-
tion to a problem as a sequential simulation.

14.3.2.1 Principles of Parallel and Distributed Simulation. To ensure strict
chronological order in large-scale simulation, events are processed one at a time, resulting
in an (apparently) sequential program. Only by eliminating the event list in its traditional
form, so as to capture the interdependence of the process being simulated, can additional
parallelism be obtained [16]. This is the objective of parallel simulation. Indeed, parallel
simulation shows great potential in terms of exploiting the inherent parallelism of a sys-
397
14.3 SIMULATION TECHNIQUES


tem, and the concurrency among events to achieve execution speedup. Good surveys of
the literature may be found in [21].
A parallel simulator is composed of a set of logical processes (LPs) which interact by
means of messages, each carrying an event and its timestamp, thus called event messages.
Each LP is responsible for managing a subset of the model state, called the local state.
Each event e received by an LP represents a transition in its local state. The events sched-
uled by the simulation of e are sent as event messages to neighboring LPs to be simulated
accordingly. In a simulation, events must always be executed in increasing order. Anom-
alous behavior might result if an event is incorrectly simulated earlier in real time and af-
fects state variables used by subsequent events. In the physical model, this would repre-
sent a situation in which future events could influence the present. This is referred to as
causality error. Several synchronization protocols have been proposed to deal with this
problem. These techniques can be classified into two groups: conservative and optimistic.
Conservative synchronization techniques rely on blocking to avoid violation of depen-
dence constraints, and optimistic methods rely on detecting synchronization errors at run
time and on recovery using a rollback mechanism.

14.3.2.2 Conservative Simulation. Conservative approaches enforce event causal-
ity by requiring that each LP elaborate an event only if it is certain that it will not receive
an earlier event. Consequently, events are always executed in chronological order at any
LP. Each logical process LPi maintains an input queue (lij) for each of its neighbors LPj. In
the case that one or more (input) queues are empty, the LP is blocked because an event
with a smaller timestamp than the timestamp of the waiting events might yet arrive at an
empty queue. This mechanism implies that only unblocked LPs can execute in parallel. If
all the LPs were blocked, the simulation would be deadlocked. Ensuring synchronization
and avoiding deadlocks are the central problems in the conservative approach. Several
schemes have been proposed to alleviate this problem. In [16], the authors employ null
messages in order to avoid deadlocks and to increase the parallelism of the simulation.
When an event is sent on an output link, a null message bearing the same timestamp as the
event message is sent on all other output links. As is well known, it is possible to generate
an inordinate number of null messages under this scheme, nullifying any performance
gain [21].
As a result, a number of attempts to optimize this basic scheme have appeared in the
literature. For example, in [57], the authors refrain from sending null messages until such
time as the LP becomes blocked. They refer to this approach as eager events and lazy null
messages. They reported some success in using variations of Chandy“Misra approaches
to speed up logic simulation.
Boukerche and Tropper [10] employed the following approach. In the event that a null
message is queued at an LP and a subsequent message (either null or event) arrives on the
same channel, they overwrite the (old) null message with the new message. A single
buffer is associated with each input channel at an LP to store null messages, thereby sav-
ing space as well as the time required to perform the queuing and dequeuing operations
associated with null messages. Good surveys of conservative techniques can be found in
[11, 21].

14.3.2.3 Optimistic Approach. Time Warp is based on an optimistic approach and

<<

. 75
( 87 .)



>>