Locating End Devices with Semtech’s LoRa Cloud™ Geolocation Service

Introduction

Being able to locate end devices is one of the most important technologies for adding value to wireless sensors and many Internet of Things (IoT) applications. Various positioning technologies are available, though the Global Positioning System (GPS) is probably the most widely known. However, in many cases GPS may not be the best choice; for example, indoor applications where the GPS signal would be weak, or in battery-powered sensors where low power consumption is critical. Semtech’s LoRa® devices and wireless radio frequency technology (LoRa Technology) is quickly becoming the de facto standard for connecting battery-powered devices over wide areas. The ability to use LoRaWAN®-based networks to locate end devices is uniquely attractive as a geolocation technology. The end device works entirely within the LoRaWAN-based network and requires no additional hardware or power source.

In general, a radio-based locator system consists of several reference nodes with known positions, and an end device, whose position needs to be discovered. In this document, we shall refer to reference nodes as gateways, and end devices as target nodes. To locate a target node, one or more radio signal measurements must take place between the target node and the gateways. Allows us to obtain the information that characterizes the spatial relationship between the target node and each gateway. Typical measurements include the Received Signal Strength Indication (RSSI), Signal to Noise Ratio (SNR), Frequency Offset, Angle of Arrival (AOA), and Time of Arrival (TOA). Based on some or all of these measurements, along with the known positions of the gateways, a location algorithm can calculate the most likely position of the target node.

In this document, we will assume the locator system includes several gateways and one or more target nodes. The gateways may be equipped with one or more antennas, while target nodes will normally have only one. All gateways are time-synchronized through a synchronization scheme such as the Global Navigation Satellite System (GNSS). However, the target node does not need to be synchronized. Instead, it will transmit packets periodically at a predetermined rate. These packets will then be received by some or all of the gateways. Each gateway will measure the RSSI and SNR for each packet received. Depending on the gateway model, it may also produce a precise timestamp representing the TOA of the received packet. If only the RSSI and SNR measurements are available, an RSSI-based algorithm can be used to estimate the location of the target node. If the RSSI, SNR and TOA measurements are all available, the location of the target may be estimated using Time Difference of Arrival (TDOA)-based multilateration algorithms.

The location algorithm is also called a location solver. Semtech’s LoRa Cloud Geolocation offers both RSSI and TDOA-based location solvers.

Location Accuracy

Many factors may affect the accuracy of determining a target’s location. These include the quality of RSSI, SNR and TOA measurements, the Geometric Dilution of Precision (GDOP), the location solver algorithm, and other factors we will explore in this document.

Quality of Measurements

The quality of measurements is affected by both the transmitting and receiving processes. Radio packets may travel through multiple transmission paths and experience significant signal fade before reaching the receiver. Therefore, the receiver may receive multiple copies of the same packet, each arriving from different directions and reflected paths. This is called multipath and fading. Depending on the differences in length between different paths, multipath and fading may cause significant interference (both positive and negative), and cause the receiver difficulty in determining one signal from another. To derive the location of a target node, the Line of Sight (LOS) path is best, since its path length correctly represents the true distance between transmission and reception points. All other paths within the multipath will have a path length that is longer than the true distance and will cause an error in the ranging measurement. Each path may be very different, depending on the receiver’s position, because reflections are determined by the locations of the transmitter and the receiver. Therefore, it is possible to reduce the multipath effect by positioning the gateways in carefully chosen locations, such as in open and higher ground.

The packet-reception process at a gateway will also introduce a random error on all measurements. The level of random error is primarily determined by the system and any error in the time base (e.g. the GNSS signal). In general, a packet received with a higher SNR will result in a lower random-noise-based error. Since signal strength decreases with distance, a high density of gateways can help prevent low signal strength and SNR. In most cases, the random error introduced in the packet-reception process is less significant than that from multipath and fading.

Geometric Dilution of Precision (GDOP)

