F Grognard

O Bernard

Stability analysis of a wastewater treatment plant with saturated control

Keywords: Control, bioreactor, anaerobic digestion, saturation, COD

This paper presents a saturated proportional controller that achieves depollution of wastewater in a continuous anaerobic digester. This goal is reached by defining a region of the state-space where the depollution is achieved and forcing attractivity and invariance of this region. The control variable is the dilution rate and the controlled variable is a linear combination (S λ ) of the substrate concentrations, that could be the Chemical Oxygen Demand (COD) or the Biological Oxygen Demand (BOD), depending on the value of λ. No measurement of the substrate concentration in the input flow is required; the only necessary measurement is S λ .

INTRODUCTION

The control of bioreactors is a delicate problem since most of the time the available biological models are only rough approximations, the biological systems being known to be highly variable and difficult to measure. To circumvent this difficulty, [START_REF] Bastin | On-line Estimation and Adaptive Control of Bioreactors[END_REF] have introduced the mass balance based modelling. The main idea of this approach is to design estimators and controllers independently of any modelling of the biological kinetics.

Among the bioreactors, those dedicated to wastewater treatment especially suffer from the modelling uncertainties. A complex ecosystem composed by many different bacterial populations takes place in these processes, and the composition and concentration of the pollutant to degrade is not well known and evolves with respect to time. Moreover, most of the time no measurement of the involved chemical or biological species is available; this can be critical when the bioreactor is unstable as is the case for the anaerobic digestor. In these conditions, a control procedure that would guarantee the process stability should be as insensitive as possible to all these parameters.

In this paper, we will consider an anaerobic wastewater treatment process, that is a biological process in which biodegradable organic materials are decomposed in the absence of oxygen to produce methane. The underlying model assumes that two main bacterial populations are present [START_REF] Bernard | Dynamical model development and parameter identification for an anaerobic wastewater treatment process[END_REF]). The first one, the acidogenic bacteria X 1 , consumes the organic substrate S 1 and produces through an acidogenesis step volatile fatty acids (VFA) S 2 . The second population (methanogenic bacteria) X 2 , uses the VFA in a methanogenesis step as substrate for growth and produces methane.

Despite its capacity to degrade difficult substrates, this process is known to become unstable under certain circumstances, like variations of the process operating conditions, and requires therefore a monitoring procedure to detect a destabilization. This must also be associated to a control action that can avoid the risk of acidification of the fermenter. Therefore, some control laws have recently been introduced for this process like the adaptive feedback of the gaseous flow-rate measurement [START_REF] Perrier | Evaluation of control strategies for anaerobic digestion processes[END_REF][START_REF] Mailleret | Robust regulation of anaerobic digestion processes[END_REF][START_REF] Mailleret | Nonlinear adaptive control for bioreactors with unknown kinetics[END_REF] or fuzzy control of the VFA concentration [START_REF] Genovesi | A fuzzy logic based diagnosis system for the on-line supervision of an anaerobic digestor pilot-plant[END_REF][START_REF] Punal | Advanced monitoring and control of anaerobic wastewater treatment plants: Diagnosis and supervision by a fuzzy-based expert system[END_REF] to avoid acidification of the reactor. The controller that we have designed regulates a linear combination of the substrate concentrations, that we will denote S λ ; depending on the value of the parameter λ, S λ can represent the Biological Oxygen Demand (BOD) or the Chemical Oxygen Demand (COD), that is the standard measurement of the pollution level. Our controller requires the measurement, or the observation through software sensors (through the application of techniques similar to [START_REF] Alcaraz-Gonzalez | Software sensors for highly uncertain wwtps : a new approach based on interval observers[END_REF]), of S λ and has a very simple structure that takes actuator limitations into account (as is also done in [START_REF] Antonelli | Set-point regulation of an anaerobic digestion process with bounded output feedback[END_REF]); it has the advantage of not requiring any measurement of the substrate concentrations in the input flow. The variable that is used for control is the dilution rate (D).

MODEL OF ANAEROBIC DIGESTION

In this paper, we will use the model AM1 of anaerobic digestion that was presented in [START_REF] Bernard | Dynamical model development and parameter identification for an anaerobic wastewater treatment process[END_REF]:

       Ẋ1 = (µ 1 (S 1 ) -αD)X 1 Ẋ2 = (µ 2 (S 2 ) -αD)X 2 Ṡ1 = D(S 1in -S 1 ) -k 1 µ 1 (S 1 )X 1 Ṡ2 = D(S 2in -S 2 ) + k 2 µ 1 (S 1 )X 1 -k 3 µ 2 (S 2 )X 2 (1)
with X 1 , X 2 , S 1 , S 2 , D ∈ IR + , µ 1 (S 1 ) a non-decreasing and bounded function such that

µ 1 (0) = 0 and µ 1 (S 1 ) < µ 1max ∀ S 1 ≥ 0 and µ 2 (S 2 ) a function such that µ 2 (0) = 0 and µ 2 (S 2 ) ≤ µ 2max = µ 2 (S * 2 ) ∀ S 2 ≥ 0
and µ 2 (S 2 ) is non-decreasing from S 2 = 0 to S 2 = S * 2 and non-increasing afterwards with lim

S 2 →+∞ µ 2 (S 2 ) = 0
Classically, µ 1 is of the Monod type and µ 2 of the Haldane type. The terms S 1in and S 2in are the influent concentrations of S 1 and S 2 respectively. The k i represent the yield coefficients associated with bacterial growth. The parameter α ∈ [0, 1] represents the proportion of bacteria that are not fixed on the bed, and therefore that are affected by the dilution effect: α = 0 would correspond to an ideal fixed bed reactor, α = 1 to an ideal continuous stirred tank reactor. This model has been built and validated with the spirit of finding a trade-off between model complexity and mathematical handling of the model for control purpose. It is not intended at giving an accurate view of all the phenomena that take place in the reactor as higher-dimensional models do (e.g.the IWA Anaerobic Digestion Model No.1 [START_REF] Batstone | The iwa anerobic digestion model no.1 (adm1)[END_REF]).

OBJECTIVE AND CONSTRAINTS

The original control objective for depollution is to regulate the output S λ = S 1 + λS 2 (with λ ≥ 0 not always equal to 1 because S 1 and S 2 do not need to be expressed in the same units), which, depending on the chosen value for λ, can be the COD or BOD. The target value for S λ is some Sλ ≤ S λmax ≤ S λin = S 1in + λS 2in . In this paper, the objective is modified as follows

Objective 1 Given S λmin ≤ Sλ ≤ S λmax , steer all the solutions of the controlled system to a region where S λmin ≤ S λ ≤ S λmax is satisfied and stays valid for all future times Instead of achieving regulation, we will achieve attractivity and invariance of a security zone. In this formulation, S λmax is an unalterable data of the problem (fixed by depollution norms); on the other hand, S λmin can be chosen more freely: if it is taken close to S λmax , the achievement of Objective 1 is almost equivalent to the regulation of the output S λ ; if S λmin is taken close to zero, there is a risk that the system settles at a small value of S λ with a small value of the dilution rate. The pollutant concentrations in the input, S 1in and S 2in , are supposed to be constant. They do not need to be known for the application of the controller. However, in order to show stability of the controller, those values need to be known.

In order to design a controller, we first analyze the different parameters associated to the control objective. In the sequel, we will show that the following assumption needs to be imposed.

Assumption 1

The parameters satisfy the following three inequalities

λ < k 1 k 2 (2) S λmax < min(S 1in , λT 2in ) = min(S 1in , λk 2 k 1 S 1in + λS 2in ) (3)
D max < min(µ 1 (S 1in ), µ 2 (S 2in ), µ 2 (T 2in )) α (4)
The parameter λ The evolution of the pollution level follows the following equation:

Ṡλ = D(S λin -S λ ) -(k 1 -λk 2 )µ 1 (S 1 )X 1 -λk 3 µ 2 (S 2 )X 2 (5)
Condition ( 2) imposes that the pollution level decreases when the flow rate is stopped (which is the intuitive behavior of a digester). This condition is met by the identified parameters of the experimental process [START_REF] Bernard | Dynamical model development and parameter identification for an anaerobic wastewater treatment process[END_REF]) when S λ is the COD (λ = 0.064 g/mmol and k 1 k 2 = 0.368 g/mmol).

The bound S λmax

