Network coding for multi-user wireless networks

Until a few years ago, wireless-capable laptops were considered novelties by many. It is now hard to find a laptop or a hand-held computing device that is not wireless-ready. As wireless devices are becoming commodities, they have also become an indispensable part of the modern society. Not surprisingly, research in wireless communication has also been significantly advanced in the past decade, to accommodate the growing demand for these wireless devices and applications. Yet, many challenges remain in transmitting information reliably, timely, and efficiently over wireless channels. Unlike wired transmissions, wireless transmissions are subjected to limited bandwidth, and are much more susceptible to environmental noises such as fading and interferences. As a result, it is difficult to transmit information reliably at high data rates. The problem is further compounded by the strict requirements on maximum delay and minimum throughput imposed by current and future multimedia applications. That said, recent advances in coding techniques, communication protocols and architectures provide an optimistic view of future wireless networks that help proliferate high quality wireless multimedia applications. One significant advance in coding theory in the past decade is Network Coding (NC). NC refers to the notion of mixing information from different flows at intermediate nodes in the network, and it has been shown to achieve throughput capacity. In this dissertation, we investigate NC theories and practical techniques for improving throughput and reducing delay of wireless networking applications. Specifically, the dissertation will focus on theoretical analysis of NC benefits and limitations as well as design of NC-based practical protocols for improving performance in a wireless access network such as Wi-Fi or WiMax. There are three main contributions of the dissertation. First, we propose a NC-based retransmission protocol for broadcasting information from a wireless base station to multiple users in a wireless access network. The proposed NC protocol exploits the special property of wireless transmissions that users in proximity, can listen to each other's transmissions to code the packets in such a way to increase every user throughputs. Both theoretical analysis and simulation results show a significant throughput gain when using the proposed NC protocol over the standard ARQ protocol. Second, we propose a NC-based packet scheduler at a wireless base station for delivering multimedia streams, particularly scalable video streams to multiple users in a wireless access network. We formulate the NC-based packet scheduler problem in the framework of Markov Decision Process (MDP) in which, packet delay, inter-dependency of packets, and different visual contributions of packet types are taken into account, to optimize for the overall visual qualities. We describe an optimal scheduler for transmitting scalable video streams to a small number of users. For a large number of users, we propose a heuristic, simulation-based algorithm for finding the near-optimal transmission policy. Third, we introduce Random Network Coding (RNC) techniques. More specifically, we present a prioritized RNC scheme for multimedia transmissions for multi-user in a wireless access network. We then study a real-world implementation of RNC. We describe the step-by-step design of encoding and decoding modules of RNC and measure their computational rates.