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

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

doi:10.1007/978-3-540-78568-2_16

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 proceeding › Conference contribution › peer-review

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 language	English
Title of host publication	Database Systems for Advanced Applications
Subtitle of host publication	13th International Conference, DASFAA 2008, New Delhi, India, March 19-21, 2008. Proceedings
Editors	Jayant R. Haritsa, Ramamohanarao Kotagiri, Vikram Pudi
Publisher	Springer-Verlag Berlin Heidelberg
Pages	188-203
Number of pages	16
ISBN (Electronic)	9783540785682
ISBN (Print)	3540785671, 9783540785675
DOIs	https://doi.org/10.1007/978-3-540-78568-2_16
Publication status	Published - 2008
Externally published	Yes
Event	13th International Conference on Database Systems for Advanced Applications - New Delhi, India Duration: 19 Mar 2008 → 21 Mar 2008 Conference number: 13 https://dl.acm.org/doi/proceedings/10.5555/1802514

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Publisher	Springer-Verlag Berlin Heidelberg
Volume	4947 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	13th International Conference on Database Systems for Advanced Applications
Abbreviated title	DASFAA 2008
Country/Territory	India
City	New Delhi
Period	19/03/08 → 21/03/08
Internet address	https://dl.acm.org/doi/proceedings/10.5555/1802514

Access to Document

10.1007/978-3-540-78568-2_16Licence: Unspecified

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

Yu, Ping ; Sun, Weiwei ; Qin, Yongrui et al. / A Data Partition Based Near Optimal Scheduling Algorithm for Wireless Multi-channel Data Broadcast. Database Systems for Advanced Applications: 13th International Conference, DASFAA 2008, New Delhi, India, March 19-21, 2008. Proceedings. editor / Jayant R. Haritsa ; Ramamohanarao Kotagiri ; Vikram Pudi. Springer-Verlag Berlin Heidelberg, 2008. pp. 188-203 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{0e015eedc259406a91e78bdda6c9b232,

title = "A Data Partition Based Near Optimal Scheduling Algorithm for Wireless Multi-channel Data Broadcast",

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.",

keywords = "Data broadcast, Data partition, Hybrid scheduling, Multiple channels, Wireless mobile environments",

author = "Ping Yu and Weiwei Sun and Yongrui Qin and Zhuoyao Zhang and Bole Shi",

year = "2008",

doi = "10.1007/978-3-540-78568-2_16",

language = "English",

isbn = "3540785671",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer-Verlag Berlin Heidelberg",

pages = "188--203",

editor = "Haritsa, {Jayant R.} and Ramamohanarao Kotagiri and Vikram Pudi",

booktitle = "Database Systems for Advanced Applications",

address = "Germany",

note = "13th International Conference on Database Systems for Advanced Applications, DASFAA 2008 ; Conference date: 19-03-2008 Through 21-03-2008",

url = "https://dl.acm.org/doi/proceedings/10.5555/1802514",

}

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 JR Haritsa, R Kotagiri & V Pudi (eds), Database Systems for Advanced Applications: 13th International Conference, DASFAA 2008, New Delhi, India, March 19-21, 2008. Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 4947 LNCS, Springer-Verlag Berlin Heidelberg, pp. 188-203, 13th International Conference on Database Systems for Advanced Applications, New Delhi, India, 19/03/08. https://doi.org/10.1007/978-3-540-78568-2_16

A Data Partition Based Near Optimal Scheduling Algorithm for Wireless Multi-channel Data Broadcast. / Yu, Ping; Sun, Weiwei; Qin, Yongrui et al.

Database Systems for Advanced Applications: 13th International Conference, DASFAA 2008, New Delhi, India, March 19-21, 2008. Proceedings. ed. / Jayant R. Haritsa; Ramamohanarao Kotagiri; Vikram Pudi. Springer-Verlag Berlin Heidelberg, 2008. p. 188-203 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4947 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

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

AU - Yu, Ping

AU - Sun, Weiwei

AU - Qin, Yongrui

AU - Zhang, Zhuoyao

AU - Shi, Bole

N1 - Conference code: 13

PY - 2008

Y1 - 2008

N2 - 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.

AB - 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.

KW - Data broadcast

KW - Data partition

KW - Hybrid scheduling

KW - Multiple channels

KW - Wireless mobile environments

UR - http://www.scopus.com/inward/record.url?scp=47249154313&partnerID=8YFLogxK

U2 - 10.1007/978-3-540-78568-2_16

DO - 10.1007/978-3-540-78568-2_16

M3 - Conference contribution

AN - SCOPUS:47249154313

SN - 3540785671

SN - 9783540785675

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 188

EP - 203

BT - Database Systems for Advanced Applications

A2 - Haritsa, Jayant R.

A2 - Kotagiri, Ramamohanarao

A2 - Pudi, Vikram

PB - Springer-Verlag Berlin Heidelberg

T2 - 13th International Conference on Database Systems for Advanced Applications

Y2 - 19 March 2008 through 21 March 2008

ER -

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

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

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this