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

Authors: Thu L. N. Nguyen; Yoan Shin
Journal: International Journal of Distributed Sensor Networks
 (2015)

---

## 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.


---

## Body

## 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 y=Φx, where Φ is the sensing matrix. In [12, 13, 18], it is shown that a k-sparse signal x is the solution of l0 optimization if every submatrix of Φ is formed by choosing 2k arbitrary columns of Φ with full rank. In [13], it is shown that, for a small k, the l1 problem is equivalent to the l0 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 Figure1 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 Section2, 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
,
(
·
)
-
1, and (·)∗ denote the matrix transpose, inverse, and complex-conjugate operations, respectively. The operations ·0,·1, and ·2 denote l0-norm, l1-norm, and l2-norm, respectively. ConF′/F(P) is conorm of P in the extension F′/F, gcd(m,r) is the greatest common divisor of m and r, l(.) is dimension of the Riemann-Roch space, and 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 signalx be a discrete-time column vector in RN and let Ψ=Ψ1Ψ2⋯ΨN be an orthogonal basis of RN. In practice, this signal vector x can be represented as sparse coefficients by an orthonormal basis Ψ having only K≪N nonzero coefficients. Then we can write(1)x=Ψθ=∑i=1N‍θiΨi,where θi is the ith sample of sparse coefficient of θ, satisfying θ0=K which means(2)#i:θi≠0=K,and Ψi is the ith column of the sparse basis. The compressive sensing aims to recover x from knowledge of(3)y=Φx=∑i=1M‍xiΦior recover θ from knowledge of(4)y=ΦΨθ,where y∈RM, and Φ∈RM×N is the measurement matrix or thesensing matrix of size M×N with M≪N. The solution can be recovered by solving the following equation which is one of the common convex optimization problems:(5)min⁡θθ1suchthaty=Θθ,where Θ=ΦΨ is called the holographic dictionary. In [21], the authors showed that the number of measurements M required for sparse reconstruction via l1-minimization method satisfies M≈O(Klog⁡(N/K))≪N. If the measurement y is affected by unknown noise n, then the information can be expressed as(6)y=Θθ+n,and the minimization problem changes to(7)min⁡θθ1suchthatΘθ-y22<ϵfor a chosen ϵ>0, or the other unconstrained version is given by(8)min⁡θ12Θθ-y22+λθ1for a parameter λ>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,δk) for δk∈(0,1) if(9)1-δku22≤Φu22≤1+δku22holds for all k-sparse vectors u. An upper bound of the sparsity is(10)k≤cMlog⁡⁡N/M,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Φ=Φ1Φ2⋯ΦN and the representation basis Ψ=Ψ1Ψ2⋯ΨN, where Φi and Ψi(i=1,…,N) are their corresponding column vectors, theincoherence between them is defined as the largest correlation as follows:(11)μΦ,Ψ=max⁡1≤i,j≤NNΦi,Ψj.Donoho in [12] showed that (2k-1)μ<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:(12)θ^=argmin⁡θy-Θθ22suchthatθ0≤kor the error-constrained sparse coding problem given by(13)θ^=argmin⁡θθ0suchthaty-Θθ22≤ϵ.Denote the OMP operation as θ^=OMP(y,Θ,ϵ), where ϵ is an upper bound on the norm of the residual error term y-Θθ2. The algorithm can be described by Algorithm 1.Algorithm 1:OMP algorithm.
(1)   procedure OMP(Θ,y,k,ϵ)
(2)    k←1
(3)    θ^←0
(4)    r0←y
(5)    V0←∅
(6)    while  rk2>ϵ  do
(7)     Compute ai=rk-1TΘ:,i for all i∉Vk-1
(8)     Choose vk=argmaxi⁡ai
(9)     Update Vk=Vk-1∪vk
(10)   Compute θ^(Vk)=(Θ(:,Vk))Ty
(11)   Compute rk=y-(Θ(:,Vk))θ^(Vk)
(12)   Set k=k+1.
(13)  end while
(14)  return  θ^k               ⊳ Approximated solution
(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×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 RN,(i)
(k,ϵ,δ) StRIP matrix: A sensing matrix ΦM×N is said to be a (k,ϵ,δ) StRIP matrix if, for any k-sparse signal α∈RN, 1-ϵα2≤1/NΦα2≤1+ϵα2 holds with probability exceeding 1-δ;(ii)
(k,ϵ,δ) UStRIP matrix: A sensing matrix ΦM×N is said to be (k,ϵ,δ) UStRIP matrix, if, for any k-sparse signal α∈RN, Φ is (k,ϵ,δ) StRIP matrix and {β∈RN:Φα=Φβ}={α} holds with probability exceeding 1-δ.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 l1 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.DenoteFp as the finite field of order p where p is a prime power. C is an algebraic curve over Fp. Let P be the set of rational points of C/Fq(14)P=P=a1,…,an∣ai∈Fp.Note that, given Fp, the set P×Fp has |P|×p elements. Choose a divisor A of C such that deg⁡(A)<|C| and supp(A)∩C=∅. Then, by using Riemann-Rock Theorem in the Appendix, we have l(A)=deg⁡A+1-g. Order the element of P×Fp lexicographically as (0,0),(0,1),…,({|P|-1},p). For any f∈P, define a binary column vector vf which has the form(15)f0,0,…,f0,p-1,f1,0,…,f1,p-1,…,f|P|-1,0,…,f|P|-1,p-1T,where(16)fi,j=1iffi=j0,otherwisefor 0≤i≤|P|-1 and 0≤j≤p-1. The column vector {vf∣f∈P} forms a |P|p×pl(A) matrix Φ0. Then we have the following theorem.Theorem 1.
Suppose thatΦ=(1/P)Φ0; then Φ is a sensing matrix satisfying the RIP with coherence μ(Φ)≤deg⁡A/|P|.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.


## 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 signalx be a discrete-time column vector in RN and let Ψ=Ψ1Ψ2⋯ΨN be an orthogonal basis of RN. In practice, this signal vector x can be represented as sparse coefficients by an orthonormal basis Ψ having only K≪N nonzero coefficients. Then we can write(1)x=Ψθ=∑i=1N‍θiΨi,where θi is the ith sample of sparse coefficient of θ, satisfying θ0=K which means(2)#i:θi≠0=K,and Ψi is the ith column of the sparse basis. The compressive sensing aims to recover x from knowledge of(3)y=Φx=∑i=1M‍xiΦior recover θ from knowledge of(4)y=ΦΨθ,where y∈RM, and Φ∈RM×N is the measurement matrix or thesensing matrix of size M×N with M≪N. The solution can be recovered by solving the following equation which is one of the common convex optimization problems:(5)min⁡θθ1suchthaty=Θθ,where Θ=ΦΨ is called the holographic dictionary. In [21], the authors showed that the number of measurements M required for sparse reconstruction via l1-minimization method satisfies M≈O(Klog⁡(N/K))≪N. If the measurement y is affected by unknown noise n, then the information can be expressed as(6)y=Θθ+n,and the minimization problem changes to(7)min⁡θθ1suchthatΘθ-y22<ϵfor a chosen ϵ>0, or the other unconstrained version is given by(8)min⁡θ12Θθ-y22+λθ1for a parameter λ>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,δk) for δk∈(0,1) if(9)1-δku22≤Φu22≤1+δku22holds for all k-sparse vectors u. An upper bound of the sparsity is(10)k≤cMlog⁡⁡N/M,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Φ=Φ1Φ2⋯ΦN and the representation basis Ψ=Ψ1Ψ2⋯ΨN, where Φi and Ψi(i=1,…,N) are their corresponding column vectors, theincoherence between them is defined as the largest correlation as follows:(11)μΦ,Ψ=max⁡1≤i,j≤NNΦi,Ψj.Donoho in [12] showed that (2k-1)μ<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:(12)θ^=argmin⁡θy-Θθ22suchthatθ0≤kor the error-constrained sparse coding problem given by(13)θ^=argmin⁡θθ0suchthaty-Θθ22≤ϵ.Denote the OMP operation as θ^=OMP(y,Θ,ϵ), where ϵ is an upper bound on the norm of the residual error term y-Θθ2. The algorithm can be described by Algorithm 1.Algorithm 1:OMP algorithm.
(1)   procedure OMP(Θ,y,k,ϵ)
(2)    k←1
(3)    θ^←0
(4)    r0←y
(5)    V0←∅
(6)    while  rk2>ϵ  do
(7)     Compute ai=rk-1TΘ:,i for all i∉Vk-1
(8)     Choose vk=argmaxi⁡ai
(9)     Update Vk=Vk-1∪vk
(10)   Compute θ^(Vk)=(Θ(:,Vk))Ty
(11)   Compute rk=y-(Θ(:,Vk))θ^(Vk)
(12)   Set k=k+1.
(13)  end while
(14)  return  θ^k               ⊳ Approximated solution
(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×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 RN,(i)
(k,ϵ,δ) StRIP matrix: A sensing matrix ΦM×N is said to be a (k,ϵ,δ) StRIP matrix if, for any k-sparse signal α∈RN, 1-ϵα2≤1/NΦα2≤1+ϵα2 holds with probability exceeding 1-δ;(ii)
(k,ϵ,δ) UStRIP matrix: A sensing matrix ΦM×N is said to be (k,ϵ,δ) UStRIP matrix, if, for any k-sparse signal α∈RN, Φ is (k,ϵ,δ) StRIP matrix and {β∈RN:Φα=Φβ}={α} holds with probability exceeding 1-δ.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 l1 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.DenoteFp as the finite field of order p where p is a prime power. C is an algebraic curve over Fp. Let P be the set of rational points of C/Fq(14)P=P=a1,…,an∣ai∈Fp.Note that, given Fp, the set P×Fp has |P|×p elements. Choose a divisor A of C such that deg⁡(A)<|C| and supp(A)∩C=∅. Then, by using Riemann-Rock Theorem in the Appendix, we have l(A)=deg⁡A+1-g. Order the element of P×Fp lexicographically as (0,0),(0,1),…,({|P|-1},p). For any f∈P, define a binary column vector vf which has the form(15)f0,0,…,f0,p-1,f1,0,…,f1,p-1,…,f|P|-1,0,…,f|P|-1,p-1T,where(16)fi,j=1iffi=j0,otherwisefor 0≤i≤|P|-1 and 0≤j≤p-1. The column vector {vf∣f∈P} forms a |P|p×pl(A) matrix Φ0. Then we have the following theorem.Theorem 1.
Suppose thatΦ=(1/P)Φ0; then Φ is a sensing matrix satisfying the RIP with coherence μ(Φ)≤deg⁡A/|P|.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 withN points (grid); K targets are located in an isotropic area, where their positions are unknown. Wireless devices measure RSS from all the targets with Mi(i=1,…,K) available measurements, while the number of measurements is much smaller than the grid size (Mi≪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 aN×1 vector as follows:(17)θi=00⋯1⋯0T,i=1,…,K.Each θi has all elements equal to zeros, except θi(n)=1. Here n is the index on grid point where ith target is located. Then, with K targets we obtain an N×K matrix(18)θ=θ1θ2⋯θK.Denotexi∈RN as the measured signal which is recorded at the ith target. Then each signal xi is given a distinct measurement matrix Φi∈RMi×N which is a deterministic matrix. The measurement yi can be written as(19)yi=Φixi+ni,i=1,…,K.Collecting all these equations, we can write the following form:(20)y=Φx+n,where n is a measurement noise. In detail, each term in (20) can be expressed as(21)x=x1x2⋮xK,y=y1y2⋮yK,Φ=Φ10⋯00Φ2⋯0⋮⋮⋱⋮00⋯ΦK,where x∈RKN, y∈R∑i=1K‍Mi, Φ∈R∑i=1K‍Mi×KN, and n∈R∑i=1K‍Mi.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(22)x=Pθ,where x∈RKN and P is KN×KN RSS sparsity basis matrix. It is clear that x is a K-sparse vector since x0=K.


### 4.1. RSS Information MatrixP

TheKN×KN sparsity basis matrix P can be generated using the radio propagation channel model as(23)P=P10⋯00P2⋯0⋮⋮⋱⋮00⋯PK.Each Pu(u=1,…,K) is an Mi×N submatrix whose element has the form(24)Puij=p0-10nplog⁡10dijd0,i,j=1,…,N.[Pu]ij is the received signal power in dBm, np is the path loss component, dij is the real distance between transmitter and receiver, and d0 is reference distance for the far field with receive power p0.


### 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 Fp to its extension Fpr. We exploit this idea in our problem. Note that the algebraic curves over Fpr may have good properties such as large dimension and minimum distance, whereas the restricted algebraic curves P∣Fp may be very poor since the dimension of P∣Fp may be less than the dimension of Pr. Hence, by using the following theorem, we can replace Fp with Fqr to construct a matrix with large size. In [30] the author shows the following.Theorem 2.
DenoteF as algebraic function field of genus g whose constant field is the finite field Fp, F/T as an algebraic function field, F′/T as a finite separable extension, and T′ as the constant field of F′. Thus, T′/T is a finite separable extension as well. For each r>1, there exists exactly one extension Fpr/Fp of degree r with Fpr⊆F¯p and one sets Fr=FFpr⊆F¯. Therefore, one has the following. (a)
Fr/F is Galois with a cyclic Galois group of order r (Fr/F is a cyclic extension of degree r). The Galois group Gal(Fr/F) is generated by Frobenius automorphism σ which acts on Fpr by σ(α)=αp.(b)
Fpr is the full constant field of Fr.(c)
LetP∈PFPF={P∣PisaplaceofF/T} be a place of degree m. Then ConFr/F(P)=P1+⋯+Pd with d=gcd(m,r), pairwise distinct places Pi∈PFr and deg⁡Pi=m/d.IfT is a perfect field, denote Nr as the number of places of degree one in the constant field extension Fr. With special case T=F2, we have(25)N1=3,N2=5,N3=24.That means each of the three places of F2(x) of degree one has a unique extension of degree one in PF 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)
ConsiderF=F2x; there is only elliptic function field F/F2 with five places of F/F2 of genus g=1:(26)y2+y=x3+x.(ii)
LetF=Fq2 with(27)xp+1+yp+1=1,genus g=p(p-1)/2, and the number of places of degree one is N=1+p3. For instance, in (26) the number Nr of places of degree one of the function field Fr/F2r is given by [30](28)Nr=2r+1-αr+α∗r,where α,α∗∈C are the reciprocals of the root of(29)Lt=1+2t+2t2=1-αt1-α∗t,with α=-1+i=ω2, ω=exp⁡(3πi/4). Hence(30)Nr=2r+1forr≡2,6mod⁡8,2r+1+2·2r/2forr≡4mod⁡8,2r+1-2·2r/2forr≡0mod⁡8,2r+1+2(r+1)/2forr≡1,7mod⁡8,2r+1-2(r+1)/2forr≡3,5mod⁡8.Then, for a given integer s satisfying 1≤s≤Nr-1, we have an Mi×N sensing matrix Φ0i with(31)Mi=2r·Nr-1,N=2rs,μΦ0i=sNr-1.Thus,(32)log⁡NMi=log⁡2rs2r·Nr-1=log⁡2r(s-1)Nr-1,and the matrix Φ0i satisfies the RIP of order k<(Nr-1)/s+1. Therefore, we set(33)Φi=1Nr-1Φ0i.According to Section 2, our goal is achieved by calling the OMP algorithm(34)θ^i=OMPyi,ΦiPi,yi-ΦiPi22<ϵ,i=1,…,K.


## 4.1. RSS Information MatrixP

TheKN×KN sparsity basis matrix P can be generated using the radio propagation channel model as(23)P=P10⋯00P2⋯0⋮⋮⋱⋮00⋯PK.Each Pu(u=1,…,K) is an Mi×N submatrix whose element has the form(24)Puij=p0-10nplog⁡10dijd0,i,j=1,…,N.[Pu]ij is the received signal power in dBm, np is the path loss component, dij is the real distance between transmitter and receiver, and d0 is reference distance for the far field with receive power p0.


## 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 Fp to its extension Fpr. We exploit this idea in our problem. Note that the algebraic curves over Fpr may have good properties such as large dimension and minimum distance, whereas the restricted algebraic curves P∣Fp may be very poor since the dimension of P∣Fp may be less than the dimension of Pr. Hence, by using the following theorem, we can replace Fp with Fqr to construct a matrix with large size. In [30] the author shows the following.Theorem 2.
DenoteF as algebraic function field of genus g whose constant field is the finite field Fp, F/T as an algebraic function field, F′/T as a finite separable extension, and T′ as the constant field of F′. Thus, T′/T is a finite separable extension as well. For each r>1, there exists exactly one extension Fpr/Fp of degree r with Fpr⊆F¯p and one sets Fr=FFpr⊆F¯. Therefore, one has the following. (a)
Fr/F is Galois with a cyclic Galois group of order r (Fr/F is a cyclic extension of degree r). The Galois group Gal(Fr/F) is generated by Frobenius automorphism σ which acts on Fpr by σ(α)=αp.(b)
Fpr is the full constant field of Fr.(c)
LetP∈PFPF={P∣PisaplaceofF/T} be a place of degree m. Then ConFr/F(P)=P1+⋯+Pd with d=gcd(m,r), pairwise distinct places Pi∈PFr and deg⁡Pi=m/d.IfT is a perfect field, denote Nr as the number of places of degree one in the constant field extension Fr. With special case T=F2, we have(25)N1=3,N2=5,N3=24.That means each of the three places of F2(x) of degree one has a unique extension of degree one in PF 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)
ConsiderF=F2x; there is only elliptic function field F/F2 with five places of F/F2 of genus g=1:(26)y2+y=x3+x.(ii)
LetF=Fq2 with(27)xp+1+yp+1=1,genus g=p(p-1)/2, and the number of places of degree one is N=1+p3. For instance, in (26) the number Nr of places of degree one of the function field Fr/F2r is given by [30](28)Nr=2r+1-αr+α∗r,where α,α∗∈C are the reciprocals of the root of(29)Lt=1+2t+2t2=1-αt1-α∗t,with α=-1+i=ω2, ω=exp⁡(3πi/4). Hence(30)Nr=2r+1forr≡2,6mod⁡8,2r+1+2·2r/2forr≡4mod⁡8,2r+1-2·2r/2forr≡0mod⁡8,2r+1+2(r+1)/2forr≡1,7mod⁡8,2r+1-2(r+1)/2forr≡3,5mod⁡8.Then, for a given integer s satisfying 1≤s≤Nr-1, we have an Mi×N sensing matrix Φ0i with(31)Mi=2r·Nr-1,N=2rs,μΦ0i=sNr-1.Thus,(32)log⁡NMi=log⁡2rs2r·Nr-1=log⁡2r(s-1)Nr-1,and the matrix Φ0i satisfies the RIP of order k<(Nr-1)/s+1. Therefore, we set(33)Φi=1Nr-1Φ0i.According to Section 2, our goal is achieved by calling the OMP algorithm(34)θ^i=OMPyi,ΦiPi,yi-ΦiPi22<ϵ,i=1,…,K.


## 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 24×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, Mi=M(i=1,…,K). We chose the elliptic curve in (26) with given r and s.Figure2 shows the recovery ratio of the deterministic matrix formed by the elliptic cure y2+y=x3+x and the i.i.d. Gaussian matrix. With r=3 and s=3, we obtained a 32×512 sensing matrix. For each sparsity level k, 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 curvey2+y=x3+x with the same size 32×512.Figure3 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=3 and s=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=23(23-2(3+1)/2)=32 in deterministic sensing matrix case and M=O(Klog⁡(N/K))≈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.Figure4 shows localization error (LE) for different SNR levels. Here, the LE is defined as(35)LE=1K∑i=1K‍xestimatei-xactuali2.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.
(a)
SNR = 0 dB and 5 dB
(b)
SNR = 10 dB and 25 dBThe 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 Table1.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.



---

*Source: 947016-2015-08-25.xml*