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

• Ермолаев, Сергей Юрьевич
• кандидат технических наук
• 2010

Оглавление диссертации кандидат технических наук Ермолаев, Сергей Юрьевич

ВВЕДЕНИЕ

1. ЗАДАЧА СИНТЕЗА ТОПОЛОГИЧЕСКОЙ СТРУКТУРЫ

ПРИ СОЗДАНИИ СЕТЕЙ БЕСПРОВОДНОГО ДОСТУПА

1.1 Развитие беспроводных сетей передачи информации

1.2 Сети

1.2.1 Технология ЬТЕ и ее архитектура

1.2.2 Технология 11МВ и ее архитектура

1.2.3 Технология \ViMAX и ее архитектура

1.2.3.1 Основные принципы архитектуры сети \ViMAX

1.2.3.2 Варианты применения сетей \ViMAX

1.2.3.3 Место \ViMAX в иерархии структуры сетей NGN

1.2.3.4 Достоинства и недостатки

1.3 Этапы создания сети беспроводного доступа

1.3.1 Программный комплекс планирования сетей связи

1.4 Задача размещения базовых станций 34 1.4.1 Постановка модифицированной задачи размещения базовых станций

1.5 Выводы

2. СПОСОБЫ РЕШЕНИЯ ЗАДАЧ РАЗМЕЩЕНИЯ

2.1 Анализ способов решения задач размещения

2.2 Метод полного перебора

2.3 Метод ветвей и границ 56 2.3.1 Метод ветвей и отсечений

2.4 Алгоритм поиска по соседству

2.4.1 Схема «обмена клиентами»

2.4.2 Схема «перемещение устройств обслуживания»

2.4.3 Структура алгоритма

2.5 Генетический алгоритм

2.6 Выводы

3. РЕШЕНИЕ ЗАДАЧИ ОПТИМАЛЬНОГО РАЗМЕЩЕНИЯ

НА ОСНОВЕ МУРАВЬИНЫХ АЛГОРИТМОВ ОПТИМИЗАЦИИ

3.1 История появления муравьиных алгоритмов оптимизации

3.2 Особенности искусственных муравьев

3.3 Характеристики муравьиных алгоритмов оптимизации

3.4 Обобщенная структура алгоритмов муравьиной оптимизации

3.5 Принципы функционирования муравьиных алгоритмов оптимизации

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

3.7 Выводы

4. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ И ИССЛЕДОВАНИЕ ПРЕДЛОЖЕННЫХ АЛГОРИТМОВ

4.1 Среда разработки Borland Delphi

4.2 Реализация предложенных алгоритмов в среде

Borland Delphi 7.

4.2.1 Интерфейс созданного программного обеспечения

4.3 Исследование алгоритмов на основе созданного программного обеспечения

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

4.3.2 Исследование генетического алгоритма

4.3.3 Исследование муравьиного алгоритма

4.4 Выводы 145 Заключение 147 Список используемой литературы 150 Приложение

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

1G, 2G, 3G, 4G — сети сотовой связи первого, второго, третьего, четвертого поколений

3GPP (The 3rd Generation Partnership Project) - партнерский проект ETSI, занимающийся стандартизацией в области сетей 3G

3GPP2 (The 3rd Generation Partnership Project 2) - параллельный проект партнерства ETSI по стандартизации сетей 3G

AES (Advanced Encryption Standard) - улучшенный стандарт шифрования AMPS (Advanced Mobile Phone Service) - улучшенное обслуживание для мобильной связи АР (Access Point) - точка доступа

API (Application Programming Interface) - интерфейс прикладного программирования

ARQ (Automatic Repeat Request) - механизм автоматического запроса повторной передачи

ASN (Access Service Network) - сервисная сеть доступа

CATV (Cable Television) - система кабельного телевидения •

CDMA (Code Division Multiple Access) - множественный доступ с кодовым

разделением каналов

CFLP (Capacity Facility Location Problem) - емкостная задача размещения устройств обслуживания

CSN (Connectivity Service Network) - сеть подключения

D-AMPS (Digital Advanced Mobile Phone Service) - улучшенное обслуживание для мобильной связи на основе цифровой обработки

ЕАР (Extensible Authentication Protocol) - расширенный протокол аутентификации

EDGE (Enhanced Data GSM Environment) - технология повышения скорости передачи данных в сети GSM/GPRS

ETSI (European Telecommunication Standard Institute) - Европейский институт телекоммуникационных стандартов

EV-DO (Evolution Data Only) - эволюционная технология передачи только данных

FDMA (Frequency Division Multiple Access) - множественный доступ с частотным разделением каналов

