Hybrid numerical scheme for time-evolving wave fields

Many problems in geophysics, acoustics, elasticity theory, cancer treatment, food process control and electrodynamics involve study of wave field synthesis (WFS) in some form or another. In the present work, modelling of wave propagation phenomena is studied as a static problem, using finite element method and treating time as an additional spatial dimension. In particular, WFS problems are analysed using discrete methods. It is shown that a fully finite element-based scheme is very natural and effective method for the solution of such problems. Distributed WFS in the context of two-dimensional problems is outlined and incorporation of any geometric or material non-linearities is shown to be straightforward. This has significant implications for problems in geophysics or biological media, where material inhomogeneities are quite prevalent. Numerical results are presented for several problems referring to media with material inhomogeneities and predefined absorption profiles. The method can be extended to three-dimensional problems involving anisotropic media properties in a relatively straightforward manner. Copyright © 2006 John Wiley & Sons, Ltd.     

Broadcast Channels With Cooperating Decoders

We consider the problem of communicating over the general discrete memoryless broadcast channel (DMBC) with partially cooperating receivers. In our setup, receivers are able to exchange messages over noiseless conference links of finite capacities, prior to decoding the messages sent from the transmitter. In this paper, we formulate the general problem of broadcast with cooperation. We first find the capacity region for the case where the BC is physically degraded. Then, we give achievability results for the general broadcast channel, for both the two independent messages case and the single common message case     

On the Interdependence of Routing and Data Compression in Multi-Hop Sensor Networks

We consider a problem of broadcast communication in sensor networks, in which samples of a random field are collected at each node, and the goal is for all nodes to obtain an estimate of the entire field within a prescribed distortion value. The main idea we explore in this paper is that of jointly compressing the data generated by different nodes as this information travels over multiple hops, to eliminate correlations in the representation of the sampled field. Our main contributions are: (a) we obtain, using simple network flow concepts, conditions on the rate/distortion function of the random field, so as to guarantee that any node can obtain the measurements collected at every other node in the network, quantized to within any prescribed distortion value; and (b) we construct a large class of physically-motivated stochastic models for sensor data, for which we are able to prove that the joint rate/distortion function of all the data generated by the whole network grows slower than the bounds found in (a). A truly novel aspect of our work is the tight coupling between routing and source coding, explicitly formulated in a simple and analytically tractable model – to the best of our knowledge, this connection had not been studied before.     

Algorithmic Aspects of the Time Synchronization Problem in Large-Scale Sensor Networks

We study the time synchronization problem for large-scale wireless sensor networks in the high-density regime. Our interest in this problem arises from a sensor networking application, where a large number of power-constrained radio transmitters coordinate their access to a Gaussian multiple access channel to cooperate in generating a waveform stronger than any individual node would be able to generate. In a companion paper to this one, we study theoretical aspects of a time synchronization mechanism that is optimal in the limit of asymptotically high network densities. In this work we summarize those results, and explore practical implementation issues of that mechanism in the context of networks with large, but finite, numbers of nodes. Through simulations, we find that the synchronization mechanism performs very well for finite (and relatively small) networks, maintaining tight clock synchronization indefinitely.Work supported by the National Science Foundation, under awards CCR- 0238271 (CAREER), CCR-0330059, and ANR-0325556. An-swol Hu was born in Mt. Kisco, New York on February 24, 1980. He received his B.S. in Electrical Engineering from Stanford University in 2002. Currently he is a Ph.D. candidate in the School of Electrical and Computer Engineering at Cornell University. His research interests include information theory and statistical signal processing, with applications to sensor networks. Sergio D. Servetto was born in Argentina, on January 18, 1968. He received a Licenciatura en Informática from Universidad Nacional de La Plata (UNLP, Argentina) in 1992, and the M.Sc. degree in Electrical Engineering and the Ph.D. degree in Computer Science from the University of Illinois at Urbana-Champaign (UIUC), in 1996 and 1999. From 1991 to 1994 he worked as a programmer for IBM Argentina. From 1994 to 1999 he was a Graduate Research Assistant at UIUC. From 1999 to 2001 he worked at the Ecole Polytechnique Fédérale de Lausanne (EPFL), Switzerland. Since Fall 2001, he has been an Assistant Professor in the School of Electrical and Computer Engineering, Cornell University. He is also a member of the field of Applied Mathematics at Cornell. His research interests are centered around information theoretic aspects of networked systems, with a current emphasis on problems that arise in the context of large-scale sensor networks.Sergio was the recipient of the 1998 Ray Ozzie Fellowship, given to “outstanding graduate students in Computer Science”, and of the 1999 David J. Kuck Outstanding Thesis Award, for the best doctoral dissertation of the year, both from the Dept. of Computer Science at UIUC. He is also the recipient of a 2003 NSF CAREER Award. He has served on the technical program committee of various conferences (IEEE Infocom, Globecom, ICC, SECON; ACM MobiCom, MobiHoc, SenSys, WSNA). He will present a tutorial at ACM MobiHoc 2004, on the topic of “Efficient Architectures for Information Transport in Wireless Sensor Networks”. He is currently writing a book, tentatively entitled “Digital Communications over Packet-Switched Networks”, to be published by Kluwer.This revised version was published online in August 2005 with a corrected cover date.     

A Region-Based Representation of Images in MARS

We study the problem of representing images within a multimedia Database Management System (DBMS), in order to support fast retrieval operations without compromising storage efficiency. To achieve this goal, we propose new image coding techniques which combine a wavelet representation, embedded coding of the wavelet coefficients, and segmentation of image-domain regions in the wavelet domain. A bitstream is generated in which each image region is encoded independently of other regions, without having to explicitly store information describing the regions. Simulation results show that our proposed algorithms achieve coding performance which compares favorably, both perceptually and objectively, to that achieved using state-of-the-art image/video coding techniques while additionally providing region-based support.     

Network information flow with correlated sources

Consider the following network communication setup, originating in a sensor networking application we refer to as the "sensor reachback" problem. We have a directed graph G=(V,E), where V={v/sub 0/v/sub 1/...v/sub n/} and E/spl sube/V/spl times/V. If (v/sub i/,v/sub j/)/spl isin/E, then node i can send messages to node j over a discrete memoryless channel (DMC) (X/sub ij/,p/sub ij/(y|x),Y/sub ij/), of capacity C/sub ij/. The channels are independent. Each node v/sub i/ gets to observe a source of information U/sub i/(i=0...M), with joint distribution p(U/sub 0/U/sub 1/...U/sub M/). Our goal is to solve an incast problem in G: nodes exchange messages with their neighbors, and after a finite number of communication rounds, one of the M+1 nodes (v/sub 0/ by convention) must have received enough information to reproduce the entire field of observations (U/sub 0/U/sub 1/...U/sub M/), with arbitrarily small probability of error. In this paper, we prove that such perfect reconstruction is possible if and only if H(U/sub s/ | U/sub S(c)/) < /spl Sigma//sub i/spl isin/S,j/spl isin/S(c)/ for all S/spl sube/{0...M},S/spl ne/O,0/spl isin/S(c). Our main finding is that in this setup, a general source/channel separation theorem holds, and that Shannon information behaves as a classical network flow, identical in nature to the flow of water in pipes. At first glance, it might seem surprising that separation holds in a fairly general network situation like the one we study. A closer look, however, reveals that the reason for this is that our model allows only for independent point-to-point channels between pairs of nodes, and not multiple-access and/or broadcast channels, for which separation is well known not to hold. This "information as flow" view provides an algorithmic interpretation for our results, among which perhaps the most important one is the optimality of implementing codes using a layered protocol stack.