Localisation and tracking

Localisation and tracking

Localisation is attracting increased attention from both research and industry. Real time location information about people and objects offers a wealth of opportunities for improving user experiences in shopping, trade shows, conferences, museums, etc. which in turn could lead to more focused personalised experiences. In addition, it can automate tasks in warehouses like asset tracking and fork lift navigation. In the entertainment industry it can be used in large scale for crowd monitoring at festivals, and in small scale for controlling (follow spot) lights that light up performers. Health and safety are other important fields that can benefit from indoor localisation. In work environments where humans and machines work closely together, indoor positioning can mitigate the risk of people getting too close to running machines. In health care, indoor positioning combined with realtime tracking of vital physiological data can be used to monitor patients or clients in an elderly care home.

In indoor environments, the traditional services provided by e.g. GNSS solutions like GPS and GLONASS are usually not available, unreliable or inaccurate. For this reason, other technical solutions need to be applied. Needless to say that indoor localisation methods can also be applied outdoors.

For (indoor) positioning there are roughly three methods available: 

• Scene analysis (finger printing)
• Proximity localization
• Geometrical localization
  

In Scene analysis based localization, features (fingerprints) of a scene are collected and then estimation of the location of an object is done by matching online measurements with the closest a priori location fingerprints. This requires prior knowledge of the environment.

Proximity localization is another technique that provides us with a relative position. A number of anchor sensors with known position are used, and the position of the target node is determined with respect to those anchor nodes. If the target node is detected by one of the reference nodes, then it is considered to be co-located with that reference node. This technique requires a dense sensor (anchor) environment to have good accuracy. An example of this type of localisation is the use of iBeacons.

Geometrical localization is the third method. It is generally composed of two steps: ranging and localization, see Figure 1.1. The ranging process is an action of estimating the distance. In special cases like in angle of arrival (AoA) techniques, it could also mean finding the direction or angle between two nodes with respect to a given reference. The most common ranging techniques are time of arrival (ToA), angle of arrival (AoA), received signal strength information (RSSI), time difference of arrival (TDoA) and two way time of flight (TW-TOF) techniques. Localization is the mechanism of finding the exact location of a given node by utilizing the range estimates.

‍

For ranging either device free or device based methods can be applied. Device free ranging compromises a class of localisation methods that do not require the use of devices carried by the “mobile nodes”. These class of method can be “vision based”, i.e. using computer vision techniques to localised objects in camera images. Other examples include radar or acoustic sensors. Device based methods rely on a device that is carried by the mobile “node”, i.e. a person or a moving (or movable) object like a fork lift or an x-ray scanner. Fixed receivers (also called anchors or base stations) are deployed in a confined area to receive messages from the mobile nodes. Based on certain characteristics of the received messages a ranging measurement can be performed. Roughly, these characteristics are either signal strength (RSSI), angle of arrival (AoA) or time of arrival (ToA) or a hybrid combination of these. Each of these characteristics will be described in more detail.

RSSI

RSSI makes use of the received signal energy for estimating the distance. This approach relates the attenuation in the signal energy with distance. However, this requires prior knowledge of the environment and the so called  exponent regarded for that environment. If we have the knowledge of the path loss of the environment and the transmitted power, then, by measuring the strength of the received signal we can estimate the distance between the transmitting and receiving nodes. RSSI avoids the need for synchronization. This is the main advantage of RSSI. Therefore, this technique is regarded as simple and less power consuming. However, the inaccuracies present in estimating the shadowing and fading of the environment and in estimating the RSSI lead to a large ranging error.

Time of Arrival 

‍

In the ToA technique, the receiver measures the travel time, and, accordingly, estimates the distance. It is simple, and, therefore, cost effective. The distance estimate is given by the estimated time of flight multiplied by the velocity of the signal, which is the speed of light for electromagnetic waves. This mechanism is highly accurate when there is a direct path i.e. line of sight (LOS) between the nodes. However, its accuracy is degraded when the nodes are not in line of sight, i.e. when the nodes are either in obstructed line of sight (OLOS) or non-line of sight (NLOS). This is because of the additional time bias introduced by the obstacles. The ToA technique requires very precise knowledge of the transmission start time, and must ensure synchronization between the nodes involved. TW-ToF, can be used in order to avoid the need for synchronization. In this case, a round trip time is used to estimate the distance between the nodes. TDOA is another technique that avoids the need for synchronization between the target and anchor nodes.

‍

Angle of Arrival

In the AoA technique, the estimation of the signal reception angles, from at least two sources, is

compared with either the signal amplitude or carrier phase across multiple antennas. The location can be found from the intersection of the angle line for each signal source, see Figure 4. AoA estimation algorithms are very sensitive to many factors, which may cause errors in their estimation of target position.   Furthermore,  AoA  estimation  algorithms  have  a  higher  complexity  compared  to  other methods. For instance, the antenna array geometry has a major role in the estimation algorithm.

