Математические методы и модели систем определения местоположения мобильных объектов внутри зданий и сооружений тема диссертации и автореферата по ВАК РФ 05.13.18, доктор наук Воронов Роман Владимирович

• Воронов Роман Владимирович
• доктор наук
• 2017

Оглавление диссертации доктор наук Воронов Роман Владимирович

Введение

1 Задачи определения местоположения мобильных объектов в ограниченных пространствах, обзор наиболее распространенных моделей и методов

1.1 Существующие методы определения местоположения мобильных объектов в ограниченных пространствах

1.2 Обзор и классификация алгоритмов внутреннего позиционирования на основе обработки сигналов точек доступа

1.3 Применение дискретного байесовского фильтра к задаче определения местоположения мобильных объектов

1.4 Обзор алгоритмов определения мест размещения точек доступа

1.5 Использование датчиков атмосферного давления в систе

мах определения местоположения

1.6 Постановка задач исследования

1.7 Выводы

2 Математические модели и методы решения задачи оптимального размещения датчиков системы определения местоположения

2.1 Математическая модель размещения датчиков системы определения местоположения

2.2 Минимизация математического ожидания расстояния между фактическим расположением объекта и наиболее вероятной зоной, выбранной алгоритмом определения местоположения

2.3 Минимизация математического ожидания расстояния между центром зоны фактического расположения объекта и средневзвешенной точкой

2.4 Задача определения местоположения на плоскости

2.5 Модель определения местоположения на неориентированном графе

2.6 Задача определения местоположения на семействе гиперграфов

2.7 Минимизация суммарной энтропии уровней сигналов во всех зонах помещения

2.8 Обобщение задач оптимальго размещения точек доступа в системе определения местоположения

2.9 Доказательство МР ТрудНОСТИ ПОСТАВЛЕННЫХ ЗсЬД^сЬЧ^ 011Ти мизации

2.10 Алгоритмы определения мест размещения точек доступа

2.11 Выводы

Исследование и особенности применения задачи определения метрической размерности графа

3.1 Задача метрической размерности графа

3.2 Вероятностное обобщение задачи метрической размерности графа

3.3 Выводы

Методы калибровки систем определения местоположения и определения местоположения мобильного объекта

4.1 Задача автоматического построения карт уровня сигнала точек доступа системы определения местоположения

4.2 Автоматическая построение карт уровней сигналов при неизвестной дисперсии

4.3 Задача привязки трека объекта к плану помещения

4.4 Использование модели движения объектов при определении местоположения объектов в сооружениях, представляемых в виде графа

4.5 Использование инерциального измерительного модуля при определении местоположения объектов в сооружениях, представляемых в виде графа

4.6 Применение датчиков атмосферного давления для отт^вни вания высоты мобильного объекта

4.7 Выводы

5 Имитационное моделирование системы определения местоположения объектов в помещении

5.1 Описание требований к программному комплексу

5.2 Тестовые испытания алгоритмов расстановки точек доступа и построения карты уровня сигналов

5.3 Выводы

Заключение

А Пример расчетов разрешающих множеств вершин графа258

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

плана здания

Литература

Введение

Актуальность темы исследования

Задача определения местоположения мобильных объектов в зданиях и сооружениях, где невозможно использовать спутниковые системы навигации, актуальна для многих практически важных приложений бытовой и медицинской сферы, области промышленности, транспорта, сферы услуг и образования, общественной безопасности. Для примера можно назвать следующие задачи: наблюдение за детьми в детских учреждениях; поиск и отслеживание перемещений товаров на складе магазина; определение местоположения медицинского оборудования, персонала и престарелых пациентов в больнице; обнаружение шахтеров в шахтах в случаях чрезвычайных ситуаций; контроль местоположения группы сотрудников силовых структур при выполнение спецопераций внутри зданий; слежение за пожарными внутри горящего здания; определение местоположения служебных собак, ищущих взрывчатку в здании; обнаружение помеченного инструмента на большом предприятии и т. д. Определение местоположения мобильного объекта требуется в задачах эвакуации людей из помещений, маршрутизации робота в здании, построения транспортных путей, трансляции медиа-потоков в Wi-Fi сетях [25, 2б, 44, 47, 58, 89]. Например, одной из причин изменения пропускной способности сетевого соединения пользователей в сетях Wi-Fi является изменения положения пользователя в пространстве относительно базовой станции. Информация о положении пользователей в пространстве относительно базовой станции, количестве активных пользователей в радиусе действия базовой станции, является полезной и может учитываться при проведении трансляций медиа-потоков и выборе скоростей передачи информации [58].

Объектом исследования служат системы определения местоположения мобильных (передвигающихся) объектов внутри закрытых пространств - зданий и сооружений. Согласно ГОСТ Р 54257-2010 строи-

тельное сооружение - это результат строительной деятельности, предназначенный для осуществления определенных потребительских функций. Здание - это результат строительной деятельности, предназначенный для проживания и (или) деятельности людей, размещения производства, хранения продукции или содержания животных. В данном случае здание является частным случаем строительного сооружения, но иногда в технической литературе под термином "сооружение" понимают строительные сооружения, которые не являются зданиями (тоннели, мосты, плотины, башни и пр.). Далее в т6кст6 сс(3jzvx'cltт^-и--и- для обозначения закрытых пространств мы будем использовать термины "здание", "сооружение", "помещение".

Для определения местоположения объектов внутри зданий разрабатываются и применяются специальные системы, называемые системами внутреннего позиционирования (indoors positioning system), использующие локальные навигационные поля, особенностью которых является невозможность принятия сигналов от глобальных навигационных систем и ограничение на дальность распространения радиосигнала [104, 118]. Такие системы имеют иерархическую структуру управления, состоящую из размещенных на некоторой территории, связанных и комплексно взаимодействующих между собой подсистем: множества стационарных точек доступа (базовых станций, радионавигационных точек), множества разного типа датчиков, закрепленных на мобильном объекте и сервера с программами позиционирования. Эти подсистемы обладают некоторой автономностью. При передаче информации на сервер позиционирования, как правило, происходит уплотнение информации (усреднение и дискретизация показаний датчиков, рассчитанных координат, уровней сигнâjiâ и т.д• ). Для построения indoors positioning system используются различные беспроводные технологии: WiFi, ZigBee, nanoLOC, UWB, Bluetooth и др. Одной из технологий внутреннего позиционирования яв-ля6т ся RealTrack.

Популярность систем определения местоположения объектов внутри зданий привела к развитию нового направления в науке - автоматическому определению местоположения объектов [92, 202]. Под позиционированием будем понимать процесс определения местоположения мобильного объекта. В качестве синонимов мы будем использовать термины определение местоположения, локализация. Под местоположением объекта понимается точка пространства, в которой в данный момент времени находится центр его масс [52]. Пространство, в котором перемещается мобильный объект будем называть помещением, хотя фактически это может быть и зданием, и шахтой, любым сооружением, даже частично открытым пространством. Главной задачей системы позиционирования является определение скалярных величин, характеризующих местоположение объекта. Этими скалярными величинами могут быть координаты положения объекта, номер зоны на плане помещения.

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

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

ми поверхностей положения являются сферы, плоскости, конусы, гиперболоиды.

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

Кроме того, математические модели для систем внутреннего позиционирования имеют следующие особенности. В некоторых моделях пространство нахождения объекта задано в виде конечного множества зон [126, 127], множества значений навигационных параметров тоже конечны, и, следовательно, поверхности положения навигационных параметров недифференцируемы. Иногда вместо поверхности положения навигационного параметра используются его распределения для каждой зоны. Например, навигационный параметр - уровень сигнала (целое число), для каждой зоны заданы распределения уровней сигнала от радио-НШШГсЩИОННЫХ точек.

В других моделях систем внутреннего позиционирования поверхность положения навигационного параметра представляет собой множество точек на евклидовом графе. Радионавигационная точка и объект

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

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

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

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

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

Степень научной разработанности проблемы

Точность современных систем внутреннего позиционирования не ВССГ^ДЭ; ЯВЛЯ6ТСЯ ДОСТЭ/ГОЧНОИ ДЛЯ НбКОТОрЫХ ПрИКЛ^ДНЫХ ЗсЬД^сЬЧ^ • Так точность систем, применяющихся в шахтах, составляет от 20 до 100 метров. Важной задачей является повышение точности определения местоположения объектов до 4 - 5 метров, а в некоторых приложениях до 1 метра [54]. Одним из способов решения этой задачи является определение оптимальных параметров системы, ее калибровка в процессе эксплуатации, использование данных, поступающих из разных источников, в том числе от инерциального измерительного модуля.

Способ калибровки системы зависит от конкретного алгоритма определения местоположения и используемых им данных. На сегодняшний день применяются разные методы в системах внутреннего позиционирования, известно множество алгоритмов определения местоположения. Один из подходов, рассматриваемый в рамках диссертационного исследования, основан на применении карт уровня сигналов. Местоположение объекта определяется с помощью обработки характеристик принимаемого сигнала (времени прохождения, уровня сигнала). План помещения предварительно разбивается на множество зон, затем строятся карты уровня принимаемых сигналов от точек доступа. Как правило, карта уровня сигнала точки доступа формируется из средних значений уровня ее сигнала в каждой зоне помещения. Когда мобильный объект выходит в эфир, он регистрирует сигналы от всех точек доступа. Этот набор уровней сигналов сравнивается с заранее составленными картами и в качестве местоположения объекта выбирается зона с набором значений, наиболее похожим на зарегистрированный набор [104, 118, 127]. Под определением параметров в таком случае подразумевается формирование карт уровня

сигналов, а также оптимальное по точности определения местоположения объектов размещение точек доступа сети в помещении.

О тд6 л ь н ы g результаты, связанные с решением задачи размещения точек доступа систем внутреннего позиционирования, представлены в работах Гимпилевича Ю. Б., Казаковцева J1., Савочкина Д. A., Baala О., Bal lili R., BrunaIо M., Caminada A., Chang С. T. Chen Y., Chen W., Chobtrong T., Délai A., Fang S. H., Farkas K., Fondrevelle J., Francisco J.

s

A., Gondran A., Gódor G., G fines E., Haid M., Huszák A., Ji Y., Jia W., Kamil M., Kim T., Liao L.. Lin T. N., Martin R. P., Russ J. A., Shin J., Так S., Trappe W., Wang G. S., Wen Y., Xuan D., Zhang G., Zhang L. и др. В большинстве исследовании еде л eh акцент HcL обеспечение максимального покрытия, в меньшей мере уделяется внимание точности определения местоположения. Во многих работах не учитывается случайный характер уровня сигнала.

Формирование карт уровней сигналов чаще всего производится вручную специалистами, но это требует затрат ресурсов (работа специалистов и оборудования). Причем карты уровня сигнала требуется формировать не только при развертке системы, но и при любом изменении ее конфигурации, например, при добавлении новых точек доступа, изменении конфигурации помещения, добавлении новых зон, изменении условий работы точки доступа (наклон антенны). Автоматическая калибровка позволяет избежать литтт h их 3â)tpât pi cf/t^e л^ clt ь работу системы определения местоположения более эффективной.

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

определения мобильных объектов.

Цель и задачи

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

Для достижения поставленной цели требуется решить следующие

