Анализ алгоритмов маршрутизации для сетей VANET методами имитационного моделирования

Размещено на http://www.allbest.ru

Размещено на http://www.allbest.ru

Введение

Последние достижения в области аппаратных средств, программного обеспечения и коммуникационных технологий позволяют проектировать и внедрять целый ряд различных типов сетей, которые реализуются в различных средах. Автомобильная самоорганизующуюся сеть (VANET) является одной из тех сетей, которые за последние несколько лет привлекли к себе пристальное внимание. VANET обладает огромным потенциалом для повышения безопасности автомобилей и дорожного движения, качества и простоты движения, а также удобства для водителей и пассажиров, поэтому активно развивается в области исследований, стандартизации и развития. Автомобильные самоорганизующиеся сети (VANETs) возникли в связи с необходимостью обслуживания растущего числа беспроводных устройств, которые могут использоваться в транспортных средствах. Эти продукты включают устройства дистанционного бесключевого доступа, КПК, ноутбуки и системы мобильных телефонов. Использование технологий Vehicle-to-Vehicle (V2V), Vehicle-to-Roadside (VRC), Vehicle-to-Infrastructure (V2I)становится привычным по мере расширения применения портативных беспроводных устройств и систем.

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

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

Для решения задачи оптимального размещения систем мониторинга вVANETмогут быть использованы методы имитационного моделирования (ИМ).

Объектом исследования являются сети VANET.

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

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

Таким образом, в данной работе ставятся следующие задачи:

1. Выявить основные параметры беспроводных сетей VANET.

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

3. Выполнить анализ средств агентно-ориентированного моделирования для выбора среды моделирования.

3. Построить имитационную модель алгоритма маршрутизации на примере конкретного алгоритма.

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

1. Обзор алгоритмов маршрутизации сетей VANET

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

1.1 Введение в сети VANET

Транспортная сеть (VANET) представляет собой технологию, используемую для построения мобильной сети путем использования движущихся транспортных средств в качестве узлов в сети. VANET превращает каждое участвующее транспортное средство в маршрутизатор или узел, позволяющий транспортным средствам взаимодействовать в радиусе 100-300 метров. Таким образом, транспортные средства этого диапазона могут связаться друг с другом и создать сеть с более широким диапазоном [1,2]. VANET состоит из двух основных компонентов - транспортных средств и придорожной инфраструктуры. Такие компоненты обычно создают связь между транспортными средствами, идентифицируемый как связь между транспортным средством и транспортным средством (V2V) или между транспортным средством и придорожной инфраструктурой, известной как связь между транспортным средством и инфраструктурой (V2I). Как правило, предоставляемая информация часто связана с условиями дорожного движения [2,3], состоянием дорожного покрытия [2,4-8], информационно-развлекательными материалами [2,3,9] и т.д. в целях обеспечения безопасности жизни, а также комфорта как водителей, так и пассажиров.

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

Неспособность учитывать при проектировании многие важные метрики, такие как сила принимаемого сигнала, потеря пути, мощность и частота передачи [10-12], является принципиальным ограничением большинства моделей систем связи VANET. В этой связи, ученые попытались использовать различные популяционные мета-эвристические стратегии для оптимизации путей коммуникации, обычно основанные на биологической теории эволюции и генетике[9,12-14].

1.2 Био-инспирированные алгоритмы

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

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

1. Основные параметры задачи оптимизации:

· Определение задачи оптимизации: в аналитическом контексте задача оптимизации определяется, в частности, как выбор оптимального подхода (оптимального решения) по определенным параметрам[6].

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

· Население и индивидуальная кодировка: популяция -- это набор индивидуумов, где каждый индивидуум представляет собой область допустимых решений. Каждый индивидуум кодируется, используя структуру данных, основанную на булевых переменных, строках, деревьях и т. д. Некоторые индивидуальные типы кодирования включают в себя двоичную кодировку, которая состоит из набора двоичных переменных; дискретное кодирование основано на дискретном векторе целочисленных значений; естественная кодировка в который индивид представлен вектором целого числа. Кодирование играет важную роль в эффективности алгоритма разрешения, который помогает снизить вычислительную сложность [6].

