Разработка математического и программного обеспечения сервиса позиционирования в линейных сетях на примере метрополитена

Семенов Александр Евгеньевич

Разработка математического и программного обеспечения сервиса позиционирования в линейных сетях на примере метрополитена

Благодаря автономности и оперативности получения пространственных координат, спутниковое позиционирование на сегодняшний день является самым распространенным способом определения местоположения. Однако несмотря на глобальность охвата, ГНСС-технологии не могут применяться повсеместно. Препятствия на пути сигнала, идущего от спутника к приемнику приводят к его переотражению и затуханию , что, в свою очередь, вызывает большие ошибки и потерю сигнала. В связи с этим, в закрытых пространствах используют альтернативные способы локальных систем позиционирования. Применяемые в таких системах подходы, во многом основаны на классических методах определения местоположения. Однако помимо широты охвата с точки зрения разнообразия применяемых технологий, системы используют и новые уникальные методы. Одним из них является метод локализации по шаблону, зарекомендовавший себя как наиболее точный метод позиционирования в закрытых пространствах. Несмотря на стремительное развитие локальных систем позиционирования и их повсеместное внедрение, остаются пространства, где задача определения местоположения по-прежнему актуальна. В качестве примера можно взять сеть метрополитена, сложная архитектура которого заставляет пользоваться средствами навигации не только туристов, но и жителей города. Кроме того, задача актуальна и для аналогичных линейных сетей, начиная от туннелей рудных шахт и заканчивая ускорителями заряженных частиц. В представленной работе рассматривается технология позиционирования в линейной сети метрополитена по методу локализации по шаблону. По причине активного развития сотовой коммуникации в подземном транспорте, в качестве основы для создания базы шаблонов были использованы данные цифровой сотовой сети. Ключевым преимуществом разрабатываемой технологии над аналогичными системами позиционирования на основе беспроводных сетей является учет динамики сигнала, принимаемый от станции сотовой сети в процессе движения объекта. В рамках исследования были обозначены существующие подходы и технологии для решения задачи позиционирования в помещениях. Более подробно изложена методика местоопределения по данным цифровой сотовой сети. В работе описывается процесс подготовки, анализа, обработки и конечного представления пространственной базы данных, а также ключевые моменты разработки и математической оценки точности алгоритма позиционирования. Приводится пример использования веб-гис для визуализации пространственных данных с целью оперативного мониторинга изменений состояния линейной сети. Рассматривается логическая часть мобильного приложения для позиционирования в метрополитене, подводятся промежуточные итоги и поднимаются вопросы дальнейшего совершенствования технологий и их применения в линейных сетях схожего типа.

Охрана окружающей среды. Экология человека

Дипломы

Вуз: Санкт-Петербургский государственный университет (СПбГУ)

ID: 587d36475f1be77c40d58b5f

UUID: e393b12a-a519-48f2-b441-7d9ca2f4e337

Язык: Русский

Опубликовано: почти 8 лет назад

Просмотры: 19

Семенов Александр Евгеньевич

Источник: Санкт-Петербургский государственный университет

Комментировать 0

Рецензировать 0

Скачать - 5778048 bytes

Поделиться работой

Санкт-Петербургский Государственный Университет Семенов Александр Евгеньевич Разработка математического и программного обеспечения сервиса позиционирования в линейных сетях на примере метрополитена Выпускная квалификационная работа бакалавра «К защите» Научный руководитель: асс., Э.Э. Казаков « » 2016 Заведующий кафедрой: д.г.н, доц. Е.Г. Капралов « г. Санкт-Петербург 2016 » 2016

2 Оглавление Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 Глава 1. Проблема позиционирования . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.1 Определение позиционирования . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.2 Методы измерения пространственных координат . . . . . . . . . . . . . . . . . 8 1.2.1 Астрономо-геодезические . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.2.2 Инерциальные . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.2.3 Фотограмметрические . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.3 Глобальные системы позиционирования(GPS) . . . . . . . . . . . . . . . . . . . 12 1.4 Локальные системы позиционирования(LPS) . . . . . . . . . . . . . . . . . . . 13 1.4.1 Беспроводные сети . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.4.2 Инерциальные системы . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 1.4.3 Светодиодные лампы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 1.4.4 Магнитное поле . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 1.4.5 QR-коды . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 1.4.6 Гибридные системы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 1.5 Позиционирование в линейных сетях как подмножество задач позиционирования в помещениях . . . . . . . . . . . . . . . . . . . . . . . . . . 19 1.5.1 Позиционирование в метрополитене . . . . . . . . . . . . . . . . . . . . . 21 Глава 2. Обоснование методики позиционирования в линейных сетях . . . . 23 2.1 Характеристика цифровой сотовой сети . . . . . . . . . . . . . . . . . . . . . . 24 2.2 Позиционирование на основе сигнала цифровой сотовой сети . . . . . . . . . . 25 2.3 Локализация по шаблону . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 2.3.1 Общий приницп . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 2.3.2 Офф-лайн фаза. Географическая привязка . . . . . . . . . . . . . . . . 26 2.3.3 Офф-лайн фаза. Нормализация данных . . . . . . . . . . . . . . . . . . 28 2.3.4 Он-лайн фаза. Алгоритм позиционирования . . . . . . . . . . . . . . . . 31 Математическая оценка алгоритма позиционирования . . . . . . . . . . . . . . 33 Глава 3. Сбор и анализ данных . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 2.4 3.1 Технология сбора данных . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 3.2 Мониторинг состояния БД . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 Глава 4. Разработка программного обеспечения . . . . . . . . . . . . . . . . . . . 39 4.1 Создание и обработка базы шаблонов. . . . . . . . . . . . . . . . . . . . . . . . 39 4.2 Программное обеспечение для обработки данных . . . . . . . . . . . . . . . . . 49 4.3 Мобильное приложение для позиционирования . . . . . . . . . . . . . . . . . . 50

3 Заключение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 Список сокращений и условных обозначений . . . . . . . . . . . . . . . . . . . . 53 Список литературы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 Приложение А. Листинги программного кода . . . . . . . . . . . . . . . . . . . 58 Приложение Б. Картографическая визуализация состояния сотовой сети метрополитенов Москвы и Санкт-Петербурга в веб-гис NextGisWeb . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

4 Введение Информация о местоположении объекта используется для решения как строго на учно-производственных, так и бытовых задач: обывателю она позволяет ориентироваться на местности, находить интересующие места, прокладывать маршруты [1]; для географа важную роль играет связь объекта изучения с его положением во времени и пространстве; координиированные данные являются основой для построения пространственных моделей в ГИС [2], используются для индексации данных в поисковых машинах [3]. На протяжении тысячелетий было разработано множество методов и способов опреде ления местоположения. Однако революция в решении задачи местоопределения произошла с появлением глобальных навигационных спутниковых систем(ГНСС). Причиной этому по служили глобальность охвата, высокая точность и оперативность спутникового позициони рования [2]. Сегодня наблюдается тенденция роста потребителей ГНСС-технологии в связи с расширением рынка мобильных устройств. Наличие портативных приемников в смартфо нах привело не только к активному использованию приложений на основе пространственных данных(LBS) [4], но и к созданию вторичных продуктов: так новые возможности для состав ления карт открыл феномен «краудсорсинга» [5]. Несмотря на то, что геодезические спутники покрывают всю поверхность Земли, ГНСС приемники нельзя применять повсеместно. Их явное использование в закрытых простран ствах ограничено по причине ослабления сигнала, проходящего через землю, стены, воду и другие препятствия. И хотя все же существуют способы, основанные на использовании ре трансляторов спутниковых сигналов(псевдолитов), они едва ли могут быть решением в связи с затратами на установку дорогостоящего оборудывания и низкой точностью местоопреде ления [6]. Поэтому для закрытых пространств необходимо искать альтернативные способы решения задачи. Помещения являются одним из примеров таких закрытых пространств. В них люди проводят большую часть своего времени, что вызывает интерес к системам определения ме стоположения [7]. Такие системы находят применение в классических задачах навигации, составлении карт, размещении контекстной информации, рекламы и тд., а также характер ных задач обеспечения безопасности в процессе строительства [8], помощи в чрезвычайных ситуациях, удаленного управление машинами/роботами [9]. Единого и общепринтого способа позиционирования в помещениях, как в случае с ГНСС, на сегодняшний день не существует [10]. Напротив, создается много различных си стем и выбор конкретной часто зависит от структуры пространства, объекта, местополо жение которого необходимо определять, а также требуемых точностей [11]. Существующий набор способов ранжируется в зависимости от затрат на реализацию, что также играет нема ловажную и, зачастую, решающую роль. Отсюда остается большое количество пространств, где задача определения местоположения все еще остается нерешенной.

5 Одним из примеров таких пространств является сеть городского метрополитена. С точ ки зрения пространственной архитектуры, она представляет собой точки(станции), соеди ненные линиями(туннелями). Первые – это классический пример помещений, аналогичных торговым центрам, комплексам, магазинам и другим сооружениям, где человек или робот может перемещаться практически свободно. Двигаясь по линиям, вектор перемещения пред определен, что облегчает решение задачи местоопределения. Позиционирование в линейной сети метрополитена может быть использовано в качестве модели для применения в других аналогичных структурах, таких как автомобильные и железные дороги, тоннели, шахты, трубы и пр. Цель представленной работы – разработать систему определения местоположения в сети метрополитена и оценить возможность ее использования в других линейных сетях. Кон цепция разработки основана на принципах минимизации финансовых вложений, открытости данных и программного обеспечения, а также применения краудсорсингового подхода. Для достижения поставленной цели было необходимо решить следующие задачи: 1. Выбрать способ позиционирования 2. Разработать алгоритм системы позиционирования 3. Создать прототип клиентского приложения для позиционирования в метрополитене 4. Провести математическую и практическую оценку точности системы позициониро вания Практическое применение аналогичных систем позиционирования в линейных сетях достаточно широко. В [12] описывается система позиционирования на основе данных гло бальной цифровой сотовой сети(GSM1 ) в ЦЕРНе. В [9] используется аналогичный подход для навигации роботизированных машин по добыче угля, а в [13] для этих же целей при меняются инерциальные системы. На основе инерциальных систем также работает система позиционирования в линейной сети метрополитена, описанная в [14]. При изучении особенностей систем позиционирования в целом, было выявлено множе ство факторов, влияющих на использование конкретного способа позиционирование. В связи с этим было принято решение создать гибридную систему, которая сочетает в себе несколько подсистем позиционирования. Первый шаг для ее создания – это использование GSM-позици онирования как базовой подсистемы. В работе описываются теоретическая и практическая части ее разработки. В первой главе раскрывается определение позиционирования, приводится перечень су ществующих методов и способов. Определяется место позиционирования в линейных сетях на основе GSM, как класса задач позиционирования. Во второй главе приводится краткая характеристика GSM, описываются особенности данных. Дается теоретическое обоснование выбранного способа позиционирования, рассмат риваются используемые математические подходы. Практическая реализация приводится в третьей и четвертой главах. В третьей главе описывается методика сбора данных. Четвертая 1 В дальнейшем под GSM будет пониматься глобальная цифровая сотовая сеть в целом, а не ее стандарт второго пополения

6 глава посвящена реализации программного обеспечения. В заключении говорится о возмож ных вариантах развития системы. Резюмируются итоги исследования.

