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

被引:23
作者
Han, Song [1 ]
Lam, Kam-Yiu [2 ]
Chen, Deji [4 ]
Xiong, Ming [5 ]
Wang, Jiantao [3 ]
Ramamritham, Krithi [6 ]
Mok, Aloysius K. [7 ]
机构
[1] Univ Connecticut, Dept Comp Sci & Engn, Storrs, CT 06269 USA
[2] City Univ Hong Kong, Dept Comp Sci, Hong Kong, Hong Kong, Peoples R China
[3] Huawei Tech, Noahs Ark Lab, Shenzhen, Peoples R China
[4] Tongji Univ, Shanghai, Peoples R China
[5] Google Inc, Mountain View, CA 94043 USA
[6] Indian Inst Technol, Dept Comp Sci & Engn, Bombay, Maharashtra, India
[7] Univ Texas Austin, Dept Comp Sci, Austin, TX 78712 USA
关键词
Dynamic cyber-physical systems; real-time database; mode switch; temporal validity; REAL-TIME SYSTEMS; SCHEDULABILITY ANALYSIS; SCHEDULING ALGORITHMS; PERIODS;
D O I
10.1109/TKDE.2015.2496199
中图分类号
TP18 [人工智能理论];
学科分类号
081104 ; 0812 ; 0835 ; 1405 ;
摘要
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.
引用
收藏
页码:756 / 769
页数:14
相关论文
共 26 条
[1]   Choosing task periods to minimise system utilisation in time triggered systems [J].
Burns, A ;
Davis, R .
INFORMATION PROCESSING LETTERS, 1996, 58 (05) :223-229
[2]  
Gustafsson T., 2004, P 2004 ACM S APPL CO, P846
[3]   Schedulability Analysis of Deferrable Scheduling Algorithms for Maintaining Real-Time Data Freshness [J].
Han, Song ;
Chen, Deji ;
Xiong, Ming ;
Lam, Kam-Yiu ;
Mok, Aloysius K. ;
Ramamritham, Krithi .
IEEE TRANSACTIONS ON COMPUTERS, 2014, 63 (04) :979-994
[4]   On Co-Scheduling of Update and Control Transactions in Real-Time Sensing and Control Systems: Algorithms, Analysis, and Performance [J].
Han, Song ;
Lam, Kam-Yiu ;
Wang, Jiantao ;
Ramamritham, Krithi ;
Mok, Aloysius K. .
IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING, 2013, 25 (10) :2325-2342
[5]   Online Scheduling Switch for Maintaining Data Freshness in Flexible Real-Time Systems [J].
Han, Song ;
Chen, Deji ;
Xiong, Ming ;
Mok, Aloysius K. .
2009 30TH IEEE REAL-TIME SYSTEMS SYMPOSIUM, PROCEEDINGS, 2009, :115-+
[6]  
Henia R, 2007, RTSS 2007: 28TH IEEE INTERNATIONAL REAL-TIME SYSTEMS SYMPOSIUM, PROCEEDINGS, P171
[7]   Similarity-based load adjustment for real-time data-intensive applications [J].
Ho, SJ ;
Kuo, TW ;
Mok, AK .
18TH IEEE REAL-TIME SYSTEMS SYMPOSIUM, PROCEEDINGS, 1997, :144-153
[8]  
Jianjun Li, 2011, Proceedings of the 2011 IEEE 32nd Real-Time Systems Symposium (RTSS 2011), P126, DOI 10.1109/RTSS.2011.19
[9]  
Lee E.A., 2014, Introduction to Embedded Systems - A Cyber-Physical Systems Approach, V1st
[10]   Workload-Efficient Deadline and Period Assignment for Maintaining Temporal Consistency under EDF [J].
Li, Jianjun ;
Xiong, Ming ;
Lee, Victor C. S. ;
Shu, LihChyun ;
Li, Guohui .
IEEE TRANSACTIONS ON COMPUTERS, 2013, 62 (06) :1255-1268