 
Last updated on September 25, 2017. This conference program is tentative and subject to change
Technical Program for Friday September 29, 2006

FIA 
Library 
Games and Pricing in Networks 
Invited Session 
Chair: Srikant, R  Univ. of Illinois at UrbanaChampaign 
Organizer: Hajek, Bruce  Univ. of Illinois at UrbanaChampaign 
Organizer: Srikant, R  Univ. of Illinois at UrbanaChampaign 

10:0010:30, Paper FIA.140  
On KellyType Mechanisms for Polymatroids (I) 
Berry, Randall  Northwestern Univ 
Vohra, Rakesh  Northwestern Univ 
Keywords:
Abstract: We consider marketbased mechanisms for allocating transmission rates to a set of users whose rates are constrained to lie in a polymatroid capacity region. We study two simple mechanisms, both of which are generalizations of Kelly’s well known allocation mechanism to this setting. We characterize the equilibrium properties of these mechanisms for “price anticipating” users.


10:3011:00, Paper FIA.150  
Positive Externalities and Optimal Scale (I) 
Johari, Ramesh  Stanford Univ 
Kumar, Sunil  Stanford Univ 
Keywords:
Abstract: We study a system where many identical customers use a single service. Each customer experiences both positive and negative externalities from other customers using the service. We characterize the social optimum where a social planner determines the usage level of each customer. We also characterize the Nash equilibrium achieved when the usage levels are determined by the customers themselves, in their selfinterest. We study the ratio of the welfare in Nash equilibrium to that in the social optimum. The main result of the paper is that there is an optimal number of customers at which this ratio is maximized, and the maximum achieved is unity.


11:0011:30, Paper FIA.160  
Toward Topology Aware Networks (I) 
Mihail, Milena  Georgia Inst. of Tech 
Saberi, Amin  Stanford Univ 
Keywords:
Abstract: Maintaining good connectivity is critical in every network application, but becomes even more so in distributed networks without centralized design or control, such as the Internet, P2P, adhoc and sensor networks. We first argue that the graph theoretic notion of conductance and the related algebraic notions of highend spectrum and spectral gap are suitable abstractions of good connectivity. We then turn to the following questions: (a)How can the network nodes become aware, with local computations and in an efficient decentralized way, of the above mentioned global metrics? In other words, how can the clients know if the present network configuration has good conductance or large spectral gap? (b) How can the network elements maintain, with local computations and in an efficient decentralized way, the conductance, or the spectral gap within desired ranges of good performance? (c) How can the network elements become aware of topologically "critical" network areas, such as "critical links", so as to either improve the connectivity or adjust the protocols to achieve better performance?


11:3012:00, Paper FIA.170  
Price and Capacity Competition (I) 
Acemoglu, Daron  MIT 
Bimpikis, Kostas  MIT 
Ozdaglar, Asu  MIT 
Keywords:
Abstract: The major expansion and decentralization of communication networks, particularly the Internet, have motivated a new literature investigating the performance of decentralized network protocols and architectures. The distinguishing feature of this literature is the emphasis on the potential noncooperative interactions among network entities. While the focus of the literature is quantifying efficiency losses of the decentralized equilibria, most of the existing work investigates the efficiency losses resulting from the allocation of resources in an already established network. Arguably, the more important economic decisions in largescale communication networks concern the investments in the structure of the network and in capacity. Our purpose in this paper is to model price and capacity competition between service providers and investigate the efficiency properties of the resulting equilibria. Following previous research, we are interested in quantifying the extent of efficiency losses by providing various worstcase performance results for equilibria.


FIB 
Porch 
Networked Control 
Invited Session 
Chair: Franceschetti, Massimo  Univ. of California at San Diego 
Organizer: Franceschetti, Massimo  Univ. of California at San Diego 
Organizer: Kumar, P. R.  Texas A&M Univ 

10:0010:30, Paper FIB.140  
WorstCase Time Complexity of a Lattice Formation Problem (I) 
Savla, Ketan  Univ. of California, Santa Barbara 
Bullo, Francesco  UCSB 
Keywords: MultiAgent Systems and Robot Control, Networked Control Systems, Decentralized and Distributed Control
Abstract: We consider a formation control problem for a robotic network with limited communication and controlled motion abilities. We propose a novel control structure that organizes the robots in concentric layers and that associates to each layer a local leader. Through a load balancing algorithm on the asynchronous network of layers we allocate the desired number of robots on each layer. A final uniform spreading algorithm leads the robots to a latticelike formation. This novel distributed communication and control algorithm runs in linear time in the worst case.


