# A Low-Complexity GA-WSF Algorithm for Narrow-Band DOA Estimation

Authors: Haihua Chen; Jialiang Hu; Hui Tian; Shibao Li; Jianhang Liu; Masakiyo Suzuki
Journal: International Journal of Antennas and Propagation
 (2018)

---

## Abstract

This paper proposes a low-complexity estimation algorithm for weighted subspace fitting (WSF) based on the Genetic Algorithm (GA) in the problem of narrow-band direction-of-arrival (DOA) finding. Among various solving techniques for DOA, WSF is one of the highest estimation accuracy algorithms. However, its criteria is a multimodal nonlinear multivariate optimization problem. As a result, the computational complexity of WSF is very high, which prevents its application to real systems. The Genetic Algorithm (GA) is considered as an effective algorithm for finding the global solution of WSF. However, conventional GA usually needs a big population size to cover the whole searching space and a large number of generations for convergence, which means that the computational complexity is still high. To reduce the computational complexity of WSF, this paper proposes an improved Genetic algorithm. Firstly a hypothesis technique is used for a rough DOA estimation for WSF. Then, a dynamic initialization space is formed around this value with an empirical function. Within this space, a smaller population size and smaller amount of generations are required. Consequently, the computational complexity is reduced. Simulation results show the efficiency of the proposed algorithm in comparison to many existing algorithms.


---

## Body

## 1. Introduction

The narrow-band direction-of-arrival (DOA) estimation is a basic and important problem in sensor array signal processing. So far, a set of classical algorithms have been proposed, such as those in [1–7]. Based on this basic narrow-band model and the classical algorithms above, many innovative algorithms have been developed according to different models of signals, noise, and array manifolds, such as those in [8–12].Among these techniques, the weighted subspace fitting (WSF) is one of the highest estimation accuracy algorithms and it can also deal with coherent signals directly. However, its criteria is a multimodal nonlinear multivariate optimization problem. As a result, the computational complexity of WSF is very high, which prevents its application to real systems.Artificial intelligence algorithms such as Genetic Algorithm (GA) [13], Particle Swarm Optimization (PSO) [14], Joint-PSO [15], and Bee Colony [16] algorithms are considered to be general and efficient ways for such a problem. However, conventional artificial intelligence algorithms usually need a big population size to cover the whole searching space and a large number of iteration times for convergence. Although Joint-PSO is a rather efficient algorithm for SML estimation, it requires some preprocessing techniques which may make the system more complex.Based on the Genetic Algorithm, this paper proposes an improved low-complexity Genetic algorithm for WSF estimation. Firstly, it uses a hypothesis technique for a rough DOA estimation for WSF. Then, a dynamic initialization space is formed around this value with an empirical function with respect to signal-to-noise ratio (SNR). Compared to the original whole searching space, this initialization space is much smaller and can be considered to be close to the solution of WSF. Then, a smaller population size and smaller amount of generations are required. Consequently, the computational complexity is reduced. At last, simulation results show the efficiency of the proposed algorithm in comparison to many other algorithms.The rest of this paper is organized as follows. In Section2, we introduce the problem of DOA and the formulation of WSF. In Section 3, we introduce the proposed algorithm. Simulation results are shown in Section 4, and the conclusion is drawn in Section 5.


## 2. System Model and Problem Formulations

To make the article more compact, this section just shows a brief system model and problem formulation. For detailed information, the readers should refer to [5, 6].Consider that there arep sensors (the array configuration can be arbitrary) receiving q narrow-band signal waves. p and q are known. Sensors and signals are in the same far-field plane. All the signals have distinct directions θ1,θ2,…,θq. Note that the number of sensors should be greater than the number of signals, that is, p>q. Furthermore, we have assumed that the sensors are omnidirectional and the array response is ideal, otherwise some calibration techniques should be used, such as those in [17, 18]. Then, the output of the array is as follows:
(1)yt=AΘxt+et,where yt is the p-dimension output vector, xt is the q-dimension signal vector, et is the noise vector, and AΘ is the steering vector parameterized by Θ=θ1,θ2,…,θq. Taking M snapshots of the array, the observed data is Y=yt1yt2⋯ytM. Then, we calculate the covariance matrix of the observed data and make an eigen decomposition of it as follows:
(2)R^=1MYYH=∑i=1pλieieiH=E^x∧^xE^xH+σ^2E^eE^eH,where λi and ei are eigenvalues and eigenvectors, ∧^x is a diagonal matrix and constructed by the q largest eigenvalues, E^x is constructed by the corresponding eigenvectors of ∧^x, E^e is the orthogonal complement of E^x, σ^2=1/p−q∑i=q+1pλi.Then, the WSF criterion is shown as follows:(3)Θ^=argminΘLW,(4)LW=trPA⊥E^x∧^x−σ^2I2∧^x−1E^xH,where
(5)PA⊥=I−AΘAΘHAΘ−1AΘH.From (3) to (4), it is clear that the estimation of WSF is to find a set of Θ to minimize LW, which is a multimodal nonlinear multivariate optimization problem.


