Weighted Distance-Based Quantization for Distributed Estimation
- Author: Kim Yoon Hak
- Publish: Journal of information and communication convergence engineering Volume 12, Issue4, p215~220, 31 Dec 2014
-
ABSTRACT
We consider quantization optimized for distributed estimation, where a set of sensors at different sites collect measurements on the parameter of interest, quantize them, and transmit the quantized data to a fusion node, which then estimates the parameter. Here, we propose an iterative quantizer design algorithm with a
weighted distance rule that allows us to reduce a system-wide metric such as the estimation error by constructing quantization partitions with their optimal weights. We show that the search for the weights, the most expensive computational step in the algorithm, can be conducted in a sequential manner without deviating from convergence, leading to a significant reduction in design complexity. Our experments demonstrate that the proposed algorithm achieves improved performance over traditional quantizer designs. The benefit of the proposed technique is further illustrated by the experiments providing similar estimation performance with much lower complexity as compared to the recently published novel algorithms.
-
KEYWORD
Distributed source coding (DSC) , Generalized Lloyd algorithm , Quantizer design , Sensor networks , Source localization , Weighted distance
-
In distributed estimation systems where many sensor nodes located at different sites operate on power-limited batteries, each node monitors its environmental conditions, such as temperature, pressure, or sound, related to the parameter of interest and sends the data to a fusion node, which then estimates the parameter value. In such powerconstrained systems, the quantization of sensing data has been an attractive topic of research for signal processing researchers since efficient quantization at each node has a significant impact on the rate-distortion performance of the system.
For a source localization system where each sensor measures the signal energy, quantizes it, and sends the quantized sensor reading to a fusion node where the localization is performed, the maximum likelihood (ML) estimation problem using quantized data was addressed and the Cramer–Rao bound (CRB) was derived for comparison [1], assuming that each sensor used identical (uniform) quantizers. However, if the node locations are known prior to the quantization process, sensor nodes can exploit the correlation between their measurements to design quantizers minimizing the system-wide metric (i.e., the estimation error) to replace typical quantizers, which would be devised to minimize the local metric, such as the reconstruction error. It has been demonstrated that a significant performance gain can be achieved by using such quantizers with respect to simple uniform quantization at all nodes.
There is a difficulty in designing independently and locally operating quantizers that minimize a global metric (e.g., the estimation error is a function of measurements from all nodes). To circumvent this, a
cooperative designseparate encoding approach was suggested for a decentralized hypothesis testing system [2] where a distributional distance was used as a criterion for quantizer design in order to yield a manageable design procedure. The necessary conditions for the optimal quantization partition construction were formulated for distributed estimation systems [3]. A related issue is quantizer design at each node in distributed source coding (DSC) frameworks, in which data collected at different locations must be encoded separately and communicated to a fusion center by using limited transmission rates. Practical quantization methods for correlated sources have been studied in [4-6].Previously, we proposed iterative quantizer design algorithms in the Lloyd algorithm framework (see also [7-9]), which design independently operating quantizers by reducing the estimation error at each iteration. Since the Lloyd algorithm is focused on minimizing a local metric (e.g., reconstruction error of local sensor readings) during quantizer design, some modification would be inevitable in order to achieve convergence with the global metric in the Lloyd design. Hence, we suggested a weighted sum of both the metrics as a cost function (i.e., local +
λ × global,λ ≥ 0) along with a search for appropriate weights. Finding the weightλ that guarantees the convergence is the most expensive computational process and should be repeated in each iteration, leading to a high computational cost. In [10], novel non-regular mapping between quantization partitions and their codewords was iteratively constructed to achieve improved performance over typical designs. In particular, quantizers with a many-to-one correspondence were shown to yield a significant improvement at the cost of a huge computational complexity.In this paper, we propose an iterative design algorithm in the generalized Lloyd framework that seeks to design independently operating scalar quantizers by partitioning quantization regions based on the weighted distance rule so as to minimize the estimation error. We search for the weights corresponding to the codewords such that the weighted partition of the regions using the codewords will result in an iterative reduction in the system-wide performance metric. To avoid a high computational complexity, we suggest a sequential search for the weights without causing performance degradation. We show that convergence of the proposed algorithm is guaranteed by reducing the global metric in each iteration and applying our design algorithm to a source localization system where the acoustic amplitude sensor model proposed in [11] is considered. We demonstrate through experiments that improved performance over traditional quantizer designs can be achieved by using our design technique. We also evaluate the proposed algorithm by a comparison with recently published novel design techniques [9,10], both of which were recently developed for source localization in acoustic sensor networks, the application considered in this work. As expected, the
weighted distance rule adopted in the proposed algorithm shows obvious advantage over the regular designs in terms of localization accuracy.The rest of this paper is organized as follows: we present the problem formulation for quantizer design in distributed estimation in Section II. We then consider quantization based on weighted distance and elaborate the proposed design process in the Lloyd algorithm framework in Section III. As an application system, we consider source localization in acoustic sensor networks in Section IV and then, evaluate the proposed technique for this system in Section V. Finally, we present the conclusions and future directions for research on distributed systems in Section VI.
In distributed estimation systems, it is assumed that
M sensor nodes are spatially placed at known locations in a sensor field, denoted byx i ∈R 2,i = 1, …,M , and collect measurements on the unknown parameter θ ⊂R N to be estimated. The measurementzi at nodei can be expressed as follows:where
fi (θ ) denotes the sensing model employed at nodei and ωi represents the measurement noise approximated by normal distributionN (0, ). It is assumed that a quantizer ofRi bits with a dynamic range [zi,min zi,max ] is employed at sensori . Note that the quantization range can be selected for each sensor on the basis of the desirable properties of their respective sensing ranges [12]. denotes thej -th codeword at sensori , which is generated whenever the measurementzi belongs to thej -th quantization partition . Each node quantizes its measurement and sends the quantized result to a fusion node, which estimates the value of the parameter on the basis of the quantized measurements, ,i = 1, …,M fromall nodes. In this work, it is assumed that we are given a good estimator , which is used to compute the estimation error during the quantizer design process. For details about estimators that operate on quantized data, see [13, 14].III. QUANTIZATION BASED ON WEIGHTED DISTANCE
Standard quantization follows the minimum distance rule on which the next quantization partition is conducted as well as the codeword computation in an iterative manner. Formally, the Voronoi region construction (i.e., quantization partitions) is defined as follows:
where
Li =2Ri represents the number of quantization partitions and consists of measurement samples that would minimize the distortion |zi − |2 if they were assigned to thej -th quantization partition. The codewords are also updated to minimize the distortion over the corresponding quantization partitions:Clearly, the two main steps defined as Eqs. (2) and (3) in the typical Lloyd design minimize the average reconstruction error
E |zi − |2. However, minimizing the reconstruction error would not produce quantizers that minimize the estimation errorE ∥θ - ∥2, which is our system-wide distortion to be minimized in the proposed design algorithm. In this work, we propose a weighted distance rule to build quantization partitions such that the estimation error is reduced at each iteration. First, we construct the Voronoi region for each weight ,j = 1, …,Li as follows:It is noted that the minimum distance rule is generated with = ½, which will create the standard construction defined in Eq. (2). Our weighted distance rule considers various cases of partitioning determined by the weights 0 < < 1. This will produce a set of candidate partitions for our design process.
Second, we search for the optimal weight starting with that minimizes the estimation error over the corresponding quantization partition:
where () , the abbreviated notation for , can be computed by replacing with for all
i . Note that the search for the optimal weight can be conducted in a sequential manner without causing the divergence problem that typically exists in iterative algorithms. Furthermore, in calculating thej -th optimal weight, only sampleszi > ,zi ∈can be considered since only these samples create a relative difference in the estimation error as the weight is varied in Eq. (5). These benefits of the proposed algorithm allow us to achieve a substantial reduction in computational complexity while maintaining the non-increasing distortion at each step.Once the optimal weights are obtained, the next step would be to update the codewords over the Voronoi regions determined by their corresponding optimal weights: formally,
Note that the construction of the Voronoi regions, the search for optimal weights, and the subsequent computation of the codewords given in Eqs. (4), (5), and (6), respectively, are repeated at each sensor node until a certain criterion is satisfied. Clearly, these procedures are guaranteed to reduce the estimation error in each iteration, leading to convergence of the design algorithm.
> A. Summary of Proposed Algorithm
Given
Li =2Ri at sensori , the algorithm is summarized as follows and is iteratively conducted over all sensorsi = 1, ...,M until a certain criterion in the estimation error is achieved:Algorithm 1 : Iterative quantizer design algorithm at sensori Step 1 : Initialize the quantizers with and ,j = 1, …,Li . Set thresholdsϵ and iteration indexκ = 1.Step 2 : For each , construct the partitions ,j = 1, …,Li by using Eq. (4). Once the Voronoi region construction is completed, compute the optimal weight by using Eq. (5).Step 3 : Given a set of optimal weights {}, update the codewords ,j = 1, …,Li by using Eq. (6).Step 4 : Compute the average distortion D=E ∥θ - ∥2 by using the updated codewords .Step 5 : If (Dκ −1 − Dκ )/Dκ <ϵ , stop; otherwise, continue. Dκ indicates the average distortion D at theκ -th iteration.Step 6 : Replace byi .κ =κ + 1 and go to Step 2.Note that the quantizers are designed offline by using a training set that is generated on the basis of Eq. (1) and the parameter distribution
p (θ ) for a given sensor node configuration; clearly, this design process makes use of information about all measurements, and when the resulting quantizers are in actual use, each sensor uses its optimal weights to quantize the measurement available to itindependently . A discussion of the sensitivity of our quantizer to the parameter perturbation of the sensor model is presented in Section V.IV. APPLICATION OF QUANTIZER DESIGN ALGORITHM
We apply our design algorithm to a source localization system where sensor nodes equipped with acoustic amplitude sensors measure source signal energy, quantize it, and transmit the quantized data to a fusion node for estimation. For collecting the signal energy readings, we use an energy decay model proposed in [11], which was verified by a field experiment and was also used in [15,16]. This model is based on the fact that the acoustic energy emitted omnidirectionally from a sound source will attenuate at a rate that is inversely proportional to the square of the distance in free space [17]. When an acoustic sensor is employed at each node, the signal energy measured at node
i and denoted byzi can be expressed as follows:Note that θ indicates the source location to be estimated and the sensor model
fi (θ ) in Eq. (1) is replaced by the acoustic sensor model, which consists of the gain factor of thei -th nodegi , an energy decay factorα , which is approximately equal to 2 in free space, and the source signal energya . The measurement noise termωi can be approximated using a normal distribution,N (0, ). It is assumed that the signal energya is known prior to estimation in this work, but the signal energy is typically modeled as a uniform distribution and can be jointly estimated along with the source location [13].In this section, we discuss a weighted distance-based quantizer (WDQ), the quantizer designed using the algorithm proposed in Section III-A. In designing WDQ, we use the equally distance-divided quantizer (EDQ) to initialize quantizers (see Step 1 in Section III-A) because EDQ can be used as an efficient initialization for quantizer design due to its good localization performance in acoustic amplitude sensor networks [8, 9]. We generate a training set from the uniform distribution of source locations and the model parameters in Eq. (7) set as
a = 50,α = 2,gi = 1, and =σ 2 = 0. Lloyd quantizers corresponding to = 1/2,∀j are also designed from the same training set for comparison. In the experiments, we consider a sensor network whereM (=5) sensors are deployed in a sensor field measuring 10 × 10 ㎡. We design quantizers by various algorithms and evaluate them by using test sets generated from the same model parameters. The experimental results are provided in terms of the average localization errorE ∥θ - ∥2. In these experiments, the localization error is computed using the ML estimation for fast computation.> A. Performance Comparison with Typical Designs
In this experiment, 100 different five-node configurations are generated in a sensor field measuring 10 × 10 ㎡. A test set of 1000 random source locations is generated for each configuration to collect signal energy measurements with
σi = 0. These measurements are then quantized by three different quantizers, namely, uniform quantizer (Unif Q), Lloyd quantizer (Lloyd Q), and WDQ withRi = 2, 3, and 4 bits, respectively. The localization error in meters is averaged over 100 node configurations for each rateRi . Fig. 1 shows the overall rate-distortion (R-D) performance for the different quantizers. As expected, WDQ outperforms the typical designs since the proposed technique exploits the correlation between the distributed measurements to construct the weighted quantization partitions that minimize the localization error.> B. Performance Evaluation: Comparison with Previous Novel Designs
In this experiment, we evaluate the proposed algorithm by comparing it with the previous novel designs, such as distributed optimized quantizers (DOQs) in [10] and the localization-specific quantizer (LSQ) in [9] since both of them are optimized for distributed source localization and can be viewed as DSC techniques, which are developed as a tool to reduce the rate required to transmit data from all nodes to the sink. These design techniques are applied for 100 five-sensor configurations by using the EDQ initialization with
Ri = 2, 3, 4 bits and tested by generating the two test sets of 1000 random source locations withσi = 0 andσi = 0.15, respectively. The R-D performance curves are plotted for comparison in Fig. 2. It should be observed that the proposed algorithm offers good performance without incurring high computational complexity as compared to DOQ and LSQ. Note that DOQ operates in a non-regular framework, which requires a huge computation [10].> C. Sensitivity Analysis of Design Algorithms
In this section, we first investigate how the performance of the proposed design algorithm can be affected by the perturbation of the model parameters with respect to the assumptions made during the quantizer design phase. We further examine the design algorithms to understand how sensitive the localization results will be with respect to the presence of the measurement noise.
1) Sensitivity of WDQ to Parameter Perturbation
We design WDQ with
Ri = 3 for each of the 100 different five-sensor configurations and test them under various types of mismatch conditions. In this experiment, a test set of 1,000 source locations is generated witha = 50 for each configuration by varying one of the model parameters. The simulation results are tabulated in Table 1. As seen in Table 1, WDQ shows robustness to mismatch situations where the parameters used in quantizer design are different from those characterizing the simulation conditions.2) Sensitivity of Design Algorithms to Noise Level
We design quantizers with
Ri = 3 for each of the 100 different five-sensor configurations by using various design algorithms. The localization errorE ∥θ - ∥2 is averaged over 100 configurations. We investigate the sensitivity to the noise level by generating a test set of 1,000 source locations for each configuration witha = 50 and the signal-to-noise ratio (SNR) in the range of 40–100 dB by varyingσ . Note that the SNR is computed using 10 log10a 2/σ 2 and measured at 1 m from the source. For example, SNR = 40 dB corresponds to SNR = 5.5 dB measured at each sensor location on average. For a practical vehicle target, it is often much higher than 40 dB. A typical value of the variance of measurement noiseσ 2 is 0.052 (=60 dB) [11, 16]. Fig. 3 shows that the proposed quantizer is as robust to the measurement noise as the other designs.In this paper, we proposed an iterative quantizer design algorithm optimized for distributed estimation. Since the goal was to design independently operating quantizers that minimized the global metric such as the estimation error, we suggested a weighted distance rule that allowed us to partition quantization regions so as to reduce the metric iteratively in the generalized Lloyd algorithm framework. We showed that the system-wide metric could be minimized for quantizer design by searching the optimal weights in a sequential manner, yielding a substantial reduction in computational complexity. The proposed algorithm was shown to perform quite well in comparison with typical standard designs and previous novel ones. Furthermore, we demonstrated that the proposed quantizer operated robustly to mismatches of the sensor model parameters. In the future, we will continue to work on novel quantizer design methodologies and their theoretical analysis for distributed systems.
-
[]
-
[]
-
[]
-
[]
-
[]
-
[]
-
[]
-
[Fig. 1.] Comparison of weighted distance-based quantizer (WDQ) with the uniform quantizer and the Lloyd quantizer: the average localization error in meters is plotted vs. the total rate (bits) consumed by five sensors.
-
[Fig. 2.] Comparison of weighted distance-based quantizer (WDQ) with novel design techniques: The average localization error in meters is plotted vs. the total rate (bits) consumed by five sensors with σ2 = 0 (left) and σ2 = 0.152 (right). LSQ: localization-specific quantizer, DOQ: distributed optimized quantizer.
-
[Table 1.] Localization error (LE) of weighted distance-based quantizer (WDQ) with Ri = 3 due to variations of the model parameters
-
[Fig. 3.] Sensitivity to noise level: the average localization error is plotted vs. signal-to-noise ratio (SNR) with M = 5, Ri = 3, and a = 50. LSQ: localization-specific quantizer, WDQ: weighted distance-based quantizer.