Multilateration

Principle

Multilateration is commonly used in civil and military 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 synchronized receiver sites (surveillance application) or the signals from three or more synchronized emitters at one receiver location (navigation application).

Surveillance application: locating a transmitter from multiple receiver sites

If a pulse is emitted from a platform, it will generally 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 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 one extra independent TDOA measurement (there is a third TDOA, but this is dependent on the first two TDOA and does not provide extra information) and the emitter is located on the curve determined by the two intersecting hyperboloids. A fourth receiver is needed for another independent TDOA, this will give an extra hyperboloid, the intersection of the curve with this hyperboloid gives one or two solutions, the emitter is then located at the one or at the one of the two solutions.

With four receivers there are 3 independent TDOA, three independent parameters are needed for a point in three dimensional space. (And for most constellations, three independent TDOA will still give two points in 3D space). With additional receivers enhanced accuracy can be obtained. (Specifically for GPS the atmosphere does influence the traveling time of the signal and more satellites does give a more accurate location). For an overdetermined constellation (more than 4) a least squares can be used for 'reducing' the errors. Extended Kalman filters are used for improving the individual signal timings. Averaging over longer times, can also improve accuracy.

The accuracy also improves if the receivers are placed in a configuration that minimizes the error of the estimate of the position.

The emitting platform may, or may not, cooperate in the multilateration surveillance processes.

Navigation application: locating a receiver from multiple transmitter sites

Multilateration can also be used by a single receiver to locate itself, by measuring signals emitted from three or more synchronized transmitters at known locations. At least three emitters are needed for two-dimensional navigation; at least four emitters are needed for three-dimensional navigation. For expository purposes, the emitters may be regarded as each broadcasting pulses at exactly the same time on a separate frequencies (to avoid interference). In this situation, the receiver measures the TDOAs of the pulses, which are converted to range differences.

However, operational systems are more complex. These methods have been implemented: (a) pulses are broadcast by different emitters on the same frequency, with known delays between transmission times; (b) continuous signals are broadcast on different frequencies, and their measured phase differences are converted to range differences; and (c) continuous signals are broadcast on the same carrier frequency, but each emitter modulates the carrier with a unique, known code. Correlation processing is used to obtain TDOAs.

The multilateration technique is used by several navigation systems. A historic example is the British DECCA system, developed during World War II. Decca used the phase-difference of three transmitters (method (b)). LORAN-C, introduced in the late 1950s, uses method (a). A current example is the Global Positioning System, or GPS. All GPS satellites broadcast on the same carrier frequency, which is modulated by pseudorandom codes (method (c)).

Rectangular/Cartesian coordinates

Consider an emitter (E in Figure 2) at an unknown location vector

which we wish to locate. The source is within range of N+1 receivers at known locations

The subscript m refers to any one of the receivers:

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

For some solution algorithms, the math is made easier by placing the origin at one of the receivers (P₀), which makes its distance to the emitter

Spherical coordinates

Low-frequency radio waves follow the curvature of the earth rather than a straight line. In this situation, equation 1 is not valid. LORAN-C and Omega are primary examples of systems that utilize spherical (vice slant) ranges. When a spherical model for the earth is satisfactory, the simplest expression for the central angle (sometimes termed the geocentric angle) between vehicle v and station m is

Here: latitudes are denoted by φ; longitudes are denoted by λ; and λ_vm = λ_v − λ_m. Alternative, better numerically behaved equivalent expressions, can be found in Great-circle navigation.

The distance R_m from the vehicle to station m is along a great circle will then be

Here R_E is the assumed radius of the earth and σ_vm is expressed in radians.

Measuring the time difference in a TDOA system

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

Figure 3a is a simulation of a pulse waveform recorded by receivers P 0 and P 1 . The spacing between E , P 1 and P 0 is such that the pulse takes 5 time units longer to reach P 1 than P 0 . The units of time in Figure 3 are arbitrary. The following table gives approximate time scale units for recording different types of waves.

The red curve in Figure 3a is the cross-correlation function ( P 1 ⋆ P 0 ) . 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 3.

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 τ 1 = 5 .

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 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, 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, which will be an uncertainty that propagates into the calculated location. If the phase noise is large enough, the phase detector can become unstable.

Overview

Equation 3 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 transponder return to find the altitude. Three or more receivers at known locations are used to find the other two dimensions—either (x,y) for an airport application, or latitude and longitude for larger areas.

S. Bancroft first published the algebraic solution to the problem of locating a receiver using TDOA measurements involving 4 transmitters. Bancroft's algorithm reduces the problem to the solution of a quadratic equation, and yields the three Cartesian coordinates of the receiver as well as the common time of signal transmission. Other, comparable solutions and extensions were subsequently developed. The latter reference provides the solution for locating an aircraft with known altitude using TDOA measurements at 3 receivers.

When there are more measurements equations than unknown quantities (over-determined situation), the iterative Gauss-Newton algorithm for solving Non-linear least squares(NLLS) problems is generally preferred. An over-determined situation eliminates the possibility of ambiguous and/or extraneous solutions that can occur when only the minimum required number of measurements are available. The Gauss-Newton method may also be used with the minimum number of measurements — e.g., when an ellipsoidal model for earth must be employed. Since it is iterative, the Gauss-Newton method requires an initial solution estimate (which can be generated using a spherical earth model).

Multilateration systems employing spherical-range measurements utilize a combination of solution algorithms based on spherical trigonometry and the Gauss-Newton NLLS method.

Solution with limited computational resources

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 (1, 2 & 3). The TDOA problem can be turned into a system of linear equations when there are 3 or more receivers, which can reduce the computation time. Starting with equation 3, solve for R_m, square both sides, collect terms and divide all terms by v τ m :

Removing the 2 R₀ 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 1. Square R_m, group similar terms and use equation 2 to replace some of the terms with R₀.

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

Use equation 7 to generate the four constants A m , B m , C m , D m from measured distances and time for each receiver 2 ≤ m ≤ N. This will be a set of N-1 inhomogeneous linear equations.

There are many robust linear algebra methods that can solve for the values of (x,y,z), such as Gaussian Elimination. Chapter 15 in Numerical Recipes describes several methods to solve linear equations and estimate the uncertainty of the resulting values.

Two-dimensional solution

For finding the emitter location in a two dimensional geometry, one can generally adapt the methods used for the 3-D geometry. Additionally, there are specialized algorithms for two-dimensions—notable are the methods published by Fang (for a Cartesian plane) and Razin (for spherical earth).

When necessitated by the combination of vehicle-station distance (e.g., hundreds of miles or more) and required solution accuracy (e.g., less that 0.3% of the vehicle-stations distance), the ellipsoidal shape of the earth must be considered. This has been accomplished using the Gauss-Newton LLS method in conjunction with ellipsoid algorithms by Andoyer, Vincenty and Sodano.

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 of the oceans and the LORAN navigation system.

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:

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

The accuracy can be calculated by using the Cramér–Rao bound and taking account of the above factors in its formulation. Additionally, a configuration of the sensors that minimizes a metric obtained from the Cramér–Rao bound can be chosen so as to optimize the actual position estimation of the target in a region of interest.

Example applications

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.