1. Предложить и исследовать методы математического моделирования систем внутреннего позиционирования, основанных на беспроводных сетя^^с датчиков.

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

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

4. Разработать численные методы решения задачи оптимального размещения точек доступа системы определения местоположения.

5. Разработать алгоритм динамического построения карт уровней сигналов для

добавляемых точек доступа.

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

7. Спроектировать, реализовать и протестировать комплекс программ,

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

Научная новизна работы состоит в следующем.

1. Предложен метод математического моделирования систем внутреннего позиционирования, отличающийся вариабельностью способов представления покрываемой территории и методов определения ме-стоположенияпрбдн^зн^чбнныи для решения ЗсЬд^сЬЧ^ определения параметров этих систем с учетом требований к точности, безопасности, надежности, устойчивости. В предложенных моделях предполагается использование измерений, поступающих от различного рода датчиков (точек доступа беспроводной сети ^ датчиков Ivla^гI1[I/Iт ного поля, датчиков атмосферного давления тиг т.дт^.^ дт^л^я^ тигз которых используется уникальное разбиение на зоны и карта ш аб лонов измерений в этих зонах. Особенностью моделей является использование для каждой зоны вероятностных распределений всех возможных в ней комбинаций измерений.

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

3. Предложена графовая модель, предназначенная для теоретического

исследования алгоритмов размещения точек доступа системы внутреннего позиционирования. Показана связь между задачей размещения точек доступа и задачей определения разрешающего множества вертттин графа. Минимально необходимому числу точек доступа соответствует метрическая размерность графа. Рассмотрена задача построения разрешающего множества с учетом отказов точек доступа. Найдены новые формулы для отказоустойчивой метрической размерности графа, равного сильному произведению двух простых т т;е! 1ви«

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

5. Разработан алгоритм динамического построения карт уровня сигналов добавляемой точки доступа системы внутреннего позиционирования, основанный на ЕМ-методе, отличающийся использованием на М-шаге оценок вероятностей нахождения объектов в зонах помещения, вычисляемых методами позиционирования.

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

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

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

Теоретическая значимость работы

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

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

Практическая значимость работы

Разработанные математические модели, алгоритмы и программы имеют практическую ценность при проектировании систем определения местоположения мобильных объектов в помещениях, определении параметров этих систем, их установке и эксплуатации, для повышения эффективности работы систем определения местоположения и сокращения затрат на калибровку систем. Методы решения задачи определения мест размещения точек доступа можно использовать для обеспечения заданной скорости передачи информации с учетом интерференций сигналов, предотвращения перегрузки трафика беспроводной сети«I повышения кй чества работы систем определения местоположения объектов в помещениях, сокращения времени их работы в режиме off-line. Разработанные методы используются в системах определения местоположения, разработанных на базе ИТ -парка ПетрГУ.

Методология и методы исследования

В диссертационной работе используются методы математического моделирования, теории вероятностей, дискретной математики, в том числе теории графов и гиперграфов, методы построения алгоритмов, объектно-ориентированное программирование. Программы написаны на языках С++, и Java.

Положения, выносимые на защиту

1. Класс математических моделей, описывающих системы внутреннего позиционирования ^ предан аз наченных ля решения зад^ач опред^еле-ния оптимального числа и размещения узлов этих систем.

2. Численный метод определения оптимальных мест размещения точек доступа системы внутреннего позиционирования.

3. Вероятностное обобщение задачи метрической размерности графа и задача построения разрешающего множества с учетом отказов.

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

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

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

7. Методика развития системы внутреннего позиционирования и рекомендации к применению предложенных подходов.

Степень достоверности

./^.дт^ск!. teitlt н ост ть предложенных математических моделей, работоспособность и достоверность расчетов разработанных алгоритмов были проверены на реальных данных, полученных в ходе тестирования систем определения местоположения мобильных объектов, созданных в лаборатории по разработке беспроводных сетей нового поколения ПетрГУ и в МИП ООО "Наносети" при участии автора диссертации. Мировой уровень результатов исследований подтверждается внешними независимыми экспертными оценками. В 2013 году разработанная технология внутреннего позиционирования RealTrac заняла первое место в международном конкурсе систем определения местоположения внутри помещений EvAAL-2013 (http://evaal.aaloa.org/).

Апробация результатов

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

конкурсах и семинарах, среди них: 11th International Conference on Telecommunications for Intelligent Transport Systems (ITST-2011), Санкт-Петербург, 2011 год; 1st International Symposium on Wireless Systems IDAACS-SWS, Offenburg, Germany, 2012 год; X Международная научно-технически я конференция "Новые информационные технологии в ЦБП и энергетике", Петрозаводск, 2012 год; Всероссийская конференция с международным участием "Применение космических технологий для развития арктических регионов", Архангельск, 2013 год; конкурс "Evaluating AAL Systems through Competitive Benchmarking", Smart House Living Lab of the Polytechnic University of Madrid, Spain; Международный форум "Классический университет в пространстве трансграничности на севере Европы: стратегия инновационного развития", Петрозаводск, 2014 год; IX Всероссийская научно-практическая конференция "Научно-образовательная информационная среда XXI века", Петрозаводск, 2015 год; III Международная научно-практическая конференция "Инновационные технологии в науке и образовании", Чебоксары, 2015 год; научный семинар кафедры теории вероятностей и анализа данных Петрозаводского государственного университета, Петрозаводск, 2015 год; IX Международная Петрозаводская конференция "Вероятностные методы в дискретной математике", Петрозаводск, 2016 год; XI Международная научно-техническая конференция "Автоматизация и управление в ЦБП, ЛПК и энергетике", Петрозаводск, 2016 год; научный семинар факультета математики и информационных технологий Петрозаводского государственного университета, Петрозаводск, 2016 год; X Всероссийская научно-практическая конференция "Научно-образовательная информационная среда XXI века", Петрозаводск, 2016 год; IX Международная конференция "Современные методы прикладной математики, теории управления и компьютерных технологии (ПМТУКТ-2016), Воронеж, 2016 год; Международная конференция "Распределенные компьютерные и телекоммуникационные сети: управление, вычисление, связь" (DCCN-2016), Москва, 2016 год;

научный семинар Института прикладных математических исследований Карельского научного центра РАН, 2016 год; X Международная конференция "Современные методы прикладной математики, теории управления и компьютерных технологий" (ПМТУКТ-2017), Воронеж, 2017 год; Международная конференция "Распределенные компьютерные и телекоммуникационные сети: управление, вычисление, связь" (DCCN-2017), Москва, 2017 год.

Часть результатов диссертационного исследования была получена в ход^е выполнения работ над грантом Министерства образования и науки Российской Федерации (государственный контракт номер 14.ВВВ.21.0162), в котором автор диссертации является соисполнителем.

Публикации по теме исследования

П редстэ^влен н вте результаты диссертационного исследования опубликованы в научных изданиях, всего по теме диссертации опубликовано 38 работ, в том числе 1 статья в журнале, входящем в базу данных Web of Science, в рецензируемых научных изданиях из списка ВАК 14 работ, 9 свидетельств о государственной регистрации программ для ЭВМ. Материалы диссертационной работы изложены в материалах международных научных конференций, включая 2 публикации, входящих в базу денных Scopus.

Личное участие

Все основные результаты диссертации были получены автором самостоятельно. В частности, автором диссертации были построены и исследованы представленные математические модели, разработаны мето-дв! решения hoctcLb л^ен^н^в1х^ з^д^чпредло^кенные алгоритмы до в еде н ы до программной реализации.

Все опубликованные работы были спланированы и оформлены при прямом участии автора диссертации. В работе [172] описана технология RealTrac, созданная коллективом соавторов при участии автора диссертации, лежащая в основе исследуемых систем определения местоположе-

ния. В c'x'cl'x'x) .ifijnt [12, 13, 14, 16, 17, 18, 22, 24] хт j) ед с 'xs cl в л е хх x^i разработанные автором диссертации математические модели и методы решения поставленных задач. В этих работах автору принадлежит также постановка задач, доказательство утверждений, программная реализация алгоритмов, анализ тестовых испытаний. Как правило, соавторы отвечали за описание предметной области исследуемых задач, а также помощь при организации экспериментов. В работе [12] второй соавтор принимал участие в исследовании математической модели. В работе [18] второй соавтор проводил тестовые испытания разработанного метода. В работе [17] соавторам принадлежит значительный вклад в настройку оборудования, организацию экспериментов, сбор и, частично, анализ данных. В работах [25, 2б, 44, 47, 58, 89] описаны задачи эвакуации людей из помещений, маршрутизации робота в здании, построения транспортных путей, трансляции медиа-потоков в Wi-Fi сетяхj для которых необходимо решать исследуемые в диссертации задачи определения местоположения. Автору диссертации принадлежат математические модели представлен-ххпредметных областей. Статьи [44, 47, 89] были инициированы соавторами, им же принадлежат описания предметных областей. Кроме того, в работах [25, 26] совместно со вторым соавтором исследована применимость гиперграфовых моделей в задачах построения транспортных путей, эти же идеи были использованы автором в гиперграфовых моделях помещения для системы определения местоположения. Третий соавтор этих работ отвечал за описание предметной области.

Кроме того, по теме диссертации имеется работа [75], опубликованная в соавторстве в сборнике научных публикаций, а также публикации (часть в соавторстве) в материалах международных и всероссийских конференций и форумов [2, 15, 19, 20, 21, 23, 43, 45, 48, 58, 87, 127, 175]. Соавторы принимали участие с сборе материалов для обзорной части докладов«

Имеются свидетельства о государственной регистрации программ

для ЭВМ [1, 9, 59, 76, 77, 78, 80]. Автору диссертации принадлежит авторство разработанных алгоритмов, руководство их программной реализацией, кодирование и тестирование программ, оформление заявок на получение свидетельств. Соавторы принимали участие в сборе информации об имеющихся алгоритмах, кодировании и тестировании программ.

Программы [42, 46] были инициированы и разработаны соавторами. Автор диссертации принимал участие в анализе тестовых данных, оформлении заявок на получение свидетельств.

Структура работы

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

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

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

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

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

В пятой главе содержится описание приложения, имитирующего работу системы внутреннего позиционирования, приводятся результаты тестовых испытаний. Особенностью разработанной системы является использования специального алгоритма разбиения плана помещения на небольшие ЗОНЫ.

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

Глава

Задачи определения местоположения мобильных объектов в ограниченных пространствах, обзор наиболее распространенных моделей и методов

В данной главе представлено описание наиболее распространенных методов определения местоположения, формулируются задачи исследования. Результаты, 1,1,редставленн .в глa^-B(з^ опубликованы в [44, 45, 47, 48, 58, 87, 89, 127, 172, 175].

1.1 Существующие методы определения местоположения мобильных объектов в ограниченных пространствах

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

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

Основной проблемой применения методов радионавигации в помещениях является большая, чем на отрытой местности, неоднородность и неизотропность пространства. Для определения местоположения объектов внутри помещений применяют различные беспроводные технологии [41, 93, 111, 115, 121, 128, 165, 173, 186, 197].

Для классификации систем определения местоположения можно использовать следующие признаки:

• размер покрываемой территории;

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

Введение диссертации (часть автореферата) на тему «Математические методы и модели систем определения местоположения мобильных объектов внутри зданий и сооружений»

работы;

положения;

• стоимость системы;

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

По размеру территории системы определения местоположения делятся на глобальные (различные виды геопозиционирования: спутниковые, по Wi-Fi сетям, по сотовым вышкам и другие) и локальные (внутри помещений) [73].

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

навигационных

недостаточна для использования в масштабах помещений, так как ошибка определения местоположения может достигать нескольких десятков метров [73]. Кроме того, сигнал со спутников не проходит через стены и крыши зданий, что также ограничивает их применение внутри помещений. Исключением являются системы, предполагающие установку специального оборудования, ретранслирующего сигнал внутрь помещений. Примерами такого рода систем являются разработки компаний SnapTrack, Atmel, U-blox с заявляемой точностью от 1 до 50 метров.

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

здании установлено несколько базовых станций. Пример такой системы описан в [183], точность измерений достигала 2.5 метров.

Большинство из систем определения местоположения объектов внутри помещений основано на использовании беспроводных сетей (WLAN) таких стандартов^ как WiFi [49, 143, 187], ZigBee, Bluetooth, UWB и др. [50, 115, 127, 184]. Такие системы состоят из нескольких базовых станций (точек доступа) и мобильного устройства, местоположение которого необходимо определит « Иногда подобные системы требуют доволвно трудоемкого предварительного построения карт уровней сигналов точек доступа [13, 168]. Одной из проблем является переотражение сигналов от стен зданий [74]. Точность определения местоположения в стандартных беспроводных сетях составляет от 2 дл^о 30 метров.

Некоторые системы определения местоположения, основанные на беспроводных сетях, используют технологию UWB [160], прбдн азначен ную для передачи информации на малые расстояния (до 10 м). При этом для передачи сигнала применяется сразу несколько частот в диапазоне от 3.1 до 10.6 Ггц. Точки доступа могут быть расположены в непосредственной близости с другими устройствами, так как благодаря широкому диапазону частот удается избежать интерференции. Технология предполагает использование большего количества точек доступа.

На данный момент создано большое количество систем определения местоположения мобильных объектов внутри помещений. Некоторые системы используют уже существующую сетевую беспроводную инфраструктуру, например, Wi-Fi, другие - основаны на собственных разработках. В первом случае снижается стоимость на развертывание сети, но при этом не всегда можно гарантировать достаточную точность определения местоположения. Во втором случае имеется возможность контролировать физические свойства сети и, тем самым, влиять на качество и точность определения местоположения. Плотность точек доступа может быть подобрана ДЛЯ ДОС'ЛИ-^КбНия необходимой точности измерения.

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

Любая система определения местоположения объектов включает передатчики сигнала и его приемники. Измерение включает передачу и прием сигнала между используемыми устройствами. По типу расположения приемников и передатчиков сигнала можно выделить четыре основных системы определения местоположения мобильных объектов. В первой системе передатчик сигнала находится на мобильном объекте, несколько стационарных точек доступа принимают от него сигнал. Результаты измерений собираются вместе, далее определяется местоположения мобильного объекта. Во второй системе стационарные точки доступа снабжены передатчиками сигналов, а мобильных объект снабжен приемником сигналов и вычисляющим модулем. Местоположение объекта определяется на основании принятых им сигналов от точек доступа. В третьей системе мобильный объект принимает сигналы от передатчиков стационарных точек доступа и отсылает результат его измерения на центральную базовую станцию. В четвертой системе стационарные точки доступа принимают сигнал от передатчика мобильного объекта и отсылают результат его измерения обратно.

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

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

Перейдем к критериям сравнения систем определения местоположения. Под ошибкой расчета местоположения (ошибка определения местоположения, accuracy, location error) понимается среднее расстояния между рассчитанной позицией объекта и его истинной позицией. Некоторая ошибка имеется у всех систем определения местоположения, причем, чем меньше отклонение от истинной позиции, тем более точной считается система. Часто ошибка определения местоположения вступает в противоречие с другими критериями, что вынуждает идти на некоторый компромисс.

Точность (precision) оценивает разброс значений ошибки определения местоположения для большого количества испытаний. В некоторых источниках точность определяются как эмпирическое стандартное отклонение ошибки определения местоположения, в других - как эмпирическая функция распределения расстояния между рассчитанной позицией объекта и его истинной позицией. При сравнении двух систем определения местоположения лучшей является та, у которой эмпирическая функция распределения раньше достигает значений с заданной высокой вероятностью. На практике значения эмпирической функции рас-XT Л (3IX хтя ошибки ранжируются в процентильном формате. При этом указывается, чему равна точность определения местоположения в определенном проценте измерений (например, 2 метра в 90 % случаев и 2.5 метра в 95 % случаев).

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

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

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

Масштабируемость системы означает сохранение точности определения местоположения системы при увеличении расстояния до мобильного объекта. Как правило, точность определения местоположения падает при увеличении расстояния между передатчиком сигнала и его приемником. Например, иногда требуется определять местоположение объекта при его удалении на 300 метров от базовой станции. С масштабируемостью связано два понятия: покрытие и плотность. Покрытие определяет площадь, в пределах которой корректно работает система определения местоположения. Плотность определяет число мобильных объектов НО) бдиницб плогцоди ЗсЬ бдиницу врбмбни работы системы. Например, в тттсьхтсьх может потребоваться одновременное позиционирование 1000 устройств. Кроме того, можно говорить о плотности по отношению к

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

И, наконец, рассмотрим стоимость системы определения местоположения. Стоимость может зависеть от денежных затрат на закупку оборудования и программного обеспечения, времени на ее развертывание, площади покрытия, затрат на потребляемую энергию, установку системы, ее обслуживание и поддержку, количество точек доступа. Иногда стоимость системы можно снизить за счет использования существующих беспроводных систем, например, Wi-Fi. Необходимо также учитывать затраты на подзарядку аккумуляторных батарей мобильных устройств.

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

1.2 Обзор ж классификация алгоритмов внутреннего позиционирования на основе обработки сигналов точек доступа

Рассмотрим широко используемые модели и алгоритмы систем определения местоположения мобильных объектов внутри помещений и приведем

их классификацию [104]. На практике применяются различные базовые методы - триангуляция, определение местоположения по картам уровня сигналов, анализ близости, байесовские С6ТИ 51 .

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

I. Метод триангуляции

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

Методы трилатерации

Алгоритмы трилатерации основаны на измерении расстояний и в явной форме моделируют эффект затухания сигнала с расстоянием.

а) Рассмотрим оценивание расстояния в зависимости от времени прохождения сигнала (time of arrival, TOA).

В этом случае предполагается, что расстояние от мобильного устройства до точки доступа прямо пропорционально времени прохождения сигнала. В двумерном пространстве для определения местоположения объекта достаточно трех точек доступа, а в трехмерном - четырех точек доступа. При оценивании расстояния между передатчиком сигнала и приемником определяется время прохождения сигнала между ними,

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

Стандартный подход определения точки местоположения объекта таков состоит в применении метода наименьших квадратов. Пусть мобильный объект находится в точке с координатами (x,y)7 которые необходимо найти, и передает сигнал в момент времени to- Далее N точек доступа, расположенных в точках с координатами (xj ,yj) принимают сигнал в моменты времени tj, , j = 1,..., N (либо точки доступа передают СИГНАЛ «i cL ДАТЧИК мобильного объекта его принимает). Для оценивания значений (x, y) находится минимум целевой функции

N ( /- V

(x,y) = arg Dim ( V (xj - x)2 + (yj - y)2 - c(tj - to)J , j=i

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

Иногда для оценивания местоположения объекта применяют метод "ближайшего соседа". В этом случае позиция объекта определяется как расположение точки доступа, сигнал до которой прошел быстрее остальных. Это применимо в ситуации отсутствия прямой видимости и наличия больших помех. Метод, основанный на измерении времен прохождения электромагнитной волной расстояния между точкой доступа и мобильным устройством (time of flight,ToF), работает аналогично, только он не требует синхронизации часов точки доступа и мобильного устройства.

б) Рассмотрим оценивание расстояния в зависимости от разности моментов времени прихода сигналов (time difference of arrival, TDOA). В этом методе местоположение объекта определяется путем вычисления разницы расстояний между объектом и несколькими точками доступа с известным расположением. Для каждой разности моментов времени

прихода сигналов, объект находится на гиперболе (в двумерном пространстве) или на гиперболоиде (в трехмерном пространстве) на определенной разности расстоянии от точек доступа. Пусть мобильный объект находится в точке с неизвестным координатами (x,y) и передает сигнал. Точки доступа г и j имеющие координаты (xi,yi) и (xj,yj) принимают сигнал с задержкой по времени At. Тогда разница расстояний между объектом и точками доступа равна

ARij (x,y) = sj(xi - x)2 + (yi - y)2 - ^(xj - x)2 + (yj - y)2.

Для оценивания координат объекта (x,y) необходимо решить систему, составленную из уравнений вида

ARij (x,y) = cAt,

для нескольких пар г и j где c - скорость распространения сигнала.

На практике вместо точного решения часто используют линеаризацию функции ARij(x,y) и последующее применение сходящегося итеративного алгоритма. Отметим, что в двумерном случае можно обойтись системой из двух уравнений.

в) Далее рассмотрим оценивание расстояния в зависимости от уровня принятого сигнала (received signal strength, RSS). Два предыдущих метода имеют ограничения для применения на практике. В закрытых пространствах почти никогда не бывает прямой видимости между передатчиком и приемником сигнала. Прохождению сигнала мешают различные препятствия, следствием чего являются переотражения сигнала, увеличивающие время его распространения. Все это снижает точность определения местоположения объекта. Вместо этого iiрсдлсЪГсьетс.я оце нивать расстояние до мобильного объекта в зависимости от уровня принятого им сигнала от точки доступа. Имеются многочисленные модели, описывающие функциональную зависимость между уровнем сигнала и расстоянием от передатчика до приемника. Кроме того, для конкретных помещений можно строить специальные регрессионные модели. Это

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

Расчет координат (X,y) нахождения мобильного объекта может рассматриваться как задача оптимизации, где местоположения точек доступа (Xi, yi) известны, и оценки рас стояния di между объектом и точками доступа находятся при помощи функциональной зависимости уровня сигнала и пройденного сигналом расстояния. Тогда задача сводится к

( X, y )

(x,y) = arg min ^ ( \/(xj - x)2 + (Уз - У)2 - c(t3 - t0)) ■ j=i

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

г) Наконец рассмотрим метод оценки времени круговой задержки сигнала или время приема-передачи (round-trip delay time, RTD; round-trip time, RTT). В этом подходе измеряется время кругового обращения сигнала от передатчика к приемнику и обратно. В этом случае не требуется жесткой синхронизации времени на точках доступа и мобильном объекте. Для оценивания местоположения объекта используются метоДЫ 011 HC9iHHbI6 ДЛЯ МбТОДй ТОА. По сути, мобильный объект выступает в качестве радара. Объект возвращает посланный ему сигнал от точек доступа, и время на полное обращение сигнала от них дает возможность вычислить местоположение объекта. В качестве недостатка можно отметить, что на точность метода влияет неизвестное время обработки сигнала мобильным объектом при приеме и последующей его передаче. В системах дальнего или среднего действия эта задержка не так суще-

