Tag: GPS receiver

Using Wavelets for a Robust Vector-Tracking-Based GPS Software Receiver

ALFRÉD HAAR. Who is he, you might ask? Alfréd Haar was a Hungarian mathematician who introduced the concept of wavelets during his Ph.D. work on orthogonal functional systems under David Hilbert of Hilbert transform fame. And what is a wavelet? Generally speaking, a wavelet, as its name suggests, is a brief oscillation in time with an amplitude that begins at zero, goes through one or more variations, and returns to zero. It’s a bit like the cardiac cycle of each heartbeat shown on an electrocardiogram. But wavelets, unlike heartbeats, are mathematical functions with well-defined properties.

Although Haar initiated the use of wavelets back in 1909, it was not until the 1970s and 1980s that the study of the use of wavelets — wavelet analysis — was undertaken to help solve a variety of problems in science and engineering with new application areas springing up all the time. We’ll get to one of these new areas — GNSS jamming mitigation — in just a bit, but let’s discuss a more mundane application first.

Let’s say we have a digitized audio recording of Maynard Ferguson’s rendition of “MacArthur Park” in our computer. We could do a Fourier transform (related to the Hilbert transform mentioned earlier) of the entire recording, which would show us all of the specific audio frequencies making up the song. But what if we wanted to determine where in the song Ferguson played a particular high note, such as double high C (not his highest)? We could create a wavelet with that frequency and a short duration such as that of a 32nd note and use the mathematical operation of convolution (involving shifting, multiplication and integration) to find one or more spots in the recording with a similar frequency. We could extend the procedure and use a set or bank of wavelets to fully study the song in both frequency and time.

Wavelet analysis will work on many kinds of data, not just audio signals. With an appropriate set of wavelets, we could decompose the data without gaps or overlap, store the resulting product for further analyses and, if necessary, reconstitute the original data with minimal distortion. The U.S. Federal Bureau of Investigation uses wavelet analysis to store compressed digital versions of fingerprint images. A heavily damaged recording of Brahms playing one of his own compositions on an Edison wax cylinder was partially restored using wavelet analysis despite the music being immersed in noise. And the small effect of El Niños on the Earth’s rotation has been studied using wavelet analysis.

And, yes, wavelet analysis is helping to improve the use of GNSS. The tasks being undertaken include de-noising of pseudorange measurements, cycle-slip detection and elimination in carrier-phase measurements, and separating biases such as multipath from high-frequency receiver noise. In this month’s column (which, by the way, now appears four times per year), we learn about another GNSS application of wavelet analysis — specifically the use of the wavelet packet transform — to efficiently identify and separate a jamming signal from the combined signal in a GPS receiver. In a narrowband jamming test using a hardware simulator system, no positioning was possible with conventional receiver operation. But with the proposed approach, the jamming signal was readily suppressed, allowing the satellite signals to be acquired and a positioning solution to be computed. Thank you, Alfréd Haar.

---

GPS technology has been integrated into many aspects of our daily lives. Hence, there is a growing demand for a robust GPS receiver that can operate efficiently without external aiding to provide continuous, reliable and accurate positioning, navigation and timing (PNT) solutions. However, this is not always possible due to frequent loss or attenuation of signals, multipath or interference. In such challenging conditions, a system malfunction can cause safety problems, especially in health-critical applications.

Receiver architecture plays a major role in defining a receiver’s robustness against the challenges just mentioned. Scalar-tracking-based GPS receivers can achieve high navigation accuracy under line-of-sight (LOS) conditions. However, they always fail to provide adequate accuracy in signal-degraded environments such as urban, suburban and dense foliage environments. On the contrary, vector-tracking-based GPS receivers provide better performance in such challenging environments. In vector-tracking-based receivers, both the tracking loops and the navigation processor are combined to solve a single estimation problem. Hence, there are many advantages of this architecture over that of scalar-tracking-based receivers. First, information from strong signals from healthy satellites is used to track weak signals, when signals are highly attenuated or even totally blocked. Thus, vector-tracking-based receivers have better immunity to jamming and interference. Second, they can rapidly reacquire signals after a satellite outage. Third, they have an improved navigation solution accuracy compared to that of scalar-tracking-based receivers, even under normal LOS conditions. All of these advantages make vector-tracking-based receivers the best platform for our research on receiver robustness. However, vector-tracking-based receivers still suffer from degraded performance in the presence of strong jamming signals. Therefore, we are proposing a new anti-jamming technique to be employed for interference mitigation in vector-tracking-based GPS receivers.

