# A Low Computational Complexity SML Estimation Algorithm of DOA for Wireless Sensor Networks

Authors: Faming Gong; Haihua Chen; Shibao Li; Jianhang Liu; Zhaozhi Gu; Masakiyo Suzuki
Journal: International Journal of Distributed Sensor Networks
 (2015)

---

## Abstract

We address the problem of DOA estimation in positioning of nodes in wireless sensor networks. The Stochastic Maximum Likelihood (SML) algorithm is adopted in this paper. The SML algorithm is well-known for its high resolution of DOA estimation. However, its computational complexity is very high because multidimensional nonlinear optimization problem is usually involved. To reduce the computational complexity of SML estimation, we do the following work. (1) We point out the problems of conventional SML criterion and explain why and how these problems happen. (2) A local AM search method is proposed which could be used to find the local solution near/around the initial value. (3) We propose an algorithm which uses the local AM search method together with the estimation of DML or MUSIC as initial value to find the solution of SML. Simulation results are shown to demonstrate the effectiveness and efficiency of the proposed algorithms. In particular, the algorithm which uses the local AM method and estimation of MUSIC as initial value has much higher resolution and comparable computational complexity to MUSIC.


---

## Body

## 1. Introduction

Wireless sensor networks (WSNs) are commonly employed for many applications including environmental protection, structural monitoring, and passive localization and tracking. Positioning is a basic problem for most wireless sensor network applications [1–3].There are mainly two categories of WSNs node localization methods, that is, range-based localization scheme and range-free localization scheme. The accuracy of the former is obviously higher than that of the latter. Range-based localization methods include many techniques such as received signal strength indicator (RSSI), time of arrival (TOA), time difference of arrival (TDOA), and direction of arrival (DOA) [4–6]. This paper mainly focuses on the DOA estimation algorithm in WSNs.To ensure the timeliness and accuracy of the system, the DOA estimation algorithm must have low computational complexity and high DOA resolution. Multiple Signal Classification (MUSIC) [7, 8] and Estimation of Signal Parameters via Rotational Invariance Techniques (ESPRIT) [9] are two widely employed algorithms for DOA estimation in many communication systems [6, 10, 11] because the resolution of them is acceptable in some cases and the computational complexity is low enough such that timeliness of the system can be guaranteed. However, these two algorithms cannot deal with coherent signals directly which happens, for example, in multipath propagation in real environment. In this case, preprocessing techniques such as spatial smoothing [12] and matrix reconstruction [13] methods are needed. These techniques have to reduce the rank of data covariance matrix as a precondition which means that the accuracy or the array aperture would be lost [14]. Furthermore, the resolution of MUSIC and ESPRIT decreases greatly when Signal-to-Noise Ratio (SNR) gets lower for both coherent and noncoherent signals cases.In this paper, we adopt the Stochastic Maximum Likelihood (SML) algorithm for DOA estimation. The SML algorithm is much more superior to MUSIC and ESPRIT. It can deal with small number of snapshots. It can also handle coherent signals without any preprocessing technique and the resolution is much higher than that of MUSIC and ESPRIT. However, the estimation of SML is a multidimensional nonlinear optimization problem. Therefore, its computational complexity is usually very high. That is the reason why the SML algorithm has not been adopted in practical systems.For multidimensional nonlinear optimization problem, many estimation algorithms have been proposed such as Alternating Projection (AP) [15], Expectation Maximization (EM) [16], Space Alternating Generalized EM (SAGE) [17], genetic algorithm [18], ant colony algorithm [19], and Particle Swarm Optimization (PSO) [20, 21]. They are all iterative techniques. The computational complexity of SML with these algorithms is still much higher than the estimation of MUSIC or ESPRIT. The main drawback of these algorithms is that they could be trapped into a local maximum.In this paper, we focus on how to reduce the computational complexity of SML estimation of DOA.For SML criterion, there are two versions. the first one is proposed by Bohme [22]. Many literatures [23, 24] have pointed out that, in the formulation of this criterion, an important constraint that the estimated signal covariance matrix must be nonnegative definite was omitted. As a result, the global solution of this SML criterion is not unique in some cases. We call this version conventional SML. With consideration of this constraint, [23] has derived a new SML criterion. This criterion shows excellent resolution of DOA estimation and its global solution is always unique. We call it Exact SML. The Exact SML criterion involves large amount of eigendecomposition. Its computational complexity is much higher than that of conventional SML and it is hard to exploit new efficient algorithms for the estimation.Based on the conventional SML criterion, firstly we impose the omitted constraint to get the solution space. Then, it is clear to distinguish whether the global solution is optimal or not. We find that the optimal or suboptimal solution of conventional SML does exist, but in some cases the optimal solution is not the global one. From large amount of simulation and deep analysis of the intrinsic relationship between DML and SML, we find that the reason is that the distinct part between DML and conventional SML criteria leads to the problem. Based upon the analysis above, firstly we propose a local Alternating Minimization (AM) search method which can find the local solution near/around the initial value. Since the solution of DML is always unique and it is near/around the true DOA (also the solution of Exact SML), the solution of DML becomes the best initial value to get the optimal or suboptimal solution of conventional SML criterion. Simulation results show the validity of the proposed algorithm. The computational complexity of the proposed algorithm is also reduced greatly.To reduce computational complexity further, we use the solution of MUSIC as initialization and then use the local AM method to find the optimal or suboptimal solution of conventional SML. From simulation results, we can find that this algorithm shows much higher resolution than MUSIC and its computational complexity is comparable to MUSIC. Thus, this proposed algorithm is of great practical value.The rest of this paper is organized as follows. In Section2, we introduce the problem of DOA and the formulation of DML and conventional SML. In Section 3, we show the problems of conventional SML and propose two algorithms to get the optimal or suboptimal solution of conventional SML criterion. Simulation results are shown in Section 4 and conclusion is drawn in Section 5.


## 2. System Model and Problem Formulations

Without loss of generality, consider that there arep sensors and q narrow-band sources far from the array, centered around a known frequency, impinging on the sensor array from distinct directions θ1,θ2,…,θq, with respect to a reference point, respectively.Note that the received signals may be coherent because of multipath propagation. In the case where there are signals coherent, the independent signal number is less thanq. The task of DOA estimation is to detect all q directions. Also note that here we assume that the signals are narrow-band. For wideband signals, the CSM algorithms [25] can be used as a preprocessing to change into the narrow-band.Furthermore, we assume that the number of sensors should be greater than the number of received signals; that is,p>q and all the sensors are omnidirectional and not coupled.


### 2.1. Problem Formulation of DOA

