Модели и методы решения задачи оптимальной маршрутизации данных в корпоративных сетях тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат физико-математических наук Зайнуллина, Эльмира Шаукатовна

  • Зайнуллина, Эльмира Шаукатовна
  • кандидат физико-математических науккандидат физико-математических наук
  • 2008, Казань
  • Специальность ВАК РФ05.13.18
  • Количество страниц 119
Зайнуллина, Эльмира Шаукатовна. Модели и методы решения задачи оптимальной маршрутизации данных в корпоративных сетях: дис. кандидат физико-математических наук: 05.13.18 - Математическое моделирование, численные методы и комплексы программ. Казань. 2008. 119 с.

Оглавление диссертации кандидат физико-математических наук Зайнуллина, Эльмира Шаукатовна

ВВЕДЕНИЕ.

ГЛАВА 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. Сравнение решений задачи транспортировки данных методом ветвей и границ и нейросетевым методом.

Выводы.

Рекомендованный список диссертаций по специальности «Математическое моделирование, численные методы и комплексы программ», 05.13.18 шифр ВАК

Введение диссертации (часть автореферата) на тему «Модели и методы решения задачи оптимальной маршрутизации данных в корпоративных сетях»

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

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

Информация' поь сети- (Интернет, 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 наименований.

Похожие диссертационные работы по специальности «Математическое моделирование, численные методы и комплексы программ», 05.13.18 шифр ВАК

Заключение диссертации по теме «Математическое моделирование, численные методы и комплексы программ», Зайнуллина, Эльмира Шаукатовна

Выводы

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

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

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

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

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

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

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

Список литературы диссертационного исследования кандидат физико-математических наук Зайнуллина, Эльмира Шаукатовна, 2008 год

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

Обратите внимание, представленные выше научные тексты размещены для ознакомления и получены посредством распознавания оригинальных текстов диссертаций (OCR). В связи с чем, в них могут содержаться ошибки, связанные с несовершенством алгоритмов распознавания. В PDF файлах диссертаций и авторефератов, которые мы доставляем, подобных ошибок нет.