Multiple Target Localization in WSNs Based on Compressive Sensing Using Deterministic Sensing Matrices

Abstract

Accurate and low-cost localization of multiple targets or nodes is one of fundamental and challenging technical issues in wireless sensor networks (WSNs). Furthermore, compressive sensing allows that a sparse signal can be reconstructed from few measurements, and choosing a suitable sensing matrix is also important. For this purpose, random sensing matrices have been studied, while a few researches on deterministic sensing matrices have been considered. In this paper, we use compressive sensing for multiple target localization in WSNs. We formulate multiple target locations as a sparse matrix in the discrete time domain. Then, we exploit received signal strength information to recover noisy measurements, while utilizing deterministic sensing matrices and greedy algorithm to locate each target. The proposal approach reduces the number of measurements in localization process, takes low-cost, and maintains the accuracy as compared to the conventional approach which is noncompressive sensing. Further simulation shows that the proposed approach is practical in use, while being favorably comparable to the existing random sensing matrices in reconstruction performance. This cooperation between the compressive sensing using deterministic sensing matrices and multiple target localization provides a new point of view in WSN localization.

1. Introduction

Recently, many techniques for localization or positioning in wireless sensor networks (WSNs) have been considered with a variety of applications such as robotic land-mine detection, target tracking, and environmental and traffic monitoring, to name just a few. Since targets or nodes in WSNs are randomly deployed, we need to know actual locations or positions of these nodes. Even though there exists global positioning system (GPS) which provides highly accurate global location information, it is difficult to embed a GPS receiver in a WSN node because of cost and power-consumption issues. Moreover, the GPS usually does not work well in non-line-of-sight (NLoS) or indoor environments. Hence, target localization in WSNs is a hot topic for researchers [1, 2].

Generally, a localization process consists of two steps. First, we choose measurement parameters between nodes using features of the received signals such as time of arrival (ToA), time difference of arrival (TDoA), angle of arrival (AoA), and received signal strength (RSS). Then, we find the location of the node by using parameter estimation methods which depend on the signal features used in the first step. These estimation methods include triangulation, trilateration, multilateration, bounding box, fingerprinting, and some probability approaches. Localization based on RSS has been studied in indoor systems over recent years, which can be easily obtained by WiFi-integrated mobile terminals without any extra hardware [3–11].

Compressive sensing, also known as compressed sampling or sparse sampling, provides a novel framework for recovering a sparse or a compressible signal from a few measurements under certain assumptions on noise and power range by the Nyquist sampling theorem [12, 13]. Furthermore, the compressive sensing theory has been applied to localization; in particular it is suitable to multiple target localization problems which always have a large number of unknown nodes distributed in a large area. To count and localize targets, the target locations can be considered as sparse signals. By representing the location of the target over grid, the locations can be expressed as a sparse vector. Then, compressive sensing techniques are used to reconstruct those sparse locations [14–17]. The compressive sensing theory involves recovering a sparse signal x from linear measurements of the form $\mathbf{y}=\mathbf{\Phi }\mathbf{x}$ , where Φ is the sensing matrix. In [12, 13, 18], it is shown that a k-sparse signal x is the solution of ${\ell }_{\mathrm{0}}$ optimization if every submatrix of Φ is formed by choosing $\mathrm{2}k$ arbitrary columns of Φ with full rank. In [13], it is shown that, for a small k, the ${\ell }_{\mathrm{1}}$ problem is equivalent to the ${\ell }_{\mathrm{0}}$ problem if the matrix Φ satisfies restricted isometry property (RIP). Most of early works on compressive sensing construct random matrices as sensing matrices, and some recent works have designed specific deterministic sensing matrices based on some given conditions. In [19], the authors designed deterministic Toeplitz matrices having guaranteed RIP properties. Using Weil's exponential sum, they obtained a deterministic sampling of multivariate trigonometric polynomial [20]. Constructing some weaker RIPs, utilization of fast Fourier transform (FFT) or algebraic curves have been recently proposed [21–23]. There are also many related researches on this topic to improve the accuracy of recovery and to reduce the system complexity [24–27].

We consider a scenario that the nodes are randomly deployed in a large area, measured by taking RSS information from their neighbors as Figure 1 illustrates. Only few of nodes are known, which are called anchor nodes. The rest of nodes could be obtaining their location through localization method. Our proposed method is a compressive sensing using deterministic sensing matrices for multiple target localization in WSNs based on sparse and inconsistent signal measurements. The problem is formulated as a sparse approximation of a sparse matrix with its elements being RSS measurements at grid. Then we employ Orthogonal Matching Pursuit (OMP) algorithm to recover the locations of all the targets.

Figure 1

The scenario of multiple target localization in WSNs.

The rest of the paper is organized as follows. In Section 2, we provide a brief summary of sparse signal recovery using compressive sensing. The node localization problem is formulated in Section 3. In Section 4, we describe our approach for node localization in WSNs using deterministic sensing matrices. Then, numerical evaluation results are presented in Section 5, followed by concluding remarks in Section 6.

Notations. $(·{)}^T,(·{)}^{-\mathrm{1}}$ , and $(·{)}^{\mathrm{\ast }}$ denote the matrix transpose, inverse, and complex-conjugate operations, respectively. The operations ${‖·‖}_0,{‖·‖}_1$ , and ${‖·‖}_2$ denote ${\ell }_{\mathrm{0}}$ -norm, ${\ell }_{\mathrm{1}}$ -norm, and ${\ell }_{\mathrm{2}}$ -norm, respectively. $\text{Co}{\text{n}}_{F^{\prime }/F}(P)$ is conorm of P in the extension $F^{\prime }/F$ , $\gcd (m,r)$ is the greatest common divisor of m and r, $l(.)$ is dimension of the Riemann-Roch space, and $\bar{F}$ is closure of F.