· Инициализация: это способ присвоения набора исходных значений из области допустимых решений для формирования исходной популяции. Существует несколько способов выбора первого решения (исходной совокупности). Например, случайная инициализация, при которой случайным образом выбираются первые индивидуумы области допустимых решений.

· Критерий остановки: определяется как измеренное значение, которое контролирует количество циклов выполнения алгоритма разрешения. Данный критерий может быть статическим, в котором перед запуском алгоритма разрешения устанавливается фиксированное количество итераций. Более того, критерий остановки может быть динамическим и останавливаться после определенного количества раз (также известного как состояние стагнации), если функция не улучшается.

2. Роевой интеллект (РИ)

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

Генетический алгоритм -- это био-инспирированный алгоритм, предложенный в 1970-х годах [8]. Алгоритм имитирует процесс естественной эволюции. ГА -- это оптимизационный подход, основанный на популяции индивидуумов (называемых хромосомами), которые генерируют другую популяцию во время итерации. Исходная популяция устанавливается с помощью случайной инициализации. После этого все хромосомы (родители), вероятно, выбираются по двое для участия в операции кроссовера, за которой следует операция мутации. В результате обеих этих операций получается набор хромосом (потомство), которые сравниваются с родителями, так что лучшие хромосомы могут быть использованы для следующего поколения. Процессы селекции, кроссовера, мутации и генерации повторяются до тех пор, пока не будет выполненостановочный критерий. Ниже описаны операции отбора, кроссовера и мутации.

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

2. Кроссовер (скрещивание) -- это бинарная операция, которая применяется к двум хромосомам с целью генерации двух новых хромосом. Кроссовер моделирует размножение индивидов, где представление каждой хромосомы разбито на части и приводит к появлению новых хромосом, каждая из которых состоит из одной части одного родителя и другой части второго родителя. Операция кроссовера нацелена на создание новых диверсифицированных решений в области допустимых решений. Это выбор дальних решений (потомков) в области допустимых решений с точки зрения приспособленности по сравнению с оригинальными решениями (родителей). Существует несколько стратегий кроссовера, таких как одноточечный кроссовер, где одна точка отсечения выбирается случайным образом в представлении обеих хромосом, чтобы разделить их на две части. Первая часть первого родителя добавляется к последней части второго родителя, чтобы сформировать хромосому первого потомства, и наоборот. Кроме того, предлагается двухточечное пересечение, при котором применяются две точки среза [10].

3. Мутация -- это унарная операция, которая применяется к одной хромосоме, образовавшейся после кроссоверной операции. Целью мутации является небольшое изменение представления хромосомы для достижения нового решения, близкого к оригинальному в области допустимых решений с точки зрения приспособленности. Существуют различные стратегии мутации, одной из популярных является одноточечная мутация, при которой случайным образом выбирается одна точка отсечения в представлении изменяемого потомства со случайной величиной. Эта стратегия генерирует новую хромосому, близкую к изначальной в области допустимых решений. Другая стратегия мутации называется UniformMutation(Унифицированная мутация), при которой случайная величина выбирается между заданной пользователем верхней и нижней границей, которая заменяет значение выбранной точки отсечения хромосомы[11].

Муравьиный алгоритм -- это алгоритм, имитирующий поведение муравьев при поиске источника пищи, который был предложен в 1992 г. [12]. В естественной среде обитания муравьи эксплуатируют свои территории случайным образом: найдя пищу, муравьи возвращаются в колонию, прокладывая следы феромона (химического вещества). Вероятно, этот путь используют и другие муравьи, которые следуют по тропе с большим количеством феромонов, а качество тропы усиливается по сравнению с другими, менее посещаемыми тропами. Тем не менее, со временем тропа феромонов начинает испаряться, что снижает ее привлекательную прочность. Следовательно, короткая тропа, для сравнения, прокладывается чаще, и плотность феромонов на более коротких тропах становится выше, чем на более длинных. Идея муравьиного алгоритма аналогична этому поведению, представляя область допустимых решений с помощью пути, по которым путешествуют муравьи.

