When You Can’t See The Sky: How To Back-Up GPS

One frequently asked question: what happens if GPS is not available when using Haystack’s new line of LoRa hardware. For some this is about endpoints moving from an outdoor environment to an indoor one, for others it’s about redundancy in case a GNSS/GPS constellation fails, and for others the question is about how accurate Haystack is without GPS. But it’s a good question that Haystack answers better than anyone in the LPWAN industry. I wrote something kind of windy on this a while back but here’s an update/rehash:

Two Approaches

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.

By the way, we recommend using signal strength-based location (RSSI) with Semtech’s LoRa radio for non-GPS location, vs. time-based approaches.

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 form circles of radii corresponding to the distance measurement of the unknown endpoint. The intersection of the circles ultimately yields the position of the endpoint. Adding gateways or, more commonly, assuming an endpoint is in motion further refines the derived location. (When gateways are mobile the same effect occurs.)

So to summarize, if your Haystack endpoint is unable to acquire GPS location, RSSI-based trilateration is our recommended fallback using LoRa. And it’s the go-to method for indoor location.

Nearest Neighbor

For some indoor location use cases, a simple “nearest neighbor” approach may suffice for situations where you want room-level location or in, say, a mine shaft and you need to know where along the shaft someone left the box of TNT.

Let’s take the use case of a missing piece of IT equipment in a floor layout like this:

Below you will see a red star, which denotes the location of Hal’s laptop containing valuable company data. The laptop is closed and powered off but Hal’s IT team wisely added a HayTag to it. Hal left the building and his laptop behind and normally everyone in the company would be freaking out because competitor X would love to get their hands on Hal’s laptop.

But Hal’s company added a fixed HayTag reference endpoint in each room and around the open areas on the floor. Each endpoint is battery powered, affixed to the wall or ceiling by two-sided adhesive, and is very inexpensive. Like the mobile endpoint affixed to Hal’s laptop, the reference endpoints run Semtech’s LoRa radio along with Haystack’s networking stack.

Hal and his team under conventional circumstances would be freaking out looking for the laptop, but with this setup they just call Glenda in IT who does a query to see if John’s laptop is anywhere on the company’s premises. In the course of the query, Glenda illuminates all fixed reference endpoints in a building like this:

In this example, the endpoint on Hal’s laptop receives a peer-to-peer query from those nearby fixed (or mobile, if you like) endpoints and in response, sends a message to a gateway containing the combined received signal strength information from the fixed endpoints. Here, fixed endpoint “R1” is likely to provide the strongest RSSI value in response to the query, and this is where Hal will go to recover his laptop and keep his job.

Time Difference of Arrival (TDOA)

Time based approaches to RTLS are also supportable in LoRa. 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.

If you’ve been looking at your options for non-GPS location over LoRaWAN, then this is probably what their brochure says. 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.
• 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.