7 Глава 1. Проблема позиционирования Человечество издавна интересовали вопросы «Где я нахожусь?» и «Куда я должен дви гаться?». До сих пор, имея определенную подготовку, на них можно ответить, используя приметы ландшафта и вооружившись компасом и картой. Для увеличения точности опре деления местоположения изобретались десятки астрономических, геодезических приборов и совершенствовались методы линейно-угловых измерений[15]. В XX веке запуск первого ИСЗ положил начало революционной технологии определения пространственных координат методами спутниковой геодезии. Создаваемая для военной цели оперативного и автомном ного измерения пространственных координат, ориентировки и скорости движения объектов, в конечном счете системы спутникового позиционирования нашли применение в решении не только научных, но и бытовых задач. Однако спутниковые методы справляются с решением задачи позиционирования лишь до тех пор, пока речь не заходит о местах, где распростра нение сигнала ограничено или невозможно. В этом случае в силу вступают альтеративные способы позционирования [4],[11]. 1.1 Определение позиционирования В соответствии с [16] позиционирование – «получение пространственных координат объ екта по наблюдениям навигационных спутников с использованием аппаратуры потребителей ГНСС». Как видно из определения, в сущности, задача позиционирования заключается в определении координат объекта на местности. Известно, что ее можно решать как в глобаль ной(относительно общеземной модели), так и в локальной(в пределах определенной терри тории) системах координат. В глобальной системе вычисляют абсолютные геоцентрические коориднаты, а в локальной – относительные. Традиционно для определения абсолютных ко ординат используют астрономические методы, основанные на пространственно-временных параметрах небесных светил. Для определения относительных координат используют геоде зические и фотограмметрические методы, основанные на измерениях относительно наземных пунктов с известными координатами. На таком принципе основаны классические способы триангуляции, полигонометрии, тахеометрии и фототриангуляции. Астрономические и геодезические измерения проводятся в оптическом диапазоне, вследствие чего основным требованием является наличие оптической видимости точек на блюдения. По этой причине, возможность проведения работ зависит от погодных условий, рельефа местности, времени суток. Кроме того, измерительный процесс занимает продолжи тельное время и требует специализированных знаний. Встает задача создания оперативного и автономного определения местоположения. Объективных причин для их создания мно жество: задачи морской, воздущной и подземной, подводной навигации и тд.. Впервые они

8 стали осуществимы с изобретением инерциальных систем навигации(ИНС), которые поз воляют определять положение, скорость, перемещение объекта на основании собственных датчиков. Эти системы, как и в случае с классическими геодезическими и фотограмметри ческими методами, могут измерять параметры перемещения только в случае, если известно исходное положение объекта. Другими словами, ИНС позволяют определять относительные координаты объекта. Для создания системы оперативного определения абсолютных координат в эксплуата цию была введена ГНСС, вместо естественных небесных светил использующая искусствен ные спутники Земли. В связи с абсолютной автономностью и оперативностью доминирующее место в решении задачи местоопределения сегодня занимает именно спутниковое позицио нирование. Возвращаясь к терминологии, более научное определение дается в [17]: «позициониро вание – определение по спутникам параметров пространственно-временного состояния объек тов, таких как координаты объекта наблюдения, вектор скорости его движения, приращение координат по каждой координатной оси между двумя объектами, точное время наблюде ния» . Как видно термин не являются всеобъемлющем и априори относит определение ме стоположения исключительно к задачам спутикового позиционирования. Астрономические, геодезические, фотограмметрические и даже инерциальные методы, в сущности решающее ту же задачу, в определении не фигурируют. Кроме того, спутниковые системы навигации охватывают хоть и глобальное, но ограниченное пространство для применения: при таком способе позиционирования измеряют параметры сигнала, который переотражается и теряет мощность под водой, землей, в горах и помещениях. В связи с этим можно констатировать, что ГНСС решение задачи не ограничивается. Для того, чтобы выделить отдельный класс способов позиционирования, решающих проблему ГНСС, в зарубежной литературе приводится термин локальных систем позицио нирования(LPS), которые позволяют в автономном и оперативном режиме определять про странственное положение объекта в ограниченном пространстве [18]. 1.2 Методы измерения пространственных координат Несмотря на появление абсолютно новых подходов к решению задачи позициониро вания как на глобальном, так и на локальном уровне, все они основаны на классических методах измерения положения координат точек местности. 1.1.

