Навигация в помещениях с iBeacon и ИНС09.12.2014 04:48

Представьте, что перед вами поставили задачу по реализации навигации внутри помещений. Соответственно, GPS/Глонасс и тому подобные системы спутниковой навигации вам недоступны. Что делать? В этой статье мы с вами подробно рассмотрим варианты решения подобных задач в теоретической части, а в практической — реализуем «в железе» indoor-трекер для работы с маячками iBeacon по Bluetooth BLE на NodeJS на базе новейшей платформы Intel Edison, рассмотрим применение трилатерации и фильтра Калмана, библиотеку CylonJS по работе с датчиками под NodeJS.Часть 1. Теория1.1. Актуальность проблемы В последнее время всё более актуальной становится проблема навигации внутри помещений, а также предоставления посетителям услуг, основанных на их местоположении (LBS — Location-based service) и предпочтениях. Здания становятся всё более объёмными и нередко имеют довольно сложную структуру, ориентироваться в которой могут лишь те, кто постоянно посещает такие здания, а для неподготовленного человека ориентирование в таких местах превращается в пытку. Кроме того, решения, применяемые в indoor-навигации (навигации внутри помещений), помогают и в ориентировании вне зданий, на улице — там, где в условиях плотной застройки использование систем спутниковой навигации затруднено (нет спутников в прямой видимости, присутствует только отражённый/ослабленный/зашумленный сигнал GPS/Глонасc и т.д.). Особенно эта проблема актуальна для Японии с высокой плотностью городской застройки.

В случае спутниковой навигации (GPS/Глонасс) существуют сервисы OutDoor, благодаря которым вы узнаете о ближайших кафе/ресторанах/гостиницах и т.д. благодаря тому, что известно ваше текущее местоположение. А благодаря сервисам indoor-навигации вы сможете без проблем и оперативно найти ближайшую стойку регистрации в здании аэропорта, экспонат в музее (+сразу отобразится его описание на экране вашего телефона), отдел и полку с нужным вам товаром в магазине (больше не придется тратить часы на поиск всех нужных товаров в магазине), свободное место на парковке, и многое другое. Типичный пример — аудиогиды. Приходите в музей, берете аудиогид, и каждый раз вынуждены искать по номеру нужный экспонат, вводить его номер в устройство и слушать его описание. В случае применение indoor-навигации, всё производится автоматически — просто подойдите к заинтересовавшему вас экспонату, и его описание начнет проигрываться без дополнительных телодвижений с вашей стороны. Никаких сложностей и потери времени, всё просто.

Также, благодаря indoor-навигации появляются новые инструменты для маркетинга — проходя мимо вашего магазина, человек может моментально узнать о проводимых у вас акциях/мероприятиях/предоставляемых услугах, товарам, благодаря всплывающему сообщению на экране своего телефона (так называемом «Geo-fencing», причём предложенные ему предложения будут учитывать его интересы — т.к. можно учитывать информацию о его прошлых покупках), либо просто получить уведомление при приближении к определенному месту (второе направление indoor-навигации, называемое «Geo-aware»), а вы — получать статистическую информацию («тепловые карты» посетителей — своеобразный и очень мощный offline-аналог Google Analytics), основанные на перемещениях клиентов внутри ваших торговых залов (понять, какие отделы и товары пользуются повышенным интересом — очень легко). Рынок подобной геоконтекстной рекламы (LBA — location-based advertising) уже измеряется миллиардами долларов, и с развитием систем indoor-навигации ожидается его стремительный рост.

Благодаря большим коммерческим перспективам, направление indoor-навигации становится всё более востребованным и уже привлекло внимание таких крупных игроков на рынке, как Google, Apple, Qualcomm, Broadcom, Sony и т.д., и в это, без сомнения, перспективное направление уже инвестируются сотни миллионов долларов.

