Sparse GLONASS Signal Acquisition Based on Compressive Sensing and Multiple Measurement Vectors

Abstract

A sparse global navigation satellite system (GLONASS) signal acquisition method based on compressive sensing and multiple measurement vectors is proposed. The nonsparse GLONASS signal can be represented sparsely on our proposed dictionary which is designed based on the signal feature. Then, the GLONASS signal is sensed by a normalized orthogonal random matrix and acquired by the improved multiple measurement vectors acquisition algorithm. There are 10 cycles of pseudorandom codes in a navigation message, and these 10 pseudorandom codes have the same row sparse structure. So, the acquisition probability can be raised by row sparse features theoretically. A large number of simulated GLONASS signal experiments show that the acquisition probability increases with the increase in the measurement vector column dimension. Finally, the practical availability of the new method is verified by acquisition experiments with the real record GLONASS signal. The new method can reduce the storage space and energy loss of data transmission. We hope that the new method can be applied to field receivers that need to record and transmit navigation data for a long time.

This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

1. Introduction

Global navigation satellite system (GLONASS), which was developed by the Soviet Union first, is maintained and developed by Russia now. The purpose of GLONASS is to provide unlimited number of air, marine, and any other type of users with all-weather three-dimensional positioning, velocity measuring, and timing anywhere in the world or near-earth space [1]. Until the writing date of this article (25/4/2020), the number of GLONASS satellites in orbit has reached 27. 24 satellites are working normally, such as launching navigation data and time, 1 satellite is in the flight test phase, and 2 satellites are spares. 24 satellites are evenly distributed on three near-circular orbital planes, the three orbital planes are separated by 120 degrees, and the satellites in the same plane are separated by 45 degrees. The orbit altitude is about 19100 kilometers, and the running cycle is 11 hours 15 minutes 44 seconds [2]. Due to the geographical position of Russia, the inclination angle of the GLONASS orbital plane is 64.8 degrees, which is larger than that of the American global position system (GPS), which is 55 degrees, so the coverage effect is better than GPS at high latitudes [3, 4].

For the GLONASS receiver, it must acquire the satellite signal in the line of sight firstly. The GLONASS signal is a kind of a spread spectrum signal, so the spread spectrum code phase is unknown. Due to the relative motion of the satellite and the receiver, the carrier frequency is changed, called Doppler frequency. The aim of acquisition is to estimate the coarse spread spectrum code phase and Doppler frequency of the satellite in the field of view [5]. The acquisition is a two-dimensional searching process, which needs to search all the likely spread spectrum code phase and Doppler frequency at the same time. The serial acquisition method is a common method, which needs to reconstruct all possible code phase and Doppler frequency and correlate with the satellite signal. The parallel acquisition method which uses Fourier transform can improve the acquisition effect, but it increases the complexity [6].

The traditional acquisition methods are based on the Nyquist sampling theory, which is a redundant sampling method [7]. The recently proposed compressive sensing (CS) theory can greatly reduce the sampling frequency of sparse signals and reconstruct the sparse signal from the single measurement vector (SMV) through some reconstruction algorithms [8, 9]. Now, CS has been applied in many fields including medical image processing [10] and narrowband spectrum sensing [11]. In recent years, several CS-based methods have been improved for global navigation satellite system (GNSS) signal acquisition. In [12], the author proposed a two-stage deterministic GNSS signal acquisition technique using the Walsh–Hadamard matrix. The proposed method makes fast acquisition possible, but the method needs two stages which may be a little complicated. In [13], the authors proposed an efficient acquisition technique for the GPS receiver. The new method sampled and detected the GPS signal using a bank of randomized correlators with much fewer chip-matched filters than the traditional acquisition method. The GPS signals can be acquired by the proposed technique, but it increased the hardware complexity of the receiver. In [14], the authors proposed a GPS signal acquisition method based on CS. The matching pursuit algorithm is used to recover the GPS sparse signal. Numerical simulations illustrate that the method can recover the GPS sparse spike signal effectively. The application of compressive sensing in GNSS is limited to GPS with SMV, and until now, the application in GLONASS with MMV is not reported.

In radar signal processing, it needs to estimate the direction of arrival (DOA), direction finding, direction of departure (DOD), and so on [15, 16]. Multi-input multioutput radar (MIMO) uses the correlation between multiple signals and the sparsity of the radar signal to improve the performance of estimation and obtain better performance than the traditional radar [17, 18]. A natural extension of CS is the multiple measurement vectors (MMVs) where the sparse signal has the same sparse structure and is measured by the same measurement matrix [19]. When the underlying signals have the common support set, it will help to reduce the successful recovery condition. In recent years, the MMVs have been used for off-the-grid line spectrum denoising and estimation [20], heart rate monitoring [21], classification [22], etc. At present, our research group is working on modeling and simulation of the GLONASS satellite signal. In the project, we found that it is a heavy burden for storage and transmission of the satellite signal at high sampling rate, and the every millisecond signal has the same sparse feature. So, our team studies to apply the theory of compressive sensing and MMV for acquisition. In this paper, a new GLONASS signal acquisition method based on CS and MMV is proposed. We design the sparse representation dictionary according to the same pseudorandom ranging code and the different satellite carrier frequencies. An improved MMV acquisition algorithm is used to acquire the GLONASS signal. Experiment results show that the new method can acquire the GLONASS signal efficiently.

The rest of this paper is organized as follows. In Section 2, the CS and MMV are introduced briefly. Section 3 introduces the GLONASS signal and the serial acquisition method. Section 4 describes the new GLONASS signal sparse dictionary and gives the improved acquisition method based on CS and MMV. Section 5 gives the simulation results of the new method. Finally, the paper is concluded in Section 6.

2. Compressive Sensing and Multiple Measurement Vectors

