Real-Time Data Retrieval With Multiple Availability Intervals in CPS Under Freshness Constraints

摘要

Maintaining the temporal validity of real-time data in cyber-physical systems (CPSs) 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 nonunit-size data retrieval time, we provide an integer linear programming 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.