Open AccessArticle

Application of Genetic Control with Adaptive Scaling Scheme to Signal Acquisition in Global Navigation Satellite System Receiver

Chung-Liang Chang

^1,*

and

Ho-Nien Shou

Department of Biomechatronics Engineering, National Pingtung University of Science and Technology, Pingtung County, Taiwan 91201, ROC

Department of Avionics Communication & Electronics, Air Force Institute of Technology, Kaohsiung County, Taiwan 82047, ROC

Author to whom correspondence should be addressed.

Algorithms 2012, 5(1), 56-75; https://doi.org/10.3390/a5010056

Submission received: 10 December 2011 / Revised: 6 February 2012 / Accepted: 9 February 2012 / Published: 17 February 2012

Download

Browse Figures

Figure 1
Flowchart of GC acquisition procedure with adaptive scaling scheme. "> Figure 2
Performance of signal detection; (a) Probability of detection versus C/No for different acquisition methods (Tc = 1ms, K = 4, PFA = 0.1%); (b) Probability of detection versus false alarm rate (C/No = 38 dB-Hz). "> Figure 3
Evolution curve of signal acquisition for C/A-code; (a) Doppler frequency; (b) code delay. "> Figure 4
Number of initial population versus iteration (C/A-code; C/No = 45 dB-Hz). "> Figure 5
Signal acquisition results of proposed method; (a) C/A-code; (b) BOC-code; (c) P-code. "> Figure 6
Signal search results; (a) Doppler frequency evolution versus iterations (PRN-8); (b) Code delay evolution versus iterations (PRN-8). ">

Versions Notes

Abstract

This paper presents a genetic-based control scheme that not only utilizes evolutionary characteristics to find the signal acquisition parameters, but also employs an adaptive scheme to control the search space and avoid the genetic control converging to local optimal value so as to acquire the desired signal precisely and rapidly. Simulations and experiment results show that the proposed method can improve the precision of signal parameters and take less signal acquisition time than traditional serial search methods for global navigation satellite system (GNSS) signals.

Keywords:

GNSS; synchronization; genetic control

1. Introduction

The positioning and time information provided by the global navigation satellite system (GNSS) has been extensively applied to navigation, military and civil currently, among which the global positioning system (GPS) developed in America from the early 1970’s has been utilized in military applications. Each GPS satellite simultaneously transmits on two L-band frequencies, denoted by L1 and L2, which are 1575.42 and 1227.60 MHz, respectively, and the PRN code modulates with the L-band frequency. The PRN code consists of C/A (coarse acquisition) code on L1 carrier and P code on L1 and L2 carriers. The P-code is encrypted and the resulting code is termed P(Y)-code. The encrypted P(Y)-code is only accessible to authorized users with cryptographic keys. In GNSS receiver design, code and frequency synchronization plays a crucial role, including signal acquisition and signal tracking. The signal acquisition process is a two-dimensional search which relies on acquiring signal parameters (coarse code delay and Doppler frequency) for the use of phase locked loop (PLL) and delay locked loop (DLL) in the tracking loop [1]. Conventional signal search method [2] proceeds with acquisition every 500 Hz based on specific frequency search space (generally ±10 KHz). Meanwhile, this method conducts the search for coarse code delay. After a two-dimensional search (code search and frequency search domain), the “pull in” process initiates in order to estimate more accurate signal parameters. At this stage, coarse signal parameters have been acquired. Then, the estimated parameters are sent to the tracking loop to proceed with signal synchronization. Although the method can effectively acquire signal parameters, it also consumes large amounts of signal search time. In fact, such a GNSS signal acquisition problem has been dealt with by many authors [3,4,5,6,7,8]. These so-called parallel code delay search methods compute the correlation from time domain to frequency domain by utilizing a circular convolution for the fast acquisition of C/A-code signals and have been implemented in software define radio techniques [9]. Recently, a reduced Fast Fourier Transform (FFT)-based limited code correlation and multi-C/A code acquisition method have also been proposed to further improve the acquisition performance [10,11].

Although the above methods can effectively reduce system complexity and acquire signal parameters, these methods still need a hypothesis of different search frequency to test. As a result, the number of frequency bins plays a crucial factor in the signal acquisition process. In [12], the author employs that signal correlation value (search power) and its variation can reduce signal search times on a two-dimension (2D) plane using adaptive logic control method to shorten search time. The result also yields high-precision acquisition parameters. Based on such a concept, the signal search power and its variation serve as the parameter of adaptive adjustment logic in this paper along with genetic control (GC) to search for a signal parameter. In contrast to the signal acquisition of parallel code delay with fixed search space scaling method, the proposed method can shorten search speed and acquire a more accurate code delay and Doppler frequency.