2. Background

2.1. Fundamentals of Compressive Sensing

The goal of compressive sensing is to minimize the number of measurements needed to take samples of a signal. Let the signal x be a discrete-time column vector in ${\mathbb{R}}^N$ and let $\mathit{\Psi }=\left[\begin{array}{cccc}{\mathit{\Psi }}_{\mathrm{1}}& {\mathit{\Psi }}_{\mathrm{2}}& \cdots & {\mathit{\Psi }}_N\end{array}\right]$ be an orthogonal basis of ${\mathbb{R}}^N$ . In practice, this signal vector x can be represented as sparse coefficients by an orthonormal basis Ψ having only $K\ll N$ nonzero coefficients. Then we can write

$$\begin{array}{cc}& \mathbf{x}=\mathit{\Psi }\mathbf{\theta }={\displaystyle \sum }_{i=\mathrm{1}}^N‍{\theta }_i{\mathit{\Psi }}_i,\end{array}$$

(1)

where ${\theta }_i$ is the ith sample of sparse coefficient of θ, satisfying ${‖\mathbf{\theta }‖}_0=K$ which means

$$\begin{array}{cc}& \#\left\{i:{\theta }_i\ne \mathrm{0}\right\}=K,\end{array}$$

(2)

and ${\mathit{\Psi }}_i$ is the ith column of the sparse basis. The compressive sensing aims to recover x from knowledge of

$$\begin{array}{cc}& \mathbf{y}=\mathbf{\Phi }\mathbf{x}={\displaystyle \sum }_{i=\mathrm{1}}^M‍x_i{\mathbf{\Phi }}_i\end{array}$$

(3)

or recover θ from knowledge of

$$\begin{array}{cc}& \mathbf{y}=\mathbf{\Phi }\mathit{\Psi }\mathbf{\theta },\end{array}$$

(4)

where $\mathbf{y}\in {\mathbb{R}}^M$ , and $\mathbf{\Phi }\in {\mathbb{R}}^{M\times N}$ is the measurement matrix or the sensing matrix of size $M\times N$ with $M\ll N$ . The solution can be recovered by solving the following equation which is one of the common convex optimization problems:

$$\begin{array}{cc}& \underset{\mathbf{\theta }}{\min }{‖\mathbf{\theta }‖}_{\mathrm{1}}\hspace{1em}\text{such}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{that}\mathrm{\hspace{0.17em}\hspace{0.17em}}\mathbf{y}=\mathbf{\Theta }\mathbf{\theta },\end{array}$$

(5)

where $\mathbf{\Theta }=\mathbf{\Phi }\mathit{\Psi }$ is called the holographic dictionary. In [21], the authors showed that the number of measurements M required for sparse reconstruction via ${\ell }_{\mathrm{1}}$ -minimization method satisfies $M\approx \mathcal{O}(K\log (N/K))\ll N$ . If the measurement y is affected by unknown noise n, then the information can be expressed as

$$\begin{array}{cc}& \mathbf{y}=\mathbf{\Theta }\mathbf{\theta }+\mathbf{n},\end{array}$$

(6)

and the minimization problem changes to

$$\begin{array}{cc}& \underset{\mathbf{\theta }}{\min }{‖\mathbf{\theta }‖}_{\mathrm{1}}\hspace{1em}\text{such}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{that}\mathrm{\hspace{0.17em}\hspace{0.17em}}{‖\mathbf{\Theta }\mathbf{\theta }-\mathbf{y}‖}_{\mathrm{2}}^{\mathrm{2}}<ϵ\end{array}$$

(7)

for a chosen $ϵ>\mathrm{0}$ , or the other unconstrained version is given by

$$\begin{array}{cc}& \underset{\mathbf{\theta }}{\min }\frac{\mathrm{1}}{\mathrm{2}}{‖\mathbf{\Theta }\mathbf{\theta }-\mathbf{y}‖}_{\mathrm{2}}^{\mathrm{2}}+\lambda {‖\mathbf{\theta }‖}_{\mathrm{1}}\end{array}$$

(8)

for a parameter $\lambda >\mathrm{0}$ .

Some of the most important concerns of the compressive sensing are how to find an appropriate sensing matrix to guarantee recovering the signal with high probability, what kind of reconstruction algorithm to use, and its efficient computation. In [12], the authors show that the sensing matrices must satisfy the k-RIP to ensure a unique and stable solution in convex reconstruction problem. A matrix Φ obeys the RIP condition with parameters $(k,{\delta }_k)$ for ${\delta }_k\in (\mathrm{0,1})$ if

$$\begin{array}{cc}& \left(\mathrm{1}-{\delta }_k\right){‖\mathbf{u}‖}_{\mathrm{2}}^{\mathrm{2}}\le {‖\mathbf{\Phi }\mathbf{u}‖}_{\mathrm{2}}^{\mathrm{2}}\le \left(\mathrm{1}+{\delta }_k\right){‖\mathbf{u}‖}_{\mathrm{2}}^{\mathrm{2}}\end{array}$$

(9)

holds for all k-sparse vectors u. An upper bound of the sparsity is

