ГЛАВА 2
Формирование устойчивого подграфа доставки
информации
2.1. Формирование устойчивых соединений
Общее время, затрачиваемое на обновление маршрутной информации, зависит от
частоты выполнения процедуры маршрутизации и ее временной сложности. В свою
очередь, частота изменения маршрутной информации определяется устойчивостью
выбранных маршрутов. Под устойчивостью маршрута будем понимать свойство
маршрута обеспечивать передачу информации (сеанс обмена) без реконфигурации. В
этом случае задача уменьшения времени обновления маршрутной информации
сводиться к задаче формирования устойчивых путей [28] [1 Асад Махмуд Асад Аль
Насер, Аль Рабабах Мохамед Абдель-Кадер . Способ формирования устойчивых
виртуальных соединений в мобильных компьютерных сетях //Вiсник НТУУ “КПI”
Iнформатика, управлiння та обчислювальна технiка.–2002.-№ 39.-С. 126-131.
]. Каждому ребру ei,j графа G= (V, E) сопоставим величину pi,j, характеризующую
вероятность удаления ребра ei,j из графа. Соответственно, выражение p0i,j = 1–
pi,j характеризует устойчивость канала передачи данных между смежными АС. В
общем случае устойчивость пути Zn,m определяется следующим выражением:
(2.1)
Как правило, удаление некоторого ребра в графе связности сети Ad Hoc связано с
перемещением смежной АС, которой сопоставим величину pўi ,
представляющую собой вероятность удаления вершины или ее перемещения,
приводящего к изменению структуры графа. Соответственно, величина pi0 = 1- pўi
характеризует устойчивость вершины vi .
Очевидно, что вероятность удаление ребра определяется вероятностями удаления
смежных вершин, то есть:
pi,j= 1–(1– pўi )(1– pў j),
или
pi,j = pўi + pўj– pўiЧ pўj. (2.2)
Далее, определим понятия стабильности подграфа Gs = (Vs, Es) графа G= (V, E).
Подграф Gs = (Vs, Es) графа G = (V, E) стабильный, если " ei,j , pi,j ®0.
Подграф Gs = (Vs, Es) графа G = (V, E) абсолютно стабильный, если " ei,j , pi,j
=0.
Для нагруженного графа, в случае ограничения на пропускную способность каналов
передачи данных и заданной интенсивности обслуживания потоков в узлах, задержка
информации в узлах может превысить допустимую, что приводит к отказу в
обслуживании. Это также приводит к необходимости ремаршрутизации и
рассматривается как удаление вершины.
Далее, рассмотрим минимальный путь между двумя наиболее удаленными вершинами
графа, называемый диаметром (d) графа. Линейный подграф, множество вершин
которого образуют диаметр графа, обозначим как G0 = (V0, E0), соответственно: V
={ vi0 , vi | i О с }, E ={ei,j | iОA0; jОA0 }, где: vi0 – граничные вершины
диаметра графа, vi - промежуточные вершины диаметра графа, A0 – множество
индексов вершин ,образующих диаметр графа. Соответственно, устойчивость
диаметра графа Sd зависит от устойчивости его ребер, то есть: Sd =¦( Si,j ч "
ei,j О E0).
С учетом вероятности удаления ребер из диаметра графа его устойчивость
определяется по формуле:
(2.3)
Устойчивость диаметра графа можно считать одной из основных характеристик
случайного графа, влияющих на выбор стратегии управления передачей информации.
В частности устойчивость диаметра графа гарантирует то, что для любой пары АС
минимальный путь не превысит диаметр графа. Если в слабосвязанном графе диаметр
графа проходит через область сочленения подграфов и является устойчивым, то
граф остается связным при перемещении вершин, не определяющих диаметр графа.
Как правило [29-30], формирование маршрутов доставки информации связано с
построением минимального покрывающего дерева. В данном случае формирование
маршрутов доставки следует рассматривать как задачу построения максимально
стабильного дерева доставки сообщений, обеспечивающего требуемый уровень
сервиса. Для повышения стабильности дерева доставки сообщений необходимо на
множестве V ={vi | i=1,2,…,n} вершин графа определить подмножество Vs ={vi |
i=1,2,…,n}, позволяющее сформировать максимально стабильное дерево доставки
сообщений. В качестве примера рассмотрим две смежные ячейки С1 и С2 сети Ad Hoc
(рис.2.1). Как отмечалось выше, при организации сети в виде ячеек в каждой из
них назначается базовая станция (БС). Все остальные АС ячейки осуществляют
передачу информации через БС, в зоне действия которой они находятся. АС,
находящиеся в смежной области действия двух БС выполняют функции связующих
элементов (мостов) ячеек.
При определенных условиях несколько АС могут выполнять функции БС или мостов.
Например, на рис. 2.1. АС v6 и v4 могут выполнять функции мостов, а АС v1 , v2
, v3 , v5 могут выполнять функции БС ячейки C1. В свою очередь АС v7 , v8 , v10
- функции БС ячейки С2.
Рассмотрим необходимое условие назначения АС vi в качестве БС bj ячейки Сj .
Пусть Rj – радиус ячейки С1, а ri - радиус покрытия АС vi.
Пусть существует условие ri і Rj . Условие ri = Rj предполагает наличие
единственной АС, расположенной точно в центре ячейки. Условие ri > Rj допускает
наличие нескольких АС, расположенных в области Wj с радиусом rwj = ri – Rj . vi
О Wj являются потенциальными БС. Число р определяющее количество vi О Wj будем
называть р –центром ячейки.
Таким образом, р центр ячейки – множество АС из которых доступны все остальные
АС данной ячейки. Каждая из АС р-центра может выступать в качестве БС или они
могут разделять между собой нагрузку.
В качестве необходимого и достаточного условия выбора АС vi в качестве БС bj
ячейки Сj определим следующее условие:
bj = {viч (1– pўj )=max " vi О Wj }. (2.4)
Рис.2.1.
Аналогичным образом определим условие выбора АС vi в качестве моста mi,j между
ячейками Сi и Сj:
; (2.5)
Выражения (2.4)
- Київ+380960830922