Emerging Industrial Internet-of-Things systems require wireless solutions to connect sensors, actuators, and controllers as part of high data rate feedback-control loops over real-time flows. A key challenge is to provide predictable performance and agility in response to fluctuations in link quality, variable workloads, and topology changes. We propose WARP to address this challenge. WARP uses programs to specify a network's behavior and includes a synthesis procedure to automatically generate such programs from a high-level specification of the system's workload and topology. WARP has three unique features: (1) WARP uses a domain-specific language to specify stateful programs that include conditional statements to control when a flow's packets are transmitted. The execution paths of programs depend on the pattern of packet losses observed at runtime, thereby enabling WARP to readily adapt to packet losses due to short-term variations in link quality. (2) Our synthesis technique uses heuristics to improve network performance by considering multiple packet loss patterns and associated execution paths when determining the transmissions performed by nodes. Furthermore, the generated programs ensure that the likelihood of a flow delivering its packets by its deadline exceeds a user-specified threshold. (3) WARP can adapt to workload and topology changes without explicitly reconstructing a network's program based on the observation that nodes can independently synthesize the same program when they share the same workload and topology information. Simulations show that WARP improves network throughput for data collection, dissemination, and mixed workloads on two realistic topologies. Testbed experiments show that WARP reduces the time to add new flows by 5 times over a state-of-the-art centralized control plane and guarantees the real-time and reliability of all flows.

In this work, two access point (AP) selection mechanisms called STOOP and MD-STOOP are presented for enterprise wireless local area networks (WLANs). STOOP utilizes first- order stochastic dominance (FSD) tools to develop a runtime algorithm that probes the network to compare the quality of service from multiple APs in a stochastic manner. MD-STOOP utilizes the concept of mean dominance (MD) to select APs, which provides good average case performance with less overhead than STOOP. Performance of the two algorithms is evaluated through extensive simulations in comparison to the state-of-the-art. It is shown that STOOP and MD-STOOP outperform existing solutions and directions for further improvements are discussed.

Emerging applications of wireless sensor networks (WSNs) require real-time quality-of-service (QoS) guarantees to be provided by the network. Due to the nondeterministic impacts of the wireless channel and queuing mechanisms, probabilistic analysis of QoS is essential. One important metric of QoS in WSNs is the probability distribution of the end-to-end delay. Compared to other widely used delay performance metrics such as the mean delay, delay variance, and worst-case delay, the delay distribution can be used to obtain the probability to meet a specific deadline for QoS-based communication in WSNs. To investigate the end-to-end delay distribution, in this paper, a comprehensive cross-layer analysis framework, which employs a stochastic queueing model in realistic channel environments, is developed. This framework is generic and can be parameterized for a wide variety of MAC protocols and routing protocols. Case studies with the CSMA/CA MAC protocol and an anycast protocol are conducted to illustrate how the developed framework can analytically predict the distribution of the end-to-end delay. Extensive test-bed experiments and simulations are performed to validate the accuracy of the framework for both deterministic and random deployments. Moreover, the effects of various network parameters on the distribution of end-to-end delay are investigated through the developed framework. To the best of our knowledge, this is the first work that provides a generic, probabilistic cross-layer analysis of end-to-end delay in WSNs.

Emerging applications of wireless sensor networks (WSNs) require real-time event detection to be provided by the network. In a typical event monitoring WSN, multiple reports are generated by several nodes when a physical event occurs, and are then forwarded through multi-hop communication to a sink that detects the event. To improve the event detection reliability, usually timely delivery of a certain number of packets is required. Traditional timing analysis of WSNs are, however, either focused on individual packets or traffic flows from individual nodes. In this paper, a spatio-temporal fluid model is developed to capture the delay characteristics of event detection in large-scale WSNs. More specifically, the distribution of delay in event detection from multiple reports is modeled. Accordingly, metrics such as mean delay and soft delay bounds are analyzed for different network parameters. Motivated by the fact that queue build up in WSNs with low-rate traffic is negligible, a lower-complexity model is also developed. Testbed experiments and simulations are used to validate the accuracy of both approaches. The resulting framework can be utilized to analyze the effects of network and protocol parameters on event detection delay to realize real-time operation in WSNs. To the best of our knowledge, this is the first approach that provides a transient analysis of event detection delay when multiple reports via multi-hop communication are needed.

