The emerging wireless media delivery services have placed greater demands for wireless networks to support highthroughput applications while minimizing the delay of individual packets. In this paper, we investigate using inter-session network coding to send packets wirelessly for two deadline-constrained unicast sessions. Specifically, each unicast session aims to transmit a stored video file, whose packets have hard sequential deadline constraints. We first characterize the corresponding deadlineconstrained capacity region under heterogeneous channel conditions and heterogeneous deadline constraints. We show that this deadline-constrained capacity region can be achieved asymptotically by modifying the existing generation-based schemes. Despite its asymptotic optimality, the generation-based scheme has poor performance and high complexity in the practical regime small & medium file sizes. To address these problems, we further develop new immediately-decodable network coding (IDNC) schemes that admit superior performance in the practical regime while being provably optimal in the asymptotic regime. In contrast to the existing delay/deadline-based IDNC results, which focus on a single multicast session (intra-session network coding) with homogeneous channel conditions, our new IDNC design takes full account of channel heterogeneity and provides the first rigorous asymptotic optimality analysis for two unicasts with (potentially heterogeneous) hard deadline constraints.
Date of this Version