9 Рисунок 1.1 — Связь методов и способов оперативного позиционирования 1.2.1 Астрономо-геодезические Классическая задача определения координаты пункта 𝐴, при известных координатах пунктов 𝐴1 , 𝐴2 ,...,𝐴𝑁 и углах 𝛼1 ,𝛼2 ...𝛼𝑚 решается при помощи угловой засечки по форму лам Юнга(прямая задача) и Гаусса(обратная задача). Чтобы построить один треугольник засечки, необходимо иметь хотя бы два исходных пункта. Однако обычно имеется несколько треугольников, объдиненных в сеть, и в этом случае решается система уравнений(прямая задача): ⎧ 2 )+𝑋2 ·𝑐𝑡𝑔(𝛼1 )−𝑌1 +𝑌2 ⎪ ⎪ 𝑋𝐴 = 𝑋1 ·𝑐𝑡𝑔(𝛼𝑐𝑡𝑔(𝛼 ⎪ 1 )+𝑐𝑡𝑔(𝛼2 ) ⎪ ⎪ ⎪ 𝑌1 ·𝑐𝑡𝑔(𝛼2 )+𝑌2 ·𝑐𝑡𝑔(𝛼1 )−𝑋1 +𝑋2 ⎪ ⎪ 𝑌 = ⎪ 𝑐𝑡𝑔(𝛼1 )+𝑐𝑡𝑔(𝛼2 ) ⎨ 𝐴 ... ⎪ ⎪ ⎪ 𝑚 )+𝑋𝑛 ·𝑐𝑡𝑔(𝛼𝑚−1 )−𝑌 𝑛−1+𝑌𝑛 ⎪ ⎪ 𝑋𝐴 = 𝑋𝑛−1·𝑐𝑡𝑔(𝛼𝑐𝑡𝑔(𝛼 ⎪ 𝑚−1 )+𝑐𝑡𝑔(𝛼𝑛 ) ⎪ ⎪ ⎪ ⎩𝑌 = 𝑌 𝑛−1·𝑐𝑡𝑔(𝛼𝑚 )+𝑌𝑛 ·𝑐𝑡𝑔(𝛼𝑚−1)−𝑋𝑛−1+𝑋𝑛 𝐴 𝑐𝑡𝑔(𝛼𝑚−1)+𝑐𝑡𝑔(𝛼𝑚 ) (1.1) где: 𝑋𝐴 ,𝑌𝐴 – координаты определяемой точки A Традиционно, угловая засечка применяется в астрономических наблюдениях положе ния небесных светил и при построении геодезической сети способом триангуляции. Линейную засечку используют для вычисления координат пункта 𝐴, при известных координатах пунктов 𝐴1 , 𝐴2 ,...,𝐴𝑁 и сторонах 𝐷1 ,𝐷2 ...𝐷𝑛 . Общий случай линейной засечки – пространственная линейная засечка, когда известны не только плановые но и высотные координаты исходных пунктов[17]:

10 ⎧ ⎪ ⎪ 𝐷12 = (𝑋1 − 𝑋𝐴 )2 + (𝑌1 − 𝑌𝐴 )2 + (𝑍1 − 𝑍𝐴 )2 ⎪ ⎪ ⎪ ⎪ ⎨𝐷2 = (𝑋 − 𝑋 )2 + (𝑌 − 𝑌 )2 + (𝑍 − 𝑍 )2 2 𝐴 2 𝐴 2 𝐴 2 ⎪ ⎪ ... ⎪ ⎪ ⎪ ⎪ ⎩𝐷2 = (𝑋 − 𝑋 )2 + (𝑌 − 𝑌 )2 + (𝑍 − 𝑍 )2 𝑛 𝐴 𝑛 𝐴 𝑛 𝐴 𝑛 (1.2) где: 𝑋𝐴 , 𝑌𝐴 , 𝑍𝐴 – координаты определяемой точки A 𝑋𝑖 , 𝑌𝑖 , 𝑍𝑖 , 𝑖 = 1..𝑛 – известные координаты точек 𝐴𝑖 Классический пример использования линейной засечки – геодезическая трилатерация. 1.2.2 Инерциальные Сущность определения местоположения с использованием инерциальных методов состо ит в определении положения движущегося объекта по линейным и угловым составляющим его ускорения. Линейные составляющие измеряются при помощи акселерометров, угловые – при помощи гироскопов. Зная исходное положение объекта, можно определить вектор его движения путем непрерывного интегрирования совокупности дифференциальных уравнений вида 1.3 [17]. ∫︁ 𝑥= 𝑡 ∫︁ ( 0 𝑡 𝑎𝑥 𝑑𝑡 + 𝑣𝑥 0)𝑑𝑡 + 𝑥0 (1.3) 0 Основное преимущество использования инерциальных систем – их независимость от внешних источников: все измерения проводятся на основе датчиков самой системы. Поэтому их можно применять вне зависимости от среды(водная или воздушная, закрытая или откры тая). Накопление ошибок в таких системах прямо пропорционально времени, что является основной проблематикой их применения. По этой причине, для инерциальных систем необхо дима периодическая калибровка. Однако в случае изменения местоположения за короткий промежуток времени их точность становится на порядок выше. Эта особенность является определяющей для использования инерциальных методов при аэрокосмической съемке [19]. 1.2.3 Фотограмметрические Из фотограмметрии известно, что местоположения точек местности можно определять по фотоснимкам. В его основе лежит условие коллинеарности, согласно которому центр фо тографирования, точка местности и ее изображение на фотоснимке лежат на одной прямой. Для того, чтобы им воспользоваться необходимо устройство для фиксации изображения,

11 сопряженное с вычислительным центром, элементы ориентирования изображения относи тельно геодезической системы координт, а также механизм определения положения точек фотоснимка во внутренней системе координат. Сущность определения положения точки мест ности по точкам фотоснимка показана на Рис. 1.2. Рисунок 1.2 — Связь координат точек аэроснимка и местности [20] Зависимость (1.4) позволяет связать координаты фотоснимка с координатами точки местности, если известна ее высота1 [20]: ⎧ ⎨𝑋 ⎩𝑌 𝑀 𝑀 − 𝑋𝑆 = (𝑍𝑀 − 𝑍𝑆 ) · − 𝑌𝑆 = (𝑍𝑀 − 𝑍𝑆 ) · 𝑎1 𝑥+𝑎2 𝑦−𝑎3 𝑓 𝑐1 𝑥+𝑐2 𝑦−𝑐3 𝑓 𝑏1 𝑥+𝑏2 𝑦−𝑏3 𝑓 𝑐1 𝑥+𝑐2 𝑦−𝑐3 𝑓 (1.4) где: 𝑋𝑀 , 𝑌𝑀 , 𝑍𝑀 – координаты точки местности в системе OXYZ 𝑥𝑚 , 𝑦𝑚 , 𝑧𝑚 – координаты изображения точки местности на фотоснимке 𝑋𝑆 , 𝑌𝑆 , 𝑍𝑆 – линейный элементы внешнего ориентирования фотоснимка 𝑥, 𝑦, 𝑧 – координаты точек снимка в системе oxy 𝑎𝑖 , 𝑏𝑖 , 𝑐𝑖 , 𝑖 = 1..3 – направляющие косинусы, являющиеся функциями от угловых элемен тов внешнего ориентирования фотоснимка Проблема использования зависимости (1.4) состоит в том, что обычно элементы внеш него ориентирования(ЭВО) и высота точки местности неизвестны. Для нахождения ЭВО, используют опорные точки местности с известными геодезическими координатами. Зная как минимум три такие точки, можно вычислить линейные и угловые элементы внешне го ориентирования. Для нахождения высоты есть два подхода: на основе теории стереопары фотоснимков строится модель рельефа или же берется некоторая средняя высота на всю площадь снимка. Применение того или иного подхода зависит от требуемых точностей. 1 Для системы координат SXYZ

12 1.3 Глобальные системы позиционирования(GPS) Все ГНСС сотоят из трех сегментов: космического(спутники), управляющего(наземные станции) и потребительcкого(приемники). Несмотря на радикальное изменение возможно стей определения координат, спутниковое позиционирование основывается на классичекой пространственной линейной засечке. Для ее решения от каждого спутника(всего их должно быть не менее 4-x) к приемнику передаются т.н. эфимириды, в которых содержится ин формация о координатах спутников (Рис. 1.3). Расстояние вычисляется двумя способами: фазовым(POA) и кодовым(TOA) [21]. Первый имеет высокую геодезическую точность и, со ответственно, стоимость. Второй же значительно ниже по точности, и цене приемного обору дывания, и, как следствие, значительно более распространенный: именно кодовые приемники устанавливают в смартфоны. Рисунок 1.3 — Концепция определения положения объекта способом GPS [21] В связи с накоплением ошибок при прохождении сигнала через атмосферу, для целей высокоточного позиционирования также применяется дифференциальный способ. Его сущ ность состоит в вычислении приращения координат пунктов при измерении несколькими приемниками с учетом абсолютных координат опорной станции. В этом случае предполага ется, что ошибки приемника на базовой станции будут повторяться и на соседних пунктах. Они могут быть учетены при помощи транслирования поправок, которые вычисляются по абсолютным координатам опорной станции [17]. Точность определение абсолютных координат при абсолютном ГНСС-позиционирова нии в плоскости XY составляет не более 3.5 метров. Использование же дифференциального способа и постобработки позволяет достигать миллиметровых точностей. [22] Сегодня в штатном режиме действуют две полноценные ГНСС: американская(GPS)[22] и российская(ГЛОНАСС)[23]. Активно развиваются и ГНСС других стран: европей ская(Galileo)[24] и китайская(Beidou)[25].

13 1.4 Локальные системы позиционирования(LPS) 1.4.1 Беспроводные сети Беспроводные сети позволяют передавать информацию между устройства ми(Bluetooth), обеспечивают выход в Интернет(Wi-Fi) и обеспечивают абонентов сотовой связью(GSM). Помимо этого, на их онове построены самые распространенные способы пози ционирования в помещениях. Они подразделяются на локальные(LAN) и глобальные(WAN). В первых информация передается на коротких волнах, в последних – на длинных. Покрытие локальных сетей значительно меньше, по сравнению с глобальными, а точность существенно выше[12]. Методика позиционирования во всех беспроводных сетях схожая и заключается в анализе параметров передающих станций на приемнике. В качестве приемника обычно выступает датчик смартфона. Передатчиком в GSM-сетях(CPS) является станция цифровой сотовой сети, в Wi-Fi сетях – точка доступа(AP), а в Bluetooth – специальные маячки(т.н. «биконы»). В [4] приводится классификация способов позиционирования в беспроводных сетях: – Анализ соседства(Proximity). Местоположение определяется зоной покрытия некоторого радиопередатчика. Разброс ошибок будет прямо пропорционален площа ди покрытия конкретным передающим устройством [26]. – Линейная засечка. Классический геодезический метод измерения, в котором рас стояние является функцией параметров сигнала [27]. – Анализ сцены(Scene граммы(Radio Analysis). Frequency Также известен analysis) и метод как анализ локализации по радио шабло ну(Fingerprinting). Точность этого метода считается самой высокой, но подвержена изменениям во внешней среде [4], [11], [8]. Анализ соседства не требует вычислений параметров сигнала. В случае использования этого метода, от точки Wi-Fi или Bluetooth передатчика требуется только его уникальный идентификатор, на основе которого можно получить координаты станции и привязанную к ней контекстную информацию[28]. При использовании линейной засечки и локализации по шаблону измеряют следующие параметры передающей станции, точки или маячка[29]: 1. AOA(Angle Of Arrival) – угол приходящего сигнала. Местоположение определяет ся по методу обратной угловой засечки. Главный недостаток – возикновение ложных углов вследствие переотражения приходящего сигнала. 2. TOA(Time Of Arrival) – время распространения сигнала(аналогичен кодовому способу ГНСС-позиционирования). 3. POA(Phase Of Arrival) – фаза принимаемого сигнала(аналогичен фазовому спо собу ГНСС-позиционирования).

14 4. RSS(Recieved-Signal Strength) – сила принимаемого сигнала. При использовании линейной засечки, основанной на RSS, используют зависимость между расстоянием и силой принимаемого сигнала. Из законов телекоммуникации известна формула Фриса[30]: 𝑃𝑑 = 𝑃0 − 10 · 𝑛 · 𝑙𝑔( 𝑑 ) 𝑑0 (1.5) где: 𝑃𝑑 – RSS 𝑃0 – сила сигнала, измеренная на калибровочном расстоянии 𝑛 – коэффициент потери мощности сигнала при распространении в некоторй среде 𝑑 – расстояние между приемником и передатчиком 𝑑0 – калибровочное расстояние Из формулы следует, что, имея калибровочную мощность на известном расстоянии от передатчика, можно получить расстояние в любой точке покрываемой передатчиком зоны. Проведя аналогичные измерения единовременно с 𝑛 вышкек с известными координатами, можно получить 𝑛 расстояний. Используя формулу линейной засечки, на следующем шаге можно вычислить местоположения принимающего устройства [27]. Методика локализации по шаблону состоит из двух этапов. Первая т.н. офф-лайн фа за заключатеся в последовательном измерением параметра сигнала(это может быть AOA, TOA, POA и/или RSS) в каждой точке помещения, на основе чего создается карта-радио грамма (Рис. 1.4). В он-лайн фазе данные, полученные в реальном времени сравниваются с имеющимися в базе данных. Наиболее схожий участок базы и будет являться текущим местоположением приемника[4]. Рисунок 1.4 — Пример карты-радиограммы [31] Выбор беспроводной сети для целей позиционирования в первую очередь зависит от тре буемых точностей и финансовых возможностей заказчика. Так как спрос на сотовую связь и Интернет постепенно ведет к повсеместному внедрению цифровой сотовой сети и сети Wi-Fi, финансовые затраты на эти две технологии минимальны. Из них Wi-Fi сети дают более вы сокую (метровую) точность [4], в связи с чем по праву занимают лидирующую позицию по

15 популярности среди всех LPS. Хотя LAN сети заметно уступают всем беспроводным сетям по точности(от сотен до десятков метров [32]), они незаменимы на обширных пространствах, где нет необходимости в точном определении местоположения. Сети Bluetooth развиты в меньшей степени, однако этот стандарт активно популяризи руется компанией Apple, которая продвигает свой бренд маячков «iBeacon». В основном их применяют для целей геоконтекстной информации и навигации. Практическое применение биконов выявило две основные проблемы: недолговечность и высокое энергопотребление[33]. Несмотря на это, использование метода локализации по шаблону позволяет добиваться суб метровых точностей позиционирования [34]. В ультразвуковых сетях(UWB) измеряются параметры сигнала на ультразвуковых вол нах, в связи с чем чувтсвителность к изменениям во внешней среде намного ниже. Поэтому UWB системы обладают самой высокой точностью позиционирования([35],[12]). Основным недостатком таких систем являются финансовые затраты на систему передатчиков ультра звуковых волн [11]. 1.4.2 Инерциальные системы Наиболее популярным способом позиционирования при помощи инерциальных систем является Pedestrian Dead Reckoning(PDR) – «навигационное счисление пути». PDR-системы постоены на инерциальных системах, а основой для позиционирования служат встроенные в мобильные устройства акселеромеры и гироскопы. С их помощью последовательно решают задачи определения шага(от момента отрыва стопы до ее постановки), его длины и направле ние движения пользователя. Отмечается, что способ удобен для определения местоположе ния роботов[36]. Когда же инерциальные системы используются человеком, возникает резкое накопление ошибок в связи со сложностью и случайностью его перемещения. Человек может класть смартфон в карман, поворачивать его перпендикулярно движению. Поэтому их ча сто используют для определения резких скачков ускорения в сочетании с другими системами позиционирования[37],[36]. 1.4.3 Светодиодные лампы Позиционирование по свету ламп стало возможным c появлением светодиодных ламп(LED), которые позволяют передавать информацию в оптическом диапазоне длин волн, аналогично Wi-Fi2 [39]. Если лампы будут передавать на приемник собственные координаты, 2 Отсюда произошел термин Li-Fi, впервые упомянутый Харальдом Хаасом на своем выступлении на TED-конференции в 2011 году[38]

16 то для определения местоположения может применяться фотограмметрический метод (см. раздел 1.4). Используется стандартный подход, за тем исключением, что в роли фотоаппара та выступает сенсор экрана мобильного телефона. При попадании на него света как минимум от трех ламп, можно найти элементы внешнего ориентирования мобильного устройства, по сле чего по координатам пикселов сенсора вычисляется его пространственное положение(Рис. 1.5). Фотограмметрический метод позволяет добиваться субметровой точности местоопреде ления [40]. Рисунок 1.5 — Использование светодиодных ламп для передачи информации [39] Существуют реализации систем позиционирования, основанных на силе принимаемого сигнала от LED. Принип аналогичен тому, что применяется в сетях Wi-Fi, только вместо радиоволн, на приемник приходят оптические волны. При таком подходе добиваются субсан тиметровой точности позиционирования [41]. Главное ограничение на широкое применение таких систем – это небольшая зона покры тия света от лампы, поэтому Li-Fi используют только в относительно небольших помещени ях. Кроме того, при фотограмметрическом методе решения необходимо попадание света от трех ламп единовременно, что во многих местах не наблюдается. 1.4.4 Магнитное поле Известно, что изменения в магнитном поле Земли вызваны наличием элементов же леза в различных предметах. Помещения, где их концентрация особенно высока, обладают уникальной и неоднородной картиной магнитного поля. Эту неоднородность используют для

17 целей позиционирования: применяют метод локализации по шаблону. По аналогии с позици онированием по шаблону в беспроводных сетях, в оффлайн фазе составляется карта-шаблон исследуемой территории, в каждой ячейке которого содержатся параметры магнитного по ля(Рис. 1.6). В онлайн фазе параметры магнетометра сравниваются с картой, после чего находится наиболее подходящий участок, который и будет показывать текущее местополо жение устройства. MPS-позиционирование позволяет добиваться метровых точностей [42]. Рисунок 1.6 — Пример шаблона магнитного поля[31] Преимуществом такой системы является отсутствие затрат на покупку дополнительно го оборудывания. Главный же недостаток – изменения во внутренней инфраструктуре поме щения(к примеру, перепланировка), которые в свою очередь влияют на картину магнитного поля. При каждой флуктуации такого рода необходимо проводить повторные измерения для обновления карты-шаблона [11]. 1.4.5 QR-коды Классический представитель класса систем основанных на методе анализа соседства. Владелец помещения устанавливает специальные штрих-коды, с зашифрованной url-ссылкой на веб-страницу, на которой указываются географическое положение метки на плане здания и контекстная информация(текстовая, аудио, видео, реклама), относящаяся к данной точке. Пользователь, на мобильном устройстве которого предустановлено ПО для интерпретации QR-кода, фотографирует метку, после чего на экране отображается заложенная в нем инфор

18 мация3 . Способ считается выгодным с точки зрения финансовых затрат и скорости создания системы – сегодня он активно применяется для определения местоположения в музеях [43]. Однако способ неприемлем для непрерывного отслеживания местоположения. Рисунок 1.7 — Пример QR-кода на сайт http://openstreetmap.ru 1.4.6 Гибридные системы Во всех перечисленных способах есть свои недостатки. Поэтому часто разрабатываются системы, сочетающие в себе все плюсы составляющих. В [44] описывается использование гибридной системы на основе сочетания MPS, Wi-Fi и PDR. В этом исследовании проводится сравнительный анализ систем во всех возможных сочетаниях (Wi-Fi и PDR, MPS и Wi-Fi и тд.) и их программная реализация(Рис. 1.8). Средняя ошибка комбинации трех компонентов составила порядка 3-х метров. В [27] используют сочетание беспроводных сетей Wi-Fi и GSM. Авторы утверждают, что для позиционирования по точкам доступа Wi-Fi на основе линейной засечки необходимо иметь три передатчика, что в помещениях можно наблюдать не всегда. Поэтому была разработана система, которая в качестве альтернативных/дополнительных точек использует станции сотовой сети (Рис. 1.9). 3 Идея QR-позиционирования по сути аналогична ориентированию на местности. Вместо базы данных используется человеческая память, а вместо QR-cсылок – характерные признаки ландшафта.

19 Рисунок 1.8 — Результаты навигации при использовании различных комбинаций гибридных систем[44] Рисунок 1.9 — Пример гибридных систем позиционирования. Wi-Fi и GSM[27] Кроме того системы включают в себя ГНСС, что позволяет осуществлять непрерывное позиционирование при переходе с открытых в закрытые пространства[45]. 1.5 Позиционирование в линейных сетях как подмножество задач позиционирования в помещениях В обобщенной задаче определения местоположения подразумевается, что объект мо жет находиться в любой точке пространства и характер его движения случайный. Однако в большинстве случаев он перемещается в пределах некоторого участка транспортной сети. Как отмечалось ранее, несмотря на высокую точность спутникового позиционирования, в городской среде, в горах, где есть препятствия для распространения радиосигнала, проис

20 ходит его переотражение, вследствие чего ошибка позиционирования увеличивается. В связи с этим в GPS-навигаторах учитывается тот факт, что вероятность нахождения транспорт ного средства на дороге, а не внутри здания или озера, выше. Для этого разрабатываются алгоритмы корреляции перемещения объекта с дорожной сетью, которые в англоязычной литературе объединены под термином «map matching» [46]. Идея «map mathing» может быть применена и в локальных системах позиционирова ния. В помещениях, под землей перемещение ограничено самим пространством. Поэтому для позиционирования в железнодорожных и автомобильных туннелях, в трубах или сети метро политена можно решать задачу только на тех участках, где перемещение объекта в принципе возможно. Так для обеспечения безопасности в процессе добычи полезных ископаемых людей по степенно заменяют автоматизированные системы. К примеру, решают задачу позициониро вания и навигации вагонеток при добыче угля. Шахта представляет собой линейную сеть с расположенными внутри нее мобильными станциями, по которой двигаются вагонетки. В [9] cтанции используют для GSM-позиционирования по методу локализации по шаблону. Авторы отмечают, что такой подход позволяет им добиваться необходимых точностей. Суще ствуют и аналогичные исследования, однако вместо GSM применяют инерциальные системы [13]. В [12] ставится задача позиционирования с субметровой точностью в другой линейной системе – подземном туннеле ЦЕРНа. Его размеры достаточно внушительные: восемь секций по 27км в длине, радиус каждой из которых составляет 2.2 м. Для создания дополнитель ной инфраструктуры высокоточного позиционирования(к примеру UWB) в системе такого размера требуются большие финансовые затраты. Поэтому GSM-позиционирование по шаб лону – наиболее оптимальное решение (Рис. 1.10). Их расположение позволяет использовать для этого не только базовые, но и соседние станции. В работе проводится анализ изменения силы сигнала в зависимости от расположения мобильной станции (Рис. 1.11) и условий из мерения. В результате была достигнута 80-метровая плановая точность. Авторы заключают, что добиться требуемых точностей, им поможет дополнительная калибровка шаблонов.

21 Рисунок 1.10 — GSM станции(отмечено стрелками) в туннеле ЦЕРНа[12] . Рисунок 1.11 — Пример шаблона, созданного на основе GSM в ЦЕРНе. Линиями показываются измерения. Цветом обозначены сигналы от разных базовых станций[12]. 1.5.1 Позиционирование в метрополитене Для навигации на станциях метрополитена ориентируются при помощи подвесных, на стенных и напольных указателей, а для прокладки маршрута по линиям соответствующие приложения. Существует программное обеспечение для прокладки непрерывного маршрута как на станциях, так и на линиях метро. Однако системы, которая позволяла бы опреде лять местоположение на этих маршрутах, на сегодняшний день не существует, есть только прототипы.

22 Один из примеров такой системы описан в работе [14], посвященной системе навигации в метрополитене на основе инерциальной системы. Разработчики создали первое в своем роде мобильное приложение, именуемое MetroNavigator, которое позволяет определять ме стоположение при помощи датчиков ИНС смартфона. Во время перемещения поезда метро политена, пользотваель такого приложения, отслеживающего характер движения поезда по данным акселерометров и гироскопов, видит на экране свое местоположение, время до при бытия в пункт назначения/следующей станции и просматривает наземные точки интереса (Рис. 1.12). Основная проблема при работе с MetroNavigator – накопление ошибок при продолжи тельных маршрутах, в связи с чем для калибровки ИНС в дальнейшем планируют исполь зовать точки Wi-Fi. Рисунок 1.12 — Визуализация режима навигации в MetroNavigator [14] На рынке мобильных приложений для навигации в метро также существует несколько примеров, в которых используются методы анализа соседства и линейной засечки [47],[48]. Однако в связи с тем, что одна GSM-станция охватывает сразу несколько станций метропо литена, точность таких систем остается невысокой.

23 Глава 2. Обоснование методики позиционирования в линейных сетях Как и в большинстве подходов к решению задачи позиционирования в помещениях с использованием алгоритма локализации по шаблону, процесс разработки системы делится на два блока: создание базы данных(офф-лайн фаза) и разработка алгоритма определения местоположения(он-лайн фаза). Применительно к поставленной задаче, в основу создания первого блока положен сле дующий принцип. Группа операторов перемещается по метрополитену и осуществляет сбор данных, используя мобильные устройства с необходимыми встроенными датчиками. По окон чании сбора, данные отправляют на сервер обработки, который в свою очередь проверяет их на предмет разного рода ошибок, осуществляет географическую привязку, уравнивает базу даных и выдает результат о количестве и качестве собранных данных в графическом и картографическом представлениях(Рис. 2.1). Операторы проверяют текущее состояние сети и принимают решение на предмет необходимости дальнейшего сбора данных. Рисунок 2.1 — Архитектура системы. Серверная часть Второй блок также состоит из нескольких этапов. Сначала выбирается и математически обосновывается некоторый набор возможных для применения алгоримов определения место

24 положения. Затем каждый из них обосновывается математически и реализуется программно. Сопоставление результатов определения местоположения разными алгоритмами позволяет провести апиорную оценку точности каждого, а также разработать наиболее подходящую версию прототипа уже на мобильной платформе. 2.1 Характеристика цифровой сотовой сети Исходная концепция разрабатываемой системы не предполагает затраты на покупку дополнительного оборудывания или модификации существующего. Этот факт служит обос нованием выбора в качестве базы сеть цифровой мобильной сотовой связи. Век цифровых технологий привел к широкому развитию этой сети, благодаря потребностям в телефонной связи, СМС, доступу в Интернет и пр[49]. В городских условиях, где концентрация або нентов высока, сотовая сеть развивается особенно активно: увеличивается количество стан ций, применяются новые стандарты передачи данных. В последние десятилетия пассажиры пользуются услугами операторов сотовой связи в метрополитене [50], что является хорошим подспорьем для использования сотовой сети как основы для создания системы позициониро вания в подземном транспорте. В силу исторического развития, традиционно мобильные сотовые сети классифицируют по поколениям: 1. 2G. Цифровая сотовая сеть, эксплуатируемая по стандарту GSM, с помощьюю кото рого предоставляются пакеты услуг телефонной связи и передачи СМС. Над GSM существуют дополнительные надстройки, такие как GPRS и EDGE, увеличивающие скорость обмена данными и предоставляющие возможность выхода в Интернет. На сегодняшний день остается самой распространенной сетью в мире[49]. 2. 3G. Широкополосная цифровая сотовая сеть, растространяемая по стандартам WSDMA, UMTS. Обеспечивает повышенную скорость передачи данных и выход в Интенет[49]. 3. 4G. Новейшая высокоскоростная(до 1Гбит/сек) широкополосная цифровая сотовая сеть распространяемая по стандартам LTS и WiMAX [49] Системы всех поколений цифровой сотовой сети основаны на схожем принципе постро ения и включают в себя три подсистемы[49]: – Мобильные станции. Каждая состоит из подвижного терминала(мобильный теле фон) и SIM-карты, которая отвечающет за идентификацию и регистрацию абонента в сотовой сети. При регистрации пользователя в сотовой сети ему присваивается 16-значный уникальный идентификатор абонента IMSI, содержащийся в SIM-карте. По IMSI можно определить страну(MCC) и оператора(MNC) регистрации. На сего дняшний день наиболее популярными операторами сотовой сети в России являются «МТС», «Мегафон», «Билайн» и «Теле2»[49].

25 – Подсистема базовых станций(БС). Отвечает за приемопередачу сигнала с мо бильным устройством и центром коммутации мобильной связи. БС обеспечивает по крытие сотовой сетью в пределах территории, ограниченной зоной обслуживания т.н. соты. Каждая БС имеет уникальный идентификатор соты (LAC) и идентификатор самой станции (CID). – Коммутационная подсистема(MSC). Центральный компонент системы, устанав ливающий исходящие вызовы, осуществляющий доставку СМС и тд.. Мобильная станция также обладает возможностью приема данных не только с базовой станции, но и единовременно с нескольких(соседних). Эта функция была реализована во избежании потери сигнала при перемещении пользователя за пределы зоны действия базовой станции. Таким образом, на мобильное устройство поставляется набор идентификаторов, определяющих страну, поколение сети, оператора, соту, базовую и соседние станции. Помимо этих параметров, на мобильном устройстве также может быть измерена сила принимаемого от базовой станции сигнала(RSS). 2.2 Позиционирование на основе сигнала цифровой сотовой сети Как отмечалось ранее, сила сигнала может быть использована для местоопределения способами линейной засечки и локализации по шаблону. В первом случае последотвательно находится зависимость расстояния от силы сигнала (формула 1.5), а затем, при достаточном наборе станций сотовой сети с известными координатами, местоположение вычисляется по формуле 1.2. Если же координаты базовых станций неизвестны, а координаты приемника известны, то при многократном получении идентичного набора параметров, можно опреде лить местоположение базовой станции. Определив таким образом координаты набора вышек, можно решать прямую задачу определения местоположения принимающего устройства, ис пользуя аналогичный подход[51]. Однако исходя из формулы линейной засечки, ее применение требует выполнения глав ного условия: наличие данных о местоположении вышек или возможность их получения в данных условиях. В описываемой задаче условие не выполняется, в связи с чем используется метод локализации по шаблону.

26 2.3 Локализация по шаблону 2.3.1 Общий приницп Пусть в некоторый интервал времени на исследуемой территории наблюдается 𝑚 ак тивных БС 𝑆. Тогда каждая 𝑖-я БС покрывает некоторую область и описывается набором данных: 𝑆𝑖 = [𝑟𝑠𝑠𝑖1 ,𝑟𝑠𝑠𝑖2 ,...,𝑟𝑠𝑠𝑖𝑛 ] (2.1) где: 𝑛 – количество ячеек в шаблоне 𝑆𝑖 – БС 𝑟𝑠𝑠𝑖𝑗 – RSS в точке 𝐿𝑖 , от станции 𝑆𝑖 Искомый шаблон есть не что иное, как совокупность данных от всех доступных БС. Визуально такой шаблон представляет собой карту-радиограмму 𝑅𝑀 и может быть описан как: 𝑅𝑀 = [𝑇1 ,𝑇2 ,...,𝑇𝑚 ] (2.2) где: 𝑇 – набор (𝑆𝑖 ,𝐿𝑖 ) Для создания базы шаблонов и составления карты необходимо: 1. Измерить силу сигнала на всей исследуемой территории 2. В соответствии со схемой сбора данных, осуществить географическую привязку каждой ячейки шаблона(𝐿𝑖 ) 3. «Нормализовать» данные: устранить случайные и систематические ошибки, прове сти уравнивание После завершения этапа подготовки данных, создается собственно алгоритм позициони рования, который заключается в идентификации измеренного параметра в подготовленной базе шаблонов и сопоставлении его с наиболее схожей точкой 𝑟𝑠𝑠𝑖+𝑘 , пространственное поло жение 𝐿𝑖+𝑘 которой и будет являться решением задачи. 2.3.2 Офф-лайн фаза. Географическая привязка На первом этапе создания шаблона необходимо выбрать способ привязки собранных данных. В исходной задачи имеется:

27 1. территория – линии метрополитена 2. объект – поезд метрополитана 3. регистрирующиее устройство – мобильная станция Исходная задача сводится к определению местоположения поезда, движущегося внутри линейной сети метрополитена, при помощи мобильного телефона, принимающего различные параметры от базовой и соседних вышек сотовой сети. Так как управлять движением поезда пользователь не может, то единственных выход – определенным образом вычислить характер его движения1 . Все поезда перемещаются по одной схеме: в пределах одной ветки с останов ками на каждой станции(за исключением ситуаций, когда та или иная станция закрыты по техническим причинам). Пассажир же заранее знает станцию прибытия и отправления, ко ординаты которых могут быть получены с карты. Кроме того, кинематика движения поезда на каждом перегоне условно может быть описана как последовательное равноускоренное, равномерное и равнозамедленное движение. ⎧ ⎪ ⎪ 𝑆𝑎1 + 𝑆𝑎2=0 + 𝑆𝑎3 = 𝑆 ⎪ ⎪ ⎪ ⎪ 𝑉 ·(𝑡1 −𝑡0 ) ⎪ ⎪ + 𝑉 · (𝑡2 − 𝑡1 ) + 𝑉 ·(𝑡32−𝑡2 ) = 𝑆 ⎪ ⎨ 2 𝑉 𝑆𝑡1 = Δ𝑡 (𝑡 − 𝑡0 )2 ⎪ ⎪ ⎪ ⎪ ⎪ 𝑆𝑡2 = 𝑉 · 𝑡 + 𝑆𝑡1 ⎪ ⎪ ⎪ ⎪ ⎩𝑆 = 𝑉 · (𝑡 − 𝑡 )2 + 𝑆 + 𝑉 · 𝑡 𝑡3 2 𝑡2 Δ𝑡3 (2.3) где: 𝑆𝑎1 ,𝑆𝑎2 ,𝑆𝑎3 – расстояния от станции отправления до текущего положения поезда на участках равноускоренного, равномерного и равнозамедленного движения. 𝑆 – длина перегона 𝑉 – скорость поезда после разгона 𝑡0 ,𝑡1 ,𝑡2 ,𝑡3 – моменты времени начала движения, максимального ускорения, начала оста новки и полной остановки. 𝑡 – текущий момент времени Решение системы уравнений позволит получить расстояние в любой момент времени от начала движения поезда. Все, что для этого необходимо – это знать моменты времени 𝑡 = 0..3. Для их регистрации понадобятся часы и фиксатор моментов времени, которые будут записываться в память устройства. Также, оператор, собирающий данные, должен сообщать регистрирующей системе станции отправления и прибытия. Получив набор расстояний, можно приступить к определению координат зафиксиро ванных точек. Необходимым условием является наличине геоданных по линейной сети и станциям метрополитена. Имея их, можно определить координаты зафиксированных точек способом линейной интерполяции: 1 Этот факт отличает передвижение в метрополитене от некоторых других упомянутых линейных систем: в шахтах движение вагонеток может контролироваться оператором

28 ⎧ ⎨𝐷𝑥 = 𝐷𝑥 + 𝐷𝑥𝑖+1 −𝐷𝑥𝑖 · (𝑥 − 𝑥 ) 𝑖 𝑖 𝑥𝑖+1 −𝑥𝑖 𝐷𝑦 −𝐷𝑦 𝑖 ⎩𝐷𝑦 = 𝐷𝑦 + 𝑖+1 · (𝑦 − 𝑦 ) 𝑖 𝑦𝑖+1 −𝑦𝑖 (2.4) 𝑖 где: 𝐷𝑥,𝐷𝑦 – расстояния по осям абсцисс и ординат от исходной станции до текущего ме стоположения 𝐷𝑥𝑖 ,𝐷𝑦𝑖 ,𝐷𝑥𝑖+1 ,𝐷𝑦𝑖+1 – расстояние по осям абсции и ординат от исходной станции до 𝑖,𝑖 + 1-го узла линии 𝑥𝑖 ,𝑦𝑖 ,𝑥𝑖 + 1,𝑦𝑖 + 1 – пространственные координаты 𝑖, 𝑖 + 1 узла линии 𝑥,𝑦 - искомые координаты текущего местоположения 2.3.3 Офф-лайн фаза. Нормализация данных После привязки данных можно приступать ко второму этапу. В нашем случае шабло ны представляют совокупность параметров, описывающих сигналы, которые принимаются со станций сотовой сети. Параметром, который наиболее точно характеризует изменение про странственного положения мобильной станции является сила сигнала. Как отмечалось, есть прямая зависимость от расстояния до сотовой станции. В процессе движения, расстояние, в свою очередь, зависит от времени. Следовательно, можно задать функцию силы сигнала от расстояния (Рис. 2.2). 𝑃𝑖 = 𝑓 (𝐷𝑖 ) (2.5) где: 𝑖 - уникальный идентификатор вида «MCC-MNC-LAC-CID» Такая функция и будет являться шаблоном для конкретной станции сотовой сети. Рисунок 2.2 — Общий вид шаблона

29 Увеличение количества измерений приводит к избыточности данных, а следовательно возникает задача уравнивания. При решении такого рода задач, на первом этапе учитывают систематические ошибки, а затем используют наиболее подходящий математический аппа рат для фильтрации случайных ошибок. Применительно к искомой задаче, систематические ошибки главным образом связаны с привязкой данных, вследствие чего наблюдается сдвиг по временной оси(Рис. 2.3). Рисунок 2.3 — Устранение ошибки за привязку данных Он устраняется при помощи последовательного сдвига сигналов относительно друг дру га. Сдвиг выполняется на основе поиска соответстувющих участков сигналов в разных из мерениях. Алгоритм поиска соответствий состоит в последовательном вычислении коэффи циентов корреляции между кривыми. Величина сдвига отсчитывается от точки, в которой наблюдается максимум среди всех вычисленных коэффциентах корреляции в каждой паре сравниваемых сигналов. После нахождения максимума, вносится поправка в соответствую щее измерение. Корреляция между сигналами прямо пропорциональна степени схожести между ними. Для ее увеличения сигналы предварительно сглаживаются. Иными словами, устраняются случайные ошибкив поведении сигнала, которые возникают вследствие особенностей его рас пространения во внешней среде, точности измерения на приемнике, экранирования и тд. (Рис 2.4).

30 Рисунок 2.4 — Устранение шума Для выделения общего тренда, шум «фильтруется». Для устранения характерных «всплесков» традиционно используют медианные фильтры. Их основная особенность - мини мальное влияния на исходно «гладкие» сигналы. Это позволяет использовать такие фильтры без риска потери данных для сигналов, обрабатываемых на разных датчиках. Используют алгоритмы сглаживания более высокой сложности, наиболее популярными их которых явля ются фильтр Калмана[29] и многочастичный фильтр[37]. Альтернативныым подходом к выделению общего тренда функции является аппрокси мация. В случае с цифровым сигналом, при аппроксимации подбирается полином, описываю щий ее наилучшим образом. Подбор полинома может быть произведен по методу наименьших квадратов, в результате чего его степень будет определяться минимальной суммой квадратов отклонений от аппроксимирующей функции (2.6). ⎧ ⎨𝐹 = 𝐴𝑥𝑛 + 𝐵𝑥𝑛−1 + ... + 𝑀 𝑥 + 𝐿 ⎩[𝑝𝑉 𝑉 ] = 𝑚𝑖𝑛 (2.6) где: 𝐹 – аппроксимируюащя функция 𝐴,𝐵..𝐿 – коэффициенты полинома 𝑥 – переменная [𝑝𝑉 𝑉 ] – сумма квадратов отклонения исходной функции от аппроксимирующей Однако изучив прицип по-которому происходит изменение сигнала во время движения поезда на линейных участках метрополитена, степень функции можно определить априори. Так как поезд движется прямолинейно и станции сотовой сети расположены относительно друг друга достаточно часто, то можно предположить, что во всех случаях поезд будет при ближаться к БС до тех пор, пока расстояние между ними не будет минимально, а затем отдаляться. Сила сигнала при этом будет последовательно возрастать, достигнет точки мак

31 симума, а затем будет убывать. Следовательно, в этом случае функция, описывающая сигнал имеет параболический вид, а степень полинома равна 2 (2.7). ⎧ ⎨𝐹 = 𝐴𝑥2 + 𝐵𝑥 + 𝐶 ⎩[𝑝𝑉 𝑉 ] = 𝑚𝑖𝑛 (2.7) Совокупность сглаженных сигналов от всех видимых БС на перегоне является шаб лоном, описывающим один линейный участок(перегон) сети метрополитена. Совокупность шаблонов будет составлять базу данных, являющейся основой для алгоритма позициониро вания. 2.3.4 Он-лайн фаза. Алгоритм позиционирования После того как база шаблонов готова, можно приступать к разработке алгоритма опре деления местоположения. Как отмечалось, его сущность сводится к сопоставлению участка данных, собранного в он-лайн режиме с базой шаблонов. Основная задача – установить мето дику, по которой будет происходить процесс идентификации. Для этого сначала необходимо определиться, какой конечный результат будет считаться удовлетворительным. В первом приближении точности позиционирования можно разбить на три класса, начиная с наиболее низкого: перегон, участок перегона и точка на перегоне. Помимо точности, качество алго ритма будет также определяться временными затратами. Точность и время на обработку в свою очередь зависят от: 1. Количества сот покрывающих перегон. 2. Количества БС, пойманных за промежуток времени 𝑡. 3. Характера сигнала от каждой БС. Шаг 1. Выбор всех собранных БС за промежуток веремени 𝑡1 из базы шаблонов. Возможны две ситуации: только один текущий перегон описывается уникальным набором из 𝑛 пойманных станций или таких перегонов 𝑚 штук. Первая ситуация дает возможность грубо определить текущее местоположение. В остальных случаях выборку необходимо сужать. Шаг 2. Определение характера кривых из наборов данных за промежутки времени 𝑡1 и 𝑡2 и его сравнение с базой данных шаблонов. Рассмотрим идеальный случай, при котором перегон был определен на предыдущем шаге. После однозначной идентификации перегона, необходимо определить на каком участке находится объект. Этого можно добиться на осно вании характера сигнала: – Возрастает: начало перегона2 – Практически не меняется: середина перегона – Убывает: конец перегона 2 С практической точки зрения вернее говорить не о перегоне, а об участке перегона, который описывается набором БС. Однако для простоты понимания алгоритма будем считать, что описывается целый перегон.

32 Основной проблемой определения характера сигнала на коротком промежутке време ни является шум. Для простоты эксперемента3 , использовался следующий подход. Вначале шум устраняется при помощи уже упомянутой аппроксимации. Затем, данные собранные за первые 𝑡1 сек., за вторые 𝑡2 сек. и за общее время 𝑡1 + 𝑡2 сек. сравнивались между собой. Если во всех случаях характер кривой совпал, значит он был определен верно. Если нет – сбор данных необходимо продолжать. При удачном раскладе участок на перегоне будет определен за 𝑡1 + 𝑡2 сек.. Однако существует неоднозначность, связанная с количеством активных БС: если пе регон покрывает лишь одна станция, то аналогичная ситуация возникнет и на параллельном ему. Это приводит к тому, что направление движения по такой схеме определить нельзя. По этому активных станций должно быть не менее двух – только в этом случае перегон будет определен одназначно. Шаг 3. Определение характерных точек. Наиболее удачные случаи: попадание в на бор данных точек пересечения сигналов с различных БС; появления новой БС; потеря сиг нала одной из БС. В этом случае можно определить текущее местоположение на перегоне с максимальной точностью. В более формальном виде, алгоритм позиционирования представлен на Рис. 2.5). 3 Применение более сложных фильтров будет рассмотрено в последующих работах.

