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

Содержание:

Введение

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

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

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

В данной работе рассмотрено такое семейство распределенных алгоритмов как волновое. Далее выбранное семейство алгоритмов проанализировано и реализовано в среде агентного моделирования Netlogo. Кроме того, составлено руководство для реализации моделей волновых алгоритмов в СИМ NetLogo. Руководство включает в себя описание алгоритмов, особенности и эффективности алгоритмов, а также инструкции к написанию кода на языке Logo, который используется в среде имитационного моделирования NetLogo.

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

Итак, объект исследования - волновые алгоритмы.

Предмет исследования – особенности функционирования различных алгоритмов из семейства волновых алгоритмов с анализом их эффективности и надежности.

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

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

1. Рассмотреть предметную область распределенных алгоритмов и сред имитационного моделирования.
2. Рассмотреть виды волновых алгоритмов и проанализировать их.
3. Сравнить среды имитационного моделирования для выявления более подходящей СИМ (системы имитационного моделирования) для выполнения поставленной задачи.
4. Составить требования к разработке имитационных моделей волновых алгоритмов.
5. Проектирование имитационных моделей волновых алгоритмов в СИМ NetLogo для демонстрации их работы.
6. Представить описание алгоритмов и их реализацию в СИМ NetLogo.

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

• 1. Распределенные системы

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

Существует несколько причин, по которым распределенные системы оказываются более предпочтительны, либо их применение становится неизбежным [2]:

1. Обмен информацией.
2. Совместное использование ресурсов.
3. Повышение надежности за счет дублирования.
4. Повышение производительности за счет параллельного выполнения.
5. Упрощение проектирования за счет специализации.
   1. Семейство волновых алгоритмов

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

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

Инициаторами называются стартовые процессы, которые начинают выполнение алгоритма по какому-либо условию. То есть инициатор запускает распространение информации или же отправку сообщения.

Неинициаторы же ответственны за то, чтобы принять сообщение от инициатора и продолжить исполнение алгоритма.

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

1. Кольцевой алгоритм.
2. Древесный алгоритм.
3. Алгоритм эха.
4. Алгоритм опроса.
5. Фазовый алгоритм.
6. Алгоритм Финна.
   1. Имитационное моделирование

Известно, что имитационное моделирование находит свое применение в самых широких областях производства, науки, бизнеса. Действительно, очень многие исследования нуждаются в проведении различных имитационных экспериментов. Их целью является прогнозирование поведения изучаемого объекта или системы, которая является сложной и динамической. Такие имитационные эксперименты предоставляют возможность рассмотреть ситуацию с различных сторон, при этом используя различные вводные данные. Тем самым повышая вероятность принять верное решение, например, в современных реалиях ведения бизнеса и организации предприятия [3]. Так в результате проведения экспериментов выявляется самый выгодный способ ведения бизнеса и организации структуры предприятия. После этого есть смысл проверить значения таких параметров для бизнес-процессов как затраты, оперативность бизнес-операций. С такой целью целесообразно сымитировать поведение модернизированного бизнес-процесса, определяя при этом результативность модернизации по ключевым показателям. Таким образом, системы имитационного моделирования являются неотъемлемой частью систем поддержки принятия решений (СППР). Также в автоматизированном проектировании имитационное моделирование играет немаловажную роль.

Существует три вида имитационного моделирования [4]:

1. Агентное моделирование.
2. Дискретно-событийное моделирование.
3. Системная динамика.

В данной работе рассматривается именно агентное моделирование.

Рисунок 1.1. Виды имитационного моделирования

• 1. Дискретно-событийное моделирование

При анализировании различных процессов иногда используют способ рассмотрения отдельно взятых этапов в процессе. То есть весь процесс разбивается на конкретные главные этапы.

