Comparative Analysis of Models and Methods for Solving the Problem of Structural Synthesis for Modern Mobile Communication Systems

Введение

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

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

Основные подходы к решению данной проблемы рассматривалось в ^{[1 -5]}. Как правило, для исследования использовалась конкретная сеть (например, сотовая сеть третьего поколения на основе технологии WCDMA) с конкретными требованиями к критерию оптимизации и ограничениями. Но, в силу постоянных изменений систем сотовой связи целесообразно формализовать (для того, чтобы в дальнейшем решить) задачу в общем виде. Это позволит адаптироваться к периодическим изменениям к качеству обслуживания, возникающими при переходе к другой технологии сотовых систем.

1. Постановка задачи и ее особенности

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

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

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

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

Обобщенно алгоритм решения данной задачи можно представить следующим образом (рис. 1).

Рисунок 1 – Обобщенный алгоритм частотно-территориального планирования

Рассмотрим основные этапы данного алгоритма более подробно. В качестве исходных данных будет выступать следующая информация:

- карта местности с ориентировочной численностью населения;

- ориентировочная плотность населения, нагрузка на одного абонента и требования к ее росту и т.д.;

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

- требования к качеству обслуживания (вероятность ошибки, неуспешные вызовы, параметры качества передачи речи и т.д.);

- параметры, описывающие физические характеристики распространения радиоволн.

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

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

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

Фактически данная задача определяет целый класс задач синтеза сотовой сети мобильной связи. Каждая задача будет определяться целью (критериальной функцией) и ограничениями.

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

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

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

2. Анализ существующих подходов к решению задачи структурного синтеза

Задачи построения сотовых сетей рассматривались с разными критериями и требованиями ^[6],[8-10]. В зависимости от целей и ограничений для решения поставленных задач применяют как традиционные, так и эвристические методы. Ключевым этапом решения задачи является определение мест расположения базовых станций и расчёт зоны покрытия. Существующие программные комплексы, которые позволяют решать данную задачу, накладывают существенные ограничения на выбор начальных условий построения сети. К ним относятся использование сравнительно узкого диапазона частот и определенных категорий местности, что делает их неуниверсальными. Специфика сетей нового поколения при расчёте местоположений базовых станций требует учитывать множество параметров: ландшафт, плотность застройки, населенность, а также полный диапазон частот работы сетей.

В работе ^[6] рассматриваются алгоритмы выбора координат базовых станций мобильной сети с учетом распределения абонентского трафика (плотности населения). Для решения данной задачи в методике предложены два варианта применения алгоритмов кластерного анализа. При выборе координат учитывается, в первую очередь, максимум величины обслуживаемого трафика. Кроме того, важными требованиями для работы алгоритмов считаются:

- обеспечение необходимого уровня качества обслуживания;

- обеспечение требования как по полосе пропускания, так и по интенсивности абонентского трафика ^[6].

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

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

В ^[8] описывается разработка метода размещения базовых станций с учётом потерь при распространении сигнала. Основой метода являются муравьиные алгоритмы. Ограничения – диапазон частот 1 – 5 ГГц и равнинная территория с малой плотностью деревьев.

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

В ^[10] решается задача проектирования структуры сети для систем третьего поколения, в частности, WCDMA. В качестве критерия используется минимизация количества базовых станций. В частности, базовая станция определена:

- возможными географическими координатами;

- техническими характеристиками (мощность радиопередатчика, чувствительность приемника, высота и коэффициент усиления антенны и т.д.).

Идея решения основана на определения для каждой базовой станции ее веса, характеризующего так называемую «оптимальность» ее размещения ^[10]. Согласно этому критерию все множество потенциальных базовых станций сужается до тех пор, пока оно не будет содержать минимального количества станций, достаточного для решения задачи.

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

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

3. Формализация задачи

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

. (1)

Предполагается, что D1,…, Dk представляют собой непересекающиеся замкнутые ограниченные области. Как частный случай данного варианта это может быть некоторая точка с географическими координатами (x,y).

Пусть базовая станция bi задается следующим образом:

. (2)

Здесь p – точка, принадлежащая D, а r – вектор, характеризующий параметры базовой станции:

. (3)

Каждой паре величин можно поставить в соответствие функцию стоимости:

. (4)

Необходимо выбрать такие характеристики каждой базовой станции, чтобы минимизировать общую стоимость их размещения. Иными словами, необходимо выбрать такое количество базовых станций N, а также для базовой станции b1 - такую конфигурацию (p1, r1, c1); для базовой станции b2 – такую конфигурацию (p2, r2, c2) и т.д., чтобы минимизировать следующую целевую функцию:

. (5)

Главным требованием при решении любой аналогичной задачи является покрытие всей территории D. Пусть на основании выбранных характеристик (географических координат и радиусов действия, в частности) получены области их покрытия d1,…,dN. Тогда должно выполняться требование:

. (6)

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

, (7)

где Kj – j-я характеристика качества обслуживания. Пусть требуется, чтобы данная характеристика удовлетворяла условию:

, (8)

где Rj – множество приемлемых значений j-й характеристики. Условие (8), например, может быть переписано в виде:

, (9)

или

. (10)

Пусть при выборе конфигурации bi получим фиксированные значения вектора К.

Тогда задача структурного синтеза может быть сведена к выбору такого количества N и таких параметров базовых станций, чтобы, при выполнении условий (6) и (8), минимизировать целевую функцию (5).

Таким образом, получили формализацию исследуемой задачи в обобщенном виде.

Выводы

В данной работе были решены следующие задачи.

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

2. Проанализированы существующие задачи и подходы к их решению.

3. На основании проведенного анализа получена формализация оптимизационной задачи со стоимостной целевой функцией.