Neural Ordinary Differential Equations (Neural ODEs or NODEs) excel at modeling continuous dynamical systems from observational data, especially when the data is irregularly sampled. However, existing training methods predominantly rely on numerical ODE solvers, which are time-consuming and prone to accumulating numerical errors over time due to autoregression. In this work, we propose VF-NODE, a novel approach based on the variational formulation (VF) to accelerate the training of NODEs. Unlike existing training methods, the proposed VF-NODEs implement a series of global integrals, thus evaluating Deep Neural Network (DNN)--based vector fields only at specific observed data points. This strategy drastically reduces the number of function evaluations (NFEs). Moreover, our method eliminates the use of autoregression, thereby reducing error accumulations for modeling dynamical systems. Nevertheless, the VF loss introduces oscillatory terms into the integrals when using the Fourier basis. We incorporate Filon's method to address this issue. To further enhance the performance for noisy and incomplete data, we employ the natural cubic spline regression to estimate a closed-form approximation. We provide a fundamental analysis of how our approach minimizes computational costs. Extensive experiments demonstrate that our approach accelerates NODE training by 10 to 1000 times compared to existing NODE-based methods, while achieving higher or comparable accuracy in dynamical systems. The code is available at https://github.com/ZhaoHongjue/VF-NODE-ICLR2025.

This paper introduces the Real-DRL framework for safety-critical autonomous systems, enabling runtime learning of a deep reinforcement learning (DRL) agent to develop safe and high-performance action policies in real plants while prioritizing safety. The Real-DRL consists of three interactive components: a DRL-Student, a PHY-Teacher, and a Trigger. The DRL-Student is a DRL agent that innovates in the dual self-learning and teaching-to-learn paradigm and the safety-status-dependent batch sampling. On the other hand, PHY-Teacher is a physics-model-based design of action policies that focuses solely on safety-critical functions. PHY-Teacher is novel in its real-time patch for two key missions: i) fostering the teaching-to-learn paradigm for DRL-Student and ii) backing up the safety of real plants. The Trigger manages the interaction between the DRL-Student and the PHY-Teacher. Powered by the three interactive components, the Real-DRL can effectively address safety challenges that arise from the unknown unknowns and the Sim2Real gap. Additionally, Real-DRL notably features i) assured safety, ii) automatic hierarchy learning (i.e., safety-first learning and then high-performance learning), and iii) safety-informed batch sampling to address the experience imbalance caused by corner cases. Experiments with a real quadruped robot, a quadruped robot in Nvidia Isaac Gym, and a cart-pole system, along with comparisons and ablation studies, demonstrate the Real-DRL's effectiveness and unique features.

Purely data-driven deep neural networks (DNNs) applied to physical engineering systems can infer relations that violate physics laws, thus leading to unexpected consequences. To address this challenge, we propose a physics-knowledge-enhanced DNN framework called Phy-Taylor, accelerating learning-compliant representations with physics knowledge. The Phy-Taylor framework makes two key contributions; it introduces a new architectural physics-compatible neural network (PhN) and features a novel compliance mechanism, which we call physics-guided neural network (NN) editing. The PhN aims to directly capture nonlinear physical quantities, such as kinetic energy, electrical power, and aerodynamic drag force. To do so, the PhN augments NN layers with two key components: 1) monomials of the Taylor series for capturing physical quantities and 2) a suppressor for mitigating the influence of noise. The NN editing mechanism further modifies network links and activation functions consistently with physics knowledge. As an extension, we also propose a self-correcting Phy-Taylor framework for safety-critical control of autonomous systems, which introduces two additional capabilities: 1) safety relationship learning and 2) automatic output correction when safety violations occur. Through experiments, we show that Phy-Taylor features considerably fewer parameters and a remarkably accelerated training process while offering enhanced model robustness and accuracy.

This paper proposes the Phy-DRL: a physics-regulated deep reinforcement learning (DRL) framework for safety-critical autonomous systems. The Phy-DRL has three distinguished invariant-embedding designs: i) residual action policy (i.e., integrating data-driven-DRL action policy and physics-model-based action policy), ii) automatically constructed safety-embedded reward, and iii) physics-model-guided neural network (NN) editing, including link editing and activation editing. Theoretically, the Phy-DRL exhibits 1) a mathematically provable safety guarantee and 2) strict compliance of critic and actor networks with physics knowledge about the action-value function and action policy. Finally, we evaluate the Phy-DRL on a cart-pole system and a quadruped robot. The experiments validate our theoretical results and demonstrate that Phy-DRL features guaranteed safety compared to purely data-driven DRL and solely model-based design while offering remarkably fewer learning parameters and fast training towards safety guarantee.

Abstract Advances in deep learning have revolutionized cyber‐physical applications, including the development of autonomous vehicles. However, real‐world collisions involving autonomous control of vehicles have raised significant safety concerns regarding the use of deep neural networks (DNNs) in safety‐critical tasks, particularly perception. The inherent unverifiability of DNNs poses a key challenge in ensuring their safe and reliable operation. In this work, we propose perception simplex ( ), a fault‐tolerant application architecture designed for obstacle detection and collision avoidance. We analyse an existing LiDAR‐based classical obstacle detection algorithm to establish strict bounds on its capabilities and limitations. Such analysis and verification have not been possible for deep learning‐based perception systems yet. By employing verifiable obstacle detection algorithms, identifies obstacle existence detection faults in the output of unverifiable DNN‐based object detectors. When faults with potential collision risks are detected, appropriate corrective actions are initiated. Through extensive analysis and software‐in‐the‐loop simulations, we demonstrate that provides deterministic fault tolerance against obstacle existence detection faults, establishing a robust safety guarantee.

Computer Science is being increasingly used in medicine to improve quality of care and patient outcome. Clinical Decision Support Systems (CDSSs) that codify clinical Best Practice Guidelines (BPGs) and provide situation-specific advice to physicians CDSSs have shown effectiveness in reducing adverse patient outcomes during clinical evaluations. However, representing both the BPG and the associated physical processes in software is complex and tedious, making CDSSs prone to bugs. This can be mitigated using a modular software architecture that encapsulates computational representation of physical processes for finer-grained development and verification leading to improved comprehensibility, shareability and maintainability. This paper discusses the sources of complexity in CDSSs, and proposes a software architecture that consists of an encoding of the BPG's medical knowledge into executable representations comprising of a patient digital twin, diagnosis and treatment workflows, an adherence monitor, a User Interface (UI) and a middleware for seamless integration with existing Hospital Information Systems. We developed a CDSS for Pediatric Sepsis Management co-designed by physicians using our approach. We use the Fluid Resuscitation therapy of this CDSS as a case study to illustrate the development process.

Timing correctness is crucial in a multi-criticality real-time system, such as an autonomous driving system. It has been recently shown that these systems can be vulnerable to timing inference attacks, mainly due to their predictable behavioral patterns. Existing solutions like schedule randomization cannot protect against such attacks, often limited by the system’s real-time nature. This article presents “ SchedGuard++ ”: a temporal protection framework for Linux-based real-time systems that protects against posterior schedule-based attacks by preventing untrusted tasks from executing during specific time intervals. SchedGuard++ supports multi-core platforms and is implemented using Linux containers and a customized Linux kernel real-time scheduler. We provide schedulability analysis assuming the Logical Execution Time (LET) paradigm, which enforces I/O predictability. The proposed response time analysis takes into account the interference from trusted and untrusted tasks and the impact of the protection mechanism. We demonstrate the effectiveness of our system using a realistic radio-controlled rover platform. Not only is “ SchedGuard++ ” able to protect against the posterior schedule-based attacks, but it also ensures that the real-time tasks/containers meet their temporal requirements.

This article proposes a novel extension of the Simplex architecture with model switching and model learning to achieve safe velocity regulation of self-driving vehicles in dynamic and unforeseen environments. To guarantee the reliability of autonomous vehicles, an ℒ 1 adaptive controller that compensates for uncertainties and disturbances is employed by the Simplex architecture as a verified high-assurance controller (HAC) to tolerate concurrent software and physical failures. Meanwhile, the safe switching controller is incorporated into the HAC for safe velocity regulation in the dynamic (prepared) environments, through the integration of the traction control system and anti-lock braking system. Due to the high dependence of vehicle dynamics on the driving environments, the HAC leverages the finite-time model learning to timely learn and update the vehicle model for ℒ 1 adaptive controller, when any deviation from the safety envelope or the uncertainty measurement threshold occurs in the unforeseen driving environments. With the integration of ℒ 1 adaptive controller, safe switching controller and finite-time model learning, the vehicle’s angular and longitudinal velocities can asymptotically track the provided references in the dynamic and unforeseen driving environments, while the wheel slips are restricted to safety envelopes to prevent slipping and sliding. Finally, the effectiveness of the proposed Simplex architecture for safe velocity regulation is validated by the AutoRally platform.

Many cyber-physical systems are offloading computation-heavy programs to hardware accelerators (e.g., GPU and TPU) to reduce execution time. These applications will self-suspend between offloading data to the accelerators and obtaining the returned results. Previous efforts have shown that self-suspending tasks can cause scheduling anomalies, but none has examined inter-task communication. This paper aims to explore self-suspending tasks' data chain latency with periodic activation and asynchronous message passing. We first present the cause for suspension-induced delays and worst-case latency analysis. We then propose a rule for utilizing the hardware co-processors to reduce data chain latency and schedulability analysis. Simulation results show that the proposed strategy can improve overall latency while preserving system schedulability.

Perception of obstacles remains a critical safety concern for autonomous vehicles. Real-world collisions have shown that the autonomy faults leading to fatal collisions originate from obstacle existence detection. Open source autonomous driving implementations show a perception pipeline with complex interdependent Deep Neural Networks. These networks are not fully verifiable, making them unsuitable for safety-critical tasks. In this work, we present a safety verification of an existing LiDAR based classical obstacle detection algorithm. We establish strict bounds on the capabilities of this obstacle detection algorithm. Given safety standards, such bounds allow for determining LiDAR sensor properties that would reliably satisfy the standards. Such analysis has as yet been unattainable for neural network based perception systems. We provide a rigorous analysis of the obstacle detection system with empirical results based on real-world sensor data.

This paper presents a self-cueing real-time frame-work for attention prioritization in AI-enabled visual perception systems that minimizes a notion of state uncertainty. By attention prioritization we refer to inspecting some parts of the scene before others in a criticality-aware fashion. By self-cueing, we refer to not needing external cueing sensors for prioritizing attention, thereby simplifying design. We show that attention prioritization saves resources, thus enabling more efficient and responsive real-time object tracking on resource-limited embedded platforms. The system consists of two components: First, an optical flow-based module decides on the regions to be viewed on a subframe level, as well as their criticality. Second, a novel batched proportional balancing (BPB) scheduling policy decides how to schedule these regions for inspection by a deep neural network (DNN), and how to parallelize execution on the GPU. We implement the system on an NVIDIA Jetson Xavier platform, and empirically demonstrate the superiority of the proposed architecture through an extensive evaluation using a real-word driving dataset.

This paper explorescriticality-based real-time schedulingof neural-network-based machine inference pipelines in cyber-physical systems (CPS) to mitigate the effect of algorithmic priority inversion. We specifically focus on the perception subsystem, an important subsystem feeding other components (e.g., planning and control). In general, priority inversion occurs in real-time systems when computations that are of lower priority are performed together with or ahead of those that are of higher priority. In current machine perception software, significant priority inversion occurs becauseresource allocationto the underlying neural network models does not differentiate between critical and less critical data within a scene. To remedy this problem, in recent work, we proposed an architecture to partition the input data into regions of different criticality, then formulated a utility-based optimization problem to batch and schedule their processing in a manner that maximizes confidence in perception results, subject to criticality-based time constraints. This journal extension matures the work in several directions: (i) We extend confidence maximization to a generalized utility optimization formulation that accounts for criticality in the utility function itself, offering finer-grained control over resource allocation within the perception pipeline; (ii) we further instantiate and compare two different criticality metrics (distance-based and relative velocity-based) to understand their relative advantages; and (iii) we explore the limitations of the approach, specifically how inaccuracies in criticality-based attention cueing affect performance. All experiments are conducted on the NVIDIA Jetson AGX Xavier platform with a real-world driving dataset.

Real-time systems have recently been shown to be vulnerable to timing inference attacks, mainly due to their predictable behavioral patterns. Existing solutions such as schedule randomization lack the ability to protect against such attacks, often limited by the system's real-time nature. This paper presents “SchedGuard”: a temporal protection framework for Linux-based hard real-time systems that protects against posterior scheduler side-channel attacks by preventing untrusted tasks from executing during specific time segments. SchedGuard is integrated into the Linux kernel using cgroups, making it amenable to use with container frameworks. We demonstrate the effectiveness of our system using a realistic radio-controlled rover platform and synthetically generated workloads. Not only is SchedGuard able to protect against the attacks mentioned above, but it also ensures that the real-time tasks/containers meet their temporal requirements.

Securing cyber-physical systems (CPS) against malicious attacks is of paramount importance because these attacks may cause irreparable damages to physical systems. Recent studies have revealed that control programs running on CPS devices suffer from both control-oriented attacks (e.g., code-injection or code-reuse attacks) and data-oriented attacks (e.g., non-control data attacks). Unfortunately, existing detection mechanisms are insufficient to detect runtime data-oriented exploits, due to the lack of runtime execution semantics checking. In this work, we propose Orpheus, a new security methodology for defending against data-oriented attacks by enforcing cyber-physical execution semantics. We first present a general method for reasoning cyber-physical execution semantics of a control program (i.e., causal dependencies between the physical context/event and program control flows), including the event identification and dependence analysis. As an instantiation of Orpheus, we then present a new program behavior model, i.e., the event-aware finite-state automaton (eFSA). eFSA takes advantage of the event-driven nature of CPS control programs and incorporates event checking in anomaly detection. It detects data-oriented exploits if a specific physical event is missing along with the corresponding event dependent state transition. We evaluate our prototype's performance by conducting case studies under data-oriented attacks. Results show that eFSA can successfully detect different runtime attacks. Our prototype on Raspberry Pi incurs a low overhead, taking 0.0001s for each state transition integrity checking, and 0.063s~0.211s for the cyber-physical contextual consistency checking.

The paper discusses algorithmic priority inversion in mission-critical machine inference pipelines used in modern neural-network-based cyber-physical applications, and develops a scheduling solution to mitigate its effect. In general, priority inversion occurs in real-time systems when computations that are of lower priority are performed together with or ahead of those that are of higher priority.1In current machine intelligence software, significant priority inversion occurs on the path from perception to decision-making, where the execution of underlying neural network algorithms does not differentiate between critical and less critical data. We describe a scheduling framework to resolve this problem, and demonstrate that it improves the system’s ability to react to critical inputs, while at the same time reducing platform cost.

