Overload Management Through Selective Data Dropping

Introduction

During system and network overload periods, excessive delay or even data loss may occur. To maintain the quality of control of an NCS, the implementation system (including both computer and network) overload must be correctly handled. As we can see in the previous chapters, a common approach to dealing with this overload problem is to dynamically change the sampling period of the control loops. In this chapter, as an alternative to the explicit sampling period adjustment, we present an indirect sampling period adjustment approach which is based on selective sampling data dropping according to the (m, k)-firm model [HAM 94]. The interest of this alternative is its easy implementation despite having less adjustment quality, since only the multiples of the basic sampling period can be exploited. Upon overload detection, the basic idea is to selectively drop some samples according to the (m, k)-firm model to avoid long consecutive data drops. The consequence is that the shared network and processor will be less loaded. However, the control stability and performance must still be maintained to an acceptable level. This can be achieved by keeping either the total control tasks on a same processor or the messages sharing a same network bandwidth schedulable under the (m, k)-firm constraint.

In this chapter, we first give a sufficient condition for scheduling a set of control tasks under (m, k)-firm constraint (section 5.2). Then, through several examples, we Chapter written by Flavia FELICIONI, Ning JIA, Françoise SIMONOT-LION and Ye-Qiong SONG.

present the methods for determining the value of k for a given control loop which will still maintain control loop stability (section 5.3), and the optimal values of m and the control gains which minimize a total cost function either in the presence of the control task configuration changes (section 5.4) or by further coping with the plant state changes (section 5.5). The problem of control loop stability with on-line parameter switching is also discussed in section 5.5.1.

To better illustrate this approach, let us first present the generic system architecture. Then, we identify the problem to solve and provide several notations.

System architecture

We consider a global control architecture that integrates a set of plants to control, each one being controlled by a discrete controller. We are interested in the deployment of the control application onto limited resources; for example, all the numerical controllers share the same processors or all the plant states sampled by sensors are transmitted to the controller through the same communication architecture. Moreover, we suppose that according to the global state of the plant, a supervisor chooses the current working mode of the global system. In particular, it can stop the control of a plant, start the control of a plant or modify the control strategy of a plant (control law, sampling period, etc.). The consequence of the transition between working modes is the modification of the set of active tasks/messages that can bring about -some of them are stopped, -new tasks are activated or new messages are transmitted, -the characteristics of tasks may be modified, for example, changing their Worst Case Execution Time (WCET); the characteristics of messages can be modified, for example, their size or the sampling period can be transformed by using a new control strategy.

This means that the scheduling of the messages on a network or the scheduling of the tasks on a processor have to be redefined each time the supervisor modifies the global control mode. The schedulability analysis of a set of tasks or messages subject to hard real-time constraints (all the instances have to meet their deadline) can lead to over provisioning of the resources and this oversizing can be worse in the case of an architecture that implements several working modes as already mentioned before. Moreover, the relationship between the performance of the control and the scheduling of the activities is not well known quantitatively; therefore, the identification of the scheduling parameters relies generally on experiments and/or simulations [SIM 05] that are not exhaustive and so, cannot be generalized. So, a feasible scheduling provided by applying the relaxation of timed constraints as proposed in the classical solution does not lead systematically to the optimal performance of the control application.

Therefore, we propose a new scheduling architecture for handling such configurations as well as an adaptive technique that makes adjustments on-line for, on the one hand, the (m, k)-firm constraints of activities (data transmission and/or task implementing the control law) and, on the other hand, the parameters of the control laws. By doing so, the global performance of the application is fixed at an optimized level and the schedulability under (m, k)-firm constraints is guaranteed.

In the case study that will illustrate the adaptive approach, we consider plants that correspond to harmonic oscillators (as, for example, cart systems, a pendulum or an inverted pendulum). Furthermore, the solution is detailed for processor sharing and therefore, we will deal with the scheduling of tasks instead of messages.

The scheduling architecture is illustrated in figure 5.1. The system to control is composed of a set of plants (Plant 1, Plant 2, ..., Plant n) that are assumed to be independent. Each plant is controlled by a controller (Controller 1, Controller 2, ..., Controller n). In this example, the controllers are deployed as a set of n tasks (τ 1 , τ 2 , .., τ n ) on the same processor. A task handler is dedicated to the identification of the optimal configuration of (m i , k i )-firm constraints for each task τ i running on the processor. The system is observed by a supervisor, assumed implemented on another processor. The role of the supervisor is to observe the state of the plants and to decide at each instant which plants have to be controlled and which control laws have to be applied. Each time the supervisor modifies the configuration of the system, it sends the task handler a list of active controllers as well as their new characteristics, in short, the activation period and the worst case execution time of the control law. Of course, the schedulability of this task set must be guaranteed in sense of (m i , k i )-firm.

Problem statement

The global problem of finding, at each instant an optimized scheduling of control tasks can be divided into several sub-problems.

-Firstly, we have to ensure, at least the stability of each controlled system. This will be achieved by the specification of the highest value of k i in the constraint (m i , k i ) of each task τ i sharing the processor that ensures the stability under a (1, k i )-firm constraint.

-A second problem concerns the optimization issue. Two main considerations have to be taken into account in this context : what is the cost function? what are the criteria? For the first question, we will use the (Linear Quadratic Regulator LQR) cost function that is classically applied in the control community. The determination of the value of the parameter m i in the (m i , k i ) constraint of each task τ i will answer the second question.

Solutions to these different problems will be presented in the remaining part of this chapter. But, first of all, let us give more details in the following section on how to schedule tasks under (m, k)-firm constraint.

Scheduling under (m, k)-firm constraint

The (m, k)-firm model was first proposed by Hamdaoui and Ramanathan in order to precisely characterize the timing constraints required by certain kinds of applications [HAM 94]. It allows the specification of the guarantee level required by real-time applications tolerating deadline miss of certain instances of tasks or messages. More specifically, in this chapter a task or a message τ i is said to have (m i , k i )-firm deadlines if at least m i out of any k i consecutive instances must meet their deadlines and if the schedulability analysis of a set of tasks or messages subject to such (m, k)-firm constraints must furnish a deterministic guarantee. Note that, m i = k i = 1 means that each instance of τ i is constrained by a firm deadline. Initially, this technique was introduced to deal with overloading in real-time message stream handling, but it was soon seen that it could be used in real-time control applications [RAM 99]. Two problems must be solved for such constraint specifications :

-scheduling policy : how to schedule a set of tasks or messages subject to (m, k)firm;

-schedulability analysis : for a given scheduling policy, how to guarantee that the constraints are satisfied.

The main solutions to these problems are briefly described in the following.

Two classes of scheduling policies that were developed to take into account the (m, k)-firm constraints were studied : dynamic scheduling and static scheduling.

In the following, we consider a set of tasks or message streams τ i , each of them being defined by -C i , the largest time needed by the instances of τ i to complete the task instance execution or the message instance transmission; -D i , the relative deadline of τ i , supposed to be the same for each instance; -and, when τ i is periodic or sporadic, its period or the minimum inter-arrival h i ; -m i and k i , the parameters of the (m, k)-firm constraint imposed to τ i ; -the (m i , k i )-pattern, Π i defined as the sequence Π i (0), Π i (1), .., Π i (k -1) where Π i (j) = 1 indicates that the (j + n.k) th (n ≥ 0)) instance of τ i has to meet its deadline, Π i (j) = 0 indicates that it is not mandatory that the (j + n.k) th instance of τ i meets its deadline, and consequently,

n +ki -1 j =n Π i (j) = m i for n > 0.

Dynamic scheduling policy under (m, k)-firm constraints