$$\begin{array}{cc}& k\le \frac{cM}{\log \left(N/M\right)},\end{array}$$

(10)

where c is a positive constant. Some notable sensing matrices satisfying the k-RIP with high probability are independent identically distributed (i.i.d.) Gaussian, Bernoulli, and random Fourier ensembles.

For a given sensing matrix $\mathbf{\Phi }=\left[\begin{array}{cccc}{\mathbf{\Phi }}_{\mathrm{1}}& {\mathbf{\Phi }}_{\mathrm{2}}& \cdots & {\mathbf{\Phi }}_N\end{array}\right]$ and the representation basis $\mathit{\Psi }=\left[\begin{array}{cccc}{\mathit{\Psi }}_{\mathrm{1}}& {\mathit{\Psi }}_{\mathrm{2}}& \cdots & {\mathit{\Psi }}_N\end{array}\right]$ , where ${\mathbf{\Phi }}_i$ and ${\mathit{\Psi }}_i\mathrm{\hspace{0.17em}\hspace{0.17em}}(i=\mathrm{1},\dots ,N)$ are their corresponding column vectors, the incoherence between them is defined as the largest correlation as follows:

$$\begin{array}{cc}& \mu \left(\mathbf{\Phi },\mathit{\Psi }\right)=\underset{\mathrm{1}\le i,j\le N}{\max }\sqrt{N}\left|〈{\mathbf{\Phi }}_i,{\mathit{\Psi }}_j〉\right|.\end{array}$$

(11)

Donoho in [12] showed that $(\mathrm{2}k-\mathrm{1})\mu <\mathrm{1}$ ensures unique k-sparse signal recovery by Basis Pursuit (BP), and Tropp and Gilbert in [28] then extended the sufficient condition to the OMP. Gribonval and Vandergheynst in [29] showed that Matching Pursuit (MP) derives a unique solution with exponential convergence.

2.2. Orthogonal Matching Pursuit (OMP) Algorithm

The OMP algorithm aims to approximate the solution of the following problem:

$$\begin{array}{cc}& \widehat{\mathbf{\theta }}=\arg \hspace{0.17em}\underset{\mathbf{\theta }}{\min }{‖\mathbf{y}-\mathbf{\Theta }\mathbf{\theta }‖}_{\mathrm{2}}^{\mathrm{2}}\hspace{1em}\text{such}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{that}\mathrm{\hspace{0.17em}\hspace{0.17em}}{‖\mathbf{\theta }‖}_{\mathrm{0}}\le k\end{array}$$

(12)

or the error-constrained sparse coding problem given by

$$\begin{array}{cc}& \widehat{\mathbf{\theta }}=\arg \hspace{0.17em}\underset{\mathbf{\theta }}{\min }{‖\mathbf{\theta }‖}_{\mathrm{0}}\hspace{1em}\text{such}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{that}\mathrm{\hspace{0.17em}\hspace{0.17em}}{‖\mathbf{y}-\mathbf{\Theta }\mathbf{\theta }‖}_{\mathrm{2}}^{\mathrm{2}}\le ϵ.\end{array}$$

(13)

Denote the OMP operation as $\widehat{\mathbf{\theta }}=\text{OMP}(\mathbf{y},\mathbf{\Theta },ϵ)$ , where ϵ is an upper bound on the norm of the residual error term ${‖\mathbf{y}-\mathbf{\Theta }\mathbf{\theta }‖}_2$ . The algorithm can be described by Algorithm 1.

Algorithm 1: OMP algorithm.

( $$\mathit{1}$$ )   procedure OMP $$(\mathbf{\Theta },\mathbf{y},k,ϵ)$$

( $$\mathit{2}$$ )     $$k\leftarrow \mathrm{1}$$

( $$\mathit{3}$$ )     $$\widehat{\mathbf{\theta }}\leftarrow \mathrm{0}$$

( $$\mathit{4}$$ )     $${\mathbf{r}}_{\mathrm{0}}\leftarrow y$$

( $$\mathit{5}$$ )     $$V_{\mathrm{0}}\leftarrow \mathrm{\varnothing }$$

( $$\mathit{6}$$ )    while   $${‖{\mathbf{r}}_k‖}_{\mathit{2}}>ϵ$$   do

( $$\mathit{7}$$ )     Compute $$a_i=\left|{\mathbf{r}}_{k-\mathrm{1}}^T\mathbf{\Theta }\left(:,i\right)\right|$$ for all $$i\notin V_{k-\mathrm{1}}$$

( $$\mathit{8}$$ )     Choose $$v_k={\text{argmax}}_i{a}_i$$

( $$\mathit{9}$$ )     Update $$V_k=V_{k-\mathrm{1}}\cup v_k$$

(10)   Compute $$\widehat{\mathbf{\theta }}(V_k)=(\mathbf{\Theta }(:,V_k){)}^T\mathbf{y}$$

(11)   Compute $${\mathbf{r}}_k=\mathbf{y}-(\mathbf{\Theta }(:,V_k))\widehat{\mathbf{\theta }}(V_k)$$

( $$\mathit{12}$$ )   Set $$k=k+\mathrm{1}$$ .

( $$\mathit{13}$$ )  end while

( $$\mathit{14}$$ )  return   $${\widehat{\mathbf{\theta }}}_k$$                ⊳ Approximated solution

( $$\mathit{15}$$ ) end procedure

2.3. Related Works on Deterministic Sensing Matrices

