# Data Reduction with Quantization Constraints for Decentralized Estimation in Wireless Sensor Networks

Authors: Yang Weng
Journal: Mathematical Problems in Engineering
 (2014)

---

## Abstract

The unknown vector estimation problem with bandwidth constrained wireless sensor network is considered. In such networks, sensor nodes make distributed observations on the unknown vector and collaborate with a fusion center to generate a final estimate. Due to power and communication bandwidth limitations, each sensor node must compress its data and transmit to the fusion center. In this paper, both centralized and decentralized estimation frameworks are developed. The closed-form solution for the centralized estimation framework is proposed. The computational complexity of decentralized estimation problem is proven to be NP-hard and a Gauss-Seidel algorithm to search for an optimal solution is also proposed. Simulation results show the good performance of the proposed algorithms.


---

## Body

## 1. Introduction

The developments in microelectromechanical systems technology, wireless communications, and digital electronics have enabled the deployment of low-cost wireless sensor networks (WSNs) in large scale using small size sensor nodes [1]. In such networks, the distributed sensors collaborate with a fusion center to jointly estimate the unknown parameter. If fusion center receives all measurement data from all sensors directly and processes them in real time, the corresponding processing of sensor data is known as the centralized estimation, which has several serious drawbacks, including poor survivability and reliability, heavy communications, and computational burdens. Since all sensors have limited battery power, their computation and communication capability are severely limited; the decentralized estimation methods are widely discussed in recent years [2–6]. In the decentralized estimation framework, every sensor is also a subprocessor. It first preprocesses the measurements in terms of a criterion and then transmits its local compression data to the fusion center. Upon receiving the sensor messages, the fusion center combines them according to a fusion rule to generate the final result. In such networks, less information is transmitted leading to a significant power-saving advantage which is very important in the case of WSNs.To minimize the communication cost, only limited amount of information is allowed to be transmitted through networks; dimensionality reduction estimation methods have attracted considerable attentions [7–9]. The basic idea of the dimensionality reduction estimation strategy is to prefilter the high-dimensional observation vector by a linear transformation (matrix) to project the observation onto the subspace spanned by basis vectors and filter the result with a low-rank estimation. Indeed, dimensionality reduction estimation and filtering are important for a wide range of signal processing applications where data reduction, robustness against noise, and high computational efficiency are desired.Quantization has been viewed as a fundamental element in saving bandwidth by reducing the amount of data to represent a signal and well studied in digital signal processing and control where a signal with continuous values is quantized due to a finite word-length of microprocessor [10]. In WSNs, quantization is also necessary to reduce the energy consumption as communications consume the most energy as the amount of energy consumed is related to the amount of data transmitted. An interesting distributed estimation approach based on the sign of innovation (SOI) has been developed for dynamic stochastic systems in [11] where only transmission of innovation of a single bit is required. A general multiple-level quantized innovation Kalman filter for estimation of linear dynamic stochastic systems has been presented in [12]. The solution to the optimal filter is given in terms of a simple Riccati recursion as in the standard Kalman filter. A random field estimation problem with quantized measurements in sensor networks has been considered in [13]. In the early work [14], the trade-off between dimension reduction and quantization in minimum mean squared error estimation problem is investigated.In this paper, different from the existing work, the dimensionality reduction and quantization for local data compression are considered in an integrated way. Data reduction with quantization constraints estimation for an unknown vector is formulated as an optimization problem. Both centralized and decentralized estimation frameworks are developed. The closed-form solution for the centralized estimation framework is proposed. By using computational complexity theory, the intractability of decentralized estimation problem is established. A Gauss-Seidel type iteration algorithm to search for an optimal solution is also proposed for the decentralized estimation problem.The rest of this paper is organized as follows. With given communication bandwidth, the bits allocation problem has been formulated as an optimization problem in Section2. The closed-form solution for the centralized estimation framework is proposed in Section 3. The computational complexity of decentralized estimation problem is proved to be NP-hard and a Gauss-Seidel algorithm to search for an optimal solution is also proposed in Section 4. Simulation results are reported in Section 5 to show the performance of our methods. Concluding remarks are given in Section 6.


