Whole-Region Hybrid Search Algorithm for DSSS Signal Acquisition

Abstract

The conventional hybrid search algorithm for direct sequence spread spectrum (DSSS) signal acquisition terminates once a decision variable exceeds the detection threshold. Therefore, a spurious “hit” declared before the search reaches the cell where the target signal is located avoids any possibility of a correct detection. This behavior increases the probability of false detection, especially in abnormal scenarios, such as when in the presence of interfering signals. To improve the probability of correct detection under a constant false-alarm rate criterion, this paper proposes an advanced hybrid acquisition scheme, whose search area is extended to the whole Doppler frequency and code phase delay uncertainty region. To reduce the mean acquisition time (MAT) increment resulting from this increased search area, both parameters of a Tong detector and the detection threshold are adaptively customized, according to a signal-to-noise ratio estimate obtained during the search operation. In addition, analytic expressions for the detection probability and false-alarm probability are derived. The most prominent advantage of the proposed method is that it can reduce the false detection probability noticeably, with little increase in resource utilization, and an acceptable MAT. The validity of this algorithm is verified, both theoretically and through simulation. The proposed algorithm is particularly suitable for DSSS signal acquisition when in the presence of either multiple access interference or continuous wave interference.

1 Introduction

Direct sequence spread spectrum (DSSS) systems are widely used in the fields of telemetry, track & command (TT&C), communications, navigation, etc., because of their strong anti-jamming capabilities and superior interception avoidance performance. The regular operation of DSSS systems must be ensured by the acquisition and tracking modules, for code and carrier synchronization [1].

In the acquisition phase, coarse estimates of Doppler frequency and code phase delay are obtained from the received signal. Acquisition is performed by searching among a two-dimensional uncertainty region, whose dimensions are the Doppler frequency and the code phase delay. The two-dimensional uncertainty region is divided into a two-dimensional grid of smaller search cells, considering the size of the uncertainty region and the expected search precision. Generally, the grid search strategy is divided into three classes: full parallel search, full serial search, and hybrid search. The full parallel search, which searches the whole uncertainty region (all the grid cells) simultaneously, is capable of fast acquisition, but at the expense of hardware complexity. The full serial search, which searches the uncertainty region on a cell by cell basis, is the simplest strategy, but implies an increased mean acquisition time (MAT). The hybrid search (HS), which searches the uncertainty region block by block, provides a tradeoff between these two extremes, and is hence widely used [2, 3]. The work presented in this paper is therefore based on the HS strategy.

An inherent drawback of conventional HS is that the process is terminated once a decision variable exceeds the detection threshold, independently of whether the cell where the target signal is effectively located has been searched or not [4]. For simplicity, the cell where the target signal is located is denoted by $H_1$ cell, and the other cells are denoted by $H_0$ cells. When using the HS strategy, a declaration that the signal is synchronized ($H_1$ decision) can be made incorrectly, if a $H_0$ cell with lower search order than the $H_1$ cell produces a decision variable exceeding the detection threshold; this results in false detection (we distinguish here false detection—the incorrect alignment between the local replica and the received signal—from false-alarm—an incorrect decision on whether the signal is present or not). In the event of false detection, the tracking loop is initiated with the erroneous initial state obtained from acquisition, which leads to abnormal tracking loop operation; as a consequence, acquisition is inevitably restarted. The amount of time consumed on abnormal tracking and acquisition restarts (i.e., the penalty time), is considerably larger than the time spent on a single-time acquisition process [5]. Therefore, false detections are disruptive to DSSS system operation; the probability of their occurrence within the acquisition process needs to be reduced to the greatest extent. Denote the decision variable corresponding to $H_0$ ($H_1$) cells as $\varLambda _{H_0}$ ($\varLambda _{H_1}$). The probability density function (PDF) of $\varLambda _{H_0}$ will unfortunately be affected by interferences [6], severe weather, ionospheric non-ideal characteristics, and energy leaking from an adjacent $H_1$ cell (especially when the signal power is abnormally large). Consequently, the probability that $\varLambda _{H_0}$ results in a $H_1$ decision (false detection probability) may increase considerably. The application of the conventional HS algorithm is therefore limited, in some abnormal situations.

Several methods have been proposed to deal with the false detection problem. The simplest category is based on verification strategies, and includes methods such as coincidence detectors with multiple threshold values [7], and the Tong detector [8]. These methods perform well in abnormal environments with accidental and random disturbances (e.g., bursty ionosphere interference or noisy signals), whereas they exhibit poor detection performance when in the presence of persistent and deterministic interference, or extraordinarily strong signal conditions. Some methods are mainly focused on interference mitigation, including multiple access interference (MAI) recovering and cancellation [9], adaptive filtering for continuous wave interference (CWI) suppression [10], and antenna array based interference mitigation [11]. However, the complexity of these methods increases highly in intricate scenarios aggregating various types of interference, and a priori knowledge about the interference (such as the interference form and the number of interferers) is required. Antenna array based methods pose extra requirements on hardware facilities and power dissipation, which are not justifiable in some practical applications. These methods are certainly necessary when the jamming-to-signal ratio (JSR) is extremely high; however, considering the above-mentioned limitations of interference mitigation methods, other algorithms are preferred in some moderate JSR situations.

