Hussein El Ghor
email: husseinelghor@ul.edu.lb

Maryline Chetto
email: maryline.chetto@univ-nantes.fr

Optimal Real-Time Scheduling Algorithm for Wireless Sensors with Regenerative Energy

Keywords: Real-time systems, dynamic voltage and frequency scaling, energy harvesting, slack energy, optimal scheduling 1

Dynamic Voltage and Frequency Scaling (DVFS) is a promising and broadly used energy efficient technique to overcome the main problems arising from using a finite energy reservoir capacity and uncertain energy source in real-time embedded systems. This work investigates an energy management scheme for real-time task scheduling in variable voltage processors located in sensor nodes and powered by ambient energy sources. We use DVFS technique to decrease the energy consumption of sensors at the time when the energy sources are limited. In particular, we develop and prove an optimal realtime scheduling framework with speed stretching, namely Energy Guarantee Dynamic Voltage and Frequency Scaling (EG-DVFS), that jointly accounts not only for the timing constraints, but also for the energy state incurred by the properties of the system components. EG-DVFS relies on the well-known ED-H scheduling algorithm combined with DVFS technique where the sensor processing frequency is fine tuned to further minimize energy consumption and to achieve an energy autonomy of the system. Further, an exact feasibility test for a set of periodic, aperiodic or evern sporadic tasks is presented.

places where human beings have no access to reach these remote places all the time to manually recharge or replace the battery after it is discharged. In order for wireless sensor networks to become a ubiquitous part of our environment, energy harvesting sources to power sensor nodes must be employed to significantly increase the autonomy of the nodes and to overcome the energy limitations of battery-powered systems. Energy scavenging is essentially a technology that converts renewable generation into electrical energy which can be used to power electronic devices [START_REF] Priya | Energy Harvesting Technologies[END_REF]. Several implemented prototypes like Heliomote [START_REF] Raghunathan | Design considerations for solar energy harvesting wireless embedded systems[END_REF] or Prometheus [START_REF] Jiang | Perpetual environmentally powered sensor networks[END_REF] demonstrate the dominance of renewable energy to achieve perpetual operation.

Hence, energy scavenging represents a new candidate for the natural progression of energy optimization techniques, especially when the system should be designed to operate perpetually. However, the energy captured from the environmental energy sources is often inconstant and unpredictable [START_REF] Severini | Energy-aware lazy scheduling algorithm for energy-harvesting sensor nodes[END_REF], and therefore, a novel power management framework should be developed dedicated to energy scanvenging systems that is able to operate properly to achieve energy autonomy [START_REF] Liu | Harvesting-Aware Power Management for Real-Time Systems With Renewable Energy[END_REF].

Various power management techniques for reducing the energy consumption have been investigated in the earlier works. One of them is Dynamic Voltage Frequency Scaling (DVFS) [START_REF] Miao | Dynamic Power Management and Dynamic Voltage Scaling in Real-time CMP Systems[END_REF] and the other is Dynamic Power Management (DPM) [START_REF] Liu | Task merging for dynamic power management of cyclic applications in real-time multi-processor systems[END_REF]. DVFS is a popular and broadly used power management method in real-time systems. This method can be used to decrease the power consumption of a system at the time when the sources are limited [START_REF] Hong | Power optimization of variable-voltage core-based systems[END_REF], [START_REF] Luo | Static and dynamic variable voltage scheduling algorithms for real-time heterogeneous distributed embedded systems[END_REF]. Dynamic power management, on the other side, is a technique used to decrease the power consumption of a system. In dynamic power management the power manager puts the devices which are not being used in sleep mode and some power is saved [START_REF] Lu | Low-power task scheduling for multiple device[END_REF], [START_REF] Sinha | Dynamic Power Management in Wireless Sensor Networks[END_REF]. Although DVFS and DPM techniques are both dominant in reducing the energy consumption of the system, any portable device such as wireless sensor network will eventually deplete the energy reservoir. In addition, and while considering the energy reservoir as the only energy source, such design techniques will be wortheless.

Based on the green computing concept, developing energy-efficient mechanisms for real-time applications in wireless sensor networks becomes increasingly attractive. Nonetheless, the amount of energy harvested each day at a particular time varies in a nondeterministic manner. Therefore, energy management schemes are important in energy harvesting embedded systems as it helps in reducing the deadlines miss rate [START_REF] Kansal | Power management in energy harvesting sensor networks[END_REF], [START_REF] Liu | An adaptive scheduling and voltage/frequency selection algorithm for real-time energy harvesting systems[END_REF]. Under this context, DVFS technique has been widely employed to reduce energy consumption in energy harvesting systems.

The main objective of this paper is to design a scheduler that is able to assign periodic tasks to time slots while still guaranteeing all timing and power requirements during the whole lifetime of the application. This can be achieved by integrating the ED-H scheduling algorithm, that is proved in [START_REF] Chetto | Optimal Scheduling for Real-Time Jobs in Energy Harvesting Computing Systems[END_REF] to be an optimal scheduler for preemptive uniprocessor scheduling of independent tasks, with a dynamic voltage and frequency scaling technique to guarantee predictable task executions even in the face of energy shortage and to achieve lowest energy dissipation. This means adopting a strategy based on the complementary employment of an energy guarantee scheme for variable voltage processors dedicated to energy harvesting systems.