FTTx (Fiber То The .) — архитектура широкополосного доступа с использованием оптического волокна на участке от центральной станции до некоторой точки «х»

GPRS (General Packet Radio Service) - подсистема услуг пакетной передачи данных

GSM (Global System for Mobile Telecommunications) - глобальная система мобильной связи

HSDPA (High Speed Downlink Packet Access) - высокоскоростной пакетный доступ в линии «вниз»

HSUPA (High Speed Uplink Packet Access) - высокоскоростной пакетный доступ в линии «вверх» '

ISDN (Integrated Service Digital Network) - цифровая сеть с интеграцией служб IEEE (Institute of Electrical and Electronics Engineers) — институт инженеров по электротехнике и электронике

IMT-2000 (International Mobile Telecommunications 2000) - международная программа, проводящаяся под эгидой ITU IP (Internet Protocol) — протокол сети Интернет

IPTV (Internet Protocol Television) - технология передачи телевидения по IP-сети

ITU (International Telecommunications Union) — международный союз электросвязи

JDC (Japan Digital Cellular) - Японская цифровая сотовая связь

KPI (Key Performance Indicators) — ключевые индикаторы (параметры) качества функционирования сети сотовой связи

LTE (Long Term Evolution) — долгосрочная эволюция сетей сотовой связи MAC (Medium Access Control) — уровень управления доступом к среде передачи

MIMO (Multiple Input Multiple Out) - антенная технология, имеющая несколько входов и несколько выходов (по отношению к каналу)

MSAN (Multi Service Access Node) - мультисервисный узел доступа

MSCFLP (Multi Source Capacity Facility Location Problem) - емкостная задача размещения устройств обслуживания со множеством источников обслуживания

NGN (Next Generation Network) - сеть следующего поколения

NMT (Nordic Mobile Telephone) - Северная система мобильной телефонии

NP-hard (Nonpolynomial) - трудная задача, обладающая свойством отсутствия возможности решения за время, ограниченное полиномом некоторой степени

NTT (Nippon Telegraph & Telephone Corporation) - Японская корпорация по телеграфии и телефонии

OFDM (Orthogonal Frequency Division Multiplexing) — механизм модуляции посредством ортогональных несущих

OFDMA (Orthogonal Frequency Division Multiple Access) — множественный доступ посредством ортогональных несущих

PDC (Personal Digital Cellular) - персональная цифровая сотовая связь

PLC (Power Line Communication) - технология передачи данных по существующим электрическим линиям

PON (Passive Optical Network) - технология пассивных оптических сетей QoS (Quality of Service) - качество услуг связи

RTMS (Radio Telephone Mobile System) - радиотелефонная система мобильной связи

SAE (System Architecture Evolution) — эволюция архитектуры системы, архитектура сети LTE

SMS (Short Message Service) - услуга коротких сообщений

SSCFLP (Single Source Capacity Facility Location Problem) - емкостная задача размещения устройств обслуживания с одним источником обслуживания

SUI (Stanford University Interim) - канальная модель распространения сигналов, разработанная рабочей группой IEEE 802.16-2004 в университете Стэнфорда

TACS (Total Access Communications System) - система связи с общим доступом

TDMA (Time Division Multiple Access) - множественный доступ с временным разделением каналов

UFLP (Uncapacitated Facility Location Problem) - не емкостная задача размещения устройств обслуживания

UMB (Ultra Mobile Broadband) - технология сверх мобильной широкополосной связи

UMTS (Universal Mobile Telecommunications System) — универсальная система мобильной связи

VLAN (Virtual Local Area Network) - виртуальная локальная сеть VoD (Video on Demand) - передача видео данных по запросу

VoIP (Voice over Internet Protocol) - технология передачи голоса «поверх» IP

VSAT (Very Small Aperture Terminal) - технология спутниковой связи с очень малой апертурой

W-CDMA (Wideband Code Division Multiple Access) - стандарт сети радиодоступа сотовой связи с широкополосным CDMA

WiFi (Wireless Fidelity) - технология беспроводного доступа на базе стандарта IEEE802.il

WiMAX (Worldwide Interoperability for Microwave Access) - технология беспроводного широкополосного доступа на базе стандарта IEEE 802.16 WLAN (Wireless Local Area Network) - беспроводная локальная сеть xDSL (. .Digital Subscriber Link) - технология цифровой абонентской линии AC — абонентская станция БС — базовая станция

БШД - беспроводной широкополосный доступ МАО - муравьиные алгоритмы оптимизации МСЭ - международный союз электросвязи ПО - программное обеспечение РФ - Российская Федерация '

ТфОП - сеть телефонной связи общего пользования

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

