Диссертация (1143658), страница 15
Текст из файла (страница 15)
В рамках раздела применяются следующие термины:Вершина — валидная составляющая сети второго уровня, вершинапредфрактального графа.Узел — элемент вне сети второго уровня, имеющий с данной сетью связь(OBU автомобиля или RSU).В данной терминологии именно узел является рассматриваемым в данномразделе «висячим узлом».
Так же далее под словом «сеть» будет подразумеваться«сеть второго уровня».105Важность висячих узлов как компоненты сети заключается в том, чтофрактальная топология накладывает существенные ограничения на количествовершин и количество их связей, а значит, и на их положение.Можно провести следующую аналогию: возьмем плоскость с единичнойплощадью, и случайным образом расположим на ней N окружностей, которыемогут пересекаться, но не могут совпадать. В данной модели центр окружности —это узел, а сама окружность — это дальность действия связи.
Таким образомокружностимогутсвязыватьсятолькосвоимицентрами.Необходимо,рассматривая центры окружностей как узлы, получить предфрактальный граф.Пусть затравка будет полносвязным графом с количеством узлов, равным M, апорядок предфрактального графа равен K. Тогда количество вершин этого графаравно MK. Значит, первое основное требование, чтобы наши узлы можно былообъединить в предфрактальный граф — это N = MK. Но равенство случайного числаодному определенному значению — это маловероятное событие.
Помимо этого,каждый узел должен быть способен соединиться с 3 или 4 другими узлами, приэтом список соединений для каждого узла должен быть уникальным, что, учитываяограниченный радиус действия, так же вводит ограничения на расположение узлов,еще больше уменьшая вероятность образования предфрактального графа из набораузлов.Наличие вершин, не раскрывшихся в подграфы (вершины с нулевымиидентификаторами), облегчает образование предфрактального графа, но тем неменее успешное образование такого графа все еще не гарантировано.Наличие висячих вершин (вернее, возможность их наличия), позволяетпосмотреть на данную модель иначе: так же расположим на единичной площадкеN узлов (окружностей), но теперь подберем такое K, что N ≥ MK.
Условиедоступности для вершин выполняется, таким образом возможно образоватьпредфрактальный граф с полносвязной затравкой с числом вершин M и порядкомK. При этом не нужно игнорировать или удалять (N — MK) оставшихся узлов: онистановятся висячими узлами. Т.е. каждый из таких узлов имеет связь с одним илинесколькими вершинами предфрактального графа, но эти связи являются106побочными, т. е. Не вносящими корректировок в граф. Другими словами, наличиевисячих узлов позволяет образовать граф, в котором всегда можно выделитьподграф, являющийся предфрактальным.Индекс висячего узла всегда нулевой, а число идентификаторов равно числуидентификаторов вершины, с которой он связан.В рамках сетей VANET висячие узлы представляют собой устройства(машины), которые не состоят в основной сети, но связаны с ее вершиной(ами),таким образом:имеется «запас» узлов для будущих операций ЗВЗ;каждый узел может получать актуальную информацию, не нарушаятопологию сети.5.2 Алгоритмы работы системыПри образовании предфрактального графа используются две операции:ЗВЗ(А) и ЗВЗ(В).
Каждой из этих операций необходим предфрактальный графпервого порядка (граф-затравка), либо больше. Но на первом этапе сетьпредставлена единичным узлом, тогда, проведениеЗВЗ(А) или ЗВЗ(В)неосуществимо. Значит, образование графа-затравки представляет из себяотдельную задачу, которую необходимо рассмотреть подробно.На первом этапе существует единственная вершина, соответствующая RSU.Изначально индекс такой вершины «0». Данная вершина ожидает подключения,каждое из которых будет являться висячим узлом с идентификатором «0». Увершины нет ограничений на количество узлов, однако, для образования графазатравки с M вершинами необходимо, как минимум, (М — 1) узлов.
Если узлов(−1)больше, то мы имеем Смножеств узлов, которые могут образовать завтравку.Таким образом, из этого набора множеств необходимо выбрать только одно.Необходимо, чтобы каждый из (М-1) узлов мог связаться с остальными (M2) узлами, т. к. мы рассматриваем полносвязные затравки.
Если данное условиевыполняется для нескольких множеств узлов, то дальнейший выбор проводится поуровню мощности сигнала.107Выбор множества узлов осуществляется вершиной: каждый узел приподключении начинает передавать вершине информацию о том, с какими узламион может соединиться (они все должны быть между собой связаны, но в рамкахрассматриваемой модели сети эти связи будут попросту игнорироваться), и каковокачество связи с каждым узлом.
Данная информация может быть представленаэлементарной таблицей, где первая колонка — MAC-адреса (или любой другойуникальный физический идентификатор) узла, которые доступны данному узлу, авторая колонка — качество связи с ним, выраженное, как правило, в децибелах.Когда выбор множества узлов окончен, вершина сообщает каждому узлу,связи с какими узлами необходимо выделить. Далее выполняется назначениеиндексов.Назначение индексов происходит следующим образом: изначальнаявершина присваивает себе первый по порядку индекс (идентификатор «a»),сортирует имеющийся список физически адресов по возрастанию, и по порядкуприсваивает каждой новой вершине тот идентификатор, какому соответствуетномеру его физического адреса в списке, после чего сообщает каждой вершине ееидентификатор.Таким образом, формируется граф-затравка с введенной системойиндексации.
Сеть, несмотря на размеры, становится полностью функциональной.Оставшиеся узлы продолжают «висеть» принимая полезную информацию от сети,ожидая возможности принять участие в операциях ЗВЗ.Алгоритм на рисунке 5.2 поясняет действия RSU, когда происходит перваядля данного графа ЗВЗ. Первой ЗВЗ будет считаться самая первая, либо та, котораяпроисходит после полного распада сети.RSU получает списки доступных устройств, когда их набирается достаточнодляпроведенияЗВЗ,даннойустройствовысылаетостальнымспискирекомендаций, принимает ответ и выбирает три узла, которые станут вершинамисети. В данном алгоритме будущие индексы вершин распределяет RSU.
Индексданного устройства на начало алгоритма всегда «0» и на конец алгоритма всегда«а». При этом устройство должно принимать от каждого узла, который появится в108зоне действия, его уникальные идентификаторы (гос. номер, VIN-номер и т. п.) ихранить таблицу присутствия.Рисунок 5.2 – Алгоритм проведения первой ЗВЗАлгоритм на рисунке 5.3 описывает действия, которые должен выполнятьвисячий узел, чтобы попасть в сеть VANET.Алгоритм начинается с того, что устройство активировано и задействовалосетевой интерфейс (точка входа).Устройство (узел) слушает эфир и выясняет, какие устройства доступны, изних он ищет устройства, уже состоящие в графе; если какое-либо из этих устройствсообщает, что начинается ЗВЗ, то узел «сосредотачивается» на этом.109Сначала происходит подготовка к ЗВЗ: узел принимает список устройств,связь с которыми необходимо проверить, и возвращает обновленный список, вкотором отсутствуют устройства, связь с которыми невозможна.
Далее узелпринимает ответ, на основании которого принимается решение, будет данный узелучаствовать в ЗВЗ или нет.Если нет, то узел возвращается в исходное состояние, иначе он принимаетокончательный список устройств, которые будут его будущими соседями в сети,также он принимает тип ЗВЗ и индекс (в зависимости от того, первая это ЗВЗ в сетиили нет, индекс может быть как действующим индексом вершины, так и новыминдексом данного узла). Если требуется, узел вычисляет собственный индекс, ирассказывает об этом соседям, принимая от них аналогичные сообщения.Если никаких ошибок не обнаружено, алгоритм завершается, данный узелстановится вершиной сети.Рисунок 5.3 – Действия висячего узла110Алгоритм на рисунке ъ поясняет порядок образования нового индекса длявисячего узла в зависимости от типа проводимой ЗВЗ.Если ЗВЗ первая для данной сети, то алгоритм не будет выполняться вовсе,т.
к. готовый индекс новой вершине (узлу) сообщит RSU.НАЧАЛООжидание узловНетИмеются узлы для ЗВЗ?ДаАВКакой тип ЗВЗ?Обмен данными с соседямипо сегментуОбмен данными междуугловым вершинамиВыбор подходящих узлов ивершин. ОсуществлениеЗВЗ(В)Выбор подходящих узлов ивершин. ОсуществлениеЗВЗ(А)ВершинаИзменение индекса старойвершины или созданиеиндекса нового узла?УзелНетЕсть нулевые разряды?ДаИзменение индекса старойвершины или созданиеиндекса нового узла?Заменить левыйнулевой разряд направый значимыйразрядВершинаУзелУгловая вершина, неучаствовавшая в ЗВЗ,распространяет другимузлам левый разряд своегоиндекса (адреса)Получение индекса отвершины, с которой созданасвязьСтарые вершины добавляютэтот разряд себе слеваВзять левый разряд индексавершины; добавить справанулей столько, сколькоразрядов в индексе старойвершиныДобавить справапредыдущийправый разрядПолучить индекс угловойвершины сегмента,соседствующей с той, ккоторой данный узелприсоединилсяВзять правый значимыйразряд индекса вершинысегмента, соседствующей стой, к которой данный узелприсоединилсяВзять индекс основнойвершиныДобавить справаполученный разрядсоседаКОНЕЦСеть имеет фрактальнуюструктуру, индексыназначеныНет Есть нулевые разряды?ДаЗаменить левый нулевойразряд на полученныйразряд соседаРисунок 5.4 – Порядок образования нового индекса для висячего узла взависимости от типа проводимой ЗВЗ111Алгоритм на рисунке 5.5 поясняет действия вершины графа, направленныена осуществление ЗВЗ, когда вершина, выполняющая алгоритм, принимает участиев ЗВЗ.В начале вершина определяет (при помощи собственного индекса), являетсяли она угловой.
В зависимости от этого возможно или невозможно проведениеЗВЗ(А). Далее, если вершина угловая, она согласует проведение ЗВЗ с другимиугловыми вершинами, формирует список рекомендованных устройств, которыйсостоит из висячих узлов данной вершины, ее соседей по сегменту и висячих узловдругих двух угловых вершин (при ЗВЗ(А) только три вершины участвуют в данномпроцессе).
Если вершина не угловая, то сформированный список рекомендованныхустройств состоит из собственных висячих узлов вершины и ее соседей по сегменту(связь с которыми будет разбиваться новыми вершинами при ЗВЗ(В)).Вершина сообщает собственным висячим узлам о начале ЗВЗ и отправляетсписок рекомендованных устройств. Далее вершина принимает обновленныесписки и проверяет их, вынося решение: возможно ли ЗВЗ(А) и возможна лиЗВЗ(В), если ни одна операция невозможна, алгоритм возвращается в исходноеположение, иначе выбирается (если возможны обе) одна из двух операций(приоритет у операции ЗВЗ(А), т. к.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