## 2. Problem Formulation

Consider a sensor network deployed withL sensor nodes. Each sensor, say the ith sensor, can take observation yi∈ℛni which is correlated with an unknown random parameter x∈ℛm. The observations will be transmitted to a fusion center to estimate the unknown parameter x under some certain criterion. In this paper, we consider the minimum mean squared error (MMSE) criterion [15, 16].Through a transform matrixKi∈ℛri×ni, ri≤ni, each sensor transforms the observation into a ri×1 vector Kiyi, whereafter the transformed vector will be quantized into several bits and transmited to the fusion center. In this paper, we assume that there is no information exchange among sensors. We also assume without loss of generality that the unknown parameter x and observations yi are zeromean. The auto- and cross-covariance matrices Rxx,Rxyi,Ryiyj, ∀i,j∈{1,…,L} are available at the FC. The role of FC is to combine the received quantization information
(1){Q(K1y1),Q(K2y2),…,Q(KLyL)},
according to
(2)x^=f(Q(K1y1),Q(K2y2),…,Q(KLyL)),
where f(·) is the fusion function and Q(·) is a given quantizer. Our goal is to design the linear transforms {K1,…,KL} and the fusion function f(·) such that the mean squared error (MSE) is as small as possible under the constraint that the total number of bits can be transmitted to FC. Throughout this work, we will focus only on the linear design of fusion function f(·) which can be represented in the form
(3)x^=f(Q(K1y1),Q(K2y2),…,Q(KLyL))=∑i=1LCiQ(Kiyi).The given quantizerQ(·) is considered as a minimum squared error distortion quantizer [17]. We assume that the quantizer input vector Z=(z1,…,zr)T is a random vector with uncorrelated components. Each component has zero mean and variance σi2. Under the Gaussian assumption, the quantizer output Q(Z) is treated as a noise source that introduces independent white noise v as
(4)Z=Q(Z)+v,
whose mean is zero and covariance is [17]
(5)Σvv=E(vvT)=diag{γ12,…,γr2}=diag{σ122-2B1,…,σr22-2Br},
where γi2=σi22-2Bi is the squared error distortion for the ith component and Bi is the bits used by the the ith component zi.Therefore, the mean squared error at the fusion center can be calculated as follows:(6)E∥x-x^∥2=E∥x-∑i=1L‍CiQ(Kiyi)∥2=E∥x-∑i=1L‍Ci(Kiyi-vi)∥2+∑i=1L‍E∥Civi∥2=E∥x-∑i=1L‍CiKiyi∥2+∑i=1L‍∑s=1m‍∑t=1ri‍cstiγit2=E∥x-∑i=1L‍CiKiyi∥2+∑i=1L‍∑s=1m‍∑t=1ri‍cstiσit22-2Bit,
where Ki is the local linear transform operator, Ci={csti}m×ri is the fusion operator at the fusion center and Bit is the quantization bits for the tth elements of vector Kiyi. The optimal estimation of random vector x under individual sensor bandwidth constraint can be formulated as follows:
(7)minimizeE(∥x-x^∥2)subjectto∑i=1L‍∑t=1ri‍Bit≤B,Ci∈ℛm×ri,Ki∈ℛri×ni.By appropriate pre- and postwhitening process if necessary, we assume without loss of generality that the auto- and cross-covariance matricesRxx,Rxyi,Ryiyj, ∀i,j∈{1,…,L} have full rank and the elements of observation vector taken by each sensor are uncorrelated [18].


## 3. Centralized Data Reduction with Quantization Constraints

