True-range multilateration (also termed range–range multilateration and spherical multilateration) is a method to determine the location of a movable vehicle or stationary point in space using multiple ranges (distances) between the vehicle/point and multiple spatially-separated known locations (often termed "stations"). Applications involving vehicle location are termed navigation when on-board persons/equipment are informed of its location, and are termed surveillance when off-vehicle entities are informed of the vehicle's location.
Two slant ranges from two known locations can be used to locate a third point in a two-dimensional Cartesian space (plane), which is a frequently applied technique (e.g., in surveying). Similarly, two spherical ranges can be used to locate a point on a sphere, which is a fundamental concept of the ancient discipline of celestial navigation — termed the altitude intercept problem. Moreover, if more than the minimum number of ranges are available, it is good practice to utilize those as well. This article addresses the general issue of position determination using multiple ranges.
In two-dimensional geometry, it is known that if a point lies on two circles, then the circle centers and the two radii provide sufficient information to narrow the possible locations down to two – one of which is the desired solution and the other is an ambiguous solution. Additional information often narrow the possibilities down to a unique location. In three-dimensional geometry, when it is known that a point lies on the surfaces of three spheres, then the centers of the three spheres along with their radii also provide sufficient information to narrow the possible locations down to no more than two (unless the centers lie on a straight line).
True-range multilateration can be contrasted to the more frequently encountered pseudo-range multilateration, which employs range differences to locate a (typically, movable) point. Pseudo range multilateration is almost always implemented by measuring times-of-arrival (TOAs) of energy waves. True-range multilateration can also be contrasted to triangulation, which involves the measurement of angles.
Terminology
There is no accepted or widely-used general term for what is termed true-range multilateration here . That name is selected because it: (a) is an accurate description and partially familiar terminology (multilateration is often used in this context); (b) avoids specifying the number of ranges involved (as does, e.g., range–range; (c) avoids implying an application (as do, e.g., DME/DME navigation or trilateration) and (d) and avoids confusion with the more common pseudo-range multilateration.
Obtaining ranges
For similar ranges and measurement errors, a navigation and surveillance system based on true-range multilateration provide service to a significantly larger 2-D area or 3-D volume than systems based on pseudo-range multilateration. However, it is often more difficult or costly to measure true-ranges than it is to measure pseudo ranges. For distances up to a few miles and fixed locations, true-range can be measured manually. This has been done in surveying for several thousand years e.g., using ropes and chains.
For longer distances or moving vehicles, a radio/radar system is generally needed. This technology was first developed circa 1940 in conjunction with radar. Since then, three methods have been employed:
- Two-way range measurement, one party active This is the method used by traditional radars (sometimes termed primary radars) to determine the range of a non-cooperative target, and now used by laser rangefinders. Its major limitations are that: (a) the target does not identify itself, and in a multiple target situation, mis-assignment of a return can occur; (b) the return signal is attenuated (relative to the transmitted signal) by the fourth power of the vehicle-station range (thus, for distances of tens of miles or more, stations generally require high-power transmitters or large/sensitive antennas); and (c) many systems utilize line-of-sight propagation, which limits their ranges to less than 20 miles when both parties are at similar heights above sea level.
- Two-way range measurement, both parties active This method was reportedly first used for navigation by the Y-Gerät aircraft guidance system fielded in 1941 by the Luftwaffe. It is now used globally in air traffic control – e.g., secondary radar surveillance and DME/DME navigation. It requires that both parties have both transmitters and receivers, and may require that interference issues be addressed.
- One-way range measurement The time of flight (TOF) of electromagnetic energy between multiple stations and the vehicle is measured based on transmission by one party and reception by the other. This is the most recently developed method, and was enabled by the development of atomic clocks; it requires that the vehicle (user) and stations having synchronized clocks. It has been successfully demonstrated (experimentally) with Loran-C and GPS. This 2-D scenario is sufficiently important that the term trilateration is often applied to all applications involving a known baseline and two range measurements.
The baseline containing the centers of the circles is a line of symmetry. The correct and ambiguous solutions are perpendicular to and equally distant from (on opposite sides of) the baseline. Usually, the ambiguous solution is easily identified. For example, if P is a vehicle, any motion toward or away from the baseline will be opposite that of the ambiguous solution; thus, a crude measurement of vehicle heading is sufficient. A second example: surveyors are well aware of which side of the baseline that P lies. A third example: in applications where P is an aircraft and C1 and C2 are on the ground, the ambiguous solution is usually below ground.
If needed, the interior angles of triangle C1-C2-P can be found using the trigonometric law of cosines. Also, if needed, the coordinates of P can be expressed in a second, better-known coordinate system—e.g., the Universal Transverse Mercator (UTM) system—provided the coordinates of C1 and C2 are known in that second system. Both are often done in surveying when the trilateration method is employed. Once the coordinates of P are established, lines C1-P and C2-P can be used as new baselines, and additional points surveyed. Thus, large areas or distances can be surveyed based on multiple, smaller triangles—termed a traverse.
An implied assumption for the above equation to be true is that <math>r_1</math> and <math>r_2</math> relate to the same position of P. When P is a vehicle, then typically <math>r_1</math> and <math>r_2</math> must be measured within a synchronization tolerance that depends on the vehicle speed and the allowable vehicle position error. Alternatively, vehicle motion between range measurements may be accounted for, often by dead reckoning.
A trigonometric solution is also possible (side-side-side case). Also, a solution employing graphics is possible. A graphical solution is sometimes employed during real-time navigation, as an overlay on a map.
Three Cartesian dimensions, three measured slant ranges
thumb|Fig. 2 3-D True-Range Multilateration Scenario. C1, C2 and C3 are known centers of spheres in the x,y plane. P is point whose (x,y,z) coordinates are desired based on its ranges to C1, C2 and C3.
thumb|right|220px|3-D Trilateration limits the potential positions amount to two (here A or B)
There are multiple algorithms that solve the 3-D Cartesian true-range multilateration problem directly (i.e., in closed-form) – e.g., Fang. Moreover, one can adopt closed-form algorithms developed for pseudo range multilateration. Bancroft's algorithm (adapted) employs vectors, which is an advantage in some situations.
The simplest algorithm corresponds to the sphere centers in Fig. 2. The figure 'page' is the plane containing C1, C2 and C3. If P is a 'point of interest' (e.g., vehicle) at <math>(x,y,z)</math>, then Pythagoras's theorem yields the slant ranges between P and the sphere centers:
: <math> \begin{align}
r_1^2 & = x^2 + y^2 + z^2 \\[4pt]
r_2^2 & = (x-U)^2 + y^2 + z^2 \\[4pt]
r_3^2 & = (x-V_x)^2 + (y-V_y)^2 + z^2
\end{align} </math>
Thus, the coordinates of P are:
The plane containing the sphere centers is a plane of symmetry. The correct and ambiguous solutions are perpendicular to it and equally distant from it, on opposite sides.
Many applications of 3-D true-range multilateration involve short ranges—e.g., precision manufacturing. The requirement that an aircraft be equipped with an atomic clock precludes its general use. However, GPS receiver clock aiding is an area of active research, including aiding over a network. Thus, conclusions may change. 3-D true-range multilateration was evaluated by the International Civil Aviation Organization as an aircraft landing system, but another technique was found to be more efficient. Accurately measuring the altitude of aircraft during approach and landing requires many ground stations along the flight path.
General multilateration
The general multilateration problem consists of computing the unknown position <math display="inline">\boldsymbol {\hat p} = \left[ \hat x, \hat y, \hat z \right]^\text{T}</math> of some target node in 3D space. (Though, the approach described here works also in higher dimensions.) For that, it is assumed that there are <math display="inline">N</math> anchor nodes. The position <math display="inline">\boldsymbol p_i =
\left[
x_i, y_i, z_i
\right]^\text{T}</math> (for <math display="inline">i = 1 \ldots N</math>) of each anchor node must be known. Moreover, it is assumed that the distances <math display="inline">d_i</math> between each anchor node and the target node is known.
The distance <math display="inline">d_i</math> between the <math display="inline">i</math>-th anchor node and the target node is given as follows.<math display="block">d_i =
\left\|
\boldsymbol p_i - \boldsymbol {\hat p}
\right\|_2
=
\sqrt{
(x_i - \hat x)^2
+ (y_i - \hat y)^2
+ (z_i - \hat z)^2
}</math>Below, two different algorithms are shown to compute the target node's position <math display="inline">\boldsymbol {\hat p}</math>. The first algorithm computes the target position by only using the anchor node positions <math display="inline">\boldsymbol p_i</math> and the distances <math display="inline">d_i</math> between the target node and the anchor nodes. The second algorithm assumes that a rough estimate of <math display="inline">\boldsymbol {\hat p}</math> is given. This algorithm then iteratively refines this estimate.
Direct solution
This algorithm computes the target node's position <math display="inline">\boldsymbol {\hat p}</math> from the anchor node positions <math display="inline">\boldsymbol p_i</math> and the (squared) distances <math display="inline">d_i</math>.<math display="block">d_i^2 =
\left\|
\boldsymbol p_i - \boldsymbol {\hat p}
\right\|_2^2
=
\left\|
\boldsymbol p_i
\right\|_2^2
+
\left\|
\boldsymbol {\hat p}
\right\|_2^2
-
2 \boldsymbol p_i^\text{T} \boldsymbol {\hat p}</math> A somewhat unpleasant thing in the equation above is the term <math display="inline">\left\|
\boldsymbol {\hat p}
\right\|_2^2</math>. To get rid of this term, one may subtract the mean from both sides of the equation <math display="inline">d_i^2
=
\left\|
\boldsymbol p_i
\right\|_2^2
+
\left\|
\boldsymbol {\hat p}
\right\|_2^2
-
2 \boldsymbol p_i^\text{T} \boldsymbol {\hat p}</math>.<math display="block">d_i^2
-
\frac{1}{N}
\sum_{k=1}^N d_k^2
=
\left\|
\boldsymbol p_i
\right\|_2^2
+
\left\|
\boldsymbol {\hat p}
\right\|_2^2
-
2 \boldsymbol p_i^\text{T} \boldsymbol {\hat p}
-
\frac{1}{N}
\sum_{k=1}^N
\left(
\left\|
\boldsymbol p_k
\right\|_2^2
+
\left\|
\boldsymbol {\hat p}
\right\|_2^2
-
2 \boldsymbol p_k^\text{T} \boldsymbol {\hat p}
\right)</math> The key is, that <math display="inline">\left\|
\boldsymbol {\hat p}
\right\|_2^2</math> does not depend on <math display="inline">k</math> in the sum on the right-hand side. And therefore <math>\frac{1}{N}
\sum_{k=1}^N
\left\|
\boldsymbol {\hat p}
\right\|_2^2
=
\left\|
\boldsymbol {\hat p}
\right\|_2^2</math>. Hence, <math display="inline">\left\|
\boldsymbol {\hat p}
\right\|_2^2</math> is removed from the right-hand side.<math display="block">d_i^2
-
\frac{1}{N}
\sum_{k=1}^N d_k^2
=
\left\|
\boldsymbol p_i
\right\|_2^2
-
2 \boldsymbol p_i^\text{T} \boldsymbol {\hat p}
-
\frac{1}{N}
\sum_{k=1}^N
\left\|
\boldsymbol p_k
\right\|_2^2
+
\frac{1}{N}
\sum_{k=1}^N
2 \boldsymbol p_k^\text{T} \boldsymbol {\hat p}
</math> This can be rearranged as follows.<math display="block">\underbrace{
d_i^2
-
\frac{1}{N}
\sum_{k=1}^N d_k^2
-
\left\|
\boldsymbol p_i
\right\|_2^2
+
\frac{1}{N}
\sum_{k=1}^N
\left\|
\boldsymbol p_k
\right\|_2^2
}_{b_i}
=
{\underbrace{
2
\cdot
\left(
\frac{1}{N}
\sum_{k=1}^N
\boldsymbol p_k
-
\boldsymbol p_i
\right)}_{\boldsymbol a_i^\text{T}
\boldsymbol{\hat p}
</math> Using the abbreviations defined above, the equation for the <math display="inline">i</math>-th anchor node becomes <math>b_i = 2 \boldsymbol a_i^\text{T} \boldsymbol{\hat p}
</math>. By incorporating all anchor nodes, the multilateration problem can be written as single equation with the vector <math>\boldsymbol b = \left[
b_1, \dots, b_N
\right]^\mathrm{T}
</math> and the matrix <math>\boldsymbol A = \left[
\boldsymbol a_1, \dots, \boldsymbol a_N
\right]^\text{T}
</math>. <math display="block">\boldsymbol A \boldsymbol{\hat p} = \boldsymbol b
</math>The final task is to solve this equation for position <math display="inline">\boldsymbol {\hat p} </math> of the target node. A usual choice is the least squares solution:<math display="block">\boldsymbol{\hat p} =
\left(
\boldsymbol A^\text{T} \boldsymbol A
\right)^\text{-1}
\boldsymbol A^\text{T}
\boldsymbol b
</math>
Iterative algorithm
This algorithm can be used if a initial rough estimate of the target node's position <math display="inline">\boldsymbol {\hat p}</math> is available. This initial estimate is used to iteratively compute a more accurate estimate of <math display="inline">\boldsymbol {\hat p}</math>. For this, a Gauss–Newton algorithm is used with the following update equation.<math display="block">\boldsymbol{\hat p}^{(k+1)}
=
\boldsymbol{\hat p}^{(k)}
-
\left(
{\boldsymbol{J}^{(k)^\text{T} \boldsymbol{J}^{(k)}
\right)^{\text{-1
{\boldsymbol{J}^{(k)^\text{T}
\boldsymbol{f}^{(k)}</math>In this equation, <math display="inline">\boldsymbol{\hat p}^{(k)}</math> is the estimate of <math display="inline">\boldsymbol {\hat p}</math> computed in the last iteration. The initial rough estimate is <math display="inline">\boldsymbol{\hat p}^{(0)}</math>. After a refinement step using the foruma above, <math display="inline">\boldsymbol{\hat p}^{(k+1)}</math> is the new refined estimate of <math display="inline">\boldsymbol {\hat p}</math>. <math display="inline">\boldsymbol{J}^{(k)}</math> is the Jacobian matrix (see below). In each update step, the algorithm seeks to minimize the error <math display="inline">\left\| \boldsymbol{f}^{(k)} \right\|_2</math> define by the error vector <math display="inline">\boldsymbol{f}^{(k)}</math>.<math display="block">\boldsymbol{f}^{(k)}
=
\begin{bmatrix} \Delta_1^{(k)} - d_1 \\ \vdots \\ \Delta_N^{(k)} - d_N \end{bmatrix}</math>This error vector contains the distance <math display="inline">\Delta_i^{(k)}
=
\left\| \boldsymbol p_i - \boldsymbol {\hat p}^{(k)} \right\|_2</math> between all anchor node positions <math display="inline">\boldsymbol p_i</math> and the current estimate <math display="inline">\boldsymbol{\hat p}^{(k)}</math>. The Jacobian matrix <math display="inline">\boldsymbol{J}^{(k)}</math> of <math display="inline">\boldsymbol{f}^{(k)}</math> can be written as follows.<math display="block">\boldsymbol{J}^{(k)}
=
\frac{ \partial\,\boldsymbol{f}^{(k){\partial\,{\boldsymbol{\hat p}^{(k)^\mathrm{T
=
\boldsymbol{D}^{(k)}
\left(
\boldsymbol {1}_N \boldsymbol {\hat p^{(k)^\mathrm{T} - \boldsymbol{P}
\right)</math>Here, <math display="inline">\boldsymbol{D}^{(k)} = \mathrm{diag}\left(\Delta_1^{(k)}, \ldots, \Delta_N^{(k)} \right)</math> is a diagonal matrix of all <math display="inline">\Delta_i^{(k)}</math> and <math>\boldsymbol P =
\begin{bmatrix} \boldsymbol{p}_1 & \dots & \boldsymbol{p}_N \end{bmatrix}^\mathrm{T}</math> is a matrix whose rows are the positions of all anchor nodes. The vector <math>\boldsymbol{1}_N</math> is a column vector of length <math>N</math> that contains only ones.
The algorithm
- Obtain a rough initial estimate <math display="inline">\boldsymbol{\hat p}^{(0)}</math> of the target node's position.
- Set <math display="inline">k=0</math>.
- If <math display="inline">k</math> equals a predefined maximum number iterations, stop the algorithm. In this case, the algorithm did not converge!
- Compute distances <math display="inline">\Delta_i^{(k)}</math> (with <math>i = 1 \ldots N</math>) between anchor positions <math display="inline">\boldsymbol p_i</math> and the current estimate <math display="inline">\boldsymbol{\hat p}^{(k)}</math>.
- Compute the error vector <math display="inline">\boldsymbol{f}^{(k)}</math>.
- If the error <math display="inline">\left\| \boldsymbol{f}^{(k)} \right\|_2</math> is below a prefined threshold, stop the algorithm. Convergence is achieved.
- Compute the Jacobian <math display="inline">\boldsymbol{J}^{(k)}</math>.
- Solve the equation <math display="inline">\boldsymbol{J}^{(k)} \boldsymbol{v}^{(k)} = \boldsymbol{f}^{(k)}</math> for <math display="inline">\boldsymbol{v}^{(k)}</math> using linear least squares method.<br> The algebraic solution is the Moore–Penrose inverse: <math>\boldsymbol{v}^{(k)}
=
\left(
{\boldsymbol{J}^{(k)^\text{T} \boldsymbol{J}^{(k)}
\right)^{\text{-1
{\boldsymbol{J}^{(k)^\text{T}
\boldsymbol{f}^{(k)}</math>
- Compute the updated position estimate: <math display="inline">\boldsymbol{\hat p}^{(k+1)}
=
\boldsymbol{\hat p}^{(k)}
-
\boldsymbol{v}^{(k)}</math>.
- If the distance <math display="inline">\left\| \boldsymbol{\hat p}^{(k+1)} - \boldsymbol{\hat p}^{(k)} \right\|_2</math> between the current and the last estimated target position is below a predefined threshold, stop the algorithm. Convergence is achieved.
- Increase <math display="inline">k</math> by one.
- Go to bullet point 3.
Note:
- This algorithm converges usually within only a few steps.
- The threshold on <math display="inline">\left\| \boldsymbol{f}^{(k)} \right\|_2</math> is not mandatory and can also be left out.
- Step 8 through should be solved numerically instead of using the algebraic solution.
Python implementation
<syntaxhighlight lang="python3" line="1">
def refine_position_estimate(initial_position_guess, anchor_positions, distances, error_threshold, estimate_threshold, max_iterations):
assert initial_position_guess.ndim == 1
assert anchor_positions.ndim == 2
assert initial_position_guess.shape[0] == anchor_positions.shape[0]
P = anchor_positions
p_hat = initial_position_guess.copy()
for iter_idx in range(max_iterations):
delta = np.linalg.norm(P - p_hat[:, None], axis=0)
delta = np.maximum(delta, 1e-12)
f = delta - distances
error = np.linalg.norm(f)
if error <= error_threshold:
print(f"Converged: Error is below threshold: {error}")
break
J = (p_hat[None, :] - P.T)
J /= delta[:, None]
v = np.linalg.lstsq(J, f, rcond=None)[0]
p_hat_diff = np.linalg.norm(v)
if p_hat_diff <= estimate_threshold:
print(f"Converged: Distance between last estimate and current estimate is below threshold: {p_hat_diff}")
break
p_hat -= v
else:
print("WARNING: Algorithm did NOT converge!")
print(f"Number of required iterations: {iter_idx}")
return p_hat</syntaxhighlight>
Example usage
In this example, there are seven anchor nodes with known positions. The distances between the target node and all anchor nodes are also perfectly known. For this example, the algorithm needs only three iterations to achieve the required accuracy.
<syntaxhighlight lang="python3" line="1">
anchor_positions = np.array([
[0.0, 0.0, 0.0],
[40, 25, 75],
[0, 80, 0],
[100, 11, 22],
[0, 45, 87],
[0, 0, 100],
[0, 50, 0]
]).T
true_target_position = np.array([30.0, 40.0, 50.0])
true_distances = np.linalg.norm(anchor_positions - true_target_position[:, None], axis=0)
- An initial rough estimate of the target position.
- This is typically obtained using a (rough) direct estimator or from some prior knowledge.
initial_target_position_estimate = true_target_position + [3, 2, -4]
estimated_target_position = refine_position_estimate_wikpedia(
initial_position_guess=initial_target_position_estimate,
anchor_positions=anchor_positions,
distances=true_distances,
error_threshold=1e-6,
estimate_threshold=1e-6,
max_iterations=1000
)
target_position_error = np.linalg.norm(estimated_target_position - true_target_position)
print()
print(f"True target position: {true_target_position}")
print(f"Initial estimate: {initial_target_position_estimate}")
print(f"estimated target position: {estimated_target_position}")
print(f"Achieved accuracy: {target_position_error:.12f}")
</syntaxhighlight>
Output:
<syntaxhighlight lang="output">
Converged: Error is below threshold: 1.543685171566139e-09
Number of required iterations: 3
True target position: [30. 40. 50.]
Initial estimate: [33. 42. 46.]
estimated target position: [30. 40. 50.]
Achieved accuracy: 0.000000001463
</syntaxhighlight>
Two spherical dimensions, two or more measured spherical ranges
right|thumb|300px|Fig. 3 Example of celestial navigation altitude intercept problem (lines of position are distorted by the map projection)
This is a classic celestial (or astronomical) navigation problem, termed the altitude intercept problem (Fig. 3). It is the spherical geometry equivalent of the trilateration method of surveying (although the distances involved are generally much larger). A solution at sea (not necessarily involving the Sun and Moon) was made possible by the marine chronometer (introduced in 1761) and the discovery of the 'line of position' (LOP) in 1837. The solution method now most taught at universities (e.g., U.S. Naval Academy) employs spherical trigonometry to solve an oblique spherical triangle based on sextant measurements of the 'altitude' of two heavenly bodies. This problem can also be addressed using vector analysis. Historically, graphical techniques – e.g., the intercept method – were employed. These can accommodate more than two measured 'altitudes'. Owing to the difficulty of making measurements at sea, 3 to 5 'altitudes' are often recommended.
As the earth is better modeled as an ellipsoid of revolution than a sphere, iterative techniques may be used in modern implementations. In high-altitude aircraft and missiles, a celestial navigation subsystem is often integrated with an inertial navigation subsystem to perform automated navigation—e.g., U.S. Air Force SR-71 Blackbird and B-2 Spirit.
While intended as a 'spherical' pseudo range multilateration system, Loran-C has also been used as a 'spherical' true-range multilateration system by well-equipped users (e.g., Canadian Hydrographic Service). (in addition to the multilateration solution algorithm), which enables measurements collected at different times to be compared and averaged in some manner; and (b) utilize an iterative solution algorithm, as they (b1) admit varying numbers of measurements (including redundant measurements) and (b2) inherently have an initial guess each time the solution algorithm is invoked.
Hybrid multilateration systems
Hybrid multilateration systems – those that are neither true-range nor pseudo range systems – are also possible. For example, in Fig. 1, if the circle centers are shifted to the left so that C1 is at <math>x_1^\prime = - \tfrac{1}{2} U, y_1^\prime = 0</math> and C2 is at <math>x_2^\prime = \tfrac{1}{2} U, y_2^\prime = 0</math> then the point of interest P is at
: <math> \begin{align}
x^\prime & = \frac { (r_1^\prime + r_2^\prime)(r_1^\prime - r_2^\prime) } {2 U} \\[4pt]
y^\prime & = \pm \frac { \sqrt{ (r_1^\prime + r_2^\prime)^2 - U^2 } \sqrt{ U^2 - (r_1^\prime - r_2^\prime)^2 } } {2 U}
\end{align} </math>
This form of the solution explicitly depends on the sum and difference of <math>r_1^\prime</math> and <math>r_2^\prime</math> and does not require 'chaining' from the <math>x^\prime</math>-solution to the <math>y^\prime</math>-solution. It could be implemented as a true-range multilateration system by measuring <math>r_1^\prime</math> and <math>r_2^\prime</math>.
However, it could also be implemented as a hybrid multilateration system by measuring <math>r_1^\prime + r_2^\prime</math> and <math>r_1^\prime - r_2^\prime</math> using different equipment – e.g., for surveillance by a multistatic radar with one transmitter and two receivers (rather than two monostatic radars). While eliminating one transmitter is a benefit, there is a countervailing 'cost': the synchronization tolerance for the two stations becomes dependent on the propagation speed (typically, the speed of light) rather that the speed of point P, in order to accurately measure both <math>r_1^\prime \pm r_2^\prime</math>.
While not implemented operationally, hybrid multilateration systems have been investigated for aircraft surveillance near airports and as a GPS navigation backup system for aviation.
Preliminary and final computations
thumb|Fig. 4 2-D true-range multi-lateration (trilateration) system ranging measurements
The position accuracy of a true-range multilateration system—e.g., accuracy of the <math>(x,y)</math> coordinates of point P in Fig. 1 -- depends upon two factors: (1) the range measurement accuracy, and (2) the geometric relationship of P to the system's stations C1 and C2. This can be understood from Fig. 4. The two stations are shown as dots, and BLU denotes baseline units. (The measurement pattern is symmetric about both the baseline and the perpendicular bisector of the baseline, and is truncated in the figure.) As is commonly done, individual range measurement errors are taken to be independent of range, statistically independent and identically distributed. This reasonable assumption separates the effects of user-station geometry and range measurement errors on the error in the calculated <math>(x,y)</math> coordinates of P. Here, the measurement geometry is simply the angle at which two circles cross—or equivalently, the angle between lines P-C1 and P-C2. When point P- is not on a circle, the error in its position is approximately proportional to the area bounded by the nearest two blue and nearest two magenta circles.
Without redundant measurements, a true-range multilateration system can be no more accurate than the range measurements, but can be significantly less accurate if the measurement geometry is not chosen properly. Accordingly, some applications place restrictions on the location of point P. For a 2-D Cartesian (trilateration) situation, these restrictions take one of two equivalent forms:
- The allowable interior angle at P between lines P-C1 and P-C2: The ideal is a right angle, which occurs at distances from the baseline of one-half or less of the baseline length; maximum allowable deviations from the ideal 90 degrees may be specified.
- The horizontal dilution of precision (HDOP), which multiplies the range error in determining the position error: For two dimensions, the ideal (minimum) HDOP is the square root of 2 (<math>\sqrt{2} \approx 1.414</math>), which occurs when the angle between P-C1 and P-C2 is 90 degrees; a maximum allowable HDOP value may be specified. (Here, equal HDOPs are simply the locus of points in Fig. 4 having the same crossing angle.)
thumb|Fig. 5 HDOP contours for a 2-D true-range multilateration (trilateration) system
Planning a true-range multilateration navigation or surveillance 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 service volume (three dimensions). Fig. 5 shows horizontal DOPs (HDOPs) for a 2-D, two-station true-range multilateration system. HDOP is infinite along the baseline and its extensions, as only one of the two dimensions is actually measured. A user of such a system should be roughly broadside of the baseline and within an application-dependent range band. For example, for DME/DME navigation fixes by aircraft, the maximum HDOP permitted by the U.S. FAA is twice the minimum possible value, or 2.828, Generally, emphasis is placed on the effects of range measurement errors, rather than on the effects of algorithm numerical errors.
Applications
- Land surveying using the trilateration method
- Aerial surveying
- Maritime archeology surveying
- DME/DME RNAV aircraft navigation
- Multiple radar integration (e.g., FAA ERAM)
- Celestial navigation using the altitude intercept method
- Intercept method—Graphical solution to the altitude intercept problem
- Calibrating laser interferometers
- SHORAN, Oboe, Gee-H — Aircraft guidance systems developed for 'blind' bombing
- JTIDS (Joint Tactical Information Distribution System) U.S./NATO system that (among other capabilities) locates participants in a network using inter-participant ranges
- USAF SR-71 Blackbird aircraft — Employs astro-inertial navigation
- USAF B-2 Spirit aircraft — Employs astro-inertial navigation
- Experimental Loran-C technique