During the system development process, domain experts and developers often make assumptions about specifications and implementations. However, most of the assumptions being taken for granted by domain experts and developers are too tedious to be documented by them. When these unspecified assumptions are violated in an environment in which the system operates, failures can occur. According to the U.S. Food and Drug Administration (FDA) medical device recall database, medical device recalls caused by software failures are at an all-time high. One major cause of these recalls is violations of unspecified assumptions made in medical systems. Therefore, it is crucial to have tools to automatically identify such unspecified assumptions at an early stage of the systems development process to avoid fatal failures. In this article, we present a tool called Unspecified Assumption Carrier Finder ( UACFinder ) that uses data mining techniques to automatically identify potential syntactic carriers of unspecified assumptions in system design models. The main idea of this tool is based on the observation we obtained from our earlier analysis of software failures in medical device recalls caused by unspecified assumptions. We observed that unspecified assumptions often exist in medical systems through syntactic carriers , such as constant variables , frequently read/updated variables , and frequently executed action sequences . Therefore, we develop the UACFinder to automatically find these potential unspecified assumption syntactic carriers rather than unspecified assumptions themselves. Once the UACFinder identifies the potential unspecified assumption syntactic carriers , domain experts and developers can validate whether these syntactic carriers indeed carry unspecified assumptions. We use a simplified cardiac arrest treatment scenario as a case study to evaluate the UACFinder in mining potential syntactic carriers of unspecified assumptions. In addition, we invite a medical doctor to validate unspecified assumptions carried by the mined syntactic carriers . The case study demonstrates that the UACFinder is effective in helping to identify potential unspecified assumptions from system design models.

The Unmanned aerial vehicles (UAVs) sector is fast-expanding. Protection of real-time UAV applications against malicious attacks has become an urgent problem that needs to be solved. Denial-of-service (DoS) attack aims to exhaust system resources and cause important tasks to miss deadlines. DoS attack may be one of the common problems of UAV systems, due to its simple implementation. In this paper, we present a software framework that offers DoS attack-resilient control for real-time UAV systems using containers: ContainerDrone. The framework provides defense mechanisms for three critical system resources: CPU, memory, and communication channel. We restrict attacker's access to CPU core set and utilization. Memory bandwidth throttling limits attacker's memory usage. By simulating sensors and drivers in the container, a security monitor constantly checks DoS attacks over communication channels. Upon the detection of a security rule violation, the framework switches to the safety controller to mitigate the attack. We implemented a prototype quadcopter with commercially off-the-shelf (COTS) hardware and open-source software. Our experimental results demonstrated the effectiveness of the proposed framework defending against various DoS attacks.

Improving patient care safety is an ultimate objective for medical cyber-physical systems. A recent study shows that the patients' death rate can be significantly reduced by computerizing medical best practice guidelines. To facilitate the development of computerized medical best practice guidelines, statecharts are often used as a modeling tool because of their high resemblances to disease and treatment models and their capabilities to provide rapid prototyping and simulation for clinical validations. However, some implementations of statecharts, such as Yakindu statecharts, are priority-based and have synchronous execution semantics which makes it difficult to model certain functionalities that are essential in modeling medical guidelines, such as two-way communications and configurable execution orders. Rather than introducing new statechart elements or changing the statechart implementation's underline semantics, we use existing basic statechart elements to design model patterns for the commonly occurring issues. In particular, we show the design of model patterns for two-way communications and configurable execution orders and formally prove the correctness of these model patterns. We further use a simplified airway laser surgery scenario as a case study to demonstrate how the developed model patterns address the two-way communication and configurable execution order issues and their impact on validation and verification of medical safety properties.

Simulink is widely used for model-driven development (MDD) of cyber-physical systems. Typically, the Simulink-based development starts with Stateflow modeling, followed by simulation, validation, and code generation mapped to physical execution platforms. However, recent trends have raised the demands of rigorous verification on safety-critical applications to prevent intrinsic development faults and improve the system dependability, which is unfortunately challenging. Even though the constructed Stateflow model and the generated code pass the validation of Simulink Design Verifier and Simulink Polyspace, respectively, the system may still fail due to some implicit defects contained in the design model (design defect) and the generated code (implementation defects). In this article, we bridge the Stateflow-based MDD and a well-defined rigorous verification to reduce development faults. First, we develop a self-contained toolkit to translate a Stateflow model into timed automata, where major advanced modeling features in Stateflow are supported. Taking advantage of the strong verification capability of Uppaal, we can not only find bugs in Stateflow models that are missed by Simulink Design Verifier but also check more important temporal properties. Next, we customize a runtime verifier for the generated non-intrusive VHDL and C code of a Stateflow model for monitoring. The major strength of the customization is the flexibility to collect and analyze runtime properties with a pure software monitor, which offers more opportunities for engineers to achieve high reliability of the target system compared with the traditional act that only relies on Simulink Polyspace. In this way, safety-critical properties are both verified at the model level and at the consistent system implementation level with physical execution environment in consideration. We apply our approach to the development of a typical cyber-physical system-train communication controller based on the IEC standard 61375. Experiments show that more ambiguousness in the standard are detected and confirmed and more development faults and those corresponding errors that would lead to system failure have been removed. Furthermore, the verified implementation has been deployed on real trains.

According to the U.S. Food and Drug Administration (FDA) medical device recall database, medical device recalls are at an all-time high. One of the major causes of the recalls is due to implicit assumptions of which either the medical device operating environment does not match, or the device operators are not aware of. In this paper, we present IAFinder (Implicit Assumption Finder), a tool that uses data mining techniques to automatically extract invariants from design models implemented with statecharts. By identifying invariants that are not explicitly specified in the design models, we are able to find implicit assumptions and better facilitate domain experts to validate them and make the validated implicit assumptions explicit. We use a cardiac arrest statechart model as a case study to illustrate the usage of IAFinder in identifying implicit assumptions.

As the complexity of Cyber-Physical Systems (CPS) increases, it becomes increasingly challenging to ensure CPS reliability, especially in the presence of software and/or physical failures. The Simplex architecture is shown to be an efficient tool to address software failures in such systems. When physical failures exist, however, Simplex may not function correctly because physical failures could change system dynamics and the original Simplex design may not work for the new faulty system. To address concurrent software and physical failures, this article presents the RSimplex architecture, which integrates Robust Fault-Tolerant Control (RFTC) techniques into the Simplex architecture. It includes the uncertainty monitor, the High-Performance Controller (HPC), the Robust High-Assurance Controller (RHAC), and the decision logic that triggers the switch of the controllers. Based on the output of the uncertainty monitor, we introduce a monitor-based switching rule in the decision logic in addition to the traditional envelope-based rule. The RHAC is designed based on RFTCs. We show that RSimplex can efficiently handle a class of software and physical failures.

In this paper, we present a formal model-driven design approach to establish a safety-assured implementation of multifunction vehicle bus controller (MVBC), which controls the data transmission among the devices of the vehicle. First, the generic models and safety requirements described in International Electrotechnical Commission Standard 61375 are formalized as time automata and timed computation tree logic formulas, respectively. With model checking tool Uppaal, we verify whether or not the constructed timed automata satisfy the formulas and several logic inconsistencies in the original standard are detected and corrected. Then, we apply the code generation tool Times to generate C code from the verified model, which is later synthesized into a real MVBC chip, with some handwriting glue code. Furthermore, the runtime verification tool RMOR is applied on the integrated code, to verify some safety requirements that cannot be formalized on the timed automata. For evaluation, we compare the proposed approach with existing MVBC design methods, such as BeagleBone, Galsblock, and Simulink. Experiments show that more ambiguousness or bugs in the standard are detected during Uppaal verification, and the generated code of Times outperforms the C code generated by others in terms of the synthesized binary code size. The errors in the standard have been confirmed and the resulting MVBC has been deployed in the real train communication network.

For a cyber-physical system, its execution behaviors are often impacted by human interactive behaviors. However, the assumptions about a cyber-physical systems expected human interactive behaviors are often informally documented, or even left implicit and unspecified in system design. Unfortunately, such implicit human interaction assumptions made by safety critical cyber-physical systems, such as medical cyber-physical systems (M-CPS), can lead to catastrophes. Several recent U.S. Food and Drug Administration (FDA) medical device recalls are due to implicit human interaction assumptions. In this paper, we classify the categories of constraints in human interaction assumptions in the medical domain and develop a mathematical assumption model that allow M-CPS engineers to explicitly and precisely specify assumptions about human interactions. Algorithms are developed to integrate mathematical assumption models with system model so that the safety of the system can be not only validated by both medical and engineering professionals but also formally verified by existing formal verification tools. We use an FDA recalled medical ventilator scenario as a case study to show how the mathematical assumption model and its integration in M-CPS design may improve the safety of the ventilator and M-CPS in general.

Improving effectiveness and safety of patient care is an ultimate objective for medical cyber-physical systems. Many medical best practice guidelines exist in the format of hospital handbooks which are often lengthy and difficult for medical staff to remember and apply clinically. Statechart is an effective tool to model medical guidelines and enables clinical validation with medical staffs. However, some advanced statechart elements could result in high cost, such as low understandability, high difficulty in clinical validation, formal verification, and failure trace back. The paper presents a pattern-based statechart modeling approach for medical best practice guidelines, i.e., model medical guidelines with basic statechart elements and model patterns which are built upon these basic elements. For practical use, we implement the proposed approach based on open-source Yakindu statecharts. We also use a simplified cardiac arrest scenario provided to our team by Carle Foundation Hospital as a case study to validate the proposed approach.

Improving safety of patient care is an ultimate objective for medical systems. Though many medical best practice guidelines exist and are in hospital handbooks, they are often lengthy and difficult for medical professionals to remember and apply clinically. Hence, developing safe and correct medical best practice guideline systems is an urgent need. Many efforts have been made in modeling, clinical validation, model level formal verification of medical best practice guidelines. However, code level verification is also necessary to develop verifiable safe and correct medical guideline systems. The paper presents an approach to transform safety properties specified in verifiable medical guideline models to JavaMOP runtime monitor and specify JavaMOP monitors to runtime monitor these safety properties during execution of Java code generated from validated and verified statechart models. We use a simplified version of a cardiac arrest scenario provided by Carle Foundation Hospital as a case study to validate the proposed approach.

Implicit physical environment assumptions made by safety critical cyber-physical systems, such as medical cyber-physical systems (M-CPS), can lead to catastrophes. Several recent U.S. Food and Drug Administration (FDA) medical device recalls are due to implicit physical environment assumptions. In this paper, we develop a mathematical assumption model and composition rules that allow M-CPS engineers to explicitly and precisely specify assumptions about the physical environment in which the designed M-CPS operates. Algorithms are developed to integrate the mathematical assumption model with system model so that the safety of the system can be not only validated by both medical and engineering professionals but also formally verified by existing formal verification tools. We use an FDA recalled medical ventilator scenario as a case study to show how the mathematical assumption model and its integration in M-CPS design may improve the safety of the ventilator and M-CPS in general.

This paper presents a new schedulability test for safety-critical software undergoing a transition from single-core to multicore systems - a challenge faced by multiple industries today. Our migration model consists of a schedulability test and execution model. Its properties enable us to obtain a utilization bound that places an allowable limit on total task execution times. Evaluation results demonstrate the advantages of our scheduling model over competing resource partitioning approaches, such as Periodic Server and TDMA.

Improving effectiveness and safety of patient care is an ultimate objective for medical cyber-physical systems. A recent study shows that the patients' death rate can be reduced by computerizing medical guidelines [20]. Most existing medical guideline models are validated and/or verified based on the assumption that all necessary medical resources needed for a patient care are always available. However, the reality is that some medical resources, such as special medical equipment or medical specialists, can be temporarily unavailable for an individual patient. In such cases, safety properties validated and/or verified in existing medical guideline models without considering medical resource availability may not hold any more.

Using wireless networks in medical Cyber-Physical Systems could be challenging. Because the medical system not only assists the medical personnel to deliver medical services to the patient but also needs to deal with accidental situations such as communication failures without compromising the patient's safety. Previous research work tackled the communication failure problems in medical CPS from architecture perspectives. However, as medical devices configurations become more complex when a medical CPS is composed of many medical devices, we need to know that whether the certain configuration and a combination of the devices will not compromise the patient's safety. We present an algorithm to tackle the problem that whether a given system configuration exists a possible series of system transitions that allows the physicians to perform medical operations; in the mean time, the system transitions ensure the patient's safety while communication failures may happen during the transitions.

As technology advances, medical devices are playing increasingly more important roles in patient care. Unfortunately, based on the U.S. Food and Drug Administration (FDA) data, medical device recalls are at an all time high. One of the major causes of the recalls is due to defective software. In fact, one in every three medical devices that use software for operation has been recalled because of failures in the software itself. Unlike traditional software, software-based medical devices have specific domain fault modes, and these fault modes have been not addressed in software design literature, such as dosage calculation fault. In this paper, we first present a process that collects software-related medical device recalls from the FDA database. Collecting all software-related medical device recalls is an effort that needs the support and contributions from a large research, industrial, and medical community, To facility such effort, we have developed a web-based platform for different users to contribute and share new software-related medical device recalls into the collection. Second, we analyze one hundred software-related recalls that we have collected from the FDA database. Our analysis reveals that there are four major categories of software failures in medical device recalls and implicit assumptions made by medical device manufacturers are among one of the leading causes in medical device recalls. Last, we present an approach for implicit assumption management in medical cyber-physical system designs.

Use of telecommunication technologies for remote, continuous monitoring of patients can enhance effectiveness of emergency ambulance care during transport from rural areas to a regional center hospital. However, the communication along the various routes in rural areas may have wide bandwidth ranges from 2G to 4G; some regions may have only lower satellite bandwidth available. Bandwidth fluctuation together with real-time communication of various clinical multimedia pose a major challenge during rural patient ambulance transport.; [email protected] availability of a pre-transport route-dependent communication bandwidth database is an important resource in remote monitoring and clinical multimedia transmission in rural ambulance transport. Here, we present a geo-communication dataset from extensive profiling of 4 major US mobile carriers in Illinois, from the rural location of Hoopeston to the central referral hospital center at Urbana. In collaboration with Carle Foundation Hospital, we developed a profiler, and collected various geographical and communication traces for realistic emergency rural ambulance transport scenarios. Our dataset is to support our ongoing work of proposing "physiology-aware DASH", which is particularly useful for adaptive remote monitoring of critically ill patients in emergency rural ambulance transport. It provides insights on ensuring higher Quality of Service (QoS) for most critical clinical multimedia in response to changes in patients' physiological states and bandwidth conditions. Our dataset is available online1 for research community.

