Communications Research Colloquium and Informal Seminar

See also the archive of previous semesters: Spring 2002, Fall 2002, Spring 2003.

Speaker:

Jun Chen.

Title:

Two talks (public A exam).

Abstract:

The title of the first topic is The Capacity of Finite-State Channels with Feedback. We consider a class of finite state feedback channels. We first introduce a simplified equivalent channel model, and then construct the optimal stationary and nonstationary input processes that maximize the long-term directed mutual information. Furthermore, we give a sufficient condition under which the channel's Shannon capacity can be achieved by a stationary input process. The corresponding converse coding theorem and direct coding theorem are proved.

The title of the second topic is The Sum-Rate Distortion Function and Optimal Rate Allocation for the Quadratic Gaussian CEO Problem. We consider a distributed sensor network in which several observations are communicated to the fusion center using limited transmission rate. The observations must be separately encoded so that the target can be estimated with minimum average distortion. We address the problem from an information theoretic perspective and establish the inner and outer bound of the admissible rates-distortion region. The quadratic Gaussian case is discussed in detail and the results are applied to characterize the sum-rate distortion function for the quadratic Gaussian CEO problem. The optimal rate allocation for a generalized quadratic Gaussian CEO problem will also be exploited.

Note: this seminar consists of Jun's A exam. The public part of this exam is expected to last for about 1.5 hours, and anyone interested is welcome to attend. The members of his committee are Professors Toby Berger (chair), Richard Durrett, and Sergio Servetto.

Speaker:

Xin Zhang.

Title:

Rate Allocation in Distributed Sensor Networks.

Abstract:

We consider a distributed sensing system in which several observations are communicated to the fusion center using limited transmission rate. The observations must be separately encoded so that the target can be estimated with minimum average distortion. Under the assumption that the encoders (i.e. sensors) are unlimited in complexity, we get an achievable region of rates and average distortion. The quadratic Gaussian case is discussed in detail and the results are applied to the quadratic Gaussian CEO problem to derive an upper bound on the sum-rate distortion function.

Speaker:

An-swol Hu.

Title:

Asymptotically Optimal Time Synchronization in Dense Sensor Networks.

Abstract:

We consider the problem of synchronization of all clocks in a sensor network, in the regime of asymptotically high node densities. We formulate this problem as one in which all clocks must line up with the clock of an arbitrary node in the network (of course without assuming that this clock can be observed everywhere in the network, nor assuming that this node has any special hardware--this node could be any). We give a state-space description for the generation of observable data as a function of the ideal clock, and we derive an optimal estimator for determining the state of the ideal clock. A salient feature of our approach is that nodes collaborate to generate an aggregate waveform that can be observed simultaneously by all nodes, and that contains enough information to synchronize all clocks. This aggregate waveform effectively simulates the presence of a "super-node" capable of generating a high-power, network-wide time reference signal.

Note: this is a re-run of a paper An-swol presented last Friday in San Diego, at the ACM Workshop on Wireless Sensor Networks and Applications (WSNA), held in conjunction with ACM MobiCom 2003.

Speaker:

Ron Dabora.

Title:

Data Aided Time Synchronization for CPM over Time Selective Fading Channels.

Abstract:

In this talk we discuss data-aided time synchronization for Continuous Phase Modulation (CPM) over time selective Rayleigh fading channels. CPM is an important class of digital modulation that combines good spectral efficiency with the desirable property of constant signal modulus. This latter characteristic enables the use of highly efficient non-linear power amplification in transmission and provides inherent robustness to amplitude fading in reception. The discussion is divided into two parts:

• In the first part we analyze the Cramer-Rao lower bound (CRB): using a mismatched AR1 fading model, we will analytically investigate the dependence of the bound on the key parameters, such as signal-to-noise ratio (SNR), channel correlation, sampling rate and sequence length. Simple expressions are obtained for the case of Minimum Shift Keying (MSK), where it is shown how the bound can be used as a sequence design tool to optimize synchronization performance.

• In the second part we present the derivation of a Maximum-Likelihood (ML) oriented estimation algorithm. Using the mismatched AR1 correlation model and a high SNR approximation we are able to compress the search to a single parameter search, only on the delay parameter. The estimator derived is proved to be asymptotically consistent and unbiased. We also present the analytically derived variance of the estimate and compare it with simulation results obtained with for a nominal MSK scenario. The estimator derived is shown to obtain significantly better performance than the conventional static-channel ML estimator.

Note: this is Ron's Masters thesis work, done at Tel Aviv University (Israel) before coming to Cornell this Fall (2003) for his PhD.

Speaker:

Panos Papadimitratos.

Title:

Secure Communication in Mobile Ad Hoc Networks.

Abstract:

The visions of nomadic computing, ubiquitous network access, and pervasive computing have stimulated much interest in the development of enabling networking technologies. The Mobile ad hoc networking (MANET) paradigm comprises such wireless networks, which can be rapidly deployed and operate without a fixed communication infrastructure. Ad hoc networks are expected to support a wide range of commercial and tactical applications, in a variety of environments. However, the proliferation of MANET-based applications is strongly dependent on the security of these systems. Our approach to this complex problem is to secure the communication and maintain connectivity despite malicious or selfish behavior. We designed and experimented with protocols that secure both phases of communication in ad hoc networks. In this talk, we will discuss protocols securing the route discovery and the data transmission to provide a complete security solution at the network layer.

Speaker:

Balaji S. Prabhakar.

Title:

The Parisi and Coppersmith-Sorkin Conjectures for the Random Assignment Problem.

Abstract:

