Memetic particle swarm optimization scheme for direction-of-arrival estimation in multipath environment

1 Introduction

The use of an antenna array technique for direction-of-arrival (DOA) estimation has been widely studied for radio frequency applications [2, 6]. In wireless communications, signals exhibit the multi-path effect; when a signal propagates through two or more paths and reaches a receiving antenna, the signal energy is concentrated around the DOA, which causes the nominal DOA phenomenon. This nominal DOA phenomenon can substantially degrade the DOA estimation performance [5, 9].

Several DOA estimation methods have been studied. These methods include the minimum variance distortionless response (MVDR) method [3] and conventional subspace-based methods involving singular value decomposition, such as the multiple signal classification (MUSIC) method [24], estimation of signal parameters by using the rotational invariance technique (ESPRIT), and variants of ESPRIT under different conditions [22]. Estimates obtained using the MUSIC and MVDR methods may be biased because multipath propagation and signal dispersion are correlated [6]. Furthermore, in these methods, the search complexity and estimation accuracy primarily depend on the number of search grids used during the search. Moreover, the time consumption and the required number of search grids are difficult to determine in these methods. An efficient search-free modification of this approach, involving polynomial rooting rather than spectral searching, was proposed [21] for an efficient DOA estimation. However, polynomial rooting is suboptimal in multipath environments. Moreover, inappropriate root selection because of problems occurring in the calculation of local solutions often incurs a severe bias in the estimated parameters of a signal, particularly in low signal-to-noise-ratio (SNR) environments [6]. ESPRIT [22] may exhibit high performance and offer computational advantages; how-ever, it requires a translation-invariant structured array, and the estimation variance is large. An efficient approach to solve this problem is to reduce the nominal DOA phenomenon and search complexity by mapping the full dimension of an element space into a low-dimension beam space through beam-forming [6]. In general, in multipath environments, signal DOA is nominally a DOA phenomenon, causing the DOA estimation method to be biased. Recently, dynamical uniform and static logarithmic quantization strategies have been proposed to compensate for quantization errors [28]. Some data-driven model predictive control systems apply modified partial least squares to industrial control systems because the simplicity of computation enables updating of the online prediction mode and excellent approximation ability [7]. Therefore, in this study, received signals were projected onto an appropriate beam space to reduce the multipath effect. The scheme was as follows: First, particle swarm optimization (PSO) and MVDR methods were used to estimate the DOA of signals. Second, the individual best position of the swarm and the beam space MVDR (BMVDR) method were used to construct an objective function. The first-order Taylor expansion of the objective function and local search techniques were used to enhance the search accuracy and reduce the search complexity.

PSO, an evolutionary computation technique, has drawn considerable attention since it was proposed by Kennedy and Eberhart in 1995 [11]. The technique is based on the social behavior of animals, such as bird flocking, insect swarming, and fish schooling. PSO has been successfully used to over-come complex optimization problems. Furthermore, this technique is easy to implement and can efficiently solve difficult optimization problems, such as numerical optimization [4, 8] and multi-objective [12] and nonlinear processing problems [23, 27]. PSO is similar to evolutionary algorithms, such as genetic and differential evolution algorithms, and is a population-based random search optimization technique, where the population is called a swarm. Each swarm consists of numerous particles that represent solutions of the pertinent problem. The position of each particle in the search space is updated according to the particle velocity, and the local and global best positions of the particle in the search space are determined. In PSO, many points are simultaneously evaluated in a parameter space, and although the technique is likely to converge to some local optimal solution, convergence to the global optimum is not guaranteed, particularly when the objective function has a numerous dimensions or is a complex nonlinear function. Moreover, PSO can rapidly determine the global optimum; however, it cannot perform a refined local search to compute the global optimum with high accuracy, unless specific procedures are incorporated in the operator.