In this paper, HS is extended to a search strategy that covers the whole code-phase-delay/Doppler-frequency uncertainty region. Instead of interrupting the search once the decision variable of a given cell has exceeded the detection threshold, the decision variable is calculated for all the cells, and a maximum selection among the cells that exceeded the detection threshold is then performed. The proposed algorithm performs better than HS, as long as $\varLambda _{H_1}$ is larger than all the $\varLambda _{H_0}$s. This algorithm, where the whole uncertainty region is covered with the hybrid acquisition algorithm and the maximum is then selected, is hereafter abbreviated as the whole-region hybrid search- maximum selected (WRHS-MS) acquisition algorithm. When the target signal is present, this algorithm can significantly decrease the probability of false detection, relatively to the conventional HS algorithm. Both a theoretical analysis and simulation results—including detection and false-alarm probabilities—for the proposed algorithm are provided in this paper.

However, the WRHS-MS acquisition algorithm has a disadvantage in that it requires a higher MAT than the HS acquisition algorithm for a single-time acquisition process, owing to the higher number of searched cells. To reduce MAT to a certain extent, we have referred to the parameter optimization method proposed in [12], which optimizes the parameters of the Tong detector and the detection threshold, according to a practical signal-to-noise ratio (SNR) given a priori. In this paper, the SNR estimate is obtained during the WRHS-MS search process, and then works as a reference to adjust the parameters in the following search process. The dwell-time spent on searching the remaining cells after parameter adjustment is thus reduced, and acquisition is consequently accelerated.

The remainder of this paper is organized as follows. In Sect. 2, the conventional HS strategy is described, and its difficulties concerning false detections in the presence of the target signal are analyzed. Section 3 proposes the WRHS-MS acquisition algorithm, and analyzes its performance in detail. To save MAT, the WRHS-MS algorithm is improved by adaptive parameter adjustment in Sect. 4. In Sect. 5, a simulation analysis is presented. The conclusions are drawn in Sect. 6.

2 Conventional HS Acquisition Algorithm

2.1 Conventional HS Strategy Model

In conventional HS, the two-dimensional grid of the acquisition uncertainty region is generally searched by rows or by columns, in parallel (the cells in each row or column are therefore considered as a block). The decision variables of a block are obtained in parallel, and a maximum selection among these decision variables follows. The maximum decision variables are used for detection. If the detection threshold is exceeded on a certain block, a $H_1$ decision is made, and the acquisition process is terminated. Otherwise, the algorithm moves to the next block; this is repeated until the end of the two-dimensional grid. In brief, one may say that in the HS scheme a parallel search is used within a block, whereas a serial search is used among blocks.

Fig. 1

Two-dimensional cell grid of the acquisition uncertainty region

Taking the two-dimensional grid shown in Fig. 1 as an example, assume that the search proceeds by rows, from top to bottom. N denotes the number of columns (and is therefore also the number of parallel searches). M denotes the number of rows, and determines the size of the serial search (i.e., the amount of search blocks). The detection and false-alarm probabilities are expressed as [4]

$$\begin{aligned} P_{D\_HS} &= \frac{1}{M}\frac{1-\left( 1-P_{Fa\_blk}\right) ^M}{P_{Fa\_blk}}P_{D\_blk}, \end{aligned}$$

(1)

$$\begin{aligned} P_{FA\_HS} &= 1-\left( 1-P_{Fa\_blk}\right) ^M, \end{aligned}$$

(2)

where $P_{D\_blk}$ and $P_{Fa\_blk}$ respectively denote the detection and false-alarm probabilities for an individual block. To achieve good detection performance with single-dwell detection under a constant false alarm rate (CFAR) criterion, large SNR ($\eta$) values are required. Therefore, in practice, Tong detection (with its variable dwell-time detection) is extensively used [13]. Considering a Tong detector, the detection and false-alarm probabilities of the individual blocks become [14]

$$\begin{aligned} P_{D\_blk}= \frac{\left( 1/P_{d\_blk}-1\right) ^B-1}{\left( 1/P_{d\_blk}-1\right) ^A-1}, \end{aligned}$$

(3)

$$\begin{aligned} P_{Fa\_blk}= \frac{\left( 1/P_{fa\_blk}-1\right) ^B-1}{\left( 1/P_{fa\_blk}-1\right) ^A-1}, \end{aligned}$$

(4)

where B and A denote the initial and upper limit values of the counter, respectively. Probabilities $P_{d\_blk}$ and $P_{fa\_blk}$ represent the detection and false-alarm probabilities of individual blocks with single-dwell detection, and are given by

$$\begin{aligned} P_{d\_blk}= \int _{V_t}^{+\infty }f(z|H_1)\left[ 1-P_{fa\_cel}(z)\right] ^{N-1}dz, \end{aligned}$$

(5)

$$\begin{aligned} P_{fa\_blk}= 1-\left[ 1-P_{fa\_cel}(V_t)\right] ^N, \end{aligned}$$

