# Distributed Binary Quantization of a Noisy Source in Wireless Sensor Networks

Authors: Sahar Movaghati; Masoud Ardakani
Journal: Journal of Sensors
 (2014)

---

## Abstract

In distributed (decentralized) estimation in wireless sensor networks, an unknown parameter must be estimated from some noisy measurements collected at different sensors. Due to limited communication resources, these measurements are typically quantized before being sent to a fusion center, where an estimation of the unknown parameter is calculated. In the most stringent condition, each measurement is
converted to a single bit. In this study, we propose a distributed quantization scheme which is based on single-bit quantized data from each sensor and achieves high estimation accuracy at the fusion centre.
We do this by designing some local binary quantizers which define a multithreshold quantization rule for each sensor. These local binary quantizers are initially designed so that together they mimic the
functionality of a multilevel quantizer. Later, their design is improved to include some error-correcting capability, which further improves the estimation accuracy from the sensors’ binary data. The distributed
quantization formed by such local binary quantizers along with the proper estimator proposed in this work achieves better performance, compared to the existing distributed binary quantization methods, specially
when fewer sensors with low measurement noise are available.


---

## Body

## 1. Background and Introduction

The distributed quantization and estimation problem involves estimating an unknown parameter from several noisy measurements [1]. This problem appears in many distributed sensing systems in a wide range of applications, such as medical imaging, environmental monitoring, and target tracking. In many of these cases a central processing unit or fusion center (FC) has to determine an unknown signal from some noisy observations received from distributed sensors. In wireless sensor networks (WSNs), sensors encapsulate their measurement readings inside the communication packets, according to the standard protocols, such as IEEE 802.15.4 and ZigBee, and transmit these packets to the FC. These protocols take care of the lower layers’ services (the term “layer” refers to the OSI model), such as routing and dealing with errors caused by channel noise. In this study, we assume that the WSN communication protocols provide error-free communication services for us. We focus our interest on the measurement data inside the packets and the advantage of optimum quantizer design at the application layer to improve estimation performance at the FC.Normally, due to system constraints, such as shortage of energy and bandwidth resources, distributed observations need to be compressed before being sent to the FC [2]. Quantizing the observations reduces the transmission load in the network; however, it implies some information loss, reducing the estimation accuracy. Therefore, quantizer and estimator design is an important problem in distributed estimation, which has attracted considerable attention in the recent literature [3–15].SupposeN noisy measurements of a random parameter X have the form Zn=X+wn, 1≤n≤N, where wn are independent zero mean measurement noises. If all the measurements are available in the estimator without any distortion, an unbiased estimation with error variance as low as (∑‍1/σn2)-1 can be achieved, where σn is the variance of the measurement noise for the nth observation [3]. Because of communication constraints in a WSN, the measurements are quantized before transmission using a local quantization rule; that is, yn=Qn(Zn). The goal is then to design these local quantization rules, as well as the procedure to be used for estimating X from the quantized data.Some existing distributed estimation algorithms are based on applying a uniform quantizer to quantize each analog measurement into a few bits [3–8, 16]. In all these algorithms, the number of quantization bits for each analog measurement is decided based on the signal-to-noise ratio (SNR). For example, in [3], the number of quantization bits for the nth measurement, 1≤n≤N, is log⁡2(1+V/σn). In some applications such as WSNs, this means the sensors with higher SNR, that is, smaller σn, will have to send more bits; hence, they consume more power for data transmission. Consequently, the better sensors become more exhausted and die more quickly, which in turn reduces the long-term performance of the estimation task.Another technique has been proposed by [9] which is based on adding some deterministic or random control input to the observation data, prior to the quantization. Therefore, the quantized value of the nth observation is y~n=Qn(Zn+vn), where vn is a deterministic or random signal. To find the optimal control input, a metric based on the Cramer-Rao lower bound (CRLB), or the Fisher information, is optimized [9, 17, 18].Under severely stringent bandwidth or power conditions it is preferred to quantize each measurement into only one bit. Distributed estimation based on local binary quantizations has been studied in [4, 10–14, 19]. In [4], the local binary quantization is performed by comparing the analog measurement value to a fixed threshold in the middle of the analog data range. The estimation performance of a set of local binary quantizers is studied in [13] for asymptotic condition; that is, N→∞.The local binary quantizers with a single fixed threshold are not very efficient, specially when the number of measurementsN is small and the measurement noise is low. To improve the performance, [10, 11] suggest adaptive thresholds, which are sequentially adjusted according to the previously generated bits. In their approach, the threshold used for quantizing the nth measurement value is adjusted based on the previous (n-1) bits. In [11], to find the optimum threshold for the nth measurement a maximum likelihood (ML) estimator must be derived every time based on the n previous generated bits and the n previous thresholds.The estimation based on local binary-quantized observations is further studied in [12], where they consider different thresholds τ={τk,k∈Z} on the analog range to assure that there will always be a threshold close to the true parameter X. Out of the N observations, Nk measurements are quantized according to threshold τk, where ∑k‍Nk=N. Through CRLB, they find the set of optimal threshold values τk* and their associated frequencies Nk*.In the above distributed estimation methods based on binary data, the generation of each bit is performed using a single threshold. A multithreshold quantization scheme was suggested by [14]. Based on the distributed estimation method in [14], each measurement is used to estimate one of the bits in the binary representation of the unknown parameter. According to [14], if N measurements are available, N/2 of them estimate the first bit of the unknown parameter, N/4 estimate the second bit, and so on. So, the bth bit in the binary representation of the unknown parameter is estimated N/2b times. Hence, the value for that bit is determined by taking the average among the N/2b binary values, and, consequently, X is estimated by combining the final value of the individually estimated bits.In this work we propose a new method for distributed binary quantization to improve the estimation performance at the FC. To do that, we design local quantizers to compress each local measurement to a single bit and suggest a centralized estimator to infer the unknown from those bits. Therefore, our goal in this work is to (i) first formulate the distributed quantization as a set ofN local binary quantizers (local-Qs), (ii) jointly design these local-Qs to find the optimal set of N local-Qs, which can maximize the estimation accuracy of X, and (iii) find a centralized algorithm for the FC that combines these binary-quantized data to form an accurate estimate of X.Our distributed quantization method benefits from multithreshold local quantizers to achieve high estimation accuracy. Compared to the binary quantization algorithms in [4, 11, 12, 14], our method achieves a better MSE performance at the FC, specially when limited number of sensors are available, with low measurement noise. This is while minimum computation and transmission load is imposed on the sensors.The rest of this paper is organized as follows. In Section2, the detailed setup of the problem and the required definitions and assumptions are provided. In Section 3, the design of a distributed quantizer based on different binary numeral systems is introduced. Section 4 proposes optimal local-Qs to improve the estimation performance. In Section 5, the appropriate decoder/estimator to be used in the FC is formulated. Finally, in Section 6, the simulation results are shown for performance evaluation.