In [HAM 95], the (Distance Based Priority DBP) algorithm is proposed for nonpre-emptive tasks. It implements a dynamic scheduling that is based, at each scheduling point (e.g., arrival instant or departure instant of a task instance), on the distance to a failure state of each task or message. The failure of τ i is defined as the situation where more than k im i instances among the k i last ones have missed their deadline. The highest priority is given to the task that has the lowest distance to its failure. A FIFO strategy is applied when the distance to the failure is the same for several tasks. The schedulability analysis, based on Markov chain, proposed in [HAM 95] provides a probabilistic guarantee. Further studies have been proposed for improving this approach. In particular, in [LI 06], a sufficient condition is specified for a set of periodic or sporadic messages, scheduled using DBP and (Earliest Deadline First EDF).

Static scheduling policy under (m, k)-firm constraints and schedulability issue

If these dynamic policies provide a good quality of service for a set of streams, they appear quite costly in the context of control applications sharing processors or network resources. To deal with such applications, [RAM 99] considered a system composed of several control applications. The controllers are implemented as preemptive tasks running on two processors. When a failure occurs on one processor, all the tasks that were allocated there migrate to the other one, leading to a possible overload situation. In this case, a static scheduling based on (m, k)-firm constraints is proposed. The mandatory instances of each task are scheduled according to the fixed priority of the task, while the lowest priority is given to the optional instances. Given a couple (m i , k i ) for each τ i , the instance number a (a ≥ 0) is mandatory if a = a.m i ki × ki m i . This classification has been improved in [QUA 00] by a global approach that determines on-line the mandatory instances of all the tasks τ i subject to a (m i , k i )-firm constraint. As this problem has been proved NP-hard, a heuristic was proposed. Furthermore, [QUA 00] provides, on the one hand, an algorithm for evaluating of an upper bound of each τ i response time for a "deeply-red" pattern (a "deeply-red" pattern is such that Π i (a) = 1 if 0 ≤ a < m i and Π i (a) = 0 in the other case) and, on the other hand, it demonstrated that if for each task τ i , the response time is less than the deadline for a (m i , k i ) "deeply-red" pattern, each τ i is schedulable for any (m i , k i ) pattern.

Static scheduling under (m, k)-constraints and mechanical words

In [JIA 05], a new method using the properties of the mechanical words is developed for the schedulability analysis of a set of non-pre-emptive tasks under (m i , k i )firm constraints. First, it proved that the static patterns defined in the literature can be characterized in the form of the mechanical words leading to a largely simplified schedulability assessment. Then, by identifying the defaults of these patterns, it proposed a new way, based on a cellular line, to determine the (m i , k i ) pattern of each task τ i . Through intensive simulations, this technique has been demonstrated to achieve an improvement in the schedulable region. Considering α = m i ki , if α is rationale, then the mechanical word whose slope is α is (k i )-periodic; the classification of the instances as mandatory or optional is therefore based on formula (5.1) :

Π i (a) = (a + 1) .αa.α , ∀0 ≤ a < k i .

(5.1)

The upper bound of the response time of a non-pre-emptive task τ i subject to a (m i , k i ) constraint is obtained, assuming that the sequence is convergent, by the limit of R q i when q → ∞. R q i is given by the classical recurrent equation (5.2):

R 0 i = C i R q i = max j > i (C j ) + j < i m j k j R q -1 i h j C j , ( 5.2)
where i > j means that the priority of the task τ i is lower than the priority of task τ j .

If, for each mandatory instance of each task τ i , R q i + C i < D i , then the system is proved to be schedulable.

Let us consider now a set of pre-emptive tasks scheduled using a fixed priority strategy defined by the rate monotonic algorithm (the larger the period is, the smaller the priority is); in [RAM 99] and [JIA 05], it is proved that it is possible to limit the length of the interference interval of a task τ i due to a task of higher priority τ j to the basic period h i (the basic period is the interval between two instances of a task subject to a hard real-time constraint, meaning a (k, k)-firm one). In this case, we first consider a set of intervals associated to the task τ i and defined in (5.3). h j is the basic period of a task τ j . i > j means h j < h i (i.e. the priority of the task τ i is lower than the priority of task τ j ):

S i,j = l k j m j h j , ∀l N | l k j m j h j < h i (5.3) S i = i-1 j =1 S i,j .
Then, the response time of a task may be evaluated by equation (5.4):

n j (t) = m j k j t h j W i (t) = C i + i-1 j =1 n j (t)C j .
(5.4)

If, for each task τ i , min r Si ( W i (r ) r ) ≤ 1, then the (m, k)-firm constraint can be met by all the tasks. This condition is sufficient in general cases. It is necessary and sufficient if the tasks are synchronous (i.e., the first release time of all the tasks starts at the same time, often at t = 0).

Sufficient condition for schedulability assessment under (m, k)-pattern defined by a mechanical word

The computation of the sequence W i for each task τ i , as it is presented in the recurrence relation (5.4), is non-deterministic and it is difficult, if not impossible, to apply it on-line. Therefore, below, we propose a sufficient condition that ensures the schedulability of a set of tasks under (m, k)-firm constraints. We consider a task set (τ 1 , τ 2 , ..., τ n ); these tasks are periodic and their periods, named "basic period" in the following are, respectively, h 1 , h 2 , ..., h n . We assume here that the tasks are scheduled according to a pre-emptive fixed priority policy based on the rate-monotonic algorithm (the larger the basic period is, the lower the priority is) and that the (m, k)-pattern of each task is defined by a mechanical word through equation (5.1):

The (m i , k i )-firm constraint of each task τ i is satisfied if

C i + i-1 j =1 n i,j C j < h i , ∀1 ≤ i ≤ n,
(5.5)

where n i,j = m j kj hi hj .

In fact,

i-1 j =1 n i,j C j gives the workload generated by all the tasks whose priority is higher than τ i before instant h i (remember that we are dealing with the special case where

h 1 < h 2 • • • < h n ). So it is clear that the deadline is met for τ i if the total workload C i + i-1 j =1 n i,j C j can be finished within [0, h i ].
Note that the above schedulability condition is sufficient and necessary when the basic period of a task is a multiple of the basic period of all the tasks with higher priority. In the other cases, it degenerates to a sufficient condition.

Systematic dropping policy in control applications

This chapter introduces an approach based on the (m, k)-firm model in order to schedule a set of tasks or messages sharing a common resource. The proposed scheduling principles can be seen as a particular case of the period adjustment technique. More specifically we consider that the period of activities sharing a resource (tasks implementing the control law or samples transmitted by a sensor on a network) can be chosen among a limited number of multiples of the basic sampling period. For example, if the basic period for sampling the plant state is h i and if the (m i , k i )pattern, Π i of an activity τ i (task or message) is Π i = [10100110], then, the actual period will be h i or 2.h i or 3.h i . In fact, in this chapter, we will consider that each optional instance of τ i is dropped systematically.

As introduced in [SET 96] and improved in [EKE 00], the determination of (m i , k i )-pattern, Π i for each activity τ i is relevant to an optimization problem for which the cost function is an indicator of the system performance. In the following, we propose a co-design approach dealing with both points : the scheduling parameters and the control parameters. In short, the technique that will be presented in the following sections aims to determine an optimal configuration, or more exactly one that is suboptimal in practice, of m i , k i , Π i for each activity τ i and of the gain γ i of the controller implemented by the task.

Stability analysis of a multidimensional system

The purpose of this section is to present how to guarantee at least the stability condition of control systems. In fact, we are interested by systems whose structure is presented in figure 5.2.

Generic model

The plant is defined as a linear continuous-time system whose evolution is modeled by equation (5.6):

dx = Axdt + Budt + dv c , (5.6)
where x is the state vector of the system and u is the output of the controller x ∈ R p , u ∈ R q . The parameters A and B are two matrices whose dimensions are, respectively, (p, p) and (p, q). v c is a white noise whose covariance is R c dt. The dimension of the constant matrix R c is (p, p).

