# Adaptive Localization in Wireless Sensor Network through Bayesian Compressive Sensing

Authors: Zuoxin Xiahou; Xiaotong Zhang
Journal: International Journal of Distributed Sensor Networks
 (2015)

---

## Abstract

The estimation of the localization of targets in wireless sensor network is addressed within the Bayesian compressive sensing (BCS) framework. BCS can estimate not only target locations but also noise variance of the environment. Furthermore, we provide adaptive iteration BCS localization (AIBCSL) algorithm, which is based on BCS and will choose measurement sensors according to the environment adaptively with only an initial value, while other frameworks require prior knowledge such as target numbers to choose measurements. AIBCSL suppose that environment noise variance is identical in interested area in a short period of time and change measurement numbers until terminal condition is reached. To suppress noise, we optimize estimation result by energy threshold strategy (ETS), which takes that transmit energy of noise focused on single grid is much lower than signal into consideration. And multisnapshot BCS (MT-BCS) will be explained and lead to a good result in low SNR level situation.


---

## Body

## 1. Introduction

Wireless sensor network (WSN) has enjoyed tremendous popularity in the last decades [1, 2]. Around it there are lots of subjects. Estimating the localization of target in wireless sensor network is one of the hot topics [3]. Localization subject in most of self-organization networks has experienced excited discussion in both single target environment [4] and multitargets [5] environment, although the location of target is known to sources in some situations which are merely for data aggregation or system management, such as networks based on industrial wireless communication protocol WIA-PA [6]. Wireless network localization often appears in smart applications or tracking system such as road traffic monitoring, health monitoring, or military target tracking, which have enjoyed tremendous popularity. State-of-the-art paper gives to the interested reader several effective approaches proposed in the last decades for localization in WSN. The measurement techniques in wireless sensor network localization can be classified into three categories [3], which include angle-of-arrival estimation (AOA), distance related measurements, and RSS profiling techniques. However, the custom methods lead to poor performance in multitargets situation.In this paper, we will introduce a novel method to wireless sensor network localization. We assume that target numbers are far less than the number of grids utilized to represent the locations of the targets. Thus target locations could be considered as sparse signal. We will consider using Bayesian compressive sensing (BCS) standpoint to solve the localization problem. BCS originated from custom compressive sensing (CS), while it employs Bayesian formalism to estimate the underlying signal. CS theory has been applied to the area of localization or target counting in [7]. However, there is no information showing that BCS method has been introduced to wireless sensor network localization. BCS have many merits compared to custom CS: (i) BCS provides not only estimation result of sparse signal but also the error message (also be known as error bars); (ii) the BCS framework provides an estimate for the posterior density function of additive noise encountered when implementing the compressive measurements. BCS algorithm is better than many other custom CS algorithms such as OMP, L1-norm, and LASSO. Another attractive advantage is that BCS is suitable for developing adaptive method by using message from error bars. Our paper analyzes the basis of BCS and introduces an adaptive iteration BCS method later. Adaptive iteration BCS will improve the accuracy of localization compared to BCS, which can be seen in the simulation section. Except for that, our paper proposes an energy threshold strategy for postprocess and yields good effect.The original work about CS is [8]. CS is a novel sampling theory that can reconstruct s sparse signal from a small number of measurements [9]. There are many methods for recovering signal from sparse signal, which include L1-norm in [8], OMP in [10], and LASSO in [11]. Reference[7] has applied CS to the area of target count and localization in wireless sensor network, that is, the first paper to rigorously justify the validity of the problem formulation of CS localization in wireless sensor network. Since CS is put forward, there are many branches from it, such as distributed CS and Bayesian CS. Reference [12] is a work of using distributed CS in wireless sensor network localization. Bayesian compressive sensing was proposed by Ji and Xue in 2008 [13]. Bayesian compressive sensing uses Bayesian standpoint to explain CS problem and has never been seen in the area of wireless sensor network. Reference [14] comes up with an adaptive Bayesian compressed sensing algorithm and applied it to wireless network. Reference [15] executed DOA estimate by Bayesian estimate in antenna array, which directly links measurements with signal directions and an energy method could been applied. Reference [16] utilized a hierarchical form of the Laplace prior to model the sparsity of the unknown signal and in that way provided a method to estimate the localization by BCS in this paper. From another perspective, CS is welcome in the area of multitarget localization [17].The organization of this paper is as follows. In Section2, we will first explain the basis of BCS and multisnapshot BCS. Localization model and adaptive iteration BCS algorithm is demonstrated in the second part of Section 2. Section 3 is our simulation work and Section 4 concludes merits and application scenarios of our method.


## 2. Materials and Methods

### 2.1. Bayesian Compressive Sensing

Compressive sensing (CS) theory implies that if a signal has a sparse representation by a certain basis then it can be recovered from fewer measurements than Nyquist sampling theorem. A signalx∈RN will be represented by a N×N transform basis Ψ and a sparse signal s, formulizing that(1)x=Ψs.If s has only K entries (s0=K) with K≪N being not equal zero, signal x is called K-sparse. Assume we get measurements y∈RN; y and x are expressed to be linear formula:(2)y=Φx=ΦΨs=Θs,where Φ is M×1 measurement vector, such that Θ is a M×N projection matrix. Take zero mean Gaussian noise ε~N(0,δε2) into consideration: (3)y=Θs+ε.Equation (3) depicts the projection of sparse signal s and measurements y. If we can recover y of N dimension from s of M dimension, then less memory costs and calculation costs will be taken.


#### 2.1.1. Single-Snapshot BCS-Based Sparse Signal Estimation (ST-BCS)

