Data scheduling for multi-item requests in multi-channel on-demand broadcast environments

On-demand broadcast is an effective wireless data dissemi- nation technique to enhance system scalability and capabil- ity to handle dynamic user access patterns. With the rapid development of mobile applications, there is an increasing need for systems to support efficient processing of requests for multiple data items in multiple channels broadcast en- vironments. Few studies, however, have considered the on- demand scheduling mechanisms for multi-item requests in multi-channel broadcast environments. In this paper, we investigate the scheduling problems arising in this new envi- ronment and observe that existing single-item requests based algorithms are unable to perform efficiently. Two potential problems are identified and examined. First, these algo- rithms take an excessively long time to serve the last few data items in a request because they disregard the relation- ship between data items and their parent requests. We claim that these algorithms su®er the request starvation problem in scheduling multi-item requests. Second, these algorithms cannot achieve the expected performance gain with multi- ple channels. We observed a broadcast mismatch problem in multi-channel broadcast environments. Thus, we propose an innovative algorithm to solve these two potential prob- lems. The simulation results show that the performance of the proposed algorithm is superior to other classical algo- rithms under a variety of circumstances. Copyright 2008 ACM.