“Evolution” has been extensively applied in the natural sciences and artificial intelligence. This concept originated from J.D. Bagley’s dissertation in 1967 [13]. Afterwards, J.H. Holland was influenced by this concept and proposed related application research to become the precursor of a genetic algorithm [14,15]. This method has been proven to be an effective optimization method and a robust search technique as well [16,17,18,19]. In early research [20], the author has initially verified the feasibility of GC in terms of signal acquisition. Within certain frequency and code search space, several sets of initial signal parameters (code and frequency search value) are generated in local replica. Each set of initial parameters consists of both code delay and Doppler frequency. These signal parameters are coded to serve as the initial individuals (code delay individual and Doppler frequency individual, respectively) in the proposed method. Then, each set of initial individuals (including code delay and Doppler frequency individuals) processed through correlation generates an output value, which serves as the fitness value of that set of initial individuals. Afterwards, the evolutionary process of selection, reproduction, crossover and mutation begins. During the search process, once the fitness value exceeds the initial threshold (set at noise floor level), the desired signal may fall within the vicinity of the corresponding parameters of that set of individual. In the next iteration, the signal search space is narrowed down, the sets of individual are decreased and the threshold is increased. If the fitness value exceeds the maximum threshold, the result of acquisition is successful. Otherwise, the acquisition result may simply contain noise, which calls for a repeated run of evolution process. Although this method speeds up signal search time, the acquired parameter value can be a local optimal solution. Thus, an adaptive scaling scheme is utilized to assure a global solution during the signal acquisition process. Simulations and experiment results reveal that this method not only saves signal search time but also finds more accurate signal acquisition parameters for GPS signal. Comparison results of the published methods are also demonstrated in this paper.

The organization of this paper is as follows. Section 2 describes the signal acquisition process and the possible problems to be encountered. Section 3 depicts how to apply the proposed method to GNSS signal acquisition. Section 4 explains the simulation and experimental procedure of the proposed method and provides the performance evaluation and comparison of published methods with the proposed method. An example is listed to analyze the feasibility of this method. Finally, Section 5 summarizes the key points of this paper.

2. Problem Formulation

2.1. Signal Model

The major purpose of this paper is to employ an evolution method to enhance the performance of GNSS signal acquisition. Under the scenario of ignoring data modulation and interference, the incoming signal is down-converted and then transferred to a digital Intermediate Frequency (IF) signal. The signal at sampling time, t_k, can be described as:

(1)

where P is the power of the direct line-of-sight GNSS signal, f_c is the IF and . The variables f_d, θ and τ denote the Doppler frequency, carrier phase, and code delay, respectively. The noise components w(t_k) are referred to as white Gaussian noise distribution, in which the power spectrum density is N₀/2. The N₀ stands for single sideband power spectrum density of noise. G(·) is the filtered code sequence expressed by C/A-code, P-code or binary offset carrier (BOC) signal [12,21,22].

2.2. Correlation and Detection Process

The baseband signal r(t_k) multiplies a locally generated replica and the result is processed through correlation operation. The resultant output is expressed as:

(2)

where N_k,c is number of samples per coherent accumulation segment, equal to T_c/T_s, where T_s is the sampling period and T_c is code chip rate. u and v are the guessed value of the Doppler frequency and code delay, respectively, in frequency search space [f_c-u_max,lo, f_c+u_max,up] and code search space [v_max,lo, v_max,up]. The values u_max,up and u_max,lo are the upper and lower boundaries of the Doppler frequency, respectively. Similarly, the values v_max,up and v_max,lo are the upper boundary and lower boundary of code delay, respectively. is an unfiltered local replica. The in-phase I_k and quadrature-phase Q_k are squared respectively and then summed altogether. The result is accumulated after K non-coherent integration time. The correlation output is shown as follows:

(3)

where R(·) is the correlation function between the filtered incoming signal and local replica and T_c represents the coherent accumulation interval; the values ε_f,k and ε_θ_,k are the differences between incoming and internally generated Doppler frequency estimate, and that between incoming and internally generated carrier phase estimate, respectively. The value ε_τ_,k represents the estimated code delay error. Each of R(ε_τ_,k) and sinc(ε_f,kT_c) has a maximum amplitude of 1 when ε_τ_,k and ε_f,k take the value of zero. If these values are not zero, the result is a decrease in the amplitude of correlations. The value w_I,k and w_Q,k denote the in-phase and quadrature-phase noise samples with variance σ² = N_k,cN₀/2, respectively. The acquisition process is to find maximum y(u,v) through a search on the two-dimensional (frequency and code domain) grid of trial points, frequency point u and code point v. Two hypothesis tests define the test statistic for signal detection [23,24,25]. When the value y(u,v) exceeds the set threshold v, the signal is considered present (hypothesis H₁). Otherwise, the signal is absent (hypothesis H₀). Under hypothesis H₁, the probability of signal detection P_D is given by

