Разработка мобильных решений для позиционирования и навигации внутри помещений
Анализ методов позиционирования и навигации внутри помещений: GSM, Wi-Fi, BLE Beacons, VLC. Анализ приложения "Muzeo Nazionale di Castel Sant’Angelo". Рассмотрение этапов разработки мобильных решений для позиционирования и навигации внутри помещений.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | дипломная работа |
| Язык | русский |
| Дата добавления | 07.12.2019 |
| Размер файла | 2,6 M |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
Разработка мобильных решений для позиционирования и навигации внутри помещений
Введение
На протяжении последних лет позиционирование и навигация внутри помещений становится всё более необходимой и популярной. В мире строится большое количество зданий с огромной площадью и очень сложной структурой. Торговый центры, аэропорты, железнодорожные вокзалы, музеи, офисы компаний, здания университетов чаще всего имеют несколько этажей и немаленькую площадь. Например, торговый центр “Небо”, расположенный по адресу Нижний Новгород, Большая Покровская улица, дом 82, имеет 8 этажей и общую площадь 142 000 м2. Как быстро среднестатистический человек сможет найти нужный магазин в таком торговом центре? А если в нем нет карт этажей и указателей? Это точно займет какое-то время, которое можно было бы потрать на что-нибудь ещё.
К тому же GPS (Global Positioning System), к которому мы так привыкли и который выручает нас в незнакомых городах становится не очень полезным, если ты находишься внутри здания. Причина этого довольно проста, для корректной работы GPS необходимо иметь в прямой видимости несколько спутников, то есть между навигатором и спутником не должно быть каких-либо препятствий. К препятствиям относятся облака, стены, здания и тому подобное.
В настоящее время можно заметить, что всё больше организаций начинают внедрять решения для позиционирования человека внутри помещений, причем не только для навигации.
Многие музеи на основе близости человека к определенным точкам, отображают информацию об экспонате в специальном приложении. Как пример такого музея, можно привести “Замок Святого Ангела” в Риме, который отображает информацию о локации, в которой в данный момент находится человек через приложение “Muzeo Nazionale di Castel Sant'Angelo”.
Позиционирование внутри помещений применяется также в сфере обслуживания. В настоящее время, сеть ресторанов “McDonald's” внедряет специальные локаторы, которые можно взять при заказе еды и поставить на выбранный столик. Официанты с их помощью могут легко находить нужный столик, а посетителям не приходится стоят около кассы в ожидании заказа.
Помимо описанных применений, позиционирование и навигация внутри помещений используется во многих других отраслях и продолжает набирать популярность в настоящее время.
1.Постановка задачи
навигация мобильный позиционирование
Цель данной работы - изучить мобильные решения для позиционирования и навигации внутри помещения, описать преимущества и недостатки каждого метода и предложить алгоритм, улучшающий точность определения позиции. Также, требуется создать приложение, в котором будут реализованы выбранные методы.
1.1 Методы позиционирования и навигации внутри помещений
Для изучения были выбраны 4 технологии: GSM (Global Solutions for Mobile Communication), Wi-Fi, BLE (Bluetooth Low Energy) Beacons и VLC (Visible Light Communication).
В данном исследовании предстоит изучить каждый метод, определить преимущества и недостатки использования каждого метода в рамках сложности настройки, точности определения позиции, энергопотребления, стоимости реализации и применимости для задачи навигации внутри помещения. Для каждой технологии должен быть представлен подробный алгоритм работы с ней, а также реализация этого алгоритма в мобильном приложении. Более того, каждый метод требует улучшения точности позиционирования путем использования дополнительных алгоритмов и сенсоров.
1.2 Мобильное приложение
В рамках проекта нужно создать мобильное приложение на платформе Android, реализующее описанные алгоритмы. Пользователь должен иметь возможность выбрать желаемый тип навигации (GSM, Wi-Fi, BLE Beacons, VLC) и для каждого получить текущее местоположение. Также, если приложение активно, то оно будет отслеживать перемещения пользователя и обновлять информацию на экране.
В приложении необходима карта помещения, внутри которого будет происходить навигация. На карте должны отображаться этажи, комнаты, коридоры, двери, лестницы и другие помещения, присутствующие внутри здания. Также, в приложении нужна возможность выбора желаемой точки назначения и построения оптимального маршрута до неё от текущего местоположения или другой точки, выбранной пользователем.
2.Обзор существующих решений
2.1 Примеры существующих алгоритмов
В данный момент на рынке есть немалое количество решений для позиционирования и навигации внутри помещений. В основном эти решения делятся на два типа:
· Коммерческие проекты. Эти проекты создаются для продажи и настраиваются под конкретные запросы клиентов. Клиентами чаще всего являются крупные проекты или компании, например торговые центры, аэропорты, вокзалы и тому подобное. Более того, данные проекты могут быть недоступны для некоммерческого использования или использования в малых проектах.
· Проекты специфичные для компании. Такие проекты разрабатываются компанией или нанятой командой для самой компании. Они заточены под решение специфичных проблем и чаще всего недоступны для общего доступа.
Также, все решения базируются на какой-то конкретной технологии. Для каждого метода можно привести несколько проектов, которые используют его в своих решениях.
В качестве первого примера, можно привести проект “Google Radar”. Этот проект был создан в 2001 году для навигации в офисах Google. Он основывается на силе сигнала Wi-Fi сетей. Проект был разработан для сотрудников Google и не находится в общем доступе. В настоящее время о судьбе проекта ничего не известно.
В 2005 году группа людей из университетов Америки и при поддержке компании Intel выпустила статью “Accurate GSM Indoor Localization”, в которой описывается их решение по навигации внутри помещений с использование GSM технологий. Согласно статье, они достигли точности в 5 метров в многоэтажных домах. Для получения такой точности они проводили сканирование здания с помощью специального модема и созданной ими программы, а затем на основе этих данных методом K-ближайших соседей определялось текущее местоположение.
Решений, использующих BLE Beacons сейчас намного больше, чем остальных. В качестве примеров хочу выделить Polestar и GoIndoor. Оба проекта предоставляют SDK, возможность настройки карты и сканирования установленных Beacons. Также, с их помощью можно построить маршрут до выбранной точки. Polestar и GoIndoor SDK можно получить по пробной подписке, которая ограничивает использование некоторых функций.
При поддержке Microsoft было разработано решение для позиционирования внутри помещений, основанное на VLC. Принцип позиционирования был расписан в статье “Wearables Can Afford: Light-weight Indoor Positioning with Visible Light”. Главное преимущество данного решения в том, что оно не требует хорошей камеры и процессора от устройства, на котором оно работает.
В конце апреля 2018 года компания Philips представила решение для навигации внутри магазинов, основанное на VLC. Продукт использует лампы Philips и предоставляется самой компанией в крупные учреждения. Открытого доступа к данному продукту и описанию решения в данный момент нет.
2.2 Проблемы в существующих решениях
Каждое описанное решение специализируется на одной технологии, что, уменьшает возможность использования этого решения в других сферах деятельности или при других условиях. Например, решения, основанные на Wi-Fi технологиях, будет невозможно применить в помещениях, где нет или очень мало точек доступа. Поэтому, реализация всех методов в одном приложении расширяет возможности его дальнейшего применения.
Также, многие существующие решения основываются только на данных, полученных от точек доступа или маячков, в зависимости от выбранной технологии. Это будет являться проблемой, если все точки доступа или маячки окажутся вне зоны видимости. К тому же сигнал от передатчиков чаще всего очень нестабильный и может изменяться под влиянием различных факторов.
Рисунок 1. Изменение сигнала Wi-Fi сети в течение 2-х минут
На графике (Рисунок 1) можно заметить, что сигнал Wi-Fi сети может сильно изменяться в течение нескольких секунд и при условии, что приемник сигнала остается неподвижен.
В данной работе будет предложен способ улучшения точности позиционирования на основе датчиков телефона и дополнительных алгоритм. Он позволит уменьшить вероятность некорректного определения местоположения из-за отсутствия или не стабильности сигнала.
3.Технологии позиционирования внутри помещений
В рамках данной работы было изучено 4 метода для позиционирования и навигации внутри помещений. Для каждого метода были выявлены преимущества и недостатки. Далее будет рассмотрен каждый метод в отдельности.
3.1 GSM
“GSM - это наиболее используемая беспроводная технология во всём мире. Она доступна на территории более чем 219 стран и занимает более 90% рынка.” (4G Americans, GSM Global System for Mobile Communications). Это означает, что данная технология доступна и может быть использована практически везде. Также, GSM используется в технологии A-GPS для улучшения времени холодного старта и позволяет использовать GPS без прямой видимости со спутниками, основываясь на уже собранных данных.
Определять местоположения с помощью вышек сотовой связи можно двумя способами. Первый алгоритм основан на предварительном сканировании здания и описан в исследовании “Accurate GSM Indoor Localization”. Второй использует метод, основанный на силе сигнала и местоположении трёх или более вышек.
Первый алгоритм требует наличие специального оборудования с помощью которого нужно проводить предварительное сканирование. Ввиду его отсутствия и невозможности заменить данное оборудование другим, данный алгоритм не был реализован.
Второй алгоритм определения местоположения по вышкам сотовой связи стоит из трех этапов:
· Сканирование вышек, используя Android API (Application programming interface)
· Поиск местоположения каждой вышки в базе данных
· Определение текущего местоположения методом трилатерации. Трилатерация - это метод определения положения путём построения на местности системы смежных треугольников, в которых измеряются длины их сторон.
Данный алгоритм был реализован, но ввиду ограничений, которые будут описаны ниже, он не был использован в итоговой версии приложения.
Во-первых, в Android API есть ограничение доступа к информации о вышках сотовой связи. При тестировании метода было замечено, а позже подтверждено наблюдениями других разработчиков, что получить информацию можно только о той вышке, у которой достаточно сильный сигнал для подключения к ней. Вышки с более слабым сигналом не будут отображаться в результатах сканирования, хотя они могли быть использованы в алгоритме. Также, в будущих версиях обновление данных будет оптимизировано для уменьшения энергопотребления устройства. То есть, сканирование сети будет проводиться намного реже, а информация о вышках будет кэшироваться и может быть неактуальной во время работы алгоритма.
Однако, самой большой проблемой стал поиск подходящей базы данных, содержащей актуальные местоположения вышек. Единой базы, которая бы включала все вышки в Нижнем Новгороде найти не удалось. Большинство из существующих сервисов предоставляют актуальную информацию о вышках в Америке или других странах Европы.
Во время реализации данного метода были протестированы две базы данных, которые предоставляли данные о местоположении вышек в Нижнем Новгороде. Эксперимент заключался в перемещении по городу и активном сканировании ближайших вышек.
Далее данные о вышках отправлялись на сервер и в статистику записывалась информация о существовании этой вышки в базе.
Рисунок 2. Маршрут сканирования сети в Нижнем Новгороде. 2019г.
На карте (Рисунок 2) отображен маршрут, на протяжении которого проводилось сканирование вышек сотовой связи.
Результаты проведенного эксперимента:
· OpenCellId - позиционируется как одна из самых крупных баз данных, содержащих информацию о местоположении вышек сотовой связи в мире. Но проведя эксперимент, было выяснено, что в базе находится только 20% просканированных вышек.
· MyLinkov API - предоставляет собой агрегатор нескольких баз данных. Данный агрегатор, как и базы данных, которые он использует больше не поддерживается, но возможность использовать API всё ещё остается. В результате эксперимента c помощью данного агрегатора удалось определить 50% вышек.
Эксперимент показывает, что в лучшем случае при использовании данного метода можно использовать лишь 50% видимых вышек. Следующий шаг данного алгоритма - трилатерация - требует в качестве входных данных хотя бы 3 вышки с известным местоположением и сигналом. Это значит, что для успешного определения местоположения нужно как минимум 6 доступных вышек. Внутри помещения телефон чаще всего определяет 3-4 вышки сотовой связи, поэтому становится невозможно применить алгоритм трилатерации для определения местоположения.
В связи с плохими результатами, показанными базами данных, были изучены сервисы, предоставляющие возможность определения текущего местоположения по информации, полученной от вышек. Среди таких сервисов были выбраны два: Google Geolocation и Yandex.Locator API, так как они предоставляли самые точные данные о местоположении. В документации заявляется, что Google Geolocation используют данные местоположения и ближайших вышек, которые были собраны со всех пользователей и на их основе определяет текущую позицию. Yandex.Locator не предоставляет информации о способе обработки данных. Оба сервиса принимают список ближайших вышек и их сигнал и возвращают местоположение и точность его определения. Точность определения позиции с их помощью составляет ~30 метров, что так же является плохим показателем.
Таким образом, использование GSM без предварительного сканирования сигнала во всех помещениях становится невозможным ввиду недостаточного покрытия базами данных вышек в Нижнем Новгороде и ограничениями платформы Android.
3.2 Wi-Fi
Принцип работы метода определения текущего местоположения на основе точек доступа Wi-Fi по большей части схож с работой метода основанного на GSM. Для определения местоположения с помощью этой технологии так же можно использовать предварительное сканирование и алгоритм трилатерации.
Предварительное сканирование, так же, как и в предыдущем методе не было реализовано ввиду сложности настройки такого метода. Сложность заключается в том, что сигнал точки доступа может очень сильно изменяться под действием многих различных факторов, таких как перемещение людей и различных предметов, открытые или закрытые двери и многое другое. Таким образом, данный метод требует постоянной калибровки, что является невозможным.
Так как точек доступа Wi-Fi намного больше, чем вышек сотовой связи, значит то, что они могут предоставить лучшую точность определения. В связи с этим был реализован метод определения местоположения, основанный на алгоритме трилатерации, но он в итоге не был использован. Причиной является то, что несмотря на большее количество точек доступа, данных о их местоположении меньше, чем о вышках, так как они чаще меняются и могут перемещаться. Для этого метода также был проведен эксперимент со сканированием точек доступа. Описание и маршрут эксперимента можно увидеть на странице 12. Для определения местоположения точки доступа были использованы MyLinkov и Wiglet API.
· Wiglet API - данный ресурс позволяет искать точки доступа не только через их идентификатор, но и по имени, что дает больший шанс нахождения точки доступа.
Обе базы данных показали плохой результат: количество определенных точек доступа составило ~5%. В связи с невозможностью получить точное местоположении были использованы сервисы Google Geolocation и Yandex.Locator. Описание сервисов можно прочитать выше, на странице 13. Оба сервиса показали примерно одинаковую точность в ~15 метров.
Ещё один недостаток использования Wi-Fi технологий на платформе андроид заключается в том, что производить сканирование точек доступа можно только 4 раза в 2 минуты (то есть каждые 30 секунд). Внутри помещений подобная задержка будет особо заметна при перемещении. К тому же API с помощью которого производится сканирование в будущих версиях будет запрещено к использованию (developer.android.com, WifiManager).
Таким образом, Wi-Fi технологии сохраняют все недостатки GSM технологий, но предоставляют больше возможностей для точного определения местоположения. Использование данного метода подходит для организаций, которые сами могут создать базу собственных точек доступа и их местоположений и использовать её в своих приложения.
3.3 BLE Beacons
Метод навигации, использующий BLE Beacons, в настоящее время является наиболее популярным для навигации внутри помещений. Они дешевые, маленькие, чаще всего с независимым источником питания (батарейкой) и могут быть незаметно установлены практически в любом месте. К тому же, в соответствии с GSMA (GSM Association) “Точность определения местоположения с помощью beacons составляет 10 сантиметров”.
Одним из главных преимуществ BLE Beacons является их минимальное энергопотребление за счет использования технологии Bluetooth Low Energy (BLE). Данная технология была введена в эксплуатацию в 2016 году для использования в сфере Internet of Things (IoT). Исследование Monika Adarsh (2018) показывает, что потребление электроэнергии в Bluetooth LE снизилось более чем в два раза по сравнению в Bluetooth Classic.
В настоящее время существует очень много производителей BLE Beacons и несколько протоколов передачи данных. Наиболее используемыми протоколами BLE Beacons являются iBeacon (Apple, 2013) и Eddystone (Google, 2015). Покупка данных устройств в рамках проекта была нецелесообразной, особенно ввиду того, что существует несколько приложений, которые могут эмулировать работу BLE Beacons. Поэтому для тестирования использовалось несколько телефонов с установленными симуляторами маячков и протоколом передачи данных iBeacon.
Рисунок 3. iBeacon data
На схеме (Рисунок 3) показаны данные, которые передает iBeacon. Данными являются последовательность байт, подпоследовательность которых предоставляет информацию о текущем маячке:
· Prefix позволяет определить принадлежность маячка к компании или типу передачи данных. С помощью поля iBeacon type (0x02) можно однозначно сказать, что данный маячок передает данные в формате iBeacon
· UUID (Universally Unique Identifier, универсальный уникальный идентификатор) - идентификатор маячка, должен быть уникальным среди всех используемых маячков.
· Major number - определяет принадлежность маячка какой-либо большой группе. Например, в этом поле может записан этаж, на котором размещен маячок. Данное поле может быть одинаково на разных маячках.
· Minor number - уникальный номер внутри группы. Может совпадать для разных маячков, которые находятся в разных группах.
Каждому маячку было присвоен UUID, Major number (номер этажа) и minor number, было выбрано их местоположение и эти данные были сохранены внутри приложения. Для определения текущей позиции используется алгоритм трилатерации, который принимает местоположение и расстояние до трех точек и на их основе возвращает текущую позицию устройства.
Хотя маячки дают большую точность по сравнению с предыдущими методами, они также имеют нестабильный сигнал, который зависит от многих факторов и в результате которого ухудшается точность определения текущего местоположения устройства. С использованием трилатерации, но без дополнительных алгоритмов и сенсоров точность определения местоположения составила ~3 метра.
3.4 VLC
VLC, в противоположность методам рассматриваемым ранее, в данный момент не имеет большого распространения в сфере навигации внутри помещений, так как имеет ряд сложностей в применении.
Главный принцип работы данного метода в том, что специальные лампы рассылают свой идентификатор с помощью высокочастотного непрерывного мигания. Так как они могут мигать с очень высокой частотой, это остается незаметным человеческому глазу, но может быть детектировано камерой телефона или специальным устройством. Также, лампы уже установлены во всех помещениях и обеспечивают очень хорошее покрытие для позиционирования.
Более того, с помощью этого решается проблема пропускной способности различных предметов - сигнал из соседних помещений просто не будет детектироваться устройством, так как свет не проходит сквозь стены. Таким образом, с помощью этого метода и без использования дополнительных алгоритмов улучшения точности как минимум можно определить комнату, в которой находится устройство. Главной проблемой при использовании данного метода является то, что для детектирования высокочастотного сигнала нужно либо специальное устройство, либо камера с очень высоким разрешением. А это значит, что данный метод будет недоступен для общего пользования.
3.4.1 Поляризатор
Изучив различные источники, было найдено решение, предложенное командой Microsoft. Они разработали систему, которая может считывать данные, передаваемые с помощью света, даже на устройствах с плохой камерой и производительностью. Решение основано на принципе работы LCD (liquid crystal display) и модуляции света.
Рисунок 4. Устройство LCD
Выше (Рисунок 4) представлено устройство LCD, состоящего из 6 частей. Работа LCD заключается в следующем:
1. Неполяризованный свет испускается подсветкой (6)
2. Затем поляризуется с помощью поляризационного фильтра (5)
3. Далее свет проходит сквозь стекло (4), не меняясь
4. Жидкие кристаллы (3), которые меняют своё состояние под воздействием напряжения взаимодействуют со светом, преломляя его.
5. Свет, прошедший через кристаллы, попадает на другое стекло (2) и на этом этапе человеческий глаз видит только подсветку
6. Чтобы увидеть что-либо на дисплее необходим второй поляризационный фильтр (1), который преобразует свет, прошедший через кристаллы, в видимые глазу изменения, так как расположен перпендикулярно первому фильтру.
Основываясь на устройстве LCD, можно создать собственный поляризатор, который будет транслировать нужные данные с низкой частотой мигания, но всё ещё незаметной глазу.
От LCD в поляризаторе остается первый поляризационный фильтр и жидкие кристаллы между двумя стеклами. Жидкие кристаллы под напряжением будут перенаправлять поляризованный свет, а без напряжения оставлять без изменения. Но, так как, отсутствует второй поляризационный фильтр для смотрящего не будет никаких заметных изменений. Если установить второй поляризационный фильтр на камеру, то устройство начнет видеть изменение в свете: поляризатор будет менять свой цвет с темного на светлый и тем самым передавать код. Поляризатором будет являться небольшое устройство из фильтра, кристалла со стеклом и контроллером, который в нужный момент будет менять напряжение на кристаллах. Это устройство может быть установлено на любую лампу и даже на окно, главное, чтобы был источник света, который будет проходить через кристаллы и изменяться.
Было проведено исследование, где можно приобрести материалы для изготовления такого устройства. В России можно найти только поляризационные фильтры, а вот электропроводящее стекло и жидкие кристаллы оказались труднодоступны.
Также, существует вариант приобрести дисплей и снять с него ненужные детали, но этот способ тоже имеет свои недостатки. Во-первых, отделение компонентов дисплея друг от друга может быть очень сложным и привести к тому, что устройство в итоге не будет работать. Более того, отделить подсветку от кристаллов на большинстве дисплеев невозможно, так как они прикреплены к одной плате. Во-вторых, дисплеи состоят из большого количества кристаллов (пикселей), что также усложняет работу по модуляции света: нужно одновременно на каждый кристалл подавать одинаковое напряжение.
Ввиду всего вышесказанного было принято решение смоделировать работу поляризатора с помощью обычного телефона. Телефон будет передавать сигнал с помощью изменения цвета с черного на белый и обратно. Такое же поведение, но незаметное глазу, присутствовало бы при использовании настоящего поляризатора.
3.4.2 Передача сигнала
Для передачи сообщения с помощью света, нужно применять специальные алгоритмы кодирования сообщения и передачи сигнала.
В качестве идентификатора для каждого устройства используется натуральное число, которое передается как двоичный код. Так как возможны ошибки при передаче сигнала, требуется применить один из методов кодирования, который позволил бы исправить ошибки в полученном коде. В качестве алгоритма был выбран код Хэмминга, так как он минимально увеличивает длину итогового сообщения. Код Хэмминга позволяет исправить одинарную ошибку и определить двойную. В данной работе не рассматриваются циклические методы кодирования, так как они сильно увеличивают размер сообщения, а значит время полного получения сигнала. К тому же ошибка приема данных в данном проекте не так критична, так как сигнал передается постоянно и вероятно будет считан ещё раз. Построение кода Хэмминга основано на принципе проверки на четность числа единиц. В каждое сообщение добавляются контрольные биты, с помощью которых при декодировании можно определить и исправить ошибку. Количество контрольных битов равно двоичному логарифму от исходной длин сообщения.
Из алгоритмов передачи сигнала было выбрано Манчестерское кодирование, так как оно имеет возможность самосинхронизации (возможность приемнику синхронизоваться с передатчиком) и наименее затратно по количеству передаваемых бит. В данном алгоритме каждый бит сообщения кодируется перепадом напряжения с 0 на 1 при передаче единичного бита и с 1 на 0 при передаче нулевого бита. При одинаковых битах, идущих подряд, в начале такта происходит изменение напряжения на противоположное. А изменение напряжения, определяющее текущий бит, обязательно происходит в середине каждого такта, что позволяет приемнику синхронизироваться с передатчиком. Чтобы определить начало сообщения используется преамбула, которая позволяет приемнику определить с какого места начать читать данные. Для Манчестерского кодирования оптимальной преамбулой является 10101010, так как изменение цвета будет происходить только в середине такта, что позволит легче синхронизоваться с устройством.
Рисунок 5. Манчестерское кодирование
На рисунке 5 показан пример передачи сигнала с помощью Манчестерского кодирования. Стрелками обозначен перепад напряжения.
Для передачи сообщения была создана небольшая веб-страница, которая передает идентификатор с помощью изменения фона страницы с черного на белый в соответствии с Манчестерским кодированием и частотой 5Гц. Частота в 5Гц была выбрана исходя из возможностей камеры мобильного телефона, более подробно об этом будет написано ниже.
3.4.3 Получение сигнала
Сигнал детектируется камерой телефона с помощью стандартных методов Android API. Детектирование и обработка сигнала включает несколько шагов:
1. Включение камеры в режиме видеозаписи.
Режим видеозаписи был выбран ввиду того, что таким образом можно добиться наибольшей частоты кадров в секунду. В режиме съемки фотографии частота получения кадров снижается из-за того, что перед запросом на получение изображения проводится настройка камеры, а после обработка изображения. К тому же, время настройки и обработки не константное, поэтому становится невозможно синхронизоваться с передатчиком.
Видео записывается в минимальном разрешении - 480x360px, так как в используемом алгоритме не требуется хорошее разрешение для детектирования сигнала и таким образом появляется возможность использовать данное приложение на устройствах с плохой камерой.
2. Сохранение видео каждые 2 секунды
Стандартные методы Android API не поддерживают передачу и обработку видео в потоковом режиме, поэтому было принято решение каждые несколько секунд сохранять файл и в отдельном потоке обрабатывать его, пока идёт запись следующего файла.
3. Получение кадров из видео
Так как передача сигнала происходит с частотой в 5Гц, кадры необходимо получать хотя бы с частотой в 10Гц. Но так как частота кадров в секунду в видеозаписи по-прежнему остается не константной, и смена цвета экрана происходит не мгновенно, то становится невозможно определить принадлежность кадра к конкретному такту, если он был получен на границе изменения цвета.
Рисунок 6. Получение фреймов частотой в 10Гц
На схеме выше (Рисунок 6) можно увидеть, что сообщение 111 может быть получено неверно при определенной позиции кадра.
Рисунок 7. Получение фреймов с частотой в 15Гц
Поэтому было принято решение производить считывание кадра частотой в 15Гц, чтобы на каждый такт было выявлено 3 кадра и даже если один из них окажется на границе смены цвета по двум другим можно будет однозначно определить какой бит был передан (Рисунок 7).
Таким образом, из видео запрашиваются кадры по времени, с разницей между двумя кадрами в 67мс (15Гц - смена кадра каждые 1/15 секунды или 67мс).
4. Определение основного цвета кадра
Для каждого кадра вычисляется основной цвет, как среднее между цветом всех пикселей. В качестве оптимизации вместо суммирования всех пикселей, используется только каждый десятый, в итоге обрабатывается только около 2000 пикселей. Это является достаточным для определения среднего цвета, так как в кадре не будет присутствовать мелких деталей, которые повлияли бы на результат.
Так как в данном решении используется только черный и белый цвета, полученный цвет необходимо отнести к одной из этих групп. В процессе тестирования было обнаружено, что черный при различном освещении не сильно изменяется, в отличии от белого. Поэтому было принято решение определять как черный цвет только те кадры, средний цвет которого по каждому каналу RGB (Red, Green, Blue) не больше 80 (число получено в результате проведенных тестов). Все остальные цвета причисляются к белому. Полученный цвет добавляется как единичный или нулевой бит к текущему сообщению.
5. Декодирование сигнала
Процесс продолжается до тех пор, пока не будет получено достаточное количество битов для декодирования сообщения. За количество битов принимается троекратная длина закодированного сообщения с преамбулой. Так как было задано, что на каждый такт выделяется 3 кадра, сначала нужно попытаться разбить текущий код на подпоследовательности по 3 элемента. Каждая подпоследовательность должна удовлетворять одному из условий:
a) Равны только первый или второй бит подпоследовательности
b) Равны только второй и третий бит подпоследовательности
Эти условия следуют из того, что в середине каждого такта обязательно происходит смена цвета. Для каждого разбиения считается ошибка - количество подпоследовательности, которые не удовлетворяют ни одному из условий. Из разбиений выбирается то, у которого наименьшая ошибка. Затем каждые 3 бита в соответствии с Манчестерским кодированием заменяются на один исходный бит. Если в подпоследовательности была ошибка, то анализируются биты слева и справа и выбирается наиболее вероятный исходный бит. В исходных битах сигнала после этого ищется преамбула, чтобы определить начало сообщения и затем сообщение декодируется с помощью кода Хэмминга.
В данном разделе требуется уточнить, что данный алгоритм был создан для тестирования системы и маловероятно применим в настоящем приложении, так как получение сигнала основано на том, что в кадре ничего кроме передатчика нет. Этот алгоритм можно сравнить со сканированием QR-кода, для правильной работы приемник должно находиться в непосредственной близости к передатчику. Данный алгоритм можно улучшить с помощью детектирования передатчиков путем сравнения последовательных кадров и анализирования их положения относительно камеры, но требуется учитывать возможность перемещения приемника, изменение угла обзора и многие другие факторы.
Таким образом, дальнейшее улучшение решение возможно с помощью алгоритмов компьютерного зрения и требует отдельного исследования, основа которого заложена в текущей работе.
Как результат, данная технология имеет множество возможностей для развития и может предоставлять точность в пределах нескольких сантиметров. К тому же эта технология не подразумевает реализацию алгоритмов, основанных на силе сигнала, а значит она менее подвержена различным колебаниям, зависящим от передвижения предметов и многих других факторов.
4.Улучшение точности
Так как данные о местоположении, полученные с помощью вышеописанных методов, могут быть неточны, ввиду различных факторов и нестабильности сигнала, одной из задач было улучшение точности путем использования датчиков телефона и дополнительных алгоритмов.
4.1 Фильтр Калмана
Для сглаживания полученных данных и улучшения точности в определении местоположения был выбран фильтр Калмана, так как он работает в онлайн режиме, и его реализация включает использование информации, поступающей с датчиков телефона. В качестве датчиков был использован акселерометр, показывающий ускорение движения по осям x, y и z и компас, определяющий направление движения.
Фильтр Калмана использует динамическую модель системы (например, физический закон движения), известные управляющие воздействия и множество последовательных измерений для формирования оптимальной оценки состояния. Алгоритм состоит из двух повторяющихся фаз: предсказание и корректировка. На первой рассчитывается предсказание состояния в следующий момент времени (с учетом неточности измерения). На второй - новая информация с датчика корректирует предсказанное значение (также с учетом неточности этой информации). Благодаря пошаговой структуре алгоритма, он может отслеживать состояние объекта в реальном времени, используя только информацию о предыдущем состоянии, текущее состояние системы и ошибку в измерении.
Рисунок 8. Фильтр Калмана
На схеме (Рисунок 8) представлен алгоритм работы фильтра Калмана. Далее будут разобраны все переменные, указанные в формулах с теми значениями, которые применяются в текущем проекте.
Начальными значениями являются: нулевой вектор состояния (X) и единичная матрица P. Матрица P - это апостериорная ковариационная матрица ошибок, задающая оценку точности полученной оценки вектора состояния.
На формуле 1 представлен вектор состояния системы, который включает в себя координаты X и Y на плоскости и проекция скорости на координатные оси.
|
(2) |
Первым шагом этапа предсказания является предсказание текущего состояния системы на основе предыдущей итерации вычисления (Формула 2).
|
(3) |
На формуле 3 представлена матрица эволюции системы. Она воздействует на вектор на каждом шаге предсказания системы. В качестве переменной t, используется время прошедшее, с предыдущего обновления вектора состояния.
|
(4) |
Можно заметить, что если расписать формулу (Формула 4), то на шаге предсказания X и Y изменяются по закону прямолинейного равномерного движения.
|
(5) |
На формуле 5 представлен вектор управляющих воздействий. В текущем решении - это вектор проекции ускорения на оси X и Y.
|
(6) |
Формула 6 отображает матрицу управления, которая воздействует на вектор u (Формула 5).
|
(7) |
Теперь, если вернуться к изначальной формуле (Формула 2), можно заметить, что на первом шаге используется стандартная формула равноускоренного прямолинейного движения (формула 7).
|
(8) |
На втором шаге обновляется матрица P - предсказывается ошибка ковариации (Формула 7).
|
(9) |
На формуле 9 показана используемая ковариационная матрица шума процесса (Q), где acc - это параметр ошибочности данных, полученных с акселерометра, а t - время прошедшее с начала процесса фильтрации. Стоит заметить, что в данном решении было сделано допущение, что ошибка акселерометра по оси X не влияет на ошибку по оси Y.
|
(10) |
На первом шаге этапа корректировки высчитывается коэффициенты усиления (Формула 10), которые отображают степень доверия расчетной и эмпирической величинам. В формуле используется матрица H, связывающая вектор состояния и вектор измерений.
На формуле 11 представлена ковариационная матрица шума измерений. В качестве значений этой матрицы берется точность измерения местоположения с помощью вышеописанных методов.
На следующем шаге обновляется оценка с учетом измерений, поступающих с акселерометра и компаса. Для того, чтобы получить ускорение в системе координат, связанной с Землёй, необходимо умножить инвертированную матрицу поворота, полученную с компаса на вектор ускорения, полученного с акселерометра. Таким образом, в качестве измерений получается ускорение на север и восток или ax и ay.
Последний шаг - это обновление ошибки ковариации (Формула 13). В данной формуле I - единичная матрица. Все остальные параметры были описаны выше.
4.2 Результаты применения
Фильтр Калмана применялся к каждому методу и в результате тестирования было выявлено, что не для всех методов он позволяет улучшить результат.
Алгоритм оказался плохо применим к текущей реализации методов основанных на GSM и Wi-Fi, так как с их помощью местоположение определялось стабильно (то есть не было выявлено признаков большой зашумленности данных), но с плохой точностью. Фильтр Калмана в первую очередь основывается на данных о местоположении и пытается их уточнить, но если признаков шума в исходных данных не обнаруживается, то измерения с датчиков не сильно влияют на итоговый результат. В первую очередь, такое поведение вызвано использованием сторонних сервисов, где вероятно уже происходит сглаживание данных и тем, что сервисы не выдают достаточно точное местоположение. Предположительно, алгоритм с использованием предварительного сканирования мог бы быть уточнен с помощью фильтра Калмана, так как он выдает лучшую точность, но больше подвержен нестабильности сигнала от точек доступа или вышек сотовой связи.
Фильтр Калмана показал хороший результат для BLE Beacons. Так как сила сигнала, полученная непосредственно с Bluetooth датчика, является нестабильной в силу неточности датчика и ряда других факторов, то и итоговые результаты о местоположении будут содержать большое количество шума. Фильтр Калмана помог сгладить нестабильность в получении местоположения и снизил увеличил точность определения местоположения с 3-х метров до одного.
Стоит понимать, что фильтр Калмана напрямую не влияет на определение точности местоположения, он убирает шум и выбросы, которые дают плохую точность, вследствие чего средняя точность определения местоположения увеличивается.
Для технологии VLC фильтр Калмана тоже применялся, но неуспешно на данном этапе реализации этого метода. В данном решении для определения местоположения по VLC необходимо находиться в непосредственной близости от передатчика, а так как для тестирования использовалось ограниченное количество передатчиков, и они располагались с меньшей частотой, чем могли бы располагаться лампы, то данные о местоположении поступали реже, чем в предыдущих методах. Фильтр Калмана, как уже говорилось ранее, в первую очередь использует информацию о местоположении и уточняет её с помощью датчиков.
В случае VLC возникает ситуация с недостатком информации о местоположении, следовательно на данном этапе применение фильтра не дает видимых результатов. В дальнейшем, после реализации алгоритма детектирования передатчиков, фильтр Калмана вероятно будет показывать хорошие результаты.
5.Мобильное приложение
Для тестирования вышеописанных алгоритмов было создано приложение на платформе Android. Системные требования: Android 6+, поддержка модулей Wi-Fi и Bluetooth, камера (минимальное разрешение 480x360px).
Исходный код приложения доступен в репозитории по адресу: https://github.com/FionaRo/IndoorNavigation.
5.1 Карта помещения
Для тестирования было выбрано общежитие университета “Высшая Школа Экономики” по адресу Львовская 1в, подъезд 1. Приложение должно отображать карту внутренних помещений, включая этажи, лестницы и двери. Для создания карты был выбран сервис Mapwize. Он позволяет создавать карты помещений, ставить метки на помещения и создавать маршруты между метками. В текущем решении используется бесплатная версия этого сервиса и он имеет ограничения на количество создаваемых объектов.
Рисунок 9. Карта помещения
На рисунке 9 показана карта, созданная с помощью сервиса Mapwize. На ней отображаются жилые блоки, тех. помещения, лестницы, коридоры и двери. Также, на рисунке отображен маршрут между двумя помещениями.
5.2 Функционал приложения
Рисунок 10. Выбор метода позиционирования
Приложение позволяет выбрать каким методом определять текущее местоположение (Рисунок 10).
Рисунок 11. Поиск и отображение локации
В приложении отображается текущее местоположение, полученное с помощью выбранного метода, и с помощью компаса определяется направление телефона. Также, доступна возможность выбрать объект нажатием на него либо через поиск в списке (Рисунок 11).
Рисунок 12. Маршрут от текущей локации
В приложении можно построить маршрут от текущего местоположения (Рисунок 12). Маршрут будет построен с учетом указанных дверей. Приложение также учитывает наличие лестниц и может строить маршруты с одного этажа на другой.
5.3 Архитектура приложения
Приложение использует MVP (Model-View-Presenter) паттерн, так как он считается наиболее оптимальным для разработки мобильного приложения.
Рисунок 13. MVP паттерн
Схема (Рисунок 13) отображает взаимодействия в программе, которая использует MVP паттерн.
В данном приложении в качестве View выступает главное окно (MainActivity), оно отсылает в Presenter (LocationScanner) события о смене типа определения местоположения. LocationScanner содержит поле locationManager типа ILocationManager, при смене типа позиционирования этому полю присвается один из экземпляров классов: CellLocationManager, WiFiLocationManager, BeaconsLocationManager или VlcLocationManager. Каждый из этих классов имплементирует метод интерфейса ILocationManager - getLocation.
Presenter каждые 500мс вызывает метод getLocation у текущего locationManager. В этот метод передается callback (функция обратного вызова), так как методы не имеют возможности вернуть информацию о местоположении мгновенно. Каждый из классов в методе getLocation запускают алгоритм определения местоположения, описанный выше. Для каждого из классов есть свой набор Models для работы с камерой, запрашивания данных с сервисов и обработки данных различными алгоритмами.
После завершения работы алгоритма вызывается callback, в который передается текущая локация. Эта локация затем передается в фильтр Калмана, который возвращает отфильтрованные данные в Presenter. После получения итогового местоположения Presenter вызывает метод updateLocation у View, в котором обновляется местоположение на карте.
6.Сравнение технологий
Одной из задач данной работы являлось сравнение технологий в рамках сложности настройки, точности определения позиции, энергопотребления, стоимости реализации и применимости для задачи навигации внутри помещения.
Таблица 1. Сравнение методов позиционирования
Таблица 1 представляет сравнение реализованных методов позиционирования. GSM и Wi-Fi невозможно применить для навигации внутри помещений в текущем варианте, так как они показывают плохую точность в определении местоположения. VLC применима для навигации внутри помещения, но требует доработки, так как на текущем этапе может вызывать сложности при использовании.
1 - Сложность настройки определяется временем, которое может быть затрачено на установку оборудования. Для GSM и Wi-Fi не требуется производить настройку оборудования. Для Beacons требуется настроить уникальные идентификаторы и расположить их по всему зданию. VLC требует создания и программирования специальных поляризаторов и установка их на лампы внутри здания.
2 - Энергопотребление определяется частотой сканирования и энергопотреблением используемых модулей. GSM имеет высокое энергопотребление, так как сканирование вышек сотовой связи происходит с высокой частотой. Сканирование сетей Wi-Fi имеет ограничение на 4 запроса в 2 минуты, поэтому снижается количество потребляемой энергии. BLE Beacons потребляет наименьшее количество энергии, благодаря технологии Bluetooth Low Energy. VLC использует камеру, которая потребляет большое количество энергии.
3 - Нулевая стоимость оборудования объясняется отсутствием необходимости его закупки. Для использование требуется только создание приложения.
4 - Цены взяты с сайтов: aliexpress.com, passkit.com и estimote.com.
5 - Цена оборудования взята из исследования “Wearables Can Afford: Light-weight Indoor Positioning with Visible Light”.
6 - GSM и Wi-Fi могут применимы для позиционирования внутри помещений с использованием алгоритма, включающего предварительное сканирование сетей.
7 - VLC требует доработки алгоритма детектирования передатчика для уменьшения сложности использования данного метода.
7.Результаты
В данной работе были изучены 4 метода позиционирования и навигации внутри помещений: GSM, Wi-Fi, BLE Beacons и VLC. Для каждой технологии был реализован ряд алгоритмов определения местоположения. Во время реализации и изучения были выявлены недостатки и преимущества каждой технологии и был проведен сравнительный анализ 4-х методов, в результате которого было выяснено, что GSM и Wi-Fi технологии требуют реализации более точных алгоритмов и не могут в стандартном виде конкурировать по точности с BLE Beacons и VLC. BLE Beacons и VLC показали примерно равную точность и оптимальность их использования для навигации внутри помещений. Преимуществом BLE Beacons перед VLC в настоящее время остается сравнительная легкость в их использовании. Также, был реализован фильтр Калмана для улучшения точности и сглаживания шума на основе акселерометра и компаса.
Данная работа показывает возможности использования данных методов для навигации внутри помещения и задает дальнейший вектор развития данной темы в сторону улучшения алгоритмов GSM и Wi-Fi и более глубокого изучения технологии VLC.
Литература
1.https://github.com/FionaRo/IndoorNavigation
2.https://en.wikipedia.org/wiki/Manchester_code
3.https://en.wikipedia.org/wiki/Hamming_code
4.https://en.wikipedia.org/wiki/True_range_multilateration
5.https://docs.mapwize.io/developers/android/sdk/latest/
6.https://developer.android.com
7.4G Americans (2014). GSM Global system for Mobile Communications.
8.Infsoft GmbH. Indoor Positioning & Navigation. A Guide on Technologies and Use Cases.
9.Fred Zahradnik (2018). What Is Trilateration?
10.Latif Ullah Khan. Visible light communication: Applications, architecture, standardization and research challenges
11.Zdenмk NМMEC, Pavel BEZOUЉEK (2008) The Time Difference of Arrival Estimation of Wi-Fi Signals
12.Oleg Katov (2018) Reduce GPS data error on Android with Kalman filter and accelerometer
13.Zhice Yang1, Zeyu Wang1, Jiansong Zhang2, Chenyu Huang3, Qian Zhang1 Wearables Can Afford: Light-weight Indoor Positioning with Visible Light
14.Victor Bahl, Venkat Padmanabhan (2001) Radar
15.Veljo Otsason, Alex Varshavsky, Anthony LaMarca, and Eyal de Lara, Accurate GSM Indoor Localization
16.Latif UllahKhan (2016) Visible light communication: Applications, architecture, standardization and research challenges.
Размещено на Allbest.ru
Подобные документы
Реализация программного решения по из взаимодействию друг с другом клиент-серверного приложения и web-сервера. Обеспечение мобильного устройства пользователя данными, необходимыми для навигации. Внесение корректив в таблицы с датчиками и картами.
курсовая работа [766,6 K], добавлен 23.08.2017Разработка мультитач-ориентированного приложения для туристических фирм на языке C# с использованием WPF. Применение Expression Blend для создание приложения интерактивной навигации. Проектирование программы для навигации в торговом центре "Гудвин".
отчет по практике [1,1 M], добавлен 16.09.2012Разработка алгоритма фильтрации данных, полученных с систем спутниковой навигации с помощью GNSS-модуля. Анализ работы фильтра Калмана, его программная реализация под конкретную задачу. Выбор навигационных модулей для получения данных позиционирования.
дипломная работа [3,6 M], добавлен 12.01.2016Информационная структура, навигационная система и номенклатура страниц web-приложения. Проектирование web-приложение для организации взаимодействия внутри компании через сети Intranet, включающее функцию проведения экспертных опросов. Схема базы данных.
курсовая работа [6,6 M], добавлен 21.01.2015Мобильные операционные системы. Основные характеристики систем iOS и Android, их достоинства, недостатки и индивидуальные возможности. Анализ преимуществ лидирующих мобильных платформ для разработки приложения. Основные различия в механизмах безопасности.
дипломная работа [806,5 K], добавлен 01.01.2018Определение эффективности методов RSS и TOA, их сравнение в позиционировании абонентских станций внутри помещений и на открытых пространствах. Принципы локализации абонентов в стандарте IEEE 802.11. Использование систем локализации объектов в сетях Wi-Fi.
курсовая работа [1,5 M], добавлен 07.12.2013История возникновения и развития современной робототехники, применение технологий искусственного интеллекта. Разработка структурной схемы системы навигации мобильного робота, коррекция траектории его движения, методы управления локальными перемещениями.
дипломная работа [1,1 M], добавлен 18.05.2011Современное состояние рынка мобильных приложений. Основные подходы к разработке мобильных приложений. Обоснование выбора целевой группы потребителей приложения. Этапы проектирования и разработки мобильного приложения для операционной системы Android.
курсовая работа [987,1 K], добавлен 27.06.2019Знакомство с проблемами обнаружения вредоносного программного обеспечения для мобильных устройств. Анализ функций антивирусного пакета Kaspersky Mobile Security 8.0. Характеристика наиболее распространенных антивирусных программ для мобильных устройств.
реферат [55,1 K], добавлен 11.01.2017Анализ игровых жанров для мобильных устройств и целевой аудитории. Разработка концепции игрового приложения, основной механики, меню и интерфейса игры. Описание переменных скриптов. Реализация выбора цели и стрельбы. Настройка работоспособности игры.
дипломная работа [1,4 M], добавлен 19.01.2017
