Диссертация (1143658), страница 16
Текст из файла (страница 16)
она инициирует рост графа «наружу», образуя«места» для будущих вершин).Проведение операции ЗВЗ заключается в выборе трех вершин, которыестанут частью нового сегмента. При ЗВЗ(А) вершина согласовывает действия сдругими угловыми вершинами, при ЗВЗ(В) вершина согласовывает действия ссоседями по сегменту, чтобы те были готовы к подразбиению связи.
КогдаприготовлениязаконченывершинасообщаетостартеЗВЗ,высылаетокончательный список устройств, тип ЗВЗ и собственный индекс, после чегопринимает индексы новых вершин, обновляет свой индекс и рассылает сообщениео необходимости обновления индексов всем остальным вершинам.Если не было обнаружено критических ошибок, алгоритм завершается,иначе начинается сначала.112Рисунок 5.5 – Действия вершины графа, направленные на осуществление ЗВЗАлгоритм на рисунке 5.6 поясняет действия вершины графа при отсутствииактивности другой, соседней вершины, либо при получении сигнала об удалениисегмента графа (подграфа).Если данной вершине удается связаться с вершиной, из-за которой началработу данный алгоритм, то его выполнение прекращается; иначе данная вершинавыясняет, находится ли с неактивной вершиной в соседних сегментах одногопорядка (подграф-затравка, подграф ФГ2, …, подграф Фгn-1): если нет, то развитиесобытий не зависит от данной вершины, и она прекращает выполнение данного113алгоритма; иначе данная вершина определяет размер сегмента, который будетзаменять неактивный сегмент (замещающий должен быть, минимум, на одинпорядок меньше), запрашивает от RSU таблицу присутствия удаленного сегмента(вершины) и проводит диагностику своего сегмента (все вершины сегмента делаютэто одновременно), может ли он заместить эти связи, не разрушив свои (внутрисегмента), соседние сегменты обмениваются данной информацией и выясняют,есть ли хотя бы один сегмент, способный это выполнить.Рисунок 5.6 – Действия вершины при отсутствии активности или удалениисоседней вершины1145.3 Разработка прототипа системыДля реализации модели и предложенных подходов к построению, адресациии маршрутизации разработана программа, на базе платформы .NET Frameworkверсии 4.5 и языка программирования Visual C#.Для создания графического интерфейса пользователя использовался наборбиблиотек Windows Forms, входящий в состав фреймворка .NET.
Windows Formsсодержит все необходимые компоненты для реализации функционального иудобного интерфейса.Средства визуализации топологии VANET-сети также с помощью WindowsForms. Основной используемый для этого инструмент – графическое поле«PictureBox» и стандартные средства создание графических элементов (средстварисования).Для повышения репрезентативности моделируемой VANET-сети былопринято решение использовать информацию о транспортных системах реальныхгородов.
В качестве источника информации была использована открытая базаданных – Open Street Maps (OSM) [89, 90, 91], которая содержит подробную картумира.Для представления географических объектов в базе данных OSMиспользуются три основные сущности:узлы (англ. nodes) – точки на карте, обозначаемые географическимикоординатами. Узлы лежат в основе представления всех географических объектовв базе данных OSM;пути (англ.
ways) – векторы, состоящие из набора узлов. Не замкнутыепути в OSM используются аналогично линейным топографическим символам,например, c помощью путей обозначаются автомобильные и железнодорожныедороги. Также в OSM используются замкнутые пути, с помощью которыхпредставляются различные плоскости;отношения (англ. relations) – группы путей и узлов, логическисвязанных друг с другом.115Описанные сущности представляют собой примитивы, на основе которыхописываются все объекты, содержащиеся в OSM.
Каждый узел, путь и отношение,заносимое в базу данных, наделяется уникальным идентификатором, также придобавлении в базу заносится метаинформация. Для хранения информации одеталях конкретных объектов (например, число полос движения, название улицы,и т.д.) используется механизм меток (англ. tags), представляющих собой парыключ-значение.Для представления базы данных OSM используется несколько форматовфайлов, основными из которых являются OSM XML и PBF [92].Формат OSM XML основан на стандарте XML.
Для представления базовыхсущностей используются теги node, way и relation, метаинформация сохраняется ватрибутах тегов. В случае путей и отношений входящие в них элементы хранятся,как вложенные теги, содержащие ссылки на идентификаторы.Формат PBF (Protocolbuffer Binary Format) хранит информацию в бинарномформате, что позволяет значительно экономить объём памяти необходимый дляхранения базы данных [93].Для извлечения информации об автомобильных дорогах был реализованкласс OsmParser, производящий обработку файлов формата OSM XML. Обработкафайла производится в два этапа: на первом этапе из файла формата OSM XMLизвлекается информация об узлах, которая сохраняется в хэш-таблицу, в качествеключа в которой используется идентификатор узла. Далее из OSM XML-файлаизвлекаются пути, имеющие тег highway со значением, использующимся дляобозначения элемента дорожно-транспортной системы.
Далее извлечённые путисохраняются в XML-файл.Для получения информации о положения узла по его идентификаторуиспользуется поиск по составленной хэш-таблице.Для хранения и отрисовки карты используется классы Road и Node.Объекты класса Road инициализируются значениями, хранящимися в теге roadсформированного XML-файла.116При инициализации класса Road координаты узлов, составляющих дорогу,преобразовываются из географических координат в точку на растровомизображение, используя информацию о минимальное и максимальное значениешироты и долготы из OSM XML-файла.Отрисовка дороги (рисунок 5.7) на растровом изображение производитсяпутём соединения пар узлов, составляющих дорогу, линиями.
Толщина линиизависит от числа дорожных полос, которое указывается в OSM XML-файле. Вслучае, когда данная информация отсутствует по умолчанию используетсязначение, равное двум полосам.Рисунок 5.7 – Пример результата отрисовки дороги на основе информации изOSM XML файлаОписанныйподходпозволяетпроизводитьмоделированиененаабстрактной плоскости со случайно расставленными узлами VANET-сети, а нареальной дорожной карте любого города.При запуске программы открывается основное окно графическогоинтерфейса (рисунок 5.8).117Рисунок 5.8 – Основное окно графического интерфейсаРабота с программой начинается с моделирования размещения узлов(автомобилей) – предполагаемых участников сети и компонент топологии.Для этого в программе предусмотрен механизм генерации заданногоколичествакоординатсослучайнымизначениямиабсциссиординат.Координатной плоскостью является элемент (виджет) PictureBox в главном окнепрограммы. Возможны два способа генерации: с наложением моделей устройствна схему улиц, либо совершенно случайное расположение узлов на плоскости.Процесс импорта схемы улиц, а также генерации точек на плоскости полностьюавтоматизирован и происходит по нажатию кнопки «Добавить», расположенной вглавном окне графического интерфейса.
Для импорта схемы улиц необходимонажать «Файл – импортировать карту» и выбрать файл с расширением .osm взятыйиз проекта OpenStreetMap.При этом данные об узлах как о точках на плоскости заносятся в структуруданных «RegularGraph», являющуюся стандартной реализацией структуры данных«взвешенный граф». В качестве весов выступают расстояния между точками наплоскости.Далее необходимо создать связь между точками, то есть смоделироватьвозможную сеть VANET при заданном расположении RSU и автомобилей.
Данное118действие происходит по нажатию кнопки «Создать связи» и полностьюавтоматизировано.При нажатии на данную кнопку создается новая структура данных –«фрактальный граф», реализация которого схожа с реализацией классическойструктуры данных «граф», однако данная структура данных так же хранит таблицуприсутствия, а сам класс FractalGraph представляет методы взаимодействия с ней.ИменновданномклассереализованыалгоритмыпротеканияЗВЗииндексирования.Изначально основной класс программы производит объединение первыхчетырех узлов без использования класса «FractalGraph». Это связано с тем, чтоалогритмы контроллеров VANET предусматривают то, что первая ЗВЗ отличаютсяпо своей структуре от ЗВЗ(А) и ЗВЗ(В). Далее основной класс программыслучайнымобразомвыбираетвершинуграфа(этонеобходимо,чтобысмоделировать распределенную сеть, т.е.
независимое взаимодействие вершин),находит при помощи специального алгоритма три узла, которые подходят дляпроведения ЗВЗ(А) или ЗВЗ(В), после чего переправляет данную информацию вкласс FractalGraph, который и выполняется сами ЗВЗ, а также перераспределениеиндексов. Алгоритмы проведения ЗВЗ и индексации во многом совпадают салгоритмами контроллеров VANET, основные различия заключаются в отсутствиираспределенности.
Основной критерий выбора узлов для ЗВЗ – это расстояние отвершины графа, которая выбрана для проведения ЗВЗ. В данной модели принятосчитать расстояние между узлами абсолютной мерой оптимальности возможнойсвязи.После того, как связи образованы, программа имеет возможностьсмоделировать путь между двумя вершинами с использованием алгоритмамаршрутизации описанного в 3.1.3. Вид главного окна после импорта схемы улиц,размещения узлов, создания связей и выделения пути представлен на рисунке 5.9.119Рисунок 5.9 – Вид главного окна после импорта схемы улиц, размещения узлов,создания связей и выделения путиПосле создания связей имеется возможность посмотреть математическийвид образованного графа (рисунок 5.10), для этого необходимо нажать «Опции –Показать структуру графа».
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
