TOSA: A Near-Optimal Scheduling Algorithm for Multi-Channel Data Broadcast

• Main Authors: ZHENG, Baihua, XU, Xia, JIN, Xing, LEE, Dik Lun
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2005
• Subjects: wireless broadcast; mobile computing; multiple channels; scheduling; Databases and Information Systems; Numerical Analysis and Scientific Computing
• Online Access: https://ink.library.smu.edu.sg/sis_research/587; https://ink.library.smu.edu.sg/context/sis_research/article/1586/viewcontent/MDM05_final.pdf
• Institution: Singapore Management University

Wireless broadcast is very suitable for delivering information to a large user population. In this paper, we concentrate on data allocation methods for multiple broadcast channels. To the best of our knowledge, this is the first allocation model that takes into the consideration of items' access frequencies, items' lengths. and bandwidth of different channels. We first derive the optimal average expected delay for multiple channels for the general case where data access frequencies, data sizes, and channel bandwidths can all be non-uniform. Second, we develop TOSA, a multi-channel allocation method that does not assume a uniform broadcast schedule for data items on the same channel. TOSA is based on the idea of two-level data allocation, i.e., a high-level optimization step for allocating data to the channels, followed by a low-level optimization step to schedule data within a channel. We show that TOSA achieves near-optimal performance in terms of average waiting time and significantly outperforms the existing algorithms.