Hierarchical scheduling allows reservation of processor bandwidth and the use of different schedulers for different applications on a single platform. We propose a hierarchical scheduling interface called synchronized deferrable servers that can reserve different processor bandwidth on each core, and can combine global and partitioned scheduling on a multicore platform. Significant challenges will arise in the response time analysis of a task set if the tasks are globally scheduled on a multiprocessor platform and the processor bandwidth reserved for the tasks on each processor is different, as a result, existing works on response time analysis for dedicated scheduling on identical multiprocessor platforms are no longer applicable. A new response time analysis that overcomes these challenges is presented and evaluated by simulations. Based on this new analysis, we show that evenly allocating bandwidth across cores is "better" than other allocation schemes in terms of schedulability, and that the threshold between lightweight and heavyweight tasks under hierarchical scheduling may be different from the threshold under dedicated scheduling.

Providing QoS and performance guarantees to arbitrarily divisible loads has become a significant problem for many cluster-based research computing facilities. While progress is being made in scheduling arbitrarily divisible loads, current approaches are not efficient and do not scale well. In this paper, we propose a linear algorithm for real-time divisible load scheduling. Unlike existing approaches, the new algorithm relaxes the tight coupling between the task admission controller and the task dispatcher. By eliminating the need to generate exact schedules in the admission controller, the algorithm avoids high overhead. We experimentally evaluate the new algorithm. Simulation results demonstrate that the algorithm scales well, can schedule large numbers of tasks efficiently, and performs similarly to existing approaches in terms of providing real-time guarantees.

Application of runtime monitoring to maintain the health of an embedded real-time software system requires that anomalous behavior be detected within a bounded time while preserving the temporal guarantees of the underlying system. Existing results can compute bounds on the detection latency of runtime monitors that are realized as a deferrable server running at the highest priority. In this paper, we generalize those results to allow monitors to run at an arbitrary priority. We also present an analysis of queue length in predictable runtime monitoring, which allows one to compute an upper bound on queue length. When implementing predictable runtime monitoring, system engineers are presented with several challenges in configuring the parameters of monitor servers. To address those challenges, we explore the tradeoffs among key server parameters and make recommendations about how best to select those parameters to achieve system monitoring objectives.

Limited energy resources in wireless sensor networks (WSNs) call for a comprehensive cross-layer analysis of energy consumption in a multi-hop network. In this paper, we provide a stochastic analysis of the energy consumption in a random network environment. Accordingly, a comprehensive cross-layer analysis framework, which employs a stochastic queueing model in realistic channel environments, is developed. This framework accurately predicts the distribution of energy consumption for nodes in WSNs during a given time period. We show that when the time duration is long, the energy consumption asymptotically approaches a Normal distribution. Using the distribution of energy consumption, the distribution of node lifetime is also investigated. With the help of this probabilistic model, a case study with an anycast protocol is conducted to show how the developed framework can analytically predict the distribution of energy consumption and lifetime. Comprehensive simulations and testbed experiments are provided to validate the developed model. The cross-layer framework is also used to identify relationships between the distribution of energy consumption and network parameters, such as network density, duty cycle, and traffic rate. To the best of our knowledge, this is the first work to investigate probabilistic distribution of energy consumption in WSNs.

Dynamic program monitoring has been applied in software-intensive systems to detect runtime constraint violations and trigger system recovery actions. Uncontrolled monitoring activities may, however, delay detection of a violation for an unbounded time and, worse, affect the original system's schedulability. In this paper, we introduce the concept of predictable monitoring, which demands a bound on detection latency while ensuring temporal non-interference by the monitoring process. We present off-line analysis techniques for predicting the maximum detection latency with fixed-priority scheduling under two types of monitoring schemes: synchronous and asynchronous. For asynchronous monitoring, we illustrate how to achieve predictable monitoring by bounding the detection latency and controlling the monitoring budget using a bandwidth-preserving, server-based approach.

Emerging applications of wireless sensor networks (WSNs) require real-time quality of service (QoS) guarantees to be provided by the network. However, designing real-time scheduling and communication solutions for these networks is challenging since the characteristics of QoS metrics in WSNs are not well known yet. Due to the nature of wireless connectivity, it is infeasible to satisfy worst-case QoS requirements in WSNs. Instead, probabilistic QoS guarantees should be provided, which requires the definition of probabilistic QoS metrics. To provide an analytical tool for the development of real-time solutions, in this paper, the distribution of end-to-end delay in multi-hop WSNs is investigated. Accordingly, a comprehensive and accurate cross-layer analysis framework, which employs a stochastic queueing model in realistic channel environments, is developed. This framework captures the heterogeneity in WSNs in terms of channel quality, transmit power, queue length, and communication protocols. A case study with the TinyOS CSMA/CA MAC protocol is conducted to show how the developed framework can analytically predict the distribution of end-to-end delay. Testbed experiments are provided to validate the developed model. The cross-layer framework can be used to identify the relationships between network parameters and the distribution of end-to-end delay and accordingly, to design real-time solutions for WSNs. Our ongoing work suggests that this framework can be easily extended to model additional QoS metrics such as energy consumption distribution. To the best of our knowledge, this is the first work to investigate probabilistic QoS guarantees in WSNs.

