Dynamic priority scheduling of periodic queries in on-demand data dissemination systems. (July 2017)

• Record Type: Journal Article
• Authors: Zhou, Quan; Li, Guohui; Li, Jianjun; Shu, LihChyun; Zhang, Cong; Yang, Fumin
• Is Part Of: Information systems. Volume 67(2017)
• Page Start: 58
• Page End: 70
• Publication Date: 2017-07
• Subjects: On-demand -- Data dissemination -- Bandwidth consumption -- Dynamic priority -- Periodic queries; Database management -- Periodicals; Electronic data processing -- Periodicals; Bases de données -- Gestion -- Périodiques; Informatique -- Périodiques; Database management; Electronic data processing; Periodicals; 005.7
• DOI: 10.1016/j.is.2017.03.005
• Languages: English
• ISSNs: 0306-4379

Abstract

Highlights: We propose EDFS, a variant of the classic EDF scheduling algorithm, which can be used to schedule real-time tasks in the data broadcast environment. We also provide a necessary and sufficient schedulability test for EDFS. Based on EDFS, we propose, to our best knowledge, the first dynamic priority based broadcast scheduling algorithm, EDFS-BS, which comprehensively considers the real-time characteristics of the tasks, the sharing feature of the broadcast data items and the continuity of the broadcast services. We also analyze the schedulability of EDFS-BS and provide a bandwidth utilization based schedulability test for it. We conduct extensive experiments to evaluate the performance of EDFS-BS versus existing solutions with comparable quality. The experimental results reveal the efficiency of EDFS-BS as compared to its competitors, in terms of service ratio and bandwidth consumption. Abstract: As an important wireless data broadcast technique, on-demand broadcast has been widely used for dynamic and large-scale data dissemination. An important class of emerging data broadcast applications requires monitoring multiple data items continuously in order to support data-driven decision making. Since wireless bandwidth is a precious shared medium, an important problem to solve is how to disseminate data to periodic queries, so that all the requests can be satisfied while the bandwidth consumption is minimized. In this paper, we first propose a new real-time scheduling algorithm calledEDFS, which is a variant of the classic EDF [24] algorithm. Based onEDFS, we propose a novel on-line broadcast scheduling algorithm, calledEDFS-BS . To our best knowledge, EDFS-BS is the first dynamic priority based broadcast scheduling algorithm that can be utilized to satisfy the timing constraints of periodic queries. We also propose a bandwidth utilization based schedulability test forEDFS-BS, which is used to ensure timing predictability of a periodic query set. Extensive experiments have been conducted to compareEDFS-BS versus existing solutions with comparable quality. The results show thatEDFS-BS outperforms them considerably in terms of wireless bandwidth consumption and query service ratio.