Adaptive Source Location Estimation Based on Compressed Sensing in Wireless Sensor Networks

Abstract

Source localization is an important problem in wireless sensor networks (WSNs). An exciting state-of-the-art algorithm for this problem is maximum likelihood (ML), which has sufficient spatial samples and consumes much energy. In this paper, an effective method based on compressed sensing (CS) is proposed for multiple source locations in received signal strength-wireless sensor networks (RSS-WSNs). This algorithm models unknown multiple source positions as a sparse vector by constructing redundant dictionaries. Thus, source parameters, such as source positions and energy, can be estimated by $ℓ_{1}$ -norm minimization. To speed up the algorithm, an effective construction of multiresolution dictionary is introduced. Furthermore, to improve the capacity of resolving two sources that are close to each other, the adaptive dictionary refinement and the optimization of the redundant dictionary arrangement (RDA) are utilized. Compared to ML methods, such as alternating projection, the CS algorithm can improve the resolution of multiple sources and reduce spatial samples of WSNs. The simulations results demonstrate the performance of this algorithm.

1. Introduction

Wireless sensor networks (WSNs) [1, 2] are widely applied in environmental surveillance, such as detection, location, and tracking of multiple targets. Because of limited sensing range, communication capacity, computation ability, and energy in WSNs, it is necessary to utilize a collaborative signal processing algorithm [3, 4]. Source localization estimation is an important task that WSNs need to perform, which is fundamental for an accurate tracking and motion analysis of the source. Depending on the physical mechanism, most source location algorithms in WSNs or sensor arrays can be classified into three kinds, namely, direction of arrival (DOA) measurement [5, 6], time difference of arrival (TDOA) [7, 8], and received signal strength or energy (RSS) [9– 11]. DOA is applicable when the source emits a coherent, narrowband signal, which is not suitable to broadband sources. TDOA needs accurate distributable synchronization methods in order to keep distributed sensor nodes sampling in a synchronized fashion. However, these characteristics of DOA and TDOA are not very practical for low-cost and low-power WSNs. RSS can effectively overcome the limitations of DOA and TDOA, thus increasingly applied in source localization [9, 11].

Recently, many approaches for source location in RSS-WSNs have been proposed. Maximum likelihood (ML) estimation [10] is one of the state-of-the-art methods in RSS-WSNs. A multiresolution search algorithm based on ML is found in [10]. Expectation maximization (EM) algorithms [12] and alternating projection (AP) algorithms [9] are used for multiple source localization. A ML that is based on quantized data and can reduce the communication of RSS-WSNs is introduced by [11].

To reduce the Cramer-Rao lower bound (CRLB) of estimation, these preceding algorithms require more nodes and must be laid out as in a uniform formation as possible. However, more energy would be consumed in communication among nodes as a result of more nodes. Under some conditions, such as underwater surveillance, nodes are too expensive to deploy densely [13, 14]. Accordingly, how to locate multiple sources when spatial samplings are few or when WSNs are deployed sparsely is still an open problem [2].

The proposition of compressed sensing (CS) [15, 16] can solve the contradiction between the accuracy of source location and energy consumption of networks. CS provides a framework in which signals are compressed while they are measured. The paper [17] introduces a new theory for distributed compressive sensing (DCS) to enable new distributed coding algorithms that exploit both intrasignal (for single sensor) and intersignal (for sensor networks) correlation structures, which can be used in WSNs for reducing measurements. A novel sample mechanism based on CS is proposed in [18], where working nodes are randomly chosen in space, while the others are “sleeping” to save energy. The sparse event detection in large WSNs is formulated in CS framework in [19]. Moreover, [20] derives the theoretic bound to detection and estimation for compressive measurements. Since CS can cut down intersensor communications, thus it is applied to source localization in DOA-WSNs and RSS-WSNs in [21, 22], respectively.

However, the calculation of source location is much more complex when the observation scene is larger. The low-complexity algorithms based on CS are not found in [18, 21, 22]. Motivated by this, we proposed a low-complexity source location based on CS. In this algorithm, unknown multiple source positions are represented as a sparse vector by constructing redundant dictionaries which are similar to [22]. The positions of sources are converted to the position of nonzero elements in a sparse vector, and sources are located by $ℓ_{1}$ norm minimization. The multiresolution dictionary is adopted to cut down the complexity of $ℓ_{1}$ norm minimization to reduce the complexity of source location in a large scene. To resolve two sources that are close to each other, a data-driven and adaptive dictionary refinement and the optimization of redundant dictionary arrangement (RDA) are utilized in this algorithm. In addition, the deployment of nodes impacts the accuracy of source location. This paper also focuses on this to find out which distribution of nodes is suitable to source localization based on CS.

In the following section, the model of source localization based on CS is introduced, and the sampling mechanism is also presented. A low-complexity and adaptive algorithm for multiple source localization is presented in Section 3. Extensive experiments have been conducted to compare the performance of CS-based algorithm with that of the existing AP method in Section 4 and where the impact from WSNs deployment is also discussed. Conclusions and future works are given in Section 5.

2. Problem Formulation

2.1. Sparse Signal Model

A new sensing paradigm called compressed sensing or compressed sampling [15, 16] (CS) goes against the common knowledge in data acquisition-Nyquist sampling theorem. The main idea of CS theory is that the system can compress the redundant information in Nyquist bandwidth while the system is measuring. Thus, CS can recover certain signals from far fewer samples than traditional methods and can reduce the quantity of systemic data.

The first principle of CS is sparsity. Sparsity expresses the fact that many natural signals S are sparse, or sparse when expressed in a convenient basis as follows:

S = \sum ψ_{n} θ_{n} = Ψ θ .

(1)

Here, Ψ consists of a group of orthonormal basis (such as a wavelet basis) named to represent a matrix and θ is the coefficient sequence of $S$ .

