Диссертация (1143658), страница 11
Текст из файла (страница 11)
При этом каждый узелможет видеть любой другой, доступный ему, и быть с ним связанным, при этом обаузла будут идентифицировать друг друга нулевым индексом, что означаетневозможностьучастиятакойсвязивинформационныхпроцессах76предфрактального графа. Однако возможность видеть такие связи обеспечиваетвозможностьростапредфрактальногографа.Узел,несостоящийвпредфрактальном графе, но связанный с тем, который в нем состоит, будемназывать висячим.Случай первый, ЗВЗ(А).Данная операция инициирует, как было определено, рост графа «наружу»,соответственно дополнение индексов будет происходить влево.
Так же, учитываявведенное ограничение на число связей одного узла, новый узел можетподключиться только к такому старому, у которого меньше четырех связей. Еслирассматривать предфрактальный граф первого порядка и выше с полносвязнымквадратом в качестве затравки, подключение возможно только к угловымвершинам. Таких вершин четыре, из чего следует, что в любой момент времени прилюбом порядке фрактальности (за исключением вырожденного случая, – нулевогопорядка – которые будет рассмотрен далее) за протекание операции ЗВЗ(А)отвечают только четыре вершины. Данные вершины должны общаться междусобой,синхронизируяпротекание ЗВЗ(А).Каждаяизугловыхвершинобменивается с другими угловыми вершинами информацией о своих висячихузлах, и рассылает каждому висячему узлу рекомендации того, с какими узламинеобходимо образовать связь, чтобы войти во фрактальный граф.
Висячие узлыанализируют данную инфомрацию, сообщая тому узлу, к которому хотятподключиться, о том, какие связи им доступны. Далее угловые вершины вновьобмениваются данной информацией. На основе полученных данных проводитсяанализ на выявление совпадений в списках связей.
При выявлении совпадения(фактически, когда три висячих узла сообщили о том, что могут образоватьнеобходимые для ЗВЗ(А) связи) угловая вершина дает соответствующемувисячему узлу команду о том, что он может начать процесс ЗВЗ(А).
Даннуюкоманду почти одновременно получают три висячих узла, и они выделяют междусобой необходимые связи. Когда данные связи образованы, все три узла посылаютсоответствующим (уже бывшим) угловым вершинам информацию о том, что77ЗВЗ(А) закончена. На этом этапе происходит реорганизация индексов.
Этотпроцесс подробнее будет рассмотрен дальше.Случай второй, ЗВЗ(В).При данной операции происходит рост графа «внутрь». Как былоопределено ранее, при данной операции задействуется только одна «старая»вершина, поэтому процесс ЗВЗ(В) описывается проще. «Старая» вершина знаетсвоих соседей в подграфе-завтравке благодаря индексам, так же она видит все узлы(так же висячие), которые могут создать связь как с ней, так и с один илинесколькими его соседями. Данный вершина передает висячим узлам информациюо том, с кем необходимо образовать связи, чтобы произвести ЗВЗ(В).
Когда онаполучает ответ от трех узлов, что они могут связаться между собой, и каждый изних может связаться с одним из трех соседей «старой» вершины, с которым неможет связаться (или может, но не станет) другой висячий узел, он дает даннымтрем узлам команду выделить связи между собой и произвести ЗВЗ(В). Далеепроисходит реорганизация индексов.Таким образом можно выделить следующие требования, которымнеобходимо удовлетворить для протекания операций ЗВЗ: ЗВЗ(А): Наличие у, как минимум, трех угловых вершин висячих узлов; Из всех висячих узлов три, принадлежащие разным угловымвершинам, могут связаться друг с другом (образовать графтреугольник). ЗВЗ(В): Наличие у вершины, как минимум, трех висячих узлов, каждыйиз которых может связаться с различными соседями даннойвершины в сегменте; Узлы,удовлетворяющиепредыдущемуусловию,связаться между собой.Процессы индексации будут выглядеть следующим образом.могут78Пусть k – число идентификаторов в индексе узла предфрактального графадо операции ЗВЗ (у всех вершин, как было определено, число идентификатороводинаково).При ЗВЗ(А) только что вошедшие в граф вершины будут иметь в своеминдексе первый идентификатор, который равен первому идентификатору тойвершины, с которой они связались, остальные k идентификаторов будут нулевыми.При этом среди «старых» угловых вершин будет одна, которая не участвовала вЗВЗ(А), и теперь все остальные вершины добавляют слева к индексуидентификатор, который равен первому идентификатору индекса данной угловойвершины.
На рисунке 3.16 представлен граф до начала ЗВЗ(А).Рисунок 3.16 – Предфрактальный граф до ЗВЗ(А)На рисунке 3.17 представлен процесс индесации бывших висячих узлов.79Рисунок 3.17 – Процесс индесации висячих узловНа рисунке 3.18 представлен процесс переназначения индексов «старых»вершин.Рисунок 3.18 – Процесс индексации при ЗВЗ(А); а) – до начала процесса; б) –индексация бывших висячих узлов; в) – переназначение индексов «старых» вершин80При ЗВЗ(В) только что образовавшиеся вершины для начала полностьюскопируют индекс той вершины, к которой они присоединились.
Далее каждая изних прибавит справа идентификатор, который равен последнему идентификаторув индексе соответствующей угловой вершины сегмента, соседствующей с той, ккоторой данный узел присоединился.Если до ЗВЗ(В) в индексах вершин не было нулей, то вершина, к которойпроизошло присоединение прибавит справа такой же идентификатор, какой наданный момент является последним в ее индексе; все остальные вершины графаприбавят справа нуль.Если до ЗВЗ(В) в индексе вершины, к которой происходит присоединение,были нули, то вершина заменит самый левый нуль на стоящий перед нимидентификатор, а индексы остальных вершин останутся без изменения.Первый случай возникает, когда ЗВЗ(В) порождает рост порядкафрактальности графа, а второй случай, - когда граф растет без изменения порядкафрактальности.
Пример протекания процесса ЗВЗ(B) представлен на рисунке 3.19.Рисунок 3.19 – Индексация при ЗВЗ(В); а) до начала процесса; б) по завершениюпроцесса81Таким образом, методсаморегуляции VANET-сети с фрактальнойтопологией можно описать как совокупность подходов и алгоритмов к построению,адресации и маршрутизации в сети, которые на каждом шаге роста графа топологиигарантируют ее фрактальные свойства.
Метод саморегуляции VANET-сети долженприменяться при любом изменении в топологии сети (добавлении, удалении узла)и заключается в следующем:1.Выявление узла (узлов) не входящих в структуру предфрактального2.Определение информации, необходимой узлу, чтобы он смог статьграфа.частью предфрактального графа (войти в новый подграф-затравку).3.Связь узла с другими узлами графа, выявление висячих узлов и выборспособа их включения в предфрактальный граф.4.Перестроение индексов узлов предфрактального графа.5.Построение маршрутов согласно алгоритму из раздела 3.1.3.3.3Исследованиепредложенногометодаавтоматизированнойсаморегуляции с использованием имитационной модели VANETсетиДля проверки предложенных подходов к построению, адресации имаршрутизации, разработана имитационная модель VANET-сети.
Имитационнаямодель отражает принцип взаимодействия узлов VANET-сети, представленной ввиде графа. В рамках модели введены два типа сущностей OBU и RSU. Множество = {1 , 2 … } представляет собой набор OBU автомобилей, являющихся узламиVANET-сети. Множество = {1 , 2 … } представляет собой набор RSU,являющихся узлами VANET-сети. Каждый узел или описывается рядомпараметров = {1 , 2 … } для OBU и = {1 , 2 … } для RSU.Параметры, описывающие OBU: текущее местоположение (); список соседей OBU (); радиус охвата ()82 идентификатор в сети (); регистрационный номер (); шлюзовой RSU ();Параметры, описывающие RSU: таблица присутствия OBU (); список соседних RSU () идентификатор в сети ().Граф топологии сети образуется в зависимости от параметров , OBU и , RSU.
Связи каждой из вершин графа соответствуют ее наборусоседей.При помощи программной реализации имитационной модели произведенопыт, заключающийся в подтверждении: возможности создания топологии VANET-сети по правилам,описанным в 3.1.1; корректностираспределенияадресовмеждуузламисетивсоответствии с правилами, описанными в 3.1.2; возможности реализации и проверки работоспособности алгоритмовмаршрутизации, предложенного в 3.1.3.Опыт заключался в проверке возможности объединения в сеть автомобилейи RSU на участке дорожной карты г. Москва, в зависимости от плотностиавтомобилей на дорогах.В рамках опыта разработанная программа воспроизводила случайныеучастки дорожной карты Москвы площадью 2 кв.
км. и случайным образомрасставляла на ней определенное количество точек, соответствующих положениюавтомобилей и единственного RSU. OBU и RSU описываются параметрами ={1 , 2 … } и = {1 , 2 … }.Далее расположенные на карте точки объединялись в сеть согласноправилам, описанным в 3.1.1, радиус охвата каждого из узлов был принят за 300метров. Пример 500 OBU объединенных в сеть с предфрактальной топологией83представлен на рисунке 3.20.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
