Coding-based data broadcast scheduling in on-demand broadcast

According to data broadcast, we can satisfy multiple requests for the same data item in a broadcast tick. However, there is no significant breakthrough in performance improvement until recently that some studies proposed to use network coding in data broadcast. After broadcasting an encoded packet which encodes a number of data items, multiple clients can retrieve different requested data items in a broadcast tick. This not only utilizes bandwidth more efficiently, but also improves system performance. In this work, we propose a generalized encoding framework to incorporate network coding into data scheduling algorithms for on-demand broadcast. In the framework, data scheduling can be formulated as a weighted maximum clique problem in a graph where the weight of the clique is defined according to the performance objectives of the applications. Under the proposed framework, existing data scheduling algorithms for on-demand broadcast can be migrated into their corresponding coding versions while preserving their original criteria in scheduling data items. Our simulation results using a number of representative scheduling algorithms show that significant performance improvement can be achieved with coding. © 2006 IEEE.