Scheduling periodic continuous queries in real-time data broadcast environments

Hongya Wang, Yingyuan Xiao, Lih-Chyun Shu

Research output: Contribution to journalArticle

12 Citations (Scopus)

Abstract

On-demand broadcast is a promising data dissemination approach in mobile computing environments thanks to its adaptability and scalability for large-scale and dynamic workload. An important class of emerging data broadcast applications needs to monitor multiple time-varying data items continuously to be kept aware of the up-to-date information. This paper investigates the broadcast schedule problem for disseminating timely data to periodic continuous queries, and a systematic and highly efficient solution for applications of this type is provided. In particular, we propose a novel measure, called Bandwidth Utilization, to quantify the minimum bandwidth demand of a periodic continuous query set. The timing predictability can be ensured if a set of periodic continuous queries passes a bandwidth utilization based schedulability test. The schedulability test techniques are also extended to deal with dynamic query arrival and departure. An efficient online scheduling algorithm, called RM-UO, is developed, which can fulfill the timing constraints combined with the proposed query release and deletion policies. To demonstrate the effectiveness of theoretical results, an illustrative algorithm implementation is presented along with comprehensive performance analysis. Simulation results show that our solution offers nice timing predictability whereas other comparable best effort scheduling algorithms such as SIN-α and DTIU experience different deadline miss ratios at different query workloads.

Original languageEnglish
Article number5989798
Pages (from-to)1325-1340
Number of pages16
JournalIEEE Transactions on Computers
Volume61
Issue number9
DOIs
Publication statusPublished - 2012 Aug 10

Fingerprint

Continuous Queries
Broadcast
Timing
Scheduling
Bandwidth
Predictability
Query
Scheduling algorithms
Real-time
Scheduling Algorithm
Workload
Data Dissemination
Online Scheduling
Mobile computing
Mobile Computing
Online Algorithms
Deadline
Adaptability
Efficient Solution
Deletion

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computational Theory and Mathematics

Cite this

@article{c7a9525f1e8f40d2960c1ea3708cc6b3,
title = "Scheduling periodic continuous queries in real-time data broadcast environments",
abstract = "On-demand broadcast is a promising data dissemination approach in mobile computing environments thanks to its adaptability and scalability for large-scale and dynamic workload. An important class of emerging data broadcast applications needs to monitor multiple time-varying data items continuously to be kept aware of the up-to-date information. This paper investigates the broadcast schedule problem for disseminating timely data to periodic continuous queries, and a systematic and highly efficient solution for applications of this type is provided. In particular, we propose a novel measure, called Bandwidth Utilization, to quantify the minimum bandwidth demand of a periodic continuous query set. The timing predictability can be ensured if a set of periodic continuous queries passes a bandwidth utilization based schedulability test. The schedulability test techniques are also extended to deal with dynamic query arrival and departure. An efficient online scheduling algorithm, called RM-UO, is developed, which can fulfill the timing constraints combined with the proposed query release and deletion policies. To demonstrate the effectiveness of theoretical results, an illustrative algorithm implementation is presented along with comprehensive performance analysis. Simulation results show that our solution offers nice timing predictability whereas other comparable best effort scheduling algorithms such as SIN-α and DTIU experience different deadline miss ratios at different query workloads.",
author = "Hongya Wang and Yingyuan Xiao and Lih-Chyun Shu",
year = "2012",
month = "8",
day = "10",
doi = "10.1109/TC.2011.154",
language = "English",
volume = "61",
pages = "1325--1340",
journal = "IEEE Transactions on Computers",
issn = "0018-9340",
publisher = "IEEE Computer Society",
number = "9",

}

Scheduling periodic continuous queries in real-time data broadcast environments. / Wang, Hongya; Xiao, Yingyuan; Shu, Lih-Chyun.

In: IEEE Transactions on Computers, Vol. 61, No. 9, 5989798, 10.08.2012, p. 1325-1340.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Scheduling periodic continuous queries in real-time data broadcast environments

AU - Wang, Hongya

AU - Xiao, Yingyuan

AU - Shu, Lih-Chyun

PY - 2012/8/10

Y1 - 2012/8/10

N2 - On-demand broadcast is a promising data dissemination approach in mobile computing environments thanks to its adaptability and scalability for large-scale and dynamic workload. An important class of emerging data broadcast applications needs to monitor multiple time-varying data items continuously to be kept aware of the up-to-date information. This paper investigates the broadcast schedule problem for disseminating timely data to periodic continuous queries, and a systematic and highly efficient solution for applications of this type is provided. In particular, we propose a novel measure, called Bandwidth Utilization, to quantify the minimum bandwidth demand of a periodic continuous query set. The timing predictability can be ensured if a set of periodic continuous queries passes a bandwidth utilization based schedulability test. The schedulability test techniques are also extended to deal with dynamic query arrival and departure. An efficient online scheduling algorithm, called RM-UO, is developed, which can fulfill the timing constraints combined with the proposed query release and deletion policies. To demonstrate the effectiveness of theoretical results, an illustrative algorithm implementation is presented along with comprehensive performance analysis. Simulation results show that our solution offers nice timing predictability whereas other comparable best effort scheduling algorithms such as SIN-α and DTIU experience different deadline miss ratios at different query workloads.

AB - On-demand broadcast is a promising data dissemination approach in mobile computing environments thanks to its adaptability and scalability for large-scale and dynamic workload. An important class of emerging data broadcast applications needs to monitor multiple time-varying data items continuously to be kept aware of the up-to-date information. This paper investigates the broadcast schedule problem for disseminating timely data to periodic continuous queries, and a systematic and highly efficient solution for applications of this type is provided. In particular, we propose a novel measure, called Bandwidth Utilization, to quantify the minimum bandwidth demand of a periodic continuous query set. The timing predictability can be ensured if a set of periodic continuous queries passes a bandwidth utilization based schedulability test. The schedulability test techniques are also extended to deal with dynamic query arrival and departure. An efficient online scheduling algorithm, called RM-UO, is developed, which can fulfill the timing constraints combined with the proposed query release and deletion policies. To demonstrate the effectiveness of theoretical results, an illustrative algorithm implementation is presented along with comprehensive performance analysis. Simulation results show that our solution offers nice timing predictability whereas other comparable best effort scheduling algorithms such as SIN-α and DTIU experience different deadline miss ratios at different query workloads.

UR - http://www.scopus.com/inward/record.url?scp=84864576602&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84864576602&partnerID=8YFLogxK

U2 - 10.1109/TC.2011.154

DO - 10.1109/TC.2011.154

M3 - Article

VL - 61

SP - 1325

EP - 1340

JO - IEEE Transactions on Computers

JF - IEEE Transactions on Computers

SN - 0018-9340

IS - 9

M1 - 5989798

ER -