Abstract
The number of embedded systems in safety-critical applications are continuously increasing. These systems requires high level of reliability and have strict timing constraints specially in case of fault occurrence. One method to enhance the reliability and availability of these systems is to introduce the concept of optimization of diagnostic fault queries and real time database management systems. Both of them can be used to trace back failures to faults and trigger suitable recovery actions. Our major concern is the completion of diagnostic query in bounded time in order to satisfy timing constraints for fault recovery (e.g. actuator freezing). For this purpose it is important to provide a solution which can optimize the diagnostic fault queries in a manner that they can complete their execution within the pre-defined deadline of the real time system. Our proposed algorithm optimize the diagnostic fault queries using genetic algorithm, so that the overall Worst Case Execution Time (WCET) of these queries can be minimized. A diagnostic query is represented in the form of (i) Left Deep Tree (LDT) and (ii) Bushy Tree (BT). Each query tree is converted into multiple task graphs by considering different combinations of nodes (in query tree). Our genetic algorithm selects the task graph with minimum make span (scheduling length), so that the goal of fault diagnosis within the defined deadline of the real time system can be achieved. The evaluation based on our results shows that the WCET of the diagnostic queries is better in case of bushy trees and ring topology.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
References
Amin, S., Obermaisser, R.: Time-triggered scheduling of query executions for active diagnosis in distributed real-time systems. In: 2017 22nd IEEE International Conference on Emerging Technologies and Factory Automation (ETFA), pp. 1–9. IEEE (2017)
Ban, W., Lin, J., Tong, J., Li, S.: Query optimization of distributed database based on parallel genetic algorithm and max-min ant system. In: 2015 8th International Symposium on Computational Intelligence and Design (ISCID), vol. 2, pp. 581–585. IEEE (2015)
Bateman, F., Noura, H., Ouladsine, M.: Fault tolerant control strategy based on the DoA: application to UAV. In: 7th IFAC Symposium on Fault Detection Supervision and Safety of Technical Processes (2009)
Ducard, G.J.: Fault-Tolerant Flight Control and Guidance Systems: Practical Methods for Small Unmanned Aerial Vehicles. Springer, Heidelberg (2009)
Fang, L., Wang, P., Yan, J.: A multi-copy join optimization of information integration systems based on a genetic algorithm. In: The Third International Multi-Conference on Computing in the Global Information Technology, ICCGI 2008, pp. 223–228. IEEE (2008)
Idoudi, N., Duvallet, C., Sadeg, B., Bouaziz, R., Gargouri, F.: Structural model of real-time databases: an illustration. In: 2008 11th IEEE International Symposium on Object Oriented Real-Time Distributed Computing (ISORC), pp. 58–65. IEEE (2008)
Kandasamy, N., Hayes, J.P., Murray, B.T.: Time-constrained failure diagnosis in distributed embedded systems: application to actuator diagnosis. IEEE Trans. Parallel Distrib. Syst. 16(3), 258–270 (2005)
Kiefer, M., Heimel, M., Breß, S., Markl, V.: Estimating join selectivities using bandwidth-optimized kernel density models. Proc. VLDB Endow. 10(13), 2085–2096 (2017)
Kratica, J., Ljubić, I., Tošić, D.: A genetic algorithm for the index selection problem. In: Workshops on Applications of Evolutionary Computation, pp. 280–290. Springer (2003)
Li, J., Deshpande, A., Khuller, S.: Minimizing communication cost in distributed multi-query processing. In: IEEE 25th International Conference on Data Engineering, ICDE 2009, pp. 772–783. IEEE (2009)
Mingyao, X., Xiongfei, L.: Embedded database query optimization algorithm based on particle swarm optimization. In: 2015 Seventh International Conference on Measuring Technology and Mechatronics Automation (ICMTMA), pp. 429–432. IEEE (2015)
Muenchhof, M., Beck, M., Isermann, R.: Fault-tolerant actuators and drives structures, fault detection principles and applications. Ann. Rev. Control 33(2), 136–148 (2009)
Munnich, A., Farber, G.: Calculating worst-case execution times of transactions in databases for event-driven, hard real-time embedded systems. In: 2000 International Database Engineering and Applications Symposium, pp. 149–157. IEEE (2000)
Vellev, S.: An adaptive genetic algorithm with dynamic population size for optimizing join queries (2008)
Zhang, Q., Li, S., Xu, J.: Qscheduler: a tool for parallel query processing in database systems. In: 2014 19th International Conference on Engineering of Complex Computer Systems (ICECCS), pp. 73–76. IEEE (2014)
Zhang, Y., Jiang, J.: Bibliographical review on reconfigurable fault-tolerant control systems. IFAC Proc. Volumes 36(5), 257–268 (2003)
Acknowledgment
This work has been supported in part by the German Research Foundation (DFG) under project ADISTES (OB384/6-1, 629300).
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Tabassam, N., Amin, S., Obermaisser, R. (2020). Minimizing the Worst Case Execution Time of Diagnostic Fault Queries in Real Time Systems Using Genetic Algorithm. In: Arai, K., Kapoor, S. (eds) Advances in Computer Vision. CVC 2019. Advances in Intelligent Systems and Computing, vol 944. Springer, Cham. https://doi.org/10.1007/978-3-030-17798-0_46
Download citation
DOI: https://doi.org/10.1007/978-3-030-17798-0_46
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-17797-3
Online ISBN: 978-3-030-17798-0
eBook Packages: Intelligent Technologies and RoboticsIntelligent Technologies and Robotics (R0)