Содержание к диссертации
Введение
1 Современное состояние проблемы планирования сетей UMTS 14
1.1 Предпосылки создания и стандартизация UMTS 14
1.2 Анализ процесса планирования радиоподсистемы UTRAN 16
1.2.1 Структурная схема и состав оборудования сети UMTS 17
1.2.2 Структура каналов и кадров 20
1.2.3 Характеристика транспортных и физических каналов UTRAN 22
1.2.3.1 Каналы синхронизации (P-SCH, S-SCH) 23
1.2.3.2 Общий пилот-канал (CPICH) 24
1.2.3.3 Широковещательный канал (ВСН) 26
1.2.3.4 Канал случайного доступа (RACH) 26
1.2.3.5 Прямой канал доступа (FACH) 26
1.2.3.6 Канал вызова (РСН) 27
1.2.3.7 Выделенный транспортный канал (DCH) 27
1.2.3.8 Совмещенный прямой канал (DSCH) 28
1.2.3.9 Общий восходящий пакетный канал (СРСН) 28
1.2.4 Анализ процедур физического уровня 29
1.2.4.1 Процедура поиска ячейки 29
1.2.4.2 Процедуры управления мощностью 30
1.2.4.3 Процедуры хэндовера 31
1.2.5 Сравнение ключевых параметров UMTS и GSM технологий 32
1.3 Применение репитеров в сетях GSM и UMTS 35
1.3.1 Принцип работы и классификация репитеров GSM 36
1.3.1.1 Широкополосные репитеры 37
1.3.1.2 Канальные репитеры 39
1.3.1.3 Репитеры с переносом частоты 40
1.3.1.4 Переключаемые репитеры 43
1.3.2 Применение репитеров в системе UMTS 45
1.3.2.1 Расчет емкости и уровня шумов Node В в сети без репитеров.. 46
1.3.2.2 Расчет емкости и уровня шумов Node В в сети с репитерами... 49 1.4 Постановка задач исследования 54
1.4.1 Задача оптимизации площадей зон Soft/Softer handover 55
1.4.2 Задача баланса трафика между ячейками сети 56
1.4.3 Формализация задачи исследования. 56
Теоретические основы исследования 59
2.1 Общая характеристика методов оптимизации 59
2.2 Характеристика эвристических методов оптимизации 68
2.2.1 Метод имитации отжига (Simulated Annealing, SA) 68
2.2.2 Генетический метод 72
2.2.2.1 Введение 72
2.2.2.2 Формализация генетического метода 74
2.2.2.3 Оператор воспроизводства GA 77
2.2.2.4 Оператор кроссинговера GA .81
2.2.2.5 Оператор мутации GA 84
2.2.2.6 Примеры использования и оценка эффективности GA 87
2.2.3 Метод DIRECT (Dividing RECTangles) 92
2.2.3.1 Оптимизация Липшица 92
2.2.3.2 Инициализация DIRECT метода 94
2.2.3.3 Определение потенциально оптимальных прямоугольников... 95
2.2.3.4 Разделение потенциально оптимальных прямоугольников. 97
2.3 Определение ключевых параметров оптимизации сети UMTS 100
2.3.1 Угол наклона и азимут антенны 100
2.3.2 Мощность общего пилот-канала (CPICH) 101
2.3.3 Определение взаимосвязи между значениями TILT и CPICH 102
2.3.4 Расчет оптимальных значений CPICH мощности для различных углов наклона антенн 105
2.3.5 Определение целевой функции 107
2.3.6 Критерии эффективности методов оптимизации 108
2.3.6.1 Число обслуживаемых мобильных терминалов 108
2.3.6.2 Уровень загрузки ячеек сети 108
2.3.6.3 Показатель оптимальности по SHO 109
2.3.7 Выводы ПО
2.4 Схема имитационной модели в среде MATLAB 110
2.4.1 Статический метод планирования сети 111
2.4.2 Значения параметров среды моделирования 112
2.4.3 Интерфейсы используемого программного обеспечения 113
2.4.4 Характеристика сценария моделирования 115
3 Применение эвристических методов оптимизации для планирования сети UMTS 116
3.1 Постановка задачи 116
3.1.1 Правила управления параметрами радиоподсистемы 117
3.2 Применение метода случайного поиска 120
3.3 Применение метода экспертной оценки 121
3.3 Применение генетического метода 123
3.3.1 Характеристика параметров генетического алгоритма 124
3.3.1.1 Представление данных в генах 124
3.3.1.2 Определение процедуры выбора 125
3.3.1.3 Определение процедуры кроссовера 125
3.3.1.4 Определение процедуры мутации 126
3.3.2.1 Правило 1 - изменение значений угла наклона антенн и значений мощности пилот-каналов ячеек сети 127
3.3.2.3 Правило 2 — изменение только мощности пилот-канала 130
3.3.2.4 Правило 3 — мощность пилот-канала как функция от угла наклона антенны 132
3.4 Применение метода имитации отжига 135
3.4.1 Результаты оптимизации для закона «медленного охлаждения». 136
3.4.2 Результаты оптимизации для закона «геометрического охлаждения» 140
3.4.3 Выводы 142
3.5 Применение DIRECT метода 143
3.7 Выводы 145
4 Обсуждение полученных результатов 146
4.1 Анализ результатов при использовании методов случайного поиска и экспертной оценки 146
4.2 Анализ результатов при использовании генетического алгоритма 151
4.3 Анализ результатов при использовании метода имитации отжига 155
4.4 Общий анализ эффективности применяемых алгоритмов 158
4.5 Выводы 167
Заключение 168
Список использованной литературы
- Анализ процесса планирования радиоподсистемы UTRAN
- Характеристика эвристических методов оптимизации
- Правила управления параметрами радиоподсистемы
- Анализ результатов при использовании генетического алгоритма
Введение к работе
Наблюдающееся в настоящее время бурное развитие отрасли мобильной связи, наряду с другими тенденциями, характеризуется быстро расширяющимся спектром новых услуг и технологий. Универсальная Система Мобильной Связи (UMTS) создавалась с целью предоставления абоненту широкого спектра дополнительных услуг таких как видеоконференции по мобильному телефону, доступ в Интернет, услуг связанных с определением местоположения пользователя.
Однако в связи с использованием в UMTS нового типа радиоинтерфейса (WCDMA1) возникает ряд технических проблем. Причина этого заключается в необходимости учета множества особенностей, не рассматривавшихся в сетях GSM. К таким особенностям относится смешанный тип трафика с различной скоростью передачи данных, несимметричная загрузка прямого и обратного каналов, разные требования к качеству для различных услуг.
Настоящая диссертация в основном сфокусирована на решении задач планирования и оптимизации сети, которые актуальны в первую очередь с практической точки зрения. Например, задача увеличения емкости сети путем планирования параметров радиоподсистемы, задача баланса нагрузки в прямом и обратном каналах, задача планирования значений мощности пилот-канала ячеек сети, задача планирования транспортной сети UMTS с учетом существующей структуры транспортной сети для GSM.
Таким образом, в настоящее время существует актуальная научно-техническая проблема разработки и совершенствования методов планирования и оптимизации параметров радиоподсистемы сети сотовой связи третьего поколения UMTS.
1 WCDMA — Широкополосный многостанционный доступ с кодовым разделением каналов (Wideband Code Division Multiple Access)
7 Состояние вопроса
Проблема планирования параметров радиоподсистемы сети UMTS стала особенно актуальной начиная с 2000 года, после запуска сетей 3G в Европе. Исследования в этой области проводятся в основном в Скандинавских странах и Великобритании. Вопросы поиска оптимальной топологии сети третьего поколения (места размещения площадок, конфигурация базовых станций) рассматривались в работах Andreas Eisenblatter, Armin Fugenschuh, Alexander Martin, Pete Moulton, Jonathan P. Castro [18, 19,38,70].
В качестве наиболее полного обобщения теоретических и практических основ основ планирования UMTS следует отметить книгу Laiho J., Wacker А. and Novosad, Т. eds., Radio Network Planning and Optimization for UMTS, John Wiley & Sons, Ltd., 2002.
Задача планирования оптимальной архитектуры транспортной сети UMTS рассмотрена в работах Janos Harmatos, Aron Szentesi [53,54].
Решение проблемы баланса трафика в ячейках сети UMTS путем адаптивной настройки мощности общего пилот-канала (CPICH) было предложено в [98]. При обычном методе расчета значений мощности CPICH и угла наклона антенн с помощью программного обеспечения пусть даже с очень точной моделью расчета зон покрытия, в любом случае будет использоваться статическая карта распределения абонентской нагрузки. Т.е. ситуаций неравномерной загрузки ячеек в определенный момент времени избежать не удастся. Динамическое изменение CPICH мощности и подстройка порогового уровня шума в ячейке NoiseRaise делает сеть адаптивной к любому распределению трафика.
Таким образом, обзор результатов новых исследований в данной области показывает, что они могут быть сгруппированы по следующим основным направлениям:
8 Задача увеличения емкости сети путем оптимизации параметров радиоподсистемы (значение мощности пилот-канала CPICH, угол наклона антенн TILT, допустимый уровень шума в обратном канале - параметр NoiseRaise).
Задача оптимизации площадей зон мягкого/полумягкого хэндовера fSoft/Softer Handover Overhead. SHO У Известно, что в сети UMTS соединение абонента может осуществляться через несколько ячеек сети одновременно, что называется мягким (soft) хэндовером, в том случае если ячейки принадлежат разным базовым станциям и полумягким (softer), если ячейки принадлежат одной базовой станции (Node В). Если мобильный терминал находится в области SHO, то происходит занятие радиоканалов одновременно у нескольких базовых станций, что приводит к неэффективному использованию радиоресурса. В то же время исключить зоны SHO полностью нельзя, так как в этом случае будет потеряна непрерывность соединения внутри сети. Более того, при нахождении мобильного терминала в мягком/полумягком хэндовере появляется выигрыш, связанный с пространственным разнесением антенн в обратном канале связи (macro diversity), что приводит к снижению интерференции в сети. Таким образом, задача оптимизации площадей зон SHO заключается в определении таких параметров радиоподсистемы (в основном это значения мощности CPICH и углов наклона антенн ячеек сети), при которых наблюдается оптимальное значение SHO. Из литературы известно оптимальное значение площадей зон SHO для сети построенной на основе 3-х секторных базовых станциий, которое составляет около 35%, что также согласуется с практикой [66]. Идеальной считается ситуация, когда в ячейке 65% мобильных терминалов осуществляют соединение с сетью по радиоканалам только этой ячейки. Остальные 35% мобильных терминалов данной ячейки находятся в
9 мягком/полумягком хэндовере, когда соедиение с сетью осуществляется более чем через одну ячейку сети. Задача баланса трафика между ячейками сети UMTS. В отличие от сети GSM, где площадь обслуживания и емкость ячейки находятся в слабой зависимости, в UMTS, при увеличении трафика в ячейке происходит уменьшение ее зоны обслуживания, что в конечном счете приводит к появлению необслуживаемых зон. Для избежания ситуации перегрузки одних ячеек и слабой загрузки других ячеек необходимо определять параметры CPICH мощности и допустимого уровня шума в обратном канале (NoiseRaise) индивидуально для каждой ячейки. Цель диссертационной работы заключается в разработке методов повышения эффективности построения и функционирования системы подвижной связи третьего поколения UMTS путем использования эвристических методов оптимизации применительно к планированию параметров радиоподсистемы сети UMTS. Для достижения поставленной цели в диссертации поставлены следующие научные задачи: Задачи исследования
Провести исследование эвристических методов оптимизации: генетического метода, метода имитации отжига, метода разделения на прямоугольники с целью изучения возможности их использования для определения оптимальных параметров радиоподсистемы сети UMTS.
Сформулировать и обосновать критерий оптимизации радиоподсистемы сети UMTS.
Сформулировать и обосновать правила управления параметрами радиоподсистемы сети UMTS.
Провести исследование изменения емкости сети UMTS при использовании ретрансляторов сигнала (репитеров).
Разработать программное обеспечение в среде MATLAB, позволяющее произвести оценку предлагаемых методов оптимизации.
10 Методы исследования
В настоящей диссертационной работе использован математический аппарат эвристических методов оптимизации таких как генетический метод, метод имитации отжига, метод разделения на прямоугольники (DIRECT). Значительная часть результатов работы была получена с использованием вычислительных алгоритмов, реализованных на компьютере в среде Matlab. Источники информации
Для достижения цели диссертации был использован широкий спектр источников, таких как книги, статьи IEEE, информация из проекта "Momentum", финансируемого Siemens, Ericsson и Vodafone в Германии, который посвящен, вопросам оптимизации радио подсистемы сетей UMTS [18, 19, 38]. Также в диссертации была использована информация о реальных проблемах стоящих перед отделом планирования сети 3G/UMTS, полученная в результате гранта Британского Совета и стажировки автора в компании Vodafone в Великобритании в 2004 году. Научная новизна
Предложено и обосновано использование методов оптимизации таких как генетического метода, метода имитации отжига, метода разделения на прямоугольники применительно к решению задачи определения параметров радиоподсистемы с целью увеличения емкости сети UMTS;
Получены расчетные формулы для численной оценки снижения емкости базовой станции UMTS в зависимости от количества подключенных к ней репитеров.
Практическая ценность
1. Обоснованные в диссертационной работе подходы, модели и
разработанные алгоритмы обеспечивают увеличение емкости сети UMTS, без
дополнительных капитальных затрат на оборудование.
2. Разработанные методы и полученные результаты исследования могут быть
применены как в отделах планирования радиосети компании оператора
сотовой связи, так и в компаниях-разработчиках программного обеспечения для планирования сети UMTS.
3. Отдельные задачи, рассматриваемые в диссертации, могут быть
использованы в учебном процессе ВУЗов при подготовке бакалавров,
дипломированных специалистов и магистров по специальности 201200
«Средства связи с подвижными объектами».
4. На основе развития эвристических методов оптимизации разработано
программное обеспечение, позволяющее производить расчет ключевых
параметров WCDMA радиоинтерфейса.
Апробация и внедрение результатов работы
Основные научные и прикладные результаты диссертационной работы были использованы при выполнении комплекса работ, связанных с подготовкой к интеграции UMTS в существующую GSM инфраструктуру в ОАО «Мобильные ТелеСистемы», а также при разработке методик планирования и оптимизации сетей третьего поколения в Государственном Специализированном Проектном Институте Радио и Телевидения.
Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы и приложений.
В главе 1 изложено современное состояние проблемы планирования сети UMTS, изображена структурная схема и состав оборудования, а также приведена характеристика транспортных и физических каналов UTRAN. На основе анализа процедур физического уровня, и сравнения параметров радиоинтерфейса WCDMA и GSM технологий осуществлена постановка задач исследования.
В главе 2 рассмотрен математический аппарат теоретических основ исследования. Кроме характеристики эвристических методов оптимизации, определены правила по которым производится оптимизация параметров радиоподсистемы; определена целевая функция и обоснованы критерии эффективности алгоритмов оптимизации.
В главе 3 рассмотрено использование метода случайного поиска, метода экспертной оценки, генетического метода оптимизации, метода имитации отжига, а также DIRECT метода применительно к задаче определения углов наклона антенн и значений мощностей пилот-канала в сети UMTS. Рассмотрены варианты использования правил управления параметрами радиоподсистемы при проведении оптимизации (изменение угла наклона TILT и значений СРІСН мощности (CPICH+TILT), изменение только СРІСН мощности (СРІСН Only), определение мощности пилот-канала в соответствии со значением угла наклона антенн CPICH=f(TILT)).
В главе 4 приводится обсуждение полученных результатов оптимизации, а также осуществляется общий анализ эффективности применяемых методов по критериям, определенным в главе 2.
В Заключении сформулированы основные выводы и результаты диссертационной работы.
В Приложении 1 приведен список условных сокращений. В Приложении 2 указаны параметры базовых станций сети UMTS, использованные при моделировании.
В Приложении 3 приведены результаты имитационного моделирования в табличном виде.
В Приложении 4 приведены листинги основных подпрограмм, реализованных в среде Matlab.
В Приложении 5 помещены акты внедрения результатов диссертационной работы.
На защиту выносятся:
1. На основании проведенного исследования для решения задачи оптимизации параметров радиоподсистемы сети UMTS можно рекомендовать методы эвристической оптимизации такие как генетический метод и метод имитации отжига. Метод случайного поиска, метод экспертной оценки и DIRECT метод не рекомендуются к применению.
2. В качестве критерия оптимизации целесообразно использовать максимум
числа обслуживаемых мобильных терминалов при накладываемых
ограничениях на равномерность загрузки ячеек сети и на оптимальность зон
мягкого хэндовера, а не максимум пропускной способности сети.
3. Рекомендуется использовать правила управления параметрами
радиоподсистемы сети UMTS, заключающиеся в изменении только значений
мощности пилот-каналов (CPICH Only), определении значений мощностей
пилот-каналов в соответствии со значениями углов наклона антенн
(CPICH=f(TILT)). Правило CPICH+TILT к использованию не рекомендуется.
4. В том случае если время расчета является критически важным параметром,
рекомендуется использовать метод имитации отжига, если необходимо
добиться максимального увеличения емкости сети и время расчета не
является особо критичным параметром, то рекомендуется использовать
генетический метод оптимизации.
Основные положения и результаты диссертационной работы опубликованы в журнале «Мобильные Системы» №9, 2005 г., Электросвязь №8, 2005 г., «Мобильные Системы» №6,7 за 2003 год, докладывались на международном семинаре «Перспективы развития современных средств и систем телекоммуникаций», Санкт-Петербург в 2002 году. В целом, в печатных изданиях были опубликованы 9 работ и получен один патент на изобретение.
Анализ процесса планирования радиоподсистемы UTRAN
Процесс планирования радиоподсистемы UTRAN подразделяется на три основных этапа: определение границ планирования (dimensioning), детальное планирование параметров радиосети (detailed radio network planning) и оптимизация сети (optimisation).
Основной целью этапа определения границ планирования является приблизительная оценка требуемого числа базовых станций и их конфигурации, контроллеров и коммутаторов сети (RNC, MS С), что необходимо для расчета затрат на оборудование. Как правило результатом данного этапа является бюджет радиоканала (link b udget), приведенный в Приложении 2.
Целью этапа детального планирования радиоподсистемы UTRAN является определение зоны обслуживания сети, таким образом, чтобы прямой и обратный канал были сбалансированы. Этап детального планирования также включает определение реальных координат расположения площадок базовых станций и построение модели распределения трафика.
Целью фазы оптимизации является улучшение показателей производительности сети. Процесс оптимизации заключается в изменении конфигурация базовых станций, высот подвеса, азимутов и углов наклона антенн таким образом, чтобы максимально снизить общий уровень интерференции в сети. Ключевыми показателями эффективности работы сети UMTS являются: Значение емкости сети Процент разорванных радиосоединений Процент неуспешных доступов в сеть Число ячеек в Активном Наборе (Active Set)
В настоящей работе в анализируется третий этап планирования сети (optimisation), поскольку на первых двух этапах особых проблем, как правило, не возникает.
Согласно спецификациям института 3GPP (Third Generation Partnership Project), стандарт UMTS состоит из нескольких фаз развития функциональности системы (Releases): Release 99, Release 4, Release 5, Release 6, Release 7. Главным требованием к каждой последующей стадии эволюции от сетей второго поколения к сетям третьего поколения является требование полной совместимости структурных элементов сети. В данной главе дается широкий обзор архитектуры системы UMTS Release 99 и Release 4 и основных ее компонентов.
Элементы сети UMTS могут группироваться на основе подсети, к которой они принадлежат или на основе схожести выполняемых функций [56]. По своим функциям элементы сети группируются в сеть радиодоступа - RAN (Radio Access Network или UMTS территориального уровня - UTRAN), которая управляет всеми функциями, относящимися к радиосвязи, и в базовую сеть - CN (Core Network), которая обеспечивает коммутацию и маршрутизацию вызовов и каналы передачи данных во внешние сети. Также определяются оборудование пользователя (UE - User Equipment), которое посредством нового радио интерфейса (Uu) взаимодействует с UTRAN (Рис.1).
Основными характеристиками UMTS, которые в свое время определили требования для построения ее архитектуры, функций и протоколов являются: — Максимизация унификации при обработке данных с коммутацией пакетов и с коммутацией каналов при использовании уникального пакета протоколов воздушного интерфейса и при использовании одного и того же интерфейса для соединения UTRAN с областями обслуживания (доменами) как PS, так и CS базовой сети. — Максимизация, по возможности, общности с GSM. — Использование транспортного протокола ATM в качестве основного транспортного механизма в UTRAN. Остановимся более подробно на функциональных характеристиках и элементах сети UTRAN (рис.2).
UTRAN включает в себя одну или несколько подсистем радиосети -RNS (Radio Network Subsystem). RNS - это подсеть в UTRAN, состоящая из контроллера радиосети (RNC) и одного или нескольких Node В. RNC обеспечивает управление радиоресурсами UTRAN. Он сопрягается с CN (обычно с одним MSC и одним SGSN), а также реализует протокол RRC (управления радиоресурсами), который определяет сообщения и процедуры между подвижной станцией и UTRAN. Логически он соответствует BSC (контроллеру базовой станции) в GSM. RNC могут соединяться друг с другом через интерфейс lur. RNC и Node В соединяются с помощью интерфейса Iub.
Node В преобразует поток данных между интерфейсами Iub и Uu. Основная функция Node В заключается в обработке на уровне L1 в воздушном интерфейсе (канальное кодирование и перемежение, адаптация скорости, расширение спектра и т.д). Также Node В выполняет одну из основных операций по управлению радиоресурсами — управление мощностью во внутреннем контуре.
Характеристика эвристических методов оптимизации
Такие алгоритмы разделяют область поиска на набор многомерных кубиков, на которых нижняя граница функции цели вычисляется с помощью интервальной техники. Используя интервальную арифметику на каждом шаге, получаем набор последовательно уменьшающихся интервалов, который содержит глобальное решение исходной задачи. Алгоритм останавливается, когда размер интервалов достигает заранее заданного значения [56]. Методы интервалов требуют, чтобы функция цели была задана явно, т.к. это выражение используется интервальной техникой для вычисления границ. Методы, использующие технику ветвей и границ, в силу древовидной структуры являются объектом исследований в контексте параллельных вычислений. Некоторые разработки параллельных алгоритмов ветвей и границ приводятся в [57].
Каждый шаг метода туннелей состоит из двух фаз: фаза минимизации улучшает значение текущего рекорда; фаза туннелирования находит точку из допустимого множества, отличную от последней, где найдено значение минимума. Полученная на фазе туннелирования точка рассматривается как стартовая для очередного цикла. Главный недостаток этого алгоритма -необходимость решения сложных нелинейных дифференциальных уравнений.
Основная идея метода имитации отжига [12, 17], исходит из физики процесса замерзания жидкостей или рекристаллизации металлов в процессе обжига.
Метод имитации отжига позволяет преодолеть локальные минимумы и искать глобальный минимум целевой функции. Платой за это преимущество является медленная работа алгоритма в случае большой размерности целевой функции. В 50х годах был исследован процесс отжига металла и построена его математическая модель. Если раскалить кусок металла, то его внутренняя энергия достигнет высокого значения. Кристаллическая решетка при этом будет наименее упорядочена, т.к. тепловые флуктуации атомов решетки будут велики. Это соответствует начальному состоянию функции. Если затем быстро охладить металл, то атомы будут находиться в энергетически невыгодных состояниях. Энергия системы снизится, но не достигнет глобального минимума. Кристаллическая решетка будет иметь множество дефектов, т.е. отклонений в расположении атомов от оптимального значения, а металл будет иметь высокую твердость (закаливание). Если охлаждение проводить медленно (отжиг), то с плавным уменьшением температуры тепловые колебания узлов решетки около состояния минимума энергии будут плавно уменьшаться, и в результате охлаждения решетка будет иметь высокую упорядоченность, а энергия системы достигнет глобального минимума.
Имитация отжига применяется для NP-полных задач, например, задачи коммивояжера, не поддающихся точному алгоритмическому решению. Данный метод используется при автоматическом размещении компонент на печатных платах, при их автотрассировке и во многих других задачах. Преимущество алгоритма — поиск глобального минимума и отсутствие ограничений на вид минимизируемой функции Е. Недостаток — требование бесконечно медленного охлаждения, на практике означающее медленную работу алгоритма.
Целевая функция здесь является аналогом равновесия термодинамической системы и видоизменяется путем добавления случайных величин (условий температурного режима). Процесс повторяется достаточное число раз для каждой температуры, после чего температура понижается и весь процесс происходит снова до состояния полной заморозки. Избегание попадания в незначительные локальные минимумы (замерзание) зависит от «схемы отжига», выбора начальной температуры, количества итераций для каждой температуры и насколько уменьшается температура на каждом шаге процесса «охлаждения».
Эволюционные алгоритмы [69] являются поисковыми методами, основная идея которых заимствована из биологического процесса естественного отбора и процесса выживания. Такие алгоритмы отличаются от традиционных методов оптимизации тем, что поиск производится из «популяции» решений, а не из одной точки. Каждая итерация метода производит «естественный отбор», который отсеивает неподходящие решения. Решения с высокой пригодностью («биологической реакцией на естественный отбор») «скрещиваются» с другими решениями путем обмена частей одних решений на другие. Решения могут «мутировать» из-за небольших замен одного элемента решения. Скрещивания и мутации генерируют новые решения, которые «генетически» настроены на области допустимого множества, для которых уже было обнаружено хорошее решение. Существует несколько различных типов эволюционных поисковых алгоритмов: алгоритмы генетического программирования, алгоритмы эволюционного программирования, алгоритмы эволюционных стратегий, генетические алгоритмы . Эволюционные алгоритмы обладают слабой сходимостью к глобальному решению, но вместе с тем, хорошо обрабатывают сильно зашумленные функции с большим числом незначительных локальных решений, не «прилипают» к локальным экстремумам и способны получить глобальное решение.
Правила управления параметрами радиоподсистемы
Целесообразность оптимизации сети путем совместного изменения значений CPICH мощности и углов наклона антенн поясняется Рис.47
На Рис.47(а) изображен случай обслуживания мобильных терминалов 1 и 2 базовой станций Node В1. Поскольку целью оптимизации является увеличение емкости системы, а выравнивание нагрузки между секторами способствует данной цели, то необходимо путем изменения параметров секторов перераспределить области обслуживания секторов так, чтобы абонент 1 обслуживался NodeBl, а абонент 2 обслуживался Node В2.
Указанная цель может достигаться тремя способами:
1) Первый способ заключается в снижении CPICH мощности Node В1, Рис. 47 (Ь). В этом случае главным недостатком является интерференция от каналов трафика NodeBl к Node В 2. Главным преимуществом правила является простота и скорость практической реализации. Параметры CPICH мощности корректируются в RNC.
2) Второй способ заключается в увеличении угла наклона антенны Node В1, но без снижения уровня CPICH сигнала, Рис. 47(c). Однако в этом случае значение CPICH мощности остается высоким для ячейки малого размера, что приводит к интерференции пилот-каналов соседних ячеек. Более того, излишне большое значение мощности пилот-канала неэффективно, поскольку использует ресурс мощности каналов трафика, который мог быть выделен на обслуживание дополнительного количества мобильных терминалов. Недостатком правила является высокая трудоемкость практической реализации.
3) Третий способ заключается в одновременном изменении углов наклона антенн и значений CPICH мощностей. В работе исследуется две возможности применения данной стратегии: взаимонезависимое изменение углов наклона и значений CPICH мощностей - метод оптимизации разработанный на основе определения множества углов наклона антенн, а значения CPICH мощностей определяются исходя из правил максимума обслуживаемой нагрузки при текущем значении угла наклона антенны (см. раздел 2.3.4).
Метод перебора или равномерного поиска является простейшим из прямых методов поиска минимального или максимального значения функции f(x) и состоит в следующем. Разобьем множество решений Ма[а,Ь] на п равных частей точками деления: . Ь а п xt=a + i , i = 0..n п Вычислив значения f(x) в точках xt, путем сравнения найдем точку хт, где т - это число от 0 до и, такую, что f(x„ ) = min(F(xi)), У і є [0..п] Полученное решение будет лишь одним из локальных минимумов.
Следует заметить, что для поиска глобального мимнимума в задаче определения параметров СРІСН мощности и углов наклона антенн требуется перебрать очень большое число вариантов, равное (і О2 J , где N— число ячеек в сети.
В связи со значительными временными ресурсами, требуемыми для расчета числа обслуживаемых мобильных терминалов, в настоящей работе исследована небольшая часть всего множества решений. При использовании метода случайного поиска, правила CPICH+TILT и CPICH Only дают приблизительно одинаковый конечный результат.
Результаты моделирования приведены в табл. 3.1 (Приложение 3) и на Рис.48. Следует отметить, что говорить о какой-либо оптимизации в этом случае не приходится. Среднее число обслуживаемых мобильных терминалов после определения новых параметров радиоподсистемы равно 792, что на 11 мобильных терминалов больше чем до «оптимизации». Пропускная способность сети «увеличилась» с 22.1 до 23.8 Мбит/с.
Анализ результатов при использовании генетического алгоритма
Для выбора метода оптимизации, обладающего наибольшей эффективностью решения задачи максимизации емкости сети, а также отвечающего ряду других критериев, произведем сравнительный анализ всех методов, рассмотренных в настоящем исследовании.
Наибольшее число обслуживаемых мобильных терминалов равное 1134, было полученно при использовании генетического метода по правилу CPICH=f(TILT) (рис.87). Это же правило применяемое при оптимизации генетическим методом обладает максимальным процентом увеличения емкости сети (46.2%), рис.88, однако оно уступает методу разделения на прямоугольники (DIRECT) по критерию равномерности загрузки сети (277 против 244) (рис.90). Кроме того, при использовании генетического алгоритма и правила CPICH=f(TILT) показатель оптимальности сети по SHO (SI=7.6%) больше, чем при использовании метода имитации отжига и стратегии CPICH Only (SI=2.2%). Следует также отметить, что при оптимизации генетическим методом для рассмотренного участка сети и 30 поколений требуется около 12.5 часов, а при оптимизации методом имитации отжига - около 8.5 часов (рис.92).
Остальные правила управления параметрами радиоподсистемы при оптимизации генетическим методом (CPICH+TILT, CPICH Only) заметно уступают по эффективности правилу CPICH=f(TILT). Максимальное число обслуживаемых мобильных терминалов, полученное с использованием правила CPICH+TILT составляет 1003, что соответствует увеличению емкости сети на 27.77% (рис.88). Среднее число обслуживаемых мобильных терминалов, полученное с использованием правила CPICH Only, равно 999 (увеличение емкости на 27.24%).
Далее приведен ряд диаграмм, где изображены показатели эффективности исследуемых методов оптимизации.
Анализ результатов, полученных методом имитации отжига, позволяют сделать вывод об относительно высокой эффективности данного метода. Средний процент увеличения емкости сети по всем стратегиям метода имитации отжига составляет 42.17%, что всего на 4.03% ниже результата полученного при оптимизации генетическим методом по правилу CPICH=f(TILT).
Однако главным преимуществом метода имитации отжига по сравнению с другими методами является малое время расчета (около 8.5 часов при методе имитации отжига против 12.5 часов при генетическом методе) при небольшом снижении результата оптимизации около 4%.
Метод разделения на прямоугольники (DIRECT) имеет наибольшее среди исследованных алгоритмов время расчета и в то же время обладает далеко не лучшим процентом увеличения емкости сети (30.28%). Однако метод DIRECT позволяет распределить нагрузку в сети наиболее равномерно. Значение параметра CL=244.0, что ниже чем у всех остальных методов (генетический алгоритм, правило CPICH=f(TILT), CL=277; метод имитации отжига, CPICH Only - CL=287.9).
1. Вопрос выбора наиболее эффективного метода оптимизации параметров радиоподсистемы для решения задачи увеличения емкости сети необходимо рассматривать с двух сторон. В том случае, если время расчета является критически важным параметром, то рекомендуется использовать метод имитации отжига. Что касается правил управления параметрами радиоподсистемы, то несмотря на то , что были выявлены два правила (CPICH+TILT, CPICH Only) позволяющие получить примерно одинаковый результат увеличения емкости сети - 42.75% и 42.4% соответственно, рекомендуется применять правило CPICH Only, поскольку в этом случае не требуется производить изменения углов наклона антенн и достаточно изменений значений CPICH мощности ячеек сети, что снижает затраты на проведения оптимизации сети.
2. Если необходимо добиться максимального увеличения емкости сети и время расчета не является особо критичным параметром, то рекомендуется использовать генетический метод оптимизации. При использовании правила определения значений мощности пилот-канала в соответствии с углом наклона антенн CPICH=f(TILT), которое позволяет получить наилучший результат по сравнению с другими правилами, среднее значение увеличения емкости сети равно 46.32%, максимальное -63.8%.
3. Применение метода разделения на прямоугольники (DIRECT) позволяет увеличить емкость сети в среденем на 30%, однако требует очень больших временных затрат, поэтому метод DIRECT не рекомендуется к применению. Необходимо отметить, что значительное время расчета параметров сети обусловлено большим временем расчета значений целевой функции для чего необходимо производить полный цикл расчета сети с постоянно изменяемыми параметрами.
