Consensus-based sparse signal reconstruction algorithm for wireless sensor networks

Abstract

This article presents a distributed Bayesian reconstruction algorithm for wireless sensor networks to reconstruct the sparse signals based on variational sparse Bayesian learning and consensus filter. The proposed approach is able to address wireless sensor network applications for a fusion-center-free scenario. In the proposed approach, each node calculates the local information quantities using local measurement matrix and measurements. A consensus filter is then used to diffuse the local information quantities to other nodes and approximate the global information at each node. Then, the signals are reconstructed by variational approximation with resultant global information. Simulation results demonstrate that the proposed distributed approach converges to their centralized counterpart and has good recovery performance.

Keywords

Compressive sensing sparse variational Bayesian consensus filter wireless sensor networks

Introduction

The ongoing concerns about environment and global warming pose more challenges in meeting the increasing demand for deployment of wireless communication networks.^1,2 The green communication (GC) has become a new trend in the design and operation of wireless communication networks. In the future communication system, the Internet of Things (IoT) will play an important role. As a key enabling technology of IoT, wireless sensor networks (WSNs) help IoT to flourish by fusing sensing and wireless communication.^3,4 Generally, a WSN consists of a large number of sensor nodes with low processing, limited power, low storage capacity, and unreliable communication over short-range radio links.^5,6 Based on the WSNs, the potential applications of IoT in industrial automation, habitat monitoring, and smart cities are numerous and diverse.^7–10 However, the energy demand for IoT will increase dramatically in the near future considering the widespread interest and adoption of various organizations, which will lead to higher carbon footprint and other environmental issues.

The recently developed compressive sensing (CS) theory^11,12 is a new sampling paradigm that can achieve acquisition of information contained in a large-scale data using much fewer samples than that are required by Nyquist sampling theorem. By exploiting sparsity, which is inherent characteristic of many natural signals, CS enables the signal to be stored in few samples and subsequently be recovered accurately. Moreover, the CS has been extensively applied in WSNs since the signals in many applications exhibit sparsity. Sparse Bayesian learning (SBL) was introduced in Tipping¹³ and has become a popular method for sparse signal recovery in CS.^14,15 In SBL, the sparse signal recovery problem is formulated from a Bayesian perspective, while the sparsity information is exploited by assuming a hierarchical sparse prior to the signal of interest. To recover the values of model parameters, an inference algorithm is derived based on well-known Type-II Maximum Likelihood which assumes that the hyperprior are uninformative.¹⁶ In contrast to uninformative, a fully Bayesian treatment was introduced in Bishop and Tipping¹⁷ with the variational rendition of sparse Bayesian learning (VSBL), where both the model parameters and hyperparameters can be estimated for the distribution.¹⁶

On the other hand, due to the high fault tolerance and scalability, distributed processing is becoming increasingly popular in WSNs applications. Different from the centralized approach that rely on a fusion center (FC), distributed processing requires no central coordinator and only single-hop communications among neighbors that aim to achieve consensus on local estimates. However, most sparse signal recovery algorithms operate in a centralized manner. Recently, distributed processing for CS applications has received considerable attention.^18–21 Moreover, the VSBL algorithm is a centralized method and may not be used for sparse signal reconstruction in a distributed WSN directly.

Average-consensus algorithms have lately investigated as a family of low-complexity iterative distributed algorithms, where sensors in a group communicate with each other to reach a consensus.²² In more detail, each sensor receives information from others and adjusts their own information state with the goal to reach an agreement in a scalable and fault-tolerant manner.²³ Consensus was initially elaborated in Tsitsiklis et al.²⁴ and has received a considerable attention in many subjects due to its wide range of applications such as load balancing in parallel calculation,²⁵ coordination of autonomous agents, distributed control,²⁶ and data fusion.^27–29

In this article, we develop a distributed sparse signal reconstruction algorithm using probabilistic graphical models in the Bayesian framework. First, three global information quantities are particularly designed for distributed Sparse Bayesian inference by centralized update equations. Then, several average-consensus iterations are needed to reach a consensus on global information quantities in each local variational Bayesian (VB) step. In comparison with the centralized VSBL algorithms, the proposed algorithm allows each sensor to parallelly reconstruct sparse signal with local information and moderate inter-node communication.

The rest of this article is structured as follows: the fundamental of compressive sampling is provided in section “Background,” and introduces the sparse signal recovery using SBL. The system model is described in section “Problem statement and system model.” The centralized variational Bayesian inference for the system model is developed in section “Variational approximation.” Then, the proposed distributed sparse signal reconstruction is presented in section “Distributed variational SBL algorithm.” Numerical results are provided in section “Simulations,” followed by conclusions in the final section.

Notation

Throughout this article, we use b, B , and b for scalars, matrices, and column vectors, respectively. The superscripts $(\cdot)^{T}$ and $(\cdot)^{- 1}$ denote the transpose and the inverse of a matrix, respectively. $E_{p (x)} (\cdot)$ denotes the expectation with respect to $p (x)$ . $U_{int} [a, b]$ and $N (μ, \sum)$ denote the integer uniform distribution in the interval $[a, b]$ and multivariate Gaussian distribution with mean $μ$ and variance $\sum$ , respectively. $I_{N}$ and $tr$ denote the $N \times N$ identity matrix and trace of matrix, respectively. $| | \cdot | |_{0}$ , $| | \cdot | |_{p}$ , and $| | \cdot | |_{2}$ denote $ℓ_{0} - norm$ , $ℓ_{p} - norm$ , and $ℓ_{2} - norm$ , respectively.

