автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Модели и методы решения задачи оптимальной маршрутизации данных в корпоративных сетях

На правах рукописи

ЗАЙНУЛЛИНА ЭЛЬМИРА ШАУКАТОВНА

МОДЕЛИ И МЕТОДЫ РЕШЕНИЯ ЗАДАЧИ ОПТИМАЛЬНОЙ МАРШРУТИЗАЦИИ ДАННЫХ В КОРПОРАТИВНЫХ СЕТЯХ

Специальность 05 13 18 - Математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

»ШИН»»!«»

003 1В454В

Казань 2008

Работа выполнена в Казанском государственном техническом университете им А Н Туполева

Научный руководитель доктор технических наук, профессор

Емалетдинова Лилия Юнеровна

Официальные доктор физико-математических наук, профессор

оппоненты Елизаров Александр Михайлович

доктор физико-математических наук, профессор Кирпичников Александр Петрович

Ведущая организация Марийский государственный технический

университет

Защита состоится оР&^е&я-^Я 2008 года в ^ часов на заседании диссертационного совета Д 212 079 01 в Казанском государственном техническом университете им АН Туполева по адресу 420111, г Казань, ул Карла Маркса, 10

С диссертацией можно ознакомиться в библиотеке Казанского государственного технического университета им А Н Туполева

Автореферат разослан Л Л ЛМ&аЛ,^^- 2008 г

Ученый секретарь диссертационного совета ,

доктор физ -мат наук, профессор П Г Данилаев

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность проблемы В современных условиях информатизация корпоративной деятельности является одним из важных направлений повышения эффективности организационного управления

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

Информация по сети (Интернет, Ethernet, локальные сети, корпоративные сети) передается в виде пакетов данных из одной вычислительной машины в другую с помощью специальных устройств -маршрутизаторов, которые представляют собой устройства со специальным программным обеспечением, сетевыми интерфейсами ввода/вывода В основе функционирования программного обеспечения маршрутизатора лежат различные алгоритмы маршрутизации Существует множество алгоритмов, которые различаются по скорости работы, оптимальности получаемых маршрутов, приспосабливаемости к изменяющимся условиям сети и т д

Алгоритмы маршрутизации определяют оптимальный маршрут из удаленного узла в центр на основе вычисляемых показателей (метрик) или их комбинаций Примерами метрик могут быть длина пути, время прохождения, число промежуточных узлов Ряд используемых в маршрутизаторах алгоритмов динамически переопределяют оптимальные направления в зависимости от занятости очередного узла маршрута Однако применительно к рассматриваемой задаче алгоритмы маршрутизации при построении оптимального маршрута из удаленного узла в центр не учитывают время передачи в центральный узел информации других удаленных узлов Поэтому актуальным вопросом является создание математической модели рассматриваемой задачи и ее решение

Одним из подходов к решению задачи является использование аппарата искусственных нейронных сетей Теория нейронных сетей является новым направлением математики и информатики и представляет интересную область для исследования Такие известные ученые, как Джон Д Хопфилд, Дэвид В Танк, Шианг-Сун Занг, Зонг-Бен Су, Чанг П Квонг, И И Меламед и другие, проводят теоретические и практические исследования по созданию нейронных сетей с различной динамикой для решения задач линейной, квадратичной, нелинейной, комбинаторной оптимизации Методы, основанные на использовании искусственных нейронных сетей, позволяют значительно повысить оперативность решения данного класса задач, обеспечивая достаточную точность результата Поэтому необходимо разработать модели и алгоритмы решения рассматриваемой задачи на основе теории нейронных сетей

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

1 проанализировать существующие алгоритмы маршрутизации данных в компьютерных сетях,

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

3 разработать методику и алгоритм решения задачи на основе построенной нейросетевой модели,

4 доказать сходимость построенной нейронной сети к устойчивым точкам,

5 исследовать влияние выбора начальных состояний нейросетевой модели и режимов функционирования нейронной сети Хопфилда на качество получаемых решений,

6 разработать методику и алгоритм вычисления коэффициентов штрафных слагаемых целевой функции нейросетевой модели,

7 доказать устойчивость допустимых состояний нейронной сети Методы исследования Для решения поставленных задач в работе

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

Научная новизна В диссертационной работе получены следующие новые научные результаты

1 разработана дискретная и нейросетевая модели задачи оптимальной

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

2 сформулировано и доказано условие сходимости нейросетевой модели к устойчивым точкам при несимметричной матрице весов,

3 сформулировано и доказано достаточное условие устойчивости допустимых состояний построенной нейронной сети,

4 разработана методика вычисления коэффициентов штрафных членов функции энергии сети

