Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Введение

навигация алгоритм спутниковый программирование

В последнее время все более актуальной становится проблема навигации внутри помещений, а также предоставления посетителям услуг, основанных на их местоположении (LBS - Location-based service) и предпочтениях. Здания становятся все более объемными, часто имеют сложную структуру расположения тех или иных помещений, что затрудняет перемещение по ним.

Кроме того, решения, применяемые в навигации внутри помещений могут быть использованы при ориентировании на улицах - там, где нельзя использовать спутниковый сигнал ввиду плотной застройки или других факторов, которые могут ослабить принимаемый сигнал GPS/Глонасс и т.д.

В дополнение к понятной и простой всем навигации, показывающей, где пользователь находится сейчас, и предлагающей маршрут, сервисы геолокации часто предлагают посетить те или иные заведения недалеко от текущей геопозиции, основываясь на его предпочтениях. В данном контексте сервисы для навигации внутри помещений могут предложить еще больше опций. Например, Pierdicca et al. пишут об их розничном опыте или о том, как они его называют - «Intelligent Retail Environment». Они заключают, что интеллектуальные навигационные системы предоставляют владельцам большие возможности для понимания поведения потребителей. Использование bluetooth маячков предоставляет данные, которые могут быть преобразованы в информацию об определенных областях магазина, определяющих наиболее популярные места магазина. Кроме того, INS можно использовать для создания более привлекательных маркетинговых стратегий. В то же время клиенты всегда заинтересованы в новых способах получения скидок или привлекательных предложений, поэтому они также заинтересованы в такой системе. Широкое применение Indoor Navigation Systems (INS) нашли в таких местах, как аэропорты и музеи. Человек не каждый день посещает музей или аэропорт, а еще чаще эти места находятся в незнакомом городе, в котором люди могут говорить на иностранном языке. Тут на помощь приходят сервисы навигации, которые помогут проложить кратчайший маршрут до стойки регистрации, или провести пользователя к интересующему его экспонату. Кроме того, если при стандартном использовании аудиогида в музее пользователю нужно каждый раз сканировать штрихкод, чтобы прослушать информацию об экспонате, то в случае с INS достаточно близко подойти, после чего приложение на смартфоне само среагирует и выдаст нужную информацию.

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



1. Методы навигации внутри помещений

Пути решения проблем навигации внутри помещений []:

1. Навигация по Wi-Fi;

2. Геомагнитное позиционирование;

3. Системы спутниковой навигации + Инерционные навигационные системы;

4. Навигация по базовым станциям GSM;

5. Использование Bluetooth маячков.

1.1 Wi-fi

Для навигации по точкам беспроводных сетей Wi-Fi используется уже существующая в здании инфраструктура. Реализация выглядит следующим образом:

– Устройство пользователя сканирует доступные Wi-Fi точки доступа;

– Отправляет собранные данные на сервер;

– На основе информации о расположении Wi-Fi точек доступа сервер; анализирует и выдает информацию о текущем местоположении;

– Координаты пользователя отображаются на устройстве.

При использовании доступных точек доступа в здании, погрешность может достигать 25 метров. Можно создать специально для этих целей собственную Wi-Fi инфраструктуру, однако, это требует немалых затрат. Кроме того, существуют проблемы с идентификацией устройств, подключенных к сети, для последующего построения карты передвижений клиентов. Например, начиная с iOS 8, mac-адреса Apple-устройств (iPhone, iPad) постоянно меняются, для предотвращения «рекламной» слежки.



1.2 Геомагнитное позиционирование

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

1.3 Системы спутниковой навигации и инерционные навигационные системы

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

1.4 Навигация по базовым станциям GSM

В зоне видимости сотового телефона / GSM-модема постоянно находятся как минимум одна базовая станция GSM, а обычно - несколько. Их координаты известны и зачастую не изменяются (за исключением мобильных базовых станций). Благодаря различным сервисам, предоставляющим информацию о том, какие базовые станции сейчас находятся в зоне видимости телефона, можно получить их идентификаторы, по которым затем получить информацию об их расположении и затем, используя триангуляцию, получить приблизительные текущие координаты. Минус такого метода опять же в малой точности конечной геопозиции.

1.5 Использование Bluetooth маячков

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

Устройство маячков от Estimote

Внутреннее устройство Bluetooth маячков достаточно простое (Рис. 1). Основными компонентами, срывающимися под корпусом, являются []:

– Небольшой ARM компьютер;

– Bluetooth модуль;

– Батарейка.

Рис. 1. Маячок Estimote



Прошивка устройства содержится в микросхеме от Nordic Semiconductor. Она гарантирует правильность работы маячков. Несмотря на то, что вычислительные мощности процессора невелики, их достаточно для обработки важных данных и шифрования ID маячков.

Антенна устройства излучает радиоволны частотой 2,4 ГГц и имеет специальную форму - зигзаг. Это позволяет улучшить форму распространяемого сигнала, максимально приблизив его к сфере. чтобы избежать «пустых» зон (зоны, куда не распространяется сигнал).