33 Рисунок 2.5 — Он-лайн фаза позиционирования 2.4 Математическая оценка алгоритма позиционирования Для оценки точности позиционирования, алгоритмическая часть приложения сначала создается на станционарной машине. Оценка производится следующим образом. За исходные данные принимается таблица с географически привязанными сырыми данными. Затем проис ходит «разбиение» данных на основное и тестовое множества. Тестовое множество заменяет собой набор перегонов, полученных в он-лайн режиме. Из них случайным образом выбира ется один перегон и точка на нем, которая в сущности является текущим местоположением пользователя. Далее происходит имитация сбора данных: начиная от исходной точки, вы

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

35 Глава 3. Сбор и анализ данных Помимо того, что данные по метрополитену являются основой для позиционирования, они также уникальны в своем роде: аналогичных проектов, распространяемых под откры той лицензией, в России не было до сих пор. Это дает возможность использовать данные по сотовой сети, состоянию магнитного поля, зашумленности и тд. в других разработках. Более того, описанная технология сбора и сервис предварительной обработки данных да ют возможность собирать данные самостоятельно и получать географически корректные и привязанные данные. 3.1 Технология сбора данных Первый шаг – организация сбора данных. Для этого должны быть определены: – Аппаратная часть – Программное обеспечение – Технология сбора В силу принятой концепции «минимизации финансовых вложений», в качестве аппара туры использовались мобильные устройства(смартфоны) любых производителей. Современ ные смартфоны позволяют не только принимать данные с разных источников, но и предо ставляют возможность доступа к этим данным посредством API. Однако при использовании разных моделей, в первую очередь приходится учитывать особенности их операционной си стемы. Так, модели iPhone не предоставляют открытого доступа к собираемым данным. Некоторые модели Huawei(было отмечено на HUAWEI HN3-U00) не дают возможности по лучения RSS сотового сигнала. В телефонах компании Samsung нет информации о соседних вышках. Немаловажную роль играет и аппаратура, которая в зависимости от модели также будет давать разные результаты. Исследовав особенности смартфонов, было принято решение подбирать программное обеспечение для сбора и обработки данных под операционную систему Android. При выборе программного обеспечения учитывался ряд критериев, таких как возможности логгирования, удобного представления собираемых данных, расстановки дополнительных меток из тексто вого файла и пр.[52]. Так как программы, удовлетворяющей всем требуемым критериям не было найдено, компанией NextGIS было создан собственный продукт «Nextgis Logger». При ложение позволяет собирать данные с внешних источников, таких как ГНСС, GSM, bluetooth и др., а также с собственных датчиков: акселерометр, гироскоп, магнетометр и пр. Данные логгируются в двух режимах: непрерывный автоматический сбор с определенных пользова телем источников и дискретное внесение отметок, контролируемое пользователем. Общая технология сбора данных в метрополитене состоит в следующем:

36 1. Подготовка файла с марками(станциями метрополитена) и его загрузка в «Nextgis Logger». 2. Выбор необходимых источников данных для логгирования(Рис. 3.1). Рисунок 3.1 — Интерфейс «NextGISLogger». Выбор доступных устройств. 3. Инициализация логгера и расстановка меток в контрольных точках начала движе ния, максимального разгона, начала торможения и полной остановки(Рис. 3.2). Рисунок 3.2 — Интерфейс «NextGISLogger». Расстановка меток. 4. Проверка текущего состояния по интересующим параметрам(Рис. 3.3).

37 Рисунок 3.3 — Интерфейс «NextGISLogger». Текущие данные по сотовой сети. 5. Сохранение сессии по окончании сбора и отправка архивированных логов на сервер обработки Как видно, технология сбора данных достаточно простая и не требует специализиро ванных знаний и подготовки. Однако для создания полной и качественной базы данных по метрополитенам в разных городах для каждого поколения и оператора сотовой сети, силами одного-двух пользователей обойтись достаточно сложно. Возможное решение – краудсорсинг. Его применение может быть выгодно пользователям, для которых важно иметь качествен ную и актуальную базу данных. При таком подходе потребуется приложение, позволяющее проверять состояние базы данных. 3.2 Мониторинг состояния БД Для оперативного отслеживания покрытия GSM-данными по метрополинету пользо вателю важно знать, куда прокладывать маршрут и что представляют из себя собранные данные. Были ли допущены ошибки в процессе сбора данных? Если на некотором участке метки были расставлены некорректно, то на него необходимо вернуться и осуществить сбор заново. Обеспечен ли данными тот или иной участок перегона? В противном случае пози ционирование на нем невозможно. Корректны ли данные? Доверять данным можно только после проведения серии измерений. Поэтому для оператора важно знать количество проез дов по перегонам и насколько измерения из разных заездов коррелируют друг с другом.