Given a real-time energy savenging system that is known to be feasible, we propose an Energy Guarantee -Dynamic Voltage and Frequency Scaling (EG-DVFS) scheduling algorithm with DVFS technique that allows to guarantee that all deadlines are met while still relying on a smaller solar cells as well as limited size of the energy storage element. The targeted system is predominantly energy efficient and the dissipated energy by tasks is not fixed since we can scale the processor speed to reduce energy consumption. Provided that the average scavenging power is sufficient for continuous operation, EG-DVFS makes best use of the available energy so as to minimize the necessary energy reservoir capacity. Thus, our system operates in energy neutral mode. This means that instead of saving some energy to elongate the operating time of energy reservoir, the system only consumes the energy recharged by the harvested power from the environmental energy source while still minimizing the energy consumption of the system, by slowing down the processor speed to the lowest possible state, leading to the absence of no deadline violation whenever possible.

The rest of the paper is organized as follows: Section 2 presents the prior research related to this work, whereas the energy scavenging system model and assumptions are presented in Section 3. Section 4 gives the necessary background materials that are essential for understanding the paper. The Energy Guarantee -Dynamic Voltage and Frequency Scaling (EG-DVFS) scheduling algorithm is presented in section 5. The optimality of EG-DVFS is proved in section 6. Section 7 concludes the paper.

Prior Work

Energy scavenging system design have been extensively studied using dynamic voltage and frequency selection technique. Researchers mainly focus on reducing the energy consumption by the tasks, hence reducing the processor power while still meeting the tasks deadline. Fot this sake, several scheduling algorithms have been developed that focus on energy efficient techniques for energy scavenging real-time systems.

The first valuable work that really studies the problem of power management while considering ambient energy sources has been studied in [START_REF] Kansal | Power management in energy harvesting sensor networks[END_REF]. Authors build a system that switches between busy mode and idle mode depending on harvested energy from the source. Later, Moser at al. [START_REF] Moser | Real-time scheduling for energy harvesting sensor nodes[END_REF] targets the case of scheduling tasks with deadlines on a uniprocessor system that is powered by a rechargeable energy reservoir. Authors propose an optimal idling energy-clairvoyant real-time scheduler named lazy scheduling algorithm (LSA). In LSA, the ready task with the earliest deadline is authorized to execute only if the system is able to keep on running at full processor speed and without violating its deadline. Disadvantages of LSA are the following: first, tasks run at maximum processor speed and hence, deadines of some future tasks may not be respected because of energy shortage. Second, the total energy dissipated by a task is necessarily proportional to its execution time, which is not the real case and finally the slack time is not used for energy savings.

Recently, many researchers have extensively studied low power systems in accordance with Dynamic Voltage and Frequency Scaling. In [START_REF] Liu | Energy Aware Dynamic Voltage and Frequency Selection for Real-Time Systems with Energy Harvesting[END_REF], authors proposed an energy-aware DVFS (EA-DVFS) algorithm that aims to exploit the slack time as much as possible to reduce the deadline miss rate. This can be achived by using a good tradeoff between the saved energy and the processor speed. The available energy mainly depends on the energy stored in the reservoir and the energy harvested from the renewable energy source. In case of insufficient available energy, the processor slows down the task execution; otherwise, the tasks are executed at maximum processor speed. The advantage of EA-DVFS is that it increases the percentage of feasibly executed tasks and reduces the storage capacity in case of low overload. However, EA-DVFS sill suffer from some inconvenients: First, authors perform the energy availability test based only on the single current task. Second, the scheduler can continue its operation as long as the energy is sufficient to complete executing a task whose relative deadline is no more than the remaining operation time of system at maximum processor speed [START_REF] Liu | Energy Aware Dynamic Voltage and Frequency Selection for Real-Time Systems with Energy Harvesting[END_REF]. For example, let us consider that the energy reservoir has only 1% energy and the system can execute the current task at full speed without exhausting the energy reservoir. Then, the EA-DVFS scheduler will run the task at maximum processor speed, which is not the correct behavior. Second, when using the task slacks, the proposed algorithm only considers the currect task instead of take into account all tasks in the ready queue. Hence, slack time is not fully exploited for reducing energy consumption.

To further improve such inconvenients, authors in [START_REF] Liu | Harvesting-Aware Power Management for Real-Time Systems With Renewable Energy[END_REF], propose harvestingaware DVFS (HA-DVFS) scheduler. HA-DVFS algorithm works as follows: HA-DVFS scales down the processor speed whenever possible for reducing energy dissipation. Indeed, the processor will speed up the execution of tasks in case of energy overflow. In this case, the current running task will finish its execution earlier before its deadline and thus, more slack time will be available for the succeeding tasks where the proseccor will have the opportunity to be slowed down for more energy saving.

To fully exploit the slack time, Chetto [START_REF] Chetto | Optimal Scheduling for Real-Time Jobs in Energy Harvesting Computing Systems[END_REF] proposed a scheduling algorithm, ED-H (Earliest Deadline -Harvesting), that accounts on the limits of both time and energy. ED-H relies on two basic concepts: slack time and slack energy. ED-H was proved in [START_REF] Chetto | Optimal Scheduling for Real-Time Jobs in Energy Harvesting Computing Systems[END_REF] to be optimal. However, in order to build an optimal schedule, ED-H needs to know the future task characteristics and the profile of the used energy source.

Later in [START_REF] Tan | A dynamic scheduling algorithm for energy harvesting embedded systems[END_REF], authors proposed an algorithm based on the DVFS technique that dynamically concentrates all disperse free time together to harvest energy by dynamically scheduling harvesting tasks and service tasks.

System Model and Assumptions

Hereafter, we consider a real-time energy scavenging system that consists of three major units: energy source module, energy dissipation module and energy reservoir of limited capacity (see figure ).

