The advent of Software-Defined Vehicles (SDVs) has revolutionized the automotive industry by enabling rapid innovation through the integration of software-driven functionalities. The Scalable Open Architecture for Embedded Edge (SOAFEE) framework, an innovative open software architecture, integrates cloud-native methodologies into in-vehicle environments. By leveraging this framework, the containerization of Robot Operating System (ROS) applications has gained widespread adoption for deploying and maintaining autonomous driving applications. However, real-time performance remains a critical challenge, particularly in addressing end-to-end (E2E) latency within ROS systems to ensure responsiveness and timely task execution. Existing tools, such as the Chain-Aware ROS Evaluation Tool (CARET), have contributed significantly to realtime performance evaluation. Nevertheless, these tools exhibit limitations when assessing E2E latency in containerized environments involving multiple containers. To address this gap, we introduce Distributed ROS Application Performance Profiler (DRAPP), a solution referenced CARET with enhancements, designed specifically to evaluate E2E latency in ROS-based applications. Our approach includes experiments using Autoware, deployed across multiple containers within the SOAFEE framework, with a primary focus on analyzing E2E processing latency. Preliminary empirical results demonstrate that DRAPP outperforms existing tools in both usability and effectiveness for latency evaluation, representing a significant step forward in the performance assessment of in-vehicle software for autonomous systems.

The Viterbi algorithm is a key operator for structured sequence inference in modern data systems, with applications in trajectory analysis, online recommendation, and speech recognition. As these workloads increasingly migrate to resource-constrained edge platforms, standard Viterbi decoding remains memory-intensive and computationally inflexible. Existing methods typically trade decoding time for space efficiency, but often incur significant runtime overhead and lack adaptability to various system constraints. This paper presents FLASH Viterbi, a Fast, Lightweight, Adaptive, and Hardware-Friendly Viterbi decoding operator that enhances adaptability and resource efficiency. FLASH Viterbi combines a non-recursive divide-and-conquer strategy with pruning and parallelization techniques to enhance both time and memory efficiency, making it well-suited for resource-constrained data systems. To further decouple space complexity from the hidden state space size, we present FLASH-BS Viterbi, a dynamic beam search variant built on a memory-efficient data structure. Both proposed algorithms exhibit strong adaptivity to diverse deployment scenarios by dynamically tuning internal parameters. To ensure practical deployment on edge devices, we also develop FPGA-based hardware accelerators for both algorithms, demonstrating high throughput and low resource usage. Extensive experiments show that our algorithms consistently outperform existing baselines in both decoding time and memory efficiency, while preserving adaptability and hardware-friendly characteristics essential for modern data systems. All codes are publicly available at https://github.com/Dzh-16/FLASH-Viterbi.

Autonomous machines often encounter complex timing constraints, such as those concerning end-to-end timing guarantees and real-time data fusion, etc. Tasks are often event-triggered or time-triggered at varying rates and exhibit data dependencies in between. Maintaining the real-time performance of autonomous machines becomes a highly challenging endeavor. In this paper, we formulate the workload of an autonomous machine as a hybrid Directed Acyclic Graph (DAG), which contains both time-trigger tasks and event-trigger tasks, with a distinct focus on the task of ensuring timing consistency in data fusion and adherence to end-to-end constraints within the DAG model. We design a concise mechanism to select suitable data received by a node and transmit them to successor nodes. This ensures both the timing disparity—as reflected by the differences in timestamps of the data used for fusion—and the end-to-end latency from the sensor to the controller is confined within a certain boundary. The proposed method is proven to be optimal as it always selects suitable data to guarantee the timing correctness of an autonomous machine as far as it (inherently) has the capacity. Experimental results show that our method can significantly improve the success rate of guaranteeing both timing consistency and end-to-end constraints of the autonomous machine.

Most existing research in probabilistic real-time scheduling analysis has primarily focused on systems with only stochastic execution times, neglecting the stochastic nature of task release patterns in many real-world applications. Current approaches for handling stochastic release times rely on computationally expensive convolution-based methods, which has poor scalability, especially when both execution and release times are stochastic. This paper presents novel techniques to apply the Chernoff Bound approach to the analysis of systems with both stochastic execution and release times. The key challenge lies in adapting the Chernoff Bound, which traditionally operates on a fixed number of random variables, to handle the stochastic job counts resulting from stochastic release patterns. Our main contribution is a new technique for bounding convolutions involving random numbers of random variables using Chernoff principles. Through comprehensive evaluation, we demonstrate that our approach achieves several orders of magnitude speedup compared to state-of-the-art convolution-based methods while simultaneously improving analysis precision.

Chains of tasks are ubiquitous and used in a broad spectrum of applications. In these chains, tasks execute according to their timing. Then, they communicate by writing to and reading from shared memory. The schedule of tasks and the read/write instants are naturally subject to uncertainties (variability in the execution time, interference due to shared resources of higher priority tasks, etc.). Despite the impact of uncertainties, we believe that current analysis of task chains cannot handle them properly. In this paper, we borrow the notion of jitter to model uncertainties and we propose a novel event model that explicitly captures jitter in read and write operations, decoupled from task scheduling. We develop a (linear-time complexity) compositional analysis framework that tracks how this jitter propagates across chains and impacts metrics such as reaction time, data age, and end-to-end latency. Our model supports arbitrary communication paradigms (e.g., implicit, LET, mid-execution) and is applicable to the analysis of real-world frameworks such as ROS2 without requiring intrusive changes.

In recent years, extensive research has been carried out on real-time typed scheduling and analysis of parallel tasks represented as directed acyclic graphs (DAGs) executed on heterogeneous multicores. Although previous studies have examined the schedulability of typed DAG tasks, they still encounter pessimism caused by interference from other tasks. In this article, we explore the worst case response time (WCRT) analysis of typed scheduling for DAG tasks under global scheduling. Here, each vertex in a typed DAG task experiences interference from within itself as well as from higher priority tasks. First, we propose an efficient method to bound the WCRT of typed DAG tasks based on the state-of-the-art parallel task analysis approach. Then, we discover a technique to mitigate the pessimism caused by other tasks, albeit in a nonoptimal manner. Finally, we conduct experiments using randomly generated typed DAG tasks to evaluate the performance of our proposed methods. The results indicate that our proposed approach can yield less pessimistic WCRT under global scheduling.

Mobile operating systems, such as Android, are increasingly used across diverse applications, where ensuring high responsiveness to user interactions is critical, particularly in mission-critical and real-time scenarios. Mobile operating systems typically process user interaction events and UI rendering on the same thread, commonly referred to as the main thread of a mobile application. As a result, user interaction handling can face significant delays when blocked by overloaded UI rendering tasks, compromising responsiveness. Existing mobile operating systems lack effective mechanisms to mitigate this issue. This paper addresses the problem by restructuring the UI rendering workflow to improve responsiveness in the presence of heavy rendering workloads. Specifically, two techniques are proposed that are tailored to whether the event handling results require screen display. Experimental results demonstrate improvements in both average-case and worst-case response times of event handling, enhancing the UI responsiveness. Although the implementation focuses on Android, the proposed approaches are adaptable to other mobile operating systems with similar rendering architectures, such as iOS and HarmonyOS.

Coarse-Grained Reconfigurable Arrays (CGRAs) are specialized accelerators commonly employed to boost performance in workloads with iterative structures. Existing research typically focuses on compiler or architecture optimizations aimed at improving CGRA performance, energy efficiency, flexibility, and area utilization, under the idealistic assumption that kernels can access all data from Scratchpad Memory (SPM). However, certain complex workloads–particularly in fields like graph analytics, irregular database operations, and specialized forms of high-performance computing (e.g., unstructured mesh simulations)–exhibit irregular memory access patterns that hinder CGRA utilization, sometimes dropping below 1.5%, making the CGRA memory-bound. To address this challenge, we conduct a thorough analysis of the underlying causes of performance degradation, then propose a redesigned memory subsystem and refine the memory model. With both microarchitectural and theoretical optimization, our solution can effectively manage irregular memory accesses through CGRA-specific runahead execution mechanism and cache reconfiguration techniques. Our results demonstrate that we can achieve performance comparable to the original SPM-only system while requiring only 1.27% of the storage size. The runahead execution mechanism achieves an average 3.04× speedup (up to 6.91×), with cache reconfiguration technique providing an additional 6.02% improvement, significantly enhancing CGRA performance for irregular memory access patterns.

