Reinforcement Learning (RL) has gained significant attention in recent years. As RL software becomes more complex and infiltrates critical application domains, ensuring its quality and correctness becomes increasingly important. An indispensable aspect of software quality/correctness insurance is testing. However, testing RL software faces unique challenges compared to testing traditional software, due to the difficulty on defining the outputs' correctness. This leads to the RL test oracle problem. Current approaches to testing RL software often rely on human oracles, i.e. convening human experts to judge the correctness of RL software outputs. This heavily depends on the availability and quality (including the experiences, subjective states, etc.) of the human experts, and cannot be fully automated. In this paper, we propose a novel approach to design test oracles for RL software by leveraging the Lyapunov stability control theory. By incorporating Lyapunov stability concepts to guide RL training, we hypothesize that a correctly implemented RL software shall output an agent that respects Lyapunov stability control theories. Based on this heuristics, we propose a Lyapunov stability control theory based oracle,$\operatorname{LPEA}(\vartheta, \theta)$, for testing RL software. We conduct extensive experiments over representative RL algorithms and RL software bugs to evaluate our proposed oracle. The results show that our proposed oracle can outperform the human oracle in most metrics. Particularly, LPEA$(\vartheta=100 \%, \theta=75 \%)$outperforms the human oracle by$53.6 \%, 50 \%, 18.4 \%, 34.8 \%, 18.4 \%, 127.8 \%, 60.5 \%, 38.9 \%$, and 31.7 % respectively on accuracy, precision, recall, F1 score, true positive rate, true negative rate, false positive rate, false negative rate, and ROC curve's AUC; and LPEA ($\vartheta=100 \%, \theta=50 \%$) outperforms the human oracle by$48.2 \%, 47.4 \%, 10.5 \%, 29.1 \%$,$10.5 \%, 127.8 \%, 60.5 \%, 22.2 \%$, and 26.0 % respectively on these metrics.

AutopilotingConnected and Autonomous Vehicles(CAVs) is an important application for mobile computing. A promising context to realize autopiloting CAVs is cooperative driving on dedicated highways. For such a context, an indispensable driving scenario isCooperative Lane Change(CLC). Due to the safety concerns of this driving scenario, a verifiably safe solution is needed (at least, the solution design should be formally provably safe). However, this demand is complicated by the inherently unreliable wireless communications between the CAVs. In this paper, we focus on the well-adoptedConstant Time Headway(CTH) safety rule. We propose a CLC protocol, and formally prove its guarantee of the CTH safety and liveness, even under arbitrary wireless packet losses. These theoretical claims are further confirmed by our simulations. The simulation results also show that our proposed protocol significantly improves lane change success rates (by$5.3\% \sim +\infty \%$) than other alternatives under adverse conditions. Furthermore, the sensitivity study results also show our protocol can tolerate reasonable disturbances.

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

Control-CPSs are usually safety or mission critical, hence they demand thorough debugging. As nowadays control-CPSs reaching millions of lines of source code, traditional human-flesh debugging is no longer sufficient. We need automated software fault localization (SFL) to assist the debugging. In automated SFL, automatically generated test cases are fed to the control-CPS (or the simulator of the control-CPS), to generate thousands of cyber-subsystem code traces and physical-subsystem trajectories. Next, another automated program, aka oracle, is needed to label the correctness of these physical-subsystem trajectories (and hence cyber-subsystem code traces), even without knowing if there is a bug in the cyber-subsystem. Control-CPS oracle design is a known hard problem. To our best knowledge, AR-SI oracle (denoted as AO in the following) is the most widely adopted control-CPS oracle so far. On the other hand, recently, transformer emerges as a major game changer in the domain of time series prediction. As AO is also time series prediction based, people naturally wonder if transformers can also be used as control-CPS oracles; and if so, can it outperform AO. In this paper, we answer this question by comparing AO with an intuitive design of transformer control-CPS oracle (simplified as TO in the following). Our comparison results show that in terms of SFL accuracy and latency, the TO does not significantly outperform the AO; in terms of false positive rate, the AO performs significantly better; and in terms of false negative rate, the TO performs significantly better.