In this section, we consider a simple centralized framework where the entire data is available at a single sensor node and the centralized case of optimization problem (7) can be simplified as follows:
(8)minimizeE∥x-x^∥2=E∥x-K(r)y∥2+∑i=1r‍σi22-2Bisubjectto∑i=1r‍Bi≤B,K(r)∈ℛm×n,
where K(r) is the approximation matrix and B is the total bits to be transmitted.The optimal estimation without observation compression in the MMSE sense is as follows:(9)x^=RxyRyy-1y=Ky,
with estimation error covariance matrix
(10)P=Rxx-RxyRyy-1Ryx,
where K is called optimal estimation matrix. We write formula (9) as a linear model by introducing an estimation error e as
(11)x=x^+e=RxyRyy-1y+e.We consider the problem that the optimal estimation matrixK is replaced by an approximating matrix K(r) with lower rank r<n. With a given compressed dimension r, we want to find an optimal K(r) such that the MMSE is as small as possible. The linear model (11) is modified as
(12)x=x^(r)+e(r)=K(r)y+e(r).
The estimation error covariance matrix can be calculated as follows:
(13)P(r)=E(e(r)e(r)T)=E((e+Ky-K(r)y)(e+Ky-K(r)y)T)=P+(K-K(r))Ryy(K-K(r))T.
Therefore, the approximation matrix K(r) introduces an extra variance term
(14)ε2=tr[(K-K(r))Ryy(K-K(r))T]=tr[(KRyy1/2-K(r)Ryy1/2)(KRyy1/2-K(r)Ryy1/2)T].
The matrix KRyy1/2=RxyRyy-1/2 has an SVD of the form
(15)KRyy1/2=UΣVT.
By minimizing ε2, it is not hard to show that the best approximation matrix is
(16)K(r)=UΣ(r)VTRyy1/2.
The extra variance is then
(17)ε2=∑i=r+1m‍λi2,
where λr+1,…,λm are the smallest m-r singular values of KRyy1/2.Therefore the optimization problem (18) is as follows:
(18)minimize∑i=r+1m‍λi2+∑i=1r‍σi22-2Bisubjectto∑i=1r‍Bi≤B,r.
If r is given, we can solve this optimization problem by a Laplacian multiplier [19].


## 4. Decentralized Data Reduction with Quantization Constraints

