Complex embedded systems, such as robotics, automotive and high-tech manufacturing, are hard to maintain due to their complex nature. To advance our understanding of the software engineering practice for complex embedded systems, we conducted a series of empirical studies at ASML, a leading manufacturer of lithography machines for semi-conductor industry. We started with an interview study exploring how developers use execution logs, essential artifacts that capture the runtime behavior of software systems. The empirical insights obtained from this study led us to explore subtopics about model inference from logs, modeling practice and log comparison. Motivated by the observation that developers often manually sketch behavioral models based on logs, we propose a model inference technique that can extract models by combining log analysis, and analysis of a running system under stimuli. As observed in this model inference study, the transition from code to models requires developers to work with a hybrid system which consists of handwritten code and models. We then study modeling practices and the roles of model in such hybrid systems. Particularly, we study why developers violate modeling guidelines, providing implications for researchers and tool builders to support developers in modeling complex embedded systems. Another interesting observation from the interview study is that developers face challenges in comparing multiple logs generated from such systems. We therefore conduct a literature study to provide an overview of the existing techniques and identify the limitations of the existing techniques. In this project, we study logs and models in complex embedded systems, providing tool builders, researchers and practitioners with implications to facilitate log analysis, model inference, modeling practice and log comparison.

Software-defined networking (SDN) is a cornerstone of next-generation networks and has already led to numerous advantages for data-center networks and wide-area networks. However, SDN is not widely adopted in constrained networks, such as Wireless Sensor Networks (WSN), due to excessive control overhead, lossy medium, and in-band control channels. Therefore, a key challenge to enable Software-Defined Wireless Sensor Networks (SD-WSN) is to reduce the number of control messages required to configure the data plane. In this paper, we propose a cluster-based flow control approach in hybrid SDNs. Our approach is hybrid in the sense that it takes advantage of distributed legacy routing and centralized SDN routing. In addition, it makes a trade-off between the granularity of flow control and the communication overhead induced by the SDN controller. The approach partitions a network into clusters with minimum number of border nodes. Instead of handling the individual flows of each node, the SDN controller only manages incoming and outgoing traffic flows of clusters through border nodes, while the flows inside each cluster are controlled by a distributed legacy WSN routing algorithm. Our proof-of-concept implementations in both software and hardware show that our approach is efficient with respect to reducing the number of nodes that must be managed and the number of control messages. In comparison to benchmark solutions with and without clustering, our solution reduces communication costs for flow configuration in an SD-WSN at least by 27% and at most by 88% respectively, without degrading packet delay nor delivery rate.

Abstract Context Models, as the main artifact in model-driven engineering, have been extensively used in the area of embedded systems for code generation and verification. One of the most popular behavioral modeling techniques is the state machine. Many state machine modeling guidelines recommend that a state machine should have more than one state in order to be meaningful. However, single-state state machines (SSSMs) violating this recommendation have been used in modeling cases reported in the literature. Objective We aim for understanding the phenomenon of using SSSMs in practice as understanding why developers violate the modeling guidelines is the first step towards improvement of modeling tools and practice. Method To study the phenomenon, we conducted an exploratory study which consists of two complementary studies. The first study investigated the prevalence and role of SSSMs in the domain of embedded systems, as well as the reasons why developers use them and their perceived advantages and disadvantages. We employed the sequential explanatory strategy, including repository mining and interview, to study 1500 state machines from 26 components at ASML, a leading company in manufacturing lithography machines from the semiconductor industry. In the second study, we investigated the evolutionary aspects of SSSMs, exploring when SSSMs are introduced to the systems and how developers modify them by mining the largest state-machine-based component from the company. Results We observe that 25 out of 26 components contain SSSMs. Our interviews suggest that SSSMs are used to interface with the existing code, to deal with tool limitations, to facilitate maintenance and to ease verification. Our study on the evolutionary aspects of SSSMs reveals that the need for SSSMs to deal with tool limitations grew continuously over the years. Moreover, only a minority of SSSMs have been changed between SSSM and multiple-state state machine (MSSM) during their evolution. The most frequent modifications developers made to SSSMs is inserting events with constraints on the execution of the events. Conclusions Based on our results, we provide implications for developers and tool builders. Furthermore, we formulate hypotheses about the effectiveness of SSSMs, the impacts of SSSMs on development, maintenance and verification as well as the evolution of SSSMs.

Smartphones, wearables, and Internet-of-Things (IoT) devices produce a wealth of data that cannot be accumulated in a centralized repository for learning supervised models due to privacy, bandwidth limitations, and the prohibitive cost of annotations. Federated learning provides a compelling framework for learning models from decentralized data, but conventionally, it assumes the availability of labeled samples, whereas on-device data are generally either unlabeled or cannot be annotated readily through user interaction. To address these issues, we propose a self-supervised approach termed scalogram-signal correspondence learning based on wavelet transform (WT) to learn useful representations from unlabeled sensor inputs as electroencephalography, blood volume pulse, accelerometer, and WiFi channel-state information. Our auxiliary task requires a deep temporal neural network to determine if a given pair of a signal and its complementary view (i.e., a scalogram generated with WT) align with each other, by optimizing a contrastive objective. We extensively assess the quality of learned features with our multiview strategy on diverse public data sets, achieving strong performance in all domains. We demonstrate the effectiveness of representations learned from an unlabeled input collection on downstream tasks with training a linear classifier over pretrained network, usefulness in low-data regime, transfer learning, and cross-validation. Our methodology achieves competitive performance with fully supervised networks and it works significantly better than pretraining with autoencoders in both central and federated contexts. Notably, it improves the generalization in a semisupervised setting as it reduces the volume of labeled data required through leveraging self-supervised learning.

