article

On burst transmission scheduling in mobile TV broadcast networks

Authors:

Mohamed Hefeeda,

Cheng-Hsin HsuAuthors Info & Claims

IEEE/ACM Transactions on Networking (TON), Volume 18, Issue 2

Pages 610 - 623

https://doi.org/10.1109/TNET.2009.2030326

Published: 01 April 2010 Publication History

Abstract

In mobile TV broadcast networks, the base station broadcasts TV channels in bursts such that mobile devices can receive a burst of traffic and then turn off their radio frequency circuits till the next burst in order to save energy. To achieve this energy saving without scarifying streaming quality, the base station must carefully construct the burst schedule for all TV channels. This is called the burst scheduling problem. In this paper, we prove that the burst scheduling problem for TV channels with arbitrary bit rates is NP-complete.We then propose a practical simplification of the general problem, which allows TV channels to be classified into multiple classes, and the bit rates of the classes have power of two increments, e.g., 100, 200, and 400 kbps. Using this practical simplification, we propose an optimal and efficient burst scheduling algorithm. We present theoretical analysis, simulation, and actual implementation in a mobile TV testbed to demonstrate the optimality, practicality, and efficiency of the proposed algorithm.

References

[1]

Digital Video Broadcasting - Handheld (DVB-H) Home Page, 2008 {Online}. Available: http://www.dvb-h.org/

[2]

G. May, "The IP Datacast system--Overview and mobility aspects," in Proc. IEEE ISCE, Reading, U.K., Sep. 2004, pp. 509-514.

[3]

M. Kornfeld and G. May, "DVB-H and IP Datacast--Broadcast to handheld devices," IEEE Trans. Broadcast., vol. 53, no. 1, pt. 2, pp. 161-170, Mar. 2007.

[4]

Digital Video Broadcasting (DVB); Transmission System for Hand-held Terminals (DVB-H), Standard EN 302 304 Ver. 1.1.1, European Telecommunications Standards Institute (ETSI), Nov. 2004.

[5]

"FLO technology overview," 2009 {Online}. Available: http://www. mediaflo.com/news/pdf/tech_overview.pdf

[6]

Digital Video Broadcasting (DVB); DVB-H Implementation Guidelines, Standard EN 102 377 Ver. 1.3.1, European Telecommunications Standards Institute (ETSI), May 2007.

[7]

F. Hartung, U. Horn, J. Huschke, M. Kampmann, T. Lohmar, and M. Lundevall, "Delivery of broadcast services in 3G networks," IEEE Trans. Broadcast., vol. 53, no. 1, pt. 2, pp. 188-199, Mar. 2007.

[8]

S. Cho, G. Lee, B. Bae, K. Yang, C. Ahn, S. Lee, and C. Ahn, "System and services of terrestrial digital multimedia broadcasting (T-DMB)," IEEE Trans. Broadcast., vol. 53, no. 1, pt. 2, pp. 171-178, Mar. 2007.

[9]

M. Takada and M. Saito, "Transmission system for ISDB-T," Proc. IEEE, vol. 94, no. 1, pp. 251-256, Jan. 2006.

[10]

G. Faria, J. Henriksson, E. Stare, and P. Talmola, "DVB-H: Digital broadcast services to handheld devices," Proc. IEEE, vol. 94, no. 1, pp. 194-209, Jan. 2006.

[11]

Radio Broadcasting Systems: Digital Audio Broadcasting (DAB) to Mobile, Portable and Fixed Receivers, Standard EN 300 401 Ver. 1.3.3, European Telecommunications Standards Institute (ETSI), May 2001.

[12]

FLO forum home page, 2008 {Online}. Available: http://www.floforum. org/

[13]

"DVB-H global mobile TV: FAQ," 2008 {Online}. Available: http:// dvb-h.org/faq.htm

[14]

Digital Video Broadcasting (DVB); Framing Structure, Channel Coding and Modulation for Digital Terrestrial Television, Standard EN 300 744 Ver. 1.5.1, European Telecommunications Standards Institute (ETSI), Jun. 2004.

[15]

