Network Coding for Sensor Networks, Distributed Storage and Video Streaming

A new generalized approach to routing called Network Coding (NC) allows the intermediate routers to modify and combine packets from different sources and destinations in such a way that increases the overall throughput. This dissertation aims to develop the theories and applications of NC via four main thrusts: (1) Energy efficient NC techniques for sensor networks, (2) Novel NC techniques and protocols for Internet video streaming, (3) Stochastic data replenishment for large scale NC-based distributed storage systems, (4) Real-world implementation of NC-based distributed video streaming system.;In thrust one, we describe a novel cross-sensor coding technique that combines network topology and coding techniques to maximize the life-time of a sensor network, by addressing the uneven energy consumption problem in data gathering sensor networks where the nodes closer to the sink tend to consume more energy than those of the farther nodes. Our approach is based on the following observation from the sensor networks using On-Off Keying and digital transmission: transmitting bit "1" consumes much more energy than bit "0". Our proposed coding technique exploits this difference to reduce the communication energy by limiting the number of bits "1" in the output codeword (low-weight codeword) and to use NC-based cross-sensor coding technique to equalize the communication energy among the nodes. This cross-sensor coding scheme can significantly extend the network lifetime as compared with traditional (binary) coding by solving the energy-consumption unfairness problem.;In thrust two, we describe a rate distortion aware hierarchical NC technique and transport protocol for Internet video streaming. We begin by proposing a NC-based multi-sender streaming framework that reduces the overall storage, eliminates the complexity of sender synchronization, and enables TCP streaming. Furthermore, we propose a Hierarchical Network Coding (HNC) technique that facilitates scalable video streaming to combat bandwidth fluctuation on the Internet. This HNC technique enables receiver to recover the important data gracefully in the presence of limited bandwidth which causes an increase in decoding delay. Simulations demonstrate that under certain scenarios, our proposed NC techniques can result in bandwidth saving up to 60% over the traditional schemes.;In thrust three, we present a theory of NC-based data replenishment to automate the process of data maintenance for large scale distributed storage systems. The data replenishment mechanism is the core of these systems that promises to reduce the coordination complexity and increases performance scalability. The data replenishment automates the process of maintaining a sufficient level of data redundancy to ensure the availability of data in presence of peer departures and failures. The dynamics of peers entering and leaving the network is modeled as a stochastic process. We propose a novel analytical time-backward technique to bound the expected time, the longer the better, for a piece of data to remain in P2P systems. Both theoretical and simulation results are in agreement, indicating that our proposed data replenishment via random linear network coding (RLNC) outperforms other popular strategies that employ repetition and channel coding techniques. Specifically, we show that the expected time for a piece of data to remain in a P2P system is exponential in the number of peers used to store the data for the RLNC-based strategy, while they are quadratic for other strategies. Furthermore, the time-backward technique can be applied to problems in other disciplines such as gene population modeling in theoretical biology.;Finally in thrust four, we present the architecture, design, and experimental results of an actual NC-based distributed video streaming system. We first implement random linear network coding (RLNC) library and show the feasibility of using RLNC in P2P video streaming applications. Then we design, implement and analyze RESnc---a resilient P2P video storage and streaming over the Internet using network coding. RESnc increases the streaming throughput and data resiliency against peer departures and failures using peer diversity. (Abstract shortened by UMI.)...