research-article

Dependent Data Broadcasting for Unordered Queries in a Multiple Channel Mobile Environment

Authors:

Jiun-Long Huang,

Ming-Syan ChenAuthors Info & Claims

IEEE Transactions on Knowledge and Data Engineering, Volume 16, Issue 9

Pages 1143 - 1156

https://doi.org/10.1109/TKDE.2004.39

Published: 01 September 2004 Publication History

Publisher Site

Abstract

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.

References

[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.

Crossref

Google Scholar

[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.

Digital Library

Google Scholar

[3]

D. Aksoy and M.J. Franklin, “Scheduling for Large-Scale On-Demand Data Broadcasting,” Proc. IEEE INFOCOM Conf., pp. 651-659, Mar. 1998.

Crossref

Google Scholar

[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.

Digital Library

Google Scholar

[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.

Crossref

Google Scholar

[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.nbsp69-94, July 1999.

Digital Library

Google Scholar

[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.

Digital Library

Google Scholar

[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.

Digital Library

Google Scholar

[9]

D.E. Goldberg, Genetic Algorithms in Search, Optimization, and Machine Learning. Addison Wesley, 1989.

Digital Library

Google Scholar

[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.

Crossref

Google Scholar

[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.

Digital Library

Google Scholar

[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.

Digital Library

Google Scholar

[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.

Digital Library

Google Scholar

[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.

Digital Library

Google Scholar

[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.

Crossref

Google Scholar

[16]

T. Imielinski and S. Viswanathan, “Adaptive Wireless Information Systems,” Proc. SIGDBS (Special Interest Group in DataBase Systems) Conf., Oct. 1994.

Google Scholar

[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.

Digital Library

Google Scholar

[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.

Digital Library

Google Scholar

[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.

Digital Library

Google Scholar

[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.nbsp293-702, Mar. 2000.

Digital Library

Google Scholar

[21]

A. Nanopoulos D. Katsaros and Y. Manolopoulos, “Effective Prediction of Web-User Accesses: A Data Mining Approach,” Proc. WEBKDD Workshop, Aug. 2001.

Google Scholar

[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.

Digital Library

Google Scholar

[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.

Digital Library

Google Scholar

[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.

Digital Library

Google Scholar

[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.nbsp33-42, Oct. 1998.

Digital Library

Google Scholar

[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.

Crossref

Google Scholar

[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.

Crossref

Google Scholar

[28]

M. Wall, “GAlib: A C++ Library of Genetic Algorithm Components,” http://lancet.mit.edu/ga, Aug. 1996.

Google Scholar

[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.

Digital Library

Google Scholar

[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.

Digital Library

Google Scholar

[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.

Digital Library

Google Scholar

[32]

G.K. Zipf, Human Behaviour and the Principle of Least Effort. Addison Wesley, 1949.

Google Scholar

Cited By

View all

Guohui Li Quan Zhou Jianjun Li (2015)A Novel Scheduling Algorithm for Supporting Periodic Queries in Broadcast EnvironmentsIEEE Transactions on Mobile Computing10.1109/TMC.2015.239841714:12(2419-2432)Online publication date: 1-Dec-2015
https://dl.acm.org/doi/10.1109/TMC.2015.2398417
Chu C(2013)On efficient 3D data disseminationWireless Networks10.1007/s11276-013-0579-819:8(1901-1914)Online publication date: 1-Nov-2013
https://dl.acm.org/doi/10.1007/s11276-013-0579-8
Kim SKim HLee KLee DSuh S(2012)Agent-based Mobile Data Caching Strategies Using Data SignificanceJournal of Integrated Design & Process Science10.5555/2590501.259050616:2(51-64)Online publication date: 1-Apr-2012
https://dl.acm.org/doi/10.5555/2590501.2590506
Show More Cited By

Index Terms

Dependent Data Broadcasting for Unordered Queries in a Multiple Channel Mobile Environment

Recommendations

Exploiting replication on dependent data allocation for ordered queries over multiple broadcast channels

Data broadcasting has been recognized as an important means for information dissemination in mobile computing environments. In some mobile applications, the data items broadcast are dependent upon one another. However, most prior studies on broadcasting ...
Broadcast program generation for unordered queries with data replication
SAC '03: Proceedings of the 2003 ACM symposium on Applied computing

We study in this paper the problem of broadcasting dependent data for unordered queries. However, most prior studies on dependent data broadcasting are limited to the premise of no data replication. Different from other prior studies, we investigate the ...
An efficient partition and matching algorithm for query-set-based broadcasting in multiple channel mobile environment

Broadcast is an efficient and scalable method for resolving the bandwidth limitation in a wireless environment. In many applications, mobile clients might need more than one data item. However, most previous researches on query-set-based broadcasting ...

Reviews

Reviewer: Pierre N. Radulescu-Banu

Data broadcasting is a promising technique for improving bandwidth utilization and conserving 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 future mobile environments. In view of this, the authors relax this restriction and explore the problem of broadcasting dependent data in multiple broadcast channels. They develop a genetic algorithm to generate broadcast programs. The 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. Section 1 of the paper is an introduction. Section 2 gives an overview of genetic algorithms, defines the system architecture, and describes the problem. In section 3, the model of dependent data broadcasting is analyzed in order to derive some properties for the average access time in a multiple-channel environment. Section 4 is devoted to the design of the genetic algorithm. Performance evaluation is conducted in Section 5. Section 6 offers some conclusions. An appendix contains the proofs for all lemmas used throughout the paper. Online Computing Reviews Service

Access critical reviews of Computing literature here

Become a reviewer for Computing Reviews.

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Transactions on Knowledge and Data Engineering

IEEE Transactions on Knowledge and Data Engineering Volume 16, Issue 9

September 2004

144 pages

ISSN:1041-4347

Issue’s Table of Contents

Publisher

IEEE Educational Activities Department

United States

Publication History

Published: 01 September 2004

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

17
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 03 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Guohui Li Quan Zhou Jianjun Li (2015)A Novel Scheduling Algorithm for Supporting Periodic Queries in Broadcast EnvironmentsIEEE Transactions on Mobile Computing10.1109/TMC.2015.239841714:12(2419-2432)Online publication date: 1-Dec-2015
https://dl.acm.org/doi/10.1109/TMC.2015.2398417
Chu C(2013)On efficient 3D data disseminationWireless Networks10.1007/s11276-013-0579-819:8(1901-1914)Online publication date: 1-Nov-2013
https://dl.acm.org/doi/10.1007/s11276-013-0579-8
Kim SKim HLee KLee DSuh S(2012)Agent-based Mobile Data Caching Strategies Using Data SignificanceJournal of Integrated Design & Process Science10.5555/2590501.259050616:2(51-64)Online publication date: 1-Apr-2012
https://dl.acm.org/doi/10.5555/2590501.2590506
Wang J(2012)Set-based broadcast scheduling for minimizing the worst access time of multiple data items in wireless environmentsInformation Sciences: an International Journal10.1016/j.ins.2012.02.038199(93-108)Online publication date: 1-Sep-2012
https://dl.acm.org/doi/10.1016/j.ins.2012.02.038
Gao XLu ZWu WFu B(2011)Algebraic algorithm for scheduling data retrieval in multi-channel wireless data broadcast environmentsProceedings of the 5th international conference on Combinatorial optimization and applications10.5555/2032927.2032934(74-81)Online publication date: 4-Aug-2011
https://dl.acm.org/doi/10.5555/2032927.2032934
Huang JHuang J(2010)Exploiting replication on dependent data allocation for ordered queries over multiple broadcast channelsWireless Networks10.1007/s11276-009-0230-x16:7(1817-1836)Online publication date: 1-Oct-2010
https://dl.acm.org/doi/10.1007/s11276-009-0230-x
Dewri RWhitley DRay IRay I(2008)Optimizing Real-Time Ordered-Data Broadcasts in Pervasive Environments Using Evolution StrategyProceedings of the 10th International Conference on Parallel Problem Solving from Nature --- PPSN X - Volume 519910.5555/2951659.2951763(991-1000)Online publication date: 13-Sep-2008
https://dl.acm.org/doi/10.5555/2951659.2951763
Dewri RWhitley DRay IRay IRyan C(2008)Evolution strategy based optimization of on-demand dependent data broadcast schedulingProceedings of the 10th annual conference on Genetic and evolutionary computation10.1145/1389095.1389416(1699-1700)Online publication date: 13-Jul-2008
https://dl.acm.org/doi/10.1145/1389095.1389416
Park SJung SKim WChoi H(2008)A data allocation scheme for multiple wireless broadcast channelsProceedings of the 2nd international conference on Ubiquitous information management and communication10.1145/1352793.1352848(256-262)Online publication date: 31-Jan-2008
https://dl.acm.org/doi/10.1145/1352793.1352848
Robert JSchabanel NGabow H(2007)Pull-based data broadcast with dependenciesProceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms10.5555/1283383.1283409(238-247)Online publication date: 7-Jan-2007
https://dl.acm.org/doi/10.5555/1283383.1283409
Show More Cited By

Abstract

References

Cited By

Index Terms

Recommendations

Exploiting replication on dependent data allocation for ordered queries over multiple broadcast channels

Broadcast program generation for unordered queries with data replication

An efficient partition and matching algorithm for query-set-based broadcasting in multiple channel mobile environment

Reviews

Access critical reviews of Computing literature here

Comments

Information

Published In

Publisher

Publication History

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations