Broadcasting Nested Message Sets

In this paper, we take a deterministic approach to the problem of broadcasting nested message sets. We mainly consider the scenario where a common message and a private message are to be encoded into a signal and transmitted over a broadcast channel towards a set of users. A group of the users, called public receivers, demand only the common message and the rest, called private receivers, demand both messages. A Linear deterministic model for broadcast channels assumes that every user receives a linear transformation of the sent signal. This model is mainly motivated by the MIMO Gaussian broadcast problem in the high SNR regime. We start our study with a simple, yet rich, class of such broadcast channels. We address the main challenges in designing optimal encoding schemes and seek new techniques. In particular, we give an exact characterization of the ultimate rates of communication (together with a class of linear codes that achieves them) over channels with three public and any number of private receivers. We show sub-optimality of these schemes for channels with more than three public receivers and propose a block Markov scheme which allows communication at higher rates. Using this technique, we characterize a set of achievable rates of communication. The intuitions and techniques that we develop over this class of channels guide us towards designing optimal codes for (general) linear deterministic channels. We fully characterize the set of all admissible rates of communication for linear deterministic channels with two public and any number of private receivers. We extend this result to also allow communication of three nested message sets. The study of deterministic models is aimed to be instructive for understanding more general channels. In this regard, we consider the problem of broadcasting two nested message sets over general broadcast channels with two public and one private receiver. For such general broadcast channels, the ultimate rates of communications (and consequently optimal communication schemes) are still unknown. We adapt the block Markov encoding scheme, which we developed within the framework of linear deterministic channels, to general broadcast channels and characterize a set of achievable rates. We discuss potential future directions that seem promising.

Broadcasting and Multicasting Nested Message Sets

Shirin Saeedi Bidokhti

Finding theoretical limits on the performance of communication systems and designing schemes to achieve them is one of the fundamental questions in information theory. While the theory of point-to-point communication is well-investigated, most problems have remained unresolved when communication is over a multi-user system. This lack of understanding is unsatisfactory for today’s growing networks. Recently, significant progress has been made on these problems through a deterministic approach which lays out a promising path in developing a better understanding of multi-user communication systems and in devising new communication schemes. In this thesis, we take a deterministic approach to the problem of communicating nested message sets over wireless and wireline networks. This class of problems is motivated by its applications in video streaming services over heterogeneous networks, where users have different quality-of-service demands. This thesis mainly considers the scenario where a common message (e.g., the low resolution information of a video stream) and a private message (e.g., a higher level of resolution) are to be encoded into a signal and transmitted over a shared medium (e.g., mobile networks, the Internet) towards a set of users. A group of the users, called public receivers, demand only the common message and the rest, called private receivers, demand both messages. The focus is on single-hop broadcast channels and multi-hop wireline networks. A Linear deterministic model for broadcast channels assumes that every user receives a linear transformation of the sent signal. This model is mainly motivated by the MIMO Gaussian broadcast problem in the high SNR regime. We start our study with a simple, yet rich, class of such broadcast channels. We address the main challenges in designing optimal encoding schemes and seek new techniques. In particular, we give an exact characterization of the ultimate rates of communication (together with a class of linear codes that achieves them) over channels with three public and any number of private receivers. We show sub-optimality of these schemes for channels with more than three public receivers and propose a block Markov scheme which allows communication at higher rates. Using this technique, we characterize a set of achievable rates of communication. The intuitions and techniques that we develop over this class of channels guide us towards designing optimal codes for (general) linear deterministic channels. We fully characterize the set of all admissible rates of communication for linear deterministic channels with two public and any number of private receivers. We extend this result to also allow communication of three nested message sets. The study of deterministic models is aimed to be instructive for understanding more general channels. In this regard, we consider the problem of broadcasting two nested message sets over general broadcast channels with two public and one private receiver. For such general broadcast channels, the ultimate rates of communications (and consequently optimal communication schemes) are still unknown. We adapt the block Markov encoding scheme, which we developed within the framework of linear deterministic channels, to general broadcast channels and characterize a set of achievable rates. This achievable rate-region turns out to be equal to the best previously known region (over channels with two public and one private receiver). Nonetheless, we argue that it remains possible that our block Markov encoding scheme may strictly outperform the previous schemes over channels with more (public) receivers. We discuss potential future directions that seem promising. When communication takes place over a multi-hop network, devising optimal communication strategies becomes much more challenging as the encoding scheme of the source should be designed jointly together with the encoding schemes of all the intermediate nodes of the network. We explore this problem over wireline networks, assuming two public and one private receiver. First, we ask if one can always devise a simple and rate-optimal strategy to route the private information to the private receiver and on the remaining network multicast the common message to all receivers. We discuss networks for which this strategy is suboptimal and characterize a class of networks for which it is indeed optimal. We also establish close connections of this problem to linear deterministic channels. This connection lets us formulate another strategy for nodes’ operations which achieves higher rates of transmission. Characterizing all admissible rates of communication over this three-receiver network remains open for further investigation.

EPFL2012

Efficient decentralized communications in sensor networks

Razvan Cristescu

This thesis is concerned with problems in decentralized communication in large networks. Namely, we address the problems of joint rate allocation and transmission of data sources measured at nodes, and of controlling the multiple access of sources to a shared medium. In our study, we consider in particular the important case of a sensor network measuring correlated data. In the first part of this thesis, we consider the problem of correlated data gathering by a network with a sink node and a tree communication structure, where the goal is to minimize the total transmission cost of transporting the information collected by the nodes, to the sink node. Two coding strategies are analyzed: a Slepian-Wolf model where optimal coding is complex and transmission optimization is simple, and a joint entropy coding model with explicit communication where coding is simple and transmission optimization is difficult. This problem requires a joint optimization of the rate allocation at the nodes and of the transmission structure. For the Slepian-Wolf setting, we derive a closed form solution and an efficient distributed approximation algorithm with a good performance. We generalize our results to the case of multiple sinks. For the explicit communication case, we prove that building an optimal data gathering tree is NP-complete and we propose various distributed approximation algorithms. We compare asymptotically, for dense networks, the total costs associated with Slepian-Wolf coding and explicit communication, by finding their corresponding scaling laws and analyzing the ratio of their respective costs. We argue that, for large networks and under certain conditions on the correlation structure, "intelligent", but more complex Slepian-Wolf coding provides unbounded gains over the widely used straightforward approach of opportunistic aggregation and compression by explicit communication. In the second part of this thesis, we consider a queuing problem in which the service rate of a queue is a function of a partially observed Markov chain, and in which the arrivals are controlled based on those partial observations so as to keep the system in a desirable mildly unstable regime. The optimal controller for this problem satisfies a separation property: we first compute a probability measure on the state space of the chain, namely the information state, then use this measure as the new state based on which to make control decisions. We give a formal description of the system considered and of its dynamics, we formalize and solve an optimal control problem, and we show numerical simulations to illustrate with concrete examples properties of the optimal control law. We show how the ergodic behavior of our queuing model is characterized by an invariant measure over all possible information states, and we construct that measure. Our results may be applied for designing efficient and stable algorithms for medium access control in multiple accessed systems, in particular for sensor networks.

EPFL2004

Broadcast, relay and feedback in Gaussian channels

Sibi Raj Bhaskaran Pillai

Network information theory explores the fundamental data transport limits over communication networks. Broadcasting and relaying are two natural models arising in communication contexts where multiple users share a common communication medium. Number of relay and broadcasting models are considered in this thesis. We first collect the existing methodologies of communication over a discrete memoryless relay channel. A new communication strategy over this channel is also proposed, which achieves the same data-rates as the best known schemes in literature, incurring a lower delay at the same time. We then consider the Gaussian broadcast channel (GBC), and show that its capacity region is enlarged by the availability of feedback, even if the feedback is from only one of the receivers. We further show a low complexity, explicit capacity achieving strategy over a GBC with degraded receivers. A combination of relay and broadcast models, called the relay-broadcast channel (RBC) is analyzed next. Achievable regions are proposed for different RBC scenarios. For the Gaussian version of an RBC, we characterize the complete capacity region when the receivers are degraded with respect to the relay. The final part of this thesis investigates communication over fading channels. We propose upper bounds for non-coherent, as well as lower bounds for coherent communication over a MIMO fading channel.