The plant state is sampled periodically; the sampling period is noted h. The jth sampled plant state vector transmitted at times jh is consumed by the linear discrete controller defined in equation (5.7); it is noted x j in the following:

u j = -Lx j i = 0, 1, 2.... (5.7)
We assume that this controller is implemented as a task. As the purpose is to share the processor among several controller tasks and therefore to decrease the processor bandwidth consumed by this task, in case of an overload situation, several of its instances are rejected according to a (m, k)-firm model and under the constraint that the stability of the system has to be ensured.

Each time an instance is executed, it produces a command u j . This command is maintained until a new command is produced. The use of the (Zero-Order Holder ZOH) and the periodicity of the systematic instances dropping defined by the (m, k)pattern provide a discrete time behavior of the system modeled by equation (5.8) :

x j +1 = Φ j x j + Γ j u j + v j , j = 0, 1, 2..., (5.8)
where Φ j and Γ j are given by

Φ j = e Afj Γ j = fj h 0 e As dsB.
The value of f j is the distance, in terms of the number of basic sampling periods, between two updates of the command. For example, if, for a given controller task, the

(m, k)-pattern is Π = [1001000], we get f 0 = 3 and f 1 = 4.
v j is a discrete white noise with a zero mean and

Ev j v T j = R 1 (f j h) = fj h 0 e
As R c e A T s ds.

(5.9)

As formerly written, the task instances are periodically rejected according to a given (m, k)-pattern, f j + f j +1 + f j +m -1 = k and f j = f j +m , ∀j > 0, the period of the system defined in (5.8) is m, meaning also Φ j = Φ j +m , Γ j = Γ j +m .

Example of multidimensional system

As an example, we propose to study the control of a cart that can move in one direction guided by a rail. The purpose of the control strategy is to drive the cart to a given position. We suppose that the friction parameters are negligible.

An initial reference position is defined and the position of the cart, d is measured with regard to this reference. ḋ notes the speed of the cart. Therefore, the state vector of the plant is x T = [d, ḋ]. The parameters p and q of the generic model are, respectively, equal to 2 and 1. The simplified model of the plant is given by the following equation (5.10):

d = -k 1 ḋ + k 2 u.
(5.10)

An identification of the system furnished the value of the parameters k 1 and k 2 :

k 1 = 12.6559 and k 2 = 1.9243
The continuous model of the system according to the state space representation is given by the generic equation (5.6). In this example, A = 0 1 0 -k 1 , B = 0 k 2 and v c = 0. The output of the cart is periodically sampled (period h). The closed-loop model is given by equation (5.11) :

x j +1 = Φ (h) x j + Γ (h) u j , (5.11) with Φ (h) = 1 1-e -k 1 h k1 0 e -k1 h and Γ (h) = k2 k1 h -1-e -k 1 h k1 1 -e -k1 h .
The command elaborated by the controller is

u j = L(x ref -x j ), (5.12)
where L is the gain L = k c k d and x ref is the targeted reference defined as

x ref = d ref 0 T (d ref is
the reference of the position on the rail where the cart has to stop).

Sampling period definition

The basic sampling period h basic is determined according to the empirical "rule of thumb" formulated in [ÅST 97] : 0.2 < ω 0 < 0.6, where ω 0 is the natural frequency of the system (ω 0 = 20, for the cart considered in this example). The period h basic has to be chosen in [0.01, 0.03]. A study of this system shows that its performance in terms of rise time and overshot is optimal for h basic = 0.01s. So we will use this value as the basic sampling period.

Controller parameters

We note k c,0.01 and k d,0.01 , the parameters of the controller obtained for a basic sampling period h basic = 0.01s. Their values are evaluated by solving the Linear Quadratic Regulator (LQR) problem proposed in [ÅST 97]. The final results are k c,0.01 = 121 and k d,0.01 = 6.5.

Stability condition

The configuration of a dropping policy based on the (m, k)-firm model needs to identify the values of k, m, and the (m, k)-pattern. The first problem to solve concerns the stability of the system, and the question is which parameter of the constraint is critical for ensuring this property. This identification relies on the intuitive idea that is : if a system is stable for a given (1, k)-firm policy, it will be stable for any dropping policy based on a (m, k)-firm. Therefore, we propose to evaluate, for each task, k max , the greatest value of k, so that the system is guaranteed to be stable for each constraint (m, k) with k ≤ k max and m ≤ k.

The analysis of equation (5.8), shows that on the one hand, a system subject to a (m, k)-firm constraint can be considered as a system with sampling periods varying according to a regular form specified by the (m, k)-pattern and, on the other hand, a system subject to a (1, k)-firm constraint is equivalent to a system controlled under a sampling period equal to k times the basic period. Therefore, the determination of k max is equivalent to the determination of the maximal value of h that ensures the system stability.

In particular, if we study the example proposed in section 5.3.2, let us note Ψ (h) = Φ (h) -Γ (h) L, given by

Ψ (h) = 1 -k c k2 k1 h -1-e -k 1 h k1 1-e -k 1 h k1 -k d k2 k1 h c -1-e -k 1 h h k c k2 k1 1 -e -k1 h e -k1 h -k d k2 k1 1 -e -k1 h
.

By applying the Jury criteria [FRE 63], the following three conditions provide a necessary and sufficient condition for the system stability :

1. a 2 < 1, 2. a 2 > a 1 -1, 3. a 2 > -a 1 -1,
where

a 1 = Ψ 1,1 Ψ 2,2 -Ψ 1,2 Ψ 2,1
, a 2 = -Ψ 1,1 -Ψ 2,2 ; Ψ i,j notes the element placed in line i, column j of the matrix Ψ; a 1 and a 2 are expressed according to the controller parameters (k c , k d ) and the sampling period h. This defines a domain of admissible t-uple (k c , k d , h).

In practice, the determination of the greatest admissible value of the sampling period starts by fixing k d = k d,0.01 , which is the value obtained for k d when h = h basic = 0.01s (the basic period). Then we study k c according to h under the following constraints deduced from Jury's conditions.

So, we need to analyze the function that expresses the maximal value of h for each value of k c , with k d being fixed at the value k d,0.01 . In fact, we study the function k cM ax (h), which is evaluated by

k cM ax (h) = k c1 (h) if k c1 (h) < k cLim (h) k c2 (h) if k c1 (h) ≥ k cLim (h) ,
where

k cLim (h) = 4k 1 e k1 h hk 2 (e k1 h -1) k c1 (h) = 2k 1 k 1 + k 1 e k1 h + k 2 k d -k 2 k d e k1 h k 2 (2 -2e k1 h + hk 1 + hk 1 e k1 h ) k c2 (h) = k 1 (k 1 + k 2 k d ) e k1 h -1 k 2 (-1 -hk 1 + e k1 h ) ,
and we obtain the stability region in a space (h, k c ). This region, for the example proposed in 5.3.2, is identified by the gray color in figure 5.3. It represents, for each point k c , all the admissible values of h. For example, for k c = k c,0.01 , the maximal value of h, h max , ensuring the stability is given by the abscissa of the point P and h can be chosen in the interval [0.01, h max ].

As mentioned before, the period adjustment based on a (m, k)-firm model is equivalent to a regular sequence of time intervals between to consecutive samples, specified by the (m, k)-pattern; each time interval is a multiple of the basic period. Therefore, for the cart system, k max is determined by hm a x h b a s ic and the maximal sampling period, ensuring the stability and corresponding to a (1, k max ) constraint, is equal to k max h basic .

Optimized control and scheduling co-design