Providing QoS and performance guarantees to arbitrarily divisible loads has become a significant problem for many cluster-based research computing facilities. While progress is being made in scheduling arbitrarily divisible loads, previous approaches have no support for advance reservations. However, with the emergence of grid applications that require simultaneous access to multi-site resources, supporting advance reservations in a cluster has become increasingly important. In this paper we propose a new divisible load real-time scheduling algorithm that supports advance reservations in a cluster. Our approach not only enforces the real-time agreement but also addresses the under-utilization concerns raised by advance reservations. The impact of advance reservations on system performance is systematically studied. Simulation results show that, with the proposed algorithm and appropriate advance reservations, the system performance could be maintained at the same level as the no reservation case.

This paper presents a method for determining the feasible processing window for a leader robot that controls a group of follower robots. A processing window is defined as the time interval from the instant the platform starts collecting data to the moment the robot leader finishes planning and communicates with follower robots. The method determines the minimum processing window after considering the different bounds affecting the control of the robot, such as of robot’s processing power, robot sensors and the motion of the robots in the group. We present a derivation of the bounds that affect the processing window of the leader robot and an algorithm for determining the feasible window or adjusting the parameters that affect the processing window in case a feasible processing window cannot be achieved because of an overload condition. The application considered in this paper is a group of mobile robots that self deploy, retrieve, and reconfigure barrels to improve the safety of highway construction/maintenance workers.

Mobile robotic systems must sense constraints imposed by a dynamically changing environment and predictably react to those changes in real-time. Complexity arises in mobile robotic systems because the computing platform travels through the environment with which the system is interacting. These systems have spatio-temporal requirements in the sense that correct behavior is defined in terms of both space and time. The focus of this paper is mobile robotic platforms that must sense their environment and avoid obstacles as they navigate from one point to another. We present a design and analysis methodology for these platforms that integrates spatio-temporal attributes with fixed priority realtime scheduling through the use of zone and processing window abstractions. We propose an algorithm for adjustment of the processing window in order maximize the speed of the robot as it faces obstacles in the environment.

Providing QoS and performance guarantees to arbitrarily divisible loads has become a significant problem for many cluster-based research computing facilities. While progress is being made in scheduling arbitrarily divisible loads, some of proposed approaches may cause inserted idle times (IITs) that are detrimental to system performance. In this paper we propose a new approach that utilizes IITs and thus enhances the system performance. The novelty of our approach is that, to simplify the analysis, a homogenous system with IITs is transformed to an equivalent heterogeneous system, and that our algorithms can schedule real-time divisible loads with different processor available times. Intensive simulations show that the new approach outperforms the previous approach in all configurations. We also compare the performance of our algorithm to the current practice of manually splitting workloads by users. Simulation results validate the advantages of our approach.

Cluster computing has emerged as a new paradigm for solving large-scale problems. To enhance QoS and provide performance guarantees in cluster computing environments, various real-time scheduling algorithms and workload models have been investigated. Computational loads that can be arbitrarily divided into independent pieces represent many real-world applications. Divisible load theory (DLT) provides insight into distribution strategies for such computations. However, the problem of providing performance guarantees to divisible load applications has not yet been systematically studied. This paper investigates such algorithms for a cluster environment. Design parameters that affect the performance of these algorithms and scenarios when the choice of these parameters have significant effects are studied. A novel algorithmic approach integrating DLT and EDF (earliest deadline first) scheduling is proposed. For comparison, we also propose a heuristic algorithm. Intensive experimental results show that the application of DLT to real-time cluster-based scheduling leads to significantly better scheduling approaches

Multimedia applications need support for both real-time computation and real-time communications because of their sensitivity to delay and jitter. It therefore requires the operating system to provide soft real-time support in the processor and the network subsystems. In this work, we present a network subsystem, which can cooperate with any CPU scheduler to provide network quality of service (QoS) to multimedia applications. This system, called VRE-NET, allows applications to reserve bandwidth for the protocol processing capacity of the network subsystem. The bandwidth reservation can be adjusted according to different QoS requirements. We provide a mechanism for users to associate each multimedia application with a rate controller that automatically adjusts the bandwidth reservation. The implementation was done in the Linux 2.6.0 kernel.