(4)

where ρ = P/2σ², T_y is the test statistic, Pr(·) refers to probability and I₀(·) is the zero-order modified Bessel function of the first kind. The false alarm rate of hypothesis H₀ to H₁ is as shown in Equation 5

(5)

where p₁(·) and p₀(·) are non-central and central chi-square χ² distribution with two degrees of freedom, respectively. Suppose the signal is acquired successfully, the Doppler frequency and code delay can be obtained. The constant threshold v = vσ²ln(P_FA^-1) is often selected in order to achieve a certain probability of false alarm in noise alone by employing the well-known Neyman–Pearson criterion [26].

The above depiction shows that what concerns the designer is to rapidly find the required u and v in a short time so as to have the correlation exceed the set threshold. The following chapters demonstrate that the proposed acquisition method can effectively speed up signal acquisition speed and maintain high estimated parameter precision.

3. Methodology

The acquisition time and the precision of signal parameters lie in the signal search space and each search step size. That is, the guessed number of trial search point determines each time the signal search time. Although a smaller step size increases the precision of estimated signal parameter, it also increases search times, which causes longer acquisition time. Contrariwise, the larger the step size, the more loss of correlation. In the GC process, the search space (including frequency and code space) and the number of acquisition trial points are adjusted to shorten signal search time. The adaptive scaling scheme is to enhance the accuracy of signal parameters. In the following, the whole process of proposed method applied to signal acquisition is illustrated.

3.1. Signal Acquisition with Genetic Control

Step 1. Doppler frequency and code delay encoding

The first step in employing GC to conduct signal acquisition is to convert the locally generated Doppler frequency and code delay to string by way of a binary encoding method [27]. The respective upper bound of Doppler frequency and code delay (u_max,up and v_max,up) is converted to string and the length is expressed as mand n, respectively.

(6)

where S_f and S_g are the Doppler frequency and code delay individuals, respectively. m and n are the maximum bit number of Doppler frequency and code delay individuals. Each bit in the individual is termed as genetic gene.

Step 2. Fitness function determination

After the parameters are encoded, it is necessary to define fitness function to evaluate the quality of each individual. To put it simply, fitness function is the performance index which determines the quality of the individual, retains the superior gene and removes the inferior gene in order to gradually upgrade the overall performance index through evolution by generation. During the signal acquisition process, the signal detection margin serves as fitness function, which is defined by

(7)

where w_k = w_I,k + jw_Q,k is the noise term as depicted in Equation 3. E[·] is the expectation value and Z is the initial population size depicted in step 3. The output y(u_z,v_z) can be obtained through correlation of coherent integration and non-coherent integration. The goal of GC is to find the optimal u_z and v_z parameters in order to maximize Q_z value.

Step 3. Initial population size selection

In Step 1 the search parameters have been encoded as one pair, which are one set of solution in the signal acquisition result. Before utilizing GC, Z sets of parameters must be produced randomly, which represents initial population indicated by

(8)

The evolution of initial populations is adopted to obtain an optimal solution. The number of initial populations depends on the complexity of the search problem. The solution derived from the adoption of initial population may be poor in performance. However, through the evolution process, the subsequent generation outperforms the previous one and finally achieves the optimal value.

Step 4. Selection and reproduction

Similar to the cell division of organisms, the probability of reproduction is based on the rule of survival of the fittest. Selection is the process that prefers individuals with high fitness over low-fitness ones. Thus, the probability of choosing certain individuals is in proportion to its fitness. Suppose the fitness value of i-th individual (u_i,v_i) is Q_i, the probability of reproduction is represented by

(9)

The most prevalent natural selection method of reproduction is a roulette wheel game, the slot division of which is proportional to the fitness value of the individual. The high-fitness ones stand a higher chance of being selected in roulette game.

Step 5. Crossover

Biologically, crossover is the exchange of genes between the chromosomes of two parents. One-point crossover is a method that operates on binary strings. Here, crossover contributes to the information exchange between individuals. The site of point-to-point crossover is random. The individual after crossover consists of parts of genes from each parent. Thus, this new individual is distinct from its previous one. The purpose of crossover is to combine superior genes from different individuals in order to generate new individuals with a higher performance index. However, not every chosen new individual has to go through crossover. Suppose in Equation 6, the exchange point between the i-th Doppler frequency individual S_fⁱ, code delay individual S_gⁱ and the next set S_fⁱ⁺¹ is k, and S_gⁱ⁺¹ is l, correspondingly. The new individuals after crossover are illustrated in Equations 10 and 11:

(10)

(11)

Step 6. Mutation

In biological systems, besides natural selection, an organism goes through mutation to adapt itself to its surroundings in order to survive. The above-depicted procedure merely maintains original individuals and combines superior genes from different individuals with high fitness levels. However, no matter how many times reproduction and crossover take place, the GC does not produce characteristics that are inherently absent in individuals. The function of mutation lies in producing characteristics which are originally absent in high-fitness individuals. The k-th bit of i-th Doppler frequency individual S_fⁱ and code delay individual S_gⁱ is changed from (1→0), shown as follows:

(12)

Although the above method can acquire the optimal value, large population size is required during search process, which often leads to longer computation time. To reduce search time, the population size and search space boundary are automatically adjusted during each iteration process to speed up search time. The following is the process of the proposed method.

3.2. GC with Adaptive Scaling Scheme

In each iteration, fixed and large numbers of initial populations result in a longer signal search time. As a result, the initial detection of the presence of a desired signal (the signal parameters have not been accurately acquired yet) allows us to decrease the number of initial populations in the next search. The (p+1)-th iteration of initial population size is as follows:

(13)

where . When the Q_max^(p) exceeds the noise floor, GC method initiates two procedures. The first procedure is that when Q_max^(p) exceeds the set detection threshold v (depicted in Section 2), it indicates that the desired signal has been acquired and the GC process terminates. The second procedure is when the Q_max^(p) is between the detection threshold and the initial detection threshold. In such case, the adaptive scaling scheme begins to control the number of initial population. The initial detection margin is set at 1.4Q and the definition of Q is the same as that in Equation 7. The only difference is that Q is the fitness value acquired under the scenario of no desired signal. Meanwhile, the scaler also controls and adjusts the search space of Doppler frequency and code delay, which is depicted in the following:

(14)

(15)

where

(16)

(17)

(18)

(19)

where α and β are reduced factors, which mainly control the convergence rate during the signal acquisition process.

The adaptive scaling scheme adjusts the Doppler frequency and code delay boundaries with the increase of acquisition iteration. Thus, this adjustment results in faster convergence and more accurate values of the signal parameter.

3.3. Termination Criterion

The termination criterion of GC normally regulates reproduction generation or detects the difference between generations. If there is no evolution after several generations, the evolution has terminated, which indicates the convergence to optimal value. The Errin Equation 20 approximates zero, which means the GC with adaptive scaling scheme process comes to an end.

(20)

where M is the final iteration number after proposed scheme converge. When the control process finishes, the chosen optimal individual is decoded so as to obtain the Doppler frequency and code delay of the desired signal.

4. Simulation Results and Performance Analysis

4.1. Performance Criterion

This section compares the proposed method with the other published methods in acquiring GNSS signals under the same simulation parameter. Three types of signal are presented for signal acquisition analysis under no consideration for mutual jamming between signals. Suppose signals are down converted to 20 MHz and the sampling frequency is 64 MHz, which fulfills Nyquist’s sampling requirement due to the fact that the P-code has a bandwidth of 20.46 MHz. To verify the proposed method as capable of acquiring GNSS signals, the post-correlation signal-to-noise-ratio (PSNR) is adopted to evaluate the performance of different methods and is calculated as follows:

(21)

where C_p is the highest peak of search power during the correlation process. E[C_n] depicts the mean power of noise term C_n. The proposed method was evaluated by using a developed program under the MATLAB environment.

4.2. Simulation Parameters Setup

Figure 1. Flowchart of GC acquisition procedure with adaptive scaling scheme.

The process of applying GC with an adaptive scaling scheme to signal acquisition is shown in Figure 1. For each parameter, all individuals of the current population are evaluated and a local optimal value is selected. This operation is repeated as many times as required with a diversified population. This diversity is assured by the application of GC operators in binary coding. Once a set of local optimal values is obtained, a global one is selected. Similarly, this process is carried out for all search values to produce the solution per iteration. At this stage, if the acquisition process is not terminated, the maximum search space boundaries (including Doppler frequency and code delay) are adjusted by subjecting them to an evolution cadence (variation of fitness function). This process is repeatedly carried out in this manner as long as it has not entered into offspring stagnation; otherwise, the program is interrupted by a fixed maximum iteration number. The initial population size of C/A-code is set at 1500, P-code, and BOC is set at 1500, 7000, and 5750, respectively, with carrier to noise density ratio (C/No) is 45 dB-Hz, crossover probability 0.85, mutation probability 0.008 and false alarm rate P_FA = 0.01 in control process of proposed scheme. The selection criterion of initial population size is calculated as follows:

(22)

where μis a scale factor with a value between 0.8 and 1. The chip length of C/A-code is 1023. Figure 2a illustrates the detection probability as a function of the C/No. It is shown that the adoption of GC under an adaptive and without an adaptive scaling scheme improves roughly 0.2 dB and 0.8 dB, respectively, in detection performance, in contrast to the adoption of the traditional method. Figure 2b demonstrates a receiver operating characteristics (ROC) curve with C/No = 38 dB-Hz. It shows that the proposed method improves the detection performance with adaptive scaling scheme.

Figure 2. Performance of signal detection; (a) Probability of detection versus C/No for different acquisition methods (T_c = 1ms, K = 4, P_FA = 0.1%); (b) Probability of detection versus false alarm rate (C/No = 38 dB-Hz).

4.3. Simulation Results

A large number of initial populations can speed up signal search time, but is also requires a higher hardware cost. The initial population size, crossover and mutation probability value are set, based on an experience rule to be successfully utilized in the GC process to acquire desired signals. Figure 3 shows the examples for the evolution values of two parameters (Doppler frequency and code delay) for C/A-code. The protruding “○” in Figure 3 is caused by mutation in GC. The two figures ( 3a,b ) show that in utilizing the adaptive scaling scheme, the signal search space will gradually narrow down its space after each iteration to ensure the estimated signal parameter to converge to global optimal value and also reduce iteration times. Contrariwise, a longer acquisition time is required without using the scheme. Figure 4 illustrates the 2D signal search path using the proposed method in application to different signal types, which include C/A-code, P-code and BOC. These diagrams show that the use of GC can effectively reduce search times. On the other hand, Figure 5 analyzes the relation between the number of initial population and search times regarding C/A-code. The result demonstrates that when the number of initial population adopts a roughly 1.5 times code period length of C/A-code (1023 chip), the signal can be accurately acquired within fewer search times under C/No = 45 dB-Hz. When the number of the initial population is below 0.5 times code period length, the proposed method cannot acquire the signal. Such a result is the same with P-code and BOC.

Figure 3. Evolution curve of signal acquisition for C/A-code; (a) Doppler frequency; (b) code delay.

Figure 4. Number of initial population versus iteration (C/A-code; C/No = 45 dB-Hz).

Figure 5. Signal acquisition results of proposed method; (a) C/A-code; (b) BOC-code; (c) P-code.

Table 1. Performance comparison of different acquisition methods (simulated).

**Table 1.** Performance comparison of different acquisition methods (simulated).
Method	Traditional (Serial search) (Fixed search space bound)		Parallel code delay [28] (Fixed code/Doppler search space bound)		Parallel frequency [28] (Fixed code/Doppler search space bound)		Parallel code delay [12] (Adaptive logiccontrol method)		Parallel code delay (GC with adaptive scaling scheme)
Type	C/A-code	P-code/BOC	C/A code	P-code/BOC	C/A-code	P-code/BOC	C/A-code	P-code/BOC	C/A-code	P-code/BOC
Execute time	1505.2	2202.3/1704.3	720.5	1392.3/983,2	901.2	1793.8/1103.6	700.4	1226.1/960.4	650.4	1783.2/850.9
Repetitions (Without Pull-in)	401 (50 Hz step size)	401 (50 Hz step size)	401 (50 Hz step size)	401 (50 Hz step size)	1 ms code chip length	0.5 s/4 ms code chip length	34 (10~1 KHz)	140/78 (10~280 Hz)	39	145/96
Parameter Precision	Poor (Count on number of bins)	Poor (Count on number of bins)	Fair (Count on number of bins)	Fair (Count on number of bins)	Fair	Poor	High	Fair	High	Fair
Complexity	Low	Fair	Fair (Count onFFT size)	High (Count on FFT size)	Fair (Count onFFT size)	High (Count on FFT size)	Fair	High	Fair	High (Count on number of population)

