We consider the problem of resource provisioning for real-time cyber-physical applications in an open system environment where there does not exist a global resource scheduler that has complete knowledge of the real-time performance requirements of each individual application that shares the resources with the other applications. Regularity-based Resource Partition (RRP) model is an effective strategy to hierarchically partition and assign various resource slices among such applications. However, previous work on RRP model only discusses uniform resource environment, where resources are implicitly assumed to be synchronized and clocked at the same frequency. The challenge is that a task utilizing multiple resources may experience unexpected delays in non-uniform environments, where resources are clocked at different frequencies. This paper extends the RRP model to non-uniform multi-resource open system environments to tackle this problem. It first introduces a novel composite resource partition abstraction and then proposes algorithms to construct and reconfigure the composite resource partitions. Specifically, the Acyclic Regular Composite Resource Partition Scheduling (ARCRP-S) algorithm constructs regular composite resource partitions and the Acyclic Regular Composite Resource Partition Dynamic Reconfiguration (ARCRP-DR) algorithm reconfigures the composite resource partitions in the run time upon requests of partition configuration changes. Our experimental results show that compared with state-of-the-art methods, ARCRP-S can prevent unexpected resource supply shortfall and improve the schedulability up to 50%. On the other hand, ARCRP-DR can guarantee the resource supply during the reconfiguration with moderate computational overhead.

Applying high-speed real-time wireless technologies in industrial applications has the great potential to reduce the deployment and maintenance costs compared to their wired counterparts. Wireless technologies enhance the mobility and reduce the communication jitter and delay for mobile industrial equipment, such as mobile collaborative robots. Unfortunately, most existing wireless solutions employed in industrial fields either cannot support the desired high-speed communications or cannot guarantee deterministic, real-time performance. A more recent wireless technology, RT-WiFi, achieves a good balance between high-speed data rates and deterministic communication performance. It is however developed on commercial-of-the-shelf (COTS) hardware, and takes considerable effort and hardware expertise to maintain and upgrade. To address these problems, this paper introduces the software-defined radio (SDR)-based RT-WiFi solution which we call SRT-WiFi. SRT-WiFi provides full-stack configurability for high-speed real-time wireless communications. We present the overall system architecture of SRT-WiFi and discuss its key functions which achieve better timing performance and solve the queue management and rate adaptation issues compared to COTS hardware-based RT-WiFi. To achieve effective network management with rate adaptation in multi-cluster SRT-WiFi, a novel scheduling problem is formulated and an effective algorithm is proposed to solve the problem. A multi-cluster SRT-WiFi testbed is developed to validate the design, and extensive experiments are performed to evaluate the performance at both device and system levels.

Smart factory automation has an ongoing trend to employ high-speed real-time wireless technologies to interconnect heterogeneous industrial assets to perform various sensing and control services, and support mobile equipment to conduct designated tasks in a collaborative fashion. Applications in automation industries usually have stringent requirements on both high data rates and deterministic real-time performance. Existing efforts, however, either cannot meet the performance requirements or are based on commercial-off-the-shelf (COTS) hardware and cannot provide full-stack configurability [1].

Skill-based robot programming has been extensively investigated in robotic manufacturing systems. Sensor inputs are usually used to determine the correctness of skill execution. However, the effectiveness of sensor monitoring is affected by the limitation of sensor coverage (e.g., camera view), the detection algorithms' physical requirements, and the trajectory of robot motion. Without sufficient sensor coverage, the robot system may be late in capturing critical faults that drastically reduce performance. Furthermore, without proper metrics to quantify the capability of sensor monitoring, it is difficult for non-expert users to know how well the monitor system can capture fault events and their impact on actual task execution time. To address the above issues, we propose a sensing-based quality-aware robot programming guidance system to quantify the capability of sensor monitoring in terms of its execution time and camera coverage. We provide users a flexible way to specify quality specifications for user-defined sections-of-interests. Our system guides users to select proper skill parameters and add additional cameras to meet the quality requirements based on the sensing quality measures. We apply our system framework to a 6DOF robot arm for an object pick-up task.

We consider the problem of resource provisioning for real-time cyber-physical applications in an open system environment where there does not exist a global resource scheduler that has complete knowledge of the real-time performance requirements of each individual application that shares the resources with the other applications. Regularity-based Resource Partition (RRP) model is an effective strategy to hierarchically partition and assign various resource slices among the applications. However, RRP model does not consider changes in resource requests from the applications at run time. To allow for the run time adaptation to change resource requirements, we consider in this paper the issues in online resource partition reconfiguration, including semantics issues that arise in configuration transitions that may cause application failures. Based on the reconfiguration semantics, we study the online resource reconfigurability problem under the RRP model where the availability factors of resource partitions may be reconfigured during run time. We formalize the Dynamic Partition Reconfiguration (DPR) problem and provide a solution to this problem. Extensive experiments have been conducted to evaluate the performance of the proposed approach in different scenarios. We also present a case study using the autonomous F1/10 model car; the controller of the F1/10 car requires resource adaptation to satisfy the computing needs of its PID controller and vision system under different operating conditions. Our implementation demonstrates the effectiveness and benefit of online resource partition reconfiguration using the DPR approach in a real system.

The adoption of real-time wireless technologies within the ever-growing field of networked industrial control systems is continuously gaining popularity. Widespread sensing and actuation devices based on high-throughput wireless standards allow for an increased system mobility and lower configuration and maintenance costs. The IEEE 802.11 standard, especially in its most recent amendments, pushes performance to a very high level, theoretically approaching those of the most common real-time Ethernet networks. Its nondeterministic communication behavior, however, makes 802.11 unsuitable for mission- and safety-critical applications with high-reliability requirements, at least in its standard form. In this paper, we present several major solutions that tackled this issue to achieve real-time and reliability guarantees in wireless networked control systems, capitalizing on the strong efforts devoted to the adoption of IEEE 802.11 physical layer (PHY) technologies. We first provide a deep analysis of the 802.11 protocols in order to propose guidelines toward smart parameter selection at the data-link layer (DLL). In addition, the design of effective rate selection algorithms is considered as a way of increasing both the timeliness and reliability of data delivery. A further systematic solution is represented by real-time (RT)-WiFi, a new time-division multiple-access (TDMA)-based highly configurable DLL protocol that enables high-speed hard real-time data exchange over 802.11 networks. An important goal of this paper is also to provide a thorough comparison among different discussed solutions, in order to put in evidence their advantages and disadvantages, possibly in relation with systems based on different underlying PHYs. We will finally highlight the open challenges and future directions in this active research field.

A cyberphysical avatar is a semi-autonomous robot that adjusts to an unstructured environment and performs physical tasks subject to critical timing constraints while under human supervision. This article first realizes a cyberphysical avatar that integrates three key technologies: body-compliant control, neuroevolution, and real-time constraints. Body-compliant control is essential for operator safety, because avatars perform cooperative tasks in close proximity to humans; neuroevolution (NEAT) enables “programming” avatars such that they can be used by non-experts for a large array of tasks, some unforeseen, in an unstructured environment; and real-time constraints are indispensable to provide predictable, bounded-time response in human-avatar interaction. Then, we present a study on the tradeoffs between three design parameters for robotic task systems that must incorporate at least three dimensions: (1) the amount of training effort for robot to perform the task, (2) the time available to complete the task when the command is given, and (3) the quality of the result of the performed task. A tradeoff study in this design space by using the imprecise computation as a framework is to perform a common robotic task, specifically, grasping of unknown objects. The results were validated with a real robot and contribute to the development of a systematic approach for designing robotic task systems that must function in environments like flexible manufacturing systems of the future.

The quality of SLS products is dramatically degraded by excessive temperature gradients in the thermal profile of the powder bed. Thermal gradients in the presintering temperature, which is defined as powder temperature before laser scans, are inevitable in commercial SLS machines due to various reasons. Such a gradient will propagate to the postsintering temperature, which is defined as the material temperature right after laser scans, if constant laser power is used for sintering. To eliminate thermal gradients in the postsintering temperature, this paper proposes an automatic laser control system to adjust laser power according to the presintering temperature. Infrared cameras are used for presintering temperature measurements, which are used to compute optimal laser power profiles. Two control granularities are implemented: 1) vector-level control eliminates thermal gradients in the postsintering temperature of a single scan line and 2) layer-level control minimizes the difference of postsintering temperature of several areas, each of which consists of a number of scan lines, on the build surface. Experimental results show that variations in the postsintering temperature have been reduced by both implementations (to 60% and 20% respectively) compared to the presintering temperature.

Applying wireless technologies in cyber-physical systems (CPSs) has received significant attention in recent years. In our previous work, a high-speed and flexible real-time wireless communication protocol called RT-WiFi was designed to support a wide range of CPSs, and we presented an implementation with a single access point (AP). To serve the CPS applications with communication nodes geographically distributed over a large area, multicluster RT-WiFi networks with multiple APs need to be deployed. Although effective scheduling algorithms have been designed to schedule tasks in RT-WiFi networks with a single AP, uncoordinated packet transmissions from multicluster RT-WiFi networks may suffer from cochannel interferences that cause performance degradation. The multicluster RT-WiFi network management problem is to resolve the cochannel interference through channel assignment for clusters and through phasing assignment for communication tasks. In this article, we first derive a conjunctive normal form encoding of the problem and design a TScheduler that searches feasible solutions through the SAT solver. A novel LRTree Scheduler is further designed to solve the problem in chain graphs while keeping the number of used channels small and the network management overhead low. A testbed of the multicluster RT-WiFi network is deployed to validate the design of the multicluster RT-WiFi network and evaluate the performance of the proposed scheduling algorithms compared to the contention-based methods in regular WiFi networks. Performance of these scheduling algorithms in large-scale networks is further evaluated through extensive simulations on both static and dynamic multicluster RT-WiFi networks.

Ready-to-assemble furniture is a popular trend for today’s furniture companies such as IKEA due to its relative lower price and easier delivery to customers than assembled furniture. However, assembling furniture from an instruction manual by customers themselves is a tedious task. With the advance in robotics in recent years, having a robot to perform the furniture assembly is a viable idea but the cost of robotic furniture assembly is a barrier, as the overhead of using artificial intelligence techniques such as deep learning can be prohibitive. This paper presents a robotic system with a library of assembly skills that are acquired by machine learning and can be reused for different furniture sets. By applying these skills, the robot can be programmed to automatically perform the assembly task. We describe how to design a robotic task programming system that supports composition of skills and how to specify a complex assembly task to be completed by the robot with its skill set.

Although modern robots in warehousing systems can perform adequately in a goods-to-person model using hand-designed algorithms that are specialized to a particular environment, developing a robotic system that is capable of handling new products at an inexpensive cost remains a challenge. A conspicuous example of this challenge is seen in Amazon's use of autonomous robots to fetch customers' orders in their massive warehouses. To encourage advance in this technology, Amazon organized the competition, Amazon Picking Challenge that asked participants to develop their own hardware and software for the general task of picking a designated set of products from inventory shelves and then placing them at a target location (called a pick-and-place task). Current technology for pick-and-place tasks is still insufficient to meet the demand for low-cost automation. Handling awkward or oddly shaped object must still depend on hand-programming or specialized robotic systems, making manufacturing automation less flexible and expensive. In this paper, we shall present the design and implementation of a software system that is a step in advancing the technology toward full automation at reasonable costs. Our system integrates a set of state-of-the-art techniques in computer vision, deep-learning, trajectory optimization, visual servoing to create a library of skills that can be composed to perform a variety of robotic tasks. We demonstrate the capability of our system for performing autonomous pick-and-place tasks with an implementation using Hoppy, an industrial robotic arm in an environment similar to the Amazon Picking Challenge.

With the ever-growing interests in applying wireless technologies for networked embedded systems to serve as the communication fabric, many real-time wireless technologies have been recently developed to support time-critical sensing and control applications. We proposed in previous work the RT-WiFi protocol that provides real-time high-speed predictable data delivery and enables designs to meet time-critical industrial needs. However, without explicit reliability enforcement mechanisms, our previous RT-WiFi design is either subject to uncontrolled packet loss due to noise and other interferences or may suffer from inefficient communication channel usage. In this article, we explicitly consider interference from both Wi-Fi and non-Wi-Fi based interference sources and propose two sets of effective solutions for reliable data transmissions in RT-WiFi-based networked embedded systems. To improve reliability against general non-Wi-Fi based interference, based on rate adaptation and retransmission techniques, we present an optimal real-time rate adaption algorithm together with a communication link scheduler that has low network management overhead. A novel technique called overbooking is introduced to further improve the schedulability of the communication link scheduler while maintaining the required communication reliability. For Wi-Fi-based interference, we present mechanisms that utilize virtual carrier sensing to provide reliable data transmission while co-existing with regular Wi-Fi networks. We have implemented the proposed algorithms in the RT-WiFi network management framework and demonstrated the system performance with a series of experiments.

In open systems, no global scheduler has knowledge of the complete resource requirements from all the applications. Each application has its own task group and can generate tasks on demand at run time. Regularity-based Resource Partition (RRP) model is an effective strategy to hierarchically allocate resource in such environments. However, when applying the RRP model to multi-resource environments, end-to-end tasks could experience unexpected delay and miss the deadlines. The tasks might arrive at non-resource-slice boundaries because the resource slice sizes of different physical resource may vary in such non-uniform environments. This paper extends the RRP model to non-uniform multi-resource open systems. It introduces a novel composite resource partition abstraction, identifies the feasible conditions for hierarchical regular composite resource partitioning and proposes an acyclic regular composite resource partition scheduling (ARCRPS) algorithm. Simulation results show that compared with the state-of-the-art approach, ARCRPS improves the acceptance ratio by 20% and 25% in uniform and non-uniform multi-resource environments, respectively. A multi-resource scheduling framework jointly considering the CPU and network resources is also designed and implemented to evaluate the feasibility of this theoretical model in practice.

Wireless sensing and networking technologies have taken a strong foothold in the process control industry. The focus has now shifted towards applying control with wireless technology. As such, the current industrial wireless sensor network architectures are under increased scrutiny about their real-time, reliability, and security performances. In this paper, we take a renewed look at network synchronization, the basic building block to support real-time activities. We present our analysis, key observations, and recommendations. We also get into the depth of WirelessHART, the most deployed industrial wireless network architecture, and affirm that, with good practice, we could achieve highly reliable synchronization to provide guaranteed packet deliveries. The correctness of the time synchronization analysis in both line and mesh network topologies is verified through extensive simulation experiments.

Maintaining the freshness of real-time data is one of the crucial design issues in cyber-physical systems (CPS). Past studies have focused on designing update algorithms to minimize the workload imposed by a fixed set of update tasks while ensuring the temporal validity of data. In this paper, we revisit this problem in dynamic cyber-physical systems (DCPS) which may exhibit multi-modal behavior. Any solution to this problem must recognize that: (1) different update algorithms may be needed in different modes according to the workload in each mode, and (2) temporal validity of data must be maintained not only in each mode but also during the mode switch. To strike a balance between data freshness and system schedulability, we propose a utilization-based scheduling selection (UBSS) strategy. We first introduce two synchronous mode switch algorithms, named search-based switch (SBS) and adjustment-based switch (ABS) to search for the proper switch point online and execute all update tasks in the new mode synchronously. SBS checks for temporal validity at the beginning time slot of each idle period in the schedule, while ABS relaxes this restriction through schedule adjustment. To support immediate mode switch, we propose an asynchronous switch algorithm named instant switch (IS) to reduce the switch delay. IS schedules outstanding jobs from the old mode together with the jobs in the new mode using the least-available-laxity-first scheduling policy. Our experimental results demonstrate the effectiveness of these three algorithms. They also show that UBSS strategy can significantly outperform a single fixed update algorithm in terms of maintaining better data freshness while incurring only limited online switch overhead.

We present a study on the tradeoffs between three design parameters for robotic task systems that function in partially unknown and unstructured environments, and under timing constraints. The design space of these robotic tasks must incorporate at least three dimensions: (1) the amount of training effort to teach the robot to perform the task, (2) the time available to complete the task from the point when the command is given to perform the task, and (3) the quality of the result from performing the task. This paper presents a tradeoff study in this design space for a common robotic task, specifically, grasping of unknown objects in unstructured environments. The imprecise computation model is used to provide a framework for this study. The results were validated with a real robot and contribute to the development of a systematic approach for designing robotic task systems that must function in environments like flexible manufacturing systems of the future.

Robotic grasping of a target object without advance knowledge of its three-dimensional model is a challenging problem. Many studies indicate that robot learning from demonstration (LfD) is a promising way to improve grasping performance, but complete automation of the grasping task in unforeseen circumstances remains difficult. As an alternative to LfD, this paper leverages limited human supervision to achieve robotic grasping of unknown objects in unforeseen circumstances. The technical question is what form of human supervision best minimizes the effort of the human supervisor. The approach here applies a human-supplied bounding box to focus the robot's visual processing on the target object, thereby lessening the dimensionality of the robot's computer vision processing. After the human supervisor defines the bounding box through the man-machine interface, the rest of the grasping task is automated through a vision-based feature-extraction approach where the dexterous hand learns to grasp objects without relying on pre-computed object models through the NEAT neuroevolution algorithm. Given only low-level sensing data from a commercial depth sensor Kinect, our approach evolves neural networks to identify appropriate hand positions and orientations for grasping novel objects. Further, the machine learning results from simulation have been validated by transferring the training results to a physical robot called Dreamer made by the Meka Robotics company. The results demonstrate that grasping novel objects through exploiting neuroevolution from simulation to reality is possible.

Wireless networked control systems have received significant attention due to their great advantages in enhanced system mobility, and reduced deployment and maintenance cost. To support a wide range of high-speed wireless control applications, we presented in our prior work the design and implementation of a flexible real-time high-speed wireless communication platform called RT-WiFi. RT-WiFi currently provides up to 6kHz sampling rate and deterministic timing guarantee on packet delivery. While guaranteed delivery latency is essential for networked control, control performance is also impacted by communication jitter and other QoS parameters. To reduce jitter, a flexible network manager is needed to control network-wide scheduling of packet transportation. In this paper, we present an RT-WiFi network manager design and propose efficient solutions for two fundamental RT-WiFi network management problems. To improve control performance in networked control systems, our RT-WiFi network manager is designed to generate data link layer communication schedule with minimum jitter under both static and dynamic network topologies. In order to minimize network management overhead, an efficient data structure called S-tree is invented to manage the communication requests to deal with network dynamics. We have implemented the RT-WiFi network manager, and validated its network and control performance through extensive experiments with a real application.

Although the deferrable scheduling algorithm for fixed priority transactions ( DS-FP) has been shown to provide a better performance compared with the More-Less (ML) method, there is still a lack of any comprehensive studies on the necessary and sufficient conditions for the schedulability of DS-FP. In this paper, we first analyze the necessary and sufficient schedulability conditions for DS-FP, and then propose a schedulability test algorithm for DS-FP by exploiting the fact that there always exists a repeating pattern in a DS-FP schedule. To resolve the limitation of fixed priority scheduling in DS-FP, we then extend the deferrable scheduling to a dynamic priority scheduling algorithm called DS-EDF by applying the earliest deadline first (EDF) policy to schedule update jobs. We also propose a schedulability test for DS-EDF and compare its performance with DS-FP and ML through extensive simulation experiments. The results show that the schedulability tests are effective. Although the schedulability of DS-EDF is lower than DS-FP and the repeating patterns in DS-EDF schedules are longer than those in DS-FP due to the use of dynamic priority scheduling, the performance of DS-EDF is better than both DS-FP and ML in terms of CPU utilization and impact on lower priority application transactions.

