Часть 1/3

Часть 3/3 (в процессе перевода)

III.  Проблемы многолучевой интерференции FTM и MUSIC

По данным Wi-Fi Alliance протокол FTM обеспечивает измерение расстояния с метровой точностью [11]. Однако недавнее исследование [13] показало, что, хотя это утверждение в целом верно для условий прямой видимости, но не относится к ситуациям вне прямой видимости (NLOS). На верхнем уровне проблема связана с наличием препятствий и многолучевости, присущих помещениям. Как показано на Рисунке 3, отраженный сигнал может быть мощнее, чем прямой, поэтому инициатор может посчитать длину траектории отраженного сигнала реальным расстоянием до ответчика.

Каким бы простым и ясным ни казалось это объяснение, действительность, особенно на реальном оборудовании, как будет продемонстрировано далее, более разнообразна. В работе [13] остались без ответа следующие вопросы:

1) какое влияние несколько экземпляров передаваемого сигнала и их относительная мощность оказывают на точность FTM, и

2) играют ли препятствия дополнительную роль в наблюдаемой неточности?

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

В итоге, учитывая, что ограничения FTM обусловлены многолучевой интерференцией, MUSIC может оказаться физическим методом разделения множественных траекторий и вычисления ToF прямой траектории. К сожалению, многочисленные исследования [6], [15], [16] показали, что он плохо работает с оборудованием Wi-Fi. Тем не менее, неизвестно, в какой степени MUSIC может помочь повысить точность FTM.

Чтобы ответить на эти вопросы, проведен анализ измерений с использованием стандартного оборудования (полное описание испытательного стенда см. в § V-B). Полученные результаты помогут разработать решение FUSIC, представленное в § IV.

A. Оценка проблемы

Прямая видимость. Чтобы установить точку отсчета, проведен анализ простого случая, при котором между инициатором и ответчиком имеется прямая видимость. Две станции размещаются в длинном коридоре, расстояние между ними измеряется с помощью FTM, при этом фактическое расстояние между ними изменяется от 1 до 60 м. Каждый эксперимент повторяется 5 раз, и в качестве выходных данных принимается среднее значение и стандартное отклонение результатов всех экспериментов. Как и ожидалось (Рисунок 4), FTM очень хорошо работает в этой ситуации со средней ошибкой оценки 0,76 м и 1,56 м для 90-го процентиля.

Препятствие на линии прямой видимости при наличии многолучевости. Для оценки точности FTM в условиях NLOS поставлен эксперимент, показанный на Рисунке 5a.

Две станции размещаются рядом с отражателем (стеной). Расстояние между двумя станциями L изменяется от 2 м до 10 м с шагом 2 м. Расстояние до отражателя D меняется между двумя значениями: 6 м и 8 м. Для каждого значения L и D проводятся эксперименты в двух разных вариантах: в прямой видимости и с человеком, находящимся между двумя станциями.

На Рисунке 5b показаны полученные результаты. Простейший вывод заключается в том, что FTM неточен при отсутствии прямой видимости: ошибка составляет до 3,03 м для D = 6 м и 7,62 м для D = 8 м.

Более внимательное наблюдение заключается в том, что в условиях NLOS FTM не рассчитывает длину траектории, по которой распространяется отраженный сигнал. На Рисунке 5b имеется геометрическая длина (теоретическое значение) траектории отражения, которую можно рассчитать благодаря частично управляемой среде распространения с единственным отражателем. Эти данные показывают, что полученное значение FTM находится между значением длины прямой траектории и теоретическим значением длины отраженной. В § III-B представлены результаты исследования основных причин этого наблюдения и использования полученных данных для разработки предлагаемого решения.

