Привет, Хабр! Меня зовут Даулет Курмантаев, я дата-сайентист в крупной казахстанской телеком-компании. Работаю в отделе Customer Experience Management. Мы анализируем качество связи и автоматизируем решения по строительству и модернизации базовых станций.

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

Почему важно знать уровень сигнала

Чтобы улучшать качество связи, нужно понимать, где она стабильная, а где нет. Это помогает:

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

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

Данные от 3GPP (MDT)

На рынке уже есть отличное решение от стандартизатора мобильных сетей 3GPP. Там разработали протокол MDT — Minimization of Drive Tests. Он позволяет смартфонам клиентов автоматически собирать и передавать данные о качестве связи оператору.

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

Временное решение: Speedtest

Пока ждём запуска имплементации MDT, используем датасет Ookla. Приложение Speedtest собирает информацию о скорости интернета и геолокации пользователей. Мы покупаем этот датасет, агрегируем данные и строим карты покрытия, которыми могут пользоваться коллеги из коммерческого и технического отделов. Для визуализации используем геоячейки H3 с разрешением 11 и стороной 25 метров.

Интерполяция: как предсказать сигнал там, где его никто не измерял

Данные Ookla полезны, но тоже адски кластеризованы: в оживлённых местах, в центрах городов и вдоль трасс измерений много, а в непопулярных местах и на окраинах их почти нет.

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

Как проверяем точность интерполяции

Чтобы валидация моделей была более честной, убираем все точки в радиусе 75 метров от той, которую хотим предсказать. Обычное разбиение на тренировочную и тестовую выборку здесь не подходит – оно создаёт корреляции между точками и искажает результаты.

Мы используем метод jackknifing или «складной нож»: удаляем по одной точке → интерполируем её значение → считаем ошибку → повторяем много раз, чтобы получить среднюю ошибку.

Теперь более подробно расскажу о методах интерполяции, которые мы используем.

Метод ближайших соседей (kNN)

Мы предполагаем, что уровень сигнала в какой-то точке будет похож на уровень в ближайших к ней точках. Алгоритм находит заданное количество соседей и вычисляет среднее значение. Это простой и быстрый способ со сложностью 0(nlog(n)).

Допустим, у нас есть точка без измерений. Алгоритм ищет N ближайших точек с известными значениями и усредняет их. Проблема в том, что этот метод не учитывает расстояние между точками. Если один сосед находится в 5 метрах, а другой — в 100, их влияние на предсказание будет одинаковым.

Чтобы это исправить, используем взвешивание (IDW – Inverse Distance Weighting): чем ближе точка, тем больше её вес. Так интерполяция становится более точной.

Обычно kNN и IDW смешиваются, чтобы получить небольшой сабсет соседей и на них уже делать обратное взвешивание по расстоянию.

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

Как это решить? С помощью кригинга.

Кригинг

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

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

Немного проанализируем дальше — что нам это даёт?

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

Вектор справа учитывает близость: чем ближе точка к той, что мы хотим интерполировать, тем больше будет ковариата.

Как найти ковариацию?

Ключевая идея: ковариация между двумя точками зависит только от расстояния между ними.

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

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

Чтобы найти ковариацию экспериментально, можно:

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

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

Зная функцию ковариации, мы можем:

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

У кригинга при этом есть пара значительных ограничений:

Высокая вычислительная сложность. Расчёт ковариации для всех точек требует ресурсов 0(n²). Обратная матрица занимает 0(n³) по сложности. Само предсказание линейное от n – 0(n).
Не учитывается физика сигнала. Метод опирается только на географическую близость, но не на законы распространения радиоволн, что важно для мобильной связи

Универсальный кригинг

Более прогрессивная версия кригинга — универсальный кригинг или regression kriging. Это когда ожидание интерполяции будет не постоянной величиной, а результатом определённой модели.

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

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

Получается, осталась только вычислительная сложность. Это решается тем, что мы делаем кригинг локально. Вместо того, чтобы для предсказания интерполируемой точки использовать всех соседей, берём только какое-то N ближайших к ней.

Добавляем физику

А теперь давайте поговорим про физику уровня сигнала.

Величина, которую мы хотим предсказать, называется RSRP — Reference Signal Received Power. Это мощность сигнала, которую получает устройство клиента.

Что влияет на сигнал:

Расстояние до антенны. Мощность сигнала зависит от расстояния — чем дальше антенна, тем хуже сигнал.
Положение антенны. Уровень сигнала зависит от того, куда направлена антенна.
Среда. Есть эффект fading, связанный с различными макрофеноменами в окружающей среде — здания, деревья, рельеф, которые добавляют свою стохастичность. А ещё есть small scale fading — это абсолютно случайные явления, которые почти невозможно предсказать. Например, когда в одном углу комнаты есть связь, а в другом — нет. Также на сигнал влияют другие факторы: погода, влажность.

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

Мы построили нашу модель RSRP как линейную регрессию множества различных параметров, а именно:

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

В итоге получаем не просто интерполяцию, а модель, отражающую реальное поведение радиоволн.

Поэлементный универсальный кригинг

Как уже отмечалось, вычислительная сложность кригинга — O(n³). Это делает метод дорогим при обработке больших объёмов данных. Однако сложность можно значительно снизить, если выполнять интерполяцию отдельно для каждой радиосоты, а затем агрегировать результаты.

Допустим, в сети есть k сот. В среднем каждая из них содержит n/k точек измерений. Тогда кригинг для одной соты займёт O(n³/k³), а для всех сот — O(n³/k²). Если в сети около k ≈ 30 000 сот, ускорение составит 30 000² = 900 000 000 ≈ 1 миллиард раз, хотя сложность остается кубической.

Агрегация покрытия индивидуальных сот

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

Однако этот подход создает проблему, которую проще всего объяснить на примере. Представим, что в некоторой точке сота A показывает уровень RSRP -100 дБм. А при интерполяции из соседней соты B получается, что в этой же точке уровень RSRP -90 дБм. При агрегации окажется, что в данной точке покрытие обеспечивает сота B с уровнем -90 дБм, что противоречит реальным измерениям.

Эта сложная проблема, которая аналогична компромиссу между смещением и дисперсией (bias-variance trade-off): что учитывать — фактические данные одной соты или предсказание модели для соседней соты?

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

В примере выше у нас есть предсказанные значения RSRP для сот A и B (-100 и -90 дБм), а также их стандартные отклонения. Поскольку измерения для соты А были сделаны прямо в интересующей нас точке, её стандартное отклонение будет маленьким (менее 5 дБм). У соты B значение RSRP интерполировано на некотором удалении от точек с фактическими измерениями, поэтому стандартное отклонение предсказания сильно выше — до 25 дБм.

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

где c — настраиваемый параметр, определяющий баланс между измерениями и предсказаниями.

Дополнительные преимущества поэлементного кригинга

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

Какой метод интерполяции эффективнее

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

Что дальше?

У нас есть хороший рабочий прототип, но это не предел возможностей. Мы продолжаем улучшать качество входных данных, добавлять новые фичи и более сложные модели.

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

Если у вас есть вопросы, предложения или идеи — пишите в комментариях, обсудим!

Подготовка текста и редактура: Виктория Русакова

Геоинтерполяция от А до Я: как создать карту покрытия сети