Multilateration

From Wikipedia, the free encyclopedia
  (Redirected from Time difference of arrival)
Jump to navigation Jump to search

Multilateration is a navigation and surveillance technique based on the measurement of the times of arrival (TOAs) of energy waves (radio, acoustic, seismic, etc.) having a known propagation speed. The time origin for the TOAs is arbitrary. (By the reciprocity principle, any conceptual method that can be used for navigation can also be used for surveillance, and vice versa.) For surveillance, a subject of interest – in cooperative surveillance, often a vehicle – transmits to multiple receiving stations having synchronized 'clocks'. For navigation, multiple synchronized stations transmit to a user receiver. To find the coordinates of a user in n dimensions (typically, n = 2 or n = 3), at least n + 1 TOAs must be measured. Multilateration systems are also called hyperbolic systems, for reasons discussed below.

One can view a multilateration system as measuring n + 1 TOAs, and then either: (a) determining the time of transmission (TOT) and n user coordinates; or (b) ignoring the TOT and forming n time difference of arrivals (TDOAs), which are used to find n user coordinates. Systems and algorithms have been developed for both concepts. The latter (b) is addressed first, as it was the first implemented (roughly, pre-1975); in practice, those systems largely determine a user/vehicle location in two dimensions. A TDOA, when multiplied by the propagation speed, is the difference in the true ranges between the user and the two stations involved (i.e., the unknown TOT cancels). The former (a) is addressed second (it was implemented, roughly, post-1975). In practice, TOT/non-TDOA systems largely determine a user/vehicle location in three dimensions. A TOA, when multiplied by the propagation speed, is termed a pseudo range. However, there is no conceptual reason that TDOA or TOT algorithms should be linked to a number of dimensions.

For surveillance, a TDOA system determines the difference in the subject of interest's distance to pairs of stations at known fixed locations. For one station pair, the distance difference results in an infinite number of possible subject locations that satisfy the TDOA. When these possible locations are plotted, they form a hyperbolic curve. To locate the exact subject's position along that curve, multilateration relies on multiple TDOAs. For two dimensions, a second TDOA, involving a different pair of stations (typically one station is one of the first two, and one station is new), will produce a second curve, which intersects with the first. When the two curves are compared, a small number of possible user locations (typically, one or two) are revealed. Multilateration surveillance can be performed without the cooperation or even knowledge of the subject being surveilled.

TDOA multilateration was a common technique in earth-fixed radio navigation systems, where it was known as hyperbolic navigation. These systems are relatively undemanding of the user receiver, as its 'clock' can have low-performance/cost and is usually unsynchronized with station time.[1] The difference in received signal timing can even be measured visibly using an oscilloscope. This formed the basis of a number of widely used navigation systems starting in World War II with the British Gee system and several similar systems deployed over the next few decades. The introduction of the microprocessor greatly simplified operation, increasing popularity during the 1980s. The most popular TDOA hyperbolic navigation system was Loran-C, which was used around the world until the system was shut down in 2010. The widespread use of satellite navigation systems like the Global Positioning System (GPS) have made TDOA systems largely redundant, and most have been decommissioned. GPS is also a hyperbolic navigation system, but also determines the TOT in order to provide accurate time.

Multilateration should not be confused with any of:

All of these systems (and combinations of them) are commonly used with radio navigation and surveillance systems.

Principle[edit]

Prior to deployment of GPS and other global navigation satellite systems (GNSSs), multilateration systems were often defined as TDOA systems – i.e., systems that form TDOAs as the first step in processing a set of measured TOAs. As result of deployment of GNSSs, two issues arose: (a) What system type are they (multilateration, trilateration, or another)? (b) What are the defining characteristic(s) of a multilateration system?

  • The technical answer to (a) has long been known: GPS and other GNSSs are multilateration navigation systems with moving transmitters.[2][3] However, because the transmitters are synchronized not only each other but a time standard, GNSS receivers are also sources of time, provided they compute TOT. This requires different solution algorithms than older TDOA algorithms. Thus, a case can also be made that GNSSs are a separate category of systems – e.g., hyperbolic navigation and timing systems or hyperbolic navigation with moving transmitters.
  • There is no authoritative answer to (b). However, a reasonable two-part answer is (1) a system whose use only involves measurement of TOAs or (if the propagation speed is accounted for) only pseudo ranges; and (2) a system whose station clocks must be synchronized. This definition includes GNSSs as well as TDOA systems.

