Location Aware Apps — Location

Smartphones and other devices with location tracking capability have enabled a number of use cases in everyday life. E.g.:

1. Navigation services while travelling by various modes of transport
2. On-demand services such as cabs, delivery and home services
3. Health and fitness apps that track activity patterns
4. Location based marketing services
5. Augmented reality and gaming apps
6. Indoor asset tracking
7. Indoor proximity engagement

Location aware apps that run on these devices build on a number of underlying technologies. This is a series of articles that provide an overview of the various technologies that are brought together to deliver these use cases.

1. Location
2. Connectivity
3. Geographic Information

Location

This section provides an overview of the different approaches for determining a device’s location. When the location maps to a geographical point, the process is referred to as geolocation. Depending on the use case, a combination of the various approaches can be used, considering the following:

• Precision: For some scenarios, knowledge of proximity is sufficient
• Accuracy: The different techniques inherently have different levels of uncertainty
• Latency: The time taken to compute the location varies for each of the approaches
• Lag: The approach also depends on the rate at which the location is updated
• Power: The different sensors used for geolocation each have their own power profiles
• Reliability: Each approach has its own failure modes e.g. network availability

GNSS

Global Navigation Satellite Systems (GNSS) provides the most precise way of autonomously determining a device’s location. The Global Positioning System (GPS) is a system of satellites providing global coverage, and owned by the United States government. The satellites transmit a signal to indicate their precise location with a timestamp, and receivers can combine the data from four or more satellites to calculate their own precise location using trilateration. GPS consists of two services — the Standard Positioning Service (SPS) for civilian use, and the Precise Positioning Service (PPS) for military use. The horizontal accuracy for PPS was around 5m, and with a deliberate scrambling mechanism called Selective Availability (SA), SPS accuracy was limited to 100m. The precise location was determined by a dual-band receiver that would decode the signal sent on the L1 and L2 bands. SPS used a low-cost single-band receiver that only decoded the L1 band signal. Since SA was switched off in 2000, single-band receivers also have had an accuracy of 5m — more accurate dual-band receivers are still expensive due to patent protections. With upgraded satellites, a new open signal in the L5 band will allow low-cost receivers to determine their location to a 30cm accuracy — these should be available in smartphones starting in 2018.

The receiver first calculates the pseudo-range from multiple satellites using code-phase tracking. The location is then computed as the intersection of these ranges based on an awareness of the satellite position. These computations use the time, the ephemeris (precise orbital information that is valid for four hours) and the almanac (low-resolution orbital information that tis valid for 180 days) as received from the satellites. The accuracy of the computed location depends on factors like atmospheric variation, multi-path effects, and errors in the ephemeris and clock.

GNSS Augmentation

Whereas consumer applications for positioning are able to tolerate a lower accuracy, some applications such as surveying and air navigation need to use various augmenting techniques to compensate for these errors and improve the positioning accuracy. The ionospheric effects generally change slowly, and are consistent in a geographic region. Ground stations are able to determine this ionospheric variation, and transmit it to mobile receivers using regional Satellite Based Augmentation Systems (SBAS) or Ground Based Augmentation Systems (GBAS). Without this data, receivers use a mathematical model to compensate for ionospheric variations. Ephemeris and clock errors may be due to the SA mechanism, or due to inaccuracies in the satellite clock and other factors that affect the actual orbit of the satellites.

Differential Positioning

Reference stations at known locations can be used to compute positioning errors using carrier phase tracking, and then transmit the correction information over a SBAS or GBAS. With Differential GNSS, the reference stations compute errors in the pseudo-range to determine compensations for SA, as well as ionospheric variation. It typically uses a GBAS mechanism to transmit the correction parameters to ‘rovers’ within a few 10s of km, resulting in up to 1m positioning accuracy. With Real-Time Kinematic (RTK) systems, the reference stations transmits carrier phase corrections to rovers at most 15km away, and allows cm-level accuracy. RTK uses double differencing wherein, it uses two receivers to compensate for differences in satellite clocks as well as receiver clocks. With Precise Point Positioning (PPP), dual-band stations are able to compensate for errors over a larger area (1000s km) resulting in cm to dm level accuracy. PPP convergence can take a long time, and is performed as a post processing operation.

Multi-Constellation Positioning

