Диссертация (1143658), страница 10
Текст из файла (страница 10)
Максимальное расстояниемежду вершинами в графе равно диаметру графа.Рассмотрим теорему «О кратчейшем пути между максимально удаленнымивершинами в предфрактальном графе с полносвязной затравкой».Теорема: В предфрактальном графе n-го порядка фрактальности сполносвязным графом в качестве затравки кратчайший путь между двумявершинами содержит не более (2n – 1) ребер.Доказательство:Докажемданноеутверждение,используяметодматематической индукции.1) n = 1. В данном случае имеется граф-затравку, он полносвязный, такчто длина пути между двумя любыми вершинами равна 1.
Так же 21 –1. Условие выполняется.702) n = 2. Имеется предфрактальный граф с четырьмя подграфамизатравками. На предыдущем шаге определено, что длина пути вподграфе-затравке равна 1. Длина пути между двумя подграфамизатравками так же равна 1.
Тогда возможно из любого узла внутриподграфа-затравкипереместитьсявдругой(1шаг),далеепереместиться в нужный подграф-затравку (1 шаг), наконец внутриэтого подграфа переместиться к нужной вершине (1 шаг). Такимобразом длина маршрута равна 3. 22-1 = 3. Условие выполняется.3) n = k. Согласно условию теоремы, возможно переместиться междудвумя узлами графа, который представляет собой предфрактальныйграф (k-1)-го порядка, за 2k-1-1 шагов. Учитывая закономерностьнайденнуюнавторомшаге,получаем:(2−1 − 1) + (2−1 − 1) + 1 = 2 ∙ (2−1 − 1) + 1 = 2 − 1Таким образом, путь заданной длины существует.
Его эффективностьследует из рассуждений в ходе доказательства: из пункта два следует, что внутриподграфа-затравки мы всегда перемещаемся по одному ребру, так же мыиспользуем только одно ребро для перехода между подграфами-затравками. Какбыло сказано, единица – это кратчайшее возможное расстояние между двумявершинами, следовательно, самое эффективное из возможных. Таким образом еслипри перемещении от узла к узлу внутри подграфа-затравки используется наиболееэффективный путь и при перемещении от подграфа-затравки к другому подграфутак же используется наиболее эффективный путь, то можно сделать вывод, что ихсовокупность так же является наиболее эффективный путем.Рассмотрим заключение доказательства более подробно, чтобы оно быломаксимально понятно: воспользуемся графом на рисунке 7.
Рассмотрим путь отвершины «aa» к вершине «cb». В подграфе «А» необходимо переместиться за однодействие, при этом в конечном итоге мы окажемся в подграфе «С», переход вкоторый имеется у вершины «ac», необходимо переместиться в вершину «ac».Далее необходимо перейти в другой подграф, и в подграфе «С» мы уже71гарантировано не более чем за один шаг можем переместиться в вершину «cb».Таким образом, три шага, как и утверждает теорема.
Если рассмотреть всевозможные маршруты, то можно видеть, что они длиннее: если в подграфе «А»переместиться в «ac» не напрямую, то, путь станет как минимум на один шагбольше, а если переместиться изначально не в подграф «С», но в любой другой, тоэто будет означать, что чтобы переместиться в граф «С» нужно сделать одиндополнитльныйпереходмеждуподграфами,атакжесделатьодиндополнительный шаг внутри подграфа (т.к. по третьему правилу одна вершина неможет быть связана более, чем с одним подграфом). В первом случаенеэффективность маршрута заключалась в том, что между двумя узлами в затравкеперемещение произошло более, чем за 1, во втором случае перемещение междуподграфами произошло более, чем за 1 шаг.
Соответственно неэффективныепереходы от вершины к вершине создали неэффективный маршрут.В названии сказано, что это теорема о кратчейшем пути между максимальноудаленными вершинами в предфрактальном графе с полносвязной затравкой, т.е.между не максимально удаленными вершинами путь может быть и меньше. Так,например, рассматривая тот же граф, при необходимости попасть из «aa» в «ba», тократчайший (следовательно эффективнейший) путь содержит только два ребра.Очевидно, это связано с тем, что нет необходимости двигаться в подграфе «В».Однако теорема не утверждает, что кратчайший маршрут только один. Так,например, в том же графе эффективных путей от вершины «ab» к вершине «cb»два:ab – ac – ca – cb.ab – ba – bc – cb.Теперь перейдем к рассмотрению алгоритма маршрутизации. Данныйалгоритм как раз будет выделять только один маршрут.Смысл алгоритма заключается в том, что для перехода из одного сегментаX в другой сегмент Y необходимо на каждом шаге перемещаться в вершину *yвнутри затравки, а затем в единственную соседствующую затравку.72Для лучшего понимания алгоритма рассмотрим предфрактальный граф n-гопорядка, представленный на рисунке 3.13.
Для того чтобы до сегмента, напримерD, из любого другого сегмента (A, B, C), необходимо добраться до единственногоребра соединяющего, эти сегменты т.е. «add..», «bdd..», «cdd..».Рисунок 3.13 – Предфрактальный граф n-го порядкаВ свою очередь, для этого необходимо добраться до сегмента D подграфепредыдущего порядка (рисунок 3.14).Рисунок 4.14 – Предфрактальный граф n-1-го порядка73Повторим эту операцию еще n-3 раза (рисунок 3.15).Рисунок 3.15 – Предфрактальный граф 2-го порядкаТаким образом, видно, что для перехода в необходимый сегмент (напримерD), нужно на каждом шаге переходить в вершину *d внутри затравки, а затем вединственную соседнюю затравку.Данный алгоритм можно удобно рассмотреть, как алгоритм преобразованиявходного индекса в выходной за минимальное число шагов.
При этом за один шагиндекс можно преобразовать в другой только согласно правилу преобразованияиндекса.Вход: индекс Q, индекс W.Выход: индекс E = индекс В.Если индексы – это массивы, то указатель – номер элемента в массиве. Еслиимеется указатель x, то выражение «идентификатор x» следует понимать как«элемент массива, на который указывает x». Если указатель смещается вправо запредел индекса, то он указывает на пустую ячейку.Шаг 1.Установим указатель x на последний идентификатор Q,установим указатель y на первый идентификатор W, установим указатель z напервый идентификатор Q.74Приведенное правило замены, если рассмотреть его подробно аналогичноописанному выше правилу преобразования индекса. Многоточие означает, чтопоследний идентификатор повторяется некоторое число раз, и кроме него справадругих идентификаторов нетШаг 2.Если идентификатор x не равен идентификатору y, то заменитьидентификатор x на идентификатор y по следующему правилу: заменаидентификатора x на y возможна, когда Q имеет вид *a, либо *ab…; в первомслучае результатом будет *b, во втором - *ba… Установить x на последнийидентификатор Q.
Иначе сдвинуть указатель x на один влево, если возможно, иначене делать ничего.Шаг 3.Если идентификатор z равен идентификатору y, тогда сдвинуть yна один вправо, установить x на последний идентификатор Q, сдвинуть z на одинвправо. Иначе не делать ничего.Шаг 4.Если идентификатор y равен 0 или указывает на пустую ячейку,то закончить алгоритм. Иначе вернуться к шагу 2.3.2Описание метода саморегуляции VANET-сети с фрактальнойтопологиейВ данном разделе описывается метод автоматизированной саморегуляцииVANET-сети с фрактальной топологией. Метод основывается на подходах иалгоритмах к построению, адресации и маршрутизации в предфрактальныхструктурах,описанныхвразделе3.1.Подтермином«саморегуляция»подразумевается способность сети к перестроению своей топологии без нарушенияфрактальности, а также способность к построению оптимальных маршрутов наоснове описанного алгоритма маршрутизации.
В данном разделе описываетсяпроцесс построения VANET-сети с предфрактальной топологией, под терминомузел и вершина понимаются OBU автомобиля или RSU.Систему адресации на основе индексов удобно использовать в процессахпостроения сети, т.к. индексы позволяют определять узлам, какое место в сети онизанимают и с кем они связаны.75Ранее были рассмотрены два способа ЗВЗ: ЗВЗ(А) – Замена вершины затравкой при помощи операциидобавления нового узла; ЗВЗ(В) – Замена вершины затравкой при помощи операции разбиенияребра.Одна из особенностей этих операций заключается в том, что при ихприменении новый узел связывается ребром с одной старой вершиной, в случаеЗВЗ(А), или с двумя, в случае ЗВЗ (В), при этом, учитывая, что речь идет опредфрактальных графах, очевидно, что даже в случае ЗВЗ(В) в конечном счетеновый узел образует подграф-затравку только с одной старой вершиной.
То естькаждый новый узел производит подключение только к одной вершине, состоящейв предфрактальном графе.Данноесвойствоудобноиспользоватьвпроцессахобразованиясамоподобной топологии сети, т.к. появляется возможность выделить конечноемножество вершин, участвующих в образовании нового подграфа-затравки, дажево фрактальном (бесконечном) графе [88].Теперь нужно определить, какая информация необходима узлу, чтобы онсмог стать частью предфрактального графа (войти в новый подграф-затравку).Наиболее важной информацией, которую новый узел должен получить отстарой вершины, является индекс старой вершины. Учитывая систематикуиндексов и их уникальность, новый узел сможет определить свое будущее место вграфе, зная индекс той вершины, к которой он присоединяется.Остальная необходимая новому узлу информация определяется видомоперацииЗВЗ,которуювыполняетновыйузел,чтобыстатьчастьюпредфрактального графа.Следует так же оговорить следующее, ограничение на четыре связиработает исключительно внутри фрактальной топологии.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