In this paper, we introduce a Video Representation Fusion Network (VRFN) for movie genre classification. Different from the previous works, which use frame-level features for movie genre classification, our approach uses video classification architecture to create video-level features from a group of frames and fuse these features temporally to learn long-term spatiotemporal information for the movie genre classification task. We use a pre-trained I3D model to generate intermediate video representations and connect it with a C3D-LSTM model for feature fusion and movie genre classification. LMTD-9 dataset which contains 4007 trailers multi-labeled with 9 movie genres is used for training and evaluation of the model. The experimental results demonstrate that learning long-term temporal dependencies by fusing video representations improves the performance in movie genre classification. Our best model outperforms state-of-the-art methods by 3.4% improvement in AUPRC(macro).

Models, as the main artifact in model-driven engineering, have been extensively used in the area of embedded systems for code generation and verification. One of the most popular behavioral modeling techniques is state machine. Many state machine modeling guidelines recommend that a state machine should have more than one state in order to be meaningful. However, single-state state machines (SSSMs) violating this recommendation have been used in modeling cases reported in the literature.

Processing big data generated in large Internet of Things (IoT) networks is challenging current techniques. To date, a lot of network clustering approaches have been proposed to improve the performance of data collection in IoT. However, most of them focus on partitioning networks with static topologies, and thus they are not optimal in handling the case with moving objects in the networks. Moreover, to the best of our knowledge, none of them has ever considered the performance of computing in edge servers. To solve these problems, we propose a highly efficient IoT network dynamic clustering solution in edge computing using deep reinforcement learning (DRL). Our approach can both fulfill the data communication requirements from IoT networks and load-balancing requirements from edge servers, and thus provide a great opportunity for future high performance IoT data analytics. We implement our approach using a Deep Q-learning Network (DQN) model, and our preliminary experimental results show that the DQN solution can achieve higher scores in cluster partitioning compared with the current static benchmark solution.

Software-defined networking (SDN) is a cornerstone of next-generation networks and has already led to numerous advantages for data-center networks and wide-area networks, for instance in terms of reduced management complexity and more fine-grained traffic engineering. However, the design and implementation of SDN within wireless sensor networks (WSN) have received far less attention. Unfortunately, because of the multi-hop type of communication in WSN, a direct reuse of the wired SDN architecture could lead to excessive communication overhead. In this paper, we propose a cluster-based flow management approach that makes a trade-off between the granularity of monitoring by an SDN controller and the communication overhead of flow management. A network is partitioned into clusters with a minimum number of border nodes. Instead of having to handle the individual flows of all nodes, the SDN controller only manages incoming and outgoing traffic flows of clusters through border nodes. Our proof-of-concept implementations in software and hardware show that, when compared with benchmark solutions, our approach is significantly more efficient with respect to the number of nodes that must be managed and the number of control messages exchanged.

Stress and accompanying physiological responses can occur when everyday emotional, mental and physical challenges exceed one's ability to cope. A long-term exposure to stressful situations can have negative health consequences, such as increased risk of cardiovascular diseases and immune system disorder. It is also shown to adversely affect productivity, well-being, and self-confidence, which can lead to social and economic inequality. Hence, a timely stress recognition can contribute to better strategies for its management and prevention in the future. Stress can be detected from multimodal physiological signals (e.g. skin conductance and heart rate) using well-trained models. However, these models need to be adapted to a new target domain and personalized for each test subject. In this paper, we propose a deep reconstruction classification network and multi-task learning (MTL) for domain adaption and personalization of stress recognition models. The domain adaption is achieved via a hybrid model consisting of temporal convolutional and recurrent layers that perform shared feature extraction through supervised source label predictions and unsupervised target data reconstruction. Furthermore, MTL based neural network approach with hard parameter sharing of mutual representation and task-specific layers is utilized to acquire personalized models. The proposed methods are tested on multimodal physiological time-series data collected during driving tasks, in both real-world and driving simulator settings.

Embedded systems are a class of computer systems that are typically characterized by a tight interaction with the physical environment. Various methodologies have been adopted for the development of such systems, ranging from traditional waterfall to modern agile techniques. One of the agile techniques that has recently attracted increasing attention is Behavior-Driven Development (BDD). BDD promotes the engagement of all stakeholders in every development iteration to minimize the misunderstanding between technical and non-technical stakeholders and, consequently, to speed up the development process and lower the costs. In this paper, we investigate the application of BDD to the development of embedded systems, especially focusing on the testing of timing requirements for real-time embedded software. In particular, we extend BDD with time-related concepts and propose an approach to generate test code for the verification of timing behavior of real-time embedded systems. Our approach offers more automation for the development of test code compared to existing BDD tools, thus minimizing the risk of timing faults and reducing development costs and time-to-market.

In the high-tech and automotive industry, bandwidth considerations and widely accepted standardization are two important reasons why Ethernet is currently being considered as an alternative solution for real-time communication (compared to traditional fieldbusses). Although Ethernet was originally not intended for this purpose, the development of the Ethernet AVB standard enables its use for transporting high-volume data (e.g. from cameras and entertainment applications) with low-latency guarantees. In complex industrial systems, the network is shared by many applications, developed by different parties. To face this complexity, the development of these applications must be kept as independent as possible. In particular, from a network point of view, progress of all communication streams must be guaranteed, and the performance for individual streams should be predictable using only information regarding the stream under study and the general parameters of the communication standard used by the network. Initial methods to guarantee latency for Ethernet AVB networks rely on the traditional busy-period analysis. Typically, these methods are based on knowledge of the inter-arrival patterns of both the stream under study and the interfering streams that also traverse the network. The desired independence is therefore not achieved. In this paper, we present an independent real-time analysis based on so-called eligible intervals , which does not rely on any assumptions on interfering priority classes other than those enforced in the Ethernet AVB standard. We prove this analysis is tight in case there is only a single higher-priority stream, and no additional information on interference is known. In case there are multiple higher-priority streams, we give conditions under which the analysis is still tight. Furthermore, we compare the results of our approach to the two most recent busy-period analyses, point out sources of pessimism in these earlier works, and argue that assuming more information on the sources of interference (e.g. a minimal inter-arrival time between interfering frames) has only limited advantages.

