A Multiple Target Localization with Sparse Information in Wireless Sensor Networks

Abstract

It is a great challenge for wireless sensor network to provide enough information for targets localization due to the limits on application environment and its nature, such as energy, communication, and sensing precision. In this paper, a multiple targets localization algorithm with sparse information (MTLSI) was proposed using compressive sensing theory, which can provide targets position with incomplete or sparse localization information. It does not depend on extra hardware measurements. Only targets number detected by sensors is needed in the algorithm. The monitoring region was divided into a plurality of small grids. Sensors and targets are randomly dropped in grids. Targets position information is defined as a sparse vector; the number of targets detected by sensor nodes is expressed as the product of measurement matrix, sparse matrix, and sparse vector in compressive sensing theory. Targets are localized with the sparse signal reconstruction. In order to investigate MTLSI performance, BP and OMP are applied to recover targets localization. Simulation results show that MTLSI can provide satisfied targets localization in wireless sensor networks application with less data bits transmission compared to multiple targets localization using compressive sensing based on received signal strengths (MTLCS-RSS), which has the same computation complexity as MTLIS.

1. Introduction

Dramatic advances in wireless communication and microelectromechanical-system fabrication technology have enabled the use of wireless sensor networks (WSNs). There are a large number of sensor nodes in WSNs. The sensor nodes collect the properties of interest of their local environment and communicate and share information with their neighbors to improve their limited measurement or decision capabilities. WSNs have been considered for various monitoring and control applications, such as target detection, recognition, localization [1], and environmental monitoring [2].

Localization plays a vital role in wireless sensor networks design and application. It limits the development of research and application of wireless sensor network to a large extent, especially in unattended cases. Additionally, due to the constraints of energy and hardware, low-communication and computation localization becomes popular research area for wireless sensor networks. In particular, limited by environmental factors, information extraction technology, and uncertainly communication networks, the physical information for localization presents strong incompleteness [3], which brings great challenge for wireless sensor networks design.

In this paper, we consider the problem of multiple targets localization in WSNs, which is one of the key tasks in applications of WSNs. Various algorithms depending on device measurement have been proposed for targets localization, such as received signal strength (RSS), time-of-arrival (TOA), angle-of-arrival (AOA), and time difference of arrival (TDOA). Also, focusing on low-cost and low capability sensor networks, device-free localization (DFL) is another popular localization direction [4]. Different from the traditional localization technique, DFL realizes localization without hardware equipment. For example, [5] presented a signal dynamic model and adopted the geometric method and the dynamic cluster-based probabilistic cover algorithm to solve the DFL problem. Wilson and Patwari formulated the DFL as a radio tomography imaging problem and solved the problem with regularization method [6, 7]. The above works require that there should be sufficient number of wireless links to guarantee the localization performance, and these techniques will be infeasible when few wireless links are available. Considering the limit of the energy of wireless sensor network and information incompleteness, novel targets localization method using sparse information becomes one of hot topics in WSNs. Owing to the recent advances in sparse signal reconstruction for compressive sensing (CS), in this study, we consider the target locations as a sparse signal and reconstruct the signal using the CS technique. Considering binary-detected model, a multiple target localization algorithm with sparse information (MTLSI) is proposed using compressive sensing theory. MTLSI uses targets number detected by sensor node localizing targets. The targets position is defined as a sparse vector in the discrete space and the number of detected targets by sensor nodes is expressed as the product of measurement matrix, sparse matrix, and sparse vector in compressive sensing theory. We recovered the target location with Basis Pursuit (BP) [8] and Orthogonal Matching Pursuit (OMP) [9], respectively. Localization performance is analyzed with different sensing radius, nodes quantity, targets quantity, and measurement noise. Simulation results show the validity and superiority of MTLSI in targets localization.

The organization of the paper is as follows. In Section 2, related works on localization using compressive sensing is concluded and analyzed. In Section 3, network model and parameters are described. Multiple targets localization using compressive sensing algorithm is proposed. Simulation results are shown in Section 5 and the performance of MTLSI is analyzed in detail. Conclusion is drawn and future work is discussed in Section 6.