System Model

Energy Source Module

In this paper we talk about a real-time embedded system which is powered by an energy source unit that harvests the energy from external environmental sources like wind, sun, etc. Energy harvested from time t 1 to t 2 can be calculated using the following formula:

E s (t 1 , t 2 ) = t2 t1 P s (t)dt (1)
Where P s (t) is the worst case charging rate (WCCR) on the harvested source power output. We assume that it is not possible to determine the exact amount of energy harvested before hand but we can certainly predict the energy harvested by shadowing the previous energy source profile.

Energy Dissipation Module

We consider a real-time embedded system equipped with a DVFS technique as the primary power management technique. We assume that the DVFSenabled varaible speed processor works with N discrete frequencies ranging from

f min = f 1 ≤ f 2 ≤ • • • ≤ f N = f max
where f 1 is the minimum and f N is the maximum frequency at which the processor can work.

We characterize here a set of independent and non-preemptive periodic tasks that can be denoted as follows: Γ = {τ i |1 ≤ i ≤ n}. A five-tuple (r i , C i , D i , T i , E i ) is used to characterize a periodic real-time task τ i , where r i , C i , D i , T i and E i indicate the arrival time, the worst case execution time, the relative deadline, the period and the worst case energy consumption of task τ i , respectively. The instances of the tasks that are ready to get processed enter the ready queue where the task with the earliest deadline has the highest priority and should be executed first and preemption is allowed.

The power consumption of the tasks running in the processor depends on the processors frequency. This means that the power consumption of a task, say τ i , is dependent on its voltage and frequency level which is given by the relationship

P dyn = C L V 2 f (2)
Where C L is the gate load capacitance. We define a slowdown factor as the ratio of the current frequency to the maximum frequency of the processor and is denoted by S n . This factor can range from S min to 1.

S n = f n f max (3)
When we stretch a task τ i by a slowdown factor S k , then its actual execution time, denoted by C i (a), at frequency f k will be C i /S k . We assume that each task τ i from a task set Γ have different power dissipation which also changes with its frequencies. Thus a task will have maximum power dissipation at its maximum frequency and it decreases as the frequency decreases. For convenience, we define power dissipation of a task as a function of task index and its slowdown factor P D (τ i , S k ). The energy dissipation of the task can be found as shown below:

E D (St i , F t i ) = P D (τ i , S k ) × C i /S k (4)
Where St i and F t i are respectively the start time and finish time of task τ i .

Energy Storage Module

Energy reservoir is also required in an energy scavenging real-time system since the system needs it to continue operation even in abscence of energy harvested from the environment. In our work, we use an energy reservoir, for example a rechargeable battery, that has a nominal capacity C and it is used to store the extra amount of energy harvested for the future use at times of crisis. In our case, we ignore the amount of energy wasted in the process of charging and discharging and hence we use an ideal energy storage unit.

There is an upper limit to the storage device denoted by C max which is the maximum capacity of the energy reservoir. The lower limit of the capacitor, denoted as C min , cannot be zero since there is an energy reserved in the capacitor for worst case scenarios. During the normal operation mode and at a given time t we have

C min ≤ C(t) ≤ C max (5)
and

C(t 2 ) ≤ C(t 1 ) + E s (t 1 , t 2 ) -E D (t 1 , t 2 ) ∀ t 2 > t 1 (6)

Terminology

In this subsection, we state some definitions that will be helpful in the remainder of this paper.

Definition 1 A schedule ω for a task set Γ is said to be time-valid if the deadlines of all tasks of Γ are met in ω, considering that ∀ 1 ≤ i ≤ n, E i = 0.
Definition 2 A schedule ω for a task set Γ is said to be energy-valid if the deadlines of all tasks of Γ are met in ω, considering that ∀ 1 ≤ i ≤ n, C i = 0.

Definition 3 A schedule ω for a task set Γ is said to be valid if the deadlines of all tasks of Γ are met in ω, starting with a storage fully charged, with the energy generated by a given energy source.

Definition 4 A task set Γ is said to be temporally-feasible if there exists a valid schedule for Γ without considering its energy constraints.

Definition 5 A task set Γ is said to be energy-feasible if there exists an energy valid schedule for Γ . Definition 6 A system is said to be feasible if there exists at least one valid schedule for ω with the given energy source and energy storage. Otherwise, it is infeasible.

When systems are infeasible, the limiting factors are either both time and energy or only time or only energy. We focus in this article on feasible systems only.

Definition 7 A scheduling algorithm ω for a task set Γ is said to be optimal if it finds a valid schedule whenever one exists.

Background Materials

Classical Concepts for Real-Time Scheduling

we recall some concepts related to real-time scheduling. To formally present the background material, we define the following factors: the processor demand and the slack time.

Definition 8

The processor demand of a task set Γ on the time interval

[t 1 , t 2 ) is h(t 1 , t 2 ) = t1≤r k ,d k ≤t2 C k (7)
Denote now t c as the current time where we have to schedule a task set Γ by a certain scheduling algorithm ω. In the real-time scheduling theory (without energy consideration), and for a given task set Γ , the term slack time is defined as the longest interval of time starting at t c during which the processor may be idle continuously while still respecting all the timing constraints.

Definition 9

The slack time of a task τ i at current time t c is

ST τi (t c ) = d i -t c -h(t c , d i ) -AT i (8)
Where AT i is the total remaining execution time of uncompleted tasks currently ready at t c and in the time interval [t c , d i ). Hence, ST τi (t c ) gives the time available by the processor after executing uncompleted tasks with deadlines at or before d i .

