CompressionGroup/DSNProject

From WikiBiron
Revision as of 10:07, 22 July 2005 by Ciancio (talk | contribs)

Distributed Energy-Efficient Wavelet Compression Algorithms for Wireless Mutihop Sensor Networks

Low cost programmable sensors can be deployed in the environment to perform a variety of coordinated tasks, such as object tracking, environment monitoring/ surveillance and control. The fast development and decreasing cost of wireless technologies have made sensor networks a key technology for the future, and led to substantial interest on distributed algorithms targeted at these networks.

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.

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





Retrieved from "https://biron.usc.edu/wiki/index.php?title=CompressionGroup/DSNProject&oldid=94"