Multi-Peak Double-Dwell GPS Weak Signal Acquisition Method and VLSI Implementation for Energy-Constrained Applications

Abstract

Power consumption of Global Positioning System (GPS) acquisition is a great challenge for energy-constrained applications. In this work, a metric named acquisition mean computation overhead is proposed to measure the energy cost. A novel multi-peak double-dwell (MP/DD) acquisition method for GPS weak signal is proposed. It adopts multi-peak correlation results as candidates in the first acquisition dwell and selects the largest one as the final acquisition result in the second acquisition dwell. Theoretical analysis and numerical simulation are presented in detail. Meanwhile, the very-large-scale integration (VLSI) implementation of coarse- and fine-grained acquisition engines applied to the proposed method is done. The detection probability and acquisition mean computation overhead are simulated using the Monte-Carlo method, and its mean acquisition power is tested with an actual chip. We fabricated the GPS signal acquisition engine with a 40 nm complementary metal oxide semiconductor (CMOS) process. The simulation results demonstrate that detection probability is promoted from 18% to 67% when signal power is equal to 23 dB/Hz. The acquisition mean computation overhead is reduced greatly by 64%. Measurement results show that the energy consumption of this design is only 21.5% of the conventional double-dwell/maximum (DD/MAX) method.

1. Introduction

Global Positioning System (GPS) signal deteriorates greatly in urban environments, and its signal power often degrades down to −144 dBm, resulting in difficult acquisition. With the advent of wearable applications and the Internet of Things (IoT), the energy consumption of GPS receivers is becoming increasingly important. Currently, the power consumption of commercialized GPS products is high—up to 20–30 mW in continually position mode [1]. Thus, they are not suitable for energy-sensitive applications, such as smart watches and sharing bikes. In a real GPS receiver, the acquisition engine consumes over 70% energy due to its complex computation and repeated acquisition in urban areas.

Until now, researchers have studied several methods of GPS signal acquisition. These acquisition methods mainly focus on the reduction of acquisition time, thus reducing The Time to First Fix (TTFF), or increase the sensitivity while ignoring the energy consumption [2]. Research on GPS acquisition mainly addresses three aspects, which are correlation, integration, and searching strategy. For correlation, the fast Fourier transform (FFT)-based parallel code acquisition method has been the most popular algorithm in recent years due to its fast searching compared with serial code acquisition [3,4,5].

In a weak signal environment, 1 ms correlation results are not reliable because of noise interference. In this case, methods such as coherent integration, non-coherent integration, and differentially coherent integration should be applied to further improve the signal-to-noise ratio (SNR) [6]. Coherent integration is an efficient method to improve sensitivity, but the time is limited because of the bit transition. Non-coherent integration is less sensitive, but infers extra squaring loss. A multiple of one data bit interval is chosen as predetection integration time to estimate the most likely data bit combination and reverse the data signs subsequently for very weak GPS signals [7,8]. A combined coherent and differentially coherent acquisition scheme avoids complex FFT post-processing of correlation results and acquires −147 dBm GPS signal in 200 ms without any assistance data [9]. Rigorous mathematical analysis and Monte-Carlo simulation shows that differentially combined integration can decrease approximately 3 dB loss of non-coherent integration for weak GPS signals [10]. Since received weak signals may suffer self-interference from other strong satellite signals, a partitioned subspace projection method is proposed to mitigate the self-interference [11]. A new space-borne GPS receiver called Navigator employs special signal processing algorithms in radiation-hardened hardware that enable fast acquisition and high sensitivity for high-altitude satellites [12].

The maximum/threshold crossing (MAX/TC) method is the most commonly used acquisition searching strategy [13]. It is a hybrid criterion where the uncertainty region is divided into N_s sectors with M cells each. The cell is selected according to the MAX criterion inside a sector. In detail, in a sector, select cell C^(j) if u^(j) ≥ u⁽ⁱ⁾, for i = 1, …, M; choose cell C^(j) if u^(j) ≥ ξ, else go to next sector. Note that for M = N_c, N_s = 1, ξ = −∞, the MAX/TC criterion reduces to the MAX criterion, while for M = N_c, Ns = N_c, it reduces to the TC criterion. The usefulness of dealing with the MAX/TC criterion lies in the fact that the sector size M is a significant parameter to be optimized in order to achieve minimum acquisition time for a serial architecture, or reasonable complexity for a parallel architecture [14]. A proper selection of the probability of a false alarm using constant false alarm rate (CFAR) criteria can obtain a lesser mean acquisition time than fixed threshold method or MAX method without threshold [15]. A threshold function approach was proposed to simplify the CFAR criteria by a modeling procedure and an approximation procedure [16]. In a word, MAX/TC has complexity in threshold setting and high acquisition false alarm probability in weak signal scenarios.

