Taking Positioning Indoors - Inside GNSS - Global Navigation Satellite Systems Engineering, Policy, and Design

Taking Positioning Indoors

Wireless local area networks (WLANs), popularly known as Wi-Fi, were originally designed for data applications. Over the past decade or so, WLAN infrastructure has been implemented for high-speed wireless Internet access in homes, “hot-spots,” university campuses, and corporate buildings. Hundreds of millions of Wi-Fi access points (APs) are deployed in major urban areas worldwide.

Wireless local area networks (WLANs), popularly known as Wi-Fi, were originally designed for data applications. Over the past decade or so, WLAN infrastructure has been implemented for high-speed wireless Internet access in homes, “hot-spots,” university campuses, and corporate buildings. Hundreds of millions of Wi-Fi access points (APs) are deployed in major urban areas worldwide.

Today, in the lead author’s lab on the third floor of the Atwater Kent Laboratory at the Worcester Polytechnic Institute, we can read the addresses of 48 Wi-Fi access points within range of our Wi-Fi–capable devices.

Wardriving or access point mapping is a term commonly used for the process of locating Wi-Fi APs while moving around an area and building a database that can be leveraged later for Wi-Fi localization.

In 2000, three years after release of the first IEEE 802.11 WLAN standard, articles describing the use of Wi-Fi signals for indoor geolocation appeared in the research literature. During the past few years, Wi-Fi positioning or localization has found its way in metrowide positioning systems.

GPS was not designed for indoor applications and does not perform well in indoor and dense urban areas. Wi-Fi localization complements GPS positioning by providing robust indoor coverage, reduction in time to fix, reduced power consumption, and resistance to interference. GPS complements Wi-Fi by providing outdoor coverage and a universal coordinate reference frame.

Emerging “smart” devices, such as Apple’s iPhone, use Wi-Fi localization technology to complement GPS and cell tower localization in numerous everyday consumer applications, particularly in metropolitan areas. Applications range from social networking to tagging photos or videos with the corresponding location information. This animation shows the density of daily Skyhook location requests in New York City, per square kilometer per hour.

In this article, we describe the evolution of the Wi-Fi localization technology with particular emphasis on its recent application in smart devices. We describe how this technology evolved out of time-of-arrival (TOA)-based GPS technology and how these two technologies are intertwined to address the needs of rapidly expanding consumer applications.

Wi-Fi: From Data Transmission to Localization
Since its inception in the 1980s, Wi-Fi has become one of the wonders of the wireless revolution, nurturing ground-breaking innovations in popular applications. Always seeking higher data rates (now on the order of 100 Mbps), Wi-Fi users employ the technology for wireless Internet access and the ever-growing multimedia applications that it supports.

These Internet applications are commonly used in indoor areas, where extensive multipath conditions require robust methods to achieve high data rates. As a result, WLANs introduced the first popular commercial application of spread spectrum technology, orthogonal frequency division multiplexing (OFDM), and more recently multi-input multi-output (MIMO) antenna systems.

. . .

The Emergence of Wi-Fi Localization
In the second half of 1990s the Defense Advanced Research Projects Agency (DARPA) launched its small unit operation situation awareness system (SUO/SAS) program aiming at one-meter accuracy for indoor geolocation in military and public safety operations.

About the same time, venture capitalists started funding startup companies such as PinPoint in Woburn, Massachusetts, and WhereNet, based in Santa Clara, California. Both were seeking to develop and implement indoor geolocation technologies with accuracies comparable to those required for SUO/SAS.

. . .

Wi-Fi Localization: TOA versus RSS
The idea of Wi-Fi localization created substantial enthusiasm in the industry. Various companies filed numerous patents targeting TOA-based indoor geolocation, and the general idea of using a wireless networking infrastructure for associated applications spread to standardization activities such as IEEE 802.15.3 for UWB communications and IEEE 802.15.4 for sensor networks using ZigBee technology.

Although TOA-based Wi-Fi localization uses an existing infrastructure, designers still need to modify the mobile devices’ hardware to extract the TOA estimate from a received Wi-Fi signal. Moreover, implementation of a precision TOA-based system faces the same multipath challenges encountered previously, demanding complex algorithms and solutions.

. . .

RTLS: Indoor Tracking Using Wi-Fi Signals
The first generation of RSS-based RTLS products were software programs running on laptops and palm-top computers equipped with Wi-Fi devices used for indoor tracking applications. The system included a localization software and a graphical user interface (GUI). The localization software operated in two modes: data collection, in which the user builds up the reference database, and localization, when the software locates a terminal based on the relative strengths of RSS readings. The GUI in the mobile devices shows the map of building and estimated location of the terminal.

. . .

WPS: A Software GPS
In metrowide Wi-Fi localization, a database is collected by wardriving the streets of a metropolitan area, using GPS to tag the location and time of measurements. Later, when a WPS mobile terminal reads the RSS of surrounding Wi-Fi access points, it sends a request to a server to calculate the terminal’s location by comparing its RSS readings with the database and previous GPS readings using a pattern-recognition algorithm.

