| | This Article | |
| |
| |
| | Share | |
| |
| |
| | Bibliographic References | |
| |
| |
| | Add to: | |
| |
 Digg
 Furl
 Spurl
 Blink
 Simpy
 Google
 Del.icio.us
 Y!MyWeb
| |
| | Search | |
| |
| |
| | |
Dependent Data Broadcasting for Unordered Queries in a Multiple Channel Mobile Environment
September 2004 (vol. 16 no. 9)
pp. 1143-1156
Data broadcast is a promising technique to improve the bandwidth utilization and conserve the power consumption in a mobile computing environment. In many applications, the data items broadcast are dependent upon one another. However, most prior studies on broadcasting dependent data are restricted to a single broadcast channel environment, and as a consequence, the results are of limited applicability to the upcoming mobile environments. In view of this, we relax this restriction and explore in this paper the problem of broadcasting dependent data in multiple broadcast channels. By analyzing the model of dependent data broadcasting, we derive several theoretical properties for the average access time in a multiple channel environment. In light of the theoretical results, we develop a genetic algorithm to generate broadcast programs. Our experimental results show that the theoretical results derived are able to guide the search of the genetic algorithm very effectively, thus leading to broadcast programs of very high quality.
[1] S. Acharya, M.J. Franklin, and S. Zdonik, Dissemination-Based Data Delivery Using Broadcast Disks IEEE Personal Comm., vol. 2, no. 6, Dec. 1995.
[2] S. Acharya and S. Muthukrishnan, Scheduling On-Demand Broadcasts: New Metrics and Algorithms Proc. Fourth ACM/IEEE Int'l Conf. Mobile Computing and Networking, pp. 43-94, Oct. 1998.
[3] D. Aksoy and M.J. Franklin, Scheduling for Large-Scale On-Demand Data Broadcasting Proc. IEEE INFOCOM Conf., pp. 651-659, Mar. 1998.
[4] A. Bar-Noy, J. Naor, and B. Schieber, Pushing Dependent Data in Clients-Providers-Servers Systems Proc. Sixth ACM/IEEE Int'l Conf. Mobile Computing and Networking, pp. 222-230, Aug. 2000.
[5] A. Bar-Noy and Y. Shilo, Optimal Broadcasting of Two Files over an Asymmetric Channel Proc. IEEE INFOCOM Conf., pp. 267-274, Mar. 1999.
[6] Y.C. Chehadeh, A.R. Hurson, and M. Kavehrad, Object Organization on a Single Broadcast Channel in the Mobile Computing Environment Multimedia Tools and Applications, vol. 9, no. 1, pp. 69-94, July 1999.
[7] M.-S. Chen, K.-L. Wu, and P.S. Yu, Optimizing Index Allocation for Sequential Data Broadcasting in Wireless Mobile Computing IEEE Trans. Knowledge and Data Eng., vol. 15, no. 1, Jan./Feb. 2003.
[8] Y.D. Chung and M.H. Kim, Effective Data Placement for Wireless Broadcast Distributed and Parallel Databases, vol. 9, no. 2, pp. 133-150, Mar. 2001.
[9] D.E. Goldberg, Genetic Algorithms in Search, Optimization, and Machine Learning. Addison Wesley, 1989.
[10] V. Gondhalekar, R. Jain, and J. Werth, Scheduling on Airdisks: Efficient Access to Personalized Information Services via Periodic Wireless Data Broadcast Proc. IEEE Int'l Conf. Comm. Conf., June 1997.
[11] C.-L. Hu and M.-S. Chen, Dynamic Data Broadcasting with Traffic Awareness Proc. 22th IEEE Int'l Conf. Distributed Computing and Systems, July 2002.
[12] Q.L. Hu, D.L. Lee, and W.-C. Lee, Dynamic Data Delivery in Wireless Communication Environments Proc. Int'l Workshop on Mobile Data Access, pp. 218-229, Nov. 1998.
[13] Q.L. Hu, W.-C. Lee, and D.L. Lee, Indexing Techniques for Wireless Data Broadcast under Data Clustering and Scheduling Proc. Eighth ACM Int'l Conf. Information and Knowledge Management, pp. 351-718, Nov. 1999.
[14] J.-L. Huang, W.-C. Peng, and M.-S. Chen, Binary Interpolation Search for Solution Mapping on Broadcast and On-Demand Channels in a Mobile Computing Environment Proc. 10th ACM Int'l Conf. Information and Knowledge Management, Nov. 2001.
[15] A.R. Hurson, Y.C. Chehadeh, and J. Hannan, Object Organization on Parallel Broadcast Channels in a Global Information Sharing Environment Proc. 19th IEEE Int'l Performance, Computing, and Comm. Conf., pp. 347-353, Feb. 2000.
[16] T. Imielinski and S. Viswanathan, Adaptive Wireless Information Systems Proc. SIGDBS (Special Interest Group in DataBase Systems) Conf., Oct. 1994.
[17] T. Imielinski, S. Viswanathan, and B.R. Badrinath, Data on Air: Organization and Access IEEE Trans. Knowledge and Data Eng., vol. 9, no. 9, pp. 353-372, June 1997.
[18] W.-C. Lee, Q.L. Hu, and D.L. Lee, A Study on Channel Allocation for Data Dissemination in Mobile Computing Environments ACM/Baltzer Mobile Networks and Applications, vol. 4, no. 5, pp. 117-129, May 1999.
[19] C.-W. Lin and D.L. Lee, Adaptive Data Delivery in Wireless Communication Environments Proc. 20th IEEE Int'l Conf. Distributed Computing Systems, pp. 444-456, Apr. 2000.
[20] S.-C. Lo and A.L.P. Chen, Optimal Index and Data Allocation in Multiple Broadcast Channels Proc. 16th Int'l Conf. Data Eng., pp. 293-702, Mar. 2000.
[21] A. Nanopoulos, D. Katsaros, and Y. Manolopoulos, Effective Prediction of Web-User Accesses: A Data Mining Approach Proc. WEBKDD Workshop, Aug. 2001.
[22] W.-C. Peng and M.-S. Chen, Efficient Channel Allocation Tree Generation for Data Broadcasting in a Mobile Computing Environment ACM Wireless Networks, vol. 9, no. 2, pp. 117-129, 2003.
[23] K. Prabhakara, K.A. Hua, and J.H. Oh, Multi-Level Multi-Channel Air Cache Designs for Broadcasting in a Mobile Environment Proc. 16th Int'l Conf. Data Eng., pp. 167-186, Feb.-Mar. 2000.
[24] N. Shivakumar and S. Venkatasubramanian, Efficient Indexing for Broadcast Based Wireless Systems ACM/Baltzer Mobile Networks and Applications, vol. 4, no. 6, pp. 433-446, Jan. 1996.
[25] C.-J. Su and L. Tassiulas, Joint Broadcast Scheduling and User's Cache Management for Efficient Information Delivery Proc. Fourth ACM/IEEE Int'l Conf. Mobile Computing and Networking, pp. 33-42, Oct. 1998.
[26] D.A. Tran, K.A. Hua, and K. Prabhakaran, On The Efficient Use of Multiple Physical Channel Air Cache Proc. IEEE Wireless Comm. and Networking Conf., pp. 17-21, 2002.
[27] D.A. Tran, K.A. Hua, and M. Tantaoui, A Multi-Multicast Sharing Technique for Large-Scale Video Information Systems Proc. IEEE Int'l Conf. Comm., Apr.-May 2002.
[28] M. Wall, GAlib: A C++ Library of Genetic Algorithm Components http://lancet.mit.eduga, Aug. 1996.
[29] J.L. Xu, Q.L. Hu, D.L. Lee, and W.-C. Lee, SAIU: An Efficient Cache Replacement Policy for Wireless On-Demand Broadcasts Proc. Ninth ACM Int'l Conf. Information and Knowledge Management, pp. 46-53, Nov. 2000.
[30] J. Xu, D.L. Lee, and B. Li, On Bandwidth Allocation for Data Dissemination in Celluar Mobile Networks ACM/Kluwer J. Wireless Networks (WINET), vol. 9, no. 2, pp. 103-116, Mar. 2003.
[31] J.X. Yu, T. Sakata, and K.L. Tan, Statistical Estimation of Access Frequencies in Data Broadcasting Environments ACM/Baltzer Wireless Networks, vol. 6, no. 2, pp. 89-98, Mar. 2000.
[32] G.K. Zipf, Human Behaviour and the Principle of Least Effort. Addison Wesley, 1949.
Index Terms:
Data broadcast, dependent data, unordered query, mobile information system, mobile computing.
Citation:
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, vol. 16, no. 9, pp. 1143-1156, Sept. 2004, doi:10.1109/TKDE.2004.39