IEEE 802.1Qch, also known as cyclic queuing and forwarding (CQF) shaper, enhanced the dynamic and flexible behavior of time-sensitive networking. Schedulability of the CQF is one of the major research fields used to improve system performance. Existing CQF heuristic scheduling approaches only consider the relative deadline in stream sorting or the link utilization in route selection, which encounters limitations while striving to attain high schedulability of streams. We propose an efficient scheduling for CQF. The main contributions are: We provide the earliest virtual absolute deadline first policy, which prioritizes stream instances based on their earliest absolute deadlines, intending to prior allocate resources to the stream instance with the greatest “urgency.” To provide a deep insight into efficient route selection, we then introduce a quality-of-service-aware indicator of a route that mainly accounts for slot utilization and route length, which enables us to select a route with a balance of slot utilization and shorter route length for a stream instance. With the comprehensive evaluation, our method achieves an average schedulability improvement of 31.73%, 17.93%, and 31.85% compared with state-of-the-art methods. Furthermore, our approach can be extended to other CQF-related shapers or time-division scheduling scenarios, significantly enhancing stream schedulability.

In autonomous driving (AD) systems, complex data dependencies exist between tasks with different activation rates, making it very hard to analyze the system’s timing behaviors. This paper formulates an AD system as a multi-rate directed acyclic graph (DAG) and introduces a novel reaction time bound for critical chains within this multi-rate DAG. Furthermore, we introduce a priority assignment strategy tailored to optimize priority allocation, effectively minimizing the reaction time of critical task chains. This strategy comes with theoretical guarantees, ensuring that the achieved latency bound is only slightly higher than the ideal one. Our empirical work demonstrates that the newly proposed reaction time bound outperforms current standards, achieving an average improvement of $5.46 \%$. Furthermore, our strategy for priority assignment significantly enhances the success rate of achieving timing correctness in the AD system, exceeding the baseline method by a notable $19.24 \%$.

The integration of edge computing with digital twins (DTs) has been instrumental in driving substantial advancements in the Internet of Vehicles (IoV) domain in recent times, particularly within the 6G wireless networks where DTs enable real-time simulation, monitoring, analysis, and high-speed transmissions for connected vehicles. Despite these benefits, several challenges arise, including dynamic network topologies resulting from the high-speed vehicle mobility, frequent edge server switches causing instability and increased latency, and the limited computing resources struggling to cope with the demanding computational tasks. This article addresses these issues by proposing a framework where the vehicles serve as the auxiliary mobile edge computing (MEC) servers. It introduces an enhanced density-based spatial clustering of applications with the noise (DBSCAN) algorithm designed to improve the clustering of vehicles under high-speed movement scenarios. Moreover, a multi-to-multi matching algorithm is devised to effectively associate vehicles with the auxiliary MEC servers. To alleviate the problem of insufficient computing resources due to intense computational loads during DT updates, a deep reinforcement learning (DRL)-based approach is utilized to make the optimal computation offloading decisions. This work further refines the offloading strategy by adopting the improved double deep Q-network (DDQN) and the dueling deep Q-network algorithms. Simulation experiments validate that the proposed clustering improvement and the DRL-based offloading decision-making scheme outperform the existing baseline methods across multiple performance metrics, such as clustering effectiveness, processing latency reduction, algorithmic efficiency, and convergence rate.

Time-Sensitive Networking (TSN) has become the most popular technique in modern safety-critical Automotive and Industrial Automation Networks by providing deterministic transmission policies. However, the data of TSN messages may be affected by transient faults. IEEE 802.1CB, a reliability standard in TSN, protects against such faults by providing disjoint redundant routes for each stream. However, the unique assumption may present a new challenge, i.e., an inadequate number of redundant routes that may negatively impact stream scheduling. This paper presents an offline fault-tolerant TSN scheduling approach that considers such impacts for real-time streams (such as Time-Trigger (TT) and Audio Video Bridging (AVB) streams). Specifically, we intend to calculate the minimum upper bound number of disjoint routes required for each stream to meet the reliability requirements, subsequently enhancing the network’s schedulability. We also propose a service degradation function for AVB streams when the network is under heavy load caused by redundant transmissions of TT streams. This function will maintain schedulability and reliability for AVB streams. Experiments with small-and large-scale synthetic networks show the efficiency.

Electrophoretic displays (EPDs), also known as e-paper, offer a paper-like visual experience by reflecting ambient light, making them distinct from traditional LCD or LED displays. They are favored for their eye comfort, energy efficiency, and material flexibility, which make them appealing for a wide range of embedded devices, including eReaders, smartphones, tablets, and wearables. However, EPDs face a significant challenge: the necessity for a fast refresh rate (to maintain an acceptable display performance) introduces a pronounced ghosting effect. This effect results in noticeable color discrepancies between the displayed and source images, harming the user experience and hindering EPDs’ broader application in devices requiring dynamic content display. This article proposes a software-based solution to address the ghosting issue in EPDs. Our approach involves developing analytical models to predict the occurrence of ghosting effects and adjusting the source images to counteract the anticipated color deviations, which can reduce the perceivable ghosts on the display. Experimental evaluation conducted on real-world EPDs validates the effectiveness of our proposed approach in reducing the ghosting effect.

Fault tolerance, energy management, and quality of service (QoS) are essential aspects for the design of real-time embedded systems. In this work, we focus on exploring methods that can simultaneously address the above three critical issues under standby-sparing. The standby-sparing mechanism adopts a dual-processor architecture in which each processor plays the role of the backup for the other one dynamically. In this way, it can provide fault tolerance subject to both permanent and transient faults. Due to its duplicate executions of the real-time jobs/tasks, the energy consumption of a standby-sparing system could be quite high. With the purpose of reducing energy under standby-sparing, we proposed three novel scheduling schemes: The first one is for (1, 1)-constrained tasks, and the second one and the third one (which can be combined into an integrated approach to maximize the overall energy reduction) are for general ( m,k )-constrained tasks that require that among any k consecutive jobs of a task no more than ( k - m ) out of them could miss their deadlines. Through extensive evaluations and performance analysis, our results demonstrate that compared with the existing research, the proposed techniques can reduce energy by up to 11% for (1, 1)-constrained tasks and 25% for general ( m,k )-constrained tasks while assuring ( m,k )-constraints and fault tolerance as well as providing better user perceived QoS levels under standby-sparing.

For real-time embedded systems, QoS (Quality of Service), fault tolerance, and energy budget constraint are among the primary design concerns. In this research, we investigate the problem of energy constrained standby-sparing for both periodic and aperiodic tasks in a weakly hard real-time environment. The standby-sparing systems adopt a primary processor and a spare processor to provide fault tolerance for both permanent and transient faults. For such kind of systems, we firstly propose several novel standby-sparing schemes for the periodic tasks which can ensure the system feasibility under tighter energy budget constraint than the traditional ones. Then based on them integrated approachs for both periodic and aperiodic tasks are proposed to minimize the aperiodic response time whilst achieving better energy and QoS performance under the given energy budget constraint. The evaluation results demonstrated that the proposed techniques significantly outperformed the existing state-of-the-art approaches in terms of feasibility and system performance while ensuring QoS and fault tolerance under the given energy budget constraint.

Robot Operating System (ROS) is a prevailing software framework for robotic appliscation development. Graphics Processing Unit (GPU) is widely used in many ROS applications as a first-order computation resource. Unfortunately, ROS does not do any resource management for GPU, and different components in a ROS application directly submit their GPU workload without coordinating with each other, which may cause severe problems in both general performance and realtime capability. This paper presents ROSGM, a real-time ROS 2G PUM anagement framework. Instead of providing a fixed GPU management policy for all scenarios, ROSGM allows the addition of any management policy as a plug-in and dynamic switching among different management policies at run-time, which is helpful since GPU management policies are typically device-dependent, and different applications or the same application in different modes may need different GPU management policies. Besides, ROSGM supports dynamic task loading and unloading for integrating additional functionalities when required at run-time. We conduct experiments to evaluate ROSGM. The results show that by properly managing the GPU resource using ROSGM, we can significantly improve the performance of ROS 2 applications. The flexibility of adding management policies as plug-ins, dynamic switching of management policies, and dynamic task loading and unloading helps improve the adaptability of ROSGM.

In the autonomous driving (AD) system, complex data dependencies exist between tasks with different activation rates, making it very hard to analyze systems’ real-time behaviors. This paper formulates the AD system as a multi-rate DAG and proposes an integrated framework to co-analyze the schedulability of individual tasks and the end-to-end latency of task chains in the multi-rate DAG. Integer linear programming (ILP) techniques are developed to guide how to drop redundant workload to increase the chance that timing requirements can be met. This paper proposed one analysis framework which enables an automated process in which designs of the AD system are created, analyzed and refined in an iterative way, i.e., the analysis result in the last iteration provides valuable guidance to redesign the AD system in the next iteration. Experiments are conducted to evaluate the performance of our analysis method.

In recent years, the maturation of modern multicore processor technology and its increasing adoption in critical industrial domains have posed significant challenges for real-time systems, primarily due to contention for shared cache resources and the resulting uncertainty. To address this issue, contemporary processors employ cache partitioning techniques, enhancing temporal predictability by isolating cache access among processor cores. However, this isolation technique may lead to real-time tasks missing their deadlines due to an insufficient number of cache partitions. Consequently, this paper investigates the schedulability of preemptive global Earliest Deadline First (EDF) real-time scheduling algorithms that support dynamic cache allocation. We propose an innovative LAG-based schedulability analysis method for these algorithms and present a utilization-based schedulability condition that reduces analysis time complexity while improving analysis accuracy. Lastly, the performance and efficiency of the proposed schedulability determination method are validated through simulation experiments with randomly generated tasks.