(6)

where $V_t$ is the detection threshold, $P_{fa\_cel}(V_t)$ is the false-alarm probability for individual cells, and $f(z|H_1)$ is the PDF of $\varLambda _{H_1}$. The corresponding expressions are given in [15]. Herein it is assumed (as is done in some other papers), that there is merely one $H_1$ cell in the uncertainty region, with the other $MN-1$ cells containing only noise.

2.2 Analysis of the Conventional HS Strategy Limitations

The detection threshold is preset in the light of the CFAR criterion; therefore, the false detection probability is determined by the PDF of $\varLambda _{H_0}$. Normally, the PDF of $\varLambda _{H_0}$ is Rayleigh (solid curve in Fig. 2); the dashed line in this figure denotes the PDF of $\varLambda _{H_1}$ ($\eta =12\,{{\mathrm {dB}}}$ and a Rician PDF are considered here). In abnormal scenarios, the expectation of $\varLambda _{H_0}$ deviates from zero, (as exemplified by the dotted curve in Fig. 2), and the probability of $\varLambda _{H_0}$ exceeding the detection threshold increases considerably.

Fig. 2

Probability density functions for the decision variable amplitude

In practice, the PDF deviation exemplified above may be caused by unexpected phenomena such as interferences [6], severe weather, ionospheric non-ideal characteristics, and extraordinarily strong signals. To describe these effects, normalized noise-free decision variables are analyzed. The corresponding results are shown in Fig. 3 for the case of interfering conditions, and in Fig. 4 for unmixed target signal conditions (which is the extreme condition of a strong target signal). Figure 3a, b correspond to MAI and CWI scenarios, respectively. These pictures show both the whole two-dimensional normalized correlations in the code-phase-delay/Doppler-frequency uncertainty region, and their projections upon each dimension. For visualization, only a fraction of the code phase delay values (from 0 to 50 chips) are shown. The settings used here are the same ones used in the simulation section below. The normalized decision variables are obtained normalizing the correlations by the maximum value of the auto-correlation and JSR (only in Fig. 3). As shown, the correlations in $H_0$ cells are not absolutely zero, owing to interference and signal power leakage; this increases the probability of false detection.

Fig. 3

Normalized decision variable in MAI and CWI scenarios. a MAI scenario. b CWI scenario

Fig. 4

Normalized auto-correlation of Doppler frequency and code phase delay for an unmixed target signal

It can therefore be concluded that, when using conventional HS strategy, some $H_1$ decisions will erroneously be made in $H_0$ cells being searched before the $H_1$ cell, even if $\varLambda _{H_1}$ is larger than those $\varLambda _{H_0}$s. Taking the false detected cell as the initial condition for the tracking loop operation leads to a waste of time, which is much longer than a single acquisition time. The ratio between the time wasted by abnormal tracking and the normal single acquisition time (i.e., the penalty factor) is valued from 100 to $10^4$ in [5]. Preventing false detections is therefore a primary goal in the acquisition phase. In this respect, the WRHS-MS acquisition algorithm introduced in the following section is necessary and practicable.

3 WRHS-MS Acquisition Algorithm

To avoid unexpected terminations before reaching the $H_1$ cell, and thus reduce the resulting false detection probability, a search strategy covering the whole uncertainty region is needed. The proposed WRHS-MS acquisition algorithm does precisely that.

The number of decision variables obtained for each block during Tong detection, denoted as k, is at least $A{-}B$. The maximum element of these variables (denoted by $\varLambda _{max}$) is selected. If at least one block triggers the Tong detector, a secondary maximum selection is performed among the set of $\varLambda _{max}$ values corresponding to the blocks with detections. Estimates of the Doppler frequency and code phase delay are then derived from the block with the maximum $\varLambda _{max}$. Otherwise, an acquisition failure is announced.

The false-alarm probability of WRHS-MS acquisition with Tong detection is, therefore, given by:

$$\begin{aligned} P_{FA\_WRHS-MS}=1-\left[ 1-P_{Fa\_blk}(V_t)\right] ^M, \end{aligned}$$

(7)

which is the same expression of conventional HS.

To derive the final detection probability, let us summarize the situations leading to a correct detection:

• 1. The $H_1$ block triggers the Tong detector, whereas the $H_0$ blocks do not. The corresponding probability is

  $$\begin{aligned} P_{D}(0)=P_{D\_blk}\left( 1-P_{Fa\_blk}\right) ^{M-1}. \end{aligned}$$

  (8)