2. Related Works

In wireless sensor networks, limited by environmental factors, information extraction technology, and uncertain communication networks, the physical information for localization presents strong incompleteness. Localization in wireless sensor networks should be adaptive with the sparse information. Furthermore, it will be a good choice that the method has a lower computation, data transmission, and energy consumption, especially without extra hardware equipment for the sensor. Sometime, localization algorithm needs to balance the precision and all these limits. Recently, compressive sensing theory has shown great potential applied value in the field of sparse signal image processing. Applying appropriate reconstruction algorithm, compressive sensing theory can recover complicated image information from less measurements [10–12]. Considering that CS has excellent performance in signal reconstruction, it has been applied to realize traditional localization problem recently. In [13], wireless sensor network monitoring region was divided into N discrete grids, and target positions are modeled as a N-dimensional vector of K-sparse. The rationality of CS theory applying in the localization is demonstrated theoretically. A sparse recovery algorithm called greedy matching pursuit (GMP) is also proposed for target localization with good performance. The work achieves better performance in solving the traditional localization problem. However, the accurate measurement matrices need to be known a priori, which incurs plenty of measuring works. For the limited wireless sensor networks, it is a great challenge to provide the accurate measurements in many applications. For multiple targets in the network monitoring area, Chen et al. [14] proposed a localization method using compressive sensing theory, where received signal strengths is needed that lead to extra hardware function and energy consumption. Motivated by the observation that the location information of the target is not only sparse but changes slowly and continuously over time as well, [15] merged the Bayesian theory into the CS theory and proposed a novel RCS algorithm to reconstruct the gradually changed sparse signal. The RCS algorithm makes use of the space-domain and time-domain features of the signal. However, there is large communication and computation load. An optimal recovery mechanism is proposed in [16]; however, network has to transmit a large amount of iterative information among sensor nodes, which also causes more energy consumption. On the other hand, mobile device assistant is applied to CS-based localization. Aiming at an accurate indoor localization scheme, [17] applied the theory of Multitask Bayesian Compressive Sensing (MBCS) to indoor localization. The proposed scheme assembles the strength measurements of signals from the mobile devices (MDs) to distinct access points (APs) and jointly utilizes them at a central unit or a specific AP to achieve localization. It can alleviate the burden of MDs while simultaneously giving a precise estimation of the locations. Energy is a vital issue in wireless sensor networks design, and simultaneously reducing the communication cost of network in sparse information is also an important job in localization mechanism design. In paper [18], we proposed a CS-based localization method, where targets localization information is provided by the binary-detected model without hardware equipment. The initial measurements are not very accurate. But there is less data transmission and lower energy consumption. In this paper, the performance of the CS-based localization method MTLSI using binary-detected model is further analyzed and compared with multiple targets localization using compressive sensing based on received signal strengths (MTLCS-RSS) [14]. Simulation results show that algorithm MTLSI has equivalent localization precision with MTLCS-RSS while MTLCS-RSS depends on RSS measure and transmission.

3. Network Model and Parameter Definition

3.1. Network Model

Sensor nodes are randomly deployed in the network. Each node is static and location-aware; targets are also in static state. For the convenience of study, the monitoring region is defined as the square area of $n\times n$ , it is divided into N ( $N=n\times n$ ) grids. M ( $M\ll N$ ) sensor nodes with position information are randomly deployed within some grids. Considering the effectiveness of network coverage (the monitored area is covered by a minimum number of sensors), we assume that there is at most one node for each grid. K ( $K<M\ll N$ ) targets are scattered in different grids, and there is no more than one target in each grid. Moreover, the real targets' position is assumed as the corresponding grid center. The diagram of the network is shown in Figure 1.

Figure 1

The diagram of network.

3.2. Binary-Detected Model