При таком виде моделирования весь процесс разбивается на объекты, которые в дальнейшем и моделируются индивидуально. Такие объекты являются отдельными сущностями, но всё-таки большинство деталей в моделировании не учитываются. С помощью такой технологии моделирования принято моделировать различные бизнес-процессы. Пример такого подхода к моделированию показан на рисунке 1.2.

Рисунок 1.2. Пример дискретно-событийного моделирования

• 1. Системная динамика

Данный способ имитационного моделирования встречается в самых различных исследованиях и стезях бизнеса. Системная динамика [6] даёт возможность смоделировать системы высокой сложности и на высоком уровне абстракции, то есть не рассматривая мельчайшие детали. К примеру, мельчайшими деталями могут являться свойства отдельно взятых продуктов, событий или людей. Модели, построенные таким способом имитирования, дают возможность сложить общее представление о системах и являются отличным решением для стратегического планирования.

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

Рисунок 1.3. Пример цикла обратной связи в системной динамике

• 1. Агентное моделирование

Агентное моделирование – это один из методов имитационного моделирования, рассматривающий поведение децентрализованных агентов. Кроме того, данный метод исследует как такое поведение определяет поведение всей системы как единое целое. В отличие от системной динамики аналитик определяет поведение агентов на индивидуальном уровне, а глобальное поведение возникает как результат деятельности множества агентов (моделирование «снизу вверх») [7]. Агентное моделирование применяется в огромном количестве различных сфер деятельности. Оно может использоваться в социологии, политологии и многих других.

Существует не так много программ, которые выступают средами имитационного моделирования, в данной работе будут рассмотрены следующие:

1. Repast [8].
2. Anylogic [9].
3. NetLogo [10].

Рисунок 1.4. Пример модели в Anylogic об обслуживании клиента в компании

Рисунок 1.5. Пример интерфейса в Netlogo

Глава 2. Описание и проектирование волновых алгоритмов

В данной главе проведено сравнение и анализ различных сред агентного моделирования, также рассмотрено семейство волновых алгоритмов и дано их описание. Кроме того, описан этап проектирования для дальнейшего моделирования в среде агентного моделирования Netlogo.

• 1. Сравнение сред имитационного моделирования

Существует множество различных сред имитационного моделирования (СИМ), далее приведены критерии оценки, а также сравнение таких сред имитационного моделирования, как: NetLogo, AnyLogic и Repast.

Критерии оценки СИМ

Основываясь на статье о современных СИМ [11,17,18,19] далее приведены критерии оценки систем имитационного моделирования.

Для сравнения систем имитационного моделирования в статье Джелла Никукарана [12] предложено сравнение СИМ по наличию следующих функций:

1. Построение модели.
2. Выполнение.
3. Отладка.
4. Анимация.
5. Вывод результатов.

Далее каждая функция рассмотрена более подробно с точки зрения того какие возможности может предоставить система имитационного моделирования.

Функция «построение модели» отвечает за все возможности, с помощью которой в СИМ можно промоделировать необходимый бизнес-процесс, то есть построить модель, которая будет визуализировать или имитировать вид бизнес-процесса. Все подгруппы данного критерия показаны на рисунке 2.1.

Рисунок 2.1. Функция «построение модели»

Функция «выполнение» отвечает за то, как ведет себя необходимый бизнес-процесс в различных заданных ситуациях. Например, возможность изучить как выполняется модель с изменением базы генератора случайных чисел или с изначально заданными значениями. Все подгруппы данного критерия показаны на рисунке 2.2.

Рисунок 2.2. Функция «выполнение»

Функция «отладка» отвечает за то, как СИМ справляется с выявлением различных ошибок, которые возникают в процессе моделирования и работы имитации. Все подгруппы критерия показаны на рисунке 2.3.

Рисунок 2.3. Функция «отладка»

Критерий «анимация» отвечает за визуальную составляющую модели, то есть то, как СИМ показывает модель (в замедленном режиме, изменение угла обзора и т. д.). Все подгруппы этого критерия показаны на рисунке 2.4.

Рисунок 2.4. Критерий «анимация»

