Clinical language models (LMs) are increasingly applied to support clinical risk prediction from free-text notes, yet their uncertainty estimates often remain poorly calibrated and clinically unreliable.In this work, we propose Clinical Uncertainty Risk Alignment (CURA), a framework that aligns clinical LM-based risk estimates and uncertainty with both individual error likelihoods and cohort-level ambiguities.CURA first fine-tunes domain-specific clinical LMs to obtain task-adapted patient embeddings, and then performs uncertainty fine-tuning of a multi-head classifier using a bi-level uncertainty objective.Specifically, an individuallevel calibration term aligns predictive uncertainty with each patient's likelihood of error, while a cohort-aware regularizer pulls risk estimates toward event rates in their local neighborhoods in the embedding space and places extra weight on ambiguous cohorts near the decision boundary.We further show that this cohort-aware term can be interpreted as a crossentropy loss with neighborhood-informed soft labels, providing a label-smoothing view of our method.Extensive experiments on MIMIC-IV clinical risk prediction tasks across various clinical LMs show that CURA consistently improves calibration metrics without substantially compromising discrimination.Further analysis illustrates that CURA reduces overconfident false reassurance and yields more trustworthy uncertainty estimates for downstream clinical decision support.

Wearable devices, which continuously capture activity and physiological data, offer dynamic insights into patient health that complement traditional static clinical predictors. While integrating wearable and clinical data has shown promise for predicting clinical outcomes, the impact of cohort variability on model robustness remains underexplored. In this study, we investigate the impact of cohort variability on predictive model performance in a clinical study focused on predicting pancreatic surgery outcomes using data from Fitbit wristbands and clinical characteristics. This study, initiated before the COVID-19 pandemic and disrupted by surgery delays, highlights substantial variations in patient data before and after the pandemic. Our findings also show that the predictive utility of wearable and clinical features varies across patients. To address these challenges, we propose Adaptive Mixture of Experts (AdaMoE) , a Mixture of Experts model with a diversity regularization that adaptively adjusts the weighting of wearable and clinical features per patient. In a clinical study of 83 pancreatic surgery patients, our approach achieves improved performance compared to existing models and shows promise for handling cohort variability. This work underscores the importance of accounting for cohort variability in predictive modeling and suggests a pathway to enhance model robustness under cohort variability.

OBJECTIVE: Early detection of surgical complications allows for timely therapy and proactive risk mitigation. Machine learning (ML) can be leveraged to identify and predict patient risks for postoperative complications. We developed and validated the effectiveness of predicting postoperative complications using a novel surgical Variational Autoencoder (surgVAE) that uncovers intrinsic patterns via cross-task and cross-cohort presentation learning. MATERIALS AND METHODS: This retrospective cohort study used data from the electronic health records of adult surgical patients over 4 years (2018-2021). Six key postoperative complications for cardiac surgery were assessed: acute kidney injury, atrial fibrillation, cardiac arrest, deep vein thrombosis or pulmonary embolism, blood transfusion, and other intraoperative cardiac events. We compared surgVAE's prediction performance against widely-used ML models and advanced representation learning and generative models under 5-fold cross-validation. RESULTS: 89 246 surgeries (49% male, median [IQR] age: 57 [45-69]) were included, with 6502 in the targeted cardiac surgery cohort (61% male, median [IQR] age: 60 [53-70]). surgVAE demonstrated generally superior performance over existing ML solutions across postoperative complications of cardiac surgery patients, achieving macro-averaged AUPRC of 0.409 and macro-averaged AUROC of 0.831, which were 3.4% and 3.7% higher, respectively, than the best alternative method (by AUPRC scores). Model interpretation using Integrated Gradients highlighted key risk factors based on preoperative variable importance. DISCUSSION AND CONCLUSION: Our advanced representation learning framework surgVAE showed excellent discriminatory performance for predicting postoperative complications and addressing the challenges of data complexity, small cohort sizes, and low-frequency positive events. surgVAE enables data-driven predictions of patient risks and prognosis while enhancing the interpretability of patient risk profiles.

Advances in computer vision and deep learning have made video-based Human Action Recognition (HAR) increasingly feasible. However, running HAR on live video streams encounters significant delays on embedded platforms due to computational demands. This work addresses real-time HAR performance challenges through four key contributions: (1) an experimental study identifying standard Optical Flow (OF) extraction as the primary latency bottleneck in a state-of-the-art HAR pipeline, (2) an analysis of the latency-accuracy trade-off between traditional and deep learning-based OF methods, underscoring the need for an efficient motion feature extractor with minimal impact on accuracy, (3) the design of Integrated Motion Feature Extractor (IMFE) , a novel unified neural network architecture that substantially reduces motion feature extraction latency, and (4) the development of RT-HARE , a real-time HAR system optimized for embedded platforms. Experiments on three benchmark datasets of various characteristics using the Nvidia Jetson Xavier NX platform demonstrate that RT-HARE achieves real-time HAR with lower and more stable latency, reduced power consumption, and a smaller memory footprint while maintaining recognition accuracy comparable to more complex server-based HAR models.

Recent advances in machine learning and hardware have produced embedded devices capable of performing real-time object detection with commendable accuracy. We consider a scenario in which embedded devices rely on an onboard object detector, but have the option to offload detection to a more powerful edge server when local accuracy is deemed too low. Resource constraints, however, limit the number of images that can be offloaded to the edge. Our goal is to identify which images to offload to maximize overall detection accuracy under those constraints. To that end, the paper introduces a reward metric designed to quantify potential accuracy improvements from offloading individual images, and proposes an efficient approach to make offloading decisions by estimating this reward based only on local detection results. The approach is computationally frugal enough to run on embedded devices, and empirical findings indicate that it outperforms existing alternatives in improving detection accuracy even when the fraction of offloaded images is small. Code for the paper's solution is available at https://github.com/qiujiaming315/edgeml-object-detection.

Modern control systems are embracing multi-tier architectures integrating end devices and edge servers. However, due to the distinct control performance demands associated with each control task, it is a formidable challenge to optimize the control performance of multiple control tasks subject to stringent computation resource constraints while guaranteeing stability. Moreover, inherent contradictions exist in the timing aspect between the stability guarantee, which relies on offline analysis, and the run-time control performance, which should be enhanced online. It is essential to bridge the gap between the real-time scheduling of control tasks and their actual control performance. In this paper, we propose a novel real-time scheduling approach for multi-tier control systems, which leverages end devices for executing real-time control tasks and edge devices for runtime coordination. Specifically, we first introduce a new datadriven value function, called time/state/utility functions (TSUF), for modeling control system performance. TSUF captures not only timing but also the dynamic states of the physical plants. Subsequently, we propose value-based control scheduling (VCS), which is a multi-granularity scheduling mechanism based on our TSUF value function. VCS distinguishes the scheduling of stability jobs for ensuring system stability and performance jobs for optimizing real-time control performance based on run-time physical states. Finally, through realistic case studies involving multiple control loops, we demonstrate the advantages of VCS over existing scheduling approaches in terms of both control and real-time performance.

Along with the fourth industrial revolution, industrial automation systems are evolving into a multi-tier end-edge computing architecture. Edge controllers, which are equipped with a larger computing capacity compared to local controllers, can communicate with local plants over mainstream wireless networks such as WirelessHART, Wi-Fi, and cellular networks. Well-known challenges induced by networks, such as uncertain time delays and packet drops, have been intensively investigated from various perspectives: control synthesis, network design, or control and network co-design. The status quo is that the industry remains hesitant to close the loop between the edge controller and the actuation side due to safety concerns. This work offers an alternative perspective to address the safety concern, by exploiting the design freedom of an end-edge computing architecture. Specifically, we present a smart actuation framework, which deploys (1) an edge controller, which communicates with physical plant via wireless network, accounting for optimality, adaptation, and constraints by conducting computationally expensive operations; (2) a smart actuator, which is co-located with the physical plant on the end tier and executes a local control policy, accounting for system safety in the view of network imperfections, (3) the end-edge control co-design strategies and cooperation logic for both performance and stability. For certain classes of plants, semi-globally asymptotic stability of the resulting end-edge control systems is established when the edge controller is the model predictive control (MPC), or policy iteration-based learning control. We also provide an adaptation strategy for the end-edge control systems facing model parameter mismatches when the edge controller employs reinforcement learning. Extensive simulations demonstrate the advantages of the proposed end-edge co-design and cooperation procedures. Note to Practitioners—Edge computing is gaining momentum in areas that require low latency and high efficiency, i.e., mobile computing, video analytics, and autonomous driving. Industrial automation systems are also evolving into a multi-tier end-edge computing architecture. It pays obvious dividends to leverage the cooperation between end and edge, benefiting from fast and reliable communication on the end side, and powerful computation capacity on the edge side. The current end-edge cooperation focuses on how to partition tasks and offload computation resources in order to minimize delay and energy consumption, as well as how to balance the tradeoff between them. However, the impacts of end-edge cooperation on the safety, optimality, and cost of industrial automation have not been systematically studied. This paper aims to tailor end-edge cooperation in a smart actuation framework, for industrial automation to reconcile the above aspects by leveraging co-design of end and edge controllers and their switching logic. Extensive pure and semi-physical simulations demonstrate the advantages in performance and system stability of the proposed end-edge co-design and cooperation procedures.

Extracorporeal membrane oxygenation (ECMO) is an essential life-supporting modality for COVID-19 patients who are refractory to conventional therapies. However, the proper treatment decision has been the subject of significant debate and it remains controversial about who benefits from this scarcely available and technically complex treatment option. To support clinical decisions, it is a critical need to predict the treatment need and the potential treatment and no-treatment responses. Targeting this clinical challenge, we propose Treatment Variational AutoEncoder (TVAE), a novel approach for individualized treatment analysis. TVAE is specifically designed to address the modeling challenges like ECMO with strong treatment selection bias and scarce treatment cases. TVAE conceptualizes the treatment decision as a multi-scale problem. We model a patient's potential treatment assignment and the factual and counterfactual outcomes as part of their intrinsic characteristics that can be represented by a deep latent variable model. The factual and counterfactual prediction errors are alleviated via a reconstruction regularization scheme together with semi-supervision, and the selection bias and the scarcity of treatment cases are mitigated by the disentangled and distribution-matched latent space and the label-balancing generative strategy. We evaluate TVAE on two real-world COVID-19 datasets: an international dataset collected from 1651 hospitals across 63 countries, and a institutional dataset collected from 15 hospitals. The results show that TVAE outperforms state-of-the-art treatment effect models in predicting both the propensity scores and factual outcomes on heterogeneous COVID-19 datasets. Additional experiments also show TVAE outperforms the best existing models in individual treatment effect estimation on the synthesized IHDP benchmark dataset.

IoT devices are increasingly the source of data for machine learning (ML) applications running on edge servers. Data transmissions from devices to servers are often over local wireless networks whose bandwidth is not just limited but, more importantly, variable. Furthermore, in cyber-physical systems interacting with the physical environment, image offloading is also commonly subject to timing constraints. It is, therefore, important to develop an adaptive approach that maximizes the inference performance of ML applications under timing constraints and the resource constraints of IoT devices. In this paper, we use image classification as our target application and propose progressive neural compression (PNC) as an efficient solution to this problem. Although neural compression has been used to compress images for different ML applications, existing solutions often produce fixed-size outputs that are unsuitable for timing-constrained offloading over variable bandwidth. To address this limitation, we train a multi-objective rateless autoencoder that optimizes for multiple compression rates via stochastic taildrop to create a compression solution that produces features ordered according to their importance to inference performance. Features are then transmitted in that order based on available bandwidth, with classification ultimately performed using the (sub)set of features received by the deadline. We demonstrate the benefits of PNC over state-of-the-art neural compression approaches and traditional compression methods on a testbed comprising an IoT device and an edge server connected over a wireless network with varying bandwidth.

As industrial plants embrace modern technologies, such as edge computing and wireless networks, industrial control systems have evolved into multitier cyber–physical systems. While traditional local controllers enjoy reliable connectivity to sensors/actuators, they suffer from the limited computation capacity of embedded devices. In contrast, edge servers introduce more computation resources connected to sensors/actuators through wireless networks. Offloading control functions to edge servers presents new opportunities to enhance control performance but also poses critical challenges. As wireless networks have limited bandwidth and varying reliability, it is important to optimize control performance by dynamically offloading a subset of the control functions to edge servers under the bandwidth constraint. Furthermore, the selection of offloaded control functions depends on both the cyber (wireless) and physical states of the wireless control systems. In this article, we tackle the problem of optimizing the control performance of multiple control loops through dynamic edge offloading. We establish a data-driven model to predict the control performance of each feedback control loop based on its cyber–physical states. We then develop a dynamic edge offloading approach to optimize the overall control performance of a system with multiple feedback control loops while guaranteeing their stability under fluctuating cyber–physical conditions. Finally, we demonstrate the efficacy of the data-driven model and offloading approach in case studies comprising simulations of up to 20 industrial robots.

Raw audit logs provide a comprehensive record of clinicians' activities on an electronic health record (EHR) and have considerable potential for studying clinician behaviors. However, research using raw audit logs is limited because they lack context for clinical tasks, leading to difficulties in interpretation. We describe a novel unsupervised approach using the comparison and visualization of EHR action embeddings to learn context and structure from raw audit log activities. Using a dataset of 15 767 634 raw audit log actions performed by 88 intern physicians over 6 months of EHR use across inpatient and outpatient settings, we demonstrated that embeddings can be used to learn the situated context for EHR-based work activities, identify discrete clinical workflows, and discern activities typically performed across diverse contexts. Our approach represents an important methodological advance in raw audit log research, facilitating the future development of metrics and predictive models to measure clinician behaviors at the macroscale.

OBJECTIVE: Extracorporeal membrane oxygenation (ECMO) resource allocation tools are currently lacking. We developed machine learning (ML) models for predicting COVID-19 patients at risk of receiving ECMO to guide patient triage and resource allocation. MATERIAL AND METHODS: We included COVID-19 patients admitted to intensive care units for >24 h from March 2020 to October 2021, divided into training and testing development and testing-only holdout cohorts. We developed ECMO deployment timely prediction model ForecastECMO using Gradient Boosting Tree (GBT), with pre-ECMO prediction horizons from 0 to 48 h, compared to PaO2/FiO2 ratio, Sequential Organ Failure Assessment score, PREdiction of Survival on ECMO Therapy score, logistic regression, and 30 pre-selected clinical variables GBT Clinical GBT models, with area under the receiver operator curve (AUROC) and precision recall curve (AUPRC) metrics. RESULTS: ECMO prevalence was 2.89% and 1.73% in development and holdout cohorts. ForecastECMO had the best performance in both cohorts. At the 18-h prediction horizon, a potentially clinically actionable pre-ECMO window, ForecastECMO, had the highest AUROC (0.94 and 0.95) and AUPRC (0.54 and 0.37) in development and holdout cohorts in identifying ECMO patients without data 18 h prior to ECMO. DISCUSSION AND CONCLUSIONS: We developed a multi-horizon model, ForecastECMO, with high performance in identifying patients receiving ECMO at various prediction horizons. This model has potential to be used as early alert tool to guide ECMO resource allocation for COVID-19 patients. Future prospective multicenter validation would provide evidence for generalizability and real-world application of such models to improve patient outcomes.

We present an end-to-end model using streaming physiological time series to predict near-term risk for hypoxemia, a rare, but life-threatening condition known to cause serious patient harm during surgery. Inspired by the fact that a hypoxemia event is defined based on a future sequence of low SpO2 (i.e., blood oxygen saturation) instances, we propose the hybrid inference network (hiNet) that makes hybrid inference on both future low SpO2 instances and hypoxemia outcomes. hiNet integrates 1) a joint sequence autoencoder that simultaneously optimizes a discriminative decoder for label prediction, and 2) two auxiliary decoders trained for data reconstruction and forecast, which seamlessly learn contextual latent representations that capture the transition from present states to future states. All decoders share a memory-based encoder that helps capture the global dynamics of patient measurement. For a large surgical cohort of 72,081 surgeries at a major academic medical center, our model outperforms strong baselines including the model used by the state-of-the-art hypoxemia prediction system. With its capability to make real-time predictions of near-term hypoxemic at clinically acceptable alarm rates, hiNet shows promise in improving clinical decision making and easing burden of perioperative care.

Major postoperative complications are devastating to surgical patients. Some of these complications are potentially preventable via early predictions based on intraoperative data. However, intraoperative data comprise long and fine-grained multivariate time series, prohibiting the effective learning of accurate models. The large gaps associated with clinical events and protocols are usually ignored. Moreover, deep models generally lack transparency. Nevertheless, the interpretability is crucial to assist clinicians in planning for and delivering postoperative care and timely interventions. Towards this end, we propose a hierarchical model combining the strength of both attention and recurrent models for intraoperative time series. We further develop an explanation module for the hierarchical model to interpret the predictions by providing contributions of intraoperative data in a fine-grained manner. Experiments on a large dataset of 111,888 surgeries with multiple outcomes and an external high-resolution ICU dataset show that our model can achieve strong predictive performance (i.e., high accuracy) and offer robust interpretations (i.e., high transparency) for predicted outcomes based on intraoperative time series.

Burnout is a significant public health concern affecting nearly half of the healthcare workforce. This paper presents the first end-to-end deep learning framework for predicting physician burnout based on electronic health record (EHR) activity logs, digital traces of physician work activities that are available in any EHR system. In contrast to prior approaches that exclusively relied on surveys for burnout measurement, our framework directly learns deep representations of physician behaviors from large-scale clinician activity logs to predict burnout. We propose the Hierarchical burnout Prediction based on Activity Logs (HiPAL), featuring a pre-trained time-dependent activity embedding mechanism tailored for activity logs and a hierarchical predictive model, which mirrors the natural hierarchical structure of clinician activity logs and captures physicians' evolving burnout risk at both short-term and long-term levels. To utilize the large amount of unlabeled activity logs, we propose a semi-supervised framework that learns to transfer knowledge extracted from unlabeled clinician activities to the HiPAL-based prediction model. The experiment on over 15 million clinician activity logs collected from the EHR at a large academic medical center demonstrates the advantages of our proposed framework in predictive performance of physician burnout and training efficiency over state-of-the-art approaches.

Given the risks and cost of hospitalization, there has been significant interest in exploiting machine learning models to improve perioperative care. However, due to the high dimensionality and noisiness of perioperative data, it remains a challenge to develop accurate and robust encoding for surgical predictions. Furthermore, it is important for the encoding to be interpretable by perioperative care practitioners to facilitate their decision making process. We proposeclinical variational autoencoder (cVAE), a deep latent variable model that addresses the challenges of surgical applications through two salient features. (1) To overcome performance limitations of traditional VAE, it isprediction-guided with explicit expression of predicted outcome in the latent representation. (2) Itdisentangles the latent space so that it can be interpreted in a clinically meaningful fashion. We apply cVAE to two real-world perioperative datasets to evaluate its efficacy and performance in predicting outcomes that are important to perioperative care, including postoperative complication and surgery duration. To demonstrate the generality and facilitate reproducibility, we also apply cVAE to the open MIMIC-III dataset for predicting ICU duration and mortality. Our results show that the latent representation provided by cVAE leads to superior performance in classification, regression and multi-task predictions. The two features of cVAE are mutually beneficial and eliminate the need of a predictor. We further demonstrate the interpretability of the disentangled representation and its capability to capture intrinsic characteristics of hospitalized patients. While this work is motivated by and evaluated in the context of clinical applications, the proposed approach may be generalized for other fields using high-dimensional and noisy data and valuing interpretable representations.

Embedded devices are becoming increasingly pervasive in safety-critical systems of the emerging cyber-physical world. While trusted execution environments (TEEs), such as ARM TrustZone, have been widely deployed in mobile platforms, little attention has been given to deployment on real-time cyber-physical systems, which present a different set of challenges compared to mobile applications. For safety-critical cyber-physical systems, such as autonomous drones or automobiles, the current TEE deployment paradigm, which focuses only on confidentiality and integrity, is insufficient. Computation in these systems also needs to be completed in a timely manner (e.g., before the car hits a pedestrian), putting a much stronger emphasis on availability.To bridge this gap, we present RT-TEE, a real-time trusted execution environment. There are three key research challenges. First, RT-TEE bootstraps the ability to ensure availability using a minimal set of hardware primitives on commodity embedded platforms. Second, to balance real-time performance and scheduler complexity, we designed a policy-based event-driven hierarchical scheduler. Third, to mitigate the risks of having device drivers in the secure environment, we designed an I/O reference monitor that leverages software sandboxing and driver debloating to provide fine-grained access control on peripherals while minimizing the trusted computing base (TCB).We implemented prototypes on both ARMv8-A and ARMv8-M platforms. The system is tested on both synthetic tasks and real-life CPS applications. We evaluated rover and plane in simulation and quadcopter both in simulation and with a real drone.

This article considers a setting where embedded devices are used to acquire and classify images. Because of limited computing capacity, embedded devices rely on a parsimonious classification model with uneven accuracy. When local classification is deemed inaccurate, devices can decide to offload the image to an edge server with a more accurate but resource-intensive model. Resource constraints, e.g., network bandwidth, however, require regulating such transmissions to avoid congestion and high latency. This article investigates this offloading problem when transmissions regulation is through a token bucket, a mechanism commonly used for such purposes. The goal is to devise a lightweight, online offloading policy that optimizes an application-specific metric (e.g., classification accuracy) under the constraints of the token bucket. This article develops a policy based on a deep$Q$-network (DQN), and demonstrates both its efficacy and the feasibility of its deployment on embedded devices. Of note is the fact that the policy can handle complex input patterns, including correlation in image arrivals and classification accuracy. The evaluation is carried out by performing image classification over a local testbed using synthetic traces generated from the ImageNet image classification benchmark. Implementation of this work is available athttps://github.com/qiujiaming315/edgeml-dqn.

As the role of virtualization technology becomes more prevalent, the range of applications deployed in virtualized systems is steadily growing. This increasingly includes applications with soft real-time requirements that benefit from low and predictable latency, even when co-located with other virtualized hosts with arbitrary traffic patterns. In this paper, we examine the policies and mechanisms affecting communication latency between virtual machines based on the Xen platform, and identify limitations that can result in long or unpredictable network stack latency for virtual machines deployed on this platform. To address these limitations, we propose and implementVATC, aVirtualization-Aware Traffic Controlframework that supports differentiation (via rate-limited prioritization) of outbound and inbound network traffic from co-located virtualized hosts. Results of our experiments show how and why VATC can offer predictable (soft) latency guarantees to applications running on virtualized hosts with minimum overhead.

The cloud's flexibility and promise of seamless auto-scaling notwithstanding, its ability to meet service level objectives (SLOs) typically calls for some form of control in resource usage. This seemingly traditional problem gives rise to new challenges in a cloud setting, and in particular a subtle yet significant trade-off involving load-distribution decisions (the distribution of workload across available cloud resources to optimize performance), and rate limiting (the capping of individual workloads to prevent global over-commitment). This paper investigates that trade-off through the design and implementation of a real-time messaging system motivated by Internet-of- Things (IoT) applications, and demonstrates a solution capable of realizing an effective compromise. The paper's contributions are in both explicating the source of this trade-off, and in demonstrating a possible solution.

Machine learning techniques have shown promise in predicting clinical deterioration of hospitalized patients based on electronic health record (EHR). However, building accurate early warning systems (EWS) remains challenging in practice. EHRs are heterogeneous, comprising both static and time-series data. Moreover, missing values are prevalent in both static and time-series data, and the missingness of certain data can be correlated to clinical outcomes. This paper proposes a novel approach for integrating static and time-series clinical data in deep recurrent models through multi-modal fusion. Furthermore, we exploit the correlation of static and time-series data through cross-modal imputation in an integrated recurrent model. We apply the proposed approaches to a dataset extracted from the EHR of 20,700 hospitalizations of adult oncology patients in a research hospital. The experiments demonstrate the proposed approaches outperform the state-of-the-art models in terms of predictive accuracy in generating early warnings for clinical deterioration. A case study further establishes the efficacy of the predictive model for early warning systems under realistic clinical settings.

No abstract available.

Fault-tolerant coordination services have been widely used in distributed applications in cloud environments. Recent years have witnessed the emergence of time-sensitive applications deployed in edge computing environments, which introduces both challenges and opportunities for coordination services. On one hand, coordination services must recover from failures in a timely manner. On the other hand, edge computing employs local networked platforms that can be exploited to achieve timely recovery. In this work, we first identify the limitations of the leader election and recovery protocols underlying Apache ZooKeeper, the prevailing open-source coordination service. To reduce recovery latency from leader failures, we then design RT-Zookeeper with a set of novel features including a fast-convergence election protocol, a quorum channel notification mechanism, and a distributed epoch persistence protocol. We have implemented RT-Zookeeper based on ZooKeeper version 3.5.8. Empirical evaluation shows that RT-ZooKeeper achieves 91% reduction in maximum recovery latency in comparison to ZooKeeper. Furthermore, a case study demonstrates that fast failure recovery in RT-ZooKeeper can benefit a common messaging service like Kafka in terms of message latency.

Machine learning and data mining techniques are increasingly being applied to electronic health record (EHR) data to discover underlying patterns and make predictions for clinical use. For instance, these data may be evaluated to predict clinical deterioration events such as cardiopulmonary arrest or escalation of care to the intensive care unit (ICU). In clinical practice, early warning systems with multiple time horizons could indicate different levels of urgency, allowing clinicians to make decisions regarding triage, testing, and interventions for patients at risk of poor outcomes. These different horizon alerts are related and have intrinsic dependencies, which elicit multi-task learning. In this paper, we investigate approaches to properly train deep multi-task models for predicting clinical deterioration events via generating multi-horizon alerts for hospitalized patients outside the ICU, with particular application to oncology patients. Prior knowledge is used as a regularization to exploit the positive effects from the task relatedness. Simultaneously, we propose task-specific loss balancing to reduce the negative effects when optimizing the joint loss function of deep multi-task models. In addition, we demonstrate the effectiveness of the feature-generating techniques from prediction outcome interpretation. To evaluate the model performance of predicting multi-horizon deterioration alerts in a real world scenario, we apply our approaches to the EHR data from 20,700 hospitalizations of adult oncology patients. These patients' baseline high-risk status provides a unique opportunity: the application of an accurate model to an enriched population could produce improved positive predictive value and reduce false positive alerts. With our dataset, the model applying all proposed learning techniques achieves the best performance compared with common models previously developed for clinical deterioration warning.

In the article, we explore the feasibility of monitoring outpatients using Fitbit Charge HR wristbands and the potential of machine learning models to predict clinical deterioration (readmissions and death) among outpatients discharged from the hospital. We developed and piloted a data collection system in a clinical study that involved 25 heart failure patients recently discharged. The results demonstrated the feasibility of continuously monitoring outpatients using wristbands. We observed high levels of patient compliance in wearing the wristbands regularly and satisfactory yield, latency, and reliability of data collection from the wristbands to a cloud-based database. Finally, we explored a set of machine learning models to predict deterioration based on the Fitbit data. Through fivefold cross-validation, K nearest neighbor achieved the highest accuracy of 0.8667 for identifying patients at risk of deterioration using the data collected from the beginning of the monitoring. Machine learning models based on multimodal data (step, sleep, and heart rate) significantly outperformed the traditional clinical approach based on LACE index. Moreover, our proposed Weighted Samples One-Class SVM model with estimated confidence can reach high accuracy (0.9635) for predicting the deterioration using data collected within a sliding window, which indicates the potential for allowing timely intervention.

Industrial automation traditionally relies on local controllers implemented on microcontrollers or programmable logic controllers. With the emergence of edge computing, however, industrial automation evolves into a distributed two-tier computing architecture comprising local controllers and edge servers that communicate over wireless networks. Compared to local controllers, edge servers provide larger computing capacity at the cost of data loss over wireless networks. This article presents switching multitier control (SMC) to exploit edge computing for industrial control. SMC dynamically optimizes control performance by switching between local and edge controllers in response to changing network conditions. SMC employs a data-driven approach to derive switching policies based on classification models trained based on simulations while guaranteeing system stability based on an extended Simplex approach tailored for two-tier platforms. To evaluate the performance of industrial control over edge computing platforms, we have developedWCPS-EC, a real-time hybrid simulator that integrates simulated plants, real computing platforms, and real or simulated wireless networks. In a case study of an industrial robotic control system, SMC significantly outperformed both a local controller and an edge controller in face of varying data loss in a wireless network.

Industrial automation is embracing wireless sensor-actuator networks (WSANs). Despite the success of WSANs for monitoring applications, feedback control poses significant challenges due to data loss and stringent energy constraints in WSANs. Holistic control adopts a cyber-physical system approach to overcome the challenges by orchestrating network reconfiguration and process control at run time. Fundamentally, it leverages self-awareness across control and wireless boundaries to enhance the resiliency of wireless control systems. In this article, we explore efficient holistic control designs to maintain control performance while reducing the communication cost. The contributions of this work are five-fold: (1) We introduce a holistic control architecture that integrates Low-power Wireless Bus (LWB) and two control strategies, rate adaptation and self-triggered control ; (2) We present heuristics-based and optimal rate selection algorithms for rate adaptation; (3) We design novel network adaptation mechanisms to support rate adaptation and self-triggered control in a multi-hop WSAN; (4) We build WCPS-RT, a real-time network-in-the-loop simulator that integrates MATLAB/Simulink and a physical WSAN testbed to evaluate wireless control systems; (5) We empirically explore the tradeoff between communication cost and control performance in holistic control approaches. Our studies show that rate adaptation and self-triggered control offer advantages in control performance and energy efficiency, respectively, in normal operating conditions. The advantage in energy efficiency of self-triggered control, however, may diminish under harsh physical and wireless conditions due to the cost of recovering from data loss and physical disturbances.

Edge computing systems for Industrial Internet of Things (IIoT) applications require reliable and timely message delivery. Both latency discrepancies within edge clouds, and heterogeneous loss-tolerance and latency requirements pose new challenges for proper quality of service differentiation. Efficient differentiated edge computing architectures are also needed, especially when common fault-tolerant mechanisms tend to introduce additional latency, and when cloud traffic may impede local, time-sensitive message delivery. In this paper, we introduce FRAME, a fault-tolerant real-time messaging architecture. We first develop timing bounds that capture the relation between traffic/service parameters and loss-tolerance/latency requirements, and then illustrate how such bounds can support proper differentiation in a representative IIoT scenario. Specifically, FRAME leverages those timing bounds to schedule message delivery and replication actions to meet needed levels of assurance. FRAME is implemented on top of the TAO real-time event service, and we present empirical evaluations in a local edge computing test-bed and an Amazon Virtual Private Cloud. The results of those evaluations show that FRAME can efficiently meet different levels of message loss-tolerance requirements, mitigate latency penalties caused by fault recovery, and meet end-to-end soft deadlines during normal, fault-free operation.

Wireless sensor-actuator networks enable an efficient and cost-effective approach for industrial sensing and control applications. To satisfy the real-time requirement of such applications, these networks adopt centralized scheduling algorithms to optimize the real-time performance based on global information. Existing centralized algorithms mostly focus on scheduling time-triggered flows. They cannot effectively schedule event-triggered flows due to the dynamics and unpredictability of events. In this paper, we propose three fundamental centralized algorithms that reserve as few resources as possible for event-triggered flows such that the real-time performance of time-triggered flows is not affected. We then analyze their advantages and disadvantages. Based on the analysis, we combine their advantages, including those in terms of their resource requirements, into a centralized algorithm. Finally, we conduct extensive simulations based on both real topologies and random topologies. The simulations indicate that for most test cases the schedulability of our combined algorithm is close to optimal solutions.

This paper presents CaM, a holistic cache and memory bandwidth resource allocation strategy for multicore real-time systems. CaM is designed for partitioned scheduling, where tasks are mapped onto cores, and the shared cache and memory bandwidth resources are partitioned among cores to reduce resource interferences due to concurrent accesses. Based on our extension of LITMUSRT with Intel's Cache Allocation Technology and MemGuard, we present an experimental evaluation of the relationship between the allocation of cache and memory bandwidth resources and a task's WCET. Our resource allocation strategy exploits this relationship to map tasks onto cores, and to compute the resource allocation for each core. By grouping tasks with similar characteristics (in terms of resource demands) to the same core, it enables tasks on each core to fully utilize the assigned resources. In addition, based on the tasks' execution time behaviors with respect to their assigned resources, we can determine a desirable allocation that maximizes schedulability under resource constraints. Extensive evaluations using real-world benchmarks show that CaM offers near optimal schedulability performance while being highly efficient, and that it substantially outperforms existing solutions.

There is increasing interest in supporting time-critical services in cloud computing environments. Those cloud services differ from traditional hard real-time systems in three aspects. First, cloud services usually involve latency requirements in terms of probabilistic tail latency instead of hard deadlines. Second, some cloud services need to handle aperiodic requests for stochastic arrival processes instead of traditional periodic or sporadic models. Finally, the computing platform must provide performance isolation between time-critical services and other workloads. It is therefore essential to provision resources to meet different tail latency requirements. As a step towards cloud services with stochastic latency guarantees, this paper presents a stochastic response time analysis for aperiodic services following a Poisson arrival process on computing platforms that schedue time-critical services as deferrable servers. The stochastic analysis enables a service operator to provision CPU resources for aperiodic services to achieve a desired tail latency. We evaluated the method in two case studies, one involving a synthetic service and another involving a Redis service, both on a testbed based on Xen 4.10. The results demonstrate the validity and efficacy of our method in a practical setting.

Wireless sensor-actuator networks (WSANs) are gaining momentum in industrial process automation as a communication infrastructure for lowering deployment and maintenance costs. In traditional wireless control systems, the plant controller and the network manager operate in isolation, which ignores the significant influence of network reliability on plant control performance. To enhance the dependability of industrial wireless control, we propose a holistic cyber-physical management framework that employs runtime coordination between the plant control and network management. Our design includes a holistic controller that generates actuation signals to physical plants and reconfigures the WSAN to maintain the desired control performance while saving wireless resources. As a concrete example of holistic control, we design a holistic manager that dynamically reconfigures the number of transmissions in the WSAN based on online observations of physical and cyber variables. We have implemented the holistic management framework in the wireless cyber-physicalsimulator (WCPS). A systematic case study is presented based on two five-state plants and a load positioning system using a 16-node WSAN. Simulation results show that the holistic management design has significantly enhanced the dependability of the system against both wireless interferences and physical disturbances, while effectively reducing the number of wireless transmissions.

Cyber-physical systems (CPS) involve tight integration of cyber (computation) and physical domains, and both the effectiveness and correctness of a cyber-physical system application may rely on successful enforcement of constraints such as bounded latency and temporal validity subject to physical conditions. For many such systems (e.g., edge computing in the Industrial Internet of Things), it is desirable to enforce such constraints within a common middleware service (e.g., during event processing). In this article, we introduce CPEP, a new real-time middleware for cyber-physical event processing, with (1) extensible support for complex event processing operations, (2) execution prioritization and sharing, (3) enforcement of time consistency with load shedding, and (4) efficient memory management and concurrent data processing. We present the design, implementation, and empirical evaluation of CPEP and show that it can (1) support complex operations needed by many applications, (2) schedule data processing according to consumers’ priority levels, (3) enforce temporal validity, and (4) reduce processing delay and improve throughput of time-consistent events.

As the scale and density of data centers continue to grow, cost-effective data center management (DCM) is becoming a significant challenge for enterprises hosting large-scale online and cloud services. Machines need to be monitored, and the scale of operations mandates an automated management with high reliability and real-time performance. The limitations of today’s typical DCM network are many-fold. Primarily, it is a fixed wired network, and hence scaling it for a large number of servers increases its cost. In addition, with server densities increasing over recent years, this network also has to be cabled correctly and the management of this network parallels the complexity of managing a data network, since it needs to be networked with multiple switches and routers. In this article, we propose a wireless sensor network as a cost-effective networking solution for DCM while satisfying the reliability and latency performance requirements of DCM. We have developed CapNet, a real-time wireless sensor network for power capping, a time-critical DCM function for power management in a cluster of servers. CapNet employs an efficient event-driven protocol that triggers data collection only on the detection of a potential power capping event. We deploy and evaluate CapNet in a data center. Using server power traces, our experimental results on a cluster of 480 servers inside the data center show that CapNet can meet the real-time requirements of power capping. CapNet demonstrates the feasibility and efficacy of wireless sensor networks for time-critical DCM applications.

Wireless Sensor-Actuator Networks (WSANs) are being adopted as an enabling technology for Industrial Internet of Things (IIoT) in process industries. Industrial applications impose stringent requirements in reliability and real-time performance on WSANs. To enhance reliability, industrial standards, such as WirelessHART, embrace Time Slotted Channel Hopping (TSCH) that integrates channel hopping and TDMA at the MAC layer. Within a network governed by a same gateway, WirelessHART prohibits channel reuse, i.e., concurrent transmissions in the same channel, to avoid interference between concurrent transmissions. Preventing channel reuse however negatively affects real-time performance. To meet the demand for both reliability and real-time performance by industrial applications, we propose a conservative channel reuse approach designed to enhance the real-time performance while limiting its impact on reliability in WSANs. In contrast to traditional channel reuse designed to optimize performance at the cost of reliability, our conservative approach introduces channel reuse only when needed to meet the timing constraints of flows. Finally, we present an algorithm to detect reliability degradation caused by channel reuse so that channels can be reassigned to further improve reliability. Experimental results based on two physical testbeds show that our approach significantly improves real-time performance while maintaining a high degree of reliability.

Real-time virtualization is an emerging technology for embedded systems integration and latency-sensitive cloud applications. Earlier real-time virtualization platforms require offline configuration of the scheduling parameters of virtual machines (VMs) based on their worst-case workloads, but this static approach results in pessimistic resource allocation when the workloads in the VMs change dynamically. Here, we present Multi-Mode-Xen (M2-Xen), a real-time virtualization platform for dynamic real-time systems where VMs can operate in modes with different CPU resource requirements at run-time. M2-Xen has three salient capabilities: (1) dynamic allocation of CPU resources among VMs in response to their mode changes, (2) overload avoidance at both the VM and host levels during mode transitions, and (3) fast mode transitions between different modes. M2-Xen has been implemented within Xen 4.8 using the real-time deferrable server (RTDS) scheduler. Experimental results show that M2-Xen maintains real-time performance in different modes, avoids overload during mode changes, and performs fast mode transitions.

Objective: To review and analyze the literature to determine whether wearable technologies can predict health outcomes. Materials and methods: We queried Ovid Medline 1946 -, Embase 1947 -, Scopus 1823 -, the Cochrane Library, clinicaltrials.gov 1997 - April 17, 2018, and IEEE Xplore Digital Library and Engineering Village through April 18, 2018, for studies utilizing wearable technology in clinical outcome prediction. Studies were deemed relevant to the research question if they involved human subjects, used wearable technology that tracked a health-related parameter, and incorporated data from wearable technology into a predictive model of mortality, readmission, and/or emergency department (ED) visits. Results: Eight unique studies were directly related to the research question, and all were of at least moderate quality. Six studies developed models for readmission and two for mortality. In each of the eight studies, data obtained from wearable technology were predictive of or significantly associated with the tracked outcome. Discussion: Only eight unique studies incorporated wearable technology data into predictive models. The eight studies were of moderate quality or higher and thereby provide proof of concept for the use of wearable technology in developing models that predict clinical outcomes. Conclusion: Wearable technology has significant potential to assist in predicting clinical outcomes, but needs further study. Well-designed clinical trials that incorporate data from wearable technology into clinical outcome prediction models are required to realize the opportunities of this advancing technology.

In recent years, there has been significant interest in developing real-time schedulers for parallel tasks. Most of that research has concentrated on idealized task models where tasks do not access any shared resources protected with locks. In this paper, we consider the problem of scheduling parallel tasks which experience contention due to shared resources. In particular, we provide a schedulability test for federated scheduling by deriving blocking time analyses for parallel tasks that access shared resources protected by FIFO-ordered and priority-ordered spin locks. Our numerical evaluation on randomly generated task sets indicates that priority-ordered locks generally provide better schedulability results than FIFO-ordered locks. We also incorporated both FIFO-ordered and priority-ordered spin lock implementations into a federated scheduling platform, which is able to schedule parallel tasks written with OpenMP. Via empirical evaluations, we found that priority-ordered locks also have better performance than FIFO-ordered locks in practice.

Industrial automation has emerged as an important application of wireless sensor-actuator networks (WSANs). To meet stringent reliability requirements of industrial applications, industrial standards such as WirelessHART adopt Time Slotted Channel Hopping (TSCH) as its MAC protocol. Since every link hops through all the channels used in TSCH, a straightforward policy to ensure reliability is to retain a link in the network topology only if it is reliable in all channels used. However, this policy has surprising side effects. While using more channels may enhance reliability due to channel diversity, more channels may also reduce the number of links and route diversity in the network topology. We empirically analyze the impact of channel selection on network topology, routing, and scheduling on a 52-node WSAN testbed. We observe inherent tradeoff between channel diversity and route diversity in channel selection, where using an excessive number of channels may negatively impact routing and scheduling. We propose novel channel and link selection strategies to improve route diversity and network schedulability. Experimental results on two different testbeds show that our algorithms can drastically improve routing and scheduling of industrial WSANs.

Cyber-physical applications are subject to temporal validity constraints, which must be enforced in addition to traditional QoS requirements such as bounded latency. For many such systems (e.g., automotive and edge computing in the Industrial Internet of Things) it is desirable to enforce such constraints within a common middleware service (e.g., during event processing). In this paper, we introduce CPEP, a new real-time middleware for cyber-physical event processing, with (1) extensible support for complex data processing operations, (2) execution prioritization and sharing, (3) enforcement of absolute time consistency with load shedding, and (4) efficient memory management and concurrent data processing. We present the design, implementation, and empirical evaluation of CPEP and show that it can (1) support complex operations needed by many applications, (2) schedule data processing according to consumers' QoS requirements, (3) enforce temporal validity, and (4) reduce processing delay and improve throughput of temporally valid events.

While trains traditionally relied on field bus to support real-time control applications, next-generation trains are moving toward Ethernet as an integrated, high-bandwidth communication infrastructure for real-time control and best-effort consumer traffic. Time-Triggered Ethernet (TT-Ethernet) is a promising technology for train networks because of its capability to achieve deterministic latencies for real-time applications based on pre-computed transmission schedules. However, the deterministic scheduling approach of TT-Ethernet faces significant challenges in handling scheduling uncertainties caused by switch failures and legacy end devices in train networks. Due to the physical constraints on trains, train networks deal with switch failures by bypassing failed switches using a short circuiting mechanism. Unfortunately, this mechanism incurs scheduling errors as frames bypassing the failed switch may arrive ahead of the pre-computed schedule, resulting in early, unexpected, and out of order arrivals. Furthermore, as trains evolve from traditional communication technologies to TT-Ethernet, the network must support legacy end devices that may generate frames at times unknown to the TT-Ethernet. We propose a novel traffic shaping approach to deal with scheduling uncertainties in TT-Ethernet. The traffic shaper of a TT-Ethernet switch buffers early frames and then releases them at their pre-scheduled arrive time. Furthermore, we devise an efficient buffer management method for the traffic shaper in face of fault scenarios. Finally, we use the traffic shaper to integrate legacy devices into TT-Ethernet. We have implemented the traffic shaping approach in a 24-port TT-Ethernet switch specifically designed for train networks. Experiments show the traffic shaping strategy can effectively deal with scheduling uncertainties incurred by switch failures and legacy devices.

Low-Power Wide-Area Network (LPWAN) heralds a promising class of technology to overcome the range limits and scalability challenges in traditional wireless sensor networks. Recently proposed Sensor Network over White Spaces (SNOW) technology is particularly attractive due to the availability and advantages of TV spectrum in long-range communication. This paper proposes a new design of SNOW that is asynchronous, reliable, and robust. It represents the first highly scalable LPWAN over TV white spaces to support reliable, asynchronous, bi-directional, and concurrent communication between numerous sensors and a base station. This is achieved through a set of novel techniques. This new design of SNOW has an OFDM based physical layer that adopts robust modulation scheme and allows the base station using a single antenna-radio (1) to send different data to different nodes concurrently and (2) to receive concurrent transmissions made by the sensor nodes asynchronously. It has a lightweight MAC protocol that (1) efficiently implements per-transmission acknowledgments of the asynchronous transmissions by exploiting the adopted OFDM design; (2) combines CSMA/CA and location-aware spectrum allocation for mitigating hidden terminal effects, thus enhancing the flexibility of the nodes in transmitting asynchronously. Hardware experiments through deployments in three radio environments - in a large metropolitan city, in a rural area, and in an indoor environment - as well as large-scale simulations demonstrated that the new SNOW design drastically outperforms other LPWAN technologies in terms of scalability, energy, and latency.

Despite over a decade of research and development in fall detection systems, accurate and reliable systems in use are few. The existing fall detection approaches leave three major challenges unsolved: (1) insufficient fall data for model training process, (2) unreliable labeling of ground truth, and (3) resorting to artificial falls to model falls. In this paper we highlight these challenges in a clinical study with community-dwelling adults. The data collected from the real world reveal significant differences between artificial falls and actual falls, and also to illuminate the limitations of existing algorithms. We further make recommendations for future work, based on the challenges, experience, and lessons we learned from this study.

Wireless sensor–actuator networks (WSANs) offer an appealing communication technology for process automation applications to incorporate the Internet of Things (IoT). In contrast to other IoT applications, process automation poses unique challenges for industrial WSAN due to its critical demands on reliable and real-time communication. While industrial WSANs have received increasing attention in the research community recently, most published results to date have focused on the theoretical aspects and were evaluated based on simulations. There is a critical need for experimental research on this important class of WSANs. We developed an experimental testbed by implementing several key network protocols of WirelessHART, an open standard for WSANs that has been widely adopted in the process industries based on the HART. We then performed a series of empirical studies showing that graph routing leads to significant improvement over source routing in terms of worst-case reliability, but at the cost of longer latency and higher energy consumption. It is therefore important to employ graph routing algorithms specifically designed to optimize latency and energy efficiency. Our studies also suggest that channel hopping can mitigate the burstiness of transmission failures; a larger channel distance can reduce consecutive transmission failures over links sharing a common receiver. Based on these insights, we developed a novel channel hopping algorithm that utilizes far away channels for transmissions. Furthermore, it prevents links sharing the same destination from using channels with strong correlations. Our experimental results demonstrate that our algorithm can significantly improve network reliability and energy efficiency.

The AMC-IA mixed-criticality scheduling analysis was proposed as an improvement to the AMC-MAX adaptive mixed-criticality scheduling analysis. However, we have identified several necessary corrections to the AMC-IA analysis. In this article, we motivate and describe those corrections, and discuss and illustrate why the corrected AMC-IA analysis cannot be shown to outperform AMC-MAX.

Interactive web services increasingly drive critical business workloads such as search, advertising, games, shopping, and finance. Whereas optimizing parallel programs and distributed server systems have historically focused on average latency and throughput, the primary metric for interactive applications is instead consistent responsiveness, i.e., minimizing the number of requests that miss a target latency. This paper is the first to show how to generalize work-stealing, which is traditionally used to minimize the makespan of a single parallel job, to optimize for a target latency in interactive services with multiple parallel requests.

A mixed-criticality system comprises safety-critical and non-safety-critical tasks sharing a computational platform. Thus, different levels of assurance are required by different tasks in terms of real-time performance. In addition, as the computational demands of real-time tasks are increasing, tasks may require internal parallelism in order to complete within stringent deadlines. In this paper, we consider the problem of mixed-criticality scheduling of parallel real-time tasks and propose a novel mixed-criticality federated scheduling (MCFS) algorithm for parallel real-time tasks based on the directed acyclic graph model. MCFS is based on federated intuition for scheduling parallel real-time tasks. It strategically assigns cores and virtual deadlines to tasks in order to achieve good schedulability. For task sets with only high-utilization tasks (utilization >= 1), we prove that MCFS provides a capacity augmentation bound of 3.41 and 3.73 for dual-criticality and multi- criticality, respectively. We also show that MCFS have capacity augmentation bounds of 3.67m/(m-1) for a dual-criticality system with both high- and low-utilization tasks, which to our knowledge is the first such performance bound for parallel mixed-criticality tasks. We also present an implementation of an MCFS runtime system in Linux that supports parallel programs written in OpenMP. We conduct both numerical and empirical experiments to demonstrate the practicality of our MCFS approach.

Recent years have witnessed the convergence of two important trends in real-time systems: growing computational demand of applications and the adoption of processors with more cores. As real-time applications now need to exploit parallelism to meet their real-time requirements, they face a new challenge of scaling up computations on a large number of cores. Randomized work stealing has been adopted as a highly scalable scheduling approach for general-purpose computing. In work stealing, each core steals work from a randomly chosen core in a decentralized manner. Compared to centralized greedy schedulers, work stealing may seem unsuitable for real-time computing due to the non-predictable nature of random stealing. Surprisingly, our experiments with benchmark programs found that random work stealing (in Cilk Plus) delivers tighter distributions in task execution times than a centralized greedy scheduler (in GNU OpenMP).To support scalable soft real-time computing, we develop Real-Time Work-Stealing platform (RTWS), a real-time extension to the widely used Cilk Plus concurrency platform. RTWS employs federated scheduling to allocate cores to multiple parallel real-time tasks offline, while leveraging the work stealing scheduler to schedule each task on its dedicated cores online. RTWS supports parallel programs written in Cilk Plus and requires only task parameters that can be readily measured using existing Cilk Plus tools. Experimental results show that RTWS outperforms Real-Time OpenMP in term of deadline miss ratio, relative response time and resource efficiency on a 32-core system.

Wireless sensor networks (WSNs) face significant scalability challenges due to the proliferation of wide-area wireless monitoring and control systems that require thousands of sensors to be connected over long distances. Due to their short communication range, existing WSN technologies such as those based on IEEE 802.15.4 form many-hop mesh networks complicating the protocol design and network deployment. To address this limitation, we propose a scalable sensor network architecture - called Sensor Network Over White Spaces (SNOW) - by exploiting the TV white spaces. Many WSN applications need low data rate, low power operation, and scalability in terms of geographic areas and the number of nodes. The long communication range of white space radios significantly increases the chances of packet collision at the base station. We achieve scalability and energy efficiency by splitting channels into narrowband orthogonal subcarriers and enabling packet receptions on the subcarriers in parallel with a single radio. The physical layer of SNOW is designed through a distributed implementation of OFDM that enables distinct orthogonal signals from distributed nodes. Its MAC protocol handles subcarrier allocation among the nodes and transmission scheduling. We implement SNOW in GNU radio using USRP devices. Experiments demonstrate that it can correctly decode in less than 0.1ms multiple packets received in parallel at different subcarriers, thus drastically enhancing the scalability of WSN.

With recent adoption of wireless sensor-actuator networks (WSANs) in industrial automation, industrial wireless control systems have emerged as a frontier of cyber-physical systems. Despite their success in industrial monitoring applications, existing WSAN technologies face significant challenges in supporting control systems due to their lack of real-time performance and dynamic wireless conditions in industrial plants. This article reviews a series of recent advances in real-time WSANs for industrial control systems: 1) real-time scheduling algorithms and analyses for WSANs; 2) implementation and experimentation of industrial WSAN protocols; 3) cyber-physical codesign of wireless control systems that integrate wireless and control designs; and 4) a wireless cyber-physical simulator for codesign and evaluation of wireless control systems. This article concludes by highlighting research directions in industrial cyber-physical systems.

Clouds have become appealing platforms for not only general-purpose applications, but also real-time ones. However, current clouds cannot provide real-time performance to virtual machines (VMs). We observe the demand and the advantage of co-hosting real-time (RT) VMs with non-real-time (regular) VMs in a same cloud. RT VMs can benefit from the easily deployed, elastic resource provisioning provided by the cloud, while regular VMs effectively utilize remaining resources without affecting the performance of RT VMs through proper resource management at both the cloud and the hyper visor levels. This paper presents RT-Open Stack, a cloud CPU resource management system for co-hosting real-time and regular VMs. RT-Open Stack entails three main contributions: (1) integration of a real-time hyper visor (RT-Xen) and a cloud management system (Open Stack) through a real-time resource interface, (2) a real-time VM scheduler to allow regular VMs to share hosts with RT VMs without interfering the real-time performance of RT VMs, and (3) a VM-to-host mapping strategy that provisions real-time performance to RT VMs while allowing effective resource sharing with regular VMs. Experimental results demonstrate that RT-Open Stack can effectively improve the real-time performance of RT VMs while allowing regular VMs to fully utilize the remaining CPU resources.

Thermal control is critical for real-time systems as overheated processors can result in serious performance degradation or even system breakdown due to hardware throttling. The major challenges in thermal control for real-time systems are (i) the need to enforce both real-time and thermal constraints; (ii) uncertain system dynamics; and (iii) thermal sensor noise. Previous studies have resolved the first two, but the practical issue of sensor noise has not been properly addressed yet. In this paper, we introduce a novel thermal control algorithm that can appropriately handle thermal sensor noise. Our key observation is that even a small zero-mean sensor noise can induce a significant steady-state error between the target and the actual temperature of a processor. This steady-state error is contrary to our intuition that zero-mean sensor noise induces zero-mean fluctuations. We show that an intuitive attempt to resolve this unusual situation is not effective at all. By a rigorous approach, we analyze the underlying mechanism and quantify the noised-induced error in a closed form in terms of noise statistics and system parameters. Based on our analysis, we propose a simple and effective solution for eliminating the error and maintaining the desired processor temperature. Through extensive simulations, we show the advantages of our proposed algorithm, referred to as Thermal Control under Utilization Bound with Virtual Saturation (TCUB-VS).

As virtualization technology becomes ever more capable, large-scale distributed applications are increasingly deployed in virtualized environments such as data centers and computational clouds. Many large-scale applications have soft real-time requirements and benefit from low and predictable latency, even in the presence of diverse traffic patterns between virtualized hosts. In this paper, we examine the policies and mechanisms affecting communication latency between virtual machines based on the Xen platform, and identify limitations that could result in long or unpredictable network traffic latencies. To address these limitations, we propose VATC, aVirtualization-Aware Traffic Controlframework for prioritizing network traffic in virtualized hosts. Results of our experiments show how and why VATC can improve predictability and reduce delay for latency sensitive applications, while introducing limited overhead.

Wireless sensor-actuator networks are gaining ground as the communication infrastructure for process monitoring and control. Industrial applications demand a high degree of reliability and real-time guarantees in communication. Because wireless communication is susceptible to transmission failures in industrial environments, industrial wireless standards such as WirelessHART adopt reliable graph routing to handle transmission failures through retransmissions and route diversity. While these mechanisms are critical for reliable communication, they introduce substantial challenges in analyzing the schedulability of real-time flows. This paper presents the first worst-case end-to-end delay analysis for periodic real-time flows under reliable graph routing. The proposed analysis can be used to quickly assess the schedulability of real-time flows with stringent requirements on both reliability and latency. We have evaluated our schedulability analysis against experimental results on a wireless testbed of 69 nodes as well as simulations. Both experimental results and simulations show that our delay bounds are safe and enable effective schedulability tests under reliable graph routing.

WirelessHART is a new standard specifically designed for real-time and reliable communication between sensor and actuator devices for industrial process monitoring and control applications. End-to-end communication delay analysis for WirelessHART networks is required to determine the schedulability of real-time data flows from sensors to actuators for the purpose of acceptance test or workload adjustment in response to network dynamics. In this paper, we consider a network model based on WirelessHART, and map the scheduling of real-time periodic data flows in the network to real-time multiprocessor scheduling. We then exploit the response time analysis for multiprocessor scheduling and propose a novel method for the delay analysis that establishes an upper bound of the end-to-end communication delay of each real-time flow in the network. Simulation studies based on both random topologies and real network topologies of a$74$-node physical wireless sensor network testbed demonstrate that our analysis provides safe and reasonably tight upper bounds of the end-to-end delays of real-time flows, and hence enables effective schedulability tests for WirelessHART networks.

This paper considers the scheduling of parallel real-time tasks with implicit deadlines. Each parallel task is characterized as a general directed acyclic graph (DAG). We analyze three different real-time scheduling strategies: two well known algorithms, namely global earliest-deadline-first and global rate-monotonic, and one new algorithm, namely federated scheduling. The federated scheduling algorithm proposed in this paper is a generalization of partitioned scheduling to parallel tasks. In this strategy, each high-utilization task (utilization ≥ 1) is assigned a set of dedicated cores and the remaining low-utilization tasks share the remaining cores. We prove capacity augmentation bounds for all three schedulers. In particular, we show that if on unit-speed cores, a task set has total utilization of at most m and the critical-path length of each task is smaller than its deadline, then federated scheduling can schedule that task set on m cores of speed 2, G-EDF can schedule it with speed 3 + v5/2 2.618, and G-RM can schedule it with speed 2 + v3 3.732. We also provide lower bounds on the speedup and show that the bounds are tight for federated scheduling and G-EDF when m is sufficiently large.

Real-time hybrid simulation (RTHS) is an important tool in the design and testing of civil and mechanical structures when engineers and scientists wish to understand the performance of an isolated component within the context of a larger structure. Performing full-scale physical experimentation with a large structure can be prohibitively expensive. Instead, a hybrid testing framework connects part of a physical structure within a closed loop (through sensors and actuators) to a numerical simulation of the rest of the structure. If we wish to understand the dynamic response of the combined structure, this testing must be done in real-time, which significantly restricts both the size of the simulation and the rate at which it can be conducted.

Recent years have witnessed two major trends in the development of complex real-time embedded systems. First, to reduce cost and enhance flexibility, multiple systems are sharing common computing platforms via virtualization technology, instead of being deployed separately on physically isolated hosts. Second, multicore processors are increasingly being used in real-time systems. The integration of real-time systems as virtual machines (VMs) atop common multicore platforms raises significant new research challenges in meeting the real-time performance requirements of multiple systems. This paper advances the state of the art in real-time virtualization by designing and implementing RT-Xen 2.0, a new real-time multicore VM scheduling framework in the popular Xen virtual machine monitor (VMM). RT-Xen 2.0 realizes a suite of real-time VM scheduling policies spanning the design space. We implement both global and partitioned VM schedulers; each scheduler can be configured to support dynamic or static priorities and to run VMs as periodic or deferrable servers. We present a comprehensive experimental evaluation that provides important insights into real-time scheduling on virtualized multicore platforms: (1) both global and partitioned VM scheduling can be implemented in the VMM at moderate overhead; (2) at the VMM level, while compositional scheduling theory shows partitioned EDF (pEDF) is better than global EDF (gEDF) in providing schedulability guarantees, in our experiments their performance is reversed in terms of the fraction of workloads that meet their deadlines on virtualized multi-core platforms; (3) at the guest OS level, pEDF requests a smaller total VCPU bandwidth than gEDF based on compositional scheduling analysis, and therefore using pEDF at the guest OS level leads to more schedulable workloads in our experiments; (4) a combination of pEDF in the guest OS and gEDF in the VMM -- configured with deferrable server -- leads to the highest fraction of schedulable task sets compared to other real-time VM scheduling policies; and (5) on a platform with a shared last-level cache, the benefits of global scheduling outweigh the cache penalty incurred by VM migration.

The largest source of energy consumption in buildings is heating, ventilation, and air conditioning (HVAC). For an HVAC system to provide comfort and minimize energy consumption, it is crucial to understand the spatiotemporal thermal dynamics, especially in large open spaces. To optimize HVAC control, it is important to establish accurate dynamic thermal models. For this purpose, we constructed a real-world test bed by instrumenting an HVAC-controller auditorium using multiple types of sensors. Based on the dataset, we develop and evaluate a novel data-driven approach to model the complex thermal dynamics in a large space through a combination of data clustering and system identification techniques. Real-world data shows that our approach achieves low estimation errors. Our modeling approach therefore provides a practical foundation for HVAC control and optimization for large open spaces.

Industry is adopting Wireless Sensor-Actuator Networks (WSANs) as the communication infrastructure for process control applications. To meet the stringent real-time performance requirements of control systems, there is a critical need for fast end-to-end delay analysis for real-time flows that can be used for online admission control. This paper presents a new end-to-end delay analysis for periodic flows whose transmissions are scheduled based on the Earliest Deadline First (EDF) policy. Our analysis comprises novel techniques to bound the communication delays caused by channel contention and transmission conflicts in a WSAN. Furthermore, we propose a technique to reduce the pessimism in admission control by iteratively tightening the delay bounds for flows with short deadlines. Experiments on a WSAN testbed and simulations demonstrate the effectiveness of our analysis for online admission control of real-time flows.

Federated scheduling is a strategy to schedule parallel real-time tasks: It allocates a dedicated cluster of cores to each high-utilization task (utilization ≥ 1); It uses a multiprocessor scheduling algorithm to schedule and execute all low-utilization tasks sequentially, on a shared cluster of the remaining cores. Prior work has shown that federated scheduling has the best known capacity augmentation bound of 2 for parallel tasks with implicit deadlines. In this paper, we explore the soft real-time performance of federated scheduling and address average-case workloads instead of worst-case ones. In particular, we consider stochastic tasks — tasks for which execution time and critical-path length are random variables. In this case, we use bounded expected tardiness as the schedulability criterion. We define a stochastic capacity augmentation bound and prove that federated scheduling algorithms guarantee the same bound of 2 for stochastic tasks. We present three federated mapping algorithms with different complexities for core allocation. All of them guarantee bounded expected tardiness and provide the same capacity augmentation bound. In practice, however, we expect them to provide different performance, both in terms of the task sets they can schedule and the actual tardiness they guarantee. Therefore, we present numerical evaluations using randomly generated task sets to examine the practical differences between the three algorithms.

Data center management (DCM) is increasingly becoming a significant challenge for enterprises hosting large scale online and cloud services. Machines need to be monitored, and the scale of operations mandates an automated management with high reliability and real-time performance. Existing wired networking solutions for DCM come with high cost. In this paper, we propose a wireless sensor network as a cost-effective networking solution for DCM while satisfying the reliability and latency performance requirements of DCM. We have developed Cap Net, a real-time wireless sensor network for power capping, a time-critical DCM function for power management in a cluster of servers. Cap Net employs an efficient event-driven protocol that triggers data collection only upon the detection of a potential power capping event. We deploy and evaluate Cap Net in a data center. Using server power traces, our experimental results on a cluster of 480 servers inside the data center show that Cap Net can meet the real-time requirements of power capping. Cap Net demonstrates the feasibility and efficacy of wireless sensor networks for time-critical DCM applications.

Traditional fixed-priority scheduling analysis for periodic and sporadic task sets is based on the assumption that all tasks are equally critical to the correct operation of the system. Therefore, every task has to be schedulable under the chosen scheduling policy, and estimates of tasks' worst-case execution times must be conservative in case a task runs longer than is usual. To address the significant underutilization of a system's resources under normal operating conditions that can arise from these assumptions, several mixed-criticality scheduling approaches have been proposed. However, to date, there have been few quantitative comparisons of system schedulability or runtime overhead for the different approaches. In this article, we present a side-by-side implementation and evaluation of the known mixed-criticality scheduling approaches, for periodic and sporadic mixed-criticality tasks on uniprocessor systems, under a mixed-criticality scheduling model that is common to all these approaches. To make a fair evaluation of mixed-criticality scheduling, we also address previously open issues and propose modifications to improve particular approaches. Our empirical evaluations demonstrate that user-space implementations of mechanisms to enforce different mixed-criticality scheduling approaches can be achieved atop Linux without kernel modification, with reasonably low (but in some cases nontrivial) overhead for mixed-criticality real-time task sets.

With the advent of industrial standards such as WirelessHART, process industries are now gravitating towards wireless control systems. Due to limited bandwidth in a wireless network shared by multiple control loops, it is critical to optimize the overall control performance. In this article, we address the scheduling-control co-design problem of determining the optimal sampling rates of feedback control loops sharing a WirelessHART network. The objective is to minimize the overall control cost while ensuring that all data flows meet their end-to-end deadlines. The resulting constrained optimization based on existing delay bounds for WirelessHART networks is challenging since it is nondifferentiable, nonlinear, and not in closed-form. We propose four methods to solve this problem. First, we present a subgradient method for rate selection. Second, we propose a greedy heuristic that usually achieves low control cost while significantly reducing the execution time. Third, we propose a global constrained optimization algorithm using a simulated annealing (SA) based penalty method. We study SA method under both constant factor penalty and adaptive penalty. Finally, we formulate rate selection as a differentiable convex optimization problem that provides a quick solution through a convex optimization technique. This is based on a new delay bound that is convex and differentiable, and hence simplifies the optimization problem. We study both the gradient descent method and the interior point method to solve it. We evaluate all methods through simulations based on topologies of a 74-node wireless sensor network testbed. The subgradient method is disposed to incur the longest execution time as well as the highest control cost among all methods. Among the SA-based constant penalty method, the greedy heuristic, and the gradient descent method, the first two represent the opposite ends of the tradeoff between control cost and execution time, while the third one hits the balance between the two. We further observe that the SA based adaptive penalty method is superior to the constant penalty method, and that the interior point method is superior to the gradient method. Thus, the interior point method and the SA-based adaptive penalty method are the two most effective approaches for rate selection. While both methods are competitive against each other in terms of control cost, the interior point method is significantly faster than the penalty method. As a result, the interior point method upon convex relaxation is more suitable for online rate adaptation than the SA based adaptive penalty method due to their significant difference in run-time efficiency.

The nine papers in this special issue cover multiple aspects of emerging wireless body area networks (WBANs) for ubiquitous healthcare.

Our deteriorating civil infrastructure faces the critical challenge of long-term structural health monitoring for damage detection and localization. In contrast to existing research that often separates the designs of wireless sensor networks and structural engineering algorithms, this paper proposes a cyber-physical codesign approach to structural health monitoring based on wireless sensor networks. Our approach closely integrates 1) flexibility-based damage localization methods that allow a tradeoff between the number of sensors and the resolution of damage localization, and 2) an energy-efficient, multilevel computing architecture specifically designed to leverage the multiresolution feature of the flexibility-based approach. The proposed approach has been implemented on the Intel Imote2 platform. Experiments on a simulated truss structure and a real full-scale truss structure demonstrate the system's efficacy in damage localization and energy efficiency.

Recently, multi-core processors have become mainstream in processor design. To take full advantage of multi-core processing, computation-intensive real-time systems must exploit intra-task parallelism. In this paper, we address the problem of real-time scheduling for a general model of deterministic parallel tasks, where each task is represented as a directed acyclic graph (DAG) with nodes having arbitrary execution requirements. We prove processor-speed augmentation bounds for both preemptive and non-preemptive real-time scheduling for general DAG tasks on multi-core processors. We first decompose each DAG into sequential tasks with their own release times and deadlines. Then we prove that these decomposed tasks can be scheduled using preemptive global EDF with a resource augmentation bound of$4$. This bound is as good as the best known bound for more restrictive models, and is the first for a general DAG model. We also prove that the decomposition has a resource augmentation bound of$4$plus a constant non-preemption overhead for non-preemptive global EDF scheduling. To our knowledge, this is the first resource augmentation bound for non-preemptive scheduling of parallel tasks. Finally, we evaluate our analytical results through simulations that demonstrate that the derived resource augmentation bounds are safe in practice.

Interference between concurrent transmissions can cause severe performance degradation in wireless sensor networks (WSNs). While multiple channels available in WSN technology such as IEEE 802.15.4 can be exploited to mitigate interference, channel allocation can have a significant impact on the performance of multi-channel communication. This paper proposes a set of distributed protocols for channel allocation in WSNs with theoretical bounds. We first consider the problem of minimizing the number of channels needed to remove interference in a WSN, and propose both receiver-based and link-based distributed channel allocation protocols. Then, for WSNs with an insufficient number of channels, we formulate a fair channel allocation problem whose objective is to minimize the maximum interference (MinMax) experienced by any transmission link in the network. We prove that MinMax channel allocation is NP-hard, and propose a distributed link-based MinMax channel allocation protocol. Finally, we propose a distributed protocol for link scheduling based on MinMax channel allocation that creates a conflict-free schedule for transmissions. The proposed decentralized protocols are efficient, scalable, and adaptive to channel condition and network dynamics. Simulations based on the topologies and data traces collected from a WSN testbed of 74 TelosB motes have shown that our channel allocation protocols significantly outperform a state-of-the-art channel allocation protocol.

As multicore processors become ever more prevalent, it is important for real-time programs to take advantage of intra-task parallelism in order to support computation-intensive applications with tight deadlines. We prove that a Global Earliest Deadline First (GEDF) scheduling policy provides a capacity augmentation bound of 4-2/m and a resource augmentation bound of 2-1/m for parallel tasks in the general directed a cyclic graph model. For the proposed capacity augmentation bound of 4-2/m for implicit deadline tasks under GEDF, we prove that if a task set has a total utilization of at most m/(4-2/m) and each task's critical path length is no more than 1/(4-2/m) of its deadline, it can be scheduled on a machine with m processors under GEDF. Our capacity augmentation bound therefore can be used as a straightforward schedulability test. For the standard resource augmentation bound of 2-1/m for arbitrary deadline tasks under GEDF, we prove that if an ideal optimal scheduler can schedule a task set on m unit-speed processors, then GEDF can schedule the same task set on m processors of speed 2-1/m. However, this bound does not lead to a schedulabilty test since the ideal optimal scheduler is only hypothetical and is not known. Simulations confirm that the GEDF is not only safe under the capacity augmentation bound for various randomly generated task sets, but also performs surprisingly well and usually outperforms an existing scheduling technique that involves task decomposition.

Low Power Listening (LPL) is a common MAC-layer technique for reducing energy consumption in wireless sensor networks, where nodes periodically wakeup to sample the wireless channel to detect activity. However, LPL is highly susceptible to false wakeups caused by environmental noise being detected as activity on the channel, causing nodes to spuriously wakeup in order to receive nonexistent transmissions. In empirical studies in residential environments, we observe that the false wakeup problem can significantly increase a node's duty cycle, compromising the benefit of LPL. We also find that the energy-level threshold used by the Clear Channel Assessment (CCA) mechanism to detect channel activity has a significant impact on the false wakeup rate. We then design AEDP, an adaptive energy detection protocol for LPL, which dynamically adjusts a node's CCA threshold to improve network reliability and duty cycle based on application-specified bounds. Empirical experiments in both controlled tests and real-world environments showed AEDP can effectively mitigate the impact of noise on radio duty cycles, while maintaining satisfactory link reliability.

As computer hardware becomes increasingly powerful, there is an ongoing trend towards integrating QoS-critical systems as virtual machines (domains) on a common, virtualized computing platform. Given the lower latency of local inter-domain communication (IDC) on the same host (compared to inter-host communication), system administrators may preferably colocate domains so that they can communicate locally. When multiple IDC flows contend on the same host, it is important to properly prioritize IDC flows among domains to meet their respective QoS requirements. This paper examines the limitations of IDC in Xen, a widely used open-source virtual machine monitor (VMM) that recently has been extended to support real-time domain scheduling. We find that both the VMM scheduler and the manager domain can significantly impact IDC QoS under different conditions, and show that improving the VMM scheduler alone cannot effectively prevent priority inversion for local IDC. To address those limitations, we present RTCA, a Real-Time Communication Architecture within the manager domain in Xen, along with experimental results that demonstrate the latency of high-priority IDC can be improved dramatically from ms to μs by a combination of the RTCA and a real-time VMM scheduler.

The multi-core revolution presents both opportunities and challenges for real-time systems. Parallel computing can yield significant speedup for individual tasks (enabling shorter deadlines, or more computation within the same deadline), but unless managed carefully may add complexity and overhead that could potentially wreck real-time performance. There is little experience to date with the design and implementation of realtime systems that allow parallel tasks, yet the state of the art cannot progress without the construction of such systems. In this work we describe the design and implementation of a scheduler and runtime dispatcher for a new concurrency platform, RT-OpenMP, whose goal is the execution of real-time workloads with intra-task parallelism.

The integration of wireless sensors with mobile phones is gaining momentum as an enabling platform for numerous emerging applications. These mobile systems face dynamic environments where both application requirements and ambient wireless conditions change frequently. Despite the existence of many MAC protocols, none can provide optimal characteristics along multiple dimensions, especially when the conditions are frequently changing. Instead of pursuing a one-MAC-fit-all approach we present the Self-Adapting MAC Layer (SAML) that dynamically selects and switches MAC protocols to gain the desired characteristics in response to changes in ambient conditions and application requirements. SAML comprises (1) a Reconfigurable MAC Architecture (RMA) that can switch to different MAC protocols at run time and (2) a learning-based MAC Selection Engine that selects the protocol most suitable for the current condition and requirements. To the application SAML appears as a traditional MAC layer and realizes its benefits through a simple API for the mobile applications. We have implemented SAML in TinyOS 2.x and built three prototypes containing up to five MACs. We evaluate the system in controlled tests and real-world environments using a new gateway device that integrates a 802.15.4 radio with Android phones. Our experimental results show that SAML can effectively adapt MAC layer behavior to meet varying application requirements in dynamic environments through judicious selection and efficient switching of MAC protocols.

Multicore processors are becoming ubiquitous, and it is becoming increasingly common to run multiple real-time systems on a shared multicore platform. While this trend helps to reduce cost and to increase performance, it also makes it more challenging to achieve timing guarantees and functional isolation. One approach to achieving functional isolation is to use virtualization. However, virtualization also introduces many challenges to the multicore timing analysis, for instance, the overhead due to cache misses becomes harder to predict, since it depends not only on the direct interference between tasks but also on the indirect interference between virtual processors and the tasks executing on them. In this paper, we present a cache-aware compositional analysis technique that can be used to ensure timing guarantees of components scheduled on a multicore virtualization platform. Our technique improves on previous multicore compositional analyses by accounting for the cache-related overhead in the components' interfaces, and it addresses the new virtualization-specific challenges in the overhead analysis. To demonstrate the utility of our technique, we report results from an extensive evaluation based on randomly generated workloads.

Recent years have seen the emergence of wireless cyber-physical systems that must support real-time queries of physical environments through wireless sensor networks. This paper proposes Real-Time Query Scheduling (RTQS), a novel approach to conflict-free transmission scheduling for real-time queries in wireless sensor networks. First, we show that there is an inherent tradeoff between latency and real-time capacity in query scheduling. We then present three new real-time schedulers. The nonpreemptive query scheduler supports high real-time capacity but cannot provide low response times to high-priority queries due to priority inversions. The preemptive query scheduler eliminates priority inversions at the cost of reduced capacity. The slack stealing query scheduler combines the benefits of the preemptive and nonpreemptive schedulers to improve the capacity while meeting the end-to-end deadlines of queries. We provide schedulability analysis for each scheduler. The analysis and advantages of our approach are validated through NS2 simulations.

Home area networks (HANs) consisting of wireless sensors have emerged as the enabling technology for important applications such as smart energy. These applications impose unique network management constraints, requiring low data rates but high network reliability in the face of unpredictable wireless environments. This paper presents two in-depth empirical studies on wireless channels in real homes, providing key design guidelines for meeting the network management constraints of HAN applications. The spectrum study analyzes spectrum usage in the 2.4 GHz band where HANs based on the IEEE 802.15.4 standard must coexist with existing wireless devices. We characterize the ambient wireless environment in six apartments through passive spectrum analysis across the entire 2.4 GHz band over seven days in each apartment. We find that the wireless conditions in these residential environments are much more complex and varied than in a typical office environment. Moreover, while 802.11 signals play a significant role in spectrum usage, there also exists non-negligible noise from non-802.11 devices. The multi-channel link study measures the reliability of different 802.15.4 channels through active probing with motes in ten apartments. We find that there is not always a persistently reliable channel over 24 hours, and that link reliability does not exhibit cyclic behavior at daily or weekly timescales. Nevertheless, reliability can be maintained through infrequent channel hopping, suggesting dynamic channel hopping as a key tool for meeting the network management requirements of HAN applications. Our empirical studies provide important guidelines and insights in designing HANs for residential environments.

Embedded real-time systems face significant challenges in thermal management. While earlier research on feedback thermal control has shown promise in dealing with the uncertainty in thermal characteristics, multicore processors introduce new challenges that cannot be handled by previous solutions designed for single-core processors. Multicore processors require the temperature and real-time performance of multiple cores be controlled simultaneously, leading to multi-input-multi-output control problems with inter-core thermal coupling. Furthermore, current Dynamic Voltage and Frequency Scaling (DVFS) mechanisms only support a finite set of states, leading to discrete control variables that cannot be handled by standard linear control techniques. This paper presents Real-Time Multicore Thermal Control (RT-MTC), a novel feedback thermal control framework pecifically designed for multicore real-time systems. RT-MTC dynamically enforces both the desired temperature set point and the schedulable CPU utilization bound of a multicore processor through DVFS. RT-MTC employs a rigorously designed, efficient controller that can achieve effective thermal control with the small number of frequencies commonly supported by current processors. The robustness and advantages of RT-MTC over existing thermal control approaches are demonstrated through both experiments on an Intel Core 2 Duo processor and simulations under a wide range of uncertainties in power consumption.

With the rapid permeation of smartphones and wireless sensors in our society, smartphones are poised to become personal hubs connecting wireless sensors with users and the Internet. Due to frequent changes to applications and network conditions, wireless networks connecting a personal hub and wireless sensors must meet time-varying QoS requirements at minimal energy cost. This paper presents the architecture of a novel Protocol Service System (PSS) towards the vision of protocol service over the air. In contrast to traditional wireless networks where a single MAC protocol is statically selected a priori, PSS switches among multiple MAC protocols at run time to dynamically optimize power efficiency subject and meet current QoS requirements. To meet the memory constraint on wireless sensors PSS employs a component-based reconfigurable MAC architecture to support multiple MAC protocols at significantly reduced memory footprint through component sharing. The feasibility of PSS has been demonstrated through a proof-of-concept implementation of the PSS architecture and the development of a personal hub prototype running the Android OS.

Transmission power control (TPC) has the potential to reduce power consumption in Wireless Sensor Networks (WSNs). However, despite a multitude of existing protocols, they still face significant challenges in real-world deployments. A practical TPC protocol must be robust against complex and dynamic wireless properties, and efficient for resource-constrained sensors. This paper presents P-TPC, a practical TPC protocol designed on control-theoretic techniques. P-TPC features a highly efficient controller designed on a dynamic model that combines a theoretical link model with online parameter estimation. P-TPC's robustness and energy savings are demonstrated through trace-driven simulations and real-world experiments in a campus building and residential environments.

Wireless sensor networks are evolving from single-application platforms towards an integrated infrastructure shared by multiple applications. Given the resource constraints of sensor nodes, it is important to optimize the allocation of applications to maximize the overall Quality of Monitoring (QoM). Recent solutions to this challenging application allocation problem are centralized in nature, limiting their scalability and robustness against network failures and dynamics. This paper presents a distributed game-theoretic approach to application allocation in shared sensor networks. We first transform the optimal application allocation problem to a submodular game and then develop a decentralized algorithm that only employs localized interactions among neighboring nodes. We prove that the network can converge to a pure strategy Nash equilibrium with an approximation bound of 1=2. Simulations based on three real-world datasets demonstrate that our algorithm is competitive against a state-of-the-art centralized algorithm in terms of QoM.

Clinical study found that early detection and intervention are essential for preventing clinical deterioration in patients, for patients both in intensive care units (ICU) as well as in general wards but under real-time data sensing (RDS). In this paper, we develop an integrated data mining approach to give early deterioration warnings for patients under real-time monitoring in ICU and RDS.

Traditional fixed-priority scheduling analysis for periodic task sets is based on the assumption that all tasks are equally critical to the correct operation of the system. Therefore, every task has to be schedulable under the scheduling policy, and estimates of tasks' worst case execution times must be conservative in case a task runs longer than is usual. To address the significant under-utilization of a system's resources under normal operating conditions that can arise from these assumptions, three main approaches have been proposed: priority assignment, period transformation, and zero-slack scheduling. However, to date there has been no quantitative comparison of system schedulability or run-time overhead for the different approaches. In this paper, we present what is to our knowledge the first side-by-side evaluation of those approaches, for periodic mixed-criticality tasks on uniprocessor systems, under a mixed-criticality scheduling model that is common to all three approaches. To make a fair evaluation of zero-slack scheduling, we also address two previously open issues: how to accommodate execution of a task after its deadline, and how to account for previously unidentified forms of interference between mixed-criticality tasks. Our simulations show that while priority assignment and period transformation are most likely to be able to schedule a randomly selected task set, a small fraction of the task sets are schedulable only under the zero-slack approach. Our empirical evaluation demonstrates that user-space implementations of mechanisms to enforce period transformation and zero-slack scheduling can be achieved on Linux without kernel modification, with suitably low overhead for mixed-criticality real-time task sets.

We present a co-designed scheduling framework and platform architecture that together support compositional scheduling of real-time systems. The architecture is built on the Xen virtualization platform, and relies on compositional scheduling theory that uses periodic resource models as component interfaces. We implement resource models as periodic servers and consider enhancements to periodic server design that significantly improve response times of tasks and resource utilization in the system while preserving theoretical schedulability results. We present an extensive evaluation of our implementation using workloads from an avionics case study as well as synthetic ones.

With the advent of industrial standards such as Wireless Hart, process industries are now gravitating towards wireless control systems. Due to limited bandwidth in a wireless network shared by multiple control loops, it is critical to optimize the overall control performance. In this paper, we address the scheduling-control co-design problem of determining the optimal sampling rates of feedback control loops sharing a Wireless Hart network. The objective is to minimize the overall control cost while ensuring that all data flows meet their end-to-end deadlines. The resulting constrained optimization based on existing delay bounds for Wireless Hart networks is challenging since it is non-differentiable, non-linear, and not in closed-form. We propose four methods to solve this problem. First, we present a sub gradient method for rate selection. Second, we propose a greedy heuristic that usually achieves low control cost while significantly reducing the execution time. Third, we propose a global constrained optimization algorithm using a simulated annealing (SA) based penalty method. Finally, we formulate rate selection as a differentiable convex optimization problem that provides a closed-form solution through a gradient descent method. This is based on a new delay bound that is convex and differentiable, and hence simplifies the optimization problem. We evaluate all methods through simulations based on topologies of a 74-node wireless sensor network testbed. Surprisingly, the sub gradient method is disposed to incur the longest execution time as well as the highest control cost among all methods. SA and the greedy heuristic represent the opposite ends of the trade off between control cost and execution time, while the gradient descent method hits the balance between the two.

Driven by the evolution of modern computer architectures from uni-processor to multi-core platforms, there is an increasing need to provide light-weight, efficient, and predictable support for fine-grained parallel and distributed execution of soft real-time tasks with end-to-end timing constraints, modeled as directed a cyclic graphs whose edges capture dependences among their subtasks. At the same time, there is a need to support state of the art programming models such as distributed components, whose ability to encapsulate functionality and allow context-specific optimizations is essential to manage the increasing complexity of modern distributed real-time and embedded systems and systems-of-systems. Real-time distributed middleware such as RT-CORBA has not kept pace with these developments, and a new generation of middleware is needed that can map these dependent subtask graphs onto distributed hosts with multi-core architectures, efficiently and within a simple, lightweight, and intuitive component programming model. To overcome these limitations, we have designed and implemented MC Flow, a novel distributed real-time component middleware for dependent subtask graphs running on multi-core platforms. MC Flow provides three new contributions to the state of the art in real-time component middleware: (1) a very lightweight component model that facilitates system integration and deployment through automatic code generation at compile time from a deployment plan specification, (2) transparent optimization of inter-component communication, and (3) the use of interface polymorphism to separate functional correctness from data copying and other performance constraints so that they can be configured and enforced independently but in a type-safe manner. Empirical evaluations of our approach in comparison to the widely used TAO real-time middleware show that MC Flow performs comparably to TAO when only one core is used and outperforms TAO when multiple cores are involved.

The four papers in this special section present examples of recent advances in the state-of-the-art of cyber-physical systems and cooperating objects.

With the emergence of wireless sensor networks, an enabling communication technology for distributed real-time systems, we face the critical challenge of meeting the end-to-end deadlines of real-time flows. This paper presents Real-time Flow Scheduling (RFS), a novel conflict-free real-time transmission scheduling approach for periodic real-time flows in wireless sensor networks. In contrast to existing transmission scheduling algorithms that ignore interference between transmissions or prevent spatial reuse within the same channel, RFS supports spatial reuse through a novel interference-aware transmission scheduling. While recent work on conflict-free transmission scheduling focused on specialized communication patterns such as queries and converge cast, RFS is designed for peer-to-peer real-time flows with arbitrary inter-flow interference. Moreover, RFS has three salient that make it particularly suitable for real-time systems: First, RFS includes a real-time schedulability analysis that accounts for interference between real-time flows. Second, RFS improves reliability by incorporating retransmissions in a flexible scheduling scheme. Finally, RFS enhances scalability by dividing the network into neighborhoods and provides real-time performance for flows crossing multiple neighborhoods through a novel application of the Release Guard protocol. RFS was evaluated through simulations based on the traces collected from an indoor wireless sensor network test bed. Compared to a traditional TDMA protocol, RFS reduces flow latencies by up to 2.5 times, while improving the real-time capacity by as much as 3.9 times.

WirelessHART is a new wireless sensor-actuator network standard specifically developed for process industries. A key challenge faced by WirelessHART networks is to meet the stringent real-time communication requirements imposed by process monitoring and control applications. Fixed-priority scheduling, a popular scheduling policy for real-time networks, has recently been shown to be an effective real-time transmission scheduling policy in WirelessHART networks. Priority assignment has a major impact on the schedulability of real-time flows in these networks. This paper investigates the open problem of priority assignment for periodic real-time flows in a WirelessHART network. We first propose an optimal priority assignment algorithm based on local search for any given worst case delay analysis. We then propose an efficient heuristic search algorithm for priority assignment. We also identify special cases where the heuristic search is optimal. Simulations based on random networks and the real topology of a physical sensor network test bed showed that the heuristic search algorithm achieved near optimal performance in terms of schedulability, while significantly outperforming traditional priority assignment policies for real-time systems.

As system integration becomes an increasingly important challenge for complex real-time systems, there has been a significant demand for supporting real-time systems in virtualized environments. This paper presents RT-Xen, the first real-time hypervisor scheduling framework for Xen, the most widely used open-source virtual machine monitor (VMM). RT-Xen bridges the gap between real-time scheduling theory and Xen, whose wide-spread adoption makes it an attractive platform for integrating a broad range of real-time and embedded systems. Moreover, RT-Xen provides an open-source platform for researchers and integrators to develop and evaluate real-time scheduling techniques, which to date have been studied predominantly via analysis and simulations.

Home area networks (HANs) consisting of wireless sensors have emerged as the enabling technology for important applications such as smart energy. These applications impose unique QoS constraints, requiring low data rates but high network reliability in the face of unpredictable wireless environments. This paper presents two in-depth empirical studies on wireless channels in real homes, providing key design guidelines for meeting the QoS constraints of HAN applications. The spectrum study analyzes spectrum usage in the 2.4 GHz band where HANs based on the IEEE 802.15.4 standard must coexist with existing wireless devices. We characterize the ambient wireless environment in six apartments through passive spectrum analysis across the entire 2.4 GHz band over seven days in each apartment. We find that the wireless conditions in these residential environments are much more complex and varied than in a typical office environment. Moreover, while 802.11 signals play a significant role in spectrum usage, there also exists non-negligible noise from non-802.11 devices. The multichannel link study measures the reliability of different 802.15.4 channels through active probing with motes in ten apartments. We find that there is not always a persistently reliable channel over 24 hours, and that link reliability does not exhibit cyclic behavior at daily or weekly timescales. Nevertheless, reliability can be maintained through infrequent channel hopping, suggesting dynamic channel hopping as a key tool for meeting the QoS requirements of HAN applications. Our empirical studies provide important guidelines and insights in designing HANs for residential environments.

The WirelessHART standard has been specifically designed for real-time communication between sensor and actuator devices for industrial process monitoring and control. End-to-end communication delay analysis for WirelessHART networks is required for acceptance test of real-time data flows from sensors to actuators and for workload adjustment in response to network dynamics. In this paper, we map the scheduling of real-time periodic data flows in a WirelessHART network to real-time multiprocessor scheduling. We, then, exploit the response time analysis for multiprocessor scheduling and propose a novel method for the end-to-end delay analysis of the real-time flows that are scheduled using a fixed priority scheduling policy in a WirelessHART network. Simulations based on both random topologies and real network topologies of a physical testbed demonstrate the efficacy of our end-to-end delay analysis in terms of acceptance ratio under various fixed priority scheduling policies.

Home area networks (HANs) promise to enable sophisticated home automation applications such as smart energy usage and assisted living. However, recent empirical study of HAN reliability in real-world residential environments revealed significant challenges to achieving reliable performance in the face of significant and variable interference from a multitude of coexisting wireless devices. We propose the Adaptive and Robust Channel Hopping (ARCH) protocol: a lightweight receiver-oriented protocol which handles the dynamics of residential environments by reactively channel hopping when channel conditions have degraded. ARCH has several key features. First, ARCH is an adaptive protocol that channel-hops based on changes in channel quality observed in real time. Second, ARCH is a distributed protocol that selects channels on a per-link basis, due to the large link-to-link variations in channel quality observed under empirical study. Third, ARCH is designed to be robust and lightweight. ARCH uses a practical handshaking approach to handle channel desynchronization and an efficient sliding-window scheme that does not involve expensive calculations or modeling, and can be reasonably implemented on memory-constrained wireless sensor platforms. Fourth, ARCH introduces minimal communication overhead for applications where packet acknowledgements are already enabled. We evaluate our approach through real deployment in real-life apartments with residents' daily activity. Our results demonstrate that ARCH can reduce packet retransmissions by a median of 42.3% compared to using a single, fixed wireless channel, and can enable up to a 2.2X improvement in delivery rate on the most unreliable links in our experiment. Under a multi-hop routing scenario, ARCH reduced radio usage by 31.6% on average, by reducing the ETX of each link by up to 83.6%. Due to ARCH's lightweight reactive design, most links achieve this improvement in reliability with 10 or fewer channel hops per day.

Multi-core processors offer a significant performance increase over single core processors. Therefore, they have the potential to enable computation-intensive real-time applications with stringent timing constraints that cannot be met on traditional single-core processors. However, most results in traditional multiprocessor real-time scheduling are limited to sequential programming models and ignore intra-task parallelism. In this paper, we address the problem of scheduling periodic parallel tasks with implicit deadlines on multi-core processors. We first consider a synchronous task model where each task consists of segments, each segment having an arbitrary number of parallel threads that synchronize at the end of the segment. We propose a new task decomposition method that decomposes each parallel task into a set of sequential tasks. We prove that our task decomposition achieves a resource augmentation bound of 2.62 and 3.42 when the decomposed tasks are scheduled using global EDF and partitioned deadline monotonic scheduling, respectively. Finally, we extend our analysis to directed a cyclic graph tasks. We show how these tasks can be converted into synchronous tasks such that the same transformation can be applied and the same augmentation bounds hold.

With the emergence of high data rate sensor network applications, there is an increasing demand for high-performance query services. To meet this challenge, we propose Dynamic Conflict-free Query Scheduling (DCQS), a novel scheduling technique for queries in wireless sensor networks. In contrast to earlier TDMA protocols designed for general-purpose workloads, DCQS is specifically designed for query services in wireless sensor networks. DCQS has several unique features. First, it optimizes the query performance through conflict-free transmission scheduling based on the temporal properties of queries in wireless sensor networks. Second, it can adapt to workload changes without explicitly reconstructing the transmission schedule. Furthermore, DCQS also provides predictable performance in terms of the maximum achievable query rate. We provide an analytical capacity bound for DCQS that enables DCQS to handle overload through rate control. NS2 simulations demonstrate that DCQS significantly outperforms a representative TDMA protocol (DRAND) and 802.11b in terms of query latency and throughput.

Mission-critical target detection imposes stringent performance requirements for wireless sensor networks, such as high detection probabilities and low false alarm rates. Data fusion has been shown as an effective technique for improving system detection performance by enabling efficient collaboration among sensors with limited sensing capability. Due to the high cost of network deployment, it is desirable to place sensors at optimal locations to achieve maximum detection performance. However, for sensor networks employing data fusion, optimal sensor placement is a nonlinear and nonconvex optimization problem with prohibitively high computational complexity. In this paper, we present fast sensor placement algorithms based on a probabilistic data fusion model. Simulation results show that our algorithms can meet the desired detection performance with a small number of sensors while achieving up to seven-fold speedup over the optimal algorithm.

Thermal management is critical for clusters because of the increasing power consumption of modern processors, compact server architectures and growing server density in data centers. Thermal balancing mitigates hot spots in a cluster through dynamic load distribution among servers. This paper presents two Control-theoretical Thermal Balancing (CTB) algorithms that dynamically balance the temperatures of different servers based on online measurements. CTB features controllers rigorously designed based on optimal control theory and a difference equation model that approximates the thermal dynamics of clusters. Control analysis and simulation results demonstrate that CTB achieves robust thermal balancing under a wide range of uncertainties: (1) when different tasks incur different power consumptions on the CPUs, (2) when servers experience different ambient temperatures, and (3) when servers experience thermal faults.

The robust operation of many sensor network applications depends on deploying relays to ensure wireless coverage. Radio mapping aims to predict network coverage based on a small number of link measurements. This problem is particularly challenging in complex indoor environments where walls significantly affect radio signal propagation. Nevertheless, we show that it is feasible to accurately predict coverage through a two-step process: a propagation model is used to predict signal strength at a recipient node, which is then mapped to a coverage prediction. Through an in-depth empirical study, we show that complex models do not necessarily produce accurate estimates of signal strength: there is an important tradeoff between model accuracy and the number of parameters that must be estimated from limited training data. We find that the best performance is achieved by a family of models which classify walls based on their attenuation into a small number of classes and develop an algorithm to perform this classification automatically. Based on these insights, we build a novel Radio Mapping Tool (RMT) for predicting radio converge in indoor environments. Experimental results demonstrate RMT's effectiveness in two buildings: RMT reduces the number of locations where coverage is erroneously predicted to exist by as much as 39% and 54% compared to the classic log-normal radio propagation model.

Recent years have witnessed the emergence of shared sensor networks as integrated infrastructure for multiple applications. It is important to allocate multiple applications in a shared sensor network, in order to maximize the overall Quality of Monitoring (QoM) subject to resource constraints (e.g., in terms of memory and network bandwidth). The resulting constrained optimization problem is a difficult and open problem since it is discrete, nonlinear, and not in closed-form. This paper makes several important contributions towards optimal multi-application allocation in shared sensor networks. (1) We formulate the optimal application allocation problem for a common class of distributed sensing applications whose QoM can be modeled as variance reduction functions. (2) We prove key theoretical properties of the optimization problem, including the monotonicity and submodularity of the variance reduction functions and the multiple knapsack structure of constraints; (3) By exploiting these properties, we propose a local search algorithm, which is efficient and has a good approximation bound, for application allocation in shared sensor networks. Simulations based on both real-world datasets and randomly generated networks demonstrate that our algorithm is competitive against simulated annealing in term of QoM, with up to three orders of magnitude reduction in execution times, making it a practical solution towards multi-application allocation in shared sensor networks.

Developing large-scale distributed real-time and embedded (DRE) systems is hard in part due to complex deployment and configuration issues involved in satisfying multiple quality for service (QoS) properties, such as real-timeliness and fault tolerance. This paper makes three contributions to the study of deployment and configuration middleware for DRE systems that satisfy multiple QoS properties. First, it describes a novel task allocation algorithm for passively replicated DRE systems to meet their real-time and fault-tolerance QoS properties while consuming significantly less resources. Second, it presents the design of a strategizable allocation engine that enables application developers to evaluate different allocation algorithms. Third, it presents the design of a middleware agnostic configuration framework that uses allocation decisions to deploy application components/replicas and configure the underlying middleware automatically on the chosen nodes. These contributions are realized in the DeCoRAM (Deployment and Configuration Reasoning and Analysis via Modeling) middleware. Empirical results on a distributed testbed demonstrate DeCoRAM’s ability to handle multiple failures and provide efficient and predictable real-time performance.

Wireless sensor networks are evolving from dedicated application-specific platforms to integrated infrastructure shared by multiple applications. Shared sensor networks offer inherent advantages in terms of flexibility and cost since they allow dynamic resource sharing and allocation among multiple applications. Such shared systems face the critical need for allocation of nodes to contending applications to enhance the overall Quality of Monitoring (QoM) under resource constraints. To address this need, this paper presents Utility-based Multi-application Allocation and Deployment Environment (UMADE), an integrated application deployment system for shared sensor networks. In sharp contrast to traditional approaches that allocate applications based on cyber metrics (e.g., computing resource utilization), UMADE adopts a cyber-physical system approach that dynamically allocates nodes to applications based on their QoM of the physical phenomena. The key novelty of UMADE is that it is designed to deal with the inter-node QoM dependencies typical in cyber-physical applications. Furthermore, UMADE provides an integrated system solution that supports the end-to-end process of (1) QoM specification for applications, (2) QoM-aware application allocation, (3) application deployment over multi-hop wireless networks, and (4) adaptive reallocation of applications in response to network dynamics. UMADE has been implemented on TinyOS and Agilla virtual machine for Telos motes. The feasibility and efficacy of UMADE have been demonstrated on a 28-node wireless sensor network testbed in the context of building automation applications.

Thermal control is crucial to real-time systems as excessive processor temperature can cause system failure or unacceptable performance degradation due to hardware throttling. Real-time systems face significant challenges in thermal management as they must avoid processor overheating while still delivering desired real-time performance. Furthermore, many real-time systems must handle a broad range of uncertainties in system and environmental conditions. To address these challenges, this paper presents Thermal Control under Utilization Bound (TCUB), a novel thermal control algorithm specifically designed for real-time systems. TCUB employs a nested feedback loop that dynamically controls both processor temperature and CPU utilization through task rate adaptation. Rigorously modeled and designed based on control theory, TCUB can maintain both desired processor temperature and CPU utilization, thereby avoiding processor overheating and maintaining desired soft real-time performance. A salient feature of TCUB lies on its capability to handle a broad range of uncertainties in terms of processor power consumption, task execution times, ambient temperature, and unexpected thermal faults. The robustness of TCUB makes it particularly suitable for real-time embedded systems that must operate in highly unpredictable environments. The advantages of TCUB are demonstrated through extensive simulations under a broad range of system and environmental uncertainties.

WirelessHART is an open wireless sensor-actuator network standard for industrial process monitoring and control that requires real-time data communication between sensor and actuator devices. Salient features of a WirelessHART network include a centralized network management architecture, multi-channel TDMA transmission, redundant routes, and avoidance of spatial reuse of channels for enhanced reliability and real-time performance. This paper makes several key contributions to real-time transmission scheduling in WirelessHART networks: (1) formulation of the end-to-end real-time transmission scheduling problem based on the characteristics of WirelessHART, (2) proof of NP-hardness of the problem, (3) an optimal branch-and-bound scheduling algorithm based on a necessary condition for schedulability, and (4) an efficient and practical heuristic-based scheduling algorithm called Conflict-aware Least Laxity First (C-LLF). Extensive simulations based on both random topologies and real network topologies of a physical testbed demonstrate that C-LLF is highly effective in meeting end-to-end deadlines in WirelessHART networks, and significantly outperforms common real-time scheduling policies.

This paper presents the design, deployment, and empirical study of a wireless clinical monitoring system that collects pulse and oxygen saturation readings from patients. The primary contribution of this paper is an in-depth clinical trial that assesses the feasibility of wireless sensor networks for patient monitoring in general hospital units. We present a detailed analysis of the system reliability from a long term hospital deployment over seven months involving 41 patients in a step-down cardiology unit. The network achieved high reliability (median 99.68%, range 95.21% -- 100%). The overall reliability of the system was dominated by sensing reliability of the pulse oximeters (median 80.85%, range 0.46% -- 97.69%). Sensing failures usually occurred in short bursts, although longer periods were also present due to sensor disconnections. We show that the sensing reliability could be significantly improved through oversampling and by implementing a disconnection alarm system that incurs minimal intervention cost. A retrospective data analysis indicated that the system provided sufficient temporal resolution to support the detection of clinical deterioration in three patients who suffered from significant clinical events including transfer to Intensive Care Units. These results indicate the feasibility and promise of using wireless sensor networks for continuous patient monitoring and clinical deterioration detection in general hospital units.

Driven by the confluence between the need to collect data about people's physical, physiological, psychological, cognitive, and behavioral processes in spaces ranging from personal to urban and the recent availability of the technologies that enable this data collection, wireless sensor networks for healthcare have emerged in the recent years. In this review, we present some representative applications in the healthcare domain and describe the challenges they introduce to wireless sensor networks due to the required level of trustworthiness and the need to ensure the privacy and security of medical data. These challenges are exacerbated by the resource scarcity that is inherent with wireless sensor network platforms. We outline prototype systems spanning application domains from physiological and activity monitoring to large-scale physiological and behavioral studies and emphasize ongoing research challenges.

Wireless Sensor Networks (WSNs) represent a new generation of networked embedded systems that must achieve long lifetimes on scarce amounts of energy. Since radio communication accounts for the primary source of power drain in these networks, a large number of different radio power management protocols have been proposed. However, the lack of operating system support for flexibly integrating them with a diverse set of applications and network platforms has made them difficult to use. This article focuses on providing link layer support toward realizing a unified power management architecture (UPMA) for WSNs. In contrast to existing monolithic approaches, we provide (i) a set of standard interfaces that separate link layer power management protocols from common MAC level functionality, (ii) an architectural framework that allows applications to easily swap out different power-management protocols depending on its needs, and (iii) a mechanism for coordinating multiple applications with different power management requirements. We have implemented our approach on both the Mica2 and Telosb radio drivers in TinyOS-2.0, the second generation of the de facto standard operating system for WSNs. Microbenchmark results show that our approach can coordinate the power-management requirements of multiple applications in a platform independent fashion while incurring negligible overhead.

Many wireless sensor networks require sufficient sensing coverage over long periods of time. To conserve energy, a coverage maintenance protocol achieves desired coverage by activating only a subset of nodes, while allowing the others to sleep. Existing coverage maintenance protocols are often designed based on simplistic sensing models that do not capture the stochastic nature of distributed sensing. We propose a new sensing coverage model based on the distributed detection theory, which captures two important characteristics of sensor networks, i.e., probabilistic detection by individual sensors and data fusion among sensors. We then present three coverage maintenance protocols that can meet the specified event detection probability and false alarm rate. The centralized protocol only activates a small number of sensors, but introduces extremely long coverage configuration delay. The Se-Grid protocol reduces the configuration time by dividing the network into separate fusion groups, but increases the number of active sensors due to the lack of collaboration among sensors in different groups. In contrast, by coordinating overlapping fusion groups, the Co-Grid protocol can effectively reduce the number of active sensors and the coverage configuration time. The advantages of Co-Grid have been validated through simulations and benchmark results on Mica2 motes.

Different distributed real-time systems (DRS) must handle aperiodic and periodic events under diverse sets of requirements. While existing middleware such as Real-Time CORBA has shown promise as a platform for distributed systems with time constraints, it lacks flexible configuration mechanisms needed to manage end-to-end timing easily for a wide range of different DRS with both aperiodic and periodic events. The primary contribution of this work is the design, implementation, and performance evaluation of the first configurable component middleware services for admission control and load balancing of aperiodic and periodic event handling in DRS. Empirical results demonstrate the need for, and the effectiveness of, our configurable component middleware approach in supporting different applications with aperiodic and periodic events, and providing a flexible software platform for DRS with end-to-end timing constraints.

Real-time hybrid testing of civil structures represents agrand challenge in the emerging area of cyber-physical systems. Hybrid testing improves significantly on either purely numerical or purely empirical approaches by integrating physical structural components and computational models. Actuator dynamics, complex interactions among computers and physical components, and computation and communication delays all hamper the ability to conduct accurate tests. To address these challenges, this paper presents initial work towards a Cyber-physical Instrument for Real-time hybrid Structural Testing (CIRST). CIRST aims to provide two salient features: a highly configurable architecture for integrating computers and physical components; and system support for real-time operations in distributed hybrid testing. This paper presents the motivation of the CIRST architectureand preliminary test results from a proof-of-concept implementation that integrates a simple structural element and simulation model. CIRST will have broad impacts on thefields of both civil engineering and real-time computing.It will enable high-fidelity real-time hybrid testing of awide range of civil infrastructures, and will also providea high-impact cyber-physical application for the study andevaluation of real-time middleware.

Supporting uninterrupted services for distributed soft real-time applications is hard in resource-constrained and dynamic environments, where processor or process failures and system workload changes are common. Fault-tolerant middleware for these applications must achieve high service availability and satisfactory response times for client applications. Although passive replication is a promising fault tolerance strategy for resource-constrained systems, conventional client failover approaches are non-adaptive and load-agnostic, which can cause system overloads and significantly increase response times after failure recovery.This paper presents four contributions to the study of passive replication for distributed soft real-time applications. First, it describes how our Fault-tolerant Load-aware and Adaptive middlewaRe (FLARe) dynamically adjusts failover targets at runtime in response to system load fluctuations and resource availability. Second, it describes how FLARe's overload management strategy proactively enforces desired CPU utilization bounds by redirecting clients from overloaded processors. Third, it presents the design and implementation of FLARe's lightweight middleware architecture that manages failures and overloads transparently to clients. Finally, it presents experimental results on a distributed Linux testbed that demonstrate how FLARe adaptively maintains soft real-time performance for clients operating in the presence of failures and overloads with negligible runtime overhead.

An increasing number of distributed real-time applications are running on multicore platforms. However, existing real-time middleware (e.g., Real-Time CORBA) lacks adequate support for ensuring the timing constraints of soft real-time tasks on multicore platforms, and thus is dependent on (potentially inadequate) support from the underlying operating system. This paper makes three contributions to the state of the art in real-time system software for multicore platforms. First, it offers what is to our knowledge the first experimental analysis of real-time performance of vanilla Linux primitives on multicore platforms. Second, it presents MC-ORB, the first real-time object request broker (ORB) designed to address the nuances of multiprocessor (and especially multicore) platforms with a novel core-aware middleware thread architecture and allocation service for soft real-time tasks. Third, it evaluates MC-ORB's performance on a Linux multicore testbed, the results of which demonstrate its efficiency and effectiveness.

This article presents Agilla, a mobile agent middleware designed to support self-adaptive applications in wireless sensor networks. Agilla provides a programming model in which applications consist of evolving communities of agents that share a wireless sensor network. Coordination among the agents and access to physical resources are supported by a tuple space abstraction. Agents can dynamically enter and exit a network and can autonomously clone and migrate themselves in response to environmental changes. Agilla's ability to support self-adaptive applications in wireless sensor networks has been demonstrated in the context of several applications, including fire detection and tracking, monitoring cargo containers, and robot navigation. Agilla, the first mobile agent system to operate in resource-constrained wireless sensor platforms, was implemented on top of TinyOS. Agilla's feasibility and efficiency was demonstrated by experimental evaluation on two physical testbeds consisting of Mica2 and TelosB nodes.

Real-time and embedded systems have traditionally been designed for closed environments where operating conditions, input workloads, and resource availability are known a priori and are subject to little or no change at runtime. There is an increasing demand, however, for autonomous capabilities in open distributed real-time and embedded (DRE) systems that execute in environments where input workload and resource availability cannot be accurately characterized a priori. These systems can benefit from autonomic computing capabilities, such as self-(re)configuration and self-optimization, that enable autonomous adaptation under varying—even unpredictable—operational conditions. A challenging problem faced by researchers and developers in enabling autonomic computing capabilities to open DRE systems involves devising adaptive planning and resource management strategies that can meet mission objectives and end-to-end quality of service (QoS) requirements of applications. To address this challenge, this paper presents the Integrated Planning, Allocation, and Control (IPAC) framework, which provides decision-theoretic planning, dynamic resource allocation, and runtime system control to provide coordinated system adaptation and enable the autonomous operation of open DRE systems. This paper presents two contributions to research on autonomic computing for open DRE systems. First, we describe the design of IPAC and show how IPAC resolves the challenges associated with the autonomous operation of a representative open DRE system case study. Second, we empirically evaluate the planning and adaptive resource management capabilities of IPAC in the context of our case study. Our experimental results demonstrate that IPAC enables the autonomous operation of open DRE systems by performing adaptive planning and management of system resources.

Feedback control techniques have recently been applied to a variety of real-time systems. However, a fundamental issue that was left out is guaranteeing system controllability and the feasibility of applying feedback control to such systems. No control algorithms can effectively control a system which itself is uncontrollable or infeasible. In this paper, we use the multiprocessor utilization control problem as a representative example to study the controllability and feasibility of distributed real-time systems. We prove that controllability and feasibility of a system depend crucially on end-to-end task allocations. We then present algorithms for deploying end-to-end tasks to ensure that the system is controllable and utilization control is feasible for the system. Furthermore, we develop runtime algorithms to maintain controllability and feasibility by reallocating tasks dynamically in response to workload variations, such as task terminations and migrations caused by processor failures. We implement our algorithms in a robust real-time middleware system and report empirical results on an experimental test-bed. We also evaluate the performance of our approach in large systems using numerical experiments. Our results demonstrate that the proposed task allocation algorithms improve the robustness of feedback control in distributed real-time systems.

Abstract Many wireless sensor networks must sustain long lifetimes on limited energy resources. Two major approaches, transmission power control and sleep scheduling, have been proposed to reduce the radio power consumption in the transmission state and the idle state, respectively. In this paper, we first review existing transmission power control and sleep scheduling approaches and then describe a Unified Radio Power Management framework for the design and implementation of holistic radio power management solutions in wireless sensor networks. It has two key components: (1) a novel optimization approach called Minimum Power Configuration that minimizes the aggregate radio power consumption of all ratio states and (2) a Unified Power Management Architecture (UPMA) that aims to support the flexible cross‐layer integration of different power management strategies. A novel feature of UPMA is that it enables cross‐layer coordination and joint optimization of different power management strategies that exist at multiple network layers. Copyright © 2008 John Wiley & Sons, Ltd.

Existing off-line schedulability analysis for real-time systems can only handle periodic or sporadic tasks with known minimum inter-arrival times. Modeling sporadic tasks with fixed minimum inter-arrival times is a poor approximation for systems in which tasks arrive in bursts, but have longer intervals between the bursts. In such cases, schedulability analysis based on the existing sporadic task model is pessimistic and seriously overestimates the task's time demand. In this paper, we propose a generalized sporadic task model that characterizes arrival times more precisely than the traditional sporadic task model, and we develop a corresponding schedulability analysis that computes tighter bounds on worst-case response times. Experimental results show that when arrival time jitter increases, the new analysis more effectively guarantees schedulability of sporadic tasks.

Different distributed cyber-physical systems must handle a periodic and periodic events with diverse requirements. While existing real-time middleware such as Real-Time CORBA has shown promise as a platform for distributed systems with time constraints, it lacks flexible configuration mechanisms needed to manage end-to-end timing easily for a wide range of different cyber-physical systems with both aperiodic and periodic events. The primary contribution of this work is the design, implementation and performance evaluation of the first configurable component middleware services for admission control and load balancing of a periodic and periodic event handling in distributed cyber-physical systems. Empirical results demonstrate the need for, and the effectiveness of, our configurable component middleware approach in supporting different applications with a periodic and periodic events, and providing a flexible software platform for distributed cyber-physical systems with end-to-end timing constraints.

Wireless sensor networks (WSNs) have become an increasingly compelling platform for Structural Health Monitoring (SHM) applications, since they can be installed relatively inexpensively onto existing infrastructure. Existing approaches to SHM in WSNs typically address computing system issues or structural engineering techniques, but not both in conjunction. In this paper, we propose a holistic approach to SHM that integrates a decentralized computing architecture with the Damage Localization Assurance Criterion algorithm. In contrast to centralized approaches that require transporting large amounts of sensor data to a base station, our system pushes the execution of portions of the damage localization algorithm onto the sensor nodes, reducing communication costs by an order of magnitude in exchange for moderate additional processing on each sensor. We present a prototype implementation of this system built using the TinyOS operating system running on the Intel Imote2 sensor network platform. Experiments conducted using two different physical structures demonstrate our system's ability to accurately localize structural damage. We also demonstrate that our decentralized approach reduces latency by 64.8% and energy consumption by 69.5% compared to a typical centralized solution, achieving a projected lifetime of 191 days using three standard AAA batteries. Our work demonstrates the advantages of a holistic approach to cyber-physical systems that closely integrates the design of computing systems and physical engineering techniques.

Mission-critical target detection imposes stringent performance requirements for wireless sensor networks, such as high detection probabilities and low false alarm rates. Data fusion has been shown as an effective technique for improving system detection performance by enabling efficient collaboration among sensors with limited sensing capability. Due to the high cost of network deployment, it is desirable to place sensors at optimal locations to achieve maximum detection performance. However, for sensor networks employing data fusion, optimal sensor placement is a non-linear optimizationproblem with prohibitive computational complexity. In this paper, we present fast sensor placement algorithms based on a probabilistic data fusion model.Simulation results show that our algorithms can meet the desired detection performance with a small number of sensors while achieving up to 7-fold speedup over the optimal algorithm.

Topology control can reduce power consumption and channel contention in wireless sensor networks by adjusting the transmission power. However, topology control for wireless sensor networks faces significant challenges, especially in indoor environments where wireless characteristics are extremely complex and dynamic. We first provide insights on the design of robust topology control schemes based on an empirical study in an office building. For example, our analysis shows that Received Signal Strength Indicator and Link Quality Indicator are not always robust indicators of Packet Reception Rate in indoor environments due to significant multi-path effects. We then present Adaptive and Robust Topology control (ART), a novel and practical topology control algorithm with several salient features: (1) ART is robust in indoor environments as it does not rely on simplifying assumptions about the wireless properties; (2) ART can adapt to variations in both link quality and contention; (3) ART introduces zero communication overhead for applications which already use acknowledgements. We have implemented ART as a topology layer in TinyOS 2.x. Our topology layer only adds 12 bytes of RAM per neighbor and 1.5 kilobytes of ROM, and requires minimal changes to upper-layer routing protocols. The advantages of ART have been demonstrated through empirical results on a 28-node indoor testbed.

Real-time image transmission is crucial to an emerging class of distributed embedded systems operating in open network environments. Examples include avionics mission re-planning over Link-16, security systems based on wireless camera networks, and online collaboration using camera phones. Meeting image transmission deadlines is a key challenge in such systems due to unpredictable network conditions. In this paper, we present CAMRIT, a Control-based Adaptive Middleware framework for Real-time Image Transmission in distributed real-time embedded systems. CAMRIT features a distributed feedback control loop that meets image transmission deadlines by dynamically adjusting the quality of image tiles. We derive an analytic model that captures the dynamics of a distributed middleware architecture. A control theoretic methodology is applied to systematically design a control algorithm with analytic assurance of system stability and performance, despite uncertainties in network bandwidth. Experimental results demonstrate that CAMRIT can provide robust real-time guarantees for a representative application scenario.

Feedback control techniques have recently been applied to a variety of real-time systems. However, a fundamental issue that was left out is guaranteeing system controllability and the feasibility of applying feedback control to such systems. No control algorithms can effectively control a system which itself is uncontrollable or infeasible. In this paper, we use the multi-processor utilization control problem as a representative example to study the controllability and feasibility of distributed real-time systems. We prove that controllability and feasibility of a system depend crucially on end-to-end task allocations. We then present algorithms for deploying end-to-end tasks to ensure the system is controllable and utilization control is feasible for the system. Furthermore, we develop runtime algorithms to maintain controllability and feasibility by reallocating tasks dynamically in response to workload variations such as task terminations and migrations caused by processor failures. We implement our algorithms in a robust real-time middleware and report empirical results on an experimental test-bed. Our results demonstrate that the proposed task allocation algorithms improve the robustness of feedback control in distributed real-time systems.

Wireless sensor networks (WSNs) introduce new challenges to topology control due to the prevalence of lossy links. We propose a new topology control formulation for lossy WSNs that captures the stochastic nature of lossy links and quantifies the worst-case path quality in a network. We develop a novel localized scheme called Configurable Topology Control (CTC). The key feature of CTC is its capability of flexibly configuring the topology of a lossy WSN to achieve desired path quality bounds in a localized fashion. Furthermore, CTC can incorporate different control strategies (per-node/per-link) and optimization criteria. Simulations using a realistic radio model of Mica2 motes show that CTC significantly outperforms a representative traditional topology control algorithm called LMST in terms of both communication performance and energy efficiency. Our results demonstrate the importance of incorporating lossy links of WSNs in the design of topology control algorithms.

In this paper, we propose a new approach to wireless sensor network assisted navigation while avoiding moving dangers. Our approach relies on an embedded roadmap in the sensor network that always contains safe paths. The roadmap is adaptive, i.e., it adapts its topology to changing dangers. Mobile robots in the environment use the roadmap to reach their destinations. We evaluated the performance of embedded roadmap both in simulations using realistic conditions and with real hardware. Our results show that the proposed navigation algorithm is better suited for sensor networks than traditional navigation field based algorithms. Our observations suggest that there are two drawbacks of traditional navigation field based algorithms, (i) increased power consumption, (ii) message congestion that can prevent important danger avoidance messages to be received by the robots. In contrast, our approach significantly reduces the number of messages on the network (up to 160 times in some scenarios) while increasing the navigation performance.

Radio power management is of paramount concern in wireless sensor networks that must achieve long lifetimes on scarce amounts of energy. While a multitude of power management protocols have been proposed in the past, the lack of system support for flexibly integrating them with a diverse set of applications and network platforms has made them diffcult to use. Instead of proposing yet another power management protocol, this paper focuses on providing link layer support towards realizing a Unified Power Management Architecture (UPMA) for flexible radio power management in wireless sensor networks. In contrast to the monolithic approaches adopted by existing power management solutions, we provide (1) a set of standard interfaces that allow different power management protocols existing at the link layer to be easily implemented on top of common MAC level functionality, (2) an architectural framework for enabling these protocols to be easily swapped in and out depending on the needs of the applications that require them, and (3) a mechanism for coordinating the existence of multiple applications, each of which may have different requirements for the same underlying power management protocol. We have implemented these features on the Mica2 and Telosb radio stacks in TinyOS-2.0. Microbenchmark results demonstrate that the separation of power management from MAC level functionality incurs a negligible decrease in performance when compared to existing monolithic implementations. Two case studies show that the power management requirements of multiple applications can be easily coordinated, sometimes even resulting in better power savings than any one of them can achieve individually.

Standards-based quality of service (QoS)-enabled component middleware is increasingly being used as a platform for developing distributed real-time embedded (DRE) systems that execute in open environments where operational conditions, input workload, and resource availability cannot be characterized accurately a priori. Although QoS-enabled component middleware offers many desirable features, until recently it lacked the ability to efficiently allocate resources and configure platform-specific QoS settings based on utilization of system resources and application QoS. Moreover, it has also lacked the ability to monitor and enforce application QoS requirements. This paper presents two contributions to research on adaptive resource management for component-based DRE systems. First, we describe the structure and functionality of the Resource Allocation and Control Engine (RACE), which is an open-source adaptive resource management framework built atop standards-based QoS-enabled component middleware. Second, we demonstrate the effectiveness of RACE in the context of a representative DRE system: NASA's Magnetospheric Multi-scale Mission system.

Many mission-critical distributed real-time applications must handle aperiodic tasks with end-to-end deadlines. However, existing middleware (e.g., RT-CORBA) lacks schedulability analysis and run-time enforcement mechanisms needed to give online real-time guarantees for aperiodic tasks. The primary contribution of this work is the design, implementation, and performance evaluation of the first realization of deferrable server and admission control mechanisms for aperiodic tasks in middleware. Empirical results on a KURT-Linux testbed demonstrate the efficiency and effectiveness of our deferrable server and admission control mechanisms in TAO's federated event service.

Many distributed real-time systems face the challenge of dynamically maximizing system utility and meeting strin- gent resource constraints in response to fluctuations in sys- tem workload. Thus, online adaptation must be adopted in face of workload changes in such systems. We present the MultiParametric Rate Adaptation (MPRA) algorithm for discrete rate adaptation in distributed real-time systems with end-to-end tasks. The key novelty and advantage of MPRA is that it can efficiently produce optimal solutions in response to workload variations such as dynamic task ar- rivals. Through offline preprocessing MPRA transforms an NP-hard utility optimization problem to the evaluation of a piecewise linear function of the CPU utilization. At run time MPRA produces optimal solutions by evaluating the function based on the CPU utilization. Analysis and simu- lation results show that MPRA maximizes system utility in the presence of varying workloads, while reducing the on- line computation complexity to polynomial time.

Recent years have seen the emergence of wireless sensor network systems that must support high data rate and real- time queries of physical environments. This paper proposes Real-Time Query Scheduling (RTQS), a novel approach to conflict-free transmission scheduling for real-time queries in wireless sensor networks. First, we show that there is an inherent trade-off between prioritization and throughput in conflict-free query scheduling. We then present three new real-time scheduling algorithms. The non-preemptive query scheduling algorithm achieves high throughput while intro- ducing priority inversions. The preemptive query schedul- ing algorithm eliminates priority inversion at the cost of reduced throughput. The slack stealing query scheduling algorithm combines the benefits of preemptive and non- preemptive scheduling by improving the throughput while meeting query deadlines. Furthermore, we provide schedu- lability analysis for each scheduling algorithm. The anal- ysis and advantages of our scheduling algorithms are vali- dated through NS2 simulations.

The diverse requirements of wireless sensor network applications necessitate the development of multiple media access control (MAC) protocols to meet their varying throughput, latency, and network lifetime needs. Building new MAC protocols has proven to be extremely difficult, however, given the monolithic nature of existing protocol implementations as well as their dependence on a particular radio or processor platform. To address these issues, we propose the MAC Layer Architecture (MLA), a componentbased architecture for power-efficient MAC protocol development in wireless sensor networks. MLA consists of optimized, reusable components that implement a common set of features shared by existing MAC protocols, as well as abstractions that encapsulate the intricacies of the hardware platforms they run on. Through an instantiation of MLA in TinyOS 2.0.1, we have implemented five representative MAC protocols. Empirical results show that MLA results in significant code reuse among different protocols, while achieving comparative performance and memory footprints to monolithic implementations of the same protocols.

Energy management is a critical concern in wireless sensornets. Despite its importance, sensor network operating systems today provide minimal energy management support, requiring applications to explicitly manage system power states. To address this problem, we present ICEM, a device driver architecture that enables simple, energy efficient wireless sensornet applications. The key insight behind ICEM is that the most valuable information an application can give the OS for energy management is its concurrency. Using ICEM, a low-rate sensing application requires only a single line of energy management code and has an efficiency within 1.6 % of a hand-tuned implementation. ICEM’s effectiveness questions the assumption that sensornet applications must be responsible for all power management and sensornets cannot have a standardized OS with a simple API.

This article proposes the minimum power configuration (MPC) approach to power management in wireless sensor networks. In contrast to earlier research that treats different radio states (i.e., transmission/reception/idle) in isolation, MPC integrates them in a joint optimization problem that depends on both the set of active nodes and the transmission power. We propose four approximation algorithms with provable performance bounds and two practical routing protocols. Simulations based on realistic radio models show that the MPC approach can conserve more energy than existing minimum power routing and topology control protocols. Furthermore, it can flexibly adapt to network workload and radio platforms.

Many real-time systems must control their CPU utilizations in order to meet end-to-end deadlines and prevent overload. Utilization control is particularly challenging in distributed real-time systems with highly unpredictable workloads and a large number of end-to-end tasks and processors. This paper presents the Decentralized End-to-end Utilization CONtrol (DEUCON) algorithm, which can dynamically enforce the desired utilizations on multiple processors in such systems. In contrast to centralized control schemes adopted in earlier works, DEUCON features a novel decentralized control structure that requires only localized coordination among neighbor processors. DEUCON is systematically designed based on recent advances in distributed model predictive control theory. Both control-theoretic analysis and simulations show that DEUCON can provide robust utilization guarantees and maintain global system stability despite severe variations in task execution times. Furthermore, DEUCON can effectively distribute the computation and communication cost to different processors and tolerate considerable communication delay between local controllers. Our results indicate that DEUCON can provide a scalable and robust utilization control for large-scale distributed real-time systems executing in unpredictable environments.

There is an increasing demand to introduce adaptive capabilities in distributed real-time and embedded (DRE) systems that execute in open environments where system operational conditions, input workload, and resource availability cannot be characterized accurately a priori. To meet these needs, this paper presents the hierarchical distributed resource-management architecture (HiDRA), which provides adaptive resource management using control-the ore tic techniques that adapt to workload fluctuations and resource availability. In contrast to adaptive control techniques that manage only one type of system resource, HiDRA features a hierarchical control scheme that manages both bandwidth and processor utilization simultaneously. This paper presents three contributions to research in adaptive resource management for DRE systems. First, we describe the structure and functionality of HiDRA. Second, we present an analytical model of HiDRA that formalizes its control theoretic behavior and present analytical performance guarantees. Third, we evaluate the performance of HiDRA via experiments on a representative DRE system that performs distributed target tracking in real-time. Our analytical and empirical results indicate that HiDRA yields predictable, stable, and high system performance, even in the face of changing workload.

With the emergence of high data rate sensor net-work applications, there is an increasing demand for high-performance query services in such networks. To meet this challenge, we propose Dynamic Conflict-free Query Scheduling (DCQS), a novel scheduling technique for queries in wireless sensor networks. In contrast to earlier TDMA protocols designed for general-purpose networks and workloads, DCQS is specifically designed for query services supporting in-network data aggregation. DCQS has several important features. First, it optimizes the query performance and energy efficiency by exploiting the temporal properties and precedence constraints introduced by data aggregation. Second, it can efficiently adapt to dynamic workloads and rate changes without explicitly reconstructing the transmission schedule. In addition, we provide an analytical capacity bound for DCQS in terms of query completion rate. This bound enables DCQS to handle overload through rate control. NS2 simulation results demonstrate that DCQS significantly outperforms a representative TDMA protocol (DRAND) and the 802.11 protocol in terms of query latency, throughput, and energy efficiency.

Many wireless sensor network applications must resolve the inherent conflict between energy efficient communication and the need to achieve desired quality of service such as end-to-end communication delay. To address this challenge, we propose the Real-time Power-Aware Routing (RPAR) protocol, which achieves application-specified communication delays at low energy cost by dynamically adapting transmission power and routing decisions. RPAR features a power-aware forwarding policy and an efficient neighborhood manager that are optimized for resource-constrained wireless sensors. Moreover, RPAR addresses important practical issues in wireless sensor networks, including lossy links, scalability, and severe memory and bandwidth constraints. Simulations based on a realistic radio model of MICA2 motes show that RPAR significantly reduces the number of deadlines missed and energy consumption compared to existing real-time and energy-efficient routing protocols.

Recent years have seen rapid growth of online services that rely on large-scale server clusters to handle high volume of requests. Such clusters must adaptively control the CPU utilizations of many processors in order to maintain desired soft real-time performance and prevent system overload in face of unpredictable workloads. This paper presents DUC-LB, a novel distributed utilization control algorithm for cluster-based soft real-time applications. Compared to earlier works on utilization control, a distinguishing feature of DUC-LB is its capability to handle system dynamics caused by load balancing, which is a common and essential component of most clusters today. Simulation results and control-theoretic analysis demonstrate that DUCLB can provide robust utilization control and effective load balancing in large-scale clusters.

No abstract available.

No abstract available.

This paper presents the design and implementation of an adaptive Web server architecture to provide relative and absolute connection delay guarantees for different service classes. The first contribution of this paper is an adaptive architecture based on feedback control loops that enforce desired connection delays via dynamic connection scheduling and process reallocation. The second contribution is the use of control theoretic techniques to model and design the feedback loops with desired dynamic performance. In contrast to heuristics-based approaches that rely on laborious hand-tuning and testing iteration, the control theoretic approach enables systematic design of an adaptive Web server with established analytical methods. The adaptive architecture has been implemented by modifying an Apache server. Experimental results demonstrate that the adaptive server provides robust delay guarantees even when workload varies significantly.

Greedy geographic routing is an attractive localized routing scheme for wireless sensor networks due to its efficiency and scalability. However, greedy geographic routing may fail due to routing voids on random network topologies. We study greedy geographic routing in an important class of wireless sensor networks (e.g., surveillance or object tracking systems) that provide sensing coverage over a geographic area. Our analysis and simulation results demonstrate that an existing geographic routing algorithm, greedy forwarding (GF), can successfully find short routing paths based on local states in sensing-covered networks. In particular, we derive theoretical upper bounds on the network dilation of sensing-covered networks under GF. We also propose a new greedy geographic routing algorithm called Bounded Voronoi Greedy Forwarding (BVGF) that achieves path dilation lower than 4.62 in sensing-covered networks as long as the communication range is at least twice the sensing range. Furthermore, we extend GF and BVGF to achieve provable performance bounds in terms of total number of transmissions and reliability in lossy networks.

This paper proposes Efficient Sleep Scheduling based on Application Timing (ESSAT), a novel power management scheme that aggressively exploits the timing semantics of wireless sensor network applications. We present three ESSAT protocols each of which integrates (1) a lightweight traffic shaper that actively shapes the workload inside the network to achieve predictable timing properties over multiple hops, and (2) a local scheduling algorithm that wakes up nodes just-in-time based on the timing properties of shaped workloads. Our ESSAT protocols have several distinguishing features. First, they can save significant energy with minimal delay penalties. Second, they do not maintain TDMA schedules or communication backbones; as such, they are highly efficient and suitable for resource constrained sensor platforms. Moreover, the protocols are robust in highly dynamic network environments, i.e., they can handle variable multi-hop communication delays and aggregate workloads involving multiple queries, and can adapt to varying workload and network topologies. Our simulations showed that DTS-SS, an ESSAT protocol, achieved an average node duty cycle 38-87% lower than SPAN, and query latencies 36-98% lower than PSM and SYNC.

Wireless sensor networks (WSNs) are difficult to program and usually run statically-installed software limiting its flexibility. To address this, we developed Agilla, a new middleware that increases network flexibility while simplifying application development. An Agilla network is deployed with no pre-installed application. Instead, users inject mobile agents that spread across nodes performing application-specific tasks. Each agent is autonomous, allowing multiple applications to share a network. Programming is simplified by allowing programmers to create agents using a high-level language. Linda-like tuple spaces are used for inter-agent communication and context discovery. This preserves each agent’s autonomy while providing a rich infrastructure for building complex applications, and marks the first time mobile agents and tuple spaces are used in a unified framework for WSNs. Our efforts resulted in an implementation for MICA2 motes and the development of several applications. The implementation consumes a mere 41.6KB of code and 3.59KB of data memory. An agent can migrate 5 hops in less than 1.1 seconds with 92% reliability. In this paper, we present Agilla and provide a detailed evaluation of its implementation, an empirical study of its overhead, and a case study demonstrating its use.

This paper presents MobiQuery, a spatiotemporal query service that allows mobile users to periodically gather information from their surrounding areas through a wireless sensor network. A key advantage of MobiQuery lies in its capability to meet stringent spatiotemporal performance constraints crucial to many applications. These constraints include query latency, data freshness and fidelity, and changing query areas due to user mobility. A novel just-in-time prefetching algorithm enables MobiQuery to maintain robust spatiotemporal guarantees even when nodes operate under extremely low duty cycles. Furthermore, it significantly reduces the storage cost and network contention caused by continuous queries from mobile users. We validate our approach through both theoretical analysis and simulation results under a range of realistic settings.

Many mission-critical applications require spatiotemporal data services for mobile users or objects. Examples include distributed object tracking and fire monitoring by firefighters. To support such applications, wireless sensor networks must satisfy a set of stringent spatiotemporal constraints despite having low network duty cycles and scarce resources. We have developed two new wake-up and topology maintenance protocols, directional tree maintenance (DTM) and omnidirectional tree creation (OTC), to support spatiotemporal services in mobile environments. A key feature of our protocols is that they provide robust spatiotemporal performance while maintaining low overhead and energy consumption. Our simulations showed that both DTM and OTC can successfully deliver over 85% of query results to a mobile user within desired spatiotemporal constraints, even when the sleep schedule is as long as 15 s, the user changes direction every minute, and the location error is as high as 10 m. The benefits of our protocols have been validated through theoretical analysis and empirical results on a testbed of Mica2 motes.

Agilla is a mobile agent middleware that facilitates the rapid deployment of adaptive applications in wireless sensor networks (WSNs). Agilla allows users to create and inject special programs called mobile agents that coordinate through local tuple spaces, and migrate across the WSN performing application-specific tasks. This fluidity of code and state has the potential to transform a WSN into a shared, general-purpose computing platform capable of running several autonomous applications at a time, allowing us to harness its full potential. We have implemented and evaluated a fire tracking application to determine how well Agilla achieves its goals. Fire is modeled by agents that gradually spread throughout the network, engulfing nodes by inserting fire tuples into their local tuple spaces. Fire tracker agents are then used to form a perimeter around the fire. Using Agilla, we were able to rapidly create and deploy 47 byte fire agents, and 100 byte tracker agents on a WSN consisting of 26 MICA2 motes. Our experiments show that the tracker agents can form an 8-node perimeter around a burning node within 6.5 seconds and that it can adapt to a fire spreading at a rate of 7 seconds per hop. We also present the lessons learned about the adequacy of Agilla's primitives, and regarding the efficiency, reliability, and adaptivity of mobile agents in a WSN.

Autonomous mobile agent navigation is crucial to many mission-critical applications (e.g., search and rescue missions in a disaster area). In this paper, we present how sensor networks may assist probabilistic roadmap methods (PRMs), a class of efficient navigation algorithms particularly suitable for dynamic environments. A key challenge of applying PRM algorithms in dynamic environment is that they require the spatiotemporal sensing of the environment to solve a given navigation problem. To facilitate navigation, we propose a set of query strategies that allow a mobile agent to periodically collect real-time information (e.g., fire conditions) about the environment through a sensor network. Such strategies include local spatiotemporal query (query of spatial neighborhood), global spatiotemporal query (query of all sensors), and border query (query of the border of danger fields). We investigate the impact of different query strategies through simulations under a set of realistic fire conditions. We also evaluate the feasibility of our approach using a real robot and real motes. Our results demonstrate that (1) spatiotemporal queries from a sensor network result in significantly better navigation performance than traditional approaches based on on-board sensors of a robot; (2) the area of local queries represent a tradeoff between communication cost and navigation performance; (3) through in-network processing our border query strategy achieves the best navigation performance at a small fraction of communication cost compared to global spatiotemporal queries.