Once the stability of the system ensured, there is a further step needed to deal with the optimization issue. So, to do this, we first define a cost function used for determining an optimal control (section 5.4.1) and, then, we identify the global optimization problem for a set of closed loops where the algorithms implementing the control laws share one processor (section 5.4.2). Finally, the proposed approach is illustrated by a case study in section 5.4.3.

The optimization approach relies on two phases :

-The first is done off-line. For each task, τ i , a value of k i ensuring the stability of the system is fixed according to the method described in 5.3.3. For each value of m i,j such that 1 ≤ m i,j ≤ k i , a (m i,j , k i )-pattern Π i,j is defined based on the mechanical words technique (see section 5.2, page 192). Then, for each pattern Π i,j , the cost function of the system is evaluated. Such a function is proposed in section 5.4.1. -The second phase is done by the task handler as illustrated in figure 5.1. It concerns the global optimization of the system. For each working mode, the task handler has to configure the (m, k)-firm constraints and the scheduling parameters of each task implementing the control law of each system and sharing the same processor.

Optimal control and individual cost function

An indicator of the closed-loop performance can be given, among others, by the Least Quadratic (LQ) cost function , which provides a form of "cumulative cost" for an infinite horizon. Applied to a system described by equation (5.6), it is defined by the following formula :

J ∞ = lim N →∞ 1 N E( N 0 x T (t)Qx(t) + u T (t)Ru(t)dt),
where Q and R are two matrices that respectively weigh the state and the input of the plant.

For a task τ i that implements the ith controller, given k i such that the stability is ensured, J ∞ i is the cost function to minimize. We consider all the numbers of mandatory instances m i (1 ≤ m i ≤ k i ), assuming that the corresponding patterns Π i are defined using the mechanical words approach; for each possible value of m i and Π i we determine the optimal control law, in fact the gain of the controller, which minimizes the cost function. As the intervals between two instances are time varying, according to the pattern, the optimal control law is described by a sequence of gain, L i,p for p = 1, 2, ..., m i . For example, let us consider k i = 10, for m i = 3; the (m i , k i )-pattern Π i is equal to [1001001000], and we need to determine three values of the gain : L i,1 , L i,2 , L i,3 to apply using the control law when producing the command to the actuator, respectively, at the first, second, and third mandatory instances.

We consider the discrete time-varying model of the plant presented in (5.8). We denote by h i the basic period of the ith plant controller.

The following discrete form of J ∞ i is evaluated for each possible value of m i (1 ≤ m i,j ≤ k i ) and therefore for the corresponding sequences (f i,0 , f i,1 , ..., f i,m i , j -1 ) :

J i (m i,j ) = 1 m i,j H i ki m i , j H i k i h i p=0 x T i,p Q i,p x i,p + 2x T i,p M i,p u i,p + u T i,p R i,p u i,p + 1 m i,j H i ki ⎛ ⎜ ⎝E x T m i H i k i h i Q i0 x m i , j H i k i h i + m i , j H i k i h i p=0 J i,p ⎞ ⎟ ⎠ , (5.13)
where H i is the time horizon of the ith plant, under the condition

m i , j H i ki hi
N * , x i,p is the plant state measured at the pth sample and u i,p the corresponding command sent to the actuator,

Q i,p = fi , p hi 0 Φ T i (t)QΦ i (t)dt, M i,p = fi , p hi 0 Φ T i (t)QΓ i (t)dt, R i,p = fi , p hi 0 (Γ T i (t)QΓ i (t) + R i )dt, J i,p = tr(Q fi , p hi 0
R ic (t)dt with R ic , the covariance of v i , and Φ i (t) = e A i t and Γ i (t) = t 0 e A i t dtB i . The optimal control law that minimizes the cost function 5.13 is given by [ÅST 97] as u i,p = -L i,p x i,p , p = 0, 1, ...,

(5.14)

where

L i,p = Γ T i,p S i,p+1 Γ i,p + R i,p -1 Γ T i,p S i,p+1 Φ i,p + M T i,p .
(5.15) S i,p is obtained from the recurrent equation

S i,m H i k i = Q 0 S i,l = Φ T i,l S i,l+1 Φ i,l + Q i,l -Γ T i,l S i,l+1 Φ i,l + M T i,l T Γ T i,l S i,l+1 Γ i,l + R i,l -1 Γ T i,l S i,l+1 Φ i,l + M i,l for 0 ≤ l ≤ m i,j H i,j k i h i .
(5.16)

Taking into account the periodicity of the pattern, Φ i,p = Φ i,p+m i , j and Γ i,p = Γ i,p+m i , j . Consequently, the solution of equation (5.16) is also periodic with a period m i,j when calculated on a sufficiently long time horizon [BIT 91] i.e., S i,l = S i,l+m i , j . Then, the gain of the controller L i,p is designed using the steady-state solution of the Ricatti equation (5.15), and its solution is also periodic :

L i,p = l i,p+m i , j .
With this computation, it is possible, for a given (m i,j , k i )-pattern, to determine the best sequence of L i,p that allows us to partially compensate the task instance dropouts.

When time goes to infinity, (lim H i → ∞), the influence from the initial condition decreases and because S i,l = S i,l+m i , j , equation (5.13) may be written as

J ∞ i (m i,j ) = 1 m i,j h i m i , j -1 p=0 trS i,p+1 R i,j + m i , j -1 p=0 J i,p .
(5.17)

Global optimization

Let us now consider the problem introduced at the beginning of section 5.4. As mentioned before, the problem is the global optimization of a set of controllers deployed as a set of tasks sharing the same processor. In the last section (5.4.1), we demonstrated, for a given (m, k)-firm constraint and a given (m, k)-pattern, how to determine the sequence of controller gains that compensate for the task instance dropout between two mandatory instances; this set of gains is identified in order to minimize a cost function that represents a cumulative cost and is derived from the LQ function. Using this evaluation, realized off-line, each task τ i that may be activated in one of the possible working modes, is characterized by several attributes :

-its basic period h i and its priority P i , -the execution time of the task C i , -the parameter k i that ensures the stability of the system under a period k i h i , -the number n i of values m i,j such that a systematic dropping of the task instances can be done following the (m i,j , k i )-firm constraint :

-for each value m i,j :

-the value of m i,j , -the (m i,j , k i ) pattern, Π i,j ; we recall that it is defined thanks to the mechanical words, -the list of gains to apply at each instance of the task : L i,1 , L i,2 , ...,L i,m i , j -J i,j the value of the cost function obtained by using these gains repeatedly on each interval [pk i , (p + 1) k i ] for p ≥ 0.

This information is used on-line for the resolution of the global optimization problem. As soon as a new working mode is defined, the task handler knows which plant needs to be controlled and by which controller; at this point, it has to choose, for each active controller, and therefore for each corresponding task τ i , what the value of the parameter m i is that has to be applied in order to minimize a global cost function. We denote the number of tasks activated in one working mode by n.

Let us consider a set of tasks τ i , 1 ≤ i ≤ n, described by the parameters given above; the global optimization problem consists in determining (s i,1 , s i,2 , .., s i,ni ) for each task τ i that minimizes

n i=1 n i j =1
(-s i,j J i,j ),

(5.18) with s i,j {0, 1},

n i j =1 s i,j = 1, i = 1, .., n.
Under the schedulability constraint that has to be met by all tasks τ i , i = 1, .., n, this condition is equivalent to the one formulated in equation (5.5) :

C i + i-1 j =1 ⎡ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ n j p=1 s j,p m j,p k j h i h j ⎤ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ C j < h i .
(5.19)

This optimization problem can be seen as a Multiple-Choice, Multiple Dimension Knapsack (MMKP) problem [MAR 90] that has been proved to be NP-hard. Therefore, solving this problem on-line requires developing an heuristic algorithm ensuring that it can provide a tight sub-optimal solution. In the following, we apply a slightly modified version of the computationally cheaper algorithm HEU proposed in [KHA 02]. For our optimization problem, the proposed algorithm is

Case study

In this section, we apply the method presented above to a case study. Let us consider four cart systems, cart 1 , cart 2 , cart 3 , and cart 4 , similar to the one presented in section 5.3.2. The control of these cart systems can be active or not depending on the Algorithm 5.1: Modified computationally cheaper heuristic 1) to find a feasible solution first, that is to say, select m i,j for each τ i while satisfying the constraints given in (5.19); for this purpose, the algorithm HEU is modified by always setting the value of m i,j of each task τ i to be equal to 1 (if the solution is infeasible in this case, no other solution will be feasible);