Bayesian compressive sensing (BCS) will recovery from Bayesian estimation standpoint. Because ε is a zero mean Gaussian random, the likelihood model of recovering y from s is (4)p(y∣s,δε2)=(2πδε2)-M/2exp⁡-12δε2y-Θs2.According to Bayesian estimation theorem, the analysis of CS problem turns out to be a priori constrained optimization problem. The priori condition is that s is a sparse vector (s0=K). The posterior probability [16] is(5)p(s∣λ)=∏i=1NNsi∣0,λi-1,where N(si∣0,λi-1) means that si is Gaussian random where mean is zero and variance is λi-1. λ=λ1,λ2,…,λN is super-parameters at the service of solving priori probability, which will control the sparse level of s.BCS provides a method to estimates and even noise covariance by only a few measurements y through maximize posterior probability. In that viewpoint, posterior probability of s and δε2 are maximized; that is, s^=argmax⁡s⁡p[s,δε2,λ]∣y. Posterior probability is(6)p[s,δε2,λ]∣y=p(s∣δε2,y,λ)p([δε2,λ]∣y).p
(
s
∣
δ
ε
2
,
y
,
λ
) provides the estimation of s, and p([δε2,λ]∣y) gives the result of noise estimation. Our target is maximizing the first item [16]. Formulize it by multivariable Gaussian distribution [16]:(7)p(s∣δε2,y,λ)=2π-M+1/2Σ-1/2exp⁡⁡-12s^-μTΣ-1s^-μ,where mean and covariance are(8)μ=1δε2ΣΘTy,Σ=1δε2ΘTΘ+Λ-1,Λ=diag(λ1,λ2,…,λN).Thus, we must first estimate u and Σ to accomplish the task above. Assuming λ0=1/δε2, we use maximum likelihood estimation (MLE) to get parameters λ0,λ. The logarithm function is (9)Lλ0,λ=log⁡⁡s∣λ0,λ=-12Mlog⁡⁡2π+log⁡⁡C+sTC-1s,where C=δ2I+ΘΛ-1ΘT and I is eye matrix. max⁡⁡L(λ0,λ) with respect to λ0 and λ will get iteration relationship as below:(10)λinew=1-λiΣiiμi2,i∈{1,2,…,N},λ0new=M-∑i=1N(1-λiΣii)y-Θμ22,where Σii is ith diagonal element of Σ. Given the initial values of λ0,λ, update Σ and μ by (8) and (10) until convergence. For the reason that BCS will return with Σ, it is superior to custom CS method when applied to adaptive estimate. BCS estimation result is [15](11)s^=1δε2ΘTΘδε2+Λ-1ΘTy.


#### 2.1.2. Multisnapshot BCS-Based Sparse Signal Estimation (MT-BCS)

To suppress the noise, take the relevant of more than one signal in a short period of time into account. DoW samples at W different times, and then(12)yt=Θst+εt,t={1,2,…,W}.Maximizing posterior of s turns to be(13)s^=1W∑t=1Warg⁡max⁡stp[st,δε2,λ]∣yt,t={1,2,…,W}.Super-parameters can iterated by following equations:(14)λinew=W-λi∑j=1WΣii(j)∑j=1Wμi2(j),i∈{1,2,…,N},λ0new=∑j=1WM-∑i=1N(1-λiΣii(j))∑j=1Wy(j)-Θ(j)μ(j)22.Similarly but not the same, estimated result of s is as below in MT-BCS: (15)s^=1W∑j=1WΘTΘ+Λ-1Θ(j)Ty(j).


### 2.2. Location Sensing Formulation

#### 2.2.1. Localization Model

First we divide localization area to beN=nx×ny grids. Then assign index for grids from 1~N as Figure 1. The coordinate of index is calculated by (16)xi=mod⁡i,nx,y(i)=i-mod⁡(i,nx)+1.Assume T targets (also known as sources) are distributed sporadic in those areas, such that they can be represented by a sparse vector s=s1,s2,…,sNT, where si represents the energy of target in ith grid area. If there is no target in ith grid, si=0.Figure 1
Localization girds and index.Energy attenuation [3] from ith grid to jth gird is(17)Pr(dij)=PiGijdijα,dij>d0Pi,dij≤d0,where Pi is signal intensity in ith grid and d0 is a very short reference distance. dij is Euclidean distance from ith grid to jth gird. Gij is Rayleigh fading factor from i to j which is related to specific environment. α is distance factor, often choose between [2.0, 5.0].Combining (1) and (13),(18)Ψ=1G21d21α⋯GN1dN1αG12d12α1⋯GN2dN2α⋮⋮⋱⋮G1Nd1NαG2Nd2Nα⋯1,(19)s=P1,P2,…,PNT.The signal x=x1,x2,x3,…,xNT is the energy intensity in ith gird. According CS theorem, M (k<M≪N) measurements that satisfy RIP rules [8] are able to recover signal without loss. Thus, we deploy M sensors in interested areas. In (2), if there is sensor in grid j, Φ(i,j)=1; otherwise, Φ(i,j)=0. We also need consider noise such as (3).


#### 2.2.2. BCS Based Adaptive Localization

