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

В данной статье описывается пример использования библиотеки GeoAlchemy -- расширения библиотеки SQLAlchemy, которое предназначено для работы с пространственными БД. В качестве иллюстрации выбрана задача расчета покрытий базовых станций сотовой сети.

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

Краткие сведения о SQLAlchemy и GeoAlchemy

Библиотека на языке Python с открытым исходным кодом SQLAlchemy -- предназначена для работы с реляционными СУБД с применением технологии ORM. Она служит для синхронизации объектов Python и записей реляционной базы данных. SQLAlchemy позволяет описывать структуры баз данных и способы взаимодействия с ними на языке Python без использования SQL.

GeoAlcemy -- пространственное расширение библиотеки SQLAlchemy, позволяющее производить обработку пространственных данных. В настоящий момент GeoAlchemy поддерживает такие базы данных и их пространственные расширения, как PostGIS, Spatialite, MySQL, Oracle, и MS SQL Server 2008.

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

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

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. 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

На начальном этапе 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.

Построение модели GeoAlchemy

Данные по базовым станциям и их покрытиям будем хранить в БД PostgreSQL с пространственным расширением PostGIS.