Наша инфраструктура для фильтрации потоков местоположения в режиме реального времени

Перевод статьи Our framework for real-time filtering of location streams, автор - hypertrack.com

Одна из самых больших проблем с непрерывным отслеживанием местоположения связана с изменчивым качеством показаний GPS смартфона. На точность GPS влияет множество факторов, таких как:

  • Качество приемника GPS
  • Источник сигнала (триангуляция башни ячейки WiFi)
  • Окружающая среда (наблюдение за горизонтом в режиме видимости в открытом пространстве)
  • Состояние устройства (начальное исправление режима полета в режиме низкого энергопотребления)

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

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

На высоком уровне у нас есть две категории фильтров. Двоичные фильтры (да / нет) для удаления шумных датчиков и фильтров GPS для точной настройки показаний GPS для более гладких полилиний и точного расчета расстояния. Двоичные фильтры смотрят на атрибуты показания GPS (временная метка точности скорости источника) и применяют эвристику вокруг кластеризации ускорения расстояния, неподвижной по сравнению с перемещением и т. Д., Чтобы отсеять неточные показания GPS. Фильтры настройки являются более алгоритмическими и ресурсоемкими по своей природе. Хотя каждый из них достоин отдельного блога (скоро), я дам краткий обзор наших корректирующих фильтров:

  • Фильтр Калмана. Использует прошлый поток местоположения для прогнозирования следующей координаты GPS, которая затем взвешивается (используя шум) против фактического показания GPS для получения конечных координат. Это интенсивное вычисление и требует прошлых чтений для построения исторических моделей. Мы считаем это эффективным при исправлении ошибок в шумных данных.

  • Фильтр OSM: использует общедоступные данные RoadStreetMap и отображает наши следы GPS до ближайших возможных дорог. Это последний фильтр в нашем конвейере и принимает следы GPS, которые были отфильтрованы всеми другими фильтрами и привязали их к дороге. Это интенсивность данных и требует много запросов к БД, но мы оптимизировали ее для работы в десятки миллисекунд. Следующий снимок экрана показывает, как мы берем необработанные показания GPS (красные маркеры) и отображаем их на дорогах (синие маркеры).

Пример-3

Давайте рассмотрим некоторые из наших конструктивных ограничений. У нас есть сотни драйверов, отправляющих тысячи показаний GPS через наш драйвер SDK. Крайне важно быстро и эффективно обрабатывать этот поток входящего местоположения, чтобы мы могли отображать состояние в реальном времени этих драйверов. Каждая незначительная задача (включая фильтрацию) должна выполняться асинхронно, чтобы иметь минимальное время поворота, чтобы сохранить батарею на телефоне водителя. Мы поддерживаем автономный режимгде водителям необходимо продолжать работу с приложениями через неоднородные или отсутствующие сетевые области в течение длительных периодов времени. Когда сеть восстанавливает резервные копии, их накопленные местоположения отправляются на сервер при параллельных пакетных вызовах. Следовательно, сервер не может полагаться на получение сообщений в том порядке, в котором они были записаны, и должен иметь возможность обрабатывать потоки местоположения вне порядка .

Чтобы удовлетворить эти ограничения, нам понадобилось хранилище данных в памяти, которое может поддерживать упорядочение сообщений. Мы выбрали комбинацию Redis SortedSet & Hashes для хранения горячих данных, т. Е. Последних X часов показаний GPS для каждого драйвера, который мы отслеживаем. SortedSet поддерживает упорядочение по меткам времени и имеет интерфейс для извлечения ключей до и после заданного ключа (контекст необходим для фильтрации). Хэши отлично подходят для хранения реальных объектов для быстрого поиска. Наконец, мы используем сельдерей с CloudAMQP для асинхронной обработки.

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

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

Пример-2.jpg

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

Мы с удовольствием создаем платформу отслеживания местоположения, и вам понравится использовать ее. Подпишитесь на HyperTrack, чтобы опробовать наши API. И следите за обновлениями, чтобы узнать больше о наших внутренностях!