Category Archives: Real-time Systems

Reducing error in time synchronization for multisensor arrangements in aerial applications, with interesting formulae for the clock drift of IMUs

June 19, 2017 12:18 ,

J. Li, L. Jia and G. Liu, “Multisensor Time Synchronization Error Modeling and Compensation Method for Distributed POS,” in IEEE Transactions on Instrumentation and Measurement, vol. 65, no. 11, pp. 2637-2645, Nov. 2016. DOI: 10.1109/TIM.2016.2598020.

An airborne distributed position and orientation system (POS) is high-precision measurement equipment that can accurately provide multinode time-spatial reference for novel remote sensing system as multitask imaging sensors and array antenna synthetic aperture radar. However, it is difficult for multisensor to precisely acquire information at the same moment and result in data fusion error. Thus, the measurement precision is severely degraded. To solve the problem, a multisensor time synchronization error modeling and compensation method is proposed. Based on the component and operation principles of distributed POS, the time synchronization mechanism is analyzed. Multisensor time synchronization error models that include time delay error, random error, and time-varying error are established. A time synchronization error compensation method of the distributed POS is proposed. The experiment results show that the proposed method can accurately calibrate and compensate for the time synchronization error, and improve the measurement precision of the distributed POS. It verified the validity of the proposed method.

Posted in: Real-Time Systems , Tagged:

Estimating the execution time of programs before compiling

June 19, 2017 10:45 ,

Peter Altenbernd, Jan Gustafsson, Björn Lisper, Friedhelm Stappert, Early execution time-estimation through automatically generated timing models,, Real-Time Systems, November 2016, Volume 52, Issue 6, pp 731–760, DOI: 10.1007/s11241-016-9250-7.

Traditional timing analysis, such as worst-case execution time analysis, is normally applied only in the late stages of embedded system software development, when the hardware is available and the code is compiled and linked. However, preliminary timing estimates are often needed in early stages of system development as an essential prerequisite for the configuration of the hardware setup and dimensioning of the system. During this phase the hardware is often not available, and the code might not be ready to link. This article describes an approach to predict the execution time of software through an early, source-level timing analysis. A timing model for source code is automatically derived from a given combination of hardware architecture and compiler. The model is identified from measured execution times for a set of synthetic training programs, compiled for the hardware platform in question. It can be used to estimate the execution time for code running on the platform: the estimation is then done directly from the source code, without compiling and running it. Our experiments show that, using this model, we can predict the execution times of the final, compiled code surprisingly well. For instance, we achieve an average deviation of 8 % for a set of benchmark programs for the ARM7 architecture.

Posted in: Real-Time Systems , Tagged:

Calculating (experimental) probability distributions of the execution of sequential software

April 29, 2016 10:44 ,

Laurent David, Isabelle Puaut, Static Determination of Probabilistic Execution Times, Proceedings of the 12th 16th Euromicro Conference on Real-Time Systems (ECRTS’04). Link.

Most previous research done in probabilistic schedulability analysis assumes a known distribution of execution times for each task of a real-time application. This is however not trivial to determine it with a high level of confidence. Methods based on measurements are often biased since not in general exhaustive on all the possible execution paths, whereas methods based on static analysis are mostly Worst-Case Execution Time – WCET – oriented. Using static analysis, this work proposes a method to obtain probabilistic distributions of execution times. It assumes that the given real time application is divided into multiple tasks, whose source code is known. Ignoring in this paper hardware considerations and based only on the source code of the tasks, the proposed technique allows designers to associate to any execution path an execution time and a probability to go through this path. A source code example is presented to illustrate the method.

Posted in: Real-Time Systems , Tagged: , ,

Pdf form of the WCET of code execution

April 29, 2016 10:26 ,

S. Edgar and A. Burns, Statistical analysis of WCET for scheduling, Real-Time Systems Symposium, 2001. (RTSS 2001). Proceedings. 22nd IEEE, 2001, pp. 215-224. DOI: 10.1109/REAL.2001.990614.

To perform a schedulability test, scheduling analysis relies on a known worst-case execution time (WCET). This value may be difficult to compute and may be overly pessimistic. This paper offers an alternative analysis based on estimating a WCET from test data to within a specific level of probabilistic confidence. A method is presented for calculating an estimate given statistical assumptions. The implications of the level of confidence on the likelihood of schedulability are also presented.

