<<

. 77
( 87 .)



>>



STAGE 2 routing path

possible path

Cell incarnations


process process
2,1 2,n(2)


Figure 14.6 Logical interconnection between levels of the parallel simulator.




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


the null-messages paradigm, whereas communications within Stage 2 are based on an op-
timistic scheme [30].
The implementation is based on an object-oriented methodology using C++ as the pro-
gramming language, which makes it easy to maintain and flexible to any changes. Every
MH object is constructed as a base class with parameters that are generalized to all mobile
hosts. The four classes of mobiles (workers, static users, wanderers, and travelers) are de-
rived from the base MH class. MH objects are created in Stage 1 container processes,
whereas cell objects are created in Stage 2 container processes.
Three levels in the SWiMNet simulator have been defined, in which logical activities
of objects are elaborated:

1. Movement precomputation (Level 1) is composed of Nmb mobile host incarnations.
2. Event sorting (Level 2) is composed of Ncells event sorters.
3. Channel allocation simulation (Level 3) is composed of Ncells cell incarnations.

The communications within and between the two stages are shown in Figure 14.6.
Every MH incarnation process generates events for each MH it maintains. Then, those
events are sent to the event sorter process (ES) for the cell where the event takes place.
The MH incarnations are independent of each other. Thus, activities of Level 1 are com-
pletely parallelizable. Similarly, event sorters are independent of each other. However, cell
incarnations, where channel management simulation takes place, are mutually dependent.
In SWiMNet, the optimism lies in the following: every time a move-in event is simulat-
ed at any cell incarnation, the latter optimistically assumes that the call is still on, unless it
already received notification that the call was blocked by means of a call blocked mes-
sage. In the case in which a late notification is received, that is, a call blocked message is
received after the corresponding move-in event has been simulated, a rollback is per-
formed that retracts and corrects the simulations that follow and include the move-in
event. A call blocked message is sent by any cell incarnation whenever a move-out event
is simulated, if the simulation of the corresponding channel request event in the event cou-
ple did not actually result in a channel being allocated. This implies that from Level 1, it is
necessary to keep track of at least the event that follows every move-out event in the se-
quence of events for the same mobile host. This information may then be used to con-
struct a call blocked message.
Rolling back the computation might result in the need for retracting an incorrectly sent
call blocked message by means of a call allocated message. For instance, let us assume
that a call was notified as blocked because of channel unavailability after a channel was
allocated to another call. If the allocated call turns out to be already blocked in a previous
cell, then the call that was notified as blocked can indeed be allocated. A call blocked and
a call allocated message relative to the same call correspond to a pair of antimessages in
Time Warp simulations [30, 31], hence a sign can be associated with these messages. In a
Time Warp simulator, a call blocked message has a positive sign, whereas a call allocated
message has a negative sign.
Due to the optimistic assumption, the elaboration of a simulation message whose cor-
responding precomputed event was already elaborated always causes a rollback. However,
the way in which data are stored in the simulator allows rollbacks to be optimized, i.e.,
only a portion of precomputed events need to be involved in the rollback, and such a por-
tion is exactly computed without the need to inspect any additional event.
405
REFERENCES


The simulator is automatically generated by the master process, which reads the de-
scription file of the simulation model and partitions the model into two stages. The de-
scription file includes the mobility model, the call arrival model, the cellular system map,
the system architecture, the experiment seed, and the simulation time of termination. The
main tasks of the master are (1) generating parameters for every single logical entity, i.e.,
positions, speeds, movement times, etc. for each mobile host incarnation, according to the
general description of the mobility model; and (2) deciding the number of processes per
stage and mapping the processes to processors. Process mapping is an important factor in
improving the efficiency of parallel simulation protocols. Currently, a simple static map-
ping discipline has been adopted: given a number of processors allocated to the simula-
tion, half of the processors are used for Stage 1 and half for Stage 2.
Performance analysis of SWiMNet applied to wireless and mobile system can be found
in [7, 9]. Further work is underway to evaluate its performance for mobile ad hoc networks.


14.4 CONCLUSION

This chapter focuses on several challenging design and modeling aspects of wireless, mo-
bile, and ad hoc networks. We presented a discussion of modeling issues related to physi-
cal transmission and interference, topology, mobility, workload, and performance figures
for mobile ad hoc networks simulation.
Modeling and simulation are traditional methods to evaluate large-scale wireless and
multihop network designs. However, modeling is often intractable with today™s large and
complex mobility and traffic patterns in wireless and multihop systems. Thus, researchers
have turned increasingly to the use of simulation studies of these systems. Though, de-
tailed simulations of large-scale, wireless, mobile, and ad hoc networks require enormous
execution time and large amounts of memory due to the complexity involved in the simu-
lation and mobility models. Even on high-performance workstations, the execution time is
in the order of days and memory requirements on the order of gigabytes, which impose
restrictions on the type of systems that can be simulated. Parallel and distributed simula-
tion (PDES) could be exploited to overcome these problems.
In this chapter, both sequential and parallel simulation tools for wireless mobile and ad
hoc networks have been reviewed. We have also presented some recent examples of simu-
lation methodologies to improve the simulation run time of these networks using PDES
techniques.