1.2. Варианты решения проблемы С актуальностью проблемы и перспективностью разобрались, осталось разобраться с её реализацией. Основной недостаток систем спутникового позиционирования — проблематичность их применения в закрытых помещениях, в результате чего приходится искать иные пути решения проблемы indoor-навигации. Их несколько: 1) Навигация по Wi-Fi. Используется уже существующая инфраструктура сетей связи — точки беспроводных сетей Wi-Fi, и это наименее затратный вариант. Методика определение координат следующая– устройство пользователя сканирует доступные Wi-Fi-точки доступа, затем информацию о них отправляет на сервер, где эти данные по базе данных сопоставляются с координатами этих точек доступа, по которым и вычисляются координаты пользователя. К сожалению, координаты Wi-Fi точек точно не известны, плюс могут меняться (перенесли Wi-Fi точку в другое место или заменили её на другую — координаты уже оказываются неверными).Точность при таком подходе оставляет желать лучшего (погрешность — до 25 метров! А при использовании специально созданной wi-fi инфраструктуры — точность 3–5 метров, но это уже требует ощутимых затрат на создание и обслуживание подобной системы), да и идентицифировать клиентов по Wi-Fi, привязывая их расположение к карте помещений, проблематично — начиная с iOS 8, mac-адреса Apple-устройств (iPhone, iPad) постоянно меняются, для предотвращения «рекламной» слежки.

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

3) Системы спутниковой навигации (GPS/Глонасс и т.д.) + инерциальные навигационные системы (ИНС). Применимо, когда периодически появляется сигнал систем спутниковой навигации — например, проезд по тоннелю — когда въезжаем в тоннель, нам ещё доступны актуальные координаты и направление движения с GPS/Глонасс-спутников, далее при въезде в тоннель мы теряем сигнал, и используем уже инерциальную навигационную систем (ИНС, на базе акселерометра, гироскопа, магнитометра), которая использует в качестве начальных условий последние актуальные данные с GPS/Глонасс до потери связи со спутником и поддерживает их актуальность на основе получаемых с датчиков данных о текущей скорости/ускорении/направлении движения, до возобновления связи со спутниками. Стоит принимать во внимание, что в ИНС ошибки постоянно накапливаются, и со временем данные, полученные с ИНС, становятся все более и более отличными от действительности.

4) Ориентирование по базовым станциям операторов сотовой связи (GSM).В зоне видимости сотового телефона / GSM-модема постоянно находятся как минимум одна базовая станция GSM, а обычно — несколько. Координаты расположения этих базовых станций — известны (благодаря многочисленным навигационным сервисам, например Яндекс.Навигатор — приложение получает информацию о видимых вашим телефоном базовых станций и текущем вашем положении по GSM/Глонасс, и отправляет эти сведения в Яндекс, где на основе этих данных строится база соответствий «Базовая станция-координаты», к которой имеется свободный доступ через предоставляемое API). Отправляем в модем команду AT+CREG=2, в результате чего начинаем получать сообщения +CREG: с информацией о текущей подключенной базовой станции — LAC и CELLID (соответственно код зоны и идентификатор базовой станции). Отправив эти данные на один из специальных сервисов (предоставляемый Яндекс, Google и другими компаниями), получаем координаты этой базовой станции. Многие модемы позволяют получить список видимых базовых станций (БС) с указанием их LAC и CELLID — остаётся только через базы данных с координатами БС получить их координаты и методом триангуляции определить свое примерное местоположение.Минусы — невысокая точность (БС может быть удалена на расстоянии в 35 км от пользователя + некоторые БС являются мобильными и постоянно меняют свою дислокацию).

5) Использование Bluetooth-маячков Becon — даёт достаточную точность при приемлемом уровне финансовых затрат; перспективная технология, которая активно развивается, поэтому именно на iBeacon остановимся подробно в следующем разделе и реализуем на практике.

6) Навигация, основанная на синергетическом эффекте — решает задачу определения текущего местоположения, используя все (или большинство) из перечисленных выше способов. Эффективность достигается за счёт того, что мы используем сразу несколько векторов определения координат, что способствует компенсации ошибок и повышению точности определения координат. На реализацию подобной системы, кстати, в прошлом году фондом развития центра разработки и коммерциализации новых технологий «Сколково» был выделен грант в 1 млн $.

