Broadcasting on-demand data with time constraints using multiple channels in wireless broadcast environments
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.
on-demand data broadcasting miss rate latency np-hard competitive analysis data overlapping