Multilateration is commonly used in civil and military applications to either (a) locate a vehicle (aircraft, ship or car/truck/bus) by measuring the TOAs of a signal from the vehicle at multiple stations having known coordinates and accurate, synchronized 'clocks' (surveillance application) or (b) enable the vehicle to locate itself relative to multiple transmitters at known locations (stations) and having synchronized clocks using their signal TOAs (navigation application). When the stations are fixed to the earth and do not provide time, the measured TOAs are almost always used to form one fewer TDOAs.

For vehicles, surveillance or navigation stations (including required associated infrastructure) are often provided by government agencies. However, privately-funded entities have also been (and are) station/system providers – e.g., wireless phone systems. Multilateration is also used by the scientific and military communities for non-cooperative surveillance.

Surveillance application: locating a transmitter from multiple receiver sites[edit]

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.

Fig 1. A two-sheeted hyperboloid

In simple terms, with two receivers at known locations, an emitter can be located onto one hyperboloid.[4] 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. Extended Kalman filters are used for improving the individual signal timings. 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.[5]

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.

Navigation application: locating a receiver from multiple transmitter sites[edit]

Multilateration can also be used by a single receiver to locate itself, by measuring signals emitted from synchronized transmitters at known locations (termed stations). At least three emitters are needed for two-dimensional navigation; at least four emitters are needed for three-dimensional navigation. For expository purposes, the emitters may be regarded as each broadcasting pulses at exactly the same time on separate frequencies (to avoid interference). In this situation, the receiver measures the TOAs of the pulses. In TDOA systems, the TOAs are differenced and multiplied by the speed of propagation to create true range differences. In GNSS systems, different algorithms are used that implicitly form TDOAs but also compute TOT.

In operational systems, several methods have been implemented to avoid self-interference. A historic example is the British Decca system, developed during World War II. Decca used the phase-difference of three transmitters. Loran-C, introduced in the late 1950s, used time offset transmissions. A current example is the Global Positioning System (GPS). All GPS satellites broadcast on the same carrier frequency, which is modulated by different pseudorandom codes.

Another complication occurs when the transmitters are moving along known trajectories, which is the situation for GNSSs. This requires that the satellites broadcast their trajectory information.

Advantages and disadvantages[edit]

Advantages Disadvantages
Low user equipage cost – A cooperative surveillance user only needs a transmitter. A navigation user only needs a receiver having a basic 'clock'. Station locations – Stations must nearly surround the service area
Accuracy – Avoids the ‘turn-around’ error inherent in many two-way ranging systems Station count – Requires one more station than a system based on true ranges and often two more than a system that measures range and azimuth
Small stations – Avoids use of the large antennas needed for measuring angles Station synchronization and, for surveillance, inter-station communications are required
For navigation, number of users is unlimited (users only receive) Stations may require power and communications where not available
Uncooperative and undetected surveillance are possible For surveillance, users may mutually interfere (generally requires pulsed transmissions)
Viable over great distances (e.g., satellite navigation) For navigation, stations must transmit effectively simultaneously but not mutually interfere

Multilateration surveillance was used during World War I to locate the source of artillery fire using sound waves. Longer distance radio-based navigation systems became viable during World War II, with the advancement of radio technologies. The development of atomic clocks for synchronizing widely separated stations was instrumental in the development of the GPS and other GNSSs. Owing to its high accuracy at low cost of user equipage, today multilateration is the concept most often selected for new navigation and surveillance systems.

Measurement geometry and related factors[edit]

Rectangular/Cartesian coordinates[edit]

Geometry of spherical waves emanating from an emitter and passing through several receivers.
Fig 2. TDOA geometry.

Consider an emitter (E in Figure 2) at an unknown location vector

which we wish to locate. The source is within range of N + 1 receivers at known locations

The subscript m refers to any one of the receivers:

0 ≤ mN

The distance (Rm) from the emitter to one of the receivers in terms of the coordinates is

 

 

 

 

(1)

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

 

 

 

 