Using complex envelope representation, thep-dimensional vector received by the array can be expressed as(1)xt=∑k=1qaθkskt+nt,where sk(t) is the kth signal received at a certain reference point. n(t) is a p-dimensional noise vector. a(θ) is the “steering vector” of the array towards direction θ, which is presented as(2)aθ=a1θe-jω0τ1θ,…,apθe-jω0τpθT,where ai(θ) is the amplitude response of the ith sensor to a wave-front impinging from the direction θ. τi(θ) is the propagation delay between the ith sensor and the reference point. The superscript T denotes the transpose of a matrix.In the matrix notation, (1) can be rewritten as(3)xt=AΘst+nt,(4)AΘ=aθ1aθ2⋯aθq,(5)st=s1ts2t⋯sqtT,(6)Θ=θ1θ2⋯θq.Suppose that the received vectorsx(t) are sampled at N time instants (snapshots) t1,t2,…,tN and define the matrix of the sampled data as(7)X=xt1xt2⋯xtN.The problem of DOA estimation is to be stated as follows. Given the sampled data X, obtain a set of estimated directions(8)Θ^=θ^1θ^2⋯θ^qof θ1,θ2,…,θq.For DOA estimation, we have the following common assumptions.(A1)
The array configuration is known and anyp steering vectors for different q directions are linearly independent; that is, the matrix A(Θ) has full rank.(A2)
n(ti) are statistically independent samples from a complex Gaussian random vector with zero mean and the covariance matrix σ2Ip, where Ip is a p×p identity matrix and σ2 is an unknown real number.(A3)
s(ti) satisfy the condition(9)rank⁡S=rank⁡st1st2⋯stN=r≤q.S is the signal covariance matrix. In the case of r<q, the signals are coherent or fully correlated. s(ti) are independent of n(tj) for any i and j.(A4)
q<p, p,q, and r are known. The snapshots N should be greater than r.(A5)
p, q, and r satisfy the condition that a unique solution of DOA exists in the noise-free case. When the direction θ is expressed by a single real parameter, the sufficient condition of the uniqueness is given by q<2rp/(2r+1) and the necessary condition is given by q≤2rp/(2r+1) [26].


### 2.2. Maximum Likelihood Estimation

There are two ML algorithms. One is Deterministic ML, and the other is Stochastic ML. Difference between them lies in their models of signals. The solution of DML is always unique when a unique solution exists, while the solution of the conventional SML is not unique in some cases. Our first task is to reveal the reason why and how the problems happen in the conventional SML. As a contrast, we introduce these two algorithms briefly.


#### 2.2.1. Deterministic ML (DML)

The DML estimator is derived by imposing the following assumption on the signals in addition to (A1)–(A5):(A6D)
s(ti) are unknown deterministic parameters.The DML criterion according to [15] is given by(10)Θ^DML=arg⁡minΘ⁡LDMLΘ,LDMLΘ=tr⁡PA⊥R^,where(11)PA=AΘAHΘAΘ-1AHΘ,PA⊥=I-PA,R^=1NXXH.PA is the projection operator onto the space spanned by the columns of the matrix AΘ. H denotes the Hermitian conjugate. R^ is the sample covariance matrix of the sampled data.


#### 2.2.2. Stochastic ML (SML)

The SML criterion of DOA is formulated under the following assumption:(A6S)
s(ti) are statistically independent samples from a complex Gaussian random vector with zero mean and a certain covariance matrix S with rank⁡{S}=r.According to the assumptions (A2), (A3), and (A6S),x(t) is modeled as a p-dimensional complex Gaussian random vector with zero mean and the covariance matrix R:(12)R=ExtixtjHt=AΘSAHΘ+σ2Ip,where S is the signal covariance matrix and it must be nonnegative definite.The joint density function of the sampled dataX is given by(13)fSMLX=∏i=1M1det⁡πR×exp⁡xtiHR-1xti.Taking the log function of (13) and ignoring the constant term, the log-likelihood function of the model R in (12) with respect to the unknown parameters Θ, S, and σ2 is(14)LΘ,S,σ2=-Mln⁡det⁡R+1N∑i=1NxtiHR-1xti.The second term of (14) can be written into a trace form of matrix; then, (14) becomes(15)LΘ,S,σ2=-Mln⁡det⁡R+tr⁡R-1R^,where the sample covariance matrix R^ is given as above.The SML estimation of DOA is to be stated as the problem to findΘ which maximizes (15) under the following conditions:(C1)
Θ=θ1θ2⋯θq∈U. U is a set of all possible Θ determined by the array configuration.(C2)
S is nonnegative definite.(C3)
σ2 is a nonnegative real number.According to [22, 24, 27], when condition (C2) is omitted, the estimation of σ^2 and S^ is shown as follows:(16)σ^2=1p-qtr⁡PA⊥R^,S^=A⋆R^-σ^2IA⋆H,where(17)A⋆=AHΘAΘ-1AHΘ.Then, the conventional SML criterion [22] is shown as(18)Θ^Conv.=arg⁡minΘ⁡σ^2p-qdet⁡A⋆R^A.As [23, 24] have pointed out, the above conventional SML criterion is formulated by considering that S is a set of Hermitian matrices, and not a set of Hermitian positive (semi)definite matrices as it should be. In other words, condition (C2) is omitted. As a result, the global solution of (18) is not unique [23] in some cases.To overcome this defect, [23] has derived a new SML criterion with consideration of condition (C2). This criterion shows excellent resolution of DOA estimation and its global solution is always unique. It is called Exact SML. The Exact SML criterion involves large amount of eigendecomposition. Its computational complexity is much higher than that of conventional SML and it is hard to exploit new efficient algorithms for the estimation. Therefore, in this paper, we try to find out how these problems of the conventional SML happen and whether there are efficient methods to get the optimal or suboptimal solutions of SML.


## 2.1. Problem Formulation of DOA

Using complex envelope representation, thep-dimensional vector received by the array can be expressed as(1)xt=∑k=1qaθkskt+nt,where sk(t) is the kth signal received at a certain reference point. n(t) is a p-dimensional noise vector. a(θ) is the “steering vector” of the array towards direction θ, which is presented as(2)aθ=a1θe-jω0τ1θ,…,apθe-jω0τpθT,where ai(θ) is the amplitude response of the ith sensor to a wave-front impinging from the direction θ. τi(θ) is the propagation delay between the ith sensor and the reference point. The superscript T denotes the transpose of a matrix.In the matrix notation, (1) can be rewritten as(3)xt=AΘst+nt,(4)AΘ=aθ1aθ2⋯aθq,(5)st=s1ts2t⋯sqtT,(6)Θ=θ1θ2⋯θq.Suppose that the received vectorsx(t) are sampled at N time instants (snapshots) t1,t2,…,tN and define the matrix of the sampled data as(7)X=xt1xt2⋯xtN.The problem of DOA estimation is to be stated as follows. Given the sampled data X, obtain a set of estimated directions(8)Θ^=θ^1θ^2⋯θ^qof θ1,θ2,…,θq.For DOA estimation, we have the following common assumptions.(A1)
The array configuration is known and anyp steering vectors for different q directions are linearly independent; that is, the matrix A(Θ) has full rank.(A2)
n(ti) are statistically independent samples from a complex Gaussian random vector with zero mean and the covariance matrix σ2Ip, where Ip is a p×p identity matrix and σ2 is an unknown real number.(A3)
s(ti) satisfy the condition(9)rank⁡S=rank⁡st1st2⋯stN=r≤q.S is the signal covariance matrix. In the case of r<q, the signals are coherent or fully correlated. s(ti) are independent of n(tj) for any i and j.(A4)
q<p, p,q, and r are known. The snapshots N should be greater than r.(A5)
p, q, and r satisfy the condition that a unique solution of DOA exists in the noise-free case. When the direction θ is expressed by a single real parameter, the sufficient condition of the uniqueness is given by q<2rp/(2r+1) and the necessary condition is given by q≤2rp/(2r+1) [26].