Для коммуникации маячков c устройством-приемником используется технология Bluetooth Smart, являющаяся последней версией стандарта Bluetooth Low Energy, предназначенного для передачи данных малых объемов. Максимальный размер пакета, передаваемого с помощью Bluetooth 4.2 составляет 257 байт. Такого размера не хватит для отправки медиаконтента, однако, достаточно для передачи идентификаторов маячков и информации о силе излучаемого сигнала, необходимой для последующего расчет приблизительного расстояния между смартфоном и маячком.

Свойства маячков и распространяемого сигнала

Маячки обладают рядом определенных свойств []:

1. Мощность распространяемого сигнала (Broadcasting Power). Это свойство напрямую влияет на радиус сигнала. Чем больше мощность, тем больше радиус распространяемого сигнала. Также увеличивая мощность сигнала, можно добиться большей стабильности. Однако, увеличение мощности достаточно сильно влияет на время жизнь батареи. В теории радиус сигнала при уровне сигнала в 4 дБм (децибел-милливатт) достигает 70 метров. На практике же это значение равно 40-50 метрам.

2. Интервал между сигналами (Advertising Interval). Bluetooth маячки не распространяют сигнал постоянно, они делают это с некоторой периодичностью. Временной интервал описывает, с какой периодичностью маячки будут отправлять сигнал. Значение можно изменять от 100 миллисекунд до 2000. Также, как и мощность сигнала, увеличение значения интервала положительно влияет на стабильность и точность, но отрицательно влияет на время жизни батареи.

3. Измеренная мощность (Measured power). Фабрично установленная величина, равная мощности сигнала на расстоянии одного метра от Bluetooth маячка. Используется для последующего определения расстояния до маячка.

4. Показатель уровня принимаемого сигнала(RSSI). RSSI - Received Signal Strength Indicator. Уровень мощности сигнала принятого приемником. При изначальной мощности в 4 дБм RSSI может величина -26 показывает, что устройство находится в нескольких сантиметрах от источника сигнала, величина в -100 приблизительно равно 40-50 метрам.

5. Зоны сигнала (Proximity zones). Протокол iBeacon определяет четыре зоны по уровню сигнала:

– Очень близко к маячку (до 1 метра);

– Близко (1-3 метра от маячка);

– Далеко (достаточно далеко от маячка);

– Неизвестно (Скорее всего вне зоны сигнала).

Протоколы взаимодействия с маячками

На данный момент существует два наиболее распространенных протокола передачи данных маячками []:

– iBeacon. Данный протокол был представлен компанией Apple в 2013 году на Worldwide Developers Conference. Технология описывается следующим образом [, ]: «iBeacon это технология предоставляющая новые возможности для приложений, работающих с геолокацией. Взяв за основу технологию Bluetooth Low Enegry (BLE), любое устройство поддерживающее протокол iBeacon может быть использовано для установления некоего региона вокруг себя. Это позволяет iOS устройствам определять момент вхождения в определенный регион, определяя в то же время приблизительное расстояние до источника сигнала» [].

Пакеты, которые передают устройства по протоколу iBeacon содержат информацию, представленную в табл. 1 ниже:

Таблица 1. Пакет информации по протоколу iBeacon

Поле	Размер	Описание
UUID	16 байт	Уникальный идентификатор группы маячков, определяющий их тип или принадлежность одной организации.
Major	2 байта	Беззнаковое значение, с помощью которого можно группировать маячки с одинаковым UUID
Minor	2 байта	Беззнаковое значение, с помощью которого можно группировать маячки с одинаковым UUID и Major
Measured power	1 байт	Значение показателя уровня принимаемого сигнала (RSSI - Received Signal Strength Indicator), которое используется для определения близости (proximity) маячка к приемнику (мобильному устройству). Измеряется в dBm.

Рассмотрим пример формирования идентификаторов для маячков компании, владеющей магазинами в разных городах (Табл. 2).

Таблица 2. Пример таблицы идентификаторов для маячков розничной сети

Город	Москва	Санкт-Петербург	Владивосток
UUID	D9B9EC1F-3925-43D0-80A9-1E39D4CEA95C
Major	1	2	3
Minor	Одежда	10	10	10
	Еда	20	20	20
	Техника	30	30	30

UUID является общим для всех местоположений. Это позволяет iOS устройству использовать один общий идентификатор для любого магазина в разных регионах. Затем каждому конкретному магазину присваивается свой идентификатор внутри «зоны» идентификатора UUID. Также можно Конкретизировать Minor значение, разбив маячки по этажам или по отделам с разной спецификацией.

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

Используя эту информацию, iOS устройство может идентифицировать момент входа в магазин или выхода из него, а также в каком отделе находится пользователь. Фрейм протокола iBeacon представлен на рис. 2 [].

Рис. 2. Фрейм протокола iBeacon

