Авторефераты по всем темам >>
Авторефераты по техническим специальностям
На правах рукописи
УДК 004.7(43) Шаваша
Алаа МЕТОДИКА ДИНАМИЧЕСКОЙ МАРШРУТИЗАЦИИ В БЕСПРОВОДНЫХ КОМПЬЮТЕРНЫХ СЕТЯХ НА ОСНОВЕ АРХИТЕКТУРНО-ЦЕЛЕВОГО ПОДХОДА
Специальность 05.13.15 - л Вычислительные машины, комплексы и компьютерные сети
АВТОРЕФЕРАТ
диссертации на соискание ученой степени кандидата технических наук
Москва - 2012
Работа выполнена на кафедре Автоматизированных систем обработки информации и управления Института компьютерных технологий Федерального государственного бюджетного образовательного учреждения Московский государственный университет экономики, статистики и информатики (МЭСИ).
Научный консультант: Заслуженный деятель науки и техники РФ доктор технических наук, профессор Пятибратов Александр Петрович кандидат технических наук, доцент Микрюков Андрей Александрович Научный консультант: доктор технических наук, доцент Оцоков Шамиль Алиевич
Официальные оппоненты: доктор технических наук, профессор Петров Андрей Борисович кандидат технических наук, доцент Трембач Василий Михайлович
Ведущая организация: Федеральное государственное унитарное предприятие научно-исследовательский институт Восход.
Защита состоится 29 мая 2012г. в 14:00 часов на заседании диссертационного совета Д212.131.05 при МГТУ МИРЭА по адресу:
г. Москва, пр. Вернадского, д. 78, в ауд. №412.
С диссертацией можно ознакомиться в библиотеке МГУ МИРЭА.
Отзывы на автореферат в двух экземплярах, заверенные печатью, просим направлять по адресу: 119454, г. Москва, пр. Вернадского, д. 78.
Автореферат разослан 26 апреля 2012г.
Ученый секретарь Диссертационного совета Д212.131.Кандидат технических наук, доцент Е.Г. Андрианова
Общая характеристика работы
Актуальность темы. В настоящее время большое распространение получил такой класс беспроводных сетевых технологий, как беспроводные самоорганизующиеся ad hoc-сети. Такие сети предоставляют ряд принципиально новых возможностей, таких как автономность составляющих элементов, отсутствие необходимости централизованного управления и др. Каждый узел ad hoc- сети может выполнять функции маршрутизатора и принимать участие в ретрансляции пакетов данных. ad hoc-сети имеют свои специализированные протоколы маршрутизации.
В связи с возможностью самоорганизации ad hoc- сетей они активно используются для построения распределительных информационно- вычислительных сетей. Недостатком таких сетей является ограниченная полоса пропускания и зона радиовидимости сети. Существует ряд специализированных протоколов в ad hoc- сетях, совершенствованием которых в настоящее время занимается ряд научных школ академических институтов, предприятий и вузов.
Недостатком проведенных на сегодняшний день исследований является отсутствие математических моделей и методов оценки производительности ad hoc- сетей в зависимости от загруженности сети, мобильности узлов сети, решаемых на узлах сетевых задач, числа узлов и других параметров. Параметры ad hoc- сети изменяются в процессе ее функционирования, что приводит к снижению производительности сети. Для поддержания производительности сети на заданном уровне требуется динамическое изменение активного на данный момент времени протокола на другой с учётом изменения параметров сети.
Таким образом, недостаточная исследованность указанных вопросов приводит к снижению показателей эффективности функционирования ad hoc- сетей. Кроме того, принятая в настоящее время классификация протоколов не всегда позволяет оценить целесообразность применения конкретных решений для того или иного состояния сети, которое характеризуется ее параметрами.
Требуется разработка методического аппарата, позволяющего на основе анализа состояния сети, оценки ее параметров, решать задачу динамического выбора предпочтительного протокола маршрутизации.
Цель диссертационной работы состоит в совершенствовании функционирования ad hoc - сетей за счет динамического выбора протокола маршрутизации в беспроводной сети с учётом следующих параметров:
мобильности узлов, числа узлов сети и классов сетевых задач, загруженных в узлах сети.
В соответствии с указанной целью в работе поставлены и решены следующие основные взаимосвязанные задачи:
1. Анализ алгоритмов и протоколов маршрутизации в беспроводных компьютерных сетях, особенностей маршрутизации, характеристик и параметров беспроводных сетей.
2. Разработка концептуальных положений архитектурно - целевого подхода к решению задачи адаптивной маршрутизации в компьютерных беспроводных сетях.
3. Разработка методики динамической адаптивной маршрутизации в беспроводных сетях на основе выбора предпочтительного протокола маршрутизации.
4. Экспериментальные оценки эффективности разработанных предложений.
Объектом исследования являются сетевые протоколы и службы передачи данных в беспроводных компьютерных сетях.
Предметом исследования является совокупность теоретических, методических и практических положений, моделей и алгоритмов маршрутизации в беспроводных компьютерных сетях.
Методы исследования. При выполнении диссертационной работы использовались теоретические положения: теории систем, теории алгоритмов, теории оптимизации, теории интеллектуальных систем и сетей.
Основные положения, выносимые на защиту - концептуальные положения по решению задачи моделирования и анализа процессов функционирования беспроводных компьютерных сетей и повышения их эффективности на основе их самоорганизации, определяющие с позиции системного подхода общие принципы формализации процессов управления сетью, выполнения пользовательских требований, принятия маршрутизационных решений, поддержания характеристик сети на уровне заданных требований, а также обоснование и построение критериев эффективности на основе моделей их архитектур. Выбор наилучшего маршрутизационного решения осуществляется в корпоративной среде взаимодействия с учетом совокупности сетевых факторов взаимодействия, включающих параметры качества функционирования беспроводной компьютерной сети;
- обобщенный алгоритм обоснования целесообразных параметров маршрутизационных решений, отражающий сложную итерационную процедуру их выбора на основе заданных пользователем оценочных общесистемных показателей и представления сетевой среды реализации пользовательских приложений;
- математическая модель выбора и обоснования маршрутизационного решения, представляющая собой двухэтапную процедуру, алгоритмы и методика динамической маршрутизации на основе применения нейросетевых технологий выбора наиболее предпочтительного протокола маршрутизации. В качестве исходных данных используются: структура сети, типы узлов, надежность доставки пакетов, мобильность пользователей, задержка и флюктуация задержек, пропускная способность чувствительность к профилю трафика, количество потерянных пакетов, время доставки и другие параметры;
- методика выбора предпочтительного протокола маршрутизации в беспроводной компьтерной ad hoc- сети в зависимости от ее состояния, архитектурной модели и целевых установок. На основе разработанной методики по заданным пользовательским требованиям, целевым факторам, параметрам управления сетью, информационно-технической структуре сети осуществляется выбор маршрутизационного решения, обеспечивающего максимальное значение показателя эффективности функционирования сети - количества обслуживаемых запросов за единицу времени. Методика включает два этапа. На первом из них обосновывается решение о выборе предпочтительного протокола маршрутизации, а на втором - решение о целесообразности перехода на выбранный протокол. В качестве инструментального средства использована интеллектуальная нейросетевая технология, позволяющая в реальном масштабе времени принимать эффективные маршрутизационные решения.
Научная новизна В диссертации поставлена и решена актуальная научно-техническая задача совершенствования функционирования ad hoc - cетей на основе динамического выбора метода маршрутизации.
Автором лично получены следующие новые научные результаты:
1. Разработаны концептуальные основы моделирования и анализа процессов функционирования беспроводных компьютерных сетей и повышения их эффективности на основе их самоорганизации, отличающиеся предложенными архитектурно-целевыми подходами к формализации методов маршрутизации беспроводных сетей, целевых установок и характеристик беспроводной коммуникационной среды. Предложенные концептуальные основы определяют с позиции системного подхода общие принципы формализации процессов управления сетью, выполнения пользовательских требований, принятия маршрутизационных решений, поддержания характеристик сети на уровне заданных требований, а также обоснование и построение критериев эффективности на основе моделей их архитектур.
2. Разработана математическая модель динамического управления беспроводной компьютерной сетью, позволяющая обосновать перечень параметров сетевых факторов взаимодействия, перечень целесообразных параметров маршрутизационных решений, требования к ним, отличающаяся возможностью формализации решения задачи обоснованного выбора предпочтительного протокола маршрутизации на основе архитектурно - целевого подхода с учетом пользовательских задач. Разработанная модель является новой и позволяет учитывать взаимосвязь и влияние друг на друга:
информационной, технической и логической структур беспроводной компьютерной сети; методов маршрутизации и основных пользовательских требований, предъявляемых к беспроводной сети; маршрутизационных решений и базовых параметров функционирования беспроводной сети.
3. Разработана методика динамического выбора протокола маршрутизации беспроводной сети в зависимости от ее состояния, архитектурной модели и целевых установок с использованием интеллектуальных технологий, отличающаяся возможностью по заданным пользовательским требованиям, целевым факторам, параметрам управления сетью, информационно- технической структуре сети обеспечить получение максимального значения показателя эффективности функционирования сети - количество обслуживаемых запросов за единицу времени. Методика состоит из двух этапов, на первом из которых обосновывается решение о выборе предпочтительного протокола маршрутизации, а на втором - решение о целесообразности перехода на выбранный протокол, и отличающаяся возможностью принятия оптимального решения по переходу на предпочтительный протокол с учетом функциональных характеристик сети (текущего состояния в узлах сети, временных затрат на переход на новый протокол с учетом пороговых значений). В качестве инструментального средства использована интеллектуальная нейросетевая технология, обеспечивающая в реальном масштабе времени принятие эффективных маршрутизационных решений.
4. Обоснована эффективность разработанной методики динамического выбора протокола маршрутизации беспроводной сети. Результаты вычислительного эксперимента подтвердили работоспособность разработанной методики, на основе которой выработаны научно обоснованные рекомендации по совершенствованию функционирования беспроводных сетей.
Практическая значимость результатов исследования заключается в том, что полученные результаты могут быть использованы для повышения качества функционирования существующих и проектируемых беспроводных компьютерных сетей путем адаптации сетевых протоколов к инициированным приложениям и задачам за счет выбора наиболее предпочтительного протокола маршрутизации беспроводной сети в зависимости от пользовательских требований, мобильности узлов и других параметров сети.
Достоверность основных результатов подтверждается корректным использованием математического аппарата, соответствием основных разработанных теоретических положений результатам полученных экспериментальных данных, сходимостью результатов моделирования с имеющимися экспериментальными данными, ясной физической интерпретацией полученных результатов.
Апробация работы Основные положения диссертации и научные выводы прошли апробацию в виде публикаций в печати и докладов на научных конференциях и семинарах: в сборниках трудов научно-технологического центра развития учебного процесса (НТЦ РУП) Московского государственного университета экономики, статистики и информатики (МЭСИ), по мере получения научных результатов они докладывались на семинарах НТЦ РУП и постоянно-действующих Научнотехнических семинарах Института компьютерных технологий МЭСИ.
Материалы опубликованы в 4 печатных работах объемом 2,5 п.л, одна статья опубликована в рецензируемом журнале, рекомендованном ВАК Минобрнауки РФ.
Структура и объем работы: Диссертационная работа состоит из введения, четырех глав, заключения и библиографического списка литературы из 56 наименования. Диссертация содержит 140 стр. машинописного текста, рисунка и 5 таблицы.
Оглавление диссертации ПЕРЕЧЕНЬ ИСПОЛЬЗУЕМЫХ СОКРАЩЕНИЙ ВВЕДЕНИЕ.
ГЛАВА 1. АНАЛИЗ МЕТОДОВ МАРШРУТИЗАЦИИ В КОРПОРАТИВНЫХ БЕСПРОВОДНЫХ КОМПЬЮТЕРНЫХ СЕТЯХ.
1.1. Особенности организации информационного обмена, топологии и существующих протоколов маршрутизации в корпоративных беспроводных компьютерных сетях.
1.2. Анализ задач, решаемых при синтезе топологической структуры беспроводных компьютерных сетей.
1.3. Анализ алгоритмов маршрутизации в беспроводных компьютерных сетях и их классификация.
1.4. Анализ топологии, характеристик и параметров функционирования беспроводных компьютерных сетей.
1.5. Цели и задачи диссертационного исследования.
1.6. Выводы.
ГЛАВА 2. РАЗРАБОТКА АРХИТЕКТУРНО-ЦЕЛЕВОГО ПОДХОДА К ОБОСНОВАНИЮ РЕШЕНИЯ ЗАДАЧИ ДИНАМИЧЕСКОЙ МАРШРУТИЗАЦИИ В БЕСПРОВОДНОЙ КОМПЬЮТЕРНОЙ СЕТИ.
2.1. Концептуальная модель архитектурно-целевого обоснования требований к параметрам беспроводной компьютерной сети.
2.2. Формальное описание беспроводной компьютерной сети на основе архитектурно-целевого подхода.
2.3. Формализация решения поставленной задачи исследования.
2.4. Выводы.
ГЛАВА 3. РАЗРАБОТКА МОДЕЛИ, АЛГОРИТМОВ И МЕТОДИКИ ДИНАМИЧЕСКОЙ МАРШРУТИЗАЦИИ В БЕСПРОВОДНОЙ КОМПЬЮТЕРНОЙ СЕТИ.
3.1.Алгоритм обоснования целесообразных параметров маршрутизационных решений.
3.2. Задача представления сетевой среды реализации пользовательских приложений.
3.3. Разработка модели и методики представления и динамического выбора рациональных маршрутизационных решений на основе математического аппарата искусственных нейронных сетей.
3.4. Выводы.
ГЛАВА 4. ЭКСПЕРИМЕНТАЛЬНАЯ ОЦЕНКА РАЗРАБОТАННОЙ МЕТОДИКИ ДИНАМИЧЕСКОЙ МАРШРУТИЗАЦИИ В БЕСПРОВОДНОЙ КОМПЬЮТЕРНОЙ СЕТИ.
4.1. Экспериментальная оценка эффективности протоколов маршрутизации AODV, DSR, DSDV, применяемых а ad hoc - сетях.
4.2. Экспериментальная оценка эффективности решения задача выбора предпочтительного протокола маршрутизации.
4.3. Реализация разработанной методики динамического выбора маршрутизационных решений и разработка компьютерной программы.
4.3. Выводы.
ЗАКЛЮЧЕНИЕ.
СПИСОК ЛИТЕРАТУРЫ.
ПРИЛОЖЕНИЕ 1. Листинг программы.
ПРИЛОЖЕНИЕ 2. Акты о внедрении.
ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ
Во введении обоснована актуальность темы, объект и предмет исследования, сформулирована цель работы и научная проблема исследования, направления ее решения, раскрываются методы исследования, научная новизна и практическая ценность диссертации, реализация и внедрение результатов работы, основные положения, выносимые на защиту.
В первой главе Анализ методов маршрутизации в корпоративных беспроводных компьютерных сетях проведен анализ особенностей технологии беспроводных сетей, методов и протоколов маршрутизации и их самоорганизации.
Беспроводные самоорганизующиеся сети обладают следующими особенностями: реализация топологии сети на основе принципа взаимодействия "каждый с каждым"; повышенная устойчивость сети при отказе отдельных компонентов; допущение произвольной масштабируемости сети в виде увеличения зоны информационного покрытия в режиме самоорганизации;
использование динамической маршрутизации трафика, специальных процедур контроля состояния сети.
Топология беспроводных самоорганизующихся сетей постоянно изменяется из-за перемещения узлов сети или изменения условий распространения радиосигнала, поэтому протоколы и технические решения, используемые в классических проводных сетях передачи данных, например, централизованная маршрутизация с иерархией заранее назначенных маршрутизаторов, в беспроводных самоорганизующихся сетях оказываются неэффективными и не обеспечивают нужную производительность.
Рассмотрен один из классов самоорганизующихся беспроводных сетей - ad hoc-сети и приведена классификация протоколов ad hoc-сетей:
- по типу используемых для маршрутизации данных:
(топологические, географические) - по принципу работы: (проективные, реактивные, гибридные) - по критерию определения оптимальности маршрута (протоколы вектора расстояний, протоколы состояния каналов ) В настоящее время существует множество протоколов маршрутизации в аd hoc-сетях, среди которых наиболее часто используемые: AODV, DSR, OLSR, OSPF MANET, FSR, LANMAR.
Каждый класс протоколов потенциально имеет свои преимущества и недостатки при использовании в ad hoc-сетей. Адекватное теоретическое сравнение протоколов осложнено тем, что на процесс передачи данных в AdHocсетях оказывает влияние большое число различных факторов, многие из которых носят случайных характер и слабо поддаются строгому математическому анализу. В настоящее время основным инструментом сравнительного анализа протоколов маршрутизации при работе в ad hoc-сетях является имитационное моделирование.
Проведенный анализ показал, что протоколы и технические решения, используемые в классических проводных сетях передачи данных, в ad hoc - сетях оказываются неэффективными и не обеспечивают требуемую производительность. Кроме того, на сегодняшний день не существует достаточно точных и адекватных моделей и инструментариев, с помощью которых решается задача поддержания показателей производительности беспроводных компьютерных сетей с учетом изменения параметров их функционирования в реальном масштабе времени.
Обоснована необходимость разработки методов маршрутизации, использующих решение задачи динамического выбора предпочтительного протокола маршрутизации в зависимости от совокупности факторов, таких как загрузки сети, числа узлов в сети и загруженных в них сетевых задач, мобильности узлов сети и других параметров.
Сформулированы цель и задачи исследования, заключающиеся в необходимости разработки методического аппарата, позволяющего на основе анализа состояния сети, оценки ее параметров в реальном масштабе времени, решать задачу динамического выбора предпочтительного протокола маршрутизации для обеспечения поддержания показателей производительности сети на уровне, не ниже заданного.
Во второй главе Разработка архитектурно-целевого подхода к обоснованию решения задачи динамической маршрутизации в беспроводной компьютерной сети В работе обосновано, что актуальной научной задачей является обеспечение выбора метода маршрутизации БКС на основе ее архитектурной модели, целевых установок корпоративной сети и решаемых сетевых задач.
Методы маршрутизации относятся к наиболее эффективным механизмам повышения производительности современных коммуникационных сред, отличающихся распределенностью, мобильностью и мультисервисностью.
Высокой вариативностью построения алгоритмов функционирования. При этом при выборе методов маршрутизации как правило не учитываются архитектурные особенности и целевые установки корпоративных беспроводных и самоорганизующихся сетей в целом, что в свою очередь приводит к резкому ухудшению характеристик взаимодействия пользовательских приложений и снижению производительности сети. Это связано с невыводимостью алгоритмов маршрутизации из системного целевого базиса беспроводной компьютерной сети и использованием таких методов поиска виртуальных соединений узлов, которые не зависят от оценки выполнения целеполагания беспроводной компьютерной сети и ее архитектурных особенностей (информационной, технической и логической структур) в целом. Маршрутизация в современных беспроводных компьютерных сетях носит самостоятельный независимый характер.
Особенностью предложенной концептуальной модели является то, что в настоящее время не существует доказательно выводимого способа выбора метода маршрутизации сети беспроводной корпоративной или самоорганизующейся сети исходя из её заданной архитектуры и целеполагания пользователя, однако достижимый уровень последнего фактора в силу высокой вариативности методов маршрутизации значительно зависит от этих методов.
Основным способом оценки приемлемости выбранного метода маршрутизации является моделирование его процесса в условиях адекватного представления информационной структуры подсети в виде набора данных и возможности определения реальных параметров потоков данных между узлами сети.
Источниками указанных потоков данных являются запросы пользователей на запуск задач и запускаемые для решения задачи приложения.
Сделана вербальная постановка задачи: для реализованной корпоративной беспроводной или самоорганизующейся сети, имеющей заданную архитектуру необходимо выбрать такой метод маршрутизации беспроводных сетей, который бы обеспечивал наиболее предпочтительные значения факторов своего целеполагания.
Проведено исследование влияния характеристик выбранного метода маршрутизации на системные показатели беспроводных сетей на базе разработанной концептуальной модели, которая включает:
формализации методов маршрутизации беспроводных сетей;
формализации целевых установок беспроводных сетей;
взаимосвязи указанных выше факторов развития и конструирования беспроводных сетей.
Концептуальная модель основана на предположении о чувствительности апостериорных значений показателей качества беспроводной сети к выбранным методам маршрутизации. Данное предположение вызывает необходимость учета архитектурных особенностей беспроводной сети и ее целевых установок в виде системных показателей качества. Обобщенная схема концептуальной модели архитектурно-целевого обоснования параметров беспроводных сетей представлена на рис. 1.
Требования пользовательских сетевых приложений П р о е Целеполагание БКС Архитектура БКС к A=
A =
TS - техническая структура БКС, определяющая множество узлов и другие технические ресурсы, также уточняемые ниже;
LS - логическая структура БКС, связанная с реализацией множества протоколов по обеспечению взаимодействия пользовательских (прикладных) процессов (приложений), построенных в соответствии с выбранной моделью взаимосвязи. В общем случае в состав логической модели можно включить протоколы сеансового, транспортного, сетевого и канального уровней, привязываясь к семиуровневой модели взаимосвязи открытых сетей.
Важнейшим элементом концептуальной модели обоснования метода маршрутизации беспроводной сети является фактор целеполагания данной сети.
Целеполагание представляет собой совокупность важнейших пользовательских требований к качеству функционирования беспроводной сети.
Требования, определяющие фактор целеполагания могут быть представлены в форме следующих системных характеристик (свойств):
производительности, надежности, безопасности, управляемости, интегрируемости, поддержки разных классов трафика, качества сетевого обслуживания, расширяемости, масштабируемости и прозрачности. В частности, характеристики производительности сети могут принимать форму времени реакции сети, пропускной способности, задержки передачи. Характеристики надежности и безопасности - такими параметрами, как: готовность (коэффициент готовности), вероятность доставки пакета узлу назначения без искажения, вероятности потери пакетов, вероятность искажения бита передаваемой информации, безопасность (защита от НСД), отказоустойчивость и др.
Таким образом, определенный выше фактор целеполагания - C представлен в виде кортежа:
C = < P, Z, Ts(P,Z), E(Ts) >, (2) где P - множество пользовательских рабочих мест, обеспечиваемых КС взаимодействием в полном объеме требований. В упрощенном виде множество P может состоять из перечня пользователей КС, наделенных определенными полномочиями по инициализации и решению пользовательских приложений (специальных прикладных процессов);
Z - множество пользовательских приложений (задач), решаемых пользователями БКС в интересах бизнеса или другого человеческого интереса;
Ts(P,Z) - множество важнейших пользовательских требований к качеству функционирования беспроводной сети, соотнесенных с элементами множеств P и Z. В самом простом случае, когда пользовательские требования не соотносятся с отдельными приоритетными задачами или пользователями данный элемент C приобретает простой вид - Ts;
E(Ts) - функция предпочтения (выбора вариантов маршрутизации), определяющая приоритетность различных пользовательских требований исходя из интересов самого пользователя.
Задачу архитектурно-целевого обоснования метода маршрутизации можно сформулировать следующим образом: необходимо для реализованной беспроводной сети выбрать такой метод маршрутизации, который бы обеспечивал наиболее предпочтительные значения фактора своего целеполагания.
Функция выбора вариантов маршрутизации (предпочтения) представлена в следующем виде:
E(Ts)=
m*- выбранный метод маршрутизации беспроводной сети;
Mv - множество методов маршрутизации беспроводных сетей;
учитываемых при решении задачи;
Ar Цархитектура корпоративной сети.
Тогда указанную выше вербальную постановку решаемой задачи можно представить в виде:
Kz[Кy,, Q, E(CZ,m*, Mv, Ar)] max (4) Tdp Tzт Tdp - время доставки пакетов;
Tzт - требуемое время доставки пакетов;
Ky - количество узлов сети;
Q - приоритет решаемых задач;
Kz- показатель эффективности (количество обслуживаемых запросов за единицу времени) Для решения задачи в виде (4) требуется разработка соответствующего методического аппарата, обеспечивающего возможность по заданным пользовательским требованиям синтезировать архитектурно-целевые факторы корпоративной беспроводной сети, а также информационно-технические структуры сети.
В третьей главе Разработка модели, алгоритмов и методики динамической маршрутизации в беспроводной компьютерной сети разработана структурно-функциональная схема инструментальной моделирующей системы (ИМС), не зависящая от конкретной программно - аппаратной реализации для адекватного представления сетевой нагрузки, сетевых протоколов, возможности достоверной оценки важнейших системных вероятностно-временных характеристик. В общем виде маршрутизационное решение (МР) представлено следующим образом:
МР = <П, М, Т >, (5) где: П - протокол маршрутизации;
М - используемая оценочная метрика возможных маршрутов передачи сообщений по сети;
Т - маршрутная таблица, определяющая для каждого сообщения исходя из адресов получателя и потребителя информации, точный адрес следующего шага в передаче этого сообщения.
Протокол маршрутизации задает конкретное правило обработки и накопления информации, необходимой для формирования маршрутной таблицы, используемой для определения направления передачи принятого сообщения в зависимости от содержания его адресной группы.
В общем случае, обоснование целесообразных параметров маршрутизационых решений требует сложной итерационной процедуры выбора, представления, моделирования и оценки различных существующих и разработанных вариантов таких решений. На рис. 2 представлен обобщенный алгоритм обоснования целесообразных параметров маршрутизационных решений, который имеет следующие особенности своей реализации.
Рис.2. Обобщенный алгоритм обоснования целесообразных параметров маршрутизационных решений Блок 1. На этапе представления сети и пользовательских данных обеспечивается реальное отражение характеристик решений пользовательских специальных прикладных задач и процессов с учетом всего контингента должностных лиц, их приоритетности, закрепления за ними корпоративных задач, использования всего перечня корпоративных ресурсов, распределенных по компонентам сети, а также реальных нагрузок решения приложений. На этом же этапе представляется топология беспроводной корпоративной сети, включая ее декомпозицию на различные фрагменты, имеющие свои специфические процедуры взаимодействия (проводные и беспроводные подсети).
Блок 2. Представление списка исследуемых вариантов маршрутизационных решений опирается на систематизированное представление задачи маршрутизации в беспроводных компьютерных сетях. При этом должны быть представлены для исследования несколько наиболее вероятных вариантов (список) таких маршрутизационных решений.
Блок 3. Выбор очередного варианта из предложенных к исследованию маршрутизационного решения обуславливается готовностью к проведению сеанса моделирования в полном масштабе пользовательских нагрузок и обеспечения возможности снятия временных параметров реализации соответствующих процессов.
Блок 4. Проведение сеанса моделирования происходит на однотипных данных, характеризующих устоявшийся режим использования корпоративной сети и всех ее участков (подсетей). Данное условие обеспечивает возможность сравнения результатов для различных маршрутизационных решений между собой с целью обоснованного выбора наиболее целесообразного из них.
Блок 5. По окончании перебора списка исследуемых вариантов маршрутизационных решений алгоритм завершает свою работу. Иначе - осуществляется выбор следующего варианта из списка.
Блок 6. Представление сравнительных оценочных данных для всех исследуемых вариантов маршрутизационных решений по всем заданным пользователем оценочным общесистемным показателям.
На основе формальной маршрутизационной модели, обобщенного алгоритма обоснования целесообразных параметров маршрутизационных решений представленных выше средств анализа сетевых решений разработана методика выбора маршрутизационных решений, представленная на рис.Рис. 3. Методика выбора сетевых маршрутизационных решений На первом этапе проводится анализ и выбор возможных МР для исследования. Эта неформальная процедура, основанная на известных рекомендациях, результатах практического использования различных методов маршрутизации и с учетом специфики исследуемой корпоративной сети.
На втором этапе проводится моделирование выбранных МР. Этот этап является самым содержательным с точки зрения программной реализации инструментальной моделирующей среды, используемой в работе.
На третьем этапе осуществляется представление списка выбранных МР для проведения сеанса моделирования корпоративных сетевых процессов в виде погружения очередной разработанной модели МР в среду моделирования.
Проведение сеансов моделирования корпоративных сетевых процессов - содержание четвертого этапа. На пятом этапе реализуется процедура сравнительной оценки выбранных МР, результаты которой представляются на шестом этапе в процессе формирования выбора предпочтительного МР. Для построения модели принятия решения о выборе предпочтительного МР обосновано применение математического аппарата теории искусственных нейронных сетей (НС). Как известно, задача синтеза НС состоит из следующих этапов: нейросетевой интерпретации задачи (выбора архитектуры сети), конструирования энергетической функции сети и определения параметров сети (матрицы синоптических связей и вектора внешних смещений) или обучения сети. На первом этапе была синтезирована архитектура НС, затем проведено её обучение. Для поиска неизвестных параметров, обеспечивающих адекватность НС данным эксперимента был использован метод обратного распространения ошибки. В результате синтезирована НС (рис.4), представляющая собой двухслойный персептрон. Для обучения и тестирования нейронной сети использовалась программа, написанная на Delphi с использованием библиотеки NeuralBase. Обучающая выборка состояла из 300 примеров, число узлов в сети изменялось от 2 до 1000, номер преобладающего класса от1 до 4, средняя мобильность узлов от 0,01 до 0,9. Среднеквадратическая ошибка, усредненная по всем обучающим примерам, составила 0,00027.
На входы подаются значения параметров функционирования сети, а выходы обеспечивают выбор соответствующего протокола маршрутизации.
Рис. 4. Двухслойный персептрон для решения задачи выбора МР Входы синтезированного персептрона:
х1 - средняя мобильность узлов;
х2 - номер преобладающего класса пользовательских задач в узлах сети (табл.1);
х3 - число узлов в сети;
Выходы синтезированного персептрона:
y1 - выход возбуждается при выборе протокола AODV и не возбуждается во всех остальных случаях, y2 - выход возбуждается при выборе протокола DSR и не возбуждается во всех остальных случаях, y3 - выход возбуждается при выборе протокола DSDV и не возбуждается во всех остальных случаях.
Совокупность пользовательских задач, решаемых в узлах сети подразделяется на классы (см. табл.1). Каждая из задач характеризуется набором параметров (надежностью, задержкой, флуктуацией и пропускной способностью). Каждый из классов задач характеризуется чувствительностью, которая оценивается цифрами от 1 до 3 (1 - низкая чувствительность, 2 - средняя, 3 - высокая).
Таблица Чувствительность классов сетевых пользовательских задач к параметрам сети Переход на новый протокол передачи данных в беспроводной компьютерной сети не может происходить мгновенно, требуется сохранение текущего состояния в узлах сети, разрыв соединений и повторное подключение (Reconnect). Очевидно, что переход на новый протокол целесообразен тогда, когда эффект ускорения работы сети, полученный в результате использования выбранного протокола превосходит временные затраты, связанные с переходом на этот протокол.
На основе разработанной методики по заданным пользовательским требованиям, целевым факторам, параметрам управления сетью, информационно- технической структуре сети осуществляется выбор маршрутизационного решения, обеспечивающего максимальное значение показателя эффективности функционирования сети - количества обслуживаемых запросов за единицу времени. Методика включает два этапа.
На первом из них обосновывается решение о выборе предпочтительного протокола маршрутизации, а на втором - решение о целесообразности перехода на выбранный протокол. В качестве инструментального средства использована интеллектуальная нейросетевая технология, позволяющая в реальном масштабе времени принимать эффективные маршрутизационные решения, представленная на рис. 5.
Рис. 5. Схема выбора предпочтительного протокола В данной схеме используется две нейросети: описанный выше обученный многослойный персептрон НС1 и необученный НС2. Блок оценки сетевых характеристик определяет характеристики сети с действующим протоколом. По заданным входным данным НС1 определяет предпочтительный протокол, информация о выбранном протоколе поступает на входы блока перехода на выбранный протокол, который должен осуществить этот переход. На входы этого блока поступает информация от НС2 после завершения его обучения. Блок перехода на выбранный протокол осуществляет данный переход, после этого блоком оценки эффективности определяется эффективность нового протокола.
Оценка эффективности рассчитывается как отношение времени доставки пакетов или других сетевых характеристик по старому протоколу к новому протоколу.
если эффективность меньше заданного порогового значения, то формируется информация о неверном переходе, которая поступает на входы блока формирования обучающей выборки. Данный блок формирует обучающую выборку для НС2. Информация с выходов данного блока поступает на блок обучения НС2. Данный блок осуществляет обучение НС2 После завершения обучения НС2 по заданным входным параметрам характеристикам сети и выбранного протоколу блоком НС1 определяет целесообразность перехода на новый протокол. Информация с выходов НС2 поступает на входы блока перехода на новый протокол, который только, если переход целесообразен осуществляет данный переход.
Практические результаты реализации данного методического аппарата представлены в четвертой главе.
В четвертой главе Экспериментальная реализация разработанной методики динамической маршрутизации в беспроводной компьютерной сети представлены результаты вычислительного эксперимента по выбору предпочтительного протокола маршрутизации.
Эксперименты проводились на модели беспроводной самоорганизующейся ad hoc- сети. Рассматривались протоколы маршрутизации: AODV, DSDV, DSR.
В результате моделирования протоколов оценивались такие показатели работы сети, как: коэффициент доставки пакетов (рис. 5), 0,0,0,DSR 0,AODV DSDV 0,0,5 10 15 20 25 30 35 Число узлов БКС Рис. 5. Зависимость коэффициента доставки пакетов от числа узлов сети время доставки пакетов для каждого рассматриваемого протокола беспроводной сети при различной пользовательской нагрузке (рис.6).
2,1,DSR AODV DSDV 0,5 10 15 20 25 30 35 Число узлов БКС Рис. 6. Зависимость времени доставки пакетов от числа узлов Коэффицент доставки пакетов сек Время доставки пакетов в На основе полученных сравнительных оценочных данных сделаны выводы о достоинствах и недостатках тех или иных протоколов в зависимости от пользовательской нагрузки, мобильности узлов и других факторов.
При проведении экспериментов сделано допущение, что сетевые пользовательские задачи подразделяются на четыре класса (табл.1).
В результате проведенного вычислительного эксперимента с использованием синтезированного двухслойного персептрона была получена зависимость коэффициента абсолютного ускорения от числа узлов, которая представлена на рисунке 7. Коэффициент абсолютного ускорения представляет собой отношение времени доставки пакетов с использованием текущего протокола маршрутизации ко времени доставки пакетов с использованием протокола маршрутизации, выбранного на основе разработанной методики.
Значение коэффициента абсолютного ускорения для каждого протокола (DSR, AODV, DSDV) определялось с учетом одинаковой мобильности узлов и номера преобладающего класса задач для всех протоколов.
Рис.7. Зависимость коэффициента абсолютного ускорения от числа узлов Из рис. 7. видно, что при числе узлов больше 15 значение коэффициента абсолютного ускорения равна единице, т.е. выбранный протокол является DSR.
Значение коэффициента абсолютного ускорения выбранного протокола для числа узлов равное 35 в 2 раза и более чем в 3 раза выше для AODV и DSDV.
При малом числе узлов, например, при 10, как видно из рис. 7, значение коэффициента абсолютного ускорения выбранного протокола может быть равной 1,1, т.е. на 10% лучше по сравнению с другими протоколами.
Предложенная методика выбора предпочтительного маршрутизационного решения обладает универсальностью и может быть использована для поддержки принятия решений по обоснованию протокольных реализаций в различных классах беспроводных компьютерных сетей.
В ходе экспериментальной оценки разработанной методики подтверждена ее эффективность. Результаты вычислительного эксперимента подтвердили ее работоспособность и эффект ускорения работы сети.
Разработанная программа может быть реализована в виде службы, функционирующей на одном из узлов сети, которая периодически опрашивает узлы, получая данные об их мобильности, числе узлов, классов решаемых задач, и т.д., на основе разработанной модели принимает решение о переходе на соответствующий протокол.
Основные результаты работы 1. Проведен анализ и классификация существующих методов и протоколов маршрутизации в беспроводных компьютерных ad hoc-сетях с оценкой их эффективности по различным метрикам. Показано, что для обеспечения поддержания производительности сети на заданном уровне требуется динамическое изменение активного на данный момент времени протокола на другой с учетом изменения параметров функционирования сети.
2. Обоснована необходимость разработки методов маршрутизации, использующих решение задачи динамического выбора предпочтительного протокола маршрутизации в реальном масштабе времени в зависимости от совокупности факторов, таких как загрузки сети, числа узлов в сети и загруженных в них сетевых задач, мобильности узлов сети и других параметров.
3. Обоснована необходимость использования архитектурно - целевого подхода при разработке методики адаптивной маршрутизации. Разработана концептуальная модель решения поставленной в исследовании задачи в основе которой лежит зависимость апостериорных значений показателей качества беспроводной компьютерной сети от выбранных методов маршрутизации.
Указанная зависимость обусловила необходимость учета архитектурных особенностей сети и ее целевых установок при построении концептуальной модели, включающей такие компоненты как: архитектура сети (информационная, техническая и логическая структуры), целеполагание (множество пользовательских требований к сети, автоматизированных рабочих мест, пользовательских приложений и функция предпочтения, определяющая приоритетность различных пользовательских требований) и характеристики беспроводной коммуникационной среды.
4. Разработана структурно-функциональная схема инструментальной моделирующей системы, учитывающей адекватное представление сетевой нагрузки пользовательскими приложениями, возможность достоверной оценки важнейших системных вероятностно-временных характеристик и адекватного представления сетевых протоколов, включая маршрутизационные решения и возможность обеспечения реальной чувствительности заданных общесистемных характеристик к варьируемым сетевым параметрам.
5. Разработан обобщенный алгоритм обоснования целесообразных параметров маршрутизационных решений, отражающий сложную итерационную процедуру их выбора на основе заданных пользователем оценочных общесистемных показателей и представления сетевой среды реализации пользовательских приложений, которая позволяет обеспечивать адекватное отражение совокупности факторов (параметров пользовательского контингента должностных лиц, пользовательских задач, используемых программноаппаратных ресурсов, допустимых характеристик пространственной и временной мобильности пользовательского контингента, требуемых значений показателей качества функционирования беспроводной среды взаимодействия) средствами инструментальной среды моделирования с целью обоснованного выбора варьируемых параметров сетевых факторов взаимодействия. Проведена верификация инструментальной среды моделирования, подтвердившая достаточный уровень доверия к полученным результатам.
6. Разработана математическая модель динамического управления беспроводной компьютерной сетью с использованием интеллектуальных технологий, позволяющая обосновать перечень параметров сетевых факторов взаимодействия, перечень целесообразных параметров маршрутизационных решений, требования к ним. На основе модели решается задача обоснованного выбора предпочтительного протокола маршрутизации на основе архитектурно - целевого подхода с учетом пользовательских задач, загруженных в узлы сети.
Разработанная модель учитывает взаимосвязь и влияние друг на друга:
информационной, технической и логической структур беспроводной компьютерной сети; методов маршрутизации и основных пользовательских требований, предъявляемых к беспроводной сети; маршрутизационных решений и базовых параметров функционирования беспроводной сети.
7. На основе разработанной модели предложена методика выбора предпочтительного протокола маршрутизации в беспроводной ad hoc- сети в зависимости от ее состояния, архитектурной модели и целевых установок. На основе разработанной методики по заданным пользовательским требованиям, целевым факторам, параметрам управления сетью, информационно- технической структуре сети осуществляется выбор маршрутизационного решения, обеспечивающего максимальное значение показателя эффективности функционирования сети - количества обслуживаемых запросов за единицу времени. Методика включает два этапа. На первом из них обосновывается решение о выборе предпочтительного протокола маршрутизации, а на втором - решение о целесообразности перехода на выбранный протокол. В качестве инструментального средства использована интеллектуальная нейросетевая технология, позволяющая в реальном масштабе времени принимать эффективные маршрутизационные решения.
8. Проведено экспериментальное исследование разработанной методики.
Результаты вычислительного эксперимента подтвердили работоспособность разработанной методики, на основе которой выработаны научно обоснованные рекомендации по совершенствованию функционирования беспроводных сетей.
Основные публикации автора по теме диссертации:
Публикации в изданиях, рекомендованных ВАК:
1. Шаваша А. Решение задачи выбора предпочтительного протокола маршрутизации в ad hoc-сетях на основе использования аппарата нейронных сетей // Открытое образование. - 2011. - № 6. - С. 59-63.
Публикации в других изданиях:
1. Пятибратов А.П., Шаваша А. Выбор конфигурации локальной сети. - М.:
Сборник научных трудов НТЦ развития учебного процесса МЭСИ, вып. 6, 2009.
С. 53-63.
2. Шаваша А., Пятибратов А.П. Технология формирования локальной компьютерной сети предприятия: общая постановка задачи и требования к формируемой сети. - М.: Сборник научных трудов НТЦ развития учебного процесса МЭСИ, вып. 6, 2009. С. 48-51.
3. Шаваша А, Микрюков А.А. Адаптивная маршрутизация в беспроводных сетях, VII Международная научно-методическая конференция Совершенствование подготовки IT-специалистов по направлению Прикладная информатика для инновационной экономикиФ: Сборник научных трудов / Московский государственный университет экономики, статистики и информатики - М., 2011. С.278-282.
4. Микрюков А.А., Шаваша А. Особенности задачи синтеза топологической структуры и методов управления беспроводными компьютерными ad hocЦ сетями. - М.: Сборник научных трудов НТЦ развития учебного процесса МЭСИ, вып. 1, 2012.
По мнению автора настоящая диссертационная работа представляет собой научно-квалификационную работу, в которой получена совокупность научно обоснованных технических разработок по архитектурно-целевому обоснованию метода маршрутизации в беспроводных самоорганизующихся компьютерных сетях, имеющих важное значение для ускорения работы этих сетей.
Благодарности Автор диссертационной работы выражает глубокую благодарность и признательность своему научному руководителю кандидату технических наук, доценту Микрюкову А.А., доктору технических наук, профессору Пятибратову А. П., а также научному консультанту доктору технических наук, доценту Оцокову Ш.А. за научно-технические и методические консультации, способствующих постановке и успешному решению основных задач исследования.
Авторефераты по всем темам >>
Авторефераты по техническим специальностям