38 Помимо оператора, который отвечает за сбор данных, информация важна в том числе и для администратора базы данных. Ответы на вопросы могут дать веб-карты, обеспечивающие удобный и повсеместный просмотр, доступ к которым осуществляется через URL. Для создания веб-карт применя ются веб-гис. В работе использовалась разработка компании Nextgis «NextGIS Web». Она позволяет добавлять слои векторных, растровых данных, подключать слои WMS, WFS. В ней также есть возможность соединения с базой данных, что позволяет отображать все из менения, происходящие в ней в он-лайн режиме (Рис. 3.4). Рисунок 3.4 — Интерфейс NextGIS Web. Данные по метрополитену Санкт-Петербурга.

39 Глава 4. Разработка программного обеспечения После того, как данные собраны, можно приступать к созданию программной части по их обработке. Она состоит из двух блоков: блок создания и обработки базы данных на серверной стороне и блок позиционирования, который тестируется на серверной и реализу ется на клиентской стороне. Первый блок включает создание базы данных, ее наполнение, нормализацию, графическую и картографическую визуализацию. Блок позиционирования состоит из разработки собственно модулей позиционирования и математической оценки их точности. 4.1 Создание и обработка базы шаблонов. После завершения работы по сбору данных, оператор отправляет их на сервер-храни лище. Он в свою очередь связан с сервером обоработки данных, который с заданной перио дичностью запрашивает информацию о поступлении новых данных. При появлении таковых инициализируется цепочка обработки. Центральное звено в ней – наполнение БД. Его осно ваная задача – привести сырые данные к географически привязанным шаблонам. Он состоит из нескольких блоков модулей. Блок 1. Интерпретация и валидация. Как упоминалось в предыдущей главе, сбор данных выполняется в двух режимах: логгирование с датчиков(автоматический режим) и расстановка меток(ручной режим). Метки – основа для географической привязки логов. Чтобы осуществить привязку, логи и метки необходимо сопоставить в единую структуру. Для этого используется уникальное поле временной отметки. Так как оба режима используют часы с одного устройства и работают синхронно, то можно его можно использовать для сортировки. (Рис. 4.1). Рисунок 4.1 — Разработка ПО. Сопоставление данных по временным отметкам

40 На перегонах и станциях используются разные способы позиционирования. Поэтому отсортированным данным необходимо присвоить состояние: остановка, переход или дви жение(см. главу 1). Для этого используется последовательность ввода меток на станци ях(Рис.4.2). Так как метки собираются в ручном режиме, возможны ошибки оператора. По этому здесь же путем сравнения со «словарями»(графы возможных переходов на станциях и перегонов на линиях), проверяется правильность последователности ввода меток. Рисунок 4.2 — Разработка ПО. Расстановка меток В процессе единовременного сбора данных с нескольких устройств метки могут расстав ляться на одном базовом устройстве. Для получения недостающих файлов, метки создаются на основе базовых с учетом временной поправки. Методика сбора данных в этом режиме подразумевает единовременную инициализацию сессий на всех устройствах(Рис. 4.3).

41 Рисунок 4.3 — Интерпретация и валидация исходных данных. Блок 2. Географическая привязка. На следующем этапе каждую запись пре добработанного лог-файла можно географически привязать. Для этого исходные данные разбиваются на перегоны. Для каждого перегона рассчитываются параметры движения по езда по формуле 2.3. Затем для каждой точки перегона находится время в пути, начиная с предыдущей станции. Полученное значение используется для привязки при помощи линей ной интерполяции (Формула 2.4). После завершения привязки каждая точка будет помещена в координатное пространство базовых слоев линий и станций метрополитена (Рис. 4.4).

42 Рисунок 4.4 — Привязка точек на перегоне Блок 3. Аппроксимация. Согласно принципам анализа данных, их форма пред ставления должна быть не только текстовая, но и графическая. Она позволяет увидеть осо бенности исследуемого явления и выявить зависимости, трудно воспринимаемые при анализе текста. Применительно к искомой задаче, необходимо проанализировать поведение сигнала на линейных участках сети метрополитена. В качестве такого участка берется перегон между двумя соседними станицями (Рис. 4.5).

43 Рисунок 4.5 — Поведение сотовых сигналов на тестовом перегоне. Геопривязанные данные. На Рис. 4.5 показан перегон «Сретенский Бульвар – Курская» Московского метрополи тена. Сотовый сигнал передается от вышек сотовой сети 2G оператора «Мегафон». Данные собирались с двух устройств единовременно несколькими измерениями: в левой колонке пред ставлены графики с мобильного телефона модели «Samsung», в правой – «Sony». На перегоне проведено три заезда(три измерения): каждый заезд – строка на графике. Цветом выделены сигналы, получаемые с разных вышек. Сплошная структура линий показывает, что сигнал принимается с базовой станции, а пунктирная – с соседней. Ось абсцисс показывает рассто яние от станции отправления, а ось ординат – силу сигнала в дб. Из графика видно, что: – Общее поведение сигнала не меняется со временем, что можно просделить сравнивая сигналы из разных измерений. Наблюдая подобную картину на выборке из других перегонов, можно отметить, что данные, собранные в определенный момент времени будут актуальны и в будущем(с учетом особенностей, указанных в главе 1). – Общее поведение сигнала не меняется в зависимости от модели телефона. С одной стороны общая тенденция остается неизменной. Это позволяет использовать

44 разные устройства для наполнения базы данных измерениями. Однако стоит отме тить, что у разных моделей различная степень фильтрации шума. На данном графике четко видно, что «зашумленность» сигнала у модели Sony значительно вы ше, чем у модели Samsung. – Модель Samsung не предоставляет данных по соседним вышкам. В один и тот же момент времени Samsung ловит сигнал только с базовой станции, тогда как Sony в том числе и с соседней. Так как с увеличением количества вышек, сигнал от которых принимается в определенный момент времени, увиличивается информатив ность создаваемого шаблона, этот факт будет накладывать определенные ограниче ния для работы алгоритма позиционирования на модели Samsung. – Существует сдвиг по оси абсцисс, вызванный ошибкой привязки данных. В основном сдвиг возникает вследствие принятой аппроксимации движения поезда. Для уменьшения ошибки при уравнивании, сдвиг необходимо устранить. Перечисленные особенности послужили основой для разработки алгоритма уравнива ния географически привязанных данных. В его задачи входит: – Минимизировать влияние зашумленности сигнала. Так как степень зашум ленности зависит от модели телефона, то алгоритм минимизации должен работать таким образом, чтобы «зашумленные» сигналы фильтровать с высокой степенью, при этом не оказывая сильного влияния на визуально «гладкие» сигналы. В каче стве такого алгоритма используется медианный фильтр. – Устранить ошибки привязки данных. После применения медианного фильтра схожесть сигналов с разных устройств увеличивается. Это позволяет сравнивать участки сигналов для нахождения ошибки сдвига(Рис. 4.6).

45 Рисунок 4.6 — Алгоритм устранения ошибки за привязку данных – Усреднить сигналы. Поведение кривых в процессе уравнивания можно также проследить графически. Устранение ошибки привязки происходит в два этапа. На первом этапе находятся соответ ствия в рамках одного заезда (Рис. 4.7).