We consider the sensing matrix Φ in usual. It can be chosen as a $M\times N$ random Gaussian matrix whose entries obey i.i.d. Gaussian distribution. The matrix Φ must also satisfy RIP condition to guarantee unique and exact reconstructed solution. Meanwhile, random matrices have critical drawbacks such as cost and complexity in reconstruction, error in signal approximation, significant space requirement for storage, and no efficient algorithm to verify whether a sampled sensing matrix satisfies the RIP property. In [21], some weaker RIP conditions have been considered. With a uniform distribution of vector α among all k-sparse vectors in ${\mathbb{R}}^N$ ,

• (i)

$(k,ϵ,\delta$ ) StRIP matrix: A sensing matrix ${\mathbf{\Phi }}_{M\times N}$ is said to be a $(k,ϵ,\delta )$ StRIP matrix if, for any k-sparse signal $\mathit{\alpha }\in {\mathbb{R}}^N$ , $\left(\mathrm{1}-ϵ\right){‖\mathit{\alpha }‖}^2\le {‖\left(\mathrm{1}/N\right)\mathbf{\Phi }\mathit{\alpha }‖}^2\le \left(\mathrm{1}+ϵ\right){‖\mathit{\alpha }‖}^2$ holds with probability exceeding $\mathrm{1}-\delta$ ;

(ii)

( $k,ϵ,\delta$ ) UStRIP matrix: A sensing matrix ${\mathbf{\Phi }}_{M\times N}$ is said to be $(k,ϵ,\delta )$ UStRIP matrix, if, for any k-sparse signal $\mathit{\alpha }\in {\mathbb{R}}^N$ , Φ is $(k,ϵ,\delta$ ) StRIP matrix and $\{\beta \in {\mathbb{R}}^N:\mathbf{\Phi }\mathit{\alpha }=\mathbf{\Phi }\beta \}=\{\mathit{\alpha }\}$ holds with probability exceeding $\mathrm{1}-\delta$ .

In [22], a sensing matrix is designed with chirp sequences forming the columns using FFT. They show empirically that this type of matrix is valid as compressed sensing measurements. This is done by a comparison with random projections and modified RIP conditions. These conditions still guarantee the recovery, but with a smaller probability. In [23], a new method to construct binary sensing matrices is introduced by using algebraic curves over a finite field. They show that if we choose appropriate curves, we can obtain matrices better than DeVore's ones. Some highlighted results such as deterministic construction of sensing matrices via algebraic curves over finite fields in terms of coherence and chirp sensing matrices, second-order Reed-Muller codes, binary Bose-Chaudhuri-Hocquenghem (BCH) codes, and the sensing matrices with statistical RIP in terms of the RIP have been introduced in [24].

2.4. Motivation

In localization problems, there are two main techniques to select a sensing matrix Φ: access point selection; orthogonalization and signal recovery using ${\ell }_{\mathrm{1}}$ minimization. Since random matrices have critical drawbacks such as that given in Section 2.3, we have to construct a matrix that is valid for compressed sensing measurement and guarantees the recovery. Thus, exploiting specific structures of the deterministic sensing matrices is required to solve these problems of the random sensing matrices. In this paper, using the results in [23], we will obtain a binary matrix Φ which achieves better performance in recovery by choosing an appropriate curve. This sensing matrix Φ is obtained by taking projections from the chosen curve.

Denote ${\mathbb{F}}_p$ as the finite field of order p where p is a prime power. $\mathcal{C}$ is an algebraic curve over ${\mathbb{F}}_p$ . Let $\mathcal{P}$ be the set of rational points of $\mathcal{C}/{\mathbb{F}}_q$

$$\begin{array}{cc}& \mathcal{P}=\left\{P=\left(a_{\mathrm{1}},\dots ,a_n\right)\hspace{0.17em}|\hspace{0.17em}{a}_i\in {\mathbb{F}}_p\right\}.\end{array}$$

(14)

Note that, given ${\mathbb{F}}_p$ , the set $\mathcal{P}\times {\mathbb{F}}_p$ has $\left|\mathcal{P}\right|\times p$ elements. Choose a divisor A of $\mathcal{C}$ such that $\mathrm{deg}(A)<\left|\mathcal{C}\right|$ and $\mathrm{supp}(A)\cap \mathcal{C}=\varnothing$ . Then, by using Riemann-Rock Theorem in the Appendix, we have $l(A)=\mathrm{deg}A+\mathrm{1}-g$ . Order the element of $\mathcal{P}\times {\mathbb{F}}_p$ lexicographically as $(\mathrm{0,0}),(\mathrm{0,1}),\dots ,(\{\left|\mathcal{P}\right|-\mathrm{1}\},p)$ . For any $f\in \mathcal{P}$ , define a binary column vector $v_f$ which has the form

$$\begin{array}{cc}& {\left[f_{\mathrm{0,0}},\dots ,f_{\mathrm{0},p-\mathrm{1}},f_{\mathrm{1,0}},\dots ,f_{\mathrm{1},p-\mathrm{1}},\dots ,f_{\left|\mathcal{P}\right|-\mathrm{1,0}},\dots ,f_{\left|\mathcal{P}\right|-\mathrm{1},p-\mathrm{1}}\right]}^T,\end{array}$$

(15)

where

