A major issue in wireless sensor networks is to prolong network lifetime by efficient energy management. In this paper we present an initial study of maximum lifetime routing in sparse sensor networks. We have studied simulations of how different heuristic routing algorithms influence the energy consumption of individual sensor nodes, and thus the functional lifetime of a sparse sensor network. The functional lifetime of the sensor network can be either until the first node has run out of energy or until a certain threshold of nodes has demised. We have also compared the maximum lifetime of the heuristic algorithms to the maximum lifetime of an optimal routing solution. Our simulations with nonaggregated data indicates that using one of the presented heuristic routing algorithms are not enough to find a near optimal routing. Our study is made in the AROS framework.

Engineers of embedded software systems rely on efficient design techniques and tools along with efficient run-time support. In the design of complex embedded real-time systems, the hierarchical scheduling framework (HSF) has been introduced as a design-time framework enabling compositional schedulability analysis of embedded software systems with real-time properties. Moreover, the HSF provides a run-time framework guaranteeing that these nonfunctional requirements are met. In this paper a system consists of a number of semi- independent components called subsystems, and these subsystems are allowed to share logical resources. The HSF makes sure that the individual subsystems respect their allocated CPU budgets. However, as semi-independent subsystems share logical resources, extra complexity is introduced. Specifically, the contribution of this paper is a novel method to allow for budget overruns; a common scenario when a subsystem utilizes shared logical resources. This proposed method is not only more resource efficient than existing methods, but it is also more appropriate for supporting composability of independently developed real-time subsystems.

The paper presents two novel methods to bound the stack memory used in preemptive, shared stack, real-time systems. The first method is based on branch-and-bound search for possible preemption patterns, and the second one approximates the first in polynomial time. The work extends previous methods by considering a more general task-model, in which all tasks can share the same stack. In addition, the new methods account for precedence and offset relations. Thus, the methods give tight bounds for a large set of realistic systems. The methods have been implemented and a comprehensive evaluation, comparing our new methods against each other and against existing methods, is presented. The evaluation shows that our exact method can significantly reduce the amount of stack memory needed.

The hierarchical scheduling framework (HSF) has been introduced as a design-time framework enabling compositional schedulability analysis of embedded software systems with real-time properties. In this paper a system consists of a number of semi-independent components called subsystems. Subsystems are developed independently and later integrated to form a system. To support this design process, our proposed methods allow non-intrusive configuration and tuning of subsystem timing-behaviour via subsystem interfaces for selecting scheduling parameters. This paper considers two methods to handle overruns due to resource sharing between subsystems in the HSF. We present the scheduling algorithms for overruns and their associated schedulability analysis, together with analysis that shows under what circumstances one or the other overrun method is preferred. Furthermore, we show how to calculate resource-holding times within our framework.

In this paper, we present the development of a plug-in framework for integration of real-time analysis methods in the Rubus Integrated Component Environment (Rubus-ICE). We also present the implementation, and evaluate the integration, of two state of the art analysis techniques (i) response-time analysis for tasks with offsets and (ii) shared stack analysis, as plug-ins, in the Rubus-ICE framework. The paper shows that the proposed framework is well suited for integration of complex analysis methods. However, experience also show that analysis methods are not easily transferred from an academic environment to industry. The main reason for this, we believe, originates from differences in requirements and assumptions between industry and academia.

Efficient design-time management and documentation of run-time data elements are of paramount importance when developing and maintaining modern real-time systems. In this paper, we present the results of an industrial case-study in which we have studied the state of practice in data management and documentation. Representatives from five companies within various business segments have been interviewed and our results show that various aspects of current data management and documentation are problematic and not yet mature. Results show that companies today have a fairly good management of distributed signals, while internal ECU signals and states are, in many cases, not managed at all. This lack of internal data management results in costly development and maintenance and is often entirely dependent of the know-how of single individual experts. Furthermore, it has, in several cases, resulted in unused and excessive data in the systems due to the fact that whether or not a data is used is unknown.

This paper presents algorithms that (1) facilitate system-independent synthesis of timing-interfaces for subsystems and (2) system-level selection of interfaces to minimize CPU load. The results presented are developed for hierarchical fixed-priority scheduling of subsystems that may share logical recourses (i.e. semaphores). We show that the use of shared resources results in a tradeoff problem, where resource locking times can be traded for CPU allocation, complicating the problem of finding the optimal interface configuration subject to schedulability. This paper presents a methodology where such a tradeoff can be effectively explored. It first synthesizes a bounded set of interface-candidates for each subsystem, independently of the final system, such that the set contains the interface that minimizes system load for any given system. Then, integrating subsystems into a system, it finds the optimal selection of interfaces. Our algorithms have linear complexity to the number of tasks involved. Thus, our approach is also suitable for adaptable and reconfigurable systems.

This paper presents a protocol for resource sharing in a hierarchical real-time scheduling framework. Targeting real-time open systems, the protocol and the scheduling framework significantly reduce the efforts and errors associated with integrating multiple semi-independent subsystems on a single processor. Thus, our proposed techniques facilitate modern software development processes, where subsystems are developed by independent teams (or subcontractors) and at a later stage integrated into a single product. Using our solution, a subsystem need not know, and is not dependent on, the timing behaviour of other subsystems; even though they share mutually exclusive resources. In this paper we also prove the correctness of our approach and evaluate its efficiency.