Compared with custom CS method, BCS not only provides sparse estimation result, but also gives estimation of noise. In this section, we develop an adaptive BCS algorithm that will choose measurements adaptively for target localization in wireless sensor network. The algorithm assumes that noises in the interested area are consistent, which means that the variances of noise in anywhere of interested area are identical in a short period of time. Measurement numbers change based on the feedback of variances of noise by BCS estimation, until the inconsistency of variances comes to be a small value.At the beginning, we chooseM1 sensors randomly (that is an initial value) by primary device to acquire signal from interested gird area. The BCS estimated noise variance of those sensors is δ(1)2={δ112,δ212,…,δK112}, where K(1) means that signal is K(1)-sparse at the first iteration. We develop a constraint condition then, and dM sensors will be increased from the next iteration if that condition is not satisfied. The approach of choosing the dM sensors comes to two situations: (i) if there is no sensor in the grid area localized by BCS at the last iteration, we will increase a measurement in that grid and (ii) if there have been sensor in the grid area localized by BCS at the last iteration, we choose another grid that without been measured randomly. Set Bayesian estimation error δ(a)2={δ1(a)2,δ2(a)2,…,δK(a)(a)2} at the ath iteration, where K(a) means that signal is K(a)-sparse. There are two iteration termination (constraint) conditions used in our paper. One of them is the comparison of ξ1 with threshold η1, and the expression of ξ1 is(20)ξ1=δδ(a)2μ(a)-δδ(a-1)2μ(a-1),μ(a),μ(a-1)≠00,μ(a)orμ(a-1)=0.ξ1 represents the convergence rate in some degree, which put forward that the mean and variance change little at the convergence process. Second, consider that the Gaussian random is identical anywhere in the interested area, such that we let ξ2=δδ(a)2 be reasonable. The combination of ξ1 and ξ2 comes to be (21)ξ=ξ1<η1,ξ2<η2,Strongestconditionξ1<η1ξ2<η2ξ1<η1orξ2<η2,Weakestcondition.Algorithm 1 gives the whole adaptive algorithm procedure.Algorithm 1:Adaptive iteration BCS localization (AIBCSL).
(
1)  Set  ξ1=Inf, ξ2=Inf, a=1, Given initial sensor number M=M1
(2)  R=randperm(N). Set {M1}=R1:M1.
(3)  While  a<max⁡_iteration and ξ is false
(4)    Update Θ.
(5)    s,idx,K(a),δ(a)2=BCSMa,Θ.
(6)    Determine mean and variance of δ(a)2=δ1(a)2,δ2(a)2,…,δKa(a)2
μ(a)=1K(a)∑i=1K(a)δi(a)2,δδ(a)2=1K(a)∑i=1K(a)δi(a)2-μ(a)2
(7)    Calculate ξ by (21).
(8)    a=a+1
(9)    dM=length(idx), Ma+1=Ma+dM
(10)  Increase acquisition from the added dM sensors.
{Ma+1}=unique{Ma,idx,R~}, where R~ contains values from R to satisfy that Ma+1=Ma+dM.
(11) End
(12) Return grids (locations) of target idx.


#### 2.2.3. Strategy to Determine Targets

According to (19), s is K-sparse vector. BCS localization returns the energy result of all N locations. Random noise will increase error rate. In this section, we assume that energy of noise source is much less than true target, such that we can estimate targets’ location by energy threshold strategy (ETS) further [15]. More specifically, the entries of estimated sparse signal are sorted according to their energy, sk2,k=1,…,K, from high to low, such that idx1=max⁡k⁡sk2 and idxK=min⁡k⁡sk2, where idxk means sort index. Setting threshold ηs, algorithm only reserves parts of all targets with the maximal energy. The determined algorithm by energy threshold is depicted as Algorithm 2.Algorithm 2:Energy threshold strategy (ETS).
(
1) Set  k=1, SSk=0
(2) [S,idx]=sort(|sk|2, “descend”)
(3) While  k<=K and SSk<ηs
(4)  SSk=SSk+Sk,
(5)  k=k+1
(6) End
(7) Return targets’ position {idx1,…,idxk}


## 2.1. Bayesian Compressive Sensing

Compressive sensing (CS) theory implies that if a signal has a sparse representation by a certain basis then it can be recovered from fewer measurements than Nyquist sampling theorem. A signalx∈RN will be represented by a N×N transform basis Ψ and a sparse signal s, formulizing that(1)x=Ψs.If s has only K entries (s0=K) with K≪N being not equal zero, signal x is called K-sparse. Assume we get measurements y∈RN; y and x are expressed to be linear formula:(2)y=Φx=ΦΨs=Θs,where Φ is M×1 measurement vector, such that Θ is a M×N projection matrix. Take zero mean Gaussian noise ε~N(0,δε2) into consideration: (3)y=Θs+ε.Equation (3) depicts the projection of sparse signal s and measurements y. If we can recover y of N dimension from s of M dimension, then less memory costs and calculation costs will be taken.


### 2.1.1. Single-Snapshot BCS-Based Sparse Signal Estimation (ST-BCS)

Bayesian compressive sensing (BCS) will recovery from Bayesian estimation standpoint. Because ε is a zero mean Gaussian random, the likelihood model of recovering y from s is (4)p(y∣s,δε2)=(2πδε2)-M/2exp⁡-12δε2y-Θs2.According to Bayesian estimation theorem, the analysis of CS problem turns out to be a priori constrained optimization problem. The priori condition is that s is a sparse vector (s0=K). The posterior probability [16] is(5)p(s∣λ)=∏i=1NNsi∣0,λi-1,where N(si∣0,λi-1) means that si is Gaussian random where mean is zero and variance is λi-1. λ=λ1,λ2,…,λN is super-parameters at the service of solving priori probability, which will control the sparse level of s.BCS provides a method to estimates and even noise covariance by only a few measurements y through maximize posterior probability. In that viewpoint, posterior probability of s and δε2 are maximized; that is, s^=argmax⁡s⁡p[s,δε2,λ]∣y. Posterior probability is(6)p[s,δε2,λ]∣y=p(s∣δε2,y,λ)p([δε2,λ]∣y).p
(
s
∣
δ
ε
2
,
y
,
λ
) provides the estimation of s, and p([δε2,λ]∣y) gives the result of noise estimation. Our target is maximizing the first item [16]. Formulize it by multivariable Gaussian distribution [16]:(7)p(s∣δε2,y,λ)=2π-M+1/2Σ-1/2exp⁡⁡-12s^-μTΣ-1s^-μ,where mean and covariance are(8)μ=1δε2ΣΘTy,Σ=1δε2ΘTΘ+Λ-1,Λ=diag(λ1,λ2,…,λN).Thus, we must first estimate u and Σ to accomplish the task above. Assuming λ0=1/δε2, we use maximum likelihood estimation (MLE) to get parameters λ0,λ. The logarithm function is (9)Lλ0,λ=log⁡⁡s∣λ0,λ=-12Mlog⁡⁡2π+log⁡⁡C+sTC-1s,where C=δ2I+ΘΛ-1ΘT and I is eye matrix. max⁡⁡L(λ0,λ) with respect to λ0 and λ will get iteration relationship as below:(10)λinew=1-λiΣiiμi2,i∈{1,2,…,N},λ0new=M-∑i=1N(1-λiΣii)y-Θμ22,where Σii is ith diagonal element of Σ. Given the initial values of λ0,λ, update Σ and μ by (8) and (10) until convergence. For the reason that BCS will return with Σ, it is superior to custom CS method when applied to adaptive estimate. BCS estimation result is [15](11)s^=1δε2ΘTΘδε2+Λ-1ΘTy.