Префикс протокола содержит следующие данные: 0x0201061AFF004C0215. Они разбиваются таким образом:

1. 0x020106 идентифицирует пакет как BLE General Discoverable и BR / EDR. Фактически это означает, что маячок работает в режиме вещания, а не соединения с устройством;

2. 0x1AFF говорит, что следующие данные имеют длину 26 байт и являются данными, специфичными для производителя;

3. 0x004C - это Bluetooth Sig ID от Apple и является частью этой спецификации, которая делает его зависимым от Apple;

4. 0x02 - это вторичный идентификатор, который обозначает сигнальный маячок, который используется всеми iBeacons;

5. 0x15 определяет оставшуюся длину в 21 байт (16 + 2 + 2 + 1);

– Eddystone. Это протокол, представленный компанией Google, который определяет формат сообщений, передаваемых устройствами с поддержкой BLE. Он описывает несколько разных типов кадров, которые могут использоваться отдельно или совместно в приложениях, работающих с маячками [].

Протокол Eddystone поддерживает 5 видов пакетов (advertisment packet):

1. «Eddystone-UID - 16-байтовый идентификатор, который состоит из 10-байт namespaceId и 6-байт instanceId» [];

2. «Eddystone-URL - транслирует URL. Любой длинный URL можно сократить с помощью Google URL Shortener или любого другого сервиса сокращения ссылок, что бы поместится в ограниченный 18 байтами Advertisment packet. После декодирования, URL может быть использован любым клиентом с доступом к интернету. Eddystone-URL является основой Physical Web (о котором речь пойдет дальше) и позволяет легко обнаруживать и взаимодействовать с окружающими нас умными устройствами и сервисами»[11];

3. «Eddystone-TLM - телеметрия, доступны такие данные как напряжение аккумуляторной батареи, температура устройства, количество отправленных пакетов с момента включения и время с момента включения»[11];

4. «Eddystone-eTLM - зашифрованная версия кадра телеметрии»[11];

5. «Eddystone-EID - маячок с поддержкой Eddystone-EID меняет свой 8-байтный AES-encrypted идентификатор псевдо-случайным образом со средним периодом, который задается разработчиком в диапазоне от 1 секунды до 9 часов. Для генерации идентификатора используется ключ (Ephemeral Identity Key или EIK) и таймер на самом маячке. Ключ генерируется во время подготовки и настройки маячка и затем передается в службу разрешения, например, Proximity Beacon API»[11];

На рис. 3 представлены фреймы трех типов пакетов.

Рис. 3. Фреймы UUID, URL, TLM.

Далее следует описание оставшихся двух типов пакетов (Табл. 3, 4).

Таблица 3. Фрейм IED

Сдвиг байта	Поле	Описание поля
0	Тип фрейма	Значение 0х30
1	Данные сигнала	Мощность на расстоянии 0 м
2	EID[0]	8 байтовый идентификатор
…	…
9	EID[9]

Таблица 4. Фрейм eTLM

Сдвиг байта	Поле	Описание поля
0	Тип фрейма	Значение 0х20
1	Версия	Версия пакета TLM. В данном случае 0x01
2	ETLM[0]	12 байт зашифрованной информации
…	…
13	ETLM[11]
14	SALT[0]	Соль из 16 бит
15	SALT[1]
16	MIC[0]	Проверка целостности сообщения
17	MIC[1]



2. Поиск кратчайшего пути

2.1 Необходимость

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

2.2 Анализ алгоритмов нахождения кратчайшего пути

Краткое описание наиболее распространенных алгоритмов поиска кратчайшего пути [, ]:

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

– Алгоритм Беллмана - Форда находит кратчайшие пути от одной вершины графа до всех остальных во взвешенном графе. Вес ребер может быть отрицательным;

– Алгоритм поиска А* находит маршрут с наименьшей стоимостью от одной вершины (начальной) к другой (целевой, конечной), используя алгоритм поиска по первому наилучшему совпадению на графе;

– Алгоритм Флойда - Уоршелла находит кратчайшие пути между всеми вершинами взвешенного ориентированного графа;

– Алгоритм Джонсона находит кратчайшие пути между всеми парами вершин взвешенного ориентированного графа;

– Алгоритм Ли (волновой алгоритм) основан на методе поиска в ширину. Находит путь между вершинами s и t графа (s не совпадает с t), содержащий минимальное количество промежуточных вершин (ребер). Основное применение - трассировки электрических соединений на кристаллах микросхем и на печатных платах. Так же используется для поиска кратчайшего расстояния на карте в стратегических играх;

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

Таким образом можно исключить Алгоритм Ли (волновой алгоритм).

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

Данное условия позволяет исключить следующие алгоритмы:

– Алгоритм Флойда-Уоршелла;

– Алгоритм Джонсона;

– Алгоритм поиска А*.

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

2.3 Принцип работы алгоритма Дейкстры

Алгоритм Дейкстры работает следующим образом []:

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

