Journal Home > Volume 2 , issue 4

In this paper we present a large scale, passive positioning system that can be used for approximate localization in Global Positioning System (GPS) denied/spoofed environments. This system can be used for detecting GPS spoofing as well as for initial position estimation for input to other GPS free positioning and navigation systems like Terrain Contour Matching (TERCOM). Our Location inference through Frequency Modulation (FM) Signal Integration and estimation (LoSI) system is based on broadcast FM radio signals and uses Received Signal Strength Indicator (RSSI) obtained using a Software Defined Radio (SDR). The RSSI thus obtained is used for indexing into an estimated model of expected FM spectrum for the entire United States. We show that with the hardware for data acquisition, a single point resolution of around 3 miles and associated algorithms, we are capable of positioning with errors as low as a single pixel (more precisely around 0.12 mile). The algorithm uses a large-scale model estimation phase that computes the expected FM spectrum in small rectangular cells (realized using geohashes) across the Contiguous United States (CONUS). We define and use Dominant Channel Descriptor (DCD) features, which can be used for positioning using time varying models. Finally we use an algorithm based on Euclidean nearest neighbors in the DCD feature space for position estimation. The system first runs a DCD feature detector on the observed spectrum and then solves a subset query formulation to find Inference Candidates (IC). Finally, it uses a simple Euclidean nearest neighbor search on the ICs to localize the observation. We report results on 1500 points across Florida using data and model estimates from 2015 and 2017. We also provide a Bayesian decision theoretic justification for the nearest neighbor search.


menu
Abstract
Full text
Outline
About this article

LoSI: Large Scale Location Inference Through FM Signal Integration and Estimation

Show Author's information Tathagata Mukherjee( )Piyush KumarDebdeep PatiErik BlaschEduardo PasiliaoLiqin Xu
Department of Computer Science, University of Alabama in Huntsville, Huntsville, AL 35806, USA.
CompGeom Inc., Tallahassee, FL 32311, USA.
Department of Statistics, Texas A&M University, College Station, TX 77843, USA.
Air Force Research Laboratory, Rome, NY 13441, USA.
Air Force Research Laboratory, Shalimar, FL 32579, USA.
CompGeom Inc., Tallahassee, FL 32579, USA.

Abstract

In this paper we present a large scale, passive positioning system that can be used for approximate localization in Global Positioning System (GPS) denied/spoofed environments. This system can be used for detecting GPS spoofing as well as for initial position estimation for input to other GPS free positioning and navigation systems like Terrain Contour Matching (TERCOM). Our Location inference through Frequency Modulation (FM) Signal Integration and estimation (LoSI) system is based on broadcast FM radio signals and uses Received Signal Strength Indicator (RSSI) obtained using a Software Defined Radio (SDR). The RSSI thus obtained is used for indexing into an estimated model of expected FM spectrum for the entire United States. We show that with the hardware for data acquisition, a single point resolution of around 3 miles and associated algorithms, we are capable of positioning with errors as low as a single pixel (more precisely around 0.12 mile). The algorithm uses a large-scale model estimation phase that computes the expected FM spectrum in small rectangular cells (realized using geohashes) across the Contiguous United States (CONUS). We define and use Dominant Channel Descriptor (DCD) features, which can be used for positioning using time varying models. Finally we use an algorithm based on Euclidean nearest neighbors in the DCD feature space for position estimation. The system first runs a DCD feature detector on the observed spectrum and then solves a subset query formulation to find Inference Candidates (IC). Finally, it uses a simple Euclidean nearest neighbor search on the ICs to localize the observation. We report results on 1500 points across Florida using data and model estimates from 2015 and 2017. We also provide a Bayesian decision theoretic justification for the nearest neighbor search.

Keywords:

Global Positioning System (GPS)-free positioning, Frequency Modulation (FM) radio, signals of opportunity
Received: 05 May 2019 Revised: 03 June 2019 Accepted: 04 June 2019 Published: 05 August 2019 Issue date: December 2019
References(100)
[1]
H. C. Chu and R. H. Jan, A GPS-less, outdoor, self-positioning method for wireless sensor networks, Ad Hoc Networks, vol. 5, no. 5, pp. 547-557, 2007.
[2]
A. Popleteev, Indoor positioning using FM radio signals, PhD dissertation, University of Trento, Trento, Italy, 2011.
[3]
J. Krumm, G. Cermak, and E. Horvitz, RightSPOT: A novel sense of location for a smart personal object, in UbiComp 2003: Ubiquitous Computing, A. K. Dey, A. Schmidt, and J. F. McCarthy, eds. Springer, 2003, pp. 36-43.
[4]
F. J. Perez-Grau, R. Ragel, F. Caballero, A. Viguria, and A. Ollero, An architecture for robust UAV navigation in GPS-denied areas, Journal of Field Robotics, vol. 35, no. 1, pp. 121-145, 2018.
[5]
Z. H. Wang, E. Blasch, G. S. Chen, D. Shen, X. P. Lin, and K. Pham, A low-cost, near-real-time two-UAS-based UWB emitter monitoring system, IEEE Aerospace and Electronic Systems Magazine, vol. 30, no. 11, pp. 4-11, 2015.
[6]
Q. Miao, B. Q. Huang, and B. Jia, Estimating distances via received signal strength and connectivity in wireless sensor networks, arXiv:1801.09350, 2018.
[7]
J. Hightower and G. Borriello, Location systems for ubiquitous computing, Computer, vol. 34, no. 8, pp. 57-66, 2001.
[8]
K. Mohta, M. Watterson, Y. Mulgaonkar, S. K. Liu, C. Qu, A. Makineni, K. Saulnier, K. Sun, A. Zhu, J. Delmerico, et al., Fast, autonomous flight in GPS-denied and cluttered environments, Journal of Field Robotics, vol. 35, no. 1, pp. 101-120, 2018.
[9]
M. Hazas, J. Scott, and J. Krumm, Location-aware computing comes of age, Computer, vol. 37, no. 2, pp. 95-97, 2004.
[10]
V. W. Zheng, H. Cao, S. H. Gao, A. Adhikari, M. Lin, and K. C. C. Chang, Cold-start heterogeneous-device wireless localization, in Proc. 30th AAAI Conf. Artificial Intelligence, Phoenix, AZ, USA, 2016, pp. 1429-1435.
[11]
E. Martin, O. Vinyals, G. Friedland, and R. Bajcsy, Precise indoor localization using smart phones, in Proc. 18th ACM Int. Conf. Multimedia, Firenze, Italy, 2010, pp. 787-790.
[12]
A. Varshavsky, E. De Lara, J. Hightower, A. LaMarca, and V. Otsason, GSM indoor localization, Pervasive and Mobile Computing, vol. 3, no. 6, pp. 698-720, 2007.
[13]
Y. Chen, D. Lymberopoulos, J. Liu, and B. Priyantha, FM-based indoor localization, in Proc. 10th Int. Conf. Mobile Systems, Applications, and Services, Low Wood Bay, UK, 2012, pp. 169-182.
[14]
P. Misra and P. Enge, Global Positioning System: Signals, Measurements and Performance, 2nd ed. Lincoln, MA, USA: Ganga-Jamuna Press, 2006.
[15]
A. Cameron, GLONASS gone… Then back, , 2016.
[16]
GPS is a time bomb, , 2016.
[17]
S. Cole, Backup PNT methods are essential for GPS-denied environments, , 2016.
[18]
M. Pomerleau, No GPS signal, no problem: Army works on ops in denied regions, , 2017.
[19]
T. Hawks and B. McMahon, Time warfare: Threats to GPS aren’t just about navigation and positioning, , 2017.
[20]
D. Hambling, Ships fooled in GPS spoofing attack suggest Russian cyberweapon, , 2017.
[21]
M. Pomerleau, Threat from Russian UAV jamming real, officials say, , 2016.
[22]
R. Beckhusen, Russia plans to turn civilian cell phone towers into cruise missile jammers, , 2016.
[23]
DARPA, Beyond GPS: 5 next-generation technologies for Positioning, Navigation and Timing (PNT), , 2014.
[24]
J. Lendino, DARPA to re-invent GPS navigation without the use of satellites, , 2015.
[25]
SBIR, GPS-denied positioning using networked communications, , 2015.
[26]
R. Adams, DOD units, universities test air platforms in GPS-denied environment, , 2017.
[27]
F. S. Gady, Is the pentagon getting ready to dump GPS, , 2017.
[28]
J. LaMance, J. DeSalas, and J. Jarvinen, Assisted GPS: A low-infrastructure approach, , 2002.
[29]
S. Zhao, Y. M. Chen, H. Y. Zhang, and J. A. Farrell, Differential GPS aided inertial navigation: A contemplative realtime approach, in Proc. IFAC World Congress, Cape Town, South Africa, 2014, pp. 8959-8964.
[30]
J. P. Golden, Terrain contour matching (TERCOM): A cruise missile guidance aid, in Proc. SPIE 0238, Image Processing for Missile Guidance, San Diego, CA, USA, 1980.
[31]
A. L. Majdik, D. Verda, Y. Albers-Schoenberg, and D. Scaramuzza, Air-ground matching: Appearance-based GPS-denied urban localization of micro aerial vehicles, Journal of Field Robotics, vol. 32, no. 7, pp. 1015-1039, 2015.
[32]
A. Srinivasan and J. Wu, A survey on secure localization in wireless sensor networks, , 2007.
[33]
S. H. Fang, J. C. Chen, H. R. Huang, and T. N. Lin, Is FM a RF-based positioning solution in a metropolitan-scale environment? A probabilistic approach with radio measurements analysis, IEEE Transactions on Broadcasting, vol. 55, no. 3, pp. 577-588, 2009.
[34]
V. Otsason, A. Varshavsky, A. LaMarca, and E. de Lara, Accurate GSM indoor localization, in Proc. 7th Int. Conf. Ubiquitous Computing, Berlin, Heidelberg, 2005, pp. 141-158.
[35]
A. Savvides, C. C. Han, and M. B. Strivastava, Dynamic fine-grained localization in Ad-Hoc networks of sensors, in Proc. 7th Annu. Int. Conf. Mobile Computing and Networking, Rome, Italy, 2001, pp. 166-179.
[36]
R. Fuller, Tutorial on location determination by RF means, in Mobile Entity Localization and Tracking in GPS-less Environments, R. Fuller and X. D. Koutsoukos, eds. Springer, 2009, pp. 213-234.
[37]
L. Cong and W. H. Zhuang, Non-line-of-sight error mitigation in TDOA mobile location, in IEEE Global Telecommunications Conf., San Antonio, TX, USA, 2001, pp. 680-684.
[38]
J. V. Stoep, Design and implementation of reliable localization algorithms using received signal strength, PhD dissertation, University of Washington, Seattle, WA, USA, 2009.
[39]
A. Popleteev, V. Osmani, O. Mayora, and A. Matic, Indoor localization using audio features of FM radio signals, in International and Interdisciplinary Conference on Modeling and Using Context, M. Beigl, H. Christiansen, T. R. Roth-Berghofer, A. Kofod-Petersen, K. R. Coventry, and H. R. Schmidtke, eds. Springer, 2011, pp. 246-249.
[40]
T. S. Rappaport, Wireless Communications: Principles and Practice. Upper Saddle River, NJ, USA: Prentice Hall, 1996.
[41]
E. Blasch, S. Ravela, and A. Aved, Handbook of Dynamic Data Driven Applications Systems. Springer, 2018.
[42]
T. Mukherjee, A. Adolfsson, E. L. Pasiliao Jr, and P. Kumar, Hierarchical learning for FM radio based aerial localization using RSSI, in Proc. 2nd GNU Radio Conf., 2017.
[43]
H. W. Silver, The ARRL Handbook for Radio Communications, 92nd ed. Newington, CT, USA: ARRL, 2015.
[44]
A. Khattab, Y. A. Fahmy, and A. Abdel Wahab, High accuracy GPS-free vehicle localization framework via an ins-assisted single RSU, International Journal of Distributed Sensor Networks, .
[45]
S. Waterman, North Korean jamming of GPS shows system’s weakness, , 2012.
[46]
M. L. Psiaki and T. E. Humphreys, GNSS spoofing and detection, Proceedings of the IEEE, vol. 104, no. 6, pp. 1258-1270, 2016.
[47]
G. M. Djuknic and R. E. Richton, Geolocation and assisted GPS, Computer, vol. 34, no. 2, pp. 123-125, 2001.
[48]
E. K. Lee, S. Yang, S. Y. Oh, and M. Gerla, RF-GPS: RFID assisted localization in VANETs, in IEEE 6th Int. Conf. Mobile Adhoc and Sensor Systems, Macau, China, 2009, pp. 621-626.
[49]
E. D. Kaplan, Understanding GPS: Principles and Applications. Norwood, MA, USA: Artech House, 1996.
[50]
J. A. Farrell, T. D. Givargis, and M. J. Barth, Real-time differential carrier phase GPS-aided INS, IEEE Transactions on Control Systems Technology, vol. 8, no. 4, pp. 709-721, 2000.
[51]
N. C. Talbot, M. T. Allison, and M. E. Nichols, Centimeter accurate global positioning system receiver for on-the-fly real-time kinematic measurement and control, US Patent 5519620, May 21, 1996.
[52]
B. W. Parkinson, M. L. O’connor, G. H. Elkaim, and T. Bell, Method and system for automatic control of vehicles based on carrier phase differential GPS, US Patent 6052647, April 18, 2000.
[53]
M. L. O’Connor, Carrier-phase differential GPS for automatic control of land vehicles, PhD dissertation, Stanford University, Stanford, CA, USA, 1997.
[54]
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, 2005.
[55]
D. G. Borkowski, H. F. Fung, H. F. Habal, K. Chao, S. Kai, and D. P. Robert II, Cellular network-based location system, US Patent 5519760, May 21, 1996.
[56]
O. S. Oguejiofor, V. N. Okorogu, A. Adewale, and B. O. Osuesu, Outdoor localization system using RSSI measurement of wireless sensor network, International Journal of Innovative Technology and Exploring Engineering, vol. 2, no. 2, pp. 1-6, 2013.
[57]
G. Q. Mao, B. Fidan, and B. D. O. Anderson, Wireless sensor network localization techniques, Computer Networks, vol. 51, no. 10, pp. 2529-2553, 2007.
[58]
M. Ibrahim and M. Youssef, Cellsense: An accurate energy-efficient GSM positioning system, IEEE Transactions on Vehicular Technology, vol. 61, no. 1, pp. 286-296, 2012.
[59]
J. A. McEllroy, J. F. Raquet, and M. A. Temple, Use of a software radio to evaluate signals of opportunity for navigation, in Proc. 19th Int. Technical Meeting of the Satellite Division of the Institute of Navigation (ION GNSS 2006), 2006.
[60]
J. Barnes, C. Rizos, J. L. Wang, D. Small, G. Voigt, and N. Gambale, Locata: A new positioning technology for high precision indoor and outdoor positioning, in Proc. 2003 Int. Symp. GPS/GNSS, Tokyo, Japan, 2003, pp. 9-18.
[61]
M. M. Atia, A. Noureldin, and M. J. Korenberg, Dynamic online-calibrated radio maps for indoor positioning in wireless local area networks, IEEE Transactions on Mobile Computing, vol. 12, no. 9, pp. 1774-1787, 2013.
[62]
Y. Chen, D. Lymberopoulos, J. Liu, and B. Priyantha, Indoor localization using FM signals, IEEE Transactions on Mobile Computing, vol. 12, no. 8, pp. 1502-1517, 2013.
[63]
H. Abdelnasser, R. Mohamed, A. Elgohary, M. Farid Alzantot, H. Wang, S. Sen, R. R. Choudhury, and M. Youssef, SemanticSLAM: Using environment landmarks for unsupervised indoor localization, IEEE Transactions on Mobile Computing, vol. 15, no. 7, pp. 1770-1782, 2016.
[64]
C. Laoudias, G. Constantinou, M. Constantinides, S. Nicolaou, D. Zeinalipour-Yazti, and C. G. Panayiotou, The airplace indoor positioning platform for android smartphones, in IEEE 13th Int. Conf. Mobile Data Management, Bengaluru, India, 2012, pp. 312-315.
[65]
L. Petrou, G. Larkou, C. Laoudias, D. Zeinalipour-Yazti, and C. G. Panayiotou, Demonstration abstract: Crowdsourced indoor localization and navigation with anyplace, in Proc. 13th Int. Symp. Information Processing in Sensor Networks, Berlin, Germany, 2014, pp. 331-332.
[66]
A. Konstantinidis, G. Chatzimilioudis, D. Zeinalipour-Yazti, P. Mpeis, N. Pelekis, and Y. Theodoridis, Privacy-preserving indoor localization on smartphones, IEEE Transactions on Knowledge and Data Engineering, vol. 27, no. 11, pp. 3042-3055, 2015.
[67]
FCC, FCC wireless 911 requirements, , 2001.
[68]
M. Azizyan, I. Constandache, and R. R. Choudhury, SurroundSense: Mobile phone localization via ambience fingerprinting, in Proc. 15th Annu. Int. Conf. Mobile Computing and Networking, Beijing, China, 2009, pp. 261-272.
[69]
H. Aly and M. Youssef, Dejavu: An accurate energy-efficient outdoor localization system, in Proc. 21st ACM SIGSPATIAL Int. Conf. Advances in Geographic Information Systems, Orlando, Florida, 2013, pp. 154-163.
[70]
C. C. Counselman III and T. D. Hall, Instantaneous radiopositioning using signals of opportunity, US Patent 6492945, December 10, 2002.
[71]
C. Yang, T. Nguyen, and E. Blasch, Mobile positioning via fusion of mixed signals of opportunity, IEEE Aerospace and Electronic Systems Magazine, vol. 29, no. 4, pp. 34-46, 2014.
[72]
M. Ocana, L. M. Bergasa, M. A. Sotelo, J. Nuevo, and R. Flores, Indoor robot localization system using WiFi signal measure and minimizing calibration effort, in Proc. IEEE Int. Symp. Industrial Electronics, Dubrovnik, Croatia, 2005, pp. 1545-1550.
[73]
V. Moghtadaiee, A. G. Dempster, and S. Lim, Indoor localization using FM radio signals: A fingerprinting approach, in 2011 Int. Conf. Indoor Positioning and Indoor Navigation, Guimaraes, Portugal, 2011, pp. 1-7.
[74]
L. Engelbrecht and A. Weinberg, Location determination system and method using television broadcast signals, US Patent 5510801, April 23, 1996.
[75]
S. P. Tarzia, P. A. Dinda, R. P. Dick, and G. Memik, Indoor localization without infrastructure using the acoustic background spectrum, in Proc. 9th Int. Conf. Mobile Systems, Applications, and Services, Bethesda, MD, USA, 2011, pp. 155-168.
[76]
M. Hazas and A. Hopper, Broadband ultrasonic location systems for improved indoor positioning, IEEE Transactions on Mobile Computing, vol. 5, no. 5, pp. 536-547, 2006.
[77]
V. W. Zheng, E. W. Xiang, Q. Yang, and D. Shen, Transferring localization models over time, in Proc. 23rd AAAI Conf. Artificial Intelligence, Chicago, IL, USA, 2008, pp. 1421-1426.
[78]
V. W. Zheng, S. J. Pan, Q. Yang, and J. J. Pan, Transferring multi-device localization models using latent multi-task learning, in Proc. 23rd AAAI Conf. Artificial Intelligence, Chicago, IL, USA, 2008, pp. 1427-1432.
[79]
A. Youssef, J. Krumm, E. Miller, G. Cermak, and E. Horvitz, Computing location from ambient FM radio signals [commercial radio station signals], in IEEE Wireless Communications and Networking Conf., New Orleans, LA, USA, 2005, pp. 824-829.
[80]
ComStudy, , 2016.
[81]
R, Margolies, R. Becker, S. Byers, S. Deb, R. Jana, S. Urbanek, and C. Volinsky, Can you find me now? Evaluation of network-based localization in a 4G LTE network, in IEEE Conf. Computer Communications, Atlanta, GA, USA, 2017, pp. 1-7.
[82]
RTL-SDR, , 2017.
[83]
Gustavo Niemeyer, Geohash, , 2019.
[84]
A. Fox, C. Eichelberger, J. Hughes, and S. Lyon, Spatio-temporal indexing in non-relational distributed databases, in 2013 IEEE Int. Conf. Big Data, Silicon Valley, CA, USA, 2013, pp. 291-299.
[85]
J. O’Rourke, Computational Geometry in C, 2nd ed. New York, NY, USA: Cambridge University Press, 1998.
[86]
M. De Berg, M. Van Kreveld, M. Overmars, and O. C. Schwarzkopf, Computational geometry, in Computational Geometry: Algorithms and Applications, M. de Berg, O. Cheong, M. van Kreveld, and M. Overmars, eds. Springer, 2000, pp. 1-17.
[87]
T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, 3rd ed. Cambridge, MA, USA: MIT Press, 2009.
[88]
M. Charikar, P. Indyk, and R. Panigrahy, New algorithms for subset query, partial match, orthogonal range searching, and related problems, in Automata, Languages and Programming: 29th International Colloquium, Málaga, Spain, 2002, pp. 451-462.
[89]
E. L. Lehmann and G. Casella, Theory of Point Estimation. New York, NY, USA: Springer Science & Business Media, 2006.
[90]
W. Rudin, Principles of Mathematical Analysis, 3rd ed. New York, NY, USA: McGraw-Hill, 1964.
[91]
G. Casella and R. L. Berger, Statistical Inference, 2nd ed. Pacific Grove, CA, USA: Duxbury, 2001.
[92]
Z. L. Wu, C. H. Li, J. K. Y. Ng, and K. R. P. Leung, Location estimation via support vector regression, IEEE Transactions on Mobile Computing, vol. 6, no. 3, pp. 311-321, 2007.
[93]
R. H. Myers, D. C. Montgomery, G. G. Vining, and T. J. Robinson, Generalized Linear Models: With Applications in Engineering and the Sciences, 2nd ed. New York, NY, USA: John Wiley & Sons, 2012.
[94]
C. R. Rao, Information and the accuracy attainable in the estimation of statistical parameters, in Breakthroughs in Statistics, S. Kotz and N. L. Johnson, eds. Springer, 1992, pp. 235-247.
[95]
C. Fritsche, U. Orguner, E. Özkan, and F. Gustafsson, On the Cramer-Rao lower bound under model mismatch, in 2015 IEEE Int. Conf. Acoustics, Speech and Signal Processing (ICASSP), Brisbane, Australia, 2015, pp. 3986-3990.
[96]
P. J. Huber, Robust estimation of a location parameter, in Breakthroughs in Statistics, S. Kotz and N. L. Johnson, eds. New York, NY, USA: Springer, 1992, pp. 492-518.
[97]
R. O. Duda, P. E. Hart, and D. G. Stork, Pattern Classification. Wiley, 1973.
[98]
K. P. Murphy, Machine Learning: A Probabilistic Perspective. Cambridge, MA, USA: MIT Press, 2012.
[99]
J. A. Shaw, Radiometry and the Friis transmission equation, American Journal of Physics, vol. 81, no. 1, pp. 33-37, 2013.
[100]
T. Vincenty, Direct and inverse solutions of geodesics on the ellipsoid with application of nested equations, Survey Review, vol. 23, no. 176, pp. 88-93, 1975.
Publication history
Copyright
Rights and permissions

Publication history

Received: 05 May 2019
Revised: 03 June 2019
Accepted: 04 June 2019
Published: 05 August 2019
Issue date: December 2019

Copyright

© The author(s) 2019

Rights and permissions

The articles published in this open access journal are distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/).

Reprints and Permission requests may be sought directly from editorial office.

Return