Flavia E Felicioni
email: flaviaf@fceia.unr.edu.ar

J Sergio

Junco
email: sjunco@fceia.unr.edu.ar

A Lie Algebraic Approach to Design of Stable Feedback Control Systems with Varying Sampling Rate

This paper addresses the design of a controller family that, given a continuous-time linear plant sampled at a varying rate, asymptotically stabilizes the closed loop. Under the assumption of having a finite and known set of allowable sampling intervals, the problem is formulated as that of stabilizing a discrete-time switched system (DTSS). The solution approach consists in choosing the controller parameters in order for the Lie algebra generated by the closed-loop DTSS-matrices to be solvable, as this property guarantees the existence of a common Lyapunov function for the control system. The results can be applied to design digital controllers sharing resources, as it is the case of networked control systems, where the need of adapting the rate of task scheduling may originate significant sampling time variations.

INTRODUCTION

Point to point communication and dedicated central processing unit (CPU) traditionally used in control systems implementations are being replaced in many applications by distributed communication (via a common network) and/or shared CPUs (at each node or CPU there are several tasks related with the control of different systems).

The use of common shared resources reduces costs and provides better resource's throughput, benefits that are frequently accompanied by noticeable increments in the amount of information exchanged between the system nodes. As a result, the real-time deadlines of measurement and actuation tasks may be violated due to execution delays, which can lead to performance degradation or even instability of a control system.

In order to mitigate these problems, several measures to achieve an efficient use of available resources have been suggested, rate adaptation of task scheduling among them. For a shared CPU, a feedback scheduler that adjusts the sampling rates of the control loops to guarantee schedulability in different resource conditions was used in [START_REF] Eker | A Feedback Scheduler for Real-Time Controller Tasks[END_REF] and [START_REF] Cervin | Feedback feedforward scheduling of control tasks[END_REF]. In a context of networked control systems, [START_REF] Antunes | Dynamic Rate and Control Adaptation in Networked Control Systems, 5 th Intern[END_REF], (Velazco et al., 2004), and [START_REF] Felicioni | Control de Tráfico de Redes de Comunicación de Sistemas Distribuidos de Control[END_REF], present techniques to adapt the communication rate of the distributed controllers to the available network bandwidth.

Rate adaptation introduces the need to design control laws adapted to these variations and aimed at reducing the performance degradation induced by a varying sampling rate if invariant (non rate-adaptive) controllers were used and, simultaneously, ensuring closed-loop stability.

In order to adapt control laws to rate variations, an optimal design of state-feedback linear quadratic controllers (LQ) was proposed in [START_REF] Cervin | Feedback feedforward scheduling of control tasks[END_REF]. But, as shown in [START_REF] Schinkel | Optimal control for systems with varying sampling rate[END_REF], control systems designed with this optimal-LQ technique, may suffer from instability under certain switching sequences. Due to this undesirable result, [START_REF] Schinkel | Optimal control for systems with varying sampling rate[END_REF] adopts a linear matrix inequalities (LMI) approach to design stable optimal controllers. However, their numerical solutions can be very conservative (see section 4.2).

As a given control system undergoing sampling rate variation can be thought of as a concatenation of systems in time, it can be modeled as a Discrete-Time Switched System (DTSS). This is the mathematical framework exploited in this paper for the control system design problem.

A review of available results to study asymptotic stability of switched systems was presented in [START_REF] Liberzon | Basic problems in stability and design of switched systems[END_REF]. In particular, it was established that if a family of systems that constitutes a switched system has a Common Lyapunov Function (CLF), then, asymptotic stability is guaranteed for any switching sequence. Furthermore, global uniform (for all switching signals) exponential stability was proved for a continuous-time switched system described by a compact family of linear systems, under the condition that each matrix in the family is stable and the Lie algebra associated with the family is solvable. This result was demonstrated connecting the Lie algebra solvability with the existence of a Quadratic CLF. A discrete-time counterpart of this result was presented in [START_REF] Blondel | Approximations of the rate of growth of switched linear systems[END_REF] and [START_REF] Theys | Joint Spectral Radius: theory and approximations[END_REF].

Here, we propose to use Blondel-Theys's result to solve the following problem: given a linear plant sampled at varying rate, design a controller family that asymptotically stabilizes the closed-loop for a given sampling policy.

PROBLEM FORMULATION AND BACKGROUND

This section first formalizes the description of a control system with varying sampling rate as a DTSS. It proceeds with the closer examination of related results and mathematical tools used to formulate and solve the problem.

Switched Linear Systems

Definition (Hespanha and Morse,1999) A Continuous-Time Switched Linear System is defined by a parameterised family of realizations

P = {(A i , B i , C i , D i ): i ∈ p ={1, 2, …, p}},
together with a family of piecewise constant switching signals S:={σ:[0,∞)→ p }, and the (input-state-output) dynamics (1).

(1)

( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) t t t t x t A x t B u t y t C x t D u t σ σ σ σ = + = +
Analogously, a Discrete-Time Switched Linear System with the discrete time base {t k : k ∈ N 0 } has the following form:

(

k k k k k k k k x A x B y C x D u σ σ σ σ + = + = + p k k u k k u i D With u k = u(t k ), x k = x(t k ), and y k = y(t k ). 2) 1 () () ( ) ( )
Due to the switching of the matrices inside the family P, both systems, (1) and (2), are time-varying.

Varying-rate Sampled-data Control Systems

The discretization with a sampling time h t of the open-loop continuous-time plant described by the linear model (3) yields the discrete-time linear system (4), whose matrices are given in (5), if a zero-order hold is considered.