Препятствие на линии прямой видимости при отсутствии многолучевости. Аналогичный эксперимент проводится на открытом воздухе (отсутствие многолучевости), чтобы выяснить источник ошибок FTM в условиях NLOS: эффект многолучевой интерференции или относительная диэлектрическая проницаемость препятствия, находящегося на линии прямой видимости. С этой целью проводятся измерения FTM на разных расстояниях, изменяя при этом количество p людей между двумя устройствами, p ϵ 0,1,2,3. На Рисунке 6а показана экспериментальная установка с одним человеком, выступающим в качестве препятствия. В ходе этих экспериментов также фиксировались значения индикации уровня принимаемого сигнала (Received Signal Strength Indication, RSSI), чтобы установить зависимость уровня сигнала от количества людей, выступающих в качестве препятствий.

Как видно на Рисунке 6b, появление людей в качестве препятствий на линии прямой видимости оказывает незначительное влияние на расчет расстояния при отсутствии многолучевости. Это ясно показывает, что влияние относительной диэлектрической проницаемости незначительно, и полученный результат наблюдения при наличии отражателя связан, главным образом, с многолучевым распространением.

B. Причина проблемы в настройках многолучевости

Чтобы лучше понять основные причины низкой точности FTM при наличии многолучевости, проведен ряд экспериментов. В экспериментальную установку для исследования многолучевости (Рисунок 5а) помещаются до 8 добровольцев в качестве препятствий с L = 5м и D = 8м. Новым в этой серии экспериментов является то, что рядом с ответчиком находится компьютер, который оснащен сетевой картой Intel 5300 Wi-Fi, и на котором запущена утилита Linux CSI Tool [22] для сбора CSI во время проведения эксперимента.

Целью анализа является понимание результатов, получаемых FTM, на уровне сигнала. Два устройства FTM помещаются в три разных среды:

1) короткое расстояние (L = 2 м) и прямая видимость;

2) среднее расстояние (L = 6 м) и прямая видимость с простыми препятствиями (один человек);

3) дальнее расстояние (L = 10 м) и прямая видимость со сложными препятствиями (2 человека).

Кроме данных FTM, фиксируются CSI, и для анализа PDP используется метод MUSIC. Данные для первого варианта среды (Рисунок 7а) соответствуют ожиданиям: при наличии прямой видимости преобладает прямая траектория, а ошибка незначительна. Но данные на Рисунках 7b и 7c позволяют более глубоко понять суть происходящего в условиях NLOS. Точность FTM не является простой функцией наличия или отсутствия прямой видимости, а зависит от мощности прямого сигнала по отношению к отраженному. Если прямой сигнал близок по мощности отраженному сигналу (Рисунок 7b), то значение FTM все еще достаточно точно. Но если отраженный сигнал явно мощнее, то FTM становится неточным (Рисунок 7c).

Для дополнительного подтверждения полученных результатов проведены новая серия экспериментов, в которых изменяется уровень помех за счет 8 добровольцев, которые размещаются на линии прямой видимости между двумя устройствами FTM (L = 5 м и D = 8 м). На Рисунке 8 показана ошибка FTM как функция от значения, которое определено как коэффициент мощности сигнала.

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

где K – количество выявленных траекторий,

τ_k и P(τ_k) – ToF и мощность сигнала на траектории k (k = 1 соответствует прямой траектории) соответственно.

Как видно из графика на Рисунке 8, значение ошибок FTM зависит от мощности сигнала, который распространяется по прямой траектории, по сравнению с траекториями в условиях NLOS. Этот вывод используется в § IV как часть решения по корректировке значения FTM.

C. MUSIC и проблема неточности

Для оценки способности MUSIC точно рассчитывать ToF с помощью CSI, полученной из стандартных контроллеров сетевого Wi-Fi-интерфейса, Wi-Fi-станция и точка доступа (ТД) устанавливаются на расстоянии 5 м друг от друга. Станция передает серию из 100 пакетов, а точка доступа фиксирует CSI для каждого пакета. Эксперимент проводится в помещении с отражателем, находящимся на расстоянии 8 м от линии прямой видимости между станцией и точкой доступа. В этих условиях предполагается, что будут получены две траектории длиной 5 м и 16,8 м соответственно. К каждой записи CSI применяется метод MUSIC, а задержки первого и второго пика рассматриваются как расчетное значение ToF прямой и отраженной траекторий соответственно. ToF преобразуется в расстояние путем умножения на скорость света. На Рисунке 9 видно, что ошибка расчета расстояния значительна. Расчетное расстояние изменяется от 32 м до 61,8 м и в среднем примерно в 12 раз больше фактического.

