Broadcasting on-demand data with time constraints using multiple channels in wireless broadcast environments

作     者：Liu, Chuan-Ming Su, Ta-Chih 

作者机构：Natl Taipei Univ Technol Dept Comp Sci & Informat Engn Taipei 106 Taiwan 

出 版 物：《INFORMATION SCIENCES》 (信息科学)

年 卷 期：2013年第242卷

页      面：76-91页

核心收录：

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：On-demand data broadcasting Data overlapping NP-hard Competitive analysis Latency Miss rate 

摘      要：Data Broadcasting is an effective approach to provide information to a large group of clients in ubiquitous environments. How to generate the data broadcast schedule to make the clients average waiting time as short as possible is an important issue. In particular, when the data access pattern is dynamic and data have time constraints, such as traffic and stock information, scheduling the broadcast for such data to fulfill the requests is challenging. Since the content of the broadcast is dynamic and the request deadlines should be met, such data broadcasting is referred to as on-demand data broadcasting with time constraints. Many papers have discussed this type of data broadcasting with a single broadcast channel. In this paper, we investigate how to schedule the on-demand broadcast for the data with time constraints using multiple broadcast channels and provide two heuristics to schedule the data broadcast. The objective of the proposed heuristics is to minimize the miss rate (i.e., ratio of the number of requests missing deadlines to the number of all requests) and latency (i.e., time between issuing and termination of the request). We show that the offline version of the considered problem is NP-hard and present a competitive analysis on the proposed heuristics. More discussion about the proposed heuristics is given through extensive simulation experiments. The experimental results validate that the proposed heuristics achieve the objectives. (C) 2013 Elsevier Inc. All rights reserved.