1 i k k t + = - (3) x A x B u y C x D u = + = + (4) ( ) ( ) ( ) ( )
1 k i k i k d i k d i x h x h y C h x D h u + = Φ + Γ = + (5) ( ) ( ) ( ) ( )
0 i i Ah i di h As i d h e C h C h e Bd s D h Φ = = Γ = = ∫
For varying sampling time h i , system (4) can be modeled as (2), with σ(k) = i ∈ p , which yields the equivalence of matrices (6). ( 6)

) ( ) ( ) ( ) ( i i i i i i i i h D D h C C h B h A = = Γ = Φ =
A Closed-Loop Discrete-Time System results from the interconnection of the sampled plant with the linear discretetime dynamic controller (7). Note that the controller parameters adapt themselves to the sampling period.

(7) 1 , , , , ( ) ( )
k C i k C i d i k Ci k Ci d i k v A v B C h u C v D C h x + = + = + k x ) k
Defining the augmented state (

, then the closed-loop dynamics is described by ( 8)

T k k x v         ⋅ Φ =         ⋅         ⋅ ⋅ Γ ⋅ ⋅ Γ + Φ =         + + k k CL i k k i C i i C i C i i i C i i k k x x A h C B C h h C D h h x ν ν ν , , , , 1 1 ) ( ) ( ) ( ) ( ) ( (8)
Particularly, for a static state feedback controller u L , the closed-loop matrix of equation ( 8) reduces to

k i x = (9) i i i i i i CL i L L h h Γ + Φ = Γ + Φ = Φ ) ( ) (

Asymptotic Stability in Closed-loop.

The problem to solve in this paper is the following:

Given the family describing the open-loop systems (4), associated with a finite number of sampling periods {h i , i ∈ } , find a family of controllers (A

C,i , B C,i , C C,i , D C,i ; i ∈ p )
such that the DTSS closed-loop system ( 9) is asymptotically stable.

Variations of this controller design problem have been approached in [START_REF] Sala | Computer control under time-varying sampling period: An LMI gridding approach[END_REF] and [START_REF] Schinkel | Optimal control for systems with varying sampling rate[END_REF] adopting a LMI framework to synthesize optimal controllers that guarantee closed-loop stability under any sampling sequence. More specifically, Sala solves the problem with a unique common controller, while Schinkel obtains a family of controllers associated to the sampling rates.

The solution provided by this work consists of a family of stabilizing controllers with the property that the resulting closed-loop descriptions have a Quadratic CLF (QCLF). It is assumed that the switching signal (which generates the varying parameter h i in our system ( 8)) is determined by a scheduler policy yielding a finite number of known sampling periods.

As reported in [START_REF] Liberzon | Basic problems in stability and design of switched systems[END_REF], the existence of a QCLF for a family of (autonomous) systems guarantees asymptotic stability for arbitrary switching signals. Blondel and Theys, approaching DTSS in a similar way as [START_REF] Liberzon | Basic problems in stability and design of switched systems[END_REF] did for continuous-time systems, proved that if the Lie algebra associated to a family of stable matrices is solvable, then, there exists a QCLF. This result is quoted in the theorem below.

Theorem [Blondel] [Theys]. Let P be the family of matrices {M 1 , M 2 … , M p } and consider the switched linear system ,

M k i k x M x = +1 i ∈ P.
If all matrices in P have spectral radius ρ(M i ) less than 1 (largest modulus of their eigenvalues) and the Lie algebra associated to P is solvable, then the system has a QCLF.

An equivalent result was first established in [START_REF] Gurvits | Stability of discrete linear inclusion[END_REF] for the particular case where each M i in the family takes the form e Ai .

In this paper, the matrices M i are the closed loop matrices , i.e., the approach to solve the stability problem consists in imposing the conditions of the precedent theorem to the family of matrices

CL i Φ { } p i P CL i ∈ Φ = ;
(8), in order to design the

family of controllers (A C,i , B C,i , C C,i , D C,i ; i ∈ p ) looked for.

Mathematical Background

The matrix Lie algebra g:={M i : i ∈ p } generated by the family of square matrices

P ={M 1 , M 2 … , M p } wrt the standard Lie bracket [M ν , M γ ] = M ν M γ -M γ M ν ,
is the linear space spanned by iterated Lie brackets of matrices of the family [START_REF] Liberzon | Basic problems in stability and design of switched systems[END_REF], [START_REF] Theys | Joint Spectral Radius: theory and approximations[END_REF].

For the Lie algebra g, the sequence g (m) is defined as g (0) :=g, g (m+1) :=[g (m) , g (m) ]⊂ g (m) .

If g (m) =0 for some m, then g is said to be solvable.

Given the Lie algebra g, the sequence g m is defined as g 0 :=g , g m+1 :=[g, g m ]⊂ g m .

If g m =0 for some m, then g is called nilpotent.

The nilpotency of a Lie algebra is a sufficient condition for its solvability. Also, the Lie algebra g:={M i : i ∈ p } is solvable if and only if the Lie algebra g ~{ : i ∈ = :

CONTROLLER DESIGN

As already pointed-out, we propose here to choose the controller parameters in order for the Lie algebra generated by the closed-loop DTSS-matrices (8) to be solvable. More explicitly, as the closed-loop model ( 8) is associated to each sampling time, a family of closed-loop matrices is recovered, each of them being parameterized by the corresponding controller set of parameters, which have to be determined in such a way that the sequence g (m) generated by the closedloop family is forced to be zero for some m.

Three cases are presented in the sequel, and the conditions to obtain solvable algebras associated with a family of DTSS matrices are given. These methods are illustrated by some examples in the next section.

Case 1: If g (1) =0, the algebra is solvable, the matrices are pairwise commutative (abelian case), i.e. all the brackets between matrices in the set P={ } are zero. This is an application of a particular case of Blondel's Theorem, which was first proved in [START_REF] Kumpati | A Common Lyapunov Function for Stable LTI Systems with Commuting A-Matrices[END_REF].

Φ Φ Φ

For each pair of matrices in the family, this condition requires that    

. To do that, the controller parameters must to satisfy the following design matrix equation

1 2 1 2 2 1 , 0 CL CL CL CL CL CL Φ Φ =Φ Φ -Φ Φ = (10) 1 2 2 1 CL CL CL CL Φ Φ = Φ Φ
For the controller structure in (9), due to , (10) reduces to

1 2 1 2 2 1 Ah Ah e e Φ Φ = = Φ Φ (11) 1 2 2 1 1 2 2 2 1 1 2 2 1 1 L L L L L Φ Γ + Γ Γ = Φ Γ + Γ Γ L 1 - ) 1 k x - )
For a closed-loop matrix of order n x n the matrix equation ( 11) implies n 2 equations to satisfy. The possibility of satisfying these constraints depends on the number of openloop inputs and outputs and the chosen controller structure.

Case 2: The algebra generated by a family of upper (or lower) triangular matrices is solvable, with m=n+1. As (8) typically does not have a triangular structure, this proposition requires to put (10), in a triangular form by using a similarity transformation common to all.

From digital control theory, the exponential map of the open-

loop system A=R T R -1 is (12) 1 1 At R TR t T t e e Re R - - = =
where R is a similarity transformation. If it is a Jordan decomposition, T has an upper (or lower) triangular form (or a diagonal one).

Applying this transformation to the input part in (6) ( )

1 1 0 0 0 t t t Ax Tx Tx t t e Bds R e R Bds R e ds R B R G R B - -   Γ = = = =       ∫ ∫ ∫ (13)
Here, we consider a state-feedback controller, then by using ( 13) and ( 4), ( 10) becomes ( )

(14) ( ) ( 1 1 Tt k t t x R e G R BL
1 t t G R BL R -
Depending on the open-loop structure, the satisfaction of this condition requires to choose some controller parameters equal to zero. Thus, in several cases, some degrees of freedom for the election of gains of the state-feedback controllers are lost.

Case 3: Here, we analyse the solvability of the algebra generated by a pair of matrices of order 2.

In order to design the pair of controllers, we compute some brackets and derive two equations that must be satisfied to obtain a solvable algebra.

Consider closed-loop matrices M 1 and M 2 , then the sum of diagonal elements of first bracket [M 1 ,M 2 ]=M 3 is zero, i.e. M 3(1,1) =-M 3(2,2) (where M i(k,j) refers to the element of column k and row j from matrix M i ). From the computation of next brackets,

M 3 =[M 1 ,M 2 ], M 4 =[M 1 ,M 3 ], M 5 =[M 2 ,M 3 ], M 6 =[M 3 ,M 4 ], M 7 =[M 3 ,M 5 ], M 8 =[M 6 ,M 7 ],
and so on, it is possible to verify for all i in the set, the same diagonal elements condition, i.e. M i(1,1) =-M i(2,2) andM i(1,1) =-M i(2,2) . The generated algebra for this pair is g (0) =span{M 1 , M 2 , M 3 , M 4 , M 5 , M 6 , M 7 , M 8 ,…}, g (1) =span{M 3 , M 4 , M 5 , M 6 , M 7 , M 8 ,…}, g (2) =span{M 4 , M 5 , M 6 , M 7 , M 8 ,…}, g (3) =span{M 6 , M 7 , M 8 ,…}, g (4) ={M 8 ,…} and so on.

Consider a pair of indices k and j such that k≠j, r≤{k, j}≤ r+2, for some r, and the elements 2,2) are non-zero. To obtain that the next common bracket [M k , M j ] gives a 0 2*2 we must to satisfy both following equations:

M k(1,1) , M k(1,2) , M k(2,1) , M k(2,2) , M j(1,1) , M j(1,2) , M j(2,1) , M j(
(1,1) (1,2) (1,1) (2,1) (1,2) (2,1) (1,1) (1,1) k j k j k k j j M M M M M M M M = = (15)
The iterated bracket computation produces non-linear combinations of the controller parameters in the elements in equation ( 15) (typically they are linear in matrices M 1 , M 2 ). Thus, the solution of these equations becomes more complicated when the value of m is increased. Clearly, nonlinear methods must be required to solve this problem.

EXAMPLES

This section shows some examples to illustrate the methods mentioned in the last section to satisfy the Lie algebra conditions in each of the three cases.

Finding the solutions requires solving a set of non-linear equations. That can be done in symbolic or numerical forms. For example, in the first case by using the symbolic method solve from MAPLE, or in the latter case by using the numerical methods fsolve from MATLAB or MAPLE.

An Introductory Example

In the first order system taken from [START_REF] Cervin | Feedback feedforward scheduling of control tasks[END_REF]

Φ Φ Φ

(1) =0). Furthermore, if ( )

