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").Accuracy limitations of range–range (spherical) multilateration systems, Harry B. Lee, Massachusetts Institute of Technology, Lincoln Laboratory, Report Number: DOT/TSC-RA-3-8-(1) (Technical note 1973-43), Oct. 11, 1973 Energy waves may be involved in determining range, but are not required.
True-range multilateration is both a mathematical topic and an applied technique used in several fields. A practical application involving a fixed location occurs in surveying. 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."Rho-Rho Loran-C Combined with Satellite Navigation for Offshore Surveys". S.T. Grant, International Hydrographic Review, undated
Solution methods
True-range multilateration algorithms may be partitioned based on problem space dimension (generally, two or three), problem space geometry (generally, Cartesian or spherical) and presence of redundant measurements (more than the problem space dimension). Any pseudo-range multilateration algorithm can be specialized for use with true-range multilateration.
Two Cartesian dimensions, two measured slant ranges (trilateration)
An analytic solution has likely been known for over 1,000 years, and is given in several texts. Moreover, one can easily adapt algorithms for a three dimensional Cartesian space.
The simplest algorithm employs analytic geometry and a station-based coordinate frame. Thus, consider the circle centers (or stations) C1 and C2 in Fig. 1 which have known coordinates (e.g., have already been surveyed) and thus whose separation is known. The figure 'page' contains C1 and C2. If a third 'point of interest' P (e.g., a vehicle or another point to be surveyed) is at unknown point , then Pythagoras's theorem yields
Thus,
Note that has two values (i.e., solution is ambiguous); this is usually not a problem.
While there are many enhancements, Equation is the most fundamental true-range multilateration relationship. Aircraft DME/DME navigation and the trilateration method of surveying are examples of its application. During World War II Oboe and during the Korean War SHORAN used the same principle to guide aircraft based on measured ranges to two ground stations. SHORAN was later used for off-shore oil exploration and for aerial surveying. The Australian Aerodist aerial survey system utilized 2-D Cartesian true-range multilateration.Adastra Aerial Surveys retrieved Jan. 22, 2019. 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."The Nature of Geographic Information: Trilateration", Pennsylvania State Univ., 2018. 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 and relate to the same position of P. When P is a vehicle, then typically and 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
There are multiple algorithms that solve the 3-D Cartesian true-range multilateration problem directly (i.e., in closed-form) – e.g., Fang."Trilateration and extension to global positioning system navigation", B.T. Fang, Journal of Guidance, Control, and Dynamics, vol. 9 (1986), pp 715–717. Moreover, one can adopt closed-form algorithms developed for pseudo range multilateration."Closed-form Algorithms in Mobile Positioning: Myths and Misconceptions", Niilo Sirola, Proceedings of the 7th Workshop on Positioning, Navigation and Communication 2010 (WPNC'10), March 11, 2010. Bancroft's algorithm"An Algebraic Solution of the GPS Equations", Stephen Bancroft, IEEE Transactions on Aerospace and Electronic Systems, Volume: AES-21, Issue: 7 (Jan. 1985), pp 56–59. (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 , then Pythagoras's theorem yields the slant ranges between P and the sphere centers:
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.