GPS World

Tag: sensor network

  • Innovation: Where Are We?

    Innovation: Where Are We?

    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
    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).
    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.
    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.
    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

    1. Individual sensor calibration is the approach where the sensor delays are determined separately, for example, Inno-Cal-E1, where Inno-Cal-E2 is the measured range between stations A and B, Inno-Cal-E3and Inno-Cal-E4 are the calibration functions, and Inno-Cal-E5 is the corrected range.
    2. 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 Inno-Cal-E6.

    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.
    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.
    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.
    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.
    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:

    Inno-Eq1

    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.
    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.
    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.
    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.

  • Challenged Positions: Dynamic Sensor Network, Distributed GPS Aperture, and Inter-nodal Ranging Signals

    A performance assessment demonstrates the ability of a networked group of users to locate themselves and each other, navigate, and operate under adverse conditions in which an individual user would be impaired. The technique for robust GPS positioning in a dynamic sensor network uses a distributed GPS aperture and RF ranging signals among the network nodes.

    By Dorota A. Grejner-Brzezinska, Charles Toth, Inder Jeet Gupta, Leilei Li, and Xiankun Wang

    In situations where GPS signals are subject to potential degradations, users may operate together, using partial satellite signal information combined from multiple users. Thus, collectively, a network of GPS users (hereafter referred to as network nodes) may be able to receive sufficient satellite signals, augmented by inter-nodal ranging measurements and other sensors, such as inertial measurement unit (IMU), in order to form a joint position solution.

    This methodology applies to numerous U.S. Department of Defense and civilian applications, including navigation of dismounted soldiers, emergency crews, on-the-fly formation of robots, or unmanned aerial vehicle (UAV) swarms collecting intelligence, disaster or environmental information, and so on, which heavily depend on availability of GPS signals. That availability may be degraded by a variety of factors such as loss of lock (for example, urban canyons and other confined and indoor environments), multipath, and interference/jamming. In such environments, using the traditional GPS receiver approach, individual or all users in the area may be denied the ability to navigate.

    A network of GPS receivers can in these instances represent a spatially diverse distributed aperture, which may be capable of obtaining gain and interference mitigation. Further mitigation is possible if selected users (nodes) use an antenna array rather than a single-element antenna. In addition to the problem of distributed GPS aperture, RF ranging among network nodes and node geometry/connectivity forms another topic relevant to collaborative navigation. The challenge here is to select nodes, which can receive GPS signals reliably, further enhanced by the distributed GPS aperture, to serve as pseudo-satellites for the purpose of positioning the remaining nodes in the network.

    Collaborative navigation follows from the multi-sensor navigation approach, developed over the past several years, where GPS augmentation was provided for each user individually by such sensors as IMUs, barometers, magnetometers, odometers, digital compasses, and so on, for applications ranging from pedestrian navigation to georegistration of remote sensing sensors in land-based and airborne platforms.

    Collaborative Navigation

    The key components of a collaborative network system are

    • inter-nodal ranging sub-system (each user can be considered as a node of a dynamic network);
    • optimization of dynamic network configuration;
    • time synchronization;
    • optimum distributed GPS aperture size for a given number of nodes;
    • communication sub-system; and
    • selection of master or anchor nodes.

    Figure 1 illustrates the concept of collaborative navigation in a dynamic network environment. Sub-networks of users navigating jointly can be created ad hoc, as indicated by the circles. Some nodes (users) may be parts of different sub-networks.

    FIGURE 1. Collaborative navigation concept.
    FIGURE 1. Collaborative navigation concept.

    In a larger network, the selection of a sub-network of nodes is an important issue, as in case of a large number of users in the entire network, computational and communication loads may not allow for the entire network to be treated as one entity. Still, information exchange among the sub-networks must be assured.

    Conceptually, the sub-networks can consist of nodes of equal hierarchy or may contain master (anchor) nodes that normally have a better set of sensors and collect measurements from all client nodes to perform a collaborative navigation solution. Table 1 lists example sensors and techniques that can be used in collaborative navigation.

    TABLE 1. Typical sensors for multi-sensor integration: observables and their characteristics, where X,Y,Z are the 3D coordinates, vx, vy, vz are the 3D velocities,
    TABLE 1. Typical sensors for multi-sensor integration: observables and their characteristics, where X,Y,Z are the 3D coordinates, vx, vy, vz are the 3D velocities,

    The concept of a master node is also crucial from the stand point of distributed GPS aperture, where it is mandatory to have master nodes responsible for combining the available GPS signals.

    Master nodes or some selected nodes will need anti-jamming protection to be effective in challenged electromagnetic (EM) environments. These nodes may have stand-alone anti-jamming protection systems, or can use the signals received by antennas at various nodes for nulling the interfering signals.

    Research Challenges

    Finding a solution that renders navigation for every GPS user within the network is challenging. For example, within the network, some GPS nodes may have no access to any of the satellite signals, and others may have access to one or more satellite signals. Also, the satellite signals received collectively within the network of users may or may not have enough information to determine uniquely the configuration of the network.

    A methodology to integrate sensory data for various nodes to find a joint navigation solution should take into account:

    • acquisition of reliable range measurements between nodes (including longer inter-nodal distances);
    • limitation of inter-nodal communication (RF signal strength);
    • assuring time synchronization between sensors and nodes; and
    • limiting computational burden for real time applications.

    Distributed GPS Apertures

    In the case of GPS signal degradation due to increased path loss and radio frequency interference (RFI), one can use an antenna array at the receiver site to increase the gain in the satellite signal direction as well as steer spatial nulls in the interfering signal directions. For a network of GPS users, one may be able to combine the signals received at various receivers (nodes) to achieve these goals (beam pointing and null steering); see Figure 2.

    Figure 2.Distributed antenna array.
    Figure 2. Distributed antenna array.

    However, a network of GPS users represents a distributed antenna aperture with large (hundreds of wavelengths) inter-element spacing. This large thinned antenna aperture has some advantage and many drawbacks. The main advantage is increased spatial resolution which allows one to discriminate between signals sources with small angular separations. The main drawback is very high sidelobes (in fact, grating lobes) which manifest as grating nulls (sympathetic nulls) in null steering. The increased inter-element spacing will also lead to the loss of correlation between the signals received at various nodes. Thus, space-only processing will not be sufficient to increase SNR by combining the satellite signals received at various nodes. One has to account for the large delay between the signals received at various nodes.

    Similarly, for adaptive null steering, one has to use space-time adaptive processing (STAP) for proper operation. These research challenges must be solved for distributed GPS aperture to become a reality:

    • Investigate the increase in SNR that can be obtained by employing distributed GPS apertures (accounting for inaccuracies in the inter-nodal ranging measurements).
    • Investigate the improvement in the signal-to-interference-plus-noise ratio (SINR) that can be obtained over the upper hemisphere when a distributed GPS aperture is used for adaptive null steering to suppress RFI in GPS receivers. Obtain an upper bound for inter-node distances.
    • Based on the results of the above two investigations, develop approaches for combined beam pointing and null steering using distributed GPS apertures.

    Inter-Nodal Ranging Techniques

    In a wireless sensor network, an RF signal can be used to measure ranges between the nodes in various modes. For example, WLAN observes the RF signal strength, and UWB measures the time of arrival, time difference of arrival, or the angle of arrival. There are known challenges, for example, signal fading, interference or multipath, to address for a RF-based technique to reliably serve as internodal ranging method.

    Ranging Based on Optical Sensing. Inter-nodal range measurements can be also acquired by active and passive imaging sensors, such as laser and optical imaging sensors. Laser range finders that operate in the eye-safe spectrum range can provide direct range measurements, but the identification of the object is difficult. Thus, laser scanners are preferred, delivering 3D data at the sensor level. Using passive imagery, such as digital cameras, provides a 2D observation of the object space; more information is needed to recover 3D information; the most typical techniques is the use of stereo pairs or, more generally, multiple-image coverage. The laser has advantages over optical imagery as it preserves the 3D object shapes, though laser data is more subject to artifacts due to non-instantaneous image formation.

    In general, regardless whether 2D or 3D imagery is used, the challenge is to recognize the landmark under various conditions, such as occlusions and rotation of the objects, when the appearance of the landmark alternates and the reference point on the landmark needs to be accurately identified, to compute the range to the reference point with sufficient accuracy.

    Network Configuration

    Nodes in the ad hoc network must be localized and ordered considering conditions, such as type of sensors on the node (grade of the IMU), anti-jamming capability, positional accuracy, accuracy of inter-nodal ranging technique, geometric configuration, computational cost requirements, and so on. There are two primary types of network configurations used in collaborative navigation: centralized and distributed.

    • Centralized configuration is based on the concept of server/master and client nodes.
    • Distributed configuration refers to the case where nodes in the network can be configured without a master node, that is, each node can be considered equal with respect to other nodes.

    Sensor Integration

    The selection of data integration method is an important task; it should focus on arriving at an optimal solution not only in terms of the accuracy but also taking the computational burden into account. The two primary options are centralized and decentralized extended Kalman filter (EKF).

    • Centralized filter (CF) represents globally optimal estimation accuracy for the implemented system models.
    • Decentralized filter (DF) is based on a collection of local filters whose solutions can be combined by a single master filter. DFs can be further categorized based on information-sharing principles and implementation modes.

    Centralized, Decentralized EKF. These two methods can provide comparable results, with similar computational costs for networks up to 30 nodes. Figures 3–5 describe example architectures of centralized/decentralized EKF algorithms.

    In Figure 3, all measurements collected at the nodes and the inter-nodal range measurements are processed by a single centralized EKF. Figures 4 and 5 illustrate the decentralized EKF with the primary difference between them being in the methods of applying the inter-nodal range measurements. The range measurements are integrated with the observations of each node by separate EKF per node in Figure 4, while Figure 5 applies the master filter to integrate the range measurements with the EKF results of all participating nodes.

    FIGURE 3. Centralized extended Kalman filter.
    FIGURE 3. Centralized extended Kalman filter.
    FIGURE 4. Decentralized EKF, option 1.
    FIGURE 4. Decentralized EKF, option 1.
    FIGURE 5. Decentralized EKF, option 2.
    FIGURE 5. Decentralized EKF, option 2.

    Performance Evaluation

    To provide a preliminary performance evaluation of an example network operating in collaborative mode, simulated data sets and actual field data were used. Figure 6 illustrates the field test configuration, showing three types of nodes, whose trajectories were generated and analyzed.

    FIGURE 6. Collaborative navigation field test configuration.
    FIGURE 6. Collaborative navigation field test configuration.

    Nodes A1, A2, and A3 were equipped with GPS and tactical grade IMU, node B1 was equipped with GPS and a consumer grade IMU, and node C1 was equipped with a consumer grade IMU only. The following assumptions were used: all nodes were able to communicate; all sensor nodes were time-synchronized; nodal range measurements were simulated from GPS coordinates of all nodes; and the accuracy of GPS position solution was 1–2 meters/coordinate (1s); the accuracy of inter-nodal range measurements was 0.1meters (1s); all measurements were available at 1 Hz rate; the distances between nodes varied from 7 to 70 meters.

    Individual Navigation Solution. To generate the navigation solution for specific nodes, either IMU or GPS measurements or both were used. Since the reference trajectory was known, the absolute value of the differences between the navigation solution (trajectory) and the reference trajectory (ground truth) were considered as the navigation solution error. Figure 7 illustrates the absolute position error for the sample of 60 seconds of simulated data, with a 30-second GPS outage for nodes A1, A2, A3 and B1 (node C1 is not shown, as its error in the end of the test period was substantially bigger than that of the remaining nodes. Table 2 shows the statistics of the errors of each individual node’s trajectory for different sensor configurations.

    FIGURE 7. GPS/IMU positioning error for A1, A2, A3, B1 (includes a 30-second GPS outage.)
    FIGURE 7. GPS/IMU positioning error for A1, A2, A3, B1 (includes a 30-second GPS outage.)

    Table-2

    Collaborative Solution. In this example, collaborative navigation is implemented after acquiring the individual navigation solution of each node, which was estimated with the local sensor measurements. The collaborative navigation solution is formed by integrating the inter-nodal range measurements to other nodes in a decentralized Kalman filter, which is referred to as “loose coupling of inter-nodal range measurements.” The test results of different scenarios are listed in Table 3. For cases labeled “30-sec GPS outage,” the GPS outage is assumed at all nodes that are equipped with GPS. The results listed in Table 3 indicate a clear advantage of collaborative navigation for nodes with tactical and consumer grade IMUs, particularly during GPS outages. When GPS is available (see, for example, node A1) the individual and collaborative solutions are of comparable accuracy.

    Table-3

    The next experiment used tight coupling of inter-nodal range measurements at each node’s EKF in order to calibrate observable  IMU errors even during GPS outages. In addition, varying numbers of master nodes are considered in this example. The tested data set was 600 seconds long, with repeated simulated 60-second GPS gaps, separated by 10-second periods of signal availability. The inter-nodal ranges were ~20 meters.

    Table 4 and Figure 8 summarize the navigation solution errors for collaborative solution of node C1 equipped with consumer grade IMU only, supported by varying quality other nodes. The error of the individual solution for this node in the end of the 600-second period reach nearly 250 kilometers (2D). Even for the case with a single anchor node (A1), the accuracy of the 2D solution is always better than 2 meters. Another 900-second experimental data with repeated GPS 60-second gaps on B1 node was analyzed with inter-nodal ranging up to 150 meters. Table 5 summarizes the results for C1 node.

    Table-4

    FIGURE 8. Absolute error for IMU-only and collaborative navigation solutions of C1 (GPS outage.)
    FIGURE 8. Absolute error for IMU-only and collaborative navigation solutions of C1 (GPS outage.)

    Table-5

    Future Work

    Collaborative navigation in decentralized loose integration mode improves the accuracy of a user with consumer grade IMU from several hundreds of meters (2D) to ~16 m (max) for a 30-s GPS gap, depending on the number of inter-nodal ranges and availability of GPS on other nodes. For a platform with GPS and consumer grade IMU (node B1) the improvement is from a few tens of meters to below 10 m.

    Better results were obtained when tight integration mode was applied, that is, inter-nodal range measurements were included directly in each EKF that handles measurement data collected by each individual node (architecture shown in Figure 4). For repeated 60-second GPS gaps, separated by 10-second signal availability, collaborative navigation maintains the accuracy at ~1–2 meter level for entire 600 s tested for nodes C1 and B1.

    Even though the preliminary simulation results are promising, more extended dynamic models and operational scenarios should be tested. Moreover, it is necessary to test the decentralized scenarios 1 and 2 (Figures 4–5) and then compare them with the centralized integration model shown in Figure 3. Ad hoc network formation algorithm should be further investigated.

    FIGURE 9. Absolute errors in collaborative navigation solutions of C1.
    FIGURE 9. Absolute errors in collaborative navigation solutions of C1.

    The primary challenges for future research are:

    • Assure anti-jamming protection for master nodes to be effective in challenged EM environments. These nodes can have stand alone anti-jamming protection system, or can use the signals received by antennas at various nodes for nulling the interfering signals.
    • Since network of GPS users, represents a distributed antenna aperture with large inter-element spacing, it can be used for nulling the interfering signals. However, the main challenge is to develop approaches for combined beam pointing and null steering using distributed GPS apertures.
    • Formulate a methodology to integrate sensory data for various nodes to obtain a joint navigation solution.
    • Obtain reliable range measurements between nodes (including longer inter-nodal distances).
    • Assess limitations of inter-nodal communication (RF signal strength).
    • Assure time synchronization between sensors and nodes.
    • Assess computational burden for the real time application.

    Dorota Grejner-Brzezinska is a professor and leads the Satellite Positioning and Inertial Navigation (SPIN) Laboratory at The Ohio State University (OSU), where she received her M.S. and Ph.D. in geodetic science. 
Charles Toth is a senior research scientist at OSU’s Center for Mapping. He received a Ph.D. in electrical engineering and geoinformation sciences from the Technical University of Budapest, Hungary.
Inder Jeet Gupta is a research professor in the Electrical and Computer Engineering Department of OSU. He received a Ph.D. in electrical engineering from OSU.
Leilei Li is a visiting graduate student at SPIN Lab at OSU.
Xiankun Wang is a Ph.D. candidate in geodetic science at OSU