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

• Лазарев, Евгений Александрович
• кандидат технических наук
• 2013

Оглавление диссертации кандидат технических наук Лазарев, Евгений Александрович

ВВЕДЕНИЕ

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

ОПТИМИЗАЦИИ СЕТИ ПЕРЕДАЧИ ДАННЫХ

§ 1.1 Задачи транспортного типа

§ 1.2 Подходы к решению многокритериальных задач

§ 1.3 Применение метода ветвей и границ для решения задач оптимизации

§ 1.4 Применение генетических алгоритмов для решения задач оптимизации

§ 1.5 Применение алгоритма имитации отжига для решения задач оптимизации

§ 1.6 Модели и методы оптимизации сетей передачи данных

Выводы по главе

ГЛАВА 2. МАТЕМАТИЧЕСКАЯ МОДЕЛЬ, ЗАДАЧА И АЛГОРИТМЫ

ОПТИМИЗАЦИИ СЕТИ ПЕРЕДАЧИ ДАННЫХ

§ 2.1 Структура сети Интернет

§ 2.2 Математическая модель сети передачи данных

§ 2.3 Задача оптимизации сети передачи данных

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

2.3.2 Пример решения задачи

§ 2.4 Нахождение множества Парето-оптимальных решений задачи оптимизации сети передачи данных методом полного перебора

2.4.1 Описание метода

2.4.2 Результаты вычислительных экспериментов

§ 2.5 Нахождение множества Парето задачи оптимизации сети передачи данных методом ветвей и границ

2.5.1 Описание метода

2.5.2 Пример решения задачи методом ветвей и границ

2.5.3 Результаты вычислительных экспериментов

Выводы по главе

ГЛАВА 3.СИНТЕЗ СУБОПТИМАЛЬНОГО МНОЖЕСТВА РЕШЕНИЙ

ЗАДАЧИ ОПТИМИЗАЦИИ СЕТИ ПЕРЕДАЧИ ДАННЫХ

§ 3.1 Представительная выборка

§ 3.2 Отыскание субоптимального множества решений

§ 3.3 Методика оценки отклонения субоптимального множества решений от совокупности Парето

3.3.1 Метод подсчета решений

3.3.2 Метод усреднения отклонения от точного решения

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

3.4.1 Описание метода

3.4.2 Дополнительные эвристики

3.4.3 Пример решения задачи с помощью генетического алгоритма

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

3.4.5 Результаты вычислительных экспериментов

§ 3.5 Нахождение субоптимального множества решений задачи оптимизации сети передачи данных с помощью алгоритм имитации отжига

3.5.1 Описание метода

3.5.2 Дополнительные эвристики

3.5.3 Результаты вычислительных экспериментов

§ 3.6 Использование комбинированных методов

§ 3.7 Сводные графики результатов вычислительных экспериментов

Выводы по главе

ГЛАВА 4.ПРОГРАММНЫЙ КОМПЛЕКС РЕШЕНИЯ ЗАДАЧИ

ПРОЕКТИРОВАНИЯ И ОПТИМИЗАЦИИ СЕТИ ПЕРЕДАЧИ ДАННЫХ И РЕКОМЕНДАЦИИ ПО ПРИМЕНЕНИЮ АЛГОРИТМОВ

§ 4.1 Назначение и возможности программного комплекса

§ 4.2 Описание архитектуры программного комплекса

§ 4.3 Описание графического пользовательского интерфейса

4.3.1 Основное окно работы программы

4.3.2 Главное меню программы

4.3.3 Окно параметров алгоритма

§ 4.4 Типовой сценарий работы с программным комплексом

§ 4.5 Рекомендации по применению алгоритмов

4.5.1 Использование метода полного перебора

4.5.2 Использование метода ветвей и границ и комбинированного метода

4.5.3 Использование генетического алгоритма

4.5.4 Использование алгоритма имитации отжига

Выводы по главе

ЗАКЛЮЧЕНИЕ

ЛИТЕРАТУРА

СПИСОК СОКРАЩЕНИЙ

ПРИЛОЖЕНИЯ

Приложение А. Справка о внедрении результатов диссертационной работы в ООО

«Теком»

Приложение Б. Акт о внедрении результатов диссертационной работы в учебный процесс

Нижегородского государственного технического университета им. Р.Е. Алексеева

Приложение В. Свидетельство о государственной регистрации программы для ЭВМ

Приложение Г. Теоремы о NP-трудности и максимальной мощности множества Парето-

оптимальных решений задачи оптимизации сети передачи данных

Приложение Д. Архитектура интерактивного программного комплекса

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

ВВЕДЕНИЕ

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

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

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

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

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

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

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

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

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

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