. . .

Evolution of Hybrid Localization
One of the fundamental advantages of WPS is that it can be used as a standalone software solution for netbooks and laptops when they are not equipped with GPS or cell phone chipsets. This solution is natural, because netbooks and laptops use Wi-Fi chipsets to establish Internet connections. When a Wi-Fi network is available, WPS works.

Smart phones have cellular network connections as well as Wi-Fi chipsets. Wi-Fi signals from hot spots, home routers, and public access and enterprise wireless networks cover most of the indoor and urban areas where Internet applications are commonly used. In locales such as interstate highways, where Wi-Fi signals may not be available all the time, less accurate cell-tower localization can complement this coverage.

. . .

Database Collection and Algorithms
The size of a Wi-Fi AP database can be huge compared to the database of a RTLS system in a single building. On a national basis, the collection procedure requires many wardrivers across many metropolitan areas.

In general the distribution of the actual Wi-Fi access points in metropolitan areas forms a stochastic process with particular spatial and temporal characteristics, because the number of the access points and their locations are constantly changing. During any given time interval, new access points are installed and some old access points are re-located or even disestablished.

. . .

Wi-Fi localization is emerging as a new technology that complements GPS in coverage, time to fix, and power consumption. This began with the introduction of RTLS technology tailored for more precise indoor applications in specific buildings and then extended to WPS technology with less rigorous requirements for accuracy but a wider geographic coverage— i.e., a metropolitan area.

RTLS is currently combined with GPS to provide accurate indoor tracking and coarser outdoor tracking when the asset or personnel is moving between two specific building destinations. WPS is integrated with GPS to provide for a comprehensive coverage in numerous everyday consumer applications. To extend the Wi-Fi localization applications to the military and public safety, we need to understand the effects of electromagnetic and radio frequency interference in this technology to have an optimum solution for its integration with GPS techniques.

For the complete story, including figures, graphs, and images, please download the PDF of the article, above.

The authors would like to thank Dr. Pratap Misra of Mitre Corporation, for the careful review, comments and discussions, Glen Gibbons, and Dr. Allen Levesque for editorial comments, and Richard Sutton of Skyhook Wireless for providing the video used on the website of the magazine.

Additional Resources
[1] Alsindi, N., and K. Pahlavan, “Cooperative Localization Bounds for Indoor Ultra Wideband Wireless Sensor Networks,” EURASIP Journal on Advances in Signal Processing: special issue on Cooperative Localization in Wireless Ad Hoc and Sensor Networks, vol. 2008, article ID 852509, pp. 1–13, April, 2008
[2] Bahl, P. and V. Padmanabhan, “RADAR: an In-Building RF-based User Location and Tracking System,” Proceedings of IEEE INFOCOM, vol. 2, pp.775–784, Israel, March 2000
[3] Cheng, Y. C., and Y.Chawathe, A. LaMarca, and J.Krumm, “Accuracy Characterization for Metropolitan-scale Wi-Fi Localization,” Proceedings of Mobisys 2005, pp. 233–245, 2005
[4] Hatami, A., and K. Pahlavan, “A Comparative Performance Evaluation of RSS-Based Positioning Algorithms Used in WLAN Networks,” Proceedings of IEEE Wireless Communications and Networking Conference, vol. 4, pp. 2331–2337, March 2005
[5] Li, X. and K. Pahlavan, M. Latva-aho, and M. Ylianttila, “Indoor Geolocation Using OFDM Signals in HIPERLAN/2 Wireless LANs,” Proceedings of IEEE PIMRC, vol.2, pp. 1449–1453, London, September 2000
[6] Pahlavan, K., and F. Akgul, M. Heidari, A. Hatami, J. Elwell, and R. Tingley “Indoor Geolocation in the Absence of Direct Path,” IEEE Wireless Communications, vol. 13, no. 6, pp. 50–58, December 2006
[7] Pahlavan, K., and P. Krishnamurthy, and J. Beneat, “Wideband Radio Propagation Modeling for Indoor Geolocation Applications,” IEEE Communications Magazine, pp.60–65, April 1998
[8] Pahlavan, K., and X. Li, and J. Makela, “Indoor Geolocation Science and Technology,” IEEE Communications Magazine, vol. 40, no. 2, pp. 112–118, February 2002
[9] Qi, Y., and H. Kobayashi, “On Relation among Time Delay and Signal Strength Based Geolocation Methods,” Proceedings of IEEE Global Telecommunications Conference, vol. 7(1-5), pp. 4079–4083, Dececember 2003
[10] Roos, T., and P. Myllymaki, H. Tirri, P. Miskangas, and J. Sievanen, “A Probabilistic Approach to WLAN User Location Estimation,” International Journal of Wireless Information Networks, Vol. 9, No. 3, July 2002