1. Из непосещенных вершин выбирается вершина с наименьшей величиной пути от начальной вершины. Если у нескольких вершин эта величина одинаковая, то выбирается любая из них;

2. Алгоритм помечает выбранную вершину, как посещенную;

3. Алгоритм проверяет всех ее соседей. Если у соседа расстояние больше, чем сумма расстояния до текущей вершины и длины ребра, то уменьшаем его и запоминаем новый список вершин, которые нужно обойти, чтобы получить кратчайший путь;

4. Если вершины отмечены, как посещенные, то алгоритм завершает свою работу, если нет, то переходим к пункту 1.

Расмотрим на примере. Имеется граф из 5 вершин (Рис. 4). Начальной вершиной является А, следовательно ее расстояние равно 0. Для наглядности приведено текущее состояние графа на таблице 5.

Рис. 4. Состояние графа после инициализации

Таблица 5. Состояние графа после инициализации

	A	B	C	D	E
Посещена	-	-	-	-	-
Расстояние	0	?	?	?	?
Путь	[A]	[]	[]	[]	[]



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

Рис. 5 Состояние графа после первой итерации

Таблица 6. Состояние графа после первой итерации

	A	B	C	D	E
Посещена	+	-	-	-	-
Расстояние	0	3	?	1	?
Путь	[А]	[А, В]	[]	[A, D]	[]

Затем повторяем алгоритм, пока все вершины не окажутся посещенными (Рис. 6-9, Табл. 7-10).



Рис. 6. Состояние графа после второй итерации.

Таблица 7. Состояние графа после второй итерации

	A	B	C	D	E
Посещена	+	-	-	+	-
Расстояние	0	3	?	1	2
Путь	[А]	[А, В]	[]	[A, D]	[A, D, E]

Рис. 7. Состояние графа после третьей итерации

Таблица 8. Состояние графа после третьей итерации

	A	B	C	D	E
Посещена	+	-	-	+	+
Расстояние	0	3	11	1	2
Путь	[А]	[А, В]	[A, D, E, C]	[A, D]	[A, D, E]



Рис. 8. Состояние графа после четвертой итерации

Таблица 9. Состояние графа после четвертой итерации

	A	B	C	D	E
Посещена	+	+	-	+	+
Расстояние	0	3	8	1	2
Путь	[А]	[А, В]	[A, B, C]	[A, D]	[A, D, E]

Финальное состояние графа с расстояниями и путями до каждой из вершин из начальной (Рис. 9).

Рис. 9. Состояние графа после пятой итерации



Таблица 10. Состояние графа после пятой итерации

	A	B	C	D	E
Посещена	+	+	-	+	+
Расстояние	0	3	8	1	2
Путь	[А]	[А, В]	[A, B, C]	[A, D]	[A, D, E]

2.4 Создание тестового графа для тестирования алгоритма

Ввиду удобства и распространенности формата JSON ответы с сервера будут приходить именно в этом виде (Рис. 10). Поэтому для того, чтобы протестировать работу алгоритма, граф был описан в таком виде. Затем программа трансформирует полученные данные в массив для работы алгоритма [].

Рис. 10. Пример описания графа, состоящего из трех вершин.



3. Выбор языка программирования

3.1 ОС iOS

Для создания нативных приложений для ОС iOS можно использовать Objective-C или Swift. Существует, как минимум, несколько аргументов в пользу Swift [, , ]:

– В соответствии с информацией, опубликованной Apple, Swift более чем в 2.6 раза быстрее, чем Objective-C;

– Swift является более устойчивым к ошибкам программиста языком за счет строгой типизации и опциональных типов;

– Поддержка динамических библиотек;

– Swift более читаемый язык, чем Objective-C;

– Унифицировано согласование Swift с управлением памятью. Поддержка автоматического подсчета ссылок (ARC) является полной по процедурным и объектно-ориентированным путям кода. В Objective-C, ARC поддерживается внутри Cocoa API и объектно-ориентированного кода, но он не доступен для C кода и API, например Core Graphics. Это означает, что программист будет должен взять на себя управление памятью при работе с Core Graphics APIs, и других более старых API, доступных на iOS;

– Требует меньшее количество кода;

– Постоянно растущее сообщество, готовое помогать друг другу и создавать; новые, интересные open-source проекты.

3.2 ОС Android

Для создания нативных приложений для ОС Android на данный момент существует несколько вариантов используемых языков: Kotlin, Scala, Java. Для разработки данного приложения был выбран язык Java по следующим причинам:

– Java остается самым популярным языком для разработки мобильных Android-приложений;

– Не требует никаких надстроек над средой разработки для начала работы;

– Позволяет реализовать самый объемный функционал;

– Активно развивается в сфере мобильной разработки.

Выбор среды разработки для программирования под ОС Android

Для разработки приложения под ОС Android существует две самые распространенные среды разработки: Eclipse и Android Studio от JetBrains [, ].

