IoT Geofencing: как мы сократили время определения функциональных зон, используя H3-индексы

в 12:42, , рубрики: embedded, geofencing, Uber H3, whoosh

Зоны ограничений

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

Коллеги намекают, что бронь переговорки истекает через три минуты

Коллеги намекают, что бронь переговорки истекает через три минуты

В нашем сервисе есть несколько основных типов зон:

  • Limited — самая большая, где можно ездить (и в принципе допустимо находиться). Все остальные зоны находятся внутри неё. Эту зону вы видите в приложении, как основную

  • Permitted — уже можно не только ездить, но и парковаться

  • Forbidden — нахождение самоката запрещено. Имеет расписание, то есть может быть активной в определенные дни/часы

  • Functional — особый тип; позволяет докидывать новые бизнес правила поверх базовых по мере необходимости. Все зоны ограничения, которые видны в приложении — как раз этого типа

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

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

Как похорошела Казань при кикшеринге

Как похорошела Казань при кикшеринге

Мечтают ли самокаты об IoT модулях?

Небольшое отступление про электронику на борту. Каждый самокат оснащен IoT-модулем; тут можно подробно почитать, зачем.

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

IoT получает от GNSS-модуля текущую координату и основные параметры движения (accuracy, speed, ...), а также ряд других метаданных (timestamp, satelliteNum, …) из GGA, VTG и RMC NMEA-сообщений. Обогащаясь дополнительными данными от других датчиков, получаем сообщение track, которое и уходит по MQTT в наш бэкенд:

{ 
  "type": "track", 
  "src": "GPS", 
  "lat": 51.681629, 
  "lon": 39.220795, 
  "speed": 0.3, 
  "wheel": 0, 
  "accur": 0.7, 
  "heading": 333.76, 
  "gnss_ts": 1664964443000, 
  "pressure": 937.862061, 
  "roll": -17.91, 
  "pitch": -1.29, 
  "yaw": -47.81, 
  "tStamp": 1664961106 
}

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

Backend забирает эти данные, делает свои дела и выдает решение. Звучит отлично — каждый занимается своим делом и не лезет к другому, все довольны.

Или нет?

Проблемы взаимодействия IoT-Backend

Несмотря на нагруженность сервиса и сложность расчетов, процессинг track события работает достаточно быстро (на удивление для меня). Коллеги из бэкенда пытались мне объяснить, как все устроено, но я запомнил лишь кашу из PostgreSQL, PostGIS, Redis и Tile38.

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

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

IoT Geofencing: как мы сократили время определения функциональных зон, используя H3-индексы - 3

Поясню, что есть что:

  • gnss_ts — момент получения самокатом координаты, находящейся в зоне ограничения. Это время GNSS-модуль получает от спутников в GPRMC сообщении и оно предельно точное. Однако есть нюанс — обычно приемники работают с частотой 1Hz, и этот момент измерения координаты может отстоять от zone border на секунду в худшем случае

  • iot sent coord — момент отправки IoT-модулем координаты; мы его не фиксируем, но знаем, что он где-то тут

  • back_ts — момент получения бэком координаты

  • SET cmd — отправка бэком команды на ограничение скорости

  • iot got cmd — получение скутером команды и её обработка; этот момент времени тоже не фиксируем, обработка занимает незначительное время

  • ANS msg — получение бэком сообщения от самоката об успешной обработке команды

По back_ts есть интересный нюанс. Мы долго думали, почему же так плохо работает навигационный модуль — координаты довольно сильно прыгали. Но однажды построили тот же самый трек точками и заподозрили проблему не в модуле, а в том, как эти точки сохраняются в базе данных. Дело в том, что сеть не гарантирует попадание на бэк в том же порядке, в котором координаты были отправлены с железки, что и вызывало показанные ниже артефакты отрисовки. Решение было банально простым — сменить sort key с back_ts на gnss_ts, и проблема ушла. Очевидное решение, понимание которого пришло не сразу…

Слева направо: gnss ts, str(platform ts), platform ts. Сортировка по gnss ts (правильный вариант)

Слева направо: gnss ts, str(platform ts), platform ts. Сортировка по gnss ts (правильный вариант)