Statistical quality control (SQC) applies multivariate statistics to monitor production processes over time and detect changes in their performance in terms of meeting specification limits on key product quality metrics. These limits are imposed by customers and typically assumed to be a single target value, however, for some products, it is more reasonable to target a range of values. Under this assumption we propose a multi-stage approach for mapping operating conditions to product quality classes. We use principal component analysis (PCA) and a pattern mining algorithm to reduce dimensionality and identify predictive patterns in time series of operating conditions in order to improve the performance of the classifier. We apply this approach to an industrial machining process and obtain significant improvements over models trained using features based on the last value of each process variable.

Summary In cyber‐physical systems such as intelligent lighting, the system responds autonomously to observed changes in the environment. In such systems, more than one output may be acceptable for a given input scenario. This type of relationship between the input and output makes it difficult to analyze machine learning algorithms using commonly used performance metrics such as classification accuracy (CA). CA only measures whether a predicted output is right or not, whereas it is more important to determine whether the predicted output is relevant for the given context or not. In this direction, we introduce a new metric, the relevance score (RS) that is effective for the class of applications where user perception leads to non‐deterministic input–output relationships. RS determines the extent by which a predicted output is relevant to the user's context and behaviors, taking into account the variability and bias that come with human perception factors. We assess the performance of a number of machine learning algorithms, using different datasets, including data from an intelligent lighting pilot. We find that using RS instead of CA is appropriate to analyze the performance of conventional machine learning algorithms, particularly for the class of non‐deterministic multiple‐output problems. Our method may be applied to other scenarios in which cyber‐physical systems involve humans in the control loop. Copyright © 2016 John Wiley & Sons, Ltd.

Asynchronous Radio Duty Cycling (ARDC) protocols can make embedded networked devices more energy efficient by keeping their radio off most of the time without a need for synchronization between devices. Some ARDC protocols can operate under 6LoWPAN adaptation layer in order to enable the vision of Internet-of-Things for battery operated devices. In this paper, we propose three different protocols which are modifications of the widely accepted ARDC protocol, ContikiMAC. The proposed solutions drastically improve energy efficiency and link layer delay for broadcast packets. Moreover, the proposed solutions are backward compatible with ContikiMAC and provide high reliability against frame reception errors. We present a detailed comparison with the legacy ContikiMAC and a standardized ARDC protocol, IEEE 802.15.4e Coordinated Sampled Listening (CSL), as well as the case of no duty cycling.

Radio duty cycling (RDC) is a method for making resource constrained Internet-of-Things devices more energy efficient. RDC protocols achieve energy efficiency by keeping their radio off most of the time. Asynchronous RDC (ARDC) forms a subclass in which devices are not synchronized. ARDC behavior may lead to reliability and predictability problems for broadcast and unicast message transmissions in the MAC layer when the parameters of the protocol are not carefully selected, which we demonstrate by concrete examples. We investigate the dependability issues of generic ARDC protocols and provide analytical results for parameter settings that enhance dependability, while maintaining performance of the ARDC protocols in terms of energy efficiency and link delay. We also provide an analytical comparison of two widely accepted protocols, ContikiMAC and IEEE 802.15.4e Coordinated Sampled Listening.

The IETF ROLL working group developed Routing Protocol for Low Power and Lossy Networks (RPL) for packet routing within Low power and Lossy Networks (LLNs) formed by resource constrained devices. RPL handles LLN issues such as unreachable parent and routing loops by triggering reconstruction of routing tree. For unreachable neighbor detection, RPL requires an external mechanism with very low communication overhead. This rules out the use of proactive mechanisms that employ keep-alive messages. Instead, RPL suggests to use IPv6 Neighbor Unreachability Detection (NUD), which is a reactive mechanism maintaining timers that trigger control messages. However, due to the use of fixed timeout intervals, NUD suffers from frequent premature timeouts and the communication overhead of NUD is still substantial. We propose a cross layer trust-based NUD mechanism, which adapts its timeout intervals based on network traffic without the need for explicit coordination among nodes. The proposed mechanism takes advantage of overhearing at the link layer and uses the statistics about packets that are not sent to the node itself, i.e. that would otherwise be discarded. Our evaluation shows that the proposed mechanism decreases the number of control messages significantly, while the packet delivery rate remains comparable to classical NUD.

Busy period analysis is often used as a basis for worst-case response time analysis of priority based systems. However, when shaping strategies are used to prevent starvation of lower priorities, it becomes difficult to achieve tightness results using this method. The reason for this is that a busy period is defined as the longest interval in which there exists pending load. It is exclusively based on execution time, and does not take the amount of provided bandwidth into account. As a consequence, it is less suitable for the study of idling systems. In particular, we do not yet have tightness results regarding the analysis of the Ethernet AVB standard, in which credit-based shaping is applied. In this paper, we propose an alternative to the use of busy periods. We show that, by defining an eligible interval in such a way that provisioning is taken into account, tight worst-case response time bounds can more easily be obtained for Ethernet AVB, at least in the case of either lower-or higher-priority interference.