According to the Nyquist sampling theory, the sampling rate of the signal must be more than twice the maximum frequency of the signal which will get a large number of redundant data. The CS theory is proposed by Donoho et al. [8, 9], which points out that the sparse signal can be sensed by a lower sampling rate, which is much lower than that of the Nyquist theory. The sparse signal can be recovered accurately from the measurement data of CS. The CS consists of three parts: sparse representation of the signal, measurement matrix, and signal reconstruction [23].

In CS, the sparse signal $\mathbf{x}\in R^{N\times 1}$ can be measured by the measurement matrix $\mathrm{\Phi }\in R^{M\times N}M<N$, which can be expressed as$$\begin{array}{}\text{(1)}& \mathbf{y}=\mathbf{\Phi }\mathbf{x}+\mathbf{n}=\mathbf{\Phi }\mathbf{\Psi }\mathbf{s}+\mathbf{n}=\mathbf{\Theta }\mathbf{s}+\mathbf{n},\end{array}$$where $\mathbf{y}\in R^{M\times 1}$ is the CS measurement data, $\mathrm{\Psi }$ is the sparse dictionary, and $\mathbf{n}\in R^{M\times 1}$ is the interference noise. The sparse signal can be reconstructed from the measurement data through some reconstruction algorithms. The sparse signal reconstruction problem can be described as follows:$$\begin{array}{c}\text{(2)}& {\mathbf{x}}_0=\arg \min x_0\text{s.t.}\hspace{1em}\mathbf{y}=\mathbf{\Phi }\mathbf{x}+\mathbf{n},\end{array}$$where ${\cdot }_0$ means zero-norm which counts the number of nonzero elements. We can get the best sparse solution by solving the optimization argument. The zero-norm provides a simple notion of sparsity, but is not a right notion of norm in mathematics because it does not satisfy the norm definition by simple verification.

The sparse signal reconstruction is an NP-hard problem and has strict condition. Naturally, some methods are proposed to promote the recovery effect, for example, MMV where a single matrix $\mathrm{\Phi }\in R^{M\times N}$ is used to obtain the measurements of multiple sparse signals $\mathbf{X}={\mathbf{x}}_1,{\mathbf{x}}_2,\dots ,{\mathbf{x}}_L\in R^{N\times L}$ with the same support set. The measurements of MMV can be expressed as ${\mathbf{y}}_1=\mathrm{\Phi }{\mathbf{x}}_1,{\mathbf{y}}_2=\mathrm{\Phi }{\mathbf{x}}_2,\dots ,{\mathbf{y}}_L=\mathrm{\Phi }{\mathbf{x}}_L$. Given $\mathbf{Y}\in R^{M\times L}$ and $\mathrm{\Phi }\in R^{M\times N}$, the sparse signal reconstruction based on MMV is an optimization problem [24]:$$\begin{array}{c}\text{(3)}& \min {\mathbf{X}}_{\text{row}-0}\text{s.t.}\hspace{1em}{\mathbf{Y}-\mathbf{\Phi }\mathbf{X}}_F\le \epsilon ,\end{array}$$where ${\cdot }_{\text{row}-0}$ counts the nonzero row of matrix $\mathbf{X}$ and ${\cdot }_F$ is the Frobenius norm. To solve the optimization problem (3), some SMV recovery algorithms have extended to MMV. Orthogonal matching pursuit for MMV (OMPMMV) [25], simultaneous orthogonal matching pursuit (SOMP) [26], MMV focal underdetermined system solver (MFOCUSS) [27], etc., are proposed. When the sparse signals have a common sparse feature, the MMV can lead to a reconstruction advantage. The same support set provides more information to the optimization, so the reconstruction result based on MMV is better than SMV. In [20], authors proposed a novel fast sparse direction-of-arrival (DOA) estimation algorithm based on the MMV and a smooth 0-norm algorithm for the multiple-input multiple-output radar. For the MMV-based joint smooth function, the DOA estimation can be achieved by using the corresponding gradient-based sparse signal reconstruction. The proposed method can solve the MMV problem and achieve better DOA estimation performance for both white and colored Gaussian noises. In [28], authors proposed a new sparse synthetic aperture radar (SAR) imaging method using the MMV model to reduce the computation cost and enhance the imaging result. The sparse row structure information of MMV is used to improve the imaging quality under sub-Nyquist sampling rate. The experimental results suggest that the proposed method can obtain SAR imaging more effectively than SMV.

3. GLONASS Signal and Acquisition

GLONASS satellite signal consists of navigation message, pseudorandom (PR) ranging code, and carrier [29]. Navigation message contains system time, ephemeris, satellite health, ionosphere delay parameters, etc. The navigation message is transmitted by the satellite with a rate of 50 bps (20 milliseconds per data). The rate becomes 100 bps after Meander coding. In order to improve the anti-interference ability of the system, Modulo-2 addition with the PR ranging code [30] is performed on the navigation message. PR ranging code is a sequence of the maximum length shift register (m sequence) which is sampled at the output of the 7^th stage of the 9^th stage shift register. All the GLONASS satellites utilize the same PR ranging code and are distinguished by the different carrier frequencies. The sequence length is 511, and the bit rate is 511 kilobits per second, so it is repeated every 1 millisecond. The generating polynomial of the 9th stage shift register is$$\begin{array}{}\text{(4)}& GX=1+X^5+X^9.\end{array}$$