Актуальность темы

Стремительное развитие беспроводных телекоммуникационных технологий в последние два десятилетия привело к непрерывной смене одних стандартов в области беспроводной связи другими. Так, например, в Российской Федерации лишь в последние несколько лет начали появляться сети сотовой связи третьего поколения (сети 3G), а уже мировыми проектными организациями, разработаны документы, определяющие основы нового стандарта - сети 4G. Анализ тенденций развития телекоммуникационной отрасли показывает, что сети 4G будут создаваться на основе следующих технологий: LTE, WiMAX. Одним из возможных вариантов построения вероятно будет сосуществование вышеназванных технологий, в зависимости от потребностей операторов связи. Сети беспроводной связи 4G предоставляют широкий спектр услуг широкополосного доступа: передача голоса, передача данных, Интернет, видео телефония, мобильное телевещание и др.

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

Характерной особенностью всех стандартов, разработанных в последние годы, является .ориентация на обеспечение требуемых показателей качества обслуживания QoS. Не исключением является и стандарт IEEE 802.16-2004, на который ориентировано представленное диссертационное исследование, -стандарт беспроводных сетей для организации фиксированного широкополосного доступа.

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

Среди публикаций, посвященных изучению методологии создания сетей IEEE 802.16-2004 и решению задач размещения базовых станций, следует отметить исследования Вишневского В.М., Ляхова А.И., Портного С.Л., Шахновича И.В., Широкова В. Также существуют исследования, ориентированные на решение общих задач размещения, среди которых можно выделить работы Кочетова Ю.А., Пащенко М.Г., Береснева В.Л. Среди зарубежных ученых, занимающихся исследованием вопросов размещения, можно выделить фамилии Murphy S., Amaldi Е., Capone A., Sridharan R., Klincewicz J.G., Barcelo J., Beasley J.E. Большинство публикаций, посвященных решению задач размещения, ориентируются на использование точных методов. При этом решаются задачи небольшой размерности, поскольку точные методы, обладающие экспоненциальной зависимостью времени работы от количества входных данных, теряют свою эффективность с увеличением размерности.

Объектом исследования являются беспроводные сети фиксированного широкополосного доступа, создаваемые операторами связи.

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

Цель работы и задачи исследования

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

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

- формулировка критериев задачи оптимизации, учитывающих потери сигналов при распространении;

- анализ существующих методов решения ЫР-трудных задач размещения;

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

- создание программного обеспечения для решения задач размещения любой размерности и конфигурации;

- проведение вычислительных экспериментов на основе созданного программного обеспечения.

Методы исследования

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

Достоверность результатов

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

Научная новизна

Научная новизна диссертационного исследования заключается в следующем:

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

- предложен алгоритм размещения базовых станций на основе генетического подхода;

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

Личный вклад .

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

Практическая ценность и реализация результатов работы

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

Полученные результаты и алгоритмы могут быть использованы научно-исследовательскими, проектными организациями и телекоммуникационными компаниями при проектировании и внедрении сетей стандарта "\У1МАХ.

Основные теоретические и практические результаты, полученные в диссертационном исследовании, использованы в ООО «Саха-Белком» и внедрены в учебный процесс ГОУВПО ПГУТИ, что подтверждено соответствующими актами.

Апробация работы

Основное содержание работы докладывалось и обсуждалось на XIV, XV и XVI Российской научно-технической конференции ПГУТИ (Самара, 2007г., 2008г. и 2009г.), на VIII Международной научно-технической конференции «Проблемы техники и технологий телекоммуникаций» (Уфа, 2007г.), на IX, X, XI и XII Международной конференции «Цифровая обработка сигналов и ее применение» (Москва, 2007г., 2008г., 2009г., 2010г.), IX Международной научно-технической конференции «Кибернетика и высокие технологии» (Воронеж, 2008г.).

Публикации

По теме диссертации опубликовано 16 работ, в том числе 2 работы из перечня, рекомендованного ВАК РФ для публикации результатов диссертационных исследований, 1 статья в журнале «Telecommunication Sciences» (Украина), 6 тезисов, 6 докладов в трудах международных научных конференций, а также 1 свидетельство о регистрации программы для ЭВМ.

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

- модифицированная постановка задачи размещения базовых станций;

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

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

- результаты сравнительного анализа предложенных алгоритмов размещения базовых станций.

Структура и объем работы

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

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

4.4 Выводы