Эти наблюдения согласуются с выводами в работах [6], [16]. Более того, значения, рассчитанные MUSIC, сильно отличаются от одного пакета к другому (стандартное отклонение 6,9 м), поэтому любая статическая калибровка, которая заключается в усреднении ошибки и ее учету при дальнейшем расчете ToF, не будет эффективной.

Тем не менее, на Рисунке 9 отражен очень интересный факт. Хотя расчетные длины прямых и отраженных траекторий не верны, разница расчетных длин двух траекторий одинакова для всех 100 пакетов и соответствует фактической разнице длин траекторий.

В этом конкретном эксперименте наблюдается почти постоянное смещение – 12,3 м. Этот же факт отражен и в других работах ([6], [7], [15], [16]). Решение, которое использует его в FUSIC, представлено в следующем разделе.

IV.  FUSIC

В этом разделе представлен FUSIC – алгоритм, объединяющий FTM и MUSIC и обеспечивающий точное определение местоположения Wi-Fi-источников даже при наличии многолучевости. В качестве входных данных FUSIC использует потенциально неверные выходное значение FTM и матрицу CSI и рассчитывает расстояние между двумя Wi-Fi-устройствами, поддерживающими FTM. FUSIC не требует внесения изменений в стандарт, в точки доступа и может быть реализован в виде приложения на пользовательском устройстве.

В FUSIC требуется решить две ключевые проблемы. Во-первых, необходимо установить факт ошибки FTM при расчете расстояния по траектории отраженного сигнала. Во-вторых, при установлении факта ошибки FTM требуется скорректировать ошибку, чтобы рассчитать правильную длину прямой траектории.

Основное знание, положенное в основу проекта FUSIC, заключается в том, что значение FTM вводит в заблуждение, если прямая траектория не является самой главной (§ III-B, Рисунок 7). MUSIC, с другой стороны, предоставляет профиль задержки мощности всех траекторий и позволяет выяснить доминирует ли прямая траектория. Слияние этих двух методов может предложить подход, способный определить некорректность значения FTM и при необходимости скорректировать конечное значение. Но превратить это знание в практическое решение двух ключевых проблем не так уж и просто. Во-первых, как показывают полученные данные (Рисунок 7b), FTM может точно рассчитывать расстояния, даже если прямая траектория не является доминирующей. В этом случае попытка корректировки может привести к ухудшению результата. Во-вторых, даже зная, что значение FTM ошибочно, не ясно, как его объединение с результатами MUSIC, показавшими себя крайне неточными, каким-то образом приведет к получению точных результатов. В Алгоритме 1 в обобщенном виде показано, как FUSIC решает все эти проблемы. Далее описаны основные пункты алгоритма.

A. Обнаружение необходимости корректировки FTM

Как показали полученные данные измерений в § III (Рисунок 7), вопрос о правильности значения FTM нельзя сводить к простому знанию того, является ли прямая траектория доминирующей или нет. Иногда прямая траектория не является доминирующей, а FTM дает точные результаты. Поэтому решить о корректировании значения FTM сложнее, чем может показаться на первый взгляд.

Для решения этой проблемы в FUSIC вводится новый параметр – R, который количественно определяет влияние прямой траектории на общий спектр MUSIC (строка 2, Алгоритм 1). R определяется по следующей формуле:

 Он аналогичен метрике lfactor, используемой в CUPID [17].

Если значение R превышает пороговое значение R_threshoid, то FUSIC не выполняет никакой коррекции (строка 4, алгоритм 1). В противном случае будет выполнен алгоритм коррекции, представленный в § IV-B. Выбор правильного значения для R_threshold зависит от решения интересного компромисса: если порог слишком низок, то FUSIC может изменить правильные значения FTM и привести к ненужным ошибкам. С другой стороны, если оно слишком велико, то FUSIC может не исправить ошибочные измерения FTM. В предлагаемом прототипе R_threshold выбран так, чтобы алгоритм исправления ошибок применялся как можно реже. Подробный анализ при R_threshold = 0,5, изложенный в §V, показывает существенные улучшения функционирования алгоритма .