(2)

Spherical coordinates[edit]

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[6] and Omega[7] are examples of systems that utilize spherical ranges. When a spherical model for the earth is satisfactory, the simplest expression for the central angle (sometimes termed the geocentric angle) between vehicle v and station m is

Here: latitudes are denoted by φ; longitudes are denoted by λ; and λvm = λv − λm. Alternative, better numerically behaved equivalent expressions, can be found in great-circle navigation.

The distance Rm from the vehicle to station m is along a great circle will then be

Here RE is the assumed radius of the earth and is expressed in radians.

Time of transmission (user clock offset or bias)[edit]

Multilateration systems measure n + 1 TOAs in order to compute the user's location in n dimensions. It's possible to also compute the transmitter(s) time of transmission (TOT) in the clock time scale used to measure the TOAs. 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 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: (1) TOT as known to the user receiver provides 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. However, user receivers are usually not synchronized with 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 (UTC) 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.[8]

TOA adjustments[edit]

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 along all signal paths. This is equivalent to assuming that the propagation medium is homogeneous. However, that is not always sufficiently true; some paths may involve unacceptable propagation delays due to inhomogeneities in the medium. Accordingly, to improve solution accuracy, some systems adjust (generally, move to an earlier time) measured TOAs to account for known propagation delays. Thus, 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 variations in the conductivity of soil.

Calculating the time difference in a TDOA system[edit]

Fig 3a. Pulse Signal
Fig 3b. Wide-band Signal
Fig 3c. Narrow-band Signal
Examples of measuring time difference with cross correlation.

The basic measurements are the TOAs of multiple signals () at the vehicle (navigation) or at the stations (surveillance). The distance in equation 1 is the wave speed () times transit time, which is unknown, as the time of transmission is not known. A TDOA multilateration system calculates the time differences () of a wavefront touching each receiver. The TDOA equation for receivers m and 0 is

 

 

 

 

(3)

The quantity is often termed a pseudo range. It differs from the true range between the vehicle and station by an offset or bias which is the same for every station. Differencing two pseudo range yields the difference of two true ranges.

Figure 3a is a simulation of a pulse waveform recorded by receivers and . The spacing between , and is such that the pulse takes 5 time units longer to reach than . The units of time in Figure 3 are arbitrary. The following table gives approximate time scale units for recording different types of waves.

Type of wave Material Time units
Acoustic Air 1 millisecond
Acoustic Water 1/2 millisecond
Acoustic Rock 1/10 millisecond
Electromagnetic Vacuum, air 1 nanosecond

The red curve in Figure 3a is the cross-correlation function . The cross correlation function slides one curve in time across the other and returns a peak value when the curve shapes match. The peak at time = 5 is a measure of the time shift between the recorded waveforms, which is also the value needed for Equation 3.

Figure 3b is the same type of simulation for a wide-band waveform from the emitter. The time shift is 5 time units because the geometry and wave speed is the same as the Figure 3a example. Again, the peak in the cross correlation occurs at .

Figure 3c is an example of a continuous, narrow-band waveform from the emitter. The cross correlation function shows an important factor when choosing the receiver geometry. There is a peak at Time = 5 plus every increment of the waveform period. To get one solution for the measured time difference, the largest space between any two receivers must be closer than one wavelength of the emitter signal. Some systems, such as the LORAN C and Decca mentioned at earlier (recall the same math works for moving receiver & multiple known transmitters), use spacing larger than 1 wavelength and include equipment, such as a Phase Detector, to count the number of cycles that pass by as the emitter moves. This only works for continuous, narrow-band waveforms because of the relation between phase (), frequency (ƒ) and time (T)

The phase detector will see variations in frequency as measured phase noise, which will be an uncertainty that propagates into the calculated location. If the phase noise is large enough, the phase detector can become unstable.

Solution algorithms[edit]

Overview[edit]

First, assume that the station locations are known as a function of time. For TDOA systems, the stations are fixed to the earth and their locations are surveyed. Satellite systems follow well-defined orbits and broadcast orbital information. 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 values (x,y,z). The system must then solve for the unknown user (often, vehicle) location in real time. Civilian air traffic control multilateration systems use the Mode C SSR transponder message to find an aircraft's altitude. Three or more receivers at known locations are used to find the other two dimensions—either (x,y) for an airport application, or latitude and longitude for larger areas.

