References

gyroscopy

Гироскопия и навигация

Giroskopiya i Navigatsiya / Gyroscopy and Navigation

0869-70352075-0927

AO «Концерн «ЦНИИ «Электроприбор»

10.17285/0869-7035.2016.24.1.003-035

gyroscopy-334

Research Article

Статьи

Обзор параметрических методов позиционирования на основе концепции отпечатка пальца

A survey of fingerprinting and parametric fingerprint-positioning methods

Мюллер

Ф.

Müller

Мюллер Филипп, докторант.

Райтохарью

Raitoharju

Райтохарью Mатти, доктор наук, научный сотрудник.

Али-Лойту

С.

Ali-Löytty

Али-Лойту Симо, преподаватель

Вирола

Л.

Wirola

Вирола Лаура, научный сотрудник.

Пише

Р.

Piché

Пише Роберт. Доктор наук, профессор.

Технологический университет Тампере, факультет автоматизации и проектированияФинляндияTampere University of TechnologyFinland

Технологический университет Тампере, факультет математики.ФинляндияTampere University of TechnologyFinland

Технологический университет Тампере.ФинляндияTampere University of TechnologyFinland

2016

01122025

2413648

2025

Мюллер Ф., Райтохарью M., Али-Лойту С., Вирола Л., Пише Р.

Müller P., Raitoharju M., Ali-Löytty S., Wirola L., Piché R.

Данная работа распространяется под лицензией Creative Commons Attribution 4.0.

This work is licensed under a Creative Commons Attribution 4.0 License.

https://www.gyroscopy.ru/jour/article/view/334

Под термином «позиционирование на основе отпечатка пальца» (англ. fingerprinting – метод отпечатка пальца, метод фингерпринтинга) понимается большое разнообразие методов определения местоположения приемника с использованием базы данных мощностей радиосигнала, ранее измеренных и привязанных к координатам. Непараметрические методы, напр. метод k взвешенных ближайших соседей (WKNN), невозможно использовать в крупномасштабных службах для мобильных устройств вследствие больших объемов данных и требований к передаче информации. В предлагаемой работе представлен обзор параметрических методов фингерпринтинга, которые используют представления данных на основе моделей. Рассмотрены три различные группы параметрических методов: методы, использующие области покрытия, методы, использующие потери при распространении сигнала, и методы, использующие смесь нормальных распределений. В рамках каждой группы рассматриваются различные подходы, их достоинства и недостатки. Обсуждается качество позиционирования в помещении с использованием некоторых из приведенных подходов в различных сценариях по данным беспроводных локальных сетей (WLAN). Полученные результаты сравниваются с результатами для непараметрического метода WKNN.

The term fingerprint-based (FP) positioning includes a wide variety of methods for determining a receiver’s position using a database of radio signal strength measurements that were collected earlier at known locations. Nonparametric methods such as the weighted k-nearest neighbor (WKNN) method are infeasible for largescale mobile device services because of the large data storage and transmission requirements. In this work we present an overview of parametric FP methods that use model-based representations of the survey data. We look at three different groups of parametric methods: methods that use coverage areas, methods that use path loss models, and methods that use Gaussian mixtures. Within each group we study different approaches and discuss their pros and cons. Furthermore, we test the positioning performance of several of the analyzed approaches in different scenarios using real-world WLAN indoor data and compare the results to those of the WKNN method.

Фингерпринтингпараметрические методы позиционированиясравнение.

Fingerprint-based (FP) positioningparametric FP methodscomparison.

References1

ЛИТЕРАТУРА

S. Gezici, Z. Tian, G. B. Biannakis, H. Kobayashi, A. F. Molisch, H. V. Poor, and Z. Sahinoglu, “Localization via ultra-wideband radios: a look at positioning aspects for future sensor networks,” IEEE Signal Processing Magazine, vol. 22, no. 4, pp. 70–84, July 2005.

F. Gustafsson and F. Gunnarsson, “Mobile positioning using wireless networks: possibilities and fundamental limitations based on available wireless network measurements,” IEEE Signal Processing Magazine, vol. 22, no. 4, pp. 41–53, July 2005.