Abstract Despite their great advancement, current pedestrian detection methods focus on single static images, which fail to employ richer information available from the video sequences. Compared with still images, videos can offer temporal information of objects in the time dimension, thus providing the potential to obtain more robust detection performance. Here, a novel pedestrian detection method based on visible part detection and temporal calibration is proposed. Specifically, a part‐aware module to predict the visible body part of each pedestrian instance, which enables us to obtain precise motion information of partially occluded pedestrians in a video sequence, is first developed. Then, the temporal coherence for each pedestrian instance based on the predicted motion information is constructed. After that, an adaptive temporal calibration method is introduced to effectively calibrate the final detection result. This method on two video pedestrian detection benchmarks, that is, Caltech‐New and MOT17Det, is evaluated. Experimental results show that this method performs favourably against existing pedestrian detection approaches.

The complexity of modern system-on-chip (SoC) designs and the ever shortened time-to-market (TTM) makes the third-party intellectual property (3PIP) a cornerstone in the modern SoC supply chain. Various 3PIPs are involved in modern SoCs, performing functionality ranging from computation accelerating to sensitive data processing. The wide use of 3PIPs also raises security concerns, e.g., hardware Trojans inserted in 3PIPs may compromise the security of the whole system. While SoC integrators carefully evaluate the functionality of the acquired 3PIPs, there lack effective and low-cost solutions for third-party IP security validation in the SoC environment. Exacerbating the issue, Trojans may be located in multiple IPs and will only perform malicious tasks collaboratively. To address these limitations and to protect modern SoCs, we propose a runtime 3PIP Trojan detection framework. The new framework, named IP-Tag, is a tag-based structure to track the requests on SoC and enforce fine-grained access control in individual IPs. The proposed framework can detect and prevent illegal access and sensitive data leakage on IPs within the SoC environment. The proposed IP-Tag framework was demonstrated on an RISC-V-based SoC and also implemented on an FPGA platform for security and performance analysis. Our experimental results show that the developed IP-Tag can detect and prevent illegal access and sensitive data leakage in SoC with malicious IPs. The hardware overhead is 7.9% LUTs and 7.8% Flip-Flops and a performance overhead is 2.2%.

With the increasing demand for real-time computing applications on energy-harvesting embedded devices which are deployed wherever it is not possible or practical to recharge, the worst-case performance analysis becomes crucial. However, it is difficult to bound the worst-case response time of tasks under both timing and energy constraints due to the uncertainty of harvested energy. Based on this motivation, this paper studies response time analysis for Energy-Harvesting Mixed-Criticality (EHMC) systems. We present schedulability analysis algorithm to extend the Adaptive Mixed Criticality (AMC) approach to EHMC systems. Furthermore, we develop two response time bounds for it. To our best knowledge, this is the first work of response time analysis for EHMC systems. Finally, we examine both the effectiveness and the tightness of the bounds by experiments.

With the rapid growth of industrial Internet of Things (IIoT) applications, real-time wireless networks (RTWNs) are playing an increasingly important role in providing realtime, reliable, and secure communication services for these applications. A key challenge in RTWN management is to ensure real-time Quality of Services (QoS), especially in the presence of unexpected external (i.e., application-side) and internal (i.e., network-side) disturbances. This paper presents a novel framework, DS-PaS, to determine the packet transmission schedule for multi-channel multi-hop RTWNs at the data link layer in a distributed and dynamic fashion. DS-PaS is able to (i) handle external disturbances, (ii) support spatial reuse, (iii) meet deadlines of all critical tasks, and (iv) minimize the number of dropped non-critical packets. To avoid transmission collisions when using inconsistent information in a distributed framework, DS-PaS incorporates several key advances in both the data-link layer protocol and algorithm design so that individual nodes can build on-line schedules with only local interference information. Extensive evaluation based on both testbed implementation and simulation validates the correctness of the DS-PaS design and demonstrates its effectiveness compared to the state of the art.

The fifth-generation (5G) cellular networks are increasingly considered for industrial applications, such as factory automation systems. In 5G networks, Enhanced Mobile Broadband (eMBB) and Ultra-Reliable Low-Latency Communication (URLLC) are two essential services. eMBB services require high data rates with some lower bounds while URLLC traffic is subject to strict latency and reliability requirements. Existing approaches to scheduling coexisting eMBB and URLLC traffic all assume that URLLC traffic preempts eMBB traffic immediately upon arrival, which can adversely impact the achievable eMBB data rates. Furthermore, none of the prior work considers guaranteeing minimum data rate requirements imposed on certain eMBB traffic. This paper proposes a new model to capture the URLLC and eMBB requirements and introduces a novel framework, QoSG-RA, to perform network resource allocation for coexisting eMBB and URLLC traffic. QoSG-RA builds on a hybrid offline/online approach which performs offline resource allocation to ensure the Quality of Service (QoS) requirements of eMBB and URLLC traffic to be satisfied and online resource allocation to maximize fairness on the data rates among eMBB traffic based on runtime information. QoSG-RA is able to (i) meet latency and reliability requirements of URLLC traffic, and (ii) maximize the data rates for eMBB traffic in a fair way while fulfilling their minimum data rate requirements. Experimental results demonstrate the effectiveness of QoSG-RA compared to the state-of-the-art.

Energy harvesting is a promising approach to powering real-time embedded devices which are deployed wherever it is not possible or practical to recharge. Since the stochastic nature of harvested energy makes it challenging to simultaneously guarantee both timing and energy constraints of energy-harvesting real-time systems, the worst-case performance analysis becomes more crucial when analyzing the system schedulability. In this paper, we study the performance analysis problem of energy-harvesting mixed-criticality (EHMC) systems scheduled by an energy-aware adaptation of EDF. In particular, we propose a new method that can be used to derive time demand bounds for a mixed-criticality task set, which upper-bound the total amount of time required to satisfy both the processor and energy demand of the task set in any time interval of a given size for each criticality mode. Moreover, we calculate the minimum size of the capacitor for our schedulability test to be valid. Experiment results show that our approach is significantly more powerful than previous approaches to energy harvesting mixed-criticality systems.

Time-sensitive network (TSN) has emerged as one of the enhancement Ethernet technologies of real-time applications for future industrial networks. However, the data of TSN messages may be unexpectedly changed within the transmission duration due to electromagnetic interference. A cyclic redundancy check (CRC) can detect such errors and notify the sender node to retransmit the erroneous message through automatic repeat request (ARQ). The time when the error occurs is uncertain. Consequently, the time when performing the retransmission requests is also random, which results in different transmission sequences and violates the deterministic transmission of TSN. In addition, the returned CRC detection messages also might be at fault during transmission. In order to provide the fault tolerance capability of critical flows in TSN without violating the nature of deterministic transmission, this article proposes a pro-active fault-tolerant TSN scheduling algorithm (PFT-TSN), which not only transmits a certain number of instance copies for critical flows but provides network transmission services for noncritical flows. The challenge is that schedulability and safety of critical flows are tradeoffs in terms of the number of transmissions per instance of critical flows and the schedulability. Moreover, the transmission service of noncritical flows can also affect the schedulability of critical flows. We conduct comprehensive experiments with synthetic networks to show that the proposed method can meet both safety and schedulability requirements for critical flows, and noncritical flows are also allowed to be transmitted by the service degradation.

Many modern real-time parallel applications can be modeled as a directed acyclic graph (DAG) task. Recent studies show that the worst-case response time (WCRT) bound of a DAG task can be significantly reduced when the execution order of the vertices is determined by the priority assigned to each vertex of the DAG. How to obtain the optimal vertex priority assignment, and how far from the best-known WCRT bound of a DAG task to the minimum WCRT bound are still open problems. In this article, we aim to construct the optimal vertex priority assignment and derive the minimum WCRT bound for the DAG task. We encode the priority assignment problem into an integer linear programming (ILP) formulation. To solve the ILP model efficiently, we do not involve all variables or constraints. Instead, we solve the ILP model iteratively, i.e., we initially solve the ILP model with only a few primary variables and constraints, and then at each iteration, we increment the ILP model with the variables and constraints which are more likely to derive the optimal priority assignment. Experimental work shows that our method is capable of solving the ILP model optimally without involving too many variables or constraints, e.g., for instances with 50 vertices, we find the optimal priority assignment by involving 12.67% variables on average and within several minutes on average.