проектирования СПД применяются парадигмы объектно-ориентированного программирования.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Личный вклад автора. Содержание диссертации и основные положения, выносимые на защиту, отражают персональный вклад диссертанта в опубликованные работы. Математическая модель сети передачи данных, алгоритмы, основанные на эволюционно-генетическом подходе и методе ветвей и границ, разработаны совместно с соавторами. Решающая процедура, основанная на методе имитации отжига, все дополнительные эвристики и способы оценки субоптимальной совокупности решений предложены соискателем. Программный комплекс решения задачи проектирования и оптимизации сети передачи данных (свидетельство о государственной регистрации программы для ЭВМ в приложении В) и все алгоритмы, представленные в работе, реализованы лично диссертантом. Подготовка публикаций проводилась совместно с соавторами, причем соискателем были лично написаны [39, 40, 41, 43, 44]. Все представленные результаты вычислительных экспериментов получены диссертантом.

В первой главе (Методы решения многокритериальных задач оптимизации сети передачи данных) даются общие сведения о задачах транспортного типа (§1.1), проводится обзор подходов (§1.2) и некоторых алгоритмов (§1.3, §1.4 и §1.5) решения многокритериальных задач, моделей и методов оптимизации сетей передачи данных (§1.6).

Во второй главе (Математическая модель, задача и алгоритмы оптимизации сети передачи данных [31, 32, 34, 36, 37, 39, 42, 44]) рассматривается структура телекоммуникационной сети (§2.1), предлагается математическая модель сети передачи данных (§2.2), формулируется задача оптимизации СПД (§2.3). Для поиска совокупности Парето-оптимальных решений рассматриваемой задачи адаптируется метод ветвей и границ (§2.5). Анализируется его вычислительная сложность. Приводится пример решения задачи оптимизации сети передачи данных предложенным методом и результаты вычислительных экспериментов.

В третьей главе (Синтез субоптимального множества решений задачи оптимизации сети передачи данных [31, 32, 33, 35, 40, 41]) вводятся понятия представительной выборки (§3.1) и субоптимальной совокупности (§3.2), предлагаются два способа оценки отклонения субоптимального множества решений от совокупности Парето (§3.3). Для решения рассматриваемой в диссертационной работе задачи применяются эвристические процедуры поиска субоптимального множества решений на основе генетического алгоритма (§3.4) и метода имитации отжига (§3.5). Приводятся оценки вычислительной сложности предложенных алгоритмов. В §3.6 предлагается комбинированный метод решения рассматриваемой задачи. В §3.7 представлены сводные графики результатов вычислительных экспериментов.

В четвертой главе (Программный комплекс решения задачи проектирования и оптимизации сети передачи данных и рекомендации по применению алгоритмов [38, 125]) в §4.1 описывается назначение и возможности программного комплекса. В §4.2 рассматривается архитектура разработанного программного обеспечения, представлена высокоуровневая схема взаимодействия между его компонентами. В §4.3 описывается графический пользовательский интерфейс. В параграфе представлено описание основного окна работы программы, элементов меню, а также окна параметров алгоритма. В §4.4 дается типовой сценарий работы с программным комплексом. В §4.5 представлены рекомендации по использованию предложенных алгоритмов.

В заключении изложены основные научные и практические результаты диссертационной работы.

Приложение содержит документы о внедрении и использовании результатов диссертационной работы, свидетельство о государственной регистрации программы для ЭВМ, доказательства теорем о ИР-трудности и максимальной мощности множества Парето-оптимальных решений рассматриваемой задачи, описание архитектуры интерактивного программного комплекса (ИПК), иМЬ-диаграммы основных классов ИПК, пример конфигурационного файла р^тз.хт!, описывающего решающие алгоритмы.

Заключение диссертации по теме «Системный анализ, управление и обработка информации (по отраслям)», Лазарев, Евгений Александрович

Выводы по главе

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

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

3. Описана архитектура разработанного программного комплекса, приведена схема взаимодействия между компонентами ИПК.

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

5. Разработано программное обеспечение, реализующее предложенные алгоритмы. Получено авторское свидетельство об официальной регистрации программы для ЭВМ № 2012616035.

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

ЛИТЕРАТУРА

1 Айзерман, М.А. Выбор вариантов: основы теории [Текст] / М.А. Айзерман, Ф.Т. Алескеров II - М.: Наука, 1990. - 240 с.

2 Алексеев, О.Г. Комплексное применение методов дискретной оптимизации [Текст] / О.Г. Алексеев. - М.: Наука. Гл. ред. физ-мат. лит., 1987.-248 с.

3 Батищев, Д.И. Генетические алгоритмы решения экстремальных задач [Текст] / Д.И. Батищев. Воронеж, 1995. - 62 с.

4 Батищев, Д.И. Методы оптимального проектирования [Текст] / Д.И. Батищев. - М.: Радио и связь, 1984. - 248 с.

5 Березовский, Б.А. Задача наилучшего выбора [Текст] / Б.А. Березовский,