1 1 i i ah ah i e e l a + - 1
< for all i, both hypothesis of Theorem in subsection 2.3 are satisfied, implying the asymptotic stability under any sampling sequence.

The closed-loop for a second sampling time h 2 =α h 1 , being α an integer, is

(

1 1 2 1 1 a h a h CL e e a α α Φ = + -) 2
l . Due to the simple structure of this example, it is possible to obtain that in time t=αh ( )

2 1 CL CL α Φ = Φ 1 +t 0 .
For example if α=2, the satisfaction of the mentioned equation requires to adopt ( ) (  )

1 1 1 2 1 1 2 2 2 1 a h ah a h l ae l e l a e -+ = + 1 u    l
. With this adaptation of the control parameter, the plant reaches the same final state value in one step of sampling time h 2 or in two steps of sampling time h 1 . Then, this election of l 2 allows us to compensate the augmented sampling interval with no degradation in terms of plant state response.

Numerical Example

Here, we solve a numerical problem as an example of Case 3. Due to the numerical distortion introduced by the discretization (5), it is necessary to consider the number precision as large as possible in order to obtain a good numerical solution.

For the second order plant taken from [START_REF] Schinkel | Optimal control for systems with varying sampling rate[END_REF]

0 1 0 10000 0.1 1 x x   = +   - -  
with two sampling times (P=2), h 1 =0.002 and ε=15 (see note), the family of closed-loop matrices ( 9) is { , } 1 0.9801 0.0020 -19.8649+0.0020 0.9799+0.0020

CL 1,1 1,2 l l   Φ =    
.9884+0.0002 0.0014+0.0002 14.0909+0.0014 -0.9886+0.0014

2,1 2,2 2,1 2,2 l l l l       -0 - CL ε Φ =
To obtain the controller parameters for this family, we first compute the seven first Lie brackets as exposed in Case 3. Assuming k=7 and j=6, we derive the non-linear equations ( 15) to obtain M 8 =[M 6 ,M 7 ]=0 2*2 . Then, the algebra g associated with this pair {Φ Cl,1 , Φ Cl,ε } is solvable being m=4.

The parameters that satisfy equations (15) were obtained by further calculations of fsolve command, initialized with a starting guess (parameters designed with LQR in [START_REF] Schinkel | Optimal control for systems with varying sampling rate[END_REF], see also the Remark below).

[ ] [ ] 1 177.820193769818 -19.683275734678 140.481223090893 -0.113548333882

L L ε = =
The spectral values for closed loop matrices are ρ( )= 0.97997188< 1 and ρ( )= 0.984352978< 1 and g

1 CL Φ CL ε Φ (4) =0,
then the hypothesis of Theorem in Section 2 are satisfied and it guarantees asymptotic stability for arbitrary switching.

The difference between the final value of L 1 and the starting one, L 1,0 =[195.401 -19.4121] designed with LQR, is rather small compared with the difference between L 1,0 and L 1,f =[0.5784 -0.0507] obtained via LMI by Schinkel et al..

Remark:

From digital control theory the sampling time must be chosen under the limit established by Shannon theorem (h<π/ω 0 ) In [START_REF] Schinkel | Optimal control for systems with varying sampling rate[END_REF] that limit is not respected by the second sampling time, i.e. 0.094. For that reason, we select h 2 =0.03 (ε=15) (h<π/99.999).

The controller parameters for this sampling time h 2 , L2=[-130.29664515561 1.123104069925], were designed as in [START_REF] Schinkel | Optimal control for systems with varying sampling rate[END_REF]. For example, if the switching signal is σ={1,2}, the dynamics switches between Φ and and always in that sequence, the augmented sampling time system is a periodic one, described by Φ = * . The spectral radius is ρ( Φ )>1 shows that, even each matrix is stable, a sequence of them it is not.

1 CL 1 CL Φ CL ε Φ 1 CL e + CL ε Φ 1 CL e +

Symbolic Example -Commuting matrices

Here, we solve a symbolic problem in the frame of Case 1 for the linear second order model of the cart system of Fig 1.

Rac k

Encoder Pinion (rwheel)

τs f(t) Gear Figure 1: Cart System
The closed-loop system with a state-feedback controller, for

h i = α h 1 with α≥1, is ( ) ( ) ( ) (
)

1 1 1 1 1 1 1 1 1 1 1 1 2 2 1 , 1 1 1 1 1 1 1 2 2 ,2 ,2 1 1 1 1 1 1 k h k h k h k h k h k h e k e k h l h l k k k k k k k e l e e l k k α α α α α α α α α α - - - - -     - -     - - -            - - -    , 1 1 e α α -   -      
Symbolic solution of (11) for the controller L α is presented in Appendix I (equations ( 17) and ( 18)). This controller can be calculated as a non-linear function depending on plant parameters k 1 and k 2 , the sampling times h 1 and α h 1 , and the controller parameters L 1 designed via traditional methods (pole-placement, LQR,..).

For example, consider the plant k 1 =12.65, k 2 =1.92, the sampling period h 1 =0.02 and the controller L 1 =[-121 -6.5] designed via LQR for Q=[1 0;0 0] R=0.0006. The controller parameters L α are continuous functions of α, as we can see in Fig. 2 a) and b).

Upper diagonal matrices

Here, we solve a numerical problem using the Case 2. A paper machine head box model taken from [START_REF] Franklin | Digital Control of Dynamic Systems[END_REF]

is as follows:

[ ]

1 2 0.2 0.1 1 0 1 0.05 0 0 0 0.7 0 0 1 1 0 x x -         = - +     -    
  - + +   = - + -      
We can see that the first column elements cannot be modified by changing the controller parameters. Thus, Φ remains unchanged (equals its original value).

,(1,1)

CL t

Using this controller, the closed-loop matrix (for h 1 =0.

CL h l l l l l l l l   - + +   Φ = - + -   +    
Its eigenvalues are { } Thus, we have a fixed eigenvalue at 0.966 and the others two can be placed by using l Thus, we have a fixed eigenvalue at 0.934 and the others two can be placed by using l 2,4 y f 2,3 .

In the same way we can proceed for any sampling period.

As each closed-loop matrix has an upper diagonal form, the generated algebra associated with a family of them is solvable. The initial introduction of the similarity matrix transformation (R and R -1 ) is a key feature that makes this controller design possible.

CONCLUSIONS

Rate adaptation of task execution is increasingly used in order to optimize allocation and throughput of shared resources in communication and computing systems. This practice may provoke significant variations in the sampling time of digital controllers immersed in networked control systems, with negative impact in closed-loop stability and performance. Motivated by these problems, this paper addressed the problem of designing a controller family that, given a continuous-time linear plant sampled at a varying rate, asymptotically stabilizes the closed loop.

The solvability of the Lie algebra generated by a family of stable matrices, as a sufficient condition for the asymptotic stability of the discrete-time switching system represented by them, is a previous result being used to solve the problem. This condition has been imposed to the closed-loop sampled system in order to obtain the parameterisation of a given state-feedback controller structure that solves the problem.

Conditions to find the solutions have been provided for three cases, which have been illustrated with examples.

In a paper following this one, this work has been complemented with some results on closed-loop performance and robustness, that we have obtained via the calculation of the joint spectral radius of the set of matrices defining the discrete-time switching system.

In what concerns future work, we will explore other Liealgebra solvability conditions, essentially in order to be able to take into account different types of controller structures, beyond the state-feedback controllers considered in this research. ( ) )

/ 2 k h k h k h k h k h k h k h k h k

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1,2 1 2 1,2 1 2 1,2 1 1 2 1,2 1 2 1,2 1 2 1,2 1 2 2 2 2 1 2 1,2 1 1 1 1 2 k h k h k h k h k h k h k h k h l
)