Testing in realistic environments is often overlooked in the early development of new technology. This paper describes a test to evaluate the whole chain from an accelerometer mounted on a motor to a sensor node sending wireless data to an access point. A pilot gives a great opportunity to get input from end-users (which could be very useful at the initial stages of a project), and provide potential contacts for next pilots. The goal of the pilot was to get a better understanding of the targeted environment and possible interference It may also lead to the discovery of issues not yet thought of issues important for the resulting design of the end product.

We present a contract-based technique to achieve reuse of known worst-case execution times (WCET) in conjunction with reuse of software components. For resource constrained systems, or systems where high degree of predictability is needed, classical techniques for WCET- estimation will result in unacceptable overestimation of the execution-time of reusable software components with rich behavior. Our technique allows different WCETs to be associated with subsets of the component behavior. The appropriate WCET for any usage context of the component is selected be means of component contracts over the input domain. In a case-study we illustrate our technique and demonstrate its potential in achieving tight WCET- estimates for reusable components with rich behavior.

This paper presents a novel method to determine the maximum stack memory used in preemptive, shared stack, real-time systems. We provide a general and exact problem formulation applicable for any preemptive system model based on dynamic (run-time) properties. We also show how to safely approximate the exact stack usage by using static (compile time) information about the system model and the underlying run-time system on a relevant and commercially available system model: a hybrid, statically and dynamically, scheduled system. Comprehensive evaluations show that our technique significantly reduces the amount of stack memory needed compared to existing analysis techniques. For typical task sets a decrease in the order of 70% is typical

In previous work, we presented a tight approximate response-time analysis for tasks with offsets. While providing a tight bound on response times, the tight analysis exhibits similarly long execution times as does the traditional methods for calculating response-times for tasks with offsets. The existing method for fast analysis of tasks with offsets is not applicable to the tight analysis. In this paper we extend the fast analysis to handle the distinguishing trait of the tight analysis; continuously increasing interference functions. Furthermore, we provide another speedup; by introducing pessimism in the modelling of interference at certain points, we speed up the convergence of the numerical solving for response-times without increasing the pessimism of the resulting response-times. The presented fast-and-tight analysis is guaranteed to calculate the same response-times as the tight analysis, and in a simulation study we obtain speedups of more than two orders of magnitude for realistically sized tasks sets compared to the tight analysis. We also demonstrate that the fast-and-tight analysis has comparable execution time to that of the fast analysis. Hence, we conclude that the fast-and-tight analysis is the preferred analysis technique when tight estimates of response-times are needed, and that we do not need to sacrifice tightness for analysis speed; both are obtained with the fast-and-tight analysis.

We present 2V-DBP-SNAP, an algorithm that allows hard real-time tasks in an embedded real-time control system to read a snapshot of a number of data elements in a real-time database. Furthermore, 2V-DBP-SNAP allows these data elements to be shared with soft real-time tasks, which access them using a database query language, and with other hard real-time tasks that use database pointers. 2V-DBP-SNAP allows temporal behavior and memory consumption to be accurately predicted. Introducing snapshot transactions is beneficial for embedded control-systems, such as for engine control in an automotive system, since a snapshot of the state of the environment can be collected, e.g., the state of all cylinders in the engine. 2V-DBP-SNAP is lightweight and predictable, both with respect to computational and memory overhead, and is therefore highly suited for resource constrained systems.

This paper investigates the concept of share-driven scheduling of networks using servers with real-time properties. Share-driven scheduling provides fairness and bandwidth isolation between predictable as well as unpredictable streams of messages on the network. The need for this kind of scheduled real-time communication network is high in applications that have requirements on flexibility, both during development for assigning communication bandwidth to different applications, and during run-time to facilitate dynamic addition and removal of system components. We illustrate the share-driven scheduling concept by applying it to the popular controller area network (CAN). We propose a scheduling mechanism that we call simple server-scheduled CAN (S/sup 3/-CAN), for which we also present an associated timing analysis. Additionally, we present a variant of S/sup 3/-CAN called periodic server-scheduled CAN (PS/sup 2/-CAN), which for some network configurations gives lower worst-case response-times than S/sup 3/-CAN. Also for this improvement, a timing analysis is presented. Moreover, we use simulation to evaluate the timing performance of both S/sup 3/-CAN and PS/sup 2/-CAN, comparing them with other scheduling mechanisms.

We propose monitoring of software components, and use of monitored software components, as a general approach for engineering of embedded computer systems. In our approach, a component's execution is continuously monitored and experience regarding component behaviour is accumulated. As more and more experience is collected the confidence in the component grows; with the goal to eventually allow certification of the component. Continuous monitoring is also the base for contract checking, and provides means for post-mortem crash analysis; an important prerequisite for many companies to start use 3rd party component in their dependable systems. In this paper we show how four software engineering goals can be reached by monitoring four component properties.

We present a method that enables an efficient implementation of the approximative response-time analysis (RTA) for tasks with offsets presented by Tindell [(1992)] and Palencia Gutierrez et al. [(1998)]. The method allows for significantly faster implementations of schedulability tools using RTA. Furthermore, reducing computation time, from tens of milliseconds to just a fraction of a millisecond, as we show, is a step towards online RTA in for example admission control systems. We formally prove that our reformulation of earlier presented equations is correct and allow us to statically represent parts of the equation, reducing the calculations during fix-point iteration. We show by simulations that the speedup when using our method is substantial. When task sets grow beyond a trivial number of tasks and/or transactions a speed-up of more than 100 times (10 transactions and 10 tasks/transaction) compared to the original analysis can be obtained.