Background

In this following, we will briefly review the principle of CS and SBL,^13,30 which is a centralized sparse signal recovery algorithm.

Let $s \in R^{N}$ be an original signal, consider the following noisy measurement model

y = Φ s + v

(1)

where $y \in R^{M}$ is the measurement vector, $Φ \in R^{M \times N}$ denotes the measurement matrix, and $v \in R^{M}$ denotes the measurement noise. For the CS signal reconstruction, the s is assumed to have a sparse representation $x \in R^{N}$ on some basis $Ψ \in R^{N \times N}$ , that is, $s = Ψ x$ . According to the characteristics of signal, the basis has a predefined structure, for example, wavelet basis and Fourier basis. While $| | x | |_{0} = s << N$ , the signal can be considered as sparse over the basis. Therefore, equation (1) can be modified as follows

y = Hx + v

(2)

where $H = Φ Ψ \in R^{M \times N}$ is also referred as equivalent measurement matrix.

In order to recover x from the noisy measurement y , following optimization problem can be used

min_{x} | | x | |_{0}, s . t . | | Hx - y | | \leq ϵ

(3)

where $ϵ > 0$ is an estimate of the measurement noise level. Since the above optimization problem (3) is non-deterministic polynomial (NP)-hard and cannot be solved effectively, the conventional CS approaches generally resort to solve the following optimization problem

min_{x} \frac{1}{2} | | Hx - y | |_{2} + λ | | x | |_{p}

(4)

where $0 < p \leq 1$ and $λ > 0$ are regularized parameters. When $p = 1$ , the problem in equation (4) becomes a convex problem, and the solution of equation (3) can be obtained with overwhelming probability. For $p < 1$ case, equation (4) is non-convex but a closer approximation to sparsity than $p = 1$ case and shows superior performance.^31,32

From a Bayesian perspective, the CS problem can be also formulated by SBL whose close relationship to non-convex $ℓ_{p} - norm$ minimization problem is revealed in Wipf and colleagues.^33,34 In SBL framework, a zero-mean Gaussian prior distribution is considered

p (x | Γ) = Π_{i = 1}^{N} N (x_{i} | 0, γ_{i})

(5)

where $Γ \in R^{N \times N}$ is a diagonal matrix that is composed of N hyperparameters $γ_{i} (i = 1, \dots, N)$ controlling the prior variance of each component. In Tipping,¹³ and Wipf and colleagues,^30,34 the rationale of using this prior has been elaborated. With uniform hyperpriors $p (γ_{i})$ and $p (σ^{2})$ , one can infer these hyperparameters by maximizing

\begin{matrix} \log p (Γ, σ^{2} | y) \propto \log p (y | Γ, σ^{2}) \\ = \log \int p (y | x, σ^{2}) p (x | Γ) d x \end{matrix}

(6)

As per the analysis in Tipping,¹³ solving equation (6) is equivalent to minimizing the following cost function

L = \log | \sum | + y^{T} \sum^{- 1} y

(7)

where $\sum = σ^{2} I_{M} + H Γ H^{T}$ . In Tipping,¹³ the expectation maximization (EM) algorithm is employed to solve equation (17). Given these hyperparameters, x can be obtained by maximizing the posterior distribution

\begin{matrix} x & = \arg max_{x} p (x | y, Γ, σ^{2}) \\ = \arg max_{x} p (y | x, σ^{2}) p (x | Γ) \\ = Γ H^{T} \sum^{- 1} y \end{matrix}

(8)

In Wipf and colleagues,^30,34 authors provide the theoretical justification for applying SBL to sparse signal recovery and demonstrate superior performance compared with other algorithms.

Problem statement and system model

A network with K nodes modeled by an undirected graph $G = (V, E, A)$ of the order K is considered in this study. In the considered system, the nodes in $V = {1, 2, \dots, K}$ represent the sensors, the edge $(k, l)$ in the set $E \subseteq E \times E$ models that sensor l can transmit the information to sensor k, and the adjacency matrix $A = [a_{kl}]_{K \times K}$ with non-negative adjacency element $a_{ij}$ . An edge of $G$ is positive, that is, $a_{kl} > 0 \Leftrightarrow (k, l) \in E$ . Node j is called a neighbor of node i if $(k, l) \in E$ and $l \neq k$ . The neighbor set of node k is denoted by $N_{k}$ . Each node is able to process the data that are stored locally and exchange messages with its neighbors. An example graph is illustrated in Figure 1.

Figure 1.

An example of network structure.

Assuming that each node observes a linear combinations of unknown sparse signal $x \in R^{N}$ , the resultant matrix will be sparse. Then, the measurement corrupted by some noise at node k is as follows

y_{k} = H_{k} x + e_{k}

(9)