## 2. Problem Setup

SupposeX is a random scalar distributed according to the pdf P(X). A number of noisy measurements of X are observed as
(1)Zn=X+wn1≤n≤N,
where wn for 1≤n≤N are i.i.d. additive noise. In this work, we assume that P(X) is a uniform distribution in the interval [-V,V], and the measurement noise is Gaussian with zero mean and variance σ2. It is straightforward to modify the proposed distributed estimation method to work with other signal and noise pdfs. An example for Gaussian X is discussed in Section 4.3.Considering the most stringent scenario, only single-bit data transmission is allowed for sending each measurement to the FC. Therefore, each measurementZn is quantized to a bit yn, according to a local binary quantization rule Qn(·).Note that data transmission over nonideal channels can involve some errors due to channel noise, which can be dealt with separately using error detection and error correction techniques implemented in the WSN communication protocols. In this study, we do not consider any noise or error added by the channel; that is, the communication channel is assumed to be error-free. Therefore, all errors discussed here are due to the measurement or quantization noise, not the channel noise. Thus, the goal is to design a set of local binary quantization rulesQn(·) to be used for quantizing the observations Zn and also to design an estimation algorithm that combines the quantized binary data yn to form an accurate estimate of X at the FC, that is, X^ (see Figure 1).Figure 1
The overall distributed estimation method.Assume that the parameter range[-V,V] is “partitioned” into L “divisions” δl; 1≤l≤L. Compressing the real-valued measurement Zn to a bit yn can be performed through introducing a local-Q Pn, which is a function mapping each division δl, 1≤l≤L to a binary value, that is, 0 or 1. Therefore, the quantization of each measurement can be described as
(2)yn=Pn(l)iffZn∈δl.
Each local-Q is an ordered sequence of L binary values, that is, a binary vector of length L. Wherever the binary value alters between two successive divisions the threshold between those divisions is regarded as an edge in the local-Q; see Figure 2. Therefore, a local-Q denoted by Pn is associated with a set of edges, that is, {en1,en2,…,enϵn}, where ϵn is the number of edges in Pn. These edges define a new partitioning of [-V,V] into ϵn+1 “cells”; see Figure 2. Similar to multiresolution quantization [20, 21], different quantizers have different cell sizes (resolution); however, in our method all local quantizers have binary output.Figure 2
A sample local-Q.It must be mentioned that, due to the additive Gaussian noise, the analog measurementsZn are in the range (-∞,∞). However, since the desired parameter which must be estimated in the FC is within the range [-V,V], the local-Qs are defined over this range. Therefore, if Zn is in (-∞,-V) or (V,∞) it will be mapped to V or -V, respectively.


## 3. Distributed Quantization

In this section we describe how a set of local-Qs are designed. For now, assume that we haveN=B noiseless observations of X. In other words, each observation equals X, which must be quantized into one bit, yb, 1≤b≤B. Since the combinations of B bits can specify maximum of L=2B values, one can generate yb; 1≤b≤B, so that together they identify the division of X among L distinct divisions within the range [-V,V]. In order to achieve that, B local-Qs must be appropriately designed.Consider the analog range[-V,V] to be partitioned into L equal-length divisions (considering equal-length divisions is intuitive when we have a uniform source. For nonuniform sources a nonequal partitioning must be considered; see Section 4.3), δl, 1≤l≤L. To identify to which division among the total L divisions X belongs, B bits are provided for the FC, using B local-Qs; that is, Pb,1≤b≤B. These local-Qs can be designed so that, for each division on the range [-V,V], the B bits together make the B-digit binary label/word assigned to that division. Figure 3 illustrates B=4 local-Qs that together assign 4-digit binary words to the 16 divisions. This assignment is conducted using the “natural” binary numeral system. In other words, reading vertically from left to right, the first division is assigned 0000, the second is assigned 0001, the third is assigned 0010, and so on. If a different binary numeral systems, referred to as the “labeling” scheme in this work, is used for labeling the divisions, a different set of B local-Qs would result. This is why the local-Qs in Figure 3 are identified as PbNr, 1≤b≤B, where the superscript “Nr” stands for the natural labeling. If instead of the natural labeling, Gray labeling is used, a set of local-Qs, that is, PbGr, will be produced; see Figure 4. Clearly, other labeling schemes can be considered.Figure 3
The natural basis local-Qs forB=4.Figure 4
The Gray basis local-Qs forB=4.Similarly, for the noisy scenario, we can quantize each local noisy measurementZb, 1≤b≤B, using one of the local-Qs Pb, 1≤b≤B. Depending on where Zb falls, Pb decides the bth bit. Since there are N=B measurements, the bth measurement provides the bth digit of the B-digit binary word, for 1≤b≤B. At the FC, the B bits are used to remake the B-digit binary word and thereby construct X^.The above described method can be viewed as adistributed quantizer, since a uniform L-level quantization is implemented using B separate binary quantizers. In a noiseless scenario, the performance of this distributed quantizer is the same as the centralized scalar quantizer, meaning that its MSE is Δ2/12, where Δ=2V/L. Moreover, when all observations are equal to X, using either PbNr, 1≤b≤B, PbGr, 1≤b≤B, or any other set of B local-Qs based on different labelings, results in the same MSE, that is, Δ2/12. However, in the presence of the measurement noise, any of the B bits of the distributed quantizer might be quantized wrong, leading to a larger estimation error in the FC. In this case, the overall MSE at the FC is affected totally differently by different local-Qs and also depends on the position of the unknown X. Thus, writing the MSE in closed form will not have a simple or insightful structure. In Section 5.3, we derive the CRLB to compare to the simulation results of our method.One way to reduce the final MSE is to use better labeling schemes, which results in different local-Qs. In Section4.1, the optimal local-Qs for achieving the best performance are discussed. For uniform X, using the Gray labeling to design the local-Qs achieves the optimal estimation performance. However, this is not the case for other distributions of X. For Gaussian X, the optimal local-Qs are discussed in Section 4.3.It is possible to further enhance the estimation when more observations are available. In the same noise level, whenN>B measurements are used, it is possible to estimate X more accurately, using the same L=2B-level quantizer as the basic quantizer. In such cases, the extra measurements can be used to repeat some of the binary digits and reduce the bit error rate of those bits, that is, a similar approach as [14]. However, instead of simple bit repetition, one can better employ the extra measurements to get the optimal estimation performance. This is further discussed in Section 4.2.In the following sections, we introduce an algebraic approach to further explain the distributed quantization. Through that, we find the optimal local-Qs to get the best estimation performance whenN≥B. In particular, for N>B, an analogy between error-correcting codes and the distributed quantization is used.