Окей, перейдем к оценке происходящего на основе реальных данных. Нас интересует разница во времени между gnss_ts и iot got cmd (при условии, что отправка SET-команды от бэка и ANS-сообщения от самоката занимают примерно одинаковое время):

latency=dt0 + dt1 + dt2/2

Выгрузили из Postgres 1000 поездок, в которых было одно пересечение зоны ограничения скорости, причём был как въезд, так и выезд из неё; получили по ним необходимые метки времени. Ниже приведен график распределения временных интервалов dt0, dt1, dt2, пунктиром отмечены медианы распределений:

IoT Geofencing: как мы сократили время определения функциональных зон, используя H3-индексы - 6

Итого, если взять latency и посчитать её медиану (предпочтительнее, т.к. отбрасывает уж совсем исключительные случаи) и среднее, то получим вот такой результат:

median(iot_got_cmd - gnss_ts)=3.465s \ avg(iot_got_cmd - gnss_ts)=7.138s

IoT Geofencing: как мы сократили время определения функциональных зон, используя H3-индексы - 8

Можно рассчитать перцентили распределения задержек:

  • 75 перцентиль = 5.166 сек

  • 90 перцентиль = 13.846 сек

  • 95 перцентиль = 28.390 сек

То есть:

  • В 90% случаев задержка < 14 сек

  • Задержки, которые < 10 сек, составляют 86.7%

Для наглядности построим функцию их распределения:

IoT Geofencing: как мы сократили время определения функциональных зон, используя H3-индексы - 9

Какие же выводы?

  • Работает, но не очень. Даже идеальные две секунды на rq/rs — слишком много. На полной скорости в 25km/h самокат успеет проехать ~16 метров; а ведь есть зоны, у которых даже ширина меньше

  • Существует много случаев, когда координата или команда идет непозволительно долго, 20% поездок выходят за рамки 10 секунд. 10 секунд, Карл!

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

Стоит добавить, что эта аналитика проводилась для 2G-модулей связи. Переход на 4G заметно улучшил процесс доставки данных в обе стороны, но тогда мы еще этого не знали. Можно использовать более скоростные GNSS (10Hz), можно чаще отправлять данные — но это ближе к оптимизациям, чем к существенному исправлению ситуации.

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

Автономная система геозонирования

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

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

То есть, в плюсах:

  1. Децентрализация части геодезических вычислений вне серверного софта (хотя бэкендеры подсказывают, что им и так нормально)

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

  3. Система продолжает работать при аномалиях работы сети или даже в оффлайне

Минусы:

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

Так давайте же просто скачаем все зоны региона в формате GeoJSON, напишем import geopandas as gpd и быстренько сами все посчитаем на борту, исключив бэкенд!

Правда, есть нюанс...

  • У нас вычислитель (ARM Cortex M4) работает на частоте 100MHz

  • И NV Storage лишь в несколько десятков мегабайт

  • А оперативки — всего 256K, из которой половина отдана под кучу для RTOS

  • Да и питона там нет и судя по всему, уже не будет…

Но все же, попробуем что-то с этим сделать.

Типовые решения

Тут стоить отметить, что ни я, ни ребята из embedded-команды не имеют уверенных знаний и опыта в манипуляции пространственными отображениями, структурами данных и алгоритмами в этой области. Мы решали задачу, исходя и конкретной проблемы сервиса и, делая это, много чего изучали впервые. ГИС-инженер справился бы с этим всем куда лучше. Однако нам требовалось решение, которое можно было бы перенести на IoT-модуль, что отбрасывало большинство типичных подходов и готовых библиотек. Возможно, будут неточности и упущения в ГИС-области — буду признателен, если дополните наши рассуждения в комментариях.

