Federated learning has become increasingly popular for its ability to process large, distributed datasets and speed up learning while protecting data privacy. However, it typically relies on a central server for coordination, which can be a bottleneck and a single point of failure. To address these limitations, we developed a novel distributed learning architecture that eliminates the need for a central server. The architecture utilizes the hashgraph consensus algorithm (HCA), a distributed ledger technology, which enables the computing nodes to train machine learning models using local data and aggregation with models received from their neighbors. Our work demonstrates that distributed learning using hashgraph consensus can be performed efficiently and is a valid alternative to traditional federated learning. To strengthen this claim, we analyze resilient federated learning in a decentralized setting. Our analysis includes scenarios with denial-of-service and model poisoning attacks. We introduce trimmed soft-medoid (TSM), a resilient aggregation method that has proven resilience to model poisoning attacks. It can be performed at every node using the information available from the hashgraph. An extensive evaluation is conducted using two multimodal machine learning tasks, human emotion recognition and activity recognition. The results confirm that decentralized learning using hashgraph consensus maintains performance parity with traditional federated learning using a central server. This is shown in both normal and adversarial scenarios. We also evaluate the latency and memory overhead of the proposed approach. These are reported to be under an acceptable range, latency of 1s and memory overhead of 8.8-13 GB, for decentralized machine learning.

Graph representations in fixed dimensional feature space are vital in applying learning tools and data mining algorithms to perform graph analytics. Such representations must encode the graph's topological and structural information at the local and global scales without posing significant computation overhead. This paper employs a unique approach grounded in networked control system theory to obtain expressive graph representations with desired properties. We consider graphs as networked dynamical systems and study their controllability properties to explore the underlying graph structure. The controllability of a networked dynamical system profoundly depends on the underlying network topology, and we exploit this relationship to design novel graph representations using controllability Gramian and related metrics. We discuss the merits of this new approach in terms of the desired properties (for instance, permutation and scale invariance) of the proposed representations. Our evaluation of various benchmark datasets in the graph classification framework demonstrates that the proposed representations either outperform (sometimes by more than 6 results to the state-of-the-art embeddings.

Graph Neural Networks (GNNs) have shown remarkable merit in performing various learning-based tasks in complex networks. The superior performance of GNNs often correlates with the availability and quality of node-level features in the input networks. However, for many network applications, such node-level information may be missing or unreliable, thereby limiting the applicability and efficacy of GNNs. To address this limitation, we present a novel approach denoted as Ego-centric Spectral subGraph Embedding Augmentation (ESGEA), which aims to enhance and design node features, particularly in scenarios where information is lacking. Our method leverages the topological structure of the local subgraph to create topology-aware node features. The subgraph features are generated using an efficient spectral graph embedding technique, and they serve as node features that capture the local topological organization of the network. The explicit node features, if present, are then enhanced with the subgraph embeddings in order to improve the overall performance. ESGEA is compatible with any GNN-based architecture and is effective even in the absence of node features. We evaluate the proposed method in a social network graph classification task where node attributes are unavailable, as well as in a node classification task where node features are corrupted or even absent. The evaluation results on seven datasets and eight baseline models indicate up to a 10% improvement in AUC and a 7% improvement in accuracy for graph and node classification tasks, respectively.

Machine learning provides a valuable tool for analyzing high-dimensional functional neuroimaging data, and is proving effective in predicting various neurological conditions, psychiatric disorders, and cognitive patterns. In functional magnetic resonance imaging (MRI) research, interactions between brain regions are commonly modeled using graph-based representations. The potency of graph machine learning methods has been established across myriad domains, marking a transformative step in data interpretation and predictive modeling. Yet, despite their promise, the transposition of these techniques to the neuroimaging domain has been challenging due to the expansive number of potential preprocessing pipelines and the large parameter search space for graph-based dataset construction. In this paper, we introduce NeuroGraph, a collection of graph-based neuroimaging datasets, and demonstrated its utility for predicting multiple categories of behavioral and cognitive traits. We delve deeply into the dataset generation search space by crafting 35 datasets that encompass static and dynamic brain connectivity, running in excess of 15 baseline methods for benchmarking. Additionally, we provide generic frameworks for learning on both static and dynamic graphs. Our extensive experiments lead to several key observations. Notably, using correlation vectors as node features, incorporating larger number of regions of interest, and employing sparser graphs lead to improved performance. To foster further advancements in graph-based data driven neuroimaging analysis, we offer a comprehensive open-source Python package that includes the benchmark datasets, baseline implementations, model training, and standard evaluation.

Deep neural networks have demonstrated prominent capacities for image classification tasks in a closed set setting, where the test data come from the same distribution as the training data. However, in a more realistic open set scenario, traditional classifiers with incomplete knowledge cannot tackle test data that are not from the training classes. Open set recognition (OSR) aims to address this problem by both identifying unknown classes and distinguishing known classes simultaneously. In this paper, we propose a novel approach to OSR that is based on the vision transformer (ViT) technique. Specifically, our approach employs two separate training stages. First, a ViT model is trained to perform closed set classification. Then, an additional detection head is attached to the embedded features extracted by the ViT, trained to force the representations of known data to class-specific clusters compactly. Test examples are identified as known or unknown based on their distance to the cluster centers. To the best of our knowledge, this is the first time to leverage ViT for the purpose of OSR, and our extensive evaluation against several OSR benchmark datasets reveals that our approach significantly outperforms other baseline methods and obtains new state-of-the-art performance.

As the popularity of graphics processing units (GPUs) grows rapidly in recent years, it becomes very critical to study and understand the security implications imposed by them. In this paper, we show that modern GPUs can “broadcast” sensitive information over the air to make a number of attacks practical. Specifically, we present a new electromagnetic (EM) side-channel vulnerability that we have discovered in many GPUs of both NVIDIA and AMD. We show that this vulnerability can be exploited to mount realistic attacks through two case studies, which are website fingerprinting and keystroke timing inference attacks. Our investigation recognizes the commonly used dynamic voltage and frequency scaling (DVFS) feature in GPU as the root cause of this vulnerability. Nevertheless, we also show that simply disabling DVFS may not be an effective countermeasure since it will introduce another highly exploitable EM side-channel vulnerability. To the best of our knowledge, this is the first work that studies realistic physical side-channel attacks on non-shared GPUs at a distance.

Distributed machine learning algorithms are increasingly used in multirobot systems and are prone to Byzantine attacks. In this article, we consider a distributed implementation of the stochastic gradient descent (SGD) algorithm in a cooperative network, where networked agents optimize a global loss function using SGD on the local data and aggregation of the estimates of immediate neighbors. Byzantine agents can send arbitrary estimates to their neighbors, which may disrupt the convergence of normal agents to the optimum state. We show that if every normal agent combines its neighbors’ estimates (states) such that the aggregated state is in the convex hull of its normal neighbors’ states, then the resilient convergence is guaranteed. To assure this sufficient condition, we propose a resilient aggregation rule based on the notion ofcenterpoint, which is a generalization of the median in the higher-dimensional Euclidean space. We evaluate our results using examples of target pursuit and pattern recognition in multirobot systems. The evaluation results demonstrate that distributed learning with average, coordinate-wise median, and geometric median-based aggregation rules fail to converge to the optimum state, whereas the centerpoint-based aggregation rule is resilient in the same scenario.

Memory corruption attacks such as code injection, code reuse, and non-control data attacks have become widely popular for compromising safety-critical Cyber-Physical Systems (CPS). Moving target defense (MTD) techniques such as instruction set randomization (ISR), address space randomization (ASR), and data space randomization (DSR) can be used to protect systems against such attacks. CPS often use time-triggered architectures to guarantee predictable and reliable operation. MTD techniques can cause time delays with unpredictable behavior. To protect CPS against memory corruption attacks, MTD techniques can be implemented in a mixed time and event-triggered architecture that provides capabilities for maintaining safety and availability during an attack. This paper presents a mixed time and event-triggered MTD security approach based on the ARINC 653 architecture that provides predictable and reliable operation during normal operation and rapid detection and reconfiguration upon detection of attacks. We leverage a hardware-in-the-loop testbed and an advanced emergency braking system (AEBS) case study to show the effectiveness of our approach.

Distributed multi-task learning provides significant advantages in multi-agent networks with heterogeneous data sources where agents aim to learn distinct but correlated models simultaneously. However, distributed algorithms for learning relatedness among tasks are not resilient in the presence of Byzantine agents. In this paper, we present an approach for Byzantine resilient distributed multi-task learning. We propose an efficient online weight assignment rule by measuring the accumulated loss using an agent’s data and its neighbors’ models. A small accumulated loss indicates a large similarity between the two tasks. In order to ensure the Byzantine resilience of the aggregation at a normal agent, we introduce a step for filtering out larger losses. We analyze the approach for convex models and show that normal agents converge resiliently towards their true targets. Further, an agent’s learning performance using the proposed weight assignment rule is guaranteed to be at least as good as in the non-cooperative case as measured by the expected regret. Finally, we demonstrate the approach using three case studies, including regression and classification problems, and show that our method exhibits good empirical performance for non-convex models, such as convolutional neural networks.

The rowhammer bug belongs to software-induced hardware faults, and has been exploited to form a wide range of powerful rowhammer attacks. Yet, how to effectively detect such attacks remains a challenging problem. In this paper, we propose a novel approach named RADAR (Rowhammer Attack Detection via A Radio) that leverages certain electromagnetic (EM) signals to detect rowhammer attacks. In particular, we have found that there are recognizable hammering-correlated sideband patterns in the spectrum of the DRAM clock signal. As such patterns are inevitable physical side effects of hammering the DRAM, they can "expose" any potential rowhammer attacks including the extremely elusive ones hidden inside encrypted and isolated environments like Intel SGX enclaves. However, the patterns of interest may become unapparent due to the common use of spread-spectrum clocking (SSC) in computer systems. We propose a de-spreading method that can reassemble the hammering-correlated sideband patterns scattered by SSC. Using a common classification technique, we can achieve both effective and robust detection-based defense against rowhammer attacks, as evaluated on a RADAR prototype under various scenarios. In addition, our RADAR does not impose any performance overhead on the protected system. There has been little prior work that uses physical side-channel information to perform rowhammer defenses, and to the best of our knowledge, this is the first investigation on leveraging EM side-channel information for this purpose.

Fog/'Edge computing is increasingly used to support a wide range of latency-sensitive Internet of Things (IoT) applications due to its elastic computing capabilities that are offered closer to the users. Despite this promise, IoT applications with user mobility face many challenges since offloading the application functionality from the edge to the fog may not always be feasible due to the intermittent connectivity to the fog, and could require application migration among fog nodes due to user mobility. Likewise, executing the applications exclusively on the edge may not be feasible due to resource constraints and battery drain. To address these challenges, this paper describes URMILA, a resource management middleware that makes effective tradeoffs between using fog and edge resources while ensuring that the latency requirements of the IoT applications are met. We evaluate URMILA in the context of a real-world use case on an emulated but realistic IoT testbed.

Cyber-Physical Systems (CPS) are used in many applications where they must perform complex tasks with a high degree of autonomy in uncertain environments. Traditional design flows based on domain knowledge and analytical models are often impractical for tasks such as perception, planning in uncertain environments, control with ill-defined objectives, etc. Machine learning based techniques have demonstrated good performance for such difficult tasks, leading to the introduction of Learning-Enabled Components (LEC) in CPS. Model based design techniques have been successful in the development of traditional CPS, and toolchains which apply these techniques to CPS with LECs are being actively developed. As LECs are critically dependent on training and data, one of the key challenges is to build design automation for them. In this paper, we examine the development of an autonomous Unmanned Underwater Vehicle (UUV) using the Assurance-based Learning-enabled Cyber-physical systems (ALC) Toolchain. Each stage of the development cycle is described including architectural modeling, data collection, LEC training, LEC evaluation and verification, and system-level assurance.

The paper presents RoboScape, a collaborative, networked robotics environment that makes key ideas in computer science accessible to groups of learners in informal learning spaces and K-12 classrooms. RoboScape is built on top of NetsBlox, an open-source, networked, visual programming environment based on Snap! that is specifically designed to introduce students to distributed computation and computer networking. RoboScape provides a twist on the state of the art of robotics learning platforms. First, a user's program controlling the robot runs in the browser and not on the robot. There is no need to download the program to the robot and hence, development and debugging become much easier. Second, the wireless communication between a student's program and the robot can be overheard by the programs of the other students. This makes cybersecurity an immediate need that students realize and can work to address. We have designed and delivered a cybersecurity summer camp to 24 students in grades between 7 and 12. The paper summarizes the technology behind RoboScape, the hands-on curriculum of the camp and the lessons learned.

This paper proposes a new forward reachability analysis approach to verify safety of cyber-physical systems (CPS) with reinforcement learning controllers. The foundation of our approach lies on two efficient, exact and over-approximate reachability algorithms for neural network control systems using star sets, which is an efficient representation of polyhedra. Using these algorithms, we determine the initial conditions for which a safety-critical system with a neural network controller is safe by incrementally searching a critical initial condition where the safety of the system cannot be established. Our approach produces tight over-approximation error and it is computationally efficient, which allows the application to practical CPS with learning enable components (LECs). We implement our approach in NNV, a recent verification tool for neural networks and neural network control systems, and evaluate its advantages and applicability by verifying safety of a practical Advanced Emergency Braking System (AEBS) with a reinforcement learning (RL) controller trained using the deep deterministic policy gradient (DDPG) method. The experimental results show that our new reachability algorithms are much less conservative than existing polyhedra-based approaches. We successfully determine the entire region of the initial conditions of the AEBS with the RL controller such that the safety of the system is guaranteed, while a polyhedra-based approach cannot prove the safety properties of the system.

Elastic auto-scaling in cloud platforms has primarily used horizontal scaling by assigning application instances to distributed resources. Owing to rapid advances in hardware, cloud providers are now seeking vertical elasticity before attempting horizontal scaling to provide elastic auto-scaling for applications. Vertical elasticity solutions must, however, be cognizant of performance interference that stems from multi-tenant collocated applications since interference significantly impacts application quality-of-service (QoS) properties, such as latency. The problem becomes more pronounced for latency-sensitive applications that demand strict QoS properties. Further exacerbating the problem are variations in workloads, which make it hard to determine the right kinds of timely resource adaptations for latency-sensitive applications. To address these challenges and overcome limitations in existing offline approaches, we present an online, data-driven approach which utilizes Gaussian Processes-based machine learning techniques to build runtime predictive models of the performance of the system under different levels of interference. The predictive online models are then used in dynamically adapting to the workload variability by vertically auto-scaling co-located applications such that performance interference is minimized and QoS properties of latency-sensitive applications are met.

The following topics are dealt with: wireless sensor networks; protocols; learning (artificial intelligence); Internet; Internet of Things; social networking (online); data mining; Bluetooth; mobile robots; wireless channels.

Attacks in cyber-physical systems (CPS) which manipulate sensor readings can cause enormous physical damage if undetected. Detection of attacks on sensors is crucial to mitigate this issue. We study supervised regression as a means to detect anomalous sensor readings, where each sensor's measurement is predicted as a function of other sensors. We show that several common learning approaches in this context are still vulnerable to stealthy attacks, which carefully modify readings of compromised sensors to cause desired damage while remaining undetected. Next, we model the interaction between the CPS defender and attacker as a Stackelberg game in which the defender chooses detection thresholds, while the attacker deploys a stealthy attack in response. We present a heuristic algorithm for finding an approximately optimal threshold for the defender in this game, and show that it increases system resilience to attacks without significantly increasing the false alarm rate.

The exponential growth of information and communication technologies have caused a profound shift in the way humans engineer systems leading to the emergence of closed-loop systems involving strong integration and coordination of physical and cyber components, often referred to as cyber-physical systems (CPSs). Because of these disruptive changes, physical systems can now be attacked through cyberspace and cyberspace can be attacked through physical means. The paper considers security and resilience as system properties emerging from the intersection of system dynamics and the computing architecture. A modeling and simulation integration platform for experimentation and evaluation of resilient CPSs is presented using smart transportation systems as the application domain. Evaluation of resilience is based on attacker-defender games using simulations of sufficient fidelity. The platform integrates 1) realistic models of cyber and physical components and their interactions; 2) cyber attack models that focus on the impact of attacks to CPS behavior and operation; and 3) operational scenarios that can be used for evaluation of cybersecurity risks. Three case studies are presented to demonstrate the advantages of the platform: 1) vulnerability analysis of transportation networks to traffic signal tampering; 2) resilient sensor selection for forecasting traffic flow; and 3) resilient traffic signal control in the presence of denial-of-service attacks.

Design methods and tools evolved to support the principle of "separation of concerns" in order to manage engineering complexity. Accordingly, most engineering tool suites are vertically integrated but have limited support for integration across disciplinary boundaries. Cyber–physical systems (CPSs) challenge these established boundaries between disciplines, and thus, the status quo on the tools market. The question is how to create the foundations and technologies for semantically precise model and tool integration that enable reuse of existing commercial and open source tools in domain-specific design flows. In this paper, we describe the lessons learned in the design and implementation of an experimental design automation tool suite, OpenMETA, for complex CPS in the vehicle domain. The conceptual foundation for the integration approach is platform-based design: OpenMETA is architected by introducing two key platforms: the model integration platform and the tool integration platform. The model integration platform includes methods and tools for the precise representation of semantic interfaces among modeling domains. The key new components of the model integration platform are model integration languages and the mathematical framework and tool for the compositional specification of their semantics. The tool integration platform is designed for executing highly automated design-space exploration. Key components of the platform are tools for constructing design spaces and model composers for analytics workflows. The paper concludes with describing experience and lessons learned by using OpenMETA in drivetrain design and by adapting OpenMETA to substantially different CPS application domains.

Fault detection and isolation schemes are designed to detect the onset of adverse events during operations of complex systems, such as aircraft and industrial processes. The state-of-the-art fault diagnosis systems on aircraft combine an expert-created reference model of the associations between faults and symptoms, and a Naïve Bayes reasoner. For complex systems with many dependencies between components, the expert-generated reference models are often incomplete, which hinders timely and accurate fault diagnosis. Mining aircraft flight data is a promising approach to finding these missing relations between symptoms and data. However, mining algorithms generate a multitude of relations, and only a small subset of these relations may be useful for improving diagnoser performance. In this paper, we adopt a knowledge engineering approach that combines data mining methods with human expert input to update an existing reference model and improve the overall diagnostic performance. We discuss three case studies to demonstrate the effectiveness of this method.

Cache-related preemption delay (CRPD) analysis is crucial when designing embedded control systems that employ preemptive scheduling. CRPD analysis for single-level caches has been studied extensively based on useful cache blocks (UCBs). As high-performance embedded processors are increasingly used, which are often equipped with multi-level caches, CRPD analysis for cache hierarchies also needs to be investigated. Recently, an approach has been proposed to estimate CRPD for multi-level non-inclusive caches. Since multi-level inclusive caches are also commonly used, especially in some multi-core processors, it becomes important to study how to analyze CRPD for inclusive cache hierarchies. However, as shown in this paper, new challenges appear due to the strict inclusion enforcement in the multi-level inclusive caches, which make the traditional UCB concept hard to use. In this paper, we propose a new concept of useful positive references (UPRs) to replace the UCB concept. Based on UPRs, we propose an approach to bound the additional cache misses due to a preemption in a two-level inclusive cache hierarchy. We present theoretical analysis to show the approach is safe, and we evaluate the proposed approach on a set of benchmarks to demonstrate its effectiveness. To the best of our knowledge, this is the first attempt to analyze CRPD for multi-level inclusive caches.

Safety analysis is important when designing and developing cyber-physical systems (CPS). An autonomous vehicle can be described as a complex CPS where the physical dynamics of the vehicle interact with the control systems. The challenge is ensuring safety despite nonlinearities, hybrid dynamics, and disturbances as well as complex cyber-physical interactions. In this paper, we present an approach for the safety analysis of automotive control systems using multimodal port-Hamiltonian systems (PHS). The approach uses the Hamiltonian function to represent the energy of the safe and unsafe states and employs passivity to prove that trajectories that begin in safe regions cannot enter unsafe regions. We first apply the approach to the safety analysis of a longitudinal vehicle dynamics composed with an adaptive cruise control (ACC) system. We then extend the results to the safety analysis of a combined longitudinal and lateral vehicle dynamics composed with an ACC and lane keeping control (LKC) system. Simulation results are presented to demonstrate the approach.

The papers included in this special section were presented at the Sixth Annual ACM/IEEE International Conference on Cyber-Physical Systems (ICCPS 2015) that was held on April 14-16, 2015 in Seattle, WA, USA, as part of the Eighth Annual Cyber-Physical Systems Week. ICCPS is the premier single-track conference for reporting advances in all aspects of cyber-physical systems, including theory, tools, applications, systems, testbeds, and field deployments. Its focus includes the core science and technology for developing fundamental principles that underpin the integration of cyber and physical elements, with application domains that include transportation, energy, water, agriculture, ecology, supply-chains, medical and assistive technology, sensor and social networks, and robotics.

To penetrate sensitive computer networks, attackers can use spear phishing to sidestep technical security mechanisms by exploiting the privileges of careless users. In order to maximize their success probability, attackers have to target the users that constitute the weakest links of the system. The optimal selection of these target users takes into account both the damage that can be caused by a user and the probability of a malicious e-mail being delivered to and opened by a user. Since attackers select their targets in a strategic way, the optimal mitigation of these attacks requires the defender to also personalize the e-mail filters by taking into account the users' properties. In this paper, we assume that a learned classifier is given and propose strategic per-user filtering thresholds for mitigating spear-phishing attacks. We formulate the problem of filtering targeted and non-targeted malicious e-mails as a Stackelberg security game. We characterize the optimal filtering strategies and show how to compute them in practice. Finally, we evaluate our results using two real-world datasets and demonstrate that the proposed thresholds lead to lower losses than non-strategic thresholds.

Design automation tools evolved to support the principle of "separation of concerns" to manage engineering complexity. Accordingly, we find tool suites that are vertically integrated with limited support (even intention) for horizontal integratability (i.e. integration across disciplinary boundaries). CPS challenges these established boundaries and with this - market conditions. The question is how to facilitate reorganization and create the foundation and technologies for composable CPS design tool chains that enables reuse of existing commercial and open source tools? In this paper we describe some of the lessons learned in the design and implementation of a design automation tool suite for complex cyber-physical systems (CPS) in the vehicle domain. The tool suite followed a model- and component-based design approach to match the significant increase in design productivity experienced in several narrowly focused homogeneous domains, such as signal processing, control and aspects of electronic design. The primary challenge in the undertaking was the tremendous heterogeneity of complex cyber-physical systems (CPS), where such as vehicles has not yet been achieved. This paper describes some of the challenges addressed and solution approaches to building a comprehensive design tool suite for complex CPS.

Starting with the seminal work by Kempe et al., a broad variety of problems, such as targeted marketing and the spread of viruses and malware, have been modeled as selecting a subset of nodes to maximize diffusion through a network. In cyber-security applications, however, a key consideration largely ignored in this literature is stealth. In particular, an attacker often has a specific target in mind, but succeeds only if the target is reached (e.g., by malware) before the malicious payload is detected and corresponding countermeasures deployed. The dual side of this problem is deployment of a limited number of monitoring units, such as cyber-forensics specialists, so as to limit the likelihood of such targeted and stealthy diffusion processes reaching their intended targets. We investigate the problem of optimal monitoring of targeted stealthy diffusion processes, and show that a number of natural variants of this problem are NP-hard to approximate. On the positive side, we show that if stealthy diffusion starts from randomly selected nodes, the defender's objective is submodular, and a fast greedy algorithm has provable approximation guarantees. In addition, we present approximation algorithms for the setting in which an attacker optimally responds to the placement of monitoring nodes by adaptively selecting the starting nodes for the diffusion process. Our experimental results show that the proposed algorithms are highly effective and scalable.

When designing hard real-time embedded systems, it is required to estimate the worst-case execution time (WCET) of each task for schedulability analysis. Precise cache persistence analysis can significantly tighten the WCET estimation, especially when the program has many loops. Methods for persistence analysis should safely and precisely classify memory references as persistent. Existing safe approaches suffer from multiple sources of pessimism and may not provide precise results. In this paper, we first identify some sources of pessimism that two recent approaches based on younger set and may analysis may encounter. Then, we propose two methods to eliminate these sources of pessimism. The first method improves the update function of the may analysis-based approach; and the second method integrates the younger set-based and may analysis-based approaches together to further reduce pessimism. We also prove the two proposed methods are still safe. We evaluate the approaches on a set of benchmarks and observe the number of memory references classified as persistent is increased by the proposed methods. Moreover, we empirically compare the storage space and analysis time used by different methods.

In many multi-core architectures, inclusive shared caches are used to reduce cache coherence complexity. However, the enforcement of the inclusion property can cause invalidation of memory blocks at higher cache levels. In order to ensure safety, analysis of cache hierarchies with inclusive caches for worst-case execution time (WCET) estimation is typically based on conservative decisions. Thus, the estimation may not be tight. In order to tighten the estimation, this paper proposes an approach that can more precisely analyze the behavior of a cache hierarchy maintaining the inclusion property. We illustrate the approach in the context of multi-level instruction caches. The approach first analyzes all the inclusive caches in the hierarchy in a bottom-up direction, and then analyzes the remaining non-inclusive caches in a top-down direction. In order to capture the inclusion victims and their effects, we also propose a concept of aging barrier and integrate it with the traditional must and persistence analyses to safely slow down their aging process so as to derive more precise analyses. We evaluate the proposed approach on a set of benchmarks and the evaluation reveals that the estimations are tightened.

Multi-level inclusive caches are often used in multi-core processors to simplify the design of cache coherence protocol. However, the use of such cache hierarchies poses great challenges to tight worst-case execution time (WCET) estimation due to the possible invalidation behavior. Traditionally, multi-level inclusive caches are analyzed in a level-by-level manner, and at each level three analyses (i.e. must, may, and persistence) are performed separately. At a particular level, conservative decisions need to be made when the behaviors of other levels are not available, which hurts analysis precision. In this paper, we propose an approach which analyzes a multi-level inclusive cache by integrating the three analyses for all levels together. The approach is based on the abstract interpretation of a concrete operational semantics defined for multi-level inclusive caches. We evaluate the proposed approach and also compare it with two state-of-the-art approaches. From the experimental results, we can observe the proposed approach can significantly improve the analysis precision under relatively small cache size configurations.

Modeling spreading processes for infections has been a widely researched area owing to its application in variety of domains especially epidemic spread and worm propagation. Until recently, infection propagation models usually inspired by epidemic spreading, solely relied upon the underlying network properties without taking into account the variation in node specific properties, such as its ability to spread infection or recover from an infection. Owing to this fact, these models have been agnostic to the effects such node heterogeneity might have in the overall infection (or immunization) process. In this paper, we incorporate node properties in a well-known ac[SIRS] model for infection propagation, and propose new heuristics to curb the spread of infection in heterogeneous networks. The proposed heuristics are validated against various network topologies, including a real-world example of an email exchange network.

In this paper we propose a distributed, low-power, self-organizing MAC scheme for low-power wireless sensor and control applications. In such applications, nearly periodic traffic needs to be handled so that the communication delays are minimized and the transmission is as predictable as possible. We propose Asynchronous Random Schedules with Collision Forecast (ARS/CF) for this purpose, together with a multichannel extension based on an improved modulation scheme to improve capacity scaling of the basic ARS/CF scheme. We analyze and simulate the basic single-hop ARS/CF implementation with regard to throughput and delay when used both in single- and multi-channel settings. Finally, we consider the implementation of ARS/CF in a multi-hop setting.

In this paper, we study local interaction rules that enable a network of dynamic agents to synchronize to a common zero-input state trajectory despite the malicious influence of a subset of adversary agents. The agents in the networked system influence one another by sharing state or output information according to a directed, time-varying graph. The normal agents have identical dynamics modeled by linear time-invariant (LTI) systems that are weakly stable, stabilizable, and detectable. The adversary agents are assumed to be omniscient and can take any uniformly continuous state or output trajectory. We design dynamic state and output control laws under the assumption that there is either an upper bound on the number of neighbors that may be adversaries, or an upper bound on the total number of adversary agents in the network. The control laws use only local information (i.e., information from neighbors in the network) and are resilient in the sense that they are able to mitigate the malicious influence of the adversary nodes and facilitate asymptotic synchronization of the normal agents. The conditions on the network topology required for the success of the synchronization control laws are specified in terms of network robustness. Network robustness is a novel topological property that codifies the notion of sufficient redundancy of directed edges between subsets of nodes in the network.

Probability of successful delivery under deadline constraints is one of the most important performance measures in a wireless real-time multihop control and sensor network. In this paper we approach the problem of determining the probability of successful packet delivery by calculating the per-link outage probability for different fading channel models. We provide easily computable results for the end-to-end reliability for two different physical layer designs. Furthermore, we show that incorporating physical layer information into routing and scheduling decisions can result in significant performance improvements when strict deadlines are imposed on the system.

This paper addresses the problem of resilient in-network consensus in the presence of misbehaving nodes. Secure and fault-tolerant consensus algorithms typically assume knowledge of nonlocal information; however, this assumption is not suitable for large-scale dynamic networks. To remedy this, we focus on local strategies that provide resilience to faults and compromised nodes. We design a consensus protocol based on local information that is resilient to worst-case security breaches, assuming the compromised nodes have full knowledge of the network and the intentions of the other nodes. We provide necessary and sufficient conditions for the normal nodes to reach asymptotic consensus despite the influence of the misbehaving nodes under different threat assumptions. We show that traditional metrics such as connectivity are not adequate to characterize the behavior of such algorithms, and develop a novel graph-theoretic property referred to as network robustness. Network robustness formalizes the notion of redundancy of direct information exchange between subsets of nodes in the network, and is a fundamental property for analyzing the behavior of certain distributed algorithms that use only local information.

The design of wireless sensor networks for detection applications is a challenging task. On one hand, classical work on decentralized detection does not consider practical wireless sensor networks. On the other hand, practical sensor network design approaches that treat the signal processing and communication aspects of the sensor network separately result in sub optimal detection performance because network resources are not allocated efficiently. In this work, we attempt to cross the gap between theoretical decentralized detection work and practical sensor network implementations. We consider a cross-layer approach, where the quality of information, channel state information, and residual energy information are included in the design process of tree-topology sensor networks. The design objective is to specify which sensors should contribute to a given detection task, and to calculate the relevant communication parameters. We compare two design schemes: (1) direct transmission, where raw data are transmitted to the fusion center without compression, and (2) in-network processing, where data is quantized before transmission. For both schemes, we design the optimal transmission control policy that coordinates the communication between sensor nodes and the fusion center. We show the performance improvement for the proposed design schemes over the classical decoupled and maximum throughput design approaches.

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.

