View source for Pseudo-range multilateration

{{short description|Navigation and surveillance technique}}

'''Pseudo-range multilateration''', often simply '''multilateration''' ('''MLAT''') when in context, is a technique for [[Earth:Geopositioning|determining the position]] of an unknown point, such as a vehicle, based on measurement of the ''[[Earth:Time of arrival|times of arrival]]'' (TOAs) of energy waves traveling between the unknown point and multiple stations at known locations. When the waves are transmitted by the vehicle, MLAT is used for surveillance; when the waves are transmitted by the stations, MLAT is used for [[Earth:Navigation|navigation]] (''[[Engineering:Hyperbolic navigation|hyperbolic navigation]]''). In either case, the stations' clocks are assumed synchronized but the vehicle's clock is not.

Prior to computing a solution, the common ''time of transmission'' (TOT) of the waves is unknown to the receiver(s), either on the vehicle (one receiver, navigation) or at the stations (multiple receivers, surveillance). Consequently, also unknown is the wave ''[[Physics:Time of flight|times of flight]]'' (TOFs){{snd}} the ranges of the vehicle from the stations divided by the wave propagation speed. Each ''pseudo-range'' is the corresponding TOA multiplied by the propagation speed with the same arbitrary constant added (representing the unknown TOT).

In navigation applications, the vehicle is often termed the "user"; in surveillance applications, the vehicle may be termed the "target". For a mathematically exact solution, the ranges must not change during the period the signals are received (between first and last to arrive at a receiver). Thus, for navigation, an exact solution requires a stationary vehicle; however, multilateration is often applied to the navigation of moving vehicles whose speed is much less than the wave propagation speed.

If <math>d</math> is the number of physical dimensions being considered (thus, vehicle coordinates sought) and <math>m</math> is the number of signals received (thus, TOAs measured), it is required that <math>m \ge d + 1</math>. Then, the fundamental set of <math>m</math> measurement equations is:

: TOAs (<math>m</math> measurements) = TOFs (<math>d</math> unknown variables embedded in <math>m</math> expressions) + TOT (one unknown variable replicated <math>m</math> times).