Posted in: Real-Time Systems , Tagged: ,

Improvement on the classical regression-based estimation algorithm of the relative clock frequency of two remotely connected clocks for better behaviour under outliers, and a good related works section on the estimation of clock relative frequency

December 22, 2015 17:57 ,

Oka Saputra, K.; Wei-Chung Teng; Tsung-Han Chen, Hough Transform-Based Clock Skew Measurement Over Network, in Instrumentation and Measurement, IEEE Transactions on , vol.64, no.12, pp.3209-3216, Dec. 2015, DOI: 10.1109/TIM.2015.2450293.

The accurate clock skew measurement of remote devices over network connections is crucial to device fingerprinting and other related applications. Current approaches use the lower bound of offsets between the target device and the measurer to estimate clock skew; however, the accuracy of estimation is severely affected when even a few offsets appear below the crowd of offsets. This paper adopted the Hough transform to develop a new method, which searches for the densest part of the whole distribution. This method is effective in filtering out the upper and lower outliers such that the skew values derived from the remaining offsets are stable, even when lower outliers occur, or when the measuring time is not long enough for current approaches to achieve stable results. The experimental evaluation of the proposed method has been conducted in order to compare its performance with that of linear programming algorithm (LPA) and two other approaches. During the five consecutive measurements of 1000 offsets each, skews of the proposed method varied within the range of 0.59 ppm, whereas LPA resulted in the range of 0.89 ppm. Both ranges increased to 1.34 and 63.93 ppm, respectively, when the lower bounds encountered interference from lower outliers.

Notes:

  • They assume there is no NTP running in the background; however, their results seem to come from a conventional TCP/IP network, where it is difficult not to find NTP enabled.
Posted in: Communication networks, Real-Time Systems , Tagged: ,

Scheduling of communications between several nodes for better achieving real-time constraints in a distributed control system, and also a very detailed dynamical model of a wheeled vehicle

November 12, 2015 20:08 ,

Naim Bajcinca, Wireless cars: A cyber-physical approach to vehicle dynamics control, Mechatronics, Volume 30, September 2015, Pages 261-274, ISSN 0957-4158, DOI: 10.1016/j.mechatronics.2015.04.016.

A non-conventional drive-by-wireless technology for guidance and control of a redundantly actuated electric car supported by an on-board wireless network of sensors, actuators and control units is proposed in this article. Several optimization-based distributed feedforward control schemes are developed for such powertrain infrastructures. In view of the limitations of the commercial off-the-shelf wireless communication technologies and the harshness of the in-vehicle environments, a pressing design and implementation aspect, in addition to the robustness against information loss, refers to fulfilling the hard real-time computational requirements. In this work, we address such problems by introducing several distributed event-based control schemes in conjunction with adaptive scheduling at the protocol level. Hereby we obtain a simple tuning mechanism to compromise between the outcome accuracy and computation efficiency (i.e., communication traffic intensity). Using simulative evaluations, we demonstrate the viability of the proposed algorithms and illustrate the impact of external interferences in an IEEE 802.15.4 based wireless communication solution.

Posted in: Communication networks, Task scheduling , Tagged: , ,

Survey on Model-Driven Software Engineering for real-time embedded systems and robotics

October 1, 2015 18:37 ,

Brugali, D., Model-Driven Software Engineering in Robotics: Models Are Designed to Use the Relevant Things, Thereby Reducing the Complexity and Cost in the Field of Robotics, in Robotics & Automation Magazine, IEEE , vol.22, no.3, pp.155-166, Sept. 2015, DOI: 10.1109/MRA.2015.2452201.

A model is an abstract representation of a real system or phenomenon [1]. The idea of a model is to capture important properties of reality and to eglect irrelevant details. The properties that are relevant and that can be neglected depend on the purpose of creating a model. A model can make a particular system or phenomenon easier to understand, quantify, visualize, simulate, or predict.

Posted in: Real-Time Systems, Robotic software , Tagged: , ,

A new algorithm for clock synchronization in wireless sensor networks with bounded delays, that includes interesting references to surveys