46 Рисунок 4.7 — Поведение сотовых сигналов на тестовом перегоне. Сдвиг сигналов по устройствам. На Рис. 4.7 каждая колонка – сигнал принимаемый от конкретной станции сотовой сети. Цветом показаны устройства, принимающие сигнал, в строках, по аналогии с Рис. 4.5 показаны заезды. Видно, что для сигналов, принятых на разных устройствах взаимное соответствие было найдено. Второй этап – устранение ошибок в рамках заездов(Рис. 4.8).

47 Рисунок 4.8 — Поведение сотовых сигналов на тестовом перегоне. Сдвиг сигналов по заездам. Каждая строка графика – станця сотовой сети. Цветом обозначено сочетание "пользо ватель–заезд". Из графика видно общее поведение сигнала для каждой станции. Также наблюдаются его локальные флуктуации, которые устраняются на последнем шаге фильтрации сигнала в соответствии с формулой 2.7.

48 Рисунок 4.9 — Поведение сотовых сигналов на тестовом перегоне. Сглаженные сигналы. После завершения каждого этапа нормализации, результат сохраняется в базу данных. В структуру базы данных входят: – Данные по метрополитену. Это геоданные, включающие линейный слой линий и то чечный слой станций метрополитена1 , а также графы возможных перегонов и пере ходов на узловых станциях. – Исходные данные и состояние их обработки. – Предобработанные данные – Привязанные данные – Уравнивненные данные – Анализ уравненных данных – Представления для визуализации выходных геоданных (Рис. 4.10). 1 Данные подготовлены компанией NextGIS

49 Рисунок 4.10 — Структура базы данных 4.2 Программное обеспечение для обработки данных В качестве языка программирования для ядра системы был выбран Python. Обладая обширным набором открытых библиотек по анализу данных(numpy,scipy,pandas), работе с геоданными(shapely), интеграцией с базой данных(sqlalchemy,psycopg2) язык позволяет эко номить временя, требуемое на разработку стандартных функций.

50 База шаблонов создавалась при помощи СУБД PostgreSQL. Причина такого выбора – ее интеграция с расширением для хранения в базе и географических данных их обра ботки PostGIS. Несомненнымм преимуществами этой СУБД также является ее производи тельность, а также поддержка объектно-ориентированного и реляционного подхода к базам данных. Для графической визуализации использовался язык программирования R. Будучи са мым востребованным инструментом в анализе данных, R обладает мощным набором стати стических функций, использование которых требует грамотного инструмента по визуализа ции данных. Таким является пакет ggplot2, который и послужил основой для построения графиков. В связи с необходимостью публикации карт в Интернете, было принято решение исполь зовать веб-гис NextGisWeb QGIS. Помимо интеграции с базой данных, NextGISWeb QGIS позволяет загружать картографические стили, подготовленные в настольной ГИС QGIS. Все данные опубликованы в открытом доступе, программное обеспечение имеет откры тый исходный код, а проект распространяется под открытой лицензией GNU GPL v2. 4.3 Мобильное приложение для позиционирования Как упоминалось ранее, установка приложения возможна только на смартфоны с опе рационной системой «Android». После завершения установки на пользовательском телефоне, можно определять его местоположение. На текущем этапе отслеживание может происходить только на линейных участках сети: на станциях метрополитена местоположение будет опре деляться точкой в масштабе всей станции. В базовом варианте, интерфейс приложения достаточно простой и включает в себя схему метро, кнопку инициализации и индикатор точности позиционирования(Рис. 4.11).

51 Рисунок 4.11 — Интерфейс NextGIS Metrocell После нажатия кнопки инициализации начинается процесс сбора данных сотовой сети. После того, как получен первый сегмент данных длиной в 𝑡 сек., начинается поиск соотству ющего участка данных в базе шаблонов. По прошествии следующих 𝑡 секунд происходит корреляция сигналов, результат которой позволяет оценить местоположение не только огра ничиваясь каким-либо перегоном, но и участком на нем. В зависимости от промежуточного результата, каждые 𝑡 секунд индикатор точности позиционирования обновляется. Если пе регон не определен, то цвет остается красным, если определен – оранжевым. Как только определен участок перегона, цвет меняется на желтый. И, наконец, когда определена точка на перегоне индикатор принимает зеленый цвет. Рисунок 4.12 — Он-лайн фаза позиционирования

52 Заключение В ходе представленной работы был разработан прототип приложения, который поз воляет определять местоположение в линейной сети по данным цифровой сотовой сети на примере метрополитена. Качественным усовершенствованием существующих аналогичных решений является использование изменения характера сигнала в процессе движения объек та. Для решения задачи был выбран наиболее устойчивый к влиянию случайных ошибок метод локализации по шаблону. Результатами работы являются: – Создана база данных по сотовым сетям метрополитенов Москвы и Санкт-Петербурга – Составлена серия веб-карт для мониторинга текущего покрытия данными сотовой сети и оценки их качества – Разработан прототип алгоритма позиционирования и проведена математическая оценка его точности Дальнейшая работа включает: – Cоздание мобильного приложения – Практическую оценку качества алгоритма позиционирования – Использование инерциальных систем для идентификации остановок поезда – Упрощение методики сбора данных Мобильное приложения для позиционирования в метрополитене в первую очередь мо жет использоваться как дополнение к сервисам позиционирования на поверхности для непре рывной навигации. Отслеживание текущего местоположения – актуальная задача при пере мещении в городах со сложной инфраструктурой городского транспорта. Он-лайн режим позволит жителям городов оценить временные затраты до прибытия в пункт назначения, а туристам найти интересующие достопримечательности, рестораны, мероприятия и тд. Полученные в ходе работы результаты позволяют рассчитывать на использование опи санных подходов не только в метрополитене, но и в линейных сетях со схожей архитектурой.

53 Список сокращений и условных обозначений ГНСС – Глобальная Навигационная Спутниковая Система GSM – Global System for Mobile Communications (Глобальная система для мобильного общения) ИНС – Инерциальная Навигационная Система LPS – Local Positioning System (Локальная Система Позиционирования) POA – Phase Of Arrival (Фаза приходящего сигнала) TOA – Time Of Arrival (Время приходящего сигнала) LAN – Local Area Network (Локальная беспроводная сеть) WAN – Wide Area Network (Глобальая беспроводная сеть) CPS – Cellular positioning system (Система позиционирования по станциям сотовой сети) AP – Access Point (Точка доступа) PDR – Pedestrian Dead Reckoning (Навигационное счисление пути) MCC – Mobile Country Code (Мобильный код страны) MNC – Mobile Network Code (Мобильный код сети) LAC – Local Area Code (Код соты) CID – Cellular Identificator (Идентификатор станции сотовой сети)

54 Список литературы 1. Карлащук В. И., Карлащук С. В. Спутниковая навигация. Методы и средства. — М. : СОЛОН-Пресс, 2006. — 176 с. 2. Капралов Е. Г., Кошкарев А. В., С. Т. В. Геоинформатика (Классический университет ский учебник). — М. : ИЦ Академия, 2005. — 480 с. 3. Lin H., Batty M. Виртуальные географические среды / под ред. В. C. Тикунов. — Крас нодар : Краснодарская панорама досуга, 2015. — 352 с. 4. Alshami I. H., Ahmad N. A., Sahibuddin S. Dynamic WLAN Fingerprinting RadioMap for Adapted Indoor Positioning Model // Springer International Publishing Switzerland. — 2015. 5. Казаков Э. Э. Краудсорсинг геоданных в России в мире // Сборник материалов между народной научно-практической конференции. Геодезия, Картография, Геоинформатика и Кадастры. От идеи до внедрения. Т. 4 / под ред. О. А. Лазебник. — Санкт-Петербург ский Государственный Университет. Спб. : Политехника, нояб. 2015. — С. 229—233. 6. Jardak N., Samama N. Indoor Positioning Based on GPS-Repeaters: Performance Enhancement using an Open Code Loop Architecture // IEEE Transactions on Aerospace and Electronic Systems. — 2009. — Янв. — Т. 45, № 1. — С. 347—359. 7. Waqar W., Chen Y., Vardy A. Smartphone positioning in sparse Wi-Fi environments // Computer Communications. — 2016. — Т. 73, Part A. — С. 108—117. 8. A Real-Time Location-Based Services System Using WiFi Fingerprinting Algorithm for Safety Risk Assessment of Workers in Tunnels / P. Lin [и др.] // Mathematical Problems in Engineering. — Beijing, 2014. — С. 1—10. 9. Positioning algorithms of underground coal mines based on virtual Radio-map and Markov chain / L. Cui L. and Li, J. He, M. Shi // Journal of PLA University of Science and Technology(Natural Science Edition). — 2014. 10. Щёкотов М. С., Кашевник А. М. Сравнительный анализ систем позиционирования смартфонов в помещениях // Труды СПИИРАН. — Спб., 2012. — С. 459—471. 11. Pritt N. Indoor location with Wi-Fi fingerprinting // 2013 IEEE Applied Imagery Pattern Recognition Workshop (AIPR). — Окт. 2013. — С. 1—8. 12. Performance and limits of KNN-based positioning methods for GSM networks over leaky feeder in underground tunnels / F. Pereira [и др.] // Journal of Location Based Services. — 2012. — Т. 6, № 2. — С. 117—133. 13. Schiffbauer W. H. Navigation and control of continuous mining systems for coal mining // IEEE. — 1996.

55 14. Stockx T., Hecht B., Schöning J. SubwayPS: Towards Smartphone Positioning in Underground Public Transportation Systems // Proceedings of the 22Nd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. — Dallas, Texas : ACM, 2014. — С. 93—102. — (SIGSPATIAL ’14). 15. Генике А. А., Побединский Г. Г. Глобальные спутниковые системы определения место положения и их применение в геодезии. — М. : Картгеоцентр, 2004. — 355 с. 16. ГОСТ Р 53611-2009. Глобальная навигационная спутниковая система. Методы и техно логии выполнения землемерных и землеустроительных работ. Общие технические тре бования. — М. : Стандартинформ, 2012. — 12 с. 17. Курошев Г. Д. Космическая геодезия и глобальные системы позиционирования. — СПб. : Изд-во С.-Петерб. ун-та., 2011. — 184 с. 18. Kolodziej K. W., Hjelm J. Local Positioning Systems: LBS Applications and Services. — CRC Press, 2006. — 488 pp. 19. Bajers F. Inertial Navigation System. — Denmark, Aalborg University, 2008. — 122 pp. 20. Назаров А. С. Фотограмметрия. — Минск : ТетраСистемс, 2006. — 400 с. 21. Курошев Г. Д. Геодезия и география. — СПб : Изд-во С.-Петерб. ун-та., 1999. — С. 372. 22. Official U.S. Government information about the Global Positioning System (GPS) and related topics. GPS Accuracy. — URL: http://www.gps.gov/systems/gps/performance/accuracy/. 23. Информационно-аналитический центр координатно-временного и навигационного обес печения. История развития ГЛОНАСС. — URL: https://www.glonass-iac.ru/guide/. 24. European Space Agency. What is Galileo? — URL: http://www.esa.int/Our_Activities/ Navigation/The_future_-_Galileo/What_is_Galileo. 25. Beidou Navigation Satellite System. Development Process. — URL: http://www.beidou.gov. cn/2012/12/14/20121214e14a946961514cce98ab04d876258343.html. 26. Namiot D. On indoor Positioning // International Journal of Open Information Technologies. — 2015. — Т. 3. 27. Mahamud M. A., Chowdhury M. Indoor Location System with Wi-Fi and Alternative Cellular Network Signal // International Journal of Multimedia and Ubiquitous Engineering. — 2015. — Т. 10, № 3. — С. 59—70. 28. Namiot D. Context-Aware Browsing – A Practical Approach // 2012 Sixth International Conference on Next Generation Mobile Applications, Services and Technologies. — Сент. 2012. — С. 18—23. 29. Pahlavan K., Li X., Makela J. P. Indoor geolocation science and technology // IEEE Communications Magazine. — 2002. — Февр. — Т. 40, № 2. — С. 112—118. 30. Рутледж Д. Энциклопедия практической электроники. — М. : ДМК-Пресс, 2002. — 528 с.

