A near optimal algorithm for generating broadcast programs on multiple channels

ABSTRACT

In a wireless environment, the bandwidth of the channels and the energy of the portable devices are limited. Data broadcast has become an excellent method for efficient data dissemination. In this paper, the problem for generating a broadcast program of a set of data items with the associated access frequencies on multiple channels is explored. In our approach, an expected average access time of the broadcast data items is first derived. The broadcast program is then generated, which minimizes the expected average access time. Simulation is performed to compare the performance of our approach with two existing approaches. The result of the experiments shows that our approach outperforms others and is in fact close to the optimal.

REFERENCES

• 1: Swarup Acharya , Rafael Alonso , Michael Franklin , Stanley Zdonik, Broadcast disks: data management for asymmetric communication environments, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.199-210, May 22-25, 1995, San Jose, California, United States
• 2: S. Acharya, M. Franklin and S. Zdonik, "Disseminationbased Data Delivery Using Broadcast Disks", IEEE Personal Communications, 2(6), Dec. 1995.
• 3: Swarup Acharya , Michael J. Franklin , Stanley B. Zdonik, Disseminating Updates on Broadcast Disks, Proceedings of the 22th International Conference on Very Large Data Bases, p.354-365, September 03-06, 1996
• 4: Swarup Acharya , Michael J. Franklin , Stanley B. Zdonik, Prefetching from Broadcast Disks, Proceedings of the Twelfth International Conference on Data Engineering, p.276-285, February 26-March 01, 1996
• 5: Rafael Alonso , Henry F. Korth, Database system issues in nomadic computing, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.388-392, May 25-28, 1993, Washington, D.C., United States
• 6: T.F. Bowen, G. Gopal, G. Herman, T. Hickey, K.C. Lee, W.H. Mansfield, J. Raitz, and A. Weinrib. "The Datacycle Architecture". Communications of the ACM, pages 850-857, 1995.
• 7: Jim Gray , Prakash Sundaresan , Susanne Englert , Ken Baclawski , Peter J. Weinberger, Quickly generating billion-record synthetic databases, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.243-252, May 24-27, 1994, Minneapolis, Minnesota, United States
• 8: A.R. Hurson, Y.C. Chehadeh and J. Hannan, "Object Organization on Parallel Broadcast Channels in a Global Information Sharing Environment," IEEE International Performance, Computing, and Communications Conference (IPCCC), February 2000.
• 9: Gary Herman , K. C. Lee , Abel Weinrib, The datacycle architecture for very high throughput database systems, Proceedings of the 1987 ACM SIGMOD international conference on Management of data, p.97-103, May 27-29, 1987, San Francisco, California, United States
• 10: Sohail Hameed , Nitin H. Vaidya, Efficient algorithms for scheduling data broadcast, Wireless Networks, v.5 n.3, p.183-193, May 1999 [doi>10.1023/A:1019194826654]
• 11: Tomasz Imieĺinski , B. R. Badrinath, Data management for mobile computing, ACM SIGMOD Record, v.22 n.1, p.34-39, March 1993 [doi>10.1145/156883.156888]
• 12: 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
• 13: Wen-Chih Peng , Ming-Syan Chen, Dynamic generation of data broadcasting programs for a broadcast disk array in a mobile computing environment, Proceedings of the ninth international conference on Information and knowledge management, p.38-45, November 06-11, 2000, McLean, Virginia, United States [doi>10.1145/354756.354780]
• 14: 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
• 15: Evaggelia Pitoura , George Samaras, Data Management for Mobile Computing, Kluwer Academic Publishers, Norwell, MA, 1997
• 16: N. Shivakumar and S. Venkatasubramanian, "Energy- Efftcient Indexing For Information Dissemination In Wireless Systems," ACM, Journal of Wireless and Nomadic Application, 1996.
• 17: Kian-Lee Tan , Beng Chin Ooi, Batch scheduling for demand-driven servers in wireless enviroments, Information Sciences: an International Journal, v.109 n.1-4, p.281-298, Aug. 1998 [doi>10.1016/S0020-0255(97)10075-5]
• 18: Nitin H. Vaidya , Sohail Hameed, Scheduling data broadcast in asymmetric communication environments, Wireless Networks, v.5 n.3, p.171-182, May 1999 [doi>10.1023/A:1019142809816]
• 19: J.W. Wong. "Broadcast delivery", Proceeding of the IEEE, 76(12): 1566-1577, 1988.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Distributed networks

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

General Terms:
Algorithms, Design, Performance

Keywords:
broadcast program, data allocation, multiple broadcast channels, wireless environment