July 27, 2015 10:26 ,

Emanuele Garone, Andrea Gasparri, Francesco Lamonaca, Clock synchronization protocol for wireless sensor networks with bounded communication delays, Automatica, Volume 59, September 2015, Pages 60-72, ISSN 0005-1098, DOI: 10.1016/j.automatica.2015.06.014.

In this paper, we address the clock synchronization problem for wireless sensor networks. In particular, we consider a wireless sensor network where nodes are equipped with a local clock and communicate in order to achieve a common sense of time. The proposed approach consists of two asynchronous consensus algorithms, the first of which synchronizes the clocks frequency and the second of which synchronizes the clocks offset. This work advances the state of the art by providing robustness against bounded communication delays. A theoretical characterization of the algorithm properties is provided. Simulations and experimental results are presented to corroborate the theoretical findings and show the effectiveness of the proposed algorithm.

Posted in: Communication networks, Real-Time Systems , Tagged: , ,

The problem of monitoring events that can only be predicted stochastically, applied to mobile sensors for monitoring

July 17, 2015 12:18 ,

Jingjin Yu; Karaman, S.; Rus, D., Persistent Monitoring of Events With Stochastic Arrivals at Multiple Stations, Robotics, IEEE Transactions on , vol.31, no.3, pp.521,535, June 2015, DOI: 10.1109/TRO.2015.2409453.

This paper introduces a new mobile sensor scheduling problem involving a single robot tasked to monitor several events of interest that are occurring at different locations (stations). Of particular interest is the monitoring of transient events of a stochastic nature, with applications ranging from natural phenomena (e.g., monitoring abnormal seismic activity around a volcano using a ground robot) to urban activities (e.g., monitoring early formations of traffic congestion using an aerial robot). Motivated by examples like these, this paper focuses on problems in which the precise occurrence times of the events are unknown apriori, but statistics for their interarrival times are available. In monitoring such events, the robot seeks to: (1) maximize the number of events observed and (2) minimize the delay between two consecutive observations of events occurring at the same location. This paper considers the case when a robot is tasked with optimizing the event observations in a balanced manner, following a cyclic patrolling route. To tackle this problem, first, assuming that the cyclic ordering of stations is known, we prove the existence and uniqueness of the optimal solution and show that the solution has desirable convergence rate and robustness. Our constructive proof also yields an efficient algorithm for computing the unique optimal solution with O(n) time complexity, in which n is the number of stations, with O(log n) time complexity for incrementally adding or removing stations. Except for the algorithm, our analysis remains valid when the cyclic order is unknown. We then provide a polynomial-time approximation scheme that computes for any ε > 0 a (1 + ε)-optimal solution for this more general, NP-hard problem.

Posted in: Real-Time Systems, Robot sensors, Task scheduling , Tagged:

Soft-real time scheduling in distributed systems based on accrued utility of distributable threads, including situations of node failures

May 20, 2015 09:19 ,

Ravindran B., Anderson J. S., Jensen E. D., On Distributed Real-Time Scheduling in Networked Embedded Systems in the Presence of Crash Failures, Lecture Notes in Computer Science, vol. 4761, pp. 67-81, DOI: 10.1007/978-3-540-75664-4_8.

We consider the problem of scheduling distributable real-time threads in networkedembedded systems that operate under run-time uncertainties including those on thread execution times, thread arrivals, and node failure occurrences. We present a distributed scheduling algorithm called CUA. We show that CUA satisfies thread time constraints in the presence of crash failures, is early-deciding, has an efficient message complexity of O(f n) (where f is the number of crashes that actually occur and n is the number of nodes), and is time-optimal with a time lower bound of O(D + f d + nk) (where D is the message delay upper bound, d is the failure detection bound, and k is the maximum number of threads). In crash-free runs, the algorithm constructs schedules within O(D + nk), and yields optimal total utility if nodes are also not overloaded. The algorithm is also “best-effort” in that a high importance thread that may arrive at any time has a very high likelihood for feasible completion (in contrast to classical admission control algorithms which favor feasible completion of admitted threads over admitting new ones, irrespective of thread importance).

Posted in: Real-Time Systems , Tagged: , ,