skip to main content
10.1145/1864349.1864385acmconferencesArticle/Chapter ViewAbstractPublication PagesubicompConference Proceedingsconference-collections
research-article

A grid-based algorithm for on-device GSM positioning

Published: 26 September 2010 Publication History

Abstract

We propose a grid-based GSM positioning algorithm that can be deployed entirely on mobile devices. The algorithm uses Gaussian distributions to model signal intensity variations within each grid cell. Position estimates are calculated by combining a probabilistic centroid algorithm with particle filtering. In addition to presenting the positioning algorithm, we describe methods that can be used to create, update and maintain radio maps on a mobile device. We have implemented the positioning algorithm on Nokia S60 and Nokia N900 devices and we evaluate the algorithm using a combination of offline and real world tests. The results indicate that the accuracy of our method is comparable to state-of-the-art methods, while at the same time having significantly smaller storage requirements.

References

[1]
}}T. F. Chan, G. H. Golub, and R. J. LeVeque. Algorithms for computing the sample variance: Analysis and recommendations. The American Statistician, 37(3):242{247, 1983.
[2]
}}M. Y. Chen, T. Sohn, D. Chmelev, D. Hahnel, J. Hightower, J. Hughes, A. LaMarca, F. Potter, I. E. Smith, and A. Varshavsky. Practical metropolitan-scale positioning for GSM phones. In Proceedings of the 8th International Conference on Ubiquitous Computing (UbiComp), volume 4206 of Lecture Notes in Computer Science, pages 225--242. Springer, 2006.
[3]
}}C. Drane, M. Macnaughtan, and C. Scott. Positioning GSM telephones. Communications Magazine, IEEE, 36(4):46--54, 59, 1998.
[4]
}}B. Ferris, D. Hahnel, and D. Fox. Gaussian processes for signal strength-based location estimation. In Robotics: Science and Systems. The MIT Press, 2006.
[5]
}}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 Proceedings of the 10th annual international conference on Mobile computing and networking (MobiCom), pages 70--84. ACM, 2004.
[6]
}}J. Hightower and G. Borriello. Particle Filters for location estimation in ubiquitous computing: A case study. In Proceedings of the 6th International Conference on Ubiquitous Computing (Ubicomp), pages 88--106. Springer, 2006.
[7]
}}Juniper Research. Mobile location based services: Applications, forecasts & opportunities 2009--2014. Research report, March 2010.
[8]
}}J. Krumm and E. Horvitz. LOCADIO: Inferring motion and location from Wi-Fi signal strenghts. In Proceedings of the 1st International Conference on Mobile and Ubiquitous Systems (Mobiquitous), pages 4--14. IEEE, 2004.
[9]
}}J. Krumm and J. Platt. Minimizing calibration effort for an indoor 802.11 device location measurement system. MSR-TR-2003-82, Microsoft Research, Seattle, WA, 2003.
[10]
}}J. Kukkonen, E. Lagerspetz, P. Nurmi, and M. Andersson. BeTelGeuse: A platform for gathering and processing situational data. IEEE Pervasive Computing, 8(2):49--56, 2009.
[11]
}}H. Laitinen, J. Lahteenmaki, and T. Nordstrom. Database correlation method for GSM location. In Proceedings of the 53rd IEEE Vehicular Technology Conference (VTC). IEEE, 2001.
[12]
}}A. LaMarca, Y. Chawathe, S. Consolvo, J. Hightower, I. E. Smith, J. Scott, T. Sohn, J. Howard, J. Hughes, F. Potter, J. Tabert, P. Powledge, G. Borriello, and B. N. Schilit. Place Lab: Device positioning using radio beacons in the wild. In Proceedings of 3rd International Conference on Pervasive Computing (PERVASIVE), volume 3468, pages 116--133. Springer, 2005.
[13]
}}L. Liao, D. Fox, and H. Kautz. Extracting places and activities from GPS traces using hierarchical conditional random fields. International Journal of Robotics Research, 26(1):119--134, 2007.
[14]
}}V. Otsason, A. Varshavsky, A. LaMarca, and E. de Lara. Accurate GSM indoor localization. In Proceedings of the 7th International Conference on Ubiquitous Computing (UbiComp), volume 3660 of Lecture Notes in Computer Science, pages 141--158. Springer, 2005.
[15]
}}T. Roos, P. Myllymaki, and H. Tirri. A statistical modeling approach to location estimation. IEEE Transactions on Mobile Computing, 1(1):59--69, 2002.
[16]
}}T. Roos, P. Myllymaki, H. Tirri, P. Misikangas, and J. Sievanen. A probabilistic approach to WLAN user location estimation. International Journal of Wireless Information Networks, 9(3):155--164, 2002.
[17]
}}A. Schwaighofer, M. Grigoras, V. Tresp, and C. Hoffmann. GPPS: A Gaussian process positioning system for cellular networks. In Advances in Neural Information Processing Systems 16. MIT Press, 2003.
[18]
}}T. Sohn, A. Varshavsky, A. LaMarca, M. Y. Chen, T. Choudhury, I. Smith, S. Consolvo, J. Hightower, W. G. Griswold, and E. de Lara. Mobility detection using everyday GSM traces. In Proceedings of the 8th International Conference on Ubiquitous Computing (Ubicomp), pages 212--224, 2006.
[19]
}}S. Thrun, D. Fox, W. Burgard, and F. Dellaert. Robust Monte Carlo localization for Mobile Robots. Artificial Intelligence, 128:99--141, 2001.
[20]
}}A. Varshavsky, E. de Lara, J. Hightower, A. LaMarca, and V. Otsason. GSM indoor localization. Pervasive and Mobile Computing, 3:698--720, 2007.
[21]
}}A. Varshavsky, A. LaMarca, J. Hightower, and E. de Lara. The SkyLoc floor localization system. In Proceedings of the 5th Annual IEEE International Conference on Pervasive Computing and Communications (PerCom), pages 125--134. IEEE, 2007.
[22]
}}T. Vincenty. Direct and Inverse Solutions of Geodesics on the Ellipsoid with Application of Nested Equations. Survey Review, 23(176):88--93, 1975.
[23]
}}Z. Wu, C. Li, J. K.-Y. Ng, and K. R. Leung. Location estimation via support vector regression. IEEE Transactions on Mobile Computing, 6(3):311--321, 2007.

