GraphWavelets

From WikiBiron
Revision as of 20:09, 8 July 2011 by Sunil (talk | contribs)

Wavelet Filterbanks for Graph based Data

In this work we propose the construction of two-channel wavelet filterbanks for analyzing functions defined on the vertices of any arbitrary finite weighted undirected graph. These graph based functions are referred to as graph-signals as we build a framework in which many concepts from the classical signal processing domain, such as Fourier decomposition, signal filtering and downsampling can be extended to graph domain. Especially, we observe a spectral folding phenomenon in bipartite graphs which occurs during downsampling of these graphs and produces aliasing in graph signals. We propose quadrature mirror filters on graph (referred to as graph-QMF) for bipartite graph which cancel aliasing and lead to perfect reconstruction. For arbitrary graphs we present a bipartite subgraph decomposition which produces an edge-disjoint collection of bipartite subgraphs. Graph-QMFs are then constructed on each bipartite subgraph leading to multi-dimensional separable wavelet filterbanks on graphs. Our proposed filterbanks are critically sampled and we state necessary and sufficient conditions for orthogonality, aliasing cancellation and perfect reconstruction. The filterbanks are realized by Chebychev polynomial approximations.

Assume that a number of power-constrained sensors are spr\-ead over an area, acquiring data, e.g., temperature measurements. An estimate of the temperature in each point of that area is to be made available at a central node (sink) based on transmissions from the sensors. Each sensor is capable of transmitting data only over a small distance. Communication is done via data hoping, where data from each sensor is forwarded (using other sensors as relay stations) until it reaches the target node. Such a network is referred to as a multihop network.

A simple and naive design would be for each sensor to just transmit a quantized version of its own measurement to the central node. However, this approach would not be exploiting the fact that measurements originated from spatially close sensors are likely to be correlated, and energy would be wasted with the transmission of redundant data to the central node. As an alternative, since data is correlated, it would be reasonable to use some sort of transform as a means to decorrelate the information from sensors, and, therefore, represent the measurements using fewer bits.

Servetto and Gastpar have proposed the use of distributed transforms to decorrelate data. A main drawback of those algorithms is that in a power constrained sensor network scenario, transmission costs account for most (if not all) the energy consumption. Distributed algorithms that rely on a potentially large number of intersensor communications, or do not take into account communication costs as a function of the number of bits and the distances over which bits are transmitted, might in the end be elevating power consumption to unacceptable levels. For example, in the case of distributed wavelet algorithms, the amount of necessary data exchanges and the degree of decorrelation achieved are directly related to the number of levels of decompositions used. Depending on the network properties (data correlation, distances between sensors, etc), a specific number of decompositions may perform better.

Distributed implementation of the wavelet transform poses several challenges. First, if the filters contain anticausal terms, sensors would be required to transmit data backwards (i.e., away from the sink instead of towards the sink) or alternatively to send uncompressed data forward. Second, any data transmitted back and forth over the network has to be quantized, since tramsmissions at full precision can substantialy increase energy consumption, affecting the final performance. In this project we develop a distributed wavelet transform algorithm to decorrelate data as it flows through the network. We eliminate unnecessary transmissions by calculating partial approximations of the wavelet coefficients based on the available data at each sensor. The coefficients are refined at future nodes, as data is forwarded to the sink. We also address the impact of data quantization on the final distortion. We derive an upper bound to the resulting extra distortion introduced by quantization in terms of the bits allocated to the partial data, and use it as a tool to design the quantizers so the extra distortion is within a given threshold.

We then address the scenario where energy-constrained sensors in a wireless sensor network can choose among different distributed coding schemes to encode their data. We propose a framework where the network is described as a graph, with sensors representing the nodes, and where communication and processing costs are associated to edge weights and the coding schemes associated to states of operation. After carefully describing data transitions and edge costs, we show that a shor\-test-path algorithm can be used to find the optimum network configuration, i.e., the one that leads to the lowest overall energy.

Our methods discussed above apply when the transform is performed along a single path (ergo, no overlapping paths). Naturally, this breaks down when applying this transform along more general routing trees that have overlapping paths. To address this problem, we propose a wavelet transform that can be computed along an arbitrary routing tree using wavelet lifting. This eliminates the need for costly heuristics to merge overlapping 1D transforms. The transform is critically sampled, exploits data correlation across adjacent paths, and is computed in a unidirectional manner to avoid incurring additional costs for backward transmissions found in existing 2D transforms. An optimization technique (analogous to that in our previous work) is then developed for our proposed tree based transform to select the number of levels of decomposition at each node that results in minimum cost. We also propose a method for joint transform and routing optimization using our tree based transform to exploit a trade-off between high inter-node data correlation (for good compression efficiency) and low total distance to route to the sink (for low total routing cost).

More detailed information about this project can be found in the publications below.



Distributed compression algorithms for quantizer design, encoding of quantized data and source localization in sensor networks

In sensor networks, multiple correlated observations are available from many sensors that can sense, compute and communicate. Often these sensors are battery-powered and operate under strict limitations on wireless communication bandwidth. This motivates the use of data compression in the context of various tasks such as detection, classification, localization and tracking, which require data exchange between sensors. The basic strategy for reducing the overall energy usage in the sensor network would then be to decrease the communication cost at the expense of additional computation in the sensors. One important sensor collaboration task with broad applications is source localization. Since practical systems will require quantization of the observations before transmission, different quantizer designs should be compared in terms of localization error.