To realize the grand vision of automated driving in smart vehicle cyber-physical systems (CPS), one important task is to support the merging of connected automated vehicles (CAVs) from a metered-ramp to highway. Certain safety rules must be guaranteed. However, this demand is complicated by the inherently unreliable wireless communications. In this article, we focus on the well adopted constant-time-headway (CTH) safety rule. We propose a highway and metered-ramp CAV collaborative merging protocol, and formally prove its guarantee of the CTH safety and liveness under arbitrary wireless data packet losses . These theoretical claims are further validated by our simulations. Furthermore, the simulation results also show significant improvements in the merging efficiency over other solution alternatives. Particularly, the merging success rates are more than 99% better in 11 out of 18 comparison pairs, and 0% (i.e., tied) ∼ 71% better in the remaining 7 comparison pairs.

A key challenge in generate-and-validate automated program repair is directing the search for fixes so that it can efficiently find those that are more likely to be correct. To this end, several techniques use machine learning to capture the features of programmer-written fixes. In existing approaches, fitting the model typically takes placebeforefix generation and is independent of it: the fix generation process uses the learned model as one of its inputs. However, the intermediate outcomes of an ongoing fix generation process often provide valuable information about which candidate fixes were “better”; this information could profitably be used to retrain the model, so that each new iteration of the fixing process would also learn from the outcome of previous ones. In this paper, we propose theLianatechnique for automated program repair, which is based on this idea ofrepeatedlylearning the features of generated fixes. To this end,Lianauses a fine-grained model that combines information about fix characteristics, their relations to the fixing context, and the results of test execution. The model is initially trained offline, and then repeatedly updated online as the fix generation process unravels; at any step, the most up-to-date model is used to guide the search for fixes—prioritizing those that are more likely to include the right ingredients. In an experimental evaluation on 732 real-world Java bugs from 3 popular benchmarks,Lianabuilt correct fixes for 134 faults (83 ranked as first in its output)— improving over several other generate-and-validate program repair tools according to various measures.

Unlike standalone embedded devices, behaviors of a cyber-physical system (CPS) are highly dynamic. Many parameter values (e.g., those related to nature environment and third party black box functions) are unknown offline. Furthermore, distributed sub-CPSs may exchange data online. In this article, we first propose the concept of parametric hybrid automata (PHA) to describe such complex CPSs. As some PHA parameter values are unknown until runtime, conventional offline model checking is infeasible. Instead, we propose to carry out PHA model checking online, as a fault prediction mechanism. However, this usage is challenged by the high time cost of state reachability verification, which is the conventional focus of model checking. To address this challenge, we propose that the model checking shall focus on online scenario reachability validation instead. Furthermore, we propose a mechanism to compose/decompose scenarios. Our scenario reachability validation can exploit linear programming to achieve polynomial time cost. Evaluations on a state-of-the-art train control system show that our approach can cut online model checking time cost from over 1 h to within 200 ms.

Periodically online verification has been widely recognized as a practical and promising method to handle the non-deterministic and unpredictable behavior of dynamic CPS systems. However, it is a challenge to keep the online verification of CPS systems finishing quickly in time to give enough time for the running system to respond, if any error is detected. Nevertheless, the problems under verification for each cycle are highly similar to each other. Most of the differences are caused by run-time factors like changing of parameters' values or the reorganization of active components in the system. Under this investigation, this paper presents an incremental verification technique for online verification of CPS systems. A method is given to distinguish the differences between the problem under verification and the previous verified problem. Then, by reusing the problem space of the previous verified problem as a warm-start base, the modified part can be introduced into the base, which can be solved incrementally and efficiently. A set of case studies on a real-case train control system is presented in this paper to demonstrate the performance of the incremental online verification technique.