Localization in wireless sensor networks is an important functionality that is required for tracking personnel and assets in industrial environments, especially for emergency response. Current commercial localization systems such as GPS suffer from the limitations of either high cost or low availability in many situations (e.g., indoor environments that exclude direct line-of-sight signal reception). The development of industrial wireless sensor networks such as WirelessHART provides an alternative. In this article, we present the design and implementation of ColLoc: a collaborative location and tracking system on WirelessHART as an industrially viable solution. This solution is built upon several technological advances. First, ColLoc adds the roaming functionality to WirelessHART and thus provides a means for keeping mobile WirelessHART devices connected to the network. Second, ColLoc employs a collaborative framework to integrate different types of distance measurements into the location estimation algorithm by weighing them according to their precision levels. ColLoc adopts several novel techniques to improve distance estimation accuracy and decreases the RSSI presurvey cost. These techniques include introducing distance error range constraints to the measurements, judiciously selecting the initial point in location estimation and online updating the signal propagation models in the anchor nodes, integrating Extended Kalman Filter (EKF) with trilateration to track moving objects. Our implementation of ColLoc can be applied to any WirelessHART-conforming network because no modification is needed on the WirelessHART field devices. We have implemented a complete ColLoc system to validate both the design and the effectiveness of our localization algorithm. Our experiments show that the mobile device never drops out of the WirelessHART network while moving around; with the help of even one dependable anchor, using RSSI can yield at least 75% of distance errors below 5 meters, which is quite acceptable for many typical industrial automation applications.

The Internet of Things (IoT) is considered to be the biggest challenge and opportunity for the Internet today. The Internet of Things makes it possible to connect embedded devices in physical environments to the Internet and interact with those devices through both IP and web interfaces. As a subset of the Internet of Things, the wireless embedded Internet targets at enabling resource-limited wireless devices with IP functions and connecting them to the Internet through low-power and low-bandwidth wireless networks. In this paper, we describe our design of the network infrastructure of wireless embedded Internet for industrial automation, and present the implementation and demonstration of a prototype system which integrates WirelessHART mesh networks into the Internet and supports web-based monitoring and control services.

Applying wireless technologies in control systems can significantly enhance the system mobility and reduce the deployment and maintenance cost. Existing wireless technology standards, however either cannot provide real-time guarantee on packet delivery or are not fast enough to support high-speed control systems which typically require 1kHz or higher sampling rate. Nondeterministic packet transmission and insufficiently high sampling rate will severely hurt the control performance. To address this problem, in this paper, we present our design and implementation of a real-time high-speed wireless communication protocol called RT-WiFi. RT-WiFi is a TDMA data link layer protocol based on IEEE 802.11 physical layer to provide deterministic timing guarantee on packet delivery and high sampling rate up to 6kHz. It incorporates configurable components for adjusting design trade-offs including sampling rate, latency variance, reliability, and compatibility to existing Wi-Fi networks, thus can serve as an ideal communication platform for supporting a wide range of high-speed wireless control systems. We implemented RT-WiFi on commercial off-the-shelf hardware and integrated it into a mobile gait rehabilitation system. Our extensive experiments demonstrate the effectiveness of RT-WiFi in providing deterministic packet delivery in both data link layer and application layer, which further eases the controller design and significantly improve the control performance.

Maintaining sensor data validity while exercising timely control is crucial in real-time sensing and control systems. The goal of scheduling algorithms deployed in such systems is to maintain the validity of real-time sensor data so as to maximize the schedulability of update transactions with minimum update workload so that control actions occur on time. In this paper, we first propose a dynamic scheduling algorithm, called Deferrable Scheduling with Least Actual Laxity First (DS-LALF). DS-LALF is designed by extending the deferrable scheduling algorithm, DS-FP which is designed for fixed priority systems. We develop a schedulability test algorithm for DS-LALF based on pattern analysis and a pattern search algorithm to find the shortest and earliest pattern in the schedule. Then, based on DS-LALF, a co-scheduling algorithm called Co-LALF-to schedule update transactions and control transactions in a real-time sensing and control system together-is developed 1) to meet the deadlines of all the control transactions and 2) to maximize the quality of data (QoD) utilized by the control transactions. Co-LALFschedules the jobs in the ascending order of their actual laxities and defers the release times of update jobs as long as the corresponding sensor data are maintained within the required quality. Experimental results show that DS-LALF incurs lower update workload compared with DS-FP and ML, and its schedulability is close to DS-FP but is much better than ML and DS-EDF. The experimental results also show that Co-LALF is effective in improving the overall performance by ensuring better QoD for the real-time data while meeting the deadline constraints of all the control transactions.

In a real-time database system for detection of critical events,On co-scheduling of periodic update and application transactions with fixed priority assignment for real-time monitoring meeting the deadlines of the application transactions and maintaining the quality of the real-time data objects are two critical issues in ensuring the effectiveness of performing the real-time monitoring tasks. Unfortunately, these two goals conflict with each other and are difficult to be achieved at the same time. To address this update and application transaction co-scheduling problem, in this paper, we propose a fixed priority scheduling algorithm called Periodic Co-Scheduling (PCS). PCS uses periodic update transactions to maintain the temporal validity of real-time data objects. It judiciously decides the priority order among all the update and application transactions so that the constructed co-schedule can satisfy the deadline constraints of all the application transactions while maximizing the qualities of the real-time data objects. The effectiveness of the PCS algorithm is validated through our extensive simulation experiments.

WirelessHART™ was released in September 2007 and became an IEC standard in April 2010 (IEC 62591). It is the first open wireless communication standard specifically designed for process measurement and control applications deployed in harsh and noisy environments. WirelessHART distinguishes itself from other public standards by maintaining a central Network Manager. The Network Manager is responsible for maintaining up-to-date routes and communication schedules for the network, thus guaranteeing the reliable and real-time network communications. To deal with the intensive computation requirement in a centralized WirelessHART Network Manager, particularly of middle or large scale network sizes, in this article, we utilize parallelization techniques to implement the Network Manager on embedded multicore architectures. By leveraging the multicore capabilities of the AMD Embedded G-Series Dual-Core processor, we utilize the Texas Multicore Technologies' (TMT) SequenceL™ language and runtime environment to parallelize the algorithms proposed in our previous work for constructing reliable routing graphs and real-time communication schedule. Our experiments show that AMD Embedded G-Series is an ideal platform for medium to large size WirelessHART network and SequenceL™ language can help significantly reduce the development cycle and further improve the algorithm efficiency and system performance in embedded multicore architectures.

Wireless applications in process automation started in areas where wireless sensors provide rich process information to the automation systems. Shortly after WirelessHART became the international standard, both ISA100.11a and WirelessHART claimed that their respective wireless technology could be applied to control as well. Although both standards provide provisions for supporting control over wireless, actual installations of wireless control systems have been slow to be adopted. Due to people's wariness of using wireless in combination with the serious nature of control, what is needed is a demonstration of performance and reliability of control when being executed across wireless media. A good starting point is a comparison between a wireless control system and its wired counterpart. In this paper we first study if we can establish a WirelessHART control loop the same way as a wired one; then we study if our WirelessHART control loop could achieve the same execution rates and reliability as a wired Foundation Fieldbus control loop. The experiment affirms that, in most likely cases, control over a WirelessHART network could be as good as control over a wired fieldbus.

Localization in wireless sensor networks is an important functionality that is required for tracking personnel and assets in industrial environments, especially for emergency response. Current commercial localization systems such as GPS suffer from the limitations of either high cost or low availability in many situations (e.g., in-door environments that exclude direct line-of-sight signal reception). The development of industrial wireless sensor networks such as Wireless Hart provides an alternative. In this paper, we present the design and implementation of Roaming Hart: a collaborative localization system on Wireless Hart as an industrially viable solution. This solution is built upon several technological advances. First, Roaming Hart adds the roaming functionality to Wireless Hart and thus provides a means for keeping mobile Wireless Hart devices connected to the network. Second, Roaming Hart employs a collaborative framework to integrate different types of distance measurements into the location estimation algorithm by weighing them according to their precision levels. Roaming Hart adopts several novel techniques to improve distance estimation accuracy and decreases the RSSI pre-survey cost. These techniques include introducing distance error range constraints to the measurements, judiciously selecting the initial point in location estimation and on line updating the signal propagation models in the anchor nodes. Our implementation of Roaming Hart can be applied to any Wireless Hart-conforming network because no modification is needed on the Wireless Hart field devices. We have implemented a complete Roaming Hart system to validate both the design and the effectiveness of our localization algorithm. Our experiments show that the mobile device never drops out of the Wireless Hart network while moving around, with the help of even one dependable anchor, using RSSI can yield at least 75% of distance errors below 5 meters, which is quite acceptable for many typical industrial automation applications.

Hierarchical scheduling is a hot topic in realtime systems. In a hierarchical real-time system, the resource partition is the intermediate level between physical resources and real-time tasks. A resource partition operates on the shared physical resources at a fraction of the rate, and serves as a scheduling interface between the lower-level real-time tasks and the shared physical resources. Thus a key problem is how to define this scheduling interface on resource partitions. Regularity-bounded methodology is one important type of resource partitioning algorithms. This paper extends Mok and Feng's Regularity-based Resource Partition Model from a single-resource platform to a uniform multiresource platform. We present a resource partitioning algorithm called AAF-Multi Scheduling for solving the time slice overlap problem on a multiresource platform without violating the schedulability bound given by Feng on a single-resource platform. AAF-Multi is a global scheduling algorithm with O(Ω · log Ω) time complexity (Ω = resource amount × hyper period), where hyper period is the least common multiple of the periods of the resource partitions.