After Modulo-2 addition with the PR ranging code, the navigation message is modulated to different frequencies by binary phase shift keying. The GLONASS is a frequency division multiple access (FDMA) system, and satellites are distinguished according to different carrier frequencies. The navigation signals transmitted by the GLONASS satellite have two carrier frequencies, L1 and L2:$$\begin{array}{c}\text{(5)}& L1:f1=1602+k\ast 0.5625\text{\hspace{0.17em}MHz,}L2:f2=1246+k\ast 0.4375\text{\hspace{0.17em}MHz,}\end{array}$$where $k$ is the frequency number of the satellite. The range of $k$ is $-7\sim 6$, which can provide 14 different carrier frequencies. A receiver on Earth cannot receive the signals coming from satellites in opposite points of an orbit plane (antipodal), so the two satellites can transmit navigation radio signals on equal frequencies [31]. That is to say, the 14 frequencies can support the usage of 28 satellites.

Multipath propagation phenomenon is inevitable in the wireless communication system because of the radio signal reflection or refraction [32, 33]. The GLONASS terminal receives the satellite signal with two or more paths including the line-of-sight component. Multipath disturbance is an important error source in the navigation system, which can result in position error because of the biased ranging measurements. In this paper, we give the GLONASS signal model which takes the multipath into account; however, how to mitigate the multipath is out of scope of this paper.

In the receiver, the kth GLONASS intermediate frequency signal on the L1 band can be expressed as (L1 band is discussed in this paper only)$$\begin{array}{}\text{(6)}& {\mathbf{X}}_k\mathbf{t}={\displaystyle \sum _{i=0}^R{a}_i\mathbf{C}t{\mathbf{D}}_k\mathbf{t}cos2\pi f_I+k\times 0.5625+f_d\mathbf{t}+{\theta }_k+\mathbf{n}\mathbf{t}},\end{array}$$where $R$ is the multipath number, $a_i$ is the multipath signal amplitude, $\mathbf{C}\mathbf{t}$ is the GLONASS satellite PR ranging code, and ${\mathbf{D}}_k\mathbf{t}$ is the navigation message. After down converting, $f_I+k\times 0.5625$ is the intermediate frequency (IF) of the kth satellite, $f_d$ is the Doppler frequency shift, ${\theta }_k$ is the carrier phase, and $\mathbf{n}\mathbf{t}$ is the noise interference.

Serial acquisition algorithm is an often-used spread spectrum signal acquisition method for GLONASS or GPS [34, 35]. The method is based on multiplication of the incoming signal and the locally generated reference signal, which is the PR ranging code with phase delay and Doppler frequency shift carrier signals. The PR ranging code has a certain code phase, from 0 to 510 chips. The incoming signal is multiplied by this locally generated PR ranging code. After the multiplication with the PR ranging code, the incoming signal is multiplied by the locally generated carrier signal. Because the phase of the incoming signal is unknown, the incoming signal is necessary to be multiplied with the in-phase (I) and quadrature (Q) signal. The two products are integrated over the period of the PR ranging code, finally squared, and added. The output exceeds the predefined threshold if the PR ranging code delay and Doppler frequency are corresponding to the signal. The receiver concludes that there is the GLONASS satellite in the line of sight. The serial search acquisition method has two different sweeps: a PR ranging code phase sweep over all 511 different code phases and a frequency sweep over all possible carrier frequencies of $\pm 10$ kHz with the searching steps of 500 Hz for the high dynamic receiver. In this case, the total number of inner product operation for one satellite is$$\begin{array}{}\text{(7)}& 511\times 2\frac{10000}{500}+1=511\times 41=20951,\end{array}$$which is a very large number of combinations for the whole navigation system. This exhausting search routine is the main weakness of the acquisition method.

4. GLONASS Signal Acquisition Based on CS and MMV

A new GLONASS signal acquisition method based on CS and MMV has been proposed. A sparse dictionary corresponding to the satellite is designed according to the satellite PR ranging code and intermediate frequency. The satellite signal has been measured by the same random matrix first, which is compressed largely. Then, a MMV reconstruction algorithm is used for the acquisition of the satellite. The new acquisition method is mainly composed of two parts: sparse dictionary and reconstruction algorithm.

4.1. Sparse Dictionary of GLONASS Satellite Signal

The GLONASS signal can be simplified as $\mathbf{C}\mathbf{t}-\tau \cos 2\pi f_I+k\times 0.5625+f_d\mathbf{t}+{\theta }_k$ in navigation data ignoring multipath and noise. The premise of compressive sensing application is sparsity, so the signal needs to be represented sparsely [36]. The signal is nonsparse in common transform basis, for example, discrete cosine transform (DCT), fast Fourier transform (FFT), and discrete wavelet transform (DWT). A sparse dictionary based on the signal feature must be designed. $Ct$ is the PR ranging code which is an orthogonal sequence, and the cosine signal is sparse based on Fourier transform. For the PR ranging code, $\mathbf{C}\mathbf{t}-{\tau }_1\cdot \mathbf{C}\mathbf{t}-\tau$ equals 1 when $\tau ={\tau }_1$. So $\mathbf{C}\mathbf{t}-\tau cos2\pi f_I+k\times 0.5625+f_d\mathbf{t}+{\theta }_k\cdot \mathbf{C}\mathbf{t}-{\tau }_1$ is a cosine signal if $\tau ={\tau }_1$, which is a sparse signal. All the GLONASS satellites use the same PR ranging code, so the sparse dictionary of the kth satellite signal can be expressed as$$\begin{array}{}\text{(8)}& {\mathbf{\Psi }}^k={\mathbf{C}}_{t-\tau }\otimes e^{-j2\pi f_I+k\times 0.5625+\Delta f_d\mathbf{t}+{\theta }_k},\end{array}$$where ${\mathbf{C}}_{t-\tau }$ is the PR ranging code phase delay, $e^{-j2\pi f_I+k\times 0.5625+\mathrm{\Delta }{f}_d\mathbf{t}+{\theta }_k}$ is the frequency with the step of $\mathrm{\Delta }{f}_d$, $f_I+k\times 0.5625$ stands for the kth satellite signal IF, and $\otimes$ is the Kronecker product. The position of the sparse value is corresponding to the PR ranging code phase and Doppler frequency.

