Coding based wireless broadcast scheduling in real time applications

Using network coding in wireless networks can increase throughput and reduce energy consumption. However there are only a few works considering the quality of service which is important to real time applications. This paper focuses on network coding based broadcast scheduling problem in real time wireless networks with packet delay constraint and aims at minimizing the number of packets which miss their deadlines under two receiver models. In the first model, receiver drops the encoded packet which cannot be decoded immediately. We formulate the broadcast scheduling problem with an integer linear programming and prove that it is NP-hard. We also propose a packet encoding and broadcasting algorithm based on the maximum weight clique in the graph. In the second model, receiver can buffer all received encoded packets and decode out their wanted packets when enough packets are received. According to marking colors on the vertices of the weighted graph, an effective heuristic algorithm is proposed in this paper. Simulation results show that our algorithm significantly reduces the deadline miss ratio in most cases, which is an important performance metric in real time applications.