Самокаты и их место в этом мире

Если кратко, то знать местоположение скутера для нас критически важно по трём причинам:

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

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

3. Чтобы контролировать, что кто-то из юзеров по ошибке (или целенаправленно) не оказался вместе со скутером за пределами зоны работы сервиса.

Помимо перечисленных пунктов есть и другие проблемы, которые возникают если теряются координаты скутера, но они как правило не так болезненно сказываются на работе сервиса.

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

Немного обо всей этой спутниковой магии

Вокруг Земли летают специальные спутники (GPS, ГЛОНАСС, BeiDou, Galileo и так далее — в зависимости от того, кто их запускал) и постоянно шлют вниз специальные сигналы. Приёмник (напр. современный телефон) эти сигналы ловит и обрабатывает. Большое значение здесь имеет время, точнее часы — всё должно быть чётко синхронизировано. В сигнале содержится информация о времени его отправки со спутника, и, сверяя его со временем прихода, приемник определяет сколько этот сигнал до него шёл. Далее, зная скорость распространения (а для радиоволн, коими являются спутниковые сигналы, это скорость света), приёмник определяет расстояние до данного спутника — псевдодальность. Но одной такой псевдодальности недостаточно, поэтому нам нужно видеть несколько спутников (минимум три, но чем больше, тем лучше).

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

А вообще, если есть желание почитать подробнее про GPS, то очень рекомендую этот сайт — это лучшее описание спутниковой навигации, что я встречал.

А проблема-то в итоге в чём?

Справедливо напрашивается вопрос: спутники же никуда не делись, и продолжают отправлять свои сигналы, почему же тогда навигация сломалась? И если она все же сломалась, то почему бы её не починить?

Ответом будут два слова, которые звучат как стиль танца, но на деле являются методами радиоэлектронной борьбы — jamming и spoofing. Ну а на нашем это просто глушилки.

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

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

На самом деле, даже в гражданских приемниках имеются всякие дополнительные модули, которые пытаются не дать навигатору сбить себя с толку (напр. инерциальная система навигации), но это как классическая история замка и отмычки — чем сложнее замок, тем изощреннее отмычка. Ну и чтобы узнать действительно ли оно работает, можете поспрашивать жителей Воронежа или Ростова‑на‑Дону как там у них с навигацией. Или спросить любого москвича, который время от времени стабильно телепортируется в аэропорт Шереметьево.

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

То есть всё-таки получается, что спутниковая навигация - В С Ё...

Проблема ясна, как будем решать?

И вот тут хочется передать слово капитану Очевидность озвучить одну важную мысль:

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

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

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

Осталось только понять как на основе этих сигналов определять расстояние. И вот тут уже становится немного сложнее. По сути, мы можем использовать всего два свойства распространения сигналов: скорость и мощность (ну или время и затухание). С первым мы уже знакомы по ГНСС. А второе использует тот факт, что сигнал затухает (т.е. теряет мощность) по мере распространения. Это позволяет на стороне приемника приблизительно оценить расстояние до источника, при условии, что известна изначальная мощность сигнала и известен закон распространения. Звучит вроде бы элементарно, но на деле есть нюанс, причем далеко не один. Предлагаю отдельно рассмотреть каждый из наших ориентиров и определить какие возможности и сложности есть для определения расстояния до них.

Базовая станция (в нашем случае 4G)

• Уровень принимаемого сигнала: всегда имеется в наличии, НО неизвестна мощность передатчика и среда слишком сильно влияет на затухание (много препятствий и наличие отражений сигналов);

• Время распространения: есть механизм Timing Advance и он даёт точность порядка 50м, НО находится под капотом работы сети и как правило от модема его не получить.

WiFi точка доступа

• Уровень принимаемого сигнала: аналогично с базовой станцией;

• Время распространения: есть технология RTT, НО она доступна только на самых современных устройствах.

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

Впрочем, если всё же не гнаться за точностью, а пытаться получить хоть какое‑то местоположение на основе имеющейся информации, то в целом нам и не нужно определять расстояние до ориентира, достаточно лишь информации о том, что он где‑то рядом. На самом деле, учитывая примерную дальность 4G вышки, которая не превышает несколько километров (а в условиях города из‑за плотной застройки она еще меньше), получение сигнала конкретной вышки уже говорит о том, что мы от неё неподалёку. А с wifi точками доступа ситуация еще лучше, потому что обычный роутер бьёт не дальше чем на несколько сотен метров.

Итого, допустим мы имеем скутер А и мы знаем, что он находится в точке 1. Тогда набор wifi точек доступа и базовых станций, сигнал которых видит скутер А, также находится неподалёку от точки 1.
Следовательно, в случае если мы имеем скутер Б, местоположение которого на данный момент неизвестно, но нам известно, что он видит примерно те же wifi точки и базовые станции, что и скутер А, то мы можем с определенной долей уверенности сказать, что скутер Б находится приблизительно в точке 1.
Таким образом, мы с вами снова изобрели велосипед, точнее так называемый fingerprinting.

Однако и тут не без нюансов.

Когда мы говорим о местоположении, то мы в первую очередь подразумеваем пару широта/долгота. И справедливо возникает вопрос: а точки (55.755864, 37.617698) и (55.755865, 37.617699) это одно и то же местоположение или нет?