Time-sensitive networking (TSN) is an industry-standard networking protocol that is widely deployed in safety-critical industrial and automotive networks thanks to its quality-of-service (QoS) mechanisms, esp. deterministic transmission and bounded end-to-end delay for time-triggered (TT) flows. In this article, we focus on TT flows and address the issue of fault tolerance against permanent and transient faults with both spatial and temporal redundancy. We present an efficient heuristic algorithm for online incremental rerouting and rescheduling of disrupted flows, assuming the paths and schedules of existing flows stay fixed. It is complementary to and can be combined with offline routing and scheduling algorithms for achieving fault tolerance based on frame replication and elimination for reliability (FRER) (IEEE 802.1CB). Performance evaluation shows that our approach is able to better recover the system’s degree of redundancy (DoR) and has a higher acceptance rate than related work.

Malicious attackers may disrupt the safety of autonomous systems through compromising sensors to feed wrong measurements to the controller. This article proposes attack-resilient sensor fusion that combines local sensor readings and shared sensing information from multiple sources. The method results in higher resilience against sensor attacks through jointly considering sensing noise and uncertain communication delay. To be specific, we first identify the considerable impact of the delay on determining attacked sensors. Second, we present a novel two-dimensional abstract sensor model, where each measurement is augmented as a probabilistic interval based on the convolution of the noise and delay. Third, we propose a fusion algorithm that admits the fused value with highest joint probability distribution of the intervals to tolerate corrupted measurements. Finally, we demonstrate the effectiveness of our method in a vehicle-platoon case study using extensive simulations and testbed experiments.

Dynamic Information Flow Tracking (DIFT) is a technique that facilitates run-time data-flow analysis on a running process, allowing a system to overcome the limitations of finding data dependencies statically at compilation time. DIFT serves as the backbone for applications including data-flow integrity (DFI). However, previous uses of DIFT towards DFI often have large overhead in terms of hardware, software or both, and often cannot provide fine-granularity tracking for software object, such as variables. To address these limitations, we present FineDIFT as a DFI framework which utilizes DIFT to generate a live data-flow graph of a running process and perform hardware-based assisted analysis at fine-granularity, thus being able to enforce the application’s Data-Flow Graph (DFG). We provide a sample implementation on a RISC-V core with a performance overhead of 5.03% for BEEBS benchmarks and hardware overhead of 6% LUTs and 8% Flip-Flops in the FPGA implementation, if excluding the Content-Addressable Memory (CAM) like structure used for metadata storage. With CAM-like structure being synthesized using FPGA logic, the total hardware overhead is$\approx 2 \times $LUTs and 33% Flip-Flops compared to the original RISC-V core. We also use the real-world application and customized vulnerable application to demonstrate the effectiveness of the proposed framework in protecting computing systems.

Summary In recent years, electric vehicles (EVs) receive intensive attention due to their environment‐friendly nature and outstanding energy efficiency. However, there are still obstacles in EVs' popularity. Battery related issues are most concerned from users' perspective. While the evolution in battery technology may help to address the aforementioned problems eventually, other solutions are in urgent demand for the time being. In this paper, we propose an innovative charge scheduling method that could significantly improve EV users' charging experience with the nowadays battery technology. Specifically, the proposed method takes into account the characteristics of the batteries to be charged as well as the constraints of the external power grid; thus, a plan can be devised for efficiently allocating the power of the charging station to the EVs through cyber‐physical system. Our method prioritizes jobs based on their marginal utilities to maximize user satisfaction with limited power resource. The power allocation in our method is managed globally and constrained by specific rules to avoid waste or overload in the power grid. Lastly, we simulate several power scheduling methods in charging stations, which validates that the user satisfaction under our method is higher than that of other traditional method.

Pedestrian detection is a crucial task in intelligent transportation systems, which can be applied in autonomous vehicles and traffic scene video surveillance systems. The past few years have witnessed much progress on the research of pedestrian detection methods, especially through the successful use of the deep learning based techniques. However, occlusion and large scale variation remain the challenging issues for pedestrian detection. In this work, we propose a Part-Aware Multi-Scale Fully Convolutional Network (PAMS-FCN) to tackle these difficulties. Specifically, we present a part-aware Region-of-Interest (RoI) pooling module to mine body parts with different responses, and select the part with the strongest response via voting. As such, a partially visible pedestrian instance can receive a high detection confidence score, making it less likely to become a missing detection. This module operates in parallel with an instance RoI pooling module to combine local parts and global context information. To handle vast scale variation, we construct a fully convolutional network in which multi-scale feature maps are generated efficiently, and small-scale and large-scale pedestrians are detected separately. By integrating these structures, the proposed detector achieves the state-of-the-art performance on the Caltech, KITTI, INRIA and ETH pedestrian detection datasets.

Along with the rapid growth of Industrial Internet-of-Things (IIoT) applications and their penetration into many industry sectors, real-time wireless networks (RTWNs) have been playing a more critical role in providing real-time, reliable, and secure communication services for such applications. A key challenge in RTWN management is how to ensure real-time Quality of Services (QoS) especially in the presence of unexpected disturbances and lossy wireless links. Most prior work takes centralized approaches for handling disturbances, which are slow and subject to single-point failure, and do not scale. To overcome these drawbacks, this article presents a fully distributed packet scheduling framework called FD-PaS . FD-PaS aims to provide guaranteed fast response to unexpected disturbances while achieving minimum performance degradation for meeting the timing and reliability requirements of all critical tasks. To combat the scalability challenge, FD-PaS incorporates several key advances in both algorithm design and data link layer protocol design to enable individual nodes to make on-line decisions locally without any centralized control. Our extensive simulation and testbed results have validated the correctness of the FD-PaS design and demonstrated its effectiveness in providing fast response for handling disturbances while ensuring the designated QoS requirements.

FPGA vendors provide OpenCL software development kits for easier programmability, with the goal of replacing the time-consuming and error-prone register-transfer level (RTL) programming. Many studies explore optimization methods (e.g., loop unrolling, local memory) to accelerate OpenCL programs running on FPGAs. These programs typically follow the default OpenCL execution model, where a kernel deploys multiple work-items arranged into work-groups. However, the default execution model is not always a good fit for an application mapped to the FPGA architecture, which is very different from the multithreaded architecture of GPUs, for which OpenCL was originally designed. In this work, we identify three other execution models that can better utilize the FPGA resources for the OpenCL applications that do not fit well into the default execution model. These three execution models are based on two OpenCL features devised for FPGA programming (namely, single work-item kernel and OpenCL channel). We observe that the selection of the right execution model determines the performance upper bound of a particular application, which can vary by two orders magnitude between the most suitable execution model and the most unsuitable one. However, there is no way to select the most suitable execution model other than empiricall exploring the optimization space for the four of them, which can be prohibitive. To help FPGA programmers identify the right execution model, we propose Boyi, a systematic framework that makes automatic decisions by analyzing OpenCL programming patterns in an application. After finding the right execution model with the help of Boyi, programmers can apply other conventional optimizations to reach the performance upper bound. Our experimental evaluation shows that Boyi can 1) accurately determine the right execution model, and 2) greatly reduce the exploration space of conventional optimization methods.

Adaptive Cache Replacement Policy (ACRP) has been implemented in recently proposed commercial multi-core processors. ACRP consists of two candidate cache replacement policies and dynamically employs the policy which is with fewer cache misses at the moment. ACRP can diminish the overall cache misses, but at the same time it augments the performance inference between co-running applications and makes the performance prediction much harder. Unfortunately, very little work has focused on the performance impact from this mechanism. In this paper, we firstly expose the performance variation problem due to adaptive cache replacement policies. Secondly, we present Bubble-Bound, a low-overhead measurement-based method to estimate a program's performance variation caused by the dynamic adaptation of cache replacement policies. By using a stress program to characterize the pressure and sensitivity, our method can predict a bound for the performance degradation between co-located applications and enable “safe” co-locations on the processors with ACRP.

ROS (Robot Operating System) is currently the most popular robotic software development framework. Robotic software in safe-critical domain are usually subject to hard real-time constraints, so designers must formally model and analyze their timing behaviors to guarantee that real-time constraints are always honored at runtime. This paper studies real-time scheduling and analysis of processing chains in ROS2, the second-generation ROS with a major consideration of real-time capability. First, we study response time analysis of processing chains on ROS2 executors. We show that the only existing result of this problem is both optimistic and pessimistic, and develop new techniques to address these problems and significantly improve the analysis precision. Second, we reveal that the response time of a processing chain on an executor only depends on its last scheduling entity (callback), which provides useful guidance for designers to improve not only the response time bound, but also the actual worst-case/average response time of the system at little design cost. We conduct experiments with both randomly generated workload and a case study on realistic ROS2 platforms to evaluate and demonstrate our results.