In the rest of this section, we will replace S 2 with the coordinate T 2 = S 2 + k 2 k 1 S 1 . This results in the following system:

         Ẋ1 = (µ 1 (S 1 ) -αD)X 1 Ẋ2 = (µ 2 (T 2 -k 2 k 1 S 1 ) -αD)X 2 Ṡ1 = D(S 1in -S 1 ) -k 1 µ 1 (S 1 )X 1 Ṫ2 = D(T 2in -T 2 ) -k 3 µ 2 (T 2 -k 2 k 1 S 1 )X 2 (6) considered in the positively invariant set {(X 1 , X 2 , S 1 , T 2 ) ∈ IR 4 + |T 2 ≥ k 2 k 1 S 1 }.
In these new variables, the measure S λ is rewritten as

S λ = S 1 + λS 2 = (1 -λ k 2 k 1 )S 1 + λT 2 .
We will now impose a condition that we will call "regulability": this condition makes sure that, whatever the level Sλ ≤ S λmax that is regulated, there corresponds a non trivial equilibrium for system (6). If S λ is set at some prespecified value Sλ , there should exist a constant dilution D > 0 corresponding to an equilibrium. From the Ẋi = 0 equations, we see that such an equilibrium should satisfy:

µ 1 ( S1 ) = µ 2 ( Sλ -S1 λ ) > 0
This potentially results in several values of S1 > 0 for our equilibrium, and corresponding values of D. Introducing this into the Ṡ1 = Ṫ2 = 0 equations, we obtain

0 = (S 1in -S1 ) -k 1 α X1 0 = (T 2in -T2 ) -k 3 α X2
Isolating X1 and X2 , we get X1 = S 1in -S1 k 1 α and X2 = T 2in -T2 k 3 α . At the equilibrium, X1 and X2 should be positive. Noticing that S1 ≤ Sλ < S λmax and λ T2 ≤ Sλ < S λmax , it suffices to impose (3) to have X1 and X2 positive at any equilibrium having Sλ < S λmax . This assumption also forces S λmax < S λin ; it is reasonable, as we want to bring pollution to a lower level than its influent value.

Bounded control

The control variable is the dilution rate, so that it must be non-negative, and it cannot be arbitrarily high. There is an a priori upper-bound on the maximal flow-rate D max due to the physical constraint associated to the pumping mechanism. This bound can be seen as a given data, but it can also be seen as a design parameter (a different choice of input valve can give a different value of upper-bound for D max ). On the other hand, the minimal value of the flow-rate is, theoretically, zero; however, in the industrial environment, the output of the industrial plant that produces the waste cannot be totally stopped, it is lower-bounded by some D min > 0. We will design a controller that satisfies both these bounds. Moreover, equation ( 4) is imposed to avoid a wash-out of the bacteria of the reactor (we do not prove this property due to space limitation).

Bounded state

Based on that assumption and for D min and D max fixed, it can be shown that the solutions are bounded: there exist S 1min , T 2min > 0 such that, for any controller D min ≤ D(X 1 , S 1 , X 2 , S 2 ) ≤ D max and for any initial condition in the positive orthant (X 1 (0), S 1 (0), X 2 (0), S 2 (0)) ∈ IR 4 + , there exists a finite time T > 0 after which the following four inequalities are valid for all t ≥ T :

S 1in < k 1 X 1 (t) + S 1 (t) < S 1in α , T 2in < k 3 X 2 (t) + T 2 (t) < T 2in α (7)
S 1min < S 1 (t) < S 1in , T 2min < T 2 (t) < T 2in (8)
These inequalities are not proven here due to space limitation: they are a consequence of the differentiation of the quantities k 1 X 1 + S 1 , k 3 X 2 + T 2 , S 1 and T 2 and result in the following lemma Lemma 1 Let 0 < D min < D max be fixed. Then, for any initial condition (X 1 (0), X 2 (0), S 1 (0), S 2 (0)) belonging to IR 4 + , and for given constants S 1in , S 2in such that Assumption 1 is satisfied, there exists a time T > 0 such that, for all t ≥ T , we have

X 1min < X 1 (t) < S 1in k 1 α 0 < X 2 (t) < T 2in k 3 α S 1min < S 1 (t) < S 1in T 2min < T 2 (t) < T 2in
along the solution of (1) for any choice of

D(t) ∈ [D min , D max ].

CONTROL DESIGN

We choose a simple proportional controller in the form

D = D max -D min 2 1 + sat S λmax + S λmin -2S λ S λmax -S λmin + D min (9)
where sat(s) = s max(|s|,1) (the controller is illustrated on Figure 1). As stated in Objective 1, this controller is not designed to regulate S λ at a prespecified value Sλ , but rather to ensure attractivity and invariance of the region of the state space where S λ belongs to an interval [S λmin , S λmax ]. Such a controller should be more robust than a controller aimed at exactly regulating the output. The main This controller is based on the following philosophy:

(i) if S λ ≥ S λmax then the flow is minimal: it prevents the pollution from leaving the plant in too large an amount; the pollution is lowered inside the plant and the bacteria grow in order to face the higher depollution requirement;

(ii) if S λ ≤ S λmin then the flow is allowed to be maximal because the pollution level is low enough to be certain that this maximal flow will not drive the system into the region where the pollution is too high;

(iii) if S λmin < S λ < S λmax then the controller is linear and built such that it is continuous at the boundaries of this region.

The description of the controller as (i)-(ii)-(iii) allows for the separate description of the controlled system (1)-( 9) in the three corresponding regions, that we will name Ω 1 , Ω 2 , and Ω 3 , respectively:

Region Ω 1 : D = D min The region Ω 1 is defined as

Ω 1 = {(X 1 , X 2 , S 1 , S 2 ) ∈ (IR + ) 4 |S 1 + λS 2 ≥ S λmax }
In this region, where S λ ≥ S λmax , the flow rate is rendered minimal to limit the outflow of pollutants. System (1) can be rewritten as

       Ẋ1 = (µ 1 (S 1 ) -αD min )X 1 Ẋ2 = (µ 2 (S 2 ) -αD min )X 2 Ṡ1 = D min (S 1in -S 1 ) -k 1 µ 1 (S 1 )X 1 Ṡ2 = D min (S 2in -S 2 ) + k 2 µ 1 (S 1 )X 1 -k 3 µ 2 (S 2 )X 2 (10)
This system can be analyzed as a cascade system between the (X 1 , S 1 ) subsystem and the (X 2 , S 2 ) subsystem. For any constant D min < µ 1max α , the state of the (X 1 , S 1 ) subsystem globally converges to the non-trivial equilibrium ( X1 , S1 ) =

S 1in -µ -1 1 (αD min ) k 1 α
, µ -1 1 (αD min ) . Also, the smaller D min is, the smaller S1 is. Because the solutions of the whole system are bounded, we know that the behavior of the whole system (10) can be deduced from the behavior of the (X 2 , S 2 ) subsystem on the manifold (X 1 , S 1 ) = ( X1 , S1 ). This system is

Ẋ2 = (µ 2 (S 2 ) -αD min )X 2 Ṡ2 = D min ( S2in -S 2 ) -k 3 µ 2 (S 2 )X 2 (11)
Generically, this system has two non-trivial equilibria because µ 2 is similar to an Haldane function; the equilibria are characterized by the two values of S 2 that are such that µ 2 (S 2 ) = αD min (S m 2 < S * 2 < S M

2 ). It is straightforward to show that S M 2 is an unbounded increasing function D min . Independently of the choice of D min , Lemma 1 shows that S 2 ≤ T 2 ≤ T 2in after a finite time. Also, if we take D min small enough, we can have S M 2 > T 2in , so that no convergence to the equilibrium corresponding to S 2 = S M 2 can take place and all solutions converge towards the equilibrium corresponding to S 2 = S m 2 . This equilibrium is characterized by Sλ = S1 + λS m 2 = µ -1 1 (αD min ) + λS m 2 , which can be made as small as we want by reducing D min . This ensures that system (10) has a single equilibrium, and that this equilibrium lies in the region where S λ < S λmax . We can show that this equilibrium is attractive for all initial conditions for system (10), so that we know that S λ = S λmax is reached in finite time. We have then shown attractivity of Ω 2 ∪ Ω 3 for D min small enough. We now have to show invariance of this set. On its border, (5) becomes:

Ṡλ = D min (S λin -S λmax ) -(k 1 -λk 2 )µ 1 (S 1 )X 1 -λk 3 µ 2 (S 2 )X 2
We can show that, in the region defined by the constraints ( 7)-( 8), we have (k 1 -λk 2 )µ 1 (S 1 )X 1 + λk 3 µ 2 (S 2 )X 2 ≥ M when S λ = S λmax for some M > 0. This shows that, for D min > 0 small enough Ṡλ < 0 when S λ = S λmax . We then see that, as long as D min is small enough, the region Ω 2 ∪ Ω 3 is attractive and invariant. We then state the following assumption to deduce Lemma 2:

Assumption 2 The minimal dilution rate D min > 0 is taken small enough.

where the exact extent of the "small enough" term is defined in the attractivity and invariance conditions stated before this assumption.

Lemma 2 Under Assumptions 1 and 2, there exists a finite time T after which the region Ω 2 ∪ Ω 3 is attractive and invariant for system (1) with the controller (9). This lemma ensures that the depollution objective is achieved by the controller; the pollution level will always be kept below S λmax once the controller has forced the system into that region. We will now study the behavior of the system in Ω 2 and check if Objective 1 is achieved.

Region Ω 2 : D = D max The region Ω 2 is defined as

Ω 2 = {(X 1 , X 2 , S 1 , S 2 ) ∈ (IR + ) 4 |S 1 + λS 2 ≤ S λmin }
In this region, where S λ ≤ S λmin , system (1) can be rewritten as:

       Ẋ1 = (µ 1 (S 1 ) -αD max )X 1 Ẋ2 = (µ 2 (S 2 ) -αD max )X 2 Ṡ1 = D max (S 1in -S 1 ) -k 1 µ 1 (S 1 )X 1 Ṡ2 = D max (S 2in -S 2 ) + k 2 µ 1 (S 1 )X 1 -k 3 µ 2 (S 2 )X 2 (12)
In Ω 2 , we only need to check the evolution of S λ (t), which follows the equation ( 5):

Ṡλ = D max (S λin -S λ ) -(k 1 -λk 2 )µ 1 (S 1 )X 1 -λk 3 µ 2 (S 2 )X 2 ≥ D max (S λin -S λmin ) -(k 1 -λk 2 )µ 1 (S 1 )X 1 -λk 3 µ 2 (S 2 )X 2
From Lemma 1, we know that there exists a finite time T > 0 after which X 1 (t) ≤ S 1in k 1 α and X 2 (t) ≤ T 2in k 3 α . We then have

Ṡλ ≥ D max (S λin -S λmin ) -(k 1 -λk 2 ) max S 1 ≤S λmin µ 1 (S 1 ) S 1in k 1 α -λk 3 max S 2 ≤ S λmin λ µ 2 (S 2 ) T 2in k 3 α
for all S λ ≤ S λmin . In order to have Ṡλ always positive, we impose the following assumption Assumption 3 Suppose that

D max > (k 1 -λk 2 )µ 1 (S λmin ) S 1in k 1 α + λk 3 max S 2 ≤ S λmin λ µ 2 (S 2 ) T 2in k 3 α S λin -S λmin (13)
As D max is upper-bounded because of equation ( 4), this assumption can be satisfied by picking the free parameter S λmin small enough. From this expression, we deduce the following lemma:

Theorem 1 Assumptions 1, 2, and 3 ensure that there exists a finite time after which Objective 1 is satisfied by system (1) with controller ( 9).

This theorem is a consequence of the observations made prior to its statement, which show that all solutions have to leave Ω 2 after a finite time, and of Lemma 2 which shows the same thing for Ω 1 .

All solutions then converge to the invariant set Ω 3 inside which the depollution objective is achieved. Note that attractivity and invariance of the region of interest is not directly ensured: the solutions first have to converge to the region where ( 7)-( 8) is satisfied (and we have shown that this takes place in finite time), and then we know that Ω 3 is attractive and invariant.

SIMULATIONS

We have implemented controller (9) on model (1). For the simulations, we have used the parameters of the model that were given in [START_REF] Bernard | Dynamical model development and parameter identification for an anaerobic wastewater treatment process[END_REF]. We then fixed the following "free" parameters as follows:

S λmax = 1.5; S λmin = 1.3; S 1in = 15; S 2in = 15; λ = 0.0064; D max = 0.5; D min = 0.05.

As can be seen from these parameters, the purpose of the control design is here to steer S λ into the interval [1.3, 1.5] with a control effort lying in the interval [0.05, 0.5]. We have considered (S 1 , S 2 , X 1 , X 2 )(0) = (15, 15, 0.1, 0.1) as initial conditions. This set is characterized by a low biomass at the start and a high pollution level in the reactor (S λ (0) = 15.96), coming from the large amount of S 1 in the reactor. The dilution rate is then set at the minimal level during the first two and half days. As can be seen on Figure 2, this forces a decrease of the pollution level S λ , S 1 and S 2 . Simultaneously, the biomasses X 1 and X 2 quickly increase. After 3 days, the pollution level settles at the desired value, between S λmin and S λmax . However, it is interesting to notice that this does not mean that the solution has reached its equilibrium: between day 3 and day 20, we observe a continuing increase of X 1 and X 2 , coupled with an increase of D; indeed, after three days, the reactor is able to treat the wastewater, but the dilution must stay moderate; the subsequent increase of biomass ensures that the plant can handle a higher dilution rate. After that, the equilibrium is reached.

CONCLUSION

In this paper, we have given a control law for the regulation of a model of anaerobic digestion with two bacteria. We have presented a control that regulates the pollution level: it ensures that the pollution level stays between a minimal and a maximal value while the dilution rate is also fixed between a minimal and a maximal value. No analysis of the actual behavior of the system inside the region where S λ belongs to the desired interval has been presented here, but a condition can be given to ensure that the system has a single equilibrium.

Our controller requires that a measure of the pollution level is available online. If it is not the case, we will need to design an observer that will help reconstruct the value of S λ from the available observations, namely the methane gaseous flow rate= k 6 µ 2 (S 2 )X 2 , and some measures of S λ (made with large time intervals in between them). No influent concentration knowledge is required.

Figure 1 :

 1 Figure 1: Form of the controller (9)

Figure 2 :

 2 Figure 2: Time evolution of the states, control D, and output S λ for the control system


J.-L Grognard

Gouzé

Positive control of Lotka-Volterra systems

Keywords: Predator-Prey, Lotka-Volterra, Positive control, Lyapunov design

We consider the n-dimensional Lotka-Volterra system of differential equation representing the predator-prey interaction between n species. In this paper, we will try to control the system by the mean of a sign-definite control law that is based on a classical Lyapunov function for Lotka-Volterra-systems.

Introduction

In order to describe the interaction between n species that are being the predator or the prey of each other, the Lotka-Volterra model _ x = diag(x)(Ax + a) [START_REF] Deleenheer | Accessibilty properties of controlled Lotka-Volterra systems[END_REF] is often used (where x P IR n + , a P IR n , A P IR n¢n , and diag(x) is a matrix containing the elements of the vector x on its diagonal). This system is obviously positive. The vector a describes the individual growth or death-rate of each species (when a i > 0, the species is growing in the absence of any other interaction; when a i < 0, it is dying). The diag(x)Ax term represents the quadratic interaction between the species. In the original Volterra paper [START_REF] Volterra | Variations and fluctuations in the number of coexisting animal species[END_REF], it was supposed that A was a skew symmetric matrix. Indeed, this assumption stems from the observation that, if species i is the predator of species j, the species i is benefiting from the predation in the quadratic form +a ij x i x j , while the prey is being consumed at the rate a ij x i x j , both terms of the interaction having the same magnitude in order to satisfy the mass-balance of the interaction (when the x i (t) state represents the mass of the ith species at time t).

Most of the work that has been devoted to Lotka-Volterra systems mainly concentrates on the analysis of the behavior of the solutions. In this paper, we will introduce some control to influence the behavior of the system. We will concentrate on a control action that can only act on the growth rates of the species, so that the model becomes

_ x = diag(x)(Ax + a + bu) (2)
1 where b P IR n and u P IR + . The u term can be seen as the rate of application of a pesticide on a field, the rate of release of a predator, or a single factor that influences the growth-rate of all the species, like lightning or temperature. We will suppose that this control action is always non-negative: this is quite natural for the rate of application of pesticide, for the rate of release of a predator (if we assume that they cannot be caught afterwards), for the light and temperature, if the only actuator that we have are a lighting or a heating system. We will not assume that all the elements of b have the same sign, so that the same control action can benefit a species i (where b i > 0) and harm a species j (where b j < 0). Such a control objective was already pursued in [START_REF] Goh | Optimal control of a prey-predator system[END_REF][START_REF] Kolmanovskii | Control of a predator-prey system with intraspecies competition[END_REF] through optimal control theory, but those were limited to two-dimensional systems; a preliminary study of accessibility for n-dimensional Lotka-Volterra systems was however given in [START_REF] Deleenheer | Accessibilty properties of controlled Lotka-Volterra systems[END_REF] while a first controller for those n-dimensional systems was given in [START_REF] Gouzé | Global stabilization of n-dimensional population models by a positive control[END_REF].

