Multilateration
More actions
Multilateration is a process of determining position of an object from separated sources. It can be done in 2D or 3D. Multilateration can be used as a technique for 3D tracking using electromagnetic signals or acoustic signals.[1] The measurements are usually signal travel times, or differences between travel times, between the tracked object and several stations at known positions. Each measurement is converted into a distance or a distance difference, and the position is the point that agrees with all of them.[2]
The Global Positioning System works this way, with a receiver measuring "pseudoranges" to at least four satellites.[3] In virtual reality and augmented reality, an early example of range-based head tracking is the ultrasonic head position sensor built for Ivan Sutherland's 1968 head-mounted display.[4] Later systems include the ultrasonic and inertial Constellation tracker, sold as the InterSense IS-900,[1] and research that adds ultra-wideband radio ranging to AR headsets.[5]
How it works
In time of flight ranging, the propagation time of a signal between a transmitter and a receiver is multiplied by the signal velocity to give the distance between them. With distances from three reference nodes, basic geometry gives the location of the device.[2] Trilateration is the closely related method of determining position by measuring distances to points at known coordinates; at a minimum it requires three ranges to three known points.[3]
When only the difference in arrival times at two stations is known, the object lies on one branch of a hyperbola in 2D or on a hyperboloid in 3D, with the two stations at the foci.[6] The location is found as the intersection of several such hyperbolas or hyperboloids.[2][7]
For a 2D plane, multilateration generally needs 3 sensors/sources minimum. For 3D, it generally needs 4 sensors/sources minimum.[6] The same count appears in satellite navigation: a GPS receiver's clock error is unknown, so each pseudorange is "almost like range, except that it includes clock errors", and the three position coordinates plus the receiver clock error make four unknowns that require at least four pseudorange measurements.[3]
Methods
The main ways of obtaining the measurements differ in what is timed and which devices must share a clock.
| Method | What is measured | Synchronization | Examples |
|---|---|---|---|
| TOA (time of arrival, also called time of flight) | Absolute propagation time between transmitter and receiver, converted to a range[2] | Strict synchronization between transmitters and receivers[2] | UWB ranging to anchor nodes;[7] infrared-triggered ultrasonic ranging in the Constellation tracker[8] |
| Two-way ranging (round-trip time) | Round-trip time of a message and its reply, minus the known reply delay[7] | No synchronization needed between the two devices[7] | UWB transceiver on a Microsoft HoloLens in a 2018 study[5] |
| TDOA (time difference of arrival) | Difference between arrival times of the same signal at two stations[2] | Only the fixed stations must be synchronized with each other; the tracked tag does not[7] | UWB asset tracking and other real-time location systems[7] |
| Pseudorange | Signal travel time measured with an unsynchronized receiver clock[3] | Receiver clock error is solved for as a fourth unknown[3] | Global Positioning System[3] |
| Carrier phase | Phase shift of a continuous wave between transmitter and receiver[1] | Only relative changes within one wavelength can be measured, so the starting distance must be known[1] | Sutherland's 1968 ultrasonic head position sensor[4] |
Solving the equations
It can be done using iterative methods, also known as numerical methods, using least squares methods. In 1976 Wade Foy described Taylor-series estimation, which linearizes the equations and gives a least-sum-squared-error solution; the paper notes that convergence is not proved, but that most example problems converge to the correct solution from reasonable initial guesses, and that the method also gives the statistical spread of the solution errors.[9] Non-iterative alternatives followed. S. Bancroft's 1985 algebraic solution of the GPS equations is a non-iterative alternative to the Newton's method iteration usually used, and it also admits batch processing of more than four pseudoranges.[10] For time difference measurements, Y. T. Chan and K. C. Ho published a non-iterative estimator in 1994 that approximates the maximum-likelihood solution and reaches the Cramer-Rao lower bound when errors are small, with less computation than the Taylor-series method.[11]
There is only one place where all of the signals overlap, and that is where the object is. Real measurements contain noise, so systems estimate the position that best fits every measurement. The 2018 HoloLens study, for example, assumed Gaussian range noise and solved for the position that minimizes the sum of squared differences between computed and measured distances.[5] With more measurements than unknowns, GPS point positioning uses least squares estimation in the same way.[3]
Station geometry affects accuracy. The standard metric used in GPS and other range-based systems is the geometric dilution of precision (GDOP), which describes how much random range noise is amplified into position error at a given point.[8] The HoloLens study reported its accuracy only for position dilution of precision (PDOP) values below 10.[5]
Error sources
Acoustic systems depend on the speed of sound, which varies with temperature, humidity and air currents. Welch and Foxlin give a rule of thumb that the speed of sound changes about 0.1 percent per degree Fahrenheit, corresponding to about a one-millimeter error per degree Fahrenheit at one meter.[1] Ultrasonic positioning systems therefore often include temperature sensors.[2] Sound is also slow: an acoustic measurement takes about one millisecond per foot of range, and systems may have to wait 5 to 100 ms for echoes of the previous measurement to die out, giving update rates as slow as 10 Hz.[1]
Reflections cause multipath errors. Pulsed acoustic systems can avoid most of them by waiting for the first pulse, which arrives by the direct path unless the path is blocked; this works for sound because it travels slowly enough to separate the direct pulse from the first echo.[1] Radio waves travel about a million times faster (roughly one foot per nanosecond), so ranging with 1 mm resolution by simple counting would require a timer running at 300 GHz.[1] For radio time of flight, accuracy depends on signal bandwidth and sampling rate, and errors grow when there is no direct line of sight because obstacles force the signal onto a longer path.[2] Ultra-wideband pulses are short enough that reflected arrivals can be separated and filtered at the receiver.[7]
Use in VR and AR tracking
Sutherland's ultrasonic head sensor
Sutherland's 1968 head-mounted display could use either of two head position sensors, one mechanical and one ultrasonic. The ultrasonic sensor was designed and built at MIT Lincoln Laboratory by Charles Seitz and Stylianos Pezaris. Three transmitters on the head-mounted optics sent continuous ultrasound at 37, 38.6 and 40.2 kHz to four receivers mounted in a square array in the ceiling, so that phase changes could be measured over twelve paths.[4] Because the wavelength of sound at 40 kHz is about 1/3 inch, each measurement was ambiguous at 1/3 inch intervals; the computer counted whole phase changes to follow larger motions, which left an unknown constant "initialization error" in each path length. Sutherland expected to resolve these errors with the geometric redundancy of twelve measurements, but wrote that a full report on the ultrasonic sensor was not yet possible.[4] The head position sensors of the system covered a working volume about six feet in diameter and three feet high.[4]
Welch and Foxlin, citing Meyer and colleagues, noted that this "phase-coherent" method measures continuously without latency but can only measure relative distance changes within a cycle; they added that multipath reflections in a room make the received phase vary unpredictably, which they suggest could be why no successful phase-coherent acoustic tracker had been developed.[1] All commercial acoustic ranging systems known to them instead timed the flight of a brief ultrasonic pulse.[1]
Ultrasonic time-of-flight devices
Ultrasonic time-of-flight ranging was used in several commercial 3D input devices, including the Logitech 6-D Mouse, the Mattel Power Glove, the Lipman VSCOPE and the Kantek Ringmouse.[8]
Constellation and the InterSense IS-900
Eric Foxlin, Michael Harrington and George Pfeifer of InterSense presented Constellation at SIGGRAPH 98 as a wide-range wireless tracker for AR and virtual set applications. It combined an inertial sensor package with ultrasonic time-of-flight range measurements to a "constellation" of transponder beacons mounted at known locations. Rangefinder modules on the headset triggered the beacons one at a time with infrared codes, each beacon answered with an ultrasonic pulse, and the time of flight was converted to a distance using the speed of sound.[8] At least six range measurements, between at least three headset microphones and at least three fixed beacons, were needed to fully determine the position and orientation of the headset.[8]
Rather than collecting ranges from three beacons, computing a trilateration fix and feeding that position to a filter, Constellation fed each range measurement individually into an extended Kalman filter that corrected the drift of the inertial system.[8] Because the filter already knew roughly where the tracker was, it could predict each range and reject measurements that did not match, such as echoes or noise that arrived before the real pulse. The authors described it as the first time-of-flight motion tracker with latency less than the flight time of its ranging signals, which the inside-out arrangement and the inertial sensors made possible.[8] Their error simulation, which used a multilateration algorithm, gave a positional resolution of 0.7 to 1.5 mm over most of the test volume and a combined systematic position error of 2.3 to 4.7 mm for the error levels they believed were present in their laboratory setup.[8] Constellation was brought to market as the InterSense IS-900, which achieved scalable range with ceiling-mounted emitters and fused its acoustic ranges with inertial sensors.[1] The design is an example of sensor fusion in positional tracking.
Ultra-wideband
Multilateration can be done with UWB. UWB is a general term for radio communication with a bandwidth close to or greater than 500 MHz; impulse radio UWB sends pulses lasting nanoseconds or picoseconds, and its main use case is localization.[7] A tag can be located from time of flight or two-way ranging to three anchor nodes, or from time differences of arrival at synchronized anchors. The IEEE 802.15.4z standard describes two-way ranging, double-sided two-way ranging, TDOA and time of flight in its MAC functional description, and UWB support has appeared in consumer devices such as smartphones.[7]
In a 2018 study, researchers at Fraunhofer IOSB mounted a UWB transceiver on a Microsoft HoloLens to locate objects that the headset's cameras could not see. The headset's own visual-inertial odometry gave the antenna position at each moment, and range measurements taken from many positions were combined by trilateration to locate a static UWB transponder. They reported a mean localization accuracy of 6 cm with a standard deviation of 3.3 cm for PDOP values below 10, and, in ranging tests at a ground-truth distance of 1 m, a mean error of 18.06 cm with a standard deviation of 1.77 cm for their most precise two-way ranging method, a bias they attributed partly to imperfect antenna delay calibration.[5]
Comparison with angle-based methods
Multilateration uses distances or distance differences. Angle of arrival methods instead measure the direction from which a signal arrives and can locate a device with as few as two monitors in 2D or three in 3D, but a small angle error becomes a large position error as distance increases.[2] Welch and Foxlin list triangulation among the methods used when several optical sensors at known locations estimate the position of a light source.[1] The Constellation authors gave simpler mathematics as one reason for choosing acoustic ranging over optical bearing measurements: three range measurements fix a position, while six bearing angles are needed to solve for position and orientation.[8]
See also
References
- ↑ 1.00 1.01 1.02 1.03 1.04 1.05 1.06 1.07 1.08 1.09 1.10 1.11 Greg Welch, Eric Foxlin (2002-11). "Motion Tracking: No Silver Bullet, but a Respectable Arsenal". IEEE Computer Graphics and Applications, vol. 22, no. 6. pp. 24-38. https://doi.org/10.1109/MCG.2002.1046626. Retrieved 2026-09-27.
- ↑ 2.0 2.1 2.2 2.3 2.4 2.5 2.6 2.7 2.8 Faheem Zafari, Athanasios Gkelias, Kin K. Leung (2019). "A Survey of Indoor Localization Systems and Technologies". IEEE Communications Surveys & Tutorials, vol. 21, no. 3. pp. 2568-2599. doi:10.1109/COMST.2019.2911558. https://arxiv.org/abs/1709.01015. Retrieved 2026-09-27.
- ↑ 3.0 3.1 3.2 3.3 3.4 3.5 3.6 Geoffrey Blewitt (1997). "Basics of the GPS Technique: Observation Equations". Geodetic Applications of GPS. Swedish Land Survey. https://web.gps.caltech.edu/classes/ge111/Docs/GPSbasics.pdf. Retrieved 2026-09-27.
- ↑ 4.0 4.1 4.2 4.3 4.4 Ivan E. Sutherland (1968-12). "A head-mounted three dimensional display". Proceedings of the AFIPS Fall Joint Computer Conference, part I. pp. 757-764. https://doi.org/10.1145/1476589.1476686. Retrieved 2026-09-27.
- ↑ 5.0 5.1 5.2 5.3 5.4 Francisco Molina Martel, Juri Sidorenko, Christoph Bodensteiner, Michael Arens (2018-09). "Augmented Reality and UWB Technology Fusion: Localization of Objects with Head Mounted Displays". Proceedings of the 31st International Technical Meeting of the Satellite Division of the Institute of Navigation (ION GNSS+ 2018). pp. 685-692. doi:10.33012/2018.16046. https://publica-rest.fraunhofer.de/server/api/core/bitstreams/aaa5d7fe-a1a4-4ced-bc81-f0bcafd3f5ef/content. Retrieved 2026-09-27.
- ↑ 6.0 6.1 "Object Tracking Using Time Difference of Arrival (TDOA)". MATLAB documentation. MathWorks. https://www.mathworks.com/help/fusion/ug/object-tracking-using-time-difference-of-arrival.html. Retrieved 2026-09-27.
- ↑ 7.0 7.1 7.2 7.3 7.4 7.5 7.6 7.7 7.8 Dieter Coppens, Adnan Shahid, Sam Lemey, Ben Van Herbruggen, Chris Marshall, Eli De Poorter (2022). "An Overview of UWB Standards and Organizations (IEEE 802.15.4, FiRa, Apple): Interoperability Aspects and Future Research Directions". IEEE Access, vol. 10. pp. 70219-70241. doi:10.1109/ACCESS.2022.3187410. https://arxiv.org/abs/2202.02190. Retrieved 2026-09-27.
- ↑ 8.0 8.1 8.2 8.3 8.4 8.5 8.6 8.7 8.8 Eric Foxlin, Michael Harrington, George Pfeifer (1998-07). "Constellation: A Wide-Range Wireless Motion-Tracking System for Augmented Reality and Virtual Set Applications". Proceedings of SIGGRAPH 98. ACM. pp. 371-378. doi:10.1145/280814.280937. https://www.intersense.com/wp-content/uploads/2018/10/Constellation-_A_Wide-Range_Wireless_Motion-Tracking_System_for_Augmented_Reality_and_Virtual_Set_Applications.pdf. Retrieved 2026-09-27.
- ↑ Wade H. Foy (1976-03). "Position-Location Solutions by Taylor-Series Estimation". IEEE Transactions on Aerospace and Electronic Systems, vol. AES-12, no. 2. pp. 187-194. https://doi.org/10.1109/TAES.1976.308294. Retrieved 2026-09-27.
- ↑ S. Bancroft (1985-01). "An Algebraic Solution of the GPS Equations". IEEE Transactions on Aerospace and Electronic Systems, vol. AES-21, no. 1. pp. 56-59. https://doi.org/10.1109/TAES.1985.310538. Retrieved 2026-09-27.
- ↑ Y. T. Chan, K. C. Ho (1994). "A simple and efficient estimator for hyperbolic location". IEEE Transactions on Signal Processing, vol. 42, no. 8. pp. 1905-1915. https://doi.org/10.1109/78.301830. Retrieved 2026-09-27.