Delay Aware Broadcast Scheduling in Wireless Networks Using Network Coding

Using network coding in wireless networks can increase throughput and reduce energy consumption. Recently there are many works focusing on how to utilize network coding to increase throughput while there are few works considering the quality of service such as delay. This paper focuses on network coding based broadcast scheduling in wireless networks with the packet delay constraint and aims at minimizing the number of packets which miss their deadlines. Every client needs some packets and has already had some packets in the cache, we propose a graph model to describe the relationship between these packets. By assigning vertex weight as a decreasing function of packet deadline, we propose an encoding algorithm based on the maximum weight clique in the graph to help the sender decide how to broadcast. Simulation results show that our algorithm can reduce the deadline miss ratio which is an important performance metric in the delay sensitive applications.