## 4. Optimal Distributed Quantization

Assume that there areN independent noisy measurements from the unknown X. To achieve the best estimation, one needs to obtain the optimal set of local-Qs to be assigned to the analog measurements. For a fixed B, if N=B, the solution to the above problem results in the optimal labeling scheme. If N>B, the result is an error-correcting distributed quantization. These two cases are studied separately in the following sections.


### 4.1. Best Labeling Scheme,N=B

In Section3, we discussed two sets of local-Qs, resulting from applying two different labeling systems, that is, natural and Gray. In this section we discuss other sets of local-Qs. It is worth mentioning again that if no measurement noise is present all of these sets of local-Qs will have the same performance. However, in the presence of measurement noise, they have different performances in terms of the estimation MSE.To locate a variable inL distinct divisions (in the interval [-V,V]), B bits are needed, where B=log⁡2L. To generate such B bits, an eligible set of B local-Qs can be chosen from a variety of choices. As mentioned in Section 2, each local-Q is basically a binary vector of length L. Choosing B “eligible local-Qs” that can identify L different divisions is analogous to choosing B linearly independent binary vectors (please note that the algebraic calculations are done in GF (2)) of size L. The B “eligible local-Qs” are called the “basis local-Qs,” for brevity.The set of natural local-Qs in Section3 gives one example set of basis local-Qs, namely, the “natural basis local-Qs” PbNr,1≤b≤B, Figure 3. Taking the natural basis local-Qs as the reference vectors and linearly combining them to generate a new set of B linearly independent vectors, we obtain a different set of basis local-Qs. The linear combinations of the B reference local-Qs into a new set of B linearly independent local-Qs can be represented by a B×B binary matrix of rank B. For example, for B=4 a special combination of natural basis local-Qs can be shown by
(3)GBB=[1100011000110001],
which indicates a combination of the local-Qs as
(4)P1Gr=P1Nr,P2Gr=P1Nr⊕P2Nr,P3Gr=P2Nr⊕P3Nr,P4Gr=P3Nr⊕P4Nr,
where ⊕ means modulo-2 summation of the L-valued binary vectors representing the local-Qs. The new set of basis local-Qs obtained by the GBB example in (3) is the set of Gray local-Qs (Figure 4).In this work, we focus on the natural basis local-Qs as the original local-Q set and their linear combinations, in the form ofGBB, for producing new local-Q sets. By searching all matrices of type GBB, one can find the best basis local-Qs with the lowest MSE, for each SNR level. As mentioned above, GBB must be full rank. Moreover, a permutation of the vectors of GBB results in the same set of local-Qs. Hence, the size of the search space is
(5)Ω1(B)=1B!∏i=1B‍(2B-2i-1).


### 4.2. Error-Correcting Local-Qs,N>B

As mentioned earlier, havingN>B measurements available, the estimation accuracy can be improved by repeating some of the local-Qs. However, a more effective approach is proposed here, by choosing new local local-Qs for the redundant measurements. Taking the B basis local-Qs of Section 3 as starting point, N local-Qs are obtained so that together they generate N-bit words to identify L=2B divisions. Obviously, using N-bit words instead of B-bit words (as in Section 3) is a redundant way of labeling an L-division quantization. However, this redundancy enables some error correction possibility in estimating the division of X. This property is analogous to error-correcting property in channel coding, where some redundant bits are added to the B-bit messages to make N-bit codewords [22]. This happens by adding extra vectors to the generator matrix.Among theN local-Qs used to quantize the N measurements, there must be at least B linearly independent local-Qs. Hence, the N local-Qs are produced by linear combination of a set of B basis local-Qs according to a B×N matrix of rank B. For example, consider the matrix
(6)GBN=[1100101011011000111010001011],
which is used to produce N local-Qs from the B natural basis local-Qs. In this example, the first part of GBN is a 4×4 matrix similar to (3). Therefore, there will be the four Gray basis local-Qs among the 7 local-Qs produced by GBN. Figure 5 shows the 3 extra local-Qs.Figure 5
Local-Qs for the extra 3 bits.DifferentGBN matrices can be used to produce different sets of local-Qs, each having a different estimation performance. A repetition strategy, in which some of the basis local-Qs are repeated for quantizing the extra measurements, is a special case of the explained approach. However, by searching among different matrices one can find a set of N local-Qs that have better performance than a mere repetition scheme. The optimal set of local-Qs for each values of N and B depends on the SNR and can be obtained by exhaustive search. The size of the search space is given by
(7)Ω2(B,N)=Ω1(B)×(2B-1+(N-B-1)N-B).In Section6, some optimal results are shown and discussed. It is worth mentioning that the search for finding the optimal local-Qs is done in the FC and happens only once. After the optimal set of local-Qs is obtained, each local-Q is assigned to each sensor. As long as the measurement noise variance does not change a lot, the local-Qs do not need to be updated.It is worthwhile pointing that there is a difference between the functionality of error-correcting codes when used against channel noise and when, in this case, used in the distributed estimation problem. In channel coding, the source of bit error is the additive channel noise which contaminates the coded bits after they are sent on the channel. On the contrary, in the case of distributed quantization, the bit error happens during the quantization process when the bits are being generated. The main difference this causes is that, unlike the channel coding, the a priori bit error probability (BEP) is not the same for all bits. Even in a homogeneous scenario with i.i.d. noise for all the observations, that is, the sameσ, the probability of error for each bit depends on its local-Q and how small thecell lengths are in that local-Q. Moreover, the BEPs also depend on the value of X. Because of these fundamental differences, known optimal channel codes are no longer optimal for distributed estimation. Also, a separate study is required for the decoder/estimator of the proposed error-correcting quantization method.


