This article needs additional citations for verification .(June 2017) |
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"). [1] [2] 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. [3] [4] 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.
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.
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 and/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:
This section needs expansion. You can help by adding to it. (June 2017) |
True-range multilateration algorithms may be partitioned based on
Any pseudo-range multilateration algorithm can be specialized for use with true-range multilateration.
An analytic solution has likely been known for over 1,000 years, and is given in several texts. [6] 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,
(1) |
Note that has two values (i.e., solution is ambiguous); this is usually not a problem.
While there are many enhancements, Equation 1 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. [7] 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. [8] 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.
There are multiple algorithms that solve the 3-D Cartesian true-range multilateration problem directly (i.e., in closed-form) – e.g., Fang. [9] Moreover, one can adopt closed-form algorithms developed for pseudo range multilateration. [10] [6] Bancroft's algorithm [11] (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:
(2) |
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. [12] Integrating range measurement from three or more radars (e.g., FAA's ERAM) is a 3-D aircraft surveillance application. 3-D true-range multilateration has been used on an experimental basis with GPS satellites for aircraft navigation. [5] 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. [13] 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. [14] Accurately measuring the altitude of aircraft during approach and landing requires many ground stations along the flight path.
This is a classic celestial (or astronomical) navigation problem, termed the altitude intercept problem (Fig. 3). It's 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. [15] [16] This problem can also be addressed using vector analysis. [17] 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. [18] 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). [2] This enabled the coverage area of a Loran-C station triad to be extended significantly (e.g., doubled or tripled) and the minimum number of available transmitters to be reduced from three to two. In modern aviation, slant ranges rather than spherical ranges are more often measured; however, when aircraft altitude is known, slant ranges are readily converted to spherical ranges. [6]
When there are more range measurements available than there are problem dimensions, either from the same C1 and C2 (or C1, C2 and C3) stations, or from additional stations, at least these benefits accrue:
The iterative Gauss–Newton algorithm for solving non-linear least squares (NLLS) problems is generally preferred when there are more 'good' measurements than the minimum necessary. An important advantage of the Gauss–Newton method over many closed-form algorithms is that it treats range errors linearly, which is often their nature, thereby reducing the effect of range errors by averaging. [10] The Gauss–Newton method may also be used with the minimum number of measured ranges. Since it is iterative, the Gauss–Newton method requires an initial solution estimate.
In 3-D Cartesian space, a fourth sphere eliminates the ambiguous solution that occurs with three ranges, provided its center is not co-planar with the first three. In 2-D Cartesian or spherical space, a third circle eliminates the ambiguous solution that occurs with two ranges, provided its center is not co-linear with the first two.
This article largely describes 'one-time' application of the true-range multilateration technique, which is the most basic use of the technique. With reference to Fig. 1, the characteristic of 'one-time' situations is that point P and at least one of C1 and C2 change from one application of the true-range multilateration technique to the next. This is appropriate for surveying, celestial navigation using manual sightings, and some aircraft DME/DME navigation.
However, in other situations, the true-range multilateration technique is applied repetitively (essentially continuously). In those situations, C1 and C2 (and perhaps Cn, n = 3,4,...) remain constant and P is the same vehicle. Example applications (and selected intervals between measurements) are: multiple radar aircraft surveillance (5 and 12 seconds, depending upon radar coverage range), aerial surveying, Loran-C navigation with a high-accuracy user clock (roughly 0.1 seconds), and some aircraft DME/DME navigation (roughly 0.1 seconds). Generally, implementations for repetitive use: (a) employ a 'tracker' algorithm [19] (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 – 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 and C2 is at then the point of interest P is at
This form of the solution explicitly depends on the sum and difference of and and does not require 'chaining' from the -solution to the -solution. It could be implemented as a true-range multilateration system by measuring and .
However, it could also be implemented as a hybrid multilateration system by measuring and 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 .
While not implemented operationally, hybrid multilateration systems have been investigated for aircraft surveillance near airports and as a GPS navigation backup system for aviation. [20]
This section needs expansion. You can help by adding to it. (June 2018) |
The position accuracy of a true-range multilateration system—e.g., accuracy of the 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 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:
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). [21] [22] 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, [23] which limits the maximum usage range (which occurs along the baseline bisector) to 1.866 times the baseline length. (The plane containing two DME ground stations and an aircraft in not strictly horizontal, but usually is nearly so.) Similarly, surveyors select point P in Fig. 1 so that C1-C2-P roughly form an equilateral triangle (where HDOP = 1.633).
Errors in trilateration surveys are discussed in several documents. [24] [25] Generally, emphasis is placed on the effects of range measurement errors, rather than on the effects of algorithm numerical errors.
Navigation and surveillance systems typically involve vehicles and require that a government entity or other organization deploy multiple stations that employ a form of radio technology (i.e., utilize electromagnetic waves). The advantages and disadvantages of employing true-range multilateration for such a system are shown in the following table.
Advantages | Disadvantages |
---|---|
|
|
True-range multilateration is often contrasted with (pseudo range) multilateration, as both require a form of user ranges to multiple stations. Complexity and cost of user equipage is likely the most important factor in limiting use of true-range multilateration for vehicle navigation and surveillance. Some uses are not the original purpose for system deployment – e.g., DME/DME aircraft navigation.
The Global Positioning System (GPS), originally Navstar GPS, is a satellite-based radio navigation system owned by the United States government and operated by the United States Space Force. It is one of the global navigation satellite systems (GNSS) that provide geolocation and time information to a GPS receiver anywhere on or near the Earth where there is an unobstructed line of sight to four or more GPS satellites. It does not require the user to transmit any data, and operates independently of any telephone or Internet reception, though these technologies can enhance the usefulness of the GPS positioning information. It provides critical positioning capabilities to military, civil, and commercial users around the world. Although the United States government created, controls and maintains the GPS system, it is freely accessible to anyone with a GPS receiver.
Supervised learning (SL) is a paradigm in machine learning where input objects and a desired output value train a model. The training data is processed, building a function that maps new data to expected output values. An optimal scenario will allow for the algorithm to correctly determine output values for unseen instances. This requires the learning algorithm to generalize from the training data to unseen situations in a "reasonable" way. This statistical quality of an algorithm is measured through the so-called generalization error.
In navigation, dead reckoning is the process of calculating the current position of a moving object by using a previously determined position, or fix, and incorporating estimates of speed, heading, and elapsed time. The corresponding term in biology, to describe the processes by which animals update their estimates of position or heading, is path integration.
Radio navigation or radionavigation is the application of radio waves to determine a position of an object on the Earth, either the vessel or an obstruction. Like radiolocation, it is a type of radiodetermination.
In geodesy, the figure of the Earth is the size and shape used to model planet Earth. The kind of figure depends on application, including the precision needed for the model. A spherical Earth is a well-known historical approximation that is satisfactory for geography, astronomy and many other purposes. Several models with greater accuracy have been developed so that coordinate systems can serve the precise needs of navigation, surveying, cadastre, land use, and various other concerns.
A longest common subsequence (LCS) is the longest subsequence common to all sequences in a set of sequences. It differs from the longest common substring: unlike substrings, subsequences are not required to occupy consecutive positions within the original sequences. The problem of computing longest common subsequences is a classic computer science problem, the basis of data comparison programs such as the diff
utility, and has applications in computational linguistics and bioinformatics. It is also widely used by revision control systems such as Git for reconciling multiple changes made to a revision-controlled collection of files.
In aviation, distance measuring equipment (DME) is a radio navigation technology that measures the slant range (distance) between an aircraft and a ground station by timing the propagation delay of radio signals in the frequency band between 960 and 1215 megahertz (MHz). Line-of-visibility between the aircraft and ground station is required. An interrogator (airborne) initiates an exchange by transmitting a pulse pair, on an assigned 'channel', to the transponder ground station. The channel assignment specifies the carrier frequency and the spacing between the pulses. After a known delay, the transponder replies by transmitting a pulse pair on a frequency that is offset from the interrogation frequency by 63 MHz and having specified separation.
Dilution of precision (DOP), or geometric dilution of precision (GDOP), is a term used in satellite navigation and geomatics engineering to specify the error propagation as a mathematical effect of navigation satellite geometry on positional measurement precision.
The pseudorange is the pseudo distance between a satellite and a navigation satellite receiver, for instance Global Positioning System (GPS) receivers.
In Euclidean plane geometry, Apollonius's problem is to construct circles that are tangent to three given circles in a plane (Figure 1). Apollonius of Perga posed and solved this famous problem in his work Ἐπαφαί ; this work has been lost, but a 4th-century AD report of his results by Pappus of Alexandria has survived. Three given circles generically have eight different circles that are tangent to them (Figure 2), a pair of solutions for each way to divide the three given circles in two subsets.
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.
Acoustic location is a method of determining the position of an object or sound source by using sound waves. Location can take place in gases, liquids, and in solids.
Augmentation of a global navigation satellite system (GNSS) is a method of improving the navigation system's attributes, such as precision, reliability, and availability, through the integration of external information into the calculation process. There are many such systems in place, and they are generally named or described based on how the GNSS sensor receives the external information. Some systems transmit additional information about sources of error, others provide direct measurements of how much the signal was off in the past, while a third group provides additional vehicle information to be integrated in the calculation process.
Time of arrival is the absolute time instant when a radio signal emanating from a transmitter reaches a remote receiver. The time span elapsed since the time of transmission is the time of flight . Time difference of arrival (TDOA) is the difference between TOAs.
Wi-Fi positioning system is a geolocation system that uses the characteristics of nearby Wi‑Fi access points to discover where a device is located.
A long baseline (LBL) acoustic positioning system is one of three broad classes of underwater acoustic positioning systems that are used to track underwater vehicles and divers. The other two classes are ultra short baseline systems (USBL) and short baseline systems (SBL). LBL systems are unique in that they use networks of sea-floor mounted baseline transponders as reference points for navigation. These are generally deployed around the perimeter of a work site. The LBL technique results in very high positioning accuracy and position stability that is independent of water depth. It is generally better than 1-meter and can reach a few centimeters accuracy. LBL systems are generally employed for precision underwater survey work where the accuracy or position stability of ship-based positioning systems does not suffice.
An inertial navigation system is a navigation device that uses motion sensors (accelerometers), rotation sensors (gyroscopes) and a computer to continuously calculate by dead reckoning the position, the orientation, and the velocity of a moving object without the need for external references. Often the inertial sensors are supplemented by a barometric altimeter and sometimes by magnetic sensors (magnetometers) and/or speed measuring devices. INSs are used on mobile robots and on vehicles such as ships, aircraft, submarines, guided missiles, and spacecraft. Older INS systems generally used an inertial platform as their mounting point to the vehicle and the terms are sometimes considered synonymous.
Satellite navigation solution for the receiver's position (geopositioning) involves an algorithm. In essence, a GNSS receiver measures the transmitting time of GNSS signals emitted from four or more GNSS satellites and these measurements are used to obtain its position and reception time.
In surveying, triangulation is the process of determining the location of a point by measuring only angles to it from known points at either end of a fixed baseline by using trigonometry, rather than measuring distances to the point directly as in trilateration. The point can then be fixed as the third point of a triangle with one known side and two known angles.
Trilateration is the use of distances for determining the unknown position coordinates of a point of interest, often around Earth (geopositioning). When more than three distances are involved, it may be called multilateration, for emphasis.