This paper presents the Networked Control Systems Windtunnel (NCSWT), an integrated modeling and simulation tool for the evaluation of networked control systems (NCS). NCSWT integrates Matlab/Simulink and ns-2 using the High Level Architecture (HLA). Our implementation of the NCSWT based on HLA guarantees accurate time synchronization and data communication in heterogenous simulations. NCSWT uses the Model Integrated Computing (MIC) techniques to define HLA-based model constructs such as federates representing the simulators and interactions between the simulators. NCSWT also uses MIC techniques to define models representing the control system and network dynamics for the rapid synthesis of simulations.

Recently, many applications have arisen in distributed control that require consensus protocols. Concurrently, we have seen a proliferation of malicious attacks on large-scale distributed systems. Hence, there is a need for (i) consensus problems that take into consideration the presence of adversaries and specify correct behavior through appropriate conditions on agreement and safety, and (ii) algorithms for distributed control applications that solve such consensus problems resiliently despite breaches in security. This paper addresses these issues by (i) defining the adversarial asymptotic agreement problem, which requires that the uncompromised agents asymptotically align their states while satisfying an invariant condition in the presence of adversaries, and (ii) by designing a low complexity consensus protocol, the Adversarial Robust Consensus Protocol (ARC-P), which combines ideas from distributed computing and cooperative control. Two types of omniscient adversaries are considered: (i) Byzantine agents can convey different state trajectories to different neighbors in the network, and (ii) malicious agents must convey the same information to each neighbor. For each type of adversary, sufficient conditions are provided that ensure ARC-P guarantees the agreement and safety conditions in static and switching network topologies, whenever the number of adversaries in the network is bounded by a constant. The conservativeness of the conditions is examined, and the conditions are compared to results in the literature.

System integration is the elephant in the china store of large-scale cyber-physical system (CPS) design. It would be hard to find any other technology that is more undervalued scientifically and at the same time has bigger impact on the presence and future of engineered systems. The unique challenges in CPS integration emerge from the heterogeneity of components and interactions. This heterogeneity drives the need for modeling and analyzing cross-domain interactions among physical and computational/networking domains and demands deep understanding of the effects of heterogeneous abstraction layers in the design flow. To address the challenges of CPS integration, significant progress needs to be made toward a new science and technology foundation that is model based, precise, and predictable. This paper presents a theory of composition for heterogeneous systems focusing on stability. Specifically, the paper presents a passivity-based design approach that decouples stability from timing uncertainties caused by networking and computation. In addition, the paper describes cross-domain abstractions that provide effective solution for model-based fully automated software synthesis and high-fidelity performance analysis. The design objectives demonstrated using the techniques presented in the paper are group coordination for networked unmanned air vehicles (UAVs) and high-confidence embedded control software design for a quadrotor UAV. Open problems in the area are also discussed, including the extension of the theory of compositional design to guarantee properties beyond stability, such as safety and performance.

The integration of physical systems through computing and networking has become pervasive, a trend now known as cyber-physical systems (CPS). Functionality in CPS emerges from the interaction of networked computational and physical objects. System design and integration are particularly challenging because fundamentally different physical and computational design concerns intersect. The impact of these interactions is the loss of compositionality which creates tremendous challenges. The key idea in this article is to use passivity for decoupling the control design of networked systems from uncertainties such as time delays and packet loss, thus providing a fundamental simplification strategy that limits the complexity of interactions. The main contribution is the application of the approach to an experimental case study of a networked multi-robot system. We present a networked control architecture that ensures the overall system remains stable in spite of implementation uncertainties such as network delays and data dropouts, focusing on the technical details required for the implementation. We describe a prototype domain-specific modeling language and automated code generation tools for the design of networked control systems on top of passivity that facilitate effective system configuration, deployment, and testing. Finally, we present experimental evaluation results that show decoupling of interlayer interactions.

In the past decade, numerous consensus protocols for networked multi-agent systems have been proposed. Although some forms of robustness of these algorithms have been studied, reaching consensus securely in networked multi-agent systems, in spite of intrusions caused by malicious agents, or adversaries, has been largely underexplored. In this work, we consider a general model for adversaries in Euclidean space and introduce a consensus problem for networked multi-agent systems similar to the Byzantine consensus problem in distributed computing. We present the Adversarially Robust Consensus Protocol (ARC-P), which combines ideas from consensus algorithms that are resilient to Byzantine faults and from linear consensus protocols used for control and coordination of dynamic agents. We show that ARC-P solves the consensus problem in complete networks whenever there are more cooperative agents than adversaries. Finally, we illustrate the resilience of ARC-P to adversaries through simulations and compare ARC-P with a linear consensus protocol for networked multi-agent systems.

Over the past decade, wireless sensor networks have advanced in terms of hardware design, communication protocols, resource efficiency, and other aspects. Recently, there has been growing interest in mobile wireless sensor networks, and several small-profile sensing devices that are able to control their own movement have already been developed. Unfortunately, resource constraints inhibit the use of traditional navigation methods, because these typically require bulky, expensive, and sophisticated sensors, substantial memory and processor allocation, and a generous power supply. Therefore, alternative navigation techniques are required. In this paper we present TripNav, a localization and navigation system that is implemented entirely on resource-constrained wireless sensor nodes. Localization is realized using radio interferometric angle of arrival estimation, in which bearings to a mobile node from a small number of infrastructure nodes are estimated based on the observed phase differences of an RF interference signal. The position of the mobile node is then determined using triangulation. A digital compass is also employed to keep the mobile node from deviating from the desired trajectory. We demonstrate using a real-world implementation that a resource-constrained mobile sensor node can accurately perform waypoint navigation with an average position error of 0.95 m.

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.

In this article, we describe a distributed, peer-to-peer gesture recognition system along with a software architecture modeling technique and authority control protocol for ubiquitous cameras. This system performs gesture recognition in real time by combining imagery from multiple cameras without using a central server. We propose a system architecture that uses a network of inexpensive cameras to perform in-network video processing. A methodology for transforming well-designed single-node algorithm to distributed system is also proposed. Applications for ubiquitous cameras can be modeled as the composition of a finite-state machine of the system, functional services, and middleware. A service-oriented software architecture is proposed to dynamically reconfigure services when system state changes. By exchanging data and control messages between neighboring sensors, each node can maintain broader view of the environment with integrated video-processing results. Our prototype system is built on Windows machines, and uses standard video cameras as sensors and local network as a communication channel.

Mobile wireless sensors require position updates for tracking and navigation. We present a localization technique that uses the Doppler shift in radio transmission frequency observed by stationary sensors. We consider two scenarios. In the first, the mobile node is carried by a person. In the second, the mobile node controls a robot. In both approaches the mobile node transmits an RF signal, and infrastructure nodes measure the Doppler-shifted frequency. Such measurements enable us to calculate the position and velocity of the mobile transmitter. Our experimental results demonstrate that this technique is viable and accurate for resource-constrained mobile sensor tracking and navigation.

The application of model-based diagnosis schemes to real systems introduces many significant challenges, such as building accurate system models for heterogeneous systems with complex behaviors, dealing with noisy measurements and disturbances, and producing valuable results in a timely manner with limited information and computational resources. The Advanced Diagnostics and Prognostics Testbed (ADAPT), which was deployed at the NASA Ames Research Center, is a representative spacecraft electrical power distribution system that embodies a number of these challenges. ADAPT contains a large number of interconnected components, and a set of circuit breakers and relays that enable a number of distinct power distribution configurations. The system includes electrical dc and ac loads, mechanical subsystems (such as motors), and fluid systems (such as pumps). The system components are susceptible to different types of faults, i.e., unexpected changes in parameter values, discrete faults in switching elements, and sensor faults. This paper presents Hybrid Transcend, which is a comprehensive model-based diagnosis scheme to address these challenges. The scheme uses the hybrid bond graph modeling language to systematically develop computational models and algorithms for hybrid state estimation, robust fault detection, and efficient fault isolation. The computational methods are implemented as a suite of software tools that enable diagnostic analysis and testing through simulation, diagnosability studies, and deployment on the experimental testbed. Simulation and experimental results demonstrate the effectiveness of the methodology.

Wear and tear from sustained operations cause systems to degrade and develop faults. Online fault diagnosis schemes are necessary to ensure safe operation and avoid catastrophic situations, but centralized diagnosis approaches have large memory and communication requirements, scale poorly, and create single points of failure. To overcome these problems, we propose an online, distributed, model-based diagnosis scheme for isolating abrupt faults in large continuous systems. This paper presents two algorithms for designing the local diagnosers and analyzes their time and space complexity. The first algorithm assumes the subsystem structure is known and constructs a local diagnoser for each subsystem. The second algorithm creates the partition structure and local diagnosers simultaneously. We demonstrate the effectiveness of our approach by applying it to the Advanced Water Recovery System developed at the NASA Johnson Space Center.

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.

The paper describes a target tracking system running on a heterogeneous sensor network (HSN) and presents results gathered from a realistic deployment. The system fuses audio direction of arrival data from mote class devices and object detection measurements from embedded PCs equipped with cameras. The acoustic sensor nodes perform beamforming and measure the energy as a function of the angle. The camera nodes detect moving objects and estimate their angle. The sensor detections are sent to a centralized sensor fusion node via a combination of two wireless networks. The novelty of our system is the unique combination of target tracking methods customized for the application at hand and their implementation on an actual HSN platform.

The Mobile Air Quality Monitoring Network (MAQUMON) is presented. The system consists of a number of car-mounted sensor nodes measuring different pollutants in the air. The data points are tagged with location and time utilizing an on-board GPS. Periodically, the measurements are uploaded to a server, processed and then published on the SensorMap portal. Given a sufficient number of nodes and diverse mobility patterns, a detailed picture of the air quality in a large area will be obtained at a low cost.

Real-life cyber-physical systems, such as automotive vehicles, building automation systems, and groups of unmanned vehicles are monitored and controlled by networked control systems. The overall system dynamics emerges from the interaction among physical dynamics, computational dynamics, and communication networks. Network uncertainties such as time-varying delay and packet loss cause significant challenges. This paper proposes a passive control architecture for designing wireless networked control systems that are insensitive to network uncertainties. We describe the architecture for a system consisting of a robotic manipulator controlled by a digital controller over a wireless network and we show that the system is stable even in the presence of time-varying delays. We present simulation results that demonstrate the advantages of the architecture with respect to stability and performance and show that the system is insensitive to network uncertainties.

Stochastic hybrid system (SHS) models can be used to analyze and design complex embedded systems that operate in the presence of uncertainty and variability. Verification of reachability properties for such systems is a critical problem. Developing sound computational methods for verification is challenging because of the interaction between the discrete and the continuous stochastic dynamics. In this paper, we propose a probabilistic method for verification of SHSs based on discrete approximations focusing on reachability and safety problems. We show that reachability and safety can be characterized as a viscosity solution of a system of coupled Hamilton-Jacobi-Bellman equations. We present a numerical algorithm for computing the solution based on discrete approximations that are derived using finite-difference methods. An advantage of the method is that the solution converges to the one for the original system as the discretization becomes finer. We also prove that the algorithm is polynomial in the number of states of the discrete approximation. Finally, we illustrate the approach with two benchmarks: a navigation and a room heater example, which have been proposed for hybrid system verification.

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.

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 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.

In this paper, we address the problem of tracking cooperative mobile nodes in wireless sensor networks. Aiming at a resource efficient solution, we advocate the use of sensors that maintain their location information and rely on the tracking service only when their locations change. In the proposed approach, the tracked node transmits a signal and infrastructure nodes measure the Doppler shifts of the transmitted signal. We show that Mica2 motes can measure RF Doppler shifts with 0.2 Hz accuracy corresponding to a 0.14 m/s error in relative speed estimates using radio inter-ferometric technique.

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.