E. Trevisani and A. Vitaletti, “Cell-id location technique, limits and benefits: an experimental study,” in Proceedings of Sixth IEEE Workshop on Mobile Computing Systems and Applications (WMCSA 2004). Windermere, Cumbria, United Kingdom, December 2004.

L. Wirola, “Studies on location technology standards evolution in wireless networks,” Ph.D. dissertation, Tampere University of Technology, March 2010. [Online]. Available: http://URN.fi/URN:NBN:fi:tty-201002121065

D. Dardari, A. Conti, U. Ferner, A. Giorgetti, and M. Z. Win, “Ranging with ultrawide bandwidth signals in multipath environments,” Proceedings of the IEEE, vol. 97, no. 2, pp. 404–426, February 2009.

R. Mautz, “Indoor positioning technologies,” Habilitation Thesis, http://ecollection.library.ethz.ch/eserv/eth:5659/eth-5659-01.pdf, February 2012.

H. Liu, H. Darabi, P. Banerjee, and J. Liu, “Survey of wireless indoor positioning techniques and systems,” IEEE Transactions on Systems, Man, and Cybernetics, Part C: Applications and Reviews, vol. 37, no. 6, pp. 1067–1080, November 2007.

M. I. Silventoinen and T. Rantalainen, “Mobile station emergency locating in GSM,” in Proceedings of IEEE International Conference on Personal Wireless Communications. New Delhi, India, February 1996, pp. 232–238.

I. Constandache, S. Gaonkar, M. Sayler, R. R. Choudhury, and L. Cox, “EnLoc: Energyefficient localization for mobile phones,” in 2009 Proceedings IEEE INFOCOM. Rio de Janeiro, Brazil, April 2009, pp. 2716–2720.

M. A. Spirito, S. Pöykkö, and O. Knuuttila, “Experimental performance of methods to estimate the location of legacy handsets in GSM,” in IEEE VTS 54th Vehicular Technology Conference (VTC), 2001. Atlantic City, NJ, USA, October 2001, pp. 2716–2720.

J. A. del Peral-Rosado, J. A. López-Salcedo, G. Seco-Granados, F. Zanier, and M. Crisci, “Analysis of positioning capabilities of 3GPP LTE,” in Proceeddings of 25th International Technical Meeting of the Satellite Division of ION, Nashville, TN, USA, September 2012.

L. Wirola, T. A. Laine, and J. Syrjärinne, “Mass-market requirements for indoor positioning and indoor navigation,” in 2010 International Conference on Indoor Positioning and Indoor Navigation (IPIN). Zurich, Switzerland, September 2010.

J. Park, D. Curtis, S. Teller, and J. Ledlie, “Implications of device diversity for organic localization,” in 2011 Proceedings IEEE INFOCOM, April 2011, pp. 3182–3190.

A. F. Molisch, Wireless Communications, 2nd ed. Wiley - IEEE, January 2011.

V. Honkavirta, T. Perälä, S. Ali-Löytty, and R. Piché, “A comparative survey of WLAN location fingerprinting methods,” in Proceedings of the 6th Workshop on Positioning, Navigation and Communication 2009 (WPNC’09). Hannover, Germany, March 2009, pp. 243–251.

C. Figuera, I. Mora-Jiménez, A. Guerrero-Curieses, J. L. Rojo-Álvarez, E. Everss, M. Wilby, and J. Ramos-López, “Nonparametric model comparison and uncertainty evaluation for signal strength indoor location,” IEEE Transactions on Mobile Computing, vol. 8, no. 9, pp. 1250–1264, September 2009.

P. Müller, M. Raitoharju, and R. Piché, “A field test of parametric WLAN-fingerprintpositioning methods,” in Proceedings of the 17th International Conference on Information Fusion (Fusion 2014). Salamanca, Spain, July 2014, pp. 1–8.

S. Han, Z. Gong, W. Meng, and C. Li, “An indoor radio propagation model considering angles for WLAN infrastructures,” Wireless Communications and Mobile Computing, 2015 (in press).

S. Shrestha, J. Talvitie, and E. S. Lohan, “Deconvolution-based indoor localization with WLAN signals and unknown access point locations,” in 2013 International Conference on Localization and GNSS (ICL-GNSS). Torino, Italy, June 2013, pp. 1–6.

