Wi-Fi positioning system

Wi-Fi positioning system (WPS) or WiPS/WFPS is used where GPS and GLONASS are inadequate due to various causes including multipath and signal blockage indoors. Such systems include indoor positioning systems. Wi-Fi positioning takes advantage of the rapid growth in the early 21st century of wireless access points in urban areas.

The most common and widespread localization technique used for positioning with wireless access points is based on measuring the intensity of the received signal (received signal strength indication or RSSI) and the method of "fingerprinting".^[1][2][3] Typical parameters useful to geolocate the Wi-Fi hotspot or wireless access point include the SSID and the MAC address of the access point. The accuracy depends on the number of positions that have been entered into the database. The Wi-Fi hotspot database gets filled by correlating mobile device GPS location data with Wi-Fi hotspot MAC addresses.^[4] The possible signal fluctuations that may occur can increase errors and inaccuracies in the path of the user. To minimize fluctuations in the received signal, there are certain techniques that can be applied to filter the noise.

In the case of low precision, some techniques have been proposed to merge the Wi-Fi traces with other data sources such as geographical information and time constraints (i.e., time geography).^[5]

Motivation and applications

Accurate indoor localization is becoming more important for Wi-Fi based devices due to the increased use of augmented reality, social networking, health care monitoring, personal tracking, inventory control and other indoor location-aware applications.^[6][7]

The popularity and low price of Wi-Fi network interface cards is an attractive incentive to use Wi-Fi as the basis for a localization system and significant research has been done in this area in the past 15 years.^[1][3][8]

Problem statement and basic concepts

The problem of Wi-Fi based indoor localization of a device consists in determining the position of client devices with respect to access points. Many techniques exist to accomplish this, and these may be classified into four main types: received signal strength indication (RSSI), fingerprinting, angle of arrival (AoA) and time of flight (ToF) based techniques.^[8][9]

In most cases the first step to determine a device's position is to determine the distance between the target client device and a few access points. With the known distances between the target device and access points, trilateration algorithms may be used to determine the relative position of the target device,^[7] using the known position of access points as a reference. Alternatively, the angle of arriving signals at a target client device can be employed to determine the device's location based on triangulation algorithms.^[8]

A combination of these techniques may be used to increase the accuracy of the system.^[8]

Existing localization techniques

RSSI and lateration based

RSSI localization techniques are based on measuring signal strength from a client device to several different access points, and then combining this information with a propagation model to determine the distance between the client device and the access points. Trilateration (sometimes called multilateration) techniques can be used to calculate the estimated client device position relative to the known position of access points.^[7][8]

Though one of the cheapest and easiest methods to implement, its disadvantage is that it does not provide very good accuracy (median of 2-4m), because the RSSI measurements tend to fluctuate according to changes in the environment or multipath fading.^[1]

Fingerprinting based

Traditional fingerprinting is also RSSI-based, but it simply relies on the recording of the signal strength from several access points in range and storing this information in a database along with the known coordinates of the client device in an offline phase. This information can be deterministic^[1] or probabilistic.^[3] During the online tracking phase, the current RSSI vector at an unknown location is compared to those stored in the fingerprint and the closest match is returned as the estimated user location. Such systems may provide a median accuracy of 0.6m and tail accuracy of 1.3m.^[8][10]

Its main disadvantage is that any changes of the environment such as adding or removing furniture or buildings may change the "fingerprint" that corresponds to each location, requiring an update to the fingerprint database. However, the integration with other sensor such as camera can be used in order to deal with changing environment.^[11][12][13]

Angle of arrival based

Linear array of antennas receiving a signal. The phase-shift difference of the received signal arriving at antennas equally separated by a "d" distance is used to compute the angle of arrival of the signal. Picture reproduced from ^[8]

With the advent of MIMO WiFi interfaces, which use multiple antennas, it is possible to estimate the AoA of the multipath signals received at the antenna arrays in the access points, and apply triangulation to calculate the location of client devices. SpotFi,^[8] ArrayTrack^[6] and LTEye^[14] are proposed solutions which employ this kind of technique.

Typical computation of the AoA is done with the MUSIC algorithm. Assuming an antenna array of $M$ antennas equally spaced by a distance of $d$ and a signal arriving at the antenna array through $L$ propagation paths, an additional distance of $d \times sin\theta$ is traveled by the signal to reach the second antenna of the array.^[8]

