Outdoor positioning

The Global Positioning System (GPS) is a widely-used solution for deriving location, developed by the USA for military and civilian use. It uses trilateration and distance measurements by leveraging radio signals sent by satellites. Satellites are deployed in such a way that at least four of them cover any point on earth. A master control station precisely knowns the location of each satellite as a reference point (i.e., source). A GPS-equipped device derives its distance from a satellite by subtracting the time the signal was sent (included within it) and the time it was received, multiplied by the speed of light. Location is then obtained by combining the obtained distances and the known position of the satellites. GPS positioning works outdoors, as the signal from satellites is significantly attenuated by built-up environments (for instance, urban areas with many buildings) and foliage. The GPS system allows an accuracy of 15-20 meters for civilian use. Such an accuracy can be increased through the Differential GPS approaches, which leverages a different GPS receiver – whose position is accurately known – to compensate the noise in the range measurements due to inaccuracies (e.g., in the clocks and satellite orbits).

Indoor positioning

A practical solution to determine the location of a device indoors is to leverage an existing WiFi infrastructure. This approach works particularly well when WiFi access points are densely deployed, such as in both office and commercial environments (e.g., malls). In detail, WiFi-based positioning relies on known locations of WiFi access points; mobile devices may either passively scan for them or actively probe those nearby to collect the Received Signal Strength (RSS). The RSS is a measure of the power of a radio signal sent by a source as measured at a receiver. The power of a radio signal degrades over distance; therefore, the RSS expresses how far the receiver is from a transmitter.

Fingerprinting is a techniques that leverages spatial variations in the observed signal for positioning purposes. Fingerprinting is the de-facto approach for indoor positioning that involves collecting predetermined patterns at different locations and inferring the mobile device location as the best fit for the observed pattern. In particular, fingerprinting consists of two main phases.

  • Training (or calibration). RSS patterns are first observed at well-defined reference positions. The corresponding database (also called radio map) is then built off-line generally once, or as often as access points are added, moved (replaced), or removed  from the network.
  • Estimation. RSS measurements are compared with those in the radio map and the actual position of the device is determined based on best match. This phase is executed on-line, i.e., as needed by the mobile devices.

As an example, the following radio map:

Latitude Longitude AP1 RSS AP2 RSS AP3 RSS
60.186856 24.822191 -59 dBm -75 dBm -71 dBm
60.186875 24.822321 -35 dBm -64 dBm -50 dBm
60.186886 24.821988 -69 dBm -66 dBm -73 dBm
60.186659 24.822079 -40 dBm -65 dBm -52 dBm

corresponds to the indoor scenario illustrated in the picture below.

Sample indoor scenario

The red circles in the picture indicate the location of WiFi access points, whereas the green squares the position where RSS measurements were taken. Accordingly, the radio map has four rows (one per measurement, excluding the table headers) and five columns (two for latitude and longitude as well as three for each of the access points). The RSS value is expressed in dBm, which indicates the power ratio in decibels with one milliwatt used as reference.

For fingerprinting to work, RSS measurements should exhibit certain properties: spatial variability, namely, they should significantly vary upon moving for a few meters; temporal consistency, that is, the source signal strength should not change over time. The simplest option to estimate position with fingerprinting is through a deterministic approach that takes measurements as scalar values and determines location by means of vector comparison, for instance, based on the smallest Euclidean distance between the observed and the recorded patterns.

A more accurate technique consists in using the k-nearest neighbors algorithm, which works as follows – the parameter k is given as input to the algorithm.

  • Find the k best-matching measurements in the radio map according to some distance (e.g., Euclidean distance).
  • Combine these k entries to derive a location estimate for the device. This is generally accomplished by calculating the geometric centroid of the locations corresponding to the k closest access points.

Last modified: Saturday, 19 September 2020, 11:08 PM