B. Исправление вывода FTM

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

Исправление ошибок в особом случае. Начнем с рассмотрения особого случая, в котором между инициатором и ответчиком имеются только две траектории распространения сигнала: траектория прямой видимости с большими препятствиями и отраженная траектория. Этот случай соответствует тому, что показан на Рисунке 7c. В этом случае FTM рассчитает длину отраженной траектории. Ошибку FTM можно представить в виде разницы между его выходным значением и длиной прямой траектории. Идея, лежащая в основе FUSIC, заключается в том, чтобы использовать MUSIC для расчета ошибки FTM и, таким образом, корректировки выходного значения FTM. Трудность заключается в том, чтобы использовать MUSIC, плохо работающий на оборудовании Wi-Fi, для расчета ошибки FTM, который на самом деле работает лучше.

Для решения этой проблемы используется ключевой постулат, который изложен в §III-C: несмотря на неточность, разница расчетных значений ToF (следовательно, расстояний), полученная методом MUSIC для любых двух траекторий, действительно точна. Т.о. FUSIC может использовать неточные расчетные ToF траекторий распространения сигнала, выделенных методом MUSIC, для вычисления ошибки измерения FTM.

d̅_ϵ = (τ_отраж – τ_прям) x c, где

τ_отражи τ_прям – расчетные значения ToF для прямой и отраженной траекторий соответственно,

с≈3 х 10⁸ м/с – скорость света.

Прямая траектория выбирается из спектра MUSIC по минимальному расчетному значению ToF. Зная d̅_ϵ, алгоритм FUSIC вычисляет точное значение ToF для прямой траектории, вычитая это значение из измерения расстояния по протоколу FTM: d_fusic= d_ftm – d̅_ϵ.

Алгоритм общего назначения. В общем случае может быть несколько траекторий распространения сигнала между инициатором и ответчиком, и нет никаких предположений, касающихся относительных уровней мощности различных сигналов, достигающих приемника. При таких обстоятельствах, рассмотренных в § III-A (Рисунок 5b), измерения FTM не обязательно отражают длину конкретной траектории. Вместо этого, FTM рассчитывает значение между длинами прямой и отраженной траекторий. Более того, ошибки FTM увеличиваются по мере ослабления прямого сигнала по сравнению с отраженными (Рисунок 8).

В ходе моделирования этого явления выход FTM рассматривается как длина не реальной отраженной траектории, а виртуальной, на длину которой влияют длины и относительные мощности доминирующих траекторий распространения сигнала. Поэтому FUSIC учитывает сумму разниц всех длин траекторий относительно прямой, вычисляемой MUSIC, и присваивает траекториям веса́ пропорционально уровням мощности их сигналов. Затем вычисляется расчетная ошибка измерения FTM, τ̅, в терминах ToF (= d̅_ϵ / c), как разность средневзвешенного значения ToF и ToF прямой траектории (строка 6, алгоритм 1):

Эта величина также называется средней избыточной задержкой ([23], [24]). Алгоритм FUSIC окончательно устраняет влияние ошибки (строка 7, алгоритм 1) и выводит скорректированное значение расстояния, рассчитываемое по формуле d_fusic= d_ftm– τ̅  х с.

Часть 1/3

Часть 3/3 (в процессе перевода)

Список использованных источников

1. P. Bahl and V. N. Padmanabhan, "Radar: an in-building rf-based user location and tracking system," in Proceedings IEEE INFOCOM 2000. Conference on Computer Communications. Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies (Cat. No.00CH37064), 2000, pp. 775-784 vol.2.

2. Y. Ma, N. Selby, and F. Adib, "Minding the billions: Ultra-wideband localization for deployed rfid tags." in ACM MobiCom. 2017. pp. 248- 260.

