Network Coding In Wireless Broadcast Networks

Since the advent of network coding, its theoretical benefits have been well recognized. However, so far none real applications have extensively employed network coding in practice. The imminent problems network coding introduces include large decoding delay, significant extra computation overhead and security concerns. This paper aims to address the first two problems in wireless broadcast networks.In the first place, to address the unfair decoding delay problem of existing schemes, we propose the rate-controlled network coding scheme (RANC), which can effectively reduce the decoding delay of the receiver suffering from a poor channel condition, without compromising the system throughput. Based on RANC, we further propose a moving window network coding with early loss alarm scheme (MWNC-ELA), which achieves similar decoding delay performance to RANC, but greatly simplifies its feedback mechanism. As a benchmark of MWNC-ELA, we analyze the decoding delay performance of RANC using random walk theory. Simulation results show that the proposed schemes outperform the existing solutions in terms of throughput, decoding delay and feedback overhead.Secondly, to address the problem that MWNC-ELA has no throughput guarantee, we re-design a dynamic MWNC-ELA scheme. We prove that the revised MWNC-ELA scheme can achieve any target throughput within the network capacity with finite average encoding window length. Moreover, we give analytical characterization of the feedback overhead incurred by MWNC-ELA. To meet the challenges in an environment, where the BS has no topology information about the networks, we propose moving window network coding with delay exceed alarm scheme (MWNC-DEA). The encoding of MWNC-DEA is determined by all the receivers in an online fashion. Simulation results show that MWNC-DEA can not only be compatible with no topology information, but also guarantee strict delay constraint for the receivers.Lastly, to avoid the efficiency degradation of feedback delay, we propose moving window network coding without explicit feedback scheme, which can guarantee high reliability without explicit feedback. Then, to address the bottleneck problem in single-hop wireless broadcasting, we study the optimal cooperative broadcast strategy and propose MWNCast. We prove three properties of MWNCast. Firstly, MWNCast can approach the cooperative capacity with packet loss ratio dropping almost exponentially with the increase of window size. Secondly, the average decoding delay of a receiver is on the order of O(1/(1-p)2with respect to the traffic intensity p. Thirdly, MWNCast can achieve the linear decoding complexity O(W) with respect to the window size W...