Optimal scheduling with pairwise coding under heterogeneous delay constraints

Network coding has the potential to provide powerful support to transmit real-time traffic in wireless network. In this paper, we utilize pairwise coding to schedule the flows which have heterogeneous delay constraints and weights. Our goal is to maximize the weighted sum of scheduled packets that satisfy the delay constraints. We formulate the problem as an integer linear programming problem, and propose two algorithms to solve it. The first algorithm drops the integral constraints and rounds the fractional solutions in such a way that the rounded solution is also optimal. Inspired by the first algorithm and for better running time, we propose the second algorithm based on a minimum cost flow formulation. The formulation is proved to be equivalent to the original integer linear programming formulation. Simulations are conducted to show the effectiveness of our approach over two greedy algorithms.