where $y_{k} \in R^{m_{k}}$ is the local measurement of node k, $m_{k}$ is the number of simultaneous measurements made at node k, $H_{k} \in R^{m_{k} \times N}$ is the local measurement matrix of node k, $m_{k}$ is the number of simultaneous measurements made at node k, and $e_{k} \in R^{m_{k}}$ is the measurement noise at node k. The measurements at all K nodes are stacked as follows. Let M be the total number of measurements at all nodes, that is, $M = \sum_{k = 1}^{K} m_{k}$ . The global measurement vector, $Y \in R^{M}$ , the global observation matrix, $H \in R^{M \times N}$ , and the global observation noise vector, $e \in R^{M}$ , are defined as follows

Y = [\begin{matrix} y_{1} \\ ⋮ \\ y_{K} \end{matrix}], H = [\begin{matrix} H_{1} \\ ⋮ \\ H_{K} \end{matrix}], e = [\begin{matrix} e_{1} \\ ⋮ \\ e_{K} \end{matrix}]

(10)

Then the global observation model is given by

Y = Hx + e

(11)

where $e ~ N (0, β^{- 1} I_{M})$ . The elements of H are derived from a Gaussian distribution with zero mean and variance $1 / M$ . Note that this construction of H satisfies the restricted isometry property (RIP) in the design of CS schemes. From the measurement model (11) and noise statistics, the measurements likelihood function is set by

\begin{matrix} p (Y | x, β) & = Π_{k = 1}^{K} p (y_{k} | x, β) \\ = Π_{k = 1}^{K} \frac{β^{m_{k} / 2}}{{(2 π)}^{m_{k} / 2}} \exp [- \frac{β}{2} | | y_{k} - H_{k} x | |^{2}] \end{matrix}

(12)

Moreover, an appropriate conjugate prior with respect to equation (12) is further attached on the parameter $β$ so as to complementing the likelihood. The prior for the noise precision $β$ is selected to be a Gamma distribution with parameters $ϱ$ and $δ$ , that is

p (β | ϱ, δ) = G (β | ϱ, δ) = \frac{δ^{ϱ} β^{ϱ - 1} \exp [- δ β]}{Γ (ϱ)}

(13)

To reflect our knowledge about sparsity of x , a hierarchically heavy-tailed prior is selected for the signal x next. There are two levels of hierarchy set for the model. For the first level, a Gaussian prior is attached to x , that is

\begin{matrix} p (x | α) & = N (x | 0, A^{- 1}) = Π_{i = 1}^{N} p (x_{i} | α_{i}) \\ = Π_{i = 1}^{N} {(2 π)}^{- 1 / 2} α_{i}^{1 / 2} \exp [- \frac{1}{2} x_{i}^{2} α_{i}] \end{matrix}

(14)

where $α = [α_{1}, α_{2}, \dots, α_{N}]^{T}$ is a vector of precision parameters of $x_{i} s$ , $A = diag (α)$ and the $x_{i} s$ have been assumed to be a priori independent. Next, as the second level, the precision parameters $α_{i} s$ also depend on a prior distribution which is assumed to follow a Gamma distribution, expressed as

p (α_{i} | a_{i}, b_{i}) = G (α_{i} | a_{i}, b_{i}) = \frac{b_{i}^{a_{i}} α_{i}^{a_{i} - 1} \exp [- b_{i} α_{i}]}{Γ (a_{i})}

(15)

So far, the system model is developed. For the Bayesian model described above, we illustrate the directed acyclic graph (DAG) in Figure 2, where $a = [a_{1}, \dots, a_{N}]^{T}$ and $b = [b_{1}, \dots, b_{N}]^{T}$ . Now, the centralized variational approximation method for the developed hierarchical Bayesian model is presented in the next section.

Figure 2.

DAG of the hierarchical Bayesian model.

Variational approximation

According to Bayes’ theorem

p (φ | Y, ϕ) = \frac{p (Y | φ) p (φ | ϕ)}{p (Y | ϕ)}

(16)

where $φ = [x_{1}, \dots, x_{n}, β, α_{1}, \dots, α_{m}]^{T}$ are the unknown parameters and hidden variables of the model, and $ϕ = [a_{1}, \dots, a_{n}, b_{1}, \dots, b_{n}, δ, ϱ]^{T}$ are the hyperparameters of the imposed prior. In order to estimate the value of the hyperparameters, that is, $ϕ$ , the following log-likelihood is maximized

\log p (Y | ϕ) = F (q (φ)) + KL (q (φ) | | p (φ | Y, ϕ))

(17)

where F is the free energy given by the following expression

F (q (φ), ϕ) = \int q (φ) \log (\frac{p (Y | φ) p (φ | ϕ)}{q (φ)}) d φ

(18)

and

KL (q (φ) | | p (φ | Y, ϕ)) = \int q (φ) \log (\frac{q (φ)}{p (φ | Y, ϕ)})

(19)