В заключительной главе диссертации было описано программное обеспечение, созданное в среде Borland Delphi 7.0 и предназначенное для решения задач размещения базовых станций различной размерности. Представленное программное обеспечение не является полноценным программным комплексом по планированию и оптимизации беспроводных сетей. Его можно рассматривать в качестве дополнительного модуля к программному комплексу. Тем не менее, оно позволяет вычислять конфигурацию беспроводной широкополосной сети, выдавая в качестве итогового результата матрицы размещения базовых станций на местах кандидатах, и матрицы подключения клиентов к базовым станциям. Также программа рассчитывает минимальную суммарную стоимость полученной конфигурации. В программе присутствуют три различных по структуре способа решения задачи размещения базовых станций: полный перебор, генетический алгоритм, муравьиный алгоритм. Было проведено исследование реализованных алгоритмов на задачах различной размерности. Подводя итоги проведенных компьютерных экспериментов, необходимо отметить следующие моменты:

1. Эвристические методы затрачивают гораздо меньше времени на нахождение решения, в отличие от точных методов.

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

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

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

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

ЗАКЛЮЧЕНИЕ

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

В результате анализа доступных работ по данной тематике выявлены их общие моменты и определены ключевые недостатки. Во-первых имеется недостаток работ, посвященных задачам размещения базовых станций в сетях IEEE 802.16-2004. Во-вторых, в имеющихся исследованиях при постановке задачи отсутствует учет потерь сигналов при распространении в радиоканале, что не соответствует реальным процессам при передаче информации между базовыми и абонентскими станциями. Поэтому в диссертации сформулирована модифицированная постановка задачи, учитывающая потери сигналов в радиоканале. Также показано, что существующие работы по решению задач размещения в основном используют точные методы решения, обладающие экспоненциальной зависимостью времени работы от количества входных данных, т.е. размерности задачи. К тому же задача оптимального размещения базовых станций является NP-трудной. Наличие указанных обстоятельств привело к тому, что было принято решение отказаться от использования точных методов и перейти к эвристическим, которые являются приближенными методами и обеспечивают получение оптимальных (субоптимальных) результатов за приемлемое время.

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

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

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

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

В целом по итогам работы можно сформулировать следующие основные полученные результаты:

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

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

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

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

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

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

Список литературы диссертационного исследования кандидат технических наук Ермолаев, Сергей Юрьевич, 2010 год

1. Вишневский, В. Технология сотовой связи LTE почти 4G / В. Вишневский, А. Красилов, И. Шахнович // Первая миля. - 2009. - № 2. - С. 2-13.

2. IEEE 802.16 первый стандарт мобильной связи 4G / По материалам «Huawei Technologies Communicate» // Век качества. - 2008. - № 6. - С. 50-52.

3. Абилов, A.B. Сети сотовой связи. Учебное пособие / A.B. Абилов. Ижевск: ИжГТУ, 2000.-20 е.: ил.

4. Громаков, Ю.А. Стандарты и системы подвижной радиосвязи / Ю.А. Громаков. М.: Эко-Трендз, 1997. - 239 с.

5. Бабков, В.Ю. Системы мобильной связи / В.Ю. Бабков, М.А. Вознюк, В.И. Дмитриев. С.-Пб.: С.-ПБ ГУТ, 1999. - 330 с.

6. Волков, Л.Н. Системы цифровой радиосвязи: базовые методы и характеристики / Л.Н. Волков, М.С. Немировский, Ю.С. Шинаков. М.: Эко-Трендз, 2005. - 392 е.: ил.

7. Бабков, В.Ю. Системы связи с кодовым разделением каналов / В.Ю. Бабков, М.А. Вознюк, А.Н. Никитин, М.А. Сивере. С.-Пб.: С.-ПБ ГУТ, 1999. - 120 с.

8. Тихвинский, В. О. Управление и качество услуг в сетях GPRS/UMTS / В.О, Тихвинский, С. В. Терентьев. М.: Эко-Трендз, 2007. - 400 с.

9. Тихвинский, В.О. Сети подвижной связи третьего поколения: экономические и технические аспекты развития в России / В.О. Тихвинский. М.: Радио и связь, 2004.-312 с.

10. Тихвинский, В.О. Подвижная связь третьего поколения: Экономика и качество услуг / В.О. Тихвинский, Е.Е. Володина. М.: Радио и связь, Горячая линия - Телеком, 2005. - 240 с.

11. Кааранен, X. Сети UMTS. Архитектура, мобильность, сервисы / X. Кааранен, А. Ахтиайнен, Л. Лаитинен. М.: Техносфера, 2007. - 464 с.

12. Парфенов, Б.А. Нас ждет решающий год / Б.А. Парфенов // Вестник связи. -2008.-№ 1.-С. 38-41.

13. IEEE Std 802.16-2004. IEEE Standard for Local and metropolitan area networks. Part 16: Air Interface for Fixed Broadband Wireless Access Systems. IEEE, 1 October 2004.

