ГЛАВА 2
Формирование маршрутов в мобильных компьютерных сетях
2.1. Оптимальная маршрутизация в мобильных компьютерных сетях
В общем случае задача оптимальной маршрутизации рассматривается как задача
выбора представительного множества путей, оптимальных по заданному критерию.
Одним из наиболее распространенных подходов к решению задач оптимизации
является подход, при котором один из параметров рассматривается в качестве
критерия оптимизации, а остальные переводятся в ранг ограничений. В сетях с
фиксированной топологией в качестве критерия оптимизации рассматривается время
передачи пакетов, отождествляемое с длинной пути. В этом случае данная задача
сводится к задаче нахождения кратчайшего пути. В общем случае данная задача
является NP-полной, то есть имеет экспоненциальную сложность, поскольку имеет
явный переборный характер. Вопросы оптимальной маршрутизации при наличии одного
источника и одного получателя информации достаточно подробно рассмотрены в
работах [81-88]. При наличии одного источника и некоторого множества
получателей информации формируется дерево оптимальных путей.
В общем случае, при некотором множестве источников и получателей информации,
множество деревьев оптимальных путей целесообразно объединить в частично
остовной граф. Под частично остовным графом будем понимать связанный граф,
покрывающий заданное множество вершин.
Для мобильных компьютерных сетей в качестве критерия оптимальности дерева путей
целесообразно рассматривать минимальное время ремаршрутизации, обеспечивающее
безразрывную передачу информации при перемещении абонентских систем. В этом
случае длина пути переходит в разряд ограничений. Время ремаршрутизации зависит
от количества и времени возвратов по виртуальному дереву в результате
перемещения абонентских систем. Узел дерева в котором осуществляется изменение
маршрута будем называть точкой ветвления маршрута. Время ремаршрутизации Тс
между двумя смежными листьями равно: Тс = Тз + Тр, где: Тз - задержка в
передачи по звену дерева, т.е. между соседними вершинами; Тр – время коммутации
в точке ветвления. При наличии некоторого числа k промежуточных звеньев время
маршрутизации равно: Тс = ТзЧ k + Тр. При расположении точки ветвления на i –ом
уровне Тi равно Тi = ТзЧ i + Тр.
При последовательном обходе всех листьев каждая точка ветвления обходиться m
-1, где: m- число нисходящих ветвей дерева. В этом случае суммарное время
ремаршрутизации при обходе всех листьев определяется величиной:
На основании анализа полученного выражения можно сделать вывод, что с
сокращением числа уровней дерева сокращается время ремаршрутизации. Таким
образом задачу сокращения времени ремаршрутизации можно свести к задаче
построения дерева с минимальным числом уровней.
В свою очередь большинство алгоритмов маршрутизации базируется на алгоритмах
нахождения минимального пути Дейкстра или Флойда, которые не обеспечивают
минимальное число уровней дерева.
В общем случае время выполнения [84] алгоритма Дейкстра нахождения минимального
пути между двумя вершинами равно: , где - число дуг графа, а – число его
вершин. В свою очередь нахождение кратчайших путей между парами всех вершин
графа равно: , что значительно лучше, чем для алгоритма Флойда , особенно для
больших разряженных графов.
В реальных случаях вместо задачи нахождения кратчайших путей целесообразно
формировать некоторое множество путей, длина которых не превышает некоторой
допустимой величины . В этом случае время выполнения алгоритма нахождения путей
между всеми парами вершин графа может быть сокращено. В данной работе
предлагается следующий способ решения данной задачи.
Пусть задан граф G=(V,U) с некоторым множеством V вершин и множеством U ребер.
Разобьем (рис. 2.1) граф G=(V,U) на два подграфа: G=(V0,U0) и G1=(V1,U1). ,
где: , при чем вершина , а вершина .
В общем случае построение пути из произвольной вершины vs П V1 до вершины vi О
V1 возможно при условии: T(Pmax)і T(P0s,i), где: P0s,I - минимальный путь от
вершины vs до наиболее удаленной вершины vi О V1.
С целью оценки граничных значений времени задержки передачи информации
рассмотрим произвольный путь Ps,i от вершины vs к вершине vi О V1, проходящий
через вершину vk О V1. В этом случае этот путь Ps,i=(ds,k) + Pk,i , где: vk О
Vs и vi О Vs .
Затем в качестве вершины vk выбираем вершину, ближайшую к вершине vs, что
соответствует расстоянию dmin . В этом случае Ps,i = dmin + Pk,i . Путь Pk,i
принадлежит множеству путей подграфа G1 потому, что vk О V1 и vi О V1 . Из
этого следует, что D1 і Pk,i , где: и соответственно: Ph і Ps,i . В этом случае
верхняя граница задержки передачи данных Th при vs П Vs определяется следующим
соотношением:
Th = T(dmin )+ T(Ds).
В свою очередь, нижняя граница задержки передачи Ta определяется расстоянием от
вершины vs до наиболее удаленной вершины vi О V1 .
Рассмотрим процедуру формирования множества путей между вершиной vs и
множеством вершин vi О V1
Пусть выполняется условие:
, (2.1)
где: - минимальный путь до ближайшей вершины vm О V1.
Это соответствует тому, что вершина vm О V1 является ближайшей к вершине vs.
Далее, обозначим через эксцентриситет вершины в подграфе G1=(V1,U1).
В данном случае достаточным условием допустимого пути между вершиной и любой
вершиной vi О V1 является:
(2.2)
С учетом условия (2.2) стратегия построения множества допустимых путей между
вершиной и множеством вершин V1 заключается в следующем:
Находится с помощью метода Дейкстра минимальный путь до ближайшей вершины vm О
V1.
Определяются кратчайшие пути внутри подграфа G1=(V1,U1), ме