## 2.2. Maximum Likelihood Estimation

There are two ML algorithms. One is Deterministic ML, and the other is Stochastic ML. Difference between them lies in their models of signals. The solution of DML is always unique when a unique solution exists, while the solution of the conventional SML is not unique in some cases. Our first task is to reveal the reason why and how the problems happen in the conventional SML. As a contrast, we introduce these two algorithms briefly.


### 2.2.1. Deterministic ML (DML)

The DML estimator is derived by imposing the following assumption on the signals in addition to (A1)–(A5):(A6D)
s(ti) are unknown deterministic parameters.The DML criterion according to [15] is given by(10)Θ^DML=arg⁡minΘ⁡LDMLΘ,LDMLΘ=tr⁡PA⊥R^,where(11)PA=AΘAHΘAΘ-1AHΘ,PA⊥=I-PA,R^=1NXXH.PA is the projection operator onto the space spanned by the columns of the matrix AΘ. H denotes the Hermitian conjugate. R^ is the sample covariance matrix of the sampled data.


### 2.2.2. Stochastic ML (SML)

The SML criterion of DOA is formulated under the following assumption:(A6S)
s(ti) are statistically independent samples from a complex Gaussian random vector with zero mean and a certain covariance matrix S with rank⁡{S}=r.According to the assumptions (A2), (A3), and (A6S),x(t) is modeled as a p-dimensional complex Gaussian random vector with zero mean and the covariance matrix R:(12)R=ExtixtjHt=AΘSAHΘ+σ2Ip,where S is the signal covariance matrix and it must be nonnegative definite.The joint density function of the sampled dataX is given by(13)fSMLX=∏i=1M1det⁡πR×exp⁡xtiHR-1xti.Taking the log function of (13) and ignoring the constant term, the log-likelihood function of the model R in (12) with respect to the unknown parameters Θ, S, and σ2 is(14)LΘ,S,σ2=-Mln⁡det⁡R+1N∑i=1NxtiHR-1xti.The second term of (14) can be written into a trace form of matrix; then, (14) becomes(15)LΘ,S,σ2=-Mln⁡det⁡R+tr⁡R-1R^,where the sample covariance matrix R^ is given as above.The SML estimation of DOA is to be stated as the problem to findΘ which maximizes (15) under the following conditions:(C1)
Θ=θ1θ2⋯θq∈U. U is a set of all possible Θ determined by the array configuration.(C2)
S is nonnegative definite.(C3)
σ2 is a nonnegative real number.According to [22, 24, 27], when condition (C2) is omitted, the estimation of σ^2 and S^ is shown as follows:(16)σ^2=1p-qtr⁡PA⊥R^,S^=A⋆R^-σ^2IA⋆H,where(17)A⋆=AHΘAΘ-1AHΘ.Then, the conventional SML criterion [22] is shown as(18)Θ^Conv.=arg⁡minΘ⁡σ^2p-qdet⁡A⋆R^A.As [23, 24] have pointed out, the above conventional SML criterion is formulated by considering that S is a set of Hermitian matrices, and not a set of Hermitian positive (semi)definite matrices as it should be. In other words, condition (C2) is omitted. As a result, the global solution of (18) is not unique [23] in some cases.To overcome this defect, [23] has derived a new SML criterion with consideration of condition (C2). This criterion shows excellent resolution of DOA estimation and its global solution is always unique. It is called Exact SML. The Exact SML criterion involves large amount of eigendecomposition. Its computational complexity is much higher than that of conventional SML and it is hard to exploit new efficient algorithms for the estimation. Therefore, in this paper, we try to find out how these problems of the conventional SML happen and whether there are efficient methods to get the optimal or suboptimal solutions of SML.


## 2.2.1. Deterministic ML (DML)

The DML estimator is derived by imposing the following assumption on the signals in addition to (A1)–(A5):(A6D)
s(ti) are unknown deterministic parameters.The DML criterion according to [15] is given by(10)Θ^DML=arg⁡minΘ⁡LDMLΘ,LDMLΘ=tr⁡PA⊥R^,where(11)PA=AΘAHΘAΘ-1AHΘ,PA⊥=I-PA,R^=1NXXH.PA is the projection operator onto the space spanned by the columns of the matrix AΘ. H denotes the Hermitian conjugate. R^ is the sample covariance matrix of the sampled data.


## 2.2.2. Stochastic ML (SML)

The SML criterion of DOA is formulated under the following assumption:(A6S)
s(ti) are statistically independent samples from a complex Gaussian random vector with zero mean and a certain covariance matrix S with rank⁡{S}=r.According to the assumptions (A2), (A3), and (A6S),x(t) is modeled as a p-dimensional complex Gaussian random vector with zero mean and the covariance matrix R:(12)R=ExtixtjHt=AΘSAHΘ+σ2Ip,where S is the signal covariance matrix and it must be nonnegative definite.The joint density function of the sampled dataX is given by(13)fSMLX=∏i=1M1det⁡πR×exp⁡xtiHR-1xti.Taking the log function of (13) and ignoring the constant term, the log-likelihood function of the model R in (12) with respect to the unknown parameters Θ, S, and σ2 is(14)LΘ,S,σ2=-Mln⁡det⁡R+1N∑i=1NxtiHR-1xti.The second term of (14) can be written into a trace form of matrix; then, (14) becomes(15)LΘ,S,σ2=-Mln⁡det⁡R+tr⁡R-1R^,where the sample covariance matrix R^ is given as above.The SML estimation of DOA is to be stated as the problem to findΘ which maximizes (15) under the following conditions:(C1)
Θ=θ1θ2⋯θq∈U. U is a set of all possible Θ determined by the array configuration.(C2)
S is nonnegative definite.(C3)
σ2 is a nonnegative real number.According to [22, 24, 27], when condition (C2) is omitted, the estimation of σ^2 and S^ is shown as follows:(16)σ^2=1p-qtr⁡PA⊥R^,S^=A⋆R^-σ^2IA⋆H,where(17)A⋆=AHΘAΘ-1AHΘ.Then, the conventional SML criterion [22] is shown as(18)Θ^Conv.=arg⁡minΘ⁡σ^2p-qdet⁡A⋆R^A.As [23, 24] have pointed out, the above conventional SML criterion is formulated by considering that S is a set of Hermitian matrices, and not a set of Hermitian positive (semi)definite matrices as it should be. In other words, condition (C2) is omitted. As a result, the global solution of (18) is not unique [23] in some cases.To overcome this defect, [23] has derived a new SML criterion with consideration of condition (C2). This criterion shows excellent resolution of DOA estimation and its global solution is always unique. It is called Exact SML. The Exact SML criterion involves large amount of eigendecomposition. Its computational complexity is much higher than that of conventional SML and it is hard to exploit new efficient algorithms for the estimation. Therefore, in this paper, we try to find out how these problems of the conventional SML happen and whether there are efficient methods to get the optimal or suboptimal solutions of SML.