The traditional sampling method in process control systems is based on a periodic task model. This is because controllers are executed in a strictly periodic manner. Sensors sample the process data and send it periodically to the appropriate controllers through a communication system such as the field bus. Since the field bus is shared by multiple sensors, there is some delay (control loop latency)between the sampling and control actions. In order to minimize the control loop latency, a higher than necessary sampling frequency is typically adopted, which results in unnecessary waste of energy. In this paper, we propose Min Max: a sampling interval control algorithm for tackling this problem. In Min Max, sampling tasks are not periodic but have both maximum and minimum distance constraints. This sampling model has advantages that are especially important in the domain of wireless control for industrial automation. We shall then discuss the jitter property of sampling schemes under this model and propose algorithms for controlling the sampling intervals of sensors in terms of the Min Max problem (UMin Max) which we shall introduce. Though this problem is NP-hard in general, even for special case of unit-time tasks, we show how to reduce Min Max to well-studied scheduling models such as Liu and Layland-type periodic models and pinwheel models, at the expense of some loss of schedulability. These reductions allow us to derive efficient schedulability tests that can be used to solve the sampling interval control problem in practice. Simulations are used to compare the performance of different UMin Max schedulers in two key figures of merit: the acceptance ratio and the jitter ratio. Simulation of a process control system model also shows that UMin Max can reduce about 40% of the traffic load on the communication system which is especially important for energy-aware wireless process control applications.

In this paper, we report on the design and implementation of MBStar, a higher-frequency, real-time, reliable, secure protocol for wireless body area networks (WBAN). As in most proposals for body sensor networks, MBStar adopts the star topology for communication, and is designed to support a message rate as high as 400 Hz, which to the best of our knowledge, is the highest among low-power wireless communication protocols implemented at the present time. The physical layer of MBStar utilizes 802.15.4 DSSS compatible radio for which a higher-frequency, reliable, TDMA MAC layer is built. There is a simple application layer designed for security on top of it. MBStar utilizes public/private key encryption for provisioning devices and does not involve any human configuration before device join. Considering the resource limit of most embedded systems, the TDMA requirement of computing a shared global communication schedule presents a practical problem since it may not be feasible for all the devices to communicate in a long hyper-period while the communication schedule between devices is being created or modified as devices depart and rejoin. We solve this problem by keeping only the global hyper-period schedule on the gateway side, with each device being configured with a shorter, local period. Then, retransmission is employed to resolve any conflicts between the devices. Our strategy has the property that, given any fixed task set, the minimal average number of retransmissions is independent of any communication scheduling algorithm, and the EDF (Earliest Deadline First) is optimal for our communication architecture. Finally, we present experimental results that demonstrate that MBStar is an effective protocol for wireless body area networks.

Typical real-time sensing and control systems consist of a set of update tasks for installing sensor measurements from the operation environment and a set of control tasks to access to these measurements for making control decisions. Although configuring the sensors with higher sampling rates could improve the accuracy of the measurements and control quality in general, scheduling high frequent update jobs may seriously affect the schedulability of the control tasks. Missing or delaying the control tasks may severely degrade the overall control performance of the system. In this paper, instead of using the traditional periodic update model, we adopt the a periodic update model in generating update jobs for maintaining data validity. We propose an adaptive co-scheduling algorithm called Least Idle Slot First (LISF) to schedule the update tasks and control tasks with the purposes to meet the deadlines of the control tasks and maximize the quality of control (QoC) offered by the control tasks. LISF schedules the jobs in the ascending order of the number of available idle slots before their deadlines and defers the release times of update jobs as long as the corresponding data objects are maintained within the required quality. The experiment results show that LISF can effectively improve the system schedulability and the control performance in the real-time sensing and control systems.

Industrial wireless mesh networks are deployed in harsh and noisy environments for process measurement and control applications. Compared with wireless community networks, they have more stringent requirements on communication reliability and real-time performance. Missing or delaying of the process data by the network may severely degrade the overall control performance. In this paper, we abstract the primary reliability requirements in typical industrial wireless mesh networks and define three types of reliable routing graphs for different communication purposes. We present efficient algorithms to construct them and describe the recovery mechanisms in the event of component failures. Based on these graphs, data link layer communication schedules are generated to achieve end-to-end real-time performance. We demonstrate through extensive experimental results that our algorithms can achieve highly reliable routing, improved communication latency and stable real-time communication in large-scale networks at the cost of modest overhead in device configuration.

Peak power consumption of buildings in large facilities like hospitals and universities becomes a big issue because peak prices are much higher than normal rates. During a power demand surge an automated power controller of a building may need to schedule ON and OFF different environment actuators such as heaters and air quality control while maintaining the state variables such as temperature or air quality of any room within comfortable ranges. The green scheduling problem asks whether a scheduling policy is possible for a system and what is the necessary and sufficient condition for systems to be feasible. In this paper we study the feasibility of the green scheduling problem for HVAC(Heating, Ventilating, and Air Conditioning) systems which are approximated by a discrete-time model with constant increasing and decreasing rates of the state variables. We first investigate the systems consisting of two tasks and find the analytical form of the necessary and sufficient conditions for such systems to be feasible under certain assumptions. Then we present our algorithmic solution for general systems of more than 2 tasks. Given the increasing and decreasing rates of the tasks, our algorithm returns a subset of the state space such that the system is feasible if and only if the initial state is in this subset. With the knowledge of that subset, a scheduling policy can be computed on the fly as the system runs, with the flexibility to add power-saving, priority-based or fair sub-policies.

This paper presents the design and analyzes the performance of a reliable communication scheme for the traffic control system built upon a wireless process control protocol, aiming at enhancing the robustness and timeliness of the safety-critical control applications. By exploiting the slot-based predictable access and the grid topology of urban area road networks, the proposed scheme establishes one primary and secondary route from the controller to each node and allocates the time slots accordingly. This is facilitated by a split-merge operation that makes a sender node sense the primary channel(channel to the primary receiver) and take the secondary channel only if the first one is not free in a single slot, while making the receiver first listen to the primary sender and switch to the secondary sender. Our scheme also finds the path with the lowest error rate by modeling the split-merge operation as a single virtual link and applying shortest path algorithm. The experimental results show that the proposed scheme greatly enhances the transmission success ratio for the grid-style traffic control network and the improvement scales up with the network size. In addition, the routing scheme can further find the path that can improve the delivery ratio of control messages compared with the traditional grid routing scheme.

Unlike wired networks, the configuration and the behavior of wireless networks are heavily dependent on many environmental factors. While this makes it more difficult to build a wireless network testbed whose behavior is controllable, it also makes the availability of such a testbed all the more desirable. Indeed, the difficulties in building a good wireless mesh testbed belie the fact that most research work on mesh network performance is backed up only by computer simulations. In this paper, we present a practical design philosophy in which a realistic and controllable wireless mesh network testbed is built with a relatively small deployment of physical equipments by exploiting the idea of a virtual network. Specifically, we simulate a virtual network within the testbed and use one physical wireless transceiver to simulate multiple virtual devices. An observer who only reads the transmitted wireless messages will not be able to tell the difference from a real wireless mesh. Our approach has been adopted in a recent industry-standard testing suite, namely, Wi-HTest. In this paper, we shall discuss our experience in building Wi-HTest by applying the virtual network approach.

A real-time scheduler is robust (sustainable) for a certain task set if its schedulability is preserved under lighter system load by the scheduler. The first part of this paper shows that NPr (non-preemptive) robustness of a zero-concrete periodic task set against increase in period is sufficient to guarantee NPr robustness for all variants of the task set. This proof includes the corresponding concrete or non-concrete periodic and sporadic task sets against any kind of reduction in system load. Based on this result, the second part of this paper gives the necessary and sufficient conditions for robustness for both NPr fixed-priority (NPFP) and NPr earliest-deadline first (NPEDF) schedulers under both discrete time and dense time assumption separately.

WirelessHART was released in September 2007 and is the first open wireless communication standard specifically designed for real-time process control applications. It is designed to the same standards as its wired counterpart for reliability and interoperability. To ensure the compliance with the HART Communication Protocol and the adherence to its strict timing requirements, all WirelessHART devices must be thoroughly tested and registered with the HART Communication Foundation (HCF). In this paper, we present Wi-HTest, the test suite designed to exercise WirelessHART devices, thus facilitating compliance assessment. We discuss the detailed architecture of Wi-HTest and highlight several critical features like packet handling with accurate timing control and fault data injection. We also describe a sniffer called Wi-Analys for capturing WirelessHART packets along with their timing information and a post process suite for analyzing the packets. These three tools together provide the complete compliance verification environment for WirelessHART. Based on the test specification developed by HCF, a representative test case is conducted for the purpose of demonstration. This test case in turn shows that Wi-HTest is a novel and efficient test suite for verifying the compliance of real-time WirelessHART devices.

WirelessHART is an emerging wireless communication standard that is targeted at the real-time process control industry.An example application of wireless communication in an industrial process control plant is the location of field engineers. The capability to locate personnel is a safety critical issue in process control plants because of high risks posed by toxic chemicals and other hazards. This paper presents the design, implementation and evaluation of a location-aware application built upon WirelessHART. The aim of this application is to locate a mobile device (and thus the person carrying the device) via the deployed WirelessHART network. The application is a software-based - no device modifications are required. Consequently, it is applicable to any WirelessHART network. In this application, both the mobile device (a handheld device or a badge carried by a worker) and field devices (attached to the plant process) periodically send health reports of their neighbors to the network manager. The network manager analyzes these reports and discards the untrustworthy pairs through comparison. Next, the network manager feeds the average received signal indications to a well-trained radio propagation model to derive the location. To evaluation our solution, several preliminary experiments are carried out and the results are very promising, with a median error less than 4 meters, which is good enough for the industrial requirement. To the best of our knowledge, this is the first attempt to develop location-aware application in WirelessHART networks.

