End-to-End Delay Analysis in Wireless Network Coding: A Network Calculus-Based Approach

Network coding provides a powerful mechanism for improving performance of wireless networks. In this paper, we present an analytical approach for end-to-end delay analysis in wireless networks that employ inter-session coding. Prior work on performance analysis in wireless network coding mainly focuses on the throughput of the overall network. Our approach aims to analyze the end-to-end delay performance of each flow in the network. The theoretical basis of our approach is network calculus. In order to apply network calculus to the analysis of wireless network coding, we address three specific problems: identifying traffic flows, characterizing broadcast links, and measuring coding opportunities. We make three main contributions. First, we obtain theoretical formulations for computing the delay bounds of bursty flows in wireless networks employing network coding. Second, based on the formulations, we figure out the factors that affect the end to end delays, and find an interesting phenomenon that, as traffic grows, the overall delay can potentially decrease. Third, in order to exploit the benefit of our findings, we introduce a new scheduling scheme that can improve the performance of current practical wireless network coding.