### 4.3. Gaussian Source

Up to this end we had assumed that the unknown parameterX is uniformly distributed. Therefore, in Section 3, we had started our method by first assuming uniform partitioning of the range [-V,V] into L equal divisions. If the parameter X is not uniformly distributed, the uniform partitioning of the range is not optimal. However, still the same methodology described in Sections 4.1 and 4.2 can be used to design the optimal local-Qs, but with different partitioning of the range of X. As an example, we discuss the Gaussian source. The results of applying our distributed quantization method for a Gaussian parameter are presented in Section 6.For a Gaussian source, we assume that the range ofX, that is, (-∞,∞), is partitioned according to the Lloyd-Max algorithm [23, 24] for centralized quantization. For example, for X~N(0,1), the optimal B=3-bit centralized quantization has the range of X partitioned into L=8 divisions as (-∞,-1.748,-1.05,-0.5006,0,0.5006,1.05,1.748,∞). To derive B local-Qs for a Gaussian noise, we take the same steps as in Sections 4.1 and 4.2, except that the value of edges for every local-Q is a subset of the above edges.


### 4.4. Suboptimal Search Strategy

Due to the nature of the optimization problem, an exhaustive search must be performed to find the optimal local-Qs. In many WSN applications,B and N are small quantities, and the search is feasible. For those values of B and N where the search space size is too big, suboptimal strategies can be suggested to reduce the complexity. Some of those strategies are discussed here.Strategy 1.
When aB-bit precision is practiced with N sensors, there must be always B linearly independent local-Qs among the N local-Qs. Based on the simulation results, it can be investigated that, for uniform X and Gaussian noise, there are always the same B independent local-Qs for every SNR value. In this scenario, the B local-Qs derived based on Gray labeling, that is, P1Gr,…,PBGr, are always among the N optimal local-Qs. Therefore, for uniform X and Gaussian noise, to design the N local-Qs for any SNR, one can fix B of them to be the Gray local-Qs. This reduces the size of the search space from Ω2(B,N) to Ω2′(B,N), which is equal to the second term of the product in (7).Strategy 2.
Another simplifying strategy can be practiced for big values ofN. During the simulations, it was observed that when N gets bigger while B is constant, some local-Qs are repeated among the optimal local-Qs. Therefore, even for very big N, one can limit the search to a smaller space, for example, N0<N, find the optimal local-Qs for that subspace, and repeat the same N0 local-Qs for the rest of the observations.Both of the above strategies can be combined to reduce the search space. For example, for a uniformly distributed unknown parameter with Gaussian measurement noises, a suboptimal search method is explained as follows. For1≤n≤B, one uses P1Gr,…,PBGr. For B+1≤n≤N0, a search is performed on a space with size Ω2′(B,N0). For N0+1≤n≤2N0, 2N0+1≤n≤3N0,…, the same N0 local-Qs are repeated. A third strategy which further reduces the complexity is presented in Section 5.3.


## 4.1. Best Labeling Scheme,N=B

In Section3, we discussed two sets of local-Qs, resulting from applying two different labeling systems, that is, natural and Gray. In this section we discuss other sets of local-Qs. It is worth mentioning again that if no measurement noise is present all of these sets of local-Qs will have the same performance. However, in the presence of measurement noise, they have different performances in terms of the estimation MSE.To locate a variable inL distinct divisions (in the interval [-V,V]), B bits are needed, where B=log⁡2L. To generate such B bits, an eligible set of B local-Qs can be chosen from a variety of choices. As mentioned in Section 2, each local-Q is basically a binary vector of length L. Choosing B “eligible local-Qs” that can identify L different divisions is analogous to choosing B linearly independent binary vectors (please note that the algebraic calculations are done in GF (2)) of size L. The B “eligible local-Qs” are called the “basis local-Qs,” for brevity.The set of natural local-Qs in Section3 gives one example set of basis local-Qs, namely, the “natural basis local-Qs” PbNr,1≤b≤B, Figure 3. Taking the natural basis local-Qs as the reference vectors and linearly combining them to generate a new set of B linearly independent vectors, we obtain a different set of basis local-Qs. The linear combinations of the B reference local-Qs into a new set of B linearly independent local-Qs can be represented by a B×B binary matrix of rank B. For example, for B=4 a special combination of natural basis local-Qs can be shown by
(3)GBB=[1100011000110001],
which indicates a combination of the local-Qs as
(4)P1Gr=P1Nr,P2Gr=P1Nr⊕P2Nr,P3Gr=P2Nr⊕P3Nr,P4Gr=P3Nr⊕P4Nr,
where ⊕ means modulo-2 summation of the L-valued binary vectors representing the local-Qs. The new set of basis local-Qs obtained by the GBB example in (3) is the set of Gray local-Qs (Figure 4).In this work, we focus on the natural basis local-Qs as the original local-Q set and their linear combinations, in the form ofGBB, for producing new local-Q sets. By searching all matrices of type GBB, one can find the best basis local-Qs with the lowest MSE, for each SNR level. As mentioned above, GBB must be full rank. Moreover, a permutation of the vectors of GBB results in the same set of local-Qs. Hence, the size of the search space is
(5)Ω1(B)=1B!∏i=1B‍(2B-2i-1).


## 4.2. Error-Correcting Local-Qs,N>B