where KL is the Kullback–Leibler divergence between the true posterior $p (φ | Y, ϕ)$ and the variational distribution $q (φ)$ . It is noted here that the KL divergence is greater than or equal to zero and is minimized when $q (φ) = p (x | Y, ϕ)$ . Hence, $F (q (φ), ϕ)$ also can be regarded as evidence lower bound. The minimization of KL divergence is equivalent to maximizing the evidence lower bound. From an optimization point of view, the model parameters of $q (φ)$ is well-suited so that the lower bound can be minimized. However, due to the complexity of model, computing the posterior of interest is troublesome. Thus, we resort to a simpler variational free form $q (x, β, α)$ to approximate the posterior in equation (16).

Based on the mean-field theory from statistical physics, $q (x, β, α)$ can be fully factorized into a family of q-distribution with respect to the parameters as follows

\begin{matrix} q (x, β, α) & = q (x) q (β) q (α) \\ = Π_{i = 1}^{N} q (x_{i}) q (β) Π_{i = 1}^{N} q (α_{i}) \end{matrix}

(20)

that is, all model parameters are assumed to be a posteriori independent. This fully factorized form of distribution $q (x, β, α)$ turns out to be computationally tractable. In fact, if $φ_{i}$ denote the ith component of the vector $φ = [x_{1}, \dots, x_{N}, β, α_{1}, \dots, α_{N}]^{T}$ containing the parameters of the Bayesian hierarchical model, then $φ_{- i}$ refers to all parameters after removing the ith component. Maximizing the free energy in equation (17) is realized by computing the functional derivatives with respect to each of the $q (\cdot)$ distributions while fixing the other distributions and setting $\partial F (q) / \partial q (\cdot) = 0$ . Furthermore, the computation of $\partial F (q) / \partial q (\cdot) = 0$ can be expressed as follows³⁵

\log q (φ_{i}) \propto E_{q (φ_{- i})} [\log (p (Y | φ) p (φ | ϕ))]

(21)

where $E_{q (φ_{- i})}$ denotes the expectation with respect to $\underset{j \neq i}{Π} q (φ_{j})$ . This cannot be solved directly, as all the factors $q (φ_{i})$ are interdependent on each other. Then, the coupled $q (φ_{i})$ involves an optimization process in turn, where the factors are initialized appropriately, and each one of them is updated iteratively. Moreover, the lower bound is known to be gradually increased until convergence in this process.

The log joint distribution of Y and $φ$ is expressed as follows

\log (p (Y | φ) p (φ | ϕ)) = \sum_{k = 1}^{K} \log p (y_{k} | x, β) + \sum_{i = 1}^{N} p (x_{i} | α_{i}) + \sum_{k = 1}^{K} \sum_{i = 1}^{m_{k}} p (α_{i} | a_{i}, b_{i}) + p (β | δ, ϱ)

(22)

Due to the conjugacy properties of the chosen distributions, as mentioned previously, a general solution (21) can be derived analytically as follows

\begin{matrix} q (x) & \propto \exp (E_{q (α) q (β)} [\log (p (Y | φ) p (φ | ϕ))]) \\ \propto \exp (E_{q (β)} [\sum_{k = 1}^{K} \log p (y_{k} | x, β)] + E_{q (α)} [\sum_{i = 1}^{N} p (x_{i} | α_{i})]) \\ \propto N (x | m, \sum) \end{matrix}

(23)

\begin{matrix} q (β) & \propto \exp (E_{q (x) q (α)} [\log (p (Y | φ) p (φ | ϕ))]) \\ \propto \exp (E_{q (x)} [\sum_{k = 1}^{K} \log p (y_{k} | x, β)] + E_{q (α)} [\sum_{i = 1}^{N} p (x_{i} | α_{i})]) \\ \propto G (β | \tilde{ϱ}, \tilde{δ}) \end{matrix}

(24)

\begin{matrix} q (α) & \propto \exp (E_{q (x) q (β)} [\log (p (Y | φ) p (φ | ϕ))]) \\ \propto \exp (E_{q (x) q (β)} [\sum_{k = 1}^{K} \log p (y_{k} | x, β)]) \\ \propto G (α | \tilde{a}, \tilde{b}) = Π_{i = 1}^{N} G (α_{i} | \tilde{a_{i}}, \tilde{b_{i}}) \end{matrix}

(25)

where

\sum = {(diag (E [α_{i}]) + E [β] \sum_{k = 1}^{K} H_{k}^{T} H_{k})}^{- 1}

(26)

m = E [β] \sum \sum_{k = 1}^{K} H_{k}^{T} y_{k}

(27)

{\tilde{a}}_{i} = a + \frac{1}{2}

(28)

{\tilde{b}}_{i} = b + \frac{E [x_{i}^{2}]}{2}

(29)

\tilde{ϱ} = ϱ + \frac{M}{2}

(30)

\begin{matrix} \tilde{δ} = δ + \frac{1}{2} \sum_{k = 1}^{K} y_{k}^{T} y_{k} - E [x]^{T} \sum_{k = 1}^{K} H_{k}^{T} y_{k} \\ + \frac{1}{2} tr (\sum_{k = 1}^{K} H_{k}^{T} H_{k} \cdot (\sum + m^{T} m)) \end{matrix}

(31)

The required moments can be easily evaluated using the following results