In this article, we describe a general methodology for enhancing sensing accuracy in cyber-physical systems that involve structured human interactions in noisy physical environment. We define structured human interactions as domain-specific workflow. A novel workflow-aware sensing model is proposed to jointly correct unreliable sensor data and keep track of states in a workflow. We also propose a new inference algorithm to handle cases with partially known states and objects as supervision. Our model is evaluated with extensive simulations. As a concrete application, we develop a novel log service called Emergency Transcriber , which can automatically document operational procedures followed by teams of first responders in emergency response scenarios. Evaluation shows that our system has significant improvement over commercial off-the-shelf (COTS) sensors and keeps track of workflow states with high accuracy in noisy physical environment.

Wireless medical cyber-physical systems are widely adopted in the daily practices of medicine, where huge amounts of data are sampled by the wireless medical devices and sensors, and is passed to the decision support systems (DSSs). Many text-based guidelines have been encoded for work-flow simulation of DSS to automate health care based on those collected data. But for some complex and life-critical diseases, it is highly desirable to automatically rigorously verify some complex temporal properties encoded in those data, which brings new challenges to current simulation-based DSS with limited support of automatical formal verification and real-time data analysis. In this paper, we conduct the first study on applying runtime verification to cooperate with current DSS based on real-time data. Within the proposed technique, a user-friendly domain specific language, named DRTV, is designed to specify vital real-time data sampled by medical devices and temporal properties originated from clinical guidelines. Some interfaces are developed for data acquisition and communication. Then, for medical practice scenarios described in DRTV model, we will automatically generate event sequences and runtime property verifier automata. If a temporal property violates, real-time warnings will be produced by the formal verifier and passed to medical DSS. We have used DRTV to specify different kinds of medical care scenarios and have applied the proposed technique to assist existing wireless medical cyber-physical system. As presented in experiment results, in terms of warning detection, it outperforms the only use of DSS or human inspection, and improves the quality of clinical health care of hospital.

The ultimate objective of medical cyber-physical systems is to enhance the safety and effectiveness of patient care. To ensure safe and effective care during emergency patient transfer from rural areas to center tertiary hospitals, reliable and real-time communication is essential. Unfortunately, real-time monitoring of patients involves transmission of various clinical multimedia data including videos, medical images, and vital signs, which requires use of mobile network with high-fidelity communication bandwidth. However, the wireless networks along the roads in rural areas range from 4G to 2G to low speed satellite links, which poses a significant challenge to transmit critical patient information. In this paper, we present a bandwidth-compliant criticality-aware system for transmission of massive clinical multimedia data adaptive to varying bandwidths during patient transport. Model-based clinical automata are used to determine the criticality of clinical multimedia data. We borrow concepts from DASH, and propose physiology-aware adaptation techniques to transmit more critical clinical data with higher fidelity in response to changes in disease, clinical states, and bandwidth condition. In collaboration with Carle's ambulance service center, we develop a bandwidth profiler, and use it as proof of concept to support our experiments. Our preliminary evaluation results show that our solutions ensure that most critical patient's clinical data are communicated with higher fidelity.

Paroxysmal sympathetic hyperactivity (PSH) is an important clinical problem of severe traumatic brain injury (TBI) which incurs approximately 90% of all TBI-related costs. However, current detection approach is hampered by no consensus clinical diagnostic criteria, paroxysmal episode feature with complex manifestations, and already overloaded clinical activities. These limitations cause delayed recognitions which result in poor clinical outcomes. In this paper, we design an integrated Medical Cyber-Physical System (Medical CPS) for early detection of paroxysmal sympathetic hyperactivity patients. First, a formal model is proposed to describe clinical diagnostic criteria. With the formalized models employed, we implement an early detector and integrate it with revised medical device adapters into Medical CPS. Our system will monitor patient conditions automatically and continuously to relieve medical staff from the heavy burden of clinical activities and provide timely decision supports. Evaluations on 107 clinical cases extracted from medical publications demonstrate the effectiveness and the efficiency of our integrated system.

Today, sepsis syndrome is one of the leading cause of death globally, and is of great clinical importance. In this paper, we present a self-adaptively evolutionary sepsis screening system to shorten the time of syndrome detection and improve the positive effect of treatment, with the screening frequency and content can be automatically adjusted according to the current status of the patient. First, we propose a novel graphical computation model named AdapDBN with a clearly defined syntax for the medical knowledge presentation, especially for the presentation of the pathophysiology model of the disease. Then, the semantics of AdapDBN is formally defined for the evolutionary inference of syndrome onset probability. Finally, we demonstrate how to initialize AdapDBN with sepsis-related epidemiologic statics, published clinical research and physician's knowledge and how to incorporate it into existing sepsis screening and decision support flow. We evaluate its effectiveness and superiority with comparisons to existing computation techniques.

As patient condition changes rapidly in acute care, the monitoring and treatment plan must be adapted accordingly to ensure safe and effective patient care. Most current medical monitoring systems provide little contextual information on patient state. We present best practice assist system to help medical staff assess patient state more accurately and adapt her care plan according to the best practice guidelines and community consensus. The main components of our system are 1) an efficient and clinically sound representation of patient state in the form of disease and interacting organ states 2) a best practice manager that encodes the best practice monitoring and treatment guidelines for a given patient condition. Both components are modeled using finite state machine formalism. In addition, we have implemented a patient control panel and a graphical display to simulate clinical scenarios. Using a cardiac arrest scenario, we demonstrate how our system can help medical staff with patient assessment and adherence to best practice.

Simulink is widely used for model driven development (MDD) of industrial software systems. Typically, the Simulink based development is initiated from Stateflow modeling, followed by simulation, validation and code generation mapped to physical execution platforms. However, recent industrial trends have raised the demands of rigorous verification on safety-critical applications, which is unfortunately challenging for Simulink. In this paper, we present an approach to bridge the Stateflow based model driven development and a well- defined rigorous verification. First, we develop a self- contained toolkit to translate Stateflow model into timed automata, where major advanced modeling features in Stateflow are supported. Taking advantage of the strong verification capability of Uppaal, we can not only find bugs in Stateflow models which are missed by Simulink Design Verifier, but also check more important temporal properties. Next, we customize a runtime verifier for the generated nonintrusive VHDL and C code of Stateflow model for monitoring. The major strength of the customization is the flexibility to collect and analyze runtime properties with a pure software monitor, which opens more opportunities for engineers to achieve high reliability of the target system compared with the traditional act that only relies on Simulink Polyspace. We incorporate these two parts into original Stateflow based MDD seamlessly. In this way, safety-critical properties are both verified at the model level, and at the consistent system implementation level with physical execution environment in consideration. We apply our approach on a train controller design, and the verified implementation is tested and deployed on a real hardware platform.

The high degree of predictability in real-time systems makes it possible for adversaries to launch timing inference attacks such as those based on side-channels and covert-channels. We present TaskShuffler, a schedule obfuscation method aimed at randomizing the schedule for such systems while still providing the real-time guarantees that are necessary for their safe operation. This paper also analyzes the effect of these mechanisms by presenting schedule entropy - a metric to measure the uncertainty (as perceived by attackers) introduced by TaskShuffler. These mechanisms will increase the difficulty for would-be attackers thus improving the overall security guarantees for real-time systems.

The paper considers the challenge of maximizing the quality of information collected to meet decision needs of real-time Internet-of-Things applications. A novel scheduling model is proposed, where applications need multiple data items to make decisions, and where individual data items can be captured at different levels of quality. We assume the existence of a single bottleneck over which data objects are collected and schedule the transmission of these objects over the bottleneck to meet decision deadlines and data validity constraints, while maximizing quality. A family of heuristic algorithms is presented to solve this problem. Their performance is empirically compared leading to insights into the solution space.

The Internet of Things heralds a new generation of data-centric applications, where controllers connect to large numbers of heterogeneous sensing devices. We consider a model, where the control loop does not execute periodically. Instead, controllers are prompted by contextual cues to make one-off decisions, resulting in sporadic activations. Since the need for data arises only sporadically, sensors do not sample data continuously. Rather, they are normally off (e.g., to save energy), but are activated by the controller on demand, when data is needed. Collected data has validity intervals, after which it must be re-sampled, since the measured value may change. Once a decision is made based on the data, sensors are turned off again. We call this model sporadic decision-centric data scheduling with normally-off sensors. It gives rise to novel scheduling problems because of the way the timing of activation of different sensors affects load attributed to data sampling; the shorter the interval between activation of a given sensor and the time a corresponding decision is made, the lower the number of samples taken by that sensor to support the decision, and thus decision cost. The paper defines the aforementioned decision-centric data scheduling problem and derives the optimal scheduling policy, called EDEF-LVF, for this task model. Simulation results confirm the superiority of EDEF-LVF compared to several baselines.

In a medical environment such as Intensive Care Unit, there are many possible reasons to cause errors, and one important reason is the effect of human intellectual tasks. In this paper, we first provide five categories of generic intellectual tasks of humans, where tasks among each category may lead to potential medical errors. Then, we present an integrated modeling framework to model a medical Cyber-Physical-Human System (CPHSystem) and use UPPAAL as the foundation to integrate and verify the whole medical CPHSystem design models. When designing a medical CPHSystem, developers need to consider whether the system design can mitigate the errors caused by these tasks or not. With a verified and comprehensive model, we can design a more accurate and acceptable system. We use a cardiac arrest resuscitation guidance and navigation system (CAR-GNSystem) as the motivation example for such medical CPHSystem modeling. Experimental results show that the CPHSystem models help determine system design flaws and can mitigate the potential medical errors caused by the human intellectual tasks.

The sophistication of malicious adversaries is increasing every day and most defenses are often easily overcome by such attackers. Many existing defensive mechanisms often make differing assumptions about the underlying systems and use varied architectures to implement their solutions. This often leads to fragmentation among solutions and could even open up additional vulnerabilities in the system.

Multicore architecture brings a significant challenge in designing critical real-time systems because of timing variability caused by concurrent accesses to shared memory. We propose a memory bandwidth regulated system architecture and a novel analysis method to address this challenge. In the proposed architecture, each core's memory access rate is regulated in a globally coordinated manner. The architecture allows system designers to control the system to satisfy desired real-time performance. The proposed analysis method provides a way to calculate worst case response time of each real-time task independently from other activities on other cores; it only depends on the task under analysis, the assigned bandwidth, and the number of cores in the system. We believe this independence is critical to enable modular certification of critical real-time systems. We implement the proposed system model on the gem5 architecture simulator. We evaluate the proposed analysis method by comparing the computed runtime with the measured runtime on the modified simulator. We show that the analysis method provides reasonable upper-bounds based on the SPEC2006 benchmark suite.

Memory bandwidth in modern multi-core platforms is highly variable for many reasons and it is a big challenge in designing real-time systems as applications are increasingly becoming more memory intensive. In this work, we proposed, designed, and implemented an efficient memory bandwidth reservation system, that we call MemGuard. MemGuard separates memory bandwidth in two parts: guaranteed and best effort. It provides bandwidth reservation for the guaranteed bandwidth for temporal isolation, with efficient reclaiming to maximally utilize the reserved bandwidth. It further improves performance by exploiting the best effort bandwidth after satisfying each core's reserved bandwidth. MemGuard is evaluated with SPEC2006 benchmarks on a real hardware platform, and the results demonstrate that it is able to provide memory performance isolation with minimal impact on overall throughput.

The Simplex architecture ensures the safe use of an unverifiable complex/smart controller by using it in conjunction with a verified safety controller and verified supervisory controller (switching logic). This architecture enables the safe use of smart, high-performance, untrusted, and complex control algorithms to enable autonomy without requiring the smart controllers to be formally verified or certified. Simplex incorporates a supervisory controller that will take over control from the unverified complex/smart controller if it misbehaves and use a safety controller. The supervisory controller should (1) guarantee that the system never enters an unsafe state (safety), but should also (2) use the complex/smart controller as much as possible (minimize conservatism). The problem of precisely and correctly defining the switching logic of the supervisory controller has previously been considered either using a control-theoretic optimization approach or through an offline hybrid-systems reachability computation. In this work, we show that a combined online/offline approach that uses aspects of the two earlier methods, along with a real-time reachability computation, also maintains safety, but with significantly less conservatism, allowing the complex controller to be used more frequently. We demonstrate the advantages of this unified approach on a saturated inverted pendulum system, in which the verifiable region of attraction is over twice as large compared to the earlier approach. Additionally, to validate the claims that the real-time reachability approach may be implemented on embedded platforms, we have ported and conducted embedded hardware studies using both ARM processors and Atmel AVR microcontrollers. This is the first ever demonstration of a hybrid-systems reachability computation in real time on actual embedded platforms, which required addressing significant technical challenges.

In this paper, we introduce a novel mechanism that identifies abnormal system-wide behaviors using the predictable nature of real-time embedded applications. We introduce Memory Heat Map (MHM) to characterize the memory behavior of the operating system. Our machine learning algorithms automatically (a) summarize the information contained in the MHMs and then (b) detect deviations from the normal memory behavior patterns. These methods are implemented on top of a multicore processor architecture to aid in the process of monitoring and detection. The techniques are evaluated using multiple attack scenarios including kernel rootkits and shellcode. To the best of our knowledge, this is the first work that uses aggregated memory behavior for detecting system anomalies especially the concept of memory heat maps.

Multi-core platforms represent the answer of the industry to the increasing demand for computational capabilities. From a real-time perspective, however, the inherent sharing of resources, such as memory subsystem and I/O channels, creates inter-core timing interference among critical tasks and applications deployed on different cores. As a result, modular per-core certification cannot be performed, meaning that: (1) current industrial engineering processes cannot be reused, (2) software developed and certified for single-core chips cannot be deployed on multi-core platforms as is. In this work, we propose the Single Core Equivalence (SCE) technology: a framework of OS-level techniques designed for commercial (COTS) architectures that exports a set of equivalent single-core virtual machines from a multi-core platform. This allows per-core schedulability results to be calculated in isolation and to hold when multiple cores of the system run in parallel. Thus, SCE allows each core of a multi-core chip to be considered as a conventional single-core chip, ultimately enabling industry to reuse existing software, schedulability analysis methodologies and engineering processes.

This paper solves the challenge of offline response time analysis of independent periodic tasks with constrained deadlines early in the software development cycle, under generalized rate-monotonic scheduling. CPU budgets are allocated to different applications and each application is composed of multiple periodic tasks that must share the same budget. Physical application requirements impose specifications on task periods and deadlines from the very beginning, but unlike the common assumption in traditional response time analysis, task execution times are not known. This is because task execution times depend on the exact system implementation, which is not finalized until later in the development cycle. Questions facing designers become: will my task meet its deadline given lack of knowledge of other tasks' execution times? What is the smallest deadline that my task can meet? These questions are traditionally addressed by using a two level scheduler: CPU is partitioned and assigned to application, and task priorities are determined within the scope of an application, and when server becomes active it schedules the tasks locally. Such two level scheduling approach introduces priority inversion across applications. In our approach, different applications' tasks are globally scheduled and yet the CPU resource is still partitioned and assigned to applications as a CPU budget. We schedule all the tasks globally while enforcing application budgets. The proposed new form of response time analysis is called budgeted generalized rate-monotonic analysis to compute the maximum response time for each task given only application budgets and task periods, but without knowledge of task execution times. We formulate this schedulability problem as a mixed integer linear programming problem and demonstrate a solution that computes the exact worst-case response times. Evaluation shows that our solution outperforms, in terms of schedulability, both global utilization bounds and mechanisms that attain temporal modularity via resource partitioning.

