How To Solve The Hardest LPWAN Geolocation Problems
Much of our work at Haystack right now focuses on applications requiring GPS-based geolocation of LoRa endpoints, but we also get questions on how to solve for location when GPS is unavailable. We are also working on time-based location of LoRa endpoints in support of new, decentralized blockchain initiatives, especially proof of location.
First, if you don’t know our views on the weaknesses of LoRaWAN you can look here and here. In sum, battery-powered LoRaWAN cannot realistically support high-precision GNSS/GPS unless battery life of just a few days will suffice or a large battery pack is acceptable. For most developers, it will not so we’ve witnessed attempts by some LoRaWAN developers to push a type of geolocation hack using uplink-only Time Difference of Arrival to locate mobile LoRaWAN endpoints, which we’ve debunked here. For mobile LoRa applications, it’s just hard to cite a rational reason to choose LoRaWAN over better options.
Two Different Approaches to RF Location Without Using GPS
Determining the location of a mobile object using a radio without GNSS/GPS is not a new concept — RADAR has been with us for decades. But finding the location of a mobile LoRa endpoint without GNSS/GPS is different.
There are two fundamental approaches to determining the location of a mobile, GPS-less LoRa endpoint: time-based and signal strength-based. In both cases the precision of the resulting geolocation measurement is enhanced through the use of more than one gateway in a given coverage area. In cases where there is only a single gateway within range of an endpoint, we can determine the general location of the endpoint unless the endpoint is moving (or if the endpoint is stationary and the gateway is moving), in which case the resulting granularity of location precision is significantly improved.
Signal Strength-based Location
The first method of location utilizes a signal strength measurement, also known as RSSI (Received Signal Strength indicator). RSSI is a power measurement, typically used with dBm units. dBm is a logarithmic unit of power, in which: 0dBm = 1 milliwatt (mW), -10dBm = 0.1mW, -100dBm = 10^-100 mW.
Signal strength decays with distance from the transmitter in a nonlinear way. Due to this nonlinear decay, signal strength measurements can provide high-resolution location measurements when the range is small, but very imprecise measurements when the range is long.
Time of Flight-based Location
It is also possible to measure the time it takes for the radio signal to travel from one device (e.g. an endpoint) to a second device (e.g. a gateway). This is referred to as a TOF measurement (Time Of Flight). The procedure for measuring TOF is much more difficult than the process of measuring RSSI, but TOF has a few advantages.
- the speed of light is constant within a given medium (e.g. air), so the modeling equations are simpler than for RSSI
- TOF increases linearly with distance. For example, the radio signal crosses one meter in roughly three nanoseconds.
- Antennas do not typically radiate in a perfectly spherical pattern. The RSSI can vary depending on the orientation of the antenna.
The best radio location technologies tend to use both RSSI and TOF measurements, though TOF is more common and RSSI is used to provide special corrections. In fact, the best radio location technologies use many additional inputs to improve the location precision — often referred-to as “sensor fusion.”
Multilateration
Multilateration is frequently referred-to, incorrectly, as “triangulation” (triangulation is actually the process used by Angle Of Arrival). Multilateration can be used with RSSI or Time-of Flight measurements or both. The basic idea is that a point can be determined in space as long as at least three distance vectors to this point are known. An illustration is shown in the diagram below, where three gateways of fixed, known position scribe circles of radii corresponding to the distance measurement of the unknown endpoint. The intersection of the circles ultimately yields the position of the unknown endpoint.
Time Difference of Arrival (TDOA)
TDOA is a method of distance measurement that considers the time difference between a group of received messages. There are two variants of TDOA: uplink and downlink.
Uplink TDOA
A network in which an endpoint of unknown position transmits a radio message to multiple gateways of known position is the basis for uplink TDOA. The gateways of known position actually contain multiple receivers, carefully constructed in an array. At each receiver in the array, the transmitted message is received at a slightly different time depending on the position and orientation of the unknown endpoint in relation to the array. For example, if an array consists of two antennas spaced 3m apart, and if the unknown device is directly to the side of the array, then one antenna will receive the message about 9 nanoseconds before the other. From this we know the direction of the unknown device. If multiple stations are involved, then the location of the unknown device can be determined.
Uplink TDOA can be observed in many campus-level RTLS (real-time location system) products. It is also used in some cellular networks and LPWANs, although to a much lower degree of precision. The advantage of uplink TDOA is that network synchronization can be relatively imprecise (milliseconds, or even seconds). The disadvantage of uplink TDOA is that the infrastructure becomes very large, complex, and expensive due to antenna array requirements. For longer range radios, the arrays need to become quite large (many meters across) in order to deliver precise location.
The myriad drawbacks of uplink TDOA when implemented on a unidirectional wireless protocol like LoRaWAN are discussed here.
Downlink TDOA
In a downlink TDOA network, gateways of known position and time transmit messages to an endpoint of unknown position and time. The transmission of each message, from each corresponding gateway device, must be tightly synchronized in time. The receiver can compare the expected time of arrival of each message with the actual time of arrival, in order to determine the relative times-of-flight of each message.
Downlink TDOA is used in systems like GPS/GNSS and LORAN. For downlink TDOA, the radio systems on all the devices can be quite simple, but the timing of the gateways must be very precise. The major challenge with downlink TDOA is network time synchronization.
Downlink TDOA, when implemented with LPWAN’s, requires a return path to transmit the resulting times-of-flight (or the computed location, if processing occurs at the endpoint) to the gateway, and is therefore only realistically supportable with a LPWAN protocol that is fully bi-directional.
Angle of Arrival (AOA)
Strictly speaking, uplink TDOA implements a form of Angle-of-Arrival via its antenna array, but in most literature AOA stipulates the use of particular antenna hardware which is highly directional and, at any time, knows its angle. When a message is received from an unknown device, the gateway knows the angle its antenna is directed at that time, and thus can determine the direction of the unknown endpoint relative to itself.
The most common implementation of AOA is in a rotating RADAR assembly, which combines the angle measurement with Doppler and signal strength measurements to get range and direction.
Challenges of Implementing TOF-based radio measurements
So we’ve described some of the challenges of building TDOA networks — particularly the challenge of time synchronizing network infrastructure on a Downlink TDOA network. However, there are challenges merely in detecting and receiving a radio signal with sufficient time precision. Importantly, there are two:
· Determining an “edge” in the received signal. That is, a component of the signal which can be used as a precise indicator of a point in time.
· Implementing a method to achieve high time precision with limited signal bandwidth
Edge Correlation
Edge correlation is the process of detecting an edge in a received radio signal. It is an important part of any digital radio receiver and demodulator, but for location systems there is an extra requirement of precision. In these systems, an edge is implemented as an encoded, modulated sequence. These sequences are carefully engineered to have very high autocorrelation properties. One of the sequences with highest autocorrelation is a frequency sweep signal, also called a “chirp.” Chirp Spread Spectrum modulation is the fundamental technology Semtech’s LoRa radio uses to modulate data, therefore LoRa can be a suitable radio technology for detecting edges in radio signals and thus for utility as a time synchronization technology. There are other technologies that can correlate edges with high precision, too, such as Ultra-Wideband (UWB) or long-coded Direct Sequence Spread Spectrum (DSSS), but LoRa is our focus today.
Effects of Bandwidth on Time Precision
The radio demodulator is the apparatus that is interpreting all symbols (i.e. bits) in a received signal, including such edges as described above. If the demodulator can run at a very high frequency — say 1 GHz — it will naturally have high time precision, because each symbol (i.e. bit) that it receives is being streamed-in every 1 nanosecond. If the demodulator runs at 1 MHz, each symbol (bit) is received each 1 microsecond. The higher the bandwidth of the demodulator, the higher time precision it has.
If we make it a requirement that a location system must deliver one meter precision, we need to ensure that time precision is better than 3 nanoseconds (light travels 1 meter in about 3 nanoseconds). A 3 nanosecond symbol (bit) stipulates a 333 MHz radio bandwidth. There are certain techniques that can be used to improve the bandwidth efficiency of a high data rate message, but in any case the bandwidths become prohibitively large as precision requirements become stricter. Additionally, there is another problem: as the bits get “shorter”, the energy of each bit gets smaller. Smaller bit energy means shorter radio range. Achieving high time precision on a low bandwidth demodulator — one which can also provide long communication range — is one of the principal challenges of our work on geolocation today at Haystack.
Using Ensemble Averages to Extrapolate High Precision Edges
The LoRa demodulator has a 500 kHz bandwidth, so the intrinsic time precision of LoRa is 2 microseconds. In 2 microseconds, a radio signal can travel 670 m, so we need to do something more in order to implement a high precision edge. Fortunately, we can do this by averaging an “ensemble” of edges against a reference interval — GPS uses this same basic strategy.
The downside of this strategy is that there is a lot of time-on-air for the ensemble transmissions. With LoRa, each packet in the ensemble must be sent at a precise, fixed interval which is at smallest about 3 milliseconds. If we want to deliver 20 nanosecond time precision (±10 ns, or ± 3.3m), we can theoretically build an average across an ensemble of 100 edges of 2 microseconds precision, and this requires a minimum of about 300 milliseconds to transmit. For Uplink TDOA, it becomes impractical when hundreds or even thousands of endpoints in range of each other are transmitting concurrently to provide their locations. Furthermore, if the endpoints are battery powered, there is a huge energy cost in sending frequent, long transmissions.
For Downlink TDOA, on the other hand, ensemble averaging can be practical. GPS has 32 satellites in orbit, which broadcast their ensembles. As the endpoints are just receivers, there can be a theoretically infinite number of them. If the broadcast infrastructure is ground-based, as with LORAN, the same principles are true.
Working Around the Challenges
A LoRa-based system implementing downlink-based TDOA is therefore ground-based and uses ensemble averaging to provide high-precision timing, much like LORAN. Compared to LORAN, modern technology advances massively reduce the cost, size, and oversight required to deploy the infrastructure. Modern computation, networking, and software have advanced such to the extent which they can be deployed at a consumer price target, in consumer environments, and without a centralized management authority if you consider nascent efforts like FOAM.
With a LoRa-based system of downlink-based TDOA, the gateway nodes require a moderate, reliable power source (e.g. 1 Watt) as well as a reliable means of orchestrating the transmissions. The power requirement is achievable easily via a reliable grid or with very inexpensive solar & battery generators.
What We Are Observing At Haystack
We will share more on this in the near future, but currently we have validated using a memory oscilloscope in the lab, that:
- Low-cost LoRa gateways can implement an ensemble-averaged time measurement system, with better than 11 nanosecond precision. In other words, less than four meter precision, which is better (yes, only in the lab so far) than GPS.
- The DASH7 Advertising Protocol invented by Haystack forms the basis for this high-precision gateway synchronization technique. The DASH7 Background Flood message type forms the basis of a “synchronization message,” which is an ensemble of very small packets. I have written before about DASH7’s unique synchronization capabilities, but here we are taking this capability a step further.
- Downlink TDOA using DASH7 and LoRa can employ location beacons (or just gateways) that require no communication backhaul and may be powered by a wall plug or inexpensive solar panel. In other words, a ground-based alternative to GPS. It’s also possible to use the high-accuracy GPS time source to synchronize those location beacons and gateways — the GPS time signal is relatively easy to receive, sometimes even indoors.
- Low-cost, low-power microcontrollers can support high precision time references.
- Ensemble-averaged time measurement can run on microcontroller firmware.
- The low-cost LoRa gateways utilize the $3.00 SX1276 endpoint radio, not the much more expensive ($60.00+) SX1301, as discussed in this post last week.
- The core challenge in the implementation of a Downlink TDOA network, is maintaining the high precision synchronization between transmitters. This is a difficult challenge, but it is a solved problem. LORAN does it, GPS does it, and only Haystack does it over LoRa.
Get the latest about Haystack by signing up for our newsletter here.