СТВбННООДНсЬК^О ДЛЯ СИСТ6М ближнего действия онсь су^т^ественно вл^и^я^ет на результат.

Методы ангуляции

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

II. Определение местоположения по картам уровня сигналов

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

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

Для этого пространство возможного местоположения объекта сперва становится дискретным - разбивается на конечное множество зон, в каждой из которых может находиться мобильный объект. Затем во всех

зонах для каждой точки доступа определяется и ставится в соответствие некоторая характеристика уровня сигнала, обычно его усредненное значение. На втором этапе, проходящем во время эксплуатации системы определения местоположения (фаза онлайн), датчики мобильного объекта собирают информацию о сигнале со всех точек доступа. Далее по специальному алгоритму определяется наиболее вероятная позиция мобильного объекта путем сопоставления собранных измерений с данными из карт уровня сигналов [134].

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

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

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

а) Метод максимального правдоподобия (highest probability). На

первом этапе пространство разбивается на N зон возможного расположения мобильного объекта. Затем для каждой точки доступа и для каждой зоны 3 = 1,..., N задаются распределения случайных величин з^ - уровней сигналов от точек доступа в зонах. Эти случайные величины являются дискретными, так как радиопередача осуществляется в цифровой форме, и входной сигнал регистрируется, например, с использованием аналого-цифровых преобразователей или управляемых автоматических регуляторов усиления.

