A Data Partition Based Near Optimal Scheduling Algorithm for Wireless Multi-channel Data Broadcast

Ping Yu, Weiwei Sun, Yongrui Qin, Zhuoyao Zhang, Bole Shi

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Citation (Scopus)

Abstract

Data broadcast is an efficient way to disseminate information to large numbers of users in wireless environments. The Square Root Rule (SRR) is the theoretical basis for the single channel broadcast scheduling. In this paper, we extend the SRR and propose the Multi-channel Square Root Rule (MSRR) for scheduling variable-length data with skewed access probabilities on variable-bandwidth channels. The theoretical optimal average access latency is also provided. However, this optimal value can not be achieved in reality. Based on MSRR, we provide a two-phase scheduling algorithm which achieves near optimal access latency. First data are partitioned and allocated to different channels according to MSRR. Second, different scheduling strategies are adopted on each channel according to the skewness of data subset allocated on that channel. Experiments show that the difference of average access latency between our results and the optimal value is below five percent in most situations.

Original languageEnglish
Title of host publicationDatabase Systems for Advanced Applications
Subtitle of host publication13th International Conference, DASFAA 2008, New Delhi, India, March 19-21, 2008. Proceedings
EditorsJayant R. Haritsa, Ramamohanarao Kotagiri, Vikram Pudi
PublisherSpringer-Verlag Berlin Heidelberg
Pages188-203
Number of pages16
ISBN (Electronic)9783540785682
ISBN (Print)3540785671, 9783540785675
DOIs
Publication statusPublished - 2008
Externally publishedYes
Event13th International Conference on Database Systems for Advanced Applications - New Delhi, India
Duration: 19 Mar 200821 Mar 2008
Conference number: 13
https://dl.acm.org/doi/proceedings/10.5555/1802514

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
PublisherSpringer-Verlag Berlin Heidelberg
Volume4947 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference13th International Conference on Database Systems for Advanced Applications
Abbreviated titleDASFAA 2008
CountryIndia
CityNew Delhi
Period19/03/0821/03/08
Internet address

    Fingerprint

Cite this

Yu, P., Sun, W., Qin, Y., Zhang, Z., & Shi, B. (2008). A Data Partition Based Near Optimal Scheduling Algorithm for Wireless Multi-channel Data Broadcast. In J. R. Haritsa, R. Kotagiri, & V. Pudi (Eds.), Database Systems for Advanced Applications: 13th International Conference, DASFAA 2008, New Delhi, India, March 19-21, 2008. Proceedings (pp. 188-203). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4947 LNCS). Springer-Verlag Berlin Heidelberg. https://doi.org/10.1007/978-3-540-78568-2_16