The amount of information that is churned out daily around the world is staggering, and hence, future technological advancements are contingent upon development of scalable acquisition, inference, and communication mechanisms for this massive data. This Ph.D. dissertation draws upon mathematical tools from information theory and statistics to understand the fundamental performance limits of universal compression of this massive data at the packet level using universal compression just above layer 3 of the network when the intermediate network nodes are enabled with the capability of memorizing the previous traffic. Universality of compression imposes an inevitable redundancy (overhead) to the compression performance of universal codes, which is due to the learning of the unknown source statistics. In this work, the previous asymptotic results about the redundancy of universal compression are generalized to consider the performance of universal compression at the finite-length regime (that is applicable to small network packets). Further, network compression via memory is proposed as a compression-based solution for the compression of relatively small network packets whenever the network nodes (i.e., the encoder and the decoder) are equipped with memory and have access to massive amounts of previous communication. In a nutshell, network compression via memory learns the patterns and statistics of the payloads of the packets and uses it for compression and reduction of the traffic. Network compression via memory, with the cost of increasing the computational overhead in the network nodes, significantly reduces the transmission cost in the network. This leads to huge performance improvement as the cost of transmitting one bit is by far greater than the cost of processing it.

This thesis studies cooperative sensing and transmission in the context ofwireless sensor networks (WSNs). We especially focus on two means of cooperative sensing and transmission, namely, distributed source coding and relaying. We consider systems where the usefulness of the measured data is dependent on how old the data is and we therefore need low-delay transmission schemes. At first sight, the low-delay criterion may seem to be of little relevance, but it is this aspect in particular that distinguishes this thesis from many of the existing communication theoretic results, which often are asymptotic in the block lengths. The thesis is composed of an introductory part, discussing the fundamentals of communication theory and how these are related to the requirements of WSNs, followed by a part where the results of the thesis are reported in Papers A-H. Papers A-D study different scenarios for distributed source-channel coding. In Paper A, we consider transmission of correlated continuous sources and propose an iterative algorithm for designing simple and energy-efficient sensor nodes. In particular the cases of the binary symmetric channel as well as the additive white Gaussian noise channel are studied. In Paper B, the work is extended to channels with interference and it is shown that also in this case there can be significant power savings by performing a joint optimization of the system.Papers C and D use a more structured approach and propose side-information-aware source-channel coding strategies using lattices and sinusoids. In Paper E, we apply the methods we have used in joint source-channel coding to the famous Witsenhausen counterexample. By using a relatively simple iterative algorithm, we are able to demonstrate the best numerical performance known to date. For the case of systems with relays, we study the transmission of a continuous Gaussian source and the transmission of an uniformly distributed discrete source. In both situations, we propose algorithms to design low-delay source-channel and relay mappings. By studying the structure of the optimized source-channel and relay mappings, we provide useful insights into how the optimized systems work. These results are reported in Papers F and G. In Paper H, we finally consider sum-MSE minimization for the Gaussian multiple-input, multiple-output broadcast channel. By using recently discovered properties of this problem, we derive a closed-form expression for the optimal power allocation in the two-user scenario and propose a conceptually simple and efficient algorithm that handles an arbitrary number of users. Throughout the thesis we show that there are significant gains if the parts of the system are jointly optimized for the source and channel statistics. All methods that are considered in this thesis yield very low coding and decoding delays. In general, nonlinear mappings outperform linear mappings for problems where there is side-information available. Another contribution of this thesis is visualization of numerically optimized systems that can be used as inspiration when structured low-delay systems are designed. / The author changed name from Johannes Karlsson to Johannes Kron in January 2011. QC 20110512

info:eu-repo/semantics/nonPublished