In addition, the system computation time of GC depends on the maximum initial population size Z and iteration number M, which takes 0(ZM). For example, regarding the hardware implementation, the standard GC method takes 2 × 1500 plus 1500 multiplications and 2 × 1500 additions for C/A-code. Therefore, the total required number of operations equals 4500 multiplications and 3000 additions. The adoption of GC with an adaptive scaling scheme takes additional memory for the adaptive adjustment. Table 1 compares the simulated performances of our proposed method with those of the existing methods. The execution time is measured using the tic and toc functions in MATLAB. An average personal computer (PC) is adopted for 20 execution time measurements, with the mean computed as well [28]. The table indicates that the proposed method is superior in time and more precise in parameter than other methods in acquiring three different types of signal. It is noteworthy that because P-code has a longer period time, code length of only that segment (about 2 ms) is utilized for signal acquisition during simulation. Hence, its acquisition time is the longest among different signal types. A tradition (serial search) method is superior in its easy implementation of hardware, but is inferior in parameter precision than other methods. Parallel code delay with fixed code/Doppler search space method [28] is higher in parameter precision rapidity, but is also higher in hardware cost. Although parallel frequency with a fixed code/Doppler search space boundary method is rapid in acquisition time, it is limited by the length of FFT and sampling rate. Thus, this method cannot be efficiently promoted and is seldom applied to realistic circuits. In addition, a parallel code delay with adaptive logic control method is low in hardware implementation complexity, high in estimated parameter precision and parallels the proposed method; the parallel code delay with proposed method is more rapid and efficient in acquisition time. Despite the fact that the proposed method is somewhat higher in hardware implementation complexity (count on number of initial population), it has the potential to be implemented in hardware under the gradual and continuous enhancement of integration circuit design technique.

4.4. Experimental Results

In this section, experimental results are presented to verify the feasibility of the proposed method to reduce acquisition time. Because P-code is currently a military code, the signal cannot be acquired in the actual environment. Thus, the acquisition is conducted only in terms of GPS signal in this experiment, where the IF is 4.092 MHz and sampling frequency is 16.368 Hz.

The data samples from antennae are stored and, afterwards, post-processed for signal acquisition analysis. The results have been obtained for PRN-8, the location of which is at an elevation of 30 degrees at the time of data collection. Table 2 depicts experimental results of GC, utilizing adaptive and non-adaptive scaling schemes, as well as the results of a traditional method. The table demonstrates that the proposed method can achieve better signal parameter precision within a shorter time, as opposed to traditional methods, where one must narrow frequency search step size to enhance parameter precision. This consumes large amounts of signal search time. The table reveals that the average convergence iteration number of the proposed method is below 17 times (except for PRN-8 and PRN-4), which greatly saves a lot of hardware computation time. In addition, the high PSNR can cause the GC process to converge more rapidly in order to speed up the computation time. Note that the iteration numbers of the proposed scheme in the signal acquisition of PRN-8 and PRN-4 are 29 and 30, respectively, which are higher than that of other satellites. The reason is that the estimate parameter converges to a local optimal solution and thus the signal acquisition engine repeats the search process, which increases the iteration number. The same scenario also happens to the GC method without an adaptive scaling scheme in the case of PRN-8 and PRN-4. Figure 6a,b depicts the acquisition parameter search curve of frequency shift and code delay versus iteration number, respectively. Figure 6a shows that the proposed scheme converges to a local optimal solution in the 18th iteration and thus restarts search process. In the 29th iteration the proposed scheme converges to a global optimal solution and successfully acquires a signal parameter. Table 2 compares the performances of the proposed method with a traditional (serial search) method [1] for PRN-8. This table shows that the proposed method can successfully acquire the satellite signal in the sky. Note that search times for PRN-8 and PRN-4 are longer because the signal power of the satellite is weaker.

Table 2. Acquisition results of three methods.

**Table 2.** Acquisition results of three methods.
PRN	Traditional (Serial search) method (frequency search step size: 50 Hz)			GC with adaptive scaling scheme			GC w/o adaptive scaling scheme
PRN		(samples)	PSNR		(samples)	PSNR (Iterations)		(samples)	PSNR (Iterations)
11	2050	12728	21.1701	2014	12731	21.2801(15)	2021	12724	21.2709(17)
8	2250	550	18.7897	2275	553	18.8675(29)	2268	548	18.8602(57)
27	2000	4363	21.2701	2020	4360	21.2784(15)	2010	4365	21.2712(25)
25	1350	9790	21.0104	1370	9787	21.0341(14)	1364	9782	21.0292(25)
28	6600	12400	21.5693	6610	12403	21.5718(14)	6614	12407	21.5782(34)
19	6050	10911	21.5326	6069	10912	21.5332(14)	6049	10911	21.5301(26)
20	2450	15905	19.1023	2441	15907	19.1238(17)	2438	15906	19.1211(25)
17	5350	4016	23.7094	5380	4014	23.7832(11)	5383	4016	23.7621(13)
4	2900	3105	18.7036	2884	3103	18.7432 (30)	2890	3106	18.7419(60)