In the project, we consider the effect of quantization on source localization and provide distributed algorithms for quantizer design, encoding of quantized data and localization based on them, to achieve good data compression.

More detailed information about this project can be found in the publications below.



  • Publications
    • G. Shen and A. Ortega, "Transform-based Distributed Data Gathering". To Appear in IEEE Transactions on Signal Processing. arXiv:0909.5177v3
    • S.K. Narang, G. Shen and A. Ortega, "Unidirectional Graph-based Wavelet Transforms for Efficient Data Gathering in Sensor Netowkrs". IEEE International Conference on Acoustic, Speech and Signal Processing (ICASSP'10), Dallas, April 2010.
    • S. Lee, S. Pattem, M. Sathiamoorthy,B. Krishnamachari, and A. Ortega "Spatially-Localized Compressed Sensing and Routing in Multi-hop Sensor Networks". In Proceedings of Third International Conference on Geosensor Networks (GSN'09), Oxford, July 2009. PDF format
    • P. Tarrio, G. Valenzise, G. Shen and A. Ortega, "Distributed Network Configuration for Wavelet-based Compression in Sensor Networks". Third International Conference on Geosensor Networks (GSN'09), Oxford, Jul 2009. PDF format
    • G. Shen, S. Pattem and A. Ortega, "Energy-efficient Graph-based Wavelets for Distributed Coding in Wireless Sensor Networks". IEEE International Conference on Acoustic, Speech and Signal Processing (ICASSP'09), Taipei, Apr 2009. PDF format
    • G. Shen, S. Narang and A. Ortega, "Adaptive Distributed Transforms for Irregularly Sampled Wireless Sensor Networks". IEEE International Conference on Acoustic, Speech and Signal Processing (ICASSP'09), Taipei, Apr 2009. PDF format
    • S. Pattem, G. Shen, Y. Chen, B. Krishnamachari and A. Ortega, "SenZip: An Architecture for Distributed En-route Compression in Wireless Sensor Networks". In Workshop on Sensor Networks for Earth and Space Science Applications (ESSA'09), San Francisco, Apr 2009. PDF format
    • G. Shen and A. Ortega, "Joint Routing and 2D Transform Optimization for Irregular Sensor Network Grids Using Wavelet Lifting". International Symposium on Information Processing in Sensor Networks (IPSN'08), St. Louis, Apr 2008. PDF format
    • G. Shen and A. Ortega, "Optimized Distributed 2D Transforms for Irregularly Sampled Sensor Network Grids Using Wavelet Lifting". IEEE International Conference on Acoustic, Speech and Signal Processing (ICASSP'08), Las Vegas, Apr 2008. PDF format
    • A. Ciancio and A. Ortega, "Energy Efficient Data-Representation and Routing for Wireless Sensor Networks Based on a Distributed Wavelet Compression Algorithm". International Symposium on Information Processing in Sensor Networks (IPSN'06), Nashville, Apr 2006. PDF format
    • A. Ciancio and A. Ortega, "A Dynamic Programming Approach to Distortion-Energy Optimization for Distributed Wavelet Compression With Applications to Data Gathering in Wireless Sensor Networks". IEEE International Conference on Acoustic, Speech and Signal Processing (ICASSP'06), Toulouse, France, May 2006. PDF format
    • Y. H. Kim and A. Ortega, "Maximum A Posteriori (MAP)-Based Algorithm for Distributed Source Localization using Quantized Acoustic Sensor Readings". IEEE International Conference on Acoustic, Speech and Signal Processing (ICASSP'06), Toulouse, France, May 2006. PDF format
    • A. Ciancio and A. Ortega, "Energy Consumption Optimization in Wireless Sensor Networks Using Dynamic Programming (Work-in-progess)". International Symposium on Information Processing in Sensor Networks (IPSN'05), Los Angeles, Apr 2005. PDF format
    • A. Ciancio and A. Ortega,"Distributed Wavelet Compression Algorithm for Wireless Multihop Sensor Networks Based on Lifting". International Conference on Acoustics, Speech and Signal Processing (ICASSP'05), Philadelphia, Mar 2005. PDF format
    • Y. H. Kim and A. Ortega, "Quantizer Design for Source localization in Sensor Networks". IEEE International Conference on Acoustic, Speech and Signal Processing (ICASSP'05), Philadelphia, March 2005. PDF format
    • Y. H. Kim and A. Ortega, "Quantizer Design and Distributed Encoding Algorithm for Source Localization in Sensor Networks". International Symposium on Information Processing in Sensor Networks (IPSN'05), Los Angeles, April 2005. PDF format
    • A. Ciancio and A. Ortega,"Distributed Wavelet Compression Algorithm for Wireless Sensor Networks Based on Lifting", International Conference on Acoustics, Speech and Signal Processing (ICASSP'04), Montreal, May 2004. PDF format


  • People



  • Related Links



  • Acknowledgements
    • This work was supported in part by NASA under grant AIST-05-0081
Retrieved from "https://biron.usc.edu/wiki/index.php?title=GraphWavelets&oldid=1925"