There are growing demands to leverage network connectivity and interoperability of medical devices in order to improve patient safety and the effectiveness of medical services. However, if not properly designed, the integration of medical devices through networking could significantly increase the complexity of the system and make the system more vulnerable to potential errors, jeopardizing patient safety. The system must be designed and verified to guarantee the safety of patients and the effectiveness of medical services in the face of potential problems such as network failures. In this paper, we propose organ-centric hierarchical control architecture as a viable solution that reduces the complexity in system design and verification. In our approach, medical devices are grouped into clusters according to organ-specific human physiology. Each cluster captures common patterns arising out of medical device interactions and becomes a survivable semiautonomous unit during network failures. Further, safety verification and runtime enforcement can be modularized along organ-centric hierarchical control structure. We show the feasibility of the proposed approach under Simulink's model-based development framework. A simplified scenario for airway laser surgery is used as a case study.

The trend in the semiconductor industry toward multicore processors poses a significant challenge to many suppliers of safety-critical real-time embedded software. Having certified their systems for use on single-core processors, these companies may be forced to migrate their installed base of software onto multicore processors as single-core processors become harder to obtain. These companies naturally want to minimize the potentially high costs of recertifying their software for multicore processors. In support of this goal, we propose an approach to solving a fundamental problem in migrating legacy software applications to multicore systems, namely that of preventing conflicts among I/O transactions from applications residing on different cores. We formalize the problem as a partition scheduling problem that serializes I/O partitions. Although this problem is strongly NP-complete, we formulate it as a Constraint Programming (CP) problem. Since the CP approach scales poorly, we propose a heuristic algorithm that outperforms the CP approach in scalability.

The Simplex Architecture ensures the safe use of an unverifiable complex controller by using a verified safety controller and verified switching logic. This architecture enables the safe use of high-performance, untrusted, and complex control algorithms without requiring them to be formally verified. Simplex incorporates a supervisory controller and safety controller that will take over control if the unverified logic misbehaves. The supervisory controller should (1) guarantee the system never enters and unsafe state (safety), but (2) use the complex controller as much as possible (minimize conservatism). The problem of precisely and correctly defining this switching logic has previously been considered either using a control-theoretic optimization approach, or through an offline hybrid systems reach ability computation. In this work, we prove that a combined online/offline approach, which uses aspects of the two earlier methods along with a real-time reach ability computation, also maintains safety, but with significantly less conservatism. We demonstrate the advantages of this unified approach on a saturated inverted pendulum system, where the usable region of attraction is 227% larger than the earlier approach.

New features are often added incrementally to avionics systems to minimize the need for redesign and recertification. However, it then becomes necessary to check that the timing constraints of existing as well as new applications are met. We facilitate these checks by introducing a new data switch that bounds the latency of end-to-end communications across a network. This switch runs a clock-driven switching algorithm that is throughput-optimal with a bounded worst-case delay for all feasible traffic. We propose associated heuristics that determine whether the timing constraints of an integrated modular avionics (IMA) system network that uses this switch are met, even if new features have caused traffic to increase, and then search for alternative network configurations if necessary. Virtual integration is used to make a combined analysis of the worst-case delay in the network and the local buses of individual computing modules. This analysis considers the shared network topology, local hardware architectures, and specified IMA configurations. Our approach can be used by a system architect as an effective method for quickly determining which possible system architectures should be pursued to meet timing constraints, and it allows the cascading effects of changes to be tracked and managed. We demonstrate how these heuristics work through an example in which changes are made to an environmental monitoring facility within an avionics system that uses our switch.

Medical devices are increasingly capable of interacting with each other by leveraging network connectivity and interoperability, promising a great benefit for patient safety and effectiveness of medical services. However, ad-hoc integration of medical devices through networking can significantly increase the complexity of the system and make the system more vulnerable to potential errors and safety hazards. In this paper, we address this problem and introduce an organ-centric compositional development approach. In our approach, medical devices are composed into semi-autonomous clusters according to organ-specific physiology in a network-fail-safe manner. Each organ-centric cluster captures common device interaction patterns of sensing and control to support human physiology. The library of these formally verified organ-centric architectural patterns enables rapid and safe composition of supervisory controllers, which are specialized for specific medical scenarios. Using airway-laser surgery as a case study of practical importance, we demonstrate the feasibility of our approach under Simulink's model-driven development framework.

Medical Device Plug-and-Play (MDPnP) permits the mitigation of preventable medical errors. However, MDPnP results in a dynamic environment, which presents great challenges to traditional software architectures. This paper addresses these challenges by describing an abstract representation of dynamic clinical environment and a modular architecture is utilized to support safe system reconfiguration.

Integrated Modular Avionics (IMA) architecture has been widely adopted by the avionics industry due to its strong temporal and spatial isolation capability for safety-critical real-time systems. The fundamental challenge to integrating an existing set of single-core IMA partitions into a multi-core system is to ensure that the isolation of the partitions will be maintained without incurring huge redevelopment and recertification costs. To address this challenge, we developed an optimized partition scheduling algorithm which considers exclusive regions to achieve the synchronization between partitions across cores. We show that the problem of finding the optimal partition schedule is NP-complete and present a Constraint Programming formulation. In addition, we relax this problem to find the minimum number of cores needed to schedule a given set of partitions and propose an approximation algorithm which is guaranteed to find a feasible schedule of partitions if there exists a feasible schedule of exclusive regions.

Hierarchical scheduling of periodic resources has been increasingly applied to a wide variety of real-time systems due to its ability to accommodate various applications on a single system through strong temporal isolation. This leads to the question of how one can optimize over the resource parameters while satisfying the timing requirements of real-time applications. A great deal of research has been devoted to deriving the analytic model for the bounds on the design parameter of a single resource as well as its optimization. The optimization for multiple periodic resources, however, requires a holistic approach due to the conflicting requirements of the limited computational capacity of a system among resources. Thus, this paper addresses a holistic optimization of multiple periodic resources with regard to minimum system utilization. We extend the existing analysis of a single resource in order for the variable interferences among resources to be captured in the resource bound, and then solve the problem with Geometric Programming (GP). The experimental results show that the proposed method can find a solution very close to the one optimized via an exhaustive search and that it can explore more solutions than a known heuristic method.

The Physically-Asynchronous Logically-Synchronous (PALS) system is a recently proposed architectural pattern for cyber-physical systems. It guarantees a logically synchronous design abstraction for real-time distributed computations. In this work, we develop a new middleware, called PALSware, to support an efficient and robust implementation of the PALS system and its extensions. PALSware guarantees consistency in distributed applications by eliminating any asynchronous interactions resulting from distributed clocks and node failures. We present a layered design for this middle-ware that is both reusable in different system architectures and can be extended with architecture-specific solutions for fault management. We demonstrate the middleware for an academic control testbed and show the consistency in a fault injection framework designed for this middleware.

Security violations are becoming more common in real-time systems - an area that was considered to be invulnerable in the past - as evidenced by the recent W32.Stuxnet and Duqu worms. A failure to protect such systems from malicious entities could result in significant harm to both humans as well as the environment. The increasing use of multicore architectures in such systems exacerbates the problem since shared resources on these processors increase the risk of being compromised. In this paper, we present the SecureCore framework that, coupled with novel monitoring techniques, is able to improve the security of realtime embedded systems. We aim to detect malicious activities by analyzing and observing the inherent properties of the real-time system using statistical analyses of their execution profiles. With careful analysis based on these profiles, we are able to detect malicious code execution as soon as it happens and also ensure that the physical system remains safe.

Memory bandwidth in modern multi-core platforms is highly variable for many reasons and is a big challenge in designing real-time systems as applications are increasingly becoming more memory intensive. In this work, we proposed, designed, and implemented an efficient memory bandwidth reservation system, that we call MemGuard. MemGuard distinguishes memory bandwidth as two parts: guaranteed and best effort. It provides bandwidth reservation for the guaranteed bandwidth for temporal isolation, with efficient reclaiming to maximally utilize the reserved bandwidth. It further improves performance by exploiting the best effort bandwidth after satisfying each core's reserved bandwidth. MemGuard is evaluated with SPEC2006 benchmarks on a real hardware platform, and the results demonstrate that it is able to provide memory performance isolation with minimal impact on overall throughput.

Patients in the intensive care unit (ICU) are exposed to multiple potentially critical complications such as delirium, acute lung injury, acute renal failure, and sepsis. Those who suffered critical complications and survived often require costly long term care, e.g., post-hospital treatment attributed to delirium alone adds $143-152 billion per year to U.S. healthcare costs. Delirium in hospitalized patients could be reduced by 30-40% if first rate care is widely available. However, “mass production” of low cost expert physicians is impossible. In 2010, ICUs already comprised 20% of hospitals' budgets in U.S. As the population ages, ICU usages will intensify. The magnitude of challenges faced in the ICU is enormous, and complicated by the fact that critical complications in ICU mentioned above are NOT single diseases. They are syndromes with a very wide range of precipitating factors, including aging, surgery, trauma, anesthesia, compromised immunity, systemic inflammation, infection or drug side effects. For example, with disparate mechanisms of onset, patients with sepsis have highly variable presentations: one may have a fever and high white blood cell count while another has a low body temperature and low white blood cell count. This is also a complex big data challenge. A critically ill patient can generate up to a million data points per hour from monitoring devices that need to be analyzed together with medical records, genetic profile and physicians' insight. To address these challenges, it is important to create an accurate and robust model of the pathophysiological organ interactions and the effect and side effects of treatments, using physician supervised machine learning that integrates the conventional clinical data, biomarkers and genetic profile. Such a quantitative model will provide key description of characteristic patterns in critical complications, leading to early warning and timely preventive intervention. The success will open a new scientific frontier, cyber - medical systems: ushering synchronized advancement of medicine, nano-biosensors, genetics, machine learning and safety critical system integration architecture and development process. This will improve almost all aspects of medicine, creating a new industry segment, and greatly reduce costs of health care.

Real-time embedded systems are increasingly being built using commercial-off-the-shelf (COTS) components such as mass-produced peripherals and buses to reduce costs, time-to-market, and increase performance. Unfortunately, COTS-interconnect systems do not usually guarantee timeliness, and might experience severe timing degradation in the presence of high-bandwidth I/O peripherals. Moreover, peripherals do not implement any internal priority-based scheduling mechanism, hence, sharing a device can result in data of high priority tasks being delayed by data of low priority tasks. To address these problems, we designed a real-time I/O management system comprised of 1) real-time bridges with I/O virtualization capabilities, and 2) a peripheral scheduler. The proposed framework is used to transparently put the I/O subsystem of a COTS-based embedded system under the discipline of real-time scheduling, minimizing the timing unpredictability due to the peripherals sharing the bus. We also discuss computing the maximum delay due to buffered I/O data transactions as well as determining the buffer size needed to avoid data loss. Finally, we demonstrate experimentally that our prototype real-time I/O management system successfully exports multiple virtual devices for a single physical device and prioritizes I/O traffic, guaranteeing its timeliness.

The assurance of reliability becomes increasingly challenging as the complexity of networked control systems (NCS) rapidly increases. Simplex architecture was designed to tolerate control software design and implementation. This architecture consists of a high assurance controller (HAC) and a high performance controller (HPC). The HAC uses the linear state feedback control to create a large maximum stability region (MSR). The HPC aims at achieving a better control performance and may use any design. However, the plant's states under HPC must stay within the MSR, or the control is switched to HAC.

Quality of service (QoS) and, in particular, reliability and a bounded low latency are essential attributes of safety-critical wireless systems for medical applications. However, wireless links are typically prone to bursts of errors, with characteristics which vary over time.We propose a wireless system suitable for real-time remote patient monitoring in which the necessary reliability and guaranteed latency are both achieved by an efficient error control scheme. We have paired an example remote electrocardiography application to this wireless system. We also developed a tool chain that uses a formal description of the proposed wireless medical system architecture in the architecture analysis and design language to assess various combinations of system parameters: we can determine the QoS in terms of packet-delivery ratio and the service latency, and also the size of jitter buffer required for seamless ECG monitoring. A realistic assessment, based on data from the MIT-BIT arrhythmia database, shows that the proposed wireless system can achieve an appropriate level of QoS for real-time ECG monitoring if link-level error control is correctly implemented. Additionally, we present guidelines for the design of energy-efficient link-level error control, derived from energy data, obtained from simulations.

We propose a model-based description and analysis framework for the design of wireless system architectures. Its aim is to address the shortcomings of existing approaches to system verification and the tracking of anomalies in safety-critical wireless systems. We use Architecture Analysis and Description Language (AADL) to describe an analysis-oriented architecture model with highly modular components. We also develop the cooperative tool chains required to analyze the performance of a wireless system by simulation. We show how this framework can support a detailed and largely automated analysis of a complicated, networked wireless system using examples from wireless healthcare and video broadcasting.

Shared resource access interference, particularly memory and system bus, is a big challenge in designing predictable real-time systems because its worst case behavior can significantly differ. In this paper, we propose a software based memory throttling mechanism to explicitly control the memory interference. We developed analytic solutions to compute proper throttling parameters that satisfy schedulability of critical tasks while minimize performance impact caused by throttling. We implemented the mechanism in Linux kernel and evaluated isolation guarantee and overall performance impact using a set of synthetic and real applications.

This demonstration presents our NASS (Network Aware Supervisory System) framework prototype for medical device integration systems. The NASS framework interconnects medical devices over wireless for convenience, seamlessness and sanitation, and provides safety-guaranteed supervision. Our prototype was developed in Sun Java Real-time Environment. Real-time Java provides well-formed convenience of dynamically loading and unloading medical application logic and safety rules on the fly in real-time environments. To tackle the complexity of using real-time Java in the safety-critical system, we also applied HW/SW codesign method. Real-time Java Environment + Linux operating system may not be robust enough for medical devices to fully rely on. In our prototype, the supervisor software in Java performs all logical decisions including contingency plan generation derived from the safety rules. Once logic is decided, the decisions and plans for the devices are delivered to the hardware implemented in FPGA at each device to physically drive medical equipments. Since the execution of decisions and plans are delegated to the hardware, any failure in software does not harm the integrated safety. Our demonstration shows how safety is managed in different kinds of failures from wireless network failures to device software failures.

