The world of indoor location continues to evolve, with a number of variations on when and under what circumstances you might be able to wander around your local mall getting directions to your favorite ice-cream store on your iPhone. Some malls are mapped, some are not, some (most) have Wi-Fi hot-spots and Bluetooth beacons, some may be in areas where outdoor directional beacon are being tested and their signals penetrate indoors. But the thing they have in common is that most seem to lose GPS/GNSS signals once you get a few tens of meters away from the front entrance.
Some companies have managed to make indoor location in your mall work with a combination of GPS, plus all the RF signals that can be received, plus using inertial and/or magnetic sensors in your mobile phone, and sometimes also with detailed indoor map-matching — but no-one seems to do this in a simple, consistent, reproducible way for any store wanting to ensure you arrive at their door, or for a telecommunication industry wishing to standardize how it works for E911 and then field it everywhere.
So I’ve actually been looking for an indoor location outfit who might have found a consistent solution that can work from place to place — by that I mean from mall to mall, city to city, country to country, even continent to continent, and every time after first set-up — and I suspect that I may have now found one.
The team at iPosi in Denver is still working on their solution, but they have run some pretty convincing demonstrations in some very challenging locations, so they may have found an inside edge that could take them many places (sorry, about that pun).
While iPosi’s headquarters are is in Denver, the company also has labs in Boulder and offices in Dallas. It hasn’t been around too long — since 2011 — but it has been busy filing patents for the key technologies that drive their location technology. Of 40 total patents in the pipeline, five have been granted or allowed, 15 are pending, and 20 more are in development. With only six employees, iPosi is a small outfit, but it also gets design assistance from a European design center for other GNSS signal designs.
One of the key GNSS elements the iPosi team has going for them is an in-house developed GPS receiver with a sensitivity of -175 dBm. If you could get any sort of a signal deep inside a building, it’s possible that they might be able to receive it. But, for sure, anything you would receive deep inside would be just multipath – right? There are other pieces to this story however.
The iPosi system design is based on mobile phone “small-cell” installations. The world now has around 100 million multi-floor buildings with an average of eight floors each, and most buildings present some level of attenuation for external mobile phone cell-tower signals — never mind GPS signals. Most of us should be familiar with having to leave meetings to get “bars.” holding the phone up against a window, walking around to catch reflected indoor signals, and eventually having to leave the building and be with a group of other people who are doing the same thing – looking for a clear cell-phone signal to make a call. In the Northern U.S. and Canada in the winter, this can even be hazardous to your health!
So small cells behave as basically indoor “repeaters” of mobile phone signals. iPosi believes that an average of four of these repeaters are needed to broadcast sufficient signal on each average building floor. So iPosi embeds each small cell with one of its high-sensitivity receivers. Once positioned indoors, and over time, the receivers self-locate inside the building. Currently, installation of small cells can be somewhat cumbersome and time consuming, but non-GPS small cells can be located during installation using traditional indoor surveying techniques — such as laser-based measurements. Either that, or no measurements are made at all, and no device location information is associated with a device.
Small-cell setup.
With each small cell equipped with a high-sensitivity receiver — with especially clever algorithms to differentiate and interpret multipath over time — each device goes to work transmitting repeater mobile-phone signals and eventually self-locates. Contained within these signals are each small-cell location, plus a timing message that allows any standards-compliant handset to calculate range to each transmitter and to perform an OTDOA (Observed Time Difference Of Arrival) position fix.
If the small-cell location at install is also fed into the GIS database for the building and, more importantly, for the local area, the E911 “dispatchable address” for that building has GPS-level accuracy. And first responders will also have numerous other small-cell location aids within the building.
Another detail is that the iPosi receiver uses A-GNSS (including ephemeris) data, so it only needs small snapshots of signal to deduce position. This means very low power consumption for positioning at the small cell, which is good because small cells are mostly battery powered.
So, does it work? In FCC E911 demonstrations at the Omni Hotel in San Francisco, iPosi consistently located to within 50 meters horizontally and a few meters vertically.
Masonry, turn-of-20th-century construction
Approximately 15 floors, similar to surrounding
Test site: ninth floor hotel room
Horizontal error = 38 m, Vertical error = 9.5 m
There were several other tests in representative converted apartments, a modern four-story steel and concrete building, and inside a university auditorium. But the one that really caught my attention was the test iPosi ran in the basement of an engineering center.
Engineering center, lower basement 3.5 m below grade.
That’s 3.5 meters below grade! The iPosi receiver measurement system was able to determine that some of the signals were actually received directly from a GPS satellite — unbelievable! That’s through concrete and stone down to 3.5 meters below grade with a simple patch antenna!
Most of your average mall locations are not as location-hazardous as this basement test. Its possible that finding your way to the closest indoor ice-cream store could soon be child’s play, which will be especially helpful for the kids with smartphones.
iPosi is working with some of the key equipment suppliers in the industry. It’s quite likely that some of its evaluation sites could soon evolve into operational indoor location facilities. And iPosi’s argument is that its indoor location solution is truly scalable or can be readily standardized — as the telecom companies apparently would love for all indoor location technology to be — so the iPosi solution can readily transition across borders and countries, and roll out could be greatly simplified.
Tony Murfin
Hard to say if this will be the winning indoor location solution, but in the end the market will decide if it really is a scalable, simple solution, and if it will succeed — right?
When subjected to very strong interference, a GNSS receiver can be totally blinded and stop working. This is often the scope of intentional jammers. However, in a number of cases the presence of interference is severe enough to significantly decrease receiver performance, but not so much as to make the receiver lose its lock on the satellite signals or blind the acquisition of the satellite signals.
Such intermediate power values turn out to be the most dangerous cases, because sometimes they cannot be detected, but lead to a worsening of the positioning performance. The accuracy of the position solution depends on, among others, the quality of the pseudorange measurements and/or the phase measurements. Thus, when radio-frequency interference (RFI) degrades the pseudorange and phase measurements or induces cycle slips on the phase measurements, the accuracy of the position solution will decrease.
Impact on the Front End
The front-end filters the incoming signal, demodulating it to the chosen intermediate frequency before performing the analog-to-digital conversion (ADC).We must consider the presence in the front end of the adjustable gain control (AGC) between the analog portion of the front end and the ADC. When the GNSS band is interference-free, AGC gain depends almost exclusively on thermal noise, since the received signal power is below that of the thermal noise floor. When in-band interference is present, the AGC will squeeze the incoming signal to match the maximum dynamics of the ADC, causing a reduction of the amplitude of the useful signal, which may be lost. This may typically happen in the presence of some kind of wide-band interference (WBI) spread over a bandwidth larger than the passband of the front-end filter.
With narrow-band (NBI) or continuous-wave interference (CWI), statistics of the digital signal at the ADC output are also affected. In this case the AGC can still compress the input signal to avoid a stronger saturation, but the following receiver stages will have to deal with a GNSS contribution quantized only on lower levels.
In the presence of stronger interference, even the other components of the front end (filters and amplifiers) may be led to work outside of their nominal regions, generating nonlinear effects or clipping phenomena (in which the signal amplitude exceeds the hardware’s capability to treat them). In both cases, spurious harmonics are generated and mixed with the useful signal in the front end itself.
Impact on the Acquisition Stage
If the interference is not driving the AGC/ADC to full saturation, the acquisition module is still able to perform its task, processing the interfered signal to estimate the code phase and the Doppler shift with respect to the local code. The correlation with the local code can be seen as a spreading operation followed by a filter.
Figure 1. GPS L1 C/A acquisition search space in (a) an interference-free environment and in the presence of (b) –140 dBW in-band CWI; (c) –135 DBW in-band CWI; (d) –130 dBW in-band DWI.
Figure 1 showsthe acquisition search space for different levels of theinterfering power of a CWI from –140 to –130 dBW compared to the interference-free case. The search spaces depicted for the four scenarios are achieved using 1 ms of coherent integration time and three non-coherent accumulations, and the peak-to-noise-floor separation defined as
is considered as a figure of merit. The value of αmean decreases as the interfering power increases, thus increasing the probability of a false alarm. With the increasing power of the CWI, a modulation effect in the search space floor in the Doppler domain dimension can be observed. Such an effect is mainly determined by the new harmonics components generated by the multiplication between the locally generated carrier and received CWI. Such an effect also depends on how the interfering signal and the useful GNSS signal are combined at the entrance to the acquisition block, which in turn depends on the random variables φ0 and θint.
In the presence of WBI, a different effect is observed in the acquisition search space. Considering a band-limited Gaussian white noise spread all over the GNSS useful filtered signal components, the effect on the CAF envelop is an increase in the noise floor. This increases the search space noise floor. The presence of additive band-limited noise causes a uniform increase in the noise floor tin the search space that might mask the correct correlation peak and thus fool the acquisition process.
Impact on the Tracking Stage
Interference impact on the tracking stage has a direct consequence on the quality of the measured pseudorange. Harmful interfering signals increase the variance of the time-of-arrival (TOA) estimate by the discriminator and modify the shape of the S-curve of the code discriminator, thus creating in some cases a bias in the measurements.
Figure 2 depicts outputs of the early-prompt-late correlators. In the presence of in-band CWI and of NBI, the interference is injected 9.3 seconds after the beginning of the tracking stage where the receiver is correctly locked on the received signal. A CWI, shifted 200 kHz with respect to the signal intermediate frequency (in correspondence with a C/A code spectrum line), increases the noise at the correlators outputs and leads to harmonic behavior of the early-prompt-late correlator outputs.
Figure 2. GPS L1 C/A code tracing error comparison: coherent and non-coherent early-late processing (CELP and NELP).
NBI increases the variance of the correlators’ outputs; this directly increases the pseudorange error and the noise on the receiver phase measurements. Additive band-limited noise leads to an overall increase in the carrier phase discriminator output variance over the 3σ threshold, which for a PLL two-quadrant arctangent discriminator is 45 degrees. When in presence of strong CWI, a sudden jump of the phase discriminator output is detected as soon as the CWI is injected onto the received signal.
Impact on the Estimated Signal-to-Noise Ratio
Sticking to the definition of C/N0 as the ratio between the received power and the power spectral density due to thermal noise at the input of the receiver, the presence of interference should not change the value, since the thermal noise is not increasing. However, the C/N0 value provided by the receivers is estimated on the basis of the correlator outputs at the tracking stage. For this reason the estimation is affected by the presence of the additional (nonthermal) noise generated by the interference. The variation of the C/N0 can also be used as observable for interference (or other threats) detection.
Chapters: The Interference Threat; Classification of Interfering Sources and Analysis of the Effects on GNSS Receivers; The Spoofing Menace; Analytical Assessment of Interference on GNSS Signals; Interference Detection Strategies; Classical Digital Signal Processing Countermeasures to Interference in GNSS; Interference Mitigation Based on Transformed Domain Techniques; Antispoofing Techniques for GNSS. The book is intended for members of the engineering/scientific community with pre-existing knowledge of satellite navigation principles and GNSS.
FabIo Dovis holds a Ph.D. in elecronics and communications engineering from Politecnico di Torino, Italy, where he is an associate professor.
By Thorsten Lück, Günter Heinrichs, IFEN GmbH, and Achim Hornbostel, German Aerospace Center
This article discusses the GALANT adaptively steered antenna array and receiver and demonstrates the test scenarios generated with the GNSS simulator. Exemplary results of different static and dynamic test scenarios are presented, demonstrating the attitude determination capabilities as well as the interference detection and mitigation capabilities.
The vulnerability of GNSS to radio frequency interference and spoofing has become more and more of a concern for navigation applications requiring a high level of accuracy and reliability, for example, safety of life applications in aviation, railway, and maritime environments.In addition to pure power jamming with continuous wave (CW), noise or chirp signals, cases of intentional or unintentional spoofing with wrong GNSS signals have also been reported.
Hardware simulations with GNSS constellation signal generators enable the investigation of the impact of radio interference and spoofing on GNSS receivers in a systematic, parameterized and repeatable way. The behavior of different receivers and receiver algorithms for detection and mitigation can be analyzed in dependence on interference power, distance of spoofers, and other parameters. This article gives examples of realistic and advanced simulation scenarios, set up for simulation of several user antennas simultaneously.
The professional-grade high-end satellite navigation testing and R&D device used here is powerful, easy to use, and fully capable of multi-constellation / multi-frequency GNSS simulations for safety-of-life, spatial and professional applications. It provides all L-band frequencies for GPS, GLONASS, Galileo, BeiDou, QZSS, SBAS and beyond in one box simultaneously. It avoids the extra complexity and cost of using additional signal generators or intricate architectures involving several hardware boxes, and offers full control of scenario generation. A multi-RF capable version provides up to four independent RF outputs and a master RF output that combines the RF signal of each of the up to four individual RF outputs.
Each individual RF output is connected to one or more “Merlin” modules (the core signal generator module for one single carrier) allowing simulation of up to 12 satellites per module. Because of the flexible design of the Merlin module, each one can be configured to any of the supported L-band frequencies.
As one chassis supports up to nine individual Merlin modules, different Multi-RF combinations are feasible:
two RF outputs with up to four modules each
three RF outputs with up to three modules each
four RF outputs with up to two modules each.
With these configurations, the user can simulate different static or dynamic receivers or even one receiver with multiple antennas, covering such challenging scenarios as ground networks, formation flying or use of beam-forming antennas.
As the user is free to assign each individual module to a dedicated simulated antenna, the user could also employ up to nine modules to simulate nine different carrier signals for one single antenna using the master RF output, thus simulating the complete frequency spectrum for all current available GNSS systems in one single simulation.
All modules are calibrated to garantee a carrier phase coherency of better than ±0.5°. Figure 1 shows the output at the RF master of two modules assigned to the same carrier but with a phase offset of 180°.
Figure 1. Carrier-phase alignment of the high-end simulator with six modules compared to the first module.
Theoretically, the resulting signal should be zero because of the destructive interference. In practice, a small residual signal remains because of component tolerance, small amplitude differences and other influences. Nevertheless the best cancellation can be seen at this point. The phase accuracy can now simply be estimated from the measured power level of the residual signal:
(1)
(2)
with
This means that the sum of two sine waves with the same frequency gives another sine wave. It has again the same frequency, but a phase offset and its amplitude is changed by the factor A. The factor A does affect the power level. If φ is 180° then A is 0, which means complete cancellation.
So A shows the power of the resulting signal relative to the single sine wave. It can also be transformed to dB:
(3)
Figure 2 shows the carrier suppression as a function of carrier phase offset with a pole at 180ϒ.
Figure 2. Carrier suppresion as a function of phase delay.
The factory calibration aligns the modules to a maximum of 0.5ϒ misalignment. The measured suppresion therefore shall be better than 41.18 dBc. In practice, the residual signal is also caused by other influences, so that the actual phase alignment can be expected to be much better.
With four RF outputs, the received signal of a four element antenna can be configured very easily. Figure 3 shows the dialog to configure a four-element antenna with the geometry shown in Figure 4. Note that the antenna elements are configured in the body-fixed system with the x-axis to front and the y-axis to the right (inline with a north-east-down, NED, system when facing to north), while the geometry shown in Figure 4 follows an east-north-up (ENU) convention.
Figure 3. Configuration of individual antennas per receiver.Figure 4. Geometry of the GALANT four-element phased-array antenna (view from top).
The following sections give an overview of multi-antenna systems and discuss results from a measurement campaign of the German Aerospace Center (DLR) utilizing the simulator and the DLR GALileo ANTenna array (GALANT) four-element multi-antenna receiver.
Multi-Antenna Receivers
Multi-antenna receivers utilize an antenna array with a number of antenna elements. The signals of each antenna element are mixed down and converted from analog to digital for baseband processing. In the baseband, the signals received by the different antenna elements are multiplied with complex weighting factors and summed. The weighting factors are chosen in such a way that the received signals from each antenna element cancel out into the direction of the interferers (nulling) and additionally, for advanced digital beamforming, such that the gain is increased into the direction of the satellites by forming of individual beams to each satellite. Because all these methods work with carrier phases, it is important that in the simulation setup, the signals contain the correct carrier phases at the RF-outputs of the simulator corresponding to the user satellite and user-interferer geometry, and the position and attitude of the simulated array antenna.
Figure 5 presents the geometry of a rectangular antenna array with 2×2 elements and a signal s(t) impinging from direction (ϕ, θ).
Figure 5. Parallel wavefront impinging on a rectangular array with 2×2 elements.
The spacings of the elements dx, dy are typically half a wavelength, but can also be less. The range difference for antenna element i relative to the reference element in the center of the coordinate system depends on the incident direction (ϕ, θ) and the position (m=0,1, n=0,1) of the element within the array:
(4)
The corresponding carrier phase shift is:
(5)
For CRPA and adaptive beam forming applications, the differential code delays may be neglected if they are small compared to the code chip length. However, it is essential that the carrier phase differences are precisely simulated, because they contain the information about the incident direction of the signal and are the basis for the array processing in the receiver. For instance, the receiver can estimate the directions of arrival of the incident signals from these carrier phase differences.
Now we consider a 2×2 array antenna. It can be simulated with the simulator with four RF outputs, where each output corresponds to one antenna element. In the simulator control software, a user with four antennas is set up, where the position of each antenna element is defined as an antenna position offset relative to the user position. In this approach, both differential code and carrier delays due to the simulated array geometry are taken into account, because the code and carrier pseudoranges are computed by the simulator for the position of each antenna element. However, the RF hardware channels of the receiver front-end may have differential delays against each other, which may even vary with time. If the direction of the satellites and interferers shall be estimated correctly by the receiver algorithms, a calibration signal is required to measure and compensate these differential hardware delays.
For the real antenna system, a binary phase-shift keying (BPSK) signal with zero delay for each antenna channel is generated by the array receiver and fed into the antenna calibration port. For the simulation, this calibration signal must also be generated by the constellation simulator.
In a simple way, a satellite in the zenith of the user antenna can be simulated, which has the same distance and delay to all antenna elements. Unfortunately, this simple solution includes some limitations to the simulated position and attitude of the user, because the user position must be at the Equator (if a “real” satellite is simulated in form of a geostationary satellite) and the antenna must not be tilted.
With a small customization of the simulator software, these limitations could be overcome. Figure 6 shows how to set up the generation of a reference signal. This reference signal can either be simulated as a transmitter directly above the user position, which follows the user position and thus allows also simulations offside the Equator, or simulated as a zero-range signal on all RF outputs, neglecting any geometry, which is the preferred method. The latter one is more or less identical to the reference/calibration signal generated by the receiver itself.
Figure 6. Configuration of a modulated reference signal.
The power level of this signal is held constant and is not affected by any propagation delay or attenuation simulated by the control center.
Attitude Determination
According to Figure 5, the phase difference measured between antenna elements is a function of the direction of arrival (DoA). Thus, the DoAs of the incident signals can be estimated from the phase differences. In the GALANT receiver, the DoAs are estimated by an EPSPRIT algorithm after correlation of the signals. Compared with the (known) positions of the GNSS satellites, this allows the estimation of the antenna array attitude. Figure 7 shows the sky-plot of simulated satellites as seen at receiver location (simulated on the right; reconstructed by the receiver from the decoded almanac in the middle and the DoA on the left). By comparison of the estimated DoAs of all satellites and the skyplot from the almanac, the attitude of the antenna is estimated (left). In addition, the attitude angles simulated by the simulator is given (right).
Figure 7. Simulating and estimating attitude with a multi-element antenna.
Simulation of Interference
It is possible to simulate some simple types of interference. Possible interference scenarios are:
Wideband Noise. By increasing the power of a single satellite of the same or another GNSS constellation, a wideband pseudo-noise signal can be generated. Using a geostationary satellite also enables simulating an interference source at low elevations and constant position. Use of power-level files also allow generation of scenarios with intermittent interference (switching on and off the interference) with switching rates up to 5 Hz.
CW or Multi-Carrier IF. By disabling the spreading code and navigation message, a CW signal can be generated. The simulator also allows configuration of subcarrier modulations. Without spreading code (or to be precise with a spreading code of constant zero) the generated signal will consist of two carriers symmetrically around the original signal carrier (for example, configuring a BOC(1,1) signal will create two CW signals at 1.57542 GHz ± 1.023 MHz, thus producing “ideal” interferer for the Galileo E1 OS signal.)
Depending on the number of Merlin modules per RF output, interference to signal ratios up to 80 dB could be realized, limited by a dynamic range of 40 dB within one module and additional 40 dB range between two modules. However, the maximum power level of one individual signal is currently limited to -90 dBm. If only one channel per module is used, the maximum power level of this single signal can be increased by another 18 dB (for example, by using one module solely for interference generation and another module for GNSS simulation).
Figure 8 shows the simulated geometry for an interference scenario based on wideband noise generated by a geostationary satellite, producing –90 dBm signal power at the receiver front end. The interference source is very near to the direction of PRN 22 with a jammer power of –90 dBm, resulting in a jammer to signal ratio of J/S = 25 dB.
Figure 8. Geometry for the wideband noise interference scenario.
Figure 9 shows the two-dimensional antenna pattern as a result of the beam-forming before and after switching on the interferer. The mitigation algorithm tries to minimize gain into the direction of the interferer. As this also decreases gain into the direction of the intended satellite, the C/N0 drops by approximately 10 dB for PRN 22, because its main beam is shifted away from the interference direction. For satellites in other directions, the decrease in C/N0 is less: compare Figure9with Figure 10. However, the receiver still keeps tracking the satellite. After switching of beamforming, the signal is lost.
Figure 9. Beamforming for PRN 22 (light green line in lower plot) to mitigate for interference.Figure 10. Tracking is lost after switching off beamforming for individual channels (light blue, purple) and all channels (at the end of the plot).
Simulation of Spoofing
The simulation of a spoofing signal requires twice the resources as the real-world scenario, as every “real” LoS-signal must also be generated for the spoofing source. A simulation of an intentional spoofer who aims to spoof a dedicated position in this context is, however, very similiar to the simulation of a repeater ([un-]intentional interferer) device:
The repeater (re-)transmits the RF signal received at its receiver position. A receiver tracking this signal will generate the position of the repeater location but will observe an additional local clock error defined by the processing time within the repeater and the travel time between repeater and receiver position. A correct simulation for a multi-antenna receiver therefore has to superpose the code and carrier range as observed at the repeater location (considering geometric range between the transmit antenna of the repeater and the individual antenna elements) with the code and carrier ranges at the receiver location.
Instead of the location of the repeater P2, however, any intended location Px could be used to simulate an intelligent spoofer attack (Figure 11).
The simulator can generate such scenarios by configuring the position of the (re-)transmitting antenna and the intended position (for example, the position of the repeater). By calculating the difference between the real receiver position and the position of the transmitting antenna, the additional delay and free-space loss can be taken into account. The user may also configure the gain of the transmit antenna and the processing time within the repeater. Currently, this setup does only support one “user” antenna to be simulated. However, this feature combined with multi-antenna support will enable the simulator to simulate repeater or intelligent spoofer attacks in the future (Figure 12). To distinguish the “real” signal from the “repeated” signal, the “repeated” signal could be tagged as a multipath signal. This approach would allow simulation of the complete environment of “real” and “repeated” GNSS signals in one single simulator.
Figure 11. Geometry of repeater/spoofer and GNSS receiver.Figure 12. Simulator’s capability to simulate a repeater.
Manufacturers
The simulator producing the results described here is the NavX-NCS from IFEN GmbH. The simulator is valuable laboratory equipment for testing not only standard or high-end single-antenna GNSS receivers, but also offers additional benefit for multi-antenna GNSS receivers like the DLR GALANT controlled reception pattern antenna system.
The GNSS constellation simulator offers up to four phase-coherent RF outputs, allowing the simulation of four antenna elements with two carrier frequencies, each utilizing one single chassis being 19 inch wide and 2 HU high.
Simulation of intentional and unintentional interference is a possible feature of the simulator and allows receiver designers and algorithm developers to test and enhance their applications in the presence of interference to identify, locate and mitigate for interference sources.
Thorsten Lück studied electrical engineering at the universities in Stuttgart and Bochum. He received a Ph.D. (Dr.- Ing.) from the University of the Federal Armed Forces in Munich in 2007 on INS/GNSS integration for rail applications. Since 2003, he has worked for IFEN GmbH, where he started as head of R&D embedded systems in the receiver technology division. In 2012 he changed from receiver development to simulator technologies as product manager of IFEN’s professional GNSS simulator series NavX-NCS and head of the navigation products department.
Günter Heinrichs is the head of the Customer Applications Department and business development at IFEN GmbH, Poing, Germany.He received a Dipl.-Ing. degree in communications engineering in 1988, a Dipl.- Ing. degree in data processing engineering and a Dr.-Ing. degree in electrical engineering in 1991 and 1995, respectively. In 1996 he joined the satellite navigation department of MAN Technologie AG in Augsburg, Germany, where he was responsible for system architectures and design, digital signals, and data processing of satellite navigation receiver systems. From 1999 to April 2002 he served as head and R&D manager of MAN Technologie’s satellite navigation department.
Achim Hornbostel joined the German Aerospace Center (DLR) in 1989 after he received his engineer diploma in electrical engineering from the University of Hannover in the same year. Since 2000, he has been a staff member of the Institute of Communications and Navigation at DLR. He was involved in several projects for remote sensing, satellite communications and satellite navigation.In 1995 he received his Ph.D. in electrical engineering from the University of Hannover.His main activities are in receiver development, interference mitigation and signal propagation.
The German Galileo test and development infrastructure GATE has been recertified to serve as a Galileo open‐air test laboratory, for receiver integrity testing (RAIM) for safety‐of‐life (SoL) applications, and for Galileo SIS ICD conformance of signal characteristics and signal quality.
The GATE facility, in Berchtesgaden, is operated by IFEN GmbH. Certification was conducted by TÜV SÜD, an international service corporation focusing on consulting, testing, certification and training.
GATE consists of eight transmitting stations that emit Galileo signals in the GATE test area in Berchtesgaden, as well as two monitoring stations that receive and process these signals.
For application tests, it is essential for GATE to provide constant Galileo specifications for tests, including position accuracy, signal spectrum and navigation data. This is necessary for both test types: tests with the eight “GATE satellites” only and tests with simultaneously usage of the already-existing Galileo satellites in orbit.
The compliance to the specification was verified by the company NavCert GmbH from Braunschweig, Germany, in a recertification of the GATE test bed. Compared to a full certification, taking place every three years, a recertification only verifies the compliance to the specification by the use of random inspections though tests in GATE.
The recertification also includes an audit of the operation processes of the operating company IFEN GmbH. Here, the implementation and adherence to process procedures for GATE operation were verified. This includes questions such as whether a sufficiently technical skilled team is available for operating GATE, if the performed application tests are documented in a reproducible way, and how the GATE team handles non‐conformances to the specification and improvements to the system.
With finalization of the recertification work, the GATE certificate was extended by TÜV SÜD to January 2016. Because of this, GATE customers can rely on the independent verification of the GATE test and development environment for upcoming testing activities, IFEN said.
As an add‐on, customers of IFEN’s NavX‐NCS GNSS simulator benefit from the recertification by obtaining a confirmation from an independent organization (TÜV Süd), reassuring the functionality of GPS and Galileo signal characteristics and signal quality as per SIS ICD, IFEN said.
DigPilot, a Norwegian supplier of surveying equipment and instruments for building and construction, has developed a flexible 3D machine guidance system based on Septentrio’sAsteRx2eH OEM GNSS receivers.
AsteRx2eH is a single-board dual-frequency dual-antenna 272-channel GPS/GLONASS OEM heading receiver, which provides 20-Hz data output of position, heading and pitch/roll data to the machine guidance system. As a member of Septentrio’s AsteRx family of compact OEM boards, the AsteRx2eH receiver is built around the same advanced GNSS chipset and shares the family’s all-in-view GPS and GLONASS tracking and advanced signal processing algorithms for robust tracking and high-precision positioning, even in challenging environments.
The DigPilot machine guidance system uses wireless technology for all of the installed sensors, instead of being hard-wired into the machine. All the components come packed in a hardened plastic case for transportation from one machine to another. The sensors can be clipped into brackets on the excavator arm and cab and calibrated to the machine and bucket in a matter of minutes, Septentrio said. The operator uses an intuitive graphics display on a rugged touchscreen console to control the arm and shovel following a preloaded grade plan.
The DigPilot machine guidance systems have been documented to improve on-the-job safety, productivity and quality of work while reducing costs dramatically. With the DigPilot system, companies can move the 3D guidance system around the fleet of construction equipment as needed, at a fraction of the cost of installing hard-wired systems on multiple machines, Septentrio said.
DigPilot customers are also using APS-3 GNSS RTK receivers from Altus Positioning Systems, a Septentrio company, in conjunction with the on-board machine guidance system for high-precision site surveys and as-builts.
“With the Septentrio OEM receivers we know we can count on the highest levels of accuracy, reliability, ruggedness and performance,” said Jan Floberg, CEO and founder of DigPilot. “We tested all other available GNSS products on the market before deciding on Septentrio. The AsteRx2eH outperforms the other brands in its ability to obtain and hold fix and heading in the rugged terrain of western Norway. We have deployed over 1,000 systems to date.”
Altus and Septentrio products will be on display at World of Concrete in Outdoor Booth 032025 at the Las Vegas Convention Center, Feb. 3-6.
NovAtel Inc. has announced the FlexPak6D enclosed GNSS receiver, a flexible dual-antenna solution for application developers seeking a high-precision heading-capable positioning engine for space-constrained applications.
Designed for efficient and rapid integration, the compact, lightweight receiver tracks GPS, GLONASS, Galileo and BeiDou. Antenna placement is flexible, which means the antenna baseline can be set according to space available on the vehicle and the heading accuracy required. In addition, the modular nature of the FlexPak6D’s OEM6 firmware provides users with the ability to configure the receiver for their unique application needs.
Scalable for sub-meter to centimeter-level positioning, the FlexPak6D delivers NovAtel’s ALIGN precision heading and relative heading firmware, as well as its GLIDE firmware for smooth decimeter-level pass-to-pass accuracy, and RAIM for increased GNSS pseudorange integrity.
“Our FlexPak6D builds on our popular lightweight FlexPak form factor,” said Jason Hamilton, vice president of marketing for NovAtel. “The modular, flexible design makes it easy to integrate into land, air and marine-based industries, particularly for low payload UAV and robotic applications.”
The FlexPak6D will be available for shipping February 2, 2015.
An Object-Oriented Software Platform Suitable for Multiple Receivers
By Eliot Wycoff, Yuting Ng, and Grace Xingxin Gao
INNOVATION INSIGHTS by Richard Langley
AND NOW FOR SOMETHING COMPLETELY DIFFERENT. My first introduction to computer programming was during a visit to the Faculty of Mathematics at the University of Waterloo when I was still a high school student. We got to keypunch a simple program onto cards using the FORTRAN programming language and submit the “job” to the university’s IBM 7040 mainframe computer. That visit helped seal the choice of Waterloo for my undergraduate education — but in applied physics, not math.
Once I became an undergraduate, I learned how to properly program in FORTRAN (actually FORTRAN IV with the WATFOR compiler developed at Waterloo) and in assembly language on the SPECTRE virtual computer (written in FORTRAN), both on Waterloo’s new IBM 360 mainframe. Knowing how to program was instrumental in my graduate work on the geodetic application of very long baseline interferometry (VLBI) at York University. Being humble Canadians (and despite the fact that VLBI was invented in Canada), we called it just LBI. My LBI data analysis FORTRAN program was initially on a box full of punched cards that I would have to carry back and forth to the computer center being careful not to drop the box and get the cards out of order.
While I was a graduate student, I also got to use the Spiras-65 minicomputer that controlled the playback of the LBI recorded tapes at the National Research Council in Ottawa.It was programmed using punched paper tape.
I saw the progression from punched tape and cards to the use of terminals to enter programs and magnetic tapes for storing them and the data to be analyzed. The University of New Brunswick, where I came to work in 1981, was one of the first universities in Canada to introduce an interactive terminal- (or work-station-) based time-sharing system for programmers to develop and run their jobs on the central computer. The last card reader at UNB was retired in 1987.
By the time I came to work at UNB, the era of the personal computer had already dawned. Although the Department of Surveying Engineering (as it was then called) acquired an HP 1000 minicomputer for various research tasks, personal computers began to show up on faculty members’ desks and in their labs. Some of us started out with Apple II computers (we used them, for example, for recording data from Transit–U.S. Navy Navigation Satellite System–receivers) and progressed through various Macintosh models.
Once I became a professor, I did less and less programming myself–leaving it up to my graduate students to do the heavy lifting in that area. These days, my personal programming efforts are limited to short scripts mostly using the Python language. Python, which gets its name from the Monty Python’s Flying Circus television series, was first introduced back in 1991 but it is only relatively recently that its popularity has taken off. Python can be run on a wide variety of platforms under many operating systems.
One of the key features of Python is that it supports multiple programming paradigms, including object-oriented programming (OOP).OOP is a programming methodology based on the use of data structures, known as objects, rather than just functions and procedures. The objects, organized into classes, exchange information in a standardized way and their use helps ensures good code modularity.
In this month’s column, we take a look at how Python has been used to develop a software-defined GNSS receiver — one well-suited to processing data from a network of receiver front ends.
“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.
With billions of GNSS-enabled devices in use today, the potential gains from harnessing data collected over a network of GNSS receivers has never been greater, yet the necessary architectures to handle and extract useful data collected over such networks are not well explored. Traditional uses of GNSS in cooperative positioning treat individual GNSS receivers as “black boxes” that merely output navigation solutions. As such, the wealth of information contained in each receiver’s raw signals is largely discarded.
Of particular interest are ideas such as inter-receiver aiding, in which networked receivers might share acquisition, tracking, and navigation information (possibly in real time) to improve receiver performance. In addition, a network of receivers might also be used as a sensing tool: it is expected that atmospheric parameters, for instance, could be recovered by analyzing the raw signal data arriving at an appropriately sized network.
In light of these interesting research areas, it would be expedient to develop a set of tools that can process and handle the raw data being produced at every receiver in a GNSS receiver network. Existing software-defined receivers (SDRs) have gone a long way towards making the fast prototyping of new receiver architectures possible. An SDR attempts to shift as many receiver functions, such as mixing and tracking, from being implemented in hardware to being implemented in software. This allows for fast prototyping as receiver components can be more quickly modified in software than in hardware. The hardware components that a GNSS SDR still requires are an antenna and a front end including an analog-to-digital converter (ADC). An analog GNSS signal is received at the antenna. It is then mixed to an intermediate frequency and digitized by the ADC. The digital stream is then processed by the SDR’s software component.
But with regard to processing data from a receiver network, existing SDRs have a number of notable flaws. In brief, existing software receivers are designed to process the data arriving at one real-world receiver. Thus a procedural coding design is typically used. While procedural code is a good solution for the linear processes that occur in a single receiver (acquisition, tracking, demodulation of the navigation data, position calculations, and so on), this software design style does not adapt well to the task of performing all of these actions on multiple receivers with the additional goal that each receiver shares tracking data with every other one. In such scenarios, not only is there data being produced for every receiver in the network, but there is also data being produced about the relationships between the receivers in the network. Thus, an SDR that was originally designed to process data from only one receiver will prove difficult to adapt to the task of processing many.
Luckily, object-oriented programming, a well-known and widely used software design philosophy, is well suited to the receiver network problem. Therefore, for this work, we designed and implemented an object-oriented software platform for many receivers. Python was chosen as the programming language because of its support for object-oriented programming, its portability, its free cost, its numerical abilities (using open-source libraries such as NumPy and SciPy), and its ease of use. And as a reference, an existing Matlab software receiver was used as a basis for developing many of the core algorithms in this work. We call our development simply the Python Receiver.
Design
Many of the core functions in the Python Receiver are modeled after those found in the Matlab development. Thus, this particular implementation is suited for the raw GPS L1 signal data mixed to an intermediate frequency by the SDR front end. In addition, the basic algorithms for acquisition, scalar tracking, and navigation are similar to the Matlab ones, with the exception that acquisition is made more robust by using multiple noncoherent integrations. The primary innovation of this software, however, is in the way in which the code is organized. For tracking multiple receivers, the Python Receiver was designed under an object-oriented approach.
FIGURE 1 illustrates the main objects that a user would be expected to use in the Python Receiver. Each object is defined as a class, and as such each object is capable of storing object-specific data as well as performing certain object-specific functions. The hierarchy of Figure 1 roughly illustrates which objects are defined as members of other classes for typical usage. Thus, inside any instance of the network class may exist any number of receiver objects. Likewise, an instance of the constellation class may be home to any number of satellite objects.
FIGURE 1. Typical object (class) hierarchy.
For data coming from a single real-world receiver, use of the Python Receiver would typically be as follows. First, a user would initialize an instance of the receiver class using a dictionary of predefined settings, such as the file location of the data source. Second, the user would initialize a constellation object of satellites by passing the pseudorandom noise (PRN) code values of each satellite to be included in the constellation. At this point, the user could then use built-in functionality in the receiver object to perform acquisition of all of the satellites in the constellation. Results of this acquisition attempt would be stored in the receiver object, where they could then be used to run the receiver’s built-in scalar tracking functionality. Likewise, scalar tracking data would be stored in the receiver object, and again the user could use the receiver’s built-in navigation functionality to decode the navigation bits produced during scalar tracking and perform navigation computations. Satellite-specific ephemerides would be stored in the relevant satellite objects.
Navigation solutions are stored as a part of the receiver’s state object. The state object, which is also used in the satellite class, is a container for holding state information in the Earth-centered Earth-fixed (ECEF) coordinate system (such as position and velocity) and clock terms, and it also provides the ability to return position coordinates in other systems, such as the GPS geodetic system (frame) of WGS 84. While it is not a key feature of the Python Receiver, the state object is designed as an object so that it can be readily used elsewhere should an algorithm need to store state information and have coordinate transformations readily available.
Tracking channels need not be restricted to the hierarchy shown in Figure 1. During operation for just one data source, the scalar tracking function defined at the receiver level will initialize a sufficient number of tracking channels to track all of its observed satellites. However, when operating on multiple sources of data and with the intent to share tracking outputs between channels, it is helpful to place tracking channels into groups, as shown in FIGURE 2. In the example that will be discussed in following sections, two real-world receivers observed a similar set of satellites. It was therefore helpful to define channel groups for each commonly observed satellite, with one channel in the group corresponding to the satellite as tracked by the first receiver, and the other channel corresponding to the satellite as tracked by the second. Tracking groups as a class, however, may be easily modified for other experimental purposes.
FIGURE 2. Left: an independent tracking channel (corresponding to one tracking channel object). Right: a channel group. Note that in the channel group, updates to the code and carrier phase of each channel may be performed cooperatively.
Independent tracking channels have an update function that processes the next segment of raw data in three main steps: computing correlations (early, late, and prompt), producing discriminator outputs, and generating code and carrier-frequency updates. For a group of channels, this sequence of steps is interrupted after discriminator outputs have been computed. At this point, the channel group may instruct the tracking channels to update their code and carrier frequencies independently or through some other cooperative means that considers data across all of the channels.
As for the last few classes: correlators and filters are defined as objects so that they can be easily changed depending on the experimental circumstances. And satellites, in addition to holding satellite-specific ephemerides, have built-in functionality to return their locations given a particular epoch of GPS Time.
Naturally, core functions such as these would be found in traditional software receivers, but by repackaging them into the object-oriented framework, both code reusability and modifiability increase. And in addition, by defining classes for networks of receivers and groups of tracking channels, simulations and experiments involving cooperative positioning of receivers become easier to conduct.
Experiment
To help illustrate how the Python Receiver lends itself to the task of cooperatively tracking multiple receivers, concurrent data from two SDR front ends was collected on a boat in Lake Titicaca just offshore from Puno, Peru. The boat was a small motorized ferry capable of transporting approximately twenty passengers. One antenna and front end, hereafter referred to as “Receiver X” was placed on the port side of the boat, while the other, “Receiver Y” was placed on the starboard side. Maintaining a fixed baseline, both receivers captured raw GPS L1 signals from separate portions of the sky and mixed them to an intermediate frequency of 5.456 MHz. Raw data collection was performed concurrently at both receivers for 15 minutes as the boat returned from the floating islands of the Uros people to the dock at Puno. Finally, while Lake Titicaca is at a high elevation in the Altiplano (the Andean Plateau), the surrounding mountains do not rise far above the horizon, and thus visibility was quite good in most directions.
Some challenges, however, present themselves in this data set. While Receiver X was able to acquire eight satellites, and Receiver Y was able to acquire 10, the signal quality at Receiver Y was generally poor. In Figure 3, in-phase prompt correlator outputs from traditional scalar tracking are shown for both Receivers X and Y and satellites with PRN codes 27 and 29. For satellite 27, Receiver Y loses lock of the signal between code periods 100,000 and 200,000, and for satellite 29, it completely loses track of the signal after only a few thousand code periods. (Recall that the C/A-code period is one millisecond.)
FIGURE 3. The in-phase prompt correlator outputs for both receivers and satellites PRN 27 and 29. The cyan dots are correlator outputs, the red line is the locking metric, and the dashed green and blue lines are the thresholds set for determining good and poor lock, respectively. Locking metric values above the dashed green line represent a good lock, and values below the dashed blue line represent loss-of-lock. Note that y-axis values differ from graph to graph.
To better characterize the tracking performance of each receiver-satellite pair, a locking metric was designed and implemented, the values of which are shown as the red lines in the graphs of Figure 3. Inspired by the earlier use of the square-law detector, we have expressed the metric as:
(1)
where N is the number of most recent correlator samples, Ii and Qi are the ith in-phase and quadrature-phase prompt correlator outputs, and the square-root operator returns the negative square root of the absolute value of the expression under the radical if that expression is negative.
After visually examining the relationship of this locking metric with the quality of the in-phase prompt correlator outputs, two thresholds were determined in order to better characterize the quality of the tracking loop lock. The first threshold, represented as the dashed green lines in the graphs of Figure 3, is the threshold above which the tracking loops were considered locked well. Its value was set to 250. The second threshold, whose value was set to 150 and is represented by the dashed blue lines, is the threshold below which the tracking loops were considered to be in a complete loss-of-lock situation. Locking metric values between 150 and 250 were considered as representing a situation in which the tracking loops were weakly locked to the incoming signals.
Despite the poor performance of Receiver Y in tracking many of its signals, navigation functionality in the Python Receiver was still able to recover sufficient ephemerides from the tracking data to perform position calculations. FIGURE 4 shows the navigation solutions for Receiver Y over a 13-minute interval, roughly capturing the route that the ferry took westward back to Puno. Note that the moustache-shaped region in the right-hand side of the map is the collection of floating islands of the Uros. Just as the ferry left these islands, the navigation solutions for Receiver Y become much nosier. Possible reasons for this are the slight change in heading that the ferry made, or the thicket of reeds that surrounded the boat during this portion of the journey. Navigation results for Receiver X were much less noisy.
FIGURE 4. The trip back to Puno on the left (west) from the floating islands of the Uros on the right (east) as determined by traditional scalar tracking and navigation at Receiver Y. Image courtesy of Google Earth and the GPS Visualizer.
Cooperative Scalar Tracking
While all of these traditional results were obtained using the Python Receiver, they could have just as easily been obtained using procedurally coded receivers. Assuming, however, that one is interested in performing experiments that involve data sharing between multiple receivers, the Python Receiver lends itself handily to the task.
An experiment was devised in which scalar tracking performed at both Receivers X and Y would be done cooperatively. In particular, it was observed that often when one of the two receivers momentarily lost track of its signal for a particular satellite, the other receiver would be tracking well. In addition, it was noted that because the two receivers maintained a fixed baseline during tracking, their tracking channels should have maintained a steady difference in code phases that changed slowly provided that the receiver-satellite geometry did not change quickly. As shown in FIGURE 5, the only violation of this scenario would occur when one of the two receivers lost lock and thus allowed for drift in its code-tracking loop. It should be noted that unlike the situation in Figure 5, the reported code difference between the two receivers suffered from a bias that grew linearly in time. This bias, which was likely due to clock errors in one or both of the receiver front ends, was eliminated through a linear regression before the plotting of the figure.
FIGURE 5. The code-phase difference between Receivers X and Y for PRN 27 from 300,000 to 500,000 milliseconds. Note the large variance around 400,000 milliseconds corresponding to a loss-of-lock for Receiver Y.
All of these observations motivated the following cooperative scalar tracking design. First, any satellite that was observed by only one receiver would be independently tracked by that receiver in the traditional manner. A single tracking loop object would be allocated in Python for this particular receiver-satellite pair. Second, any satellite that was observed by both receivers would have a channel group object allocated in Python. This channel group would contain two tracking channel objects, one for each receiver.
As shown in Figure 2, this channel group required specific code to be written to handle the cooperative updates of both receivers’ code and carrier frequencies. The algorithm was designed as follows. For each update epoch (generated by a call of the channel group’s update function), if both of the tracking channels were locked to their incoming signals, the channel group would save their code-phase difference for that code period. And since both channels were locked, both would update their code and carrier frequencies in the traditional manner, relying on discriminator outputs only.
If, on the other hand, one of the tracking channels was in a loss-of-lock situation, the channel group would search the previous 5,000 milliseconds of data for code periods during which, presumably, both tracking channels were mutually locked. This data would contain information about the expected code-phase difference between the two tracking channels at the current code period. At this point, a linear regression on the data from the mutually locked code periods was used to determine this expected code-phase difference. Finally, we note again that this expected code-phase difference would only remain valid under the assumption that the receiver-satellite geometry was not changing rapidly, as was the case for this data. But acknowledging that some changes in the geometry might occur (such as a change in heading of the boat) is the reason why the search interval for mutually locked data was limited to five seconds.
Assuming that one of the receivers was in a loss-of-lock situation and that sufficient data from the past five seconds existed to generate an estimate of the current expected code-phase difference, the channel group could then make a cooperative update of the lockless tracking channel. For this channel, the channel group would replace the traditional code-tracking discriminator outputs with the offset of the expected code-phase difference dexp from the currently observed code-phase difference dcur. In the following equation, the new discriminator output is denoted as c:
. (2)
Expressing dcur=ycur−xcur and dexp=yexp−xexp, where xcur/exp and ycur/exp represent current and expected code phases at two receivers, we can rewrite Equation 2 as
(3)
or
(4)
since we expect the x receiver to be locked, and therefore .
Some finer points to mention include that the “loss-of-lock” and “tracking well” designations were determined by way of the locking metric defined in the previous section. In addition, if a receiver was “tracking weakly,” it would update its code and carrier frequencies by relying solely on its own discriminator outputs. Also, because in traditional scalar tracking loss-of-lock might occur for an extended interval greater than five seconds at one receiver (such as Receiver Y’s tracking of satellite 27 seen in Figure 3 between 300,000 and 400,000 milliseconds), whenever the channel group was called to cooperatively update a lockless tracking channel’s code frequency, it would record the current code-phase difference between both receivers. Under all scenarios, the carrier-frequency update would be done independently at each channel using discriminator outputs alone. And finally, in order for both receivers to share relevant data with each other during tracking, clock bias terms found after traditional scalar tracking were used to align in time the raw data files for each receiver appropriately.
Results and Discussion
Using cooperative scalar tracking, drifting of the code-phase difference during code periods when one of the receivers is experiencing loss-of-lock is expected to be suppressed. And indeed, results such as those shown in FIGURE 6 verify this expectation. Since cooperative scalar tracking does not attempt to modify the way either receiver tracks during periods of good lock, this type of modified scalar tracking is not expected to produce less noisy tracking results. It is expected, however, to help lockless tracking channels to regain track after short signal outages, similar to the benefits of vector tracking.
FIGURE 6. The code-phase difference between Receivers X and Y for PRN 27 from 300,000 to 500,000 milliseconds, this time using cooperative scalar tracking. Presence of the red line indicates code periods during which cooperative code-phase updates were made for Receiver Y. Note that noisy drifting of the code-phase difference is suppressed.
Strikingly, this form of cooperative tracking allowed for Receiver Y to continually track the signal from satellite 29 (albeit with occasional outages) for the full thirteen minutes of data shown in FIGURE 7. Whereas in Figure 3, Receiver Y very quickly loses track of satellite 29, Figure 7 shows that Receiver Y, under cooperative scalar tracking, can maintain a good enough lock on the signal that by roughly 750,000 code periods, it is able to pick up the signal again quite strongly. This change in signal strength may have been due to a slight change in heading that the ferry made near Isla Taquile towards the end of this data set (see Figure 4 and FIGURE 8).
FIGURE 7. The in-phase prompt outputs for Receiver Y and PRN 29 using cooperative scalar tracking. Compare this to the bottom-right graph in Figure 3. Inter-receiver aiding allowed Receiver Y to track this signal for a majority of the code periods.FIGURE 8. The trip back to Puno as determined by Receiver Y after cooperative scalar tracking and navigation computations. Compared to Figure 4, the navigation solutions are less noisy. Image courtesy of Google Earth and the GPS Visualizer.
Given the locking metric defined in the section “Experiment,” quantitative measures of how often each channel spent locked or in loss-of-lock can be made. In total, both receivers tracked six common satellites (with each receiver also tracking other satellites independently). TABLE 1 shows the locking frequencies for each commonly tracked satellite.
TABLE 1. Percent of time each tracking channel spent locked. Lock was designated if the locking metric was above 150. The best values for Receiver Y are highlighted in green, with the most notable improvement occurring for satellite 29.
Granted that the drift in the code phase for lockless tracking channels is curtailed in cooperative scalar tracking, an improvement in navigation solutions is also expected. This expectation is verified by comparing the qualitative level of noise in the solutions of Figure 8 to the solutions in Figure 4. Notably, the noise in the reed thicket (the section of the route immediately after leaving the moustache-shaped floating islands region) is suppressed. Not shown are the navigation solutions for the port side receiver, Receiver X, which by comparison to Receiver Y were relatively good in both forms of scalar tracking.
Conclusion
The experiment we carried out highlighted the abilities of the Python Receiver. Data from two SDR front ends and associated antennas placed on either side of a small transport ferry was used to track both receivers by using groups of tracking channels that could cooperatively modify their individual channels’ code and carrier frequencies. In this way, loss-of-lock in many of the tracking channels was avoided leading to improved navigation precision. More importantly, it is expected that future experiments like these can be easily implemented within the framework of the Python Receiver, and thus topics like cooperative vector tracking might be more easily investigated.
Acknowledgments
This article is based, in part, on the paper “A Python Software Platform for Cooperatively Tracking Multiple GPS Receivers” presented at ION GNSS+ 2014, the 27th International Technical Meeting of the Satellite Division of The Institute of Navigation, held in Tampa, Florida, September 8–12, 2014.
Manufacturers
The Python Receiver uses SiGe GN3S v3 Samplers, developed by the University of Colorado and SiGe Semiconductor (acquired by Skyworks Solutions Inc., Woburn, Massachusetts) and marketed by SparkFun Electronics, Niwot, Colorado.
ELIOT WYCOFF received his B.S. in applied mathematics from Columbia University, New York, in 2011. While working on the Python Receiver, he was a graduate student in the Department of Aerospace Engineering at the University of Illinois at Urbana-Champaign (UIUC).
YUTING NG obtained a B.S. in electrical and computer engineering from UIUC in 2014. She is currently a graduate student in the Department of Aerospace Engineering, UIUC.
GRACE XINGXIN GAO is an assistant professor in the Department of Aerospace Engineering, UIUC. She received her B.S. in mechanical engineering in 2001 and her M.S. in electrical engineering in 2003, both from Tsinghua University, China. She obtained her Ph.D. in electrical engineering at Stanford University in 2008. Before joining UIUC in 2012, Gao was a research associate at Stanford University.
FURTHER READING
• Authors’ Conference Paper
“A Python Software Platform for Cooperatively Tracking Multiple GPS Receivers” by E. Wycoff and G.X. Gao in Proceedings of ION GNSS+ 2014, the 27th International Technical Meeting of the Satellite Division of The Institute of Navigation, Tampa, Florida, September 8–12, 2014, pp. 1417–1425.
• Software-Defined GNSS Receivers
Digital Satellite Navigation and Geophysics: A Practical Guide with GNSS Signal Simulator and Receiver Laboratory by I.G. Petrovski and T. Tsujii with foreword by R.B. Langley, published by Cambridge University Press, Cambridge, U.K., 2012.
A Software-Defined GPS and Galileo Receiver: A Single-Frequency Approach by K. Borre, D.M. Akos, N. Bertelsen, P. Rinder, and S.H. Jensen, published by Birkhäuser Engineering, Springer-Verlag GmbH, Heidelberg, 2007.
Learn Python in One Hour by V.R. Volkman, published by Modern Software Press, L.H. Press Inc., Ann Arbor, Michigan, 2014.
A Primer on Scientific Programming with Python by H.P. Langtangen, published by Springer-Verlag GmbH, Heidelberg, 2009.
“Python for Scientific Computing” by T.E. Oliphant in Computing in Science & Engineering, Vol. 9, No. 3, May–June 2007, pp. 10–20, doi: 10.1109/MCSE.2007.58.
Fundamentals of Global Positioning System Receivers: A Software Approach, 2nd edition, by J. B.-Y. Tsui, published by Wiley-Interscience, John Wiley & Sons, Inc., Hoboken, New Jersey, 2005.
“An Assisted GPS Acquisition Method Using L2 Civil Signal in Weak Signal Environment” by D.J. Cho, C. Park, and S.J. Lee in Journal of Global Positioning Systems, Vol. 3 No. 1-2, December 2004, pp. 25–31.
“Lock Detection in Costas Loops” by A. Mileant and S. Hinedi in IEEE Transactions on Communications, Vol. 40, No. 3, March 1992, pp. 480–483, doi: 10.1109/26.135716.
The xOEMcore, now being offered by Oxford Technical Solutions (OxTS), is an inertial navigation system that can also serve as a framework for other positioning systems.
The xOEMcore is a combined six-axis inertial measurement unit and navigation system with sensor fusion in one compact OEM module. In its base form, the xOEMcore measures and outputs raw accelerations and angular rates with small, high-grade MEMS gyros and accelerometers. With a simple upgrade, the xOEMcore is turned into a full inertial navigation system, able to take aiding data from external sources such as GNSS and blend it in the on-board Kalman filter. It is desgined for integration inside any solution that requires robust, high-performance position and orientation.
xOEMcore provides continuity from one point to the next, so detecting unexpected measurements from other devices is easy, the company said. It has deterministic error growth for accuracy, a high update rate and lowdelay, enabling easier control of vehicles and robots.
As a framework, the xOEMcore can be merged other technologies, such as GNSS and vision positioning. The xOEMcore solves conflicts between the two systems, removing timing mismatches, delays, jumps and inconsistencies.
The xOEMcore is small, light and low power. The inertial sensors have low drift rates — less than 5-meters drift after 60 seconds can be achieved in real-time with only odometer aiding. Heading, roll and pitch can be accurate to 0.05 degrees, exceeding magnetic heading and vertical reference system performance.
We appear incompletely before you this month. A funny thing happened on the way to the presses: we discovered that we had more content than pages in which to squeeze it. “All the news that fits to print,” the motto of the New York Times, can in this instance not be ours. All the news just won’t fit!
First to feel the axe, lamentably, was Innovation, an article on the Python receiver; you will see it in February. Also pushed to the near future is reporting on the recent Stanford PNT Symposium; it appears in the December GNSS Design & Test e-newsletter, see the website if you don’t yet subscribe. Herewith, an ultra-brief account of a presentation by Greg Turetzky, Intel. The reporters identified this paper and one on BeiDou as “harbingers of change in the industry.”
The Turetzky paper, “Ubiquitous Location: Challenges and Opportunities ofEnabling All-day, Everywhere Location for All Mobile Platforms,” laid out the phenomenal growth of location-based services and the implications for design requirements in GNSS-wireless at the user device and silicon levels. The compound annual growth rate of GNSS devices will continue, from its current 22 percent level to a robust 9 percent for the years 2016–2022, and heading for seven billion installed units by 2022.
From Greg Turetzky’s Ubiquitous Location paper, presented at Stanford PNT Symposium.
Cutting to the chase, the design challenges for GNSS are to:
Take advantage of smaller geometries to achieve higher clock speeds, more memory, lower active power and smaller size, while reducing standby power from leakage;
Incorporate new methodologies in chip and system design; integrate multiple radios on a single die to reduce cost and size;
Integrate multiple radio sources into a single location solution;
Bring together a disparate value chain.
The technology roadmaps embrace most modalities of positioning: GNSS, Bluetooth, Wi-Fi, cellular, and SBAS, and cross most platforms, including wearables. “We think that another, unemphasized challenge,” reporters Litton and Langenstein note, “is in the increasing density of these units with the current specifications on out-of-band emissions and the spectrum sharing and spectrum management factors in the ubiquity of the devices.”
Tune in to our free webinar Receiver Design for the Future,with Greg Turetzky of Stanford speaking on Ubiquitous Location, scheduled for Jan. 15 (1 p.m. EST/ 10 a.m. PST/ 6 p.m. GMT). Register today!
Ultra-Low-Power, High-Accuracy Location for Wearable GNSS Devices: From Host-Based to On-Chip
Photo: Steve Malkos, Manuel del Castillo, and Steve Mole, Broadcom Inc., GNSS Business Unit
As location penetrates smaller and smaller devices that lack memory and computation power, GNSS chips must reacquire the standalone capability that they shed when first going to small form factors such as phones. A new chip with a new architecture demonstrates navigation and tracking and avoids burdening its main processor with heavy software.
By Steve Malkos, Manuel del Castillo, and Steve Mole, Broadcom Inc., GNSS Business Unit
End users first experienced the amazing capabilities of GPS 12 years ago with early mass-market GPS devices. The focus was on navigation applications with specific tracking devices like personal navigation devices and personal digital assistants (PNDs, PDAs). With the advent of smartphones, GPS became a must-have feature. Other constellations were added to improve performance: GLONASS, QZSS, SBAS, and very recently, BeiDou. In the current phase, the focus is shifting to fitness applications and background location. This is not an insignificant change.
Always-on connected applications, high-resolution displays, and other such features do not improve battery life. This article describes new ultra-low-power, high-accuracy location solutions for wearables’ power consumption.
Impact of Always-On Connected Applications
New applications require frequent GNSS updates with regard to user position. Sometimes the application will be open and other times it will not. The chips need to keep working in the background, buffering information and taking predefined actions. The GNSS chips need to be able to cope with these new requirements in a smart way, so that battery life is not impacted. Saving power is now the name of the game.
Furthermore, GNSS is penetrating small devices: the Internet of Things (IoT) and wearables. They do not have the luxury of large resources (memory, computation power) as smartphones do. GNSS chips cannot leverage the resources in those devices; they need to be as standalone as possible. In summary, the new scenario demands chips that:
do not load device’s main processor with heavy software;
use less power while maintaining accuracy;
can be flexibly configured for non-navigation applications.
New GNSS Chip Architectures
The industry is designing chips to meet these requirements by including the following features:
measurement engine (ME) and positioning engine (PE) hosted on the chip;
accelerometer and other sensors directly managed by the chip;
new flexible configurations, duty cycling intervals, GNSS measurement intervals, batching, and so on.
These features require hardware and software architectural changes. The new chips need more RAM than that required for smartphones, as they must now host the ME and PE. Wearables and IoT devices are small, cheap, and power-efficient. They do not have large processors and spare memory to run large software drivers for the GNSS chip. In many cases, the device’s microcontroller unit (MCU) is designed to go into sleep mode if not required, that is, during background applications. Therefore, new GNSS chips with more RAM are much better adapted to this new scenario.
New chips must tightly integrate with sensors. The accelerometer provides extremely valuable information for the position update. It can detect motion, steps, motion patterns, gestures, and more. However, as a general rule, the MCU’s involvement in positioning should be minimized to reduce power consumption. For power efficiency, the new GNSS chips must interface directly with the sensors and host the sensor drivers and the sensor software.
Finally, new chips must adapt to different human activities as they are integrated into wearable devices. This is the opposite approach from past developments where GNSS development was focused on one use case: car navigation. Now they must adapt to walking, running, cycling, trekking, swimming, and so on. All these activities have their particularities that can determine different modes in which new GNSS chips can work. Electronics must now conform to humans instead of the other way around. New wearable-chip GNSS tracking strategies include dynamic duty cycling and buffering, which contribute to the goal of reducing power consumption without compromising accuracy.
Satellite positioning embedded in devices over the last few years first saw on-chip positioning before the era of smartphones, where you had dedicated SoCs that supported the silicon used to compute the GNSS fix. These expensive chips had lots of processing power and lots of memory. Once GNSS started to be integrated into cellphones, these expensive chips did not make sense. GNSS processing could be offloaded from the expensive SoCs, and part of the GNSS processing was moved onto the smartphone application processor directly.
Since navigation is a foreground type of application, the host-based model was, and is still, a very good fit. But with advances in wearable devices, on-chip positioning will become the new architecture. This is because the host processor is small with very limited resources on wearables; and because energy must be minimized in wearables, reducing the processor involvement when computing GNSS fixes is critical.
Some vendors are taking old stand-alone chips designed for PNDs and repurposing them for wearable devices. This approach is not efficient, as these chips are large, expensive, and use a lot of power.
GNSS Accuracy
While the new fitness and background applications in wearables have forced changes in GNSS chips’ hardware and software architectures, GNSS accuracy cannot be compromised. Customers are used to the accuracy of GNSS; there’s no going backwards in performance in exchange for lower power consumption.
Figure 1. Software architecture for wearables.
A series of tests shown here demonstrate how a new wearable, ultra-low-power GNSS chip produces a comparable GNSS track to existing devices using repurposed full-power sportwatch chips, while using only a fraction of the power.
Speed Accuracy. Not only does the ultra-low-power solution produce a comparable GNSS track, it actually outperforms existing solutions when it comes to speed and distance, thanks to close integration with sensors and dynamic power saving features (Figures 2 and 3).
Figure 2. Ultra-low-power versus full power.Figure 3. Full-power sportwatch, left, and ultra-low power chip, right, in more accuracy testing.
GNSS Reacquisition. GNSS-only wearable devices face a design challenge: to provide complete coverage and to avoid outliers. This is seen most clearly when the user runs or walks under an overpass (Figure 4). Familiar to urban joggers everywhere, the underpass allows the user to cross a busy road without needing to check for traffic, but requires the GNSS to reacquire the signals on the tunnel exit. See the GNSS track in Figure 5: when the device reacquires the signals, the position and speed accuracy suffers.
Figure 4. Position accuracy on reacquisition, emerging from overpass.Figure 5. GNSS speed accuracy on reacquisition.
Using the filtered GNSS and sensors, however (Figure 6), enables smooth tracking of speed and distance through the disturbance.
Figure 6. Sensors provide smooth speed estimate.
Urban Multipath. The pace analysis in Figure 7 shows a user instructed to run at a constant 8-minute/mile pace, stopping to cross the street where necessary. The red line on each plot shows the true pace profile. The commercial GNSS-only sportwatch on top shows frequent multipath artifacts, missing some of the stops and, worse for a runner, incorrectly showing erroneously high pace. The ultra-low-power chip captures all the stops and shows a constant running pace when not stopped.
Figure 7. Urban multipath tests.
It is well known in the community that regular sportwatches give unreliable speed and distance estimates in urban environments — where most organized running races are held! There’s nothing worse, as a runner, than to hear the distance beep from your watch going off earlier than expected: how demoralizing! The major benefit of this solution is that the speed estimate is much more reliable in the presence of multipath. At the same time, battery life can be extended because the GNSS is configured to use significantly less power.
fSpeed in existing solutions is computed in two different ways: indirectly from two consecutive, time-stamped GNSS position estimates, each derived from range measurements to the satellites, and directly from the Doppler frequency offset measurements to the satellites. Both range and frequency measurements are subject to significant error when the direct path to the satellite is blocked and a reflection is acquired.
The effects of multipath mean that the range error may in typical urban environments be hundreds of meters. The frequency error is also a function of the local geometry and is typically constrained by the magnitude of the user’s horizontal speed.
In either case, the GNSS device alone, in the presence of signal multipath, generates a velocity vector that fluctuates significantly, especially when there is a change in the satellites used or signal propagation path between the two consecutive positions. A variety of real-life cases generate this sudden fluctuation in velocity vector:
Running along a street in an urban canyon and turning a 90-degree corner.
Running along a pedestrian lane and taking a short road underpass.
Running under tree cover and suddenly arriving at an open area.
Running under an elevated highway and turning 90 degrees to a wide-open area.
In each case, the chips are using a certain set of satellites, and suddenly other, higher signal-strength satellites become available. A typical situation is for the position to be lagging the true position (while under tree cover, going through an underpass) and needing to catch up with the true position when arriving to the wide-open area. A jump in position is inevitable in that situation. This is not too bad for the GNSS track, but it will mean a noticeable peak in the speed values that is not accurate. Fitness applications save all of the computed speed values and generate a report for each workout. These reports are not accurate, especially the maximum speed values, for the reasons explained above.
Figure 8 describes a typical situation where the actual speed of the runner is approximately constant. GNSS fixes are computed regularly; however, the speed computed from subsequent GNSS fixes have sudden peaks that spoil the workout speed reports.
Figure 8. Sudden peaks spoil workout speed reports.
The new ultra-low-power solutions for wearables solve this problem by deriving speed and accumulated distance from the sensors running in the device. This avoids incorrect speed peaks, while still being responsive to true pace changes by the runner.
In running biomechanics, runners increase pace by increasing step cadence and/or increasing step length. Both methods depend on the runner’s training condition, technique, biomechanics, and so on. As a general rule, both step cadence and step length increase as the running speed increases from a jogging speed to a 1,500-meter race speed.
A runner may use one mechanism more than the other, depending on the moment or on the slope (uphill or downhill). In the case of male runners, the ratio of step length to height at a jogging speed is ~60 percent.The ratio of step length to height in a 1,500 meter race speed is ~100 percent. For female runners, the respective ratios are ~55 percent and ~90 percent.
The ultra-low-power chips take into account both mechanisms to derive the speed values. The sensor algorithms count the number of steps every time interval and translates the number of steps into distance multiplying by the step length. The reaction time of the GNSS chip to speed changes based on a higher cadence is immediate.
Speed changes due to longer steps are also measured by the ultra-low-power chips. The step length is constantly calibrated by the GNSS fixes when the estimated GNSS position error is low. The reaction time of the GNSS chip to speed changes based on longer steps has some delay, as it depends on the estimated error of the GNSS fixes.
Manufacturer
The ultra-low-power, high-accuracy, 40-nanometer single-die BCM4771 chip was designed by Broadcom Corporation. It is now being manufactured in production volumes and is focused on the wearables and IoT markets.It consumes five times less power than conventional GNSS chips (~10 mW) and needs 30 KBytes of memory in the MCU for the software driver. It features tight integration with the accelerometer and innovative GNSS tracking techniques for extremely accurate speed, accumulated distance, and GNSS tracking data.
Steve Malkos is an associate director of program management in the GPS Business Unit at Broadcom, responsible for defining GPS sensor hub and indoor positioning features. He has a B.S. in computer science from Purdue University, and currently holds eight patents,10 more pending, in location.
Manuel del Castillo is an associate director of marketing for Broadcom in the GNSS group. He has an MS in electronic engineering from the Polytechnic Universityand an MBA from the Instituto de Empresa, both in Madrid, Spain. He holds three patents in location with five more pending.
Steve Mole is a manager of software engineering for Broadcom in the GNSS group. He received his bachelor’s degree in physics and astrophysics from the University of Manchester.
Topcon Positioning Group said that its latest GNSS reference receiver, the NET-G5, is capable of tracking a new signal from the GLONASS constellation.
The GLONASS-M 55 satellite was launched in June 2014 and is equipped with the experimental payload capable of transmitting signals in the L3 frequency band. Engineers successfully tracked the signal with the NET-G5 receiver during a series of recent tests at the Topcon Technology Center in Moscow. The use of signals in L3 band alongside L1 and L2 bands is expected to further enhance the competitiveness of the GLONASS system.
“Topcon is committed to continually investing in research and development to offer end-users and the industry the most up-to-date solutions,” said Ivan Di Federico, chief strategy officer for Topcon Positioning Systems. “Our premier engineers, scientists and designers bring world’s first products and technologies to market, and the ability of the NET-G5 to track the latest signal — a first for the industry — is an excellent example of that dedication.”
Using Vanguard and Universal Tracking technologies, the NET-G5 receiver incorporates 452-channels capable of tracking the full GNSS signal spectrum, including modernized GPS, GLONASS, Galileo, BeiDou, QZSS and SBAS signals.
Ambiguity and Environmental Data: Two Further Key Challenges of Multisensor Positioning
By Paul D. Groves, Lei Wang, Debbie Walter, and Ziyi Jiang, University College London
The coming requirements of greater accuracy and reliability in a range of challenging environments for a multitude of mission-critical applications require a multisensor approach and an over-arching methodology that does not yet exist. Part 1 of this article, in the October issue, examined the two key concepts of complexity and context. In this continuation, we complete our overview with exploration of the requirements of ambiguity and environmental data.
Ambiguity occurs when measurements can be interpreted in more than one way, leading to different navigation solutions, only one of which is correct. Any navigation technique can potentially produce ambiguous measurements. The likelihood depends on both the positioning method and the context, both environmental and behavioral. Urban and indoor positioning techniques that do not require dedicated infrastructure are particularly vulnerable to ambiguity. Poor handling of ambiguity results in erroneous navigation solutions and the navigation system can become “lost,” whereby it is unable to recover and may even reject correct measurements.
There are six main causes of ambiguity: feature identification, pattern matching, propagation anomalies, geometry, system reliability, and context ambiguity. Each of these is described in turn below.
Feature Identification Ambiguity. The proximity, ranging, angular positioning, and Doppler positioning methods all use landmarks for positioning. These may be radio, acoustic, or optical signals, or natural or man-made features of the environment. For reliable positioning, these signals or features must be correctly identified.
Digital signals intended for positioning incorporate identification codes. However, where a signal is weak and/or interference is high, it may be possible to use the signal for positioning but not decode the identification information. For signals of opportunity — that is, not designed for positioning — the identification codes may be encrypted, while analog signals do not typically have identifiers. These signals must be identified using their frequencies and an approximate user position, in which case there may be multiple candidates. Even where a signal of opportunity is identifiable, the transmission site may change without warning. For example, Wi-Fi access points are sometimes moved and mobile phone networks are periodically refigured. Thus, there is a risk of false landmark identification.
Environmental features are difficult to identify uniquely. In image-based navigation, man-made features, such as roads, buildings, and signs, are easiest to identify in images due to their line and corner features. However, similar objects are often repeated in relatively close proximity. For example, Figure 18 shows the locations of the five “no entry” signs in a 1,200-meter circuit of Central London streets. Two of the signs are within 20 meters of each other. (Figure numbering continues the sequence beginning in Part 1, October issue.)
Figure 18. “No entry” signs in a 1,200-meter circuit of Central London. (Background image courtesy of Bing maps | Photo: Paul D. Groves, Lei Wang, Debbie Walter and Ziyi Jiang, University College London)
Pattern-Matching Ambiguity. The pattern-matching positioning method maintains a database of measurable parameters that vary with position. Examples include terrain height, magnetic field variations, Wi-Fi signal strengths, and GNSS signal availability information. Values measured at the current unknown user position are compared with predictions from the database over a series of candidate positions. The position solution is then obtained from the highest scoring candidate(s).
An inherent characteristic of pattern matching is that there is sometimes a good match between measurements and predictions at more than one candidate position. Figure 19 and Figure 20 show GNSS shadow-matching scoring maps based on smartphone measurements taken at the same location 40 seconds apart. The scores are obtained by comparing GNSS signal-to-noise measurements with signal availability predictions derived from a 3D city model. In Figure 19, maximum scores (shown in dark red) are only obtained in the correct street, whereas in Figure 20, there is also a high-scoring area in the adjacent street, giving two possible position solutions.
Figure 19. GNSS shadow-matching scoring map – unambiguous case (the cross shows the true position and white areas are indoor locations). (Photo: Paul D. Groves, Lei Wang, Debbie Walter and Ziyi Jiang, University College London)Figure 20. GNSS shadow-matching scoring map – unambiguous case (the cross shows the true position and white areas are indoor locations). (Photo: Paul D. Groves, Lei Wang, Debbie Walter and Ziyi Jiang, University College London)
Figure 21 presents another example, showing the height of a road vehicle derived from a barometric altimeter at three different times. Provided the altimeter is regularly calibrated, it may be used for terrain-referenced navigation (TRN), determining the car’s position along the road by comparing the measured height with a database. However, if only the current height is compared, it will typically match the database at multiple locations within the search area, as the figure shows. The ambiguity can be reduced by comparing a series of measurements from successive epochs, known as a transect, with the database. This approach is applicable to any pattern-matching technique. However, increasing the transect length to reduce the ambiguity also reduces the update rate, and the ambiguity problem can never be eliminated completely.
Figure 21. Height of a car derived from a barometric altimeter at three different times; readings of around 235 m are highlighted. (Photo: Paul D. Groves, Lei Wang, Debbie Walter and Ziyi Jiang, University College London)
Signal Propagation Anomalies. The ranging, angular positioning, and Doppler positioning methods all make the assumption that the signal propagates from the transmitter (or other landmark) to the user in a straight line at constant speed. Significant position errors can therefore arise when these assumptions are not valid due to phenomena such as non-line-of-sight reception, multipath interference, and severe atmospheric refraction. In challenging environments, such as dense urban areas and indoors, multiple signals are typically affected by propagation anomalies, and it is not always easy to determine which signals are contaminated.
Where the position solution is overdetermined (that is, more than the minimum number of signals are received), different combinations of signals will produce different position solutions when there are significant propagation anomalies.
Figures 22 and 23 illustrate this for conventional GNSS positioning using a Leica Viva geodetic receiver, showing the position errors obtained using different combinations of GPS and GLONASS signals. In Figure 22, the receiver is located on a high rooftop and the majority of position solutions are within 15 meters of the mean, with the remainder easily dismissible as outliers. However, in Figure 23, where the receiver is located in a dense urban location, the candidate position solutions are spread over more than 100 meters, and the correct position solution is not clear. The densest cluster of positions is far from both the centroid and the truth. Therefore, anomalous signal propagation may be treated as an ambiguity problem.
Figure 22. GNSS position errors using different combinations of signals in a rooftop environment. (Photo: Paul D. Groves, Lei Wang, Debbie Walter and Ziyi Jiang, University College London)Figure 23. GNSS position errors using different combinations of signals in a dense urban environment. (Photo: Paul D. Groves, Lei Wang, Debbie Walter and Ziyi Jiang, University College London)
Geometric Ambiguity. Geometric ambiguity occurs when more than one position solution may be derived from a set of otherwise unambiguous measurements. Figure 24 shows two examples. On the left, two ranging measurements in two dimensions produce circular lines of position that intersect in two places. On the right, a ranging measurement and a direction-finding measurement are made using the same signal. As direction finding has a 180° ambiguity, the lines of position also intersect at two places.
Figure 24. Geometric ambiguity in two dimensions from two ranging measurements (left), and a ranging and direction-finding measurement (right). (Photo: Paul D. Groves, Lei Wang, Debbie Walter and Ziyi Jiang, University College London)
System Reliability. Navigation subsystems can produce incorrect information for a host of different reasons. Some examples include:
user equipment hardware and software faults;
transmitter hardware and software faults;
out-of-date databases used for pattern matching, including TRN, GNSS shadow matching, and map matching;
wheel slips in odometry;
the effects of passing vehicles and animals on environmental feature visibility, availability and strength of radio signals, and Doppler-based dead reckoning.
Some of these failure modes are easily detectable through the measurements failing basic range checks or being absent altogether. In other cases, faults may be detected by consistency checks within the subsystem. For example, wheel slip may be detected by comparing measurements from different wheels, while Doppler radar and sonar systems typically incorporate a redundant beam to enable the interruption of a beam by a vehicle or animal to be detected.
Subsystems can sometimes output incorrect information that is plausible. An ambiguity thus exists where it is uncertain whether or not a measurement may be trusted. An ambiguity also exists where a fault has been detected, but not its source. Thus, some of the information produced by the subsystem must be incorrect, but some of it may be correct.
Context Ambiguity. As discussed in Part 1 of this article (October issue), the optimum way of processing sensor information depends on the context. However, if context information is used, the navigation solution will then depend on the assumed context. For example, if an indoor environment is assumed, indoor radio positioning and map-matching algorithms that are only capable of producing an indoor position solution may be used. Similarly, if an urban environment is assumed, GNSS shadow matching and outdoor map matching may be selected, resulting in an outdoor position solution. Adoption of pedestrian and vehicle motion constraints can also lead to different navigation solutions.
Context determination is not a completely reliable process. Therefore, to minimize the impact of incorrect context assumptions on the navigation solution, the context should be treated as ambiguous whenever there is significant uncertainty.
Possible Solutions
There is no obvious solution to the ambiguity problem. Instead, different approaches to integrating ambiguous information may be adopted depending on the relative priorities of solution availability, reliability, and processing load. The main approaches, illustrated in Figure 25, are discussed below. They all require the subsystems to present the different measurement hypotheses and their associated probabilities to the integration algorithm.
Figure 25. Methods of handling ambiguous measurements in a navigation integration algorithm. (Photo: Paul D. Groves, Lei Wang, Debbie Walter and Ziyi Jiang, University College London)
Accept or reject the lead hypothesis. The simplest way of handling ambiguous information is to maintain a single-hypothesis navigation solution and consider only the most-probable hypothesis from each subsystem. This is then accepted or rejected based on the following criteria:
Whether the probability of the highest scoring hypothesis above a certain threshold.
Whether the probability of the second-highest scoring hypothesis below a certain threshold.
Whether the highest-scoring measurement hypothesis is consistent with the current integrated navigation solution. (Determinable using measurement innovation filtering.)
Context may be incorporated into this approach by accepting the highest-scoring behavioral and environmental contexts where they meet the above criteria and computing a context-independent navigation solution otherwise.
This approach is processor-efficient, but high integrity and availability cannot be achieved simultaneously. Low acceptance thresholds provide high reliability by rejecting most erroneous measurements, but low solution availability as many good measurements are also rejected. Conversely, high acceptance thresholds provide availability at the expense of reliability.
Accept all hypotheses into a single-hypothesis solution. A probabilistic data association filter (PDAF) accepts multiple measurement or context hypotheses, weighting them according to their probabilities, but represents the navigation solution as the mean and covariance of a uni-modal distribution. The measurement update to the state estimation error covariance matrix accounts for the spread in the hypotheses such that the state uncertainties can sometimes increase following a measurement update.
This approach reconciles the demands of integrity and availability at the price of a moderate increase in processing load. However, the uni-modal navigation solution can sometimes be misleading. For example, if a pattern-matching system determines that the user is equally likely to be in one of two parallel streets, the overall position solution will be midway between those streets.
Multi-hypothesis integration accepting all hypotheses. Multi-hypothesis integration deals with multiple measurement and context hypotheses by spawning multiple integration filters, one for each hypothesis. Each filter is allocated a probability based not only on the probabilities of the measurements input to it, but also on the consistency of those measurements with the prior estimates of that filter. This consistency-based scoring is essential; otherwise the filter hypothesis that inputs the highest-scoring measurement hypotheses will always dominate, regardless of whether those measurements are consistent across subsystems and successive epochs.
A fundamental characteristic of multi-hypothesis filtering is that the number of hypotheses grows exponentially from epoch to epoch. This is clearly impractical, so the number of hypotheses is limited by merging the lowest scoring hypotheses into higher scoring neighbors.
The overall navigation solution is the weighted sum of the constituent filter hypotheses. Each individual filter hypothesis describes a uni-modal distribution. However, the combined navigation solution is multi-modal. Thus, the position probability can be higher in two streets than in the buildings between those streets. This is a clear advantage over the PDAF-based approach, but the processing load is higher.
Multi-modal integration accepting all hypotheses. A multi-modal filter is not constrained to model the states it estimates in terms of a mean and covariance. This enables it to process multiple measurement and/or context hypotheses and represent the result as a weighted sum of the probability distributions arising from the individual hypotheses. Suitable data-fusion algorithms include the Gaussian mixture filter and the particle filter. A key advantage over multi-hypothesis integration is that measurements may be treated as continuous probability distributions instead of as a set of discrete hypotheses. This enables pattern-matching measurements to be integrated more naturally and offers greater flexibility in handling signal propagation anomalies.
A Gaussian mixture filter models the probability distribution of the navigation solution as the weighted sum of a series of multi-variate Gaussian distributions. An example is the iterative Gaussian mixture approximation of the posterior (IGMAP) technique, which has been applied to terrain referenced navigation integrated with inertial navigation.
A particle filter models the probability distribution of the navigation solution using a series of semi-randomly distributed samples, known as particles. Between a thousand and a million particles are typically deployed, with a higher density of particles in higher probability regions of the distribution. Particle filters have been used with a number of different navigation technologies, including TRN, pedestrian map matching, Wi-Fi positioning, and GNSS shadow matching.
Multi-modal integration algorithms offer the greatest flexibility in reconciling the demands of solution availability and reliability, but also potentially impose the highest processing load.
Issues to Resolve
The key challenge in handling ambiguous measurements is determining realistic probabilities for each hypothesis. A probability must also be calculated for the null hypothesis, that is, the hypothesis that every candidate measurement output by the subsystem is wrong. The same applies to ambiguous context.
A feature identification algorithm must allocate a score to every database feature that it compares with the sensor measurements. In practice, only features within a predefined search area, based on the prior position solution and its uncertainty, will be considered. Features scoring above a certain threshold will be possible matches. Similarly, pattern- matching algorithms allocate a score to each candidate position in the search area according to how well the sensor measurements match the database at that point. For correct handling of ambiguous matches, these scores should be as close as possible to the probabilities of the feature match or candidate position being correct.
Feature identification and pattern-matching algorithms can also fail to consider the correct feature or candidate position for several reasons. The correct feature or position may be outside the database search area. It may be absent due to the database being out of date. The sensor may also observe or be affected by a temporary feature that is not in the database, such as a vehicle. The null hypothesis probability must account for all of these possibilities. In practice, it will be higher where there is no good match between the measurements and database.
Signal propagation anomalies affect the error distributions of ranging, angle, and Doppler shift measurements, and the positions and velocities derived from them. These error distributions depend on whether the signals are direct line-of-sight (LOS), non-line-of-sight (NLOS), or multipath- contaminated LOS. However, this is not typically known. Signal strength measurements, environmental context, signal elevation (for GNSS), distance from the transmitter (for terrestrial signals), consistency between different measurements, and 3D city models can all contribute useful information. However, their relationship with the measurement errors is complex, so a semi-empirical approach is needed.
Moving on to reliability, virtually any subsystem can produce false information. The overall probability will typically be very low and thus only significant for high-integrity applications. However, the failure probability will be higher in certain circumstances, in which case the relevant subsystem should report a higher null probability. For example, in odometry, the probability of a wheel slip depends on host vehicle dynamics. Similarly, a radio signal is more likely to be faulty if it is weaker than normal. Repeated measurements, changes to the update interval, and sudden changes in a sensor output are also indicative of potential faults.
Geometric ambiguity is easy to quantify as the candidate solutions have equal probability in the absence of additional information.
As proposed in Part 1, the context determination process should produce multiple context hypotheses, each with an associated probability. Therefore, it is important to ensure that all navigation subsystems that use this context information do so in a probabilistic manner. Thus, where different context hypotheses lead to different values of the measurements output by a navigation subsystem, each measurement hypotheses should be accompanied by a probability derived from the context probabilities.
A further issue to resolve is the relationship between discrete and continuous ambiguity. Ambiguities in feature identification, solution geometry, failures, and context categorization are discrete and are suited to integration filters that treat them as a set of discrete hypotheses. However, the position solution ambiguity in pattern-matching is continuous, that is, the probability density is a continuous function of position, albeit sampled at discrete grid points. This probability distribution may be input directly to a particle filter. However, if the integration algorithm is a uni-modal filter or a bank of uni-modal filters, the probability distribution must be converted to a set of discrete hypotheses. This can be done by fitting a set of Gaussian distributions to the probability distribution. For signal propagation anomalies, their presence or absence is discrete. However, the resulting measurement error distribution is continuous, so a similar approach is appropriate.
The same challenging environments that require multiple navigation subsystems to maximize solution availability, accuracy, and reliability can also induce those subsystems to produce ambiguous measurements. Consequently, the modular integration architecture proposed in Part 1 should be capable of handling ambiguous measurements.
This is discussed further in our IEEE/ION PLANS 2014 paper, “The Four Key Challenges of Advanced Multisensor Navigation and Positioning.”
Environmental Data
Position-fixing systems need information about the environment, sometimes known as a “world model,” to operate. Proximity, ranging, and angular positioning all use landmarks that must be identified. For GNSS and other long-range radio systems, identification codes are determined when the system is designed and incorporated in the user equipment. However, this is not practical for shorter range signals, whether opportunistic or designed for positioning, due to the vast numbers of transmitters available worldwide and the fact that many will be installed during the lifetime of the user equipment. The user equipment will also require information on the characteristics of a signal to enable it to use that signal for ranging. A mobile device equipped with a generic radio or transceiver may be required to download software to enable it to use a proprietary indoor positioning system. For environmental feature-matching techniques, the user equipment requires information to enable it to identify each landmark.
Navigation using landmarks also requires their positions and, for passive ranging, their timing offsets. Signals designed for positioning typically provide this information, but it can take a long time to download (30 seconds for GPS C/A code) and can be difficult to demodulate under poor reception conditions. The positions of opportunistic radio transmitters and environmental features must be determined by other means.
For positioning using the pattern-matching method, a measurement of radio signal strength or a characteristic of the environment, such as the terrain height or magnetic field, is compared with a database to determine position. Therefore, a database providing values of the measured parameter over a regular grid of positions is required. Map matching requires a map database to indicate where the user can and cannot go. GNSS shadow matching requires a 3D city model to predict signal visibility.
Finally, as discussed in Part 1 of this article, mapping is required to determine environmental context information from the position solution and to enable location-dependent context connectivity information (for example, the location of train stations) to be used for context determination.
Possible Solutions
We discuss in turn the environmental data collection and its distribution to the user equipment.
Data Collection. Positioning data may be collected either from a systematic survey or by the users. In either case, regular updates will be required. A systematic survey might be conducted by the subsystem supplier, a national mapping agency, or a private third party. The user will need to pay for the data in some way. It could be included in the equipment cost, via a subscription payment, by accepting advertising, or through general taxation (for some national mapping agency data). For mobile devices, such as smartphones, mapping data may be available for some applications, but not others.
Single-user data collection does not involve user charges, but only provides data for places the user has already visited. A simple approach requires a good position solution to collect mapping data. This can work for applications that normally use GNSS, but require backups for temporary outages. However, it does not work for areas where GNSS reception is poor. Simultaneous localization and mapping (SLAM) techniques can perform mapping without a continuous position solution. However, there are several constraints. First, a good position solution that is independent of the data being mapped is required at some point, usually the start. Second, a navigation system including dead-reckoning technology must be used. Third, locations must be visited repeatedly within a short period of time (to achieve “loop closure”). Finally, only features close to the user can be mapped.
Cooperative mapping by a group of users solves many of the problems of single-user mapping. It can provide individual users with data for places they have not visited before. Distant landmarks can also be mapped more easily by multiple users, particularly where it is necessary to determine a timing offset as well as the location. However, a method for comparing and combining data from multiple users is required.
Data Distribution. For data collected by a systematic survey, there are two main data distribution models: pre-loading and streaming. Pre-loading requires sufficient user equipment data storage to cover the area of operation. New data may have to be loaded prior to a change in operating area, and updates will be required. However, a continuous communications link is not needed.
Streaming requires much less data to be stored by the user and provides up-to-date information, but only where a communications link is available. Although buffering can bridge short outages, navigation data is simply not available for areas without sufficient communications coverage. Continuous streaming can also be expensive. One solution is a cooperative approach using peer-to-peer communications for much of the data distribution. A pair of users traveling in opposite directions along the same route will each have data that is useful to the other. A further possibility is to incorporate local information servers in Wi-Fi access points for exchanging information relevant to the immediate locality. This might be best suited to indoor navigation, where there is an incentive for the building operator to provide the service.
For data collected by a single user, no data distribution is required other than a back-up. For cooperative data collection by multiple users, a method of data exchange is needed. This can be via a central server, communicating either in real time or whenever the user returns to base. It can also be through peer-to-peer communications or through local information servers, where there is an incentive to provide them.
Issues to Resolve
Standardization is a major part of the data management challenge. A multisensor navigation system will typically incorporate multiple subsystems with data requirements. This might include road or building mapping, radio signal information, terrain height, magnetic anomalies, visual landmarks, and building signal-masking information for GNSS shadow matching. There will be a different standard for each type of data. Furthermore, different subsystem suppliers will often use different standards for the same type of data. This is sometimes done for commercial and/or security reasons, so the data may be encrypted. There may also be technical reasons for different data standards. For example, in image-based navigation, different feature recognition algorithms require different descriptive data.
Ideally, all navigation data in a multisensor system should be distributed by the same method. This requires agreement of storage and communication protocols that can handle many different data formats, including encrypted proprietary data and future data formats. Open standards for each type of data should also be agreed, noting that consumer cooperative positioning using peer-to-peer communications and/or local information servers is probably only practical with open data formats. Ideally, the standards should be scalable to enable precisions, spatial resolutions, and search areas to be adapted to the available data storage and communications capacity.
Peer-to-peer data exchange requires a suitable communications link. Bluetooth is the established standard for consumer applications. Classic Bluetooth provides sufficient capacity, but it takes longer to establish a connection than passing pedestrians or vehicles remain within range. Bluetooth low energy can establish a connection quickly, but the data capacity is limited to 100 kbit/s. This is sufficient for some kinds of navigation data, but not others. Professional and military users have more flexibility to select suitable datalinks.
Finally, establishing local information servers requires both standardization and an incentive for the hosts. Demand would be greater if there were applications beyond navigation and positioning. Possibilities include product information in shops and exhibit information in museums, both of which might be provided more efficiently from a local server than the Internet. For home users to provide local information servers, they would also have to benefit from them, a potential “chicken-and-egg” problem. For military applications, local information servers are a potential security risk and a target for attack.
Conclusions and Recommendations
Achieving accurate and reliable navigation in challenging environments without additional infrastructure requires complex multisensor integrated navigation systems. However, implementing them presents four key challenges: complexity, context, ambiguity, and environmental data handling. Each of these problems has been explored and solutions proposed.
Conclusions. In Part 1 of this article, a modular integration architecture was proposed to enable multiple subsystems from different organizations to be integrated without the need for whole system expertise or sharing of intellectual property. Furthermore, context-adaptive navigation was proposed to enable a navigation system to respond to changes in the environment and host vehicle (or user) behavior, deploying the most appropriate algorithms. A new probabilistic approach to context determination was proposed and results presented from a number of context detection experiments.
Here, it has been shown that navigation solution ambiguity can arise from feature identification, pattern matching, propagation anomalies, solution geometry, system reliability issues, and context ambiguity. A number of methods for handling ambiguous measurements in a multisensor navigation system have been reviewed.
Finally, methods of collecting and distributing data such as locations of radio transmitters and other landmarks, information for identifying signals and landmarks, road or building mapping, terrain height, magnetic anomalies, and building signal-masking information (for GNSS shadow matching) have been discussed.
Implementing the ideas proposed in this two-part article requires both standardization and further research. Standardization is needed to enable the communication between modules produced by different suppliers of information such as the integrated navigation solution, sensor measurements and characteristics, calibration parameters, performance requirements, context information, mapping, and signal and feature characteristics.
Further research is needed to support this standardization process, including the identification of a set of fundamental measurement types and their error sources, and the establishment of the best set of context categories for integrated navigation.
Extensive research into context detection and determination is needed, including the measurements to use, the statistical parameters to derive from those measurements, and a set of context association and connectivity rules.
An assessment of the different methods for handling ambiguous measurements is needed, comparing accuracy, reliability, solution availability, and processing load. This will enable the community to determine which methods are suited to different applications.
Finally, there is a need for a practical demonstration of the key concepts proposed in this paper, including modular integration, context adaptivity, ambiguous measurement handling, and collection and distribution of environmental data.
Paul D. Groves is a lecturer at University College London (UCL), where he leads a program of research into robust positioning and navigation. He is an author of more than 60 technical publications, including the book Principles of GNSS, Inertial and Multi-Sensor Integrated Navigation Systems, now in its second edition. He is a Fellow of the Royal Institute of Navigation and holds a doctorate in physics from the University of Oxford.
Lei Wang is a Ph.D. student at UCL. He received a bachelor’s degree in geodesy and geomatics from Wuhan University. He is interested in GNSS-based positioning techniques for urban canyons.
Debbie Walter is a Ph.D. student at UCL. She is interested in navigation techniques not reliant on GNSS, multi-sensor integration, and robust navigation. She has an MSci from Imperial College London in physics and has worked as an IT software testing manager.
Ziyi Jiang was a postdoctoral research associate at UCL until 2014, working on urban GNSS and other projects. He holds a bachelor’s degree in engineering from Harbin University and a Ph.D. in rail positioning from UCL. He now works in finance.
All authors are members of UCL Engineering’s Space Geodesy and Navigation Laboratory (SGNL).
