1

Scheduling in Energy Autonomous Objects

Maryline CHETTO

In an autonomous system, in other words a system supplied during its entire lifetime by ambient energy, the issue of scheduling must be addressed in jointly taking into account the two physical constraints: time and energy. The fundamental scheduling questions can be raised as follows: is a scheduler as efficient, simple and high-performance as earliest deadline first (EDF) is appropriate? Is there, in this new context of perpetual energy autonomy, a scheduler which is optimal with acceptable implementation costs? How do we dimension the energy storage unit in such a way that no energy starvation, and therefore no deadline violation can occur at any time?

This chapter proposes to answer these questions according to the following plan:

1.1. Introduction

Electrical energy supply is a crucial issue, in particular in the design of portable systems that by nature have to be autonomous from an energy point of view. Today, this issue is mainly handled by dynamic voltage scaling (DVS) or dynamic power management (DPM) methods that aim to reduce the energy consumption of electronic circuits. Thus, the proposed solutions allow us to extend the durations separating two successive recharges of a battery without overcoming them.

However, the new generations of embedded systems, in particular those functioning in hostile or inaccessible environments, limit human intervention. They function with the help of batteries (or any other kind of energy storage unit), which are continuously recharged over time from a renewable energy source. There is no doubt that the DVS and DPM techniques prove to be very useful in autonomous systems: they lead to using lower capacity batteries, smaller solar panels, etc. But these techniques do not allow, by themselves, to ensure infinite operation, called energy-neutral. Energy-neutrality is defined here by the property of the embedded system to operate in such a way as to respect all of its timing constraints and this, by only using the energy available in the storage unit without ever lacking any.

An autonomous system is built around three components (see Figure 1.1):

Figure 1.1. Diagram of an ambient energy harvesting system

Designing such a system requires the resolution of a certain number of issues related to the harvesting, storage and the use of ambient energy [PRI 09]. It has to be provided with a durable autonomy (from one to tens of years) while maintaining an acceptable real-time performance level. In this chapter, we focus on the consumer of energy, a machine whose energy needs are variable in time. These needs are required by the real-time tasks whose processing has to be done in predefined time intervals. Therefore, the energy needs are not identical and continuous over time. They depend on the timing profile of the tasks, very generally characterized by a period and/or a deadline. An embedded system and mainly an autonomous intelligent sensor has to function during several years or even several tens of years without any possibility of intervention. This is why guaranteeing offline that it will respect its constraints is of importance. The implementation will be made difficult or even impossible by the uncertainty attached to the quantity of harvested energy. We can, therefore, see that the design of an autonomous system leads to several fundamental questions. Assuming that the energy supply is perfectly characterized (energy source profile, size of the storage battery, etc.), how do we verify and guarantee before the system becomes operational that it will have a continuous autonomy with an always acceptable performance level? This, therefore, means, first of all, to define this performance, often called Quality-of-Service, characterized by application constraints. In this chapter, we consider a firm real-time system whose performance level is mostly related to the percentage of jobs satisfying their deadlines.

From a software point of view, a real-time system is composed of application tasks and the real-time operating system (commonly referred to as RTOS) that ensures their scheduling. In Chapter 1, Volume 1 [CHE 14d], we have recalled the real-time schedulers typically implemented in current RTOSs. These schedulers have, for the most part, the particularity of being online, non-idling, priority-driven and preemptive. Their implementation does not lead to any major difficulty: one or more data structures organized in lists have to be managed. The role of the scheduler is to order these lists and update them, either using a fixed-priority policy such as rate monotonic or a dynamic-priority policy such as EDF [LIU 73]. However, these optimal schedulers offer their performance under the assumption that there is no energy limitation. Indeed, their optimality assumes that the processor has, at any time, the energy required for the execution of any job. Thus, we can see that the only constraint to be handled by the scheduler is a timing one. Schedulability conditions associated with these schedulers are, therefore, centered around the utilization factor of the processor or the processor demand by time interval.

In an energy-autonomous system, the issue of scheduling is related to jointly taking into account the two physical constraints: time, which is measured in seconds and energy, which is measured in joules. The following fundamental questions are, therefore, raised: can an efficient and capable scheduler, such as EDF, be suitable for systems subject to, besides timing constraints, energy constraints? Are there, in this new context proper to renewable energy harvesting, schedulers which are at the same time optimal and easily implementable? The initial studies related to these questions date back to the 2000s [ALL 01].

1.2. Modeling and terminology

1.2.1. System model

Hereafter, we describe the RTEH model that comprises a computing element, a set of jobs, an energy storage unit, an energy harvesting unit and the environmental energy source (see Figure 1.2).

1.2.1.1. Job model

We consider a set of real-time jobs that is executed on a single processing unit. A single operating frequency is supported. We assume the energy consumed in the idle state to be negligible. The energy consumption comes integrally from dynamic switching. The jobs are executed by exclusively using the energy generated by the environmental source. We denote by t = {ti, i = 1, ., n} the set of n preemptible jobs. The jobs are independent from one another. We associate the four-tuple (ri, Ci, Ei, di) with the job ti. This job arrives at time ri called release time, and requires a worst-case execution time of Ci time units and consumes Ei energy units in the worst case. The quantity Ei is not necessarily proportional to Ci [JAY 06]. In other words, the effective energy consumption of a job does not vary linearly with its effective execution time. During each time unit, we know an upper bound on the energy consumption of every job equal to eMax energy units. The exact amount of energy effectively drained in every time unit is, however, not known beforehand. The deadline of ti denoted by di represents the date at which ti has to have terminated its execution. We assume that min0=i=n ri = 0. Let dMax = max0=i=n di and D = max0=i=n (di - ri) be, respectively, the latest absolute deadline and the greatest relative deadline among those of the jobs of t. Ec(t1,t2) denotes the energy consumed by the jobs on the time interval [t1, t2). If the energy consumed by a job in each time unit is no less than the energy harvested on this same time unit, we say that the job is discharging [ALL 01]. Every job of t is discharging. Consequently, the residual capacity of the energy storage unit never increases every time a job executes.

Figure 1.2. The RTEH model

1.2.1.2. Energy production model

The...