## 3. Properties of Conventional SML and Efficient Algorithms

In this section, firstly we define a new model of observation data, and we express the DML and SML criterions in unified forms. After that we explain why the global solution of conventional SML is not unique in some cases. Then, we analyze the properties of all the local solutions of conventional SML. Finally we propose two effective and efficient algorithms to find the optimal or suboptimal solution of SML.


### 3.1. Unified Forms of DML and SML

Model (1) or (3) can be rewritten as follows:(19)xt=VSΘxSt+VNΘxNt,where VS(Θ) is a p×q matrix of which columns form an orthonormal system of the signal subspace, which is spanned by {a(θ1),a(θ2),…,a(θq)}; VN(Θ) is a p×(p-q) matrix of which columns form an orthonormal system of the noise subspace, which is the orthogonal complement of the signal subspace. xS(t) is the signal component of x(t) in the signal subspace, and xN(t) is the noise component of x(t) in the noise subspace.Using a square root matrix of a nonnegative definite matrix (for a nonnegative definite matrixB, the square root matrix B1/2 is defined as a matrix C, which satisfies B=CCH. The following notations are used: (B1/2)H=BH/2, (B1/2)-1=B-1/2, and ((B1/2)H)-1=((B1/2)-1)H=B-H/2, and we have (B-1)1/2=B-H/2), VS(Θ) is presented as(20)VSΘ=AΘAHΘAΘ-H/2.From the above definition, we have(21)VSHΘVSΘ=I,VNHΘVNΘ=I,VSΘVSHΘ=PA,VNΘVNHΘ=I-PA=PA⊥.From (19) and the definition of VS and VN, we have(22)RSS=VSHΘRVSΘ,RNN=VNHΘRVNΘ,where RSS and RNN are the covariance matrixes for the components of x(t) in the signal subspace and noise subspace, respectively.Define the unitary matrix(23)GΘ=VSΘVNΘ.Then, the covariance matrix R can be represented as(24)R=VSΘPVSHΘ+σ2Ip=GΘRSS00σ2Ip-qGHΘ,where P=(AH(Θ)A(Θ))H/2S(AH(Θ)A(Θ))1/2 and RSS=P+σ2Iq is a q×q Hermitian matrix. Since S must be nonnegative definite, P must be nonnegative definite. Then, condition (C2) becomes(25)RSS-σ2Iq≥0.The DML criterion can be rewritten as(26)Θ^DML=arg⁡minΘ⁡tr⁡PA⊥R^(27)=arg⁡minΘ⁡tr⁡VNΘVNHΘR^(28)=arg⁡minΘ⁡tr⁡VNHΘR^VNΘ(29)=arg⁡minΘ⁡tr⁡R^NN.Similarly, the SML criterion is rewritten as(30)Θ^Conv.=arg⁡minΘ⁡det⁡R^SS1p-qtr⁡R^NNp-q.


### 3.2. Problems of Conventional SML

Since in the formulation of conventional SML condition (C2) is omitted, in this subsection, firstly we have an important definition of solution space. Define(31)SR^=Θ∣Θ∈U,R^SSΘ-σ^2ΘI≥0.We call this area the SML solution space.Obviously, the global solution of (30) which locates in the solution space is the optimal solution of SML. The global solution which locates out of the solution space is not optimal.In (30), define(32)LConv.Θ=LSΘLNΘ,where(33)LSΘ=det⁡R^SSΘ,LNΘ=1p-qtr⁡R^NNp-q.Next, we analyze the nonuniqueness of global solution of conventional SML criterion in two cases.


#### 3.2.1. Noise-Free Case

Because of assumption (A5), a unique solution of DOA exists. As proved in the Appendix, the DML estimator has a unique solution in the noise-free case. Therefore, the DML estimator provides the true directions of arrivalΘ.In the noise-free case,Lconv.(Θ)=0 holds when LS(Θ)=0 or LN(Θ)=0. Since LN(Θ)=0 is equivalent to LDML(Θ)=0, a set of the true directions Θ is one of the solutions.Next, we consider the question if there existsΘ^ such that LS(Θ^)=0.Since(34)det⁡RSSΘ^=det⁡AHΘ^AΘ2det⁡Sdet⁡AHΘ^AΘ^,LS(Θ^)=0 holds when(35)det⁡S=0ordet⁡AHΘ^AΘ=0holds. In the former case, that is, the case of r<q, Lconv.(Θ^)≡0 holds for any Θ^. This indicates that the SML estimation fails completely. If σ2 is not zero but very small, then the same failure does not happen. Instead, the latter case, that is, det⁡{AH(Θ^)A(Θ)}=0, becomes a dominant factor which makes LS(Θ^) or Lconv.(Θ^) small.The remaining question is whether there existsΘ^ such that det⁡{AH(Θ^)A(Θ)}=0. To illustrate this question, we do numerical simulations. We consider the case of uniform linear arrays. The steering vector for a uniform linear array composed of omnidirectional sensors is represented as(36)aθ=1e-jϕθ⋯e-jp-1ϕθT,ϕθ=2πΔλsin⁡θ,where λ is the wavelength of signals impinging on the array and Δ is the sensor spacing between the adjacent two sensors. As a necessary condition that a unique direction θ is determined by the phase parameter ϕ, Δ≤λ/2 is imposed on the array configuration.Numerical solutions of (35) are shown in Figure 1, where the sensor spacing Δ=λ/2. In Figure 1(b), θ^3 is held fixed to −60°. Other parameters of simulations are shown in figure caption.Figure 1
Orbits of(θ^1,θ^2) for which LS(Θ^)=0.
(a)
p
=
3, q=2, θ1=0°, and θ2=8°
(b)
p
=
6, q=3, θ1=0°, θ2=8°, θ3=16°, and θ^3=-60°From Figure1, it can be confirmed that there exist an infinite number of Θ^ such that det⁡{AH(Θ^)A(Θ)}=0 for uniform linear arrays. We have to note that these are solutions of the conventional SML criterion in noise-free case, but obviously they are not the adequate solutions. From the simulation above, it can be stated that the conventional SML is not unique in the noise-free case.


#### 3.2.2. Noisy Case