14. Шахнович, И. Стандарт широкополосного доступа IEEE 802.16 для диапазонов ниже 11 ГГц / И. Шахнович // ЭЛЕКТРОПИКА: НТБ. 2005. - № 1. -С. 8-14.

15. Шахнович, И. Стандарт широкополосного доступа IEEE 802.16-2004. Режим OFDMA и адаптивные антенные системы / И. Шахнович // ЭЛЕКТРОНИКА: НТБ. 2005. - № 2. - С. 46-52.

16. Кучерявый, Е.А. Сети WiMAX, их характеристики и перспективы внедрения Электронный документ. / Е.А. Кучерявый, Д.А. Молчанов. Режим доступа: http://www.multiinfocom.ru/ru/artpdf/setiwimaxchar.pdf. - 10.12.2006.

17. Шахнович, И. Широкополосная мобильность: IEEE 802.1 бе. Часть 1: МАС-уровень / И. Шахнович // ЭЛЕКТРОНИКА: НТБ. 2007. - № 2. - С. 18-27.

18. Шахнович, И. Широкополосная мобильность: IEEE 802.1 бе. Часть 2: Физический уровень и элементная база / И. Шахнович // ЭЛЕКТРОНИКА: НТБ. -2008. -№ 1.-С. 98-104.

19. Шахнович, И. Архитектура сети WiMAX: основные элементы и принципы / И. Шахнович // Первая миля. 2009. - № 1. - С. 6-15.

20. Осипов, И.Е. Mesh-сети: технологии, приложения, оборудование / И.Е. Осипов // Технологии и средства связи. 2006. - № 4. - С. 38-45.

21. Бакланов, И.Г. NGN: принципы построения и организации / И.Г. Бакланов. -М.: Эко-Трендз, 2008. 400 с.

22. Вишневский, В. Системы поллинга: теория и применение в широкополосных беспроводных сетях / В. Вишневский, О. Семенова. М.: Техносфера, 2007. - 312 с.

23. Свердлов, Д. «Скартел» начинает с Yota / Д. Свердлов // Connect! Мир связи.-2008.-№ 10.-С. 68.

24. Широков, В. Методология создания беспроводных мультисервисных сетей класса WiMAX / В. Широков // Технологии и средства связи. 2010. - № 1. - С. 32-33.

25. Вишневский, В.М. Широкополосные беспроводные сети передачи информации / В.М. Вишневский, А.И. Ляхов, И.В. Шахнович, C.JI. Портной. -М.: Техносфера, 2005. 456 с.

26. Зыбин, В.А. Исследование новых возможностей использования технологии WiMAX / В.А. Зыбин, В.В. Крылов // Труды научной конференции по радиофизике. Нижний Новгород, 2006. - С. 66-67.

27. Иванов, А. Оборудование WiMAX решение компании Alvarion / А. Иванов, С. Портной // Первая миля. - 2009. - № 2. - С. 32-39.

28. Erceg, V. Channel models for fixed wireless applications / V. Erceg, K.V.S Hari, et al. // Tech. Rep. IEEE 802.16a-03/01, June 2003.

29. Бузов, A.JI. Управление радиочастотным спектром и электромагнитная совместимость радиосистем. Учебн. пособие / A.JI. Бузов, М.А. Быховский, Н.В. Васехо и др. Под ред. д.т.н., проф. М.А. Быховского. М.: Эко-Трендз, 2006.-376 е.: илл.

30. Lenstra, J.K. Complexity of scheduling under precedence constraints / J.K. Lenstra, K.A.H.G. Rinnooy // Operations Research. 1978. - № 26. - P. 22-35.

31. Neebe, A.W. An algorithm for the fixed-charge assigning users to sources problem / A.W. Neebe, M.R. Rao // Journal of the Operational Research Society.1983.-№34.-P. 1107-1113.

32. Barcelo, J. A heuristic Lagrangean algorithm for the capacitated plant location problem / J. Barcelo, J. Casanovas // European Journal of Operational Research.1984.-№ 15.-P. 212-226.

33. Klincewicz, J.G. A Lagrangean relaxation heuristic for capacitated facility location with single-source constraints / J.G. Klincewicz, H. Luss // Journal of the Operational Research Society. 1986. - № 37. - P. 495-500.

34. Erlenkotter, D. A dual-based procedure for uncapacitated facility location / D. Erlenkotter // Operations Research. 1978. - № 26. - P. 992-1009.

35. Sridharan, R. A Lagrangian heuristic for the capacitated plant location problem with single source constraints / R. Sridharan // European Journal of Operational Research. 1991, - № 66. - P. 305-312.