The behavior of the uncontrolled system (1) is well documented (see [START_REF] Volterra | Variations and fluctuations in the number of coexisting animal species[END_REF][START_REF] Gouzé | Global behavior of n-dimensional Lotka-Volterra systems[END_REF]), and citing the work of Volterra: If there exists an equilibrium, and if the initial state is different from it, there will be fluctuations in the numbers of at least some of the species, and these fluctuations will not dampen. If those fluctuations occur for the pest species, it will most often result in peaks of the pest population that are higher than the pest population at the equilibrium. The control action will then be used to steer the solutions of the Lotka-Volterra system to the positive equilibrium of the uncontrolled system (that we denote e P IR n + ), so that those peaks are not present anymore and the pest population is monitored.

The existence of such an equilibrium implies that system (2) can be rewritten as

_ x = diag(x)(A(x e) + bu) (3)
where a = Ae. We will build a controller u(x) that will ensure global asymptotic stability of e inside the positive orthant with u non-negative.

The paper is structured as follows: in Section 2, we will study the controllability of system (3) and show that, in many cases, the system is uncontrollable with a positive feedback. In Section 3, we will develop a controller (for the cases where noncontrollability has not been shown), and we will illustrate its action in simulations in Section 4. Finally we will give some conclusions.

Controllability of Lotka-Volterra systems with nonnegative controls

In this paper, we will concentrate on the Lotka-Volterra predator-prey system

_ x = diag(x)(A(x e) + bu) (4)
where x; e P IR n + , b P IR n , A P IR n¢n is skew-symmetric and u P IR + .

In this section, we will outline cases where system (4) is not controllable so that, in those cases, we will not try and build a controller for the stabilization of the equilibrium. Indeed, we can show the following proposition Proposition 1 If det(A) = 0, then system (4) is not controllable with u ! 0. Moreover, for any neighborhood N of e, there exists x 0 P N such that x(t) (with initial condition in x 0 ) cannot be steered to e with non-negative control.

Proof: If det(A) = 0, one of the eigenvalues of A is zero, to which corresponds a left eigenvector v such that v T A = 0. We will now show that e is not reachable for some initial conditions in the positive orthant. Indeed, let us consider the time-derivative of the function

U(x) = v T ln(x)
along the solutions of (4) (where ln(x) = [ln(x 1 ); ¡ ¡ ¡ ; ln(x n )] T ). This results in

_ U = v T (A(x e) + bu) = v T bu
If we suppose, without loss of generality, that v T b ! 0, U can only increase along the solutions of (4) when the control action is constrained to being non-negative. As a consequence, if U(x(0)) > U(e), no control u(t) ! 0 can steer x(t) to e. As the gradient of U is non-zero at e, it is obvious that we can find x(0) as close as we want to e and such that U(x(0)) > U(e). For good measure, we will now build such a x(0) and show that it can be made as close as we want to e, so that the system is not even locally controllable in e.

Let us fix x j (0) = e j + for all j such that v j ! 0 and x j (0) = e j for all j such that v j < 0. With that choice, it is clear that

U(x(0)) > U(e)

for any given 0 < < min j Pf1;¡¡¡;ng (e j ). Therefore, we have that U(x(t)) ! U(x(0)) > U(e) for all t > 0, so that x(t) cannot converge towards e. It is also clear that we can take as small as we want and still show that e cannot be reached from x(0), so that there exists no neighborhood N of the equilibrium such that all of its elements can be steered to e.

2

It should be noted that Proposition 1 results in the non-controllability of the desired equilibrium when n is odd. Indeed, in this case, the skew-symmetric matrix A always has an eigenvalue in 0.

Moreover, when det(A) = 0, the existence of a positive equilibrium for (4) results

in the existence of a continuum of equilibria

x £ = e + v with v an eigenvector corresponding to the eigenvalue in 0 and P IR. The choice of e in the transformation of system (1) into (2) is therefore not unique.

There is a chance that some kind of controller can be build to steer x(t) from

x 0 to e when U(x 0 ) < U(e) and v T b > 0, but this would not result in stability of the equilibrium, and any kind of uncertainty could drive x(t) in the region where U(x(t)) > U(e), resulting in the impossibility of bringing x(t) back to e.

In the remainder of this text, we will consider that A is invertible.

Control design

In this section, we still consider system (4), but we now suppose that A is invertible. This directly implies that n is even. In this case, it is well known that system (4), with u = 0, has a first integral: V (x) = 1 T x e T ln(x)

where 1 = [1 1 ¡ ¡ ¡ 1] T . Indeed, the time-derivative of this functions is:

_ V = 1 T diag(x)(A(x e) +
bu) e T (A(x e) + bu) = x T (A(x e) + bu) e T (A(x e) + bu) = (x e) T A(x e) + (x e) T bu = (x e) T bu which is zero when u = 0.

Using V as a Control Lyapunov Function, we will render its derivative negative semi-definite. This is simply achieved with a feedback in the form

u = ( b T (x e)) (5)
where (s) = 0 when s 0 and s(s) > 0 when s > 0. This feedback results in the following evolution of the first integral:

_ V = (x e) T b( b T (x e))
which is negative if b T (x e) < 0 and 0 otherwise. We can then show the following result Proposition 2 The solutions of system (4) (with A invertible) with control (5) converge to the hyperplane b T (x e) = 0. Moreover, in the case where n = 2 and in the case where n = 4 and b = 1 (for P IR), the equilibrium e is globally asymptotically stable Proof: We have seen that the control (5) makes the time-derivative of the Lyapunov function V negative semi-definite. We will then conclude the analysis through LaSalle's invariance principle that states that the solutions of system (4) (with controller (5)) starting in a positively invariant compact set will converge towards the largest invariant set of the region where _ V = 0 inside . In this case, we can take the region surrounded by the level-set V (x) = V as compact set (for some V > V (e)).

This region is positively invariant, so that LaSalle's principle can be applied and the solutions converge to the largest invariant set of the region where _ V = 0 fx P jb T (x e) ! 0g. We will denote this invariant set .

We can see that the solutions converge to the intersection of with the set fx P jb T (x e) = 0g. Indeed, the solutions of (4) can only converge to a set of nonwandering points [START_REF] Guckenheimer | Nonlinear oscillations, dynamical systems, and bifurcations of vector fields[END_REF]. Considering the continuously differentiable function

Z(x) = b T A 1 ln(x) whose time-derivative is _ Z = b T A 1 A(x e) b T A 1 bu = b T (x e) 0
when x P , LaSalle's invariance principle indicates that lim t3+I b T (x(t) e) = 0 for all solutions with initial condition in (whose invariance indicates that x(t) stays in ). Therefore, any x P such that b T (x e) > 0 cannot be a nonwandering point, so that we deduce that all solutions of (4) with u given in (5) converge to a subset w of fx P jb T (x e) = 0g.

This set w contains the equilibrium x = e. It must now be examined if other solutions preserve the invariance of the hyperplane b T (x e) = 0 because those invariant solutions would be candidates to attract the interconnected system (4)-( 5). We

will then analyze the system on the hyperplane with u = 0, which is the value of the feedback when b T (x e) = 0.

We are able to handle two cases: n = 2 In this case, the global asymptotic stability of e is trivial: if a solution, other than x(t) = e stays on the hyperplane, it is at the intersection of the hyperplane and a level set of the Lyapunov function V (x) (> V (e)). In this case, this intersection results in two disconnected points of the hyperplane. Invariance of the hyperplane on these points cannot be achieved because they are no equilibria.

The only invariant solution of the hyperplane is then the equilibrium e, which is therefore globally asymptotically stable. We will now characterize the set defined by those three equalities.

The intersection of the hyperplane (a) and (b) define a two-dimensional plane in the 4-dimensional space. Indeed, they intersect in e (so that we know that they intersect in the positive orthant) and they are not identical because (a) does not contain the origin while (b) contains the origin. We can then isolate two of the four coordinates (x a ; x b ) (not necessarily (x 1 ; x 2 )) and isolate them in (a) (b) as functions of the other two coordinates (x c ; x d ):

x a

x b = C 1 x c x d + C 2 e
where C 1 P IR 2¢2 and C 1 P IR 2¢4 We then replace (x a ; x b ) with this function in (c), so that (c) is now a two-dimensional quadratic form. The set of all the potentially invariant solutions inside the hyperplane 1 T (x e) is then a quadratic form, that is an ellipse, a hyperbola or a parabola (containing e). Let us now consider a solution x(t) that would belong to this ellipse, this parabola, or the branch of the hyperbola that contains e. Because those are one dimensional objects containing a single equilibrium, any solution converges to the equilibrium in forward time or in backward time: we have lim t3+I x(t) = e or lim t3 I x(t) = e