Recently, the double-dwell/maximum (DD/MAX) acquisition method has been proposed to solve the above problem. The double-dwell scheme uses no threshold in detecting weak GPS signals, and achieves improved performance in terms of detection probability and false alarm probability compared with the conventional MAX/TC criteria. Nevertheless, its low detection probability in weak signal environment leads to a rapid increase of acquisition energy cost [17].

For energy-constrained applications, energy will be an important issue. A novel acquisition method is proposed to reduce energy consumption for IoT applications. The main contributions are listed as follows.

• An acquisition energy metric is proposed first to characterize the measure acquisition mean computation overhead (AMCO). Previous research focuses on the acquisition performance, not the energy consumption.
• A novel multi-peak double-dwell (MP/DD) acquisition method for GPS weak signals. Previous searching strategies (e.g., MAX/TC and DD/MAX) regard the correlation peak as the estimated signal, which is valid for strong signals. However, they ignore the fact that there is a high possibility of the signal appearing in the sub-peaks for weak signals. The MP/DD method not only detects the peak, but also some sub-peaks.
• A hybrid very-large-scale integration (VLSI) architecture is proposed, including coarse-grained acquisition in the first dwell and fine-grained acquisition in the second dwell. A test chip with MP/DD method is fabricated in 40 nm CMOS technology.

The rest of this paper is organized as follows. Section 2 introduces related GPS acquisition works. Section 3 introduces the proposed MP/DD GPS weak signal acquisition method. Section 4 discusses the simulation results and measurement results, and Section 5 concludes this paper.

2. Materials and Methods

2.1. Acquisition Energy Metric

The acquisition energy cost refers to the amount of energy consumed by the GPS receiver when a particular satellite signal is captured, and is closely related to GPS acquisition computation overhead. Therefore, this paper proposes a metric ${\overline{C}}_{acq}$ to measure acquisition mean computation overhead (AMCO) as shown in Equation (1), where ${\overline{N}}_{iter}$ represents the average number of iterations required by the first successful acquisition, and it is only determined by the detection probability $P_D$. The computation overhead of a single acquisition $\overline{c}$ depends on the particular integration algorithm and acquisition strategy. Thus, the acquisition energy optimization is a balance of detection probability and computation overhead.

$${\overline{C}}_{acq}=\overline{c} \times {\overline{N}}_{iter}=\overline{c} \times {\displaystyle \sum }_{k=1}^{\infty } k{P}_D{\left(1-P_D\right)}^{k-1}=\frac{\overline{c}}{P_D}$$

(1)

GPS civil signal L1 C/A is a Code Division Multiple Access (CDMA) system where signals are modulated by Binary Phase-Shift Keying (BPSK). GPS signal acquisition is the detection, and the estimation of code phase and frequency shift is essential. According to the acquisition strategy, correlation results are first generated with parameters in searching space, after the estimated code phase τ and Doppler frequency f_d are given by the decision algorithm. This DD/MAX method divides the whole searching space into η subsets. It generates test variables twice in each subset so that two peaks are obtained. If these two peaks occur in the same code phase, it deems the phase as the final acquisition result. Otherwise, the next subset will continue to be searched until all subsets are completed. Therefore, its acquisition single computation overhead includes two possibilities. One is that acquisition is declared in the kth subset with the possibility (P_D + P_F)/η after kN/η searching cells. Another is that acquisition is never declared with the possibility 1 − P_D − P_F after searching all N cells. The AMCO of DD/MAX can be derived as

$${\overline{C}}_{DD/MAX}=\frac{1}{P_D}[\frac{P_D+P_F}{\eta }{{\displaystyle \Sigma }}_{k=1}^{\eta } (\frac{2kN}{\eta }{T}_{\mathrm{int}}{C}_{cell})+\left(1-P_D-P_F\right)\times 2N{T}_{\mathrm{int}}{C}_{cell}],$$

(2)

