Wireless Network Coding

The theory of network coding was established by R. Ahlswede, N. Cai, S.-Y. R. Li, and R. W. Yeung in around 2000. This result is an important extension of C. E. Shannon's point to point communication theory to complex networks. The in-node signal processing cost in modern communication system is becoming more and more cheaper while the finite frequency spectrum resources are facing more and more communication demands. Network coding theory can be viewed as exchanging the in-node computation cost for network throughput, which immediately arises lots of attentions since its birth. However, there are two big difficulties in putting the beautiful theory into practice. First, practical networks are significantly different from the ideal model used in establishing network coding theory. If those practical issues cannot be well solved, the throughput gain from network coding will be limited. Second, linear network coding explicitly assumes that the underlying supporting network is lossless. It is a challenging task to apply the theory into wireless environment, due to the fading and broadcasting characters of wireless channels. This thesis solves the key problems when applying network coding into wireless networks. It presents the following three research achievements.In the first research achievement, I extend the traditional network coding in lossless networks which operates on 0-1 bits, to a new framework which defines network coding on the posterior probability of each bit. The major innovation of this research is that I propose a different approach to perform network coding in both Gaussian and fading channel that can fully utilize the independently observed information at the relay node even the relay cannot successfully decode the source message. Beyond the basic principle and applications, a new network code optimization algorithm is also proposed for the new framework.In the second research achievement, I study the optimal network code construction problem in wireless multicast under QoS constraints. Almost all previous works about network coding focus on the throughput gain without considering the QoS requirements. I formulate QoS-driven network coding as a stochastic optimization problem and establish the relationship among QoS constraints, network codeword, multicast client number, and clients' link conditions using large deviations principle. Given the client number and the links' average packet error rates, based on the relationship I establish, I propose a practical algorithm to calculate the optimal network codeword that supports the maximal source rate while satisfies the QoS constraints.In the third research achievement, I study network coded broadcast with multi-rate transmission, motivated by the unexpected observation that broadcast without network coding cannot achieve maximum throughput in wireless fading channels. The network coded broadcast poses new constraints for the receivers to manage stable queues while the fading channel characteristics require the broadcast to operate at multi-rate to achieve higher throughput. I propose a joint scheduling and network coding strategy for such network coded broadcast system to achieve maximum throughput under queue stability constraints. This strategy can be viewed as a generalization of the classical backpressure scheduling rule to coded information flow. Alternatively, it can also be viewed as an extension of network coding theory to queuing system.