This paper proposes the minimum power configuration (MPC) approach to energy conservation in wireless sensor networks. In sharp contrast to earlier research that treats topology control, power-aware routing, and sleep management in isolation, MPC integrates them as a joint optimization problem in which the power configuration of a network consists of a set of active nodes and the transmission powers of the nodes. We show through analysis that the minimum power configuration of a network is inherently dependent on the data rates of sources. We propose several approximation algorithms with provable performance bounds compared to the optimal solution, and a practical Minimum Power Configuration Protocol (MPCP) that can dynamically (re)configure a network to minimize the energy consumption based on current data rates. Simulations based on realistic radio models of the Mica2 motes show that MPCP can conserve significantly more energy than existing minimum power routing and topology control protocols.

Feedback control real-time scheduling (FCS) aims at satisfying performance specifications of real-time systems based on adaptive resource management. Existing FCS algorithms often rely on the existence of continuous control variables in real-time systems. A number of real-time systems, however, support only a finite set of discrete configurations that limit the adaptation mechanisms. This paper presents hybrid supervisory utilization control (HySUCON) for scheduling such real-time systems. HySUCON enforces processor utilization bounds by managing the switchings between the discrete configurations. Our approach is based on a best-first-search algorithm that is invoked only if reconfiguration is necessary. Theoretical analysis and simulations demonstrate that the approach leads to robust utilization bounds for varying execution times. Experimental results demonstrate the algorithm performance for a representative application scenario.

No one middleware communication model completely solves the problem of ensuring schedulability in every DRE system. Furthermore, there have been few studies to date of the trade-offs between alternative middleware communication models under different application scenarios. This paper makes three contributions to the state of the art in middleware for distributed real-time and embedded systems. First, it describes what we believe is the first example of integrating release guards directly with CORBA distributable threads to ensure appropriate release times for sub-tasks along an end-to-end computation. Second, it presents empirical results in which release guards improve schedulability of distributable threads compared to a greedy protocol in which arriving tasks simply begin to run as soon as they can. Third, we offer the first empirical comparisons of the distributable thread and event channel models under three different communication scenarios and then using a randomized workload.

Many real-time systems must control their CPU utilizations in order to meet end-to-end deadlines and prevent overload. Utilization control is particularly challenging in distributed real-time systems with highly unpredictable workloads and a large number of end-to-end tasks and processors. This paper presents the decentralized end-to-end utilization control (DEUCON) algorithm that can dynamically enforce desired utilizations on multiple processors in such systems. In contrast to centralized control schemes adopted in earlier work, DEUCON features a novel decentralized control structure that only requires localized coordination among neighbor processors. DEUCON is systematically designed based on recent advances in distributed model predictive control theory. Both control-theoretic analysis and simulations show that DEUCON can provide robust utilization guarantees and maintain global system stability despite severe variations in task execution times. Furthermore, DEUCON can effectively distribute the computation and communication cost to different processors and tolerate considerable communication delay between local controllers. Our results indicate that DEUCON can provide scalable and robust utilization control for large-scale distributed real-time systems executing in unpredictable environments.

A key challenge for distributed real-time and embedded (DRE) middleware is maintaining both system reliability and desired real-time performance in unpredictable environments where system workload and resources may fluctuate significantly. This paper presents FC-ORB, a realtime object request broker (ORB) middleware that employs end-to-end utilization control to handle fluctuations in application workload and system resources. The contributions of this paper are three-fold. First, we present a novel utilization control service that enforces desired CPU utilization bounds on multiple processors by adapting the rates of end-to-end tasks within user-specified ranges. Second, we describe a set of middleware-level mechanisms designed to support end-to-end tasks and distributed multi-processor utilization control in a real-time ORB. Finally, we present extensive experimental results on a Linux testbed. Our results demonstrate that our middleware can maintain desired utilizations in face of uncertainties and variations in task execution times, resource contentions from external workloads, and permanent processor failure. FC-ORB demonstrates that the integration of utilization control, end-to-end scheduling and fault-tolerance mechanisms in DRE middleware is a promising approach for enhancing the robustness of DRE applications in unpredictable environments.

No abstract available.

This article presents FAR, a Face-Aware Routing protocol for mobicast---a spatiotemporal variant of multicast tailored for sensor networks with environmental mobility. FAR features face-routing and timed-forwarding for delivering a message to a mobile delivery zone. Both analytical and statistical results show that FAR achieves reliable spatial and just-in-time message delivery with only moderate communication and memory overhead. This article also presents a novel distributed algorithm for spatial neighborhood discovery for FAR bootstrapping. The spatiotemporal performance and reliability of FAR are demonstrated via network simulations.

An effective approach for energy conservation in wireless sensor networks is scheduling sleep intervals for extraneous nodes while the remaining nodes stay active to provide continuous service. For the sensor network to operate successfully, the active nodes must maintain both sensing coverage and network connectivity. Furthermore, the network must be able to configure itself to any feasible degree of coverage and connectivity in order to support different applications and environments with diverse requirements. This article presents the design and analysis of novel protocols that can dynamically configure a network to achieve guaranteed degrees of coverage and connectivity. This work differs from existing connectivity or coverage maintenance protocols in several key ways. (1) We present a Coverage Configuration Protocol (CCP) that can provide different degrees of coverage requested by applications. This flexibility allows the network to self-configure for a wide range of applications and (possibly dynamic) environments. (2) We provide a geometric analysis of the relationship between coverage and connectivity. This analysis yields key insights for treating coverage and connectivity within a unified framework; in sharp contrast to several existing approaches that address the two problems in isolation. (3) We integrate CCP with SPAN to provide both coverage and connectivity guarantees. (4) We propose a probabilistic coverage model and extend CCP to provide probabilistic coverage guarantees. We demonstrate the capability of our protocols to provide guaranteed coverage and connectivity configurations through both geometric analysis and extensive simulations.

In this paper, we present a spatiotemporal communication protocol for sensor networks, called SPEED. SPEED is specifically tailored to be a localized algorithm with minimal control overhead. End-to-end soft real-time communication is achieved by maintaining a desired delivery speed across the sensor network through a novel combination of feedback control and nondeterministic geographic forwarding. SPEED is a highly efficient and scalable protocol for sensor networks where the resources of each node are scarce. Theoretical analysis, simulation experiments, and a real implementation on Berkeley motes are provided to validate the claims.

An increasing number of distributed real-time systems face the critical challenge of providing quality of service guarantees in open and unpredictable environments. In particular, such systems often need to enforce utilization bounds on multiple processors in order to avoid overload and meet end-to-end deadlines even when task execution times are unpredictable. While recent feedback control real-time scheduling algorithms have shown promise, they cannot handle the common end-to-end task model where each task is comprised of a chain of subtasks distributed on multiple processors. This paper presents the end-to-end utilization control (EUCON) algorithm that adaptively maintains desired CPU utilization through performance feedbacks loops. EUCON is based on a model predictive control approach that models utilization control on a distributed platform as a multivariable constrained optimization problem. A multi-input-multi-output model predictive controller is designed based on a difference equation model that describes the dynamic behavior of distributed real-time systems. Both control theoretic analysis and simulations demonstrate that EUCON can provide robust utilization guarantees when task execution times deviate from estimation or vary significantly at runtime.

An increasing number of distributed real-time systems face the critical challenge of providing end-to-end quality of service (QoS) guarantees in open and unpredictable environments. In particular, such systems often need to guarantee the CPU utilization on multiple processors in order to achieve overload protection and meet end-to-end deadlines while task execution times are unpredictable. While the recently developed feedback control real-time scheduling algorithms have shown promise, they cannot handle the common end-to-end task model in distributed systems where each task is comprised of a chain of subtasks distributed on multiple processors. We present the end-to-end utilization control (EUCON) algorithm that features a distributed feedback loop that dynamically enforces desired CPU utilization bounds on multiple processors based on online performance measurements EUCON is based on a model predictive control approach that models the utilization control problem on a distributed platform as a multivariable constrained optimization problem. A multiinput-multioutput model predictive controller is designed based on a difference equation model that describes the dynamic behavior of distributed real-time systems. Both control theoretic analysis and simulations demonstrate that EUCON can provide robust utilization guarantees even when task execution times deviate from the estimation or vary significantly at run-time.

This work presents a novel protocol for a spatiotemporal variant of multicast called mobicast, designed to support message delivery in ad hoc sensor networks. The spatiotemporal character of mobicast relates to the obligation to deliver a message to all the nodes that will he present at time t in some geographic zone Z, where both the location and shape of the delivery zone are a function of time over some interval (t/sub start/, t/sub end/). The protocol, called face-aware routing (FAR), exploits ideas adapted from existing applications of face routing to achieve reliable mobicast delivery. The key features of the protocol are a routing strategy, which uses information confined solely to a node's immediate spatial neighborhood, and a forwarding schedule, which employs only local topological information. Statistical results shows that, in uniformly distributed random disk graphs, the spatial neighborhood size is usually less than 20. This suggests that FAR is likely to exhibit a low average memory cost. An estimation formula for the average size of the spatial neighborhood in a random network is another analytical result reported in this paper. This paper also presents a novel and low cost distributed algorithm for spatial neighborhood discovery.

Wireless sensor networks often face the critical challenge of sustaining long-term operation on limited battery energy. Coverage maintenance protocols can effectively prolong network lifetime by maintaining sufficient sensing coverage over a region using a small number of active nodes while scheduling the others to sleep. We present a novel distributed coverage maintenance protocol called the Coordinating Grid (Co-Grid). In contrast to existing coverage maintenance protocols which are based on simpler detection models, Co-Grid adopts a distributed detection model based on data fusion that is more consistent with many distributed sensing applications. Co-Grid organizes the network into coordinating fusion groups located on overlapping virtual grids. Through coordination among neighboring fusion groups, Co-Grid can achieve comparable number of active nodes as a centralized algorithm, while reducing the network (re-)configuration time by orders of magnitude. Co-Grid is especially suitable for large and energy-constrained sensor networks that require quick (re-)configuration in response to node failures and environmental changes. We validate our claims by both theoretical analysis and simulations.

Greedy geographic routing is attractive in wireless sensor networks due to its efficiency and scalability. However, greedy geographic routing may incur long routing paths or even fail due to routing voids on random network topologies. We study greedy geographic routing in an important class of wireless sensor networks that provide sensing coverage over a geographic area (e.g., surveillance or object tracking systems). Our geometric analysis and simulation results demonstrate that existing greedy geographic routing algorithms can successfully find short routing paths based on local states in sensing-covered networks. In particular, we derive theoretical upper bounds on the network dilation of sensing-covered networks under greedy geographic routing algorithms. Furthermore, we propose a new greedy geographic routing algorithm called Bounded Voronoi Greedy Forwarding (BVGF) that allows sensing-covered networks to achieve an asymptotic network dilation lower than 4:62 as long as the communication range is at least twice the sensing range. Our results show that simple greedy geographic routing is an effective routing scheme in many sensing-covered networks.

General purpose middleware has been shown to be effective off-the-shelf, in meeting diverse functional requirements for a wide range of distributed systems. However, middleware customization is necessary for many networked embedded systems because of the resource constraints in the networked nodes. We demonstrate that reduced middleware footprint can be achieved while maintaining real-time properties of applications running on such systems. We also give evidence that empirical measurement using a representative application is crucial to guide (1) selection of feature subsets from general purpose middleware and (2) trade-offs among different dimensions of design metrics including real-time, footprint, and portability.

Real-time image transmission is crucial to an emerging class of distributed embedded systems operating in open network environments. Examples include avionics mission re-planning over Link-16, security systems based on wireless camera networks, and online collaboration using camera phones. Meeting image transmission deadlines is a key challenge in such systems due to unpredictable network conditions. In this paper, we present CAMRIT, a control-based adaptive middleware framework for real-time image transmission in distributed real-time embedded systems. CAMRIT features a distributed feedback control loop that meets image transmission deadlines by dynamically adjusting the quality of image tiles. We derive an analytic model that captures the dynamics of a distributed middleware architecture. A control theoretic methodology is applied to systematically design a control algorithm with analytic assurance of system stability and performance, despite uncertainties in network bandwidth. Experimental results demonstrate that CAMRIT can provide robust real-time guarantees for a representative application scenario.

No abstract available.

Real-time scheduling theory offers constant-time schedulability tests for periodic and sporadic tasks based on utilization bounds. Unfortunately, the periodicity or the minimal interarrival-time assumptions underlying these bounds make them inapplicable to a vast range of aperiodic workloads such as those seen by network routers, Web servers, and event-driven systems. This paper makes several important contributions toward real-time scheduling theory and schedulability analysis. We derive the first known bound for schedulability of aperiodic tasks. The bound is based on a utilization-like metric we call synthetic utilization, which allows implementing constant-time schedulability tests at admission control time. We prove that the synthetic utilization bound for deadline-monotonic scheduling of aperiodic tasks is 1/1+/spl radic/1/2. We also show that no other time-independent scheduling policy can have a higher schedulability bound. Similarly, we show that EDF has a bound of 1 and that no dynamic-priority policy has a higher bound. We assess the performance of the derived bound and conclude that it is very efficient in hit-ratio maximization.

In this paper, we present a real-time communication protocol for sensor networks, called SPEED. The protocol provides three types of real-time communication services, namely, real-time unicast, real-time area-multicast and real-time area-anycast. SPEED is specifically tailored to be a stateless, localized algorithm with minimal control overhead End-to-end soft real-time communication is achieved by maintaining a desired delivery speed across the sensor network through a novel combination of feedback control and non-deterministic geographic forwarding. SPEED is a highly efficient and scalable protocol for sensor networks where the resources of each node are scarce. Theoretical analysis, simulation experiments and a real implementation on Berkeley motes are provided to validate our claims.

Sensor networks often involve the monitoring of mobile phenomena. We believe this task can be facilitated by a spatiotemporal multicast protocol which we call "mobicast". Mobicast is a novel spatiotemporal multicast protocol that distributes a message to nodes in a delivery zone that evolves over time in some predictable manner. A key advantage of mobicast lies in its ability to provide reliable and just-in-time message delivery to mobile delivery zones on top of a random network topology. Mobicast can in theory achieve good spatiotemporal delivery guarantees by limiting communication to a mobile forwarding zone whose size is determined by the global worst-case value associated with a compactness metric defined over the geometry of the network (under a reasonable set of assumptions). In this work, we first studied the compactness properties of sensor networks with uniform distribution. The results of this study motivate three approaches for improving the efficiency of spatiotemporal multicast in such networks. First, spatiotemporal multicast protocols can exploit the fundamental tradeoff between delivery guarantees and communication overhead in spatiotemporal multicast. Our results suggest that in such networks, a mobicast protocol can achieve relatively high savings in message forwarding overhead by slightly relaxing the delivery guarantee, e.g., by optimistically choosing a forwarding zone that is smaller than the one needed for a 100% delivery guarantee. Second, spatiotemporal multicast may exploit local compactness values for higher efficiency for networks with non uniform spatial distribution of compactness. Third, for random uniformly distributed sensor network deployment, one may choose a deployment density to best support spatiotemporal communication. We also explored all these directions via simulation and results are presented in this paper.

An effective approach for energy conservation in wireless sensor networks is scheduling sleep intervals for extraneous nodes, while the remaining nodes stay active to provide continuous service. For the sensor network to operate successfully, the active nodes must maintain both sensing coverage and network connectivity. Furthermore, the network must be able to configure itself to any feasible degrees of coverage and connectivity in order to support different applications and environments with diverse requirements. This paper presents the design and analysis of novel protocols that can dynamically configure a network to achieve guaranteed degrees of coverage and connectivity. This work differs from existing connectivity or coverage maintenance protocols in several key ways: 1) We present a Coverage Configuration Protocol (CCP) that can provide different degrees of coverage requested by applications. This flexibility allows the network to self-configure for a wide range of applications and (possibly dynamic) environments. 2) We provide a geometric analysis of the relationship between coverage and connectivity. This analysis yields key insights for treating coverage and connectivity in a unified framework: this is in sharp contrast to several existing approaches that address the two problems in isolation. 3) Finally, we integrate CCP with SPAN to provide both coverage and connectivity guarantees. We demonstrate the capability of our protocols to provide guaranteed coverage and connectivity configurations, through both geometric analysis and extensive simulations.

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.

Attainment of software performance assurances in open, largely unpredictable environments has recently become an important focus for real-time research. Unlike closed embedded systems, many contemporary distributed real-time applications operate in environments where offered load and available resources suffer considerable random fluctuations, thereby complicating the performance assurance problem. Feedback control theory has recently been identified as a promising analytic foundation for controlling performance of such unpredictable, poorly modeled software systems, the same way other engineering disciplines have used this theory for physical process control. In this paper we describe the design and implementation of ControlWare, a middleware QoS-control architecture based on control theory, motivated by the needs of performance-assured Internet services. It offers a new type of guarantees we call convergence guarantees that lie between hard and probabilistic guarantees. The efficacy of the architecture in achieving its QoS goals under realistic load conditions is demonstrated in the context of web server and proxy QoS management.

While early research on real-time computing was concerned with guaranteeing avoidance of undesirable effects, such as overload and deadline misses, adaptive real-time systems are designed to handle such effects dynamically. Various research efforts have addressed the characterization and improvement of the dynamic behavior of real-time systems. However, to the authors' knowledge, no unified framework exists for designing adaptive, real-time software systems based on specifications of desired dynamic behavior. We propose such a framework based on control theory. Using control theory, a designer can (i) specify the desired behavior in terms of a set of performance metrics that can be mapped to a dynamic response of the control system, (ii) establish an underlying control model of the real-time systems, and (iii) design a resource scheduler using feedback control design methods to guarantee runtime satisfaction of the specifications. This is in contrast to more ad-hoc techniques. We also show that simply using long-term average performance metrics is not sufficient in designing controllers. We then develop a new algorithm based on two PID controllers that meet both the transient and steady-state performance requirements.

Despite the significant body of results in real-time scheduling, many real world problems are not easily supported. While algorithms such as Earliest Deadline First, Rate Monotonic, and the Spring scheduling algorithm can support sophisticated task set characteristics (such as deadlines, precedence constraints, shared resources, jitter, etc.), they are all "open loop" scheduling algorithms. Open loop refers to the fact that once schedules are created they are not "adjusted" based on continuous feedback. While open-loop scheduling algorithms can perform well in static or dynamic systems in which the workloads can be accurately modeled, they can perform poorly in unpredictable dynamic systems. In this paper, we present a new scheduling paradigm, which we call feedback control real-time scheduling. Feedback control real-time scheduling defines error terms for schedules, monitors the error, and continuously adjusts the schedules to maintain stable performance. This paper also presents a practical feedback control real-time scheduling algorithm, FC-EDF, which is a starting point in the long-term endeavor of creating a theory and practice of feedback control scheduling.

Despite the significant body of results in real-time scheduling, many real world problems are not easily supported. While algorithms such as Earliest Deadline First, Rate Monotonic, and the Spring scheduling algorithm can support sophisticated task set characteristics (such as deadlines, precedence constraints, shared resources, jitter etc.), they are all "open loop" scheduling algorithms. Open loop refers to the fact that once schedules are created they are not "adjusted" based on continuous feedback. While open-loop scheduling algorithms can perform well in static or dynamic systems in which the workloads can be accurately modeled, they can perform poorly in unpredictable dynamic systems. In this paper, we present a feedback control real-time scheduling algorithm and its evaluation. Performance results demonstrate the effectiveness of the algorithm when execution times vary from the worst case and when there are major shifts of total load in the system. A key part of this feedback solution is its explicit use of deadline based metrics.