36. Pirkul, H. Efficient algorithm for the capacitated concentrator location problem / H. Pirkul // Computers & Operations Research. 1987. - № 14. - P. 197-208.

37. Beasley, J.E. Lagrangian heuristics for location problems / J.E. Beasley // European Journal of Operational Research. 1993. - № 65. - P. 383-399.

38. Сухарев, А.Г. Курс методов оптимизации: учеб. пособие / А.Г. Сухарев, А.В. Тимохов, В.В. Федоров. 2-е изд. - М.:ФИЗМАТЛИТ, 2005. - 368 с.

39. Шор, Н.З. О скорости сходимости метода обобщенного градиентного спуска с растяжением пространства / Н.З. Шор // Кибернетика. 1970. - № 2. - С. 8085.

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

41. Береснев, В.JI. Алгоритм неявного перебора для задачи типа размещения и стандартизации / B.JI. Береснев // Управляемые системы. Новосибирск, Институт математики Сиб.отд. АН СССР. Вып. 12. - С. 24-34.

42. Кочетов, Ю.А. Лагранжевы релаксации в задаче выбора оптимального состава системы технических средств / Ю.А. Кочетов, М.Г. Пащенко // Управляемые системы. ИМ СО РАН, 1993. - вып.31. - С. 26-39.

43. Береснев, В.Л. Дискретные задачи размещения и полиномы от булевых переменных / В.Л. Береснев. Новосибирск: Изд-во Инст. математики, 2005. — 408 с.

44. Görtz, S. A subgradient-based branch-and-bound algorithm for the capacitated facility location problem Электронный документ. / S. Görtz, A. Klose. Режим доступа: http://www.imf.au.dk/publications/wp/2009/imf-wp-2009-01 .pdf. -6.10.2009.

45. Bockmayr, A. Pseudo-Boolean and finite domain constraint programming: a case study Электронный документ. / A. Bockmayr, T. Kasper // Режим доступа: http://www.princeton.edu/~chaff/papers/pseudo-boolean-and-finite.pdf. - 7.02.2006.

46. Holland, J.H. Adaptation in natural and artificial systems / J.H. Holland. Ann Arbor: University of Michigan Press, 1992. - 228 pp.

47. Рутковский Л. Нейронные сети, генетические алгоритмы и нечеткие системы: Пер. с польск. И.Д. Рудинского / Л. Рутковский, Д. Рутковская, М. Пилиньский. — М.: Горячая линия Телеком, 2006. — 383 е.: ил.

48. Freisleben, В. Genetic local search algorithm for solving symmetric and asymmetric traveling salesman problems / B. Freisleben, P. Merz // Proceedings of IEEE International Conference on Evolutionary Computation, 1996, IEEE Press, pp. 616-621.

49. Батищев, Д.И. Генетические алгоритмы решения экстремальных задач. Учебное пособие / Д.И. Батищев. Воронеж: ВГТУ, 1995. - 69 с.

50. Слюсар, В.И. Синтез антенн на основе генетических алгоритмов. Часть 1 / В .И. Слюсар // Первая миля. 2008. - № 6. - С. 16-23.

51. Слюсар, В.И. Синтез антенн на основе генетических алгоритмов. Часть 2 / В.И. Слюсар // Первая миля. 2009. - № 1. - С. 22-25.

52. Лютиков, Б.Г. Модифицированный генетический алгоритм выбора конфигурации оборудования проектируемой телекоммуникационной сети /Б.Г. Лютиков, Д.В. Морозов, В.П. Морозов // Телекоммуникации. 2008. - № 5. - С. 10-12.

53. Бугров, Д.А. Применение эволюционного метода для оптимизации магистральной сети связи / Д.А. Бугров, Н.Л. Сторожук // Электросвязь. 2007. -№ 5. - С. 30-33.

54. Курейчик, В.В. Эволюционные, синергетические и гомеостатические методы принятия решений / В.В. Курейчик. Таганрог: Изд-во ТРТУ, 2001. -221 с.

55. Курейчик, В.М. Генетические алгоритмы и их применение / В.М. Курейчик. Таганрог: Изд-во ТРТУ, 2002. - 242 с.

56. Курейчик, В.М. Генетические алгоритмы. Учебное пособие / В.М. Курейчик, В.В. Курейчик, Л.А. Гладков. М.: Физматлит, 2006. - 320 с.

57. Алексеева, Е.В. Алгоритмы локального поиска для задачи о р-медиане с предпочтениями клиентов: автореф. дис. . канд. физ-мат. наук: 01.01.09: защищена 24.10.2007 / Е.В. Алексеева, Ин-т мат. им. С. Л. Соболева СО РАН. -Новосибирск, 2007. 19 с.