A.B. Гнедин // - М.: Наука, 1984.- 196 с.

6 Березовский, Б.А. Многокритериальная оптимизация. Математические аспекты [Текст] / Б.А. Березовский, Ю.М. Барышников, В.И. Борзенко, Л.М. Кемпнер // - М.: Наука, 1989. - 128 с.

7 Бертсекас, Д. Сети передачи данных [Текст] / Д. Бертсекас, Р. Галлагер // -М.: Мир, 1989.-544 с.

8 Бесслер, Р. Проектирование сетей связи [Текст] / Р. Бесслер, А. Дойч // -М.: Радио и связь, 1988. - 272 с.

9 Вишневский, В.И. Теоретические основы проектирования компьютерных сетей [Текст] / В.И. Вишневский. М.: Техносфера, 2003. - 512с.

10 Гермейер, В.Б. Введение в теорию исследования операций [Текст] /

B.Б. Гермейер. - М.: Наука, 1971. - 383 с.

11 Голынтейн, Е.Г. Новые направления в линейном программировании [Текст] / Е.Г. Гольштейн, Д.Е. Юдин. М.: «Сов. радио», 1966. - 527 с.

12 Гостев, В.М. Система оптимизации проектирования сетей передачи данных [Текст] / В.М. Гостев. Ученые записки Казанского университета. Серия: Физико-математические науки, 2007. № 2. - С. 35-48.

13 Гэри, М. Вычислительные машины и труднорешаемые задачи [Текст]/ М. Гэри, Д. Джонсон. - М.: Мир, 1982. - 416 с.

14 Джонс, М.Т. Программирование искусственного интеллекта в приложениях [Текст] / М.Т. Джонс // - М.: ДМК Пресс, 2006. - 312 с.

15 Дубов, Ю.А. Многокритериальные модели формирования и выбора вариантов систем / Ю.А. Дубов, С.И. Травкин, В.Н. Якимец // - М.: Наука, 1986.-296 с.

16 Дэвис, Д. Вычислительные сети и сетевые протоколы / Д. Дэвис, Д. Барбер, У. Прайс, С. Соломонидес // - М.: Мир, 1982. - 564 с.

17 Дуничкина, H.A. Анализ и алгоритмы решения бикритериальных задач управления обслуживанием стационарных объектов шоЬіІе-процессорами [Текст]: дис. канд. физ.-мат. наук: 05.13.01: защищена 05.04.2012 г. / Дуничкина Надежда Александровна. - Нижний Новгород, 2012. - 163 с. -Библиогр.: с. 147-158. - 04201201112.

18 Дуничкина, H.A. Об оценке приближенных решений бикритериальных задач дискретного программирования [Текст] / H.A. Дуничкина, Ю.С. Федосенко // Информационные системы и технологии ИСТ-2009. Материалы XV международной научно-технической конференции. -Н.Новгород: НГТУ, 2009. - С. 300-302.

19 Дуничкина, H.A. Применение муравьиного алгоритма для решения бикритериальной задачи обслуживания группы стационарных объектов [Текст] / H.A. Дуничкина // Сб. трудов аспирантов и магистрантов. Технические науки. - Нижний Новгород: Изд. ННГАСУ, 2008. - С. 162166.

20 Жожикашвили, В.А. Сети массового обслуживания. Теория и применение к сетям ЭВМ / В.А. Жожикашвили, В.М. Вишневский // - М.: Радио и связь, 1988. - 192 с.

21 Зайченко, Ю.П. Структурная оптимизация сетей ЭВМ / Ю.П. Зайченко, Ю.В. Гонта // - Киев: Техшка, 1986. - 168 с.

22 Канторович, JI.B. О перемещении масс [Текст] / JT.B. Канторович // Доклады Академии Наук СССР. - 1942. - Т. 37. - С. 199-201.

23 Канторович, JI.B. Применение математических методов в вопросах анализа грузоперевозок [Текст] / JI.B. Канторович, М.К. Гавурин // Проблемы повышения эффективности работы транспорта, Академия Наук СССР. - 1949.-С. 110-138.

24 Кини, P.JI. Принятие решений при многих критериях: предпочтения и замещения / P.J1. Кини, X. Райфа // - М.: Радио и связь, 1981. - 560 с.

25 Клейнрок, Л. Вычислительные системы с очередями / Л. Клейнрок. - М.: Мир, 1979.-600 с.

26 Коган, Д.И. Бикритериальные модели и парето-оптимальные стратегии обслуживания группировки стационарных объектов [Текст] / Д.И. Коган, Ю.С. Федосенко, H.A. Дуничкина // Труды IX Международной конференции «Идентификация систем и задачи управления - SICPRO' 12». Москва 30 января - 2 февраля 2012 г. Институт проблем управления им. В.А. Трапезникова РАН. - М.: Институт проблем управления им. В.А. Трапезникова РАН, 2012. - С. 287-300.