As mentioned earlier, havingN>B measurements available, the estimation accuracy can be improved by repeating some of the local-Qs. However, a more effective approach is proposed here, by choosing new local local-Qs for the redundant measurements. Taking the B basis local-Qs of Section 3 as starting point, N local-Qs are obtained so that together they generate N-bit words to identify L=2B divisions. Obviously, using N-bit words instead of B-bit words (as in Section 3) is a redundant way of labeling an L-division quantization. However, this redundancy enables some error correction possibility in estimating the division of X. This property is analogous to error-correcting property in channel coding, where some redundant bits are added to the B-bit messages to make N-bit codewords [22]. This happens by adding extra vectors to the generator matrix.Among theN local-Qs used to quantize the N measurements, there must be at least B linearly independent local-Qs. Hence, the N local-Qs are produced by linear combination of a set of B basis local-Qs according to a B×N matrix of rank B. For example, consider the matrix
(6)GBN=[1100101011011000111010001011],
which is used to produce N local-Qs from the B natural basis local-Qs. In this example, the first part of GBN is a 4×4 matrix similar to (3). Therefore, there will be the four Gray basis local-Qs among the 7 local-Qs produced by GBN. Figure 5 shows the 3 extra local-Qs.Figure 5
Local-Qs for the extra 3 bits.DifferentGBN matrices can be used to produce different sets of local-Qs, each having a different estimation performance. A repetition strategy, in which some of the basis local-Qs are repeated for quantizing the extra measurements, is a special case of the explained approach. However, by searching among different matrices one can find a set of N local-Qs that have better performance than a mere repetition scheme. The optimal set of local-Qs for each values of N and B depends on the SNR and can be obtained by exhaustive search. The size of the search space is given by
(7)Ω2(B,N)=Ω1(B)×(2B-1+(N-B-1)N-B).In Section6, some optimal results are shown and discussed. It is worth mentioning that the search for finding the optimal local-Qs is done in the FC and happens only once. After the optimal set of local-Qs is obtained, each local-Q is assigned to each sensor. As long as the measurement noise variance does not change a lot, the local-Qs do not need to be updated.It is worthwhile pointing that there is a difference between the functionality of error-correcting codes when used against channel noise and when, in this case, used in the distributed estimation problem. In channel coding, the source of bit error is the additive channel noise which contaminates the coded bits after they are sent on the channel. On the contrary, in the case of distributed quantization, the bit error happens during the quantization process when the bits are being generated. The main difference this causes is that, unlike the channel coding, the a priori bit error probability (BEP) is not the same for all bits. Even in a homogeneous scenario with i.i.d. noise for all the observations, that is, the sameσ, the probability of error for each bit depends on its local-Q and how small thecell lengths are in that local-Q. Moreover, the BEPs also depend on the value of X. Because of these fundamental differences, known optimal channel codes are no longer optimal for distributed estimation. Also, a separate study is required for the decoder/estimator of the proposed error-correcting quantization method.


## 4.3. Gaussian Source

Up to this end we had assumed that the unknown parameterX is uniformly distributed. Therefore, in Section 3, we had started our method by first assuming uniform partitioning of the range [-V,V] into L equal divisions. If the parameter X is not uniformly distributed, the uniform partitioning of the range is not optimal. However, still the same methodology described in Sections 4.1 and 4.2 can be used to design the optimal local-Qs, but with different partitioning of the range of X. As an example, we discuss the Gaussian source. The results of applying our distributed quantization method for a Gaussian parameter are presented in Section 6.For a Gaussian source, we assume that the range ofX, that is, (-∞,∞), is partitioned according to the Lloyd-Max algorithm [23, 24] for centralized quantization. For example, for X~N(0,1), the optimal B=3-bit centralized quantization has the range of X partitioned into L=8 divisions as (-∞,-1.748,-1.05,-0.5006,0,0.5006,1.05,1.748,∞). To derive B local-Qs for a Gaussian noise, we take the same steps as in Sections 4.1 and 4.2, except that the value of edges for every local-Q is a subset of the above edges.


## 4.4. Suboptimal Search Strategy

Due to the nature of the optimization problem, an exhaustive search must be performed to find the optimal local-Qs. In many WSN applications,B and N are small quantities, and the search is feasible. For those values of B and N where the search space size is too big, suboptimal strategies can be suggested to reduce the complexity. Some of those strategies are discussed here.Strategy 1.
When aB-bit precision is practiced with N sensors, there must be always B linearly independent local-Qs among the N local-Qs. Based on the simulation results, it can be investigated that, for uniform X and Gaussian noise, there are always the same B independent local-Qs for every SNR value. In this scenario, the B local-Qs derived based on Gray labeling, that is, P1Gr,…,PBGr, are always among the N optimal local-Qs. Therefore, for uniform X and Gaussian noise, to design the N local-Qs for any SNR, one can fix B of them to be the Gray local-Qs. This reduces the size of the search space from Ω2(B,N) to Ω2′(B,N), which is equal to the second term of the product in (7).Strategy 2.
Another simplifying strategy can be practiced for big values ofN. During the simulations, it was observed that when N gets bigger while B is constant, some local-Qs are repeated among the optimal local-Qs. Therefore, even for very big N, one can limit the search to a smaller space, for example, N0<N, find the optimal local-Qs for that subspace, and repeat the same N0 local-Qs for the rest of the observations.Both of the above strategies can be combined to reduce the search space. For example, for a uniformly distributed unknown parameter with Gaussian measurement noises, a suboptimal search method is explained as follows. For1≤n≤B, one uses P1Gr,…,PBGr. For B+1≤n≤N0, a search is performed on a space with size Ω2′(B,N0). For N0+1≤n≤2N0, 2N0+1≤n≤3N0,…, the same N0 local-Qs are repeated. A third strategy which further reduces the complexity is presented in Section 5.3.


## 5. Decoding

In the FC, a decoding method must be used to estimate the unknown parameter from the received binary-quantized measurementsyn. Here, we explain two types of decoders, that is, the discrete and continuous decoders, which estimate X based on the discrete and continuous a posteriori distributions, respectively. For the sake of better understanding the overall behavior of the distributed estimation method, we first explain the discrete decoder. In both estimators the receiver only needs to do the computations once at the beginning of the algorithm to build a lookup table, which is used during the estimation procedure.


