Multilateration
Encyclopedia
Multilateration is a navigation
Navigation
Navigation is the process of monitoring and controlling the movement of a craft or vehicle from one place to another. It is also the term of art used for the specialized knowledge used by navigators to perform navigation tasks...

 technique based on the measurement of the difference in distance to two or more stations at known locations that broadcast signals at known times. Unlike measurements of absolute distance or angle, measuring the difference in distance results in an infinite number of locations that satisfy the measurement. When these possible locations are plotted, they form a hyperbolic curve
Hyperbola
In mathematics a hyperbola is a curve, specifically a smooth curve that lies in a plane, which can be defined either by its geometric properties or by the kinds of equations for which it is the solution set. A hyperbola has two pieces, called connected components or branches, which are mirror...

. To locate the exact location along that curve, a second measurement is taken to a different pair of stations to produce a second curve, which intersects with the first. When the two are compared, a small number of possible locations are revealed, producing a "fix".

Multilateration is a common technique in radio navigation
Radio navigation
Radio navigation or radionavigation is the application of radio frequencies to determine a position on the Earth. Like radiolocation, it is a type of radiodetermination.The basic principles are measurements from/to electric beacons, especially...

 systems, where it is known as hyperbolic navigation
Hyperbolic navigation
Hyperbolic navigation refers to a class of radio navigation systems based on the difference in timing between the reception of two signals, without reference to a common clock. Calculating the distance from the stations based on these timings produces a series of hyperbolic lines...

. These systems are relatively easy to construct as there is no need for a common clock, and the difference in the signal timing can be measured visibly using an oscilloscope
Oscilloscope
An oscilloscope is a type of electronic test instrument that allows observation of constantly varying signal voltages, usually as a two-dimensional graph of one or more electrical potential differences using the vertical or 'Y' axis, plotted as a function of time,...

. This formed the basis of a number of widely used navigation systems starting in World War II
World War II
World War II, or the Second World War , was a global conflict lasting from 1939 to 1945, involving most of the world's nations—including all of the great powers—eventually forming two opposing military alliances: the Allies and the Axis...

 with the British Gee
GEE (navigation)
Gee was the code name given to a radio navigation system used by the Royal Air Force during World War II.Different sources record the name as GEE or Gee. The naming supposedly comes from "Grid", so the lower case form is more correct, and is the form used in Drippy's publications. See Drippy 1946....

 system and several similar systems introduced over the next few decades. The introduction of the microprocessor
Microprocessor
A microprocessor incorporates the functions of a computer's central processing unit on a single integrated circuit, or at most a few integrated circuits. It is a multipurpose, programmable device that accepts digital data as input, processes it according to instructions stored in its memory, and...

 greatly simplified operation, greatly increasing popularity during the 1980s. The most popular hyperbolic navigation system was LORAN-C, which was used around the world until the system was shut down in 2010. Other systems continue to be used, but the widespread use of satellite navigation systems like GPS
Global Positioning System
The Global Positioning System is a space-based global navigation satellite system that provides location and time information in all weather, anywhere on or near the Earth, where there is an unobstructed line of sight to four or more GPS satellites...

 have made these systems largely redundant.

Multilateration should not be confused with trilateration
Trilateration
In geometry, trilateration is the process of determinating absolute or relative locations of points by measurement of distances, using the geometry of circles, spheres or triangles. In addition to its interest as a geometric problem, trilateration does have practical applications in surveying and...

, which uses distances or absolute measurements of time-of-flight
Time-of-flight
Time of flight describes a variety of methods that measure the time that it takes for an object, particle or acoustic, electromagnetic or other wave to travel a distance through a medium...

 from three or more sites, or with triangulation
Triangulation
In trigonometry and geometry, triangulation is the process of determining the location of a point by measuring angles to it from known points at either end of a fixed baseline, rather than measuring distances to the point directly...

, which uses the measurement of absolute angles. Both of these systems are also commonly used with radio navigation systems; trilateration is the basis of GPS.

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
Locus (mathematics)
In geometry, a locus is a collection of points which share a property. For example a circle may be defined as the locus of points in a plane at a fixed distance from a given point....

 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. 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
Optimization (mathematics)
In mathematics, computational science, or management science, mathematical optimization refers to the selection of a best element from some set of available alternatives....

 problem and solved using, for example, a least squares