Capacity augmentation bound (CAB) is a widely used quantitative metric in theoretical analysis for directed acyclic graph (DAG) parallel real-time tasks, which reveals the key factors the schedulability of DAG tasks heavily depending on: the normalized utilization (the ratio of the total utilization to the core numbers) and the tensity (the maximum ratio of task's longest path length to task's deadline). However, CAB requires both factors of a schedulable task system to be capped by the same threshold. A task system with a normalized utilization slightly larger than that threshold but very small tensity, or very smaller normalized utilization but slightly larger than that threshold has good chance to be scheduled are both denied by CAB. To this end, we propose a new concept called capacity augmentation function (CAF) to better characterize the schedulability of parallel real-time tasks, which provides a more loose and different threshold for both factors. In particular, we derive a CAF-based linear-time schedulability test for real-time constrained-deadline DAG tasks under global EDF, which entirely dominates the state-of-the-art CAB-based test for constrained-deadline settings. Finally, we conduct experiments to compare the acceptance ratio of our CAF-based test with the existing schedulability tests also having linear-time complexity. The results show that CAF-based test significantly outperforms the existing linear-time schedulability test under different parameter settings.

Demand response is considered as a valuable functionality of the power grid and its potential impacts continue expanding with grid modernization. Colocation data centers (simply called colocation) are recognized as a notably promising resource for demand response due to their high power demand and remarkable potential in demand management. A major challenge of colocation demand response is the split incentive, that is, colocation operators desire demand response for financial compensation while tenants may not embrace demand response due to lack of incentives. Another key challenge is caused by renewable energy co-located with data centers. Demand response mechanisms overlooking the uncertainty of renewable would cause much inefficiency in terms of energy saving and economic aspects. Existing work considers the two challenges separately in the context of data centers. By contrast, this work jointly addresses them and specially studies mechanism design for colocation data centers in presence of co-located renewable. We propose a hierarchical demand response scheme, which is based on a new two-level market mechanism that results in a win-win situation for both parties, i.e., tenants who choose to reduce power demand obtain financial rewards from the operator, while the operator receives financial compensation from the electric power company due to its tenants' demand reduction. At each demand response period, the colocation operator solicits bids (amount of energy reduction) from tenants and tenants who choose to participate responds to the operator with their bids. The proposed mechanism provably converges to a unique equilibrium solution, and at the equilibrium, neither the operator or tenants can improve their individual economic performance by changing their own strategies. Further, we present a stochastic optimization based algorithm, which uses predictions of the co-located renewable to determine the colocation operator's best strategy. At the equilibrium, the algorithm has a provable economic performance guarantee in terms of the prediction error. We finally evaluate the designed mechanism via detailed simulations and the results show the efficacy and validate the theoretical analysis for the mechanism.

Along with the rapid development and deployment of real-time wireless network (RTWN) technologies in a wide range of applications, effective packet scheduling algorithms have been playing a critical role in RTWNs for achieving desired Quality of Service (QoS) for real-time sensing and control, especially in the presence of unexpected disturbances. Most existing solutions in the literature focus either on static or dynamic schedule construction to meet the desired QoS requirements, but have a common assumption that all wireless links are reliable. Although this assumption simplifies the algorithm design and analysis, it is not realistic in real-life settings. To address this drawback, this paper introduces a novel reliable dynamic packet scheduling framework, called RD-PaS. RD-PaS can not only construct static schedules to meet both the timing and reliability requirements of end-to-end packet transmissions in RTWNs for a given periodic network traffic pattern, but also construct new schedules rapidly to handle abruptly increased network traffic induced by unexpected disturbances while minimizing the impact on existing network flows. The functional correctness of the RD-PaS framework has been validated through its implementation and deployment on a real-life RTWN testbed. Extensive simulation-based experiments have also been performed to evaluate the effectiveness of RD-PaS, especially in large-scale network settings.

As the shared last level cache (LLC) in multicore processors has been shown to be a critical resource for system performance, much work has been proposed for improving the quality of service (QoS) and throughput on LLC. Cache Allocation Technology (CAT) and Adaptive Cache Replacement Policies (ACRP) are two of the techniques that are featured in recent Intel processors. CAT implements way partitioning and provides the ability to control the cache space allocation among cores. ACRP works with multiple replacement policies and enables the cache to adapt to the cache replacement policy with less cache misses. In this paper, we first show an interesting finding that ACRP technique can violate the performance isolation provided by CAT. We find the cause for this problem is that the ACRP chooses the cache replacement policy upon the global information even although the cache space partitioning is being enabled by CAT. As the result, the cache/performance isolation can be impaired by the interference on cache replacement policy. To deal with this problem, we propose a low overhead method to predict the worst execution time degradation caused by the replacement policy adaptation. Thus, in the partitioned cache space, if the worst execution time estimated by our method is not beyond the response time required for this program, the QoS for this program can be quaranteed no matter how the cache replacement policies alternate.

DAG task model is a general parallel task model that has been widely concerned and studied by researchers. The combination of mixed-criticality and DAG task model makes it difficult to analyze system behaviors. Under federated mixed-criticality scheduling algorithm, tasks are physically isolated with regard to computation resources, which leads to lower analysis complexity and better performance. However, federated mixed-criticality scheduling algorithm suffers resource waste as in federated scheduling, and almost half of processor resources can be wasted in extreme cases. In this paper, we address the problem and propose a novel semi-federated mixed-criticality algorithm (SFMC). SFMC combines semi-federated scheduling with mixed-criticality systems, whose original architecture is changed to a dual-hierarchical one. When analyzing the combined system, we first allocate finer-grained processor resources to each MC DAG task, then we prove the correctness of the SFMC algorithm in both normal and critical states. The proposed algorithm is evaluated on randomly generated independent DAG task sets based on OpenMP benchmarks. Experiment results present that our algorithm has better performance on schedulability than the federated mixed-criticality scheduling algorithm.

With the fast growth of civil drones, their security problems meet significant challenges. A commercial drone may be hijacked by a GPS-spoofing attack for illegal activities, such as terrorist attacks. The target of this article is to develop a technique that only uses onboard gyroscopes to determine whether a drone has been hijacked. Ideally, GPS data and the angular velocities measured by gyroscopes can be used to estimate the acceleration of a drone, which can be further compared with the measurement of the accelerometer to detect whether a drone has been hijacked. However, the detection results may not always be accurate due to some calculation and measurement errors, especially when no hijacking occurs in curve trajectory situations. To overcome this, in this article, we propose a novel and simple method to detect hijacking only based on gyroscopes’ measurements and GPS data, without using any accelerometer in the detection procedure. The computational complexity of our method is very low, which is suitable to be implemented in the drones with micro-controllers. On the other hand, the proposed method does not rely on any accelerometer to detect attacks, which means it receives less information in the detection procedure and may reduce the results accuracy in some special situations. While the previous method can compensate for this flaw, the high detection results also can be guaranteed by using the above two methods. Experiments with a quad-rotor drone are conducted to show the effectiveness of the proposed method and the combination method.

Real-time wireless networks (RTWNs) are fundamental to many Internet-of-Things (IoT) applications. RTWNs typically apply time-division multiple access (TDMA)-based media access control mechanisms and often demand deterministic end-to-end packet delivery to meet the given quality of service (QoS) requirements. Packet scheduling in an RTWN thus plays a critical role for achieving the desired performance but is a challenging problem especially when the RTWN is large and must deal with multiple disturbances (i.e., unexpected events causing abrupt workload changes associated with certain sensing tasks) occurring concurrently. This paper introduces a novel distributed dynamic packet scheduling framework, D2-PaS. D2-PaS is capable of processing disturbances and minimizes the number of dropped packets while ensuring that all critical events due to disturbances are handled by their deadlines. As a distributed approach, D2-PaS constructs schedules locally at individual nodes, which significantly reduces the amount of schedule-related information to be broadcast by the gateway. As a dynamic approach, D2-PaS applies a lightweight packet dropping algorithm to determine on-line at the gateway which packets can be dropped in response to disturbances and disseminate this information to the network. D2-PaS has been implemented on a multi-hop RTWN testbed to validate its applicability on hardware and a popular RTWN stack. Both testbed measurements and extensive simulation results demonstrate the effectiveness of D2-PaS.

Real-time and embedded systems are shifting from single-core to multi-core processors, on which the software must be parallelized to fully utilize the computation capacity of the hardware. Recently, much work has been done on real-time scheduling of parallel tasks modeled as directed acyclic graphs (DAG). However, most of these studies assume tasks to have implicit or constrained deadlines. Much less work considered the general case of arbitrary deadlines (i.e., the relative deadline is allowed to be larger than the period), which is more difficult to analyze due to intra-task interference among jobs. In this article, we study the analysis of Global Earliest Deadline First (GEDF) scheduling for DAG parallel tasks with arbitrary deadlines. We develop new analysis techniques for GEDF scheduling of a single DAG task and this new analysis techniques can guarantee a better capacity augmentation bound 2.41 (the best known result is 2.5) in the case of a single task. Furthermore, the proposed analysis techniques are also extended to the case of multiple DAG tasks under GEDF and federated scheduling. Finally, through empirical evaluation, we justify the out-performance of our schedulability tests compared to the state-of-the-art in general.