Let us now consider the estimation framework in a multisensor setup, under a total available rateB which has to be shared among all sensors. In the decentralized manner, the ith sensor transforms the observation yi∈ℛni into a ri×1 vector Kiyi through a transform matrix Ki∈ℛri×ni, ri≤ni, whereafter the transformed vector will be quantized into several bits and transmited to the fusion center. By the linear fusion rule at the fusion center, the mean squared error at the fusion center can be calculated as follows:
(19)E∥x-x^∥2=E∥x-∑i=1L‍CiQ(Kiyi)∥2=E∥x-∑i=1L‍CiKiyi∥2+∑i=1L‍∑s=1m‍∑t=1ri‍cstiσit22-2Bit,
where Ki is the local linear transform operator, Ci={csti}m×ri is the fusion operator at the fusion center and Bit is the quantization bits for the tth elements of vector Kiyi. Therefore, the decentralized estimation of random vector x under individual sensor bandwidth constraint can be formulated as follows:
(20)minimizeE∥x-x^∥2=E∥x-∑i=1L‍CiKiyi∥2nnnnnnnnnnnnnnnnnn+∑i=1L‍∑s=1m‍∑t=1ri‍cstiσit22-2Bitsubjectto∑i=1L‍∑t=1ri‍Bit≤B,Ci∈ℛm×ri,Ki∈ℛri×ni.Theorem 1.
The computational complexity of solving problem (20) is NP-hard even in the case with absence of channel distortions for quantization of each sensor.Proof.
We present the simplified formulations to analyze the computation complexity of problem (7). Let the L distributed sensor nodes make observations on a common random parameter vector x∈ℛm according to
(21)yi=Hix+vi,i=1,2,…,L,
where Hi∈ℛmi×m is the observation matrix and vi∈ℛmi is the additive noise which is zero mean and spatially uncorrelated. According to [18], we can assume that the sensor noises are uncorrelated with the input signal x. Without loss of generality, we can assume that the unknown parameter vector x has an autocovariance matrix Rxx=Im and the noise covariance matrix is Rvi=Imi.
The MSE at the FC can be calculated as follows:(22)E∥x-x^∥2=E∥x-∑i=1L‍CiQ(Kiyi)∥2=E∥x-∑i=1L‍CiKiyi∥2+∑i=1L‍∑s=1m‍∑t=1ri‍cstiσit22-2Bit.
In the absence of channel distortions, the MSE at the FC can be simplified as
(23)E(∥x-x^∥2)=E∥x-∑i=1L‍CiQ(Kiyi)∥2=E∥x-∑i=1L‍Ci(Kiyi-vi)∥2+∑i=1L‍E∥Civi∥2=E∥x-∑i=1L‍CiKiyi∥2+∑i=1L‍∑s=1m‍∑t=1ri‍cstiγit2=E∥x-∑i=1L‍CiKiyi∥2=E∥x-∑i=1L‍CiKi(Hix+vi)∥2=E(x-∑i=1L‍CiKi(Hix+vi))T×(x-∑i=1L‍CiKi(Hix+vi))=Tr((x-∑i=1L‍CiKi(Hix+vi))TE(x-∑i=1L‍CiKi(Hix+vi))×(x-∑i=1L‍CiKi(Hix+vi))T)=Tr[(Im-∑i=1L‍CiKiHi)E(xxT)nnnnnn×(Im-∑i=1L‍CiKiHi)Tnnnnnn+∑i=1L‍(CiKiE(viviT)KiTCiT)]=Tr[(Im-∑i=1L‍CiKiHi)(Im-∑i=1L‍CiKiHi)Tnnnnn+∑i=1L‍(CiKiKiTCiT)(Im-∑i=1L‍CiKiHi)T]=∥Im-∑i=1L‍CiKiHi∥F2+∑i=1L‍Tr(CiKiKiTCiT),
where the last step follows from the independence assumptions and the fact that the autocovariance of x and vi is normalized to Im and Imi, respectively; the notation Tr(·) denotes the trace of a matrix, and the subscript F denotes the usual Frobenius norm of a matrix. Therefore, the optimal linear DES design problem under individual sensor power constraint can be formulated as follows:
(24)minimizeE∥x-x^∥2=∥I-∑i=1L‍CiKiHi∥F2nnnnnnnnnnnnnnnnnn+∑i=1L‍Tr(CiKiKiTCiT)subjectto∑i=1L‍Tr(KiKiT)≤k,Ci∈ℛm×ri,cccccccccccccccccccccccccccccccccKi∈ℛri×ni,
where k is the total rate constraint since the transmission power for sensor i to send Kiyi to fusion center is linearly proportional to Tr(KiKiT).
From (23), the MSE at the FC can be written as
(25)E(∥x-x^∥2)=Tr[(Im-∑i=1L‍CiKiHi)(Im-∑i=1L‍CiKiHi)Tnnnnnn+∑i=1L‍(CiTKiTKiCi)(Im-∑i=1L‍CiKiHi)T].
Following the fact of matrix derivatives of traces [20],
(26)∂∂XTr(XA)=AT,∂∂XTr(XTBX)=BX+BTX,
we can eliminate variables {Ci} by minimizing E∥x-x^∥2 with respect to {Ci}. As a result, the optimization problem (24) is equivalent to
(27)minimizeTr(I+∑i=1L‍HiTKiT(KiTKi)-1KiHi)-1subjectto∑i=1L‍Tr(KiKiT)≤k,Ki∈ℛri×ni.
When Ki is a vector, problem (27) is equivalent to “minimum sum of squares” problem which is NP-complete [21].
Therefore, the computational complexity of solving problem (20) is NP-hard even in the case with absence of channel distortions for quantization of each sensor.Remark 2.
The NP-completeness of optimization problem (20) leads to the intractability of finding the globally optimal solution in polynomial time. Instead of finding a globally optimal solution, a locally optimal solution may be sufficient in many applications. An effective heuristic algorithm should be proposed to search for the optimal solution of optimization problem (20).An algorithm that could be used to search for the optimal solution is the Gauss-Seidel type iteration algorithm which may converge to a locally optimal solution and widely used in estimation, detection, and classification with sensor networks [22–27]. In this paper, a Gauss-Seidel type iteration algorithm is proposed to search the optimal solution for that problem sensor by sensor.Suppose that all sensor nodes except nodej have fixed transformation matrix Kl, l≠j, l=1,…,L. The goal is to determine the optimal Kj. From the perspective of a selected node j, suppose that all other nodes have decided on (arbitrary) suitable approximations of their observations, and the question becomes to optimally choose the approximation to be provided by terminal j, where we without loss of generality set j=1. Observations taken by sensor node 1 are denoted by y1. The remaining observations which may be thought of as being merged into one node are denoted by y2. In line with this, we can partition the covariance matrix of the entire vector into four parts, according to
(28)Ry=(Ry1Ry1y2Ry2y1Ry2).Denotingξ=x-C1K1y1, η=K2y2, the distortion by dimension reduction is
(29)E∥x-x^∥2=E∥x-(C1K1y1+C2K2y2)∥2=E∥ξ-C2η∥2.
The optimal estimation matrix is
(30)C2=RξηRη-1=E[(x-C1K1y1)(K2y2)T](E(K2y2)(K2y2)T)-1=(Rxy2K2T-C1K1Ry1y2K2T)(K2Ry2K2T)-1K2y2.
Take (30) into (29) as
(31)E∥x-x^∥2=∥(K2Ry2K2T)-1x-C1K1y1-(Rxy2K2T-C1K1Ry1y2K2T)nnnnn×(K2Ry2K2T)-1K2y2∥2=∥ζ-C1K1ν∥2.
Denote
(32)ζ=x-Rxy2K2T(K2Ry2K2T)-1K2y2,ν=y1-Ry1y2K2T(K2Ry2K2T)-1K2y2.
Equation (31) is simplified as
(33)E∥x-x^∥2=∥ζ-C1K1ν∥2.
Obviously, the optimal solution of sensor by sensor optimization problem can be solved because the question has been reduced to that in the centralized case. Based on the previous analysis, it is easy to construct a Gauss-Seidel type iteration algorithm to search for an optimal solution of optimization problem (20). We omit it here.


