OVERVIEW

Objectives – Methods – Accomplishments

With support from both CENS and a small ITR grant, we have continued to make progress in understanding the fundamental information theoretic underpinnings of sensor networks, in the following areas.

1. Scalability. We have extended results showing how networks that sense point sources can become scalable to also show that under a spatial distortion constraint one can also provide scalable networks to sense distributed phenomena. Two CENS technical reports were produced and we are now working on a journal paper.
2. Data fusion: we have extended solutions from other researchers for point sources to deal with fusion in the presence of noise also for distributed phenomena (the Gaussian CEO problem). This work is now being written up for publication. We have also produced bounds for the n-helper and related data fusion problems, explained in a CENS technical report. These collectively answer some questions on the benefits/limits of local cooperation.
3. Distributed coherent combining: the question being addressed is the extent that data can be pre-processed in the nodes making the observations before being combined, for both narrowband and wideband sources, and at what penalty in performance. This could give performance close to that of coherent beamforming with a small fraction of the data exchange. Preliminary results are encouraging.
4. Sensor diversity: the question of how small motions of observers could increase detection probabilities in highly obstructed environments was investigated by two undergraduate researchers, and also by Aman Kansal. Analytical results and simulations showed large gains were possible, which then led to experimentation by Prof. Kaiser’s group. The general notion of how to reduce model/sensing uncertainty has become an organizing principle for much of the NIMS research and has already resulted in one publication.

APPROACH

From 2003:

With support from both CENS and a small ITR grant, significant progress has been made in understanding the fundamental information theoretic underpinnings of sensor networks. It has long been known in information theory that while for single links source coding and channel coding may be separately optimized to obtain a globally optimal result, this separation fails for network problems. Further, even determination of rate distortion and capacity regions alone without their interactions has proven to be very difficult. However, recent progress in problems on the scalability of ad hoc networks suggests that for sensor networks it may be possible to make rapid progress.

In summary, recent results have shown that if nodes both generate traffic and relay it, then scalability will not be achieved (i.e., the per node transport capacity goes to zero as the network expands), even if the nodes cooperate to the maximum possible extent in transmission. However, in sensor networks where there is some distortion permitted in the observations the amount of information to be collected ultimately does not depend on the number of sensors. (This remains to be quantified for particular sources). Thus, scalability is achieved if the information can be processed locally (using network rate-distortion coding), and then the results conveyed over distance for example using standard internet techniques since this will be a small fraction of the traffic. That is, source and channel coding might need to be considered jointly on local scales to determine parameters of point or distributed sources, but the long-range transport can be considered separately using well-established techniques. The implication is that the local processing and communications is by far the most important problem. If it is not done properly, the network is not scalable; if it is done properly, not only does the network scale but the long-range transport problem is essentially solved.

ACCOMPLISHMENTS

From 2003:

Since local problems are amenable to numerical optimizations, we consider this to be a breakthrough in understanding that will have consequences for both theory and the development of algorithms. The results were recently presented at the IEEE Communications Theory Workshop, and a journal paper is in preparation.

We have derived the source-destination pair distributions that lead to scalability, quantified the bandwidth cost for scalable hierarchical communication systems, and have made progress on tightening bounds on the benefits of cooperative communication. We have also tightened the capacity regions for problems involving cooperative communication among three and four communicating parties, by far the most likely configurations for such cooperation in multi-hop routing through sensor networks.

FUTURE DIRECTIONS

In area (D), the two topics requiring the most intensive investigation are adaptive sampling (being pursued in the NIMS program) and how local cooperation can be optimized. The latter is important because for scalable systems it is in the local interactions that most resources will be consumed. Coming to an understanding of how much cooperation and of what type is needed for different density/Nyquist rate ratios will be an important focus. Our results so far indicate that at high oversampling the main question is how to limit the number of nodes involved, while obviously near the Nyquist rate very deep cooperation is required. We would like to quantify these general notions through theoretical bounds and practical algorithms. The bounds will be pursued as extensions to both our rate distortion and Gaussian CEO problem work, with formulation of optimization problems for non-Gaussian distributions. Practical algorithms will focus upon alternative cooperative source coding and routing strategies considered in combination. Recent work in this area at MICS has considered tree-based routing strategies and quantization at source followed by joint coding. We have constructed examples where alternative strategies do considerably better, but some work will be required to come up with robust algorithms. Another local optimization relates to how to trade bit rate against performance in performing coherent combining such as broad-band beamforming. For example, relative phase can be determined at particular frequencies over a set of observations at a node, and a single complex number exchanged as compared to the complete sequence of observations. A variety of parameterizations are being investigated to determine which lead to better performance/bit rate curves.

PEOPLE

FACULTY

G. Pottie

GRADUATE STUDENTS

A. Pandya
H. Luo
A. Kansal

UNDERGRADUATE STUDENTS

T. Jin
O. Akanni