Точность расчета локации объекта в беспроводных сетях стандарта nanoLOC

04.12.2015

Измерение расстояний между двумя радиоузлами по стандарту IEEE 802.15.4a производится с помощью метода Round Trip Time (RTT). Радиоузлы обмениваются кадрами, фиксируя время отправления, обработки и приема кадров. На основании временных меток рассчитывается время распространения сигнала в эфире. На основании вычисленного времени распространения сигнала и константы скорости света рассчитывается расстояние между радиоузлами [1, 2].

В идеальных условиях (при прямолинейном распространении электромагнитной волны и при отсутствии ошибок измерений) измеренное расстояние будет равняться действительному. Однако на практике из-за отражений сигнала результат измерений расстояния будет завышен (сигнал распространяется не по прямой, – Non-Line Of Sight (NLOS).

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

Point-based и area-based подходы для определения локаций и их точность

Для определения местоположения локации можно пользоваться двумя подходами: point-based (определение вероятной точки, в которой находится объект) и area-based (определение вероятной области нахождения объекта) [4]. При использовании последнего возможны варианты в способе задания формы области, которая, как правило, характеризуется некоторым значением вероятности нахождения в ней объекта.

Поскольку в случае использования стандарта IEEE 802.15.4a область локации объекта может быть представлена областью пересечения окружностей с центрами в соответствующих базовых станциях и радиусами, равными измеренным расстояниям от базовых станций до объекта, то локацию удобно описывать с помощью area-based подхода. Эта область имеет стопроцентную вероятность нахождения в ней объекта, при условии, что все измерения от БС выполнены без ошибок (см. Рисунок 1).

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

Рисунок 1. Область локации объекта

Вероятную точку нахождения объекта внутри вероятной области локации можно рассчитать, например, с помощью метода триангуляции  (см. точку 2 на Рисунке 1). Этот способ расчета соответствует простой модели, в которой для любой БС вероятность нахождения объекта в точке расположенной внутри окружности соответствующей измерению расстояния до этой БС тем больше, чем ближе точка к центру окружности.

Другой способ расчета point-based-локации внутри вероятной области локации может быть основан на более сложной модели или использовать определенные из экспериментов эвристики, выдавая в качестве результата, например, точку 1 (см. Рисунок 1).

Оценку точности локации можно определить по-разному, в зависимости от того, какой подход используется для расчета, area-based или point-based:

1. размер зоны вероятного нахождения объекта (вероятность, с которой объект находится внутри зоны, задается заранее);
2. статистическая оценка разброса расчетов локации или кучность;
3. расстояние между действительным положением объекта на местности и рассчитанным.

Первая оценка применяется к area-based, а вторые две к point-based подходам.

Как обсуждалось выше, измеренные расстояния между базовой станцией и мобильным узлом в стандарте IEEE 802.15.4a всегда выше действительных. Это связано с отражениями электромагнитной волны от различных объектов окружения, в том числе от поверхности земли. Обычно разница между измеренным и действительным значениями расстояний между БС и объектом лежит в пределах от 1 до 10 метров, но в определенных случаях она может составлять значительно большие величины [5, 6].

Необходимо отметить, что завышенные измерения расстояний между мобильным объектом и базовой станцией в различной степени влияют на конечную точность определения локации объекта. Большое значение имеет положение мобильного объекта относительно базовых станций. Так, в [7] отмечено, что чем больше базовых станций задействовано при измерениях, тем больше вероятность того, что произойдет взаимное вычитание ошибок NLOS при вычислении локации (ситуация, когда базовые станции находятся вокруг объекта).

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

Различные оценки области локации area-based подхода и их точность

В случае area-based подхода важным является выбор простой оценки полученной области локации.

Рисунок 2. Возможные оценки области локации

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

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

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

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

В экспериментах, проводимых коллективом автором, в качестве оценки точности локации для area-based подхода чаще всего использовалась величина, равная квадратному корню из площади области локации, – это еще один вариант оценки точности area-based-локации.

Влияние завышенных измерений на оценку точности локации

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

Рисунок 3. Различия в относительном размере областей локаций

Точность измерения расстояния в отсутствии NLOS, составляет 1 метр [1, 2]. При условии корректной расстановки базовых станций на карте, в случае отсутствия NLOS получаем, что расстояние от вычисленной локации до каждой из окружностей не должно превышать 1 метра (см. Рисунок 3б). Однако при наличии ошибок в измерениях, связанных с отражениями сигналов, пересекающиеся окружности образуют некоторую достаточно большую область (см. Рисунок 3в), поскольку полученные измерения значительно больше действительных расстояний между БС и объектом.

Часто в нескольких циклах измерений для определенной БС не все из измерений являются значительно завышенными (по циклом измерений понимается процедура регистрации расстояний между мобильным узлом и несколькими БС). Для одного цикла измерений невозможно определить является ли данное измерение до БС завышенным. Можно определить факт завышения измерения для определенной БС при наличии минимум трех результатов циклов  измерений, в двух из которых измерения выполнены без ошибок для соответствующей БС. Оценить степень ошибки NLOS можно по размеру области локации относительно размеров всех окружностей, с помощью которых эта область образована.

Необходимо выделить ситуации, когда пользоваться area-based подходом не следует. Это зависит от взаимного расположения мобильного объекта и базовых станций [8]. Так, в случае, показанном на Рисунке 4, мобильный объект находится вне треугольника ∆ABC, образованного базовыми станциями.

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

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

Поэтому в ситуации, показанной на Рисунке 4, в качестве рассчитанной  локации объекта правильнее взять точку 1 (точку, близкую к месту пересечения окружностей), а область нахождения объекта определить областью пересечения колец, ограниченных измеренным R и истинным R₀ расстоянием до базовых станции (на Рисунке 4 для наглядности кольцо с шириной ∆R вырезано только для одной окружности с центром в точке А).

Рисунок 4. Возможные конфигурации области локации

Как видно, заштрихованная область явно меньше области, образованной пересечением окружностей. Другими словами область  пересечения окружностей не будет отражать реальной точности локации (area-based метрика будет явно завышена).

Обнаружение завышенных измерений в результатах одного цикла измерений

Ошибку, связанную с NLOS, можно легко обнаружить даже в результатах одного цикла измерений при наличии большого числа базовых станций, от которых одновременно измеряются расстояния до исследуемого объекта. В случае если окружность, связанная с измерением расстояния, не касается области локации объекта, а сама область находится внутри окружности, то измерение, очевидно, является завышенным, и его использование для определения point-based-локации на основе области локации представляет сложности (окружность с центром в точке A на Рисунке 5).

Рисунок 5. Завышенное измерение от БС «А»

Влияние заниженных измерений на оценку точности локации

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

На Рисунке 6 показано, как использование окружности, соответствующей заниженному измерению, дает в результате расчетов неправильную уменьшенную область локации объекта.

Рисунок 6. Искажения результатов расчета локаций из-за ошибок в измерении расстояний

При такого рода ошибках в измерениях расстояний от БС до объекта в большинстве случаев значение оценки точности area-based-локации (площадь области) будет меньше действительного (см. Рисунок 6), а сама область стопроцентного нахождения объекта получается «смещенной». Это смещение области локации, несмотря на то, что значение оценки точности area-based-локации будет меньше (точность якобы выше), может в действительности увеличить расстояние между действительным положением объекта и рассчитанным на основе этой области – значение оценки точности point-based-локации будет больше, что соответствует меньшей точности.

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

Интегральная точность расчета локаций при многократном измерении расстояний до покоящегося объекта

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

Чем выше выбирается вероятность, тем больше будет радиус окружности и меньше уровень значимости оценки. Зависимость между значением вероятности и радиусом нелинейная.

Рисунок 7. Интегральная точность расчета локаций при многократном измерении расстояний до покоящегося объекта

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

Интегральную оценку точности можно использовать вместо аналогичных area-based оценок, поскольку она является более устойчивой к выбросам. Кроме того, она является простой с точки зрения вычислений, а способ ее расчета не зависит от используемых алгоритмов расчета локации по набору измеренных расстояний от БС, что позволяет использовать ее для сравнения точности различных алгоритмов локаций.

Зависимость интегральной точности расчета локаций от количества измерений

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

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

Рисунок 8. Влияние выбора БС для измерения на область локации 

Слева показана ситуация, когда результатом расчета локации является точка 1 (есть измерение от базовой станции A, а от базовой станции Е измерение отсутствует), а справа – около точки 2. Таким образом, после накопления нескольких циклов измерений с различными наборами базовых станций в области вероятного нахождения объекта образуется два кластера точек (см. Рисунок 9).

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

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

Проверка точности расчета локаций

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

На практике [4, 9] для оценки точности локации часто используется эмпирическая функция распределения вероятности ошибки локации (см. Рисунок 10).

Рисунок 10. Функция распределения вероятности ошибки локации

Для нахождения такой функции определяется разница ∆R_err между измеренным значением и действительным положением радиоузла до БС. Эта разница соответствует значению абсолютной погрешности одного измерения. После накопления достаточного количества данных строится функция, по оси абсцисс которой откладывается величина ∆R_err, равная разности между истинным и рассчитанным положением объекта, а по оси ординат – значение равное доле измерений, для которых абсолютное значение ошибка измерения ∆R_err меньше заданной величины R. В качестве точности локации используется величина, соответствующая ошибке ∆R_err при заданной вероятности. Часто в качестве точности локации используют 50% и 75% квантили соответствующих эмпирических функций распределения [9].

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

Как показала практика, для коммерчески обоснованной конфигурации базовых станций на открытом пространстве с плотностью расположения на местности до 1 шт. / 1000 м² возможно достижение абсолютной точности позиционирования объекта до 1-2 метров. Для закрытых помещений в пределах зданий (плотность расположения БС в несколько раз выше) имеет смысл говорить лишь о надежном определении местоположения с точностью до комнаты.

Отметим, что для этих двух крайних случаев (открытые и закрытые пространства) для описания точности локации чаще всего применяются разные походы: point-based и area-based соответственно.