The slack time of the task set Γ is then the minimum of the slack times of all tasks in Γ .

Definition 10

The slack time of a task set Γ at current time t c is

ST Γ (t c ) = min di>tc ST τi (t c ) (9)
Equation 9 represents the maximum continuous time that the processor can be inactive starting from time t c while still respecting the deadlines of all the tasks in Γ .

Earliest Deadline-Havesting (ED-H) Scheduler

Before presenting the ED-H scheduler, we have to introduce some novel concepts related to the feasibe scheduling when considering both time and energy constraints. These factors are the energy demand and the slack energy.

Let us denote r k , d k and E k as the release time, deadline and worst case energy consumption of task τ k respectively.

Definition 11

The energy demand of a task set Γ on the time interval

[t 1 , t2) is g(t 1 , t 2 ) = t1≤r k ,d k ≤t2 E k (10)
In [START_REF] Hussein El Ghor | A real-time scheduling framework for embedded systems with environmental energy harvesting[END_REF], we defined the concept of slack energy of a task τ i at a current time t c as the amount of energy surplus in the reservoir that can be used from t c till the start time of τ j and without violating its timing and energy requirements.

Definition 12

The slack energy of a task τ i at current time t c is

SE τi (t c ) = E(t c ) + E s (t c , d i ) -g(t c , d i ) (11)
The slack energy of the task set Γ is determined by the minimum slack energy of all the tasks.

Definition 13

The slack energy of a task set Γ at current time t c is

SE Γ (t c ) = min tc<ri<di<d SE τi (t c ) ( 12
)
Where d is the deadline of the active task at time t c .

ED-H scheduler [START_REF] Chetto | Optimal Scheduling for Real-Time Jobs in Energy Harvesting Computing Systems[END_REF] is an extension of EDF with energy budgeting that manages timing and energy requirements as well as the replenishment rate of the storage unit for monoprocessor embedded systems with solar energy harvesting capability. The novelty of ED-H is that it prevents energy starvation. The main intuition behind ED-H is that it dynamically adapts the processor state to the runtime harvested power variations without violating the deadlines of the tasks. This means that ED-H has to verify the following two conditions to let the processor busy:

1. The available energy in the reservoir is enough to execute the ready task with the highest priority even for the next unit timeslot. 2. The energy consumption in that time-slot must guarantee the energy feasibility of all future occurring tasks considering their timing and energy requirements and the replenishment rate of the storage.

When these conditions are verified, ED-H will schedule tasks according to the EDF policy. However, ED-H may result in unnecessary deadline violations if one of these conditions is not fulfilled. The processor will then stay idle so that the energy reservoir is fully replenished or the slack time becomes equal to zero. Note that the ED-H degenerates to the EDF scheduling policy if the processor utilization is equal to one. ED-H was proved in [START_REF] Chetto | Optimal Scheduling for Real-Time Jobs in Energy Harvesting Computing Systems[END_REF] to be optimal for a considered real-time energy harvesting system.

Theorem 1

The ED-H scheduling algorithm is optimal for the real-time energy harvesting model.

Proof See [START_REF] Chetto | Optimal Scheduling for Real-Time Jobs in Energy Harvesting Computing Systems[END_REF].

Moreover, Chetto produced the necessary feasibility condition for a given task set Γ that is scheduled by the ED-H algortithm. The test for the schedulability of ED-H is reduced to test time-feasibility and energy-feasibility separately [START_REF] Chetto | Optimal Scheduling for Real-Time Jobs in Energy Harvesting Computing Systems[END_REF].

As for the time-feasibility condition, consider that for every task τ i in a given task set Γ , E i = 0.

Lemma 1 A task set Γ is time-feasible by ED-H if and only if

sup 0≤t1<t2<dmax h(t 1 , t 2 ) t 2 -t 1 ≤ 1 ( 13
)
Where

d max = max 1≤i≤n d i
Proof See [START_REF] Chetto | Optimal Scheduling for Real-Time Jobs in Energy Harvesting Computing Systems[END_REF].

Now, consider the energy-feasibility condition where it is assumed that for every task τ i in a given task set Γ , C i = 0. Lemma 2 A task set Γ is energy-feasible by ED-H if and only if

sup 0≤t1<t2<dmax g(t 1 , t 2 ) C + E s (t 1 , t 2 ) ≤ 1 ( 14
)
Where

d max = max 1≤i≤n d i
Proof See [START_REF] Chetto | Optimal Scheduling for Real-Time Jobs in Energy Harvesting Computing Systems[END_REF].

From Lemma 1, and Lemma 2, we can deduce the feasibility test for a given task set Γ .

Lemma 3 A task set Γ is feasible by ED-H if and only if

sup 0≤t1<t2<dmax h(t 1 , t 2 ) t 2 -t 1 ≤ 1 and sup 0≤t1<t2<dmax g(t 1 , t 2 ) C + E s (t 1 , t 2 ) ≤ 1 ( 15
)
Proof See [START_REF] Chetto | Optimal Scheduling for Real-Time Jobs in Energy Harvesting Computing Systems[END_REF].

5 Energy Guarantee -Dynamic Voltage and Frequency Scaling (EG-DVFS) Algorithm

Overview of the Scheduling Algorithm