The PR ranging code length is 511, so the satellite signal possibly has 511 different code phases. For a high dynamic receiver, the Doppler frequency range is $\pm 10\hspace{0.17em}\text{kHz}$ with the searching step of 500 Hz, that is to say, there are 41 frequencies. The Kronecker product of code phase delay and frequency sweep is $511\times 41=20951$. If the length of the GLONASS signal is $N$, the dictionary dimension is $20951\times N$. According to the kth satellite sparse dictionary, the kth GLONASS signal ${\mathbf{x}}^k$ can be sparsely represented as$$\begin{array}{}\text{(9)}& {\mathbf{x}}^k={\mathbf{\Psi }}^k{\mathbf{s}}^k,\end{array}$$where ${\mathbf{s}}^k$ is a sparse signal if the kth GLONASS satellite is in the field of view.

The histogram of the $k=2$ GLONASS satellite under different transform bases is shown in Figure 1. The receiver intermediate frequency is 5.5 MHz, so the satellite signal frequency is $5.5+2\times 0.5625=6.6250\hspace{0.17em}\text{MHz}$. The signal-to-noise ratio (SNR) is −20 dB, and the noise is additive white Gaussian noise which is added using the MATLAB function “awgn.” The simulation signal has two paths, and multipath signal amplitude is half the line-of-sight signal. PR ranging code phase and Doppler frequency are set randomly. The GLONASS PR ranging code period is 1 ms, so the selected experimental signal size is 1 ms with 40 MHz sampling frequency. In the experiment, the “haar” wavelet is chosen as the analysis function. The sparse representation results are the same based on other wavelet functions. From the histogram, we can find that the signal is nonsparse and cannot be represented sparsely under DCT, FFT, and DWT dictionary. Most of the values are below normalized 0.1 based on the designed sparse dictionary of this paper. The GLONASS signal can be represented sparsely because all the values below 0.1 are considered as noise which can be set to 0.

[figure omitted; refer to PDF]

4.2. GLONASS Signal Acquisition Based on CS and MMV

Sparsity is the essential prerequisite for CS. The GLONASS signal is a sparse signal based on the sparse dictionary, so the CS can be used for compressing and reconstructing the signal. At the satellite, the signal ${\mathbf{x}}^k$ transmitted by the satellite is a clean signal which is not polluted by the noise. But, at the receiver, the incoming signal is ${\mathbf{x}}^k+\mathbf{n}$ which is contaminated by the noise and multipath interference. According to CS theory, the polluted GLONASS signal can be compressed by a random matrix $\mathrm{\Phi }$ which has carried out orthogonalization between the arbitrary column vectors first, and then a compressed signal ${\mathbf{y}}^k$ is got:$$\begin{array}{}\text{(10)}& {\mathbf{y}}^k=\mathbf{\Phi }{\mathbf{x}}^k+\mathbf{n}=\mathbf{\Phi }{\mathbf{\Psi }}^k{\mathbf{s}}^k+\mathbf{\Phi }\mathbf{n}={\mathbf{\Theta }}^k{\mathbf{s}}^k+\mathbf{\Phi }\mathbf{n}.\end{array}$$

Duration of one navigation message is 10 ms after Meander coding, but the period of PR ranging code is 1 ms. That means there are 10 repetitions of the PR ranging code in one navigation message. If the satellite signals are sensed by every millisecond, then MMV can be expressed as a matrix:$$\begin{array}{}\text{(11)}& \mathbf{Y}={\mathbf{y}}_1,{\mathbf{y}}_2,\dots ,{\mathbf{y}}_L=\mathbf{\Phi }{\mathbf{x}}_1+{\mathbf{n}}_1,\mathbf{\Phi }{\mathbf{x}}_2+{\mathbf{n}}_2,\dots ,\mathbf{\Phi }{\mathbf{x}}_L+{\mathbf{n}}_L=\mathbf{\Phi }\mathbf{X}+\mathbf{\Phi }\mathbf{N},\end{array}$$where $\mathbf{X}={\mathbf{x}}_1,{\mathbf{x}}_2,\dots ,{\mathbf{x}}_L$ is the signal matrix and $\mathbf{N}={\mathbf{n}}_1,{\mathbf{n}}_2,\dots ,{\mathbf{n}}_L$ is the noise matrix.

The sparse signal can be obtained from formula (3) according to the MMV reconstruction algorithm. But, the GLONASS signal acquisition is different from the sparse signal reconstruction problem. The purpose of CS signal reconstruction is to reconstruct the sparse signal value and position accurately. The GLONASS signal acquisition is interested in the position of the largest sparse value only. The corresponding PR ranging code phase and Doppler frequency can be obtained from the position. Secondly, the satellite sparse dictionary dimension is large, so some classical reconstruction algorithms which have inverse operation are unfit for GLONASS signal acquisition. In this paper, the greedy algorithm is used for GLONASSS signal acquisition.

The greedy algorithm is a successful sparse signal reconstruction method which carries out exhaustive iteration for reducing the residual error by updating the optimal dictionary atom [37]. At iteration, one atom (one column of the sensing matrix) is chosen to add to the support set once for reducing the residual error maximally. The algorithm terminates when the iteration numbers exceed the given value or the error falls below the given threshold. Many variants are available in the family of the greedy algorithm, which hope to offer improvements either in complexity or/and in the accuracy. The orthogonal matching pursuit (OMP) can get good reconstruction effect, which is more famous than other greedy algorithms [38]. The OMPMMV [25] is a successful algorithm for MMV sparse signal reconstruction. The algorithm needs some improvements for MMV GLONASS signal acquisition [14]. The PR ranging code is an orthogonal sequence which can simplify the updating of residual error, and the error is not suitable as a termination condition because the GLONASS signal has strong noise. The more important reason is that the GLONASS signal acquisition is more interested in the position of the sparse value than the sparse value. Taking these into consideration, an improved MMV greedy acquisition algorithm for GLONASS signal acquisition is proposed.

The new algorithm has some similarities with the greedy algorithm. The inner product of the residual error with the sensing matrix is identical to the greedy algorithm in iteration step 1. But, there are some differences. Firstly, the PR ranging code is an orthogonal sequence, so the maximum inner product value is selected for updating the residual error which requires a least square calculation in the OMP algorithm. Secondly, the residual error is not suitable as the stopping condition of iteration because the GLONASS signal SNR can deteriorate into −20 dB or worse. In the greedy acquisition algorithm, the judgment condition is the total iteration $I$. A specific sparse dictionary is designed for one satellite once, so the sparsity is 1 for a dictionary in theory. To enhance the result, the total number of iterations $I$ is set to $5-10$. Finally, the purpose of acquisition is to estimate the coarse PR ranging code phase and Doppler frequency of the satellite signal but not reconstruct the sparse signal. The final output of the acquisition algorithm is acquiring the satellite or not (Algorithm 1).

Algorithm 1: GLONASS signal acquisition based on CS and MMV.

 

Input: sparse dictionary $\mathrm{\Psi }$, measurement data $\mathbf{Y}=\mathrm{\Phi }\mathbf{X}+\mathrm{\Phi }\mathbf{N}=\mathrm{\Phi }\mathrm{\Psi }\mathbf{S}+\mathrm{\Phi }\mathbf{N}=\mathrm{\Theta }\mathbf{S}+\mathrm{\Phi }\mathbf{N}$, total iteration times $I$, threshold coefficient $\gamma$;

 

Initial: residual error ${\mathbf{R}}^0=\mathbf{Y}$, sparse solution ${\mathbf{S}}^0=\mathbf{0}$, support set ${\mathbf{C}}^0=\varnothing$, and $k=0$;

 

Iteration:

(1)

Perform the inner product operation of residual error and the sensing matrix $\mathrm{\Theta }$ according to ${\mathbf{P}}^k={\mathbf{R}}^{k-1},\mathrm{\Theta }$, where $p^{k}j={{\mathbf{R}}^{k-1}}^{\prime }\cdot {\mathrm{\Theta }}_j/{{\mathrm{\Theta }}_j}_2^2$ is the j^th column of ${\mathbf{P}}^k$;

(2)

Find the maximum inner product value $p_{j_{\text{m}}}^k=\arg \max {{\mathbf{p}}^{k}j}_2$, add the index of the maximum into the support set ${\mathbf{C}}^k={\mathbf{C}}^{k-1}\cup j_{\text{m}}$, and add the maximum inner product value into the corresponding position of sparse signal ${\mathbf{S}}^{k}j={\mathbf{S}}^{k-1}j+p_{j_m}^k$;

(3)

Update the residual error ${\mathbf{R}}^k=\mathbf{Y}-{\mathrm{\Theta }}_{C^k}{\mathbf{S}}^k$;

(4)

$k=k+1$, if $k=I$, stop the iteration and turn to step 5. Otherwise, turn to step 1;

(5)

Judgment: if ${S_m}^2\ge \gamma {S_{\text{ms}}}^2$, $S_m=\arg \max s$ and $S_{ms}$ is the second maximum sparse value, acquisition is complete and turn to output 1. Otherwise, turn to output 2;

 

Output1: acquire the satellite successfully, and output the corresponding position index of $S_m$ from the dictionary;

 

Output2: there is no satellite in the line of sight.

5. Numerical Simulation Experiments

The implementation of the new acquisition algorithm is shown in Figure 2. The incoming GLONASS signal is polluted by noise. The GLONASS signal is compressed by the matrix $\mathrm{\Phi }\in {\mathbf{R}}^{M\times N}$ which is a normalized orthogonal random matrix. The MMV is obtained by rearranging the compressed signal. In the receiver, the satellite dictionary is generated for acquisition. The PR ranging code module generates the spreading spectrum code for all satellites. The local oscillation module generates the carrier. There is a 90° phase-shifted version because the phase of the GLONASS signal is unknown [39]. The different GLONASS satellites have different intermediate frequencies. The dictionary module needs to adjust the intermediate frequency of the local oscillator according to the satellite number. Simulation and analysis of the new method with MATLAB is given in the following sections.

[figure omitted; refer to PDF]

5.1. MMV Acquisition at Different Noise and Compressive Ratio

Noise and compressive ratio are the main reasons which affect the acquisition effect of MMV. In this experiment, the influences of noise and compressive ratio at different MMV dimensions are analyzed. For the convenience of discussion, we define the compressive ratio (CR) as$$\begin{array}{}\text{(12)}& \alpha =\frac{M}{N},\end{array}$$where $N$ and $M$ are the length of the GLONASS signal and the compressed data, respectively. The compression ratio intuitively describes the ratio of the compressed signal to the original signal.

