Расчет покрытий базовых станций сотовой сети

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

Краткие сведения о задаче расчета покрытий

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

1. Идентификаторы станции т.е. mcc, mnc, lac, cid (подробнее об этих идентификаторах можно прочитать в википедии
2. Частота, на которой работает БС.
3. Высота подвеса.
4. Тип сети (2G, 3G, 4G).
5. Азимут "луча" станции.
6. Ширина сектора станции в градусах.

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

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

Алгоритм расчета покрытий

Используемые понятия Сектор обзора станции: сектор радиуса MAX_RADIUS с центром в точке установки станции, дугою сектора 120 градусов, и направлением AZIMUTH. Зона покрытия станции: искомый участок сектора обзора станции. Точки данного участка характеризуются тем, что расстояние от точки до данной станции будет меньше, чем до любой другой станции данного оператора, работающей по данной технологии (2G, 3G, 4G).

Инициализация. Производится группировка станций по оператору (т.е. по параметрам mcc и mnc) и технологии (2G, 3G, 4G). Для каждой группы алгоритм расчета покрытий производится независимо.

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

Этап второй. Построение зон покрытия станций. Для каждого покрытия, инициализированного на предыдущем этапе, производится следующие действия:

1. Выбирается очередное покрытие (далее COVERAGE).
2. Находятся те сектора обзора, которые пересекаются с COVERAGE, и для каждого такого сектора обзора (далее currentSECT) производится:
   1. Найти пересечение покрытия COVERAGE и текущего сектора currentSECT.
   2. Вычислить тот участок пересечения, который лежит ближе к сектору currentSECT, чем к покрытию.
   3. Отрезать от COVERAGE этот участок пересечения.
3. Вернуть результат всех обрезаний — COVERAGE содержит искомое покрытие станции.

Пример выполнения пунктов 2.1. - 2.3. приведен в разделе «Обрезка покрытий»

Обрезка покрытий

Рассмотрим одну итерацию построения зоны видимости конкретной станции (п.п. 2.1. - 2.3. алгоритма). Пусть A — точка расположения станции, для которой строится покрытие, B — точка расположения станции, сектор обзора которой пересекается с текущей зоной покрытия станции A.

Тогда требуется найти тот участок COVERAGE, который находится в секторе currentSECT, и точки которого расположены ближе к точке B, чем к точке A

• 

  Рисунок 1. Разбиение плоскости на две полуплоскости.

• 

  Рисунок 2 Выявление части сектора currentSECT, которая не может принадлежать зоне покрытия станции A (зеленый цвет).

• 

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

На начальном этапе COVERAGE совпадает с сектором обзора станции A как показано на рисунке 1.

Для выявления того участка пересечения COVERAGE и currentSECT, который лежит ближе к сектору B, чем к A, нужно:

1. Провести линию, перпендикулярную отрезку AB, и проходящую через середину данного отрезка. Данная линия разбивает плоскость на две полуплоскости, при этом точки, лежащие на данной линии, находятся на одинаковом расстоянии от точек A и B (см. рисунок 1). На данном рисунке точки левой полуплоскости будут лежать ближе к точке A, чем к точке B.
2. Разрезать данной линией сектор currentSECT. В результате та часть сектора, в которой расположена точка B, (на рисунке 2 она находится в правой полуплоскости) не может принадлежать зоне покрытия станции A (COVERAGE), поскольку она расположена ближе к станции B.
3. Из COVERAGE вырезается часть сектора currentSECT, расположенная ближе к точке B, чем к точке A. Результат показан на рисунке 3.

Реализация алгоритма в GRASS GIS

Предположим, что у нас имеется векторная карта, которая называется stations, и которая связана с БД, содержащей следующие поля:

• cat целочисленное поле -- идентификатор станции
• r поле хранит максимальный радиус действия станции
• x координата x станции
• y координата y станции
• min нижняя граница сектора видимости (в градусах)
• max верхняя граница сектора видимости (в градусах)

Далее проделаем следующие действия:

1. Создадим скрипт построения секторов обзора станций
2. Напишем скрипт обрезки покрытий COVERAGE станций
3. Объединим полученные скрипты для обработки всех станций

Построение секторов станций

Для построения секторов воспользуемся модулем v.in.ascii. Этот модуль позволяет создавать векторные объекты, считывая координаты углов объектов из файла или из stdin. Наша задача -- получить координаты станций, рассчитать границы секторов и подать на вход команды v.in.ascii строки с координатами следующего вида:

B 17
 121.621622 709.97921
 128.378378 709.97921
 ...
 121.621622 709.97921
C 1 1
 121.496622 709.762703649
 1 5

Здесь B 17 говорит о том, что будем создавать границу (boundary) объекта, состоящую из 17-ти точек, координаты которых перечислены в последующих строках. Строка C 1 1 означает, что далее идут координаты центроида, числа 1 5 несут информацию о категории данного центроида (пятая категория в первом слое). Более подробно об этих и других обозначениях см. в документации v.in.ascii.

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

v.sector input=stations output=sectors radius=r x=x y=y min_angle=min max_angle=max

Модуль написан на языке Python и по сути является оберткой над двумя командами v.db.select (извлечение из базы данных параметров, задающих сектора) и v.in.ascii. Более подробную информацию можно посмотреть в исходном коде модуля.

Примеры результатов работы

Примеры фрагментов покрытий представлены на рисунках:

• 

  Рисунок 4. Фрагмент рассчитанного покрытия сети 3G на территории Москвы.

• 

  Рисунок 5. Фрагмент рассчитанного покрытия сети 3G на территории Москвы.