автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.13, диссертация на тему:Методы и средства построения моделирующих комплексов и обучающих систем на основе технологий распределенного моделирования

ВВЕДЕНИЕ.

ГЛАВА 1. ТЕХНОЛОГИИ РАСПРЕДЕЛЕННОГО МОДЕЛИРОВАНИЯ.

1.1. Аналитический обзор архитектур распределенного моделирования.

1.1. ¡.Развитие архитектур распределенного моделирования.

1.1 ^.Отечественные разработки в области распределенного моделирования.

1.1.3. Сравнение архитектуры с НЬА сОШиАЬБР.

1.2. Архитектура распределенного моделирования НЬА и формирование требований по ее доработке.

1.2.1. Общая структура системы на базе архитектуры высокого уровня. Основные понятия и определения.

1.2.4. Система исполнения.

1.2.5. Механизм управления обменом данными.

1.2.4.2 Механизм управления ходом времени в процессе моделирования.

1.3. Задачи по доработке архитектуры высокого уровня.

ВЫВОДЫ ПО ГЛАВЕ 1.

ГЛАВА 2 МОДЕРНИЗАЦИЯ МЕХАНИЗМА УПРАВЛЕНИЯ ОБМЕНА ДАННЫМИ В ХОДЕ РАСПРЕДЕЛЕННОГО МОДЕЛИРОВАНИЯ.

2.1 .аппроксимация информационных полей и сигнатур ограничивающими объемами.

2.2.Формальная постановка задачи аппроксимации.

2.3.Аппроксимации сложных пространственных объемов параллелепипедом с минимальным объемом.

2.4.Эффективный алгоритм аппроксимации.

2.4.1 .Аппроксимация диаметра.

2.4.2.Вычисление аппроксимирующего параллелепипеда.

2.4.4.Алгоритм для вычисления Вор1(Б).

2.4.5.Алгоритм аппроксимации множества точек ограничивающим параллелепипедом с минимальным объемом.

2.5.Альтернативный реализованный алгоритм.

2.5. ¡.Алгоритм расчета ограничивающего параллелепипеда по методу сетки.

2.6. Экспериментальные исследования разработанного механизма аппроксимации.

2.7. Эксперименты, демонстрирующие преимущества от использования модернизированного метода представления областей подписки и обновления по сравнению со стандартной службой ББМ.

ВЫВОДЫ ПО ГЛАВЕ 2.

ГЛАВА 3. ОПТИМИЗАЦИЯ ГРУПП МНОГОТОЧЕЧНОЙ РАССЫЛКИ В

СИСТЕМАХ РАСПРЕДЕЛЕННОГО МОДЕЛИРОВАНИЯ.

3.1 .Методы представления соединений в ходе распределенного моделирования.

3.2.Формальная постановка задачи опимизации.

3.2.1 Схожесть задачи с «проблемой упаковки рюкзака».

3.2.2. Описание задачи.

3.2.3. Анализ применимости различных методов оптимизации.

3.2.4. Функция затрат.

3.3 .Вычисление времени простоя сообщения в очереди и передачи сообщения по сети.

3.4 Различные ситуации, возникающие при группировке.

3.5. Алгоритм замера производительности.

3.6.Алгоритмы группировки.

3.6. ¡.Алгоритм наибольшего исходящего соединения (НИС).

3.6.2. Алгоритм наибольшего исходящего соединения с ограничением на входе (НИСОВ).

3.6.3.Результаты, показывающие эффективность НИС и НИСОВ.

ВЫВОДЫ ПО ГЛАВЕ 3.

ГЛАВА 4. МЕХАНИЗМ СИНХРОНИЗАЦИИ ХОДА ВРЕМЕНИ В РАЗЛИЧНЫХ ПРОГРАММНО-АППАРАТНЫХ РЕАЛИЗАЦИЯХ.

4.1. Анализ архитектур синхронизации времени.

4.2. Синхронизация времени в ходе распределенного моделирования на основе протокола NTP.

4.2.1. Сетевой протокол времени NTP.

4.2.2. Архитектура системы синхронизации времени.

4.2.3.Реализация модели синхронизации времени.

4.2.4.Конфигурации сети.

