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

• Автор: Ермолаев, Сергей Юрьевич
• Шифр специальности: 05.12.13
• Научная степень: Кандидатская
• Год защиты: 2010
• Место защиты: Самара
• Количество страниц: 163 с. : ил.

ОГЛАВЛЕНИЕ
ВВЕДЕНИЕ
1. ЗАДАЧА СИНТЕЗА ТОПОЛОГИЧЕСКОЙ СТРУКТУРЫ
ПРИ СОЗДАНИИ СЕТЕЙ БЕСПРОВОДНОГО ДОСТУПА
1.1 Развитие беспроводных сетей передачи информации
1.2 Сети
1.2.1 Технология 1ЛГЕ и ее архитектура
1.2.2 Технология 11МВ и ее архитектура
1.2.3 Технология ViMAX и ее архитектура
1.2.3.1 Основные принципы архитектуры сети ViMAX
1.2.3.2 Варианты применения сетей ViMAX
1.2.3.3 Место ViMAX в иерархии структуры сетей ХСХ
1.2.3.4 Достоинства и недостатки
1.3 Этапы создания сети беспроводного доступа
1.3.1 Программный комплекс планирования сетей связи
1.4 Задача размещения базовых станций
1.4.1 Постановка модифицированной задачи размещения базовых станций
1.5 Выводы
2. СПОСОБЫ РЕШЕНИЯ ЗАДАЧ РАЗМЕЩЕНИЯ
2.1 Анализ способов решения задач размещения
2.2 Метод полного перебора
2.3 Метод ветвей и границ
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 Среда разработки ВоНапй Ое1рЫ
4.2 Реализация предложенных алгоритмов в среде
Вог1апй Ве1р1н 7.0
4.2.1 Интерфейс созданного программного обеспечения
4.3 Исследование алгоритмов на основе созданного программного обеспечения
4.3.1 Исследование метода полного перебора
4.3.2 Исследование генетического алгоритма
4.3.3 Исследование муравьиного алгоритма
4.4 Выводы
Заключение
Список используемой литературы
Приложение

СПИСОК СОКРАЩЕНИЙ
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) - Европейский институт телекоммуникационных стандартов

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