2) and then to iteratively improve the solution by replacing, for eachτ i , the current value of m i,j by another value corresponding to a better performance while keeping the constraints (5.19) satisfied; if no such solution can be found, the algorithm tries an iterative improvement of the solution which; a) first replaces m i,j for one task τ i , which is not schedulable with the current value of m i,j ; b) and then replace the value of m i ,j for all tasks τ i ( i = i) by a value providing a worse performance; the original algorithm HEU tries to find, after the first step, a better solution requiring less resource consumption which, however, does not exist in our model, therefore, this property also help us to delete an unprofitable search procedure in HEU;

3) The iteration finishes when no other feasible solution can be found;

working mode chosen by the supervisor (see figure 5.1). The tasks implementing each controller share the same processor.

A Matlab/Simulink model of the system is specified. The scheduling policy is implemented using the toolbox TrueTime [CER 03]. The system is then analyzed by tracing an indicator of the control performance during the simulation of this model running on a given scenario. This indicator is given, for each controlled cart system, by function (5.20), which is evaluated at each simulation step:

J i (t) = t 0 x T i (s) Q i x i (s) + u T i (s) R i u i (s) ds, ( 5.20)
where Q i = 1 0 0 0 and R i = 0.00006 for each cart i , i = 1, 2, 3, 4.

Furthermore, we can observe the state of each task instance during the simulation (running, pre-empted, not activated).

Plants and controllers

The generic continuous model of the cart system, cart i for 1 ≤ i ≤ 4 (see equation 5.6) is given by dx = 0 1 0 -11.4662

M i xdt + 0 1.7434 M i udt + dv c , (5.21)
where M i is the mass of cart i :

M 1 = 1.5, M 2 = 1.2, M 3 = 0.9, M 4 = 0.6.
The controller of each cart i is noted as controller i , the task which implements the controller i is τ i , and its basic period is h i :

h 1 = 0.007, h 2 = 0.0085, h 3 = 0.01, h 4 = 0.0115.

Scheduling parameters

The tasks τ i are scheduled according to a fixed pre-emptive priority policy under an implicit deadline constraint for their mandatory instances (D i = h i ). The priorities of the tasks are defined thanks to their basic period (the larger the period is, the lower the priority is). So, in any working mode, there is the following relation between the task priorities : priority(τ 1 ) > priority(τ 2 ) > priority(τ 3 ) > priority(τ 4 )

Let us now fix the parameters of the constraint (m, k)-firm for each task. The value of the parameter k i is defined in order to ensure the stability of the system under a period equal to k i h i . In this case study, we identified the following value of k i :

k 1 = 5, k 2 = 8, k 3 = 10, k 4 = 1.
We consider, in the considered experiments, that the four tasks have the same execution time :

C 1 = C 2 = C 3 = C 4 = 3 ms
and that the execution time of the task handler is C th = 2, 5 ms. Furthermore, its priority is higher in the system.

Optimal controller

The controller of cart i is defined by u i = L i x i , where the gain L i is evaluated for each interval between two consecutive mandatory instances according to the (m i , k i )firm strategy used for this plant. As detailed in section 5.4.2, the value of the gain is calculated in order to optimize the control performance during this interval. The cost function, to minimize, in this case study is the discrete form of

J i = lim N →∞ N 0 x T (t)Q i x(t) + u T (t)R i u(t) dt, (5.22)
where Q i = 1 0 0 0 and R i = 0.00006 for each cart i , i = 1, 2, 3, 4.

Simulation scenario

The system is observed along a scenario that introduces three working modes and two types of working mode switchings:

-at time t = 0s, the first two cart systems (cart 1 and cart 2 ) are to be controlled; therefore, only two tasks are running : τ 1 and τ 2 implementing, respectively, the Controller 1 and Controller 2 ; the set of tasks to be scheduled is {τ 1 , τ 2 }; -at time t = 1s, the fourth cart system (cart 4 ) has to be controlled; so, τ 4 implementing the Controller 4 is activated; the set of tasks to be scheduled is {τ 1 , τ 2 , τ 4 }; -at time t = 2s, the third cart system (cart 3 ) has to be controlled; so, τ 3 implementing the Controller 3 is activated; the set of tasks to be scheduled is {τ 1 , τ 2 , τ 3 , τ 4 }.

Two pre-emptive-fixed priority scheduling policies were modeled:

-Hard real-time constraints. We consider that all the task instances are mandatory; in this case, the gain of each controller is constant and determined in order to optimize the cost function (5.22) for the basic sampling period of each system.

-Adaptive system. In this case, we implement a systematic dropout of the nonmandatory instances according to the (m, k)-firm constraints specified for each task; the gain of the controller is adapted to each inter-sample interval length in order to optimize the performance of each system; the value of k is constant for a given system in each working mode, while the value of m is evaluated for each system at the beginning of each working mode in order to optimize the global cost function proposed in (5.18) under the schedulability condition (5.19).

Simulation results for hard real-time constraints

The control performance of each system as well as the evolution of the task state are illustrated in figures 5.4-5.6.