58. Кочетов, Ю.А. Методы локального поиска для дискретных задач размещения: автореф. дис. . д-ра физ-мат. наук: 05.13.18: защищена1901.2010 / Ю.А. Кочетов, Ин-т. выч. матем-ки и матем-ой геофизики СО РАН. Новосибирск, 2009. - 30 с.

59. Федорова, М.А. Вычислительные и эволюционные методы в стохастических системах с обнаружением и адаптацией: автореф. дис. . канд. физ-мат. наук: 01.01.09: защищена 07.11.2007 / М.А. Федорова, Ул. гос. ун-т. Ульяновск, 2007.-23 с.

60. Cortinhal, M.J. Genetic algorithms for the single source capacitated location problem: a computational study / M.J. Cortinhal, M.E. Captivo // 4th Metaheuristics International Conference. Porto, Portugal. 2001. - P. 355-359.

61. Ярушкина, Н.Г. Эффективность генетических алгоритмов для задач автоматизированного проектирования / Н.Г. Ярушкина, A.M. Наместников // Известия РАН. Теория и системы управления. 2002. - № 2. - С. 127-134.

62. Ермолаев, С.Ю. Оптимальное размещение базовых станций / С.Ю. Ермолаев // Telecommunication Sciences. 2010. - T. 1, №1. - С. 82-90.

63. Корнеенко, В.П. Методы оптимизации / В.П. Корнеенко. М.: Высшая школа, 2007. - 664 е.: ил.

64. Dorigo, M. Optimization, learning and natural algorithms (in italian) / M. Dorigo // Ph.D. dissertation, Dipartimento di Elettronica, Politécnico di Milano, Italy. -1992.-P. 140.

65. Deneubourg, J.-L. The self-organizing exploratory pattern of the Argentine ant / J.-L. Deneubourg, S. Aron, S. Goss, J.M. Pasteels // Journal of Insect Behavior. -Vol. 3.-1990.-P. 159.

66. Goss, S. Self-organized shortcuts in the Argentine ant / S. Goss, S. Aron, J.-L. Deneubourg, J.M. Pasteels // Naturwissenschaften. vol. 76. - 1989. - P. 579-581.

67. Pasteels, J.M. Self-organization mechanisms in ant societies (i): Trail recruitment to newly discovered food sources / J.M. Pasteels, J.-L. Deneubourg, S. Goss // Experientia Supplementum. Yol. 54. - 1987. - P. 155.

68. Dorigo, M. Ant System: Optimization by a colony of cooperating agents / M. Dorigo, V. Maniezzo, A. Colorni // IEEE Transactions on Systems, Man, and Cybernetics Part B. - Vol. 26, № 1. - 1996. - P. 29-41.

69. Dorigo, M. Ant colonies for the traveling salesman problem / M. Dorigo, L.M. Gambardella // BioSystems. Vol. 43, № 2. - 1997. - P. 73-81.

70. Dorigo, M. Ant Colony System: A cooperative learning approach to the traveling salesman problem / M. Dorigo, L.M. Gambardella // IEEE Transactions on Evolutionary Computation. Vol. 1, № 1. - 1997. - P. 53-66.

71. Stutzle, T. MAX-MIN Ant System / T. Stutzle, H.H. Hoos // Future Generation Computer Systems. Vol. 16, № 8. - 2000. - P. 889-914.

72. Bullnheimer, B. A new rank-based version of the Ant System: A computational study / B. Bullnheimer, R.F. Hartl, C. Strauss // Central European Journal for Operations Research and Economics. Vol. 7, № 1. - 1999. - P. 25-38.

73. Maniezzo, V. Exact and approximate nondeterministic tree-search procedures for the quadratic assignment problem / V. Maniezzo // INFORMS Journal on Computing. Vol. 11, № 4. - 1999. - P. 358-369.

74. Blum, C. The hyper-cube framework for ant colony optimization / C. Blum, M. Dorigo // IEEE Transactions on Systems, Man, and Cybernetics Part B. - Vol. 34, №2.-2004.-P. 1161-1172.

75. Dorigo, M. Ant algorithms for discrete optimization / M. Dorigo, G. Di Caro, L.M. Gambardella // Artificial Life. Vol. 5, № 2. - 1999. - P. 137-172.

76. Dorigo, M. The Ant Colony Optimization meta heuristic / M. Dorigo, G. Di Caro // New Ideas in Optimization, D. Corne et al., Eds. McGraw Hill, London, UK. -1999.-P. 11-32.