ACKNOWLEDGMENTS

This work was supported by the Canada Research Program and Canada Foundation for In-
novation (AB), and the Italian MIUR FIRB-PERF “Performance Evaluation of Complex
Systems: Techniques, Methodologies and Tools” project funds (LB).


REFERENCES

1. R. Bagrodia, R. Meyer, et. al., “PARSEC: a Parallel Simulation Environment for Complex Sys-
tems,” UCLA Technical report, 1997.
406 SIMULATION AND MODELING OF WIRELESS, MOBILE, AND AD HOC NETWORKS


2. H. Bertoni, Radio Propagation for Modern Wireless Systems, Prentice-Hall, Upper Saddle Riv-
er, NJ, 2000.
3. C. Bettstetter, “Smooth is Better than Sharp: a Random Mobility Model for Simulation of Wire-
less Networks,” in Proceedings of ACM International Workshop on Modeling, Analysis and Sim-
ulation of Wireless and Mobile Systems (MSWiM™01), Rome, Italy, July 2001.
4. C. Bettstetter, H. Hartenstein, and X. P©rez-Costa, “Stochastic Properties of the Random Way-
point Mobility Model: Epoch Length, Direction Distribution and Cell-Change Rate,” in Pro-
ceedings of the 5th ACM International Workshop, MSWiM2002, September 2002.
5. C. Bettstetter, “Mobility Modeling in Wireless Networks: Categorization, Smooth Movement,
and Border Effects,” Mobile Computing and Communications Review, 5, 3, July 2001.
6. L. Bononi, G. D™Angelo, and L. Donatiello “HLA-based Adaptive Distributed Simulation of
Wireless Mobile Systems,” in Proceedings of IEEE/ACM International Workshop on Parallel
and Distributed Systems (PADS™03), San Diego, CA, June 2003.
7. A. Boukerche, S. K. Das, and A. Fabbri “SWiMNet: A Scalable Parallel Simulation Testbed for
Wireless and Mobile Networks,” ACM/Kluwer Wireless Networks, 7, 467“486, 2001.
8. A. Boukerche and A. Fabbri “Partitioning PCS Networks for Distributed Simulation,” in IEEE High
Performance Computing (HiPC), LNCS 1970, Springer-Verlag, New York, pp. 449“458, 1970.
9. A. Boukerche, S. K. Das, A. Fabbri, and O. Yildiz, “Exploiting Model Independence for PCS
Network Simulation,” in Proceedings of ACM/IEEE Parallel and Distributed Simulation
(PADS™99), pp. 166“173, Atlanta, 1999.
10. A. Boukerche and C. Tropper,”Parallel Simulation on the Hypercube Multiprocessor,” in Dis-
tributed Computing, Spring Verlag, New York, 1993.
11. A. Boukerche, “Time Management in Parallel Simulation,” in High Performance Cluster Com-
puting, Vol. 2, B. Rajkumar (Ed.), Prentice-Hall, Upper Saddle River, NJ, 1999.
12. J. Broch, D. A. Maltz, D. B. Johnson, Y.-C. Hu, and J. Jetcheva, “A Performance Comparison of
Multi-Hop Wireless Ad Hoc Network Routing Protocols,” in Proceedings of MobiCOM™99,
Dallas Texas, October 1998; also at http://www.monarch.cs.cmu.edu
13. T. Camp, J. Boleng, and V. Davies, “A Survey of Mobility Models for Ad Hoc Network Re-
search,” Wireless Communications and Mobile Computing, Special issue on Mobile Ad Hoc
Networking: Research, Trends and Applications, 2002.
14. C. Carothers, R. Fujimoto, Y.-B. Lin, and P. England, “Distributed Simulation of Large-scale
PCS Networks,” in Proceedings of the 2nd International Workshop on Modeling, Analysis, and
Simulation of Computer and Telecommunication systems, February 1994.
15. D. Cavin, Y. Sasson, and A. Schiper, “On the Accuracy of MANET Simulators,” in Proceedings
of POMC™02, Toulouse, France, October 2002.
16. K. M. Chandy and J. Misra, “Distributed Simulation: A Case Study in Design and Verification
of Distributed Programs,” IEEE Transactions on Software Engineering, SE-5, 440“452, Sep-
tember 1979.
17. S. R. Das and K. Jones, “Time-Parallel Algorithms for Simulation of MAC Protocols,” in Pro-
ceedings of MASCOTS 2001, Cincinnati, Ohio, August 2001.
18. S. Corson and J. Macker, “Mobile Ad Hoc Networking (MANET): Routing Protocol Perfor-
mance Issues and Evaluation Considerations,” RFC 2501, Jan. 1999.
19. DMSO: Defence Modeling and Simulation Office (1998), High Level Architecture RTI Inter-
face Specification, Version 1.3, 1998.
20. FraSiMo, Framework for Simulation of Mobility in OMNET++, TKN Berlin, see http://www-
tkn.ee.tu-berlin.de/research/research\_texte/framework.html
21. R. M. Fujimoto, “Parallel Discrete Event Simulation,” Communications of the ACM, 33, 10,
30“53, October 1990.
407
REFERENCES