Достоверность результатов работы Основные положения диссертационной работы получены на основании достоверных знаний прикладной математики и использования строгого математического аппарата Полученные теоретические результаты подтверждены вычислительными экспериментами, актами использования в деятельности государственных организаций и внедрения в учебный процесс

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

Апробация работы Основные результаты работы докладывались и обсуждались на следующих международных, всероссийских конференциях и семинарах XI! Международная молодежная научная конференция «Туполевские чтения» (Казань, 2004), XVI Международная научно-техническая конференция «Математические методы и информационные технологии в экономике, социологии и образовании» (Пенза, 2005), VIII Международная научно-практическая конференция «Фундаментальные и прикладные проблемы приборостроения, информатики и экономики» (Москва, 2005), IV Общероссийская конференция с международным участием «Новейшие технологические решения и оборудование» (Москва, 2006), Всероссийская научная конференция студентов и аспирантов (Вологда, 2007), XV Международная молодежная научная конференция «Туполевские чтения» (Казань, 2007)

Публикации По теме диссертации опубликовано 8 научных работ, включая 2 статьи и б тезисов докладов

Структура и объем диссертации Диссертационная работа состоит из введения, четырех глав, заключения, библиографического списка и двух приложений Работа содержит 119 страниц машинописного текста, 51 рисунок и 23 таблицы Список литературы включает 88 наименований

СОДЕРЖАНИЕ РАБОТЫ

Во введении содержится обоснование актуальности проблемы, основные научные положения и результаты

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

Рассматривается корпоративная распределенная информационная система, в которой имеется узел, являющийся центром обработки информации, и удаленные узлы, данные из которых должны быть переданы в центральный узел для обработки

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

Предполагается, что передача информации осуществляется при следующих условиях

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

2 Топология сети, работоспособность каналов и объемы передаваемой информации в процессе решения задачи остаются неизменными

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

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

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

IP-адресов в физические осуществляется с помощью протокола разрешения адресов ARP (Address Resolution Protocol). Для этого просматривается специальная ARP-таблица узла отправителя. Особенностью этой таблицы является возможность отсутствия физического адреса. Если физический адрес в ARP-таблице найден, то пакет передается по этому адресу.

Вычислительная машина - источник

Пункт назначения (сетевой адрес) | Маршрутизатор 1 (физический адрес)

Таблица маршрутизации

ARP - таблица

Маршрутизатор 1

Таблица маршрутизации

ARP - таблица

Пункт назначения (сетевой адрес) I Маршрутизатор 2 (физический | адрес)

Маршрутизатор 2

Таблица маршрутизации

ARP - таблица

Таблица маршрутизации

ARP - таблица

пакет Пункт назначения (сетевой адрес)

| Маршрутизатор 3 (физический адрес) I

Маршрутизатор 3

Вычислительная машина - пункт назначения

Пункт назначения (сетевой адрес) Пункт назначения (физический адрес)

Таблица маршрутизации

ARP - таблица

Рис. 1. Процесс маршрутизации данных

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

1. В таблице маршрутизации сетевого устройства отправителя ищется 1Р-адрес машины - «пункта назначения». Если этот адрес найден, то в результате просмотра АРР-таблицы определяется физический адрес,

по которому посылается пакет, иначе осуществляется переход к п 2

2 Ищется 1Р-адрес сети, в которой находится машина - «пункт назначения» Если адрес найден, то с помощью АРР-таблицы определяется физический адрес, по которому отправляется пакет, иначе осуществляется переход к п 3

3 Определяется физический адрес, соответствующий 1Р-адресу установленному по умолчанию, по которому передается пакет

Если при реализации алгоритма физический адрес в А1ЧР-таблице отсутствует, то технология передачи пакета состоит из следующих дополнительных этапов

1 Всем сетевым устройствам широковещательно рассылается пакет с А1ЧР-запросом с целью определения физического адреса, которому принадлежит 1Р-адрес места назначения

2 Исходящий пакет ставится в очередь

3 Каждое сетевое устройство, получившее АР*Р-запрос, сравнивает свой 1Р-адрес с 1Р-адресом в АРР-запросе Если адреса совпали то по физическому адресу отправителя запроса посылается ответ, содержащий как физический адрес, так и 1Р-адрес текущего сетевого устройства

4 После получения ответа на свой АРР-запрос, сетевое устройство -отправитель формирует новую строку в своей АРР-таблице и по физическому адресу отправляет пакет, который ранее был поставлен в очередь

5 Если же не был получен ответ на АЯР-запрос, то протокол 1Р будет уничтожать пакеты, предназначенные этому адресату

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