Dynamic Street Lighting Systems (DSLS) have been advertised as a means to reduce cost, reduce light pollution and increase feelings of safety. The dynamism is based on sensing and actuation, and uses communication between the light poles. While there have been many proposals for dynamic street lighting there is actually little data available about their operation. In this paper we present results from the monitoring of an installed DSLS in Eindhoven, The Netherlands for a period of more than a year. Besides questions of energy saving, we examined commissioning problems, effects of message loss, effects of the weather and general performance characteristics. The contribution includes a novel model for describing the outcomes of metrics as a function of sensor information. The results demonstrate that energy saving can be a strong driver for the introduction of DSLS but economic savings much less; the results also show a versatile usage of the collected data.

The functional correctness and the performance of smart environment applications can be hampered by faults. Fault tolerance solutions aim to achieve graceful performance degradation in the presence of faults, ideally without leading to application failures. This is a reactive approach and, by itself, gives little flexibility and time for preventing potential failures. We argue that the key step in achieving high dependability is to predict faults before they occur. We propose a proactive fault prevention framework, which predicts potential low-level hardware, software and network faults and tries to prevent them via dynamic adaptation. Many statistical fault prediction algorithms have been proposed in the literature. In this paper, we evaluate and compare the performances of two fault prediction models, namely, multiple linear regression, and artificial neural networks by using them to predict the remaining useful life of a battery-powered wireless sensor network node. The results show that the proposed framework will provide better control over performance degradation of smart environment applications, and will increase reliability and availability, and reduce manual user interventions.

Low-power wireless networks play an important role in the Internet of Things. Typically, these networks consist of a very large number of lossy and low-capacity devices, challenging the current state of the art in protocol design. In this context the Trickle algorithm plays an important role, serving as the basic mechanism for message dissemination in notable protocols such as RPL and MPL. While Trickle's broadcast suppression mechanism has been proven to be efficient, recent work has shown that it is intrinsically unfair in terms of load distribution and that its performance relies strongly on network topology. This can lead to increased end-to-end delays (MPL), or creation of sub-optimal routes (RPL). Furthermore, as highlighted in this work, there is no clear consensus within the research community about what the proper parameter settings of the suppression mechanism should be. We propose an extension to the Trickle algorithm, called adaptive-k, which allows nodes to individually adapt their suppression mechanism to local node density. Supported by analysis and a case study with RPL, we show that this extension allows for an easier configuration of Trickle, making it more robust to network topology.

In this paper, we compare and survey different ways to model the scheduling delays corresponding to non-preemptive critical sections being executed by the tasks of different components that ultimately need to share one processor. We focus on the performance of compositional timing analyses for systems and we compare different protocols for the arbitration of tasks that wish to execute critical sections. Such analysis methods support timing predictable composition of independently validated components. This validation consists of analyzing the worst-case impact of critical sections on the schedules of the component's tasks. Finally, we evaluate the performance of the analysis methods by means of a simulation study.

Many smart city lighting applications require information about the location of light poles, in particular about which light poles are neighbors along the street with respect to passing traffic. This paper addresses the problem of deriving the topology of light poles in a smart city, relying only on the data gathered from Passive Infrared Sensors attached to the light poles. A statistical algorithm is presented and evaluated based on a data set gathered from a real deployment in a residential area.

Simulations are often used to improve the development and test time of industrial embedded systems in different domains, such as healthcare, railway, automobile and aerospace. This paper introduces a general framework capable of simulating real components simultaneously with simulated ones, in real-time, and with a low impact on the performance of the overall system. Our framework is loosely dependent on the application and the domain where the application is developed in. More importantly, it enhances interoperability and reuse, because it paves the way to reuse existing simulating tools and models and to integrate separately developed models from earlier stages in the design into a single coherent simulation.

Applications in smart environments can make use of a user positioning service for various purposes such as activity recognition, context awareness and indoor navigation. We propose a novel solution to the user positioning problem based on inplane detection, which employs infrared light emitters and sensors placed horizontally on fixed positions along the circumference. The presented solution outputs all convex areas that are likely to contain the cross section of a user. The performance is evaluated in simulations of various indoor environments and for various numbers of users present using centroid offset, precision and ratio of equivalent diameters metrics. The simulation results show that the proposed solution determines the individual positions of multiple users in a room with very high performance.

In this paper we consider various flavors of the stack resource policy (SRP) for arbitrating access to shared resources in a hierarchical scheduling framework (HSF) upon a uni-processor. We propose algorithms for exploring and selecting the (local) resource ceilings within components, such that it results in an optimal composition of resource-sharing components in an HSF. Existing methods are non-optimal, because (i) they optimize just the length of global non-preemptive execution of tasks and (ii) they do not detect whether or not resources are shared globally (i.e., between tasks of different components). Lifting these limitations leads to an exponential growth of the design space. This paper contributes a fast three-step methodology which lifts these limitations, i.e., we apply the SRP at each level of the HSF to just the resources being shared. Our algorithm selects those component interfaces (i.e., by fixing the local resource ceilings of each component) that minimize the system load.

We present a solution for service discovery of resource constrained devices based on mDNS/DNS-SD. We extend the mDNS/DNS-SD service discovery protocol with support for proxy servers. Proxy servers temporarily store information about services offered on resource constrained devices and respond on their behalf while they are not available. We analyze two protocols for the delegation mechanism between a service provider and a proxy server: an active proxy protocol, as used in the mDNS/DNS-SD implementation by Apple, and a new, passive proxy protocol. We implement and simulate both approaches. Based on the delay and energy usage, we show that the second approach converges faster, thus saving more energy by allowing the resource constrained device to be turned off earlier.