( ( )

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 ,2 1 1,1 1 1,2 1,1 1,1 1,1 1 1,2 1,1 1 1,2 1,1 1,1 2 2 1 2 1 1,1 1 2 1 1,1 1 2 1 1,1 1 2 1 1,1 2 1 , 1 2 2 / 2 k h k h k h k h k h k h k h k h k h k h
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1,1 2 1,1 2 1,1 2 1,1 1 2 1,1 2 1,1 1 2 1,2 1 2 1,2 1 1 2 1,2 1 2 1,2 1 2 1,2 1 2 1,2 2 2 2 1 2 1,2 1 1 1 2 k h k h k h k h k h k h k h k h k h k h

i

  in the set {h i , i ∈ p }, then the algebra associated to closed-loop family results solvable.As for a Jordan decomposition e has an upper (or lower) triangular form, we propose to design state-feedback controller L Tt t in such a way that each matrix has an upper (or lower) triangular form.

Figure 2 :

 2 Figure 2: Controller parameters as function of α.

Acknowledgments: the authors are grateful to the unknown reviewers whose suggestions helped improving the clarity of the presentation.

Appendix A. FIRST APPENDIX

In order to verify conditions (11) for the plant (16), the controller parameters L l for the sampling period αh were obtained in a symbolic form by using MAPLE, as follow:


Flavia Felicioni
email: flaviaf@fceia.unr.edu.ar

Fceia -

Jia Ning
email: ning.jia@loria.fr

Françoise Simonot-Lion

Optimal On-line (m,k)-firm Constraint Assignment for Real-time Control Tasks Based on Plant State Information

In this paper, we study the problem of scheduling a set of control tasks. We distinguish three different situations of states of controlled plants: not activated, steady state situation and transient situation. The infinite-horizon and finite-horizon cost functions are respectively used to represent the performance of each control task in last two situations. We propose a scheduling architecture in which, according to the plant state situation, the task handler switches between these two types of performance criterion to determine an on-line (m,k)-constraint based control task scheduling strategy, so that the overall control performance is maintained at a high level in each situation subject to the task schedulability. The approach is exemplified on a set of controllers for different plants.

Introduction

We consider N physical plants. One dedicated controller implemented as a real-time task controls each plant. Each instance of a task is responsible for carrying out the control law computation and has a deadline by which it is expected to complete its computation. We consider a centralized implementation of all the controllers. At any time, there are n activated plants (with n ≤ N), i.e. n activated tasks. This raises the problem of the schedulability of these n tasks so that the stability is ensured for each controlled plant. In addition to this mandatory objective, we propose to define a scheduling approach that optimizes the control performance. The proposed approach is based on a task instance dropping strategy.

In [START_REF] Jia | Feedback scheduling based on (m,k)-firm constraint model for the handling of a set of real-time controllers[END_REF], we have presented a scheduling approach for a set of control tasks. In this case, the infinite-horizon cost function was used to represent the control performance of each control task. This policy selectively rejects the execution of task instances, so that the overall control performance (sum of the cost function of each task) is maintained at high level and the schedulability is ensured.

In this paper, we focus on the scheduling decision based on the current states of controlled plants; i.e. control tasks are scheduled in a way that reflects the current control performance requirement. Concretely, we distinguish different situations according to the states of the n activated plants (steady: the plant output is in steady state; transient: the plant output is in transient state). The This work has been partially supported by ANR SSIA_NV_15. infinite-horizon and finite-horizon cost functions are respectively used in these situations for describing the control performance of each control task. Based on these cost functions, the proposed scheduling approach selectively rejects the execution of control tasks instances, so that the overall control performance is always maximized and the set of tasks are schedulable. Specifically, changes in plant references or disturbances affecting the plants, may induce the corresponding tasks to be executed more frequently than that in steady state. The system architecture is shown in Figure 1. We suppose that a supervision function of all the controlled plants is implemented in a separate computer. The purpose of this function is to establish the new control objective and to notify the task handler that has to define the new scheduling parameters for this new objective. Specifically, the scheduling parameters are given for each task i τ as a (m i ,k i )-firm constraint [START_REF] Quan | Enhanced Fixed-priority Scheduling with (m,k)-firm Guarantee[END_REF] [START_REF] Ramanathan | Overload management in Real-Time control applications using (m,k)-firm guarantee[END_REF]. A (m i ,k i )-firm constraint means that the deadlines of at least m i among any k i consecutive instances of a control task i τ must be met (m i ,k i N + ∈ , m i ≤ k i ). Since the discarded instances will not be executing the control law, this tends to degrade the control performance. However, if each controller is designed to accept a control performance degradation until k i -m i deadlines misses among k i consecutive task instances (in fact, under a suited basic sampling period, control systems can tolerate misses of the control law updates to a certain extent), the controlled plant can then be conceived so that to offer the control performance levels between (k i ,k i )-firm (ideal case) and (m i ,k i )-firm (worst case) with as many intermediate levels as the possible values between k i and m i . This results in a controlled plant with graceful degradation of control performance.

As the discarded instances can be thought of as a sampling period variation, the controlled plant can be thought of as a concatenation of systems in time, and it can be modeled as a Discrete-Time Switched System (DTSS) [START_REF] Theys | Joint Spectral Radius: theory and approximations[END_REF]. For that reason, we propose an explicit analysis to ensure closed-loop stability for DTSS.

An alternative approach for achieving the scheduling objective of this paper is to adjust on-line the period of control tasks, as the approach proposed in [START_REF] Cervin | Feedback feedforward scheduling of control tasks[END_REF][5] [START_REF] Seto | On task schedulability in real-time control systems[END_REF]. However, this requires a convex cost function to represent the performance degradation, and that is not the general case. Furthermore, these approaches maintain the control performance optimality and control task schedulability by the regulation of the periods of control tasks. However, changing the period of a task may necessitate a change in the periods of dependant tasks as task periods are often carefully selected for an efficient exchange of information between relative tasks; in addition, the change in sampling period of a sub-system alters dynamics of the sub-system and leads to an unavoidable additional study for the approaches based on the regulation of the sampling periods.

The paper is organized as follows. The task model and the scheduling properties under (m,k)-firm constraint is contained in section 2. Section 3 shows how to choose the (m,k)-firm constraint for a control task, presents the finite and infinite-horizon cost function under (m,k)-firm constraint and analyzes closed-loop stability. A formal description and the solution of the scheduling problem are presented in section 4. Section 5 discusses a numerical example of the proposed scheduling approach. Finally, we summarize our work and show the perspectives.

Task model and scheduling properties

In this section, we provide the task model and a task instance classification strategy for fitting the (m,k)-firm constraint; some properties associated to the strategy required to assess the schedulability of control tasks and calculate the cost functions are given as well as a schedulability condition is introduced.

The controller of each plant is realized by a real-time task and the n tasks are executed on a single processor. Each instance of each task is responsible for carrying out the control law computation; therefore each task τ i is characterized by the following parameters: • T i , C i , D i : the time interval between two consecutive instances (period), the maximum execution time and the deadline of each instance; we consider

D i =T i • m i , k i : the (m,k)-firm constraint for τ i with m i ≤ k i .
For meeting the (m,k)-firm constraint, a task instance classification strategy was proposed in [START_REF] Quan | Enhanced Fixed-priority Scheduling with (m,k)-firm Guarantee[END_REF] [START_REF] Ramanathan | Overload management in Real-Time control applications using (m,k)-firm guarantee[END_REF], which classifies the instances of each task into mandatory and optional instances. Only the mandatory instances have to be executed while optional instances could be not executed at all in case of processor overload; for both categories, deadlines have to be met must be met.

We proposed in [START_REF] Jia | Ordonnancement sous contraintes (m,k)-firm et combinatoire des mots[END_REF], [START_REF] Lothaire | Algebraic Combinatorics on Words[END_REF] the equation (1) to determine this classification.

i i i i a am k k m ⎢ ⎥ = ⎡ ⎤ ⎢ ⎥ ⎣ ⎦ (1)
For a = 0,1,…, τ i is classified as mandatory if the equation ( 1) is verified and as optional, otherwise.

Example 1. Let τ i be under [START_REF] Cervin | Feedback feedforward scheduling of control tasks[END_REF][START_REF] Eker | A Feedback Scheduler for Real-Time Controller Tasks[END_REF]-firm constraint, the condition (1) is verified only for a=0+αk, 1+αk and 3+αk (α∈N). Therefore the instances activated at 0,1,3,5, etc are mandatory; those activated 2,4,7 are optional. The determination of the schedulability of a set of tasks under (m,k)-firm constraints has been proved in [START_REF] Quan | Enhanced Fixed-priority Scheduling with (m,k)-firm Guarantee[END_REF] to be NP-hard; however, using the task instance classification strategy (1), the schedulability of tasks can be explicitly proved; we demonstrated in [START_REF] Jia | Graceful Degradation of the Quality of Control through Data Drop Policy[END_REF] that for a single control loop, the control performance obtained with the task classification (1) is sub-optimal.

Equation (1) implies that the mandatory instances are periodically distributed; if the n th instance is classified as mandatory instance, the (n+k) th instance is also classified as mandatory instance. Below, there are some properties of the instance classification strategy (1), which will be used to determine the schedulability of control tasks and to calculate the cost function.

Lemma 1 [7] [START_REF] Ramanathan | Overload management in Real-Time control applications using (m,k)-firm guarantee[END_REF]. Under the task instance classification strategy (1), the index of the j th mandatory instance for each task τ i is

i i j m k ⎢ ⎥ ⋅ ⎣ ⎦ Lemma 2 [7][14]
. Under task instance classification strategy (1), there are exactly ( )

i i i tm T k ⎡ ⎤ ⎢
⎥ mandatory instances for each task τ i before time instant t.

Corollary 1. Under the task instance classification strategy (1), the number of optional instances between the j th and (j+1) th mandatory instances for each task τ i , is given by: ( )( ) ( )

1 1 j m k j m k i i i i ⎢ ⎥ ⎢ ⎥ + - - ⎢ ⎥ ⎢ ⎥ ⎣ ⎦ ⎣ ⎦
Proof. the proof follows from lemma 1 and 2.

In this work, the control tasks are scheduled using the fixed priority policy. The mandatory instances of all the tasks are assigned the rate-monotonic priorities: the mandatory instances of τ i are assigned a higher priority than the mandatory instances of τ j if T i <T j .

A task under (m,k)-firm constraint is said to be schedulable if its (m,k)-firm constraint is satisfied. For the case where instances of each task are classified using equation ( 1), the following theorem proposed in [START_REF] Jia | Feedback scheduling based on (m,k)-firm constraint model for the handling of a set of real-time controllers[END_REF] can be used to determine the task schedulability:

Theorem 1 [9]. Given a task set (τ 1, τ 2 …τ n ) such that T 1 <T 2 < ..<T n . Let: ij j j i j n m k T T ⎡ ⎤ ⎡ ⎤ = ⋅ ⎢ ⎥ ⎢ ⎥ If 1 1 i i i j j i j C n C T - = + ≤ ∑ for all 1 ≤ i ≤ n, then the (m i, k i )-firm constraint of each task τ i is satisfied.
The above schedulability condition is sufficient and necessary if the period of a task is multiple of the periods of all the lower priority tasks. In the other case, it degenerates to a sufficient condition.

Performance and Stability

In section 3.1, we establish an off-line method to choose T i and k i for each plant i. By using these values, we can design the controller thanks to a control design technique (state-feedback controller, LQ-optimal design). For each plant i, and for each m i in the set [1.. k i ], we must calculate controller parameters as presented in section 3.2. Section 3.3 highlights a misconception introduced in [START_REF] Eker | A Feedback Scheduler for Real-Time Controller Tasks[END_REF] about closed-loop performance. Finally, a LMI formulation, which guarantees the stability of the control, is given in section 3.4.

Sampling time selection (T i and k i ) satisfying the constraint of step response

In this section, we present how to choose both, the value of the sampling period T i and the value of k i for (m,k)-firm constraint of each i th plant, so that the step response requirement is respected by using the control theory.

The sampling period selection is a compromise among many factors. Most authors coincide that it is the closed-loop bandwidth the main factor that provides the maximum bound for its value [START_REF] Åström | Computer-Controlled Systems[END_REF]. Its limitation is stated by the sampling theorem: ω CL (closed-loop frequency) should be lower than π/T. Even more, to obtain a good closed-loop performance, based on the closed-loop temporal response, ω CL should be inside the restricted interval proposed in [START_REF] Åström | Computer-Controlled Systems[END_REF], the "rule of thumb": 0.2<ω CL T<0.6. As well, the open-loop plant frequency should respect the sampling theorem (section 3.3). This rule considers the rise time as the step response parameter, which represents how much time the output of a second order under-damped system needs to go from 10% to 90% of its final value. Furthermore, the overshoot should be lower than an admissible threshold (typically 10%) and the rise time T r will be lower than a given time T rM .

In order to relate the continuous-time equivalent parameter with the sampling period (h), we propose to use N r the number of sampling periods per rise time to be chosen between 2 and 10. Note that this rule characterizes the rise time only when it has, among the closed-loop poles, a conjugate-complex pole-pair that dominates the step response. In the case of closed-loop systems with real, stable and very different poles, a class of stiff systems where the rise time can be approximated by Tr=3/a (95%) where a is the continuous-time equivalent slower pole mapped by the relationship z=e sh , we propose to adopt the N r limits as before (2 to 10).

By changing the controller parameters at a change in sampling period, and maintaining the value of N r within its bounds; the rise time remains approximately constant.

Then, this rule is useful to calculate approximately the minimum and maximum values for the sampling period. Specifically, we propose to assign to the sampling time T i the maximum value of N r , then T i =T irM /10. By using the minimum value N r =2, k i should be 5. Possible variations (4 or 6) will depend on the real value of N r , evaluated as function of T i . As we see in fig. 2, for a pendulum both, the time and the response times, remain approximately constant for the extreme N r values.

Optimal LQ design under (m,k)-firm constraint

For each plant i and each k i , we calculate the m i controller parameters using a LQ design [START_REF] Eker | A Feedback Scheduler for Real-Time Controller Tasks[END_REF] [START_REF] Ramanathan | Overload management in Real-Time control applications using (m,k)-firm guarantee[END_REF]. The LQ cost functions, with respect to task instance classification, are calculated for both, finite and infinite horizon strategy. These functions are used by the task handler (section 4.2) as the control performance index to calculate and assign the (m,k)-firm constraint to each control task.

Assume that each plant i is described by the differential equation:

i i i i i i c dx A x dt B u dt dv = + + (2)
where x i is the state vector containing state variables of the controlled plant, and u i is the control signal. The process v ic has mean value of zero and uncorrelated increments. The incremental covariance of v ic is R ic dt.

Let the control task realizing the controller be under a (m,k)-firm constraint, the period of control task to be T i , and let its instances be classified using equation [START_REF] Åström | Computer-Controlled Systems[END_REF]. For simplifying the cost function calculation, we suppose that the executions of all the optional instances are rejected (in practice, optional instances could be assigned the lowest priority and can be scheduled also, under an on-line schedulability test).

The control signal u i,j is computed by a mandatory instance, therefore the time that u i,j is held as constant can be calculated using Corollary 1. From that, the j th control signal is held during

( )( ) ( ) ( )
1 i i i i ij i h T j m k j m k ⎢ ⎥⎢ ⎥ = + - ⎣ ⎦⎣ ⎦ . During the time k i T i , the period h ij assumes m i values of jT i .
The discrete time-varying model of the plant (2) is:

, 1 , , , i j ij i j ij i j i j x x u v + = Φ + Γ + j = 0,1,2,… (3)
where

0 ij ij h Ah As ij ij e e d s B Φ = Γ = ∫ (4)
v i,j is a discrete-time Gaussian white-noise process with zero mean value and the following property:

, , 0

T ij h T A A i j i j Vij ic Ev v R e R e d τ τ τ = = ∫
Since the mandatory instances are distributed periodically in task instance sequence, we have

Φ ij = Φ ij+mi, Γ ij = Γ ij +mi .
The sampled cost function that the controller aims to minimized is chosen as:

( ) 1 ' ' , , , , , , 0 1 0 0 1 2 (5 )
i i i i i i i i i i i i i i H m k T T T T i i j ij i j i j ij i j i j ij i j i i i i H m k T T ij N i N m m j k k J xQ x xM u uR u H m k E x Q x J - = - = ⎛ ⎜ ⎜ = + + + ⎜ ⎜ ⎝ ⎞ ⎛ ⎞ ⎟ ⎜ ⎟ ⎟ + + ⎜ ⎟ ⎟ ⎝ ⎠ ⎟ ⎠ ∑ ∑ ' 0 ( ) ( ) ij h T ij i i Q tQ td t = Φ Φ ∫ , 0 ( ) ( ) ij h T ij i i M t Q t dt = Φ Γ ∫ ( ) ' 0 ( ) ( ) ji h T ij i i i R tQ t R d t = Γ Γ + ∫ , 0 ( ) ij T ij ic J tr Q R d τ τ ⎛ ⎞ = ⎜ ⎟ ⎝ ⎠ ∫ and ( ) i A t i t e Φ = , 0 ( ) i t A s i i t e ds B Γ = ⋅ ∫ ; m i i i H k T N + ∈ and
H i is the i th plant time horizon.

The optimal control law that minimizes the cost function ( 5) is given by [START_REF] Åström | Computer-Controlled Systems[END_REF] as:

, , , i j i j i j u L x = - j = 0,1,2,… (6)
where

( ) ( ) 1 ' , , 1 , 1 ,
T T T i j ij i j ij ij ij i j i j ij L S R S M - + + = Γ Γ + Γ Φ + (7)
and S i,t is obtained from the recurrent equation:

( )( )( ) 0 , ' , , 1 1 ' , 1 , 1 , 1
i i i H i i m kT T i j ij i j ij ij T T T T T T ij i j ij ij ij i j ij ij ij i j ij ij S Q S S Q S M S R S M + - + + + = = Φ Φ + -Γ Φ + Γ Γ + Γ Φ + (8)
Because of the periodicity of Φ ij and Γ ij , the steady state solution of the Riccati equation ( 7) is periodic with period m i [START_REF] Bittanti | The periodic Riccati equation[END_REF], i.e., , , i i j i j m S S + =

. The controller gain matrix L i,j is designed using the steady-state solution of Riccati equation ( 7) and its solution is also periodic: L i,j =L i,j+mi Lemma 3. The minimal value of J i under task instance classification strategy (1) is given as:

( )

1
,0 ,0 ,0 , 1 0 1 ( , , )

i i i i H m T k T ij i i i i i i i i j V i i i j i i i J H m k x S x trS R J H m T T k ⎡ ⎤ - ⎢ ⎥ ⎢ ⎥ + = ⎛ ⎞ ⎜ ⎟ ⎜ ⎟ = + + ⎜ ⎟ ⎡ ⎤ ⎜ ⎟ ⎢ ⎥ ⎜ ⎟ ⎝ ⎠ ⎢ ⎥ ∑ (9)
where , 0 ( )

ij h i j ic J tr Q R d τ τ ⎛ ⎞ = ⎜ ⎟ ⎝ ⎠ ∫ Proof.
The minimal value of J j given by optimal LQ controller ( 6) is derived in [START_REF] Åström | Computer-Controlled Systems[END_REF] as

( ) 1 ,0 ,0 ,0 , 1 0 1 i N T ij i i i i i j V i j i i j J x S x t r S R J N T - + = ⎛ ⎞ ⎜ ⎟ = + + ⎜ ⎟ ⎝ ⎠ ∑
where N i is the number of control law updates. As the control law is only updated by a mandatory instance, the number of control law updates is therefore equal to the number of mandatory instances. Lemma 2 shows that there are exactly

( ) i i i i H m Tk ⎡ ⎤ ⎢
⎥ mandatory instances before instant H i , we therefore get

( ) i i i i H m Tk i N ⎡ ⎤ ⎢ ⎥ = .
When time goes to infinity ( lim i H → ∞ ), the influence from the initial condition decreases and because , , i i j i j m S S + = , (9) may be written as:

1 1 , 1 0 0 1 ( , , ) i i m m ij i i i ij V i j i i j j J m k trS R J m T - - + = = ⎛ ⎞ ⎜ ⎟ ∞ = + ⎜ ⎟ ⎝ ⎠ ∑ ∑ (10)
According to [START_REF] Jia | Graceful Degradation of the Quality of Control through Data Drop Policy[END_REF], the instance sequence is chosen as uniformly as possible. For that, during each interval k i T i the varying model (2) will update m i times, and the period h ij assumes a value in the set Ψ i ={f i,0 T i , f i,1 T i , …,f i,mi-1 T i } (j is replaced by f i,p obtained as in [START_REF] Jia | Graceful Degradation of the Quality of Control through Data Drop Policy[END_REF]). For example, if k i /m i is an integer, the optimal sequence in [START_REF] Jia | Graceful Degradation of the Quality of Control through Data Drop Policy[END_REF] gives f i,0 =f i,1 =…=f mi-1 = k i /m i .

Closed-loop performance

From digital control theory, we know that if we reduce the sampling time of a plant, the open-loop performance will be closer to the continuous-time system one. So, a similar behavior for the closed-loop performance is expected (when the sampling period grows, the plant response becomes worse than the continuous time one, forcing performance degradation). But fig. 4 in [START_REF] Eker | A Feedback Scheduler for Real-Time Controller Tasks[END_REF] shows the closed-loop cost as function of the sampling time for a given plant (pendulum), where the controller parameters are obtained with an infinite time horizon LQ design. Surprisingly, in this figure, some high peaks appear for some specifics sampling periods. Then, the classical conception mentioned before is contradicted, i.e. faster sampling not necessarily increases control performance. To highlight this unexpected conclusion, we made the same analysis as in [START_REF] Eker | A Feedback Scheduler for Real-Time Controller Tasks[END_REF] (fig. 3), and we found that the first peak occurred when the sampling period is T=π/ω A , where ω A is the open-loop frequency of the plant. The reason for this peak is that the sampling theorem is not respected for the open-loop plant (plant resonance), that is unacceptable. Even, as we show in fig. 4, one can satisfy the mentioned "rule of thumb" inside the section limited at top and at bottom by both red straight lines.

Summarizing, to select the maximum sampling period (k i T i ) we add to the selection criteria presented in section 3.1, the verification of the sampling theorem for the open-loop plant. In this more restricted area, the classical digital control conception remains valid.

Closed-loop Stability

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 control law parameters to this variation, we use the design presented in section 3.2. But, as it was shown in [START_REF] Schinkel | Optimal control for systems with varying sampling rate[END_REF], controllers designed with optimal-LQ techniques, may suffer from instability under certain switching sequences, i.e. when the sampling period changes. Due to this undesirable result, [START_REF] Schinkel | Optimal control for systems with varying sampling rate[END_REF] adopts a linear matrix inequalities (LMI) framework to design stable optimal controllers.

We will use a LMI framework to find a Common Quadratic Lyapunov Function (CQLF), then, asymptotic stability is guaranteed for any (m,k)-firm sequence proving the stability of the control. Firstly, we consider the set of m i controller parameters to be calculated for each possible value of

m i £ i ={ 1 0 1 , , , i i i i m m m m L L
L -}, by using equation [START_REF] Jia | Ordonnancement sous contraintes (m,k)-firm et combinatoire des mots[END_REF], where j=f d (f d depends on the delivery sequence [START_REF] Jia | Graceful Degradation of the Quality of Control through Data Drop Policy[END_REF]) and d=0,1…,m i -1, i.e. for the set Ψ i . Secondly, we consider the set of open-loop discrete time models (2), Θ i ={ ( )(

) ( )

1 1 2 2
, , , , , ,

i i i i i i ik ik Φ Γ Φ Γ Φ Γ
} and evaluate the k i periods, taking into account possible interruptions in a planned sequence at any time.

By using elements in both sets, we can establish a new set of m i •k i closed-loop models, (3) without noise,

, l d i i d il il m A L = Φ + Γ
, where l varies between 1 and k i ( ( )

, il il Φ Γ ∈Θ i ) and d between 0 and m i -1 ( d i L ∈£ i ).
In order to prove the stability of DTSS [START_REF] Theys | Joint Spectral Radius: theory and approximations[END_REF], we should find a CQLF for the set of matrices , n d i A , where 1 1,.., , with 0,..,

i i n k d m - = = . Then, we formulate a set of m i •k i inequalities: ( ) , , 0, n d n d T i i A P A P n d -< ∀ ∀ ,
and for this set, we propose to use the LMI toolbox from Matlab in order to find the common matrix P=P T >0.

Scheduling architecture and supervision

As we stated above, during the execution of the application, we distinguish 3 situations of states of controller plants: steady state, transient state and not activated plant. This information is provided by the supervision task. Section 4.1 describes how plant states are identified. A new system state, determined by the supervision task, requires the definition of new scheduling parameters by the task handler (section 4.2).

Plant State Detection

In this section, we specify how the supervision component identifies the situation of states of controlled plants. We consider the situation 1-for non activated plant and two situations for an activated one: 2-Steady state (or near) and 3-Transient state. Situation 1 is used 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). Reaching or leaving situation 1 for a plant modifies the value of n.