Для разработки приложения в рамках данной работы была выбрана Android Studio, поскольку Google сам продвигает эту среду разработки, совместно участвуя в ее создании с компанией JetBrains и включая туда новые идеи и инструменты, заточенные под мобильную разработку.

Стек технологий для приложения Android

В разработке помимо стандартных библиотек, связанных с Android SDK, таких как Android Support Library[?], использовались сторонние библиотеки инструментов.

Основные из них:

– RxJava. Библиотека легко внедряет реактивное программирование в проект. Позволяет легко отслеживать различные события и манипулировать потоками данных. В основе лежит паттерн «Наблюдатель». Использовалась для различных обработок данных [].

– Dagger. Благодаря этой библиотеке, в проекте реализовано внедрение зависимости (Dependency Injection). Используется для управления зависимостями внутри проекта [].

– ButterKnife. Упрощает код за счет использования аннотаций в классах для ссылки на виджеты из верстки экранов [].



3.3 iOS

MVC

Архитектура MVC берет свое начало из 80-х годов двадцатого века. Она была впервые сформулирована Трюгве Реенскаугом. Данная концепция применима при разработке программ для стационарных компьютеров, у которых есть ярко выраженный контроллер в виде мыши и клавиатуры и представление в виде монитора. В таком виде данная архитектура долго и успешно применялась [].

На рис. 11 приведено схематическое изображение архитектуры.

Рис. 11. Структура MVC

Компоненты архитектуры MVC:

– Модель (Model) предоставляет данные и реагирует на команды контроллера, изменяя свое состояние;

– Представление (View) отвечает за отображение данных модели пользователю, реагируя на изменения модели;

– Контроллер (Controller) интерпретирует действия пользователя, оповещая модель о необходимости изменений.

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

В документации от Apple приведена несколько видоизмененная структура работы MVC (Рис. 12) [].

Рис. 12. Видоизмененная структура MVC

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

Несмотря на довольно прозрачную структуру, она несет в себе большие риски превращения в Massive View Controller, так как контроллер очень сильно вовлечен в жизненный цикл представления и становится сложно точно определять, что он является отдельной сущностью. В итоге, в попытках избежать превращения в Massive View Controller, получается, что представление становится классом, который просто перенаправляет действия в контроллер. Соответственно, необходимость в разделении представления контроллера и представления уходит на второй план, и происходит их объединение. Таким образом, в действительности данный паттерн выглядит так, как показано на рис. 13:

Рис. 13. Окончательный вид паттерна MVC

MVVM

Одним из относительно новых подходов к архитектуре приложений является паттерн MVVM (Рис. 14) [].

Рис. 14. Паттерн MVVM

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

1. View;

2. ViewModel;

3. Model.

Model является тем же самым компонентом, что и model в MVC. В условиях iOS разработки View является ViewController, а ViewModel это отдельный класс, который является своеобразным клеем, который соединяет между собой данные и их представление. При этом ключевой особенностью MVVM является то, что ViewModel не содержит ссылки на View. Следовательно, ViewModel может разрабатываться отдельно от View, а View позже может быть заменен на совершенно другой. Это достигается за счет различных подходов для связывания подготовленных данных из ViewModel с представлением:

– Notifications;

– Key Value Observing;

– Callback;

– Delegates;

– Functional Reactive Programming.

Наиболее популярным решением является использование Functional Reactive Programming (FRP). В основе этой парадигмы лежат потоки данных и реагирование на них.

Functional Reactive Programming - это парадигма программирования, впервые введенная Коналом Эллиотом, и являющаяся комбинацией двух понятий:

– Reactive Programming - парадигма, основной идеей которой является фокусировка на потоках данных, а не на постоянных величинах[];

– Functional Programming - парадигма, в которой главенствующее место отводится расчетам с помощью функций в математическом стиле, неизменности и выразительности[].

В самом языке программирования Swift нет поддержки FRP. Однако, существуют различные расширения, позволяющие добавить такую возможность. Два наиболее известных фреймворка[]:

1. RxSwift;

2. ReactiveCocoa.

ReactiveCocoa или RxSwift

Библиотека ReactiveCocoa была написана под Objective-C, когда язык Swift еще не был анонсирован. Затем после выхода Swift основной язык разработки изменился, однако, код на Objective-C остался в проекте.

RxSwift это Swift версия библиотеки Rx, создаваемая командой ReactiveX. Данная команда также занимается разработкой Rx. Net, RxJava or RxJS, и соответственно все эти библиотеки имеют в общем одинаковую структуру. Поэтому при необходимости переход от одного языка к другому потребует знаний в области языка, но не изучения новой библиотеки. Кроме того, данный фреймворк с самого начала разрабатывался на языке Swift, учитывая все его отличия.

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

В данном проекте в разработке используется язык Swift, поэтому было принято решение использовать библиотеку, которая написана на том же языке - RxSwift.

