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

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

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

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

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, и которая связана с БД, содержащей следующие поля (естественно, что названия полей могут быть иными):

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

Был написан модуль v.view.areas (язык реализации -- Python), который производит расчеты покрытий согласно приведенному выше алгоритму.

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

 v.view.areas cat=id input=stations output=result radius=r x=x y=y min_angle=min max_angle=max 

В последующих разделах рассмотрены основные части модуля, выполняющие соответствующие этапы алгоритма:

1. Построение секторов обзора станций.
2. Циклическая обработка всех секторов обзора для вычисления покрытий COVERAGE станций.

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

Для построения секторов воспользуемся модулем 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. Детали реализации можно посмотреть в исходном коде модуля.

Модуль обрезки покрытий

Был реализован вспомогательный модуль v.clip.by.maps, отвечающий за построение покрытия конкретной базовой станции. Модуль принимает на вход следующие параметры:

• input -- название карты, в которой хранится сектор обзора станции, для которой рассчитывается покрытие;
• prefix -- префикс названий карт, в которых хранятся сектора обзора станций;
• output -- название выходой карты, в которой будет храниться покрытие станции.

Данный модуль считывает названия карт в список names и последовательно производит обрезку сектора. Наиболее важные действия происходят в цикле:

for currentSECT in names:
   # Найти пересечение покрытия COVERAGE и текущего сектора currentSECT.
   # Вычислить тот участок пересечения, который лежит ближе к сектору currentSECT, чем к покрытию.
   grass.run_command(
       'v.cliparea',
       input=currentSECT, cutter=COVERAGE, output=tmp_clipped_map
   )
   # Отрезать от COVERAGE этот участок пересечения. 
   grass.run_command('v.overlay',
       ainput=COVERAGE, binput=tmp_clipped_map, output=tmp_overlay_map, operator='not',
       flags='t',
       overwrite=True, quiet=True
   )
   # Заменяем out_map на результат обрезки покрытия
   grass.run_command('g.copy', vect='%s,%s' % (tmp_overlay_map, COVERAGE), overwrite=True, quiet=True)

Содержимое цикла несколько упрощено по сравнению с реальным кодом, детали реализации можно посмотреть по приведенной выше ссылке.

Также можно заметить, что в данном цикле используется еще один вспомогательный модуль v.cliparea, вычисляющий участок сектора currentSECT, который необходимо отрезать от COVERAGE. Модуль извлекает местоположения базовых станций из карт COVERAGE и currentSECT (они хранятся как центроиды соответствующих полигонов), и расчитывает уравнение секущей прямой, которой обрезается покрытие currentSECT (см. рисунок 2).

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

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

• 

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

• 

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