27 Коган, Д.И. Динамическое программирование и дискретная многокритериальная оптимизация [Текст]: учеб. пособие / Д.И. Коган. -Н. Новгород: Изд-во ННГУ им. Н.И. Лобачевского, 2005. - 260 с.

28 Корбут, A.A. Дискретное программирование [Текст] / A.A. Корбут, Ю.Ю. Финкелыитейн; под. ред. Д.Б. Юдина. - М.: Наука, 1969. - 368 с.

29 Кормен, Т. Алгоритмы: построение и анализ [Текст] / Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн // 2-е изд. М.: «Вильяме», 2006. - 1296 с.

30 Краснощекое, П.С. Математические модели в исследовании операций [Текст] / П.С. Краснощекое. М.: Наука, 1984. - 64 с.

31 Лазарев, Е.А. Оптимизация на графах с помощью методов глобальной оптимизации [Текст] / Е.А. Лазарев, Д.Е. Шапошников // Информационные системы и технологии ИСТ-2010. Материалы XVI международной научно-технической конференции. - Н.Новгород: НГТУ,

2010.-С. 294.

32 Лазарев, Е.А. Бикритериальная модель и алгоритмы синтеза оптимальной сети передачи данных [Текст] / Е.А. Лазарев, Д.Е. Шапошников // Информационные системы и технологии ИСТ-2011. Материалы XVII международной научно-технической конференции. - Н.Новгород: НГТУ,

2011.-С. 351.

33 Лазарев, Е.А. Об оценке точности решения бикритериальной задачи синтеза оптимальной сети передачи данных эвристическими алгоритмами [Текст] / Е.А. Лазарев, Д.Е. Шапошников // Будущее технической науки. Материалы X международной молодежной научно-технической конференции. - Н.Новгород: НГТУ, 2011. - С. 64.

34 Лазарев, Е.А. Бикритериальная модель сети передачи данных [Текст] / Е.А. Лазарев, Д.Е. Шапошников, П.В. Мисевич // Системы управления и информационные технологии, №3.2(45), 2011. - С. 255-258.

35 Лазарев, Е.А. Генетические алгоритмы оптимизации сети передачи данных [Текст] / Е.А. Лазарев, Д.Е. Шапошников, П.В. Мисевич // Системы управления и информационные технологии, №4(46), 2011. - С. 59-63.

36 Лазарев, Е.А. Бикритериальная модель сети передачи данных [Текст] / Е.А. Лазарев, Д.Е. Шапошников // Информационные системы и технологии ИСТ-2012. Материалы XVIII международной научно-технической конференции. - Н.Новгород: НГТУ, 2012. - С. 313-314.

37 Лазарев, Е.А. Применение метода ветвей и границ для оптимизации структуры сети передачи данных [Текст] / Е.А. Лазарев, Д.Е. Шапошников // Информационные системы и технологии ИСТ-2012. Материалы XVIII международной научно-технической конференции. -Н.Новгород: НГТУ, 2012. - С. 310-312.

38 Лазарев, Е.А. Средства автоматизации проектирования оптимальной структуры сети передачи данных [Текст] / Е.А. Лазарев, Д.Е. Шапошников // Информационные системы и технологии ИСТ-2012. Материалы XVIII международной научно-технической конференции. -Н.Новгород: НГТУ, 2012. - С. 315.

39 Лазарев, Е.А. О применении эвристик для метода ветвей и границ решения задачи оптимизации сети передачи данных [Текст] / Е.А. Лазарев // Труды Нижегородского государственного технического университета им. Р.Е. Алексеева. - Н.Новгород: НГТУ, 2012, №3. - С. 91-96.

40 Лазарев, Е.А. Методы оценки эффективности алгоритмов решения многокритериальных задач [Текст] / Е.А. Лазарев // Журнал Средневолжского математического общества. - 2012. - Т. 14. - № 2. -С. 81-86.

41 Лазарев, Е.А. Алгоритм имитации отжига решения задачи оптимизации сети передачи данных [Текст] / Е.А. Лазарев // Системы управления и информационные технологии, №3(49), 2012. - С. 50-53.

42 Лазарев, Е.А. Метод ветвей и границ для оптимизации структуры сети передачи данных [Текст] / Е.А. Лазарев, Д.Е. Шапошников, П.В. Мисевич // Известия Волгоградского государственного технического университета: актуальные проблемы управления вычислительной техники и информатики в технических системах, № 10(97), выпуск 14, 2012. - С. 189-193.

43 Лазарев, Е.А. Применение метода ветвей и границ для решения бикритериальной задачи оптимизации сети передачи данных [Текст] / Е.А. Лазарев // Нижегородская сессия молодых ученых. Технические науки. Материалы докладов (17; 2012). - Нижний Новгород: Зверева И.А., 2012.-С. 96-99.