Control-CPS software fault localization (SFL, aka bug localization) is of critical importance as bugs may cause major failures, even injuries/deaths. To locate the bugs in control-CPSs, SFL tools often demand many labeled ("correct"/"incorrect") source code execution traces as inputs. To label the correctness of these traces, we must judge the corresponding control-CPS physical trajectories' correctness. However, unlike discrete outputs, the boundaries between correct and incorrect physical trajectories are often vague. The mechanism (aka oracle) to judge the physical trajectories' correctness thus becomes a major challenge. So far, the ad hoc practice of ``human oracles'' is still widely used, whose qualities heavily depend on the human experts' expertise and availability. This paper proposes an oracle based on the well adopted autoregressive system identification (AR-SI). With proven success for controlling black-box physical systems, AR-SI is adapted by us to identify the buggy control-CPS as a black-box. We use this identification result as an oracle to judge the control-CPS's behaviors, and propose a methodology to prepare traces for control-CPS debugging. Comprehensive evaluations on classic control-CPSs with injected real-life and artificial bugs show that our proposed approach significantly outperforms the human oracle approach in SFL accuracy (recall) and latency, and in oracle false positive/negative rates. Our approach also helps discover a new real-life bug in a consumer-grade control-CPS.

Control Cyber-Physical Systems (CPSs) constitute a major category of CPS. In control CPSs, in addition to the well-studied noises within the physical subsystem, we are interested in evaluating the impact of cross-domain noise : the noise that comes from the physical subsystem, propagates through the cyber subsystem, and goes back to the physical subsystem. Impact of cross-domain noise is hard to evaluate when the cyber subsystem is a black box, which cannot be explicitly modeled. To address this challenge, this article focuses on the two-level control CPS, a widely adopted control CPS architecture, and proposes an emulation based evaluation methodology framework. The framework uses hybrid model reachability to quantify the cross-domain noise impact, and exploits Lyapunov stability theories to reduce the evaluation benchmark size. We validated the effectiveness and efficiency of our proposed framework on a representative control CPS testbed. Particularly, 24.1% of evaluation effort is saved using the proposed benchmark shrinking technology.

In a reconfigurable battery pack, the connections among cells can be changed during operation to form different configurations. This can lead a battery, a passive two-terminal device, to a smart battery that can reconfigure itself according to the requirement to enhance operational performance. Several hardware architectures with different levels of complexities have been proposed. Some researchers have used existing hardware and demonstrated improved performance on the basis of novel optimization and scheduling algorithms. The possibility of software techniques to benefit the energy storage systems is exciting, and it is the perfect time for such methods as the need for high-performance and long-lasting batteries is on the rise. This novel field requires new understanding, principles, and evaluation metrics of proposed schemes. In this article, we systematically discuss and critically review the state of the art. This is the first effort to compare the existing hardware topologies in terms of flexibility and functionality. We provide a comprehensive review that encompasses all existing research works, starting from the details of the individual battery including modeling and properties as well as fixed-topology traditional battery packs. To stimulate further research in this area, we highlight key challenges and open problems in this domain.

The charging power supply for batteries may be variable under many circumstances, e.g., when using solar panels or air-driven generators as the energy source. The mismatch between the voltages of the power supply and the battery may cause significant charging inefficiency. In this paper, we use reconfigurable batteries to solve this voltage mismatch problem. We develop algorithms to dynamically decide the battery connections, to both minimize the voltage mismatch and maintain SOC balancing among difference batteries. We build a hardware prototype to implement and validate our method and use simulation experiments to empirically evaluate its performance.

