Студопедия

Главная страница Случайная страница

Разделы сайта

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






Й этап (корректировка маршрутов)






На каждом шаге алгоритма происходит обновление оценок стоимостей по рекуррентной формуле:

), (7.2)

где – «коэффициент обучения» (обычно выбирается m =0.5), а lk(f, r) вычисляется по формуле:

. (7.3)

Технология прокладки маршрута с помощью описанного алгоритма заключается в следующем: при передаче пакета данных узлу-получателю f узел-источник s0 сначала пересылает его к соседнему узлу r=a1, на котором значение функции минимально, затем этот узел a1 пересылает пакет узлу r=a2, на котором достигается минимум функции и т.д. до тех пор, пока пакет данных не придет в заданный узел-получатель f.

Эффективность описанного алгоритма Q-маршрутизации зависит от выбора коэффициента обучения μ [25]. При значениях m, близких к 1, вырастет риск возникновения так называемых «узких мест», т.е. появления маршрутов, совместно используемых для передачи данных несколькими парами «источник-получатель».

Заметим, что если маршрут оптимален, то любой содержащийся в нём подмаршрут тоже оптимален. Таким образом, если несколько пар «источник-получатель» будут передавать пакеты данных только по оптимальному маршруту, то это с большой вероятностью приведёт к перегрузке соответствующих каналов связи ТКС.

При значениях “коэффициента обучения” m, близких к 0, изменения стоимостей маршрутов будут мало влиять на решение. В этом случае вычисляемые по алгоритму маршруты могут быть достаточно далеки от глобально оптимальных.

Экспериментальные исследования показали, что распределённый алгоритм Q-маршрутизации достаточно легко адаптируется как к непредсказуемым изменениям структурных параметров динамических ТКС, так и к возможным изменениям направлений и интенсивности информационных потоков в них. На рис.7.1. приводится сравнительная характеристика алгоритмов Q-маршрутизации (Q-routing) и OSPF-алгоритма (Shortest path) [25]. Ось X на приведённой диаграмме соответствует средней загрузке сети, ось Y - среднему времени доставки пакетов. Как видно из рис. 7.1, при увеличении нагрузки на сеть алгоритм Q-маршрутизации оказывается более устойчивым, чем OSPF (который является стандартом в современных сетях).

Рис.7.1. Сравнительная оценка эффективности работы алгоритмов Q-маршрутизации и OSPF

7.3. Мульти-агентная маршрутизация информационных потоков

В мульти-агентной постановке задачи маршрутизации каждый узел рассматривается как автономный сетевой агент (АСА), самостоятельно принимающий решения на основе имеющейся у него сетевой информации. Эта информация не обязательно в точности отражает действительное состояние ТКС и может использоваться агентом для передачи её другим агентам (как это представлено на рис. 7.2, б). Кроме того, узловые агенты могут объединяться в группы, совместно решая задачу определения и прокладки оптимальных маршрутов.

Таким образом, мульти-агентная модель содержит в себе классическую модель маршрутизации, изображенную на рис.7.2, а. Однако она позволяет решать задачи маршрутизации в условиях неполноты и/или неопределённости имеющейся сетевой информации.

 

 

a)
б)

Рис.7.2. Классическая и мульти-агентная модели ТКС

Для нахождения решения задачи мульти-агентной маршрутизации обычно используют одну из двух схем [29–31, 69]:

- централизованную с координатором («глобально-оптимальное» решение), когда сбор сетевой информации и принятие решений для группы агентов осуществляется специальным ведущим агентом-координатором,

- распределенную («локально-оптимальное» решение), когда каждый агент ТКС принимает решение самостоятельно.

Эти схемы представлены на Рис. 7.3, а) и б).

 

a)
б)

Рис.7.3. Централизованная и распределённая схемы маршрутизации

7.3.1. Построение графовой модели мульти-агентной сети

В качестве математической модели статической ТКС, чьи коммуникационные характеристики не изменяются с течением времени, будем рассматривать граф

(7.4)

где V – множество узлов, E – упорядоченное множество направленных дуг.

Определим набор параметров, характеризующих коммуникационные возможности мульти-агентной ТКС. Рассмотрим множество всевозможных пар узлов графа G вида:

(7.5)

где первый элемент пары является узлом-источником необходимых данных, а второй – узлом-получателем запрошенных данных. Остальные параметры мульти-агентной модели определены следующим образом:

D – множество пар «источник-получатель», осуществляющих передачу пакетов в данный момент времени (),

Π – упорядоченное множество всех маршрутов для всех пар узлов из D (оно может быть усечённым, как это представлено на рис.7.4),

Π d – множество возможных маршрутов для данной пары узлов .

s
f

Рис.7.4. Усечённое множество маршрутов для пары «источник-получатель» узлов s и d.

На возможных маршрутах передачи данных Π d зададим матрицу инциденций

, где (7.6)

