User:Electron9/Multilateration

Multilateration, also known as hyperbolic positioning, is the process of locating an object by accurately computing the time difference of arrival (TDOA) of a signal emitted from the object to three or more receivers. It also refers to the case of locating a receiver by measuring the TDOA of a signal transmitted from three or more synchronised transmitters.

Multilateration should not be confused with trilateration, which uses distances or absolute measurements of time-of-flight from three or more sites, or with triangulation, which uses a baseline and at least two angles measured e.g. with receiver antenna diversity and phase comparison.

Principle

Multilateration is commonly used in civil and military surveillance applications to accurately locate an aircraft, vehicle or stationary emitter by measuring the time difference of arrival (TDOA) of a signal from the emitter at three or more receiver sites.

If a pulse is emitted from a platform, it will arrive at slightly different times at two spatially separated receiver sites, the TDOA being due to the different distances of each receiver from the platform. In fact, for given locations of the two receivers, a whole set of emitter locations would give the same measurement of TDOA. Given two receiver locations and a known TDOA, the locus of possible emitter locations is a one half of a two-sheeted hyperboloid.

In simple terms, with two receivers at known locations, an emitter can be located onto a hyperboloid^[1]. Note that the receivers do not need to know the absolute time at which the pulse was transmitted - only the time difference is needed.

Consider now a third receiver at a third location. This would provide a second TDOA measurement and hence locate the emitter on a second hyperboloid. The intersection of these two hyperboloids describes a curve on which the emitter lies.

If a fourth receiver is now introduced, a third TDOA measurement is available and the intersection of the resulting third hyperboloid with the curve already found with the other three receivers defines a unique point in space. The emitter's location is therefore fully determined in 3D.

In practice, errors in the measurement of the time of arrival of pulses mean that enhanced accuracy can be obtained with more than four receivers. In general, N receivers provide N-1 hyperboloids. When there are N > 4 receivers, the N-1 hyperboloids should, assuming a perfect model and measurements, intersect on a single point. In reality, the surfaces rarely intersect, because of various errors. In this case, the location problem can be posed as an optimization problem and solved using, for example, a least squares method or an extended Kalman filter.

Additionally, the TDOA of multiple transmitted pulses from the emitter can be averaged to improve accuracy.

Reciprocal case: locating a receiver from multiple transmitter sites

Multilateration can also be used by a single receiver to locate itself, by measuring the TDOA of signals emitted from three or more synchronised transmitters at known locations. This can be used by navigation systems, an example being the British DECCA navigation system, developed during World War II, which used the phase-difference of two transmitters, rather than the TDOA of a pulse, to define the hyperboloids. This allowed the transmitters to broadcast a continuous wave signal. Phase-difference and time-difference can be considered the same for narrow-band transmitters.

Derivation

Consider an emitter at unknown location $(x,y,z)$ which we wish to locate. Consider also a multilateration system comprising four receiver sites at known locations: Central site, Left site,, Right site, fourth site - Q.

The travel time (T) of pulses from the emitter at ( $x,y,z$ ) to each of the receiver locations is simply the distance divided by the pulse propagation rate (c):

T_{L}={\frac {1}{c}}\left({\sqrt {(x-x_{L})^{2}+(y-y_{L})^{2}+(z-z_{L})^{2}}}\right)

T_{R}={\frac {1}{c}}\left({\sqrt {(x-x_{R})^{2}+(y-y_{R})^{2}+(z-z_{R})^{2}}}\right)

T_{Q}={\frac {1}{c}}\left({\sqrt {(x-x_{Q})^{2}+(y-y_{Q})^{2}+(z-z_{Q})^{2}}}\right)

T_{C}={\frac {1}{c}}\left({\sqrt {(x-x_{C})^{2}+(y-y_{C})^{2}+(z-z_{C})^{2}}}\right)

If the site C is taken to be at the coordinate system origin,

T_{C}={\frac {1}{c}}\left({\sqrt {x^{2}+y^{2}+z^{2}}}\right)

Then the time difference of arrival between pulses arriving directly at the central site and those coming via the side sites can be shown to be:

\tau _{L}=T_{L}-T_{C}={\frac {1}{c}}\left({\sqrt {(x-x_{L})^{2}+(y-y_{L})^{2}+(z-z_{L})^{2}}}-{\sqrt {x^{2}+y^{2}+z^{2}}}\right)

\tau _{R}=T_{R}-T_{C}={\frac {1}{c}}\left({\sqrt {(x-x_{R})^{2}+(y-y_{R})^{2}+(z-z_{R})^{2}}}-{\sqrt {x^{2}+y^{2}+z^{2}}}\right)

\tau _{Q}=T_{Q}-T_{C}={\frac {1}{c}}\left({\sqrt {(x-x_{Q})^{2}+(y-y_{Q})^{2}+(z-z_{Q})^{2}}}-{\sqrt {x^{2}+y^{2}+z^{2}}}\right)

where $(x_{L},\ y_{L},\ z_{L})$ is the location of the left receiver site, etc, and $c\$ is the speed of propagation of the pulse, often the speed of light. Each equation defines a separate hyperboloid.