Критерий «вывод результатов» отвечает за то, как система имитационного моделирования формирует отчётность по результатам выполнения определенного бизнес-процесса, в каких видах можно получить результаты (вывод на печать, табличная версия), а также как СИМ анализирует полученные результаты. Все подгруппы данного критерия показаны на рисунке 2.5.

Рисунок 2.5. Критерий «вывод результатов»

Большинство данных критериев являются нечисловыми, то есть не поддаются количественной оценке, поэтому оценка будет производиться путём сравнения различных параметров систем имитационного моделирования. К примеру, не в каждой СИМ имеется графический редактор, следовательно его наличие будет записан как положительная оценка определенного критерия. Исходя из теста различных СИМ будет выявлена та имитационная среда, что будет наиболее удобна в решении конкретно нашей поставленной задачи.

СИМ Repast

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

AnyLogic – это разработка для имитационного моделирования, включающий в себя все три самых популярных метода моделирования. Данное программное обеспечение было разработано российской группой TheAnylogic Company на языке программирования Java. Не так давно был запущен сервис AnyLogic Cloud, который даёт возможность выкладывать имитационные модели в веб-пространство и тем самым демонстрировать его другим людям без каких-либо затрат во времени. Веб-сервис показан на рисунке 2.7.

AnyLogic имеет в себе графический язык, который даёт возможность апгрейдить уже построенные модели языком Java. Кроме того, в данном ПО интегрирован компилятор Java, тем самым позволяя создавать Java апплеты. Интерфейс программы представлен на рисунке 2.8.

Рисунок 2.7. Веб-сервис AnyLogic Cloud

Рисунок 2.8. Интерфейс AnyLogic

AnyLogic имеет множество положительных сторон:

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

СИМ NetLogo

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.

• 1. Проектирование волновых алгоритмов

Далее приведено описание работы каждого выбранного волнового алгоритма, а также построены к ним блок-схемы. Информация о волновых алгоритмах была взята из учебного пособия по распределенным системам и алгоритмам [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].

• 1. Реализация кольцевого алгоритма

Для начала необходимо создать несколько несвязанных агентов или «черепашек», которые будут отвечать за процессы в алгоритме. Созданные агенты показаны на рисунке 3.1.

Рисунок 3.1. Созданные агенты

Далее для данного алгоритма необходимо, чтобы у каждого процесса было по 2 связи, через которые потом будет производиться передача сообщений. Данная функция будет создана через функцию create-link-with внутри программы NetLogo. Получившаяся картина показана на рисунке 3.2.

Рисунок 3.2. Процессы со связями

Далее случайно выбирается один процесс, который будет являться инициатором, его цвет будет отображён как красный. Для этого внутри программы выбирается агент с нулевым номером и помечается красным цветом. Получившаяся картина показана на рисунке 3.3.

Рисунок 3.3. Появление инициатора

После этого, по цепочке идёт передача сообщения от инициатора к одному из связанных с ним неактивному процессу. Теперь ранее неактивный процесс становится инициатором и загорается красным цветом, далее он будет передавать сообщение. Изначальный инициатор загорается серым цветом для того, чтобы пользователь понимал, что в этом процессе уже было сообщение, но в данный момент он не является инициатором. Данная ситуация показана на рисунке 3.4.

Рисунок 3.4. Появление нового инициатора

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

Рисунок 3.5. Ситуация на 4 тик

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

Рисунок 3.6. Последний тик алгоритма

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

• 1. Древесный алгоритм

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

Рисунок 3.7. Изначальный древесный алгоритм

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

Рисунок 3.8. Передача информации

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

Рисунок 3.9. Конец выполнения древесного алгоритма

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

• 1. Алгоритм эха

В данном алгоритме инициатором выступает один процесс, который передаёт сообщение соседним неактивным процессам. Изначальные данные алгоритма показаны на рисунке 3.10.

Рисунок 3.10. Начало алгоритма эха

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

