An efficient dictionary refinement algorithm for multiple target counting and localization in wireless sensor networks

Abstract

Many applications provided by wireless sensor networks rely heavily on the location information of the monitored targets. Since the number of targets in the region of interest is limited, localization benefits from compressive sensing, sampling number can be greatly reduced. Despite many compressive sensing–based localization methods proposed, existing solutions are based on the assumption that all targets fall on a sampled and fixed grid, performing poorly when there are targets deviating from the grid. To address such a problem, in this article, we propose a dictionary refinement algorithm where the grid is iteratively adjusted to alleviate the deviation. In each iteration, the representation coefficient and the grid parameters are updated in turn. After several iterations, the measurements can be sparsely represented by the representation coefficient which indicates the number and locations of multiple targets. Extensive simulation results show that the proposed dictionary refinement algorithm achieves more accurate counting and localization compared to the state-of-the-art compressive sensing reconstruction algorithms.

Introduction

Location is highly critical to many services provided by wireless sensor networks (WSNs), ¹ such as geographic routing, wildlife monitoring, and health caring. Localization is a fundamental issue of WSNs that has been extensively studied in the literature. In daily life, the global positioning system (GPS) ² is widely applied to achieve self-localization. However, there are still some situations where it does not work well (e.g. indoors or under the ground). Moreover, having each target GPS-equipped is extremely infeasible and expensive for WSNs.

The limitations of GPS have promoted a large body of localization approaches, which can be classified into two categories: range-based and range-free approaches. Range-based approaches are simple but susceptible to fading, noise, and non–line of sight. Range-free approaches perform localization by exploiting the connectivity between targets and sensors. They do not need extra hardware support but are usually imprecise and easily sensitive to the density of sensors. More seriously, both range-based and range-free approaches are computationally inefficient as they require the exchange of a large number of data to measure distances or determine connectivity. However, in most applications, sensors are resource-constrained (e.g. low power, low memory, and low operational ability), leading these solutions impractical. Therefore, it is quite necessary to develop a localization approach with less data collection and processing.

Compressive sensing (CS)^3,4 offers a novel solution to the localization problem in WSNs. As a novel signal processing technique, CS theory asserts that a small number of measurements will suffice for recovering the original sparse or compressible signals. Since the number of targets in the region of interest is limited, localization benefits from CS, sampling number can be greatly reduced. As a consequence, CS attracts considerable attention in the localization field, and a lot of localization approaches based on CS are proposed that will be discussed later. In these approaches, the continuous physical space is discretized into a fixed grid which corresponds to a dictionary. By assuming that all targets fall exactly on some grid points, the measurement vector can be sparsely represented as a sparse linear combination of the dictionary atoms. Then, localization is accomplished by sparse signal recovery followed by support detection.

Unfortunately, as a matter of fact, the assumption usually does not establish that all targets fall exactly on a fixed grid. It is noteworthy that there always exist targets that deviate from the fixed grid no matter how fine the space is sampled. In such a case, there exists mismatch between the assumed and actual sparsifying dictionaries. This is the so-called “dictionary mismatch” problem. Existing research indicates that the existence of dictionary mismatch will deteriorate the performance of CS dramatically.^5,6

Since CS has been focused on the signals that can be sparsely or compressibly represented under a finite dictionary, discretization of the physical space is inevitable. It is intuitively reasonable that both dictionary mismatch and recovery error can be reduced with a dense grid. Therefore, one naturally wonders whether a denser grid leads to more accurate sparse signal recovery. In fact, according to CS theory, the sampled grid should not be too dense. This is because the dictionaries, corresponding to densely-sampled grids, have high inter-column correlation. The high correlation of dictionary atoms violates the restricted isometry property (RIP) condition of CS. ¹⁹ In fact, the performance of CS may degrade considerably in the presence of dictionary mismatch, even when the physical space is fine-grained discretized.

In this article, we study the dictionary mismatch problem and develop an efficient dictionary refinement algorithm. The key idea is to dynamically adjust the grid to alleviate or even eliminate the mismatch between the assumed and the actual sparsifying dictionaries. First of all, we regard the sparsifying dictionary as a parameterized dictionary, with the sampled grid as the underlying parameters. Consequently, the original counting and localization problem is formulated as a joint sparse signal recovery and grid parameter estimation problem. Then, an iterative two-step algorithm is developed that alternately optimizes over the sparse signal and grid parameters in a manner of optimizing over one while keep another fixed. Therefore, the original joint optimization problem is transformed into two sub-problems that can be effectively solved by existing optimization tools. Finally, we demonstrate via simulation that the proposed dictionary refinement algorithm performs significantly better than the state-of-the-art CS reconstruction algorithms.

The main contributions of this article can be summarized as follows:

• We study the dictionary mismatch problem in CS-based localization and develop an efficient dictionary refinement algorithm. Based on the algorithm, the grid can be dynamically adjusted to alleviate or even eliminate the mismatch between the assumed and actual sparsifying dictionaries.

• To achieve dictionary refinement, we view the sparsifying dictionary as a parameterized dictionary, with the sampled grid as the underlying parameters. Therefore, the original counting and localization problem is formulated as a joint sparse signal recovery and grid parameter estimation problem.