4.2.5. Форматы данных.

4.2.6. Временная шкала NTP и ее хронометрия.

4.2.7. Первичная частота и стандарты времени.

4.2.8. Передача времени и частоты.

4.2.9. Определение частоты.

4.3. Эксперимент по применению предложенной архитектуры временной синхронизации.

ВЫВОДЫ ПО ГЛАВЕ 4.

Одной из основных тенденций в разработке систем моделирования является переход от идеологии построения изолированной системы к системам распределенного моделирования. В соответствии с данным подходом, даже тот тренажер (или модель), функционирование которого не требует взаимодействия с другими тренажерами и внешними моделями, должен создаваться с учетом возможности его включения в будущем в систему распределенного моделирования. Основным преимуществом от использования подобного подхода является возможность соединения независимо разработанных тренажеров и моделей в моделирующие комплексы с качественно новыми возможностями. При этом объединяемые тренажеры и модели могут находиться не только на разных компьютерах, но и даже в разных городах, необходимым условием при этом является только наличие компьютерной сети между ними, например Интернет.

Применение систем распределенного моделирования позволяет:

1. Проводить обучение операторов для отработки совместных действий в критических ситуациях (например, отрядов МЧС, службы управления воздушным движением, служб управления транспортными перевозками).

2. Осуществлять поддержку принятия решений при выборе метода проведения операций (например, спасательных операций при стихийных бедствиях).

3. Принимать решения по логистической поддержке.

4. Осуществлять проведение научно-исследовательских экспериментов, в которых задействованы территориально удаленные моделирующие комплексы.

Основными преимуществами от использования систем распределенного моделирования являются:

1. Возможность многократного использования разработанных моделей в составе различных моделирующих комплексов для решения различных задач;

2. Снижение затрат на организацию тренингов и совместных учений различных масштабов;

3. Снижение затрат на эксплуатацию реальной техники (Для отработки групповых действий нет необходимости использовать реальную технику);

4. Снижение загрязнения окружающей среды продуктами технической деятельности;

5. Повышение безопасности процесса обучения совместным действиям.

Поэтому актуальной 'является задача разработки методов и средств построения моделирующих комплексов и обучающих систем на основе технологий распределенного моделирования. Основой практической реализации любой архитектуры распределенного моделирования является среда обмена данными между участниками распределенного моделирования. В качестве базовой среды передачи данных в настоящее время используются локальные и глобальные компьютерные сети. Современным компьютерным сетям присущ ряд ограничений, которые необходимо учитывать при построении систем распределенного моделирования.

Целью диссертационной работы является разработка методов и средств построения систем распределенного моделирования на базе современных сетевых технологий.

В соответствии с поставленной целью в работе решаются следующие задачи:

• анализ существующих технологий и архитектурных решений создания систем распределенного моделирования и выбор архитектуры на базе сформулированных критериев. определение направ шений модернизации выбранной архитектуры для обеспечения ее практической реализуемости на существующих компьютерных сетях.

• модернизация механизма управления обменом данными в ходе распределенного моделирования.

• разработка метода построения систем распределенного моделирования с большим количеством участников.

• разработка механизма обеспечения низкоуровневой временной синхронизации при проведении распределенного моделирования.

Методы исследования и примененный математический аппарат: При работе над диссертацией использовались методы передачи данных в сетях, прикладные методы теории построения вычислительных систем и сетей, теория графов, вычислительная геометрия, алгоритмы прикладной математики, аппарат математической статистики и прикладное программирование.

Научная новизна состоит в следующем:

1. Предложен новый подход к построению распределенных моделирующих комплексов и обучающих систем на базе универсальной стандартизованной архитектуры, основанный на выборе одной из существующих архитектур распределенного моделирования на основе сформулированных функциональных критериев и модернизации выбранной архитектуры для обеспечения ее практической реализуемости на существующих компьютерных сетях.

2. Разработан метод модернизации служб логической фильтрации данных, передаваемых в ходе распределенного моделирования, выбранной архитектуры, позволяющий проводить распределенное моделирование сложных информационных систем на низкоскоростных каналах связи, и проведена экспериментальная оценка результатов, подтверждающая эффективность предложенного метода.

