开销敏感的多处理器最优节能实时调度算法

嵌入式多处理器系统的能耗问题变得日益重要,如何减少能耗同时满足实时约束成为多处理器系统节能实时调度中的一个重要问题.目前绝大多数研究基于关键速度降低处理器的频率以减少动态能耗,采用关闭处理器的方法减少静态能耗.虽然这种方法可以实现节能,但是不能保证最小化能耗.而现有最优的节能实时调度未考虑处理器状态切换的时间和能量开销,因此在切换开销不可忽视的实际平台中不再是最优的.文中针对具有独立动态电压频率调节和动态功耗管理功能的多处理器系统,考虑处理器切换开销,提出一种基于帧任务模型的最优节能实时调度算法.该算法根据关键速度来判断系统负载情况,确定具有最低能耗值的活跃处理器个数,然后根据状态切换开销来确定最优调度序列.该算法允许实时任务在处理器之间任意迁移,计算复杂度小,易于实现.数学分析证明了该算法的最优性.     

一种面向嵌入式实时系统的安全策略优化生成方法

由于受到系统资源和实时性的限制,对于嵌入式实时系统的安全扩展很难延用通用计算机系统的安全设计方法,因此需要对其进行专门的研究。为了在确保实时性的前提下使嵌入式实时系统的安全性达到最优,本文提出了一套完整的安全设计方法,包括安全任务图模型和安全评估模型,在此基础上,又提出了一种基于整数线性规划的安全策略优化生成方法ILPOS。该安全策略优化生成方法同时解决了安全算法选择和实时可调度性检测两方面的问题,克服了一般分阶段优化方法的不足,从而充分地利用系统可用时间来实现安全扩展。仿真实验结果表明,与传统的启发式安全设计算法相比,ILPOS方法在各种实时性约束条件下都能有效地提高系统的安全性。     

Combining sketches and wavelet analysis for multi time-scale network anomaly detection

With the rapid development and the increasing complexity of computer and communication systems and networks, traditional security technologies and measures can not meet the demand for integrated and dynamic security solutions. In this scenario, the use of Intrusion Detection Systems has emerged as a key element in network security.In this paper we address the problem proposing a wavelet-based technique able to detect network anomalies almost in real-time. In more detail, our approach is based on the combined use of sketches and wavelet analysis to reveal the anomalies in data collected at the router level. Moreover, to improve the detection rate we propose a multi time-scale analysis. The performance analysis, presented in this paper, demonstrates the effectiveness of the proposed method.     

Rolling-horizon scheduling for energy constrained distributed real-time embedded systems

Energy-efficient scheduling approaches are critical to battery driven real-time embedded systems. Traditional energy-aware scheduling schemes are mainly based on the individual task scheduling. Consequently, the scheduling space for each task is small, and the schedulability and energy saving are very limited, especially when the system is heavily loaded. To remedy this problem, we propose a novel rolling-horizon (RH) strategy that can be applied to any scheduling algorithm to improve schedulability. In addition, we develop a new energy-efficient adaptive scheduling algorithm (EASA) that can adaptively adjust supply voltages according to the system workload for energy efficiency. Both the RH strategy and EASA algorithm are combined to form our scheduling approach, RH-EASA. Experimental results show that in comparison with some typical traditional scheduling schemes, RH-EASA can achieve significant energy savings while meeting most task deadlines (namely, high schedulability) for distributed real-time embedded systems with dynamic workloads.     

基于构件的嵌入式实时软件建模与分析

嵌入式实时软件具有严格的时间要求,任何时间错误都可能造成重大的经济损失甚至导致灾难性的后果。因此,在软件开发早期,对其时间需求进行形式化的分析和验证是非常重要的。本文提出一种基于构件的嵌入式实时软件建模与分析方法,该方法不仅可以检测出需求模型中的时间冲突,有助于保证嵌入式实时软件时间约束的正确性,而且也也使得分析结果具有可复用、可扩展的优点。     

Online adaptive utilization control for real-time embedded multiprocessor systems