Heterogenerous multi-cores utilize the strength of different architectures for executing particular types of workload, and usually offer higher performance and energy efficiency. In this paper, we study the worst-case response time (WCRT) analysis of typed scheduling of parallel DAG tasks on heterogeneous multi-cores, where the workload of each vertex in the DAG is only allowed to execute on a particular type of cores. The only known WCRT bound for this problem is grossly pessimistic and suffers the non-self-sustainability problem. In this paper, we propose two new WCRT bounds. The first new bound has the same time complexity as the existing bound, but is more precise and solves its non-self-sustainability problem. The second new bound explores more detailed task graph structure information to greatly improve the precision, but is computationally more expensive. We prove that the problem of computing the second bound is strongly NP-hard if the number of types in the system is a variable, and develop an efficient algorithm which has polynomial time complexity if the number of types is a constant. Experiments with randomly generated workload show that our proposed new methods are more precise than the existing bound while having good scalability.

The k nearest neighbor (kNN) query in road networks is a traditional query type in spatial databases. This query has found new applications in the fast-growing location-based services, e.g., finding the k nearest Uber cars of a user for ridesharing. KNN queries in these applications are non-trivial to process due to the frequent location updates of data objects (e.g., movements of the cars). This calls for novel spatial indexes with high efficiency in not only query processing but also update handling. To address this need, we propose an index structure that uses a "lazy update" strategy to reduce the costs of update handling without sacrificing query efficiency or answer accuracy. We cache the location updates of data objects and only update the corresponding entries in the index when they are queried. We further propose a kNN query algorithm based on this index. This algorithm takes advantage of the strengths of both the CPU and the GPU. It first identifies the queried region and updates the index over this region using the GPU. Then, it uses the GPU to query the index and produce a candidate result set, which is later refined by the CPU to obtain the final query answer. We conduct experiments on real data and compare the proposed algorithm with state-of-the-art kNN algorithms. The experimental results show that the proposed algorithm outperforms the baseline algorithms by orders of magnitude in query time.

Along with the rapid growth of Industrial Internet-of-Things (IIoT) applications and their penetration into many industry sectors, real-time wireless networks (RTWNs) have been playing a more critical role in providing real-time, reliable and secure communication services for such applications. A key challenge in RTWN management is how to ensure real-time Quality of Services (QoS) especially in the presence of unexpected external and internal disturbances. Most prior work takes a centralized approach for handling disturbances, which is slow and subject to single-point failure, and does not scale. To overcome these drawbacks, this paper presents a fully distributed packet scheduling framework called FD-PaS. FD-PaS aims to provide guaranteed fast response to unexpected disturbances while dropping a minimum number of packets for meeting the deadlines of all critical tasks. To combat the scalability challenge, FD-PaS incorporates several key advances in both algorithm design and data link layer protocol design to enable individual nodes to make on-line decisions locally without any centralized control. Our extensive simulation and testbed results have validated the correctness of the FD-PaS design and demonstrated its effectiveness in providing fast response for handling disturbances.

Heterogenerous multi-cores utilize the strength of different architectures for executing particular types of workload, and usually offer higher performance and energy efficiency. In this paper, we study the worst-case response time (WCRT) analysis of typed scheduling of parallel DAG tasks on heterogeneous multi-cores, where the workload of each vertex in the DAG is only allowed to execute on a particular type of cores. The only known WCRT bound for this problem is grossly pessimistic and suffers the non-self-sustainability problem. In this paper, we propose two new WCRT bounds. The first new bound has the same time complexity as the existing bound, but is more precise and solves its non-self-sustainability problem. The second new bound explores more detailed task graph structure information to greatly improve the precision, but is computationally more expensive. We prove that the problem of computing the second bound is strongly NP-hard if the number of types in the system is a variable, and develop an efficient algorithm which has polynomial time complexity if the number of types is a constant. Experiments with randomly generated workload show that our proposed new methods are significantly more precise than the existing bound while having good scalability.

Capacity augmentation bound is a widely used quantitative metric in theoretical studies of schedulability analysis for directed acyclic graph (DAG) parallel real-time tasks, which not only quantifies the suboptimality of the scheduling algorithms, but also serves as a simple linear-time schedulability test. Earlier studies on capacity augmentation bounds of the sporadic DAG task model were either restricted to a single DAG task or a set of tasks with implicit deadlines. In this paper, we consider parallel tasks with constrained deadlines under global earliest deadline first policy. We first show that it is impossible to obtain a constant bound for our problem setting, and derive both lower and upper bounds of the capacity augmentation bound as a function with respect to the maximum ratio of task period to deadline. Our upper bound is at most 1.47 times larger than the optimal one. We conduct experiments to compare the acceptance ratio of our capacity augmentation bound with the existing schedulability test also having linear-time complexity. The results show that our capacity augmentation bound significantly outperforms the existing linear-time schedulability test under different parameter settings.

Currently, a number of crowdsourcing‐based mobile applications have been implemented in mobile networks and Internet of Things (IoT), targeted at real‐time services and recommendation. The frequent information exchanges and data transmissions in collaborative crowdsourcing are heavily injected into the current communication networks, which poses great challenges for Mobile Wireless Networks (MWN). This paper focuses on the traffic scheduling and load balancing problem in software‐defined MWN and designs a hybrid routing forwarding scheme as well as a congestion control algorithm to achieve the feasible solution. The traffic scheduling algorithm first sorts the tasks in an ascending order depending on the amount of tasks and then solves it using a greedy scheme. In the proposed congestion control scheme, the traffic assignment is first transformed into a multiknapsack problem, and then the Artificial Fish Swarm Algorithm (AFSA) is utilized to solve this problem. Numerical results on practical network topology reveal that, compared with the traditional schemes, the proposed congestion control and traffic scheduling schemes can achieve load balancing, reduce the probability of network congestion, and improve the network throughput.

The fast growth of civil drones raises significant security challenges. A legitimate drone may be hijacked by GPS spoofing for illegal activities, such as terrorist attacks. The target of this paper is to develop techniques to let drones detect whether they have been hijacked using onboard motion sensors (accelerometers and gyroscopes). Ideally, the linear acceleration and angular velocity measured by motion sensors can be used to estimate the position of a drone, which can be compared with the position reported by GPS to detect whether the drone has been hijacked. However, the position estimation by motion sensors is very inaccurate due to the significant error accumulation over time. In this paper, we propose a novel method to detect hijacking based on motion sensors measurements and GPS, which overcomes the accumulative error problem. The computational complexity of our method is very low, and thus is suitable to be implemented in the micro-controllers of drones. Experiments with a quad-rotor drone are conducted to show the effectiveness of the proposed method.

Real-time wireless networks (RTWNs) are fundamental to many Internet-of-Things (IoT) applications. Packet scheduling in an RTWN plays a critical role for achieving desired performance but is a challenging problem especially when the RTWN is large and subject to unexpected disturbances from the environment. Few solutions exist to tackle this challenge but they suffer serious limitations. This paper introduces a novel distributed dynamic packet scheduling framework, D2-PaS. D2-PaS aims to minimize the number of dropped packets while ensuring that all critical events due to disturbances are handled by their deadlines. D2-PaS builds on a number of observations that help reduce the scheduling overhead, and thus is efficient and scalable. Besides extensive simulation, D2-PaS has been implemented on an RTWN testbed to validate its applicability on real hardware. Both testbed measurements and simulation results confirm the effectiveness of D2-PaS. Compared to the best known work, D2-PaS reduces packet drop rates by 65% and 90% on average and in the best case, respectively, and also achieves 100% success for all the randomly generated task sets.

Demand response is considered as a valuable functionality of the power grid and its potential impacts continue expanding with grid modernization. Colocation data centers (simply called colocation) are recognized as a notably promising resource for demand response due to their high power demand and remarkable potential in demand management. A major challenge of colocation demand response is the split incentive, that is, colocation operators desire demand response for financial compensation while tenants may not embrace demand response due to lack of incentives. To address this challenge, we study a hierarchical demand response scheme, where tenants within a colocation respond to the colocation operator while the operator interacts with the electric power company. We propose that twolevel marketing is suitable to this hierarchical scheme, and design a new market mechanism that results in a win-win situation for the operator and tenants. Specially, tenants who chooses to reduce power demand obtain financial rewards from the operator, while the operator receives financial compensation from the electric power company due to its tenants' demand reduction. An appealing feature of the mechanism is that it provably converges to a unique equilibrium solution. At the equilibrium, neither the operator or tenants can improve their individual economic performance by changing their own strategies. We evaluate the designed mechanism via detailed simulations and the results show the efficacy and validate the theoretical analysis for the mechanism.