Multirobot systems are being increasingly used for a variety of tasks in manufacturing, surveillance, and space exploration. These systems can degrade or develop faults during operation, and, therefore, require online diagnosis algorithms to ensure safe operation. Centralized approaches to online diagnosis of robot formations do not scale well for two primary reasons: 1) the computational complexity of the algorithm grows significantly with the number of robots, and 2) the individual robots must communicate a large number of measurements to a central diagnoser. To overcome these problems, we present a distributed, model-based, qualitative fault-diagnosis approach for formations of mobile robots. The approach is based on a bond-graph modeling framework that can deal with multiple sensor types and isolate process, sensor, and actuator faults. The diagnosis scheme employs relative measurement orderings to discriminate among faults by exploiting the temporal order of measurement deviations. This increases the discriminatory power of the measurement set and produces a more efficient fault-isolation algorithm. We describe a distributed diagnoser design algorithm applied to robot formations. Experimental results demonstrate the improvement in both the discriminatory power of the measurements produced by the relative measurement orderings, and the computational efficiency achieved by the distributed-diagnosis approach

Sensor Webs are heterogeneous collections of sensor devices that collect information and interact with the environment. They consist of wireless sensor networks that are ensembles of small, smart, and cheap sensing and computing devices that permeate the environment as well as high-bandwidth rich sensors such as satellite imaging systems, meteorological stations, air quality stations, and security cameras. Emergency response, homeland security, and many other applications have a very real need to interconnect such diverse networks and access information in real-time. While Internet protocols and Web standards provide well-developed mechanisms for accessing this information, linking such mechanisms with resource-constrained sensor networks is very challenging because of the volatility of the communication links. This paper presents a service-oriented programming model for sensor networks which permits discovery and access of Web services. Sensor network applications are realized as graphs of modular and autonomous services with well-defined interfaces that allow them to be described, published, discovered, and invoked over the network providing a convenient way for integrating services from heterogeneous sensor systems. Our approach provides dynamic discovery, composition, and binding of services based on an efficient localized constraint satisfaction algorithm that can be used for developing ambient-aware applications that adapt to changes in the environment. A tracking application that employs many inexpensive sensor nodes, as well as a Web service, is used to illustrate the approach. Our results demonstrate the feasibility of ambient-aware applications that interconnect wireless sensor networks and Web services.

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.

Fault diagnosis of coupled mobile robots requires a large number of measurements to be communicated either between the robots or from the robots to a central diagnoser. As computational complexity increases with the number of measurements, centralized algorithms become inefficient. This paper presents a distributed approach for qualitative fault diagnosis of coupled mobile robots. The approach is based on a bond graph modeling framework which incorporates local and distributed control algorithms, multiple sensor types, and both actuator and sensor faults. Relative measurement orderings are introduced to discriminate faults by exploiting the temporal order of the measurement deviations. This increases the discriminatory power of a set of measurements and results in a more efficient qualitative diagnosis algorithm. Distributed diagnosers are designed and applied to coupled mobile robots. Experimental results for a system consisting of two robots pushing a box demonstrate the improvement in both discriminatory power of the measurements and efficiency of the distributed diagnosis approach

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.

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.

Embedded software and systems are at the intersection of electrical engineering, computer engineering, and computer science, with, increasing importance, in mechanical engineering. Despite the clear need for knowledge of systems modeling and analysis (covered in electrical and other engineering disciplines) and analysis of computational processes (covered in computer science), few academic programs have integrated the two disciplines into a cohesive program of study. This paper describes the efforts conducted at Vanderbilt University to establish a curriculum that addresses the needs of embedded software and systems. Given the compartmentalized nature of traditional engineering schools, where each discipline has an independent program of study, we have had to devise innovative ways to bring together the two disciplines. The paper also describes our current efforts in using learning technology to construct, manage, and deliver sophisticated computer-aided learning modules that can supplement the traditional course structure in the individual disciplines through out-of-class and in-class use.

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.

Many networked embedded sensing and control systems can be modeled as hybrid systems with interacting continuous and discrete dynamics. These systems present significant challenges for monitoring and diagnosis. Many existing model-based approaches focus on diagnostic reasoning assuming appropriate fault signatures have been generated. However, an important missing piece is the integration of model-based techniques with the acquisition and processing of sensor signals and the modeling of faults to support diagnostic reasoning. This paper addresses key modeling and computational problems at the interface between model-based diagnosis techniques and signature analysis to enable the efficient detection and isolation of incipient and abrupt faults in hybrid systems. A hybrid automata model that parameterizes abrupt and incipient faults is introduced. Based on this model, an approach for diagnoser design is presented. The paper also develops a novel mode estimation algorithm that uses model-based prediction to focus distributed processing signal algorithms. Finally, the paper describes a diagnostic system architecture that integrates the modeling, prediction, and diagnosis components. The implemented architecture is applied to fault diagnosis of a complex electro-mechanical machine, the Xerox DC265 printer, and the experimental results presented validate the approach. A number of design trade-offs that were made to support implementation of the algorithms for online applications are also described.

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 paper presents an approach for dynamic software reconfiguration in sensor networks. Our approach utilizes explicit models of the design space of the embedded application. The design space is captured by formally modeling all the software components, their interfaces, and their composition. System requirements are expressed as formal constraints on QoS parameters that are measured at runtime. Reconfiguration is performed by transitioning from one point of the operation space to another based on the constraints. We demonstrate our approach using simulation results for a simple sensor network that performs one-dimensional tracking.

The ability to characterize sensing quality is central to the design and deployment of practical distributed sensor networks. This paper introduces the concept of a sensing field defining, for each point in the physical space of a phenomenon of interest, a measure of how well a sensor network can sense the phenomenon at that point. Using target localization and tracking as examples, the paper derives an upper bound for this measure of goodness measure, using the Cramer-Rao bound and models of sensor observation and network layout. It then evaluates the validity of statistical observation models used by a family of estimators. Simulation results of applying the analytical analysis to a randomly spaced network are presented.

In this paper, the supervisory control of hybrid systems is introduced and discussed at length. Such control systems typically arise in the computer control of continuous processes, for example, in manufacturing and chemical processes, in transportation systems, and in communication networks. A functional architecture of hybrid control systems consisting of a continuous plant, a discrete-event controller, and an interface is used to introduce and describe analysis and synthesis concepts and approaches. Our approach highlights the interaction between the continuous and discrete dynamics, which is the cornerstone of any hybrid system study. Discrete abstractions are used to approximate the continuous plant. Properties of the discrete abstractions to be appropriate representations of the continuous plant are presented, and important concepts such as determinism and controllability are discussed. Supervisory control design methodologies are presented to satisfy control specifications described by formal languages. Several examples are used throughout the paper to illustrate our approach.