We apply the binary-detected model in the localization algorithm. If target $T_i$ is within the sensor node $\mathrm{S}{\mathrm{N}}_j$ 's sensing radius r, then the target can be detected by $\mathrm{S}{\mathrm{N}}_j$ ; the $\mathrm{S}{\mathrm{N}}_j$ 's detecting result $y_{ji}$ for $T_i$ is 1, else $y_{ji}$ is 0. It is formulated as follows:

$$\begin{array}{cc}& y_{ji}=\left\{\begin{array}{cc}\mathrm{1}\hfill & d_{ji}\le r\hfill \\ \mathrm{0}\hfill & d_{ji}>r;\hfill \end{array}\right.\end{array}$$

(1)

$d_{ji}$ is the Euclidean distance between target $T_i$ and sensor node $\mathrm{S}{\mathrm{N}}_j$ .

3.3. Parameter Definition

The multitargets localization will be constructed as a compressive sensing sparse signal reconstruction problem, and the relative parameters matrix involved in the problem is defined as follows.

(1) Sparse Vector of Target Position Information $\mathit{s}$ . K monitored targets coordinate the center of relative grids, respectively. The information vector of target position is defined as $\mathit{s}$ , $\mathit{s}={\left\{s_k,\hspace{0.17em}\hspace{0.17em}k=1,2,\dots ,N\right\}}^{\mathrm{T}}$ , and $\mathit{s}$ is an $N\times 1$ vector. If there is a target in k grid, $s_k=1$ , otherwise $s_k=0$ . Because there are K targets in the monitored area, only K elements of the vector $\mathit{s}$ are 1 and the rest are all 0.

(2) Sparse Matrix $\mathit{\Psi }$ . We define $\mathit{\Psi }$ as an $N\times N$ sparse matrix. If a target in the $j\hspace{0.17em}\hspace{0.17em}(1\le j\le N)$ grid is detected by the sensor node located in the $i\hspace{0.17em}\hspace{0.17em}(1\le i\le N)$ grid, then ${\Psi }_{ij}=\mathrm{1}$ , otherwise ${\Psi }_{ij}=\mathrm{0}$ . So, the matrix $\mathit{\Psi }$ can be presented as in the following formula:

$$\begin{array}{cc}& \mathit{\Psi }=\left(\begin{array}{cccc}{\Psi }_{\mathrm{11}}& {\Psi }_{\mathrm{12}}& \cdots & {\Psi }_{\mathrm{1}N}\\ {\Psi }_{\mathrm{21}}& {\Psi }_{\mathrm{22}}& \cdots & {\Psi }_{\mathrm{2}N}\\ ⋮& ⋮& ⋮& ⋮\\ {\Psi }_{N\mathrm{1}}& {\Psi }_{N\mathrm{2}}& \cdots & {\Psi }_{NN}\end{array}\right).\end{array}$$

(2)

Taking $\mathit{X}={\left\{x_1,x_2,\dots ,x_N\right\}}^{\mathrm{T}}$ , then formula (3) shows the targets number sensed by each node, which we place at every grid at the all monitored area. Consider

$$\begin{array}{cc}& \mathbf{X}=\mathit{\Psi }\mathbf{s}\mathbf{.}\end{array}$$

(3)

(3) Measurement Matrix $\mathbf{\Phi }$ . If $M\hspace{0.17em}\hspace{0.17em}(M=O\left(K\log \left(N/K\right)\hspace{0.17em}\hspace{0.17em}\&\hspace{0.17em}\hspace{0.17em}M\ll N\right))$ sensor nodes are randomly deployed in N grid, the measurement matrix $\mathbf{\Phi }$ is shown in the following formula:

$$\begin{array}{cc}& \mathbf{\Phi }={\left(\begin{array}{cccccc}\mathrm{0}& \cdots & \mathrm{1}& \mathrm{0}& \cdots & \cdots \\ \mathrm{0}& \cdots & \mathrm{0}& \mathrm{1}& \mathrm{0}& \cdots \\ ⋮& ⋮& ⋮& ⋮& ⋮& ⋮\\ \mathrm{0}& \cdots & \cdots & \mathrm{0}& \mathrm{1}& \mathrm{0}\end{array}\right)}_{M\times N}.\end{array}$$

(4)

If sensor node $i\hspace{0.17em}\hspace{0.17em}(1\le i\le M)$ is located in the $j\hspace{0.17em}\hspace{0.17em}(1\le i\le N)$ grid, ${\Phi }_{ij}=\mathrm{1}$ , otherwise ${\Phi }_{ij}=\mathrm{0}$ . According to the network model, only one element is 1 in each row of the matrix $\mathbf{\Phi }$ and the rest are 0. So there are M nonzero values in $\mathbf{\Phi }$ . After deployment, sensor node positions are determined, and the measurement matrix is also determined.

(4) Measurement Vector $\mathit{y}$ . $\mathit{y}={\left\{y_1,y_2,\dots ,y_M\right\}}^{\mathrm{T}}$ is measurement vector. When the i sensor node detected that there were k targets within its sensing range, $y_i=k\hspace{0.17em}\hspace{0.17em}(k\le K)$ . The measurement vector $\mathit{y}$ can be used to record the detected target information of M sensor nodes.

(5) Sensing Matrix $\mathit{A}$ . According to definitions and physical meaning of each matrix above, the measurement vector $\mathit{y}$ satisfies the following equation:

$$\begin{array}{cc}& \mathbf{y}=\mathbf{\Phi }\mathbf{X}=\mathbf{\Phi }\mathit{\Psi }\mathbf{s}=\mathbf{A}\mathbf{s}\mathbf{.}\end{array}$$

(5)

The equation builds a relationship between the measurement vector and the target position information vector, then ${\mathit{A}}_{M\times N}$ is defined as sensing matrix.

Considering the measurement noise, the above formula $\mathit{y}={\left\{y_1,y_2,\dots ,y_M\right\}}^{\mathrm{T}}$ should be expressed as follows:

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

(6)

where $\mathbf{\epsilon }=\{{\epsilon }_{\mathrm{1}},{\epsilon }_{\mathrm{2}},\dots ,{\epsilon }_M{\}}^{\mathrm{T}}$ is the additive Gaussian white noise.

4. Multiple Target Localization Using Compressive Sensing Theory

4.1. Algorithm Description

According to compressive sensing theory [19], if recovering signals are sparse or compressible under a certain basis, we can acquire the sparse signal or its unique sparse representation with fewer noisy measurements through a recovery algorithm. Targets number sensed by each sensor node can easily be obtained. Considering the static wireless sensor monitoring network, there are only K nonzero values in the target position information vector s, so s is a sparse vector by the definition of sparsity [20]. Furthermore, the vector can be recovered by taking a recovery algorithm.

According to above statement, we can obtain the network localization information without the matrix $\mathit{X}$ by placing a sensor node at each grid. Only through $\mathit{X}$ multiplied by the matrix $\mathbf{\Phi }$ , the measurement vector $\mathit{y}$ detected by M sensor nodes can be obtained. Then the sparse vector $\mathit{s}$ representing targets position information can be recovered by using the recovery algorithm. In the centralized localization, M nodes will deliver the compressive measurements vector $\mathit{y}$ and sensing matrix $\mathit{A}$ to the sink node, and the sparse vector $\mathit{s}$ can be reconstructed through the compressive sensing theory. Eventually multitarget localization is finished.

4.2. Orthogonalization of Sensing Matrix

As stated in CS theory, the successful recovery of a signal by CS has a great relativity with the characteristics of measurement matrix and sparse matrix. The matrix $\mathbf{A}=\mathbf{\Phi }\mathit{\Psi }$ obeys RIP (Restricted Isometry Property) with parameters $(K,\delta )$ for $\delta \in (\mathrm{0,1})$ ; if function (7) holds for all K-sparse vector x, then the sparse signal can be recovered with high precision. Consider

$$\begin{array}{cc}& \mathrm{1}-\delta \le \frac{{‖Ax‖}_2^2}{{‖x‖}_2^2}\le \mathrm{1}+\delta .\end{array}$$

(7)

By the definition in Section 3, the sparse matrix $\mathit{\Psi }$ and the measurement matrix $\mathbf{\Phi }$ are obtained according to the sensor network topology structure. They are coherent in spatial domain; namely, $\mathbf{A}=\mathbf{\Phi }\mathit{\Psi }$ does not satisfy the RIP, and the CS theory cannot be directly applied. To solve this problem, a data preprocessing on measurement vector $\mathit{y}$ is introduced. Considering the sensing matrix $\mathbf{A}=\mathbf{\Phi }\mathit{\Psi }$ , $\mathbf{T}=\mathrm{o}\mathrm{r}\mathrm{t}\mathrm{h}({\mathbf{A}}^{\mathrm{T}}{)}^{\mathrm{T}}$ where T is an orthogonal basis for the range of A, and ${\mathbf{A}}^{+}$ returns the generalized inverse of matrix $\mathit{A}$ . Then,

$$\begin{array}{cc}& \mathbf{Y}=\mathbf{T}{\mathbf{A}}^{+}\mathbf{y}=\mathbf{T}{\mathbf{A}}^{+}\mathbf{A}\mathbf{s}=\mathbf{T}\mathbf{s}\mathbf{.}\end{array}$$

(8)

In the case of noise,

$$\begin{array}{cc}& \mathbf{Y}=\mathbf{T}{\mathbf{A}}^{+}\mathbf{y}=\mathbf{T}{\mathbf{A}}^{+}\mathbf{A}\mathbf{s}+\mathbf{T}{\mathbf{A}}^{+}\mathbf{n}=\mathbf{T}\mathbf{s}+{\mathbf{n}}^{\prime }.\end{array}$$

(9)

This procedure has the same effect as orthogonalizing the two matrices [14]. Since T is an orthogonal matrix, s can be well recovered from Y via recovery algorithm based on the CS theory after the above process is performed at the sink node.

4.3. Localization Recovery Algorithm

According to the above analysis, multitargets localization in WSN can be properly solved by the sparse vector recovery algorithm of the CS. Among the existing recovery algorithms, ${\mathcal{l}}_{\mathrm{1}}$ minimization and greedy algorithm are two major approaches. ${\mathcal{l}}_{\mathrm{1}}$ minimization methods, such as Basis Pursuit (BP), solve a convex minimization problem instead of the combinatorial problem. The methods work correctly for all sparse signals and provide theoretical performance guarantees. Most ${\mathcal{l}}_{\mathrm{1}}$ minimization methods are sensitive to noise and often suffer from heavy computational complexity. Greedy algorithms, such as Orthogonal Matching Pursuit (OMP), iteratively identify the supports of the targets signal and construct an approximation on the set of the chosen supports, until a halting condition is met. They can solve large-scale recovery problems more efficiently. The computational complexity of greedy algorithms is significantly lower than that of ${\mathcal{l}}_{\mathrm{1}}$ minimization. In this paper, we applied both BP and OMP to derive nonzero elements in the unknown sparse vector s, which exactly indicate the targets position. The performance of the two recovery algorithms is analyzed, respectively.

In the localization recovery algorithm, the input matrices are $\mathit{Y}$ and $\mathit{T}$ , and the targets estimation position is ultimately obtained with $\mathit{K}$ times iterating. The detailed procedure is as follows. Firstly, network constructs the measurement matrix with the detected target information. Secondly, the algorithm selects a column of the orthogonal matrix $\mathit{T}$ , which has the maximum correlation with the redundant vector $r_0$ (the initial redundant vector is $\mathit{Y}$ ), and then all elements of this column are placed as zero to update the matrix $\mathit{T}$ . Thirdly, the matrix $\mathit{Y}$ subtracts the relevant portion and continues to iterate. The iteration is forced to stop until the number of iterations reaches the sparsity of $\mathit{K}$ . $\widehat{s}$ obtained by OMP or BP is the recovery of the sparse vector $\mathit{s}$ , so the positions of target are determined. The proposed localization algorithm has low computational complexity and less time consuming. And it can satisfy the localization requirement. The pseudocode is shown in Algorithm 1.

Algorithm 1: Pseudocode of localization recovery algorithm.

(1) Sensors detect targets

(2) Construct Y

(3) Initialize $r_{\mathit{0}}\leftarrow Y$ , $\Lambda \leftarrow []$ and $t\leftarrow \mathit{1}$ .

(4) For   $t\leftarrow \mathit{1}$ to K

     do ${\lambda }_t\leftarrow \mathrm{a}\mathrm{r}\mathrm{g}\hspace{0.17em}\mathrm{m}\mathrm{a}{\mathrm{x}}_{j=\mathit{1},\dots ,N}\left|〈r_{t-\mathit{1}},T_j〉\right|$

     set $\Lambda =[\Lambda ,\mathit{T}(:,{\lambda }_t)]$ and ${\mathit{T}}_{{\lambda }_t}=\mathit{0}$

       $\widehat{s}\leftarrow \mathrm{a}\mathrm{r}\mathrm{g}\hspace{0.17em}\mathrm{m}\mathrm{i}\mathrm{n}{‖Y-\Lambda \widehat{s}‖}_{\mathit{2}}$

(5)  Calculate new residual $r_t\leftarrow Y-\Lambda \widehat{s}$

(6)    $t=t+\mathit{1}$

(7) End for

(8) Return( $\widehat{s}$ )

5. Simulation Results and Performance Evaluation

Simulation is done to evaluate the performance of the algorithm proposed in the paper. The monitored network is divided into $N\hspace{0.17em}\hspace{0.17em}(N=n\times n)$ grids. $K\hspace{0.17em}\hspace{0.17em}(K<M)$ targets without position information are randomly placed in K grids. There is no more than one target in each grid. Detected targets number is collected at $M\hspace{0.17em}\hspace{0.17em}(M\ll N)$ arbitrary sensor nodes, but there is no more than one sensor node in each grid. In addition, if MTLSI reports a target at a grid, the center of the grid is used as the estimated position of the reported target. The node's sensing radius is r. When the distance between nodes and target is shorter than r, the sensor nodes can detect the target. Considering the reliability and robustness of the proposed method, we intentionally add the Gaussian white noise to the measurements. Due to the specificity of the model, the Gaussian white noise is added to the distance between nodes and targets. Each presented result is the average value with 200 random runs. Finally, the localization performance is studied under different sensing radius, targets quantity, and sensor quantity.

5.1. Localization Error

In this paper, localization error is defined as the average Euclidean distance between the real positions and the recovered positions of the K targets. It is shown as follows:

$$\begin{array}{cc}& e=\frac{\left(\mathrm{1}/K\right){\sum }_{i=\mathrm{1}}^K\sqrt{{\left(x_i-x_i^{\prime }\right)}^{\mathrm{2}}+{\left(y_i-y_i^{\prime }\right)}^{\mathrm{2}}}}{r}.\end{array}$$

(10)

In (10), K is the total number of the targets with real positions $\left(x_1,y_1\right),\left(x_2,y_2\right),\dots ,(x_K,y_K)$ , respectively. $\left(x_1,y_1^{\prime }\right),\left(x_2,y_2^{\prime }\right),\dots ,(x_K^{\prime },y_K^{\prime })$ are the corresponding estimated target positions. r is the sensing radius of nodes.

In the simulation, there are $M=40$ sensor nodes randomly deployed in the monitoring area, which is divided into a 20 × 20 ( $N=20\times 20$ ) grid. The sensing radius of nodes is 14 ( $r=14$ ). There are 10 ( $K=10$ ) targets located in the monitoring area. Figure 2(a) shows the recovered targets position and real target position, while Figure 2(b) shows the localization error without noise. The average localization error with BP and OMP are 19.02% and 20.50%, respectively. BP does better than OMP as expected. Both of them satisfy the localization requirement in WSN [21].

Figure 2

$K=10$ targets localization results without noise.

MTLSI performances with noise measurements are also studied. Figures 3 and 4 show the localization error under SNR 15 dB and SNR 25 dB. The average localization error with BP and OMP are 19.07% and 20.62% under SNR 15 dB, respectively, and the average localization error with BP and OMP are 19.22% and 21.99% under SNR 25 dB, respectively. Localizing the same number of targets with MTLSI, the bigger the measurement noise is, the bigger the error is, which is consistent with the reality. Furthermore, the localization error is very close for the case with measurement noise and without noise. It indicates that MTLSI can tolerate a certain level of measurement noise.

Figure 3

$K=10$ target localization results under SNR = 15 dB.

Figure 4

$K=10$ targets localization results under SNR = 25 dB.

5.2. Localization Error versus Sensing Radius

The bigger the node's sensing radius, the higher the probability that the node detects more targets. Different sensing radius will lead to different measures matrix $\mathit{y}$ . The performance will be affected by different sensing radius. Localization error varies with the ratio $r/n$ studied. In cases $K=10$ and $M=40$ , simulations are done without noise, SNR = 25 dB and SNR = 15 dB, respectively. In Figure 5, MTLSI using BP recovering algorithm has a lower localization error than MTLSI using OMP recovering algorithm. Localization error shows the same trend varying with $r/n$ under different noise environments. Localization error decreases with the increasing of the ratio if $r/n<0.7$ , and the error increases when the ratio continues to increase. The error reaches the minimum when $r/n=0.7$ . When $r/n<0.7$ , r is smaller compared with the fixed n. The absolute distance between real positions and recovered positions of target changes less with the radius r. Localization error is defined as the ratio of the absolute error and sensing radius shown in (10) above. So for the fixed absolute distance error, when r is smaller, the localization error is bigger.

Figure 5

Localization error versus sensing radius.

When $r/n>0.7$ , for the sensing radius that is bigger, each sensor node can almost detect all targets in the monitored area, which brings more noise and leads to a lower localization precision of the reconstruction algorithm in CS. So the localization error becomes bigger as $r/n$ increases.

5.3. Localization Error versus Number of Targets

Under the parameters $M=40$ , $N=20\times 20$ , and $r/n=0.7$ , the performance of localization algorithm is investigated with the number of targets changing from 2 to 25. Three cases SNR = 25 dB, SNR = 5 dB, and without noise are studied. As shown in Figure 6, MTLSI using BP and OMP show the same trend. When $K<15$ , under different noise level, the less the number of targets is, the lower the localization accuracy is. It is consistent with the fact in CS theory that the bigger the sparsity is, the more accurate the recovery sparse vector is. When the targets number $K=15$ , the localization error with BP is close to 19%, while the localization error with OMP is nearly 25%. With the targets number increasing when $K>15$ , the localization error changes less and maintains at around 19% and 25% for MTLSI using BP and OMP, respectively. On the other hand, when $K<8$ , MTLSI with OMP does better than with BP.

Figure 6

Localization error versus number of targets.

5.4. Localization Error versus Number of Sensor Nodes

Under the parameters $N=20\times 20$ , $r=14$ , localization error is studied with different number of sensor nodes in SNR = 25 dB, SNR = 15 dB and without noise cases. Simulation is conducted when the number of sensor nodes M varies from 20 to 100 at a step size of 5. As shown in Figure 7, for both BP and OMP recovered method, the larger the M is, the smaller the error for all numbers of targets will be. Localization error range is from 35% to 5%. It is rational in the theoretic analysis. In CS theory, more measurements mean more information obtained about the network. The sparse vector can be recovered more precisely and the localization error is smaller.

Figure 7

Localization error versus number of sensor nodes.

5.5. Computation Complexity

MTLSI has the same computation complexity with the multiple targets localization algorithm using compressive sensing theory based on received signal strength (MTLCS-RSS) proposed in [14], with the same recovery algorithm, such as BP and OMP. The measurement in [14] is RSS, which depends on hardware device to acquire. Furthermore, there are some challenges to distinguish the RSS transmitted by different targets. In MTLSI, the measured value is 1 if the sensor has discovered the target or 0 if the sensor has not discovered the target. The data bits collected to localize target are small. With the same conditions, the performances of MTLSI and MTLCS-RSS are compared. Figure 8 shows localization error with different sensing radius, respectively, by OMP and BP recovery algorithm. No matter with OMP or BP, MTLCS-RSS works better than MTLSI. The localization error decreases monotonically with the increasing sensing radius by MTLCS-RSS. As mentioned in Section 4.2, there is an inflection point at $r/n=0.7$ by MTLSI in the localization error varying with sensing radius. Beside very small sensing radius ( $r/n<0.35$ ), the localization error is lower than 40% by both MTLSI and MTLCS-RSS that satisfy with the application requirement.

Figure 8

Localization error versus sensing radius.

Figure 9 shows the localization error varying with the targets number. With OMP recovery method, MTLSI and MTLCS-RSS have the same tendency. The more the targets, the lower the localization error. The results meet the expected design objective. With BP recovery methods, MTLCS-RSS works better than MTLSI. The localization error increases with the increasing targets number, but the localization is totally lower than 25%. There is no big difference between the two methods in the localization performance varying with the targets number.

Figure 9

Localization error versus number of targets.

Figure 10 shows localization error varying with the number of sensor nodes. Both MTLSI and MTLCS-RSS provide a decreasing localization error with increasing number of sensor nodes. It is rational that the more the information can be used, the more precise the targets' position can be acquired. The localization error is not more than 35%.

Figure 10

Localization error versus number of sensor nodes.

Comparing with Figures 8–10, some conclusion can be made. BP recovery method works batter in both MTLSI and MTLCA-RSS for OMP is a proximal greedy recovery method. MTLSI owns the same performance with MTLCS-RSS with OMP recovery method, while MTLCS-RSS works better than MTLSI with BP recovery method. It is attributed to the more precise RSS measurements and BP recovery mechanism. On the other hand, MTLSI can deliver the satisfied localization performance with low data bits transmission and extra hardware equipment.

6. Conclusion

In this paper, considering hardware measurement cost in wireless sensor networks localization, we use targets number sensed by each node to induce the targets position. It is a range-free algorithm. On the other hand, the localization information shows sparsity for the network characteristic and environment. We applied compressive sensing theory to the localization mechanism MTLSI, using preprocessing to induce incoherence needed in the CS theory and postprocessing to compensate for spatial discretization caused by grid assumption. The positions of target are represented as a sparse vector, and the number of detected targets by sensor nodes is expressed as the product of measurement matrix, sparse matrix, and sparse vector in compressive sensing theory. The sparse vector of target positions is reconstructed by Basis Pursuit (BP) and Orthogonal Matching Pursuit (OMP). MTLSI performance under different measurement noise, sensor radius, targets number, and sensor nodes number is investigated. Simulation results validate that MTLSI can satisfy the multitarget localization accuracy requirement in the case of incomplete information. When $r/n=0.7$ , the localization error of MTLSI reaches the minimum. In the situation stated in the paper, the localization error increases with the number of targets increasing and is maintained at about 19% with BP and 25% with OMP eventually. With the number of sensor nodes increasing, the localization accuracy will be improved. MTLSI has the same computation complexity as multiple targets localization using compressive sensing based on received signal strengths (MTLCS-RSS). It can be applied without extra equipment and low data bits transmission, which satisfy the requirements of target localization in wireless sensor network in the case of incomplete information.