Cited By

View all
  • (2022)A tale of three datasetsCommunications of the ACM10.1145/346267265:3(67-74)Online publication date: 23-Feb-2022
  • (2022)Why and What?Wireless Localization Techniques10.1007/978-3-031-21178-2_1(1-10)Online publication date: 9-Nov-2022
  • (2020)RF Fingerprints Prediction for Cellular Network Positioning: A Subspace Identification ApproachIEEE Transactions on Mobile Computing10.1109/TMC.2019.289327819:2(450-465)Online publication date: 1-Feb-2020
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
UbiComp '10: Proceedings of the 12th ACM international conference on Ubiquitous computing
September 2010
366 pages
ISBN:9781605588438
DOI:10.1145/1864349
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

In-Cooperation

  • University of Florida: University of Florida

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 26 September 2010

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. GSM
  2. energy efficiency
  3. fingerprinting
  4. mobile computing
  5. particle filtering
  6. positioning

Qualifiers

  • Research-article

Conference

Ubicomp '10
Ubicomp '10: The 2010 ACM Conference on Ubiquitous Computing
September 26 - 29, 2010
Copenhagen, Denmark

Acceptance Rates

UbiComp '10 Paper Acceptance Rate 39 of 202 submissions, 19%;
Overall Acceptance Rate 764 of 2,912 submissions, 26%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)11
  • Downloads (Last 6 weeks)0
Reflects downloads up to 09 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2022)A tale of three datasetsCommunications of the ACM10.1145/346267265:3(67-74)Online publication date: 23-Feb-2022
  • (2022)Why and What?Wireless Localization Techniques10.1007/978-3-031-21178-2_1(1-10)Online publication date: 9-Nov-2022
  • (2020)RF Fingerprints Prediction for Cellular Network Positioning: A Subspace Identification ApproachIEEE Transactions on Mobile Computing10.1109/TMC.2019.289327819:2(450-465)Online publication date: 1-Feb-2020
  • (2019)Uncovering mobile infrastructure in developing countries with crowdsourced measurementsProceedings of the Tenth International Conference on Information and Communication Technologies and Development10.1145/3287098.3287113(1-11)Online publication date: 4-Jan-2019
  • (2018)Location Information Quality: A ReviewSensors10.3390/s1811399918:11(3999)Online publication date: 16-Nov-2018
  • (2018)Pedestrian navigation and GPS deteriorationsProceedings of the 30th Australian Conference on Computer-Human Interaction10.1145/3292147.3292154(266-277)Online publication date: 4-Dec-2018
  • (2018)Visualizing Location Uncertainty on Mobile DevicesProceedings of the ACM on Interactive, Mobile, Wearable and Ubiquitous Technologies10.1145/31917622:1(1-22)Online publication date: 26-Mar-2018
  • (2018)Large-scale Wireless Fingerprints Prediction for Cellular Network PositioningIEEE INFOCOM 2018 - IEEE Conference on Computer Communications10.1109/INFOCOM.2018.8485957(1007-1015)Online publication date: Apr-2018
  • (2017)Identifying Value in Crowdsourced Wireless Signal MeasurementsProceedings of the 26th International Conference on World Wide Web10.1145/3038912.3052563(607-616)Online publication date: 3-Apr-2017
  • (2016)An empirical study on the regularity of route mobilityProceedings of the 2016 ACM International Joint Conference on Pervasive and Ubiquitous Computing: Adjunct10.1145/2968219.2968420(1418-1425)Online publication date: 12-Sep-2016
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media