3. Разработан метод решения задачи рационального распределения участников распределенного моделирования по группам многоточечной рассылки, позволяющий минимизировать объем передаваемых данных по каналам связи, а также увеличить количество участников моделирования. Проведенные эксперименты показали эффективность разработанных методов группировки по сформулированным критериям.

4. Предложен механизм корректной низкоуровневой временной синхронизации в информационных системах для выбранной архитектуры распределенного моделирования, позволяющий устранить

U U 1 U U V/ дополнительный сетевой трафик, связанный с несвоевременной посылкой данных.

Практическая ценность. Разработанные методы и алгоритмы реализованы в виде программного обеспечения и позволяют создавать системы распределенного моделирования на основе предложенной архитектуры наиболее эффективно в условиях сложившихся ограничений, накладываемых существующим аппаратным и программным обеспечением вычислительных систем.

На защиту выносятся следующие основные результаты;

1. подход к построению моделирующих комплексов.

2. методы и средства реализации систем распределенного моделирования на базе существующих сетей.

В рамках данного подхода разработаны:

1. метод управления обменом данными в ходе распределенного моделирования на основе логической фильтрации данных.

2. метод снижения загрузки сети за счет использования групп многоточечной рассылки.

3. механизм низкоуровневой временной синхронизации в ходе моделирования.

Содержание работы;

Первый раздел содержит аналитический обзор существующих архитектур распределенного моделирования, выбор архитектуры отвечающей поставленным требованиям и формирование предложений по доработке выбранной архитектуры для обеспечения ее практической реализуемости на существующих компьютерных сетях.

ВЫВОДЫ ПО ГЛАВЕ 4.

В целях снижения сетевого трафика в ходе распределенного моделирования, вызванного рассинхронизацией внутренних часов аппаратных платформ участников распределенного моделирования, предлагается использовать синхронизацию от внешнего источника точного времени.

На основе проведенного анализа архитектур внешней синхронизации выбрана наиболее универсальная и низкостоимостная архитектура. С целью оценки эффективности использования предложенной архитектуры разработан и проведен ряд экспериментов. Результаты экспериментов показали, что при использовании предложенной архитектуры внешней синхронизации возможно снижение сетевого трафика до 60%. В каждом конкретном эксперименте снижение сетевого трафика сильно зависело от отношения общего количества передаваемых данных в ходе распределенного моделирования к размеру пакета синхронизации времени.

В дальнейшей работе предполагается использовать данный критерий для оценки целесообразности применения методов внешней синхронизации.

ЗАКЛЮЧЕНИЕ

Применение технологий распределенного моделирования позволяет создавать обучающие системы и моделирующие комплексы с качественно новыми возможностями, а также обладает рядом преимуществ с точки зрения организации коллективных научно-исследовательских работ, связанных с моделированием, и крупномасштабных учений. Разработка принципиально новой архитектуры распределенного моделирования сопряжена со значительными затратами времени и средств, что особенно важно в условиях жестких финансовых ограничений, свойственных проведению научно-исследовательских работ в нашей стране. В работе решены задачи:

1. На основе анализа существующих технологий распределенного моделирования выбрана наиболее совершенная архитектура на сегодняшний день (2002 год), а именно архитектура высокого уровня НЬА;

2. Выбранная архитектура проанализирована с точки зрения ее практической реализуемости на существующих компьютерных сетях и выделены основные направления ее модернизации. Сформулированные задачи по доработке разделены на две основные группы:

• Логический уровень (уровень функциональности НЬА);

• Уровень аппаратно-программной реализации.

3. В рамках решения задач первой группы по доработке механизмов передачи данных НЬА разработан и реализован метод предварительной фильтрации данных. Проведенный объем экспериментов продемонстрировал высокую эффективность предложенного метода;

4. В рамках решения задач второй группы сформулированы и решены следующие две основные подзадачи:

1.1. Разработан и реализован в виде программного обеспечения метод построения систем распределенного моделирования с использованием передачи данных по методу многоточечной рассылки на основе предложенных и реализованных алгоритмов оптимальной группировки. Проведенные эксперименты показали, что в ряде случаев использование многоточечной рассылки является единственным методом, обеспечивающим необходимое качество передачи сообщений;