77. Gambardella, L.M. Ant Colony System hybridized with a new local search for the sequential ordering problem / L.M. Gambardella, M. Dorigo // INFORMS Journal on Computing. Vol. 12, № 3. -2000. - P. 237-255.

78. Manfrin, M. Parallel ant colony optimization for the traveling salesman problem I M. Manfrin, M. Birattari, T. Stutzle, M. Dorigo // In Proceedings of ANTS 2006, ser. LNCS, M. Dorigo et al., Eds., vol. 4150. Springer Verlag. 2006. - P. 224-234.

79. Gutjahr, W.J. A graph-based ant system and its convergence / W.J. Gutjahr // Future Generation Computer Systems. Vol. 16, № 9. - 2000. - P. 873-888.

80. Zlochin, M. Model-based search for combinatorial optimization: A critical survey / M. Zlochin, M. Birattari, N. Meuleau, M. Dorigo // Annals of Operations Research. -Vol. 131, № 1-4.-2004.-P. 373-395.

81. Dorigo, M. Ant colony optimization artificial ants as a computational intelligence technique // M. Dorigo, M. Birattari, T. Stutzle // IEEE Computational Intelligence Magazine. - Vol. 1, № 4. - 2006. - P. 28-39.

82. Dorigo, M. An introduction to ant colony optimization Электронный документ. / M. Dorigo, К. Socha. Режим доступа: http://iridia.ulb.ac.beAridiaTrSeries/IridiaTr2006-01 ОгООЗ .pdf. -17.10.2008.

83. Fiechter, C.N. Efficient reinforcement learning / C.N. Fiechter // In Proceedings of the Seventh Annual ACM Conference on Computational Learning Theory (COLT 1994), New Brunswick, NJ. 1994. - P. 88-9.7.

84. Gambardella, L.M. MACS-VRPTW: A multiple ant colony system for vehiclerouting problems with time windows / L.M. Gambardella, E.D. Taillard, G. Agazzi //i

85. New Ideas in Optimization, D. Corne et al., Eds. McGraw Hill, London, UK. -1999.-P. 63-76.

86. Merkle, D. Ant colony optimization for resource-constrained project scheduling / D. Merkle, M. Middendorf, H. Schmeck // IEEE Transactions on Evolutionary Computation. Vol. 6, № 4. - 2002. - P. 333-346.

87. De Campos, L.M. Ant colony optimization for learning Bayesian networks / L.M. de Campos, J.M. Fernandez-Luna, J.A. Gamez, J.M. Puerta // International Journal of Approximate Reasoning. Vol. 31, № 3. - 2002. - P. 291-311.

88. Montemanni, R. Ant colony system for a dynamic vehicle routing problem / R. Montemanni, L.M. Gambardella, A.E. Rizzoli, A.V. Donati // Journal of Combinatorial Optimization. Vol. 10. - 2005. - P. 327-343.

89. Штовба, С.Д. Муравьиные алгоритмы: теория и применение / С.Д. Штовба // Программирование. 2005. - №4. - С. 1-16.

90. Shmygelska A. An ant colony optimisation algorithm for the 2d and 3d hydrophobic polar protein folding problem Электронный документ. / A. Shmygelska, H.H. Hoos. Режим доступа: http://www.ncbi.nlm.nih.gov/pmc/articles/PMC555464 - 14.12.2009.

91. Dorigo, M. Evolving self-organizing behaviors for a Swarm-bot / M. Dorigo, V. Trianni, E. Sahin // Autonomous Robots. Vol. 17, № 2-3. - 2004. - P. 223-245.

92. Di Caro, G. AntNet: Distributed stigmergetic control for communications networks / G. Di Caro, M. Dorigo // Journal of Artificial Intelligence Research. Vol. 9.- 1998.-P. 317-365.

93. Соболь, И.М. Метод Монте-Карло / И.М. Соболь. M.: Наука. Главная редакция физико-математической литературы, 1985. - 80 с.

94. Бакнелл, Д.М. Фундаментальные алгоритмы и структуры данных в Delphi: Пер. с англ. / Д.М. Бакнелл. СПб.: ООО «ДиаСофтЮП», 2003. - 560 с.

95. Сухарев, М.В. Основы Delphi. Профессиональный подход / М.В. Сухарев. СПб.: Наука и техника, 2004. - 600 с.

96. Ермолаев, С.Ю. Свидетельство о государственной регистрации программы для ЭВМ. Конфигуратор оптимальной топологии для беспроводной сети стандарта IEEE 802.16-2004 / С.Ю. Ермолаев, Т.С. Шестакова. № 2010616639 от 6.10.2010.-1 с.