The deadband approach presented in [START_REF] Otanez | Using Deadbands to Reduce communication in Networked Control Systems[END_REF] is used to distinguished situation 2 and 3. Each controlled plant has a state, which asymptotically tracks the reference r, which is supervised by the supervision task. Let y 1 be this plant state. The following condition is set up:

( ) ( ) ( ) { } 1 1 1 1 1 min , i i y h nh y nh y nh th δ + - <
where th is a threshold to prevent false identifications due to noise. h i is the detection period of the supervision component for the plant i. We proposed to select this time equal to the i th sampling period. If this condition is verified, the plant is considered as in steady state, otherwise, it is in transient state. This plant state detection mechanism has as advantages that it depends on the actual evolution and it detects, in the same way, reference changes or/and non-modeled perturbations.

Task Handler

We implement a task handler which at each situation change, adjusts the (m,k)-firm constraint for each task by considering the current control performance indicator and the task schedulability objective. In this section, we formulate the scheduling problem and give the solution. After, the scheduling architecture is presented.

We suppose that the value k i of each τ i has been carefully chosen (section 3.1) and is constant during the execution of application. The value of m i is chosen in [1 .. k i ] on line by the task handler. For each control task τ i , each possible value of m i is associated with two values g ij and g ij ' corresponding to the control performance, respectively, in transient situation and in steady one. Suppose that a lower value of g ij or g ij ' represents a better control performance, the aim of the task handler at a change in situation of plant states is to find, for each τ i , a value m i ∈ [1.. k i ] so that the sum of g ij or g ij ' (according to the situation which the plants fall into) for j∈ [1.. k i ] and i∈ [1.. n] is minimized subject to the task schedulability. Then, condition in Theorem 1 is modified taking into account the mentioned performance indicators. This is formally formulated as the following optimization problem: To determine the sequence