1.2. Разработан механизм внешней временной синхронизации на основе использования протокола ШТ. Проведен ряд экспериментов продемонстрировавших целесообразность применения данного технического решения.

Результаты проведенной диссертационной работы сделали возможным построение систем распределенного моделирования на основе предложенной архитектуры и обеспечили их функционирование на существующих сетях в рамках научно-исследовательских и опытно-конструкторских работ, проводившихся по заказу Министерства Обороны России и сводного департамента оборонной промышленности Минпромнауки России.

1. Conceptual Models of the Mission Space (CMMS). Technical Framework Document number: USD/A&T-DMSO-CMMS-0002Defense Modeling and Simulation 0fficel901 N. Beauregard St., Suite 504, Alexandria, VA 22311.

2. Modular Reconfigurable C4I Interface (MRCI). Defense Modeling and Simulation Office.

3. DIS Steering Committee. Standard for Information Technology Protocols for Distributed Interactive Simulation, March 1994. IEEE Standard 1278.

4. DIS Steering Committee. The DIS Vision: A Map to the Future of Distributed Simulation. Version 1, May 1994.

5. Architecture issues for DIS-to-HLA conversion. Technical report 97-014 December 1997 Daniel J. Paterson, Eric Anschuetz, Mark Biddle, Dave Kotick, Thai Nguyen Naval Air Warfare Center Training Systems Division Orlando, FL 32826-3224.

6. Transitioning your DIS simulator to HLA. Deb Fullford, Sue Hoxie, Ben Lubetsky MÄK Technologies 185 Alewife Brook Parkway Cambridge, MA 02138.

7. Aggregate level simulation protocol (ALSP). Mary C. Fischer, PhD US Army Simulation, Training and Instrumentation Command.

8. High Level Architecture Overview and Rules. Dr. Judith Dahmann Defense Modeling and Simulation Office.

9. Department of Defense High Level Architecture Interface Specification, Version 1.3, DMSO, April 1998, http://hla.dmso.mil.

10. Department of Defense High Level Architecture Rules, Version 1.3, DMSO, April 1998, http://hla.dmso.mil.

11. Department of Defense High Level Architecture Object Model Template, Version 1.3, DMSO, April 1998, available at http://hla.dmso.mil.

12. IEEE P1516/D1 Draft Standard for. Modeling and Simulation (M&S) High Level Architecture (HLA) Framework and Rules. Copyrightr 1998 by the Institute of Electrical and Electronics Engineers, Inc.345 East 47th Street, New York, NY 10017, USA.

13. HLA Data Distribution Management: Design Document. Version 0.7 Defense Modeling and Simulation Office.

14. HLA Time Management Design Document. Version 1.0 Defense Modeling and Simulation Office 15 August 1996.

15. N. Roussopoulos and D. Leifker. Direct spatial search on pictorial databases using packed R-trees. Proc. ACM SIGACT-SIGMOD Conf. Principles Database Systems, pages 17-31, 1985.

16. T. Sellis, N. Roussopoulos, and C. Faloutsos. The R + -tree: A dynamic index for multi-dimensional objects. In Proc. 13th VLDB Conference, pages 507-517, 1987.

17. N. Beckmann, H.-P. Kriegel, R. Schneider, and B. Seeger. The R-tree: An efficient and robust access method for points and rectangles. In ACM SIGMOD Int. Conf. on Manag. of Data, pages 322-331, 1990.

18. M. Held, J.T. Klosowski, and J.S.B. Mitchell. Evaluation of collision detection methods for virtual reality y-throughs. In Proc. 7th Canad. Conf. Comput. Geom., pages 205-210, 1995.

19. S. Gottschalk, M.C. Lin, and D. Manocha. OBB-tree: A hierarchical structure for rapid interference detection. In Proc. SIGGRAPH '96, pages 171-180,1996.

20. EE Trans. Visualization and Computer Graphics, 1(3):218-230, September 1995.

21. H. Samet. Spatial Data Structures: Quadtrees, Octrees, and Other Hierarchical Methods. Addison-Wesley, Reading, MA, 1989.

