Abstract
We consider the problem of broadcasting multiple variable-bit-rate (VBR) video streams from a base station to many mobile devices over a wireless network, so that: (i) perceived quality on mobile devices is maximized, (ii) bandwidth utilization is maximized, and (iii) energy consumption of mobile devices is minimized. We show that this problem is NP-Complete. We propose an approximation algorithm for the base station to statistically multiplex and transmit multiple VBR streams to achieve these objectives. We analytically analyze the performance of our algorithm and prove that it achieves optimal bandwidth utilization and near-optimal energy saving. Our algorithm frees network operators from the manual and error-prone bandwidth reservation process, which is usually used in practice for broadcasting VBR streams. We implement the proposed algorithm in a trace-driven simulator, and conduct extensive simulations. The simulation results show that our algorithm outperforms the existing algorithms in many aspects, including number of late frames, number of concurrently broadcast video streams, and energy saving of mobile devices. We also implement the proposed algorithm in a real testbed for video broadcasting as a proof of concept. The results from the testbed confirm that the proposed algorithm: (i) does not result in playout glitches, (ii) achieves high energy saving, and (iii) runs in real time. Copyright 2009 ACM.