Можно конечно попробовать ограничить количество знаков после запятой, сказав что вот после этой циферки нам уже не надо. Но на самом деле эти циферки - это градусы и с реаль��ым пространством, которое мы привыкли воспринимать в метрах, оно соотносится не столь однозначно. То есть 1° широты составляет ~111 км, а вот долгота зависит от широты и 1° долготы может быть как всё те же ~111 км (на экваторе), так и всего ~19.3 км.
Но что если всё-таки придумать как динамически обрабатывать значения в градусах и... В этот раз предлагаю ничего не изобретать, а воспользоваться уже знакомой и можно сказать излюбленной нами системой геопространственного индексирования h3 от компании Uber. Она позволяет конвертировать координаты в специальные индексы, которым в пространстве соответствует шестиугольные ячейки определенного размера.

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

Значит, получаем следующий рецепт:

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

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

В общем, охапка дров и location готов...
Ну а если серьезно, то большому счёту, суть подхода сводится к решению двух задач.
При решении первой задачи, для каждого скутера, чьё местоположение нам известно, мы фиксируем список видимых wifi точек и базовых станций (то есть отпечаток, fingerprinting, уловили, да?)), а также соответствующий h3 индекс и собираем всё это в базу.
Далее, для решения второй задачи, то есть для определения местоположения скутера, нам необходимо сформировать аналогичный отпечаток, и найти максимально на него похожий среди всех тех, что есть в нашей базе. Тогда h3 индекс, соответствующий полученному отпечатку, и будет определять область пространства, в которой находится искомый скутер.

Я уже вижу, как вдумчивые читатели к этому моменту начинают негодовать. Мол, «если у тебя координат вообще нет, то как ты свою базу наполнять собрался?»
Хороший вопрос. Следующий вопрос.

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

И еще, во всей этой истории имеется два допущения:

• Мы считаем, что WiFi точки и Базовые станции как правило статичны, то есть единожды собрав базу, у нас нет необходимости ежеминутно её обновлять (хотя это не мешает нам ввести некий TTL для измерений и периодически базу подчищать);

• В качестве идентификатора WiFi точки доступа мы используем mac адрес и предполагаем, что он уникален (что не совсем так), а также что каждый отдельно взятый mac адрес виден в ограниченном числе ячеек и не может например встречаться в разных регионах (тоже не совсем так, но и с этим можно бороться)

Пример реализации

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

{
    "cell": "250_01_457B_00485A0B",
    "wifi": [
        "50:ff:20:03:69:80",
        "d4:72:26:3f:20:7e",
        "b0:95:75:5e:5a:1e",
        "92:4d:05:cc:be:71",
        "e4:18:6b:6c:03:78",
        "b4:1c:30:ef:17:16",
        "e4:fd:a1:e8:cc:a3",
        "b0:4e:26:c7:70:61",
        "28:3b:82:59:40:11",
        "bc:75:74:c2:38:84",
        "b0:be:76:54:40:b6",
        "9c:5c:8e:ae:c2:34",
        "52:ff:20:42:bc:14"
    ],
    "coord": {
        "lat": 55.823082,
        "lon": 37.385208
    }
}

Ну и соответственно наличие поля coord определяет используем мы эту информацию для пополнения нашей базы или наоборот пытаемся получить местоположение потерявшегося скутера. Если это поле есть, то мы конвертируем его в h3 индекс и для каждого из mac адресов делаем запись в базу, в итоге получая что-то вроде:

Примерно тоже самое мы делаем и для базовой станции.

А вот если координата нам не известна, то мы идём как бы от обратного и достаём из нашей базы все h3 индексы соответствующие полученным mac адресам и ищем среди них самый часто встречающийся. Иными словами, пытаемся определить на отпечаток какого из h3 индексов имеющихся в базе максимально похож наш текущий.
Собственно на карте частотность h3 индексов, полученных по исходному набору wifi точек выглядит следующим образом:

В итоге, нам достаточно выбрать любую из желтых ячеек (яркость соответствует количеству вхождений), и мы имеем приемлемое по точности местоположение, определенное по wifi точкам. Даже не верится, что оно работает.

Ну и напоследок несколько интересных фактов:

• на момент 23го года в Москве и области в зоне работы нашего сервиса было обнаружено 2.5 млн уникальных mac адресов (это уже с предварительной фильтрацией мобильных точек доступа, но без учёта 5 ГГц точек - их наши модемы не видят)

• был обнаружен загадочный mac адрес (ce:2d:e0:5e:c3:9f), который встречается по всей Москве (впоследствии оказалось, что это всё городская wifi сеть MT_FREE, но для меня всё еще загадка, как они сделали её всю под одним mac адресом)

• в среднем наш скутер видит порядка 8 различных точек доступа (опять же, это для Москвы и для нашего конкретного модема), что не так уж мало, если задуматься. То есть у нас реально повсюду есть WiFi и вот вы сейчас сидите и читаете это, а пространство вокруг вас буквально кишит разными сигналами... Слегка шокирующая мысль, не так ли?

С вами был Фарук, надеюсь вам было интересно вместе со мной изобретать новый способ позиционирования. И как обычно, увидимся в комментариях ;-)