В работе был осуществлен анализ алгоритмов маршрутизации, которые были классифицированы в соответствии с критериями, приведенными в таблице 1

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

равенство всех маршрутизаторов по отношению друг к другу При использовании алгоритмов иерархической организации маршрутизаторы разделяются по уровням Алгоритмы с поузловым вычислением маршрута предполагают в каждом узле вычисление очередного узла маршрута Алгоритмы с полным вычислением маршрута определяют весь маршрут полностью Внутридоменные алгоритмы маршрутизации действуют только в пределах доменов, междоменные - как в пределах доменов, так и между ними Алгоритм состояния канала определяет кратчайшие маршруты с помощью алгоритма Дейкстры В основе алгоритма маршрутизации по вектору расстояний лежит алгоритм Беллмана-Форда или Форда-Фалкерсона

Таблица 1 Типы алгоритмов маршрутизации

Критерий Типы алгоритмов

Способ заполнения таблиц маршрутизации Статические и динамические

Вид процесса передачи пакета Одномаршрутные и многомаршрутные

Вид архитектуры сети Одноуровневые или иерархические

Метод вычисления Алгоритмы с поузловым или полным вычислением маршрута

В соответствии с используемым протоколом Внутридоменные и междоменные

Вид алгоритма поиска пути Алгоритмы состояния канала или вектора расстояний

Анализ алгоритмов маршрутизации показал, что среди всего множества алгоритмов только алгоритмы Дейкстры, Беллмана-Форда, Форда-Фалкерсона строят оптимальные маршруты Однако эти алгоритмы не учитывают время ожидания освобождения канала в предпоследнем узле маршрута, связанного с центром Поэтому необходимо разработать модели и методы решения задачи транспортировки данных из удаленных узлов в центральный узел распределенной информационной системы

Во второй главе проведен анализ возможности использования классических моделей задач, связанных с нахождением оптимального маршрута, для решения рассматриваемой задачи, построена дискретная модель поставленной задачи и разработан алгоритм ее решения на основе метода «ветвей и границ», построена нейросетевая модель исходной задачи и разработан нейросетевой метод и алгоритм ее решения, доказана сходимость нейронной сети к устойчивому состоянию из любого начального состояния сети при несимметричной матрице синаптических весов

Анализ задач нахождения оптимальных маршрутов показал невозможность сведения исходной задачи к классическим задачам

определения маршрутов, таким как задача нахождения кратчайшего пути, задача коммивояжера, задача динамической транспортной сети, классическая транспортная задача

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

(/ = 1 ,п) - объем данных в удаленном / -м узле, и(; - скорость передачи

данных по каналу связи / -го и у -го узлов, если канал связи отсутствует, то

и,, = 0 Поскольку узлы в маршруте не повторяются, то (п +1) - максимальное узлов в маршруте Маршрут представляется в виде матрицы

у

число

X = (х/а)(л+1)х(п+1)' элементы которой принимают следующие значения

И, если узел I имеет порядковый номер а в маршруте, [О, если узел / не включается в маршрут

Пример топологии сети, маршрута и его кодировки приведен на рис 2 Для записи целевой функции в дискретной постановке вводятся фиктивные узлы, состояния которых описываются дополнительными переменными ху 0 = 0 и х1 „+2 =0 (у = 1,л + 1)

Номер узла 2

X - (Х1а )бх5 ~

Номеров маршруте

1 0 0 0 0

0 1 0 0 0

0 0 1 0 0

0 0 0 0 0

0 0 0 1 0

а)

б)

Рис 2 а) Один из возможных маршрутов передачи данных в случае задачи с 5 узлами, б) Кодировка этого маршрута состояниями 25 бинарных переменных

Целевая функция исходной задачи записывается в виде

п+1п+1л+1 у

Ф0-тЕ Е Е — Х1а(Х1,а--\ +Х1 о- + 1 2 ,=1 у=1«=11>?

)+ тах

п п+1

II"

л п п п+Ц/

• тт,

~хп+\а х>,а-1

(1)

Л + 1Л + 1П + 1 \/

где г 2 Е 2 --х1а(х]а-1 - время передачи объема данных V, из

разрывного узла г в центр без учета времени ожидания освобождения предпоследнего канала,

( П п+1 у 1 л п л+Ц/ 4

шах X I —1—Хп+Ла ^--Х! I — х1а{х]а^+х]а+^),0 - время

ожидания освобождения канала, соединяющего предпоследний и центральный узлы

Ограничения задачи формулируются следующим образом

хг1=1 (2)

л+1

X *п+1 а ~ 1 а =1

(3)

-I л+1л+1л+1

¿/=1;=1а=1 (4)

1*1