In noisy case, to analyze the nonuniqueness of the global solution of conventional SML, we do simulations to plot all of the local solutions of it. In Figure2, we show two samples. The simulations are done with uniform linear arrays of omnidirectional sensors which is the same as above. The true DOA are 0° and 8°. The scenarios are described in captions. In Figure 2, the shadow area is the solution space according to (31). Obviously, the solution which locates in this area can guarantee condition (C2). The crosses represent all local solutions.Figure 2
Samples in the conventional SML estimation with uniform linear arrays of omnidirectional sensors:p=3, q=2, r=2, and N=10 in (a); p=4, q=2, r=1, and N=10 in (b). The true DOA are 0° and 8°.
(a)
The point A is the local solution closest to the true DOA while B is the global solution where SNR = 30 dB
(b)
There is no local solution in the solution space where SNR = 0 dBIn Figure2(a), the local solution point A locates in the solution space and it is the closest to the true DOA. Furthermore, we find that this solution coincides with the solution of Exact SML [23]. Therefore, point A is the optimal solution of SML. However, in fact, the local solution point B is the global solution of conventional SML. As a result, global search methods fail in this case of conventional SML estimation.In Figure2(b), point C is the solution of exact SML and there is no local solution of conventional SML in the solution space. It means that all the solutions can not guarantee condition (C2). In fact, this case rarely happens only when the SNR is low, for example, when SNR = 0 dB. Point E is the global solution of conventional SML although it is obviously not the adequate solution. Therefore, global search methods also fail in this case.Note that although point D locates out of the solution space, it is the nearest local solution to the true DOA. We call this local solution the suboptimal solution of SML. Comparing the criterions of DML and conventional SML, that is, (29) and (30), we can find that the minimization of DML criterion equals the minimization of LN(Θ). Therefore, the distinct part between DML and conventional SML criterion, that is, LS(Θ), leads to the problem. In fact, from Figure 2 we can find that all the local solutions except for the optimal and suboptimal solutions appear around the orbits of Θ for which LS(Θ^)=0 in noise-free case.


### 3.3. Exact SML Estimation

From the analysis above, we can know that the essential reason of the failure of conventional SML is that its criterion is formulated without considering condition (C2). The main idea of the exact formulation of SML is how to guarantee condition (C2) while maximizing the log-likelihood function (15).According to [23], the exact SML is shown as follows.Letl1(Θ)≥l2(Θ)≥⋯≥lq(Θ) be eigenvalues of RSS(Θ):(37)Θ^=arg⁡maxΘ⁡LηΘΘ,(38)LηΘΘ=-Nln⁡∏k=1ηΘlkΘ·σηΘ2Θp-ηΘ,where the index η(Θ) is found as a unique index in {0,1,…,q} which satisfies one of the following:(39)σηΘ2Θ≥l1ΘforηΘ=0,lηΘ>σηΘ2Θ≥lηΘ+1forηΘ=1,2,…,q-1,lqΘ>σηΘ2ΘforηΘ=qand σk2(Θ) for k=0,1,2,…,q⁡ are given as(40)σk2Θ=1p-ktr⁡R^-∑i=1kliΘ.Note that the indexη(Θ) can be considered as the rank of S which guarantees that S^ is nonnegative definite. In fact, the conventional SML criterion is formulated under the model that rank⁡{S}=q (this can be verified such that if we impose η(Θ)=q to (37), the exact SML criterion is the same as the conventional SML criterion). However, when SNR is low or snapshots are small (the failure case), the estimated S^ becomes coherent which can not guarantee that S^ is nonnegative definite. Therefore, the model that rank⁡{S}=q is not suitable in this case and there is only suboptimal solution for conventional SML criterion.


### 3.4. Efficient Algorithms for Conventional SML Estimation

From the analysis above, we can obtain the following two important properties of conventional SML criterion:(1)
Global search methods fail in conventional SML estimation.(2)
The optimal or suboptimal solution of conventional SML does exist in all local solutions.Therefore, the next problem is how to find the optimal or suboptimal solution of conventional SML. Since global search methods fail in DOA estimation of conventional SML, here we propose a local search method. This local search method is based on the Alternating Minimization (AM) algorithm.


#### 3.4.1. Local AM Algorithm

The local AM algorithm contains two phases:(1)
Initialization phase: determine a set of initial values of directions.(2)
Convergence phase: repeat the following updating process until all parameters are converged. At each updating process, let one parameter, sayθ^k, be variable and let all other parameters be held fixed. Find θ^k minimizing the criterion in (30) by one-dimensional local search with respect to θ^k. Change the index k of the parameter to be updated into (kmod⁡q)+1.Note that in the convergence phase the parameter is updated by one-dimensional local search. Therefore, the search result is a local minimum which is near/around the initial value. As a result, the initial value is very important. Furthermore, since local search method is used, the computational complexity of this process is low.


#### 3.4.2. Efficient Algorithms

As we have analyzed above, the solution of DML is unique (see the proof in the Appendix). The distinct part between DML and conventional SML criterions leads to the problem of conventional SML but it also makes the optimal solution of conventional SML have higher resolution than that of DML. It can be considered that the solution of DML is just near/around the optimal or suboptimal solution of SML. Then, the solution of DML becomes a best initial value.Therefore, for conventional SML estimation, we propose the first algorithm which uses the local AM method together with the solution of DML as initial value. The effectiveness of this proposed algorithm can be verified in the simulation section.For DML estimation, it is still a multidimensional nonlinear optimization problem. Its computational complexity is still much higher than that of MUSIC. Then, an inspiration comes to us that why do not we use the solution of MUSIC as initial value since the solution of MUSIC is unique and it is also near/around the optimal or suboptimal solution of conventional SML. Then, its computational complexity could be greatly decreased.Therefore, we propose the second algorithm which uses the local AM method together with the solution of MUSIC as initial value. Next we show the effectiveness and efficiency of the proposed two algorithms through simulations.


## 3.1. Unified Forms of DML and SML

Model (1) or (3) can be rewritten as follows:(19)xt=VSΘxSt+VNΘxNt,where VS(Θ) is a p×q matrix of which columns form an orthonormal system of the signal subspace, which is spanned by {a(θ1),a(θ2),…,a(θq)}; VN(Θ) is a p×(p-q) matrix of which columns form an orthonormal system of the noise subspace, which is the orthogonal complement of the signal subspace. xS(t) is the signal component of x(t) in the signal subspace, and xN(t) is the noise component of x(t) in the noise subspace.Using a square root matrix of a nonnegative definite matrix (for a nonnegative definite matrixB, the square root matrix B1/2 is defined as a matrix C, which satisfies B=CCH. The following notations are used: (B1/2)H=BH/2, (B1/2)-1=B-1/2, and ((B1/2)H)-1=((B1/2)-1)H=B-H/2, and we have (B-1)1/2=B-H/2), VS(Θ) is presented as(20)VSΘ=AΘAHΘAΘ-H/2.From the above definition, we have(21)VSHΘVSΘ=I,VNHΘVNΘ=I,VSΘVSHΘ=PA,VNΘVNHΘ=I-PA=PA⊥.From (19) and the definition of VS and VN, we have(22)RSS=VSHΘRVSΘ,RNN=VNHΘRVNΘ,where RSS and RNN are the covariance matrixes for the components of x(t) in the signal subspace and noise subspace, respectively.Define the unitary matrix(23)GΘ=VSΘVNΘ.Then, the covariance matrix R can be represented as(24)R=VSΘPVSHΘ+σ2Ip=GΘRSS00σ2Ip-qGHΘ,where P=(AH(Θ)A(Θ))H/2S(AH(Θ)A(Θ))1/2 and RSS=P+σ2Iq is a q×q Hermitian matrix. Since S must be nonnegative definite, P must be nonnegative definite. Then, condition (C2) becomes(25)RSS-σ2Iq≥0.The DML criterion can be rewritten as(26)Θ^DML=arg⁡minΘ⁡tr⁡PA⊥R^(27)=arg⁡minΘ⁡tr⁡VNΘVNHΘR^(28)=arg⁡minΘ⁡tr⁡VNHΘR^VNΘ(29)=arg⁡minΘ⁡tr⁡R^NN.Similarly, the SML criterion is rewritten as(30)Θ^Conv.=arg⁡minΘ⁡det⁡R^SS1p-qtr⁡R^NNp-q.