3. S. Shen, M. Gowda, and R. Roy Choudhury, "Closing the gaps in inertial motion tracking," in ACM MobiCom. 2018, pp. 429 444.

4. S.-M. Moosavi-Dezfooli. Y.-A. Pignolet, and D. Dzung, "Simultaneous acoustic localization of multiple smartphones with euclidean distance matrices," in EWSN, 2016, pp. 4146.

5. D. Vasisht, G. Zhang, O. Abari, H.-M. Lu, J. Flanz, and D. Katabi, “Inbody backscatter communication and localization." in ACM SIGCOMM. 2018. pp. 132-146.

6. D. Vasisht, S. Kumar, and D. Katabi, "Decimeter-level localization with a single Wi-Fi access point," in USENIX NSDI, 2016. pp. 165-178.

7. E. Soltanaghaei, A. Kalyanaraman, and K. Whitehouse. "Multipath triangulation: Decimeter-level Wi-Fi localization and orientation with a single unaided receiver," in ACM MobiSys, 2018. pp. 376-388.

8. (2017, July) Path guide: A new approach to indoor navigation. [Online]. Available: https://www.microsoft.com/en-us/research/blog/path-guide-new-approach-indoor-navigation/

9. IEEE, "IEEE draft standard for information technology telecommunications and information exchange between systems - local and metropolitan area networks-specific requirements part 11: Wireless lan medium access control (mac) and physical layer (phy) specifications,” IEEE P802.11-REVmc/D6.0, June 2016, pp. 1-3774, 2016.

10. M. Rea, A. Fakhreddine, D. Giustiniano, and V. Lenders, "Filtering noisy 802.11 time-of-flight ranging measurements from commoditized Wi-Fi radios,” IEEE/ACM Transactions on Networking, pp. 2514-2527, 2017.

11. W.-F. Alliance®. (2017, Feb.) Wi-fi certified location™ brings wi-fi® indoor positioning capabilities. [Online]. Available: https://www.wi-fi.org/news-events/newsroom/wi-fi-certified- location-brings-wi-fi-indoor-positioning-cap abilities

12. A. developers documentation. (2018) Wi-fi location:ranging with rtt. [Online]. Available: https://developer.android.com/guide/topics/connectivity/Wi-Fi-rtt

13. M. Ibrahim, H. Liu, M. Jawahar, V. Nguyen, M. Gruteser, R. Howard, B. Yu, and F. Bai, "Verification: Accuracy evaluation of Wi-Fi fine time measurements on an open platform,” in ACM MobiCom, 2018. pp. 417- 427.

14. R. Schmidt, "Multiple emitter location and signal parameter estimation," IEEE Transactions on Antennas and Propagation, pp. 276-280, 1986.

15. M. Kotaru, K. Joshi. D. Bharadia, and S. Katti, "Spotfi: Decimeter level localization using Wi-Fi." in ACM SIGCOMM, 2015. pp. 269-282.

16. W. Gong and J. Liu, "Sifi: Pushing the limit of time-based Wi-Fi localization using a single commodity access point,” ACM UbiComp, pp. 10:1-10:21, 2018.

17. S. Sen, J. Lee, K.-H. Kim, and P. Congdon. "Avoiding multipath to revive inbuilding Wi-Fi localization," in ACM MobiSys. 2013. pp. 249-262.

18. J. Xiong, K. Sundaresan, and K. Jamieson. "Tonetrack: Leveraging frequency-agile radios for time-based indoor wireless localization," in ACM MobiCom, 2015. pp. 537-549.

19. Y. Xie, Z. Li, and M. Li. "Precise power delay profiling with commodity Wi-Fi," in ACM MobiCom. 2015, p. 53-64.

20. A. T. Mariakakis, S. Sen. J. Lee, and K.-H. Kim. “Sail: Single access point-based indoor localization." in ACM MobiSys. 2014. pp. 315-328.

21. Z. Tian, Z. Li, M. Zhou. Y. Jin. and Z. Wu, "PILA: sub-meter localization using CSI from commodity wi-fi devices,” Sensors, 2016.