### 5.1. Discrete A Posteriori

As a discrete decoder, the estimator locatesX in one of the discrete divisions δl, 1≤l≤L, from the received bits. In this section we propose an ML estimator that decodes the N received bits to estimate thedivision of X among the L divisions.As discussed in Section4, for each value of X a set of N local-Qs together generate an N-bit “codeword.” Assuming no measurement noise, there are L=2B different codewords; that is, cl=[c1lc2l⋯cNl], 1≤l≤L. There is a one-to-one correspondence between these valid codewords and the L divisions, that is, δl, 1≤l≤L. In the presence of measurement noise, each of the N bits, that is, yn, 1≤n≤N, might be wrong, resulting in a “received word” (note that the notation “received” does not imply a communication channel or channel error)   y=[y1,y2,…,yn], which might include some bit errors. The discrete decoder’s function is to find the most likely valid codeword based on the received N-bit word y, which in turn results in estimating the division of X. This estimator can be reduced to a lookup table that can be saved in the receiver.To build the lookup table for the discrete decoder, the likelihoods, or equivalently the a posteriori probabilities, of all theL valid codewords conditioned on the received word y are calculated. The codeword with the maximum likelihood is chosen as the decoder’s decision corresponding to each y. The center of mass [23] for that division is recognized as the estimated value X^. This decoder is therefore referred to as the discrete ML estimator. The a posteriori likelihood of each codeword can be written as
(8)P(cl∣y)∝P(cl)∏n=1N‍P(yn∣cl),
where P(cl) is the a priori probability of codeword cl, which is equal to P(Γl-1≤X≤Γl), where Γl-1 and Γl indicate the left and right edges of the lth quantization division δl, corresponding to cl. For uniform X, Γl-1=-V+(l-1)Δ, and Γl=-V+lΔ.Since each valid codeword is associated with one of theL divisions δl, 1≤l≤L, each term of the product in (8) can be described as
(9)P(yn∣cl)=P(yn∣Γl-1≤X≤Γl)=∫Γl-1Γl‍P(yn∣X)P(X)dX∫Γl-1Γl‍P(X)dX.
The denominator in the second line is by definition P(cl), the a priori probability of the codeword cl, which for uniform X is equal for every cl. Remembering that yn can be either 0 or 1, (9) can be written as
(10)P(yn∣cl)=∫Γl-1Γl‍P1n(X)(yn)(1-P1n(X))(1-yn)P(X)dX,
where P1n(X) is the probability that the nth bit is 1 when the parameter value is X, that is, P(yn=1∣X). The formula to calculate P1n(X) is given in Appendix B. Using (10) and (8) one can find the a posteriori probability of the codewords.At the beginning of the algorithm a decoding table is formed by calculating the a posteriori probabilities for different values of the received word, that is,yk, 1≤k≤2N, and different valid codewords cl, 1≤l≤L. This calculation is done once in the FC and does not need to repeat every time. The decoding table has 2N entries, one for every possible value of y, associating it with a codeword which has the highest likelihood P(cl∣y). For every estimation instance, based on the received word, the decoder chooses the corresponding codeword from the table as the most likely codeword and announces the center of mass of the associated division as X^. It is easy to see that the lookup table depends on the local-Qs set, as well as σ.The discrete ML decoder is based on finding the a posteriori probability of the valid codewords, which have one-to-one correspondence with the division ofX. Therefore, they can only locate X with a limited precision. To better estimate the analog parameter X, a continuous decoder can be used instead of the discrete decoder, resulting in better estimation performance.


### 5.2. Continuous A Posteriori

The continuous decoder is designed based on the continuous a posteriori pdf ofX. Using the a posteriori pdf, a MAP or MMSE estimator can be designed. Again, similar to the discrete decoder, the receiver only needs to do the computations once at the beginning of the algorithm to build a lookup table, which is used during the estimation procedure.The continuous a posteriori distribution ofX, that is, P(X∣y), can be written as
(11)P(X∣y)∝P(X)∏n=1N‍P(yn∣X)∝P(X)∏n=1N‍P1n(X)(yn)(1-P1n(X))(1-yn).
The factorization in (11) is valid since the measurement noises as well as the quantization procedures are independent for different measurements. Once the above a posteriori conditional distribution is derived, one can find X^=argmax⁡XP(X∣y) or X^=E{X∣y} as a MAP or MMSE estimator of X, respectively.In the FC, the following calculations are done once to build a decoding table. For each possible received wordyk, 1≤k≤2N, the MAP or MMSE estimation X^k is calculated to build an entry in the lookup table, mapping yk to X^k. Every time an N-bit word is received at the decoder this lookup table is used to find X^.It is easy to investigate that the MSE performance of the continuous decoder is better than the discrete one, while the computational complexity of the continuous decoder is only slightly higher than the discrete decoder. The performance of different decoders is studied through simulations in Section6 and compared to the CRLB for the optimum unbiased estimator.


### 5.3. Performance Bounds

To evaluate the performance of our estimator, we have calculated the CRLB for a set of local-Qs. In our distributed estimation method, for the case of Gaussian or uniformX and Gaussian noise, the CRLB can be the indicator of the best estimation performance if the estimator is unbiased. The unbiasedness of our MMSE estimator is proven in Appendix A. The CRLB of the estimation method is given by
(12)(∑n=1N‍∫X‍{(∂P1n(X)/∂X)2P1n(X)+(∂P1n(X)/∂X)21-P1n(X)}hhhhhih×P(X)dX+J2∑n=1N‍∫X‍{(∂P1n(X)/∂X)2P1n(X)+(∂P1n(X)/∂X)21-P1n(X)})-1,
where, for a uniform X, J2=0, and, for a Gaussian X with zero mean and variance σx2, J2=1/σx2. See Appendix B for derivation of (12).Strategy 3.
Based on the CRLB, a strategy can be devised to reduce the computational complexity of the search method described in Section4. As explained there, the optimal local-Qs are found by minimizing the MSE. That is to say, for every candidate set of N local-Qs, the MSE of estimation is found through simulation, and finally the set of local-Qs with the lowest MSE is selected. To reduce the complexity, we suggest using an MSE bound, that is, the CRLB, instead of finding the actual MSE. So, for every candidate set of local-Qs, the CRLB is calculated based on (12), and the set with the lowest CRLB value is selected. Using this strategy along with the other two strategies in Section 4.4, the complexity of finding the local-Qs will be reduced greatly. The MSE results for the suboptimal local-Qs have been compared with the optimal local-Qs in Section 6.