Least squares
The method of least squares is a standard approach to the approximate solution of overdetermined systems, i.e., sets of equations in which there are more equations than unknowns. "Least squares" means that the overall solution minimizes the sum of the squares of the errors made in solving every...

 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
Decca Navigator System
The Decca Navigator System was a low frequency hyperbolic navigation system that was first deployed during World War II when the Allied forces needed a system which could be used to achieve accurate landings...

 navigation system, developed during World War II, which used the phase
Phase (waves)
Phase in waves is the fraction of a wave cycle which has elapsed relative to an arbitrary point.-Formula:The phase of an oscillation or wave refers to a sinusoidal function such as the following:...

-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.

TDOA geometry

Consider an emitter (E in Figure 2) at an unknown location vector
E = (x, y, z)


which we wish to locate. The source is within range of N+1 receivers at known locations
P0, P1, ..., Pm, ..., PN.

The subscript m refers to any one of the receivers:
Pm = (xm, ym, zm)
0 ≤ m ≤ N


The distance (R) from the emitter to one of the receivers in terms of the coordinates is


The math is made easier by placing the origin at one of the receivers (P0), which makes its distance to the emitter

Measuring the Time Difference in a TDOA System

The distance in equation is the wave speed () times transit time (). A TDOA multilateration system measures the time difference () of a wavefront touching each receiver. The TDOA equation for receivers m and 0 is


Figure 3a is a simulation of the a pulse waveform recorded by receivers and . The spacing between , and is such that the pulse takes 5 time units longer to reach than . The units of time in Figure 3 are arbitrary. The following table gives approximate time scale units for recording different types of waves.
cross-correlation
Cross-correlation
In signal processing, cross-correlation is a measure of similarity of two waveforms as a function of a time-lag applied to one of them. This is also known as a sliding dot product or sliding inner-product. It is commonly used for searching a long-duration signal for a shorter, known feature...

 function . The cross correlation function slides one curve in time across the other and returns a peak value when the curve shapes match. The peak at time = 5 is a measure of the time shift between the recorded waveforms, which is also the value needed for Equation .

Figure 3b is the same type of simulation for a wide-band waveform from the emitter. The time shift is 5 time units because the geometry and wave speed is the same as the Figure 3a example. Again, the peak in the cross correlation occurs at .

Figure 3c is an example of a continuous, narrow-band waveform from the emitter. The cross correlation function shows an important factor when choosing the receiver geometry. There is a peak at Time = 5 plus every increment of the waveform period. To get one solution for the measured time difference, the largest space between any two receivers must be closer than one wavelength of the emitter signal. Some systems, such as the LORAN C and Decca
Decca Navigator System
The Decca Navigator System was a low frequency hyperbolic navigation system that was first deployed during World War II when the Allied forces needed a system which could be used to achieve accurate landings...

 mentioned at earlier (recall the same math works for moving receiver & multiple known transmitters), use spacing larger than 1 wavelength and include equipment, such as a Phase Detector
Phase detector
A phase detector or phase comparator is a frequency mixer, analog multiplier or logic circuit that generates a voltage signal which represents the difference in phase between two signal inputs...

, to count the number of cycles that pass by as the emitter moves. This only works for continuous, narrow-band waveforms because of the relation between phase (), frequency (f) and time (T).
The phase detector will see variations in frequency as measured phase noise
Phase noise
Phase noise is the frequency domain representation of rapid, short-term, random fluctuations in the phase of a waveform, caused by time domain instabilities...

, which will be an uncertainty that propagates
Propagation of uncertainty
In statistics, propagation of error is the effect of variables' uncertainties on the uncertainty of a function based on them...

 into the calculated location. If the phase noise is large enough, the phase detector can become unstable.

3-D Solution

Equation is the hyperboloid described in the previous section, where 4 receivers (0 ≤ m ≤ 3) lead to 3 non-linear equations in 3 unknown values (x,y,z). The system must then solve for the unknown emitter location in real time.

Civilian air traffic control multilateration systems use the Mode C SSR
Secondary surveillance radar
Secondary surveillance radar is a radar system used in air traffic control , that not only detects and measures the position of aircraft i.e. range and bearing, but also requests additional information from the aircraft itself such as its identity and altitude...

 transponder return to find the altitude (z). Three or more receivers at known locations are used to find the other 2 dimensions (x, y).