Используя FRP, можно создать несколько асинхронных потоков данных и подписаться на поток событий с помощью интерфейса IObserver <T>. Интерфейс IObservable <T> уведомляет подписанный интерфейс IObserver <T> всякий раз, когда происходит событие.

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

Пример такого связывания:

self.viewModel.sections

asObservable()

bindTo (self.collectionView.rx.items (dataSource: self.dataSource))

addDisposableTo (self.disposeBag)

В этом примере мы подписываемся на последовательность приходящих секций из ViewModel, а затем передаем их в dataSource для UICollectionView. При каждом обновлении переменной sections во ViewModel, будет также происходить обновление CollectionView.

Coordinators

Паттерн MVVM будет использован при создании модулей программы. Архитектурный паттерн для взаимодействия модулей между собой основан на идее Координаторов, предложенной Soroush Khanlou [] на конференции NSSpain'15, а затем проанализированный в статье [] Ильи Пучки.

Координатор - это объект, который управляет одним или несколькими контроллерами представлений. Извлекая всю логику движения из ваших контроллеров представлений, и перемещая эти вещи на один уровень, вы облегчите себе жизнь[].

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

Рис. 15. Структура архитектуры с координатором

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

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

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

3.4 Android

MVP

В разработке приложения на ОС Android была выбрана архитектура MVP. Она отлично подходит для стандартной разработки под ОС Android без необычных особенностей касательно оповещения пользователя об обновлении информации или наоборот - оповещения модели о событиях пользователя. Позволяет разделить код на четкие фрагменты для бизнес-логики и отображения представления. Схема MVP показана на рис. 16 [].

Рис. 16. Структура архитектуры MVP

MVP состоит из следующих компонентов:

– Model;

– View;

– Presenter.

Использование архитектуры MVP позволяет создать абстракцию представления. Для этого реализуется интерфейс представления с набором методов и свойств. Презентер хранит ссылку на представление (реализацию интерфейса) и подписывается на изменения в представлении и обращается к модели для ее изменения. Представление занимается отображением на интерфейсе данных из модели и изменений этой модели. Модель занимается хранением и обновлением данных в связи с изменениями на отображении благодаря движениям пользователя.

Реализация алгоритма нахождения кратчайшего пути

Для реализации алгоритма был создан специальный класс Vertex для представления вершин графа, а также класс Dijkstra, который получает на вход вершины графа, начальную вершину, и просчитывает все кратчайшие пути от нее до остальных. В iOS класс Vertex соответствует протоколам Hashable и Equatable, в Android перегружены методы equalsTo() и hashcode(), это позволяет сравнить две вершины на равенство. Это достигается с помощью идентификатора, который присваивается каждой вершине, и который затем является индикатором равенства или неравенства. Также каждая вершина содержит координаты точки, где она должна быть отображена на карте. При инициализации изображения, полученного с сервера, рассчитывается коэффициент, на который умножается изначальный размер изображения, чтобы увеличить его или уменьшить для полного отображения на экране. На этот же коэффициент затем умножаются координаты каждой вершины. Также каждая вершина содержит массив соседей, каждый из которых представлен кортежем. Каждый кортеж содержит соседнюю вершину и вес пути до этой вершины. Так как вершины являются классами, то они передаются по ссылке, следовательно вершина в кортеже указывает на ту же ячейку памяти, что и вершина в сете, переданном в Dijkstra. Алгоритм Dijkstra получает на вход Set вершин. Этот тип для хранения данных означает, что каждая вершина внутри сета является уникальной. Это позволяет уменьшить количество времени, которое нужно потратить на поиск кратчайших путей из начальной вершины.

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

Алгоритм ближайшего соседа - один из простейших эвристических методов решения задачи коммивояжера. Относится к категории «жадных» алгоритмов.

Определение:

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

3.5 Реализация модуля карты в ОС iOS

Карта помещения, в котором находится пользователь, рисуется в векторном формате для того, чтобы при увеличении качество изображения не изменялось. Для отображения векторного изображения карты используется формат PDF. Так как PDF может хранить векторную информацию, то это позволяет увеличивать изображение карты без потери качества. А за счет того, что информация в файле векторная, итоговый размер файла невелик. Для отображения карты используются встроенные средства для работы с PDF изображениями. Для отображения карты был создан новый класс MapView, которые наследуется от UIVIew. Он состоит по сути из трех слоев:

1. UIScrollView;

2. TiledPDFView (Рис. 17);

3. Слой с вспомогательной информацией.

Первый слой используется для зуммирования карты и скролла. Это системный UI элемент.

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

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

Рис. 17. Листинг класса TiledPDFView.

3.6 Реализация модуля карты в ОС Android

Для отображения карты и основных жестов для взаимодействия с ней используется бибилотека MapView []. Основная концепция заключается в существовании нескольких классов, отвечающих за разные слои в карте, используются из них следующие:

1. MapLayer. Слой, позволяющий поворачивать, зуммировать и передвигать карту;