10:3011:00, Paper FIB.150  
On Consensus Over Random Networks (I) 
TahbazSalehi, Alireza  Univ. of Pennsylvania 
Jadbabaie, Ali  Univ. of Pennsylvania 
Keywords: Networked Control Systems, MultiAgent Systems and Robot Control, Sensor Networks in Communications
Abstract: We consider the decentralized consensus problem over random information networks. In such networks, the underlying graph of the network at a given time instance is random and independent of all other times. For such a framework, we present a simple necessary and sufficient criteria for asymptotic consensus using simple ergodicity and probabilistic arguments. Finally, we investigate a special case for which the decentralized consensus algorithm converges to the average of the initial values.


11:0011:30, Paper FIB.160  
Regular Quantization for CommunicationConstrained Feedback Channels (I) 
Baillieul, John  Boston Univ 


11:3012:00, Paper FIB.170  
Delay Impulsive Systems: A Model for NCSs (I) 
Naghshtabrizi, Payam  Univ. of California at Santa Barbara 
Hespanha, Joao  Electrical and Computer Eng 
Keywords:
Abstract: We consider a large class of Networked Control Systems (NCSs): onechannel NCSs, twochannel NCSs with dynamic (nonanticipative) feedback controllers and twochannel NCSs with anicipative controllers. NCSs in all cases consist of a LTI plant and a linear static or dynamic feedback controller connected through a communication network where the sensors and actuators can be distributed. Due to the shared, unreliable channel to connect plant and controller, the sampling intervals are uncertain and variable. Moreover, samples may be dropped and experience uncertain and variable delays before arriving at the destination. We show that the resulting NCSs can presented as an a bstract (in general MIMO) sampleddata system with variable sampling intervals and delay which can be modeled by linear infinitedimensional impulsive systems. The infinite dimensionality of the system arises from the existence of delays. We provide conditions for the stability of the closedloop expressed in terms of LMIs. By solving these LMIs, one can determine positive constants related to each entity sent through the network that determines an upper bound between the sampling time and the next update time at the destination of that entity, for which stability of the closedloop system is guaranteed.


FIC 
Butternut 
Distributed Systems and Aerospace Applications 
Invited Session 
Chair: Neogi, Natasha  Univ. of Illinois, UrbanaChampaign 
Organizer: Neogi, Natasha  Univ. of Illinois, UC 
Organizer: Langbort, Cedric  UIUC 

10:0010:30, Paper FIC.140  
A Constant Factor Approximation Algorithm for EventBased Sampling (I) 
Cogill, Randy  Stanford Univ 
Lall, Sanjay  Stanford Univ 
Hespanha, Joao  UC Santa Barbara 
Keywords: Decentralized and Distributed Control
Abstract: We consider a control system in which sensor data is transmitted from the plant to a receiver over a communication channel, and the receiver uses the data to estimate the state of the plant. Using a feedback policy to choose when to transmit data, the goal is to schedule transmissions to balance a tradeoff between communication rate and estimation error. Computing an optimal policy for this problem is generally computationally intensive. Here we provide a simple algorithm for computing a suboptimal policy for scheduling state transmissions which incurs a cost within a factor of six of the optimal achievable cost.


10:3011:00, Paper FIC.150  
Distributed Mobile Disk Cover  a Building Block for Mobile Backbone Networks (I) 
Srinivas, Anand  MIT 
Zussman, Gil  MIT 
Modiano, Eytan  MIT 
Keywords: Decentralized and Distributed Control, Sensor Networks, Performance Analysis
Abstract: The novel hierarchical architecture of Mobile Backbone Networks has been recently studied by a few different approaches. An important subproblem related to the design and operation of such networks is the problem of constructing and maintaining a Geometric Disk Cover (GDC) under mobility. While from the context of static nodes and centralized solutions the GDC problem has been extensively studied, the Mobile GDC problem did not receive much attention. We present two new algorithmic approaches for the solution of this problem. These approaches significantly differ from previously presented approaches. In order to analyze the worst case performance of the algorithms, we develop a novel graphbased analysis technique. Then, we develop a methodology to compute bounds on the average case performance of recently presented stripbased algorithms. We use these bounds along with simulation results to evaluate the performance of the algorithms. It is shown that the proposed algorithms perform very well under mobility, thereby providing an important building block for the construction and maintenance of Mobile Backbone Networks.