R. Bucher and D. Misra show the detailed algebra to locate 1 receiver with TDOA between 3 transmitters. Their solution is a set of linear equations to find (x, y) and a quadratic for (z).

Improving accuracy with a large number of receivers can be a problem for devices with small embedded processors because of the time required to solve several simultaneous, non-linear equations . The TDOA problem can be turned into a system of linear equations when there are 5 or more receivers, which can reduce the computation time. Starting with equation , solve for Rm, square both sides, collect terms and divide all terms by :


Removing the 2 R0 term will eliminate all the square root terms. That is done by subtracting the TDOA equation of receiver m = 1 from each of the others (2 ≤ m ≤ N)


Focus for a moment on equation . Square Rm, group similar terms and use equation to replace some of the terms with R0.


Combine equations and , and write as a set of linear equations of the unknown emitter location x,y,z


Use equation to generate the four constants from measured distances and time for each receiver 2 ≤ m ≤ N. This will be a set of N homogeneous linear equations.

There are many robust linear algebra methods that can solve for the values of (x,y,z), such as Singular value decomposition
Singular value decomposition
In linear algebra, the singular value decomposition is a factorization of a real or complex matrix, with many useful applications in signal processing and statistics....

 or Gaussian Elimination
Gaussian elimination
In linear algebra, Gaussian elimination is an algorithm for solving systems of linear equations. It can also be used to find the rank of a matrix, to calculate the determinant of a matrix, and to calculate the inverse of an invertible square matrix...

. Chapter 15 in Numerical Recipes
Numerical Recipes
Numerical Recipes is the generic title of a series of books on algorithms and numerical analysis by William H. Press, Saul Teukolsky, William Vetterling and Brian Flannery. In various editions, the books have been in print since 1986...

  describes several methods to solve linear equations and estimate the uncertainty of the resulting values.

2-D Solution

Finding the emitter location in a two dimensional geometry can use any of the methods used for the 3-D geometry. The coordinate frame is typically defined to make the z dimension zero or constant. Examples of 2-D multilateration are short wave radio long distance communications through the Earth's atmosphere, acoustic wave propagation in the sound fixing and ranging channel
Sofar channel
The SOFAR channel , or deep sound channel , is a horizontal layer of water in the ocean at which depth the speed of sound is minimal. The SOFAR channel acts as a waveguide for sound, and low frequency sound waves within the channel may travel thousands of miles before dissipating...

 of the oceans and the LORAN navigation system.

Accuracy

For trilateration
Trilateration
In geometry, trilateration is the process of determinating absolute or relative locations of points by measurement of distances, using the geometry of circles, spheres or triangles. In addition to its interest as a geometric problem, trilateration does have practical applications in surveying and...

 or multilateration, calculation is done based on distances, which requires the frequency and the wave count of a received transmission. For triangulation
Triangulation
In trigonometry and geometry, triangulation is the process of determining the location of a point by measuring angles to it from known points at either end of a fixed baseline, rather than measuring distances to the point directly...

 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 angle
Angle
In geometry, an angle is the figure formed by two rays sharing a common endpoint, called the vertex of the angle.Angles are usually presumed to be in a Euclidean plane with the circle taken for standard with regard to direction. In fact, an angle is frequently viewed as a measure of an circular arc...

s 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
Trilateration
In geometry, trilateration is the process of determinating absolute or relative locations of points by measurement of distances, using the geometry of circles, spheres or triangles. In addition to its interest as a geometric problem, trilateration does have practical applications in surveying and...

, where with planar problems just three distances are known and computed. Multilateration serves for several aspects:
  • over-determination of an n-variable quadratic problem
    Quadratic equation
    In mathematics, a quadratic equation is a univariate polynomial equation of the second degree. A general quadratic equation can be written in the formax^2+bx+c=0,\,...

     with (n + 1) + m quadratic equation
    Quadratic equation
    In mathematics, a quadratic equation is a univariate polynomial equation of the second degree. A general quadratic equation can be written in the formax^2+bx+c=0,\,...

    s
  • stochastic errors prohibiting a deterministic
    Determinism
    Determinism is the general philosophical thesis that states that for everything that happens there are conditions such that, given them, nothing else could happen. There are many versions of this thesis. Each of them rests upon various alleged connections, and interdependencies of things and...

     approach to solving the equations
  • clustering needs to segregate members of various clusters contributing to various models
    Model theory
    In mathematics, model theory is the study of mathematical structures using tools from mathematical logic....

     of solving, i.e. fixed locations, oscillating
    Oscillation
    Oscillation is the repetitive variation, typically in time, of some measure about a central value or between two or more different states. Familiar examples include a swinging pendulum and AC power. The term vibration is sometimes used more narrowly to mean a mechanical oscillation but sometimes...

     locations and moving locations