E. Tan, L. Guo, S. Chen, and X. Zhang, "PSM-throttling: Minimizing energy consumption for bulk data communications in WLANs," in Proc. IEEE ICNP, Beijing, China, Oct. 2007, pp. 123-132.

[16]

X. Yang, Y. Song, T. Owens, J. Cosmas, and T. Itagaki, "Performance analysis of time slicing inDVB-H," in Proc. Joint IST Workshop Mobile Future SympoTIC, Bratislava, Slovakia, Oct. 2004, pp. 183-186.

[17]

E. Balaguer, F. Fitzek, O. Olsen, and M. Gade, "Performance evaluation of power saving strategies for DVB-H services using adaptive MPE-FEC decoding," in Proc. IEEE PIMRC, Berlin, Germany, Sep. 2005, pp. 2221-2226.

[18]

Q. Zhang, F. Fitzek, and M. Katz, "Cooperative power saving strategies for IP-services supported over DVB-H networks," in Proc. IEEE WCNC, Hong Kong, China, Mar. 2007, pp. 4107-4111.

[19]

M. Kornfeld, "Optimizing the DVB-H time interleaving scheme on the link layer for high quality mobile broadcasting reception," in Proc. IEEE ISCE, Dallas, TX, Jun. 2007, pp. 1-6.

[20]

V. Vadakital, M. Hannuksela, and M. Gabbouj, "Time-interleaved simulcast and redundant intra picture insertion for reducing tune-in delay in DVB-H," in Proc. PV, Lausanne, Switzerland, Nov. 2007, pp. 123-132.

[21]

M. Rezaei, M. Hannuksela, and M. Gabbouj, "Tune-in time reduction in video streaming over DVB-H," IEEE Trans. Broadcast., vol. 53, no. 1, pt. 2, pp. 320-328, Mar. 2007.

[22]

M. Rezaei, I. Bouazizi, and M. Gabbouj, "Joint video coding and statistical multiplexing for broadcasting over DVB-H channels," IEEE Trans. Multimedia, vol. 10, pp. 1455-1464, Dec. 2008.

Digital Library

[23]

M. Rezaei, M. Hannuksela, and M. Gabbouj, "Video encoding and splicing for tune-in time reduction in IP datacasting (IPDC) over DVB-H," in Proc. IEEE ICME, Toronto, ON, Canada, Jul. 2006, pp. 601-604.

[24]

M. Rezaei, M. Hannuksela, and M. Gabbouj, "Video splicing and fuzzy rate control in IP multi-protocol encapsulator for tune-in time reduction in IP datacasting (IPDC) over DVB-H," in Proc. IEEE ICIP, Atlanta, GA, Oct. 2006, pp. 3041-3044.

[25]

T. Wiegand, G. Sullivan, G. Bjntegaard, and A. Luthra, "Overview of the H.264/AVC video coding standard," IEEE Trans. Circuits Syst. Video Technol., vol. 13, no. 7, pp. 560-576, Jul. 2003.

Digital Library

[26]

"Advanced video coding for generic audiovisual services," Joint Video Team, 2005, ITU-T Rec. H.264 & ISO/IEC 14496-10 AVC.

[27]

Digital Video Broadcasting (DVB); IP Datacast Over DVB-H: Content Delivery Protocol, Standard EN 102 472 Ver. 1.1.1, European Telecommunications Standards Institute (ETSI), Nov. 2006.

[28]

Digital Video Broadcasting (DVB); DVB Specification for Data Broadcasting, Standard EN 301 192 Ver. 1.4.1, European Telecommunications Standards Institute (ETSI), Jun. 2004.

[29]

M. Garey and D. Johnson, Computers and Intractability: A Guide to The Theory of NP-Completeness. San Francisco, CA: Freeman, 1979.

Digital Library

[30]

P. Brucker, Scheduling Algorithms, 4th ed. New York: Springer, 2004.

Digital Library

[31]

Y. Bartal, S. Leonardi, and G. S. R. Sitters, "On the value of preemption in scheduling," in Proc. Workshop APPROX, Barcelona, Spain, Aug. 2006, pp. 39-48.

Digital Library