where $P_D$ is the detection probability of DD/MAX, $P_F$ is the false alarm probability of DD/MAX, N is the correlation result number of the searching space, $T_{\mathrm{int}}$ is integration time for acquisition, and $C_{cell}$ is the computation overhead of a correlation per unit integration time for one cell.

2.2. Proposed MP/DD Method

Double stages are included in the proposed multi-peak double-dwell (MP/DD) acquisition method. In the first stage, multiple peaks of test variables are selected as candidates of the signal test variable; in the second stage, the only signal test variable is singled out from these candidates whose SNR is enhanced by the longer time integration. The acquisition method is described in detail as follows.

Step 1: The object searching space S(τ,f) is divided to discrete space S_ij(τ_i,f_j) including N searching cells, and test variables ξ_ij(τ_i,f_j) are generated by the specified parameters τ_i and f_j in each searching cell. These test variables are integrated over a period T_int which costs NT_intC_cell computation overhead.

Step 2: The first dwell search is carried on ξ_ij(τ_i,f_j), and the largest M test variables ξ⁽¹⁾_ij(τ_i,f_j) are picked up, whose searching cell S⁽¹⁾_ij(τ_i,f_j) will be used in the next dwell. The computation overhead of selecting the largest M ξ⁽¹⁾_ij(τ_i,f_j) among all test variables is C_s, and it is small enough to be ignored compared to C_cell. M is a number whose value can be configured;

Step 3: The second dwell is carried only on the sets S⁽¹⁾_ij(τ_i,f_j), and double integration time 2T_int is used to generate test variables ξ⁽²⁾_ij(τ_i,f_j) with 2T_intMC_cell computation overhead.

Step 4: The largest ξ⁽²⁾_ij(τ_i,f_j) is singled out, and its parameters are recognized as the final estimated τ and f_d. The computation overhead of selecting the largest ξ⁽²⁾_ij(τ_i,f_j) among M test variables is small.

The state diagram of the proposed method is demonstrated in Figure 1. Its detection probability $P_D$ and false alarm probability $P_F$ are obtained as follows:

$$P_D=P_D^1{P}_D^2\hspace{1em}{P}_F=\left(1-P_D^1\right)+P_D^1\left(1-P_D^2\right),$$

(3)

where $P_D^1$ is the probability that the M test variables include the signal test variable in the first dwell, and $P_D^2$ is the probability that detects the signal test variable in the second dwell.

For simplicity, the signal test variable is regarded as existing in one of the searching cells randomly, and the noise test variable in spare ones. Hypothesis testing is used where the alternative hypothesis (H₁) means that the signal test variable exists and the null hypothesis (H₀) means the noise test variable exists. The distribution of the signal test variable is in connection with the energy detector pattern. Without loss of generality, coherent and non-coherent integration algorithms are adopted here. Thus, signal test variable and noise test variable are regarded as non-central chi-square distribution $f_{H_1}$ and central chi-square distribution $f_{H_0}$ [18].

If M is large enough to include the signal test variable in the whole M selected test variables, the minimum test variable $V_{th}$ can be expressed as:

$$M={{\displaystyle \int }}_{V_{th}}^{\infty }{f}_{H_1}\left(x\right)dx+\left(N-1\right){{\displaystyle \int }}_{V_{th}}^{\infty }{f}_{H_0}\left(x\right)dx.$$

(4)

Thus, the equivalent threshold $V_{th}$(M,N,σ) which picks up the largest M test variables including the signal test variable from all N variables can be deduced as:

$$V_{th}\left(M,N,\sigma \right)={[F_{H_1}\left(x\right)+\left(N-1\right)F_{H_0}\left(x\right)]}^{-1}\left(F_{H_1}(\infty )+\left(N-1\right)F_{H_0}(\infty )-M\right),$$

(5)

where F_H0 and F_H1 are the probability distribution functions of signal and noise test variables, respectively, which are determined by SNR. The SNRs of the signal test variables are related to signal power level and integration time as:

$$\sigma =\frac{C}{N_0}-10{\log }_{10}\left(B_{pd}\right)+10{\log }_{10}\left(F_s\times T_{int}\right)-L_{sq}-L_d,$$

(6)

where $B_{pd}$ is the noise band, $F_s$ is the sample frequency, $T_{int}$ is the coherent integration time, and $L_{sq}$ and $L_d$ are square and digital process loss.

