Статья «When FTM Discovered MUSIC: Accurate WiFi-based Ranging in the Presence of Multipath» опубликована в материалах Международной конференции IEEE по компьютерным коммуникациям, которая прошла в Торонто, Канада, с 6 по 9 июля 2020 г. (IEEE International Conference on Computer Communications, INFOCOM 2020). Идеи, изложенные в этой публикации, получили дальнейшее развитие, в частности, в статье «FSI: A FTM Calibration Method Using Wi-Fi Physical Layer Information» («FSI: метод калибровки FTM с использованием информации о физическом уровне Wi-Fi»), опубликованной во 2-й части материалов 17-й Международной конференции по беспроводным алгоритмам, системам и приложениям, которая прошла в Даляне, Китай, с 24 по 26 ноября 2022 г. (Wireless Algorithms, Systems, and Applications; WASA 2022).
Аннотация. Недавно (относительно, в 2016 году – прим. пер.) стандартизирован IEEE протокол точного измерения времени (Fine Timing Measurement, FTM), основанный на измерении дальности по времени распространения сигнала (Time-Of-flight, TOF). Большое количество публикаций посвящены определению местоположения Wi-Fi-устройств в помещениях. С другой стороны доступных соответствующих решений по состоянию на данный момент очень мало. Поэтому появление FTM может стать поворотным моментом в преодолении разрыва между теорией и практикой. Эксперименты с первыми картами Wi-Fi, поддерживающими FTM, показывают, что в условиях прямой видимости (Line-Of-Sight, LOS), они обеспечивают точность до нескольких метров, но точность в условиях вне прямой видимости (Non-Line-Of-Sight, NLOS) может быть не такой высокой. В этой статье представлен FUSIC – первый метод, который улучшает точность измерений с помощью FTM в условиях LOS до значений в условиях NLOS без необходимости внесения каких-либо изменений в стандарт.
Для этого в методе FUSIC используются измерения FTM и MUSIC, которые недостоверны в условиях NLOS, но позволяют решить следующую двуединую задачу:
1) установление факта неточности значения, получаемого по протоколу FTM;
2) внесение соответствующих корректив для исправления неточности этого значения.
Эксперименты, проведенные в 4-х различных физических помещениях, показывают, что:
а) метод FUSIC повышает точность измерения расстояния с помощью протокола FTM в условиях LOS до значений NLOS и т.о. позволяет достичь заявленную цель;
б) возможности протокола FTM по определению местоположения Wi-Fi-устройств в помещениях значительно улучшаются.
I. Введение
Разработка методов по определению местоположения Wi-Fi-устройств в помещениях уходит своими корнями в проект RADAR [1], реализованный почти 20 лет назад. Его основная идея заключалась в том, чтобы использовать общедоступную Wi-Fi-инфраструктуру для определения местоположения с точностью до нескольких метров в помещениях, в которых обычно сигналы GPS отсутствуют. Для определения местоположения мобильных вычислительных устройств предлагалось оценивать расстояния до точек доступа Wi-Fi, местоположение которых известно. С тех пор определение местоположения в помещении стала серьезной научной и технологической задачей. Предложены десятки подходов, представляющих пространство решений, которое со временем расширилось за счет различных базовых технологий, в частности, UWB [2], измерительных датчиков [3], акустики [4], и развития мобильных вычислительных устройств, например, смартфонов, планшетов, RFID-меток, носимых устройств и даже микроимплантов [5]. Тем не менее, основной постулат RADAR остается верным и по сей день: Wi-Fi широко распространен, поэтому является основной платформой для определения местоположения в помещениях. Недавно Wi-Fi-системы преодолели метровый барьер точности, обещая впечатляющую точность до нескольких дециметров [6], [7].
Но к сожалению, достаточно посмотреть на свой смартфон, чтобы понять масштаб отставания внедрения этих технологий на рынке, несмотря на участие таких гигантов отрасли, как Google и Microsoft [8].
На этом фоне ассоциация IEEE недавно решила обратить свое внимание на метод определения местоположения Wi-Fi-источников. В рамках поправки 802.11mc [9] она стандартизировала протокол точного измерения времени FTM (Fine Timing Measurement), основанный на времени распространения сигнала (Time-of-Flight, ToF) [10] для вычисления расстояния между Wi-Fi-клиентом и точкой доступа. FTM обеспечивает точность до нескольких метров, которая уступает точности, полученной в некоторых недавних работах [7], но достаточную для многих приложений, например, для умного дома [6] или навигации в торговых центрах. Еще более важно то, реализация стандартизированного и встроенного в прошивки протокола FTM, использующего часы с пикосекундным разрешением, может стать важным поворотным моментом для определения местоположения в помещениях, а определение местоположения – стандартной услугой на наших мобильных устройствах. Хотя протокол 802.11mc поддерживается не всеми доступными в настоящее время Wi-Fi-устройствами, он уже получил поддержку основных производителей устройств Wi-Fi [11] и используется в ОС Android [12]. Например, недавние телефоны Google Pixel 2 и 3 совместимы со стандартом 802.11mc.
В теории Wi-Fi FTM выглядит прорывным подходом, но реальное положение дел не так оптимистично. Рассмотрим простой случай: пользователь стоит в 5 м от точки доступа с поддержкой FTM и считывает измерения на устройстве, оснащенной картой Wi-Fi FTM. На Рисунке 1 видно, что в течение первых 30 с, пока пользователь обращен лицом к точке доступа и находится в зоне LOS, FTM практически точно оценивает расстояние между пользователем и точкой доступа. Однако стоит пользователю повернуться на 180°, перекрыв тем самым линию LOS между клиентом и точкой доступа, и точность FTM резко падает.
Это можно объяснить наличием многолучевой интерференции радиосигнала в помещении. После 30 с сигнал, который распространялся по линии прямой видимости, ослаблен препятствием в виде человеческого тела. Поэтому FTM рассчитывает расстояние по (наиболее сильному) отраженному сигналу. Эта недостаток Wi-Fi FTM, который проявляется в зоне вне прямой видимости (NLOS), недавно рассматривался в работе [13], но никакого решения не предложено. Подход MUSIC (Multiple Signal Classification) [14] может показаться физическим методом, способным различить множественные траектории и вычислить время прохождения прямой траектории. К сожалению, многочисленные исследования [15], [16] показали, что он плохо работает на оборудовании Wi-Fi.
В этой работе представлен FUSIC – подход, объединяющий FTM и MUSIC с целью обеспечения точности FTM, полученных в условиях LOS, для условий NLOS. FUSIC не требует внесения изменений в стандарт, он просто принимает в качестве входных данных расчет расстояния по протоколу FTM, информацию о состоянии канала Wi-Fi (Channel State Information, CSI) и исправляет ошибку, если обнаруживает ее наличие. Поэтому FUSIC можно реализовать в виде автономного пользовательского приложения на мобильных устройствах без внесения каких-либо модификаций в точки доступа.
На пути достижения поставленной FUSIC цели имеется ряд проблем.
Во-первых, хотя характеристики FTM в условиях NLOS, показанные на Рисунке 1, подробно рассмотрены в работе [13], два главных вопроса остались открытыми:
1) какое влияние несколько экземпляров передаваемого сигнала и их относительная мощность оказывают на точность FTM, и
2) играют ли препятствия дополнительную роль в наблюдаемой неточности?
При прохождении препятствий скорость распространения радиочастотного сигнала снижается на величину, зависящую от относительной диэлектрической проницаемости препятствий. FTM преобразует ToF в расстояние с помощью скорости света, поэтому возможны потенциальные ошибки. Однако влияние таких ошибок на точность FTM пока не изучено.
Во-вторых, FUSIC должен обнаруживать факт неточности значения, рассчитываемого FTM, даже если это значение и CSI являются его единственными входными данными. Прямолинейный подход может состоять в том, чтобы применить MUSIC к CSI, получить профиль задержки мощности (Power-Delay Profile, PDP) и, если прямой сигнал не является самым мощным, сделать вывод о наличии ошибки. Однако измерения показывают, что значение FTM может быть точным, даже если прямой сигнал не является самым сильным, а применение коррекции к точному результату может сделать его ошибочным. В результате, как только FUSIC обнаруживает, что FTM вернул неточный результат, то он должен его скорректировать, имея в качестве входных данных только это значение и профиль задержки мощности MUSIC, которые ошибочны.
В двух словах эти проблемы решаются с помощью анализа измерений, полученных стандартным оборудованием, который должен пролить свет на факторы, приводящие к низкой производительности Wi-Fi FTM в условиях NLOS. Совмещение выходного сигнала FTM с профилем задержки мощности принятых сигналов, взятом из MUSIC, позволяет получить точное представление о связи между многолучевым распространением сигнала и значением FTM. Это представление используется для разработки двух основных частей FUSIC: механизма выявления ошибочных результатов расчета FTM и механизма исправления ошибок, объединяющего данные FTM и MUSIC.
Суть данной статьи можно кратко изложить следующим образом.
В разделе III проводится анализ измерений Wi-Fi FTM и MUSIC с использованием стандартного оборудования. Мы оцениваем недостатки FTM в условиях NLOS и изучаем их основные причины на уровне сигнала. Кроме того, оценивается способность MUSIC повысить точность FTM.
В разделе IV используем результаты, полученные в ходе анализа измерений, для разработки FUSIC – алгоритма, который использует в качестве входных данных расстояния, рассчитанные FTM, и CSI, а также:
1) способен определять факт неточности результата измерения расстояния, полученного FTM, и
2) при необходимости корректировать этот результат.
В разделе V используется испытательный стенд, включающий стандартное оборудование, для проведения всесторонней оценки FUSIC в 4 различных физических условиях, включая контролируемую среду, университетский ресторан, склад и студенческую комнату отдыха. Эти эксперименты показывают, что:
а) FUSIC повышает точность измерения расстояний с помощью FTM в условиях NLOS до точности, получаемой в условиях LOS, и за счет этого позволяет достичь поставленной цели;
б) возможности FTM по определению местоположения в помещениях значительно улучшаются.
II. Базовая проблематика
В этом разделе представлены необходимые сведения для понимания сути статьи.
A. Информация о состоянии канала (CSI)
В беспроводных системах сигнал, который достигает приемника, обычно искажается (например, ослабляется и отражается) каналом, по которому он проходит, прежде чем достичь приемника. Если обозначить сигнал, посланный передатчиком, переменной х, то сигнал y, достигший приемника, определяется уравнением:
y = H * x + n (1)
где матрица H отражает комплексное затухание и фазовые сдвиги, которым подвергается сигнал при прохождении через канал, а n – фоновый шум, который часто считается белым гауссовским шумом с нулевым средним значением. H называется информацией о состоянии канала (CSI) и отражает свойства канала между отправителем и получателем. Во многих исследовательских работах ([6], [7], [15]-[21]) предлагаются решения с использованием CSI, т.к. ее обработка может дать полезную информацию о распространении сигнала, в т.ч. время распространения сигнала (Time-Of-flight, TOF), угол наклона траектории (Angle of Arrival, AoA) и профиль задержки мощности (Power Delay Profile, PDP).
B. MUSIC в частотной области: расчет ToF для нескольких траекторий распространения
Для краткости предлагается интуитивно понятное краткое изложение MUSIC (Multiple Signal Classification) [14], необходимое для понимания данной работы. Более подробное описание представлено в работах [14], [15], [18]. Алгоритм MUSIC различает сигналы с помощью ожидаемых изменений фазы, если они приходят из заданного местоположения. Он основан на измерениях, полученных от каждой поднесущей OFDM системы (как, например, в случае Wi-Fi). Это осуществимо за счет того, что для данного ToF разница в частоте сигнала приводит к разнице в фазе в принимающей системе. Фактически, два сигнала, которые достигают антенны после прохождения за время ToF τ, достигнут этой антенны с ожидаемой разностью фаз -2π x (fj – fa) x τ, где fj и fa – частоты этих сигналов. Это означает, что, зная измерения сигнала на разных поднесущих OFDM в диапазоне Wi-Fi, можно получить ToF для разных траекторий распространения. MUSIC использует это свойство для построения модели, способной различать ToF различных траекторий распространения. Алгоритм MUSIC использует в качестве входных данных CSI соответствующего канала связи и возвращает спектр, отражающий мощность сигнала, принимаемого приемником в каждый момент времени, своего рода PDP. По пикам спектра можно установить траектории распространения и рассчитать их ToF и мощности.
C. Точное измерение времени (FTM)
Протокол точного измерения времени (FTM) стандартизирован в IEEE 802.11-2016 (включен как часть поправки 802.11mc) [9]. Он позволяет станции Wi-Fi вычислять расстояние до точки доступа в радиусе действия без необходимости привязки к конкретной точке доступа. Протокол рассчитывает ToF между двумя Wi-Fi-устройствами, то есть времени, которое требуется сигналу, передаваемому одним устройством, для достижения другого.
Как показано на Рисунке 2, процесс начинается со станции Wi-Fi (называемой инициатором), которая ищет точки доступа, поддерживающие FTM.
Если обнаружена точка доступа с поддержкой FTM, инициатор отправляет ей кадр запроса FTM. При получении этого запроса точка доступа может проигнорировать его или стать ответчиком. В последнем случае две станции начинают серии обменов пакетами (FTM, ACK), т.н. блоками, которая позволяет инициатору рассчитать время приема-передачи (Round Trip Time, RTT) с ответчиком. Блок FTM состоит из нескольких пакетов FTM, отправляемых ответчиком, получение каждого из которых подтверждается инициатором. Обе станции фиксируют временные метки отправки и получения пакетов блока. RTT рассчитывается следующим образом:
RTT = (t4 − t1) − (t3 − t2),
где t1 и t2 обозначают время отправки ответчиком и приема инициатором пакета FTM соответственно, а t3, t4 — время отправки инициатором и приема ответчиком сигнала ACK соответственно. В результате расстояние между двумя устройствами рассчитывается из ToF (которое составляет половину RTT) путем умножения последнего на скорость света. Следует обратить внимание на то, что сеанс FTM также может состоять из нескольких блоков. В этом случае количество блоков согласовывается в начале процесса. RTT для сеанса FTM с N блоками является средним значением RTT для каждого блока.
Хотя подход, лежащий в основе FTM, не является новым, его стандартизация IEEE и последующая встроенная реализация в прошивках контроллеров сетевого интерфейса (NIC) Wi-Fi, использующая временные метки с пикосекундным разрешением [9], могут существенно изменить ситуацию на практике. В следующем разделе представлена оценка точности некоторых из первых сетевых карт с встроенной поддержкой FTM, имеющихся на рынке.
Часть 2/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.