Несколько вычислительных задач были решены с использованием новых подходов, вдохновленных поведением пчел. Общий подход называется алгоритмомжизни пчел, в котором были использованы два основных поведения пчел: кормление пищей и воспроизводство. Пищевое поведение наблюдается, когда пчелы ищут новые гнезда или же во время кормления. Для этого некоторые пчелы (называемые скаутами) перемещаются и исследуют регион, чтобы найти источник пищи. Если они что-то находят, они возвращаются на так называемый «танцпол» в улей, чтобы поделиться этой находкой со своими товарищами по гнезду, используя язык танца, который может быть разным в зависимости от расстояния, на котором было обнаружено место. Некоторые пчелы (которых называют «фуражирами») набираются для того, чтобы воспользоваться этим открытием. Репродуктивное поведение гарантируется королевой, которая спаривается с несколькими беспилотниками. Через три дня королева откладывает яйца. Неоплодотворённая яйцеклетка приводит к появлению беспилотника, в то время как оплодотворённая яйцеклетка приводит к появлению рабочего или королевы в зависимости от качества пищи, предоставляемой личинкам [13].

Алгоритм подобен тому, как птицы стекаются в реальной жизни. Используя оптимизацию роя, метод рассматривает частицу, определяемую ее положением (то есть качеством решения) и его скоростью (то есть способностью двигаться к другому решению, которое может быть лучше) [14]. Этот алгоритм гарантирует, что каждая частица выбирает одну из лучших ранее встречавшихся позиций или движется к новой позиции, используя скорость частицы, если эта новая является лучшей. Метод роя частиц выполняет эти шаги, пока не достигнет критерия остановки.

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

Когда бактерии помещаются в вещество с однородной концентрацией питательных веществ, они проявляют поисковое поведение, но с увеличенной длиной плавания и уменьшенным временем остановки. Однако, когда бактерии обнаруживают изменение уровня концентрации питательных веществ, они плывут по градиенту концентрации в сторону наиболее богатого питательными веществами участка и тратят меньше времени на остановку [19]. Такое поведение было применено для решения нескольких вычислительных задач путем представления области допустимых решений с помощью бактериальной области, где бактерии меняют место с одного решения на другое[20].

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

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

1.3 Параметры беспроводных сетей

Масштабируемость сети

Масштабируемость -- это способность сети эффективно обрабатывать большое количество узлов. Масштабируемость считается одной из самых сложных задач сетевого исследования, поскольку если она не поддерживается должным образом, производительность сети может быстро ухудшиться [15]. Масштабируемость довольно хорошо поддерживается традиционными сетевыми методами, если плотность сети низкая (то есть небольшое количество узлов). Однако эти традиционные методы менее эффективны для крупных сетей. Напротив, био-инспирированные решения по своей природе являются масштабируемыми (лучший путь к еде с муравьями, лучшие новые гнезда для пчел, лучшая организация путешествий для птиц и т. д). Даже если число особей очень велико (т. е. сети высокой плотности). В результате ученые, занимающиеся компьютерными сетями, были заинтересованы в поиске новых решений сетевых проблем с использованием тех же самых био-вдохновленных принципов, которые включают: местное сотрудничество между людьми (между соседями), локальное общение для получения глобальной информации о состоянии сети [13].

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

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

Биотехнологии позволяют внедрять адаптивные и самоорганизующиеся решения и поддерживать более современную информацию о состоянии сети по сравнению с традиционными методами [15].

