Positioning in Challenging Environments Using Ultra-Wideband Sensor Networks By Zoltan Koppanyi, Charles K. Toth and Dorota A. Grejner-Brzezinska INNOVATION INSIGHTS by Richard Langley QUICK. WHO WAS THE FIRST TO PREDICT THE EXISTENCE OF RADIO WAVES? If you answered James Clerk Maxwell, you are right. (If you didn’t and have an electrical engineering or physics degree, it’s back to school for you.) In the mid-1800s, Maxwell developed the theory of electric and magnetic forces, which is embodied in the group of four equations named after him. This year marks the 150th anniversary of the publication of Maxwell’s paper “A Dynamical Theory of the Electromagnetic Field” in the Philosophical Transactions of the Royal Society of London. Interestingly, Maxwell used 20 equations to describe his theory but Oliver Heaviside managed to boil them down to the four we are familiar with today. Maxwell’s theory predicted the existence of radiating electromagnetic waves and that these waves could exist at any wavelength. Maxwell had speculated that light must be a form of electromagnetic radiation. In his 1865 paper, he said “This velocity [of the waves] is so nearly that of light, that it seems we have strong reason to conclude that light itself (including radiant heat, and other radiations if any) is an electromagnetic disturbance in the form of waves propagated through the electromagnetic field according to electromagnetic laws.” That electromagnetic waves with much longer wavelengths than those of light must be possible was conclusively demonstrated by Heinrich Hertz who, between 1886 and 1889, built various apparatuses for transmitting and receiving electromagnetic waves with wavelengths of around 5 meters (60 MHz). These waves were, in fact, radio waves. Hertz’s experiments conclusively proved the existence of electromagnetic waves traveling at the speed of light. He also famously said “I do not think that the wireless waves I have discovered will have any practical application.” How quickly he was proven wrong. Beginning in 1894, Guglielmo Marconi demonstrated wireless communication over increasingly longer distances, culminating in his bridging the Atlantic Ocean in 1901 or 1902. And, as they say, the rest is history. Radio waves are used for data, voice and image one-way (broadcasting) and two-way communications; for remote control of systems and devices; for radar (including imaging); and for positioning, navigation and time transfer. And signals can be produced over a wide range of frequencies from below 10 kHz to above 100 GHz. Conventional radio transmissions use a variety of modulation techniques but most involve varying the amplitude, frequency and/or phase of a sinusoidal carrier wave. But in the late 1960s, it was shown that one could generate a signal as a sequence of very short pulses, which results in the signal energy being spread over a large part of the radio spectrum. Initially called pulse radio, the technique has become known as impulse radio ultra-wideband or just ultra-wideband (UWB) for short and by the 1990s a variety of practical transmission and reception technologies had been developed. The use of large transmission bandwidths offers a number of benefits, including accurate ranging and that application in particular is being actively developed for positioning and navigation in environments that are challenging to GNSS such as indoors and built-up areas. In this month’s column, we take a look at the work being carried out in this area by a team of researchers at The Ohio State University. “Innovation” is a regular feature that discusses advances in GPS technology and its applications as well as the fundamentals of GPS positioning. The column is coordinated by Richard Langley of the Department of Geodesy and Geomatics Engineering, University of New Brunswick. He welcomes comments and topic ideas. Email him at lang @ unb.ca. GNSS technology provides position, navigation and timing (PNT) information with high accuracy and global coverage where line-of-sight between the satellites and receivers is assured. This condition, however, is typically not satisfied indoors or in confined environments. Emerging safety, military, location-based and personal navigation applications increasingly require consistent accuracy and availability, comparable to that of GNSS but in indoor environments. Most of the existing indoor positioning systems use narrowband radio frequency signals for location estimation, such as Wi-Fi, or telecommunication-based positioning (including GSM and UMTS mobile telephone networks). All these technologies require dedicated infrastructure, and the narrowband RF systems are subject to jamming and multipath, as well as loss of signal strength while propagating through walls. In contrast, using ultra-wideband (UWB) signals can, to some extent, remediate those problems by offering better resistance against interference and multipath, and they feature better signal penetration capability. Due to these properties, the use of UWB has the potential to support a broad range of applications, such as radar, through-wall imagery, robust communication with high frequency, and resistance to jamming. Furthermore the impulse radio UWB (IR-UWB), the subject of this article, can be an efficient standalone technology or a component of positioning systems designed for multipath-challenged, confined or indoor environments, where GNSS signals are compromised. IR-UWB positioning can be useful in typical emergency response applications such as fires in large buildings, dismounted soldiers in combat situations, and emergency evacuations. In such circumstances, the positioning/navigation systems must determine not only the exact position of any individual firefighter or soldier to facilitate their team-based mission, but also navigate them back to safety. Under these scenarios, a temporary ad hoc network has to be quickly deployed, as the existing infrastructure is usually non-functional, damaged or destroyed at that point. The UWB-based systems may easily satisfy these criteria: (1) nodes placed in the target area can rapidly establish the network geometry even if line-of-sight between nodes is not available, (2) the communication capability allows for sharing measurements, and (3) the node positions may be calculated based on these measured ranges in a centralized or distributed way. Once the node coordinates have been determined, the tracking of the moving units can start. Obviously, the resistance against jamming makes this solution attractive for military applications. Ad Hoc Network Formation for Emergency Response Quick deployment Sufficient positioning accuracy Robustness against interference (jamming) Signal penetration through solid structures Generally, positioning systems, both local and global, require an infrastructure, which defines the implementation of a coordinate frame. For example, the national reference frames and their realizations support conventional land surveying, or the satellite and the GPS tracking subsystems, as well as the beacons in Wi-Fi systems. UWB positioning also follows the same logic; the network infrastructure defines a local coordinate system and allows for range measurements between the network nodes and the tracked unit(s). Ad Hoc Sensor Network: Ad hoc networks are temporary, and thus, the node coordinates are not expected to be known or measured a priori; consequently, they are calculated based on measuring the ranges between the units in the initial phase, and can be updated subsequently if the network configuration changes. Anchored Networks: The network nodes’ coordinates are known. If only local coordinates are known, then to connect to a global coordinate frame, at least one node’s global coordinates and a direction vector must be known to anchor and orient the network. Anchor-Free Networks: No node coordinates are known, thus the localization problem is underdetermined. Nevertheless, the problem is still solvable, if it is extended with additional constraints. Tracking: Once a network is established, static/moving objects can be positioned in the network coordinate system.   Ultra-Wideband Ranging At the beginning of the 21st century, the Federal Communications Commission (FCC) introduced new regulations that enabled several commercial applications and initiated research on UWB application to PNT. The current FCC rules for pulse-based positioning or localization implementations require the applied bandwidth be between 3.1 and 10.6 GHz and the bandwidth to be higher than 500 MHz or the fractional bandwidth to be more than 0.2. The typical IR-UWB ranging system consists of multiple transceiver units, including the transmitter and the receiver components. The transmitter emits a very short pulse (high bandwidth) with low energy, and the receiver detects the signal after it travels through the air, interacting with the environment. After reaching objects, the emitted pulse is backscattered as several signals, which likely reach the receiver at different times. In contrast, conventional RF signals are longer in duration, thus the backscattered waves overlap each other at the receiver, forming a complex waveform, and may not be distinguishable individually. Due to the shortness of the UWB signals, measurable peaks are nicely separated, representing different signal paths. The wave shape of the impulse response of the transmission medium highly depends on the environment complexity due to multipath. Detections in the received wave are determined by a peak-detecting algorithm. Note that the travel time is generally determined from the first detection, as it is assumed to be from the shortest path, although other peak detection algorithms also exist. In the experiments discussed in this article, a commercial UWB radio system was used. This sensor’s bandwidth is between 3.1 and 5.3 GHz, with a 4.3-GHz center frequency. Three methods are available to obtain ranges: (1) coarse range estimation, based on the received signal strength with dynamic recalibration; (2) precision range measurement (PRM), which uses the two-way time-of-flight technique; and (3) the filtered range estimates (FRE) method that refines the PRM solution using Kalman filtering. In our investigations, PRM data were used in static situations, when both the unit to be positioned and the reference units were static (such as when determining network node coordinates), and FRE was logged in kinematic scenarios. Localization in a UWB Network Commercial UWB products usually provide capabilities for all three applications: communication, ranging and radar imaging. In positioning applications, identical units are used for both the rovers — that is, the units to be localized — and the static nodes of the network. The general terminology, however, is that the rover unit with unknown position is called the receiver, and units deployed at known locations are called transmitters. We will also use the terms rover and stations. The positions are typically defined in a local coordinate system. The usual ranging methods used in RF technologies, including signal strength and fingerprinting, time of arrival, angle of arrival, and time difference of arrival, are also applicable to UWB systems. TABLE 1 lists the ranging methods and typical performance levels; the achievable accuracies are based on external references. Note that the accuracy depends on the sensor hardware and network configuration, applied bandwidth, signal-to-noise ratio, peak detection algorithm, experiment circumstances, formation and the environment complexity. TABLE 1. Typical accuracy of the different UWB localization techniques. Note that the results depend on the hardware, antenna, applied bandwidth, experiment circumstances and geometric configuration; * denotes indoor environment with area coverage of a few times 10 × 10 meters, with line-of-sight conditions, and ** refers to the maximum error in the outdoor test area of about 100 × 100 meters). Signal Strength. The received signal strength (RSS) requires modeling of the signal loss, which is a challenging problem since signals at different frequencies interact with the environment in different ways, and thus the resulting accuracy is generally inadequate for most applications. The fingerprinting approach is also applied to UWB positioning; the signal-strength vector received from the transmitters identifies a location by the best match, where the vector-location pairs are measured in a calibration/training phase and stored in a database. Time of Flight. The time-of-flight method requires the synchronization of the clocks of the UWB units, which is difficult, in particular, in the low-cost systems. Therefore, most UWB systems are based on the two-way time-of-flight method, which eliminates the unknown clock delay between the sensors, although it also has its own challenges. The range between two units is obtained by measuring the time difference of the transmitted and received pulses plus knowing the fixed response time of the responding unit. Computing Position in a Network. Once the ranges are known in a network environment, the position is determined by circular lateration. The principle for the 2D case with three stations is shown in FIGURE 1. Note that each range determines a circle around the known stations (stations 1, 2 and 3 in the figure), thus, if the stations’ coordinates are known, the unknown position can be calculated as the intersection of these circles. The problem is treated as a system of non-linear equations; note that the lateration requires at least three or four nodes in an adequate spatial distribution for 2D and 3D positioning, respectively. The measured ranges, characterized by the error terms usually modeled with a normal distribution, are depicted by the dotted parallel circles around the solid “perfect” range in Figure 1. Note that this is an optimization problem, which can be solved with direct numerical approximation, such as gradient methods, or by solving the respective linear system after linearizing the problem with close initial position values. FIGURE 1. Circular lateration. Time Difference and Angle of Arrival. The time difference of arrival (TDoA) approach is useful when the time synchronization is not established. The unknown time delays are eliminated by subtracting the travel times between the rover and the stations, and the response time of the responding unit must be known. The location estimation is similar to the time of arrival case, but rather than the intersection of the circles, hyperbolic function curves representing constant TDoA values are used to determine the rover position. Also, if errors are present in the measurements, the position calculation becomes an optimization problem instead of finding the root of an equation. The TDoA can be combined with the angle of arrival (AoA). This method assumes that the set of UWB antennas are arranged in an array, and the angle can be calculated as the time difference of the first and the last detection from different antennas of the array. Calibration The ranges obtained by UWB sensors could be further improved by calibration — for example, by estimating antenna and hardware delays. In our outdoor tests, the joint calibration model (see Two Calibration Models box) was used, and coefficients of various model functions were estimated. During these tests, the UWB units were placed at the corners of a 15  × 15 meter area (see FIGURE 2). FIGURE 2. Outdoor test configuration. At two diagonal corners, two UWB units with a 1.5-meter vertical separation were installed on poles, while at the two other corners only one unit was used. These six units formed the nodes or the stations of the network. In all cases, a GPS antenna was fixed to the top of the poles to provide reference data. A pushcart with two UWB units, a logging laptop computer, a GPS antenna and a receiver formed the rover system. The reference solution was obtained by using the GPS measurements, with the accuracy around 1 centimeter after kinematic post-processing using precise satellite orbit and clock data. During calibration, the pushcart was collecting stationary data at points 1 to 12, marked on a 5 × 5 meter grid, as shown in Figure 2. Two Calibration Models Individual sensor calibration is the approach where the sensor delays are determined separately, for example, , where  is the measured range between stations A and B, and  are the calibration functions, and  is the corrected range. Joint calibration model is the approach where the calibration function does not provide the offset per station, but rather gives the relative offset between the two stations, where . The calibration model as a function of the measured distance can be constant, linear or a higher-order polynomial.   After acquiring range data between the rover and network stations, three types of joint calibration functions were investigated: constant, linear and polynomial models. The coefficients of these functions were estimated from the measured ranges and GPS-provided reference positions at all grid points. The estimated functions with respect to the six network nodes are shown in FIGURE 3. Our hypothesis was that the accuracy is assumed to depend on the rover-station distance, and thus, the detected discrepancies between the rover and reference points are expected to be higher if the distance is larger. The results indicate that a constant correction (that is, an antenna delay) is generally sufficient, indicating that the calibration may be applicable to similar installations. In some cases, a linear trend (a distance dependency) may be recognized due to slight data changes, but the observed regression lines are either increasing or decreasing, which clearly rejects the distance-dependency hypothesis. The linear and second-order polynomial functions likely model only local effects. The corrections provided by these functions depend on the environment, and consequently, are valid only in that configuration and where they were observed. FIGURE 3. Calibration models. Error surfaces, derived as the approximation of a second-order surface from the residuals at the grid points between the receiver and the six station units, show that the discrepancies can be as large as 0.5 meter. Calibrated results using the constant model show that all the discrepancies are less than 10 centimeters with an empirical standard deviation of 3.6 centimeters. This suggests that, at least, the constant-model-based calibration is needed. Tracking Outdoors and Indoors If the coordinates of the network nodes and the calibration parameters are known, the location of the moving rover can be calculated with circular lateration. The experiment described in this section is based on the same field test as presented earlier. For assessing the outdoor tracking performance, a random trajectory of the pushcart inside and outside of the rectangle defined by nodes was acquired (see FIGURE 4). The reference trajectory was obtained by GPS and the UWB trajectory was calculated with circular lateration. FIGURE 4. Trajectory solutions. TABLE 2 presents a statistical comparison of the coordinate component differences between the GPS reference and the UWB trajectory based on calibrated ranges. The mean of the X and Y coordinate differences are around 0 centimeters, and their standard deviations are 9.7 and 13.2 centimeters, respectively, with the largest differences being less than half a meter in both coordinate components. Note that the vertical coordinates have large errors due to the small vertical angle, which translates to weak geometric conditions for error propagation. TABLE 2. Statistical results for the coordinate components. Indoor UWB positioning is more challenging than outdoor, as propagation through walls modifies the RF signals resulting in attenuations and delays. Furthermore, the geometric error propagation conditions (that is, the shape of the network) may also reduce the quality of positioning. In the indoor tests, a personal navigation system demonstration prototype built in our lab (shown in FIGURE 5) was used as a rover. During the tests, the person was moving at a normal pace, and the rover unit recorded the ranges from the reference stations. Concerning the network, two point types are defined: (1) network nodes depicted by a double circle in the figure, which are used in the tracking phase; and (2) reference points marked by a single circle, which support the validation of the positioning results. FIGURE 5. Indoor test configuration. Since no reference solution was available during the indoor testing, the calibration method’s consistency was evaluated based on the relative or internal accuracy metric, which is the a posteriori reference standard deviation error: where v is the vector of residual errors and r=dim(ATA) – rank(ATA) is the degrees of freedom of the network with A being the design matrix describing the geometry of the network. The m0 values are shown in FIGURE 6. This parameter describes the statistical difference of the measurements from the assumed model (circular lateration). The average m0 is 7.6 centimeters without calibration, and higher if any of the outdoor calibration models are used. FIGURE 6. The indoor test results showing values of m0 at the epochs. To estimate the absolute or external accuracy without a reference trajectory, points 1002 and 1004 were used as checkpoints with known coordinates. Obviously, these points were not part of the network. The UWB rover unit was placed at these points, and data were acquired in a static mode. The coordinates were continuously calculated after measuring at least three ranges. TABLE 3 presents the statistical results. Note that the average is not 0, thus the result is biased, indicating that the signal penetration and/or multipath effects are present in this complex indoor environment. Also, note that no calibration was performed, as no indoor calibration results were available, and using the outdoor calibration models only decreased the positioning accuracy. In addition, the standard deviations indicate the average m0 is consistent with the external error for point 1002, while this hypothesis is rejected for point 1004. TABLE 3. Differences between the UWB position estimations and the correct coordinates at points 1002 and 1004. Taking a closer look at the results of point 1004, the ambiguity problem of the circular lateration can be observed. The random measurement error can be large enough to cover two possible intersections in circular lateration, thus the estimator may oscillate between two solutions. Two main causes for this ambiguity are a weak network configuration and the large ranging errors (see FIGURE 7). FIGURE 7. Ambiguity of lateration. Ad Hoc UWB Sensor Network We have also carried out tests on an indoor ad hoc sensor network using different coordinate estimation methods. Indoor distance measurements typically do not follow a normal or Gaussian error distribution but rather a Gaussian mixture distribution, which demands the use of a robust estimation method. Our results showed that the maximum likelihood estimation technique performs better than conventional least squares for this type of network. Conclusion Ultra-wideband technology is an effective positioning method for short-range applications with decimeter-level accuracy. The coverage area can be extended with increasing network size. The technology can be used independently or as a component of an integrated positioning/navigation system. GPS-compromised outdoor situations and indoor applications can be supported by UWB in permanent and ad hoc network configurations. While UWB technology is relatively less affected by environmental conditions, signal propagation through objects or other non-line-of-sight conditions can reduce the reliability and accuracy. Acknowledgments This article is based, in part, on the paper “Performance Analysis of UWB Technology for Indoor Positioning,” presented at the 2014 International Technical Meeting of The Institute of Navigation, held in San Diego, Calif., Jan. 27–29, 2014. Manufacturer The experiments discussed in the article used a Time Domain Corp. PulsON 300 UWB radio system. ZOLTAN KOPPANYI received his B.Sc. degree in civil engineering in 2010 and his M.Sc. in land surveying and GIS in 2012, both from Budapest University of Technology and Economics (BME), Hungary. He also received a B.Sc. in computer science from the Eötvös Loránd University, Budapest, in 2011. He is a Ph.D. student at BME and was a visiting scholar at the Ohio State University (OSU), Columbus, in 2013. His research area is human mobility pattern analysis and indoor navigation. CHARLES K. TOTH is a research professor in the Department of Civil, Environmental and Geodetic Engineering at OSU. He received an M.Sc. in electrical engineering and a Ph.D. in electrical engineering and geo-information sciences from the Technical University of Budapest, Hungary. His research expertise covers broad areas of 2D/3D signal processing; spatial information systems; high-resolution imaging; surface extraction, modeling, integrating and calibrating of multi-sensor systems; multi-sensor geospatial data acquisition systems, and mobile mapping technology. DOROTA A. GREJNER-BRZEZINSKA is a professor in geodetic science, and director of the Satellite Positioning and Inertial Navigation (SPIN) Laboratory at OSU. Her research interests cover GPS/GNSS algorithms, GPS/inertial and other sensor integration for navigation in GPS-challenged environments, sensors and algorithms for indoor and personal navigation, and Kalman and non-linear filtering. Further Reading • Authors’ Conference Paper “Performance Analysis of UWB Technology for Indoor Positioning” by Z. Koppanyi, C.K. Toth, D.A. Grejner-Brzezinska, and G. Jozkow in Proceedings of ITM 2014, the 2014 International Technical Meeting of The Institute of Navigation, San Diego, Calif. January 27–29, 2014, pp. 154–165. • U.S. Regulations on Ultra-Wideband “Ultra-Wideband Operation” in Code of Federal Regulations, Title 47, Chapter I, Subchapter A, Part 15, U.S. National Archives and Records Administration, Washington, D.C., October 1, 2014. Available online. • Introduction to Ultra-Wideband “History and Applications of UWB” by M.Z. Win, D. Dardari, A.F. Molisch, W. Wiesbeck, and J. Zhang in Proceedings of the Institute of Electrical and Electronics Engineers, Vol. 97, No. 2, February 2009, pp. 198–204, doi: 10.1109/JROC.2008.2008762. “Ultra-Wideband and GPS: Can They Co-exist” by D. Akos, M. Luo, S. Pullen, and P. Enge in GPS World, Vol. 12, No. 9, September 2001, pp. 59–70. • Ultra-Wideband Signal Peak Detection and Ranging Ultra-Wideband Ranging for Low-Complexity Indoor Positioning Applications by G. Bellusci, Ph.D. dissertation, Delft University of Technology, Delft, The Netherlands, 2011. “Ultra-Wideband Range Estimation: Theoretical Limits and Practical Algorithms” by I. Guvenc, S. Gezici, and Z. Sahinoglu in Proceedings of ICUWB2008, the 2008 Institute of Electrical and Electronics Engineers International Conference on Ultra-Wideband, Hannover, Germany, September 10–12, 2008, Vol. 3, pp. 93–96, doi: 10.1109/ICUWB.2008.4653424.  • Received Signal Strength Fingerprinting “Increased Ranging Capacity Using Ultrawideband Direct-Path Pulse Signal Strength with Dynamic Recalibration” by B. Dewberry and W. Beeler in Proceedings of PLANS 2012, the Institute of Electrical and Electronics Engineers / Institute of Navigation 2012 Position, Location and Navigation Symposium, Myrtle Beach, S.C., April 23–26, 2010, pp. 1013–1017, doi: 10.1109/PLANS.2012.6236843. “Indoor Ultra-Wideband Location Fingerprinting” by H. Kröll and C. Steiner in Proceedings of IPIN 2010, the 2010 International Conference on Indoor Positioning and Indoor Navigation, Zurich, September 15–17, 2010, pp. 1–5, doi: 10.1109/IPIN.2010.5648087. • Ultra-Wideband Time-of-Arrival and Angle-of-Arrival“Ultra-Wideband Time-of-Arrival and Angle-of-Arrival Estimation Using Transformation Between Frequency and Time Domain Signals” by N. Iwakiri and T. Kobayashi in Journal of Communications, Vol. 3, No. 1, January 2008, pp. 12–19, 10.4304/jcm.3.1.12-19. • Maxwell’s Equations “The Long Road to Maxwell’s Equations” by J.C. Rautio in IEEE Spectrum, Vol. 51, No. 12, December 2014, North American edition, pp. 36–40 and 54–56, doi: 10.1109/mspec.2014.6964925. A Student’s Guide to Maxwell’s Equations by D. Fleisch, Cambridge University Press, Cambridge, U.K., 2008.