Автореферат

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

Введение

Сотовая связь - одно из революционных достижений в области беспроводных сетей, ставшее обыденным за последние 10 лет. Роль этой технологии в наши годы столь же велика, как бум персональных компьютеров в 80-е годы. Мобильный телефон превратился в привычный предмет обихода, по стоимости приближающихся к обычному телефонному аппарату (а по распространенности уже превзошедший число аппаратов фиксированной связи). Рост сотовых сетей связи носит по истине взрывной характер. Число их абонентов уже превысило миллиард - примерно столько, сколько всего абонентов проводной связи.

К настоящему моменту на территории Украины действуют следующие операторские компании, имеющих лицензии на предоставление услуг сотовой связи: "Life", "UMC", "КиевСтар", "Билайн" и др. Во многих регионах можно встретить несколько операторских компаний, предоставляющих абонентам услуги сотовой связи различных стандартов. Именно поэтому, в условиях жесткой конкуренции, когда необходимо предоставить абонентам сотовую связь с высоким качеством, нужно найти правильный подход к проектированию сотовых сетей. Из вышесказанного возникает ряд вопросов о необходимости и целесообразности проектирования сотовых сетей на различных этапах их эксплуатации. При проектировании сетей мобильной связи зачастую нелегко выбрать оптимальное решение. Много проблем связано с необходимостью обеспечения непрерывного покрытия, увеличения радиуса покрытия одной базовой станции и т. п. Иногда компании-производители предлагают экзотические решения, которые не выходят за рамки теории и ориентируются при построении сетей на усредненные характеристики оборудования, имеющегося на телекоммуникационном рынке.

Обоснование актуальности

Сети беспровод­ного доступа, в которых количество базовых станций насчитывается несколькими десятками, давно стали обычным явлением. Популярность беспроводных сетей объ­ясняется наличием целого ряда присущих им достоинств.Таким образом, остро встает вопрос о проектировании беспроводных сетей, что предполагает решение множества сложных взаимосвязанных задач.При проектировании сотовых сетей возникает ряд вопросов о необходимости и целесообразности проектирования сотовых сетей на различных этапах их эксплуатации. Что касается проблемы проектирования то ее необходимо рассматривать с двух сторон: когда планируется развернуть сотовую сеть на заданной территории охвата и, когда сотовая сеть уже успешно эксплуатируется абонентами. На начальной стадии проектирования сотовой сети возникает необходимость нахождения оптимального варианта соотношения между эффективностью и сложностью системы, что позволяет определить начальную конфигурацию сети и план дальнейшего ее развития. Эффективность достигается за счет обеспечения требуемого качества работы всей системы с минимальными затратами на оборудование, т.к. любое усложнение архитектуры системы приводит к удорожанию требуемого оборудования. Исходя из этого, необходимо, с максимально возможной точностью, определить основные характеристики сети.

К основным характеристикам сети можно отнести допустимую телефонную нагрузку и частотно - территориальное планирование. Эти характеристики позволяют получить систему с заданной вероятностью отказа в обслуживании подвижных абонентов сети при заданном качестве связи. Если рассмотреть эту проблему более подробно, то в целом эффективность планирования будет достигаться за счет территории охвата, расчета по емкости сети, планирования передачи и оптимизации сети. Рассмотрим другой вариант, когда сотовая сеть достаточное время эксплуатируется и мы имеем дело с опытным оператором. Допустим, что количество абонентов непрерывно увеличивается. Тогда наступает такой момент, когда в отдельных сотах в час наибольшей нагрузки появляется скопление подвижных абонентов, нагрузка на базовую станцию максимальна и она не справляется со всем объемом поступающих вызовов. Абонентам поступают отказы в обслуживании. В следствии этого возникает такое понятия, как "traffic handover" (передача управления вызовом по критерию нагрузки). Но, к сожалению, не всегда удается решить вопросы перегрузки при помощи процедуры "handover" или перераспределения радиоканалов. Можно использовать также изменение частотного плана с повторным использованием частот, изменить ширину спектра канала связи и другие всем известные методы. Но на сегодняшний момент оператор еще не готов к таким серьезным шагам. Поэтому оператор вынужден установить дополнительную базовую станцию. Для этого необходимо сделать предварительный расчет, задав конкретные параметры базовой станции, и то качество обслуживания, которое устроит разборчивого абонента. Возможно, что нет необходимости в дополнительном пояснении о целесообразности проектирования, но это порождает следующий вопрос о методах проектирования, которые будут рассмотрены в разделе "Обзор существующих методов и разработок".

Цели и задачи работы

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

Обзор существующих методов и разработок

При проектировании сотовой сети можно использовать распространенные методы компьютерного анализа и автоматического проектирования,предоставляемые такими программными продуктами, как "RPS2" и "WireLess Insite" (и др.). Но, к сожалению, не все операторы могут позволить себе такую роскошь. Особенно, это касается малых региональных операторских компаний, использующих оборудование сотовой связи стандартов AMPS, DAMPS. Также данные системы предназначены для проектирования сотовой сети "с нуля" и непригодны для оптимизации существующих сетей. Предварительные расчеты новой базовой станции уже в эксплуатируемой сети, практически, все операторы производят самостоятельно. Каждый оператор делает это по-разному и, в большинстве случаев, условно, так как только после ввода в эксплуатацию нового оборудования базовой станции, набирая статистические данные производят коррекцию ее параметров. Это несколько затрудняет работоспособность сети и требует определенного времени для принятия решений.

Автоматизированная система RPS2

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

Автоматизированная система WireLess Insite

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

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

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

Будем рассматривать задачу со следующими условиями. Пусть имеется набор мест I = (1,..., n), в которых молено разместить базовые станции. Каждая базовая стан­ция имеет определенную емкость a[i] >= 0, i принадлежит I, выраженную в Мбит/с или в допустимом количестве подключаемых к ней клиентов. Задан набор мест рас­положений клиентов J = (1,...,m), каждый из которых имеет свою потребность в полосе пропускания b[j] >= 0, j € J, и каждый клиент должен быть подключен только к одной базовой станции. Существует фиксированная цена установки базовых станций f[i] > О, i € I, если базовая станция установлена в г-м месте-кандидате, и фиксированная цена подключения клиентов с[i][j] >= 0, i € I, j € J, если j-й клиент подключается к базовой станции, установленной в г'-i месте-кандидате. Необходимо установить базовые станции среди подмножества потенциальных мест размещения S так, чтобы все клиенты были подключены, емкостные ограничения базовых станций не нарушались, а суммарная стоимость, состоящая из фиксированных цен установки базовых станций и цен подключений клиентов, была минимальной. Введем следующие обозначения: x[i][j] = 1, если клиент j подключен к базовой станции, размещенной в i-м месте-кандидате, х [i][j] = 0 в противном случае, и y[i] = 1, если в i-м месте-кандидате установлена базовая станция, y[i] = 0, в противном случае. Теперь, в линейно-целочисленном виде задачу можно сформулировать так:

Ограничения (2) гарантируют, что будут подключены все клиенты, причем каж­дый клиент подключается только к одной базовой станции. Ограничения (3) связаны с ограничениями, накладываемыми на емкости базовых станций, а также обеспечи­вают подключение клиентов только к установленным базовым станциям. (4) и (5) накладывают на переменные ограничения целочисленности. В литературе такую задачу общепринято называть емкостной задачей размеще­ния с одним источником. Ее изучению посвящены рыботы: [4], [5], [6], [7] и др. В большинстве статей для решения задачи используют Лагранжевы эвристики. Емкостная задача размещения с одним источником, как и многие другие задачи оптимизации, содержит ограничения, из-за чего возникает вопрос о том, как обхо­диться с ограничениями и недопустимыми решениями при разработке генетических алгоритмов для решения задач данного типа.

Первым шагом в разработке генетического алгоритма для данной задачи являет­ся создание удобного представления данных. Для емкостной задачи размещения с одним источником обычное двоичное представление переменных в виде 0 и 1 неудобно, поскольку потребуются двоичные строки длины n х m и, в тоже время, это не гарантирует того, что ограничения связанные с подключением клиентов и емкостные ограничения не будут нарушены. Для того чтобы избежать вышеописан­ной ситуации с нарушениями ограничений, будем использовать представление, где каждая хромосома является m-мерным вектором, состоящим из целых чисел от 1 до n: целое число, находящееся на j-м месте обозначает номер места-кандидата, в котором расположена базовая станция, и к которой подключен j'-й клиент. Далее, будем применять название "i-я базовая станция", подразумевая под этим базовую станцию, установленную в i-м месте-кандидате. Так, например, если n = 3 и m = 7, хромосома {2, 1, 3, 1, 1, 2, 3} представляет одно из возможных решений задачи, где клиенты 2, 4, 5 подключены к базовой станции с номером 1, клиенты 1, 6 - к базовой станции с номером 2, а 3 и 7 - к базовой станции с номером 3.

Мультистарт и генетический алгоритм

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

Поиск с запретами и генетический алгоритм

Поиск с запретами (Tabu Search) является одним из наиболее используемых мета-эвристик. Основоположником алгоритма поиска с запретами является Glover [2]. Более детальное описание алгоритма можно найти в работе [3]. Поиск с запрета­ми активно использует историю поиска как для того, чтобы выйти из локального оптимума, так и для исследования пространства поиска. Простой алгоритм поиска с запретами использует обычный локальный поиск, а также использует краткосрочную память, чтобы избежать зацикливания и для выхода из локального оптимума. Краткосрочная память используется как список запретов или табу, который содержит недавно посещенные решения и препятствует движению поиска по направлению к этим решениям. Таким образом, окрестность текущего решения ограничивается решениями, не принадлежащими списку запре­тов. Решения, не принадлежащие списку запретов, иногда называют разрешенным списком или разрешенным набором решений. На каждом шаге из разрешенного списка выбирается решение, производится поиск и это решение заносится в за­прещенный список, а одно из решений, уже находящихся в запрещенном списке, исключается из этого списка, например, с использованием очередности FIFO. Спи­сок запретов выбирается определенной длинны L которая, как правило, меньше мощности всего пространства поиска. При наличии маленькой продолжительности запрета, поиск сосредоточится в небольшой области части пространства поиска. И наоборот, если запрет будет более длинным, то это подтолкнет к исследованию боль­шего пространства поиска, поскольку будет запрещен возврат в большее количество решений. В нашей задаче поиск с запретами будем применять по отношению к решениям-производителям, после того как они приняли участие в скрещивании и по отношению к новым найденным улучшенным решениям-потомкам

Планируемые результаты

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

Заключение

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

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

Примечание: данный автореферат не является окончательной версией автореферата магистерской работы, т.к. завершение исследований по теме магистерского проекта планируется до 31.12.2007

Список источников