Online Mode Switch Algorithms for Maintaining Data Freshness in Dynamic Cyber-Physical Systems

Maintaining the freshness of real-time data is one of the crucial design issues in cyber-physical systems (CPS). Past studies have focused on designing update algorithms to minimize the workload imposed by a fixed set of update tasks while ensuring the temporal validity of data. In this paper, we revisit this problem in dynamic cyber-physical systems (DCPS) which may exhibit multi-modal behavior. Any solution to this problem must recognize that: (1) different update algorithms may be needed in different modes according to the workload in each mode, and (2) temporal validity of data must be maintained not only in each mode but also during the mode switch. To strike a balance between data freshness and system schedulability, we propose a utilization-based scheduling selection (UBSS) strategy. We first introduce two synchronous mode switch algorithms, named search-based switch (SBS) and adjustment-based switch (ABS) to search for the proper switch point online and execute all update tasks in the new mode synchronously. SBS checks for temporal validity at the beginning time slot of each idle period in the schedule, while ABS relaxes this restriction through schedule adjustment. To support immediate mode switch, we propose an asynchronous switch algorithm named instant switch (IS) to reduce the switch delay. IS schedules outstanding jobs from the old mode together with the jobs in the new mode using the least-available-laxity-first scheduling policy. Our experimental results demonstrate the effectiveness of these three algorithms. They also show that UBSS strategy can significantly outperform a single fixed update algorithm in terms of maintaining better data freshness while incurring only limited online switch overhead.

1 Introduction

Maintaining data freshness is a key issue in many Cyber-Physical Systems (CPS) that depend on the timely processing of massive amount of real-time data [2], [3]. Real-time data track the current status of entities in the system and are typically sampled and stored in a real-time database system (RTDBS) [4]. A sampled data value is valid only for a certain time interval, called temporal validity interval  [5], and its freshness degrades with time. To maintain its freshness, a new data value needs to be installed into the database by a corresponding update task before the validity of its old value expires. Otherwise, the system may not be able to detect and respond to environmental changes in a timely fashion.