We propose a cyber-physical system of unmanned quadcopters to locate air pollution sources in a timely manner. The system consists of a physical part and a cyber part. The physical part includes unmanned quadcopters equipped with multiple sensors. The cyber part carries out control laws. We simplify the control laws by decoupling the quadcopters’ horizontal-plane motion control from vertical motion control. To control the quadcopter’s horizontal-plane motions, we propose a controller that combines pollutant dynamics with quadcopter physics. To control the quadcopter’s vertical motions, we adopt an anti-windup proportional-integral (PI) controller. We further extend the horizontal-plane control laws from a single quadcopter to multiple quadcopters. The multi-quadcopter control laws are distributed and convergent. We implement a prototype quadcopter and carry out experiments to verify the vertical control laws. We also carry out simulations to evaluate the horizontal-plane control laws. With quadcopter parameters set commensurate with our prototype implementation’s, our simulations show that the control laws can drive quadcopters to locate pollution source(s) in a timely way.

The charging and discharging procedure of a battery is a typical electrochemical process, which can be modeled as a dynamic system. State of charge (SoC) is a commonly used measure to quantify the charge stored in the battery in relation to its full capacity. Recent efforts of optimizing battery performance require more accurate SoC information. The noise in sensor readings makes the estimation even more challenging, especially in battery-operated systems where the supply voltage of the sensor keeps changing. Traditionally used methods of Coulomb counting and extended Kalman filter suffer from the accumulation of noise and common phenomenon of biased noise, respectively. The traditional approach of dealing with ever-increasing demand for accuracy is to develop more complicated and sophisticated solutions, which generally require special models. A key challenge in the adoption of such systems is the inherent requirement of specialized knowledge and hit-and-trial-based tuning. In this paper, we explore a new dimension from the perspective of a self-tuning algorithm, which can provide accurate SoC estimation without error accumulation by creating a negative feedback loop and enhancing its strength to penalize the estimation error. Specifically, we propose a novel method, which uses a battery model and a conservative filter with a strong feedback, which guarantees that worst-case amplification of noise is minimized. We capitalize on the battery model for data fusion of current and voltage signals for SoC estimation. To compute the best parameters, we formulate the linear matrix inequality conditions, which are optimally solved using open-source tools. This approach also features a low computational expense during estimation, which can be used in real-time applications. Thorough mathematical proofs, as well as detailed experimental results, are provided, which highlight the advantages of the proposed method over traditional techniques.

This paper presents an overview of recent trends in Battery System Management Architectures (BSMAs). After introducing the main characteristics of large battery packs, the state of the art in BSMAs is discussed. Two emerging concepts are in the focus of this contribution. On the one hand, there is a development from centralized battery management architectures with a single control entity towards decentralized management where the computational resources are distributed across the battery pack and, hence, move closer to the individual battery cells. This enables a more scalable and modular battery system architecture, while, at the same time, posing challenges regarding hardware and management algorithm design. On the other hand, the static setup of the series- and parallel-connected cells forming the battery pack may be developed towards a reconfigurable architecture such that the electrical topology of the pack can be adaptively changed. Such reconfigurability could increase the reliability of battery packs and reduce management efforts such as cell balancing. At the same time, limited energy efficiency of the additional hardware poses a challenge. We give an outlook how these two trends could be combined into distributed reconfigurable BSMAs. This introduces a set of challenges which have to be solved in order to benefit from the increased scalability, reliability and safety such designs could offer.

In this article, we propose formation control of nonholonomic mobile robots avoiding obstacles in a distributed manner for cluttered environments. The introduction of a virtual robot restructures the formation control problem into a tracking control problem between the virtual reference robot and follower robots. A novel obstacle avoidance approach is proposed based upon the scaling of whole (partial) formation corresponding to a centralized (distributed) framework. For the distributed environment with limited communication, our approach utilized proportional-integral average consensus estimators, whereby information from each robot diffuses through the communication network. The theoretical contribution is to determine the time constant involved in the diffusion process, which can affect overall system performance. The asymptotic convergence of follower robots to the position and orientation of the reference robot is ensured using the Lyapunov function. The new technique is tested with complete, limited, and no information availability. Several simulation results are provided that demonstrate the formation control and obstacle avoidance for multirobots using the proposed scheme.