The naive approach of simply scheduling tasks with full processor speed may produce some deadline violations. This may occur when after the execution of task, say τ 1 , another task, say τ 2 , is ready with the highest priority. If now the required energy to complete the execution of τ 2 at full processor speed is not available in the energy storage unit even when using the available slack time, the ED-H scheduler produces a deadline violation. If the processor speed would be scaled down to decrease the energy consumption of τ 2 instead of executing at full speed, this deadline violation might have been avoidable. These considerations directly lead us to the principle of Energy Guarantee -Dynamic Voltage and Frequency Scaling (EG-DVFS) algorithm: scale the processor speed only if it is necessary to decrease the energy consumption of tasks while still guaranteeing the deadlines of tasks. In other words, we need to perform a check at run-time for the energy availability and after that adjust the scheduling. If the available energy is not enough for a task's scheduling, we must make adjustments to deal with the energy shortage.

Initially, all tasks are executed according to EDF scheduler where the system operates at full processor speed. We assume that the start time of any given task is derived under the assumption that the task executes at the constant processor speed until its completion. Let us consider that, there are M task instances in the ready queue. St i and F t i are denoted as the start time and finish time of task τ i respectively. Obviously, the start time of the first task instance, say τ 1 , in the ready queue is equal to its release time.

St 1 = r 1 (16)
Thus, we can compute the start time of the remaining task instances as:

St i = max(r i , F t i-1 ) 2 ≤ i ≤ M -1 (17)
When applying the EG-DVFS policy for a ready task, say τ i , with the highest priority, we have to ensure that the available energy is sufficient to to completely execute τ i . This means that we have to compute the remaining energy in the energy storage unit at the end of the task execution using the following equation:

C(F t i ) = C(St i ) + E s (St i , F t i ) -E i (St i , F t i ) (18)
If C(F t i ) > 0, then EG-DVFS instantaneouly executes τ i at the scheduled start time and with full processor speed (S i = 1). On the other side, energy conflicts occur if the required energy is simply not available at the finishing time F t i . This means that when the energy is required to execute τ i , the energy storage level is not sufficient to meet the deadline (energy reservoir is exhausted at F t i ). In this step, we have to "stretch" the task executions to minimize their energy dissipation by executing at lower energy and frequency levels of the processor. Thus, EG-DVFS has to decide the slowdown factor for τ i based on the processor utilization and energy state. Following this rule, the tasks can be slowed down by a factor S n in cases where we have insufficient energy to run the task at its full speed which in turn increases the worst case execution time. Thus, we have to compute the slack time of the system at St i and the task's execution time will be stretched to the actual execution time C i (a) where:

C i (a) = C i + ST (St i ) (19)
The finishing time of task instance τ i can be calculated as

F t i = St i + C i (a) (20)
Consequently the start time of the next task instance will be:

St i+1 = max(r i+1 , F t i ) (21)
The slowdown factor is thus computed thanks to the following equation:

S i = C i C i (a) (22)
It is worthwhile to mention that since, every task τ i must complete the execution before its absolute deadline , then the following equation must hold:

r i + d i -c i (a) ≥ max{r i , t} (23)
Where t is the current time instance.

Furthermore, the execution of any real-time task τ i is considered to be preemptable which means that when a task of higher priority becomes ready, it will preempt the execution of the current task of lower priority. This implies that the start time of a task τ i is equal to St i = max(r i , F t i-1 ) when τ i finishes its execution without being preempted by other task. When preemption occurs, the start time of the newly arrived task is equal to r i . That is

St i = max(r i , F t i-1 ) if r i + d i -C i (a) ≥ max(r i , t) r i otherwise (24)
However, when we resume execution of the preempted task , it has the opportunity to run at the same or different processor speed, depending upon the system state.

Description of the EG-DVFS Scheduler

In what follows, we consider a given task set Γ that is known to be feasible for the real-time energy harvesting model. Let Q r (t) be the queue of uncompleted tasks ready for execution at t. The EG-DVFS scheduling algorithm obeys the following rules.

-Rule 1: The future running task in Q r (t) is ordered according to the EDF policy. -Rule 2: The processor is imperatively idle in

[t, t + 1) if Q r (t) = φ. -Rule 3: The incoming power is wasted in [t, t + 1) if Q r (t) = φ and C(t) = C. -Rule 4: The processor operates at maximum speed in [t, t+1) if Q r (t) = φ
and at least one of the following conditions is satisfied:

(t) = φ, 0 < C(t) < C, ST Γ (t) > 0 and SE Γ (t) > 0.
All tasks in the ready queue are ordered according to the EDF policy. The only case that the processor is imperatively idle is when the ready queue is empty. The incoming power is wasted only when the ready queue is empty and the energy reservoir is fully replenished. Rules 4.1 and 4.2 say that the processor is active and can operate at full speed if either the energy storage unit is fully charged or using slack time at current time t would cause a deadline violation of at least one future task. Rules 5.1 and 5.2 state that the processor must scale down its speed to decrease the energy consumption of the tasks if the energy rservoir is depleted or executing any task at full speed would prevent at least one future task from being executed before its deadline because of energy starvation (slack time is zero). In this case EG-DVFS must decide the speed at which the task should be executed depending on the energy availability. This means that for the execution of the ready task to be accomplished, we must consider the amount of energy harvested during its execution time and then decide the amount by which the task can be stretched in order to avoid energy deficiency at any point of time. Rule 6 says that the processor operates at full speed when the energy reservoir capacity at time t is not empty even if there is slack time.

6 Properties of EG-DVFS Scheduling

Optimality of EG-DVFS

First, we will demonstrate that EG-DVFS is optimal with respect to minimizing the processor energy consumption and the maximum lateness. Let L max be the maximum lateness that upper-bounds the time by which any task misses its deadline.