Original CS theory proposes that Ψ is orthonormal basis. Some signals are sparse or compressible when expressed in a tight frame [16] or a redundant dictionary [23]. The papers [23, 24] extend CS to the theory under the condition of redundant dictionaries.

Consider that M sensor nodes are deployed over a three-dimensional region and defined as ${\vec{r}}_{m}, m = 1,2, \dots, M$ that represents their respective locations. Consider also that there exist K isotropic acoustic sources in the same region and define their location vectors as ${\vec{r}}_{k}, k = 1,2, \dots, K$ . The geometry of densely and sparsely distributed WSNs is shown in Figures 1(a) and 1(b), respectively. The world coordinate system is defined as: X-, Y-, and Z-axis are mutually orthogonal, of which X- and Y-axis are set to be on the horizontal plane and Z-axis is perpendicular to the horizontal plane and points upward. According to the energy delay model of [11], the measurement of $m th$ node is denoted as

s_{m} = \sum_{k = 1}^{K} \frac{g_{m} p_{k}}{{‖ {\vec{r}}_{m} - {\vec{r}}_{k} ‖}_{2}^{α}} + w_{m},

(2)

where

{∥ ∙ ∥}_{2}

denotes the

ℓ_{2}

norm,

p_{k}

is the strength of the k-source,

g_{m}

is the received gain of the m-node, α is the attenuation exponent that is assumed to be 2~4, and

w_{m}

is the zero mean additive white Gaussian noise with variance

σ^{2}

Figure 1

The geometry of WSNs and sources.

The positions of sources are relatively sparse in comparison with a large observation scene, which is shown in Figure 1. Here, the redundant dictionaries are adopted to represent the received signals of RSS-WSNs. The redundant dictionary is essentially the geometric projection in space. In the form of this dictionary, the measurement of mth node is denoted as

s_{m} = ψ_{m} θ + w_{m},

(3)

where

ψ_{m}

consists of a redundant dictionary. Other parameters are defined as follows:

\begin{gathered} ψ_{m} = (h_{m 1}, h_{m 2}, \dots, h_{m N}), \\ h_{m n} = \frac{g_{m}}{{‖ {\vec{r}}_{m} - {\vec{r}}_{n} ‖}_{2}^{α}}, \\ θ = {(0, p_{1} \dots p_{k} \dots 0)}^{T}, \end{gathered}

(4)

where

m = 1,2, \dots, M, n = 1, 2, \dots, N

ψ_{m} \in R^{N}

, and

θ \in R^{N}

If the three-dimensional scene is divided into $N_{x} * N_{y} * N_{z} = N$ discrete subscenes, K sources are located in K subscenes. Ψ denotes the projection matrix from the nodes to the subscenes, which reflect the energy attenuation coefficients between the nodes and the subscenes in physics. The positions of the nonzero elements in θ are the positions of sources, the intensities of nonzero components are the power of the sources, and the number of nonzero components is the number of sources. Because K is much smaller than $N, θ$ is considered to be sparse. Thus, a sparse representation of received signal for single sensor is obtained.

One snap received signal is formulated in a matrix for RSS-WSNs with M nodes

\begin{matrix} (\begin{pmatrix} s_{1} \\ s_{2} \\ ⋮ \\ s_{M} \end{pmatrix}) & = (\begin{pmatrix} ψ_{1} \\ ψ_{2} \\ ⋮ \\ ψ_{M} \end{pmatrix}) * θ + (\begin{pmatrix} w_{1} \\ w_{2} \\ ⋮ \\ w_{M} \end{pmatrix}) \\ = (\begin{pmatrix} h_{11}, & h_{12}, & \dots & h_{1 n} & \dots & h_{1 N} \\ h_{21}, & h_{22}, & \dots & h_{2 n} & \dots & h_{2 N} \\ ⋮ & ⋮ & ⋱ & ⋱ & ⋮ \\ h_{M 1}, & h_{M 2}, & \dots & h_{1 n} & \dots & h_{M N} \end{pmatrix}) * θ + (\begin{pmatrix} w_{1} \\ w_{2} \\ ⋮ \\ w_{M} \end{pmatrix}), \end{matrix}

(5)

where

ψ_{m}

is defined as row vector of the redundant dictionary.

For simplicity, (5) can be written as

S = Ψ θ + W,

(6)

where

S = (s_{1}, s_{2}, \dots, s_{M}), S \in R^{M}

Ψ = {(ψ_{1}, ψ_{2}, \dots, ψ_{M})}^{T}, Ψ \in R^{M * N}

, and

W = (w_{1}, w_{2}, \dots, w_{M}), W \in R^{N}

The advantage of this sparse representation is that signal $θ$ contains both the locations and the intensities of sources. Thus, the parametric estimation of the sources can be converted into the recovery of $θ$ . However, a large observation scene would mean that the length of θ is so long that the recovery is excessively complex.

2.2. CS-Based Sampling in RSS-WSNs

As mentioned above, S is expanded in redundant dictionary $Ψ$ , and the coefficient sequence θ is sparse. If Φ denotes WSNs' sampling mechanism, the measurement Z can be expressed as follows:

Z = Φ S + W_{1} = Φ Ψ θ + W_{1},

(7)

where

Z \in R^{N_{S}}

Φ \in R^{N_{S} * M}, N_{S} \leq M

, and

W_{1} = Φ W \in R^{N_{S}}

Another important principle of CS theory is incoherent sampling. Incoherent sampling demands the coherence between sampling matrix (Φ) and representing matrix (Ψ) to be as small as possible. Usually, the coherence $μ (Φ, Ψ)$ between $Φ$ and $Ψ$ is defined as [25]

μ (Φ, Ψ) = \sqrt{N} \max_{1 \leq k \leq N_{S}, 1 \leq j \leq N} | 〈 φ_{k}, ψ_{j} 〉 |,

(8)

where

Φ = [φ_{1}, φ_{2}, \dots, φ_{N_{S}}]^{T}

φ_{k}

is row vector of Φ, and

