TOSA: a near-optimal scheduling algorithm for multi-channel data broadcast

ABSTRACT

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.

REFERENCES

• 1: Daniel Barbará , Tomasz Imieliński, Sleepers and workaholics: caching strategies in mobile environments, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.1-12, May 24-27, 1994, Minneapolis, Minnesota, United States
• 2: Sohail Hameed , Nitin H. Vaidya, Log-time algorithms for scheduling single and multiple channel data broadcast, Proceedings of the 3rd annual ACM/IEEE international conference on Mobile computing and networking, p.90-99, September 26-30, 1997, Budapest, Hungary [doi>10.1145/262116.262136]
• 3: G. H. Hardy, J. E. Littlewood, and G. Plya. Further Remarks on Method: The Inequality of Schwarz. Cambridge University Press, 1952.
• 4: Chih-Hao Hsu , Guanling Lee , Arbee L. P. Chen, Index and Data Allocation on Multiple Broadcast Channels Considering Data Access Frequencies, Proceedings of the Third International Conference on Mobile Data Management, p.87-93, January 08-11, 2002
• 5: Jiun-Long Huang , Ming-Syan Chen, Dependent Data Broadcasting for Unordered Queries in a Multiple Channel Mobile Environment, IEEE Transactions on Knowledge and Data Engineering, v.16 n.9, p.1143-1156, September 2004 [doi>10.1109/TKDE.2004.39]
• 6: A. R. Hurson, Y. C. Chehadeh, and J. Hannan. Object organization on parallel broadcast channels in a global information sharing environment. In Proceedings of 19th IEEE International Performance, Computing, and Communications Conference (IPCCC'00), February 2000.
• 7: Guanling Lee , Meng-Shin Yeh , Shou-Chih Lo , Arbee L. P. Chen, A Strategy for Efficient Access of Multiple Data Items in Mobile Environments, Proceedings of the Third International Conference on Mobile Data Management, p.71-78, January 08-11, 2002
• 8: Optimal Index and Data Allocation in Multiple Broadcast Channels, Proceedings of the 16th International Conference on Data Engineering, p.293, February 28-March 03, 2000
• 9: Multi-Level Multi-Channel Air Cache Designs for Broadcasting in a Mobile Environment, Proceedings of the 16th International Conference on Data Engineering, p.167, February 28-March 03, 2000
• 10: H. Schwetman. Mesquite Software, Inc, http://www.mesquite.com, 1998.
• 11: Narayanan Shivakumar , Suresh Venkatasubramanian, Efficient indexing for broadcast based wireless systems, Mobile Networks and Applications, v.1 n.4, p.433-446, Dec. 1996
• 12: N. H. Vaidya and S. Hameed. Data broadcast in asymmetric environments. In Proceedings of the 1st International Workshop on Satellite-based Information Services (WOSBIS'96), Rye, NY, USA, November 1996.
• 13: Wai Gen Yee , Shamkant B. Navathe, Efficient data access to multi-channel broadcast programs, Proceedings of the twelfth international conference on Information and knowledge management, November 03-08, 2003, New Orleans, LA, USA [doi>10.1145/956863.956893]
• 14: Wai Gen Yee , Shamkant B. Navathe , Edward Omiecinski , Christopher Jermaine, Efficient Data Allocation over Multiple Channels at Broadcast Servers, IEEE Transactions on Computers, v.51 n.10, p.1231-1236, October 2002 [doi>10.1109/TC.2002.1039849]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS

Keywords:
mobile computing, multiple channels, scheduling, wireless broadcast