Networked robotics are a typical cyber–physical system (CPS). This paper presents the cyber physical interaction model to perform formation control and tracking in the presence of other robots and static obstacles. It discusses how such a model can be effectively utilized to deal with kinodynamic and operation range constraints. The cyber system is also responsible for feasible trajectory generation based upon regional path segments and to ensure that all the robots maneuver through obstacles in a safe manner. The introduction of virtual robot restructures the formation control problem into a tracking control problem between virtual reference robot and follower robots. A novel obstacle avoidance approach is proposed based upon the scaling of whole (partial) formation corresponding to centralized (distributed) framework. The involved CPS has network structure preserving properties that are key to effective distributed decision making. The novel formation control, obstacle avoidance, and trajectory tracking approaches facilitate networked robots to be effectively controlled through the cyber system. We also discuss efficient and optimal implementation of the proposed trajectory generator using computer-aided design for CPSs. Evaluation of the proposed approach is provided that demonstrate the formation control, trajectory tracking, and obstacle avoidance for multirobots using the proposed scheme.

Multimedia streaming applications with stringent QoS requirements in 60 GHz mmWave wireless personal area networks (WPANs) demand high rate and low latency data transfer as well as little service disruption. In this paper, we consider the problem of robust relay placement in 60 GHz WPANs with directional antenna. Relays forward traffic from transmitter devices to receiver devices facilitating i) the primary communication path for non-line-of-sight (NLOS) transceiver pairs, and ii) secondary (backup) communication path for line-of-sight (LOS) or NLOS transceiver pairs. By incorporating a classic directional antenna model and characterizing the link contention, we formulate the robust minimum relay placement problem and the robust maximum utility relay placement problem with the objective to minimize the number of relays deployed and maximize the network utility, respectively. Efficient algorithms are developed to solve both problems and have been shown to incur less service disruption in presence of moving subjects that may block the LOS paths in the environment.

With the emergence of many commercial-off-the-shelf (COTS) and/or open-source hardware and software, we can now build cheap Unmanned Aerial Vehicles (UAVs). This will enable a broad spectrum of potential UAV based mobile applications. In this work, we propose a simple open UAV platform: Ard-μ-copter. Ard-μ-copter is a quadcopter built upon the open source ArduPilot [1] infrastructure library and hardware. Comparing to the many existing commercial quadcopters platforms and open source quadcopter platforms, Ard-μ-copter platform is fully open source, simple (i.e. what the "μ" stands for), and with good documentations.

Recently there is a growing interest of incorporating cellular architecture (with wired base stations and last-hop wireless connections) into fieldbuses to support mobile real-time applications. A promising trend is that such cellular fieldbuses will go multichannel multiradio, due to the wide availability of cheap multichannel commercial-off-the-shelf (COTS) wireless nodes, and the rise of 4G and future cellular technologies. For multichannel multiradio cellular fieldbuses, per-flow real-time schedulability guarantee in the inter-cell level has not yet been well studied. Particularly, unlike 3G cellular networks, which use static FDMA/CDMA to isolate cells, the multichannel multiradio feature allows neighboring cells to use the same radio frequency channel at different time-slots, or the same time-slot at different radio frequency channels. How to carry out channel time-slot scheduling is therefore the focus of this paper. To address this issue, we propose a greedy scheduling algorithm, together with a polynomial time closed-form schedulability test. The relationship between the schedulability test result, greedy scheduling schedulability, and schedulability is explored. We prove the equivalence of the three for chained cellular fieldbus topology, a typical topology with broad applications. This also implies the optimality of greedy scheduling, and the sufficiency and necessity of the schedulability test in the context of chained topology. To demonstrate and validate these schedulability theories, we carry out a case study on a classic admission planning problem. The schedulability test not only serves as a planning constraint, but also guides us to propose an approximation algorithm to solve the NP-hard admission planning problem. Comparisons to exhaustive search corroborate the validity of our schedulability theories.