Figure 6. Signal search results; (a) Doppler frequency evolution versus iterations (PRN-8); (b) Code delay evolution versus iterations (PRN-8).

Table 3 shows that the proposed method estimates the frequency shift of PRN-8 to be 2.275 KHz, which has better precision than the other method. Although the iteration number of proposed scheme in the signal acquisition of PRN-8 is more than that of other satellites, its computation time is much shorter than that of traditional method (shorter by roughly 2.5 times).

Table 3. Performance comparison of experiment results.

**Table 3.** Performance comparison of experiment results.
Signal type	GPS C/A PRN-8
Method	Traditional(Serial search)	GC with adaptive scaling scheme	GC w/o adaptive scaling scheme (Fixed code/Doppler search space bound)
Code delay (chip)	34.43 chip	553 samples	548 samples
Code delay (chip)	(550 samples)	553 samples	548 samples
Frequency shift (Hz)	2250 Hz	2275 Hz	2268 Hz
Repetitions	6563568 (401 × 16368)	16048	84000
Repetitions	(50 Hz step size)	(29 iterations)	(25 iterations) × 1500
Post-correlation SNR (dB)	18.7897	18.8675	18.8602
Execution Time (sec)	1817.24	806	705

5. Conclusions

In this paper, a novel GC with an adaptive scaling scheme is proposed, verified and applied to GNSS signal acquisition through simulation and experiment. It combines an adaptive scaling scheme that guides and controls the signal acquisition parameter boundaries and population size. Indeed, this proposed method can shorten the acquisition time and yield more accurate parameters using larger numbers of initial populations. Besides, the proposed scheme is simple in operation process and easy in digital circuit implementation owing to its choice of 0 and 1. In the future, the goal is oriented towards the reduction of hardware implementation complexity to meet the demand for low cost.

Acknowledgements

The authors would like to thank the reviewers and editor for giving the valuable comments to refine this paper. Also, many thanks to Jyh-Ching Juang of Mechatronics Laboratory, National Cheng Kung University for providing instruments to conduct our experiments and also the National Science Council of Taiwan for their support of this work under grant NSC 100-2221-E-020-027.

References