Рисунок 3.11. Этап передачи сообщения

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

Рисунок 3.12. Завершение алгоритма эха

Таким образом были построены все вышеперечисленные волновые алгоритмы.

• 1. Фазовый алгоритм

Необходимо создать агентов, которые имеют размер 3, синий цвет и форму кружков. Также необходимо с помощью команды «layout-circle turtles (world-width / 2 - 10)» расположить их по кругу, а кроме этого, задать инициатора. Полученная модель показана на рисунке 3.13.

Рисунок 3.13. Начальное состояние модели

Далее необходимо задать код, который будет передавать цвет от одного агента к другому, при этом инициатор является красным, затем переходит в неактивное состояние, а агент, который принял сообщение «загорается» красным, то есть становится активным. Этот алгоритм проходит до тех пор, пока один из агентов не передаст сообщение количество (n-4) раз. То есть на один меньше, чем количество агентов в цепочке. Второй этап выполнения алгоритма показан на рисунке 3.14.

Рисунок 3.14. Второй этап выполнения алгоритма

Третий этап выполнения алгоритма показан на рисунке 3.15.

Рисунок 3.15. третий этап выполнения алгоритма

Далее на рисунке 3.16 показан последний этап выполнения алгоритма.

Рисунок 3.16. Последний этап выполнения алгоритма

После данного этапа алгоритм закончил своё выполнение, так как нижний агент принял и передал 3 сообщения, то есть (n – 4).

• 1. Алгоритм Финна

Необходимо задать код, который создаёт модель, а также будет передавать цвет от одного агента к другому, при этом инициатор является красным, затем переходит в неактивное состояние, а агент, который принял сообщение «загорается» красным, то есть становится активным. Кроме того, необходимо задать связи между процессами. Модель показана на рисунке 3.17.

Рисунок 3.17. Изначальная модель алгоритма