• To solve the joint optimization problem, we decompose it into two sub-problems and develop an iterative two-step algorithm to solve the sub-problems. In each iteration, the sparse signal and grid parameters are updated in turn.

• We conduct extensive simulations to evaluate the performance of the proposed dictionary refinement algorithm. The superiority of our algorithm compared with other sparse reconstruction algorithms is confirmed by the simulation results.

The rest of this article is organized as follows. Section “Related work” gives a review on related work. A brief background information about CS is presented in section “CS.” Section “Network model and problem statement” provides the network model and problem statement. In section “Problem formulation,” we mathematically formulate the counting and localization problem. Section “Localization via dictionary refinement” provides detailed descriptions on the proposed dictionary refinement algorithm. The performance of our algorithm is demonstrated in section “Numerical evaluation.” Finally, conclusion is summarized in section “Conclusion.”

Notations used in this article are as follows. $\mathbb{R}$ denotes the set of real numbers. Capital boldface letters and lowercase boldface letter are reserved for matrices and vectors, respectively. |·| denotes the amplitude of a scalar or cardinality of a set. × denotes Cartesian product. $\Vert ·{\Vert }_0$ , $\Vert ·{\Vert }_1$ , and $\Vert ·{\Vert }_2$ are the ${\ell }_0$ , ${\ell }_1$ , and ${\ell }_2$ norms, respectively. For a given matrix A, ${\mathbf{A}}^{-1}$ and ${\mathbf{A}}^{\mathrm{T}}$ denote the inverse and transpose, respectively.

Related work

In this section, we review the related work in the field of CS-based localization. Cevher et al. ⁷ propose to apply CS to target localization for the first time. The localization problem is transformed into a sparse recovery problem by sampling the physical space into a grid. In addition, a Bayesian framework ⁸ is proposed and the sparse approximation to its optimal solution is also provided. However, the drawback that a dictionary needs to be maintained at each sensor limits its applications. Meanwhile, the demand of communication among sensors also leads to poor performance in sparse WSNs. Feng et al. ⁹ model the locations of multiple targets as a sparse matrix and propose a CS-based indoor localization approach. Although it declares to be able to localize multiple targets, the approach can localize only one target once in that the data compression is not sufficient enough. In Feng et al.,^10,11 a clustering idea is further introduced to reduce system cost. The localization performance relies heavily on the clustered results and cluster matching algorithms. Nevertheless, in general, it is difficult to choose a proper clustering scheme and an effective cluster matching algorithm. Zhang et al. ¹² consider multiple target localization without the prior knowledge of target number. Different from Feng et al., ⁹ the authors view the locations of multiple targets as a sparse vector whose sparsity corresponds to the number of targets. Then, a greedy matching pursuit (GMP) algorithm is proposed to recover the sparse signal with a high probability. Au et al. ¹³ apply CS to develop a positioning system which consists of a coarse stage and a fine stage. The coarse stage is executed to obtain the approximate positions of a target using a proximity constraint and then more accurate position is obtained by CS in the fine stage. Guyen et al. ¹⁴ propose an indoor positioning system where the radio map is decomposed into a dictionary and a sparse representation matrix using the K-SVD dictionary learning algorithm. Then, the real-time received signal strength (RSS) vector is matched with the columns of the sparse representation matrix. The reference point with the least matching error is determined to be closest to the target. In fingerprint-based localization approaches, the construction of fingerprint database is usually time-costing. By exploiting the spatial and temporal relativity, Zhang et al. ¹⁵ develop a new fingerprint database construction method with only a few fingerprint collection. Different from the above-mentioned range-based methods, Liu et al. ¹⁶ develop a range-free CS-based localization method. Instead of collecting RSS measurements directly, the information whether targets are in the range of sensors are utilized to achieve localization at the cost of unreliable accuracy. Nguyen and Shin ¹⁷ develop a CS-based localization method which collects RSS measurements according to a deterministic sensing matrix rather than random sensing matrix. By exploiting the sparsity of spatial signals and the compressibility of temporal signals, Sun et al. ¹⁸ develop a two-dimensional (2D) localization framework using CS.

In the above-mentioned solutions, a common assumption is made that all targets fall exactly on a fixed grid. However, it should be noted that there always exist targets that deviate from the grid no matter how fine the space is sampled. In such a case, the traditional CS-based localization methods perform poor. Additionally, it should be noted that we assume each RSS measurement taken by a sensor is the sum of the strengths of the received signals that come from all targets while the sensor cannot distinguish the signals from different targets. Therefore, it is impossible to directly derive distance estimates or approximation information between sensors and targets. As a result, the traditional range-based or range-free localization methods cannot be applied in our context.

CS

Consider a discrete signal given by the vector $\mathbf{s}\in {\mathbb{R}}^N$ . It is sparse if $\mathbf{s}$ has only a few non-zero coefficients, that is, $\parallel \mathbf{s}{\parallel }_0<<N$ . More generally, $\mathbf{s}$ is compressible in the sense that it has many small coefficients, and only a few large coefficients. Results in CS have shown that if $\mathbf{s}$ is sparse or compressible, then it is possible to reconstruct it from $M(M<<N)$ measurements yielded by a measurement matrix $\mathbf{\Phi }\in {\mathbb{R}}^{M\times N}$

$$\mathbf{z}=\mathbf{\Phi }\mathbf{s}$$ (1)