$$\begin{array}{cc}& f_{i,j}=\left\{\begin{array}{cc}\mathrm{1}\hfill & \text{if}\mathrm{\hspace{0.17em}\hspace{0.17em}}f\left(i\right)=j\hfill \\ \mathrm{0},\hfill & \text{otherwise}\hfill \end{array}\right.\end{array}$$

(16)

for $\mathrm{0}\le i\le \left|\mathcal{P}\right|-\mathrm{1}$ and $\mathrm{0}\le j\le p-\mathrm{1}$ . The column vector $\{v_f\hspace{0.17em}|\hspace{0.17em}f\in \mathcal{P}\}$ forms a $\left|\mathcal{P}\right|p\times p^{l(A)}$ matrix ${\mathbf{\Phi }}_{\mathrm{0}}$ . Then we have the following theorem.

Theorem 1.

Suppose that $\mathbf{\Phi }=(\mathrm{1}/\sqrt{\left|\mathcal{P}\right|}){\mathbf{\Phi }}_{\mathrm{0}}$ ; then Φ is a sensing matrix satisfying the RIP with coherence $\mu (\mathbf{\Phi })\le \mathrm{deg}A/\left|\mathcal{P}\right|$ .

To get an optimal solution, the matrix Φ must satisfy the RIP of order $k=M/\log (N/M)$ at least. Gaussian matrix is one of this type. However, this is a random matrix. Thus, by using Theorem 1, we try to construct deterministic sensing matrices for smaller range of k.

3. Problem Formulation

Consider the two-dimensional localization problem, a sensor network with N points (grid); K targets are located in an isotropic area, where their positions are unknown. Wireless devices measure RSS from all the targets with $M_i\mathrm{\hspace{0.17em}\hspace{0.17em}}(i=\mathrm{1},\dots ,K)$ available measurements, while the number of measurements is much smaller than the grid size $(M_i\ll N)$ .

Since at each time the target is located at a specific point in the time domain, the localization problem can be modeled as a sparse problem. Assume that the target is located at one of the Reference Points (RPs), and the location of a target over the grid is represented by a $N\times \mathrm{1}$ vector as follows:

$$\begin{array}{cc}& {\mathbf{\theta }}_i={\left[\begin{array}{cccccc}\mathrm{0}& \mathrm{0}& \cdots & \mathrm{1}& \cdots & \mathrm{0}\end{array}\right]}^T,\hspace{1em}i=\mathrm{1},\dots ,K.\end{array}$$

(17)

Each ${\mathbf{\theta }}_i$ has all elements equal to zeros, except ${\mathbf{\theta }}_i(n)=\mathrm{1}$ . Here n is the index on grid point where ith target is located. Then, with K targets we obtain an $N\times K$ matrix

$$\begin{array}{cc}& \mathbf{\theta }=\left[\begin{array}{cccc}{\mathbf{\theta }}_{\mathrm{1}}& {\mathbf{\theta }}_{\mathrm{2}}& \cdots & {\mathbf{\theta }}_K\end{array}\right].\end{array}$$

(18)

Denote ${\mathbf{x}}_i\in {\mathbb{R}}^N$ as the measured signal which is recorded at the ith target. Then each signal ${\mathbf{x}}_i$ is given a distinct measurement matrix ${\mathbf{\Phi }}_i\in {\mathbb{R}}^{M_i\times N}$ which is a deterministic matrix. The measurement ${\mathbf{y}}_i$ can be written as

$$\begin{array}{cc}& {\mathbf{y}}_i={\mathbf{\Phi }}_i{\mathbf{x}}_i+{\mathbf{n}}_i,\hspace{1em}i=\mathrm{1},\dots ,K.\end{array}$$

(19)

Collecting all these equations, we can write the following form:

$$\begin{array}{cc}& \mathbf{y}=\mathbf{\Phi }\mathbf{x}+\mathbf{n},\end{array}$$

(20)

where n is a measurement noise. In detail, each term in (20) can be expressed as

$$\begin{array}{cc}& \mathbf{x}=\left[\begin{array}{c}{\mathbf{x}}_{\mathrm{1}}\\ {\mathbf{x}}_{\mathrm{2}}\\ ⋮\\ {\mathbf{x}}_K\end{array}\right],\hspace{1em}\hspace{1em}\mathbf{y}=\left[\begin{array}{c}{\mathbf{y}}_{\mathrm{1}}\\ {\mathbf{y}}_{\mathrm{2}}\\ ⋮\\ {\mathbf{y}}_K\end{array}\right],\hspace{1em}\hspace{1em}\mathbf{\Phi }=\left[\begin{array}{cccc}{\mathbf{\Phi }}_{\mathrm{1}}& \mathrm{0}& \cdots & 0\\ \mathrm{0}& {\mathbf{\Phi }}_{\mathrm{2}}& \cdots & 0\\ ⋮& ⋮& \ddots & ⋮\\ \mathrm{0}& \mathrm{0}& \cdots & {\mathbf{\Phi }}_K\end{array}\right],\end{array}$$

(21)

where $\mathbf{x}\in {\mathbb{R}}^{KN}$ , $\mathbf{y}\in {\mathbb{R}}^{{\sum }_{i=\mathrm{1}}^K‍M_i}$ , $\mathbf{\Phi }\in {\mathbb{R}}^{{\sum }_{i=\mathrm{1}}^K‍M_i\times KN}$ , and $\mathbf{n}\in {\mathbb{R}}^{{\sum }_{i=\mathrm{1}}^K‍M_i}$ .

Our goal is to determine the locations of all targets accurately only using a small number of measurements with a fast and low-complexity algorithm.

4. Main Results

With the aforementioned notions, we can write an arbitrary sparse signal as

$$\begin{array}{cc}& \mathbf{x}=\mathbf{P}\mathbf{\theta },\end{array}$$

(22)

where $\mathbf{x}\in {\mathbb{R}}^{KN}$ and P is $KN\times KN$ RSS sparsity basis matrix. It is clear that x is a K-sparse vector since ${‖\mathbf{x}‖}_{\mathrm{0}}=K$ .

4.1. RSS Information Matrix P

The $KN\times KN$ sparsity basis matrix P can be generated using the radio propagation channel model as

$$\begin{array}{cc}& \mathbf{P}=\left[\begin{array}{cccc}{\mathbf{P}}_{\mathrm{1}}& 0& \cdots & 0\\ 0& {\mathbf{P}}_{\mathrm{2}}& \cdots & 0\\ ⋮& ⋮& \ddots & ⋮\\ 0& 0& \cdots & {\mathbf{P}}_K\end{array}\right].\end{array}$$

(23)

Each ${\mathbf{P}}_u\mathrm{\hspace{0.17em}\hspace{0.17em}}(u=\mathrm{1},\dots ,K)$ is an $M_i\times N$ submatrix whose element has the form

$$\begin{array}{cc}& {\left[{\mathbf{P}}_u\right]}_{ij}=p_{\mathrm{0}}-\mathrm{10}{n}_p{\log }_{\mathrm{10}}\left(\frac{d_{ij}}{d_{\mathrm{0}}}\right),\hspace{1em}i,j=\mathrm{1},\dots ,N.\end{array}$$

(24)

$[{\mathbf{P}}_u{]}_{ij}$ is the received signal power in dBm, $n_p$ is the path loss component, $d_{ij}$ is the real distance between transmitter and receiver, and $d_{\mathrm{0}}$ is reference distance for the far field with receive power $p_{\mathrm{0}}$ .

4.2. Sensing Matrix Φ

Reference [20] gives a construction of sensing matrices using polynomials in finite fields. Also, it can be extended from a finite field ${\mathbb{F}}_p$ to its extension ${\mathbb{F}}_{p^r}$ . We exploit this idea in our problem. Note that the algebraic curves over ${\mathbb{F}}_{p^r}$ may have good properties such as large dimension and minimum distance, whereas the restricted algebraic curves $\mathcal{P}\hspace{0.17em}|\hspace{0.17em}{\mathbb{F}}_p$ may be very poor since the dimension of $\mathcal{P}\hspace{0.17em}|\hspace{0.17em}{\mathbb{F}}_p$ may be less than the dimension of ${\mathcal{P}}_r$ . Hence, by using the following theorem, we can replace ${\mathbb{F}}_p$ with ${\mathbb{F}}_{q^r}$ to construct a matrix with large size. In [30] the author shows the following.

Theorem 2.

Denote F as algebraic function field of genus g whose constant field is the finite field ${\mathbb{F}}_p$ , $F/T$ as an algebraic function field, $F^{\prime }/T$ as a finite separable extension, and $T^{\prime }$ as the constant field of $F^{\prime }$ . Thus, $T^{\prime }/T$ is a finite separable extension as well. For each $r>\mathrm{1}$ , there exists exactly one extension ${\mathbb{F}}_{p^r}/{\mathbb{F}}_p$ of degree r with ${\mathbb{F}}_{p^r}\subseteq {\bar{\mathbb{F}}}_p$ and one sets $F_r=F{\mathbb{F}}_{p^{\text{r}}}\subseteq \bar{F}$ . Therefore, one has the following.

• (a)

$F_r/F$ is Galois with a cyclic Galois group of order r ( $F_r/F$ is a cyclic extension of degree r). The Galois group Gal $(F_r/F)$ is generated by Frobenius automorphism σ which acts on ${\mathbb{F}}_{p^r}$ by $\sigma (\alpha )={\alpha }^p$ .

(b)

${\mathbb{F}}_{p^r}$ is the full constant field of $F_r$ .

(c)

Let $P\in {\mathbb{P}}_F\mathrm{\hspace{0.17em}\hspace{0.17em}}\left({\mathbb{P}}_F=\{P\hspace{0.17em}|\hspace{0.17em}P\mathrm{\hspace{0.17em}\hspace{0.17em}}is\mathrm{\hspace{0.17em}\hspace{0.17em}}a\mathrm{\hspace{0.17em}\hspace{0.17em}}place\mathrm{\hspace{0.17em}\hspace{0.17em}}of\mathrm{\hspace{0.17em}\hspace{0.17em}}F/T\}\right)$ be a place of degree m. Then $\text{Co}{\text{n}}_{F_r/F}(P)=P_{\mathrm{1}}+\cdots +P_d$ with $d=gcd(m,r)$ , pairwise distinct places $P_i\in {\mathbb{P}}_{F_r}$ and $\mathrm{deg}{P}_i=m/d$ .

If T is a perfect field, denote $N_r$ as the number of places of degree one in the constant field extension $F_r$ . With special case $T={\mathbb{F}}_{\mathrm{2}}$ , we have

$$\begin{array}{cc}& N_{\mathrm{1}}=\mathrm{3},\hspace{1em}\hspace{1em}{N}_{\mathrm{2}}=\mathrm{5},\hspace{1em}\hspace{1em}{N}_{\mathrm{3}}=\mathrm{24}.\end{array}$$

(25)

That means each of the three places of ${\mathbb{F}}_{\mathrm{2}}(x)$ of degree one has a unique extension of degree one in ${\mathbb{P}}_F$ and so on. Also, several explicit examples of function fields are considered, namely, elliptic and hyperelliptic function fields and Kummer and Artin-Schreier extensions of the rational function field such as the following.

• (i)

  Consider $F={\mathbb{F}}_{\mathrm{2}}\left[x\right]$ ; there is only elliptic function field $F/{\mathbb{F}}_{\mathrm{2}}$ with five places of $F/{\mathbb{F}}_{\mathrm{2}}$ of genus $g=\mathrm{1}$ :

  $$\begin{array}{cc}& y^{\mathrm{2}}+y=x^{\mathrm{3}}+x.\end{array}$$

  (26)

• (ii)

  Let $F={\mathbb{F}}_{q^{\mathrm{2}}}$ with

  $$\begin{array}{cc}& x^{p+\mathrm{1}}+y^{p+\mathrm{1}}=\mathrm{1},\end{array}$$

  (27)
  genus $g=p(p-\mathrm{1})/\mathrm{2}$ , and the number of places of degree one is $N=\mathrm{1}+p^{\mathrm{3}}$ .

For instance, in (26) the number $N_r$ of places of degree one of the function field ${\mathbb{F}}_r/{\mathbb{F}}_{{\mathrm{2}}^r}$ is given by [30]

$$\begin{array}{cc}& N_r={\mathrm{2}}^r+\mathrm{1}-\left({\alpha }^r+{{\alpha }^{\mathrm{\ast }}}^r\right),\end{array}$$

(28)

where $\alpha ,{\alpha }^{\mathrm{\ast }}\in \mathbb{C}$ are the reciprocals of the root of

$$\begin{array}{cc}& L\left(t\right)=\mathrm{1}+\mathrm{2}t+\mathrm{2}{t}^{\mathrm{2}}=\left(\mathrm{1}-\alpha t\right)\left(\mathrm{1}-{\alpha }^{\mathrm{\ast }}t\right),\end{array}$$

(29)

with $\alpha =-\mathrm{1}+i=\omega \sqrt{\mathrm{2}}$ , $\omega =\exp (\mathrm{3}\pi i/\mathrm{4})$ . Hence

$$\begin{array}{cc}& N_r=\left\{\begin{array}{cc}{\mathrm{2}}^r+\mathrm{1}\hfill & \hspace{0.5em}\hspace{0.5em}\text{for}\mathrm{\hspace{0.17em}\hspace{0.17em}}r\equiv \mathrm{2},\mathrm{6}\hspace{0.17em}\mathrm{mod}\hspace{0.17em}\mathrm{8},\hfill \\ {\mathrm{2}}^r+\mathrm{1}+\mathrm{2}·{\mathrm{2}}^{r/\mathrm{2}}\hfill & \hspace{0.5em}\hspace{0.5em}\text{for}\mathrm{\hspace{0.17em}\hspace{0.17em}}r\equiv \mathrm{4}\hspace{0.17em}\mathrm{mod}\hspace{0.17em}\mathrm{8},\hfill \\ {\mathrm{2}}^r+\mathrm{1}-\mathrm{2}·{\mathrm{2}}^{r/\mathrm{2}}\hfill & \hspace{0.5em}\hspace{0.5em}\text{for}\mathrm{\hspace{0.17em}\hspace{0.17em}}r\equiv \mathrm{0}\hspace{0.17em}\mathrm{mod}\hspace{0.17em}\mathrm{8},\hfill \\ {\mathrm{2}}^r+\mathrm{1}+{\mathrm{2}}^{(r+\mathrm{1})/\mathrm{2}}\hfill & \hspace{0.5em}\hspace{0.5em}\text{for}\mathrm{\hspace{0.17em}\hspace{0.17em}}r\equiv \mathrm{1},\mathrm{7}\hspace{0.17em}\mathrm{mod}\hspace{0.17em}\mathrm{8},\hfill \\ {\mathrm{2}}^r+\mathrm{1}-{\mathrm{2}}^{(r+\mathrm{1})/\mathrm{2}}\hfill & \hspace{0.5em}\hspace{0.5em}\text{for}\mathrm{\hspace{0.17em}\hspace{0.17em}}r\equiv \mathrm{3},\mathrm{5}\hspace{0.17em}\mathrm{mod}\hspace{0.17em}\mathrm{8}.\hfill \end{array}\right.\end{array}$$

(30)

Then, for a given integer s satisfying $\mathrm{1}\le s\le N_r-\mathrm{1}$ , we have an $M_i\times N$ sensing matrix ${\mathbf{\Phi }}_{\mathrm{0}}^i$ with

$$\begin{array}{cc}& M_i={\mathrm{2}}^r·\left(N_r-\mathrm{1}\right),\hspace{1em}N={\mathrm{2}}^{rs},\hspace{0.17em}\\ \mu \left({\mathbf{\Phi }}_{\mathrm{0}}^i\right)=\frac{s}{\left(N_r-\mathrm{1}\right)}.\end{array}$$

(31)

Thus,

$$\begin{array}{cc}& \log \left(\frac{N}{M_i}\right)=\log \left(\frac{{\mathrm{2}}^{rs}}{{\mathrm{2}}^r·\left(N_r-\mathrm{1}\right)}\right)=\log \left(\frac{{\mathrm{2}}^{r(s-\mathrm{1})}}{N_r-\mathrm{1}}\right),\end{array}$$

(32)

and the matrix ${\mathbf{\Phi }}_{\mathrm{0}}^i$ satisfies the RIP of order $k<(N_r-\mathrm{1})/s+\mathrm{1}$ . Therefore, we set

$$\begin{array}{cc}& {\mathbf{\Phi }}_i=\frac{\mathrm{1}}{N_r-\mathrm{1}}{\mathbf{\Phi }}_{\mathrm{0}}^i.\end{array}$$

(33)

According to Section 2, our goal is achieved by calling the OMP algorithm

$$\begin{array}{cc}& {\widehat{\mathbf{\theta }}}_i=\text{OMP}\left({\mathbf{y}}_i,{\mathbf{\Phi }}_i{\mathbf{P}}_i,{‖{\mathbf{y}}_i-{\mathbf{\Phi }}_i{\mathbf{P}}_i‖}_{\mathrm{2}}^{\mathrm{2}}<ϵ\right),\hspace{1em}i=\mathrm{1},\dots ,K.\end{array}$$

(34)

5. Numerical Evaluation

We performed computer simulations and provide in this section numerical evaluation results of the proposed method using RSS measurements in indoor environments. Targets were assumed to be randomly placed in a 30 m × 30 m square. We divided this area into $\mathrm{24}\times \mathrm{24}$ grid. In our work, we used the OMP algorithm to compute the sparse solution. Without loss of generality, we assumed that the number of measurements of each target was the same; that is, $M_i=M\mathrm{\hspace{0.17em}\hspace{0.17em}}(i=\mathrm{1},\dots ,K)$ . We chose the elliptic curve in (26) with given r and s.

Figure 2 shows the recovery ratio of the deterministic matrix formed by the elliptic cure $y^{\mathrm{2}}+y=x^{\mathrm{3}}+x$ and the i.i.d. Gaussian matrix. With $r=\mathrm{3}$ and $s=\mathrm{3}$ , we obtained a $\mathrm{32}\times \mathrm{512}$ sensing matrix. For each sparsity level k, $\mathrm{100,000}$ input signals were used to compute the ratio. The results show that the performance of the proposed deterministic matrix is comparable to the i.i.d. Gaussian matrix.

Figure 2

Recovery ratio of a random Gaussian matrix and the proposed deterministic matrix formed by elliptic curve $y^{\mathrm{2}}+y=x^{\mathrm{3}}+x$ with the same size $\mathrm{32}\times \mathrm{512}$ .

Figure 3 illustrates an example of actual multiple target localization. 20 targets were randomly deployed in this area. In our simulations, we employed the RSS indoor model defined in [7]. We have $r=\mathrm{3}$ and $s=\mathrm{3}$ , and signal-to-noise ratio (SNR) was equal to 25 dB. Each location was observed over 100 simulations. The result shows the effectiveness of location recovery from compressive measurement via using the Gaussian random matrix and the proposed deterministic matrix with elliptic curve. The number of RSS measurements was required at least $M={\mathrm{2}}^{\mathrm{3}}({\mathrm{2}}^{\mathrm{3}}-{\mathrm{2}}^{(\mathrm{3}+\mathrm{1})/\mathrm{2}})=\mathrm{32}$ in deterministic sensing matrix case and $M=\mathcal{O}(K\log (N/K))\approx \mathrm{30}$ in the i.i.d. Gaussian matrix case. The simulation result shows that both approaches achieve a comparably high level of accuracy with a similar number of measurements. However, note that only the deterministic construction is feasible in practical use.

Figure 3

Performance of position recovery for 20 targets.

Figure 4 shows localization error (LE) for different SNR levels. Here, the LE is defined as

$$\begin{array}{cc}& \text{LE}=\frac{\mathrm{1}}{K}{\displaystyle \sum }_{i=\mathrm{1}}^K‍{‖{\mathbf{x}}_{\text{estimate}}^i-{\mathbf{x}}_{\text{actual}}^i‖}^{\mathrm{2}}.\end{array}$$

(35)

In this simulation, K was fixed to 5 and the values of $r,s$ were the same as previous simulations. As shown in Figure 4(a), when the RSS measurements were heavily affected by noise with small SNR (0 dB or 5 dB), the LEs of two approaches are almost the same. However, when SNR becomes larger (10 dB or 25 dB), it may affect the LE performance. With large SNR, the LE of the localization using the deterministic matrix is drastically decreased when the number of measurements becomes large, as clearly observed in Figure 4(b).

Figure 4

Localization errors of two approaches with various SNR levels.

The simulation results indicate that multiple target localization using the proposed deterministic sensing matrix can achieve good LE performance which is comparable to that of random sensing matrix. It can be found in the summary statistics in Table 1.

Table 1

The minimum values of location error in meters with respect to various SNR levels using the two approaches.

SNR level (dB)	Sensing matrix
	Random	Deterministic
0	0.01	0.025
5	0.025	0.02
10	0.019	0.03
25	0.03	0.024

6. Conclusion

This paper investigates the problem of multiple target localization in WSNs based on compressive sensing using deterministic sensing matrices. We show that the sensing matrix obtained by taking projections of chosen curve validates our problem formulation. Experimental results show that the OMP using the proposed deterministic sensing matrix compares favorably with existing random sensing matrix in reconstruction performance, while achieving a high accuracy. This approach offers an efficient way in localization process, and it can be also applied in other applications such as error correction, imaging, and secure communication.