A smart factory generates vast amounts of data that require transmission via large-scale wireless networks. Thus, the reliability and real-time performance of large-scale wireless networks are essential for industrial production. A distributed data transmission scheme is suitable for large-scale networks, but is incapable of optimizing performance. By contrast, a centralized scheme relies on knowledge of global information and is hindered by scalability issues. To overcome these limitations, a hybrid scheme is needed. We propose a hierarchical data transmission framework that integrates the advantages of these schemes and makes a tradeoff among real-time performance, reliability, and scalability. The top level performs coarse-grained management to improve scalability and reliability by coordinating communication resources among subnetworks. The bottom level performs fine-grained management in each subnetwork, for which we propose an intrasubnetwork centralized scheduling algorithm to schedule periodic and aperiodic flows. We conduct both extensive simulations and realistic testbed experiments. The results indicate that our method has better schedulability and reduces packet loss by up to $22\%$ relative to existing methods.

This brief presents a field-programmable gate array-based implementation of a reconfigurable digital down converter (DDC) that can process input bandwidth of up to 3.6 GHz and provide a flexible down-converted output. The proposed DDC consists of a mixer and a resampling filter. The resampling filter can work at much higher clock rate. The reason is that all the single-cycle recursive loops in the resampling filter are pipelined by using either real/imaginary part-time multiplexing or parallel processing technique. With features like arbitrary sampling rate conversion, and dynamic configuration, the proposed design is highly flexible, so that it can generate a down-converted output with sampling rate, selectable within the range of 1 kS/s-225 MS/s. Moreover, the flexibility is further improved by being able to specify the output sampling rate and center frequency to a resolution of less than 1 S/s. The experimental results show that the proposed design can achieve the same functionality as the existing work but with fewer hardware resources.

We revisit the moving k nearest neighbor (MkNN) query, which computes one's k nearest neighbor set and maintains it while at move. Existing MkNN algorithms are mostly safe region based, which lack efficiency due to either computing small safe regions with a high recomputation frequency or computing larger safe regions but with a high cost for each computation. In this demonstration, we showcase a system named INSQ that adopts a novel algorithm called the Influential Neighbor Set (INS) algorithm to process the MkNN query in both two-dimensional Euclidean space and road networks. This algorithm uses a small set of safe guarding objects instead of safe regions. As long as the the current k nearest neighbors are closer to the query object than the safe guarding objects are, the current k nearest neighbors stay valid and no recomputation is required. Meanwhile, the region defined by the safe guarding objects is the largest possible safe region. This means that the recomputation frequency is also minimized and hence, the INS algorithm achieves high overall query processing efficiency.

Real-time task graphs are used to describe complex real-time systems with non-cyclic timing behaviors. The workload of such systems are typically bursty, which may degrade their schedulability even with sufficient resource in the long term. In this paper, we propose to use task graph transformation to improve system schedulability. The idea is to insert artificial delays to the release times of certain vertices of a task graph to get a new graph with a smoother workload, while still meeting the timing constraints of the original task graph. Delaying the release time of a vertex may smoothen the workload of some paths of the task graph, but at the same time make the workload of other paths even more bursty. We developed efficient techniques to search for an appropriate release time delay for each vertex. Experiments with randomly generated task systems show that the proposed transformation method can make a significant number of task systems that was originally unschedulable to become schedulable, and the transformation procedure is very efficient and can easily handle large-scale task graph systems in very short computation time.

In the formal analysis of real-time systems, modeling of branching codes and modeling of intratask parallelism structures are two of the most important research topics. These two real-time properties are combined, resulting in the fork-join real-time task (FJRT) model, which extends the digraph-based task model with forking and joining semantics. We prove that the EDF schedulability problem on a preemptive uniprocessor for the FJRT model is coNP-hard in the strong sense, even if the utilization of the task system is bounded by a constant strictly less than 1. Then, we show that the problem becomes tractable with some slight structural restrictions on parallel sections, for which we propose an exact schedulability test with pseudo-polynomial time complexity. Our results thus establish a borderline between the tractable and intractable FJRT models.

In this paper, we present a novel channelization architecture, which can simultaneously process two channels of complex input data and provide up to 1024 independent channels of complex output data. The proposed architecture is highly modular and generic, so that parameters of each output channel can be dynamically changed even at runtime in terms of the bandwidth, center frequency, output sampling rate, and so on. It consists of one tunable pipelined frequency transform (TPFT)-based coarse channelization block, one tuning unit, and one resampling filter. Based on the analysis of the data dependence between the subbands, a novel channel splitting scheme is proposed to enable multiple subbands to share the proposed TPFT block. The multiplier block (MB) and subexpression sharing techniques are used to reduce the number of arithmetic units of the TPFT block. Moreover, the proposed Farrow-based resampling filter does not require division operation and dual-port RAMs resulting in significant area saving. Finally, we implement the proposed channelization architecture in a single field-programmable gate array. The experiment results indicate that our design provides the flexibility associated with the existing works, but with greater resource efficiency.

The analysis of global multiprocessor scheduling is more difficult than its uniprocessor counterpart. Due to the unknown critical instant, existing techniques use over-approximations of task interference for efficient yet pessimistic analysis. In this paper, we proposed a new technique to improve the precision of interference estimation. The key is to identify and resolve contradicting assumptions made in the analysis procedure. The resulting new analysis method improves the analysis precision at the price of a higher complexity. Then we introduce techniques to optimize the new method for better efficiency. Experiments with randomly generated task sets are conducted to evaluate both the precision and efficiency of the proposed new method.

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

There are many timing unreliable computing components in modern computer systems, which are typically forbidden in hard real-time systems due to the timing uncertainty. In this paper, we propose a computation offloading mechanism to utilise these timing unreliable components in a hard real-time system, by providing local compensations. The key of the mechanism is to decide (1) how the unreliable components are utilized and (2) how to set the worst-case estimated response time. The local compensation has to start when the unreliable components do not deliver the results in the estimated response time. We propose a scheduling algorithm and its schedulability test to analyze the feasibility of the compensation mechanism. To validate the proposed mechanism, we perform a case study based on image-processing applications in a robot system and simulations. By adopting the timing unreliable components, the system can handle higher-quality images and with better performance.

Scheduling mixed-criticality systems that integrate multiple functionalities with different criticality levels into a shared platform appears to be a challenging problem, even on single-processor platforms. Multi-core processors are more and more widely used in embedded systems, which provide great computing capacities for such mixed-criticality systems. In this paper, we propose a partitioned scheduling algorithm MPVD to extend the state-of-the-art single-processor mixed-criticality scheduling algorithm EY to multiprocessor platforms. The key idea of MPVD is to evenly allocate tasks with different criticality levels to different processors, in order to better explore the asymmetry between different criticality levels and improve the system schedulability. Then we propose two enhancements to further improve the schedulability of MPVD. Experiments with randomly generated task sets show significant performance improvement of our proposed approach over existing algorithms.

The response time analysis problem is intractable for most existing real-time task models, except the simplest ones. Exact solutions for this problem in general have exponential complexity, and may run into scalability problems for large-scale task systems. In this paper, we study approximate analysis for static-priority scheduling of the Digraph Real-Time task model, which is a generalization of most existing graph-based real-time task models. We present two approximate analysis methods RBF and IBF, both of which have pseudo-polynomial complexity. We quantitatively evaluate their analysis precision using the metric speedup factor. We prove that RBF has a speedup factor of 2, and this is tight even for dual-task systems. The speedup factor of IBF is an increasing function with respect to k, the number of interfering tasks. This function converges to 2 as k approaches infinity and equals 1 when k = 1, implying that the IBF analysis is exact for dual-task systems. We also conduct simulation experiments to evaluate the precision and efficiency of RBF and IBF with randomly generated task sets. Results show that the proposed approximate analysis methods have very high efficiency with low precision loss.

High-speed, fixed-latency serial links find application in distributed data acquisition and control systems, such as the timing trigger and control (TTC) system for high energy physics experiments. However, most high-speed serial transceivers do not keep the same chip latency after each power-up or reset, as there is no deterministic phase relationship between the transmitted and received clocks after each power-up. In this paper, we propose a fixed-latency serial link based on high-speed transceivers embedded in Xilinx field programmable gate arrays (FPGAs). First, we modify the configuration and clock distribution of the transceiver to eliminate the phase difference between the clock domains in the transmitter/receiver. Second, we use the internal alignment circuit of the transceiver and a digital clock manager (DCM)/phase-locked loop (PLL) based clock generator to eliminate the phase difference between the clock domains in the transmitter and receiver. The test results of the link latency are shown. Compared with existing solutions, our design not only implements fixed chip latency, but also reduces the average system lock time.

Scheduling mixed-criticality systems is a challenging problem. Recently a number of new techniques are developed to schedule such systems, among which an approach called OCBP has shown interesting properties and drawn considerable attentions. OCBP explores the job-level priority order in a very flexible manner to drastically improve the system schedulability. However, the job priority exploration in OCBP involves nontrivial overheads. In this work, we propose a new algorithm LPA (Lazy Priority Adjustment) based on the OCBP approach, which improves the state-of-the-art OCBP-based scheduling algorithm PLRS in both schedulability and run-time efficiency. Firstly, while the time-complexity of PLRS' online priority management is quadratic, our new algorithm LPA has linear time-complexity at run-time. Secondly, we present an approach to calculate tighter upper bounds of the busy period size, and thereby can greatly reduce the run-time space requirement. Thirdly, the tighter busy period size bounds also improve the schedulability in terms of acceptance ratio. Experiments with synthetic workloads show improvements of LPA in all the above three aspects.