Задача о принадлежности точки многоугольнику — фундаментальная в вычислительной геометрии, и у неё есть несколько классических вариантов решения:

  1. Метод пересечения лучей (Ray Casting) — один из самых простых и интуитивно понятных способов определения местоположения точки. Идея заключается в том, чтобы провести луч из точки в бесконечность и подсчитать, сколько раз он пересекается с гранями многоугольника. Если количество пересечений нечетное, то точка лежит внутри многоугольника, в противном случае — вне. Точки, лежащие точно на ребрах многоугольника, считаются внутренними. Этот метод прост для понимания и реализации, однако может быть вычислительно затратным для сложных многоугольников с большим количеством ребер

  2. Метод суммирования углов (Angle Sum) — использует концепцию суммы внутренних углов многоугольника. Он вычисляет сумму углов, образованных между тестовой точкой и каждой парой точек, составляющих многоугольник. Если эта сумма равна 2π, то точка внутренняя, если 0 — внешняя

  3. Метод пересечения отрезков (Line Segment Intersection) — предполагает анализ того, лежит ли данная точка внутри многоугольника, проверяя ее пересечения с каждым сегментом ребер. Если точка пересекает нечетное количество ребер, она лежит внутри многоугольника, в противном случае — вне. Этот метод отличается простотой и эффективностью, он не требует сложных математических уравнений и может работать с многоугольниками с любым количеством ребер

  4. И другие! Есть еще масса иных примитивных геометрических решений этой задачи. И даже существуют примеры подобных реализаций в embedded

Но мы не стали на них останавливаться. Мы не понимали, как скоро упремся в возможности железки при масштабировании зон и увеличении числа вершин полигонов. Начинали копать в эту сторону довольно давно, когда зоны только начинались — тогда в Москве их было не больше нескольких десятков. Уже в процессе решения задачи зон становилось больше, появлялись скругления (и как следствие, сложность полигонов возрастала на порядки). Все нужно было тщательно бенчмаркать именно с валидным профилем использования, но он настолько динамично менялся, что рабочее решение сегодня могло захлебнуться уже завтра на наших вычислительных мощностях (не стоит нас жалеть, по меркам embedded у нас нормальный вычислитель). В итоге, мы пошли искать что-то более реализуемое, хотя бы в теории. И с запасом под будущие изменения.

Красиво, но страшно

Красиво, но страшно

Выше описана голая теория из википедии, но существуют и очень достойные реализации, применяющие внутри себя какой-то из базовых подходов, поверх которого навешаны разные оптимизации. Например, есть библиотека TG от авторов Tile38 (Ultra Fast Geospatial Database & Geofencing Server).

TG использует индексирование полигонов, делая операции с пространственными отношениями очень быстрыми. В основе она использует Ray Casting алгоритм, но для его ускорения на больших полигонах, сегменты линий индексируются и хранятся в Natural & YStripes структурах, которые являются кастомной надстройкой авторов над R-tree.

Пример R-tree индексанции полигона

Пример R-tree индексанции полигона
И превращение операций O(n) — Ray Casting в операции O(log n) — Ray Casting + RTree

И превращение операций O(n) — Ray Casting в операции O(log n) — Ray Casting + RTree

Звучит уже куда интереснее, но наше внимание привлекли иные подходы к обработке ГИС-данных.

Geohash, Uber H3: кодирование географии в строку

Geohash — это алгоритм, который преобразует географические координаты (широту и долготу) в строку, используя 32 символа: 0-9, b-z, исключая a, i, l, o. Он разделяет земной шар на квадраты, а их еще раз на квадраты, и еще и еще несколько раз. Посмотреть на разбиение карты в онлайне можно здесь.

IoT Geofencing: как мы сократили время определения функциональных зон, используя H3-индексы - 13

Чем больше символов в строке Geohash, тем меньше квадрат, который она представляет, тем точнее указано местоположение. С каждым новым символом в строке Geohash, квадрат делится на 32 равные части, итеративно сужая область область поиска.

Geohash прост в реализации и понимании, хорошо подходит для простого кодирования пары (lat; lng) в строку. Из коробки он больше ничего не умеет, и пока мы думали, как его можно применить в нашей задаче, наткнулись на другое интересное (очень!) решение.

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

IoT Geofencing: как мы сократили время определения функциональных зон, используя H3-индексы - 14

Библиотека на языке С доступна на Github для коммерческого использования. Есть биндинги для других языков и весьма разнообразное API (поиск соседей, вычисление расстояний, иерархии ячеек, построение графов), которое в перспективе можно применять для каких-то иных манипуляций с ГИС-данными на борту транспортного средства. И еще есть пример внедрения у аналогичного бизнеса!

