Fundamental Limits Of Delay And Security In Device-To-Device Communication
Distributed communication poses novel challenges for efficient operation of such networks and requires design considerations that are fundamentally different from those of classical point-to-point communication systems. This thesis studies two such design issues, (1) delay management and (2) security, and attempts to understand the information-theoretic limits of distributed communication with regard to these issues. First, the tradeoff between delay and partial reconstruction in peer-to-peer (P2P) networks is studied, i.e., the number of messages a peer must obtain to reconstruct a given fraction of the data. Using a binary erasure version of the multiple descriptions (MD) problem to model the P2P network, the thesis presents coding schemes based on systematic MDS (maximum distance separable) codes and random binning strategies that achieve a Pareto optimal delayreconstruction tradeoff. The erasure MD setup is then used to propose a layered coding framework for MD, which is then applied to vector Gaussian MD and shown to be optimal for symmetric scalar Gaussian MD with two levels of receivers and no excess rate at the central receiver. Second, delay-reconstruction tradeoffs are studied for a more decentralized network in which peers are allowed to encode and generate their own messages based on their current partial knowledge of the file, and a coding scheme based on erasure compression and Slepian-Wolf binning is presented. The cod- ing scheme is shown to provide a Pareto optimal delay-reconstruction tradeoff for the case of symmetric peers (i.e., each peer generates packets of the same rate). In the process of characterizing the aforementioned tradeoff, an improved outer bound on the rate region of the general multi-terminal source coding problem from information theory is also established. It is further shown that in the case of asymmetric peers, the aforementioned coding scheme is not optimal. Third, lossy compression is studied from the viewpoint of security. An adversarial lossy source coding problem is considered in which a source is encoded into n packets, any t of which may be altered in an arbitrary way by Byzantine adversaries. The decoder receives the n packets and, without knowing which packets were altered, seeks to reconstruct the original source to meet a distortion constraint. A layered architecture for this problem is examined, which separates lossy compression from coding for adversarial errors. This architecture is shown to be optimal for binary sources with Hamming distortion and Gaussian sources with quadratic distortion, yet suboptimal in general. Finally, an adversarial 3-encoder lossless source coding problem with multiple sources is considered in which the number of packets corrupted by adversaries is unknown to the honest entities in the network. It is shown that this problem is equivalent to an instance of the symmetric MLD (multi-level diversity) coding problem with three sources and three encoders, in which there are no adversaries but the decoder may receive only a subset of the three messages and then reconstructs a subset of the three sources.
Wagner, Aaron B.
Avestimehr, Amir Salman; Wicker, Stephen B.; Tang, Ao
Ph. D., Electrical Engineering
Doctor of Philosophy
dissertation or thesis