Increasing the distance between the sender and receiver may decrease the accuracy.  The AoA technique can be used with other techniques to increase its accuracy.

UWB vs Wifi/Bluetooth

Ultra Wide Band (UWB) signals are characterized by a bandwidth which is either greater than 500 MHz or exceeding 20% of the center frequency of radiation. This wide spectrum is often implemented by generating waveforms with short pulses, in the order of nanoseconds.

Because of the very small pulse duration, UWB improves the multipath resolvability. Multipath resolvability is defined as the number of paths that can be separated by a receiver. Thus, one of the advantages of UWB is its ability to distinguish between multipaths. Because of the lower frequency components, UWB signals can penetrate obstacles reaching to objects that are hidden or shadowed by certain materials.

It is mainly those two advantages (multipath resolvability and penetration through obstacles) that make UWB the most appropriate solution for indoor localization and ranging. Additionally, UWB signals can be transmitted without a carrier and therefore are known as carrierless signals, giving rise to lower cost, more power efficient receivers, and less complex front end design. This makes them suitable for sensor technology. According to the FCC, in order to avoid any interference that could be caused by UWB to other currently present technologies, the maximum transmission power is subject to −41 dBm/MHz, limiting its application to moderate data rates or short range communication. Theoretically, UWB can offer sub-centimeter level ranging accuracy with a very high precision.

In comparison Wifi and Bluetooth are relying on so called narrow band radio. The bandwidth of a default Wifi channel is only 20MHz, while Bluetooth channel bandwidth is only 1 MHz. As a result the signal modulation for Wifi and Bluetooth is completely different than UWB. The data is modulated by varying power level, phase, frequency and amplitude. Instead, UWB uses generated pulses with a certain spacing in time between the pulses to code information. To generate a sharp pulse all frequencies in the entire bandwidth of the UWB radio are used. The sharp pulse characteristic allows for precise time of arrival determination compared to the more curved signals produced by narrow band radio.

For both narrow band as well as ultra wide band radio, all three ranging methods can be applied. However, due to the pulse character of UWB, the AoA and ToA ranging methods have a much higher accuracy for UWB. For RSSI based ranging the difference between narrow band and ultra wide band is not so prominent. 

Localisation and tracking algorithms

To perform geometrical localization, fixed anchor nodes are required. Geometrical techniques can be divided into triangulation and trilateration. Triangulation needs angle information in determining the location of a target node. In order to have angle information, there is a need for an array of antennas or a directional antenna, which makes it complex and less cost effective.

Using trilateration to calculate the 3D position of a mobile node based on 4 distances is mathematically not very complicated if the distances are known to be exact. However, in reality the distances are not exact, even though UWB is considered to produce pretty precise distance measurements. The problems arise trying to cope with inaccuracy. First of all it is beneficial to use much more than just 4 distance measurements to do a location calculation. Measurement errors can be averaged out when using many distances. One of the most obvious mathematical techniques to calculate “optimal location” is using a so called Nonlinear Least Square (NLS) Algorithm. However,  this technique does not rely on “historic locations”. In case of a moving object, like a person, there is additional “information” that can be used to calculate positions. Mostly the jargon switches to “tracking” in these cases. Using historic locations have mathematically proven benefits. One of the most famous algorithms to exploit these historic information is the Kalman Filter that was invented in 1960. Since then several variations of the Kalman Filter have been derived, let’s call them the Kalman family:

• Extended Kalman Filter
• Finite Impulse Response Filter
• Particle Filter
• Bayesian methods

To summarise, these algorithms use “distance measurements” and “historic positions” to calculate the track of a moving object. 

However, besides the two sources of information, additional sources can be added like for example data coming from a so called Inertial Movement Unit (IMU). These sensors are well known and every mobile phone has one. An IMU is responsible, among other things, for switching your screen from portrait to landscape for example. An IMU sensor is in fact a composed sensor. It almost always has an “accelerometer” and a “gyroscope”. Accelerometer measure acceleration (in all three spatial dimensions) and a gyroscope measures the so called “angular velocity” of an object. In many cases an IMU is complemented with a “magnetic compass” that measures the angle of the magnetic north. An IMU can be used to measure the orientation of an object. Note that orientation and location are two separate things. Also, by applying the laws of (Newton/classical) mechanics, the data coming from an IMU can be used to calculate (relative) location as well. However, due to measurements errors and the mathematical nature by which the location is calculated, a location calculated by IMU only is only  valid for a short time frame.

It is clear that an IMU can supply another source of information for our Kalman family algorithms making it possibly even more accurate.

‍