Linux as real-time system

The Open Source Automation Development Lab ran experiments on the latency of various systems running mainline Linux with real-time Kernel. They generated billions of statistical samples over more than one year of simulation time. One of the most interesting parameters measured is the total preemption latency (interrupt processing plus wakeup of a user space process). Note that we are talking about a pure Linux system here, not a real-time system that runs Linux as a task in parallel with dedicated real-time threads.

x86 VIA C7 @1000 MHz running Fedora 10 with Kernel 2.6.33.14-rt31, maximum latency 112 µs in a total of 87.8 billion cycles

The latencies of various Linux systems had shown to have small variation and not a single outlier had been detected in the whole dataset. This implies that Linux systems provide a generic feature for determinism and thus could be trusted for hard real-time tasks.

However, before you are going to wire a critical nuclear power plant controller to your Linux box, consider this:
Although the tests had been very extensive, there is still a chance that a certain condition exists where the delay exceeds the expected duration. In the tests this condition just never might have occured. I expect that the guys at OSADL have done their experiments quite accurately, so that the probability for such a case might be in the order of micro-percent. However, if you instrument a really critical system, the costs for the remaining risk are still striking.

So what do to next? Use Linux for a real-time system or not?

Use it, but don’t fully depend on it. Monitor the results. If your system has a safe state that would be entered in case a deadline is – other than expected from the measurement results – missed, Linux can be quite an attractive choice. Anyway, in order to create a dependable system, you need dependable drivers for interacting with the process environment.

For the timing issues of the operating system, the experiments and results from OSADL are extremely valuable to engineers building real-time system with Linux.

• Long-term data of the determinism of mainline Linux real-time @ Open Source Automation Development Lab

Reading thousand sensors in the blink of an eye

A cyber-physical system is formed by a network of interacting sensors and actuators. With the availability of small inexpensive sensor elements, such a network may contain thousands of interacting sensors. This makes such systems a little bit similar to biological systems. For example, the human body has 3 billion touch sensor cells. Still a notable difference though.

However, even for a few thousand sensors, conventional communication methods come into trouble. With a typical network, it takes too long to transmit such a large number of sensor measurements.

In the paper “A Scalable and Efficient Approach for Obtaining Measurements in CAN-based Control Systems” scientists from Portugal and Austria present a solution to this problem by polling many sensors at once while actually transmitting only one representative measurement.

Example for a priority-based medium access control; "0" is dominant over "1"

The idea is based on so-called priority-based medium access control protocols:

• the message consists of a number of bits, each bit being 0 or 1 (any message can be encoded that way)
• when the bits are sent via transmission medium, one of the states can overwrite the other (for example if 1 overrides 0, then a synchronously transmitted 1 and 0 result in a 1)
• all sensors start their transmission at the same time, for example triggered by a query message
• a transmitting sensor monitors its own transmission; if a bit gets overwritten it immediately stops transmission. This way it is possible to get the largest value (or by inverting the messages, the lowest value) of a number of sensors with a single query. If there are thousands of sensors, the protocol definitely pays off.

A few sensor measurements (green) with high information content are sufficient to interpolate the overall dataset

Andersson, Pereira, Elmenreich, Tovar, Pacheco and Cruz employ this method to get a map of sensor readings with just a few messages. The priority-based protocol is here used to select the sensor messages with high information content. This approach greatly reduces the time for obtaining sensory information, which makes cyber-physical systems ready for use in fast control systems.

The full paper is available as a technical report. It was published in the highly respected IEEE Transactions on Industrial Informatics:

• B. Andersson, N. Pereira, W. Elmenreich, E. Tovar, F. Pacheco, and N. Cruz. A scalable and efficient approach for obtaining measurements in CAN-based control
  systems. IEEE Transactions on Industrial Informatics, 4(2):80–91, May 2008.

Efficiently detecting a frequency using a Goertzel filter

The Goertzel algorithm detects a specific, predetermined frequency in a signal. This can be used to analyze a sound source for the presence of a particular tone. The algorithm is simpler than an FFT and therefore a candidate for small embedded systems.

With the following C code you can analyze an array of samples for a given frequency:

double goertzelFilter(int samples[], double freq, int N) {
    double s_prev = 0.0;
    double s_prev2 = 0.0;    
    double coeff,normalizedfreq,power,s;
    int i;
    normalizedfreq = freq / SAMPLEFREQUENCY;
    coeff = 2*cos(2*M_PI*normalizedfreq);
    for (i=0; i<N; i++) {
        s = samples[i] + coeff * s_prev - s_prev2;
        s_prev2 = s_prev;
        s_prev = s;
    }
    power = s_prev2*s_prev2+s_prev*s_prev-coeff*s_prev*s_prev2;
    return power;
}

However, there are two issues with that approach: first, the samples need to be stored, which requires a lot of RAM memory that might not be easily available on a microcontroller. Second, the detection of a signal might be delayed until the sample buffer is full and gets analyzed.
As an improvement, we can formulate the filter also as a real time algorithm that analyzes one sample at a time:

double RTgoertzelFilter(int sample, double freq) {
    static double s_prev = 0.0;
    static double s_prev2 = 0.0;  
    static double totalpower = 0.0;  
    static int N = 0;
    double coeff,normalizedfreq.power, s;
    normalizedfreq = freq / SAMPLEFREQUENCY;
    coeff = 2*cos(2*M_PI*normalizedfreq);
    s = sample + coeff * s_prev - s_prev2;
    s_prev2 = s_prev;
    s_prev = s;
    N++;
    power = s_prev2*s_prev2+s_prev*s_prev-coeff*s_prev*s_prev2;
    totalpower += sample*sample;
    if (totalpower == 0) totalpower=1;
    return power / totalpower / N;
}

Note that the initialization of the static variables takes place only at the first time when the function is called. The return value has been normalized using the total power and number of samples.
This filter delivers a result after each sample without storing the samples, but it considers the whole history of the signal. If you want to detect the sudden presence of a tone, it is better to limit the history of the filter. This can be done using the tandemRTgoertzelFilter:

double tandemRTgoertzelFilter(int sample, double freq) {
    static double s_prev[2] = {0.0,0.0};
    static double s_prev2[2] = {0.0,0.0};  
    static double totalpower[2] = {0.0,0.0};  
    static int N=0;       
    double coeff,normalizedfreq,power,s;
    int active;
    static int n[2] = {0,0};
    normalizedfreq = freq / SAMPLEFREQUENCY;
    coeff = 2*cos(2*M_PI*normalizedfreq);
    s = sample + coeff * s_prev[0] - s_prev2[0];
    s_prev2[0] = s_prev[0];
    s_prev[0] = s;
    n[0]++;
    s = sample + coeff * s_prev[1] - s_prev2[1];
    s_prev2[1] = s_prev[1];
    s_prev[1] = s;    
    n[1]++;
    N++;
    active = (N / RESETSAMPLES) & 0x01;
    if  (n[1-active] >= RESETSAMPLES) { // reset inactive
        s_prev[1-active] = 0.0;
        s_prev2[1-active] = 0.0;  
        totalpower[1-active] = 0.0;  
        n[1-active]=0;    
    }
    totalpower[0] += sample*sample;
    totalpower[1] += sample*sample;
    power = s_prev2[active]*s_prev2[active]+s_prev[active]
       * s_prev[active]-coeff*s_prev[active]*s_prev2[active];
    return power / (totalpower[active]+1e-7) / n[active];
}

The tandem filter is the combination of two real-time filters, which are reset alternatively every RESETSAMPLES. Except for the first RESETSAMPLES, the active filter always has a history between RESETSAMPLES and 2 * RESETSAMPLES samples. Meanwhile the inactive filter is building up its history again. This is necessary because the algorithm needs some time to reach a steady state. In my test runs, I successfully used a value of 200 samples for RESETSAMPLES in order to detect a 440 Hz signal in a 44kHz audio sample. Even for an 8 bit Microcontroller without an FPU, the tandem implementation is fast enough. For high performance computation, I further recommend to translate the algorithm to fixed point arithmetic.

An Orchestra of Bits and Bytes: Time-Triggered Advanced Driver Assistance Systems