7.3.2. Постановка задачи маршрутизации для мульти-агентной сети

Любая задача мульти-агентной point-to-point маршрутизации информационных потоков может быть описана конечным набором пар узлов ТКС .

Определим основные параметры задачи:

Φ d – интенсивность информационного потока между узлами пары ,

Φ = (Φ 1, Φ 2, …) – вектор распределения интенсивности информационных потоков,

– общая интенсивность информационных потоков D,

xp – общая интенсивность информационного потока на маршруте ,

x = (x1, x2, …) – вектор распределения информационных потоков,

δ lp – доля интенсивности информационного потока xp, которая приходится на дугу l,

ρ l – нагрузка на дугу , определяемая по формуле

,

ρ = (ρ l, ρ 2, …) – вектор распределения нагрузок на дуги,

Tp – средняя стоимость маршрута ,

T = (T1, T2, …) – вектор распределения стоимостей по маршрутам.

 

Для формализации и решения задачи оптимальной маршрутизации введём дополнительные условия:

 

I. Средняя стоимость маршрута определяется как сумма стоимостей нагрузок на его дуги, т.е.

;

II. Для любой дуги справедливо

и ;

III. Для каждой дуги , T l (p l) выпукла и либо строго монотонно возрастает на интервале, где T l (p l)< ∞, либо T l (p l) = const;

IV. Функция T l (p l) непрерывна на всей области определения, причем на интервале, где T l (p l) < ∞, она непрерывно дифференцируема.

Для централизованной схемы с агентом-координатором решение задачи мульти-агентной маршрутизации представляет собой некоторое распределение информационных потоков, при котором общие затраты на их обслуживание минимальны.

Пусть F – общая стоимость распределения информационных потоков. Тогда

. (7.7)

Для любого маршрута и для любой пары узлов справедливы соотношения

. (7.8)

Таким образом, постановка задачи для централизованной схемы мульти-агентной маршрутизации запишется следующим образом:

F → min (7.9)

при следующих ограничениях:

. (7.10)

Для распределённой схемы мульти-агентной маршрутизации задача ставится для каждой пары отдельно. В данном случае оптимальным решением является распределение информационного потока, при котором его стоимость для каждой пары в отдельности – минимальна. Такое решение является локально оптимальным.

Введём понятие минимального потока между парой узлов d как функцию вида

, .

Тогда решением задачи будет вектор распределения потоков x, удовлетворяющий следующим соотношениям

, (7.11)

где A(x) = (A1(x), A2(x), …) – вектор минимальных потоков [19].

7.3.3. Модификация стоимости нагрузки на канал связи с ограниченной пропускной способностью

Для ТКС, в которых пропускная способность каналов связи ограничена, функция T l (p l) будет удовлетворять следующим ограничениям:

, (7.12)

где pmax – максимальная пропускная способность канала связи l.

В этом случае условие IV будет нарушено. Этого можно избежать, если ввести вспомогательную функцию T l(ε ) (p l) вида

(7.13)

где величина ε > 0 и сколь угодно мала.

Лемма 7.1. Для T l(ε ) (p l) вида (7.13) выполняются условия I-IV параграфа 7.2.2.

Доказательство. Очевидно, что условия I и II будут выполнены. Докажем, что T l(ε ) (p l) непрерывно дифференцируема на [0, pmax).

Рассмотрим функцию . Она непрерывно дифференцируема на всей области определения и строго монотонно возрастает, причём

. (7.14)

Рассмотрим T l(ε ) (p l) в точке {pmax-ε }. Учитывая (12), получаем:

(7.15)

Из (7.12) следует, что в точке {pmax} функция T l(ε ) (p l) стремится к ∞, т.е. T l(ε ) (p l) непрерывна на всей области определения. С учётом (7.12) и (7.13) получаем следующее выражение для производной вспомогательной функции:

(7.16)

Отсюда следует, что функция T l(ε ) (p l) непрерывно дифференцируема на (0, pmax)\{pmax -ε }. Рассмотрим пределы её производной слева и справа от точки {pmax-ε }.

Так как из этого следует, что

,

то функция T l(ε ) (p l) непрерывно дифференцируема на (0, pmax). Следовательно, условие IV выполняется для вспомогательной функции (7.13).

Для выполнения условия III достаточно доказать, что оно выполняется на промежутке (pmax-ε, pmax). На этом интервале функция T l(ε ) (p l) как произведение двух выпуклых и положительных функций будет выпуклой и строго монотонно возрастающей.

Таким образом, лемма 7.1 доказана.

Отсюда следует, что, рассматриваемые для данной модели ТКС методы мульти-агентной маршрутизации применимы к ТКС с ограниченной пропускной способностью каналов связи. При этом оценочные функции стоимостей маршрутов будут строиться с некоторой погрешностью.






© 2023 :: MyLektsii.ru :: Мои Лекции
Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.
Копирование текстов разрешено только с указанием индексируемой ссылки на источник.