## 5. Simulations

In this section, we implement several simulations to show the performance of our proposed method. Both centralized and decentralized estimation frameworks are considered.


### 5.1. Centralized Estimation Framework

In centralized estimation framework, entire data is available at a single sensor and the observation data compression is needed in order to reduce communication requirement. Consider a linear model(34)y=Hx+ε,H∈ℛn×m,
where H∈ℛn×m and ε is a white noise with covariance matrix Σε=σ2I. In addition, x and ε are uncorrelated. In simulation, we set n=50, m=10, σ2=1, and Σx=RRT, where R is drawn from a standard normal distribution. The estimation performance for centralized estimation framework with different bandwidth constraints is shown in Figure 1. The bottom solid line is the Cramer-Rao lower bound (CRLB). The dimension reduction and quantization lead to the gap between the centralized estimation curve and CRLB.Figure 1
Estimation performance for centralized estimation with different bandwidth constraints.We plot the estimation performance for different reduced dimensions in Figure2. Three cases of bandwidth constraint are considered (B=20,25,30). The bottom solid line is the CRLB. The blue line with circle is the MSE for the data only with dimension reduction. When quantization is implemented after dimension reduction, the optimal strategy allocates the bandwidth to the most important dimension. Do not waste the bandwidth on the less important dimension which would leads to bad performance.Figure 2
Comparison of estimation performance with different reduced dimensions.The comparison of estimation performance for different signal-to-noise ratios (SNR) is shown in Figure4. The SNR is defined as
(35)SNR=Tr(HΣyHT)nσ2.


### 5.2. Decentralized Estimation Framework