Steven Bancroft was apparently the first to publish an algebraic solution to the problem of locating a user (vehicle) and the common TOT using only TOA measurements involving four transmitters.[9] Bancroft's algorithm, as do many, reduces the problem to the solution of a quadratic equation, and yields the three Cartesian coordinates of the receiver as well as the common time of signal transmissions. Other, comparable solutions and extensions were subsequently developed.[10][11][12][13][8] The latter reference provides the solution for locating an aircraft with known altitude using TOA measurements at 3 receivers.

When there are more TOA measurements than unknown quantities – including the common time/range offset – e.g., 5 or more GPS satellite TOAs, the iterative Gauss–Newton algorithm for solving non-linear least squares (NLLS) problems is generally preferred.[14] An over-determined situation eliminates the possibility of ambiguous and/or extraneous solutions that can occur when only the minimum required number of 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. Since it is iterative, the Gauss–Newton method requires an initial solution estimate.

Multilateration systems employing spherical-range measurements (e.g., Loran-C, Decca) utilized a variety of solution algorithms based on either spherical trigonometry[15] or the Gauss–Newton NLLS iterative method.

Three-dimensional Cartesian solutions[edit]

For Cartesian coordinates, when four TOAs are available and the TOT is needed, Bancroft's[9] or another closed-form (direct) algorithm are one option, even if the stations are moving. When the four stations are stationary and the TOT is not needed, extension of Fang's algorithm (based on DTOAs) to three dimensions is a second option.[8] A third option, and likely the most utilized in practice, is the iterative Gauss–Newton NLLS method.[14][8]

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.[2][3] Wide Area Multilateration (WAM), a 3-D aircraft surveillance system, employs a combination of three or more TOA measurements and an aircraft altitude report.

Two-dimensional Cartesian solutions[edit]

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 motiated by GPS -- for example, Bancroft's[16] or Krause's. [11] Additionally, there are specialized TDOA algorithms for two-dimensions and stations at fixed locations — notable is Fang's method.[17]

A comparison of 2-D Cartesian algorithms for airport surface surveillance has been performed.[18] However, as in the 3-D situation, it's likely the most utilized algorithms are based on Gauss–Newton NLLS.[14][8]

Examples of 2-D Cartesian multilateration systems are those used at many major airports (in many nations) to surveil aircraft on the surface or at very low altitudes.

Two-dimensional spherical solutions[edit]

Razin[15] developed a closed-form solution for a spherical earth. Williams and Last[19] 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[20] method in conjunction with ellipsoid algorithms by Andoyer,[21] Vincenty[22] and Sodano.[23]

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[edit]

Improving accuracy with a large number of receivers 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 Rm, square both sides, collect terms and divide all terms by :

 

 

 

 

(4)

Removing the 2R0 term will eliminate all the square root terms. That is done by subtracting the TDOA equation of receiver m = 1 from each of the others (2 ≤ mN)

 

 

 

 

(5)

Focus for a moment on equation 1. Square Rm, group similar terms and use equation 2 to replace some of the terms with R0.

 

 

 

 

(6)

Combine equations 5 and 6, and write as a set of linear equations of the unknown emitter location x,y,z

 

 

 

 

(7)

Use equation 7 to generate the four constants from measured distances and time for each receiver 2 ≤ mN. This will be a set of N − 1 inhomogeneous linear equations.

There are many robust linear algebra methods that can solve for the values of (x,y,z), such as Gaussian elimination. Chapter 15 in Numerical Recipes[24] describes several methods to solve linear equations and estimate the uncertainty of the resulting values.

Accuracy[edit]

For trilateration or multilateration, calculation is done based on distances, which requires either the time of arrival or the frequency and the wave count of a received transmission. For triangulation or multiangulation, calculation is done based on angles. For electronic systems, this requires the phases of received transmission plus the wave count.

For lateration compared to angulation, the numerical problems compare, but the technical problem is more challenging with angular measurements, as angles require two measures per position when using optical or electronic means for measuring phase differences instead of counting wave cycles.