L max = max τi (F t i -d i ) (25)
Theorem 2 Given a task τ i in a task set Γ with arbitrary arrival times r i , computation times C i and deadlines d i , the EG-DVFS algorithm that at every scheduling instant t i executes the task with the earliest deadline among all the ready tasks with a processing slowdown factor S i is optimal with respect to minimizing the processor energy consumption and the maximum lateness. The optimum processing factor is

S i = Ci Ci+ST Γ (ti) if SE Γ (t i ) ≈ 0 or C(t i ) ≈ 0 1 otherwise ( 26
)
Proof Suppose that there can be another slowdown factor S i where we slow down the ready task with the earliest deadline, say τ k , to the maximum possible extent just before its deadline in order to achieve the maximum energy savings.

Clearly S i must be no more than S i . Here, we have the following cases: Case 1: The energy reservoir is fully replenished or there is no slack time. This case directly follows Rule 4. In this case the processor will execute at full processor speed, then S i = S i = 1. This contradicts that there exists a slowdown factor to achieve more energy saving. Case 2: The energy is fully depleted or the slack energy is zero. This case directly follows Rule 5. Here the processor must slow down its speed to achieve energy saving while still guaranteeing the deadlines of future tasks. To stretch the task execution at time t i , we use the slack time ST Γ (t i ) of the system t i . To obtain more energy saving, we must stretch the task execution by using another slack time, say ST Γ (t i ) greater than ST Γ (t i ). However, following the definition of slack time, we get that ST Γ (t i ) is the longest interval of time starting at t i during which the processor may be idle continuously while still respecting all the timing constraints. Thus, using ST Γ (t i ) > ST Γ (t i ) can give rise to conditions where we have sufficient energy to execute the present task with S i speed, but still there is a timing constraint for the future tasks. Consequently even if the future task runs with the slowdown factor equals one which is highest frequency, it cannot meet its deadline as the task before it was slowed down to more than its maximum extent. This contradicts that S i exists. This concludes that S i is the optimal slowdown factor that achieves the best energy saving. In additon, since EG-DVFS stretches the task execution to its maximum extent without violating future deadlines, then the deadline of tasks will be approximately tight since tasks will finish very close to their deadlines and consequently, the maximum lateness L max will be the smallest possible.

In what follows, we will prove that EG-DVFS Scheduling algorithms optimal in the sense that if EG-DVFS is not able to schedule a given task set Γ , then no other scheduling algorithm is able to schedule it. For this sake, we have to show that EG-DVFS makes the best use of the available time and energy. The scheduling policy presented in this article is inherently energy-driven. Thus, a deadline violation occurs if EG-DVFS fails to completely execute a task, say τ i , assigned by an energy dissipation E i before its deadline d i . A deadline violation can occur due one of the two following situations:

-Time starvation: A deadline d cannot be guaranteed when a task is not able to finish its execution before its deadline and the energy reservoir is not depleted at time d (i.e. C(d) > 0). -Energy starvation: A deadline d cannot be guaranteed when a task is not able to finish its execution before its deadline because the energy reservoir is exhausted when the deadline violation occurs (i.e. C(d) ≈ 0)

We suppose that when system is initialized, we have a full energy storage capacity, i.e., C(0) = C. Furthermore, the processor is idle at a given time t only if the ready queue is empty. The proof of theorems 1 and 2 directly follows the proof of the optimality of ED-H in [START_REF] Chetto | Optimal Scheduling for Real-Time Jobs in Energy Harvesting Computing Systems[END_REF].

Theorem 3 Let Γ be a set of tasks that are scheduled by the EG-DVFS algorithm. Suppose that a task with deadline d and release time r is missed because of time starvation with C(d) > 0. Then there exists a time instant t such that the processor load h(t,d) d-t in the interval [t, d] exceeds one and no schedule exists where d and all previous deadlines are met.

Proof Let us suppose that t 0 is the maximal time before d where the processor was running with a low processor speed. Clearly, such a time exists. At first, the processor constantly operates with full speed on the tasks within the time interval [t 0 , d). We consider here the two following cases:

Case 1: There is at least one ready task at time t 0 . The processor stops to slowdown the processor at time t 0 if: Case 1a: The energy reservoir is fully recharged at time t 0 , i.e. C(t 0 ) = C from rule 4.1.

Case 1b: The slack time of the task set Γ becomes zero at time t 0 , i.e. ST Γ (t 0 ) = 0 from rule 4.2.

However, since the processor is constantly operating at full speed on tasks in time interval [t 0 , d) and E(d) > 0, then there is no slack time in [t 0 , d). Therefore, EG-DVFS will directly execute tasks with deadline at or before d which are ready at time t 0 and released within [t 0 , d) by applying the EDF strategy. But since no slack time is found, this implies that d -t 0 > h(t 0 , d) which contradicts that d is missed.

Case 2: There is no ready task at time t 0 . In this case t 0 must coincide with the arrival of a task, say τ k , whose release time r k = t 0 that verifies r k ≤ r. Here we have 2 cases:

Case 2a: d k ≤ d. This means that τ k is completely executed before d 2 since d is the first violated deadline and tasks are scheduled according to the EDF policy in EG-DVFS.

Case 2a1: According to rule 4, the processor operates at maximum speed at time r k either because there is no slack time at r k (ST (r 2 ) = 0) or because the energy reservoir at r 2 is fully replenished. But since E(d) > 0, then ST (r 2 ) is no greater than zero. Consequently the processor demand in the time interval [r k , d), given by h(r k , d) = r k ≤rj ,dj ≤d C j ≤ d -r k which contracdicts that the deadline d is missed. And no other scheduler can produce a valid schedule on [r k , d).

