Time slicing in mobile TV broadcast networks with arbitrary channel bit rates

Mobile TV networks have received significant attention from the industry and academia, as they have already been deployed in several countries and their expected market potential is huge. In such networks, a base station broadcasts TV channels in bursts with bit rates much higher than the encoding bit rates of the videos. This enables mobile receivers to receive a burst of traffic and then turn off their receiving circuit till the next burst to conserve energy. The base station needs to construct a transmission schedule for all bursts of different TV channels. Constructing optimal (in terms of energy saving) transmission schedules has been shown to be an NP-complete problem when the TV channels are encoded at arbitrary bit rates. In this paper, we propose a near-optimal approximation algorithm to solve this problem. We prove the correctness of the proposed algorithm and derive its approximation factor. We also conduct extensive evaluation of our algorithm using real implementation in a mobile TV testbed and simulations. Our experimental and simulation results show that the proposed algorithm: (i) is practical and produces correct burst schedules, (ii) achieves near-optimal energy saving for mobile devices, and (iii) runs efficiently in real time.