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

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

), (7.2)

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

. (7.3)

Технология прокладки маршрута с помощью описанного алгоритма заключается в следующем: при передаче пакета данных узлу-получателю f узел-источник s₀ сначала пересылает его к соседнему узлу r=a₁, на котором значение функции минимально, затем этот узел a₁ пересылает пакет узлу r=a₂, на котором достигается минимум функции и т.д. до тех пор, пока пакет данных не придет в заданный узел-получатель 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, а. Однако она позволяет решать задачи маршрутизации в условиях неполноты и/или неопределённости имеющейся сетевой информации.

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

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

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

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

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

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

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

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

(7.4)

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

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

(7.5)

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

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

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

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

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

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

, где (7.6)

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

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

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

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

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

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

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

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

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

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

,

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

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

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

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

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)

где p_max – максимальная пропускная способность канала связи 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, p_max).

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

. (7.14)

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

(7.15)

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

(7.16)

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

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

,

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

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

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

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