Case 2a2: According to rule 6, the processor operates at full speed at time r k when 0 < C(t) < C, ST Γ (t) > 0 and SE Γ (t) > 0. As the slack time of the task set Γ at time r 2 is greater than zero, this means that the processor demand, which is the sum of the WCET of all tasks with arrival and deadline within time interval [r k , d), is smaller than the allowed time (d -r k ), i.e. h(r k , d) = r k ≤rj ,dj ≤d C j < d -r k . This contradicts that d is missed. Now, we can show that a related result also holds for the energy starvation case, too.

Theorem 4 Let Γ be a set of tasks that are scheduled by the EG-DVFS algorithm. Suppose that a task with deadline d and release time r is missed because of energy starvation with C(d) = 0. Then there exists a time instant t such that the energy load g(t,d) C+Es(t,d) in the interval [t, d] exceeds one and no schedule exists where d and all previous deadlines are met.

Proof Let us consider that deadline d is the first deadline of the task set that is missed by EG-DVFS due to energy starvation, i.e. C(d) = 0. Let t 0 be the largest time before d (t 0 < d) where a task with deadline greater than d is released such that the energy reservoir is fully replenished at t 0 (C(t 0 ) = C) and no task τ i waiting just before t 0 . As t 0 is the last time instance with the above properties, then the processor is idle in the time interval [t 0 -1, t 0 ) since no task is ready (Rule 2). The processor is now operating with full speed at least in the time interval [t 0 , t 0 + 1). Here we have 2 cases: Case 1: No task with deadline greater than d is executed within the time interval [t 0 , d). The energy reservoir is fully charged time t 0 , then according to Rule 4.1, the processor will at full speed and the stored energy is used to advance all waiting tasks with release time greater than or equal to t 0 and deadline at or before d with an energy demand equal to g(t 0 , d). But, since the task set Γ is feasible, then the demanded energy to complete the execution at full processor speed is no more than the energy reservoir capacity plus the energy drained from the source, or shortly g(t 0 , d) < C + E s (t 0 , d). From above, we can conclude that all tasks ready within the time interval [t 0 , d) are completely executed without depleting the energy reservoir, consequently C(d) > 0 which contradicts that d is missed. Case 2: At least one task with deadline greater than d is executed within the time interval [t 0 , d). Since there is no task waiting with deadline smaller than d, the processor would operate on task, say τ 2 with d 2 > d. Consider t 2 be the latest time where τ 2 executed. But since d < d 2 and tasks are executed according to the earliest deadline rule in EG-DVFS, then r 2 must be no more than r 1 . At time t 2 , one of the following situations occurs.

Case 2a: Tasks are executed at full processor speed all the times in [t 2 , d). Let's consider now that a task, say τ 3 is released after t 2 an with deadline d 3 < d 2 , then τ 2 is preempted by τ 3 . Hence, SE Γ (r 3 ) is greater than zero. This implies that g(r 3 , d) < C(r 3 ) + E s (r 3 , d). Consequently, the maximum amount of energy required by tasks released at or after r 3 and with deadline at or before d is g(r 3 , d). This contradicts that the energy reservoir is empty at d and hence the deadline d is not violated.

Case 2b: The processor works at lower speed from t 3 -1 to t 3 with t 3 > t 2 and at full speed all in the time interval [t 3 , d). The processor stops working with lower speed at time t 3 by Rule 4 if C(t 3 ) = C or ST Γ (t 3 ) = 0. Here, there is no task ready at t 3 with deadline smaller than d since t 0 is the latest one. In addition, no task with deadline after d is executed in the time interval [t 2 , d) which includes time t 3 . Thus all the energy drained from the source is used to advance waiting tasks with deadline greater than d. To maintain a maximum energy level at r, the processor will contineously scale the processor speed till time r where C(r) = C. But since the task set Γ is feasible, then g(r, d) < C(r)+E s (r, d). That contradicts deadline violation of d and E(d) = 0.

From the above two theorems, we conclude the following: First, in the time starvation case, there exists some interval of time [t, d) before the deadline d is violated such that the processor load h(t,d) d-t exceeds one. And second, in the energy starvation case, there exists some interval of time [t, d) before the deadline d is violated such that the energy load g(t,d) C+Es(t,d) exceeds one. These considerations lead us to Theorem 3 one of the major results for uniprocessor scheduling in real-time energy harvesting (RTEH) systems with DVFS scaling:

Theorem 5 The EG-DVFS scheduling algorithm is optimal for RTEH systems with DVFS scaling.

Proof The proof of this theorem follows immediately from Theorems 3 and 4. We consider in the above theorem the case of scheduling a task set Γ by EG-DVFS algorithm where a deadline d of task τ is missed and it is the first deadline in Γ that is missed by EG-DVFS. In what follows, we distinguish between the case where d is violated because of time starvation (Theorem 3) and energy starvation (Theorem 4) respectively. According to theorem 3, time starvation occurs when there exists some interval of time [t, d) before the deadline d is violated such that the processor load

