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.
This research is supported in part by the National Natural Science Foundation of China (NSFC) under grant 60503035 and the National High-Tech Research and Development Plan of China under Grant 2006AA01Z234.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Xu, J., Lee, D.L., Hu, Q., Lee, W.C.: Data Broadcast. In: Handbook of Wireless Networks and Mobile Computing, John Wiley, Chichester (2002)
Imielinski, T., Viswanathan, S., Badrinath, B.R.: Data on air: Organization and access. IEEE Trans. on Knowledge and Data Engineering 9(3), 353–372 (1997)
Xu, J., Lee, W.C., Tang, X.: Exponential index: A parameterized distributed indexing scheme for data on air. In: MobiSys. 2004, pp. 153–164 (2004)
Yao, Y., Tang, X., Lim, E., Sun, A.: An energy-efficient and access latency optimized indexing scheme for wireless data broadcast. IEEE Trans. on Knowledge and Data Engineering 18(8), 1111–1124 (2006)
Ammar, M.H., Wong, J.W.: The design of teletext broadcast cycles. Performance Evaluation 5(4), 235–242 (1985)
Vaidya, N.H., Hameed, S.: Scheduling data broadcast in asymmetric communication environments. ACM/Baltzer Journal of Wireless Networks (WINET) 5(3), 171–182 (1995)
Hameed, S., Vaidya, N.H.: Efficient algorithms for scheduling data broadcast. ACM/Baltzer Journal of Wireless Networks (WINET) 5(3), 183–193 (1999)
Acharya, S., Alonso, R., Franklin, M., Zdonik, S.: Broadcast disks: Data management for asymmetric communications environments. In: SIGMOD 1995, pp. 199–210 (1995)
Ardizzoni, E., Bertossi, A.A., Pinotti, M.C., Ramaprasad, S., Rizzi, R., Shashanka, M.V.S.: Optimal skewed data allocation on multiple channels with flat broadcast per channel. IEEE Trans. on Computer 54(5), 558–572 (2005)
Prabhakara, K., Hua, K., Oh, J.: Multi-level multi-channel air cache design for broadcasting in a mobile environment. In: ICDE 2000, pp. 167–176 (2000)
Yee, W., Navathe, S.: Efficient data access to multi-channel broadcast programs. In: CIKM 2003, pp. 153–160 (2003)
Yee, W.G., Navathe, S.B., Omiecinski, E., Jermaine, C.: Efficient data allocation over multiple channels at broadcast servers. IEEE Trans. on Computers, Special Issue on Mobility and Databases 51(10), 1231–1236 (2002)
Peng, W.C., Chen, M.S.: Efficient channel allocation tree generation for data broadcasting in a mobile computing environment. Wireless Networks 9, 117–129 (2003)
Hung, J.J., Seifert, A.: Flexsched: A parameterized data schedule generator for multi-channel broadcast systems. In: MDM 2006 (2006)
Huang, J.L., Peng, W.C., Chen, M.S.: Som: Dynamic push-pull channel allocation framework for mobile data broadcasting. IEEE Trans. on Mobile Computing 5(8), 974–990 (2006)
Leong, H.V., Si, A.: Data broadcasting strategies over multiple unreliable wireless channels. In: CIKM 1995 (1995)
Zheng, B.H., Wu, X., Jin, X., Lee, D.L.: Tosa: a near-optimal scheduling algorithm for multi-channel data broadcast. In: MDM 2005, pp. 29–37 (2005)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
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: Haritsa, J.R., Kotagiri, R., Pudi, V. (eds) Database Systems for Advanced Applications. DASFAA 2008. Lecture Notes in Computer Science, vol 4947. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-78568-2_16
Download citation
DOI: https://doi.org/10.1007/978-3-540-78568-2_16
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-78567-5
Online ISBN: 978-3-540-78568-2
eBook Packages: Computer ScienceComputer Science (R0)