Considering that the $k^{{th}}$ propagation path arrives with angle $\theta _{k}$ with respect to the normal of the antenna array of the access point, $\gamma _{k}$ is the attenuation experienced at any antenna of the array. The attenuation is the same in every antenna, except for a phase shift which changes for every antenna due to the extra distance traveled by the signal. This means that the signal arrives with an additional phase of $-2\pi \times d \times sin\theta \times f/c$ at the second antenna and $-2\pi \times d \times (m-1) \times sin\theta \times f/c$ at the $m^{th}$ antenna.^[8]

Therefore, the following complex exponential can be used as a simplified representation of the phase shifts experienced by each antenna as a function of the AoA of the propagation path:^[8]

$${\displaystyle \phi (\theta _{k})=exp(-j2\pi \times d\times \sin(\theta _{k})\times f/c)}$$

${\displaystyle \phi(\theta_k)=exp(-j2\pi\times d\times\sin(\theta_k)\times f/c)}$

The AoA can then be expressed as the vector $\vec a(\theta_k)\gamma_k$ of received signals due to the $k^{{th}}$ propagation path, where $\vec a(\theta_k)$ is the steering vector and given by:^[8]

$${\displaystyle {\vec {a}}(\theta _{k})=[1,\ \phi (\theta _{k}),\ ...,\ \phi (\theta _{k})^{M-1}]^{T}}$$

${\displaystyle {\vec {a}}(\theta _{k})=[1,\ \phi (\theta _{k}),\ ...,\ \phi (\theta _{k})^{M-1}]^{T}}$

There is one steering vector for each propagation path, and the steering matrix $\mathbf {A}$ (of dimensions $M \times L$) is then defined as:^[8]

$${\displaystyle \mathbf {A} =[{\vec {a}}(\theta _{1}),...,{\vec {a}}(\theta _{L})]}$$

${\displaystyle \mathbf {A} =[{\vec {a}}(\theta _{1}),...,{\vec {a}}(\theta _{L})]}$

and the received signal vector ${\vec {x}}$ is:^[8]

$${\displaystyle {\vec {x}}=\mathbf {A} {\vec {\Gamma }}}$$

${\displaystyle \vec x = \mathbf{A}\vec \Gamma}$

where ${\displaystyle {\vec {\Gamma }}=[{\vec {\gamma }}_{1}...{\vec {\gamma }}_{L}]}$ is the vector complex attenuations along the $L$ paths.^[8] OFDM transmits data over multiple different sub carriers, so the measured received signals ${\vec {x}}$ corresponding to each sub carrier form the matrix $\mathbf {X}$ expressed as:^[8]

$${\displaystyle \mathbf {X} =[{\vec {x}}_{1}...{\vec {x}}_{L}]=\mathbf {A} [{\vec {\Gamma }}_{1}...{\vec {\Gamma }}_{L}]=\mathbf {AF} }$$

${\displaystyle \mathbf {X} =[{\vec {x}}_{1}...{\vec {x}}_{L}]=\mathbf {A} [{\vec {\Gamma }}_{1}...{\vec {\Gamma }}_{L}]=\mathbf {AF} }$

The matrix $\mathbf {X}$ is given by the channel state information (CSI) matrix which can be extracted from modern wireless cards with special tools such as the Linux 802.11n CSI Tool.^[15]

This is where the MUSIC algorithm is applied in, first by computing the eigenvectors of $\mathbf{X}\mathbf{X}^H$ (where $\mathbf{X}^H$ is the conjugate transpose of $\mathbf {X}$) and using the vectors corresponding to eigenvalue zero to calculate the steering vectors and the matrix $\mathbf {A}$.^[8] The AoAs can then be deduced from this matrix and used to estimate the position of the client device through triangulation.

Though this technique is usually more accurate than others, it may require special hardware in order to be deployed, such as an array of six to eight antennas^[6] or rotating antennas.^[14] SpotFi^[8] proposes the use of a superresolution algorithm which takes advantage of the number of measurements taken by each of the antennas of the WiFi cards with only three antennas, and also incorporates ToF based localization to improve its accuracy.

Time of flight based

Figure showing a measuring station sending a DATA frame to a client station and waiting until receiving the ACK. $\delta$ is the scheduling delay (offset) originated at the target client device, and it depends on how much time it takes for the ACK to be scheduled. T_P is the signal propagation time between transmitter and receiver, and is usually assumed to be the same on the way to the target and back. T_ACK is the time needed to transmit the ACK frame. The time of flight corresponds to the T_MEASURED. Picture reproduced from ^[16]