\begin{matrix} E [x] = m \\ E [x_{i}^{2}] = \sum_{ii} + m_{i}^{2} \\ E [α_{i}] = \frac{{\tilde{a}}_{i}}{\tilde{b_{i}}} \\ E [β] = \frac{\tilde{ϱ}}{\tilde{δ}} \end{matrix}

(32)

From the above, it is noted that the aforementioned formulas can be used to compute the parameters of model in a centralized manner when all the measurements can be gathered in a FC. However, in the distributed scenario, there is no FC in the network and the formulas derived above cannot be implemented directly. In order to develop the distributed algorithm for VSBL, the formulas so far discussed will be reformulated in the following section such that the VSBL can be used for distributed sparse learning in a WSN.

Distributed variational SBL algorithm

Since the measurements are divided into K different nodes, the following global quantities can be defined by inspecting equations (26)–(31)

\begin{matrix} A = \sum_{k = 1}^{K} A_{k} \\ B = \sum_{k = 1}^{K} B_{k} \\ C = \sum_{k = 1}^{K} C_{k} \end{matrix}

(33)

where $A_{k}$ , $B_{k}$ , and $C_{k}$ are defined as local quantities and are defined as follows

\begin{matrix} A_{k} = H_{k}^{T} H_{k} \\ B_{k} = H_{k}^{T} y_{k} \\ C_{k} = y_{k}^{T} y_{k} \end{matrix}

(34)

Hence, equations (26)–(31) can be reformulated as follows

\sum = (diag (E [α_{i}]) + E [β] A)^{- 1}

(35)

m = E [β] \sum B

(36)

{\tilde{a}}_{i} = a + \frac{1}{2}

(37)

{\tilde{b}}_{i} = b + \frac{E [x_{i}^{2}]}{2}

(38)

\tilde{ϱ} = ϱ + \frac{M}{2}

(39)

\tilde{δ} = δ + \frac{1}{2} C - E [x]^{T} B + \frac{1}{2} tr (A \cdot (\sum + m^{T} m))

(40)

It should be noted that all the required parameters can be computed based on the variational approximation method and using the global quantities. In the sense of distributed calculation, each sensor communicates with its neighbors and operates accordingly. In the distributed variational sparse Bayesian learning (DVSBL) algorithm, the global quantities A , B , and C cannot be calculated locally. However, one can compute them by averaging the local quantities from all nodes in equation (34). This is because the global quantities in equation (34) can be redetermined as follows

\begin{matrix} A = \frac{1}{K} \sum_{k = 1}^{K} H_{k}^{T} H_{k} \\ B = \frac{1}{K} \sum_{k = 1}^{K} H_{k}^{T} y_{k} \\ C = \frac{1}{K} \sum_{k = 1}^{K} y_{k}^{T} y_{k} \end{matrix}

(41)

It is easy to see that above redefinition has no impact on the parameter approximations considered in equations (26)–(31). After inspecting the average formulas mentioned in equation (41), the idea of an average-consensus filter suggested in Kingston and Beard³⁶ can be employed to approximate the global information quantities. In particular, the local information quantities of each sensor are interchanged with their neighbors, then each sensor’s global information quantities changes depending on the local information quantities input from others using consensus filter. Hence, the DVSBL algorithm can be developed by employing such average-consensus filter.

According to Kingston and Beard,³⁶ a consensus filter can be formulated as follows in a continuous compact form

\overset{\cdot}{ξ} = (I - ϵ L) ξ

(42)

where L is the Laplacian matrix of graph and is defined as follows