Accuracy of multilateration is a function of several variables, including:
  • The antenna
    Antenna (radio)
    An antenna is an electrical device which converts electric currents into radio waves, and vice versa. It is usually used with a radio transmitter or radio receiver...

     or sensor
    Sensor
    A sensor is a device that measures a physical quantity and converts it into a signal which can be read by an observer or by an instrument. For example, a mercury-in-glass thermometer converts the measured temperature into expansion and contraction of a liquid which can be read on a calibrated...

     geometry
    Geometry
    Geometry arose as the field of knowledge dealing with spatial relationships. Geometry was one of the two fields of pre-modern mathematics, the other being the study of numbers ....

     of the receiver(s)
    Receiver (radio)
    A radio receiver converts signals from a radio antenna to a usable form. It uses electronic filters to separate a wanted radio frequency signal from all other signals, the electronic amplifier increases the level suitable for further processing, and finally recovers the desired information through...

     and transmitter(s)
    Transmitter
    In electronics and telecommunications a transmitter or radio transmitter is an electronic device which, with the aid of an antenna, produces radio waves. The transmitter itself generates a radio frequency alternating current, which is applied to the antenna. When excited by this alternating...

     for electronic
    Electronics
    Electronics is the branch of science, engineering and technology that deals with electrical circuits involving active electrical components such as vacuum tubes, transistors, diodes and integrated circuits, and associated passive interconnection technologies...

     or optical
    Optics
    Optics is the branch of physics which involves the behavior and properties of light, including its interactions with matter and the construction of instruments that use or detect it. Optics usually describes the behavior of visible, ultraviolet, and infrared light...

     transmission.
  • The timing accuracy of the receiver system, i.e. thermal stability
    Drift (telecommunication)
    In telecommunication, a drift is a comparatively long-term change in an attribute, value, or operational parameter of a system or equipment. The drift should be characterized, such as "diurnal frequency drift" and "output level drift." Drift is usually undesirable and unidirectional, but may be...

     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
    Line-of-sight propagation
    Line-of-sight propagation refers to electro-magnetic radiation or acoustic wave propagation. Electromagnetic transmission includes light emissions traveling in a straight line...

    , 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

  • Sound ranging
    Sound ranging
    In land warfare, sound ranging is a method of determining the coordinates of a hostile artillery battery using data derived from the sound of its guns firing...

     – Using sound to locate artillery fire.
  • Decca Navigator System
    Decca Navigator System
    The Decca Navigator System was a low frequency hyperbolic navigation system that was first deployed during World War II when the Allied forces needed a system which could be used to achieve accurate landings...

     – 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
    OMEGA Navigation System
    OMEGA was the first truly global radio navigation system for aircraft, operated by the United States in cooperation with six partner nations.-History:OMEGA was originally developed by the United States Navy for military aviation users...

     – 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
    Electronic warfare support measures
    In military telecommunications, the terms Electronic Support or Electronic Support Measures describe the division of electronic warfare involving actions taken under direct control of an operational commander to detect, intercept, identify, locate, record, and/or analyze sources of radiated...

     multilateration systems, including Kopáč
    Kopác passive sensor
    Kopáč was an early electronic warfare support measures system developed in Czechoslovakia in the early 1960s that used measurements of time difference of arrival of pulses at three sites to accurately detect and track airborne emitters...

    , Ramona
    Ramona passive sensor
    Ramona was the second generation Czechoslovakian electronic support measures system that uses measurements of time difference of arrival of pulses at three or four sites to accurately detect and track airborne emitters by multilateration.-History:...

    , Tamara
    Tamara passive sensor
    Tamara was the third generation Czechoslovak electronic support measures system that used measurements of time difference of arrival of pulses at three or four sites to accurately detect and track airborne emitters by multilateration. Tamara's serial numbers were KRTP-86 and KRTP-91 and it...

    , VERA
    VERA passive sensor
    VERA -VERA passive radiolocator is an electronic support measures system that uses measurements of time difference of arrival of pulses at three or four sites to accurately detect and track airborne emitters....

     and possibly Kolchuga
    Kolchuga passive sensor
    The Kolchuga passive sensor is an ESM system developed in Ukraine. Its detection range is limited by line-of-sight but may be up to for very high altitude, very powerful emitters...

     – location of a transmitter using multiple receivers
  • Mobile phone tracking
    Mobile phone tracking
    Mobile phone tracking refers to the attaining of the current position of a mobile phone, stationary or moving. Localization may occur either via multilateration of radio signals between radio towers of the network and the phone, or simply via GPS...

     – using multiple base stations to estimate phone location (by either the phone itself, or the phone network)
  • Reduced Vertical Separation Minima
    Reduced Vertical Separation Minima
    Reduced Vertical Separation Minima or Minimum is an aviation term used to describe the reduction of the standard vertical separation required between aircraft flying above FL285 and up to FL410 from 2,000 feet to 1,000 feet...

     (RVSM) monitoring using Secondary Surveillance Radar
    Secondary surveillance radar
    Secondary surveillance radar is a radar system used in air traffic control , that not only detects and measures the position of aircraft i.e. range and bearing, but also requests additional information from the aircraft itself such as its identity and altitude...

     – Mode C/S transponder replies to calculate the position of an aircraft. Application to RVSM was first demonstrated by Roke Manor Research Limited
    Roke Manor Research Limited
    Founded in 1956, Roke Manor Research Limited is a UK company based at Roke Manor in Romsey, Hampshire. It is a contract research and development business for communications, networks, and electronic sensors. In addition to supporting Chemring, work is also conducted in both the public and private...

     in 1992.

