Real-Time Scheduling in Cyber-Physical System

A Cyber-Physical System (CPS) is a system where physical components and computational components are tightly integrated. Tasks in a CPS generally need to be accomplished correctly in terms of not only functionality but also punctuality. Real-time scheduling provides the methodology of determining the task execution order on a shared resource in order to make as many tasks in a CPS as possible to meet their deadlines. We addressed four different challenges in this dissertation, i.e., minimizing delay variations of real-time control tasks in a CPS, schedulability of jobs in a distributed real-time system (DRTS), tradeoff between energy savings and real-time stream deadline meetings in a wireless sensor network, and minimizing the impact of network dynamics on a wireless networked control system (WNCS).

For many CPSs, control performance is strongly dependent on delay variations of the control tasks. Such variations can come from a number of sources including task preemptions, variations in task workloads and perturbations in the physical environment. We designed a general adaptive framework that incorporates a powerful heuristic aiming to minimize delay variations.

In a DRTS, jobs are often executed on a number of processors and must complete by their end-to-end deadlines. Job deadline requirements may be violated if resource competition among different jobs on a given processor is not considered. We designed a distributed, locally optimal algorithm to assign local deadlines to the jobs on each processor to meet as many jobs? end-to-end deadline requirements as possible in a distributed soft real-time system.

Most of the wireless sensors are powered by batteries with a limited amount of energy, hence require the transmission to be energy efficient. Lower transmission rates can greatly reduce transmission energy. However, if the lowest transmission rate is selected, many messages can miss their deadlines, which degrades the Quality of Service (QoS) for CPS applications. We have designed an on-line transmission rate selection approach to maximize the number of packets to meet their deadlines with a small increase in the energy dissipation.

A key design challenge in a WNCS is to design efficient data link layer scheduling algorithms to achieve deterministic end-to-end real-time communication while the WNCS is disturbed by various physical events. In this work, we adopted a rhythmic task in adaptive to external disturbances and designed an effective approach to adjust existing schedule for all the nodes in the WNCS when the disturbances happen.