L. Koski, R. Piché, V. Kaseva, S. Ali-Löytty, and M. Hännikäinen, “Positioning with coverage area estimates generated from location fingerprints,” in Proceedings of the 7th Workshop on Positioning, Navigation and Communication 2010 (WPNC’10). Dresden, Germany, March 2010, pp. 99–106.

J. Machaj, R. Piché, and P. Brida, “Rank based fingerprinting algorithm for indoor positioning,” in 2011 International Conference on Indoor Positioning and Indoor Navigation (IPIN). Guimaraes, Portugal, September 2011, pp. 6–11.

L. Wirola, L. Wirola, and R. Piché, “Bandwidth and storage reduction of radio maps for offline WLAN positioning,” in 2013 International Conference on Indoor Positioning and Indoor Navigation (IPIN). Montbeliard-Belfort, France, October 2013.

S. Eisa, J. Peixoto, F. Meneses, and A. Moreira, “Removing useless APs and fingerprints from WiFi indoor positioning radio maps,” in 2013 International Conference on Indoor Positioning and Indoor Navigation (IPIN). Montbeliard-Belfort, France, 2013, pp. 739–745.

M. Raitoharju, T. Fadjukoff, S. Ali-Löytty, and R. Piché, “Using unlocated fingerprints in generation of WLAN maps for indoor positioning,” in Proceedings of PLANS 2012 IEEE/ION Position Location and Navigation Symposium. Myrtle Beach, SC, USA, April 2012, pp. 576–583.

L. Wirola, I. Halivaara, and J. Syrjärinne, “Requirements for the next generation standardized location technology protocol for location-based services,” Journal of Global Positioning Systems, vol. 7, no. 2, pp. 91–103, 2008.

K. Kaemarungsi and P. Krishnamurthy, “Properties of indoor received signal strength for WLAN location fingerprinting,” in The First Annual International Conference on Mobile and Ubiquitous Systems: Networking and Services (MOBIQUITIOUS 2004). Boston, MA, USA, August 2004, pp. 14–23.

T. Vaupel, J. Seitz, F. Kiefer, S. Haimerl, and J. Thielecke, “Wi-Fi positioning: System considerations and device calibration,” in 2010 International Conference on Indoor Positioning and Indoor Navigation (IPIN). Zurich, Switzerland, September 2010.

C. Laoudias, R. Piché, and C. G. Panayiotou, “Device signal strength self-calibration using histograms,” in 2012 International Conference on Indoor Positioning and Indoor Navigation (IPIN). Sydney, NSW, Australia, November 2012.

L. Koski, T. Perälä, and R. Piché, “Indoor positioning using WLAN coverage area estimates,” in 2010 International Conference on Indoor Positioning and Indoor Navigation (IPIN). Zurich, Switzerland, September 2010.

A. Haeberlen, E. Flannery, A. M. Ladd, A. Rudys, D. S. Wallach, and L. E. Kavraki, “Practical robust localization over large-scale 802.11 wireless networks,” in MobileCom’04. Philadelphia, PA, USA, September-October 2004.

M. B. Kjaergaard, “Indoor location fingerprinting with heterogeneous clients,” Pervasive and Mobile Computing, vol. 7, no. 1, pp. 31–43, 2011.

Y.-C. Cheng, Y. Chawathe, A. LaMarca, and J. Krumm, “Accuracy characterization for metropolitan-scale Wi-Fi localization,” in Proceedings of the 3rd International Conference on Mobile Systems, Applications and Services (MobiSys 2005). Seattle, WA, USA, June 2005.

A. M. Hossain and W.-S. Soh, “Cramér-Rao bound analysis of localization using signal strength difference as location fingerprint,” in 2010 Proceedings IEEE INFOCOM. San Diego, CA, USA, March 2010.

A. H. Jazwinski, Stochastic Processes and Filtering Theory, ser. Mathematics in Science and Engineering. Academic Press, 1970, vol. 64.

S. Särkkä, Bayesian Filtering and Smoothing. Cambridge University Press, 2013.

