Pseudo-range multilateration, often simply multilateration (MLAT) when in context, is a technique for determining the position of an unknown point, such as a vehicle, based on measurement of biased times of flight (TOFs) of energy waves traveling between the vehicle and multiple stations at known locations. TOFs are biased by synchronization errors in the difference between times of arrival (TOA) and times of transmission (TOT): TOF = TOA − TOT. Pseudo-ranges (PRs) are TOFs multiplied by the wave propagation speed: PR = TOF·s. In general, the stations' clocks are assumed synchronized but the vehicle's clock is desynchronized. In MLAT for surveillance, the waves are transmitted by the vehicle and received by the stations; the TOT is unique and unknown, while the TOAs are multiple and known. When MLAT is used for navigation (as in hyperbolic navigation), the waves are transmitted by the stations and received by the vehicle; in this case, the TOTs are multiple but known, while the TOA is unique and unknown. In navigation applications, the vehicle is often termed the "user"; in surveillance applications, the vehicle may be termed the "target". The vehicle's clock is considered an additional unknown, to be estimated along with the vehicle's position coordinates. If d is the number of physical dimensions being considered (e.g., 2 for a plane) and m is the number of signals received (thus, TOFs measured), it is required that m ≥ d + 1 {\displaystyle m\geq d+1} . Processing is usually required to extract the TOAs or their differences from the received signals, and an 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 d vehicle coordinates; or (b) ignores the TOT and forms m − 1 {\displaystyle m-1} (at least d) time difference of arrivals (TDOAs), which are used to find the d vehicle coordinates. Almost always, d = 2 {\displaystyle d=2} (e.g., a plane or the surface of a sphere) or d = 3 {\displaystyle d=3} (e.g., the real physical world). Systems that form TDOAs are also called hyperbolic systems, for reasons discussed below. A multilateration navigation system provides vehicle position information to an entity "on" the vehicle (e.g., aircraft pilot or Global Positioning System (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 Prior to deployment of GPS and other global navigation satellite systems (GNSSs), pseudo-range multilateration systems were often defined as (synonymous with) TDOA systems – 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.)
The technical answer to (a) has long been known: GNSSs are a variety (or sub-species) of multilateration navigation systems having moving transmitters. 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.
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 (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 m received signals, TDOA systems form m − 1 {\displaystyle m-1} 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 m − 1 {\displaystyle m-1} "secondary" stations' TOAs. When m = 3 {\displaystyle m=3} , there are 3 possible TDOA combinations, each corresponding to a station being the de facto master. When m = 4 {\displaystyle m=4} , there are 16 possible TDOA sets, 12 of which do not have a de facto master. When m = 5 {\displaystyle m=5} , there are 125 possible TDOA sets, 120 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 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 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 Decca system, developed during World War II. Decca used the phase-difference of three transmitters. Later, Omega elaborated on this principle. For 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
The TOT concept is illustrated in Figure 2 for the surveillance function and a planar scenario ( d = 2 {\displaystyle d=2} ). Aircraft A, at coordinates ( x A , y A ) {\displaystyle (x_{A},y_{A})} , broadcasts a pulse sequence at time t A {\displaystyle t_{A}} . The broadcast is received at stations S 1 {\displaystyle S_{1}} , S 2 {\displaystyle S_{2}} and S 3 {\displaystyle S_{3}} at times t 1 {\displaystyle t_{1}} , t 2 {\displaystyle t_{2}} and t 3 {\displaystyle t_{3}} respectively. Based on the three measured TOAs, the processing algorithm computes an estimate of the TOT t A {\displaystyle t_{A}} , from which the range between the aircraft and the stations can be calculated. The aircraft coordinates ( x A , y A ) {\displaystyle (x_{A},y_{A})} 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 computed TOT is after the actual TOT, the computed ranges do not have a common point of intersection (dashed-line circles in Figure 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. 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
E → = ( x , y , z ) , {\displaystyle {\vec {E}}=(x,y,z),}
which we wish to locate (surveillance problem). The source is within range of m = n + 1 {\displaystyle m=n+1} receivers at known locations
P → 0 , P → 1 , … , P → i , … , P → n . {\displaystyle {\vec {P}}_{0},{\vec {P}}_{1},\ldots ,{\vec {P}}_{i},\ldots ,{\vec {P}}_{n}.}
The subscript i refers to any one of the receivers:
P → i = ( x i , y i , z i ) , {\displaystyle {\vec {P}}_{i}=(x_{i},y_{i},z_{i}),}
0 ≤ i ≤ n . {\displaystyle 0\leq i\leq n.}
The distance ( R i {\displaystyle R_{i}} ) 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 1 is not valid. Loran-C and Omega are examples of systems that use spherical ranges. When a spherical model for the Earth is satisfactory, the simplest expression for the central angle (sometimes termed the geocentric angle) θ v i {\displaystyle \theta _{vi}} between vehicle v and station i is
cos θ v i = sin φ v sin φ i + cos φ v cos φ i cos ( λ v − λ i ) , {\displaystyle \cos \theta _{vi}=\sin \varphi _{v}\sin \varphi _{i}+\cos \varphi _{v}\cos \varphi _{i}\cos(\lambda _{v}-\lambda _{i}),}
where latitudes are denoted by φ {\displaystyle \varphi } , and longitudes are denoted by λ. Alternative, better numerically behaved equivalent expressions can be found in great-circle navigation. The distance R i {\displaystyle R_{i}} from the vehicle to station i is along a great circle will then be
R i = R E θ v i , {\displaystyle R_{i}=R_{E}\,\theta _{vi},}
where R E {\displaystyle R_{E}} is the assumed radius of the Earth, and θ v i {\displaystyle \theta _{vi}} 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.
Solution algorithms
General algorithm behavior Generally, using a direct (non-iterative) algorithm, m = d + 1 {\displaystyle m=d+1} measurement equations can be reduced to a single scalar nonlinear "solution equation" having one unknown variable (somewhat analogous to Gauss–Jordan elimination for linear equations) – e.g., a quadratic polynomial in one vehicle Cartesian coordinate. The vehicle position and TOT then readily follow in sequence. When m = d {\displaystyle m=d} , 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 (do not provide vehicle positions which have the same measurements, but are the result of mathematical manipulations). Without redundant measurements (i.e., m = d + 1 {\displaystyle m=d+1} ), 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., m > d + 1 {\displaystyle m>d+1} ), a 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 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 ( d + 1 {\displaystyle d+1} ) 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 d + 1 {\displaystyle d+1} 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 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 ) {\displaystyle (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 ) {\displaystyle (x,y)} for an airport application, or latitude/longitude for off-airport applications.) Stephen 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. 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. Notably, all closed-form solutions were found a decade or more after the GPS program was initiated using iterative methods. Closed-form solutions often involve squaring the distance or pseudo-range to avoid local linearization of a square root operation. However, this squaring alters noise statistics and can lead to suboptimal solutions. Typically, a two-step simplification is employed: first, solving a linear least squares problem neglecting spherical constraints (squared distance), and then finding the intersection with the constraint. This approach may suffer performance degradation in the presence of noise. A more refined technique involves directly solving a "constrained least squares" problem, while also addressing modified noise statistics. While this method may not yield a closed-form solution and often necessitates iterative approaches, it offers significant advantages. By bypassing local linearization, it facilitates convergence to a global minimum without requiring an initial guess. Additionally, it tends to encounter fewer local minima and demonstrates increased accuracy, particularly in noisy environments. The constrained least squares solution for TDOA systems was apparently initially proposed by Huang et al. and further explored by subsequent researchers. Similar methodologies were introduced for TOT systems also illustrating how to convert a problem from TDOA to TOT by incorporating an additional equation and an unknown clock bias. The TOT solution outperforms the TDOA solution due to the latter's susceptibility to noise coloring, caused by the subtraction of reference station's TOA. Robust version such as the "constrained least absolute deviations" is also discussed and shows superior performance to least squares in scenarios involving non-Gaussian noise and contamination from outlier measurements. 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 algorithms For Cartesian coordinates, when four TOAs are available and the TOT is needed, Bancroft's 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. Another 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 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 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 is 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 algorithms Razin developed a closed-form algorithm 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, n + 1 {\displaystyle n+1} , numbered 0 , 1 , 2 , … , n {\displaystyle 0,1,2,\dots ,n} ) can be a problem for devices with small embedded processors, because of the time required to solve several simultaneous, non-linear equations (1, 2, 3). The TDOA problem can be turned into a system of linear equations when there are three or more receivers, which can reduce the computation time. Starting with equation 3, solve for R i {\displaystyle R_{i}} , square both sides, collect terms and divide all terms by c τ i = R i − R 0 {\displaystyle c\tau _{i}=R_{i}-R_{0}} :
Removing the 2 R 0 {\displaystyle 2R_{0}} term will eliminate all the square root terms. That is done by subtracting the TDOA equation of receiver i = 1 {\displaystyle i=1} from each of the others ( 2 ≤ m ≤ n {\displaystyle 2\leq m\leq n} )
Focus for a moment on equation 1. Square R 0 {\displaystyle R_{0}} , group similar terms and use equation 2 to replace some of the terms with R 0 {\displaystyle R_{0}} .
Combine equations 5 and 6, and write as a set of linear equations (for 2 ≤ i ≤ n {\displaystyle 2\leq i\leq n} ) of the unknown emitter location x , y , z {\displaystyle x,y,z}
Use equation 7 to generate the four constants A i , B i , C i , D i {\displaystyle A_{i},B_{i},C_{i},D_{i}} from measured distances and time for each receiver 2 ≤ i ≤ n {\displaystyle 2\leq i\leq n} . This will be a set of n − 1 {\displaystyle n-1} inhomogeneous linear equations. There are many robust linear algebra methods that can solve for ( x , y , z ) {\displaystyle (x,y,z)} , such as Gaussian elimination. Chapter 15 in Numerical Recipes describes several methods to solve linear equations and estimate the uncertainty of the resulting values.
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:
Can use redundant measurements ( m > d + 1 ) {\displaystyle (m>d+1)}
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 m > d + 1 {\displaystyle m>d+1} 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 d + 1 {\displaystyle d+1} 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 o