C s m k T T C T i n

- = = ⎡ ⎤ ⎡ ⎤ + ≤ = ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ∑ ∑
where I and F are situation indicators: in transient state, I is 1 and F is 0, and in steady state, I is 0 and F is 1. The values g ij and g ij ' are given in two way: one is using directly the cost ( 8) and [START_REF] Khan | Solving the knapsack problem for adaptive multimedia systems[END_REF], and the other way is to take the relative performance degradation percentage: ( , , ) ( , , ) ( , , )

ij i i i i i J H m k J H k k J H k k -
and ( , , ) ( , , ) ( , , )

ij i i i i i J m k J k k J k k ∞ -∞ ∞ (12)
Using the first control performance representation method, the optimization problem is to minimize the overall cost of the application. However, the sub-systems with lower costs may suffer from great control performance degradation due to a low value of m i . That is, the task handler maintains the value of each m i as great as possible for the sub-systems with greater costs by reducing the value of m i for the sub-systems with lower costs. Using [START_REF] Otanez | Using Deadbands to Reduce communication in Networked Control Systems[END_REF] as the control performance criteria avoids such a situation. 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.

The time horizon H i for the finite-horizon cost functions is an important design parameter, which directly affects the overall control performance, and need to be carefully chosen. Here, we choose H i as the settling time (approx. three times the rise time). To calculate [START_REF] Otanez | Using Deadbands to Reduce communication in Networked Control Systems[END_REF] in an off-line form, we considered the typical values of the reference values neglecting noise.

