Real-Time Data Retrieval with Multiple Availability Intervals in CPS under Freshness Constraints

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalNot applicablepeer-review

1 Scopus Citations
View graph of relations

Author(s)

  • Chenchen Fu
  • Peng Wu
  • Yingchao Zhao
  • Song Han

Related Research Unit(s)

Detail(s)

Original languageEnglish
Pages (from-to)2743-2754
Journal / PublicationIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Volume37
Issue number11
Early online date23 Jul 2018
Publication statusPublished - Nov 2018

Abstract

Maintaining the temporal validity of real-time data in Cyber-Physical Systems (CPS) is of critical importance to ensure correct decision making and appropriate system operation. Most existing work on real-time data retrieval assumes that the real-time data under study are always available, and the developed scheduling algorithms mainly focus on making real-time decisions while meeting the temporal validity (freshness) constraints. This assumption, however does not hold in many real-life CPS applications with intermittent data availability, such as in energy harvesting based sensing systems. In this paper, we study the Multi-interval Availability-constrained Fresh Data Retrieval (MAFDR) problem, which aims to retrieve all required real-time data on time for a set of decision tasks while taking both the temporal validity and data availability constraints into consideration. We present the formulation of the MAFDR problem and study its complexity under different settings. For the scenario of single decision task with unit-size data retrieval time, we propose a polynomial-time optimal data retrieval algorithm, which comprises a task finish time selection phase and an optimal retrieval schedule construction phase. For the general scenario of multiple decision tasks with non-unit-size data retrieval time, we provide an Integer Linear Programming (ILP) formulation for the MAFDR problem and propose a fast heuristic algorithm based on max flow. The effectiveness of the proposed algorithms has been validated through extensive experiments by comparing to the optimal solution and the state-of-the-art approach.

Research Area(s)

  • CPS, data availability., data freshness, Data models, Decision making, Heuristic algorithms, real-time data retrieval, Real-time systems, Schedules, sensor network, Sensors, Task analysis

Citation Format(s)

Real-Time Data Retrieval with Multiple Availability Intervals in CPS under Freshness Constraints. / Fu, Chenchen; Wu, Peng; Li, Minming; Xue, Chun Jason; Zhao, Yingchao; Han, Song.

In: IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 37, No. 11, 11.2018, p. 2743-2754.

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalNot applicablepeer-review