With the advance of hardware technology, more features are incrementally added to already existing networked systems. Avionics has a stronger tendency to use preexisting applications due to its complexity and scale. As resource sharing becomes intense among the network and the computing modules, it has become a difficult task for the system designer to make confident architectural decisions even for incremental changes. Providing a tailored environment to model and analyze incremental changes requires a combination of software tools and hardware support. We have built a virtual integration tool called ASIIST which can provide a worst-case end-to-end latency of data that is sent through a network and the internal bus architecture of the end-systems. Also, we have devised a new real-time switching algorithm which guarantees the worst-case network delay of preexisting network traffic under feasible conditions. With the real-time switch support, ASIIST can provide an early modularized analysis of the end-to-end latency to make architectural design choices and incremental changes easier for the user.

Open Analytic Runtime (OAR) Models embed analysis algorithms into runtime architectural models, thus integrating the model and its analytic interpretations. Such an integration is critical for Cyber-Physical Systems (CPS) when model parts are independently developed by different teams as it is the case in multi-tier industries, e.g. avionics and automotive. Analysis algorithms play a central role augmenting the designer's capacity to automatically verify properties of interest in systems at the scale and complexity required by these industries. Unfortunately, the verification results are valid only if the assumptions of the different analysis algorithms (analytic assumptions) are consistent with each other. This paper presents our work on the automatic verification of one important class of analytic assumptions in OAR models: resource allocation assumptions. These assumptions are modeled as Resource Allocation (RA) contracts. RA contract constructs include not only the typical assumes and guarantees but also runtime facts and implications. Finally, we automatically determine the correct sequence of execution of the analysis algorithms based on the contract input/output dependencies described in our models. Together these characteristics enable the automatic assumption verification that preserves the scalability of analytic models. We illustrate our approach using an example model with analysis algorithms for security, schedulability, and energy efficiency.

New features are often added incrementally to avionics systems. This avoids redesign and recertification but still requires verifying the timing constraints of both new and existing applications. We introduce a new switch that facilitates this verification by bounding the latency of end-to-end communication across a network. Our clock-driven real-time switching algorithm is throughput-optimal with a bounded worst-case delay for all feasible traffic. Associated heuristics can verify whether the timing constraints of an avionics network are met, after new features have caused traffic to increase, and then search for alternative network configurations if necessary. We show how these heuristics cope with changes to an example environmental monitoring architecture within an avionics system that incorporates our switch. Our approach to analysis can be used to determine, quickly but rigorously, which system architecture meet timing constraints, and it allows the system architect to manage the cascading effects of component changes in a comprehensive manner.

The unpredictable worst-case timing behavior of multicore architectures has been the biggest stumbling block for a widespread use of multicores in hard real-time systems. A great deal of research effort has been devoted to address the issue. Among others, the development of a new multicore architecture has emerged as an attractive solution because it can eliminate the unpredictable interference sources in the first place. This opens a new possibility of system-level optimizations with multicore based hard real-time systems. To address this issue, we propose a new perspective of WCET model called tunable WCET, in which the WCETs of tasks are elastically adjusted according to the optimal shared resource allocation and arbitration methods. For this, we propose novel WCET-aware harmonic round-robin bus scheduling and two-level cache partitioning method. We present a mixed integer linear programming formulation as the solution to the optimization of tunable WCETs. Our experimental results show that the proposed methods can significantly lower overall system utilizations.

In telecardiology, electrocardiogram (ECG) signals from a patient are acquired by sensors and transmitted in real time to medical personnel across a wireless network. The use of IEEE 802.11 wireless LANs (WLANs), which are already deployed in many hospitals, can provide ubiquitous connectivity and thus allow cardiology patients greater mobility. However, engineering issues, including the error-prone nature of wireless channels and the unpredictable delay and jitter due to the nondeterministic nature of access to the wireless medium, need to be addressed before telecardiology can be safely realized. We propose a medical-grade WLAN architecture for remote ECG monitoring, which employs the point-coordination function (PCF) for medium access control and Reed-Solomon coding for error control. Realistic simulations with uncompressed two-lead ECG data from the MIT-BIH arrhythmia database demonstrate reliable wireless ECG monitoring; the reliability of ECG transmission exceeds 99.99% with the initial buffering delay of only 2.4 s.

Cyber-physical systems (CPS) are physical and engineered systems whose operations are monitored, coordinated, controlled and integrated by a computing and communication core. Just as the internet transformed how humans interact with one another, cyber-physical systems will transform how we interact with the physical world around us. Many grand challenges await in the economically vital domains of transportation, health-care, manufacturing, agriculture, energy, defense, aerospace and buildings. The design, construction and verification of cyber-physical systems pose a multitude of technical challenges that must be addressed by a cross-disciplinary community of researchers and educators.

Most dynamic voltage and frequency scaling (DVS) techniques adjust only CPU parameters, however, recent embedded systems provide multiple adjustable clocks which can be independently tuned. When considering multiple components, energy optimal frequencies depend on task set characteristics such as the number of CPU and memory access cycles. In this work, we propose a realistic energy model considering multiple components with individually adjustable frequencies such as CPU, system bus and memory, and related task set characteristics. The model is validated on a real platform and shows less than 2% relative error compared to measured values. Based on the proposed energy model, we present an optimal static frequency assignment scheme for multiple DVS components to schedule a set of periodic realtime tasks. We simulate the energy gain of the proposed scheme compared to other DVS schemes for various task and system configurations, showing up to a 20% energy reduction.

The authors propose an adaptive frequency hopping (AFH) algorithm, entitled robust adaptive frequency hopping (RAFH), for providing increased reliability of a wireless medical telemetry system (WMTS) under coexistence environment with non-medical devices. The conventional AFH scheme classifies channels into ‘good’ or ‘bad’ according to the threshold-based on–off decision by packet error rate (PER) measurement, and only uses good channels with a uniform hop probability. Unlike the conventional AFH scheme, RAFH is a novel technique, which solves a constrained entropy maximisation problem and assigns every channel a different hop probability as a decreasing function of the measured PER. The key novelty of RAFH over existing AFH schemes is that it reflects the relative channel condition by assigning non-uniform hop probabilities. By adopting constrained entropy maximisation, RAFH not only improves the average PER, but also reduces the PER fluctuation over time under a dynamic interference environment, both of which increase the reliability of WMTS. Through extensive simulation, we show that RAFH outperforms basic frequency hopping (FH) and the conventional AFH with respect to the PER under various scenarios of dynamic interference.

Providing high-quality broadcast services for soft real-time applications over wireless networks such as CDMA2000, which have high bit error rates, requires the control of errors that occur during data transmission. Reed-Solomon (RS) forward error correction (FEC) in the medium access control (MAC) layer performs this role in 3G broadcast services. We propose new analytic models for predicting the performance of RS coding and its execution time, which take into account the memory property of a fading channel, different channel conditions, and a variable level of block interleaving. We identify RS decoding as a significant cause of variability in execution time, taking the form of jitter, which depends on the channel conditions. We analyze the size of buffer required to absorb the jitter under different channel conditions. We then formulate a trade-off between the performance of RS coding and the delay that it causes in transmitting a fixed amount of data with different levels of block interleaving. Finally, we show how to balance the quality with which content is presented against an acceptable buffering delay, which is very important to soft real-time applications, by using an adequate level of block interleaving. This study offers a guide for the provision of efficient broadcast services in real time with stochastically guaranteed quality.

System-on-Chip (SoC) is a promising paradigm to implement safety-critical embedded systems, but it poses significant challenges from a design and verification point of view. In particular, in a mixed-criticality system, low criticality applications must be prevented from interfering with high criticality ones. In this paper, we introduce a new design methodology for SoC that provides strong isolation guarantees to applications with different criticalities. A set of certificates describing the assumed application behavior is extracted from a functional Architectural Analysis and Design Language (AADL) specification. Our tools then automatically generate hardware wrappers that enforce at run-time the behavior described by the certificates. In particular, we employ run-time monitoring to formally check all data communication in the system, and we enforce timing reservations for both computation and communication resources. Verification is greatly simplified because certificates are much simpler than the components used to implement low-criticality applications. The effectiveness of our methodology is proven on a case study consisting of a medical pacemaker.

In hard real-time systems such as avionics, computer board level designs are typically customized to meet specific reliability and real time requirements. This paper focuses on computer-aided application-specific design of I/O architecture using PCI as an example. We have built a tool (ASIIST) that will enable engineers to explore design spaces at the I/O bus architecture level, performing analysis that incorporates bus protocols, to provide guarantees of real-time properties.

Embedded systems in safety-critical environments demand safety guarantees while providing many useful services that are too complex to formally verify or fully test. Existing application-level fault-tolerance methods, even if formally verified, leave the system vulnerable to errors in the real-time operating system (RTOS), middleware, and microprocessor. We introduce the system-level simplex architecture, which uses hardware/software co-design to provide fail-operational guarantees for both logical application-level faults, as well as faults in previously dependent layers including the RTOS and microprocessor. We also provide an end-to-end design process for the system-level simplex architecture where the AADL architecture description is automatically constructed and checked and the VHDL hardware code is generated. To show the efficacy of System-Level Simplex design, we apply the approach to both a classic inverted pendulum and a cardiac pacemaker. We perform fault-injection tests on the inverted pendulum design which demonstrate robustness in spite of software controller and operating system faults. For the pacemaker, we contrast the provided safety guarantees with those of a previous-generation pacemaker.

Pattern solutions for software and architectures have significantly reduced design, verification, and validation times by mapping challenging problems into a solved generic problem. In the paper, we present an architecture pattern for ensuring synchronous computation semantics using the PALS protocol. We develop a modeling framework in AADL to automatically transform a synchronous design of a real-time distributed system into an asynchronous design satisfying the PALS protocol. We present a detailed example of how the PALS transformation works for a dual-redundant system. From the example, we also describe the general transformation in terms of intuitively defined AADL semantics. Furthermore, we develop a static analysis checker to find necessary conditions that must be satisfied in order for the PALS transformation to work correctly. The transformations and static checks that we have described are implemented in OSATE using the generated EMF metamodel API for model manipulation.

Real-time embedded systems are increasingly being built using commercial-off-the-shelf (COTS) components such as mass-produced peripherals and buses to reduce costs, time-to-market, and increase performance. Unfortunately, COTS interconnect systems do not usually guarantee timeliness, and might experience severe timing degradation in the presence of high-bandwidth I/O peripherals. To address this problem, we designed a real-time I/O management system comprised of 1) real-time bridges, and 2) a reservation controller. The proposed framework is used to transparently put the I/O subsystem of a COTS-based embedded system under the discipline of real-time scheduling. We also discuss computing a delay bound for I/O data transactions and determining worst-case buffer size. Finally, we demonstrate experimentally that our prototype real-time I/O management system successfully prioritizes I/O traffic and guarantees its timeliness.

In complex hard real-time systems with tight constraints on system resources, small changes in one component of a system can cause a cascade of adverse effects on other parts of the system. We address the inherent complexity of making architectural decisions by raising the level of abstraction at which the analysis is performed. Our analysis approach gives the system architect a rigorous method for quickly determining which system architectures should be pursued, and it allows the architect to track and manage the cascading effects of subsystem/component changes in a comprehensive, quantitative manner. The end product is a virtual architecture analysis that systematically incorporates the inherent coupling among interacting system components that share limited system resources.

Fault tolerance is an important aspect in real-time computing. In real-time control systems, tasks could be faulty due to various reasons. Faulty tasks may compromise the performance and safety of the whole system and even cause disastrous consequences. In this paper, we describe ORTEGA (On-demand Real-TimE GuArd), a new software fault tolerance architecture for real-time control systems. ORTEGA has high fault coverage and reliability. Compared with existing real-time fault tolerance architectures, such as Simplex, ORTEGA allows more efficient resource utilizations and enhances flexibility. These advantages are achieved through the on-demand detection and recovery of faulty tasks. ORTEGA is applicable to most industrial control applications where both efficient resource usage and high fault coverage are desired.

The convergence of computers and the physical world is the theme for next generation networking research. This trend calls for real-time network infrastructure, which requires a high-speed real-time WAN to serve as its backbone. However, commercially available high-speed WAN switches (routers) are designed for best-effort Internet traffic. A real-time switch design for the aforementioned networks is missing. We propose a real-time switch design using a crossbar switching fabric. The proposed switch can be implemented by making minimal modification, or even simplification, to the widely implemented iSLIP crossbar switch scheduler. Our real-time switch serves periodic and aperiodic traffic with real-time virtual machine tasks, which simplifies analysis, provides isolation, and facilitates future hierarchical scheduling and flow aggregation. Taking advantage of the fact that most industrial real-time network flows rarely change, our switch is better adapted to providing high bandwidths and low latencies.

Cache partitioning techniques have been proposed in the past as a solution for the cache interference problem. Due to qualitative differences with general purpose platforms, real-time embedded systems need to minimize task real-time utilization (function of execution time and period) instead of only minimizing the number of cache misses. In this work, the partitioning problem is presented as an optimization problem whose solution sets the size of each cache partition and assigns tasks to partitions such that system worst-case utilization is minimized thus increasing real-time schedulability. Since the problem is NP-Hard, a genetic algorithm is presented to find a near optimal solution. A case study and experiments show that in a typical real-time embedded system, the proposed algorithm is able to reduce the worst-case utilization by 15% (on average) if compared to the case when the system uses a shared cache or a proportional cache partitioned environment.

Integrating COTS components in critical real-time systems is challenging. In particular, we show that the interference between cache activity and I/O traffic generated by COTS peripherals can unpredictably slow down a real-time task by up to 44%. To solve this issue, we propose a framework comprised of three main components: 1) a COTS-compatible device, the peripheral gate, that controls peripheral access to the system; 2) an analytical technique that computes safe bounds on the I/O-induced task delay; 3) a coscheduling algorithm that maximizes the amount of allowed peripheral traffic while guaranteeing all real-time task constraints. We implemented the complete framework on a COTS-based system using PCI peripherals, and we performed extensive experiments to show its feasibility.

The problem of identifying suitable conditions for the schedulability of (nonpreemptive) recurring tasks with deadlines is of great importance to real-time systems. In this paper, motivated by the problem of scheduling radar dwells, we show that scheduling problems of this nature show a sharp threshold behavior with respect to system utilization. Sharp thresholds are associated with phase transitions: When the utilization of a task set is less than a critical value, it can be scheduled almost surely and, when the utilization increases beyond the critical level, almost no task set can be scheduled. We make connections to work on random graphs to prove the sharp threshold behavior in the scheduling problem of interest. Using extensive experiments, we determine the threshold for the radar dwell scheduling problem and use it for performance optimization. The connections to random graph theory suggest new ways for understanding the average-case behavior of scheduling policies. These results emphasize the ease with which performance can be controlled in a variety of real-time systems.

