<<

. 71
( 87 .)



>>

Proceedings of IEEE/ACM Workshop on Mobile Ad Hoc Networking and Computing (Mobi-
HOC), Boston, MA, August 2000.
9. L. Buttyan and J. P. Hubaux, “Stimulating Cooperation in Self-Organizing Mobile Ad Hoc Net-
works.” ACM Journal for Mobile Networks (MONET), Special Issue on Mobile Ad Hoc Net-
working, 2002.
10. S. Corson and J. Macker, “Mobile Ad Hoc Networking (MANET),” ietf rfc 2501, January 1999.
11. J. Macker and S. Corson, “Mobile Ad Hoc Networks: Routing Technology for Dynamic Wire-
less Networking,” in Ad Hoc Networking, IEEE Press/Wiley, 2003.
12. R. Dawkins, The Selfish Gene. Oxford University Press, Oxford, 1976.
13. E. R. Weintraub (Ed.), Toward a History of Game Theory. Duke University Press, Durham, NC,
1992.
14. F. Eric and S. Shenker, Learning and Implementation on the Internet, 1997.
15. S. Giordano, “Mobile ad hoc networks,” in Handbook of Wireless Networks and Mobile Com-
puting. Wiley, New York, 2001
371
REFERENCES


16. S. Giordano and I. Stojmenovic, “Position Based Ad Hoc Routes in Ad Hoc Networks,” in
Handbook of Ad Hoc Wireless Networks, M. Ilyas (Ed.). CRC Press, to appear.
17. E. Kalai and E. Lehrer, “Rational Learning Leads to Nash Equilibrium,” Econometrica, 61, 5,
1019“1045, September 1993.
18. A. Westerlund, L. Feeney, and B. Ahlgren, “Spontaneous Networking: An Application-Oriented
Approach to Ad Hoc Networking.” IEEE Communications Magazine, June 2001.
19. J. Li and J. Jannotti and D. De Couto and D. Karger and R. Morris, “A Scalable Location Ser-
vice for Geographic Ad Hoc Routing,” in Proceedings of ACM MOBICOM 2000.
20. J. P. Macker, V. D. Park, and M. S. Corson, “Mobile and Wireless Internet Services: Putting the
Pieces Together,” Communication Magazine, June 2001.
21. S. Marti, T. J. Giuli, K. Lai, and M. Baker, “Mitigating Routing Misbehavior in Mobile Ad Hoc
Networks,” in Proceedings of the Sixth Annual International Conference on Mobile Computing
and Networking, pp. 255“265. ACM Press, 2000.
22. P. Michiardi and R. Molva, “CORE: A Collaborative Reputation Mechanism to Enforce Node
Cooperation in Mobile Ad Hoc Networks,” in Proceedings of the Sixth IFIP Conference on Se-
curity, Communications, and Multimedia (CMS 2002), 2002.
23. P. Michiardi and R. Molva, “Game Theoretic Analysis of Security in Mobile Ad Hoc Net-
works.” Technical Report RR-02-070, Institut Eurecom, April 2002.
24. P. Michiardi and R. Molva, “Simulation-Based Analysis of Security Exposures in Mobile Ad
Hoc Networks,” in Proceedings of the Mobile Ad Hoc Networks European Wireless Conference,
2002.
25. S. Milgram, “The Small World Problem, Psychology Today, 1967.
26. J. F. Nash, “Equilibrium Points in N-person Games,” Proc. Nat. Acad. Sci. U.S.A., 36, 48“49,
1950.
27. P. R. Kumar and P. Gupta, “The Capacity of Wireless Networks,” IEEE Transactions on Infor-
mation Theory, March 2000.
28. E. M. Belding-Royer, “Routing Approaches in Mobile Ad Hoc Networks,” in Mobile Ad Hoc
Networking, IEEE Press/Wiley, 2004.
29. P. Michiardi and R. Molva, “Ad Hoc Network Security,” in Ad Hoc Networking, IEEE Press/Wi-
ley, 2003.
30. V. Srinivasan, P. Nuggehalli, C. F. Chiasserini, and R. R. Rao, “Cooperation in Wireless Ad Hoc
Networks,” in Proceedings of IEEE Infocom 2003.
31. A. Urpi, M. A. Bonuccelli, and S. Giordano, “Modeling Cooperation in Mobile Ad Hoc Net-
works: A Formal Description of Selfishness,” in Proceedings of WiOpt 2003, pp. 303“312.
32. J. Vaucher, P. Kropf, G. Babin, and T. Jouve, “Experimenting with Gnutella Communities,” in
Distributed Communities on the Web (DCW 2002), Sydney, Australia, April 2002.
33. D. J. Watts, Small Worlds: The Dynamics of Networks between Order and Randomness, Prince-
ton University Press, Princeton, NJ, 1999.
34. S. Zhong, Y. R. Yang, and J. Chen, “Sprite: A Simple, Cheat-Proof, Credit-Based System for
Mobile Ad-Hoc Networks,” Technical Report, Yale/DCS/TR1235, Department of Computer
Science, Yale University, July 2002.
CHAPTER 14




