BEARS 2007: Wireless Foundations Poster Abstracts
- “Delay-Constrained Source Coding for a Peak Distortion Measure,” Cheng Chang and Anant Sahai
We consider the problem of lossy source coding under a peak distortion measure in which source symbols are revealed to the encoder in real time and need to be reconstructed by the decoder within a fixed end-to-end delay. Following the lossless case in [3], we investigate the tradeoff between end-to-end delay and the probability of distortion violation. As in the lossless case, the delay-constrained error (distortion-violation) exponent is generally much higher than the fixed-block coding case.
- “Network Coding for Distributed Storage Networks,” Alexandros G. Dimakis, P. Brighten Godfrey, Martin Wainwright and Kannan Ramchandran
Peer-to-peer distributed storage systems provide reliable access to data through redundancy spread over nodes across the Internet. A key goal is to minimize the amount of bandwidth used to maintain that redundancy. Storing a file using an erasure code, in fragments spread across nodes, promises to require less redundancy and hence less maintenance bandwidth than simple replication to provide the same level of reliability. However, since fragments must be periodically replaced as nodes fail, a key question is how to generate a new fragment in a distributed way while transferring as little data as possible across the network.
In this paper, we introduce a general technique to analyze storage architectures that combine any form of coding and replication, as well as presenting two new schemes for maintaining redundancy using erasure codes. First, we show how to optimally generate MDS fragments directly from existing fragments in the system. Second, we introduce a new scheme called Regenerating Codes which use slightly larger fragments than MDS but have lower overall bandwidth use. We also show through simulation that in realistic environments, Regenerating Codes can reduce maintenance bandwidth use by 25% or more compared with the best previous design---a hybrid of replication and erasure codes---while simplifying system architecture.
- “Geographic Gossip: Efficient Aggregation for Sensor Networks,” A.G. Dimakis, A.D. Sarwate, and M. Wainwright
Gossip algorithms for aggregation have recently received significant attention for sensor network applications because of their simplicity and robustness in noisy and uncertain environments. However, gossip algorithms can waste significant energy by essentially passing around redundant information multiple times. Specifically, for realistic sensor network model topologies like grids and random geometric graphs, the inefficiency of gossip schemes is caused by slow mixing times of random walks on those graphs. We propose and analyze an alternative gossiping scheme that exploits geographic information. By utilizing a simple resampling method, we can demonstrate substantial gains over previously proposed gossip protocols. In particular, for random geometric graphs, our algorithm computes the true average to accuracy 1/na using O(n{1.5}√ log n) radio transmissions, which reduces the energy consumption by a √n/log n factor over standard gossip algorithms.
- “A New Approach to Encoding and Decoding Under Varying Sampling Rate,” Lara Dolecek and Venkat Anantharam
The current trends in digital data storage applications demand higher storage capacity and higher data rates while keeping the disk size the same. To fully benefit from advanced coding and signal processing techniques available to meet these demands, timing recovery must be performed under increasingly more stringent constraints. Sampling errors caused by poor timing recovery, such as repetitions or deletions of symbols, severely impact the decoder's performance and can undermine the benefits of other system components. As an alternative to these more complex and more expensive timing recovery schemes, we adopt a coding theoretic point of view in addressing this problem. We investigate how to modify codes of practical interest, such as LDPC codes, to ensure that they would, in addition to excellent additive error correction properties, be equipped with good synchronization error correction capabilities. In particular, we have proposed a technique to thin array-based LDPC codes with only a small loss in the rate, such that the resulting thinned code is immune to additive errors as well a synchronization error. We also proposed a modified message passing decoding algorithm for these codes and appropriate for the channels in which, in addition to additive errors, a synchronization error can also occur. The proposed decoding algorithm has the same complexity as the standard message passing algorithm used to decode LDPC codes over channels with additive noise. We are currently generalizing our proposed techniques to include more general families of codes as well as multiple synchronization error correction capability.
- “Analysis of Absorbing Sets of LDPC Codes,” Lara Dolecek, Zhengya Zhang, Venkat Anantharam, Borivoje Nikolic and Martin Wainwright
Low density parity check codes (LDPC) are known to perform very well under iterative decoding in the moderate bit error rate (BER) region. However, these codes also exhibit a change in the slope of the BER vs. signal to noise ratio (SNR) curve in the very low BER region (termed error floor), a region which is of interest for many practical applications. Since this region is out of reach of pure software simulations, in general very little is known about the causes of this behavior, and consequently wider deployment of LDPC codes in such applications is still limited. We have experimentally observed that certain structures, which we call absorbing sets, intrinsic to the parity check matrix of a given code, are the dominant causes of the errors in the very low BER region. In this project we study absorbing sets of the smallest size (which are shown experimentally to dominate low BER performance) for various LDPC constructions. We have already described in detail the smallest a bsorbing sets for high rate array-based LDPC codes and showed how their number scales with the codeword length. By performing a comprehensive analysis of such structures, the goal is to gain a deeper understanding of why LDPC codes perform the way they do in the low BER region. This understanding will in turn lead to addressing the questions of how to design better LDPC codes (or improve existing ones) and how to analytically predict their low BER performance, both of which are presently largely unanswered.
- “Reliable Communication in the Presence of a Primary ARQ System,” Krish Eswaran, Michael Gastpar and Kannan Ramchandran
While the majority of spectrum currently gets allocated for specific systems with a specific use, one hope is that certain parts of the spectrum can be reused by cognitive radio systems. These cognitive radios must reuse the spectrum in such a way that a primary system for which the spectrum was originally allocated continues to function. Given this restriction, the cognitive radio wants to achieve the maximum allowable throughput.
We study a problem motivated by cognitive radio in which the primary is a packet system that employs ARQ feedback in its design. In order for the primary to achieve a specified target rate, the secondary must transmit within an interference budget. Realistically, the
interference budget is unknown to the secondary. Absent this knowledge, we propose a scheme in which the secondary can stay within its interference budget through the primary's ARQ feedback. Under certain assumptions, we show there exists an information-theoretically optimal rate-interference budget (RIB) tradeoff. We compare how far fixed strategies are from this RIB function as we vary the interference budget. Further, we exhibit a strategy that is optimal beyond a threshold interference budget and within 1 bit per primary packet elsewhere.
- “Fundamental Limits of Broadcasting in Wireless Networks,” Birsen Serkeci Mergen
Many network protocols rely on the broadcast of certain control messages to the entire network. Traditional broadcasting schemes have been designed based on criteria such as minimizing the total number of transmissions and the energy consumption. Recently, physical layer cooperative schemes have been shown to offer several advantages over the network layer approaches. This form of cooperation employs distributed transmission resources at the physical layer as a single radio with spatial diversity. In this work, we are interested in designing broadcasting schemes with high data transfer rate. At first, we determine upper bounds to the broadcast capacity, i.e. the maximum data transfer rate from a given node to every other node in a relay network. We then propose cooperative broadcasting schemes that approach these bounds and show that they provide superior performance compared to traditional multi-hop communication.
- “Computation Over Multiple-Access Channels,” Bobak Nazer
Computation and communication are often treated as wholly separate problems. A communications engineer, tasked to design a multi-user system for performing computations while facing communications constraint, would almost certainly employ a version of the "separation principle." We consider the problem of computing functions over multiple-access channels (MACs) and show that in many cases of interest, a joint design can exploit a match between the structure of the channel and the function to be computed. In many cases of interest, a MAC output is a (deterministic) function of its inputs, corrupted by noise. By using structured source and channel codes, we can convert such a MAC into a reliable computation system. This structural gain does not hinge on the correlations between the sources and, with a perfect matching, increases the computation rate proportionally to the number of users. Furthermore, our underlying schemes are modular and depend primarily on coding techniques originally developed for their lower complexity.
- "The Source Coding Game with a Cheating Switcher," Harikrishna Palaiyanur
Berger’s paper ‘The Source Coding Game’, IEEE Trans. Inform. Theory, 1971, considers the problem of finding the rate-distortion function for an adversarial source comprised of multiple known IID sources. The adversary, called the ‘switcher’, was allowed only causal access to the source realizations and the rate-distortion function was obtained through the use of a type covering lemma. In this paper, the rate-distortion function of the adversarial source is described, under the assumption that the switcher has non-causal access to all source realizations. The proof utilizes the type covering lemma and simple conditional, random ‘switching’ rules. The rate-distortion function is once again the maximization of the R(D) function for a region of attainable IID distributions.
- “Channels with Nosy "Noise",” Anand D. Sarwate and Michael Gastpar
Communication models in which the transmitted codeword is corrupted by a jammer are studied. The assumptions on the jammer are that it can base its attack on the actual transmitted codeword, but is restricted by a cost constraint. Within this framework it is shown that if a small random secret, or key, is made available to the encoder and decoder, the maximum reliable rate of communication is the same as if the jammer did not know the transmitted codeword. As a step in the proof, list-decodable codes with list size L are shown to achieve rates within L-1 of the capacity.
- “On Compression of Encrypted Video,” Daniel Schonberg
We consider video sequences that have been encrypted uncompressed. Since encryption masks the source, traditional data compression algorithms are rendered ineffective. However, it has been shown that through the use of distributed source-coding techniques, the compression of encrypted data is in fact possible. This means that it is possible to reduce data size without requiring that the data be compressed prior to encryption. Indeed, under some reasonable conditions, neither security nor compression efficiency need be sacrificed when compression is performed on the encrypted data (Johnson et al., 2004).
In this paper we develop an algorithm for the practical lossless compression of encrypted gray scale video. Our method is based on considering the temporal correlations in video. This move to temporal dependence builds on our previous work on memoryless sources, and one- and two-dimensional Markov sources. For comparison, a motion-compensated lossless video encoder can compress each unencrypted frame of the standard ``Foreman'' test video sequence by about 57%. Our algorithm can compress the same frames, after encryption, by about 33%.
- "Prediction and Modeling for the Ultra-Wideband Channel," Jonathan Tsao, Dana Porrat, David Tse
We conduct a feasibility study of UWB channel prediction to answer the following two questions: Is the UWB channel predictable? Is UWB channel prediction useful? We setup the problem in the following way: A receiver travels along a linear trajectory at a constant velocity. The transmitter and environment are stationary. Using past channel measurements, the receiver predicts future measurements of the channel, assuming its direction of movement and velocity remain constant.
Our approach is to decompose the time evolution of the channel, which is jointly correlated in time and delay, in terms of the time evolution of individual paths, which are independent across delay. A measurement campaign was conducted in the Berkeley Wireless Research Center (BWRC) library, where measurements were taken with line of sight (LOS) and non line of sight (NLOS) conditions. We develop a channel prediction algorithm, and evaluate results in terms of the matched filter output energy (MFOE). AIterating through the six strongest paths, our prediction algorithm achieves more than 70\% (40\%) of the possible MFOE over a prediction distance of 34~cm for the LOS (NLOS) conditions. These results are good as the coherence distance, distance for which the channel is approximately constant, is less than 1 cm.
- “Distributed Sparse Random Projections for Compressible Sensor Data,” Wei Wang, Minos Garofalakis, and Kannan Ramchandran
Suppose a large-scale wireless sensor network measures data which is compressible, so that n real data values can be well-approximated using only k coefficients in an appropriate transform domain (where k<n). We address the problem of recovering an approximation of the n data values by querying any k + m sensors, where m is the overhead cost to be determined. To solve this problem, we present an efficient distributed algorithm based on sparse random projections. Our distributed algorithm has the property that the encoding is blind to the compressing transform and the data model (including knowledge of k). Only the decoder needs to know this information, which it uses to query and reconstruct in polynomial time. Sensors act independently and randomly, and thus our algorithm is completely decentralized and robust.
- “Robust Distributed Multi-View Video Compression for Wireless Camera Networks,”
Chuohao Yeo and Kannan Ramchandran
We are investigating the use of inter-view correlation between cameras with overlapping views for delivering error-resilient video in a distributed fashion for wireless camera networks. The main focus in this work is on robustness which is imminently needed in a wireless setting. Our current system has low encoding complexity, is robust under tight latency constraints, and requires no inter-sensor communications. Decoder motion search, which has been successfully employed for single-camera distributed compression in PRISM (Power-efficient Robust hIgh-compression Syndrome-based Multimedia coding), is extended to the multi-view setting to include decoder disparity search based on two-view camera geometry. We are also exploring the use of scene depth information when it is available. In particular, dense stereo correspondence and view synthesis are utilized as an alternative way of generating side-information. The proposed PRISM-MC achieved PSNR gains of up to 1.7 dB over simulcast solutions in experiments conducted with a wireless channel simulator.