1.3. Технология Beacon Схема работы проста — у нас есть установленные по всему периметру Bluetooth-маячки, координаты расположения которых мы знаем. Эти маячки с заданной периодичностью производят широковещательную рассылку, содержащую идентифицирующую их информацию. Пользовательское приложение циклично получает эти данные, по базе данных определяет координаты маячков, и на основе силы сигнала (позволяющей определить удалённость от каждого из них) определяет своё местоположение. Подобные маячки часто называют маяками iBeacon, что ошибочно. Правильнее называть их Beacon-маяками, поскольку iBeacon — это название стандарта от Apple для использования в мобильных приложениях под iOS, а Beacon — это собственно физическая реализация маячков:

Рассмотрим подробнее Beacon-мачки.

В плане физической реализации Beacon-маячки — это обычные Bluetooth 4.0 LE (Low Energy) устройства, таким образом, их роль может с успехом выполнять любое устройство, оснащённое BLE-чипом — например, cмартфоны на базе Android, а также iPhone, iPad, обычные ноутбуки, Raspberry Pi с usb bluetooth-донглом и т.д., на которое установлено специальное приложение, реализующее функции Beacon-маячка. Типичный Beacon-маячок, показанный на рисунке выше, имеет довольно компактные размеры, и способен проработать всего лишь от одной батарейки до двух лет. Схемотехнически состоит из батарейки и Soc (Systen-On-Chip) Texas Instruments CC2540/2541 (ещё применяют Nordic nRF51822), представляющий собой 8051 микроконтроллер, в который загружается прошивка для реализации функции Beacon-маячка, и периферийный модуль Bluetooth LE. Дальность действия маячка — в среднем 10 метров (варьируется от 15–20 см до 25–40 м в зависимости от модели и настроек). Периодичность выдачи данных — 200 мс, но это опять же, как правило, настраивается — можно настроить и на более частую периодичность, и на более редкую. Срок службы от одной батарейки — в зависимости от модели от чуть менее одного года до трёх лет (в среднем — 2 года). Цена одного маячка — порядка 15–20 долларов. Маячок является простым устройством, который только выдаёт всем подряд в эфир свои данные (в advertising-режиме), используя Bluetooth профиль GATT (при этом к нему даже не нужно выполнять подключение), тем не менее, производители, как правило, закладывают возможность подключения к маячку с целью его удалённого конфигурирования (редактирование данных, выдаваемых в эфир + периодичность выдачи данных и мощность излучения).

1.4. Применение и безопасность маячков Beacon. Помимо рассмотренных в начале данной статьи сфер применения, маячки Beacon могут использоваться, благодаря своей миниатюрности и большому сроку работы на одном заряде батареи, на предприятиях и в строительстве, для ориентирования грузов, персонала, техники. Также, предлагается использование подобных маячков и в автомобилях. Например, машина может быть одним большим Beacon-маяком, благодаря чему можно реализовывать функции вроде «Где моя машина» — для поиска машины на больших парковках. Но не стоит переоценивать эту технологию и не стоит забывать про вопросы безопасности её использования. В некоторых источниках я встречал предложение использовать Beacon-маяки в машине для дистанционного открытия шлагбаума. Подъезжает машина, в которую встроен Beacon-маячок — шлагбаум (на въезде в предприятие/гараж и т.д.) автоматически открывается. Тут нужно вспомнить про то, что технология не предоставляет никаких средств безопасности, и ничто не мешает злоумышленнику просто сканировать в режиме реального времени эфир, на предмет обнаружения искомого маяка, который вызовет открытие шлагбаума. Далее остаётся только прописать в свой поддельный маячок искомые pUUID, Major и Minor, включить его — и чужой шлагбаум поднимется (либо откроются двери), открыв вам путь на чужую территорию. В этом случае лучше отказаться от применения Beacon-маячков и прибегнуть к реализации диалогового кода обмена, с шифрованием, между передатчиком (машиной) и приёмником (шлагбаумом), что исключит возможность взлома.

Также ничто не мешает злоумышленнику нарушить вам ориентирование по заранее расставленным в помещении маячкам, выставив свой поддельный, с вашими pUUID/Major/Minor, нарушив навигацию в помещении. Либо, если положение груза определяется по закрепленному на нём маячку, злоумышленник может выставить в нужном месте свой, с данными маяка на грузе, и забрать себе этот груз.

Используя данную технологию, помните об этом, и используйте свои способы защиты.

1.5. Формат данных. Рассмотрим формат выдаваемых маячком данных. С заданной периодичностью, циклически, маячек выдает один и тот же набор данных:

Общая структура Bluetooth — пакета следующая:

Преамбула (4 байта) — префикс пакета, позволяющий установить, что мы имеем дело именно с Beacon-маячком. Всегда равен 4c000215. Преамбула состоит из 4х полей: идентификатор компании (2 байта, в данном примере — 4c00), тип (1 байт, в примере — 0×02) и длина данных (1 байт, значение — 0×15).

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

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

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

Следующая иллюстрация даёт наглядное представление о назначении этих идентифицирующих маяки параметров:

TX Power (параметр K на рисунке выше, 2 байта) — эталонное значение мощности маячка, представляющее собой силу сигнала на расстоянии в 1 метр от маячка. Измеряется и записывается в маячек 1 раз при его производстве. Данная константа используется при определения расстояния от пользователя до маячка. Первый бит является знаковым (1 — »-», 0 — »+»). Например, TX Power в нашем примере (см. рисунок выше, параметр «К») — 0xBE. Это 190 в десятичной системе счисления. Тогда эталонная сила сигнала на расстоянии 1 м от маячка составляет 256 — 190 = -66 dBm.

Остановимся подробнее на определении расстояния до маячков. Чтобы определить наше положение в пространстве, нужно знать не только координаты маяков, которые нам видны (координаты мы можем определить на основе pUUID/Major/Minor), но и расстояние до них. Это нам позволяет сделать параметр RSSI (Received Signal Strength Indicator), вычисляемый пользовательским Bluetooth-приёмником на основе силы принимаемого сигнала. Чем выше значение этого параметра — тем ближе мы находимся к маячку. TX Power — это и есть RSSI, только эталонный, измеренный производителем маячка на расстоянии 1 метра от него. Для определения расстояния до маячка (в метрах) используется текущее значение RSSI, и эталонный TX Power для коррекции, следующим образом:

Геокоординаты нам не нужны, ведь мы хотим определять свое местоположение относительно помещения, поэтому привязываемся к координатам внутри самого помещения. На примере выше круги — это опорные столбы помещения, на каждом из которых закреплено по маячку. Помещение ограничено координатами (0,0), (9,0), (9,7), (0,7). Если данные маяков, которые крепите, неизвестны — можете запустить в смартфоне приложение, отображающее pUUID/Major/Minor маячков в зоне видимости (например, под Android есть iBeacon Locate), и составить подобную карту расположения маячков.

На первый взгляд, ничего сложного нет в определении нашего местоположения — сканируем Beacon-маяки, по таблице (см. рисунок выше) определяем их координаты, по RSSI вычисляем их удалённость, и определяем своё местоположение… Но вот с этого момента и начинается самое интересное…

Суровая реальность вносит свои коррективы. Дело в том, что даже в условиях прямой видимости с маячком параметр RSSI «скачет», хаотично меняя своё значение, в результате чего без применения математического аппарата определить расстояние до маячка становится делом затруднительным. Это происходит из-за следующих факторов:

Ориентация и характеристика направленности излучения или приёма антенной маячка/пользовательского устройства Присутствие крупных экранирующих объектов (человек таковым тоже является) по направлению от маячка до устройства Наличие поблизости поверхностей из материалов, хорошо отражающих радиосигнал, а также большое скопление маячков Beacon на одной территории, за счёт многолучевой интерференции с основным лучём Для начала, нам нужно как-то усреднить значение RSSI с каждого из маячков. Для этого, настраиваем маячки на выдачу данных с максимальной частотой (выше периодичность выдачи данных — больше данных для усреднения, соответственно и выше точность на выходе, но принимайте во внимание, что с повышением периодичности выдачи данных вы снижаете ресурс батареи маячка, так что нужно искать «золотую середину»), накапливаем их в буфере, и с определённой периодичностью (например, раз в секунду) считаем на основе накопленных в буфере данных среднее RSSI для каждого из маячков (в дальнейшем на основе этих «средних» RSSI будем определять наши координаты каждую секунду), затем очищаем буфер и следующую секунду заново накапливаем данные, и так циклически.

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

Следует не забывать, что расчеты производим в двумерном пространстве (только две оси — X и Y), а расстояние до маячков у нас — в трёхмерном, соответственно, если разница по оси Z между наблюдателем и маячками ощутима, нужно строить проекции на оси X, Y:

Здесь A — это полученное расстояние через RSSI, B — высота расположения маячка от нашей двумерной плоскости (в которой находится наблюдатель — устройство, координаты которого определяем), C — расстояние до маячка в этой плоскости, которое и требуется найти. Т.к. образуемый треугольник — равносторонний, то по теореме Пифагора можем без труда найти искомое расстояние, и использовать его в своих расчетах.

Итак, мы определили своё местоположение по трём маячкам с помощью трилатерации, но… Рано радоваться. Даже если мы стоим на месте — наше местоположение всё равно «скачет», но тем не менее на практике таким образом удалось получить точность в 3 метра.

Например, если просто раз в секунду выбирать маячок с лучшим RSSI, то при 10 последовательных измерениях получаем картину следующего плана (одно деление сетки равно 4 метрам):

(красным показано положение устройства, координаты которого определяем и с которого производится измерение, а цифры в кружках — кол-во раз, которое указанный маячок имел лучшее среднее RSSI при 10 последовательных измерениях). Соответственно, и триангуляция даёт нам не совсем приемлемый результат.

Таким образом, требуется дальнейшая математическая обработка полученных результатов, и тут на помощь нам приходит фильтр Калмана. Фильтр убирает шумы измерения (случайные всплески) и выдаёт результат как с учетом результатов текущих измерений, так и с учётом предсказанных результатов на основе прошлых измерений. Фильтр использует динамическую модель системы (закон движения) и 2 повторяющиеся циклически стадии: предсказание и корректировка. На первом этапе — предсказании — мы рассчитываем состояние системы в следующий момент времени, а на втором — корректировке — корректируем наш прогноз, используя результат очередного измерения:

Подробней о данном фильтре можно почитать в статье Фильтр Калмана — Введение Отмечу лишь, что в фильтре имеется возможность учитывать управляющее воздействие. Например, таким управляющим воздействием может быть информация с акселерометра, что значительно улучшает результат (в таком варианте погрешность составляет уже не 3 метра в нашем случае, а 1–1.5 — тоже не мало, но связано отчасти с тем, что фильтр Калмана использует систему с заданным уравнением движения, а мы имеем дело с хаотичным движением). Т.е. схема следующая: считаем средние RSSI → выбираем 3 маячка с лучшими RSSI → получаем координату путём трилатерации → подаём на вход фильтра Калмана (вместе с показаниями акселерометра в качестве управляющего воздействия).

Есть возможность уменьшения погрешности — применять сразу 2 системы — помимо основного определения положения при помощи Beacon маячков, использовать для коррекции этого положения инерциальную навигационную систему, состоящую из акселерометра, гироскопа и компаса (магнитометра — его применение не обязательно, но весьма желательно):

Акселерометр — показывает проекции действующих сил. Когда устройство неподвижно либо движется без ускорения, акселерометр выдает значения проекций ускорения свободного падения (силы тяжести) на его оси. Гироскоп — показывает проекции угловых скоростей. Когда устройство неподвижно, то получаем нули. При изменении угла наклона устройства выдаст скорость вращения, разложенную на оси. Магнитометр — показывает напряжённость магнитного поля, разложенную на оси. Данные с этих датчиков не пригодны для применения в «сыром» виде и также, как и в случае с маячками, требуют математической обработки, плюс весьма желательно применение температурного датчика для термокомпенсации, т.к. у MEMS-гироскопов имеется довольно ощутимый температурный дрейф.

Для использования требуется выработать степень доверия к той или иной системе. Например, задать, что мы при определении координат на 90% доверяем ИНС (т.к. у ИНС доверительная вероятность выше), а на 10% — Beacon-маячкам (т.е. в последнем случае ошибки и скачки куда выше). При таком варианте, с применением ИНС, точность определения координат можно улучшить до 20–30 см (вообще, на точность определения координат влияет ещё количество расположенных маячков — чем ближе расположены к нашему устройству, тем выше точность, но тем дороже реализация, т.к. маячки — штука не копеечная).

В следующей статье мы рассмотрим практическую реализацию Beacon-трекера на основе новой платформы для создания Интернета вещей Intel Edison — напишем приложение под NodeJS.