44 Лазарев, Е.А. Методы ускорения адаптированного алгоритма ветвей и границ решения потоковых задач оптимизации теории графов на примере задачи оптимизации сети передачи данных [Текст] / Е.А. Лазарев // Управление в технических, эргатических, организационных и сетевых системах УТЭОСС-2012. Материалы V Российской мультиконференции по проблемам управления. - СПб.: ГНЦ РФ ОАО «Концерн «ЦНИИ «Электроприбор», 2012. - С. 1232-1235.

45 Ландсберг, С.Е. Синтез двухуровневой топологической структуры распределенной информационно-телекоммуникационной сети [Текст] / С.Е. Ландсберг, A.A. Рындин, A.B. Хаустович // - Телематика-96: тез. докл. Всероссийской научно-методической конференции. - С.-Петербург, 13-17 мая 1996.-С. 68-69.

46 Ларичев, О.И. Объективные модели и субъективные решения [Текст] / О.И. Ларичев. - М.: Наука, 1987. - 144 с.

47 Ларичев, О.И. Теория и методы принятия решений [Текст] / О.И. Ларичев. - М.: Логос, 2006. - 296 с.

48 Ларман, К. Применение UML 2.0 и шаблонов проектирования [Текст] / К. Ларман. - М.: Вильяме, 2006. - 736 с.

49 Макаров, И.М. Теория выбора и принятия решений [Текст] / И.М. Макаров, Т.М. Виноградская II - М.: Наука, 1982. - 328 с.

50 Максименков, A.B. Основы проектирования информационно-вычислительных систем и сетей ЭВМ [Текст] / A.B. Максименков, М.Л. Селезнев // - М.: Радио и связь, 1991. - 320 с.

51 Морозов, A.A. Вычислительные эксперименты по оценке пропускных способностей и временных характеристик сетей передачи данных [Текст] /

A.A. Морозов, В.М. Гостев, Р.Ф. Хабиббулин // Исследования по информатике. - Казань: Отечество, 2001. - Вып. 3. - С. 149-164.

52 Ногин, В.Д. Основы теории оптимизации [Текст] / В.Д. Ногин, И.О. Протодьяконов, И.И. Евлампиев. - М.: Высшая школа, 1986. - 384 с.

53 Ногин, В.Д. Принятие решений в многокритериальной среде: количественный подход [Текст] / В.Д. Ногин. - 2-е изд., испр. и доп. -М.: Физматлит, 2004. - 176 с.

54 Ногин, В.Д. Принятие решений при многих критериях [Текст] /

B.Д. Ногин. - СПб: Изд-во Ютас, 2007. - 104 с.

55 Олифер, В.Г. Компьютерные сети. Принципы, технологии, протоколы [Текст] / В.Г. Олифер, H.A. Олифер. - СПб.: Питер, 2006. - 864 с.

56 Подиновский, В.В. Парето-оптимальные решения многокритериальных задач [Текст] / В.В. Подиновский, В.Д. Ногин. - 2-е изд., испр. и доп. - М.: Физматлит, 2007. - 256 с.

57 Прилуцкий, М.Х. Многоиндексные задачи распределения ресурсов в иерархических системах [Текст] / М.Х. Прилуцкий, Л.Г. Афраймович // Автоматика и телемеханика, 2006, № 6. - С. 194-205.

58 Прилуцкий, М.Х. Многокритериальные многоиндексные задачи объёмно-календарного планирования [Текст] / М.Х. Прилуцкий // Известия академии наук. Теория и системы управления, 2007, № 1. - С. 78-82.

59 Прилуцкий, М.Х. Оптимизационные задачи планирования транспортировки газа [Текст] / Прилуцкий М.Х., Костюков В.Е. // Информационные технологии и вычислительные системы. 2007, №2. - С. 67-73.

60 Прилуцкий, М.Х. Оптимизационные задачи объёмно-календарного планирования для нефтеперерабатывающих предприятий [Текст] / Прилуцкий М.Х., Костюков В.Е. // Системы управления и информационные технологии, №2.1(28), 2007. - С. 188-192.

61 Прилуцкий, М.Х. Распределение однородного ресурса в иерархических системах древовидной структуры [Текст] / М.Х. Прилуцкий // Труды международной конференции «Идентификация систем и задачи управления SICPRO 2000». Москва, 26-28 сентября 2000 г. М.: Институт проблем управления им. В.А. Трапезникова РАН, 2000. - С. 2038-2049.

62 Саати, T.JI. Принятие решений при зависимостях и обратных связях: Аналитические сети [Текст] / T.JI. Саати. - М.: Издательство ЛКИ, 2008. -360 с.

63 Сигал, И.Х. Введение в прикладное дискретное программирование. Модели и вычислительные алгоритмы [Текст] / И.Х. Сигал, А.П. Иванова. - М.: Физматлит, 2007. - 304 с.

