Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

On-demand broadcast is an effective wireless data dissemination technique to enhance system scalability and capability 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 environments. 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 environment and observe that existing single-item requests based algorithms are unable to perform efficiently. Two potential problems are identified and examined. First, these algorithms take an excessively long time to serve the last few data items in a request because they disregard the relationship between data items and their parent requests. We claim that these algorithms suffer the request starvation problem in scheduling multi-item requests. Second, these algorithms cannot achieve the expected performance gain with multiple channels. We observed a broadcast mismatch problem in multi-channel broadcast environments. Thus, we propose an innovative algorithm to solve these two potential problems. The simulation results show that the performance of the proposed algorithm is superior to other classical algorithms under a variety of circumstances.

REFERENCES

• 1: D. Aksoy and M. Franklin. RXW: Scheduling for Large-scale On-demand Data Broadcasting. INFOCOM'98. Seventeenth Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings. IEEE, 1998.
• 2: D. Aksoy and M. Leung. Pull vs Push: a Quantitative Comparison for Data Broadcast. Global Telecommunications Conference, GLOBECOM'04 IEEE, 2004.
• 3: Jun Chen , Ganping Huang , Victor C. S. Lee, Scheduling algorithm for multi-item requests with time constraints in mobile computing environments, Proceedings of the 13th International Conference on Parallel and Distributed Systems, p.1-7, December 05-07, 2007 [doi>10.1109/ICPADS.2007.4447832]
• 4: Yon Dohn Chung , Myoung-Ho Kim, QEM: A Scheduling Method for Wireless Broadcast Data, Proceedings of the Sixth International Conference on Database Systems for Advanced Applications, p.135-142, April 19-21, 1999
• 5: C. Hu and M. Chen. Adaptive Balanced Hybrid Data Delivery for Multi-channel Data Broadcast. IEEE International Conference on Communications, 2, 2002.
• 6: J. Huang and W. Peng. An Effective Broadcast Program Generation Algorithm for Dependent Data. Emerging Information Technology Conference, 2005., pages 119--122, 2005.
• 7: T. Imielinski , S. Viswanathan , B. r. Badrinath, Data on Air: Organization and Access, IEEE Transactions on Knowledge and Data Engineering, v.9 n.3, p.353-372, May 1997 [doi>10.1109/69.599926]
• 8: K.-W. Lam and S.-L. Hung. Scheduling Real-Time Requests in On-Demand Broadcast Environments. Lecture Notes in Computer Science, NBiS, LNCS, 4658:258ĺC267, 2007.
• 9: Guanling Lee , Shou-Chih Lo, Broadcast data allocation for efficient access of multiple data items in mobile environments, Mobile Networks and Applications, v.8 n.4, p.365-375, August 2003 [doi>10.1023/A:1024579512792]
• 10: 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
• 11: Victor C. Lee , Xiao Wu , Joseph Kee-Yin Ng, Scheduling real-time requests in on-demand data broadcast environments, Real-Time Systems, v.34 n.2, p.83-99, October 2006 [doi>10.1007/s11241-006-7982-5]
• 12: C. L. Liu , James W. Layland, Scheduling algorithms for multiprogramming in a hard-real-time environment, Readings in hardware/software co-design, Kluwer Academic Publishers, Norwell, MA, 2001
• 13: K. Liu and V. Lee. Analysis of Data Scheduling Algorithms for Multi-item Requests in Multi-channel On-demand Broadcast Environments. Technical Report, Computer Science Department, City University of Hong Kong, 2008.
• 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]
• 15: 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
• 16: Nitin Prabhu , Vijay Kumar, Data scheduling for multi-item and transactional requests in on-demand broadcast, Proceedings of the 6th international conference on Mobile data management, May 09-13, 2005, Ayia Napa, Cyprus [doi>10.1145/1071246.1071254]
• 17: Navrati Saxena , M. Cristina Pinottti, On-line balanced k-channel data allocation with hybrid schedule per channel, Proceedings of the 6th international conference on Mobile data management, May 09-13, 2005, Ayia Napa, Cyprus [doi>10.1145/1071246.1071283]
• 18: Herb Schwetman, CSIM19: CSIM19: a powerful tool for building system models, Proceedings of the 33nd conference on Winter simulation, December 09-12, 2001, Arlington, Virginia
• 19: A. Waluyo, B. Srinivasan, D. Taniar, and W. Rahayu. Incorporating Global Index with Data Placement Scheme for Multi Channels Mobile Broadcast Environment. EUC 2005 LNCS, 3824:755--764, 2005.
• 20: J. Wong. Broadcast Delivery. Proceedings of the IEEE, 76(12):1566--1577, 1988.
• 21: J. W. Wong , M. H. Ammar, Analysis of Broadcast Delivery in a Videotex System, IEEE Transactions on Computers, v.34 n.9, p.863-866, September 1985 [doi>10.1109/TC.1985.1676645]
• 22: Jianliang Xu , Xueyan Tang , Wang-Chien Lee, Time-Critical On-Demand Data Broadcast: Algorithms, Analysis, and Performance Evaluation, IEEE Transactions on Parallel and Distributed Systems, v.17 n.1, p.3-14, January 2006 [doi>10.1109/TPDS.2006.14]
• 23: G. Zipf. Human Behavior and the Principle of Least Effort. 1949.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.4 Systems and Software

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.5 On-line Information Services

General Terms:
Algorithms, Performance

Keywords:
mobile computing, multi-item requests, multiple channels, on-demand broadcast, scheduling algorithms