• 2. The $H_1$ block triggers the Tong detector, and a maximum selection result, denoted as $(\varLambda _{H_1})_{max}$, is obtained. Additionallly, the maximum value of the set $\{(\varLambda _{H_0})_{max}(j)|j=1,2,\ldots ,i\}$ is smaller than $(\varLambda _{H_1})_{max}$, where i $(1\le i<M)$ is the amount of $H_0$ blocks with detections and $\{(\varLambda _{H_0})_{max}(j)|j=1,2,\ldots ,i\}$ is the set constituted by the maximum selection results from each of these blocks. In this case, the probability is

  $$\begin{aligned} P_{D}(i)& = \left\{ \begin{array}{l} P_{D\_blk}\left[ C_{M-1}^iP_{Fa\_blk}^i(1-P_{Fa\_blk})^{M-i-1}\right] \times \\ \int _{0}^{+\infty }f_{max\_Nk}(z|H_1)\left[ 1-\int _{z}^{+\infty }f_{max\_Nk}(u|H_0)du\right] ^idz \end{array} \right\} ,\nonumber \\ i= & 1,2,\ldots ,M-1, \end{aligned}$$

  (9)

  where $f_{max\_Nk}(z|H_1)$ and $f_{max\_Nk}(u|H_0)$ are the posterior PDFs of $(\varLambda _{H_1})_{max}$ and $(\varLambda _{H_0})_{max}$ conditioned to their corresponding blocks having triggered the Tong detector. The expressions are

  $$\begin{aligned} f_{max\_Nk}(z|H_1)&= C_k^1\left( f_{max\_N}(z|H_1)\big /P_{d\_blk}\right) \left[ \int _{V_t}^{z}\left( f_{max\_N}(u|H_1)\big /P_{d\_blk}\right) du\right] ^{k-1}\nonumber \\&= kf(z|H_1)\left( 1-P_{fa\_cel}(z)\right) ^{N-1}\left[ P_{d\_blk}-P_{d\_blk}(z)\right] ^{k-1}\bigg /P_{d\_blk}^k \nonumber \\&= \frac{k}{2\sigma _u^2}{\mathrm{exp}}\left( -\frac{z+\lambda }{2\sigma _u^2}\right) I_0\left( \frac{\sqrt{z\lambda }}{\sigma _u^2}\right) \left( 1-P_{fa\_cel}(z)\right) ^{N-1} \nonumber \\&\quad \times \,\left[ P_{d\_blk}-P_{d\_blk}(z)\right] ^{k-1}\bigg /P_{d\_blk}^k, \end{aligned}$$

  (10)
  $$\begin{aligned} f_{max\_Nk}(z|H_0)&= C_k^1\left( f_{max\_N}(z|H_0)\big /P_{fa\_blk}\right) \left[ \int _{V_t}^{z}\left( f_{max\_N}(u|H_0)\big /P_{fa\_blk}\right) du\right] ^{k-1}\nonumber \\&= \frac{kC_N^1}{P_{fa\_blk}}f(z|H_0)\left[ \int _{0}^{z}f(u|H_0)du\right] ^{N-1}\nonumber \\&\quad \times \,\left[ \int _{V_t}^{z}\frac{C_N^1}{P_{fa\_blk}}f(u|H_0) \left[ \int _{0}^{u}f(v|H_0)dv\right] ^{N-1}du\right] ^{k-1}\nonumber \\&= \frac{kN}{2\sigma _u^2}e^{-\frac{z}{2\sigma _u^2}} \left( 1-e^{-\frac{z}{2\sigma _u^2}}\right) ^{N-1} \left[ P_{fa\_blk}-\left( 1-\left( 1-e^{-\frac{z}{2\sigma _u^2}} \right) ^N\right) \right] ^{k-1}\Bigg /P_{fa\_blk}^k, \end{aligned}$$

  (11)

In these equations, $\sigma _u$ is the standard deviation of the decision variable. Functions $f_{max\_N}(z|H_1)\big /P_{d\_blk}$ and $f_{max\_N}(z|H_0)\big /P_{fa\_blk}$ are the posterior PDFs of the maximum decision variables in the H1 and H0 blocks, respectively, conditioned to the corresponding decision variable exceeding the detection threshold. In addition, note that $P_{d\_blk}(z)$ is different from $P_{d\_blk}$, given that its lower limit of integration is z, not $V_t$. The same difference also exists between $P_{fa\_blk}(z)$ and $P_{fa\_blk}$.

Therefore, the detection probability in WRHS-MS acquisition using Tong detection is

$$\begin{aligned} P_{D\_WRHS-MS}&= \sum _{i=0}^{M-1}P_{D}(i)\nonumber \\&= \sum _{i=0}^{M-1} \left\{ \begin{array}{l}P_{D\_blk}\left[ C_{M-1}^iP_{Fa\_blk}^i(1-P_{Fa\_blk})^{M-i-1}\right] \times \\ \int _{V_t}^{+\infty }f_{max\_Nk}(z|H_1)\left[ 1-\int _{z}^{+\infty }f_{max\_Nk}(u|H_0)du\right] ^idz\\ \end{array} \right\} . \end{aligned}$$

(12)

The correctness of the formulas for $P_{FA\_WRHS-MS}$ and $P_{D\_WRHS-MS}$, and the performance improvement of the proposed WRHS-MS algorithm will be demonstrated in Sect. 5 by simulation.

The proposed algorithm is, however, more time-consuming on a single acquisition cycle than the conventional HS algorithm, owing to the additional search area. Therefore, some additional steps will be taken to reduce the time-consumption of WRHS-MS. To do this, an adaptive parameter adjustment algorithm is proposed, and will be discussed in the next section.

4 Adaptive Parameter Adjustment Algorithm Based on WRHS-MS

In general, both the Tong detector parameters and the detection threshold are designed considering the SNR lower bound. Nevertheless, in practice, the SNR is not always at its lower bound. Therefore, the fixed parameter configuration of conventional HS is not the optimum option for scenarios with values of SNR above the lower bound, where it leads to an unnecessary waste of time.

To solve this problem, a parameter optimization method is proposed in [12], which adjusts the detection parameters according to the particular SNR, estimated by assistant modules. This method can decrease the MAT, but the acquisition unit relies on (and is limited by) the performance of those external modules. A self-adaptive parameter adjustment acquisition algorithm may therefore be preferred.

In this section, such an adaptive parameter adjustment algorithm is proposed. The three key points involved in this adaptive algorithm are discussed next: parameter optimization of the Tong detector, SNR estimation, and parameter adjustment.

4.1 Parameter Optimization of the Tong Detector

The parameter optimization of multiple-dwell detectors aims at minimizing the mean dwell-times in the $H_0$ blocks, $n_{H_0}$, with constraints on the detection and false-alarm probabilities [16]. Given that most of the acquisition time is spent on evaluating $H_0$ blocks, and the time cost of evaluating the $H_1$ block is relatively small, this method was simplified in [12] to

$$\begin{aligned} \begin{array}{ll} {\mathrm{min}} & n_{H_0}\\ {\mathrm{s.t.}} & P_{D\_blk}=P_{D\_blk}^*\\ & P_{Fa\_blk}=P_{Fa\_blk}^*, \end{array} \end{aligned}$$

(13)

where ${\mathrm{min}}$ denotes the minimization operator, and $P_{D\_blk}^*$ and $P_{FA\_blk}^*$ are the desired detection probability and false-alarm probability with Tong detection, respectively.

The expression of $n_{H_0}$ is [14]

$$\begin{aligned} n_{H_0}=\frac{B}{1-2P_{fa\_blk}}-\frac{AP_{Fa\_blk}}{1-2P_{fa\_blk}}. \end{aligned}$$

(14)

Generally, B is configured to be either 1 or 2; however, $B=1$ is more widely used. In any case, B can be considered to be a fixed value, and $n_{H_0}$ is therefore a function of A and $V_t$ (through $P_{fa\_blk}$). Considering that, for a given $\eta$, $P_{D\_blk}$ and $P_{Fa\_blk}$ are merely functions of A and $V_t$, (13) can be rewritten as

$$\begin{aligned} \begin{array}{ll} {\mathrm{min}} & \quad n_{H_0}(A,V_t)\\ {\mathrm{s.t.}} & \quad P_{D\_blk}(A,V_t)=P_{D\_blk}^*\\ & \quad P_{Fa\_blk}(A,V_t)=P_{Fa\_blk}^*. \end{array} \end{aligned}$$

(15)

Therefore, optimizing the Tong detector parameters becomes a problem of finding the values of A and $V_t$ leading to the minimum $n_{H_0}$ under a certain $\eta$, with constraints on the detection and false-alarm probabilities.

4.2 SNR Estimation

As mentioned above, the value of $\eta$ is needed for parameter adjustment. Fortunately, SNR estimates can be easily obtained during WRHS-MS operation, once the acquisition is successful. In WRHS-MS, N variables corresponding to the N cells of the same block are obtained simultaneously, within a single dwell-time; the set of these variables is denoted by ${\varvec{\Lambda }}=\left\{ \varLambda _i|i=1,2,\ldots ,N\right\}$. The peak-to-average ratio (PAR) defined in [17] can therefore be calculated for each block. As shown in [18], the PAR expected value in the $H_1$ block can be written as

$$\begin{aligned} {\mathrm{E}}\{PAR\}&= {\mathrm{E}}\left\{ \frac{\parallel {\varvec{\Lambda }}\parallel _{\infty }}{\frac{1}{N} \parallel {\varvec{\Lambda }}\parallel _1 - \parallel {\varvec{\Lambda }}\parallel _{\infty } }\right\} \nonumber \\& = \frac{A_s^2/2+\sigma _u^2}{\sigma _u^2}\nonumber \\& = 10^{\eta /10}+1, \end{aligned}$$

(16)

where ${\mathrm{E}}\{{\cdot }\}$ denotes the expectation operator, $\parallel {\cdot }\parallel _{\infty }$ and $\parallel {\cdot }\parallel _1$ denote the infinity- and 1-norm, respectively, $A_s$ is the target signal amplitude, and $\sigma _u^2$ is the noise variance.

The value of $\eta$ can be derived from the PAR expected value, as follows:

$$\begin{aligned} \eta =10{\mathrm{log}}_{10}\left( {\mathrm{E}}\{PAR\}-1\right) . \end{aligned}$$

(17)

In the Tong detection procedure at each block, more than $k_0=A-B$ dwell-times are involved; this means that more than $k_0$ samples of the PAR can be obtained. Therefore, in practice, estimates of $\eta$ derived from the mean value of the PAR samples are used, instead of statistical expectations. The estimate of $\eta$, denoted as ${\hat{\eta }}$, can thus be expressed as

$$\begin{aligned} {\hat{\eta }}=10{\mathrm{log}}_{10}\left( {\overline{PAR}}-1\right) , \end{aligned}$$

(18)

where ${\overline{PAR}}$ denotes the mean value of the PAR samples.

For simplicity, the transmitted signal power and the characteristics of the transmission channel are assumed to be stationary during the single-time acquisition period. This is a reasonable assumption, considering that the single-time acquisition is generally quite short. Therefore, ${\hat{\eta }}$ is close to the true value of $\eta$, and can be used as a reference for acquisition parameter adjustment.

The performance of the SNR estimation procedure can be evaluated by considering the relative error $\epsilon$ and standard deviation $\sigma$ of the estimate, which are defined as

$$\begin{aligned} \epsilon= {\mathrm{E}}\left\{ \frac{|{\hat{\eta }}-\eta |}{\eta }\right\} , \end{aligned}$$

(19)

$$\begin{aligned} \sigma= \sqrt{{\mathrm{E}}\left\{ |{\hat{\eta }}-\eta |^2\right\} }. \end{aligned}$$

(20)

Such an analysis will be presented (through simulation) in Sect. 5.

4.3 Adaptive Parameter Adjustment

The acquisition parameters—including the detection threshold $V_t$ and the upper limit A of the Tong detector—are adjusted according to the value of ${\hat{\eta }}$ obtained during the search procedure of WRHS-MS, and are used for detection in the subsequent blocks. The adjustment criterion is to shorten MAT, while satisfying the requirements on detection and false-alarm probabilities. A flow chart of the WRHS-MS acquisition algorithm with adaptive parameter adjustment is shown in Fig. 5. SNR estimation and parameter adjustment are the key steps in WRHS-MS acquisition with adaptive parameter adjustment. Considering that analytical solutions to the optimization problem (15) are difficult to obtain, parameter adjustment is performed numerically, using the fact that A is a positive integer. Each possible value of A corresponds to a range of SNR and a specific $V_t$. The values of A and their corresponding SNR bounds and $V_t$ values can be pre-calculated and stored in a lookup table (LUT), to be used in the acquisition process. Using this approach, the obtained SNR estimate is used as an index to the values of A and $V_t$ to be used for parameter adjustment. Given that the updated parameters will be used for detection only in the remaining blocks, the impact of this MAT optimization process is mainly felt on detections in the blocks being searched after the $H_1$ block.

Fig. 5

Flow chart of the WRHS-MS acquisition algorithm with adaptive parameter adjustment

Table 1 Lookup table for parameter adjustment

Let us assume, for example, that the expected detection probability is 0.9, and the false-alarm probability is $10^{-5}$. The block is constituted by cells with various code phase delays and a constant Doppler frequency. The numerical optimization procedure was performed with computer assistance, involving the false-alarm probability expression (7), the detection probability expression (12), the expression of the dwell-times of $H_0$ blocks (14), and the optimization equation (15). The obtained optimized parameters are listed in Table 1. Herein, the detection threshold corresponds to the square-law detector, to avoid square-root extraction.

The parameters in the second and forth columns of Table 1 are stored in ROM (${\mathrm{ROM}}\_\eta$ and ${\mathrm{ROM}}\_V_t$, respectively). The values of A and $V_t$ corresponding to the SNR estimate can now be acquired from the LUT. If the lower bound of the practical SNR is 11.93 dB, parameter A is initialized as 7, and $V_t$ is initialized as 18.8274. The corresponding dwell-time of $H_0$ blocks is 1.19094. Assuming that the SNR estimate obtained during the acquisition process is 13 dB, the optimum values become $A=4$ and $V_t = 23.6866$, as obtained from the LUT. With the optimized parameters, the corresponding dwell-times in the $H_0$ block are reduced to 1.01488. As a result, the dwell-time of the single-time acquisition process is reduced.

It is worth noting that the proposed WRHS-MS algorithm merely changes the search control logic and appends an SNR estimation module and a LUT. Therefore, its resource utilization and implementation complexity will not increase noticeably, when compared with the conventional HS algorithm.

5 Simulation Analysis

5.1 Performance of the WRHS-MS Acquisition Algorithm

A series of Monte Carlo simulations were carried out using the GPS L1 C/A signal specifications, to verify the theoretically predicted performance of the WRHS-MS acquisition algorithm. A parallel code-phase and serial Doppler-frequency grid search was adopted. For simplicity, the Doppler frequency was searched from the minimum to the maximum value. The theoretical performance of the WRHS-MS acquisition algorithm was calculated using (7) and (12); the simulations were run with the same parameters listed in Table 2.

The receiver operating characteristic (ROC) curves obtained both theoretically and by simulation are shown in Fig. 6, for several typical SNR values encountered in the GPS acquisition phase. The Tong detector parameters were set as $B=1$ and $A=3$. As shown in Fig. 6, the simulation results for all $P_D$ ($P_{FA}$) obtained with 5000 ($10^6$) trials agree very well with the theoretical results, confirming the accuracy of the analytical expressions.

Table 2 Simulation parameters

Fig. 6

ROC curves of WRHS-MS acquisition ($B=1, A=3$)

5.2 HS and WRHS-MS Acquisition Algorithm Comparison

The performances of HS and WRHS-MS were analyzed and compared; the obtained results can be seen in Fig. 7. It should be noted that these tests were carried out under a null code-phase and Doppler residuals condition (i.e., with perfect synchronization); perturbation effects will be considered later. As indicated in Fig. 7, in the higher $P_{FA}$ region the detection probability in HS acquisition decreases as the false-alarm probability increases. The reason lies in the fact that in this region false-alarms in $H_0$ blocks tested before the $H_1$ cell will erroneously terminate the search algorithm, leading to a decrease in the detection probability. Considering that the false-alarm probability is generally below $10^{-2}$, the correct detection probabilities of HS and WRHS-MS are almost the same.

Fig. 7

ROC performance comparison of the HS and WRHS-MS algorithms ($B=1, A=3$)

Fig. 8

ROC curves with a constant false alarm rate of $10^{-5}$ ($B=1, A=3$)

When the existence of code-phase and Doppler frequency residuals is considered, signal energy leakage from the $H_0$ cell will exert an effect on adjacent $H_0$ cells. As an example, a Doppler frequency residual of $\hat{f_d}-f_d=1/(2T)$ and a false-alarm probability of $10^{-5}$ were considered, and the resulting detection probabilities versus $\eta$ were analyzed by simulation. The results are illustrated in Fig. 8. This figure shows that, when the signal power is high (e.g., $\eta =25 \,{\mathrm{dB}}$; ${\mathrm{CNR}}=55\,{\mathrm{dBHz}}$), the power leakage to adjacent $H_0$ cells is considerable, and cannot be neglected. In HS, incorrect detections made in one of the adjacent $H_0$ cells appearing (in search order) before $H_1$ lead to a decrease in the correct detection probability.

Additional Monte Carlo simulations were conducted to analyze the distribution patterns of the detected cells by both conventional HS and WRHS-MS. Without loss of generality, we assumed that the $H_1$ cell was located at the null chip-delay and 0.4 kHz Doppler offset. The results shown in Fig. 9 were obtained with 5000 trials. This sample size is the default configuration for all subsequent Monte Carlo simulations. The dot-marked cells in this figure indicate the cells where a $H_1$ decision was made (we will call them detected cells). The star symbol identifies the true $H_1$ cell. Clearly, the only correct detections occur for a dot/star coincidence. Figure 9a shows that, with conventional HS, detections are incorrectly declared in $H_0$ cells appearing before (in search order) the $H_1$ cell, even though $\varLambda _{H_1}$ may be larger than those $\varLambda _{H_0}$s. In contrast, this situation does not occur when using the WRHS-MS acquisition algorithm, as shown in Fig. 9b.

A simulation in the presence of MAI was also performed, to characterize the decrease in false detection probability achieved by the WRHS-MS acquisition scheme (when compared to the conventional HS scheme) in such conditions. The SNR before detection was $\eta = 15\,{\mathrm{dB}}$, and the MAI signal power was 10 dB larger than that of the target signal. The GPS C/A code, PRN 2, was used as the code of the MAI signal. The MAI Doppler frequency was set to −7 kHz, and is thus located before the $H_1$ block, in search order. The obtained results are shown in Fig. 10. The amount of false detections by HS is large, while that of WRHS-MS is greatly decreased. Similarly, a simulation in a CWI scenario was performed; the results are shown in Fig. 11. A single-tone signal was chosen here as the CWI signal; the JSR was 10 dB, and the frequency bias between the CWI and the target signal was considered to be zero.

Fig. 9

Distribution pattern of the cells detected by HS and WRHS-MS with a strong target signal ($\eta =25$ dB). a HS. b WRHS-MS

Fig. 10

Distribution pattern of the cells detected by HS and WRHS-MS with MAI ($\eta =15$ and $JSR=10$ dB). a HS. b WRHS-MS

Fig. 11

Distribution pattern of the cells detected by HS and WRHS-MS with CWI ($\eta =15$ and $JSR=10$ dB). a HS. b WRHS-MS

As is easily seen from these results, the WRHS-MS algorithm had better performance than the conventional HS algorithm, concerning the correct detection probability.

5.3 SNR Estimation Performance

SNR estimates can be obtained by (18) with WRHS-MS, which is important for the adaptive parameter adjustment. In this subsection, the performance of SNR estimation—including the relative error $\epsilon$ and standard deviation $\sigma$—was also evaluated by Monte Carlo simulation. The performance of the adaptive parameter adjustment based on the obtained SNR estimates will be discussed in the following subsection. Given that the estimation performance depends on the number of samples—which is indirectly determined by parameter A—two typical values of A were used: four and seven. The obtained results are illustrated in Fig. 12, and show that the relative error of the SNR estimate is less than 0.06. Additionally, the standard deviation does not exceed 0.8 dB, and decreases with the increase in $\eta$. It can therefore be concluded that the SNR estimate is sufficiently accurate to direct the acquisition parameters adjustment.

Fig. 12

SNR estimation performance analysis. Histograms of the relative error, and error standard deviation

5.4 WRHS-MS Acquisition with Adaptive Parameter Adjustment

To verify the MAT saving performance of WRHS-MS with the adaptive parameter adjustment, a simulation was conducted, with the parameters shown in Table 2. The number of blocks in the serial search (i.e., M) was 25; 24 of them were $H_0$ blocks, and the remaining one was the $H_1$ block, located at the middle of the whole search region, so that an indication of the average MAT saving performance could be obtained. The value of $\eta$ was chosen to be 18 dB (other values of $\eta$ will be considered later). The obtained values for MAT (in units of dwells) are tabulated in Table 3. The theoretical values for MAT were obtained by

$$\begin{aligned} N_{PA}= n_{H_0\_initial}\times M_{before}+n_{H_0\_after}\times M_{after}, \end{aligned}$$

(21)

$$\begin{aligned} N_{Fixed}= n_{H_0\_initial}\times \left( M_{before}+M_{after}\right) , \end{aligned}$$

(22)

where $N_{PA}$ and $N_{Fixed}$ denote the dwell-times of WRHS-MS with parameter adjustment and without parameter adjustment, respectively, and $n_{H_0\_initial}$ and $n_{H_0\_after}$ denote the mean dwell-times of the $H_0$ blocks before and after parameter adjustment, also respectively. For example, for initial parameters $A=7$ and $V_t=18.8274$, the corresponding $n_{H_0\_initial}$ is 1.19094 (see Table 1). Given that the SNR was chosen to be 18 dB, A and $V_t$ after adjustment change to 2 and 43.3265, respectively, and $n_{H_0\_after}$ accordingly changes to 1. The number of blocks to be searched before and after parameter adjustment are denoted as $M_{before}$ and $M_{after}$. Parameter adjustment occurred in the $H_1$ block, which is located in the middle of the frequency space to be searched; therefore, $M_{before}=M_{after}=12$. The theoretical values of MAT can thus be derived from (21) and (22).

As shown in Table 3, the adaptive parameter adjustment algorithm did increase acquisition speed by approximately 10 %.

Table 3 MAT performance comparison ($\eta =18$ dB, $M=25$)

As a follow-up to Sect. 5.3, the MAT performance was also analyzed with values of $\eta$ ranging from 10 to 22 dB. The obtained theoretical and simulation results are shown in Fig. 13. As can be seen, the simulation results deviated from the theoretical ones, whether the parameter adjustment was used or not. This is a consequence of the impact of signal power leakage on the $H_0$ cells. However, both simulation and theoretical results show that the MAT value decreases when the adaptive parameter adjustment is performed. The effectiveness of the parameter adjustment procedure is thus verified.

Fig. 13

MAT (in dwells) as a function of $\eta$, with and without adaptive parameter adjustment ($M=25$)

Moreover, the MAT performance of WRHS-MS with adaptive parameter adjustment becomes even better when the number of blocks increases and/or the $H_1$ cell placement moves to the front-end of the whole search region. Another Monte Carlo simulation was carried out to verify this tendency. Values of 25, 51, 101, 201, and 401 were used for M (the number of blocks to be searched), and various search order locations were used for the $H_1$ block. The values of MAT and normalized MAT (i.e., MAT in dwells divided by M) were obtained using 500 trials; the results are shown in Fig. 14. In this figure, the search order location of the $H_1$ block in the whole uncertainty region varies from 0 to 1, in steps of 0.25. A value of 0 indicates that the $H_1$ block is the first to be searched; a value of 1 indicates that the $H_1$ block is searched last, a value of 0.5 indicates that the $H_1$ block is in the middle of the search sequence, and so on. As can be seen in this figure, the expected relation between M, the search order of the $H_1$ block, and the MAT behavior is verified.

Fig. 14

MAT and normalized MAT versus the search order of the $H_1$ block (0 indicates that the $H_1$ block is searched first, and 1 indicates that the $H_1$ block is searched last)

6 Conclusions

An advanced hybrid search algorithm covering the whole uncertainty region of Doppler frequency and code phase delay was proposed for DSSS signal acquisition. The proposed algorithm added a secondary maximum selection, to improve the probability of correct detection during the acquisition phase, under the CFAR criterion. In abnormal scenarios, the probability of false detection when the target signal is present was greatly reduced, when compared with conventional HS. In addition, to improve the MAT performance of the proposed WRHS-MS acquisition algorithm, an adaptive parameter adjustment method assisted by an SNR estimate was suggested. Analytical expressions for the detection probability and false-alarm probability were derived. The validity of this algorithm was verified, both theoretically and by simulation. The proposed algorithm is especially applicable in scenarios where interference is present; both cases of MAI and CWI interferences were discussed.

In this paper, we considered only communications between cooperative transceivers. As a result of this cooperative relation, the transmitter signal model was well known to the receiver. However, in a broader view of the context, it is possible for both adversaries and allies to coexist simultaneously in a DSSS system. Bayesian game theory [19, 20] would then provide an approach to detect network invaders; this is a topic well suited for future studies.