По ходу реcёрча мы наткнулись на статью от американских коллег под брендом LINK. У них указан изначальный Vehicle-Cloud Communications Lag в диапазоне 6 - 30 секунд (хотя нижняя планка, конечно же, странновато высокая), и то, что они смогли сократить время процессинга координаты менее, чем до 1 секунды! И они тоже используют для этого решение, построенное на H3-индексах.

IoT Geofencing: как мы сократили время определения функциональных зон, используя H3-индексы - 15

Никаких деталей технической реализации не приводится, но, тем не менее, мы получили для себя некий референс:

  • Время обработки координаты составляет 0.9 сек

  • Карты загружены в IoT-модуль

  • Обработки происходит на встроенном вычислителе (правда, сказано, что equipped with five microprocessors that work together to quickly synthesize GPS. Ну, пять так пять, будем надеяться, что это просто правки отдела маркетинга)

Звучит, как настало время имплементации и бенчмарков!

Подготовка карт

Подготовка зон, извлеченных из базы данных в перевариваемый IoT формат — ключевая процедура процесса. Затратив пренебрежительно малое время на выборку и процессинг данных, ужав исходные объемы в тысячи раз, мы получаем возможность использовать IoT-модуль для бортовых вычислений. Сейчас расскажу, как все устроено.

В памяти IoT лежит файл _base.json , содержащий данные о конфигурации базовой зоны:

{
	"ver": 1.0,
	"region": "MOW",
	"ts": 1718723274,
	"baseRes": 9,
	"nCells": 21121,
	"maxIntersect": 7,
	"offset": 180,
	"minRes": 7,
	"maxRes": 13
}

И рядом лежит _base.map, содержащий H3-индексы и прочерки, длина которых — maxIntersect * 3 символов:

IoT Geofencing: как мы сократили время определения функциональных зон, используя H3-индексы - 16

Где-то виден лишь H3-индекс (8911aa71b5bffff---------------------), а где-то, кроме него, еще и ссылки на дочерние файлы (8911aa71adbffffaeiatkatlatm---------). Это значит, что в ячейке базовой зоны 8911aa71adbffff обнаружены функциональные зоны aei , atk , atl и atm . А это в свою очередь значит, что в той же папке лежат файлы aei.map , atk.map , atl.map и atm.map. И еще мы решили, что трех символов будет с запасом достаточно на потенциальный рост числа функциональных зон с учетом мощности используемого алфавита.

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

Нужно выдерживать постоянный оффсет между переходами среди H3-индексов — ведь файл отсортирован по ним, а значит, по нему можно пробежаться бинарным поиском. Для Москвы baseRes получился 9; в каждую ячейку с этим разрешением попадает от 0 до 7 функциональных зон. Конечно, это может изменится с любой новой итерацией добавления полигонов, поэтому расчет и оценку баланса берет на себя скрипт анализа и подготовки данных.

Так выглядят дочерние зоны, разбитые на ячейки с разным разрешением, на фоне базовой зоны (H3-индекс 8a11aa784a8ffff):

IoT Geofencing: как мы сократили время определения функциональных зон, используя H3-индексы - 17

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

Однако в H3 не просто ячейки с индексами, они иерархичны. У каждой ячейки, не считая ячеек самого большого и самого маленького разрешения, есть родительская ячейка и набор дочерних ячеек. Таким образом, если в массиве индексов некоторый набор ячеек имеет одного общего родителя, то логично этот набор заменить одним — родительским. И так далее по иерархии, пока у нас не останутся ячейки, которые уже невозможно схлопнуть . Для этого в библиотеке H3 есть функция compact; она выполняет сжатие массива индексов, причем без потерь.

Для понимания приведу пример зоны, заполненной тремя разными способами.

Зона заполнена ячейками с разрешением 7. Границы зоны заполнены не очень. Индексов — 11 —Зона заполнена ячейками с разрешением 10. Границы зоны заполнены идеально, но индексов — 39902

Зона заполнена ячейками с разрешением 7. Границы зоны заполнены не очень. Индексов — 116
Зона заполнена ячейками с разрешением 7. Границы зоны заполнены не очень. Индексов — 116