11:0011:30, Paper FIC.160  
LeaderBased MultiAgent Coordination through Hybrid Optimal Control (I) 
Bjorkenstam, Staffan  Chalmers Univ. of Tech 
Ji, Meng  Georgia Inst. of Tech 
Egerstedt, Magnus  Georgia Inst. of Tech 
Martin, Clyde  Texas Tech. Univ 
Keywords: MultiAgent Systems and Robot Control, Networked Control Systems, Hybrid Systems
Abstract: The problem of optimally transferring a linear dynamical system between affine varieties arises in a number of applications such as path planning and robot coordination. In this paper, this problem, as well as generalizations to switched linear systems, is solved in the context of minimum energy control. In particular, we present a novel algorithm for obtaining the globally optimal solution through a combination of Hilbert space methods and dynamic programming. As a driving application, the problem of leaderbased multiagent coordination is considered, and we show how our proposed algorithm can be used for optimal coordination purposes.


11:3012:00, Paper FIC.170  
Airspace Complexity (I) 
Lee, Keumjin  GEORGIA Tech 
Feron, Eric  GEORGIA Tech 
Pritchett, Amy  Georgia Inst. of Tech 
Keywords: Decentralized and Distributed Control, Networked Control Systems, MultiAgent Systems and Robot Control
Abstract: This paper addresses the question of extracting “airspace complexity” from given aircraft position and speed data. Airspace complexity aims at describing “how difficult” a given aircraft configuration is, from the standpoint of the air traffic controller working with or without aiding devices. In this paper, we attempt to find “airspace transforms”, that is, maps from airspace configurations to graphics that extract and clearly display the state of the system relative to some measure of risk. Building on systemtheoretic concepts, fast optimization tools and the seminal work of John Andrews (Lincoln Laboratory), we propose a set of possible airspace transforms that appear to achieve this goal. We discuss how such transforms might be useful as decision aids. We also postulate scalar measures of “air traffic complexity” and illustrate our approach on a few examples.


12:0012:30, Paper FIC.180  
Target Tracking of Arrival Aircraft Using Hybrid Estimation (I) 
Seah, Chze Eng  Purdue Univ 
Hwang, Inseok  Purdue Unversity 
Keywords: Hybrid Systems, Decentralized and Distributed Control, Stochastic Systems and Control
Abstract: A bottleneck to the flow of air traffic is in the traffic around airports. Accurate tracking of aircraft movements around airports is important in order to improve the traffic capacity and safety. We propose a hybrid estimation algorithm that utilizes the knowledge of arrival aircraft flight plans and landing profiles to improve tracking accuracy of aircraft movements. We utilize Gaussian mixture approximations and hypothesis merging to overcome the exponentially growing complexity of the estimation problem. A continuousstatedependent mode transition matrix is used to accurately model the mode transition probabilities of the hybrid system. As a result, we need to solve a multivariate integral in order to compute the mode transition probabilities of the hybrid system. By approximating the continuousstate distributions as Gaussian probability density functions, we simplify the multivariate integration problem and then compute the integral using a Monte Carlo (MC) integration method. We analyze the convergence and probabilistic error bound of the MC integration method. We demonstrate the performance of the proposed algorithm with an arrival aircraft tracking example.


FID 
Pine 
Network Optimization 
Invited Session 
Chair: Ho, Tracey  California Inst. of Tech 
Organizer: Meyn, Sean  Univ. of Florida 
Organizer: Médard, Muriel  MIT 
Organizer: Kötter, Ralf  Tech. Univ. München 

10:0010:30, Paper FID.140  
FAST Copper for Broadband Access (I) 
Chiang, Mung  Princeton Univ 
Huang, Jianwei  Princeton Univ 
Tan, Chee Wei  Princeton Univ 
Cendrillon, Raphael  Marvell Hong Kong Ltd 
Xu, Dahai  Princeton Univ 
Yi, Yung  Princeton Univ 
Keywords:
Abstract: This is an overview of the ongoing FAST Copper project, which is aimed at substantial improvements in rate, reach, reliability, and quality in copperlastmile broadband access through fiber/DSL deployment, engineering innovations, and fundamental research. The project is funded by NSF, and is currently pursued jointly by Princeton University, Stanford University, and Fraser Research Lab. In this article, we outline the motivations, challenges, and research issues associated with the project, including connections with many branches of fundamental research, collaboration with industry partners, and emphasis on architectural decisions in broadband access networks. We also report some of the recent results by the Princeton team in each of the four dimensions: Frequency, Amplitude, Space, and Time.