Statistically, the first dwell detection probability $P_D^1$ and the first dwell false detection probability $P_F^1$ can be expressed in Equation (7). Moreover, the second dwell detection probability $P_D^2$ and the second dwell false detection probability $P_F^2$ are represented in Equation (8). The difference between the first and the second dwell is that σ’ is 3 dB higher than σ.

$$P_D^1\left(M,N,\sigma \right)={{\displaystyle \int }}_{V_{th}\left(M,N,\sigma \right)}^{\infty }{f}_{H_1}\left(x,\sigma \right)dx\hspace{1em}\hspace{1em}\hspace{1em}{P}_F^1\left(M,N,\sigma \right)={{\displaystyle \int }}_0^{V_{th}\left(M,N,\sigma \right)}{f}_{H_0}\left(x,\sigma \right)dx$$

(7)

$$P_D^2\left(1,M,{\sigma }^{’}\right)={{\displaystyle \int }}_{V_{th}\left(1,M,{\sigma }^{‘}\right)}^{\infty }{f}_{H_1}\left(x,{\sigma }^{’}\right)dx\hspace{1em}\hspace{1em}\hspace{1em}{P}_F^2\left(1,M,{\sigma }^{‘}\right)={{\displaystyle \int }}_0^{V_{th}\left(1,M,{\sigma }^{’}\right)}{f}_{H_0}\left(x,{\sigma }^{’}\right)dx$$

(8)

Since explicit formulation descriptions of detection probability and false detection probability are difficult to integrate with Equations (7) and (8), numeral calculation and Monte-Carlo simulation of the presented acquisition algorithm are carried out.

Threshold is not required in the second dwell if the satellite is determined to exist, so the false alarm probability of MP/DD is the complementary set of detection probability, as Equation (9) shows. Based on the above analysis, the AMCO of MP/DD consisting of three parts is derived in Equation (10).

$$P_F=1-P_D$$

(9)

$${\overline{C}}_{MP/DD}=\frac{1}{P_D}\left(T_{int}N{C}_{cell}+2T_{int}M{C}_{cell}+C_S\right)$$

(10)

3. Results

3.1. Algorithm Verification

To verify the performance of the proposed method, theory analysis and numerical simulation were carried out. In the remainder of this paper, the searching space included 1/2 of code CHIP step and 16 frequency shift bins, so the overall number of the whole searching space N was 32,736. Since the data rate of GPS L1 C/A signal is 50 bps, the coherent integration was limited to 10 ms due to bit transition. In the first dwell, 10 ms coherent integration and five times non-coherent integration were combined, which means a half-bit integration method was used in coherent integration [19]. In the second dwell, coherent integration time was still 10 ms and non-coherent time was extended from 5 to 10 times. In Equation (6), $B_{pd}$ is 4.092 MHz, $F_s$ is 16.368 MHz, and $L_{sq}$ and $L_d$ are both regarded as 2 dB.

Based on Equations (3)–(10), the theoretical performance of the proposed method is derived and shown in Figure 2. Apparently, the detection probability increased with the ascending number of M. The detection probability was above 90% when M equaled 160 with signal CN0 (carrier-to-noise density) equal to 24 dB/Hz, while it did not increase notably when M was over 160. Thus, it provides a reasonable balance between detection probability and acquisition single computation overhead when M = 160.

For further study, the proposed acquisition method was established with MATLAB and Monte-Carlo simulations were carried out whose data were collected from the Spirent GPS Constellation Simulator. In the Monte-Carlo simulation, the acquisition simulation parameters were the same as the theoretical analysis. For comparison of performance between different acquisition methods, the DD/MAX method was simulated in the same simulation environment and all N feasible cells were divided into 16 sections to obtain a low false alarm probability.

Figure 3a shows the detection probability of MP/DD and DD/MAX methods by Monte-Carlo simulation. When detecting weak signals (CN0 equal to 23 dB/Hz), our method obviously had a detection probability of about 67%, being higher than that of DD/MAX which was only 18%. Besides, the false alarm probability of MP/DD was also acceptable because it was the complementary set of its high detection probability. Overall, these simulation results are consistent with the above theoretical analysis.

Not only did MP/DD have remarkably high sensitivity (verified above), but it had lower AMCO compared to DD/MAX. According to Equations (3) and (10), the AMCO of MP/DD and DD/MAX were derived and normalized. As shown in Figure 3, the AMCO of MP/DD was only 26% of DD/MAX when CN0 was 23 dB/Hz. When CN0 exceeded 23 dB/Hz, the AMCO of MP/DD and DD/MAX were significantly decreased, where the difference between them was small enough to be ignored.

3.2. VLSI Implementation and Test

In order to improve the energy efficiency of the proposed GPS signal acquisition scheme, two types of acquisition engines were implemented with the proposed MP/DD acquisition method. One is a coarse-grained acquisition engine (CGAE) used for narrowing the parameter scope in the first dwell. The other type is a fine-grained acquisition engine (FGAE) applied to final signal parameter estimation in the second dwell.

The CGAE generates correlation results in the first dwell, which then preselects possible parameters according to the multi-peak method. Considering the initial parameter scope continuity, a matched filter is applied to CGAE and the circuit architecture is illustrated in Figure 4. The signal data is processed with matched filter, Doppler mixing, and then accumulated in static random access memory (SRAM); finally, the multi-peak selection module gives the narrowed parameter scope.

The fine-grained acquisition engine is used to generate correlation results and estimates the final parameter from the preselected parameter scope, according to the maximum value strategy. Considering the discreteness of the preselected parameters, the fine-grained acquisition engine adopts many acquisition channels, and each channel includes an independently-configurable correlator and mixer, and its circuit architecture is shown in Figure 5.

The acquisition process is carried out with the software scheduling. The coarse-grained acquisition engine gives the preselected parameter, and the fine-grained uses the preselected parameter to estimate the final parameter; the coarse-grained and fine-grained engines use the pipeline alternately to work, and thus the hardware achieves a high utilization rate.

Moreover, the GPS signal acquisition engine was integrated in a System-on-Chip (SoC) to verify its performance. Its die photograph using a 40 nm complementary metal oxide semiconductor (CMOS) process and test environment are shown in Figure 6a,b. We verified the performance of the MP/DD algorithm and architecture. The test chip contained two operation modes—one is the conventional DD/MAX algorithm, and the other is the MP/DD algorithm proposed in this paper. As shown in Figure 7, the average acquisition energy of GPS acquisition was measured under two modes, and the channel number of FGAE was 160 in VLSI implementation.

4. Discussions

The test results were consistent with the simulation, and the energy consumption in the proposed MP/DD acquisition method was only 21.5% of the conventional DD/MAX when the carrier to noise ratio was 23 dB/Hz, which shows its great advantages for energy-constrained applications.

From Figure 3b and Figure 7, for GPS weak signals, the decrease ratio in the mean acquisition computation overhead and mean acquisition energy of MP/DD compared with DD/MAX was close: 60% vs. 64% for CN0 of 22 dB/Hz and 74% vs. 78.5% for CN0 of 23 dB/Hz. Since AMCO takes correlation into consideration while the VLSI architecture includes units such as matched filter, Doppler mixing, and SRAMs, the ratio has little difference. For signals whose CN0 are higher than 23 dB/Hz, the detection probabilities of MP/DD and DD/MAX are both high, and therefore mean acquisition computation overhead and mean acquisition energy of these two methods are almost equal to each other.

5. Conclusions

High-sensitivity and low-power GPS receiver could be an important building-block for the next-generation Internet-of-Things applications. Previous work focused on high-sensitivity GPS receivers. With the advent of the IoT, the energy consumption of GPS is an increasing concern. Most of the power is consumed in GPS acquisition engine. So, low-power acquisition engines are the main focus of GPS receivers in IoT devices.

In general, our work is comprehensive from theory to practice in GPS acquisition. Its novelty mainly exists in ultra-low power acquisition for weak signals. Firstly, the AMCO metric of acquisition energy is proposed. Secondly, in order to reduce the acquisition energy in weak GPS signal scenarios, a novel multi-peak double-dwell acquisition method is proposed. A theoretical model was established to verify its rationality, and Monte-Carlo simulations show its high detection probability and low mean computation overhead with weak GPS signals. Finally, the VLSI architecture of coarse- and fine-grained acquisition engines suitable for the MP/DD method is proposed. The test chip was fabricated with 40 nm CMOS process, where actual energy measurements illustrate that the proposed metric AMCO can approximately characterize the acquisition energy of GPS receiver, and the acquisition engine using MP/DD method can reduce power consumption greatly for energy-constrained applications.

In the future, there are more innovations for low-power GPS acquisition engines; for example, new acquisition methods using machine learning and analog computing for matched filter and IoT applications.