In this study, to overcome the premature convergence of PSO and effectively estimate the DOA in multipath environments, a local search was incorporated into PSO to develop an MPSO method for DOA estimation in a multipath environment. The proposed MPSO method is simple and feasible because it involves a first-order Taylor series expansion of the objective function through BMVDR criterion techniques [10] for limiting the solution to certain local optimization points. The method improves the capability of PSO to determine optimal solutions. The first-order Taylor series approximates the spatial scanning vector in terms of the estimated deviation results and reduces a complex optimization problem to a simple one-dimensional optimization problem [20]. Simulation results indicated that the DOA estimation from the proposed estimator exhibits excellent performance in the multipath environment.

The remainder of this paper is organized as follows: The problem description is provided in Section II. Section III introduces the MPSO estimator for DOA estimation, and Section IV presents empirical results that demonstrate the effectiveness of the proposed method. The last section, Section V, summarizes the conclusions.

2 Problem description

Consider a uniform linear array (ULA) consisting of M omnidirectional sensors receiving signals generated by P far-field narrowband sources. The signal received at the kth measured snapshot can be expressed as x ( k ) = ∑ p = 1 P a ( θ p ) s p ( k ) + n ( k )(1) where k = 1, 2, ⋯, N. N and s _p (k) are the number of snapshots and the pth signal source, respectively. n ( k ) = [ n 1 ( k ) n 2 ( k ) ⋯ n M ( k ) ] T is sensor noise, and x ( k ) = [ x 1 ( k ) x 2 ( k ) ⋯ x M ( k ) ] T , that is, x _i (k) is the ith sensor receiving signals, and a (θ _p ) is a steering vector defined by

a ( θ p ) = [ 1 exp ( - j 2 π d sin θ p λ ) ⋯ exp ( - j 2 π d ( M - 1 ) sin θ p λ ) ] T(2) where j = - 1 , and λ is the wavelength of the signal carrier, and d is the interelement spacing in the sensor array. Multipath reflections are assumed to follow the local scattering model [25], and the scattered multipath signal of each user can be suitably approximated using a single-point source with an angle spread in a specified angular interval centered at the line-of-sight angle, θ _p . For each θ _p , there is a set of uniformly distributed J random multipath angles are spread over the interval [θ _p - 0.5ξθ, θ _p + 0.5ξθ] [24], where ξθ is the angle spread. For multipath reflections, Equation (1) can be expressed as x ( k ) = ∑ p = 1 P ∑ j = 1 J α p , j a ( θ p , j ) s p ( k ) + n ( k ) = ∑ p = 1 P b ( θ p ) s p ( k ) + n ( k ) ,(3) where α_p,j is the associated complex gain because of the multipath effect, θ_p,j is the direction angle of the jth path of the pth signal, and b (θ _p ) is the sum of J paths for the pth signal. Equation (3) can be rewritten by using matrix notation for the signals received from M sensors as follows x ( k ) = B ( θ ) s ( k ) + n ( k ) ,(4) where B ( θ ) = [ b ( θ 1 ) b ( θ 2 ) ⋯ b ( θ P ) ] , s (k) = [ s 1 ( k ) s 2 ( k ) ⋯ s P ( k ) ] T . Generally, n (k) are assumed to be a zero-mean Gaussian process such that E [ n ( k ) ] = 0 , R n = E [ n ( k ) n ( k ) H ] = σ n 2 I M(5) where E [·] denote the expectation and the superscript H and complex conjugate transpose, respectively. I _M is an M × M identity matrix.

The following assumptions are included:

The number of sources P is known or can be estimated and P < M [25].

The second order propagation model corresponding to Equation (4) can be expressed as R = E { x ( k ) x H ( k ) } = B ( θ ) R s B H ( θ ) + R n(6) where R _s = E [s (t) s ^H (t)] is the source signal covariance matrix. For a finite number of received signals, the received signal covariance matrix R is replaced by the estimated sample average R ˆ , which is given as follows R ˆ = ( 1 / N ) ∑ k = 1 N x ( k ) x H ( k ) ,(7)