1 п+1 л+1 л+1 л+1л+1п+1

I (Х,а-1+*;,в+1) «<'.;)= О ...

2а=1/=1;=1 (О)

ГО, если и„ * О При <р(1,])=\

[1, если оч = О

\2

п л+1 Л + 1

Е IX« - 2>

а=1 /=1 /=1

ч1?!Л+1

,а+1

- О

(7)

Ограничение (2) требует, чтобы маршрут начинался с узла, для которого разорвался канал, соединяющий его с центром Ограничение (3) требует, чтобы маршрут заканчивался центральным узлом Ограничение (4) требует, чтобы в маршруте любые два узла не имели одинаковый порядковый номер Ограничение (5) необходимо для того, чтобы не допускать повторение узлов в маршруте Ограничение (6) требует соблюдение топологии сети при построении маршрута Ограничение (7) требует неразрывности маршрута

Для решения задачи (1)-(7) разработан алгоритм, основанный на методе «ветвей и границ», в соответствии с которым ветвление заключается в разбиении подмножества Хк на взаимно непересекающиеся подмножества путем выбора очередного канала связи в маршруте из узла г в центральный узел п+1 Нижняя граница вершины Хк дерева ветвлений вычисляется по

формуле /'™жн=ф<',<), где к - номер вершины дерева ветвлений, Хк -матричное представление маршрута, содержащего определенную последовательность узлов

Для решения задачи (1)-(7) с помощью нейросетевого подхода используется следующая интерпретация исходных данных и переменных Рассматривается нейронная сеть, состоящая из (л + 1)х(л + 1) бинарных нейронов, где первое (л + 1) - число удаленных узлов вместе с центральным узлом, а второе (л + 1) - максимальное число узлов в маршруте Переменные х1а е {0,1} (/ = 1, л +1, а = 1, л +1) определяют состояния нейронов

Решение задачи (1)-(7) в нейросетевой постановке базируется на решении задачи минимизации времени передачи объема Уг без учета времени ожидания в предпоследнем узле маршрута и оценке этого времени ожидания

Целевая функция, описывающая время передачи объема Уг из узла г с разрывной связью в центральный узел по маршруту без учета времени ожидания в предпоследнем узле маршрута, запишется как

+ху1а+1)=> тш (8)

Г1

—, если 3 канал связи между узлами / и у

где в0,7)=

[о, в противном случае Для решения задачи (8), (2)-(7) с помощью нейронной сети Хопфилда необходимо перейти от задачи условной оптимизации к задаче безусловной оптимизации, построив соответствующую функцию энергии сети Для этого к целевой функции (8) добавляются штрафные функции, каждая из которых интерпретируется как штраф за нарушение соответствующего ограничения исходной задачи, увеличивающий целевую функцию при отклонении от накладываемых ограничений Затем полученная функция энергии сети приводится к виду функции Ляпунова

¿/=1у=1 1=1 4 '

1*1

где а>ц - вес связи между / -ми ^ -м нейронами, - порог срабатывания / -

го нейрона, х,, х] - состояния / -го и } -го нейронов соответственно

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

процессе динамики сети состояния определенных нейронов фиксируются следующим образом хг1 = 1, хга = 0 {а = 2,п + 1), х(1 = 0 (/ * г, / = 1,л + 1) При этом ограничение (4) автоматически вытекает из ограничения неразрывности маршрута (7)

Для задачи (8), (3), (5)-(7) функция энергии представляется в виде следующего функционала

, N Ап "+1л+1л+1 . . ( п+1 \2

I I 1М/,У)хю(худ_1+хм+1)+Л1 1хп+и-1 +

^ (=1 у=1 а=1 Ча=1 )

П +1 /7+1 П+1 П+1П+1П+1