Fixed-priority scheduling with deferred preemption(FPDS) and fixed-priority scheduling with preemption thresholds(FPTS) have been proposed in the literature as viable alternatives to fixed-priority preemptive scheduling (FPPS), that reduce memory requirements, reduce the cost of arbitrary preemptions, and may improve the feasibility of a task set even when preemption overheads are neglected. This paper aims at advancing the relative strength of limited preemptive schedulers by combining FPDS and FPTS. In particular, we present a refinement of FPDS with preemption thresholds for both jobs and sub-jobs, termed FPGS. We provide an exact schedulability analysis for FPGS, and show how to maximize the feasibility of a set of sporadic tasks under FPGS for given priorities, computation times, periods, and deadlines of tasks. We evaluate the effectiveness of FPGS by comparing the feasibility of task sets under FPGS with other fixed-priority scheduling algorithms by means of a simulation. Our experiments show that FPGS allows an increase of the number of task sets that are schedulable under fixed-priority scheduling.

This paper addresses the problem of scheduling periodic parallel tasks on a multi-resource platform, where tasks have real-time constraints. The goal is to exploit the inherent parallelism of a platform comprised of multiple heterogeneous resources. A resource model is proposed, which abstracts the key properties of any heterogeneous resource from a scheduling perspective. A new scheduling algorithm called PSRP is presented, which refines MSRP. The schedulability analysis for PSRP is presented. The benefits of PSRP are demonstrated by means of an example application showing that PSRP indeed exploits the available concurrency in heterogeneous real-time systems.

Many embedded systems have complex timing constraints and, at the same time, have flexibility requirements which prohibit offline planning of the entire system. To support a mixture of time-triggered and event-triggered tasks, some industrial systems deploy a real-time operating system (RTOS) with a table-driven dispatcher complemented with a preemptive scheduler to allocate free time slots to event-driven tasks. Rather than allocating dedicated time-slots to time-triggered tasks, we propose to dynamically re-allocate time-slots of time-triggered tasks within a pre-computed time range to maximize the available processing capacity for event-triggered tasks. Although the concept - called slotshifting - is not new, we are unaware of a commercial RTOS with such support. After identifying the mechanisms for an RTOS implementation of slotshifting, we discuss the run-time overheads for admitting aperiodic requests into the system1.

Hierarchical scheduling frameworks (HSFs) provide means for composing complex real-time systems from well-defined, independently analyzed components. To support resource sharing in two-level HSFs, three synchronization protocols based on the stack resource policy (SRP) have recently been presented for single-processor execution platforms, i.e., HSRP, SIRAP, and BROE. This paper presents a transparent implementation of these three protocols side-by-side in an HSF-enabled real-time operating system. Transparent synchronization interfaces make it possible to select a protocol during integration time based on its relative strengths. A timing interface describes the required budget to execute a component on a shared platform and an accessor's maximum critical-section execution time to global shared resources. These resources are arbitrated based on the available budget of the accessing task. We enable this explicit synchronization of virtual time with global time by means of a novel virtual-timer mechanism. Moreover, we investigate system overheads caused by each synchronization protocol, so that these can be included in the system analysis. Based on the analytical and implementation overheads of each protocol, we present guidelines for the selection of a synchronization protocol during system integration. Finally, we show that unknown task-arrival times considerably complicate an efficient implementation of SIRAP's self-suspension mechanism. We briefly discuss the implementation complexity caused by these arrivals for bandwidth-preserving servers, e.g., deferrable servers and BROE.

Hierarchical scheduling frameworks (HSFs) have been extensively investigated as a paradigm for facilitating temporal isolation between components that need to be integrated on a single shared processor. In the presence of shared resources, however, temporal isolation may break when one of the accessing components executes longer than specified during global resource access. The ability to confine such temporal faults makes the HSF more dependable. As a solution we propose a stack-resource-policy (SRP)-based synchronization protocol for HSFs, named Hierarchical Synchronization protocol with Temporal Protection (HSTP). When a component exceeds its specified critical-section length, HSTP enforces a component to self-donate its own budget to accelerate the resource release. In addition, a component that blocks on a locked resource may donate budget. The schedulability of those components that are independent of the locked resource is unaffected. HSTP efficiently limits the propagation of temporal faults to resource-sharing components by disabling local preemptions in a component during resource access. We finally show that HSTP is SRP-compliant and applies to existing synchronization protocols for HSFs.

Optimizing performance of wireless sensor networks leads to trade-offs between local computation and communication. With the usage of on-node processing, the lifetime of the sensor nodes can be extended as raw data does not need to be sent out and logged by an external device. In this paper we present our approach for on-node processing of ECG signals to signal abnormal heart rate conditions. We develop an algorithm that is significantly simpler than traditional approaches but has similar quality and that can run on sensors with very limited resources. We give results of our approach when applied to reference sequences. We also estimate the amount of information that gets transmitted over the wireless link in case of applying the on-node processing algorithm and compare it with the remote logging case. We propose fusing movement information with ECG data to provide a more accurate assessment of the patients current health.

Pervasive computing environments consist of many independent collaborating electronic devices, including sensors and actuators. Ad-Hoc extendibility of such systems is desirable but the current network technologies use the concept of a central coordinator device in the network or define application profiles which are not easy to extend and maintain. The distributed architecture proposed in this paper allows these devices to organize themselves automatically to execute some pervasive system application without the intervention of a central controlling device. The knowledge that defines interactions between these devices is derived from an ontological model of a particular domain. This knowledge is distributed over the devices such that every device only has information about its own interactions and operations. A simple demonstration of this architecture is presented.

Hierarchical scheduling frameworks (HSFs) provide means for composing complex real-time systems from well-defined, independently analyzed subsystems. To support resource sharing within two-level HSFs, three synchronization protocols based on the stack resource policy (SRP) have recently been presented, i.e. HSRP, SIRAP and BROE. This paper describes the first implementation presenting these three SRP-based synchronization protocols side-by-side in a HSF-enabled real-time operating system. We base our implementations on the commercially available real-time operating system μC/OS-II, extended with proprietary support for periodic tasks, idling periodic servers and two-level preemptive scheduling. Moreover, we investigate the system overhead of the synchronization primitives of each protocol. Transparent interfaces allow a protocol to be selected during integration time based on its relative strengths.

In this paper, we consider multimedia Quality-of-Service (QoS) in resource constrained embedded systems, where scalable applications are structured as directed acyclic graphs of tasks, which communicate via shared buffers. Scalable multimedia applications allow to trade quality for resource usage during run-time. We present two QoS problems: (i) temporal dependencies between subchains of tasks due to a common predecessor, and (ii) mode change latency in applications. These problems are addressed through advanced memory management techniques. For the first problem, it is shown how additional access to the buffer, in particular the support for dropping selected frames, allows to guarantee the Quality of Service of the application during overload conditions, preventing congestion in one buffer to propagate across the whole application. For the latter problem, the approach of in-buffer scaling is applied to reduce the mode change latency in scalable multimedia processing applications, which can adapt their memory requirements during runtime according to a set of predefined modes. The latter approach is validated with simulation results.

Fixed-priority preemption-threshold scheduling (FPTS) has been proposed as a generalization of fixed-priority preemptive scheduling (FPPS) and fixed-priority non-preemptive scheduling (FPNS) with the aim to improve schedulability and reduce run-time overheads. In this paper, we show that the existing worst-case response time (WCRT) analysis for FPTS is pessimistic and present an exact WCRT analysis. Moreover, we refine the task model for FPTS, making FPTS also a generalization of fixed-priority scheduling with deferred preemption (FPDS). Finally, we present exact analysis for FPTS for this refined task model and an example showing that FPTS can improve on FPPS and FPDS.

Hard real-time embedded systems need to guarantee that tasks always meet their deadlines. Exact schedulability tests can guarantee this for fixed-priority, preemptively scheduled systems even under the tightest resource constraints. However, these tests are pseudo-polynomial in complexity. This can become a limiting factor in open systems where it might be necessary to have run-time admission tests. A linear-time sufficient test has therefore been developed to estimate response-time upper bounds. In line with utilization-based sufficient tests, we propose to improve this test for task sets with harmonically related task periods. Moreover, we make it possible to reuse this test in the context of hierarchically scheduled (partitioned) resources. In such systems several applications are given a virtual share (budget) of the processor. By modeling the unavailability of processor resources to an application as two fictive tasks, we can also use a budget's period to improve response-time bounds1.

Smart spaces typically consist of collaborating heterogeneous nodes with various resource capacities, e.g. processing, memory, storage, energy capabilities. Low capacity nodes can operate using very simple protocols, allowing them to provide and consume only simple services, as opposed to devices with higher capacity, which are not limited by such constraints. Providing seamless connection and collaboration between low and high capacity nodes, i.e. interoperability, remains a challenge. This paper presents an approach for interoperability among nodes of a smart lighting system via a gateway node considering nodes of two platforms: low capacity wireless light sensors and actuators on the one hand and high capacity Smart-M3 nodes on the other hand. The gateway node is able to communicate over heterogeneous networks using different communication protocols, transferring light model information between the smart space nodes.

Proposed safety applications for vehicle-to-vehicle (V2V) communication rely mostly on periodic broadcasting. In this work we analyze the performance and fairness aspects of such an one-hop periodic broadcast communication. We show that communication reliability is greatly dependent on the random relative phasing of the communicating vehicles and on the impact of hidden nodes. For a random initial phasing some vehicles suffer from consecutive packet losses thereby becoming invisible to neighboring vehicles for a long time, whereas some other vehicles have no packet loss at all. We propose a simple and effective approach to provide fair transmission opportunities and show the improvements through simulations.

The overall Quality of Service (QoS) delivered by a system depends on the resources available to its constituting components. Achieving predictable QoS behaviour therefore requires a resource-aware component framework. Moreover, for applications that exhibit highly fluctuating loads and that have to compete for resources at runtime, the framework must also allow dynamic reconfiguration. The goal of this paper is to explore some basic principles and architectural choices for building such a resource-aware component framework that allow predictable composition of a system from distributed components. Major features of the envisioned framework are: wrapping components into networked services, automated extension of those services with resource management, and runtime third-party composition of the networked services.

This paper addresses the consistency and scalability behavior of a soft-state signaling protocol. Soft-state is state that has a predefined validity period. A soft-state protocol is a signaling approach in which soft-states are periodically refreshed by the receipt of a message indicating a new validity period and possibly a new value. Unrefreshed state eventually expires and recovers as soon as a subsequent refresh message is received. This protocol is widely used in distributed systems where components need to keep track of the state of other components. Within such a system, the state consistency is affected by many parameters, some given by the environment while others are tunable. The environment parameters are the loss probability and latency of the channel between the endpoints, and the change rate of the source state. The tunable parameters are the refresh period and timeout period. In this study, we dissect the overall system inconsistency into false-positive and false-negative cases, address the tradeoff between the two, and analyze their sensitivity towards parameter changes. In the end, we identify the necessary measures to optimize each of them. Our results show that false-positive ratio can be optimized by using a state cancellation mechanism, whilst the false-negative ratio can be optimized by specifying the timeout period as a function of the other parameters. Moreover, we study the systempsilas scalability behavior by observing the growth of messages overhead that is needed to keep inconsistency ratio constant as the channelpsilas loss probability increases.