Maintaining the temporal validity of real-time data is one of the crucial issues in a real-time database system. Past studies focus on designing algorithms to minimize imposed workload by a fixed set of update transactions while maintaining data freshness within validity intervals. In this paper we revisit this problem by investigating the cost of data freshness maintenance and online scheduling overhead in the presence of mode changes in real-time systems. We propose to apply periodic scheduling policies when the imposed update workload is low to maintain high data freshness. When the update workload becomes high, we propose to switch to more sophisticated algorithms to improve schedulability. In the latter case, not only each scheduling policy must be able to schedule the task set in the corresponding mode, temporal validity must also be maintained during the mode changes. To address this problem, two algorithms, named search-based switch (SBS) and adjustment-based switch (ABS) are proposed to search for the proper switch point online. SBS checks the temporal validity at the beginning time slot of each idle period while ABS further relaxes this restriction through schedule adjustment. Our experimental results demonstrate the correctness and efficiency of these two algorithms. Our results also show that scheduling switch according to the runtime processor workload can significantly outperform a single fixed scheduling policy in terms of data freshness while incurring only limited online switch overhead.

The schedulability testing for the deferrable scheduling algorithm for fixed priority transactions (DS-FP) remainsan open problem since its introduction. In this paper, wetake the first step towards investigating necessary and sufficient conditions for the DS-FP schedulability. We propose a necessary and sufficient schedulability condition for the algorithm in discrete time systems, and prove its correctness. Based on this condition, we propose a schedulability test algorithm that is more accurate than the existing test that is only based on a sufficient condition. Our algorithm exploits the fact that there is always a repeating pattern in a DS-FP schedule in discrete time systems. We demonstrate through examples that our schedulability test algorithm outperforms the existing algorithm in terms of accuracy.

Abstract — To overcome the inherent lossy property of wireless links and increase network throughput, many multi-path routing protocols have been proposed to improve the reliability and latency of packet delivery in wireless networks. Multi-path routing protocols, however, do not take advantage of existing coding opportunities to maximize network throughput. In this paper, we propose a novel coding-aware multi-path routing protocol (CAMP), which forwards packets over multiple paths dynamically based on path reliability and coding opportunity. CAMP employs a route discovery mechanism which returns to the source multiple paths along with ETX (Expected Transmission Count) of all links on each path. Using a novel forwarding mechanism, CAMP splits the traffic among multiple paths and actively creates instead of passively waiting for coding opportunity by switching its path to maximize the switching gain. Experimental results demonstrate that CAMP can achieve much higher throughput than comparable schemes for delivering packets in wireless networks. I.

Wireless technology has been regarded as a paradigm shifter in the process industry. The first open wireless communication standard specifically designed for process measurement and control applications, WirelessHART was officially released in September 2007 (as a part of the HART 7 Specification). WirelessHART is a secure and TDMA-based wireless mesh networking technology operating in the 2.4GHz ISM radio band. In this paper, we give an introduction to the architecture of WirelessHART and share our first-hand experience in building a prototype for this specification. We describe several challenges we had to tackle during the implementation, such as the design of the timer, network wide synchronization, communication security, reliable mesh networking, and the central network manager. For each challenge, we provide a detailed analysis and propose our solution. Based on the prototype implementation, a simple WirelessHART network has been built for the purpose of demonstration. The demonstration network in turn validates our design. To the best of our knowledge, this is the first reported effort to build a WirelessHART protocol stack.

This paper formulates and illustrates the integration of resource safety verification into a design methodology for development of verified and robust real-time embedded systems. Resource-related concerns are not closely linked with current xUML model-based software development although they are critical for embedded systems. We describe how to integrate resource analysis techniques into the early phase of an xUML-based development cycle. Our hybrid framework for resource safety verification combines static resource analysis and runtime monitoring. A case study based on an embedded controller for satellite simulation, TableSat, illustrates the benefits obtained by incorporating resource verification into design and combining static analysis and runtime monitoring.

WirelessHART was released in September 2007 and is the first open wireless communication standard specifically designed for process control applications. As an optional part of the HART® Communication Protocol, WirelessHART is designed to the same standards for reliability and interoperability. To ensure the compliance and adherence to the high level of interoperability defined by the HART Communication Foundation (HCF), all WirelessHART devices must be thoroughly tested and registered with the HCF. In this paper, we present Wi-HTest, the test engine designed to exercise WirelessHART devices, thus facilitating compliance assessment. We discuss the detailed architecture of Wi-HTest and highlight several critical features like virtual devices and fault data injection.

WirelessHART is the first open wireless standard for the process control industry. Previously we demonstrated a three-node prototype network based on an early release of the protocol stack. In this demonstration we build a fully operational WirelessHART sensor network of multiple nodes. We show the creation of the network and the execution of process monitoring applications on the network. This new demonstration network serves as a proof of concept for the revised WirelessHART standard and as a platform for our future research and experiments.

Data uncertainty is a common problem for the real-time monitoring of data streams. In this paper, we address the issue of efficiently monitoring the satisfaction/violation of user-defined constraints over data streams where the data uncertainty can be probabilistically characterized. We propose a monitoring architecture SPMON that can incorporate probabilistic models of uncertainty in constraint monitoring. We adapt the concept of data similarity in real-time databases to the processing of uncertain data streams. In doing so, we generalize the data similarity by a new concept psr (probabilistic similarity region) that allows us to define similarity relations for probabilistic data with respect to the set of constraints being monitored. This enables the construction of lightweight filters for saving bandwidth. We also show how to efficiently update the filter conditions at run-time.

In many emerging time-critical applications, the exact time of event occurrences may not be known. In such cases, events can be represented as a probabilistic occurrence within a time interval. Thus, monitoring of timing constraints, generally used in time- critical systems, needs to incorporate the uncertainty of event occurrences. In this paper, we propose mechanisms to monitor the satisfaction/violation of timing constraints that can be assessed probabilistically. We assume a uniform distribution of event occurrence within a time interval. Our proposed algorithm determines whether the probability that a timing constraint has been satisfied exceeds a specified threshold value. A confidence threshold is a minimum satisfaction probability of the timing constraint. A timing constraint is violated if the confidence threshold is not reached. We design an efficient monitoring algorithm for detecting timing violations of a set of timing constraints by finding the earliest expiration time (EET) for each timing constraint. Since it is critical to derive implicit constraints for early detection of violation of timing constraints, we present the derivation of the implicit constraints under uncertainty using an all-pairs shortest path algorithm. Further, we propose pruning techniques to discard unnecessary implicit constraints. We present the properties and proofs of our approach.

This paper addresses the problem of processing eventtiming queries over event streams where the uncertainty in the values of the timestamps is characterizable by histograms. We describe a stream-partitioning technique for checking the satisfaction of a probabilistic timing constraint upon event arrivals in a systematic way in order to delimit the "probing range" in event streams. This technique can be formalized as a probabilistic timing join (PTJoin) operator where the join condition is specified by a time window and a confidence threshold in our model. We present efficient PTJoin algorithms that tightly delimit the probing range and efficiently invalidate events in event streams.

Wireless sensor networks have been a very active research field in the past few years. However, most of extant research has focused on wireless sensing, such as environmental and habitat monitoring [6]. In this paper, we investigate the feasibility of applying wireless technologies in industrial real-time process control systems. We define a minimum set of assumptions about the underlying sensor networks in order to achieve realtime support for process control. These assumptions are necessary and practical from an industrial perspective. We formulate the modeling of a wireless process control configuration as a multi-processor scheduling problem. The resulting scheduling problem is solved by the scheduler synthesis tool MSP.RTL [7] to produce a valid configuration for deployment. The deployment, because of the way it is derived, will provide real-time wireless support for the controlled processes. Simulation results on data from real plant configurations show that this approach can also drastically reduce potential interferences between wireless transfers.

This paper provides a comprehensive approach to the problem of monitoring timing constraints over event streams for which the timestamp values are inherently uncertain. We first propose a generic framework for capturing the early detection of the violation of timing constraints, based on the notion of probabilistic violation time. In doing so, we provide a systemic approach for deriving a set of necessary constraints at compilation time. Our work is innovative in that the framework is formulated to be "modular" with respect to the probability distributions on timestamp values. We demonstrate the applicability of the framework for two different timestamp models, Gaussian and histogram. The Gaussian model is appropriate for representing event timing from a wide variety of sensors with well-modelled physical noise characteristics; we show how we can efficiently derive the probabilistic violation time of timing constraints by exploiting the relation between the Gaussian distribution parameters. The histogram model can be used where the timestamps of events are available from measurements only as arbitrary probability distributions: we show how to derive an efficient timing constraint monitoring method for the histogram model

In a wireless sensor network, a sensor measures environmental data. It also relays data for other sensors. While sensing workload is the same among sensors, relaying workload differs. Sensors closer to the data sink carry more data traffic. This becomes more prominent as the network scales up. The drawback of this is that nodes in the network degrade unevenly and the network ages in a non-uniform way. This paper seeks the ways to deploy the network so that the workload is evenly distributed, thus the network overall behavior degrades in a smooth fashion. Assuming that the sensors should be evenly deployed within the monitored area, we look at the approach where a set of more powerful nodes are designated for data relaying. We look at the approach to deploy relaying nodes that are easy to implement in practice. In particular, we select sub-regions to deploy relaying nodes at calculated density. We propose a simple method where the density is simply based on the size of the area whose data is relayed by these nodes.

With processor speed doubling every 18 months, more and more system functionalities are implemented as software (SW) in the design process of embedded systems. Selecting the "right" RTOS before the SW is developed is very important. In this paper, we present an RTOS modeling tool based on SystemC. It is configurable to support modeling and timed simulation of most popular embedded RTOSs. Timing fidelity is achieved by using delay annotation. The OS timing information is derived from published benchmark data. Experiments show that the accuracy of our approach is able to help designers gain confidence in their RTOS selection. By avoiding using an instruction set simulator, the simulation can be speeded up by more than 3 orders of magnitude. Any other component integrable with SystemC can also be integrated in our simulation environment.

In a pure sensor network thousands of sensors are distributed over a large area. Sensor data is relayed from sensor node to node until it reaches the edge node, where it is then routed by wire to the host. In this paper we study the effect of data collection on the battery and buffer of a sensor node, and on the overall sensor network. We determine the relationship among battery life, sampling frequency, buffer size, etc. We claim that using identical sensors throughout a large scale sensor network may not achieve the best result. We suggest some guidelines for deploying a large scale sensor network. We then propose routing algorithms that are robust, truly distributed, and efficient in utilizing the sensor network.

Unlike preemptive scheduling policies, non-preemptive real-time scheduling policies can exhibit anomalies even for the single-processor case. In particular, a task set that is schedulable by a non-preemptive scheduler may become unschedulable when the utilization of the task set decreases relative to the CPU speed, e.g., when a faster CPU is used to run the same task set. In this paper, we define the notion of robustness to capture the essence of the scheduling anomaly on real-time system performance. We shall show that it is difficult to test for robustness in general but there are sufficient conditions for guaranteeing robustness.

A real-time task usually generates data. The study on real-time tasks either ignores this fact like most of the research do, or models data as execution time like when handling multimedia data. On the other hand, the network research community usually pays little attention to the data source other than assuming certain characteristics. There are many real world applications where data is not generated at a constant rate during task execution, and the average data rate is not the same among tasks. In this paper we study a new task model with data output as an explicit parameter. We analyze the data output of such task set. We shall derive the data source parameters assumed by network studies. Different scheduling policy results in different data output curve, we look at this in detail with simulations. Our work extends the real-time research to cover a new set of real world applications; it also complements the network study on data transmission.

A preschedule is a static schedule without assuming constant and completely predictable rate of resource supply. A generalized prescheduling framework and a sound, complete, and PTIME preschedule generator was proposed in Wang et al. (2004) based on linear programming (LP). Since infinitely small time slices are not implementable for resources with context switch overhead, it is desirable to define and solve the prescheduling problem on the domain of integers so that context switching can occur only at boundaries of time quantums. However, integral LP (ILP) is NP-hard in the strong sense in general, so the ILP approach is not applicable and better techniques are needed. This paper answers this challenge by giving a sound, complete and PTIME rational-to-integral preschedule transformer based on a technique which we call "round-and-compensate".

Increasingly, business applications need to capture consumers' complex preferences interactively and monitor those preferences by translating them into event-condition-action (ECA) rules and syntactically correct processing specification. An expressive event model to specify primitive and composite events that may involve timing constraints among events is critical to such applications. Relying on the work done in active databases and real-time systems, this research proposes a new composite event model based on real-time logic (RTL). The proposed event model does not require fixed event consumption policies and allows the users to represent the exact correlation of event instances in defining composite events. It also supports a wide-range of domain-specific temporal events and constraints, such as future events, time-constrained events, and relative events. This event model is validated within an electronic brokerage architecture that unbundles the required functionalities into three separable components - business rule manager, ECA rule manager, and event monitor - with well-defined interfaces. A proof-of-concept prototype was implemented in the Java programming language to demonstrate the expressiveness of the event model and the feasibility of the architecture. The performance of the composite event monitor was evaluated by varying the number of rules, event arrival rates, and type of composite events.

We propose an algorithm for monitoring timing constraints to satisfy confidence threshold requirements when there is uncertainty in the exact timing of event occurrences. In our model, a timed event trace is examined for possible satisfaction/violation with respect to a given set of timing constraints. Every event occurrence has a timestamp given by a time interval. Assuming that the time of occurrence is uniformly distributed over the time interval, our algorithm determines whether the probability that a timing constraint has been satisfied exceeds a specified threshold value. Timing constraints are composed of deadline and delay constraints for which satisfaction probabilities are defined. A confidence threshold is a minimum satisfaction probability of the timing constraint. A timing constraint is violated if the confidence threshold is not reached by the timed event trace. We present a ptime monitoring algorithm for detecting timing violation by finding the earliest expiration time (EET) of the deadline timer for each of the cases P = 100%, 50% /spl les/ P < 100%, and 0% < P < 50%, where P is the confidence threshold of the timing constraint. We give a derivation of the implicit constraints needed for computing the EET, and we show how to use an all-pairs shortest path algorithm to compute the implicit constraints.

We propose a class of real-time data access protocols called SSP (similarity stack protocol). The correctness of SSP schedules is justified by the concept of similarity which allows different but sufficiently timely data to be used in a computation without adversely affecting the outcome. SSP schedules are deadlock-free, subject to limited blocking, and do not use locks. We give a schedulability bound for SSP and also report simulation results which show that SSP is especially useful for scheduling real-time data access on multiprocessor systems. Finally, we present a variation of SSP which can be implemented in an autonomous fashion in the sense that scheduling decisions can be made with local information only.

The integration of mobile agents with SNMP creates significant advantages for the management of complex networks. Nevertheless, the security concerns of mobile agent technology limit its acceptance in practice. A key issue is to safeguard resource usage abuse by malicious or buggy mobile agents on the hosting system. This paper describes how the TINMAN architecture, a framework and a suite of tools for enforcing resource safety of mobile code is applied to mobile SNMP agents. TINMAN uses a suite of resource-usage checking tools which consists of a resource bound predictor a usage certification generator and a verifier at compile-time, and certificate validation and monitoring tools at run-time. This paper shows how TINMAN tools can provide 100% coverage by a combination of off-line static analysis and run-time monitoring in enforcing safety on resource consumption of mobile SNMP agents. Experimental results from the current TINMAN implementation are given.

Efficient algorithms have been developed by a number of authors to detect constraint violation or satisfaction of timed events. In extant work, the time of every event occurrence is assumed to be known exactly. However there are practical situations where we are not sure about the exact time of occurrence of an event but we may be able to capture the uncertainty by a time interval. In this paper we propose new types of timing constraints: possible and certain constraints that are pertinent to an event model where timestamps are given by time intervals. We extend previous work in timed event monitoring that is time-point based to our interval-based model. We give an efficient algorithm for monitoring timing constraints under event timing uncertainty, and sketch its proof of correctness by extending the pruning algorithm on the constraint graph to cover interval timestamps.

In real-time resource partitioning, a shared resource is partitioned by a resource-level scheduler such that each partition is accessible only by an individual application task group. Tasks within the same task group are scheduled by an application-task-level scheduler that is specialized to the real-time requirements of the tasks in the group. An ideal goal for resource partitioning in real-time systems is to achieve a complete separation of concerns so that: (1) each task group may be executed as if it had access to its own dedicated resource, and (2) there is minimal interaction between the resource-level scheduler and the application-task-level scheduler. In [15], we introduced the notion of a real-time virtual resource which operates at a fraction of the rate of the shared physical resource and whose rate of operation varies with time but is bounded. In this paper we discuss an approach to bound the variation of the rate of operation of a real-time virtual resource by characterizing the rate variation from both temporal and supply dimensions and by expanding on the concept of regularity that was first introduced in [19]. For the case of regular resource partitioning, we show that the utilization bounds of both fixed-priority scheduling and dynamic-priority scheduling remain unchanged from those for dedicated resources. We determine the utilization bounds for the more general case of irregular partitioning. In particular, both types of partitions can be efficiently constructed by exploiting compositionality, properties vis-a-vis the regularity measure.

Window-Constrained Scheduling is one of the task models proposed in recent years for scheduling periodic realtime tasks where service must be guaranteed in only a fraction. of the periods. In RTSS'2000, a Dynamic Window-Constrained Scheduling (DWCS) algorithm was proposed by West and Poellabauer (2000) for multiplexing multiple packet streams where the number of consecutive packet lost must be bounded. In this paper we show that the DWCS algorithm can fail for arbitrarily low aggregate utilization rates of the packet streams. We shall show that Window-Constrained Scheduling is NP-hard in the strong sense. However if the execution time of all jobs is of unit size, as might be modelled in some packet stream applications, then a schedule must exist as long as the aggregate utilization rate is no more than the number of processors (packet switching resources). Some subclasses of the Window-Constrained Scheduling for unit-size jobs can be transformed to the well known Liu and Layland model or the more recent Pfair model and can therefore be scheduled optimally and at low scheduling cost. In considering the general unit-size-job case, we note that nonproportionate progress in scheduling Window-Constrained tasks is often the cause of unschedulability, no matter how low the aggregate utilization rate is. We shall define the notion of Pfairness in relation to the Window-Constrained Scheduling model so as to quantitatively describe the concept of strictly proportionate progress. An EDF (Earliest-Deadline-First) based algorithm will be defined for the Window-Constrained Scheduler problem. This algorithm is computationally efficient, on-line, and Pfair A sufficient schedulability test for this EDF-based algorithm is proved.

Simulation and verification are two conventional techniques for the analysis of specifications of real-time systems. While simulation is relatively inexpensive in terms of execution time, it only validates the behavior of a system for one particular computation path. On the other hand, verification provides guarantees over the entire set of computation paths of a system, but is, in general, very expensive due to the state-space explosion problem. We introduce a new technique: simulation-verification combines the best of both worlds by synthesizing an intermediate analysis method. This method uses simulation to limit the generation of a computation graph to that set of computations consistent with the simulation. This limited computation graph, called a simulation-verification graph, can be one or more orders of magnitude smaller than the full computation graph. A tool, XSVT, is described which implements simulation-verification graphs. Three paradigms for using the new technique are proposed. The paper illustrates the application of the proposed technique via an example of a robot controller for a manufacturing assembly line.

Timeliness is an important attribute for e-brokerage both in the detection of opportunities in a narrow time window and also in facilitating differentiation of end-to-end quality of service (QoS). In this paper, we demonstrate how real-time event monitoring techniques can be applied to time-critical e-brokerage. We start with a formal timed event model which provides the semantics for specifying complex timing correlation rules in composite events. The formal event model of the system is based on RTL (Real Time Logic), which is important for disambiguating informal specifications when multiple instances of the same event type may appear in a timing correlation rule involving composite events. This leads to our design of an e-brokerage, online stock monitoring and alerting system which enables users to express their complex preferences and provides an alert service to users in a timely manner. The user's preferences are monitored by a real-time event monitor. We report the design of this system and some performance data characterizing some key timing parameters. Our system is being used by a class of MBA students in a field test.

This paper formalizes the concept of similarity which has been used on an ad hoc basis by application engineers to provide more flexibility in concurrency control. We show how the usual correctness criteria of concurrency control, namely, final-state, view, and conflict serializability, can be weakened to incorporate similarity. We extend the weakened correctness criteria described previously for real-time applications which may run continually, have concurrent transaction executions, or skip unimportant computations. A semantic approach based on the similarity concept is then taken to propose a sufficient condition for scheduling real-time transactions without locking of data.

The multiframe model of hard-real-time tasks is a generalization of the well-known periodic task model of C. Liu and J. Layland (1973). The feasibility analysis of systems of multiframe tasks which are assigned priorities according to the rate-monotonic priority assignment scheme is studied. An efficient sufficient feasibility test for such systems of multiframe tasks is presented and proved correct-this generalizes a result of A.K. Mok and D. Chen (1997).

With the increasing complexity of enterprise networks and the Internet, event correlation is playing an increasingly important role in network as well as integrated system management systems. Even though the timing of events often reveals important diagnostic information about event relationships and should therefore be represented in event correlation rules or models, most extant approaches lack a formal mechanism to define complex temporal relationships among correlated events. In this paper, we discuss the formal use of composite events for event correlation and present a composite event specification approach that can precisely express complex timing constraints among correlated event instances, for which efficient compilation and detection algorithms have been developed in Mok et al., (1997). A Java implementation of this approach, called Java Event Correlator (JECTOR), is described, and some preliminary experimental results of using JECTOR in an experimental network management environment are also discussed in the paper.

The concept of data similarity was introduced by T.-W. Kuo and A.K. Mok (1996) to capture the semantics of real time applications where the consistency requirement of a transaction can be relaxed modulo a binary relation on the data space. Even though the notion of data similarity is naturally suited to many applications in the process control industry, its adoption is hampered by the lack of an easy interface to COTS (commercial-off-the-shelf) components. We report our ongoing work in incorporating the idea of data similarity into embedded applications, especially in the process control industry. Our approach is to allow designers to specify similarity predicates by means of an SQL-like interface to the client applications. Query processing is performed by a compact firm-real-time database engine called SRDE (Similarity-based Real-time Database Engine). SRDE is object oriented and is designed to manage real-time data efficiently in a distributed environment. By exploiting data similarity, SRDE can be used to minimize data traffic according to the client's specifications. SRDE has been implemented in 100% JAVA that supports JDBC API. We demonstrate the use of SRDE in a typical industrial control application.

We propose a toolset for designing real-time systems. The toolset is based on a design methodology for real-time systems. The purpose of a design methodology is to provide a set of procedures and guidelines that, with human intervention and interaction, allow designers to systematically obtain implementations of systems that conform precisely to their design specifications. Our methodology is designed for automation. We present the toolset and case study of the design of a simple VCR system. The methodology is based on a formal model and precise descriptions of the components of the system. The underlying model of our methodology is composed of a control level and a data-flow level that, together with a resource scheduler and the application-specific code, make up the system under design.

A model for periodic tasks is proposed that explicitly incorporates jitter-the uncertainty in the arrival times of individual frames. Feasibility-analysis of systems of such tasks is studied in the context of dynamic-priority, preemptive, uniprocessor scheduling. From a computational complexity perspective, the problem is shown to be no more difficult than feasibility analysis in systems of periodic tasks that do not exhibit jitter. Several feasibility analysis algorithms are presented and proven correct.

How to exploit application semantics to improve the performance of a real-time data-intensive application has been an active research topic in the past few years. Weaker correctness criteria and semantics-based concurrency control algorithms were proposed to provide more flexibility in reordering read and write events. Distinct from the past work, this paper exploits the tradeoff between data consistency and system workload. The definition of similarity is combined with the idea of transaction skipping to provide a theoretical foundation for reducing the workload of a transaction system. We also propose guidelines to adjust the execution frequencies of a static set of transactions and prove their correctness. The strengths of this work were verified by simulation experiments on an air traffic control example (Peng et al., 1997).

As real time applications become more complex and distributed, monitoring for timing constraint compliance becomes more important in facilitating the enforcement of conditional guarantees and for recovery purposes. C.E. Chodrow et al. (1991) described a O(n/sup 3/) satisfiability checking algorithm for timing constraint monitoring at each check point, where n is the number of time terms in the timing constraint specification. We show that a timing violation can be caught as early as possible by deriving and monitoring a minimum set of timing constraints from the timing constraint specification. We show that only O(n) time is needed in the worst case for checking at each check point. An implementation based on the results reported herein appears in a companion paper (A.K. Mok and G. Liu, 1997).

We provide a framework for discussing how to adjust load in order to handle periodic processes whose timing parameters vary with time. The schedulability of adjustable periodic processes by a preemptive fixed priority scheduler is formulated in terms of a configuration selection problem for which a PTIME solution is shown. When the list of allowable configurations is implicitly given by a set of scalable periodic processes, the corresponding period assignment problem is shown to be NP-Complete. We present an approximation algorithm for the period assignment problem for which we show some encouraging experimental results.

In this article, we consider symbolic model checking for event-driven real-time systems.We first propose a Synchronous Real-Time Event Logic (SREL) for capturing the formal semantics of synchronous, event-driven real-time systems.The concrete syntax of these systems is given in terms of a graphical programming language called Modechart, by Jahanian and Mok, which can be translated into SREL structures.We then present a symbolic model-checking algorithm for SREL.In particular, we give an efficient algorithm for constructing OBDDs (Ordered Binary Decision Diagrams) for linear constraints among integer variables.This is very important in a BDD-based symbolic model checker for real-time systems, since timing and event occurrence constraints are used very often in the specification of these systems.We have incorporated our construction algorithm into the SMV v2.3 from Carnegie-Mellon University and have been able to achieve one to two orders of magnitude in speedup and space saving when compared to the implementation of timing and event-counting functions by integer arithmetics provided by SMV.

The well known periodic task model of C.L. Liu and J.W. Layland (1973) assumes a worst case execution time bound for every task and may be too pessimistic if the worst case execution time of a task is much longer than the average. We give a multiframe real time task model which allows the execution time of a task to vary from one instance to another by specifying the execution time of a task in terms of a sequence of numbers. We investigate the schedulability problem for this model for the preemptive fixed priority scheduling policy. We show that a significant improvement in the utilization bound can be established in our model.

A key index of the performance of a rule-based program used in real-time monitoring and control is its response time. We first extend the definition of response time of an EQL rule-based program for distributed computation. To reduce the response time through distributed computation, we decompose an EQL program into disjoint modules. We then describe a tool which computes the response-times of finite-state EQL rule-based programs according to the imprecise computation paradigm, i.e., this tool always yields a range which is monotonically tightened as more time is spent in the computation. During the computation, a user can interrupt the analyzer and get both an intermediate result which is a guaranteed bound and a bound-quality factor which quantifies the tightness of this result. Our approach uses fast textual analysis to get initial bounds. It then performs a heuristic search by pruning the state-transition graph to improve the bound quality. A program-decomposition technique for reducing the search effort is also discussed. An analysis example on an EQL program involving 2/sup 59/ states is presented.

The well-known periodic task model of Liu and Layland (1973) assumes a worst-case execution time bound for every task and may be too pessimistic if the worst-case execution time of a task is much longer than the average. We give a multiframe real-time task model which allows the execution time of a task to vary from one instance to another by specifying the execution time of a task in terms of a sequence of numbers. We investigate the schedulability problem for this model for the preemptive fixed priority scheduling policy. We show that a significant improvement in the utilization bound can be established in our model.

MSP.RTL is a tool for producing real time schedulers for a wide variety of timing constraints. The input to MSP.RTL can be customized for different application domains, as long as their timing semantics can be expressed in RTL (real time logic). The scheduler synthesis algorithm treats the real time scheduling problem as a temporal constraint satisfaction problem with additional resource constraints. The current version of MSP.RTL computes cyclic schedules for multiprocessor systems in a three part process: the first part constructs a temporal constraint graph representing the input timing specification. The second part finds a set of solutions of the temporal constraint graph by using a combination of constraint satisfaction and an incremental positive cycle detection algorithm. The third part searches the set of solutions to find a feasible schedule which satisfies the resource constraints by exploiting search strategies and results from real time scheduling theory. We have used the MSP.RTL tool to solve same benchmark problems including a sanitized version of the Boeing 777 Integrated Airplane Information Management System (AIMS).

As software control of time-critical functions in embedded systems becomes more common, a means for the precise specification of their behavior and formal methods for analyzing system requirements become increasingly important. Modechart is a graphical specification language introduced to meet this need. The main focus of this paper is on methods and supporting tools for representing and reasoning about properties of time-critical systems specified in Modechart. The paper describes a verification methodology which takes advantage of the structuring inherent in a Modechart specification to determine whether a system specification satisfies the required properties. The paper also describes the implementation of a mechanical verifier, based on the proposed approach, which has been recently integrated as part of the Modechart Toolset prototype development environment from the Naval Research Lab [7].

Summary form only given, as follows. Static models are not appropriate for next-generation distributed real-time applications that are likely to be adaptive in nature, (for example, to provide a high degree of fault tolerance). During the last few years, the real-time systems community has started to counter this criticism by extending traditional work to cover newer application domains, The central problem remains, however, that the concept of adaptivity is often domain-specific and sometimes ill-defined in the context of bringing distributed real-time systems concept into better focus. Accordingly, be it resolved that future distributed embedded and real-time applications will be adaptive and that meanings, challenges and research paradigms await discovery. The charge to the panel is to defend (or to dismiss as fluff) the above resolution.