SIMULATION AND MODELING
OF WIRELESS, MOBILE,
AND AD HOC NETWORKS

AZZEDINE BOUKERCHE and LUCIANO BONONI




14.1 INTRODUCTION

Mobile ad hoc networking technologies and wireless communication systems are growing
at an ever faster rate, and this is likely to continue in the foreseeable future. Higher relia-
bility, better coverage and services, higher capacity, mobility management, and wireless
multimedia are all parts of the potpourri. The evolution of new systems and improved de-
signs will always depend on the ability to predict mobile, wireless, and ad hoc networks™
performance using analytical or simulation methods. Modeling and simulation are tradi-
tional methods used to evaluate wireless network designs. To date, mathematical model-
ing and analysis have brought some insights into the design of such systems. However, an-
alytical methods are often not general or detailed enough for evaluation and comparison
of various proposed wireless and mobile systems and their services. Thus, simulation can
significantly help system engineers to obtain crucial performance characteristics.
However, detailed simulations of these systems may require excessive amounts of CPU
time, and their execution on sequential machines has long been known to have computa-
tional requirements that far exceed the computing capabilities of the fastest available ma-
chines. For instance, it is not unusual for simulations of large wired and wireless networks
to require hundreds hours or even days of machine time. As a consequence, the develop-
ment of methods to speed up simulations has recently received a great deal of interest [6,
7, 8, 9, 22, 38, 65].
With the ever increasing use of simulation for designing large and complex systems,
wireless mobile and ad hoc networks have brought several challenges to the parallel and
373
Mobile Ad Hoc Networking. Edited by Basagni, Conti, Giordano, and Stojmenovic.
ISBN 0-471-37313-3 © 2004 Institute of Electrical and Electronics Engineers, Inc.
374 SIMULATION AND MODELING OF WIRELESS, MOBILE, AND AD HOC NETWORKS


distributed discrete-event simulation (PDES) community. The challenges require not only
extension of and advances in current parallel and distributed simulation methodologies,
but also the discovery of innovative approaches and techniques to deal with the rapidly ex-
panding expectations of wireless network designers [6].
In this chapter, we shall present some guidelines related to Mobile Ad Hoc Networks
(MANETs) modeling and simulation, several sequential network simulation testbeds, and
distributed simulation testbeds for wireless and mobile networks. We shall also address
the challenges PDES community has to face in order to design high-performance simula-
tors.


14.2 DESIGN AND MODELING OF WIRELESS AND MOBILE
AD HOC NETWORKS