На втором этапе задача состоит в том, что бы для заданного вектора уровня сигнала 3 = (31,..., зм) от точек доступа, измеренных приемником мобильного объекта найти зону 3 с максимальной условной вероятностью р(3 | 3):

3 * = а^ тах{р( ^ 1 з)}.

з

Запись р(3 | 3) обозначает апостериорную вероятность находиться в зоне 3, при условии, что был зафиксирован вектор уровня сигнала 3.

Если от точки доступа г сигнал не зафиксирован, то будем считать 3* = 0.

Используя формулу Байеса, получаем:

ри 13) = рщш.

р(з)

Если предположить, что все вероятности р(3) нахождения объекта в каждой зоне одинаковы, то для данного вектора 3

Р(3)

Таким образом,

а^тах{р(з | 3)} = а^тах{р(3 | 3)}.

зз

Общепринятым [126] является предположение, что для каждой зоны 3 = 1,..., N компоненты вектора 3 являются совместно независимыми случайными величинами. Поэтому

м

Р(3 | 3) = Р((31, ■■■ ,3м) | 3) = П Р(3* | 3)'

На практике при расчетах произведение следует брать по тем индексам г, для которых &г > 0:

I 3) = П Р(&г 1 3)

i: «¿>0

Это мотивировано тем, что ситуация, когда &г = 0 может возник-

г

брать в расчет не следует.

Для работы алгоритма на первом этапе необходимо оценить вероятности р(&г | 3). Оценки этих вероятностей можно определить на основе предварительных испытаний. Как известно [126], уровень сигнала в каждой такой зоне будет колебаться под влиянием многих слабо зависимых факторов и поэтому, основываясь на центральной предельной теореме, можно считать, что величина имеет нормальное распределение. Следовательно, для полного описания карт уровня сигналов системы определения местоположения достаточно знать величины агз и - соответственно, математическое ожидание и дисперсию дискретной случайной ^в6Jтичин^b)I *

Пусть 0 - индексное множество полученных в ходе испытаний векторов сил сигналов для всех зон, 0(3) - индексное множество векторов уровня сигналов для зоны 3 = 1,..., N. Таким образом

N

0 = 1)0(3).

з=1

Для каждого к € 0(3) обозначим = (&к1, &кМ) - зафиксиро-

3

г

положительных значений (то есть нулевые значения не учитываем):

кг

аА3) = 1{к : к € 0(3)& &кг > 0}| • Будем полагать а() = 0 если для зоны 3 и точки доступа г отсутствуют результаты измерений.

Далее дискретную случайную величину 3* для зоны 3 аппроксимируем при помощи нормального распределения N (а* (3), а). Среднеквадратичное отклонение а подбирается экспериментально.

Таким образом, оценки вероятностей для 3* можно оценить, например, таким образом:

б) Метод ближайшего соседа. В этом методе на этапе онлайн для измеренного мобильным объектом вектора уровня сигналов ищется k ближайших векторов в карте, составленной на этапе офлайн для всего

k

екта определяется путем взвешенного усреднения найденных позиций.

В качестве примера можно привести алгоритм RADAR, требующий предварительных данных в виде известных уровней сигналов от каждой точки доступа для набора точек помещения (x,y). В качестве результата при определении местоположения выбирается такая точка, набор уровней сигналов для которой наиболее похож на зарегистрированный мобильным объектом набор.

Список литературы диссертационного исследования доктор наук Воронов Роман Владимирович, 2017 год

Литература

[1] Андреева, И. С. Программа оптимальной расстановки базовых станций системы локации в помещении / И. С. Андреева, Р. В. Воронов / / в и дет ел ь от тзо о государственной регистрации программы для ЭВМ. Правообладатель: Петрозаводский государственный университет. Свидетельство №2016660258. Заявка №2016617511. Дата поступления 12.07.2016. Зарегистрировано в Реестре программ для ЭВМ 09.09.2016.

[2] Андреева, И. С. Эвристический алгоритм расстановки базовых станций системы локации объектов в помещении / И. С. Андреева, Р. В. Воронов //В сборнике: Научно-образовательная информационная среда XXI века. Материалы X Всероссийской научно-практической конференции. - Петрозаводск. - 2016. - С. 4-6.

[3] Асанов, М. О. Дискретная оптимизация: Учебное пособие / М. О. Асанов. - Екатеринбург, 1998.

[4] Ахо, А. В. Построение и анализ вычислительных алгоритмов / А. В. Ахо, Д. Э. Хопкрофт, Д. Д. Ульман. - Москва: Мир, 1979.

[5] Ахо, А. В. Структуры данных и алгоритмы / А. В. Ахо, Д. Э. Хопкрофт, Д. Д. Ульман. - Москва: Вильяме, 2003.

[6] Берж, К. Теория графов и её применение / К. Берж. - Москва: Издательство иностранной литературы, 1962.

[7] Берштейн, Л. С. Нечеткие графы и гиперграфы / Л. С. Берштейн, А. В. Боженюк. - Москва: Научный мир, 2005.

[8] Бочаров, П. П. Теория вероятностей. Математическая С Т 8.Т И С Т И К с! / П. П. Бочаров, А. В. Печинкин. - 2-е изд.- Москва: ФИЗМАТЛИТ, 2005. - 296 с.

[9] Бурлакова, В. В. Программа для определения оптимального размещения точек доступа системы локации с учетом погрешности измерений / В. В. Бурлакова, Р. В. Воронов // Свидетельство о государственной регистрации программы для ЭВМ. Правообладатель: Петрозаводский государственный университет. Свидетельство №2016660279. Заявка №2016617600. Дата поступления 12.07.2016. Зарегистрировано в Реестре программ для ЭВМ 12.09.2016.

[10] Вагнер, Г. Основы исследования операций: В 3 т. / Г. Вагнер. -Москва: Мир, 1972 - 1973.

[11] Вентцель, Е. С. Исследование операций / Е. С. Вентцель. - Москва: Наука, 1980.

[12] Воронов, Р. В. Автоматическая калибровка локальных систем позиционирования на основе построения карты сил сигналов / Р. В. Воронов, О. В. Лукашенко, А. П. Мощевикин // Труды Карельского научного центра РАН. - 2014. - №4. - С. 29-35.

[13] Воронов, Р. В. Динамическое создание карт уровня АМГьсигиилоп для систем локального позиционирования / Р. В. Воронов, С. В. Малодушев // Системы и средства информатики. - 2014. - Т. 24. -№1. - С. 79-91.

[14] Воронов, Р. В. Задача оптимального размещения точек доступа системы позиционирования объектов в помещении / Р. В. Воронов // Вестник Санкт-Петербургского университета. Серия 10. Прикладная математика. Информатика. Процессы управления. - 2017. - Вып. 1. - С. 61-73.

[15] Воронов, Р.В. Задача оптимального расположения базовых станций системы локации в помещениях / Р. В. Воронов, В. В. Бурли кони //В сборнике: Научно-образовательная информационная

XXI века. Материалы IX Всероссийской научно-практической конференции. - 2015. - С. 46-48.

[16] Воронов, Р. В. Задача привязки траектории объекта к плану помещения / Р. В. Воронов, А. С. Галов, А. П. Мощевикин, А. М. Воронова //

записки Петрозаводского государственного университета. Серия: Естественные и технические науки. - 2015. - №2 (147). - С. 87-91.

[17] Воронов, Р. В. Метод обработки

данных рО)СпрбДбЛбннои сбти дат чиков давления для оценки относительной высоты мобильного узла / Р. В. Воронов, А. С. Волков, С. А. Региня, А. А. Федоров, А. П. Мощевикин // Современные проблемы науки и образования. -2013. - №4; ГПЬ: http://www.science-education.ru/110-9631

[18] Воронов, Р. В. Метод определения местоположения мобильных объектов в тттсз

/ Р. В. Воронов, А. С. Галов, А. П. Мощевикин, А. М. Воронова, Т. В. Стёпкина // Современные проблемы науки и образования. - 2014. - №4; ГПЬ: ЫI р: /www.science-education.ru/118-13876

[19] Воронов, Р. В. О подходах к задаче расстановки базовых станций для внутренних систем позиционирования / Р. В. Воронов, О. В. Лукашенко //В сборнике: Распределенные компьютерные и телекоммуникационные сети: управление, вычисление, связь. Материалы XIX международной научной конференции (БССХ-2016). Том 1. Архитектура, методы управления, моделирования и проектирования компьютерных сетей. - Москва, 2016. С. 181-184.

[20] Воронов, Р. В. Обобщение задачи определения метрической размерности

графа / Р. В. Воронов //В сборнике: Вероятностные методы

в дискретной математике. Материалы IX Международной Петрозаводской конференции. - Петрозаводск. - 2016. - С. 20-22.

[21] Воронов, Р. В. Обобщенная задача локации мобильных объектов в помещениях / Р. В. Воронов //В сборнике: Инновационные технологии в науке и образовании. Материалы III международной научно-практической конференции. - Чебоксары. - 2015. - №3. -С. 183-185.

[22] Воронов, Р. В. Отказоустойчивая метрическая размерность графа ходов шахматного короля / Р. В. Воронов // Вестник Санкт-Петербургского университета. Серия 10. Прикладная математика. Информатика. Процессы управления. - 2017. - Вып. 3. - С. 241-249.