In this paper we present a complete approach to programming sensor networks. The main contribution concerns the separation of three abstraction levels, viz., application level, network level and node level, leaving more room for standardization than with current practices. In addition we propose to program the network from an overall perspective rather than programming individual nodes. The proposed model is event- based, corresponding closely to the nature of wireless sensors and admits content-based addressing of nodes and groups of nodes. The paper describes how the three abstraction levels come together and gives examples of the approach at all three levels.

This paper presents a secure resource control solution for service oriented applications. Through this, resources on a shared device can be protected from malicious abuse and become controllable for special QoS provisioning. Services are grouped into virtual communities and service access can only be done within the scope of a virtual community. Using soft-state management, services and their underlying resources are monitored by a novel device management service which runs on each device and can activate or deactivate hosted services.

This paper presents the design and implementation of RELTEQ, a timed event management algorithm based on relative event times, supporting long event interarrival time, long lifetime of the event queue, no drift and low overhead. It is targeted at embedded operating systems. RELTEQ has been conceived to replace and improve the existing timed event management approach in ¿C/OS II, a real-time operating system used by one of our industrial partners. Experimental results confirm a lower overhead of the proposed method in terms of processor requirements compared to the existing approach.

Fixed-priority scheduling with deferred preemption (FPDS) has been proposed in the literature as a viable alternative to fixed-priority pre-emptive scheduling (FPPS), that obviates the need for non-trivial resource access protocols and reduces the cost of arbitrary preemptions. This paper shows that existing worst-case response time analysis of hard real-time tasks under FPDS, arbitrary phasing and relative deadlines at most equal to periods is pessimistic and/or optimistic. The same problem also arises for fixed-priority non-pre-emptive scheduling (FPNS), being a special case of FPDS. This paper provides a revised analysis, resolving the problems with the existing approaches. The analysis is based on known concepts of critical instant and busy period for FPPS. To accommodate for our scheduling model for FPDS, we need to slightly modify existing definitions of these concepts. The analysis assumes a continuous scheduling model, which is based on a partitioning of the timeline in a set of non-empty, right semi-open intervals. It is shown that the critical instant, longest busy period, and worst-case response time for a task are suprema rather than maxima for all tasks, except for the lowest priority task. Hence, that instant, period, and response time cannot be assumed for any task, except for the lowest priority task. Moreover, it is shown that the analysis is not uniform for all tasks, i.e. the analysis for the lowest priority task differs from the analysis of the other tasks. These anomalies for the lowest priority task are an immediate consequence of the fact that only the lowest priority task cannot be blocked. To build on earlier work, the worst-case response time analysis for FPDS is expressed in terms of known worst-case analysis results for FPPS. The paper includes pessimistic variants of the analysis, which are uniform for all tasks, illustrates the revised analysis for an advanced model for FPDS, where tasks are structured as flow graphs of subjobs rather than sequences, and shows that our analysis is sustainable.

In a ubiquitous computing environment, devices host services that are accessed by anonymous users. This causes threats of resource abuse through malicious attacks or resource scarcity through unintentional excessive service invocations. In this paper, the secure resource control for service sharing is presented which depends on two basic functionalities: access control and soft-state management. Services are grouped into virtual communities for secure access. Service cooperation through external orchestration can only be done within a virtual community. Services can be activated/deactivated by a device management service running on their host devices. Real-time resource utilization of services for virtual community applications is monitored. Therefore, resources on a shared device can be protected from malicious use and become controllable for special quality of service provisioning.

The current service- and device discovery protocols are not platform- and network independent Therefore, proxy servers will be needed to extend the range of IP-based discovery protocols to non-IP domains. We developed an architecture of a proxy that enables UPnP devices and services to be discovered on the Bluetooth network and vice versa, and allows Bluetooth devices and UPnP control points to access and utilize services located on devices in the other network. We managed to keep all functionality needed for effective proxying running on a single device, e.g. the mobile phone or the Residential Gateway. © 2007 IEEE.

Fixed-priority scheduling with deferred preemption (FPDS) has been proposed in the literature as a viable alternative to fixed-priority preemptive scheduling (FPPS), that both reduces the cost of arbitrary preemptions and removes the need for non-trivial resource access protocols. This paper shows that existing worst-case response time analysis of hard real-time tasks under FPDS, arbitrary phasing and relative deadlines at most equal to periods is both pessimistic and optimistic. This paper provides a revised analysis, resolving the problems with the existing approaches. The analysis assumes a continuous scheduling model. It is shown that the critical instant, longest busy period, and worst-case response time for a task are suprema rather than maxima for all tasks, except for the lowest priority task. Moreover, it is shown that the analysis is not uniform for all tasks, i.e. the analysis for the lowest priority task differs from the analysis of the other tasks, because only the lowest priority task cannot be blocked. To build on earlier work, the worst-case response time analysis for FPDS is expressed in terms of known worst-case analysis results for FPPS. The paper includes pessimistic variants of the analysis, which are uniform for all tasks.

Service Oriented Architecture (SOA) is emerging as an enabling technology for sharing distributed heterogeneous resources on the network. Consequently, securing services is an increasing concern. Research issues include privacy protection for service providers, transparent access control for service consumers, secure service discovery and composition. In this paper, we present an access control approach which uses virtual communities to secure service discovery and access (VICSDA). Services grouped in virtual communities can only be discovered and accessed by authenticated community members. Meanwhile, services are autonomous to define their local access control policy. Moreover, behavior of these autonomous services is monitored in order to guarantee a better QoS provision. Using a virtual community overlay network on top of a SOA infrastructure, VICSDA can provide authentication, message confidentiality and integrity to secure service discovery and access. Better application performance can be achieved through VICSDA. We integrated VICSDA with a 3D video streaming application. This example provides us with some initial evidence that VICSDA is a viable solution to our target problems.