In this section, we shall introduce the basic characteristics and major issues pertaining to
MANETs™ modeling and simulation. A complete definition of all aspects of interest and a
fit-all solution for simulation is not possible and out of the scope in this chapter, because
it depends on the objectives sought by the designers and the assumptions they have made.
Thus, we will point out only some of the most promising and interesting challenges and
solutions to the modeling of mobile ad hoc networking and communications, and we will
present the state of the art of simulation of wireless, mobile, and ad hoc systems. The
main purpose of a simulation-based study for a MANET system is to obtain detailed in-
formation about performance figures, behavior, overheads, quality of service, and many
other metrics regarding the system, protocols, and policies adopted at many levels of the
ISO/OSI protocol stack [12, 18, 23, 29, 56]. Among all the model parameters, one defined
as “factor” is selected as the varying parameter whose effect on the performance indices is
to be evaluated [29]. Evaluating system performance via modeling and simulation con-
sists of two preliminary steps: (1) defining the system model, and (2) adopting the appro-
priate simulation technique to estimate the metrics needed to evaluate the performamce of
the system. In what follows, we will first talk about MANET modeling. Some concepts
can be considered general for every wireless and mobile system (e.g., wireless PCS, cellu-
lar networks), whereas others can be considered specific to MANETs.

14.2.1 Mobile Ad Hoc Network Modeling
As stated before, it is not convenient to talk about MANET models without defining the
set of objectives and questions the simulation experiments should answer to. Every sys-
tem model is tailored depending on the goal of the simulation project. Any unrequired ad-
ditional detail will introduce overheads, possible errors and a slowdown of the simulation
process [26]. Any missing detail relevant for the performance evaluation of the system
will also introduce errors and lead to approximated results and the need for additional
model updates [15, 26]. General-purpose models are known to be very complex and hard
to adapt to specific system models. Today, many simulation tools provide a library of sim-
ulation models written by professional modelers and researchers [20, 45, 46, 47, 55].
Many times, when incremental updates are performed by different people, the model vali-
dation becomes a time-consuming and difficult task to overcome [15]. Most of the times,
models are supplied or exchanged without any comments and/or documentation, requir-
ing a great effort of designers to interpret and validate them [15]. Today, most of the mod-
375
14.2 DESIGN AND MODELING OF WIRELESS AND MOBILE AD HOC NETWORKS


els can be defined by using object-oriented paradigms and languages, such as Java,
C/C++, and OTcl/Tk, just to mention a few. This makes it possible and more practical to
extend, adopt, exchange, and reuse existing models in new simulation projects. Inheri-
tance allows us to create module hierarchies and instances of complex objects, with a sim-
ple management of model libraries. Widespread adoption of object oriented-languages
works in favor of model distribution among researchers. C++ models and tools are usual-
ly adopted and preferred to Java-based tools for simulation-performance purposes. Mod-
eling component-based units can be performed with the adoption of high-level composi-
tional languages and a set of application tools [45, 46, 47, 55].
In the performance evaluation of a wireless, mobile ad hoc system, every simulation
experiment should be done under a variety of modeling conditions and factors, in order to
capture detailed and “realistic” effects of the real system. These conditions should be well
defined and may have wide and clear interactions at various levels in the model. As an ex-
ample, correct model design should evaluate a priori any possible relationship among
physical, topology, and mobility levels, up to the protocol layers such as Medium Access
Control, Logical Link Control, Network, Transport, and Application. Examples of such
conditions include transmission ranges, power consumption, detection thresholds, data-
traffic sources and loads, buffering storage, user mobility and topology restrictions, signal
propagation and obstacles, interference and bit errors, just to mention a few.
Figure 14.1 shows a roadmap of some modeling issues that will be considered in this
chapter. The edge-based representation of the multiple effects, relationships, and condi-
tions among the modeling issues is shown just to put in some evidence the nontrivial work
of the modeler. Also, Figure 14.1 emphasizes that mobility plays a central role in the mod-
el design. All of these conditions need to be represented and managed within the system
model, by means of well-defined and efficiently manageable data structures. Many solu-
tions which model the test conditions, in many simulation studies, have been proposed in
the literature for wireless and mobile system models, and will be discussed in this chapter.
Specifically, simulation models for wireless and mobile systems in general, and MANETs