However, it is worthy noting that few signals in practice are truly sparse or compressible themselves; rather they can be sparsely or compressibly represented as $\mathbf{s}=\mathbf{\Psi }\mathbf{w}$ in some representation basis $\mathbf{\Psi }\in {\mathbb{R}}^{N\times N}$ , where $\mathbf{w}$ is sparse or compressible. In such a case, the measurement vector can be reexpressed as

$$\mathbf{z}=\mathbf{\Phi }\mathbf{\Psi }\mathbf{w}=\mathbf{Dw}$$ (2)

where $\mathbf{D}$ is named as a sparsifying dictionary, its column vector ${\mathbf{d}}_i$ is called as atom. Therefore, the sparse recovery problem can be transferred to a dictionary atom selection problem.

Given $\mathbf{z}$ and $\mathbf{D}$ , the goal of CS is to recover $\mathbf{w}$ with high accuracy. Generally, CS achieves this by exploiting the sparsity (compressibility) property of $\mathbf{w}$ . At present, there are various sparse recovery algorithms in the literature, for example, basis pursuit (BP), ²⁰ orthogonal matching pursuit (OMP), ²¹ and sparse Bayesian learning (SBL). ²²

Network model and problem statement

Network model

Without loss of generality, we consider the problem of localization for K targets in a 2D area covered by a WSN, as can be seen in Figure 1(a). Each target is equipped with an emitter which broadcasts beacons periodically. The RSS measurements are collected by M sensors and then transferred to a distant fusion center (FC). At last, in the FC, a sparse reconstruction algorithm is applied to recover the locations of these targets. In this manner, the computing load is transferred from sensors to the FC, significantly reducing the energy consumption of sensors. Assume that the targets and sensors are located with positions $\{{\mathbf{\tau }}_k{\}}_{k=1}^K$ and $\{{\mathbf{t}}_m{\}}_{m=1}^M$ , where ${\mathbf{\tau }}_k=(x_k,y_k)$ denotes the position of the kth target and ${\mathbf{t}}_m$ denotes the position of the mth sensor. Then, the measurement of the mth sensor can be given as

$$z_m=\sum _{k=1}^K{\alpha }_{k}f({\mathbf{t}}_m,{\mathbf{\tau }}_k)+{\epsilon }_m$$ (3)

where ${\alpha }_k$ , ${\epsilon }_m$ , and $f(\mathbf{t},\mathbf{\tau }\mathbf{)}$ denote transmitted power, additive noise, and energy decay function, respectively. In this article, we use the path loss model presented in Clouqueur et al. ²³ to define the energy decay function