Parkinson, B.W.; Spilker, J.J. Global Positioning System: Theory and Applications; American Institute of Aeronautics and Astronautics: Washington, DC, USA, 1996; Volume 1. [Google Scholar]
Braasch, M.S.; van Dierendonck, A.J. GPS receiver architectures and measurements. Proc. IEEE 1999, 87, 48–64. [Google Scholar] [CrossRef]
Van Nee, D.J.R.; Coenen, A.J.R.M. New fast GPS code-acquisition technique using FFT. Electron. Lett. 1991, 27, 158–160. [Google Scholar] [CrossRef]
Namgoong, W.; Meng, T.H. Minimizing power consumption in direct sequence spread spectrum correlators by resampling IF samples-part I: Performance analysis. IEEE Trans. Circuits Syst. II 2001, 48, 450–459. [Google Scholar] [CrossRef]
Starzyk, J.; Zhu, Z. Averaging Correlation for C/A Code Acquisition and Tracking in Frequency Domain. In Proceeding of the IEEE Midwest Symposium on Circuits and Systems, Dayton, OH, USA, 14-17 August 2001; 2, pp. 905–908.
Pang, J.; van Graas, F.; Starzyk, J.; Zhu, Z. Fast direct GPS P-code acquisition. GPS Solut. 2003, 7, 168–175. [Google Scholar] [CrossRef]
Akopian, D. Fast FFT based GPS satellite acquisition methods. IEE Proc Radar Sonar Navig. 2005, 152, 277–286. [Google Scholar] [CrossRef]
Wilde, W.D.E.; Sleewaegen, J.M.; Simsky, A.; Vandewiele, C.; Peeters, E.; Grauwen, J.; Boon, F. New Fast Signal Acquisition Unit for GPS/Galileo Receivers. In Proceeding of the ENC GNSS, Manchester, UK, 8-10 May 2006; pp. 1–11.
Brown, A.; May, M.; Tanju, B. Benefits of software GPS receivers for enhanced signal processing. GPS Solut. 2000, 4, 56–66. [Google Scholar] [CrossRef]
Sagiraju, P.K.; Raju, G.V.S.; Akopian, D. Fast acquisition implementation for high sensitivity global positioning systems receivers based on joint and reduced space search. IET Radar Sonar Navi. 2008, 2, 376–387. [Google Scholar]
Jan, S.S.; Lin, Y.C. A new multi-C/A code acquisition method for GPS. GPS Solut. 2009, 13, 293–303. [Google Scholar] [CrossRef]
Chang, C.L. Using fuzzy logic controller with adaptive detection scheme for fast acquisition of satellite navigation signals. J. Chin. Inst. Eng. 2010, 33, 367–378. [Google Scholar]
Bagley, J.D. The Behavior of Adaptive Systems Which Employ Genetic and Correlative Algorithms. Ph.D. Dissertation, University of Michigan, Ann Arbor, MI, USA, 1967. [Google Scholar]
Holland, J.H. Adaptation in Natural and Artificial Systems; University of Michigan Press: Ann Arbor, MI, USA, 1975. [Google Scholar]
Dugan, N.; Erkoç, Ş. Genetic algorithms in application to the geometry optimization of nanoparticles. Algorithms 2009, 2, 410–428. [Google Scholar] [CrossRef]
De Jong, K.A. An Analysis of the Behavior of a Class of Genetic Adaptive Systems. Ph.D. Dissertation, University of Michigan, Ann Arbor, MI, USA, 1975. [Google Scholar]
Goldberg, D.E. Genetic Algorithms in Search, Optimization and Machine Learning; Addison-Wesley: Reading, MA, USA, 1989. [Google Scholar]
Fogel, D.B. An introduction to simulated evolutionary optimization. IEEE Trans. Neural. Netw. 1994, 5, 3–14. [Google Scholar] [CrossRef]
Cilla, R.; Patricio, M.A.; García, J.; Berlanga, A.; Molina, J.M. Recognizing human activities from sensors using hidden Markov models constructed by feature selection techniques. Algorithms 2009, 2, 282–300. [Google Scholar] [CrossRef]
Chang, C.L.; Shou, H.N.; Juang, J.C. Application of Innovation-Based Genetic Control Scheme to Signal Acquisition for Global Navigation Satellite Systems. In Proceedings of theICROS-SICE International Joint Conference, Fukuoka, Japan, 18-21 August 2009; pp. 3569–3574.
Rockwell International Corporation, Interface Control Document ICD-GPS-200; Rockwell International Corporation: Downey, CA, USA, 1991; pp. 9–86.
European Space Agency. Galileo Open Service Signal-In-Space Interface Control Document (OS SIS ICD). September 2010. Available online: http://ec.europa.eu/enterprise/policies/satnav/galileo/open-service/index_en.htm (accessed on 16 February 2012).
Zigangirov, K.S. Theory of Code Division Multiple Access Communication; IEEE Press, Wiley: New York, NY, USA, 2004. [Google Scholar]
Torrieri, D. Principles of Spread-Spectrum Communication Systems; Springer: New York, NY, USA, 2004. [Google Scholar]
Barket, M. Signal Detection and Estimation, 2nd ed; Artech House: Norwood, MA, USA, 2005. [Google Scholar]
Dillard, G.M. Mean-level detection of nonfluctuating signals. IEEE Trans. Aerosp. Electron. Syst. 1974, AES-10, 795–799. [Google Scholar] [CrossRef]
Davis, L. Handbook of Genetic Algorithms; Van Nostrand Reinhold: New York, NY, USA, 1991. [Google Scholar]
Borre, K.; Akos, D.M.; Bertelsen, N.; Rinder, P.; Jensen, S.H. A Software-Defined GPS and Galileo Receiver: A Signal-Frequency Approach; Birkhauser Boston: New York, NY, USA, 2007. [Google Scholar]

© 2012 by the authors; licensee MDPI, Basel, Switzerland. This article is an open-access article distributed under the terms and conditions of the Creative Commons Attribution license (http://creativecommons.org/licenses/by/3.0/).

Share and Cite

MDPI and ACS Style

Chang, C.-L.; Shou, H.-N. Application of Genetic Control with Adaptive Scaling Scheme to Signal Acquisition in Global Navigation Satellite System Receiver. Algorithms 2012, 5, 56-75. https://doi.org/10.3390/a5010056

AMA Style

Chang C-L, Shou H-N. Application of Genetic Control with Adaptive Scaling Scheme to Signal Acquisition in Global Navigation Satellite System Receiver. Algorithms. 2012; 5(1):56-75. https://doi.org/10.3390/a5010056

Chicago/Turabian Style

Chang, Chung-Liang, and Ho-Nien Shou. 2012. "Application of Genetic Control with Adaptive Scaling Scheme to Signal Acquisition in Global Navigation Satellite System Receiver" Algorithms 5, no. 1: 56-75. https://doi.org/10.3390/a5010056

Article Menu