64 Соколов, И.А. Проблемы построения информационно-телекоммуникационных систем интегрированного типа [Текст] / И.А. Соколов, A.B. Полянский, Э.В. Киселёв, И.Н. Синицин, А.И. Темнов // Системы и средства информатики. Вып. 11. — М.: Наука, 2001. - С. 5-23.

65 Соснина, E.H. Топология городских распределенных интеллектуальных электрических сетей 20 кВ // E.H. Соснина, А.Б. Лоскутов, A.A. Лоскутов // Промышленная энергетика, 2012, №5. - С. 11-17.

66 Стецко, A.A. Автоматизированное проектирование вычислительных сетей крупных проектных организаций [Текст] / A.A. Стецко. -Ульяновск: УлГТУ, 2007. - 195 с.

67 Страуструп, Б. Язык программирования С++. Специальное издание [Текст] / Б. Страуструп; пер. с англ. - М.: ООО «Бином-Пресс», 2005. -1104 с.

68 Толстой, А.Н. Методы нахождения наименьшего суммового километража при планировании перевозок в пространстве [Текст] / А.Н. Толстой // Планирование перевозок. Сборник первый. - 1930. - С. 23-55.

69 Фишберн, П. Теория полезности для принятия решений [Текст] / П. Фишберн. - М.: Наука, 1978. - 352 с.

70 Хачатуров, В.Р. Аппроксимационно-комбинаторный метод и некоторые его приложения [Текст] / В.Р. Хачатуров. - ЖВМиМФ. - 1974. - Т. 14. -№6.-С. 1464-1487.

71 Хачатуров, В.Р. Комбинаторные методы и алгоритмы решения задач дискретной оптимизации большой размерности [Текст] / В.Р. Хачатуров, В.Е. Веселовский, A.B. Злотов, С.У. Калдыбаев. - М.: Наука, 2000. - 354 с.

72 Ху, Т. Целочисленное программирование и потоки в сетях [Текст] / Т. Ху. -М.: Мир, 1974.-520 с.

73 Шапошников, Д.Е. Моделирование электрических распределительных сетей на основе концепции иерархических распределенных канальных систем / Д.Е. Шапошников, М.Н. Ушакова // Труды Нижегородского государственного технического университета им. P.E. Алексеева. -Н.Новгород: НГТУ, 2012, №4. - С. 111-116.

74 Шварц, М. Сети ЭВМ. Анализ и проектирование [Текст] / М. Шварц. -М.: Радио и связь, 1981. - 336 с.

75 Шлюгаев, А.Ю. Математические модели и алгоритмы оптимизации стратегий однопроцессорного обслуживания пространственно рассредоточенной группировки стационарных объектов [Текст]: дис. канд. техн. наук: 05.13.18: защищена 13.11.2008 г. / Шлюгаев Александр Юрьевич. - Нижний Новгород, 2008. - 202 с. - Библиогр.: с. 185-195. -04200816372.

76 Шмалько, А.В. Цифровые сети связи: основы планирования и проектирования [Текст] / А.В. Шмалько. - М.: Эко-Трендз, 2001. - 282 с.

77 Штойер, Р. Многокритериальная оптимизация: теория, расчет и приложения [Текст] / Р. Штойер; пер. с англ. - М.: Радио и связь, 1992. -504 с.

78 Эккель, Б. Философия Java. Библиотека программиста [Текст] / Б. Эккель. - СПб.: Питер, 2009. - 640 с.

79 Янбых, Г.Ф. Оптимизация информационно-вычислительных сетей [Текст] / Г.Ф. Янбых, Б.А. Столяров. - М.: Радио и связь, 1987. - 232 с.

80 Beasley, D. An overview of genetic algorithms: Part 1, Fundamentals [Text] / D. Beasley, D. Bull, R. Martin // University Computing. - 1993. - Vo. 2. - P. 58-69.

81 Dantzig, G.B. Application of the Simplex Method to a Transportation Problem [Text] / G.B. Dantzig // Proceedings of the Activity Analysis of Production and Allocation Conference. - 1951. - P. 359-373.

82 Davis, L. Handbook of Genetic Algorithms [Text] / L. Davis. - New York: Van Nostrand Reinhold, 1991. - 385 p.

83 Deb, K. A fast elitist non-dominated sorting genetic algorithm for multi-objective optimization: NSGA-II [Text] / K. Deb, K. Agrawal, A. Pratap, T. Meyarivan // Proceedings of parallel problem solving from nature. - 2000. -Vo. VI. - P. 849-858.

84 Dorigo, M. Ant Colony Optimization [Text] / M. Dorigo, T. Stützle. - MIT Press, 2004.-319 p.

85 Edmonds, J. Theoretical improvements in algorithmic efficiency for network flow problems / J. Edmonds, R.M. Karp // Journal of the ACM. - 1972. - Vo. 19(2): - P. 248-264.