The optimization problem [START_REF] Lothaire | Algebraic Combinatorics on Words[END_REF] has the similar form as that in [START_REF] Jia | Feedback scheduling based on (m,k)-firm constraint model for the handling of a set of real-time controllers[END_REF] which was qualified as the multiple-choice multi-dimension knapsack problem (MMKP) [START_REF] Martello | Knapsack Problems: Algorithms and Computer Implementations[END_REF], and was proved to be NP-hard problem. For solving the optimization problem, the heuristic algorithm based on a so-called computationally cheaper heuristic algorithm (HEU) proposed in [START_REF] Khan | Solving the knapsack problem for adaptive multimedia systems[END_REF] is used. It has been shown that the algorithm is efficient and suitable for an on-line use for real-time application.

At each change in the situation of at least one plant, the task handler receives the information about the current plants states. Based on this information (n current activated plants), and the values of v ij that were evaluated off-line, it deduces the new (m,k)-firm constraint for each control task by solving the optimization problem [START_REF] Lothaire | Algebraic Combinatorics on Words[END_REF]. The control tasks are then scheduled according to these (m,k)-firm constraints.

Case study

In this section, we illustrate the scheduling approach presented above by studying the control of four plants. Plant 1 (resp. Plant 2 , Plant 3 , Plant 4 ) corresponds to a harmonic oscillator system, (resp. to a cart system, a pendulum and an inverted pendulum).

Plants and Controllers

Each plant is modeled by the differential equation (2):

Plant 1 : 0 1 0 , -18 0 516 A B ⎡ ⎤ ⎡ ⎤ = = ⎢ ⎥ ⎢ ⎥ ⎣ ⎦ ⎣ ⎦
and v c has the incremental covariance:

1 0.0025 -0.005 = -0.005 0.01 c R ⎡ ⎤ ⎢ ⎥ ⎣ ⎦ ; Plant 2 : 0 1 0 , 0 -12.6558 1.9243 A B ⎡ ⎤ ⎡ ⎤ = = ⎢ ⎥ ⎢ ⎥ ⎣ ⎦ ⎣ ⎦
and v c has the incremental covariance 1 0.005625 -0.075 = -0.075

1 c R ⎡ ⎤ ⎢ ⎥ ⎣ ⎦ ; Plant 3 : 0 1 0 , -22.206 -0.9424 0.48036 A B ⎡ ⎤ ⎡ ⎤ = = ⎢ ⎥ ⎢ ⎥ ⎣ ⎦ ⎣ ⎦
and v c has the incremental covariance

3 0 0 = 0 22.2066 c R ⎡ ⎤ ⎢ ⎥ ⎣ ⎦ ; Plant 4 : 0 1 0 0 0 0 0 -14 0 2 , 0 0 0 1 0 0 0 28 0 2 A B ⎡ ⎤ ⎡ ⎤ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ = = ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎣ ⎦ ⎣ ⎦
and v c has the incremental covariance