2. BitmapLayer. Слой, использующийся для отображения карты;

3. MarkLayer. Создан для отображения пинов на карте;

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



3.7 Отрисовка кратчайшего пути на карте

С помощью встроенных средств для работы с PDF файлами было реализовано отображение карты и ее зумирование. Для отображения маршрута используется встроенная библиотека CoreGraphics, позволяющая в данном случае строить маршруты с закругленными углами.

Для работы приложения на ОС Android используется файл карты в формате PNG. В приложении реализована поддержка основных жестов для удобства работы пользователя с картой - зуммирование pinch-to-zoom, а также повороты с помощью двух пальцев. Для отображения маршрута реализованы классы и методы, позволяющие строить маршрут с закругленными углами, как показано на рис. 18.

а б

Рис. 18. Пример отображения кратчайшего пути в iOS (а) и Android (б)

Красными точками отмечены первоначальные точки графа. Зелеными добавленные точки графа, которые планируется посетить.

Для того, чтобы проверить, что три точки находятся не на одной прямой, используется формула нахождения площади. Если три точки образуют площадь больше нуля, то значит они находятся не на одной прямой и через них нужно построить закругленную линию [].

Также при построении закругленной линии указывается радиус закругления, который проставляется как указано на рис. 19.

Рис. 19. Выставление радиуса

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

Реализация определения текущих координат с помощью маячков



3.8 iOS

Для определения текущего местоположения пользователя в пространстве, оборудованным Bluetooth маячками, воспользуемся знаниями полученными в ходе изучения Estimote SDK for Apple iOS [].

В первую очередь необходимо создать вспомогательное приложение, назовем его Location Builder, с помощью которого можно конфигурировать помещение и маячки внутри него. Для этого:

– В личном кабинете Estimote были получены идентификаторы приложения;

– В программу добавлены используемые нами маячки и идентификаторы;

– Добавлен код конфигурации помещения;

– Добавлен код отправки сконфигурированного помещения на сервер.

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

public func indoorLocationManager (_ manager: EILIndoorLocationManager,

didUpdatePosition position: EILOrientedPoint,

with positionAccuracy: EILPositionAccuracy,

in location: EILLocation)

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



3.9 Android

Использование Estimote SDK для Android

В этом разделе будут объяснены фундаментальные аспекты, возможности и ограничения технологии Bluetooth маячков в приложении для платформы Android.

Требования к работе:

– Компьютер с установленным ПО (Android Studio);

– Смартфон с операционной системой Android 4.3 выше;

– Аккаунт Estimote;

– Estimote маячки.

Для начала работы непосредственно с SDK при разработке приложения, необходимо в файл зависимостей build.gradle (Module: app) добавить следующую зависимость []:

compile 'com.estimote:sdk:0.11.1@aar'

Затем необходимо в студии синхронизировать gradle файлы, для добавления необходимых классов в код проекта.

Для того, чтобы приложение работало на устройствах с OC 6 и выше, необходимо запросить разрешения на ACCESS_COARSE_LOCATION в режиме реального времени.

Далее перейдем к мониторингу маячков и определению расстояния до них (далее - ranging).

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

Каждый маячок распространяет свой Bluetooth сигнал с определенной силой - силой, которая уменьшается при преодолении расстояния. Это позволяет приемнику грубо определить, как далеко он находится от маячка.

Начало ranging'a.

В первую очередь необходимо в коде создать экземпляр класса BeaconManager (его сигнатура идет в пакете SDK) и передать ему так называемый идентификатор UUID. Верным решением будет выставить этот идентификатор одинаковым у всех необходимых маячков. Затем у объекта класса BeaconManager необходимо вызвать метод connect. В момент времени, когда произойдет соединение с менеджером, следует в методе обратного вызова onServiceReady, символизирующего о том, что менеджер готов к работе, вызвать метод startRanging, для начала поиска близлежащих маячков.

Важное замечание: при смене активности приложения с «Активно» на «Не активно» необходимо прекратить отслеживание маячков соответствующим методом stopRanging.

Следующим шагом является регистрация так называемого слушателя, который будет оповещать о найденных маячках. Для этого необходимо вызвать метод setRangingListener и ему передать интерфейс BeaconManager. RangingListener, который в свою очередь в методе обратного вызова onBeaconsDiscovered сообщит о найденных маячках и передаст список объектов Beacon всех обнаруженных маячков.

Объект класса Beacon содержит всю необходимую информацию:

– Major

– Minor

– MeasuredPower

– RSSI

– TxPower

Фильтрация сигналов с маячков

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

Фильтр Калмана - один из наиболее популярных алгоритмов фильтрации данных, используемый во многих сферах науки. После обработки данных фильтр избавляется от шумов и убирает лишнюю информацию. В фильтра Калмана есть возможность ввести начальную информацию о характере системы, связи переменных, что сильно помогает выстраивать более точную оценку поведения системы. Но даже в простейшем случае он дает весьма неплохие результаты [, ].