10:3011:00, Paper FID.150  
Economic Aspects of Network Coding (I) 
Ahmed, Ebad  MIT 
Eryilmaz, Atilla  LIDS, Massachusetts Inst. of Tech 
Medard, Muriel  MIT 
Ozdaglar, Asu  MIT 
Keywords:
Abstract: This work focuses on a cellular system scenario of a single base station broadcasting incoming files (or users) to multiple receivers over a timevarying channel. The basestation sets a price per receiver and per file to maximize its profit. The files may or may not enter the system depending on the price of service, the delay performance and their randomly determined valuations. Under this scenario, we consider the use of Network Coding and Scheduling as the transmission strategies. Our analysis provides approximate characterization of the optimal admission rate, price and revenue as functions of the first and second moments of the service time processes under mild assumptions. We show that optimal network coding window size is highly insensitive to the number of receivers, which suggests that pricing and coding decisions can be decoupled. Moreover, we demonstrate that network coding leads to a significant (almost tenfold) gain in the revenue compared to scheduling.


11:0011:30, Paper FID.160  
Distributed Scheduling Schemes for Throughput Guarantees in Wireless Networks (I) 
Sharma, Gaurav  Purdue Univ 
Joo, Changhee  Purdue Univ 
Shroff, Ness  Purdue Univ 
Keywords:
Abstract: Wireless networks differ from their wireline counterparts in that a group of simultaneously active wireless links interfere with each other. This interference between links significantly complicates the scheduling component in wireless systems. This is especially problematic in multihop wireless networks, where the number of nodes can be quite large and one cannot assume the presence of a central authority. The extent of the interference varies across networks as it is physical layer dependent, and with it varies the complexity of scheduling. In this work, we discuss some commonly used interference models in the literature along with distributed scheduling schemes that can provide provable throughput guarantees under those models. A detailed analysis of the communication overhead is provided for the scheduling schemes, and the results indicate that this overhead can significantly impact the network throughput.


11:3012:00, Paper FID.170  
Heterogeneous Congestion Control (I) 
Tang, Ao (Kevin)  California Inst. of Tech 
Wei, David  California Inst. of Tech 
Low, Steven  California Inst. of Tech 
Chiang, Mung  Princeton Univ 
Keywords:
Abstract: When heterogeneous congestion control protocols that react to different pricing signals (e.g. packet loss, queueing delay, ECN marking etc.) share the same network, the current theory based on utility maximization fails to predict the network behavior. Unlike in a homogeneous network, the bandwidth allocation now depends on router parameters and flow arrival patterns. It can be nonunique, inefficient and unfair. This paper has two objectives. First, we demonstrate the intricate behaviors of a heterogeneous network through simulations and present a rigorous framework to help understand its equilibrium properties. We briefly review basic results on equilibrium and uniqueness. By identifying an optimization problem associated with {em every} equilibrium, we show that every equilibrium is Pareto efficient and provide an upper bound on efficiency loss due to pricing heterogeneity. Second, we propose a simple slow timescale sourcebased algorithm to decouple bandwidth allocation from router parameters and flow arrival patterns and prove its feasibility. The scheme needs only local information. In addition to numerical examples and packetlevel simulations, WAN in Lab experiments are also presented to demonstrate the effectiveness and other features of the proposed solution.


FIE 
Lower Level 
Compressed Sensing 
Invited Session 
Chair: Baron, Dror  Rice Univ 
Organizer: Bresler, Yoram  Univ. of Illinois 
Organizer: Strauss, Martin  Univ. of Michigan 
Organizer: Baron, Dror  Rice Univ 

