Proximity detection in distributed simulation of wireless mobile systems

ABSTRACT

The distributed and the Grid Computing architectures for the simulation of massively populated wireless systems have recently been considered of interest, mainly for cost reasons. Solutions for generalized proximity detection for mobile objects is a relevant problem, with a big impact on the design and the implementation of parallel and distributed simulations of wireless mobile systems. In this paper, a set of solutions based on tailored data structures, new techniques and enhancements of the existing algorithms for generalized proximity detection are proposed and analyzed, to increase the efficiency of distributed simulations. The paper includes the analysis of computation complexity of the proposed solutions and the performance evaluation of a testbed distributed simulation of ad hoc network models. Recent works have shown that the performance of distributed simulation of dynamic complex systems could benefit from a runtime migration mechanism of model entities, which reduces the communication overheads. Such migration mechanisms may interfere with the generalized proximity detection implementations. The analysis performed in this paper illustrates the effects of many possible compositions of the proposed solutions, in a real testbed simulation framework.

REFERENCES

• 1: Blelloch, G., Narlikar, G. A practical comparison of N-body algorithms. Parallel Algorithms. Series in Discrete Mathematics and Theoretical Computer Science, Volume 30, 1997.
• 2: Luciano Bononi , Michele Bracuto , Gabriele D'Angelo , Lorenzo Donatiello, Performance analysis of a parallel and distributed simulation framework for large scale wireless systems, Proceedings of the 7th ACM international symposium on Modeling, analysis and simulation of wireless and mobile systems, October 04-06, 2004, Venice, Italy [doi>10.1145/1023663.1023676]
• 3: Luciano Bononi , Michele Bracuto , Gabriele D'Angelo , Lorenzo Donatiello, A New Adaptive Middleware for Parallel and Distributed Simulation of Dynamically Interacting Systems, Proceedings of the Eighth IEEE International Symposium on Distributed Simulation and Real-Time Applications (DS-RT'04), p.178-187, October 21-23, 2004 [doi>10.1109/DS-RT.2004.3]
• 4: Bononi, L., Bracuto, M., D'Angelo, G., Donatiello, L. Analysis of High Performance Communication and Computation Solutions for Parallel and Distributed Simulation. HPCC '05: Springer LNCS Proceedings of the 2005 International Conference on High Performance Computing and Communications.
• 5: Luciano Bononi , Michele Bracuto , Gabriele D'Angelo , Lorenzo Donatiello, Scalable and Efficient Parallel and Distributed Simulation of Complex, Dynamic and Mobile Systems, Proceedings of the 2005 Workshop on Techniques, Methodologies and Tools for Performance Evaluation of Complex Systems, p.136, September 19-19, 2005 [doi>10.1109/FIRB-PERF.2005.17]
• 6: Luciano Bononi , Gabriele D'Angelo , Lorenzo Donatiello, HLA-based Adaptive Distributed Simulation of Wireless Mobile Systems, Proceedings of the seventeenth workshop on Parallel and distributed simulation, p.40, June 10-13, 2003
• 7: Neville Thomas, Dynamic Grid-Based Multicast Group Assignment in Data Distribution Management, Proceedings of the Fourth IEEE International Workshop on Distributed Simulation and Real-Time Applications, p.47, August 25-27, 2000
• 8: DMSO: Defense Modeling and Simulation Office. High Level Architecture RTI Interface Specification, Vers. 1.3, 1988
• 9: Richard M. Fujimoto, Parallel and Distribution Simulation Systems, John Wiley & Sons, Inc., New York, NY, 1999
• 10: Gao, J., Guibas, L.J., Nguyen, A. Distributed Proximity Maintenance in Ad Hoc Mobile Networks. DCOSS '05: Proceedings of First IEEE International Conference on Distributed Computing in Sensor Systems.
• 11: IEEE STD 1516-2000. Standard for modeling and simulation, High Level Architecture (HLA).
• 12: Zhengrong Ji , Junlan Zhou , Mineo Takai , Jay Martin , Rajive Bagrodia, Optimizing parallel execution of detailed wireless network simulation, Proceedings of the eighteenth workshop on Parallel and distributed simulation, May 16-19, 2004, Kufstein, Austria [doi>10.1145/1013329.1013356]
• 13: Valeri Naoumov , Thomas Gross, Simulation of large ad hoc networks, Proceedings of the 6th ACM international workshop on Modeling analysis and simulation of wireless and mobile systems, September 19-19, 2003, San Diego, CA, USA [doi>10.1145/940991.941001]
• 14: L. Felipe Perrone , David M. Nicol, Using N-Body Algorithms for Interference Computation in Wireless Cellular Simulations, Proceedings of the 8th International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems, p.49, August 29-September 01, 2000
• 15: Jeff S. Steinman , Frederick Wieland, Parallel proximity detection and the distribution list algorithm, Proceedings of the eighth workshop on Parallel and distributed simulation, p.3-11, July 06-08, 1994, Edinburgh, Scotland, United Kingdom
• 16: Kevin Walsh , Emin Gün Sirer, Staged simulation: A general technique for improving simulation scale and performance, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.14 n.2, p.170-195, April 2004 [doi>10.1145/985793.985797]
• 17: Frederick Wieland , David Carnes , Gregory Schultz, Using quad trees for parallelizing conflict detection in a sequential simulation, Proceedings of the fifteenth workshop on Parallel and distributed simulation, p.117-123, May 15-18, 2001, Lake Arrowhead, California, United States

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.8 Types of Simulation
          Subjects: Discrete event

Additional Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.8 Types of Simulation
          Subjects: Distributed

General Terms:
Algorithms, Design, Experimentation, Performance

Keywords:
data distribution management, distributed simulation, proximity detection, wireless systems