Y. Bar-Shalom, R. X. Li, and T. Kirubarajan, Estimation with Applications to Tracking and Navigation, Theory Algorithms and Software. John Wiley & Sons, 2001.

R. Piché, “Robust estimation of a reception region from location fingerprints,” in 2011 International Conference on Localization and GNSS (ICL-GNSS). Tampere, Finland, June 2011, pp. 31–35.

L. Koski, “Positioning with Bayesian coverage area estimates and location fingerprints,” Master’s thesis, Tampere University of Technology, http://math.tut.fi/posgroup/koski_mscth.pdf, March 2010.

M. Raitoharju, S. Ali-Löytty, R. Piché, and M. Dashti, “Positioning with multilevel coverage area models,” in 2012 International Conference on Indoor Positioning and Indoor Navigation (IPIN). Sydney, NSW, Australia, November 2012.

S. Geman and D. Geman, “Stochastic relaxation, Gibbs distributions, and the Bayesian restoration of images,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. PAMI-6, no. 6, pp. 721–741, 1984.

A. P. Dempster, N. M. Laird, and D. B. Rubin, “Maximum likelihood from incomplete data via the EM algorithm,” Journal of the Royal Statistical Society. Series B (Methodological), vol. 39, no. 1, pp. 1–38, 1977.

V. Honkavirta, “Location fingerprinting methods in wireless local area networks,” Master’s thesis, Tampere University of Technology, http://urn.fi/URN:NBN:fi:tty-200911137109, November 2008.

C. Laoudias, C. G. Panayiotou, and P. Kemppi, “On the RBF-based positioning using WLAN signal strength fingerprints,” in Proceedings of the 7th Workshop on Positioning, Navigation and Communication 2010 (WPNC’10). Dresden, Germany, March 2010, pp. 93–98.

K. Kaji and N. Kawaguchi, “Design and implementation of WiFi indoor localization based on Gaussian mixture model and particle filter,” in 2012 International Conference on Indoor Positioning and Indoor Navigation (IPIN). Sydney, NSW, Australia, November 2012.

H. Hashemi, “The indoor radio propagation channel,” Proceedings of the IEEE, vol. 81, no. 7, pp. 943–968, July 1993.

N. Patwari, I. Alfred O. Hero, M. Perkins, N. S. Correal, and R. J. O’Dea, “Relative location estimation in wireless sensor networks,” IEEE Transactions on Signal Processing, vol. 51, no. 8, pp. 2137–2148, August 2003.

X. Li, “RSS-based location estimation with unknown pathloss model,” IEEE Transactions on Wireless Communications, vol. 5, no. 12, pp. 3626–3633, December 2006.

T. Roos, P. Myllymäki, and H. Tirri, “A statistical modeling approach to location estimation,” IEEE Transactions on Mobile Computing, vol. 1, no. 1, pp. 59–69, Jan-Mar 2002.

S. M. Bo-Chieh Liu, K.-H. Lin, and J.-C. Wu, “Analysis of hyperbolic and circular positioning algorithms using stationary signal-strength-difference measurements in wireless communications,” IEEE Transactions on Vehicular Technology, vol. 55, no. 2, pp. 499–509, March 2006.

H. Nurminen, J. Talvitie, S. Ali-Löytty, P. Müller, E. S. Lohan, R. Piché, and M. Renfors, “Statistical path loss parameter estimation and positioning using RSS measurements in indoor wireless networks,” in 2012 International Conference on Indoor Positioning and Indoor Navigation (IPIN). Sydney, NSW, Australia, November 2012.

J. Salo, L. Vuokko, H. M. El-Sallabi, and P. Vainikainen, “An additive model as a physical basis for shadow fading,” IEEE Transactions on Vehicular Technology, vol. 56, no. 1, pp. 13–26, January 2007.

V. Erceg, L. J. Greenstein, S. Y. Tjandra, S. R. Parkoff, A. Gupta, B. Kulic, A. A. Julius, and R. Bianchi, “An empirically based path loss model for wireless channels in suburban environments,” IEEE Journal on Selected Areas in Communications, vol. 17, no. 7, pp. 1205–1211, 1999.