## 3.2. Problems of Conventional SML

Since in the formulation of conventional SML condition (C2) is omitted, in this subsection, firstly we have an important definition of solution space. Define(31)SR^=Θ∣Θ∈U,R^SSΘ-σ^2ΘI≥0.We call this area the SML solution space.Obviously, the global solution of (30) which locates in the solution space is the optimal solution of SML. The global solution which locates out of the solution space is not optimal.In (30), define(32)LConv.Θ=LSΘLNΘ,where(33)LSΘ=det⁡R^SSΘ,LNΘ=1p-qtr⁡R^NNp-q.Next, we analyze the nonuniqueness of global solution of conventional SML criterion in two cases.


### 3.2.1. Noise-Free Case

Because of assumption (A5), a unique solution of DOA exists. As proved in the Appendix, the DML estimator has a unique solution in the noise-free case. Therefore, the DML estimator provides the true directions of arrivalΘ.In the noise-free case,Lconv.(Θ)=0 holds when LS(Θ)=0 or LN(Θ)=0. Since LN(Θ)=0 is equivalent to LDML(Θ)=0, a set of the true directions Θ is one of the solutions.Next, we consider the question if there existsΘ^ such that LS(Θ^)=0.Since(34)det⁡RSSΘ^=det⁡AHΘ^AΘ2det⁡Sdet⁡AHΘ^AΘ^,LS(Θ^)=0 holds when(35)det⁡S=0ordet⁡AHΘ^AΘ=0holds. In the former case, that is, the case of r<q, Lconv.(Θ^)≡0 holds for any Θ^. This indicates that the SML estimation fails completely. If σ2 is not zero but very small, then the same failure does not happen. Instead, the latter case, that is, det⁡{AH(Θ^)A(Θ)}=0, becomes a dominant factor which makes LS(Θ^) or Lconv.(Θ^) small.The remaining question is whether there existsΘ^ such that det⁡{AH(Θ^)A(Θ)}=0. To illustrate this question, we do numerical simulations. We consider the case of uniform linear arrays. The steering vector for a uniform linear array composed of omnidirectional sensors is represented as(36)aθ=1e-jϕθ⋯e-jp-1ϕθT,ϕθ=2πΔλsin⁡θ,where λ is the wavelength of signals impinging on the array and Δ is the sensor spacing between the adjacent two sensors. As a necessary condition that a unique direction θ is determined by the phase parameter ϕ, Δ≤λ/2 is imposed on the array configuration.Numerical solutions of (35) are shown in Figure 1, where the sensor spacing Δ=λ/2. In Figure 1(b), θ^3 is held fixed to −60°. Other parameters of simulations are shown in figure caption.Figure 1
Orbits of(θ^1,θ^2) for which LS(Θ^)=0.
(a)
p
=
3, q=2, θ1=0°, and θ2=8°
(b)
p
=
6, q=3, θ1=0°, θ2=8°, θ3=16°, and θ^3=-60°From Figure1, it can be confirmed that there exist an infinite number of Θ^ such that det⁡{AH(Θ^)A(Θ)}=0 for uniform linear arrays. We have to note that these are solutions of the conventional SML criterion in noise-free case, but obviously they are not the adequate solutions. From the simulation above, it can be stated that the conventional SML is not unique in the noise-free case.


### 3.2.2. Noisy Case

In noisy case, to analyze the nonuniqueness of the global solution of conventional SML, we do simulations to plot all of the local solutions of it. In Figure2, we show two samples. The simulations are done with uniform linear arrays of omnidirectional sensors which is the same as above. The true DOA are 0° and 8°. The scenarios are described in captions. In Figure 2, the shadow area is the solution space according to (31). Obviously, the solution which locates in this area can guarantee condition (C2). The crosses represent all local solutions.Figure 2
Samples in the conventional SML estimation with uniform linear arrays of omnidirectional sensors:p=3, q=2, r=2, and N=10 in (a); p=4, q=2, r=1, and N=10 in (b). The true DOA are 0° and 8°.
(a)
The point A is the local solution closest to the true DOA while B is the global solution where SNR = 30 dB
(b)
There is no local solution in the solution space where SNR = 0 dBIn Figure2(a), the local solution point A locates in the solution space and it is the closest to the true DOA. Furthermore, we find that this solution coincides with the solution of Exact SML [23]. Therefore, point A is the optimal solution of SML. However, in fact, the local solution point B is the global solution of conventional SML. As a result, global search methods fail in this case of conventional SML estimation.In Figure2(b), point C is the solution of exact SML and there is no local solution of conventional SML in the solution space. It means that all the solutions can not guarantee condition (C2). In fact, this case rarely happens only when the SNR is low, for example, when SNR = 0 dB. Point E is the global solution of conventional SML although it is obviously not the adequate solution. Therefore, global search methods also fail in this case.Note that although point D locates out of the solution space, it is the nearest local solution to the true DOA. We call this local solution the suboptimal solution of SML. Comparing the criterions of DML and conventional SML, that is, (29) and (30), we can find that the minimization of DML criterion equals the minimization of LN(Θ). Therefore, the distinct part between DML and conventional SML criterion, that is, LS(Θ), leads to the problem. In fact, from Figure 2 we can find that all the local solutions except for the optimal and suboptimal solutions appear around the orbits of Θ for which LS(Θ^)=0 in noise-free case.


## 3.2.1. Noise-Free Case