This results in lim t3+I V (x(t)) = V (e) or lim t3 I V (x(t)) = V (e) This is not possible, unless x(t) = e because V (x(t)) must stay constant on the hyperplane (u = 0 implies _ V = 0). This unacceptable behavior is illustrated on the branch H 1 of the hyperbola that is shown on Figure 1: the potential solution crosses the level sets of V , which is unacceptable. Similarly, if x(t) is a solution that stays on the branch of the hyperbola that does not contain e, it will slide indefinitely on that branch and go to infinity (staying in the positive orthant or intersecting the borders of the orthant). This results in V (x(t)) going to infinity, which is impossible because V must stay constant.

This unacceptable behavior is illustrated on the branch H 2 of the hyperbola that is shown on Figure 1: the potential solution goes to the border x d = 0, so that V goes to infinity, which is unacceptable.

Those solutions sliding along those objects cannot exist, so that they do not belong to the largest invariant set in 1 T (x e), which we have then shown to be reduced to the equilibrium e. This equilibrium is therefore globally asymptotically stable.

2 For now, our analysis is limited to the case n = 2 and n = 4 (with b = 1) because, in more general cases, the computation of the time-derivatives of W results in a quadratic form for _ W , a cubic form for W ,... whose intersection is hard to compute, and is the object of current research. The approach that is developed in this paper is a Jurdjevic-Quinn approach to the control problem. However, in the proof of Proposition 2, we take a practical approach to show that the equilibrium is globally asymptotically stable by going back to the LaSalle principle, instead of showing the stability by computing the Lie Algebra that is used by Jurdjevic-Quinn [START_REF] Jurdjevic | Controllability and stability[END_REF].

Application

We will now consider two simple case of Lotka-Volterra systems in order to illustrate the efficiency of our controller. The first one is a "one predator-one prey" system in the form

_ x 1 = x 1 (x 2 2 2u) _ x 2 = x 2 ( x 1 + 1 u) (6)
where x 1 is the predator and x 2 is the prey. A single control action is available, which acts on the death-rate of the predator (increase it with u ! 0) and the growth-rate of the prey (decrease it with u ! 0). For example, this could be a pesticide that both kills predators and preys. As suggested in [START_REF] Guckenheimer | Nonlinear oscillations, dynamical systems, and bifurcations of vector fields[END_REF], the control action that will be applied is u = (2(x 1 1) + (x 2 2))

where we here define 8 < :

(s) = 0 when s < 0 1 when s > 1 s otherwise For an initial condition in x 0 = (3; 4), this results in the behavior illustrated on Figures 2 and3. Figure 2 shows that, when the solution is above the separating line 2(x 1 1) + (x 2 2) a control action is taken and the solution crosses the level set of V (x), but when the solution is below this line, no control action is taken so that the solution follows a level set of V (x). This is further illustrated by Figure 3: the time-evolution of x 1 and x 2 show that convergence actually takes place, while the evolution of u and V show that, between time 0:5 and time 3, no control action is taken (because it would result in an increase of V ), so that V stays constant during that time-span; the rest of the time, V decreases along the solution.

We will now illustrate our controller on a more intricate system containing two super-predator (x 1 and x 2 ), two preys (x 3 and x 6 ) and two intermediates of the foodchain (x 4 and x 5 ), for which we have

_ x 1 = x 1 ( +4x 3 +3x 4 13 u ) _ x 2 = x 2 ( +2x 4 +3x 5 9 u ) _ x 3 = x 3 ( 4x 1 +4 ) _ x 4 = x 4 (
We also see, on that model, that we can only act on the system by controlling the superpredator population. The target equilibrium is e = (1; 2; 1; 3; 1; 4) T . As suggested in this paper, we then apply a controller in the form u = (x 1 + x 2 3) [START_REF] Volterra | Variations and fluctuations in the number of coexisting animal species[END_REF] which results in the stabilization of the system. The behavior of the system is illustrated in Figure 4. We see that the two species that are illustrated (x 1 and x 6 ) converge to their equilibrium value (the other 4 species also converge). We can also see that the solution is quite oscillatory, with u alternating between 0 and positive values during Corresponding to that observation, we see that V decreases in steps, its value staying constant every time u equals 0.

This system illustrates the fact (that was already evidenced in two-dimensions in [START_REF] Goh | Optimal control of a prey-predator system[END_REF]) that it is possible to regulate the pest (the preys) by controlling the predator. Also, as long as the equilibrium value and the model are well-known, the form of (8) also illustrates that we only need to know the value of the species that are acted upon (x 1 and x 2 in this case).

Eliminating the necessity of knowing the exact value of the equilibrium in order to compute the constant term in [START_REF] Volterra | Variations and fluctuations in the number of coexisting animal species[END_REF] is the object of further research. We will try and introduce some adaptation in the control law so that the control law can be written u = (x 1 + x 2 (t)) with (t) converging to 3, and the stability of the equilibrium is preserved. : Time-evolution of x 1 , x 6 , u and V for the controlled system (7) with x 0 = (3; 4; 2; 5; 3; 6) as initial condition

Conclusion

In this paper, we have introduced a control law for the stabilization of the Lotka-Volterra predator-prey system through positive feedback. The stability analysis is based on LaSalle's invariance principle and is limited to a few cases. The extension of the analysis to the case where n is large (which applications in Section 4 show to be working) and the introduction of adaptation in the control law is the object of further research.

n = 4

 4 We here only consider the case where b = 1 (for other forms of b, our work is still in progress). The time derivative of W (x) = 1 T (x e) (we drop the factor) is_ W = x T (A(x e) + 1u) = e T Ax + 1 T xuAlong an invariant solution inside the hyperplane, this time derivative must be 0, so that we must have e T Ax = 0. Differentiating e T Ax inside the hyperplane results in e T Adiag(x)A(x e)If it exists, an invariant solution inside the hyperplane must then satisfy

Figure 1 :

 1 Figure1: Level sets of V (x) (dotted-lines) and branches of hyperbola (dash-dotted lines) that intersect, showing that no invariant solution other than x(t) = e is possible inside the hyperplane 1 T (x e) = 0

Figure 2 :Figure 3 :

 23 Figure2: Phase-plane of the controlled Lotka-Volterra system[START_REF] Jurdjevic | Controllability and stability[END_REF]. The dash-dotted line represent the separating "hyperplane" b T (x e) = 0, the dotted lines represent the level sets of V (x) and the remaining line represents a solution of (6) with x 0 = (3; 4) as initial condition (it is solid when a control is applied and dashed when u = 0)

Figure 4

 4 Figure4: Time-evolution of x 1 , x 6 , u and V for the controlled system (7) with x 0 = (3; 4; 2; 5; 3; 6) as initial condition


L Boukhalfa
email: leila.boukhalfa@esigetel.fr

P Minet

S Midonnet
email: serge.midonnet@esigetel.fr

A Solution for QoS Support in Wireless ad hoc Networks

More and more applications supported by MANETs require Quality of Service (QoS). Much research has been done to date on QoS in ad-hoc networks. In this paper, we present our solution to provide QoS support through different QoS components. We show that the scheduling component does not suffice to satisfy QoS flow requirements because of radio interferences. Interferences could decrease the application throughputs. This can be a real problem for applications that need bandwidth guarantees. To offer guarantees to QoS flows, we propose a solution made up of five QoS components.

I. INTRODUCTION

Mobile Ad-hoc NETwork (MANET) is an autonomous system of mobile nodes connected by wireless links. It is self-organizing, rapidly deployable and requires no fixed infrastructure. Ad-hoc networks have known a great success and now, they are opening up to civilian applications having requirements of Quality of Service (QoS) [START_REF] Boukhalfa | Mobile ad-hoc networks and QoS demanding applications[END_REF]. Hence, achieving QoS [START_REF] Demetrios | A glance at Quality of Service in Mobile Ad-Hoc Networks[END_REF] in MANET corresponds to a real need. The QoS, requested from the network, could be defined in terms of one or a set of parameters such as delay, bandwidth, packet loss, delay and jitter. MANET networks are faced with specific constraints: a) the limited bandwidth because of the reduced available radio resources, b) the highly dynamic topology because of versatile radio propagation and the node's mobility, c) the power constraints because network nodes rely on battery power for energy. These MANET specificities make difficult to achieve QoS in these networks.