The multilateration system must then solve for the unknown target location $(x,y,z)$ in real time. All the other symbols are known.

Note that in civilian air traffic control multilateration systems, the unknown height, $z$ , is often directly derived from the Mode C SSR transponder return. In this case, only three sites are required for a 3D solution.

2D

\tau _{L}=T_{L}-T_{C}={\frac {1}{c}}\left({\sqrt {(x-x_{L})^{2}+(y-y_{L})^{2}}}-{\sqrt {x^{2}+y^{2}}}\right)

\tau _{Q}=T_{Q}-T_{C}={\frac {1}{c}}\left({\sqrt {(x-x_{Q})^{2}+(y-y_{Q})^{2}}}-{\sqrt {x^{2}+y^{2}}}\right)

Multilateration accuracy

For trilateration or multilateration, calculation is done based on distances, which requires the frequency and the wave count of a received transmission. For triangulation or multiangulation, calculation is done based on angles, which requires the phases of received transmission plus the wave count.

For lateration compared to angulation, the numerical problems compare, but the technical problem is more challenging with angular measurements, as angles require two measures per position when using optical or electronic means for measuring phase differences instead of counting wave cycles.

Trilateration in general is calculating with triangles of known distances/sizes, mathematically a very sound system. In a triangle, the angles can be derived if one knows the length of all sides, (see congruence), but the length of the sides cannot be derived based on all of the angles, not without knowing the length of at least one of the sides (a baseline) (see similarity).

In 3D, when four or more angles are in play, locations can be calculated from n+1=4 measured angles plus one known baseline or from just n+1=4 measured sides.

Multilateration is, in general, far more accurate for locating an object than sparse approaches such as trilateration, where with planar problems just three distances are known and computed. Multilateration serves for several aspects:

over-determination of an n-variable quadratic problem with (n+1)+m quadratic equations
stochastic errors prohibiting a deterministic approach to solving the equations
clustering needs to segregate members of various clusters contributing to various models of solving, i.e. fixed locations, oscillating locations and moving locations

Accuracy of multilateration is a function of several variables, including:

The antenna or sensor geometry of the receiver(s) and transmitter(s) for electronic or optical transmission.
The timing accuracy of the receiver system, i.e. thermal stability of the clocking oscillators.
The accuracy of frequency synchronisation of the transmitter oscillators with the receiver oscillators.
Phase synchronisation of the transmitted signal with the received signal, as propagation effects as e.g. diffraction or reflection changes the phase of the signal thus indication deviation from line of sight, i.e. multipath reflections.
The bandwidth of the emitted pulse(s) and thus the rise-time of the pulses with pulse coded signals in transmission.
Inaccuracies in the locations of the transmitters or receivers when used as a known location

The accuracy can be calculated by using the Cramér–Rao bound and taking account of the above factors in its formulation.

Example applications

Decca Navigator System - A system used from the end of World War II to the year 2000, employing the phase-difference of multiple transmitters to locate on the intersection of hyperboloids
OMEGA Navigation System - A worldwide system similar to Decca, shut down in 1997
GEE - British aircraft location technique from World War II, using accurate reference transmitters
LORAN-C - navigation system using TDOA of signals from multiple synchronised transmitters
Passive ESM multilateration systems, including Kopáč, Ramona, Tamara, VERA and possibly Kolchuga - location of a transmitter using multiple receivers
GSM localization - using multiple base stations to estimate phone location (by either the phone itself, or the phone network)
Reduced Vertical Separation Minima (RVSM) monitoring using Secondary Surveillance Radar - Mode C/S transponder replies to calculate the position of an aircraft. Application to RVSM was first demonstrated by Roke Manor Research Limited in 1992.

References

The Bucher Algorithm, which can solve the multilateration problem
The Multilateration Executive Reference Guide is an easy-to-read reference for air traffic management, airport and airline professionals to learn more about this next-generation surveillance technology

Notes

^ In other words, given two receivers at known locations, one can derive a three-dimensional surface (characterized as one half of a hyperboloid) for which any two points on said surface will have the same differential distance from said receivers, i.e., a signal transmitted from any point on the surface will have the same TDOA (measured by the receivers) as a signal transmitted from any other point on the surface.
Therefore, in practice, the TDOA corresponding to a (moving) transmitter is measured, a corresponding hyperbolic surface is derived, and the transmitter is said to be "located" somewhere on the that surface.

Category:Elementary geometry Category:Euclidean geometry Category:Radio navigation Category:Geolocation Category:Ubiquitous computing Category:Wireless locating

[1] In other words, given two receivers at known locations, one can derive a three-dimensional surface (characterized as one half of a hyperboloid) for which any two points on said surface will have the same differential distance from said receivers, i.e., a signal transmitted from any point on the surface will have the same TDOA (measured by the receivers) as a signal transmitted from any other point on the surface.
Therefore, in practice, the TDOA corresponding to a (moving) transmitter is measured, a corresponding hyperbolic surface is derived, and the transmitter is said to be "located" somewhere on the that surface.

[1]