## 5.1. Discrete A Posteriori

As a discrete decoder, the estimator locatesX in one of the discrete divisions δl, 1≤l≤L, from the received bits. In this section we propose an ML estimator that decodes the N received bits to estimate thedivision of X among the L divisions.As discussed in Section4, for each value of X a set of N local-Qs together generate an N-bit “codeword.” Assuming no measurement noise, there are L=2B different codewords; that is, cl=[c1lc2l⋯cNl], 1≤l≤L. There is a one-to-one correspondence between these valid codewords and the L divisions, that is, δl, 1≤l≤L. In the presence of measurement noise, each of the N bits, that is, yn, 1≤n≤N, might be wrong, resulting in a “received word” (note that the notation “received” does not imply a communication channel or channel error)   y=[y1,y2,…,yn], which might include some bit errors. The discrete decoder’s function is to find the most likely valid codeword based on the received N-bit word y, which in turn results in estimating the division of X. This estimator can be reduced to a lookup table that can be saved in the receiver.To build the lookup table for the discrete decoder, the likelihoods, or equivalently the a posteriori probabilities, of all theL valid codewords conditioned on the received word y are calculated. The codeword with the maximum likelihood is chosen as the decoder’s decision corresponding to each y. The center of mass [23] for that division is recognized as the estimated value X^. This decoder is therefore referred to as the discrete ML estimator. The a posteriori likelihood of each codeword can be written as
(8)P(cl∣y)∝P(cl)∏n=1N‍P(yn∣cl),
where P(cl) is the a priori probability of codeword cl, which is equal to P(Γl-1≤X≤Γl), where Γl-1 and Γl indicate the left and right edges of the lth quantization division δl, corresponding to cl. For uniform X, Γl-1=-V+(l-1)Δ, and Γl=-V+lΔ.Since each valid codeword is associated with one of theL divisions δl, 1≤l≤L, each term of the product in (8) can be described as
(9)P(yn∣cl)=P(yn∣Γl-1≤X≤Γl)=∫Γl-1Γl‍P(yn∣X)P(X)dX∫Γl-1Γl‍P(X)dX.
The denominator in the second line is by definition P(cl), the a priori probability of the codeword cl, which for uniform X is equal for every cl. Remembering that yn can be either 0 or 1, (9) can be written as
(10)P(yn∣cl)=∫Γl-1Γl‍P1n(X)(yn)(1-P1n(X))(1-yn)P(X)dX,
where P1n(X) is the probability that the nth bit is 1 when the parameter value is X, that is, P(yn=1∣X). The formula to calculate P1n(X) is given in Appendix B. Using (10) and (8) one can find the a posteriori probability of the codewords.At the beginning of the algorithm a decoding table is formed by calculating the a posteriori probabilities for different values of the received word, that is,yk, 1≤k≤2N, and different valid codewords cl, 1≤l≤L. This calculation is done once in the FC and does not need to repeat every time. The decoding table has 2N entries, one for every possible value of y, associating it with a codeword which has the highest likelihood P(cl∣y). For every estimation instance, based on the received word, the decoder chooses the corresponding codeword from the table as the most likely codeword and announces the center of mass of the associated division as X^. It is easy to see that the lookup table depends on the local-Qs set, as well as σ.The discrete ML decoder is based on finding the a posteriori probability of the valid codewords, which have one-to-one correspondence with the division ofX. Therefore, they can only locate X with a limited precision. To better estimate the analog parameter X, a continuous decoder can be used instead of the discrete decoder, resulting in better estimation performance.


## 5.2. Continuous A Posteriori

The continuous decoder is designed based on the continuous a posteriori pdf ofX. Using the a posteriori pdf, a MAP or MMSE estimator can be designed. Again, similar to the discrete decoder, the receiver only needs to do the computations once at the beginning of the algorithm to build a lookup table, which is used during the estimation procedure.The continuous a posteriori distribution ofX, that is, P(X∣y), can be written as
(11)P(X∣y)∝P(X)∏n=1N‍P(yn∣X)∝P(X)∏n=1N‍P1n(X)(yn)(1-P1n(X))(1-yn).
The factorization in (11) is valid since the measurement noises as well as the quantization procedures are independent for different measurements. Once the above a posteriori conditional distribution is derived, one can find X^=argmax⁡XP(X∣y) or X^=E{X∣y} as a MAP or MMSE estimator of X, respectively.In the FC, the following calculations are done once to build a decoding table. For each possible received wordyk, 1≤k≤2N, the MAP or MMSE estimation X^k is calculated to build an entry in the lookup table, mapping yk to X^k. Every time an N-bit word is received at the decoder this lookup table is used to find X^.It is easy to investigate that the MSE performance of the continuous decoder is better than the discrete one, while the computational complexity of the continuous decoder is only slightly higher than the discrete decoder. The performance of different decoders is studied through simulations in Section6 and compared to the CRLB for the optimum unbiased estimator.


## 5.3. Performance Bounds

To evaluate the performance of our estimator, we have calculated the CRLB for a set of local-Qs. In our distributed estimation method, for the case of Gaussian or uniformX and Gaussian noise, the CRLB can be the indicator of the best estimation performance if the estimator is unbiased. The unbiasedness of our MMSE estimator is proven in Appendix A. The CRLB of the estimation method is given by
(12)(∑n=1N‍∫X‍{(∂P1n(X)/∂X)2P1n(X)+(∂P1n(X)/∂X)21-P1n(X)}hhhhhih×P(X)dX+J2∑n=1N‍∫X‍{(∂P1n(X)/∂X)2P1n(X)+(∂P1n(X)/∂X)21-P1n(X)})-1,
where, for a uniform X, J2=0, and, for a Gaussian X with zero mean and variance σx2, J2=1/σx2. See Appendix B for derivation of (12).Strategy 3.
Based on the CRLB, a strategy can be devised to reduce the computational complexity of the search method described in Section4. As explained there, the optimal local-Qs are found by minimizing the MSE. That is to say, for every candidate set of N local-Qs, the MSE of estimation is found through simulation, and finally the set of local-Qs with the lowest MSE is selected. To reduce the complexity, we suggest using an MSE bound, that is, the CRLB, instead of finding the actual MSE. So, for every candidate set of local-Qs, the CRLB is calculated based on (12), and the set with the lowest CRLB value is selected. Using this strategy along with the other two strategies in Section 4.4, the complexity of finding the local-Qs will be reduced greatly. The MSE results for the suboptimal local-Qs have been compared with the optimal local-Qs in Section 6.