L'augmentation du trafic sur les réseaux sans fil ne permet plus de traiter les données en utilisant les protocoles standard des réseaux filaires, qui sont eux sans interférences. Ainsi, les nœuds des réseaux sans fil doivent coopérer en exploitant les corrélations inhérentes à la proximité des utilisateurs afin d'exploiter au mieux la capacité d'un tel réseau.Dans cette thèse, nous considérons tout d'abord le problème de codage de source avec information adjacente compressée. Le nœud coopératif, ayant accès à un signal corrélé avec celui de la source, peut en envoyer une version compressée au destinataire sur un lien indépendant, permettant d'économiser du débit sur le lien principal. En utilisant une caractérisation des cellules de Voronoi du quantificateur utilisé, nous avons pu améliorer un algorithme de décodage itératif basé sur des codes LDPC.La seconde partie de la thèse traite des problèmes de codage de canal, où les nœuds coopératifs sont des relais. L'exemple le plus simple d'une telle communication est le canal à relais, où un relais aide à la communication entre la source et la destination. Alors que dans le problème de codage de source, le canal de corrélation entre la source et le nœud coopératif est fixé, dans le codage de canal, la question est de savoir quelle opération effectuer au relais. Tout d'abord, nous considérons un problème quelque peu dual au problème de codage de source avec information adjacente compressée, en considérant des bruits corrélés au relais et la destination. Puis, nous étudions des bornes sur la capacité et des débits atteignables pour deux extensions du canal à relais, le canal à relais bidirectionnel avec des bruits corrélés au relais et aux destinations, où deux sources échangent leurs données avec l'aide d'un relais, et le canal multidirectionnel avec liens directs (qui modélisent la proximité des utilisateurs), où les utilisateurs sont regroupés dans des clusters et échangent leurs données localement au sein d'un même cluster avec l'aide d'un relais. / The current wireless data traffic growth cannot be handled by classical multi-hop network protocols as in interference-free wired networks, thus it has been recognized that network nodes need to cooperate in order to take advantage of source and/or channel signal correlations, which is needed to achieve fundamental capacity limits.This thesis first considers a cooperative source coding problem, namely binary source coding with coded side information (CoSI): the helper node has access to a signal that is correlated with the source and may send a compressed version on a separate link to the destination, thus rate can be saved on the main source-destination link. Using a characterization of the Hamming-space Voronoi regions of the quantizer at the helper node, an improved practical scheme based on LDPC codes is proposed.The second part of the thesis considers cooperative channel coding, where helper nodes are relays. The simplest example of such a communication is the relay channel, in which a relay node helps the source to send its message to the destination. Whereas in the source coding problem, the correlation between source and side information is given, in channel coding, the main question is to find the best relaying operation. First, a somewhat dual problem to source coding with CoSI is studied, by considering correlated noises at the relay and destination. Then, various extensions of the relay channel are characterized using upper bounds on capacity and achievable rates: the two-way relay channel with correlated noises at the relay and destinations, where two sources wish to exchange their data with the help of a relay, and the multiway relay channel with direct links, where users, grouped into fully connected clusters (users in a cluster can overhear each others' messages), wish to exchange their messages locally within a cluster with the help of one relay.

We are concerned with addressing the worst-case distributed source coding (DSC) problem in asymmetric and interactive communication scenarios and its application to data-gathering wireless sensor networks in enhancing their lifetime. First, we propose a unified canonical framework, obtained by considering different communication constraints and objectives, to address the variants of DSC problem. Second, as for the worst-case information-theoretic analysis, the notion of information entropy cannot be used, we propose information ambiguity, derive its various properties, and prove that it is a valid information measure. Third, for a few variants of our interest of DSC problem, we provide the communication protocols and prove their optimality. In a typical data-gathering sensor network, the base-station that wants to gather sensor data is often assumed to be much more resourceful with respect to energy, computation, and communication capabilities compared to sensor nodes. Therefore, we argue that in such networks, the base-station should bear the most of the burden of communication and computation in the network. Allowing the base-station and sensor nodes to interactively communicate with each other enables us to carry this out. Our definition of sensor network lifetime allows us to reduce the problem of maximizing the worst-case network lifetime to the problem of minimizing the number of bits communicated by the nodes in the worst-case, which is further reduced to the worst-case DSC problem in asymmetric and interactive communication scenarios, with the assumption that the base-station knows the support-set of sensor data. We demonstrate that the optimal solutions of the energy-oblivious DSC problem variants cannot be directly applied to the data-gathering sensor networks, as those may be inefficient in the energy-constrained sensor networks. We address a few energy-efficient variants of DSC problem and provide optimal communication protocols for the sensor networks, based on those variants. Finally, we combine distributed source coding with two other system level opportunities of channel coding and cooperative nature of the nodes to further enhance the lifetime of the sensor networks. We address various scenarios and demonstrate the dependence of the computational complexity of the network lifetime maximization problem on the complex interplay of above system-level opportunities.