The goal of this paper is to present a QoS support taking into account the interferences to provide the bandwidth requested by QoS flows. The reminder of this paper is organized as follows.

In section II, we present some elements influencing QoS. Section III shows how to support QoS in ad-hoc networks through different mechanisms. We also show that the WCBQ scheduler does not take into account radio interferences. We then describe our solution for QoS support in section IV. Finally we conclude this paper and present some future perspectives.

II. FACTORS INFLUENCING QoS

Several factors can have an impact on the QoS perceived by the user. Among these factors, we emphasize on the scheduling, the routing and the interferences.

A. WCBQ Scheduler

In a network, packet scheduling policy refers to the decision process used to select the next packet that will be transmitted. At present, many schedulers are used in wired networks such as First In First Out (FIFO), Stochastic Fair Queueing (SFQ), Fair Queueing (FQ), and CBQ. Whereas in wireless networks, only FIFO and PriQueue schedulers are used.

The scheduling policy adopted in our solution is inspired from the one used in wired networks. We recall that our aim is the QoS support in ad-hoc networks in order to differentiate services between different traffic classes. One solution is to provide a minimum part of the requested bandwidth to different traffic classes. This means that the medium capacity must be shared between traffic classes. We are then interested in the CBQ scheduler [START_REF] Floyd | Link-sharing and Resource Management Models for Packet Networks[END_REF] (Class Based Queueing) and we have extended it to the wireless environment. CBQ aims at carrying out two goals. The first one is that each class should be able to receive roughly its allocated bandwidth. The secondary one is that when some class is not using its allocated bandwidth, the distribution of the excess bandwidth among the other classes should not be arbitrary, but should be done according to their relative allocations. Hence, CBQ leads to a good resource utilization. To fulfill these two goals, CBQ requires three modules:

• Classifier: it inserts packets ready to be sent by the node in the appropriate class queue. • Estimator: it estimates the bandwidth used by each class in the appropriate time interval. This information is used to determine whether or not each class has received its allocated bandwidth. • Selector: using the information from the estimator, it has to decide which class queue is allowed to send a packet.

According to [START_REF] Floyd | Link-sharing and Resource Management Models for Packet Networks[END_REF][START_REF] Fragouli | Controlled multimedia wireless link sharing via enhanced class-based queueing with channel state-dependent packet scheduling[END_REF], a selector should implement two mechanisms which are the general scheduler and the link

A

Journées Doctorales Informatique et Réseaux -JDIR'07

sharing scheduler. The general scheduler is to be used to schedule the class queues if the allocated bandwidth for each class can meet the requirement. Otherwise, the linksharing scheduler is used to adjust the transmission rates. WCBQ associates with each class a queue, a priority and an allocated bandwidth (see Fig. 1). DATA_Queues are dedicated to receive data packets. As we distinguish tow classes of flows (see section IV.1), we assign distinct data queues to each flow class. CTRL_Queue is dedicated to receive control packets (e.g. routing packets). This queue has the highest priority, thus, it is served before DATA_Queues.

In [START_REF] Boukhalfa | Comparative evaluation of CBQ and PriQueue in a MANET[END_REF], we have shown by means of simulations that WCBQ provides the following properties: P1: it shares the node bandwidth between flows present on the node proportionally to their weights. P2: it minimizes the standard deviation of the average bandwidth except for forwarded flows with low throughput. P3: it minimizes the end-to-end delay except for forwarded flows with low throughput. P4: it minimizes the standard deviation of the end-to-end delay for all flows.

B. Optimized Link State Routing Protocol

OLSR [START_REF] Clausen | Optimized Link State Routing Protocol (OLSR)[END_REF] is an optimization of the wired link state routing protocol OSPF [START_REF] Moy | OSPF OSPF Version 2[END_REF] for mobile ad-hoc networks. Its innovation lies on the fact that it uses the MultiPoint Relay (MPR) technique. The MPRs of a node corresponds to a subset of its one hop neighbors that allows to reach (in terms of radio range) all two-hop nodes (see Fig. 2). The MPRs technique allows to reduce the control packet size (each node declares only the links with its one hop neighbors that selected it as MPR), and reduces the number of retransmissions when flooding control messages in the network: only the MPRs of the sender forward its packets.

OLSR considers two types of control messages which are neighbor messages, denoted "Hello", and Topology Control messages, denoted "TC". The first ones are received by all one hop neighbors, but they are not forwarded to further nodes. The second ones are flooded in the entire network via the MPR nodes. Periodically, each node broadcasts a Hello message containing the information about its neighbors and their link status. This allows each node to: (i) learn its neighbors at one and two hops and hence construct its neighbor table ; (ii) select its MPRs among its one hop neighbors to cover all its two-hop neighbors. In order to construct a topology table, each MPR node periodically sends a TC message containing the list of neighbors that have selected the source of the TC as a multipoint relay.

TC messages are forwarded in the entire network. Only the MPR nodes of the sender retransmit the received TC. This avoids useless retransmissions and hence optimizes flooding in the network. Each node of the network maintains a topology table, in which it records the information about the network topology obtained from TC messages. The routing table is built from the information contained in the neighbor and topology tables, using the Dijkstra algorithm. Therefore, if any of these tables is changed, the routing table is recalculated to update the route to each known destination in the network. Thus, OLSR provides optimal routes in terms of number of hops, which are immediately available when needed.

C. Radio Interferences

In ad hoc networks, the radio medium being shared, each packet is physically received by all nodes in the transmission range of the sender, whereas nodes in the interference area only detect a busy medium. In IEEE802.11 networks, the medium access is done by a CSMA/CA (Carrier Sense Multiple Access/Collision Avoidance) protocol, like for instance the 802.11b. Collisions lead to a decrease in the medium useful throughput [START_REF] Al Agha | Réseaux de mobiles et réseaux sans fil[END_REF].

Let us consider a scenario of 8 nodes and one flow f1. The flow f1 requests a bandwidth of 300kb/s. f1 is generated by node N0 toward node N9 (fig. 3). To illustrate the interference phenomenon, we measure the consumed bandwidth at the MAC level on route node N6 and on node N2 located in the interference area of route node N0. We note that (see Fig. 4) flow f1 has consumed 464kb/s on N2. It represents nearly five times the bandwidth requested by f1. Indeed, node N2 is disrupted by any packet of flow f1, once when N0 transmits, because N2 is in the interference area of N0, a second time when N1 transmits because N2 is in the transmission range of N1, a third time when N3 transmits because N2 is in its transmission range, a fourth time when N8 transmits because N2 is in its interference area, and a fifth time when the node itself transmits. For node N4, that does not belong to the route, the bandwidth consumed by f1on this node is nearly three times the bandwidth requested by f1. Indeed, N4 is in the transmission range of N0 and N1 and in the interference area of N2. These three nodes belong to the route of flow f1. Consequently, N4 is disrupted each time one of these nodes transmit. We conclude that because of the interferences, a flow consumes more bandwidth than it requests. This illustrates the necessity to take into account the interferences in all solutions managing quality of service with bandwidth requirements.

In the following, we assume that interferences caused by a transmitting node are limited to two hops, as usually done.

III. QoS SUPPORT FOR WIRELESS AD HOC NETWORKS

The maturity of wireless technologies on the one hand, and the evolution of applications on the other hand, justify the introduction of Quality of Service (QoS) in ad-hoc networks. The majority of Quality of Service algorithms used in wired networks relies on the knowledge of precise information concerning the network state. They consider a weak loss rate, a large available bandwidth and a stable network topology. Thus, these algorithms cannot be applied just as they are in a wireless environment. In the following, we present a QoS support designed for ad hoc networks.

A. QoS Components

In [START_REF] Boukhalfa | Mobile ad-hoc networks and QoS demanding applications[END_REF] we have presented a general QoS architecture and defined its different components illustrated in Fig. 5.

Among these components we are interested in the five following components:

• QoS model specifies the architecture in which services can be provided as well as the necessary mechanisms such as classification. The QoS model directly influences the functionality of the other components.

• Admission control is the mechanism that allows to accept or reject a new flow according to (i) the available resources on the path taken by this flow and (ii) the QoS requirements of this flow;

• QoS signaling is used to propagate QoS control information in the network, to reserve and release resources, as well as to generate the QoS reports that indicate the effectively measured QoS. QoS signaling can be associated with routing with or without QoS.

• QoS routing aims to find routes with sufficient resources to meet the application requirements but does not reserve resources.

• The scheduler determines the message transmission order according to the priorities given to QoS classes.

B. WCBQ and Interferences

In this section, we show that WCBQ does not manage interferences. Therefore, the best effort flows can degrade the quality of service of QoS flows already accepted.