Fault tolerance is an important aspect in real-time computing. In real-time control systems, tasks could be faulty due to various reasons. Faulty tasks may compromise the performance and safety of the whole system and even cause disastrous consequences. In this paper, we describe On-demand real-time guard (ORTEGA), a new software fault tolerance architecture for real-time control systems. ORTEGA has high fault coverage and reliability. Compared with existing real-time fault tolerance architectures, such as Simplex, ORTEGA allows more efficient resource utilizations and enhances flexibility. These advantages are achieved through the on-demand detection and recovery of faulty tasks. ORTEGA is applicable to most industrial control applications where both efficient resource usage and high fault coverage are desired.

We present the Lightning Protocol, a hard real-time, fast, and lightweight protocol to elect the sensor closest to an impulsive sound source. This protocol can serve proximity-based localization or leader election for sensor collaboration. It utilizes the fact that electromagnetic waves propagate much faster than acoustic waves to efficiently reduce the number of contending sensors in the election. With simple RF bursts, most basic comparison operations, no need of clock synchronization, and a memory footprint as small as 5,330 bytes of ROM and 187 bytes of RAM, the protocol incurs O(1) transmissions, irrespective of the sensor density, and guarantees hard real-time (O(1)) localization time cost. Experiment results using UC Berkeley Motes in a common office environment demonstrate that the time delay for the Lightning Protocol is on the order of milliseconds. The simplicity of the protocol reduces memory cost, computation complexity, and programming difficulty, making it desirable for low-end wireless sensors.

Web applications have been increasingly deployed on the Internet. How to effectively allocate system resources to meet the Service Level Objectives (SLOs) is a challenging problem for Web application providers. In this article, we propose a scheme for automated performance control of Web applications via dynamic resource allocations. The scheme uses a queueing model predictor and an online adaptive feedback loop that enforces admission control of the incoming requests to ensure the desired response time target is met. The proposed Queueing-Model-Based Adaptive Control approach combines both the modeling power of queueing theory and the self-tuning power of adaptive control. Therefore, it can handle both modeling inaccuracies and load disturbances in a better way. To evaluate the proposed approach, we built a multi-tiered Web application testbed with open-source components widely adopted in industry. Experimental studies conducted on the testbed demonstrated the effectiveness of the proposed scheme.

Cyber-physical systems are networked, component-based, real-time systems that control and monitor the physical world. We need software architectures that limit fault-propagation across unreliable components. This paper introduces our simplex reference model which is distinguished by: a plant being controlled in an external context, a machine performing the control, a domain model that estimates the plant state, and the safety requirements that must be met. The simplex reference model assists with constructing CPS architectures which limit fault-propagation. We present a representative case study to highlight the ideas behind the model and our particular decomposition.

The convergence of computer and physical world calls for next generation Wide Area Network (WAN) infrastructures for hard real-time and embedded applications. Such networks need virtual topologies to achieve scalability, configurability, and flexibility. Virtual topologies are made of virtual links, for which, the state-of-the-art building tool is Guaranteed Rate server based aggregates (GR- aggregates). However, common-practice weight assignment scheme couples GR-aggregate End-to-End (E2E) delay bound with aggregate's data throughput inverse proportionally. This is undesirable for many hard real-time embedded sensing/actuating applications, whose traffic has small data throughput but requires short E2E delay. We propose Guaranteed Delay server based aggregates (GD-aggregates), which allow assigning weights according to priorities instead of data throughput. This decouples E2E delay guarantee from data throughput, hence meets the needs of hard realtime embedded applications. In addition, GD-aggregates can be analyzed with simple closed form formulae, and can be easily planned with optimization tools.

Wireless LAN for industrial control (IC-WLAN) provides many benefits, such as mobility, low deployment cost, and ease of reconfiguration. However, the top concern is robustness of wireless communications. Wireless control loops must be maintained under persistent adverse channel conditions, such as noise, large-scale path loss, fading, and many electromagnetic interference sources in industrial environments. The conventional IEEE 802.11 WLANs, originally designed for high bandwidth instead of high robustness, are therefore inappropriate for IC-WLAN. A solution lies in the direct sequence spread spectrum (DSSS) technology: by deploying the largest possible processing gain (slowest bit rate) that fully exploits the low data rate feature of industrial control, much higher robustness can be achieved. We hereby propose using DSSS-CDMA to build IC-WLAN. We carry out fine-grained physical layer simulations and Monte Carlo comparisons. The results show that DSSS-CDMA IC-WLAN provides much higher robustness than IEEE 802.11/802.15.4 WLAN, so that reliable wireless industrial control loops become feasible. We also show that deploying larger processing gain is preferable, to deploying more intensive convolutional coding. The DSSS-CDMA IC-WLAN scheme also opens up a new problem space for interdisciplinary study, involving real-time scheduling, resource management, communication, networking, and control

Embedded control systems consist of multiple components with different criticality levels interacting with each other. For example, in a passenger jet, the navigation system interacts with the passenger entertainment system in providing passengers the distance-to-destination information. It is imperative that failures in the non-critical subsystem should not compromise critical functionality. This architectural principle for robustness can, however, be easily compromised by implementation-level errors. We describe Safe- Flow, which statically analyzes core components in the system to ensure that they use non-core values communicated through shared memory only if they are run-time monitored for safety or recoverability. Using simple, local annotations and semantic restrictions on shared memory usage in the core component, SafeFlow precisely identifies accesses to unmonitored non-core values. With a few false positives, it identifies erroneous dependencies of critical data on noncore values that can arise due to programming errors, inadvertent accesses, or wrong assumptions regarding the absence of difficult-to-detect implementation errors such as data races and synchronization. We demonstrate the utility of SafeFlow by applying it to discover critical value flow dependencies in three prototype systems.

Due to the complexity and requirements of modern realtime systems, multiple teams must often work concurrently and independently to develop the various components of the system. Since a team typically only knows the dependency relations between the components they wrote and those they directly use, keeping track of system-wide dependency relations is not possible for any individual team. To further complicate matters, dependency relations often change as software components are refined or their interactions modified. Because the robustness of any real-time system hinges on the availability of essential services in spite of faults and failures in useful but non-essential components, keeping track of the constantly evolving dependency relations between the system's components is crucial. If a system's designers cannot ensure that critical services only USE but do not DEPEND ON less critical components, a seemingly minor fault can propagate along complex and unforeseen dependency chains and bring down the entire system. Therefore, automatically tracking and analyzing system-wide dependency relations given only local dependency information is vital for the development of robust real time systems. This paper presents DMF (dependency management framework), a prototype toolkit for dependency management in designing robust real-time systems. We demonstrate the usability and scalability of DMF with a case study of ION CubeSat, the University of Illinois at Urbana-Champaign 's first student-developed satellite.

How to effectively allocate system resources to meet service level objectives (SLOs) is a challenging problem for Web services providers. In this paper, we propose a scheme for autonomous performance control of Web applications. It uses a queueing model predictor and an online adaptive feedback loop that enforces admission control of the incoming requests to ensure the desired response time target is met. The proposed queueing-model-based adaptive control approach combines both the modeling power of queueing theory and self-tuning power of adaptive control. Therefore, it can handle both modeling inaccuracies and load disturbances in a better way. To evaluate the proposed approach, we built a multi-tiered Web application testbed with open-source components widely used in industry. Experimental studies conducted on the testbed demonstrated the effectiveness of the proposed approach

Patterns are a valuable method for communicating software engineering expertise about proven solutions for common problems. This paper evaluates the use of domain-independent patterns in a case study of Etherware, a middleware for networked control with a real-time, safety-critical applications model. The case study illustrates the positive and negative impact that four existing patterns have on availability, reliability, and robustness for real-time, safety-critical systems. In particular, we observe Etherware's specialized usage of the filter pattern, confirm this usage among other middleware technologies, and subsequently present the adaptive control filter, a design pattern for real-time, safety-critical middleware which can mitigate timing dependencies in networked control

Advances in networking, sensors, and embedded devices have made it feasible to monitor and provide medical and other assistance to people in their homes. Aging populations will benefit from reduced costs and improved healthcare through assisted living based on these technologies. However, these systems challenge current state-of-the-art techniques for usability, reliability, and security. This is a particular challenge for open and extensible systems that combine software and hardware from many vendors and provide information to diverse clinicians. In this paper we present the I-Living architecture for assisted living that allows independent parties work together in a dependable, secure, and low-cost fashion with predictable properties. Our approach is based on an Assisted Living Service Provider (ALSP) who provides a server that collects and maintains encrypted assisted persons (APs)' records. Our ALSP can be a third party distinct from APs, communication providers, and clinicians; or it can be part of an ISP, hospital or similar enterprise. We have explored the architecture by developing a collection of applications and implementing them in a prototype system. Our system shows the feasibility and opportunity of an open approach to assisted living systems.

This paper proposes novel techniques for scheduling radar dwells in phased array radar systems. In order to handle complex physical characteristics such as dwell interleaving, transmitting duty cycle constraint, and energy constraint, we propose a notion of schedulability envelope. The schedulability envelope designed offline hides the details of complex radar dwell scheduling and provides a simple measure for the schedulability check. Using the schedulability envelope, the proposed technique can efficiently perform the admission control for dynamic target tracking tasks. The simulation results show that the proposed approach can significantly improve the system utilization by taking advantage of dwell interleaving while guaranteeing the schedulability and physical constraints.

In this paper, we consider the problem of designing optimal asynchronous wake-up schedules to facilitate distributed power management and neighbor discovery in multihop wireless networks. We first formulate it as a block design problem and derive the fundamental trade-offs between wake-up latency and the average duty cycle of a node. After the theoretical foundation is laid, we then devise a neighbor discovery and schedule bookkeeping protocol that can operate on the optimal wake-up schedule derived. To demonstrate the usefulness of asynchronous wake-up, we investigate the efficiency of neighbor discovery and the application of on-demand power management, which overlays a desirable communication schedule over the wake-up schedule mandated by the asynchronous wake-up mechanism. Simulation studies demonstrate that the proposed asynchronous wake-up protocol has short discovery time which scales with the density of the network; it can accommodate various traffic characteristics and loads to achieve an energy savings that can be as high as 70 percent, while the packet delivery ratio is comparable to that without power management

How to allocate computing and communication resources in a way that maximizes the effectiveness of control and signal processing, has been an important area of research. The characteristic of a multi-hop Real-Time Wireless Sensor Network raises new challenges. First, the constraints are more complicated and a new solution method is needed. Second, a distributed solution is needed to achieve scalability. This article presents solutions to both of the new challenges. The first solution to the optimal rate allocation is a centralized solution that can handle the more general form of constraints as compared with prior research. The second solution is a distributed version for large sensor networks using a pricing scheme. It is capable of incremental adjustment when utility functions change. This article also presents a new sensor device/network backbone architecture---Real-time Independent CHannels (RICH), which can easily realize multi-hop real-time wireless sensor networking.

It has long been recognized that energy conservation usually comes at the cost of degraded performance such as longer delay and lower throughput in stand-alone systems and communication networks. However, there have been very few research efforts in quantifying such trade-offs. In this paper, we develop analytical models to characterize the relationships among energy, delay and throughput for different power management policies in wireless communication. Based on the decision when to put nodes to low-power states, we divide power management policies into two categories, i.e., 1) time-out driven and 2) polling-based. M/G/1/K queues with multiple vacations and an attention span are used to model time-out driven policies while transient analysis is applied to derive the state transition probability in polling-based systems. We find that For time-out driven power management policies, the "optimal" policy exhibits a threshold structure, i.e., when the traffic load is below certain threshold, a node should switch to the low-power state whenever possible and always remain active otherwise. From our analysis, contrary to general beliefs, polling-based policies such as the IEEE 802.11 PSM are not energy efficient for light traffic load.

Traditional control systems consist of sensors, controllers, and actuators operating with tight periodic dependencies, and communicating over dedicated real-time channels such as CAN or FDDI. However, best effort networks such as 802.11 are being increasingly used in such systems. The unpredictable delays and losses in such networks violate the periodicity assumptions of digital control design, and the consequent fail-safe actions incur significant performance penalties. In this paper, we propose a co-design based approach to address the periodicity requirements of digital control design, and improve robustness by extending deadlines through graceful degradation to the fail-safe action. In particular, we analytically demonstrate significant deadline extensions in the control loop of a traffic control testbed based on our approach. Such deadline extensions also facilitate fault tolerance techniques such as component restarts, and system management mechanisms such as online component upgrades. We validate the results by experiments in the testbed.

The rapid advancement and deployment of Web applications call for a precise yet simple model for capacity planning and analysis purposes. The most widely deployed Web application architecture is the 3-tiered system, which is composed of a front-end Web server, an application server and a backend database server. In this paper, we present an analytical model of the 3-tiered Web application architecture. We show by using queueing network theory, we can model the 3-tiered Web application architecture accurately. A test-bed is built to measure model parameters based on industry standard server components and TPC-W benchmark. Validation results show that the proposed model predicts performance measures such as response time and throughput accurately.

In this paper, we investigate the problem of providing efficient communication primitives across domains of wireless sensor network (WSN) applications. We argue both qualitatively and quantitatively that group communication among sensors of geographic proximity is one of the basic building blocks of many WSN applications. Furthermore, group communication awareness needs to be embedded and implemented at the MAC layer due to the broadcast nature of wireless medium. We devise a MAC protocol, called LGC-MAC to enable efficient single-hop one-to-many and many-to-one communication. We present case studies of two example applications, acoustic target tracking and propagation of information with feedback using LGC-MAC and demonstrate that LGC-MAC can improve the response time, alleviate channel contention and provide better fault tolerance to packet collisions and wireless errors.

This paper describes a fast recovery mechanism that meets the requirements of embedded real-time systems. In general purpose computing, restart is an established technology for achieving high availability. Restart has also been used in soft real-time systems where the temporary interruption of service is undesirable but acceptable. However, it has not been widely used in small embedded real-time systems with hard deadlines, mainly because the traditional approaches do not meet their requirements of low memory and processor overhead, and fast response times with little variations. We have developed process resurrection, a novel restart mechanism for recovering from crash failures to meet these requirements. The experiments on an inverted pendulum control system shows that it can recover the control process in time after a crash (eg. segmentation fault). Another experiment conducted on an MP3 audio player shows that this technique is also applicable to some multimedia applications.

When real-time embedded system software needs to be upgraded, it will be more dependable if the new software is sufficiently tested on the actual deployment platform. The challenge is to provide a safeguard for protecting the normal operations from faulty upgrades. However, the safeguard must be not only efficient but also able to be added and taken away as needed without shutting down the normal operations. We have developed an architecture based on simplex architecture and process resurrection and have applied it to the inverted pendulum control system. The measurements show that the overhead is small and justifiable.

A robust system is one that can ensure essential services in spite of faults and failures in useful but non-essential components. Unless we can ensure that critical services can only USE but not depend on less critical components, a seemingly minor fault can propagate along complex and implicit dependency chains and bring down the system. Modern real time systems are often developed concurrently by multiple teams. A team typically only knows the dependency relations between their components and neighboring components. In addition, dependency relations will change as software components and their interactions are being modified. Therefore, how to automatically track and analyze the system wide dependency from local information is important for the development of robust real time systems. This paper presents dependency algebra - a unified theoretical framework plus a prototype toolkit for dependency management in real-time systems

In this article, we define the time-indexing problem as the in-network storage and querying of sensor network data based solely on the time attribute. We argue qualitatively why existing storage schemes may be insufficient as solutions. We then present, analyze, and evaluate novel and lightweight solutions to both the storage and the querying subproblems for time indexing. First, the time-indexed storage problem is formally defined and two formulations are presented seeking to optimize generic utility functions that are derived from concerns about energy, bandwidth usage, and storage balancing. We present and analyze decentralized protocols to solve these formulations and prove the optimality of some of our solutions. Secondly, maintenance and use of simple overlays among rendezvous point nodes in order to enable fault-tolerant and efficient time-indexed queries are discussed. Finally, simulation results are presented to quantify performance characteristics of the protocols, and we find that our proposed scheme has low query overhead that scales with system size and density while exhibiting very good load-balancing and fault-tolerance properties. The use of time-indexed structure is shown to achieve more than double the lifetime of sensor networks compared to existing approaches in some scenarios.

In this paper, we present a minimum spanning tree (MST)-based algorithm, called local minimum spanning tree (LMST), for topology control in wireless multihop networks. In this algorithm, each node builds its LMST independently and only keeps on-tree nodes that are one-hop away as its neighbors in the final topology. We analytically prove several important properties of LMST: 1) the topology derived under LMST preserves the network connectivity; 2) the node degree of any node in the resulting topology is bounded by 6; and 3) the topology can be transformed into one with bidirectional links (without impairing the network connectivity) after removal of all unidirectional links. Simulation results show that LMST can increase the network capacity as well as reduce the energy consumption.

Switching the devices to low-power states in prolonged periods of inactivity is a widely used technique to conserve energy for battery-powered wireless devices. In this paper, we present a mathematical abstraction of time-out driven power management policies together with different wakeup mechanisms in wireless networks to characterize the energy-performance trade-offs. The time-out driven power management is modeled as a M/G/1/K queue with multiple vacations and an attention span. We then derive the steady state behaviors of such systems, and present a closed-form solution for systems with large buffers. The analysis reveals that the "best" power management policy to minimize the energy-delay product exhibits a threshold structure, i.e., when the traffic load is below a certain threshold, a node should switch to the low-power state whenever possible and always remain active otherwise, and suggests a threshold-based power management protocol.

Distinct from wireless ad hoc networks, wireless sensor networks are data-centric, application-oriented, collaborative, and energy-constrained in nature. In this paper, formulate the problem of data transport in sensor networks as an optimization problem whose objective function is to maximize the amount of information (utility) collected at sinks (subscribers), subject to the flow, energy and channel bandwidth constraints. Also, based on a Markov model extended from [3], we derive the link delay and the node capacity in both the single and multi-hop environments, and figure them in the problem formulation. We study three special cases under the problem formulation. In particular, we consider the energy-aware flow control problem, derive an energy aware flow control solution, and investigate via ns-2 simulation its performance. The simulation results show that the proposed energy-aware flow control solution can achieve high utility and low delay without congesting the network.

The promise of middleware is to enable integration and evolution of complex systems dynamically. In demanding domains such as wireless control networks, fulfilling this promise while maintaining complete generality is extremely complicated. Understanding and exploiting the forcing functions of a domain helps manage this complexity by avoiding redundant generalizations. Domainware exploits this technique and adopts a simpler architecture to support more important nonfunctional requirements effectively. This paper presents Etherware, a domainware for wireless control networks. Capitalizing on our development of a fairly complex control system testbed, commonly supported yet redundant generalizations are identified and eliminated. The resulting architecture is simple, and can support a wide range of trade-offs that can be manipulated easily at run-time. This is illustrated by showing how the performance of control time protocol (CTP), an Etherware service, is optimized by the additional options available in Etherware

We define the time indexing problem as the in-network storage and querying of sensor network data based solely on the time attribute. We argue qualitatively why existing storage schemes may be insufficient as solutions. We then present, analyze, and evaluate novel and lightweight solutions to both the storage and the querying sub-problems for time indexing. First, the time-indexed storage problem is formally defined, and two formulations are presented, seeking to optimize generic utility functions that are derived from concerns about energy, bandwidth usage, and storage balancing. We present and analyze decentralized protocols to solve these formulations, and prove the optimality of some of our solutions. Secondly, maintenance and use of simple overlays among rendezvous point nodes, in order to enable fault-tolerant and efficient time-indexed queries, are discussed. Finally, simulation results are presented to quantify performance characteristics of the protocols, and we find that our proposed scheme has low query overhead that scales with system size and density while exhibiting very good load balancing and fault tolerance properties.

Timing constraints for radar tasks are usually specified in terms of the minimum and maximum temporal distance between successive radar dwells. We utilize the idea of feasible intervals for dealing with the temporal distance constraints. In order to increase the freedom that the scheduler can offer a high-level resource manager, we introduce a technique for nesting and interleaving dwells online while accounting for the energy constraint that radar systems need to satisfy. Further, in radar systems, the task set changes frequently and we advocate the use of finite horizon scheduling in order to avoid the pessimism that is inherent in schedulers that assume a task executes forever. We also develop the notion of modular schedule update which allows portions of a schedule to be altered without affecting the entire schedule, thereby simplifying the scheduler. Through extensive simulations, we validate our claims of providing greater scheduling flexibility without compromising on performance when compared with earlier work based on templates constructed offline.

Route selection is an important aspect of the design of real-time systems in which messages might have to travel over multiple hops to reach their destination and multiple paths exist between a source and a destination. The length of a route affects the ability to meet deadlines and greedy routing might leave certain messages with no feasible route. We consider bus-based networks on which periodic message transmissions need to be scheduled and present a technique for synthesizing routes such that all messages meet their deadlines. Our offline technique enables system designers to configure routes in a large-scale embedded system. In our solution, we allow message fragmentation and utilize multiple paths to satisfy the requirements of each message. The routing problem is NP-complete and our approximation algorithm is based on a linear programming formulation. In our methodology, we deal with both earliest deadline first and rate monotonic scheduling at each bus in the system. Apart from point-to-point messages, we discuss scheduling multicast messages to facilitate the publisher/subscriber model. Finally, we also mention some heuristics for online routing which might be of value in soft real-time systems.

Acoustic awareness is an important service in ubiquitous computing environments. This paper presents a fast lightweight acoustic event localization protocol, the Lightning protocol, to locate impulsive sound sources using arrays of wireless micro-sensors. This protocol utilizes domain-invariant knowledge of acoustic and electromagnetic wave propagation to efficiently reduce the number of contending sensors in the localization process. It incurs O(1) transmissions irrespective of the sensor density and guarantees O(1) time delay in localization. Experiment results using UC Berkeley Motes demonstrate that the time delay for Lightning Protocol to locate hand clap sounds is in terms of milliseconds.

In many practical real-time applications, there is a given set of task frequencies (i.e., inverse of task periods) corresponding to predetermined QoS options that the applications can choose. For example, in audio applications, the typical choices of playback frequencies are for CD quality, radio quality, and phone quality. Similar configurations can be found in streaming video and in control applications. In such systems, applications dynamically arrive requesting one of the periods provided by the QoS manager. Thus, the accurate and efficient online schedulability test is essential for any task set whose periods are chosen from the QoS period set. For this purpose, we propose new utilization bounds as a function of given QoS periods. As long as there is a set of given periods that can be chosen by applications, the bounds developed can be used by the QoS manager to quickly determine the schedulability of dynamic applications.

We devise and evaluate a fully decentralized, light-weight, dynamic clustering algorithm for target tracking. Instead of assuming the same role for all the sensors, we envision a hierarchical sensor network that is composed of 1) a static backbone of sparsely placed high-capability sensors which assume the role of a cluster head (CH) upon triggered by certain signal events and 2) moderately to densely populated low-end sensors whose function is to provide sensor information to CHs upon request. A cluster is formed and a CH becomes active, when the acoustic signal strength detected by the CH exceeds a predetermined threshold. The active CH then broadcasts an information solicitation packet, asking sensors in its vicinity to join the cluster and provide their sensing information. We address and devise solution approaches (with the use of Voronoi diagram) to realize dynamic clustering: (I1) how CHs operate with one another to ensure that only one CH (preferably the CH that is closes to the target) is active with high probability, (I2) when the active CH solicits for sensor information, instead of having all the sensors in its vicinity reply, only a sufficient number of sensors respond with nonredundant, essential information to determine the target location, and (I3) both the packets that sensors send to their CHs and packets that CHs report to subscribers do not incur significant collision. Through both probabilistic analysis and ns-2 simulation, we use with the use of Voronoi diagram, the CH that is usually closes to the target is (implicitly) selected as the leader and that the proposed dynamic clustering algorithm effectively eliminates contention among sensors and renders more accurate estimates of target locations as a result of better quality data collected and less collision incurred.

Bluetooth is a promising new wireless technology that enables portable devices to form short-range wireless ad hoc networks. In this paper, we present a new, distributed Bluetooth scatternet formation algorithm, called loop scatternet formation, which forms scatternets with slave/slave bridges only. In addition to meeting the criteria of maintaining connectivity, minimizing the number of piconets and the maximum degree of devices, the proposed algorithm formalizes the notion of network diameter and node contention. The loop scatternet thus formed incurs a much smaller network diameter and the number of node pairs for which a device has to serve, as a relay node is significantly smaller than that in the other types of scatternets. To validate the design, we derive the bounds of the number of piconets, the network diameter, and the maximum node contention. We also conduct ns-2 simulation to evaluate the performance of loop scatternets. Both analytical and simulation results validate the desirable features of loop scatternets.

In the paper, we devise and evaluate a fully decentralized, light-weight, dynamic clustering algorithm for target tracking. Instead of assuming the same role for all the sensors, we envision a hierarchical sensor network that is composed of (a) a static backbone of sparsely placed high-capability sensors which assume the role of a cluster head (CH) upon triggered by certain signal events; and (b) moderately to densely populated low-end sensors whose function is to provide sensor information to CHs upon request. A cluster is formed and a CH becomes active, when the acoustic signal strength detected by the CH exceeds a pre-determined threshold. The active CH then broadcasts an information solicitation packet, asking sensors in its vicinity to join the cluster and provide their sensing information. We address and devise solution approaches (with the use of Voronoi diagram) to realize dynamic clustering: (I1) how CHs cooperate with one another to ensure that for the most of time only one CH (preferably the CH that is closest to the target) is active; (I2) when the active CH solicits for sensor information, instead of having all the sensors in its vicinity reply, only a sufficient number of sensors respond with non-redundant, essential information to determine the target location; and (I3) both packets with which sensors respond to their CHs and packets that CHs report to subscribers do not incur significant collision. Through both probabilistic analysis and ns-2 simulation, we show with the use of Voronoi diagram, the CH that is usually closest to the target is (implicitly) selected as the leader and that the proposed dynamic clustering algorithm effectively eliminates contention among sensors and renders more accurate estimates of target locations as a result of better quality data collected and less collision incurred.

In this paper, we present a minimum spanning tree (MST) based topology control algorithm, called local minimum spanning tree (LMST), for wireless multi-hop networks. In this algorithm, each node builds its local minimum spanning tree independently and only keeps on-tree nodes that are one-hop away as its neighbors in the final topology. We analytically prove several important properties of LMST: (1) the topology derived under LMST preserves the network connectivity; (2) the node degree of any node in the resulting topology is bounded by 6; and (3) the topology can be transformed into one with bidirectional links (without impairing the network connectivity) after removal of all uni-directional links. These results are corroborated in the simulation study.

Due to the slow advancement of battery technology, power management in wireless networks remains to be a critical issue. Asynchronous wakeup has the merits of not requiring global clock synchronization and being resilient to network dynamics. This paper presents a systematic approach to designing and implementing asynchronous wakeup mechanisms in ad hoc networks. The optimal wakeup schedule design can be formulated as a block design problem in combinatorics. We propose a neighbor discovery and schedule bookkeeping protocol that can operate on the optimal wakeup schedule derived. Two power management policies, i.e. slot-based power management and on-demand power management, are studied to overlay desirable communication schedule over the wakeup schedule mandated by the asynchronous wakeup mechanism. Simulation studies indicate that the proposed asynchronous wakeup protocol is quite effective under various traffic characteristics and loads: energy saving can be as high as 70%, while the packet delivery ratio is comparable to that without power management.

This paper proposes novel techniques for scheduling radar dwells in phased array radar systems. In order to handle complex physical characteristics such as dwell interleaving, transmitting duty cycle constraint, and energy constraint, we propose a notion of schedulability envelope. The schedulability envelope designed offline hides the details of complex radar dwell scheduling and provides a simple measure for the schedulability check. Using the schedulability envelope, the proposed technique can efficiently perform the admission control for dynamic target tracking tasks. The simulation results show that the proposed approach can significantly improve the system utilization by taking advantage of dwell interleaving while guaranteeing the schedulability and physical constraints.

How to allocate computing and communication resources in a way that maximizes the effectiveness of control and signal processing has been an important area of research. The characteristic of a multi-hop real-time wireless sensor network raises new challenges. First, the constraints are more complicated and a new solution method is needed. Second, we need a distributed solution to achieve scalability. This paper presents solutions to both of the new challenges. The first solution to the optimal frequency allocation is a centralized solution that can handle the more general form of constraints as compared with prior research. The second solution is a distributed version for large networks using a pricing scheme. It is capable of incremental adjustment when utility functions change.

This paper addresses the problem of scheduling real-time dwells in multi-function phase array radar systems. To keep track of targets, a radar system must meet its timing and energy constraints. We propose a new task model for radar dwells to accurately characterize their timing parameters. We develop an algorithm of transforming every dwell task as a semi-period task so the dwell task can meet its timing constraint and the interarrival times of the task will not be a constant. We also develop an enhanced template-based scheduling algorithm to schedule such tasks to meet the timing and energy constraints. Simulation results show that this algorithm can significantly improve the resource utilization.

The new millennium heralds the convergence between computing, communication, and the intelligent control of our physical environments. Embedded systems often have a long life cycle. This paper reviews our research group's work on how to upgrade embedded control systems without shutting them down, and how to protect the system from bugs and attacks that could be introduced by software upgrades.

Sensor networks can be considered distributed computing platforms with many severe constraints, including limited CPU speed, memory size, power, and bandwidth. Individual nodes in sensor networks are typically unreliable and the network topology dynamically changes, possibly frequently. Sensor networks also differ because of their tight interaction with the physical environment via sensors and actuators. Because of this interaction, we find that sensor networks are very data-centric. Due to all of these differences, many solutions developed for general distributed computing platforms and for ad-hoc networks cannot be applied to sensor networks. After discussing several motivating applications, this paper first discusses the state of the art with respect to general research challenges, then focuses on more specific research challenges that appear in the networking, operating system, and middleware layers. For some of the research challenges, initial solutions or approaches are identified.