Suppose that there are n jobs and n machines and it costs c(i,j) to execute job i on machine j. The assignment problem concerns the determination of a one-to-one assignment of jobs onto machines so as to minimize the cost of executing all the jobs. When the c(i,j) are independent and identically distributed exponentials of mean 1, Parisi has made the beautiful conjecture that the average minimum cost equals the sum of 1/i^2 from i=1 to n.

Coppersmith and Sorkin have generalized Parisi's conjecture to the average value of the smallest k-assignment when there are n jobs and m machines. These conjectures have been open for some time now. This talk outlines the resolution of these conjectures. As background, we shall survey approaches to the assignment problem from computer science, statistical physics, and probability.

Joint work with Chandra Nair and Mayank Sharma.

Bio: Balaji Prabhakar is with the Departments of Electrical Engineering and Computer Science at Stanford University. He is currently interested in network algorithms, scalable network performance prediction, wireless networks and information theory. He is a Fellow of the Alfred P. Sloan Foundation, and has received the NSF CAREER award, the Erlang Prize from the INFORMS Applied Probability Society, and the Rollo Davidson Prize from the University of Cambridge.

Speaker:

Steven Low.

Title:

Fast TCP.

Abstract:

We interpret TCP/AQM (active queue management) as carrying out a distributed algorithm over the Internet to maximize aggregate source utility. Different protocols correspond to different optimization algorithms to solve the same prototype problem with different utility functions. All equilibrium properties such as throughput, queue length, fairness are determined by this underlying utility maximization problem. We show that the equilibrium of TCP/RED become unstable as delay increases, or more strikingly, as network capacity increases. We present an improved algorithm, FAST TCP, that adopts a different implementation strategy and can maintain stability and sustain multi-Gbps throughput over wide area, using standard MTU. We describe recent experimental results over live intercontinental networks.

(With FAST Team and Partners at http://netlab.caltech.edu/FAST.)

Bio: Steven H. Low received his B.S. degree from Cornell University and PhD from Berkeley, both in EE. He was with AT&T Bell Laboratories, Murray Hill, from 1992 to 1996 and with the University of Melbourne, Australia, from 1996 to 2000. He is now an Associate Professor at the California Institute of Technology, Pasadena. He was a co-recipient of the IEEE William R. Bennett Prize Paper Award in 1997 and the 1996 R&D 100 Award. He is on the editorial boards of the IEEE/ACM Transactions on Networking and the Computer Networks Journal, and has been a guest editor of the IEEE Journal on Selected Areas in Communications.

Speaker:

Balaji S. Prabhakar.

Title:

Simple, Scaleable Network Algorithms.

Abstract:

Randomized algorithms are particularly well-suited for coping with the so-called "curse of dimensionality" from which many networking problems suffer. The main idea of randomized algoriths is simple to state: Rather than contend with a large state space, the trick is to make decisions based upon a few randomly chosen samples.

This talk will illustrate the use of randomization in devising simple-to-impelement, high-performance network algorithms; specifically, for switch scheduling, web caching, and bandwidth partitioning.

Bio: Balaji Prabhakar is with the Departments of Electrical Engineering and Computer Science at Stanford University. He is currently interested in network algorithms, scalable network performance prediction, wireless networks and information theory. He is a Fellow of the Alfred P. Sloan Foundation, and has received the NSF CAREER award, the Erlang Prize from the INFORMS Applied Probability Society, and the Rollo Davidson Prize from the University of Cambridge.

Speaker:

Rimon Barr.

Title:

JiST: Java in Simulation Time for Scalable Simulation of Mobile Ad hoc Networks.

Abstract:

Discrete event simulators are important scientific tools. For example, research in the areas of wireless ad hoc and sensor networks is fundamentally dependent on simulators. Yet, existing tools for modelling the behaviour of such networks are often unsatisfactory, because they severely limit the possible scale, level of detail or duration of the simulation results.

In this talk, I will describe a new approach for constructing discrete event simulators that leverages virtual machines and combines the traditional systems-based and language-based approaches to simulator construction. JiST, for Java in Simulation Time, is a simulation engine that embodies this new technique. It embeds simulation execution semantics directly into the Java virtual machine. I will explain how the basic system works and then demonstrate that this approach is not only surprisingly efficent, but also flexible. Finally, I will illustrate a practical application of JiST through SWANS, a Scalable Wireless Ad hoc Network Simulator that runs atop JiST. SWANS can simulate wireless networks of 100,000 nodes and up, more than an order of magnitude larger than what existing simulators can achieve on equivalent hardware.

Speaker:

Qing Zhao.

Title:

On the Use of Channel State for Energy Efficient Information Retrieval in Sensor Networks.

Abstract:

We consider information retrieval in wireless sensor networks where a mobile access point (MA) extracts data collected by sensor nodes. Energy efficiency, defined as the expected number of bits reliably received for each unit of energy consumed, is introduced as the performance measure. Under this metric, we examine two strategies: opportunistic transmission which exploits realizations of channel states and predetermined scheduling which utilizes channel distribution. Taking into account the energy cost of channel acquisition, we reveal that the sum-rate improvement achieved by exploiting channel state information (CSI) does not always justify the extra cost of channel state estimation; the simple predetermined scheduler can outperform the opportunistic strategy.

For applications where the opportunistic strategy is optimal, we propose a decentralized protocol that achieves the performance upper bound of the centralized opportunistic transmission. The key idea is to incorporate local channel state information into the backoff scheme of carrier sensing. Without knowing other sensors' channel states, each sensor decides whether to transmit and the rate of the transmission. Backoff function which maps the channel state to backoff time is constructed and robustness to propagation delay observed.