4.7. Нейросетевая маршрутизация в мульти-агентных ткс

Рассмотрим нейросетевую маршрутизацию в мульти-агентных ТКС. Как известно [14,16,28,30], нейронные сети представляют собой эффективную вычислительную модель, позволяющую распознавать образы или аппроксимировать функции любой сложности, основываясь на неполной информации, заключенной в обучающей базе данных (БД).

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

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

Для решения задач маршрутизации используются в основном два вида нейронных сетей: сети перцептронного типа и сети Хопфилда. Однако решения, вычисляемые сетями перцептронного типа, как правило, неустойчивы. Поэтому ниже рассматриваются нейронные сети Хопфилда (НСХ) и их модификация.

Построим нейронную сеть для мульти-агентной модели, предложенной в 4.6.

Рассмотрим оптимизационную задачу (4.6.6)-(4.6.7). Данная задача при выполнении условий I-IV имеет, по крайней мере, одно решение. При этом для всех решений значения вектора распределения нагрузок ρ будут одними и теми же.

Достаточным условием решения оптимизационной задачи (4.6.6)-(4.6.7) с линейными ограничениями при помощи НСХ, является строгое монотонное возрастание минимизируемой функции.

Рассмотрим систему (4.6.4). Так как для конкретного множества значением функции Φ_D является положительная константа, то её можно перенести в левую часть, не меняя условий задачи, т.е.

. (4.7.1)

Введём матрицу Δ вида

, (4.7.2)

где δ_ij – доля интенсивности информационного потока x_j, которая приходится на ребро (канал связи) i.

Так как ρ_l = ρ_l(x), то задачу (4.6.6)-(4.6.7) можно переформулировать следующим образом:

FΦ_D → min (4.7.3)

при ограничениях

. (4.7.4)

В качестве возможных решений задачи (4.7.3), (4.7.4) будем искать векторы (ρ, x). Без потери общности можно считать, что и .

Построим энергетическую функцию E = E(ρ, x) для НСХ, решающей оптимизационную задачу (4.7.3)-(4.7.4). Потребуем, чтобы функция E была квадратичной формой от (ρ, x).

Сначала рассмотрим функцию E₀:

, (4.7.5)

где α_ij - некоторые положительные константы, причем α₁₁ – достаточно малое число. Однако E₀ не является квадратичной формой, так как в первой сумме присутствуют нелинейные элементы T_l(ρ_l).

Заменим первую сумму в (4.7.5) на квадрат линейной комбинации ρ. Тогда получим следующую энергетическую функцию для НСХ:

(4.7.6)

где параметры и достаточно малы.

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

Замена (4.7.5) на (4.7.6) допустима, поскольку для двух строго возрастающих функций с одинаковыми областями определения (задаваемыми системой (4.7.4) экстремумы достигаются в одинаковых точках.

Таким образом, синтезирована модель НСХ, состоящая из |E|+|Π| нейронов, где Π - упорядоченное множество всех маршрутов для всех пар узлов, а E – множество рёбер графа, соответствующего ТКС. Эта модель НСХ ориентирована на централизованную схему мульти-агентной маршрутизации, представленной на рис. 4.2.2, а).

Теперь рассмотрим задачу локальной оптимизации (4.6.8) для распределённой схемы мульти-агентной маршрутизации, изображённой на рис. 4.2.2., б). При выполнении условий I-IV эта задача имеет, по крайней мере, одно решение.

Рассмотрим первое уравнение системы (4.6.8). В силу второго и четвертого неравенств системы получим, что для любого x справедливо неравенство вида

. (4.7.8)

Отсюда следует, что неотрицательная функция (T(x)-Γy)x принимает нулевые значения (с учетом остальных ограничений) в точках возможных решений неравенств (4.7.8). Это означает, что точки минимумов данной функции совпадают с решениями оптимизационной задачи (4.6.8). С учетом (4.7.8) и того, что

, (4.7.9)

переформулируем задачу (4.7.1) следующим образом:

(4.7.10)

Эту задачу можно свести к следующей оптимизационной задаче:

(4.7.11)

Заметим, что z_p=0, если

T_p(x) = (ΓA(x))_p.

Поэтому с учетом неравенств x_p≥0 и z_p>0 получим, что

T_p(x)>(ΓA(x))_p и x_p=0. (4.7.12)

Построим НСХ, решающую оптимизационную задачу (4.7.11). В качестве возможных решений будем искать векторы (x, z). Так же, как и в предыдущей задаче, будем полагать, что и .

Из первого равенства в системе ограничений следует, что

. (4.7.13)

Таким образом, энергетическая функция E для НСХ будет иметь следующий вид:

(4.7.14)

Модель НСХ с энергетической функцией (4.7.14) состоит из 2|Π| нейронов, где Π - упорядоченное множество всех маршрутов для всех пар узлов ТКС. Эта нейронная сеть ориентирована на решение задачи локальной оптимизации для распределенной схемы мульти-агентной маршрутизации.

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

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