56 31. Using Wi-Fi/magnetometers for indoor location and personal navigation / Y. Li [и др.] //. — 2015. 32. GSM RSSI-based positioning using extended Kalman filter for training artificial neural networks / K. Anne [и др.] //. Т. 60. — 2004. — С. 4141—4145. 33. Бабаев iBeacon: Мифы и реальность. — 2016. — URL: https://habrahabr.ru/post/278689/. 34. An ibeacon primer for indoor localization / P. Martin [и др.] //. — 2014. — С. 190—191. 35. Holm S. Ultrasound positioning based on time-of-flight and signal strength //. — 2012. 36. A Reliable and accurate indoor localization method using phone inertial sensors / F. Li [и др.] //. — 2012. — С. 421—430. 37. Harle R. A survey of indoor inertial positioning systems for pedestrians // IEEE Communications Surveys and Tutorials. — 2013. — Т. 15, № 3. — С. 1281—1293. 38. Haas H. Wireless data from every light bulb. — URL: http://www.ted.com/talks/harald_ haas_wireless_data_from_every_light_bulb. 39. Sharma R. R., Raunak, Sanganal A. Li-Fi Technology. Transmission of data through light. 40. Yoshino M., Haruyama S., Nakagawa M. High-accuracy positioning system using visible LED lights and image sensor //. — 2008. — С. 439—442. 41. Indoor three-dimensional location estimation based on LED visible light communication / S.-H. Yang [и др.] // Electronics Letters. — 2013. — Т. 49, № 1. — С. 54—56. 42. Indoor positioning system using geomagnetic anomalies for smartphones / S.-E. Kim [и др.] //. — 2012. 43. Намиот Д. Е. Использование двумерных штрих-кодов для создания системы позицио нирования и навигации в помещении // Прикладная информатика. — 2013. — С. 31— 39. 44. A Hybrid WiFi Magnetic Matching PDR Approach for Indoor navigation with smartphone / Y. Li [и др.] // IEEE COMMUNICATIONS LETTERS. — 2016. — Т. 20, № 1. — С. 169— 172. 45. Fritsche C., Klein A., Wurtz D. Hybrid GPS/GSM Localization of Mobile Terminals using the Extended Kalman Filter // IEEE. — 2009. 46. Jagadeesh G. R., Srikanthan T., Zhang X. D. A Map Matching Method for GPS Based Real-Time Vehicle Location // THE JOURNAL OF NAVIGATION. — 2004. — С. 429— 440. 47. Яндекс Определение местоположения без GPS: как устроен Яндекс.Локатор. — URL: https://habrahabr.ru/company/yandex/blog/162955/. 48. Lozenko D. V. Карта Метро. — URL: https://play.google.com/store/apps/details?id=com. blogspot.formyandroid.underground&hl=ru.

57 49. Берлин A. Н. Сотовые системы связи: Учебное пособие. — М. : Интернет-Университет Информационных Технологий; БИНОМ. Лабо- ратория знаний, 2009. — 360 с. 50. Министерство связи и массовых коммуникаций Российской Федерации. Мониторинг состояния и динамики развития инфотелекоммуникационной структуры. — М., 2015. 51. Promwad Как определить местоположение по сетям сотовой связи (Cell ID). — 2010. — URL: http://habrahabr.ru/company/promwad/blog/223635/. 52. Петряков С. Сбор данных из внешних источников и внутренних сенсоров с помощью NextGIS Logger. — 2015. — URL: http://gis-lab.info/qa/nextgis-logger.html.

58 Приложение А Листинги программного кода Листинг А.1 Пример функции привязки данных на Python def g e o _ r e f ( s e l f ) : """ E x t r a c t p a r s e d l o g s from DB, i t e r a t e t h r o u g h them ( and by d e v i c e ) , s p l i t d a t a on 5 groups , which c o n t a i n s 1 user , 1 segment , and 1 movement t y p e ( s t o p , move or i n t e r c h a n g e s ) , and i n i t i a l i z e t h e p r o c e s s i n g a l g o r i t h m o f each group . Morover a t t h e end o f t h f u n c t i o n there i s a v i s u a l i z i n g of georeferenced r e s u l t ( currently only f o r c e l l s , not f o r a n o t h e r d e v i c e s such as a c c e l e r o m e t r , g y r o s c o p e and e t c ) : return : 10 """ print ’ G e o r e f e r e n c e r s t a r t s ! ’ print 30* "−" # use s q l a l c h e m y s e s s i o n s t o f a s t e r commiting o f c h a n g e s 15 # l o o k a t h t t p s : / / ru . w i k i b o o k s . o r g / w i k i /SQLAlchemy m e t r o c e l l _ e n g i n e = c r e a t e _ e n g i n e ( " p o s t g r e s q l : / / "+ s e l f . server_conn [ ’ u s e r ’ ]+ ’ : ’+ u t i l i t i e s . if_none_to_str ( s e l f . server_conn [ ’ password ’ ] )+ ’@ ’+ s e l f . server_conn [ ’ h o s t ’ ]+ ’ : ’+ u t i l i t i e s . if_none_to_str ( s e l f . server_conn [ ’ p o s t g r e s _ p o r t ’ ] )+ ’ / ’ + s e l f . server_conn [ ’ dbname ’ ] ) M e t r o c e l l _ s e s s i o n = s e s s i o n m a k e r ( bind = m e t r o c e l l _ e n g i n e ) s e l f . session = Metrocell_session () # i t e r a t e through devices 20 f o r d e v i c e in [ ’ c e l l ’ ] : Parsed_data . __table__ = ’ parsed_ ’+d e v i c e

59 try : 25 30 35 40 45 50 parsed_df = u t i l i t i e s . get_pd_df_from_sql ( s e l f . server_conn , s e l f . server_conn [ ’ t a b l e s ’ ] [ ’ parsed_ ’ + d e v i c e ] ) except : pass parsed_zip_df = parsed_df [ parsed_df [ ’ z i p _ i d ’ ] . i s i n ( s e l f . zip_ids ) ] _parsed_zip_df = parsed_zip_df . s o r t _ v a l u e s ( by = [ ’ TimeStamp ’ ]) _parsed_zip_df = _parsed_zip_df [ parsed_zip_df [ ’ r a t i o ’ ] . i s n u l l () ] s e g m e n t _ s l i c e s = _parsed_zip_df . groupby ( [ ’ id_from ’ , ’ id_to ’ , ’ User ’ , ’ move_type ’ ] ) s e l f . proc_len = len ( parsed_zip_df ) s e l f . step = 0 # i t e r a t e thtough the groups f o r ( id_from , id_to , User , move_type ) , segment_df in segment_slices : s e l f . id_from = id_from s e l f . id_to = id_to s e l f . device = device s e l f . key_rows = segment_df [ segment_df [ ’ s t a t i o n _ i d ’ ] . notnull () ] _segment_df = s e l f . s e s s i o n . query ( Parsed_data ) \ . f i l t e r _ b y ( id_from = id_from , id_to=id_to , User = User , move_type = move_type , r a t i o = None ) \ . order_by ( Parsed_data . TimeStamp . a s c ( ) ) i f move_type == ’ i n t e r ’ : s e l f . s t e p+=1 #t o d o : no a l g o r i t h m t o r e f e r e n c e i n t e r c h a n g e s ! continue segment_graph = s t r ( id_from ) . z f i l l ( 3 ) + ’− ’ + s t r ( id_to ) . z f i l l (3) try : s e l f . segment_georef ( segment_graph , _segment_df , s e l f . extractor ) except : s e l f . s t e p+=1 print s y s . e x c _ i n f o ( ) [ 0 ] , s y s . e x c _ i n f o ( ) [ 1 ] continue i f move_type == ’ move ’ : u t i l i t i e s . p lo t _ si g na l _ po w er ( s e l f . server_conn , ’ g e o r e f e r e n c i n g _ r a w ’ , id_from , id_to , s e l f . c i t y ) 55 f o r z_id in s e l f . z i p _ i d s : u t i l i t i e s . update_postgre_rows ( s e l f . server_conn , s e l f . server_conn [ ’ t a b l e s ’ ] [ ’ p r o c e s s i n g _ s t a t u s ’ ] , z_id , ’ g e o r e f e r e n c e d ’ , True , i n d e x _ c o l = ’ z i p _ i d ’ )

60 Листинг А.2 Пример функции визуализации данных на R e o r e f e r e n c i n g _ a v e r a g e d <− f u n c t i o n ( host , port , u s e r , password , dbname , plot_base , id_from , id_to , c i t y ) { #g e o r e f e r e n c i n g f u n c t i o n tablename <− " averaged_cell_meta " 5 drv<− dbDri ver ( " PostgreSQL " ) p l o t _ f o l d e r = p a s t e ( plot_base , c i t y , ’ a v e r a g e d _ c e l l ’ , s e p= ’ / ’ ) con<− dbConnect ( drv , dbname = dbname , h o s t = host , p o r t = port , u s e r = u s e r , password = password ) i f ( d b E x i s t s T a b l e ( con , tablename ) ) { seg_df <− dbGetQuery ( con , p a s t e ( "SELECT * FROM " , tablename , " WHERE 10 city = ’" , city , " ’ AND segment_id =’" , p a s t e ( id_from , id_to , s e p= ’− ’ ) , "’ ", sep = ’ ’ )) 15 seg_df = seg_df [ ( s e g _ d f $ r a t i o >0)&( s e g _ d f $ r a t i o <1) , ] s e g _ d f $ l a c c i d = p a s t e ( seg_df$LAC , seg_df$CID , s e p = ’_ ’ ) GENs <− unique ( seg_df$NetworkGen ) fo r (GEN in GENs) { p l o t _ f o l d e r _ g e n = p a s t e ( p l o t _ f o l d e r ,GEN, s e p= ’ / ’ ) i f ( ! dir . e x i s t s ( p l o t _ f o l d e r _ g e n ) ) dir . c r e a t e ( p l o t _ f o l d e r _ g e n ) 20 gen_df = seg_df [ seg_df$NetworkGen == GEN, ] MNCs = unique ( gen_df$MNC ) f o r (MNC in MNCs) { plot_folder_mnc = p a s t e ( p l o t _ f o l d e r _ g e n ,MNC, s e p= ’ / ’ ) i f ( ! dir . e x i s t s ( plot_folder_mnc ) ) dir . c r e a t e ( plot_folder_mnc ) mnc_df = gen_df [ gen_df$MNC == MNC, ] power<−g g p l o t ( mnc_df , a e s ( x=r a t i o , y=Power , c o l o u r = l a c c i d ) )+ g g t i t l e ( p a s t e ( " Segment " , seg_df$segment [ 1 ] , s e p= ’ : ’ ) )+theme ( p l o t . t i t l e = element_text ( f a c e = ’ b o l d ’ ) ) power2 = power + geom_line ( s i z e =1.5) plot_name = p a s t e ( id_from , ’_ ’ , id_to , " . png" , s e p = ’ ’ ) g g s a v e ( f i l e n a m e = plot_name , p l o t = power2 , path = plot_folder_mnc , width = 4 0 0 , h e i g h t = 4 0 0 , u n i t s = ’mm’ ) #saved_ref_path<−plot_folder_mnc + ’ / ’ + plot_name push_to_db ( con , plot_name , id_from , id_to , c i t y ,MNC) } 25 30 35 } } else { print ( " There i s no such t a b l e ! " ) } 40 }

61 Приложение Б Картографическая визуализация состояния сотовой сети метрополитенов Москвы и Санкт-Петербурга в веб-гис NextGisWeb Рисунок Б.1 — Центр Москвы. MTS 2G и 3G.

62 Рисунок Б.2 — Восток Санкт-Петербурга. Мегафон 2G.

Рецензии:

Авторизуйтесь, чтобы добавить рецензию

- у работы пока нет рецензий -

Отзывы:

Авторизуйтесь, чтобы оставить отзыв