Задача локации мобильных объектов на графе

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

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

Целью моей работы является разработка алгоритма для такой системы.

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

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

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

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

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

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

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

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

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

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

Т. В. Стёпкина