Ψ = [ψ_{1}, ψ_{2}, \dots, ψ_{N}]

ψ_{j}

is column vector of

Ψ \cdot μ (Φ, Ψ) \in [1, \sqrt{N}]

According to the measurement Z, $ℓ_{1},$ norm minimization can stably recover θ when the number of measurements exceeds [25]

N_{S} \geq C \cdot μ^{2} (Φ, Ψ) \cdot K \log N,

(9)

where

N_{S}

denotes the number of measurements and C is a known (small) constant which depends on the recovery precision.

If Ψ extends from an orthonormal basis to redundant dictionary, it is necessary to give restrictions to $Φ$ and $Ψ$ . A random sampling matrix needs to satisfy [23]

P (| {‖ Φ v ‖}_{2}^{2} - {‖ v ‖}_{2}^{2} | \geq ε {‖ v ‖}_{2}^{2}) \leq 2 e^{- c N_{s} ε^{2} / 2} .

(10)

Here, $v$ is any vector with the length of M, $ε \in (0,1 / 3)$ and $c > 0$ . The intercoherence of $Ψ$ denotes $μ (Ψ) = \max_{1 \leq i, j \leq N, i \neq j} | 〈 ψ_{i}, ψ_{j} 〉 |$ and $ψ_{n} (n = 1, 2, \dots, N)$ are the column vectors. When $K - 1 \leq 1 / 16 μ^{- 1}$ , the $ℓ_{1}$ minimization can recover θ with a probability of at least $1 - e^{- t}$ from the measurements, whose numbers satisfy [23]

N_{S} \geq C_{1} (K \log (\frac{N}{K}) + C_{2} + t),

(11)

where

C_{1}, C_{2}, t

are constants that are related with the restricted isometry principle (RIP) of a sampling matrix.

In this study, the Bernoulli matrix is adopted as the sampling matrix that satisfies the restriction of (10). More details are shown in [23]. The variable of Bernoulli matrix $ϕ_{k, m}$ is shown as follows:

\begin{gathered} ϕ_{k, m} = {\begin{cases} 1 & with probability 0.5, \\ 0 & with probability 0.5, \end{cases} \\ k = 1,2, \dots, N_{s}, m = 1,2, \dots, M, N_{S} \leq M . \end{gathered}

(12)

Φ consists of

ϕ_{k, m}

, and the column vectors of Φ are irrelevant with each other. In physics, 0 and 1 mean that the nodes are disabled and enabled to receive the data, respectively. The number of rows in Φ is the sampling number

N_{S}

. Because this study focuses on the algorithm of source localization in sparse RSS-WSNs, the sampling number is assumed to be

N_{S} = M

, which means full samplings in space.

According to (9) and (11), θ can be recovered by minimizing $ℓ_{0}$ norm, which can be expressed in

\hat{θ} = \arg \min_{θ \in R^{N}} {‖ θ ‖}_{0}, s . t . {‖ Z - Φ Ψ θ ‖}_{2} \leq ε,

(13)

where

{∥ ∙ ∥}_{0}

denote the

ℓ_{0}

norm.

Unfortunately, solving this $ℓ_{0}$ minimization is a NP problem and imposes combinatorial complexity. Therefore, some simplifications are used. [8, 16] proposes solving $ℓ_{1}$ minimization instead of $ℓ_{0}$ minimization

\hat{θ} = \arg \min_{θ \in R^{N}} {‖ θ ‖}_{1}, s . t . {‖ Z - Φ Ψ θ ‖}_{2} \leq ε .

(14)

The optimization (14) is known as basis pursuit (BP). When the measurements contain noise, BP may be represented as the dual problem [8]

\hat{θ} = \arg \min_{θ \in R^{N}} ({‖ Z - Φ Ψ θ ‖}_{2} + λ {‖ θ ‖}_{1}),

(15)

where

{∥ ∙ ∥}_{1}

denotes the

ℓ_{1}

norm and λ is the coefficient that describes the tradeoff between denoising and retaining sparsity.

3. CS-Based Source Localization

3.1. Multiresolution Redundant Dictionary

A redundant dictionary is related to the grid number at each dimension ( $N_{x}, N_{y}, N_{z}$ ) and the dictionary arrangement. If $N_{x} * N_{y} * N_{z} = N$ is assumed to be big, theoretical localization accuracy is increased, but the computation cost of signal recovery is extremely high. For a signal with the length of $N$ , the optimization could be evaluated using $O (N)$ operations. If the optimization is divided into β steps, in which each recovery needs $β * O (N^{1 / β})$ operations, such an approach could reduce the overall complexity of CS-based source localization from $O (N)$ to $β * O (N^{1 / β})$ . Assuming $N_{x} = N_{y} = N_{z} = 1000$ , $β = 3$ , the complexity would be reduced from $O (1 0^{9})$ to $3$ * $O (1 0^{3})$ . Thus a multiresolution redundant dictionary is suitable for low-powered RSS-WSNs.

According to CS sample principle, θ could be stably recovered by $ℓ_{1}$ norm minimization when the number of measurements must satisfy (11). Assuming $C = 1$ and $μ (Φ, Ψ) = 0.75$ , the relationship between $N_{S}$ and the high bound of $N$ for different K is shown in Figure 2. If the sample number is fixed, such as $N_{S} = 9$ , the length of θ must not exceed 25 for $K = 5, 54$ for $K = 4, 207$ for $K = 3, 2980$ for $K = 2$ , and $8.9 \times 1 0^{6}$ for $K = 1$ . Too long θ would go against CS sample principle and lead to poor estimation for few spatial samples. Therefore, the multiresolution redundant dictionary could effectively control the length of θ to address this problem.

Figure 2

Relationship between sample number and the high bound of N.

As mentioned above, a multiresolution redundant dictionary can sharply reduce the length of θ and the computation for a large-scale scene. Figure 3 shows the process of constructing a multiresolution dictionary. Firstly, the initial resolution is set to be low, and the sources are located in a certain grid or several grids by signal recovery. Secondly, the grid or the combination of several grids is considered as new space and is used to build a new redundant dictionary, which has smaller grids than before. Then sources are located in specified smaller grids by signal recovery. Thirdly, the combination of these smaller grids is considered as another new space, and the redundant dictionary is updated. Then the process is repeated until the minimum grid is up to resolution requirement.

Figure 3

Multiresolution redundant dictionary.

For the same scene, iterative times of recovery would decrease with the increasing of N when constructing a redundant dictionary. A bigger N is likely to disobey the CS sample principle. Therefore, it is necessary to ensure proper N to make a tradeoff between iterative times and incoherence and a tradeoff between iterative times and recovery precision.

3.2. Adaptive Dictionary Refinement

The spatial subdivision schemes of dictionary can be divided into uniform and adaptive ones. The length of each grid is equal for uniform schemes, while the length of each grid is weighted by the data-driven criteria for adaptive schemes. In this study, both schemes are adopted in the localization algorithm. Because of none prior source location, the initial dictionary is made up of uniform grids. Then sources may be located in one or several interested and coarse grids, which would be adaptively partitioned into many subgrids. The numbers of subgrids are weighted by the recovery signal ${\hat{θ}}^{iter - 1}$ of previous iteration. There are $N^{iter} (j)$ subgrids in jth interested grid, given by

N^{iter} (j) = w^{iter} (j) * N,

(16)

where N denotes the total number of subgrids in the current iteration. The weighted values

w^{iter} (j)

can be calculated by the previous

{\hat{θ}}^{iter - 1}

, expressed as

w^{iter} (j) = \frac{{\hat{θ}}^{iter - 1} (j)}{\sum_{j = 1}^{N} {\hat{θ}}^{iter - 1} (j)} .

(17)

The elements of

{\hat{θ}}^{iter - 1}

should be preprocessed by

{\hat{θ}}^{iter - 1} (j) = {\begin{cases} {\hat{θ}}^{iter - 1} (j), & {\hat{θ}}^{iter - 1} (j) \geq 0, \\ 0, & otherwise . \end{cases}

(18)

Figure 4 shows the procedure of adaptive grid refinement in the iterations. First iteration adopts the uniform grid centers, and the sources are located coarsely in some grids (Figure 4(a)). Then these grids are split into subgrids with different resolutions depending on the estimated intensity from them. And the grid is more close to the source, which could have higher resolution, shown in Figures 4(b), 4(c), and 4(d).

Figure 4

Adaptive grid refinement in the iterations: the observation scene is 1000*1000*100.

3.3. Redundant Dictionary Arrangement

In this study, continuous coordinate indexing is utilized to arrange grids of redundant dictionary. The world Cartesian coordinates system is defined in Section 2.2. Additionally, we denote local axis as 1st-, 2nd-, and 3rd-axis depending on the indexing order, which are shown in Figure 5.

Figure 5

Continuous coordinate indexing of redundant dictionary in local coordinate system.

The indexing in local coordinate system has the following steps. Firstly, a 3rd-axis coordinate is fixed. Then the grids are arranged from small 1st-axis coordinate to big one on the plane that consists of 1st- and 2nd-axis, until all 2nd-axis coordinates are arranged. Secondly, turn to another plane that consists of 1st- and 2nd-axis. Then arrange all grids in this plane in the same manner as the first step. Finally, all 3rd-axis coordinates are arranged, and all grids are arranged (Figure 5). In other words, this redundant dictionary is indexed from 1st-axis to 2nd-axis, then to 3rd-axis. And the distance between neighbors in 1st, 2^nd, and 3rd-axis is 1, $N_{1 st-axis}$ , and $N_{1 st-axis} * N_{2 nd-axis}$ , respectively. Note that $N_{1 st-axis}$ , $N_{2 nd-axis}$ , and $N_{3 rd-axis}$ denote the number of grids in three axis, respectively.

After sensors are deployed randomly in the interest of scene, there are multiple sources to be located. The arrangement of a redundant dictionary impacts the capacity to resolve multiple sources. For the same three-dimensional scene, redundant dictionary could be indexed in six manners, called redundant dictionary arrangement (RDA), in the form of $κ$ . RDA is essentially how to define 1st-, 2nd-, and 3rd-axis as X-, Y-, and Z-axis, respectively. There are six definitions shown in Figure 6. The distances between neighbors in X-, Y-, and Z-axis $(Δ N_{x (κ)}^{}$ , $Δ N_{y (κ)}^{}$ , $Δ N_{z (κ)}^{})$ under different RDAs are shown in Table 1.

Table 1

Six RDAs.

κ	Indexing order $1 st \to 2 nd \to 3 rd$	$Δ N_{x (κ)}^{}$	$Δ N_{y (κ)}^{}$	$Δ N_{z (κ)}^{}$
1	$Z \to Y \to X$	$N_{y} N_{z}$	$N_{z}$	1
2	$Y \to Z \to X$	$N_{y} N_{z}$	1	$N_{y}$
3	$X \to Z \to Y$	1	$N_{x} N_{z}$	$N_{x}$
4	$Z \to X \to Y$	$N_{z}$	$N_{x} N_{z}$	1
5	$Y \to X \to Z$	$N_{y}$	1	$N_{x} N_{y}$
6	$X \to Y \to Z$	1	$N_{x}$	$N_{x} N_{y}$

Figure 6

Six definitions of X-, Y-, and Z-axis.

Under certain form of RDA (κ), $Δ N_{κ} (k, j)$ denotes the distance between two arbitrary sources (k- and j-source) in $θ$ . (19) is used to calculate $Δ N_{κ} (k, j)$

\begin{matrix} Δ N_{κ} (k, j) & = | Δ N_{x (κ)}^{} {[\frac{(X_{k} - X_{j})}{Δ x}]}_{I} | \\ + | Δ N_{y (κ)}^{} {[\frac{(Y_{k} - Y_{j})}{Δ y}]}_{I} | \\ + | Δ N_{z (κ)}^{} {[\frac{(Z_{k} - Z_{j})}{Δ z}]}_{I} |, \end{matrix}

(19)

where

(X_{k}, Y_{k}, Z_{k})

and

(X_{j}, Y_{j}, Z_{j})

are the positions of k- and j-source, respectively.

Δ x

Δ y,

and

Δ z

is the grid unit of

X -

Y -

, and

Z -

axis, respectively, and

[A]_{I}

denotes the nearest integers less than or equal to

A

The optimization of RDA is essentially how to refine the direction of X-, Y-, and Z-axis in order to make the distance of two close sources in θ as large as possible, which is shown in

\hat{κ} = \arg \max_{κ} {\min_{1 \leq k \neq j \leq K} [Δ N_{κ} (k, j)]},

(20)

where

\min_{1 \leq k \neq j \leq K} [Δ N_{κ} (k, j)]

is the minimal distance of K sources.

For instance two isotropic acoustic sources have been coarsely estimated and found that their distance has one grid in X-axis after previous iteration. This means that ${[(X_{1} - X_{2}) / Δ x]}_{I} = 1$ and $Y_{1} = Y_{2}, Z_{1} = Z_{2}$ . If $κ = 3, 6, Δ N = 1;$ if $κ = 4, 5, Δ N = N_{z}$ or $N_{y}$ ; if $κ = 1, 2, Δ N = N_{y} N_{z}$ . Figure 7 shows the relative positions of these two sources under different RDAs. Theoretically speaking, it is more accurate to recover the signal whose nonzero components distance is $N_{y} N_{z}$ than the signal whose nonzero components distance is 1, especially when this signal is sparse in the form of a redundant dictionary. Accordingly, the optimization of RDA can improve the ability to distinguish close sources.

Figure 7

Two sources are located in θ.

3.4. Signal Recovery Algorithm

It is well known that the signal can be recovered by nonconvex optimization, convex optimization, and statistics optimization. Orthogonal matching pursuit (OMP) [6] is a typical nonconvex optimization, which has a high calculation efficiency. And least absolute shrinkage and selection operator (LASSO) [7] is a typical convex method, that has a high recovery accuracy but the calculation is more complex than OMP. Statistics optimization, such as sparse Bayesian learning [26], has a higher calculation efficiency than convex algorithm and a higher recovery accuracy than nonconvex algorithm. Accordingly, sparse Bayesian learning [26] is utilized to locate sources.

In sparse Bayesian learning, a three-stage hierarchical form of Laplace priors is utilized to model the sparsity of the unknown signal $θ$ , and the solving of (14) or (15) is done by maximizing posterior probability. θ is assumed to satisfy the following equation:

p (θ | λ_{L}) = \frac{{λ_{L}}^{N / 2}}{2^{N}} \exp (- \sqrt{λ_{L}} {‖ θ ‖}_{1}),

(21)

where

λ_{L}

is the coefficient of Laplace priors. The Laplace priors mean that θ submits to Gauss distribution, whose mean is zero and variance follows the Gamma distribution.

λ_{L}

is essentially the coefficient of Gamma distribution, which impacts

p (θ | λ_{L})

and recovery accuracy.

3.5. CS-Based Source Localization Procedure

The proposed CS-based source localization algorithm is summarized in Algorithm 1.

Algorithm 1: CS-based source localization algorithm.

Input: The positions of randomly deployed sensors and their measurements Z.

Initialization: Construct the sampling matrix $Φ$ . The initial search space is the three-dimensional scene covered by RSS-WSNs. The RDA κ is arbitrary. $θ = 0$ , the set of nonzero elements in θ is null, and the iterative times is zero.

Step $1$ : The process of estimation: $i t e r \leftarrow i t e r + 1$ .

(a) Construct redundant dictionary depending on the search space.

(b) ${\hat{θ}}^{iter} = \arg \min_{θ \in R^{N}} ({∥ Z - Φ Ψ θ ∥}_{2} + λ {∥ θ ∥}_{1})$ . (More details in Section 3.4.)

${\hat{θ}}^{iter} (j) = {\begin{smallmatrix} {\hat{θ}}^{iter} (j), & {\hat{θ}}^{iter} (j) \geq τ \geq 0, \\ 0, & otherwise, \end{smallmatrix}$ τ is the threshold to determine whether an element is a nonzero element.

(c) Adaptive dictionary refinement based on $w^{iter + 1} (j) = {\hat{θ}}^{iter} (j) / \sum_{j = 1}^{N} {\hat{θ}}^{iter} (j)$ .

$Λ^{iter} = {j | {\hat{θ}}^{iter} (j) > τ}$ , $K = {∥ Λ^{iter} ∥}_{0}$ . Select the center of the grid ${Λ_{k}}^{iter}$ as the source positions ${\vec{\hat{r}}}_{k}^{}^{iter}, k = 1,2, \dots, K$ . (More details in Section 3.2.)

(d) If $K = 1$ , RDA is unchanged.

If $K > 1$ , optimize RDA for the next iteration. $\hat{κ} = \arg \max_{κ} {\min_{1 \leq k \neq j \leq K} [Δ N_{κ} (k, j)]}$ . (More details in Section 3.3.)

Step $2$ : Output ${\vec{\hat{r}}}_{k}^{}^{iter}$ until the resolution is up to initial setting.

4. Simulations and Analysis

In order to evaluate the performance of the proposed algorithms, we conducted some typical numerical simulations. The simulation parameters are set in Table 2.

Table 2

Simulation parameters.

Observation scene	1000 m1000 m100 m
Source number	1 or 2
Source positions	Located randomly in the scene
Source intensity	3000, 3000
SNR	10 dB
Experiment times	$N_{T} = 200$
Sensor gain	1
Sensor number	9, 18, 36, 54
Sensor positions	Locate in the scene and submit to uniform distribution
Resolution requirement	1 m1 m0.1 m

4.1. RSS-WSNs Deployment

Generally speaking, sensor nodes can be deployed in a plane, or in two planes, or in a three-dimensional space. The manner of deployment [27] is classified into random distribution and uniform formation. In this study, area coverage is the primary objective for deployment, and more details are in paper [7, 13, 28]. For different localization algorithms, it is necessary to deploy nodes in a proper manner to improve localization accuracy. For ML, the more uniform the nodes are within the sensor field layout, the smaller the CRLR and the higher the localization accuracy are.

The localization accuracy is defined as the root mean square (RMS), given by

RMS = \frac{1}{N_{T}} \sqrt{\sum_{i = 1}^{N_{T}} {‖ {\vec{\hat{r}}}_{i} - {\vec{r}}_{i 0} ‖}_{2}^{2}} .

(22)

Here, ${\vec{r}}_{i 0}$ is the source position, ${\vec{\hat{r}}}_{i}$ is the estimated position in i-experiment, and $N_{T}$ is the experiment time.

However, the CS-based algorithm is the opposite of ML. Because the distribution of nodes impacts on $μ (Φ, Ψ)$ , the proper RSS-WSNs' deployment can make Φ to be as incoherent with $Ψ$ as possible. The more randomly the nodes are deployed, the smaller $μ (Φ, Ψ)$ and RMS are.

We contract the impacts on $μ (Φ, Ψ)$ and RMS from the four RSS-WSNs' deployments, which are in uniform formation in a plane, uniform formation in two planes, random distribution in a plane, and random distribution in two planes, respectively. The simulation results are presented in Figure 8. Figures 8(a) and 8(b) show the deployment impacts on RMS, and Figures 8(c) and 8(d) show the deployment impacts on $μ (Φ, Ψ)$ . The triangles and the squares represent uniform formation and random distribution, respectively.

Figure 8

RSS-WSNs' deployment impacts RMS and $μ (Φ, Ψ)$ .

In Figures 8(a) and 8(b), the RMS of random distribution is smaller than the RMS of uniform formation, especially when $N_{S}$ is 9 and 18. It is because that $μ (Φ, Ψ)$ of random distribution is smaller than $μ (Φ, Ψ)$ of uniform formation, which is shown in Figures 8(c) and 8(d). Reducing $μ (Φ, Ψ)$ can weaken the coherence between $Φ$ and Ψ, which is good for signal recovery. Simulations demonstrate that the random deployment of RSS-WSNs can weaken the coherence between Φ and Ψ, hence reducing the RMS.

4.2. Coefficients of the Recovery Algorithm

As mentioned above, $λ_{L}$ determines $p (θ | λ_{L})$ . Consequently, it impacts the RMS of source localization. $p (θ | λ_{L})$ is a function of $K$ and $λ_{L}$ which is shown in Figure 9(a). When $λ_{L}$ ranges among 0.1, 1, 5, 10, and 20. And RMS varies as $N_{S}$ and $λ_{L}$ change, which is shown in Figure 9(b).

Figure 9

Coefficients for recovery algorithm.

For the same $K$ , $p (θ | λ_{L})$ increases as $λ_{L}$ decreases. It means that the probability that $θ$ has K-sparsity increases. For the same $p (θ | λ_{L})$ , K increases as $λ_{L}$ decreases (Figure 9(a)). If $λ_{L}$ is extremely small, the probability that θ has a big K is large, which would lead to the appearance of fake sources. Because of this relationship between $p (θ | λ_{L})$ and $λ_{L}$ , RMS is always below 1 m when $λ_{L} = 0.1$ (as shown in Figure 9(b)). After comprehensive consideration of RMS and false alarms, the coefficient is chosen to $λ_{L} = 0.1$ .

4.3. Single Source Localization

In this subsection, the sample number $N_{S}$ ranges from 9, 18, 36 to 54,and the nodes are randomly deployed in a three-dimensional observation scene. RMS is related with SNR and $N_{S}$ , which is shown in Figure 10. The blue squares denote $N_{S} = 9$ , the red upward-pointing triangles $N_{S} = 18$ , the green circles $N_{S} = 36$ , and the black downward-pointing triangles $N_{S} = 54$ .

Figure 10

RMS varies with SNR (single source).

Figure 10 shows that higher SNR leads to lower RMS for the same $N_{S}$ , and more samples (or bigger $N_{S}$ ) leads to lower RMS for the same SNR. Especially when SNR = 10 dB and the sample number is above 18, RMS is below 3 m. As SNR increases, RMS decreases until below 1 m. When $SNR \geq 20 dB$ , the decreasing of RMS becomes slower along as $N_{S}$ increases. When $SNR \geq 20 dB$ , $N_{S} = 9$ makes RMS below 1 m.

In order to compare with other existing methods, the alternating projection (AP) algorithm [9] is also simulated as one effective localization algorithm based on ML. AP utilizes matrix projection to replace the inversion of matrix, and it locates unknown multiple sources through alternating optimization. The simulation results are shown in Figure 11 and Figure 13.

Figure 11

Compared to AP (single source).

For the same $N_{S}$ , CS-based localization algorithm has lower RMS than AP. We found that the performance of CS-based algorithm when $N_{S} = 18$ is similar to or better than the performance of AP even when $N_{S} = 36$ . For instance, as SNR = 0 dB or 10 dB, RMS of CS-based ( $N_{S} = 18$ ) is similar to AP ( $N_{S} = 36$ ), but as $SNR \geq 20 dB$ , RMS of CS-based ( $N_{S} = 18$ ) is smaller than AP ( $N_{S} = 36$ ). The same situation happens between CS-based when $N_{S} = 9$ and AP when $N_{S} = 18$ . As SNR = 0 dB or 10 dB, CS-based is similar to AP, but as $SNR \geq 20 dB$ CS-based is better than AP. Thus CS-based algorithm needs smaller nodes than AP algorithm to achieve the same RMS. When RSS-WSNs are sparsely distributed, CS-based performance is better than AP.

4.4. Two-Source Localization

The observation scene can be adaptively divided into subscenes through constructing redundant dictionaries. For multiple sources, their locations can be converted into estimating of the positions of one source or two closely sources in a subscene. As mentioned above, single-source localization has been analyzed. It is known that RMS of multiple sources is a function of SNR, $N_{S}$ , and the distance between two sources. We assume SNR to be 20, 10, 0, and −10 dB, $N_{S}$ to be 36 and 18, and the distance between two sources to be 1 m, 5 m, and 25 m, respectively. The histograms of the estimated number of sources at different SNR and source distances are shown in Figure 12.

Figure 12

Distribution of the estimated number of sources of different SNR and $N_{S}$ (two sources).

Figure 13

Contrast between CS-based and AP in localization performance (two sources).

When SNR is 20 or 10 dB (Figures 12(a), 12(b), 12(e), and 12(f)), RSS-WSNs can stably distinguish two sources with the probability above 0.8, even if the distance of two sources is close to the resolution requirement (1 m). The probability of distinguishing sources decreases as SNR decreases. Especially, if SNR = −10 dB, the probability that two sources are well separated is below 0.5 (Figure 12(d)). Comparing Figures 12(a) 12(b) to 12(e) 12(f), it is found that few spatial samples would make the probability of fake source greater. For example, as SNR = 10 dB and $N_{S} = 18$ , the probability of fake source is nearly up to 0.2. Additionally, Figure 12 shows that the probability of accurate estimation increases with the increasing of the distance between sources.

We explore the RMS of CS-based and AP algorithm in locating two sources, especially when they are close to each other. SNR is assumed to be 20 dB, and the distance between two sources ranges from 1 m to 29 m, increasing in steps of 4 m. The contrast between CS-based and AP is illustrated in Figure 13. The dotted lines and the solid lines stand for AP and CS-based, respectively. The triangles and the squares are the first source and the second one, respectively.

In Figure 13, for CS-based and AP algorithm, simulation shows that the RMS of locating two sources is larger than that of locating a single source. It is because the parameters that are needed to estimate increase with the augment of the number of sources. In CS-based algorithm, the augment of source number results in the augment of the sparsity $K$ . If $N_{S}$ is fixed, the augment of K would lead to the decreasing of location accuracy.

Theoretically, RMS decreases as the distance between sources increases for both CS-based and AP. However, when nodes are sparse, the RMS of multiple sources using AP is around 15 m (Figure 13). It is because the performance of AP has a strong relationship with the density of nodes, and RMS decreases as the density of nodes increases up to a certain level. If the density is not up to this level, RMS does not obviously decrease with the great increasing of the distance. However, CS-based algorithm has a different performance. At the same condition, the RMS of CS-based is smaller than AP, especially when $N_{S} = 9$ or 18.

In Figures 13(c) and 13(d), when the two sources are close to each other $(d \leq 13 m)$ , RMS does not decrease as $N_{S}$ increases from 36 to 54. This is because their positions of them in θ are too close to precisely recover $θ$ . Thus, it is necessary to optimize RDA (shown in (20)) to resolve two close sources.

In order to explore the impact from the optimization of RDA, two sets of simulation results are shown in Figure 14. One set is without RDA optimization (dashed line), and the other is with RDA optimization (solid line). The triangles and the squares represent the first source and the second source, respectively.

Figure 14

RDA impacts on RMS.

In Figure 14, CS-based localization algorithm improves with RDA optimization. The RMS of two sources with the procedure is smaller than that without the procedure, which is obvious when the distance between the sources is less than 21 m. This demonstrates that RDA optimization can effectively improve the capacity to resolve multiple close sources. However, when two sources are far apart (i.e., the distance between the sources is more than 21 m), the impact on RMS from the procedure is little. This is because no matter which RDAs are utilized, the distance between sources is enough to be resolved. At this time, RDA optimization is not of much importance.

5. Conclusions and Outlook

This work proposes an effective source localization algorithm based on CS, which is used on sparsely distributed RSS-WSNs. Extensive simulations show that the proposed algorithm consistently outperforms the existing ML algorithms. Compared to ML, CS-based algorithm improves the accuracy of single- and multiple-sources localization at the same number of samples. With the same accuracy of localization, this algorithm can effectively reduce the number of spatial samples.

Additionally, multi-resolution redundant dictionary reduces the complexity of calculation, and the adaptive dictionary refinement and the optimization of RDA can improve the efficiency of multiple source localization. A simulation demonstrates that the random deployment of nodes is more suitable to this algorithm than uniform formation.

There are other adaptive spatial partitioning approaches to construct redundant dictionary, such as KD tree or RP tree. Future work concerns about tree partitioning and treeindexing in CS-based source location algorithm.

Footnotes

Acknowledgments

The authors would like to thank the anonymous referees for their kind comments and valuable suggestions. They would like to thank S. D. Babacan and R. Molina with Northwestern University and A. K. Katsaggelos with University of Granada for sharing the program of signal recovery (FastLaplace). they wish to give their sincere thanks to Chen Yong-qiang, Tan Wei-xian, Lin Yue-guan, Kou Bo, Jiang Hai, and Xiang Yin with IECAS for thoughtful comments and suggestions during numerous discussions. Finally, they wish to thank Mark Xiang Wei, Zeylord Bautista, and Dong Fang for their help during writing and thank Ouyang Yue with IECAS for his help during revision.

References

Model

Zibulevsky

Signal reconstruction in sensor arrays using sparse representations

Signal Processing 2006 86 3 624 638

2-s2.0-30844441893

10.1016/j.sigpro.2005.05.033

Yick

Mukherjee

Ghosal

Wireless sensor network survey

Computer Networks 2008 52 12 2292 2330

2-s2.0-46449122114

10.1016/j.comnet.2008.04.002

Y. H.

Energy-based collaborative source localization using acoustic microsensor array

EURASIP Journal on Applied Signal Processing 2003 2003 4 321 337

2-s2.0-0037445307

10.1155/S1110865703212075

Kumar

Zhao

Shepherd

Collaborative signal and information processing in microsensor networks

IEEE Signal Processing Magazine 2002 19 2 13 14

2-s2.0-0036503624

10.1109/MSP.2002.985672

Malioutov

D. M.

A Sparse Signal Reconstruction Perspective for Source Localization with Sensor Arrays, Master of Science 2003

Electrical Engineering and Computer Science Massachusetts Institute of Technology

Tropp

J. A.

Gilbert

A. C.

Signal recovery from random measurements via orthogonal matching pursuit

IEEE Transactions on Information Theory 2007 53 12 4655 4666

2-s2.0-64649083745

10.1109/TIT.2007.909108

Tibshirani

Regression shrinkage and selection via the lasso

Journal of the Royal Statistical Society. Series B 1996 58 267 288

Chen

S. S.

Donoho

D. L.

Saunders

M. A.

Atomic decomposition by basis pursuit

SIAM Journal on Scientific Computing 1998 20 1 33 61

2-s2.0-0032131292

Ampeliotis

Berberidis

Low complexity multiple acoustic source localization in sensor networks based on energy measurements

Signal Processing 2010 90 4 1300 1312

2-s2.0-72949110576

10.1016/j.sigpro.2009.10.015

10.

Sheng

Y. H.

Maximum likelihood multiple-source localization using acoustic energy measurements with wireless sensor networks

IEEE Transactions on Signal Processing 2005 53 1 44 53

2-s2.0-11844301315

10.1109/TSP.2004.838930

11.

Niu

Varshney

P. K.

Target location estimation in sensor networks with quantized data

IEEE Transactions on Signal Processing 2006 54 12 4519 4528

2-s2.0-33947187995

10.1109/TSP.2006.882082

12.

Gorodnitsky

I. F.

Rao

B. D.

Sparse signal reconstruction from limited data using FOCUSS: a re-weighted minimum norm algorithm

IEEE Transactions on Signal Processing 1997 45 3 600 616

2-s2.0-0031102203

13.

Ishizuka

Aida

Performance study of node placement in sensor networks

Proceedings of the 24th International Conference on Distributed Computing Systems

March 2004

Tokyo, Japan

598 603

14.

Partan

Kurose

Levine

B. N.

A survey of practical issues in underwater networks

the 1st ACM International Workshop on Underwater Networks (WUWNet '06)

September 2006

Los Angeles, Calif, USA

17 24

2-s2.0-34247377791

10.1145/1161039.1161045

15.

Candès

E. J.

Wakin

M. B.

An introduction to compressive sampling: a sensing/sampling paradigm that goes against the common knowledge in data acquisition

IEEE Signal Processing Magazine 2008 25 2 21 30

2-s2.0-41949092318

10.1109/MSP.2007.914731

16.

Donoho

D. L.

Compressed sensing

IEEE Transactions on Information Theory 2006 52 4 1289 1306

2-s2.0-33645712892

10.1109/TIT.2006.871582

17.

Baron

Wakin

M. B.

Duarte

M. F.

Distributed compressed sensing

2005

18.

Ling

Tian

Decentralized sparse signal recovery for compressive sleeping wireless sensor networks

IEEE Transactions on Signal Processing 2010 58 7 3816 3827

2-s2.0-77953757231

10.1109/TSP.2010.2047721

19.

Meng

Han

Sparse event detection in wireless sensor networks using compressive sensing

the 43rd Annual Conference on Information Sciences and Systems (CISS '09)

March 2009

Baltimore, Md, USA

181 185

2-s2.0-70349659937

10.1109/CISS.2009.5054713

20.

Baraniuk

R. G.

Davenport

M. A.

Wakin

M. B.

Detection and estimation with compressive measurements

2006

21.

Cevher

Gurbuz

A. C.

McClellan

J. H.

Chellappa

Compressive wireless arrays for bearing estimation

IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP '08)

April 2008

New York, NY, USA

2497 2500

2-s2.0-51449109098

10.1109/ICASSP.2008.4518155

22.

Cevher

Duarte

M. F.

Baraniuk

R. G.

Distributed target localization via spatial sparsity

the 16th European Signal Processing Conference

2008

23.

Rauhut

Schnass

Vandergheynst

Compressed sensing and redundant dictionaries

IEEE Transactions on Information Theory 2008 54 5 2210 2219

2-s2.0-43749118418

10.1109/TIT.2008.920190

24.

Candès

E. J.

Eldar

Y. C.

Needell

Randall

Compressed sensing with coherent and redundant dictionaries

Applied and Computational Harmonic Analysis 2011 31 1 59 73

2-s2.0-78049352374

10.1016/j.acha.2010.10.002

25.

Candès

Romberg

Sparsity and incoherence in compressive sampling

Inverse Problems 2007 23 3 969 985

2-s2.0-34249687049

10.1088/0266-5611/23/3/008

26.

Babacan

S. D.

Molina

Katsaggelos

A. K.

Bayesian compressive sensing using laplace priors

IEEE Transactions on Image Processing 2010 19 1 53 63

2-s2.0-72949095917

10.1109/TIP.2009.2032894

27.

Younis

Akkaya

Strategies and techniques for node placement in wireless sensor networks: a survey

Ad Hoc Networks 2008 6 4 621 655

2-s2.0-39149099807

10.1016/j.adhoc.2007.05.003

28.

Chakrabarty

Iyengar

S. S.

Cho

Grid coverage for surveillance and target location in distributed sensor networks

IEEE Transactions on Computers 2002 51 12 1448 1453

2-s2.0-0036933529

10.1109/TC.2002.1146711