## 6. Numerical Results

In this section, different simulation results are discussed in order to study the performance of the proposed distributed estimation method. Both scenarios in Section4.1, where N=B, and Section 4.2, where N>B, are considered. The results are shown for two distributions of the unknown parameter, that is, uniform and Gaussian. For the case of uniform unknown parameter, X is uniformly distributed in the interval [-1,1]. For Gaussian X, it is distributed according to N(0,0.1). Comparison with other methods, such as [4, 11, 12, 14], is discussed. The performance is evaluated in terms of the MSE. In all simulations, the measurement noise is i.i.d. zero mean Gaussian with variance σ2. Note that this SNR is only related to the measurement noise, while the channel is assumed to be error-free.Figure6 shows the performance of the distributed estimation method for a uniform source. Since X is uniform, E{X2}=V2/3; therefore, the average SNR is 10log⁡10(V2/3σ2). At each SNR, the optimal set of local-Qs was found by searching all matrices GBN for B=3 and N=3, 5, and 8. For the case of N=8, the results of the suboptimal search method based on both Strategy 1 and Strategy 3 are also shown in the figure. Note that, for all cases, the continuous MMSE estimator is used in the decoder. The results show that when N=B the optimal local-Q set for every SNR is the Gray basis local-Qs. When N>B, for each SNR a different set of optimal local-Qs are found, reducing the estimation error. For example, for the case of B=3 and N=8 the optimal local-Qs for SNR =18.2 dB are presented in Table 1. From the table, we can see that the local-Qs P1, P2, and P3 are the 3 Gray basis local-Qs, and the rest are linear combinations of those.Table 1
Optimal local-Qs for uniformX, B=3, N=8, and SNR =18.2 dB.
P
1
0
0
0
0
1
1
1
1
P
2
0
0
1
1
1
1
0
0
P
3
0
1
1
0
0
1
1
0
P
4
0
1
1
0
0
1
1
0
P
5
0
1
1
0
0
1
1
0
P
6
0
0
1
1
0
0
1
1
P
7
0
1
0
1
0
1
0
1
P
8
0
1
0
1
1
0
1
0Figure 6
Effect of error-correcting local-Qs in estimation performance.For the case ofN=8 the performance of our algorithm is compared with the distributed estimation proposed by Luo [14]. Based on Luo’s algorithm, N/2=4 measurements are quantized to the first bit in a natural binary system, N/4=2 measurements are used to estimate the second bit, and the remaining 2 measurements are used for the third bit. As can be seen in Figure 6, the optimal sets of 8 local-Qs for different SNRs outperform the method of [14].The three different decoding methods based on the discrete and continuous a posteriori functions in Section5 are compared in Figure 7. The first decoding method is the ML estimation based on the discrete a posteriori likelihood of the codewords discussed in Section 5.1. The other two methods are the MAP and MMSE estimations based on the continuous a posteriori density of X in Section 5.2. Also, the CRLB for uniform X has been shown for comparison.Figure 7
Performance of different decoding methods, for GaussianX.For a Gaussian parameter with zero mean and varianceσx2=0.1, the results for N=B=3 are shown in Figure 8. The average SNR in this case is 10log⁡10(σx2/σ2). Please note that, as explained in Section 4.3, the values for division edges of the centralized quantizer, that is, Γl, 1≤l≤L, are set to σx×{-1.748,-1.05,-0.5006,0,0.5006,1.05,1.748} [23]. As an example, the optimal local-Qs for SNR =5.2 dB are presented in Table 2. Note that the local-Qs are lineally independent, but, unlike the case of uniform X, the optimal local-Qs are not the Gray basis local-Qs.Table 2
Optimal local-Qs for GaussianX, N=B=3, SNR =5.2 dB.
P
1
0
1
1
0
0
1
1
0
P
2
1
0
0
0
1
1
1
0
P
3
0
1
0
1
1
0
1
0Figure 8
Performance of our distributed estimation method for Gaussian parameter withσx2=0.1, B=3.Figure9 compares the performance of our proposed method with other binary quantization methods, for N=10. The circle points in Figure 9 show the MSE for the suboptimal local-Qs found using the three suboptimal search strategies. For the method proposed by Ribeiro and Giannakis [12], the CRLB for the optimal solution is indicated. Two adaptive quantization methods proposed by Fang and Li [11], that is, AQ-VS and AQ-ML, are also shown in the figure. For the AQ-ML, before quantizing each measurement a ML estimation must be calculated. It can be seen from Figure 9 that for SNR >15 dB our method has lower MSE compared to [11, 12], while its complexity for “each estimation job” (as long as the SNR does not change a lot) is less than those algorithms.Figure 9
Performance comparison for different methods forN=10.


## 7. Conclusion

In this study we proposed an optimum distributed quantization method to estimate unknown parameter form sensors’ noisy measurements, each compressed to one bit. The estimation method is based on designing multithreshold local-Qs to generate a single bit from each analog measurement and an appropriate decoder to be used at the fusion center for estimating the unknown. The results show that, for GaussianX, when B measurements are used to achieve an estimation with B-bit precision, the optimal B local-Qs are those based on the Gray labeling for all SNRs. For scenarios where N>B measurements are available, extra local-Qs are found to achieve an error-correcting capability compared to the case when only B measurements are available. The results have been compared with other distributed estimation methods with binary quantization and show better performance when a limited number of sensors with lower measurement noise are available.



---

*Source: 368643-2014-08-12.xml*