In decentralized estimation framework, the distributed sensors collaborate with a fusion center to jointly estimate the parameters. Since all sensors have limited battery power, their computation and communication capability are severely limited. As a result, local data compression is needed in order to reduce communication requirement.Let the3 distributed sensor nodes make observations on a common random parameter vector x∈ℛm according to
(36)yi=Hix+vi,i=1,2,3,
where Hi∈ℛmi×m is the observation matrix and vi∈ℛmi is the additive noise which is zero mean and spatially uncorrelated. In addition, x and vi are uncorrelated. In simulation, we set mi=15, m=10, σ2=1, and Σx=RRT, where R is drawn from a standard normal distribution.The comparison of centralized and decentralized estimation performance is shown in Figure3. The bottom solid line is the CRLB. The estimation for centralized and decentralized framework are plotted in red dash line with circle and blue dot line with square for different bandwidth constraints, respectively. The decentralized estimation performance is slightly worse than the centralized estimation since the Gauss-Seidel method cannot guarantee the optimal solution [22].Figure 3
Comparison of estimation performance with different SNR.Figure 4
Comparison of estimation performance for centralized and decentralized framework.


## 5.1. Centralized Estimation Framework

In centralized estimation framework, entire data is available at a single sensor and the observation data compression is needed in order to reduce communication requirement. Consider a linear model(34)y=Hx+ε,H∈ℛn×m,
where H∈ℛn×m and ε is a white noise with covariance matrix Σε=σ2I. In addition, x and ε are uncorrelated. In simulation, we set n=50, m=10, σ2=1, and Σx=RRT, where R is drawn from a standard normal distribution. The estimation performance for centralized estimation framework with different bandwidth constraints is shown in Figure 1. The bottom solid line is the Cramer-Rao lower bound (CRLB). The dimension reduction and quantization lead to the gap between the centralized estimation curve and CRLB.Figure 1
Estimation performance for centralized estimation with different bandwidth constraints.We plot the estimation performance for different reduced dimensions in Figure2. Three cases of bandwidth constraint are considered (B=20,25,30). The bottom solid line is the CRLB. The blue line with circle is the MSE for the data only with dimension reduction. When quantization is implemented after dimension reduction, the optimal strategy allocates the bandwidth to the most important dimension. Do not waste the bandwidth on the less important dimension which would leads to bad performance.Figure 2
Comparison of estimation performance with different reduced dimensions.The comparison of estimation performance for different signal-to-noise ratios (SNR) is shown in Figure4. The SNR is defined as
(35)SNR=Tr(HΣyHT)nσ2.


## 5.2. Decentralized Estimation Framework

In decentralized estimation framework, the distributed sensors collaborate with a fusion center to jointly estimate the parameters. Since all sensors have limited battery power, their computation and communication capability are severely limited. As a result, local data compression is needed in order to reduce communication requirement.Let the3 distributed sensor nodes make observations on a common random parameter vector x∈ℛm according to
(36)yi=Hix+vi,i=1,2,3,
where Hi∈ℛmi×m is the observation matrix and vi∈ℛmi is the additive noise which is zero mean and spatially uncorrelated. In addition, x and vi are uncorrelated. In simulation, we set mi=15, m=10, σ2=1, and Σx=RRT, where R is drawn from a standard normal distribution.The comparison of centralized and decentralized estimation performance is shown in Figure3. The bottom solid line is the CRLB. The estimation for centralized and decentralized framework are plotted in red dash line with circle and blue dot line with square for different bandwidth constraints, respectively. The decentralized estimation performance is slightly worse than the centralized estimation since the Gauss-Seidel method cannot guarantee the optimal solution [22].Figure 3
Comparison of estimation performance with different SNR.Figure 4
Comparison of estimation performance for centralized and decentralized framework.


## 6. Conclusion

In this paper, we have considered a bandwidth constrained sensor network in which a set of distributed sensors and a fusion center collaborate to estimate an unknown vector. With given communication bandwidth, the bits allocation problem has been formulated as an optimization problem. Both centralized and decentralized estimation frameworks have been developed. The closed-form solution for the centralized estimation framework has been proposed. The computational complexity of decentralized estimation problem has been proved to be NP-hard and a Gauss-Seidel type iteration algorithm to search for an optimal solution has been also proposed. Simulation results show the good performance of the proposed algorithms.



---

*Source: 932358-2014-01-09.xml*