Ниже будет представлено подробное описание работы алгоритма.

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

Рис. 20. Структура архитектуры с координатором

Уравнения представлены в матричной форме. В случае же с одной переменной матрицы вырождаются в обычные скалярные значения.

Подстрочный индекс отвечает за момент времени: k - текущий, k-1 - предыдущий. Верхний индекс со знаком «минус» обозначает, что это предсказанное промежуточное значение.

Перейдем непосредственно к описанию переменных.

- предсказание состояния системы в текущий момент времени.

F - матрица перехода между состояниями (динамическая модель системы).

- состояние системы в прошлый момент времени.

B - матрица применения управляющего воздействия.

- управляющее воздействие в прошлый момент времени.

- предсказание ошибки.

- ошибка в прошлый момент времени.

Q - ковариация шума процесса.

- усиление Калмана (Kalman Gain).

H - матрица измерений, отображающая отношение измерений и состояний.

R - ковариация шума измерения.

- измерение в текущий момент времени.

I - матрица идентичности.

Определение модели процесса.

Для применения описанного алгоритма фильтрации необходимо определить матрицы / значения переменных, определяющих динамику системы и измерений F, B и H.

F - переменная, которая описывает динамику системы. Приравняем эту переменную к 1 (то есть мы явно указываем, что предсказываемое значение и предыдущее состояние будут равны).

B - переменная, которая определяет применение управляющего

воздействия. В нашей модели управляющих воздействий

нет (нет информации о них), поэтому принимаем B = 0.

H - матрица, с помощью нее определяется отношение между измерениями и состоянием системы. Примем ее значение = 1.

Определение сглаживающих свойств

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

На приведенном ниже рисунке можно увидеть результат работы алгоритма фильтрации.

Изначально (без фильтрации) информация с маячков представляет типичную «пилу» с некоторой амплитудой. После применения фильтра можно пронаблюдать (Рис. 21), как кривая сильно сгладилась, и значения в каждой точке приблизились к истинным.

Рис. 21. Результат работы фильтра Калмана

Алгоритм трилатерации

Вычисления при помощи алгоритма трилатерации используют вычисления расстояний для определения неизвестных координат объекта. Точность измерений достигается путем аппроксимации расстояний, используя итеративный метод наименьших квадратов [].

Самый очевидный способ решения задачи определения координат - определить неизвестные координаты как пересечение n сфер, центры которых являются координатами маячков (Рис. 22). Расстояние от приемника до маячка - радиус каждой сферы.

Рис. 22. Приемник в системе, связанной с тремя маячками

Тогда для каждой сферы можно составить уравнение:

+ + = , i = 1, n. (1)

Где x, y, z - координаты маячка; , , - координаты приемника.

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

Приведение к системе линейных уравнений.

Решения системы: A = (2) - значительное улучшение относительно нахождения координат через пересечения сфер.

Необходимо привести систему (1) к виду (2).

Прибавим и вычтем , , в уравнении (1). Получим:

+ + =

Раскрыв скобки и перегруппировав, получаем:

)) + )) + )) =

[ + + + + + ] =

[ + ] = ,

Где

=

- дистанция между маячками i и j.

В данном случае j-ое уравнение было использовано в качестве инструмента линеаризации. Так как не имеет значения, какое уравнение использовать в качестве такого инструмента, обычно выбирают 1-ое уравнение. Так как i = 1, n; это ведет к системе из n-1 переменных с тремя неизвестными.

)) + )) + )) = [ + ] =

)) + )) + )) = [ + ] =

)) + )) + )) = [ + ] =

Такая система линейных уравнений легко сводится к матричной форме:

A = (3)

Имеем:

A = , = , =

Метод наименьших квадратов.

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

Так как расстояния всего лишь приближенные, требуется определить как A

Минимизируем сумму квадратов:

S = =

Что в свою очередь ведет к:

= . (4)

Существует несколько способов решения выражения (4)

Если матрица не сингулярная, то:



=

Серверная часть системы

3.10 Выбор сервера для хранения данных

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

Одним из хорошо зарекомендовавших себя сервисом является Firebase. Основной идеей сервиса является использование NoSQL базы данных. Это позволяет сократить время получения данных, а также дает возможность спроектировать приложение так, чтобы пользователь получал все недостающие файлы с сервера после восстановления подключения к интернету [, ].

Кроме того, Firebase предоставляет много других функций и сервисов, представленных на рис. 23.



Рис. 23. Сервисы, предоставляемые Firebase.

3.11 Формирование базы данных на сервере

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

1. Избегать вложенных данных;

2. Создавать необходимо легко масштабируемую структуру данных;

3. Максимально денормализировать данные и разбивать их по группам, чтобы получать только необходимую информацию по запросу.

Как должна выглядеть структура базы данных на первый взгляд:

- Корневая ссылка

- Помещение 1

- Название

- Идентификатор

- Список вершин графа карты

- Вершина g1

...