Trilateration in general is calculating with triangles of known distances/sizes, mathematically a very sound system. In a triangle, the angles can be derived if one knows the length of all sides, (see congruence), but the length of the sides cannot be derived based on all of the angles, not without knowing the length of at least one of the sides (a baseline) (see similarity).

In 3D, when four or more angles are in play, locations can be calculated from n + 1 = 4 measured angles plus one known baseline or from just n + 1 = 4 measured sides.

Multilateration is often more accurate for locating an object than trilateration or triangulation, as (a) it is inherently difficult or expensive to accurately measure the true range (distance) between a moving vehicle and a station, and (b) accurate angle measurements require large antennas which are costly and difficult to site. Multilateration serves for several aspects:

Accuracy of multilateration is a function of several variables, including:

  • The antenna or sensor geometry of the receiver(s) and transmitter(s) for electronic or optical transmission.
  • The timing accuracy of the receiver system, i.e. thermal stability of the clocking oscillators.
  • The accuracy of frequency synchronisation of the transmitter oscillators with the receiver oscillators.
  • Phase synchronisation of the transmitted signal with the received signal, as propagation effects as e.g. diffraction or reflection changes the phase of the signal thus indication deviation from line of sight, i.e. multipath reflections.
  • The bandwidth of the emitted pulse(s) and thus the rise-time of the pulses with pulse coded signals in transmission.
  • Inaccuracies in the locations of the transmitters or receivers when used as a known location

The accuracy can be calculated by using the Cramér–Rao bound and taking account of the above factors in its formulation. Additionally, a configuration of the sensors that minimizes a metric obtained from the Cramér–Rao bound can be chosen so as to optimize the actual position estimation of the target in a region of interest.[5]

Planning a multilateration system often involves a dilution of precision (DOP) analysis to inform decisions on the number and location of the stations and the system's service area (two dimensions) or service volume (three dimensions). In a DOP analysis, the TOA measurement errors are taken to be statistically independent and identically distributed. This reasonable assumption separates the effects of user-station geometry and TOA measurement errors on the error in the calculated user position.[25][26]

Station synchronization[edit]

Multilateration requires that the spatially separated stations – either transmitters (navigation) or receivers (surveillance) – have synchronized 'clocks'. Except for GNSSs, station 'clocks' could, and often have been, devices that measured elapsed time from a common arbitrary origin (zero time) and returned to zero (reset) frequently. Multiple methods have been used for station synchronization. Typically, method selection is based on the distance between stations. In approximate order of increasing distance, methods have included:

  • Clockless stations wired to single clock (navigation and surveillance) – Clockless stations are hard wired to a central location having the single system clock. Wire lengths are generally equal, but that may not be necessary in all applications. This method has been used for locating artillery fire (stations are microphones).
  • Test target (surveillance) – A test target is installed at a fixed, known location that's visible to all receivers. The test target transmits as an ordinary user would, and its position is calculated from the TOAs. Its known position is used to adjust the receiver clocks. ASDE-X uses this method.
  • Clockless stations radio-linked to single clock (navigation and surveillance) – Clockless stations are radio-linked (e.g., microwave) to a central location having the single system clock. Link delays are equalized. This method is used by some WAM systems.
  • Fixed transmitter delays (navigation) – One transmitter is designated the master; the others are secondaries. The master transmits first. Each secondary transmits a fixed (short) time after receiving the master's transmission. Loran-C originally used this method.
  • Satellite time transfer (navigation and surveillance) – There are multiple methods for transferring time from a reference site to a remote station via satellite. The simplest is to synchronize the stations to GPS time.[27] Some WAM systems use this method.
  • Atomic clocks (navigation and surveillance) – Each station has one or more synchronized atomic clocks. GNSSs use this method and Omega did. Loran-C switched to it. Even atomic clocks drift, and a monitoring and correction system may also be required.

Service area or volume[edit]

While the performance of all navigation and surveillance systems depends upon the user's location relative to the stations, multilateration systems are more sensitive to the user's location than most. For example, consider a hypothetical two-station surveillance system that monitors the location of a railroad locomotive along a straight stretch of track (a one dimension situation). The locomotive carries a transmitter and the track is straight in both directions beyond the stretch that's monitored. Such a system would work well when a locomotive is between the two surveillance system's stations. But it would not work at all when a locomotive is not between the stations. Then the multilateration system would always indicate that the locomotive was at the nearer station.