Memory Channel(s)
Devices Energy 1D, 2D, 3D
Application
User Money Resources Simulated Area Obstacles
Resources QoS Bouncing
System Host Leave & Replace
Torus
Border Policy
Overload Performance Figures
Underload
CBR,VBR,...
Uniform, Normal
MH distribution
Load (traffic)
Hot Spot
Monodirectional
initial steady state Real sample
Bidirectional
Link and Topology
(A)symmetry... absolute
Mobility
relative
Closed
Exposed term. System Arrivals
Collision Domain Balanced
Hidden term.
Open (interarrivals)
Capture effect...
Free Space
Error Model Propagation Model
SINR, SNR TwoRay
BER, FER Shadowing...
Gilbert ...
Interference Model Coverage Area
Fading (Ricean, Rayleigh) Reflection Scattering Thresholds: CTX, RTX ... Antenna beams
Shadowing Refraction Diffraction Transmission, Detection, Interference areas


Figure 14.1. The modeling roadmap.
376 SIMULATION AND MODELING OF WIRELESS, MOBILE, AND AD HOC NETWORKS


in particular, have to deal with at least two innovative concepts with respect to wired net-
work models: the user-mobility and open-broadcast nature of the wireless medium. In this
chapter we will discuss the model definition issues related to these innovative concepts
for wireless mobile systems, with a special attention to MANETs. Our presentation starts
from the bottom and proceeds to the upper levels, that is, from physical, topological, and
mobility models, up to protocol layers. The model implementation would depend on the
model-definition languages and simulation techniques and tools adopted, thereby requir-
ing additional validation and verification efforts. Hence, we will not discuss in detail the
model implementation, verification, and validation in this chapter.

14.2.1.1 Simulated Area and Boundary Policy. In this section, we shall discuss
the simulated area and the boundary policy concepts, as well as a relevant set of assump-
tions related to the design and modeling of the simulated area, which may have many ef-
fects on the simulation of the target system [3, 12, 13, 32, 55]. This area is the virtual the-
ater of execution of the simulation, and the area size is not important in this discussion.
The area size becomes important when coupled with other parameters governing the mo-
bility, propagation, and node-density models considered in the proposed scenario.
First of all, the simulated area of interest is limited (i.e., it is bounded by limit bor-
ders); it can be mono- or multidimensional, and can be represented by Cartesian coordi-
nates1 as follows:

Monodimensional (1-D) area is a simple linear path for a set of MHs (e.g., a simple
highway-simulation model). The relevant parameter is one single x coordinate along
the linear path, varying in the limited range [minX, maxX]. Such a model can be
used in cellular systems, assuming a linear path between a set of adjacent cells, and
it is infrequently used in MANET system simulation.
Bidimensional (2-D) areas are the most used models because they allow us to embed
and map any possible user path in a real (flat) geographical area. Every portion of a
real geographical area can be mapped on a 2-D grid with (x, y) coordinates varying in
the limiting ranges [minX, maxX] and [minY, maxY]. Definition of subgridding cells
can be exploited to manage and sample object distributions. As an example, hierar-
chies of grid cells can simplify the management of “neighbor” objects in adjacent
cells, and can support object distribution policies (e.g., n objects per grid cell). When
object density evolution is required to be evaluated, grids allow a consistent, snap-
shot-based sampling and runtime calculation of the objects™ distribution.
3-D models. Sometimes, 2-D models can be extended to three-dimensional space
models (x, y, z); for example, when modeling user mobility inside buildings with
many floors, user mobility can be described by including vertical movements, as in
staircases and elevators [34].

The simulated area may also be enriched with obstacles, affecting user mobility and
propagation of signals. A brief discussion will be presented in the following sections
about propagation and mobility models. Obstacles can be modeled and realized as addi-
tional data structures.
The boundary policy is another relevant characteristic of the simulated area that one
might consider in the model design. This policy defines the behavior of the mobile hosts

<<

. 71
( 87 .)



>>