Simulations are done with Network Simulator NS2 [START_REF]The network simulator -ns-2 v.2.1b7a[END_REF]. Simulation parameters are summarized in the following table: For WCBQ, we have calculated the weight φ(f j ) associated with each flow f j , present on the node N and requesting B(f j ) bandwidth units, as follows:

where n is the number of flows, having the same priority, present on the node N. Now, let us consider the following scenario:

We consider an ad-hoc network constituted by eight nodes (N0, ..., N7). We assume that each flow corresponds to one traffic class and all flows start and stop transmitting at the same time.

First, we consider two QoS flows having bandwidth requirements. The following table specifies source, destination and requested bandwidth for each flow. We measure the average bandwidth obtained by each flow at its destination node. Fig. 7, shows that each flow has received its requested bandwidth (300kb/s for f1 and 400kb/s for f2). Now, we introduce a best effort flow f0 (Fig. 8) where its source is N0, its destination is N1 and its requested bandwidth is 200kb/s. We measure the average bandwidth of each flow at its destination node in two cases:

Case1: QoS and BE flows have the same priority Simulation results (Fig. 9) show that (i) the bandwidth received by QoS flow f2 has fallen from 400kb/s (in absence of f0) to 337kb/s (in presence of f0). (ii) the bandwidth received by QoS flow f1 has decreased from 300kb/s ( in absence of f0) to 291kb/s (in presence of f0). On the other hand, Best effort flow f0 has received its requested bandwidth (200kb/s). We notice that the introduction of the BE flow f0 has generated interferences. These interferences have disrupted QoS flows f1 and f2 leading to the degradation of their quality of service.

Case2: QoS flows have a higher priority than BE flows Graph Fig. 7 In this case, though QoS flows f1 and f2 have a higher priority than best effort flow f0, the quality of service of QoS flow has been degraded by the introduction of BE flow f0. Indeed, the bandwidth received by QoS flow f2 has fallen from 400kb/s in absence of f0, to 339kb/s in presence of f0. Similarly, the bandwidth received by QoS flow f1 has decreased from 300kb/s in absence of f0, to 287kb/s in presence of f0. On the other hand, best effort flow f0 has received its requested bandwidth (200kb/s).

We can conclude that WCBQ shares the available bandwidth between flows according to their weight without taking into account the interferences generated by flows. Consequently, an admission control is necessary not only for QoS flows but also for best effort flows to take into account the interferences they can generate on QoS flows and to protect QoS flows already accepted.

IV. SOLUTION FOR QoS SUPPORT

In this section we present our solution of QoS support taking into account interferences generated by flows present in the network. This solution is made up of the following components: QoS model, Admission control, QoS routing, QoS signaling and scheduling.

First, we present the flow types considered in our solution and show how they are managed. Then we present the admission control rules of a new flow taking account the interferences generated by this flow. After that, we describe the extension of the routing protocol OLSR in order to provide routes satisfying the QoS requirements. Finally we show how to make coexist different flow types through the WCBQ scheduler.

A. QoS Model

We consider two flow types:

-QoS flows having QoS requirements expressed in terms of bandwidth, -Best Effort (BE) flows having no specific QoS requirements.

To share the medium bandwidth between QoS flows and BE flows, we will use a provisioning. The provisioning consists in reserving a percentage of the nominal bandwidth to each flow type. We consider then:

-ProvQoS N : provisioning of QoS flows on node N.

-ProvBE N : provisioning of BE flows on node N.

We assume that ProvQoS N and ProvBE N are global parameters of the network and they are identical on all network nodes. Two solutions can be proposed for the management of QoS and BE flows whether we authorize or not each flow type to exceed its provisioning: 1) Each of the two flow types can never exceed its provisioning. In this case, QoS flows consume a bandwidth lower or equal to the QoS provisioning, and BE flows consume a bandwidth lower or equal to the BE provisioning. 2) Each of the two flow types can exceed its provisioning. In this case, the bandwidth not used by one flow type can be used by the other, and when necessary, each flow type can recover its share of bandwidth used by the other one.

For an effective use of the node resources, we adopt the second solution i.e. each flow type can exceed its provisioning. We can distinguish three cases of bandwidth consumption of QoS and BE flows (Fig. 11).

Let us consider the following notations:

Case 1: no flow type exceeds its provisioning.

B. Scheduling

For the scheduling, we use WCBQ. As in case 2 of section III, QoS flows have a higher priority than BE flows. The highest priority is granted to the CTRL_Queue associated with control flows (e.g. OLSR packets).

C. Admission control

Let us recall that, the admission control is the mechanism deciding whether a new flow is accepted or not, depending on (i) the available resources in the network and (ii) the requirements of this QoS flow. Then, whatever the QoS required by a new flow f, this flow is accepted by the admission control if and only if: -the QoS of already accepted QoS flows is not compromised; -the QoS required by the flow f can be satisfied.

1) QoS flows with bandwidth requirements

In our solution, the admission control of QoS flows having bandwidth requirements takes into account the interferences i.e. a flow will be accepted only if the interferences that it generates are acceptable for already accepted flows and the QoS it will receive is compatible with that required taking into account the interferences generated by other flows. For that, the admission control must check for each route node that the QoS flow is supported by this node and by all its one and two hop neighbors. As the destination does not retransmit the flow which is intended to it, the admission control, checks only that the flow is supported by its destination. We present the admission control rules in section D.

2) BE flows BE flows have no specific QoS constraint, but an admission control is necessary to verify that they do not exceed their available bandwidth. The admission control of a new BE flow is carried out locally on each route node. It consists in checking, on each route transmitting node, that the new flow is supported by this node and by all its one and two-hop neighbors.

3) Computation of the needed bandwidth

We note that, because of the interferences, a flow f requiring a bandwidth B(f) at the application level, consumes really a bandwidth B real (f) at the MAC level, higher than B(f). This is true on any route node and on any neighbor node of a route node. That is due to the interferences. Before presenting the admission control rules, we show below, how to evaluate the bandwidth really consumed by a flow.

In our solution, the route is supposed to be straight or with a low curvature, so that a route node belongs to the interference zone of itself, at most its two predecessors and at most its two successors. Hence, the value of 5 in formula [START_REF] Boukhalfa | Mobile ad-hoc networks and QoS demanding applications[END_REF].

B real (f) ≤ coef.min(5, hop).B(f) (1)
Where: hop the number of hops from the source to the destination. coef a coefficient allowing to take into account the overhead induced by the MAC acknowledgement and the headings of the protocols: physical, MAC, IP and UDP. The coef also depends on the packet size. For example, for a QoS flow whose packet size is equal to 500 bytes, and with a medium of 2Mb/s, the value of coef is equal to 1.144.

We note that the value coef.min (5, hop).B(f) corresponds to the maximum bandwidth that a flow can consume on a node i.e. the bandwidth really consumed by a flow on any node is never higher than coef.5.B(f) with our assumptions.

4) Admission control rules

After having calculated the bandwidth really consumed by a flow, we present below the rules of the admission control.

The admission control is performed for the two flow types QoS and BE. It consists in checking:

• For each route node N (except the destination) and for each node M at a distance lower than or equal to two hops of N :

-For a QoS flow f with bandwidth constraints: Where :

BQoS a N = max (ProvQoS N -BQoS u N , available N ) BBE a N = max (ProvBE N -BBE u N , available N ) Available N = (ProvQoS N -BQoS u N ) + (ProvBE N -BBE u N )
We will show in the IV.4.B how to calculate the available QoS bandwidth BQoS a as well as the available best effort bandwidth BBE a .

D. QoS Routing

The OLSR routing protocol with QoS support aims at finding:

-for QoS flows, the shortest route satisfying the requested bandwidth. -for BE flows, the shortest route.

The OLSR extension which we propose consists in: (i) modifying the choice of the multipoint relay and (ii) adding information in control messages Hello and TC, information necessary to the admission control and the QoS routing. We also present the rules of admission control adapted to this extension.

1) Selection of MPRs according to the available bandwidth

In an ad hoc network, the native OLSR protocol provides an optimal route to any destination in the network. This route is optimal in terms of number of hops but does not take into account the requirements of QoS flows. For a QoS flow, we need to find a route which satisfies the required quality of service. However, the route found by OLSR consists of MPR nodes. This is why we perform the MPR selection according to the QoS local available bandwidth denoted BQoS a .

In the extension we propose, multipoint relays are selected so as to reach the two hop neighbors through a one-hop neighbor with the maximum QoS available bandwidth (BQoS a ) i.e. if a two-hop neighbor can be reached by several one-hop neighbors then the one having the larger BQoS a is selected. Because we have taken into account the bandwidth to select the MPR nodes, the MPRs are called MPRBs.

