ГЛАВА 2
ФОРМИРОВАНИЕ ОПТИМАЛЬНОГО ПУТИ МНОГОАБОНЕНТСКОЙ ДОСТАВКИ СООБЩЕНИЙ
2.1. Построение дерева доставки сообщений
Не зависимо от способа маршрутизации при многоабонентской доставки формируется
дерево доставки сообщений. При использовании статических методов маршрутизации
дерево доставки сообщений формируется перед началом сеанса передачи информации
на основе маршрутной информации, расположенной в коммутационных узлах сети. При
динамической маршрутизации дерево доставки сообщений формируется в процессе
продвижения многоадресного пакета по сети. При использовании различных способов
лавинообразной маршрутизации также происходит формирование дерева доставки
сообщений. Таким образом, задачу многоадресной передачи можно рассматривать в
контексте формирования оптимального дерева доставки сообщений.
В случае фиксированной структуры системы дерево доставки является достаточно
стабильным. В мобильных системах дерево доставки динамически изменяется в связи
с перемещением МТ.
В общем случае, компьютерную сеть можно представить в виде нагруженного графа
G(V, E), где V= { viзi=1,2…n}- множество вершин графа, E={ei,jзi,j=1,2…n} –
множество ребер графа. Каждое ребро ei,j графа характеризуется весом wi,j. В
зависимости от решаемой задачи величина wi,j может характеризовать длину li,j
ребра, задержку ti,j или стоимость ci,j передачи информации по каналу,
соответствующему ребру ei,j.
При рассмотрении вопросов маршрутизации и распределения потоков [59,60,61] в
качестве ограничения вводится значение допустимой задержка td доставки пакетов
между произвольными узлами сети, а в качестве критерия оптимизации
рассматривается сумма весов W ребер, образующих данный путь. Сумму весов пути
принято [62,63] отождествлять с его стоимостью. При использовании известных
алгоритмов формирования кратчайших путей к каждой вершине формируется свой
собственный путь не зависимо от путей к другим вершинам. В случае
многоабонентской доставки это приводит к неоправданному дублированию
информационных потоков [64]. В качестве примера рассмотрим нагруженный граф,
представленный на рис. 2.1.
Рис. 2.1.
Здесь в качестве исходной вершины выступает вершина v1 , которая связана
кратчайшими путями с множеством вершин Vm = { viзi=12,…,16}.
В табл. 2.1. приведены значения весов wi,j ребер ei,j графа, представленного на
рис 2.1.
Таблица 2.1
v1
v2
v3
v4
v5
v6
v7
v8
v9
v10
v11
v12
v13
v14
v15
v16
v1
-
-
v2
-
-
v3
-
-
v4
4
-
v5
11
-
v6
11
10
12
v7
10
-
v8
0
14
15
v9
-
10
v10
14
5
v11
12
10
v12
-
-
v13
-
-
v14
-
-
v15
5
6
v16
15
В соответствие с значениями wi,j между вершиной v1 и вершиной v11 формируется
минимальный путь P0 = (e1,3, e3,7, e7,10, e10,11) с длиной L0=15.
Между вершиной v1 и вершиной v12 формируется путь P1 = (e1,3, e3,6, e6,9,
e9,12) с длиной L1=16.
Между вершиной v1 и вершиной v13 формируется путь P2 = (e1,2, e2,5, e5,13) с
длиной L2=15.
Между вершиной v1 и вершиной v14 формируется путь P3 = (e1,3, e3,7, e7,10,
e10,11, e11,14) с длиной L3=18.
Между вершиной v1 и вершиной v15 формируется путь P4 = (e1,4, e4,8, e8,15) с
длиной L4=14.
Между вершиной v1 и вершиной v16 формируется путь P5 = (e1,3, e3,7, e7,10,
e10,16) с длиной L5=17.
Несмотря на то, что каждый из путей является кратчайшим, общая длина всех
путей, исключая путь P0, достаточно значительная и равна 85. На рис. 2.1
кратчайшие пути выделены жирными линиями.
В случае многоабонентской доставки сообщений с источником в вершине vs и
множеством вершин Vm = { viзi=1,2…n}, определяющих группу АС, получателей
информации, задача маршрутизации состоит в нахождении дерева Ts = (Vs, Es )
доставки сообщений для которого выполняется условие:
, (2.1)
где: Ws - вес всех ребер дерева доставки сообщений.
В качестве ограничения на включение ребра ei,j в состав дерева Ts
рассматриваются условия:
* Bi,j> bs, где: Bi,j - значение пропускной способности канала; bs - требуемое
значение пропускной способности для многоабонентской доставки сообщений по
дереву графа Ts.
* td >tmax , где: td – значение допустимой задержки передачи пакетов; tmax –
максимальная задержка передачи пакетов между узлами дерева многоабонентской
передачи данных.
В общем случае источник (вершина vs) может находиться вне группы
многоабонентской доставки или входить в нее. Не зависимо от месторасположения
источника выполняются условия: Vm М Vs Н V и Es М E.
Рассмотрим случай при котором вершина vs не принадлежит группе многоабонентской
доставки сообщений, то есть vs П Vm и Vm М Vs. иначе vs О Bs и Bs Н Vs .
Множество вершин V0= Vs / Vm , является вспомогательным и обеспечивает
связность вершин дерева Ts. Мощность множества Ts оказывает влияние на
временную сложность процедуры многоабонентской доставки сообщений. С
уменьшением мощности множества Ts временная сложность многоабонентской доставки
сообщений снижается.
В качестве примера рассмотрим граф, представленный на рис. 2.2. Группу
многоабонентской дост