Smart Grid is an important application in Internet Of Things (IOT). Monitoring data in large-scale smart grid are massive, real-time and dynamic which collected by a lot of sensors, Intelligent Electronic Devices (IED) and etc.. All on account of that, traditional centralized storage proposals aren't applicable to data storage in large-scale smart grid. Therefore, we propose a data-centric storage approach in support of monitoring system in large-scale smart grid: Hierarchical Extended Storage Mechanism for Massive Dynamic Data (HES). HES stores monitoring data in different area according to data types. It can add storage nodes dynamically by coding method with extended hash function for avoiding data loss of incidents and frequent events. Monitoring data are stored dispersedly in the nodes of the same player by the multi-threshold levels means in HES, which avoids load skew. The simulation results show that HES satisfies the needs of massive dynamic data storage, and achieves load balance and a longer life cycle of monitoring network.

While much work has addressed energy minimizing problem of real-time sequential tasks, little has been done for the parallel real-time task case. In this paper, based on level-packing, we study energy minimization problem for parallel task systems with discrete operation modes and under timing constraints. For tasks with fixed (variable) parallel degrees, we first formulate the problem as a 0-1 Integer Linear Program (0-1 ILP), and then propose a polynomial-time complexity two-step (three-step) heuristic to determine task schedule and frequency assignment (and the task parallel degree). Our simulation result shows that the heuristics consume nearly the same energy as do 0-1 ILPs.

While much work has addressed the energy-efficient scheduling problem for uniprocessor or multiprocessor systems, little has been done for multicore systems. We study the multicore architecture with a fixed number of cores partitioned into clusters (or islands), on each of which all cores operate at a common frequency. We develop algorithms to determine a schedule for real-time tasks to minimize the energy consumption under the timing and operating frequency constraints. As technical contributions, we first show that the optimal frequencies resulting in the minimum energy consumption for each island is not dependent on the workload mapped but the number of cores and leakage power on the island, when not considering the timing constraint. Then for systems with timing constraints, we present a polynomial algorithm which derives the minimum energy consumption for a given task partition. Finally, we develop an efficient algorithm to determine the number of active islands, task partition and frequency assignment. Our simulation result shows that our approach significantly outperforms the related approaches in terms of energy saving.

Networks-on-Chip (NoC) has been introduced to offer high on-chip communication bandwidth for large scale multi-core systems. However, the communication bandwidth between NoC chips and off-chip memories is relatively low, which seriously limits the overall system performance. So optimizing the off-chip memory communication efficiency is a crucial issue in the NoC system design flow. In this paper, we present a memory access aware mapping algorithm for NoC, which explores SDRAM access parallelization in order to offer higher off-chip memory communication efficiency, and eventually achieve higher overall system performance. To the best of our knowledge, this is the first work to consider off-chip memory communication efficiency in application mapping on NoC. Experimental results showed that, comparing with classical NoC mapping algorithms, our algorithm can significantly improve the memory utilization and overall system throughput (on average 60% improvement).

Energy conservation is an important issue in the design of embedded systems. Dynamic Voltage Scaling (DVS) and Dynamic Power Management (DPM) are two widely used techniques for saving energy in such systems. In this paper, we address the problem of minimizing multi-resource energy consumption concerning both CPU and devices. A system is assumed to contain a fixed number of real-time tasks scheduled to run on a DVS-enabled processor, and a fixed number of off-chip devices used by the tasks during their executions. We will study the non-trivial time and energy overhead of device state transitions between active and sleep states. Our goal is to find optimal schedules providing not only the execution order and CPU frequencies of tasks, but also the time points for device state transitions. We adopt the frame-based real-time task model, and develop optimization algorithms based on 0-1 Integer Non-Linear Programming (0-1 INLP) for different system configurations. Simulation results indicate that our approach can significantly outperform existing techniques in terms of energy savings.

Static path analysis is a key process of Worst Case Execution Time (WCET) estimation, the objective of which is to find the execution path that has the largest execution time. Currently, there is an argument in the research community whether model checking is another good solution for WCET analysis, besides ILP. To our knowledge, no paper so far has addressed this argument with real performance data. In this paper, we implement both ILP and model checking for static path analysis of WCET, and the experiment results show that ILP yields very good performance, while model checking only works well for simple programs, and it is inclined to scalability problems when dealing with programs that have complex structures and large loop counts.

As Moore's law comes to an end, multi-processor (MP) systems are becoming increasingly important in embedded systems design, hence real-time schedulability analysis for MP systems has become an important research topic. In this paper, we present an exact method for schedulability analysis of global multiprocessor scheduling with either fixed-priority (FP) or earliest-deadline-first (EDF) algorithms using the model-checker NuSMV. Compared to safe but pessimistic schedulability tests based on processor utilization bounds, model-checking can provide an exact answer to the schedulability of a taskset, as well as quantitative information on each task's best-case and worst- case response times.

We study the schedulability analysis problem for nonpreemptive scheduling algorithms on multiprocessors. To our best knowledge, the only known work on this problem is the test condition proposed by Baruah for non-preemptive EDF scheduling, which will reject a task set with arbitrarily low utilization if it contains a task whose execution time is equal or greater than the minimal relative deadline among all tasks. In this paper, we firstly derive a linear-time test condition which avoids the problem mentioned above, by building upon previous work for preemptive multiprocessor scheduling. This test condition works on not only non-preemptive EDF, but also any other work-conserving non-preemptive scheduling algorithms. Then we improve the analysis and present test conditions of pseudo-polynomial time-complexity for Non-preemptive Earliest Deadline First scheduling and Non-preemptive Fixed Priority scheduling respectively. Experiments with randomly generated task sets show that our proposed test conditions, especially the improved test conditions, have significant performance improvements compared with [BAR-EDFnp].

Field Programmable Gate Arrays (FPGAs) are very popular in today's embedded systems design, and Partial Runtime-Reconfigurable (PRTR) FPGAs allow HW tasks to be placed and removed dynamically at runtime. Hardware task scheduling on PRTR FPGAs brings many challenging issues to traditional real-time scheduling theory, which have not been adequately addressed by the research community compared to software task scheduling on CPUs. In this article, we consider the schedulability analysis problem of HW task scheduling on PRPR FPGAs. We derive utilization bounds for several variants of global preemptive/nonpreemptive EDF scheduling, and compare the performance of different utilization bound tests.

Partially runtime-reconfigurable (PRTR) FPGAs allow hardware tasks to be placed and removed dynamically at runtime. We present an efficient algorithm for finding the complete set of maximal empty rectangles on a 2D PRTR FPGA, which is useful for online placement and scheduling of HW tasks. The algorithm is incremental and only updates the local region affected by each task addition or removal event. We use simulation experiments to evaluate its performance and compare to related work

Reconfigurable devices, such as field programmable gate arrays (FPGAs), are very popular in today's embedded systems design due to their low-cost, high-performance and flexibility. Partially runtime-reconfigurable (PRTR) FPGAs allow hardware tasks to be placed and removed dynamically at runtime. Hardware task scheduling on PRTR FPGAs brings many challenging issues to traditional real-time scheduling theory, which have not been adequately addressed by the research community compared to software task scheduling on CPUs. In this paper, we consider the schedulability analysis problem of HW task scheduling on PRPR FPGAs. We derive utilization bound tests for two variants of global EDF scheduling, and use synthetic tasksets to compare performance of the tests to existing work and simulation results.

Reconfigurable devices such as field programmable gate arrays (FPGAs) are very popular in today's embedded systems (design due to their low-cost, high-performance and flexibility. Partially runtime-reconfigurable (PRTR) FPGAs allow hardware tasks to be placed and removed dynamically at runtime. Hardware task scheduling on PRTR FPGAs brings many challenging issues to traditional real-time scheduling theory, which have not been adequately addressed by the real-time research community compared to software task scheduling on CPUs. In this paper, we present an efficient online task placement algorithm for minimizing fragmentation on PRTR FPGAs. First, we present a novel 2D area fragmentation metric that takes into account probability distribution of sizes of future task arrivals; second, we take into the time axis to obtain a 3D fragmentation metric. Simulation experiments indicate that our techniques result in low ratio of task rejection and high FPGA utilization compared to existing techniques

In this paper, we address the problem of static scheduling and software synthesis for dataflow graphs with the symbolic model-checker NuSMV using a two-step process: first use model-checking to obtain a static schedule with the objective of minimizing the data buffer size, then synthesize efficient code from the static schedule with the objective of minimizing code size and performance overheads due to runtime dynamic decisions. We show the effectiveness of these techniques using a number of digital signal processing examples.