h(t,d)
d-t exceeds one where C(d) > 0. Then, if EG-DVFS is unable to respect the deadline d and all earlier deadlines simultaneously in Γ , then no other scheduling algorithm can do that. Same to Theorem 4, where energy starvation occurs when there exists some interval of time [t, d) before the deadline d is violated such that the energy load g(t,d) C+Es(t,d) exceeds one. This case also concludes that it is impossible for another scheduling algorithm to guarantee the execution of task τ with deadline d and all earlier deadlines simultaneously. But, since every time deadline d is violated by EG-DVFS, we have either the time starvation reason or the energy starvation reason, and we prove that in both reasons, it is impossible for another scheduler to meet deadline d and all earlier deadlines simultaneously, then conclude that EG-DVFS is optimal.

Feasibility Analysis

In this section, we are concerned with the EG-DVFS algorithm by which, given a task set Γ , we must be capable of answering the following question: if Γ is feasible by ED-H, does it remain feasible by EG-DVFS? According to Definition 6, a task set is said to be feasible if there exists at least one valid schedule with the given energy source E s (t) and energy storage C. As we demonstrated in Theorem 5, we proved that EG-DVFS is optimal for a RTEH system with DVFS scaling, we must derive the conditions under which the EG-DVFS scheduler avoids deadline violations for a given task set Γ . In what follows, we will prove that a task set that is feasible by ED-H remains feasible by EG-DVFS. To do this, we will separate our proof to time-feasibility condition and and energy-feasibility condition. Theorem 6 A task set Γ that is time-feasible with ED-H remains feasible with EG-DVFS. Proof In the time constraint case, we consider that tasks have processing requirements only. This means that for every task τ k ∈ Γ , E k = 0. In the classical scheduling theory, we say that Γ is feasible if the processor demand in every time interval must be less than or equal to the length of this interval, or simply the processor utilization must be no more than one. Let us consider U p and U p as the processor utilization of ED-H and EG-DVFS respectively. If ED-H is feasible then U p ≤ 1. We must prove that if U p ≤ 1, then U p ≤ 1. Suppose that the task set Γ is not time-feasible by EG-DVFS, then U p > 1. But U p = n i=1 Ci(a) Ti According to ED-H, if Γ is time-feasible, then U p ≤ 1 and the total slack time during a whole hyperperiod T LCM is equal to T LCM (1 -U p ). This contradicts that U p > 1. Consequently, EG-DVFS is time-feasible since it is not processor-overloaded in any time interval.

According to the energy constraint case, tasks in Γ have only energy constraints. This means that for every task τ k ∈ Γ , C k = 0. Theorem 7 A task set Γ that is energy-feasible with ED-H remains feasible with EG-DVFS.

Proof Since Γ is energy-feasible by ED-H, then in every interval of time [t 1 , t 2 ), the energy demand is necessarily no more than the available energy in [t 1 , t 2 ), i.e. g(t 1 , t 2 ) ≤ C(t 1 ) + E s (t 1 , t 2 ). Let g (t 1 , t 2 ) be the energy demanded by tasks according to EG-DVFS. We consider two cases: Case 1: The processor executes all tasks with full speed. In this case, the demanded energy is the same in EG-DVFS and ED-H, i.e. g (t 1 , t 2 ) = g(t 1 , t 2 ). But since Γ is energy-feasible by ED-H, then ∀(t 1 , t 2 ) ⊂ [0, d max ), g(t 1 , t 2 ) ≤ C + E s (t 1 , t 2 ), consequently g (t 1 , t 2 ) ≤ C + E s (t 1 , t 2 ). This concludes that when ED-H is energy-feasible, then EG-DVFS is also energy-feasible. Case 2: The processor scales down its speed to execute some tasks τ k in Γ . In this case, the consumed energy by tasks is decreased by scaling down the processor speed to save energy. Hence, the energy demanded in EG-DVFS must be less than that of ED-H i.e. g (t 1 , t 2 ) < g(t 1 , t 2 ). But since Γ is energyfeasible by ED-H, then ∀(t 1 , t 2 ) ⊂ [0, d max ), g(t 1 , t 2 ) ≤ C + E s (t 1 , t 2 ), Hence, g (t 1 , t 2 ) ≤ C + E s (t 1 , t 2 ), and consequently Γ is energy-feasible by EG-DVFS.

From theorems 6 and 7, we can derive the feasibility of EG-DVFS. Theorem 8 A task set Γ that is feasible with ED-H remains feasible with EG-DVFS.

Conclusion

In this paper, we studied the problem of energy guarantee scheduling and dynamic voltage/frequency selection technique targeting at real-time systems with ambient energy sources. To this end, we proposed an Energy Guarantee DVFS (EG-DVFS) algorithm that considers both energy and timing constraints of the energy harvesting systems. The purpose from EG-DVFS was successfully achieved by compensating the extra/less energy harvested from the environment in such a way that the perpetual and self-sustaining operation of the system can be achieved. EG-DVFS is proved to be optimal and appropriate in minimizing the maximum lateness and the processor energy consumption. We also proved that if a given a task set Γ is feasible by ED-H, then it is also feasible by EG-DVFS. In this sense, EG-DVFS is able to feasibly schedule any task set as long as both the processor load and the energy load are no more than one. There are number of places where we can work in order to enhance the above mentioned algorithm further. First, we will explore dynamic task allocation and frequency selection scheme for multiprocessor systems based on the scheduling scheme proposed in this paper. Second, we will adapt the proposed scheduler to fixed priority environments.

1 .

 1 By multiplying the whole equality by the hyperperiod T LCM , we getT LCM U p + T LCM n i=1 ST (Sti) Ti > T LCM . But since Γ is periodic, then T LCM n i=1 ST (Sti) Tiis equal to the total slack time ST tot . By substitution, we get T LCM U p +ST tot > T LCM , then ST tot > T LCM (1 -U p ).