22. R. M. Fujimoto, Parallel and Distributed Simulation, Wiley, New York, 2000.
23. Gerla M., Tang K., and Bagrodia R. “TCP Performance in Wireless Multi-hop Networks,” in
Proceedings of IEEE WMCSA™99, New Orleans, LA, February 1999.
24. A. C. Chandra, V. Gummalla, and J. O. Limb, “Wireless Medium Access Control Protocols,”
IEEE Communications Surveys and Tutorials, 2000.
25. Georgia Institute of Technology, RTI KIT, see http://www.cc.gatech.edu/computing/pads/
fdk.html
26. J. Heidemann, N. Bulusu, J. Elson, C. Intanagonwiwat, K.-C. Lan, Y. Xu, W. Ye, D. Estrin, and
R. Govindan, “Effects of Detail in Wireless Network Simulation,” in Proceedings of the SCS
Multiconference on Distributed Simulation, Phoenix, AZ, January 2001.
27. X. Hong, T. J. Kwon, M. Gerla, D. L. Gu, and G. Pei, “A Mobility Framework for Ad Hoc Wire-
less Networks,” Lecture Notes in Computer Science, 2001.
28. X. Hong, M. Gerla, G. Pei, and C.-C. Chiang, “A Group Mobility Model for Ad Hoc Wireless
Networks,” in Proceedings of ACM MSWiM™99, Seattle, 1999.
29. R. Jain, The Art of Computer Systems Performance Evaluation, Wiley, New York, 1991.
30. D. R. Jefferson, “Virtual Time,” ACM Transactions on Programming Languages and Systems, 7,
3 404“425, July 1985.
31. D. R. Jefferson and H. Sowizral, “Fast Concurrent Simulation Using the Time Warp Mecha-
nism,” in SCS Multiconference on Distributed Simulation, pp. 63“69, 1985.
32. P. Johansson, T. Larsson, N. Hedman, B. Mielczarek, and M. Degermark, “Scenario-based Per-
formance Analysis of Routing Protocols for Mobile Ad Hoc Networks,” in Proceedings of Mo-
biCOM™99, pp. 195“206, Seattle, 1999.
33. K. Jones, “Parallel and Distributed Simulation Techniques and Applications,” Ph.D. Proposal,
November 2001, University of Cincinnatti.
34. T. S. Kim, J. K. Kwon, and D. K. Sung, “Mobility and Traffic Analysis in Three-Dimensional
High-Rise Building Environments,” IEEE Transactions on Vehicular Technology, 49, 5,
1633“1640, May 2000.
35. Y. Y. Kim and S. Q. Li, “Modeling Multipath Fading Channel Dynamics for Packet Data Perfor-
mance Analysis,” Wireless Networks, 6, December 2000.
36. C. Y. Lee William, Mobile Cellular Telecommunications: Analog and Digital Systems, Mc-
Graw-Hill, New York, 1989.
37. M. C. Little and D. L. McCue, “Construction and Use of a Simulation Package in C++,” Com-
puting Science Technical Report, University of Newcastle upon Tyne, Number 437, July 1993;
also appeared in C User™s Journal, 12, 3, March 1994.
38. M. Liljenstam and R. Ayani, “A Model for Parallel Simulation of Mobile Telecommunication
Systems,” in Proceedings of the 4th International Workshop on Modeling, Analysis and Simula-
tion of Computer and Telecommunication Systems (MASCOTS), San Jose, CA. 1996.
39. Y.-B. Lin and P. Fishwick, “Asynchronous Parallel Discrete Event Simulation,” IEEE Transac-
tions on Systems and Cybernetics, 1995.
40. M. Liljenstam, R. Ronngren, and R. Ayani, “Partitioning WCN Models for Parallel Simulation
of Radio Ressource Management,” ACM/Kluwer Wireless Networks, 7, 3, 307“324, 2001.
41. D. M. Lucantoni, M. F. Neuts, and A. R. Reibman, “Method for Performance Evaluation of
VBR Video Traffic Models,” IEEE/ACM Transactions on Networking, 2, 2, April 1994.
42. J. G. Markoulidakis, G. L. Lyberopoulos, D. F. Tsirkas, and E. D. Sykas, “Mobility Modeling in
Third Generation Mobile Telecommunication Systems,” IEEE Personal Communications,
41“56, August 1997.
43. R. A. Meyer and R. L. Bagrodia, “Improving Lookahead in Parallel Wireless Network
Simulation,” in Proceedings of 6th International Workshop on Modeling, Analysis and
408 SIMULATION AND MODELING OF WIRELESS, MOBILE, AND AD HOC NETWORKS