Надежность сети -- это способность поддерживать приемлемую производительность, несмотря на сбои в работе сети. Надежность обеспечивает устойчивость сети к сбоям в соединениях/установках или удалению узлов или целевым атакам [16]. Например, иммунная система человека состоит из набора элементов, отвечающих за распознавание и защиту от патогенных микроорганизмов (т. е. вирусов, бактерий, паразитов и т. д.) для обеспечения жизнеспособности организма человека. Поведение иммунной системы было применено для обнаружения вторжений в сети в [17] и показало лучшие результаты по сравнению с традиционными методами дискретного преобразования дерева[18].

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

2. Средства имитационного моделирования и их применение для исследования алгоритмов маршрутизации

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

2.1 Агенто-ориентированное моделирование

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

Современные программные подходы сосредоточены на концепции проектирования модели, которая кодифицирует и повторно использует повторяющиеся элементы в новых проектах. Такой подход оказывается очень полезным как при создании проекта, так и при разработке программного обеспечения. Возникающие действия и внезапное текущее поведение объектов VANET хорошо представлены посредством мультиагентного моделирования. Агенто-ориентированная модель содержит объекты с индивидуальными свойствами и действиями. Агенто-ориентированное моделирование применимо к нескольким областям, в том числе к социальным, физиологическим и биологическим системам человека. Это чрезвычайно полезный инструмент, когда речь идет о моделировании реальных событий. Аргумент в пользу использования агентного моделирования заключается в том, что сложность, вытекающая из транспортных отношений и взаимодействий в реальности, может быть реализована непосредственно с помощью агентного моделирования. Преимущество такого метода моделирования состоит в том, что достаточно знать поведение отдельных объектов данной системы для проектирования всей системы в целом.

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

Агентами являются вычислительные представления некоторых конкретных социальных субъектов -- отдельных людей или животных, организаций, таких как фирмы или органы, такие как национальные государства, -- способных взаимодействовать, то есть они могут передавать друг другу информационные сообщения и действовать на основе того, что они узнают из этих сообщений. Таким образом, каждый агент в модели является самостоятельным субъектом. Искусственная популяция может включать в себя гетерогенные агенты, что полезно, когда исследователь хочет построить модель того или иного явления с различными возможностями агентов, их ролями, перспективами или запасами знаний. В агенто-ориентированном моделировании обычно выделяют четыре важные характеристики для агентов[21]:

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

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

3. Память: у агентов есть память, в которой они записывают свои предыдущие состояния и действия.

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

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

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

2.2 Краткий обзор средств для агенто-ориентированного моделирования