22. O. D. Faugeras and J. Ponce. An object-centered hierarchical representation for 3-d objects: The prism-tree. Computer Vision, Graphics, and Image Processing, 38:1-28, 1987.

23. S. Bespamyatnikh and M. Segal. Covering a set of points by two axis-parallel boxes. In Proc. 9th Canad. Conf. Comput. Geom., pages 33-38, 1997.

24. G. Barequet and S. Har-Peled. Efficiently approximating the minimumvolume bounding box of a point set in three dimensions. In Proc. 10th ACM-SIAM Sympos. Discrete Algorithms, pages 82-91, 1999.

25. O. Egecioglu and B. Kalantari. Approximating the diameter of a set of points in the Euclidean space. Inform. Process. Lett., 32:205-211, 1989.

26. G. E. Andrews. A lower bound for the volume of strictly convex bodies with many boundary lattice points. Trans. Amer. Math. Soc., 106:270-279, 1963.

27. T.M. Chan. Output-sensitive results on convex hulls, extreme points, and related problems. Discrete Comput. Geom., 16:369-387, 1996.

28. K. L. Clarkson and P. W. Shor. Applications of random sampling in computational geometry, II.Discrete Comput. Geom., 4:387-421, 1989.

29. G. T. Toussaint. Solving geometric problems with the rotating calipers. InProc. IEEE MELECON '83, pages A10.02/1-4, 1983.

30. C. Faloutsos and K. I. Lin. FastMap: a fast algorithm for indexing, data-mining and visualization of traditional and multimedia datasets. SIGMOD

31. Record (ACM Special Interest Group on Management of Data), 24(2): 163174, June 1995.f

32. P. Gritzmann and V. Klee. Inner and outer j-radii of convex bodies in f infinite-dimensional normed spaces. Discrete Comput. Geom., 7:255-280,1992.

33. O'Rourke. Finding minimal enclosing boxes. Internat. J. Comput. Inform. Sci., 14:183-199, 1985.

34. Кармен Т. Лейзерсон Ч. Ривест Р. Алгоритмы: Построение и анализ. -М.: Центр непрырывного математического образования, 2000. 304 с.

35. К. Петцке Linux. От понимания к применению М.:«ДМК»,2000.- 572с.

36. Руководство по использованию операционной системы Altlinux Spring 2001 http://www.altlinux.ru

37. Руководство по использованию операционной системы RTLinux 3.1 http ://www.rtlinux.org

38. Руководство по применению программы анализатора сетевого трафика Ethereal версии 0.8.2. http://www.ethereal.com

39. И.И. Елисеева, М.М. Юзбашев Общая теория статистики. М.: «Финансы и статистика», 1999.- 300с.

40. Howard Abrams. Extensible Interest Management for Scalable Persistent Distributed Virtual Environments. Ph.D. Dissertation, Naval Postgraduate School, December 1999.

41. Michael Macedonia, Michael Zyda, David Pratt, and Paul Barham.Exploiting Reality with Multicast Groups: a Network Architecture for Large Scale Virtual Environments. In Virtual Reality Annual International Symposium '95, pages 2-10, March 1995.

42. Thomas W. Mastaglio and Robert Callahan. A Large-Scale Complex Virtual Environment for Team Training. IEEE Computer, 28(7), pages 49-56, July1995.г 45. Steven J. Rak and Daniel J. Van Hook. Evaluation of Grid-Based Relevance

43. Filtering for Multicast Group Assignment. In 14th Workshop on Standards for the Interoperability of Distributed Simulations, pages 739-747, March1996.

44. Christian Huitema. IPv6: The New Internet Protocol, Prentice-Hall, New Jersey, 1996, pg. 46.

45. Chris Greenhalgh and Steve Benford. Boundaries, Awareness and Interaction in Collaborative Virtual Environments. InProceedings Sixth IEEE Workshops on Enabling Technologies: Infrastructure for Collaborative Enterprises, pages 193-198, June 1997.

46. Ф. А. Новиков Дискретная математика для программистов, СПб., Питер 2001

47. Christos Papadimitriou. Computational Complexity, Addison-Wesley, Massachusetts, 1994, pg. 202.