86 Fedorin, A.N. Branch and bound approaches to solve bicriterion discrete optimization problems [Text] / A.N. Fedorin // VI International Congress on Mathematical Modeling. Book of Abstracts. September 20-26, 2004, Nizhniy Novgorod. - Nizhniy Novgorod: University of Nizhniy Novgorod. - 2004. - 79

P-

87 Figueira, J. Multiple criteria decision analysis: state of the art surveys [Text] / J. Figueira, S. Greco, M. Ehrgott. - Springer, 2005. - 1085 p.

88 Fonseca, C. An overview of evolutionary algorithms in multiobjective optimization [Text] / C. Fonseca, P. Fleming // Evolution Computing. - 1995. -Vo. 3.-P. 1-16.

89 Ford, L.R. Flows in networks [Text] / L.R. Ford Jr., D.R. Fulkerson. -Princeton.: Princeton University Press, 1962. - 194 p.

90 Ford, L.R. Maximal flow through a network [Text] / L.R. Ford Jr., D.R. Fulkerson. - Canadian journal of mathematics, 1956. - Vo. 8(3). - 399404 p.

91 Ford, L.R. Suggested computation for maximal multi-commodity network flows [Text] / L.R. Ford Jr., D.R. Fulkerson. - Man. Sei., 1958. - Vo. 5(1). -97-101 p.

92 Geoffrion, A.M. An interactive approach for multi-criterion optimization, with an application to the operation of an academic department [Text] / A.M. Geoffrion, J.S. Dyer, A. Fienberg // Management Science. - 1972. - Vo. 19.-No. 4.

93 Gerla, M. A cut-saturation algorithm for topological design of packet-switched communication networks [Text] / M. Gerla, H. Frank, W. Chou, J. Eckl // Proceedings of the IEEE national telecommunication conference, San Diego, Dec. 2-4. - 1974. - P. 1074-1085.

94 Gerla, M. On the topological design of distributed computer networks [Text] / M. Gerla, L. Kleinrock // IEEE Transactions on communications. - 1977. - Vo. 25. - No. 1. - P. 48-60.

95 Goldberg, A.V. A new approach to the maximum flow problem [Text] / A.V. Goldberg, R.E. Tarjan // Journal of the ACM, 35. - 1988. - P. 921-940.

96 Goldberg, D. Genetic Algorithms in Search, optimization, and machine learning [Text] / D. Goldberg. - Boston: Addison-Wesley, 1989. - P. 372.

97 Granville, V. Simulated annealing: A proof of convergence [Text] / V. Granville, M. Krivnek, and J-P. Rasson // IEEE Transactions on Pattern Analysis and Machine Intelligence, 16(6). - 1994. - P. 652-656.

98 Haiming, L. State-of-the-art multiobjective evolutionary algorithms - pareto panking, density estimation and dynamic population [Text], PhD thesis, 2002. -207 p.

99 Hitchcock, F.L. The distribution of a product from several sources to numerous localities [Text] / F.L. Hitchcock // Journal of Mathematics and Physics 20. - 1941. - P. 224-230.

100 Holland, J.H. Adaptation in Natural and Artificial Systems [Text] / J.H. Holland. - Ann Arbor: University of Michigan Press, 1975. - P. 211.

101 Horn, J. A niched pareto genetic algorithm for multiobjective optimization [Text] / J. Horn, N. Nafpliotis, D. Goldberg // Proceedings of the 1st IEEE Congress of Evolutionary Computation. - 1994. - P. 82-87.

102 Kirkpatrick, S. Optimization by Simulated Annealing [Text] / S. Kirkpatrick, C.D. Gelatt, M.P. Vecchi // Science. - 1983. - Vo. 220. - № 4598. - P. 671680.

103 Koopmans, Tj.C. Optimum utilization of the transportation system [Text] / Tj.C. Koopmans // Proceedings of the International Statistical Conferences. -1948.-Vo. 5.-P. 136-146.

104 Koopmans, Tj.C. A model of transportation [Text] / Tj.C. Koopmans, S. Reiter // Proceedings of the Activity Analysis of Production and Allocation Conference. - 1951. - P. 222-259.

105 Laarhoven, P. Simulated Annealing: Theory and Applications [Text] / P. Laarhoven, E. Aarts. - Dordrecht, 1987. - P. 198.

106 Land, A.H. An automatic method of solving discrete programming problems [Text] / A.H. Land, A.G. Doig // Econometrica. - 1960. - Vo. 28, № 3.- P. 497520.

107 Law Averiii, M. Simulation software or communications networks: The state of the art [Text] / M. Law Averiii, G. Mc.Comas Michael // IEEE Communications Magazine. - 1994. № 3. - P. 44-50.

108 McDonnell J. Evolutionary Programming IV [Text] / J. McDonnell, R. Reynolds, D. Fogel // Proceedings of the Fourth Annual Conference on Evolutionary Programming, 1995. - P. 805.

