Алгоритм позиционирования на основе метода K-ближайших соседей

Существуют разные алгоритмы позиционирования в помещениях. Помимо алгоритма зональной локализации возможно использовать классический метод K-ближайших соседей (KNN) для определения местоположения пользователя.

Позиционирование методом KNN требует специальной процедуры обхода и измерения данных радиосигналов биконов (BLE/WiFi) в нескольких целевых точках с помощью устройства Android с установленным приложением Navigine.

Требования:

• установленная инфраструктура маяков (BLE/WiFi);
• внедренные карты локации (привязка к реальной геометрии помещения на этапе сбора данных);
• собранные данные радиокарты;

Измерения и контекст

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

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

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

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

Navigine SDK

Профессиональные решения для indoor позиционирования в реальном времени для мобильных приложений.

Больше

Что такое «ориентир» в контексте KNN позиционирования?

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

В данном алгоритме, вместо положения маяков, регистрируются точки на карте (положение в пространстве) с известными координатами и историей наблюдений в каждой точке измерений в пределах видимости - для удобства, они называются ориентирами или целевыми точками. Эти точки являются атрибутами карты. Пример карты с ориентирами приведен ниже:

На рисунке показан пример карты (оранжевым цветом подсвечена геометрия этажа) с точками ориентирами (круги). Можно сказать, что пример лога будет состоять из 20-100 местоположений точек доступа и 10000 наблюдений RSSI от 20-50 обнаруженных передатчиков для одного местоположения.

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

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

Основная концепция алгоритма KNN локализации:

• вычислить расстояние от текущего положения до других ориентиров с заранее известным местоположением
• по текущим радиоизмерениям – соотнести данные измерений и данные для ориентиров
• выбрать первые K-точки выборки
• рассчитать положение выбранным K ориентирам

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

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

Центроидная оценка дает правильную оценку координаты,если на карте существует достаточное количество ориентиров. Если текущая координата видна из всех точек ориентиров, то результатом центроидной оценки является центр координат ориентиров.

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

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

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

Сфера применения алгоритма KNN позиционирования

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

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

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

Демо-видео для KNN

Карта признаков для этого алгоритма относительно большая по сравнению с обычной картой передатчиков. Необходимо около 20-50 маяков на помещение. При использовании зонального алгоритма, необходимо только 50 координат маяков и геометрия помещения. Для KNN, для этажа такого же размера, необходимо порядка 100 точек ориентиров и 2-3 минуты измерений в каждой точке (1000+ RSSI наблюдений от всех обнаруженных маяков в данной локации). Для 100 точек доступа сохраняются средние значения сигналов от ближайших маяков, все измерения не хранятся в радиокарте.

Точность позиционирования у KNN алгоритма выше, чем у алгоритма зонального позиционирования, если процедура сбора информации была проведена правильно.

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