22. D. Halperin, W. Hu, A. Sheth, and D. Wetherall. "Tool release: Gathering 802.1 In traces with channel state information," ACM SIGCOMM Comput. Comniun. Rev., pp. 53-53, 2011.

23. R. Bharadwaj and S. K. Koul, “Study and analysis of channel characteristics of ultra-wideband communication links using wearable antennas,” in 2017 IEEE Asia Pacific Microwave Conference (APMC), 2017, pp. 45 48.

24. S. Forcellini and L. C. Trintinalia. “Location estimation using relationship between delay spread and mean excess delay," in Proceedings. 2005 IEEE Networking, Sensing and Control, 2005, 2005, pp. 638-643.

25. F. Izquierdo, M. Ciurana, F. Barcelo, J. Paradells, and E. Zola, "Performance evaluation of a toa-based trilateration method to locate terminals in wlan," in 2006 1st International Symposium on Wireless Pervasive Computing, 2006. pp. 1-6.

26. Intel. (2019. Jan.) iwlWi-Fi: mvm: implement csi reporting. [Online]. Available: https://git.kemel.org/pub/scm/linux/kemel/git/iwlWi-Fi/iwlWi-Fi- fixes.git/commit/?id=5213e8a8a28d2c4cl43fec94e57c866a958ed52d

27. F. Zafari, A. Gkelias, and K. K. Leung. "A survey of indoor localization systems and technologies,” CoRR, 2017.

28. Z. Yang, Z. Zhou, and Y. Liu, “From rssi to csi: Indoor localization via channel response." ACM Comput. Surv, pp. 25:1-25:32, 2013.

29. P. Kumar. L. Reddy, and S. Varma. "Distance measurement and error estimation scheme for rssi based localization in wireless sensor networks,” in WCSN. 2009. pp. 1-4.

30. I. Guvenc. "Enhancements to rss based indoor tracking systems using kalman filters." in In GSPx International Signal Processing Conference, 2003.

31. B. Ferris, D. Fox. and N. Lawrence, "Wi-Fi-slam using gaussian process latent variable models." in Proceedings of the 20th International Joint Conference on Artificial Intelligence, 2007, pp. 2480-2485.

32. A. Goswami, L. E. Ortiz, and S. R. Das, “Wigem: A learning-based approach for indoor localization," in ACM CoNEXT, 2011, pp. 3:1-3:12.

33. K. Wu. Jiang Xiao. Youwen Yi, Min Gao, and L. M. Ni, “Fila: Fine-grained indoor localization." in IEEE INFOCOM. 2012, pp. 2210-2218.

34. S. A. Golden and S. S. Bateman, "Sensor measurements for wi-fi location with emphasis on time-of-arrival ranging,” IEEE Transactions on Mobile Computing, pp. 1185-1198. 2007.

35. D. Giustiniano and S. Mangold, "Caesar: Carrier sense-based ranging in off-the-shelf 802.11 wireless lan," in ACM CoNEXT, 2011. pp. 10:1- 10:12.

36. M. Youssef. A. Youssef, C. Rieger, U. Shankar, and A. Agrawala, “Pinpoint: An asynchronous time-based location determination system," in ACM MobiSys, 2006, pp. 165-176.

37. M. Ciurana, F. Barcelo-Arroyo, and F. Izquierdo, "A ranging system with ieee 802.11 data frames," in 2007 IEEE Radio and Wireless Symposium, 2007, pp. 133-136.

38. N. Tadayon. M. T. Rahman, S. Han, S. Valaee, and W. Yu, “Decimeter ranging with channel state information,” IEEE Trans. Wireless Communications. pp. 3453-3468, 2019.

39. Y. Yu, R. Chen. L. Chen, G. Guo, F. Ye, and Z. Liu, "A robust dead reckoning algorithm based on wi-fi ftm and multiple sensors," Remote Sensing. 2019.

40. L. Banin. O. Bar-Shalom, N. Dvorecki, and Y. Arnizur, “Scalable wi-fi client self-positioning using cooperative ftm-sensors," IEEE Transactions on Instrumentation and Measurement, pp. 1-13, 2018.