^ а=1 /?=1 (=1 ^ а=11=1 у=1

а*/3

+ А»1

«=1

(

п+1 п+1

/=1 /=1

/*п+1 /*г

(10)

Здесь Л0 - коэффициент, определяющий степень близости к минимальному значению функции ¿^(х) (8) при минимальных значениях Е^х) АЬА2,А3,А4 - коэффициенты, определяющие степень удовлетворения ограничений (3), (5)-(7)

Функция энергии сети (10) является целевой функцией нейросетевой модели задачи После выполнения преобразований функции (10) к виду (9) функция энергии сети имеет следующий вид

1 п+1п+1п+1 П+1 П+1П+1

Е1ОО = -гШ X <о',а ¡р Х1аХ]/} + X Т.»',аХю + /Ц (11)

I ,=1 у=1а=1 /?=1 /=1а=1

где

а>Ш1Р= ["А) ^г +<5а + 1^)-2А<5/п + 1^п+1 _

+ «Ув+г/»Ж'.у)-2А»(1 -X1 -я+1)

¿а/? (1 - 3а,П+\) + 4Л4 (1 ~ <5/,п+1 X1 - «V К + 1.Д (1 - п + 1 )" ,1, если / = /

<5„ = - символ Кронекера

1 [0, в противном случае

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

/

х,(* + 1)

fЪ^>цX^У&¡, 1=К

V 1 1

где - состояние / -го нейрона в момент времени ?, К - номер активного нейрона

В теории нейронных сетей доказана сходимость асинхронной сети к устойчивым состояниям для симметричной матрицы весов связей между нейронами с нулями на главной диагонали Анализ матрицы весов синаптических связей IV'= 1® 2 показал, что матрица является

несимметричной В работе сформулирована и доказана следующая теорема

Теорема 1 Функция энергии (11) асинхронной сети с несимметричной матрицей весов, закон динамики которой описывается следующим выражением

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

Метод решения исходной задачи в терминах теории нейронных сетей является приближенным методом, не гарантирующим получение оптимального решения Однако в случае сложной топологии телекоммуникационной сети метод «ветвей и границ» не применим Задачи подбора штрафных коэффициентов энергии сети и начальных состояний нейронов, позволяющих получать решения близкие к оптимальным исследуются в следующих главах

В третьей главе исследуется влияние коэффициентов штрафных функций на сходимость сети Хопфилда, предлагается метод вычисления коэффициентов штрафных функций и доказывается устойчивость допустимых состояний нейронной сети

Состояние сети называется допустимым, если оно удовлетворяет всем ограничениям модели Состояние сети называется недопустимым, если оно не удовлетворяет хотя бы одному ограничению модели Состояние сети называется оптимальным, если оно соответствует оптимальному решению исходной модели задачи

Анализ влияния коэффициентов штрафных функций на сходимость сети Хопфилда показал, что неправильно подобранные коэффициенты могут привести к тому, что некоторые допустимые состояния сети не будут являться устойчивыми точками

Теорема 2 Пусть х - допустимое состояние сети, а X - множество состояний сети, отличных от состояния х состоянием одного нейрона Тогда допустимое состояние х является устойчивой точкой асинхронной сети, если выполняется условие

где с?1(х),д4(х) - штрафные функции, соответствующие ограничениям (3), (7)

Идея метода вычисления коэффициентов штрафных функций заключается в вычислении коэффициентов таким образом, чтобы влияние каждой штрафной функции, соответствующей одному из ограничений задачи, на энергию сети было соизмеримым с вкладом остальных штрафных функций и целевой функции Кроме того, значения коэффициентов штрафных членов Д (/ = 1,4) должны выбираться таким образом, чтобы скорость убывания всех штрафов была соизмерима Поэтому, чем быстрее значения штрафных функций стремятся к нулю при приближении к допустимому решению, тем меньше соответствующий коэффициент

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

(5)-(7), С - константа, выбирается из условия соизмеримости штрафных функций со значениями целевой функции В работе доказано, что константа

2У,

С должна удовлетворять следующему условию С > —;—!—

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

В четвертой главе проведено исследование законов, описывающих динамику нейронной сети Хопфилда, а также влияния начальных состояний сети на сходимость сети Хопфилда, сравнение решений задачи методом «ветвей и границ» и нейросетевым методом на примере ряда типовых задач с точки зрения топологий телекоммуникационных сетей

Сеть Хопфилда с дискретным временем и дискретными состояниями

V*е х ф)-1(х)< Д1(д1(х)-д1(х))+Л4(д4(х)-д4(х))

X

штрафные функции, соответствующие ограничениям (3),

Аа тш и,

может функционировать в двух режимах синхронном и асинхронном

Синхронная динамика подразумевает, что в каждый момент времени вычисляются новые состояния всех нейронов Доказано в работах Майкла А Кохена, Стефена Гроссберга, И И Меламеда, что сеть с симметричной матрицей весов и нулями на главной диагонали, функционирующая в соответствии с синхронной динамикой, сходится к устойчивому состоянию, т е x,(t)= x,(f + 1), (/ = 1 ,п), или циклу длины 2, т е х,(í) = х,(í + 2), (/ = %п)

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

1 Последовательный перебор нейронов, те на каждой итерации выбирается один нейрон с номером из следующей последовательности К = 1,2, ,л,1,2,

2 Градиентное правило Если /0 = {/1 f(h, (f)) ф х, (t)} - множество нейронов, способных изменить свое состояние в момент времени t Тогда активный нейрон выбирается из условия К \hk\ = max|ft,¡}, где

leí о

i

3 Вероятностно-градиентное правило Вероятность выбора активного нейрона определяется по формуле р(К = ')= -^тгт. ' е 'о

11 'I

<е'о

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

Так как функция энергии сети является многоэкстремальной, то для получения наилучшего решения сеть необходимо запускать многократно из различных начальных состояний, а затем из полученных решений выбирать наилучшее В работе предлагается выбирать начальные состояния сети следующим образом хг1 = 1, xra =o(a = 2,n + l), х(1 = 0 (/ * г, / = 1,n + l), генерация остальных состояний осуществляется с помощью датчика случайных чисел Так же рассматривается влияние соотношения числа единиц и нулей в начальном состоянии на получение оптимальных решений Численные эксперименты показали, что наибольшее число оптимальных решений получается при преобладании либо нулей, либо единиц в начальном состоянии

Проведен сравнительный анализ метода «ветвей и границ» и

нейросетевого метода Выявлено, что с увеличением размерности задачи сеть Холфилда находит оптимальные или близкие к оптимальному решения значительно быстрее

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

1 Разработаны дискретная и нейросетевая математические модели оптимальной маршрутизации данных в условиях нарушения одного из каналов связи

2 Получены и обоснованы условие сходимости асинхронной нейронной сети к устойчивым состояниям при несимметричной весовой матрице и достаточное условие устойчивости допустимых состояний нейронной сети

3 Предложены методика вычисления коэффициентов штрафных членов функции энергии нейронной сети и рекомендации по выбору начальных состояний нейронов

4 Показана целесообразность использования нейросетевого подхода в случае большой размерности задачи и эффективность асинхронного закона функционирования нейронной сети на основе вычислительных экспериментов

Основное содержание диссертации изложено в следующих публикациях

1 Зайнуллина Э Ш Математическая модель задачи нахождения маршрута транспортировки данных из удаленных узлов в центральный узел распределенной информационной системы // Тез докл Междунар науч конф «XII Туполевские чтения», Т 111, Казань, 2004 С 16-18

2 Зайнуллина Э Ш, Каинов А С Особенности нейросетевого моделирования задачи комбинаторной оптимизации в распределенной среде II Сб ст XVI Междунар науч -техн конф «Математические методы и информационные технологии в экономике, социологии и образовании сборник статей», Пенза, 2005 С 451-454

3 Емалетдинова Л Ю , Зайнуллина Э Ш Модель оптимизации маршрута транспортировки данных из удаленных узлов в центральный узел распределенной системы // Науч тр VIII Междунар науч -практ конф «Фундаментальные и прикладные проблемы приборостроения, информатики и экономики», Московск roc академ приборостроен и информат, Москва, 2005 С 66-70

4 Вдовичев H M , Зайнуллина Э Ш Задачи и методы системы поддержки принятия управленческих решений в сфере социальной защиты региона // IV общерос конф с междунар участ «Новейшие технологические

решения и оборудование», Рос Академ Естествознан, Успехи современного естествознания, №6, 2006 С 23-24

5 Емалетдинова J1 Ю , Зайнуллина Э Ш Модель оптимизации маршрута транспортировки данных в распределенной системе для случая разрыва каналов связи // Вестник Казанского государственного технического университета им АН Туполева, №2(46), 2007 С 98-102

6 Зайнуллина Э Ш , Кайнов А С Методика подбора коэффициентов при решении оптимизационной задачи с помощью нейронной сети Хопфилда // Матер всерос науч конф студ и асп «Молодые исследователи - регионам», Т I, Вологда, 2007 С 103-104

7 Зайнуллина Э Ш, Кайнов А С Выбор активного нейрона при асинхронном функционировании сети Хопфилда // Тез докл Междунар науч конф «XV Туполевские чтения», Т III, Казань, 2007 С 18-20

8 Зайнуллина Э Ш Сравнение динамик функционирования сети Хопфилда с дискретным временем и дискретными состояниями // Тез докл Междунар науч конф «XV Туполевские чтения», Т III, Казань, 2007 С 21-23

Формат 60x84 1/16 Бумага офсетная Печать офсетная Печл 1,0 Услпечл 0,93 Услкр-отт 0,93 Уч-издл 1,0 Тираж 100 Заказ Л 2

Типография Издательства Казанского государственного технического университета им А Н Туполева 420111, Казань, К Маркса, 10

ВВЕДЕНИЕ.

ГЛАВА 1. ЗАДАЧА МАРШРУТИЗАЦИИ ДАННЫХ ИЗ УДАЛЕННЫХ УЗЛОВ В ЦЕНТРАЛЬНЫЙ УЗЕЛ

ИНФОРМАЦИОННОЙ СИСТЕМЫ.

1.1. Постановка задачи.

1.2. Анализ технологии маршрутизации данных.

1.3. Анализ алгоритмов маршрутизации данных.

Выводы.

ГЛАВА 2. МАТЕМАТИЧЕСКИЕ МОДЕЛИ И МЕТОДЫ

ОПТИМИЗАЦИИ МАРШРУТА ТРАНСПОРТИРОВКИ ДАННЫХ.

2.1. Анализ задач, связанных с нахождением оптимального маршрута.

2.2. Математические модели задачи транспортировки данных. 2.2.1. Дискретная модель задачи.

2.2.2. Нейросетевая модель задачи.

2.2.2.1. Общий вид нейросетевой модели Хопфилда.

2.2.2.2. Нейросетевая модель Хопфилда для исходной задачи.

2.2.2.3. Нейросетевой метод и алгоритм решения.

Выводы.

ГЛАВА 3. МЕТОД' УЛУЧШЕНИЯ СХОДИМОСТИ НЕЙРОСЕТИ К

ДОПУСТИМЫМ СОСТОЯНИЯМ.

3.1. Экспериментальный анализ влияния коэффициентов штрафных членов функции энергии на сходимость нейронной сети.

3.2. Достаточное условие устойчивости допустимых состояний.

3.3. Метод и алгоритм вычисления коэффициентов штрафных функций для задачи транспортировки данных.

3.4. Примеры решения задачи.

Выводы.

ГЛАВА 4. ЭКСПЕРИМЕНТАЛЬНЫЙ АНАЛИЗ НЕЙРОСЕТЕВОГО

МЕТОДА.

4.1. Исследование законов, описывающих динамику сети.

4.1.1. Модели динамики функционирования сети Хопфилда.

4.1.2. Сравнение функционирования сети с синхронной и асинхронной динамикой.

4.2. Исследование влияния начальных состояний сети на решение задачи.

4.3. Сравнение решений задачи транспортировки данных методом ветвей и границ и нейросетевым методом.

Выводы.

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

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

Информация' поь сети- (Интернет, Ethernet, локальные- сети, корпоративные сети) передается в виде пакетов данных из одной вычислительной машины в другую с помощью специальных устройств -маршрутизаторов, которые представляют собой устройства со специальным программным обеспечением, сетевыми интерфейсами ввода/вывода. В основе функционирования программного обеспечения маршрутизатора лежат различные алгоритмы маршрутизации. Существует множество алгоритмов, которые различаются по скорости работы, оптимальности получаемых маршрутов, приспосабливаемости к изменяющимся условиям сети и т.д.

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

Одним из подходов к решению задачи является использование аппарата искусственных нейронных сетей. Теория нейронных сетей является новым направлением математики и информатики и представляет интересную область для исследования. Такие известные ученые, как Джон Д. Хопфилд, Дэвид В. Танк, Шианг-Сун Занг, Вонг-Бен Су, Чанг П. Квонг, И. И. Меламед и другие, проводят теоретические и практические исследования по созданию нейронных сетей с различной динамикой для решения задач линейной, квадратичной, нелинейной, комбинаторной оптимизации [37, 79, 88]. Методы, основанные на использовании искусственных нейронных сетей, позволяют значительно повысить оперативность решения данного класса задач, обеспечивая'достаточную точность результата. Поэтому необходимо разработать модели и алгоритмы решения рассматриваемой задачи на основе теории нейронных сетей.

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

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

1. Проанализировать существующие алгоритмы маршрутизации данных в компьютерных сетях.

2. Построить дискретную и нейросетевую модель задачи транспортировки данных.

3. Разработать нейросетевую методику и алгоритм решения исходной задачи на основе построенной модели.

4. Доказать сходимость построенной нейронной сети к устойчивым точкам при несимметричной матрице весов синаптических связей.

5. Исследовать влияние выбора начальных состояний нейросетевой модели и режимов функционирования нейронной сети Хопфилда на качество получаемых решений.

6. Разработать методику и алгоритм вычисления коэффициентов штрафных слагаемых целевой функции нейросетевой модели.

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

Научная новизна. В диссертационной работе получены следующие новые научные результаты:

1. Разработана дискретная; и нейросетевая модели задачи' транспортировки данных из удаленного узла1 в центральный узел распределенной информационной системы в условиях разрыва связывающих каналов.

2. Сформулировано и доказано условие сходимости нейросетевой модели к устойчивым точкам при несимметричной матрице весов.

3. Сформулировано и доказано достаточное условие устойчивости допустимых состояний построенной нейронной сети.

4. Разработана методика вычисления коэффициентов штрафных членов функции энергии сети.

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

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

Апробация работы. Основные результаты работы докладывались и обсуждались на следующих международных, всероссийских конференциях и семинарах: XII Международная молодежная научная конференция «Туполевские чтения» (Казань, 2004) [89], XVI Международная научно-техническая конференция: «Математические методы и информационные технологии в экономике, социологии и образовании» (Пенза, 2005) [90], VIII Международная научно-практическая конференция «Фундаментальные и прикладные проблемы приборостроения, информатики и экономики» (Москва, 2005) [91], IV Общероссийская конференция с международным участием «Новейшие технологические решения и оборудование» (Москва, 2006) [92], Всероссийская научная конференция студентов и аспирантов, (Вологда, 2007) [94]; XV Международная молодежная научная конференция «Туполевские чтения» (Казань, 2007) [95, 96].

Публикации. По теме диссертации опубликовано 8 научных работ, включая 2 статьи и 6 тезисов докладов.

Структура и объем диссертации. Диссертационная работа состоит из введения, четырех глав, заключения, библиографического списка и двух приложений. Работа содержит 119 страниц машинописного текста, 51 рисунок и 23 таблицы. Список литературы включает 88 наименований.

Выводы

1. На сходимость сети Хопфилда помимо коэффициентов штрафных функций влияют такие факторы, как выбор динамики сети и выбор начальных состояний.

2. Поскольку при симметричной весовой матрице синхронная сеть в большинстве случаев сходится к устойчивым циклам длины 2, то предпочтительнее использовать асинхронную сеть, которая сходится только к устойчивым состояниям.

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

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

5. При небольшом числе каналов связи для решения задачи транспортировки данных из удаленного узла в центральный узел целесообразно использовать метод «ветвей и границ», поскольку он позволяет находить оптимальное решение достаточно быстро. Однако с увеличением числа каналов- связи между узлами телекоммуникационной сети растет время решения задачи, что делает невозможным использование метода «ветвей и границ». Поэтому в этих условиях предпочтение отдается нейросетевому методу.

ЗАКЛЮЧЕНИЕ

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

2. Разработаны математические модели поставленной задачи в терминах теории дискретной оптимизации и теории нейронных сетей.

3. Доказано условие сходимости асинхронной нейронной сети Хопфилда к устойчивым состояниям при несимметричной весовой матрице связей между нейронами.

4. На основе численного эксперимента по использованию различных законов динамики нейронной сети Хопфилда показана эффективность асинхронного закона функционирования нейронной сети.

5. Предложена методика вычисления коэффициентов штрафных членов функции энергии сети.

6. Доказано достаточное условие устойчивости допустимых состояний нейронной сети.

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

8. Сравнительный анализ метода «ветвей и границ» и нейросетевого метода показал целесообразность использования нейросетевого метода в случае большой размерности задачи.

1. Беллман Р. Динамическое программирование. — М.: ИЛ, 1960. — 440 с.

2. Белов В.В. и др: Теория графов. Учеб. пособие для втузов. М., «Высш. школа», 1976.

3. Бертсекас Д., Галлагер Р. Сети передачи данных: Пер. с англ. Mi: Мир, 1989. - 544 е., ил.

4. Веденов А.А., Ужов А.А., Левченко Е.Б. Архитектурные модели и функции нейронных ансамблей // Итоги науки и техники, сер. «Физические и математические модели нейронных сетей.» Т. 1. Mi: ВИНИТИ, 1990. С. 44-92.

5. Вишневский В.М. Теоретические основы проектирования компьютерных сетей. Москва: Техносфера, 2003; — 512 с.

6. Владимир Плешаков. CISCO Internetworking Technology Overview. Сервер MapK-HTT, http://nets.icf.bo£h.ru/l/index.htm

7. Волков H.K., Загоруйко Е.А. Исследование операций: учеб. для вузов. — 3-е изд., стереотип. / Под ред. B.C. Зарубина, А.П. Крищенко. М.: Изд-во МГТУ им. Н.Э. Баумана, 2004. - 440 с. (сер. математика в техническом университете; вып. XX).

8. Гилл Ф., Мюррей У., Райт М. Практическая оптимизация: Пер. с англ. -Mi: Мир, 1985. 509 е., ил.

9. Графы и их применение. Комбинаторные алгоритмы для программистов: учебное пособие / Н.И. Костюкова. — М.: Интернет университет информационных технологий; БИНОМ. Лаборатория знаний, 2007. 311 е.: ил., табл. - (серия «Основы информационных технологий»).

10. Давыдов Э.Г. Исследование операций: Учеб. пособие для студентов15