### 2.1.2. Multisnapshot BCS-Based Sparse Signal Estimation (MT-BCS)

To suppress the noise, take the relevant of more than one signal in a short period of time into account. DoW samples at W different times, and then(12)yt=Θst+εt,t={1,2,…,W}.Maximizing posterior of s turns to be(13)s^=1W∑t=1Warg⁡max⁡stp[st,δε2,λ]∣yt,t={1,2,…,W}.Super-parameters can iterated by following equations:(14)λinew=W-λi∑j=1WΣii(j)∑j=1Wμi2(j),i∈{1,2,…,N},λ0new=∑j=1WM-∑i=1N(1-λiΣii(j))∑j=1Wy(j)-Θ(j)μ(j)22.Similarly but not the same, estimated result of s is as below in MT-BCS: (15)s^=1W∑j=1WΘTΘ+Λ-1Θ(j)Ty(j).


## 2.1.1. Single-Snapshot BCS-Based Sparse Signal Estimation (ST-BCS)

Bayesian compressive sensing (BCS) will recovery from Bayesian estimation standpoint. Because ε is a zero mean Gaussian random, the likelihood model of recovering y from s is (4)p(y∣s,δε2)=(2πδε2)-M/2exp⁡-12δε2y-Θs2.According to Bayesian estimation theorem, the analysis of CS problem turns out to be a priori constrained optimization problem. The priori condition is that s is a sparse vector (s0=K). The posterior probability [16] is(5)p(s∣λ)=∏i=1NNsi∣0,λi-1,where N(si∣0,λi-1) means that si is Gaussian random where mean is zero and variance is λi-1. λ=λ1,λ2,…,λN is super-parameters at the service of solving priori probability, which will control the sparse level of s.BCS provides a method to estimates and even noise covariance by only a few measurements y through maximize posterior probability. In that viewpoint, posterior probability of s and δε2 are maximized; that is, s^=argmax⁡s⁡p[s,δε2,λ]∣y. Posterior probability is(6)p[s,δε2,λ]∣y=p(s∣δε2,y,λ)p([δε2,λ]∣y).p
(
s
∣
δ
ε
2
,
y
,
λ
) provides the estimation of s, and p([δε2,λ]∣y) gives the result of noise estimation. Our target is maximizing the first item [16]. Formulize it by multivariable Gaussian distribution [16]:(7)p(s∣δε2,y,λ)=2π-M+1/2Σ-1/2exp⁡⁡-12s^-μTΣ-1s^-μ,where mean and covariance are(8)μ=1δε2ΣΘTy,Σ=1δε2ΘTΘ+Λ-1,Λ=diag(λ1,λ2,…,λN).Thus, we must first estimate u and Σ to accomplish the task above. Assuming λ0=1/δε2, we use maximum likelihood estimation (MLE) to get parameters λ0,λ. The logarithm function is (9)Lλ0,λ=log⁡⁡s∣λ0,λ=-12Mlog⁡⁡2π+log⁡⁡C+sTC-1s,where C=δ2I+ΘΛ-1ΘT and I is eye matrix. max⁡⁡L(λ0,λ) with respect to λ0 and λ will get iteration relationship as below:(10)λinew=1-λiΣiiμi2,i∈{1,2,…,N},λ0new=M-∑i=1N(1-λiΣii)y-Θμ22,where Σii is ith diagonal element of Σ. Given the initial values of λ0,λ, update Σ and μ by (8) and (10) until convergence. For the reason that BCS will return with Σ, it is superior to custom CS method when applied to adaptive estimate. BCS estimation result is [15](11)s^=1δε2ΘTΘδε2+Λ-1ΘTy.


## 2.1.2. Multisnapshot BCS-Based Sparse Signal Estimation (MT-BCS)

To suppress the noise, take the relevant of more than one signal in a short period of time into account. DoW samples at W different times, and then(12)yt=Θst+εt,t={1,2,…,W}.Maximizing posterior of s turns to be(13)s^=1W∑t=1Warg⁡max⁡stp[st,δε2,λ]∣yt,t={1,2,…,W}.Super-parameters can iterated by following equations:(14)λinew=W-λi∑j=1WΣii(j)∑j=1Wμi2(j),i∈{1,2,…,N},λ0new=∑j=1WM-∑i=1N(1-λiΣii(j))∑j=1Wy(j)-Θ(j)μ(j)22.Similarly but not the same, estimated result of s is as below in MT-BCS: (15)s^=1W∑j=1WΘTΘ+Λ-1Θ(j)Ty(j).


## 2.2. Location Sensing Formulation

### 2.2.1. Localization Model

First we divide localization area to beN=nx×ny grids. Then assign index for grids from 1~N as Figure 1. The coordinate of index is calculated by (16)xi=mod⁡i,nx,y(i)=i-mod⁡(i,nx)+1.Assume T targets (also known as sources) are distributed sporadic in those areas, such that they can be represented by a sparse vector s=s1,s2,…,sNT, where si represents the energy of target in ith grid area. If there is no target in ith grid, si=0.Figure 1
Localization girds and index.Energy attenuation [3] from ith grid to jth gird is(17)Pr(dij)=PiGijdijα,dij>d0Pi,dij≤d0,where Pi is signal intensity in ith grid and d0 is a very short reference distance. dij is Euclidean distance from ith grid to jth gird. Gij is Rayleigh fading factor from i to j which is related to specific environment. α is distance factor, often choose between [2.0, 5.0].Combining (1) and (13),(18)Ψ=1G21d21α⋯GN1dN1αG12d12α1⋯GN2dN2α⋮⋮⋱⋮G1Nd1NαG2Nd2Nα⋯1,(19)s=P1,P2,…,PNT.The signal x=x1,x2,x3,…,xNT is the energy intensity in ith gird. According CS theorem, M (k<M≪N) measurements that satisfy RIP rules [8] are able to recover signal without loss. Thus, we deploy M sensors in interested areas. In (2), if there is sensor in grid j, Φ(i,j)=1; otherwise, Φ(i,j)=0. We also need consider noise such as (3).