Важным шагом является выбор между написанием специальной компьютерной программы (с использованием таких языков программирования, как Java, C++, C# или VisualBasic) или использованием одного из пакетов или наборов инструментов, специально созданных для помощи в проведении моделирования. Пользоваться готовым программным продуктом гораздо проще, нежели разрабатывать симулятор с нуля, так как большинство проблем, требующих большого количество времени разработки, уже реализованы в готовых решениях. Однако, есть и недостатки в использовании готовых программ, например, ограниченность функционала. Таким образом, необходимо найти средство, которое обладает следующими параметрами:

· Открытый доступ;

· возможность отладки;

· наличие обширной графической библиотеки;

· легкость в освоении;

· наличие библиотеки моделей с открытым исходных кодом.

Swarm является мультиагентной программной платформой для моделирования сложных адаптивных систем. В системе Swarm базовой единицей моделирования является стая -- коллекция агентов, выполняющих определенную последовательность действий.Swarm поддерживает подходы иерархического моделирования, при которых агенты могут состоять из стаи других агентов во вложенных структурах.Swarm предоставляет объектно-ориентированные библиотеки многократно используемых компонентов для построения моделей и анализа отображения и управления экспериментами на этих моделях [22].

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

Агенты определяют основные объекты в системе Swarm-- имитируемые компоненты. График дискретных событий на этих объектах определяет процесс, происходящий во времени. В Swarm отдельные действия происходят в определенное время; время прогрессирует только по запланированным событиям.График -- это структура данных, которая объединяет действия в определенном порядке, в котором они должны выполняться.

Фундаментальным компонентом, организующим агентов модели Swarm, является объект, называемый swarm. Swarm-- это совокупность агентов с расписанием событий над этими агентами. Swarm представляет собой целую модель, содержащую агентов, а также представление времени [22].

The recursive Porous Agent Simulation Toolkit (RePast) -- это бесплатное приложение с открытым исходным кодом для создания моделей на основе агентов. В RePast предоставляются компоненты шаблона для построения репрезентативных элементов, например таких как среда, в которой взаимодействует агент. RePast позволяет разработчикам тратить больше времени на разработку специфики своей модели (например, взаимодействие агентов, поведение и т. д.) вместо того, чтобы настраивать основы моделирования (например, планировать события, которые должны произойти, разрабатывать визуальное отображение и т. д.).

Re Past является производной инструментария моделирования Swarm. Изначально задуманная как библиотека классов Java, которая могла бы взаимодействовать с фреймворком имитационного моделирования Swarm, эта концепция была оставлена, когдабыла выпущена версия реализации Swarm на Java [23]. Следовательно, создатели RePast разработали независимый фреймворк, полностью написанный на Java, полностью объектно-ориентированный, но заимствующий несколько ключевых абстракций, присутствующих в Swarm.

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

В настоящее время Repast может быть реализован на трех различных языках/фреймворках программирования: Java (RepastJ и RepastS), Microsoft.NET (Repast.NET) и Python (RepastPy).

MASON -- это однопроцессорное ядро моделирования и инструментарий визуализации, написанный на Java, разработанный для гибкого использования в широком спектре симуляций, но с особым акцентом на «роевые» симуляциибольшого количества (до миллионов) агентов[24]. Система является открытой и бесплатной. MASON не является производным от какого-либо другого инструментария, а построен с нуля.

MASON быстрый, портативный, способный проверять и перезапускать модели инструмент с возможностью визуализации, способный мигрировать модели между платформами и выдавать гарантированно воспроизводимые результаты независимо от платформы.Модели MASON могут быть подключены к поставляемому GUI-инструментарию, который позволяет визуализировать и манипулировать моделью как в 2D, так и в 3D (с использованием Java3D), и который может создавать скриншоты и фильмы.Данный инструмент тщательно разграничивает модель и визуализацию, позволяя динамически отсоединять модели от визуализаторов или присоединять их к ним, а также менять платформы в середине рабочего цикла.

NetLogo-- это программируемая среда имитационного моделирования для симуляции природных и социальных явлений. Он подходит для построения как простых, так и сложных систем, передачи команд и управления сотнями тысяч агентов. В этой среде агенты представлены как «черепахи» (turtles). Разработанный для того, чтобы дети могли легко программировать, NetLogo иллюстрирует, что может произойти, когда популяции черепах получают набор правил, которым они должны подчиняться. NetLogo такжеимеет возможности для достаточно сложного моделирования и позволяет опытным программистам добавлять свои собственные расширения Java. NetLogo активно используется широкой аудиторией, начиная с детей младшего школьного возраста и заканчивая учеными в области социальных, компьютерных и естественных наук, а страница онлайн сообщества включает в себя модели, созданные широким кругом представителей каждой из этих групп.

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

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

NetLogo представляет собой интересную альтернативу другим средамагентного моделирования, таким как Swarm, RePast и MASON. Однако, эти среды моделирования довольно сложны для использования и требуют значительного опыта в программировании для построения имитационных моделей, в то время как для моделирования в NetLogo достаточно знать лишь основы.

NetLogoвключает в себя три основных компонента (виды агентов): Черепахи (turtles), связи (links) и пятна (patches), каждый из которых объясняется ниже:

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

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

3. Пятно: Пятна, т. е. компоненты заданной пользователем статической сетки (мира), которая является 2D или 3D миром, в котором обитают черепахи. Пятна используются при описании поведения среды.

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

Основными особенностями симулятора NetLogoявляются:

1. Открытый исходный код.

2. Простота отслеживания ошибок.

3. Подвижные агенты (черепахи) перемещаются по сетке стационарных агентов (пятен).

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

5. BehaviorSpace: инструмент, используемый для сбора данных с нескольких параллельных запусков модели.

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

7. Возможность просмотра модели как в 2D, так и в 3D.

На рисунке 2.1 представлено стартовое окно программы NetLogo.

Рисунок 2.1 -- Стартовое окно симулятора «NetLogo»

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

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

В таблице 2.1 представлено сравнение вышеупомянутых средств имитационного моделирования.

Таблица 2.1 -- Сравнение средств агенто-ориентированного программирования

	Swarm	RePast	Mason	NetLogo
Лицензия	ОЛС	ОЛС	ОЛС	Бесплатная
Документация	Ограниченная	Ограниченная	Ограниченная	Полная
Наличие библиотеки готовых моделей	Отсутствует	Отсутствует	Отсутствует	Имеется
Язык программирования	Objective-C, Java	Java, Python	Java	NetLogo
Поддержка графического интерфейса	Частично имеется	Имеется	Имеется	Имеется
Лёгкость в обучении и программировании для непрофессиональных программистов	Сложно	Средне	Средне	Легко

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

3. Моделирование и анализ имитационной модели генетического алгоритма маршрутизации в среде NetLogo

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

3.1 Моделирование работы генетического алгоритма

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

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

1. отбор (selection) - подобно реальной жизни, наименее приспособленные решения удаляются из популяции, а на оставшихся местах появляются копии оставшихся решений;

2. скрещивание (crossover) - оставшиеся решения делятся на пары, где каждая пара скрещивается с некоторой вероятностью, в процессе чего происходит обмен частей генотипов и формируются новые пары решений;

3. мутация (mutation) - происходит случайная модификация каждого из решений.

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

Блок-схема генетического алгоритма, иллюстрирующая принцип его работы представлена на рисунке 3.1.

Рисунок 3.1 -- Блок-схема генетического алгоритма

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

1. Создаются три глобальных переменных - n (число звеньев ломаной линии), start(пятно, с которого строятся маршруты), target (конечное пятно, которое необходимо достигнуть).

2. Для черепах добавляются два атрибута - x (план маршрута в виде последовательности из углов поворота), f (расстояние от последней точки маршрута до цели).

3. К интерфейсу добавляем кнопку setup, к которой добавляем процедуру определения стартового и конечного пятна, процедуру создания популяции, работа которой заключается в том, чтобы создать указанное число черепах с определенными параметрами и процедуру, которая отвечает за прокладывание и прорисовку маршрута согласно плану x. Для задания количества черепах, на интерфейс выводим слайдер pop-size. Результат можно увидеть на рисунке 3.2.

Рисунок 3.2 -- Результат действия кнопки Setup

4. Затем добавляем к интерфейсу кнопку Go, и два переключателя: hide-turtles иshow-best. Первый переключатель отвечает за скрытие черепах, что позволит оставить только траектории маршрутов (рисунок 3.3). Второй переключатель будем оставлять только лучший маршрут на данной итерации, а остальные скроет (рисунок 3.4). К кнопке Goпривязываем процедуру, с помощью которой будет реализована итерация генетического алгоритма, состоящая из отбора, скрещивания и мутации.

Рисунок 3.3 -- Результат действия слайдера hide-turtles

Рисунок 3.4 -- Результат действия слайдера show-best. На данном рисунке показан лучший из маршрутов на текущей итерации алгоритма.

5. Добавляем проверку достижения цели: если на конечном пятне есть хотя бы одна черепаха, то алгоритм останавливается. Результаты работы модели можно увидеть на рисунках 3.5, 3.6. При работе алгоритма со всеми тремя операторами (отбор, скрещивание, мутация), он практически всегда находит оптимальный маршрут.

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



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

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

3.2 Моделирование работы генетического алгоритма на примере реальной городской обстановки

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

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

Процесс моделирования имеет следующую структуру:

1. Установка входных параметров:

1.2 Плотность транспортного потока (количество транспортных средств);

1.3 установленный скоростной лимит;

1.4 радиус действия придорожных устройств оповещения;

1.5 количество придорожных устройств оповещения.

2. Моделирование транспортной сети.

3. Генерация транспортных средств.

4. Генерация начального поколения придорожных устройств оповещения для заданной транспортной сети.

5. Работа генетического алгоритма.

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

7. Повтор пунктов 5 и 6 до получения ожидаемого результата.

Для более подробного ознакомления со структурой алгоритма, см. ПРИЛОЖЕНИЕ А.

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

Генерация начальной популяции осуществляется случайным образом. Для каждого решения программа генерирует случайные координаты«x» (расположение по оси x) и «y» (расположение по оси y) на графе транспортной сети. беспроводной маршрутизация алгоритм

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

(1)

где F-- приспособленность,

N -- количество оповещенных транспортных средств,

t -- время симуляции.

Далее, из популяции удаляются решения, не соответствующие следующему неравенству:

(2)

где F -- приспособленность,

v -- общее количество транспортных средств,

s -- общее количество придорожных устройств оповещения.

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

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

3.2.3 Скрещивание

Операция скрещивания объединяет два индивидуума, порождая двух новых индивидуумов. Новые индивидуумы формируются на основе части первого родителя и части от второго родителя. Таким образом, для первого потомка мы берем координату «x»от первого родителя и координату «y»от второго родителя, для второго потомка координату «x»от второго родителя и координату «y»от первого родителя соответственно.

Например, есть два индивидуума -- A (144;12) и B (22;87). Тогда они образуют новых двух индивидуумов --AB (144;87) и BA (22;12). В каждом поколениислучайным образом создаются пары между индивидуумами, ис вероятностью они скрещиваются.

В каждом поколении у каждого индивидуума есть шанс мутировать с вероятностью . Мутация реализована в виде следующей модификации индивидуума:

1. Удаление текущего индивидуума

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

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

3.2 Анализ работы генетического алгоритма для задачи расстановки придорожных устройств оповещения

Имитационное моделирование проводилось для следующих входных данных:

· Граф транспортной сети, состоящий из 36 узлов и 60 рёбер;

· количество придорожных устройств, который распространяют информацию - 15;

· радиус действия оповещающих устройств - 250 метров;

· для транспортной сети возьмем максимальную скорость передвижения - 60 км/ч.

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

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

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

Рисунок 3.7 -- Результат генерации начальной популяции устройств оповещения на графе моделируемой сети в программе NetLogo

Как видно из рисунка, зелеными кругами обозначается радиус действия оповещающих устройств. В целях максимального приближения к реальности, центры оповещения расставлены таким образом, что их радиусы действия не могут пересекаться, так как при этом, очевидно, теряется их производительность, и центры начинают дублировать друг друга. Также стоит отметить, что при инициации работы алгоритма радиус устройств оповещения обязательно покрывает дорожное полотно, что сделано для целесообразности моделирования. Автомобили, находящиеся в радиусе, получают сигнал, и окрашиваются в зеленый цвет, который тускнеет по мере отдаления от устройства. Более того, когда автомобиль выходит за границы моделируемой области (агенты в данной программе двигаются таким образом, что при достижении максимальной координаты «x» или «y», они появляются с противоположной стороны, двигаясь, так называемо, «по кругу»), он автоматически полностью теряет сигнал и окрашивается в серый цвет, становясь «новым» автомобилем, который только что заехал в зону и еще не получал сигнал.

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

· Количество автомобилей -30

· Вероятность мутации - 0,3

· Вероятность скрещивания - 0,5

Рисунок 3.8 -- Результат работы алгоритма в виде оптимально расставленных устройств на графе

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

...