The third GLONASS satellite (which is selected at random) on the L1 band is selected for numerical simulations. The IF is 5.5 MHz after down-conversion, so the IF of the third satellite is $5.5+3\times 0.5625=7.1875$ MHz. The sampling frequency is set to 40 MHz. The time to transmit a complete PR ranging code needs 1 ms, so the length of the 1 ms GLONASS signal is 40000. The incoming signal has two paths, and the amplitude of the multipath signal is set to half the line-of-sight component. To reduce the simulation burden without loss of generality, we assume that the statistical model for the delay and Doppler frequency is uniformly distributed. The PR ranging code delay range is 0–255 codes; and the Doppler frequency range is $f_I\pm 5$ kHz. In order to improve the acquisition efficiency, the acquisition dictionary of the PR ranging code phase and frequency are set to half chip and 500 Hz, respectively. The Kronecker product of code phase and frequency is $256\times 2\times 21=10752$, which is the abscissa point. The noise is additive white Gaussian noise (AWGN) and added by the MATLAB function “awgn.” The SNR is set to −15 dB, −20 dB, and −25 dB, respectively, and the CR is set to 0.6, 0.4, and 0.2. The combinations of SNR and CR have 9 cases at the same MMV dimension. Iteration time $I$ is set to 5.

The aim of this experiment is to analyze the influence of noise and compression ratio at different MMV signal dimensions L = 1, 5, and 10. The MMV acquisition degenerates into an SMV problem when $L=1$. To save the page, the MMV acquisition results at −20 dB and −25 dB are shown in Figure 3. The results are better at −15 dB and CR is 0.6, which are shown on the author’s blog. The two red stems are the right position of the GLONASS line-of-sight component and multipath. From the figure, we can find that the new algorithm can capture the GLONASS signal successfully at −20 dB and −25 dB under different MMV dimensions. The MMV provides more relevant row sparse information, and the experimental results are better when $L=10$. At −25 dB, the new algorithm can still acquire the satellite signal except the multipath. These simulations show that the GLONASS signal acquisition based on CS and MMV is feasible, and the CR is 0.4 or 0.2 with the threshold coefficient $\gamma =2$ suitable for acquisition.

[figures omitted; refer to PDF]

5.2. Acquisition Probability Analysis

At the MMV model, GLONASS signal acquisition based on CS is mainly affected by noise, compression ratio, and MMV signal dimension. This experiment analyzes the effect of these three factors on the acquisition performance. The $k=-1$ GLONASS satellite (which is selected at random) on the L1 band is selected for numerical simulations. The center frequency is 5.5 MHz after down-conversion, so the IF of the $k=-1$ satellite is $5.5-1\times 0.5625=4.9375$ MHz. The sampling frequency is set to 30 MHz. The amplitude of the multipath signal is set to half the direct signal, and the PR ranging phase and Doppler frequency are uniformly distributed. The range of noise is from −40 dB to −10 dB with different MMV signal dimensions. The acquisition experiment repeats 200 times at every SNR and MMV signal dimension. The CR is set to 0.4 and 0.2, and the threshold coefficient $\gamma =2$.

The acquisition probabilities are shown in Figures 4(a) and 4(b) with CR = 0.4 and CR = 0.2, respectively. The transmission time of a navigation data is 10 ms after Meander coding, and data have 10 cycles of PR ranging codes, so the maximum MMV signal dimension is 10. The experimental vector dimension is set to $L=\mathrm{1,4,7},\hspace{0.17em}\text{and}\hspace{0.17em}10$. From the figures, we can see that the acquisition probabilities are low when the MMV dimension is 1, and the probability increases greatly when the MMV dimension increases to 4. The acquisition probabilities are close to the classical serial acquisition method when the dimension becomes 10. The experiments conclude that the MMV provides more relevant information between the rows and improves the performance of acquisition.

[figures omitted; refer to PDF]

5.3. Acquisition of Real GLONASS Signal

The real environment is very complicated, the terminal receives the signals of multiple satellites at the same time, which may interfere with each other, and the noise is not only additive white Gaussian noise. In this experiment, we select a real GLONASS signal for testing the MMV algorithm, and the signal is collected on July 6, 2017, by the UTREK310 receiver in the Nanjing University of Aeronautics and Astronautics.

The UTREK310 receiver is a GLONASS and GPS dual-channel signal collecting system with its matching software receiver SDRG310. The receiver radio frequency (RF) front end filters and amplifies the signal. Then, the GLONASS signal is saved at the computer after the down-converter and the analog-to-digital converter. The IF of the collected GLONASS signal is 4.5 MHz, and the sampling frequency is 20 MHz. All the satellites in the line of sight are shown in Figure 5, which is arranged from large to small according to the intensity of the serial acquisition correlation value. That is to say, the $k=-4$ satellite signal intensity is the weakest. The satellites’ constellation and acquisition results are shown in Figures 5(a) and 5(b).

[figures omitted; refer to PDF]

In this experiment, the 10 ms GLONASS signal is used for simulation, and GPS signals are removed to reduce acquisition interference. The $\pm 5$ kHz searching range of Doppler frequency is enough because the receiver is static. The PR ranging code phase is 0–510 codes. The searching step is 500 Hz and half code, respectively, so the combination of code phase and frequency sweep is $511\times 2\times 21=21462$. According to the acquisition results of experiments 1 and 2, it is appropriate to set the CR to 0.4 for high compressive ratio. All the six satellites in the line of sight can be acquired successfully. Only the acquisition results of the $k=-4$ satellite with $L=\mathrm{1,5},\hspace{0.17em}\text{and}\hspace{0.17em}10$ are shown in Figures 6(a), 6(b), and 6(c) because the satellite signal is the weakest, and the acquisition results of other five satellites are better. In the MMV acquisition algorithm, the judgment threshold $\gamma$ is set to 2 for the six satellites, but this value is not suitable for the weakest $k=-4$ satellites when the MMV signal dimension $L=1$ because the second maximum normalized value is greater than 0.5.

[figures omitted; refer to PDF]