A number of other satellite systems have also been deployed or are being developed to reduce dependency on foreign owned systems for defense applications. Other global systems includes the Russian GLONASS, the Chinese BeiDou (public accuracy of 10m and encrypted accuracy of 10cm) and the European Galileo Systems (public accuracy of 1m and encrypted accuracy of 1cm). India is developing a regional system called the NAVIC (public accuracy of 10m and encrypted accuracy of 10cm).

The signals used by the various GNSS constellations tend to be compatible so as to avoid interference, thus allowing for multi-standard receivers. Such Multi-GNSS or Multi-Constellation receivers are able to use data from multiple satellites simultaneously, and can provide improved accuracy and time to first fix, along with much improved handling of occlusions such as in urban canyons.

For scenarios where a good satellite signal is not available, a number of complementary and supplementary technologies are available for geolocation.

AGPS / AGNSS

Assisted GPS (A-GPS) uses mobile data services to make the process of acquiring GPS based location faster and more robust. When data for other positioning constellations is also provided, the service is known as A-GNSS.

A cold start of a GPS receiver is when a fresh download of the satellite configuration information is required — in this case it can take over 5 minutes to acquire the position. In a warm start, the configuration information is already available, and position acquisition can take between 1 and 3 minutes. With AGPS, the Time To First Fix (TTFF) is around 10s.

The GPS chipset in most modern mobile phones have inbuilt support for AGPS. In Mobile Station Assisted mode, the mobile device can send partial GPS data to a nearby mobile station, and a telco provided A-GPS server can calculate and return the actual location. In Mobile Station Based mode, the A-GPS server returns reference information that reduces the time taken by the mobile device to calculate its location. Overall, AGPS provides a location accuracy between 5m and 50m.

INS

Inertial Navigation Systems (INS) make use of other sensors to keep track of movement in order to fill gaps in GPS coverage. Motion sensors (accelerometers) and rotation sensors (gyroscopes) are used to estimate the orientation, velocity and acceleration of the moving object. The dead reckoning process uses these values to further estimate the actual object location. The error in these location estimates accumulate over time, and this method is effective only during short outages.

Cellular Positioning

Cellular positioning uses the known location of nearby mobile cell towers to determine a devices location. The most basic form simply uses the location of the current base station — known as the Cell ID. The location accuracy in this case depends on the size and can be enhanced with additional information such as signal strength.

It is also possible to use information from multiple base-stations to determine a device’s location using algorithms such as Time Difference of Arrival (TDOA). The location accuracy in this case depends on the density of base stations and can vary between 50m and several hundred meters in urban environments.

WiFi Positioning

Location service providers like Apple and Google support WiFi positioning, wherein the location of a device can be determined using the nearest Wireless Access Point. The service providers first build a database mapping Access Points uniquely to their GPS location determined by WiFi Scanning or by wardriving. Subsequent devices can then find their location relative to the Access Point even if they don’t have a GPS location.

A number of techniques are available to use the Access Point location to then accurately determine a device’s location. For outdoor positioning, a fast though inaccurate technique is Cell Identity, wherein the location of the Access Point with the strongest signal is used. The accuracy can vary from 25m to 200m. This technique is used by the HTML5 geolocation service, as implemented by Firefox, Chrome and Safari. Higher accuracy can be obtained using trilateration on the Received Signal Strength from multiple Access Points. This approach improves the accuracy to 7m-20m, but may produce inconsistent results due to signal interference.

An update to the WiFi specification - 802.11mc, known as WiFi RTT (Round Trip Time) can be used for a more accurate indoor position. A mobile device can estimate their distance from WiFi-RTT capable Access Points, and the use trilateration to compute their location.

Hybrid Positioning

Mobile operating systems combine the various positioning technologies to provide the most accurate estimate of the current location to other applications. E.g. the Apple ‘CoreLocation’ service, and the Google ‘FusedLocation’ provider. These services can be tuned for speed, accuracy, or battery-efficiency — the location updates are accordingly provided from the OS to the client application. Higher speed of locking will depend on either Cellular or WiFi Positioning. Higher accuracy will require a GPS lock that may be speedened by AGPS. GPS tracking devices can be significant power consumers, and Cellular and WiFi positioning will be preferred for battery efficiency.

Proximity

There are a number of ‘proximity engagement’ scenarios where proximity is used instead of absolute location e.g. guided museum tours, pushing promotional content and payments. A passive approach is to use a QR (Quick Response) code that encodes a URL, and enables ‘pull engagement’. The active approach uses short range RF communication to enable ‘push engagement’.