This localization approach takes timestamps provided by the wireless interfaces to calculate the ToF of signals and then use this information to estimate the distance and relative position of one client device with respect to access points. The granularity of such time measurements is in the order of nanoseconds and systems which use this technique have reported localization errors in the order of 2m.^[8] Typical applications for this technology are tagging and locating assets in buildings, for which room-level accuracy (~3m) is usually enough.^[17]

The time measurements taken at the wireless interfaces are based on the fact that RF waves travel close to the speed of light, which remains nearly constant in most propagation media in indoor environments. Therefore, the signal propagation speed (and consequently the ToF) is not affected so much by the environment as the RSSI measurements are.^[16]

Unlike traditional ToF-based echo techniques, such as those used in RADAR systems, Wi-Fi echo techniques use regular data and acknowledgement communication frames to measure the ToF.^[16]

As in the RSSI approach, the ToF is used only to estimate the distance between the client device and access points. Then a trilateration technique can be used to calculate the estimated position of the device relative to the access points.^[17] The greatest challenges in the ToF approach consist in dealing with clock synchronization issues, noise, sampling artifacts and multipath channel effects.^[17] Some techniques uses mathematical approaches to remove the need for clock synchronization.^[9]

Ubiquitous indoor localization on a world-wide scale

Recently, researchers have envisioned an Indoor Positioning System (IPS) that can perform ubiquitous indoor localization on a worldwide scale, similar to the GPS outdoors.^[18] The idea is to leverage the sensors embedded in today's smartphones in a crowd-sourcing manner to automatically construct the indoor floorplans^[19][20] as well as automatically construct the WiFi fingerprint. This not only automatically builds the fingerprints on a worldwide scale, but also keeps the constructed fingerprints up-to-date.

Privacy concerns

Citing the specific privacy concerns arising out of WPS, Google suggested a unified approach for opting-out a particular access point from taking part in determining location using WPS.^[21] Appending "_nomap" to a wireless access point's SSID excludes it from Google's WPS database. Google hopes that other WPS providers and data collectors, like Apple and Microsoft, follow that recommendation so that it becomes an accepted standard.^[22] Mozilla honors _nomap as a method of opting-out of its location service.^[23]

Public Wi-Fi location databases

A number of public Wi-Fi location databases are available (only active projects):

Name	Unique Wi-Fi networks	Observations	Free database download	SSID lookup	BSSID lookup	Data License	Opt-out	Coverage map	Comment
Combain Positioning Service[24]	>1,000,000,000[25]	>26,000,000,000[25]	no	yes	yes	Proprietary	_nomap supported	Map	Also Cell ID database.
Geomena[26]		55,013[27]	yes	yes	yes	CCSA	No	Map	Wiki editable
LocationAPI.org by Unwired Labs[28]	>709,510,000[29]	>4,100,000,000	no	yes	yes	Proprietary	_nomap supported	Map	Also Cell ID database
Mozilla Location Service[30]	598,462,095[31]	13,414,640,000[31]	no	no	no	Proprietary [32]	_nomap[23]	Map	Also Cell ID database whose data are public domain.
Mylnikov GEO[33]	76,655,230[33]		yes[34]	no	yes	MIT[35]	not applicable (aggregator)		Also Cell ID database[36]
Navizon[37]	480,000,000	21,500,000,000	no	no	yes	Proprietary	no	Map	Based on crowd-sourced data. Also Cell ID database.[38]
radiocells.org[39]	7,532,779		yes[40]	no	yes[41]	ODbL[42]	_nomap	Map	Based on crowd-sourced data. Also Cell ID database. Including raw data
OpenWLANMap / openwifi.su[43][44]	22,010,794		yes[45]	no	yes[46]	GFDL[47]	_nomap, request[46]	Map
WiGLE[48]	198,891,361[49]	2,891,184,857[49]	no	yes[50]	yes[50]	Proprietary	request	Map	Also Cell ID database.

See also

• Automatic vehicle location
• Hybrid positioning system
• Indoor positioning system
• MAC address
• Mobile phone tracking

External links

• Free Cell & Wlan Databases for Location Services on Fairphone Forum
• Skyhook Wireless private database coverage map
• AlterGeo – private wifi location database

References