10:0010:30, Paper FIE.140  
Algorithmic Linear Dimension Reduction in the L1 Norm for Sparse Vectors (I) 
Gilbert, Anna  Univ. of Michigan 
Strauss, Martin  Univ. of Michigan 
Tropp, Joel  Univ. of Michigan 
Vershynin, Roman  Univ. of California, Davis 
Keywords:
Abstract: Using a number of different algorithms, we can recover approximately a sparse signal with limited noise; i.e, a vector of length d with at least dm zeros or nearzeros, using little more than m log(d) nonadaptive linear measurements rather than the d measurements needed to recover an arbitrary signal of length d. We focus on two important properties of such algorithms. 1. Uniformity. A single measurement matrix should work simultaneously for all signals. 2. Computational Efficiency. The time to recover such an msparse signal should be close to the obvious lower bound, m log(d/m). This paper develops a new method for recovering msparse signals that is simultaneously uniform and quick. We present a reconstruction algorithm whose run time, O(m log^2(m) log^2(d)), is sublinear in the length d of the signal. The reconstruction error is within a logarithmic factor (in m) of the optimal mterm approximation error in l_1. In particular, the algorithm recovers msparse signals perfectly and noisy signals are recovered with polylogarithmic distortion. Our algorithm makes O(m log^2 (d)) measurements, which is within a logarithmic factor of optimal. We also present a smallspace implementation of the algorithm. These sketching techniques and the corresponding reconstruction algorithms provide an algorithmic dimension reduction in the l_1 norm. In particular, vectors of support m in dimension d can be linearly embedded into O(m log^2 d) dimensions with polylogarithmic distortion.


10:3011:00, Paper FIE.150  
Computational Issues for InteriorPoint Methods in Compressive Sampling (I) 
Candes, Emmanuel  Stanford Univ. 
Romberg, Justin  Georgia Tech. 

11:0011:30, Paper FIE.160  
Compressed Sensing Algorithms for Functions (I) 
Muthukrishnan, S  Rutgers Univ. 

11:3012:00, Paper FIE.170  
Measurements vs. Bits: Compressed Sensing Meets Information Theory (I) 
Sarvotham, Shriram  Rice Univ 
Baron, Dror  Rice Univ 
Baraniuk, Richard  Rice Univ 
Keywords:
Abstract: Compressed sensing is a new framework for acquiring sparse signals based on the revelation that a small number of linear projections (measurements) of the signal contain enough information for its reconstruction. The foundation of Compressed sensing is built on the availability of noisefree measurements. However, measurement noise is unavoidable in analog systems and must be accounted for. We demonstrate that measurement noise is the crucial factor that dictates the number of measurements needed for reconstruction. To establish this result, we evaluate the information contained in the measurements by viewing the measurement system as an information theoretic channel. Combining the capacity of this channel with the ratedistortion function of the sparse signal, we lower bound the ratedistortion performance of a compressed sensing system. Our approach concisely captures the effect of measurement noise on the performance limits of signal reconstruction, thus enabling to benchmark the performance of specific reconstruction algorithms.


12:0012:30, Paper FIE.180  
Fast Algorithms for Reconstruction in Compressed Sensing (I) 
Donoho, David  Stanford Univ. 

FIF 
Brick 
Tracking 
Regular Session 
Chair: Stipanovic, Dusan  Univ. of Illinois 

10:0010:30, Paper FIF.140  
ZeroError Target Tracking through Limited Querying of Binary Sensors 
Barbosa, Patricia R  Colorado State Univ 
Li, Hua  Colorado State Univ 
Chong, Edwin  Colorado State Univ 
Hannig, Jan  Colorado State Univ 
Kulkarni, Sanjeev  Princeton Univ 
Keywords: Information Theory, Source Coding and Compression, Sensor Networks in Communications
Abstract: We consider the problem of tracking a target that moves according to a Markov chain. An estimator queries a set of sensors to obtain tracking information. We are interested in finding the minimum number of queries per time step such that a target is trackable. Three scenarios are analyzed. First we investigate the case where the estimator is required to know the exact location of the target at each time step. We then relax our requirements and explore the case where the estimator may lose track of the target at a given time step, but it is able to ``catchup," regaining uptodate information about the target's track. Finally, we consider the case where tracking information is only known after a delay of "d" time steps. We provide necessary and sufficient conditions on the number of queries per time step to track in the above three scenarios. These conditions are stated in terms of the entropy rate of the target's Markov chain.


