A Novel Scheduling Algorithm for Supporting Periodic Queries in Broadcast Environments
A Novel Scheduling Algorithm for Supporting Periodic Queries in Broadcast Environments
复制标题
DOI：
10.1109/tmc.2015.2398417
复制
发表时间：
2015-12
影响因子：
7.9
通讯作者：
Guohui Li;Quan Zhou;Jianjun Li
中科院分区：
文献类型：
--
作者：
Guohui Li;Quan Zhou;Jianjun Li
数据广播作为一种被证明是回答具有共同数据需求的查询的有效方法，在过去的十年中受到了极大的关注，特别是在动态和大规模的数据分发方面。一类重要的新兴数据广播应用必须连续监控多个数据项，以实现数据驱动的决策制定。对于这样的应用，一个必须解决的重要问题是如何将数据分发到周期性的连续查询中，以便在满足所有请求的同时使带宽利用率最小。据我们所知，在这个主题上唯一已知的工作是在Huang等人的工作中提出的RM-UO算法。(2012年)。然而，RM-UO算法简单地利用了han等人的工作中引入的SR算法。(1996)将原始查询转换为2-调和任务，这将导致相当大的可用带宽浪费。在观察到一些查询可以合并以节省带宽消耗的基础上，我们提出了两种合并策略，即多查询合并(MQM)和冗余查询合并(RQM)，并证明了这两种合并策略都可以显著地节省带宽。此外，为了将数据分发到周期性连续查询，我们实现了一种称为UM的统一调度算法，该算法结合了MQM和RQM。通过大量的实验比较了UM算法和RM-UO算法，结果表明UM算法在无线带宽消耗和查询服务率方面明显优于RM-UO算法。
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.