Представьте, что перед вами поставили задачу по реализации навигации внутри помещений. Соответственно, 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 байт, в примере – 0x02) и длина данных (1 байт, значение – 0x15).
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 для коррекции, следующим образом:
function get_distance( rssi, tx_power ){
if (rssi == 0){
return -1; // Невозможно определить расстояние
}
var ratio = rssi / tx_power;
if ( ratio < 1 ){
return Math.pow(ratio, 10);
} else {
return 0.89976 * Math.pow(ratio, 7.7095) + 0.111;
}
}
1.6. Определение координат по Beacon-маячкам.
Для начала, нам нужно расставить в помещении Beacon-маячки (к примеру, прикрепить на двусторонний скотч к стене/опорным столбам, и чем их больше и чем маячки ближе друг к другу расположены – тем лучше будет результат определения наших координат) так, чтобы они по возможности равномерно покрывали всю площадь помещения, и привязать их к координатной сетке на карте помещения (за начало координат можно выбрать, например, угол помещения), учитывая удаленность маячков друг о друга:
Геокоординаты нам не нужны, ведь мы хотим определять свое местоположение относительно помещения, поэтому привязываемся к координатам внутри самого помещения. На примере выше круги – это опорные столбы помещения, на каждом из которых закреплено по маячку. Помещение ограничено координатами (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.
Автор: tzirulnicov