1. P. Bahl and V. N. Padmanabhan, “RADAR: an in-building RF-based user location and tracking system,” in Proceedings of 19th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM ’00), vol. 2, pp. 775–784, Tel Aviv.Israel, March 2000.
2. Y. Chen and H. Kobayashi, “Signal strength based indoor geolocation,” in Proceedings of the IEEE International Conference on Communications (ICC ’02), vol. 1, pp. 436–439, New York, NY, USA, April–May 2002.
3. Youssef, M. A.; Agrawala, A.; Shankar, A. Udaya (2003-03-01). "WLAN location determination via clustering and probability distributions". Proceedings of the First IEEE International Conference on Pervasive Computing and Communications, 2003. (PerCom 2003): 143–150. doi:10.1109/PERCOM.2003.1192736.
4. "Wi-Fi Positioning System".
5. Danalet, Antonin; Farooq, Bilal; Bierlaire, Michel. "A Bayesian approach to detect pedestrian destination-sequences from WiFi signatures". Transportation Research Part C: Emerging Technologies. 44: 146–170. doi:10.1016/j.trc.2014.03.015.
6. J. Xiong and K. Jamieson, “Arraytrack: A fine-grained indoor location system,” NSDI ’13.
7. Yang, Jie; Chen, Yingying (2009-11-01). "Indoor Localization Using Improved RSS-Based Lateration Methods". IEEE Global Telecommunications Conference, 2009. GLOBECOM 2009: 1–6. doi:10.1109/GLOCOM.2009.5425237.
8. Kotaru, Manikanta; Joshi, Kiran; Bharadia, Dinesh; Katti, Sachin (2015-01-01). "SpotFi: Decimeter Level Localization Using WiFi". Proceedings of the 2015 ACM Conference on Special Interest Group on Data Communication. SIGCOMM '15. New York, NY, USA: ACM: 269–282. doi:10.1145/2785956.2787487. ISBN 978-1-4503-3542-3.
9. Youssef, Moustafa; Youssef, Adel; Rieger, Chuck; Shankar, Udaya; Agrawala, Ashok (2006-01-01). "PinPoint: An Asynchronous Time-Based Location Determination System". Proceedings of the 4th International Conference on Mobile Systems, Applications and Services. MobiSys '06. New York, NY, USA: ACM: 165–176. doi:10.1145/1134680.1134698. ISBN 1595931953.
10. Youssef, Moustafa; Agrawala, Ashok (2007-01-04). "The Horus location determination system". Wireless Networks. 14 (3): 357–374. doi:10.1007/s11276-006-0725-7. ISSN 1022-0038.
11. Wan Mohd Yaakob Wan Bejuri, Mohd Murtadha Mohamad, Maimunah Sapri and Mohd Adly Rosly (2012). Ubiquitous WLAN/Camera Positioning using Inverse Intensity Chromaticity Space-based Feature Detection and Matching: A Preliminary Result. International Conference on Man-Machine Systems 2012 (ICOMMS 2012), Penang, MALAYSIA. See publication here, or click here if broken link
12. Wan Mohd Yaakob Wan Bejuri, Mohd Murtadha Mohamad, Maimunah Sapri and Mohd Adly Rosly (2012). Investigation of Color Constancy for Ubiquitous Wireless LAN/Camera Positioning: An Initial Outcome. International Journal of Advancements in Computing Technology, Vol. 4, No. 7, pp. 269-280, See publication here
13. Wan Mohd Yaakob Wan Bejuri, Mohd Murtadha Mohamad, Maimunah Sapri and Mohd Adly Rosly (2012). Performance Evaluation of Mobile U-Navigation based on GPS/WLAN Hybridization. Journal of Convergence Information Technology(JCIT), Vol. 7, No. 12, pp. 235-246, See publication here
14. Kumar, Swarun; Hamed, Ezzeldin; Katabi, Dina; Erran Li, Li (2014-01-01). "LTE Radio Analytics Made Easy and Accessible". Proceedings of the 6th Annual Workshop on Wireless of the Students, by the Students, for the Students. S3 '14. New York, NY, USA: ACM: 29–30. doi:10.1145/2645884.2645891. ISBN 978-1-4503-3073-2.
15. "Linux 802.11n CSI Tool". dhalperi.github.io. Retrieved 2015-11-10.
16. Marcaletti, Andreas; Rea, Maurizio; Giustiniano, Domenico; Lenders, Vincent; Fakhreddine, Aymen (2014-01-01). "Filtering Noisy 802.11 Time-of-Flight Ranging Measurements". Proceedings of the 10th ACM International on Conference on Emerging Networking Experiments and Technologies. CoNEXT '14. New York, NY, USA: ACM: 13–20. doi:10.1145/2674005.2674998. ISBN 978-1-4503-3279-8.
17. Lanzisera, S.; Zats, D.; Pister, K.S.J. (2011-03-01). "Radio Frequency Time-of-Flight Distance Measurement for Low-Cost Wireless Sensor Localization". IEEE Sensors Journal. 11 (3): 837–845. doi:10.1109/JSEN.2010.2072496. ISSN 1530-437X.
18. Youssef, Moustafa (2015-01-01). "Towards Truly Ubiquitous Indoor Localization on a Worldwide Scale". Proceedings of the 23rd SIGSPATIAL International Conference on Advances in Geographic Information Systems. GIS '15. New York, NY, USA: ACM: 12:1–12:4. doi:10.1145/2820783.2820883. ISBN 9781450339674.
19. Alzantot, Moustafa; Youssef, Moustafa (2012-01-01). "CrowdInside: Automatic Construction of Indoor Floorplans". Proceedings of the 20th International Conference on Advances in Geographic Information Systems. SIGSPATIAL '12. New York, NY, USA: ACM: 99–108. doi:10.1145/2424321.2424335. ISBN 9781450316910.
20. Elhamshary, Moustafa; Youssef, Moustafa (2014-01-01). "CheckInside: A Fine-grained Indoor Location-based Social Network". Proceedings of the 2014 ACM International Joint Conference on Pervasive and Ubiquitous Computing. UbiComp '14. New York, NY, USA: ACM: 607–618. doi:10.1145/2632048.2632051. ISBN 9781450329682.
21. "Infosecurity Blogs". Infosecurity Magazine. Retrieved 2015-09-17.
22. Google Help - Location-based services - How do I opt out? Obtained 2012-05-30
23. "MLS-Opt-Out". mozilla.com. Retrieved 2 September 2014.
24. "Combain Positioning Service". Retrieved 2016-06-21.
25. "Wifi Positioning | Wifi Location | Cell ID - Combain". Retrieved 2016-06-21.
26. "Wifi Location Service". Retrieved 2015-02-11.
27. "Geomena: Wifi geolocation". geomena.org. Retrieved 2015-06-23.
28. "Unwired Labs LocationAPI". Retrieved 2015-05-11.
29. API, Unwired. "Unwired Labs Location API - Geolocation API and Mobile Triangulation API, Cell Tower database". Unwired Labs Location API - Geolocation & Mobile Triangulation API. Retrieved 2015-06-23.
30. "Mozilla Location Service". Retrieved 2015-10-26.
31. "MLS - Statistics". location.services.mozilla.com. Retrieved 2016-05-06.
32. "CloudServices/Location/FAQ - MozillaWiki".
33. "Mylnikov GEO Wi-Fi". Retrieved 2015-05-19.
34. "Mylnikov GEO Wi-Fi Database Download". Retrieved 2015-05-19.
35. "Mylnikov GEO license". Retrieved 2014-12-19.
36. "Mylnikov GEO Mobile Cells Database". Retrieved 2014-12-19.
37. "Navizon Global Positioning System". Retrieved 2015-06-21.
38. "Navizon WiFi Coverage Map". Retrieved 2015-06-21.
39. "openBmap". Retrieved 2016-02-23.
40. "Openbmap Database Download". Retrieved 2015-01-30.
41. "Wifi Access Point finder". Retrieved 2015-01-30.
42. "Openbmap license". Retrieved 2015-01-30.
43. "OpenWLANMap". Retrieved 2015-06-23.
44. QXC, VWPDesign/. "Open WLAN Map - free and open WLAN-based location services". openwifi.su. Retrieved 2015-07-06.
45. "OpenWLANMap Database Download". Retrieved 2015-02-24.
46. "Find WLAN network". Retrieved 2014-12-19.
47. "OpenWLANMap license". Retrieved 2014-12-19.
48. "WiGLE". Retrieved 2014-12-19.
49. "WiGLE Stats". www.wigle.net. Retrieved 2015-06-23.
50. "WiGLE Wireless Network Map". Retrieved 2014-12-19.

General

• Anthony LaMarca, Yatin Chawathe, Sunny Consolvo, Jeffrey Hightower, Ian Smith, James Scott, Tim Sohn, James Howard, Jeff Hughes, Fred Potter, Jason Tabert, Pauline Powledge, Gaetano Borriello, Bill Schilit: Place Lab: Device Positioning Using Radio Beacons in the Wild. In Pervasive (2005)