Delay Reduction for Instantly Decodable Network Codes With Lossy Feedback Channels

In this paper, we study the decoding delay reduction problem for instantly decodable network coding (IDNC) with lossy feedback channels. In order to characterize the uncertainty of the reception state due to erasure feedback, we develop a statistical model of the state feedback matrix, whose elements are employed to indicate the likelihood of the reception status evaluated by the sender. The statistical model of the state feedback matrix can be updated according to the Markov model. With the established statistical model of the state feedback matrix, we build the statistical model of the IDNC graph, which can be used to indicate the likelihood of the coding opportunities among the vertices in the IDNC graph. The decoding delay reduction problem can be formulated as a maximum weight clique (MWC) problem. We develop two heuristic algorithms to solve the MWC problem, namely the maximum weight vertex (MWV) search and the approximate maximum weight path based MWV (A-MWP-MWV) search. Simulation results show that our proposed scheme based on statistical reception status model outperforms the scheme which keeps the reception state unchanged due to lossy feedback in estimating the reception status, and A-MWP-MWV outperforms MWV in solving the MWC problem without increasing additional complexity.