Simulation of Computer and Telecommunication Systems, Montreal, Canada, pp. 262“267,
July 1998.
44. MPI Primer, Developing with LAM, Ohio Supercomputer Center, The Ohio State University,
1996.
45. NS-2 Simulation Tool, see http://www.isi.edu/nsnam/ns/; NS-2 mobility extension from Rice
Monarch, see http://www.monarch.cs.rice.edu/cmu-ns.html
46. A. Varga, OMNET++, in the column “Software Tools for Networking,” IEEE Network Interac-
tive, 16, 4, July 2002; also in http://whale.hit.bme.hu/omnetpp/
47. OPNET simulation tool, see http://www.mil3.com/home.html
48. J. Panchal, O. Kelly, J. Lai, N. Mandayam, A. Ogielski, and R. Yates, “Wippet, A Virtual Testbed
for Parallel Simulations of Wireless Networks,” in PADS 98, Banff, Canada, June 1998.
49. A. C. Palaniswamy and P. A. Wilsey, “An Analytical Comparison of Periodic Checkpointing and
Incremental State Saving,” in Proceedings of the 1993 Workshop on Parallel and Distributed
Simulation, pp. 127“134.
50. Parallel and Distributed Network Simulator, PDNS, see http://www.cc.gatech.edu/computing/c
ompass/pdns/
51. K. Perumalla, R. Fujimoto, and A. Ogielski, “A TED: A Language for Modeling
Telecommunication Networks,” ACM SIGMETRICS Performance Evaluation Review, 25, 4,
March, 1998.
52. B. Ramamurthi, D. J. Goodman, and A. Saleh, “Perfect Capture for Local Radio Communica-
tions,” IEEE JSAC, SAC-5, 5, June 1987.
53. T. S. Rappaport, Wireless Communications: Principles and Practice, 2nd ed., Prentice-Hall,
Upper Saddle River, NJ, 2002.
54. E. M. Royer, P. M. Melliar-Smith, and L. E. Moser, “An Analysis of the Optimum Node Densi-
ty for Ad Hoc Mobile Networks,” in Proceedings of IEEE International Conference on Commu-
nications (ICC), Helsinki, June 2001.
55. S. Shah, E. Hernandez, and A. Helal, “CAD-HOC: A CAD Like Tool for Generating Mobility
Benchmarks in Ad-Hoc Networks,” in Proceedings of SAINT™02, Nara, Japan, February 2002.
56. W. Stallings, Wireless Communications and Networks, Prentice-Hall, Upper Saddle River, NJ,
2001.
57. Su, W. K. and C. L. Seitz, “Variants of the Chandy-Misra-Bryant Distributed Discrete Event
Simulation Algorithm,” in Proceedings of the SCS Multiconference on Distributed Simulation,
Vol. 21, No. 2, 1989.
58. M. Takai, R. Bagrodia, K. Tang, and M. Gerla, “Efficient Wireless Network Simulations with
Detailed Propagation Models,” ACM/Kluwer Wireless Networks, 7, 3, 283“306, 2001.
59. M. Takai, J. Martin, and R. Bagrodia, “Effects of Wireless Physical Layer Modeling in Mobile
Ad Hoc Networks,” in Proceedings of MobiHOC™01, Long Beach, CA, October 2001.
60. J. Tian, J. Hahner, C. Becker, I. Stepanov, and K. Rothermel, “Graph-based Mobility Model for
Mobile Ad Hoc Network Simulation,” in Proceedings of 35th Annual Simulation Symposium,
San Diego, CA, April 2002.
61. K. H. Wang and B. Li, “Group Mobility and Partition Prediction in Wireless Ad Hoc Net-
works,” in Proceedings of IEEE International Conference on Communications (ICC™02), New
York, April 2002.

<<

. 77
( 87 .)



>>