109 Michalewicz, Z. Genetic Algorithms + Data Structures = Evolution Program [Text] / Z. Michalewicz. - New York: Springer-Verlag, 1993. - P. 387.

110 Miettinen, K. Nonlinear multiobjective optimization [Text] / K. Miettinen. -Norwell: Kluwer Academic Publishers, 1999. - P. 298.

111 Monge, G. Mémoire sur la théorie des déblais et des remblais [Text] / G. Monge // Histoire de l'Académie Royale des Sciences de Paris, avec les Mémoires de Mathématique et de Physique pour la même année. - 1781. - P. 666-704.

112 Morse, J.N. Reducing the size of the nondominated set: Pruning by clustering [Text] / J.N. Morse // Computers and Operations Research. - 1980. - № 7(1-2). -P. 55-66.

113 Resende, M.G.C. Handbook of Optimization in Telecommunications [Text] / M.G.C. Resende, P.M. Pardalos. - Birkhäuser, 2006. - P. 1134.

114 Robinson, J. On the Hamiltonian Game (A Traveling Salesman Problem) [Text] / J. Robinson. Research Memorandum RM-303, The RAND Corporation, Santa Monica, California. - 1949.

115 Robinson, J. A Note on the Hitchcock-Koopmans Problem [Text] / J. Robinson. Research Memorandum RM-407, The RAND Corporation, Santa Monica, California. - 1950.

116 Rosenman, M.A. Reducing the pareto optimal set in multicriteria optimization [Text] / M.A. Rosenman, J.S. Gero. // Engineering Optimization. - 1985. - № 8.-P. 189-206.

117 Sancho, N.G. A suboptimal solution to a hierarchical network design problem using dynamic programming [Text] / N.G. Sancho // European Journal of Operational Research, 83. - 1995. - № 1. - P. 237-244.

118 Schaffer, J. Multiple objective optimization with vector evaluated genetic algorithms [Text] / J. Schaffer // Proceedings of the 1st International Conference Genetic Algorithms. - 1985. - P. 93-100.

119 Srinivas, N. Multi-objective function optimization using non-dominated sorting genetic algorithms [Text] / N. Srinivas, K. Deb // Evolution Computing. - 1994. - Vo. 2.-P. 221-248.

120 Syswerda, G. Schedule optimization using genetic algorithms [Text] / G. Syswerda // Handbook of Genetic Algorithms, 1989. - P. 2-9.

121 Zitzler, E. Multiobjective evolutionary algorithms: a comparative case study and the strength Pareto approach [Text] / E. Zitzler, L. Thiele // Transactions on Evolutionary Computation. - 1999. - Vo. 3. - P. 257-271.

122 Zitzler, E. SPEA2: Improving the Strength Pareto Evolutionary Algorithm [Text] / E. Zitzler, M. Laumanns, L. Thiele // Technical Report TIK-Report 103, Swiss Federal Institute of Technology, 2001. - P. 21.

123 Cisco: в ближайшие четыре года нас ждет четырехкратный рост объема интернет-трафика. URL:

http://www.cisco.com/web/RU/news/releases/txt/2012/060112a.html (дата обращения 22.09.2012).

124 Hobbes' Internet Timeline 10.2. URL: http://www.zakon.org/robert/internet/timeline/ (дата обращения 22.02.2013).

125 Свидетельство о государственной регистрации программы для ЭВМ № 2012616035. Программный комплекс решения задачи проектирования и оптимизации сети передачи данных / Е.А. Лазарев. - заявл. 10.05.2012; -зарег. 02.07.2012. - Федеральная служба по интеллектуальной собственности, патентам, товарным знакам РФ, Реестр программ для ЭВМ.

СПИСОК СОКРАЩЕНИЙ

ИПК интерактивный программный комплекс;

ЛПР лицо, принимающее решение;

ПО программное обеспечение;

СПД сеть передачи данных;

BF Brute Force - алгоритм полного перебора;

В&В Branch and Bound - метод ветвей и границ;

ILEC Incumbent Local Exchange Carriers - уполномоченные региональными операторами связи, предоставляющие услуги Интернета в небольшом регионе;

NAP Network Access Point - центр обмен, в котором соединяются сети большого числа операторов;

ISP Internet Service Provider - поставщик услуг сети Интернет;

POP Points of Presents - точки присутствия, представляющие собой здания или помещения, в которых размещается оборудование доступа;

SA Simulated Annealing - алгоритм имитации отжига;

SPEA_M Strength Pareto Evolutionary Algorithm Modified - модифицированный эволюционный алгоритм поиска совокупности Парето, основанный на вычислении «силы»;

UML Unified Modeling Language - язык графического описания для объектного моделирования;

XML Extensible Markup Language - расширяемый язык разметки.