Scheduling For Multi-item Queries In Wireless Data Broadcast

Data broadcast has been accepted as an efficient way of data dissemination in the wireless mobile environment.With broadcast system,data is broadcast on the public downlink channel,Clients "listen" to that channel and download data that they are interested in.In this way,broadcasting one data item can satisfy all the pending queries which require that item.The system workload is independent of the clients number in the service range.As a result,one server can support numerous data access queries simultaneously. The access time,which means the time elapsed between the moment when a query is issued and the moment when this query is satisfied,is a critical metric to evaluate the broadcasting performance.Broadcast scheduling,which determines what to be broadcast and when,can greatly affect the access time,thus has received great attention form the research community for a long time.In this paper,we discuss about the scheduling method for data broadcast system with specially focus on scheduling for multi-item queries.Broadcast for multi-item query is a basic problem in this field since multi-item query is common in practical situations. To our knowledge,less previous work has proposed since the QEM algorithm proposed in 1999.In this work,we propose scheduling strategy for multi-item queries in both periodic and on-demand broadcast mode.In periodic broadcast mode,we propose a hybrid scheduling strategy which combines the advantages of the square root rule and existing scheduling algorithms for multi-item queries.Such hybrid scheduling strategy gives better performance for scheduling multi-item queries especially those with skewed query access probability.In on-demand broadcast mode,we first adopt the paradigm based on broadcast cycles.For the two sub-problems with such paradigm, the query selection problem and the broadcast scheduling problem,we propose our novel solutions for both of them respectively.On the other hand,we also propose a preemptive scheduling algorithm for multi-item queries.It breaks through the previous broadcast cycle based paradigm and can adapt gracefully in the on-demand environment with dynamic change of the query access pattern.Simulation experiment results shows that compared with the previous approaches,our strategies can significantly improve the system performance in various cases.