T. S. Rappaport, S. Y. Seidel, and K. Takamizawa, “Statistical channel impulse response models for factory and open plan building radio communication system design,” IEEE Transactions on Communications, vol. 39, no. 5, pp. 794–807, 1991.

S. S. Ghassenizadeh, R. Jana, C. W. Rice, W. Turin, and V. Tarokh, “A statistical path loss model for in-home UWB channels,” in 2002 IEEE Conference on Ultra Wideband Systems and Technologies. Baltimore, MD, USA, May 2002, pp. 59–64.

B. Dil and P. Havinga, “RSS-based localization with different antenna orientations,” in 2010 Australasian Telecommunication Networks and Applications Conference (ATNAC). Auckland, New Zealand, 2010, pp. 13–18.

S. Shrestha, E. Laitinen, J. Talvitie, and E. S. Lohan, “RSSI channel effects in cellular and WLAN positioning,” in Proceedings of the 9th Workshop on Positioning, Navigation and Communication 2012 (WPNC’12). Dresden, Germany, March 2012, pp. 187–192.

T. S. Rappaport, Wireless Communications - Principles and Practice, 2nd ed. Prentice-Hall, 2010. 58. S. Y. Seidel and T. S. Rappaport, “914 MHz path loss prediction models for indoor wireless communications in multifloored buildings,” IEEE Transactions on Antennas and Propagation, vol. 40, no. 2, pp. 207–217, February 1992.

B. Dil and P. Havinga, “On the calibration and performance of RSS-based localization methods,” in Internet of Things 2010 Conference. Tokyo, Japan, November/December 2010.

M. Hata, “Empirical formula for propagation loss in land mobile radio services,” IEEE Transactions on Vehicular Technology, vol. 29, no. 3, pp. 317–325, August 1980.

K. Shujaee, A. Ebaid, R. George, and M. A. Sazegarnejad, “Channel modeling and range extension for UWB communications using directional antenna in LOS and NLOS path loss models,” in World Automation Congress (WAC 2008). Hawaii, HI, USA, September-October 2008.

H. W. Sorenson and D. L. Alspach, “Recursive Bayesian estimation using Gaussian sums,” Automatica, vol. 7, no. 4, pp. 465–479, July 1971.

S. Ali-Löytty, “Gaussian mixture filters in hybrid positioning,” Ph.D. dissertation, Tampere University of Technology, August 2009. [Online]. Available: http://URN.fi/URN:NBN:fi:tty200905191055

J. T.-H. Lo, “Finite-dimensional sensor orbits and optimal nonlinear filtering,” IEEE Transactions on Information Theory, vol. 18, no. 5, pp. 583–588, September 1972.

D. L. Alspach and H. W. Sorenson, “Nonlinear Bayesian estimation using Gaussian sum approximations,” IEEE Transactions on Automatic Control, vol. 17, no. 4, pp. 439–448, August 1972.

T. Koshizen, “The sensor selection task of the Gaussians mixture Bayes’ with regularized EM (GMB-REM) technique in robot position estimation,” in Proceedings of the 1999 IEEE International Conference on Robotics & Automation. Detroit, MI Detroit, MI Detroit, MI, USA, May 1999, pp. 2620–2625.

T. Koshizen, “The evolved Gaussian mixture Bayes’ technique using sensor selection task integrated with sensor fusion scheme in mobile robot position estimation,” in Proceedings of 1999 IEEE International Symposium on Computational Intelligence in Robotics and Automation (CIRA’99). Monterey, CA, USA, November 1999, pp. 202–207.

T. Koshizen, P. Bartlett, and A. Zelinsky, “Sensor fusion of odometry and sonar sensors by the Gaussian mixture Bayes’ technique in mobile robot position estimation,” in IEEE SMC ’99 Conference Proceedings, vol. 4. Tokyo, Japan, 1999, pp. 742–747.

S. Ali-L_ytty and N. Sirola, “Gaussian mixture filter in hybrid navigation,” in Proceedings of The European Navigation Conference GNSS 2007. Geneva, Switzerland, May 2007, pp. 831–837.

M. S. Arulampalam, S. Maskell, N. Gordon, and T. Clapp, “A tutorial on particle filters for online nonlinear/non-Gaussian Bayesian tracking,” IEEE Transactions on Signal Processing, vol. 50, no. 2, pp. 174–188, 2002.

S. Ali-Löytty, “Efficient Gaussian mixture filter for hybrid positioning,” in 2008 IEEE/ION Position Location and Navigation Symposium, Monterey, California, May 2008, pp. 60–66.

S. Ali-Löytty and N. Sirola, “Gaussian mixture filter and hybrid positioning,” in Proceedings of ION GNSS 2007, Fort Worth, Texas, September 2007, pp. 562–570.

M. Raitoharju and S. Ali-Löytty, “An adaptive derivative free method for Bayesian posterior approximation,” IEEE Signal Processing Letters, vol. 19, no. 2, pp. 87–90, February 2012.

B. D. O. Anderson and J. B. Moore, Optimal Filtering, ser. Prentice-Hall information and system sciences. Prentice-Hall, 1979.

S. Ali-Löytty, “On the convergence of the Gaussian mixture filter,” Tampere University of Technology, Institute of Mathematics, http://urn.fi/URN:NBN:fi:tty-2011041510704, Tech. Rep. Research report 89, 2008.

D. J. Salmond, “Mixture reduction algorithms for target tracking,” in IEE Colloquium on State Estimation in Aerospace and Tracking Applications. London, England, 1989, pp. 7/1–7/4.

D. Schieferdecker and M. F. Huber, “Gaussian mixture reduction via clustering,” in Proceedings of the 12th International Conference on Information Fusion (FUSION ’09). Seattle, WA, USA, 2009, pp. 1536–1543.

D. F. Crouse, P. Willett, K. Pattipati, and L. Svensson, “A look at Gaussian mixture reduction algorithms,” in Proceedings of the 14th International Conference on Information Fusion (FUSION’11). Chicago, IL, USA, 2011.

M. Kristan, D. Skočaj, and A. Leonardis, “Incremental learning with Gaussian mixture models,” in Computer Vision Winter Workshop 2008. Moravske Toplice, Slovenia, February 2008, pp. 25–32.

P. Müller, S. Ali-Löytty, M. Dashti, H. Nurminen, and R. Piché, “Gaussian mixture filter allowing negative weights and its application to positioning using signal strength measurements,” in Proceedings of the 9th Workshop on Positioning, Navigation and Communication 2012 (WPNC’12). Dresden, Germany, March 2012, pp. 71–76.

P. Müller, H. Wymeersch, and R. Piché, “UWB positioning with generalized Gaussian mixture filters,” IEEE Transactions on Mobile Computing, vol. 13, no. 10, pp. 2406–2414, October 2014.

C. M. Bishop and M. Svensén, “Robust Bayesian mixture modeling,” in Proceedings of 12th European Symposium on Artificial Neural Networks (ESANN 2004). Bruges, Belgium, April 2004, pp. 69–74.

G. J. McLachlan and D. Peel, “Robust cluster analysis via mixtures of multivariate tdistributions,” in Advances in Pattern Recognition, ser. Lecture Notes in Computer Science, A. Amin, D. Dori, P. Pudil, and H. Freeman, Eds. Springer Berlin Heidelberg, 1998, vol. 1451, pp. 658–666.

S. Ali-Löytty, N. Sirola, and R. Piché, “Consistency of three Kalman filter extensions in hybrid navigation,” in Proceedings of The European Navigation Conference GNSS 2005. Munich, Germany, Jul. 2005.

H. Nurminen, A. Ristimäki, S. Ali-Löytty, and R. Piché, “Particle filter and smoother for indoor localization,” in 2013 International Conference on Indoor Positioning and Indoor Navigation (IPIN2013). Montbeliard-Belfort, France, October 2013, pp. 137–146.

Степанов О. А. Применение теории нелинейной фильтрации в задачах обработки навигационной информации. СПб., 2003.

Степанов О. А., Торопов А. Б. Применение последовательных методов Монте-Карло с использованием процедур аналитического интегрирования при обработке навигационной информации. XII Всероссийское совещание по проблемам управления ВСПУ-2014. Институт проблем управления им. В. А. Трапезникова РАН. М., 2014. С. 3324-3337.

The authors declare that there are no conflicts of interest present.