$$f(\mathbf{t},\mathbf{\tau })=\{\begin{array}{c}1,\mathrm{if}d<d_0\hfill \\ \multicolumn{1}{c}{\frac{1}{{(d/d_0)}^{\gamma }},\mathrm{otherwise}}\end{array}$$ (4)

where $d=\Vert \mathbf{t}-\mathbf{\tau }{\Vert }_2$ denotes the distance between the transmitter and receiver; $d_0$ denotes the reference distance; and finally, $\gamma$ denotes the path loss coefficient. For the sake of simplicity, we make an assumption that the transmitted powers of all targets are 1. Our goal is to estimate the number K and locations $\mathbf{\Gamma }=\{{\mathbf{\tau }}_{\mathbf{k}}{\}}_{k=1}^K$ of these targets from the noisy measurement vector $\mathbf{z}=[z_1,z_2,\dots ,z_M{]}^{\mathrm{T}}$ .

Figure 1.

(a) The scenario of multiple target localization and (b) an example of grid numbering.

Problem statement

Since the number of targets is limited, localization benefits from CS, the measurement number can be greatly reduced. In order to implement CS, we divide the area of interest into a grid. The grid lines are denoted by vectors $\mathbf{x}=[x_1,x_2,\dots ,x_n{]}^{\mathrm{T}}$ and $\mathbf{y}=[y_1,y_2,\dots ,y_n{]}^{\mathrm{T}}$ , where $x_i$ and $y_i$ denote the ith grid lines in x-axis and y-axis, respectively. The intersections of grid lines are grid points. We number these grid points from 1 to N ( $N=n^2$ ). The numbering rule is shown in Figure 1(b) where the blue numbers denote the number of different grid points. The positions of these grid points, $\mathbf{\Theta }=\{{\mathbf{\theta }}_i{\}}_{i=1}^N$ , can be denoted by $\mathbf{\Theta }=\mathbf{x}\times \mathbf{y}$ and are known in advance. Define the M vector

$$\mathbf{d}\left({\mathbf{\theta }}_i\right)={[f({\mathbf{t}}_1,{\mathbf{\theta }}_i),f({\mathbf{t}}_2,{\mathbf{\theta }}_i),\dots ,f({\mathbf{t}}_M,{\mathbf{\theta }}_i)]}^{\mathrm{T}}$$ (5)

as the atom formed by the ith grid point ${\mathbf{\theta }}_i$ , where $f({\mathbf{t}}_m,{\mathbf{\theta }}_i)$ denotes the RSS collected by the mth sensor from the target at the ith grid point. Therefore, the sparsifying dictionary formed by all grid points $\mathbf{\Theta }$ is given as

$$\mathbf{D}\left(\mathbf{\Theta }\right)=[\mathbf{d}\left({\mathbf{\theta }}_1\right),\mathbf{d}\left({\mathbf{\theta }}_2\right),\dots ,\mathbf{d}\left({\mathbf{\theta }}_N\right)]$$ (6)

Conventional localization approaches based on CS pre-suppose that all targets fall exactly on the discretized grid, namely, $\mathbf{\Gamma }\subset \mathbf{\Theta }$ , then the measurement vector can be approximated as

$$\begin{array}{cc}\multicolumn{1}{c}{\mathbf{z}}& =\sum _{k=1}^K{\alpha }_k\mathbf{d}\left({\mathbf{\tau }}_{\mathbf{k}}\right)+\mathbf{\epsilon }\hfill \\ \multicolumn{1}{c}{}& =\sum _{i=1}^N{w}_i\mathbf{d}\left({\mathbf{\theta }}_i\right)+\mathbf{\epsilon }\hfill \\ \multicolumn{1}{c}{}& =\mathbf{D}\left(\mathbf{\Theta }\right)\mathbf{w}+\mathbf{\epsilon }\hfill \end{array}$$ (7)

where $\mathbf{w}=[w_1,w_2,\dots ,w_N{]}^{\mathrm{T}}$ denotes the representation coefficient formed by approximately representing $\mathbf{z}$ in $\mathbf{D}(\mathbf{\Theta })$ and encodes the number and locations of considered targets. If the kth target falls on the ith grid point, then its element $w_i={\alpha }_k$ ; otherwise, $w_i=0$ . Since the number of targets K is much smaller than the number of grid points N, $\mathbf{w}$ is a K-sparse signal. As a result, the localization issue becomes a sparse recovery issue and $M(M<<N)$ measurements are sufficient to recover $\mathbf{w}$ by exploiting its sparsity with CS.

However, in general, the targets may not fall exactly on the discretized grid no matter how fine we discretize the physical space. The existence of off-grid targets leads to the mismatch between the assumed dictionary and the actual dictionary. As a matter of fact, in practice, a small dictionary mismatch may deteriorate the signal recovery performance dramatically.

Problem formulation

To address such a dictionary mismatch problem, an effective solution is to iteratively optimize over the grid parameter $\mathbf{\Theta }$ and the representation coefficient w, which can be mathematically formulated as

$$[\tilde{\mathbf{w}},\tilde{\mathbf{\Theta }}]=\underset{\mathbf{w},\mathbf{\Theta }}{\mathrm{arg\; min}}\{\Vert \mathbf{z}-\mathbf{D}\left(\mathbf{\Theta }\right)\mathbf{w}{\Vert }_2^2+\lambda {\Vert \mathbf{w}\Vert }_1\}$$ (8)

where the regularization parameter $\lambda$ controls the sparsity of the representation coefficient $\mathbf{w}$ .

Initially, the continuous space is discretized as a uniform grid ${\mathbf{x}}^{\left(0\right)}\times {\mathbf{y}}^{\left(0\right)}$ with r denoting the distance between two adjacent grid lines. Then, the grid lines are dynamically adjusted to alleviate dictionary mismatch by optimizing grid parameters $\mathbf{x}$ and $\mathbf{y}$ . We make an assumption that the distance between any two targets is no less than r. Based on the assumption, the off-grid distance (the distance from the true target to the nearest grid line) is constrained in $[-r/2,r/2]$ . Therefore, we set the maximal adjustment range of all grid lines as $\pm r/2$ . For example, for x-axis grid lines, $x_i\in [x_i^{(0)}-r/2,x_i^{\left(0\right)}+r/2]$ , $i=1,\dots ,n$ , as can be seen in Figure 2.

Figure 2.

An illustration of the upper and lower bounds of the x-axis grid lines.

Then, we can express the upper and lower bounds of the x-axis grid lines as

$${\mathbf{x}}^{\left(u\right)}={\mathbf{x}}^{\left(0\right)}+r/2·1$$ (9)

$${\mathbf{x}}^{\left(l\right)}={\mathbf{x}}^{\left(0\right)}-r/2·1$$ (10)

where $1$ denotes the one vector. Similarly, we can obtain the upper and lower bounds of the y-axis grid lines as

$${\mathbf{y}}^{\left(u\right)}={\mathbf{y}}^{\left(0\right)}+r/2·1$$ (11)

$${\mathbf{y}}^{\left(l\right)}={\mathbf{y}}^{\left(0\right)}-r/2·1$$ (12)

Considering the bounds, problem (8) can be rewritten as

$$\begin{array}{c}[\tilde{\mathbf{w}},\tilde{\mathbf{\Theta }}]=\underset{\mathbf{w},\mathbf{\Theta }}{\mathrm{arg\; min}}\{\Vert \mathbf{z}\mathbf{-}\mathbf{D}\mathbf{\left(}\mathbf{\Theta }\mathbf{\right)}\mathbf{w}{\Vert }_2^2+\lambda {\Vert \mathbf{w}\Vert }_1\}\hfill \\ \mathrm{s}.\mathrm{t}.\mathbf{\Theta }=\mathbf{x}\times \mathbf{y}\hfill \\ {\mathbf{x}}^{\left(l\right)}\le \mathbf{x}\le {\mathbf{x}}^{\left(u\right)}\hfill \\ {\mathbf{y}}^{\left(l\right)}\le \mathbf{y}\le {\mathbf{y}}^{\left(u\right)}\hfill \end{array}$$ (13)

Furthermore, it is worth noting that the representation coefficient $\mathbf{w}=[w_1,w_2,\dots ,w_N{]}^{\mathrm{T}}$ encodes the number and locations of multiple targets. If a target is located on the ith grid points, then its element $w_i=1$ ; otherwise, $w_i=0$ . Therefore, the representation coefficient w should be non-negative. Considering this, problem (13) can be given as

$$\begin{array}{c}[\tilde{\mathbf{w}},\tilde{\mathbf{\Theta }}]=\underset{\mathbf{w},\mathrm{\Theta }}{\mathrm{arg\; min}}\{\Vert \mathbf{z}\mathbf{-}\mathbf{D}\mathbf{\left(}\mathbf{\Theta }\mathbf{\right)}\mathbf{w}{\Vert }_2^2+\lambda {\Vert \mathbf{w}\Vert }_1\}\hfill \\ \multicolumn{1}{c}{\mathrm{s}.\mathrm{t}.\mathbf{\Theta }=\mathbf{x}\times \mathbf{y}}\\ \multicolumn{1}{c}{{\mathbf{x}}^{\left(l\right)}\le \mathbf{x}\le {\mathbf{x}}^{\left(u\right)}}\\ \multicolumn{1}{c}{{\mathbf{y}}^{\left(l\right)}\le \mathbf{y}\le {\mathbf{y}}^{\left(u\right)}}\\ \multicolumn{1}{c}{0\le \mathbf{w}}\end{array}$$ (14)

where $0$ denotes the zero matrix.

Localization via dictionary refinement

In this section, we first discuss how to solve problem (14) and then present how to achieve accurate localization using the solution.

Dictionary refinement algorithm

The process of the proposed dictionary refinement algorithm is summarized in Algorithm 1. The algorithm starts with an initial equi-spaced grid sampling ${\mathbf{\Theta }}^{(0)}=({\mathbf{x}}^{(0)},{\mathbf{y}}^{(0)})$ , where ${\mathbf{x}}^{(0)}$ and ${\mathbf{y}}^{(0)}$ denote the initial values of x-axis and y-axis grid lines. Then, the grid $\mathbf{\Theta }$ is iteratively adjusted to reduce or even eliminate the dictionary mismatch.

Algorithm 1 Dictionary refinement algorithm.
Input: ${\mathbf{x}}^{\left(0\right)}$ , ${\mathbf{y}}^{\left(0\right)}$ , $i=0$ , $k_{\mathrm{out}}$ , $r_{\mathrm{th}}$
Iteration:
1: while $i<k_{\mathrm{out}}$ and $r_i>r_{\mathrm{th}}$ do
2: update ${\tilde{\mathbf{w}}}^{(i+1)}$ according to equation (15);
3: approximate the true $\mathbf{w}$ according to equation (16);
4: update ${\tilde{\mathbf{\Theta }}}^{(i+1)}$ according to equation (17);
5: calculate $r_{i+1}$ according to equation (21);
6:  $i\leftarrow i+1$ .
7: end while
8: $\tilde{\mathbf{w}}\leftarrow {\hat{\mathbf{w}}}^{\left(i\right)},\tilde{\mathrm{\Theta }}\leftarrow {\tilde{\mathbf{\Theta }}}^{\left(i\right)}$ .
Output:
$\tilde{\mathbf{w}}$ , $\tilde{\mathbf{\Theta }}$

We develop an iterative two-step algorithm to solve problem (14). The key idea of the algorithm is to alternately optimize over sparse signal w and parameter $\mathbf{\Theta }$ in each iteration. The first step of the algorithm optimizes over the representation coefficient w while keeping the grid parameters $\mathbf{\Theta }$ fixed

$$\begin{array}{c}{\tilde{\mathbf{w}}}^{(i+1)}=\underset{\mathbf{w}}{\mathrm{arg\; min}}\{\Vert \mathbf{z}-D\left({\tilde{\mathbf{\Theta }}}^{\left(i\right)}\right)\mathbf{w}{\Vert }_2^2+\lambda {\Vert \mathbf{w}\Vert }_1\}\hfill \\ \multicolumn{1}{c}{\mathrm{s}.\mathrm{t}.0\le \mathbf{w}}\end{array}$$ (15)

where superscripts denote algorithm iteration. This is a standard regularized LS optimization problem, and there exist many tools to solve this problem. In our implementation, we use the convex optimization software package. ²⁴

In practice, the solution $\tilde{\mathbf{w}}$ to equation (15) may only have a small number of significant coefficients and many negligible, but non-zero coefficients. These small coefficients contribute very little to the sparse signal. Therefore, we approximate the true w by neglecting the small coefficients

$$\hat{\mathbf{w}}=H\left(\tilde{\mathbf{w}}\right):{\hat{w}}_i=\{\begin{array}{c}0,20{\log }_{10}\left(\frac{{\tilde{w}}_i}{\underset{j}{\max }\left|{\tilde{w}}_j\right|}\right)<\delta \hfill \\ \multicolumn{1}{c}{{\tilde{w}}_i,\mathrm{otherwise}}\end{array}$$ (16)

where $\delta$ is a small negative sparsity threshold.

The second step optimizes over the grid parameters $\mathbf{\Theta }$ while keeping the approximated representation coefficient $\hat{\mathbf{w}}$ fixed

$$\begin{array}{c}{\tilde{\mathbf{\Theta }}}^{(i+1)}=\underset{\mathrm{\Theta }}{\mathrm{arg\; min}}\{\Vert z-\mathbf{D}\left(\mathbf{\Theta }\right){\hat{\mathbf{w}}}^{(i+1)}{\Vert }_2^2\}\hfill \\ \mathrm{s}.\mathrm{t}.\mathbf{\Theta }=\mathbf{x}\times \mathbf{y}\hfill \\ {\mathbf{x}}^{\left(l\right)}\le \mathbf{x}\le {\mathbf{x}}^{\left(u\right)}\hfill \\ {\mathbf{y}}^{\left(l\right)}\le \mathbf{y}\le {\mathbf{y}}^{\left(u\right)}\hfill \end{array}$$ (17)

We solve the problem using a trust-region subspace method ²⁵ where the gradient of objective function must be provided. For the sake of convenience, we transform the grid parameters $\mathbf{\Theta }$ into a vector $\mathbf{\theta }=[{\mathbf{x}}^{\mathrm{T}},{\mathbf{y}}^{\mathrm{T}}{]}^{\mathrm{T}}=[{\theta }_1,\dots ,{\theta }_{2n}{]}^{\mathrm{T}}$ (notably, a grid is determined by grid lines or grid points; therefore, we will use $\mathbf{\theta }$ and $\mathbf{\Theta }$ interchangeably to represent an example of grid in the rest of this article). Next, we deduce the gradient of objective function with respect to $\mathbf{\theta }$ .

Let

$$F\left(\mathbf{\Theta }\right)=\Vert \mathbf{z}-\mathbf{D}\left(\mathbf{\Theta }\right)\mathbf{w}{\Vert }_2^2$$ (18)

Denote by ${\nabla }_{i}F\left(\mathbf{\Theta }\right)$ , the derivation of $F\left(\mathbf{\Theta }\right)$ with respect to ${\theta }_i$ , $1\le i\le 2n$ , then we have

$${\nabla }_{i}F\left(\mathbf{\Theta }\right)=-2{(\mathbf{z}-\mathbf{Dw})}^{\mathrm{T}}\left({\nabla }_i\mathbf{D}\right)\mathbf{w}$$ (19)

where ${\nabla }_i\mathbf{D}$ indicates the gradient of the sparsifying dictionary D with respect to ${\theta }_i$ , where $1\le i\le 2n$ . As a matter of fact, according to the grid numbering rule, only n atoms of D are dependent on ${\theta }_i$ while the others are not. Therefore, the gradient of F can be given by (20)

$${\nabla }_{i}F\left(\mathbf{\Theta }\right)=\{\begin{array}{cc}-2{\left(z-Dw\right)}^{\mathrm{T}}{\displaystyle \sum _{j=i:n:n\left(n-1\right)+i}{w}_j}{\nabla }_i{d}_j& 1⩽i⩽n\\ -2{\left(z-Dw\right)}^{\mathrm{T}}{\displaystyle \sum _{j=n\left(i-n-1\right)+1:n\left(i-n\right)}{w}_j}{\nabla }_i{d}_j& n+1⩽i⩽2n\end{array}$$ (20)

After each iteration, the current system cost is calculated as

$$\begin{array}{c}{r}_{i+1}=\Vert \mathbf{z}-\mathbf{D}\left({\tilde{\mathbf{\Theta }}}^{(i+1)}\right){\tilde{\mathbf{w}}}^{(i+1)}{\Vert }_2^2+\lambda {\Vert {\tilde{\mathbf{w}}}^{(i+1)}\Vert }_1\hfill \end{array}$$ (21)

Remark 1

Algorithm 1 is a two-layer iteration procedure. In each outer iteration, sparse signal w and parameter $\mathbf{\Theta }$ are updated sequentially with maximum outer iteration number $k_{\mathrm{out}}$ . Besides, the optimization of parameter $\mathbf{\Theta }$ is also an iteration procedure with maximum inner iteration number $k_{\mathrm{in}}$ .

Remark 2

The algorithm stops when the convergence condition is reached, for example, when the iteration has been executed the maximum outer iteration number $k_{\mathrm{out}}$ or the current system cost is smaller than the cost threshold $r_{\mathrm{th}}$ .

Localization

The output results $\tilde{\mathbf{w}}$ and $\tilde{\mathbf{\Theta }}$ encode the number and locations of considered targets. The estimated target number $\hat{K}$ and target locations ${\hat{\mathbf{\theta }}}_k$ are given by

$$\hat{K}=\Vert \hat{\mathbf{w}}{\Vert }_0$$ (22)

$${\hat{\mathbf{\theta }}}_k={\tilde{\mathbf{\theta }}}_{I_k}$$ (23)

where $\left\{I_k\right\}$ is an ordered set such that $\left|{\hat{w}}_{I_k}\right|$ is the kth-largest element of $\hat{\mathbf{w}}$ .

Numerical evaluation

In this section, we conduct simulations to evaluate the effectiveness and robustness of the proposed dictionary refinement algorithm.

Simulation setup

All simulations are conducted on MATLAB R2015b. We consider a $9\mathrm{m}\times 9\mathrm{m}$ square area with $K=3$ targets. To apply CS, we sample the area into a $10\times 10$ grid, that is, r = 1m. RSS measurements from these targets are collected by $M=36$ sensors. Unless otherwise stated, we use the same scenario in the later simulations. For the sake of convenience, we refer to the proposed dictionary refinement algorithm as DicRef and compare it with the traditional CS reconstruction algorithms, including BP, OMP, and SBL.

In order to assign an estimated location to a target, we compute all pairs of the distances between ${\mathbf{\tau }}_{\mathbf{k}}$ and ${\hat{\theta }}_k$ and sort them in a non-decreasing order. Based on the sorted list, we assign a target to the first unused estimated location.

Definition 1

The average localization error, denoted by Avg.Error, is defined to be the ratio of the average distance between the estimated and actual locations of all targets versus the minimum between the estimated and actual target numbers

$$\mathrm{Avg}.\mathrm{Error}=\frac{\sum _{k=1}^{K_{\min }}{\Vert {\mathbf{\tau }}_k-{\hat{\mathbf{\theta }}}_k\Vert }_2}{K_{\min }}$$ (24)

where ${\mathbf{\tau }}_k$ and ${\hat{\mathbf{\theta }}}_k$ denote the true and estimated locations for the kth target, respectively, and $K_{\min }=min\{K,\hat{K}\}$ . All results are averaged over 100 random trials.

We have observed from simulations that the decrement of objective function usually becomes quite small within very few iterations for trust-region subspace method. Based on the observation, to reduce time cost, we set the maximum inner iteration number $k_{\mathrm{in}}=3$ in our simulations. Table 1 summarizes some parameter values used for our simulations.

Table 1.

Parameter values for simulations.

Parameters	Explanation	Values
$\lambda$	Regularization parameter	1
$\delta$	Sparsity threshold	–5 dB
$d_0$	Reference distance	1 m
$\gamma$	Path loss coefficient	2
$r_{\mathrm{th}}$	Cost threshold	0.01
$k_{\mathrm{out}}$	Maximum iteration number	100

Simulation without off-grid targets

We first consider an ideal situation where all targets are located exactly on the initial grid. The true locations of three targets are set to (4, 3), (8, 6), and (5, 8). Figure 3 shows the counting and localization results of different algorithms. It can be seen that all algorithms accurately estimate the number of these targets. In terms of localization, it can be seen that BP, SBL, and DicRef are able to accurately estimate the locations of multiple targets. In contrast, OMP fails to localize the first target.

Figure 3.

Counting and localization results of different algorithms when all targets fall exactly on the initial grid.

Simulation with off-grid targets

Then, we consider a more general situation where there exist targets deviating from the initial grid. The true positions of three targets are set to (3.85, 3.47), (8.42, 5.84), and (5.35, 8.26), respectively. In such case, all targets are located off the initial grid. Figure 4 shows the counting and localization results of different algorithms.

Figure 4.

Counting and localization results of different algorithms when there exist targets deviating from the initial grid.

As can be shown in Figure 4, when there is no noise, BP, SBL, and DicRef correctly estimate the number of targets, while OMP suffers from false targets. As for localization, the traditional CS reconstruction algorithms localize three targets to the nearest grid points. Unsurprisingly, these behaviors are the natural results incurred by dictionary mismatch. In contrast, the positions estimated by DicRef are so accurate that they are visually indistinguishable from their original positions. This example clearly indicates that, compared with the traditional CS reconstruction algorithms, the proposed dictionary refinement algorithm is able to provide better performance when there are targets deviating from the initial grid.

Effect of measurement noise

It is inevitable for measurements to be corrupted with environmental noise. In order to check the robustness of the proposed dictionary refinement algorithm against measurement noise, we intentionally add Gaussian white noise $\mathcal{N}(0,{\sigma }^2\mathbf{I})$ to measurements, where ${\sigma }^2$ denotes the variance of noise. We define the signal-to-noise ratio (SNR) as $10\underset{10}{\log }(\parallel \mathbf{z}{\parallel }_2^2/(M{\sigma }^2))$ .

Figure 5 reports the average estimated target numbers, probabilities of correct counting, and average localization errors of different algorithms under different measurement noise levels. As can be observed, with the increasing of SNR, the average estimated target numbers of all algorithms gradually approximate to the true target number, which is indicated by the horizontal baseline in Figure 5(a). When SNR is low, the proposed dictionary refinement algorithm performs much better than the other algorithms. As SNR is high, BP, SBL, and DicRef can estimate the number of targets accurately while OMP suffers from false targets. As for the probability of correct counting, the behaviors of different algorithms are similar with the average estimated target numbers. The probabilities of correct counting with respect to all algorithms increase with the increasing of SNR. When noise is serious, DicRef performs better than the other algorithms. As noise is slight, the probabilities of correct counting with respect to BP, SBL, and DicRef approximate to 1. However, the probability of correct counting of OMP keeps below 0.21 in the entire SNR range. Additionally, the average localization errors for all algorithms decrease as the SNR increases. As a matter of fact, this is reasonable as the signal reconstruction accuracy is proportional to SNR. Another important observation is that the proposed dictionary refinement algorithm performs better than the other algorithms no matter how high the noise level is. The reason lies in the fact that the proposed algorithm dynamically adjusts the grid to refine the dictionary while the other algorithms do not. Furthermore, we can see that the proposed dictionary refinement algorithm can tolerate a certain level of measurement noise. For example, when SNR is higher than 30 dB, the average localization error with respect to DicRef is no more than 0.1 m.

Figure 5.

Counting and localization performance versus SNR when measurement number $M=36$ : (a) average estimated target number, (b) probability of correct counting, and (c) conditional average localization error.

Then, to further examine the performance of the proposed dictionary refinement algorithm, we compare the cumulative distribution functions of the average localization errors of different algorithms when SNR $=20$ dB. The results are shown in Figure 6. An important observation is that the proposed dictionary refinement algorithm performs significantly better than the traditional CS reconstruction algorithms. For example, when the average localization error is limited under 1 m, the proposed dictionary refinement algorithm DicRef achieves an impressive improvement of 15% over SBL, 45% over BP, and 57% over OMP.

Figure 6.

Cumulative distribution functions (CDFs) of average location errors.

Effect of measurement number

Now, we check the performance of the proposed dictionary refinement algorithm with different measurement numbers. We set target number $K=5$ , SNR $=20$ dB and vary measurement number M from 30 to 36. The results are plotted in Figure 7, where the horizontal baseline indicates the true target number. It can be seen that, as expected, increasing measurement number brings about both counting and localization performance improvement for all algorithms. It is reasonable because the sparse recovery accuracy is proportional to measurement number when the other parameters are fixed. More importantly, compared to the others, the proposed algorithm DicRef shows significantly superior performance. The superiority can be attributed to the fact that the proposed algorithm dynamically adjusts the grid to refine the dictionary while the others suffer from serious dictionary mismatch.

Figure 7.

Counting and localization performance versus measurement number when $\mathrm{SNR}=20\mathrm{dB}$ : (a) average estimated target number, (b) probability of correct counting, and (c) conditional average localization error.

Results on different parameters

Then, to further test the performance of the proposed algorithm, we sample the same area into a denser grid with $19\times 19$ grid points. In such a case, the signal length $N=361$ , and the parameter $r=0.5m$ . We set target number $K=5$ and measurement number $M=100$ , the counting and localization results are shown in Figure 7. From Figure 7, the traditional CS reconstruction algorithms miss most targets and only estimate few targets on the near grid points. Obviously, the inferior performance is caused by dictionary mismatch. Contrastively, the proposed dictionary refinement algorithm accurately localizes all targets, and the errors are negligible. The superior performance attributes to the fact that DicRef is able to dynamically adjust grid to refine the assumed dictionary.

Complexity analysis

Eventually, we analyze the complexities of different algorithms in terms of computational complexity and CPU running times. The results are shown in Table 2. For BP, OMP, and SBL, the computational complexity are $O(N^3)$ , $O(N{K}^2)$ , and $O(N{M}^2)$ , respectively. As for DicRef, the computational complexity is dominated by the optimization of sparse signal w and parameter $\mathbf{\Theta }$ . The former is $O(N^3)$ and the latter is reduced by restricting the inner iteration number to 3. In terms of average CPU running times (over 100 trials), it can be clearly seen that DicRef is much more accurate than the other algorithms while it is inferior to the other algorithms in terms of CPU running time. The inferiority is mainly attributed to the following two factors. On one hand, DicRef is an iterative algorithm and it usually converges until a number of iterations. On the other hand, in practice, we observe that the grid parameter optimization is time consuming in each iteration. As a matter of fact, the running time can be reduced with slight accuracy loss by setting the maximum outer iteration number $k_{\mathrm{out}}$ to be a smaller value. To sum up, we can conclude that the proposed localization method can be applied in the scenarios which are sensitive to accuracy but insensitive to real time.

Table 2.

Complexity analysis of different algorithms.

Algorithms	Average error (m)	Complexity	CPU running time (s)
BP	1.39	$O\left(N^3\right)$	0.17
OMP	1.51	$O\left(N{K}^2\right)$	0.01
SBL	0.91	$O\left(N{M}^2\right)$	0.14
DicRef	0.56	$O\left(N^3\right)$	23.74

BP: basis pursuit; OMP: orthogonal matching pursuit; SBL: sparse Bayesian learning.

Conclusion

In this article, we investigated the dictionary mismatch problem in CS-based localization and developed an efficient dictionary refinement algorithm. Different from the other CS reconstruction algorithms using a fixed grid, the proposed dictionary refinement algorithm dynamically adjusts the grid to alleviate or even eliminate dictionary mismatch. To achieve this, we view the sparsifying dictionary as a parameterized dictionary, with the sampled grid as adjustable parameters; then the localization problem is transformed into a joint sparse signal recovery and parameter estimation problem; at last, an iterative two-step algorithm is developed to solve the joint optimization problem. Simulation results show that, compared to the most existing CS reconstruction algorithms, the proposed dictionary refinement algorithm achieves better performance with high time cost. In the future, we will seek for alternative solutions to reduce the cost of the proposed algorithm at the expense of allowed performance loss.