Бикритериальная модель и алгоритмы оптимизации сети передачи данных Лазарев, Евгений Александрович

Введение к работе

Актуальность работы. С развитием сети Интернет, сетей связи и коммуникации люди стали обмениваться все большими объемами информации. Немаловажную роль играет высокая доступность телекоммуникационных услуг. Так, к концу 1995 года в мире насчитывалось всего 26 миллионов пользователей сети Интернет, тогда как к сентябрю 1999 их количество перевалило за 201 миллион, а в 2012 интернет-аудитория составляет более полутора миллиардов человек (около четверти населения земного шара).

По прогнозам компании Cisco объем передаваемых данных в сети Интернет к 2015 году по сравнению с 2011 возрастет в 4 раза, достигнув отметки в тысячу экзабайт в год. Такое значительное увеличение количества передаваемой информации будет оказывать существенную нагрузку на имеющиеся сети передачи данных (СПД). Таким образом, оптимизация существующих и создание новых СПД, способных удовлетворить все растущие требования конечных пользователей, являются крайне важными и актуальными задачами.

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

Проектированию и оптимизации СПД посвящены работы В.М. Гостева, Д. Дэвиса, Ю.П. Зайченко, Л. Клейнрока, С.Е. Ландсберга, А.А. Морозова, М.Х. Прилуцкого, И.А. Соколова, А.А. Стецко, Г.Ф. Янбыха, М. Gerla и M. Averili. Фундаментальные исследования по компьютерным сетям представлены в работах Д. Бертсекаса, Р. Бесслера, В.И. Вишневского, А.В. Максименкова, В.Г. Олифер и Н.А. Олифер, М. Шварца, А.В. Шмалько, M.G.C. Resende и P.M. Pardalos. Различным методам решения многокритериальных задач оптимизации посвящены работы М.А. Айзермана, Д.И. Батищева, Ю.А. Дубова, Д.И. Когана, В.Д. Ногина, В.В. Подиновского, Ю.С. Федосенко, Д.Е. Шапошникова, Р. Штойера и других.

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

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

Объектом исследования является сеть передачи данных и методы ее оптимизации.

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

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

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

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

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

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

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

4. Программная реализация предложенных методов.

Научная новизна работы состоит в следующем.

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

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

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

   Основные положения, выносимые на защиту.

   4. 2. 1. Математическая модель сети передачи данных.

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

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

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

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

         Внедрение. Результаты работы использованы в практической деятельности ООО «Теком» при разработке системы анализа и мониторинга качества услуг широкополосного доступа IRWIn QoS, а также внедрены в учебный процесс НГТУ при организации лекционного курса «Моделирование» для студентов и аспирантов кафедр «Вычислительных систем и технологий» и «Компьютерные технологии в проектировании и производстве».

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

         4. 2. 3. 1. Вторая международная конференция «Second International Conference on Network Analysis», Nizhny Novgorod, 2012.

                  2. Международные молодежные научно-технические конференции "Информационные системы и технологии", Нижний Новгород, 2010, 2011 (выступление отмечено дипломом), 2012 (выступление отмечено дипломом).

                  3. Международная молодежная научно-техническая конференция "Будущее технической науки БТН - 2011", Нижний Новгород, 2011.

                  4. Нижегородская сессия молодых ученых, Нижний Новгород, 2012 (выступление отмечено дипломом).

                  5. Десятая научная конференция с участием зарубежных ученых «Дифференциальные уравнения и их приложения в математическом моделировании», Саранск, 2012.

                  Публикации. Материалы диссертации опубликованы в 14 печатных работах, из них четыре статьи в рецензируемых научных журналах списка ВАК

                  [1-4].

                  Личный вклад автора. Содержание диссертации и основные положения, выносимые на защиту, отражают персональный вклад диссертанта в опубликованные работы. Математическая модель сети передачи данных, алгоритмы, основанные на эволюционно-генетическом подходе и методе ветвей и границ, разработаны совместно с соавторами. Решающая процедура, основанная на методе имитации отжига, все дополнительные эвристики и способы оценки субоптимальной совокупности решений предложены соискателем. Программный комплекс решения задачи проектирования и оптимизации сети передачи данных и все алгоритмы, представленные в работе, реализованы лично диссертантом. Подготовка публикаций проводилась совместно с соавторами, причем соискателем были лично написаны [Error! Reference source not found.3, 5, 6, 7, 14]. Все представленные результаты вычислительных экспериментов получены лично диссертантом.

                  Структура и объем диссертации. Диссертация состоит из введения, четырех глав, заключения, пяти приложений и библиографического списка из 125 наименований; содержит 120 страниц текста, 34 рисунка и 12 таблиц.

                  Похожие диссертации на Бикритериальная модель и алгоритмы оптимизации сети передачи данных

                  

                  Разработка моделей, методов и алгоритмов оптимизации планов ремонтов сетей инженерной инфраструктуры городаКрыгин Андрей Александрович

                  Разработка моделей, методов и алгоритмов оптимизации планов ремонтов сетей инженерной инфраструктуры городаКрыгин Андрей Аександрович

                  

                  Математические модели и алгоритмы анализа и оптимизации функционирования локальной компьютерной сетиАль-Шрайдех Халед Садек

                  

                  Оптимизация операционных характеристик сети передачи данных с коммутацией пакетов Сущенко Сергей Петрович

                  

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

                  

                  Методы и средства исследования распределенных сетей передачи данных с неоднородным трафиком на основе неэкспоненциальных моделейНгуен Дык Тай

                  

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

                  

                  Разработка моделей и алгоритмов оптимизации процедур диагностирования на граф-моделях технических системСтепаненко Мария Анатольевна

                  

                  Анализ и разработка методов и алгоритмов оптимизации графовых моделей на кластерных вычислительных системахНей Мин Тун

                  

                  Разработка математических моделей и алгоритмов оптимизации производства изделий из сапфира для электронной техникиКлунникова, Юлия Владимировна