Файл: Разработка системы имитационного моделирования сетей передачи данных.pdf
Добавлен: 16.02.2024
Просмотров: 30
Скачиваний: 0
Рисунок 2.1. Функция «построение модели»
Функция «выполнение» отвечает за то, как ведет себя необходимый бизнес-процесс в различных заданных ситуациях. Например, возможность изучить как выполняется модель с изменением базы генератора случайных чисел или с изначально заданными значениями. Все подгруппы данного критерия показаны на рисунке 2.2.
Рисунок 2.2. Функция «выполнение»
Функция «отладка» отвечает за то, как СИМ справляется с выявлением различных ошибок, которые возникают в процессе моделирования и работы имитации. Все подгруппы критерия показаны на рисунке 2.3.
Рисунок 2.3. Функция «отладка»
Критерий «анимация» отвечает за визуальную составляющую модели, то есть то, как СИМ показывает модель (в замедленном режиме, изменение угла обзора и т. д.). Все подгруппы этого критерия показаны на рисунке 2.4.
Рисунок 2.4. Критерий «анимация»
Критерий «вывод результатов» отвечает за то, как система имитационного моделирования формирует отчётность по результатам выполнения определенного бизнес-процесса, в каких видах можно получить результаты (вывод на печать, табличная версия), а также как СИМ анализирует полученные результаты. Все подгруппы данного критерия показаны на рисунке 2.5.
Рисунок 2.5. Критерий «вывод результатов»
Большинство данных критериев являются нечисловыми, то есть не поддаются количественной оценке, поэтому оценка будет производиться путём сравнения различных параметров систем имитационного моделирования. К примеру, не в каждой СИМ имеется графический редактор, следовательно его наличие будет записан как положительная оценка определенного критерия. Исходя из теста различных СИМ будет выявлена та имитационная среда, что будет наиболее удобна в решении конкретно нашей поставленной задачи.
The Recursive Porous Agent Simulation Toolkit (Repast) – это бесплатно распространяющаяся и широко используемая СИМ, которая также включает различные библиотеки для агентного моделирования. Данная программа была разработана в Чикагском университете. Repast включает в себя реализацию на нескольких языках программирования позволяя пользователю более гибко строить имитационные модели Существует 3 версии Repast [13] Каждая из них имеет упор на определенный язык программирования (Python, Java и Microsoft.NET).
Repast J – это СИМ, которая использует язык программирования Java. Она служит для того, чтобы разрабатывать крупномасштабные агентные модели. Также включает в себя календарь события для параллельного планирования во времени. Пример на рисунке 2.6.
Repast Microsoft .NET – СИМ, реализрованная на языке C#. С помощью неё можно перенести все функции Repast J на платформу .NET и создавать дальнейшие модели с использованием любого языка программирования, который поддерживается на .NET.
Рисунок 2.6. Интерфейс Repast
AnyLogic – это разработка для имитационного моделирования, включающий в себя все три самых популярных метода моделирования. Данное программное обеспечение было разработано российской группой TheAnylogic Company на языке программирования Java. Не так давно был запущен сервис AnyLogic Cloud, который даёт возможность выкладывать имитационные модели в веб-пространство и тем самым демонстрировать его другим людям без каких-либо затрат во времени. Веб-сервис показан на рисунке 2.7.
AnyLogic имеет в себе графический язык, который даёт возможность апгрейдить уже построенные модели языком Java. Кроме того, в данном ПО интегрирован компилятор Java, тем самым позволяя создавать Java апплеты. Интерфейс программы представлен на рисунке 2.8.
Рисунок 2.7. Веб-сервис AnyLogic Cloud
Рисунок 2.8. Интерфейс AnyLogic
AnyLogic имеет множество положительных сторон:
- Интегрированное ПО для анализа данных, а также набор возможностей для бизнес-графики для демонстрирования моделей.
- С помощью языка Java есть возможность доопределить функции любых элементов модели.
- Огромное количество видов экспериментов с моделью (варьирование параметров, простой и сравнительный прогон).
- Возможность разработки анимации и графического интерфейса с помощью встроенного редактора с набором различных фигур и элементов.
NetLogo – это мультиагентная среда имитационного моделирования, основанная на языке Logo [10]. Данное ПО было разработано усилиями Массачусетского университета и компании BBN. Язык часто используется для обучения, так как не сложен в работе, но при этом остаётся мощным решением для разработки имитационных моделей. Интерфейс данной программы показан на рисунке 2.9.
Рисунок 2.9. Интерфейс NetLogo
Огромный плюс данной программы в том, что синтаксис довольно минималистичен и он лёгок в изучении, тем самым не будет проблемы создать несложную модель с образовательной целью. Также NetLogo имеет обширную библиотеку встроенных моделей для различных целей (образование, исследование, развлечение). Кроме того, есть возможность контактировать со специализированным программным обеспечением, таким как GoGo board. Разработанная модель показана на рисунке 2.10.
Рисунок 2.10. Модель в NetLogo
Сравнение систем имитационного моделирования
Далее приведено сравнение вышеописанных сред имитационного моделирования и выбрана одна из предложенных. Нужно сказать, что в расчёт были взяты только основные критерии оценки, чтобы не нагружать анализ и процесс выбора СИМ. Подводя итог анализа сред имитационного моделирования хочется сказать, что все выбранные СИМ (AnyLogic, Repast, NetLogo) подходят для построения моделей и решения именно поставленной конкретной задачи, разница между ними незначительна. AnyLogic считается одной из лучших СИМ в данным момент, но исходя из того что прошлая курсовая работа была основана на моделировании в AnyLogic хотелось рассмотреть и другое программное обеспечение в данной сфере. Кроме того, NetLogo считается всемирно признанным ПО именно для работы с распределенными системами и учитывая, что NetLogo получило наивысший балл в оценочном анализе, было принято решение моделировать волновые алгоритмы в NetLogo.
Далее приведено описание работы каждого выбранного волнового алгоритма, а также построены к ним блок-схемы. Информация о волновых алгоритмах была взята из учебного пособия по распределенным системам и алгоритмам [14] и из статьи по волновым алгоритмам [15].
Древесный алгоритм
Древесный алгоритм – это алгоритм из семейства волновых алгоритмов. Его смысл в том, что все листья, то есть процессы, которые являются вершинами дерева, запускают алгоритм и являются инициаторами. Все остальные процессы являются неактивными (неинициаторы).
Алгоритм начинается с того, что все листовые процессы отправляют сообщение вверх остальным неактивным процессам в дереве. Те процессы, что были неактивны и получили сообщение, становятся активными и тем самым становятся инициаторами, чтобы передавать сообщение дальше. И так далее волнами каждый процесс в дереве получает сообщение и после этого алгоритм завершает свою работу. Работа алгоритма в виде блок-схемы представлена на рисунке 2.11.
Рисунок 2.11. Блок-схема древесного алгоритма
Алгоритм эха
Алгоритм эха — это централизованный волновой алгоритм в сетях с произвольной топологией. Смысл данного алгоритма в том, что инициатором служит один процесс, а все остальные процессы являются неактивными.
Алгоритм начинается с того, что инициатор начинает отправку сообщения всем соседним процессам, которые находятся в состоянии неактивности. Посредством волн инициаторы передают сообщение всем своим соседям кроме процесса, который передал этот сигнал или уже является активным. После неопределенного числа волн сообщение получает каждый процесс и алгоритм заканчивает свою работу. Работа данного алгоритма представлена на рисунке 2.12.
Рисунок 2.12. Блок-схема алгоритма эха 
Кольцевой алгоритм
Кольцевой алгоритм – это алгоритм, который можно использовать в гамильтоновой сети или графе. Гамильтонов граф – это замкнутый путь, тот же цикл, где необходимо пройти через каждую вершину графа.
Смысл кольцевого алгоритма в том, чтобы инициатор передал сообщение ближайшему неактивному процессу и так по цепочке, чтобы задействовать все процессы и получить сообщение обратно с целью принятия решения. Блок-схема кольцевого алгоритма показана на рисунке 2.13.
Рисунок 2.13. Блок-схема кольцевого алгоритма 
На этом этап проектирования заканчивается, далее будет приведена реализация вышеперечисленных алгоритмов.
Фазовый алгоритм
Фазовый алгоритм является децентрализованным алгоритмом, который подходит для сетей, в которых используется произвольная топология. Такой алгоритм подходит для ориентированных сетей.
В данном алгоритме необходимо, чтобы каждый агент или процесс располагал данными о длине сети. Алгоритм может работать при условии, что все процессы будут использовать константу, которая превышает диаметр (или длину) самой сети.
Данный алгоритм применяется для любой ориентированной сети, данные в которой передаются в одну сторону. В таком случае соседями любой вершины будут как инициаторы, так и неинициаторы. Также по каждому каналу должно передаваться такое количество сообщений, которое не превышает длину сети. Двунаправленные связи тоже могут присутствовать, но они должны быть заданы парой параллельных встречных однонаправленных каналов. Блок-схема фазового алгоритма показана на рисунке 2.14.
Рисунок 2.14. Блок-схема фазового алгоритма
Алгоритм Финна
Алгоритм Финна — это волновой алгоритм, который используется для произвольных ориентированных сетей. Диаметр сети не обязательно должен быть известен заранее, но этот алгоритм опирается на однозначную идентифицируемость процессов. В сообщениях процессы обмениваются отличительными признаками, что в итоге приводит к тому, что битовая сложность данного алгоритма оказывается довольно велика.
В процессе р формируются два множества отличительных признаков Incp, и Nincp. Incp обозначает множество таких процессов q, что некоторое событие в q предшествует самому последнему событию, случившемуся в р, a Nlncp обозначает множество таких процессов q, что у каждого соседа г процесса q какое-нибудь событие в г предшествует самому последнему событию, случившемуся в р. Блок-схема алгоритма показана на рисунке 2.15.
Рисунок 2.15. Блок-схема алгоритма Финна
На этом этап проектирования заканчивается, далее приведена реализация.
Глава 3. Реализация волновых алгоритмов в NetLogo
В данной главе обсуждаются волновые алгоритмы, которые уже были спроектированы выше и далее идёт их разработка в системе имитационного агентного моделирования NetLogo. Реализация велась с помощью NetLogo User Manual [16].
Для начала необходимо создать несколько несвязанных агентов или «черепашек», которые будут отвечать за процессы в алгоритме. Созданные агенты показаны на рисунке 3.1.
Рисунок 3.1. Созданные агенты
Далее для данного алгоритма необходимо, чтобы у каждого процесса было по 2 связи, через которые потом будет производиться передача сообщений. Данная функция будет создана через функцию create-link-with внутри программы NetLogo. Получившаяся картина показана на рисунке 3.2.