### 2.2.2. BCS Based Adaptive Localization

Compared with custom CS method, BCS not only provides sparse estimation result, but also gives estimation of noise. In this section, we develop an adaptive BCS algorithm that will choose measurements adaptively for target localization in wireless sensor network. The algorithm assumes that noises in the interested area are consistent, which means that the variances of noise in anywhere of interested area are identical in a short period of time. Measurement numbers change based on the feedback of variances of noise by BCS estimation, until the inconsistency of variances comes to be a small value.At the beginning, we chooseM1 sensors randomly (that is an initial value) by primary device to acquire signal from interested gird area. The BCS estimated noise variance of those sensors is δ(1)2={δ112,δ212,…,δK112}, where K(1) means that signal is K(1)-sparse at the first iteration. We develop a constraint condition then, and dM sensors will be increased from the next iteration if that condition is not satisfied. The approach of choosing the dM sensors comes to two situations: (i) if there is no sensor in the grid area localized by BCS at the last iteration, we will increase a measurement in that grid and (ii) if there have been sensor in the grid area localized by BCS at the last iteration, we choose another grid that without been measured randomly. Set Bayesian estimation error δ(a)2={δ1(a)2,δ2(a)2,…,δK(a)(a)2} at the ath iteration, where K(a) means that signal is K(a)-sparse. There are two iteration termination (constraint) conditions used in our paper. One of them is the comparison of ξ1 with threshold η1, and the expression of ξ1 is(20)ξ1=δδ(a)2μ(a)-δδ(a-1)2μ(a-1),μ(a),μ(a-1)≠00,μ(a)orμ(a-1)=0.ξ1 represents the convergence rate in some degree, which put forward that the mean and variance change little at the convergence process. Second, consider that the Gaussian random is identical anywhere in the interested area, such that we let ξ2=δδ(a)2 be reasonable. The combination of ξ1 and ξ2 comes to be (21)ξ=ξ1<η1,ξ2<η2,Strongestconditionξ1<η1ξ2<η2ξ1<η1orξ2<η2,Weakestcondition.Algorithm 1 gives the whole adaptive algorithm procedure.Algorithm 1:Adaptive iteration BCS localization (AIBCSL).
(
1)  Set  ξ1=Inf, ξ2=Inf, a=1, Given initial sensor number M=M1
(2)  R=randperm(N). Set {M1}=R1:M1.
(3)  While  a<max⁡_iteration and ξ is false
(4)    Update Θ.
(5)    s,idx,K(a),δ(a)2=BCSMa,Θ.
(6)    Determine mean and variance of δ(a)2=δ1(a)2,δ2(a)2,…,δKa(a)2
μ(a)=1K(a)∑i=1K(a)δi(a)2,δδ(a)2=1K(a)∑i=1K(a)δi(a)2-μ(a)2
(7)    Calculate ξ by (21).
(8)    a=a+1
(9)    dM=length(idx), Ma+1=Ma+dM
(10)  Increase acquisition from the added dM sensors.
{Ma+1}=unique{Ma,idx,R~}, where R~ contains values from R to satisfy that Ma+1=Ma+dM.
(11) End
(12) Return grids (locations) of target idx.


### 2.2.3. Strategy to Determine Targets

According to (19), s is K-sparse vector. BCS localization returns the energy result of all N locations. Random noise will increase error rate. In this section, we assume that energy of noise source is much less than true target, such that we can estimate targets’ location by energy threshold strategy (ETS) further [15]. More specifically, the entries of estimated sparse signal are sorted according to their energy, sk2,k=1,…,K, from high to low, such that idx1=max⁡k⁡sk2 and idxK=min⁡k⁡sk2, where idxk means sort index. Setting threshold ηs, algorithm only reserves parts of all targets with the maximal energy. The determined algorithm by energy threshold is depicted as Algorithm 2.Algorithm 2:Energy threshold strategy (ETS).
(
1) Set  k=1, SSk=0
(2) [S,idx]=sort(|sk|2, “descend”)
(3) While  k<=K and SSk<ηs
(4)  SSk=SSk+Sk,
(5)  k=k+1
(6) End
(7) Return targets’ position {idx1,…,idxk}


## 2.2.1. Localization Model

First we divide localization area to beN=nx×ny grids. Then assign index for grids from 1~N as Figure 1. The coordinate of index is calculated by (16)xi=mod⁡i,nx,y(i)=i-mod⁡(i,nx)+1.Assume T targets (also known as sources) are distributed sporadic in those areas, such that they can be represented by a sparse vector s=s1,s2,…,sNT, where si represents the energy of target in ith grid area. If there is no target in ith grid, si=0.Figure 1
Localization girds and index.Energy attenuation [3] from ith grid to jth gird is(17)Pr(dij)=PiGijdijα,dij>d0Pi,dij≤d0,where Pi is signal intensity in ith grid and d0 is a very short reference distance. dij is Euclidean distance from ith grid to jth gird. Gij is Rayleigh fading factor from i to j which is related to specific environment. α is distance factor, often choose between [2.0, 5.0].Combining (1) and (13),(18)Ψ=1G21d21α⋯GN1dN1αG12d12α1⋯GN2dN2α⋮⋮⋱⋮G1Nd1NαG2Nd2Nα⋯1,(19)s=P1,P2,…,PNT.The signal x=x1,x2,x3,…,xNT is the energy intensity in ith gird. According CS theorem, M (k<M≪N) measurements that satisfy RIP rules [8] are able to recover signal without loss. Thus, we deploy M sensors in interested areas. In (2), if there is sensor in grid j, Φ(i,j)=1; otherwise, Φ(i,j)=0. We also need consider noise such as (3).


