Algorithms on Wireless Network Coding

Network coding is a novel technique that has a significant potential to improve throughput, robustness and security of both wireless and wireline networks. With network coding the intermediate nodes in the network have the capability to combine multiple incoming packets and forward the resulting packets over their outgoing links. This technique has a significant advantage over traditional methods such as forwarding and duplication of packets. Recently, the network coding technique has attracted a significant interest from the research community. In this dissertation, we address a number of wireless network coding problems. In particular, our work focuses on the Cooperative Data Exchange (CDE), one of the central problems in wireless network coding. In Cooperative Data Exchange, a group of clients that have a prior side information about a set of packets use a shared broadcast channel to recover the missing packets from the set. We focus on different variations of the problem, including data exchange in the presence of passive and active adversaries, data exchange subject to deadlines, as well as serving clients of different priority classes. For each variation, we analyze the complexity of the problem and present exact or approximation algorithms for its solution. We show that this set of problem is very rich and has deep connections to different areas of coding theory, algebraic geometry, and information theory