BC/NW 2012; №2 (21):4.3
МЕТОДЫ ПОЗИЦИОНИРОВАНИЯ
АБОНЕНТОВ ВНУТРИ ПОМЕЩЕНИЙ, ОСНОВАНЫЕ НА РАДИООТПЕЧАТКАХ (LOCATION
FINGERPRINTING METHODS)
Курдин В.А., Шарапов А.П.
В настоящее время происходит активное развитие систем определения местонахождения абонента, или позиционирования. Одним из основных способов решения задачи позиционирования является использование систем спутникового позиционирования (GPS, ГЛОНАСС и др.), которые активно развиваются: разрабатывается новое абонентское оборудование, на орбиту выводятся новые спутники и т.п. Недостатком спутниковой навигации является затрудненная связь со спутниками в помещениях (особенно в многоэтажных зданиях), а также отсутствие сигнала от них под поверхностью земли, например, в шахтах.
Поэтому для позиционирования абонента, находящегося внутри помещения (indoor positioning methods), используются другие методы. Эти методы можно условно разделить на две группы: методы, для работы которых необходимо дополнительное оборудование, и методы, работающие в рамках существующей инфраструктуры, основной задачей которой не является позиционирование.
Методы первой группы требуют развертывания на территории, на которой предполагается осуществлять позиционирование абонентов, отдельной сети приемопередатчиков, осуществляющих связь с носимыми абонентами портативными радиомаяками или их аналогами. Так, система Active Badge [1] предполагает наличие у каждого абонента инфракрасного (ИК) передатчика, передающего каждые 10 секунд свой идентификатор, который принимают расположенные на территории предприятия ИК-приемники. В системах Active Bat и Cricket вместо инфракрасных сигналов используется ультразвук, в связи с чем достигается большая точность позиционирования.
Более предпочтительным выглядит использование для позиционирования уже существующего оборудования. Так, в последнее время широкое распространение получили системы позиционирования абонента беспроводной Wi-Fi-сети, основной задачей которой является обеспечение передачи данных (интернет). Сходным образом можно построить системы позиционирования абонентов беспроводных сетей стандарта 4G (Wi-MAX), систем радиосвязи стандарта DECT и т.д. В подобных системах используются методы определения местонахождения абонента по радиоотпечаткам (location fingerprinting methods), которые основаны не на измерении расстояния между абонентом и базовой станцией, а на анализе величин RSS, измеренных в различных точках помещения. Методы позиционирования по радиоотпечаткам обеспечивают определение местонахождения абонента даже в очень сложных условиях, так как используют не модель распространения сигнала, а базу данных предварительно выполненных измерений [4].
Определение местонахождения по радиоотпечаткам основано на измерении показателя, называемого уровнем принимаемого сигнала (Received Signal Strength, RSS). Измерение RSS является стандартной процедурой для большого количества мобильных устройств, так как оно необходимо для их нормальной работы. Так, абонентское оборудование стандарта 802.11 (Wi-Fi) имеет возможность вывода информации об уровне сигнала от любой из доступных точек доступа для того, чтобы пользователь мог принять решение о выборе одной из них. Другим примером может служить тот факт, что радиотелефоны стандарта DECT пользуются показаниями RSS от разных базовых станций для реализации алгоритма хэндовера (подключения к базовой станции с наибольшим уровнем сигнала) [1]. Для простоты изложения под базовыми станциями (БС) далее будем понимать собственно базовые станции в телекоммуникационном оборудовании стандарта DECT и точки доступа беспроводной сети Wi-Fi.
Метод позиционирования по радиоотпечаткам состоит из двух этапов (рис.1). На первом этапе, называемом этапом калибровки или офлайн этапом, в различных точках пространства, называемых точками калибровки (КТ) (calibration points, CPs, или reference points, RPs), происходит измерение RSS от различных базовых станций. Эти измерения называются радиоотпечатками и являются частью радиокарты. На этапе определения местоположения, или онлайн-этапе, для определения местонахождения абонентского устройства используется полученная ранее радиокарта. При этом происходит анализ вектора текущих измерений RSS, который включает в себя значения RSS для всех БС, находящихся в зоне радиовидимости абонентского устройства. Процесс непосредственно определения местонахождения допускает два основных подхода: детерминистский и вероятностный.
Рис. 1. Этапы позиционирования по радиоотпечаткам
При использовании детерминистского подхода к определению
местоположения (deterministic
location estimation) определяется мера сходства вектора текущих измерений с
каждым из радиоотпечатков. Одним из первых вопросов, встающих перед
исследователями в данном случае, является вопрос выбора мер расстояния, то есть
способа оценки меры сходства между двумя векторами. В большинстве работ для этих
целей служит p-норма,
или норма Гёльдера, вычисляемая по формуле 
, где p≥1. Частными
случаями, которые используются наиболее часто, являются расстояние Манхэттена (p=1) и евклидово расстояние (p=2), а
также максимум-норма (p=∞, 
). В ряде случае используется также расстояние
Махаланобиса, при вычислении которого учитывается корреляция между случайными
величинами. Вычисляется расстояние Махаланобиса по формуле 
, где S – матрица ковариации показаний
RSS различных БС [2].
После нахождения расстояния между вектором текущего измерения и радиоотпечатком каждой из точек калибровки, необходимо определить текущие координаты. Основными методами, используемыми для этой цели, являются методы нахождения одного ближайшего соседа, K ближайших соседей, а также метод нахождения K ближайших соседей с использованием весовых коэффициентов. При использовании метода нахождения ближайшего соседа (nearest neighbor method, NN), производится поиск одного радиоотпечатка, наиболее близкого к вектору текущих измерений, и принимается решение, что текущие координаты абонентского устройства совпадают с координатами соответствующей точки калибровки. В методе K ближайших соседей (K-nearest neighbor method, KNN), частным случаем которого и является метод NN, находится K таких радиоотпечатков, а координаты вычисляются как среднее арифметическое координат соответствующих точек калибровки. Наконец, метод нахождения K ближайших соседей с использованием весовых коэффициентов (weighted K-nearest method, WKNN) отличается от метода KNN тем, что при вычислении координат вводятся весовые коэффициенты, позволяющие, например, уменьшить влияние на результат наиболее далеких из K соседей, увеличив влияние наиболее близких. В целом, методы KNN и WKNN обеспечивают бóльшую точность, особенно при K=3 или K=4 [5]. Но если точки калибровки расположены достаточно плотно, то метод NN в ряде случаев обеспечивает лучшую точность.
Как видно, при использовании детерминистского подхода используются лишь средние значения радиоотпечатков, то есть для одной точки калибровки хранится всего один вектор значений RSS. Исходный массив данных не используется.
При использовании вероятностного подхода к определению
местоположения (probabilistic location estimation) выборка измерений,
собранная на этапе калибровки, используется более эффективно. Идея заключается
в вычислении функции условного распределения вероятности нахождения абонента в
заданной точке пространства, если вектор текущих измерений RSS равен заданному [3]. Для этого
используется формула, полученная из теоремы Байеса: 
. Здесь l – вектор случайных
величин, задающий местоположение абонента, а r – вектор
случайных величин, содержащий показания RSS от различных БС.
Распределение p(l) называется априорной вероятностью нахождения в точке, определяемой координатами l. В ряде методов для упрощения предполагается, что априорная вероятность имеет равномерное распределение, то есть вероятность нахождения в любой точке пространства в границах системы позиционирования одинакова. Распределение p(r), показывающее вероятность получения заданного вектора текущих измерений, не зависит от переменной местоположения l и может быть опущено как нормализующая константа при условии, что нас интересуют не абсолютные, а относительные вероятности. Наконец, распределение p(r|l) называется функцией правдоподобия (likelihood function), т.к. показывает вероятность получения наблюдения r при условии, что абонентское устройство расположено в точке с координатами l. Получение данной функции является основной целью методов, относящихся к вероятностному подходу.
В целом, методы детерминистского подхода отличаются меньшей
вычислительной сложностью, хотя имеют свои недостатки по сравнению с вероятностным
подходом. Влияние, оказываемое на работу системы радиоотпечатками, измеренными
неверно в результате какого-либо сбоя, при использовании детерминистских
методов существенно возрастает, так как подобные выбросы могут оказать
существенное влияние на результаты усреднения. С другой стороны, правильный
выбор алгоритма усреднения может устранить эту проблему. Так, проведенное
авторами данной статьи в [6] исследование показало сильную зависимость
получаемой радиокарты от выбранного метода усреднения значений RSS. В результате был
предложен новый способ
для обработки измеренных значений RSS: вычисление средних значений среди наилучших
(метод гистограмм), который позволяет не учитывать ухудшения уровня RSS
из-за случайных помех. Согласно этому способу интервал, в котором могут изменяться
значения RSS (был выбран интервал от -10 до -109 дБм, хотя значения выше
-30 дБм практически нереализуемы на практике), разбивается на определенное
количество отрезков (например, 10). Далее подсчитывается доля значений,
попавших на первый отрезок (от -10 до -19 дБм включительно), на второй отрезок
(от -20 до -29 дБм) и так далее до последнего отрезка (от -100 до -109 дБм).
Для того чтобы определить интервал усреднения, необходимо выбрать минимальное
число расположенных подряд отрезков, сумма долей на которых меньше некоторой
граничной величины, например, 10%, при этом данные отрезки должны иметь
минимально возможные номера. Получившийся диапазон делится на такое же
количество отрезков, как и в первом случае, а затем на данном интервале точно
так же ищется диапазон для дальнейшего усреднения. В данном случае можно
провести аналогию с грубым и точным поиском, когда на первом этапе определяется
лишь интервал для дальнейшего допоиска, а на втором ищется уже сам результат.
После работы второго этапа алгоритма мы получаем диапазон для окончательного
усреднения.
На
рис.2 показаны результаты применения различных алгоритмов нахождения средних на
одном и том же наборе данных.
Рис. 2. Результаты
усреднения RSS от одной
БС
с помощью различных алгоритмов
Из графиков видно, что известные методы усреднения всегда дают на выходе заниженные значения уровня сигнала, что объясняется влиянием на них переотражений и помех. Медиана же, лучше отражая изменения уровня сигнала, все же слишком изменчива. В связи с этим для формирования радиокарты представляется оправданным использование предложенного метода усреднения, основанного на гистограммах. Этот метод, кроме того, позволяет резко снизить объём вычислений, выполняемых для позиционирования, что, в свою очередь, уменьшает скорость разряда аккумулятора абонентского устройства.
Также авторами данной статьи было проведено экспериментальное исследование возможности определения местонахождения абонента в системе доступа стандарта DECT [7]. Для определения текущих координат применялся метод дискриминантного анализа, использование которого можно отнести к детерминистскому подходу. Основной задачей метода является исследование групповых различий – различение (дискриминация) объектов по определенным признакам. Дискриминантный анализ позволяет выяснить, действительно ли группы различаются между собой, и если да, то каким образом (какие переменные вносят наибольший вклад в имеющиеся различия) [8]. Все процедуры дискриминантного анализа можно разбить на две группы: первая группа позволяет интерпретировать различия между имеющимися группами (сравнивая средние), вторая – проводить классификацию новых объектов в тех случаях, когда неизвестно заранее, к какому из существующих классов они принадлежат. Как видно, в этом алгоритм дискриминантного анализа схож с методами лоцирования по радиоотпечаткам.
Для проведения первой части дискриминантного анализа данные
подготавливаются следующим образом. Каждому экземпляру данных (вектору,
содержащему измерения RSS
от каждой из базовых станций) присваивается метка, содержащая информацию о
координатах точки, в которой производилось измерение. После выполнения этой
части дискриминантного анализа, одним из результатов работы алгоритма являются
коэффициенты функций классификации. Функции классификации предназначены для
определения того, к какому кластеру наиболее вероятно может быть отнесен каждый
объект. Число функций классификации равно количеству точек калибровки. Данные
функции имеют вид 
. Здесь индекс i
обозначает соответствующую КТ, а индексы 1, 2, ..., n
обозначают n различных БС; 
являются
константами для i-ой КТ, 
– весовые
коэффициенты для j-ой БС при
вычислении показателя классификации для i-ой
КТ; 
– наблюдаемое значение
RSS j-ой БС. Величина 
является результатом показателя
классификации. Индекс функции, имеющей максимальное значение, дает нам номер
КТ, координаты которой наиболее близки к текущим координатам абонента. По сути,
данный метод ближе всего к методу поиска ближайшего соседа, так как в
результате работы метода объект может быть отнесен только к одной из точек
калибровки, в отличие от метода KNN,
где координаты объекта, находящегося между КТ, будут вычислены как средние
координаты K ближайших
к нему точек калибровки.
В ходе исследований было выявлено, что алгоритм
дискриминантного анализа с вероятностью 99,9% определял номер комнаты, в
которой произведены измерения. Количество ошибок составило 0,0986%. Таким
образом, эксперименты показали возможность использования дискриминантного
анализа в задаче определения местоположения в системе связи стандарта DECT.
При разработке системы позиционирования, основанной на радиоотпечатках, возникают и другие задачи, выходящие за рамки данной статьи: исследование влияния сбоев и отказов в работе базовых станций на работу системы позиционирования в целом, переноса некоторых БС в другое место, появления новых БС.
Таким образом, позиционирование абонентов внутри помещений, основанное на радиоотпечатках, является сложной научно-технической задачей, решение которой требует больших усилий.
Литература
1. Hightower J., Borriello G. “Location systems for ubiquitous computing”. IEEE Computer, 1(34):57–66, August 2001.
2. Bahl P., Padmanabhan V.N. “Radar: An in-building RF-based user location and tracking system”. INFOCOM 2000. Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings. IEEE, 2(10): 775–784, March 2000.
3. Roos T., Myllymäki P., Tirri H., Misikangas P., Sievänen J. “A probabilistic approach to WLAN user location estimation”. International Journal of Wireless Information Networks, 9(3):155–163, July 2002.
4. Honkavirta V. “Location fingerprinting methods in wireless local area networks”. M.Sc. thesis, Tampere University of Technology, November 2008.
5. Li B., Salter J., Dempster A.G.,
Rizos C. “Indoor positioning techniques based on wireless LAN”. Technical
report,
6. Курдин В.А., Шарапов А.П. “Оценка уровня сигнала от базовых станций для использования в системе позиционирования абонентов”. Труды международной научно-технической конференции "Информационные средства и технологии". 16-18 октября 2007 года, в 3-х т.т. М., 2007. Т 1, стр.20-23.
7. Курдин В.А., Шарапов А.П. “Определение местонахождения абонента в системе радиодоступа стандарта DECT с помощью методов статистического анализа”. Труды международной научно-технической конференции "Информационные средства и технологии". 21-23 октября 2008 года, в 3-х т.т. М., 2008. Т 1, стр.58-61.
8. Ким Дж.-О., Мьюллер Ч.У., Клекка У.Р. и др. Факторный, дискриминантный и кластерный анализ. – М.: Финансы и статистика, 1989. – 215 с.