Processing is usually required to extract the TOAs or their differences from the received signals, and an [[Algorithm|algorithm]] is usually required to solve this set of equations. An algorithm either: (a) determines numerical values for the TOT (for the receiver(s) clock) and <math>d</math> vehicle coordinates; or (b) ignores the TOT and forms <math>m - 1</math> (at least <math>d</math>) time difference of arrivals (TDOAs), which are used to find the <math>d</math> vehicle coordinates. Almost always, <math>d = 2</math> (e.g., a plane or the surface of a sphere) or <math>d = 3</math> (e.g., the real physical world). Systems that form TDOAs are also called ''hyperbolic'' systems,<ref name="Proc">{{cite web |url=http://www.jproc.ca/hyperbolic/ |title=Hyperbolic Radionavigation Systems |last=Proc |first=Jerry |date=2021 |access-date=April 11, 2022 }}</ref> for reasons discussed below.

A multilateration ''[[Earth:Navigation|navigation]]'' system provides vehicle position information to an entity "on" the vehicle (e.g., aircraft pilot or GPS receiver operator). A multilateration ''surveillance'' system provides vehicle position to an entity "not on" the vehicle (e.g., air traffic controller or cell phone provider). By the reciprocity principle, any method that can be used for navigation can also be used for surveillance, and vice versa (the same information is involved).

Systems have been developed for both TOT and TDOA (which ignore TOT) algorithms. In this article, TDOA algorithms are addressed first, as they were implemented first. Due to the technology available at the time, TDOA systems often determined a vehicle location in two dimensions. TOT systems are addressed second. They were implemented, roughly, post-1975 and usually involve satellites. Due to technology advances, TOT algorithms generally determine a user/vehicle location in three dimensions. However, conceptually, TDOA or TOT algorithms are not linked to the number of dimensions involved.

== Background ==

===Multilateration definition===
Prior to deployment of GPS and other global [[Earth:Satellite navigation|navigation satellite]] systems (GNSSs), pseudo-range multilateration systems were often defined as (synonymous with) TDOA systems{{snd}} i.e., systems that measured TDOAs or formed TDOAs as the first step in processing a set of measured TOAs. However, as result of deployment of GNSSs (which must determine TOT), two issues arose: (a) What system type are GNSSs (pseudo-range multilateration, true-range multilateration, or another system type)? (b) What are the defining characteristic(s) of a pseudo-range multilateration system? (There are no deployed multilateration surveillance systems that determine TOT, but they have been analyzed.<ref name="Lee1" />) 
* The technical answer to (a) has long been known: GNSSs are a variety (or sub-species) of multilateration navigation systems having moving transmitters.<ref name="Abel1" /><ref name="Fang2" /> However, because the transmitters are synchronized not only with each other but also with a time standard, GNSS receivers are also sources of timing information. This requires different solution algorithms than TDOA systems. Thus, a case can also be made that GNSSs are a separate category of systems. 
* There is no authoritative answer to (b). However, a reasonable two-part answer is (1) ''a system whose only measurements are TDOAs or TOAs'' (or, if the propagation speed is accounted for, ''only measures pseudo-ranges''); and (2) ''a system whose station clocks must be synchronized''. (Note: wave propagation is required by this definition.) This definition is used here, and includes GNSSs as well as TDOA systems. TDOA systems are explicitly hyperbolic while TOA systems are implicitly hyperbolic.

===Applications overview===
Pseudo-range multilateration systems have been developed for waves that follow straight-line and curved earth trajectories and virtually every wave phenomena—electromagnetic (various frequencies and waveforms), acoustic (audible or ultrasound, in water or air), seismic, etc. The multilateration technique was apparently first used during World War&nbsp;I to locate the source of artillery fire using audible sound waves (TDOA surveillance). Multilateration surveillance is related to passive [[Towed array sonar|towed array sonar]] target localization (but not identification), which was also first used during World War&nbsp;I.

Longer distance radio-based [[Engineering:Hyperbolic navigation|navigation]] systems became viable during World War&nbsp;II, with the advancement of radio technologies. For about 1950–2000, TDOA multilateration was a common technique in Earth-fixed [[Radio navigation|radio navigation]] systems, where it was known as [[Engineering:Hyperbolic navigation|hyperbolic navigation]]. These systems are relatively undemanding of the user receiver, as its "clock" can have low performance/cost and is usually unsynchronized with station time.<ref name="Misra">"The Role of the Clock in a GPS Receiver", Pratap N. Misra, ''GPS World'', April 1996.</ref> The difference in received signal timing can even be measured visibly using an [[Engineering:Oscilloscope|oscilloscope]]. The introduction of the [[Engineering:Microprocessor|microprocessor]] greatly simplified operation, increasing popularity during the 1980s. The most popular TDOA hyperbolic navigation system was [[Engineering:Loran-C|Loran-C]], which was used around the world until the system was largely shut down.

The development of [[Engineering:Atomic clock|atomic clock]]s for synchronizing widely separated stations was instrumental in the development of the GPS and other GNSSs. The widespread use of [[Earth:Satellite navigation|satellite navigation]] systems like the [[Engineering:Global Positioning System|Global Positioning System]] (GPS) have made Earth-fixed TDOA navigation systems largely redundant, and most have been decommissioned. Owing to its high accuracy at low cost of user equipage, today multilateration is the concept most often selected for new navigation and surveillance systems—e.g., surveillance of flying (alternative to radar) and taxiing (alternative to visual) aircraft.<ref name="James">{{cite web |title=Multilateration: Radar's Replacement? |last1=James |first1=Callan |date=2007 |publisher=Aviation Today |url=https://www.aviationtoday.com/2007/04/01/multilateration-radars-replacement/#:~:text=MLat%20and%20ADS%2DB,-MLat%20and%20ADS&text=But%20MLat%20determines%20an%20aircraft's,the%20aircraft's%20ADS%2DB%20message. | access-date=April 10, 2022 }}</ref><ref name="FAA1">{{cite web |title=Wide Area Multilateration (WAM) |date=2021 |publisher=Federal Aviation Administration |url=https://www.faa.gov/nextgen/programs/adsb/atc/wam/ | access-date=April 10, 2022 }}</ref><ref name="ERA">{{cite web |title=The Multilateration Executive Reference Guide |url=http://www.multilateration.com |publisher=ERA |access-date=April 12, 2022 }}</ref>

Multilateration is commonly used in civil and military applications to either (a) locate a vehicle (aircraft, ship, car/truck/bus or wireless phone carrier) by measuring the TOAs of a signal from the vehicle at multiple stations having known coordinates and synchronized "clocks" (surveillance application) or (b) enable the vehicle to locate itself relative to multiple transmitters (stations) at known locations and having synchronized clocks based on measurements of signal TOAs (navigation application). When the stations are fixed to the earth and do not provide time, the measured TOAs are almost always used to form one fewer TDOAs.

For vehicles, surveillance or navigation stations (including required associated infrastructure) are often provided by government agencies. However, privately funded entities have also been (and are) station/system providers{{snd}} e.g., wireless phone providers.<ref name="Gustafsson">"Mobile positioning using wireless networks: possibilities and fundamental limitations based on available wireless network measurements", &nbsp;Gustafsson and F.&nbsp;Gunnarsson, ''IEEE Signal Processing Magazine'', vol.&nbsp;22, no.&nbsp;4, pp.&nbsp;41–53, July 2005.</ref> Multilateration is also used by the scientific and military communities for non-cooperative surveillance.

===Advantages and disadvantages===
The following table summarizes the advantages and disadvantages of pseudo-range multilateration, particularly relative to [[True-range multilateration|true-range]] measurements.

{| class="wikitable" style="text-align:left;
|-
! Advantages
! Disadvantages
|- 
||
* Low user equipage complexity/cost{{snd}} A cooperative surveillance user only needs a transmitter. A navigation user only needs a receiver having a basic "clock".
* Accuracy – Avoids the "turn-around" error inherent in many two-way ranging systems.
* Small stations – Avoids use of the large antennas needed for measuring angles.
* For navigation, the number of users is unlimited (users only receive).
* Uncooperative and undetected surveillance are possible.
* Uses one-way ranging which is viable over great distances (waves attenuate only as the square of range).
* Implementations have utilized several wave propagation phenomena: electromagnetic (radio), air acoustics, water acoustics, and seismic.
||
* Complexity{{snd}} The unknown TOT introduces analytic and physical complexity.
* Station locations{{snd}} To determine the vehicle location with accuracy comparable to the measurements, stations must nearly surround the service area.
* Station count{{snd}} Finding <math>d + 1</math> unknowns requires at least one more station than a system based on true ranges (<math>d</math> unknowns) and at least two more stations than a system that measures range and azimuth.
* Station synchronization (and, for surveillance, inter-station communications) are required.
* Stations may require power and communications where not readily available.
* For surveillance, users may mutually interfere (multiple users may require pulsed transmissions).
* For navigation, stations must transmit effectively simultaneously but not mutually interfere.
* Service only provided in defined region.
|}

The advantages of systems employing pseudo-ranges largely benefit the vehicle/user/target. The disadvantages largely burden the system provider.

== Principle ==

=== Frequencies and waveforms ===
Pseudo-range multilateration ''navigation'' systems have been developed utilizing a variety of radio frequencies and waveforms — low-frequency pulses (e.g., Loran-C); low-frequency continuous sinusoids (e.g., Decca); high-frequency continuous wide-band (e.g., GPS). Pseudo-range multilateration ''surveillance'' systems often use existing pulsed transmitters (if suitable) — e.g., Shot-Spotter, ASDE-X and WAM.

=== Coordinate frame ===
Virtually always, the coordinate frame is selected based on the wave trajectories. Thus, two- or three-dimensional Cartesian frames are selected most often, based on straight-line (line-of-sight) wave propagation. However, [[Polar coordinate system|polar]] (also termed circular/spherical) frames are sometimes used, to agree with curved earth-surface wave propagation paths. Given the frame type, the origin and axes orientation can be selected, e.g., based on the station locations. Standard coordinate frame transformations may be used to place results in any desired frame. For example, GPS receivers generally compute their position using rectangular coordinates, then transform the result to latitude, longitude and altitude.

=== TDOA formation ===
Given <math>m</math> received signals, TDOA systems form <math>m-1</math> differences of TOA pairs (see "Calculating TDOAs or TOAs from received signals" below). All received signals must be a member of at least one TDOA pair, but otherwise the differences used are arbitrary (any two of the several sets of TDOAs can be related by an invertible linear transformation). Thus, when forming a TDOA, the order of the two TOAs involved is not important.

Some operational TDOA systems (e.g., Loran-C) designate one station as the "master" and form their TDOAs as the difference of the master's TOA and the <math>m-1</math> "secondary" stations' TOAs. When <math>m=3</math>, there are <math>3</math> possible TDOA combinations, each corresponding to a station being the de facto master. When <math>m=4</math>, there are <math>16</math> possible TDOA sets, <math>12</math> of which do not have a de facto master. When <math>m=5</math>, there are <math>135</math> possible TDOA sets, <math>130</math> of which do not have a de facto master.

=== TDOA principle / surveillance ===
If a pulse is emitted from a vehicle, it will generally arrive at slightly different times at spatially separated receiver sites, the different TOAs being due to the different distances of each receiver from the vehicle. However, for given locations of any two receivers, a set of emitter locations would give the same time difference (TDOA). Given two receiver locations and a known TDOA, the [[Locus (mathematics)|locus]] of possible emitter locations is one half of a two-sheeted hyperboloid.

[[File:HyperboloidOfTwoSheets.svg|thumb|Fig 1. A two-sheeted hyperboloid]]

In simple terms, with two receivers at known locations, an emitter can be located onto one hyperboloid (see Figure&nbsp;1).<ref>In other words, when performing surveillance, given two receivers at known locations, one can derive a three-dimensional surface (characterized as one sheet of a hyperboloid of revolution) for which all 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 at the receivers as a signal transmitted from any other point on the surface. <br />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 that surface.</ref> Note that the receivers do not need to know the absolute time at which the pulse was transmitted{{snd}} only the time difference is needed. However, to form a useful TDOA from two measured TOAs, the receiver clocks must be synchronized with each other.

Consider now a third receiver at a third location which also has a synchronized clock. This would provide a third independent TOA measurement and a second TDOA (there is a third TDOA, but this is dependent on the first two TDOAs and does not provide additional information). The emitter is located on the curve determined by the two intersecting hyperboloids. A fourth receiver is needed for another independent TOA and TDOA. This will give an additional hyperboloid, the intersection of the curve with this hyperboloid gives one or two solutions, the emitter is then located at one of the two solutions.

With four synchronized receivers there are 3 independent TDOAs, and three independent parameters are needed for a point in three dimensional space. (And for most constellations, three independent TDOAs will still give two points in 3D space).
With additional receivers enhanced accuracy can be obtained. (Specifically, for GPS and other GNSSs, the atmosphere does influence the traveling time of the signal and more satellites does give a more accurate location).
For an over-determined constellation (more than 4 satellites/TOAs) a [[Least squares|least squares]] method can be used for 'reducing' the errors. 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.<ref name="Domingo-Perez">{{cite journal |last1=Domingo-Perez |first1=Francisco |last2=Lazaro-Galilea |first2=Jose Luis |last3=Wieser |first3=Andreas |last4=Martin-Gorostiza |first4=Ernesto |last5=Salido-Monzu |first5=David |last6=Llana |first6=Alvaro de la |title=Sensor placement determination for range-difference positioning using evolutionary multi-objective optimization |journal=Expert Systems with Applications |date=April 2016 |volume=47 |pages=95–105 |doi=10.1016/j.eswa.2015.11.008}}</ref>

The emitter may, or may not, cooperate in the multilateration surveillance process. Thus, multilateration surveillance is used with non-cooperating "users" for military and scientific purposes as well as with cooperating users (e.g., in civil transportation).

=== TDOA principle / navigation ===
Multilateration can also be used by a single receiver to locate itself, by measuring signals emitted from synchronized transmitters at known locations (stations). At least three emitters are needed for two-dimensional navigation (e.g., the Earth's surface); at least four emitters are needed for three-dimensional navigation. Although not true for real systems, for expository purposes, the emitters may be regarded as each broadcasting narrow pulses (ideally, impulses) at exactly the same time on separate frequencies (to avoid interference). In this situation, the receiver measures the TOAs of the pulses. In actual TDOA systems, the received signals are cross-correlated with an undelayed replica to extract the pseudo delay, then differenced with the same calculation for another station and multiplied by the speed of propagation to create range differences.

Several methods have been implemented to avoid self-interference. A historic example is the British [[Engineering:Decca Navigator System|Decca]] system, developed during World War&nbsp;II. Decca used the [[Physics:Phase (waves)|phase]]-difference of three transmitters. Later, Omega elaborated on this principle. For [[Engineering:Loran-C|Loran-C]], introduced in the late 1950s, all transmitters broadcast pulses on the same frequency with different, small time delays. GNSSs continuously transmitting on the same carrier frequency modulated by different pseudo random codes (GPS, Galileo, revised GLONASS).

=== TOT principle ===

[[File:MLAT TOT 2D Algorithm.svg|thumb|Fig. 2. Multilateration surveillance system TOT algorithm concept]]

The TOT concept is illustrated in Figure&nbsp;2 for the surveillance function and a planar scenario (<math>d = 2</math>). Aircraft&nbsp;A, at coordinates <math>(x_A, y_A)</math>, broadcasts a pulse sequence at time <math>t_A</math>. The broadcast is received at stations <math>S_1</math>, <math>S_2</math> and <math>S_3</math> at times <math>t_1</math>, <math>t_2</math> and <math>t_3</math> respectively. Based on the three measured TOAs, the processing algorithm computes an estimate of the TOT <math>t_A</math>, from which the range between the aircraft and the stations can be calculated. The aircraft coordinates <math>(x_A, y_A)</math> are then found.

When the algorithm computes the correct TOT, the three computed ranges have a common point of intersection which is the aircraft location (the solid-line circles in Figure&nbsp;2). If the computed TOT is after the actual TOT, the computed ranges do not have a common point of intersection (dashed-line circles in Figure&nbsp;2). It is clear that an iterative TOT algorithm can be found. In fact, GPS was developed using iterative TOT algorithms. Closed-form TOT algorithms were developed later.

TOT algorithms became important with the development of GPS. [[Astronomy:GLONASS|GLONASS]] and Galileo employ similar concepts. The primary complicating factor for all GNSSs is that the stations (transmitters on satellites) move continuously relative to the Earth. Thus, in order to compute its own position, a user's navigation receiver must know the satellites' locations at the time the information is broadcast in the receiver's time scale (which is used to measure the TOAs). To accomplish this: (1) satellite trajectories and TOTs in the satellites' time scales are included in broadcast messages; and (2) user receivers find the difference between their TOT and the satellite broadcast TOT (termed the clock bias or offset). GPS satellite clocks are synchronized to [[UTC]] (to within a published offset of a few seconds), as well as with each other. This enables GPS receivers to provide UTC time in addition to their position.

==Measurement geometry and related factors==

===Rectangular/Cartesian coordinates===

[[Image:TDOA Geometry.png|thumb|350px|alt=Geometry of spherical waves emanating from an emitter and passing through several receivers.|Fig. 3. Surveillance system TDOA geometry]]

Consider an emitter (E in Figure 3) at an unknown location vector
: <math>\vec E = (x, y, z),</math>
which we wish to locate (surveillance problem). The source is within range of <math>m = n+1</math> receivers at known locations
: <math>\vec P_0, \vec P_1, \ldots, \vec P_i, \ldots, \vec P_n.</math>
The subscript <math>i</math> refers to any one of the receivers:
: <math>\vec P_i = (x_i, y_i, z_i),</math>
: <math>0 \le i \le n.</math>

The distance (<math>R_i</math>) from the emitter to one of the receivers in terms of the coordinates is
{{NumBlk|:|
<math> 
R_i = \left| \vec P_i - \vec E \right| = \sqrt{(x_i - x)^2 + (y_i - y)^2 + (z_i - z)^2}.
</math>
|{{EquationRef|1}}}}

For some solution algorithms, the math is made easier by placing the origin at one of the receivers (''P''<sub>0</sub>), which makes its distance to the emitter
{{NumBlk|:|
<math>
R_0 = \sqrt{(0 - x)^2 + (0 - y)^2 + (0 - z)^2} = \sqrt{x^2 + y^2 + z^2}.
</math>
|{{EquationRef|2}}}}

===Spherical coordinates===
Low-frequency radio waves follow the curvature of the Earth (great-circle paths) rather than straight lines. In this situation, equation {{EquationNote|1}} is not valid. Loran-C<ref name="Hefley">''The Development of Loran-C Navigation and Timing'', Gifford Hefley, U.S. National Bureau of Standards, Oct. 1972.</ref> and Omega<ref name="Morris">''Omega Navigation System Course Book'', Peter B. Morris ''et al'', TASC, July 1994.</ref> are examples of systems that use spherical ranges. When a spherical model for the Earth is satisfactory, the simplest expression for the [[Central angle|central angle]] (sometimes termed the ''geocentric angle'') <math>\theta_{vi}</math> between vehicle <math>v</math> and station {{mvar|i}} is
: <math>
 \cos\theta_{vi} = \sin\varphi_v \sin\varphi_i + \cos\varphi_v \cos\varphi_i \cos(\lambda_v - \lambda_i),
</math>
where latitudes are denoted by <math>\varphi</math>, and longitudes are denoted by <math>\lambda</math>. Alternative, better numerically behaved equivalent expressions can be found in [[Great-circle navigation|great-circle navigation]].

The distance <math>R_i</math> from the vehicle to station {{mvar|i}} is along a great circle will then be
: <math>
 R_i = R_E \, \theta_{vi},
</math>
where <math>R_E</math> is the assumed [[Astronomy:Earth radius|radius of the Earth]], and <math>\theta_{vi}</math> is expressed in radians.

===Time of transmission (user clock offset or bias)===

Prior to GNSSs, there was little value to determining the TOT (as known to the receiver) or its equivalent in the navigation context, the offset between the receiver and transmitter clocks. Moreover, when those systems were developed, computing resources were quite limited. Consequently, in those systems (e.g., Loran-C, Omega, Decca), receivers treated the TOT as a nuisance parameter and eliminated it by forming TDOA differences (hence were termed TDOA or range-difference systems). This simplified solution algorithms. Even if the TOT (in receiver time) was needed (e.g., to calculate vehicle velocity), TOT could be found from one TOA, the location of the associated station, and the computed vehicle location.

With the advent of GPS and subsequently other satellite navigation systems: (1) TOT as known to the user receiver provides necessary and useful information; and (2) computing power had increased significantly. GPS satellite clocks are synchronized not only with each other but also with [[Physics:Coordinated Universal Time|Coordinated Universal Time]] (UTC) (with a published offset) and their locations are known relative to UTC. Thus, algorithms used for satellite navigation solve for the receiver position and its clock offset (equivalent to TOT) simultaneously. The receiver clock is then adjusted so its TOT matches the satellite TOT (which is known by the GPS message). By finding the clock offset, GNSS receivers are a source of time as well as position information. Computing the TOT is a practical difference between GNSSs and earlier TDOA multilateration systems, but is not a fundamental difference. To first order, the user position estimation errors are identical.<ref name=Geyer />

===TOA adjustments===

Multilateration system governing equations{{snd}} which are based on "distance" equals "propagation speed" times "time of flight"{{snd}} assume that the energy wave propagation speed is constant and equal along all signal paths. This is equivalent to assuming that the propagation medium is homogeneous. However, that is not always sufficiently accurate; some paths may involve additional propagation delays due to inhomogeneities in the medium. Accordingly, to improve solution accuracy, some systems adjust  measured TOAs to account for such propagation delays. Thus, space-based [[Engineering:GNSS augmentation|GNSS augmentation]] systems{{snd}} e.g., [[Engineering:Wide Area Augmentation System|Wide Area Augmentation System]] (WAAS) and [[Engineering:European Geostationary Navigation Overlay Service|European Geostationary Navigation Overlay Service]] (EGNOS){{snd}} provide TOA adjustments in real time to account for the ionosphere. Similarly, U.S. Government agencies used to provide adjustments to Loran-C measurements to account for soil conductivity variations.

== Calculating TDOAs or TOAs from received signals ==

{{multiple image
 | width     = 350
 | direction = vertical
 | footer    = Examples of measuring time difference with cross-correlation (surveillance system)
 | image1    = CrossCorr_Pulse.png
 | caption1  = Fig. 4a. Pulse signal
 | image2    = CrossCorr_Wideband.png
 | caption2  = Fig. 4b. Wide-band signal
 | image3    = CrossCorr_Narrowband.png
 | caption3  = Fig. 4c. Narrow-band signal
}}

Assume a surveillance system calculates the time differences (<math>\tau_i</math> for <math>i=1,2,...,m-1</math>) of wavefronts touching each receiver. The TDOA equation for receivers <math>i</math> and <math>0</math> is (where the wave propagation speed is <math>c</math> and the true vehicle-receiver ranges are <math>R_0</math> and <math>R_i</math>)
{{NumBlk|:|
<math>\begin{align}
 c \, \tau_i  &= c \, T_i - c \, T_0, \\
 c \, \tau_i  &= R_i - R_0.
\end{align}</math>
|{{EquationRef|3}}}}

The quantity <math>c \, T_i</math> is often termed a pseudo-range. It differs from the true range between the vehicle and station <math>i</math> by an offset, or bias, which is the same for every signal. Differencing two pseudo-ranges yields the difference of the same two true-ranges.

Figure 4a (first two plots) show a simulation of a pulse waveform recorded by receivers <math>P_0</math> and <math>P_1</math>. The spacing between <math>E</math>, <math>P_1</math> and <math>P_0</math> is such that the pulse takes 5 time units longer to reach <math>P_1</math> than <math>P_0</math>. The units of time in Figure&nbsp;4 are arbitrary. The following table gives approximate time scale units for recording different types of waves:

{| class="wikitable" style="text-align:left;
|-
! Type of wave
! Material
! Time units
|- 
| Acoustic
| Air
| 1 millisecond
|-
| Acoustic
| Water
| 1/2 millisecond
|-
| Acoustic
| Rock
| 1/10 millisecond
|-
| Electromagnetic
| Vacuum, air
| 1 nanosecond
|}

The red curve in Figure 4a (third plot) is the [[Cross-correlation|cross-correlation]] function <math>(P_1 \star P_0)</math>. 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 <math>\tau</math> value needed for equation&nbsp;{{EquationNote|3}}.

Figure 4b shows 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&nbsp;4a example. Again, the peak in the cross-correlation occurs at <math>\tau_1 = 5</math>.

Figure 4c 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 [[Engineering:Loran-C|LORAN C]] and [[Engineering:Decca Navigator System|Decca]] mentioned at earlier (recall the same math works for moving receiver and multiple known transmitters), use spacing larger than 1 wavelength and include equipment, such as a [[Engineering:Phase detector|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 <math>\theta</math>, frequency <math>f</math> and time <math>T</math>:
: <math>\theta = 2 \pi f \cdot T.</math>
The phase detector will see variations in frequency as measured [[Phase noise|phase noise]], which will be an [[Propagation of uncertainty|uncertainty that propagates]] into the calculated location. If the phase noise is large enough, the phase detector can become unstable.

Navigation systems employ similar, but slightly more complex, methods than surveillance systems to obtain delay differences. The major change is DTOA navigation systems cross-correlate each received signal with a stored replica of the transmitted signal (rather than another received signal). The result yields the received signal time delay plus the user clock's bias (pseudo-range scaled by <math>1/c</math>). Differencing the results of two such calculations yields the delay difference sought (<math>\tau_i</math> in equation&nbsp;{{EquationNote|3}}).

TOT navigation systems perform similar calculations as TDOA navigation systems. However, the final step, subtracting the results of one cross-correlation from another, is not performed. Thus, the result is <math>m</math> received signal time delays plus the user clock's bias (<math>T_i</math> in equation&nbsp;{{EquationNote|3}}).

==Solution algorithms==

===General algorithm behavior===
Generally, using a direct (non-iterative) algorithm, <math>m = d + 1</math> measurement equations can be reduced to a single scalar nonlinear "solution equation" having one unknown variable (somewhat analogous to [[Gaussian elimination|Gauss–Jordan elimination]] for linear equations) {{snd}} e.g., a quadratic polynomial in one vehicle Cartesian coordinate.<ref name="Fang" /> The vehicle position and TOT then readily follow in sequence. When <math>m = d + 1</math>, the measurement equations generally have two solution sets (but sometimes four), only one of which is "correct" (yields the true TOT and vehicle position in the absence of measurement errors). The "incorrect" solution(s) to the solution equation do not correspond to the vehicle position and TOT and are either ambiguous (yield other vehicle positions which have the same measurements) or [[Extraneous and missing solutions|extraneous]] (do not provide vehicle positions which have the same measurements, but are the result of mathematical manipulations).

Without redundant measurements (i.e., <math>m = d + 1</math>), all valid algorithms yield the same "correct" solution set (but perhaps one or more different sets of "incorrect" solutions). Of course, statistically larger measurement errors result in statistically larger errors in the correct computed vehicle coordinates and TOT. With redundant measurements (i.e., <math>m > d + 1</math>), a [[Loss function|loss function]] or cost function (also called an error function) is minimized (a quadratic loss function is common). With redundant measurements in the absence of measurement errors, the measurement equations usually have a unique solution. If measurement errors are present, different algorithms yield different "correct" solutions; some are statistically better than others.

===Algorithm selection considerations===
There are multiple categories of multilateration algorithms, and some categories have multiple members. Perhaps the first factor that governs algorithm selection: Is an initial estimate of the user's position required (as do [[Iterative method|iterative algorithms]]) or is it not? Direct (closed-form) algorithms estimate the user's position using only the measured TOAs and do not require an initial position estimate. A related factor governing algorithm selection: Is the algorithm readily automated, or conversely, is human interaction needed/expected? Most direct (closed form) algorithms have multiple  solutions, which is detrimental to their automation. A third factor is: Does the algorithm function well with both the minimum number (<math>d+1</math>) TOA measurements and with additional (redundant) measurements?

Direct algorithms can be further categorized based on energy wave propagation path—either straight-line or curved. The latter is applicable to low-frequency radio waves, which follow the earth's surface; the former applies to higher frequency (say, greater than one megahertz) and to shorter ranges (hundreds of miles).

This taxonomy has five categories: four for direct algorithms and one for iterative algorithms (which can be used with either <math>d+1</math> or more measurements and either propagation path type). However, it appears that algorithms in only three of these categories have been implemented. When redundant measurements are available for either wave propagation path, iterative algorithms have been strongly favored over closed-form algorithms.<ref name="Sirola" /> Often, real-time systems employ iterative algorithms while off-line studies utilize closed-form algorithms.

All multilateration algorithms assume that the station locations are known at the time each wave is transmitted. For TDOA systems, the stations are fixed to the earth and their locations are surveyed. For TOA systems, the satellites follow well-defined orbits and broadcast orbital information. (For navigation, the user receiver's clock must be synchronized with the transmitter clocks; this requires that the TOT be found.) Equation {{EquationNote|3}} is the hyperboloid described in the previous section, where 4 receivers (0 ≤ m ≤ 3) lead to 3 non-linear equations in 3 unknown Cartesian coordinates (x,y,z). The system must then solve for the unknown user (often, vehicle) location in real time. (A variation: air traffic control multilateration systems use the Mode C [[Physics:Secondary surveillance radar|SSR]] transponder message to find an aircraft's 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/longitude for off-airport applications.)

Steven Bancroft was apparently the first to publish a closed-form solution to the problem of locating a user (e.g., vehicle) in three dimensions and the common TOT using four or more TOA measurements.<ref name="Bancroft">[https://ieeexplore.ieee.org/document/4104017 "An Algebraic Solution of the GPS Equations"], Stephen Bancroft, ''IEEE Transactions on Aerospace and Electronic Systems'', Volume: AES-21, Issue: 7 (Jan. 1985), pp 56–59.</ref> Bancroft's algorithm, as do many, reduces the problem to the solution of a quadratic algebraic equation; its solution yields the three Cartesian coordinates of the receiver as well as the common signal TOT. Other, comparable solutions were subsequently developed.<ref name="Fang3">"Trilateration and extension to global positioning system navigation", B.T. Fang, ''Journal of Guidance, Control, and Dynamics'', vol. 9 (1986), pp 715–717.</ref><ref name="Krause">“A direct solution to GPS-type navigation equations”, L.O. Krause, ''IEEE Transactions on Aerospace and Electronic Systems'', AES-23, 2 (1987), pp 225–232.</ref><ref name="Kleusberg">Analytical GPS Navigation Solution, Alfred Kleusberg, ''University of Stuttgart Research Compendium'', 1994.</ref><ref name="Bucher Misra">{{cite journal |last1=Bucher |first1=Ralph |last2=Misra |first2=D. |date=2002 |title=A Synthesizable VHDL Model of the Exact Solution for Three-dimensional Hyperbolic Positioning System |journal=VLSI Design |volume=15 |issue=2 |pages=507–520 |doi=10.1080/1065514021000012129 |doi-access=free }}</ref><ref name="Chan">"A simple and efficient estimator for hyperbolic location", Y. T. Chan and K. C. Ho, ''IEEE Transactions on Aerospace and Electronic Systems'', Volume: AES-42, Issue: 8 (Aug. 1994), pp 1905-1915.</ref> Notably, all closed-form solutions were found a decade or more after the GPS program was initiated using iterative methods.

The solution for the position of an aircraft having a known altitude using 3 TOA measurements requires solving a quartic (fourth-order) polynomial.<ref name="Geyer">{{cite book|last=Geyer|first=Michael|date=June 2016|title=Earth-Referenced Aircraft Navigation and Surveillance Analysis|url=https://rosap.ntl.bts.gov/view/dot/12301|location=U.S. DOT National Transportation Library|publisher=U.S. DOT John A. Volpe National Transportation Systems Center}}</ref><ref name="Phatak">{{cite journal|last1=Phatak|first1=M. |last2=Chansarkar|first2=M.|last3=Kohli|first3=S. |date=January 1999|title=Position fix from Three GPS Satellites and Altitude: A direct method|journal=IEEE Transactions on Aerospace and Electronic Systems|volume=35|issue=1|page=350 |doi=10.1109/7.745705 |bibcode=1999ITAES..35..350P }}</ref>

Multilateration systems and studies employing spherical-range measurements (e.g., Loran-C, Decca, Omega) utilized a variety of solution algorithms based on either iterative methods or spherical trigonometry.<ref name="Razin">{{cite journal |last1=Razin|first1=Sheldon|date=Fall 1967|title=Explicit (Noniterative) Loran Solution|journal=Navigation: Journal of the Institute of Navigation|volume=14|issue=3|pages=265–269|doi=10.1002/j.2161-4296.1967.tb02208.x }}</ref>

=== Three-dimensional Cartesian algorithms ===
For Cartesian coordinates, when four TOAs are available and the TOT is needed, Bancroft's<ref name=Bancroft /> or another closed-form (direct) algorithm are options, even if the stations are moving. When the four stations are stationary and the TOT is not needed, extension of Fang's algorithm (based on DTOAs) to three dimensions is an option.<ref name=Geyer /> Another option, and likely the most utilized in practice, is the iterative Gauss–Newton Nonlinear Least-Squares method.<ref name=Sirola /><ref name=Geyer />

Most closed-form algorithms reduce finding the user vehicle location from measured TOAs to the solution of a quadratic equation. One solution of the quadratic yields the user's location. The other solution is either ambiguous or extraneous – both can occur (which one depends upon the dimensions and the user location). Generally, eliminating the incorrect solution is not difficult for a human, but may require vehicle motion and/or information from another system. An alternative method used in some multilateration systems is to employ the Gauss–Newton NLLS method and require a redundant TOA when first establishing surveillance of a vehicle. Thereafter, only the minimum number of TOAs is required.

Satellite navigation systems such as GPS are the most prominent examples of 3-D multilateration.<ref name="Abel1">"Existence and uniqueness of GPS solutions", J.S. Abel and J.W. Chaffee, ''IEEE Transactions on Aerospace and Electronic Systems'', vol. 26, no. 6, pp. 748–53, Sept. 1991.</ref><ref name="Fang2">"Comments on "Existence and uniqueness of GPS solutions" by J.S. Abel and J.W. Chaffee", B.T. Fang, ''IEEE Transactions on Aerospace and Electronic Systems'', vol. 28, no. 4, Oct. 1992.</ref>  Wide Area Multilateration (WAM), a 3-D aircraft surveillance system, employs a combination of three or more TOA measurements and an aircraft altitude report.

=== Two-dimensional Cartesian algorithms ===
For finding a user's location in a two dimensional (2-D) Cartesian geometry, one can adapt one of the many methods developed for 3-D geometry, most motivated by GPS—for example, Bancroft's<ref name="Geyer98">{{cite conference |title=Solving Passive Multilateration Equations Using Bancroft's Algorithm |last1=Geyer |first1=Michael |last2=Daskalakis |first2=Anastasios |date=1998 |location=Seattle, WA |conference=Digital Avionics Systems Conference (DASC) }}</ref> or Krause's.<ref name="Krause" /> Additionally, there are specialized TDOA algorithms for two-dimensions and stations at fixed locations — notable is Fang's method.<ref name="Fang">"Simple Solutions for Hyperbolic and Related Position Fixes", Bertrand T. Fang, ''IEEE Transactions on Aerospace and Electronic Systems'', September 1990, pp 748–753.</ref>

A comparison of 2-D Cartesian algorithms for airport surface surveillance has been performed.<ref name="Mantilla">"Localization algorithms for multilateration (MLAT) systems in airport surface surveillance", Ivan A. Mantilla-Gaviria, Mauro Leonardi,·Gaspare Galati and Juan V. Balbastre-Tejedor, Springer-Verlag, London, 2014</ref> However, as in the 3-D situation, it is likely the most utilized algorithms are based on Gauss–Newton NLLS.<ref name="Sirola" /><ref name=Geyer />

Examples of 2-D Cartesian multilateration systems are those used at major airports in many nations to surveil aircraft on the surface or at very low altitudes.

=== Two-dimensional spherical algorithms ===
Razin<ref name="Razin" /> developed a closed-form algorithm for a spherical earth. Williams and Last<ref name="Williams">{{cite conference |title=On Loran-C Time-Difference to Co-ordinate Converters |first1=Paul |last1=Williams |first2=David |last2=Last |conference=International Loran Association (ILA) - 32nd Annual Convention and Technical Symposium |location=Boulder, Colorado |date=November 3–7, 2003 |citeseerx=10.1.1.594.6212 |url=https://loran.org/proceedings/Meeting2003/Session9/WmsLastILA03TD2LL.pdf |conference-url=https://loran.org/proceedings/Meeting2003/ProceedingsIndex.htm}}</ref> extended Razin's solution to an osculating sphere earth model.

When necessitated by the combination of vehicle-station distance (e.g., hundreds of miles or more) and required solution accuracy, the ellipsoidal shape of the earth must be considered. This has been accomplished using the Gauss–Newton NLLS<ref name="RTCM">''Minimum Performance Standards (MPS) Automatic Co-ordinate Conversion Systems'', Report of RTCM Special Committee No. 75, Radio Technical Commission for Marine Services, Washington, D.C, 1984</ref> method in conjunction with ellipsoid algorithms by Andoyer,<ref name="Andoyer">"Formule donnant la longueur de la géodésique, joignant 2 points de l'ellipsoide donnes par leurs coordonnées geographiques", Marie Henri Andoyer, ''Bulletin Geodsique'', No. 34 (1932), pages 77–81</ref> Vincenty<ref name="Vincenty">"Direct and Inverse Solutions of Geodesics on the Ellipsoids with Applications of Nested Equations", Thaddeus Vincenty, ''Survey Review'', XXIII, Number 176 (April 1975)</ref> and Sodano.<ref name="Sodano">"General non-iterative solution of the inverse and direct geodetic problems", Emanuel M. Sodano, ''Bulletin Géodésique'', vol 75 (1965), pp 69–89</ref>

Examples of 2-D 'spherical' multilateration navigation systems that accounted for the ellipsoidal shape of the earth are the [[Engineering:Loran-C|Loran-C]] and Omega radionavigation systems, both of which were operated by groups of nations. Their Russian counterparts, [[Engineering:CHAYKA|CHAYKA]] and [[Engineering:Alpha (navigation)|Alpha]] (respectively), are understood to operate similarly.

=== Cartesian solution with limited computational resources ===
Consider a three-dimensional Cartesian scenario. Improving accuracy with a large number of receivers (say, <math>n + 1</math>, numbered <math>0, 1, 2, \dots, n</math>) can be a problem for devices with small embedded processors, because of the time required to solve several simultaneous, non-linear equations ({{EquationNote|1}}, {{EquationNote|2}}, {{EquationNote|3}}). The TDOA problem can be turned into a system of linear equations when there are three or more receivers, which can reduce the computation time. Starting with equation {{EquationNote|3}}, solve for <math>R_i</math>, square both sides, collect terms and divide all terms by <math>c \tau_i = R_i - R_0</math>:
{{NumBlk|:|
<math>\begin{align}
R_i^2 &= (c \tau_i + R_0 )^2, \\
0     &= (c \tau_i) + 2 R_0 + \frac{R_0^2 - R_i^2}{c \tau_i}.
\end{align} </math>
|{{EquationRef|4}}}}

Removing the <math>2R_0</math> term will eliminate all the square root terms.  That is done by subtracting the TDOA equation of receiver <math>i = 1</math> from each of the others (<math>2 \le m \le n</math>)
{{NumBlk|:|
<math>
0 = c \tau_i - c \tau_1 + \frac{R_0^2 - R_i^2}{c \tau_i} - \frac{R_0^2 - R_1^2}{c \tau_1}.
</math>
|{{EquationRef|5}}}}

Focus for a moment on equation {{EquationNote|1}}. Square <math>R_0</math>, group similar terms and use equation&nbsp;{{EquationNote|2}} to replace some of the terms with <math>R_0</math>.
{{NumBlk|:|
<math>
R_0^2 - R_i^2 = -x_i^2 - y_i^2 - z_i^2 + x\,2x_i + y\,2y_i + z\,2z_i.
</math>
|{{EquationRef|6}}}}

Combine equations {{EquationNote|5}} and {{EquationNote|6}}, and write as a set of linear equations (for <math>2 \le i \le n</math>) of the unknown emitter location <math>x, y, z</math>
{{NumBlk|:|
<math> \begin{align} 
 0   &=  xA_i + yB_i + zC_i + D_i, \\
 A_i &= \frac{2x_i}{c \tau_i} - \frac{2x_1}{c \tau_1}, \\
 B_i &= \frac{2y_i}{c \tau_i} - \frac{2y_1}{c \tau_1}, \\
 C_i &= \frac{2z_i}{c \tau_i} - \frac{2z_1}{c \tau_1}, \\
 D_i &= c \tau_i - c \tau_1 - \frac{x_i^2 + y_i^2 + z_i^2}{c \tau_i}
                            + \frac{x_1^2 + y_1^2 + z_1^2}{c \tau_1}.
\end{align} </math>
|{{EquationRef|7}}}}

Use equation {{EquationNote|7}} to generate the four constants <math>A_i, B_i, C_i, D_i</math> from measured distances and time for each receiver <math>2 \le i \le n</math>. This will be a set of <math>n - 1</math> inhomogeneous linear equations.

There are many robust linear algebra methods that can solve for <math>(x, y, z)</math>, such as [[Gaussian elimination]]. Chapter&nbsp;15 in [[Software:Numerical Recipes|Numerical Recipes]]<ref>[http://www.numerical.recipes/ Numerical Recipes] official website.</ref> describes several methods to solve linear equations and estimate the uncertainty of the resulting values.

=== Iterative algorithms ===
The defining characteristic and major disadvantage of iterative methods is that a 'reasonably accurate' initial estimate of the 'vehicle's' location is required. If the initial estimate is not sufficiently close to the solution, the method may not converge or may converge to an ambiguous or extraneous solution. However, iterative methods have several advantages:<ref name="Sirola">{{cite conference|title=Closed-form Algorithms in Mobile Positioning: Myths and Misconceptions|last1=Sirola|first1=Niilo|date=March 2010|citeseerx=10.1.1.966.9430|conference=7th Workshop on Positioning, Navigation and Communication 2010 WPNC'10}}.</ref>
* Can use redundant measurements <math>(m > d+1)</math>  
* Can utilize uninvertible measurement equations — Enables, e.g., use of complex problem geometries such as an ellipsoidal earth's surface. 
* Can utilize measurements lacking an analytic expression (e.g., described by a numerical algorithm and/or involving measured data) — What is required is the capability to compute a candidate solution (e.g., user-station range) from hypothetical user position quantities (e.g., latitude and longitude)
* Amenable to automated processing (avoids the extraneous and ambiguous solutions which occur in direct algorithms)
* Can treat random measurement errors linearly, which when <math>m>d+1</math> allows averaging and thus minimizes their effect on position error.

Many real-time multilateration systems provide a rapid sequence of user's position solutions — e.g., GPS receivers typically provide solutions at 1 sec intervals. Almost always, such systems implement: (a) a transient 'acquisition' (surveillance) or 'cold start' (navigation) mode, whereby the user's location is found from the current measurements only; and (b) a steady-state 'track' (surveillance) or 'warm start' (navigation) mode, whereby the user's previously computed location is updated based current measurements (rendering moot the major disadvantage of iterative methods). Often the two modes employ different algorithms and/or have different measurement requirements, with (a) being more demanding. The iterative Gauss-Newton algorithm is often used for (b) and may be used for both modes.

When there are more TOA measurements than the <math>d+1</math> unknown quantities – e.g., 5 or more GPS satellite TOAs – the iterative Gauss–Newton algorithm for solving [[Non-linear least squares|non-linear least squares]] (NLLS) problems is often preferred.  Except for pathological station locations, an over-determined situation eliminates  possible ambiguous and/or extraneous solutions that can occur when only the minimum number of TOA measurements are available. Another important advantage of the Gauss–Newton method over some closed-form algorithms is that it treats measurement errors linearly, which is often their nature, thereby reducing the effect measurement errors by averaging. The Gauss–Newton method may also be used with the minimum number of measurements.

While the Gauss-Newton NLLS iterative algorithm is widely used in operational systems (e.g., ASDE-X), the Nelder-Mead iterative method is also available. Example code for the latter, for both TOA and TDOA systems, are available.<ref name="UCNL">{{cite web|url=https://github.com/ucnl/UCNLNav|title=Underwater Communications & Navigation Laboratory Library|website=[[GitHub]] }}</ref>

== Accuracy ==

Multilateration is often more accurate for locating an object than [[True-range multilateration|true-range multilateration]] or multiangulation, as (a) it is inherently difficult and/or expensive to accurately measure the true range (distance) between a moving vehicle and a station, particularly over large distances, and (b) accurate angle measurements require large antennas which are costly and difficult to site.

Accuracy of a multilateration system is a function of several factors, including:
* The [[Geometry|geometry]] of the receiver(s) and [[Engineering:Transmitter|transmitter(s)]] for [[Engineering:Electronics|electronic]], [[Physics:Optics|optical]] or other wave phenomenon.
* The synchronization accuracy of the transmitters (navigation) or the receivers (surveillance), including the [[Drift (telecommunication)|thermal stability]] of the clocking oscillators.
* Propagation effects -— e.g., diffraction or reflection changes from the assumed [[Line-of-sight propagation|line of sight]] or curvilinear propagation path.
* The bandwidth of the emitted signals—e.g., the rise-time of the pulses employed with pulse coded signals.
* Inaccuracies in the locations of the transmitters or receivers when used as known locations.
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.<ref name=Domingo-Perez />

Concerning the first issue (user-station geometry), planning a multilateration system often involves a dilution of precision (DOP) analysis to inform decisions on the number and location of the stations and the system's service area (two dimensions) or volume (three dimensions). In a DOP analysis, the TOA measurement errors are assumed to be statistically independent and identically distributed. This reasonable assumption separates the effects of user-station geometry and TOA measurement errors on the error in the calculated user position.<ref name="Lee1">[https://rosap.ntl.bts.gov/view/dot/12133 ''Accuracy Limitations of Hyperbolic Multilateration Systems''], Harry B. Lee, Massachusetts Institute of Technology, Lincoln Laboratory, Technical Note 1973-11, March 22, 1973</ref><ref name="Lee2">[https://rosap.ntl.bts.gov/view/dot/12132 ''Improved Satellite Constellations for CONUS ATC Coverage''], Harry B. Lee and Andrew E. Wade, Massachusetts Institute of Technology, Lincoln Laboratory, Project Report ATC-23, May 1, 1974</ref>

== Station synchronization ==
Multilateration requires that spatially separated stations – either transmitters (navigation) or receivers (surveillance) – have synchronized 'clocks'. There are two distinct synchronization requirements: (1) maintain synchronization accuracy continuously over the life expectancy of the system equipment involved (e.g., 25 years); and (2) for surveillance, accurately measure the time interval between TOAs for each 'vehicle' transmission. Requirement (1) is transparent to the user, but is an important system design consideration. To maintain synchronization, station clocks must be synchronized or reset regularly (e.g., every half-day for GPS, every few minutes for ASDE-X). Often the system accuracy is monitored continuously by "users" at known locations - e.g., GPS has five monitor sites.

Multiple methods have been used for station synchronization. Typically, the method is selected based on the distance between stations. In approximate order of increasing distance, methods have included:
* Hard-wired clockless stations (navigation and surveillance) – Clockless stations are hard-wired to a central location having the single system clock. Wire lengths are generally equal, but that may not be possible in all applications. This method has been used for locating artillery fire (stations are microphones).
* Radio-linked clockless stations (navigation and surveillance) - Clockless stations are radio-linked or microwave-linked to a central location having the single system clock. Link delays are equalized. This method is used by some wide area multilateration (WAM) systems.
* Test target (surveillance) – A test target is installed at a fixed, known location that's visible to all receivers. The test target transmits as an ordinary user would, and its position is calculated from the TOAs. Its known position is used to adjust the receiver clocks. ASDE-X uses this method.
* Fixed transmitter delays (navigation) – One transmitter is designated the master; the others are secondaries. The master transmits first. Each secondary transmits a fixed (short) time after receiving the master's transmission. Loran-C originally used this method.
* Continuously broadcast phase information (navigation) - Phase information is continuously broadcast on different frequencies. Used by Decca.
* Broadcast pulsed phase information (navigation) - Pulsed phase information is broadcast on the same frequency according to a known schedule. Used by Omega.
* Satellite time transfer (navigation and surveillance) – There are multiple methods for transferring time from a reference site to a remote station via satellite. The simplest is to synchronize the stations to GPS time.<ref name="time">[https://www.nist.gov/pml/time-and-frequency-division/atomic-standards/one-way-gps-time-transfer One Way GPS Time Transfer], National Institute of Standards and Technology</ref> Some WAM systems use this method. 
* Atomic clocks (navigation and surveillance) – Each station has one or more synchronized atomic clocks. GNSSs use this method and Omega did. Loran-C switched to it. Even atomic clocks drift, and a monitoring and/or correction system may be required.

== Service area or volume ==

=== Sensitivity of accuracy to vehicle-station geometry ===
While the performance of all navigation and surveillance systems depends upon the user's location relative to the stations, multilateration systems are more sensitive to the user-station geometry than are most systems. To illustrate, consider a hypothetical two-station surveillance system that monitors the location of a railroad locomotive along a straight stretch of track—a one dimensional situation <math>(d=1)</math>. The locomotive carries a transmitter and the track is straight in both directions beyond the stretch that's monitored. For convenience, let the system origin be mid-way between the stations; then <math>TDOA = 0</math> occurs at the origin.

Such a system would work well when a locomotive is between the two stations. When in motion, a locomotive moves directly toward one station and directly away from the other. If a locomotive is distance <math>\Delta</math> away from the origin, in the absence of measurement errors, the TDOA would be <math>TDOA=\pm 2 \, \Delta / \, c</math> (where <math>c</math> is the known wave propagation speed). Thus, (ignoring the scale-factor <math>c</math>) the amount of displacement is doubled in the TDOA. If true ranges were measured instead of pseudo-ranges, the measurement difference would be identical.

However, this one-dimensional pseudo-range system would not work at all when a locomotive is not between the two stations. In either extension region, if a locomotive moves between two transmissions, necessarily away from both stations, the TDOA would not change. In the absence of errors, the changes in the two TOAs would perfectly cancel in forming the TDOA. In the extension regions, the system would always indicate that a locomotive was at the nearer station, regardless of its actual position. In contrast, a system that measures true ranges would function in the extension regions exactly as it does when the locomotive is between the stations. This one-dimensional system provides an extreme example of a multilateration system's service area.

[[File:2D Mlat Service Area v2.jpg|thumb|Fig. 5. Approximate service area of a planar multilateration system having three equally-spaced stations]]

In a multi-dimensional (i.e., <math>d=2</math> or <math>d=3</math>) situation, the measurement extremes of a one-dimensional scenario rarely occur. When it is within the perimeter enclosing the stations, a vehicle usually moves partially away from some stations and partially toward other stations. It is highly unlikely to move directly toward any one station and simultaneously directly away from another; moreover, it cannot move directly toward or away from all stations at the same time. Simply put, inside the stations' perimeter, consecutive TDOAs will typically amplify but not double vehicle movement <math>\Delta</math> which occurred during that interval—i.e., <math>(\Delta / \, c < |TDOA_{i+1}-TDOA_i| < 2 \, \Delta / \, c)</math>. Conversely, outside the perimeter, consecutive TDOAs will typically attenuate but not cancel associated vehicle movement—i.e., <math>(0 < |TDOA_{i+1}-TDOA_i| < \Delta / \, c)</math>. The amount of amplification or attenuation will depend upon the vehicle's location. The system's performance, averaged over all directions, varies continuously as a function of user location.

=== Dilution Of Precision (DOP) ===
When analyzing a 2D or 3D multilateration system, [[Engineering:Dilution of precision (navigation)|dilution of precision (DOP)]] is usually employed to quantify the effect of user-station geometry on position-determination accuracy.<ref name="Langley">[http://www2.unb.ca/gge/Resources/gpsworld.may99.pdf "Dilution of Precision"], Richard Langeley, ''GPS World'', May 1999, pp.&nbsp;52–59.</ref> The basic DOP metric is 
: <math>
?\text{DOP} = \frac{\text{XXX error (after calculations using measurements)}}{\text{pseudo-range (scaled TOA) measurement error}}.
</math>
The symbol <math>?</math> conveys the notion that there are multiple "flavors" of DOP{{snd}} the choice depends upon the number of spatial dimensions involved and whether the error for the TOT solution is included in the metric. The same distance units must be used in the numerator and denominator of this fraction{{snd}} e.g., meters. ?DOP is a dimensionless factor that is usually greater than one, but is independent of the pseudo-range (PR) measurement error. (When redundant stations are involved, it is possible to have 0 < ?DOP < 1.) HDOP is usually employed (? = H, and XXX = horizontal position) when interest is focused on a vehicle position on a plane.

Pseudo-range errors are assumed to add to the measured TOAs, be Gaussian-distributed, have zero mean (average value) and have the same standard deviation <math>\sigma_{PR}</math> regardless of vehicle location or the station involved. Labeling the orthogonal axes in the plane as <math>x</math> and <math>y</math>, the horizontal position error is characterized statistically as
:<math>
\text{HDOP} = \frac{\sqrt{\sigma_x^2 + \sigma_y^2}}{\sigma_{PR}}.
</math>
Mathematically, each DOP "flavor" is a different sensitivity ("derivative") of a solution quantity (e.g., horizontal position) standard deviation with respect to the pseudo-range error standard deviation. (Roughly, DOP corresponds to the condition <math>\Delta \to 0</math>.) That is, ?DOP is the rate of change of the standard deviation of a solution quantity from its correct value due to measurement errors{{snd}} assuming that a linearized least squares algorithm is used. (It is also the smallest variance for any algorithm.<ref name="Chaffee2">{{cite conference |title=GDOP and the Cramer-Rao bound |last1=Chaffee |first1=J. |last2=Abel |first2=J. |date=1994 |location=Las Vegas, NV |conference=IEEE Position, Location and Navigation Symposium (PLANS)  
|pages=663–668 }}</ref>) Specifically, HDOP is the sensitivity ("derivative") of the user's horizontal position standard deviation (i.e., its sensitivity) to the pseudo-range error standard deviation.

For three stations, multilateration accuracy is quite good within almost the entire triangle enclosing the stations—say, 1 < HDOP < 1.5 and is close to the HDOP for true ranging measurements using the same stations. However, a multilateration system's HDOP degrades rapidly for locations outside the station perimeter. Figure&nbsp;5 illustrates the approximate service area of two-dimensional multilateration system having three stations forming an equilateral triangle. The stations are '''M'''–'''U'''–'''V'''. BLU denotes baseline unit (station separation <math>B</math>). The inner circle is more "conservative" and corresponds to a "cold start" (no knowledge of vehicle's initial position). The outer circle is more typical, and corresponds to starting from a known location. The axes are normalized by the separation between stations.
: <math>
\xi = \frac{x}{B}, \quad \zeta = \frac{y}{B}.
</math> 
[[File:MLAT 3p HDOP.jpg|thumb|Fig. 6. HDOP contours for a planar multilateration system having three equally spaced stations]]
 
Figure 6 shows the HDOP contours for the same multilateration system. The minimum HDOP, 1.155, occurs at the center of the triangle formed by the stations (and would be the same value for true range measurements). Beginning with HDOP = 1.25, the contours shown follow a factor-of-2 progression. Their roughly equal spacing (outside of the three V-shaped areas between the baseline extensions) is consistent with the rapid growth of the horizontal position error with distance from the stations. The system's HDOP behavior is qualitatively different in the three V-shaped areas between the baseline extensions. HDOP is infinite along the baseline extensions, and is significantly larger in these area. (HDOP is mathematically undefined at the stations; hence multiple DOP contours can terminate on a station.) A three-station  system should not be used between the baseline extensions.

For locations outside the stations' perimeter, a multilateration system should typically be used only near the center of the closest baseline connecting two stations (two dimensional planar situation) or near the center of the closest plane containing three stations (three dimensional situation). Additionally, a multilateration system should only be employed for user locations that are a fraction of an average baseline length (e.g., less than 25%) from the closest baseline or plane. For example:
* To ensure that users were within the station perimeter, Loran-C stations were often placed at locations that many persons would consider "remote", e.g. to provide navigation service to ships and aircraft in the North Atlantic area, there were stations at [[Biography:Faroe Islands|Faroe Islands]] (Denmark), Jan Mayen Island (Norway) and Angissq (Greenland). 
* While GPS users on/near the Earth's surface are always outside the perimeter of the visible satellites, a user is typically close to the center of the nearest plane containing three low-elevation-angle satellites and is between 5% and 10% of a baseline length from that plane.

When more than the required minimum number of stations are available (often the case for a GPS user), HDOP can be improved (reduced). However, limitations on use of the system outside the polygonal station perimeter largely remain. Of course, the processing system (e.g., GPS receiver) must be able to utilize the additional TOAs. This is not an issue today, but has been a limitation in the past.

== Example applications ==

* [[Engineering:Global Positioning System|GPS]] (U.S.), [[Astronomy:GLONASS|GLONASS]] (Russia), Galileo (E.U.) – Global navigation satellite systems. Two  complicating factors relative to TDOA systems are: (1) the transmitter stations (satellites) are moving; and (2) receivers must compute TOT, requiring a more complex algorithm (but providing accurate time to users). 
* Sound ranging – Using sound to locate the source of artillery fire.
* Electronic targets – Using the Mach wave of a bullet passing a sensor array to determine the point of arrival of the bullet on a firing range target.
* [[Engineering:Decca Navigator System|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, technically similar to Decca but providing service for much longer range;, shut down in 1997
* [[Engineering:Gee (navigation)|Gee (navigation)]] – British aircraft location system used during World War II
* [[Engineering:Loran-C|Loran-C]] – Navigation system using TDOA of signals from multiple synchronized transmitters; shut down in the U.S. and Europe; Russian Chayka system was similar
* Passive [[Social:Electronic warfare support measures|ESM]] (electronic support measures) multilateration non-cooperative surveillance systems, including Kopáč, Ramona, Tamara, VERA and possibly Kolchuga – located a transmitter using multiple receivers
* [[Earth:Mobile phone tracking|Mobile phone tracking]] – using multiple base stations to estimate phone location, either by the phone itself (navigation, industry term is downlink multilateration), or by the phone network (surveillance, industry term is uplink multilateration)
* Reduced Vertical Separation Minima (RVSM) monitoring to determine the accuracy of Mode C/S aircraft transponder altitude information.  Application of multilateration to RVSM was first demonstrated by Roke Manor Research Limited in 1989.<ref>{{cite web|title=Perfect Timing|url=http://www.roke.co.uk/resources/articles/Perfect-Timing-ATTI-2002.pdf|access-date=31 August 2012|author=Air Traffic Technology International|year=2002|url-status=dead|archive-url=https://web.archive.org/web/20141218132533/http://www.roke.co.uk/resources/articles/Perfect-Timing-ATTI-2002.pdf|archive-date=18 December 2014}}</ref>
* Wide area multilateration (WAM) – Surveillance system for airborne aircraft that measures the TOAs of emissions from the aircraft transponder (on 1090&nbsp;MHz); in operational service in several countries <ref>{{cite web |url=https://www.faa.gov/about/office_org/headquarters_offices/ang/offices/tc/library/storyboard/detailedwebpages/wam.html |title=WAM Wide Area Multilateration |author=<!--Not stated--> |website=Federal Aviation Administration |access-date=May 12, 2022 }}</ref>
* Airport Surface Detection Equipment, Model X (ASDE-X) – Surveillance system for aircraft and other vehicles on the surface of an airport; includes a multilateration sub-system that measures the TOAs of emissions from the aircraft transponder (on 1090&nbsp;MHz); ASDE-X is U.S. FAA terminology, similar systems are in service in several countries.
* Flight Test "Truth" – [[Company:Locata Corporation|Locata Corporation]] offers a ground-based local positioning system that augments GPS and is used by NASA and the U.S. military
* Seismic Event Location – Events (e.g., earthquakes) are monitored by measuring TOAs at different locations and employing multilateration algorithms<ref name="Gomez">"A Closed-Form Solution for Earthquake Location in a Homogeneous Half-Space Based on the Bancroft GPS Location Algorithm", Demian Gomez, Charles Langston & Bob Smalley, ''Bulletin of the Seismological Society of America'', January 2015.</ref>
* [[Towed array sonar]] / SURTASS / SOFAR (SOund Fixing And  Ranging) – Systems employed by the U.S. Navy (and likely similar systems by other navies). Purposes are to detect and determine the direction and rough distance of a sound source (e.g., submarine) from listening. Sensors move, which is unusual for surveillance systems.
* MILS and SMILS Missile Impact Location Systems – Acoustic systems deployed to determine the 'splash down' points in the South Atlantic of Polaris, Poseidon and Trident missiles that were test-fired from Cape Canaveral, FL.
* Passive Sonar - Utilizes acoustic waves (TOAs and other features) to detect (and perhaps localize) ships
* Atlantic Undersea Test and Evaluation Center (AUTEC) – U.S. Navy facility that measures trajectories of undersea boats and weapons using acoustics
* Ultrasonic Indoor Positioning - 3D position of a smartphone within a building "room" can be obtained through an ultrasound system<ref>{{Cite journal|last1=Carotenuto|first1=Riccardo|last2=Merenda|first2=Massimo|last3=Iero|first3=Demetrio|last4=G. Della Corte|first4=Francesco|date=January 2020|title=Mobile Synchronization Recovery for Ultrasonic Indoor Positioning |journal=Sensors |language=en |volume=20 |issue=3 |pages=702 |doi=10.3390/s20030702 |pmc=7038533|pmid=32012789|bibcode=2020Senso..20..702C|doi-access=free}}</ref><ref>{{Cite book|last1=Carotenuto|first1=R.|last2=Merenda|first2=M.|last3=Iero|first3=D.|last4=Corte|first4=F. G. Della|title=2020 5th International Conference on Smart and Sustainable Technologies (SpliTech) |chapter=Indoor Object Positioning using Smartphone and RFID or QRCode |date=September 2020|chapter-url=https://ieeexplore.ieee.org/document/9243703|pages=1–6|doi=10.23919/SpliTech49282.2020.9243703|isbn=978-953-290-105-4|s2cid=226264802}}</ref><ref>{{cite web |url=https://www.sonitor.com/ |title=RTLS: Ultrasound-Based Accurate Indoor Positioning |author=<!--Not stated--> |date=2022 |website=Sonitor |access-date=April 27, 2022 }}</ref>
* ShotSpotter - Gunfire location system<ref>{{cite web|title=Field Evaluation of the ShotSpotter Gunshot Location System: Final Report on the Redwood City Field Trial|url=https://www.ojp.gov/ncjrs/virtual-library/abstracts/field-evaluation-shotspotter-gunshot-location-system-final-report|access-date=9 April 2021|author=U.S. Dept. of Justice|year=1999}}</ref>

== See also ==
* Ranging
* True Range Multilateration
* [[Engineering:Rangefinder|Rangefinder]]
* [[Engineering:Hyperbolic navigation|Hyperbolic navigation]] – Alternative term (to multilateration) for TDOA navigation systems with stationary transmitters
* [[FDOA]] – Frequency difference of arrival using differential Doppler measurements.
* [[Triangulation]] – Location by angular measurement on lines of bearing that intersect
* [[Trilateration]] – Location by multiple distances, typically three distances on a plane; a specific technique used in surveying. 
* [[Earth:Mobile phone tracking|Mobile phone tracking]]
* [[Multidimensional scaling]]
* [[Earth:Positioning system|Positioning system]]
* {{section link|Problem of Apollonius|Applications}}
* [[Engineering:Radiolocation|Radiolocation]]
* [[Radio navigation]]
* 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
* [[Great-circle navigation]] – Provides the basic mathematics for addressing spherical ranges
* [[Non-linear least squares]] - Form of least-squares analysis when non-linear equations are involved; used for multilateration when (a) there are more range-difference measurements than unknown variables, and/or (b) the measurement equations are too complex to be inverted (e.g., those for an ellipsoidal earth), and/or (c) tabular data must be utilized (e.g., conductivity of the earth over which radio wave propagated).
* [[Physics:Coordinated Universal Time|Coordinated Universal Time]] (UTC) - Time standard provided by GPS receivers (with published offset)
* [[Clock synchronization]] - Methods for synchronizing clocks at remote stations
* [[Engineering:Atomic clock|Atomic clock]] – Sometimes used to synchronize multiple widely separated stations
* [[Engineering:Dilution of precision (navigation)|Dilution of precision]] – Analytic technique often applied to the design of multilateration systems
* [[Gauss–Newton algorithm]] – Iterative solution method used by several operational multilateration systems
* [[Loss function]] - Also termed cost function or error function; used to convert redundant TOA measurements to a single equation
* [[Rotation of axes]] - Addresses rotating from one Cartesian coordinate frame to another
* [[Engineering:Real-time locating system|Real-time locating system]] (RTLS) - Multilateration can be employed in a RTLS indoor surveillance system. 
* Unilateration<ref name="Uni">{{cite web |url=http://wiki.gis.com/wiki/index.php/Unilateration |title=Unilateration |author=<!--Not stated--> |date=May 26, 2016 |website=The GIS Encyclopedia |access-date=April 27, 2022 }}</ref> - A type of real time locating system (RTLS)

== Notes ==
{{reflist|2}}

== Categories ==

[[Category:Elementary geometry]]
[[Category:Euclidean geometry]]
[[Category:Radio navigation]]
[[Category:Ubiquitous computing]]
[[Category:Wireless locating]]

{{Sourceattribution|Pseudo-range multilateration}}