Apple and Google have defined standards that allow BLE (Bluetooth Low Energy) Beacons to communicate with nearby devices. The beacons run in one of two modes: In ‘connected’ mode, beacons communicate using the Generic Attributes (GATT) profile, or a manufacturer specific protocol; whereas in the ‘advertising’ mode, they communicate using the Generic Access Profile (GAP). The beacons are typically in the ‘advertising’ mode, broadcasting packets to nearby receiving applications. The ‘connected’ mode is used for provisioning the beacon using a generic GATT app like the Google Beacon Tool, or a manufacturer specific provisioning app.

The Apple iBeacon protocol can be used by beacons to advertise a Unique ID along with a Major and Minor identifier. Compatible apps can have the OS notify them when any nearby beacons advertise the specified Unique ID. Applications can use the Apple CoreLocation service to monitor regions and also for ranging i.e. determine proximity to a beacon.

The Google Eddystone open protocol can be used by beacons to transmit one of four types of information packets — Eddystone-UID is similar to iBeacon, transmitting a unique Namespace and Instance ID; Eddystone-URL transmits a URL, like an active QR-code; Eddystone-TLM is used to transmit telemetry information that may contain sensor readings; and Eddystone-EID replaces the UID packet with an encrypted time-varying identification packet. Beacons may be configured to either transmit URL frames only, or to transmit identifying frames (UID or EID), optionally interleaved with URL or TLM frames.

The Google Physical Web technology is based on beacons configured for Eddystone-URL. The Chrome browser on Android and iOS was enabled to listen for these broadcasts, and notify the user. This has now been replaced on Android by the Nearby Notifications service (and the Physical Web app on iOS).

The Google Proximity Beacon API enables engagement with Eddystone-UID/EID beacons and also iBeacons that have been registered with the Google Beacon Registry. The registration process associates ownership and location data with the beacon. The beacon may also be associated with an app specific ‘attachment’. The attachment can be retrieved by nearby applications using the Nearby Messages service.

Besides BLE, other technologies that can be used for proximity detection are RFID (Radio Frequency Identification), and NFC (Near Field Communication).

An RFID system consists of tags on one side, and reader devices on the other that can read the tags using electromagnetic coupling. Tags may be active (powered, and long-range) or passive (short-range).

RFID systems operating at 125–135 kHz (LF) and 13.56 MHz (HF) operate in the near-field and use inductive coupling, where the tags can modulate their load to communicate with the reader. Systems operating beyond 100 MHz, such as 860–960 MHz (UHF) and 2400 and 5800 MHz (microwave), operate in the far-field and use backscatter (radiative) coupling, where the tags modulate the backscatter in a way similar to radar.

Passive LF tags have a range of 1cm-10cm, and work even when attached to objects containing water, tissue, wood or aluminium. Applications includes animal identification (ISO 14223) and automotive immobilisers. The 13.56 MHz passive HF tags have a range of 1cm-1m, and are effective around water/tissue, but not metals. Applications includes identification cards (ISO 14443), smart-cards, and payments using contactless bank cards such as Visa payWave and Mastercard PayPass. Passive UHF tags are effective around metals, but are not water/tissue. Applications includes product tagging (EPCGlobal, ISO 18000–6C) and Electronic Toll Collection (ETC). The 433MHz active UHF tags, also known as transponders, are used in passive keyless entry (PKE) systems, and for tracking containers and high value assets (ISO 18000–7). Active microwave tags applications includes ETC and also Real Time Location Systems (RTLS)

NFC is a specialized subset of HF RFID for short-range use cases, and allows the same device to be a tag and a reader, enabling P2P communication. Compared to QR codes, NFC tags can be dynamic and difficult to duplicate; and they allow vicinal electronic reading instead of requiring optical line-of-sight. The technology is used in NFC Tags or for P2P information exchange. Contactless Payments using mobile phones, such as Apple Pay and Samsung Pay, is one example of P2P information exchange.

Indoor Positioning

Some of the techniques such as WiFi positioning described so far support both indoor and outdoor positioning. However, indoor positioning has some distinct requirements that necessitates custom hardware and/or software:

1. Robustness to interference due to walls, windows, doors, furniture etc.
2. Accuracy to be able to distinguish between two rooms separated by a wall

Indoor positioning may also involve a Real Time Location Service (RTLS) that is used to track the location of people or objects in real time. Indoor positioning approaches require the tracked device to communicate with ‘anchors’. The anchors are installed at a fixed location, and their exact location is stored. The location of the tracked device (simply referred to as the device) is calculated based on the signalling between them and the anchors.