For the receiver, acquisition is a blind searching process. The receiver does not know which satellites are in the line of sight. That is to say, the acquisition algorithm needs to search all the possible satellites. The new algorithm needs to establish all satellites’ sparse dictionary in turn. There are no $-7,-6$, etc., satellites in the recorded signal. Taking the $k=1$ satellite, for example, acquisition results of the recorded signal based on the sparse dictionary of the $k=1$ satellite with $L=\mathrm{1,5},\hspace{0.17em}\text{and}\hspace{0.17em}10$ are shown in Figures 7(a), 7(b), and 7(c), respectively. We can find that these values are all very close to each other. We can conclude that there is no $k=1$ satellite in the line of sight according to the judgment threshold.

[figures omitted; refer to PDF]

6. Conclusions

In this paper, we proposed a new sparse GLONASS signal acquisition method based on CS and MMV. A new sparse dictionary is designed for representing the GLONASS signal, and an improved sparse MMV reconstruction algorithm is used for acquisition. A large number of simulation results show that the new method can effectively acquire simulated or real GLONASS signals at high compression ratio and low SNR circumstances with high MMV column dimension. The new method can greatly reduce the sampling rate and energy loss in signal processing and has important application prospects, such as low altitude aircraft with less noise and interference and position and monitoring of field animals which need to record the GLONASS data for a long time. The acquisition performances of the new algorithm are not ideal at lower SNR circumstances, which may be improved by applying reference [40] methods which are successful in low SNR. Our research team will continue to delve into how to improve the acquisition effect of this method.

Acknowledgments

This research was partly funded by the Special Program of National Major Scientific Instruments Equipments Development of China, grant no. 2013YQ200607, Major Projects of Natural Science Foundation of Universities in Anhui Province, grant no. KJ2019ZD35, and the National Natural Science Foundation of China, grant no. 11573001.

References

[1] Russian Institute of Space Device Engineering, Global Navigation Satellite System GLONASS-Interface Control Document, 2008.

[2] Information and analysis center for positioning, navigation and timing, https://www.glonass-iac.ru/en/

[3] E. D. Kaplan, Understanding GPS: Principles and Application, 2005.

[4] P. K. Enge, "The global positioning system: signals, measurements, and performance," International Journal of Wireless Information Networks, vol. 1 no. 2, pp. 83-105, DOI: 10.1007/bf02106512, 1994.

[5] A. A. Maksutov, D. A. Valter, G. V. Borisenko, K. A. Ovchinnikov, "Real-time simulation of the glonass system signals using SDR," Proceedings of the 2019 IEEE Conference of Russian Young Researchers in Electrical and Electronic Engineering (EIConRus), pp. 26-28, DOI: 10.1109/EIConRus.2019.8657287, .

[6] T. Hobiger, R. Haas, J. Löfgren, "Software-defined radio direct correlation GNSS reflectometry by means of GLONASS," IEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing, vol. 9 no. 10, pp. 4834-4842, DOI: 10.1109/jstars.2016.2529683, 2016.

[7] J. G. Proakis, D. K. Manolakis, Digital Signal Processing: Principles, Algorithms, and Applications, 2006.

[8] D. L. Donoho, "Compressed sensing," IEEE Transactions on Information Theory, vol. 52 no. 4, pp. 1289-1306, DOI: 10.1109/tit.2006.871582, 2006.

[9] E. J. Candès, J. Romberg, T. Tao, "Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information," IEEE Transactions on Information Theory, vol. 52 no. 2, pp. 489-509, DOI: 10.1109/tit.2005.862083, 2006.

[10] Y. Xi, J. Zhao, J. R. Bennett, M. R. Stacy, A. J. Sinusas, G. Wang, "Simultaneous CT-MRI reconstruction for constrained imaging geometries using structural coupling and compressive sensing," IEEE Transactions on Biomedical Engineering, vol. 63 no. 6, pp. 1301-1309, DOI: 10.1109/tbme.2015.2487779, 2016.

[11] M. Nazzal, A. R. Ektí, A. Görçín, H. Arslan, "Exploiting sparsity recovery for compressive spectrum sensing: a machine learning approach," IEEE Access, vol. 7, pp. 126098-126110, DOI: 10.1109/ACCESS.2019.2909976, 2019.

[12] S.-H. Kong, "A deterministic compressed GNSS acquisition technique," IEEE Transactions on Vehicular Technology, vol. 62 no. 2, pp. 511-521, DOI: 10.1109/tvt.2012.2220989, 2013.

[13] X. Li, A. Rueetschi, Y. C. Eldar, A. Scaglione, "GPS signal acquisition via compressive multichannel sampling," Physical Communication, vol. 5 no. 2, pp. 173-184, DOI: 10.1016/j.phycom.2011.07.004, 2012.

[14] G. He, M. Song, X. He, Y. Hu, "GPS signal acquisition based on compressive sensing and modified greedy acquisition algorithm," IEEE Access, vol. 7, pp. 40445-40453, DOI: 10.1109/access.2019.2906682, 2019.

[15] F. Wen, Z. Zhang, K. Wang, G. Sheng, G. Zhang, "Angle estimation and mutual coupling self-calibration for ula-based bistatic mimo radar," Signal Processing, vol. 144, pp. 61-67, DOI: 10.1016/j.sigpro.2017.09.021, 2018.

[16] X. Zhang, L. Xu, L. Xu, D. Xu, "Direction of departure (DOD) and direction of arrival (DOA) estimation in mimo radar with reduced-dimension MUSIC," IEEE Communications Letters, vol. 14 no. 12, pp. 1161-1163, DOI: 10.1109/lcomm.2010.102610.101581, 2010.

[17] F. Wen, J. Shi, "Fast direction finding for bistatic emvs-mimo radar without pairing," Signal Processing, vol. 173,DOI: 10.1016/j.sigpro.2020.107512, 2020.

