On Bandwidth-Efficient Data Broadcast.

In this paper, we leverage network coding (NC) to reduce the bandwidth consumption for data broadcast (DB). We use the concept of mixing in a different way from the traditional NC. Traditional NC mixes all data items together. However, we mix each data item from only some data items according to the queried and stored data of receivers. Therefore, each receiver in our approach is required to receive fewer coded data to decode the required information, and the sender, thereby, is able to broadcast fewer data items. We formulate an optimization problem with integer-linear programming to minimize the bandwidth consumption in DB. We prove that the problem is NP-hard and design an approximation algorithm that can be implemented in the data server. In addition, we show that different mixings of data items lead to different decoding costs for receivers. We design an algorithm to optimally code the data items with the minimum decoding cost. [ABSTRACT FROM AUTHOR]