ℓ_{ij} = {\begin{matrix} \sum_{k = 1, k \neq i}^{K} a_{i, k}, & j = 1 \\ - a_{i, j}, & j \neq i \end{matrix}

(43)

The discrete-time form of consensus filter suggested in Kingston and Beard³⁶ is as follows

ξ_{k} (τ + 1) = ξ_{k} (τ) + \sum_{k = 1}^{K} β_{kl} (τ) (ξ_{l} (τ) - ξ_{k} (τ))

(44)

where $τ$ denotes the iteration step of discrete-time consensus filter and $β_{kl} (τ)$ is the linear weight on $ξ_{l}$ at node k. Thus, the filtering algorithm can be carried out in a distributed manner if the averages given by equation (41) are obtained at every node. Here, $A_{k}$ , $B_{k}$ , and $C_{k}$ are treated as input states of consensus filter mentioned in equation (44), the outputs ${\hat{A}}_{k}$ , ${\hat{B}}_{k}$ , and ${\hat{C}}_{k}$ can asymptotically track the values of A , B , and C, respectively. Then, the hyperparameters at each node are approximated using its estimated global quantities. Thus

\sum_{k}^{t} = {(diag (E^{t} [α_{i}]) + E^{t} [β] K {\hat{A}}_{k})}^{- 1}

(45)

m_{k}^{t} = E^{t} [β] \sum_{k}^{t} K {\hat{B}}_{k}

(46)

{\tilde{a}}_{i}^{t} = a + \frac{1}{2}

(47)

{\tilde{b}}_{i}^{t} = b + \frac{E [x_{i}^{2}]}{2}

(48)

{\tilde{ϱ}}^{t} = ϱ + \frac{M}{2}

(49)

{\tilde{δ}}^{t} = δ + \frac{1}{2} K {\hat{C}}_{k} - E {[x]}^{T} K {\hat{B}}_{k} + \frac{1}{2} tr (K {\hat{A}}_{k} \cdot (Σ_{k}^{t} + m_{k}^{t T} m_{k}^{t}))

(50)

It can be noted from the above equations that each node should communicate with its neighbors several times before implementing variational approximation. However, the exchange of messages among the nodes iteratively is inevitable to consume time and energy and it is hard to know the number of iterations that are necessary to achieve consensus in different application scenarios, which are the main limitations of the proposed distributed VSBL. Moreover, another concerned problem is the design of weight matrix $Ξ = [β_{kl} (τ)]_{K \times K}$ that leads to a fast convergence rate of average consensus. Usually, the weight matrix $Ξ$ must be subject to the constraints of algebraic connectivity and graph topology

{\begin{matrix} \sum_{k = 1}^{K} β_{kl} (τ) = 1 \\ \sum_{l = 1}^{K} β_{kl} (τ) = 1 \\ β_{kl} (τ) > 0 \end{matrix}

(51)

Moreover, it has been shown that the second smallest eigenvalue of $Ξ$ determines the convergence speed of the algorithm in the case of fixed network topology.³⁷ Similar results have been obtained for time-varying network topology³⁸ and many algorithms have been proposed to accelerate the convergence in Aysal et al.³⁹ and Sardellitti et al.⁴⁰ In this article, metropolis weight is used in the simulations⁴¹

β_{kl} (τ) = {\begin{matrix} \frac{1}{1 + \max {d_{k} (τ), d_{l} (τ)}}, if {k, l} \in E (τ) \\ 1 - \sum_{l \in N_{k} (τ)} β_{kl} (τ), if k = l \\ 0, otherwise \end{matrix}

(52)

The performance of the proposed algorithm is validated using simulations, and results are presented in the next section. Moreover, the intact algorithm is given in Algorithm 1 (Figure 3).

Algorithm 1. Distributed variational Bayesian sparse learning (DVSBL) algorithm
1: Initialization: Input measurement vectors ${y_{k}}$ , measurement matrices ${H_{k}}$ , and weight matrix $Ξ$ ; initialize $\sum_{k}$ by identity matrix, $m_{k}$ by $0$ , and $a, b, ϱ, δ$ with $10^{- 6}$ .
2: for $t = 1, \dots, L$ do
3: Compute $A_{k} = H_{k}^{T} H_{k}$ , $B_{k} = H_{k}^{T} y_{k}$ , $C_{k} = y_{k}^{T} y_{k}$ and send ${A_{k}, B_{k}, C_{k}}$ to node $l \in N_{k}$ .
4: Receive ${A_{l}, B_{l}, C_{l}}$ from node $l \in N_{k}$ and fuse the local information quantities using the consensus filter (equation (44));
5: Compute equations (45)–(50) at each node;
6: If stop criterion is met, return $x_{k} (k = 1, \dots, K)$ ; otherwise go to step 5;
7: end for

Figure 3.

Algorithm architecture.

Simulations

First, a sensor network with six nodes is used to verify the performance of the proposed algorithm for distributed WSNs (Figure 4). Without loss of generality, the considered six-node network is represented by an undirected graph $G = (V, E, A)$ with a set of nodes $A = (1, 2, 3, 4, 5, 6)$ , a set of edges $E = {(1, 1), (1, 2), (1, 3), (2, 3), (2, 4), (2, 5), (3, 3), (3, 5), (3, 6), (4, 4), (4, 5), (5, 5), (5, 6), (6, 6)}$ , and an adjacency matrix

A = [\begin{matrix} 1 & 1 & 1 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & 1 & 0 \\ 1 & 1 & 1 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 & 1 & 0 \\ 0 & 1 & 1 & 1 & 1 & 1 \\ 0 & 0 & 1 & 0 & 1 & 1 \end{matrix}]

(53)

Figure 4.

Random topology.

In the considered example, the signal $x \in R^{256}$ is assumed to be sparse itself. There are altogether 10 non-zero elements $x {i} \neq 0$ in the sparse signal, where i is the index of support and $x {i}$ denotes the value of support. Here, the index and value of support are unknown and sampled over $i ~ U_{int} [1, 256]$ and $x {i} ~ N (0, 5^{2})$ , respectively. The measurement matrix $H_{k} \in R^{12 \times 256}$ of sensor node k is constructed by the entries sampled from $N (0, (1 / 72))$ . Then, the local measurement $y_{k} \in R^{12}$ is obtained using equation (1) and the global measurement matrix $H = col {H_{1}, \dots, H_{6}} \in R^{72 \times 256}$ satisfies the RIP with overwhelming probability. The measurement noise $e_{k} ~ N (0, 10^{- 4} \times I_{12})$ . The normalized mean square error (MSE) and averaged relative error are employed to evaluate the performance, which are defined as follows

Normalized MSE = \frac{| | x - \hat{x} | |_{2}}{| | x | |_{2}}

(54)

Average relative error = \frac{\sum_{k = 1}^{K} | | {\hat{x}}_{k} - x | |_{2}^{2}}{K \cdot | | x | |_{2}^{2}}

(55)

The convergence rate of the proposed algorithm is shown in Figures 5 and 6. It can be seen from the figures that both the local information quantity $C_{k}$ and the normalized MSE reach the consensus as the iteration progresses. It can also be observed that the normalized MSE has the same convergence tendency with the local information quantity. The results confirm that the consensus iterations enhance the observability by information, which is in agreement with the analysis.

Figure 5.

Convergence for local information quantity $C_{k}$ .

Figure 6.

Normalized MSE versus iteration.

The estimated x from sensor nodes using DVSBL algorithm is presented in Figure 7. It can be observed that the estimated values of actual sparse signals at all nodes are satisfactory.

Figure 7.

Estimation of x .

In order to prove the scalability of the proposed distributed algorithm, we consider two networks of different sizes, one of which is an L-connected Harary graph formed by 24 nodes, and the other is an L-connected Harary graph formed by 72 nodes. The L-connection denotes the number of neighbors for each node. In the considered example, the L is set as 3. The error performance is shown in Figures 8 and 9. It can be noted that irrespective of the size, both the networks have the comparable reconstruction performance compared to the centralized VSBL.

Figure 8.

Comparison of Normalized MSE (24 nodes).

Figure 9.

Comparison of Normalized MSE (72 nodes).

The average relative error of 72 nodes is presented in Figure 10. It can be seen that the relative error after two iterations is negligible. This demonstrates that the proposed algorithm is salable.

Figure 10.

ARE versus iteration.

Finally, the real temperature signals obtained from Intel Berkeley Research laboratory are considered to test the effectiveness of the proposed algorithm. The considered temperature signals are represented using discrete cosine transform (DCT) as shown in Figure 11. In this context, a three-connected Harary graph with 24 nodes is employed. The effectiveness of our distributed algorithm is demonstrated in Figure 12 where both the original signal and the reconstructed signal of one node are provided. It can be observed from Figure 12 that both the proposed distributed algorithm and the centralized VSBL are successful in reconstructing the temperature signals.

Figure 11.

The coefficients of DCT.

Figure 12.

Reconstructed results of temperature signal.

In a word, all the results presented so far have demonstrated the effectiveness of the distributed sparse signal reconstruction algorithm presented in this article.

Conclusion

In this article, a new distributed variational SBL algorithm for sparse signal reconstruction in a WSNs is presented. By combining VSBL and average-consensus algorithm, the DVSBL is consistent with centralized VSBL, where all data are available at FC. Experimental results demonstrate the superior recovery performance and convergence properties of the proposed distributed algorithm.

Footnotes

Academic Editor: Wei Yu

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: The work is supported by “Qing Lan Project” and “the National Natural Science Foundation of China under Grant 61572172”; “the Fundamental Research Funds for the Central Universities, No. 2016B10714”; “The Basic Research Plan in Shenzhen City under Grant (No. JCYJ20130401100512995. JCYJ20140418100633654)”; “the National Natural Science Foundation of China (No. 61001125)”; “PAPD”; and “CICAEET.”

References

Han

Qian

Jiang

. A grid-based joint routing and charging algorithm for industrial wireless rechargeable sensor networks. Comput Netw 2016; 101: 19–28.

Han

Dong

Guo

. Cross-layer optimized routing in wireless sensor networks with duty cycle and energy harvesting. Wirel Commun Mob Com 2015; 15(16): 1957–1981.

Zhao

Feng

Peng

A green distributed signal reconstruction algorithm in wireless sensor networks. IEEE Access 2016; PP(99): 1.

Guo

Chu

Sun

Accurate localization of multiple sources using semidefinite programming based on incomplete range matrix. IEEE Sens J 2016; 16: 5319–5324.

Xie

Wang

YX.

Construction of tree network with limited delivery latency in homogeneous wireless sensor networks. Wireless Pers Commun 2014; 78(1): 231–246.

Xia

Wang

Sun

. Steganalysis of least significant bit matching using multi-order differences. Secur Comm Network 2014; 78: 1283–1291.

Han

Jiang

Zhang

CY.

A survey on mobile anchors assisted localization in wireless sensor networks. IEEE Commun Surv Tutor 2016; 18(3): 2220–2243.

Han

Wan

Shu

. Two novel DOA estimation approaches for real-time assistant calibration systems in future vehicle industrial. IEEE Syst J 2015; PP: 1–12.

Shen

Tan

Wang

. A novel routing protocol providing good transmission reliability in underwater sensor networks. J Internet Technol 2015; 16(1): 171–178.

10.

Guo

Wang

. A variable threshold-value authentication architecture for wireless mesh networks. J Internet Technol 2014; 15(6): 929–936.

11.

Donoho

DL.

Compressed sensing. IEEE T Inform Theory 2006; 52(4): 1289–1306.

12.

Baraniuk

Candes

Nowak

. Compressive sampling [from the guest editors]. IEEE Signal Proc Mag 2008; 25(2): 12–13.

13.

Tipping

ME.

Sparse Bayesian learning and the relevance vector machine. J Mach Learn Res 2001; 1: 211–244.

14.

Xue

Carin

Bayesian compressive sensing. IEEE T Signal Proces 2008; 56(6): 2346–2356.

15.

Zai

Xie

Zhang

Off-grid direction of arrival estimation using sparse Bayesian inference. IEEE T Signal Proces 2013; 61(1): 38–43.

16.

Themelis

Rontogiannis

Koutroumbas

KD.

A variational Bayes framework for sparse adaptive estimation. IEEE T Signal Proces 2014; 62(18): 4723–4736.

17.

Bishop

Tipping

ME.

Variational relevance vector machines. In: Proceedings of the 16th conference on uncertainty in artificial intelligence, San Francisco, CA, 30 June–3 July 2000, pp.46–53. San Francisco, CA: Morgan Kaufmann Publishers, Inc.

18.

Mateos

Bazerque

Giannakis

GB.

Distributed sparse linear regression. IEEE T Signal Proces 2010; 58(10): 5262–5276.

19.

Mota

JFC

Xavier

JMF

Aguiar

PMQ

. Distributed basis pursuit. IEEE T Signal Proces 2012; 60(4): 1942–1956.

20.

Chen

Wassell

IJ.

A decentralized Bayesian algorithm for distributed compressive sensing in networked sensing systems. IEEE T Wirel Commun 2015; 15(2): 1282–1292.

21.

Liu

Wang

Distributed sparse signal estimation in sensor networks using H∞-consensus filtering. IEEE/CAA J Autom Sin 2014; 1(2): 149–154.

22.

Olfati-Saber

Shamma

. Consensus filters for sensor networks and distributed sensor fusion. In: Proceedings of the 44th IEEE conference on decision and control, Seville, 12–15December2005, pp.6698–6703. New York: IEEE.

23.

Olfati-Saber

Murray

RM.

Consensus problems in networks of agents with switching topology and time-delays. IEEE T Automat Contr 2004; 49(9): 1520–1533.

24.

Tsitsiklis

Bertsekas

Athans

Distributed asynchronous deterministic and stochastic gradient optimization algorithms. IEEE T Automat Contr 1986; 31(9): 803–812.

25.

Amelina

Fradkov

Jiang

. Approximate consensus in stochastic networks with application to load balancing. IEEE T Inform Theory 2015; 61(4): 1739–1752.

26.

Wang

Tan

Peng

. Coordinated control of distributed energy-storage systems for voltage regulation in distribution networks. IEEE T Power Deliver 2015; 31(3): 1132–1141.

27.

Safarinejadian

Estahbanati

ME.

Consensus filter-based distributed variational Bayesian algorithm for flow and speed density prediction with distributed traffic sensors. IEEE Syst J 2015; PP(99): 1–10.

28.

Jia

YM.

Consensus-based distributed multiple model UKF for jump Markov nonlinear systems. IEEE T Automat Contr 2012; 7(1): 230–236.

29.

Safarinejadian

Estakhri

A novel distributed variational approximation method for density estimation in sensor networks. Measurement 2016; 89: 78–86.

30.

Wipf

Rao

BD.

Sparse Bayesian learning for basis selection. IEEE T Signal Proces 2004; 52(8): 2153–2164.

31.

Davies

Gribonval

Restricted isometry constants where ℓ_p sparse recovery can fail for 0 ≪p≤ 1. IEEE T Inform Theory 2009; 55(5): 2203–2214.

32.

Chen

DR.

The improved bounds of restricted isometry constant for recovery via ℓ_p-minimization. IEEE T Inform Theory 2013; 59(9): 6142–6147.

33.

Wipf

Nagarajan

Iterative reweighted ℓ₁ and ℓ₂ methods for finding sparse solutions. IEEE J Sel Top Signa 2010; 4(2): 317–329.

34.

Wipf

Rao

Nagarajan

Latent variable Bayesian models for promoting sparsity. IEEE T Inform Theory 2011; 57(9): 6236–6255.

35.

Zhu

Leung

State estimation in unknown non-Gaussian measurement noise using variational Bayesian technique. IEEE T Aero Elec Sys 2013; 49(4): 2601–2614.

36.

Kingston

Beard

Discrete-time average-consensus under switching network topologies. In: Proceedings of the 2006 American control conference, Minneapolis, MN, 14–16 June 2006, 6 pp. New York: IEEE.

37.

Xiao

Boyd

Fast linear iterations for distributed averaging. Syst Control Lett 2004; 53(1): 65–78.

38.

Kar

Moura

JMF

. Sensor networks with random links: topology design for distributed consensus. IEEE T Signal Proces 2008; 56(7): 3315–3326.

39.

Aysal

Oreshkin

Coates

MJ.

Accelerated distributed average consensus via localized node state prediction. IEEE T Signal Proces 2009; 57(4): 1563–1576.

40.

Sardellitti

Giona

Barbarossa

Fast distributed average consensus algorithms based on advection-diffusion processes. IEEE T Signal Proces 2010; 58(2): 826–842.

41.

Xiao

Boyd

Lall

. A scheme for robust distributed sensor fusion based on average consensus. In: Proceedings of the 4th international symposium on information processing in sensor networks (IPSN 2005), Boise, ID, 15 April 2005, pp.63–70. New York: IEEE.