Because of assumption (A5), a unique solution of DOA exists. As proved in the Appendix, the DML estimator has a unique solution in the noise-free case. Therefore, the DML estimator provides the true directions of arrivalΘ.In the noise-free case,Lconv.(Θ)=0 holds when LS(Θ)=0 or LN(Θ)=0. Since LN(Θ)=0 is equivalent to LDML(Θ)=0, a set of the true directions Θ is one of the solutions.Next, we consider the question if there existsΘ^ such that LS(Θ^)=0.Since(34)det⁡RSSΘ^=det⁡AHΘ^AΘ2det⁡Sdet⁡AHΘ^AΘ^,LS(Θ^)=0 holds when(35)det⁡S=0ordet⁡AHΘ^AΘ=0holds. In the former case, that is, the case of r<q, Lconv.(Θ^)≡0 holds for any Θ^. This indicates that the SML estimation fails completely. If σ2 is not zero but very small, then the same failure does not happen. Instead, the latter case, that is, det⁡{AH(Θ^)A(Θ)}=0, becomes a dominant factor which makes LS(Θ^) or Lconv.(Θ^) small.The remaining question is whether there existsΘ^ such that det⁡{AH(Θ^)A(Θ)}=0. To illustrate this question, we do numerical simulations. We consider the case of uniform linear arrays. The steering vector for a uniform linear array composed of omnidirectional sensors is represented as(36)aθ=1e-jϕθ⋯e-jp-1ϕθT,ϕθ=2πΔλsin⁡θ,where λ is the wavelength of signals impinging on the array and Δ is the sensor spacing between the adjacent two sensors. As a necessary condition that a unique direction θ is determined by the phase parameter ϕ, Δ≤λ/2 is imposed on the array configuration.Numerical solutions of (35) are shown in Figure 1, where the sensor spacing Δ=λ/2. In Figure 1(b), θ^3 is held fixed to −60°. Other parameters of simulations are shown in figure caption.Figure 1
Orbits of(θ^1,θ^2) for which LS(Θ^)=0.
(a)
p
=
3, q=2, θ1=0°, and θ2=8°
(b)
p
=
6, q=3, θ1=0°, θ2=8°, θ3=16°, and θ^3=-60°From Figure1, it can be confirmed that there exist an infinite number of Θ^ such that det⁡{AH(Θ^)A(Θ)}=0 for uniform linear arrays. We have to note that these are solutions of the conventional SML criterion in noise-free case, but obviously they are not the adequate solutions. From the simulation above, it can be stated that the conventional SML is not unique in the noise-free case.


## 3.2.2. Noisy Case

In noisy case, to analyze the nonuniqueness of the global solution of conventional SML, we do simulations to plot all of the local solutions of it. In Figure2, we show two samples. The simulations are done with uniform linear arrays of omnidirectional sensors which is the same as above. The true DOA are 0° and 8°. The scenarios are described in captions. In Figure 2, the shadow area is the solution space according to (31). Obviously, the solution which locates in this area can guarantee condition (C2). The crosses represent all local solutions.Figure 2
Samples in the conventional SML estimation with uniform linear arrays of omnidirectional sensors:p=3, q=2, r=2, and N=10 in (a); p=4, q=2, r=1, and N=10 in (b). The true DOA are 0° and 8°.
(a)
The point A is the local solution closest to the true DOA while B is the global solution where SNR = 30 dB
(b)
There is no local solution in the solution space where SNR = 0 dBIn Figure2(a), the local solution point A locates in the solution space and it is the closest to the true DOA. Furthermore, we find that this solution coincides with the solution of Exact SML [23]. Therefore, point A is the optimal solution of SML. However, in fact, the local solution point B is the global solution of conventional SML. As a result, global search methods fail in this case of conventional SML estimation.In Figure2(b), point C is the solution of exact SML and there is no local solution of conventional SML in the solution space. It means that all the solutions can not guarantee condition (C2). In fact, this case rarely happens only when the SNR is low, for example, when SNR = 0 dB. Point E is the global solution of conventional SML although it is obviously not the adequate solution. Therefore, global search methods also fail in this case.Note that although point D locates out of the solution space, it is the nearest local solution to the true DOA. We call this local solution the suboptimal solution of SML. Comparing the criterions of DML and conventional SML, that is, (29) and (30), we can find that the minimization of DML criterion equals the minimization of LN(Θ). Therefore, the distinct part between DML and conventional SML criterion, that is, LS(Θ), leads to the problem. In fact, from Figure 2 we can find that all the local solutions except for the optimal and suboptimal solutions appear around the orbits of Θ for which LS(Θ^)=0 in noise-free case.


## 3.3. Exact SML Estimation

From the analysis above, we can know that the essential reason of the failure of conventional SML is that its criterion is formulated without considering condition (C2). The main idea of the exact formulation of SML is how to guarantee condition (C2) while maximizing the log-likelihood function (15).According to [23], the exact SML is shown as follows.Letl1(Θ)≥l2(Θ)≥⋯≥lq(Θ) be eigenvalues of RSS(Θ):(37)Θ^=arg⁡maxΘ⁡LηΘΘ,(38)LηΘΘ=-Nln⁡∏k=1ηΘlkΘ·σηΘ2Θp-ηΘ,where the index η(Θ) is found as a unique index in {0,1,…,q} which satisfies one of the following:(39)σηΘ2Θ≥l1ΘforηΘ=0,lηΘ>σηΘ2Θ≥lηΘ+1forηΘ=1,2,…,q-1,lqΘ>σηΘ2ΘforηΘ=qand σk2(Θ) for k=0,1,2,…,q⁡ are given as(40)σk2Θ=1p-ktr⁡R^-∑i=1kliΘ.Note that the indexη(Θ) can be considered as the rank of S which guarantees that S^ is nonnegative definite. In fact, the conventional SML criterion is formulated under the model that rank⁡{S}=q (this can be verified such that if we impose η(Θ)=q to (37), the exact SML criterion is the same as the conventional SML criterion). However, when SNR is low or snapshots are small (the failure case), the estimated S^ becomes coherent which can not guarantee that S^ is nonnegative definite. Therefore, the model that rank⁡{S}=q is not suitable in this case and there is only suboptimal solution for conventional SML criterion.


## 3.4. Efficient Algorithms for Conventional SML Estimation

From the analysis above, we can obtain the following two important properties of conventional SML criterion:(1)
Global search methods fail in conventional SML estimation.(2)
The optimal or suboptimal solution of conventional SML does exist in all local solutions.Therefore, the next problem is how to find the optimal or suboptimal solution of conventional SML. Since global search methods fail in DOA estimation of conventional SML, here we propose a local search method. This local search method is based on the Alternating Minimization (AM) algorithm.


### 3.4.1. Local AM Algorithm

The local AM algorithm contains two phases:(1)
Initialization phase: determine a set of initial values of directions.(2)
Convergence phase: repeat the following updating process until all parameters are converged. At each updating process, let one parameter, sayθ^k, be variable and let all other parameters be held fixed. Find θ^k minimizing the criterion in (30) by one-dimensional local search with respect to θ^k. Change the index k of the parameter to be updated into (kmod⁡q)+1.Note that in the convergence phase the parameter is updated by one-dimensional local search. Therefore, the search result is a local minimum which is near/around the initial value. As a result, the initial value is very important. Furthermore, since local search method is used, the computational complexity of this process is low.


### 3.4.2. Efficient Algorithms

As we have analyzed above, the solution of DML is unique (see the proof in the Appendix). The distinct part between DML and conventional SML criterions leads to the problem of conventional SML but it also makes the optimal solution of conventional SML have higher resolution than that of DML. It can be considered that the solution of DML is just near/around the optimal or suboptimal solution of SML. Then, the solution of DML becomes a best initial value.Therefore, for conventional SML estimation, we propose the first algorithm which uses the local AM method together with the solution of DML as initial value. The effectiveness of this proposed algorithm can be verified in the simulation section.For DML estimation, it is still a multidimensional nonlinear optimization problem. Its computational complexity is still much higher than that of MUSIC. Then, an inspiration comes to us that why do not we use the solution of MUSIC as initial value since the solution of MUSIC is unique and it is also near/around the optimal or suboptimal solution of conventional SML. Then, its computational complexity could be greatly decreased.Therefore, we propose the second algorithm which uses the local AM method together with the solution of MUSIC as initial value. Next we show the effectiveness and efficiency of the proposed two algorithms through simulations.