Cyber-Physical Systems (CPS) integrate discrete-time computing and continuous-time physical-world entities, which are often wirelessly interlinked. The use of wireless safety-critical CPS requires safety guarantees despite communication faults. This paper focuses on one important set of such safety rules: Proper-Temporal-Embedding (PTE), where distributed CPS entities must enter/leave risky states according to properly nested temporal pattern and certain duration spacing. Our solution introduces hybrid automata to formally describe and analyze CPS design patterns. We propose a novel leasing based design pattern, along with closed-form configuration constraints, to guarantee PTE safety rules under arbitrary wireless communication faults. We propose a formal procedure to transform the design pattern hybrid automata into specific wireless CPS designs. This procedure can effectively isolate physical world parameters from affecting the PTE safety of the resultant specific designs. We conduct two wireless CPS case studies, one on medicine and the other on control, to show that the resulted system is safe against communication failures. We also compare our approach with a polling based approach. Both approaches support PTE under arbitrary communication failures. The polling approach performs better under severely adverse wireless medium conditions; while ours performs better under benign or moderately adverse wireless medium conditions.

ZigBee and other wireless technologies operating in the (2.4GHz) ISM band are being applied in Wireless Personal Area Networks (WPAN) for many medical applications. However, these low duty cycle, low power, and low data rate medical WPANs suffer from WiFi co-channel interferences. WiFi interference can lead to longer latency and higher packet losses in WPANs, which can be particularly harmful to safety-critical applications with stringent temporal requirements, such as ElectroCardioGraphy (ECG). This paper exploits the Clear Channel Assessment (CCA) mechanism in WiFi devices and proposes a novel policing framework, WiCop, that can effectively control the temporal white-spaces between WiFi transmissions. Such temporal white-spaces can be utilized for delivering low duty cycle WPAN traffic. We have implemented and validated WiCop on SORA, a software-defined radio platform. Experimental results show that with the assistance of the proposed WiCop policing schemes, the packet reception rate of a ZigBee-based WPAN can increase by up to 116% in the presence of a heavy WiFi interferer. A case study on the medical application of WPAN ECG monitoring demonstrates that WiCop can bound ECG signal distortion within 2% even under heavy WiFi interference. An analytical framework is devised to model the CCA behavior of WiFi interferers and the performance of WPANs under WiFi interference with or without WiCop protection. The analytical results are corroborated by experiments.

Hybrid systems model checking is a great success in guaranteeing the safety of computerized control cyber-physical systems (CPS). However, when applying hybrid systems model checking to Medical Device Plug-and-Play (MDPnP) CPS, we encounter two challenges due to the complexity of human body: 1) there are no good offline differential equation-based models for many human body parameters; 2) the complexity of human body can result in many variables, complicating the system model. In an attempt to address the challenges, we propose to alter the traditional approach of offline hybrid systems model checking of time-unbounded (i.e., infinite horizon, a.k.a., long run) future behavior to online hybrid systems model checking of time-bounded (i.e., finite horizon, a.k.a., short run) future behavior. According to this proposal, online model checking runs as a real-time task to prevent faults. To meet the real-time requirements, certain design patterns must be followed, which brings up the codesign issue. We propose two sets of system codesign patterns for hard real time and soft real time, respectively. To evaluate our proposals, a case study on laser tracheotomy MDPnP is carried out. The study shows the necessity of online model checking. Furthermore, test results based on real-world human subject trace show the feasibility and effectiveness of our proposed codesign.

Cyber-Physical Systems (CPS) integrate discrete-time computing and continuous-time physical-world entities, which are often wirelessly interlinked. The use of wireless safety critical CPS (control, healthcare etc.) requires safety guarantees despite communication faults. This paper focuses on one important set of such safety rules: Proper-Temporal-Embedding (PTE). Our solution introduces hybrid automata to formally describe and analyze CPS design patterns. We propose a novel lease based design pattern, along with closed-form configuration constraints, to guarantee PTE safety rules under arbitrary wireless communication faults. We propose a formal methodology to transform the design pattern hybrid automata into specific wireless CPS designs. This methodology can effectively isolate physical world parameters from affecting the PTE safety of the resultant specific designs. We conduct a case study on laser tracheotomy wireless CPS to show that the resulting system is safe and can withstand communication disruptions.

