Abstract: Existing research efforts on real-time data dissemination in on-demand data broadcast environments are only concerned with scheduling single data request with deadline constraints. hhe issue of processing real-time ordered query in on-demand broadcast systems was investigated. Particularly, we first formally defined a new kind of scheduling problem called ROBS by formulating the real-time ordered ctuery processing problem. We also showed that the ROBS problem is NP-hard. Secondly, a novel scheduling algorithm called OL-ROBS was proposed to address the on-line version of ROBS. To tackle the performance issue of OL-ROBS, a delicate data structure for managing data requests was construeted and an efficient pruning algorithm was proposed. Finally, extensive simulations were conducted and the empirical resups show that OL- ROBS owns significant performance gain over the well-known Sin-8 algorithm.

Key words: Data broadcast, Real-time ordered query processing, Scheduling algorithms