## 3.4.1. Local AM Algorithm

The local AM algorithm contains two phases:(1)
Initialization phase: determine a set of initial values of directions.(2)
Convergence phase: repeat the following updating process until all parameters are converged. At each updating process, let one parameter, sayθ^k, be variable and let all other parameters be held fixed. Find θ^k minimizing the criterion in (30) by one-dimensional local search with respect to θ^k. Change the index k of the parameter to be updated into (kmod⁡q)+1.Note that in the convergence phase the parameter is updated by one-dimensional local search. Therefore, the search result is a local minimum which is near/around the initial value. As a result, the initial value is very important. Furthermore, since local search method is used, the computational complexity of this process is low.


## 3.4.2. Efficient Algorithms

As we have analyzed above, the solution of DML is unique (see the proof in the Appendix). The distinct part between DML and conventional SML criterions leads to the problem of conventional SML but it also makes the optimal solution of conventional SML have higher resolution than that of DML. It can be considered that the solution of DML is just near/around the optimal or suboptimal solution of SML. Then, the solution of DML becomes a best initial value.Therefore, for conventional SML estimation, we propose the first algorithm which uses the local AM method together with the solution of DML as initial value. The effectiveness of this proposed algorithm can be verified in the simulation section.For DML estimation, it is still a multidimensional nonlinear optimization problem. Its computational complexity is still much higher than that of MUSIC. Then, an inspiration comes to us that why do not we use the solution of MUSIC as initial value since the solution of MUSIC is unique and it is also near/around the optimal or suboptimal solution of conventional SML. Then, its computational complexity could be greatly decreased.Therefore, we propose the second algorithm which uses the local AM method together with the solution of MUSIC as initial value. Next we show the effectiveness and efficiency of the proposed two algorithms through simulations.


## 4. Simulations

In this section, simulations are shown to demonstrate the effectiveness and efficiency of the proposed algorithms by comparing with Exact SML and MUSIC.In the simulations, the array configuration is a uniform linear array composed of omnidirectional sensors, of which steering vector is represented as(41)aθ=1e-jϕθ⋯e-jp-1ϕθT,ϕθ=2πΔλsin⁡θ,where λ is the wavelength of signals impinging on the array and Δ is the sensor spacing between the adjacent two sensors. As a necessary condition that a unique direction θ is determined by the phase parameter ϕ, Δ≤λ/2 is imposed on the array configuration. In our simulations, Δ=λ/2.The SNR is defined as(42)SNRk=10log10⁡Eskt2σ2.All signals are assumed to have the identical SNR. The Root-Mean-Square-Error (RMSE) is defined as(43)RMSE=1qN∑k=1q∑n=1Nθ^k,n-θk2,where θ^k,n is the estimation of θk at the nth trial. We do simulations in Monte Carlo method and in each case we have done 100 trials.In all figures, “Exact SML” represents the Exact SML criterion and the estimation algorithm is the original AM algorithm [15]. “MUSIC” denotes the MUSIC algorithm [7]. Note that, for coherent cases, the spatial smoothing [12] method is used. “DML + Local” is the proposed algorithm one which uses DML solution as initial value and local AM method of the estimation for conventional SML criterion. In the estimation of DML, we use the AP algorithm [15]. “MUSIC + Local” represents the proposed algorithm two and the only difference to “DML + Local” is that it uses the estimation of MUSIC as initial value. “Operations” represents the summation of all the complex additions, subtractions, multiplications, and divisions in each algorithm, that is, the computational complexity.Figure3 is the case that all the received signals are independent. Figures 4 and 5 are the cases that there are signals coherent. The scenarios are described in each caption.Figure 3
For incoherent case:p=3, q=2, r=2, and N=300. The true DOA are 0° and 10°.
(a)
Resolution comparison between Exact SML, MUSIC, and proposed algorithms one and two
(b)
Comparison of computational complexity between Exact SML, MUSIC, and proposed algorithms one and twoFigure 4
For coherent case:p=4, q=2, r=1, and N=300. The true DOA are 0° and 10°.
(a)
Resolution comparison between Exact SML, MUSIC, and proposed algorithms one and two
(b)
Comparison of computational complexity between Exact SML, MUSIC, and proposed algorithms one and twoFigure 5
For coherent case:p=6, q=4, r=3, and N=300. The true DOA are 0° and 10° and 20° and 30°.
(a)
Resolution comparison between Exact SML, MUSIC, and proposed algorithms one and two
(b)
Comparison of computational complexity between Exact SML, MUSIC, and proposed algorithms one and twoFigures3(a), 4(a), and 5(a) show the resolution comparison of each algorithm. We can find the following:(1)
“Exact SML” has the highest resolution while “MUSIC” is the worst. The resolutions of “DML + Local” and “MUSIC + Local” are almost the same.(2)
The resolutions of “DML + Local” and “MUSIC + Local” become the same as “Exact SML” when SNR grows to about 10 or 15 dB.These points mean that the proposed two algorithms outperform the estimation of MUSIC in resolution and they can find the optimal solution of SML when SNR grows to about 10 or 15 dB.Figures3(b), 4(b), and 5(b) show the comparison of computational complexity between each algorithm. We can find the following:(1)
“Exact SML” has the highest computational complexity. Its computational complexity grows heavily when the number of received signals (q) becomes larger because it is a multidimensional nonlinear optimization problem and its computational complexity depends on the dimension while AM algorithm is used.(2)
“MUSIC” has the lowest computational complexity. Its computational complexity does not grow so dramatically as “Exact SML” whenq becomes larger because it is just a one-dimensional search problem.(3)
“DML + Local” also shows high computational complexity since the estimation of DML is also a multidimensional nonlinear optimization problem.(4)
The computational complexity of “MUSIC + Local” is comparable to “MUSIC” even whenq becomes larger because of the local search AM algorithm.The similar simulation results are observed in other scenarios. Therefore, we can conclude that the proposed two algorithms have good resolutions in DOA estimation which are better than that of MUSIC. In particular, the computational complexity of the proposed algorithm two (MUSIC + Local) is comparable to MUSIC.


## 5. Conclusions

This paper focused on how to reduce the computational complexity of SML estimation of DOA in positioning of nodes in WSNs. To find the optimal or suboptimal solution of SML, firstly, we proposed a local AM search method which can find a local minimum around the initial value. Then, we proposed two algorithms which use a local AM search method together with solution of DML and MUSIC as initial value, respectively. Simulation results have shown that the proposed two algorithms have better resolutions than that of MUSIC. Furthermore, the proposed algorithm which uses the local AM search method together with solution of MUSIC as initial value has comparable computational complexity to MUSIC. Next we will have practical application of this proposed algorithm in WSNs to check whether it could be applied in real systems and that is our following work.



---

*Source: 352012-2015-10-29.xml*