[32]

O. Braun and G. Schmidt, "Parallel processor scheduling with limited number of preemptions," SIAM J. Comput., vol. 32, no. 3, pp. 671-680, 2003.

Digital Library

[33]

R. Motwani, S. Phillips, and E. Torng, "Nonclairvoyant scheduling," Theor. Comput. Sci., vol. 130, no. 1, pp. 17-47, Aug. 1994.

Digital Library

[34]

U. Schwiegeishohn, "Preemptive weighted completion time scheduling of parallel jobs," in Proc. ESA, Barcelona, Spain, Sep. 1996, pp. 39-51.

Digital Library

[35]

P. Chou, "Streaming media on demand and live broadcast," in Multimedia Over IP and Wireless Networks, M. van der Schaar and P. Chou, Eds. New York: Academic, 2007, ch. 14, pp. 453-502.

[36]

"Nokia mobile broadcast solution," Feb. 2009 {Online}. Available: http://www.mobiletv.nokia.com/solutions/mbs/

[37]

Private communication with Nokia's engineers managing mobile TV base stations, Dec. 2008.

[38]

Dektec DTA-110T PCI modulator, 2008 {Online}. Available: http:// www.dektec.com/Products/DTA-110T/

[39]

"FATCAPS project," 2008 {Online}. Available: http://amuse.ftw.at/ downloads/encapsulator

[40]

"Divi catch RF-T/H transport stream analyzer," 2008 {Online}. Available: http://www.enensys.com/

[41]

"Joint scalable video model reference software. ver. JSVM 14.0, Joint Video Team, May 2008.

[42]

P. Lambert, W. de Neve, P. de Neve, I. Moerman, P. Demeester, and R. van de Walle, "Rate-distortion performance of H.264/AVC compared to state-of-the-art video codecs," IEEE Trans. Circuits Syst. Video Technol., vol. 16, no. 1, pp. 134-140, Jan. 2006.

Digital Library

[43]

T. Wiegand, H. Schwarz, A. Joch, F. Kossentini, and G. Sullivan, "Rate-constrained coder control and comparison of video coding standards," IEEE Trans. Circuits Syst. Video Technol., vol. 13, no. 7, pp. 688-703, Jul. 2003.

Digital Library

Cited By

Li MChen H(2019)Energy-Efficient Traffic Regulation and Scheduling for Video Streaming Services Over LTE-A NetworksIEEE Transactions on Mobile Computing10.1109/TMC.2018.283642118:2(334-347)Online publication date: 1-Feb-2019
https://dl.acm.org/doi/10.1109/TMC.2018.2836421
Almowuena SHefeeda M(2016)Mobile Video Streaming over Dynamic Single-Frequency NetworksACM Transactions on Multimedia Computing, Communications, and Applications10.1145/298363512:5s(1-26)Online publication date: 2-Nov-2016
https://dl.acm.org/doi/10.1145/2983635
Shah RHefeeda MZimmermann RHarras KHsu CYu Y(2016)NEWSMANProceedings, Part I, of the 22nd International Conference on MultiMedia Modeling - Volume 951610.1007/978-3-319-27671-7_9(100-113)Online publication date: 4-Jan-2016
https://dl.acm.org/doi/10.1007/978-3-319-27671-7_9
Show More Cited By

Index Terms

On burst transmission scheduling in mobile TV broadcast networks

Recommendations

Using simulcast and scalable video coding to efficiently control channel switching delay in mobile tv broadcast networks

Many mobile TV standards dictate using energy saving schemes to increase the viewing time on mobile devices, since mobile receivers are battery powered. The most common scheme for saving energy is to make the base station broadcast the video data of a ...
The use of a triangular estimator to improve scheduling in optical burst switched networks

In an optical burst switched network, variable-sized data bursts are switched on the fly using bandwidth previously reserved by their control packets. A key problem in OBS networks is the assignment of wavelengths to incoming bursts, that is, the ...
Approximation scheme for burst scheduling with minimum overhead in time slicing mobile TV