The spread-spectrum nature of GPS signals provides resistance to narrowband interference due to the spreading and despreading processes that take place at the transmitter and receiver respectively. However, a GPS signal reaches the receiver with very low power on the order of –158 dBW, which makes it vulnerable to jamming. A jammer with enough power and suitable time and frequency properties can degrade the positioning solution accuracy and may cause a total blockage of the GPS signals. Besides, the presence of a jamming signal increases the challenge of acquisition of the desired GPS signal.

Therefore, many anti-jamming techniques have been employed for interference mitigation in GPS receivers. There are various anti-jamming methods for GPS receiving systems, which are mainly classified into four groups:

1. Antenna-level techniques, which are based on the use of antenna arrays to generate a radiation (reception) pattern that attenuates the interference signal based on the direction of arrival.
2. Automatic gain control (AGC), where interference can be detected by the saturation of the AGC.
3. Post-correlation techniques, which process the signals after passing through the correlators.
4. Pre-correlation techniques, which are based on processing the signals after passing through the analog-to-digital converter but before they get to the correlators.

This article introduces a novel interference mitigation technique based on the wavelet packet transform (WPT), which belongs to the pre-correlation techniques category. The WPT enables the received interfered combined GPS signal to be represented in a transformed domain in which an interference signal can be better identified and separated, without significant degradation of the useful GPS signal. The WPT has been extensively discussed in the literature in the framework of GPS and other GNSS. For example, wavelet multi-resolution analysis has been used in one study to remove the multipath error and leave the useful signal untouched. In another study, multi-resolution analysis using wavelets was applied to pseudorange and carrier-phase GPS double differences to reduce multipath effects. And in another, researchers developed a technique to detect and remove cycle slips based on wavelet multiresolution analysis.

The WPT has been widely used in the context of jamming to mitigate pulsed and narrowband interference. Although the WPT showed outstanding performance in jamming mitigation, the main drawback of this technique is the computational complexity. In this article, we introduce a novel wavelet packet-based technique for narrowband jamming mitigation with significantly reduced computational complexity.

Signal and Interference Models

The GPS signal employs a direct sequence spread spectrum communication technique, in which the signal is multiplied by a spreading or pseudorandom noise (PRN) code. As mentioned earlier, this spreading technique gives GPS some immunity to narrowband jamming. The received digitized spread spectrum signal at the output of the receiver’s analog to digital converter (ADC) can be represented by:

(1)

where, for signal s, y_m(nT_s) is the useful GPS signal received from mth LOS satellite, j(nT_s) is the jamming signal, w(nT_s) is additive white Gaussian noise (AWGN), M is the number of visible satellites, n is the sample number and T_s is the sampling rate.

The useful received GPS signal can be described as follows:

(2)
where P is the signal power, d(nT_s) is the navigation data, c(nT_s) is the spreading pseudorandom noise code, f_IF is the intermediate frequency, n_o is the code delay, f_d is the Doppler shift, and θ_o is the carrier phase.

Interference signals are classified based on their spectrum characteristics: narrowband or wideband depending on the signal’s bandwidth relative to the bandwidth of the desired GPS signal.

Our focus in this article is on the mitigation of narrowband interference, specifically a linear chirp signal. A chirp signal can be expressed as:

(3)

where a is the chirp signal amplitude, f_o is the starting frequency, k is the sweeping frequency, and T_sw is the sweeping frequency period. The chirp is continuously repeated.

Wavelet Packet Transform

The wavelet packet transform or WPT is a class of transformed domain techniques that has been widely used in the context of jamming mitigation in GPS signal reception. It allows for the study of a signal in both time and frequency domains simultaneously. In the WPT, the signal is decomposed into approximations (the low-pass component) and details (the high-pass component) with respect to a group of local basis functions. These functions can be obtained through dyadic scaling and shifting of the so-called mother wavelet. The discrete wavelet basis functions are given by:

(4)

where j and k are integers, s_o is the dilation step, and τ_o is the scaling coefficient. The decomposition of the signal with respect to a scaling function acts as low-pass filtering of the signal, while the decomposition with respect to a wavelet function acts as high-pass filtering of the signal. The signal is then down-sampled, and this procedure is further iterated on all the sub-bands using scaled and dilated versions of the wavelet and scaling functions. This filtering process allows the decomposition of the GPS signal with respect to a local basis function, in which each of these sub-bands identifies a limited frequency band of the received signal, and the frequency resolution is dependent on the level of decomposition. The wavelet packet decomposition can be realized as a filter-bank as depicted in FIGURE 1.

Jamming Mitigation Algorithm

As mentioned earlier, the main drawback of WPT is the time complexity. Due to the decomposition of both approximation and detail components, if the signal is decomposed into L levels, the resultant number of coefficients is 2L. For instance, if we used 10 decomposition levels, the resultant number of wavelet coefficients is 210 (1,024). However, as each wavelet coefficient component represents a limited portion of the frequency of the received signal, the jamming signal will only affect a few coefficients. Thus, the main idea of the proposed algorithm is to identify those coefficients that are affected by the jamming signal and reconstruct the jamming signal after denoising them. Then, the estimated jamming signal is subtracted from the received signal to obtain the jamming-free useful GPS signal.

Identifying the wavelet coefficients affected by interference is achieved by computing the median absolute deviation (MAD). As those coefficients that are affected by interference have a higher MAD value than those that are not affected, the decision of whether the wavelet coefficients are affected by interference is based on comparing their MAD values with a certain predefined threshold. This threshold is determined based on the desired detection and false alarm probabilities according to the distribution of the received signal samples in an interference-free environment. Only the sub-bands whose MAD values exceed the threshold are considered to be affected by interference and are further decomposed.

Therefore, only the sub-bands affected by interference are isolated and iterated. This technique allows for a considerable reduction in complexity, as both detection and mitigation can be applied in a limited number of sub-bands. FIGURES 2 and 3 show the tree decomposition of the received signal of two jamming scenarios based on the proposed algorithm. The frequency offset of the jamming signal from the GPS signal is 200 kHz in the first scenario and 600 kHz in the second one. The figures clearly illustrate the huge reduction in computational complexity as for 10 levels of decomposition; we ended up having only eight wavelet coefficients instead of 1,024.

The proposed wavelet packet-based detection and mitigation algorithm is explained in three steps.

Decomposition Step. The incoming GPS signal is decomposed through a uniform filter bank by only one level. Then, MAD is computed for all the decomposed sub-bands. Only sub-bands with a MAD value greater than the predefined threshold will be further decomposed. This step is repeated until the maximum predefined decomposition level is reached.

Detection Step. The MAD value is computed for all sub-bands from the last decomposition level. Only sub-bands whose MAD value exceeds the predefined threshold are considered affected by interference and are used to reconstruct the jamming signal using the inverse wavelet transform.

Reconstruction Step. In this step, the useful GPS signal is reconstructed free of interference by subtracting the estimated jamming signal from the received signal.

Experimental Work

In our investigation, a GNSS simulation system was used to create a fully controlled environment to examine and validate the performance of the proposed method using semi-real simulation scenarios. The simulator was controlled by simulation software that enables the simulation of multipath reflections through an advanced multipath model as well as atmospheric degradation to signals and the effects of antenna patterns and terrain obscuration. Moreover, it can generate simulated land, air, space and sea trajectories. Furthermore, the simulator when connected to an interference simulation system can provide various controlled jamming environments using an interference signal generator. The full setup is shown in FIGURE 4.

The receiver used in this research is a prototype of a digital front end. The front end collects the output radio frequency (RF) signal from the simulator. Then, the RF signal is down-converted to baseband through several down-conversion stages, generating the in-phase (I) and quadrature-phase (Q) data. Then, the data is sampled and quantized through the ADC. The front end collects GPS L1 signals at different bandwidths ranging from 2.5 MHz to 20 MHz with quantization levels ranging from 1-bit to 8-bit. After that, the sampled digitized signal is sent to the computer via an Ethernet connection.

The raw I/Q GPS samples are then processed by a GPS software receiver. Our proposed algorithms have been implemented using Matlab by modifying the open-source GPS software-defined radio (SDR) receiver composed by Borre and Akos, which is widely used in research.

To verify the performance of the new proposed algorithm, a full GPS C/A-code signal was simulated using the previously mentioned simulation system. A static simulated scenario was generated for this purpose. This static scenario was run twice, once in an interference-free environment for reference, and one where the jamming signal was enabled. The simulation, front end and SDR receiver parameters are shown in TABLE 1.

FIGURES 5 and 6 show the power spectral density (PSD)of the received signal before and after applying the proposed jamming mitigation technique. The figures demonstrate that the interference components have been highly attenuated. To confirm the benefits of the proposed technique, the reconstructed useful GPS signal has been acquired using the SDR receiver.

FIGURE 7 shows that the receiver is in a total blockage as it failed to acquire any satellite before applying the jamming mitigation technique. However, FIGURE 8 shows that the proposed algorithm allowed the retrieval of seven satellites.

FIGURE 9 shows the cross-ambiguity function (CAF) of PRN31 before jamming mitigation. It is obvious from the figure that the search space is quite noisy, and the receiver fails to acquire the GPS signal due to the difficulty of isolating the peak from the noise. However, FIGURE 10 shows that the peak clearly emerges from the noise floor and can be easily detected by the receiver after applying the jamming mitigation algorithm.

These figures demonstrate the power of the proposed algorithm and confirms that the useful signal is not lost during the filtering process. Before applying the jamming mitigation algorithm, the receiver lost lock on all satellites and failed to provide a navigation solution. However, after applying the proposed algorithm, the navigation solution is available with an accuracy of about 10 meters in the east and north components and around 20 meters in the up component, as shown in FIGURE 11.

Conclusion

In this article, we have proposed a new method for mitigating a linear chirp narrowband jamming signal based on the WPT. Although the WPT has been widely used in the literature in the context of mitigating narrowband jamming, this technique is characterized by a significant computational complexity that is not only proportional to the length of the signal, but also proportional to the wavelet decomposition level.

The results show that our proposed algorithm is able to maintain excellent performance in the suppression of the jamming signal with a significant reduction in complexity. In the proposed technique, the sub-bands affected by interference are identified and are further decomposed to be used to reconstruct the jamming signal. Then, the useful GPS signal is obtained by subtracting the estimated jamming signal from the received signal. The performance of the algorithm has been assessed with respect to acquisition and navigation performance. The results show that the proposed algorithm successfully suppressed narrowband jamming without significantly degrading the useful GPS signal.

Acknowledgments

This article is based on the paper “A Novel Wavelet Packet-based Jamming Mitigation Technique for Vector Tracking-based GPS Software Receiver” presented at ION GNSS+ 2018, the 31st International Technical Meeting of the Satellite Division of The Institute of Navigation, Miami, Florida, Sept. 24–28, 2018. The research was supported by the Natural Sciences and Engineering Research Council of Canada.

Manufacturers

The simulation system used a Spirent Communications Inc. GSS6700 Multi-GNSS Constellation Simulator, a Spirent GSS8366 Interference Combiner Unit and a Keysight Technologies N5172B-503 Interference Signal Generator. The receiver front end used was a NovAtel Inc. FireHose D17088 prototype digital GNSS front end.

---

HAIDY Y. ELGHAMRAWY is a Ph.D. candidate in the Department of Electrical and Computer Engineering, Queen’s University, Kingston, Ontario, Canada. She received her M.Sc. degree in engineering physics and mathematics from the Faculty of Engineering, Cairo University, Egypt.

MOHAMED YOUSSEF is leading GPS/GNSS product development activities for Sony North America. He holds an interdisciplinary Ph.D. degree from the Department of Geomatics Engineering and the Department of Electrical and Computer Engineering, University of Calgary, Canada.

ABOELMAGD M. NOURELDIN is a cross-appointment associate professor in the Departments of Electrical and Computer Engineering at Queen’s University and the Royal Military College (RMC) of Canada in Kingston. He is the director of RMC’s Navigation and Instrumentation Research Laboratory.

 

FURTHER READING

(to come)