A Novel Scheduling Algorithm for Supporting Periodic Queries in Broadcast Environments

Being a proven efficient approach to answering queries that have common data needs, data broadcast has received much attention in the past decade, especially for dynamic and large-scale data dissemination. An important class of emerging data broadcast applications must monitor multiple data items continuously in order to enable data-driven decision making. For such applications, an important problem that must be addressed is how to disseminate data to periodic continuous queries so that all the requests can be satisfied while the bandwidth utilization is minimized. To our best knowledge, the only known work on this topic is the RM-UO algorithm proposed in the work of Huang et al. (2012). However, the RM-UO algorithm simply utilizes the Sr algorithm introduced in the work of Han et al. (1996) to transform the original queries into 2-harmonic tasks, which would lead to a considerable waste of available bandwidth. In this paper, based on the observation that some queries can be merged to save bandwidth consumption, we propose two merging polices namely Multiple Query Merging (MQM) and Redundant Query Merging (RQM), and show that both can lead to notable bandwidth savings. Further, to disseminate data to periodic continuous queries, we implement a unified scheduling algorithm called UM, which combines both MQM and RQM. Extensive experiments have been conducted to compare our UM algorithm with RM-UO, and the results show that UM outperforms RM-UO considerably in terms of wireless bandwidth consumption and query service ratio.