Much research has focused on power conservation for the processor, while power conservation for I/O devices has received little attention. In this paper, we analyze the problem of online energy-aware I/O scheduling for hard real-time systems based on the preemptive periodic task model. We propose an online energy-aware I/O device scheduling algorithm: energy-efficient device scheduling (EEDS). The EEDS algorithm utilizes device slack to perform device power state transitions to save energy, without jeopardizing temporal correctness. An evaluation of the approach shows that it yields significant energy savings with respect to no dynamic power management (DPM) techniques

The challenge in conserving energy in embedded real-time systems is to reduce power consumption while preserving temporal correctness. Much research has focused on power conservation for the processor, while power conservation for I/O devices has received little attention. In this paper, we analyze the problem of online energy-aware I/O scheduling/or hard real-time systems based on the preemptive periodic task model with non-preemptible shared resources. We extend the concept of device slack to support non-preemptible shared resources; and propose an online energy-aware I/O scheduling algorithm: energy-efficient device scheduling with non-preemptible resources (EEDS_NR). The EEDS_NR algorithm utilizes device slack to perform device power state transitions to save energy, without jeopardizing temporal correctness. An evaluation of the approach shows that it yields significant energy savings

We present an autonomous, mobile, robotics application that requires dynamic adjustments of task execution rates to meet the demands of an unpredictable environment. The Robotic Safety Marker (RSM) system consists of one lead robot, the foreman, and a group of guided robots, called robotic safety markers (a.k.a., barrels). An extensive analysis is conducted of two applications running on the foreman. Both applications require adjusting task periods to achieve desired performance metrics with respect to the speed at which a system task is completed, the accuracy of RSM placement, or the number of RSMs controlled by the foreman. A static priority scheduling solution is proposed that takes into consideration the strict deadline requirements of some of the tasks and their dynamic periods. Finally, a schedulability analysis is developed that can be executed online to accommodate the dynamic performance requirements and to distinguish between safe operating points and potentially unsafe operating points.

This work is an application of the variable-rate execution (VRE) model in Linux to support dynamic quality of service (QoS). Based on conventional time-sharing scheduling algorithms, Linux does not adequately support QoS requirements. The VRE scheduler can assign a specified execution rate to any application, and dynamically adjust the execution rate during runtime. Rate controller components are introduced to adjust a task's execution rate based on predefined rules and runtime feedbacks, such as the suspension time, the queue length, and so on. A significant feature of this work is its ability to support legacy applications at the binary level. On conventional operating systems, millions of applications have been built under time-sharing schedulers, which we call legacy applications. Under the VRE model, a legacy application can obtain a guaranteed variable execution rate. We also designed a simple default rate controller for legacy multimedia applications. The Linux kernel was slightly modified in our implementation to achieve reconfigurability. Both the VRE scheduler and the default rate controller are implemented as Linux loadable modules, which can be dynamically loaded into the kernel to replace the Linux scheduler or change the behavior of the scheduler. We provide a set of interfaces for users to design and use their own schedulers and rate controllers.

We present the design and implementation of a real-time model for the global control of robotic highway safety markers. Problems addressed in the system are: 1) poor scalability and predictability as the number of markers increases, 2) jerky movement of markers, and 3) false-hits caused by environment objects. We extensively analyze the system and offer two solutions: a basic solution and an enhanced solution. They are built respectively upon two task models: the periodic task model and the variable rate execution task model. The former is characterized by four static parameters: phase, period, worst case execution time and relative deadline. The latter has similar parameters. Its parameter values, however, are allowed to change at arbitrary times. We then examine two typical real-time scheduling approaches: rate monotonic (RM) priority driven and earliest deadline first (EDF). Analysis of their sufficient conditions shows that our system is feasibly schedulable under either RM or EDF. This conclusion justifies that the path for each safety marker can be guaranteed to be smooth under the designed real-time system. For the scalability issue, we present a sufficient condition for the upper bound on the number of barrel robots that can be reliably controlled. One key technique integrated into our real-time system is the Hough transform. We refine its traditional implementation so that, for the task of detecting safety markers, the time complexity decreases and the reliability increases with only slight additional storage for search windows. The basic idea behind our improvements is to limit the search window for safety markers.

A theory of resource sharing in a mixed system with hard real-time and non-real-time processing requirements is presented. The real-time processing is modeled as rate-based execution (RBE) tasks whose resource needs are known in advance. The non-real-time processing is modeled as aperiodic requests and dynamically mapped to weight-based variable rate execution tasks. The resource sharing requirements of the aperiodic requests are unknown a priori and only become known when a critical section is reached. A scheduling algorithm that supports resource sharing without deadlock in such a mixed system is presented with a sufficient off-line schedulability condition.