10:3011:00, Paper FIF.150  
Tracking Stopping Times 
Niesen, Urs  MIT 
Tchamkerten, Aslan  MIT 
Wornell, Gregory  MIT 
Keywords: Detection and Estimation, Information Theory
Abstract: Let {(X_i,Y_i)} be a sequence of pairs of random variables, and let S be a bounded stopping time with respect to X_i's. We propose the problem of finding a stopping time T with respect to the Y_i's that optimally tracks S in the sense that T minimizes the average reaction time E(TS)^+ while keeping the falsealarm probability P(S>T) below a given threshold alpha. This problem has applications in many different areas. In this paper we present an application related to communication over a channel with noisy feedback.


11:0011:30, Paper FIF.160  
MAP Trajectory Estimation for a Switching Process with Continuous Levels 
Han, JaeJoon  Purdue Univ 
Gelfand, Saul  Purdue Univ 
Doerschuk, Peter  Cornell Univ 
Keywords: Detection and Estimation, Statistical Signal Processing, Wireless Communications
Abstract: A Maximum A Posteriori (MAP) trajectory estimator implemented by a Dynamic Programming (DP) algorithm for a type of continuous level switching process is described. The model fits neither the standard assumptions of a Hidden Markov Model nor of a Jump Markov Linear System. Both marginal and joint MAP estimation for the state and level trajectories are considered. Computation and storage complexities are linear in the maximum duration of the process memory, which is bounded in a reduced complexity DP implementation. Critical to this result is the stationarity of the level subsequences for each state of the Markov Chain which controls the switching. The motivation for this work is the signal processing for a novel implantable ethanol biosensor.


11:3012:00, Paper FIF.170  
Estimation for Random Sensor Failure with Unknown Failure Rate 
Hounkpevi, Franck  Marquette Univ 
Yaz, Edwin Engin  Marquette Univ 
Keywords: Stochastic Systems and Control, Detection and Estimation, Statistical Signal Processing
Abstract: In this work, the problem of minimum variance estimation for random sensor failure with unknown failure rate is considered. Traditional estimation in sensor networks usually assumes the observation to contain the signal to be estimated and uses the Kalman filter to process the sensor signal for tracking. In reality, certain observations may be missing possibly due to sensor failures or high communication network traffic. For the problem of missing data in sensor networks, minimum variance estimators have been derived by extension of the Kalman filter and by incorporating the missing data rate in the design. In these proposed solutions, the sensor failure rate is critical to the success of these estimators and may not be available. Therefore, in this work, an approach is proposed to perform estimation in missing data environments where the probability of sensor failure is either unknown or a priori known but varies due to changes in environmental conditions during operation. The solution is realized through the use of adaptive estimation via parallel processing. Simulation examples are presented to show the effectiveness of the proposed solution. In addition, the robustness of the proposed technique is also shown through simulations.


