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

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

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

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

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

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

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

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

Пусть S — подмножество вершин графа V , представляющих стены помещения, и — подмножество вершин графа V, представляющих непосредственно зоны самого помещения. Очевидно, чтоS^U=V . Пусть 1 - длина зоны помещения. Вес ребра графа Gзависит от того, какие вершины он соединяет. Рассмотрим всё случаи смежных вершин:
1) Если ребро связывает щ gU и u2 gU по вертикали или горизонтали, то w (u u) l ;
w (u1 u2)=lV2 ,
2) Если ребро связывает щ gU и u2 gU по диагонали, то
3) Если ребро связывает u gU и s е S по вертикали или горизонтали, то w(us) =1^ *(1 + k), где k - это коэффициент прохождения через стену определенного материала;
l * л/2
4) Если ребро связывает u gU и s е S по диагонали, то w(us) = —-— *(1 + k);

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

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

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

Алгоритм полного перебора для задачи определения метрической размерности 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 THENBREAK;
ENDFOR

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

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

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

Процедура HAVEUNIQUEROWS(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, представлены в таблице. Из таблицы видно, что эвристический алгоритм для помещений с простой конфигурацией и при достаточно большомрадиусе действия базовых станций, справляется с задачей расстановки базовых станций также, как и алгоритм полного перебора.

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

И. С. Андреева