Зона заполнена ячейками с разрешением 10. Границы зоны заполнены идеально, но индексов — 39902
Разрешение по-прежнему 10, но применен compact. Границы всё также хороши, индексов — 2108

Разрешение по-прежнему 10, но применен compact. Границы всё также хороши, индексов — 2108

Таким образом, compact позволяет нам достаточно плотно заполнять зоны, не раздувая объем файлов с картами.

Вот только… Вы тоже обратили на это внимание? Там же дырки теперь по всей зоне!

Да, действительно. Но это вообще не проблема. Проблема тут скорее в том, чтобы объяснить, почему это всё-таки не проблема. Короче, следите за руками.

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

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

Возьмем в пример эту точку

Возьмем в пример эту точку
Превратим её в индекс с максимальным разрешением (в нашем случае 10). Такого индекса в нашей зоне нет. Пойдем искать родителей

Превратим её в индекс с максимальным разрешением (в нашем случае 10). Такого индекса в нашей зоне нет. Пойдем искать родителей
Неа

Неа
Все еще нет

Все еще нет
И снова нет такого индекса

И снова нет такого индекса
Кажется, нашелся

Кажется, нашелся
Да, это оно

Да, это оно

На последней картинке видно, что красный контур совпадает с одной из желтых ячеек. То есть выбранная точка находится в зоне! Несмотря на то, что изначальный индекс с разрешением 10 в файле отсутствует, один из его родителей (а точнее прапрадедушка) всё-таки нашелся в compact списке.

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

Каждый из дочерних файлов содержит метаданные, с помощью которых происходит его разбор. Записаны они в начале файла в формате JSON.

{
	"ver": 1.0,
	"ts": 1718723274,
	"type": "SPEED_LIMIT",
	"speed_limit": 10.0,
	"res13": 1226,
	"res12": 460,
	"res11": 186,
	"res10": 62,
	"res9": 4,
	"schedule": []
}

res9 - res13 в данных выше — это последовательность доступных разрешений, образующих зону после compact-сжатия. H3-строка всегда постоянной длины, и при низком разрешении происходит замена избыточной информации символом f , поэтому мы всегда имеем постоянный оффсет и можем пройтись по файлу бинарным поиском. Само собой, при подготовке H3-индексы отсортированы. Будем проверять все разрешения, от высокого к низкому, применяя библиотечную операцию cellToParent, и каждый инкремент искать новую строку.

Именно этот файл содержит указание, что нужно делать (speed limit 10km/h), расписание, по которому нужно работать (тут пустое), и иные метаданные, необходимые для управляющего воздействия. Если искомая строка найдена — данные вычитываются и передаются на исполнение другим системам транспортного средства.

Подготовленные карты занимают 4.2Мб в несжатом виде. И на 18 июня 2024 г. являются актуальным отображением карты функциональных зон кикшеринга Москвы для процессинга на стороне IoT-модуля.

IoT Geofencing: как мы сократили время определения функциональных зон, используя H3-индексы - 28

Алгоритм работы IoT

Покажу на примере одной из московских зон. Первое действие — валидировать конфигурацию _base.json, открыть _base.map и держать файл открытым все время работы модуля — он нужен каждый цикл поиска, а операция открытия файла f_open довольно длительная (~10ms). Для хранения мы используем карту памяти формата uSD с файловой системой FAT32, а для работы с ней — модуль FATFS.

IoT Geofencing: как мы сократили время определения функциональных зон, используя H3-индексы - 29

Переведя пару (lat; lng) в H3-индекс с базовым разрешением, можем пройтись по отсортированному файлу. Если ничего не найдем, то самоката нет в доступной для проката зоне; в противном случае мы получим от 1 до maxIntersect вхождений, которые закодированы в строке abgabhahl------------ :

Логи процесса поиска дочерних зон в базовой

Логи процесса поиска дочерних зон в базовой

Теперь нужно перебрать все дочерние зоны. В их файлах просто перечислены H3-индексы зоны в compact-виде, кластеризованные по разрешению и отсортированные по алфавиту:

IoT Geofencing: как мы сократили время определения функциональных зон, используя H3-индексы - 31