## 3. Improved Genetic Algorithm for WSF

The Genetic Algorithm (Algorithm1) is considered to be a general and effective way for such a multimodal nonlinear multivariate optimization problem.However, conventional GA usually needs a big population size to cover the whole searching space (every direction varies from −90 to 90 degrees) and a large number of generations for convergence, which means that the computational complexity is still high. To reduce computational complexity of WSF, this paper proposes an improved Genetic algorithm. The improved GA applied for WSF is shown as follows.Algorithm 1.
Genetic Algorithm(1)
Rough DOA search
A hypothesis technique is used in this step to find a rough DOA for WSF. LetLmΘ^m be a cost function of LW in (4) where m is the assuming signal number and Θ^m=θ^1,θ^2,…,θ^m.
(i)
Assumingm=1, calculate the corresponding steering vector AΘ^1, the covariance matrix of observed data R^Θ^1, and L1Θ^1 in turn. Obviously, the cost function L1Θ^1 is a one-dimensional optimization problem with respect to θ^1. Find θ^1 which minimizes L1Θ^1.
(ii)
Assumingm=2 and fixing θ^1 obtained above, calculate L2Θ^2. Now L2Θ^2 is also a one-dimensional optimization problem with respect to θ^2. Find θ^2 which minimizes L2Θ^2….
q Assuming m=q, find θ^q in the same manner.
DefineΘ^M=θ^1,θ^2,…,θ^q obtained above. This is a rough search DOA for WSF. Although it is hard to prove that Θ^M is close to the solution of WSF in theory, simulation results show that this hypothesis technique provides a rather good rough search value. Figure 1 shows the positions of a rough DOA search value, the true DOA, and the solution of WSF for both coherent and noncoherent cases. In the noncoherent case, the rough search DOA is rather close to the solution of WSF as Figure 1(a) shows, while in the coherent case, they are a little far apart (when SNR=0dB, less than 5 degrees apart) as Figure 1(b) shows. It is clear that the rough search DOA can be considered to be rather close to the solution of WSF for both cases.
(2)
Initialization space
Then around this value, we should use a “scale” to span the initialization space. This initialization space should be close or even contain the solution of WSF. Then, a smaller population size is needed and all the individuals which are randomly initiated in this space could converge quickly to the solution of WSF.
We define the “scale” empirically as follows, which is a function with respect to SNR:(6)fSNR=1eSNR/10,fornon‐coherentcase,5eSNR/10,forcoherentcase.
Note that the “scale” is different for coherent and noncoherent cases. This is because in the noncoherent case, the rough search DOA is more closer to the solution of WSF (as shown in Figure1). As a result, the initialization space could be smaller. The initialization space is defined as a set of Θ in which
(7)θ1∈θ^1−fSNR1,θ^1+fSNR1,(8)θ2∈θ^2−fSNR2,θ^2+fSNR2,…(9)θq∈θ^q−fSNRq,θ^q+fSNRq,where SNRi is the signal-to-noise ratio of the ith signal. Obviously, θ^i−fSNRi≥−90° and θ^i+fSNRi≤90°. Note that this initialization space is dynamic. When SNR gets higher, the initialization space gets smaller because the rough search DOA is closer to the solution of WSF. Then, only a small population size is needed and all the individuals will converge quickly to the solution of WSF.Figure 1
Positions of the solution of WSF, the true DOA, and the rough search DOA. (a)p=8, q=2, M=100, and SNR=0dB; all the signals are independent (noncoherent). (b) p=8, q=2, M=100, and SNR=0dB; 2 signals are fully correlated (coherent).
(a)
(b)The proposed algorithm can be summarized as follows:(1)
Rough DOA search and getΘ^M as above.
(2)
Construct the initialization space with respect to (6) to (9).
(3)
In the initialization space acquired in step 2, randomly initiate a swarm of particlesΘ¯=Θ~1,Θ~2,…,Θ~m whose position might be the potential solution to the optimization problem. m is the number of particles. Θ~i=θi1,θi2,…,θiq is defined as the ith 1≤i≤m particle’s position in the search space.
(4)
Evaluate all the individuals according to the fitness function (4), that is, LWΘ¯, and select the top m/2 individuals whose fitness function value are smaller than others.
(5)
From the selected individuals, cross and mutate to generatem−m/2 new individuals. The crossover process is similar to the following process. Randomly select two individuals in step 4 to generate a new individual. For example, select Θ~i and Θ~j to generate Θ~k. Θ~k=θi1+θj1/2,θi2+θj2/2,…,θiq+θjq/2. The mutation process is such that when an individual is selected to be mutated, it will be randomly changed to a new position. Note that crossover and mutation are probabilistic, which are called crossover probability and mutation probability.
(6)
Let the newly createdm−m/2 individuals in step 5 and the m/2 individuals selected in step 4 determine a new set of m individuals Θ¯1=Θ~11,Θ~21,…,Θ~m1.
(7)
LetΘ¯1 replace Θ¯ and go to step 4 until the convergence condition is satisfied or when the number of generations reaches the maximum.From a large number of simulations for the proposed algorithm, it is better to set the parameters as follows: the crossover probability is set to be 0.89, the population sizem, is set to be 20, the maximum number of generations is set to be 300, and the mutation probability is set to be 0.1. The convergence condition is such that the best individual of the whole population does not change for three consecutive times.Note that the proposed algorithm does not have any effect on the DOA finding accuracy compared with the conventional GA. Even if the rough search DOA and the initialization space are far from the solution of WSF, the improved GA algorithm will still find the solution of WSF through a relatively large number of generations.