1 0 0 0 0 0 0.0025 0 0 = 0 0 0 0 0 0 0 0 c R ⎡ ⎤ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎣ ⎦ .
The controller of Plant i is denoted Controller i .

Rise time specifications T rM of each plant are respectively 0.2, 0.2, 0.3 and 0.5. Then, sampling periods are related to rise time specifications, i.e., 0.02s for Plant 1 , 0.02s for Plant 2 , 0.03s for Plant 3 , and 0.05s for Plant 4 .

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 asymptotically tracking the plant state reference. The step response target for the cart is an overdamped response, while for the others they are underdamped ones, being the damping coefficient upper than 0.6 (overshoot < 10%).

The controllers are designed using [START_REF] Jia | Graceful Degradation of the Quality of Control through Data Drop Policy[END_REF] for each m i value. The design weights, which allow the satisfaction of the mentioned rise time and overshoot, are:

Controller 1 : 1 5 0 0 0 0 0 0 0 25 Q ⎡ ⎤ ⎢ ⎥ = ⎢ ⎥ ⎢ ⎥ ⎣ ⎦ , R 1 =200 Controller 2 : 2 1.25 0 0 0.0085 Q ⎡ ⎤ = ⎢ ⎥ ⎣ ⎦
, R 2 =0.0001.

Controller 3 : 3 1 0 0 0 Q ⎡ ⎤ = ⎢ ⎥ ⎣ ⎦ , R 3 =0.00001. Controller 4 : 4 1 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 Q ⎡ ⎤ ⎢ ⎥ ⎢ ⎥ = ⎢ ⎥ ⎢ ⎥ ⎣ ⎦ , R 4 =0.001.
Using the LMI control toolbox, 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,k)-firm constraints at an m adjustment, the controller parameters are calculated off-line and stored in a table.

Since the control tasks are assigned the rate-monotonic priority, the task with the largest period has the lowest priority; its execution has no influence on three possible levels are 1-Running (task being executed by the processor), 0.5-Preempted (the execution is preempted by other task); and 0-Waiting (task waits for an activation). We could verify that each task deadline is always respected (it is guaranteed by the event-triggered execution of the task handler). Evolution of the plant outputs is given in fig. 6 In order to analyze the performance degradation, we evaluate the LQ cost for each system during the simulation time. Considering that we have a dedicated CPU for each system, we calculated the nominal performance of each plant (Table 3) as the reference values. The values of Performance overall system were evaluated considering the simulation setup described before. These results depend on the simulation setup, and they are only exposed to show that using the proposed technique, the degradation of the performance should be maintained as small as possible in each situation subject to the task schedulability. Plant 4 suffered the lower cost degradation; due to the m 4 is always equal 4. Plant 2 , suffered the maximum cost degradation, due to Plant 2 performance indicators, which generates the reduction of m 2 if the other plants require the use of CPU.

Conclusion

This paper has presented a scheduling approach based on the (m,k)-firm constraint model for scheduling a set of control tasks. Given the current states of the controlled plants, the proposed approach derives a (m,k)-firm constraint for each control task, and the control tasks are scheduled using these (m,k)-firm constraints so that the schedulability of control tasks is guaranteed and the overall control performance is maintained at a high level.

Compared with feedback scheduling approaches in the literature, the advantages of the proposed approach are: the approach does not depend on the type and property of the control performance (whatever the functions of the control performance are convex, the proposed approach can always keep the overall control performance at high level while guarantying the schedulability of control tasks); at a system configuration change, the event-triggered solution reacts immediately reducing the periods of the tasks.

Figure 1 .

 1 Figure 1. Overall system architecture.

Figure 2 :

 2 Figure 2: Minimum and maximum values of N r .

Figure 3 :

 3 Figure 3: Cost vs. sampling time. Pendulum.

Figure 4 :

 4 Figure 4: ω CL T vs. sampling time. Rule of thumb.

Figure 6 :

 6 Figure 6: Output evolution of Plants.

Table 3 . Performance costs of Plant i .

 3

the other tasks. Therefore, no task instance classification will be applied to Controller 4 , or in other words, it is executed under (k,k)-firm constraint.

Using the approach proposed in section 4, the value of k i is set to respectively 6, 5, 5 and 4. The value of m for the plants may vary within [1.. k

Performance specification and simulation setup

Table 1a gives, for Controller 1 the optimal costs associated with different (m,k)-firm constraint. The column labeled "OC_IH/Degradation (%)" lists the optimal infinite-horizon costs and the relative performance degradation compared to (k,k)-firm constraint. The column "OC_FH / Degradation(%)" lists the optimal finite-horizon costs for typical initial plant states and the relative performance degradation compared to (k,k)-firm constraint. The time interval of the finite-horizon cost functions is set equal the settling time for each system (see section 4.2).

In practice, the task handler can calculate the optimal finite-horizon costs on-line. They are listed here to illustrate how task handler chooses the (m,k)-firm constraints for each controller. The simulation model was created using Simulink and the TrueTime toolbox [START_REF] Cervin | How does control timing affect performance[END_REF]. The execution time of each controller is approximately 9ms.

Simulation results

The simulation results obtained with the proposed approach are given in this section.

The model has been evaluated under the setup shown in Table 2. There, we identify the state (st) of each plant as follow: -1→Not activated, 0 → Steady-state and 1→ Transient-state. State changes (or transitions) are detected by the supervision component and, in the proposed simulation; they arrived at time « Time-Event ». Therefore, the task handler at the "Time-event", based on the overall system state, calculates the value of each m i .

At the system starting (time 0 -) only Plant 1 and Plant 3 are activated (both in steady state situation). At time 0+, the task associated with Plant 3 is activated, and then the task handler is executed in order to admit the new task (Plant 1 -> state transition from -1 to 0). The schedulability condition at time 0 -{0.009<0.02, 0.018<0.02} allows the system to accept all the instances, i.e. m 1 = k 1 and m 3 = k 3 . At time 0 + , with m i = k i , schedulability conditions are {0.009<0.02, 0.018<0.02, 0.063>0.05}, i.e. the third condition is not verified, justifying the execution of the task handler and the changes in the values of each m i . At time 0.27, the transient state of Plant 1 is detected by the supervision component and the task handler is executed, then the values of all m i are adjusted accordingly. Clearly m 1 is augmented with respect to its previous value to provide better transient performance of Plant 1 . This choice of (m,k)-firm constraints is done verifying the condition proposed in section 4, whose goal is to reduce the overall performance degradation. Other choice makes either the tasks non-schedulable or a worse overall performance degradation.

At time 0.5, Plant 2 is activated, and then a new configuration is required to manage 4 Plants. In this case the schedulability condition {0.009<0.02, 0.018<0.02, 0.045> 0.03, 0.081>0.05}, i.e. if we do not reduce the values of m i , the tasks will be non-schedulable.

The extinction of the Plant 1 transient, at time 0.62, produces a new set of m i values. In the same way, the detection of the Plant 2 transient at 0.8 requires the adjustment of the m i values. See Table 2.

At time 1.76, an inadmissible perturbation enters in the Plant 3 , the output reaches π/2, and consequently this plant is deactivated reducing the number of tasks to 3. Then, the task handler can augment m 1 and m 2 values using condition in section 3. Both values cannot assume their maximum, k 1 and k 2 , because the schedulability conditions for the 3 systems are {0.009<0.02, 0.027>0.02, 0.045>0.03}. Finally, at time 1.8 the detection of the Note that as the (m,k)-firm constraint of Controller 4 is hold as (k,k) throughout the execution of application, the change in the state of the Plant 4 has not effect on the decision of task handler.

Throughout the simulation, the rise-time requirements of plants are all met thanks to a judicious selection of k i .

The minimum delay is 9ms, i.e. the computation time. In fig. 5, we show the scheduling of Controller2. The