Несмотря на разные разрешения, длина H3-строки — константна, что позволяет двигаться по оффсетам, достигая высокой скорости обхода бинарным поиском. Для каждого нового разрешения используется операция cellToParent , пока не закончатся валидные разрешения или вхождение не будет найдено.

IoT Geofencing: как мы сократили время определения функциональных зон, используя H3-индексы - 32

В логе поиска видно, что точка нашлась в abh зоне, а до ahl мы не дошли:

Логи процесса поиска искомой точки в списке дочерних

Логи процесса поиска искомой точки в списке дочерних

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

Что по времени?

Второе поле в логах — тики системного таймера длиной в 1 мс. Между стартом поиска и нахождением точки прошло 102108 - 102010 = 89 мс. Попробуем посмотреть, что же происходит на большей выборке.

Мы подготовили тестовый скрипт, который вытаскивает все зоны из региона и ставит тестовые точки внутри них, вне их и еще в разных, потенциально интересных местах. Для каждой точки мы прописываем ожидаемый референс работы, сохраняем в CSV-файл и отдаем на обработку IoT-модулю — так мы тестируем, что он отрабатывает карту региона согласно ожиданиям.

Результат бенчмарка при выполнении скрипта выше

Результат бенчмарка при выполнении скрипта выше

То есть:

  • Для Москвы у нас получились 1682 тестовые точки

  • Общее время обработки всего CSV-файла на IoT ~40 сек

  • Среднее время обработки ~20 мс

  • Максимальное время обработки ~132 мс

  • За предел в 100 мс выходит лишь 5 точек

  • Большинство точек лежит вне функциональных зон и на их обработку тратится от 10 до 20 мс

  • Обработка большинства точек внутри функциональных зон происходит в пределах 20 — 50 мс

Выглядит, как победа!

Результаты

  • Мы смогли найти подходящее решение в рамках заданных ограничений

  • Оно работает очень быстро. Даже быстрее, чем предполагали!

  • Стандартная частота выдачи сообщений от GNSS-модуля — 1Hz, а значит раз в секунду будет запускаться код поиска. Такие тайминги микроконтроллер c RTOS вполне переварят и это не повлияет на производительность остальных потоков

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

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

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

Выводы

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

Отдельного восхищения заслуживает библиотека от Uber! Мы полюбили этот инструмент и активно пользуемся при решении некоторых ГИС-задач, но уже не на микроконтроллерах.

Хочу ещё раз проговорить, что переход на LTE Cat1 существенно улучшил latency общения с бэкендом. Проблема долгой доставки координат частично ушла в том объеме, что мы наблюдали на 2G-модулях. Тем не менее, скорость работы нашего on-the-edge-решения все еще на порядок выше.

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

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

Что дальше?

Что бы использовать это в проде, файлы должны синхронизироваться за адекватное, прогнозируемое время с использованием минимального количества трафика. Ну и не проблема, ведь есть rsync! Сейчас все проверим и быстро сделаем:

   __      ___  _  ___   ___  ___ _  _
        / / || |/ _  / _ / __| || |
     // /| __ | (_) | (_) __  __ |
     _/_/ |_||_|___/ ___/|___/_||_|

                | |         | |          
   ___ _ __ ___ | |__     __| | _____   __
  / _  '_ ` _ | '_    / _` |/ _   / /
 |  __/ | | | | | |_) | | (_| |  __/ V /
  ___|_| |_| |_|_.__/   __,_|___| _/ 

Serial Shell Service started...
 * Firmware version: 5.1.2
 * Project: iot
 * Type: app
 * Tag: prd
 * Platform: m4r0c0
 * BSP: 0
 * ADEQ: 93d1df
 * GIT hash: c3b13f
 * Comment: 
 * Build date/time: Aug 14 2024 00:09:17
 * GIT Branch: feature/ed-c74abe/geofencing_on_iot
 * MCU UID: 06000500361fb9d64aba7cc4

service@IoT> rsync --version
Unknown command name "rsync"!
Так, падажжи...

Так, падажжи...

Блин, точно.

У нас же микроконтроллер.

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

Автор: Katbert

Источник

* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js