Many embedded systems have stringent real-time constraints. An effective technique for meeting real-time constraints is to keep the processor utilization on each node at or below the schedulable utilization bound, even though each task’s actual execution time may have large uncertainties and deviate a lot from its estimated value. Recently, researchers have proposed solutions based on Model Predictive Control (MPC) for the utilization control problem. Although these approaches can handle a limited range of execution time estimation errors, the system may suffer performance deterioration or even become unstable with large estimation errors. In this paper, we present two online adaptive optimal control techniques, one is based on Recursive Least Squares (RLS) based model identification plus Linear Quadratic (LQ) optimal controller; the other one is based on Adaptive Critic Design (ACD). Simulation experiments demonstrate both the LQ optimal controller and ACD-based controller have better performance than the MPC-based controller and the ACD-based controller has the smallest aggregate tracking errors.     

Multi-objective evolution of fuzzy systems

Fuzzy systems comprise one of the models best suited to function approximation problems, but due to the non linear dependencies between the parameters that define the system rules, the solution search space for this type of problems contains many local optima. Another important issue is the identification of the optimum structure for the fuzzy system. Depending on the complexity of the model, different solutions can be found with different compromises between their approximation error and their generalization properties. Thus, the problem becomes a multi-objective problem with two clearly competing objectives, the complexity of the model and its approximation error.The algorithms proposed in the literature to construct fuzzy systems from examples usually refine iteratively a unique model until a compromise between its complexity and its approximation error is found. This is not an adequate approach for this problem because there exists a set of Pareto-optimum solutions that can be considered equivalent. Thus, we propose the use of multi-objective evolutionary algorithms because, as they maintain a population of potential solutions for the problem, they are able to optimize both objectives simultaneously. We also incorporate some new expert evolutionary operators that try to avoid the generation of worse solutions in order to accelerate the convergence of the algorithm.The proposed algorithm is tested with some target functions widely used in the literature and the results obtained are compared to other approaches.     

InRob: An approach for testing interoperability and robustness of real-time embedded software

Advances in digital technologies have contributed for significant reduction in accidents caused by hardware failures. However, the growing complexity of functions performed by embedded software has increased the number of accidents caused by software faults in critical systems. Moreover, due to the highly competitive market, software intensive subsystems are usually developed by different suppliers. Often these subsystems are required to interact with each other in order to provide a collaborative service. Testing approaches for subsystems integration support verification of the quality of service, focusing on the subsystems interfaces. The increasing complexity and tight coupling of real-time subsystems make integration testing unmanageable. The ad-hoc approach for testing is becoming less effective and more expensive. This article presents an integration testing approach denominated InRob, designed to verify the interoperability and robustness related to timing constraints of real-time embedded software. InRob guides the construction of services, based on formal models, aiming at the specifications of interoperability and robustness of test cases related to delays and time-outs of the messages exchanged in the interfaces of interconnected subsystems. The proposed formalism supports automatic test cases generation by verifying the relevant properties in the service behavioral model. As timing constraints are critical properties of aerospace systems, the feasibility of InRob is showed in the integration testing process of a telescope onboard in a satellite. The process is instantiated with existing testing tools and the case study is the software embedded in the telescope.     

Robust sensor placement for pipeline monitoring: Mixed integer and greedy optimization

Intelligent water systems – aided by sensing technologies – have been identified as an important mechanism towards ensuring the resilience of urban systems. In this work, we study the problem of sensor placement that is robust to intermittent failures of sensors, i.e. sensor interruptions. We propose robust mixed integer optimization (RMIO) and robust greedy approximation (RGA) solution approaches. The underlying idea of both approaches is to promote solutions that achieve multiple detectability of events, such that these events remain detectable even when some sensors are interrupted. Additionally, we apply a previously proposed greedy approximation approach for solving the robust submodular function optimization (RSFO) problem. We compare scalability of these approaches and the quality of the solutions using a set of real water-networks. Our results demonstrate that considering sensor interruptions in the design stage improves sensor network performance. Importantly, we find that although the detection performances of RMIO and RGA approaches are comparable, RMIO generally has better performance than RGA, and is scalable to large-scale networks. Furthermore, the results demonstrate that RMIO and RGA approaches tend to outperform the RSFO approach.     