Fig. 4 Typical service area of a two-dimensional (planar) multilateration system having three stations.

In two or three dimensions, a multilateration system's accuracy is not two-valued, as it is in a one-dimensional situation. A dilution of precision (DOP) analysis is often employed to quantify the effect of user-station geometry on accuracy.[28] In general, multilateration accuracy is quite good in the perimeter enclosing the stations but degrades rapidly for locations outside it. Fundamentally, inside the perimeter, the measurements amplify the effect of vehicle motion, while outside of the perimeter they attenuate it. Figure 4 illustrates the service area of two-dimensional system having three stations forming an equilateral triangle (BLU denotes baseline unit).

Outside the stations' perimeter, a multilateration system should typically only be used near the center of the closest baseline connecting two stations (two dimensional situation) or near the center of the closest plane containing three stations (three dimensional situation). Moreover, it should only be used in locations that are a fraction of an average baseline length (e.g., less than 20%) from the closest baseline or plane. This is the situation for an earth-based GPS user. While outside the perimeter of the visible satellites, a user is typically close to the center of the nearest plane containing three satellites and between 5% to 10% of a baseline length from that plane.

Having more than the minimum number of stations mitigates the worst situations (e.g., no solution), but not dramatically. The major value of an additional station is fault tolerance. To provide the required user-station geometry, Loran-C stations were often placed at perimeter locations that some would consider 'remote' – e.g., to provide navigation service to the North Atlantic, there were stations at: Faroe Islands (Denmark), Jan Mayen Island (Norway) and Angissq (Greenland).

Example applications[edit]

  • GPS (U.S.), GLONASS (Russia), Galileo (E.U.) – Global navigation satellite systems. Two separate complicating factors relative to TDOA systems are: (1) the transmitter stations (satellites) are moving; and (2) Receivers compute TOT, requiring a more complex algorithm but providing accurate time to users.
  • Sound ranging – Using sound to locate the source of artillery fire.
  • Electronic targets – Using the Mach wave of a bullet passing a sensor array to determine the point of arrival of the bullet on a firing range target.
  • Decca Navigator System – A system used from the end of World War II to the year 2000, employing the phase-difference of multiple transmitters to locate on the intersection of hyperboloids
  • Omega Navigation System – A worldwide system similar to Decca, shut down in 1997
  • Gee (navigation) – British aircraft location system used during World War II
  • Loran-C – Navigation system using TDOA of signals from multiple synchronised transmitters, shut down in the U.S. and Europe
  • Passive ESM multilateration systems, including Kopáč, Ramona, Tamara, VERA and possibly Kolchuga – location of a transmitter using multiple receivers
  • Mobile phone tracking – using multiple base stations to estimate phone location, either by the phone itself (termed downlink multilateration), or by the phone network (termed uplink multilateration)
  • Reduced Vertical Separation Minima (RVSM) monitoring to determine the accuracy of Mode C/S aircraft transponder altitude information. Application of multilateration to RVSM was first demonstrated by Roke Manor Research Limited in 1989.[29]
  • Wide area multilateration (WAM) – Surveillance system for airborne aircraft that measures the TOAs of emissions from the aircraft transponder (on 1090 MHz); in operational service in several countries
  • Airport Surface Detection Equipment, Model X (ASDE-X) – Surveillance system for aircraft and other vehicles on the surface of an airport; includes a multilateration sub-system that measures the TOAs of emissions from the aircraft transponder (on 1090 MHz); ASDE-X is U.S. FAA terminology, equivalent systems are in operational service in several countries.
  • Flight Test "Truth" – Locata Corporation offers a ground-based local positioning system that augments GPS and is used by NASA and the U.S. military
  • Seismic Event Location – Events (e.g., earthquakes) are monitored by measuring TOAs at different locations and employing multilateration algorithms[30]
  • Towed array sonar / SURTASS / SOFAR (SOund Fixing And Ranging) – Employed operationally by the U.S. Navy (and likely similar systems by other navies). The purpose is determining the distance and direction of a sound source from listening.
  • MILS and SMILS Missile Impact Location Systems – Acoustic systems deployed to determine the 'splash down' points in the South Atlantic of Polaris, Poseidon and Trident missiles that were test-fired from Cape Canaveral, FL.
  • Atlantic Undersea Test and Evaluation Center (AUTEC) – U.S. Navy facility that measures trajectories of undersea boats and weapons using acoustics