## 2.2.2. BCS Based Adaptive Localization

Compared with custom CS method, BCS not only provides sparse estimation result, but also gives estimation of noise. In this section, we develop an adaptive BCS algorithm that will choose measurements adaptively for target localization in wireless sensor network. The algorithm assumes that noises in the interested area are consistent, which means that the variances of noise in anywhere of interested area are identical in a short period of time. Measurement numbers change based on the feedback of variances of noise by BCS estimation, until the inconsistency of variances comes to be a small value.At the beginning, we chooseM1 sensors randomly (that is an initial value) by primary device to acquire signal from interested gird area. The BCS estimated noise variance of those sensors is δ(1)2={δ112,δ212,…,δK112}, where K(1) means that signal is K(1)-sparse at the first iteration. We develop a constraint condition then, and dM sensors will be increased from the next iteration if that condition is not satisfied. The approach of choosing the dM sensors comes to two situations: (i) if there is no sensor in the grid area localized by BCS at the last iteration, we will increase a measurement in that grid and (ii) if there have been sensor in the grid area localized by BCS at the last iteration, we choose another grid that without been measured randomly. Set Bayesian estimation error δ(a)2={δ1(a)2,δ2(a)2,…,δK(a)(a)2} at the ath iteration, where K(a) means that signal is K(a)-sparse. There are two iteration termination (constraint) conditions used in our paper. One of them is the comparison of ξ1 with threshold η1, and the expression of ξ1 is(20)ξ1=δδ(a)2μ(a)-δδ(a-1)2μ(a-1),μ(a),μ(a-1)≠00,μ(a)orμ(a-1)=0.ξ1 represents the convergence rate in some degree, which put forward that the mean and variance change little at the convergence process. Second, consider that the Gaussian random is identical anywhere in the interested area, such that we let ξ2=δδ(a)2 be reasonable. The combination of ξ1 and ξ2 comes to be (21)ξ=ξ1<η1,ξ2<η2,Strongestconditionξ1<η1ξ2<η2ξ1<η1orξ2<η2,Weakestcondition.Algorithm 1 gives the whole adaptive algorithm procedure.Algorithm 1:Adaptive iteration BCS localization (AIBCSL).
(
1)  Set  ξ1=Inf, ξ2=Inf, a=1, Given initial sensor number M=M1
(2)  R=randperm(N). Set {M1}=R1:M1.
(3)  While  a<max⁡_iteration and ξ is false
(4)    Update Θ.
(5)    s,idx,K(a),δ(a)2=BCSMa,Θ.
(6)    Determine mean and variance of δ(a)2=δ1(a)2,δ2(a)2,…,δKa(a)2
μ(a)=1K(a)∑i=1K(a)δi(a)2,δδ(a)2=1K(a)∑i=1K(a)δi(a)2-μ(a)2
(7)    Calculate ξ by (21).
(8)    a=a+1
(9)    dM=length(idx), Ma+1=Ma+dM
(10)  Increase acquisition from the added dM sensors.
{Ma+1}=unique{Ma,idx,R~}, where R~ contains values from R to satisfy that Ma+1=Ma+dM.
(11) End
(12) Return grids (locations) of target idx.


## 2.2.3. Strategy to Determine Targets

According to (19), s is K-sparse vector. BCS localization returns the energy result of all N locations. Random noise will increase error rate. In this section, we assume that energy of noise source is much less than true target, such that we can estimate targets’ location by energy threshold strategy (ETS) further [15]. More specifically, the entries of estimated sparse signal are sorted according to their energy, sk2,k=1,…,K, from high to low, such that idx1=max⁡k⁡sk2 and idxK=min⁡k⁡sk2, where idxk means sort index. Setting threshold ηs, algorithm only reserves parts of all targets with the maximal energy. The determined algorithm by energy threshold is depicted as Algorithm 2.Algorithm 2:Energy threshold strategy (ETS).
(
1) Set  k=1, SSk=0
(2) [S,idx]=sort(|sk|2, “descend”)
(3) While  k<=K and SSk<ηs
(4)  SSk=SSk+Sk,
(5)  k=k+1
(6) End
(7) Return targets’ position {idx1,…,idxk}


## 3. Results and Discussion

For the purpose of verifying aforementioned algorithms, simulations are executed in this section. Scale of interested area is 30 m × 30 m, in which we have grid size partitioned to be 1.0 m× 1.0 m. Such that there are N=900 grids in total. Deploy T targets in that area randomly. Assume the estimation target numbers are T⌢ by BCS and coordinate is {x⌢i,y⌢i∣i=1,2,…,T⌢}. We will use mean localization error (MLE) to determine the performance of localization. MLE is formulated as(22)MLE=∑i=1min⁡{T,T⌢}xi-x⌢i2+yi-y⌢i21/2min⁡{T,T⌢}.BecauseT⌢ is not identical to T sometimes, we also take target number error (TNE) as a performance criterion, where TNE is (23)TNE=T-T⌢T.Simulations are executed under noise situation, such that signal to noise ratio is defined:(24)SNR=10log⁡⁡∑m=1My(Noiseless)Mδε2.


### 3.1. BCS Simulation