The MVDR estimator is a beamforming-based estimator, which estimates the DOA of a desired signal through a spatial search of peaks of the power spectrum defined as [3] J ( θ ) = max θ 1 | a H ( θ ) R ˆ - 1 a ( θ ) |(8)

Therefore, the DOA estimated using the MVDR method is biased in the multipath environment. To reduce the multipath effect [6], researchers have proposed the BMVDR estimator, which first projects the original data into a subspace (i.e., the beam space [9]) and then processes the beam space data by using the MVDR estimator. Let Q be the M × (K + 1) beam space matrix given as follows [8]

Q = [ a ( θ ˆ 1 ) a ( θ ˆ 1 + Δ θ ) a ( θ ˆ 1 - Δ θ ) ⋯ a ( θ ˆ 1 + K 2 Δ θ ) a ( θ ˆ 1 - K 2 Δ θ ) ](9) where θ ˆ 1 is the estimated direction value of θ₁, Δθ is a small number with uniform distributions, and K is a positive even integer. The received signal projected to the beam space can be written as z ( k ) = Q H x ( k ) = Q H B ( θ ) s ( k ) + n z(10) where n _z = Q ^H n (k). Similar to Equation (4) the covariance matrix of z (k) can be rewritten as R z = E [ z ( k ) z H ( k ) ] = Q H RQ = Q H B ( θ ) R s B H ( θ ) Q + Q H R n Q(11) where R _z is a (K + 1) × (K + 1) matrix. If R _z is replaced by the estimated sample average R ˆ z , then an expression similar to Equation (7) is obtained ( R ˆ z = Q H ( 1 N ∑ k = 1 N x ( k ) x H ( k ) ) Q ). The BMVDR estimator power spectrum in the beam space can be given as J B ( θ ) = max θ 1 | a z H ( θ ) R ˆ z - 1 a z ( θ ) | = max θ 1 | a z H ( θ ) Q H R ˆ - 1 Qa z ( θ ) |(12)

In general, J _B (θ) is a highly nonlinear function of θ and Q for an appropriate initial estimate of θ ˆ 1 . Furthermore, several local maxima and the nominal DOA phenomenon may exist. PSO is associated with the premature convergence problem and can be trapped in local optima, which impairs the precision of the optimization. To overcome these drawbacks and reduce the multipath effect in multipath environments, PSO was employed in this study to obtain the initial value of θ ˆ 1 . This study used a local search procedure in MPSO to solve the parameter estimation problem in Equation (12). To reduce a complex optimization problem to a simple one-dimensional optimization problem and compute the optimum with high accuracy, a first-order Taylor series approximation of Equation (12) was used for the local search [21]. Equation (12), the BMVDR cost function, exhibits that determining the maximum is equivalent to determining the minimum of the denominator of the cost function J B ( θ ) = min θ | a z H ( θ ) Q H R ˆ - 1 Qa z ( θ ) | .(13)

In a small region ηθ, Qa _z (θ) can be approximated using a first-order Taylor series approximation at θ ˆ 1 as [9] f ( θ ) = Qa z ( θ ) ≅ f ( θ ˆ 1 ) + η θ f ′ ( θ ˆ 1 ) ,(14) where f ′ ( θ ˆ 1 ) = d d θ f ( θ ) | θ = θ ˆ 1 . The substitution of Equation (14) in Equation (13) provides min η θ [ f ( θ ˆ 1 ) + η θ f ′ ( θ ˆ 1 ) ] H R ˆ - 1 [ f ( θ ˆ 1 ) + η θ f ′ ( θ ˆ 1 ) ] ,(15)

This is a simple one-dimensional optimization problem. The optimum ηθ is given by d { [ f ( θ ˆ 1 ) + η θ f ′ ( θ ˆ 1 ) ] H R ˆ - 1 [ f ( θ ˆ 1 ) + η θ f ′ ( θ ˆ 1 ) ] } d ( η θ ) = 0 ⇒ η θ = - Re [ f ( θ ˆ 1 ) H R ˆ - 1 f ′ ( θ ˆ 1 ) ] f ′ ( θ ˆ 1 ) H R ˆ - 1 f ′ ( θ ˆ 1 )(16) where Re [·] denotes the real part of the complex quantity. The value of ηθ in Equation (16) exhibits the following characteristics [9]:

If the value of ηθ is small, a convergence solution is obtained (local or global).

The utilization of the local search method in MPSO by using the characteristic of ηθ, a hybrid algorithm combining PSO with local search techniques, was proposed in this study. An appropriate θ ˆ 1 was first searched using PSO in Equation (8) and the value of θ ˆ 1 was then updated using ηθ characteristics and local search techniques.

In this study, an MPSO method was employed for DOA estimation in the multipath environment. MPSO was combined with PSO and local search techniques; these techniques consisted of two components, a global search of the search space per-formed using a PSO-based estimator, and a local search, which accurately searched the neighborhood of potential solutions of the first component, by using the problem characteristics. The PSO and pro-posed MPSO are described in this section.

3.2 MPSO estimator

The memetic algorithm (MA) was first introduced in [15,16, 15,16]. The MA is an efficient, high-performance combination of evolutionary algorithms and local search. The proposed MPSO algorithm is a hybrid algorithm that combines PSO with new local search techniques. Empirical studies of PSO have indicated that this technique can rapidly determine optima; however, it cannot perform a refined local search to compute an optimum with high accuracy, unless specific procedures are incorporated in its operation. Thus, the MPSO is introduced to address the premature convergence problem and to avoid obtaining solutions that are not guaranteed to be local optima.

The local search techniques used in the proposed MPSO are based on the ηθ characteristics in Equation (16). Moreover, these techniques assist in approaching the exact global optimum and reduce bias in multipath environments. The characteristics of ηθ indicate that for a relatively small ηθ, a convergence solution, which may be local or global, is rapidly obtained. By contrast, for a relatively large ηθ, convergence requires considerable time and updating of the estimated deviation in the approach to the actual value. The estimated deviation ηθ progresses toward a promising search area. Thus, ηθ can be used for local searches in MPSO. The local search of MPSO can be expressed as follows θ ˆ 1 = { θ ˆ 1 + η θ , for | η θ | > ɛ θ ˆ 1 , for | η θ | ≤ ɛ(21) where θ ˆ 1 is the position of PSO and ɛ is the search precision. This local search technique is repeated until the condition ηθ < ɛ is satisfied. In this study, local search was performed for the personal best position p _i [26] and Equation (17) was then used to find the overall best position g of the swarm, to reduce the multipath effect. The pseudocode of the MPSO estimator is as follows:

Input: x (k), P, N, M, K, Δθ for the BMVDR method and S, c₁, c₂, ɛ, v_max, θ_min, θ_max for the MPSO method.

Output: DOA θ ∈ [ θ min θ max ]

Step 1. Set t = 0.

Step 2. Evaluate R ˆ and, χ by using Equations (7 and 21), respectively, and randomly generate θ _i (t) and v _i (t) for i = 1, 2, ⋯, S.

Step 3. Evaluate the fitness function Fit (θ _i (t)) in Equation (17).

Step 4. Set p _i ← θ _i (t) and g = max {Fit (θ _i (t))}.

Step 5. Update the velocities v _i (t + 1) and positions θ _i (t + 1) by using Equations (19 and 20), respectively, within the interval [ θ min θ max ] .

Step 6. Evaluate Fit (θ _i (t + 1)).

Step 7. IF Fit (θ _i (t + 1)) > Fit (θ _i (t)) then p _i ← θ _i (t + 1).

Step 8. Set θ ˆ i ← p i and evaluate ηθ _i by using Equation (16).

Step 9. While |ηθ _i | > ɛ Do

Update θ ˆ i ← θ ˆ i + η θ

End While.

Step 10. Set p i ← θ ˆ i and update g = max {p _i }.

Step 11. Set t = t + 1.

Step 12. Go to Step 5, unless the termination criterion is satisfied.

Figure 1 presents the concept of the proposed method. The concept is based on the preceding analysis.

OPEN IN VIEWER

Fig.1

Flowchart of the proposed method.

Two examples were investigated to illustrate the high DOA estimation performance of the proposed estimator for the multipath environment. The results were compared with those of other estimators, including the MUSIC [24], MVDR [3], and ESPRIT estimators [22]. To demonstrate the effectiveness of the proposed method in improving PSO, six state-of-the-art PSO methods were selected for performance comparison including PSO [11], unified PSO [17], comprehensive learning PSO [12], cooperative PSO [1], fitness-distance-ratio-based PSO [18], and fully informed particle swarm [14]. In the literature [25], the root mean squared error (RMSE) was used to compare the estimation performance. The RMSE is defined as RMSE θ ˆ 1 = [ ( 1 / F ) ∑ j = 1 F ( θ ˆ 1 , j - θ 1 ) 2 ] ,(22) where F indicates the number of independent Monte Carlo runs, and in this study, F = 100. The deviation precision was ɛ = 0.001°, and the searching grid size for the spectrum-searching estimators, such as MUSIC and MVDR, was set at 0. 001°. All the algorithms were implemented in Matrix Laboratory (MATLAB). The parameters of the all PSO-based estimators were defined as follows c 1 = c 2 = 1.496 , χ = 0.729 , V max = 9 ∘ , S = 100 , T = 100(23) where T is the number of iterations.

Example 1. Consider an eight-element ULA with a half-wavelength spacing. Let three users generate active code division multiple access (CDMA) signals [13] by using a binary phase shift keying modulation and a pseudo noise code with a processing gain of 31. Assume that the additive background noise exhibits a spatially and temporally white complex Gaussian distribution with a zero mean and a unit variance. The impinging angles of the interferers with equal power (5 dB) are [-30°, 30°]. The signal from the desired user impinges on the array at an angle of θ₁ = 0°. In the multipath environment, the incident angles of all signals with four paths are uniformly distributed over the angular interval [θ _p - 0.5ξθ, θ _p + 0.5ξθ], with the angular spread of ξθ = 5°. All multipath rays are of equal power and exhibit a fixed amplitude scale of 1 J .

Figure 2 displays the simulated beam pattern for the MVDR estimator. In the figure, the multipath environment causes the nominal DOA phenomenon (green circle region), incurring a bias of 2° in the DOA estimation method. Figure 3 presents the values of ηθ in Equation (16) with the initial θ ˆ 1 values obtained by the MVDR estimation. If the ηθ value is small, convergence is rapidly obtained and the multipath effect is reduced (green background region). Therefore, the received signals are projected onto an appropriate beam space, reducing the multipath effect. Table 1 presents the DOA estimates (RMSEs, estimated values, and standard errors) obtained using the MUSIC, MVDR, ESPRIT estimators, and the PSO-based methods along with the proposed estimator. The table indicates that the estimates obtained using all estimators, except the proposed method, are biased in the multipath environment. Moreover, the table indicates that the RMSE of the proposed method is smaller than that of the other estimators. Furthermore, the table illustrates that the standard error of the proposed method is approximately smaller than that of the other estimators. Thus, the proposed method is highly effective in determining the global optimum and exhibits a small DOA bias in the multipath environment. The MUSIC and ESPRIT estimators exhibit unsatisfactory performance at low SNRs. DOA values estimated by the PSO-based estimators at a low SNR indicate a success rate of approximately 45% in the range -5° 5°. The PSO-based estimators converge to local optima, but the PSO-based estimators are probably biased because of interference signals and the multipath effect. Figure 4 displays plots of the RMSE versus the SNR for the various estimators. Unlike MUSIC and ESPRIT estimators, the MVDR estimator is insensitive to the SNR; however, its estimation is biased in the multipath environment. The proposed estimator exhibits high performance, particularly in low SNR environments. Figure 5 presents plots of the RMSE versus the SNR for the proposed method and the six PSO-based estimators. The six PSO-based estimators exhibit very unsatisfactory convergence to local optima because of the multipath environment and interfering signals. Figure 6 presents plots of the RMSE versus the SNR for the proposed method and the six PSO-based estimators for estimation values in the range -5° 5°. The performance of the proposed method is superior to that of the PSO-based estimators. Furthermore, the local search in the proposed method is valid.

OPEN IN VIEWER

Fig.2

Beam pattern for the MVDR method in Example 1.

OPEN IN VIEWER

Fig.3

Plot of ηθ in Equation (16) against θ ˆ 1 for Example 1.

OPEN IN VIEWER

Fig.4

Plots of the RMSE of the DOA estimates versus the SNR for the MVDR, MUSIC, ESPRIT, and proposed estimators for Example 1.

OPEN IN VIEWER

Fig.5

Plots of the RMSE of the DOA estimates versus the SNR for the six PSO-based estimators and the proposed method for Example 1.

Example 2. Consider an eight-element ULA with a half-wavelength interelement spacing, seven CDMA users, and J = 8. The impinging angles of all six interferers with an equal power of 10 dB are [ - 50 ∘ - 30 ∘ - 15 ∘ 15 ∘ 30 ∘ 50 ∘ ] . The signal from a desired user impinges on the array at an angle of θ₁ = 0°. The other parameters are identical to those of Example 1. Table 2 presents the DOA estimates (RMSEs, estimated values, and standard errors) of MUSIC, MVDR, ESPRIT estimators, and all the PSO-based methods along with the proposed estimator. The estimation performance of the MUSIC and ESPRIT estimators evidently deteriorates at low SNRs. Moreover, the PSO-based methods efficiently converge to the local optimal solution. Estimates of the PSO-based methods in the range [ - 5 ∘ 5 ∘ ] indicate success rates of approximately 25% at low SNRs. The performance of the proposed estimator is superior to that of the other estimators. Figure 7 depicts plots of the RMSE performance versus the SNR for the MVDR, MUSIC, ESPRIT, and proposed estimators. The results, as anticipated, indicate that the proposed estimator provides a more accurate DOA estimate than that of the other estimators. Plots of the RMSE versus the SNR for the DOA estimates of the proposed method and the six PSO-based estimators are displayed in Figs. 8 and 9. The proposed estimator exhibits not only the benefits of local searching but also an improved DOA estimation accuracy.

OPEN IN VIEWER

Fig.6

Plots of the RMSE of the DOA estimates versus the SNR for the six PSO-based estimators (for estimates in the range -5° 5°) and proposed method for Example 1.

OPEN IN VIEWER

Fig.7

Plots of the RMSE of the DOA estimates versus the SNR for the MVDR, MUSIC, ESPRIT, and proposed estimators for Example 2.

OPEN IN VIEWER

Fig.8

Plots of the RMSE of the DOA estimates versus the SNR for the six PSO-based estimators and proposed method for Example 2.

OPEN IN VIEWER

Fig.9

Plots of the RMSE of the DOA estimates versus the SNR for the six PSO-based estimators (for estimates in the range -5° 5°) and the proposed method for Example 2.

In this study, a new MPSO scheme was proposed for the DOA estimation in multipath environments. The empirical results demonstrated that the scheme exhibits an excellent capability to escape local optima. Moreover, the results indicate reduced bias for estimates in multipath environments. The proposed approach for the DOA estimation is efficient. The approach involves a combination of PSO and local search techniques. The local search techniques involve the first-order Taylor expansion approximation of BMVDR characters to obtain the exact global optimum and reduce the bias occurring in multipath environments. PSO methods involve parallel search methods that partially depend on the initial value; however, their performance is biased in multipath environments. Moreover, their performance deteriorates when the desired global optimum is approached. The features of the PSO and the estimated deviation ηθ were combined to achieve high accuracy and rapid convergence. Computer simulations were performed to demonstrate the effectiveness of the proposed estimator at low SNRs and in multipath environments.