The rapid scaling up of modern avionics is forcing its communication infrastructure to evolve from shared medium toward multi-hop switched real-time networks. This prompts the proposal of avionics full-duplex switched Ethernet (AFDX) standard. Since its publication, AFDX has been well-received, and is deployed or to-be-deployed in state-of-the-art aircrafts, such as Airbus A380/A400M/A350, Boeing 787, Bombardier CSeries etc. On the other hand, AFDX standard only specifies the behavior that an underlying switch must follow, but leaves the architecture design open. This creates an open market for switch vendors. Among the different candidate designs for this market, the TDMA crossbar real-time switch architecture stands out as it complies with and even simplifies many mainstream switch architectures, hence lays a smooth evolution path toward AFDX. In this paper, we focus on analyzing this switch design for AFDX networks. We first prove that TDMA crossbar real-time switch architecture complies with the AFDX specifications; and derive closed-form formulae on the corresponding AFDX networks' traffic characteristics and end-to-end real-time delay bound. Then we prove the resource planning problem in the corresponding AFDX networks is NP-Hard. To address this NP-Hard challenge, we re-model the problem. Based upon the re-modeling, we propose an approximation algorithm.

To integrate the nowadays rapidly expanding distributed real-time systems, we need multi-hop real-time switched networks. A (if not "the") widely recognized/adopted real-time switch architecture is the TDMA crossbar real-time (TCRT) switch architecture. However, the original TCRT switch architecture assumes per-flow queueing. To support scalability, however, queue sharing (i.e. flow aggregation), must be allowed. With simple flow aggregation, flow burstiness can grow and infect, making schedulability and end-to-end delay bound analysis an open problem. To deal with this, we propose the real-time aggregate scheme. The scheme complies with the existing TCRT switch architecture, and deploys spatial-temporal isolation and over-provisioning to curb aggregate member flows' burstiness. This allows us to derive the closed-form end-to-end delay bound, and give the corresponding resource planning and admission control strategies. Simulations are carried out to show the effectiveness of the design.

The rapid scaling up of Networked Control Systems (NCS) is forcing traditional single-hop shared medium industrial fieldbuses (a.k.a. fieldbuses) to evolve toward multi-hop switched fieldbuses. Such evolution faces many challenges. The first is the re-design of switch architecture. To meet the real-time nature of NCS traffic, and to lay a smooth evolution path for switch manufacturers, it is widely agreed that a (if not the) promising switch architecture is an input queueing crossbar architecture running TDMA scheduling. The second challenge is real-time multicast. NCS applications usually involve complex distributed multiple-input-multiple-output interactions, which by their nature necessitate real-time multicast. In shared medium fieldbuses, real-time multicast is straightforward as data sent to the medium is heard by all nodes. On multi-hop switched fieldbuses, however, real-time multicast becomes non-trivial. In this paper, we prove real-time multicast on multi-hop switched fieldbuses is NP-Hard. What is more, real-time multicast on multi-hop switched fieldbuses is fundamentally different from Internet multicast, due to real-time requirement and the homogeneous input queueing crossbar switch architecture. Particularly, switch external links' capacities are no longer mutually independent. Such drastic change of assumptions warrants developing new routing algorithms, and a heuristic algorithm is hereby proposed.