Compared to custom methods, such as L1-norm [18], OMP [19], and LASSO [19], BCS is superior to them at certain circumstance. We will use CVX toolbox to implement L1-norm and SPAMs to implement OMP and LASSO in our experiments. In our simulation, each measurement is corrupted by Gaussian random according to (24). Energy threshold strategy is applied with ηs=0.99 in this section unless otherwise specified. All custom methods give the simulation target numbers that are identical to the real target numbers at the initialization time in all of our simulation tasks. Figure 2 shows the result of single target experiment under different SNR level. The result of BCS method is better than OMP and approximate performance compared with L1-norm and LASSO.Figure 2
MLEs in single target (T=1) simulation. M=20. Results are statistical data from 100 tests.Figure3 shows the MLE result of multitargets localization by BCS and custom CS methods in different SNR level. Target number T=5 in reality here. Setting of target number of all custom methods is 5, such that TNE is 0 of all methods except for BCS. Figure 3 proves that Bayesian is better than all of custom methods in some degree in multitarget situation.Figure 3
MLEs in multitargets (T=5) simulation. M=100. Results are statistical data from 100 tests.Figure4 shows the TNE result in different SNR level for BCS method both in single target and multitargets. In single target (T=1) situation, TNE is monotone decreasing along with SNR’s increase. In multitargets situation, most of TNEs are less than 0.6 and there is little variation. We have set T⌢=T for all custom CS methods, and the TNE of them are zeros.Figure 4
TNEs vary with SNR using BCS method. Results are statistical data from 100 tests.Figure5 examines the MLE under different measurements. It demonstrates directly that BCS is better than other methods for that BCS has less MLE than others. Another clue of that figure tells us that MLE is decreasing along with the increasing of measurements. Figure 6 gives the TNE result of BCS method when measurements increase. The trend of TNE is decreasing along with the increasing of measurements, such that we can improve the localization accuracy through increasing measurements until satisfying our demand.Figure 5
MLEs under different measurements. Results are statistical data from 100 tests.Figure 6
TNEs under different measurements using BCS method. Results are statistical data from 100 tests.
(a)
(b)
(c)The comparison between energy threshold strategy version and the not optimized version is depicted in Figure7. After ETS optimizing, TNEs and MLEs are smaller than the not optimized version with MLE and TNE decline of about 50%. It proves that ETS is effective in improving accuracy of localization.Figure 7
Comparison of MLEs and TNEs between ETS version and the not optimized version.M is initial value of measurements here. Results are statistical data from 100 tests.
(a)
ETS
(b)
TNE


### 3.2. AIBCSL Simulation

Adaptive iteration BCS localization algorithm could choose the number of sensors adaptively without user participating except for an initial value. The terminal condition used here for iteration isξ=ξ1<η1 and ξ2<η2, where η1=5*10-3 and η2=5*10-3. The maximum iteration of AIBCSL is 50 in all of our simulations in this section and tests are under 100 repetition. Energy threshold strategy is applied with ηs=0.99.Figure8 shows that AIBCSL leads to less MLE and TNE. AIBCSL is superior to BCS. It almost yields perfect result (results close to zero) when SNR is greater than 20 dB. Figure 9 demonstrates visualizing that number of measurements changes adaptively according to environment with initial value M=20 for T=1 and M=100 for T=5. With the increasing of SNR, the measurements decrease slowly, while measurements change a lot comparing T=5 with T=1.Figure 8
Compare AIBCSL with BCS. The initial value of measurement is 20 forT=1 and 100 for T=5. Results are statistical data from 100 tests.Figure 9
AIBCSL will lead to different measurements with the change of SNR. Results are statistical data from 100 tests.Figure10 is the iteration process of AIBCSL with different target numbers. ξ1 and ξ2 change along with iteration’s increase. At the convergence time, both ξ1 and ξ2 are approximately comes to be zero. Then it terminates the iteration and returns the localization result.Figure 10
The convergence process ofξ1 and ξ2. Target number T={1,3,5,7,9,11,13,15,17,19}, SNR = 25 dB. Results are statistical data from 100 tests.With the changing of target numbers, AIBCSL choose measurements adaptively. Figure11 shows the relationship between target numbers and measuments. Measurements at convergence are linear with target number, which means that AIBCSL could determine the measurements just according to the environment without needing any message about target numbers in advance. Figure 12 gives a snapshot of simulation process. In that figure, MLE of AIBCSL is better than OMP, L1-norm, and LASSO.Figure 11
Converged measurements with the increasing of target number. Results are statistical data from 100 tests.Figure 12
Snapshot of simulation. AIBCSL is compared with custom CS algorithms. Parameters:η1=5*10-3,  η2=5*10-3, and maximum iteration is 50 for BCS. Initial target number of L1-norm, OMP, and LASSO are T=5. SNR = 25 dB.


### 3.3. Multisnapshot Simulation

In this simulation work we will combine multisnapshot with adaptive localization algorithm proposed in Section2, which is called MT-AIBCSL for short in this paper. In this simulation, the terminal condition is ξ=ξ1<η1 and ξ2<η2, where η1=5*10-3 and η2=5*10-3. Number of snapshots W=2. Initial value of measurements is 20 for T=1 and 100 for T=5. All the simulation results are based on 100 times statistics. Tests are executed on different SNR and Figure 13 shows that MT-AIBCSL reduces the MLE and TNE relative to AIBCSL, especially low SNR region. That means MT-AIBCSL is really useful for reducing noise interference.Figure 13
Compare MT-AIBCSL with AIBCSL with different SNR.Because MT-AIBCSL takes full advantage of correlation of time domain, it suits the situation that the environment is not varied in a short period of time. An excellent choice is applying AIBCSL to real-time requirements and low correlation of time domain situations and vice versa.


## 3.1. BCS Simulation