The relative positions between the target node and gateways not only affects the quality of RSSI and TOA measurements, but also errors in locating target nodes by means of GDOP. GDOP can be considered an “error enhancement” factor. For the same level of measurement error, a larger GDOP translates to a higher error rate in locating a target node. GDOP is determined by the relative spatial relation of the target node to all receiving gateways. When deploying gateways, it is desirable to make sure the GDOP at all possible positions of the target node is minimal. As a rule, gateways may be deployed so that most, if not all, target nodes will be inside the maximum convex polygon formed by the gateways. For example, if the total number of gateways is six, a hexagonal positioning of gateways would be a good choice. This would achieve the most coverage space for the given density of gateways, thereby including more target nodes inside the broadcast range. This, in turn, would lead to a small GDOP. For some applications where only two-dimensional location identifications are concerned, the Horizontal Dilution of Precision (HDOP) can be used.

With gateways positioned as shown in the figure below (the white circles), notice how errors rapidly expand as device locations approach the outside of the six-gateway grid.

Note: The blue ovals indicate how the GDOP affects the size and direction of the location uncertainty. A bigger oval indicates greater amplification of uncertainty while the shape and direction of the ovals show that, approaching the edge of a network, uncertainty is greater in some directions than others.”

Gateway, Packet and Frequency Diversity

Imperfect measurements lead to errors in the location estimate. Proper positioning of the gateways may reduce the error. However, there are other techniques that can be used to improve location accuracy, such as increasing the number of gateways.

In order to produce a valid TDOA-based location estimate, at least three gateways are needed. In some cases, a fourth gateway is needed to completely remove location ambiguity. Extra gateways provide additional benefits. For example, some gateways may receive a packet with a reduced multipath effect. By combining all measurement data from all the gateways, a better location accuracy can be achieved. This is known as gateway diversity gain. Of course, increasing the number of gateways comes with an increased deployment cost.

For a constant number of gateways, location accuracy can be improved by increasing the number of antennas at each gateway. Even though the distance between two antennas may be small (about one meter), the multipath effect can be significantly different. Thus, in some cases when two antennas are fitted to the same gateway, there may be a considerable improvement in the quality of the TOA measurement. This is called antenna diversity gain.

Packet diversity is another effective way to improve accuracy. As it happens, doubling the number of packets sent from the same location could lead to improved accuracy by a factor of √2 (the square root of two). This is based on the assumption that the solver algorithm is properly designed, and the measurement error in each data packet is statistically independent. In reality, this may not always be the case, particularly for the multipath channel. To ensure that multipath fading is independent, different packets can be sent on different frequency channels, exposing each packet to different multipath and fading effects. This multiple-frequency approach is referred to as joint-packet and frequency diversity. In the presence of a strong multipath effect, location error may decrease as the number of packets transmitted increases. Upon reaching a lower bound, increasing packet numbers will not bring additional improvement.

It may be difficult to predict exactly what type and how much diversity is needed to achieve a certain level of accuracy. This will depend heavily on the field conditions. Based on field tests of eight packets and two antennas per gateway, five or more gateways are probably required to achieve average location error for a range of 50-100 meters in a typical urban area.

Location Solvers

Location solvers can be categorized as RSSI-based, where only RSSI and SNR measurements are used, or TDOA-based, where TOA, RSSI and SNR measurement are used.

RSSI-based Solver

RSSI measurements carry only an estimate of the target node’s ranging information. This is due to the fact that signal strength attenuates with the distance between the transmitter and the receiver. Various algorithms have been developed to estimate a target node’s location based on RSSI. This is referred to as an RSSI-based solver. In general, the attenuation of signal strength approximately follows an exponential law. However, the exact attenuation model varies depending on the environment and can be quite complicated. Without extra measurement and calibration, the attenuation exponent is generally unknown and the solver cannot get accurate ranging information from an RSSI measurement. The solver, which is not explicitly based on ranging information, is called a non-ranging solver.