Multiple technologies are available for indoor positioning based on different wireless signals:

• Bluetooth Positioning

The BLE beacons described earlier serve as anchors, and can be used to help devices calculate their position using the location stored during registration. Along with this, mobile devices use ‘bluetooth scanning’ to continue to update their respective Location Services with the actual location of nearby beacons.

The Location Services can then use this information to enhance the positioning of devices when they are indoors. Third party apps can also combine the signals from multiple beacons, and use trilateration for more accurate positioning. The beacons typically have a transmission range of 70m, and result in a location accuracy of 2-5m.

• Indoor WiFi Positioning

Fingerprint Positioning does pattern matching based on a database that maps the signal strength from a number of nearby access points to an geolocation. This technique requires a custom database, and works quite well for indoor positioning.

Alternatively, additional hardware can be used on the tracked devices to determine their precise location by triangulation. The hardware consists of an antenna array that can determine the Angle-of-Arrival from various access points.

WiFi is also a good way to determine the floor level in case multiple levels need to be tracked indoors. This is the mechanism used by Google Maps.

• IoT Network

Various Internet-of-Things network technologies can be used for positioning. The IoT networks may be constructed in a mesh or in a star topology. The positioning may be network-centric, where the anchor nodes calculate the position, or device-centric, where the tracked devices calculate the position. As in the other cases described earlier, the position calculation uses one of the below methods:

• Received Signal Strength (RSS) — uses variation in the strength of the signal received by the tracked devices, similar to WiFi trilateration
• Time of Arrival (ToA) — uses variation in the time at which signal arrives at the tracked device, similar to GPS trilateration. This requires that the clock at the anchors and devices are synchronized.
• Angle of Arrival (AoA) — uses variation in the angle at which signal arrives at the tracked devie.

RSS based systems such as the Wirepas mesh solution provide a power efficient solution with acceptable accuracy.

• Visual Sensors

With improving compute capability, it is now possible to use visual sensors for robotic localization in real time. The Visual SLAM algorithm (Simultaneous Localization And Mapping) is used for this purpose. Indoor Positioning is key to Augmented Reality applications, and Visual SLAM provides the ideal approach for this use case. Google and Apple have both released their Augmented Reality development libraries that implement SLAM.

Accuracy

The geolocation obtained from the different sources may be inaccurate for various reasons:

• Signal Obstruction — Buildings, tunnels, trees, mountains, clothing and the human body can all obstruct the GNSS and other positioning signals. This can result in intermittent outages of GNSS or Network signals.
• Multipath Distortion — The signal arriving at the receiver can be distorted by the multiple reflections from buildings and vehicles resulting in erroneous calculations.
• Device Build — The design of the antennae and the device can affect signal sensitivity, and its ability to handle interferences.
• Device Configuration — The accuracy of the location data available to an applications depends on various user configurable options that allow them to trade-off between battery and accuracy.

These inaccuracies can manifest themselves in a number of ways:

• Erratic off-road locations while driving
• Erratic locations while stationary
• Looping between locations while moving or stationary

To address these errors, the incoming location data needs to be appropriately filtered. There are two approaches:

• Heuristic filtering
• Statistical filtering

Some heuristic rules that can be used to filter the data:

• Age of cached location below a threshold
• Uncertainty in distance (accuracy) below a threshold
• Speed inferred from change in location below a threshold
• Acceleration inferred from GPS speed below a threshold
• Distance from road, inferred from a mapping application, below a threshold

Statistical filtering involves forming an estimate of the actual location based on a mathematical model of the observed locations. The location readings are essentially a time-series (discrete time, continuous state-space) that can be represented as a stochastic dynamic system (a system where output is dependent on internal state, driven by past inputs; and also a random noise component) using a state-space model. An optimal filter tries to adapt the states to minimise the error between the predicted signal and the observed signal (using a recursive Bayesian estimator). For linear systems, where the noise has a normal distribution (gaussian), a Kalman Filter (link1, link2) works well. The more complex Particle Filter works better when the system has non-linear characteristics, or the noise is not gaussian.

Using a statistical model of the GNSS location and the INS (Inertial Navigation System) parameters, a Kalman Filter can provide improved location tracking. In the absence of INS data, GNSS data can be combined with ‘equations of motion’ to model the trajectory of the moving object. The GNSS data can be quite inaccurate in urban canyons, and the assumption of Gaussian noise becomes invalid — in this case, accurate tracking requires the use of a Particle Filter.