## 4. Simulations

In the simulation, we compare the computational complexity of the proposed algorithm and many other existing algorithms such as AM [4], conventional GA [13], and PSO [14]. We do simulation using “Matlab” with the version of R2013a in a normal laptop where the CPU is an Intel® Core™ i5-6300U @2.40 GHz and the RAM is 8.0 GB. The SNR is signal-to-noise ratio. The root-mean-square-error (RMSE) is defined as
(10)RMSE=1qN∑k=1q∑l=1Nθ^k,l−θk2,where N is the number of independent simulation trails and θ^k,l is the estimation of θk at the lth trial. Therefore, RMSE represents the deviation between the estimated value and the true DOA. The unit is degree.Figure2 shows the RMSE of the estimation of WSF and MUSIC according to different SNRs. The scenario is the same as Figure 1(a) except for the SNR. Note that for the estimation of WSF, both the proposed algorithm and the original GA are used. The RMSE of these two methods are exactly the same. It proves that the proposed algorithm does not have any effect on the DOA finding accuracy compared with the original GA. Furthermore, Figure 2 also shows that the DOA estimation accuracy of WSF is much better than that of MUSIC as we have described in the Introduction.Figure 2
RMSE of the estimation of WSF and MUSIC.Figure3 shows the comparison of calculating time (the total computational complexity) using the proposed algorithm, original GA, PSO, and AM for WSF estimation according to different SNRs. For each SNR, we have done 30 independent simulation trials. The calculating time is the average time of 30 independent trials. Figure 3(a) shows the noncoherent case, that is, all the signals are independent, while Figure 3(b) shows the coherent case. “Proposed” represents the proposed algorithm and the other symbols represent their respective algorithms for WSF estimation. To have a fair comparison of computational complexity, their convergence accuracies are set to be the same. The scenarios are described in the captions.Figure 3
Comparison of calculating time using the proposed algorithm, original GA, PSO, and AM for WSF estimation. (a)p=8, q=2, and M=100; all the signals are independent (noncoherent case). (b) p=8, q=4, and M=100; the independent signal number is 2 (coherent case).
(a)
(b)From Figures3(a) and 3(b), it is found that the proposed algorithm is the most efficient one among these solving techniques. Furthermore, the efficiency is more obvious when the signal number increases (more directional parameters to be estimated) as Figure 3(b) shows. The total computational complexity of the proposed algorithm is about one-eighth of the original GA.As we have analyzed above, the total computational complexity of the proposed algorithm depends on two factors, that is, the population size and the iteration times. Table1 shows the comparison of computational complexity of each algorithm in detail. Table 1 is a sample of Figure 3(a) when SNR=0dB. As Table 1 shows, the population size of the proposed algorithm is 20, while for the original GA and PSO the population size should be at least 30. The average iteration times of the proposed algorithm is 35, while the original GA is 202. This is because in the proposed algorithm, the novel initialization space is much smaller than the whole search space and the solution of WSF can be considered to be close to the initialization space. As a result, a smaller population size is needed and all the particles could converge to the solution of WSF quickly (less iteration times). Consequently, the computational complexity is much lower.Table 1
Comparison of computational complexity of each algorithm in detail.
Proposed
Original GA
PSO
AM
Population size
20
30
30
—
Average iteration times
35
202
154
—
Total calculating time (seconds)
0.45
3.28
2.85
2.23


## 5. Conclusion

In this paper, an improved Genetic algorithm is proposed for WSF estimation of DOA. This proposed algorithm uses a hypothesis technique and an empirical function to determine a dynamic initialization space. Within this space, a smaller population size and smaller amount of generations are required. Consequently, the computational complexity is reduced. This paper has the following contributions: (1) The technique of limiting the initialization space is general and it can be applied to some other artificial intelligence algorithms such as PSO for DOA estimation. (2) The computational complexity of the proposed algorithm is rather low and it does not have any effect on the DOA estimation accuracy. (3) It is a general technique for DOA estimation.



---

*Source: 7175653-2018-11-04.xml*