Алгоритмы оптимальной расстановки базовых станций системы локации объекта в помещении

Алгоритмы оптимальной расстановки базовых станций системы локации объекта в помещении

Алгоритмы оптимальной расстановки базовых станций системы локации объекта в помещении

И. С. Андреева, студент, 5 курс, 2016 год, группа 22509

Научный руководитель — к. т. н., доц. Р. В. Воронов

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

В последнее время востребованными являются задачи определения местоположения какого-либо мобильного объекта в помещении. Локация объекта в помещении с помощью технологий спутниковых систем GPS, ГЛОНАСС или Beidou невозможна, так как они недоступны в помещении из-за различных преград — стен, мебели, перегородок и т. д.. По этой причине для определения местоположения объекта в помещении используются различные другие методы локации [1 – 2]. В данной работе рассматривается метод, основанный на определении мощности входного сигнала базовых станций беспроводной сети [3 – 4]. В данной работе система локации представляется множеством базовых станций, расставленных в помещении определенным образом, и устройством мобильного объекта, принимающим входные сигналы от установленных базовых станций и отправляющим их для обработки серверу.

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

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

На рис. 1 показан пример помещения, представленного в виде графа . Ширина помещения равна 5 метрам, длина — 7 метрам. Сторона квадрата равна 1 метру. Черными рёбрами показаны стены и внутренние перегородки помещения, кругами (вершины графа) обозначены зоны помещения.

Рис. 1. Представление помещения в виде графа ходов шахматного короля.

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

В ходе работы системы локации может возникнуть ряд проблем:

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

2. При недостатке базовых станций объект может оказаться в так называемой "слепой" зоне.

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

Пусть  — подмножество вершин графа , представляющих стены помещения,  — подмножество вершин графа , представляющих непосредственно зоны самого помещения. Очевидно, что. Пусть – длина зоны помещения. Вес ребра графа G зависит от того, какие вершины он соединяет. Рассмотрим всё случаи смежных вершин:

1) Если ребро связывает и по вертикали или горизонтали, то ;

2) Если ребро связывает и по диагонали, то ;

3) Если ребро связывает и по вертикали или горизонтали, то , где k – это коэффициент прохождения через стену определенного материала;

4) Если ребро связывает и по диагонали, то ;

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

Для решения поставленной задачи используется понятие метрической размерности и разрешающего множества вершин. Задача метрической размерности по [6] определяется следующим образом: “Дан неориентированный граф G = <V, E>, . Вершина позволяет отличить  от , если расстояние между вершинами  и  отличается от расстояния между вершинами  и ”. Разрешающее множество вершин — это подмножество , которое включает в себя все вершины . Метрическая размерность графа G (обозначаемая в данной работе как) – это мощность разрешающего множества. Таким образом, для решения поставленной задачи необходимо найти метрическую размерность  и разрешающее множество L.

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

Алгоритм полного перебора для задачи определения метрической размерности md и разрешающего множества L :

md = 0;

L = [ ];

sdmG = FIND_SHORTEST_DISTANCE_MATRIX(G);

sdmG' = SHORTEST_DISTANCE_MATRIX_FOR_U(sdmG);

FOR i = 1 to N DO

combs_i = COMBINATIONS(sdmG', i);

FOREACH comb_i in combs_i

IF HAVE UNIQUE ROWS(comb_i) THEN

md = i;

L = comb_i;

BREAK;

ENDIF

ENDFOREACH

IF md == i THEN BREAK;

ENDFOR

Процедура FIND_SHORTEST_DISTANCE_MATRIX(G) находит матрицу кратчайших расстояний для исходного графа G, представляющего помещение.

Процедура SHORTEST_DISTANCE_MATRIX_FOR_U(sdmG) выбирает из матрицы sdmG только те строки, которые относятся к .

Процедура COMBINATIONS(sdmG', i) генерирует комбинации длины i для матрицы sdmG'.

Процедура HAVE UNIQUE ROWS(comb_i) проверяет, чтобы все элементы (строки) в комбинации comb_i были отличны друг от друга.

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

Эвристический алгоритм для задачи определения метрической размерности md и разрешающего множества L :

md = 0

L = []

sdmG = FIND_SHORTEST_DISTANCE_MATRIX(G);

sdmG' = SHORTEST_DISTANCE_MATRIX_FOR_U(sdmG);

comb = []

WHILE NOT HAVE UNIQUE ROWS(comb)

FOREACH u in U

count_uv[u] = FIND_MAX_UNIQUE_VERTICES(u, sdmG')

v = VERTEX_WITH_MAX_COUNT_UNIQUE(count_uv)

ENDFOREACH

comb. append(sdmG'[v])

sdmG'.remove(comb)

ENDWHILE

L = comb

md = length(L)

Процедура FIND_MAX_UNIQUE_VERTICES(u, sdmG') находит максимальное число не повторяющихся расстояний от вершины u до всех остальных вершин в матрице кратчайших расстояний sdmG'.

Процедура VERTEX_WITH_MAX_COUNT_UNIQUE(count_uv) находит вершину, которая имеет максимальное число уникальных расстояний.

Результирующее множество — это наполняемое множество comb. Когда вершина включается в результирующее множество, из матрицы кратчайших расстояний sdmG' удаляются расстояния от этой вершины до всех остальных вершин.

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

	Количество установленных базовых станций при заданном радиусе действия R
R = 1 м	R = 2,5 м	R = 5 м	R = 7 м
Полный перебор	6	3	2	2
Эвристика	8	3	2	2

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

Список литературы

, , Мощевикин обработки данных распределенной сети датчиков давления для оценки относительной высоты мобильного узла // Современные проблемы науки и образования. 2013. №4.

2.  , , Стёпкина определения местоположения мобильных объектов в шахте // Современные проблемы науки и образования. 2014. №4.

Воронов задача локации мобильных объектов в помещениях [Текст] / // Инновационные технологии в науке и образовании : материалы III Междунар. науч.-практ. конф. (Чебоксары, 23 окт. 2015 г.) / редкол.: [и др.]. — Чебоксары: ЦНС «Интерактив плюс», 2015. — № 3 (3). — С. 183–185. — ISSN 2413-3981. , , “Динамическое создание карт уровня WiFi-сигналов для систем локального позиционирования”, Системы и средства информ., 24:1 (2014), 80–92 Chang G. J. Algorithmic aspects of domination in graphs //Handbook of combinatorial optimization. – Springer US, 1998. – С. 1811-1877. Epstein, L.; Levin, A.; Woeginger, G. J. The (Weighted) Metric Dimension of Graphs: Hard and Easy Cases [Электронный ресурс]: науч. статья/ Berlin Heidelberg, 2012.