Sage Journals: Discover world-class research

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.

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 Section 2, 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 are p 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}, \dots, θ_{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 than q. 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, the p-dimensional vector received by the array can be expressed as

\begin{matrix} x (t) = \sum_{k = 1}^{q} a (θ_{k}) s_{k} (t) + n (t), \end{matrix}

(1)

where

s_{k} (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

\begin{matrix} a (θ) = {[a_{1} (θ) e^{- j ω_{0} τ_{1} (θ)}, \dots, a_{p} (θ) e^{- j ω_{0} τ_{p} (θ)}]}^{T}, \end{matrix}

(2)

where

a_{i} (θ)

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

\begin{matrix} x (t) = A (Θ) s (t) + n (t), \end{matrix}

(3)

\begin{matrix} A (Θ) = [\begin{bmatrix} a (θ_{1}) & a (θ_{2}) & \dots & a (θ_{q}) \end{bmatrix}], \end{matrix}

(4)

\begin{matrix} s (t) = {[\begin{bmatrix} s_{1} (t) & s_{2} (t) & \dots & s_{q} (t) \end{bmatrix}]}^{T}, \end{matrix}

(5)

\begin{matrix} Θ = \{\begin{Bmatrix} θ_{1} & θ_{2} & \dots & θ_{q} \end{Bmatrix}\} . \end{matrix}

(6)

Suppose that the received vectors $x (t)$ are sampled at N time instants (snapshots) $t_{1}, t_{2}, \dots, t_{N}$ and define the matrix of the sampled data as

\begin{matrix} X = [\begin{bmatrix} x (t_{1}) & x (t_{2}) & \dots & x (t_{N}) \end{bmatrix}] . \end{matrix}

(7)

The problem of DOA estimation is to be stated as follows. Given the sampled data X , obtain a set of estimated directions

\begin{matrix} \hat{Θ} = \{\begin{Bmatrix} {\hat{θ}}_{1} & {\hat{θ}}_{2} & \dots & {\hat{θ}}_{q} \end{Bmatrix}\} \end{matrix}

(8)

θ_{1}, θ_{2}, \dots, θ_{q}

For DOA estimation, we have the following common assumptions. (A1)

The array configuration is known and any p steering vectors for different q directions are linearly independent; that is, the matrix $A (Θ)$ has full rank.

(A2)

$n (t_{i})$ are statistically independent samples from a complex Gaussian random vector with zero mean and the covariance matrix $σ^{2} I_{p}$ , where $I_{p}$ is a $p \times p$ identity matrix and $σ^{2}$ is an unknown real number.

(A3)

$s (t_{i})$ satisfy the condition

\begin{matrix} rank [S] = rank [\begin{bmatrix} s (t_{1}) & s (t_{2}) & \dots & s (t_{N}) \end{bmatrix}] = r (\leq q) . \end{matrix}

(9)

S is the signal covariance matrix. In the case of $r < q$ , the signals are coherent or fully correlated. $s (t_{i})$ are independent of $n (t_{j})$ 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 < 2 r p / (2 r + 1)$ and the necessary condition is given by $q \leq 2 r p / (2 r + 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 (t_{i})$ are unknown deterministic parameters.

The DML criterion according to [15] is given by

\begin{matrix} {\hat{Θ}}_{D M L} = \arg \min_{Θ} L_{D M L} (Θ), \\ L_{D M L} (Θ) = tr \{P_{A}^{⊥} \hat{R}\}, \end{matrix}

(10)

where

\begin{matrix} P_{A} = A (Θ) {(A^{H} (Θ) A (Θ))}^{- 1} A^{H} (Θ), \\ P_{A}^{⊥} = I - P_{A}, \\ \hat{R} = \frac{1}{N} X X^{H} . \end{matrix}

(11)

P_{A}

is the projection operator onto the space spanned by the columns of the matrix

A (Θ)

. H denotes the Hermitian conjugate.

\hat{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 (t_{i})$ 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 :

\begin{matrix} R = E \{x (t_{i}) x {(t_{j})}^{H} (t)\} = A (Θ) S A^{H} (Θ) + σ^{2} I_{p}, \end{matrix}

(12)

where S is the signal covariance matrix and it must be nonnegative definite.

The joint density function of the sampled data X is given by

\begin{matrix} f_{S M L} (X) = \prod_{i = 1}^{M} \frac{1}{\det [π R]} \times \exp \{x {(t_{i})}^{H} R^{- 1} x (t_{i})\} . \end{matrix}

(13)

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}

\begin{matrix} L (Θ, S, σ^{2}) = - M (\ln \det \{R\} + \frac{1}{N} \sum_{i = 1}^{N} x {(t_{i})}^{H} R^{- 1} x (t_{i})) . \end{matrix}

(14)

The second term of (14) can be written into a trace form of matrix; then, (14) becomes

\begin{matrix} L (Θ, S, σ^{2}) = - M (\ln \det \{R\} + tr \{R^{- 1} \hat{R}\}), \end{matrix}

(15)

where the sample covariance matrix

\hat{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)

$Θ = \{\begin{Bmatrix} θ_{1} & θ_{2} & \dots & θ_{q} \end{Bmatrix}\} \in 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 ${\hat{σ}}^{2}$ and $\hat{S}$ is shown as follows:

\begin{matrix} {\hat{σ}}^{2} = \frac{1}{p - q} tr \{P_{A}^{⊥} \hat{R}\}, \\ \hat{S} = A^{⋆} (\hat{R} - {\hat{σ}}^{2} I) {(A^{⋆})}^{H}, \end{matrix}

(16)

where

\begin{matrix} A^{⋆} = {(A^{H} (Θ) A (Θ))}^{- 1} A^{H} (Θ) . \end{matrix}

(17)

Then, the conventional SML criterion [22] is shown as

\begin{matrix} {\hat{Θ}}_{C o n v .} = \arg \min_{Θ} \{{\hat{σ}}^{2 (p - q)} \det \{A^{⋆} \hat{R} A\}\} . \end{matrix}

(18)

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:

\begin{matrix} x (t) = V_{S} (Θ) x_{S} (t) + V_{N} (Θ) x_{N} (t), \end{matrix}

(19)

where

V_{S} (Θ)

is a

p \times q

matrix of which columns form an orthonormal system of the signal subspace, which is spanned by

{a (θ_{1}), a (θ_{2}), \dots, a (θ_{q})}

;

V_{N} (Θ)

is a

p \times (p - q)

matrix of which columns form an orthonormal system of the noise subspace, which is the orthogonal complement of the signal subspace.

x_{S} (t)

is the signal component of

x (t)

in the signal subspace, and

x_{N} (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 matrix B , the square root matrix $B^{1 / 2}$ is defined as a matrix C , which satisfies $B = C C^{H}$ . The following notations are used: $(B^{1 / 2})^{H} = B^{H / 2}$ , $(B^{1 / 2})^{- 1} = B^{- 1 / 2}$ , and $((B^{1 / 2})^{H})^{- 1} = ((B^{1 / 2})^{- 1})^{H} = B^{- H / 2}$ , and we have $(B^{- 1})^{1 / 2} = B^{- H / 2}$ ), $V_{S} (Θ)$ is presented as

\begin{matrix} V_{S} (Θ) = A (Θ) {(A^{H} (Θ) A (Θ))}^{- H / 2} . \end{matrix}

(20)

From the above definition, we have

\begin{matrix} V_{S}^{H} (Θ) V_{S} (Θ) = I, \\ V_{N}^{H} (Θ) V_{N} (Θ) = I, \\ V_{S} (Θ) V_{S}^{H} (Θ) = P_{A}, \\ V_{N} (Θ) V_{N}^{H} (Θ) = I - P_{A} = P_{A}^{⊥} . \end{matrix}

(21)

From (19) and the definition of

V_{S}

and

V_{N}

, we have

\begin{matrix} R_{S S} = V_{S}^{H} (Θ) R V_{S} (Θ), \\ R_{N N} = V_{N}^{H} (Θ) R V_{N} (Θ), \end{matrix}

(22)

where

R_{S S}

and

R_{N N}

are the covariance matrixes for the components of

x (t)

in the signal subspace and noise subspace, respectively.

Define the unitary matrix

\begin{matrix} G (Θ) = [\begin{bmatrix} V_{S} (Θ) & V_{N} (Θ) \end{bmatrix}] . \end{matrix}

(23)

Then, the covariance matrix R can be represented as

\begin{matrix} R = V_{S} (Θ) P V_{S}^{H} (Θ) + σ^{2} I_{p} = G (Θ) [\begin{bmatrix} R_{S S} & 0 \\ 0 & σ^{2} I_{p - q} \end{bmatrix}] G^{H} (Θ), \end{matrix}

(24)

where

P = (A^{H} (Θ) A (Θ))^{H / 2} S (A^{H} (Θ) A (Θ))^{1 / 2}

and

R_{S S} = P + σ^{2} I_{q}

is a

q \times q

Hermitian matrix. Since S must be nonnegative definite, P must be nonnegative definite. Then, condition (C2) becomes

\begin{matrix} R_{S S} - σ^{2} I_{q} \geq 0 . \end{matrix}

(25)

The DML criterion can be rewritten as

\begin{matrix} {\hat{Θ}}_{D M L} = \arg \min_{Θ} tr \{P_{A}^{⊥} \hat{R}\} \end{matrix}

(26)

\begin{matrix} = \arg \min_{Θ} tr \{V_{N} (Θ) V_{N}^{H} (Θ) \hat{R}\} \end{matrix}

(27)

\begin{matrix} = \arg \min_{Θ} tr \{V_{N}^{H} (Θ) \hat{R} V_{N} (Θ)\} \end{matrix}

(28)

\begin{matrix} = \arg \min_{Θ} tr \{{\hat{R}}_{N N}\} . \end{matrix}

(29)

Similarly, the SML criterion is rewritten as

\begin{matrix} {\hat{Θ}}_{C o n v .} = \arg \min_{Θ} (\det {\hat{R}}_{S S}) (\frac{1}{p - q} {(tr \{{\hat{R}}_{N N}\})}^{p - q}) . \end{matrix}

(30)

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

\begin{matrix} S_{\hat{R}} = \{Θ | Θ \in U, ({\hat{R}}_{S S} (Θ) - {\hat{σ}}^{2} (Θ) I) \geq 0\} . \end{matrix}

(31)

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

\begin{matrix} L_{C o n v .} (Θ) = L_{S} (Θ) L_{N} (Θ), \end{matrix}

(32)

where

\begin{matrix} L_{S} (Θ) = \det \{{\hat{R}}_{S S} (Θ)\}, \\ L_{N} (Θ) = (\frac{1}{p - q} {(tr \{{\hat{R}}_{N N}\})}^{p - q}) . \end{matrix}

(33)

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, $L_{c o n v .} (Θ) = 0$ holds when $L_{S} (Θ) = 0$ or $L_{N} (Θ) = 0$ . Since $L_{N} (Θ) = 0$ is equivalent to $L_{D M L} (Θ) = 0$ , a set of the true directions Θ is one of the solutions.

Next, we consider the question if there exists $\hat{Θ}$ such that $L_{S} (\hat{Θ}) = 0$ .

Since

\begin{matrix} \det R_{S S} (\hat{Θ}) = \frac{{|\det \{A^{H} (\hat{Θ}) A (Θ)\}|}^{2} \det S}{\det \{A^{H} (\hat{Θ}) A (\hat{Θ})\}}, \end{matrix}

(34)

L_{S} (\hat{Θ}) = 0

holds when

\begin{matrix} \det S = 0 or \\ \det \{A^{H} (\hat{Θ}) A (Θ)\} = 0 \end{matrix}

(35)

holds. In the former case, that is, the case of

r < q

L_{c o n v .} (\hat{Θ}) \equiv 0

holds for any

\hat{Θ}

. 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 {A^{H} (\hat{Θ}) A (Θ)} = 0

, becomes a dominant factor which makes

L_{S} (\hat{Θ})

L_{c o n v .} (\hat{Θ})

small.

The remaining question is whether there exists $\hat{Θ}$ such that $\det {A^{H} (\hat{Θ}) 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

\begin{matrix} a (θ) = {[\begin{bmatrix} 1 & e^{- j ϕ (θ)} & \dots & e^{- j (p - 1) ϕ (θ)} \end{bmatrix}]}^{T}, \\ ϕ (θ) = \frac{2 π Δ}{λ} \sin θ, \end{matrix}

(36)

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 ϕ,

Δ \leq λ / 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), ${\hat{θ}}_{3}$ is held fixed to −60°. Other parameters of simulations are shown in figure caption.

Figure 1

Orbits of $({\hat{θ}}_{1}, {\hat{θ}}_{2})$ for which $L_{S} (\hat{Θ}) = 0$ .

From Figure 1, it can be confirmed that there exist an infinite number of $\hat{Θ}$ such that $\det {A^{H} (\hat{Θ}) 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 Figure 2, 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°.

In Figure 2(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 Figure 2(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 $L_{N} (Θ)$ . Therefore, the distinct part between DML and conventional SML criterion, that is, $L_{S} (Θ)$ , 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 $L_{S} (\hat{Θ}) = 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.

Let $l_{1} (Θ) \geq l_{2} (Θ) \geq \dots \geq l_{q} (Θ)$ be eigenvalues of $R_{S S} (Θ)$ :

\begin{matrix} \hat{Θ} = \arg \max_{Θ} L_{η (Θ)} (Θ), \end{matrix}

(37)

\begin{matrix} L_{η (Θ)} (Θ) = - N \ln \{(\prod_{k = 1}^{η (Θ)} l_{k} (Θ)) \cdot {(σ_{η (Θ)}^{2} (Θ))}^{p - η (Θ)}\}, \end{matrix}

(38)

where the index

η (Θ)

is found as a unique index in

{0,1, \dots, q}

which satisfies one of the following:

\begin{matrix} σ_{η (Θ)}^{2} (Θ) \geq l_{1} (Θ) for η (Θ) = 0, \\ l_{η} (Θ) > σ_{η (Θ)}^{2} (Θ) \geq l_{η (Θ) + 1} for η (Θ) = 1,2, \dots, q - 1, \\ l_{q} (Θ) > σ_{η (Θ)}^{2} (Θ) for η (Θ) = q \end{matrix}

(39)

and

σ_{k}^{2} (Θ)

for

k = 0,1, 2, \dots, q

are given as

\begin{matrix} σ_{k}^{2} (Θ) = \frac{1}{p - k} (tr \{\hat{R}\} - \sum_{i = 1}^{k} l_{i} (Θ)) . \end{matrix}

(40)

Note that the index $η (Θ)$ can be considered as the rank of S which guarantees that $\hat{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 $\hat{S}$ becomes coherent which can not guarantee that $\hat{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 ${\hat{θ}}_{k}$ , be variable and let all other parameters be held fixed. Find ${\hat{θ}}_{k}$ minimizing the criterion in (30) by one-dimensional local search with respect to ${\hat{θ}}_{k}$ . Change the index k of the parameter to be updated into $(k \mod 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

\begin{matrix} a (θ) = {[\begin{bmatrix} 1 & e^{- j ϕ (θ)} & \dots & e^{- j (p - 1) ϕ (θ)} \end{bmatrix}]}^{T}, \\ ϕ (θ) = \frac{2 π Δ}{λ} \sin θ, \end{matrix}

(41)

Δ \leq λ / 2

is imposed on the array configuration. In our simulations,

Δ = λ / 2

The SNR is defined as

\begin{matrix} {S N R}_{k} = 10 \log_{10} \frac{E [{|s_{k} (t)|}^{2}]}{σ^{2}} . \end{matrix}

(42)

All signals are assumed to have the identical SNR. The Root-Mean-Square-Error (RMSE) is defined as

\begin{matrix} RMSE = \sqrt{\frac{1}{q N} \sum_{k = 1}^{q} \sum_{n = 1}^{N} {|{\hat{θ}}_{k, n} - θ_{k}|}^{2}}, \end{matrix}

(43)

where

{\hat{θ}}_{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.

Figure 3 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°.

Figure 4

For coherent case: $p = 4$ , $q = 2$ , $r = 1$ , and $N = 300$ . The true DOA are 0° and 10°.

Figure 5

For coherent case: $p = 6$ , $q = 4$ , $r = 3$ , and $N = 300$ . The true DOA are 0° and 10° and 20° and 30°.

Figures 3(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.

Figures 3(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” when q 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 when q 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.

Footnotes

Appendix

Conflict of Interests

The authors declare that there is no conflict of interests regarding the publication of this paper.

Acknowledgments

The authors would like to thank all the editors and reviewers for their valuable comments and suggestions. This paper is supported by the following funds: Fundamental Research Funds for the Central University, China, nos. 24720152047A and 15CX05025A, Shandong Provincial Natural Science Foundation, China, no. ZR2014FM017, and Science and Technology Development Plan of Huangdao District, Qingdao, China, no. 2014-1-45.

References

Zhang

Banavar

M. K.

Performance comparison of localization techniques for sequential WSN discovery

Proceedings of the Sensor Signal Processing for Defence (SSPD ′12)

September 2012

London, UK

1 5

10.1049/ic.2012.0120

Rezapour

T. Y.

Atani

R. E.

Abolghasemi

M. S.

Secure positioning for shipping containers in ports and terminals using WSN

Proceedings of the 11th International ISC Conference on Information Security and Cryptology (ISCISC ′14)

September 2014

Tehran, Iran

IEEE

10 14

10.1109/ISCISC.2014.6994014

Mao

Localization Algorithms and Strategies for Wireless Sensor Networks 2009

Information Science Reference

Boukerche

Oliveira

H. A. B. F.

Nakamura

E. F.

Loureiro

A. A. F.

Localization systems for wireless sensor networks

IEEE Wireless Communications 2007 14 6 6 12

10.1109/MWC.2007.4407221

2-s2.0-37249061709

Boukerche

Oliveira

H. A. B. F.

Nakamura

E. F.

Loureiro

A. A. F.

Localization systems for wireless sensor networks

IEEE Wireless Communications 2007 14 6 6 12

10.1109/mwc.2007.4407221

2-s2.0-37249061709

AlHajri

M. I.

Goian

Darweesh

AlMemari

Shubair

R. M.

Weruaga

Kulaib

A. R.

Hybrid RSS-DOA technique for enhanced WSN localization in a correlated environment

Proceedings of the International Conference on Information and Communication Technology Research (ICTRC ′15)

May 2015

Abu Dhabi, United Arab Emirates

IEEE

238 241

10.1109/ICTRC.2015.7156466

Schmidt

R. O.

Multiple emitter location and signal parameter estimation

IEEE Transactions on Antennas and Propagation 1986 34 3 276 280

2-s2.0-0022683359

Rao

B. D.

Hari

K. V. S.

Performance analysis of root-Music

IEEE Transactions on Acoustics, Speech, and Signal Processing 1989 37 12 1939 1949

10.1109/29.45540

2-s2.0-0024937039

Roy

Kailath

ESPRIT-estimation of signal parameters via rotational invariance techniques

IEEE Transactions on Acoustics Speech and Signal Processing 1989 37 7 984 995

10.1109/29.32276

10.

Kuchar

Tangemann

Bonek

A real-time DOA-based smart antenna processor

IEEE Transactions on Vehicular Technology 2002 51 6 1279 1293

10.1109/TVT.2002.801737

2-s2.0-0036879593

11.

Lavate

T. B.

Kokate

V. K.

Sapkal

A. M.

Performance analysis of MUSIC and ESPRIT DOA estimation algorithms for adaptive array smart antenna in mobile communication

Proceedings of the 2nd International Conference on Computer and Network Technology (ICCNT ′10)

April 2010

308 311

10.1109/iccnt.2010.45

2-s2.0-77954322613

12.

Williams

R. T.

Prasad

Mahalanabis

A. K.

Sibul

L. H.

An improved spatial smoothing technique for bearing estimation in a multipath environment

IEEE Transactions on Acoustics, Speech, and Signal Processing 1988 36 4 425 432

10.1109/29.1546

2-s2.0-0023996583

13.

Gao

S.-W.

Bao

Data-based matrix decomposition technique for high resolution array processing of coherent signals

Electronics Letters 1987 23 12 643 645

10.1049/el:19870460

2-s2.0-0023643907

14.

Duan

Huang

Zhou

Chen

Shi

A decorrelation algorithm based on virtual array extension

Proceedings of the 7th International ICST Conference on Communications and Networking in China (CHINACOM ′12)

August 2012

Kun Ming, China

IEEE

348 351

10.1109/chinacom.2012.6417505

2-s2.0-84874231837

15.

Ziskind

Wax

Maximum likelihood localization of multiple sources by alternating projection

IEEE Transactions on Acoustics, Speech, and Signal Processing 1988 36 10 1553 1560

10.1109/29.7543

ZBL0850.93749

2-s2.0-0024089986

16.

Nehorai

Maximum likelihood direction finding in spatially colored noise fields using sparse sensor arrays

IEEE Transactions on Signal Processing 2011 59 3 1048 1062

10.1109/tsp.2010.2098402

MR2797716

2-s2.0-79951640867

17.

Chung

P.-J.

Bohme

J. F.

Recursive EM and SAGE-inspired algorithms with application to DOA estimation

IEEE Transactions on Signal Processing 2005 53 8 2664 2677

10.1109/TSP.2005.850339

18.

M.-H.

Y.-L.

Improving the performance of GA-ML DOA estimator with a resampling scheme

Signal Processing 2004 84 10 1813 1822

10.1016/j.sigpro.2004.06.009

2-s2.0-4444298168

19.

Shi

Huang

Hou

Fast DOA estimation algorithm for MIMO sonar based on ant colony optimization

Journal of Systems Engineering and Electronics 2012 23 2 173 178

10.1109/jsee.2012.00022

2-s2.0-84863663513

20.

Wang

Zhao

Wang

Low complexity subspace fitting method for wideband signal location

Proceedings of the 5th IEEE and IFIP International Conference on Wireless and Optical Communications Networks (WOCN ′08)

May 2008

1 4

10.1109/wocn.2008.4542533

2-s2.0-51049097476

21.

Boccato

Krummenauer

Attux

Lopes

Application of natural computing algorithms to maximum likelihood estimation of direction of arrival

Signal Processing 2012 92 5 1338 1352

10.1016/j.sigpro.2011.12.004

2-s2.0-84855608542

22.

Bohme

J. F.

Estimation of spectral parameters of correlated signals in wavefields

Signal Processing 1986 11 4 329 337

10.1016/0165-1684(86)90075-7

23.

Chen

Suzuki

Exact formulation for stochastic ML estimation of DOA

IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences 2010 93 11 2141 2152

10.1587/transfun.e93.a.2141

2-s2.0-78049491719

24.

Stoica

Ottersten

Viberg

Moses

R. L.

Maximum likelihood array processing for stochastic coherent sources

IEEE Transactions on Signal Processing 1996 44 1 96 105

10.1109/78.482015

2-s2.0-0029752942

25.

Wang

Kaveh

Coherent signal-subspace processing for the detection and estimation of Angles of arrival of multiple wide-band sources

IEEE Transactions on Acoustics, Speech, and Signal Processing 1985 33 4 823 831

10.1109/tassp.1985.1164667

2-s2.0-0022103924

26.

Wax

Ziskind

On unique localization of multiple sources by passive sensor arrays

IEEE Transactions on Acoustics, Speech, and Signal Processing 1989 37 7 996 1000

10.1109/29.32277

2-s2.0-0024701599

27.

Wax

Detection and localization of multiple sources via the stochastic signals model

IEEE Transactions on Signal Processing 1991 39 11 2450 2456

10.1109/78.98000

2-s2.0-0026255021

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

Abstract

1. Introduction

2. System Model and Problem Formulations

2.1. Problem Formulation of DOA

2.2. Maximum Likelihood Estimation

2.2.1. Deterministic ML (DML)

2.2.2. Stochastic ML (SML)

3. Properties of Conventional SML and Efficient Algorithms

3.1. Unified Forms of DML and SML

3.2. Problems of Conventional SML

3.2.1. Noise-Free Case

3.2.2. Noisy Case

3.3. Exact SML Estimation

3.4. Efficient Algorithms for Conventional SML Estimation

3.4.1. Local AM Algorithm

3.4.2. Efficient Algorithms

4. Simulations

5. Conclusions

Footnotes

Appendix

Conflict of Interests

Acknowledgments

References