Далее на рисунке 3.18. показан второй этап выполнения алгоритма (после одного нажатия кнопки «go».

Рисунок 3.18. Второй этап выполнения алгоритма

На рисунке 3.19. показан четвёртый этап выполнения алгоритма.

Рисунок 3.19. Четвёртый этап выполнения алгоритма

Последний этап выполнения алгоритма показан на рисунке 3.20. Агент 3 остался активным, так как было получено сообщение от агента 0. Процесс 2 остаётся активны и отсылает данные, которые полностью определены агенту 0, который являлся изначальным инициатором. Произошло оповещение всех агентов (процессов) в сети. Алгоритм завершил свою работу.

Рисунок 3.20. Последний этап выполнения алгоритма

Таким образом были построены все вышеперечисленные волновые алгоритмы.

Заключение

В ходе работы была изучена предметная область распределенных систем, в частности волновые алгоритмы. Кроме того, рассмотрена предметная область имитационного моделирования с углублением именно на метод агентного моделирования. Также был проведён сравнительный анализ трёх сред имитационного моделирования, используя различные критерии оценки СИМ. Сравнительный анализ включал такие среды моделирования, как: NetLogo, AnyLogic и Repast. По итогу анализа решено было выбрать NetLogo как среду разработки для поставленной задачи.

Для пяти видов волновых алгоритмов (кольцевой алгоритм, древесный алгоритм, фазовый алгоритма, алгоритм эха и алгоритм Финна) были построены блок-схемы и как итог работы были построены имитационные модели, которые наглядно показывают работу волновых алгоритмов. В дальнейшем данные имитационные модели будут использованы для описания руководства пользователя.

Построенные имитационные модели можно успешно применять для обучения студентов распределенным алгоритмам.

Библиографический список

1. Обзор распределенных систем [Электронный ресурс]. Режим доступа ‑ http://masters.donntu.org/2008/fvti/prihodko/library/dist2.htm
2. Тель Ж. Введение в распределенные алгоритмы, Изд-во МЦНМО, Москва. – 2009. – с. 616.
3. Емельянов А. А., Власова Е. А., Дума Р.В. Имитационное моделирование экономических процессов: Учебное пособие. М.: Финансы и статистика, 2002 [Электронный ресурс]. Режим доступа – http://simulation.su/uploads/files/default/immod-2009-1-19-26.pdf. Дата обращения: 30. 02. 20.
4. Виды имитационного моделирования [Электронный ресурс]. Режимдоступа ‑ https://studbooks.net/2274235/informatika/vidy_imitatsionnogo_modelirovaniya.
5. N. S. Matloff, Introduction to Discrete-Event Simulation and the SimPy Language, 2013 [Электронный ресурс]. Режим доступа ‑ http://heather.cs.ucdavis.edu/~matloff/156/PLN/DESimIntro.pdf. Дата обращения: 02. 03. 20.
6. Борщёв А. От системной динамики и традиционного ИМ – к практическим агентным моделям: причины, технология, инструменты [Электронный ресурс]. Режим доступа - http://gpss.ru/paper/borshevarc.pdf. Дата обращения 05. 03. 20.
7. Лебедюк Э. А., Агентное моделирование: состояние и перспективы [Электронный ресурс]. Режим доступа - http://simulation.su/uploads/files/default/2017-lebeduk-1.pdf. Дата обращения: 07. 03. 20.
8. Charles M., Michel J., Tutorial on agent-based modeling and simulation part 2: how to model with agents [Электронный ресурс]. Режим доступа - http://www2.hawaii.edu/~nreed/ics606/papers/Macal06model.pdf.
9. Сharles M., Everything you need to know about agent-based modelling and simulation [Электронный ресурс]. Режим доступа - https://www.researchgate.net/publication/302923196_Everything_you_need_to_know_about_agent-based_modelling_and_simulation.
10. Carbo J., Agent-based simulation with NetLogo to evaluate ambient intelligence scenarios [Электронный ресурс]. Режим доступа - https://link.springer.com/article/jos.2016.10.
11. Современные системы имитационного моделирования и критерии их оценки [Электронный ресурс]. Режим доступа - http://simulation.su/uploads/files/default/2019-dadenkov-kon.pdf. 
12. Джелал Никукаран, Критерии оценки СИМ [Электронный ресурс]. Режим обращения - http://simulation.su/uploads/files/default/obzor-2010-guravlev.pdf.
13. Michael J. and Charles M., Escaping the Accidents of History: An Overview of Artificial Life Modeling with Repast [Электронный ресурс]. Режим доступа - https://link.springer.com/chapter/10.1007/1-84628-214-4_6.
14. А. И. Миков, Е. Б. Замятина, Распределенные системы и алгоритмы, 2007 [Электронный ресурс]. Режим доступа - http://window.edu.ru/resource/466/57466.
15. Е. Б. Замятина, Д. Ф. Каримов, Волновые алгоритмы [Статья]
16. NetLogo 6.1.1 User Manual [Электронный ресурс], Режим доступа - https://ccl.northwestern.edu/netlogo/docs/dictionary.html.
17. Замятина Е.Б. Современные теории имитационного моделирования: Специальный курс. - Пермь: ПГУ, 2007. - 119 с. http://window.edu.ru/resource/717/41717
18. Замятина Е.Б. Системы имитационного моделирования и машинная имитация: теоретические основы и реализация. Методичсекое пособие / Е.Б. Замятина, В.В. Ланин, Л.Н. Лядова, А.Н. Фирсов ; Федер. агентство по образованию, ГОУВПО "Перм. гос. ун-т", Пермь, 2007 – 304 с.
19. Замятина Е.Б. Современные теории и системы имитационного моделирования: учеб. -метод. пособие / Е.Б. Замятина, В.В. Ланин, Л.Н. Лядова, А.Н. Фирсов ; Федер. агентство по образованию, ГОУВПО "Перм. гос. ун-т", 2007 г.,- 100 с.