Simplification[edit]

For applications where no need for absolute coordinates determination is assessed, the implementing of a more simple solution is advantageous. Compared to multilateration as the concept of crisp locating, the other option is fuzzy locating, where just one distance delivers the relation between detector and detected object. This most simple approach is unilateration. However, such unilateration approach never delivers the angular position with reference to the detector. Many solutions are available today. Some of these vendors offer a position estimate based on combining several laterations. This approach is often not stable, when the wireless ambience is affected by metal or water masses. Other vendors offer room discrimination with a room-wise excitation, one vendor offers a position discrimination with a contiguity excitation.

See also[edit]

  • Ranging
  • Rangefinder
  • Hyperbolic navigation – General term for multiple navigation systems that measure at least one TOA more than the physical dimensions involved
  • FDOA – Frequency difference of arrival. Analogous to TDOA using differential Doppler measurements.
  • Triangulation – Location by angular measurement on lines of bearing that intersect
  • Trilateration – Location by multiple distances – e.g. time-of-flight measurements from multiple transmitters
  • Mobile phone tracking – used in GSM networks
  • Multidimensional scaling
  • Radiolocation
  • Radio navigation
  • Real-time locating – International standard for asset and staff tracking using wireless hardware and real-time software
  • Real time location system – General techniques for asset and staff tracking using wireless hardware and real-time software
  • Great-circle navigation – Provides the basic mathematics for addressing spherical ranges
  • Non-linear least squares - Form of least-squares analysis when non-linear equations are involved; used for multilateration when (a) there are more range-difference measurements than unknown variables, and/or (b) the measurement equations are too complex to be inverted (e.g., those for an ellipsoidal earth), and/or (c) tabular data must be utilized (e.g., conductivity of the earth over which radio wave propagated).
  • Coordinated Universal Time (UTC) - Time standard provided by GPS receivers (with published offset)
  • Clock synchronization - Methods for synchronizing clocks at remote stations
  • Atomic clock – Sometimes used to synchronize multiple widely separated stations
  • Dilution of precision – Analytic technique often used with multilateration systems