48. Татт У. Теория графов. М.: Мир, 1988,

49. Яблонский С.В. "Введение в дискретную математику" -М.: Наука. 1974г.

50. Tony Ballardie, Paul Francis, Jon Crowcroft. Core Based Trees (CBT) An Architecture for Scalable Inter-Domain Multicast Routing. In Proceedings of SIGCOMM '93, pages 85-94, 1003.

51. D. Cohen and A. Kemkes. User-Level Measurements of DDM Scenarios, Proceedings of the 1998 Spring Simulation Interoperability Workshop, 98S-' SIW-072, March 1998.

52. D. Cohen and A. Kemkes. Applying User-Level Measurements to RTI 1.3

53. Release 2. In Proceedings of the 1998 Fall Simulation Interoperability Workshop, 98F-SIW-132, September 1998.

54. Peter Hoare and Richard Fujimoto. HLA RTI Performance in High Speed LAN Environments. In Proceedings of the 1998 Fall Simulation Interoperability Workshop, pages 501-510, September 1998.

55. Кристофидес H. Теория графов. Алгоритмический подход. М.: Мир, 1978.

56. Майника Э. Алгоритмы оптимизации на сетях и графах. М.: Мир, 1981.

57. Зыков A.A. Основы теории графов. М.: Наука, 1987.

58. Mills, D.L. Network Time Protocol (NTP). DARPA Network Working Group Report RFC-958, M/A-COM Linkabit, September 1985.

59. Mills, D.L. Network Time Protocol (version 2) specification and implementation. DARPA Network Working Group Report RFC-1119, University of Delaware, September 1989.

60. Postel, J. User Datagram Protocol. DARPA Network Working Group Report RFC-768, USC Information Sciences Institute, August 1980.

61. Postel, J. Daytime protocol. DARPA Network Working Group Report RFC867, USC Information Sciences Institute, May 1983.

62. Postel, J. Time protocol. DARPA Network Working Group Report RFC868, USC Information Sciences Institute, May 1983.

63. Defense Advanced Research Projects Agency. Internet Control Message Protocol. DARPA Network Working Group Report RFC-792, USC Information Sciences Institute, September 1981.

64. Su, Z. A specification of the Internet protocol (IP) timestamp option. DARPA Network Working Group Report RFC-781. SRI International, May 1981.1 67. Mills, D.L. DCN local-network protocols. DARPA Network Working Group

65. Report RFC-891, M/A-COM Linkabit, December 1983.

66. Gusella, R., and S. Zatti. The Berkeley UNIX 4.3BSD time synchronization protocol: protocol specification. Technical Report UCB/CSD 85/250, University of California, Berkeley, June 1985.

67. Gusella, R., and S. Zatti. An election algorithm for a distributed clock synchronization program. Technical Report UCB/CSD 86/275, University of California, Berkeley, December 1985.

68. Bell Communications Research. Digital Synchronization Network Plan. Technical Advisory TA-NPL-000436, 1 November 1986.

69. Braun, W.B. Short term frequency effects in networks of coupled oscillators. IEEE Trans. Communications COM-28, 8 (August 1980), 1269-1275

70. Van Dierendonck, A.J., and W.C. Melton. Applications of time transfer using NAVSTAR GPS. In: Global Positioning System, Papers Published in Navigation, Vol. II, Institute of Navigation, Washington, DC, 1984.

71. Frank, R.L. History of LORAN-C. Navigation 29, 1 (Spring 1982).

72. Vass, E.R. OMEGA navigation system: present status and plans 1977-1980. Navigation 25, 1 (Spring 1978).

73. Halpern, J.Y., B. Simons, R. Strong and D. Dolly. Fault-tolerant clock synchronization. Proc. Third Annual ACM Symposium on Principles of Distributed Computing (August 1984), 89-102.

74. Mills, D.L. Network Time Protocol (version 1) specification and implementation. DARPA Network Working Group Report RFC-1059, University of Delaware, July 1988.

75. Mills, D.L. Internet time synchronization: the Network Time Protocol. IEEE Trans. Communications 39, 10 (October 1991), 1482-1493.

76. Экспериментальны данные по аппроксимации множества точек осепараллельными параллелепипедами.