Simplification

For applications where no need for absolute coordinates determination is assessed, the implementing of a more simple solution is advantageous. Compared to multilateration as the concept of crisp locating, the other option is fuzzy locating, where just one distance delivers the relation between detector and detected object. This most simple approach is unilateration. However, such unilateration approach never delivers the angular position with reference to the detector. Many solutions are available today .
Some of these vendors offer a position estimate based on combining several laterations. This approach is often not stable, when the wireless ambience is affected by metal or water masses. Other vendors offer room discrimination with a room-wise excitation, one vendor offers a position discrimination with a contiguity excitation.

See also

  • FDOA
    FDOA
    Frequency difference of arrival , also frequently called differential Doppler , is a technique analogous to TDOA for estimating the location of a radio emitter based on observations from other points....

     Frequency difference of arrival. Analogous to TDOA using differential doppler.
  • Triangulation
    Triangulation
    In trigonometry and geometry, triangulation is the process of determining the location of a point by measuring angles to it from known points at either end of a fixed baseline, rather than measuring distances to the point directly...

     – Location by angular measurement on lines of bearing that intersect
  • Trilateration
    Trilateration
    In geometry, trilateration is the process of determinating absolute or relative locations of points by measurement of distances, using the geometry of circles, spheres or triangles. In addition to its interest as a geometric problem, trilateration does have practical applications in surveying and...

     – Location by distance (e.g. time-of-flight) measurement on coincident signals from multiple transmitters.
  • Mobile phone tracking
    Mobile phone tracking
    Mobile phone tracking refers to the attaining of the current position of a mobile phone, stationary or moving. Localization may occur either via multilateration of radio signals between radio towers of the network and the phone, or simply via GPS...

     – used in GSM networks
  • Multidimensional scaling
    Multidimensional scaling
    Multidimensional scaling is a set of related statistical techniques often used in information visualization for exploring similarities or dissimilarities in data. MDS is a special case of ordination. An MDS algorithm starts with a matrix of item–item similarities, then assigns a location to each...

  • Radiolocation
    Radiolocation
    Radiolocating is the process of finding the location of something through the use of radio waves. It generally refers to passive uses, particularly radar—as well as detecting buried cables, water mains, and other public utilities. It is similar to radionavigation, but radiolocation usually...

  • Radio navigation
    Radio navigation
    Radio navigation or radionavigation is the application of radio frequencies to determine a position on the Earth. Like radiolocation, it is a type of radiodetermination.The basic principles are measurements from/to electric beacons, especially...

  • Real-time locating – International standard for asset and staff tracking using wireless hardware and real-time software
  • Real time location system – General techniques for asset and staff tracking using wireless hardware and real-time software
The source of this article is wikipedia, the free encyclopedia.  The text of this article is licensed under the GFDL.
 
x
OK