By carefully calibrating several specific reference points, one can establish a more accurate relationship between the measured RSSI and the distance to the target node. With this information, one can extract ranging information. Once the ranging information has been determined, a ranging-based algorithm can be used to achieve better accuracy. The error in the computed range increases significantly with distance due to the fact that signal strength decreases by an exponential law. Therefore, this method is only feasible when all gateways and target nodes are located within a relatively confined area.

As illustrated below, another problem with signal strength-based techniques is that the signal attenuates significantly when passing through objects like walls and windows:

Using Signal Strength to measure distance is tough

Another way to get a more accurate location estimate is the fingerprint method, in which the whole field is split into a grid of cells. For packets sent from each cell, the corresponding RSSI at each receiving gateway is measured. The RSSI measurements from all gateways form a “fingerprint” relating to that cell. The fingerprints of all cells are measured and stored in a database. The fingerprint solver determines the location of the target node by matching fingerprints to identify the cell where the target node is most likely to be.

In Semtech’s LoRa Cloud Geolocation Service, only non-ranging solvers are currently supported. Although non-ranging solvers provide less location accuracy than ranging-based or fingerprint solvers, these are simple and are applicable to both small and large fields. The algorithms available support queries with either single or multiple-packets. Additionally, location accuracy improves by increasing the number of packets included in the query.

TDOA-based Solver

When both TOA and RSSI measurements are available, a TDOA-based solver can be used to achieve better location accuracy. This solver design may be based on various algorithms, such as Least Mean Square, Kalman Filter, Particle Filter, etc. The complexity and performance of various algorithms also varies, and they can be affected by the motion of the target node.

As noted above, the main challenge in designing a solver is combating the multipath effect. Some algorithms may be good for a line of sight (LOS) channel but may behave poorly in the presence of multipath spread. All forms of diversity (gateway, antenna, packet, and frequency) help to improve location accuracy.

One reason time-based algorithms can be more accurate is that they are less affected by passing through objects. While the signal strength is significantly reduced, the signal does not travel appreciably slower, as illustrated below:

Using Flight time to measure distance is easier

Semtech’s TDOA solver makes good use of gateway and packet diversity, as well as other multipath mitigation techniques, for better accuracy of both LOS and multipath channels.

 From the outset, LoRa Cloud Geolocation supports one-shot, single-frame and multi-frame location estimation. These algorithms make the assumption that all data contained within a single query has been transmitted from the same location, and compute a single location result. If the query contains information from a single packet (i.e. a single uplink), the algorithm will return the best estimate it can make based on that single packet. Where more than one packet is transmitted from the same location, the data can be combined into a single query and fed to the multi-frame solver. The solver will return a single location estimate based on all information sent in the multi-frame query. The solver does not use any history data or status information, since there is no historical information stored in the LoRa Cloud Service.

Current location estimation works well for static target nodes, given that multiple packets (up to 128) can be sent to the solver in one call. However, for moving target nodes, the application should perform tracking filtering on the returned locations. Since all packets in a single query are assumed to come from the same location, a location-tracking algorithm can be used to improve the results.

The benefits of packet diversity and differences between the RSSI and TDOA method for a typical measurement in an urban area can be seen in the graph below. Typical measurements include RSSI, SNR, and a timestamp of when the packet was received

Figure 1: Legend:

rssi – 1 = RSSI result on single packets
rssi – 2 = RSSI result for 2 packets in each query
rssi – 4 = RSSI result for 4 packets in each query
rssi – 8 = RSSI result for 8 packets in each query
rssi – 16 = RSSI result for 16 packets in each query
tdoa -  1 = TDOA-based result for single-packet queries
tdoa -  2 = TDOA-based result for 2-packet queries
tdoa -  4 = TDOA-based result for 4-packet queries
tdoa -  8 = TDOA-based result for 8-packet queries
tdoa -  16 = TDOA-based result for 16-packet queries
tdoa -  128 = TDOA-based result for 128-packet queries