12:0012:15, Paper FIF.181  
Temporal Sensing Capacity 
Rachlin, Yaron  Carnegie Mellon Univ 
Negi, Rohit  Carnegie Mellon Univ 
Khosla, Pradeep  Carnegie Mellon Univ 
Keywords: Sensor Networks, Information Theory, Detection and Estimation
Abstract: A large class of applications require sensor networks to monitor environments evolving through time. Examples of such applications include pollution, traffic, and agricultural monitoring. We characterize the limits of such systems by defining and bounding the `temporal sensing capacity.' The temporal sensing capacity bounds the number of sensor measurements required to detect a dependent sequence of discrete target vectors to within a desired accuracy. Rather than querying a fixed number of sensors allocated uniformly in time and space, our model assumes a sensor network that queries a subset of sensors at randomly selected locations and at random times. Our approach points to a novel manner of jointly encoding a sequence of target vectors which is useful due to the variable resources that characterize sensor networks. In order to demonstrate the gain provided by temporal correlation, we compare the temporal sensing capacity result to a sensing capacity result for detecting a single target vector.


FIG 
Visitor Center 
Timing and Capacity 
Regular Session 
Chair: Sarwate, Dilip  Univ. of Illinois 

10:0010:30, Paper FIG.140  
Capacity of the Trapdoor Channel with Feedback 
Permuter, Haim  Stanford 
Cuff, Paul  Stanford Univ 
Van Roy, Benjamin  Stanford Univ 
Weissman, Tsachy  Stanford 
Keywords: Information Theory, Control Applications, Coding Theory
Abstract: We establish that the feedback capacity of the trapdoor channel is the logarithm of the golden ratio and provide a simple communication scheme that achieves capacity. As part of the analysis, we formulate a class of dynamic programs that characterize capacities of unifilar finitestate channels. The trapdoor channel is an instance that admits a simple analytic solution.


10:3011:00, Paper FIG.150  
Mismatch Decoding of a Compound Timing Channel 
Momcilovic, Petar  Univ. of Michigan 
Keywords: Information Theory
Abstract: A compound exponentialserver timing channel consists of a number of infinitebuffer singleserver queues in tandem. The message is coded in the sequence of arrival times to the first queue. We consider the performance of a structurally simple mismatch decoder that is the maximumlikelihood decoder for a single queue.


11:0011:30, Paper FIG.160  
The Capacity Region of a Class of Discrete Degraded Interference Channels 
Liu, Nan  Univ. of Maryland 
Ulukus, Sennur  Univ. of Maryland 
Keywords: Information Theory
Abstract: We provide a singleletter characterization for the capacity region of a class of discrete degraded interference channels (DDICs). The class of DDICs considered includes the discrete additive degraded interference channel (DADIC) studied by Benzel. We show that for the class of DDICs studied, encoder cooperation does not increase the capacity region, and therefore, the capacity region of the class of DDICs is the same as the capacity region of the corresponding degraded broadcast channel.


11:3012:00, Paper FIG.170  
On the Capacity of Time Varying Channels with Periodical Feedback 
Ansari Sadrabadi, Mehdi  Univ. of Waterloo 
Maddahali, Mohammad Ali  Univ. of Waterloo 
khandani, Amir Keyvan  Univ. of Waterloo 
Keywords: Information Theory, Wireless Communications
Abstract: We evaluate the capacity of a finite state Markov channel with periodical feedback at the transmitter. It is assumed that the channel state information (CSI) is perfectly known at the receiver. The CSI is fed back to the transmitter at regular intervals by means of a noiseless feedback link. We show that the capacity is achievable by multiplexing multiple codebooks across the channel. Moreover, we derive the channel capacity for the additive white Gaussian noise (AWGN) channel with timecorrelated Rayleigh fading. The optimal adaptive coding is found for the fading channel with periodical feedback of channel states. It is shown that the optimal adaptation can be achieved by a single Gaussian codebook with adaptively allocating power based on the side information at the transmitter.


12:0012:15, Paper FIG.181  
The Low and High SNR Behavior of the OFDM Delay Limited Capacity 
Wunder, Gerhard  Fraunhofer GermanSino Lab. for Mobile Communications  MCI 
Michel, Thomas  Fraunhofer GermanSino Lab. for Mobile Communications  MCI 
Keywords: Wireless Communications, Information Theory, MIMO Systems
Abstract: The delay limited capacity (DLC) of OFDM has been considered recently in several papers. In general, the DLC is more difficult to analyze than ergodic capacity since there is only an implicit formulation. Hence, analysis often resorts to low and high SNR analysis where explicit expression can be found provided that 1) the fading distribution is continuous in the high SNR regime [1] and 2) the fading distribution is absolute continuous in the low SNR regime [2]. However, for OFDM systems the fading distribution does not fulfill these requirements since the subcarriers are highly correlated due to oversamling. Hence, the behaviour is not fully clear yet. In this paper we analyze the OFDM DLC in a general setting and derive the relevant asymptotic quantities without employing simplifying assumptions. Since we derive universal bounds our results can also be used for other classes of parallel channels with block fading characteristic.


12:1512:30, Paper FIG.182  
Timing Channel Capacity for Uniform and Gaussian Servers 
Sellke, Sarah  Purdue Univ 
Shroff, Ness  Purdue Univ 
Bagchi, Saurabh  Purdue Univ 
Wang, ChihChun  Purdue Univ 
Keywords: Information Theory
Abstract: It is well known that queues with exponentially distributed service time have the smallest Shannon capacity among all singleserver queues with the same service rate. However, the capacity of other service disiplines such as Gaussian service timing channels (GSTC) remains unknown. In this paper, we outline a preliminary investigation into the timing channel capacity, when the service distributions are uniform, Gaussian, and truncated Gaussian. We estimate the lower bounds and the upper bounds for these channels. Our study indicates that the capacity per service time increases as the ratio of the standard deviation to the mean service time of the server decreases.

 