ГЛАВА 2
Маршрутизация с использованием кластерной организации мобильной сети
2.1. Выбор размера кластера
Разбиение сети на кластеры в диссертационной работе сведено к задаче
формирования на заданном множестве V ={vi | i=1,2,…,n} вершин графа G = (V, E)
нечетких множеств с максимальной суммой кардинальных чисел . Выражение
представляет собой пару , где: - функция принадлежности, которая представляет
собой некоторую меру соответствия элемента нечеткому множеству. Функция
принадлежности характеризует взаимное расположение АС, скорость и направление
их перемещения, уровень принимаемого сигнала. Значение функции принадлежности,
как правило, определяется на канальном уровне эталонной модели открытых систем
и при решении задачи маршрутизации рассматривается в качестве исходного
параметра.
При кластерной структуре сети время маршрутизации зависит от размера кластеров
. С целью оценки данной зависимости представим суммарное время маршрутизации
как:
, (2.1)
где: – вероятность межкластерной маршрутизации; – время внутрикластерной
маршрутизации (т. е. время необходимое для маршрутизации АС внутри группы);–
время межкластерной маршрутизации. При использовании внутри кластера
лавинообразной маршрутизации и одинаковом времени обработки пакетов в узлах
максимальное значение времени внутрикластерной маршрутизации равно: где: –
диаметр графа кластера.
В свою очередь, если остовное дерево в процессе маршрутизации не изменяется, то
время межкластерной маршрутизации равно: где: – количество промежуточных узлов
на межкластерном участке пути. С учетом этого суммарное время маршрутизации
будет равно:
(2.2)
Очевидно, что наличие всего одного кластера, содержащегоячеек, , а при числе
кластеровзначение . В общем случае: .
При относительно больших размерах кластера вероятность межкластерной
маршрутизации может быть выражена через соотношение общего числа ячеек кластера
к числу его приграничных ячеек. Площадь области внутри кластера и приграничной
области равно [61]:
где: – диаметр области покрытия АС, а – диаметр кластера.
Тогда вероятность инициации межкластерной маршрутизации:
Учитывая ограничение , а также, при получим:
, (2.3)
Подставив выражение (2.3) в выражение (2.1) получим зависимость суммарного
времени маршрутизации от основных параметров сети:
(2.4)
На рис. 2.1 представлены зависимости суммарного времени маршрутизации от
диаметра кластера при различных значениях .
Рис.2.1
Кривая 1 соответствует значению =30, кривая 2 соответствует значению =20,
кривая 3 соответствует значению =15, кривая 4 соответствует значению =10. Как
видно из рис. 2.1 суммарное время маршрутизации носит нелинейный характер и в
значительной мере зависит от соотношения между размером кластера и
межкластерной областью. При этом суммарное время маршрутизации при небольшом
диаметре кластера и значительном количестве промежуточных узлов на
межкластерном участке пути резко возрастает. При увеличении диаметра кластера
влияние промежуточных узлов на суммарное время ремаршрутизации существенно
уменьшается и практически определяется временем внутрикластерной маршрутизации.
Полученные выше соотношения используются для формирования оптимальной структуры
кластеров.
С другой стороны, при использовании лавинообразной маршрутизации внутри
кластера при увеличении его размеров значительно возрастает поток управляющих
пакетов. Таким образом, размер кластера определяется из соотношения объема
управляющей информации и общего времени маршрутизации.
2.2. Алгоритма формирования кластеров
Большинство известных способов формирования кластеров [62-65] являются
централизованными, так как предполагают выбор некоторой вершины в качестве
начальной. Распределенный алгоритм формирования кластеров определяет
возможность выбора произвольной вершины в качестве исходной вершины. При этом в
качестве начальной вершины может быть выбрана вершина с максимальной или
минимальной степенью. Аналогично, в качестве предпочтительной смежной вершины
может быть выбрана вершина с максимальной или минимальной степенью. Таким
образом, возможно четыре способа формирования кластеров, которые и были
исследованы в рамках данной диссертационной работы. Более того, распределенный
алгоритм должен допускать одновременное формирование кластеров с несколькими
исходными вершинами.
которые выполняются на основе информации, предоставляемой пакетами –
периодическими сообщениями, которыми обмениваются только соседние узлы.
Содержимое пакета простое поначалу и усложняется на каждой фазе алгоритма.
Вначале каждый узел сетевой топологии выполняет алгоритм выбора
предпочтительного соседа. Затем создается лес путем соединения каждого узла к
его предпочтительному соседу и наоборот. Далее выполняется алгоритм
кластеризация внутри деревьев для того, чтобы придать соответствующую структуру
каждому дереву и построить таблицу внутризонной маршрутизации для каждого узла.
После этого алгоритм кластеризация между деревьев предоставляет структуру из
деревьев, которая сохраняется в таблицах межзонной маршрутизации узлов-шлюзов
(узлы из разных деревьев или зон, но в диапазоне прямой передачи друг к другу).
Каждому дереву присваивается имя выполнением алгоритма именования зон. Так как
построенный лес содержит множество деревьев и каждому дереву присвоено имя, то
сеть разбита на множество не перекрывающихся динамических зон.
Важным отличием алгоритма является то, что он использует пакеты для построения
леса, а также дл
- Киев+380960830922