Compared to custom methods, such as L1-norm [18], OMP [19], and LASSO [19], BCS is superior to them at certain circumstance. We will use CVX toolbox to implement L1-norm and SPAMs to implement OMP and LASSO in our experiments. In our simulation, each measurement is corrupted by Gaussian random according to (24). Energy threshold strategy is applied with ηs=0.99 in this section unless otherwise specified. All custom methods give the simulation target numbers that are identical to the real target numbers at the initialization time in all of our simulation tasks. Figure 2 shows the result of single target experiment under different SNR level. The result of BCS method is better than OMP and approximate performance compared with L1-norm and LASSO.Figure 2
MLEs in single target (T=1) simulation. M=20. Results are statistical data from 100 tests.Figure3 shows the MLE result of multitargets localization by BCS and custom CS methods in different SNR level. Target number T=5 in reality here. Setting of target number of all custom methods is 5, such that TNE is 0 of all methods except for BCS. Figure 3 proves that Bayesian is better than all of custom methods in some degree in multitarget situation.Figure 3
MLEs in multitargets (T=5) simulation. M=100. Results are statistical data from 100 tests.Figure4 shows the TNE result in different SNR level for BCS method both in single target and multitargets. In single target (T=1) situation, TNE is monotone decreasing along with SNR’s increase. In multitargets situation, most of TNEs are less than 0.6 and there is little variation. We have set T⌢=T for all custom CS methods, and the TNE of them are zeros.Figure 4
TNEs vary with SNR using BCS method. Results are statistical data from 100 tests.Figure5 examines the MLE under different measurements. It demonstrates directly that BCS is better than other methods for that BCS has less MLE than others. Another clue of that figure tells us that MLE is decreasing along with the increasing of measurements. Figure 6 gives the TNE result of BCS method when measurements increase. The trend of TNE is decreasing along with the increasing of measurements, such that we can improve the localization accuracy through increasing measurements until satisfying our demand.Figure 5
MLEs under different measurements. Results are statistical data from 100 tests.Figure 6
TNEs under different measurements using BCS method. Results are statistical data from 100 tests.
(a)
(b)
(c)The comparison between energy threshold strategy version and the not optimized version is depicted in Figure7. After ETS optimizing, TNEs and MLEs are smaller than the not optimized version with MLE and TNE decline of about 50%. It proves that ETS is effective in improving accuracy of localization.Figure 7
Comparison of MLEs and TNEs between ETS version and the not optimized version.M is initial value of measurements here. Results are statistical data from 100 tests.
(a)
ETS
(b)
TNE


## 3.2. AIBCSL Simulation

Adaptive iteration BCS localization algorithm could choose the number of sensors adaptively without user participating except for an initial value. The terminal condition used here for iteration isξ=ξ1<η1 and ξ2<η2, where η1=5*10-3 and η2=5*10-3. The maximum iteration of AIBCSL is 50 in all of our simulations in this section and tests are under 100 repetition. Energy threshold strategy is applied with ηs=0.99.Figure8 shows that AIBCSL leads to less MLE and TNE. AIBCSL is superior to BCS. It almost yields perfect result (results close to zero) when SNR is greater than 20 dB. Figure 9 demonstrates visualizing that number of measurements changes adaptively according to environment with initial value M=20 for T=1 and M=100 for T=5. With the increasing of SNR, the measurements decrease slowly, while measurements change a lot comparing T=5 with T=1.Figure 8
Compare AIBCSL with BCS. The initial value of measurement is 20 forT=1 and 100 for T=5. Results are statistical data from 100 tests.Figure 9
AIBCSL will lead to different measurements with the change of SNR. Results are statistical data from 100 tests.Figure10 is the iteration process of AIBCSL with different target numbers. ξ1 and ξ2 change along with iteration’s increase. At the convergence time, both ξ1 and ξ2 are approximately comes to be zero. Then it terminates the iteration and returns the localization result.Figure 10
The convergence process ofξ1 and ξ2. Target number T={1,3,5,7,9,11,13,15,17,19}, SNR = 25 dB. Results are statistical data from 100 tests.With the changing of target numbers, AIBCSL choose measurements adaptively. Figure11 shows the relationship between target numbers and measuments. Measurements at convergence are linear with target number, which means that AIBCSL could determine the measurements just according to the environment without needing any message about target numbers in advance. Figure 12 gives a snapshot of simulation process. In that figure, MLE of AIBCSL is better than OMP, L1-norm, and LASSO.Figure 11
Converged measurements with the increasing of target number. Results are statistical data from 100 tests.Figure 12
Snapshot of simulation. AIBCSL is compared with custom CS algorithms. Parameters:η1=5*10-3,  η2=5*10-3, and maximum iteration is 50 for BCS. Initial target number of L1-norm, OMP, and LASSO are T=5. SNR = 25 dB.


## 3.3. Multisnapshot Simulation

In this simulation work we will combine multisnapshot with adaptive localization algorithm proposed in Section2, which is called MT-AIBCSL for short in this paper. In this simulation, the terminal condition is ξ=ξ1<η1 and ξ2<η2, where η1=5*10-3 and η2=5*10-3. Number of snapshots W=2. Initial value of measurements is 20 for T=1 and 100 for T=5. All the simulation results are based on 100 times statistics. Tests are executed on different SNR and Figure 13 shows that MT-AIBCSL reduces the MLE and TNE relative to AIBCSL, especially low SNR region. That means MT-AIBCSL is really useful for reducing noise interference.Figure 13
Compare MT-AIBCSL with AIBCSL with different SNR.Because MT-AIBCSL takes full advantage of correlation of time domain, it suits the situation that the environment is not varied in a short period of time. An excellent choice is applying AIBCSL to real-time requirements and low correlation of time domain situations and vice versa.


## 4. Conclusions

In this paper, BCS is introduced to wireless sensor network localization and the results compared with custom CS are assessed. We then proposed AIBCSL and MT-AIBCSL to improve the accuracy of localization on the basis of BCS. AIBCSL take the assumption that noise variances are identical in the interested localization area in a short period of time. And simulation results proved that method is effective in noise environment. Advantages and limitations of AIBCSL and MT-AIBCSL have been analyzed in comparison with custom CS methods. The proposed adaptive methods have demonstrated the following superiorities.(i)
Estimating target locations with noise variance being known at the same time.(ii)
AIBCSL provides higher MLE and TNE than BCS and custom methods. And MT-AIBCSL is better than AIBCSL in low SNR level.(iii)
There is no need for user to know the number of targets ahead of time and only an initial value of measurement is required by using AIBCSL and MT-AIBCSL.Expect for that, an ETS provides performance improvement with almost 50% error decline, which is well suited for BCS framework and multitarget localization situation.



---

*Source: 438638-2015-08-13.xml*