[23] Воронов, Р. В. Развитие технологий локации объектов в беспроводных сист(31\/1сьх / Р. В. Воронов //В сборнике: Классический университет в пространстве трансграничности на Севере Европы: стратегия инновационного развития. Материалы Международного форума. - Петрозаводский государственный университет. - 2014. -С. 16-17.

[24] Воронов, Р. В. Применение условной энтропии при формировании рекомендаций по размещению базовых станций в локальных системах позиционирования / Р. В. Воронов, А. П. Мощевикин // Информационные технологии. - 2014. - №10. - С. 11-16.

[25] Воронова, А. М. Задача покрытия гиперсети взвешенным корневым деревом и ее приложение для оптимального проектирования схем волоков на лесосеках / А. М. Воронова, Р. В. Воронов, М. А. Пискунов // Информатика и системы управления. - 2012. - №1 (31). - С. 56-64.

[26] Воронова, А. М. Моделирование схемы волоков при помощи покрытия гиперсети взвешенным корневым деревом / А. М. Воронова, Р.

В. Воронов, М. А. Пискунов // Ученые записки Петрозаводского государственного университета. Сер. "Естественные и технические науки". - 2012. - №2 (123). - С. 114-117.

[27] Галов, А. С. Алгоритмы локации мобильного устройства в беспроводной сети базовых станций стандарта 802.15.4а (папоЬОС) / Га-лов Александр Сергеевич // диссертация на соискание ученой степени канд^ид^ата технических наук. 05.13.18. - Петрозаводск, 2016.

- 144 с.

[28] Гэри, М. Вычислительные машины и труднорешаемые задачи / М. Гэри, Д. Джонсон. - Москва: Мир, 1982.

[29] Евстигнеев, В. А. Применение теории графов в программировании / В. А. Евстигнеев. - Москва: Наука, 1985.

[30] Ершов, А. П. Введение в теоретическое программирование / А. П. Ершов. - Москва: Наука, 1977.

[31] Зыков, А. А. Гиперграфы / А. А. Зыков // Успехи математических наук. - 1974. - №6 (180).

[32] Зыков, А. А. Основы теории графов / А. А. Зыков. - Москва: Наука, 1987.

[33] Калиниченко, Ю. В. Алгоритм привязки СРБ-ч реки к дорожному графу / Ю. В. Калиниченко, Я. С. IIщей ко // Научные труды 8\\ог1(1. - 2012. - Т. 13. - №. 4. - С. 78-80.

[34] Карманов, В. Г. Математическое программирование / В. Г. Карманов. - Москва: Физматлит, 2001.

[35] Кнут, Д. Искусство программирования для ЭВМ, т. 1-3 / Д. Кнут.

- Москва: Мир 1977.

[36] Кормен, Т. Алгоритмы: построение и анализ / Т. Кормен, Ч. Лей-зерсон, Р. Ривест. - Москва: МЦНМО; БИ-НОМ. Лаборатория знаний, 2004.

[37] Кристофидес, Н. Теория графов. Алгоритмический подход / Н. Кристофидес. - Москва: Мир, 1978.

[38] Кузнецов, В. Ю. Задачи покрытия: модели, алгоритмы и приложения / В. Ю. Кузнецов, М. С. Егорова // Принятие решений в условиях неопределенности : сборник научных трудов. - 2008. С. 138-143.

[39] Липский, В. Комбинаторика для программистов / В. Липский. -Москва: Мир, 1988.

[40] Лотарев, Д. Т. Преобразование задачи Штейнера на Евклидовой плоскости к задаче Штейнера на графе / Д. Т. Лотарев, А. П. Узде.мир // Автоматика и телемеханика - 2005. - №10. - С. 80-92.

[41] Лукьянов, Е. А. Индукционное позиционирование. Введение в метод / Е. А. Лукьянов, В. С. Семенов. - Велес. - 2016. - №7-1. - С. 56-60.

[42] Малодушев, С. В. Эмулятор процесса эвакуации / С. В. Малодушен. Е. В. Абрамов, Р. В. Воронов // Свидетельство о государственной регистрации программы для ЭВМ. Правообладатель: Петрозаводский государственный университет. Сви-

ел ст во №2017612074. Заявка №2016664534. Дата поступления 28.12.2016. Зарегистрировано в Реестре программ для ЭВМ 14.02.2017.

[43] Малодушев, C.B. Вероятностная модель на графе Л .Я 3 cLf/1^cl/4 И О П тимальной расстановки базовых станций системы локации / С. В. Малодушев, Р. В. Воронов, Е. В. Абрамов //В сборнике: Современные методы прикладной математики, теории управления и компью-

терных технологии. Материалы IX международной конференции (ПМТУКТ-2016). - Воронеж, - 2016. - С. 218-221.

[44] Малодушев, С. В. Математическая модель эвакуации людей из зданий в экстренных ситуациях / С. В. Малодушев, Р. В. Воронов, Е.

B. Абрамов // Проблемы безопасности и чрезвычайных ситуаций. - 2016. - №6. - С. 29-40.

[45] Малодушев, С. В. Математическая модель эвакуации людей из здания / С. В. Малодушев, Р. В. Воронов //В сборнике: Вероятностные методы в дискретной математике. Материалы IX Международной Петрозаводской конференции. Петрозаводск. - 2016. - С. 47-49.

[46] Малодушев, С. В. Программа сканнер беспроводных Wi-Fi сетей / С. В. Малодушев, Р. В. Воронов / / Свидетельство о государственной регистрации программы для ЭВМ. Правообладатель: Петрозаводский государственный университет. Сви-Д6Т6Льство №2015619990. Заявка №2015617195. Дата поступления 04.08.2015. Зарегистрировано в Реестре программ для ЭВМ 18.09.2015.

[47] Малодушев, С. В. Определение оптимальных путей эвакуации из здания / C.B. Малодушев, Р. В. Воронов / / Фундаментальные исследования. - 2015. - №10-3. - С. 495-502.

[48] Малодушев, С. В. Моделирование эвакуации из зданий людей различных групп мобильности / С. В. Малодушев, Р. В. Воронов, А. А. Рогов //В сборнике: Современные методы прикладной математики, теории управления и компьютерных технологий. Материалы IX международной конференции (ПМТУКТ-2016). - Воронеж, 2016. -

C. 221-225.

[49] Малодушев, С. В. Определение локации в корпоративных Wi-Fi сетях / С. В. Малодушев, А. А. Рогов // Вестник южно-уральского государственного университета. Серия: Программирование. - 2016. -Т. 9, -№1.-С. 92-104.

[50] Мехтиев, А. Д. Применение сенсорных сетей для мониторинга и локального определения местоположения в промышленности / А. Д. Мехтиев и j. ip. / / Хабаршысы вест н ик « - 2013. - С. 68-62.

[51] Миниахметов, Р. М. Обзор алгоритмов локального позиционирования для мобильных устройств / Р. М. Миниахметов, А. А. Рогов, M. J1. Цымблер // Вестник ЮУрГУ. Серия "Вычислительная математика и информатика". - 2013. - Т. 2. - №2. - С. 83-96.

[52] Монаков, А. А. Теоретические основы радионавигации: учеб. пособие / А. А. Монаков // СПб.: ГУАП. - 2002.

[53] Морз, Ф. М. Методы исследования операций / Ф. Морз, Д. Е. Ким-белл. - Москва: Изд-во Наука, 1956.

[54] Мощевикин, А. П. Локация в беспроводных с6тях детчиков стан дарта nanoLOC (IEEE 802.15.4а) / А. П. Мощевикин, А. С. Галов, А. С. Волков // Информационные технологии. - 2011. - №8, - С. 13 47.

[55] Мощевикин, А. П. Точность расчета локации в беспроводных сетях датчиков стандарта nanoLOC / А. П. Мощевикин, А. С. Галов, А. С. Волков // Информационные технологии. - 2012. - №9. - С. 37-41.

[56] Овчинников, С. Системы позиционирования и мониторинга / С. Овчинников // Технологии и средства связи. - 2014. - №2. - С. 18-22.

[57] Ope, О. Теория графов / О. Ope. - Москва: Изд-во Мир, 1968. - 368 с.

[58] Петров, Е.А. Оптимизационная модель выбора битовых скоростей медиа-потоков / Е. А. Петров, А. А. Рогов, Р. В. Воронов //В сборнике: Научно-образовательная информационная среда XXI века. Материалы X Всероссийской научно-практической конференции. - Петрозаводск, - 2016. - С. 131-134.

[59] Покровская, О.О. Программа определения мест размещения базовых станций и построения карт уровня сигналов в локальных системах позиционирования / О. О. Покровская, Р. В. Воронов ! ! (^уВство о государственной регистрации программы для ЭВМ. Правообладатель: Петрозаводский государственный университет. Свидетельство №2014619815. Заявка №2014617433. Дата поступления 25.07.2014. Зарегистрировано в Реестре программ для ЭВМ 23.09.2014.

[60] Попков, В. К. Гиперсетевая технология оптимизации инженерных сетей в горной или пересеченной местности / В. К. Попков, Г. Ы. Токтошов // Вестник Бурятского государственного университета.

- 2010. - №9. - С. 276-282.

[61] Попков, В. К. Гиперсети и структурные модели сложных систем / В. К. Попков // Математические и имитационные модели сложных систем. С М-6. - Новосибирск, 1981. - С. 26-48.

[62] Попков, В. К. Математические модели живучести сетей связи / В. К. Попков. - Новосибирск: ВЦ СО АН СССР, 1990.

[63] Попков, В. К. Методологические вопросы оптимизации инженерных сетей на неоднородной территории / В. К. Попков, Г. Ы. Токтошов // Известия Томского политехнического университета. - 2010.

- Т. 317. - №5.

[64] Попков, В. К. Методы оптимизации структур зоновых сетей связи / В. К. Попков, С. Б. Кауль, М. И. Нечепуренко, Е. М. Букреев, А. И. Калеников. - Новосибирск: ИВМиМГ СО РАН, 1984.

[65] Попков, В. К. Применение теории гиперсетей в задачах оптимизации систем сетевой структуры / В. К. Попков // Проблемы оптимизации сложных систем: Материалы III Азиатской Международной школы семинара. - г. Бишкек, Кыргызская Республика, 1-12 июля 2007. - Новосибирск, 2007. - С. 87-92.

[66] Попков, В. К. Трудно решаемые задачи теории гиперсетей / В. К. Попков // Российская конференция "Дискретная оптимизация и исследование операций": Материалы конференции института математики. - Новосибирск, - 2007. - С. 69-73.

[67] Рогов, А. А. Задача выбора битовых скоростей медиапотоков / А.

A. Рогов, Р. В. Воронов, Е. А. Петров // Вестник Воронежского государственного технического университета. - 2017. - Т. 13. - №1.

- С. 18-21.

[68] Романовский, И. В. Алгоритмы решения экстремальных задач / И.

B. Романовский. - Москва: Изд-во Наука, 1977.

[69] Романовский, И. В. Дискретный анализ / И. В. Романовский. -СПб: Невский Д И йЛ 6 к т > 1999.

[70] Романовский, И. В. Субоптимальные решения / И. В. Романовский.

- Петрозаводск: Изд-во ПетрГУ, 1998.

[71] Савочкин, Д. А. Оптимизация размещения антенн для систем пространственной двумерной РНБ-.юки. П13ИЦ1П! / Д. А. Савочкин, Ю. Б. Гимпилевич // Радюелектрошка, шформатика, управлшия. -2015. - С. 7.

[72] Сачков, В. Н. Введение в комбинаторные методы дискретной математики / В. Н. Сачков. - Москва: Наука, 1982.

[73] Система локального позиционирования RealTrac [Электронный ресурс]. 2014. URL: http://rtlservice.com/technology/tehnologii pozicionirovaniya

[74] Система оперативного контроля местоположения людей в зданиях и сооружениях [Электронный ресурс]. Международная система диспетчеризации и мониторинга транспортных средств. 2014. URL: http://navitron.mobi/га/menuarticles /2010-04-09-15-28-27

[75] Сорокин, Ф. В. Методы решения задачи привязки трека к плану помещения / Ф. В. Сорокин, Р. В. Воронов // Современные научные исследования и инновации. - 2015. - №6-2 (50). - С. 19-28.

[76] Сорокин, Ф. В. Программа для тестирования алгоритмов привязки трека к плану помещения / Ф. В. Сорокин, Р. В. Воронов // Свидетельство о государственной регистрации программы для ЭВМ. Правообладатель: Петрозаводский государственный университет. Свидетельство №2015660321. Заявка №2015617204. Дата поступления 04.08.2015. Зарегистрировано в Реестре программ для ЭВМ 29.09.2015.

[77] Сорокин, Ф. В. Реализация фильтра частиц л .я привязки трб ка объекта к плану помещения / Ф. В. Сорокин, Р. В. Воронов j j (^у В ИДС'1'СЛ1) CT во о государственной регистрации программы для ЭВМ. Правообладатель: Петрозаводский государственный университет. Свидетельство №2016660280. Заявка №2016617596. Дата поступления 12.07.2016. Зарегистрировано в Реестре программ для ЭВМ 12.09.2016.

[78] Стёпкина, Т. С. Программа локации мобильных объектов на графе / Т. С. Стёпкина, Р. В. Воронов // Свидетельство о государственной регистрации программы для ЭВМ. Правообладатель: Петрозаводский государственный университет. Сви-Д6Т6ЛЬCTво №2017612248. Заявка №2016664625. Дата поступле-

ния 28.12.2016. Зарегистрировано в Реестре программ для ЭВМ 17.02.2017.

[79] Сухарев, А. Г. Курс методов оптимизации / А. Г. Сухарев, А. В. Тимохов, В. В. Федоров. - Москва: Изд-во Наука, 1986.

[80] Тимофеева, И. С. Программа оптимизации расположения точек доступа на графе / И. С. Тимофеева, Р.В. Воронов // Свидетельство о государственной регистрации программы для ЭВМ. Правообладатель: Петрозаводский государственный университет. Свидетельство №2015660455. Заявка №2015617194. Дата поступления 04.08.2015. Зарегистрировано в Реестре программ для ЭВМ 30.09.2015.

[81] Токтошов, Г. Ы. Сеточная аппроксимация элементов рельефа местности / Г. Ы. Токтошов // Информатика и проблемы телекоммуникаций: Материалы Российской научно-технической конференции. -Новосибирск. - 2009. - Т.1. - С. 23-24.

[82] Уилсон, Р. Введение в теорию графов / Р. Уилсон. - Москва: Мир, 1977.

[83] Утешев, А. Ю. Задача Ферма-Торричелли и ее развитие [Электронный ресурс] / А. Ю. Утешев / / URL: http://pmpu.ru / vf4 / algebra 2 / optimiz / distance / torri

[84] Фрэнк, Г. Сети, связи и потоки / Г. Фрэнк, И. Фриш. - Москва: Связь, 1978.

[85] Харари, Ф. Теория графов / Ф. Харари. - Москва: Мир, 1973.

[86] Хачатуров, В. Р. Комбинаторные методы и алгоритмы решения задач дискретной оптимизации большой размерности / В. Р. Хачатуров, В. Е. Веселовский, А. В. Злотов. - Москва: Наука, 2000.

[87] Чаженгин, Г. А. Исследование беспроводных систем и технологий позиционирования внутри помещений / Г. А. Чаженгин, Р. В. Воронов // В сборнике: Научно-образовательная информационная

XXI века. Материалы X Всероссийской научно-практической конференции. - Петрозаводск. - 2016. - С. 131-134.

[88] Чернецкий, В. И. Математическое моделирование стохастических систем / В. И. Чернецкий. - Петрозаводск, 1994.

[89] Щеголева, J1.B. Построение дорожного графа для маршрутизации мобильного робота в замкнутой системе коридоров / J1. В. Щего-лева, Р. В. Воронов // Инженерный вестник Дона. - 2015. - Т. 37. - №3. URL: http://ivdon.ru/ru/magazine/archive/n3y2015/3168

[90] Яглом, А. М. Вероятность и информация / А. М. Яглом, И. М. Яглом. - Москва: Наука, 1973.

[91] Abadi, М. J. Improving Heading Accuracy in Smartphone-based PDR Systems using Multi-Pedestrian Sensor Fusion /M.J. Abadi et al. // Electrical Engineering. - 2013. - V. 188. - p. 629-632.

[92] Aguilera, T. Acoustic local positioning system using an iOS device / T. Aguilera et al. // Indoor Positioning and Indoor Navigation (IPIN), 2013 International Conference on. - IEEE. - 2013. - p. 577-584.

[93] Amirhosseini, S. F. Stochastic Cloning Unscented Kalman filtering for pedestrian localization applications / S. F. Amirhosseini et al. // Indoor Positioning and Indoor Navigation (IPIN), 2013 International Conference on. - IEEE. - 2013. - p. 823-832.

[94] Ashkar, R. A low-cost shoe-mounted Inertial Navigation System with magnetic disturbance compensation / R. Ashkar et al. // Indoor Positioning and Indoor Navigation (IPIN), 2013 International Conference on. - IEEE. - 2013. - p. 833-842.

[95] Ata, O. W. An indoor propagation model based on a novel multi wall attenuation loss formula at frequencies 900 MHz and 2.4 GHz / O. W. Ata, M. S. Ala'Eddin, M. I. Jawadeh, A. I. Amro // Wireless Personal Communications. - 2013. - V. 69. - N 1. - p. 23-36.

[96] Barragán-Ramírez, G. A. The local metric dimension of strong product graphs / G. A. Barragán-Ramírez, J. A. Rodríguez-Velázquez // Graphs and Combinatorics. - 2016. - V. 32. - N. 4. - p. 1263-1278.

[97] Battiti, R. Optimal wireless access point placement for location-dependent services [Электронный ресурс] / R. Battiti, M. Brunato, A. Delai. 2003. lit t p: eprinls.biblio.uniln.il 189 1 DIT-03-052-withCover.pdf.

[98] Berman, P. Tight approximability results for test set problems in bioinformatics / P. Berman, B. DasGupta, M. Y. Kao // Journal of Computer and System Sciences. - 2005. - V. 71. - N. 2. - p. 145-162.

[99] Blankenbach, J. Position estimation using artificial generated magnetic fields / J. Blankenbach, A. Norrdine // Indoor Positioning and Indoor Navigation (IPIN), 2010 International Conference on. - IEEE. - 2010. - p. 1-5.

[100] BMP085 digital pressure sensor data sheet [Электронный ресурс] // 111 I ps: /www.sparkfun.com/datasheets/Components/General/BST-BMP085-DS000-05.pdf.

[101] Bollobas, B. Metric dimension for random graphs / B. Bollobas, D. Mitsche, P. Pralat // arXiv preprint arXiv:1208.3801. 2012.

[102] Bosch BMP085 Barometer Floating Point Pressure Calculations [Электронный ресурс] / / 111 I p: /wmrx00.sourceforge.net/Arduino/BMP085-Calcs.pdf.

[103] Caceres, J. On the metric dimension of cartesian products of graphs / J. Caceres et al. // SIAM Journal on Discrete Mathematics. - 2007. -V. 21. - N. 2. - p. 423-441.

[104] Chandrasekaran, G. Empirical Evaluation of the Limits of Localization Using Signal Strength: Beyond Cramer-Rao Bounds / G. Chandrasekaran, M. Ergin, J. Yang, S. Lui, Y. Chen, M. Gruteser, R. Martin // Proceedings of IEEE SECON. - 2004,- p. 406-414.

[105] Chartrand, G. Resolvability in graphs and the metric dimension of a graph / G. Chartrand, L. Eroh, M. A. Johnson, O. R. Oellermann // Discrete Applied Mathematic. - 2000. - V. 105. - p. 99-113.

[106] Chaudhry, M. A. Fault-tolerant metric and partition dimension of graphs / M. A. Chaudhry, I. Javaid, M. Salman // Utilitas mathematica. - 2010. - V. 83. - p. 187-199.

[107] Chehri, A. Geolocation for UWB Networks in underground mines / A. Chehri, P. Fortier, P. M. Tardif // Wireless and Microwave Technology Conference, 2006. WAMICON'06. IEEE Annual. - IEEE. - 2006. - p. 1-4.

[108] Chehri, A. UWB-based sensor networks for localization in mining environments / A. Chehri, P. Fortier, P. M. Tardif // Ad Hoc Networks. - 2009. - V. 7. - №. 5. - p. 987-1000.

[109] Chen, Y. A practical approach to landmark deployment for indoor localization / Y. Chen et al. // Sensor and Ad Hoc Communications and Networks, 2006. SECON'06. 2006 3rd Annual IEEE Communications Society on. - IEEE. - 2006. - V. 1. - p. 365-373.

[110] Chen, Y. Securing wireless localization against signal strength attacks. / Y. Chen - ProQuest, 2007.

[111] Chobtrong, T. Position Estimation Using a Low-cost Inertial Measurement Unit with Help of Kalman Filtering and Fastening-Pattern Recognition / T. Chobtrong, M. Haid, M. Kamil, E. Cfines // Indoor Positioning and Indoor Navigation (IPIN), 2013 International Conference on. - 2013. - p. 8-9.

[112] Chrysikos, T. Site-specific validation of ITU indoor path loss model at 2.4 GHz / T. Chrysikos, G. Georgopoulos, S. Kotsopoulos // IEEE International Symposium on a World of Wireless, Mobile and Multimedia Networks & Workshops. - 2009. - p. 1-6.

[113] Chung, J. Indoor location sensing using geo-magnetism / J. Chung et al. // Proceedings of the 9th international conference on Mobile systems, applications, and services. - ACM. - 2011. - p. 141-154.

[114] Dayekh, S. Cooperative geo-location in underground mines: A novel fingerprint positioning technique exploiting spatio-temporal diversity / S. Dayekh et al. // Personal Indoor and Mobile Radio Communications (PIMRC), 2011 IEEE 22nd International Symposium on. - IEEE. -2011. - p. 1319-1324.

[115] Deak, G. A survey of active and passive indoor localisation systems / G. Deak, K. Curran, J. Condell // Computer Communications. - 2012. - V. 35. - N. 16. - p. 1939-1954.

[116] Dempster, A. P. Maximum likelihood from incomplete data via the EM algorithm / A. P. Dempster, N. M. Laird, D. B. Rubin // Journal of the royal statistical society. Series B (methodological). - 1977. - p. 1-38.

[117] Tanigawa, M. Drift-free dynamic height sensor using MEMS IMU aided by MEMS pressure sensor / M. Tanigawa, H. Luinge, L. Schipper, et al. // 5th Workshop on Positioning, Navigation and Communication WPNC'08. - Hannover, Germany, March 27. - 2008. - p. 1911-196.

[118] Elnahrawy, E. The limits of localization using signal strength: A comparative study / E. Elnahrawy, X. Li, R. Martin // Proceedings of IEEE SECON. - 2004. - p. 406-414.

[119] Epstein, L. The (weighted) metric dimension of graphs: hard and easy cases / L. Epstein, A. Levin, G. J. Woeginger // Algorithmica. - 2015.

- V. 72. - N. 4. - p. 1130-1171.

[120] Fang, S. H. A novel access point placement approach for WLAN-based location systems / S. H. Fang, T. N. Lin // Wireless Communications and Networking Conference (WCNC), IEEE. - 2010. - p. 1-4.

[121] Faramondi, L. An enhanced indoor positioning system for first responders / L. Faramondi et al. // Indoor Positioning and Indoor Navigation (IPIN), 2013 International Conference on. - IEEE. - 2013.

- p. 237-244.

[122] Farkas, K. Optimization of Wi-Fi access point placement for indoor localization / K. Farkas, A. Huszak, G. Godor / / Journal I IT (Informatics k IT Today). - 2013. - V. 1. - N. 1. - p. 28-33.

[123] Fehr, M. The metric dimension of Cayley digraphs / M. Fehr, S. Gosselin, O. Oellermann // Discrete Mathematics. - 2006. - V. 306. -p. 31-41.

[124] Fernandez, S. Indoor location system based on ZigBee devices and metric description graphs / S. Fernandez et al. // Intelligent Signal Processing (WISP), 2011 IEEE 7th International Symposium on. -IEEE. - 2011. - p. 4-8.

[125] Ferreira, G. An implementation of ultrasonic time-of-flight based localization / G. Ferreira // 2nd International Conference on Wireless Communication in Underground and Confined Areas. - 2008.

[126] Galov, A. Bayesian filters for ToF and RSS measurements for indoor positioning of a mobile object / A. Galov, A. Moschevikin //

Proceedings of the International Conference on Indoor Positioning and Indoor Navigation (IPIN-2013), Montbeliard, France, October 28-31. -2013. - p. 310-317.

[127] Galov, A. S. Combination of RSS localization and ToF ranging for increasing positioning accuracy indoors / A. S. Galov, A. P. Moschevikin, R. V. Voronov // Proceedings of the 11th International Conference on ITS Telecommunications ITST-2011. - 2011. - p. 299304.

[128] Ghassemzadeh, S. S. Measurment and modeling of an ultra-wide band width indoor chanel / S. S. Ghassemzadeh, R. Jana, C. W. Rice, W. Turin, V. Tarokh // IEEE Tran. Commun. - 2004. - V. 52. - p. 17861796.

[129] Gondran, A. Wireless LAN planning: a didactical model to optimise the cost and effective payback / A. Gondran et al. // International Journal of Mobile Network Design and Innovation. - 2007. - V. 2. - N. 1. - p. 13-25.

[130] Gray, R. A. An integrated GPS/INS/baro and radar altimeter system for aircraft precision approach landings / R. A. Gray, P. S. Maybeck // Proceedings of the IEEE 1995 National Aerospace and Electronics Conference NAECON 1995. - Dayton, OH, USA. - 1995. - V. 1. - p. 161-168.

[131] Groves, P. D. Principles of GNSS, Inertial, and Multisensor Integrated Navigation Systems / P. D. Groves // Atrech House. - 2008.

[132] Hafner, P. Evaluation of smartphone-based indoor positioning using different Bayes filters / P. Hafner et al. // Indoor Positioning and Indoor Navigation (IPIN), 2013 International Conference on. - IEEE. - 2013. - p. 452-461.

[133] Harary, F. On the metric dimension of a graph / F. Harary, R. A. Melter // Ars Combinatoria. - 1976. - V. 2. - p. 191-195.

[134] Hassan, A. Advanced Location-Based Technologies and Services / A. Hassan // Boca Raton, Florida: CRC Press. - 2013.

[135] Hauptmann, M. Approximation complexity of metric dimension problem / M. Hauptmann, R. Schmied, C. Viehmann // Journal of Discrete Algorithms. - 2012. - V. 14. - p. 214-222.

[136] Hawkins, W. Vehicle localization in underground mines using a particle filter / W. Hawkins, B. L. F. Daku, A. F. Prugger // Electrical and Computer Engineering, 2005. Canadian Conference on. IEEE. - 2005.

- p. 2159-2162.

[137] Heckman, D. A tutorial on learning with bayesian networks / D. Heckman // Microsoft Research, Tech. Rep. MSR-TR-95-06, March 1995.

[138] Hellmers, H. An IMU/magnetometer-based Indoor positioning system using Kalman filtering / H. Hellmers et al. // Indoor Positioning and Indoor Navigation (IPIN), 2013 International Conference on. IEEE. -2013. - p. 896-904.

[139] Hernando, C. Fault-tolerant metric dimension of graphs / C. Hernando, M. Mora, P. J. Slater, D. R. Wood // Proc. Internat. Conf. Convexity in Discrete Structures, Ramanujan Math. Society Lecture Notes. - 2008.

- N 5. - p. 81-85.

[140] Imran, M. On dimensions of some infinite regular graphs generated by infinite hexagonal grid / M. Imran // Utilitas Mathematica. - 2013. -V. 92. - p. 3-15.

[141] Javaid I., Salman M., Chaudhry M. A., Shokat S. Fault-tolerance in resolvability // Utilitas Mathematica. - 2009. - V. 80. - p. 263-275.

[142] Ji, Y. Optimal sniffers deployment on wireless indoor localization / Y. Ji, S. Biaz, S. Wu, B. Qi // Computer Communications and Networks. ICCCN 2007. Proceedings of 16th International Conference on. - IEEE. - 2007. - p. 251-256.

[143] Kamil, M. Reference Navigation System Based in WI-FI Hotspots for Integration with Low-Cost Inertial Navigation System / M. Kamil, P. Devaux, M. Haid, T. Chobtrong, E. Gimes // Indoor Positioning and Indoor Navigation (IPIN), 2013 International Conference on. - 2013. p. 10-13.

[144] Kazakovtsev, L. Access points placement as a discrete optimization problem / L. Kazakovtsev // arXiv preprint arXiv: 1208.6363. - 2012.

[145] Khider, M. Characterization of planar-intensity based heading likelihood functions in magnetically disturbed indoor environments / M. Khider et al. // Indoor Positioning and Indoor Navigation (IPIN), 2013 International Conference on. - IEEE. - 2013. - p. 860-869.

[146] Khuller, S. Landmarks in graphs / S. Khuller, B. Raghavachari, A. Rosenfeld // Discrete Applied Mathematics. - 1996. - V. 70. - N 3. -p. 217-229.

[147] Kim, T. Cell planning for indoor object tracking based on RFID / T. Kim, J. Shin, S. Tak // Mobile Data Management: Systems, Services and Middleware, 2009. MDM'09. Tenth International Conference on. -IEEE. - 2009. - p. 709-713.

[148] Klein, D. J. A comparison on metric dimension of graphs, line graphs, and line graphs of the subdivision graphs / D. J. Klein, E. Yi // European Journal of Pure and Applied Mathematics. - 2012. - V. 5. -N 3. - p. 302-316.

[149] Kok, M. MEMS-based inertial navigation based on a magnetic field map / M. Kok et al. // Acoustics, Speech and Signal Processing (ICASSP),

2013 IEEE International Conference on. - IEEE. - 2013. - p. 64666470.

[150] Koski, L. Indoor positioning using WLAN coverage area estimates / L. Koski, T. Peral-,■ R. Piché // International Conference on Indoor Positioning and Indoor Navigation (IPIN), September 2010.

[151] Krause, A. A note on the budgeted maximization of submodular functions. / A. Krause, C. Guestrin - 2005.

[152] Krause, A. Near-optimal nonmyopic value of information in graphical models / A. Krause, C. E. Guestrin // arXiv preprint arXiv: 1207.1391. - 2012.

[153] Krause, A. Near-optimal sensor placements in Gaussian processes: Theory, efficient algorithms and empirical studies / A. Krause, A. Singh, C. Guestrin // Journal of Machine Learning Research. - 2008. - V. 9. - N. 2. - p. 235-284.

[154] Kuziak, D. Closed formulae for the strong metric dimension of lexicographi / D. Kuziak, I. G. Yero, J. A. Rodríguez-Velázquez // Discussiones Mathematicae Graph Theory. - 2016. - V. 36. - N. 4. -p. 1051-1064.

[155] Kuziak, D. On the strong metric dimension of the strong products of graphs / D. Kuziak, I. G. Yero, J. A. Rodríguez-Velázquez // Open Mathematics. - 2015. - V. 13. - N. 1.

[156] Koppe, E. Enhancement of the automatic 3D calibration for a multisensor system / E. Koppe et al. // Indoor Positioning and Indoor Navigation (IPIN), 2013 International Conference on. - 2013. - p. 5859.

[157] Li, B. How feasible is the use of magnetic field alone for indoor positioning? / B. Li et al. // Indoor Positioning and Indoor Navigation (IPIN), 2012 International Conference on. - IEEE. - 2012. - p. 1-9.

[158] Liao, L. Two birds with one stone: Wireless access point deployment for both coverage and localization / L. Liao, W. Chen, C. Zhang, L. Zhang, D. Xuan. W. Jia // IEEE transactions on Vehicular Technology. - 2011. - V. 60. - N. 5. - p. 2239-2252.

[159] Liao, L. Voronoi tracking: Location estimation using sparse and noisy sensor data / L. Liao L. et al. // Intelligent Robots and Systems, 2003.(IR()S 2003). Proceedings. 2003 IEEE/RSJ International Conference on. - IEEE. - 2003. - V. 1. - p. 723-728.

[160] Liu, H. Survey of wireless indoor positioning techniques and systems / H. Liu et al. // Systems, Man, and Cybernetics, Part C: Applications and Reviews, IEEE Transactions on. - 2007. - V. 37. - N. 6. - p. 1067-1080.

[161] Li, D. Measurement-based access point deployment mechanism for indoor localization / D. Li, B. Zhang, K. Huang, C. Li // Global Communications Conference (GLOBECOM), 2015 IEEE. - IEEE. -2015. - p. 1-6.

[162] Li, X. A grid graph-based model for the analysis of 2D indoor spaces / X. Li, C. Claramunt, C. Ray // Computers, Environment and Urban Systems. - 2010. - V. 34. - N 6. - p. 532-540.

[163] Manjusha, R. Metric dimension and uncertainty of traversing robots in a network / R. Manjusha, A. Sunny Kuriakose // International Journal on Applications of Graph Theory in Wireless Ad hoc Networks and Sensor Networks (GRAPH-HOC). - 2015. - V. 7. - N. 2/3.

[164] Manuel, P. On minimum metric dimension of honeycomb networks / P. Manuel et al. // Journal of Discrete Algorithms. - 2008. - V. 6. -N. 1. - p. 20-27.

[165] Maximov, V. Survey of Accuracy Improvement Approaches for Tightly Coupled ToA/IMU Personal Indoor Navigation System / V. Maximov,

0. Tabarovsky // International Conference on Indoor Positioning and Indoor Navigation. - 2013. - V. 28. - p. 31-34.

[166] Melter, R. A. Metric bases in digital geometry / R. A. Melter, I. Tomescu // Computer Vision, Graphics, and Image Processing. - 1984. - V. 25. - N. 1. - p. 113-121.

[167] Miao, Z. Robust height tracking by proper accounting of nonlinearities in an integrated UWB/MEMS-based-IMU/baro system / Z. Miao, A. Vydhyanathan, A. Young, H. Luinge // Proceedings of the Position Location and Navigation Symposium (PLANS), 2012 IEEE/ION. -Myrtle Beach, SC, USA. - 2012. - p. 414-421.

[168] Mikov, A. G. A Localization System Using Inertial Measurement Units from Wireless Commercial Hand-held Devices / A. G. Mikov, A. P. Moschevikin, A. A. Fedorov, A. Sikora // Proceedings of the International Conference on Indoor Positioning and Indoor Navigation (IPIN-2013), Montbeliard, France. - 2013. - p. 857-863.

[169] Mirowski, P. SignalSLAM: simultaneous localization and mapping with mixed WiFi, Bluetooth, LTE and magnetic signals / P. Mirowski et al. // Indoor Positioning and Indoor Navigation (IPIN), 2013 International Conference on. - IEEE. - 2013. - p. 357-357.

[170] Molisch, A. F. IEEE 802.15.4a channel model-final report / A. F. Molisch, K. Balakrishnan, C. C. Chong, S. Emami, A. Fort, J. Karedal, H. Schantz, U. Schuster // Tech. Rep., Document IEEE 802.1504-0062-02-004a. - 2005.

[171] Molisch, A. F. Ultrawideband Propagation Chanels - Theory, Measurment, and Modeling / A. F. Molisch // IEEE Transactions on Vehicular Tecnology. - 2005. - V. 54. - N. 5. - p. 1528-1545.

[172] Moschevikin, A. RealTrac technology at the EvAAL-2013 competition / A. Moschevikin, R. Voronov et al. // Journal of Ambient Intelligence and Smart Environments. - 2015. - V. 7. - No. 3. - p. 353-373.

[173] Moschevikin, A. The Impact of NLOS Components in Time-of-Flight Networks for Indoor Positioning Systems / A. Moschevikin, A. Galov, S. Reginya et al. // The 7th IEEE International Conference on Intelligent Data Acquisition and Advanced Computing Systems, IDAACS-2013. Piscataway: IEEE. - 2013. September, p. 2-6.

[174] Moschevikin, A. Realtrac technology overview / A. Moschevikin, A. Galov, A. Soloviev, A. Mikov, A. Volkov, S. Reginya // Evaluating AAL Systems Through Competitive Benchmarking (ser. Communications in Computer and Information Science), Eds. Springer Berlin Heidelberg. - 2013, V. 386, p. 60-71. [Online]. Available: http://dx.doi.org/10.1007/978-3-642-41043-7 6

[175] Moschevikin, A. Using Pressure Sensors for Floor Identification in Wireless Sensors Networks / A. Moschevikin, R. Voronov, A. Galov, A. Soloviev // Proceedings of the 1st IEEE International Symposium on Wireless Systems within the Conferences on Intelligent Data Acquisition and Advanced Computing Systems IDAACS-SWS, Offenburg, Germany. - 2012, - p. 2-6.

[176] Namuduri K. Dynamic WiFi fingerprinting indoor positioning system / K. Namuduri. 411c. - University of North Texas. - 2014.

[177] Nanotron Technology GmbH // http://www.nanotron.com

[178] Nemhauser, G. L. An analysis of approximations for maximizing submodular set functions / G. L. Nemhauser, L. A. Wolsey, M. L. Fisher // Mathematical Programming. - 1978. - V. 14. - N. 1. - p. 265-294.

[179] Nurminen, H. Motion model for positioning with graph-based indoor map / H. Nurminen et al. // Indoor Positioning and Indoor Navigation (IPIN), 2014 International Conference on. - IEEE. - 2014. - p. 646-655.

[180] Hahnel, B. F. D. Gaussian processes for signal strength-based location estimation B. F. D. Hahnel, D. Fox // Proceeding of Robotics: Science and Systems. - 2006.

[181] Oellermann, 0. The strong metric dimension of graphs and digraphs / 0. Oellermann, J. Peters-Fransen // Discrete Applied Mathematics. -2007. - N. 155. - p. 356-364.

[182] Okamoto, F. The local metric dimension of a graph / F. Okamoto, B. Phinezy, P. Zhang // Mathematica Bohemica. - 2010. - V. 135. - N.

3. - p. 239-255.

[183] Otsason, V. Accurate GSM indoor localization / V. Otsason, A. Varshavsky, A. LaMarca, E. de Lara // UbiComp 2005 / Lecture Notes Computer Science, Springer-Varlag. - 2005.

[184] Pei, Z. Anchor-free localization method for mobile targets in coal mine wireless sensor networks / Z. Pei et al. // Sensors. - 2009. - V. 9. - N.

4. - p. 2836-2850.

[185] Pereira, F. Accurate positioning in underground tunnels using Software-Deiined-Radio / F. Pereira, C. Theis, S. R. Cunha // Indoor Positioning and Indoor Navigation (IPIN), 2013 International Conference on. -2013. - p. 635-640.

[186] Qian, J. An improved indoor localization method using smartphone inertial sensors / J. Qian et al. // Indoor Positioning and Indoor Navigation (IPIN), 2013 International Conference on. - IEEE. - 2013. - p. 1-7.

[187] Radu, V. Indoor smartphone localization via activity aware pedestrian dead reckoning with selective crowdsourced WiFi fingerprinting / V.

Radii. M. K. Marina // Indoor Positioning and Indoor Navigation (IPIN), 2013 International Conference on. - IEEE. - 2013. - p. 553-562.

[188] Raj, F. S. On the metric dimension of few network sheets / F. S. Raj, A. George // Robotics, Automation, Control and Embedded Systems

- RACE 2015. International Conference on Robotics. IEEE. - 2015. p. 1-6.

[189] Robertson, P. Simultaneous localization and mapping for pedestrians using distortions of the local magnetic field intensity in large indoor environments / P. Robertson et al. // Indoor Positioning and Indoor Navigation (IPIN), 2013 International Conference on. - IEEE. - 2013.

- p. 925-934.

[190] Rodriguez-Velazquez, J. A. On the (adjacency) metric dimension of corona and strong product graphs and their local variants: combinatorial and computational results / J. A. Rodriguez-Velazquez, H. Fernau // arXiv preprint arXiv: 1309.2275. - 2013.

[191] Rodriguez-Velazquez, J. A. The metric dimension of strong product graphs / J. A. Rodriguez-Velazquez, D. Kuziak, I. G. Yero, J. M. Sigarreta // Carpathian Journal of Mathematics - 2015. V. 31. - N. 2, p. 261-268.

[192] Russ, J. A. Mutual information based tracking with mobile sensors J. A. Russ // ^HCCCpTSiT pi 51 - Massachusetts Institute of Technology. -2010.

[193] Sagawa, K. Classification of human moving patterns using air pressure and acceleration / K. Sagawa, T. Ishihara, A. Ina, H. Inooka // Proceedings of the 24th Annual Conference of the IEEE Industrial Electronics Society IECON'98. - Aachen, Germany. - 1998. - Vol. 2. -p. 1214-1219.

[194] Satsangi, Y. Exploiting submodular value functions for faster dynamic sensor selection: Extended version / Y. Satsangi et al. // IAS technical reports. - 2014. - N. IAS-UYA-11-02.

[195] Savic, V. Simultaneous sensor localization and target tracking in mine tunnels / V. Savic, H. Wymeersch, E. G. Larsson // Information Fusion (FUSION), 2013 16th International Conference on. - IEEE. - 2013. -p. 1427-1433.

[196] Sebo, A. On metric generators of graphs / A. Sebo, E. Tannier // Mathematics of Operations Research. - 2004. - V. 29. - N. 2. - p. 383 393.

[197] Seco, F. Joint estimation of indoor position and orientation from RF signal strength measurements / F. Seco, A. R. Jimenez, F. Zampella // Indoor Positioning and Indoor Navigation (IPIN), 2013 International Conference on. - IEEE. - 2013. - p. 78-85.

[198] Sharma, D. On Greedy Maximization of Entropy / D. Sharma, A. Kapoor, A. Deshpande // ICML. - 2015. - p. 1330-1338.

[199] Slater, P. J. Leaves of trees / P. J. Slater // Proc. 6th Southeastern Conference on Combinatorics, Graph Theory, and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1975), Congressus Numerantium 14, Winnipeg: Utilitas Math. - 1975. - p. 549-559.

[200] Slater, P.J. Dominating and reference sets in a graph / P.J. Slater // J. Math. Phys. Sci. - 1988. - V. 22. p. 445-455.

[201] Tolkiehn, M. Direction sensitive fall detection using a triaxial accelerometer and a barometric pressure sensor / M. Tolkiehn, L. Alallah. B. Lo, Y. Guang-Zhong // Engineering in Medicine and Biology Society: Annual International Conference of the IEEE EMBC. - Boston, MA, USA. - 2011. - p. 369-372.

[202] Under, J. Deploying License-free Wireless Wide-area Networks / J. Under // Indianapolis, Indiana: Cisco Press. - 2004.

[203] Vandermeulen, D. Indoor localization using a magnetic flux density map of a building / D. Vandermeulen, C. Vercauteren, M. Weyn // The Third International Conference on Ambient Computing, Applications, Services and Technologies. Porto: I ARIA. - 2013. - p. 42-49.

[204] Vilovic, I. Location optimization of WLAN access points based on a neural network model and evolutionary algorithms / I. Vilovic, N. Burum // Automatika: casopis za automatiku, mjerenje, elektroniku, racunarstvo i komunikacije. - 2015. - V. 55. - N. 3. - p. 317-329.

[205] Wang, C. S. Goal-programming-driven genetic algorithm model for wireless access point deployment optimization / C. S. Wang, C. T. Chang // Mathematical problems in engineering. - 2012. - V. 2012.

[206] Weiszfeld, E. Sur le point pour lequel la somme des distances de n points donnés est minimum / E. Weiszfeld // Tohoku Math. Journal. - 1937. - V. 43. - p. 355-386.

[207] Wen, Y. Fundamental limits of RSS fingerprinting based indoor localization / Y. Wen et al. / / Computer Communications (INFOCOM), 2015 IEEE Conference on. - IEEE. - 2015. - p. 24792487.

[208] Werner, M. Indoor Location-Based Services: Prerequisites and Foundations / M. Werner. - Springer, 2014.

[209] Widmann, D. Characterization of in-tunnel distance measurements for vehicle localization / D. Widmann et al. // Wireless Communications and Networking Conference (WCNC), 2013 IEEE. - IEEE. - 2013. -p. 2311-2316.

[210] Zejnilovic, S. Extending the metric dimension to graphs with missing edges / S. Zejnilovic, D. Mitsche, J. Gomes, B. Sinopoli // Theoretical Computer Science. - 2016. - V. 609. - p. 384-394.

[211] Zhang, H. Robotic mapping assisted by local magnetic field anomalies / H. Zhang, F. Martin // Technologies for Practical Robot Applications (TePRA), 2011 IEEE Conference on. - IEEE. - 2011. - p. 25-30.