Dynamic voltage scaling (DVS) algorithms save energy by scaling down the processor frequency when the processor is not fully loaded. Many algorithms have been proposed for periodic and aperiodic task models but none support the canonical sporadic task model. A DVS algorithm, called DVSST, is presented that can be used with sporadic tasks in conjunction with preemptive EDF scheduling. The algorithm is proven to guarantee each tasks meets its deadline while saving the maximum amount of energy possible with processor frequency scaling. DVSST was implemented in the /spl mu/C/OS-II real-time operating system for embedded systems and its overhead was measured using a stand-alone Rabbit 2000 test board. Though theoretically optimal, the actual power savings realized with DVSST is a function of the sporadic task set and the processor's DVS support. It is shown that the DVSST algorithm achieves 83% of the theoretical power savings for a robotic highway safety marker real-time application. The difference between the theoretical power savings and the actual power savings is due to the limited number of frequency levels the Rabbit 2000 processor supports.

Aperiodic requests with unknown execution times and unknown arrival patterns are dynamically mapped to rate-based execution (RBE) tasks with variable rates and scheduled such that the real-time tasks are guaranteed to meet their deadlines. The aperiodic requests dynamically share the available processor capacity without reserving a fixed processor capacity for any one aperiodic request (or class of requests). This approach was selected over the traditional approach of using a static set of server tasks to process aperiodic requests so that the available processor capacity could be proportionally shared between active aperiodic requests.

Real-time signal-processing applications for high assurance systems are commonly designed using a processing-graph software architecture. Here we demonstrate the management of latency and buffer requirements in such an architecture—the US Navy's processing graph method (PGM). By applying recent results in real-time scheduling theory to the subset of PGM employed by the US DARPA rapid prototyping of application-specific signal processors (RASSP) synthetic aperture radar (SAR) benchmark application, we identify inherent real-time properties of nodes in a PGM graph, and demonstrate how these properties can be exploited to perform useful and important system-level analyses such as schedulability analysis, end-to-end latency analysis, and memory requirements analysis. More importantly, we develop relationships between properties such as latency and buffer bounds and show how one may be traded off for the other.

Server responsiveness and scalability are more important than ever in today's client/server dominated network environments. Researchers have begun to consider cluster-based computers using commodity hardware as an alternative to expensive specialized hardware for building scalable Web servers. In this paper, we present performance results comparing two cluster-based Web servers based on different server infrastructures: MAC-based dispatching (LSMAC) and IP-based dispatching (LSNAT). Both cluster-based server systems were implemented as application-space programs running on commodity hardware. We point out the advantages and disadvantages of both systems. We also identify when servers should be clustered and when clustering will not improve performance.

We present a task model for the real-time execution of event-driven tasks in which no a priori characterization of the actual arrival rates of events is known; only the expected arrival rates of events is known. The model, called rate-bared execution (RBE), is a generalization of Mok's sporadic task model. The RBE model is motivated naturally by distributed multimedia and digital signal processing applications. We derive necessary and sufficient conditions for determining the feasibility of an RBE task set and demonstrate that earliest deadline first (EDF) scheduling is an optimal scheduling algorithm for both preemptive and nonpreemptive execution environments, as well as hybrid environments wherein RBE tasks access shared resources. Our analysis of RBE tasks demonstrates a fundamental distinction between deadline based scheduling methods and static priority based methods. We show that for deadline-based scheduling methods, feasibility is solely a function of the distribution of task deadlines in time. This is contrasted with static priority schedulers where feasibility is a function of the actual arrival rates of work for tasks. Thus whereas the feasibility of static priority schedulers is a function of the periodicity of tasks, the feasibility of deadline schedulers is independent of task arrival processes and hence deadline schedulers are more suitable for use in distributed, event-driven, real-time systems.

The Processing Graph Method (PGM)-a dataflow model widely used in the design and analysis of embedded signal-processing applications-is studied from a real-time scheduling perspective. It is shown that the problem of deciding if instances of the general model are feasible on a single processor is intractable (co-NP-complete in the strong sense); however, a useful special case is sometimes more tractable. An efficient feasibility test and an optimal preemptive scheduling algorithm are derived for this special case, and a procedure is presented which permits system architects to make efficient use of computational resources and memory requirements for buffers while constructing real-time dataflow applications that offer hard service guarantees.