Resultados de la búsqueda45 resultados
-
On Network Correlated Data Gathering
Cristescu, R.; Beferull-Lozano, B.; Vetterli, M.
(2004). ArticleWe consider the problem of correlated data gathering by a network with a sink node and a tree communication structure, where the goal is to minimize the total transmission cost of transporting the information collected by the nodes, to the sink node. Two coding strategies are analyzed: a Slepian-Wolf model where optimal coding is complex and transmission optimization is simple, and a joint entropy coding model with explicit communication where coding is simple and transmission optimization is difficult. This problem requires a joint optimization of the rate allocation at the nodes and of the transmission structure. For the Slepian-Wolf setting, we derive a closed form solution and an...
We consider the problem of correlated data gathering by a network with a sink node and a tree communication structure, where the goal is to minimize the total transmission cost of transporting the information collected by the nodes, to the sink node. Two coding strategies are analyzed: a Slepian-Wolf model where optimal coding is complex and transmission optimization is simple, and a joint entropy coding model with explicit communication where coding is simple and transmission optimization is difficult. This problem requires a joint optimization of the rate allocation at the nodes and of the transmission structure. For the Slepian-Wolf setting, we derive a closed form solution and an efficient distributed approximation algorithm with a good performance. For the explicit communication case, we prove that building an optimal data gathering tree is NP-complete and we propose various distributed approximation algorithms.
Leer más Ocultar -
Scaling Laws for Correlated Data Gathering
Cristescu, R.; Beferull-Lozano, B.; Vetterli, M.
(2004). ArticleConsider a set of correlated sources located at the nodes of a network, and a sink to which the data from all the sources have to arrive. We address the minimization of a separable joint communication cost function given by the product [rate] o [edge weight]. We present two possible approaches for rate allocation, namely Slepian-Wolf coding, and coding by explicit communication, and compare asymptotically (large networks) the associated total costs by finding their corresponding scaling laws and analyzing the ratio between them. We also provide the specific conditions on the correlation structure which determine the different cases of asymptotic behaviors.
-
Oversampled A/D Conversion of Non-Bandlimited Signals with Finite Rate of Innovation
Jovanovic, I.; Befferull-Lozano, B.
(2004). ArticleWe consider the problem of A/D conversion for non-bandlimited signals that have a finite rate of innovation, in particular, the class of a continuous periodic stream of Diracs, characterized by a set of time positions and weights. Previous research has only considered the sampling of these signals, ignoring quantization which is necessary for any practical application (e.g. UWB, CDMA). In order to achieve accuracy under quantization, we introduce two types of oversampling, namely, oversampling in frequency and oversampling in time. High accuracy is achieved by enforcing the reconstruction to satisfy either three convex sets of constraints related to (1) sampling kernel, (2) quantization and...
We consider the problem of A/D conversion for non-bandlimited signals that have a finite rate of innovation, in particular, the class of a continuous periodic stream of Diracs, characterized by a set of time positions and weights. Previous research has only considered the sampling of these signals, ignoring quantization which is necessary for any practical application (e.g. UWB, CDMA). In order to achieve accuracy under quantization, we introduce two types of oversampling, namely, oversampling in frequency and oversampling in time. High accuracy is achieved by enforcing the reconstruction to satisfy either three convex sets of constraints related to (1) sampling kernel, (2) quantization and (3) periodic streams of Diracs, which is then said to provide strong consistency, or only the first two, providing weak consistency. We propose three reconstruction algorithms, the first two achieving weak consistency and the third one achieving strong consistency. For these three algorithms, respectively, the experimental MSE performance for time positions decreases as O(1/Rt2 Rf3), and O(1/Rt2 Rf4), where Rt and Rf are the oversampling ratios in time and in frequency, respectively. It is also proved theoretically that our reconstruction algorithms satisfying weak consistency achieve an MSE performance of at least O(1/Rt2 Rf3).
Leer más Ocultar -
Error-Rate Dependence of Non-Bandlimited Signals with Finite Rate of Innovation
Jovanovic, I.; Beferull-Lozano, B.
(2004). ArticleRecent results in sampling theory [M. Vetterli et al., (2002)] showed that perfect reconstruction of nonbandlimited signals with finite rate of innovation can be achieved performing uniform sampling at or above the rate of innovation. We study analog-to-digital (A/D) conversion of these signals, introducing two types of oversampling and consistent reconstruction.
-
Power-Efficient Sensor Placement and Transmission Structure for Data Gathering under Distortion Constraints
Ganesan, D.; Cristescu, R.; Beferull-Lozano, B.
(2004). ArticleWe consider the joint optimization of sensor placement and transmission structure for data gathering, where a given number of nodes need to be placed in a field such that the sensed data can be reconstructed at a sink within specified distortion bounds while minimizing the energy consumed for communication. We assume that the nodes use joint entropy coding based on explicit communication between sensor nodes, and consider both maximum and average distortion bounds. The optimization is complex since it involves an interplay between the spaces of possible transmission structures given radio reachability limitations, and feasible placements satisfying distortion bounds. We address this problem...
We consider the joint optimization of sensor placement and transmission structure for data gathering, where a given number of nodes need to be placed in a field such that the sensed data can be reconstructed at a sink within specified distortion bounds while minimizing the energy consumed for communication. We assume that the nodes use joint entropy coding based on explicit communication between sensor nodes, and consider both maximum and average distortion bounds. The optimization is complex since it involves an interplay between the spaces of possible transmission structures given radio reachability limitations, and feasible placements satisfying distortion bounds. We address this problem by first looking at the simplified problem of optimal placement in the one-dimensional case. An analytical solution is derived for the case when there is a simple aggregation scheme, and numerical results are provided for the cases when joint entropy encoding is used. We use the insight from our 1-D analysis to extend our results to the 2-D case, and show that our algorithm for two-dimensional placement and transmission structure provides significant power benefit over a commonly used combination of uniformly random placement and shortest path trees.
Leer más Ocultar -
Sub-gaussian rotation-invariant features for steerable wavelet-based image retrieval
Tzagkarakis, G.; Beferull-Lozano, B.; Tsakalides, P.
(2004). ArticleThis paper presents a new rotation-invariant image retrieval method, which extends a recently introduced classification technique based on steerable wavelet transforms. In the proposed procedure, the feature extraction step consists of estimating the covariations (lower-order cross-correlations) between the wavelet subband coefficients, which are modeled as subGaussian random vectors. The similarity measurement is carried out first by employing norms calculating the distance between the covariation matrices representing two distinct images and second by evaluating the Kullback-Leibler Distance (KLD) between their corresponding subGaussian distributions. We provide analytical expressions...
This paper presents a new rotation-invariant image retrieval method, which extends a recently introduced classification technique based on steerable wavelet transforms. In the proposed procedure, the feature extraction step consists of estimating the covariations (lower-order cross-correlations) between the wavelet subband coefficients, which are modeled as subGaussian random vectors. The similarity measurement is carried out first by employing norms calculating the distance between the covariation matrices representing two distinct images and second by evaluating the Kullback-Leibler Distance (KLD) between their corresponding subGaussian distributions. We provide analytical expressions relating the subGaussian features corresponding to a rotated image from the features of the original image. Finally, we relate the employed optimal lower-order correlation (p≤2) to the degree of nonGaussianity of the wavelet coefficients, and we demonstrate the effectiveness of our method using real texture images.
Leer más Ocultar -
Lattice Sensor Networks: Capacity Limits, Optimal Routing and Robustness to Failures
Barreneche, G.; Beferull-Lozano, B.; Vetterli, M.
(2004). ArticleWe study network capacity limits and optimal routing algorithms for regular sensor networks, namely, square and torus grid sensor networks, in both, the static case (no node failures) and the dynamic case (node failures). For static networks, we derive upper bounds on the network capacity and then we characterize and provide optimal routing algorithms whose rate per node is equal to this upper bound, thus, obtaining the exact analytical expression for the network capacity. For dynamic networks, the unreliability of the network is modeled in two ways: a Markovian node failure and an energy based node failure. Depending on the probability of node failure that is present in the network, we...
We study network capacity limits and optimal routing algorithms for regular sensor networks, namely, square and torus grid sensor networks, in both, the static case (no node failures) and the dynamic case (node failures). For static networks, we derive upper bounds on the network capacity and then we characterize and provide optimal routing algorithms whose rate per node is equal to this upper bound, thus, obtaining the exact analytical expression for the network capacity. For dynamic networks, the unreliability of the network is modeled in two ways: a Markovian node failure and an energy based node failure. Depending on the probability of node failure that is present in the network, we propose to use a particular combination of two routing algorithms, the first one being optimal when there are no node failures at all and the second one being appropriate when the probability of node failure is high. The combination of these two routing algorithms defines a family of randomized routing algorithms, each of them being suitable for a given probability of node failure.
Leer más Ocultar -
Rate-Distortion Problem for Physics Based Distributed Sensing
Beferull-Lozano, B.; Konsbruck, Robert L.; Vetterli, M.
(2004). ArticleWe consider the rate-distortion problem for sensing the continuous space-time physical temperature in a circular ring on which a heat source is applied over space and time, and which is also allowed to cool by radiation or convection to its surrounding medium. The heat source is modelled as a continuous space-time stochastic process which is bandlimited over space and time. The temperature field is the result of a circular convolution over space and a continuous-time causal filtering over time of the heat source with the Green's function corresponding to the heat equation, which is space and time invariant. The temperature field is sampled at uniform spatial locations by a set of sensors...
We consider the rate-distortion problem for sensing the continuous space-time physical temperature in a circular ring on which a heat source is applied over space and time, and which is also allowed to cool by radiation or convection to its surrounding medium. The heat source is modelled as a continuous space-time stochastic process which is bandlimited over space and time. The temperature field is the result of a circular convolution over space and a continuous-time causal filtering over time of the heat source with the Green's function corresponding to the heat equation, which is space and time invariant. The temperature field is sampled at uniform spatial locations by a set of sensors and it has to be reconstructed at a base station. The goal is to minimize the mean-square-error per second, for a given number of nats per second, assuming ideal communication channels between sensors and base station. We find a) the centralized Rc (D) function of the temperature field, where all the space-time samples can be observed and encoded jointly. Then, we obtain b) the Rs-i (D) function, where each sensor, independently, encodes its samples optimally over time and c) the Rst-i (D) function, where each sensor is constrained to encode also independently over time. We also study two distributed prediction-based approaches: a) with perfect feedback from the base station, where temporal prediction is performed at the base station and each sensor performs differential encoding, and b) without feedback, where each sensor locally performs temporal prediction.
Leer más Ocultar -
Nested trellis codes and shaping for the transmitter side information problem
Beferull-Lozano, B.; Diggavi, S.
(2003). ArticleIn this paper, we specifically focus on the problem of power shaping and we examine nested constructions based on trellis codes, which build on simple low dimensional lattices. We propose the idea of performing shaping through a coarse lattice (source code) and we also show how this method can actually be combined with shaping through a fine lattice (channel code) so that a joint shaping can be performed by the fine and coarse lattices in the communication channel with transmitter side-information simultaneously.
-
Efficient Quantization for Overcomplete Expansions in R^n
Beferull-Lozano, B.; Ortega, A.
(2003). ArticleWe study construction of structured regular quantizers for overcomplete expansions in RN. Our goal is to design structured quantizers which allow simple reconstruction algorithms with low complexity and which have good performance in terms of accuracy. Most related work to date in quantized redundant expansions has assumed that the same uniform scalar quantizer was used on all the expansion coefficients. Several approaches have been proposed to improve the reconstruction accuracy, with some of these methods having significant complexity. Instead, we consider the joint design of the overcomplete expansion and the scalar quantizers (allowing different step sizes) in such a way as to produce...
We study construction of structured regular quantizers for overcomplete expansions in RN. Our goal is to design structured quantizers which allow simple reconstruction algorithms with low complexity and which have good performance in terms of accuracy. Most related work to date in quantized redundant expansions has assumed that the same uniform scalar quantizer was used on all the expansion coefficients. Several approaches have been proposed to improve the reconstruction accuracy, with some of these methods having significant complexity. Instead, we consider the joint design of the overcomplete expansion and the scalar quantizers (allowing different step sizes) in such a way as to produce an equivalent vector quantizer (EVQ) with periodic structure. The construction of a periodic quantizer is based on lattices in RN and the concept of geometrically scaled- similar sublattices. The periodicity makes it possible to achieve good accuracy using simple reconstruction algorithms (e.g., linear reconstruction or a small lookup table).
Leer más Ocultar
