4.6. Централизованная и распределённая маршрутизации в мульти-агентных ткс

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

, (4.6.1)

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

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

, (4.6.2)

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

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

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

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

T_l(p_l) –стоимость нагрузки ρ_l, приходящейся на ребро (канал связи) .

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

, где (4.6.3)

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

Определим основные условия и параметры задачи маршрутизации следующим образом:

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

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

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

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

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

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

ρ_l – нагрузка на ребро (канал связи) , определяемая по формуле

;

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

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

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

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

1. Средняя стоимость маршрута определяется как сумма стоимостей нагрузок на его рёбра (каналы связей), т.е.

;

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 – общая стоимость распределения информационных потоков. Тогда

. (4.6.4)

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

. (4.6.5)

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

F → min (4.6.6)

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

. (4.6.7)

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

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

, .

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

, (4.6.8)

где A(x) = (A₁(x), A₂(x), …) – вектор минимальных потоков.

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

, (4.6.9)

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

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

(4.6.10)

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

Лемма 4.6.1. Для T_l^(ε)(p_l) вида (4.6.10) выполняются условия I-IV.

Очевидно, что условия I и II будут выполнены. Докажем, что T_l^(ε)(p_l) непрерывно дифференцируема на [0,p_max).

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

. (4.6.11)

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

(4.6.12)

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

(4.6.13)

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

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

,

то функция T_l^(ε)(p_l) непрерывно дифференцируема на (0,p_max). Следовательно, условие IV выполняется для вспомогательной функции (4.6.10).

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

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

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