[18] W. Zheng, X. Zhang, Y. Wang, M. Zhou, Q. Wu, "Extended coprime array configuration generating large-scale antenna co-array in massive mimo system," IEEE Transactions on Vehicular Technology, vol. 68 no. 8, pp. 7841-7853, DOI: 10.1109/tvt.2019.2925528, 2019.

[19] J. W. Choi, B. Shim, "Statistical recovery of simultaneously sparse time-varying signals from multiple measurement vectors," IEEE Transactions on Signal Processing, vol. 63 no. 22, pp. 6136-6148, DOI: 10.1109/tsp.2015.2463259, 2015.

[20] J. Liu, W. Zhou, F. H. Juwono, "Joint smoothed l0-norm DOA estimation algorithm for multiple measurement vectors in mimo radar," Sensors, vol. 17 no. 5,DOI: 10.3390/s17051068, 2017.

[21] Z. Zhang, "Photoplethysmography-based heart rate monitoring in physical activities via joint sparse spectrum reconstruction," IEEE Transactions on Biomedical Engineering, vol. 62 no. 8, pp. 1902-1910, DOI: 10.1109/tbme.2015.2406332, 2015.

[22] Z. Wen, B. Hou, L. Jiao, "Joint sparse recovery with semisupervised music," IEEE Signal Processing Letters, vol. 24 no. 5, pp. 629-633, DOI: 10.1109/lsp.2017.2680603, 2017.

[23] E. Michael, Sparse and Redundant Representations from Theory to Applications in Signal and Image Processing, 2010.

[24] H. Li, L. Wang, X. Zhan, D. K. Jain, "On the fundamental limit of orthogonal matching pursuit for multiple measurement vector," IEEE Access, vol. 7, pp. 48860-48866, DOI: 10.1109/access.2019.2907684, 2019.

[25] J. Chen, X. Huo, "Theoretical results on sparse representations of multiple-measurement vectors," IEEE Transactions on Signal Processing, vol. 54 no. 12, pp. 4634-4643, DOI: 10.1109/tsp.2006.881263, 2006.

[26] J. A. Tropp, A. C. Gilbert, "Signal recovery from random measurements via orthogonal matching pursuit," IEEE Transactions on Information Theory, vol. 53 no. 12, pp. 4655-4666, DOI: 10.1109/tit.2007.909108, 2007.

[27] S. F. Cotter, B. D. Rao, K. Kjersti Engan, K. Kreutz-Delgado, "Sparse solutions to linear inverse problems with multiple measurement vectors," IEEE Transactions on Signal Processing, vol. 53 no. 7, pp. 2477-2488, DOI: 10.1109/tsp.2005.849172, 2005.

[28] Y. Chen, G. Li, Y. Chen, Q. Zhang, "Modified multiple-measurement vector model for SAR imaging," Proceedings of the 2016 IEEE Radar Conference,DOI: 10.1109/RADAR.2016.7485195, .

[29] X. Ben, M. Song, J. Xiong, "Glonass satellite navigation signal simulation and software development of receiving verification," Information Technology and Network security, vol. 37 no. 3, pp. 96-99, 2018.

[30] H. Deng, S. Wang, X. Sun, "Design and implementation of glonass satellite signal simulator," Journal of Guilin University of Electronic Technology, vol. 33 no. 3, pp. 200-204, 2013.

[31] G. He, M. Fang, P. Song, X. He, "Researching of glonass satellite signal acquisition," Radio Communication Technology, vol. 45 no. 6, pp. 11-26, 2019.

[32] R. Morales-Ferre, P. Richter, E. Falletti, A. De La Fuente, E. S. Lohan, "A survey on coping with intentional interference in satellite navigation for manned and unmanned aircraft," IEEE Communications Surveys & Tutorials, vol. 22 no. 1, pp. 249-291, DOI: 10.1109/comst.2019.2949178, 2020.

[33] Y. Hu, M. Z. Song, X. Y. Dang, H. L. Yan, "Interference mitigation for the gps receiver utilizing the cyclic spectral analysis and rr-mswf algorithm," Radioengineering, vol. 26 no. 3, pp. 798-807, DOI: 10.13164/re.2017.0798, 2017.

[34] P. Misra, Global Positioning System: Signals, Measurements, and Performance, 2011.

[35] B. Kai, D. M. Akos, N. Bertelsen, A Software-Defined GPS and Galileo Receiver, 2007.

[36] F. Wen, J. Wang, J. Shi, G. Gui, "Auxiliary vehicle positioning based on robust doa estimation with unknown mutual coupling," IEEE Internet of Things Journal, vol. 7 no. 6, pp. 5521-5532, DOI: 10.1109/jiot.2020.2979771, 2020.

[37] S. G. Mallat, Z. Zhang, "Matching pursuits with time-frequency dictionaries," IEEE Transactions on Signal Processing, vol. 41 no. 12, pp. 3397-3415, DOI: 10.1109/78.258082, 1993.

[38] J. A. Tropp, A. C. Gilbert, M. J. Strauss, "Algorithms for simultaneous sparse approximation part I: greedy pursuit," Signal Processing, vol. 86 no. 3, pp. 572-588, DOI: 10.1016/j.sigpro.2005.05.030, 2006.

[39] A. Albu-Rghaif, I. A. Lami, "DCSR: a dynamic channel and resolution sampling for a compressive sensing receiver to acquire gps signals," Proceedings of the IEEE International Conference on Microwaves, Communications, Antennas and Electronic Systems (COMCAS 2013),DOI: 10.1109/COMCAS.2013.6685295, .

[40] L. Wang, D. Wang, C. Hao, "A multiple-measurement vectors reconstruction method for low SNR scenarios," IEEE Transactions on Circuits and Systems II: Express Briefs, vol. 67 no. 4, pp. 785-789, DOI: 10.1109/tcsii.2019.2922172, 2020.