Performance and energy consumption estimation for commercial off-the-shelf component system design

Nowadays, component-based embedded real- time systems have been used to improve the system development as well as to keep cost down through the reuse of embedded software applications. Besides, the use of semi-formal models has been widely adopted in the embedded real-time system component and system life cycle due to their friendly and intuitive notations. However, the ever more complex systems of today require modeling methods that allow early detection of potential problems in the initial phases of development. This paper presents the mapping process of UML state machine diagram into a time Petri net with energy constraints so as to estimate execution time and energy consumption in early phases of the embedded real-time component development life cycle. The estimates obtained from the model show that the proposed approach is indeed a good approximation to the respective measures obtained from the real hardware platform.     

能量限制下基于效用获取的实时节能调度算法

面向基于电池供电的嵌入式实时系统,设计效用获取的实时节能调度算法.在实时系统的研究中,通常采用同步机制来实现任务对资源的互斥共享访问.在这种情况下,调度算法旨在能量受限下获得最大的系统效用,同时满足实时任务的可调度及任务同步.提出了两步节能算法(two-step energyefficient algorithm,TS...     

An event-based approach for formally verifying runtime adaptive real-time systems

Real-time and embedded systems are required to adapt their behavior and structure to runtime unpredicted changes in order to maintain their feasibility and usefulness. These systems are generally more difficult to specify and verify owning to their execution complexity. Hence, ensuring the high-level design and the early verification of system adaptation at runtime is very crucial. However, existing runtime model-based approaches for adaptive real-time and embedded systems suffer from shortcoming linked to efficiently and correctly managing the adaptive system behavior, especially that a formal verification is not allowed by modeling languages such as UML and MARTE profile. Moreover, reasoning about the correctness and the precision of high-level models is a complex task without the appropriate tool support. In this work, we propose an MDE-based framework for the specification and the verification of runtime adaptive real-time and embedded systems. Our approach stands for Event-B method to formally verify resources behavior and real-time constraints. In fact, thanks to MDE M2T transformations, our proposal translates runtime models into Event-B specifications to ensure the correctness of runtime adaptive system properties, temporal constrains and nonfunctional properties using Rodin platform. A flood prediction system case study is adopted for the validation of our proposal.

     

Hardware/software codesign and rapid prototyping of embeddedsystems

The complexity and the short time to market of embedded systems require the use of automated techniques during the specification, implementation, and testing phases of such systems. Due to the cost requirements and the timing constraints of such systems, application-specific hardware solutions are often needed, making the codesign of hardware and software a major topic for the design automation of embedded systems. This article describes tools for the analysis, synthesis, and rapid prototyping of distributed embedded real-time systems and presents a complete design flow from specification to implementation     

Sleep-aware mode assignment in wireless embedded systems

Minimizing energy consumption is a key issue in designing wireless embedded systems. While a lot of work has been done to manage energy consumption on single processor real-time systems, little work has been done in network-wide energy consumption management for real-time tasks. Existing work on network-wide energy minimization assumes that the underlying network is always connected, which is not consistent with the practice in which wireless nodes often turn off their network interfaces in a sleep schedule to reduce energy consumption. Moreover, existing sleep scheduling techniques are unaware of computation status and often lead to unnecessary wakeup overheads. In this paper, we propose solutions to minimize network-wide energy consumption for real-time tasks with precedence constraints executing on wireless embedded systems. Our solutions jointly consider the radio sleep scheduling of wireless nodes and the execution modes of processors. Based on different wireless network topologies, we propose energy management schemes to minimize energy consumption while guaranteeing the timing constraint and precedence constraint. When the precedence graph is a tree, our solution gives optimal result on energy management. The experiments show that our approach significantly reduces total energy consumption compared with previous works.     

VERTAF: an application framework for the design and verification of embedded real-time software

The growing complexity of embedded real-time software requirements calls for the design of reusable software components, the synthesis and generation of software code, and the automatic guarantee of nonfunctional properties such as performance, time constraints, reliability, and security. Available application frameworks targeted at the automatic design of embedded real-time software are poor in integrating functional and nonfunctional requirements. To bridge this gap, we reveal the design flow and the internal architecture of a newly proposed framework called verifiable embedded real-time application framework (VERTAF), which integrates software component-based reuse, formal synthesis, and formal verification. A formal UML-based embedded real-time object model is proposed for component reuse. Formal synthesis employs quasistatic and quasidynamic scheduling with automatic generation of multilayer portable efficient code. Formal verification integrates a model checker kernel from SGM, by adapting it for embedded software. The proposed architecture for VERTAF is component-based and allows plug-and-play for the scheduler and the verifier. Using VERTAF to develop application examples significantly reduced design effort and illustrated how high-level reuse of software components combined with automatic synthesis and verification can increase design productivity.     

A novel key-embedded scheme for secure video multicast systems

The secure distribution and maintenance of key information are essential for controlling access to video multicast systems. Unlike the conventional approaches using a dedicated channel independent of the video stream, this paper proposes a novel data embedding scheme, which we refer to as SMDE (statistical modulation data embedding), to support the media-dependent approach that exploits data-dependent channel to transmit and maintain key information. Using embedded data to convey key information is able to achieve added security and reduce bandwidth resource consumption. To this end, we present some new algorithms to embed key messages. By adopting the statistical properties of host video signal, new coding approach for embedded data, and error control algorithm, the proposed SMDE scheme can provide error resilience, transparence for adaptation mechanism, high accuracy of detecting embedded data and real-time processing capability for video applications. These advantages have been demonstrated by the extensive experimental results.     

A model-driven approach for developing a model repository: Methodology and tool support

Several development approaches have been proposed to cope with the increasing complexity of embedded system design. The most widely used approaches are those using models as the main artifacts to be constructed and maintained. The desired role of models is to ease, systematize and standardize the approach to the construction of software-based systems. To enforce reuse and interconnect the process of model specification and system development with models, we promote a model-based approach coupled with a model repository. In this paper, we propose a model-driven engineering methodological approach for the development of a model repository and an operational architecture for development tools. In addition, we provide evidence of the benefits and feasibility of our approach by reporting on a preliminary prototype that provides a model-based repository of security and dependability (S&D) pattern models. Finally, we apply the proposed approach in practice to a use case from the railway domain with strong S&D requirements.     

Multi-agent based approach for single machine scheduling with sequence-dependent setup times and machine maintenance

Scheduling of single machine in manufacturing systems is especially complex when the order arrivals are dynamic. The complexity of the problem increases by considering the sequence-dependent setup times and machine maintenance in dynamic manufacturing environment. Computational experiments in literature showed that even solving the static single machine scheduling problem without considering regular maintenance activities is NP-hard. Multi-agent systems, a branch of artificial intelligence provide a new alternative way for solving dynamic and complex problems. In this paper a collaborative multi-agent based optimization method is proposed for single machine scheduling problem with sequence-dependent setup times and maintenance constraints. The problem is solved under the condition of both regular and irregular maintenance activities. The solutions of multi-agent based approach are compared with some static single machine scheduling problem sets which are available in the literature. The method is also tested under real-time manufacturing environment where computational time plays a critical role during decision making process.     

基于实时自动机的连续时段演算的验证

时段演算是描述和推导嵌入式实时系统和混成系统性质的一种区间时态逻辑.扩展线性时段不变式是时段演算的重要子集.针对实时自动机,提出一种连续时间语义下扩展线性时段不变式的有界模型检验方法.该方法将扩展线性时段不变式的有界模型检验问题转化为量词线性算术公式的正确性问题,从而可以采用量词消去技术进行求解.首先,运用符号化的思想,在实时自动机上利用深度优先搜索找到所有满足观测时长约束的符号化路径片段;然后,将每条符号化路径片段转化为一个量词线性算术公式;最后,利用量词消去工具求解.与已有工作相比,基于实时自动机设计了验证算法.另外,降低了验证复杂度,并且加速了验证过程的实际速度.