Multilateration

Multilateration (abbreviated MLAT; more completely pseudorange multilateration; also termed hyperbolic positioning) is a technique for determining a 'vehicle's' position based on measurement of the "times of arrival" (TOAs) of energy waves (radio, acoustic, seismic, etc.) having a known waveform and speed when propagating either "from" (navigation) or "to" (surveillance) multiple system stations. These stations are at known locations and have synchronized 'clocks'. Prior to computing a solution, the "time of transmission" (TOT) of the waves is unknown to the receiver on the 'vehicle' (navigation) or the receivers at the stations (surveillance); consequently, also unknown is the wave "time of flight" (TOF). 
If formula_1 is the number of physical dimensions being considered and formula_2 is the number of TOAs available, it's required that formula_3. Then, the fundamental set of formula_2 equations is:
Each "pseudorange" is the corresponding TOA multiplied by the propagation speed with an 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'.
A "navigation" system provides position (and perhaps other) information to an entity on the subject 'vehicle' (e.g., a GPS user, either stationary or moving). A "surveillance" system provides 'vehicle' position information to an entity not on the 'vehicle' (e.g., air traffic controller or a cell phone provider). By the reciprocity principle, any method that can be used for navigation can also be used for surveillance, and vice versa. To find formula_1 'vehicle' coordinates, at least formula_10 TOAs must be measured. Almost always, formula_11 (e.g., a plane or the earth's curved surface) or formula_12 (e.g., the real world).
One can view a multilateration system as having at least formula_10 synchronized 'clocks' (at system stations) with an unknown offset from actual time. Thus, multilateration systems can also be analyzed in terms of pseudorange measurements. Using the measured TOAs, an algorithm either: (a) determines the time of transmission (TOT) for the receiver(s)' 'clock' and formula_1 user coordinates; or (b) ignores the TOT and forms formula_15 (at least formula_1) time difference of arrivals (TDOAs), which are used to find the formula_1 'vehicle's' coordinates. Systems that form TDOAs are also called "hyperbolic" systems, for reasons discussed below. A TDOA, when multiplied by the propagation speed, is the difference in the true ranges between the 'vehicle' and the two stations involved (i.e., the unknown TOT cancels).
Systems have been developed for both TOT and TDOA algorithms. In this article, TDOA or hyperbolic systems are addressed first, as they were implemented first. (It was first used in World War I and applications, such as airport surveillance, continue to be found.) Due to the technology available at the time, TDOA systems often determined a 'vehicle's' location in two dimensions. TOT systems are addressed second. They were implemented, roughly, post-1975, and usually involve satellites. Due to technology advances, TOT systems generally determine a user/vehicle location in three dimensions. However, conceptually, TDOA or TOT algorithms are not linked to the number of dimensions involved.
For surveillance, a TDOA system determines the difference in the 'vehicle's' distance to pairs of stations at known, usually fixed, locations. For one station pair, the distance difference results in an infinite number of possible subject locations that satisfy the TDOA. When these possible locations are plotted, they form a hyperbolic curve. To locate the exact subject's position along that curve, multilateration relies on multiple TDOAs. For two dimensions, a second TDOA, involving a different pair of stations (typically one station is common to both pairs, so that only one station is new), will produce a second curve, which intersects with the first. When the two curves are compared, a small number of possible user locations (typically two) are revealed. Multilateration surveillance can be performed without the cooperation or even knowledge of the subject being surveilled.
TDOA multilateration was a common technique in earth-fixed radio navigation systems, where it was known as 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. The difference in received signal timing can even be measured visibly using an oscilloscope. This formed the basis of a number of widely used navigation systems starting in World War II with the British Gee system and several similar systems deployed over the next few decades. The introduction of the microprocessor greatly simplified operation, increasing popularity during the 1980s. The most popular TDOA hyperbolic navigation system was Loran-C, which was used around the world until the system was largely shut down. The widespread use of satellite navigation systems like the Global Positioning System (GPS) have made earth-fixed TDOA navigation systems largely redundant, and most have been decommissioned. 
Pseudorange multilateration should not be confused with any of:
All of these systems (and combinations of them) are commonly used with radio navigation and surveillance systems, and in other applications. However, this terminology is not always used.
Advantages and disadvantages.
Systems employing pseudo ranges have advantages (which largely benefit the 'vehicle'/user/target) and disadvantages (which largely burden the system provider) relative to systems that employ true ranges. Multilateration was apparently first used during World War I to locate the source of artillery fire using sound waves (surveillance). Longer distance radio-based navigation systems became viable during World War II, with the advancement of radio technologies. The development of atomic clocks for synchronizing widely separated stations was instrumental in the development of the GPS and other GNSSs. 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.
Principle.
Prior to deployment of GPS and other global navigation satellite systems (GNSSs), pseudo-range multilateration systems were often defined as TDOA systems – i.e., systems that formed TDOAs as the first step in processing a set of measured TOAs. As result of deployment of GNSSs, two issues arose: (a) What system type are GNSSs (pseudo-range multilateration, true-range multilateration, or a new system type)? (b) What are the defining characteristic(s) of a pseudo-range multilateration system? 
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 –- e.g., wireless phone providers. Multilateration is also used by the scientific and military communities for non-cooperative surveillance.
TDOA algorithm 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 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 one hyperboloid (see Figure 1). Note that the receivers do not need to know the absolute time at which the pulse was transmitted – only the time difference is needed. 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 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.
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 algorithm 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. For expository purposes, the emitters may be regarded as each broadcasting pulses at exactly the same time on separate frequencies (to avoid interference). In this situation, the receiver measures the TOAs of the pulses. In TDOA systems, the TOAs are immediately differenced and multiplied by the speed of propagation to create range differences.
In operational systems, several methods have been implemented to avoid self-interference. A historic example is the British Decca system, developed during World War II. Decca used the phase-difference of three transmitters. Later, Omega used the same principle. Loran-C, introduced in the late 1950s, used time offset transmissions.
TOT algorithm principle.
The TOT concept is illustrated in Figure 2 for the surveillance function and a planar scenario (formula_11). Aircraft A, at coordinates formula_19, broadcasts a pulse sequence at time formula_20. The broadcast is received at stations formula_21, formula_22 and formula_23 at times formula_24, formula_25 and formula_26, respectively. Based on the three measured TOAs, the processing algorithm computes an estimate of the TOT formula_20, from which the range between the aircraft and the stations can be calculated. The aircraft coordinates formula_19 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 2). If the algorithm's computed TOT is after the actual TOT, the computed ranges do not have a common point of intersection (dashed-line circles in Figure 2). Similarly, if the algorithm's computed TOT is after the actual TOT, the three computed ranges do not have a common point of intersection. 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. 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.
Consider an emitter (E in Figure 3) at an unknown location vector
which we wish to locate. The source is within range of receivers at known locations
The subscript formula_2 refers to any one of the receivers:
The distance (formula_34) 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 (P0), which makes its distance to the emitter
Spherical coordinates.
Low-frequency radio waves follow the curvature of the earth (great circle paths) rather than straight lines. In this situation, equation is not valid. Loran-C and Omega are examples of systems that utilize spherical ranges. When a spherical model for the earth is satisfactory, the simplest expression for the central angle (sometimes termed the "geocentric angle") formula_35 between vehicle formula_36 and station is
Here, latitudes are denoted by formula_38 and longitudes are denoted by formula_39. Alternative, better numerically behaved equivalent expressions, can be found in great-circle navigation.
The distance formula_34 from the vehicle to station is along a great circle will then be
Here, formula_42 is the assumed radius of the earth and formula_35 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 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.
TOA adjustments.
Multilateration system governing equations – which are based on 'distance' equals 'propagation speed' times 'time of flight' – 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 GNSS augmentation systems – e.g., Wide Area Augmentation System (WAAS) and European Geostationary Navigation Overlay Service (EGNOS) – 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 the time difference in a TDOA system.
The basic measurements are the TOAs of multiple signals (formula_44) at the vehicle (navigation) or at the stations (surveillance). The distance formula_45 in equation is the wave speed (formula_46) times transit time, which is unknown, as the time of transmission is not known. A TDOA multilateration system calculates the time differences (formula_47) of a wavefront touching each receiver. The TDOA equation for receivers "m" and 0 is
The quantity formula_48 is often termed a pseudo range. It differs from the true range between the vehicle and station formula_49 by an offset or bias which is the same for every station. Differencing two pseudo range yields the difference of the two true ranges.
Figure 4a is a simulation of a pulse waveform recorded by receivers formula_50 and formula_51. The spacing between formula_52, formula_51 and formula_50 is such that the pulse takes 5 time units longer to reach formula_51 than formula_50. The units of time in Figure 4 are arbitrary. The following table gives approximate time scale units for recording different types of waves.
The red curve in Figure 4a is the cross-correlation function formula_57. 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 formula_58 value needed for Equation .
Figure 4b 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 4a example. Again, the peak in the cross correlation occurs at formula_59.
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 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 (formula_60), frequency ("ƒ") 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.
Solution algorithms.
Overview.
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 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 can have ambiguous solutions, which is detrimental to their automation. A third factor is: Does the algorithm function well with both the minimum number formula_10 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 formula_10 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. 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 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 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 only four TOA measurements. 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 time of signal transmissions. Other, comparable solutions were subsequently developed. 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.
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.
Three-dimensional Cartesian solutions.
For Cartesian coordinates, when four TOAs are available and the TOT is needed, Bancroft's or another closed-form (direct) algorithm are one option, 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 a second option. A third option, and likely the most utilized in practice, is the iterative Gauss–Newton Nonlinear Least-Squares method.
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. 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 solutions.
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 or Krause's. Additionally, there are specialized TDOA algorithms for two-dimensions and stations at fixed locations — notable is Fang's method.
A comparison of 2-D Cartesian algorithms for airport surface surveillance has been performed. However, as in the 3-D situation, it's likely the most utilized algorithms are based on Gauss–Newton NLLS.
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 solutions.
Razin developed a closed-form solution for a spherical earth. Williams and Last 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 method in conjunction with ellipsoid algorithms by Andoyer, Vincenty and Sodano.
Examples of 2-D 'spherical' multilateration navigation systems that accounted for the ellipsoidal shape of the earth are the Loran-C and Omega radionavigation systems, both of which were operated by groups of nations. Their Russian counterparts, CHAYKA and 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, formula_64, numbered formula_65) 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 three or more receivers, which can reduce the computation time. Starting with equation , solve for formula_34, square both sides, collect terms and divide all terms by formula_67:
Removing the formula_68 term will eliminate all the square root terms. That is done by subtracting the TDOA equation of receiver formula_69 from each of the others (formula_70)
Focus for a moment on equation . Square formula_71, group similar terms and use equation to replace some of the terms with formula_71.
Combine equations and , and write as a set of linear equations (for formula_70) of the unknown emitter location formula_74
Use equation to generate the four constants formula_75 from measured distances and time for each receiver formula_70. This will be a set of formula_77 inhomogeneous linear equations".
There are many robust linear algebra methods that can solve for formula_78, such as Gaussian elimination. Chapter 15 in Numerical Recipes 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:
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 formula_10 unknown quantities – e.g., 5 or more GPS satellite TOAs – the iterative Gauss–Newton algorithm for solving 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.
Accuracy.
Multilateration is often more accurate for locating an object than 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 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.
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.
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:
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 formula_81. 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 formula_82 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 formula_83 away from the origin, in the absence of measurement errors, the TDOA would be formula_84 (where formula_46 is the known wave propagation speed). Thus (ignoring the scale-factor formula_46) 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.
In a multi-dimensional (i.e., formula_11 or formula_12) situation, the measurement extremes of a one-dimensional scenario rarely occur. When it's 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 formula_83 which occurred during that interval—i.e., formula_90. Conversely, outside the perimeter, consecutive TDOAs will typically attenuate but not cancel associated vehicle movement—i.e., formula_91. 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.
When analyzing a 2-D or 3-D multilateration system, dilution of precision (DOP) is usually employed to quantify the effect of user-station geometry on position-determination accuracy. The basic DOP metric is 
The symbol formula_93 conveys the notion that there are multiple 'flavors' of DOP—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—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's 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, formula_94 regardless of vehicle's location or the station involved. Labeling the orthogonal axes in the plane as formula_95 and formula_96, the horizontal position error is characterized statistically as:
Mathematically, each DOP 'flavor' is a different sensitivity ("derivative") of a solution quantity's (e.g., horizontal position) standard deviation with respect to the pseudo range error standard deviation. (Roughly, DOP corresponds to the condition formula_98.) That is, ?DOP is the rate of change of the standard deviation of a solution quantity from its correct value due to measurement errors — assuming that a linearized least squares algorithm is used. (It is also the smallest variance for any algorithm.) 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 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 formula_99). 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.
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:
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.
Simplification.
For applications where there is no need for absolute coordinates determination, implementing a simpler 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. The simplest approach is Unilateration. However, the unilateration approach never delivers the angular position with reference to the detector.
Many products are available. Some 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.