Multi-sensor object tracking is an important feature for advanced driver assistance systems in future automobiles. Most state-of-the-art systems cannot guarantee deterministic processing of the sensor values due to unsynchronized sensing and processing units. To overcome this shortcoming we propose a paradigm shift towards a time-triggered system architecture providing a deterministic bus system, synchronized nodes, and a global time-base. In a time-triggered system, all actions like sensing, actuating and transmitting data are scheduled according to a predefined schedule – similar to the coordinated playing of an orchestra.
Simulation results have previously indicated that although non-time-triggered approaches perform well in scenarios with low process noise, the time-triggered model becomes advantageous in potentially dangerous scenarios with high dynamics. In order to validate the results of the simulation for real life scenarios, we analyzed test drives derived from a testbed featuring a Volkswagen Touran being equipped with a laser scanner, a stereo camera system, a FlexRay communication system, an object tracking subsystem and a differential GPS system as reference.

• Wilfried Elmenreich, Moritz Koplin, A Time-Triggered Object Tracking Subsystem for Advanced Driver Assistance Systems, in e & i Journal, Springer, Wien, 12(6):203-208, 2011.

e-puck – toy or research platform?

An e-puck is a small differential-wheeled robot. The openness of the design makes the e-puck especially interesting for academic use. The hardware and software is under an open source license which allows for modifictaion and redistribution of the design. Besides being cute, e-pucks offer a lot of sensory functions and allow us to do hands-on experiments on collaborative robot algorithms. So, although its cute appearence, the robot is quite capable and probably the first choice when you want to do cooperative/swarm robotics and you don’t want to build your own hardware.

This video shows a first test we did on the e-puck. The human hand also gives an impression of the small size of the e-puck.

In the second video, we show the implementation of a maze solver. To solve the task, different sensors of the e-puck (IR-Light Sensor, Distance Sensor, …) have been used. The robot follows the wall to the right until it finds its goal (a dark sector in the maze) – then the LEDs are blinking and it emits a sound. As you can see in the video, the simulation predicts very similar results.

However, you can also see that the e-puck is no sprinter. So if you think of applications like robot soccer, this is the wrong hardware (unless you like slow-motion view all the time).

Still, the openness of the hardware and the combination of many different sensors (including a simple camera) make the e-puck an interesting research plattform.

Testing embedded user interfaces with paper prototyping

Paper prototyping is a usability test where users access an interface by interacting with a paper version of the interface that is manipulated by a second person emulating the computer. The second person only manipulates the paper interface, but is not allowed to explain or give hints how to use the interface.

Paper prototyping is of special interest if you design the user interface for an embedded device mainly for the following reasons:

• developing software for an embedded system is more cumbersome than for a desktop system, therefore the paper version can safe time and can be easier adapted than for most embedded systems
• you might want to experiment with different layout of hardware interfaces, for example knobs and buttons. These can be emulated using a paper model until the decision for the final hardware design has to be done.
• it is fun! The task involves crayons, scissors, and glue and will most likely contribute well to your stress relief during daytime work!

In the following video, colleagues from University of Klagenfurt test an interface for their Geobashing application using paper prototyping:

If you want to learn more about the Geobashing application, find more information on the GeoBashing website.

A simple sensor fusion algorithm

Let’s assume, you have a set of sensors measuring the same property. By using competitive sensor fusion (see previous post for an explanation) you expect to increase the accuracy and reliablilty of the result.
In the paper [1] you can find a simple algorithm for doing that.
First, each sensor observation is modeled to have a measurement value, a measurement accuracy and a measurement instant. The instant is necessary to verify that your sensor measurements are sufficiently synchronous, otherwise you need a model to predict future observations in order to synchronize measurements.

The measurement accuracy can be fixed for each sensor or have a dynamic value based on measurement range or run-time validation. The accuracy should be expressed as the expected variance of the measurement.

Assuming that the measurement errors are uncorrelated (or, in practise, sufficiently diverse), the optimal fusion weights are given by the reciproke variance values:

The variance of the result can also be predicted by a similar formula:

Thus, even if you add a very bad sensor to an already good one, the weighted fusion can still improve the variance of the result. For example in [2], we combined distance sensors using infrared measurement with ultrasonic-based sensors in order to get a more robust result. This way, an expensive sensor could be replaced by a set of cheap ones.

1. W. Elmenreich. Fusion of continuous-valued sensor measurements using confidence-weighted averaging. Journal of Vibration and Control, 13(9-10):1303–1312, 2007. (doi:10.1177/1077546307077457)
2. W. Elmenreich. Sensor Fusion in Time-Triggered Systems. PhD thesis, Institut für Technische Informatik, 2002.