Notes[edit]

  1. ^ "The Role of the Clock in a GPS Receiver", Pratap N. Misra, GPS World, April 1996
  2. ^ a b "Existence and uniqueness of GPS solutions", J.S. Abel and J.W. Chaffee, IEEE Transactions on Aerospace and Electronic Systems, vol. 26, no. 6, pp. 748–53, Sept. 1991.
  3. ^ a b "Comments on "Existence and uniqueness of GPS solutions" by J.S. Abel and J.W. Chaffee", B.T. Fang, IEEE Transactions on Aerospace and Electronic Systems, vol. 28, no. 4, Oct. 1992.
  4. ^ In other words, given two receivers at known locations, one can derive a three-dimensional surface (characterized as one half of a hyperboloid) for which all points on said surface will have the same differential distance from said receivers, i.e., a signal transmitted from any point on the surface will have the same TDOA at the receivers as a signal transmitted from any other point on the surface.
    Therefore, in practice, the TDOA corresponding to a (moving) transmitter is measured, a corresponding hyperbolic surface is derived, and the transmitter is said to be "located" somewhere on that surface.
  5. ^ a b Domingo-Perez, Francisco; Lazaro-Galilea, Jose Luis; Wieser, Andreas; Martin-Gorostiza, Ernesto; Salido-Monzu, David; Llana, Alvaro de la (April 2016). "Sensor placement determination for range-difference positioning using evolutionary multi-objective optimization". Expert Systems with Applications. 47: 95–105. doi:10.1016/j.eswa.2015.11.008.
  6. ^ The Development of Loran-C Navigation and Timing, Gifford Hefley, U.S. National Bureau of Standards, Oct. 1972.
  7. ^ Omega Navigation System Course Book, Peter B. Morris et al, TASC, July 1994.
  8. ^ a b c d e Earth-Referenced Aircraft Navigation and Surveillance Analysis, Michael Geyer, U.S. DOT John A. Volpe National Transportation Systems Center, June 2016.
  9. ^ a b "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.
  10. ^ "Trilateration and extension to global positioning system navigation", B.T. Fang, Journal of Guidance, Control, and Dynamics, vol. 9 (1986), pp 715–717.
  11. ^ a b “A direct solution to GPS-type navigation equations”, L.O. Krause, IEEE Transactions on Aerospace and Electronic Systems, AES-23, 2 (1987), pp 225–232.
  12. ^ Analytical GPS Navigation Solution, Alfred Kleusberg, University of Stuttgart Research Compendium, 1994.
  13. ^ A Synthesizable VHDL Model of the Exact Solution for Three-dimensional Hyperbolic Positioning System, Ralph Bucher and D. Misra, VLSI Design, Volume 15 (2002), Issue 2, pp 507–520.
  14. ^ a b c "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.
  15. ^ a b "Explicit (Noniterative) Loran Solution", Sheldon Razin, Navigation: Journal of the Institute of Navigation, Vol. 14, No. 3, Fall 1967, pp. 265–269.
  16. ^ "Solving Passive Multilateration Equations Using Bancroft’s Algorithm", Michael Geyer and Anastasios Daskalakis, Digital Avionics Systems Conference (DASC); Seattle, WA; Oct. 31-Nov. 6, 1998.
  17. ^ "Simple Solutions for Hyperbolic and Related Position Fixes", Bertrand T. Fang, IEEE Transactions on Aerospace and Electronic Systems, September 1990, pp 748–753.
  18. ^ "Localization algorithms for multilateration (MLAT) systems in airport surface surveillance", Ivan A. Mantilla-Gaviria, Mauro Leonardi,·Gaspare Galati and Juan V. Balbastre-Tejedor, Springer-Verlag, London, 2014
  19. ^ Williams, Paul; Last, David (November 3–7, 2003). On Loran-C Time-Difference to Co-ordinate Converters (PDF). International Loran Association (ILA) - 32nd Annual Convention and Technical Symposium. Boulder, Colorado. CiteSeerX 10.1.1.594.6212.
  20. ^ Minimum Performance Standards (MPS) Automatic Co-ordinate Conversion Systems, Report of RTCM Special Committee No. 75, Radio Technical Commission for Marine Services, Washington, D.C, 1984
  21. ^ "Formule donnant la longueur de la géodésique, joignant 2 points de l'ellipsoide donnes par leurs coordonnées geographiques", Marie Henri Andoyer, Bulletin Geodsique, No. 34 (1932), pages 77–81
  22. ^ "Direct and Inverse Solutions of Geodesics on the Ellipsoids with Applications of Nested Equations", Thaddeus Vincenty, Survey Review, XXIII, Number 176 (April 1975)
  23. ^ "General non-iterative solution of the inverse and direct geodetic problems", Emanuel M. Sodano, Bulletin Géodésique, vol 75 (1965), pp 69–89
  24. ^ Numerical Recipes official website
  25. ^ Accuracy Limitations of Hyperbolic Multilateration Systems, Harry B. Lee, Massachusetts Institute of Technology, Lincoln Laboratory, Technical Note 1973-11, March 22, 1973
  26. ^ Improved Satellite Constellations for CONUS ATC Coverage, Harry B. Lee and Andrew E. Wade, Massachusetts Institute of Technology, Lincoln Laboratory, Project Report ATC-23, May 1, 1974
  27. ^ One Way GPS Time Transfer, National Institute of Standards and Technology
  28. ^ "Dilution of Precision", Richard Langeley, GPS World, May 1999, pp 52–59.
  29. ^ Air Traffic Technology International (2002). "Perfect Timing" (PDF). Archived from the original (PDF) on 18 December 2014. Retrieved 31 August 2012.
  30. ^ "A Closed-Form Solution for Earthquake Location in a Homogeneous Half-Space Based on the Bancroft GPS Location Algorithm", Demian Gomez, Charles Langston & Bob Smalley, Bulletin of the Seismological Society of America, January 2015.

References[edit]