Controller Area Network (CAN) is used extensively in automotive applications, with in excess of 400 million CAN enabled microcontrollers manufactured each year. In 1994 schedulability analysis was developed for CAN, showing how worst-case response times of CAN messages could be calculated and hence guarantees provided that message response times would not exceed their deadlines. This seminal research has been cited in over 200 subsequent papers and transferred to industry in the form of commercial CAN schedulability analysis tools. These tools have been used by a large number of major automotive manufacturers in the design of in-vehicle networks for a wide range of cars, millions of which have been manufactured during the last decade. This paper shows that the original schedulability analysis given for CAN messages is flawed. It may provide guarantees for messages that will in fact miss their deadlines in the worst-case. This paper provides revised analysis resolving the problems with the original approach. Further, it highlights that the priority assignment policy, previously claimed to be optimal for CAN, is not in fact optimal and cites a method of obtaining an optimal priority ordering that is applicable to CAN. The paper discusses the possible impact on commercial CAN systems designed and developed using flawed schedulability analysis and makes recommendations for the revision of CAN schedulability analysis tools.

In this article we provide a model for the dynamic behavior of media processing chains of tasks communicating via bounded buffers. The aim is to find the overall behavior of a chain from which performance parameters (such as start time and response time of individual tasks, chain end-to-end response time, number of context switches and resource utilization) follow. This behavior is characterized in terms of the elementary actions of the tasks that make up the chain. From this we derive corollaries that give design guidelines, supporting the goal of improving chain end-to-end response time and the optimization of resources, which is achieved by minimizing context-switching overhead and buffer sizes

Vector DSPs, or SIMD DSPs, have received considerable attention recently, since they are considered to be a viable alternative for dedicated hardware in signal processing for multimedia and wireless communication. It is possible to construct dedicated hardware for IIR filters with a linear speedup, but because of their recursive nature these filters are considered difficult to map efficiently on a vector DSP. The IIR programs for vector DSPs presented so far have their speedup bounded by the order of the filter. In this paper we present a program that has a linear speed up, in the sense that doubling the vector size doubles the throughput. The program is a vectorization of the incremental block-state architecture. The speedup of this program is not bounded by the order of the filter, and even works for low order filters. Besides strided memory access, no special processor features are required by our program. As a proof of concept we implemented it on the Philips EVP processor.

The paper addresses the issue of controlling streaming of scalable video over wireless links to resource-constrained devices (terminals). A controller on the terminal maximizes user perceived quality taking into account available computing resources and condition of the network. The controller determines the number of layers to be processed using a strategy calculated for the given layers configuration and network conditions. We present a method to decrease the number of pre-calculated strategies for the controller by exploring the dependency between layers configuration and network conditions.

The ever-increasing complexity of generic multimedia-content-analysis-based (MCA) solutions, their processing power demanding nature and the need to prototype and assess solutions in a fast and cost-saving manner motivated the development of the Cassandra framework. The combination of state-of-the-art network and grid-computing solutions and recently standardized interfaces facilitated the set-up of this framework, forming the basis for multiple cross-domain and cross-organizational collaborations. It enables distributed computing scenario simulations for e.g. distributed content analysis (DCA) across consumer electronics (CE) in-home networks, but also the rapid development and assessment of complex multi-MCA-algorithm-based applications and system solutions. Furthermore, the framework's modular nature-logical MCA units are wrapped into so-called service units (SU)-ease the split between system-architecture- and algorithmic-related work and additionally facilitate reusability, extensibility and upgrade ability of those SUs

This paper describes a new design of the remote device management (RDM) framework, which is suited to personal devices. Once this Remote Personal Device Management (RPDM) framework is enabled, parties like manufacturing companies, service providers, and consumers can immediately benefit from gaining access to critical information about the operational status, maintenance functionalities and potential security issues of these devices.We give an overview and comparison of existing remote management systems and rate them on several aspects. Our new system focuses more on the special requirements of personal computing devices such as security and privacy, and complies with the newly released SyncML DM specifications. We also demonstrate the implementation to prove the feasibility of our framework. Furthermore, it is one of the very first open implementations based on the SyncML DM specifications, which, in our opinion, will help researchers and developers to better understand and work more easily with this standard in the future.

Streaming video over wireless networks can be complicated by a highly varying link capacity. We present an approach that allows close-to-optimal utilization of the link bandwidth. We use a property of the medium access control (MAC) of the 802.11 standard to do instant detection of the bandwidth fluctuations by observing the transmission rate from the sending buffer. The specifics of a general MPEG stream allow classifying video-frames by their importance for the user-perceived quality. We build a scheduling mechanism that favors transmission of more important frames at the expense of the less important ones. We validate our approach by means of test-bed experiments and demonstrate a significant improvement of the end video quality.

An important research topic in the field of image processing is stereo vision. Stereo vision is the process of constructing a 3D model of a scene through processing two 2D images of this scene. The main problem is the construction of a disparity map. This is a map that describes which points in the two images correspond to the same point in the 3D scene. This paper describes the design of a parallel algorithm for constructing a disparity map. The algorithm is based on correlation and uses the epipolar constraint. A performance analysis of the implemented algorithm is given from which it is concluded that the designed algorithm has good speedup and efficiency and that the measured times are promising.

Abstract Predicate transformers that map the postcondition and all intermediate conditions of a command to a precondition are introduced. They can be used to specify certain progress properties of sequential programs.