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

Введение

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

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

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

В данной работе рассмотрено такое семейство распределенных алгоритмов как волновое. Далее выбранное семейство алгоритмов проанализировано и реализовано в среде агентного моделирования 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.

---