2) Evaluation of the available bandwidth for QoS and BE

The knowledge of the QoS local available bandwidth (BQoS a ) is necessary for the MPRB selection as well as for the admission control of QoS flows. On the other hand, the knowledge of best effort local available bandwidth (BBE a ) is necessary for the admission control of BE flows. We calculate the BQoS a and the BBE a on a given node N as follows:

BQoS a N = max (ProvQoS -BQoS u N , available N ) BBE a N = max (ProvBE -BBE u N , available N )
where:

available N = (ProvQoS -BQoS u N ) + ( ProvBE -BBE u N ).
The QoS available bandwidth (or BE available bandwidth) is calculated according to the QoS used bandwidth (BQoS u ) and the BE used bandwidth (BBE u ). The BQoS u (or BBE u ) is calculated according to the QoS load and the BE load.

• Evaluation of the load for QoS and BE

We define the QoS load (QoS_ch) on a given node N during a time interval T as the sum of QoS bytes transmitted by the node N during T. We note that QoS bytes include bytes of QoS flow data and bytes of control traffic.

Where MC is the medium capacity. We also define the BE load (BE_ch) on a given node N during a time interval T as the sum of BE bytes transmitted by the node N during T.

Each node broadcasts this information (QoS_ch and BE_ch) in the Hello messages. Consequently, each node in the ad-hoc network knows the loads QoS_ch and BE_ch of all its one and two-hop neighbors.

• Evaluation of the bandwidth used by QoS and BE

The QoS used bandwidth (or the BE used bandwidth) on a given node N is equal to the QoS (or BE) load on N plus the sum of QoS (or BE) loads on the one or two hop neighbor nodes of N:

Where: V: the one and two hop neighbor set of node N MC: Medium capacity Coef: a coefficient depending on packet size. It takes into account the overhead generated by MAC acknowledgement and protocol headers: physical, MAC, IP and UDP. The coef value is identical to that used for the evaluation of the really consumed bandwidth by a flow.

(

)

MC coef ch QoS ch QoS BQoS V N N u . _ _ ⋅ + = ∑ ( ) MC coef ch BE ch BE BBE V N N u . _ _ ⋅ + = ∑ MC T bytes QoS ch QoS ⋅ = ∑ _ _ MC T bytes BE ch BE ⋅ = ∑ _ _

3) Modification of Hello and TC messages

We have extended the Hello and TC messages in order to convey the necessary information for QoS routing and admission control. A Hello message, sent by a node, contains the following information: -its address, its QoS_ch, its BE_ch, its BQoS a and its BBE a .

-the address, the QoS_ch, the BE_ch, the BQoSa and the BBE a of any one hop neighbor with the link status.

From the Hello messages, each node in the network can know the BQoSa of all its one and two hop neighbors. Thus, each node can select its MPRB set. A TC message contains the following information: -address of the TC sender, -BQoS a of the TC sender, -BQoS min which correspond to the minimum BQoS a of all the one and two hop neighbor of the TC sender, -Address of the MPRB selectors, -BQoS a of the MPRB selectors.

From the received TC messages, each node builds its topology table.

4) Route Selection

From its neighbor and topology tables, each node builds its routing table using Dijkstra algorithm. The intermediate nodes of routes toward each destination are MPRB nodes.

• Route selection for QoS flows

When a new QoS flow f is generated on a source node, this source node selects the shortest route offering the demanded QoS by applying Dijkstra algorithm on a copy of the topology and the neighbor tables in which only nodes offering the demanded QoS are present.

The admission control of a new QoS flow is performed on the source node. According to the information it maintains from Hello and TC messages, the source cannot verify correctly the second condition of admission control seen in section IV.2.D because it does not know the BQoS a of all neighbors at one and two hops of each node belonging to the route.

In our solution, a QoS flow f is accepted if and only if for each node N on the route, f is supported by (i) the node having BQoS min which corresponds to the minimum of BQoS a of all one and two hop neighbors of node N and (ii) the node undergoing the maximum of interferences generated by f i.e. the node having B max real (f) which corresponds to the maximum of B real (f) on all one and two hop neighbors of N.

So, for this solution, the admission control of a new QoS flow f consists in checking on the source node and for each route node N (except the destination):

B N real (f) ≤ BQoS a N B max real (f) ≤ BQoS min
On the destination node D checking that:

B D real (f) ≤ BQoS a D
If the flow is not accepted on one of the route nodes or on one of the neighbors of one of the route nodes, the flow is rejected. Else, when the route satisfying the requested QoS is found, it will be fixed in order to perform source routing i.e. the list of node route addresses will be included in the header of flow packets. In this way, all packets of this flow will follow the same route to reach the destination. This route is recalculated periodically to verify if there exists either a shorter route satisfying the QoS or a broken link.

• Route selection for BE flows

Best effort flows are routed hop by hop and the admission control of these flows is performed locally on each route node and for each packet. Hence, when a new BE flow f is generated on a source node, this source node checks for each packet, if the destination node exists in its routing table. If the destination does not exist, the packet is rejected. Else the node performs a local control admission for this packet to verify if the flow is supported by itself and by all its one and two hop neighbors. If so, the flow is transmitted toward the next node according to the routing table. We note that, for each packet of a new BE flow f, the admission control consists in verifying on each route node N (except the destination):

B N real (f) ≤ BBE a N B max
real (f) ≤ BBE min BBE min is the minimum available bandwidth for BE flow in the one and two hop neighborhood of N. It is computed from BBE a values received in the Hello messages.

V. PERFORMANCE EVALUATION

In this section we report performance evaluation of the QoS support described in the previous section. We compare the obtained performances with our solution and those obtained by native OLSR. For this purpose we use the NS2 simulator with parameters given in table I of section III. However, the number of nodes is now 50. We consider two QoS flows (f1 and f2) which receive their requested QoS and then, we introduce eight best effort flows (f3,…,f10). After that, we measure the average bandwidth received by each flow at its destination node. Nodes distribution in the flat area is given by Fig. 12, and flows characteristics are given in table III. The provisioning on any node for QoS and BE flows is 1400kb/s and 600kb/s respectively. The load is computed on each node every 2 seconds. Simulation results show that QoS flows have a QoS close to that requested despite the introduction of BE flows. Their requested and obtained bandwidths are depicted in Fig. 13. Indeed, QoS flow f1 has obtained 120kb/s, QoS flow f2 has obtained 140kb/s. On the other hand, BE flows f3,…,f10 have shared the available bandwidth on the source node N29 and each node has obtained 10kb/s.

We have also measured the bandwidth received by each flow using native OLSR (see Fig. 13). We can notice that the quality of service received by QoS flows using QoS support is better than using native OLSR: see for instance the throughput granted to QoS flow f2, it is equal to 26kb/s with native OLSR and 140kb/s with our QoS support. In this paper we have proposed a new QoS support for mobile ad-hoc network taking into account radio interferences. The OLSR routing protocol has been extended for QoS signaling and QoS routing. An admission control has been integrated. We can notice that the QoS support does not require any additional OLSR message. Therefore, the overhead in OLSR message sent by a node each second is kept reasonable. Simulation results show that the accepted QoS flows received the requested throughput. Their QoS is not degraded by the introduction of BE flows. In a further work we will extend our solution to support flows with delay constraint. We will also show that our solution supports node mobility.

Fig. 2 .

 2 Fig.2. Multipoint relays of node Src

Fig. 4 .

 4 Fig.5. QoS Components

Fig. 6 .Fig. 8 .Fig. 7 .Fig. 9 .

 6879 Fig.6. Scenario of 8 nodes and 2 flows

N

  : available QoS bandwidth on node N. BBE a N : available BE bandwidth on node N. BQoS u N : QoS bandwidth used on node N. BBE u N : BE bandwidth used on node N. ProvQoS N : provisioning granted to QoS flows on node N ProvBE N : provisioning granted to BE flows on node N.

Case 2 :Case 3 :Fig. 10 .Fig. 11 .

 231011 Fig.10. Measured average bandwidth of f0 f1 and f2

•

  For the destination node D -For a QoS flow f with bandwidth constraints:

Figures

  Figures 14 and 15 represent the obtained instantaneous bandwidth received by each flow with respectively QoS support and native OLSR. With native OLSR the instantaneous bandwidth obtained by each flow is very chaotic. Whereas, with QoS, support it has weak oscillations around the requested bandwidth.

Fig. 13 .Fig. 12 .

 1312 Fig.13. Average measured bandwidth with QoS support and native OLSR