In this paper, we consider the problem of minimizing switching overhead of burst scheduling in time slicing mobile TV broadcast systems. This problem was formulated by Hsu and Hefeeda, and was given an elegant approximation scheme with an approximation ...

Comments

Information & Contributors

Information

Published In

cover image IEEE/ACM Transactions on Networking

IEEE/ACM Transactions on Networking Volume 18, Issue 2

April 2010

339 pages

ISSN:1063-6692

Issue’s Table of Contents

Publisher

IEEE Press

Publication History

Published: 01 April 2010

Revised: 18 May 2009

Received: 24 October 2008

Published in TON Volume 18, Issue 2

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

12
Total Citations
View Citations
317
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)0

Reflects downloads up to 14 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Li MChen H(2019)Energy-Efficient Traffic Regulation and Scheduling for Video Streaming Services Over LTE-A NetworksIEEE Transactions on Mobile Computing10.1109/TMC.2018.283642118:2(334-347)Online publication date: 1-Feb-2019
https://dl.acm.org/doi/10.1109/TMC.2018.2836421
Almowuena SHefeeda M(2016)Mobile Video Streaming over Dynamic Single-Frequency NetworksACM Transactions on Multimedia Computing, Communications, and Applications10.1145/298363512:5s(1-26)Online publication date: 2-Nov-2016
https://dl.acm.org/doi/10.1145/2983635
Shah RHefeeda MZimmermann RHarras KHsu CYu Y(2016)NEWSMANProceedings, Part I, of the 22nd International Conference on MultiMedia Modeling - Volume 951610.1007/978-3-319-27671-7_9(100-113)Online publication date: 4-Jan-2016
https://dl.acm.org/doi/10.1007/978-3-319-27671-7_9
CHEN C(2015)Editorial: On Building a Stronger Multimedia CommunityIEEE Transactions on Multimedia10.1109/TMM.2015.250501918:1(1-3)Online publication date: 14-Dec-2015
https://dl.acm.org/doi/10.1109/TMM.2015.2505019
Almowuena SRahman MHsu CHassan AHefeeda M(2015)Energy-Aware and Bandwidth-Efficient Hybrid Video Streaming Over Mobile NetworksIEEE Transactions on Multimedia10.1109/TMM.2015.250206718:1(102-115)Online publication date: 14-Dec-2015
https://dl.acm.org/doi/10.1109/TMM.2015.2502067
Ya-Ju Yu Ai-Chun Pang Pi-Cheng Hsiu Yuguang Fang (2015)Energy-Adaptive Downlink Resource Allocation in Wireless Cellular SystemsIEEE Transactions on Mobile Computing10.1109/TMC.2014.236901614:9(1833-1846)Online publication date: 1-Sep-2015
https://dl.acm.org/doi/10.1109/TMC.2014.2369016
Kik MGebala MKutyłowski M(2013)Bit Reversal Broadcast Scheduling for Ad Hoc SystemsProceedings of the 6th International Conference on Internet and Distributed Computing Systems - Volume 822310.1007/978-3-642-41428-2_18(223-237)Online publication date: 28-Oct-2013
https://dl.acm.org/doi/10.1007/978-3-642-41428-2_18
Li XDong MMa ZFernandes FBabaguchi NAizawa KSmith JSatoh SPlagemann THua XYan R(2012)GreenTubeProceedings of the 20th ACM international conference on Multimedia10.1145/2393347.2393390(279-288)Online publication date: 29-Oct-2012
https://dl.acm.org/doi/10.1145/2393347.2393390
Hefeeda MHsu C(2012)Design and evaluation of a testbed for mobile TV networksACM Transactions on Multimedia Computing, Communications, and Applications10.1145/2071396.20713998:1(1-23)Online publication date: 3-Feb-2012
https://dl.acm.org/doi/10.1145/2071396.2071399
Tabrizi FPeters JHefeeda M(2011)Adaptive transmission of variable-bit-rate video streams to mobile devicesProceedings of the 10th international IFIP TC 6 conference on Networking - Volume Part II10.5555/2008826.2008846(213-224)Online publication date: 9-May-2011
https://dl.acm.org/doi/10.5555/2008826.2008846
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents