Analysis and design of deterministic network coding

Abstract

In this thesis, we are concerned with the analysis and design of deterministic network coding schemes in a single hop wireless broadcast network. We analyse the throughput delay performance achieved under existing transmission schemes in the literature, and obtain insights into the characteristics of network coding schemes that allow them to achieve good performance. We use the results of our analysis to design a new transmission scheme that dynamically balances throughput and delay requirements to achieve improved performance, and derive a low feedback adaptation of this scheme, for use in practical applications with limited feedback. We introduce the notion of intermediate packet delivery, where packets may be decoded in the correct order by receivers who have received incomplete information from the sender. We show that assumptions used to determine the capacity bounds in the literature do not always apply under intermediate packet delivery, and it is possible for the rate to exceed the min-cut bound. We will demonstrate how intermediate packet delivery can be used to achieve simultaneous multi-rate delivery under non-uniform receiver channel rates, and transmission optimal asynchronous packet delivery under uniform channel rates. We design a fairness algorithm that allocates the sender's resources so all receivers experience fair delivery rate performance.