-In the interval [0, 1[, two tasks are periodically activated: τ 1 , with the period h 1 = 0.007 s, and τ 2 , with the period h 2 = 0.0085 s; all the instances of both tasks meet their deadline.

-At time t 1 = 1 s, the supervisor decides to include the control of cart 4 leading to the activation of the task τ 4 ; its period is h 4 = 0.0115 s; so, it will be activated successively at 1 s, 1.0015 s, 1.013 s, 1.0245 s, etc.; we can observe in figure 5.4 that no instance of τ 4 meets its deadline; the starting time of several instances is delayed and the completion of all the instances are after their deadline; as the priorities of τ 1 and τ 2 are higher than that of τ 4 , the activation of τ 4 has no impact on the scheduling of the two other tasks that meet always their deadlines; -At time t 2 = 2 s, the supervisor includes the control of cart 3 leading to the activation of the task τ 3 at time 2 s, 2.0115 s, 2.023 s, etc.; we can observe in figure 5.5, that no instance of this new task meets its deadline; furthermore, the interference of the three tasks of higher priority, τ 1 , τ 2 , and τ 3 , makes the processor unavailable for the task τ 4 , leading all the instances of this task to fail to run. An analysis of figure 5.6 shows how the performance of the system varies, as evaluated by function (5.20). We can note that for cart 4 , the performance is acceptable between t = 1 s, up to t = 2 s, which is before the activation of task τ 3 . Then the performance of cart 4 diverges. This is due to the interference of tasks τ 1 , τ 2 , and τ 3 , whose priorities are higher than that of τ 4 . As mentioned before, this task will never run. Finally, the performance of cart 3 is always acceptable despite the instances of the corresponding control task τ 3 never meeting their deadline.

Simulation results for (m, k)-firm constraints

The control performance of each system as well as the evolution of the task state are illustrated in the figures 5.7-5.9.

Time (s) τ τ 1 τ 2 τ 3 τ 4
Arrival time of task instances that meet their deadline Arrival time of task instances that do not meet their deadline -In the interval [0, 1[, two tasks are activated periodically: τ 1 , with the period h 1 = 0.007 s, and τ 2 , with the period h 2 = 0.0085; these tasks are schedulable under hard real-time constraints as seen in section 5.4.3.5; moreover, in this working mode, the global cost function is optimized for m 1 = k 1 and m 2 = k 2 , so all the instances of τ 1 and τ 2 are mandatory.

-At time t 1 = 1 s, the supervisor decides to include the control of cart 4 leading to the activation of task τ 4 ; in figure 5.7, at this time, the task handler is activated; as its priority is higher in the system, its completion is at time t = t 1 + C th = 1.0.0025 s; at time t 1 , the optimization of the global cost function (5.18), realized by the task handler, furnishes the value of m 1 = 5 and m 2 = 4 providing the rules for the dropping policy: (5, 5)-firm for τ 1 and (4, 8)-firm for τ 2 under the (m 2 , k 2 )-pattern Π 2 = [10101010]; as k 4 = 1, all the instances of τ 4 are mandatory; figure 5.7 shows that all the mandatory instances of τ 1 and τ 2 meet their deadline, while no instance of τ 4 does; nevertheless, all its instances run to completion, under a delayed starting time and delayed completion time.

-At time t 2 = 2 s, the supervisor includes the control of cart 3 , so a new working mode that integrates the former tasks τ 1 , τ 2 , and τ 4 and the new task τ 3 is started; the task handler has to redefine the optimal configuration of the task activation rules; in this case, function (5.18) is minimized for the following (m i , k i )-firm constraints:

-

(m 1 , k 1 ) = (2, 5) and Π 1 = [10100], -(m 2 , k 2 ) = (4, 8) and Π 1 = [10101010], -(m 3 , k 3 ) = (3, 10) and Π 1 = [1001001000], -(m 4 , k 4 ) = (1, 1
) . We can observe, in figure 5.8, that the two first instances of τ 4 and the first instance of τ 3 , activated at the beginning of this new working mode, do not meet their deadline because of a transient overload due to the execution of the task handler; after that point, all the mandatory instances of the four tasks meet their deadline. Figure 5.9 illustrates the evolution of the cost function, provided by formula (5.20). For each cart system, the performance becomes quickly stable and remains constant in each working mode.

The optimization algorithm of the global cost function (5.18) under the schedulability constraints (5.19) for a set of control tasks sharing the same processor allows for applying a best dropout policy of several well-identified instances for each tasks; the consequence is a wider availability of the processor and the possibility for each task to run its mandatory instances to completion before the deadline (the relative deadline is the basic period of each task). Furthermore, the controller itself is optimized and an adaptive gain suited to the (m i , k i )-pattern is defined.

Plant-state-triggered control and scheduling adaptation and optimization

Let us consider in this section, more precisely, the different situations of the states of the plants that may be controlled :

-the plant is not controlled; this situation occurs when the plant does not exist for the overall system (plant controlled only during certain time interval, plant deactivated because its output is out of a given domain); -it is controlled and its state is a steady state; -it is controlled, but when this control is just activated, its state is a transient state.

We have to take into account the last two cases and, in particular, we must adapt the cost functions in order to deal with both situations. For this purpose, we propose taking into consideration, depending on the situation of the plant, an infinite-horizon or a finite-horizon cost function in order to find the optimal configuration of each m i and of each controller gain L i .

Closed-loop stability of switching systems

A change in the value of m i , for a given k i , produces a sampling period variation, and then we consider a Discrete Time Switched System (DTSS) description. To adapt the control law parameters to this variation, we use the design process presented in section 5.4.1. But, as was shown in [SCH 02], controllers designed with optimal-LQ techniques may suffer from instability under certain switching sequences, i.e., when the sampling period changes. Because of this undesirable result, [SCH 02] adopts a linear matrix inequalities (LMI) framework to design stable optimal controllers. We propose using a LMI framework to find a common quadratic Lyapunov function (CQLF); then the asymptotic stability is guaranteed for any (m i , k i )-firm sequence for each plant, proving the stability of the control.

Firstly, for a fixed control task τ i , k i , we consider each possible value of the number of mandatory instances, m i . For each of these, we compute the corresponding m i controller parameters

L i,m i = L 0 i,m i , L 1 i,m i , ..., L m i -1
i,m i by using equation (5.15).

Secondly, we consider, for the control task τ i , the set of open-loop discrete time models (5.6), Θ i = {(Φ i,1 ) , (Φ i,2 ) , ..., (Φ i,ki )} and evaluate the k i periods, taking into account the possible interruptions in a planned sequence at any time.

By using the elements in both sets L i,m i and Θ i , we can establish a new set of m i .k i closed-loop models (5.7) without noise, A l i,p = Φ i,l + Γ i,l L p m i , where l varies between 1 and k i ((Φ i,l , Γ i,l ) Θ i ) and p between 0 and m i -1 ((L p i L i,m i )).

In order to prove the stability of the DTTS [LIB 99], for k i and each possible value of m i , we need to find a CQLF for the set of matrices A i n,p , where n = 1, ..., k i and p = 0, ..., m i-1 . Then, we can define a set of inequalities :

A i n,p T P A i n,p -P < 0, ∀n = 1, ..., k i , ∀p = 0, ..., m i-1 .
(5.23)

Note that the identification of a CQLF is a sufficient condition. In order to solve the problem and find the matrix P = P T > 0, we use the LMI toolbox from the Matlab tool.

On-line plant state detection

As mentioned in the previous section, three plant states are identified : nonactivated plant, steady plant state (or near), and transient plant state. Reaching or leaving the first situation for a plant modifies the value of the number of control tasks n. The dead-band approach presented in [OTA 02] is used to distinguish the steady and the transient states of a plant. Each controlled plant has a state, which asymptotically tracks the reference r, and is supervised by the supervision task. Let y i be the state of the plant i. y i can be a subset of the plant state vector x i defined in section 5.3.1. For instance, taking the previously studied cart system with x = [position speed] , if we want the position to follow the reference position r, the variable position is then the parameter of the interest, and we can define y = [1 0] * x. The following condition on two successive samples (n T e and (n + 1) N H ones) is set up :

|y i (h i + Nd i ) -y i (nh i )| < min {δ |y (nh i )| , th} ,
where th is a threshold to prevent false identifications due to noises, δ is a parameter to adjust for each plant, h i is the detection period implemented by the supervision task for plant i. If the condition is verified, then the plant is considered to be in steady state; otherwise, it is in a transient state. The advantage of this plant state detection mechanism is that it depends on the actual evolution and it detects, in the same way, reference changes or/and non-modeled perturbations.

Global optimization of control tasks taking into account the plant state

As in section 5.4, we deal with several working modes where, in each mode, a number of control tasks have to share one processor. In this section, we take into account that the working modes are identified, on the one hand, by a number of plants to be controlled, meaning, a number of given control tasks and, on the other hand, by the situation in which the plant is found. This situation corresponds to the two abovementioned cases: the plant is in a transient state (due to a new reference or noises) or is in steady state. Intuitively, the constraints, in terms of performances, that have to be applied to the control are not the same for these two situations. Therefore, we have to consider a more complex cost function than the one presented in section 5.4.

We suppose that the value k i of each τ i has been carefully chosen and is constant during the execution of application. The value of m i has to be chosen in [1..k i ] on-line by the task handler. We note n the number of tasks activated in one working mode. For each control task τ i , each possible value of m i is associated with two values G i,m i and G i,m i corresponding to the control performance, respectively, in a transient situation and in a steady one. Supposing that a lower value of G i,m i or G i,m i represents a better control performance, in the event of a situation change of the plant states, the aim of the task handler is to find, for each τ i , a value so that the sum of G i,m i or G i,m i (according to the situation into which the plants fall) for j [1 . . . k i ] and i [1 . . . n] is minimized the subject to the task schedulability condition 5.19. This is formally formulated as the following optimization problem.

Considering in a set of tasks τ i , 1 ≤ i ≤ n, described by h i , their basic period (considered as their relative deadline, i.e., D i = h i ), C i , their worst case execution time, k i the parameter of their (m, k)-constraint, n i , the number, and the list of possible values for the parameter m in the (m, k) constraint; the global optimization problem consists in determining (s i,1 , s i,2 , . . . , s i,ni ) for each task τ i that minimizes n i=1 n i j =1 (s i,,j G i,,j I + s i,,j G i,,j F ), with s i,,j {0, 1},

n i j =1
s i,,j = 1, i = 1, . . . , n and such that condition (5.19) is verified. The values of G i,,j and G i,,j have to reflect the performance offered by each solution. We identified two ways for defining the performance indicator.

-In the first case, G i,,j is defined on a finite horizon by formula (5.13) while G i,,j is evaluated on an infinite horizon using (5.17):

G i,,j = J i (m i,j ) G i,,j = J ∞ i (m i,j ).
(5.24)

We have to note that the optimization problem is to minimize the overall cost of the application. However, the sub-systems with lower costs may suffer from greater control performance degradation due to a low value of m i . That is to say, the task handler maintains the value of each m i as high as possible for the sub-systems with greater costs by reducing the value of m i for the sub-systems with lower costs.

-The second solution is concerned by a cost that represents performance degradation :

G i,j = J i (m i,j ) -J i (k i ) J i (k i ) G i,,j = J ∞ i (m i,j ) -J ∞ i (k i ) J ∞ i (k i ) , ( 5.25)
where J i (x) and J ∞ i (x) are defined, respectively, by functions (5.13) and (5.17). In this case, the control performance criteria avoid the problem given for the first solution presented. The control performance degradation of each sub-system is treated equally. On the other hand, the overall cost of application may not be optimal. So, the choice of control performance representation should be identified according to the application requirements.

In both cases, the time horizon H i for the finite-horizon cost function is an important design parameter, which directly affects the overall control performance, and needs to be carefully chosen. We propose opting for H i as the settling time (defined approximately as three times the rise time). Moreover, the off-line computation of (5.25) is done by considering the typical values of the reference values and by neglecting noise.

As in the solution presented in section 5.4.2, the optimization problem results from the MMKP. To solve this problem on-line, we also propose using the heuristic algorithm (HEU) presented in [KHA 02].

Case study

In this section, we illustrate the scheduling approach presented above by studying the control of four plants. P lant 1 (resp. P lant 2 , P lant 3 , P lant 4 ) corresponds to a harmonic oscillator system, (resp. to a cart system, a pendulum and an inverted pendulum). The controller of P lant i is denoted by Controller i . Each plant is modeled by the differential equation (5.6) whose parameters are given in the table 5.1. The controller of the P lant i is defined by equation (5.7).

The rise time specifications of each plant are, respectively, 0.2, 0.2, 0.3, and 0.5. Then, the basic sampling periods are related to rise time specifications, i.e., h 1 = 0.02s for P lant 1 , h 2 = 0.02s for P lant 2 , h 3 = 0.03s for P lant 3 , and h 4 = 0.05s for P lant 4 .

We suppose that the first state variable in vector x of each plant is the variable supervised by the supervision component. In other words, the controller tries to keep it tracking the plant state reference asymptotically. The step response target for the cart (P lant 2 ) is an over-damped response, while for the others they are under-damped, being the damping coefficient greater than 0.6 (overshoot < 10%). The gain of the controllers is computed for each possible value of m i,j , according to the approach proposed in 5.4.1. The design weights, which allow the satisfaction of the abovementioned rise time and overshoot, are presented in table 5.2.

Using the LMI control toolbox of Matlab/Simulink tool, the set of inequalities (for the overall set of discrete plants and controllers parameters), has a QCLF, guarantying stability. To allow for fast changes between different (m i,j , k i )-firm constraints at an m i,j adjustment, the controller parameters are calculated off-line and stored in a table.

As applied in section 5.4, to the control task τ i which implements the controller Controller i is assigned the rate-monotonic priority, the task with the largest period has the lowest priority; its execution has no influence on the other tasks. Therefore, no task instance classification will be applied to τ 4 , or in other words, it is executed under (k, k)-firm constraint. Using the approach proposed in section 5.3.3, the value of k i is set to, respectively, k 1 = 6, k 2 = 5, k 3 = 5 and k 4 = 1. The value of m i for the plant τ i may vary within [1..k i ]. The worst case execution time of each task is

C 1 = C 2 = C 3 = C 4 = 9 ms.
The optimal costs as well as the sequence of corresponding gains, associated with the different possible (m i , k i )-firm constraints of each task τ i are evaluated off-line and stored in order to be used on-line by the task handler. Then the Matlab/Simulink model is simulated. The deployment characteristics of the global system, for short, the specific scheduling policy, are done by using TrueTime toolbox [CER 03].

Simulation scenario

The evolution of the scenario is illustrated in figure 5.10. It shows, for each P lant i , if it is controlled or not and, in the first case, the reference that is applied and the output of the plant, respectively, noted in figure Ref i and x i for P lant i . Table 5.3 provides, at each significant instant, the value of m i that is selected by the task handler for each current task. An instant is significant if it leads to a switch between two working modes: a new plant has to be controlled, one plant is no longer activated, one plant goes from steady state to transient state, or a plant reaches its steady state.

These instants are identified on-line by the supervisor.

The sequence of significant instants in the proposed scenario is described below.

-Just before the observation of the system, we suppose that only P lant 1 and P lant 3 are controlled, while the other plants are not activated and not controlled. These two plants are in a steady state. In this case, the system is schedulable under (k 1 , k 1 ) and (k 3 , k 3 ) constraints for τ 1 and τ 3 .

-At time t 0 , P lant 4 is activated and, therefore, the set of tasks to schedule is {τ 1 , τ 3 , τ 4 }; no reference is applied to this new plant. The three plants are in a steady state. The task handler has to find the optimal configuration of m i for this set of tasks and to deduce the corresponding sequence of values for L i , the gain of each controller. For this purpose, it uses the infinite-horizon cost for each plant. The result is m 1 = 4 and m 3 = 5 (we have to note that m 4 has to be always equal to 1.) -A transient state is detected by the supervisor at time t 1 for P lant 1 (occurrence of a new reference) and P lant 4 The task handler looks for an optimal configuration of the (m i , k i ) constraints by taking into account the finite-horizon costs for P lant 1 and P lant 4 and the infinitehorizon cost for P lant 3 . This results in m 1 = 6 and m 3 = 2.

-P lant 2 is activated at time t 2 and the supervisor identifies it is in a steady state while P lant 1 and P lant 4 are still in a transient state. The values of m i defined by the task handler at this time are, respectively, m 1 = 3, m 2 = 1 and m 3 = 2.

-The supervisor detects a steady state for the P lant 1 at time t 3 . The new values evaluated for m i are m 1 = 2, m 2 = 1 and m 3 = 5.

-At time t 4 , the values of m i have to be modified as the supervisor detects a transient state for P lant 2 . Therefore, m 1 = 2, m 2 = 1 and m 3 = 5.

-P lant 3 enters in a transient state at t 5 . The adjustment of the values of m i results in m 1 = 2, m 2 = 1 and m 3 = 5.

-P lant 2 goes from transient to steady state at t 6 . This leads the task handler to readjust the m i parameters, using the infinite-horizon cost for τ 1 and τ 2 and to the finite-horizon cost for τ 3 : m 1 = 2, m 2 = 1, m 3 = 5.

-At t 7 , an inadmissible perturbation enters in P lant 3 whose output reaches π 2 and consequently, this plant is deactivated, thus reducing the number of tasks to 3. At the same time, P lant 4 enters a transient state. The task handler can therefore increase the values of m i for the tasks τ 1 and τ 2 : m 1 = 6 and m 2 = 1.

-At the end of the scenario, at time t 8 , a transient state is detected by the supervisor for P lant 2 . The last values for the m i parameters that are chosen by the task handler are m 1 = 2 and m 2 = 5. We recall that during the simulation, parameter m 4 is always equal to 1 (hard real-time constraint).

Observed performance

In order to analyze the control of the performance degradation due to the (m, k)firm policy, we evaluate the LQ cost, given by formula (5.20), for each system during the simulation time. Let us note J adaptive i as this value. On the other hand, during the same simulation time and under the same simulation setup, we calculated the nominal performance of each plant provided by the same formula when each system is controlled by a control task on a separate processor; in this case, the constraint applied is a (k, k) one and the sampling period as well as the activation period of the control task are equal to the basic period of each controller. We note J nominal i , the value obtained for P lant i . Table 5.4 presents an example of the performance degradation.

Of course, these results depend on the simulation setup, and they are only exposed here to show that using the proposed technique, the degradation of the performance should be kept as small as possible in each situation subject to the task schedulability. P lant 4 suffered the lower cost degradation due to the fact that this system has to respect a hard real-time constraint m 4 = k 4 = 1. P lant 2 suffered the maximum cost degradation, due to the P lant 2 performance indicator, which generates the reduction of m 2 as soon as the other plants require the use of the processor.

Summary

Through this case study we can see that the on-line adaptation mechanism we proposed can effectively control the degradation of the system performance during the plant state transient period and system overload. In fact, given the current states of the controlled plants, the proposed approach allows us to derive a (m, k)-firm constraint for each control task and the corresponding optimal control gain while still meeting the (m, k)-firm schedulability condition of the total control tasks. Moreover, table 5.4 shows that comparing to the idle case where the processor has infinite capacity, using our approach does not induce much performance degradation. Notice that, for the simulated scenario, if we do not allow sample data dropping (i.e., in case that all tasks are considered under hard real-time constraint), the processor will be in an overload at time t = 0.5 s. As the tasks τ 3 and τ 4 have lower priority, they are no longer executed by the processor and this leads to the instability of P lant 3 and P lant 4 . Figure 5.11 shows that starting from t = 0.5 s where the higher priority task τ 2 is released, the processor can no longer execute task τ 3 correctly and could never execute task τ 4 . As an example, figure 5.12 clearly shows that P lant 3 is not stable.

Conclusions

Computing and networking resource sharing is a common trend in NCS for achieving cost-effective solutions. However, an overload situation may occur, either by the dynamic application configuration changes or by the implementation system performance variations. For dealing with system overload situations, this chapter proposed an approach based on selectively dropping some samples while still guaranteeing the (m, k)-firm schedulability of the control tasks sharing a same processor. By adjusting both the acceptable (m, k) values and the control gains, we have shown, through case studies, that the performance degradation is efficiently controlled. The key point is the use of an algorithm that allows for finding on-line the optimal values of m and the control gains leading to minimizing a global control performance cost function.

This approach has been further extended to also take into account the transient plant state, where the plant needs more resources to be controlled than when it is in its steady state. The stability of this dynamic parameter switching closed-loop has been discussed, and we showed that the asymptotic stability is guaranteed if one can find a CQLF. This extension makes the resource utilization still more efficient. In fact, the idea behind this is that the shared resource is dynamically allocated to the plant that needs it (when it is in its transient phase), rather than being allocated to the plants that are in their steady-state and need less control.

As indicated in the introduction section of this chapter, the approach presented can be considered as an alternative to the direct sampling period adaptation for dealing with system overload situations. Using such an approach, the resulting system will be more robust as it can auto-adapt to fit with certain system overload situations.

Figure 5 . 1 .

 51 Figure 5.1. The global scheduling architecture.

Figure 5 . 2 .

 52 Figure 5.2. Control system architecture.

Figure 5 . 3 .

 53 Figure 5.3. Stability region evaluated on the case study presented in section 5.3.2. kc1 , kc2 , kcLim and kcMax are functions of the sampling period h. The stability region for the cart system is identified by the gray color.

Figure 5 . 4 .

 54 Figure 5.4. Task evolution under hard real-time constraints strategy. The detailed time interval is [0.98, 1.07] and it includes a working mode switch at time t1 = 1 s: before t1 , only two tasks are activated (τ1 and τ2 ); at time t1 , the plant cart4 has to be controlled leading to the activation of the task τ4 .

Figure 5 . 5 .

 55 Figure 5.5. Task evolution under hard real-time constraints strategy. The detailed time interval is [1.98, 2.07] and includes a working mode switch at time t2 = 2 s: before t2 , three tasks are activated (τ1 , τ2 and τ4 ); at time t2 , cart3 has to be controlled leading to the activation of the task τ3 .

Figure 5 . 6 .Figure 5 . 7 .

 5657 Figure 5.6. Control performance under hard real time constraints strategy.

  Arrival time of mandatory task instances that meet their deadline Arrival time of mandatory task instances that do not meet their deadline Arrival time of optional task instances

Figure 5 . 8 .

 58 Figure 5.8. Task evolution under (m, k)-firm strategy. The detailed time interval is [1.98, 2.07] and includes a working mode switch at time t2 = 2 s: before t2 , three tasks are activated (τ1 , τ2 and τ4 ); at time t2 , cart3 has to be controlled, leading to the activation of the task τ3 .

Figure 5 . 9 .

 59 Figure 5.9. Control performance under (m, k)-firm strategy.

F

  and I indicate the current situation: in transient state, F = 0 and I = 1 while in the steady state F = 1 and I = 0.

  Parameters of the plants whose controllers share the same processor and scheduled according to their transient and steady state.

Table 5 .

 5 2. Weights used for each performance evaluation of each controller sharing the same processor and scheduled according to the transient or steady state of the controlled plant.

Plant 1 Plant 2 Plant 3 Plant 4 Figure 5.10.

  Activation, reference (Refi for P lanti ) and output (xi for P lanti ) evolution of the four plants whose controllers share the same processor.

			P lant1		P lant2		P lant3		P lant4
			(k1 = 6)		(k2 = 5)		(k3 = 5)		(k4 = 1)
	t < t0	Ref 1	State m1 steady 6	x 1 State m2 --	State m3 steady 5	State m4 --
	[t0 t1 [		steady	4	-	-	steady	5	steady	1
	[t1 t2 [		transient 6	-	-	steady	2 transient 1
	[t2 t3 [		transient 3	steady	1	steady	2 transient 1
	[t3 t4 [		steady	2	steady	1	steady	5 transient 1
	[t4 t5 [		steady	2 transient 2	steady	2 transient 1
	[t5 t6 [		Ref 2 steady	2 transient 1 transient 5	steady	1
	[t6 t7 [		steady	2	steady	1 transient 5	steady	1
	[t7 t8 [ t ≥ t8		steady steady	6 2	steady x 2 -	5 -	--		-transient 1 -transient 1
								x 3
				Ref 3
	Ref 4
							x 4
										Time (s)
	t 0	t 1 t 2 t 3	t 4 t 5 t 6		t 7	t 8

Table 5 .

 5

3.

Values of mi as they are selected by the task handler at each working mode switch; these values are evaluated for each task activated.

Table 5 .

 5 4. Performance degradation of the four plants.

	l
	i


Stéphanie Bouillot

Christine Rampon

Emmanuelle Tillet

Philippe Huber

Tracing the glycogen