The Modechart specification language is a formalism for the specification of real-time systems. A toolset for specification, analysis and simulation for Modechart specifications exists for supporting the design and construction of real-time systems. This paper introduces a new tool in the toolset: a compiler for a class of Modechart specifications, namely, that of deterministic system specifications, extended by a subclass of the non-deterministic system specifications. The object code that the compiler generates is in ESTEREL, a member of the synchronous family of programming languages for real-time systems. We discuss a broad approach to the implementation of timing specifications, providing a range of implementation options, from the basic time step unrolling of states in ESTEREL, to the use of system timers. The compiler presented herein allows the specifier to obtain a correct implementation of a Modechart program, including timing constraints.

A key index of the performance of a rule based program used in real time monitoring and control is its response time, defined by the longest program execution time before a fixed point of the program is reached from a start state. Previous work in computing the response time bounds for rule based programs effectively assumes that all rules take the same amount of firing time. It is also assumed that if two rules are enabled, then either one of them may be scheduled first for firing. These assumptions can result in loose bounds, especially in the case programmers choose to impose a priority structure on the set of rules. We remove the uniform firing cost assumption and discuss how to get tighter bounds by taking rule priority information into account. We show that the rule suppression relation we previously introduced can be extended to incorporate rule priority information. A bound derivation algorithm for programs whose potential trigger relations satisfy an acyclicity condition is presented, followed by its correctness proof and an analysis example.>

We describe a purely declarative method for introducing modularity into forward-chaining, rule-based languages and its embodiment in the Venus rule language. The method is enforced by the syntax of the language and includes the ability to parameterize the rule groups. Drawing from two of three Venus applications developed to date, we illustrate how this form of modularity contributes directly to the resolution of certain software engineering problems associated with rule languages.>

A key index of the performance of a rule-based program used in real-time monitoring and control is its response time, defined by the maximum number of rule firings before a fixed point of the program is reached from a start state. Previous work in computing the response-time bounds for rule-based programs assumes that if two rules are enabled, then either one of them may be scheduled for firing. This assumption may be too conservative in the case when programmers choose to impose a priority structure on the set of rules. In this paper, we discuss how to get tighter bounds by taking rule-priority information into account. We show that the rule-suppression relation we previously introduced can be extended to incorporate rule-priority information. A bound-derivation algorithm for programs whose potential-trigger relations satisfy an acyclicity condition is presented, followed by its correctness proof and an analysis example.>

Present a specification language for real-time systems called Modechart. The semantics of Modechart is given in terms of real-time logic (RTL), which is especially amenable to reasoning about the absolute (real-time clock) timing of events. The semantics of Modechart has an important property that the translation of a Modechart specification into RTL formulas results in a hierarchical organization of the resulting RTL assertions. This gives us significant leverage in reasoning about properties of a system by allowing us to filter out assertions that concern lower levels of abstraction. Some results about desirable properties of Modechart specifications are given. A graphical implementation of Modechart has been completed.>

We propose a class of real-time data access protocols called SSP (Similarity Stack Protocol). The correctness of SSP schedules is justified by the concept of similarity which allows different but sufficiently timely data to be used in a computation without adversely affecting the outcome. SSP schedules are deadlock-free, subject to limited blocking and do not use locks. We give a schedulability bound for SSP and also report simulation results which show that SSP is especially useful for scheduling real-time data access on multiprocessor systems. Finally, we present a variation of SSP which can be implemented in an autonomous fashion in the sense that scheduling decisions can be made with local information only.>

We consider symbolic model-checking for event-driven real-time systems. The concrete syntax of these systems is given in terms of a graphical programming language called Modechart. We propose a logic, Synchronous Real-Time Event logic (SREL) for specifying the timing properties of these systems. We then present a symbolic model-checking algorithm which checks a modechart against an SREL formula, and discuss several implementation issues. In particular, we give an efficient solution to the problem of encoding timing and event counting functions based on Binary Decision Diagram (BDD). This solution has been incorported into the SMV system v2.3 and has been able to achieve one to two orders of magnitude in speedup and space saving when compared to the solution based on the integer operations provided by the SMV system.>

In this article, we propose a language, Asynchronous Propositional Temporal Logic (APTL), for the specification and verification of distributed hard real-time sytems. APTL extends the logic TPTL by dealing explicitly with multiple local clocks. We propose a distributed-system model which permits definition of inequalities asserting the temporal precedence of local clock readings. We show the expressiveness of APTL through two nontrivial examples. Our logic can be used to specify and reason about such important properties as bounded clock rate drifting. We then give a 2 2 0(n) tableau-based decision procedure for determining APTL satisfiability, where n is the size (number of bits) of the input formula.

Rule-based expert systems are increasingly used to monitor and control the operations of complex real-time systems which require intensive knowledge-decision processing and human expertise. These embedded AI systems must respond to events in the rapidly changing external environment so that the results of the expert system's computation in each monitor-respond cycle are valid in safely operating the real-time system. Determining how fast an expert system can respond under all possible situations is a difficult problem. We have developed an efficient analysis methodology for a large class of rule-based EQL programs to determine whether a program in this class has bounded response time. In particular, we have identified several sets of primitive behavioral constraint assertions: an EQL program which satisfies all constraints in one of these sets of assertions is guaranteed to have bounded response time. Here, we enhance the applicability of our analysis technique by introducing a facility with which the rule-based programmer can specify application-specific knowledge that is too difficult to be mechanically detected in the new language Estella in order to determine the performance of an even wider range of programs. We also describe efficient algorithms for implementing the analysis tools.>

Article Free Access Share on Formal specification of asynchronous distributed real-time systems by APTL Authors: Farn Wang View Profile , Al Mok View Profile , E. Allen Emerson View Profile Authors Info & Claims ICSE '92: Proceedings of the 14th international conference on Software engineeringJune 1992 Pages 188–198https://doi.org/10.1145/143062.143113Published:01 June 1992Publication History 4citation137DownloadsMetricsTotal Citations4Total Downloads137Last 12 Months5Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

The semantics are discussed of data-intensive real-time applications for which serializability is too recursive for consistency management. By examining the semantics of these applications the authors formalize the concept of similarity which has been used on an ad hoc basis by application engineers to provide more flexibility in concurrency control. Weaker consistency requirements based on the similarity concept are proposed. The concept of similarity is used to extend the usual correctness criteria for transaction scheduling: finite-state, view, conflict serializability to their counterparts of final-state Delta -serializability, view Delta -serializability, and conflict Delta -serializability.>

A framework is given for discussing how to adjust load in order to handle periodic processes whose timing parameters vary with time. The schedulability of adjustable periodic processes by a preemptive fixed priority scheduler is formulated in terms of a configuration selection problem. Specifically, two process transformations are introduced for the purpose of deriving a bound for the achievable utilization factor of processes whose periods are related by harmonics. This result is then generalized so that the bound is applicable to any process set and an efficient algorithm to calculate the bound is provided. When the list of allowable configurations is implicitly given by a set of scalable periodic processes, the corresponding period assignment problem is shown to be NP-complete. The authors present an approximation algorithm for the period assignment problem for which some encouraging experimental results are included.>

Consideration is given to the preemptive scheduling of hard-real-time sporadic task systems on one processor. The authors first give necessary and sufficient conditions for a sporadic task system to be feasible (i.e., schedulable). The conditions cannot, in general, be tested efficiently (unless P=NP). They do, however, lead to a feasibility test that runs in efficient pseudo-polynomial time for a very large percentage of sporadic task systems.>

The response time analysis of rule-based expert systems is discussed. The rule-based production system MRL (macro-rule-based language) is introduced. MRL has been designed to facilitate more accurate analysis of the response times of programs while maintaining the flexibility and expressiveness of traditional production systems such as OPS5. Research on modular analysis of rule-based systems is described. Several timing analysis algorithms based on this approach have been developed. One of them, a fixed-point detection algorithm is discussed to show that efficient and effective analysis of MRL programs can be achieved. In particular, a general technique called the transfer principle is introduced for exploiting analysis algorithms which are simpler to analyze. The design of the match algorithm Rhyme, an algorithm uniquely suited for more accurate analysis of the performance of real-time expert systems, is presented.>

A study is made of the real-time performance of a class of rule-based programs written in the language EQL. Response time is defined in terms of the computation paths of a program leading to fixed points; investigated is the complexity of the problem of analyzing these programs to meet response-time requirements. It is shown that the response-time analysis problem is in general undecidable and is PSPACE-hard in the case where all the variables have finite domains. A general analysis strategy which seems to be quite effective in practical cases is proposed. This strategy aims at avoiding the combinatorial state-space explosion problem inherent in brute-force approaches. Based on this strategy, a suite of analysis tools has been implemented to verify that the variables in an EQL program always converge to stable values in bounded time. The tools have been successfully applied to real-life programs.>

The problems of hard-real-time task scheduling in a multiprocessor environment are discussed in terms of a scheduling game representation of the problem. It is shown that optimal scheduling without a priori knowledge is impossible in the multiprocessor case even if there is no restriction on preemption owing to precedence or mutual exclusion constraints. Sufficient conditions that permit a set of tasks to be optimally scheduled at run time are derived.>

This paper presents a graph-theoretic algorithm for safety analysis of a class of timing properties in real-time systems which are expressible in a subset of real time logic (RTL) formulas. Our procedure is in three parts: the first part constructs a graph representing the system specification and the negation of the safety assertion. The second part detects positive cycles in the graph using a node removal operation. The third part determines the consistency of the safety assertion with respect to the system specification based on the positive cycles detected. The implementation and an application of this procedure will also be described.

The authors formalize the safety analysis of timing properties in real-time systems. The analysis is based on a formal logic, RTL (real-time logic), which is especially suitable for reasoning about the timing behavior of systems. Given the formal specification of a system and a safety assertion to be analyzed, the goal is to relate the safety assertion to the systems specification. There are three distinct cases: (1) the safety assertion is a theorem derivable from the systems specification; (2) the safety assertion is unsatisfiable with respect to the systems specification; or (3) the negation of the safety assertion is satisfiable under certain conditions. A systematic method for performing safety analysis is presented.