Towards Accurate and Robust Localization for a Proof of Location Protocol
A positioning system can be defined as a procedure used to obtain spatial information about a tracked object with respect to a set of reference points. To a large extent, localization services are based and rely on global satellite navigation systems (GNSS) like GPS (Global Positioning System). There are a number of techniques used by positioning systems without the use of GPS, utilizing radio frequency transmissions to form a wireless positioning system. Crucially, wireless networks that transport GPS data are not considered as a native positioning technique.
The measurements of and problems authenticating time and space are intricately intertwined. The majority of localization systems employed explicitly assume trusted environments, where data can be expected to be obtained correctly. The goal of this post is to provide a breakdown of these techniques and articulate why the approach the FOAM network has taken provides a foundation for accurate and robust Localization for a Proof of Location protocol.
To begin with some preliminary information, there are three general approaches used in building a positioning system. These are Proximity Detection, Scene Analysis and Triangulation. The principle and architecture utilized can impact accuracy and reliability of the positioning system, further illustrated below.
Proximity Based Detection systems estimate the distance between a mobile beacon (user) and a reference radio node. The proximity detection technique is one of the weakest forms of localization but also one of the simplest to implement. A set of fixed radio antennas is deployed and when a user is detected by one of the radio antennas, the closest antenna is considered when detecting the users location. This technique is usually used to determine if a user has entered into a specific area that is being monitored and can be a cost effective solution for context aware services such as advertising and shopping. This technique is not recommended for tracking applications.
In contrast to Proximity Detection, the Scene Analysis positioning technique uses radios in a predefined and known location to analyze an area known as the “scene”. This method collects fingerprint signatures from devices that are transmitting over radio in that area to form a database for analysis. A common fingerprinting method is based on the Received Signal Strength Indicator (RSSI) of radio frequencies from users. Given that analysis needs to be conducted on the fingerprints collected in a database, this method can sometimes be considered time-consuming and can be computational and/or labor-intensive. There are many algorithms that can be used for database analysis, which can be divided into probabilistic and deterministic types. This method is highly dependent on the pre-defined map of reference points radios.
For example, Hivemapper is a network launching later this year that is in part comprised of a dashcam to be installed in vehicles that will enable drivers to collect street level imagery in return for token rewards. To verify that the location coordinate metadata the dashcams will submit and the actual imagery have not been spoofed or falsified, Scene Analysis and fingerprinting will be employed.
In this case, the pre-defined map of reference point radios are to be comprised of LoRa Helium Hotspots: “we think of each Helium hotspot at a given location as a digital fingerprint.” Each dashcam will report to a database which hotspots it can see and connect to. If two dashcams are moving along the same path and do not report seeing the same hotspots to the database “there is potentially something nefarious about the dashcam's location.” This additional layer of validation assists in detecting dashcams that are spoofing their GPS location. However, this approach relies on a pre-defined map of reference point radios that may be spoofing their locations as well or be black listed from the network (What is Helium Network Gaming?).
The third general approach used in building a positioning system is the Triangulation estimation technique, which uses the geometric properties of triangles to estimate distance and location through signal measurements such as Time of Flight(ToF), Angle of Arrival (AoA) and RSSI. Triangulation can be further broken down and categorized into (1) angulation and (2) lateration methods. Techniques utilizing distance are known as lateration methods, whereas angulation methods measure the angle of arrival of a signal from the beacon nodes of a known location for localization.
The Angulation method calculates the direction of a RF signal received from a transmitter node by an anchor node with a known position and observing the AoA to conduct triangulation. The accuracy of this method is highly dependent and improved by the number of anchor nodes. A drawback of this approach is that it requires a complex set of antenna arrays which are very sensitive to multipath propagation.
Lateration focuses on distance instead of direction and determines the position of unknown object based on measuring the distance from anchor nodes with known locations. Lateration can be further broken down into Signal based approaches and Time based approaches.
RSSI is most often used in Signal based approaches, known for simplicity and wide range of use in localization applications, which uses a mathematical model that describes signal strength loss and distance. However, RSSI has no direct correlation to actual verifiable positioning, only signal strength, and is considered a method with limited accuracy. An environment with a lot of RF noise can effect the readings and results are usually presented as a range of maximum and minimum distance readings. Further, as user can maliciously modulate their signal strength to yield different distance calculations. Compared to time based approaches, RSSI is less costly to deploy and does not require additional hardware or clocks.
Time based positioning methods take into consideration the time taken by a user’s radio signal to reach the anchor nodes. Location is calculated by subtracting the time the signal left the source and arrived at the anchor node, Time of Arrival(ToA), and Time Differential of Arrival (TDoA) being the main methods. This approach uses the relative geometry between beacons to compute a node’s distance and requires accurate timestamp RF packets . To determine the location of a mobile user node requires at least three anchor nodes in a 2D, at least four anchor nodes are required for localization in a 3D. The accuracy of this method depends on clock synchronization between the anchor nodes. Time based approaches are considered the most accurate techniques generally.
The majority of localization systems employed using the above positioning techniques explicitly assume trusted environments, where data can be expected to be obtained correctly. With FOAM Proof of Location our goal is to enable a secure and spatially distributed location system. To do so we are working with a lateration distance based method and a clock synchronization to provide the best possible support for RF time of flight algorithms.
Radio Frequency Time of Flight Distance-Bounding algorithms are the family of algorithms most robust against malicious actors. While it is the most difficult to implement, we have determined that TDoA is the most robust and reliable technique to support Proof of Location. In the FOAM Proof of Location protocol, at least 4 or more reference nodes, known as Zone Anchors, can synchronize their clocks and form a Zone of coverage.
As we have written about in the past, to best support localization, the hardware needs to process the raw stream of Radio Frequency (RF) samples as they come in from the RF-frontend with sample-accurate timing. To achieve this we need access to the physical (PHY) layer, and do so with a FPGA powered software defined radio (SDR). Our stack now resembles a domain specific architecture (DSA) to do Time-difference of Arrival (TDOA) and other ranging techniques. Recently, at the GNU Radio conference a talk was given titled Implementing and evaluating TDOA techniques on SDRs: Lessons learned from the field that provides additional information on time based methods and the hardware required.
Get involved and learn more about testing FOAM in beta by following this link. Forthcoming posts will dive deeper into how the FOAM protocol will operate and updates from the Trust Zone Beta Program.
FOAM is a technology for applications needing secure location services. It enables a handshake between the location service providers and the user, proving the user’s location. Terrestrial radios and time-of-flight algorithms are used to perform localizations, and cryptographic signatures ensure the data cannot be spoofed. The system is independent of satellite-based location services like GPS.