Recent advances in wireless technology have brought us closer to the vision of pervasive computing where sensors/actuators can be connected through a wireless network. Due to cost constraints and the dynamic nature of sensor networks, it is undesirable to assume the existence of base stations connected by a wired backbone. In this paper, we present a network architecture suitable for sensor networks along with a medium access control protocol based on earliest deadline first.

Controlling the timing performance of a network server is a challenging problem. This paper presents a Queueing Model Based Feedback Control approach to keep the timing performance of a network server close to the service level specification. We show that in an instrumented Apache server, combining feedback control with a queueing model leads to better tracking of QoS specifications than with feedback control alone or queueing model based feed forward control alone.

In many real-time control applications, the task periods are typically fixed and worst-case execution times are used in schedulability analysis. With the advancement of robotics, flexible visual sensing using cameras has become a popular alternative to the use of embedded sensors. Unfortunately, the execution time of visual tracking varies greatly. In such environments, control tasks have a normally short computation time, but also an occasional long computation time; therefore, the use of worst-case execution time is inefficient for controlling performance optimization. Nevertheless, to maintain the control stability, we still need to guarantee the schedulability of the task set, even if the worst case arises. In this paper, we propose an integrated approach to control performance optimization and task scheduling for control applications where the execution time of each task can vary greatly. We present an innovative approach to overrun management that allows us to fully utilize the processor for optimizing the control performance and yet guaranteeing the schedulability of all tasks under worst-case conditions.

Integrating soft and hard activities in a real-time environment has been an active area of research both under fixed priority scheduling and dynamic priority scheduling. Most of the existing work, however, has been done under the assumption that soft real-time tasks and hard real-time tasks are independent. The paper presents an efficient method that allows soft realtime aperiodic tasks and hard real-time tasks to share resources.

Many application level qualities are functions of available computation resources. Recent studies have handled the computation resource allocation problem to maximize the overall application quality. However such QoS problem is fundamentally a multi-dimensional optimization problem that requires extensive computation. Therefore, online usage of optimization procedures may significantly reduce the computation resource available for applications. This raises the question of how to best use the optimization procedures for dynamic real-time task sets. This paper proposes a method called service classes configuration to address the QoS problem with dynamic arrival and departure of tasks. A simplified radar application is used as an illustrative example.

In many real time control applications, the task periods are typically fixed and worst case execution times are used in schedulability analysis. With the advancement of robotics, flexible visual sensing using cameras has become a popular alternative to the use of embedded sensors. Unfortunately, the execution time of visual tracking varies greatly. In such environments, control tasks have a normally short computation time but also an occasional long computation time; therefore, the use of worst case execution time is inefficient for controlling performance optimization. Nevertheless, to maintain the control stability, we still need to guarantee the task set, even if the worst case arises. We propose an integrated approach to control performance optimization and task scheduling for control applications where the execution time of each task can vary greatly. We create an innovative approach to elastic control that allows us to fully utilize the processor to optimize the control performance and yet guarantee the schedulability of all tasks under worst case conditions.

Presents a general scheduling methodology for managing overruns in a real-time environment, where tasks may have different criticalities and flexible timing constraints. The proposed method achieves isolation among tasks through a resource reservation mechanism which bounds the effects of task interference but which also performs efficient reclamation of the unused computation times in order to relax the utilization constraints imposed by isolation. The enhancements achieved by the proposed approach were found to be very effective with respect to classical reservation schemes. The performance has been evaluated by implementing the algorithm on a real-time kernel. The runtime overhead introduced by the scheduling mechanism has also been investigated with specific experiments, in order for this to be taken into account in the schedulability analysis. However, this overhead was found to be negligible in most practical cases.

Feedback control is one of the most common applications of real time systems. However, the design of controller frequencies, task scheduling and reliability engineering are often done separately, resulting in suboptimal results. The article provides an overview of an integrated approach to reliable real time controller design by optimizing the system control performance subject to schedulability and software reliability constraints. In control applications, the software reliability challenges goes beyond the specification, design, development and verification considerations. Advanced control techniques such as a neural net learns by example and can perform sophisticated nonlinear control. Indeed, the properties of certain advanced controllers can be difficult to analyze and verify. This problem can be addressed by using analytically redundant controllers, where the sophisticated but less reliable controller is "supervised" by a simple and reliable controller. An example of using analytically redundant controllers to enhance system reliability is the Boeing 777 flight control, where the normal controller is the new 777 controller, whereas the secondary controller is based on the well understood 747 control technology. The aircraft's state under the normal controller should be within the stability envelope of the 747 controller (Y.C. Yeh, 1995).

In many real time applications, especially those involving computer controlled systems, the application tasks often have a maximal acceptable latency, and small latency is preferred to large. The interaction between choosing task periods to meet the individual latency requirements and scheduling the resulting task set was investigated by D. Seto et al. (1996) using dynamic priority scheduling methods. We present algorithms based on static priority scheduling methods to determine optimal periods for each task in the task set. The solution to the period selection problem optimizes a system wide performance measure, subject to meeting the maximal acceptable latency requirements of each task. The paper also contributes to a new aspect of rate monotonic scheduling, the optimal design of task periods in connection with application related timing specifications and task set schedulability.

The rate of innovations in technologies has far exceeded the rate of adopting them in at least the past 20 years. To fully realize the potential of innovations, a paradigm shift is needed, from a focus on enabling technologies for completely new installations to one which is designed to mitigate the risk and cost of bringing new technologies into functioning systems. In this paper, we show that real time control software can be dependably upgrade online via the use of analytically redundant controllers.

Next-generation networks are expected to support a wide variety of services. Some services such as video, voice, and plant control traffic have explicit timing requirements on a per-message basis rather than on the average. In this paper, we develop a general model of dual-link networks to support real-time communication. We examine the desirable properties of this network and the difficulties in achieving these properties. We then introduce the concept of coherence and develop a theory of coherent dual-link networks. We show that a coherent dual-link network can be analyzed as though it is a centralized system. We then discuss practical considerations in implementing a dual-link network, and implications of this work to address problems observed in the IEEE 802.6 metropolitan area network standard.

Most real-time computer-controlled systems are built in two separate steps, each in isolation: controller design and its digital implementation. Computational tasks that realize the control algorithms are usually scheduled by treating their execution times and periods as unchangeable parameters. Task scheduling therefore depends only on the limited computing resources available. On the other hand, controller design is primarily based on the continuous-time dynamics of the physical system being controlled. The set of tasks resulting from this controller design may not be schedulable with the limited computing resources available. Even if the given set of tasks is schedulable, the overall control performance may not be optimal in the sense that they do not make a full use of the computing resource. We propose an integrated approach to controller design and task scheduling. Specifically, task frequencies (or periods) are allowed to vary within a certain range as long as such a change does not affect critical control functions such as maintenance of system stability. We present an algorithm that optimizes task frequencies and then schedules the resulting tasks with the limited computing resources available. The proposed approach is also applicable to failure recovery and reconfiguration in real-time control systems.

Most existing scheduling algorithms for hard real-time systems apply either to periodic tasks or aperiodic tasks but not to both. In practice, real-time systems require an integrated, consistent approach to scheduling that is able to simultaneously meet the timing requirements of hard deadline periodic tasks, hard deadline aperiodic (alert-class) tasks, and soft deadline aperiodic tasks. This paper introduces the Deferrable Server (DS) algorithm which will be shown to provide improved aperiodic response time performance over traditional background and polling approaches. Taking advantage of the fact that, typically, there is no benefit in early completion of the periodic tasks, the Deferrable Server (DS) algorithm assigns higher priority to the aperiodic tasks up until the point where the periodic tasks would start to miss their deadlines. Guaranteed alert-class aperiodic service and greatly reduced response times for soft deadline aperiodic tasks are important features of the DS algorithm, and both are obtained with the hard deadlines of the periodic tasks still being guaranteed. The results of a simulation study performed to evaluate the response time performance of the new algorithm against traditional background and polling approaches are presented. In all cases, the response times of aperiodic tasks are significantly reduced (often by an order of magnitude) while still maintaining guaranteed periodic task deadlines.>

Real-time computing systems are used to control telecommunication systems, defense systems, avionics, and modern factories. Generalized rate-monotonic scheduling theory, is a recent development that has had large impact on the development of real-time systems and open standards. In this paper we provide an up-to-date and self-contained review of generalized rate-monotonic scheduling theory. We show how this theory can be applied in practical system development, where special attention must be given to facilitate concurrent development by geographically distributed programming teams and the reuse of existing hardware and software components.>

The authors develop a general model of reservation-based dual-link networks to support real-time communication. They examine the desirable properties of this network and the difficulties in achieving these properties. They then introduce the concept of coherence and develop a theory of coherent dual-link networks. It is shown that a coherent dual-link network can be analyzed as though it is a centralized system. It is also shown that a coherent dual-link network can be analyzed similarly to an equivalent centralized system in terms of its schedulability for periodic message traffic.>

The authors examine a priority driven two-phase lock protocol called the read/write priority ceiling protocol. It is shown that this protocol leads to freedom from mutual deadlock. In addition, a high-priority transactions can be blocked by lower priority transactions for at most the duration of a single embedded transaction. These properties can be used by schedulability analysis to guarantee that a set of periodic transactions using this protocol can always meet its deadlines. Finally, the performance of this protocol is examined for randomly arriving transactions using simulation studies.>

A simple but efficient architecture for building multiprocessors is to connect several processors to a common backplane bus. The backplane acts as a shared resource in this architecture and contention for its use by different bus modules must be resolved. In a real-time system, this backplane must also provide scheduling support such that the timing behavior of the resulting system is analyzable. In addition, the support primitives for real-time scheduling on a backplane bus must also be constrained by the economic considerations associated with a bus standard that is intended to support both time sharing and real-time applications. The authors review the design considerations to support real-time systems in the IEEE Futurebus+ backplane specification and describe how this backplane can be used to satisfy timing constraints in priority-driven real-time systems.>

An investigation is conducted of two protocols belonging to the priority inheritance protocols class; the two are called the basic priority inheritance protocol and the priority ceiling protocol. Both protocols solve the uncontrolled priority inversion problem. The priority ceiling protocol solves this uncontrolled priority inversion problem particularly well; it reduces the worst-case task-blocking time to at most the duration of execution of a single critical section of a lower-priority task. This protocol also prevents the formation of deadlocks. Sufficient conditions under which a set of periodic tasks using this protocol may be scheduled is derived.>

An exact characterization of the ability of the rate monotonic scheduling algorithm to meet the deadlines of a periodic task set is represented. In addition, a stochastic analysis which gives the probability distribution of the breakdown utilization of randomly generated task sets is presented. It is shown that as the task set size increases, the task computation times become of little importance, and the breakdown utilization converges to a constant determined by the task periods. For uniformly distributed tasks, a breakdown utilization of 88% is a reasonable characterization. A case is shown in which the average-case breakdown utilization reaches the worst-case lower bound of C.L. Liu and J.W. Layland (1973).>

The effect of three I/O controller architectures on schedulable utilization, which is the highest attainable resource utilization at or below which all deadlines can be guaranteed, is examined. FIFO (first-in-first-out) request queuing, priority queuing, and priority queuing with preemptable service are simulated for a range of CPU computation to I/O traffic ratios. The results show that, for I/O-bound task sets and zero preemption costs, priority queuing with preemptable service can provide a level of schedulable utilization 35% higher than that attainable with FIFO queuing, and 20% higher than priority queuing and nonpreemptable service. Although the potential gain for priority queuing with preemptable service is large, further simulations that incorporate a time penalty for each preemption show that the gain is very sensitive to preemption cost. With preemption cost represented as a ratio of preemption time to the minimum-task period, the level of schedulable utilization for priority queuing with preemptable service degrades to that of priority queuing with nonpreemptible service, for a preemption cost ratio of 0.04. A high-level design of a preemptable I/O controller is described and the issues determining preemption cost are detailed, along with techniques for its minimization.>

The authors investigate the synchronization problem in the context of priority-driven preemptive scheduling on shared-memory multiprocessors. Unfortunately, a direct application of synchronization mechanisms such as the Ada rendezvous, semaphores, or monitors can lead to uncontrolled priority inversion: a high job being blocked by a lower priority job for an indefinite period of time. A task allocation scheme based on the generalized protocol is outlined.>

Real-time scheduling algorithms that provide responsive aperiodic service in the presence of hard real-time periodic tasks require the creation of a high-priority periodic server task for servicing aperiodic requests. The authors describe the extended priority exchange algorithm, which can provide better aperiodic response than previous aperiodic service algorithms, particularly for cases where the worst-case periodic load is high and little or no utilization is left for a server task. The extended-priority-exchange (EPE) algorithm attains better aperiodic responsiveness by exploiting unused time allocated to periodic tasks for aperiodic service. The average aperiodic response times for the EPE algorithm and four other aperiodic service algorithms (background, polling, deferrable server, and priority exchange) are compared for a range of periodic and aperiodic loads. Simulation results show that for a difference between the average and worst-case periodic load of only 12.5%, the EPE algorithm provides significantly better response times for aperiodic tasks.>

An approach to concurrency control is presented; it is based on the decomposition of both the database and the individual transactions. This approach is a generalization of serializability theory in that the set of permissible transaction schedules contains all the serializable schedules. In addition to providing a higher degree of concurrency than that provided by serializability theory, this approach retains three important properties associated with serializability: the consistency of the database is preserved, the individual transactions are executed correctly, and the concurrency control approach is modular. The authors formalize the last concept. The associated failure recovery procedure is presented, as is the concept of failure safety (i.e. failure tolerance).>

When periodic tasks with hard deadlines communicate over a bus, the problem of hard real-time bus scheduling arises. This paper addresses several problems of hard real-time bus scheduling, including the evaluation of scheduling algorithms and the issues of message packet pacing, preemption, priority granularity and buffering.

As part of our research in the Archons [Jensen 82] project on decentralized computers, we have developed a relational model of data consistency to replace the conventional serialization model for reasoning about the relationships among distributed system data objects in general and state variables in particular. We not only permit but encourage such relationships to be probabilistic, in the interest of efficiency. This model leads to a new formulation of co-operating processes, and thence to the notion of co-operating transactions: co-operating processes whose actions are made atomic for the sake of reliability. We believe that co-operating processes are valuable in a computer network, but essential in a decentralized computer [Jensen 82] where the conceptually singular but physically dispersed global operating system requires a transaction facility in the kernel [Jensen 80]. These ideas are illustrated by examples from our initial experience in applying the model to the Accent network operating system and other system software of the Spice personal computing network. This document is intended to be an overview of the synchronization effort in the Archons project, and future publications will elaborate on many of the individual points touched on here.