ZigBee and other wireless technologies operating in the (2.4GHz) ISM band are being applied in Wireless Body Area Networks (WBAN) for many medical applications. However, these low duty cycle, low power, and low data rate medical WBANs suffer from WiFi co-channel interferences. WiFi interference can lead to longer latency and higher packet losses in WBANs, which can be particularly harmful to safety-critical applications with stringent temporal requirements. Existing solutions to WiFi-WBAN coexistence either require modifications to WiFi or WBAN devices, or have limited applicability. In this paper, by exploiting the Clear Channel Assessment (CCA) mechanisms in WiFi devices, we propose a novel policing framework, WiCop, that can effectively control the temporal white-spaces between WiFi transmissions. Specifically, the WiCop Fake-PHY-Header policing strategy uses a fake WiFi PHY preamble-header broadcast to mute other WiFi interferers for the duration of WBAN active interval, while the WiCop DSSS-Nulling policing strategy uses repeated WiFi PHY preamble (with its spectrum side lobe nulled by a band-pass filter) to mute other WiFi interferers throughout the duration of WBAN active interval. The resulted WiFi temporal white-spaces can be utilized for delivering low duty cycle WBAN traffic. We have implemented and validated WiCop on SORA, a software defined radio platform. Experiments show that with the assistance of the proposed WiCop policing schemes, the packet reception rate of a ZigBee-based WBAN can increase by up to 43.8% in presence of a busy WiFi interferer.

As real-time industrial control systems scale up, single real-time local area network (LAN) is no longer sufficient; instead, we need real-time switches to merge many real-time LANs into real-time wide area networks (WANs). However, nowadays commercially-off-the-shelf WAN switches are designed for best-effort Internet traffic rather than real-time traffic. To address this problem, we propose a real-time crossbar switch design that minimally modifies, and even simplifies the de facto industrial standard switch design of iSLIP. Specifically, we change the iSLIP request-grant-accept negotiation to deterministic grant. The switch runs periodically with an M cell-time clock-period. Every input port runs per-flow queueing, and every output port deterministically grants input port per-flow queues according to its own M cell-time clock-period schedule. The schedules are created offline. We prove that the global scheduling can be reduced to a preemptive open shop scheduling problem; as long as every input/output needs to send/fetch no more than M cells per M cell-time clock-period, all outputs schedules do not conflict; and the scheduling algorithm takes O(N4) time (N is the number of input/output ports). Such design serves real-time periodic/aperiodic traffic in a time-division multiple-access (TDMA) fashion. This simplifies analysis, provides isolation, and results in a close-form end-to-end delay bound. We implemented the proposed real-time switch using Xilinx field programmable gate arrays (FPGAs), and built a distributed control test bed upon the switched networks. Using the test bed, we carried out experiments to compare the implemented real-time switches and iSLIP switches. The results prove the necessity of using real-time switches for real-time industrial control.

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

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

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

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

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

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

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

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

Deploying wireless LAN for industrial control (IC-WLAN) has many benefits, such as mobility, low deployment cost and ease of reconfiguration. However, the top concern is robustness of wireless communications. Wireless control loops must be maintained under persistent adverse channel conditions, such as noise, large-scale path loss and fading. Many electro-magnetic interference sources in industrial environments, e.g. electric motor and welding, make wireless communication more challenging. The conventional IEEE 802.11 WLANs, which are designed for providing high bandwidth instead of high robustness, are therefore inappropriate for IC-WLAN. On the other hand, if the low data rate feature of industrial control is fully exploited by the state-of-the-art direct sequence spread spectrum (DSSS) technology, much higher robustness can be achieved. We hereby propose using DSSS-CDMA to build IC-WLAN, and exploiting the low data rate feature of industrial control loops for enhanced robustness. We carried out fine-grained physical layer simulations and Monte Carlo comparisons. The results show that DSSS-CDMA IC-WLAN provides much higher robustness than IEEE 802.11 WLAN, so that reliable wireless industrial control loops are made feasible. The DSSS-CDMA IC-WLAN scheme also opens up a new problem space for interdisciplinary study, involving real-time scheduling and resource management, communication, networking and control. In this paper, we study the resource management problems on maximizing robustness and minimizing control utility loss. Analytical resource optimization solutions are given

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

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